第三章——操作系统知识

前言：
计算机第三章节主要知识点。

1 知识点介绍

操作系统的作用；
进程（任务）管理；
存储管理；
文件管理；
设备管理；

2 操作系统的作用

通过资源管理（软硬件资源管理），提高计算机系统的效率，改善人机界面，向用户提供友好的工作环境。

3 进程管理

3.1 进程的概念

进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。它由程序块、进程控制块（PCB）和数据块三部分组成。

3.2 进程和程序的区别

进程是程序的一次执行过程，没有程序就没有进程；
程序是完成某一特定功能的一系列程序语句的集合，只要不被破坏，他就永远存在；
程序是一个静态的概念，进程是一个动态的概念，它由创建而产生，完成任务后因撤销而消亡；进程是系统进行资源分配和调度的独立单位，而程序不是。

3.3 三态模型

运行态：占有处理器正在运行；
就绪态：指具备运行条件，等待系统分配处理器以便运行；
等待态：又称为阻塞态或睡眠态，指不具备运行条件，正在等待某个事件的完成；

运行态——等待态：等待使用资源，如等待外设传输，等待人工干预；
等待态——就绪态：资源得到满足，如外设传输结束，人工干预完成；
运行态——就绪态：运行时间片到，出现有更高优先权进程；
就绪态——运行态：CPU空闲时选择一个就绪进程；

3.4 五态模型

挂起：将进程调出内存，保存到外村队列中，并释放资源；
激活：恢复挂起进程，重新调入内存；
目的：释放进程占用的资源以缓解资源不足；
原因：中断用户的请求，父进程的请求、OS的需要（如负荷调节、对换等）；

3.5 前趋图

入度：节点被箭头指向的个数；
出度：从这个节点出去的箭头个数；

3.6 进程的同步和互斥

3.7 PV操作

临界资源：诸进程间需要互斥方式对齐进行共享的资源，如打印机、磁带机等；
临界区：每个进程中访问临界资源的那段代码称为临界区；
信号量：是一种特殊的变量；

$S \geq 0$ : 表示资源的可用数；
$S < 0$ : 绝对值表示等待资源的进程数；

3.7.1 P操作

P操作要么不执行，要么全部执行，一旦执行不能中断。P操作作用是申请资源和阻塞进程。

3.7.2 V操作

V操作要么不执行，要么全部执行，一旦执行不能中断，V操作作用是释放资源和唤醒进程。

3.7.3 例题

进程P1、P2、P3、P4和P5的前趋图如下图所示：

若用PV操作控制进程P1、P2、P3、P4和P5并发执行的过程，则需要设置5个信号S1、S2、S3、S4和S5，且信号量S1~S5的初值都等于零。图中a和b处应分别填（C）；c和d处应分别填写（B）；e和f处应分别填写（B）。

(1)
A. V(S1) P(S2)和V(S3)
B. P(S1) V(S2)和V(S3)
C. V(S1) V(S2)和V(S3)
D. P(S1) P(S2)和V(S3)

(2)
A. P(S2)和P(S4)
B. P(S2)和V(S4)
C. V(S2)和P(S4)
D. V(S2)和V(S4)

(3)
A. P(S4)和V(S4) V(S5)
B. V(S5)和P(S4) P(S5)
C. V(S3)和V(S4) V(S5)
D. P(S3)和P(S4) V(S5)

某仓库有两名发货员，一名审核员。当顾客提货时，只要发货员空闲，允许顾客进入仓库提货，当顾客离开时，审核员就检验顾客提货是否正确。其工作流程如图所示。为了利用PV操作正确地协调他们之间的工作，设置了两个信号量S1和S2，且S1的初值为2，S2的初值为1.图中的a应填写（A）；图中的b、c和d应分别填写（C）。

(1)
A. P(S1) B. P(S2)
C. V(S1) D. V(S2)

(2)
A. P(S2)、V(S2)和V(S1)
B. P(S1)、V(S1)和V(S2)
C. V(S1)、P(S2)和V(S2)
D. V(S2)、P(S1)和V(S1)

3.8 进程管理

3.8.1 死锁

死锁概念 ：进程管理是操作系统的核心，但如果设计不当，就会出现死锁的问题。如果一个进程在等待一个不可能发生的事，则进程就死锁了。而如果一个或多个进程产生死锁，就会造成系统死锁。

3.8.1.1 例题

系统有3个进程：A、B、C。这3个进程都需要5个系统资源。如果系统有多少个资源，则不可能发生死锁？
答：各自有12个时，平均每个系统都占有4个缺1个时死锁，因此至少13个资源不会死锁。
系统最少有多少个资源不会发生死锁？公式如下。

$$
N \times (M - 1) + 1
$$

N: 进程数；
M：每个进程需要的系统资源数。

3.8.1.2 死锁解决

银行家算法：分配资源的原则

当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程；
进程可以分期请求资源，但请求的总数不能超过最大需求量；
当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源。

