第2章进程管理下

1、12.3 进程同步进程同步 进程同步的主要任务：进程同步的主要任务：对对多个相关进程在执行次序上进行多个相关进程在执行次序上进行协调，以协调，以使并发执行的诸进程之间能有效地使并发执行的诸进程之间能有效地共享资源共享资源和和相相互合作互合作，从而使程序的执行具有可再现性，从而使程序的执行具有可再现性。2.3.1 进程同步的基本概念进程同步的基本概念1. 两种形式的制约关系两种形式的制约关系(1) (1) 间接相互制约关系间接相互制约关系 源于资源共享（互斥方式）源于资源共享（互斥方式）(2) (2) 直接相互制约关系直接相互制约关系 源于进程合作（同步方式）源于进程合作（同步方式）2n互斥互斥

2、：同步的特例，多个操作决不能同时执行，如：同步的特例，多个操作决不能同时执行，如:进程和进程共用一台打印机的情形。进程和进程共用一台打印机的情形。n同步同步：对于进程操作的时间顺序所加的某种限制，：对于进程操作的时间顺序所加的某种限制，如如输入进程输入进程I I和计算进程和计算进程C C共用一个缓冲区的情形共用一个缓冲区的情形, ,输输入进程入进程I I必须在计算进程必须在计算进程C C之前完成。之前完成。2.3 进程同步进程同步 A打印机打印机B I缓冲区缓冲区C3 必须互斥访问的资源称为临界资源必须互斥访问的资源称为临界资源 2. 临界资源临界资源互斥访问互斥访问例如：有两个进程共享一个例

3、如：有两个进程共享一个count变量，当两个进程按以下顺变量，当两个进程按以下顺序执行时：序执行时：P1P2n1=count;n2=count;n1=n1+1;n2=n2+1;count=n1; count=n2;假定假定count初值为初值为0，如果先执行，如果先执行P1，后执行，后执行P2，最后，最后count变量的值为变量的值为24但如果按下列顺序并发执行：P1：n1=count;P2：n2=count;P1：n1=n1+1;count=n1;P2：n2=n2+1;count=n2; 尽管P1与P2都有各自对count做了加1操作，但最后的count却是增加1，即发生了与执行顺序有关的错

4、误。 为防止这种错误，对临界资源为防止这种错误，对临界资源count必须互斥必须互斥访问。即访问。即P1访问访问count变量，变量，P2就不能访问；当就不能访问；当P1访问结束时，才允许访问结束时，才允许P2访问访问count变量。变量。 2. 临界资源临界资源互斥访问互斥访问5 每个进程中访问临界资源的那段代码每个进程中访问临界资源的那段代码对欲访问的临界资源进行检查，对欲访问的临界资源进行检查， 进入区进入区若此刻未被访问，设正在访问的标志若此刻未被访问，设正在访问的标志访问临界资源访问临界资源 临界区临界区将正在访问的标志恢复为未被访问的标志将正在访问的标志恢复为未被访问的标志退出区退

5、出区其余部分其余部分 剩余区剩余区repeat entry section critical section exit section remainder sectionuntil false3. 临界区临界区63. 临界区临界区对临界资源设一访问标志对临界资源设一访问标志flag对对flag检查，看是否被访问？检查，看是否被访问？ 该进程可以进入临界区，该进程可以进入临界区，并设置已被访问标志并设置已被访问标志该进程不能进入临界区该进程不能进入临界区YN进入临界区流程74. 同步机制应遵循的准则同步机制应遵循的准则 空闲让进空闲让进 无进程处于临界区内时，可让一个申请进入该无进程处于临界区内

