操作系统原理第4章进程同步与进程通信

1、操作系统原理操作系统原理Operating System Principles四川大学计算机学院段 磊2014 Spring第第4章章 进程同步与进程通信进程同步与进程通信n 进程同步使得进程之间能够相互协作和有序使用资源。n 进程通信是进程之间数据的相互交换和信息的相互传递。2021-10-21计算机操作系统- 第4章3/144本章目录n4.1 进程并发n4.2 临界区管理n4.3 信号量机制 n4.4 用信号量解决经典进程同步问题n4.5 管程n4.6 进程通信n4.7 线程的同步和通信2021-10-21计算机操作系统- 第4章4/1444.1 进 程 并 发 n并发是操作系统的基本特征

2、 n进程并发使得程序执行的特点发生了变化4.1.1 程序的顺序执行 n程序的顺序性包括n程序的内部顺序性n程序的外部顺序性 2021-10-21计算机操作系统- 第4章5/1444.1 进 程 并 发 n并发是操作系统的基本特征 n进程并发使得程序执行的特点发生了变化4.1.1 程序的顺序执行 n程序的顺序性包括n程序的内部顺序性n程序的外部顺序性 2021-10-21计算机操作系统- 第4章6/1444.1.1 程序的顺序执行n程序的内部顺序性n一个程序的操作代码在计算机处理器上按照顺序执行，一个代码结束后，后一个代码才能开始。n程序的外部顺序性n如果一项任务由多个程序模块组成，程序模块的运

3、行也需要按照调用顺序执行，即程序模块之间的顺序性。 2021-10-21计算机操作系统- 第4章7/144程序顺序执行具有的特点n顺序性n每个操作必须在上一个操作完成后才能开始；一个程序模块执行完成后另一个程序模块才能开始。n封闭性n程序运行独占系统全部资源，程序执行的结果除初始条件外，由程序本身决定，不会受到任何其它程序和外界因素的干扰。n再现性n针对相同的数据集合，程序执行的结果总是相同的。中断对程序执行的最终结果没有影响。程序执行的结果是可再现的。2021-10-21计算机操作系统- 第4章8/144程序顺序执行的不足n限制了多个程序模块的并发执行。n在多道程序并发执行环境下，处理器的利

4、用率低，系统性能差。n传统的程序顺序执行在多道程序环境下已不适合。 2021-10-21计算机操作系统- 第4章9/1444.1.2 进程的并发性n在多道程序环境下，程序是按照多个进程并发执行的。n进程的并发性是指一组进程执行在时间点上交替，在时间段上重叠。2021-10-21计算机操作系统- 第4章10/144进程的并发性n进程并发环境下，一个输入进程还没有完成，另一个计算进程已经开始；或者一个计算进程还没有完成，另一个输出进程已经开始。程序的外部顺序性不再存在。n并发进程之间可能是交互的，相关的。可能在同一时间段内，多个进程执行相同的软件代码，或多个进程共享某些变量，或多个进程请求同一硬件

5、资源，一个进程的执行可能影响到其他进程的执行结果，并发进程之间具有制约关系。2021-10-21计算机操作系统- 第4章11/144进程并发性举例n例如，两个计数程序A、B，都为：N = N + 1；print（N）；其中，计数值N是共享变量。如果N的初始值为0，程序A、B执行的顺序不同，产生的结果也不同。 2021-10-21计算机操作系统- 第4章12/144进程并发性举例（续）nA B程序A：N = N + 1；print（N）； /* 此时打印出的结果为1*/程序B：N = N + 1；print（N）； /* 此时打印出的结果为2*/2021-10-21计算机操作系统- 第4章13/

6、144进程并发性举例（续）nB A程序B：N = N + 1；print（N）； /* 此时打印出的结果为1*/程序A：N = N + 1；print（N）； /* 此时打印出的结果为2*/2021-10-21计算机操作系统- 第4章14/144进程并发性举例（续）nA B A B (A、B交替进行)程序A：N=N+1；程序B：N=N+1；程序A：print(N)；/* 此时打印出的结果为2*/程序B：print(N)；/* 此时打印出的结果为2*/程序运行出现了不可再现性！程序运行出现了不可再现性！2021-10-21计算机操作系统- 第4章15/144进程并发执行的特点n间断性n多个并发进

7、程共享处理器，执行过程是断断续续的，呈现间断性。n制约性n并发进程存在相互制约关系，系统必须对运行次序进行协调。n不可再现性n并发进程交替执行，如果存在共享变量等关系，程序执行的先后不同，会使共享变量的值不同。n失去封闭性n一个进程的执行环境与其它进程有关，程序执行失去了封闭性。n进程并发执行充分利用计算机资源，提高了效率。2021-10-21计算机操作系统- 第4章16/1444.1.3 进程间的竞争和协作n并发执行的进程以各自的速度向前推进，相互之间构成了相互竞争资源相互竞争资源和相互协作相互协作的关系。1进程间的竞争n多道程序并发执行环境下，进程的执行失去了封闭性。并发进程相互共处在一个

