158被浏览6,857分享邀请回答3015 条评论分享收藏感谢收起31 条评论分享收藏感谢收起当前位置： >>
第2章 处理器管理及并发进程
第2章 处理器管理及并发进程1本章学习任务进程与线程 进程调度 进程互斥与同步 管程 进程通信 死锁22.1.1 程序的顺序执行? 示意图I1 P1 O1 I2 P2 O2 I3 P3 O3? 特点简单、方便，容易理解； 确定性； 封闭性； 可再现性。3?顺序程序设计的四个特点，使得编程和调试 很方便，缺点就是计算机资源使用效率不高。我 们知道，操作系统是管理和控制计算机系统资源 并方便用户使用的一种最重要的系统软件，提高 资源的使用效率是操作系统设计的主要目标之一。 因此，必须要提出一种程序的执行方式，提高系 统的效率，这就是程序的并发执行。42.1.2 程序的并发执行? 并发（Concurrency）：一个程序的执行还没有 结束，另一个程序就已经开始。因此，从某个宏 观时间段来考察，在这段时间内，“同时”完成 了几个程序，这就叫并发，但从微观某个时刻来 看，任何时刻却只有一个程序在运行。 ? 并发性有两层含义： ①内部顺序性，对于一个程序而言，它的所有指 令是按序执行的； ②外部的并发性，对于多个程序而言，它们是交 叉运行的。5? 并行（Parallel）：若干个程序在微观上也是同时 执行的，当然，对于程序的并行执行，需要多个 处理器。 ? 本书中，主要讨论单CPU的情况，因此，程序的 执行是并发执行。 ? 现代计算机系统由于采用了通道等技术，使得处 理器与外围设备能够并行工作。6? 并发执行示意图I1 P1 O1I2P2O2I3P3O3? 并发执行的特点 程序运行“走走停停，停停走走”；由于在并发 环境下，各个程序不再独立，破坏了顺序程序的 确定性、封闭性和可再现性。72.1.3 多道程序设计? 主存中每次只存在一个程序，该程序运行时独占 整个计算机系统资源，这种程序设计方式就是 “单道程序设计”，而让多个程序同时进入一个 计算机系统的主存储器并发执行，这种程序设计 方式就是“多道程序设计”。 ? 具有多道程序设计能力的计算机系统称为多道程 序设计系统。 ? 采用多道程序设计的好处是：充分发挥了计算机 硬件的并行性，消除了处理器和外围设备的互相 等待现象，大大提高了系统的效率。8? 从总体上看，采用多道程序设计技术可以增加单 位时间内执行的作业数，但是，对于某一个作业 而言，它的执行时间可能会延长。? 【例2-1】在一个单处理器的系统中，假设有两道 作业，一道单纯计算11分钟，另一道先计算3分 钟，再打印6分钟。请问在单道程序设计系统中， 两道作业的执行总时间至少为多少分钟？而在多 道程序设计系统中，这一时间又至少为多少分钟？9? 解答：在单道系统中，两道作业必须顺序运行， 因此执行的总时间是11+（3+6）=20（分钟）。 而在多道程序设计系统中，可以让第二道作业先 进行执行，计算3分钟后，进行打印，接下去第一 道作业进行计算，这时处理器和打印机真正并行 工作，因此，这时，两道作业的执行总时间是 3+11=14（分钟）。10? 【例2-2】在一个单处理器的多道程序设计系统中， 现在有两道作业将要同时执行，一道作业以计算为主， 一道作业以I/O操作（输入输出）为主，请问，先调 度哪个作业进程？为什么？ ? 解答：在现代计算机系统中，处理器可以和外部设备 真正并行工作。因此，本题中，应该先调度I/O型的 作业进程，赋予I/O型的作业进程更高的优先级，这 样做的好处是可以提高系统资源的使用效率。这是因 为，将I/O型的作业进程先调度运行，利用CPU进行 运算，完成后让出CPU处理器，进行输入输出处理， 而此时可以调度计算型作业进程到处理器上运行，这 样做到CPU与外部设备并行工作，提高了资源利用率。 例2-1用到了这一思想。11? 【例2-3】有一台计算机，配置有1MB主存，操作系统占 用200KB，每个用户进程各占用200KB，如果用户进程等 待I/O的时间为70%，若增加1MB主存，则CPU的利用率提 高多少？再增加1MB主存，则CPU的利用率比只有1MB主 存时又提高多少？ ? 解答：当只有1MB主存时，除了操作系统占用的200KB， 则其余的800KB主存可以容纳4个用户进程。由于每个进 程等待I/O的时间为70%，那么只有四个进程都同时等待时， CPU 才 是 空 闲 的 ， 那 么 CPU 的 利 用 率 是 1 － （ 0.7 ） 4= 0.7599 ≈ 0.76；假如再增加1MB主存，则主存中的用户进 程共4+5=9个，CPU的利用率是１－（0.7） 9 ≈ 0.9596 ≈ 0.96 ， 那 么 CPU 的 利 用 率 提 高 了 （ 0.96 － 0.76 ） /0.76×100% ≈ 26%。若再增加1MB主存，则CPU的利用率 是1－（0.7） 14 ≈ 0.99，CPU的利用率又提高了（0.99－ 0.76）／0.76×100% ≈ 30%。122.1.4 并发程序执行的条件? 具有何种特性的两个程序并发执行呢？关于这个问题， Bernstein作过研究，并于1966年提出了两个程序并发执行的条 件，故又称之为Bernstein条件，即并发进程如果是无关的，则 这些进程可以并发执行。并发进程的无关性是指它们分别在不 同的变量集合上运行。下面对Bernstein条件做简单介绍。 ? 约 定 程 序 Pi 在 执 行 期 间 所 需 引 用 的 变 量 的 集 合 ， 记 作 R(Pi)={a1,a2,a3,…,an}，实际上，R(Pi)就是Pi的读集。 ? 约 定 程 序 Pi 在 执 行 期 间 所 需 修 改 的 变 量 的 集 合 ， 记 作 W(Pi)={b1,b2,b3,…,bm}，实际上，W(Pi)就是Pi的写集。 ? 有了以上的约定，Bernstein条件就可以表述为：如果两个程序 P1和P2满足R(P1)∩W(P2)∪R(P2) ∩W(P1) ∪W(P1) ∩W(P2)={}， 它们就能够并发执行，否则不能并发执行，会发生与时间有关 的错误。13? 【例2-4】对于下列四条语句，将它们的读集和写集都写出来。 解答： 语句 读集R(si) 写集W(si) s1: a=x*y; R(s1)={x,y} W(s1)={a} s2: b=z-1; R(s2)={z} W(s2)={b} s3: c=b+a+8; R(s3)={a,b} W(s3)={c} s4: w=c+5; R(s2)={c} W(s2)={w} 运用Bernstein条件，有： R(s1) ∩W(s2) ∪R(s2) ∩W(s1) ∪W(s1) ∩ W(s2)= {}，因此，语句s1和 s2可以并发执行； R(s1) ∩W(s3) ∪R(s3) ∩W(s1) ∪W(s1) ∩ W(s3)= {a}≠{}，因此语句s1 和s3不能并发执行。 同理语句s2和s3，s3和s4也不能并发执行。14? 值得注意的是，Bernstein条件是一个理论上保证 程序能够并发执行的充分条件。在操作系统中， 由于进程间共享某些资源而不满足Bernstein条件 的情况十分普遍，从理论上讲，它们是不能够并 发执行的，否则会发生与时间有关的错误。但是， 只要采取适当的措施，这些进程就可以正确、安 全地并发执行，这可以通过信号量和PV操作或者 管程机制等来予以解决。这些是涉及到进程互斥 和同步部分的内容，本章后面会详细介绍。152.2 进程? ? ? ? 2.2.1 进程的定义及其属性 2.2.2 进程的状态及其转换 2.2.3 进程控制块 2.2.4 进程队列162.2.1 进程的定义及其属性? 进程是操作系统中最基础也是最重要的 概念? 我们采用进程定义如下： 进程是并发环境下，一个具有独立功能的 程序在某个数据集上的一次执行活动，它 是操作系统进行资源分配和保护的基本单 位，也是执行的单位。17? 进程不是程序，而是程序的一次执行活动， 和传统的程序概念有着本质的区别。在日 常生活中，很容易找到类似于“程序”和 “进程”的例子，例如厨师炒菜，菜谱相 当于程序，一次炒菜过程就是一个“进 程”；再如乐谱和演奏，乐谱相当于程序， 而一次演奏就相当于一个进程；此外，火 车时刻表以及列车的运行，课程表和上课， 都有类似关系。18? 从进程的定义中，可以看出进程具有以下六个属性。 (1)动态性：进程是程序的一次执行活动，执行轨迹是“走走停停， 停停走走”，并且进程具有创建、运行到终止的生命历程。因 此，动态性是进程的一个重要属性．而程序是静态的，没有生 命周期，程序作为一种系统资源（文件形式）可以长久存在。 程序和进程的本质区别就是：程序是静态的，进程是动态的。 (2)结构性：进程不仅包括了运行于其上的程序，还包括了某个数 据集合。为了在操作系统内部实现进程，就需要一个数表结构， 即进程控制块来记录和描述进程的动态运行情况。因此，一个 进程都是有程序代码段、数据块和进程控制块三部分组成。 (3)独立性：在传统的操作系统中，进程既是资源的分配和保护的 基本单位，也是处理器调度的基本单位。在具有并发活动的系 统中，没有建立进程的程序，是不能够作为独立单位进行运行 的。在现代操作系统中，具有多进程多线程能力，进程仍然作 为资源的分配和保护的独立单位，而调度和执行的基本单位改 为由线程来完成。19? (4).并发性：并发性是进程的固有特性，引入进程的目的 之一就是让进程能够并发执行。并发性也是现代操作系统 的一个重要属性。并发就是指一个进程运行没有结束，另 一个进程就已经开始，各个进程运行在时间上可以有重叠。 ? (5)制约性：并发进程由于共享资源和相互协作，从而产生 制约关系，使得进程在关键点上需要相互等待或互相通信， 采取一些必要的措施，才能保证进程执行的结果的确定性、 唯一性和可再现性。 ? (6)共享性：同一个程序的各个进程对应的程序代码是相同 的，此外，不同进程之间还可以共享公共变量，以竞争或 协作的方式进行工作。20? 下面对程序和进程的联系作个简单介绍。从进 程的结构特性可以看出，进程包含程序，但进 程和程序并非一一对应，一个程序可以对应多 个进程（数据集不同），而同样，有的进程对 应一个程序，而有的程序可被属于不同的进程 的几个程序进行调用，每次调用就对数据进行 一次处理，而这个处理过程只是相应进程的一 部分。212.2.2 进程的状态及其转换? 进程具有并发性、制约性、动态性、结构 性以及独立性，运行轨迹是“走走停停， 停停走走”，有时在占用处理器，有时又 在申请外部设备，有时又在进行I/O处理。 为了刻画每个进程活动的过程和状态的变 化，以及为了进程控制和调度的方便，就 要记录和控制进程的运行过程，这就是进 程的状态。22? 为了管理上的方便，大多数系统中进程都具有以下三种基 本的状态。 (1)运行态（Running）：此时的进程获得了当时运行所需的 系统资源，并且正在占有CPU进行处理。 (2)等待态（Waiting），也叫阻塞态（Blocked）：运行中的 进程，由于要申请使用某个系统资源，或者申请到了某个 外部设备正在进行与外部设备进行数据传输, 或者进程运 行中出现了异常需要等待用户进行干涉处理，这时的进程 就不能继续运行下去，而不得不放弃CPU，从而转入等待 态。 (3)就绪态（Ready）：处于等待态的进程，由于所等待的事 件得到了满足，这时就转入到就绪态。就绪态的进程，运 行所需要的系统资源，除了CPU之外，全部得到了满足， 可是说“万事俱备，只欠CPU”。23? 除了以上三种基本状态之外，进程还具有 以下两种状态： (1)创建态：就是进程被创建的状态。被创建 后的进程处于就绪态。 (2)终止态：就是进程的生命周期结束,进入消 亡状态。一般地，运行态的进程运行完毕 进入终止态。24进程的五种状态及其状态转换图创建态运行态终止态调度 发生等待事件 时间片到就绪态等待事件结束 等待态25? 具有挂起功能的进程状态及其转换 有些操作系统，为了缓解内存资源的 紧张，或者调整系统的负荷或提高性 能，还引入了挂起功能。挂起功能， 就是将进程从内存换到外存，相反地， 从外存调入内存称为激活。 具有挂起功能的进程状态及其转换， 见下页的示意图。26挂起就绪态等待事件结束挂起等待态建立终止态创建态激 活激 活 挂 起调度 运行态挂 起建立落选发生等待事件 活动等待态活动就绪态 等待事件结束 图 2-4 具有挂起功能的进程状态及其转换图27图2-4中的一些状态转换介绍如下：? 新建态→挂起就绪态：新创建的进程，如果当时内存资源 比较紧张，或者系统负荷较重，为了提高系统性能，可以 将该新进程放到外存中，成为挂起就绪态的进程。 ? 活动就绪态→挂起就绪态：根据当前系统的内存使用情况 以及系统性能，可以将活动就绪态的进程对换到外存中， 变为挂起就绪态进程。 ? 挂起就绪态→活动就绪态：当内存比较空闲，或者内存中 没有活动就绪态进程，或者挂起就绪态进程的优先级比活 动就绪态的高，这时操作系统就可以将处于挂起就绪态的 进程调入内存，变为活动就绪态进程。28? 等待态 → 挂起等待态：为了提高系统效率，系统可以根据当时系 统资源使用情况和系统负荷程度，可以将活动等待态的进程对换 出内存成为挂起等待态；还有一种情况是，当系统的内存中没有 活动就绪进程时，CPU空闲，此时，就必须将至少一个处于活动 等待态的进程对换到外存，以腾出空间调进一个挂起就绪态的进 程成为活动就绪态进程。 ? 挂起等待态 → 等待态：在具有挂起功能的系统中，一个处于挂起 等待态的进程，在等待事件的发生，将它调入内存，意义并不大。 但是当内存空间比较空闲，或者可以预知该进程的等待事件很快 就会结束，或者这个进程的优先级较高，为了提高系统效率，可 以将该挂起态的进程调入内存，成为活动等待态进程，当等待事 件结束时，该进程直接转为活动就绪态进程。 ? 挂起等待态 → 挂起就绪态：对于挂起等待态的进程，当它等待的 事件结束时，就转为挂起就绪态。292.2.3 进程控制块? 进程控制块（Process Control Block， PCB），是为了描述和控制进程的运行而 定义的一种数表结构，它是进程存在的唯 一标志，也是进程实体的一部分。操作系 统对进程的管理和控制主要以PCB为依据。 PCB中包括了操作系统所需要的进程运行 的所有信息。30? 虽然不同的操作系统中，PCB的信息有所差异，但大多数 操作系统中的PCB都具有以下四部分信息： (1)标识信息。这是系统内部为进程分配的一个唯一的数值型 编号，又叫进程名或进程号，相当于人的身份证号码。当 创建一个进程时，有的系统允许创建该进程的用户可以为 该进程取一个方便记忆的名字，这个名字叫做进程外部标 识符，而被系统内部使用的进程号叫做进程内部标识符。 (2)描述信息。用来描述进程的一些基本情况，如进程当前所 处的状态，如果是等待态，还要指出等待的原因，该进程 对应的程序代码存放的位置，以及数据存放的位置等等。31（3）现场信息。用来保存进程存放在处理器中的各种信息。进程的状态是不断转换的，例如进程 从运行态到等待态，就需要保护一些必要的信 息，以便进程可以正确地运行。现场信息一般 包括控制寄存器内容，通用寄存器内容，程序 状态字（PSW)寄存器内容，系统堆栈指针，用 户堆栈指针等等。 （4）管理和控制信息。用于管理和调度一个进程。 包括进程优先级，队列指针，CPU资源的占用 和使用的时间，进程间通信信息，进程特权信 息以及资源需求和占有情况等信息。32进程控制块是操作系统中最重要的数据结构， 是进程存在的唯一标志，它为系统提供可并发 执行的独立单位。当系统创建一个进程时，就 为它分配一个PCB，并填上适当信息，并随着 进程的推进，PCB的信息不断调整和修改，以 准确刻画动态的进程的运行轨迹；当一个进程 运行结束时，系统就回收该进程的PCB，从而 该进程消亡。操作系统是根据PCB来实现对并 发环境下的进程管理和控制的，没有建立PCB 的程序是不能并发运行的。332.2.4 进程队列? 在并发环境下，系统中存在着很多进程，有的处于运行态，有的处于 就绪态，有的处于等待态，并且等待的原因可能各不相同。这些进程 是零散的，并且数目很多，可达成百上千个，如果不进行有效管理， 系统效率会大大降低。 ? 由于对进程的访问很多时候是根据进程的状态进行的，例如进程调度 就是只从就绪态的进程中选择一个占有CPU去运行，唤醒原语只是访 问处于等待态的相应进程，因此，如果能够根据其状态将进程组织成 若干个队列，就能大大提高进程的访问效率。这种设想是可行的，因 为PCB是描述进程的最重要的一种数表结构，它标志了进程的存在， 包括了系统控制和管理进程所需的所有信息，并且有一个指针信息， 这样就很容易形成队列。这样，可以把具有相同状态的进程的PCB按 照某种原则链接在一起，形成一种队列，这就是进程队列，实际上， 进程队列是一种PCB链。34? 进程队列根据进程的状态不同，可以有进程就绪队列， 进程等待队列，由于在单CPU环境下，处于运行态的 进程不超过一个，因此，没有必要建立进程运行队列。 更进一步，可以根据进程调度的策略，将就绪队列根 据优先级的不同划分为若干了就绪队列，如有的系统 将就绪队列分为前台就绪队列和后台就绪队列，优先 调度前台就绪队列中的进程，如果前台就绪队列为空， 则从后台就绪队列进行调度;对于等待队列，可以进一 步根据进程等待的原因，划分为多个进程等待队列， 例如如果一个进程要求申请一个设备，而该设备已被 其他进程占用，则该进程就加入到与该设备相关的等 待队列中去，这样，当该设备空闲时，就可以只从该 设备的进程等待队列中唤醒一个进程。35? 进程队列的组织方式可以采用单向链表， 双向链表或表格形式。 ? 单向链表和双向链表的实现方式参见下 页图示。36队首PCB1PCB2 PCB3PCB4 队首 0PCB1PCB2PCB3PCB400(1)单向链表实现的 PCB 链接 (2)双向链表实现的 PCB 的链接 图 2-5 进程队列的两种实现方式37? 有了进程队列，进程的管理和调度，实际上就是进程 控制块的出队和入队过程。例如，进程调度，就是根 据调度策略（算法）从相应的就绪队列中寻找一个进 程，将它变为运行态，并且从就绪队列中删除（出 队），当时间片到时，该进程就会让出处理器，重新 进入就绪队列的末尾（入队），等待下一轮的调度； 处于运行态的进程，如果发生等待事件，就让出处理 器，进入相应设备等待队列（入队），当等待事件结 束时，从相应的等待事件队列出队，然后进入就绪队 列（入队）。 ? 操作系统中的进程队列的管理和状态转换见下页图示。38进程创建 就绪队列 时间片到 处理器进程终止事件 1 结束 I/O 事件 1 等待队列事件 2 结束 I/O 事件 2 等待队列……I/O事件 n 结束 I/O 事件 n 等待队列图 2-6 进程队列及其入队出队示意392.3 进程的控制? 进程控制是操作系统的一项基本功能， 它的主要工作是对进程生命期进行控制， 对进程的控制主要有进程的创建，进程 的阻塞和唤醒，进程的挂起和激活，进 程的终止和撤销以及实现进程之间的状 态转换和进程通信等功能。进程的控制 是在操作系统的内核中采用进程控制原 语进行。402.3.1 操作系统内核? 为了提高操作系统的效率、稳定性和安全性， 将一些靠近硬件部分的和频繁使用的功能模块 都设计在一个软件功能层次中，让这个软件功 能模块常驻内存，这样的一些模块就是操作系 统的内核。 ? 一般操作系统内核中包括以下一些功能，如中 断处理程序，各种常用设备的驱动程序，时钟 管理，进程管理，存储器管理以及一些其他公 用的一些软件模块。41? 在操作系统内核中运行的状态，即核心 态，也称管理态； ? 对应的，不在操作系统核心态运行的状 态是用户态，也称目标态。 ? 中断是操作系统从用户态转入核心态的 唯一手段。42? 只能在核心态下运行的指令称作特权指 令，其他指令为非特权指令。如修改 PSW，开关中断，启停设备等指令是特 权指令，不是特权指令的指令就是非特 权指令，如访管指令，算术与逻辑运算 指令等就是非特权指令。在操作系统的 核心态可以执行所有指令，在用户态只 能执行非特权指令。43? 操作系统的内核是操作系统的核心部分， 是对计算机硬件扩充的最近的一层软件， 是在核心态下运行的操作系统程序。操 作系统的内核对操作系统的性能和安全 具有重要意义。进程的管理和控制是操 作系统内核的一项重要任务。442.3.2 原语? 原语（Primitive）是在操作系统内核中，由若干 条指令构成的，运行在管理态下的完成系统特定 功能的一个过程。进程管理和控制的功能均由操 作系统中的原语来完成。原语的一个重要特性就 是它的执行的原子性，即原语在执行过程中不允 许被中断，它的执行过程是一个不可分割的基本 单位，因此，原语的执行是顺序的，原语不可能 并发执行。在操作系统中通常采用屏蔽中断的方 式来实现原语。操作系统内核中的基本功能一般 都采用原语来实现，如进程的控制以及后面要讲 解的进程的互斥和同步等。45? 原语和系统调用都是使用访管指令实现的， 虽然二者的调用形式相同，但二者的区别 是明显的，原语是在操作系统内核实现的， 而系统调用是由系统进程或系统服务器实 现的；原语在运行中不允许被中断，而系 统调用在执行时可能被中断。462.3.3 进程控制原语? 进程控制原语就是对进程的生命期进行管 理和控制以及对进程状态进行转换的原语， 主要有进程的创建原语，进程的阻塞和唤 醒原语，进程的挂起和激活原语和进程的 撤销原语。47? 进程的创建 进程的创建是进程生命期的开始。创建一个进程 就是要为一个程序建立一个进程控制块并且分配 地址空间。当用户执行了一个交互式的终端作业， 或提交了一个批处理作业，或者操作系统创建了 一个服务进程，或者是一个存在的进程创建了一 个子进程时，就需要进行进程的建立。 下面以一个存在的进程通过进程创建原语建立一 个新的子进程为例，说明进程创建的主要过程：48(1) 从PCB池中申请一个空白的PCB，并且为该新进 程准备一个唯一的进程号。 (2) 为新进程的进程映像分配地址空间。 (3) 为新进程分配内存空间和其他各种资源。 (4) 初始化PCB（如设定该进程的内部标识符、状态、 优先级、程序块地址、数据块地址等）。 (5) 将新进程加入到相应的就绪进程队列中，如果 这时父进程处于就绪态，则该子进程可以直接 投入运行。49? 进程的阻塞和唤醒一个正在运行的进程，由于发生等待事件，如申请设备没有申请 到，或等待设备完成数据传输，或等待用户进行干涉，而不能继 续运行下去，它就不得不放弃CPU，从而进入阻塞状态。运行态 的进程转换为阻塞态是通过调用进程阻塞原语自发进行的。 进程阻塞的主要步骤如下： （1）停止调用者进程自身的执行，将现场信息保存到PCB。 （2）修改PCB的相关内容，如进程的状态由运行态变为等待态，并 且还要指出等待的原因等。 （3）将修改后的PCB加入到相应的进程等待队列中。 （4）转入进程调度程序，调度其他进程运行。50? 当执行的进程，在释放了某个资源时，就要担负起唤 醒由于该资源而进入等待态的进程。显然，进程的唤 醒不是自发的，而是通过占有该资源的其他进程运行 释放该资源时。进程的唤醒由进程唤醒原语实现。 进程唤醒的主要步骤如下： （1）根据唤醒的原因找出相应的等待队列，在队列中 找到进程的PCB。 （2）将该进程从等待队列出队。 （3）修改该进程的PCB，例如将进程状态由等待改为 就绪。 （4）将该进程的PCB插入到就绪队列。51? 进程的阻塞和唤醒是通过进程的切换来 实现的。进程的阻塞原语和唤醒原语的 作用恰好相反，一个进程由于等待事件 通过阻塞原语将自己阻塞起来，它必须 等到与它相关的进程（占有该资源）释 放该资源将它唤醒，否则，该阻塞进程 就永远处于等待状态。52? 进程的挂起和激活在具有挂起功能的系统中，进程的挂起和激活也是由相应的原 语实现的。进程挂起原语的工作主要有：当系统的资源紧张 （如内存）或系统性能下降时，可以通过进程挂起原语，将处 于活动就绪的进程调出内存，成为挂起就绪进程；或将处于活 动等待态的进程调出内存，成为挂起等待态的进程。当某进程 被挂起时，该进程的PCB的非常驻部分也要对换到磁盘对换区 中。进程挂起原语可以由自己或其他进程来调用。 当系统资源充裕或需要激活某个进程时，就需要通过进程激活 原语来实现，进程激活原语的工作主要有:首先将该挂起的进程 的PCB非常驻部分调进内存，然后修改进程的状态，将挂起就 绪态改为活动就绪态，将挂起等待态改为活动等待态。进程激 活原语只能由其他进程来调用。53? 进程的撤销 一个进程在正常运行结束或者在运行过程中出现 了严重异常或故障，这就需要通过操作系统或者 其父进程调用进程撤销原语对该进程进行撤销， 回收它占有的CPU和其他系统资源。进程在被撤 销时，该进程的子进程也被撤销。进程撤销可以 分成正常撤销和非正常撤销。程撤销的主要原因 有进程正常运行结束，进程执行了非法指令，进 程中出现了算术运算错误，地址越界，在目态下 执行了特权指令，I/O故障，对内存的非法使用等。54? 一个进程被撤销的步骤如下： （1）根据被撤销进程的标识号，从相应的PCB队列 中寻找到该进程的PCB，获得该进程的状态以及 资源占用情况。 （2）归还资源。撤销时，把属于父进程的资源归还 给父进程，把属于自己申请的资源归还给操作系 统，清除它的资源描述清单。 （3）若该进程还有子进程，则需要先撤销所有它的 子孙进程，以防止这些子孙进程脱离控制。 （4）撤销进程出队，该进程的PCB被操作系统回收， 加入PCB池。552.4 进程调度? 进程调度就是从就绪队列中选取一个进程 到CPU上去执行，从就绪队列中选择哪一 个进程，是进程调度策略（即进程调度算 法）问题，在什么情况下进行调度，这是 进程调度原因问题，具体怎样进行调度， 则是调度过程问题。由于进程调度是选一 个进程到CPU 上去执行，但从处理器角度 看，是处理器如何分配给各进程的问题， 因此，进程调度也被叫做处理器调度。562.4.1 进程调度简介? 一个作业从提交到最后运行，需要经过处理器两级调度， 即作业调度和进程调度。作业调度的任务就是将作业从外 存调入到内存形成就绪态的作业进程，然后通过进程调度 占有处理器运行。因此，作业调度也叫高级调度，进程调 度也叫低级调度。对于具有挂起功能的系统，还存在着中 级调度，即根据内存使用和系统性能状况，对进程实现进 程挂起和激活。因此，处理器调度共分三个层次，即低级 调度、中级调度和高级调度，进程调度是低级调度，本章 主要介绍进程调度。57? 进程调度按照进程运行是否可以被抢夺，可以分 为两种，一种是不可抢夺式，即进程在运行中不 能被其他进程抢占，除非自己运行完成或发生等 待事件或运行时间片到；可抢夺式是指当有其他 更紧迫的进程时，当前运行的进程必须让出CPU。 可抢夺式的调度方式更加灵活，系统性能更高， 得到广泛应用。 ? 产生进程调度的原因有哪些？一般地，当有下列 情况之一，就会产生系统的再次进程调度：当前 的进程运行结束或者异常终止；当前运行进程转 入等待态；在分时环境下，时间片已经用完；在 抢夺方式下，产生了更高优先级的就绪进程；产 生了中断事件。58? 进程调度过程中，要进行现场信息的保护和恢复 工作。当一个进程运行结束需要调度下一个进程 运行，或系统刚开始时调度进程运行，这时不需 保护现场。其余的情况下，要将当前放弃CPU的 进程的现场保护起来，即将该进程的PSW寄存器 内容，通用寄存器内容和控制寄存器内容写入到 该进程的PCB的对应栏目内，将新调入的进程的 PCB中的有关现场信息如PSW寄存器，通用寄存 器和控制寄存器内容写入到CPU相应的寄存器中。59? 进程调度中，进程调度算法的选择是一个很重要的问题。 由于进程调度是低级调度，调度频率很高，因此不同的算 法对于系统的性能和效率有着直接的影响。 调度算法的选择需要从以下几方面考虑： 资源利用率； 公平性； 计算时间和等待时间； 响应时间； 单位时间完成的进程个数； 力求采用的算法简单实用，总体效率高。602.4.2 进程调度的算法? 进程调度的算法很多，常用的有三种，即 先来先服务算法、优先级调度算法和时间 片轮转算法，也有的系统采用这三种算法 的综合，即多级反馈队列调度算法，此外， 彩票调度算法是一个很有特色的算法，具 有很多优点。下面对这五种算法进行介绍。61? 先来先服务调度（First Come First Service， FCFS）算法 几乎在所有的操作系统的调度算法中都有。这种调度算法总是 调度最先成为就绪态的进程，并且该进程一旦被调度占有CPU 就一直运行下去，直到运行结束或者由于等待某个事件不得不 让出处理器。先来先服务算法属于不可抢夺式调度算法．该算 法的优点是简单易懂，实现起来也很方便，但这种算法的缺点 是效率不高，偏重了计算型的进程，对I/O型的进程不利，该算 法的公平是“表面性”的，不能对就绪进程区别轻重缓急。当 前这种调度算法一般只作为辅助调度算法，例如在优先级调度 算法中，当两个进程级别完全相同时，则采用先来先服务策略 进行调度。这种算法实现时，当有新的就绪进程创建时，总是 将该新进程插入到就绪队列的末尾，每次调度时，进程调度总 是把处理器分配给就绪队列中的第一个进程。62? 优先级（Priority）调度算法 在该算法中，对系统中的每一个进程都设定一个优先级， 在进程调度时，总是选择就绪队列中优先级最高的进程获 得处理器去运行，这就是优先级调度算法。优先级是一个 整数，即优先数，有的系统约定优先数越大，优先级越高， 也有的系统，如UNIX，则是优先数越小，优先级越高。 因此，为了避免混淆，统一采用优先级，而不采用优先数 的概念。优先级调度算法中，根据是否可以抢夺，还可以分为不 可抢夺式优先级算法和可抢夺式优先级算法。63? 在不可抢夺优先级调度算法中，调度时，总是调度当时系 统中优先级最高的就绪进程，该进程只要占有处理器，就 一直运行下去，除非运行结束或由于自身原因而等待，在 该进程运行过程中，如果有优先级更高的进程进入就绪队 列，对该进程没有影响；而在可抢夺式优先级调度算法中， 总是严格保证让具有最高优先级的就绪进程使用CPU，也 就是说，在这种方式下，一个进程正在CPU上运行，如果 系统中有另一个就绪进程的优先级更高，则该进程就不得 不让出CPU，也即新的进程将正在运行的进程的CPU抢夺 了过来。因此，在这种调度算法中，CPU上运行的进程总 是当前系统中优先级最高的就绪进程。这种调度算法在实 时操作系统中特别有用。在实时系统中，首先强调的是实 时性，其次再考虑系统效率等因素．采用这种调度算法， 总是将一些紧迫的报警进程赋予最高的优先级，当紧急情 况发生，需要紧急处理的进程马上可以抢夺CPU而得到及 时响应。64? 优先级调度算法中，优先级的确定是个很重要的问题，不 同的系统处理方法也不相同。根据优先级是否可以不断变 化 ， 优 先 级 调 度 算法 可 以 分为 静 态优先 级 和动态 优 先 级．静态优先级就是在系统产生进程时，根据资源使用等 情况对该进程设定一个优先级，以后在该进程的生命周期 内，优先级是固定的，不可改变；动态优先级就是随着进 程的不断推进，优先级会进行相应的调整而不断变化。采 用动态优先级算法的系统性能要高点，但经常定期计算进 程的优先级的开销较大。优先级的设定一般可以根据进程 所使用资源的情况，进程的计算时间，进程的等待时间， 进程的紧迫程度，系统性能和效率等方面加以考虑。例如， UNIX系统中，就采用的是动态优先级调度算法，设定系 统进程的优先级高于用户进程的优先级；等待时间长的进 程优先级不断提高，在CPU上运行的进程的优先级随着时 间推移不断降低；对于外围设备使用频繁的进程或交互式 用户的进程优先级较高，等等。65? 优先级调度算法可以和先来先服务调度算法结合 使用。在一般情况下，采用优先级调度算法，当 有优先级相同的进程进行调度时，则采用先来先 服务调度算法。优先级调度算法可以这样实现： 当一个就绪进程需要加入就绪队列，需要根据 PCB中的优先级进行按序插入，优先级大的进程 总是插在队列的前面，调度时，总是选就绪队列 的第一个进程出队，占用处理器运行。66? 时间片轮转（Round Robin，RR）调度算法的典型应用是 在分时操作系统中，该算法属于可抢夺式调度算法。在分 时系统中，每个终端用户的进程一次使用处理器的最长时 间叫做“时间片”。在该调度算法下，系统将就绪进程按 照先来先服务的方式进行排队，进程调度时，每次调度就 绪队列的第一个进程，但该进程运行时间不得超过一个时 间片。当时间片到了，系统产生时钟中断，该进程就得让 出处理器（CPU被抢夺），然后重新插入到就绪队列的末 尾，等待下一轮次的调度，然后进程调度选择当时就绪队 列的第一个进程占用处理器。当占用处理器的进程运行结 束或者发生等待事件，就会引起新的进程调度。这样，就 绪队列的每个进程循环往复进行调度，每次最多运行一个 时间片，那么所有进程经过若干次调度，都会相继完成任 务。67? 在时间片轮转算法中，时间片的选择是个很重要的问题。时间片的选 择既不能太长，也不能太短，而应该是一种统计学上的折衷。时间片 的大小设定关系到计算机系统的效率，用户的反应以及进入系统的进 程数目等因素。如果时间片太长，则用户感觉到的响应会有所迟钝， 如果时间片大到让每个进程在一个时间片内就能完成任务，则时间片 轮转就退化为先来先服务调度算法了；如果时间片太短，以至于大多 数进程在一个时间片内完成不了，系统在进程的切换上花费的开销较 大，不利于系统效率的发挥。因此，时间片的设定要根据多方面因素 进行综合考虑，如系统效率、响应时间、进程切换开销以及进程的个 数等等。 ? 时间片也可以分为静态时间片和动态时间片两种。静态时间片就是时 间片始终固定，这种方式简单，但有时一个计算时间较长的进程会需 要调度很多次。例如当时间片是20ms（毫秒）时，一个需要计算20s （秒）的进程，就需要调度1000次，花费在进程切换上的开销是很大 的。对于这种情况，有些系统采用动态时间片，有一种动态时间片调 度是这样的，当第一次调度时间片用完后，以后每次调度，时间片加 倍。这样，对于一个20s的进程，在初始时间片为20ms时，只需要被 调度10次。68? 多级反馈队列轮转（Round Robin with Multiple Feedback）调度算法是 一种综合的进程调度算法，该算法是时间片轮转法、优先级调度算法 和先来先服务算法的综合应用。该算法的综合性能比较好，能够满足 各类用户的需要。该算法与以上几种算法不同之处在于，系统设置多 个就绪队列进行调度，它的主要思想是：系统将就绪进程按优先级设 置成多级，每一级就绪队列对应一个不同的时间片，较高优先级的队 列一般分配给较短的时间片。从第一级队列到最后一级队列，优先级 越来越低，但时间片越来越大．处理器在进行调度时，总是从第一级 就绪队列中选择一个进程占用处理器运行，在同一级就绪队列中调度 采用先来先服务的原则进行。只有在高一级就绪队列为空时，才会从 低一级进程就绪队列中进行选取。对于多级队列，一般将第一级就绪 队列称为前台就绪队列，其余队列称为后台就绪队列。 ? 可见，多级反馈队列轮转法，将就绪进程分成多个就绪队列，各个队 列有不同的优先级，而同一个队列优先级相同，不同队列的时间片不 同，调度时采用先来先服务，对每一个就绪队列来说，是时间片轮转 法。69? 系统在调度时，总是从第一个就绪队列中进行调度，只有高一级就绪 队列为空，才会调度下一级就绪队列。被调度到CPU上的进程，如果 在分配给的时间片（该时间片与该进程在调度时所在的就绪队列有关， 是对应的）内完成，则终止进程离开系统；假如在运行过程中，如果 发生了等待事件，就不得不放弃CPU，而转入到相应的等待队列中； 如果该进程在规定的时间片内没有完成，就放弃CPU，转入到下一级 的就绪队列队尾（下一级就绪队列优先级相应降低，但时间片相应增 长）。 ? 在系统的运作过程中，假如有新的进程产生进入第一级就绪队列，或 者以前被阻塞的进程由于等待事件的满足而从等待态转为就绪态，从 而要被加入到原先就绪队列的队尾时，假如这时的就绪进程的优先级 比当前正在CPU上运行的进程的优先级高，则系统就会抢占正在CPU 上运行的进程，将该进程放回到它调度前所在就绪进程队列的队尾， 然后进行新一次的处理器调度，调度高一级的进程就绪队列。采用这 样的可抢夺式的优先级调度算法，可以提高系统的效率，保证在CPU 上正在运行的进程总是当前系统中具有较高优先级的进程。 当前各种主流的操作系统，如UNIX，LINUX，Windows2000等均采 用这种多级反馈队列轮转调度算法。70多级反馈队列轮转调度算法示意图如图 2-7。就绪队列１（前台） 就绪队列２ PCB PCB ．．． ．．． PCB PCB PCB ．．． ．．． NULL PCB NULL… 就绪队列 n PCB PCB ．．． ．．． PCB NULL图 2-7 多级反馈队列轮转调度算法下的多就绪队列组织形式71? 策略驱动调度算法该算法是根据对各个用户的承诺进行调度的一种算法，因此也叫面向 用户承诺调度算法，这种算法的思想与前面几种进程调度算法具有很 大区别。当一个用户在工作时，假如这时系统中总共有n个注册用户， 则该用户应该获得1/n的CPU处理时间。因此，系统需要记录每个用户 从注册以来已经获得的CPU时间（这很容易算出），同时还要计算出 每个用户应该获得的CPU处理时间（用该用户登录以来的时间除以n， 就是该用户应得的CPU时间，这样策略驱动比率r=某用户实际拥有的 CPU时间/某用户应得的CPU时间。例如，若r=0.5，表示该用户实际运 行的时间只是应该拥有CPU时间的一半，若r=2.0，表示该用户实际运 行的时间已是应该拥有CPU时间的2倍。因此，在该种调度算法下， 每次调度总是选择策略驱动比率r最小的用户占有CPU运行。72? 彩票调度算法是一种很有特色的调度算法，并且具有一些很有趣的特 性。它的基本思想是：对于每个就绪态的进程，系统根据它对CPU的 使用要求，而向该进程发放一定数量的彩票。进程拥有的彩票，可以 参与“抽奖“，每张彩票对应CPU的一个固定长度的运行时间。中奖 的进程，就可以占有CPU运行。例如，系统假如总共发出了100张彩 票，进程P中奖了，则进程P占有CPU运行一个单位时间（如20毫秒）。 假如系统有5个进程，P1有10张彩票，P2有15张彩票，P3有20张彩票， P4有25张彩票，P5有30张彩票，系统共发出了100张彩票，那么由于彩 票抽奖的”绝对随机性“，则系统中P1有10％的概率占有CPU，P2有 15%的可能性占有CPU运行，等等。 ? 彩票调度算法与优先级调度算法是不同的。73?【例2-5】假如有以下6个就绪态进程，它们进入内存的时间，需要计算的时间以及优先级如 下。优先级共10级，用1～10十个整数表示，数值越大级别越高。不考虑进程调度所花的时 间，调度采用不可抢夺式，时间单位：单位时间。简单起见，设系统调度从8时刻开始。 进程名 进入就绪队列的时刻 计算时间 优先级 P1 0 2 3 P2 2 3 4 P3 3 5 8 P4 5 4 1 P5 6 3 4 P6 8 6 7 （1）写出分别采用静态优先级和先来先服务调度算法，以上进程调度执行的顺序。 （2）计算出各个进程在就绪队列中的等待时间和平均等待时间。解答： （1）由于在8时刻开始调度，这时系统中就绪队列中有6个进程，采用静态优先级算法调度，则调度序 列是 P3，P6，P2，P5，P1，P4（注：P2和P5的优先数相同，则按先来先服务调度进行）；采用先来先 服务算法，则调度序列是P1，P2，P3，P4，P5，P6。74?（2）各个进程的等待时间如下： 进程名 进入就绪队列的时刻 计算时间 静态优先级法等待时间 FCFS等待时间 P1 0 2 8+5+6+3+3-0=25 8-0=8 P2 2 3 8+5+6-2=17 8+2-2=8 P3 3 5 8-3=5 8+2+3-3=10 P4 5 4 8+5+6+3+3+2-5=22 8+2+3+5-5=13 P5 6 3 8+5+6+3-6=16 8+2+3+5+4-6=16 P6 8 6 8+5-8=5 8+2+3+5+4+3-8=17 静态优先数算法的平均等待时间是：（25+17+5+22+16+5）/6=15 先来先服务算法的平均等待时间是：（8+8+10+13+16+17）/6=12?请思考，假如在时刻3进行调度，本题的答案会不会有所不同？为什么？752.5 线程及其实现? 传统进程的缺点表现在以下两个方面： ? （1）进程既是资源分配的单位，也是调度的单位。进程 状态的频繁转换以及现场的保护和恢复会浪费大量的处理 器时间，同时，每个进程需要运行所需的必要空间限制了 系统中可以容纳的进程总数。这一点，在现代网络时代的 缺点，非常明显。进程数目的增多，增加了系统的负担。 ? （2）进程的并发粒度太粗，并发度不高，并且进程的切 换，进程之间或进程和操作系统之间的通信开销太大，特 别对当今分布式系统，并行计算以及C/S，B/S模式下的软 件应用，效率很难提高。表现在应用上，效率难以忍受， 可伸缩性弱。76? 多线程概念的产生，实际上是从进程基础上发展 起来的。为了使系统效率提高，将传统操作系统 的进程的两个功能即独立分配和保护资源和调度 与分派功能分开，将传统进程的第一项功能保留 给进程，第二项功能则由线程来。这样的好处是， 在多线程环境下，进程只负责资源分配和保护， 不需要频繁的调度和切换；而线程只负责执行， 能够轻装上阵，可以被频繁地调度和切换。可见， 多线程环境下，有了进程和线程的概念，系统效 率将会大大提高。77782.5.2 多线程环境下的进程和线 程? 多线程环境下的进程定义，很显然，就是：进程是系统进 行资源分配和保护的基本单位。进程包括容纳进程映象的 一个虚拟地址空间，以及对CPU、I/O资源、文件以及其 他资源的有保护有控制的访问。 ? 多线程环境下线程的定义是：线程是处理器调度和分派的 基本单位，是进程中能够并发，独立执行的控制序列。线 程是进程的组成部分，每个进程可以有多个线程，但至少 有一个线程（即主线程）。各个线程之间关系紧密，所有 线程共享它们所属进程拥有的资源，它们驻留在相同的地 址空间中，可以存储相同的数据。虽然同一个进程中的所 有线程共享进程获得的内存空间和资源，但每个线程都不 拥有资源。79? 线程由线程控制块（Thread Control Block，TCB）、用户堆栈、系统 堆栈以及一组处理器状态寄存器和一个私用内存存储区组成。 ? 线程也具有状态，线程的基本状态有运行态、就绪态和等待态。这里 需要注意的是，虽然提出了新的线程概念，但是线程的概念是从进程 概念发展起来的，只要区别出线程是传统进程中的调度与分派功能的 分离和发展，对理解的线程就很简单了。线程的状态转换类似于进程 的状态转换，前面章节讲的进程调度，也同理，进程调度在现代多线 程环境下的操作系统中应该是线程调度，也叫低级调度。只要把握住 线程和进程的区别和联系，传统中的进程概念对理解线程非常有帮助。 例如，进程有挂起状态，但线程就没有挂起状态，这是因为，线程不 是资源的拥有单位，因此，线程的挂起是没有意义的。当一个进程由 于系统性能原因被挂起，则它的所有线程由于共享了进程的地址空间， 而必须全部对换出去。挂起状态是进程级的状态，而不是线程级的状 态。80? 线程的特性，同传统的进程类似，也具有并发性、共享性、 动态性和结构性，但制约性和独立性需要作个说明。线程 的独立性主要体现在线程是系统调度和分派的基本单位， 线程的制约性主要是由于同一个进程的线程由于共享了某 个资源而导致的一种协作或竞争的关系，而产生线程制约 性的原因与传统进程有所不同。 ? 线程的控制原语主要有创建（Spawn）线程、阻塞（Block） 线程、活化（Unblock）线程、（Finish）结束线程。 ? 思考：线程的基本控制原语为什么没有类似于进程的挂起 和激活控制原语？81? 进程和线程的比较 ? （1）并发性 系统中进程可以并发运行，线程也可以并发运行，这样，操作系统具 有更好的并发性，更加充分利用系统资源，提高系统效率。进程间的 并发是粗粒度的，线程的并发更加“细”二者的结合使得系统效率大 大提高。 ? （2）资源分配与占有 在系统中，进程是资源分配和保护的基本单位，线程几乎不拥有资源， 但线程可以访问本进程的资源，这样，使得某进程下的各个线程之间 进行共享、通信很方便，同时，线程不必对资源进行分配和管理，从 而线程很“轻”，能够轻装上阵，专注于自己的执行序列，从而更加 灵活，效率得以提高。82?（3）系统开销与效率 系统中的进程在创建或者撤销时，系统需要对该进程进行分配资源和回收资 源，而线程的创建和撤销，由于线程不拥有资源，因此，线程的创建和撤销 相对于进程而言，开销要小得多。同样地，操作系统进程的切换所需的开销 要比该进程内的各个线程之间的切换所需的开销要大得多。特别的，同一进 程的各个线程，它们可以共享进程的资源，如代码段、数据块、I/O设备以及 已打开的文件等，因此，线程之间的通信很容易实现。 （4）调度效率与灵活性 操作系统中，进程主要是资源分配和保护的基本单位，进程拥有资源；而线 程是系统调度和分派的基本单位，线程不拥有资源，但可以访问该进程的资 源。这样，线程的调度和切换，非常的简单易行，并且在同一进程中的线程 的切换不会导致进程切换，因此，系统效率很高，并且并发程度也大大提高。?832.5.3 多线程的优点及其应用? ? ? ? 线程是系统调度和分派的单位，是轻量级进程，它共享所属进程的内存空间 和资源，但不拥有资源，线程具有以下优点： （1）节省内存空间。这是因为，多个线程共享进程的地址空间。 （2）并发粒度小，并发程度高。线程不拥有资源，只是进程中的一个执行序 列，因此，一个系统中可以存在好多线程，甚至线程的数目没有限制。 （3）线程之间通信方便。同一个进程的各个线程之间关系很密切，它们自动 共享所属进程的地址空间，对于进程中的全局数据可以自由访问，实现自然 共享。 （4）线程切换简捷。同一个进程中的各个线程由于共享同一地址空间，而线 程不拥有资源，因此，线程的切换开销很小，速度很快。 （5）线程的管理开销很小。线程的创建以及终止所需的系统开销非常的小。 这是因为线程只负责执行，不拥有资源。因此，在具有多线程功能的系统中， 相比只具有传统进程的系统有很高的系统效率。??84?下面是多线程的一些应用实例。 （1）提高文件下载速度。网络应用中下载速度的提高具有重要意义．可以将需要下载 的一个大文件分割成n个相等的小文件，采用n个线程同时下载，下载完毕后在拼接成 原来的文件。这样的下载速度会大大提高。早期著名的下载软件网络蚂蚁就采用了这 个技术。 （2）采用查询方式进行数据采集。传统地，在数据采集中，采用查询方式，效率是很 低的。但如果将查询方式的数据采集设计成一个线程，则效率就会大大提高。可以设 计一个线程专门进行数据采集，一个线程专门运算，一个线程专门用来输出。 （3）C/S和B/S网络服务离不开多线程。一个网络服务没有多线程，是不可想象的。网 络服务启动时，就在监听，如有请求，就进行接受（Accept），然后在服务端产生一个 线程，该线程专门负责与该客户端进行通信，而网络服务可以继续在端口上进行监听。 多线程的例子在现代计算机应用中可以说是无所不在，无处不在。多线程技术具有广 泛的应用前景。?852.5.4 多线程实现的三种方式? 内核级线程 内核级线程（Kernel Level Threads，KLT）的实现，它 的思想是线程管理的所有工作都是由操作系统内核来完成。 ? 用户级线程 用户级线程（User Level Threads，ULT）就是线程的所 有管理和控制任务全部由应用程序来完成，在用户空间内 实现，操作系统的内核感知不到线程的存在。 ? 混合级线程 SUN公司的Solaris操作系统是混合式线程的例子。在混 合式线程方式下，内核支持对线程的管理和控制，同时也 提供线程库使得用户也可以对线程进行建立、调度和管理。862.5.5 Java环境下多线程设计举 例? Java程序设计语言是在语言级基础上支持多线程设 计的。在Java中，设计多线程有两种方式，一种是 继承Thread类，另一种是实现Runnable接口，由于 Java只支持单一继承，如果采用继承Thread类的方 式设计多线程，则该线程类不能再继承其他类了， 因此设计多线程，采用实现Runnable接口具有更强 的通用性。但通过继承Thread类的方法实现多线程 比较简单。872.6 并发进程的概念系统中存在着许多并发进程，它们需要相互 合作或联系才能完成特定的功能，同时， 各个进程的运行又是“走走停停，停停走 走”，进程的推进速度是不可预测的。因 此，并发进程的这种复杂性成为进程管理 中理论性最强的研究课题，对理解现代操 作系统具有重要意义。882.6.1 相关进程及其关系? 并发进程中，有的进程之间可能是没有任何关系的，它们不共 享任何的系统资源，因此，这些进程互为无关进程。? 共享某些资源的进程就是互为相关进程。 ? 由于进程运行的动态性，在某些时刻，两个进程可能是无 关的，因为这时它们没有共享某个资源，但随着进程运行 的推进，就有可能共享某个资源，它们就变为相关进程， 当对共享资源的访问结束后，这些相关进程又变为无关进 程。89? 进程间的关系，一种是竞争，另一种就是协作。 进程间的竞争关系：这种竞争关系在操作系统内部十分普遍。例如， 上面的例子中两个进程对打印机的使用就是一种竞争关系，除此以外， 两个进程对共享变量的访问、对独享设备的使用等都是这种进程竞争 的关系。进程竞争的关系在并发进程中是通过进程互斥来解决的。进 程互斥在后面章节会详细介绍，也是并发进程中的重点内容。 进程间的协作关系：这种协作关系在操作系统内部也十分普遍。例如， 上面的两个进程通过一个文件来进行合作，就是这种协作关系。生产 者/消费者问题是进程间协作的典型例子。协作的各个进程间必须达到 某种“默契”才能使进程得以顺利、正确运行下去。进程间的协作是 通过进程间同步机制来实现的。进程同步机制在后面章节会详细介绍， 也是并发进程中的另一个重点内容。 ? 进程间的竞争和协作关系，广义地说，进程的竞争关系是一种特殊的 进程协作关系，也即进程互斥也是一种特殊的同步。由于无关进程的 运行，互不影响，因此，下面只讨论相关进程。902.6.2 与时间有关的错误? 一个程序，在相同运行的环境下，一会运行输出的是这个 结果，一会运行是另一种结果，这样的程序还有用户敢使 用。在多道环境下，发生的这种错误被称作“与时间有关 的错误”，意思就是一个程序在同一个数据集下，不同时 间运行的结果可能不同。 ? 下面通过三个例子来说明与时间有关的错误，特别要认真 体味为什么会发生与时间有关的错误？发生与时间有关的 错误的本质原因是什么？你根据对原因的分析，能不能提 出一种解决与时间有关的错误的办法来？91? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【例2-6】（公园游客计数问题）一个公园用计算机进行管理，简单起见，只管理游客人数， 也就是说，能够记录当前在公园中游乐的人数。完成这个功能的程序如下（类C语言）。 int count＝0; //下面两个进程并发运行 process PersonIn（void）//游客进入的处理进程 { temp= //1 temp++; //2 count= //3 } process PersonOut（void）//游客离开的处理进程 { temp= //4 temp--; //5 count= //6 }92??下面对该用计算机进行管理游客人数的程序进行分析，来指出该程序的不确 定性和不可再现性。假设某一时刻，公园中有3人，即count为3，这时，有一 个新的游客进来，另一个游客要离开。当游客进入时，要进入PersonIn进程处 理，假如执行了2语句后，该进程 被 中 断 （ 中 断 发 生 是 不 确 定 的 ） ， 这 时 temp 为 4 ， count 还 是 为 3 ， 进 程 PersonOut开始运行，经过4、5、6三个语句，最后，count为2，然后，被阻塞 的PersonIn进程继续运行，经过语句3，得到count是4，显然这是错误的，因 为本来公园有3人，一个游客离开，一个游客进来，人数应该还是3人才对。 对于这个例子，稍微改变一下分析，会得出结果是2的错误。例如，假如出去 的进程PersonOut先被处理，在语句5处理完毕后，PersonOut进程被打断，这 时，count为3，temp为2，然后PersonIn进程开始运行，经过语句1、2、3，得 到count为4，当PersonIn运行完毕后，PersonOut中断结束，继续运行，经过语 句 6 ， 得 到 count 是 2 ， 显 然 是 错 误 的 。 考 虑 另 一 种 情 况 ， 假 如 PersonIn 和 PersonOut两个进程在各自的运行中，都没有被打断，则最后的count是3。可 见，同一个程序，在同样的环境下，运行得出了不同的结果。这是多道环境 下并发进程运行产生的新问题。在多道环境下，程序运行的结果变得不确定， 不可再现了。本例的结果是属于结果不唯一的错误。93?? ? ? ? ? ? ? ? ? ? ?【例2-7】（飞机航班联机售票系统）假设有一个飞机航班售票系统，有n个 售票处，每个售票处可以共享系统的公共数据库中的飞机航班信息，设某一 天的航班的剩余票数分别存放在公共数据区域的一些单元Mj（j=1,2,3,…m； m为航班数）。本例共有n个进程，记为Salei（i=1,2,…，n）。temp是每个进 程的局部变量。售票的某一个进程的程序算法如下： process Salei（i=1,2,…,n） { 根据旅客的订票要求找到Mj； temp=Mj; //1 if(temp&=1){ //2 temp--; //3 Mj= //4 将这张票打印出来，给旅客 } else printf（“对不起，票已经售完”）; }94? 有了上例的分析方法，对本例的分析不难。下面分 析当某航班只有一张票时，会不会将该张票卖给好 多旅客。设某一航班只有一张余票，有3个旅客同 时来买同一航班的这张余票。假如第一个旅客来买， 系统执行Sale1进程，第二个旅客来买票时执行Sale2 进程，第三个旅客执行Sale3进程，假如这三个旅客 都经过了语句1、2、3，这时，每个进程各自的 temp局部变量都是0，然后将temp赋给Mj ，最后Mj 是0，这样，导致了同一张票卖给了3个不同的旅客。 这也是一种与时间有关的错误。本例和上例都属于 结果不唯一的与时间有关的错误。除了这种错误外， 还有一种会导致进程永远互相等待的错误发生。95? ? ? ? ? ? ? ? ? ? ? ? ?【例2-8】假设有两个并发进程NewMem和DeleteMem，NewMem进程负责申 请内存资源，DeleteMem进程负责回收内存资源。下列是内存管理的程序算 法，在该算法中，f是可用的内存大小，r是申请或回收的内存大小。 process NewMem(int r) ｛ if (r&f) 申请进程由于申请不到内存资源而进入相应等待队列； f-=r; //申请到内存资源后，修改内存分配表 ｝ process DeleteMem(int r) ｛ f+=r;; //对内存分配表进行相应修改 //唤醒由于等待内存资源而被阻塞的进程 ｝96? 在以上算法中，有可能会出现进程NewMem永远等待的问题。 例如，当NewMem进程申请内存时，假如申请量r比可用量f大， 则不能被分配，假设，正在这时，该进程被中断，而另一个进 程DeleteMem开始运行，该进程将所借内存资源回收，然后修 改内存分配表，并且唤醒等待内存资源的阻塞进程，但由于这 时NewMem进程还没有进入等待态，因此，DeleteMem进程无 等待进程可唤醒。这样，NewMem进程假设再没有别的内存回 收进程运行的情况下，就会发生永久等待。这也是一种与时间 有关的错误。 ? 以上介绍了三个例子，都是说明在多道程序设计环境下，会出 现与时间有关的错误。发生与时间有关的错误，使得在并发环 境下的程序运行变得复杂起来，不再具有顺序运行环境下的封 闭性、确定性和可再现性，究其原因，主要是因为并发进程由 于中断的原因而导致运行的相对速度不可预测，而对具有共享 资源（硬件资源或软件资源，如共享变量）的一段程序区域的 间断访问，从而导致了与时间有关的错误的发生。972.6.3 临界区概念及其管理要求? 所谓临界区（Critical Section），就是并发进程中与共享变量有关的程 序代码段，而把该共享变量代表的共享资源称为临界资源（Critical Resource）。? 以下是在解决与时间有关的错误的过程中，得出的临界区管理 的四个公认的管理要求。因此，一个好的解决方法必须能够满 足以上四个条件。 （1）不存在有关进程间相对推进速度、系统内有多个CPU的假 定； （2）一次最多只能有一个进程进入临界区，也即没有两个或两 个以上的进程能够同时进入临界区，当有一个进程在临界区内， 其他想进入临界区的进程必须等待，这一点充分说明了临界区 的互斥访问特性； （3）不能让一个进程在临界区内无限制地运行下去，在临界区 中的进程必须在有限时间内运行结束而离开临界区； （4）等待进入临界区的进程，在时间上不能被无限推迟。982.6.4 临界区管理的尝试? 关中断 关中断是实现临界区管理的一种最简单的方法。该方法的实现思想是， 当一个进程进入临界区后，就关闭所有中断，当该进程离开临界区后， 再重新开启所有中断。由于进程的切换是由时钟或其他中断导致的， 当所有中断被屏蔽后，其他进程不可能有运行的机会，因此，自然地， 也不会进入到该进程的临界区去执行。 这种方式的缺点是明显的：一是，这种方式下用户进程需要有开关中 断能力，但开关中断指令是特权指令，这样做，系统内核的安全会发 生严重问题；另一个缺点是，该方法只能对单CPU系统有效，对多 CPU环境下，一个用户进程关闭了中断，但运行在其他CPU上的进程 仍然可以进入它的临界区，从而仍然会发生与时间有关的错误。 从以上分析可以看出，关中断这种纯硬件方式实现对临界区的管理， 只能对单处理器环境下的内核进程有效，而对于多处理器或用户进程 则不适用。99? 纯软件互斥算法 ? 多道环境下的相关的并发进程在运行中可能会发生与时 间有关的错误，从而严重影响了新一代操作系统的设计 和开发，因此迫切需要提出一种简单有效的手段或机制 来解决这一致命的问题。众多的计算机科学研究人员从 纯软件角度进行了广泛而深入的研究，提出了很多种纯 软件的算法，有的确实能够解决临界区的管理问题，也 有的，最后最证明是错误。下面对这些纯软件实现临界 区管理的算法作一个介绍，共介绍3个典型的算法，其 中前两个算法是错误的，第三个算法是正确的。介绍的 次序采用从简单到复杂，循序渐进的方式，这样有助于 读者深刻理解并发环境下临界区管理的复杂性，从而对 后面将要讲解到的信号量机制和管程以及消息传递机制 有比较深刻的认识和感悟。100? ? ? ? ? ? ? ? ? ??测试并设置指令 测试并设置指令（Test and Set，TS）是一种软件和硬件相结合的解决临界区互斥的一种方法。 这种方法的思想是：采用一个原子操作，记为TS，用该TS操作对进程的共享变量进行测试和 设置，TS的功能用类C语言描述如下： int TS(int & flag) //这里是C/C++的引用，表示在函数内部改变的flag变量 //对调用函数的实在参数有影响 { t= flag=1; } 以上是TS原子操作的功能。TS操作首先查询出当前的共享变量的值，作为参数返回，同时将 该值置为1，特别地，TS是原子操作，该函数的执行不允许被打断。下面利用TS操作，来实 现临界区互斥。 首先设置一个各进程共享的变量flag，初值设为0。进程在进入临界区之前，需要通过TS原语 对共享变量进行测试。如果flag为0，则将flag设置成1，然后该进程进入临界区；假如flag已 经被别的进程设置为1，则该进程需要忙碌等待；当进入临界区的进程执行完毕离开时，要 将共享变量flag置为0。算法的类C语言代码如下：101? ? ? ? ? ? ? ?//进程Pi的代码，flag是共享变量 while(1) { while( TS(flag)); 临界区; flag =0; } 这种算法仍然存在忙碌等待而浪费CPU宝贵时间的毛病，因此， 这种算法在实际系统中也很少使用。在实际系统中，广泛采用 的是PV操作和信号量机制、管程机制和消息传递机制，这在下 面章节中予以介绍，是本章的重点内容。当然，通过本节临界 区管理的尝试的学习，对理解后面的内容打下了良好的基础。1022.6.5 信号量与PV操作? 杰出的软件大师Dijkstra根据对城市交通和信号灯的观察与 分析，进行抽象和数量化，提出了信号量和PV操作的概 念。 ? 信号量（Semaphore）s：是对进程而言，代表可以使用的 资源的个数。信号量在定义初始化后是一个整数，当s为 正数时，表示该类资源可以被使用的个数；当信号量s为0 时，表示该类资源已经全部分配完毕；当信号量s为负数 时，仍然表示该类资源的个数，但这时的资源，已经分配 完毕，并且还“欠”进程若干个资源，所欠资源的个数为 信号量的绝对值abs(s)，这时的信号量，也可以看着，当 前有abs(s)个进程在等待使用该类资源。一句话，简单地 说，信号量可以就看成对相关进程而言，当前可以使用的 资源的个数。103?? ? ? ? ? ?? ? ? ? ? ? ?P操作：P操作是原语操作，P操作在执行中，不能够被中断。P操作的内部过程表示为：void P(Semaphore s)｛ s--; if(s&0) wait(s); //进程调用wait进行自我封锁，转入等待状态 ｝ P操作的含义是，将信号量s减去1，如果这时s小于0，表示原先s最多是0，已经没有可用资源 了，因此，这时的进程就在s信号量上等待，自己进入等待状态。 V操作：V操作是原语操作，V操作在执行中，不能够被中断。V操作的内部过程表示为： void V(Semaphore s)｛ s++; if(s&=0) Revoke(s); //该进程担负起唤醒在信号量s上等待的进程 ｝ V操作的含义是，将信号量s 加上1，如果这时s小于等于0，表示原先s最多是-1，表示有abs(s) 个进程在等待使用该资源。因此，这时的进程，需要担负起唤醒在信号量s上等待的进程。104??信号量是一种特殊的量，有特殊的含义，记录着当前该类资源可用的个数， 在定义信号量时可以对它进行初始化，以后，对信号量的操作只能由PV操作 原语进行，在进程进入临界区之前，需要对信号量作P操作，在进程离开临界 区时，需要对信号量作V操作。对于进程互斥问题，假如有两个进程访问一 个资源，可以将该资源对应的信号量s设置为1，在进程需要进入临界区时， 要做一个P操作，于是s变为0，假如还有其他进程想进入自己的临界区，它也 需要作P操作，这时，s变为-1，根据P操作原语的功能，该进程就会进入阻塞 状态，从而实现了进程间的互斥；当第一个进程在临界区完成后，对信号量s 作加1，s变为0，表示此时，在信号量上有一个进程在等待进入临界区，于是 该进程担负起唤醒的义务，从而处于的等待态的进程进入临界区内运行。可 见，信号量和PV操作机制完全满足对临界区管理的四个要求，即进程相对速 度和CPU 个数不定，无空则等，有空让进，互斥进入，并且该进制算法简单， 易于理解，实现起来很容易。从PV操作的内部过程来看，很简单，在具体实 现时，只要将PV这两个原语设计成原语即可，原语的设计可以通过关中断实 现。 信号量和PV 操作机制在解决与时间有关的错误方面非常有效。下面从进程互 斥和进程同步两个方面来深入理解该机制解决复杂问题的思想。从以下的各 个示例和例子中，可以深刻体会到信号量和PV操作机制的“形式简单，内容 丰富”。105? 现在信号量和PV操作机制已经得到广泛使用，但在有些教科书 或系统中，PV操作又被叫做up和down，wait和signal，sleep和 wakeup，lock和unlock等，这些都是名称不同，原理类似。为了 统一和叙述方便，在本书中，信号量和PV操作机制我们全部采 用Dijkstra最早提出的形式即统一采用P操作和V操作的形式。此 外，当前在Windows系统和VC++环境下，以及Java环境下，可 以开发出进程（或线程）的互斥和同步的应用程序，在这些环 境下，虽然不是采用的操作P和V操作这种形式，但所采用的思 想还是一致的，有兴趣的读者可以参考有关书籍，这样可以对 进程（或线程）的互斥和同步机制的实现以及程序设计思想有 很深的理解，从而提高多线程程序设计的基本素养。 ? 最后提一下，P、V操作是Dijkstra的母语“上锁”、“解锁”这 两个单词的首字母。1062.7 进程的互斥和同步? 并发进程间的关系表现为进程之间的互斥 和同步关系，下面对进程的互斥和同步问 题进行深入分析和探讨。1072.7.1 进程的互斥? 进程互斥（Mutual Exclusion，Mutex）是并发进程间的一种普遍的关 系，进程互斥指的是：对于某个系统资源，当有一个进程正在使用时， 其他进程如果想使用，则必须等待，即该资源不得同时使用。直到使 用该资源的进程释放了该资源，其他进程方可使用。 ? 日常生活中进程互斥的例子有很多，例如相对方向的两个人要通过一 个独木桥，就是一个典型的进程互斥问题。 ? 有了信号量和PV操作机制，能够很有效地解决进程互斥的问题。例如， 对于前面的公园游客计数问题，采用PV操作解决后的程序如下。 ? int count=0; ? Semaphore s=1; ? //下面两个进程并发运行108? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?process PersonIn（void）//游客进入的处理进程 { P(s); //1 temp= //2 temp++; //3 count= //4 V(s); //5 } process PersonOut（void）//游客离开的处理进程 { P(s); //6 temp= //7 temp--; //8 count= //9 V(s); //10 }109? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?对于飞机航班联机售票系统，采用信号量和PV操作机制的解法如下： Semaphore s=1; //下列各进程并发执行 process Salei（i=1,2,…,n） { 根据旅客的订票要求找到Mj； P(s); //1 temp=Mj; //2 if (temp&=1){ //3 temp--; //4 Mj= //5 V(s); //6 {将这张票打印出来，给旅客}; } else ｛ printf(“对不起，票已经售完”); //7 V(s); //8，若无此语句，会出现什么情况？ ｝ }110? 从以上两个例子中可以看出，用PV操作和 信号量机制解决进程互斥非常简单，可以 形式化地描述成以下三个步骤： （1）精心确定每个进程的临界区；（2）在进入临界区前，执行P操作； （3）在离开临界区时，执行V操作。111? 进程互斥的信号量和PV操作解法，一般地，信号量初值总是为1，并 且在同一个进程代码中，P操作和V操作总是成对出现，一一对应， 缺一不可。但有人会说，在飞机联机售票系统中，P、V操作没有成 对出现啊？那里不是一个P操作，两个V操作吗？实际上，飞机售票 系统中的P、V操作仍然是成对出现的。因为，我们注意到，虽然有 两个V操作，但这两个V操作恰好分散在if和else语句中，因此，任何 一次临界区的执行，V操作只执行一次，不是吗？因此，在飞机售票 系统中，P、V操作仍然是成对出现，一一对应的。 ? 经过以上分析，进程互斥得到了简单有效的解决，单纯的进程互斥问 题就是这么简单。但是，在下面马上要讲到的进程同步问题中也通常 存在着进程互斥问题，那么进程互斥的解决就显得复杂了，需要一定 的构思和创造性。112? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【例2-9】（进程互斥的例题）假如有一个小型超市，能够最多容纳30人进行同时购物，该超市有一个入口， 一个出口。入口处有购物篮，每个购物者可以拿一个篮子进行购物，购物完毕，到出口处结账。试用信号 量和PV操作机制求解购物者购物的同步算法。（注：入口和出口处禁止两人或两人以上同时通过） 解答：本题是一个典型的进程互斥问题。对于该问题，首先需要设置一个互斥信号量mutex，初值为30，然 后再设置两个互斥信号量s1和s2，s1的初值为1，用来对购物者在入口处进入时取购物篮的互斥（因为入口、 出口处只能让一人通过）；s2的初值也为1，用来对购物者在出口处结账放下购物篮的互斥。该问题求解后 的算法如下（某个购物者进程）： typedef int S Semaphore mutex=30,s1=1,s2=1; process client_i(void) { P(mutex); P(s1); {从入口处进入超市，并且拿起一个购物篮}; V(s1)； P（s2）； {到出口处进行结账，并放回购物篮}; V(s2); {从出口处离开超市}; V（mutex）； } 读者请思考：1.为什么在本例中，进程代码内部没有写循环？2.假如该超市的入口与出口在一起，如何修改 程序？1132.7.2 进程的同步? 所谓进程同步（Synchronization），指的是并发进程之间为了合作完 成同一个任务而形成的一种制约关系，一个进程的执行依赖于另一个 进程（合作伙伴）的消息，当一个进程没有得到合作伙伴进程的消息 时，不得不等待，直到该消息到达被唤醒后，该进程才能继续向前推 进。 ? 进程同步是由于并发进程之间由于合作而形成的制约关系，也叫直接 制约关系，相应地，进程互斥中所形成的不同进程之间的竞争关系， 成为间接制约关系。 ? 日常生活中，进程同步的例子普遍存在。例如，两个人下棋就是一种 进程同步的例子。除此以外，你还能举出其他一些例子吗？ ? 进程同步的经典例子有生产者/消费者问题，哲学家就餐问题，读者/ 写者问题和理发师问题。下面对这四个问题作个详细介绍，并再举几 个例题，以深刻理解进程同步和互斥问题。114? ? ? ???生产者/消费者问题 生产者/消费者问题是一个典型的进程同步问题。为了让读者对进程同步有一个好的理解，我们循序 渐进地来对生产者/消费者问题进行分析和探讨。操作系统内部很多进程同步问题都可以看着是生产 者/消费者问题或它的简单变形。 （1）最简单的生产者/消费者问题：一个生产者，一个消费者和一个缓冲器。 该问题可以描述为：只有一个生产者，一个消费者，一个缓冲器，生产者生产的产品，只有放到缓 冲器中，消费者才可以进行消费；只有消费了产品后，生产者才可以继续生产。生产者不可以连续 两次进行生产（这样会将前面的产品冲掉）；消费者也不可以连续两次消费产品（这样就是“脏 读”）。显然，该问题是个进程同步问题。下面采用PV操作和信号量进行解决。 首先需要设置两个信号量sp和sc，sp表示是否可以将产品放入缓冲器，一开始缓冲器是空的，因此 初值是1；sc表示缓冲器中是否有产品可以被消费，一开始没有产品，显然初值应为0。 对生产者来说，首先生产产品，但生产的产品要放入缓冲器，则必须要判断缓冲器是否为空，则需 要对sp信号量作P操作，如果P操作后sp为0，则可以将产品放入缓冲器，放入缓冲器后，需要对信 号量sc的作V操作，因为这时可以消费的产品个数增加了1，因此要对sc作V操作，同时，V操作还 有一层作用就是假如有消费者等待，则生产者需要唤醒消费者；若P操作后sp小于0，则该生产者生 产的产品不能放入缓冲器，并且该生产者转入等待，直到消费者取走产品后唤醒生产者为止；对于 消费者，消费产品之前，需要对sc信号量作P操作，看看有没有产品可消费，如果P操作后，sc为0， 则可以取走产品，同时，需要对sp信号量作V操作，一方面对生产者而言，可用资源多了一个，同 时，如果有生产者在等待放入产品，消费者还需要唤醒生产者；若P操作后，sc小于0，则表示当前 无产品可取走，消费者必须等待，直到生产者生产了产品放入缓冲器后唤醒消费者为止。最简单的 生产者/消费者问题的解法如下：115? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?int buffer； Semaphore sp=1,sc=0; //下列进程并发执行 process producer(void) { while(1) { {生产一个产品product}; P(sp); Buffer= V(sc); } } process consumer(void) { while(1) { P(sc); {取走缓冲器中的产品}; V(sp); {消费该产品（对该产品进行处理）}; } }116? （2）一个生产者，一个消费者和n个缓冲器的生产者/消费者问 题 这种情况下，只有一个生产者，一个消费者，但有n个缓冲器。 这时，生产者可以连续生产n个产品，同时，消费者也可以连续 消费产品（只要有产品可消费）。因此，该问题也比较简单。 该问题主要是有n个缓冲器，可以采用数组来表示这个缓冲器， 但生产者生产到数组最后一个元素时，采用取模（取余数）的 方法转到第0个元素继续生产。生产者在生产了一个产品后，首 先要判断是否能够放入缓冲器，需要对sp作P操作，这时的sp初 值是n，同时，为了能让生产者方便地将产品放入缓冲区的指定 空闲位置，需要一个整型变量k用作位置指示，放入一个产品后， 位置向后挪动一个，下一个位置可以通过语句k=(++k)%n得到。 同理，消费者对应的sc信号量初值仍然是0，一个位置指示t， 通过语句t=(++t)%n来调整消费者下一个消费的产品位置。该问 题的解法如下：117? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?int buffer[n],k=0,t=0; Semaphore sp=n,sc=0; //下面进程并发执行 process producer(void) { while(1) { {生产一个产品product}; P(sp); Buffer[k]= k=(++k)%n; V(sc); } } process consumer(void) { while(1) { P(sc); {取走缓冲器Buffer[t]中的产品}; t=(++t)%n; V(sp); {消费该产品（对该产品进行处理）}; } }118? ? ???（3）典型的生产者/消费者问题：m个生产者，r个消费者和n个缓冲器 这是典型的生产者/消费者问题。对该问题有两种解法。 由于现在有m个生产者，r个消费者，n个缓冲器。m个生产者在生产了产品向 缓冲器中存放时，由于该m个生产者需要共享变量k这个位置指示，而这个k 变量对于所有生产者而言，必须互斥访问；同理r个消费者对位置指示t也需要 互斥访问。因此，生产者只能有一个可以进入缓冲器放产品，消费者也只可 以有一个可以进入缓冲器取物品，但一个生产者在缓冲器放物品时，消费者 是可以取物品的，因为生产者和消费者用了不同的位置指示变量。对该问题 的解法，有两种，第一种是任何时刻，只能有一个生产者或消费者在缓冲器 中；第二种是一个生产者在缓冲器中时，一个消费者可以进入缓冲器取产品。 显然第二种解法的并发度要比第一种要高点。 下面对第一种解法进行介绍，第二种解法可以在第一种解法上简单修改即可。 读者请思考，第二种解法怎样从第一种解法进行修改而得到？ 对于第一种解法，除了仍然有sp、sc信号量外，还要增加一个新的互斥信号 量s，s的初值为1。该问题的解法如下：119? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??int buffer[n],k=0,t=0; Semaphore sp=n,sc=0,s=1; //下面进程并发执行 process produceri(void) （i=1,2,3,…,m） { while(1) { {生产一个产品product}; P(sp); //1 P(s); //2 Buffer[k]= k=(++k)%n; V(s); V(sc); } } process consumerj(void) (j=1,2,3,…,r) { while(1) { P(sc); //3 P(s); //4 {取走缓冲器Buffer[t]中的产品}; t=(++t)%n; V(sp); V(s); {消费该产品（对该产品进行处理）}; }}120???下面对生产者进程进行分析，消费者进程可以同理分析而得。一个生产者生产了产品，能不 能放到缓冲区中，现在需要进行两关测试。首先，需要缓冲器有空闲，这可以从P(sp)判断得 出，当这一关通过之后，还需要判断，有没有其他的生产者或消费者在缓冲器中，这需要通 过P(s)来得到。只有经过这两关，生产者才可以将产品放入缓冲器。放入产品后，调整生产 者位置k指示，然后准备退出缓冲器，需要作V(sc)，一方面可用产品增加，另一方面需要唤 醒等待的消费进程（假如有的话），还要将对互斥信号量s作V(s)，让其他生产者或消费者可 以进入缓冲器了。 从上面的分析，可以很清楚地看出，该问题的第二种解法可以很方便的写出。前一种解法， 主要因为生产者和生产者之间、消费者和消费者之间以及生产者和消费者之间都共享了信号 量s，使得生产者和消费者不能同时进入缓冲器，只要对生产者之间设置一个互斥信号量s1， 对消费者之间也设置一个互斥信号量s2，s1和s2的初值均为1，这样第二种解法就简单地实现 了。读者可以试着写写看。 在本问题中，再一次可以发现，PV操作解决进程同步是简单有效的，但仍然会发生“危险”。 就以上面的程序代码为例，假如一个程序员粗心，将语句1和2写反了，同时语句3和4也写反 了，这样，假如开始时一个消费首先消费，该消费者经过语句P(s)，可以下去，在执行P(sc) 时，由于没有可消费的产品，于是该消费者不得不等待，直到生产者生产了产品放到缓冲器 后唤醒它为止；但是，这时，生产者要存放产品到缓冲器，首先执行P(s)，而由于这时有一 个消费者在缓冲器中，因此，任何生产者都不能进入缓冲器存放产品。这样，生产者、消费 者都全部进入永久等待，并且这种等待永远不会结束。可见，P操作的次序很重要，需要认 真仔细斟酌。但V操作的顺序不会发生永久等待，只会影响效率，为什么？121? ? ??? ? ? ? ?（4）关于生产者/消费者的一个例题 实际工作中或日常生活中，生产者/消费者问题广泛存在。下面举一个例题。 【例2-10】桌子上只有一个空盘子，每次只能放一个水果。爸爸和妈妈（父 母）向盘子中放水果，如果父母放的是苹果，则儿子可以拿的去吃；如果父 母向盘子放的是桔子，则女儿可以拿去吃。试用信号量和PV操作机制实现父 母、儿子和女儿这三个进程的同步。 解答：该问题是一个日常生活问题，在操作系统内部很有用。本问题可以简 单改为：系统中有三个进程P1、P2和P3，P1进程产生整数，如果产生的是奇数， 则由P2 进程取出打印；若产生的是偶数，则有P3进程取出打印。这两个问题 虽然形式不同，但实质是一样的。 实际上该问题是生产者/消费者问题的一个变形。该问题中，有一个生产者 （父母），两个消费者（女儿、儿子）。对该问题可以建立三个信号量，分 别是sp（Parents），ss（son），sd(daught)。 sp：表示父母是否可以将水果放入盘子，一开始盘子是空的，显然sp的初值 为1，父母要放水果，需要对sp进行测试; ss: 表示盘子中苹果的个数，儿子要吃苹果，需要对ss进行测试。 sd：表示盘子中桔子的个数，女儿要吃桔子，需要对sd进行测试。 有了以上的分析，该问题的求解就变得很简单了。解法如下：122? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Semaphore sp=1,ss=0,sd=0; //下列进程并发执行 process parents(void) { while(1) { {准备一个水果（苹果或桔子）}; P(sp); if(水果是苹果) V(ss); else V(sd); } } process Son（void） ｛ while(1) ｛ P(ss); {从盘子中取苹果}; V(sp); {吃苹果}; ｝ ｝ process Daught（void） ｛ while(1) ｛ P(sd); {从盘子中取桔子}; V(sp); {吃桔子}; ｝ ｝//读者请思考：假如在该问题中，爸爸专门往盘子放苹果，妈妈专门往盘子中放桔子，本题应怎样求解？123? ??? ? ? ? ?2. 读者/写者问题 读者/写者问题（Reader/Writer Problem）是由Courtois等于1971年提出来的另一个经典的 进程同步问题，它为并发环境下访问一个文件或数据表的数据集建立了一个可以普遍适用的 模型，对目前广泛运用的多用户或分布式数据库具有直接意义。在读者/写者问题中，读者之 间是可以共享的，可以同时读一个数据集，而读者和写者、写者和写者之间应该不能同时对 数据集进行操作，否则会发生数据不一致现象。 读者/写者问题可以分成两种类型，即优先读者的读者/写者问题和优先写者的读者写者/问题。 对于优先读者的读者/写者问题的求解必须满足以下几个要求： （1）读者可以共享； （2）写者互斥； （3）除非已经有一个写者在访问共享数据集，其他情况下，读者不应该等待； （4）写者执行写操作前，应该让所有的读者和写者退出。 本问题的求解，对于写者来说，只要设置一个写者与写者之间、读者与写者之间共享的一个 信号量w即可，w的初值为1； 对于读者，需要特殊处理，要求对读者进行计数，因为，读者 对文件是可以共享的，对于第一个访问数据集的读者，需要对该数据集“加锁”，防止写者 对数据集进行访问，而其他读者则可以直接进入访问数据集；对于最后一个读者，需要“解 锁”，以便让写者或后面的读者能够访问数据集。由于读者需要计数，而这个读者的数目 ReadCnt对于读者来说是个共享变量，每个读者需要对该变量进行互斥访问，否则会发生与 时间有关的错误，因此，还需要一个对读者计数变量ReadCnt的互斥访问的信号量mutex， 初值为0。优先读者的读者/写者问题的算法设计如下：124? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?typedef int S Semaphore mutex=1,w=1; int ReadCnt=0; //下面读者和写者进程并发执行 process Reader（void） { while(1) { P(mutex); ReadCnt++; if (ReadCnt==1) P(w); V(Mutex); {对数据集进行读操作}; P(mutex); ReadCnt--; if (ReadCnt==0) V(w); V(mutex); ｝ process Writer(void) { while(1) { P(w); {对数据集进行写操作}; V(w)； } }125? 在上述算法中，如果一个写者在临界区中，有n个读者等待读数据集， 那么恰好有一个读者在信号量w上等待，其余n-1个读者在信号量 mutex上等待，在该写者在对数据集写入时，可能会有其他写者访问 数据集，这些其他的写者都在信号量w上等待，当执行写入的写者退 出临界区时，唤醒的可能是读者，也可能是写者，这和调度程序有关。 上述算法是优先读者的，当一个读者进入临界区读数据集时，假如后 面的读者源源不断时，写者就会长时间等待，甚至会被饿死。 ? 该问题的另一种求解就是优先写者，可以设定，当有一个写者提出想 写的要求后，就不允许有新的读者再进入临界区访问文件。优先写者 的读者/写者问题留为作业，希望本书读者在优先读者的基础上能够求 解出来。 ? 值得注意的是，读者/写者问题的变形。如有一个文件F，有两组读者 用户A和B，A组中的读者可以共享对F的读取，B组中的读者用户也 可以共享F的读取，但A组与B组之间的用户是不能对F的共享读取。 实际上，这个问题可以看做是一个“读者/读者”问题。126? 3. 哲学家就餐问题 ? 哲学家就餐问题是由Dijkstra于1965年提出并解决的一个经 典进程同步问题。该问题在进程的同步中影响很大，每个 学习并发进程的人员都对该问题很感兴趣，并且每个新设 计出的进程同步原语的计算机研究人员都希望通过试图解 决哲学家就餐问题来显示他们的同步原语的功能和性能。 ? 哲学家就餐问题是这样的：有五个哲学家，他们围坐在一 张圆桌旁。哲学家们生活非常简朴，他们除了思考问题， 就是吃面条）。由于哲学家生活很简朴，每个哲学家面前 有一只空盘子，每两个哲学家之间有一支筷子，共五支筷 子。我们知道，由于面条很滑，哲学家只有拿到两只筷子 才能够吃面条。因此，当一个哲学家思考饿了后，他就试 图去拿他最近的两支筷子，每次只允许拿一支，次序不限。 当他成功拿到两支筷子后，他就可以吃面条，吃完后，将 筷子放下，就继续思考。127? 根据上面对哲学家就餐问题的介绍，作个简单的分析。显然，在本问 题中，最多只有两个哲学家同时吃面，因此，该问题的最大并行度是 2。假如每个哲学家都拿起了一支筷子，而等待拿另一支筷子，这时， 每个哲学家都拿不到第二支筷子，因此，显然发生了永久等待（死 锁）。假设再规定，哲学家每次拿筷子，总是先拿左边的筷子，然后 再拿右边的筷子。这种情况下，仍然会发生死锁。这是因为，假如哲 学家们同时感到饥饿，同时拿起了左边筷子，都在等待拿右边的筷子。 再进一步，规定假设哲学家先拿起自己左边的筷子，当发现右边的筷 子不可用时，则马上放下自己左边的筷子。这种方案表面上看，很合 理，但是，会存在这样一种概率瞬间，假如所有的哲学家同时拿起左 筷子，都同时发现右边的筷子不可用，于是都放下左边的筷子，过一 段时间，又同时拿起左边筷子，如此这样，循环往复，这样所有的哲 学家都在做“无用功”，这样会被“饿死（长时间进程的要求得不到 满足）”。因此，哲学家就餐问题还是有点难度的。哲学家就餐问题 的解法有好几种。例如，对筷子编个号，如K1、K2、K3、K4、K5， 规定哲学家拿筷子时总是先拿编号小的筷子，然后再拿编号大的筷子， 这样可以解决哲学家问题。这种解法留给读者自己思考。下面介绍一 种能够保证最大并行度并且能够适应任意数目的哲学家就餐问题的解 法。该种解法的类C语言代码如下，根据注释读者不难看懂。128? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?typedef int S //定义信号量Semaphore类型是整型的别名 const int N=5; //定义哲学家