6、时，可让一个申请进入该临界区的进程进入。临界区的进程进入。 忙则等待忙则等待 临界区内有进程时，申请进入临界区的进程必临界区内有进程时，申请进入临界区的进程必须等待。须等待。 有限等待有限等待 进程进入临界区的请求，必须在有限的时间内进程进入临界区的请求，必须在有限的时间内满足。满足。 让权等待让权等待 等待进入临界区的进程，必须立即放等待进入临界区的进程，必须立即放CPU。8信号量机制信号量机制中心街道 楼宇 1小区A小区 B城市公路进程92.3.2 解决方法解决方法信号量机制信号量机制 1、信号量机制、信号量机制 1965年荷兰学者年荷兰学者Dijkstra 提出信号量机制，是一个提出信号

7、量机制，是一个卓有卓有成效成效的进程同步机制。的进程同步机制。2、信号量的发展、信号量的发展 整型信号量、记录型信号量、整型信号量、记录型信号量、AND型信号量和信号量集型信号量和信号量集机制。机制。 102.3.2 解决方法解决方法信号量机制信号量机制 11整型信号量整型信号量整型量，除初始化外，仅能通过两个原子操作来访问。整型量，除初始化外，仅能通过两个原子操作来访问。P P操作操作 wait(S):wait(S): While S=0 do no-op; While S0S0表示可获得这个临界资源的进程个数表示可获得这个临界资源的进程个数 S=0S=0表示等待该临界资源的进程个数表示等待

8、该临界资源的进程个数P P操作：申请资源操作：申请资源 V V操作：释放资源操作：释放资源2.3.2 解决方法解决方法信号量机制信号量机制12 整型信号量未遵循整型信号量未遵循“让权等待让权等待”原则，导致忙等原则，导致忙等 引入整型变量引入整型变量value(value(代表资源数目代表资源数目) )、进程链、进程链表指针表指针L(L(链接所有等待进程链接所有等待进程) )2 2 记录型信号量记录型信号量其中：其中： 信信 号号 量量 值值 表示某种资源的数量。表示某种资源的数量。 等待队列指针等待队列指针当信号量值为负时，表示该类资源已分配完，当信号量值为负时，表示该类资源已分配完，等待该

9、类资源的进程排在等待队列中。等待该类资源的进程排在等待队列中。L L为指向该信号量等待为指向该信号量等待队列的指针。队列的指针。 定义：定义： type semaphore=recordtype semaphore=record value value：integerinteger； 信号量值信号量值 L L：list of processlist of process 信号量等待队列指针信号量等待队列指针 endend；13定义：定义：VAR S：Semaphore； 1. P操作（操作（wait 原语）原语） 每作一次每作一次P操作，申请分配一个单位的资源。操作，申请分配一个单位的资源。

10、P（S） 对信号量对信号量S 进行进行P操作。操作。 S.value ：= S.Value - 1； 若若 S.Value 0 进程继续执行。进程继续执行。 若若 S.Value 0S.Value 0 进程继续执行。进程继续执行。 若若 S.Value 0S.Value 0 则释放则释放S S等待队列中的一个进程，等待队列中的一个进程， 使之转为使之转为就绪就绪状态。状态。2 2 记录型信号量记录型信号量P、V操作原语操作原语14 P 操作操作 Procedure P（s） Var s：semaphore； begin s.value：= s.value-1； if s.value 0 the

11、n block（s.L）; end； V操作操作 Procedure V（s） Var s：semaphore； begin s.value：= s.value+1； if s.value 0 then wakeup（s.L）; end；P P、V V操作的算法描述操作的算法描述2 记录型信号量记录型信号量15 说明：说明： S.Value 0S.Value 0 时，其值表示某类资源可用数量。时，其值表示某类资源可用数量。 S.ValueS.Value 0 0 时，其绝对值表示在信号量队列中等待时，其绝对值表示在信号量队列中等待 该资源的进程数。该资源的进程数。 P P、V V操作有严格的不可

12、分割性；执行过程不允许中断；操作有严格的不可分割性；执行过程不允许中断； P P、V V操作成对出现。操作成对出现。（根据同步机制的原则，分析（根据同步机制的原则，分析P P、V V操作的特点，）操作的特点，）？问题？问题？如何使用如何使用P P、V V操作实现同步机制？操作实现同步机制？实现同步机制实现同步机制基本思想是：加基本思想是：加锁、解锁锁、解锁 考虑：考虑： 如何控制互斥地使用临界资源？如何控制互斥地使用临界资源？ 如何控制进程并发执行的时序？如何控制进程并发执行的时序？2 记录型信号量记录型信号量163 信号量的应用信号量的应用 1. 利用信号量实现进程互斥利用信号量实现进程互斥

