进程同步和进程通信

1、关于进程同步与进程通信第一张，PPT共一百四十五页，创作于2022年6月第4章 进程同步与进程通信 进程同步使得进程之间能够相互协作和有序使用资源。 进程通信是进程之间数据的相互交换和信息的相互传递。第二张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章3本章目录4.1 进程并发4.2 临界区管理4.3 信号量机制 4.4 用信号量解决经典进程同步问题4.5 管程4.6 进程通信4.7 线程的同步和通信第三张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章44.1 进 程 并 发 并发是操作系统的基本特征 进程并发

2、使得程序执行的特点发生了变化4.1.1 程序的顺序执行 程序的顺序性包括程序的内部顺序性程序的外部顺序性 第四张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章54.1 进 程 并 发 并发是操作系统的基本特征 进程并发使得程序执行的特点发生了变化4.1.1 程序的顺序执行 程序的顺序性包括程序的内部顺序性程序的外部顺序性 第五张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章64.1.1 程序的顺序执行程序的内部顺序性一个程序的操作代码在计算机处理器上按照顺序执行，一个代码结束后，后一个代码才能开始。程序的外部顺

3、序性如果一项任务由多个程序模块组成，程序模块的运行也需要按照调用顺序执行，即程序模块之间的顺序性。 第六张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章7程序顺序执行具有的特点顺序性每个操作必须在上一个操作完成后才能开始；一个程序模块执行完成后另一个程序模块才能开始。封闭性程序运行独占系统全部资源，程序执行的结果除初始条件外，由程序本身决定，不会受到任何其它程序和外界因素的干扰。再现性针对相同的数据集合，程序执行的结果总是相同的。中断对程序执行的最终结果没有影响。程序执行的结果是可再现的。第七张，PPT共一百四十五页，创作于2022年6月16.08.2

4、022计算机操作系统- 第4章8程序顺序执行的不足限制了多个程序模块的并发执行。在多道程序并发执行环境下，处理器的利用率低，系统性能差。传统的程序顺序执行在多道程序环境下已不适合。 第八张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章94.1.2 进程的并发性在多道程序环境下，程序是按照多个进程并发执行的。进程的并发性是指一组进程执行在时间点上交替，在时间段上重叠。第九张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章10进程的并发性进程并发环境下，一个输入进程还没有完成，另一个计算进程已经开始；或者一个计算进程

5、还没有完成，另一个输出进程已经开始。程序的外部顺序性不再存在。并发进程之间可能是交互的，相关的。可能在同一时间段内，多个进程执行相同的软件代码，或多个进程共享某些变量，或多个进程请求同一硬件资源，一个进程的执行可能影响到其他进程的执行结果，并发进程之间具有制约关系。第十张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章11进程并发性举例例如，两个计数程序A、B，都为：N = N + 1；print（N）；其中，计数值N是共享变量。如果N的初始值为0，程序A、B执行的顺序不同，产生的结果也不同。 第十一张，PPT共一百四十五页，创作于2022年6月16.0

6、8.2022计算机操作系统- 第4章12进程并发性举例（续）A B程序A：N = N + 1；print（N）； /* 此时打印出的结果为1*/程序B：N = N + 1；print（N）； /* 此时打印出的结果为2*/第十二张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章13进程并发性举例（续）B A程序B：N = N + 1；print（N）； /* 此时打印出的结果为1*/程序A：N = N + 1；print（N）； /* 此时打印出的结果为2*/第十三张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章

7、14进程并发性举例（续）A B A B (A、B交替进行)程序A：N=N+1；程序B：N=N+1；程序A：print(N)；/* 此时打印出的结果为2*/程序B：print(N)；/* 此时打印出的结果为2*/程序运行出现了不可再现性！第十四张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章15进程并发执行的特点间断性多个并发进程共享处理器，执行过程是断断续续的，呈现间断性。制约性并发进程存在相互制约关系，系统必须对运行次序进行协调。不可再现性并发进程交替执行，如果存在共享变量等关系，程序执行的先后不同，会使共享变量的值不同。失去封闭性一个进程的执行环境

