4.2 操作系统原理

本部分内容主要包括进程、信号量与P、V操作（并发控制）、实存管理、虚存管理（包括段页式寻址）、死锁、设备与文件管理、作业调度等方面的知识点。

1.进程的基本概念

知识点说明：

难度系数：☆☆　考查频度：☆☆　考查权重：☆☆

对于本知识点的考查，关键在于进程的各种概念与特性，主要是记忆型题目。

知识点详解：

进程是一个程序关于某个数据集的一次运行。通俗地说，当打开两个“记事本”时，“记事本”程序还是一个，但创建了两个互不相关的进程。也就是说，进程是运行中的程序，它具有 动态性 和 并发性 ，同时也是系统资源分配、调度和管理的最小单位（注：现代操作系统中还引入了线程——轻量级进程，它是 处理器分配 的最小单位）。

进程最基本的状态有3种：运行、就绪、阻塞（注：现代操作系统还引入了挂起状态）。记住它们并不难，许多考生容易产生理解偏差。其实判断其状态很简单。

· 运行态：就是占用了CPU的时候，表示正在运行。

· 就绪态：万事俱备，只欠CPU资源这一“东风”。

· 阻塞态：进入阻塞态通常是因为在等待I/O完成或等待分配到所需资源。

在操作系统中，通常使用 进程控制块（PCB ） 来标记进程，因此从某种意义上说，进程是由进程控制块、程序和数据构成的。

理解了这个基本的概念之后，更重要的是在此基础上灵活的应用。例如，在一个单CPU的计算机系统中，采用抢占式优先级的进程调度方案，且所有任务可以并行使用I/O设备。现有3个任务T1、T2和T3，其优先级分别为高、中、高，每个任务都需要先占用CPU10ms，然后再使用I/O设备13ms，最后还需再占用CPU5ms。如果操作系统的开销忽略不计，这三个任务从开始到全部结束的总时间是多少ms？其中，CPU的空闲时间共有多少ms？对于这种问题，我们可以通过绘制进程执行状态图来解答，如图4-2所示。

在第1个10ms时间片中，3个进程中T1的优先级最高，因此执行T1，其他两个进程均处于就绪态。进入第2个10ms时间片时，T1开始使用I/O，因此CPU空闲可分配，显然执行T2，因此T3仍然处于就绪态。第3个10ms时间片比较复杂一些，前3ms中T1仍然在使用I/O，而T2也开始使用I/O设备（题意说明可并行使用），因此CPU将分配给T3；然后接下来5ms中，T1需要使用CPU，它将抢占T3的CPU资源，T3进入就绪态；最后3ms中，T1已经处理完毕，而T2仍然在处理I/O，因此CPU可以分配给T3。在第4个10ms时间片中，除了中间5ms中CPU资源会被T2所抢占，其他的都可以交由T3使用，这样在这个时间片中将完成T2进程的处理，而且T3进程也将完成第一次CPU占用，开始处理I/O设备。

通过上述的分析不难得出，总共需要花的时间是58ms，而只有T3在处理I/O设备时CPU才是空闲的，共13ms。

2.信号量与P、V操作

知识点说明：

难度系数：☆☆☆☆　考查频度：☆　考查权重：☆

对于本知识点的考查，重点在于理解信号量与P、V操作的基本概念，能够正确地理解在互斥、同步方面的控制应用，并能够灵活地运用，相对来说是个难点，不过对于网络工程师考试而言出现的频度很低。

知识点详解：

在操作系统中，进程之间经常会存在 互斥 （都需要共享独占性资源时）和 同步 （完成异步的两个进程的协作）两种关系。为了有效地处理这两种情况，W·Dijkstra在1965年提出信号量和P、V操作的概念。

· 信号量：是一种特殊的变量，表现形式是一个 整型S 和一个 队列 。

· P操作：也称为down（）、wait（）操作，使S=S-1，若S<0，进程暂停执行，放入信号量的等待队列；

· V操作：也称为up（）、signal（）操作，使S=S+1，若S≤0，唤醒等待队列中的一个进程。

（1）完成互斥控制。

也就是保护共享资源，不让多个进程同时访问这个共享资源，换句话说，就是阻止多个进程同时进入访问这些资源的代码段，这个代码段称为 临界区（也称为管程） ，而这种一次仅允许一个进程访问的资源称为 临界资源 。对于临界区的代码就是：

P（信号量）

临界区

V（信号量）

由于只允许一个进程进入，因此信号量中整型值的初始值应该为1。该值表示可以允许多少个进程进入。当该值<0时，其绝对值就是等待使用的进程数，也就是等待队列中的进程数。而当一个进程从临界区出来时，就会将整型值加1，如果等待队列中还有进程，则调入一个新的进程进入（唤醒）。

