进程管理part6.pptx

第二章 进 程 管 理 Heb Nomal University Department of Computer Science12.4.3读者-写者问题1.利用记录型信号量解决读者-写者问题 读者写者问题问题描述 有两组并发进程:读者和写者,共享一组数据区。要求：允许多个读者同时可执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作第二章 进 程 管 理 Heb Nomal University Department of Computer Science2问题分析第一类：读者优先无读者、写者，新读者可以读有写者等，但有其它读者正在读，则新读者也可以读有写者写，新读者等最后一个读者完成访问后，发现写者在等，则唤醒其中一个写着。写者完成访问后，发现有等待者，按照FIFO或者其它原则唤醒写着或者所有读第二类：写者优先多个读者可以同时进行读写者必须互斥，即只允许一个写者写，也不能读者写者同时进行，写者优先于读者，即一旦有写者，则后续读者必须等待，唤醒时优先考虑写者第二章 进 程 管 理 Heb Nomal University Department of Computer Science3变量：Readcount用来表示正在读的进程数目。信号量：rmutex用来保证读者之间互斥地修改readcount。wmutex是读者和写者公用的互斥变量，用来互斥读写同时进行rmutex、wmutex初值为1，readcount初值为0第一类读者写者问题读优先第二章 进 程 管 理 Heb Nomal University Department of Computer Science4读者-写者问题可描述如下：Varrmutex,wmutex:semaphore=1,1;Readcount:integer=0;beginparbeginReader:begin/读者repeatwait(rmutex);ifreadcount=0thenwait(wmutex);Readcount=Readcount+1;signal(rmutex);performreadoperation;wait(rmutex);readcount=readcount-1;ifreadcount=0thensignal(wmutex);signal(rmutex);untilfalse;endwriter:begin/写者repeatwait(wmutex);performwriteoperation;signal(wmutex);untilfalse;endparendend第二章 进 程 管 理 Heb Nomal University Department of Computer Science5Reader()While(1)P(s);P(rmutex);If(count=0)P(wmutex);/*当第1个读者读文件时，阻止写者写*/count+V(rmutex);V(s);读文件；P(rmutex);count-;If(count=0)V(wmutex);/*当最后1个读者读完文件时，允许写者写*/V(rmutex);writer()While(1)P(s);P(wmutex);写文件；V(wmutex);V(s);第二类读者写者问题写优先设3个信号量：rmutex-读互斥信号量，初值为1；wmutex-写互斥信号量，初值为1；s-用于在写进程到达后封锁后续的读者，初值为1；count-共享变量，用于记录当前正在读文件的读者数目，初值为0；第二章 进 程 管 理 Heb Nomal University Department of Computer Science6讨论P(s)和V(s)的位置当进程/线程在某个信号量上阻塞时，仅仅在对信号量的值进行操作时才能屏蔽中断；大部分时间都是使能中断的。对I/O系统的影响最小。当一个进程持有信号量（调用P操作后继续执行）时，它只阻止其他竞争有关的临界区的进程，而所有不参与竞争进入临界区的进程不受影响。我们再来看看上次的reader-writer第二类问题第二章 进 程 管 理 Heb Nomal University Department of Computer Science7Reader()While(1)P(s);P(rmutex);If(count=0)P(wmutex);/*当第1个读者读文件时，阻止写者写*/count+V(rmutex);V(s);读文件；P(rmutex);count-;If(count=0)V(wmutex);/*当最后1个读者读完文件时，允许写者写*/V(rmutex);writer()While(1)P(s);P(wmutex);写文件；V(wmutex);V(s);Istreallythateverybodyisright？第二章 进 程 管 理 Heb Nomal University Department of Computer Science8读者：while(true)P(w);P(readcount);V(w);读V(readcount);写者：while(true)P(w);fori:=1tondoP(readcount);写fori:=1tondoV(readcount);V(w);第二类读写问题（解法2）设2个信号量：lW是读者和写者公用的互斥变量，用来互斥读写或者写写同时进行，初值为1lReadcount用来记录当前有多少个读者在访问数据，初值n第二章 进 程 管 理 Heb Nomal University Department of Computer Science9信号量集2.利用信号量集机制解决读者-写者问题在记录型信号量机制中，wait(S)或signal(S)操作仅能对信号量施以加1或减1操作，意味着每次只能获得或释放一个单位的临界资源。而当一次需要当一次需要N个某类临界资源个某类临界资源时，便要进行N次wait(S)操作，显然这是低效的。此外，在有些情况下，当资源数量低于某一下限值当资源数量低于某一下限值时，便不予以分配。因而，在每次分配之前，都必须测试该资源的数量，看其是否大于其下限值。基于上述两点，可以对AND信号量机制加以扩充，形成一般化的“信号量集”机制。Swait操作可描述如下，其中S为信号量，d为需求值，而t为下限值。第二章 进 程 管 理 Heb Nomal University Department of Computer Science10信号量集Swait(S1,t1,d1,Sn,tn,dn)ifS1t1andandSntnthenfori=1tondoSi=Si-di;endforelsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSitiandsetitsprogramcountertothebeginningoftheSwaitOperation.endifsignal(S1,d1,Sn,dn)fori=1tondoSi=Si+di;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor;2.利用信号量集机制解决读者-写者问题S为信号量，为信号量，d为需求值，为需求值，而而t为下限值。为下限值。第二章 进 程 管 理 Heb Nomal University Department of Computer Science11一般“信号量集”的几种特殊情况：(1)Swait(S,d,d)。此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配。(2)Swait(S,1,1)。此时的信号量集已蜕化为一般的记录型信号量(S1时)或互斥信号量(S=1时)。(3)Swait(S,1,0)。这是一种很特殊且很有用的信号量操作。当S1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。第二章 进 程 管 理 Heb Nomal University Department of Computer Science12VarRNinteger;L,mx:semaphore=RN,1;beginparbeginreader:beginrepeatSwait(L,1,1);Swait(mx,1,0);performreadoperation;Ssignal(L,1);untilfalse;endwriter:beginrepeatSwait(mx,1,1;L,RN,0);performwriteoperation;Ssignal(mx,1);untilfalse;endparendend利用信号量集机制解决读者-写者问题第二章 进 程 管 理 Heb Nomal University Department of Computer Science13经典问题理发师问题（Barber ProblemBarber Problem）第二章 进 程 管 理 Heb Nomal University Department of Computer Science14理发师问题（BarberProblem）第二章 进 程 管 理 Heb Nomal University Department of Computer Science15*吸烟者问题（SmokerSmoker ProblemProblem）第二章 进 程 管 理 Heb Nomal University Department of Computer Science16*吸烟者问题（Smoker Problem）1/2第二章 进 程 管 理 Heb Nomal University Department of Computer Science17*吸烟者问题（Smoker Problem）2/2第二章 进 程 管 理 Heb Nomal University Department of Computer Science18在一辆公共汽车上，司机和售票员各行其职，司机负责开车和到站停车；售票员负责售票和开、关门，当售票员关好车门后，司机才能继续开车行驶。试用P、V操作实现司机与售票员之间的同步。(北京航天航空大学2002,哈工大2000,山东科技大学2006）这里包括的同步问题有：司机到站停车后，售票员才能开门；售票员关好车门后，司机才能启动汽车；司机启动汽车后，售票员才能售票。公交车问题第二章 进 程 管 理 Heb Nomal University Department of Computer Science19设信号量：S1-允许司机启动车辆，初值为1；S2-允许售票员售票,初值为0；S3-允许售票员开车门,初值为0。司机 P（S1）启动车辆V（S2）正常行车到站停车V（S3）售票员 P（S2）售票P（S3）开车门关车门V（S1）第二章 进 程 管 理 Heb Nomal University Department of Computer Science20在公共汽车上，司机负责开车、停车和驾驶，售票员负责门的开门、关门和售票。基本操作规则是只有停车后，售票员才能开门，只有售票员关门后，司机才能开车。汽车初始状态处于行驶之中。当只有1个司机、2个售票员、2个门、每个售票员负责一个门时的协调操作。请使用P、V原语实现售票员与司机之间的协调操作，说明每个信号量的含义、初值和值的范围。公交车问题扩展第二章 进 程 管 理 Heb Nomal University Department of Computer Science21某银行有人民币储蓄业务，由n个柜员负责，有1台取号机。每个顾客进入银行后先取一个号，若有人取号则需等他人取完后才能取，取到号后等待叫号，当一个柜员人员空闲下来，就叫下一个号。试用P，V操作正确编写柜台人员和顾客进程的程序。(昆明理工大学2006)顾客相当于生产者，柜员相当于消费者，所有顾客领取号码后就进入了一个等待队列，该等待队列相当于buffer。这个问题基本符合一般意义的“生产者消费者”问题，但又有所不同，不同在于顾客（即生产者）“取号进入等待队列”操作不需要与柜员（消费者）同步，所以，只需要两个信号量即可，一个用于互斥访问等待队列（对于顾客，就是互斥使用柜员机取号；对于柜员，就是叫号时候互斥访问等待队列），一个用于柜员“叫号”操作与顾客的同步。银行问题第二章 进 程 管 理 Heb Nomal University Department of Computer Science22varmutex=1,customer_count=0:semaphore;cobeginprocesscustomerbeginrepeatp(mutex);取号码，进入队列；v(mutex);v(customer_count);endprocessserversi(i=1,.,n)beginrepeatp(customer_count);p(mutex);从队列中取下一个号码；v(mutex);为该号码持有者服务；endcoend参考解法：第二章 进 程 管 理 Heb Nomal University Department of Computer Science23小和尚打水问题第二章 进 程 管 理 Heb Nomal University Department of Computer Science242009年考研题45.（7分）三个进程分）三个进程P1、P2、P3互斥使用一个包含互斥使用一个包含N（N0）个单元的缓冲区。）个单元的缓冲区。P1每次用每次用produce（）生成一个（）生成一个正整数并用正整数并用put（）送入缓冲区某一空单元中；（）送入缓冲区某一空单元中；P2每次用每次用getodd（）从该缓冲区中取出一个奇数并用（）从该缓冲区中取出一个奇数并用countodd（）统计奇数（）统计奇数个数；个数；P3每次用每次用geteven（）从该缓冲区中取出一个偶数并用（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。描述。第二章 进 程 管 理 Heb Nomal University Department of Computer Science25定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty控制生产者与消费者之间的同步；mutex控制进程间互斥使用缓冲区。Vars1=0,s2=0,empty=N,mutex=1;ParbeginP1:beginX=produce();P(empty);P(mutex);Put();Ifx%2=0V(s2);elseV(s1);V(mutex);end.P2:beginP(s1);P(mutex);Getodd();Countodd():=countodd()+1;V(mutex);V(empty);end.P3:beginP(s2)P(mutex);Geteven();Counteven():=counteven()+1;V(mutex);V(empty);end.Parend.第二章 进 程 管 理 Heb Nomal University Department of Computer Science262011年考研题45.（8分）某银行提供分）某银行提供1个服务窗口和个服务窗口和10个供顾客等待的座位。顾客到个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：客，并为其服务。顾客和营业员的活动过程描述如下：Cobeginprocess顾客i从取号机获得一个号码；等待叫号；获得服务；Process营业员while（TRUE）叫号；为顾客服务；coend请添加必要的信号量和P、V(或wait()、signal()操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。第二章 进 程 管 理 Heb Nomal University Department of Computer Science27返回2.3.4管程机制2.利用管程解决生产者-消费者问题管程的提出 采用PV同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中。P/V缺点：（）易读性差。（）不利于修改和维护。（）正确性难以保证。因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的第二章 进 程 管 理 Heb Nomal University Department of Computer Science281.管程的基本概念1)管程的定义管程由三部分组成：局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对局部于管程的数据设置初始值的语句。此外，还须为管程赋予一个名字。第二章 进 程 管 理 Heb Nomal University Department of Computer Science29图2-11管程的示意图管程：集中式同步机制。它的基本思想是：将共享变量以及对共享变量能够进行的所有操作集中在一个模块中，一个操作系统或并发程序由若干个这样的模块所构成。由于一个模块通常较短，模块之间关系清晰，提高了可读性，便于修改和维护，正确性易于保证第二章 进 程 管 理 Heb Nomal University Department of Computer Science30管程的语法描述如下：typemonitor_name=MONITOR；define；use；procedure()；beginend;function()：值类型；beginend；begin；end第二章 进 程 管 理 Heb Nomal University Department of Computer Science31说明：l局部于管程内部的数据结构，仅能被局部于管程内部的过程所访问，任何管程外的过程都不能访问它；l反之，局部于管程内部的过程也仅能访问管程内的数据结构。由此可见，管程相当于围墙，它把共享变量和对它进行操作的若干过程围了起来，所有进程要访问临界资源时，都必须经过管程(相当于通过围墙的门)才能进入，而管程每次只准许一个进程进入管程，从而实现了进程互斥。第二章 进 程 管 理 Heb Nomal University Department of Computer Science32管程是一种程序设计语言结构成分，它和信号量有同等的表达能力，从语言的角度看，管程主要有以下特性：(1)模块化。管程是一个基本程序单位，可以单独编译。(2)抽象数据类型。管程中不仅有数据，而且有对数据的操作。(3)信息掩蔽。管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，供管程外的进程调用，而管程中的数据结构以及过程(函数)的具体实现外部不可见。第二章 进 程 管 理 Heb Nomal University Department of Computer Science33 管程的要素：管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量。为了保证管程共享变量的数据完整性，规定管程互斥进入。管程通常是用来管理资源的，因而在管程中应当设有进程等待队以及相应的等待及唤醒操作第二章 进 程 管 理 Heb Nomal University Department of Computer Science34 问题：多个进程出现在管程中 当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权；当一个进入管程的进程执行唤醒操作时（如唤醒），管程中便存在两个同时处于活动状态的进程。处理方法有三种：等待继续，直到退出或等待 等待继续，直到等待或退出 规定唤醒为管程中最后一个可执行的操作HoareHansan为了解决这类问题，引入了条件变量condition。通常，一个进程被阻塞或挂起的条件(原因)可有多个，因此在管程中设置了多个条件变量，对这些条件变量的访问，只能在管程中进行。第二章 进 程 管 理 Heb Nomal University Department of Computer Science352)条件变量管程中对每个条件变量，都须予以说明，其形式为：Varx,y:condition。该变量应置于wait和signal之前，即可表示为X.wait和X.signal。例如，由于共享数据被占用而使调用进程等待，该条件变量的形式为：nonbusy:condition。此时，wait原语应改为nonbusy.wait，相应地，signal应改为nonbusy.signal。应当指出，X.signal操作的作用，是重新启动一个被阻塞的进程，但如果没有被阻塞的进程，则X.signal操作不产生任何后果。这与信号量机制中的signal操作不同。因为，后者总是要执行s=s+1操作，因而总会改变信号量的状态。第二章 进 程 管 理 Heb Nomal University Department of Computer Science36管程和进程的异同点：（1）设置进程和管程的目的不同（2）系统管理数据结构 进程：PCB 管程：等待队列（3）管程被进程调用（4）管程是操作系统的固有成分，无创建和撤消第二章 进 程 管 理 Heb Nomal University Department of Computer Science372.利用管程解决生产者-消费者问题在利用管程方法来解决生产者-消费者问题时，首先便是为它们建立一个管程，并命名为Proclucer-Consumer,或简称为PC。其中包括两个过程：(1)put(item)过程。(2)get(item)过程。第二章 进 程 管 理 Heb Nomal University Department of Computer Science38(1)put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count来表示在缓冲池中已有的产品数目，当countn时，表示缓冲池已满，生产者须等待。(2)get(item)过程。消费者利用该过程从缓冲池中取出一个产品，当count0时，表示缓冲池中已无可取用的产品，消费者应等待。第二章 进 程 管 理 Heb Nomal University Department of Computer Science39typeproducer-consumer=monitorVarin,out,count:integer;buffer:array0,n-1ofitem;notfull,notempty:condition;procedureentryput(item)beginifcountnthennotfull.wait;buffer(in)=nextp;in=(in+1)modn;count=count+1;ifnotempty.queuethennotempty.signal;end第二章 进 程 管 理 Heb Nomal University Department of Computer Science40procedureentryget(item)beginifcount0thennotempty.wait;nextc=buffer(out);out=(out+1)modn;count=count-1;ifnotfull.quenethennotfull.signal;endbeginin=out=0;count=0end第二章 进 程 管 理 Heb Nomal University Department of Computer Science41在利用管程解决生产者-消费者问题时，其中的生产者和消费者可描述为：producer:beginrepeatproduceaniteminnextp;PC.put(item);untilfalse;endconsumer:beginrepeatPC.get(item);consumetheiteminnextc;untilfalse;end