进程同步与进程通信

关于进程同步与进程通信第4章进程同步与进程通信

进程同步使得进程之间能够相互协作和有序使用资源。

进程通信是进程之间数据的相互交换和信息的相互传递。第2页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章3本章目录4.1进程并发4.2临界区管理4.3信号量机制4.4用信号量解决经典进程同步问题4.5管程4.6进程通信4.7线程的同步和通信第3页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章44.1进程并发并发是操作系统的基本特征进程并发使得程序执行的特点发生了变化4.1.1程序的顺序执行程序的顺序性包括程序的内部顺序性程序的外部顺序性第4页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章54.1进程并发并发是操作系统的基本特征进程并发使得程序执行的特点发生了变化4.1.1程序的顺序执行程序的顺序性包括程序的内部顺序性程序的外部顺序性第5页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章64.1.1

程序的顺序执行程序的内部顺序性一个程序的操作代码在计算机处理器上按照顺序执行，一个代码结束后，后一个代码才能开始。程序的外部顺序性如果一项任务由多个程序模块组成，程序模块的运行也需要按照调用顺序执行，即程序模块之间的顺序性。第6页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章7程序顺序执行具有的特点顺序性每个操作必须在上一个操作完成后才能开始；一个程序模块执行完成后另一个程序模块才能开始。封闭性程序运行独占系统全部资源，程序执行的结果除初始条件外，由程序本身决定，不会受到任何其它程序和外界因素的干扰。再现性针对相同的数据集合，程序执行的结果总是相同的。中断对程序执行的最终结果没有影响。程序执行的结果是可再现的。第7页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章8程序顺序执行的不足限制了多个程序模块的并发执行。在多道程序并发执行环境下，处理器的利用率低，系统性能差。传统的程序顺序执行在多道程序环境下已不适合。第8页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章94.1.2

进程的并发性在多道程序环境下，程序是按照多个进程并发执行的。进程的并发性是指一组进程执行在时间点上交替，在时间段上重叠。第9页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章10进程的并发性进程并发环境下，一个输入进程还没有完成，另一个计算进程已经开始；或者一个计算进程还没有完成，另一个输出进程已经开始。程序的外部顺序性不再存在。并发进程之间可能是交互的，相关的。可能在同一时间段内，多个进程执行相同的软件代码，或多个进程共享某些变量，或多个进程请求同一硬件资源，一个进程的执行可能影响到其他进程的执行结果，并发进程之间具有制约关系。第10页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章11进程并发性举例例如，两个计数程序A、B，都为：

N=N+1；

print（N）； 其中，计数值N是共享变量。 如果N的初始值为0，程序A、B执行的顺序不同，产生的结果也不同。第11页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章12进程并发性举例（续）A→B程序A：N=N+1；print（N）；/*此时打印出的结果为1*/程序B：N=N+1；print（N）；/*此时打印出的结果为2*/第12页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章13进程并发性举例（续）B→A程序B：N=N+1；print（N）；/*此时打印出的结果为1*/程序A：N=N+1；print（N）；/*此时打印出的结果为2*/第13页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章14进程并发性举例（续）A→B→A→B(A、B交替进行)程序A：N=N+1；程序B：N=N+1；程序A：print(N)；/*此时打印出的结果为2*/程序B：print(N)；/*此时打印出的结果为2*/程序运行出现了不可再现性！第14页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章15进程并发执行的特点间断性多个并发进程共享处理器，执行过程是断断续续的，呈现间断性。制约性并发进程存在相互制约关系，系统必须对运行次序进行协调。不可再现性并发进程交替执行，如果存在共享变量等关系，程序执行的先后不同，会使共享变量的值不同。失去封闭性一个进程的执行环境与其它进程有关，程序执行失去了封闭性。进程并发执行充分利用计算机资源，提高了效率。第15页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章164.1.3