（2）完成同步控制。

最简单的同步形式是：进程A在另一个进程B到达L2以前，不应前进到超过点L1，这样就可以使用程序：

因此要确保进程B执行V操作之前，不让进程A的运行超过L1，信号量的初始值就应该为0。这样，如果进程A先执行到L1，那么执行P操作后，信号量的整型值就会小于1，也就停止执行。直到进程B执行到L2时，将信号量的整型值减1，并唤醒它以继续执行。

（3）生产者—消费者问题。

生产者—消费者是一个经典的问题，它不仅要解决生产者进程与消费者进程的同步关系，还要处理缓冲区的互斥关系，因此通常需要3个信号量来实现。其中，两个用来管理同步：empty信号量（说明空闲的缓冲区数量，最早没有产生东西，因此其初始值应为缓冲区的最大数）和full信号量（说明已填充的缓冲区数量，其初始值应为0）。另一个mutex信号量用来管理互斥，以保证同时只有一个进程在写缓冲区（因此其初始值应为1，参见“互斥控制的实现”）。

注：如果对缓冲区的读写无须进行互斥控制的话，那么就可以省去mutex信号量。

（4）阅读者和写入者问题。

假设有一个数据集被多个并行进程共享，其中有些进程只是读这个数据集，而有些进程则需要修改这个数据集的内容。这里存在着一个什么样的并发关系呢？阅读者相互不影响，但写入者则是互斥访问的。因此，解决这个问题的最简单的方法是：当没有写入者在访问共享数据集时，阅读者可以进入访问，否则必须等待。下面则是一个读者优先的解法（其中信号量access用来控制写入互斥；而信号量rc则用来控制rc（读者统计值）的互斥访问。

（5）理解P、V操作。

信号量与P、V操作的概念比较抽象，在历年的考试中总是难倒许多考生，其实主要还是没有能够正确地理解信号量的含义。

· 信号量与P、V操作是用来解决并发问题的，而在并发问题中最重要的是 互斥 与 同步 两个关系，也就是说，只要有这两个关系存在，信号量就有用武之地。因此，在解题时，应该先从寻找互斥与同步关系开始。这个过程可以套用简单互斥、简单同步、生产者—消费者、阅读者—写入者问题。

· 一般来说，一个互斥或一个同步关系可以使用一个信号量来解决，但要注意经常会忽略一些隐藏的同步关系。例如，在生产者—消费者问题中，就有两个同步关系，一是判断是否还有足够的空间给生产者存放产物，另一个是判断是否有足够的内容让消费者使用。

· 信号量的初始值通常表示资源的可用数。而且对于初始值为0的信号量，通常会先做V操作。

· 在资源使用之前，将会使用P操作；在资源用完之后，将会使用V操作。在互斥关系中，P、V操作是在一个进程中成对出现的；而在同步关系中，P、V操作则一定是在两个进程甚至多个进程中成对出现的。

另外，值得一提的是，操作系统还提供了一些高级通信原语，如Write/Read，Send/Receive可以实现相同的功能，它们能够更好地补充P、V操作的不足，完成更多的功能。

3.死锁

知识点说明：

难度系数：☆☆☆　考查频度：☆　考查权重：☆

对于本知识点，应该了解死锁的原理与防范措施，重点在于灵活地应用。

知识点详解：

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

（1）死锁发生的必要条件。

· 互斥条件：即一个资源每次只能被一个进程使用。在操作系统中这是真实存在的情况。

· 保持和等待条件：有一个进程获得了一些资源，但因正在请求其他资源而被阻塞。

· 不剥夺条件：就是系统不是抢占式的，进程已获得的资源在未使用完之前，不能剥夺，只能在使用完后由自己释放。

· 环路等待条件：若干个进程形成环型链，每个都占用对方要申请的下一个资源。

对于这些内容，关键在于融会贯通地理解与应用。为了帮助考生更好地理解，下面我们看一个例子。假设系统中有三类互斥资源R1、R2、R3，可用资源数分别是9、8、5。在T0时刻系统中有P1、P2、P3、P4和P55个进程，这些进程对资源的最大需求量和已分配资源数如表4-1所示。

进程按P1→P2→P4→P5→P3序列执行，系统状态安全吗？如果按P2→P4→P5→P1→P3序列呢？

我们先看一下，这时未分配的资源还有哪些。很明显，还有2个R1，1个R2。

