操作系统知识整理 本文简介：
第一章操作系统概述3一、操作系统的定义3二、区别程序并发与程序并行3三、操作系统的硬件环境3第二章进程、线程与作业5一、吞吐量5二、进程的概念5三、进程状态及状态转换5四、进程控制块6五、进程的组成6六、进程的队列6七、线程的概念7八、线程控制块7九、线程的实现8十、作业8十一、作业、进程、线程三者
操作系统知识整理 本文内容：
第一章
操作系统概述
3
一、
操作系统的定义
3
二、
区别程序并发与程序并行
3
三、
操作系统的硬件环境
3
第二章
进程、线程与作业
5
一、
吞吐量
5
二、
进程的概念
5
三、
进程状态及状态转换
5
四、
进程控制块
6
五、
进程的组成
6
六、
进程的队列
6
七、
线程的概念
7
八、
线程控制块
7
九、
线程的实现
8
十、
作业
8
十一、
作业、进程、线程三者之间的关系
9
第三章
中断与处理器调度
10
一、
概述
10
二、
中断概念
10
三、
中断装置
10
四、
中断处理程序
11
五、
处理器调度
12
六、
处理器调度算法
12
七、
常用的处理器调度算法（八个）
13
八、
调度级别与多级调度
17
第四章
互斥、同步与通信
19
一、
进程互斥
19
二、
共享变量与临界区
19
三、
临界区与进程互斥
19
四、
进程同步
19
五、
进程同步机制
20
六、
信号灯与PV操作的相关定义
20
七、
信号灯与PV操作的应用
22
八、
用信号灯变量解决综合问题——生产者—消费者问题
23
九、
用信号灯变量解决综合问题——读者—写者问题
26
十、
用信号灯变量解决综合问题——哲学家就餐问题
28
十一、
用信号灯变量解决综合问题——三台打印机的管理
30
十二、
用信号灯变量解决综合问题——吸烟者问题
30
十三、
进程高级通信的分类、概念及模式
32
十四、
进程通信的消息传递模式的两种实现方式
32
第五章
死锁与饥饿
36
一、
死锁的概念
36
二、
关于死锁几个有用的结论（4个）
36
三、
死锁的类型
36
四、
死锁的条件（4个）
36
五、
死锁的处理
37
六、
银行家算法（掌握思想，不需要写）
37
七、
饥饿与活锁
40
八、
死锁与饥饿的例子——独木桥问题
41
九、
死锁与饥饿的例子——过河问题
44
十、
系统举例
45
第六章
存储管理
46
一、
内存资源管理
46
二、
存储管理方式（三张图非常重要）
48
三、
虚拟存储系统（注意颠簸和页故障率反馈模型）
48
第七章
文件系统
52
一、
文件的概念
52
二、
文件的组织
52
三、
文件控制块
55
四、
文件系统的实现
56
第八章
设备与输入输出管理
58
一、
设备的分类
58
二、
数据传输方式——通道方式
58
三、
设备驱动
59
四、
虚拟设备
59
第一章
操作系统概述
一、
操作系统的定义
操作系统是位于硬件层之上，所有其他系统软件层之下的一个系统软件，使得管理系统中的各种软件和硬件资源得以充分利用，方便用户使用计算机系统。
二、
区别程序并发与程序并行
程序并行要求微观上的同时，即在绝对的同一时刻有多个程序同时向前推进；
而程序并发并不要求微观上的同时，只需从宏观上看多个程序都在向前推进。
并发：宏观上同时运行，微观上交替运行。
三、
操作系统的硬件环境
a)
定时装置
1.
绝对时钟
时间表示形式为年、月、日、时、分、秒，开机时由电源供电计时，关机时由机内电池供电计时。
操作系统使用绝对时钟记录作业进入系统和处理的时间、文件的修改和存取时间、资源占用时间、日志记录时间等。
2.
间隔时钟
又称闹钟，每间隔固定的时间发生一次时钟中断，此时系统获得控制权，以便运行系统管理和实现程序并发。
中断是系统并发的必要条件，间隔时钟是现代操作系统的基础。
利用间隔时钟还可以实现逻辑时钟。
b)
系统栈
1.
位置
内存中操作系统空间的一个固定区域。
2.
用途
1.
中断响应时保存中断现场
2.
保存操作系统子程序间相互调用的参数值、返回值、返回点以及子程序的局部变量。
c)
特权指令与非特权指令
1.
特权指令
只有在管态下才能执行
指令的执行不仅影响运行程序本身，也会影响其他程序甚至整个系统。
eg:
开关中断、修改地址映射寄存器、置程序状态字PSW、停机。
2.
非特权指令
在管态和目态下均可执行的指令称为非特权指令，这些指令的执行只与运行程序本身有关，不影响其他程序和操作系统。
eg:
数据传送指令、算术运算指令。
d)
处理器状态及状态转换
1.
处理器状态
硬件通常分为管态和目态两种状态，由程序状态字PSW中的一位进行标识。
1.
管态
管态又称为系统态、核心态，是操作系统运行时所处的状态。计算机处于管态时可以执行硬件所提供的全部指令。包括特权指令和非特权指令。
由于利用特权指令可以修改程序状态字，而机器状态是程序状态字的一部分，因而在管态下可以改变机器状态进入目态。
2.
目态
目态又称为用户态，是一般用户程序运行时所处的状态。处理器在处于目态时只能执行硬件机器指令的一个子集，即非特权指令。
一旦用户在目态执行特权指令，硬件将产生中断，进入操作系统，特权指令的执行将被制止。
由于“置程序状态字”是特权指令，所以目态程序不能将其运行状态转换为管态。
2.
状态转换
1.
目态到管态的转换
处理器状态由目态转换为管态的唯一途径是中断。
2.
管态到目态的转换
可以通过修改程序状态字（置PSW）来实现。
由于操作系统运行于管态、用户程序运行于目态，因而这种状态转换伴随着由操作系统到用户程序的转换。
e)
中断装置
1.
定义
发现并响应中断的硬件机构称为中断装置。
2.
功能
1.
发现中断
中断发生时能够识别。
有多个中断事件同时发生时，按优先级别响应最高级者。
2.
响应中断
将目前运行进程的中断向量PSW和PC压入系统栈，然后根据中断原因到指定的内存单元将新的中断向量取出并送到寄存器中，从而控制转到相应的中断处理程序。
第二章
进程、线程与作业
一、
吞吐量
衡量系统效率的尺度是吞吐量。
系统的吞吐量定义为单位时间内系统所处理的作业（程序）的道数（数量），即：
吞吐量=作业道数全部处理时间
吞吐量与系统的处理器等资源的利用率有密切的关系，提高系统的吞吐量应当从提高系统的资源利用率入手。
二、
进程的概念
进程是具有一定独立功能的程序关于一个数据集合的一次运行活动。
三、
进程状态及状态转换
a)
进程的生存期
进程从生成到执行结束的一段时间是进程的生存期。
b)
进程的状态
进程在其生存期内可能处于以下3中基本状态之一。
1.
运行态（run）
进程占有处理器资源、正在运行。
（即占用CPU，单处理器系统中任一时刻只能有一个进程处于此种状态。）
2.
就绪态（ready）
进程本身具备运行条件，但是由于处理器的数量少于可运行进程的数量，暂未投入运行，即相当于等待处理器资源。
（即未得到CPU）
3.
等待态（wait）
又称为挂起态、封锁态、睡眠态，进程本身不具备运行条件，即使分配给其他处理器也不能运行。
进程正在等待某一事件的发生，如等待某一资源被释放，等待与该进程相关的数据传输的完成信号等。
c)
状态转换
当一个就绪进程获得处理器时，其状态由就绪态变为运行态。
当一个运行进程被剥夺处理器资源时，如用完系统分给它的时间片、或者出现高优先级别的其他进程，其状态由运行态变为就绪态。
当一个运行进程因某事件受阻时，如所申请资源被占用、启动数据传输未完成，其状态由运行态变为等待态。
当所等待的事件发生时，如得到被申请的资源、数据传输完成，其状态由等待态变为就绪态。图
进程间的基本状态转换关系
四、
进程控制块
a)
定义
进程控制块（Process
Control
Block，PCB）是标志进程存在的数据结构，其中包含系统对进程进行管理所需要的全部信息。
b)
作用
多道程序系统中运行的程序需要有一个断点现场保存区域，这个区域就设在进程控制块中。
进程控制块是进程存在的标志，它由一组信息构成。
进程标识：
通常为一个整数，称为进程号，一个进程号与唯一的用户号相对应
用户标识：
通常为一个整数，称为用户号，一个用户号与多个进程号相对应
进程状态：
在就绪、运行、等待之间动态变化
调度参数：
确定下一个运行的进程
现场信息：
用于保存进程暂停的断点信息，包括通用寄存器、PSW、PC
家族联系：
记载本进程的父进程
程序地址：
记载进程所对应的程序的存储位置和所占存储空间大小
当前打开文件：
记载进程正在使用的文件
消息队列指针：
指向本进程从其他进程接收到的消息所构成消息队列的链头
资源使用情况：
记载该进程生存期间所使用的系统资源和使用时间
进程队列指针：
用于构建进程控制块队列，它是系统管理进程所需要的
五、
进程的组成
进程由两个部分组成，即进程控制块和程序，其中程序包括代码和数据等。
a)
进程控制块
进程控制块是进程的“灵魂”。
进程控制块放在系统空间中，只有操作系统才能够对其进行存取。
b)
程序
程序是进程的“躯体”，其中包括代码和数据两个部分。
c)
系统开销（system
overhead）
系统开销一般是指运行操作系统程序、对系统进程管理所花费的时间和空间。
六、
进程的队列
由于进程控制块是进程的代表，因而进程队列实际上是由进程控制块构成的队列。
因为该队列通常是以链的形式实现的，所以也称为PCB链。
a)
就绪队列
一般整个系统中有一个就绪队列。
b)
等待队列
每个等待事件有一个等待队列，所以一个系统中根据等待事件的不同有多个等待队列。如等待输入设备的队列、等待输出设备的队列等。
c)
运行队列
在单处理器系统中只有一个运行队列，在多处理器系统中每个CPU各有一个运行队列。
每个队列中只有一个进程。图
进程队列模型
七、
线程的概念
a)
定义
线程(thread)又称轻进程，是进程内的一个相对独立的执行流。
一个进程可以包含多个线程，这些线程执行同一程序中的相同代码段或不同代码段，共享数据区和堆。
一般认为，进程是资源的分配单位，线程是CPU的调度单位。
b)
线程相比进程的优点
1.
上下文切换速度快
由同一进程中的一个线程切换到另一个线程只需改变寄存器和栈，包括程序和数据在内的地址空间不变。
2.
系统开销小
创建线程比创建进程所需完成的工作少。
3.
通信容易
由于同一进程中的多个线程共享地址空间，所以一个线程写到数据空间的信息可以直接被该进程中的其他线程读取，便于通信。
八、
线程控制块
a)
定义
线程控制块(thread
control
block,
TCB)是标志线程存在的数据结构，其中包含系统对线程进行管理所需要的全部信息
b)
组成
线程标识
线程状态
调度参数
现场（通用寄存器、指令计数器、用户栈指针）
链接指针线程控制块可能属于操作系统空间，也可能属于用户进程空间（由运行系统管理和使用），这取决于线程的实现方式。
九、
线程的实现
线程有两种实现方式：在目态实现的用户级别线程，在管态实现的核心级别线程。
a)
用户级别线程
1.
用户级别线程与线程相关的控制结构——线程控制块保存在目态空间中并由运行系统进行维护。
2.
由于线程对操作系统不可见，系统调度仍以进程为单位，核心栈的个数与进程个数相对应。
3.
优点
1.
线程不依赖于操作系统，可以采用与问题相关的调度策略，灵活性好。
2.
同一进程中的线程切换不需要进入操作系统，因而实现效率较高。
4.
缺点
3.
同一进程中的线程不能真正并行，即使在多处理器环境中；
4.
由于线程对操作系统不可见，调度在进程级别，某进程中的一个线程通过系统调用进入操作系统受阻，该进程的其他线程也不能运行。
b)
核心级别线程
1.
核心级别线程的线程控制块保存于操作系统空间，线程状态转换由操作系统完成，线程是CPU调度的基本单位。
2.
因为系统调度以线程为单位，操作系统还需要为每个线程保持一个核心栈。
3.
对于核心级别线程，进程状态不具有实际意义，可以将其省略
4.
优点：并发性好，在多处理器环境中同意进程的多个线程可以真正并行执行。
5.
缺点：线程的控制和状态转换需要进入操作系统完成，系统开销比较大。
十、
作业
a)
定义
用户要求计算机系统为其完成的计算任务的集合称为作业(job)
（在这里，计算任务是广义上的计算任务）
一般来说，作业是比进程还大的一个概念。
b)
作业步(job
step)
一个作业通常包含多个计算步骤，作业中一个相对独立的处理步骤称为一个作业步。
作业步之间具有顺序或并发关系。
c)
作业与进程的关系
一个作业步通常可以由一个进程来完成，这样一个作业在内存处理时通常与多个进程相对应，即作业与进程之间具有一对多的关系。
d)
作业控制块
作业控制块(job
control
block,
JCB)是标志作业存在的数据结构，其中包含系统对作业进行管理所需要的全部信息。
e)
关于批处理作业的几个基本概念
1.
作业控制语言JCL：描述批处理作业控制意图的语言
类比C语言
2.
作业说明书：JCL的语句序列。（作业说明书一般以特殊符号$起始）
类比C语言写的程序3.
作业控制程序：解释并处理作业说明书的程序
类比编译器程序
4.
作业控制进程：执行作业控制程序的进程
f)
批处理作业——作业控制程序
作业由假脱机输入程序(SPOOLing
输入程序)控制进入输入井，经操作系统的作业调度程序选择进入内存，并为其建立作业控制进程。
作业控制进程解释作业说明书的语句，根据作业步的要求为其建立进程。图
作业控制程序的工作原理
（批处理作业）
g)
交互式作业——系统passwd文件
对分时系统来说，通常将分时用户的一次登录称为一个作业。
一次登录可以向系统提出多个请求，每个请求都可能对应一个进程，这样分时作业与进程之间也是一对多的关系。
分时系统中，通过设置一个口令文件，来实现对分时用户的管理。UNIX系统将该文件保存在/etc/passwd中，Passwd文件中包含所有注册用户的信息。图
系统passwd文件
（交互式作业）
十一、
作业、进程、线程三者之间的关系
a)
作业对进程是一对多的关系，进程对线程是一对多的关系。
b)
作业与进程
作业进入内存后变为进程，一个作业可与多个进程相对应；
进程实现作业所要完成的功能。
c)
进程与线程
在不支持多线程的系统中，进程可以视为单线程进程；
支持多线程的系统中，一个进程可以包含多个线程，至少包含一个线程。
第三章
中断与处理器调度
一、
概述
中断是实现多道程序设计的必要条件。
如果没有中断，操作系统就无法获得系统的控制权，也就不能将处理器资源分配给不同的进程。
二、
中断概念
在程序运行过程中出现某种紧急事件，必须中止当前正在运行的程序，转去处理此事件，然后再恢复原来运行的程序，这个过程称为中断。
中断的实现需要硬件和软件的合作，硬件部分称为中断装置，软件部分称为中断处理程序。中断装置和中断处理程序称为中断系统。
三、
中断装置
a)
定义
中断装置是用于发现并响应中断的硬件机构。
b)
中断装置发现并响应中断的步骤
1.
识别中断源
引起中断的事件称为中断源。
当有多个中断源存在时，中断装置选择优先级别最高的中断源。
2.
保存中断现场
将正在运行的进程的程序状态字PSW及指令计数器PC中的内容压入系统栈（内存中）。
3.
转入中断处理程序
将与中断事件对应的中断向量从内存指定单元取出送入PSW和PC中，如此便转入对应的中断处理程序。图
中断的响应过程
c)
中断源与中断字
引起中断的事件称为中断源。
用于保存与中断事件相关信息的寄存器称为中断寄存器。
中断寄存器中的内容称为中断字。
d)
中断类型
1.
强迫性中断
这类中断是正在运行的程序所不期望的，运行程序可能在任意位置被打断。
1.
时钟中断：时钟到时
2.
输入输出中断：设备出错、传输结束等
3.
控制台中断：系统操作员通过控制台发出命令
4.
硬件故障中断：掉电、内存校验错误等
5.
程序错误中断：目态程序执行特权指令、地址越界、溢出、除数为0、虚拟存储中的缺页故障等
2.
自愿性中断
这类中断事件是正在运行的程序有意识安排的，执行访管指令引起，目的是要求系统提供某种服务。
例如：一个C程序中的fp=fopen(“…txt”,
“r+w”);语句
e)
中断向量
每个中断处理程序都有一个入口地址(PC)及运行环境(PSW)，它们存放在内存中固定单元处。中断事件发生时中断装置利用PSW和PC转入对应的中断处理程序，类似向量转移。
因此，PSW和PC被称为中断向量。图
中断向量与中断处理程序
注意：
1.
每类中断事件有一个中断向量
2.
中断向量的存放位置是由硬件规定的
3.
中断向量的内容是OS在系统初始化时设置的
f)
中断嵌套
系统在处理一个中断事件的过程中又响应了一个新的中断，则称发生了中断嵌套。
一般只允许优先级更高的中断事件打断当前中断事件的处理过程，因此中断嵌套的实际层数一般不会超过中断优先级的个数。
四、
中断处理程序
进入中断处理程序后一般需要进一步保存现场。
中断装置响应中断后，通过中断向量转入中断处理程序。
中断处理程序需根据中断码进一步分析中断源，再进行相应的处理，最后根据情况决定是否需要切换进程。
a)
中断处理程序的结构
1.
关中断（屏蔽所有中断）
进一步保存现场（地址寄存器、通用寄存器等）
2.
开中断（开放高优先级别中断）
3.
中断处理
4.
恢复现场
5.
中断返回
b)
中断处理的整个过程（CPU在中断处理完成之后决定将资源交给哪个进程）
c)
中断续元
将用户自编的中断处理程序称为中断续元。
中断续元的入口地址称为中断续元入口。
五、
处理器调度
a)
定义
处理器调度(CPU
scheduling)指CPU资源在可运行实体之间的分配。
b)
分配
在不支持线程的系统中，OS将CPU分配给进程。
在支持线程的系统中，对于系统级线程，OS将CPU资源分配给线程。
对于用户级线程，OS将CPU资源分配给进程。
六、
处理器调度算法
（不考计算，知道算法的原理、意义、特点即可）
a)
概述
处理器调度算法确定了当处理器空闲时应选择哪一个就绪态进程使其投入运行。
b)
选择处理器调度算法时的指标
1.
CPU利用率：使CPU尽量处于忙碌状态
2.
吞吐量：单位时间内所处理计算任务的数量
3.
周转时间：从计算任务就绪到处理完毕所用的时间
4.
响应时间：从任务就绪到开始处理所用的时间
5.
系统开销：系统调度进程过程中所付出的时空代价
c)
衡量就绪任务处理效率的度量标准
1.
周转时间(turnaround
time)：由就绪开始时刻到处理完毕时刻的时间；
2.
平均周转时间(average
…)：所有进程的周转时间之和与进程个数的比值；
3.
等待时间：周转时间与处理时间之差；
4.
平均等待时间：所有进程的等待时间之和与进程个数的比值。
d)
处理器的调度时刻
1.
非剥夺式调度(non-preemptive)
1.
是指一个进程不能从正在运行的进程那里抢占CPU
2.
采用非剥夺式调度方式时，一个进程一旦被选中运行，将一直运行下去，直至出现如下情形：(1)该进程因某种事件而等待；(2)该进程运行完毕。
3.
优点：系统开销较小
4.
缺点：不能保证当前正在运行的进程永远是系统当前可运行进程中优先数最高的进程。
2.
剥夺式调度(preemptive)
1.
是指一个进程可以从正在运行的进程那里抢占CPU
2.
采用剥夺式调度方式时，发生如下情形可能导致进程切换:
(1)运行进程因某种事件而等待;
(2)运行进程运行完毕;
(3)出现了新的、优先级高于正在运行进程的就绪进程。
新的就绪进程可能是某进程被唤醒，也可能是动态创建的新进程。
3.
优点：能保证正在运行的进程永远是系统内当前可运行进程中优先级最高的进程。
4.
缺点：CPU在进程间频繁切换,系统开销较大。
七、
常用的处理器调度算法（八个）
a)
先到先服务算法（非剥夺式）
1.
基本思想
先到先服务(first
come
first
serve,
FCFS)算法按照进程申请CPU的次序（即进程进入就绪态的次序）进行调度。
2.
优点
具有公平性，不会出现饿死的情况。
3.
缺点
短进程（线程）等待时间长，从而导致平均等待时间较长。
4.
例子b)
最短作业优先算法（非剥夺式）
1.
基本思想
最短作业优先算法(shortest
job
first,
SJF)算法按照CPU阵发时间递增的次序调度，易于证明其平均周转（等待）时间最短。（证明见作业二）
SJF算法中的长短是指CPU阵发时间的长短。2.
优点
所有任务同时到达时，其平均周转时间最短，从而最大限度地降低了平均等待时间。
3.
缺点
具有不公平性。一个较长的就绪任务可能由于短任务的不停到达而长期得不到运行机会，发生饥饿，甚至被饿死。
4.
例子c)
最短剩余时间优先算法（剥夺式）
1.
基本思想
最短剩余时间优先算法(shortest
remaining
time
next,
SRTN)算法执行以下操作：
1.
当CPU空闲时，选择剩余时间最短的线程或进程。
2.
当一个新进程或线程到达时，比较新进程与当前运行进程的估计剩余时间。如果新进程所需的运行时间时间短，则切换运行进程。
2.
实质
该算法实质上是可剥夺形式的最短作业优先算法，能有效的增加系统吞吐量。
d)
最高响应比优先算法（非剥夺式）
1.
基本思想
最高响应比优先算法(highest
response
ratio
next,
HRN)算法是先到先服务算法和最短作业优先算法的折中，它按照响应比由大到小的次序调度。
2.
响应比计算公式
RR=BT+WTBT=1+WTBT
其中，RR为响应比，BT为CPU阵发时间，WT为等待时间。
显然，对于同时到达的任务，处理时间较短的任务将被优先调度，处理时间较长的任务将随着等待时间的增加而动态提升其响应比，因而不会出现饥饿现象。
3.
缺点
系统开销较大，要时常计算每个进程的响应比。
e)
最高优先数优先算法
1.
基本思想
最高优先数优先(highest
priority
first,
HPF)算法，在每个进程的PCB块中有一个用数字表示的优先数。当需要进行处理器分配时，系统在可运行进程中选择优先数最高者使其投入运行。
2.
优先数的确定方法
1.
静态优先数
每个进程在创建时被赋予一个优先数,
该优先数在进程的整个生存期内固定不变。
优点：比较简单,
开销较小；
缺点：公平性差,
可能造成低优先数进程的长期等待。
静态优先数法适合于批处理进程。
2.
动态优先数
每个进程在创建时被赋予一个优先数,该优先数在进程的生存期内可以动态变化。
比如，当进程获得某种资源时，其优先级应增高。又如，当进程处于就绪状态时，其优先级应随着等待时间的增长而提高等。因此，动态优先数算法适用于实时系统。
优点：资源利用率高，公平性好；
缺点：开销较大，实现较为复杂。
3.
处理机的调度时刻
1.
非剥夺式静态优先数
获得CPU的进程一直运行，直至终止、等待
2.
剥夺式动（静）态优先数
获得CPU的进程运行，直至终止、等待、出现高优先级的进程
f)
循环轮转算法（剥夺式）
1.
基本思想
循环轮转(round
robin,
RR)算法，系统为每个进程规定一个时间片(time
slice)，所有进程按照其时间片的长短轮流地运行。
2.
调度过程
采用循环轮转算法时，所有就绪进程排成一个队列。
当处理机空闲时便选择队列头部的进程使其投入运行，同时分给它一个时间片，当此时间片用完时，如果此进程既未结束，其CPU阵发也未因某种原因而等待，则剥夺此进程所占有的处理机，将其排在就绪队列的尾部，并选择就绪队列中队头的进程运行。
3.
时间片
采用循环轮转法进行调度时，时间片的长度需认真加以考虑。
如果时间片过长，则会影响系统的响应速度；
如果过短，则会频繁地发生进程切换，增加系统的开销。
通常，时间片的长度为几十毫秒至几百毫秒。
4.
优点
循环轮转法特别适用于分时系统，具有公平性且响应及时等特点。
g)
分类排队算法
1.
基本思想
分类排队(multi
level
queues,
MLQ)算法又称多级队列法，它以多个就绪队列为特征。这些队列将系统中所有可运行的进程按照某种原则加以分类，以实现某种调度目标。
2.
例子例如，在通用操作系统中，可将所有就绪进程排成如下三个队列：Q1:
实时就绪进程队列Q2:
分时就绪进程队列Q3:
批处理就绪进程队列
当处理机空闲时，首先选择Q1中的进程，若Q1为空，则选择Q2中的进程；若Q1、Q2均为空，则选择Q3中的进程。
每个队列内部又可分别采用不同的调度算法。
h)
反馈排队算法
1.
基本思想
在分类排队算法中，进程不能在就绪队列之间移动。
反馈排队算法(feed
back,
FB)也以多个就绪队列为特征，每个队列内部采用循环轮转算法，与分类排队算法不同的是进程可以在不同的就绪队列之间移动。
这些就绪队列的优先级依次递减，而其时间片长度则依次递增。图
反馈排队算法
当一个进程被创建或者等待的时间发生时，进入第一级就绪队列。
当某队列的一个进程获得处理器并且使用完该队列所对应的时间片后，如果它尚未结束，则进入下一级就绪队列。
2.
特点
1.
短进程优先处理
运行时间短的进程在经过前面几个队列之后便已经执行完，而这些队列中的进程将被优先调度。
2.
设备资源利用率高
因为与设备打交道的进程可能会由于下面的原因而进入等待状态：
(a)
所申请的资源被占用；(b)启动了I/O传输。
当进程得到所等待的资源或I/O传输完成时，它将进入第一级就绪队列，尽快获得CPU并使用资源。
3.
系统开销较小
因为运行时间长的进程最后进入优先级低的队列，这些队列的时间片较长，因而进程的调度频率较低。
3.
缺点
在反馈排队法中，如果高优先级队列一直不为空，则低优先级队列中的进程可能长时间得不到运行的机会，如此便可能会发生“饿死”现象。
为解决这一问题，常根据某种原则允许将低优先级队列中的进程移到高优先级队列中去。比如可以借助动态优先数算法调整顺序。
4.
优点
反馈排队算法是适应性(adaptive)调度的一个很好的例子。
八、
调度级别与多级调度
a)
处理器调度与低级调度
处理器调度也称为低级调度(low-level
scheduling)或短程调度(short
term
scheduling)，它将处理器资源分配给进程或线程使其真正向前推进。
低级调度与中级调度和高级调度一起构成多级调度。
b)
交换与中级调度
1.
交换
交换(swapping)是进程在内存和外存储器之间的调度。
交换的目标一般有两个：
1.
缓解内存空间等资源紧张的矛盾
2.
减小并发度以降低系统开销
提高并发度可提高资源利用率从而提高系统效率，但并发度不是越高越好。
并发度过高会导致激烈的资源竞争而使进程经常等待其它进程占有的资源，从而降低进程推进速度，甚至可能导致死锁；并发度过高还会导致CPU资源在进程或线程间的频繁切换，从而增加系统开销。
2.
中级调度
中级调度(middle-level
scheduling)是系统控制并发度的一个调度级别。
当系统并发度过高时，将内存中的某些进程暂时交换到外存储器，待系统并发度较低时再调回内存。图
具有中级调度的进程状态转换关系
（在外存中的进程由等待态到就绪态的转换可以在外存中直接完成）
c)
作业与高级调度
1.
作业调度
作业调度(job
scheduling)又称高级调度或长程调度，其职能是将一个作业由输入井调入内存，并为其建立相应的进程，使其具有运行的资格。
2.
作业的五个状态
提交状态：由输入机向输入井传输的作业处于提交状态；
后备状态：已进入输入井但未调入内存的作业处于后备状态;
执行状态：被作业调度选中进入内存处理的作业处于执行状态;
(作业分解为进程)
完成状态：处理完毕、结果在输出井的作业处于完成状态；
退出状态：由输出井向打印设备传送的作业处于退出状态。3.
作业状态之间的转换
提交->后备：由SPOOLing输入进程完成;
后备->执行：由作业调度程序(1)完成;
执行->完成：由作业调度程序(2)完成；
完成->退出：由SPOOLing输出进程完成。图
作业状态转换关系
作业调度程序(1)：
按照作业调度算法在后备作业集合中选择作业，并为其建立作业控制进程来处理该作业。
作业调度程序(2)：
等待终止的作业控制进程，并对其进行善后处理。
4.
作用
作业调度使作业以进程的形式进入内存，并获得运行资格。
但真正获得CPU运行还需要经过进程调度。
作业调度、中级调度、进程调度构成调度的三个主要级别
第四章
互斥、同步与通信
一、
进程互斥
进程互斥是进程间发生的一种间接相互作用。
这种相互作用是进程本身所不希望的，也是运行进程感觉不到的。
进程互斥可能发生在相关进程之间，也可能发生在无关进程之间。
二、
共享变量与临界区
a)
共享变量：
多个进程均需要访问的变量称为公共变量(shared
variable)，也称共享变量。
b)
临界区：
访问共享变量的程序段称为临界区(critical
region)，也称临界段。
临界区是一段代码。图
共享变量与临界区的关系
三、
临界区与进程互斥
a)
进程互斥的定义
两个或两个以上的进程不能同时进入关于同一组共享变量的临界区，否则可能发生与时间有关的错误，这种现象称为进程互斥。
注意，进程互斥是相对于共享变量而言的。
b)
进程互斥的实现
临界区的框架如下：
do
{
entry
section
临界区
exit
section
}while(1);
实现互斥就是要编写entry
section和exit
section，保证同一时刻最多只能有一个进程处于临界区内。
c)
临界区相当于一个独占型资源，对这个资源的管理应当满足以下原则：
(1)当关于某一组共享变量的所有临界区均为空闲时，一个要求进入该组共享变量某一临界区的进程应能立即进入;
(2)当关于某一组共享变量的某一临界区域被占用时，一个要求进入该组共享变量某一临界区域的进程应等待;
(3)当一个进程离开关于某一组共享变量的某一临界区时，应容许某一个等待进入关于该组共享变量某一临界区域的进程进入。
四、
进程同步
a)
进程同步的定义
进程同步是进程之间的直接相互作用，是合作进程之间有意识的行为，这种相互作用只发生在相关进程之间。b)
进程同步的概念
1.
进程同步
一组进程，为了协调其推进速度，在某些点处需要相互等待与相互唤醒，进程之间的这种相互制约关系称为进程同步。
注意：
进程同步仅发生于有逻辑关系的进程之间；进程互斥可能发生于任意两个进程之间。
2.
进程合作
一组进程单独不能正常进行，但并发可以正常进行的现象称为进程合作。
参与合作的进程称为合作进程。
进程同步是合作进程之间的直接相互作用。
五、
进程同步机制
用于实现进程间同步的工具称为同步机制，又称同步设施。
典型的进程同步机制是信号灯与PV操作。
六、
信号灯与PV操作的相关定义
（要求能解决互斥、同步问题，如生产者消费者问题、读者写者问题、哲学家就餐问题）
a)
信号灯与PV操作的定义
1.
信号灯类型
定义：
struct
semaphore
{
int
value;
pointer_to_PCB
queue;
}
说明：
Semaphore
s;
2.
信号灯类型的value和queue
一个信号灯变量包括两个部分，即值部分s.value和指针部分s.queue。
在任意时刻，s.queue可能指向空，也可能指向一个由进程控制块所构成的队列的头部。初始时它指向空。
value表示当前可用的资源数。
s.value在创建时赋一次值，之后不能直接改变value的值，只能通过P/V操作改变。
value=0时表示资源已经分配完，value<0时表示当前没有可用资源，需要排队等待。
3.
asleep()与wakeup()函数
asleep(s->queue)
执行此操作的进程的进程控制块进入队列s->queue的尾部，其状态由运行态转为等待态，系统转到处理器调度程序。
wakeup()
将队列s->queue头部的进程的进程控制块由该队列中取出，并将其排入就绪队列，其状态由等待态转为就绪态。4.
P操作原语(down)
原语：一段不可间断执行的程序称为原语。
void
P(semaphore
*s)
{
s->value--;
if(s->value
<
0)
{
//
当前申请时已经没有可用资源了asleep(s->queue);
//
进入等待队列
}
}
P操作对应申请资源
5.
V操作原语(up)
void
V(semaphore
*s)
{
s->value++;
if(s->value
<=
0)
{
//
表示当前有进程正在等待队列中等待wakeup(s->queue);
//
自己释放资源的同时将资源分配给等待队列中的第一个进程
}
}
V操作对应释放资源
6.
注意，wakeup操作将等待队列的队头元素取出，并且将其由等待态改为就绪态，这表示将当前刚刚释放的那个资源分配给这个队头进程了。
只要有进程执行了V操作，就表示有资源被释放了，释放后value>=0表示当前没有其他进程正在等待这个资源，value<0表示等待队列中正有进程在等待资源，所以要将资源分配给它，并不是只有value>0才表示有资源可以分配给等待队列中的资源的！不要弄混了！
b)
关于信号灯变量的规定
1.
必须置一次初值，只能置一次初值，且初值必需为非负整数
2.
只能执行P操作和操作，其他操作均非法
c)
关于信号灯变量的几个有用的结论
1.
当s->value>=0时，s->queue为空
2.
当s->value<0时，|s->value|为s->queue中等待进程的个数
3.
当s->value的初值为1时，可以用来实现进程互斥，这只需在进入临界区时执行一次P操作，离开临界区时执行一次V操作。
4.
当s->value的初值为非1的正整数时，可以用来管理同种组合资源（具有多个实例的同类资源，如5台打印机），申请时执行一次P操作，归还时执行一次V操作。
5.
当s->value的初值为0时，可以实现进程间的简单同步。
（需要先执行的动作执行V操作，后执行的动作在之前执行要先执行P操作后再执行）
七、
信号灯与PV操作的应用
a)
用信号灯变量实现进程互斥（初值为1）
1.
说明2.
图书借阅系统问题b)
用信号灯变量实现进程同步（初值为0）
1.
说明先动作的进程执行完动作后进行V操作，相当于给后动作的进程发出一个信号，告诉后动作进程可以开始执行了。
后动作的进程通过P操作表示看到这个信号了，然后就开始执行后动作。
2.
司机与售票员问题注意，一组先后动作对应一个信号灯。
P2先关车门，P1后启动；P1先停好车，P2后开门。
八、
用信号灯变量解决综合问题——生产者—消费者问题
a)
问题描述b)
问题分析c)
问题解决d)
求解程序
e)
优化f)
问题实质（如果是无界缓冲区，in和out的操作直接为in+1和out+1即可，不需要%k）
九、
用信号灯变量解决综合问题——读者—写者问题
a)
问题描述b)
问题分析与解决c)
求解程序
d)
分析与改进
分析:
R-R不互斥。若读者源源不断，写者可能饿死。
其实写者的操作是更新数据，应优先进行，否则读者将读到过时的数据。
改进：写者优先。
一旦有写者等待，正在读的读者都结束后，写者进入，新到达的读者等待。十、
用信号灯变量解决综合问题——哲学家就餐问题
a)
问题描述
五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一盘通心粉。由于通心粉很滑，所以需要两把叉子才能夹住。相邻两个盘子之间放有一把叉子，餐桌如图所示。哲学家的生活中有两种交替活动时段：即吃饭和思考（这只是一种抽象，即对哲学家而言其他活动都无关紧要）。
当一个哲学家觉得饿了时，他就试图分两次去取其左边和右边的叉子，每次拿一把，但不分次序。如果成功地得到了两把叉子，就开始吃饭，吃完后放下叉子继续思考。
关键问题是：能为每一个哲学家写一段描述其行为的程序，且决不会死锁吗？
b)
问题分析
哲学家从来不交谈，这就很危险.
可能产生死锁，每个哲学家都拿着左手的餐叉，永远都在等右边的餐叉（或者相反）。
即使没有死锁，也有可能发生资源耗尽。例如，假设规定当哲学家等待另一只餐叉超过五分钟后就放下自己手里的那一只餐叉，并且再等五分钟后进行下一次尝试。这个策略消除了死锁（系统总会进入到下一个状态），但仍然有可能发生“活锁”。如果五位哲学家在完全相同的时刻进入餐厅，并同时拿起左边的餐叉，那么这些哲学家就会等待五分钟，同时放下手中的餐叉，再等五分钟，又同时拿起这些餐叉。
c)
问题解决
1.
引入服务生
一个简单的解法是引入一个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉。因为服务生知道哪只餐叉正在使用，所以他能够作出判断避免死锁。
为了演示这种解法，假设哲学家依次标号为A至E。如果A和C在吃东西，则有四只餐叉在使用中。B坐在A和C之间，所以两只餐叉都无法使用，而D和E之间有一只空余的餐叉。假设这时D想要吃东西。如果他拿起了第五只餐叉，就有可能发生死锁。相反，如果他征求服务生同意，服务生会让他等待。这样，我们就能保证下次当两把餐叉空余出来时，一定有一位哲学家可以成功的得到一对餐叉，从而避免了死锁。
2.
限制最多4位哲学家同时进餐
3.
将哲学家的状态增加至3个，即思考、饥饿、进食。每个哲学家仅在饥饿时才申请叉子，并且同时申请其左右两把叉子，如果此时左右两把叉子不为空闲，则他将等待。
d)
限制最多4位哲学家同时进餐的求解程序
VAR
fork
Array
[0..4]
of
Semophore=(1,1,1,1,1)
VAR
count
:
semophore
=4
philosopher(i):
beginrepeat
THINK;
P(count)
P(fork[i])
P(fork[i+1]
mod
5)
EAT
V(fork[i+1]
mod
5)
V(fork[i])
V(count)
until
false
end;
e)
同时申请两把叉子的求解程序
用SP
信号量集解决哲学家进餐问题
VAR
fork
array[0..4]
of
Semaphore
=
(1,1,1,1,1);
Phi
:
beginrepeatTHINK;SP(
fork[i],
fork[(i+1)mod
5]
);EAT;SV(
fork[i],
fork[(i+1)mod
5]
);
until
false;
end
f)
问题实质
在实际的计算机问题中，缺乏餐叉可以类比为缺乏共享资源。
一种常用的计算机技术是资源加锁，用来保证在某个时刻，资源只能被一个程序或一段代码访问。
当一个程序想要使用的资源已经被另一个程序锁定，它就等待资源解锁。
当多个程序涉及到加锁的资源时，在某些情况下就有可能发生死锁。
例如，某个程序需要访问两个文件，当两个这样的程序各锁了一个文件，那它们都在等待对方解锁另一个文件，而这永远不会发生，这样就会导致死锁。
十一、
用信号灯变量解决综合问题——三台打印机的管理
a)
问题描述
设有3台类型相同的打印机，其编号分别为1、2、3，试编写一个申请函数require和一个释放函数return。
require当有打印机空闲时，返回分得的打印机的编号；当无打印机空闲时则等待，被唤醒后返回分得的打印机的编号。
return用于释放指定编号的空闲打印机，当有申请者等待时就将其一唤醒。
b)
求解程序
enum
lp[1..3]
of
(free,used);
//(initial
value
is
free)
表示空闲或使用状态
semaphore
S;
//(initial
value
is
3)
表示3台打印机
semaphore
mutex;//(initial
value
is
1)
用于实现互斥
1..3:
require();
void
return(i:
1..3);
{
{
P(S);
P(mutex);
P(mutex);
lp[i]=free;
//释放打印机
for(i=1;
i<=3;
i++)V(mutex);
if(lp[i]==free)V(S);
break;
}
lp[i]=used;
//占用第一台空闲打印机
V(mutex);
return(i);
}
十二、
用信号灯变量解决综合问题——吸烟者问题
a)
问题描述
假设一个系统中有三个抽烟者进程，每个抽烟者不断地卷烟并抽烟。抽烟者卷起并抽掉一颗烟需要有三种材料：烟草、纸和火柴。一个抽烟者有烟草，一个有纸，另一个有火柴。
3个供应商进程如下：
X:
提供
tobacco
和match
Y:
提供
match
和wrapper
Z:
提供
wrapper
和tobacco
tobacco烟草match火柴wrapper纸
3个吸烟者进程如下：
A:
拥有
tobacco
B:
拥有
match
C:
拥有
wrapper
限制条件如下：
(1)
同一时刻只有X、Y、Z之一可以供应资源；
(2)
在所提供的资源被耗尽后，X、Y、Z之一可以继续供应资源。
b)
传统解法
传统信号量的解法如下：
semaphore
t,
m,
w,
s;
//0,
0,
0,
1
//
t,
m,
w分别表示三种烟的量
//
s用于实现互斥
Process
X
process
Y
process
Z
P(s);P(s);P(s);
V(t);V(m);
V(w);
V(m);
V(w);
V(t);Process
A
Process
B
process
C
P(m);
P(w);
P(t);
P(w);
P(t);P(m);
smoke;
smoke;
smoke;
V(s);V(s);V(s);
c)
存在问题
进程X提供的tobacco和match分别被进程A和进程C获得，将导致死锁。
任意改变吸烟者进程的两个P操作的次序，不能防止死锁的发生。
d)
问题原因及解决方式
产生这种错误的原因是吸烟者进程所需要的另外两种资源是通过两个P操作分别申请的。
如果两种资源同时申请（同时执行P操作），则可以防止这种问题。
e)
解决问题
为此需要扩展P操作，使其能够对多个信号量变量同时执行P操作和V操作，这就是SP(simultaneous
P，同时执行P操作)和SV(同时执行V操作)。
它们作用在信号量集合上
f)
SP和SV操作
//
si的最小值是ti，每次变换的步长是di
SP(S1,t1,d1;
…;
Sn,tn,dn);
{
if
S1>=t1
and
…
and
Sn>=tn
then
for
I:=1
to
n
do
Si:=Si-di
endfor
else
将运行进程的进程控制块连到第一个si
将该进程的指令计数器内容设置为SP操作的起始位置，使得当该进程重新执行时可以对所有等待条件重新进行评估；
}
SV(s1,
d1
,
…
sn,
dn
)
{
for
i:=
1
to
n
do
Si
=
Si
+
di
将si队列上的所有进程控制块取出，并连到就绪队列中；
}
其中si为信号量，当ti和di均为1时，称为and型信号量，是最常用的一种形式。
g)
正确解法
semaphore
t,
m,
w,
s;
//0,
0,
0,
1
Process
X
Process
Y
Process
Z
loop
loop
loop
P(s);
P(s);
P(s);
SV(t,1;
m,1);SV(m,
1;w,
1);
SV(w,
1;
t,
1);
endloop
endloop
endloop
Process
A
Process
B
Process
C
loop
loop
loop
SP(m,1,1;
w,1,1);
SP(w1,1;
t,1,1);
SP(t,1,1;
m,1,1);
smoke;
smoke;
smoke;
V(s);
V(s);
V(s);
endloop
endloop
endloop
十三、
进程高级通信的分类、概念及模式
a)
进程通信的分类
1.
低级通信
将进程互斥与进程同步称为进程之间的低级通信。
2.
高级通信
进程之间大宗数据的传递称为进程之间的高级通信。
b)
进程通信的概念
进程之间的互斥、同步及信息交换统称为进程通信
(inter-process
communication,
IPC)
c)
进程通信的模式
1.
共享内存模式(shared
memory)
这种模式只适用于单机系统。
相互通信的进程之间要有公共内存，一组进程向公共内存中写，另一组进程从该公共内存中读，如此便实现了进程之间的信息传递。
2.
消息传递模式(message
passing)
这种模式不只适用于单机系统，也可以用于网络环境下。
采用这种模式时，操作系统为用户进程之间的通信提供两个基本的系统调用命令（又称原语），即发送命令(send)和接收命令(receive)。
当需要进行消息传递时，发送者仅需执行发送命令，接收者仅需执行接收命令，消息便由发送者传送给接收者。
消息如何由发送者传送给接收者完全由OS完成，对用户是透明的。
十四、
进程通信的消息传递模式的两种实现方式
a)
概述
消息传递模式在实现时分为两种方式：
直接方式：进程-进程
间接方式：进程-信箱-进程
b)
直接方式
所谓直接方式是指相互通信的进程之间在通信时直呼其名。
也就是说，发送者在发送时要指定接收者的名字，接收者在接收时要指定发送者的名字。
其系统调用主要有以下两种形式：
1.
对称形式(symmetric)
对称形式的特点是一对一的，发送者在发送时指定唯一的接收者，接收者在接收时指定唯一的发送者。
系统调用命令如下：
send(R,
M)
将消息M发送给进程R
receive(S,
N)
从进程S处接收消息至N
2.
非对称形式(asymmetric)
非对称形式的特点是多对一的，即发送者在发送时指定唯一的接收者，接收者在接收时不指定具体的发送者。
系统调用命定如下：
send(R,
M)
将消息M发送给进程R
receive(pid,
N)
接收消息至N，返回时设pid为发送进程标识
N是接收信息的内存，pid是发送进程号
发送进程相当于顾客，接收进程相当于服务员，一个服务员可以为多个顾客服务。在服务时并不知道哪位顾客要求其服务，哪一位顾客先到，就先为哪一位顾客服务。
c)
消息由发送进程空间传送到接收进程空间的途径
1.
有缓冲途径（要知道步骤）
采用这条途径时，在操作系统空间中保存着一组缓冲区。
发送进程在执行send系统调用命令时，产生自愿性中断进入操作系统，操作系统将为发送进程分配一个缓冲区，并将所发送的消息内容由发送进程空间复制到缓冲区中，然后将载有消息的缓冲区连到接收进程的消息链中。
如此就完成了信息的发送，发送进程返回到用户态，继续执行其下面的程序。
以后的某一时刻，当接收进程执行到receive系统调用命令时，也产生自愿性中断进入操作系统，操作系统将载有消息的缓冲区由消息链中取出，并将消息内容复制到接收进程空间中，然后收回该空闲缓冲区。
如此就完成了消息的接收，接收进程返回到用户态，继续执行其下面的程序。
因为消息在发送者与接收者之间的传输过程经过一次缓冲，所以提高了系统的并发性。因为发送者一旦将信息传送到缓冲区，就可以返回继续执行下面的程序，无须等待接收者真正执行接收这条消息的系统调用命令。图
发送进程与接收进程之间的关系
（M为进程发送区的起始地址，N为进程接收区的起始地址）图
缓冲区中的消息
（不论是发送者和接收者对消息链的操作应当是互斥进行的，每个进程都有可能作为接收进程，因此都有一条消息链，都有一个用于此消息链互斥的变量m_mutex，分别存放在各个进程的PCB中）图
空闲缓冲区链
（收发进程之间的关系类似于生产者——消费者问题，消息缓冲区就类似于箱子，也有一个容量k）现在给出发送原语send和接收原语receive的实现过程。Send和receive属于系统调用命令，位于用户程序中。当系统在用户态执行到这些命令时，将发生自愿性中断事件，进入操作系统，经过操作系统总控程序判断后，转到相应的处理程序。Sb是缓冲区可用数量，sm是接收进程的消息资源数量。注意：Send/receive
为高级通讯原语，可用低级原语PV实现；
但Send/receive不是真正意义的原语，可以被中断。
2.
无缓冲途径
如果操作系统没有提供消息缓冲区，将由发送进程空间直接传送到接收进程空间。
优点是节省空间。
缺点是并发性差，发送进程必须等到接收进程执行receive命令并将消息由发送进程空间复制到接收进程空间之后才能返回，以继续向前推进。
d)
间接方式
所谓间接方式是指相互通信的进程之间在通信时不是直呼对方名字，而是指明一个中间媒体，即信箱，进程之间通过信箱来实现通信。
此时，系统所提供的高级通信原语以信箱取代进程。
第五章
死锁与饥饿
一、
死锁的概念
一组进程中的每个进程均等待此组进程中其他进程所占有的、因而永远无法得到的资源，这种现象称为进程死锁，简称死锁(deadlock)
死锁发生后，参与死锁的进程将一直持续下去，除非有来自参与死锁进程之外的某种干预。
（1.
由进程竞争资源而引起的僵持称为死锁）
（2.
死锁的解除需要外在干预）
二、
关于死锁几个有用的结论（4个）
a)
参与死锁的进程数目至少为2
b)
参与死锁的所有进程均等待资源
c)
参与死锁的进程至少有2个占有资源
d)
参与死锁的进程是系统中当前正在运行的进程集合的一个子集
三、
死锁的类型
a)
竞争资源引起的死锁
由于进程争夺系统中有限资源引起的死锁。
下面谈论的死锁都是这种类型的死锁。
可再用资源：不能被多于一个进程同时使用，但被释放后可再被其它进程使用。
b)
进程通信引起的死锁
基于消息的系统中，P1等待P2的消息，P2等待P3的消息，P3等待P1的消息，这种因为循环等待消息引起的死锁称为进程通信引起的死锁。
生灭资源：使用后即不可再次利用的资源，比如消息就是生灭资源。
c)
其他原因引起的死锁
P1与P2竞争使用一个独占型资源，P1让P2先使用，P2让P1先使用，则两个进程均无法推进，这称为“After
You/After
You”问题。
四、
死锁的条件（4个）
下面给出死锁发生的4个必要条件，也称为coffman条件。
a)
资源独占(mutual
exclusion)
一个资源在同一时刻只能被分配给一个进程。
如果一个进程申请某一资源，而该资源正在被另外的某一进程所占有，则申请者需要等待，
直到占有者释放该资源。
b)
不可剥夺(non-preemption)
资源申请者不能强行地从资源占有者手中夺取资源，即资源只能由其占有者在使用完后自愿地释放。
c)
保持申请(hold
and
wait)
进程在占有部分资源后还可以申请新的资源，而且在申请新资源的时候并不释放它已经占有的资源。
d)
循环等待(circular
wait)
存在一个进程等待序列{p1,
p2,
…,
pn}，其中p1等待p2所占有的某一资源，p2等待p3所占有的某一资源……pn等待p1所占有的某一资源。
e)
当且仅当上述4个条件同时满足时，死锁才会发生。
换言之，只要破坏4个条件中任意一个，死锁就不会发生。
五、
死锁的处理
死锁的处理分为死锁的预防和死锁的避免。
a)
预防（静态）
预防就是对进程有关资源的活动加以静态的限制，所有进程都遵守协议即可不发生死锁。
预防策略有两种：预先分配和有序分配
1.
预先分配
进程在运行前一次性地向系统申请它所需要的全部资源。如果系统当前不能满足进程的全部资源请求，则不分配资源，此进程暂时不投入运行。如果系统当前能满足全部资源请求，则一次性地将所申请的资源全部分配给此进程。
进程在投入运行前就已经申请了所需要的全部资源，所以在运行期间不会再发出新的资源申请命令，破坏了“保持申请”这个必要条件。
2.
有序分配
事先将所有资源类完全排序，对每个资源类赋予唯一的整数，进程必须按照资源编号从小到大的次序申请资源。
即进程不占用资源时
可申请ri的多个资源，此后它申请rj中资源的充要条件是：f(ri)它必须一次申请。
换言之,
进程可申请某一资源类ri中资源的充要条件是它已释放了资源类rj中的所有资源,
这里f(ri)这种策略可以破坏“循环等待”这个必要条件。
b)
避免（动态）
避免就是对进程有关资源的申请命令加以动态的实时检测，拒绝不安全的资源请求命令，保证死锁不会发生。
六、
银行家算法（掌握思想，不需要写）
银行家算法就是一种避免死锁的算法。
a)
安全状态与不安全状态
如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态时一定没有死锁发生。
安全序列是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj
(j
<
i
)当前占有资源量之和。
因此安全状态至少存在一条路线：由p1到pn依次执行的路线，使得所有进程可以执行完，所以不存在死锁。
安全状态一定不是死锁状态，不安全状态不一定是死锁状态。
b)
说明
当一个新进程进入系统时，它必须声明其最大资源需求量，即每个资源类各需要多少资源实例。
当进程发出资源申请命令而且系统能够满足该请求时，系统将判断：如果分配所申请的资源，系统的状态是否安全。
如果安全则分配资源，并让申请者继续；否则不分配资源，并让申请者等待。c)
实现银行家算法所需要的数据结构
设n为系统中的进程的总数，m为资源类的总数。
P={p1,p2,…,pn};
R={r1,r2,…,rm};
1）可利用资源向量int
Available[m]
是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。初始时Available的值为系统资源总量。
2）最大需求矩阵int
Claim[n,
m]
这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Claim
[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
3）分配矩阵int
Allocation[n,
m]
这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。初始时Allocation[I,
j]=0。
4）需求矩阵int
Need[n,
m]
这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
Need[i,j]=
Claim
[i,j]-Allocation[i,j]
初始时Need=Claim
5)
当前请求矩阵
int
Request[n,
m]
这也是一个n×m的矩阵，用以表示每一个进程当前申请各个资源类中的资源实例的数量。如果Request[I,
j]=k，则进程i还需要资源rj中的k个资源实例。引入下列记法：
设X,Y为下标1..l的一维数组：
X￡Y
?
“j
(1￡j￡l),
X[j]￡Y[j]
X=Y
?
“j
(1￡j￡l),
X[j]=Y[j]
X=c
?
“j
(1￡j￡l),
X[j]=c
X±Y
?
“j
(1￡j￡l),
X[j]±Y[j]
为了实现安全性检查，需要定义以下数据结构：
6)
int
Work[m]
记录可用资源
7)
int
Finish[n]
记录进程是否可以执行完
d)
银行家算法——资源分配算法e)
银行家算法——安全性检测算法f)
银行家算法例子g)
银行家算法的保守性
七、
饥饿与活锁
a)
定义
当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿(starvation)，当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死(starve
to
death).
在忙式等待条件下发生的饥饿，称为活锁．
（饥饿是没有上界的等待，一般是因为资源分配不合理所致，等待时间超过极限就会导致饿死。）
b)
死锁与饿死的联系
饿死与死锁有一定联系：二者都是由于竞争资源而引起的，但又有明显差别，主要表现在如下几个方面：
(1)
从进程状态考虑，死锁进程都处于等待状态，忙式等待(处于运行或就绪状态)的进程并非处于等待状态，但却可能被饿死.
(2)
死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源，其等待时限没有上界(排队等待或忙式等待).
(3)
死锁一定发生了循环等待，而饿死则不然.
这也表明通过资源分配图可以检测死锁存在与否，但却不能检测是否有进程饿死.
(4)
死锁一定涉及多个进程，而饥饿或被饿死的进程可能只有一个．
c)
饥饿和饿死与资源分配策略(policy)有关，因而防止饥饿与饿死可从公平性考虑，确保所有进程不被忽视，如FCFS分配算法.
八、
死锁与饥饿的例子——独木桥问题
a)
题目描述
假设有一座东西向的车辆单行道的桥，如图所示，每次允许同方向的若干车辆通过（即桥上可以有多个同方向的车辆通过）。在桥上没有车辆时，任何一端的车辆都允许上桥通过，当有车辆上桥后，同端的车辆可以继续上桥，但另一端的车辆不能上桥。最大可载重4辆汽车。请用P、V操作来实现东西两端人过桥的问题。b)
分析思想：
本题基于读者－写者问题算法（写进程优先）。
设置两个变量：
eastn记录从东端上桥到西端的车辆数，
westn记录从西端上桥到东端的车辆数，
它们的初值均为0。
这两个变量都是互斥访问的，为此设置两个互斥访问的信号量meast和mwest，它们的初值均为1。
对于从东端过桥和从西端过桥的车辆而言，桥上没有车辆时，谁先请求谁先过桥，所以再设置一个互斥访问信号量wait，其初值为1。
增设一个信号量scount，表示桥上最多可同时上桥的车辆数，其初值为4。
int
eastn=0;
//记录从东端上桥到西端的车辆数
int
westn=0;
//记录从西端上桥到东端的车辆数
Semaphore
meast=1;
//保护eastn变量的信号量
Semaphore
mwest=1;
//保护westn变量的信号量
Semaphore
scount=4;
//表示桥上车辆计数信号量
Semaphore
wait=1;
//确定东、西两端过桥请求过桥顺序的互斥信号量1）?巴拿马运河大西洋，太平洋两个方向的船设置为两个进程Atlantic(),Pacific();?
2）?当一侧船来到运河，如果另一侧船在过河，则等待；如果自己方船在过河，同时己方船只的总过河船数小于T，则过河；如果己方船在过河，同时己方船只过河总数大于T，则等待。?
3）?为了避免饥饿和死锁，必须控制一次过河的船数T。
c)
解决程序
main()
{
Cobegin
{
进程easti（i=1,2,…）
//东端车辆过桥进程
{
while
(true)
{
P(wait);
//东端车辆先请求，则先过桥
P(meast);
//拒绝访问eastn变量
if
(eastn==0)
//若东端第一辆车过桥，则禁止西端车辆过桥
P(mwest);
eastn=eastn+1;
//东端过桥车辆数增1
V(meast);
//恢复访问eastn变量
V(wait);
//恢复车辆过桥
P(scount);
//递减还可同时上桥的车辆数
从东端向西端过桥;
V(scount);
//递增还可同时上桥的车辆数
P(meast);
//拒绝访问eastn变量
eastn--;
//东端过桥车辆数减1
if
(eastn==0)
//若东端没车辆过桥，则允许西端车辆过桥
V(mwest);
V(meast);
//恢复访问eastn变量
}
}进程westj（j=1,2,…）
//西端车辆过桥进程
{
while
(true)
{
P(wait);
//西端车辆先请求，则先过桥
P(mwest);
//拒绝访问westn变量
if
(westn==0)
//若西端第一辆车过桥，则禁止东端车辆过桥
P(meast);
westn=westn+1;
//西端过桥车辆数增1
V(mwest);
//恢复访问westn变量
V(wait);
//恢复车辆过桥
P(scount);//递减还可同时上桥的车辆数
从西端向东端过桥;
V(scount);
//递增还可同时上桥的车辆数
P(mwest);
//拒绝访问westn变量
westn--;
//西端过桥车辆数减1
if
(westn==0)
//若西端没车辆过桥，则允许东端车辆过桥
V(meast);
V(mwest);
//恢复访问westn变量
}
}
}
Coend
}
另一种解法：
九、
死锁与饥饿的例子——过河问题
a)
问题描述b)
问题分析
限定同时过河的人数在5个以内。
对两岸竞争的1、2和3、4两对石块，采用有序分配法。c)
求解程序十、
系统举例
死锁在大多数系统中都采用视而不见的“鸵鸟算法”，只在Edsger
Wybe
Dijkstra设计并实现的THE系统中采用了避免死锁的银行家算法。
第六章
存储管理
一、
内存资源管理
a)
内存分区
分区时刻
静态分区：系统初始化时分；
动态分区：申请时分。
分区大小
等长分区：2i
异长分区：依程序、程序单位、对象大小。
通常作法
静态+等长（页式、段页式）
动态+异长（段式、界地址）
b)
内存分配
1.
静态等长分区的分配
l
字位映象图（bit
map）l
空闲页面表l
空闲页面链（链表操作较耗费资源）2.
动态异常分区的分配（要能区分三种算法）
为了管理这些长度不等的区域，需要一种称为空闲区域表的数据结构l
最先适应算法l
最佳适应算法l
最坏适应算法二、
存储管理方式（三张图非常重要）
a)
页式存储管理
P181-P187
重点为P184
图6-16
b)
段式存储管理
P187-P193
重点为P191
图6-27
c)
段页式存储管理（掌握思想即可）
P193-196
三、
虚拟存储系统（注意颠簸和页故障率反馈模型）
a)
无虚拟问题
不能运行比内存大的程序；
进程全部装入内存，浪费空间（进程活动具有局部性)。
b)
程序的局部性原理
1.
时间上的局部性
一条指令的执行与这条指令的下一次执行、一个数据的访问与这条数据的下一次访问在时间上是相对集中的。因为程序中存在大量循环操作。
2.
空间上的局部性
相邻的指令与相邻的数据在执行时经常被集中用到。因为程序是顺序执行的，并且有对数组的访问。
c)
虚拟存储
进程部分装入内存，部分（或全部）装入外存，运行时访问在外存部分动态调入，内存不够淘汰。
d)
虚拟页式存储管理
1.
基本原理
在程序运行之前，部分页面被装入内存，另一部分页面（或全部页面）被装入外存。在进程运行过程中，如果所访问的页面在内存，则与无虚拟的情形相同；如果所访问的页面不在内存，则发生缺页故障，进入操作系统，由操作系统进行页面的动态调度。
2.
缺页故障的中断处理程序
访问页不在内存，发生缺页中断，中断处理程序：
找到访问页在外存的地址；
在内存找一空闲页面；
如没有，按淘汰算法淘汰一个；
如需要，将淘汰页面写回外存，修改页表和总页表；
读入所需页面（切换进程，调度其他进程）；
重新启动进程，执行被中断的指令。
3.
内存页框分配策略
1.
平均分配
2.
按进程长度比例分配
3.
按进程优先级比例分配
4.
按进程长度和优先级别比例分配
4.
外存块的分配策略
1.
静态分配
外存保持进程的全部页面：
优点：速度快—在未修改页面的情况下淘汰时不必写回
缺点：外存浪费
2.
动态分配
外存仅保持进程不在内存的页面：
优点：节省外存
缺点：速度慢--淘汰时必须写回
5.
页面调入时机
1.
请调(demand
paging)
upon
page
fault,
发生缺页中断时调入。
2.
预调(prepaging)
before
page
fault,
在缺页故障之前调入(根据程序顺序行为，不一定准）
因为不一定准，所以依然可能缺页，所以预调必须辅以请调。
6.
置换算法
用于：页淘汰、段淘汰、快表淘汰。
1.最佳算法（理论上）
2.先进先出算法
3.最近最少使用算法
4.最近不用的先淘汰算法
5.最频繁使用算法
e)
颠簸(thrashing)
1.
颠簸的定义
页面在内存与外存之间频繁换入换出，以致系统用于调度页面的时间比进程实际运行所占用的时间还要长。
颠簸是由于页故障率过高而产生的结果。
2.
颠簸的原因
(1)
分给进程物理页架过少；
(2)
淘汰算法不合理；
(3)
程序结构。
程序滥用转移指令会影响程序的局部性。
3.
颠簸的处理
(1)
增加分给进程物理页架数；
(2)
改进淘汰算法；
(3)
改进程序结构。
尽量避免使用goto语句。
f)
工作集模型g)
页故障率反馈模型
工作集模型能够成功地指导页面的分配，从而防止发生颠簸。但是它的实现开销较大，使用较为困难。
颠簸是由于页故障率高引起的，所以系统可以通过页故障率的反馈信息来动态地调整页面的分配第七章
文件系统
一、
文件的概念
文件(file)是具有符号名且在逻辑上有完整意义的信息项的有序序列。
二、
文件的组织
a)
概述
文件的组织又称文件结构，其中涉及文件的逻辑组织与文件的物理组织。
文件的逻辑组织指文件的外部组织形式，即用户所看到的文件组织形式；
文件的物理组织指文件的内部组织形式，即文件在物理存储设备上的组织形式。
b)
文件的物理组织
1.
确定文件的物理结构应考虑如下因素（四种）：
(1)记录格式
文件的记录格式分为定长和变长两种。
定长格式实现较简单、速度快，但可能浪费存储空间；
变长格式实现较复杂、速度慢，但节省存储空间。
(2)空间开销
空间开销指除保存文件内容外所需的额外存储开销，包括外存开销及使用文件时所需的内存开销。
例如文件目录、信息记录以及内存调用时保存的信息。
(3)存取速度
存取速度包括顺序存取速度、按号随机存取速度及按键随机存取速度。
(4)长度变化
长度变化指文件长度的动态增加和动态减少,尤其指文件长度的动态增加。
2.
文件的常用物理组织形式：
顺序结构、链接结构、索引结构、散列(Hash)结构、倒排结构等。
c)
文件的常用物理组织形式
1.
顺序结构(sequential
structure)——数组
2.
链接结构(linked
structure)——链表3.
索引结构(indexed
structure)——结合以上两种结构的优点4.
散列结构(hash
structure)——哈希表5.
倒排结构(inverted
structure)6.
各种文件物理结构的主要特征比较三、
文件控制块
a)
定义
文件控制块(file
control
block,
FCB)是标志文件存在的数据结构,
其中包含系统对文件进行管理所需的全部信息。
b)
内容
文件名
共享说明
文件号
文件逻辑结构
用户名
文件物理结构
文件地址建立日期
文件长度最后修改日期
记录大小最后访问日期
文件类型口令
文件属性其它
四、
文件系统的实现
a)
什么是文件系统
文件与管理信息资源的程序集合称为文件系统(file
system)。
b)
概述
为实现文件系统，内存OS空间中需保存若干表目。
此外，还需要管理用于保存文件内容的外存空间。
c)
内存所需的表目
1.
系统打开文件表(整个系统一个)
FCB中保存着系统管理文件所需的信息，这些信息作为目录项长驻外存。
当一个文件被打开时，其FCB中的信息需经常被访问，为提高速度，需将其读至内存。
系统打开文件表就是内存中用来保存已打开文件FCB的表目。
表的内容除FCB主部外,
还包含三个信息:
(1)文件号:
用于得到该文件FCB主部在外存中的位置;
(2)共享计数:
用于记录当前有多少进程正在使用该文件。其值为零时表明是一个空表目;
(3)修改标志:
用于标识某文件的FCB在内存期间是否被修改过。当最后一个正在使用该文件的进程关闭该文件时,
如果该FCB在内存期间曾被修改过,
需将内存中修改后的FCB写回外存,否则不需刷新外存。2.
用户打开文件表（每个进程一个）
由于文件可共享，多个进程可能同时打开同一文件，而其打开方式可能不同，当前的读写位置也不一样。
这些信息被记录在另一个表中,
该表称用户打开文件表,
每个进程有一个。表中的系统打开文件表入口为一指针,
指向该文件FCB在系统打开文件表中的入口地址。当多个进程共用同一文件时,
不同进程的用户打开文件表中会有相同的系统打开文件表入口。
表中的文件描述符为一正整数,
其值由其在表中的位置隐含确定，故实际不记在表中，当文件被打开后返回给进程，以后进程便可使用描述符存取该文件，而不再使用文件名字。
用户打开文件表的存储位置记录于各进程的PCB中,
用户打开文件表的长度决定了一个进程可同时打开文件的最大数量。3.
用户打开文件表与系统打开文件表的联系
用户打开文件表指向系统打开文件表。若多个进程共享同一文件,
则多个用户打开文件表目指向系统打开文件表的同一入口。第八章
设备与输入输出管理
一、
设备的分类
a)
块型设备与字符型设备
1.
块型设备
块型设备就是存储型设备，这类设备由若干个长度相同的块所构成。
2.
字符型设备
字符型设备就是输入输出型设备（包括通信设备）。这类设备进行数据传输的基本单位是字节
b)
独占设备与非独占设备
1.
独占设备
独占设备包所有字符型设备及磁带机，任意一段时间之内只能有最多一个进程占有并使用它。
2.
共享型设备
共享型设备包括除磁带机以外的所有块型设备，多个进程的数据传输以块为单位是可以交叉的。
特例：磁带机虽然也是以块为单位的存储设备，但是因为物理特性的原因必须独占使用。
二、
数据传输方式——通道方式
a)
通道的定义
通道是专门负责输入输出操作的处理器，除DMA（存储器直接访问）数据块传输功能之外，通道还具有更加强大的输入输出功能。
b)
通道方式与DMA方式的区别
相同点：以内存为中心，支持块传输。
不同点：通道是专门的处理器，有自己的指令系统，可以实施复杂的输入输出控制。
c)
通道程序的位置
通道程序放在内存中
d)
通道的内容
通道相当于一个功能单纯的处理器，主要涉及以下内容：
1.
通道指令系统
基本操作：空操作、读、写、控制、转移、结束
指令格式：（操作码，传输量，特征位，地址）
操作码指定操作类型
2.
通道控运部件
CAW：记录下一条指令存放的地址，类似指令计数器
CCW：记录正在执行的指令，类似指令寄存器
CSW：记录通道、控制器、设备的状态
CDW：暂存内存与设备之间输入输出传输的数据
3.
通道存储区域
通道并没有独立的存储空间，它需要与主机共享同一个内存空间。
通过周期窃用方式实现通道与CPU的并行工作。4.
通道程序执行过程一条通道指令可以传送一组数据，一个通道程序可以传送多组数据。
多组数据全部传输完毕后才向处理器发一次中断，因而大大减轻了主机的负担。
三、
设备驱动
a)
通道程序
CCW指令序列
静态编制或动态生成
b)
设备启动
通道启动
c)
中断处理
通道结束操作后向CPU发的中断
d)
通道与处理器之间的相互作用关系（图要看明白）四、
虚拟设备
a)
定义
利用共享型设备实现的数量较多、速度较快的独占型设备成为虚拟设备。b)
虚拟设备的实现（重点）
以假脱机系统（又称SPOOLing系统）为例，介绍虚拟设备的实现。
P285-288
操作系统知识整理 本文关键词：操作系统，整理，知识
操作系统知识整理 来源：网络整理
免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
《操作系统知识整理》
由：76范文网互联网用户整理提供,链接地址：
http://m.yuan0.cn/a/57369.html
免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。