8、系统中，一个进程的执行必然会影响到其他进程。 2021-10-21计算机操作系统- 第4章17/144进程间的竞争 n共享的资源分为：n互斥共享资源互斥共享资源：只有一个进程对资源访问，访问结束并释放后，另外的进程才能访问该资源。n同时共享资源同时共享资源：多个进程可并发访问，不需要一个进程访问结束，其他的进程就可访问的资源。n进程对互斥共享资源的竞争要求OS对进程操作采取，从时间上和顺序上加以限制，使得进程之间相互制约地使用这些资源，保证资源的完整性。 2021-10-21计算机操作系统- 第4章18/144进程间的协作n由于每个进程都以独立地不可知的速度向前推进，需要具有协作关系的进程需要

9、在某些协调点上、，使得双方都能够顺利地运行直至完成。n协作的进程之间存在数据或变量等的，进程的推进顺序受到一定的限制，进程推进需要按照特定的顺序进行，否则会发生进程执行结果的不可再现不可再现与不确定不确定的情况。 2021-10-21计算机操作系统- 第4章19/144进程间的协作n在并发进程之间存在相互协作关系时，系统需要采取同步措施，确保进程以合理的顺序推进，确保进程运行的可再现性和结果的确定性。n并发进程之间的互斥共享资源关系最终也是进程之间的一种协作关系，即并发进程协作共享资源，也是进程同步关系。 2021-10-21计算机操作系统- 第4章20/1444.1.4 进程同步n生产者和消

10、费者问题n并发进程的共享资源问题n并发进程之间的协作问题 2021-10-21计算机操作系统- 第4章21/144生产者与消费者问题n问题描述n一个有限空间的共享缓冲区，负责存放货物n生产者向缓冲区中放物品，缓冲区满则不能放n消费者从缓冲区中拿物品，缓冲区空则不能拿生产者进程生产者进程消费者进程消费者进程（如何体现进程的同步）（如何体现进程的同步）2021-10-21计算机操作系统- 第4章22/144生产者与消费者问题n缓冲池：数组表示，具有n个(0，1，n-1)缓冲区n输入指针in：指示下一个可投放产品的缓冲区n输出指针out：指示下一个可从中获取产品的缓冲区n缓冲池采用循环组织，故：n输

11、入指针加1表示成 in:= (in+1) mod n； n输出指针加1表示成out:= (out+1) mod n。n当 (in+1) mod n = out时表示缓冲池满；而in=out则表示缓冲池空。n整型变量counter：生产者进程投放产品使counter加1；消费者进程取走产品使counter减1。nVar n，integer；ntype item=；nvar buffer: array0，1，n-1 of item；nin，out: 0，1，n-1；ncounter: 0，1，n； 2021-10-21计算机操作系统- 第4章23/144生产者与消费者问题生产者进程producer

12、: repeatproduce an item in nextp；while counter=n do no-op；bufferin:=nextp；in:=in+1 mod n；counter:=counter+1；until false； 消费者进程 consumer: repeat while counter=0 do no-op；nextc:=bufferout；out:=(out+1) mod n；counter:=counter-1；consumer the item in nextc； until false； 2021-10-21计算机操作系统- 第4章24/144生产者、消费者

13、进程分析 n生产者进程 消费者进程n不存在资源的竞争，不会出现问题。n生产者进程和消费者进程并发运行n生产者进程和消费者进程对缓冲区竞争使用n出现生产者进程与消费者进程之间不能协作的问题。n当缓冲区中已经装满产品时，生产者进程得到缓冲区的访问权，生产者进程无法进行生产。n生产者进程与消费者进程都需要对变量counter进行访问，对共享变量的访问可能造成数据不一致。2021-10-21计算机操作系统- 第4章25/144生产者与消费者问题n问题的出现n两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述：（问题何在？）（问

14、题何在？）register1:=counter； register2:=counter；register1:=register1+1；register2:=register2-1；counter:=register1； counter:=register2； 2021-10-21计算机操作系统- 第4章26/144生产者与消费者问题register1:=counter； register2:=counter；register1:=register1+1；register2:=register2-1；counter:=register1； counter:=register2； register

15、1:=counter； (register1=5)register1:=register1+1； (register1=6)register2:=counter； (register2=5)register2:=register2-1； (register2=4)counter:=register1； (counter=6)counter:=register2； (counter=4) 程序的执行已经失去了再现性。为了预防产程序的执行已经失去了再现性。为了预防产生这种错误，解决此问题的关键是应把变量生这种错误，解决此问题的关键是应把变量countercounter作为临界资源处理，亦即，令生产