进程间的竞争和协作并发执行的进程以各自的速度向前推进，相互之间构成了相互竞争资源和相互协作的关系。1．进程间的竞争多道程序并发执行环境下，进程的执行失去了封闭性。并发进程相互共处在一个系统中，一个进程的执行必然会影响到其他进程。第16页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章17进程间的竞争共享的资源分为：互斥共享资源：只有一个进程对资源访问，访问结束并释放后，另外的进程才能访问该资源。同时共享资源：多个进程可并发访问，不需要一个进程访问结束，其他的进程就可访问的资源。进程对互斥共享资源的竞争要求OS对进程操作采取同步措施，从时间上和顺序上加以限制，使得进程之间相互制约地使用这些资源，保证资源的完整性。第17页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章18进程间的协作由于每个进程都以独立地不可知的速度向前推进，需要具有协作关系的进程需要在某些协调点上相互协调、相互等待，使得双方都能够顺利地运行直至完成。协作的进程之间存在数据或变量等的共享关系，进程的推进顺序受到一定的限制，进程推进需要按照特定的顺序进行，否则会发生进程执行结果的不可再现与不确定的情况。第18页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章19进程间的协作在并发进程之间存在相互协作关系时，系统需要采取同步措施，确保进程以合理的顺序推进，确保进程运行的可再现性和结果的确定性。并发进程之间的互斥共享资源关系最终也是进程之间的一种协作关系，即并发进程协作共享资源，也是进程同步关系。第19页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章204.1.4

进程同步生产者和消费者问题并发进程的共享资源问题并发进程之间的协作问题第20页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章21生产者与消费者问题问题描述一个有限空间的共享缓冲区，负责存放货物生产者向缓冲区中放物品，缓冲区满则不能放消费者从缓冲区中拿物品，缓冲区空则不能拿生产者进程消费者进程（如何体现进程的同步）第21页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章22生产者与消费者问题缓冲池：数组表示，具有n个(0，1，…，n-1)缓冲区输入指针in：指示下一个可投放产品的缓冲区输出指针out：指示下一个可从中获取产品的缓冲区缓冲池采用循环组织，故：输入指针加1表示成in:=(in+1)modn；输出指针加1表示成out:=(out+1)modn。当(in+1)modn=out时表示缓冲池满；而in=out则表示缓冲池空。整型变量counter：生产者进程投放产品使counter加1；消费者进程取走产品使counter减1。Varn，integer；typeitem=…；varbuffer:array［0，1，…，n-1］ofitem；in，out:0，1，…，n-1；counter:0，1，…，n；第22页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章23生产者与消费者问题生产者进程producer:repeat

produceaniteminnextp；

whilecounter=ndono-op；

buffer［in］:=nextp；

in:=in+1modn；

counter:=counter+1；untilfalse；消费者进程

consumer:repeat

whilecounter=0dono-op；nextc:=buffer［out］；out:=(out+1)modn；counter:=counter-1；consumertheiteminnextc；

untilfalse；第23页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章24生产者、消费者进程分析生产者进程→消费者进程不存在资源的竞争，不会出现问题。生产者进程和消费者进程并发运行生产者进程和消费者进程对缓冲区竞争使用出现生产者进程与消费者进程之间不能协作的问题。当缓冲区中已经装满产品时，生产者进程得到缓冲区的访问权，生产者进程无法进行生产。生产者进程与消费者进程都需要对变量counter进行访问，对共享变量的访问可能造成数据不一致。第24页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章25生产者与消费者问题问题的出现两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述：（问题何在？）register1:=counter；register2:=counter；register1:=register1+1；register2:=register2-1；counter:=register1；counter:=register2；第25页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章26生产者与消费者问题register1:=counter；register2:=counter；register1:=register1+1；register2:=register2-1；counter:=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作为临界资源处理，亦即，令生产者进程和消费者进程互斥地访问变量counter。第26页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章27生产者与消费者问题A1→B1→A2→B2→A3→B3经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为9，最后count的值为9。A1→A2→A3→B1→B2→B3经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为10，最后count的值为10。A1→B1→A2→B2→B3→A3count的值为11。在进程并发环境下，竞争使用的资源和共享访问的变量，如果在程序中不采取同步措施，实现互斥访问和有序访问，则会出现数据不一致等问题。A1:register1:=counter；

B1:register2:=counter；A2:register1:=register1+1；

B2:register2:=register2-1；A3:counter:=register1；

B3:counter:=register2；

