2.3进程的同步

1、2.1 进程的概念 2.2 进程控制 2.3 进程同步 2.4 进程通信 2.5 线程,第2章 进程管理,2.3进程的同步,进程的引入虽然改善了系统的资源利用率和提高了系统的吞吐量，但是进程的异步性，特别是它们在争用临界资源时，会给系统造成一定的混乱。为了解决这个问题，提出了进程同步的概念。,程序（间）并发执行的特征：,程序运行时独占资源,程序a,N = 3;,print(N),N = N + 1,print(N),K = 5;,print(K),K = K + 1,print(K),程序b,顺序执行 a b,打印结果：3 4 5 6,并发执行 a b,1,2,3,4,5,6,7,8,1,2,

2、3,4,5,6,7,8,打印结果：3 5 4 6,资源非封闭,进程的同步,进程同步问题的提出 进程异步推进可能造成混乱 混乱可能导致不可再现 进程同步目标,维持进程并发性 以提高系统效率,进程执行异步（断续）,资源的非封闭（共享）,结果不可再现,进程同步,进程间相互合作,资源有效共享,结果可再现,进程间的两种主要关系 进程间的关系与进程间的独立性 进程间的关系是在进程间相对独立的前提下发展的 独立获得资源 独立调度,进程间的同步关系（一）,正常行车,到站停车,开车,售票,开车门,关车门,司机,售票员,合作,合作,检查车况,维持秩序,获得打印数据,进程间的同步关系（二）,打印进程1,打印进程2,

3、打印,打印,互斥,获得打印数据,进程间的同步关系（三）,计算进程,打印进程,计算结果送到Buffer,从Buffer中取数,Buffer,互斥,完成数据计算,打印,通知打印进程打印,通知计算进程 送下一个数,合作,进程间的同步关系,相互合作,竞争资源,司机与售票员,多个打印者,计算者与打印者,？其他例子,流水线生产 仓库 两个队篮球比赛,两种形式的制约关系,间接相互制约关系 -源于资源共享,产生互斥问题 直接相互制约关系 -源于进程间合作,产生同步问题,正常行车,到站停车,开车,售票,开车门,关车门,司机,售票员,同步,同步,检查车况,维持秩序,同步实现初探（二）,打印进程 1,打印进程 2,