因此，当按P1→P2→P4→P5→P3的顺序执行时，首先执行P1。这时由于其R1，R2、R3的资源数都未分配够，因而开始申请资源，得到还未分配的2个R1，1个R2。但其资源仍不足，从而进入阻塞状态，并且这时所有资源都已经分配完。所以后续的进程都无法得到能够完成任务的资源，全部进入阻塞，形成死循环——死锁发生。

而当按P2→P4→P5→P1→P3的序列执行时：

· 首先执行P2，它还差一个R2资源，刚才系统中还有1个未分配的R2，因此满足其要求，就能够顺利结束进程，释放出2个R1，2个R2，1个R3。这时，未分配的资源就是4个R1，2个R2，1个R3。

· 然后执行P4，它还差一个R3，而系统中刚好有一个未分配的R3，由于满足其要求，因此也能够顺利结束，并释放出其资源。因此，这时系统就有5个R1，4个R2，1个R3，……

根据这样的方式推下去，就会发现按这个序列可以顺序地完成所有的进程，而不会出现死锁现象。从这个例子中，大家可以体会出死锁的4个条件是如何起作用的。

（2）解决死锁的策略。

· 死锁预防：“解铃还需系铃人”，随便破坏导致死锁的任一必要条件就可以预防死锁。例如，要求用户申请资源时一起申请所需的全部资源，这就 破坏了保持和等待条件 ；将资源分层，得到上一层资源后，才能够申请下一层资源，它 破坏了环路等待条件 。预防通常会降低系统的效率。

· 死锁避免：避免是指进程在每次申请资源时判断这些操作是否安全，典型算法是 “银行家算法” 。但这种算法会增加系统的开销。

· 死锁检测：前两者是事前措施，而死锁检测则是判断系统是否处于死锁状态，如果是，则执行死锁解除策略。

· 死锁解除：这是与死锁检测结合使用的，它的使用方式就是剥夺，即将资源强行分配给别的进程。

4.实存管理

知识点说明：

难度系数：☆　考查频度：☆　考查权重：☆

对于本知识点，重点是了解3种存储空间分配方法和4种分配算法。

知识点详解：

存储管理的任务是存储空间的分配与回收。在现代操作系统中通常有单一连续分配、固定分区分配、可变分区分配3种分配方法，如表4-2所示。

相对较常用的是“可变分区分配”，当一个作业完成时，使用这种方法就会检测它释放出来的内存空间是否有相邻的未分配部分（自由区），如果有，就会自动 合并自由区 。而如果作业申请大于所有的自由区，但自由区的总和大于新作业所需的存储区，这时就会进行移动合并，形成更大的存储自由区，这就称为 存储拼接 。在可变分区分配方式中，当有新作业申请分配内存时，所采用的存储分配算法有以下4种。

· 最佳适应法：选择等于或最接近于作业需求的内存自由区进行分配。这种方法可以减少碎片，但同时也可能带来更多小得无法再用的碎片。

· 首次适应法：从主存低地址开始，寻找第一个可用（即大于等于作业需求的内存）的自由区。这种方法可实现快速分配，缩短查找时间。

· 最差适应法：选择整个主存中最大的内存自由区。

· 循环首次适应算法：是首次适应法的一个变种，也就是不再每次都从头开始匹配，而是连续向下匹配。

5.虚存管理

知识点说明：

难度系数：☆☆　考查频度：☆☆　考查权重：☆☆☆

对于本知识点，应该了解虚存的概念、页面调度算法，重点在于掌握段页式管理、工作集。

知识点详解：

由于内存的大小总是有限的，因此如果都采用“实存管理”，那么大于总物理内存的作业就无法运行。为了解决这个问题，可行的方法就是用外存来换取内存，这就是虚拟存储系统。它通过将运行进程访问的地址（逻辑地址， 虚拟地址 ）与主存的物理地址（ 实地址 ）分开，使提供大于物理地址的逻辑地址空间成为可能。而建立虚拟地址和实地址之间的对应关系、实现转换的工作就称为“虚存管理”。

（1）虚存组织：常见的有分段技术、分页技术、段页式技术3种，如表4-3所示。

在现行的虚存组织方面，最常见的就是段页式管理。在进行虚实地址转换时，可以采用的公式是：

注： n 的值为 d 的总位数，（ x ）表示 x 内的内容。

（2）虚存管理：在虚存的管理中涉及载入（调入）、放置（放入分区）和交换（swapping）等问题。

· 调入策略：即何时将一页或一段从外存中调入主存。通常有两种：一为 请求调入法 ，即需要使用时才调入；二为 先行调入法 ，即将预计要使用的页/段先行调入主存。

· 放置策略：也就是调入后放在主存的什么位置，这与实存管理基本上是 一致 的。