第27页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章28生产者与消费者问题A1→B1→A2→B2→A3→B3经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为9，最后count的值为9。A1→A2→A3→B1→B2→B3经过寄存器register1得到的count值为11，经过寄存器register2得到的count值为10，最后count的值为10。A1→B1→A2→B2→B3→A3count的值为11。在进程并发环境下，竞争使用的资源和共享访问的变量，如果在程序中不采取同步措施，实现互斥访问和有序访问，则会出现数据不一致等问题。第28页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章29本章目录4.1进程并发4.2临界区管理4.3信号量机制4.4用信号量解决经典进程同步问题4.5管程4.6进程通信4.7线程的同步和通信第29页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章30再次说明：程序的制约方式间接制约方式由于竞争相同资源而引起的，得到资源的程序段可以投入运行，而得不到资源的程序段就是暂时等待，直至获得可用资源时再继续运行。直接制约方式通常在那些逻辑上相关的程序段之间发生的，一般是由于各种程序段要求共享信息引起的。第30页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章31进程同步基本概念制约关系的两种形式临界资源临界区信号量机制整型、记录型、AND型、信号量集信号量的应用实现进程互斥实现前趋关系第31页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章32进程的同步（直接作用）进程的同步：synchronism指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态第32页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章33进程的互斥（间接作用）mutualexclusion由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥临界资源：criticalresource系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量第33页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章34“司机－售票员”问题（同步）司机进程While(True){启动公车；驾驶公车；停止公车；}售票员进程While(True){关车门；卖车票；开车门；}正确运行过程While(True){（售票员）关车门（司机）启动公车；（司机）驾驶公车；（售票员）卖车票（司机）停止公车；（售票员）开车门；}第34页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第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==9

4：File15：File26：File37：Null8：Null………Spooler目录………进程切换，一切正常第35页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章36Spooler目录问题（互斥）Out：4In：7进程A： N_f_s=In;

//In==7

进程B： N_f_s=In;

//In==7

InsertFileIntoSpooler(N_f_s); In=N_f_s++;

//In==8

4：File15：File26：File37：Null8：Null………Spooler目录………进程切换进程A： InsertFileIntoSpooler(N_f_s); In=N_f_s++;

//In==8

进程切换，进程B数据丢失第36页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章374.2.1

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

进程同步准则空闲让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入忙则等待：不允许两个以上的进程同时进入互斥区有限等待：任何进入互斥区要求应在有限时间内得到满足让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权第39页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章40进程同步准则程序设计时，进入区是判别能否访问临界资源的关键。如果进程能访问临界资源，则通过进入区，进入临界区访问临界资源；否则，进程不能进入临界区访问临界资源；当进程访问临界资源完后，通过退出区，释放临界资源。第40页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章414.2.3早期的临界区管理方法1．软件方法软件方法在共享内存的单处理机或多处理机系统中实现进程的并发。软件方法假定基于内存访问级别的一些基本互斥，对内存同一位置的同时访问将被排序，而访问的顺序并不事先指定。不需要硬件或操作系统或程序设计语言的任何支持。第41页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章42早期的临界区管理方法–软件方法算法1：临界区标志法为了实现临界区的管理，采用标志来表示哪个并发进程可以进入临界区访问。确保每次只有一个进程进入临界区，但强制两个进程轮流进入临界区。违背进程同步机制中“空闲让进”原则算法2：先判断对方进程标志的进程数组标志法进程每次访问临界资源前，首先查看其他进程访问临界资源的标志。如果其他进程标志处于正在访问，则进程等待。违背了“忙则等待”的同步准则第42页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章43早期的临界区管理方法–软件方法算法3：先设置自己标志的进程数组标志法违背了“空闲让进”的同步准则算法4：双标志法标志flag用于表示每个进程是否访问临界资源，标志turn用于表示临界资源此时是否有对方进程在访问。应用性非常方便的进程同步算法在临界区访问标志算法中，出现了违背“忙则等待”或“空闲让进”准则的根本原因在于管理临界区标志要用两条指令，一条指令是看对方的标志，一条指令是设置自己的标志。

