操作系统复习

学校课本

按章学校的课本编排知识布局,后按照一些考研辅导书补充

• 本笔记规范遵守条例:记号规范

第一章 操作系统引论

操作系统提供的三大接口

• 图形接口
• 命令接口
• 系统调用
  • 相当于程序接口

库函数是高级语言提供的封装系统调用相关的函数

什么是操作系统

计算机系统

操作系统的概念

用户环境的观点

从用户的角度看，操作系统是用户与计算机硬件系统之间的接口，用户通过操作系统来使用计算机系统，即用户在操作系统的支持下，能够方便、快捷、安全、可靠地操纵计算机硬件资源，运行自己的程序。
用户可通过以下三种方式使用计算机:
①直接使用操作系统提供的键盘命令或Shell 命令语言;
②利用鼠标点击窗口中的按钮、菜单等图标，以执行相应的应用程序，如 Windows操作系统的图形用户接口;
③在应用程序中调用操作系统的内部功能模块，即系统调用接口。这些接口为用户开发和运行应用软件提供了便利的环境和手段。

资源管理的观点

把操作系统看作系统资源的管理者，是目前关于操作系统描述的主要观点。
现代计算机系统通常包括各种各样的资源，总体上可分为处理器、存储器、IO设备和文件四类，因此，操作系统的功能就是负责对计算机的这些软、硬件资源进行控制、调度、分配和回收，解决系统中各程序对资源使用请求的冲突，保证各程序都能顺利完成运行。

虚拟机观点

一台完全无软件的计算机系统称之为裸机，即使其功能再强，也是难于使用的。
如果在裸机上覆盖一层IO设备管理软件，用户便可以利用它所提供的IO命令，方便地进行数据的输入和输出。此时用户所看到的机器将是一台比裸机功能更强、使用更方便的机器，通常把覆盖了软件的机器称为虚拟机。如果在IO设备管理软件上再覆盖一层文件管理软件，则用户可利用它提供的文件管理命令，方便地进行文件的存取。如果在文件管理软件上再覆盖一层面向用户的窗口软件，则用户便可在窗口环境下更加方便地使用计算机，形成一台功能更强的虚拟机。

操作系统的发展与分类

操作系统的发展

手工操作阶段

早期的计算机只配备有硬件，没有操作系统，程序的装入、调试以及控制程序的运行都是通过控制台上的开关来实现的，用户也只能使用机器语言进行编程。
这种工作方式需要很多人工干预，形成了手工操作慢但处理机快的所谓人机矛盾，并且使用不方便。

单道批处理系统

在单道批处理系统中，设置了一个能完成作业自动转换工作的程序，该程序被称为监督程序，当操作员把一批作业交给系统后，就由监督程序控制这一批作业的自动运行。

多道批处理系统

在20世纪60年代中期引入了多道程序设计技术，形成了多道批处理系统。其基本思想是把用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”;然后由作业调度程序按一定的算法从后备队列中选择若干个作业同时装入内存，在管理程序的控制下交替执行，共享CPU和系统中的其他各种资源，每当正在运行的程序因某种原因(如等待IO操作的完成)不能继续运行时，CPU 立即转去执行另一道程序

分时操作系统

分时系统具有多路性、独立性、及时性和交互性特征，而交互性是其最重要的特征之一。

实时操作系统

实时系统与分时系统都具有多路性

分时系统按照分时原则为多个终端用户服务;而实时控制系统的多路性则主要表现在经常对多路的现场信息进行采集以及对多个对象或多个执行机构进行控制。

实时系统与分时系统都具有独立性

每个终端用户在向分时系统提出服务请求时，是彼此独立的操作，互不干扰;而在实时控制系统中信息的采集和对象的控制，也互不干扰。

实时系统与分时系统都要求及时性

实时系统是以控制对象所要求的开始截止时间或完成截止时间来确定其及时性的，一般为秒级、百毫秒级直至毫秒级，甚至有的要低于100微秒。而分时系统的及时性是以用户所要求的响应时间来确定的，一般为秒级，实时系统要求的及时性更高。

实时系统与分时系统都具有交互性

实时系统的交互仅限于访问系统中某些特定的专用服务程序;而分时系统则能向终端用户提供数据处理、资源共享等多种服务，分时系统的交互性是其主要特征。

实时系统与分时系统都要求可靠性

分时系统要求系统可靠，而实时系统要求系统高可靠度，因为实时系统的任何差错都可能带来巨大的经济损失甚至无法预料的灾难性后果。因此，实时系统往往采取多级容错措施来保证系统的高可靠性。

微机操作系统

Linux,Windows

网络操作系统

网络通信管理

主要负责实现网络中计算机之间的通信。

网络资源管理

对网络中共享的软硬件资源实施有效的管理，保证用户方便、正确地使用这些资源，提高资源的利用率。

网络安全管理

提供网络资源访问的安全措施，保证系统中共享资源的安全性。

提供网络服务

包括文件传输服务、打印服务、电子邮件服务等。

分布式操作系统

此外，分布在系统中各个站点上的软、硬件资源，可供全系统中的所有用户共享，并以透明的方式访问它们，用户看到的不是多个分散的处理单元，而是一个功能强大的计算机系统。

嵌入式操作系统

嵌入式操作系统具有微小、实时、专业、可靠、易裁剪等优点。

操作系统的特征和功能

操作系统的特征

并发性

共享性

虚拟性

异步性

操作系统的功能

处理器管理

存储器管理

设备管理

文件管理

提供用户接口

命令接口

操作系统向用户提供一组键盘操作命令。用户从键盘上输入命令，命令解释程序接收并解释这些命令，然后调用操作系统内部的相应程序，完成相应的功能。

程序接口

操作系统内核与应用程序之间的接口称为应用程序接口，是为应用程序在执行中访问系统资源而设置的，通常由一组系统调用组成，每一个系统调用都是一个能完成特定功能的子程序。系统调用只能在程序中调用，不能直接作为命令从键盘上输入执行。

图形接口

这是为了方便用户使用操作系统而提供的图形化操作界面。用户利用鼠标等交互设备，通过操作窗口、菜单、图标等图形用户界面工具，可以直观、方便、高效地使用系统服务和各种应用程序及实用工具，而不必像使用命令接口那样去记住命令名及格式。

操作系统用户接口

三种

命令接口(Command Line lnterface，CLI)

程序接口(Application Programming Interface，API)

图形接口(GraphicalUser Interface，GUI)

操作系统内核结构

三种

整体结构

• 整体结构模型又称为单体结构模型或无结构模型。
• 在整体内核结构模型中，没有明确定义和划分操作系统的结构，整个内核是由一组函数集合构成的，函数之间可以任意相互调用
• 例如 CP/M、MS-DOS、Linux系统以及早期的Unix系统等。
• 优点
  • 应用程序和底层硬件之间的接口简单直接
  • 系统效率较高
  • 具有良好的运行性能
• 缺点
  • 模块独立性差
  • 调用关系复杂，修改引入的变化可能影响到其他模块，后续系统的维护和扩充变得很困难
• Linux内核引入动态模块机制加以改进

层次结构

• 层次结构力求模块之间的调用清晰有序，减少各个模块之间的互相调用和互相依赖，特别是可能出现的循环调用问题
• 层次结构模型中，各层之间的模块只能单向依赖或单向调用，最底层(第0层)与低层硬件交互，而高层(第N层)为应用程序和用户提供接口。
• 每层都是利用较低层所提供的功能实现的，并且只有相邻层之间才能通信。
• 优点
  • 层次结构的各层相对独立
  • 把整体问题分解为若干简单问题在不同层次上解决，将复杂操作系统分解为功能相对单一的许多层次
  • 组织结构和相互依赖关系清晰明了
  • 简化了系统的设计和实现
  • 易于对操作系统增加或者替换一层而不影响其他层次
  • 保持接口一致
  • 易于维护、修改和扩充。
• 缺点
  • 令系统开销增加而效率降低
  • 层次的定义并不是一件容易的事情，各层次包含的内容难于确定。
• 分层操作系统有VAX/VMS和 Unix等。

典型操作系统介绍

本章小结

本章习题

第二章 操作系统硬件基础

只有第三小节是重点

处理器计算

处理器指令

寻址方式

寄存器

处理器特权级

存储系统

高速缓冲寄存器

内存

堆栈

磁盘

磁盘结构

非易失性存储

局部性原理

中断和时钟

中断和异常

系统调用

什么是系统调用

它是一种用户在程序一级请求操作系统内核完成某种功能服务的过程调用，每种操作系统都会提供多达几百种的系统调用，每一个系统调用都是完成某种特定内核功能的一个函数，比如大家熟悉的读磁盘操作read()、终端显示printf()等，这些系统调用表面上看起来与一般的过程调用(比如三角函数 cos(O))完全相同，但实际上有很大的区别:一般的过程调用，其调用程序与被调用过程运行在相同的状态——系统态或用户态，所以可直接由调用程序转向被调用过程;而系统调用则是调用程序运行在用户态，被调用过程运行在系统态，因而不允许由调用程序直接转向被调用过程，需要通过中断及陷入机制，先由用户态转换到系统态，经内核分析检查后，才能转向相应的内核被调用过程执行。