8、与其它进程有关，程序执行失去了封闭性。进程并发执行充分利用计算机资源，提高了效率。第十五张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章164.1.3 进程间的竞争和协作并发执行的进程以各自的速度向前推进，相互之间构成了相互竞争资源和相互协作的关系。1进程间的竞争多道程序并发执行环境下，进程的执行失去了封闭性。并发进程相互共处在一个系统中，一个进程的执行必然会影响到其他进程。 第十六张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章17进程间的竞争 共享的资源分为：互斥共享资源：只有一个进程对资源访问，访问结束并

9、释放后，另外的进程才能访问该资源。同时共享资源：多个进程可并发访问，不需要一个进程访问结束，其他的进程就可访问的资源。进程对互斥共享资源的竞争要求OS对进程操作采取同步措施，从时间上和顺序上加以限制，使得进程之间相互制约地使用这些资源，保证资源的完整性。 第十七张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章18进程间的协作由于每个进程都以独立地不可知的速度向前推进，需要具有协作关系的进程需要在某些协调点上相互协调、相互等待，使得双方都能够顺利地运行直至完成。协作的进程之间存在数据或变量等的共享关系，进程的推进顺序受到一定的限制，进程推进需要按照特定的

10、顺序进行，否则会发生进程执行结果的不可再现与不确定的情况。 第十八张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章19进程间的协作在并发进程之间存在相互协作关系时，系统需要采取同步措施，确保进程以合理的顺序推进，确保进程运行的可再现性和结果的确定性。并发进程之间的互斥共享资源关系最终也是进程之间的一种协作关系，即并发进程协作共享资源，也是进程同步关系。 第十九张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章204.1.4 进程同步生产者和消费者问题并发进程的共享资源问题并发进程之间的协作问题 第二十张，PPT共

11、一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章21生产者与消费者问题问题描述一个有限空间的共享缓冲区，负责存放货物生产者向缓冲区中放物品，缓冲区满则不能放消费者从缓冲区中拿物品，缓冲区空则不能拿生产者进程消费者进程（如何体现进程的同步）第二十一张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章22生产者与消费者问题缓冲池：数组表示，具有n个(0，1，n-1)缓冲区输入指针in：指示下一个可投放产品的缓冲区输出指针out：指示下一个可从中获取产品的缓冲区缓冲池采用循环组织，故：输入指针加1表示成 in:= (in+1) mo

12、d n； 输出指针加1表示成out:= (out+1) mod n。当 (in+1) mod n = out时表示缓冲池满；而in=out则表示缓冲池空。整型变量counter：生产者进程投放产品使counter加1；消费者进程取走产品使counter减1。Var n，integer；type item=；var buffer: array0，1，n-1 of item；in，out: 0，1，n-1；counter: 0，1，n； 第二十二张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章23生产者与消费者问题生产者进程producer: repeat

13、produce 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； 第二十三张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系

14、统- 第4章24生产者、消费者进程分析 生产者进程 消费者进程不存在资源的竞争，不会出现问题。生产者进程和消费者进程并发运行生产者进程和消费者进程对缓冲区竞争使用出现生产者进程与消费者进程之间不能协作的问题。当缓冲区中已经装满产品时，生产者进程得到缓冲区的访问权，生产者进程无法进行生产。生产者进程与消费者进程都需要对变量counter进行访问，对共享变量的访问可能造成数据不一致。第二十四张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章25生产者与消费者问题问题的出现两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在

15、用机器语言实现时，常可用下面的形式描述：（问题何在？）register1:=counter； register2:=counter；register1:=register1+1；register2:=register2-1；counter:=register1； counter:=register2； 第二十五张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章26生产者与消费者问题register1:=counter； register2:=counter；register1:=register1+1；register2:=register2-1；cou

16、nter:=register1； counter:=register2； register1:=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) 程序的执行已经失去了再现性。为了预防产生这种错误，解决此问题的关键是应把变量counter作为临界资源处理，亦即，令生产

17、者进程和消费者进程互斥地访问变量counter。第二十六张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章27生产者与消费者问题A1B1A2B2A3B3经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为9，最后count的值为9。A1A2A3B1B2B3经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为10，最后count的值为10。A1B1A2B2B3A3count的值为11。在进程并发环境下，竞争使用的资源和共享访问的变量，如果在程序中不采取同步措