第43页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章44早期的临界区管理方法–硬件方法2．硬件方法要保证进程在执行这两条指令时不被中断，可以采取锁的方式。如果临界区没有被访问，则锁是打开的，在进程访问临界区时，只要进程一进入临界区，则系统立即上锁，直到访问临界区的进程离开临界区才打开锁。测试锁和上锁这两个操作不能分开，否则会造成多个进程测试到锁打开而同时上锁的现象，引起冲突。进程在执行这两个操作期间在处理器上的运行不能被中断。软件方法来解决有一定局限性和难度，现一般借助于硬件设施。第44页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章45早期的临界区管理方法–硬件方法优点：实现简单：只需要硬件指令就可实现。适用性强：可用于多并发进程单CPU系统或共享内存多CPU系统。支持多个临界区：每个临界区用单独的变量定义，对临界区的多少没有限制，可支持多个临界区。缺点：耗费处理器时间：采用忙等待，处理器空闲时间增多。进程产生饥饿现象：一个进程离开临界区并唤醒阻塞等待的其它进程，可能阻塞更早的进程长期得不到唤醒，产生饥饿现象。可能产生死锁：在单处理器系统中，进程执行特殊指令并进入临界区，拥有更高优先级的进程抢占，但得不到没有释放的临界资源，于是这两个进程发生死锁。第45页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章46早期的临界区管理方法–硬件方法（1）禁止中断方法最简单的方法影响计算机效率不能及时处理重要程序在多处理器下方法失效（2）测试并建立指令（3）对换指令第46页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章47本章目录4.1进程并发4.2临界区管理4.3信号量机制4.4用信号量解决经典进程同步问题4.5管程4.6进程通信4.7线程的同步和通信重点与难点第47页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章48信号量机制信号量（semaphore）机制解决并发进程同步的工具在信号量同步机制中，有“检测”和“归还”两个重要的操作荷兰语“Proberen”的意思为“检测”，用P操作表示；荷兰语“Verhogen”的意思为“增量”，用V操作表示。“增量”即增加一个可以使用的临界资源，也就是“归还”的意思。第48页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章49信号量机制P操作表示同步进程发出的检测信号量操作，检测是否能够使用临界资源如果能使用，则检测通过，进程可以访问临界资源；如果不能使用，则等待，直到访问临界区的进程将临界资源归还后，等待的进程才能够访问临界资源。V操作表示访问完临界资源的进程通知等待进程已经完成了临界资源的访问，将临界资源释放。第49页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章50信号量机制信号量机制强调P操作和V操作都是原子操作。原子操作是不可分割的操作，原语。即通常所说的“要么做，要么不做”，而不可能操作没有完成就被终止。第50页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章514.3.1

整型信号量整型信号量设S为一个需要初始化值的正整型量。对S的访问只能通过P、V操作。P操作 wait（S）：whileS≤0dono-opS:＝S－1;V操作 signal（S）：S:＝S＋1;第51页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章52整型信号量S>0，表示临界资源可以访问，P(s)中的检测语句通过，调用P(s)的进程可以访问临界资源。S≤0，表示有进程在访问临界资源，此时临界资源处于忙，调用P(s)的进程只能等待，直到s的值大于0，才可以访问临界资源。第52页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章53整型信号量的应用－实现进程互斥例4-3

输入进程和计算进程共用缓冲区，如图所示。输入进程I和计算进程P并发执行，缓冲区是竞争访问的临界资源，缓冲区的大小为n。用整型信号量实现进程同步。公共缓冲区PI为缓冲区设置整型信号量mutex;设mutex的初值为1将各进程对临界区访问置于P(mutex)和V(mutex)之间第53页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章54整型信号量的应用－实现进程互斥Pi: /*输入进程*/beginwhile(输入未完成){…P(mutex);/*如果缓冲区装满，则等待*/

将一批输入数据放入缓冲区;V(mutex);}end;Pc： /*计算进程*/beginwhile(计算未完成){P(mutex);/*如果缓冲区为空，则等待*/

从缓冲区中拿出一批数据;V(mutex);

计算;…}end;coend;第54页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章55整型信号量的应用－实现进程互斥例4-3

分析：对于输入进程：只要缓冲区没有装满，进程就能将数据输入到缓冲区中。缓冲区是否装满：需要用P(mutex)去检测，如果P(mutex)检测通过，则进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。第55页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章56整型信号量的应用－实现进程互斥例4-3

分析：对于输入进程：只要缓冲区没有装满，进程就能将数据输入到缓冲区中。缓冲区是否装满：需要用P(mutex)去检测，如果P(mutex)检测通过，则进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。对于计算进程：只要缓冲区不为空，则进程能够从缓冲区中取走数据。缓冲区是否为空，需要用P(mutex)去检测，如果P(mutex)检测通过，进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。第56页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章57整型信号量的应用－实现进程互斥例4-3