· 置换策略：由于实际主存是小于虚存的，因此就可能会发现内存中已满，但需要使用的页不在主存中。这时就需要进行置换，即将一些主存中的页淘汰到外存，腾出空间给要使用的页，这个过程也称为Swapping。它的工作原理与Cache调入相类似。

最优算法（OPT）：淘汰不用的或最远的将来才用的页。这是一种理想算法，不可能实现，只是用来作为衡量算法效率的参照物。

随机算法（RAND）：随机淘汰。这种算法开销小，但性能不稳定。

先进先出算法（FIFO）：选择最早调入（也是驻留时间最长）的页。

最近最少使用算法（LRU）：选择离当前时刻最近的一段时间内使用得最少的页。

（3）工作集。

存储管理策略的基础是 局部性 原理。具体来说体现在时间局部性（指最近访问的，将来不久可能还要访问）和空间局部性（就是存储访问有成组的倾向）。根据这样的特性，Denning提出了优化性能的工作集理论。

工作集 是进程频繁访问的页面集合。从性能角度出发，该工作集应该都驻留在内存中，否则就会产生过度的页面调度活动，这又称为 “颠簸”（抖动） 。划分工作集可以按定长时间或定长页面两种方法进行。当颠簸现象发生时，说明系统负荷过大，通常采用处理器均衡调度，淘汰低优先级进程；另一种是控制缺页率，当缺页率达到上限时，增加内存分配量，达到下限时，就减少内存分配量。

6.设备与文件管理

知识点说明：

难度系数：☆　考查频度：☆☆　考查权重：☆☆

对于本知识点，需要了解设备的分类、文件的逻辑、物理结构，以及文件存储设备的管理，考查内容主要是记忆性。

知识点详解：

在计算机系统中，除CPU与主存之外，都称为设备。根据数据的组成方式，不同的设备可以分为 字符设备 （慢速设备）和 块设备 （快速设备）；根据资源性质，可以分成 独占设备 （终端、打印机）、 共享设备 （磁盘）和 虚拟设备 （如用磁盘等高速设备虚拟化为多个“高速”的打印等低速设备，该技术也称为 spooling技术 ）。其他知识点参见第3章中的“输入/输出系统”。

计算机系统中的另一类资源是软资源，包括各种系统程序、实用程序、各种应用领域的程序，以及大量的文档材料，这些东西在操作系统中是以 文件 的形式存储的。与文件相关的概念包括：数据项——数据的基本单位、记录——相关数据项的集合、文件——记录的集合。文件的组织形式称为 组织结构 ，用户可见的称为 逻辑结构 ，在外存中存放的方式称为 物理结构 。

· 逻辑结构（如表4-4所示）。

· 物理结构（如表4-5所示）。

· 文件存储设备管理（如表4-6所示）：有效地管理空闲块。

· 文件控制块（FCB）：是存放管理文件所必需的控制信息的数据结构。主要包括：基本信息（文件名、类型、组织）、保护信息（口令、所有者、期限、访问权限）、位置信息（存储位置、文件长度）、使用信息（时间、最后使用者）。

另外，关于文件的使用、目录结构等都属于较常见的概念，在此就不再详细说明。值得一提的是“ 文件链接 ”，Windows操作系统中的例子就是“快捷方式”，UNIX系统的实现也与之类似。它只是在当前目录下创建了一个文件项，但没有复制真正的内容，而且当原文件改变时，链接文件也会改变，这是与文件副本的最大区别。

7.作业调度

知识点说明：

难度系数：☆　考查频度：☆　考查权重：☆

对于本知识点，主要需要理解作业的概念，了解作业的完成时间的计算方法。

知识点详解：

作业是系统为完成一个用户的计算任务所做的工作总和。在操作系统进行作业调度时要实现的目标包括 响应时间快 （分时、实时系统的要求）、 周转时间或加权周转时间短 （批处理系统的要求，周转时间是作业从提交到完成的时间和；加权周转时间是指作业的周转时间与作业运行时间之比）、 利用率均衡 、 吞吐量大 、 系统反应时间 （从作业提交到获得首次服务时间） 短 。

调度算法包括 先来先服务（FCFS ） ，这种算法根据作业到达的时间顺序对作业进行调度，不利于短作业； 短作业优先（SJF ） ，估计运行时间最短的作业优先，不利于长作业； 响应比高者优先（HRN ） ，使用公式“（估计运行时间+等待时间）/估计运行时间”来计算谁优先； 优先级调度， 即根据预设的优先级进行调度。 eHaEQECdA28XfAo7z+Er2qhtjnLIp0CoXaPBgcpd+bBd9WtMx0vPJIvVwcAUVOlh