18、施，实现互斥访问和有序访问，则会出现数据不一致等问题。A1: register1:=counter； B1: register2:=counter；A2: register1:=register1+1； B2: register2:=register2-1；A3: counter:=register1； B3: counter:=register2； 第二十七张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章28生产者与消费者问题A1B1A2B2A3B3经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为

19、9，最后count的值为9。A1A2A3B1B2B3经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为10，最后count的值为10。A1B1A2B2B3A3count的值为11。在进程并发环境下，竞争使用的资源和共享访问的变量，如果在程序中不采取同步措施，实现互斥访问和有序访问，则会出现数据不一致等问题。第二十八张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章29本章目录4.1 进程并发4.2 临界区管理4.3 信号量机制 4.4 用信号量解决经典进程同步问题4.5 管程4.6 进程通信4.7 线程

20、的同步和通信第二十九张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章30再次说明：程序的制约方式间接制约方式由于竞争相同资源而引起的，得到资源的程序段可以投入运行，而得不到资源的程序段就是暂时等待，直至获得可用资源时再继续运行。直接制约方式通常在那些逻辑上相关的程序段之间发生的，一般是由于各种程序段要求共享信息引起的。第三十张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章31进程同步基本概念制约关系的两种形式临界资源临界区信号量机制整型、记录型、AND型、信号量集信号量的应用实现进程互斥实现前趋关系第三十一张，

21、PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章32进程的同步（直接作用）进程的同步：synchronism指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态第三十二张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章33进程的互斥（间接作用）mutual exclusion由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进

22、程的互斥 临界资源：critical resource系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量第三十三张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章34“司机售票员”问题（同步）司机进程While(True) 启动公车； 驾驶公车； 停止公车；售票员进程While(True) 关车门； 卖车票； 开车门；正确运行过程While(True) （售票员）关车门 （司机）启动公车； （司机）驾驶公车； （售票员）卖车票 （司机）停止公车； （售票员）开车门；第三十四张，PPT共一百四十五页，创作于2022年6月16.

23、08.2022计算机操作系统- 第4章35Spooler目录问题（互斥）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目录进程切换，一切正常第三十五张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章36Spooler目录

24、问题（互斥）Out：4In：7进程A：N_f_s = In; /In = 7进程B：N_f_s = In; /In = 7InsertFileIntoSpooler(N_f_s);In=N_f_s+; /In = 84：File15：File26：File37：Null8：NullSpooler目录进程切换进程A：InsertFileIntoSpooler(N_f_s);In=N_f_s+; /In = 8进程切换，进程B数据丢失第三十六张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章374.2.1 临界资源和临界区互斥共享的资源称为临界资源。在生产者

25、和消费者进程中，缓冲区和变量count都是临界资源。在程序中对临界资源访问的代码部分称为临界区。进程访问临界资源前都要判断该资源能否访问，如果能访问，进入到临界区访问临界资源；如果不能访问，则需要等待，直到该资源能够访问；访问结束后，需要将资源归还，使其他进程能够知道临界资源已经被当前进程访问结束。第三十七张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章38临界资源和临界区步骤临界资源与临界区While ( 1 ) entry_section; /申请进入critical_section; /临界区exit_section;/声明退出第三十八张，PPT

26、共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章394.2.2 进程同步准则空闲让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入忙则等待：不允许两个以上的进程同时进入互斥区有限等待：任何进入互斥区要求应在有限时间内得到满足让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权第三十九张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章40进程同步准则程序设计时，进入区是判别能否访问临界资源的关键。如果进程能访问临界资源，则通过进入区，进入临界区访问临界资源；否则，进程不能进入临界区访问临界

27、资源；当进程访问临界资源完后，通过退出区，释放临界资源。 第四十张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章414.2.3 早期的临界区管理方法 1软件方法 软件方法在共享内存的单处理机或多处理机系统中实现进程的并发。 软件方法假定基于内存访问级别的一些基本互斥，对内存同一位置的同时访问将被排序，而访问的顺序并不事先指定。 不需要硬件或操作系统或程序设计语言的任何支持。 第四十一张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章42早期的临界区管理方法 软件方法算法1：临界区标志法为了实现临界区的管理，采用标

