操作系统进程管理培训教学PPT

《操作系统进程管理培训教学PPT》由会员分享，可在线阅读，更多相关《操作系统进程管理培训教学PPT（223页珍藏版）》请在金锄头文库上搜索。

1、第第2章章 进程管理进程管理 2.1 进程的基本概念进程的基本概念2.2 进程控制进程控制2.3 进程同步进程同步2.4 经典进程同步问题经典进程同步问题2.5 管程机制管程机制 实现互斥的软件机制和硬件机制实现互斥的软件机制和硬件机制( (补充补充) )2.6 进程通信进程通信2.7 线程线程第一次课内上机实验第一次课内上机实验12.1 进程的基本概念进程的基本概念n程序的顺序执行及其特征程序的顺序执行及其特征n程序的并发执行及其特征程序的并发执行及其特征n进程的特征与状态进程的特征与状态n进程控制块进程控制块22.1.1 程序的顺序执行及其特征程序的顺序执行及其特征n程序的顺序执行程序的顺

2、序执行仅当前一操作仅当前一操作( (程序段程序段) )执行完后，才能执行后继操作。执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。据，然后进行计算，最后才能打印计算结果。 S1: a=S1: a=x+yx+y; ; S2: b=a-5; S2: b=a-5; S3: c=b+1; S3: c=b+1;32.1.1 程序的顺序执行及其特征程序的顺序执行及其特征顺序执行包含两层含义：顺序执行包含两层含义：l对于多个用户程序来说，所有程序是依次执对于多个用户程序来说，所有程序是依次执行的。（外

3、部顺序性）行的。（外部顺序性） l对于一个程序来说，它的所有指令是按序执对于一个程序来说，它的所有指令是按序执行的。（内部顺序性）行的。（内部顺序性）4n程序顺序执行的特征程序顺序执行的特征 （1）顺序性：）顺序性： 处理机的操作严格按照程序所规定的顺序执行，处理机的操作严格按照程序所规定的顺序执行，即每一操作必须在下一操作开始之前结束（或者即每一操作必须在下一操作开始之前结束（或者说下一操作必须在当前操作结束后才能开始）。说下一操作必须在当前操作结束后才能开始）。 （2）封闭性：）封闭性： 程序是在封闭的环境下执行的。即程序是在封闭的环境下执行的。即程序运行时独占全机资源，资源的状态（除初始

4、程序运行时独占全机资源，资源的状态（除初始态外）只有本程序才能改变它。态外）只有本程序才能改变它。程序一旦开始执行，其执行结果不受外界影响。程序一旦开始执行，其执行结果不受外界影响。 （3）可再现性：）可再现性： 只要程序执行时的环境和初始条件相同，当程只要程序执行时的环境和初始条件相同，当程序重复执行时，都将获得相同的结果。序重复执行时，都将获得相同的结果。 5程序的并发执行程序的并发执行包括两层含义：包括两层含义： l对于一个程序来说，它的所有指令是对于一个程序来说，它的所有指令是按序执行的。（内部顺序性）按序执行的。（内部顺序性） l对于多个程序（进程）来说，所有进对于多个程序（进程）来

5、说，所有进程是交叉执行的。（外部并发性）程是交叉执行的。（外部并发性） 2.1.3 程序的并发执行及其特征程序的并发执行及其特征 6n前趋图前趋图 前前趋趋图图(PrecedenceGraph)是是一一个个有有向向无无循循环环图图，记记为为DAG(DirectedAcyclicGraph)，用用于于描描述述进进程程之之间间执执行行的的前前后后关关系系。图图中中的的每每个个结结点点可可用用于于描描述述一一个个程程序序段段或或进进程程，乃乃至至一一条条语语句句；结结点点间间的的有有向向边边则则用用于于表表示示两两个个结结点点之之间间存存在在的的 偏偏 序序 (PartialOrder)或或 前前

6、趋趋 关关 系系 (PrecedenceRelation)“”。=(Pi,Pj)|PimustcompletebeforePjmaystart,如如果果(Pi,Pj),可可写写成成PiPj，称称Pi是是Pj的的直直接接前前趋趋，而而称称Pj是是Pi的的直直接接后后继继。在在前前趋趋图图中中，把把没没有有前前趋趋的的结结点点称称为为初初始始结结点点(Initial Node)，把把没没有有后后继继的的结结点点称称为为终终止止结结点点(FinalNode)。7n前趋图前趋图每每个个结结点点还还具具有有一一个个重重量量(Weight)，用用于于表表示示该该结结点点所含有的程序量或结点的执行时间。所含

7、有的程序量或结点的执行时间。IiCiPi和和S1S2S38n前趋图前趋图对于图对于图2-2(a)所示的前趋图，所示的前趋图，存在下述前趋关系：存在下述前趋关系：P1P2,P1P3,P1P4,P2P5,P3P5,P4P6,P4P7,P5P8,P6P8,P7P9,P8P9或表示为：或表示为：P=P1,P2,P3,P4,P5,P6,P7,P8,P9=(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)应应当当注注意意，前前趋趋图图中中必必须须不不存存在在循循环环，但但在在图图2-

8、2(b)中中却却有有着着下述的前趋下述的前趋关系：关系：S2S3,S3S29n前趋图前趋图 前前趋趋图图(PrecedenceGraph)是是一一个个有有向向无无循循环环图图，记记为为DAG(DirectedAcyclicGraph)，用用于于描描述述进进程程之之间间执执行行的的前前后后关关系系。图图中中的的每每个个结结点点可可用用于于描描述述一一个个程程序序段段或或进进程程，乃乃至至一一条条语语句句；结结点点间间的的有有向向边边则则用用于于表表示示两两个个结结点点之之间间存存在在的的 偏偏 序序 (PartialOrder)或或 前前 趋趋 关关 系系 (PrecedenceRelation

9、)“”。=(Pi,Pj)|PimustcompletebeforePjmaystart,如如果果(Pi,Pj),可可写写成成PiPj，称称Pi是是Pj的的直直接接前前趋趋，而而称称Pj是是Pi的的直直接接后后继继。在在前前趋趋图图中中，把把没没有有前前趋趋的的结结点点称称为为初初始始结结点点(Initial Node)，把把没没有有后后继继的的结结点点称称为为终终止止结结点点(FinalNode)。102.1.3 程序的并发执行及其特征程序的并发执行及其特征 图图2-3并发执行时的前趋图并发执行时的前趋图112.1.3 程序的并发执行及其特征程序的并发执行及其特征 在该例中存在下述前趋关系：在

10、该例中存在下述前趋关系：IiCi，IiIi+1,CiPi,CiCi+1，PiPi+1而而Ii+1和和Ci及及Pi-1是是重重迭迭的的，亦亦即即在在Pi-1和和Ci以以及及Ii+1之之间间，可可以并发执行。以并发执行。对于具有下述四条语句的程序段：对于具有下述四条语句的程序段：S1:a =x+2S2:b =y+4S3:c =a+bS4:d =c+b121）间断性）间断性: : 程序在并发执行时，由于它们共享系统资程序在并发执行时，由于它们共享系统资源，以及为完成同一任务而相互合作，致源，以及为完成同一任务而相互合作，致使这些并发执行的程序之间形成了相互制使这些并发执行的程序之间形成了相互制约的关

11、系。（互斥关系、同步关系）约的关系。（互斥关系、同步关系） 相互制约导致并发执行的程序具有相互制约导致并发执行的程序具有“执行执行暂停暂停执行执行”这种间断性活动规律。这种间断性活动规律。 2）失去封闭性：）失去封闭性： 程序在并发执行时，由于多个程序在并发执行时，由于多个程序共享系统资源，因而这些程序共享系统资源，因而这些资源的状态将由多个程序来改资源的状态将由多个程序来改变，致使程序的运行已失去了变，致使程序的运行已失去了封闭性。封闭性。 某程序的执行时，某程序的执行时，会受到其他程序的会受到其他程序的影响。影响。 133）不可再现性）不可再现性与时间有关的错误与时间有关的错误 程序在并发

12、执行时，由于失去了封闭性，也将导致程序在并发执行时，由于失去了封闭性，也将导致其失去可再现性。其失去可再现性。例如例如：有两个循环程序：有两个循环程序A A和和B B，它们共享一个变量，它们共享一个变量N NL1：N=N+1；gotoL1； L2：print(N)；N=0；gotoL2； 程程序序A程程序序B程序程序A和和B并发执行时，可能出现下述三种情况并发执行时，可能出现下述三种情况(设设N的值为的值为10)：(1)N=N+1在在print(N)和和N=0之前，此时得到的之前，此时得到的N值分别为值分别为11,11,0。(2)N=N+1在在print(N)和和N=0之后，此时得到的之后，此

13、时得到的N值分别为值分别为10,0,1。(3)N=N+1在在print(N)和和N=0之间，此时得到的之间，此时得到的N值分别为值分别为10,11,0。 上述三种情况中，上述三种情况中，(1)(1)、(2)(2)结果正确，结果正确，(3)(3)结果出错。可见计算结果已与并结果出错。可见计算结果已与并发程序的执行速度发程序的执行速度( (推进速度推进速度) )有关，从而使程序执行失去了可再现性。有关，从而使程序执行失去了可再现性。 142.1.4 进程的特征与状态进程的特征与状态1进程的定义和特征进程的定义和特征 进程是程序在一个数据集上的运行过程，是系进程是程序在一个数据集上的运行过程，是系统

14、进行资源分配和调度的一个独立单位。统进行资源分配和调度的一个独立单位。 (传传统统OS的定义的定义)定定义义(1) (1) 进程是程序的一次执行。进程是程序的一次执行。(2) (2) 进进程程是是一一个个程程序序及及其其数数据据在在处处理理机机上上顺顺序序执行时所发生的活动。执行时所发生的活动。(3)(3)进进程程是是进进程程实实体体的的运运行行过过程程，是是系系统统进进行行资资源分配和调度的一个独立单位源分配和调度的一个独立单位”。 其其他他15为了描述和控制进程的运行，系统为每个进程定义了为了描述和控制进程的运行，系统为每个进程定义了一个数据结构一个数据结构进程控制块。进程控制块。进程控制

15、块是进程实体的一部分，是操作系统中最重进程控制块是进程实体的一部分，是操作系统中最重要的记录型数据结构。要的记录型数据结构。 1.PCB作用：作用：使使一一个个在在多多道道程程序序环环境境下下不不能能独独立立运运行行的的程程序序( (含含数数据据) )，成成为为一一个个能能独独立立运运行行的的基基本本单单位位，一一个个能能与与其其它它进进程程并并发发执执行行的的进进程程。或或者者说说，OS是是根根据据PCB来来对对并并发发进进程程进进行行控控制和管理的。制和管理的。 例如：进程调度；现场保护和恢复；进程同步和通例如：进程调度；现场保护和恢复；进程同步和通信。信。PCB是进程存在的唯一标志是进程

16、存在的唯一标志2.1.5 进程控制块（进程控制块（PCB） 162进程控制块中的信息进程控制块中的信息PCB中记录了操作系统所需的、用于描述进程当前情中记录了操作系统所需的、用于描述进程当前情况以及控制进程运行的全部信息。具体包括下述四方况以及控制进程运行的全部信息。具体包括下述四方面的信息：面的信息： 1）进程标识符：）进程标识符： 内部标识符内部标识符( (进程号进程号) )；外部标识符外部标识符( (名名) )；父进程标识及子进程标识；用户标识父进程标识及子进程标识；用户标识 2）处理机状态：）处理机状态： 处理机状态信息主要由处理机的各种寄存处理机状态信息主要由处理机的各种寄存器中的内

17、容组成的。寄存器包括：通用寄器中的内容组成的。寄存器包括：通用寄存器、指令计数器、程序状态字（存器、指令计数器、程序状态字（PSWPSW）寄存器、用户栈指针。寄存器、用户栈指针。( (保护、恢复现场保护、恢复现场) )当处理机被中断时，这些信息都必须保存到当处理机被中断时，这些信息都必须保存到PCB中，以便中，以便该进程重新执行时，能从断点继续执行。该进程重新执行时，能从断点继续执行。 173）进程调度信息）进程调度信息：在在PCB中还存放一些与中还存放一些与进程调度进程调度和进程对换有关的信息。包括：和进程对换有关的信息。包括： 进程状态进程状态作为调度和对换时的依据。作为调度和对换时的依据

18、。 进程优先级进程优先级由于描述进程使用处理机的优先由于描述进程使用处理机的优先级别的一个整数，优先级高的进程优先获得处理级别的一个整数，优先级高的进程优先获得处理机。机。 进程调度所需的其它信息进程调度所需的其它信息它们与所采用的进它们与所采用的进程调度算法有关。程调度算法有关。 事件事件即阻塞原因。即阻塞原因。 184）进程控制信息：）进程控制信息： l程序和数据的地址程序和数据的地址指程序和数据所在的内存指程序和数据所在的内存或外存首地址；或外存首地址； l进程同步和通信机制进程同步和通信机制如信号量、消息队列指如信号量、消息队列指针等，它们可能全部或部分地存放在针等，它们可能全部或部分

19、地存放在PCB中；中； l资源清单资源清单是一张列出了除是一张列出了除CPU外的、进程所外的、进程所需的全部资源及已经分配到该进程的资源的清单；需的全部资源及已经分配到该进程的资源的清单； l链接指针链接指针它给出本进程（它给出本进程（PCB）所在队列中）所在队列中下一个进程的下一个进程的PCB的首址。的首址。 193进程控制块的组织方式进程控制块的组织方式常用的组织方式有两种：常用的组织方式有两种：链接方式链接方式和和索引方式索引方式。 1）链接方式）链接方式 把具有同一状态的把具有同一状态的PCB，用其中的链，用其中的链接字链接成一个队接字链接成一个队列。形成：列。形成：就绪队就绪队列列、

20、阻塞队列阻塞队列、空空白队列白队列等等 202）索引方式）索引方式: : 系统根据所有进程系统根据所有进程的状态建立几张索的状态建立几张索引表。如，引表。如， 就绪索引表就绪索引表 阻塞索引表等阻塞索引表等 索引表的首址记录在索引表的首址记录在专用单元中；专用单元中；每个索引表的表目中，每个索引表的表目中，记录具有相应状态的某记录具有相应状态的某个个PCBPCB的首址。的首址。 212.1.4 进程的特征与状态进程的特征与状态1进程的特征进程的特征1）结构特征：）结构特征： 程序段、相关的数据段、程序段、相关的数据段、PCB三三部分构成了部分构成了进程实体进程实体。 2）动态性：）动态性：进程

21、的实质是进程实体的一次执行过进程的实质是进程实体的一次执行过程，故程，故动态性是进程的最基本特征动态性是进程的最基本特征。 224）独立性）独立性 ：在在传传统统的的OS中中，独独立立性性是是指指进进程程实实体体是是一一个个能能独独立立运运行行、独独立立分分配配资资源和独立接受调度的基本单位。源和独立接受调度的基本单位。 5）异步性）异步性 ： 是指进程按各自独立的、不可预知的是指进程按各自独立的、不可预知的速度向前推进，或说进程实体按异步速度向前推进，或说进程实体按异步方式运行。方式运行。 3）并发性：）并发性： 这是指多个进程实体同存于内存这是指多个进程实体同存于内存中，且能在一段时间内同

22、时运行。中，且能在一段时间内同时运行。 23进程的三种基本状态：进程的三种基本状态： 1）就绪（）就绪（Ready）状态：）状态： 当进程已分配到除当进程已分配到除CPU以外的所有资源后，只要再获以外的所有资源后，只要再获得得CPU，便可立即执行，进程这时的状态称为就绪状，便可立即执行，进程这时的状态称为就绪状态。态。 2）执行（）执行（Running）状态）状态: : 进程已获得进程已获得CPU，其程序正在执行，其程序正在执行。 3）阻塞（）阻塞（Blocked）状态）状态: : 正在执行的进程由于发生某事件而暂时无法继续执行正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处

23、于暂停状态，亦即进程的执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状态（或等待状受到阻塞，把这种暂停状态称为阻塞状态（或等待状态）态）。 24进程的三种基本状态的转换：进程的三种基本状态的转换：进程调度进程调度：就绪态：就绪态执行态执行态时间片完时间片完：执行态：执行态就绪态就绪态请求请求I/O：执行态：执行态阻塞态阻塞态I/O完成完成：阻塞态：阻塞态就绪态就绪态 引起进程状态转换的典型事件：引起进程状态转换的典型事件：25挂起状态挂起状态：有些系统除了进程的三种基有些系统除了进程的三种基本状态外，还有挂起状态本状态外，还有挂起状态。1）引入挂起状态的原因

24、引入挂起状态的原因： （1）终端用户的请求：）终端用户的请求： （2）父进程请求：）父进程请求：（3）负荷调节的需要）负荷调节的需要 ： （4）操作系统的需要）操作系统的需要 ： 当当终端用户在自己的程序运行期间发终端用户在自己的程序运行期间发现有可疑问题时，希望暂停执行。现有可疑问题时，希望暂停执行。希望考察和修改子进程，或协调各希望考察和修改子进程，或协调各子进程间的活动时子进程间的活动时实时系统中工作负荷较重时，系统实时系统中工作负荷较重时，系统可把一些不重要的进程挂起。可把一些不重要的进程挂起。操操作作系系统统有有时时希希望望挂挂起起某某些些进进程程，以以便便检检查查运运行行中中的的资

25、资源源使使用用情情况况或或进行记账。进行记账。262 2）具有）具有挂起状态系统的挂起状态系统的进程状态的转换进程状态的转换 活动就绪活动就绪静止就绪静止就绪 活动阻塞活动阻塞静止阻塞静止阻塞 静止就绪静止就绪活动就绪活动就绪 静止阻塞静止阻塞活动阻塞活动阻塞挂起原语挂起原语Suspend激活原语激活原语Active27创建状态创建状态创建一个进程一般包括两个步骤：创建一个进程一般包括两个步骤： 1)1)为一个新进程创建为一个新进程创建PCB,PCB,并填写必要的管理信息。并填写必要的管理信息。2 2）把该进程转入就绪状态并插入到就绪队列中。）把该进程转入就绪状态并插入到就绪队列中。 当一个新

26、进程被创建时，系统已经为其分配了当一个新进程被创建时，系统已经为其分配了PCB,PCB,填写了进程标识等信息，但是由于该进程所必须填写了进程标识等信息，但是由于该进程所必须的资源或其他信息如主存资源等尚未分配，此时的的资源或其他信息如主存资源等尚未分配，此时的进进程已经拥有了自己的程已经拥有了自己的PCB,PCB,但进程自身还未进入主存，但进程自身还未进入主存，即进程创建工作尚未完成，进程不能被调度执行，其即进程创建工作尚未完成，进程不能被调度执行，其所处的状态就是创建状态所处的状态就是创建状态。28终止状态终止状态终止一个进程一般包括两个步骤：终止一个进程一般包括两个步骤： 当一个进程到达了