3.8.1.2.1 例题

假设系统中有三类互斥资源R1、R2、R3，可用资源数量分别为9、8、5。在T0时刻系统中有P1、P2、P3、P4、P5这5个进程，这些资源的最大需求量和已分配资源数量如下图所示：若按（B）执行序列，系统是安全的。

(1)
A. P1 -> P2 -> P4 -> P5 -> P3
B. P2 -> P4 -> P5 -> P1 -> P3
C. P2 -> P1 -> P4 -> P5 -> P3
D. P4 -> P2 -> P4 -> P1 -> P3

首先求剩下的资源数：

1
2
3

R1 = 9 - (1 + 2 + 2 + 1 + 1) = 2
R2 = 8 - (2 + 1 + 1 + 2 + 1) = 1
R3 = 5 - (1 + 1 + 3) = 0

&esmp;系统中有R类资源m个，现有n个进程互斥使用。若每个进程对R资源的最大需求为w，那么当m、n、w分别取下表中的值时，对于表中的1~6种情况，（C）可能会发生死锁。若将这些情况的m分别加上（D），则系统不会发生死锁。

(1)
A. 1 2 5
B. 3 4 5
C. 2 4 5
D. 2 4 6

(2)
A. 1、1和1
B. 1、1和2
C. 1、1和3
D. 1、2和1

3.9 任务调度

任务调度需要解决的问题：

WHEN：何时分配CPU
- 任务调度的时机，5种情形
HOW：如何分配CPU
- 任务调度方式，不可抢占，可抢占
WHAT：按什么原则分配CPU
- 任务调度算法，先来服务、短作业优先、时间片轮转调度、优先算法
- 调度算法的性能指标

第一要解决的个问题

任务调度的时机，一般来说有5种情形，可能会发生任务的调度。

不可抢占调度方式（Non-Preemptive）：

如果一个任务被调度程序选中，就会一直运行下去；
知道它因为某种原因（如I/O操作或任务间的同步）被阻塞了，或者它主动地交出了CPU的使用权。
调度时机中的前3种情况（任务创建、任务运行结束、任务被阻塞），都可能会发生调度。第4、5种情况（即发生中断），不会发生调度。

可抢占调度方式（Preemptive）：

当一个任务正在运行的时候，调度程序可以去打断它，并安排其他的任务去运行。
调度时机中的所有5种情况，都可能会发生调度。

实时操作系统大都采用可抢占调度方式。

使关键任务能够打断非关键任务的执行，确保关键任务的截止时间能够得到满足。

3.9.1 例题

任务调度是嵌入式操作系统的一个重要功能，嵌入式操作系统内核一般分为非抢占式和抢占式，以下叙述中，不正确的是（D）

A. 非抢占式内核要求每个任务要有自我放弃CPU的所有权。
B. 非抢占式内核的任务级响应时间取决于最长的任务执行时间。
C. 在抢占式内核中，最高优先级任务何时执行是可知的。
D. 抢占式内核中，应用程序可以直接使用不可重入函数。

可重入函数 ：可以被中断的函数，可返回继续执行。
不可重入函数 ：不能被中断的函数，返回执行可能导致结果出错，比如含有全局变量的函数。

3.9.2 调度算法性能指标

如何来评价一个调度算法的好坏。

调度算法的性能指标：

CPU的使用率（CPU utilization）
响应时间（responsive time）：调度器为一个就绪任务进行上下文切换时所需的时间，以及任务在就绪队列中的等待时间。
周转时间：一个任务从提交到完成所经历的时间。
调度开销：调度器在做出调度决策时所需的时间和空间开销。
公平性：大致相当的两个任务所得的CPU时间应该大致相同。要防止饥饿，即一个任务始终得不到处理器去运行。
均衡器：尽可能使整个系统的各个部分（CPU、I/O）都忙起来，提高系统资源的使用效率。
吞吐量：单位时间内完成的任务量。

这些性能指标之间具有一定的冲突性。

比如可通过让更多的任务处于就绪状态来提高CPU的使用率，但这显然会降低系统的响应时间。
调度程序的设计需要优先考虑最重要的需求，然后在各种因素之间进行折中处理。

3.9.3 任务的调度算法

3.9.3.1 先来先服务算法

先来先服务算法（First Come First Served，FCFS）：也叫先进先出算法（First In First Out，FIFO）按照任务到达的先后次序进行调度，是不可抢占的调度方式。

若当前任务占用CPU在运行，一直等到它执行完或被阻塞，才释放CPU。
被阻塞的任务，唤醒后，放在就绪队列的末尾，重新开始排队。

先来先服务算法特点：

简单，易于理解，易于实现。
一批任务的平均周转时间取决于各个任务到达的顺序，如果短任务位于长任务之后，将增大平均周转时间。
例如：假设有三个任务A、B、C，它们的实际时间分别是24、3、3分钟。

3.9.3.2 短作业优先算法