16、者作为临界资源处理，亦即，令生产者进程和消费者进程互斥地访问变量进程和消费者进程互斥地访问变量countercounter。2021-10-21计算机操作系统- 第4章27/144生产者与消费者问题nA1B1A2B2A3B3n经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为9，最后count的值为9。nA1A2A3B1B2B3n经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为10，最后count的值为10。nA1B1A2B2B3A3ncount的值为11。n在进程并发环境下，竞争使用的资

17、源和共享访问的变量，如果在程序中不采取同步措施，实现互斥访问和有序访问，则会出现数据不一致等问题。A1: register1:=counter； B1: register2:=counter；A2: register1:=register1+1； B2: register2:=register2-1；A3: counter:=register1； B3: counter:=register2； 2021-10-21计算机操作系统- 第4章28/144生产者与消费者问题nA1B1A2B2A3B3n经过寄存器register1得到的count值为11，经过寄存器register2得到的count值

18、为9，最后count的值为9。nA1A2A3B1B2B3n经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为10，最后count的值为10。nA1B1A2B2B3A3ncount的值为11。n在进程并发环境下，竞争使用的资源和共享访问的变量，如果在程序中不采取同步措施，实现互斥访问和有序访问，则会出现数据不一致等问题。2021-10-21计算机操作系统- 第4章29/144本章目录n4.1 进程并发n4.2 临界区管理n4.3 信号量机制 n4.4 用信号量解决经典进程同步问题n4.5 管程n4.6 进程通信n4.7 线程的同步和通信2021

19、-10-21计算机操作系统- 第4章30/144再次说明：程序的制约方式n间接制约方式n由于竞争相同资源而引起的，得到资源的程序段可以投入运行，而得不到资源的程序段就是暂时等待，直至获得可用资源时再继续运行。n直接制约方式n通常在那些逻辑上相关的程序段之间发生的，一般是由于各种程序段要求共享信息引起的。2021-10-21计算机操作系统- 第4章31/144进程同步n基本概念n制约关系的两种形式n临界资源n临界区n信号量机制n整型、记录型、AND型、信号量集n信号量的应用n实现进程互斥n实现前趋关系2021-10-21计算机操作系统- 第4章32/144进程的同步（直接作用）n进程的同步：sy

20、nchronismn指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。n具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态2021-10-21计算机操作系统- 第4章33/144进程的互斥（间接作用）nmutual exclusionn由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥 n临界资源：critical resourcen系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量2021-10-21计算机操

21、作系统- 第4章34/144“司机售票员”问题（同步）司机进程司机进程While(True) 启动公车；启动公车； 驾驶公车；驾驶公车； 停止公车；停止公车；售票员进程售票员进程While(True) 关车门；关车门； 卖车票；卖车票； 开车门；开车门；正确运行过程正确运行过程While(True) （售票员）关车门（售票员）关车门 （司机）启动公车；（司机）启动公车； （司机）驾驶公车；（司机）驾驶公车； （售票员）卖车票（售票员）卖车票 （司机）停止公车；（司机）停止公车； （售票员）开车门；（售票员）开车门；2021-10-21计算机操作系统- 第4章35/144Spooler目录问题（

22、互斥）Out：4In：7进程进程A：N_f_s = In; /In = 7 InsertFileIntoSpooler(N_f_s); In=N_f_s+; /In = 8进程进程B：N_f_s = In; /In = 8 InsertFileIntoSpooler(N_f_s); In=N_f_s+; /In = 94：File15：File26：File37：Null8：NullSpooler目录目录进程切换，一切正常进程切换，一切正常2021-10-21计算机操作系统- 第4章36/144Spooler目录问题（互斥）2021-10-21计算机操作系统- 第4章37/1444.2.1 临

23、界资源和临界区n互斥共享的资源称为。n在生产者和消费者进程中，缓冲区和变量count都是临界资源。n在程序中对临界资源访问的代码部分称为。n进程访问临界资源前都要判断该资源能否访问，n如果能访问，进入到临界区访问临界资源；n如果不能访问，则需要等待，直到该资源能够访问；n访问结束后，需要将资源归还，使其他进程能够知道临界资源已经被当前进程访问结束。2021-10-21计算机操作系统- 第4章38/144临界资源和临界区n步骤n临界资源与临界区While ( 1 ) entry_section; /申请进入critical_section; /临界区exit_section;/声明退出2021-