28、志来表示哪个并发进程可以进入临界区访问。确保每次只有一个进程进入临界区，但强制两个进程轮流进入临界区。违背进程同步机制中“空闲让进”原则 算法2：先判断对方进程标志的进程数组标志法进程每次访问临界资源前，首先查看其他进程访问临界资源的标志。如果其他进程标志处于正在访问，则进程等待。违背了“忙则等待”的同步准则 第四十二张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章43早期的临界区管理方法 软件方法算法3：先设置自己标志的进程数组标志法 违背了“空闲让进”的同步准则 算法4：双标志法标志flag用于表示每个进程是否访问临界资源，标志turn用于表示临界

29、资源此时是否有对方进程在访问。应用性非常方便的进程同步算法 在临界区访问标志算法中，出现了违背“忙则等待”或“空闲让进”准则的根本原因在于管理临界区标志要用两条指令，一条指令是看对方的标志，一条指令是设置自己的标志。 第四十三张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章44早期的临界区管理方法 硬件方法2硬件方法要保证进程在执行这两条指令时不被中断，可以采取锁的方式。如果临界区没有被访问，则锁是打开的，在进程访问临界区时，只要进程一进入临界区，则系统立即上锁，直到访问临界区的进程离开临界区才打开锁。 测试锁和上锁这两个操作不能分开，否则会造成多个进

30、程测试到锁打开而同时上锁的现象，引起冲突。进程在执行这两个操作期间在处理器上的运行不能被中断。软件方法来解决有一定局限性和难度，现一般借助于硬件设施。第四十四张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章45早期的临界区管理方法 硬件方法优点：实现简单：只需要硬件指令就可实现。适用性强：可用于多并发进程单CPU系统或共享内存多CPU系统。支持多个临界区：每个临界区用单独的变量定义，对临界区的多少没有限制，可支持多个临界区。缺点：耗费处理器时间：采用忙等待，处理器空闲时间增多。进程产生饥饿现象：一个进程离开临界区并唤醒阻塞等待的其它进程，可能阻塞更早的

31、进程长期得不到唤醒，产生饥饿现象。可能产生死锁：在单处理器系统中，进程执行特殊指令并进入临界区，拥有更高优先级的进程抢占，但得不到没有释放的临界资源，于是这两个进程发生死锁。第四十五张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章46早期的临界区管理方法 硬件方法（1）禁止中断方法最简单的方法影响计算机效率不能及时处理重要程序在多处理器下方法失效 （2）测试并建立指令（3）对换指令第四十六张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章47本章目录4.1 进程并发4.2 临界区管理4.3 信号量机制 4.4 用

32、信号量解决经典进程同步问题4.5 管程4.6 进程通信4.7 线程的同步和通信重点与难点第四十七张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章48信号量机制信号量（semaphore）机制 解决并发进程同步的工具 在信号量同步机制中，有“检测”和“归还”两个重要的操作 荷兰语 “Proberen” 的意思为“检测”，用P操作表示；荷兰语 “Verhogen” 的意思为“增量”，用V操作表示。“增量”即增加一个可以使用的临界资源，也就是“归还”的意思。 第四十八张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章4

33、9信号量机制P操作表示同步进程发出的检测信号量操作，检测是否能够使用临界资源如果能使用，则检测通过，进程可以访问临界资源；如果不能使用，则等待，直到访问临界区的进程将临界资源归还后，等待的进程才能够访问临界资源。V操作表示访问完临界资源的进程通知等待进程已经完成了临界资源的访问，将临界资源释放。 第四十九张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章50信号量机制信号量机制强调P操作和V操作都是原子操作。原子操作是不可分割的操作，原语。即通常所说的“要么做，要么不做”，而不可能操作没有完成就被终止。 第五十张，PPT共一百四十五页，创作于2022年6