4、打印,打印,互斥,获得打印数据,获得打印数据,同步实现初探（三）,计算进程,打印进程,计算结果送到Buffer,从Buffer中取数,Buffer,互斥,互斥,向打印进程发信号 通知其从Buffer里取数,Buffer空？,否,是,完成数据计算,打印,向计算进程发信号 通知其向Buffer送数,Buffer空？,否,是,合作,进程间的同步关系,进程同步时面临的两种主要关系,相互合作,竞争资源,司机与售票员,多个打印者,计算者与打印者,事件、设备等抽象为资源 对进程间关系的处理变为对资源的访问方式,2.3.1 同步的概念,总结： 两种制约关系 1资源共享(进程互斥、进程间的间接相互制约） 2相互

5、协作（进程同步、直接相互制约） 进程同步的任务 保证各进程能互斥地访问这些资源（有效地共享资源）。 保证协作进程或线程的顺序执行，使它们不会出现与时间有关的差错，对数据的一致性进行维护（有效地相互合作）。,临界资源,临界资源：在一段时间内只允许一个进程访问的资源 对临界资源的访问必须采用互斥的方式进行，以实现对资源的共享。,怎样才能保证并发执行结果的正确性呢？ 如果我们把两个进程中使用公共变量有关的语句，各自都抽象为一个顺序的执行单位，也就是说，保证任何一个进程即使运行到其中这些语句时被打断，在它下一次被调度到而继续执行直到退出这些语句之前，另一个进程不允许进入使用公共变量的语句执行，也就一定

6、能保证那些语句总能被顺序地执行，显然其执行结果也一定是正确的,2.3.1.3临界区问题,临界区的概念：将多个进程访问临界资源的那一段程序代码称为临界区。 在临界区中，进程能改变变量的值，更新数据表或写文件等。 系统只允许一个进程在临界区执行，而不允许其它进程进入临界区。, 解决临界区问题必须遵循的原则：,1. 当某一时刻没有进程处于临界区内时，相应的临界资源处于空闲状态。因而可允许一个请求进入临界区进程立即进入临界区，以有效地利用临界资源。 2. 如果此时已有进程进入临界区，则其它试图进入临界区的进程必须等待，以保证各进程互斥地访问临界资源。 3. 当某个进程申请进入临界区时，它应在有限时间内

7、获得系统的响应，而能够进入临界区，以免进程陷入无限等待状态。 4. 当进程不能进入临界区时，应立即释放处理机，以免进程陷入忙等待状态。 1 空闲让进；2 忙则等待；3 让权等待；4 有限等待；,临界区,临界区,进入区,临界区,退出区,进入区,临界区,退出区,. .,. .,. .,. .,阻塞等待 资源释放,改变资源 状态,释放资源 唤醒等待进程,进程 1,进程 2,2.3.2同步的实现,解决临界区问题可以用软件或硬件实现。使用硬件实现进程的同步，可以使用户的编程任务更容易且系统的效率更高。 1关中断 使用关中断解决单处理器环境下临界区的问题。 使用关中断不能解决多处理器环境下临界区的问题。

8、关闭中断将延误处理器的处理时间，使系统性能下降。,锁机制,临界资源锁机制 例：商场的试衣间 是互斥资源 是临界资源 是共享资源 每个顾客必须遵循以下过程使用试衣间：,靠锁实现资源的共享管理,观察锁状态,关锁,使用试衣间,开锁,锁机制,临界资源锁机制,锁,锁变量L,每个进程必须按照以下过程操作资源,L = 1 关闭状态，资源忙,L = 0 打开状态，资源空闲,抽象,L=1,临界区,L=0,锁机制实现,一种简单的锁操作实现,void lock( L ) check:if ( L = = 1 ) goto check; else L = 1; ,void unlock( L ) L = 0; ,锁机

9、制实现,.,.,check: if ( L = = 1),goto check;,else L = 1;,临界区,L,进程 1,进程 2,unlock( L );,.,check: if ( L = = 1),goto check;,else L = 1;,临界区,unlock( L );,.,0,0,0,锁操作模型,锁操作的一般模型,Pi：. lock( L ) C( i ) unlock( L ) .,Pj：. lock( L ) C( j ) unlock( L ) .,C( i )： Pi的临界区,Pi： 进程i,出了问题的锁,.,.,check: if ( L = = 1),goto

10、 check;,else L = 1;,临界区,unlock( L );,.,check: if ( L = = 1),goto check;,else L = 1;,临界区,unlock( L );,.,出现问题的锁,进程 1,进程 2,L,0,尚未执行,问题出在？,判断状态后 改变状态前 被打断,锁机制实现,关锁操作不可被打断 用原语实现关锁操作 关锁操作在一个指令周期内完成,锁操作的特点： 实现了进程互斥访问临界资源。 不遵循让权等待原则。忙等,信号量机制,信号量机制：由Dijkstra提出的一种解决进程的同步与互斥的工具： 信号量用于表示资源数目或请求使用某一资源的进程个数的整型量.

11、S是与临界区内所使用的共享资源有关的信号量。 S0 可供并发进程使用的资源数 S0 正在等待使用临界区的进程数,P原语操作和V原语操作,P原语操作的主要动作 S1 如果S1以后仍大于等于零，则进程继续进行 如果S1以后小于零，则将该进程阻塞以后插入阻塞队列，然后转进程调度 V原语操作的主要动作 S1 如果相加后结果大于零，则继续进行 相加后结果小于等于零，则从该信号的等待队列中唤醒一个等待进程，然后返回原进程继续执行或者转进程调度。,P操作 P（S） S-; if (S=0) 继续执行； else 阻塞并进入等待队列； ,V操作 V（S） S=S+1; if (S 0) 继续运行； else

12、唤醒等待队列中的一 个进程，并继续运行； ,信号量： PV操作,记录型的信号量机制,是一个记录型的数据结构，包含两个数据项，一是计数值域，另一是等待该信号量的进程队列首指针域。描述如下： typedef struct semaphore int value; PCB *p; semaphore；,记录型信号量的P，V操作,P( s ),s.value = s.value - 1,s .value 0 ?,本进程获得 一个资源,临界区/资源访问区,本进程进入s.p 队列，进入阻塞 状态,N,Y,V( s ),s.value = s.value+1,s .value= 0 ?,将s.p中 第一个进

13、程 唤醒，,N,Y,P(s)和V(s)操作原语,void P(s) struct semaphore s; s.value=s.value-1; if (s.value0) block(s.p); ,void v(s) struct semaphore s; s.value=s.value+1; if (s.value=0) wakeup(s.p); ,2.3.2 信号量机制,AND型信号量（只需了解） 引入原因:一个进程需要先获得两个或更多的资源后,方能执行其任务.,Process A: Process B: p(Dmutex); p(Emutex); p(Emutex); p(Dmutex

14、);,Process A: p(Dmutex);于是mutex Process: p(mutex);于是mutex Process A: p(mutex);于是mutex阻塞 Process : p(mutex);于是mutex阻塞,P1（S1）；,P1（S2）；,P2（S2）；,P2（S1）；,进程1,进程2,系统推进过程为,进程2 阻塞,进程1 阻塞,S1,S2,进程1和进程2都无法继续推进出现死锁,。,。,V(S2); V(S1);,V(S1); V(S2);,基本思想 将对多个信号量的逐个申请改为一次，用一个原子操作完成 进程要么一次获得所有的资源，要么一个也申请不到 不会存在互相等待

15、的局面,信号量集,SP（S1，S2，S3Sn）,信号量集（了解） 引入原因:在记录型信号量中每次对仅能施以加或减操作，即每次只能获得或释放一个单位的临界资源 一次需要个某类临界资源时 资源数量低于某一下限值时，便不予分配 可对信号量机制加以扩充，形成一般化的“信号量集”机制,公用与私用信号量,公用信号量：,私用信号量：,一组进程共享，都可进行P、V操作,用于进程间资源的竞争,拥有信号量的进程只对信号量进行P操作,V操作由其他进程进行,用于进程间的合作,P（s）,V（s）,访问资源,P（s）,V（s）,访问资源,进程1：,进程2：,P（s）,V（s）,后继进程：,前驱进程：,2.3.3 信号量的

16、应用,.利用信号量实现进程互斥,P(s) V(s),临界区,P(s) V(s),临界区,临界 资源,进程,进程,原理:为临界资源设置一互斥信号量，初始值为，将个进程的临界区CS置于P(S)和V(S)操作之间即可,例1：n个并发进程共用一个公用变量Q，写出信号量实现n个进程互斥时的程序描述，并说明信号量的取值范围。,2.利用信号量实现前驱关系 设有个并发执行的进程：P1: s1 ; P2: s2 为了实现前驱关系S1 S2 ，可使他们共享一个公用信号量，初值为 P1 : S1; V(s) ; P2: P(s) ; S2 ;,利用信号量解决前驱图问题,例如：PA、PB、PC为一组合作的进程，其流程

17、如图所示，使用信号量实现三个进程的同步。,A,C,B,SB =0; SC =0; Begin PA : Begin V(SB) End;,PB : Begin P(SB ) V(Sc) End;,Pc : Begin P(Sc) End;,例如：PA、PB、PC为一组合作的进程，其流程如图所示，使用信号量实现三个进程的同步。 设两个同步信号灯SB、SC分别表示进程和能够开始 执行，其初值均为0（ SB=0 ，SC=0）。,A,C,B,SB =0; SC =0; Begin PA : Begin V(SB) V(SC ) End;,Pc : Begin P(Sc ) End; EndProgra

18、m;,PB : Begin P(SB ) End;,S1,S2,S3,S4,S5,S6,Var a,b,c,d,e,f,g;semaphore :=0,0,0,0,0,0,0; begin parbegin begin S1; v(a);v(b); end; begin p(a); S2; v(c); v(d); end begin p(b); S3; v(e); end begin p(c); S4; v(f); end begin p(d); S5; v(g); end begin p(e); p(f); p(g); S6; end parend end,a,b,e,d,c,f,g,利用信号量来描述前趋图关系,S1,S3,S2,S4,S5,S6,S7,S8,具有8个结点的前趋图。图中的前趋图中共有有向边10条，可设10个信号量，初值均为0；有8个结点，可设计成8个并发进程