分析：对于输入进程：只要缓冲区没有装满，进程就能将数据输入到缓冲区中。缓冲区是否装满：需要用P(mutex)去检测，如果P(mutex)检测通过，则进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。对于计算进程：只要缓冲区不为空，则进程能够从缓冲区中取走数据。缓冲区是否为空，需要用P(mutex)去检测，如果P(mutex)检测通过，进程能够访问缓冲区。访问完后用V(mutex)释放缓冲区；如果P(mutex)检测不能通过，则进程等待。对于输入进程和计算进程：如果两个进程都能够访问缓冲区，哪个进程先访问缓冲区，关键在于哪个进程先执行P(mutex)。先执行的进程先进入缓冲区访问；后执行P(mutex)的进程等待，直到先进入缓冲区访问的进程用V(mutex)释放缓冲区为止。第57页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章58整型信号量的应用－实现进程同步例4-3

在例4-3的基础上，当输入进程和计算进程之间共用的缓冲区中只能装入一条数据时，用整型信号量实现输入进程和计算进程的同步。公共缓冲区PI当缓冲区中只能装入一条数据时，输入进程每次放入一条数据后，要等待计算进程取走数据才能再放入下一条数据。设置两个整型信号量is和ps用于输入进程和计算进程协调访问缓冲区初值分别设置为1和0第58页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章59Pi: /*输入进程*/

beginwhile(输入未完成){…P(is);将一批输入数据放入缓冲区;V(ps);}end;Pc： /*计算进程*/beginwhile(计算未完成){P(ps);

从缓冲区中拿出一批数据;V(is);

计算;…}end;coend;整型信号量的应用－实现进程同步第59页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章60整型信号量的应用－实现进程同步例4-4

分析：信号量的设置是关键：将信号量is的初值设置为1，ps的初值设置为0。总是输入进程先进入缓冲区放入数据，计算进程先等待。输入进程将一条数据放入缓冲区后释放ps，计算进程才能进入缓冲区取走一条数据。对于输入进程：如果计算进程没有进入缓冲区取走一条数据，输入进程不能再进入缓冲区放数据，因为输入进程需要计算进程释放缓冲区is。对于计算进程：如果没有输入进程释放缓冲区ps，计算进程不能多次连续进入缓冲区取走数据。第60页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章61整型信号量的应用－实现进程前趋图a,b,c,d,e,f,g:semaphore:=0,…,0beginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;beginwait(b);S3;signal(e);end;beginwait(c);S4;signal(f);end;beginwait(d);S5;signal(g);end;beginwait(e);wait(f);wait(g);S6;end;S1S2S4S3S5S6S1S2S4S3S5S6第61页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章624.3.2

记录型信号量在整型信号量中，P操作开始需要测试临界资源是否能够访问，即判断s≤0是否满足。如果满足，表示进程不能进入临界区访问，进程此时“donothing”，即什么都不做而等待。这时的等待没有放弃CPU执行权。这违背了“让权等待”的同步准则，造成处理器资源的浪费。第62页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章63记录型信号量解决忙等问题，实现让权等待记录所有等待同一资源的进程P操作wait（S）： S.value＝S.value－1 ifS.value<0thenblock（S,L）

V操作 S.value＝S.value＋1 ifS.value≤0thenwakeup（S,L）第63页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章64记录型信号量理解：记录型信号量在整型信号量的基础上进行了改进，让不能进入临界区的进程“让权等待”，即进程状态由运行转换为阻塞状态，进程进入阻塞队列中等待。若信号量s的s.value的值为正数，该正数表示可对信号量可进行的P操作的次数，即实际可以使用的临界资源数。若信号量s的s.value的值为负值，表示有多个进程申请临界资源，而又不能得到，在阻塞队列等待。s.value的绝对值表示在阻塞队列等待临界资源的进程个数。第64页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章654.3.3

AND型信号量集AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作AND型信号量集的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配AND型信号量集P原语为SwaitAND型信号量集V原语为Ssignal第65页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章66AND型信号量理解：死锁的产生？死锁的预防与解决？解决的办法是将进程所需要的资源一次性地全部分配给进程，等进程运行完后再全部一起释放。先让一个进程完成后，另一个进程才申请资源，得到资源并完成。也就是将并发的进程分为先完成进程和后完成进程。AND型信号量集是将进程在运行中所需要的临界资源全部一次性分配给进程，等进程用完后再全部一起释放。如果进程有一个临界资源没有得到，进程也不可能推进，必须将所分配到的临界资源全部归还。即要么全部得到向前推进，要么一个也不能要而等待。这样的资源分配策略可以避免死锁。第66页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章674.3.4