24、10-21计算机操作系统- 第4章39/1444.2.2 进程同步准则n空闲让进：n当无进程在互斥区时，任何有权使用互斥区的进程可进入n忙则等待：n不允许两个以上的进程同时进入互斥区n有限等待：n任何进入互斥区要求应在有限时间内得到满足n让权等待：n处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权2021-10-21计算机操作系统- 第4章40/144进程同步准则n程序设计时，进入区是判别能否访问临界进入区是判别能否访问临界资源的关键资源的关键。1.如果进程能访问临界资源，则通过进入区，进入临界区访问临界资源；2.否则，进程不能进入临界区访问临界资源；3.当进程访问临界

25、资源完后，通过退出区，释放临界资源。 2021-10-21计算机操作系统- 第4章41/1444.2.3 早期的临界区管理方法 1软件方法n 软件方法在共享内存的单处理机或多处理机系统中实现进程的并发。n 软件方法假定基于内存访问级别的一些基本互斥，对内存同一位置的同时访问将被排序，而访问的顺序并不事先指定。n 不需要硬件或操作系统或程序设计语言的任何支持。 2021-10-21计算机操作系统- 第4章42/144早期的临界区管理方法 软件方法n算法1：临界区标志法n为了实现临界区的管理，采用标志来表示哪个并发进程可以进入临界区访问。n确保每次只有一个进程进入临界区，但强制两个进程轮流进入临界

26、区。违背进程同步机制中“空闲让进”原则 n算法2：先判断对方进程标志的进程数组标志法n进程每次访问临界资源前，首先查看其他进程访问临界资源的标志。如果其他进程标志处于正在访问，则进程等待。n违背了“忙则等待”的同步准则 2021-10-21计算机操作系统- 第4章43/144早期的临界区管理方法 软件方法n算法3：先设置自己标志的进程数组标志法 n违背了“空闲让进”的同步准则 n算法4：双标志法n标志flag用于表示每个进程是否访问临界资源，标志turn用于表示临界资源此时是否有对方进程在访问。n应用性非常方便的进程同步算法 n在临界区访问标志算法中，出现了违背“忙则等待”或“空闲让进”准则的

27、根本原因在于管理临界区标志要用两条指令，一条指令是看对方的标志，一条指令是设置自己的标志。 2021-10-21计算机操作系统- 第4章44/144早期的临界区管理方法 硬件方法2硬件方法n要保证进程在执行这两条指令时不被中断，可以采取锁的方式。如果临界区没有被访问，则锁是打开的，在进程访问临界区时，只要进程一进入临界区，则系统立即上锁，直到访问临界区的进程离开临界区才打开锁。 n测试锁和上锁这两个操作不能分开，否则会造成多个进程测试到锁打开而同时上锁的现象，引起冲突。n进程在执行这两个操作期间在处理器上的运行不能被中断。软件方法来解决有一定局限性和难度，现一般借助于硬件设施。2021-10-

28、21计算机操作系统- 第4章45/144早期的临界区管理方法 硬件方法n优点：n实现简单：只需要硬件指令就可实现。n适用性强：可用于多并发进程单CPU系统或共享内存多CPU系统。n支持多个临界区：每个临界区用单独的变量定义，对临界区的多少没有限制，可支持多个临界区。n缺点：n耗费处理器时间：采用忙等待，处理器空闲时间增多。n进程产生饥饿现象：一个进程离开临界区并唤醒阻塞等待的其它进程，可能阻塞更早的进程长期得不到唤醒，产生饥饿现象。n可能产生死锁：在单处理器系统中，进程执行特殊指令并进入临界区，拥有更高优先级的进程抢占，但得不到没有释放的临界资源，于是这两个进程发生死锁。2021-10-21计

29、算机操作系统- 第4章46/144早期的临界区管理方法 硬件方法（1）禁止中断方法n最简单的方法n影响计算机效率n不能及时处理重要程序n在多处理器下方法失效 （2）测试并建立指令（3）对换指令2021-10-21计算机操作系统- 第4章47/144本章目录n4.1 进程并发n4.2 临界区管理n4.3 信号量机制 n4.4 用信号量解决经典进程同步问题n4.5 管程n4.6 进程通信n4.7 线程的同步和通信2021-10-21计算机操作系统- 第4章48/144信号量机制信号量（semaphore）机制 n解决并发进程同步的工具 n在信号量同步机制中，有“检测”和“归还”两个重要的操作 n荷

30、兰语 “Proberen” 的意思为“检测”，用P操作表示；n荷兰语 “Verhogen” 的意思为“增量”，用V操作表示。“增量”即增加一个可以使用的临界资源，也就是“归还”的意思。 2021-10-21计算机操作系统- 第4章49/144信号量机制nP操作表示同步进程发出的检测信号量操作，检测是否能够使用临界资源n如果能使用，则检测通过，进程可以访问临界资源；n如果不能使用，则等待，直到访问临界区的进程将临界资源归还后，等待的进程才能够访问临界资源。nV操作表示访问完临界资源的进程通知等待进程已经完成了临界资源的访问，将临界资源释放。 2021-10-21计算机操作系统- 第4章50/14