34、月16.08.2022计算机操作系统- 第4章514.3.1 整型信号量 整型信号量设S为一个需要初始化值的正整型量。对S的访问只能通过P、V操作。 P操作wait（S）： while S0 do no-op S:S1;V操作signal（S）： S:S1;第五十一张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章52整型信号量S0，表示临界资源可以访问，P(s)中的检测语句通过，调用P(s)的进程可以访问临界资源。S0，表示有进程在访问临界资源，此时临界资源处于忙，调用P(s)的进程只能等待，直到s的值大于0，才可以访问临界资源。 第五十二张，PPT共

35、一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章53整型信号量的应用实现进程互斥例4-3 输入进程和计算进程共用缓冲区，如图所示。输入进程I和计算进程P并发执行，缓冲区是竞争访问的临界资源，缓冲区的大小为n。用整型信号量实现进程同步。公共缓冲区PI为缓冲区设置整型信号量mutex;设mutex的初值为1将各进程对临界区访问置于P(mutex)和V(mutex)之间第五十三张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章54整型信号量的应用实现进程互斥Pi: /* 输入进程 */ begin while(输入未完成) P(m

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

37、能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。第五十五张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章56整型信号量的应用实现进程互斥例4-3 分析：对于输入进程： 只要缓冲区没有装满，进程就能将数据输入到缓冲区中。 缓冲区是否装满：需要用P(mutex)去检测，如果P(mutex)检测通过，则进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。对于计算进程： 只要缓冲区不为空，则进程能够从缓冲区中取走数据。 缓冲区是否为空，需要用P(mutex)

38、去检测，如果P(mutex)检测通过，进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。第五十六张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章57整型信号量的应用实现进程互斥例4-3 分析：对于输入进程： 只要缓冲区没有装满，进程就能将数据输入到缓冲区中。 缓冲区是否装满：需要用P(mutex)去检测，如果P(mutex)检测通过，则进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。对于计算进程： 只要缓冲区不为空，则进程能够从缓冲区中取走数据

39、。 缓冲区是否为空，需要用P(mutex)去检测，如果P(mutex)检测通过，进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。对于输入进程和计算进程： 如果两个进程都能够访问缓冲区，哪个进程先访问缓冲区，关键在于哪个进程先执行P(mutex)。 先执行的进程先进入缓冲区访问；后执行P(mutex)的进程等待，直到先进入缓冲区访问的进程用V(mutex)释放缓冲区为止。第五十七张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章58整型信号量的应用实现进程同步例4-3 在例4-3的基础上，当输入进程和

40、计算进程之间共用的缓冲区中只能装入一条数据时，用整型信号量实现输入进程和计算进程的同步。公共缓冲区PI当缓冲区中只能装入一条数据时，输入进程每次放入一条数据后，要等待计算进程取走数据才能再放入下一条数据。设置两个整型信号量is和ps用于输入进程和计算进程协调访问缓冲区初值分别设置为1和0第五十八张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章59Pi: /* 输入进程 */ begin while(输入未完成) P(is); 将一批输入数据放入缓冲区; V(ps); end;Pc： /* 计算进程 */ begin while(计算未完成) P(ps)

41、; 从缓冲区中拿出一批数据; V(is); 计算; end;coend;整型信号量的应用实现进程同步第五十九张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章60整型信号量的应用实现进程同步例4-4 分析：信号量的设置是关键： 将信号量is的初值设置为1，ps的初值设置为0。 总是输入进程先进入缓冲区放入数据，计算进程先等待。 输入进程将一条数据放入缓冲区后释放ps，计算进程才能进入缓冲区取走一条数据。对于输入进程： 如果计算进程没有进入缓冲区取走一条数据，输入进程不能再进入缓冲区放数据，因为输入进程需要计算进程释放缓冲区is。对于计算进程： 如果没有输

42、入进程释放缓冲区ps，计算进程不能多次连续进入缓冲区取走数据。第六十张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章61整型信号量的应用实现进程前趋图a,b,c,d,e,f,g:semaphore : = 0,0begin 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

43、wait(e);wait(f);wait(g); S6;end;S1S2S4S3S5S6S1S2S4S3S5S6第六十一张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章624.3.2 记录型信号量在整型信号量中，P操作开始需要测试临界资源是否能够访问，即判断s0是否满足。如果满足，表示进程不能进入临界区访问，进程此时“do nothing”，即什么都不做而等待。这时的等待没有放弃CPU执行权。这违背了“让权等待”的同步准则，造成处理器资源的浪费。 第六十二张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章63记录

44、型信号量解决忙等问题，实现让权等待记录所有等待同一资源的进程 P操作wait（S）：S.value S.value1if S.value0 then block（S,L） V操作S.value S.value1if S.value0 then wakeup（S,L）第六十三张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章64记录型信号量理解： 记录型信号量在整型信号量的基础上进行了改进，让不能进入临界区的进程“让权等待”，即进程状态由运行转换为阻塞状态，进程进入阻塞队列中等待。若信号量s的s.value的值为正数，该正数表示可对信号量可进行的P操作的次

45、数，即实际可以使用的临界资源数。若信号量s的s.value的值为负值，表示有多个进程申请临界资源，而又不能得到，在阻塞队列等待。s.value的绝对值表示在阻塞队列等待临界资源的进程个数。第六十四张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章654.3.3 AND型信号量集AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作 AND型信号量集的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配AND型信号量集P原语为SwaitAND型信号量集V原语为Ssignal第六十五张，PPT共一百四十五页，创作

46、于2022年6月16.08.2022计算机操作系统- 第4章66AND型信号量理解： 死锁的产生？ 死锁的预防与解决？解决的办法是将进程所需要的资源一次性地全部分配给进程，等进程运行完后再全部一起释放。先让一个进程完成后，另一个进程才申请资源，得到资源并完成。也就是将并发的进程分为先完成进程和后完成进程。AND型信号量集是将进程在运行中所需要的临界资源全部一次性分配给进程，等进程用完后再全部一起释放。如果进程有一个临界资源没有得到，进程也不可能推进，必须将所分配到的临界资源全部归还。即要么全部得到向前推进，要么一个也不能要而等待。这样的资源分配策略可以避免死锁。第六十六张，PPT共一百四十五页

47、，创作于2022年6月16.08.2022计算机操作系统- 第4章674.3.4 信号量集当进程需要申请的临界资源种类较多，每类临界资源个数较多时，如果用记录型信号量，进程每次只能一次申请或释放一个临界资源，非常麻烦。因此，引入信号量集。 第六十七张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章68信号量机制整型信号量基本信号量原理记录型信号量多个进程申请同一类资源AND型信号量同一进程申请多个不同资源信号量集同一进程申请多个同类资源多个进程申请多个不同资源信号量机制的对比第六十八张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机

48、操作系统- 第4章692 信号量机制信号量按联系进程的关系分成二类：公用信号量（互斥信号量）私用信号量（同步信号量） 它为一组需互斥共享临界资源的并发进程而设置，代表共享的临界资源，每个进程均可对它施加P、V操作，即都可申请和释放该临界资源，其初始值置为1。取值意义如下：信号量s1 ；表示资源空闲，可供使用。信号量s0 ；表示资源已被占用，无其它进程等待。信号量s-n ；表示资源已被占用，还有n个进程因等待资源而阻塞。它为一组需同步协作完成任务的并发进程而设置，只有拥有该资源的进程才能对它施加P操作（即可申请资源），而由其合作进程对它施加V操作（即释放资源）。第六十九张，PPT共一百四十五页，

49、创作于2022年6月16.08.2022计算机操作系统- 第4章70例题补充与讲解：1知识点：进程的前趋图题目：已知一个求值公式如下所示，如果A、B已赋值，请画出该公式求值过程的前趋图思路：分辨可以并发进行的运算保存计算的中间结果，并为每条语句命名第七十张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章71例题补充与讲解：1第七十一张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章72例题补充与讲解：2知识点：信号量的应用题目：设有一个作业由四个进程组成，这四个进程必须按右图的次序运行，试用P、V操作表达四个进程的

50、同步关系。思路：设三个同步信号量b1、b2、b3，分别表示进程T2、T3、T4是否可以开始执行，初值为0。第七十二张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章73例题补充与讲解：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操作）第七十三张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4

51、章74例题补充与讲解：3知识点：信号量的应用题目：设有两个优先级相同的进程P1和P2如下，信号量S1和S2的初值为0。请问P1、P2并发执行结束后，x、y、z的值分别是多少？进程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;思路：P1和P2具有相同的优先级，并发，具有顺序的不确定性；信号量S1和S2使得语句的执行顺序具有了制约关系绘制对应的前趋图第七十四张，PPT共一百四十五页，创作于2022年6月16.08.20

52、22计算机操作系统- 第4章75例题补充与讲解：3进程P1S1: y = 1;S2: 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 = 9第七十五张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章76提问环节关于临界区的管理软件方法临界区标志法进程数组标志法1进程数组标志法2双标志法硬件方法缺陷信号量机制整型信号量基本信号量原

53、理记录型信号量多个进程申请同一类资源AND型信号量同一进程申请多个不同资源信号量集同一进程申请多个同类资源多个进程申请多个不同资源第七十六张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章77本章目录4.1 进程并发4.2 临界区管理4.3 信号量机制 4.4 用信号量解决经典进程同步问题4.5 管程4.6 进程通信4.7 线程的同步和通信重点与难点生产者消费者问题读者写者问题哲学家就餐问题第七十七张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章78生产者-消费者问题假设缓冲池中有n个缓冲区，每个缓冲区存放一个消

54、息；可利用互斥信号量mutex使诸进程对缓冲池实现互斥访问；利用empty和full计数信号量分别表示空缓冲及满缓冲的数量。又假定这些生产者和消费者互相等效，只要缓冲池未满，生产者可将消息送入缓冲池；只要缓冲池未空，消费者可从缓冲池取走一个消息。同步问题：生产者：P进程不能往“满”的缓冲区中放产品；消费者：C进程不能从“空”的缓冲区中取产品。第七十八张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章79同步与互斥问题互斥信号量mutex：防止多个进程同时进入临界区同步信号量empty和full：保证事件发生的顺序缓冲区满时，Producer停止运行缓冲区

55、空时，Consumer停止运行概念差别互斥与同步（并发的两个要素）互斥：保护临界区，防止多个进程同时进入同步：保证进程运行的顺序合理第七十九张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章80同步/互斥信号量的使用方法互斥信号量必定成对出现：进入临界区临界区退出临界区同步信号量未必成对出现，依赖于同步关系的性质同步信号量和互斥信号量的操作顺序基本原则：互斥信号量永远紧邻临界区第八十张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章81生产者P：Wait(empty);Wait(mutex);Buffer(in)=

56、nextp;in:=(in+1) mod n;Signal(mutex);Signal(full);消费者C:Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1) mod n;Signal(mutex);Signal(empty);mutex,full,empty:semaphoremutex :=1;full:=0;empty:=n;生产者-消费者问题第八十一张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章82P：Wait(empty);Wait(mutex);Buffer(in)=nextp;i