系统调用号、系统调用服务例程及系统调用入口表

• 每种操作系统都会提供几百种系统调用，为了唯一的标识每一个系统调用，系统为每个系统调用都赋予了一个唯一的编号，称为系统调用号
• 用户程序是使用系统调用号而不是系统调用名称来告诉系统到底是要执行哪个系统调用
• 每个系统调用都会完成操作系统内核的某项服务功能，具体是由一个特定的内核函数来实现的，称为系统调用服务例程。
• 系统为了能快速地根据用户进程请求的系统调用号找到它所对应的服务例程，设置了一张系统调用入口表，用于关联系统调用号及其对应服务例程的入口地址，每个系统调用占一表项

系统调用号及参数的传递

Linux是利用一组寄存器来传递参数的,在x86-32系统上，EBX/ECX/EDX/ESIEDI按顺序依次存放前五个参数，因此每个参数的长度不能超出寄存器长度(即32位)，且参数个数不能超过五个，若某系统调用确实需要六个及以上的参数时，则只能用一个单独的寄存器指向进程地址空间中这些参数值所在的一个内存区

$\bigstar$ 系统调用处理流程

系统时钟

本章小结

本章习题

第三章 进程管理

进程的引入

进程的并发执行及特征

程序的并发执行

空闲等待时间减少，提高了资源利用率和系统吞吐量

程序并发执行的特征

间断性

表现出“执行-暂停-执行”的间断性活动规律

失去封闭性而导致程序运行结果出现不可再现性

静态程序结构不能支持并发运行的实现

进程管理功能

进程控制

进程互斥与同步

进程通信

调度

进程的概念

进程的定义和特征

进程的定义和特征

动态性

并发性

独立性

异步性

进程映像

• 进程映像是进程的实体组成
  • 程序段
  • 数据集
  • PCB：通过进程控制块（PCB）描述进程的状态信息、本身属性、对资源的占用及调度信息等
  • 栈
    • 系统在创建进程的时候会为其建立两个栈
      • 用户栈
      • 系统栈

进程与程序的区别和联系

程序是静态概念，进程是动态的

• 程序是静态概念，本身可以作为软件资源长期保存
• 进程是程序的一次执行过程，是动态的，有一定的生命周期

  进程是调度的基本单位，程序不能参与并发执行

• 进程是一个能独立运行的单位，是系统进行资源分配和调度的基本单位，能与其他进程并发执行，而程序因其自身不能描述并发运行过程中的动态信息，所以无法参与并发运行

程序和进程并非是一对一的关系

• 一个程序可由多个进程共享
• 一个进程在其执行过程中又可顺序地执行多个程序

进程状态与转换

进程的三种基本状态

就绪状态

运行状态

阻塞状态

创建状态和终止状态

创建状态

正在被创建，但还没有创建完成，尚未加入就绪队列时的状态，此时进程还不能参与CPU调度

终止状态

当前运行进程完成自己的工作后正常结束，或是运行中出现了无法克服的错误(如地址越界、使用非法指令等)而被异常终止时，将被系统强制结束，进入终止状态。

Linux进程状态解析

state

表示进程生命周期的各种状态

TASK_RUNNING

可运行状态。处于该状态的进程要么正在CPU上运行，要么位于就绪队列中等待CPU 调度运行。

TASK_INTERRUPTIBLE

可中断睡眠状态。因为等待某事件发生而阻塞睡眠的状态。当所等待的事件发生时，或者有其他异步信号到达时，该进程将被唤醒。

TASK_UNINTERRUPTIBLE

不可中断睡眠状态。与TASK_INTERRUPTIBLE类似，但不响应异步信号，只能被wakeup()(唤醒函数)显式唤醒。

TASK_STOPPED

暂停状态。当进程收到SIGSTOP(暂停执行信号)、SIGTSTP(暂停执行信号)、SIGTTIN(暂停执行信号)或SIGTTOU(暂停执行信号)信号时进入暂停状态，不可被调度运行;之后收到SIGCONT(让一个暂停进程继续执行的信号)信号时恢复到可运行状态。

TASK_TRACED

跟踪状态。进程被调试器暂停下来，等待跟踪它的进程对其进行相关处理，例如执行ptrace()(跟踪函数)系统调用。

TASK_DEAD

终止状态。进程在退出过程中所处的状态，进程所占用的资源将被回收，很快将要被系统彻底销毁。

TASK_WAKEKILL

可响应致命信号的不可中断睡眠状态。这是 Linux内核引入的一种新状态，其属性与TASK_UNINTERRUPTIBLE相似，但是可以响应致命信号。

exit_state

表示进程终止过程中的状态,

EXIT_ZOMBIE

• 僵尸状态。
• 进程已终止，除了task_struct结构以及内核堆栈以外，其余所有资源已被系统回收，等待父进程调用wait()系列函数收集它的相关统计信息，如运行时间等。

EXIT_DEAD

进程的最终状态，表示父进程已经通过wait()系列函数完成其相关信息的收集，或者父进程已设置SIGCHLD(子进程结束时，向父进程发送的信号)信号的handler(处理函数)为SIG_IGN(不处理)，之后将很快被彻底销毁。所以EXIT_DEAD状态是非常短暂的，几乎不可能通过ps命令(ps命令是显式系统中进程的情况)捕捉到。

进程控制块

进程控制块(Process Control Block，PCB)是进程映像的重要组成部分，其中记录了用于描述进程情况及控制进程运行所需要的全部信息，是进程动态特性的集中反映。

进程标识信息

进程标识符

系统中的每个进程都有区别于其他进程的唯一标识符，以标识一个进程，可以用字符串或编号表示。系统为方便跟踪管理进程，创建进程时会为新进程分配一个整数编号，称为进程的内部标识符(pid)，通常是进程的创建序号;另外某些系统为方便用户对进程的访问，会为进程设置一个由字母、数字组成的字符串作为外部标识符，它是由创建者提供的。

用户标识符

每个进程都隶属于某个用户或用户组，以便于资源共享和保护。

家族关系

多个进程之间会互成家族关系，如该进程的父进程、兄弟进程、子进程等，通常也会记录在PCB 中。

进程调度信息

是与进程调度有关的一组信息

进程状态

说明进程当前所处的状态，如前面介绍的就绪状态、运行状态、阻塞状态等，只有处于就绪状态的进程才能参与CPU调度。

进程优先级

是系统进行CPU调度的重要依据，通常用一个整数数字表示。优先级高的进程会优先获得CPU运行。

其他调度相关信息

通常与系统的进程调度算法有关，比如进程在就绪队列中等待CPU的时间、进程已执行的时间总和、进程到运行结束还需要的CPU运行时间等。

事件

进程能够继续执行前需等待的事件，即进程阻塞的原因。

进程现场信息

当前运行进程因某种原因(如时间片到或等待某事件的发生等)而暂停运行时，需记录其断点处的运行环境信息，以便以后能从断点处恢复运行。主要是由处理器中各寄存器的内容组成

通用寄存器内容

又称为用户可见寄存器，是用户程序可以访问的一组寄存器，可用于传送和暂存数据、参与算术逻辑运算、保存运算结果等。大多数处理器有8~32个通用寄存器，而RISC(精简指令集计算机)类处理器中通用寄存器数量较多，可超过100个。

指令计数器的值

其中存放了进程将要执行的下一条指令的地址。

程序状态字PSW

其中包含CPU运行状态信息，如条件码、中断允许/禁止标志、处理器特权级、任务嵌套标志等。

栈指针

每个进程都有一到两个与之相关联的栈(用户栈或内核栈)，用于保存过程调用的参数及返回地址、系统调用的参数及调用地址以及为局部变量分配存储空间等。

进程控制信息

是控制和管理进程所需要的相关信息

进程的程序和数据在内存或外存的地址。

进程同步信息

进程运行过程中与其他进程之间发生的各种制约关系。

进程通信信息

记录进程运行过程中与其他进程之间发生的信息交换情况。

资源管理信息

描述进程运行过程中资源占有情况，如使用CPU的统计时间、内存占用情况、IO设备使用情况、打开的文件记录等等。

链接指针

系统为有效管理数量众多的PCB，通常将其组织成相关的队列，某个进程的PCB可能会同时处于多个队列中，如一个就绪进程，其PCB一定在某个就绪队列中，也同时在其父进程的子进程队列中。

进程控制

进程创建

进程图

进程图是用于描述进程家族关系的有向树，图中的节点代表进程,

引起进程创建的典型事件

作业调度