31、4信号量机制n信号量机制强调P操作和V操作都是。n原子操作是不可分割的操作，原语。即通常所说的“要么做，要么不做”，而不可能操作没有完成就被终止。 2021-10-21计算机操作系统- 第4章51/1444.3.1 整型信号量 n整型信号量n设S为一个需要初始化值的正整型量。对S的访问只能通过P、V操作。 nP操作wait（S）： while S0 do no-op S:S1;nV操作signal（S）： S:S1;2021-10-21计算机操作系统- 第4章52/144整型信号量nS0，表示临界资源可以访问，P(s)中的检测语句通过，调用P(s)的进程可以访问临界资源。nS0，表示有进程在访

32、问临界资源，此时临界资源处于忙，调用P(s)的进程只能等待，直到s的值大于0，才可以访问临界资源。 2021-10-21计算机操作系统- 第4章53/144整型信号量的应用实现进程互斥例4-3 输入进程和计算进程共用缓冲区，如图所示。输入进程I和计算进程P并发执行，缓冲区是竞争访问的临界资源，缓冲区的大小为n。用整型信号量实现进程同步。公共缓冲区公共缓冲区P PI I为缓冲区设置整型信号量mutex;设mutex的初值为1将各进程对临界区访问置于P(mutex)和V(mutex)之间2021-10-21计算机操作系统- 第4章54/144整型信号量的应用实现进程互斥Pi: /* 输入进程 */

33、 begin while(输入未完成) P(mutex); /* 如果缓冲区装满，则等待 */ 将一批输入数据放入缓冲区; V(mutex); end;Pc： /* 计算进程 */ begin while(计算未完成) P(mutex); /* 如果缓冲区为空，则等待 */ 从缓冲区中拿出一批数据; V(mutex); 计算; end;coend;2021-10-21计算机操作系统- 第4章55/144整型信号量的应用实现进程互斥例4-3 分析：对于输入进程： 只要缓冲区没有装满，进程就能将数据输入到缓冲区中。 缓冲区是否装满：需要用P(mutex)去检测，如果P(mutex)检测通过，则进程

34、能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。2021-10-21计算机操作系统- 第4章56/144整型信号量的应用实现进程互斥例4-3 分析：对于输入进程： 只要缓冲区没有装满，进程就能将数据输入到缓冲区中。 缓冲区是否装满：需要用P(mutex)去检测，如果P(mutex)检测通过，则进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。对于计算进程： 只要缓冲区不为空，则进程能够从缓冲区中取走数据。 缓冲区是否为空，需要用P(mutex)去检测，如果P(mutex)检测通过，进程能够

35、访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。2021-10-21计算机操作系统- 第4章57/144整型信号量的应用实现进程互斥例4-3 分析：对于输入进程： 只要缓冲区没有装满，进程就能将数据输入到缓冲区中。 缓冲区是否装满：需要用P(mutex)去检测，如果P(mutex)检测通过，则进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。对于计算进程： 只要缓冲区不为空，则进程能够从缓冲区中取走数据。 缓冲区是否为空，需要用P(mutex)去检测，如果P(mutex)检测通过，进程能够访问

36、缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。对于输入进程和计算进程： 如果两个进程都能够访问缓冲区，哪个进程先访问缓冲区，关键在于哪个进程先执行P(mutex)。 先执行的进程先进入缓冲区访问；后执行P(mutex)的进程等待，直到先进入缓冲区访问的进程用V(mutex)释放缓冲区为止。2021-10-21计算机操作系统- 第4章58/144整型信号量的应用实现进程同步例4-3 在例4-3的基础上，当输入进程和计算进程之间共用的缓冲区中只能装入一条数据时，用整型信号量实现输入进程和计算进程的同步。公共缓冲区公共缓冲区P PI I当缓冲区中只能装入

37、一条数据时，输入进程每次放入一条数据后，要等待计算进程取走数据才能再放入下一条数据。设置两个整型信号量is和ps用于输入进程和计算进程协调访问缓冲区初值分别设置为1和02021-10-21计算机操作系统- 第4章59/144Pi: /* 输入进程 */ begin while(输入未完成) P(is); 将一批输入数据放入缓冲区; V(ps); end;Pc： /* 计算进程 */ begin while(计算未完成) P(ps); 从缓冲区中拿出一批数据; V(is); 计算; end;coend;整型信号量的应用实现进程同步2021-10-21计算机操作系统- 第4章60/144整型信号量