信号量集当进程需要申请的临界资源种类较多，每类临界资源个数较多时，如果用记录型信号量，进程每次只能一次申请或释放一个临界资源，非常麻烦。因此，引入信号量集。第67页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章68信号量机制整型信号量基本信号量原理记录型信号量多个进程申请同一类资源AND型信号量同一进程申请多个不同资源信号量集同一进程申请多个同类资源多个进程申请多个不同资源信号量机制的对比第68页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章692信号量机制信号量按联系进程的关系分成二类：公用信号量（互斥信号量）私用信号量（同步信号量）

它为一组需互斥共享临界资源的并发进程而设置，代表共享的临界资源，每个进程均可对它施加P、V操作，即都可申请和释放该临界资源，其初始值置为1。取值意义如下：信号量s＝1；表示资源空闲，可供使用。信号量s＝0；表示资源已被占用，无其它进程等待。信号量s＝-n；表示资源已被占用，还有n个进程因等待资源而阻塞。它为一组需同步协作完成任务的并发进程而设置，只有拥有该资源的进程才能对它施加P操作（即可申请资源），而由其合作进程对它施加V操作（即释放资源）。第69页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章70例题补充与讲解：1知识点：进程的前趋图题目：已知一个求值公式如下所示，如果A、B已赋值，请画出该公式求值过程的前趋图思路：分辨可以并发进行的运算保存计算的中间结果，并为每条语句命名第70页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章71例题补充与讲解：1第71页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章72例题补充与讲解：2知识点：信号量的应用题目：设有一个作业由四个进程组成，这四个进程必须按右图的次序运行，试用P、V操作表达四个进程的同步关系。思路：设三个同步信号量b1、b2、b3，分别表示进程T2、T3、T4是否可以开始执行，初值为0。第72页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第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操作）第73页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章74例题补充与讲解：3知识点：信号量的应用题目：设有两个优先级相同的进程P1和P2如下，信号量S1和S2的初值为0。请问P1、P2并发执行结束后，x、y、z的值分别是多少？进程P1y=1;y=y+2;V(S1);z=y+1;P(S2);y=z+y;进程P2x=1;x=x+1;P(S1);x=y+x;V(S2);z=x+z;思路：P1和P2具有相同的优先级，并发，具有顺序的不确定性；信号量S1和S2使得语句的执行顺序具有了制约关系绘制对应的前趋图第74页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第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第75页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章76提问环节－关于临界区的管理软件方法临界区标志法进程数组标志法1进程数组标志法2双标志法硬件方法缺陷信号量机制整型信号量基本信号量原理记录型信号量多个进程申请同一类资源AND型信号量同一进程申请多个不同资源信号量集同一进程申请多个同类资源多个进程申请多个不同资源第76页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章77本章目录4.1进程并发4.2临界区管理4.3信号量机制4.4用信号量解决经典进程同步问题4.5管程4.6进程通信4.7线程的同步和通信重点与难点生产者－消费者问题读者－写者问题哲学家就餐问题第77页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章78生产者-消费者问题假设缓冲池中有n个缓冲区，每个缓冲区存放一个消息；可利用互斥信号量mutex使诸进程对缓冲池实现互斥访问；利用empty和full计数信号量分别表示空缓冲及满缓冲的数量。又假定这些生产者和消费者互相等效，只要缓冲池未满，生产者可将消息送入缓冲池；只要缓冲池未空，消费者可从缓冲池取走一个消息。同步问题：生产者：P进程不能往“满”的缓冲区中放产品；消费者：C进程不能从“空”的缓冲区中取产品。第78页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章79同步与互斥问题互斥信号量mutex：防止多个进程同时进入临界区同步信号量empty和full：保证事件发生的顺序缓冲区满时，Producer停止运行缓冲区空时，Consumer停止运行概念差别——互斥与同步（并发的两个要素）互斥：保护临界区，防止多个进程同时进入同步：保证进程运行的顺序合理第79页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章80同步/互斥信号量的使用方法互斥信号量必定成对出现：进入临界区——临界区——退出临界区同步信号量未必成对出现，依赖于同步关系的性质同步信号量和互斥信号量的操作顺序基本原则：互斥信号量永远紧邻临界区第80页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章81生产者P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1)modn;Signal(mutex);Signal(full);消费者C:Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1)modn;Signal(mutex);Signal(empty);mutex,full,empty:semaphoremutex:=1;full:=0;empty:=n;生产者-消费者问题第81页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章82P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1)modn;Signal(mutex);Signal(full);empty=nfull=0mutex=1in,out=0生产者和消费者之间的约束：临界区。生产者在生产时，消费者不能消费。生产者-消费者问题第82页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章83P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1)modn;Signal(mutex);Signal(full);empty=nfull=0mutex=1in,out=0控制：缓冲区满时不能继续生产，制约生产者进程P。生产者-消费者问题第83页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章84C：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1)modn;Signal(mutex);Signal(empty);empty=nfull=0mutex=1in,out=0生产者和消费者之间的约束：临界区。生产者在生产时，消费者不能消费。生产者-消费者问题第84页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章85C：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1)modn;Signal(mutex);Signal(empty);empty=nfull=0mutex=1in,out=0控制：缓冲区空时不能继续消费，制约消费者进程C。生产者-消费者问题第85页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章86说明wait和signal操作成对出现；对资源信号量的wait操作在前对互斥信号量的wait操作在后P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1)modn;Signal(mutex);Signal(full);C：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1)modn;Signal(mutex);Signal(empty);生产者-消费者问题第86页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章87P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1)modn;Signal(mutex);Signal(full);P：Wait(empty,mutex);Buffer(in)=nextp;in:=(in+1)modn;Signal(mutex,full);用AND型信号量解决同一问题生产者-消费者问题第87页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章88C：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1)modn;Signal(mutex);Signal(empty);C：Wait(full,mutex);netxc=buffer(out);out:=(out+1)modn;Signal(mutex,empty);用AND型信号量解决同一问题生产者-消费者问题第88页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章89读者-写者问题有两组并发进程:读者和写者,共享一组数据区要求：允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作第89页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章90信号量描述互斥关系分析读者和写者不能同时进入共享数据区多个写者不能同时进入共享数据区多个读者可以同时进入共享数据区同步关系分析读者进入缓冲区，写者必须等待写者进入缓冲区，读者必须等待读者优先：一旦有读者进入后续读者均可进入合理顺序：读者在先来的写者之后写者优先：只要有写者等待后续读者必须等待第90页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章91信号量描述如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待第91页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章92两个进程：Reader、Writer读者与写者间的互斥信号量：Wmutex＝1多个读者间的互斥信号量：Rmutex＝1Readcount：正在读取的进程数目Readcount＝0时允许写读者-写者问题第92页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章93wait(rmutex);Ifreadcount=0then wait(wmutex);Readcount:=readcount+1;signal(rmutex);……执行读取操作wait(rmutex);Readcount:=readcount-1ifreadcount=0then signal(wmutex);signal(rmutex);读者部分读者-写者问题第93页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章94wait(wmutex);……执行写操作signal(wmutex);写者部分读者-写者问题第94页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章95增加限制条件，即同时读取的读者数不能超过RNL,mx:=RN,1信号量集：Swait(S,d,t);Ssignal(S,d)S为信号量，d为需求量，t为下限值写者：Swait(mx,1,1;L,RN,0);……执行写操作Ssignal(mx,1);读者：Swait(L,1,1);Swait(mx,1,0);……执行读取操作Ssignal(L,1);读者-写者问题第95页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章96读者优先的信号量解法typedefintsemphsemphmutex=1;semphwrite=1;intrcount=0;Reader进程While(TRUE){P(mutex);rcount++;if(rcount==1)P(write);V(mutex);Read_Action();P(mutex);rcount--;if(rcount==0)V(write);V(mutex);}Writer进程While(TRUE){P(Write);Write_Action();V(write);}第96页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章97合理顺序的信号量解法typedefintsemphsemphrmutex=1;semphwmutex=1semphwrite=1;semphconcur=1;intrcount=0;intwcount=0;Reader进程While(TRUE){P(concur);P(rmutex);rcount++;if(rcount==1)P(write);V(rmutex);V(concur);Read_Action();P(mutex);rcount--;if(rcount==0)V(write);V(mutex);}Writer进程While(TRUE){P(wmutex);wcount++;if(wcount==1)P(concur);V(wmutex);P(Write);Write_Action();V(write);P(wmutex);wcount--;if(wcount==0)V(concur);V(wmutex);}第97页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章98互斥关系分析筷子：同一时刻只能有一个哲学家拿起筷子同步关系分析就餐：只有获得两个筷子后才能进餐特殊情况考虑死锁：如果每个哲学家都拿起一只筷子，都饿死并行程度：五只筷子允许两人同时进餐哲学家就餐问题第98页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章99哲学家就餐问题的直观解法哲学家进程#defineN5voidphilosopher(inti){While(TRUE){think（）；take_forks(i);take_forks((i+1)%N);eat();put_forks(i);put_forks((i+1)%N);}}思考1：这样的解法有何问题？思考2：对左右的叉子是否可用进行验证，这样的修改有何优缺点？思考3：需要引入几个信号量才能实现最优化的解法呢？第99页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章100为防止死锁发生可采取的措施：最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子；给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之；为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿。哲学家就餐问题第100页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章101进程同步应用示例讲解：1题目：桌上有一个盘子，可以存放一个水果。父亲总是把苹果放在盘子中，母亲总是把香蕉放在盘子中；一个儿子专等吃盘中的香蕉，一个女儿专等吃盘中的苹果。分析：四人公用一个盘子；盘子每次只能放一个水果，当盘子为空时，父母均可尝试放水果，但一次只能有一人成功；盘中是香蕉，儿子吃，女儿等；盘中是苹果，女儿吃，儿子等。进程描述：Father：父亲放置水果的进程；Mother：母亲放置水果的进程；Son：儿子吃水果的进程；Daughter：女儿吃水果的进程。变量设置：dish：表示盘子是否为空，初值=1；apple：表示盘中是否有苹果，初值=0；banana：表示盘中是否有香蕉，初值=0。第101页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章102进程同步应用示例讲解：1Father:P(dish);

