进程同步知识课件

进程同步四川大学软件学院左劼背景并发(concurrent)地访问共享数据可能会引起数据不一致(inconsistency)维护数据的一致性需要某种机制保证协作进程有序地执行很多基于共享内存的解决方案都存在竞争条件(racecondition)有限缓冲区问题publicclassBoundedBuffer{publicvoidenter(Objectitem)...publicObjectremove()...privatevolatileintcount=0;privateintin=0;privateintout=0;privateObject[]buffer=newObject[BUFFER_SIZE];}enter()方法publicvoidenter(Objectitem){while(count==BUFFER_SIZE);

++count;buffer[in]=item;

in=(in+1)%BUFFER_SIZE;}问题当生产者和消费者并发地执行的时候，他们可能不能得到正确的结果！例如：如果count=5，那么执行++count和--count后，count的值可能是4、5或者6！原因:共享变量count被两个线程并发地访问并修改了分析共享变量count的修改:语句++count会被实现为下面的机器代码:register1=countregister1=register1+1count=register1语句--count会被实现为下面的机器代码:register2=countregister2=register2–1count=register2注意：这里的register1和register2是本地寄存器分析如果生产者和消费者试图并发地更新缓冲区，那么底层的机器代码可能会交错地执行具体如何交错，和两个进程如何被调度有关一个例子(假设count=5)T0:生产者:r1=count(r1=5)T1:生产者:r1=r1+1(r1=6)T2:消费者:r2=count(register2=5)T3:消费者:r2=r2–1(r2=4)T4:生产者:count=r1(count=6)T5:消费者:count=r2(count=4)于是count=4如果交换T4和T5，那么count=6但是，正确的结果应该是count=5竞争条件多个进程并发地访问和操作共享数据且执行结果和访问发生的特定顺序有关，称为竞争条件同步为了避免竞争条件，并发的进程需要同步，以保证同时只有一个进程操纵共享变量原子操作一个操作在执行过程中不会被打断为了避免竞争条件，一些语句应该被原子化地执行临界区问题(criticalsection)假设有n个进程竞争使用一些共享数据每个进程有一个特殊的代码段，称为临界区。在临界区中执行访问、操纵共享数据的动作必须保证，进程的临界区地执行是互斥的，即当一个进程在临界区内，其他的进程就不允许进入到临界区中解决临界区问题互斥：当一个进程在临界区内，其他的进程就不允许进入到临界区中有空让进：如果没有其他的进程在临界区内执行，并且有进程希望进入临界区，那么选择谁能下一个进入临界区的工作不能无限推迟有限等待：在一个进程做出进入其临界区的请求到该请求被允许期间，其它进程被允许进入其临界区的次数存在一个上限注意假设每一个进程的执行速度不为0不能对n个进程的线对速度做假设基本机器指令的执行是原子的如果两个机器指令在两个不同的CPU上并发执行，结果相当于以不确定的顺序顺序执行的结果临界区的两进程解法讨论临界区问题用于两个进程的算法两个进程标为P0和P1为方便起见，当用Pi表示一个进程的时候，用Pj表示另外一个进程，即j=1-i临界区的两进程解法publicclassWorkerextendsThread{publicWorker(inti,MutualExclusions){id=i;shared=s;}publicvoidrun(){...}

privateintid;privateMutualExclusionshared;}run()方法publicvoidrun(){

while(true){//entercriticalsectionshared.enter(id);

......//leavecriticalsectionshared.leave(id);}}MutualExclusion类publicabstractclassMutualExclusion{publicstaticvoidcriticalSection(){ //simulatethecriticalsection }publicstaticvoidnonCriticalSection(){//simulatethenon-criticalsection}

publicabstractvoidenter(intt);publicabstractvoidleave(intt);

publicstaticfinalintTURN_0=0;publicstaticfinalintTURN_1=1;}测试每一种算法publicclassTestAlgorithm{publicstaticvoidmain(Stringargs[]){MutualExclusionalg=newAlgorithm_1();Workerfirst=newWorker(0,alg);Workersecond=newWorker(1,alg);first.start();second.start();}}算法0–一个最容易想到的算法publicclassAlgorithm_0extendsMutualExclusion{publicAlgorithm_0(){flag=false;}

publicvoidenter(intt){while(flag)Thread.yield();flag=true;}publicvoidleave(intt){flag=false;}privatevolatilebooleanflag;}算法0分析算法0不能保证互斥访问当P0和P1几乎同时希望进入临界区的时候，如果调度合适，他们都会看到flag标志为false，于是都会设置标志为true，然后进入临界区算法1publicclassAlgorithm_1extendsMutualExclusion{publicAlgorithm_1(){turn=TURN_0;}publicvoidenter(intt){while(turn!=t)Thread.yield();}publicvoidleave(intt){turn=1-t;}privatevolatileintturn;}算法1分析如果turn=i，那么允许Pi进入临界区满足互斥访问保证只有一个进程可以进入临界区但不满足有空让进需要进程满足严格的交替进入临界区

如果turn=0并且P1

准备进入临界区，那么它并不能进入算法2publicclassAlgorithm_2extendsMutualExclusion{publicAlgorithm_2(){flag[0]=false;flag[1]=false;}publicvoidenter(intt){intother=1-t;flag[t]=true;while(flag[other]==true)Thread.yield();}publicvoidleave(intt){flag[t]=false;}privatevolatileboolean[]flag=newboolean[2];}算法2分析提供了充分的进程状态信息如果flag[i]=true，表示

Pi准备进入临界区满足互斥访问，但没有满足有空让进

例如：P0设置flag[0]=true，恰好在while循环之前，发生上下文切换，P1设置flag[1]=true，于是

P0和P1都要永远等待，没有哪个进程可以进入临界区算法3publicclassAlgorithm_3extendsMutualExclusion{publicAlgorithm_3(){flag[0]=false;flag[1]=false;turn=TURN_0;}publicvoidenter(intt){...}publicvoidleave(intt){...}

privatevolatileintturn;privatevolatileboolean[]flag=newboolean[2];}publicvoidenter(intt){intother=1-t;flag[t]=true;turn=other;while((flag[other]==true)&&(turn==other))Thread.yield();}publicvoidleave(intt){flag[t]=false;}算法3分析Pi设置flag[i]=true，表示Pi希望进入临界区Pi设置turn=j，表示Pi希望应该轮到Pj进入临界区符合所有的三个要求，解决了两进程的临界区问题当flag[j]=false(表示Pj不希望进入临界区)或者turn!=j(例如turn=i，表示仅仅允许Pi进入临界区)，于是Pi可以进入临界区先修改turn值的进程得到访问临界区的权利同步硬件仅仅通过软件实现的同步程序非常复杂，也容易出错，通过硬件功能的帮助，可以比较容易地实现符合要求的同步程序如何实现原子的硬件指令？单处理器环境中只要简单禁止中断就可以了但是在多处理环境中，就没有这么简单，禁止中断的工作需要传播到所有的处理器，需要处理器同步，导致效率降低可用于同步的两条指令许多系统提供了特殊的可原子化执行的硬件指令用于实现进程同步检查和修改一个存储单元的内容

test-and-set指令交换两个存储单元的内容

swap指令同步硬件结构示意代码–数据结构HardwareDataClass:publicclassHardwareData{publicHardwareData(booleanv){data=v;}

publicbooleanget(){returndata;}

publicvoidset(booleanv){data=v;}

privatebooleandata;}test-and-set指令示意代码publicclassHardwareSolution{publicstaticbooleantestAndSet(HardwareDatatarget){HardwareDatatemp=newHardwareData(target.get());target.set(true);returntemp.get();}}使用test-and-set指令实现互斥HardwareDatalock=newHardwareData(false);while(true){while(HardwareSolution.testAndSet(lock))Thread.yield();//donothing //nowincriticalsectioncodelock.set(false);//outofcriticalsection }swap(交换)指令(示意代码)publicstaticvoidswap(HardwareDataa,HardwareDatab){HardwareDatatemp=newHardwareData(a.get());a.set(b.get());b.set(temp.get());}使用swap指令实现互斥HardwareDatalock=newHardwareData(false);HardwareDatakey=newHardwareData(true);while(true){key.set(true);do{HardwareSolution.swap(lock,key);}while(key.get()==true);//nowincriticalsectioncodelock.set(false);//outofcriticalsection }信号量(Semaphore)进程同步问题是一个大量存在的问题，应用中迫切需要一种通用的操作系统机制来简化进程同步的操作信号量就是其中的一种重要同步工具信号量是一个整数，除了初始化外，只能通过两个标准原子操作P和V来访问和修改

(这两个操作也称为wait和signal)信号量的值信号量的值是有实际意义的当信号量的值大于0时，它表示，还可以无阻塞地执行多少次P操作当信号量的值小于0时，它的绝对值表示，有多少进程等待在该信号量的P操作上如果用一个信号量来同步共享资源，可以把信号量的初值设置为共享资源的数量信号量上的操作对于信号量S，操作P(S)、V(S)定义为：

P(S){

while(S<=0);

S--;

}

V(S){

S++;

}两个操作都是原子的将信号量作为通用的同步工具SemaphoreS;//初始化为1P(S);//临界区内部......V(S);信号量中的忙等P操作中，为了等待信号量的值变为正数，程序将进行连续的循环，这称为忙等，也称为自旋锁忙等白白浪费了CPU资源，而这些资源本来是可以被其他进程所使用的。所以，一般来说，应该避免忙等，在等待的时候将CPU资源让给别的进程使用但忙等信号量也有其优点，因等待的时候不需要进行上下文切换，如果等待时间不长，可能效率还更高一些避免信号量中的忙等P(S){value--;if(value<0){addthisprocesstolistblock}}V(S){value++;if(value<=0){removeaprocessPfromlistwakeup(P);}}使用信号量进行进程同步publicclassFirstSemaphore{publicstaticvoidmain(Stringargs[]){Semaphoresem=newSemaphore(1);

Worker[]ws=newWorker[5];for(inti=0;i<5;i++)ws[i]=newWorker(sem,i);for(inti=0;i<5;i++)ws[i].start();}}工作线程publicclassWorkerextendsThread{publicWorker(Semaphores,intid){sem=s;this.id=id;}publicvoidrun(){while(true){sem.P();//incriticalsectionsem.V();}}

privateSemaphoresem;privateintid;}关于信号量block和wakeup操作是操作系统以基本系统调用的方式提供的信号量必须被原子化地执行，没有两个进程可以同时执行针对同一个信号量的P、V操作单处理器:P、V操作期间禁止中断多处理器:硬件解决方法：使用test-and-set指令软件解决方法：前面讨论的复杂方法死锁死锁：两个或多个进程无限地等待一个事件，而这些事件只能由这些等待进程之一来产生假设S和Q是初始化为1的两个信号量P0 P1P(S);P(Q);P(Q);P(S);

V(S);V(Q);V(Q);V(S);饿死(饥饿)饿死

–无限期的阻塞。一个进程的等待条件得到满足，但仍然可能无限期地在信号量的等待队列中等待这是一种设计缺陷，当系统不忙的时候，不会发生，但是系统很忙的时候，有些进程虽然已经满足了执行的条件，但仍然一直等待两种类型的信号量计数信号量–信号量的值跨越一个不受限制的范围二进制信号量–信号量值只能是0或者1二进制信号量很容易用硬件实现可以使用二进制信号量来实现计数信号量经典进程同步问题有限缓冲区问题(生产者-消费者问题)

BoundedBufferProblem读者-写者问题

ReadersandWritersProblem哲学家进餐问题

Dining-PhilosophersProblem有限缓冲区问题有一个或者多个进程是生产者，持续不断地产生数据有一个或者多个进程是消费者，持续不断地消耗数据两者通过一个有限大小的缓冲区交换数据有限缓冲区问题生产者消费者有限缓冲区消费者生产者消费者......问题分析首先，对数据结构的修改不能同时进行，否则可能对结构产生破坏当缓冲区满了，生产者应该停下来等待当缓冲区空了，消费者应该停下来如果有多个消费者，不能相互影响(取到同一个数据)有限缓冲区问题publicclassBoundedBuffer{publicBoundedBuffer(){...}publicvoidenter(Objectitem){...}publicObjectremove(){...}

privatestaticfinalintBUFFER_SIZE=2;privateSemaphoremutex;privateSemaphoreempty;privateSemaphorefull;privateintin,out;privateObject[]buffer;}

构造函数publicBoundedBuffer(){count=0;in=0;out=0;buffer=newObject[BUFFER_SIZE];mutex=newSemaphore(1);empty=newSemaphore(BUFFER_SIZE);full=newSemaphore(0);}enter()方法publicvoidenter(Objectitem){empty.P();mutex.P();

//addanitemtothebufferbuffer[in]=item;in=(in+1)%BUFFER_SIZE;mutex.V();full.V();}remove()方法publicObjectremove(){full.P();mutex.P();//removeanitemfromthebufferObjectitem=buffer[out];out=(out+1)%BUFFER_SIZE;mutex.V();empty.V();

returnitem;}第一类读者-写者问题没有读者会保持等待状态，除非已经有写者获得了访问共享数据的权限或者:读者不会仅仅因为有写者在等待而等待问题:写者饥饿第二类读者-写者问题一旦写者准备就绪，尽快满足写者的写请求或者：如果写者在等待访问共享数据，那么新的读者就不能开始新的共享读问题：读者饥饿读者publicclassReaderextendsThread{publicReader(Databasedb){server=db;}publicvoidrun(){intc;while(true){c=server.startRead();//nowreadingthedatabasec=server.endRead();}}privateDatabaseserver;}写者publicclassWriterextendsThread{publicWriter(Databasedb){server=db;}publicvoidrun(){while(true){server.startWrite();//nowwritingthedatabaseserver.endWrite();}}privateDatabaseserver;}共享数据publicclassDatabase{publicDatabase(){...}publicintstartRead(){...}publicintendRead(){...}publicvoidstartWrite(){...}publicvoidendWrite(){...}//numberofactivereadersprivateintreaderCount;//controlsaccesstoreaderCountprivateSemaphoremutex;//controlsaccesstothedatabaseprivateSemaphoredb;}Database构造函数publicDatabase(){readerCount=0;mutex=newSemaphore(1);db=newSemaphore(1);}startRead()方法publicintstartRead(){mutex.P();

++readerCount;//对第一个读者if(readerCount==1)db.P();

mutex.V();returnreaderCount;}endRead()方法publicintendRead(){mutex.P();--readerCount;//最后一个读者if(readerCount==0)db.V();

mutex.V();returnreaderCount;}写者方法publicvoidstartWrite(){db.P();}publicvoidendWrite(){db.V();}哲学家进餐问题最简单的解法分别用一个信号量表示每一根筷子，都初始化为1SemaphorechopStick[]=newSemaphore[5];P操作：拿起对应的筷子V操作：放下对应的筷子哲学家iwhile(true){//getleftchopstickchopStick[i].P();//getrightchopstickchopStick[(i+1)%5].P();//eatforawhile//returnleftchopstickchopStick[i].V();//returnrightchopstickchopStick[(i+1)%5].V();//thinkforawhile}解法分析解法存在死锁的可能性！当所有5位哲学家同时想吃东西的时候，他们都拿起左边的筷子，但这是右边已经没有筷子了，全都只有等待，而都不能进餐如何解决？修正死锁问题通过限制哲学家的行为来避免死锁只允许最多4位哲学家同时进餐只有左右两边的筷子同时得到满足，哲学家才能够取得着两根筷子进餐使用一个非对称的算法，比如，让奇数号数的哲学家先取左边的筷子，而偶数号数的哲学家先取右边的筷子信号量的优缺点信号量的优点提供了一种方便、有效的进程公布机制信号量的缺陷不正确的使用可能会导致错误的结果，并且这种错误很难发现和排除不正确的使用信号量还可能导致死锁错误使用信号量的例子对于一个临界区问题，正确的代码应该是：mutex.P();criticalSection();mutex.V();如果代码不正确，将可能导致各种不同情况的错误错误代码P()和V()操作的顺序错了mutex.V();criticalSection();mutex.P();临界区根本没有得到保护都写成了P()mutex.P();criticalSection();mutex.P();将会发生死锁管程(monitors)管程是一种提供线程安全的高层次的抽象管程是一种抽象的数据结构，封装了一些私有数据，并提供了一些公有方法管程确保一个时刻只有一个线程可以在管程内活动配合条件变量，可以使用管程解决进程同步问题管程模型monitormonitor-name{//variabledeclarationspublicentryp1(…){...}publicentryp2(…){...}}管程封装限制了线程直接对管程内部的直接访问管程阻止了对管程内定义的方法的并发访问，一个时间内只有个线程或进程可以访问管程内定义的方法于是程序员不需要显式地对同步编码管程条件变量(condition)条件变量代表了一种条件，在上面只能进行两个操作wait和signal条件变量只能存在于一个管程中，并且只能从管程内的方法对它进行访问当一个线程调用x.wait的时候，就会被挂起，直到被其他线程调用x.signal而唤醒x.signal唤醒一个在x上挂起的线程，如果没有线程在x上挂起，操作不产生影响(和信号量的V()操作比较，它永远都产生影响)当线程因调用x.wait被挂起，那么该线程释放对管程的控制，而被其他线程调用x.signal唤醒，则要继续拥有对管程的控制如果挂起的线程Q被线程P唤醒了，那么必须决定线程P或者Q有一方要等待，直到对方退出管程带有条件变量的管程哲学家进餐问题的解法monitordiningPhilosophers{int[]state=newint[5];staticfinalintTHINKING=0;staticfinalintHUNGRY=1;staticfinalintEATING=2;condition[]self=newcondition[5];publicdiningPhilosophers{for(inti=0;i<5;i++)state[i]=THINKING;}

publicentrypickUp(inti){...}publicentryputDown(inti){...}privatetest(inti){...}}pickUp()方法publicentrypickUp(inti){state[i]=HUNGRY;test(i);if(state[i]!=EATING)self[i].wait;}putDown()方法publicentryputDown(inti){state[i]=THINKING;

//testleftandrightneighborstest((i+4)%5);test((i+1)%5);}test()方法privatetest(inti){if((state[(i+4)%5]!=EATING)&&(state[i]==HUNGRY)&&(state[(i+1)%5]!=EATING)){state[i]=EATING;self[i].signal;}}哲学家idp.Pickup(i);eat();dp.putDown(i);另外一种管程解法monitordiningPhilosophers{condition[]eat=newcondition[5];boolean[]chopstick=newchopstick[5];

publicentrypickUp(inti){...}publicentryputDown(inti){...}}pickUp方法publicpickUp(inti){while(!(chopstick[i]&&chopstick[(i+1)%5])){eat[i].wait();}chopstick[i]=false;chopstick[(i+1)%5]=false;}putDown方法publicputDown(inti){chopstick[i]=true;chopstick[(i+1)%5]=true;eat[(i+4)%5].signal();eat[(i+1)%5].signal();}Java中的线程同步机制Synchronized,wait(),notify()MultipleNotificationsBlockSynchronizationJavaSemaphoresJavaMonitorsJava同步机制是从管程衍生而来的，可以看成是只有一个条件变量的管程同步方法(synchronized)每一个对象都有一个相连的锁调用同步的方法(synchronized)需要获得对象的锁如果已经有其他的线程获得了锁，线程将等待当线程退出同步方法将释放锁入口队列wait和notify方法仅仅使用同步方法并不能实现复杂的同步问题和管程中的条件变量类似，Java中引入了对象上的wait()和notify()方法，其功能分别对应条件变量的wait和signal方法应该注意，管程中wait、signal是作用在条件变量上的，而Java中的wait和notify是作用在对象上的wait()方法当一个线程调用对象的wait()方法，将会发生以下事件：线程释放对象的锁 线程状态被设置为阻塞线程被放置到对象的等待队列入口队列和等待队列notify()方法当一个线程调用对象的notify()，将发生下列事件：从对象的等待队列中任意选定一个线程T将线程T移动到入口队列将线程T的线程状态设置为就绪T可以再次竞争获得对象的锁用Java实现生产者-消费者问题classBoundedBuffer{publicstaticfinalintBUFFER_SIZE=5;

publicsynchronizedvoidenter(Objectitem){...}publicsynchronizedObjectremove(){...}privateObject[]buffer=newObject[BUFFER_SIZE];privateintcount=0;privateintin=0,out=0;}enter()publicsynchronizedvoidenter(Objectitem){while(count==BUFFER_SIZE){try{wait();}catch(InterruptedExceptione){}}++count;buffer[in]=item;in=(in+1)%BUFFER_SIZE;notify();}remove()publicsynchronizedObjectremove(){while(count==0){try{wait();}catch(InterruptedExceptione){}}--count;Objectitem=buffer[out];out=(out+1)%BUFFER_SIZE;

notify();

returnitem;}多重notificationnotify()从等待队列中任意选择一个线程，也许这个线程并不是期望被选中的notify()并不能够指定特定的线程notifyAll()把等待队列中的所有线程都移动到入口队列中，这样线程可以自己决定哪一个线程应该下一个进行处理当等待队列中有多个线程时，notifyAll()提供了一种保守策略，效果不错用Java同步机制解决读者-写者问题publicclassDatabase{publicDatabase(){readerCou