《操作系统第二章进程同步与通信(第二部分)课件》由会员分享，可在线阅读，更多相关《操作系统第二章进程同步与通信(第二部分)课件（37页珍藏版）》请在金锄头文库上搜索。
1、1,第二章,进程的同步与通信,进程管理,2,本章讨论的主要问题,1、如何控制和协调并发进程异步执行 的时序？ 进程的同步机制 2、进程之间如何互相联系，传递信息？ 进程的通信,3,2.4 进程同步的概念（一）,并发执行的进程之间，通常有两种关系： 互斥关系 进程之间彼此无关，但是由于竞争使用同一共享资源而产生了相互约束的关系。这种因共享资源而产生的制约关系称为进程的互斥。 间接相互制约关系, 同步关系 多个并发执行的进程，在共同协作完成一项任务的过程中，相互约束，如一个进程在没有获得合作进程提供的必要信息之前，不能超越某个执行点。进程之间通过在执行时序上的某种限制而达到相互合作的这种约束关系称
2、为进程的同步 直接相互制约关系,一、并发进程间的约束关系,4,2.4 进程同步的概念（二）, 同步问题,缓冲区,键盘,计算,缓冲区,缓冲区,B进程,A进程,一、并发进程间的约束关系,A进程只有当缓冲区为空时，才能将数据输入缓冲区， B进程只有当缓冲区有数据时，才能从缓冲区取数进行计算。,进程的同步与互斥虽然是两个既有区别又有联系的概念，但从本质上看并发进程的异步执行都必须按一定的相互约束的时序进行，因此统称为“进程同步”。 显然，必须解决好进程的同步问题，才能保证并发进程的正常执行。,5,2.4 进程同步的概念（三）,每个进程 互斥访问临界资源的那段代码称为临界区。代码构成如下： repeat
3、 entry section 进入区 申请进入临界区 critical section 临界区 访问临界资源 exit section 退出区 退出对临界资源的访问 remainder section 剩留区 进程的其他代码 until false,二、临界资源 （criticalsection）,1。什么是临界资源 凡是以互斥方式使用的共享资源都称为临界资源。临界资源具有一次只允许一个进程使用的属性。,2。临界区 （critical section）,6,2.4 进程同步的概念（四）,空闲让进 无进程处于临界区内时，可让一个申请进入 该临界区的进程进入。 忙则等待 临界区内有进程时，申请进入
4、临界区的进程 必须等待。 有限等待 进程进入临界区的请求，必须在有限的时间 内满足。 让权等待 等待进入临界区的进程，必须立即释放CPU。,三、进程的同步机制,1、同步机制的准则,进程的同步机制就是要解决在进程异步运行时，在时间上施加某些限制，使其共享资源的操作与时间无关。 或称在执行时序上施加某种限制，达到彼此间的合作。,7,2.4进程同步的概念（五）,TS指令执行过程不可分割。 为临界资源设置一个布尔量 LOCK：,2.硬件同步机制,实现的基本思想是：对临界资源“加锁”,进程的同步机制可以用软件实现，也可以用硬件实现。,（1）用TestandSet 指令实现互斥,LOCK = ,false
5、 没有进程在临界区 true 有进程进入临界区,TS指令的形式： function ts（var lock：boolean）：boolean； begin ts：=lock； lock：=true； end；,8,2.4 进程同步的概念（六）,以两进程P1、P2并发执行为例，如果P1先执行：,调用TS指令,p1,TS=true,进入P1临界区,Lock：=false,进入剩余区,调用TS指令,p2,TS=true,进入P2临界区,Lock：=false,进入剩余区,调用TS指令,TS=true,N,Y,进入P1临界区,调用TS指令,TS=true,Y,N,调用TS指令,调用TS指令,TS=tr
6、ue,TS=true,Lock：=false,进入P2临界区,进入剩余区,若P1先进入临界区，则P2循环执行TS指令，直到P1退出临界区。,9,2.4 进程同步的概念（七）,如果P2先执行：若P2先进入临界区，则P1循环执行TS指令，直到P2退出临界区。,调用TS指令,p2,TS=true,进入P1临界区,Lock：=false,进入剩余区,调用TS指令,TS=true,N,Y,进入P2临界区,Lock：=false,进入剩余区,调用TS指令,p1,TS=true,进入P2临界区,Lock：=false,进入剩余区,调用TS指令,TS=true,Y,N,调用TS指令,调用TS指令,TS=tru
7、e,TS=true,进入P1临界区,结论： TS指令有效实现互斥（空闲让进、忙则等待） 循环测试，处于“忙等待”（未让权等待）,Lock：=false,进入剩余区,10,2.5 信号量机制及P、V操作(一）,其中： 信 号 量 值 表示某种资源的数量。 等待队列指针当信号量值为负时，表示该类资源已分配完，等待该类资源的进程排在等待队列中。L为指向该信号量等待队列的指针。,一。什么是信号量 并发进程间的相互制约关系从本质上说是由于争夺和共享资源而产生的。将资源抽象为信号量（Semaphore）， 引入在信号量基础上的同步操作原语： P操作、V操作。是一种比TS指令更加完善的同步机制。,定义： t
8、ype semaphore=record value：integer； 信号量值 l：list of process 信号量等待队列指针 end；,11,2.5 信号量机制及P、V操作 (二）, S.value ：= S.Value + 1； 若 S.Value 0 进程继续执行。 若 S.Value 0 则释放S等待队列中的一个进程 ， 使之转为就绪状态。,二。P、V操作原语,定义：VAR S：Semaphore； 1。P操作（wait 原语） 每作一次P操作，申请分配一个单位的资源。 P（S） 对信号量S 进行P操作。,2。V操作（Signal原语） V（S） 对信号量S 进行V操作，释放
9、一个单位的资源。, S.value ：= S.Value - 1； 若 S.Value 0 进程继续执行。 若 S.Value 0 进程阻塞，并进入等待队（L）。,12,2.5 信号量机制及P、V操作 (三）,P 操作 Procedure P（s）； Var s：semaphore； begin s.value：= s.value-1 if s.value 0 then 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；
10、,P、V操作的算法描述,13,2.5 信号量机制及P、V操作 (四）,说明： S.Value 0 时，其值表示某类资源可用数量。 S.Value 0 时，其绝对值表示在信号量队列中等待 该资源的进程数。 P、V操作有严格的不可分割性；执行过程不允许中断； P、V操作成对出现。,（根据同步机制的原则，分析P、V操作的特点，）,？问题？,如何使用P、V操作实现同步机制？,考虑： 如何控制互斥地使用临界资源？ 如何控制进程并发执行的时序？,实现同步机制基本思想是：加锁、解锁,14,2.5 信号量机制及P、V操作 (五）,设 mutex 公共互斥信号量 初值：mutex.Value = 1,利用P、V
11、操作实现互斥的模型,三。信号量的应用,1。实现进程互斥 以两个进程并发执行为例,进程P1 . . . P（mutex）； 进入P1临界区； V（mutex）； . . .,值0 ,进程P2 . . . P（mutex）； 进入P2临界区； V（mutex）； . . .,值0 ,值-1,进程P1先执行 P（mutex）；进程P1进入临界区； 进程P2开始执行 P（mutex）；进程P2阻塞，插入阻塞队列。 若进程P1再次执行 V（mutex）；mutex.Value=0 释放资源。,15,2.5 信号量机制及P、V操作 (六）,设 mutex 公共互斥信号量,利用P、V操作实现互斥的模型,三、
12、信号量的应用,1、实现进程互斥,初值： mutex.Value = 1,V（mutex）； . . .,值0 ,V（mutex）； . . .,进程P1,进程P2,. . .,P（mutex）；,进入P1临界区；,P（mutex）；,进入P2临界区；,值-1 ,. . .,值0 ,设先执行进程P1,16,2.5 信号量机制及P、V操作 (七）,值0 ,设 mutex 公共互斥信号量,利用P、V操作实现互斥的模型,三、信号量的应用,1、实现进程互斥,初值： mutex.Value = 1,V（mutex）； . . .,值0 ,进程P2,. . .,P（mutex）；,进入P2临界区；,V（mu
13、tex）； . . .,进程P1,P（mutex）；,进入P1临界区；,值-1,. . .,设先执行进程P2,17,P、V操作实现进程同步机制,1。实现进程互斥 定义公共的互斥信号量：mutex 初值： mutex.Value = 1 执行过程中mutex.Value 的值，在 1，0，-1 之间变化。,Var mutex : semaphore:=1; begin parbegin process 1: begin repeat P (mutex); critical section; V (mutex); remainder section; until false end,Process
14、 2:begin repeat P (mutex); critical section; V (mutex); remainder section; until false end parend End.,为了实现进程互斥地进入临界区，只须把临界区CS置于P (mutex)和V (mutex)之间。,18,2.5 信号量机制及P、V操作 (八）,分析：打印进程与计算进程之间有两个约束： 1）计算进程只有当缓冲区为空时，才能放入计算结果。 2）打印进程只有当缓冲区有结果时，才能从缓冲区取 计算结果打印。,定义两个信号量：SA、SB ，用于控制这两个约束： SA 控制打印进程从缓冲区取计算结果打印
15、。 SB 控制计算进程向缓冲区送计算结果。,2、实现进程同步 实例： 打印进程与计算进程的同步问题。,缓冲区,计算,打印机,缓冲区,缓冲区,打印进程,计算进程,SA,SB,设：SA、 SB 初值为 0 表示缓冲区为空。 当 SA 0 表示可以打印 当 SB = 0 表示可以放入计算结果。,19,2.5 信号量机制及P、V操作 (九）,2。实现进程同步 实例： 打印进程与计算进程的同步问题,设：SA 打印进程的私有信号量，初值为0， 当SA 0 时表示可以打印。 SB 计算进程的私有信号量，初值为0， 当SB = 0 时表示可以放入计算结果。,缓冲区,计算,打印机,缓冲区,打印进程,计算进程,SA,SB,缓冲区,思考题,？,？,？,？,请给出用 P、V操作实现计算进程与打印进程同步的模型。,缓冲区,缓冲区,20,2.5 信号量机制及P、V操作 (十）, 计算结果放入缓冲区； T2: V（SA）； L1: P（SB）； ,显然，进程CP与进程IOP相互制约： 只有CP执行到 T2，IOP才能