短作业优先算法（Shortest Job First，SJF）：各个任务开始执行之前，事先预计好它的执行时间，从中选择用时较短的任务优先执行。
短作业优先算法有2种实现方案：

不可抢占方式：任务正在运行时，即使来了一个更短的任务，也不会被打断，只有当它运行完毕或被阻塞时，才会让出CPU，进行新的调度。
可抢占方式：如果一个新的短任务到了，且它的运行时间要小于当前正在运行的任务剩余时间，则新任务才会抢占CPU去运行。也称为最短剩余时间优先算法（Shortest Remainning Time First，SRTF）。

3.9.3.3 例题

现有3个同时到达的作业J1、J2和J3，它们的执行时间分别是T1、T2和T3，且T1 < T2 < T3。系统按单道方式运行且采用短作业优先算法，则平均周转周期是（3）

A、T1 + T2 + T3
B、(T1 + T2 + T3) / 3
C、(3T1 + 2T2 + T3) / 3
D、(T1 + 2T2 + 3T3) / 3

3.9.3.4 时间片轮转调度

时间片轮转调度（round-robin scheduling RR）算法：

所有的就绪任务按照先来先服务的原则排成一个队列。
在每次调度的时候，把处理器分派给队列当中的第一个任务，让它去执行一小段时间（时间片）。在这个时间段里任务被阻塞或结束，或者任务的时间片用完了，它会被送到就绪队列的末尾，然后调度器再执行当前队列的第一个任务。

时间片轮转调度（round-robin scheduling RR）算法的优点：

公平性：各个就绪任务平均地分配使用CPU的时间。
活动性：每个就绪任务都能一直保持着活动性。

采用时间片轮转调度算法时，任务的时间片大小要适当选择。
时间片大小的选择会影响系统的性能和效率。

时间片太大，时间片轮转调度就没有意义；
时间片太小，任务切换过于频繁，处理器开销大，真正用于运行应用程序的时间将会减小。

时间片轮转法有一个默认前提，即位于就绪队列中的各个任务是同等重要的。

任务按照先来后到的顺序排成一个队列。
大家轮流执行相同长度的时间片。

3.9.3.5 优先级算法

给每个任务都设置一个优先级。
在任务调度的时候，在所有处于就绪状态的任务中选择优先级最高的那个任务去运行。

优先级算法分为：可抢占式和不可抢占式。

可抢占式：当一个任务正在运行，一个优先级更高的新任务进入就绪状态，会立即抢占CPU运行新任务。
不可抢占式：当一个任务正在运行，一个优先级更高的新任务进入就绪状态，等当前任务执行完再决定。

可抢占优先级调度算法的任务运行情况：

任务1被具有更高优先级的任务2所抢占，然后任务2又被任务3抢占。
当任务3完成运行后，任务2继续执行。
当任务2完成运行后，任务1才又得以继续执行。

任务优先级的确定方式。

静态方式。
动态方式。

静态优先级方式。

在创建任务的时候就确定任务的优先级，且一直保持不变直到任务结束。
缺点：高优先级的任务会一直占用着CPU运行，低优先级的任务可能会长时间地得不到CPU，一直处于“饥饿”状态。

动态优先级方式

在创建任务的时候确定任务的优先级，但该优先级可以在任务的运行过程中动态改变，以获得更好的调度性能。

在优先级算法中，把任务按照不同的优先级进行分组，不同组的任务之间使用优先级算法，同一组的各任务之间使用时间片轮转法。

3.9.3.6 优先级反转

采用优先级调度算法还有一个问题是可能会发生优先级反转（Priority inversion），出现任务“饥饿”现象。

理想情况下。

高优先级任务就绪后，能够立刻抢占低优先级任务而得到执行。

实际系统中。

但在有多个任务需要使用共享资源的情况下，可能会出现高优先级任务被低优先级任务阻塞，并等待低优先级任务执行的现象。

优先级反转（Priority inversion）：高优先级任务需要等待低优先级任务释放资源，而低优先级任务又正在等待中等优先级任务的现象。

3.9.3.7 例题

某系统中采用固定优先级调度，有3个任务，优先级顺序为x > y > z，任务z先执行，并且运行过程中独占了共享资源S，在释放s之前，任务x和y开始运行，x也申请资源s，y和z之间没有共享资源，则三个任务执行完成的顺序是（B）。

A. x、y、z
B. y、x、z
C. y、z、x
D. z、x、y

会导致进程从执行态变为就绪态的事件是（D）

A. 执行P（wait）操作
B. 申请内存失败
C. 启动I/O设备
D. 被高优先级进程抢占

3.10 分区存储

分区方法	单一连续分配	固定分区分配	可变分区分配
分区类型	静态分配法	静态分配法	动态分配法
特点	不分区，所有用户空间给某个进程或作业	分成大小不等的区域，区域分完后固定不变	分成大小不等的区域，根据用户要求动态分配