批处理系统中，提交给系统的作业通常存放在磁盘上，当作业调度程序按一定算法调度某个作业进入内存运行时，必须为该作业创建进程，分配必要的资源，并插入就绪队列。

用户登录

交互式系统中，用户从终端登录系统成功时，系统将为该终端用户创建一个进程，如Linux中的 shell进程，负责接收并解释执行用户输入的命令。

提供特定服务

比如用户进程要求打印一个文件，则系统会创建一个打印进程来完成该请求，用户不必等待打印工作结束就可以继续做其他的事情。

应用请求

比如一个文件服务器进程，当它监听到某个客户发来的文件下载请求时，可创建一个子进程来完成客户的文件下载请求，而它自己可继续监听其他客户的请求，提高对客户的响应速度。

进程创建原语

步骤

为新进程申请一个尚未被使用的pid和一个空白PCB。

为新进程分配必要的资源

比如建立进程地址空间，为其分配内存空间设置堆栈、存放程序、数据，此外还有文件、I/O设备以及初始时间片长度等。这些资源或者从系统分配，或者从父进程继承或共享。

初始化新进程的PCB

填入相关信息，如 pid，进程名、父进程标识符、处理器初始状态、进程状态、进程优先级、进程要执行程序的入口地址、进程同步信息、进程地址空间信息、资源分配情况等。

将新进程状态置为就绪状态

插入就绪队列，等待CPU 调度。

进程撤销

引起进程撤销的典型事件

正常结束而撤销

异常终止而撤销

应外界干预而撤销

①操作员或操作系统干预。比如系统发生了死锁，为解除死锁需要撤销一部分死锁进程;或者某进程进入死循环，也需要操作员来撤销它。
②父进程请求。当子进程完成父进程指派的工作后，父进程可以请求系统撤销该子进程。
③当父进程被撤销时，系统或自动撤销其所有的子孙进程。

进程撤销原语

进程阻塞与唤醒

引起进程阻塞和唤醒的典型事件

请求资源失败

等待某种操作的完成

前驱进程尚未完成

进程无新工作可做

进程阻塞原语

进程唤醒

Linux进程管理

• fork():创建一个普通进程，调用一次返回两次:在子进程中返回0，在父进程中返回子进程的pid。
• vfork():子进程能共享父进程的地址空间，且父进程会一直阻塞，直到子进程调用exit()终止运行或调用exec()加载另一个可执行文件，即子进程优先运行。
• clone():不同于前面两个，它接受一个指向某函数的指针和该函数的参数，刚创建的子进程将马上执行该函数。clone()允许子进程有选择性地继承父进程的资源，因此通常用它来创建线程。

进程同步

进程同步的基本概念

并发进程间的间接制约关系与进程互斥

临界资源

系统中某些资源一次只允许一个进程使用，这类资源称为临界资源

临界区

Hoare和 Hansen于1972年提出了临界区的概念:每个进程中访问临界资源的那段代码称为临界区。

同步机制应遵循的原则

• 空闲让进
  当没有进程处于临界区时，相应的临界资源为空闲状态，因而应允许任何一个请求进入临界区的进程立即进入自己的临界区,以有效利用资源。

• 忙则等待
  当已有进程进入临界区时，表示相应的临界资源正被访问，因而所有其他试图进入相关临界区的进程必须等待，以保证诸进程互斥访问临界资源。

• 有限等待
  对要求访问临界资源的进程，应保证该进程能在有限的时间内进入自己的临界区，以免陷入“永远等待”状态。

• 让权等待
  当进程不能进入临界区时，应立即释放CPU，以免CPU陷入“忙等”状态，以提高CPU利用率。

并发进程间的直接制约关系与进程同步

进程同步实际上就是相互合作的进程在某些关键点上相互等待和互通信息。

进程同步机制及应用

利用硬件方法解决进程互斥问题

禁止中断

利用专用机器指令解决进程互斥问题

• TSL指令
• Swap指令
  • 违反让权等待
  • 产生饥饿现象

利用软件方法解决进程互斥问题

不正确的软件算法

• 既然不正确就不做笔记了

Peterson算法

面包店算法

利用锁机制解决进程互斥问题

利用信号量机制解决进程互斥与同步问题

整型信号量机制