13、 例例1：用P（wait）、V（signal）原语实现3个进程（A、B、C）互斥进入临界区。设互斥信号量mutex=1A B C P(mutex) P(mutex) P(mutex)CSA CSB CSCV(mutex) V(mutex) V(mutex) 17序号调用进程被调用操作进入临界区运行的进程mutex值在mutex上等待的进程112AP(mutex)A03BP(mutex)A-1B4CP(mutex)A-2BC5AV(mutex)B-1C6BV(mutex)C07CV(mutex)13 信号量的应用信号量的应用 18 例例2：以计算进程C和打印进程P为例来描述两个进程的合作关系，试

14、用P、V原语实现。 设：计算进程与打印进程共用一个缓冲区，为此可设置两个信号量：full表示缓冲区满，令full=0；empty表示缓冲区空，令empty=13 信号量的应用信号量的应用 19计算进程与打印进程的P、V描述如下: 计算进程C 产生一个数据P(empty);往缓冲区送数据V(full); 打印进程P P(full);从缓冲区取数V(empty);输出结果 3 信号量的应用信号量的应用 20S1S2S3S4S5S6abcdegf例例3:S1,S2,S3,S4,S5,S6为一组合作进程为一组合作进程,其前趋图如其前趋图如图图,试用试用P、V原语实现这原语实现这6个进程的同步。个进程的

15、同步。3 信号量的应用信号量的应用 213 信号量的应用信号量的应用 22思考：利用信号量实现前趋关系思考：利用信号量实现前趋关系(p57)P1P3P4P2P5P63 信号量的应用信号量的应用 232.3 进程同步进程同步4. AND型信号量型信号量上述进程互斥问题，多个进程共享一个临界资源。上述进程互斥问题，多个进程共享一个临界资源。两个进程两个进程A A和和B B，共享数据，共享数据D D和和E E，为其分别设置互斥信号，为其分别设置互斥信号量量DmutexDmutex和和EmutexEmutex，初值为，初值为1 1。Process A： wait(Dmutex); wait(Emute

16、x);Process B： wait(Emutex); wait(Dmutex);Process A： wait(Dmutex); 于是于是Dmutex=0Process B： wait(Emutex); 于是于是Emutex=0Process A： wait(Emutex); 于是于是Emutex=-1 A阻塞阻塞Process B： wait(Dmutex); 于是于是Dmutex=-1 B阻塞阻塞设执行过程为设执行过程为共享的资源越多，死锁的可能越大共享的资源越多，死锁的可能越大242.3 进程同步进程同步 AND同步机制的基本思想：将进程在整个同步机制的基本思想：将进程在整个运行过程中

17、需要的所有资源，一次性全部分配给运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。只要尚有一进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其他所有可能为之分配个资源未能分配给进程，其他所有可能为之分配的资源，也不分配给它。即对临界资源的分配采的资源，也不分配给它。即对临界资源的分配采取原子操作。取原子操作。Swait(S1, S2, , Sn) if S1 =1 and and Sn=1 then for i:=1 to n do Si:= Si -1 ; endfor else Place the process in the waiting que

18、ue associated with the first Si found with Si 0）个单元的缓）个单元的缓冲区。冲区。P1每次用每次用produce（）生成一个正整数并用（）生成一个正整数并用put（）送入缓（）送入缓冲区某一空单元中；冲区某一空单元中；P2每次用每次用getodd（）从该缓冲区中取出一个（）从该缓冲区中取出一个奇数并用奇数并用countodd（）统计奇数个数；（）统计奇数个数；P3每次用每次用geteven（）从（）从该缓冲区中取出一个偶数并用该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥

19、活动，并说明所定义用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。的信号量的含义。要求用伪代码描述。 60定义信号量定义信号量S1控制控制P1与与P2之间的同步；之间的同步；S2控制控制P1与与P3之间的同步；之间的同步；empty控制控制生产者与消费者之间的同步；生产者与消费者之间的同步；mutex控制进程间互斥使用缓冲区。程序如下控制进程间互斥使用缓冲区。程序如下： Var s1=0,s2=0,empty=N,mutex=1; Parbegin P1:begin X=produce(); P(empty); P(mutex); Put(); If

20、x%2=0 V(s2); else V(s1); V(mutex); end. P2:begin P(s1); P(mutex); Getodd(); Countodd():=countodd()+1; V(mutex); V(empty); end. P3:begin P(s2) P(mutex); Geteven(); Counteven():=counteven()+1; V(mutex); V(empty); end. Parend. 612.5 进程通信进程通信 进程通信是指进程之间的信息交换。进程通信是指进程之间的信息交换。 进程之间的互斥和同步进程之间的互斥和同步低级通信（因其低

21、级通信（因其所交换的信息最少）所交换的信息最少）u如在进程互斥中，进程通过只修改信号量来向其如在进程互斥中，进程通过只修改信号量来向其它进程表明临界资源是否可用它进程表明临界资源是否可用u在生产者在生产者-消费者问题中，生产者通过缓冲池将所消费者问题中，生产者通过缓冲池将所生产的产品传送给消费者。生产的产品传送给消费者。 信号量机制作为通信工具的缺点：信号量机制作为通信工具的缺点： (1)效率低效率低 (2)通信对用户不透明通信对用户不透明。低级通信中共享数据的设置，数据的传送，进程的互斥都是由低级通信中共享数据的设置，数据的传送，进程的互斥都是由程序员去实现，操作系统只提供共享存储器，因此非

22、常不方便程序员去实现，操作系统只提供共享存储器，因此非常不方便622.5 进程通信进程通信 高级进程通信是指用户可直接利用操高级进程通信是指用户可直接利用操作系统所提供的一组作系统所提供的一组通信命令通信命令，高效地传，高效地传送大量数据的一种通信方式。操作系统隐送大量数据的一种通信方式。操作系统隐藏了进程通信的细节，对用户透明，减少藏了进程通信的细节，对用户透明，减少了通信程序编制上的复杂性了通信程序编制上的复杂性 。632.5 进程通信进程通信2.5.1 进程通信的类型进程通信的类型 低级通信低级通信高级通信高级通信(三大类三大类)共享存储器系统共享存储器系统消息传递系统消息传递系统（主要

23、用于网络）（主要用于网络）管道通信管道通信（首创于（首创于Unix系统）系统） 642.5 进程通信进程通信 1. 1. 共享存储器系统共享存储器系统 在共享存储器系统中，相互通信的进程共享某在共享存储器系统中，相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过些数据结构或共享存储区，进程之间能够通过这些空间进行通信。这些空间进行通信。 (1) 基于共享数据结构的通信方式基于共享数据结构的通信方式 (2) 基于共享存储区的通信方式基于共享存储区的通信方式652.5 进程通信进程通信 基于共享数据结构的通信方式 在这种通信方式中，诸进程公用某些数据结构，借以实现诸进程间的信息交换。 程

24、序员：公用数据结构的设置及对进程间同步的处理 操作系统：提供共享存储器(如缓冲池、缓冲区) 特点：低效，只适合传递相对少量的数据，属于低级通信。662.5 进程通信进程通信 基于共享存储区的通信方式 在存储器中划出了一块共享存储区，诸进程可通过对共享存储区中数据的读或写来实现通信。 672.5 进程通信进程通信2. 消息传递系统消息传递系统（主要用于网络）（主要用于网络） 操作系统隐藏了通信的实现细节，简化了通信程序编制的复杂性。682.5 进程通信进程通信直接通信方式发送进程直接把消息发送给目标进程发送进程和接收进程都以显式方式分别提供对方的标识符系统提供两条通信原语Send（Receive