57、n:=(in+1) mod n;Signal(mutex);Signal(full);empty=nfull=0mutex=1in,out=0生产者和消费者之间的约束：临界区。生产者在生产时，消费者不能消费。生产者-消费者问题第八十二张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章83P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1) mod n;Signal(mutex);Signal(full);empty=nfull=0mutex=1in,out=0控制： 缓冲区满时不能继续生产，制约生产者

58、进程P。生产者-消费者问题第八十三张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章84C：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1) mod n;Signal(mutex);Signal(empty);empty=nfull=0mutex=1in,out=0生产者和消费者之间的约束：临界区。生产者在生产时，消费者不能消费。生产者-消费者问题第八十四张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章85C：Wait(full);Wait(mutex);

59、netxc=buffer(out);out:=(out+1) mod n;Signal(mutex);Signal(empty);empty=nfull=0mutex=1in,out=0控制： 缓冲区空时不能继续消费，制约消费者进程C。生产者-消费者问题第八十五张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章86说明wait和signal操作成对出现；对资源信号量的wait操作在前对互斥信号量的wait操作在后P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1) mod n;Signal(mutex

60、);Signal(full);C：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1) mod n;Signal(mutex);Signal(empty);生产者-消费者问题第八十六张，PPT共一百四十五页，创作于2022年6月16.08.2022计算机操作系统- 第4章87P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1) mod n;Signal(mutex);Signal(full);P：Wait(empty,mutex);Buffer(in)=nextp;in:=(in+1)