27、自然结束点，或是出现了无法克服当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。的进程所终结，它将进入终止状态。 进入终止状态的进程以后不能执行，但在操作系统中进入终止状态的进程以后不能执行，但在操作系统中依然保留一个记录，其中保存状态码和一些计时统计数依然保留一个记录，其中保存状态码和一些计时统计数据，供其他进程收集。一旦其他进程完成了对终止状态据，供其他进程收集。一旦其他进程完成了对终止状态进程的信息提取之后，操作系统将删除该进程。进程的信息提取之后，操作系统将删除该

28、进程。1) 1) 回收资源回收资源2 2）删除）删除PCBPCB 29终止状态终止状态图2-2 具有创建、终止和挂起状态的进程状态图 302.2 进程控制进程控制v进程控制是进程管理中最基本的功能。进程控制是进程管理中最基本的功能。 v进程控制包括：进程控制包括： 创建进程创建进程 终止进程终止进程 进程状态转换进程状态转换 v进程控制是由进程控制是由OS的内核完成的。的内核完成的。 312.2.1 进程的创建进程的创建1引起创建进程的事件引起创建进程的事件 用户登录用户登录 作业调度作业调度 提供服务提供服务当当用用户户进进程程提提出出某某种种请请求求后后，系系统统将将专专门门创创建建一一个

29、个进进程程来来提提供供用用户户所所需需的的服服务。如，文件打印。务。如，文件打印。 上述三种情况，都是由系统内核上述三种情况，都是由系统内核为它创建一个新进程。为它创建一个新进程。 应用请求：应用请求： 是基于应用进程的需求，由应用进是基于应用进程的需求，由应用进程自己创建一个新进程，以便新进程自己创建一个新进程，以便新进程以并发运行方式完成特定任务。程以并发运行方式完成特定任务。 322.2.1 进程的创建进程的创建图 2-4 进程树 332进程的创建进程的创建 调用进程创建原语调用进程创建原语Create（），按下述步骤创建一个进程：（），按下述步骤创建一个进程： （1）申请空白）申请空白

30、PCB；（2）为新进程分配资源。主要是内存空间。）为新进程分配资源。主要是内存空间。 （3）初始化）初始化PCB。包括：。包括： 初始化标识信息初始化标识信息 初始化处理机状态信息：初始化处理机状态信息： 程序计数器，堆栈指针等程序计数器，堆栈指针等进程状态进程状态就绪或静止就绪或静止就绪、优先级等。就绪、优先级等。初始化处理机控制信息：初始化处理机控制信息：（4）将新进程插入就绪队列）将新进程插入就绪队列。 341引起进程终止的事件引起进程终止的事件 正常结束正常结束外界干预外界干预 l越界错误越界错误l保保护护错错试试图图访访问问不不允允许许访访问问的的资资源或文件，或者以不适当方式访问源

31、或文件，或者以不适当方式访问l非法指令非法指令l特特权权指指令令错错用用户户程程序序试试图图执执行行只只允许允许OS执行的指令执行的指令l运行超时运行超时l等待超时等待超时l算术运算错算术运算错被被0除除lI/O故障故障 操作员或操作系统干操作员或操作系统干 预（如发生死锁）预（如发生死锁） 父进程请求父进程请求 父进程终止父进程终止 2.2.2 进程的终止进程的终止异常结束异常结束 常见的异常常见的异常 结束事件结束事件352进程的终止过程进程的终止过程 OSOS调用终止原语，按下述过程终止进程：调用终止原语，按下述过程终止进程：(1)根根据据被被终终止止进进程程的的标标识识，从从PCB集集

32、合合中中找找除除该该进进程程的的PCB，读出该进程状态。，读出该进程状态。(2)若若被被终终止止进进程程正正处处于于执执行行状状态态，应应立立即即终终止止其其执执行行，并并置置调调度度标标志志为为真真，用用于于指指示示该该进进程程被被终终止止后后应应重重新新进进行行调调度度。若若该该进进程程还还有有子子孙孙进进程程，应应将将其其所所有有子子孙孙进进程程终终止，以防止它们成为不可控进程。止，以防止它们成为不可控进程。(3)将将被被终终止止进进程程的的所所有有资资源源，或或者者归归还还给给其其父父进进程程，或或者者归还给系统。归还给系统。(4)将将被被终终止止进进程程（它它的的PCB）从从所所在在

33、队队列列中中移移出出，等等待待其其他进程来搜索信息。他进程来搜索信息。362.2.2 进程的阻塞和唤醒进程的阻塞和唤醒1引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件 请求系统服务请求系统服务无新工作可做无新工作可做 当当执执行行进进程程请请求求OS服服务务时时，由由于于某某种种原原因因，OS并并不不立立即即满满足足该该进进程程的的请请求求时时，该该进进程程只只能能转转变变为为阻阻塞塞状状态态来等待。来等待。如，进程请求打印机，如，进程请求打印机， 系系统统往往往往设设置置一一些些具具有有特特定定功功能能的的系系统统进进程程，每每当当这这种种进进程程完完成成任任务务后后，便便把把自己阻塞起来

34、以等待新任务到来。自己阻塞起来以等待新任务到来。如，系统中发送数据的进程，如，系统中发送数据的进程， 启动某种操作启动某种操作 当当进进程程启启动动某某种种操操作作后后，如如果果该该进进程程必必须须在在该该操操作作完完成成后后才才能能继继续续执执行行，则则必必须须先先使使该该进进程程阻阻塞塞，以以等等待待操操作作完成。完成。如，启动了某如，启动了某I/O设备，设备， 新数据尚未到达新数据尚未到达 对对于于相相互互合合作作的的进进程程，如如果果其其中中一一个个进进程程需需要要获获得得另另一一个个（合合作作）进进程程提提供供的的数数据据才才能能运运行行以以对对数数据据进进行行处处理理，则则只只要要

35、其其所所需需数数据据尚尚未未到到达达，该该进进程程只只有有阻阻塞塞（等等待）。待）。如，如， 372进程阻塞过程进程阻塞过程 调用阻塞原语调用阻塞原语block把自己阻塞。（主动行为）把自己阻塞。（主动行为）阻塞（阻塞（blockblock）过程：）过程： u立即停止执行；立即停止执行；u把把PCBPCB中进程状态由中进程状态由“执行执行”改为改为“阻塞阻塞”； u将将PCBPCB插入具有相同事件的阻塞队列；插入具有相同事件的阻塞队列； u转进程调度程序，将处理机分配给某个就绪转进程调度程序，将处理机分配给某个就绪进程，并进行进程切换进程，并进行进程切换保留被阻塞进程保留被阻塞进程的处理机状态

36、（在的处理机状态（在PCBPCB中），再按新进程的中），再按新进程的PCBPCB中处理机状态设置中处理机状态设置CPUCPU的环境。的环境。 383进程唤醒过程进程唤醒过程 调用唤醒原语调用唤醒原语wakeup( )( )，将等待事件的进程唤醒。，将等待事件的进程唤醒。 唤醒原语执行过程唤醒原语执行过程： 将被唤醒进程的将被唤醒进程的PCBPCB从阻塞队列移出；从阻塞队列移出； 将其将其PCBPCB中进程状态由中进程状态由“阻塞阻塞”改为改为“就绪就绪”； 将改将改PCBPCB插入到就绪队列中。插入到就绪队列中。block（）和（）和wakeup（）是成对的。（）是成对的。 391进程的挂起进

37、程的挂起 当出现了引起进程挂起的事件时当出现了引起进程挂起的事件时( (用户进程请求将自己挂起，用户进程请求将自己挂起，或父进程请求将子进程挂起或父进程请求将子进程挂起) )，系统将用挂起原语，系统将用挂起原语suspend( )suspend( )将指定进程或处于阻塞状态的进程挂起。将指定进程或处于阻塞状态的进程挂起。 挂起原语的执行过程：挂起原语的执行过程： 检查被挂起进程的状态：检查被挂起进程的状态： 若处于活动就绪或执行状态，则将其转若处于活动就绪或执行状态，则将其转为静止就绪；为静止就绪；若处于活动阻塞若处于活动阻塞, ,则将其转为静止阻塞则将其转为静止阻塞 把该进程的把该进程的PC

38、B复制到某指定内存区域复制到某指定内存区域 为方便用户或父进程考为方便用户或父进程考查该进程的运行状态。查该进程的运行状态。 若该进程正在执行，则转进程调度程序重新调度。若该进程正在执行，则转进程调度程序重新调度。 2.2.4进程的挂起和激活进程的挂起和激活402进程的激活进程的激活 当当发发生生激激活活进进程程的的事事件件时时( (如如父父进进程程或或用用户户请请求求激激活活指指定定进进程程，而而内内存存中中已已有有足足够够空空间间时时) )，系系统统利利用用激激活活原原语语active( active( ) )将将指定进程激活。指定进程激活。 激活过程是：激活过程是： 将进程从外存调入内存

39、；将进程从外存调入内存； 若是静止就绪，则改为活动就绪；若是静止就绪，则改为活动就绪； 若是静止阻塞，则改为活动阻塞。若是静止阻塞，则改为活动阻塞。 若采用的是抢占式调度策略，则应检查被激活就绪进程若采用的是抢占式调度策略，则应检查被激活就绪进程的优先级，若其优先级比先行执行进程高，则应将处理机的优先级，若其优先级比先行执行进程高，则应将处理机分配给被激活进程。分配给被激活进程。 检查该进程现行状态：检查该进程现行状态： 412.3 进程同步进程同步n由由于于进进程程的的异异步步性性，尤尤其其是是它它们们竞竞争争临临界界资资源源时时，可能会给系统造成混乱。可能会给系统造成混乱。n进进程程同同步

40、步的的主主要要任任务务，是是使使并并发发执执行行的的进进程程之之间间能能有有效效地地共共享享资资源源和和相相互互合合作作，从从而而使使程程序序的的执执行行具具有可再现性。有可再现性。 2.3.1进程同步的基本概念进程同步的基本概念2.3.2信号量机制信号量机制2.3.3信号量的应用信号量的应用422.3.1 进程同步的基本概念进程同步的基本概念1两种形式的制约关系两种形式的制约关系 （1）间接制约关系）间接制约关系 间接制约关系源于资源共享。间接制约关系源于资源共享。如，共享打印机。如，共享打印机。 进程互斥进程互斥（2）直接制约关系）直接制约关系 源于进程间的合作。如，源于进程间的合作。如，

41、 进程同步进程同步2临界资源临界资源 在一段时间内只允许一个进程访问的资在一段时间内只允许一个进程访问的资源，即仅当一个进程访问完并释放该资源，即仅当一个进程访问完并释放该资源后，才允许另一个进程访问的资源，源后，才允许另一个进程访问的资源，称为临界资源或独占资源。称为临界资源或独占资源。 如，打印机、磁带机、共享变量、队列、如，打印机、磁带机、共享变量、队列、 43生产者生产者- -消费者问题消费者问题【例例】生产者生产者- -消费者问题消费者问题著名的进程同步问题著名的进程同步问题 共享变量：共享变量：临界资源临界资源循环缓冲区循环缓冲区生产者投放一个产品后，输入指针生产者投放一个产品后，

42、输入指针in加加1：in = ( in + 1 ) % n （n是缓冲区个数，整型是缓冲区个数，整型常量），常量），in初值为初值为0； 消费者每取出一个产品，输出指针消费者每取出一个产品，输出指针out加加1：out = ( out + 1 ) % n，out初值为初值为0； 引入一个引入一个共享共享变量变量counter, ,初值为初值为0。生产者投放一个产品，生产者投放一个产品，counter加加1，counter = n时不能再投放产品时不能再投放产品 消费者每取一个产品，消费者每取一个产品，counter减减1，counter = 0时不能再取出产品时不能再取出产品 前面交通观察前面

43、交通观察站例子亦然。站例子亦然。以下是软件临界资源的例子。以下是软件临界资源的例子。44process producer：while（condition）produceaniteminnextp；while(counter=n)no-op；/no-op表示空操作表示空操作bufferin=nextp；in=(in+1)%n；counter=counter+1；生产者进程算法如下：生产者进程算法如下：45process consumer：structitemnextc；while（condition）while（counter=0）no-op；nextc=bufferout；out=（out+1

44、）%n；counter=counter1；consumetheiteminnextc；消费者进程算法如下：消费者进程算法如下：46上上面面的的生生产产者者程程序序和和消消费费者者程程序序，在在顺顺序序执执行行时时其其结结果果是是正正确确的的。但但若若并并发发执执行行时时，可可能能会会出出现现差差错错，问问题题在在于于这这两两个个进进程程共共享享变变量量counter。生生产产者者做做counter=counter+1操操 作作 ， 消消 费费 者者 做做 counter=counter-1操操作作，这这两两个个操操作作在在机机器器语语言言实实现现时时，常常可用下面的形式描述：可用下面的形式描述

45、：生产者执行的操作：生产者执行的操作：register1=counter；register1=register1+1;counter=register1；消费者执行的操作：消费者执行的操作： register2=counter；register2=register2-1；counter=register2； 47假设某一时刻假设某一时刻counter的值为的值为5，生产者和消费者同时对，生产者和消费者同时对counter操作，按下述顺序执行：操作，按下述顺序执行：register1=counter;(生产者取得生产者取得counter的当前值为的当前值为5)register1=register

46、1+1;(生产者将该值增生产者将该值增1变为变为6)register2=counter;(消费者取得消费者取得counter的当前值为的当前值为5)register2=register21;(消费者将该值减消费者将该值减1变为变为4)counter=register2;(消费者保存消费者保存counter的新值的新值4)counter=register1;(生产者保存生产者保存counter的新值的新值6)最终最终counter的值为的值为6，正确的值应是，正确的值应是5，出现了差错。，出现了差错。学生考虑学生考虑：什么情况会出现什么情况会出现counter最终值为最终值为4的情况。的情况。解

47、决此问题的关键，是应将变量解决此问题的关键，是应将变量counter作为临界资作为临界资源处理，亦即让生产者进程和消费者进程互斥地访问源处理，亦即让生产者进程和消费者进程互斥地访问变量变量counter。482.3.1 进程同步的基本概念进程同步的基本概念3临界区（临界区（critical section） 每个进程中访问临界资源的那段代码称为临界区。每个进程中访问临界资源的那段代码称为临界区。 不不论论是是硬硬件件临临界界资资源源，还还是是软软件件临临界界资资源源，多多个个进进程程必必须须互互斥斥地地对它们访问。对它们访问。 显显然然，若若能能保保证证诸诸进进程程互互斥斥地地进进入入自自己己

48、的的临临界界区区，便便可可实实现现诸诸进进程程对对临临界界区区的的互互斥斥访访问问。为为此此，每每个个进进程程在在进进入入临临界界区区之之前前，应应先先对对欲欲访访问问的的临临界界资资源源进进行行检检查查，看看是是否否正正被被访访问问，如如果果此此刻刻该该资资源源未未被被访访问问，便便可可进进入入临临界界区区对对该该临临界界资资源源进进行行访访问问，并并设设置置它它正正被被访访问问的的标标志志；如如果果此此刻刻它它正正被被访访问问，则本进程不能进入临界区。则本进程不能进入临界区。 定义：定义：进程互斥的定义：进程互斥的定义：进程互斥进程互斥不允许两个或两个以上进不允许两个或两个以上进程同时访问

49、同一个临界资源。程同时访问同一个临界资源。进程互斥进程互斥不允许两个或两个以上进不允许两个或两个以上进程同时进入程同时进入相关临界区相关临界区。49u因因此此必必须须在在临临界界区区前前增增加加一一段段用用于于上上述述检检查查的的代代码，把这段代码称为码，把这段代码称为进入区进入区(entrysection)u相相应应地地，在在临临界界区区后后面面也也要要加加上上一一段段称称为为退退出出区区(exitsection)的的代代码码，用用于于将将临临界界区区正正被被访访问问的的标志恢复为未被访问的标志。标志恢复为未被访问的标志。 repeat非临界区非临界区进入区进入区临界区临界区退出区退出区非临

50、界区非临界区untilfalse一一般般结结构构“进进 入入 区区 ”和和“退退 出出 区区 ”的的不不同同构构成成方方法法，形形成成了了各各种种不不同的同的同步机制同步机制。504同步机制应遵循的原则同步机制应遵循的原则 为了实现各进程互斥地进入自己的临界区，一为了实现各进程互斥地进入自己的临界区，一般是在系统中设置专门的同步机制来协调各进程般是在系统中设置专门的同步机制来协调各进程间的运行。间的运行。 我我们们把把异异步步环环境境下下的的一一组组并并发发进进程程因因直直接接制制约约而而互互相相发发送送消消息息、进进行行互互相相合合作作、互互相相等等待待，使使得得各各进进程程按按一一定定的的

51、速速度度执执行行的的过过程程称称为为进进程程间间的的同同步步。具具有有同同步步关关系系的的一一组组并并发发进进程程称称为为合合作作进进程程，合合作作进进程程间间互互相相发发送送的的信信号号称称为为消消息息或或事事件。件。514同步机制应遵循的原则同步机制应遵循的原则 所有同步机制都应遵循如下四条准则：所有同步机制都应遵循如下四条准则： 空闲让进空闲让进 当当无无进进程程处处于于临临界界区区时时，表表明明临临界界资资源源处处于于空空闲闲状状态态，应应允允许许一一个个请请求求进进入入临临界界区区的的进进程程立立即即进进入入自自己己的的临临界界区区，以以便便有有效效地利用临界资源。地利用临界资源。空

52、闲让进、忙则等待、有限等待、让权等待。空闲让进、忙则等待、有限等待、让权等待。52有限等待有限等待让权等待让权等待对要求访问临界资源的进程，应保证在有对要求访问临界资源的进程，应保证在有限的时间内能进入自己的临界区，以免陷限的时间内能进入自己的临界区，以免陷入入“死锁死锁”状态。状态。不死等不死等。不互相阻塞不互相阻塞。当进程不能进入自己的临界区时，应立即当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入释放处理机，以免进程陷入“忙等忙等”。不忙碌等待不忙碌等待。忙则等待忙则等待 当已有进程进入临界区时，表明临界资源当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界

53、区的正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的进程必须等待，以保证对临界资源的互斥互斥访问访问。532.3.2 信号量机制信号量机制信号量信号量(Semaphores)机制是一种卓有成效的进程同机制是一种卓有成效的进程同步工具。信号量机制已被广泛应用于单处理机和多步工具。信号量机制已被广泛应用于单处理机和多处理机系统以及计算机网络中。处理机系统以及计算机网络中。信号量机制的发展：信号量机制的发展：整型信号量整型信号量 记录型信号量记录型信号量 AND型信号量型信号量信号量集信号量集 ( (重点介绍重点介绍) ) 541、整型信号量、整型信号量 最最初初由由Dijkst