P/V两个原语操作:Р操作源于荷兰语Proberen(测试)，V操作源于荷兰语Verhogen(增加)，但后来的系统中通常称Р操作为down()或wait()，称V操作为up()或signal()，在本书中使用wait(和 signal()表示这两个原语操作。

• p = wait
• v = signal

记录型信号量机制

信号量集机制

利用信号量机制实现进程的互斥

经典进程同步问题

生产者-消费者问题

哲学家进餐问题

读者-写者问题

理发师问题

管程机制

管程定义

• 管程是一种需要编译器支持的进程同步机制
• Hansen给出的管程定义是:“一个管程定义了一个数据结构和能为并发进程(在该数据结构上)所执行的一组操作，这组操作能同步进程和改变管程中的数据”。
  • “数据结构”是对系统中各种共享软硬件资源的抽象描述，
  • 针对该数据结构所定义的一组操作则用来实现进程间的同步及各进程对该共享资源所需进行的多种不同操作。
• 管程是一个软件模块
  • ①管程的名字
  • ②局部于管程的共享数据结构的说明
  • ③对该数据结构进行操作的一组过程，每个过程完成进程对上述数据结构的某种操作
  • ④对局部于管程的共享数据结构进行初始化的代码。管程的语法结构描述如下:
• 特征
  • 局部于管程的数据结构只能被管程内的过程访问，任何外部过程不能访问;而管程内的过程也只能访问该管程内部的数据结构。
  • 一个进程若想访问管程内的数据结构(共享资源)，只能通过调用管程内的某个过程实现间接访问。
  • 任一时刻，管程中只能有一个活跃进程，即只能有一个进程在管程中执行管程的某个过程，其他任何调用管程的进程都将被阻塞，直到管程变成可用，这一特性使管程能有效地实现互斥。

条件变量

利用管程机制解决生产者-消费者问题

Linux同步机制解析

进程调度

进程调度的基本概念

调度的层次

高级调度

• 高级调度又称作业调度或长程调度
• 任务是根据系统的资源情况，按照一定的原则从外存上的后备队列中选择若干个作业调入内存
• 高级调度的运行频率较低，通常是以分钟甚至是小时为计时单位。
• 考虑两个问题
  • 第一，选择多少个作业进入内存。
  • 第二，选择哪些作业进入内存。

低级调度

• 低级调度通常称为进程调度，有时也称短程调度
  任务是决定就绪队列中的哪个进程获得处理器，然后由分派程序把处理器分配给该进程，并为它恢复运行现场，让其运行。
• 进程调度的运行频率很高，通常是十几毫秒就要运行一次，因而其调度算法也备受关注。
• 它是系统中最基本的一种调度，进程只有通过进程调度才能获得处理器运行，现代操作系统都具有进程调度功能。

中级调度

• 中程调度。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。
• 当内存紧张时，就将那些暂时不能运行的进程(如处于阻塞状态的进程)换出到外存，回收其内存空间给别的进程，通常称此时的进程状态为挂起状态;当内存空间较充裕时，又从外存选择若干具备运行条件的挂起进程换入到内存。
• 中级调度其实就是存储器管理中的对换功能，故又称为对换调度
• 发生的频率一般是几秒钟一次。
• 当存储管理机制中引入虚拟存储技术后，进程在内外存之间交换的内容通常是其部分代码或数据，而不是整个进程映像。

进程调度功能

排队程序

分派程序

上下文切换程序

进程调度方式

非抢占方式

• 优点是
  • 实现简单且
  • 系统开销小
• 缺点
  • 不能保证紧迫型任务(如实时进程)得到及时处理。

抢占方式

剥夺的原则可以是优先级、时间片或进程还需要的运行时间等，如在实时系统中常采用优先级原则，而在分时系统中通常采用时间片原则。

• 优点
  • 可以防止一个进程长期占用CPU
  • 为系统中的全体进程提供更好的服务
• 缺点
  • 系统开销比非抢占方式大，因为进程调度和切换的频率更高。

进程调度时机

当前运行进程已完成所有工作任务而结束，或者由于某种错误而被终止运行。

当前运行进程因需要等待某事件的发生而转变成阻塞状态，如等待IO操作的完成，或执行信号量的wait()操作时因条件不满足而被阻塞等。

在分时系统中，当前运行进程时间片用完。

采用基于优先级的抢占方式调度，当就绪队列中出现优先级更高的就绪进程时。

系统完成系统调用或中断处理后，在返回到用户态之前，通常会产生一次调度时机。

选择进程调度方式及调度算法应考虑的因素

系统设计目标

• 批处理系统应尽量提高各种资源，(尤其是CPU)的利用率、增加系统吞吐量及缩短作业的平均周转时间
• 交互式系统应能及时响应各用户的请求，让它们获得均衡的响应时间，尤其当系统中有大量进程并发运行时，应使每个用户感觉不到明显的延迟
• 实时系统必须保证各实时任务能得到及时、可靠的处理网络系统应使各网络用户方便、快速、安全地共享网络资源。

  调度的公平性

  一方面系统要考虑不同类型的进程应具有不同的优先级，保证紧迫型任务得到优先调度;另一方面也要尽量使系统中每个进程都能相对公平地共享CPU及其他系统资源，避免某些低优先级进程的任务完成时间被无限期地推迟。

资源的均衡利用

合理的系统开销

调度性能的评价指标

CPU的利用率

系统吞吐量

周转时间和带权周转时间

周转时间是指从作业提交给系统到作业处理完成所经历的时间，是评价批处理系统调度性能的重要指标之一，包括作业在外存后备队列中等待进入内存的时间、进程在就绪队列中等待CPU调度的时间、在CPU上执行的时间、在阻塞队列中等待IO完成或等待其他事件发生的时间之和。一组作业周转时间的平均值称为该组作业的平均周转时间。
带权周转时间在评价系统调度性能时，会同时考虑作业的周转时间及其要求服务时间，它是作业的周转时间与要求服务时间的比值，能更准确地反映用户的感受。

响应时间

是指从用户提交一个请求开始，到系统首次对该请求产生响应为止的时间间隔，是评价交互式系统调度性能的一个非常重要的指标。

对截止时间的保证

实时系统中的实时任务通常都对应一个截止时间，系统能否保证各实时任务在截止时间完成是评价实时系统调度性能的一个很关键的指标。

进程调度算法

先来先服务调度算法

• 先来先服务调度算法(First-Come，First-Served，FCFS)是一种最简单的调度算法，可同时用于作业调度及进程调度。

短作业优先调度算法

• 短作业优先调度算法(Shortest-Job-First，SJF)对作业调度和进程调度都适用
• SJF 算法能获得最短的平均周转时间。
• 缺点
  • 实现上有问题
  • 不公平的调度算法
  • 没有考虑任务的紧迫程度

高响应比优先调度算法

• 高响应比优先调度算法(Highest Response Ratio First,HRRF)在调度时既考虑作业(进程)的要求服务时间，同时也会考虑它们在后备队列或就绪队列中的等待时间。

优先级调度算法

• 缺点
  • 计算优先级有系统开销
  • 不能保证紧迫型任务得到及时处理

时间片轮转调度算法

时间片长度需要考虑的因素

• 系统的响应时间。
• 就绪进程的数量。
  就绪进程越多，为获得较满意的响应时间，时间片应适当缩短。(3)进程调度及上下文切换的时间开销。目前的切换开销一般在10 us左右，而常用的时间片长度是几十毫秒，因此切换时间只占时间片的很小部分。
• CPU运行指令的速度。
  CPU运行速度越快，时间片可适当缩短。

多级队列调度算法

每个队列有自己独立的调度算法

比如实时进程队列采用抢占方式的优先级调度算法，系统进程队列采用非抢占方式的优先级调度算法
交互式进程队列采用时间片轮转调度算法
批处理进程采用先来先服务调度算法或短作业优先调度算法等

各队列之间的优先级不同

进程所在队列固定

系统根据进程的属性，如进程类型、优先级等，将进程永久地分配到一个固定队列中，即只要该进程处于就绪状态，就一定位于最初所分配的就绪队列中。

• 优点
  • 实现简单
  • 调度开销小
• 缺点
  • 不够灵活且低优先级队列中的进程容易产生“饥饿”现象。

多级反馈队列调度算法

Unix采用

设置多个就绪队列

各队列内部按时间片轮转算法进行调度

各队列之间采用抢占式优先级算法调度

Linux调度算法解析

CFS调度器

进程通信

• 一些通信原语之类的？感觉不是很难

进程通信类型

消息缓冲队列通信机制

Linux进程通信机制

进程死锁

死锁的基本概念

死锁的概念

综上所述，若系统中存在一组进程(两个或两个以上)，且它们中的每一个都无限等待被该组进程中另一进程所占用的且永远无法释放的资源,那么这种现象就称为进程“死锁”，或说这一组进程处于“死锁”状态。

产生死锁的原因

竞争资源

资源的分类

• 可重用资源
  • 一次只能被一个进程安全地使用，且使用后资源不会减少。
  • 一个可重用资源被某进程释放后，可立即分配给其他进程再次使用
  • 如系统中的处理器、主存、辅存、各种外设等硬件资源，以及文件、数据库和信号量等各种软件资源。
• 消耗性资源
  • 被进程使用以及使用后就消失的资源
  • 如中断、信号、消息等。
• 可重用资源又可进一步分为
  • 可剥夺资源
    • 可剥夺资源是指状态可以被保存和恢复的资源
    • 这类资源若已经分配给某进程且还没有被使用完毕，则系统可以根据需要强制性地剥夺该进程对这个资源的使用权并分配给其他进程，这种剥夺不会对该进程的运行造成有害影响
    • 如处理器、主存等。如分时系统中当前运行进程时间片到时即便没有运行完成，系统也会把处理器分配给另外一个就绪进程执行。
  • 不可剥夺资源
    • 不可剥夺资源是指若该类资源被分配给某进程使用，则必须等到该进程使用完毕主动归还给系统后才能再次分配给其他进程，如果强制剥夺，则会对当前使用进程造成有害影响
    • 如绘图仪、打印机、磁带机、文件、数据库、队列等。多个进程对可剥夺资源的竞争不会引起死锁，但对不可剥夺资源的竞争则可能导致死锁的发生.
• 多个进程在竞争消耗性资源时也可能引起死锁。

进程推进顺序不当

产生死锁的必要条件

互斥条件

某个资源在一段时间内只能由一个进程占用，一旦将其分配给某进程后，必须等待该进程使用完成且主动释放它之后，才能再次分配给其他进程使用。

占有且等待条件

进程已占有至少一个资源，又申请新的资源，由于该资源已被分配给别的进程，则该进程阻塞，但它在等待新资源时，仍继续占有已分到的资源。

不可剥夺条件

一个进程所占有的不可剥夺资源在它使用完之前，系统不能强行剥夺，只能由该进程使用完之后主动释放。

循环等待条件

系统中若干进程之间对资源的占有和请求形成了循环等待的关系，此时环路中的每个进程都已经占有一些资源，同时又在等待其相邻进程所占有的资源。
由于这四个条件是由 Edward G.Coffman，Jr.于 1971年首次提出的，因此又称为Coffman条件。

处理死锁的基本方法

预防死锁

进程申请资源或系统分配资源时必须遵循某些预先设置的限制条件，以破坏产生死锁的四个必要条件的一个或几个，防止死锁发生。该方法容易实现，但由于严格限制了系统资源的分配和使用，造成资源利用率较低。

避免死锁

该方法并不事先采取各种限制措施去破坏产生死锁的必要条件，而是在进行资源分配的过程中，用某种方法防止系统进入不安全状态，从而避免发生死锁。所谓不安全状态，是指有可能导致系统发生死锁的状态。这种方法所加限制条件较预防死锁策略少，可获得相对较高的资源利用率和系统吞吐量。

检测和解除死锁

该方法不采取任何限制性措施，进行资源分配时也不检查分配的安全性，只要系统有空闲资源就可以分配，它允许系统在运行过程中产生死锁。但系统中会设置死锁检测机构，及时地检测出系统是否出现死锁，并确定与死锁有关的进程和资源;一旦检测到系统已出现死锁，立即采取相应的措施解除死锁。这种方法没有限制条件，能最大限度地利用资源，但实现难度也最大。

预防死锁

破坏占有且等待条件

思路？优缺点？
静态分配资源…..

破坏不可剥夺条件

破坏循环等待条件

避免死锁

安全状态

安全状态定义:设系统中有n个进程，若存在一个进程序列$$。使得进程$P_i$(i= 1，2，…，n)以后还需要的资源可以通过系统现有空闲资源加上所有P_j($j$
称为安全序列，因为各进程至少可以按照安全序列中的顺序依次执行完成。
若某时刻系统处于安全状态，则它的安全序列可能不止一个，只要能找到其中的一个，就可判断当前系统是处于安全状态;反之，若一个安全序列都找不到，则称当前系统处于不安全状态。
系统进入不安全状态后虽然未必一定会发生死锁，但已经存在死锁的可能性了。

银行家算法

$\bigstar$ 银行家算法举例

看慕课的视频

死锁的检测与解除

资源分配图

技巧

• 可以先把0填上（对于一个进程既不请求也没有被分配到的资源）

计算题检查方法

• 检查进程入边的总数，和allocation的总数，可以检查进程的allocation有没有数对
• 检查进程出边的总数，和need的总数可以检查，need有没有数对
• allocation + free = 资源总数

死锁定理

死锁检测算法

死锁检测时机

死锁的解除

线程机制

• 重要的线程模型有哪些？

线程的基本概念

线程的引入

作为调度和执行的基本单位，不再是资源分配与拥有的单位，减少管理开销，且降低通信机制及同步机制的复杂度;而对资源分配与拥有的基本单位，又不进行频繁地切换处理，以减少CPU切换开销。

什么是线程

• 在引入线程的操作系统中，线程是隶属于进程的一个实体，是比进程更小的一个运行单位。
• 一个进程可以有一个或多个线程,这些线程共享该进程所拥有的资源,如地址空间(代码、数据及文件)、大部分管理信息(子进程、定时器、信号等)以及IO设备等
• 同时每个线程也有自己的一些必不可少的资源:
  • ①一个线程 ID，用以唯一地标识线程。
  • ②一组寄存器集合:表示线程运行时的处理器状态，包括程序计数器、程序状态字、通用寄存器、栈指针等。
  • ③两个栈:一个用户栈与一个内核栈，分别供线程在用户态及内核态下运行时使用。
  • ④一个私有存储区:存放线程很少的私有数据。如全局变量errno，当某个线程的系统调用失败返回时，其错误码存放在errno中，若进程中所有线程都共享该变量，则必然会造成混乱。
  • ⑤线程控制块TCB:存放线程的管理信息，如线程ID、寄存器的值、线程状态、调度优先级、相关统计信息、信号掩码等。

线程与进程的比较

多线程的应用

线程的实现机制

用户级线程ULT(User LevelThreads)

用户级线程是在用户空间中实现的。在这种方式下，线程的创建、撤销、切换、同步、通信以及线程状态的转换等操作全部由支持线程的一组应用程序代码完成，该组代码称为线程库(又称为运行时系统)，运行在用户空间。

• 优点
  • 线程切换速度快
  • 调度算法可以是应用程序专用的
  • 用户级线程可运行在任何操作系统上，不管该系统是否支持线程机制
• 存在的问题
  • 线程系统调用的阻塞问题。
    • 在典型的操作系统中，许多系统调用都会引起阻塞。当一个用户级线程执行系统调用时，会引起整个进程的阻塞，因为操作系统会把这次系统调用看成是整个进程的行为。
  • 纯用户级线程机制不能利用多处理器的优势。

内核级线程KLT(Kernel LevelThreads)

• 内核级线程是在内核空间实现的。
• 在这种方式下，线程的创建、撤销、调度切换、通信、同步以及线程状态的转换等操作全部由系统内核完成。
• 在内核中有一个进程表记录系统中所有进程的信息，同时有一个线程表，记录系统中每个线程的情况。

• 优点
  • 线程执行系统调用时，仅阻塞调用线程本身，不必阻塞整个进程，进程中其他线程仍然可以获得CPU运行。
  • 在多处理器环境下，一个进程中的多个线程可以同时在多个CPU上并行执行,提高了进程的执行速度。
  • 操作系统内核本身可以采用多线程机制，从而提高系统的运行效率。
• 缺点
  • 开销大

组合方式

多对一模型

该模型把多个用户级线程(通常属于一个进程)映射到一个内核级线程上，如图3-56所示。对用户级线程的管理是由线程库在用户空间进行的，仅当它们需要访问内核时，才将其映射到一个内核级线程上，且每次只允许一个用户级线程进行映射。

• 优点
  • 线程管理开销小
  • 效率高
• 缺点
  • 但如果一个线程因执行系统调用而阻塞，将导致整个进程阻塞
  • 因为任一时刻只有一个线程能访问内核，所以多个线程不能并行运行在多个处理器上。

一对一模型

该模型把一个用户级线程映射到一个内核级线程上，如图3-57所示。这样，当某个线程因执行系统调用而阻塞时，不会导致整个进程阻塞，其他线程可继续运行;此外，在多处理器环境中，也允许多个线程同时在多个处理器上并行运行。但一对一模型要求每创建一个用户级线程就必须为其建立对应的内核级线程，开销较大，因此往往要限制系统中的线程数量。Linux、Windows 家族、OS/2、Solaris 9及更高的版本就采用的这种模型。

多对多模型

该模型把多个用户级线程映射到较少或同样数量的内核级线程上，如图3-58所示。内核级线程的数量可随应用程序的特点及机器配置而变化，比如多处理器系统中可设置更多的内核级线程。多对多模型克服了前面两种模型的缺点，程序员可以根据需要创建多个用户级线程，当一个线程执行系统调用被阻塞时，内核可调度另一个线程来运行。IRIX、HP-Unix、Tru64 Unix等操作系统在实现多对多模型时进行了一些改进:既可把多个用户级线程映射到较少或同样数量的内核级线程上，又允许将一个用户级线程绑定到某个内核级线程上，从而保证该用户级线程能随时访问内核。
许多实现多对多模型的系统在用户级线程与内核级线程之间设置了一级中间结构，通常是轻量级进程(LWP)，如图3-59所示。LWP可共享所属进程的资源，同时还有自己的资源:TCB(记录线程ID、优先级、状态、寄存器值、与之相连的内核级线程的指针等)、栈、私有存储区等，保存在进程地址空间中，因此LWP对用户进程是可见的。每个LWP都与一个内核级线程相连，该内核级线程能被操作系统调度到CPU上运行。对于用户空间的线程库，LWP表现为线程库可以调度用户级线程到其上运行的虚拟处理器。这样，用户级线程可以通过LWP访问内核，不过内核只能看到内核级线程与用户进程中的LWP，不知道用户级线程的存在。当用户级线程不需要访问内核时，其管理工作全部由线程库完成;而当要访问内核时，必须由线程库为其分配一个LWP，借助LWP完成内核访问工作，如执行一个系统调用。如果内核级线程阻塞(如等待一次IO操作的完成)，则与之相连的LWP也阻塞，进而使与该LWP相连的用户级线程也阻塞。为使进程中的多个用户级线程能同时访问内核，可在进程中设置多个LWP(考虑到系统开销,数量也不能太多),组成“LWP池”，让这些线程多路复用LWP，这样当一个LWP阻塞时，其他LWP还能继续工作，从而提高系统的并行性。当然，也允许一些完成紧迫型任务的用户级线程“绑定”到LWP池中一个固定的LWP上，保证这些线程及时访问内核，但会增加系统开销。

Linux线程机制

本章小结

• 考点基本在信号量上(大题)
• 银行家算法

本章习题

第四章 内存管理

• 分页系统
  • 地址运算的本质：页号+页内偏移量
• 可变分区的内存分配算法
  • 首次适应算法
  • 最佳适应算法
  • 最坏适应算法

存储器管理概述

多级存储器体系

计算机的存储系统包括寄存器，Cache，主存，辅助存储器，可移动存储器和网络存储器等层次

计算机的存储系统

存储器管理功能

内存的分配与回收

地址映射

内存的保护和共享

内存扩充

程序的装入和链接

• 连接装入的定义是什么样的(t逻辑地址形成的过程)

根据链接工作进行的时机

静态链接

装入时动态链接

运行时动态链接

根据地址映射进行的时机

绝对装入

• 将地址加载装入到某个指定地址开始的一段内存空间，该地址是在编译时就已经确定的
• 装入和运行过程中都不能改变这个起始地址，因为模块中所有的地址都是基于这个起始地址进行编译的
• 无需进行地址映射，一般适合用于烧写驻留在设备中的固件程序之类的情况

静态重定位装入

• 可以加载到内存中任意合适位置
• 装入内存时，将逻辑地址统一为物理空间中的实际物理地址
• 一旦装入内存就不能再移动位置

动态重定位装入

• 装入时依然使用逻辑地址，当真正执行指令时再将指令本身或指令中操作数的逻辑地址转换为物理地址

连续存储器管理方式

为进程分配一段连续的物理内存空间，也就是将一维线性连续的虚地址空间映射到一维线性连续的实地址空间的方法。

固定分区方式

特点

• 每个分区只能装入一个程序

分配和回收的算法

• 分区分配表
• 对应的分配回收算法

缺点

• 可以容纳的并发进程的最大数量固定(分区数量和分区位置固定)
• 分区内部空间可能存在浪费
• 可容纳的进程最大尺度固定
• 容易产生内部碎片(分区内的碎片)

可变分区方式

特点

• 根据进程需求分配大小合适的空间

分配和回收的算法

• 空闲分区链
• 对应的分配回收算法

分配算法

首次适应算法

要求空闲分区链按各空闲分区起始地址递增的顺序链接。每次分配时，总是从第一个空闲分区开始查找。
优点

• 便于在高端内存留下较大的连续内存空间以满足空间需求大的进程(算法倾向于多分配使用低端内存区域)

缺点

• 容易产生外部碎片

改进：循环首次适应，但不容易满足大进程的需求

最佳适应算法

优点

• 能最大限度地保留大的空闲分区

缺点

• 非常容易产生外部碎片

最坏适应算法

特点
增大余下空间的可利用率

回收算法

上邻接

下邻接

上下邻接

无邻接

分页存储管理方式

• 是一维线性的地址空间

分页存储管理基本原理

页与页框

• 分页存储器管理是将内存物理空间和程序逻辑空间分成大小相等的块(512B~8KB),一般是$2^k B$大小,具体大小是由cpu的硬件机构决定的。
• 逻辑空间中的块称为页面(page),物理空间的块称为物理块，或者页框和帧(frame)。

逻辑地址结构

• 是一维线性的地址空间
• 地址映射公式
  • 逻辑地址A，页面大小L
  • 页号$P=\lfloor A/L \rfloor$
  • 页内地址$d = A \quad mod \quad L$

页表

• 系统为每个进程设置一张页号到物理块号的映射表，称为页表
• 页表的表项PTE(Page Table Entry),由页号和物理块号组成。
• 页表存储在内存中，只存储物理块号，页号不占用存储空间

地址映射与越界保护

• 根据页表查询到物理块号F之后，物理地址就是A’ = F $\times$ L + d
• 地址映射经历两次除法（得到页号,得到页内偏移量），一次乘法(得到物理块起始地址)，一次加法(加上块内偏移量)
• 通常由地址映射机构完成

快表

一个高速缓冲存储器，也称为联想储存器TBL(Translation Lookaside Buffer)

两级和多级页表

• 为进程的页表另外设置一张目录表(用以记录存放进程页表的物理块号)，也叫外部页表，或一级页表，进程自身的页表陈为二级页表
• 由于多级页表占用空间大，所以操作系统仅将顶级页表存储再内存中

分段存储管理基本方式

基本概念

段

• 划分的依据是有逻辑意义的一组相关信息，称为段(segment)
• 每个段都有一个字符串标识符和一个唯一的编号，称为段名和段号

逻辑地址结构

• 分段的逻辑地址空间是二维的非线性地址空间
• 段内地址d的最大位数决定了段的最大长度,而不是长度
• 段号S的位数决定了一个进程的段的最大数量

段表

• 段表记录了各个段在内存中的起始地址(段基址)和段长
• 进程的段表放在内存中
• 段表的内存起始地址和长度保存在进程的PCB中

地址映射与越界保护

段共享与保护

段页式存储管理方式

段页式存储管理首先将进程按逻辑信息分为若干段，然后每个段再按系统规定的页面大小划分为若干页面

因此每个进程的段表只有一张，页表则有多张。

地址映射机构

虚拟存储系统

虚拟存储器的基本概念

虚拟存储器(Virtual Memory)是指具有请求调入功能和置换功能，能够利用外存储器的空余空间从逻辑上对内存容量进行扩充的存储系统

• 虚拟存储器的特征是什么

  改变

  将程序装入的一次性或者整体性改为多次性

  将进程的驻留性改为置换性

  三种实现方式

  请求分页

  本书的重点

  请求分段

  请求段页

请求分页储存管理方式

请求分页需要使用带有缺页中断机构的地址映射机构实现逻辑地址到物理地址

页表

需要增加字段，供页面调入调出时参考

状态位P

表示页面是否在内存中，若不在内存，则产生缺页中断，也成为存在位

访问字段A

记录页面被访问的情况，依据所采用的页面置换算法，可能是被访问次数或者未访问时间，供页面置换时参考

修改位M

标记内存是否被修改，如果没被修改就不用写回外存，减少页面置换时间

外存地址

记录页面在外村上的地址，通常是物理块号，供调入页面时参考

缺页中断机构

地址映射机构

抖动/颠簸(thrashing)

工作集(work set)

某段时间间隔内，进程实际要访问的页面集合

页面置换策略

页面置换算法

最佳置换算法(Optimal,OPT)

先进先出置换算法(First In First Out,FIFO)

• Belady现象(Belady’s Anomaly)
  • 物理块增大时，缺页率不增反减
• 记忆方法：一进一出

最近最久未使用置换算法(Least Recently Used,LRU)

最近最少使用置换算法(Least Frequently Used, LFU)

时钟(CLOCK)置换算法

• 用最小的开销获得接近LRU算法的性能
• CLOCK算法选择将最近未使用的页面置换出去，因此又称NRU算法。

页面缓冲思想

Linux内存管理机制

Linux的物理内存空间管理

Linux虚拟地址空间管理

本章小结

注意

• 一个地址指向一个字节，所以B不用转成b(例题4-5)，感觉是因为c语言的最小基本类型是一个字节
• 逻辑地址和物理地址的位数不一样会产生什么影响？

题型

• 地址映射的计算题
• 得到内存时间的计算题
• 多级页表的设计
• 页面置换算法

本章习题

第五章 设备管理

• 目标
  • 提供与系统其他部分的简单、统一的接口，方便设备使用
  • 优化I/O操作，提高设备与CPU之间以及各种设备之间的并行性，从而提交CPU和设备的利用率

设备管理的功能

• 设备分配
• 缓冲管理
• 设备处理

输入输出系统

设备的分类

• 传输速率
  • 高速设备（每秒传输几百万个字节以上）
    • 磁盘
    • 光盘
    • 优盘
  • 中速设备（每秒传输几千字节到几十万个字节）
    • 打印机
    • 扫描仪
  • 低速设备（每秒传输几个字节到几百个字节）
    • 鼠标
    • 键盘
• 信息交换单位
  • 块设备
    • 特点：传输速率高、可寻址及一般采用DMA方式
    • 磁盘、优盘
  • 字符设备
    • 特点：传输速率低，不可寻址，一般采用中断驱动方式
    • 交互式终端
    • 打印机
• 设备共享属性分类
  • 独占设备
  • 共享设备
  • 虚拟设备
• 工作特性
  • 存储设备
    • 优盘，磁盘，光盘，存储卡
  • I/O设备
    • 键盘，显示器，打印机，扫描仪，绘图仪

设备控制器

设备控制器的功能

• 接收和识别命令
• 数据交换
• 地址识别
• 数据缓冲
• 识别和报告设备的状态
• 差错控制

设备控制器的组成

• 设备控制器与处理器的接口
  • 数据缓冲的数据寄存器
  • 设备状态的状态寄存器
  • 保存cpu发来的命令以及各种参数的命令寄存器
• 设备控制器与设备的接口
• I/O逻辑
  • 用于实现对设备的控制

I/O通道

• 通道类型
  • 字节多路通道（低速设备）
    • 以时分复用的方式执行几个通道程序
  • 数组选择通道（高速设备）
    • 一次只执行一个通道程序
  • 数组多路通道
    • 时分复用的方式执行多个通道程序
• 通道程序
  • 操作码（读，写，控制）
  • 内存地址
  • 计数
    • 指明本条通道指令所要操作数据的字节数
  • 通道程序结束位P
    • P=1表示本指令时通道程序的最后一条指令，表明该通道程序的结束
  • 记录结束标志R。
    • R=0表示该通道指令与下一条指令所处理的数据同属一个记录
    • R=1表示该通道指令时处理某记录的最后一条指令

I/O系统结构

• 总线型I/O系统结构
• 通道型I/O系统结构

输入输出控制方式

尽量减少CPU对I/O控制的干预

• 程序直接控制方式
• 中断驱动控制方式
  • 每传一个字符都要中断
• 直接存储器存取方式（DMA）
  • 在I/O设备和主存之间建立一条直接数据通路
• 通道控制方式
  • CPU
    • 根据本次I/O请求的要求组织通道程序并存放在内存中
    • 发出启动I/O指令，启动相应的通道工作
    • 启动成功后，CPU立即返回执行其他任务
  • 通道程序
    • 从内存中取出通道程序
    • 依次执行其中的通道指令
    • 控制设备执行输入输出操作
    • 当通道程序执行完成，即数据传送结束时，通道向CPU发中断请求，
  • CPU
    • 接收到中断信号后响应中断
    • 执行相应的中断处理程序

缓冲管理

• 目的
  • 缓和CPU与I/O设备间速度不匹配的矛盾
  • 减少对CPU的中断频率，放宽CPU对中断响应时间的限制
  • 提高CPU与I/O设备之间的并行性

缓冲的实现机制

c（处理时间）
M（传送时间）
T（输入时间）

• 单缓冲
  • 处理每一块数据的处理时间表示为Max（C,T）+ M
• 双缓冲
  • 处理每一块数据的处理时间表示为Max（（T+M）,C）$\approx$ Max（T,C）
• 循环缓冲
• 缓冲池

I/O软件

I/O软件的层次模型

• 用户进程
• 独立于设备的软件
• 设备驱动程序
• 中断处理程序
• 硬件

独立于设备的软件

• 设备独立性（设备无关性）
  • 用户的应用程序独立于具体使用的物理设备

独立与设备的软件功能

独立于设备的软件的基本任务是实现所有设备都需要的共性功能，并且向用户级软件提供一组统一的使用接口

• 对设备命名
• 提供设备保护，防止无权限的用户春去设备
• 提供与设备无关的逻辑块
• 实现缓冲技术
• 出错处理

设备驱动程序的基本概念

设备驱动程序的功能

接收由独立于设备的软件发来的命令和参数

检查用户I/O请求的合法性

发出I/O命令

及时响应由设备控制器发来的中断请求，调用相关的中断处理程序进行处理

对于具有通道结构的系统，还需要根据用户的I/O请求构造通道程序

设备驱动程序的特点

驱动程序是实现独立于设备的软件和设备控制器之间通信与转换的程序

驱动程序与设备控制器以及I/O设备的硬件特性紧密相关，常用的I/O驱动方式是终端驱动和DMA方式

由于驱动程序与硬件紧密相关，因而其中一部分代码必须用汇编语言编写

驱动程序应允许可重入

设备处理方式

TODO

TODO

不设置专门的进程，而只为各类设备设置相应的设备驱动程序，供用户或系统进程调用。

这种方式目前用的比较多

设备驱动程序的处理过程

将抽象要求转换为具体要求

对服务请求进行校验

检查设备的状态

传送必要的参数

启动I/O设备

设备分配

设备分配的数据结构

数据结构

设备控制表表（DCT）

记录设备的特性及与设备控制器连接的情况

• Device control table

控制器控制表（CODT）

每个设备控制器配置一张控制器控制表，记录控制器的使用状态及与通道的连接状况等

• Controller Control Table

通道控制表（CHCT）

每个通道配置一张设备控制表，记录通道的使用状态

• Channel Control Table

系统设备表（设备类表）(SDT)

整个系统一张

• System Device Table

设备分配过程

一共三个步骤

设备分配过程

分配设备

分配控制器

分配通道

SPOOLing系统

• 组成
  • 输入井和输出井（在磁盘上）
  • 预输入程序和缓输出程序
  • 井管理程序

Linux字符设备驱动程序

感觉应该不是考试重点，也没做对应的实验

Linux字符设备驱动程序基础

字符驱动程序设计

字符驱动程序举例

Linux中断处理机制

Linux中断处理机制概述

中断服务例程的注册和注销

上半部的处理过程

下半部的实现机制

本章小结

• 通道是一种特殊的处理器，所以属于硬件技术。SPOOLing、缓冲池、内存覆盖都是在内存的基础上通过软件实现的。
• 汁算机系统为每台设备确定一个编号以使区.分和识别设备，这个确定的编号称为设备的绝对号。
• 通道控制设备控制器、设备控制器控制设备工作。对于同一组输入输出命令，三者不能并行工作。
• 将系统调用参数翻译成设备操作命令的工作由设备无关的操作系统软件完成
• 如果算的是下面，要加上上面，反之亦然(单缓冲双缓冲的计算题目)

本章习题

第六章 文件系统

• 从用户的观点看主要关心
  • 文件由什么组成
  • 如何命名
  • 如何保护文件
  • 能进行哪些操作
• 从操作系统的观点看主要关心
  • 文件目录是怎样实现的
  • 怎样管理存储空间
  • 如何实现文件的按名存取及文件的共享与保护

文件和文件系统

文件

文件的概念

从概念上来讲，文件是具有符号名的、在逻辑上有完整意义的一组相关信息项的有序集合。

• Linux系统的文件名区分大小写字符。而MS-DOS和windows系列的操作系统不区分大小写

文件的类型

按文件用途可分为系统文件、库文件和用户文件

系统文件是指由操作系统以及其他系统程序(如编译程序等)组成的文件。这类文件只允许用户通过系统调用来执行，不允许用户去读取，更不允许修改。库文件是指由系统提供给用户调用的各种标准过程、函数和应用程序等，用户对库文件只能读取或执行，不能修改。用户文件是指由用户的源代码、目标文件、可执行文件和数据等组成的文件。它们的使用和修改权属于文件主及授权用户。

按文件保护级别可分为只读文件、读写文件、只执行文件和不保护文件

只读文件仅允许文件主和授权用户对其进行读，但不允许写;读写文件允许文件主和授权用户对其进行读写操作;只执行文件仅允许文件主和授权用户对其调用执行，但不能进行读写操作;不保护文件是指不做任何操作限制的文件。

按文件的存取方法可分为顺序存取文件和随机存取文件

顺序存取文件是指进程可从头顺序读取全部字节或者记录的文件，读取过程不能跳过某些内容，也不能不按顺序存取。随机存取文件是可以不按顺序地存取指定字节或者记录，或者按照关键字而不是位置来存取记录的文件。

实际操作系统中的文件分类

很多操作系统支持多种文件类型，如Windows、Unix和Linux中都有普通文件和目录文件。普通文件包含ASCII文件和二进制文件，一般用户建立的源程序文件、数据文件和操作系统自身代码文件、实用程序等都是普通文件。目录文件是管理文件系统组织结构的系统文件，对于目录文件可以像对普通文件一样对其内容信息进行相关操作。另外，Unix和 Linux系统还有特殊文件。特殊文件又包括FIFO文件、字符设备文件、块设备文件和符号链接文件，其中 FIFO文件又称为管道文件，它是Unix(Linux)提供的一种进程间通信机制;字符设备文件与输入/输出有关，主要用于处理各种串行I/O设备，如终端、打印机和网络设备等;块设备文件主要用于处理磁盘;符号链接文件又称为软链接，它通过包含另一个文件的路径名(绝对路径或者相对路径)实现文件共享。

其他分类

当然，文件还有很多分类标准，如按存放时限可分为临时文件、永久文件和档案文件;按文件的信息流向可分为输入文件、输出文件和输入输出文件;按数据形式分为源文件、目标文件和可执行文件。

文件系统

所谓文件系统，是指被管理的文件、对文件进行管理的一组软件集合以及实现管理功能所需要的数据结构(如目录表、文件控制块、位示图、i节点等)的总体。

从操作系统的角度看

文件存储空间的管理

主要任务是为每个文件分配合适的外存空间，提高外存的利用率和文件的存取速度

文件目录管理

文件系统最基本的功能就是实现文件的“按名存取“

文件地址映射

文件读写管理

文件共享和保护

文件操作

主要工作

创建文件

该操作的目的是声明文件的存在，在外存给新文件分配存储空间，并在指定目录中给它建立一个目录项，目录项中记录新文件的文件名和外存地址等属性。

删除文件

该操作首先释放文件所占用的外存空间，然后在父目录中清空该文件的目录项。

打开文件

用户在使用一个文件之前必须先打开它。该操作将文件的属性信息加载到内存打开文件表的一个表项中，并将这个表项的编号(称为文件描述符)返回给用户。以后当用户需要对文件进行读/写等操作时，就根据该文件描述符直接在打开文件表中查找文件属性信息，从而显著地提高文件操作速度。

关闭文件

当文件访问结束后，文件的属性信息就不再需要了，此时应该关闭文件以释放打开文件表中相应空间。这个过程中需要检查该文件的文件打开表项是否被修改过，若被修改过，则应把修改过的文件打开表项内容重新写回到外存，并在“打开文件表”中清空该文件的信息。

读文件

通过文件描述符查找文件打开表，从相应表项得到文件的外存地址及当前读指针，再根据用户需要读取的字节数，将数据读入指定的缓冲区中。对于顺序存取方式的文件，每次按逻辑顺序读一个或几个逻辑记录传送到用户指定的内存地址;对于随机存取方式的文件，根据用户给出的记录号(或键值)查找索引表，得到该记录的外存地址后，将该记录传送到用户指定的内存地址。

写文件

与读文件步骤类似，只是将数据写入外存中文件写指针指示的位置。对顺序存取方式的文件，找出文件信息的存放位置并写入指定信息，同时保留一个“写指针”指出下一次写文件时的存放位置;对随机存取方式的文件，首先分配一空闲盘块，把记录存入该盘块中，然后在索引表中找一空表项，并填入相关信息。

设置文件读写指针

对于可随机访问的数据文件，进程可指定数据的开始读写位置，之后所有读写操作都从这个位置开始。通常，文件系统为每一个打开的文件提供两个指针:读指针和写指针，前者指示当前的读取位置，后者指示当前的写入位置。

获取文件属性

进程经常需要得到文件的属性，例如文件类型、文件字节数、用户信息、块数、硬链接数目、访问权限和最后访问及修改时间等等。

设置文件属性

创建文件之后，有些属性是可以修改的，例如文件主或者用户组的权限等。

重命名文件

该系统调用实现更改现有文件的文件名。

锁定文件

该系统调用锁定一个文件的全部或者部分内容，以防止多个进程同时访问。

文件的结构和存取

面向用户的文件组织结构和构造方式

文件的逻辑结构

有结构的文件

顺序文件

索引文件

索引表:每条逻辑记录占一个表项，每个表项内容存放记录的关键字，长度和起始位置

索引顺序文件

直接文件和散列文件

无结构文件（流式文件）

文件的物理结构

存储介质上的组织方式

连续文件

• 优点
  • 顺序存取速度快
  • 方便地实现文件的随机存取
• 缺点
  • 对存储文件要求有连续的存储空间
  • 容易产生磁盘碎片，降低磁盘存储空间的利用率
  • 不方便文件的动态增长（不利于文件的扩展）
  • 如果使用拼接技术来消除碎片，又要消耗大量的系统时间

链接文件

• 隐式链接
  • 缺点
    • 只能对文件进行顺序存取
    • 效率低（如果希望存取一个文件的某个磁盘块，及必须从该文件的第一个盘块开始读取，才能找到指定磁盘块的位置）
    • 可靠性差（如果文件中某个磁盘块出现故障，将导致该文件的后续盘块指针丢失）
• 显式链接（FAT）
  • 目录项填入文件名，起始盘块号，文件长度
  • 优点
    • 提高检索速度（查找FAT是在内存而非磁盘中进行的）
    • 实现随机存取（一个文件的全部盘块号都集中保存在fat中）
  • 缺点
    • 随即存取的效率会降低（FAT较大时）
    • FAT占据较大的内存空间（FAT较大时）
• 总优点
  • 消除磁盘的碎片，提高了磁盘存储空间的利用率
  • 使文件很容易实现动态增长

索引文件

单级索引

索引文件的优点是支持高效的随机访问，因为从索引块中可方便地得到其所有的盘块号。磁盘存储空间采用离散分配方式，既不会产生外部碎片，也支持文件的动态增长。但缺点是由于每个文件都需要额外分配索引块，因而增加了系统存储开销，尤其是对于小文件，本身只需要几个或者几十个磁盘块，但是仍需分配一个可以存放数百个块号的索引块。

多级索引

多级索引的最大优点是提供对大文件的支持，主要缺点是访问一个磁盘块时需要启动磁盘的次数随着索引级数增加而增多，且需要更多的索引存储空间。在实际应用中，大文件毕竟是少数，因此如果只采用多级索引也并不能取得用户满意的效果。

混合索引（Uinx system V）

文件存取

文件目录管理

• 功能
  • 实现”按名存取“
  • 提高目录的索引速度
  • 允许文件重名
  • 允许文件共享

文件目录的概念

文件控制块

基本信息

• 文件名
• 用户名
• 文件类型
• 文件的物理地址
• 文件长度
• 文件的逻辑结构和物理结构

存取控制信息

使用信息

索引节点的引入

文件目录结构

文件系统通常把一组文件的目录项组织成一个独立的文件，这个全部由文件目录项组成的文件称为目录文件

单级目录结构

• 优点
  • 单级目录结构的最大优点是实现和管理简单，且能实现“按名存取”
  • 缺点
    • 第一，查找速度慢。当系统中文件较多时，目录表会很大，查找一个指定的目录项需要花费较多的时间。
    • 第二，不允许文件重名。即不同的文件不能使用相同文件名，这对多用户系统来说，是很难避免的，即使是单用户环境，当文件数量很大时也很难管理。
    • 第三，不便于实现文件共享。因为每个用户都有自己的命名习惯，用户很希望能使用不同的文件名来访问同一个文件，但单级目录结构却要求所有用户使用同一个文件名来访问同一个文件。

两级目录结构

• 主文件目录（Master File Directory，MFD）
• 用户文件目录（User File Directory。UFD）

• 优点
  • 第一，提高了目录检索速度;
  • 第二，允许文件重名，即不同用户可以对不同文件使用相同的文件名，但同一用户的文件不允许重名;
  • 第三，不同用户可以使用不同的文件名来访问系统中的同一个共享文件
• 缺点
  • 两级目录结构的缺点是缺乏灵活性，无法反映真实世界复杂的文件组织形式
  • 不能很好地满足文件多的用户的需要。

多级目录结构

目录检索技术

线性检索法

Hash方法

文件存储空间管理

基本方法

空闲表法

空闲块链表法

位示图

• n代表每行的列数，b是盘块号
• b = n(i-1) + j
• 行号 i=(b-1) DIV n + 1
• 列号 j=(b-1) MOD n + 1

成组链接法

文件共享和文件保护

文件共享

• 基于索引节点的共享方式
• 利用符号链接实现文件共享

文件保护

文件备份

批量备份

同步备份

文件访问保护

口令保护

加密保护

设置文件访问写权限

设置文件访问写权限的方法

访问控制矩阵

矩阵形式，行为用户，列为对象

访问控制表

按对象划分，一个对象一张表

用户权限表

按用户划分，一个用户一张表

磁盘调度

如何优化磁盘调度算法以改善磁盘访问速度是操作系统的重要任务之一

磁盘管理概述

数据的组织和格式

• CHS(Cyliner/Head/Sector)柱面号，磁头号，扇区号
• LBA（logical block addressing）
  • L（一个磁盘的柱面数），M(磁头数)，N（扇区数），第i柱面，j磁头，k扇区对应的LBA扇区号为
    • LBA = （i*M*N）+ j*N + k-1
  • 已知LBA，对应的柱面号i，磁头号j，扇区号k为
    • i = int(LBA/(M*N))
    • J = [LBA mod (M*N)]/N
    • k = [LBA mod (M*N)] mod N + 1
  • 磁盘的容量
    • 磁头数 $\times$ 柱面数 $\times$ 扇区数 $\times$ 每扇区字节数

磁盘访问时间

寻道时间$T_s$（是机械运动，影响最大）

• m磁头每移动一条磁道所需要的时间(与磁盘驱动器的速度相关)，n寻道距离(移动的磁道数，是影响$T_s$的主要参数)，s（启动磁臂的时间）
• $T_s = m \centerdot n + s$

旋转延迟时间$T_r$

• r磁盘旋转的速度，（旋转延迟时间是欲访问扇区旋转到磁头下面所需要的时间，与磁盘旋转速度有直接关系，可粗略的仍未是磁盘旋转半周的时间）
• $T_r = \dfrac{1}{r} \div 2 = \dfrac{1}{2r}$

传输时间$T_t$

• b要读写的字节数，r磁盘的旋转速度，N一个磁道上的字节数，（把数据从磁盘读出或向磁盘写入所需要的时间，他与磁盘的转速以及要读/写的字节数有关）
• $T_t = \dfrac{b}{rN}$

总的磁盘访问时间$T_a$

• 访问时间$T_a$ = 寻道时间$T_s$ + 旋转延迟时间$T_r$ + 传输时间$T_t$

磁盘调度算法

移臂调度

先来先服务（First Come First Served，FCFS）算法

• 优点
  • 公平且实现简单
  • 不会产生饥饿现象
• 缺点
  • 寻道时间比较长（未对寻道进行优化）

最短寻道时间优先(ShortestSeekTimeFirst,SSTF)算法

• 概念
  • 总是选择与当前磁道（磁头所在的磁道）距离最近的磁道访问请求
• 缺点
  • 不公平
  • 不能保证平均寻道距离最短
  • 产生饥饿（可能会使某些远离当前磁道的I/O请求长度得不到服务）
  • 影响磁盘的机械寿命（完全不考虑磁头当前的移动方向，可能会导致磁头频繁地改变移动方向而影响磁盘的机械寿命）

扫描（SCAN）算法(电梯算法)

• 概念
  • 确定下一条要访问的磁道时，既照顾磁头当前的移动方向，又考虑当前磁道的距离，总是从磁头当前移动方向上，选择与当前磁道距离最近的磁道访问请求，如果磁头移动方向无访问请求时，就改变磁头的移动方向，从方向再选择

循环扫描（Circular SCAN，CSCAN）算法

• 规定磁头的单向移动，当磁头完成最里层磁道访问请求时，立即返回最外面的磁道，循环扫描

N-Step-SCAN算法

• 将当前的磁盘请求队列分为若干长度为N的子队列，磁盘调度将按FSFS算法依次处理这些子队列，而在处理每个子队列时又采用SCAN算法

FSCAN（FairSCAN）算法

• 分成两个队列，一个就绪，一个运行

旋转调度

当一条磁道上，有多个扇区访问请求时，确定扇区访问顺序，以减少旋转延迟时间

Linux文件系统

Linux文件系统概述

虚拟文件系统VFS

文件系统的注册、安装和卸载

Linux文件系统对文件的操作

Ext 文件系统

本章小结

• linux的用户权限
  • rwx
  • 所有者-用户组-其他人
• 最外层的磁道号为0号，由外到内增加

• 磁盘的读取速度和转速的区别？

• 文件目录项和文件控制块的区别？
• 目录文件和文件目录项的区别？
• 硬链接和复制文件的区别是什么？
• linux是几级索引？

本章习题

• 一个文件对应一个索引节点，索引节点的总数只能说明有多少个文件。

后记

• 复习老师给的资料很重要
• 合理安排复习时间与内容
  • 没时间重看笔记，整理思路