38、的应用实现进程同步例4-4 分析：信号量的设置是关键： 将信号量is的初值设置为1，ps的初值设置为0。 总是输入进程先进入缓冲区放入数据，计算进程先等待。 输入进程将一条数据放入缓冲区后释放ps，计算进程才能进入缓冲区取走一条数据。对于输入进程： 如果计算进程没有进入缓冲区取走一条数据，输入进程不能再进入缓冲区放数据，因为输入进程需要计算进程释放缓冲区is。对于计算进程： 如果没有输入进程释放缓冲区ps，计算进程不能多次连续进入缓冲区取走数据。2021-10-21计算机操作系统- 第4章61/144整型信号量的应用实现进程前趋图a,b,c,d,e,f,g:semaphore : = 0,0b

39、egin S1;signal(a);signal(b);end;begin wait(a);S2;signal(c);signal(d);end;begin wait(b);S3;signal(e);end;begin wait(c);S4;signal(f);end;begin wait(d);S5;signal(g);end;begin wait(e);wait(f);wait(g); S6;end;S1S2S4S3S5S6S1S2S4S3S5S62021-10-21计算机操作系统- 第4章62/1444.3.2 记录型信号量n在整型信号量中，P操作开始需要测试临界资源是否能够访问，即判断

40、s0是否满足。n如果满足，表示进程不能进入临界区访问，进程此时“do nothing”，即什么都不做而等待。这时的等待没有放弃CPU执行权。这违背了“让权等待”的同步准则，造成处理器资源的浪费。 2021-10-21计算机操作系统- 第4章63/144记录型信号量n解决忙等问题，实现让权等待n记录所有等待同一资源的进程 P操作操作wait（S）：）：S.value S.value1if S.value0 then block（S,L） V操作操作S.value S.value1if S.value0 then wakeup（S,L）2021-10-21计算机操作系统- 第4章64/144记录型

41、信号量理解： 记录型信号量在整型信号量的基础上进行了改进，让不能进入临界区的进程，即进程状态由运行转换为阻塞状态，进程进入阻塞队列中等待。若信号量若信号量s s的的s.values.value的值为正数，该正数表示可对信号量可的值为正数，该正数表示可对信号量可进行的进行的P P操作的次数，即实际可以使用的临界资源数。操作的次数，即实际可以使用的临界资源数。若信号量若信号量s s的的s.values.value的值为负值，表示有多个进程申请临界的值为负值，表示有多个进程申请临界资源，而又不能得到，在阻塞队列等待。资源，而又不能得到，在阻塞队列等待。s.values.value的绝对值的绝对值表示

42、在阻塞队列等待临界资源的进程个数。表示在阻塞队列等待临界资源的进程个数。2021-10-21计算机操作系统- 第4章65/1444.3.3 AND型信号量集nAND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作 nAND型信号量集的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配nAND型信号量集P原语为SwaitnAND型信号量集V原语为Ssignal2021-10-21计算机操作系统- 第4章66/144AND型信号量理解： 死锁的产生？ 死锁的预防与解决？解决的办法是将进程所需要的资源一次性地全部分配给进程，解决的办法是将进程所需要的资

43、源一次性地全部分配给进程，等进程运行完后再全部一起释放。先让一个进程完成后，另等进程运行完后再全部一起释放。先让一个进程完成后，另一个进程才申请资源，得到资源并完成。也就是将并发的进一个进程才申请资源，得到资源并完成。也就是将并发的进程分为先完成进程和后完成进程。程分为先完成进程和后完成进程。ANDAND型信号量集是将进程在运行中所需要的临界资源全部一型信号量集是将进程在运行中所需要的临界资源全部一次性分配给进程，等进程用完后再全部一起释放。如果进程次性分配给进程，等进程用完后再全部一起释放。如果进程有一个临界资源没有得到，进程也不可能推进，必须将所分有一个临界资源没有得到，进程也不可能推进，

44、必须将所分配到的临界资源全部归还。即要么全部得到向前推进，要么配到的临界资源全部归还。即要么全部得到向前推进，要么一个也不能要而等待。这样的资源分配策略可以避免死锁。一个也不能要而等待。这样的资源分配策略可以避免死锁。2021-10-21计算机操作系统- 第4章67/1444.3.4 信号量集n当进程需要申请的临界资源种类较多，每类临界资源个数较多时，如果用记录型信号量，进程每次只能一次申请或释放一个临界资源，非常麻烦。因此，引入信号量集。 2021-10-21计算机操作系统- 第4章68/144信号量机制n整型信号量n基本信号量原理n记录型信号量n多个进程申请同一类资源nAND型信号量n同一

45、进程申请多个不同资源n信号量集n同一进程申请多个同类资源n多个进程申请多个不同资源信信号号量量机机制制的的对对比比2021-10-21计算机操作系统- 第4章69/1442 信号量机制n信号量按联系进程的关系分成二类：n公用信号量（互斥信号量）n私用信号量（同步信号量） 它为一组需互斥共享临界资源的并发进程而设置，代表共享它为一组需互斥共享临界资源的并发进程而设置，代表共享的临界资源，每个进程均可对它施加的临界资源，每个进程均可对它施加P P、V V操作，即都可申请操作，即都可申请和释放该临界资源，其初始值置为和释放该临界资源，其初始值置为1 1。取值意义如下：。取值意义如下：信号量信号量s