54、ra把把整整型型信信号号量量定定义义为为一一个个整整型型量量，除除初初始始化化外外，仅仅能能通通过过两两个个标标准准的的原原子子操操作作(Atomic Operation) wait(S)和和signal(S)来来访访问问。这这两两个个操操作作一一直直被被分分别别称称为为P、V操操作作。wait和和signal操作可描述为：操作可描述为： wait(S):whileS0dono-opS:=S-1;signal(S):S:=S+1;551、整型信号量、整型信号量 最最初初由由Dijkstra把把整整型型信信号号量量定定义义为为一一个个整整型型量量，除除初初始始化化外外，仅仅能能通通过过两两个个标

55、标准准的的原原子子操操作作(Atomic Operation) wait(S)和和signal(S)来来访访问问。这这两两个个操操作作一一直直被被分分别别称称为为P、V操操作作。wait和和signal操作可描述为：操作可描述为： wait(S):whileS0dono-opS:=S-1;signal(S):S:=S+1;56process producer：while（condition）produceaniteminnextp；while(counter=n)no-op；/no-op表示空操作表示空操作bufferin=nextp；in=(in+1)%n；wait(s);counter=c

56、ounter+1；signal(s);生产者进程算法如下生产者进程算法如下(加入整型信号量）：加入整型信号量）：57process consumer：structitemnextc；while（condition）while（counter=0）no-op；nextc=bufferout；out=（out+1）%n；wait(s);counter=counter1；signal(s);consumetheiteminnextc；消费者进程算法如下（加入整型信号量）：消费者进程算法如下（加入整型信号量）：581、整型信号量、整型信号量 最最初初由由Dijkstra把把整整型型信信号号量量定定义义

57、为为一一个个整整型型量量，除除初初始始化化外外，仅仅能能通通过过两两个个标标准准的的原原子子操操作作(Atomic Operation) wait(S)和和signal(S)来来访访问问。这这两两个个操操作作一一直直被被分分别别称称为为P、V操操作作。wait和和signal操作可描述为：操作可描述为： wait(S):whileS0dono-opS:=S-1;signal(S):S:=S+1;“忙等忙等”，未遵循，未遵循“让权等待让权等待”准则准则592、记录型信号量、记录型信号量 需需要要一一个个用用于于代代表表临临界界资资源源数数目目的的整整型型变变量量value；还还要要一一个个在在该

58、该资资源源上上阻阻塞塞的的队队列列（链链表表）指指针针L。故故信信号号量量应应采采用用记记录录型型（C语语言言中中为为结结构构型型）的结构：的结构：structsemaphoreintvalue；structsemphore*L；记录型信号量记录型信号量的结构定义的结构定义信信号号量量除除初初始始化化外外，只只能能通通过过两两个个原原子子操操作作(称称为为原原语语)wait(S)和和signal(S)来来访访问问。它它们们以以前前被被称称为为P、V操操 作作 。 下下 页页 介介 绍绍 wait和和signal操作。操作。60wait和和signal操作可用操作可用C/C+语言描述如下：语言描

59、述如下：voidwait(semaphoreS)S.value=S.value1;if(S.value0)block(S.L);/*让权等待让权等待*/voidsignal(semaphoreS)S.value=S.value+1;if(S.value=0)wakeup(S.L);/*唤醒第一个等待的进程唤醒第一个等待的进程*/P(S)V(S)S.value的初值表示系统的初值表示系统中某类资源的数目。中某类资源的数目。61wait和和signal操作的物理意义：操作的物理意义：对对信信号号量量S的的每每次次wait操操作作，意意味味着着进进程程请请求求一一个个该该类类临临界界资资源源，因因此

60、此描描述述为为S.value=S.value-1；当当S.value=1&.&Sn=1thenfori=1tondoSi=Si-1;else进程进入第一个满足进程进入第一个满足Si=t1&.&Sn=tnthenfori=1tondoSi=Si-di;else进程进入第一个遇到的满足进程进入第一个遇到的满足Siti条件的条件的Si信号信号量队列等待，同时将该进程的程序计数器地量队列等待，同时将该进程的程序计数器地址回退，置为址回退，置为Swait操作处。操作处。Ssignal(S1,d1,S2,d2,.,Sn,dn)fori=1tondoSi=Si+di;从所有从所有Si等待队列中移出进程并置入

61、就绪队列。等待队列中移出进程并置入就绪队列。664、信号量集、信号量集一般一般“信号量集信号量集”的几种特殊情况：的几种特殊情况：(1)Swait(S,d,d)。此此时时在在信信号号量量集集中中只只有有一一个个信信号号量量S，但但允允许许它它每每次次申申请请d个个资资源源，当当现现有有资资源源数数少于少于d时，不予分配。时，不予分配。(2)Swait(S,1,1)。此此时时的的信信号号量量集集已已蜕蜕化化为为一一般般的的记记录录型型信信号号量量(S1时时)或或互互斥斥信信号号量量(S=1时时)。(3)Swait(S,1,0)。这这是是一一种种很很特特殊殊且且很很有有用用的的信信号号量量操操作作

62、。当当S1时时，允允许许多多个个进进程程进进入入某某特特定定区区；当当S变变为为0后后，将将阻阻止止任任何何进进程程进进入入特特定定区区。换换言言之之，它相当于一个可控开关。它相当于一个可控开关。672.3.3 信号量的应用信号量的应用1 1利用信号量实现进程互斥利用信号量实现进程互斥 方法要点：方法要点： n为为每每个个临临界界资资源源设设置置一一个个互互斥斥信信号号量量mutex，其其初值为初值为1 1；n各各进进程程访访问问该该资资源源前前执执行行wait(mutex)操操作作，离离开开临临界界区区时时执执行行signal(mutex)操作。操作。请看下页的例子请看下页的例子 非临界区非

63、临界区 wait(mutex)/进入区进入区 临界区临界区 signal(mutex)/退出区退出区 非临界区非临界区68利用信号量实现进程互斥的简单例子利用信号量实现进程互斥的简单例子n某某交交通通路路口口设设置置了了一一个个自自动动计计数数系系统统，该该系系统统由由“观观察察者者”进进程程和和“报报告告者者”进进程程组组成成。观观察察者者进进程程能能识识别别卡卡车车，并并对对通通过过的的卡卡车车计计数数；报报告告者者进进程程定定时时（可可设设为为每每隔隔1小小时时，准准点点时时）将将观观察察者者的的计计数数值值打打印印输输出出，每每次次打打印印后后把把计计数数值值清清“0”。两两个个进进程

64、程的的并并发发执执行行可可完完成成对对每每小小时时中中卡卡车车流流量量的的统计。这两个进程的功能如下：统计。这两个进程的功能如下： process observer while (condition) observe a lorry; wait（S）; count = count + 1; signal（S）; 临临界界区区 process reporter wait（S）; print（count）; count = 0； signal（S）; 临临界界区区semaphore S ；int count = 0 ；S.value = 1 ； 【注意注意】wait (S)和和signal (S)

65、必须成对出现必须成对出现 69利用信号量实现前趋关系利用信号量实现前趋关系 【例例】利用信号量，描述语句的前趋关系（见图利用信号量，描述语句的前趋关系（见图2-12）写出一个可并发执写出一个可并发执行的程序。行的程序。图中表示：图中表示： 进程进程P1中有语句中有语句S1； 进程进程P2中有语句中有语句S2；P1执行完应通知执行完应通知P2、P3；P2得到通知后才开始执行；得到通知后才开始执行；P2执行执行完应通知完应通知P4、P5；n语语句句S1执执行行后后才才能能执执行语句行语句S2和语句和语句S3；n语语句句S2执执行行后后才才能能执执行语句行语句S4和和S5；n语语句句S3、S4和和S

66、5执执行行后后，才才能能执执行行语语句句S6。S1S2S3S4S5S6图图2-12 2-12 前趋图举例前趋图举例P1P2P3P4P5P670semaphoreS12,S13,S24,S25,S36,S46,S56;S12.value=S13.value=0;S24.value=S25.value=0;S36.value=S46.value=S56.value=0;程序描述如下：程序描述如下：初始化初始化parbegin/parbegin表示并发执行开始表示并发执行开始processP1：执行执行S1;signal(S12);signal(S13);processP2：wait(S12);执行

67、执行S2;signal(S24);signal(S25);processP3：wait(S13);执行执行S3;signal(S36);processP4：wait(S24);执行执行S4;signal(S46);processP5：wait(S25);执行执行S5;signal(S56);processP6：wait(S36);wait(S46);wait(S56);执行执行S6;parend/用用parend表示并发执行结束表示并发执行结束712.4 经典进程同步问题经典进程同步问题 n生产者生产者-消费者问题消费者问题 n读者读者-写者问题写者问题 n哲学家进餐问题哲学家进餐问题 在多道

68、程序环境下，进程同步问题十分重要，引在多道程序环境下，进程同步问题十分重要，引起了不少学者对它进行研究，由此产生了一系列起了不少学者对它进行研究，由此产生了一系列经典的进程同步问题，其中较有代表性的是：经典的进程同步问题，其中较有代表性的是：通过对这些问题的研究和学习，可以帮助我们更通过对这些问题的研究和学习，可以帮助我们更好地理解进程同步概念及实现方法。好地理解进程同步概念及实现方法。722.4.1 生产者生产者-消费者问题消费者问题前前面面已已经经对对生生产产者者-消消费费者者问问题题做做了了一一些些描描述述，但但是是未未考考虑虑进进程程的的互互斥斥和和同同步步问问题题，因因而而造造成成了

69、了共共享享变变量量counter的的不确定性。不确定性。生生产产者者-消消费费者者问问题题是是相相互互合合作作进进程程关关系系的的一一种种抽抽象象，例例如如，先介绍先介绍最简单最简单的的P-C问题问题生产者生产者- -消费者问题从特殊到一般消费者问题从特殊到一般( (从易到难从易到难) )可以分可以分3 3种形式：种形式：一个生产者、一个消费者、一个缓冲区的问题；一个生产者、一个消费者、一个缓冲区的问题；一个生产者、一个消费者、一个生产者、一个消费者、n个缓冲区的问题；个缓冲区的问题； k个生产者、个生产者、m个消费者、个消费者、n个缓冲区的问题；个缓冲区的问题；73用信号量机制解决用信号量机

70、制解决P-C问题的基本方法：问题的基本方法：1.为为生生产产者者设设置置1个个私私有有信信号号量量empty，其其初初值值为为1，表表示示有有1个个空空缓缓冲冲区区；为为消消费费者者设设置置1个个私私有有信信号号量量full，其其初初值值为为0，表表示示开开始始时时没没有有满满缓缓冲冲区区；（信号量初值由物理意义确定信号量初值由物理意义确定）2.生生产产者者将将产产品品存存入入缓缓冲冲区区之之前前，应应先先测测试试缓缓冲冲区区是是否否空空：执执行行wait(empty)操操作作；离离开开临临界界区区(存存入入产产品品)后后，应应通通知知(可可能能会会唤唤醒醒)消消费费者者：执执行行signal

71、(full)操作；操作；3.消消费费者者从从缓缓冲冲区区取取产产品品之之前前，应应先先测测试试缓缓冲冲区区是是否否满满：执执行行wait(full)操操作作；离离开开临临界界区区(取取走走产产品品)后后 ， 应应 通通 知知 (可可 能能 会会 唤唤 醒醒 )生生 产产 者者 ： 执执 行行signal(empty)操作操作74信号量机制解决进程同步问题的一般方法：信号量机制解决进程同步问题的一般方法：1.为为同同步步双双方方设设置置各各自自的的信信号号量量，初初值值为为其其初初始始状状态态可可用用的的资资源源数数(故故该该信信号号量量称称为为资资源源信信号号量量或或私有信号量私有信号量)；2

72、.同同步步双双方方任任一一进进程程在在进进入入临临界界区区之之前前，应应先先对对自自己己的的信信号号量量执执行行wait()操操作作，以以测测试试是是否否有有自自己己可可用用的的资资源源。若若有有资资源源可可用用，则则进进入临界区，否则阻塞；入临界区，否则阻塞；3.同同步步双双方方任任一一进进程程离离开开临临界界区区后后，应应对对合合作作方方(对对方方)的的信信号号量量执执行行signal()操操作作，以以通通知知(若若对对方方处处于于阻阻塞塞状状态态，则则唤唤醒醒它它)对对方方已已有资源可用有资源可用(对方已可进入临界区对方已可进入临界区)。75最简单的最简单的生产者生产者-消费者问题消费者

73、问题缓冲区缓冲区PC一个生产者、一个消费者、一一个生产者、一个消费者、一个缓冲区的问题如右图所示。个缓冲区的问题如右图所示。当缓冲区空时，生产者可将产品存入缓冲区；当当缓冲区空时，生产者可将产品存入缓冲区；当缓冲区满时，生产者必须等待缓冲区满时，生产者必须等待(阻塞阻塞)，待消费者，待消费者取走产品后将其唤醒后，才能将产品存入。取走产品后将其唤醒后，才能将产品存入。当缓冲区满时，消费者可从缓冲区取出产品进行当缓冲区满时，消费者可从缓冲区取出产品进行消费；当缓冲区空时，消费者必须等待消费；当缓冲区空时，消费者必须等待(阻塞阻塞)，待生产者存入产品后将其唤醒后，才能再从缓冲待生产者存入产品后将其唤

74、醒后，才能再从缓冲区取产品。区取产品。76最简单的最简单的生产者生产者-消费者问题消费者问题一个生产者、一个消费者、一个缓冲区的生产者一个生产者、一个消费者、一个缓冲区的生产者-消费者问题消费者问题的算法描述如下所示：的算法描述如下所示：semaphoreempty,full;empty=1;full=0;parbeginprocessProducer:.produceaniteminnextp;wait(empty);/测试测试buffer=nextp;signal(full);/通知消费者通知消费者processConsumer:wait(full);/测试测试nextc=buffer;s

75、ignal(empty);/通知通知consumetheiteminnextc;parend77生产者生产者- -消费者问题的第二种特殊情况消费者问题的第二种特殊情况一个生产者、一个消费者、一个生产者、一个消费者、n个缓冲区的个缓冲区的P-C问题问题n-1543210PC循环缓冲区循环缓冲区n为为生生产产者者设设置置一一个个资资源源信信号号量量empty，其其初初值值为为生生产产者者的的可可用用资资源源数数(空空缓缓冲冲区区的的个个数数)n，即即empty=n。n为为消消费费者者设设置置一一个个资资源源信信号号量量full，其其初初值值为为消消费费者的可用资源数者的可用资源数(满缓冲区的个数满

76、缓冲区的个数)0，即，即full=0。empty=nfull=078semaphoreempty,full;empty=n;full=0;intin=0,out=0;/下标下标parbeginprocessProducer:.produceaniteminnextp;wait(empty);/测试测试bufferin=nextp;in=(in+1)%n;signal(full);/通知消费者通知消费者与前不同与前不同79processConsumer:wait(full);/测试测试nextc=bufferout;out=(out+1)%n;signal(empty);/通知通知consume

77、theiteminnextc;parend本题中本题中in和和out不是共享变量不是共享变量(因为只有一个生产因为只有一个生产者和一个消费者者和一个消费者)，无需互斥访问。，无需互斥访问。80生产者生产者- -消费者问题的一般形式消费者问题的一般形式下面介绍生产者下面介绍生产者- -消费者问题一般形式：消费者问题一般形式：k k个生产者、个生产者、m m个消费者、个消费者、n n个缓冲区的问题。个缓冲区的问题。一般形式的生产者一般形式的生产者- -消费者问题的图示如下：消费者问题的图示如下：012345n-1P1P2P3PKC1C2C3Cm生产者生产者消费者消费者n个缓冲区的循环缓冲个缓冲区的

78、循环缓冲图图2-5生产者生产者-消费者问题示意图消费者问题示意图81u设设置置生生产产者者的的资资源源信信号号量量empty，其其初初值值为为n，表表示示开始时有开始时有n个空缓冲区；个空缓冲区；u设设置置消消费费者者的的资资源源信信号号量量full，其其初初值值为为0，表表示示开开始时有始时有0个满缓冲区；个满缓冲区；u只要有空的缓冲区，生产者便可将消息送入缓冲区；只要有空的缓冲区，生产者便可将消息送入缓冲区；u只只要要有有满满的的缓缓冲冲区区，消消费费者者便便可可从从缓缓冲冲区区取取走走一一个个消息。消息。u用用互互斥斥信信号号量量mutex对对缓缓冲冲区区(共共享享变变量量in和和out

79、)的的互互斥使用，互斥信号量斥使用，互斥信号量mutex初值为初值为1；u生生产产者者用用共共享享变变量量in作作为为下下标标访访问问缓缓冲冲区区，mutex为为其其互互斥斥信信号号量量；消消费费者者用用共共享享变变量量out作作为为下下标标访访问问缓冲区，其互斥信号量也用缓冲区，其互斥信号量也用mutex。82生产者生产者- -消费者问题可描述如下：消费者问题可描述如下： semaphoremutex,empty,full;itembuffern;intin=0，out=0；mutex.value=1;empty.value=n；full.value=0;初始化初始化83parbegin/并

80、发执行开始并发执行开始processproduceri(i=1,2,k)/生产者进生产者进程程itemnextp；while(true)produceanitemnextp；wait(empty); /测试测试wait(mutex); /互斥互斥bufferin=nextp；in=(in+1)%n；signal(mutex);/成对成对signal(full); /交叉成对交叉成对临临界界区区84processconsumerj(j=1,2,m）itemnextc；while(true)wait(full);wait(mutex);nextc=bufferout；out=(out+1)%n；s

81、ignal(mutex);signal(empty);consumetheiteminnextc;parend/并发执行结束并发执行结束临界区临界区85n在在每每个个进进程程中中，实实现现互互斥斥的的wait(mutex)和和signal(mutex)必须成对出现；必须成对出现；n对对资资源源信信号号量量empty和和full的的wait和和signal操操作作也也要要成成对对地地出出现现，但但它它们们处处于于不不同同的的进进程程中中(交叉成对交叉成对)。n在在每每个个进进程程中中的的多多个个wait操操作作顺顺序序不不能能颠颠倒倒，应应先先执执行行对对资资源源信信号号量量（也也称称私私有有信

82、信号号量量）的的wait操操作作，然然后后执执行行对对互互斥斥信信号号量量（公公有有信信号号量量）的的wait操操作作，否否则则可可能能引引起起进进程程死死锁。锁。(Why?)注意：注意：86重申信号量解决同步问题的要点：重申信号量解决同步问题的要点：1.为为同同步步双双方方设设置置各各自自的的信信号号量量，初初值值为为其其初初始始状状态态可可用用的的资资源源数数(故故该该信信号号量量称称为为资资源源信信号号量量或或私有信号量私有信号量)；2.同同步步双双方方任任一一进进程程在在进进入入临临界界区区之之前前，应应先先对对自自己己的的信信号号量量执执行行wait()操操作作，以以测测试试是是否否

83、有有自自己己可可用用的的资资源源。若若有有资资源源可可用用，则则进进入临界区，否则阻塞；入临界区，否则阻塞；3.同同步步双双方方任任一一进进程程离离开开临临界界区区后后，应应对对合合作作方方(对对方方)的的信信号号量量执执行行signal()操操作作，以以通通知知(若若对对方方处处于于阻阻塞塞状状态态，则则唤唤醒醒它它)对对方方已已有资源可用有资源可用(对方已可进入临界区对方已可进入临界区)。872.4.2 哲学家进餐问题哲学家进餐问题Dijkstra提出并解决的哲学家就餐提出并解决的哲学家就餐问题是经典的进程同步问题。哲问题是经典的进程同步问题。哲学家就餐问题描述如下：学家就餐问题描述如下：

84、有有5个个哲哲学学家家共共用用一一张张圆圆桌桌，分分别别坐坐在在周周围围的的5张张椅椅子子上上，在在圆圆桌桌上上有有5个个碗碗和和5只只筷筷子子，他他们们的的生生活活方方式式是是交交替替地地进进行行思思考考和和进进餐餐。平平时时，每每个个哲哲学学家家进进行行思思考考，饥饥饿饿时时便便试试图图拿拿起起其其左左右右最最靠靠近近他他的的筷筷子子，只只有有在在他他拿拿到到两两只只筷筷子子时时才才能能进进餐餐。进进餐餐完完毕毕，放放下下筷筷子子继继续续思思考考。图图2-7是其示意图。是其示意图。P0P1P2P3P4f4f0f1f2f3图图2-7哲学家进餐问题哲学家进餐问题88n利用记录型信号量解决哲学家

85、进餐问题利用记录型信号量解决哲学家进餐问题 桌桌子子上上的的筷筷子子f0，f1，f4是是临临界界资资源源，应应互互斥斥使使用用，可可用用一一个个信信号号量量表表示示一一只只筷筷子子，5只只筷筷子子的的5个个信信号号量量构构成成信信号号量量数数组，所有信号量的初值均为组，所有信号量的初值均为1。semaphorechopstick5；chopstick0.value=chopstick1.value=1;chopstick2.value=chopstick3.value=1;chopstick4.value=1;初初始始化化每每个个哲哲学学家家算算法法流流程程为为(1) 拿起左、右筷子；拿起左、

86、右筷子；(2) 吃面条；吃面条；(3) 放下左、右筷子；放下左、右筷子；(4) 思考问题；思考问题；(5) 返回返回(1)。89哲学家哲学家Pi(i=0,1,2,3,4)的活动可描述如下：的活动可描述如下：parbeginprocessPi(i=0，1，2，3) /前前4个哲学家个哲学家while(true)wait(chopsticki)；/拿起左边筷子拿起左边筷子wait(chopsticki+1)； /拿起右边筷子拿起右边筷子eating；/吃面条吃面条signal(chopsticki)；/放下左边筷子放下左边筷子signal(chopsticki+1)；/放下右边筷子放下右边筷子th

87、inking；/思考思考90此算法虽然能保证相邻哲此算法虽然能保证相邻哲学家对筷子的访问互斥，学家对筷子的访问互斥，但可能引起死锁。但可能引起死锁。(Why?)(Why?) processP4/第第5个哲学家个哲学家while(true)wait(chopstick4)；/拿起左边筷子拿起左边筷子wait(chopstick0)；/拿起右边筷子拿起右边筷子eating；/吃面条吃面条signal(chopstick4)；/放下左边筷子放下左边筷子signal(chopstick0)；/放下右边筷子放下右边筷子thinking；/思考思考parend91对上述哲学家就餐问题算法的死锁问题，对上述

88、哲学家就餐问题算法的死锁问题，可采取下面几种解决方法之一：可采取下面几种解决方法之一： 至至多多允允许许4个个哲哲学学家家同同时时取取左左边边的的筷筷子子，这这样样能能至至少少保保证证一一个个哲哲学学家家能能就就餐餐，并并在在用用毕毕后后释释放放他他用用过过的的两两只只筷筷子子，从而使更多的哲学家能够进餐。从而使更多的哲学家能够进餐。（请学生考虑算法的描述）（请学生考虑算法的描述）仅仅当当哲哲学学家家左左右右两两只只筷筷子子均均可可用用时时，才才允允许许他他拿拿起起筷筷子子进进餐。餐。（用（用AND信号量机制）信号量机制）规规定定奇奇数数号号哲哲学学家家先先拿拿左左边边筷筷子子，然然后后再再拿

89、拿右右边边筷筷子子；而而偶数号哲学家先拿右边筷子，然后再拿左边筷子。偶数号哲学家先拿右边筷子，然后再拿左边筷子。规定每个哲学家先拿序号小的筷子规定每个哲学家先拿序号小的筷子按序号分配。按序号分配。同同一一时时间间最最多多允允许许1 1个个哲哲学学家家进进餐餐( (即即进进餐餐互互斥斥) )。此此算算法法并发程度最差。并发程度最差。本页内容和其后的解法仅供学生阅读和思考，可本页内容和其后的解法仅供学生阅读和思考，可跳过跳过。 92解决哲学家就餐问题算法的死锁问题的方法之一：解决哲学家就餐问题算法的死锁问题的方法之一：规定至多允许规定至多允许4个哲学家同时取左边的筷子。个哲学家同时取左边的筷子。9

90、3解决哲学家就餐问题算法的死锁问题的方法之二：解决哲学家就餐问题算法的死锁问题的方法之二：用用AND信号量机制。信号量机制。94解决哲学家就餐问题算法的死锁问题的方法之三：解决哲学家就餐问题算法的死锁问题的方法之三：奇数号哲学家先拿左边筷子，然后再拿右边筷子；而奇数号哲学家先拿左边筷子，然后再拿右边筷子；而偶数号哲学家先拿右边筷子，然后再拿左边筷子。偶数号哲学家先拿右边筷子，然后再拿左边筷子。95解决哲学家就餐问题算法的死锁问题的方法之四：解决哲学家就餐问题算法的死锁问题的方法之四：规定每个哲学家先拿序号小的筷子规定每个哲学家先拿序号小的筷子(按序号分配按序号分配)。96解决哲学家就餐问题算法

91、的死锁问题的方法之五：解决哲学家就餐问题算法的死锁问题的方法之五：同一时间最多允许同一时间最多允许1个哲学家进餐个哲学家进餐(即进餐互斥即进餐互斥)。972.4.3 读者读者-写者问题写者问题一个数据文件或记录，可被多个进程共享，我们把一个数据文件或记录，可被多个进程共享，我们把只要求读该文件的进程称为只要求读该文件的进程称为“读者读者进程进程”，其他进，其他进程称为程称为“写者写者进程进程”。 u允许多个读者进程同时读一个共享文件，因为读操允许多个读者进程同时读一个共享文件，因为读操作不会使数据文件混乱；作不会使数据文件混乱；u不允许两个或两个以上写者进程同时访问共享文件，不允许两个或两个以

92、上写者进程同时访问共享文件，因为这种访问将会引起混乱；因为这种访问将会引起混乱；u不允许一个写者进程和其他读者进程同时访问共享不允许一个写者进程和其他读者进程同时访问共享文件，因为这种访问将会引起混乱。文件，因为这种访问将会引起混乱。 所所谓谓“读读者者- -写写者者问问题题”是是指指保保证证一一个个WriterWriter进进程必须与其它进程互斥地访问共享对象的同步问题。程必须与其它进程互斥地访问共享对象的同步问题。 98利用记录型信号量解决读者利用记录型信号量解决读者-写者问题写者问题 【算法分析算法分析】 u为为实实现现Reader进进程程和和Writer进进程程间间的的互互斥斥，设设置

93、置一一个个互互斥信号量斥信号量Wmutex，其初值为，其初值为1；u设设置置一一个个整整型型变变量量Rcounter，记记录录正正在在读读的的读读者者进进程程数数。其初值为其初值为0；u由由于于只只要要有有一一个个Reader进进程程在在读读，便便不不允允许许Writer进进程程去去写写，因因此此第第一一个个读读者者进进程程需需要要执执行行wait(Wmutex)操操作作，即即 当当 Rcounter=0时时 ， Reader进进 程程 才才 需需 要要 执执 行行wait(Wmutex)操操作作。若若wait(Wmutex)操操作作成成功功（表表示示此此时时无无Writer进进程程在在写写）

94、，Reader进进程程便便可可去去读读，同同时时做做Rcounter+1的操作。的操作。99u同同理理，最最后后一一个个读读进进程程Reader离离开开时时，亦亦即即计计 数数 变变 量量 Rcounter-1后后 变变 为为 0时时 ， 应应 执执 行行signal(mutex)操作，以便让操作，以便让Writer进程写。进程写。uRcounter是是被被多多个个Reader进进程程访访问问的的临临界界资资源源，为为了了对对它它互互斥斥访访问问，应应为为它它设设置置一一个个互互斥信号量斥信号量Rmutex。u写写进进程程Writer进进入入临临界界区区前前要要对对互互斥斥信信号号量量Wmut

95、ex执执行行wait操操作作，离离开开临临界界区区时时要要对对互互斥信号量斥信号量Wmutex执行执行signal操作。操作。100根据前面分析，读者根据前面分析，读者- -写者问题可描述如下：写者问题可描述如下： semaphoreWmutex，Rmutex;intRcounter=0;/读者计数变量读者计数变量Wmutex.value=1;/写写-写互斥、读写互斥、读-写互斥写互斥Rmutex.value=1;/用于用于Rcounter互斥互斥parbeginprocessReaderi(i=1,2,)/读者进程读者进程wait(Rmutex);/准备访问共享变量准备访问共享变量Rcoun

96、terif(Rcounter=0)wait(Wmutex);Rcounter=Rcounter+1;signal(Rmutex);101Reading;wait(Rmutex);Rcounter=Rcounter1;if(Rcounter=0)signal(Wmutex);signal(Rmutex);/读者进程结束读者进程结束102processWriterj(j=1,2,)/写者进程写者进程wait(Wmutex);/写写-写互斥、写写互斥、写-读互斥读互斥Writing;signal(Wmutex);parend写进程的算法描述如下：写进程的算法描述如下：103【分析分析】n当当第第一一

97、个个读读者者在在读读文文件件时时，后后续续读读者者也也可可进进入入临临界界区区读读该该文文件件，后后续续写写者者不不能能写写(在在Wmutex上上阻阻塞塞)；待待所所有有读读者者退退出出时时，由由最后退出的读者唤醒一个写者。最后退出的读者唤醒一个写者。n当当有有一一个个写写者者在在写写时时，后后续续写写者者不不能能写写，在在Wmutex上上阻阻塞塞；后后续续读读者者不不能能读读，其其中中第第一一个个读读者者在在Wmutex上上阻阻塞塞，其其余余读读者者在在Rmutex上上阻阻塞塞。该该写写者者退退出出时时，唤唤醒醒一一个个写者或读者。写者或读者。104上上述述算算法法实实际际上上是是“优优先先

98、读读者者”算算法法，当当有有读读者者正正在在读读，且且后后续续读读者者源源源源不不断断到到来来时时，写写者者将将长长期期得得不不到到服服务务。写写者者“饿饿死死”。 为为此此，可可以以考考虑虑“优优先先写写者者”的的算算法法当当有有写写者者要要写写时时，待待目目前前正正在在读读的的读读者者读读完完后后，立立即即让让写写者者去去写写（即即一一旦旦有有写写者者到到达达，后后续续的的读读者者都都必必须须等等待待，而而无无论论是是否否有读者在读文件有读者在读文件）。下面介绍写进程具有优先权的算法：下面介绍写进程具有优先权的算法： 105n互互斥斥信信号号量量Rsem1：第第一一个个写写进进程程执执行行

99、wait(Rsem1)操操作作，用用于于封封锁锁后后续续读读进进程程。最最后后一一个个写写进进程程执执行行signal(Rsem1)操作。操作。n互互斥斥信信号号量量Rsem2：第第一一个个写写进进程程到到达达后后的的第第一一个个读读者在者在Rsem1上阻塞，其后的读进程在上阻塞，其后的读进程在Rsem2上阻塞。上阻塞。n整型变量整型变量Rcounter：初值为：初值为0，用于读进程计数。，用于读进程计数。n互互斥斥信信号号量量Rmutex：用用于于读读进进程程互互斥斥访访问问共共享享变变量量Rcounter。n互互斥斥信信号号量量Wsem：第第一一个个读读进进程程执执行行wait(Wsem)

100、用用于封锁写进程。于封锁写进程。n整型变量整型变量Wcounter：初值为：初值为0，用于写进程计数。，用于写进程计数。n互互斥斥信信号号量量Wmutex：用用于于写写进进程程互互斥斥访访问问共共享享变变量量Wcounter。设置设置5个互斥信号量和个互斥信号量和2个共享计数变量个共享计数变量:106“优先写者优先写者”算法描述如下：算法描述如下：107“写者优先写者优先”问题的另一种解法：可以在教科书解问题的另一种解法：可以在教科书解法的基础上，增加一个信号量法的基础上，增加一个信号量W，用于在写进程到，用于在写进程到达时封锁后续的读者进程。达时封锁后续的读者进程。108【讨论讨论】上上述述

101、算算法法执执行行时时，当当一一个个写写者者进进程程写写完完时时，可可能能唤唤醒醒后后一一个个写写者者，也也可可能能唤唤醒醒第第一一个个在在W上上阻阻塞塞是是读读者者进进程程。要要使使一一个个写写者者写写完完离离开开临临界界区区时时，若若有有别别的的写写者者，则则唤唤醒醒一一个个写写者者；若若无无写写者者等等待待时时，才才唤唤醒醒一一个个读读者者，可可以以采采用用我我们们介介绍绍的的上上一一个个算算法法(即即写写者者也也需需计计数的那个算法数的那个算法)。1098.(2011全国试题全国试题)有两个并发进程有两个并发进程P1和和P2，共享初值为，共享初值为1的变的变量量x。P1对对x加加1，P2

102、对对x减减1。加。加1和减和减1操作的指令序列分别操作的指令序列分别如下所示。如下所示。/加加1操作操作loadR1,x/取取x到寄存器到寄存器R1中中incR1storex,R1/将将R1的内容存入的内容存入x/减减1操作操作loadR2,xdecR2storex,R2两个操作完成后，两个操作完成后，x的值的值。A可能为可能为-1或或3B只能为只能为1C可能为可能为0、1或或2D可能为可能为-1、0、1或或2C复习思考题（一）复习思考题（一）1103.S.queue，S.value是信号灯是信号灯S的两个组成部分，的两个组成部分，当当S.queue为空时，为空时，S.value的值是的值是。

103、AS.value0BS.value=0CS.value=1DSvalue04.如如果果信信号号量量的的当当前前值值为为-3，则则表表示示系系统统中中在在该该信号量上有信号量上有个等待进程。个等待进程。7.设设与与某某资资源源关关联联的的信信号号量量初初值值为为3，当当前前值值为为1。若若M表表示示该该资资源源的的可可用用个个数数，N表表示示等等待待该该资资源源的的进进程程数数，则则M、N分分别别是是_。(2010年年全全国国考考研试题研试题)A0、1B1、0C1、2D2、0BD31111.设有设有n个进程使用同一个共享变量，如果最多允个进程使用同一个共享变量，如果最多允许许m(m0)个个单单元

104、元的的缓缓冲冲区区。P1每每次次用用produce()生生成成一一个个正正整整数数并并用用put()送送入入缓缓冲冲区区某某个个单单元元中中；P2每每次次用用getodd()从从缓缓冲冲区区中中取取出出一一个个奇奇数数并并用用countodd()统统计计奇奇数数个个数数；P3每每次次用用geteven()从从缓缓冲冲区区中中取取出出一一个个偶偶数数并并用用counteven()统统计计偶偶数数个个数数。请请用用信信号号量量机机制制实实现现这这三三个个进进程程的的同同步步与与互互斥斥活活动动，并并说说明明所所定定义义的的信信号号量量的的含含义义。要要求求用用伪伪代代码码描描述述。(2009(20

105、09全国考研题第全国考研题第4545题题) )【说明说明】解本题时可不考虑缓冲区中存取各个单解本题时可不考虑缓冲区中存取各个单元的实现细节。元的实现细节。114复习思考题（二）复习思考题（二）semaphoreempty,apple,pear;itemplate;empty.value=1,apple.value=pear.value=0parbeginprocessPAwait(empty);plate=apple;signal(apple);processPBwait(empty);plate=pear;signal(pear);processPCwait(apple);apple=pla

106、te;signal(empty);processPDwait(pear);pear=plate;signal(empty);parend115116117复习思考题（三）复习思考题（三）3.今今有有一一个个文文件件F供供进进程程共共享享，现现把把这这些些进进程程分分成成A、B两两组组，规规定定同同组组的的进进程程可可以以同同时时读读文文件件F；但但当当有有A组组（或或B组组）的的进进程程在在读读文文件件F时时就就不不允允许许B组组（或或A组组）的的进进程程读读文文件件F。试试用用P、V操操作作（记记录录型型信信号号量量）来来进进行行管管理理。(从读者从读者-写者问题得到启发写者问题得到启发)4

107、.生生产产者者-消消费费者者问问题题中中，如如果果将将wait(full)和和wait(mutex)互互相相置置换换，或或者者将将signal(mutex)和和signal(empty)互相置换，结果会如何？互相置换，结果会如何？1185.试试利利用用记记录录型型信信号号量量写写出出一一个个不不会会出出现现死死锁的哲学家进餐问题的算法。锁的哲学家进餐问题的算法。6.设设自自行行车车生生产产车车间间有有两两个个货货架架，货货架架A可可以以存存放放8个个车车架架，货货架架B可可以以存存放放20个个车车轮轮；又又设设有有4个个工工人人，他他们们的的活活动动是是重重复复劳劳动动，分分别别为为：工工人人

108、1加加工工一一个个车车架架放放入入货货架架A中中；工工人人2、3分分别别加加工工车车轮轮放放入入货货架架B中中（每每人人每每次次放放入入1个个车车轮轮）；工工人人4从从货货架架A中中取取一一个个车车架架，再再从从货货架架B中中取取两两个个车车轮轮，组组装装成成一一辆辆自自行行车车。试试用用PV操操作作实实现现四四个个工人的合作。工人的合作。119信信号号量量Aempty表表示示货货架架A的的空空位位数数，其其初初值为值为8；信信号号量量Afull表表示示货货架架A上上存存放放的的车车架架数数，其其初值为初值为0；信信号号量量Bempty表表示示货货架架B的的空空位位数数，其其初初值为值为20；

109、信信号号量量Bfull表表示示货货架架B上上存存放放的的车车轮轮数数，其其初值为初值为0；信号量信号量mutex用于互斥（初值为用于互斥（初值为1）。）。【分析分析】设置资源信号量和互斥信号设置资源信号量和互斥信号量如下：量如下：120121每两个学生组成一组，各占一台机器，协同完成每两个学生组成一组，各占一台机器，协同完成上机实习；上机实习；只有一组学生到齐，并且此时机房有空闲机器时，只有一组学生到齐，并且此时机房有空闲机器时，该组学生才能进入机房；该组学生才能进入机房；上机实习由一名教师检查。检查完毕，一组学生上机实习由一名教师检查。检查完毕，一组学生同时离开机房。同时离开机房。试用试用P

110、、V操作模拟上机实习过程。操作模拟上机实习过程。（北京大学（北京大学，1997年）年）7.某某高高校校计计算算机机系系开开设设网网络络课课并并安安排排上上机机实实习习，假假设机房共有设机房共有2m台机器，有台机器，有2n名学生选该课，规定：名学生选该课，规定：122解解：在在本本题题中中，为为了了保保证证系系统统的的控控制制流流程程，增增加加了了Monitor进进程程，用用于于控控制制学学生生的的进进入入和和计计算算机机分分配配。从从题题目目本本身身来来看看，虽虽然然没没有有明明确确写写出出这这一一进进程程，但但实实际际上上这这一一进进程程是是存存在在的的。因因此此，在在解解决决这这类类问问题

111、题时时，需需要要对对题题目目加加以以认认真真分分析析，找找出出其其隐隐蔽蔽的的控控制制机机制制。同步算法描述如下：同步算法描述如下：学生的活动过程：学生的活动过程：学生到达学生到达V(student);等待允许进入等待允许进入P(enten);用用Monitor指定的计算机上机实习；指定的计算机上机实习；实习完成实习完成V(finish);等待老师检查等待老师检查P(check);释放计算机释放计算机V(computer);123老师的活动过程老师的活动过程：Repeat等待学生完成实习等待学生完成实习P(finish);等待另一学生完成等待另一学生完成P(finish);检查学生实习；检查学

112、生实习；检查完成一学生的实习检查完成一学生的实习V(check);检查完另一学生的实习检查完另一学生的实习V(check);Untilfalse124Monitor的活动过程：的活动过程：Repeat等待学生到达等待学生到达P(student);等待另一学生到达等待另一学生到达P(student);获取一台计算机获取一台计算机P(computer);获取一台计算机获取一台计算机P(computer);允许学生进入并给其指定一台计算机允许学生进入并给其指定一台计算机V(enter);允许学生进入并给其指定一台计算机允许学生进入并给其指定一台计算机V(enter);Untilfalse125126

113、8.理理发发师师问问题题描描述述如如下下：理理发发店店包包含含一一间间接接待待室室和和一一间间工工作作室室，接接待待室室内内有有n(n1)把把椅椅子子，而而工工作作室室只只有有1把把椅椅子子。如如果果没没有有顾顾客客，理理发发师师就就去去睡睡觉觉；如如果果来来时时所所有有椅椅子子都都有有人人，那那么么顾顾客客离离去去；如如果果理理发发师师在在忙忙且且接接待待室室有有空空闲闲椅椅子子，那那么么此此顾顾客客会会坐坐在在其其中中1把把空空闲闲的的椅椅子子上上等等待待；如如果果理理发发师师在在睡睡觉觉；则则顾顾客客会会唤唤醒醒他他。请请采采用用信信号号量量机机制制解解决决该该理理发发师问题师问题(可用

114、伪代码描述可用伪代码描述)。127解：引入解：引入3个信号量和个信号量和1个控制变量：个控制变量：v控制变量控制变量count用来记录等待理发的顾客数，用来记录等待理发的顾客数，初值为初值为0；当；当count=n时，新来的顾客离去。时，新来的顾客离去。v信号量信号量customers用来记录等候理发的顾客用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为数，并用作阻塞理发师进程，初值为0；v信号量信号量barbers用来记录等候顾客的理发师用来记录等候顾客的理发师数，并用作阻塞顾客进程，初值为数，并用作阻塞顾客进程，初值为0；v信号量信号量mutex用于对共享变量用于对共享变量count

115、的互斥的互斥访问，初值为访问，初值为1。128采用信号量机制解决该理发师问题的算法描述如下：采用信号量机制解决该理发师问题的算法描述如下：129信号量机制解决理发师问题算法的另一描述：信号量机制解决理发师问题算法的另一描述：130理发师问题的拓展：理发师问题的拓展：l有多个理发师的问题；有多个理发师的问题；l考虑公平性问题考虑公平性问题顾客先来先服务；顾客先来先服务；l除了接待室除了接待室(有椅子有椅子)还有接待区还有接待区(站着等候，站着等候，人数有限制人数有限制)的问题。等等。的问题。等等。1312.5 管程机制管程机制信号量机制方便、有效，但每个要访问临界资源信号量机制方便、有效，但每个

116、要访问临界资源的进程都必须自备同步操作的进程都必须自备同步操作wait(S)和和signal(S)，使大量的同步操作分散在各个进程中。使大量的同步操作分散在各个进程中。n给系统管理带来麻烦；给系统管理带来麻烦；n会因同步操作使用不当而导致系统死锁。会因同步操作使用不当而导致系统死锁。为解决上述问题，在为解决上述问题，在1974年和年和1975年，汉森年，汉森(BrinchHanson)和霍尔和霍尔(Hoare)提出了一种新的提出了一种新的进程同步机制进程同步机制管程管程(Monitors)管程的基本思路是：把分散在各进程中的临管程的基本思路是：把分散在各进程中的临界区集中起来进行管理，并把系统

117、中的共享资界区集中起来进行管理，并把系统中的共享资源用数据结构抽象地表示出来。源用数据结构抽象地表示出来。1322.5.1 管程的基本概念管程的基本概念1管程的定义管程的定义系系统统中中的的各各种种硬硬件件资资源源和和软软件件资资源源，均均可可用用数数据据结结构构加加以以抽抽象象的的描描述述，即即用用少少量量信信息息和和对对该该资资源源所所执执行行的的操操作作来表征该资源，而忽略了它们的内部结构和实现细节。来表征该资源，而忽略了它们的内部结构和实现细节。例例如如，对对一一台台电电传传机机可可用用与与分分配配该该资资源源有有关关的的状状态态信信息息(busy和和free)和和对对它它执执行行请请

118、求求和和释释放放的的操操作作，以以及及等等待待该该资源的进程队列来描述。资源的进程队列来描述。又又如如，一一个个FIFO队队列列，可可用用其其队队长长、队队首首和和队队尾尾以以及及在在该队列上执行的一组操作来描述。该队列上执行的一组操作来描述。当当共共享享资资源源用用数数据据结结构构表表示示时时，资资源源管管理理程程序序可可用用对对该该数数据据结结构构进进行行操操作作的的一一组组过过程程来来表表示示，如如资资源源的的请请求求和释放过程和释放过程request和和release。我们把这样一组相关的数据结构和过程一并称为管程。我们把这样一组相关的数据结构和过程一并称为管程。class133Han

119、son为管程所下的定义为管程所下的定义：一一个个管管程程定定义义了了一一个个数数据据结结构构和和能能被被并并发发进进程程执执行行(在在该该数数据据结结构构上上)的的一一组组操操作作，这这组组操作能同步进程和改变管程中的数据。操作能同步进程和改变管程中的数据。由定义可知，管程由三部分组成：由定义可知，管程由三部分组成：u局部于管程的共享变量说明；局部于管程的共享变量说明；u对该数据结构进行操作的一组过程；对该数据结构进行操作的一组过程；u对局部于管程的数据设置初值的语句。对局部于管程的数据设置初值的语句。u此外，还须为管程赋予一个名字。此外，还须为管程赋予一个名字。Pascal与与Java等高级

120、语言已实现了管程。等高级语言已实现了管程。134管程的示意图如图管程的示意图如图2-11。管程的语法如下：管程的语法如下：type=monitor;procedure()procedure()；共享数据共享数据一组操作过程一组操作过程初始化代码初始化代码进入队列进入队列(等待等待)条件队列条件队列(不忙不忙)图图2-11管程示意图管程示意图135n局部于管程的数据结构，仅能被局部于局部于管程的数据结构，仅能被局部于管程的过程访问，任何管程外的过程都管程的过程访问，任何管程外的过程都不能访问它；不能访问它；n局部于管程的过程仅能访问管程内的数局部于管程的过程仅能访问管程内的数据结构。据结构。管管

121、程程把把共共享享变变量量和和对对它它的的操操作作的的若若干干过过程程“封封装装”起起来来，所所有有进进程程要要访访问问临临界界资资源源时时，都都必必须须经经过过管管程程才才能能进进入入，而而管管程程每每次次只只准准许许一一个个进进程程进进入入管管程程，从从而而实实现现了了进程互斥。进程互斥。1362条件变量条件变量l利利用用管管程程实实现现进进程程同同步步时时，必必须须设设置置两两个个同同步步操作原语操作原语wait和和signal。l某某进进程程通通过过管管程程请请求求临临界界资资源源未未能能满满足足时时，管管程程调调用用wait原原语语将将该该进进程程阻阻塞塞，并并把把它它排排到到等等待待

122、队列上，如图队列上，如图2-11。l当当另另一一进进程程访访问问完完成成并并释释放放该该资资源源后后，管管程程调调用用signal原语唤醒等待队列中的队首进程。原语唤醒等待队列中的队首进程。等待的原因可有多个，为区别它们，引入了条件变等待的原因可有多个，为区别它们，引入了条件变量量condition。条件变量的说明形式为：。条件变量的说明形式为：varx,y:condition;对应的原语调用形式为：对应的原语调用形式为：x.wait;和和x.signal;等等137【说明说明】x.signal的操作与信号量中的的操作与信号量中的signal操作不同。操作不同。x.signal操操作作的的作作

123、用用，是是重重新新启启动动一一个个被被阻阻塞塞的的进进程程，但但如如果果没没有有被被阻阻塞塞的的进进程程，则则x.signal操操作作不不产产生生任任何何后后果果。而而信信号号量量中中的的signal总总是是要要执执行行s=s+1操作，因而总是要改变信号量的状态。操作，因而总是要改变信号量的状态。当当进进程程P执执行行了了x.signal操操作作唤唤醒醒进进程程Q后后，怎怎样样决决定由哪个进程占用定由哪个进程占用CPU执行，有两种处理方式：执行，有两种处理方式：P等待，直至等待，直至Q离开管程或等待另一条件；离开管程或等待另一条件；Q等待，直至等待，直至P离开管程或等待另一条件。离开管程或等待

124、另一条件。Hanson采用了第一种处理方式。采用了第一种处理方式。1382.5.2 管程应用举例管程应用举例利用管程解决生产者利用管程解决生产者-消费者问题，首先要为它们消费者问题，首先要为它们建立一个管程，命名为建立一个管程，命名为Produer_Consumer，简称，简称为为PC。其中包括两个过程：。其中包括两个过程：put(item)过程过程。生产者利用该过程将自己生产。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量的产品投放到缓冲池中，并用整型变量count来来表示在缓冲池中已有的产品数目，当表示在缓冲池中已有的产品数目，当countn时，时，表示缓冲池已满，生产者等待

125、表示缓冲池已满，生产者等待(阻塞阻塞)。get(item)过程过程。消费者利用该过程从缓冲池中。消费者利用该过程从缓冲池中取出一个产品，当取出一个产品，当count0时，表示缓冲池已无时，表示缓冲池已无可取的产品，消费者应等待。可取的产品，消费者应等待。1.1.利用管程解决生产者利用管程解决生产者- -消费者问题消费者问题139PC管程可描述如下：管程可描述如下：140利用管程解决生产者利用管程解决生产者-消费者问题时，生产者和消费消费者问题时，生产者和消费者进程可描述为：者进程可描述为：producer:beginrepeatproduceaniteminnextp;PC.put(item)

126、;untilfalse;endconsumer:beginrepeatPC.get(item);consumetheiteminnextc;untilfalse;end1412.2.利用管程解决读者利用管程解决读者- -写者问题写者问题利用管程解决读者利用管程解决读者-写者问题，首先要为它们建立写者问题，首先要为它们建立一个管程，命名为一个管程，命名为Reader_Writer，简称为，简称为R_W。其中包括其中包括4个过程：个过程：Rin()过过程程。读读者者利利用用该该过过程程进进入入读读文文件件。用用整整型型变变量量RN来来表表示示读读者者数数，WN表表示示写写者者数数。若若WN1时时，

127、表表示示已已有有写写者者要要/在在写写，读读者者等等待待(阻阻塞塞)；否则；否则RN增增1。Rout()过过程程。读读者者利利用用该该过过程程退退出出读读文文件件状状态态。读读者者读读完完离离开开时时，RN减减1，当当RN=0时时，若若有有写写者者等待，唤醒等待，唤醒1个写者。个写者。142Win()过过程程。写写者者利利用用该该过过程程进进入入写写文文件件状状态态。首首先先WN增增1，当当RN1或或WN1时时，表表示示有有读读者者在读或别的写者在写，写者等待。在读或别的写者在写，写者等待。Wout( )过过程程。写写者者写写完完离离开开时时WN减减1。若若WN0，则则唤唤醒醒1个个写写者者；

128、否否则则，若若有有读读者者等等待待，则唤醒所有等待的读者。则唤醒所有等待的读者。143Reader_Writer管程可描述如下管程可描述如下(用伪代码用伪代码)：typeR_W=monitorvarRN,WN:integer;/读者、写者计数变量读者、写者计数变量R,W:condition;procedureRin()/读者进入读的过程读者进入读的过程beginifWN0thenR.wait;/读者进程阻塞读者进程阻塞RN:=RN+1;/读者数增读者数增1endprocedureRout()/读者离开读者离开beginRN:=RN-1;ifRN=0andW.queuethenW.signal;

129、/若写者等若写者等待，则唤醒队首的一个写者待，则唤醒队首的一个写者end144procedureWin()/写者进入写的过程写者进入写的过程beginWN:=WN+1;ifRN0orWN1thenW.wait;/写者等待写者等待endprocedureWout() /写者离开写者离开beginWN:=WN-1;ifWN0thenW.signal;/若有写者等待，则唤醒队若有写者等待，则唤醒队首的一个写者进程首的一个写者进程elsewhile(R.queue)R.signal;/否则若有读者等待，否则若有读者等待，则逐个唤醒所有等待的读者则逐个唤醒所有等待的读者endbeginRN:=0;WN:

130、=0;/初始化内部数据初始化内部数据end145利用管程解决读者利用管程解决读者-写者问题时，读者和写者进程可写者问题时，读者和写者进程可描述为：描述为：parbeginreader:beginR_W.Rin();ReadFile;R_W.Rout();endwriter:beginR_W.Win();WriteFile;R_W.Wout();endparend思考：利用管程解决哲学家进餐问题。思考：利用管程解决哲学家进餐问题。1463.3.利用管程解决哲学家进餐问题利用管程解决哲学家进餐问题建立一个管程，命名为建立一个管程，命名为Philosopher，简称为，简称为PH。其中包括其中包括2

131、个过程：个过程：get(i)过过程程。第第i号号哲哲学学家家取取筷筷子子的的过过程程。用用整整型型数数组组chop0.4来来表表示示筷筷子子，chopi=1表表示示i号号筷筷子子空空闲闲，chopi=0表表示示i号号筷筷子子已已被被取取走走。设设j=(i+1)mod5。当当chopi=1且且chopj=1时时，第第i号号哲哲学学家家才才可可取取筷筷子子(chopi=0，chopj=0)；否则阻塞。；否则阻塞。put(i)过过程程。第第i号号哲哲学学家家放放下下筷筷子子的的过过程程。对对左左右右筷筷子子对对应应的的变变量量分分别别置置1，并并且且唤唤醒醒等等待待该该筷筷子子的的哲哲学学家进程。家

132、进程。147PH管程可描述如下管程可描述如下(用伪代码用伪代码)：typePH=monitorvarchop:array0.4ofinteger;cc:array0.4ofcondition;procedureentryget(integeri)/第第i号哲学家取筷子过程号哲学家取筷子过程beginj:=(i+1)mod5;L1:ifchopi=0orchopj=0thenbeginifchopi=0thencci.wait;elseccj.wait;gotoL1;/被唤醒后必须回到被唤醒后必须回到if语句开头语句开头endchopi:=0;/拿起左边的筷子拿起左边的筷子chopj:=0; /

133、拿起右边的筷子拿起右边的筷子end148procedureentryput(integeri)/i号哲学家放筷子过程号哲学家放筷子过程beginchopi:=1;/放下左边筷子放下左边筷子ifcci.queuethencci.signal;chopj:=1;/放下右边筷子放下右边筷子ifccj.queuethenccj.signal;endbeginchop0:=:chop1:=chop2:=1;/初始化数据初始化数据chop3:=chop4:=1;end149利用管程解决哲学家进餐问题时，第利用管程解决哲学家进餐问题时，第i个哲学家进程个哲学家进程可描述为：可描述为：Pi()(i=0.4)b

134、eginrepeatPH.get(i); /取筷子取筷子吃面条吃面条;PH.put(i);/放下筷子放下筷子思考问题思考问题;untilfalseendparbeginP0();P1();P2();P3();P4();parend150进程互斥和同步机制进程互斥和同步机制( (补充内容补充内容) )n软件忙等互斥方案软件忙等互斥方案n基本的硬件机制基本的硬件机制n软件非忙等互斥方案软件非忙等互斥方案n信号量信号量( (已介绍已介绍) )n管程管程( (已介绍已介绍) )n消息传递消息传递( (不介绍不介绍) )n.返回本章目录返回本章目录151互斥的软件算法互斥的软件算法1算法算法1两个进程两

135、个进程P0、P1共享一个变量共享一个变量turn，turn=i时进程时进程Pi可以进可以进入临界区。入临界区。turn的初值为的初值为0或或1无关紧要。无关紧要。i和和j分别为分别为0或或1，j=1-i。Pi进入临界区的算法如下：进入临界区的算法如下：repeatwhileturnidoskip;/*skip为空语句为空语句*/临界区；临界区；turn:=j;其它代码；其它代码；untilfalse;上述算法是用伪代码描述的。上述算法是用伪代码描述的。152 上述算法能满足互斥的要求，但它要求进入临界区的进程必上述算法能满足互斥的要求，但它要求进入临界区的进程必须严格地交替进行。须严格地交替进

136、行。不符合不符合空闲让进空闲让进原则原则。2算法算法2算法算法1的问题在于，它只记住了哪个进程允许进入它的临界的问题在于，它只记住了哪个进程允许进入它的临界区，但没有记录每个进程的状态。为了避免这种情况，可区，但没有记录每个进程的状态。为了避免这种情况，可用下面的数组来代替变量用下面的数组来代替变量turn：varflag:array0.1ofboolean;该数组的每个元素的初值均为该数组的每个元素的初值均为false。若。若flagi为为true，则表，则表示进程示进程Pi正在其临界区执行。进程正在其临界区执行。进程Pi进入临界区的算法为进入临界区的算法为repeatwhileflagjd

137、oskip;flagi:=true;临界区临界区;flagi:=false;剩余区剩余区;untilfalse;153算法算法2不能保证进程互斥访问临界区。不能保证进程互斥访问临界区。例如考虑如下执行序列例如考虑如下执行序列：T0时刻：时刻：P0进入进入while语句并发现语句并发现flag1=falseT1时刻：时刻：P1进入进入while语句并发现语句并发现flag0=falseT2时刻：时刻：P1置置flag1为为true并进入自己的临界区并进入自己的临界区T3时刻：时刻：P0置置flag0为为true并进入自己的临界区并进入自己的临界区于是，于是，P0P0和和P1P1都进入了各自的临界

138、区，从而违反了互都进入了各自的临界区，从而违反了互斥的要求。斥的要求。学生思考学生思考1542算法算法3(正确算法正确算法1，Peterson算法算法)将上述两种算法的有利思想结合在一起。进程间共享将上述两种算法的有利思想结合在一起。进程间共享2个共个共用变量：用变量：varflag:array0.1ofboolean;/初值皆为初值皆为falseturn:0.1; /初值为初值为0或或1无关紧要无关紧要进程进程Pi进入临界区的算法描述如下：进入临界区的算法描述如下：repeatflagi:=true;turn:=j;while(flagjandturn=j)doskip;临界区临界区;fla

139、gi:=false;/使有限等待使有限等待非临界区非临界区;untilfalse;155上述算法从同步准则的前上述算法从同步准则的前3条看是正确的条看是正确的(但它不满足让权等待但它不满足让权等待准则，而是忙碌等待准则，而是忙碌等待)。正确性说明如下：。正确性说明如下：设，初始时，两个进程都不在各自的临界区。设，初始时，两个进程都不在各自的临界区。(1)若若P0现在要进入临界区，而此时现在要进入临界区，而此时P1不要求进入临界区，则不要求进入临界区，则P0通过执行：通过执行：flag0=true;turn=1;后，后，P0测试测试while语句中的条件，发现语句中的条件，发现flag1为假，立

140、即进入临为假，立即进入临界区。之后，若界区。之后，若P1要求进入临界区，其执行要求进入临界区，其执行while语句发现语句发现flag0为真而忙碌等待，直至为真而忙碌等待，直至P0退出临界区并置退出临界区并置flag0为假。为假。(2)若若P0和和P1几乎同时要求进入临界区，两进程都将自己的状几乎同时要求进入临界区，两进程都将自己的状态态flagi置位置位true，且都把对方的进程号赋给，且都把对方的进程号赋给turn变量。因此变量。因此turn最后取值是先执行此赋值语句的进程号。不妨假设最后取值是先执行此赋值语句的进程号。不妨假设P0先赋先赋值，当两个进程都进入值，当两个进程都进入while

141、语句时，语句时，flagi均为均为true，但因变，但因变量量turn=0(即即turn=1不满足不满足)，P0有资格先进入临界区，有资格先进入临界区，P1在在while语句忙碌等待。语句忙碌等待。156互斥的硬件实现互斥的硬件实现1禁止中断禁止中断最简单的硬件解决方案，不需要软件算法的辅助。最简单的硬件解决方案，不需要软件算法的辅助。进程进入临界区的第一步就是进程进入临界区的第一步就是禁止一切中断禁止一切中断，在离，在离开临界区前开临界区前开放中断开放中断，这就使进程切换不可能发生，这就使进程切换不可能发生缺点：缺点：n将禁止中断的权力赋予普通用户。若一个将禁止中断的权力赋予普通用户。若一个

142、用户禁止中断后一直未开放中断，系统正用户禁止中断后一直未开放中断，系统正常运行就可能受到影响；常运行就可能受到影响；n不适用于多处理机系统。若系统有多个处不适用于多处理机系统。若系统有多个处理机，一个进程只能禁止本理机，一个进程只能禁止本CPUCPU的中断，的中断，那么其它处理机上运行的进程仍可能使用那么其它处理机上运行的进程仍可能使用互斥资源。互斥资源。1572Test-andSet指令指令(TS指令指令)或或TestandSetLock指令指令(TSL指令指令)很很多多计计算算机机都都提提供供Test-and-Set或或TestandSetLock这这样样的的机机器器指指令令，这这种种指指

143、令令将将制制定定地地址址中中的的内内容容读读至至制制定定寄寄存存器器，将将真真值值(或或非非0值值)写写入入该该地地址址，读读和和写写在在一一条条指指令令内内完完成成。在在多多处处理理机机计计算算机机系系统统中中，执执行行这这种种指指令令的的处处理理机机封封锁锁内内存存总总线线，以以禁禁止止其其它它CPU在在该该指指令令执执行行完完前前访访问问该该内内存存。该该指指令令的的语语义可表示为：义可表示为：booleanTS(booleantarget)booleanold=target;target=true;returnold;158利用利用TS指令实现进程互斥的算法是：指令实现进程互斥的算法是

144、：n每每个个临临界界资资源源都都设设置置一一个个公公共共boolean变变量量lock，表表示示自自愿愿的的两两种种状状态态：true表表示示正正在在被占用，被占用，false表示空闲，初始值为表示空闲，初始值为false。n在在进进入入区区，利利用用TS指指令令进进行行检检查查和和修修改改标标志志lock。n有进程在临界区时，重复检查；有进程在临界区时，重复检查；n直直道道其其它它进进程程退退出出时时，检检查查通通过过，进进入入临临界界区。区。159booleanlock;lock=false;ProcessPi(i=0,1,2,.,n)while(TS(lock)doskip;/忙碌等待忙

145、碌等待临界区临界区CS(CriticalSection);lock=false;其它代码其它代码;TS指令实现进程互斥的算法描述：指令实现进程互斥的算法描述：1603Swap指令指令Swap指令指令(在一条指令内，以不可分割的方在一条指令内，以不可分割的方式式)交换两个字交换两个字(字节字节)的内容。的内容。voidSwap(boolean&a,boolean&b)booleantemp;temp=a;a=b;b=temp;161在在Intelx86中，中，Swap指令称为指令称为XCHG指令。指令。Swap指令可以简指令可以简单有效地实现互斥，方法是为每个临界资源设置一个布尔变量，单有效地实

146、现互斥，方法是为每个临界资源设置一个布尔变量，例如，称为例如，称为lock，当其值为，当其值为false时表示无进程在临界区。实现时表示无进程在临界区。实现进程互斥的算法描述如下：进程互斥的算法描述如下：booleanlock;lock=false;ProcessPi(i=1,2,.,n)booleankey;while(true)key=true;while(key)Swap(lock,key);临界区临界区;lock=false;其它代码其它代码;162【例例】进程进程P0和和P1的共享变量定义及其初值为：的共享变量定义及其初值为：booleanflag2;intturn=0;flag0=

147、FALASE;flag1=FALSE;若进程若进程P0和和P1访问临界资源的类访问临界资源的类C伪代码实现如下：伪代码实现如下：(2010年全国考研试题年全国考研试题)voidP0()/进程程P0while(TRUE)flag0=TRUE;turn=1;while(flag1&(turn=1);临界区界区;flag0=FALSE;voidP1()/进程程P1while(TRUE)flag1=TRUE;turn=0;while(flag0&(turn=0);临界区界区;flag1=FALSE;复习思考题（四）复习思考题（四）163则并发执行进程则并发执行进程P0和和P1时产生的情形是时产生的情形

148、是_A.不能保证进程互斥进入临界区，会出现不能保证进程互斥进入临界区，会出现“饿死饿死”现象现象B.不能保证进程互斥进入临界区，不会出现不能保证进程互斥进入临界区，不会出现“饿饿死死”现象现象C.能保证进程互斥进入临界区，会出现能保证进程互斥进入临界区，会出现“饿死饿死”现象现象D.能保证进程互斥进入临界区，不会出现能保证进程互斥进入临界区，不会出现“饿死饿死”现象现象D本题给出的实际上就是本题给出的实际上就是Peterson算法。算法。164华中科技大学华中科技大学2000年试题年试题：进程：进程P0和和P1共享变量共享变量flag和和turn。它们进入临界区的算法描述如下：它们进入临界区的

149、算法描述如下：该算法能否正确地实现互斥？若不能，应如何修改（假定该算法能否正确地实现互斥？若不能，应如何修改（假定flag和和turn单元内容的修改和访问时互斥的）？单元内容的修改和访问时互斥的）？ 165【分析分析】不妨假设开始时不妨假设开始时turn=0考虑如下执行序列：考虑如下执行序列：时间时间语句语句执行进程执行进程T0时刻时刻flag0=true0T1时刻时刻whileturn 00T2时刻时刻进入临界区进入临界区0T3时刻时刻flag1=true1T4时刻时刻whileturn 11T5时刻时刻whileflag0 false1T6时刻时刻turn=11T7时刻时刻进入临界区进入临

150、界区1所以该算法不能实现互斥所以该算法不能实现互斥。正确的算法如正确的算法如Peterson算法。算法。166南京理工大学南京理工大学2001年试题。年试题。下面是两个进程下面是两个进程P0、P1互斥是用临界区的解决方法，互斥是用临界区的解决方法，能否达到互斥的目的？能否达到互斥的目的？设变量是设变量是flag2，且初值为：，且初值为：flag0=flag1=0;进程进程Pi:/ /*i=0或或1*/ /flagi=1;while(flag(i+1)%2=1);Pi的临界区代码；的临界区代码；flagi=0;这个题目相对比较容易。这个题目相对比较容易。学生很容易看出，两个进程可能会发生相互阻塞

151、学生很容易看出，两个进程可能会发生相互阻塞的现象。的现象。167时间时间语句语句执行进程执行进程T0时刻时刻flag0=10T1时刻时刻flag1=11T2时刻时刻while(flag0=1);P1忙等忙等T3时刻时刻while(flag1=1);P0忙等忙等考虑下列事件序列：考虑下列事件序列：P0、P1在在while语句上无限循环，都不能进入临界语句上无限循环，都不能进入临界区。故上述算法不能用来实现互斥。区。故上述算法不能用来实现互斥。168选择题选择题：关于临界区问题的一个算法（假设只有进程：关于临界区问题的一个算法（假设只有进程P1和和P2可能会进入临界区）如下可能会进入临界区）如下(

152、i为为0或或1)，该算法（，该算法（）。（浙）。（浙大大1998）a.不能保证进程互斥进入临界区，且会出现不能保证进程互斥进入临界区，且会出现“饥饿饥饿”（Starvation）b.不能保证不能保证进程进程互斥进入临界区，但不会出现互斥进入临界区，但不会出现“饥饿饥饿”c.能保证能保证进程进程互斥进入临界区，但会出现互斥进入临界区，但会出现“饥饿饥饿”d.能保证能保证进程进程互斥进入临界区，不会出现互斥进入临界区，不会出现“饥饿饥饿”repeatretry:if(turn-1)turn=i;if(turni)gotoretry;turn=-1;CriticalSection（临界区）（临界区）

153、turn=0;RemainderSection（其他区域）（其他区域）untilfalse;答案：答案：a169分析：按下面的执行序列，说明不能保证互斥：分析：按下面的执行序列，说明不能保证互斥：T0时刻时刻：P1判断判断turn-1，将，将turn置为置为0，判断第，判断第二个二个if条件不满足，准备执行条件不满足，准备执行turn=-1T1时刻时刻：P2判断判断turn-1，将，将turn置为置为0，判断第，判断第二个二个if条件不满足，执行条件不满足，执行turn=-1并进入并进入临界区临界区T2时刻时刻：P1进入临界区。进入临界区。即即P1、P2都进入了临界区，故该算法不能保证互斥。都

154、进入了临界区，故该算法不能保证互斥。170下面是出现下面是出现“饥饿饥饿”的情况的情况(设开始时设开始时turn=0)：时间语句句执行行进程程T0if(turn!=-1)trun=0P1T1if(turn!=-1)turn=1;P2T2因因turn!=0执行行gotoretry;P1T3if(turn!=-1)trun=0P1T4因因turn!=1执行行gotoretry;P2T5if(turn!=-1)turn=1;P2T6因因turn!=0执行行gotoretry;P1T7if(turn!=-1)trun=0P1T8因因turn!=1执行行gotoretry;P2T9if(turn!=-1

155、)turn=1;P2如此循环往复，如此循环往复，P1、P2都不能进入各自的临界去，都不能进入各自的临界去，“饿死饿死”。171另外还有可用于多个进程互斥的面另外还有可用于多个进程互斥的面包店算法包店算法(bakeryalgorithm)，可参，可参看有关书看有关书(例如：孟静编的例如：孟静编的操作系操作系统教程统教程原理和实例分析原理和实例分析)，在，在此不再赘述。此不再赘述。1722.6 进程通信进程通信 n进程通信进程通信进程之间的信息交换。进程之间的信息交换。n进程之间的互斥和同步，交换的信息量少进程之间的互斥和同步，交换的信息量少低级通信低级通信。 n信号量机制作为通信工具不够理想，表

156、现在：信号量机制作为通信工具不够理想，表现在： n效率低效率低； n通信对用户不透明通信对用户不透明。 n本节介绍进程本节介绍进程高级通信高级通信是指用户可直接利是指用户可直接利用用OSOS所提供的一组通信命令，高效地传送大量所提供的一组通信命令，高效地传送大量数据的一种通信方式。数据的一种通信方式。 n高级通信过程对用户是高级通信过程对用户是透明透明的。大大减少了通的。大大减少了通信程序编制的复杂性。信程序编制的复杂性。 1732.6.1 进程通信的类型进程通信的类型高级通信机制可归结为三类：高级通信机制可归结为三类： 共享存储器通信；共享存储器通信； 管道通信管道通信(共享文件共享文件)；

157、 消息传递通信。消息传递通信。n直接通信方式直接通信方式n间接通信方式间接通信方式信箱通信信箱通信单机单机(集中式集中式)适合单机或网络适合单机或网络1741共享存储器系统共享存储器系统（Shared-Memory System ）（1）基于共享数据结构的通信方式基于共享数据结构的通信方式如生产者如生产者-消费者问题中，是用有界缓冲区这消费者问题中，是用有界缓冲区这种数据结构来实现通信的。种数据结构来实现通信的。公用数据结构的设置及对进程间同步的处理，公用数据结构的设置及对进程间同步的处理，都是程序员的职责，增加了程序员的负担，而都是程序员的职责，增加了程序员的负担，而操作系统只需提供共享存储

158、器。操作系统只需提供共享存储器。低效的通低效的通信方式（低级通信）信方式（低级通信）175n先向系统申请共享存储区中的一个分区，并指定该先向系统申请共享存储区中的一个分区，并指定该分区的关键字；分区的关键字；n若系统已经将该分区分配给其它进程，则将其描述若系统已经将该分区分配给其它进程，则将其描述符返回给申请者；符返回给申请者； n申请者将获得的共享存储分区连接到本进程上；申请者将获得的共享存储分区连接到本进程上； n此后，便可象读写普通存储器那样地读写该公用存此后，便可象读写普通存储器那样地读写该公用存储分区。储分区。UNIX/LINUX与之有关的系统调用有与之有关的系统调用有4个个（2）基

159、基于于共共享享存存储储区区的的通通信信方方式式：在在存存储储区区中中划划出出一一块块共共享享存存储储区区，诸诸进进程程可可通通过过对对共共享享存存储储区区中中数数据据的的读读和和写写来来实实现现通通信信。属属于于高级通信方式高级通信方式。 1762管道管道( (pipe) )通信通信 管道管道用于连接一个读进程和一个写进程以实现它们之间通用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又称信的一个共享文件，又称pipe文件。文件。 首创于首创于UNIX系统系统 写进程以字节流的形式将大量数据送入管道；写进程以字节流的形式将大量数据送入管道； 读进程从管道中接收（读）数据。读进程

160、从管道中接收（读）数据。 由于发送进程和接收进程由于发送进程和接收进程是通过管道进行通信的，是通过管道进行通信的，故称为管道通信。故称为管道通信。为协调双方的通信，管道机制必须提供以下三方面的协调能力：为协调双方的通信，管道机制必须提供以下三方面的协调能力： 互斥互斥当一个进程正在对当一个进程正在对pipe执行读执行读/写操作时，其它进程必须写操作时，其它进程必须等待；等待；同步同步确定对方是否存在确定对方是否存在当写进程把一定数据写入当写进程把一定数据写入pipe，便去睡眠等待，直至，便去睡眠等待，直至读进程取走数据后，再把它唤醒；当读进程读一空读进程取走数据后，再把它唤醒；当读进程读一空p

161、ipe时，也应睡眠等待，直至写进程将数据写入时，也应睡眠等待，直至写进程将数据写入pipe后，再把它唤醒。后，再把它唤醒。 只有确定对方已存在时，才能进行通信。只有确定对方已存在时，才能进行通信。 177 3消息传递系统消息传递系统 (Message passing system) 其通信方式其通信方式 直接通信方式直接通信方式 间接通信方式间接通信方式( (邮箱方式邮箱方式) )消息传递机制消息传递机制用得最广泛的一种高级通信机制用得最广泛的一种高级通信机制(单机系统、多机系统、计算机网络单机系统、多机系统、计算机网络)。n进程间的数据交换进程间的数据交换,是以格式化的消息是以格式化的消息(

162、message)为为单位的。单位的。n计算机网络中，计算机网络中，message又称为报文。又称为报文。n利用系统提供的一组通信命令（原语）进行通信。利用系统提供的一组通信命令（原语）进行通信。nOS隐蔽了通信实现细节，大大简化了通信程序编制隐蔽了通信实现细节，大大简化了通信程序编制的复杂性，因而得到广泛应用。的复杂性，因而得到广泛应用。n微内核与服务器的通信采用信息传递机制。微内核与服务器的通信采用信息传递机制。1781. 直接通信方式直接通信方式 是指发送进程利用是指发送进程利用OS所提供的命令，直接把消息发送给目标所提供的命令，直接把消息发送给目标进程。进程。 要求发送和接收进程都以显式

163、方式提供对方的标识符。两要求发送和接收进程都以显式方式提供对方的标识符。两条通信原语为：条通信原语为： send（Receiver，message）；）； 发送一个消息发送一个消息message给给接收进程接收进程Receiver receive（Sender，message）；）； 接收接收Sender发来发来的消息的消息message 有时，接收进程可能与多个发送进程通信，故不可能事先知有时，接收进程可能与多个发送进程通信，故不可能事先知道发送进程。对于这样的应用，接收原语中的源进程参数，道发送进程。对于这样的应用，接收原语中的源进程参数，是完成通信后的返回值。接收原语可表示为：是完成通信

164、后的返回值。接收原语可表示为：receive（id，message）； id是返回值（标识符）是返回值（标识符） 2.6.2 消息传递通信的实现方法消息传递通信的实现方法179我我们们可可以以用用直直接接通通信信原原语语来来解解决决生生产产者者-消消费费者者问问题题。当当生生产产者者生生产产一一个个产产品品(消消息息)后后，用用send原原语语将将消消息息发发送送给给消消费费者者；而而消消费费者者用用receive原原语语来来得得到到一一个个消消息息。若若消消息息尚尚未未到到达达，消消费费者者必必须须等等待待，直直到到生生产产者者将将消消息息发发送送过过来来(此此处处是是指指无无界界缓缓冲冲区

165、区，故故没没提提生生产产者者阻阻塞塞问问题题。而而以以前前我我们们考考虑虑的的是是有有界界缓缓冲冲区问题区问题)。生产者。生产者-消费者的通信可描述如下：消费者的通信可描述如下：repeat.produceaniteminnextp;send(consumer,nextp);untilfalserepeatreceive(producer,nextc);.consumetheiteminnextc;untilfalse1802. 间接通信方式间接通信方式 是指进程之间的通信，需要通过作为共享数是指进程之间的通信，需要通过作为共享数据结构的实体据结构的实体信箱。信箱。 信箱暂存发送进程发送给目标

166、进程的消息；信箱暂存发送进程发送给目标进程的消息；接收进程从信箱中取出对方发给自己的消息。接收进程从信箱中取出对方发给自己的消息。 既可实现实时通信，也可实现非实时通信。既可实现实时通信，也可实现非实时通信。 181系统为信箱通信提供了若干条原语系统为信箱通信提供了若干条原语： （1）信箱的创建和撤消信箱的创建和撤消。信箱可由。信箱可由OS创建，创建， 也可由用户用也可由用户用OS命令创建。命令创建。 （2）消息的发送和接收消息的发送和接收。send（mailbox，message）；）；receive（mailbox，message）；）； 将一个消息将一个消息message发送到指发送到指

167、定的信箱定的信箱mailbox 从指定信箱从指定信箱mailbox接收消息接收消息message 1822.6.3 消息传递系统实现中的消息传递系统实现中的 进程同步方式进程同步方式 三种情况：三种情况： （1）发送进程阻塞、接收进程阻塞发送进程阻塞、接收进程阻塞 两个进程平时都处于阻塞状态，直到有消息传递时。两个进程平时都处于阻塞状态，直到有消息传递时。 主要用于发送进程和接收进程之间主要用于发送进程和接收进程之间无缓冲时的进程之间紧密同步。无缓冲时的进程之间紧密同步。 这种同步方式称为汇合这种同步方式称为汇合 （2）发送进程不阻塞、接收进程阻塞发送进程不阻塞、接收进程阻塞 接收进程如服务器

168、上通常都设置了多个服务进程，接收进程如服务器上通常都设置了多个服务进程， 分别用于提供不同的服务分别用于提供不同的服务 ：如打印服务：如打印服务 应用最广泛的进程同步方式应用最广泛的进程同步方式 （3）发送进程和接收进程均不阻塞发送进程和接收进程均不阻塞 发送进程和接收进程都忙于自己的事情，仅当发生某发送进程和接收进程都忙于自己的事情，仅当发生某 事件使它无法继续执行时，才把自己阻塞起来等待事件使它无法继续执行时，才把自己阻塞起来等待 也是较常见的进程同步形式也是较常见的进程同步形式 有消息队列时采用有消息队列时采用1832.6.4 消息缓冲队列通信机制消息缓冲队列通信机制美国的美国的hans

169、an提出，被广泛应用于提出，被广泛应用于本地进程本地进程之间的通信之间的通信 1.1.消息缓冲队列通信机制中的数据结构消息缓冲队列通信机制中的数据结构 1）消息缓冲区消息缓冲区其结构可描述如下：其结构可描述如下：2）PCB中有关通信的数据项中有关通信的数据项 【浦计略浦计略】184structmessage_bufferlongsender；/发送者进程标识符发送者进程标识符intsize；/消息长度消息长度chartextN；/消息正文消息正文structmessage_buffer*next；/指指向向下下一一个个消消息息缓缓冲冲区的指针区的指针；1）消息缓冲区消息缓冲区其结构可描述如下：

170、其结构可描述如下：1852）PCB中有关通信的数据项中有关通信的数据项mq；/消息队列首指针消息队列首指针mutex；/消息队列互斥信号量消息队列互斥信号量sm；/消息队列资源信号量消息队列资源信号量1862.2.发送原语发送原语send(receiver,a)getbuf(a.size,i);根据根据a.size申请缓冲区申请缓冲区ii.sender=a.sender;i.size=a.size;i.text=a.text;i.next=0;将将a中信息复制到中信息复制到消息缓冲区消息缓冲区i中中getid(PCBset,receiver.j);获得接收进程内部标识符获得接收进程内部标识符w

171、ait(j.mutex);insert(j.mq,i);将消息缓冲区插入到消息队列中将消息缓冲区插入到消息队列中signal(j.mutex);signal(j.sm);资源数目增资源数目增1(有可能唤醒接收进程有可能唤醒接收进程)1873.3.接收原语接收原语 receive(b)j=internalname;j为接收进程内部标识符为接收进程内部标识符wait(j.sm);wait(j.mutex);remove(j.mq,i);将消息队列中第一个消息将消息队列中第一个消息i移出移出signal(j.mutex);将消息缓冲区将消息缓冲区i中消中消息复制到接收区息复制到接收区bb.sende

172、r=i.senderb.size=i.sizeb.text=i.text从从自自己己的的消消息息缓缓冲冲队队列列mq 中中，摘摘下下第第一一个个消消息息缓缓冲冲区区i，并并将将其其中中的的数数据据复复制制到以到以b为首址的指定消息接收区内。为首址的指定消息接收区内。思考思考：用消息缓冲队列的发送和接收原语实现：用消息缓冲队列的发送和接收原语实现PC问题。问题。188send(B,a) sender:Asize:5text:Helloa发发送送区区amq mutexsmPCB(B)sender:Asize:5text:Hellonext:0进程进程Areceive(b) sender:Asize

173、:5text:Hellob进程进程B接接收收区区b第一个消息缓冲区第一个消息缓冲区图图2-12消息缓冲通信消息缓冲通信消息缓冲队列通信原理如图消息缓冲队列通信原理如图2-12(下图下图)所示。所示。1892.7 线程线程 n20世世纪纪60年年代代人人们们提提出出了了进进程程概概念念后后，在在OS中中一一直直都都是是以以进进程程为为能能拥拥有有资资源源和和独独立立运运行行的的基基本单位的。本单位的。n直直到到20世世纪纪80年年代代中中期期，人人们们又又提提出出了了比比进进程程更更 小小 的的 能能 独独 立立 运运 行行 的的 基基 本本 单单 位位 线线 程程（Threads）。试试图图用

174、用它它来来提提高高系系统统内内程程序序并并发执行的程度，从而进一步提高系统的吞吐量发执行的程度，从而进一步提高系统的吞吐量n进进入入20世世纪纪90年年代代后后，多多处处理理机机系系统统得得到到迅迅速速发发展展，线线程程能能比比进进程程更更好好地地提提高高程程序序的的并并发发执执行行程程度度，充充分分地地发发挥挥多多处处理理机机的的优优越越性性，因因而而近近几几年年所所推推出出的的多多处处理理机机OS，都都引引入入了了线线程程，以改善以改善OS的性能。的性能。1902.7.1 线程的基本概念线程的基本概念1线程的引入线程的引入OS引入线程，目的是减少程序在引入线程，目的是减少程序在并发执行时所

175、付出的时空开销。并发执行时所付出的时空开销。 进程进程“太重太重”，系统在进程上所花的时空开销大，系统在进程上所花的时空开销大致表现在：致表现在： 1 1）创建进程）创建进程 系系统统在在创创建建进进程程时时必必须须为为它它分分配配除除CPU以以外外的的所所有有资资源源，如如内内存存空空间间、I/O设设备备，以以及及建建立立相相应应的的PCB。 2 2）撤消进程）撤消进程 系统撤消进程时，必须先回收其所占的资源，然后系统撤消进程时，必须先回收其所占的资源，然后再撤消再撤消PCB。 191总总之之，由由于于进进程程是是一一个个资资源源拥拥有有者者，因因而而在在创创建建、撤撤消消、切切换换中中，系

176、系统统必必须须为为之之付付出出较较大大的的时时空空开开销销，故故系系统统中中的的进进程程数数目目不不宜宜过过多多，进进程程切切换换的的频频率率也也不宜过高，这限制了并发程度的进一步提高。不宜过高，这限制了并发程度的进一步提高。 3 3）进程切换）进程切换 进进程程切切换换时时，由由于于要要保保留留当当前前进进程程的的CPU环环境境和和设设置新进程的置新进程的CPU环境，因而需花费不少处理机时间。环境，因而需花费不少处理机时间。 192进进程程既既是是资资源源分分配配的的额额基基本本单单位位，又又是是调调度度和和分分派派的的基基本本单单位位。若若能能将将进进程程的的上上述述两两个个属属性性分开，

177、由操作系统分开处理，即分开，由操作系统分开处理，即 n对于作为调度和分派的基本单位，不同时作为拥对于作为调度和分派的基本单位，不同时作为拥有资源的基本单位，以做到有资源的基本单位，以做到“轻装上阵轻装上阵”； n而对于拥有资源的基本单位，又不对之进行频繁而对于拥有资源的基本单位，又不对之进行频繁的切换。的切换。 在这种思想指导下，形成了线程概念。线程只作为。线程只作为调度和分派的基本单位，而不作为资源分配的基本调度和分派的基本单位，而不作为资源分配的基本单位。一个进程通常包括多个线程。单位。一个进程通常包括多个线程。 1932.线程与进程的比较线程与进程的比较从调度性、并发性、系统开销和拥有资

178、源等方面对从调度性、并发性、系统开销和拥有资源等方面对线程和进程进行比较。线程和进程进行比较。1) 调度调度在传统操作系统中，作为拥有资源的基本单位和独在传统操作系统中，作为拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引入线程立调度、分派的基本单位都是进程。而在引入线程的操作系统中，则把线程作为调度和分派的基本单的操作系统中，则把线程作为调度和分派的基本单位，而进程作为拥有资源的基本单位，把传统进程位，而进程作为拥有资源的基本单位，把传统进程的两个属性分开，使线程基本上不拥有资源，这样的两个属性分开，使线程基本上不拥有资源，这样线程就能轻装前进，从而可显著地提高系统的并发线程就能

179、轻装前进，从而可显著地提高系统的并发程度。在同一进程中，线程切换不会引起进程切换，程度。在同一进程中，线程切换不会引起进程切换，但从一个进程的线程切换到另一个进程中的线程时，但从一个进程的线程切换到另一个进程中的线程时，将会引起进程的切换。将会引起进程的切换。1942) 并发性并发性在在引引进进线线程程的的操操作作系系统统中中，不不仅仅进进程程之之间间可可以以并并发发执执行行，而而且且在在一一个个进进程程中中的的多多个个线线程程之之间间也也可可并并发发执执行行，这这使使得得操操作作系系统统具具有有更更好好的的并并发发性性，从从而而能能更更加加有有效效地地提提高高系系统统资资源源的的利利用用率率

180、和和系系统统的的吞吞吐吐量量。例例如如，在在一一个个未未引引入入线线程程的的单单CPU系系统统中中，若若仅仅设设置置一一个个文文件件服服务务进进程程，当当该该进进程程由由于于某某种种原原因因而而被被阻阻塞塞时时，便便没没有有其其他他的的文文件件服服务务进进程程来来提提供供服服务务。在在引引入入线线程程的的操操作作系系统统中中，则则可可以以在在一一个个文文件件服服务务进进程程中中设设置置多多个个服服务务线线程程。当当第第一一个个线线程程等等待待时时，文文件件服服务务进进程程的的第第二二个个线线程程可可以以继继续续运运行行，以以提提供供文文件件服服务务；当当第第二二个个线线程程阻阻塞塞时时，则则可

181、可由由第第三三个个线线程程继继续续执执行行，提提供供服服务务。显显然然，这这样样的的方方法法可可以以显显著著地地提提高高文文件件服服务务的的质质量量和和系统的吞吐量。系统的吞吐量。1953) 拥有资源拥有资源不不论论是是传传统统的的操操作作系系统统，还还是是引引入入线线程程的的操操作作系系统统，进进程程都都可可以以拥拥有有资资源源，是是系系统统中中拥拥有有资资源源的的一一个个基基本单位。本单位。一一般般而而言言，线线程程自自己己不不拥拥有有系系统统资资源源(也也有有一一点点不不可可少少的的资资源源)，但但它它可可以以访访问问隶隶属属进进程程的的资资源源(包包括括进进程程的的代代码码段段、数数据

182、据段段以以及及所所拥拥有有的的系系统统资资源源，如如已已打打开开的的文文件件、I/O设设备备等等，可可以以供供该该进进程程中中的的所所有线程锁共享有线程锁共享)。1964) 系统开销系统开销在在创创建建或或撤撤销销进进程程时时，系系统统都都要要为为之之创创建建或或回回收收进进程程控控制制块块，分分配配或或回回收收资资源源(如如内内存存空空间间和和I/O设设备备等等)，操操作作系系统统所所付付出出的的开开销销明明显显大大于于线线程程创创建建或或撤销时的开销。撤销时的开销。类类似似地地，在在进进程程切切换换时时，涉涉及及到到当当前前进进程程的的CPU环环境境的的保保护护及及新新被被调调度度运运行行

183、进进程程的的CPU环环境境的的设设置置，而而线线程程的的切切换换仅仅需需保保存存和和设设置置少少量量寄寄存存器器内内容容，不不涉涉及及存存储储器器管管理理方方面面的的操操作作，所所以以就就切切换换代代价价而而言言，进进程程也也远远高高于于线线程程。此此外外，由由于于进进程程中中多多个个线线程程具具有有相相同同的的地地址址空空间间，在在同同步步和和通通信信的的实实现现方方面面，线线程也比进程容易。程也比进程容易。1973.线程的属性线程的属性每个线程都作为分配每个线程都作为分配CPU的基本单位，是花费最小开销的的基本单位，是花费最小开销的实体。实体。 线程具有以下属性线程具有以下属性： （1）轻

184、型实体）轻型实体 线程基本上不拥有系统资源，只是有一点线程基本上不拥有系统资源，只是有一点必不可少的、能保证独立调度和分派的资必不可少的、能保证独立调度和分派的资源。如，线程控制块源。如，线程控制块TCBTCB。 （2）独立调度和分派的基本单位）独立调度和分派的基本单位 切换非常迅速和开销小。切换非常迅速和开销小。 （3）可并发执行）可并发执行 一个进程的多个线程甚至全部线程可以并一个进程的多个线程甚至全部线程可以并发执行；不同进程的线程也能并发执行。发执行；不同进程的线程也能并发执行。 （4）共享进程资源）共享进程资源 同一进程的所有线程，都可共享该进同一进程的所有线程，都可共享该进程所拥有

185、的资源。程所拥有的资源。 1984线程的状态线程的状态在在OS中的每一个线程都可以用线程标识符和一组状中的每一个线程都可以用线程标识符和一组状态参数进行描述。态参数进行描述。 状态参数包括状态参数包括： u寄存器状态：寄存器状态：程序计数器程序计数器PCPC和堆栈指针内容和堆栈指针内容 u堆栈：堆栈：通常保存局部变量和返回地址通常保存局部变量和返回地址 u线程运行状态：线程运行状态：执行状态、就绪状态、阻塞状态执行状态、就绪状态、阻塞状态 u优先级优先级 u线程专用存储器：线程专用存储器：用于保存线程自己的局部变量拷贝用于保存线程自己的局部变量拷贝 u信号屏蔽：信号屏蔽：对某些信号加以屏蔽对某

186、些信号加以屏蔽 1992.7.2 线程间的同步和通信线程间的同步和通信1.互斥锁互斥锁（mutex）l是一种用于对资源互斥访问的机制。是一种用于对资源互斥访问的机制。l由于时间和空间开销较低，因而适合于高频度使用的关由于时间和空间开销较低，因而适合于高频度使用的关键共享数据和程序段。键共享数据和程序段。l互斥锁有两种状态：互斥锁有两种状态：u开锁开锁(unlock)状态状态用用unlock命令将命令将mutex打开打开u关锁关锁(lock)状态状态用用lock命令命令(函数函数)将将mutex关上关上l当一个线程需要读当一个线程需要读/写一个共享数据时，线程首先应为写一个共享数据时，线程首先应

187、为该数据段设置的该数据段设置的mutex执行开锁命令：先判断执行开锁命令：先判断mutex的的状态，若它已处于关锁状态，则试图访问该数据段的线状态，若它已处于关锁状态，则试图访问该数据段的线程将被阻塞；若程将被阻塞；若mutex处于开锁状态，则将处于开锁状态，则将mutex关上关上后，便去读后，便去读/写该数据段。写该数据段。l线程完成对数据的读线程完成对数据的读/写后，须发出开锁命令将写后，须发出开锁命令将mutex打打开，同时还需将阻塞在该互斥锁上的一个进程唤醒。开，同时还需将阻塞在该互斥锁上的一个进程唤醒。200为了减少线程被阻塞的机会，有的系统中还提供了为了减少线程被阻塞的机会，有的系

188、统中还提供了一种用于一种用于mutex上的操作命令上的操作命令TRYLOCK。当一个线程利用当一个线程利用TRYLOCK命令访问命令访问mutex时，时，n若若mutex处处于于开开锁锁状状态态，TRYLOCK返返回回一一个个指示成功的状态码；指示成功的状态码；n若若mutex处处于于关关锁锁状状态态，则则TRYLOCK并并不不会会阻阻塞塞该该线线程程，而而是是返返回回一一个个指指示示操操作作失失败败的的状状态码。态码。2012.条件变量条件变量在许多情况下，只利用互斥锁在许多情况下，只利用互斥锁mutex来实现互斥访来实现互斥访问，可能会引起死锁。问，可能会引起死锁。例如例如，有一线程在对有

189、一线程在对mutex1执行关锁操作成功后，便进入执行关锁操作成功后，便进入临界区临界区C，若在临界区内该线程又需访问某个临界，若在临界区内该线程又需访问某个临界资源资源R，同样也为，同样也为R设置另一个互斥锁设置另一个互斥锁mutex2。假。假如资源如资源R此时正处于忙碌状态，线程在对此时正处于忙碌状态，线程在对mutex2执执行关锁操作后必将被阻塞，这样，将使行关锁操作后必将被阻塞，这样，将使mutex1一直一直保持关锁状态；如果保持了资源保持关锁状态；如果保持了资源R的进程也要求进的进程也要求进入临界区入临界区C，但由于，但由于mutex1一直保持关锁状态而无一直保持关锁状态而无法进入临界

190、区，这样便形成了死锁。法进入临界区，这样便形成了死锁。为此引入了为此引入了条件变量条件变量。每一个条件变量通常都与一。每一个条件变量通常都与一个互斥锁一起使用。个互斥锁一起使用。2023.信号量机制信号量机制1 1）私用信号量）私用信号量同一进程的各线程间同步，进程自己设置，对同一进程的各线程间同步，进程自己设置，对OSOS不可见。不安全不可见。不安全2 2）公用信号量）公用信号量OSOS管理，安全管理，安全2032.7.3 线程的实现线程的实现n内内核核级级线线程程: : 线线程程管管理理的的全全部部工工作作由由OS内内核核来来做做，内内核核专专门门提提供供了了一一个个KLT(Kernel

191、Level Threads)应应用用程程序序设设计计接接口口(API)供供开发者使用。例如开发者使用。例如Windows 2000/XPn用用户户级级线线程程: : 线线程程管管理理的的全全部部工工作作由由应应用用程程序序来来做做，在在用用户户空空间间内内实实现现，内内核核是是不不知知道道线线程程的的存存在在的的。线线程程库库是是线线程程运运行行的的支支撑环境。撑环境。n混合式线程混合式线程（例如（例如Solaris）204第一次课内上机实验第一次课内上机实验以下四个上机实验，以下四个上机实验，每个学生可任选一个实验每个学生可任选一个实验。1.进程的创建进程的创建2.线程的创建和并发执行线程的

192、创建和并发执行3.进程同步进程同步4.进程通信进程通信205进程的创建进程的创建 (2学时学时) 上机实验要求上机实验要求本本实实验验要要求求设设计计一一个个实实现现进进程程创创建建的的程程序序，使使所所创创建建的的进进程程在在处处理理机机上上并并发发执执行行，要要求求程程序序能能对对出出现现的的异异常常进进行行报报告告。通通过过本本上上机机实实验验，学学会会在在Win32程程序序中中使使用用操操作作系系统统提提供供的的API创创建建进进程程，并并通通过过所所创创建的进程的运行情况获得对于进程并发的感性认识。建的进程的运行情况获得对于进程并发的感性认识。详细请参看详细请参看Word文档：文档：

193、“操作系统课内上机指导书操作系统课内上机指导书2012.doc”的上机实验一的上机实验一206程序的总体框架程序的总体框架 程程序序将将“test.txt”文文件件作作为为输输入入，该该文文本本文文件件的的每每一一行行都都是是有有一一个个应应用用程程序序名名以以及及该该应应用用程程序序的的参参数数构构成成 (应应 用用 程程 序序 名名 和和 参参 数数 由由 空空 格格 隔隔 开开 )。 程程 序序 从从“test.txt”文文件件中中依依次次读读出出每每一一行行存存入入cmdline字字符符串串中中，再再以以cmdline为为函函数数实实参参数数，调调用用NewProc()函函数数，通通过

194、过CreateProcess()这这个个Win32API函函数数来来建建立立一一个个 新新 进进 程程 ， 在在 该该 进进 程程 中中 运运 行行 对对 应应 的的 应应 用用 程程 序序 。“test.txt”文文件件是是在在记记事事本本中中预预先先编编制制好好的的一一个个文文本，其文件内容如下：本，其文件内容如下：Process1Process2Process3Process14207命命令令行行“Process1”也也可可写写成成“Process.exe1”。Process.exe是是当当前前目目录录中中的的可可执执行行文文件件名名，它它为为了了测测试试进进程程的的并并发发执执行行而而

195、自自行行编编制制的的，其其源源代代码码在在下下面面介介绍绍。上上述述4个个命命令令行行中中，第第4个个 命命 令令 是是 为为 了了 测测 试试 出出 错错 信信 息息 的的 ， 其其 错错 误误 是是 应应 用用 程程 序序Process1.exe不存在。测试程序不存在。测试程序Process.exe的的C+源代码如下：源代码如下：#include#include/Sleep()voidmain(intargc,char*argv) /执行时可带参数的程序执行时可带参数的程序unsignedintwt,x;x=(unsignedint)&wt;x=x*atoi(argv1);srand(x)

196、;/使用变量使用变量wt的地址作为随机序列的的地址作为随机序列的“种子种子”for(inti=0;i50;i+)/显示进程正在运行的信息，其中命令参数显示进程正在运行的信息，其中命令参数argv1作为进程的编号作为进程的编号couti+1:Processargv1正在运行！正在运行！endl;wt=200+rand()%2000;Sleep(wt);/睡眠等待睡眠等待2002200ms208需要说明的是，本实验的用来创建进程的命令行的需要说明的是，本实验的用来创建进程的命令行的可执行程序名，也可以是可执行程序名，也可以是GUI的应用程序，例如，的应用程序，例如，命令行命令行“c:windows

197、notepad.exe1.txt”将打开将打开“记事本记事本”窗口，同时在记事本窗口中打开文本文窗口，同时在记事本窗口中打开文本文件件“1.txt”(如果如果1.txt文件存在的话文件存在的话)。程序所用程序所用Win32API函数函数1GetLastError()函数函数2FormatMessage()函数函数3CreateProcess()函数函数详细请参看详细请参看Word文档文档“操作系统课内上机指导书操作系统课内上机指导书2012.doc”的上机实验一的上机实验一209线程的创建和并发执行线程的创建和并发执行 (2学时学时) 上机实验要求上机实验要求本本实实验验要要求求编编写写一一个

198、个程程序序，完完成成多多个个线线程程的的创创建建，使使得得所所创创建建的的多多线线程程在在处处理理机机上上并并发发执执行行。通通过过本本实实验验，学学习习在在Win32程程序序中中利利用用操操作作系系统统提提供供的的API创创建建线线程程，并并通通过过所所创创建建线线程程的的运运行行情情况况来来获获得得关关于于多多线线程程并并发发的的感感性性认认识识，以以及及加加深深对对临临界界资资源源(本本实验中临街资源是屏幕实验中临街资源是屏幕)互斥访问的理解。互斥访问的理解。210程序的总体框架程序的总体框架 程程序序启启动动时时由由系系统统系系统统创创建建一一个个进进程程来来执执行行程程序序，此此时时

199、进进程程只只包包含含一一个个主主线线程程，该该主主线线程程执执行行程程序序的的main代码。代码。主主线线程程运运行行时时首首先先等等待待用用户户键键入入要要创创建建的的线线程程数数(赋赋予予变变量量iThread)，以以及及每每个个线线程程运运行行的的时时间间(秒秒数数，赋赋予予变变量量wRunTime)，接接着着调调用用API函函数数GetSystemTime()获获得得当当前前的的系系统统时时间间(格格林林威威治治时时间间)，计计算算出出新新线线程程的的生生命命结结束束点点时时间间(均均用用北北京京时时间间)；然然后后循循环环调调用用函函数数CreateThread()来来创创建建iTh

200、read个个子子线线程程，这这些些子子线线程程执执行行同同一一段段代代码码(threadwork()函函数数)；最最后后，主主线线程程根根据据系系统统时时间间判判断断这这些些子子线线程程的的生生命命周周期期是是否否结结束束，当到达子线程结束时刻，则关当到达子线程结束时刻，则关runFlag。211各各子子线线程程：在在每每个个子子线线程程执执行行的的这这段段代代码码(函函数数threadwork()的的代代码码)中中，首首先先给给出出本本线线程程开开始始运运行行的的提提示示信信息息(不不同同线线程程用用线线程程号号区区别别，线线程程号号是是主主线线程程创创建建子子线线程程时时传传递递给给子子线

201、线程程的的，程程序序中中传传送送的的是是循循环环控控制制变变量量i的的值值作作为为子子线线程程号号的的)，然然后后循循环环判判断断runFlag是是否否被被主主线线程程关关闭闭，未未关关则则显显示示“几几号号线线程程第第几几次次动动作作”的的提提示示，睡睡眠眠一一段段随随机机时时间间；当当runFlag关关时时，子子线线程程结结束束循循环环，显显示示“几几号号线线程程已结束已结束”字样，然后调用字样，然后调用return语句结束本线程。语句结束本线程。212程序所用程序所用Win32API函数函数1CreateThread()函数函数2GetSystemTime()函数函数3Initializ

202、eCriticalSection()函数函数4EnterCriticalSection函数函数5LeaveCriticalSection函数函数6Sleep()函数函数详细请参看详细请参看Word文档文档“操作系统课内上机指导书操作系统课内上机指导书2012.doc”的上机实验二的上机实验二213进程同步（进程同步（2学时）学时） 上机实验要求和目的上机实验要求和目的 编编写写一一个个程程序序，实实现现生生产产者者-消消费费者者问问题题的的同同步步算算法法。通通过过程程序序运运行行时时的的输输出出信信息息，可可以以清清楚楚地地看看到到在在“生生产产者者-消消费费者者”进进程程模模型型中中，各各

203、进进程程的的活活动动情情况况，从从而而加加深深对对进进程程同同步步问问题题的的理理解解，了了解解同同步步算算法法的的程序实现方法。程序实现方法。通通过过本本上上机机实实验验的的训训练练，应应该该较较容容易易地地用用本本实实验验的的思思路路，编编程程实实现现读读者者-写写者者问问题题和和哲哲学学家家进进餐餐问问题题等等进程同步问题的算法演示。进程同步问题的算法演示。214数据结构数据结构 描述生产者描述生产者-消费者问题的类消费者问题的类sy_pc：classsy_pcprivate:intin;/生产者使用的循环缓冲区的下标生产者使用的循环缓冲区的下标intout;/消费者使用的循环缓冲区的下

204、标消费者使用的循环缓冲区的下标intcount;/循环缓冲区的个数循环缓冲区的个数HANDLEempty;/指向生产者的私有信号量指向生产者的私有信号量HANDLEfull;/指向消费者的私有信号量指向消费者的私有信号量HANDLEmutex;/指示互斥信号量指示互斥信号量lpBufferbuffer;/指向一个循环缓冲区指向一个循环缓冲区public:sy_pc(int);/构造函数构造函数voidgetbuffer(lpBuffer);/从缓冲区取出一个从缓冲区取出一个“产品产品”voidputbuffer(Buffer);/向缓冲区放入一个向缓冲区放入一个“产品产品”sy_pc();/析

205、构函数析构函数;215程序的总体设计思想程序的总体设计思想 定定义义类类sy_pc的的一一个个全全局局对对象象s_pc，其其循循环环缓缓冲冲中中缓缓冲冲区区个个数数为为10。定定义义全全局局对对象象的的目目的的是是简简化化各各生生产产者者进进程程(线线程程)和和消消费者进程费者进程(线程线程)共享信号量、缓冲区等资源，简化程序。共享信号量、缓冲区等资源，简化程序。在在类类sy_pc的的构构造造函函数数中中，利利用用Win32API函函数数CreateSemaphore()创创建建3个个信信号号量量对对象象，这这3个个对对象象的的句句柄柄分分别别是是empty、full和和mutex。empty

206、所所指指的的信信号号量量对对象象的的初初值值为为10(即即循循环环缓缓冲冲的的缓缓冲冲区区个个数数)；full所所指指的的信信号号量量对对象象的的初初值值为为0，即即初初始始状状态态，满满缓缓冲冲区区个个数数为为0；mutex所所指指的的信信号号量量对对象象的的初初值值为为1，用用于于互互斥斥访访问问共共享享变变量量in或或out。关关于于Semaphore对对象象以以及及相相关关API函数将在下面介绍。函数将在下面介绍。在在成成员员函函数数putbuffer()和和getbuffer()中中，利利用用跟跟SemaphoreObjects有有关关的的wait函函数数和和release函函数数来

207、来实实现现同同步步。这这些些函函数数将在后面具体介绍。将在后面具体介绍。详细请参看详细请参看“操作系统课内上机指导书操作系统课内上机指导书2012.doc”的上机实验三的上机实验三216进程通信（进程通信（2学时）学时） 上机实验内容和要求上机实验内容和要求要要 求求 设设 计计 实实 现现 一一 个个 进进 程程 间间 通通 信信 (InterprocessCommunication)的的程程序序，而而不不是是同同一一进进程程的的多多个个线线程程之之间间的的通通信信。Win32API提提供供了了多多种种进进程程间间通通信信的的方方法法，包包括括剪剪贴贴板板(Clipboard)、COM(OL

208、E)、动动态态数数据据交交换换(DynamicDataExchange， DDE)、 文文 件件 影影 像像 (File Mapping)、 邮邮 件件 槽槽(Mailslot)、管管道道(Pipes)、远远程程过过程程调调用用(RPC)、Windows套套接接字字(WindowsSockets)等等。本本实实验验采采用用相相对对比比较较容容易易实实现现的的有有名名管管道道(NamedPipe)实实现现进进程程间间的的通通信信。学学生生也也可可采采用用FileMapping自自行行设设计计本本实实验验。FileMapping的的使使用用可可参参考考P_C2文件夹中程序。文件夹中程序。217实验

209、总体设计实验总体设计 本实验是在本实验是在Windows2000/XP+VC+6.0环境下利用环境下利用Win32API设计实现的；进程通信机制采用有名管道；程序分两个设计实现的；进程通信机制采用有名管道；程序分两个部分，即部分，即Namedpipeserver和和Namedpipeclient。服务器设计成多线程管道服务器，其总体框架是服务器设计成多线程管道服务器，其总体框架是：1首先创建一个工作线程首先创建一个工作线程(WorkThread)，它的任务是创建，它的任务是创建若干个进程若干个进程(pipeclient)；2主线程开始无限循环：调用主线程开始无限循环：调用CreateNamed

210、Pipe创建一个创建一个有名管道实例；调用有名管道实例；调用ConnectNamedPipe等待管道客户进程等待管道客户进程请求服务；若有客户进程请求管道连接，则创建一个子线程请求服务；若有客户进程请求管道连接，则创建一个子线程来为该客户提供服务来为该客户提供服务(与该客户实现管道双向通信与该客户实现管道双向通信)；主线程；主线程返回循环开头。返回循环开头。3若没有客户请求连接，则关闭刚创建的管道实例若没有客户请求连接，则关闭刚创建的管道实例(namedpipeinstance)的句柄后重新循环。的句柄后重新循环。218管道客户程序的总体框架是管道客户程序的总体框架是：1调用调用CreateF

211、ile函数获得服务器创建的管道实例的句柄；函数获得服务器创建的管道实例的句柄；2调用调用WaitNamedPipe函数，等待函数，等待(请求请求)与服务器的管道与服务器的管道连接；连接；3若连接成功，如需要可则调用若连接成功，如需要可则调用SetNamedPipeHandleState按需要设置管道的读模式等；按需要设置管道的读模式等；4调用调用WriteFile函数向服务器发送请求信息；等待并接受函数向服务器发送请求信息；等待并接受服务器的应答信息服务器的应答信息(用用ReadFile函数实现函数实现)。这样循环往复，。这样循环往复，实现与服务器的双向通信，指导完成通信任务后结束进程。实现与

212、服务器的双向通信，指导完成通信任务后结束进程。服务器的子线程也是用服务器的子线程也是用ReadFile和和WriteFile函数实现与客户函数实现与客户进程的通信的。进程的通信的。详细请参看详细请参看“操作系统课内上机指导书操作系统课内上机指导书2012.doc”的上机实验四的上机实验四219练习题练习题3下列的进程状态变化中，下列的进程状态变化中，的变化是不可能的变化是不可能发生的。发生的。A.运行运行就绪就绪B.运行运行等待等待C.等待等待运行运行D.等待等待就绪就绪4.进程和程序的本质区别是进程和程序的本质区别是。存储在内存和外存存储在内存和外存B.顺序和非顺序执行机器指令顺序和非顺序执

213、行机器指令C.分时使用和独占使用计算机资源分时使用和独占使用计算机资源D.动态和静态特征动态和静态特征2205.某进程所要求的一次打印输出结束，该进程被唤某进程所要求的一次打印输出结束，该进程被唤醒，其进程状态将从醒，其进程状态将从。A.就绪状态到运行状态就绪状态到运行状态B.等待状态到就绪状态等待状态到就绪状态C.运行状态到等待状态运行状态到等待状态D.运行状态到就绪状态运行状态到就绪状态10.两个进程合作完成一个任务，在并发执行中，两个进程合作完成一个任务，在并发执行中，一个进程要等待其合作伙伴发来消息，或者建一个进程要等待其合作伙伴发来消息，或者建立某个条件后再向前执行，这种关系称为进程

214、立某个条件后再向前执行，这种关系称为进程间的间的。A.同步同步B.互斥互斥C.竞争竞争D.合作合作22114.进程从等待状态转到就绪状态的原因可能是进程从等待状态转到就绪状态的原因可能是。A.请求请求I/OB.I/O完成完成C.被进程调度程序选中被进程调度程序选中D.另一个进程运行结束另一个进程运行结束16某个进程从等待状态进入就绪状态可能是由某个进程从等待状态进入就绪状态可能是由于于。A.现运行进程运行结束现运行进程运行结束B.现运行进程执行了现运行进程执行了P操作操作C.现运行进程执行了现运行进程执行了V操作操作D.现运行进程时间片用完现运行进程时间片用完22221下述各项中，下述各项中，D不是引起进程切换的直不是引起进程切换的直接原因。接原因。A.运行进程的时间片用完运行进程的时间片用完B.运行进程出错运行进程出错C.运行进程要等待某一事件发生运行进程要等待某一事件发生D.有新进程进入就绪状态有新进程进入就绪状态24操作系统中，对信号量操作系统中，对信号量S的的P原语操作定义中，原语操作定义中，使进程进入相应等待队列的条件是使进程进入相应等待队列的条件是。S0B.S0返回总目录返回总目录223