苏州大学操作系统概念第六章

Chap6进程同步6.2内容1.背景2.临界区问题3.软件和硬件解决方法4.信号量5.经典同步问题6.管程7.同步实例1、背景6.4数据的不一致性多个进程并发或并行执行可在任何时候被中断，部分代码连续执行对共享数据的并发/并行访问可能导致数据的不一致性不可再现性保证并发进程正确执行顺序的机制-同步例子：解决有界缓冲问题的共享内存方法中使用n个缓冲区的问题增加变量counter初始化为0每次向缓冲区增加一个新项时，counter递增每次从缓冲区中移去一项时，counter递减6.5Shareddata#defineBUFFER_SIZE10typedefstruct{...}item;itembuffer[BUFFER_SIZE];intin=0;intout=0;intcounter=0;有界缓冲区6.6生产者进程itemnextProduced;while(1){while(counter==BUFFER_SIZE);/*donothing*/buffer[in]=nextProduced;in=(in+1)%BUFFER_SIZE;counter++;}有界缓冲区enter（）6.7消费者进程itemnextConsumed;while(1){while(counter==0);/*donothing*/nextConsumed=buffer[out];out=(out+1)%BUFFER_SIZE;counter--;}有界缓冲区remove（）6.8下列语句必须被原子性地执行counter++;counter--;原子操作意味着一个操作在整个执行期间没有中断。有界缓冲区6.9语句“count++”可按如下方式以机器语言实现：register1=counterregister1=register1+1counter=register1语句“count--”可按如下方式来实现：register2=counterregister2=register2–1counter=register2初时count=5:S0:producerexecuteregister1=counter{register1=5}S1:producerexecuteregister1=register1+1{register1=6}S2:consumerexecuteregister2=counter{register2=5}S3:consumerexecuteregister2=register2–1{register2=4}S4:producerexecutecounter=register1{counter=6}S5:consumerexecutecounter=register2{counter=4}有界缓冲区如生产者和消费者试图并发地更新缓冲区，汇编语句可能交叉执行交叉取决于生产者和消费者进程如何被调度6.10竞争条件:多个进程并发访问和操作同一数据的情况。共享数据的最终结果取决于最后操作的进程为了防止上述竞争条件，并发进程必须同步竞争条件（RaceCondition）6.11同步（Synchronization）同步：对多个相关进程在执行次序上进行协调，使并发执行的进程间能有效地共享资源和相互合作，使程序执行具有可再现性，保证数据一致性进程间有两种同步形式：访问独占资源-互斥协调执行次序-同步P1P2P1P2Printer12、临界区6.13临界资源和临界区Criticalresource(临界资源)系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量Critical-Section(临界区)涉及到临界资源的代码段叫临界区itemnextConsumed;while(1){while(counter==0);/*donothing*/nextConsumed=buffer[out];out=(out+1)%BUFFER_SIZE;counter--;}临界区临界资源6.14临界区是代码进程内的代码一段或多段不一定连续不一定相同若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问临界区(criticalsection)6.15解决临界区要求1.互斥(MutualExclusion)：假定进程Pi在其临界区内执行，其他任何进程将被排斥在自己的临界区之外具有相同临界资源的临界区才需要互斥2.有空让进(Progress)：临界区无进程执行，不能无限期地延长下一个要进入临界区进程的等待时间3.有限等待(BoundedWaiting)：每个进程进入临界区前的等待时间必须有限（不能无限等待）6.16一个访问临界资源的循环进程的描述repeatentrysectioncriticalsection;exitsectionremaindersection;untilfalse;临界区(criticalsection)3、软件和硬件解决方法6.18只有2个进程,P0和P1Pi进程的通用结构do{进入区criticalsection退出区remindersection}while(1);进程可以共享一些公共变量来同步它们的行为解决问题的初始尝试6.19共享变量:intturn;初始turn=0turn==iPi能进入临界区j=1-i进程Pido{while(turn!=i);临界区turn=j;剩余区}while(1);满足互斥条件，但不满足有空让进算法1-轮流进临界区6.20共享变量booleanflag[2];初始flag[0]=flag[1]=false.flag[i]=truePi准备进入临界区进程Pido{flag[i]:=true;while(flag[j]);criticalsectionflag[i]=false;remaindersection}while(1);满足互斥，但不满足有空让进需求，存在死锁算法2—竞争进入临界区6.21合并算法1和2的共享变量进程Pido{flag[i]:=true;turn=j;while(flag[j]andturn=j);criticalsectionflag[i]=false;remaindersection}while(1);满足三个需求；解决了两个进程的临界区问题思考：为什么？算法3-Peterson算法6.22硬件同步许多系统采用硬件同步机制来处理临界区基于锁的解决方法利用锁来保护临界区单处理器：禁止终端当前运行代码不被中断不适合多处理器现代操作系统：特殊硬件指令原子操作（不可中断操作）do{acquirelockcriticalsectionreleaselockremaindersection}while(TRUE);6.23原子地检查和修改字的内容.booleanTestAndSet(boolean&target){booleanrv=target;target=true;returnrv;}TestAndSet6.24共享数据:booleanlock=false;进程Pido{while(TestAndSet(lock));criticalsectionlock=false;remaindersection}Test-and-Set指令实现互斥4、信号量6.26信号量Semaphore一种不需要忙等待的同步工具.信号量S–整型变量仅能通过两个不可分割的[原子]操作访问P(S):whileS0dono-op;S--;V(S):S++;P(S)和V(S)操作不可中断。整型信号量的问题：忙等6.27去除忙等的信号量P(S){S--;if(S0){addthisprocesstolistblock}}V(S){S++;if(S=0){removeaprocessPfromlistwakeup(P);}}思考:S值的含义是什么?6.28两种类型信号量计数信号量–变化范围没有限制的整型值二进制信号量–变化范围仅限于0和1的信号量；容易实现可以将计数信号量S用作二进制信号量同步信号量和互斥信号量6.29互斥信号量SemaphoreS;//初始化为1P(S);CriticalSection()//临界区V(S);信号量的使用：•S必须置一次且只能置一次初值，初值不能为负数•除了初始化，只能通过执行P、V操作来访问S6.30同步信号量实现各种同步问题例子：P1和P2需要S1比S2先运行semaphoresynch=0P1:S1;signal(synch);P2:wait(synch);S2;6.31死锁和饥饿死锁–两个或多个进程无限期地等待一个事件的发生，而该事件正是由其中的一个等待进程引起的.S和Q是两个初值为1的信号量P0P1P(S);P(Q);P(Q);P(S);V(S);V(Q);V(Q)V(S);饥饿–无限期地阻塞。进程可能永远无法从它等待的信号量队列中移去.5、经典同步问题6.33经典同步问题有限缓冲区问题（生产者-消费者问题）读者写者问题哲学家就餐问题6.34信号量empty初值为1，full初值为0单缓存生产者-消费者解决方案P：Repeat生产一个产品；P(empty);送产品到缓冲区；V(full);UntilfalseC：RepeatP(full);从缓冲区中取产品；V(empty);消费产品；Untilfalse6.35共享数据semaphorefull,empty,mutex;初始化:full=0,empty=n,mutex=1多缓冲区问题共享缓冲区生产指针消费指针Producer1Producer2...ProducerMConsumer1Consumer2...ConsumerN满空指针移动方向6.36生产者：do{…produceaniteminnextp…wait(empty);wait(mutex);…addnextptobuffer…signal(mutex);signal(full);}while(1);解决方法消费者：do{…wait(full)wait(mutex);…removeanitemfrombuffertonextc…signal(mutex);signal(empty);…consumetheiteminnextc…}while(1);6.37读者写者问题读者写者问题有两组并发进程:读者和写者,共享一组数据区,要求：允许多个读者同时执行读操作；不允许读者、写者同时操作；不允许多个写者同时操作。6.38读者优先如果读者来：1）无读者、写者，新读者可以读。2）有写者等，但有其它读者正在读，则新读者也可以读。3）有写者写，新读者等如果写者来：1）无读者，新写者可以写。2）有读者，新写者等待。3）有其它写者，新写者等待。6.39读者写者问题解决方案读者：RepeatP(mutex);readcount:=readcount+1;ifreadcount=1thenP(w);V(mutex);读P(mutex);readcount:=readcount-1;ifreadcount=0thenV(w);V(mutex);Untilfalse写者：RepeatP(w);写V(w);Untilfalse6.40思考第二类读者写者问题：写者优先条件：1）多个读者可以同时进行读2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）如何用PV操作实现？6.41ShareddataSemaphorechopStick[]=newSemaphore[5];哲学家就餐问题6.42哲学家就餐问题Philosopheri:while(true){//getleftchopstickP(chopStick[i]);//getrightchopstickP(chopSt