25、r,message）;Receive（Sender,message）;例如：Send(P2,m1); Receive(P1,m1);试用直接通信方式解决生产者-消费者问题692.5 进程通信进程通信解决生产者一消费者问题解决生产者一消费者问题repeat produce an item in nextp; Send(consumer,nextp);until false; repeat Receive(producer, nextp); Consumer the item in nextc;until false;702.5 进程通信进程通信间接通信方式v进程之间的通信需要通过某种中间实体，该

26、实体用来暂存发送进程发送给目标进程的消息；接收进程则从该实体中取出对方发给自己的消息。v这种中间实体成为信箱这种中间实体成为信箱v消息在信箱中可以安全地保存，只允许核准的目标消息在信箱中可以安全地保存，只允许核准的目标用户随时读取，故可实现非实时通信。用户随时读取，故可实现非实时通信。71间接通信方式间接通信方式 信箱可由操作系统创建，也可由用户进程创建，创建者是信箱信箱可由操作系统创建，也可由用户进程创建，创建者是信箱的拥有者。据此，可把信箱分为以下三类。的拥有者。据此，可把信箱分为以下三类。1) 私用信箱私用信箱v用户进程建立，作为该进程的一部分。用户进程建立，作为该进程的一部分。v拥有者

27、有权读消息，其它用户只能发送。拥有者有权读消息，其它用户只能发送。v采用单向通信链路。采用单向通信链路。v进程结束时信箱也消失。进程结束时信箱也消失。2.5 进程通信进程通信722) 公用信箱公用信箱v它由操作系统创建。它由操作系统创建。v提供给系统中的所有核准进程使用。提供给系统中的所有核准进程使用。v进程既发送也可取出。进程既发送也可取出。v采用双向通信链路的信箱来实现。采用双向通信链路的信箱来实现。v系统运行期间始终存在。系统运行期间始终存在。3) 共享信箱共享信箱v它由某进程创建，创建指出共享进程它由某进程创建，创建指出共享进程(用户用户)的名字。的名字。v信箱的拥有者和共享者，都有权

28、从信箱中取走发送给自己的信箱的拥有者和共享者，都有权从信箱中取走发送给自己的 消息。消息。 2.5 进程通信进程通信73 在利用信箱通信时，在发送进程和接收进程之间，存在以在利用信箱通信时，在发送进程和接收进程之间，存在以下四种关系：下四种关系： (1) 一对一关系一对一关系。这时可为发送进程和接收进程建立一条两。这时可为发送进程和接收进程建立一条两者专用的通信链路，使两者之间的交互不受其他进程的干扰。者专用的通信链路，使两者之间的交互不受其他进程的干扰。 (2) 多对一关系多对一关系。允许提供服务的进程与多个用户进程之间。允许提供服务的进程与多个用户进程之间进行交互，也称为客户进行交互，也称

29、为客户/服务器交互服务器交互(client/server interaction)。 (3) 一对多关系一对多关系。允许一个发送进程与多个接收进程进行。允许一个发送进程与多个接收进程进行交互，使发送进程可用广播方式，向接收者交互，使发送进程可用广播方式，向接收者(多个多个)发送消息。发送消息。 (4) 多对多关系多对多关系。允许建立一个公用信箱，让多个进程都。允许建立一个公用信箱，让多个进程都能向信箱中投递消息；也可从信箱中取走属于自己的消息。能向信箱中投递消息；也可从信箱中取走属于自己的消息。 2.5 进程通信进程通信743. 管道通信管道通信（首创于（首创于Unix系统）系统） 所谓所谓“