46、s1 1 ；表示资源空闲，可供使用。；表示资源空闲，可供使用。信号量信号量s s0 0 ；表示资源已被占用，无其它进程等待。；表示资源已被占用，无其它进程等待。信号量信号量s s-n -n ；表示资源已被占用，还有；表示资源已被占用，还有n n个进程因等待资个进程因等待资源而阻塞。源而阻塞。它为一组需同步协作完成任务的并发进程而设置，它为一组需同步协作完成任务的并发进程而设置，只有拥有该资源的进程才能对它施加只有拥有该资源的进程才能对它施加P P操作（即可申操作（即可申请资源），而由其合作进程对它施加请资源），而由其合作进程对它施加V V操作（即释放操作（即释放资源）。资源）。2021-10-

47、21计算机操作系统- 第4章70/144例题补充与讲解：1n知识点：进程的前趋图n题目：n已知一个求值公式如下所示，如果A、B已赋值，请画出该公式求值过程的前趋图n思路：n分辨可以并发进行的运算n保存计算的中间结果，并为每条语句命名)5/()3(2ABBA2021-10-21计算机操作系统- 第4章71/144例题补充与讲解：12021-10-21计算机操作系统- 第4章72/144例题补充与讲解：2n知识点：信号量的应用n题目：n设有一个作业由四个进程组成，这四个进程必须按右图的次序运行，试用P、V操作表达四个进程的同步关系。n思路：n设三个同步信号量b1、b2、b3，分别表示进程T2、T3

48、、T4是否可以开始执行，初值为0。2021-10-21计算机操作系统- 第4章73/144例题补充与讲解：2b2,b3,b4:semaphore : = 0,0,0T1: . V(b2); V(b3); T2: P(b2); . V(b4); T3: P(b3); . V(b4); T4: P(b4); P(b4); . （因在T2和T3中都对b4做了V操作，所以T4要用两个P操作）2021-10-21计算机操作系统- 第4章74/144例题补充与讲解：3n知识点：信号量的应用n题目：n设有两个优先级相同的进程P1和P2如下，信号量S1和S2的初值为0。请问P1、P2并发执行结束后，x、y、z

49、的值分别是多少？进程P1 y = 1; y = y + 2; V(S1); z = y + 1; P(S2); y = z + y;进程P2 x = 1; x = x + 1; P(S1); x = y + x; V(S2); z = x + z;思路：思路：P1P1和和P2P2具有相同的优具有相同的优先级，并发，具有顺先级，并发，具有顺序的不确定性；序的不确定性；信号量信号量S1S1和和S2S2使得语使得语句的执行顺序具有了句的执行顺序具有了制约关系制约关系绘制对应的前趋图绘制对应的前趋图2021-10-21计算机操作系统- 第4章75/144例题补充与讲解：3进程P1S1: y = 1;S

50、2: y = y + 2; V(S1);S3: z = y + 1; P(S2);S4: y = z + y;进程P2S5: x = 1;S6: x = x + 1; P(S1);S7: x = y + x; V(S2);S8: z = x + z;x = 5; y = 12; z = 92021-10-21计算机操作系统- 第4章76/144提问环节关于临界区的管理n软件方法n临界区标志法n进程数组标志法1n进程数组标志法2n双标志法n硬件方法n缺陷n信号量机制n整型信号量n基本信号量原理n记录型信号量n多个进程申请同一类资源nAND型信号量n同一进程申请多个不同资源n信号量集n同一进程申请

51、多个同类资源n多个进程申请多个不同资源2021-10-21计算机操作系统- 第4章77/144本章目录n4.1 进程并发n4.2 临界区管理n4.3 信号量机制 n4.4 用信号量解决经典进程同步问题n4.5 管程n4.6 进程通信n4.7 线程的同步和通信生产者消费者问题读者写者问题哲学家就餐问题2021-10-21计算机操作系统- 第4章78/144生产者-消费者问题n假设缓冲池中有n个缓冲区，每个缓冲区存放一个消息；n可利用互斥信号量mutex使诸进程对缓冲池实现互斥访问；n利用empty和full计数信号量分别表示空缓冲及满缓冲的数量。n又假定这些生产者和消费者互相等效，只要缓冲池未满

52、，生产者可将消息送入缓冲池；只要缓冲池未空，消费者可从缓冲池取走一个消息。同步问题：同步问题：生产者：生产者：P P进程不能往进程不能往“满满”的缓冲区中放产品；的缓冲区中放产品；消费者消费者：C C进程不能从进程不能从“空空”的缓冲区中取产品。的缓冲区中取产品。2021-10-21计算机操作系统- 第4章79/144同步与互斥问题n互斥信号量nmutex：防止多个进程同时进入临界区n同步信号量nempty和full：保证事件发生的顺序n缓冲区满时，Producer停止运行n缓冲区空时，Consumer停止运行n概念差别互斥与同步（并发的两个要素）n互斥：保护临界区，防止多个进程同时进入n同步

53、：保证进程运行的顺序合理2021-10-21计算机操作系统- 第4章80/144同步/互斥信号量的使用方法n互斥信号量n必定成对出现：n进入临界区临界区退出临界区n同步信号量n未必成对出现，依赖于同步关系的性质n同步信号量和互斥信号量的操作顺序n基本原则：互斥信号量永远紧邻临界区2021-10-21计算机操作系统- 第4章81/144n生产者P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1) mod n;Signal(mutex);Signal(full);n消费者C:Wait(full);Wait(mutex);netxc=buffer