将苹果放入盘中；

V(apple);dish：盘子是否为空，1apple：盘中是否有苹果，0banana：盘中是否有香蕉，0Son:P(banana);

从盘中取出香蕉；

V(dish);

吃香蕉；Mother:P(dish);

将香蕉放入盘中；

V(banana);Daughter:P(apple);

从盘中取出苹果；

V(dish);

吃苹果；第102页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章103进程同步应用示例讲解：2题目：水入缸供老和尚饮用。水缸可容纳10桶水。水井很窄，每次只能容一个桶取水。水桶总数为3个。每次入、取缸水仅为1桶，且不可同时进行。请给出取水、入水的算法描述。取水：从井中取水，从缸中取水入水：水倒入缸中分析：水缸和水井互斥，即水井每次容纳一个水桶进出，水缸也是如此；井中取水、倒水入缸、取水出缸，每次用水桶1个；水缸中可以装水10桶。进程描述：Get：从井中取水入缸；Use：从缸中取水饮用。变量设置：mutex1：用于实现对水井的互斥使用，初值=1；mutex2：用于实现对水缸的互斥使用，初值=1；empty：用于记录水缸还可以装入的桶数，初值=10；full：用于记录水缸中已装入的桶数，初值=0；count：用于记录可用水桶数，初值=3。第103页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章104进程同步应用示例讲解：2Get:P(empty);P(count);P(mutex1);

井中取水；

V(mutex1);P(mutex2);

倒水入缸；

V(mutex2);V(count);V(full);mutex1：对水井的互斥使用，1mutex2：对水缸的互斥使用，1empty：缸可以装入的桶数，10full：缸中已装入的桶数，0count：可用水桶数，3Use:P(full);P(count);P(mutex2);

缸中取水；

V(mutex2);V(empty);V(count);第104页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章105进程同步应用示例讲解：3题目：有一座桥如图所示，车流如图中箭头所示。桥上不允许两车交会，但允许同方向多辆车依次通行（即桥上可以有多个同方向的车）。用P、V操作实现交通管理，以防止桥上堵塞。第105页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章106进程同步应用示例讲解：3分析：车辆过桥时，提出过桥申请，如桥上无对方车辆则过桥；若该车为本方向第一辆车，应阻塞对方车辆过桥；当本方向无车辆过桥时，允许对方车辆过桥；同方向的多辆车可依次过桥，如果对方提出过桥申请，则阻塞本方向后续车辆过桥，待桥上车辆过完后，对方车辆过桥。同方向车辆的控制类似于读者-写者问题第106页,共145页，星期六，2024年，5月08.07.2024《计算机操作系统》-第4章107进程同步应用示例