30、管道管道”，是指用于连接一个读进程和一个写进程以，是指用于连接一个读进程和一个写进程以实现他们之间通信的一个实现他们之间通信的一个共享文件共享文件，又名，又名pipepipe文件。文件。 向管道提供输入的进程（称写进程），以字符流的形式将大量数据送入管道，而接受管道输出的进程（读进程）可从管道中接收数据。该方式首创于UNIX，它能传送大量数据，被广泛采用。 发送进程发送进程接收进程接收进程字符流方式写入读出字符流方式写入读出先进先出顺序先进先出顺序2.5 进程通信进程通信752.5 进程通信进程通信762.6 线程线程n引入进程的目的引入进程的目的是为了使多个程序并发执行，是为了使多个程序并发

31、执行，以提高资源利用率和系统吞吐量。以提高资源利用率和系统吞吐量。n引入线程引入线程则是为了减少程序并发执行时的所则是为了减少程序并发执行时的所付出的时空开销，使付出的时空开销，使OSOS具有更好的并发性。具有更好的并发性。n线程主要用于线程主要用于多多CPUCPU和和网络操作系统网络操作系统77进程的两个基本属性进程的两个基本属性 回忆：回忆： （1）进程是一个拥有资源的基本单位。）进程是一个拥有资源的基本单位。 （2 2）进程同时又是一个可独立调度和分派的基本单位。）进程同时又是一个可独立调度和分派的基本单位。 进程作为一个资源拥有者，在创建、撤消、切换中，进程作为一个资源拥有者，在创建、

32、撤消、切换中，系统必须为之付出较大时空开销。所以系统中进程的数系统必须为之付出较大时空开销。所以系统中进程的数量不宜过多，进程切换的频率不宜过高，但这也就限制量不宜过多，进程切换的频率不宜过高，但这也就限制了并发程度的进一步提高。了并发程度的进一步提高。78 为解决此问题，人们想到将进程的上述两个属性分为解决此问题，人们想到将进程的上述两个属性分开，即对作为调度和分派的基本单位，不同时作为开，即对作为调度和分派的基本单位，不同时作为独立分配资源的单位，应该独立分配资源的单位，应该“轻装上阵轻装上阵”；对拥有；对拥有资源的单位，不对之进行频繁切换。资源的单位，不对之进行频繁切换。 线程因而产生线

33、程因而产生。2.6 线程线程79线程的属性线程的属性 轻型实体。线程中的实体基本上不拥有系轻型实体。线程中的实体基本上不拥有系统资源统资源 独立调度和分派的基本单位。线程的切换独立调度和分派的基本单位。线程的切换非常迅速、开销小。非常迅速、开销小。 可并发执行。可并发执行。 共享进程资源共享进程资源。2.6 线程线程80 进程与程序的区别 进程是动态的，程序是静态的；进程具有并进程是动态的，程序是静态的；进程具有并发性，而程序具有顺序性；进程具有独立性，发性，而程序具有顺序性；进程具有独立性，是资源分配和调度的基本单位，而程序无此是资源分配和调度的基本单位，而程序无此特性；进程和程序间没有一一

34、对应关系；进特性；进程和程序间没有一一对应关系；进程异步运行，会相互制约，程序不具备此特程异步运行，会相互制约，程序不具备此特性。性。2.6 线程线程81 12. 设与某资源相关联的信号量初值为设与某资源相关联的信号量初值为3，当前值为，当前值为1，若，若M表示该资表示该资源的可用个数，源的可用个数，N表示等待资源的进程数，则表示等待资源的进程数，则M,N分别是（分别是（ ） A. 0，1 B. 1，0 C. 1，2 D. 2，0解：解：B829在生产者在生产者消费者问题中，能否将生产者进程的消费者问题中，能否将生产者进程的wait(empty)和和wait(mutex)语句互换，为什么？语句互换，为什么？不能。（不能。（2分）分）因为这样可能导致系统死锁。当系统中没有空缓冲时，生产者进程的因为这样可能导致系统死锁。当系统中没有空缓冲时，生产者进程的wait(mutex)操作获取了缓冲队列的控制权，而操作获取了缓冲队列的控制权，而wait(empty) 导致生产者进程导致生产者进程阻塞，这时消费者进程也无法执行。（阻塞