54、(out);out:=(out+1) mod n;Signal(mutex);Signal(empty);mutex,full,empty:semaphoremutex :=1;full:=0;empty:=n;生产者-消费者问题2021-10-21计算机操作系统- 第4章82/144nP：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1) mod n;Signal(mutex);Signal(full);empty=nfull=0mutex=1in,out=0生产者和消费者之间的生产者和消费者之间的约束：临界区。约束：临界区。生产者在生产时

55、，消费生产者在生产时，消费者不能消费。者不能消费。生产者-消费者问题2021-10-21计算机操作系统- 第4章83/144nP：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1) mod n;Signal(mutex);Signal(full);empty=nfull=0mutex=1in,out=0控制：控制： 缓冲区满时不能继缓冲区满时不能继续生产，制约生产者续生产，制约生产者进程进程P。生产者-消费者问题2021-10-21计算机操作系统- 第4章84/144nC：Wait(full);Wait(mutex);netxc=buffer

56、(out);out:=(out+1) mod n;Signal(mutex);Signal(empty);empty=nfull=0mutex=1in,out=0生产者和消费者之间的生产者和消费者之间的约束：临界区。约束：临界区。生产者在生产时，消费生产者在生产时，消费者不能消费。者不能消费。生产者-消费者问题2021-10-21计算机操作系统- 第4章85/144nC：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1) mod n;Signal(mutex);Signal(empty);empty=nfull=0mutex=1in,ou

57、t=0控制：控制： 缓冲区空时不能继缓冲区空时不能继续消费，制约消费者续消费，制约消费者进程进程C。生产者-消费者问题2021-10-21计算机操作系统- 第4章86/144n说明nwait和signal操作成对出现；n对资源信号量的wait操作在前n对互斥信号量的wait操作在后P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1) mod n;Signal(mutex);Signal(full);C：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1) mod n;Signal(mut

58、ex);Signal(empty);生产者-消费者问题2021-10-21计算机操作系统- 第4章87/144nP：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1) mod n;Signal(mutex);Signal(full);nP：Wait(empty,mutex);Buffer(in)=nextp;in:=(in+1) mod n;Signal(mutex,full);用用AND型信号量解决同一问题型信号量解决同一问题生产者-消费者问题2021-10-21计算机操作系统- 第4章88/144nC：Wait(full);Wait(mu

59、tex);netxc=buffer(out);out:=(out+1) mod n;Signal(mutex);Signal(empty);nC：Wait(full,mutex);netxc=buffer(out);out:=(out+1) mod n;Signal(mutex,empty);用用AND型信号量解决同一问题型信号量解决同一问题生产者-消费者问题2021-10-21计算机操作系统- 第4章89/144读者-写者问题n有两组并发进程: n读者和写者,共享一组数据区n要求：n允许多个读者同时执行读操作n不允许读者、写者同时操作n不允许多个写者同时操作2021-10-21计算机操作系统

60、- 第4章90/144信号量描述n互斥关系分析n读者和写者不能同时进入共享数据区n多个写者不能同时进入共享数据区n多个读者可以同时进入共享数据区n同步关系分析n读者进入缓冲区，写者必须等待n写者进入缓冲区，读者必须等待n读者优先：一旦有读者进入后续读者均可进入n合理顺序：读者在先来的写者之后n写者优先：只要有写者等待后续读者必须等待2021-10-21计算机操作系统- 第4章91/144信号量描述n如果读者来：n1）无读者、写者，新读者可以读n2）有写者等，但有其它读者正在读，则新读者也可以读n3）有写者写，新读者等n如果写者来：n1）无读者，新写者可以写n2）有读者，新写者等待n3）有其它写