操作系统设计与实现(第二章)课件

操作系统

设计与实现Chapter2Processes操作系统

设计与实现Chapter2Process*Theimportanceofprocessinanoperatingsystem2.1Introductiontoprocesses *commonParallelism==Pseudoparallelism *Itisthecpurapidswitchingbackandforth *multiprocessoristherealparallelism *peopledesignamodel,sequentialprocesses顺序进程*Theimportanceofprocessin2.1.1TheprocessmodelCharacters:*Alltherunnablesoftwareareorganizedintoanumberofsequentialprocesses;(inthischapterwecalleditprocesses)*Theprocessisanexecutingprogram;Theprocessincludethevaluesofthealltheprogramcounter,registers，andvariables;(进程包括程序计数器、寄存器和变量的当前值。）Tothesecharacters,itiseasytoanalysisthecollectionoftheprocessesthankeeptracktherapidswitchofCPU2.1.1TheprocessmodelCharaABCDOneprogcountABCDFourprogcountABCDtimeprocessesABCDOneprogcountABCDFourproProcess---ProgramProcessisanexecutingprogram,ithasprogram,input,output,andstate.Anexample: scientistpreparethecakeforhisdaughter.Recipe:/resipi/食谱****AProcessisanactivityofsomekind,Ithasaprogram,input,output,andastate,Asingleprocessormaybesharedamongseveralprocesses,withsomeschedulingalgorithmbeingusedtodeterminewhentostopworkononeprocessandserviceadifferentone.Process---ProgramProcessisan理解进程和程序的区别：CPU：计算机科学家程序1：烘制生日蛋糕的食谱数据：面粉、鸡蛋、糖和香草汁等对应的进程1：阅读食谱、取来各种原料以及烘制蛋糕的一系列动作的总和。事件：女儿被蜜蜂螫伤保存进程1的当前状态：计算机科学家就记录下自己照着食谱做到哪儿了。程序2：急救手册数据：药物等对应的进程2：实施医疗救治（高优先级进程）当蜜蜂螫伤处理完之后，计算机科学家又回来做蛋糕，从他离开时的那一步继续做下去。理解进程和程序的区别：进程的创建系统初始化

(1)前台进程：同用户交互并替它们完成工作的哪些进程。

(2)后台进程：守护进程，处理网页、打印之类活动的进程。2.正在运行的一个进程执行了创建进程的系统调用。3.用户请求创建一个新进程。

在交互式系统中，用户可以通过键入命令启动程序。4.批处理作业的初始化

在操作系统认为有资源运行另一个作业时，它创建一个新的进程，并运行其输入队列中的一个作业。进程的创建系统初始化进程的终止正常退出：多数进程由于完成了它们的工作而终止。出错退出（自愿）:进程发现了严重错误。严重错误（非自愿）：通常是由于程序中的错误所致。例如，执行了一条非法指令，引用了不存在的内存，或除数是零。被其它进程杀死：当一个进程终止时，由该进程所创建的所有进程也都立即被杀死。进程的终止正常退出：多数进程由于完成了它们的工作而终止。Processhierarchies

AnyOS,tosupportprocess,itmustprovidesomewaytocreatealltheprocessesneeded.Usefork()

tocreateanewprocess,thefatherprocesscancreatehischildprocesses,0~~~more,andlater,theprocesstreemayappeared.InMinix,therootisinit,anditworksinthisway: readinfo,createterminal,startprogram,NFS,SMTP,WWW,FTP……ProcesshierarchiesAnyOS,toProcessStates进程之间经常需要交互、通信以及和其他进程同步。ForCommunicationbetweenprocesses exchangeinfoamongthem,but,oncemorethanoneprocessesleadtoblock**logically,ithavetostop,itwill.(waitourinput)**logically,itshouldcontinue,butitstopped,now,theCPUmaybeoccupiedbyanotherprocess.运行态（Running，在该时刻实际占用处理机）。就绪态（Ready，可运行，因为其它进程正在运行而暂时被挂起）。阻塞态（Blocked，除非某种外部事件发生，否则不能运行）。ProcessStates进程之间经常需要交互、通RunningBlockedReady12341.Processblocksforinput2.Schedulerpicksanotherprocess3.Schedulerpicksthisprocess4.InputbecomesavailableThreeStatesofprocess,andfourtransitionarethereRunningBlockedReady12341.Pro123……n-3n-2n-1…SchedulerUserprocessDiskprocessTerminalprocessInthismodel,wedon’tcareabouttheinterrupt123……n-3n-2n-1…SchedulerUserp2.1.2ImplementationofProcesses**ProcessTable(anarrayofstructures)（进程表） eachprocessisarecordofthistable,andeachrecordincludethestateoftheprocess,programcounter,stackpointer,andallocationofmemory…..;thus,whentheprocessisinreadystate,alltheinfowon’tlose.InMINIX,theprocessmanagement,memorymanagement,andfilemanagementareeachhandledbyseparatemoduleswithinthesystem,sotheprocesstableispartitioned.Lookatthepic:2.1.2ImplementationofProces操作系统设计与实现(第二章)课件InterruptVector（中断向量）Aninterruption,itrelatetoeachkindsofI/Odevice(hardware),itcontaintheaddressoftheinterruptserviceprocedure. Theinterruptprocedurestorethecurrentvariablesandinfotostacks,anddidsomeworksrelatedtoit’srecover.Now,thepreprocessisstored,andthenewonecouldcontinue.Whenitisfinished,theoldonecouldberecalled,andrunssmoothly,justnothinghadhappened.Ofcoursetheinterruptmustrelatedtotheirpriority.Therealprocedureis:InterruptVector（中断向量）Aninter操作系统设计与实现(第二章)课件2.1.3Threads（线程）1.Concept tothetraditionalprocess,oneprocessjusthasonecontrolclue（控制流）andoneprogramcounter.InmodernOS,moreandmoreOSsupportthemulti-controlclueinaprocess,andwecallthesecontrolcluethreads.Therealapplicationofthreadsmodel fromtheapplicationtoshowit’simportancetoOS2.1.3Threads（线程）1.Concept多线程的应用（1）explorernetscape（网络浏览器）

许多Web页面都包含有多幅很小的图像。 site:theimagesfolderliesD:\site\images process:builduponeconnection threads:buildupmoreconnection在浏览器内设立多个进程，同时请求传输多幅图像，可节省建立和释放链接的时间。Tosmallsizefiles,theconnection-buildingneedsmoretimethantransporting.transmittinguse.rar.zipthanfolder.多线程的应用（1）explorernetscape（多线程的应用（2）网络蚂蚁(NetAnts)是从因特网下载文件的工具软件，设计特点如下：

(A)支持HTTP和FTP协议，可同时下载1-5个文件；

(B)可随时中止正在下载的任务，任务将自动保存当前状态；

(C)支持拖放，可从浏览器中将链接拖入任务列表；

(D)裁剪板自动监视，并可指定将捕获的文件类型；

(E)捕获浏览器的动作，当用户在浏览器中单击链接时，网络蚂蚁将自动激活。多线程的应用（2）网络蚂蚁(NetAnts)是从因特网下载文ABToA:whenseverisbusy,itwillstopped,thewritingwillstopped. savethedestinationto….ToB:whenserverisbusy,otherthreadswillstilltry..thewritingwon’tstopped.useflashgetnetantABToA:whenseverisbusy,进程和线程的区别每个进程项每个线程项地址空间全局变量打开文件子进程定时器信号和信号处理程序统计信息程序计数器寄存器堆栈状态允许在同一个进程环境中有多个执行流（线程），这些流在很大程度上相对独立，但共享相同的地址空间。进程用来集合资源，而线程是CPU中调度的实体。进程和线程的区别每个进程项每个线程项地址空间程序计数器ToB:thesethreadssharethesameaddressspaceAndthesethreadscanwritetheinformationtothesameplace,thesamefile.Sothetablewillcanbeusedtothreads,thenthethreadscanberestore、block、ready….Meaning: alltheprogramcanusetheresourcesmoreefficiently,improvedtheOS’sperformance.ToB:thesethreadssharethe2.Problems TodifferentOS,theproblemsaredifferent.1）OSdon’tknowtheexistenceofthreads Thecontrolofthreadswillbyinuserspace. Thenmanythreadspackagesarethere.egP-threads2)OSknowtheexistenceofthreads thekernelwillcreatethetabletomaintainthethreads,threadstable.2.ProblemsThedifferenceofthetwokindofOSThefirstoneThesecondThreadsswitchedquickly线程完全在用户空间进行管理Threadsswitchedslow,thekernelhastojudgetheprocessandtheotherprocessOnethreadblocked,thekernelmaybeblocked.(toflashget,whenthenetworkisbroken,allthethreadsofthisprocesswillwastealotofresource.Onethreadblocked,thekernelmaychooseanotheronetorun.Conclusion: Getthemtogether,adoptthemtwo.Thedifferenceofthetwokind3)Thenewproblems!!Parent-process&child-process parentsprocesshasmanychildthreads,thenhowaboutthechild-process!!Multiprocessessharethedata-structure onethreadisclosingafile,whilethefileisbereadingbyanotherthread. onethreadisapplythememory,butnow,switchhappened,anotherthreadswillreapply.!!Errorreports inUnix,thereturnederrorvalueisstoredinavariable,whenoneisstoredavaluethere,thenanotherclearedthevalue,andwriteanewvaluetothere,then?3)Thenewproblems2.2InterProcessesCommunication(IPC)

CONTENTS:Howaprocesstosendmessagestoanotherone;Wemustmakesuretheprocessescan’teffecteachotherwhentheyarevisitingthecriticalarea;Whenthereliablerelationsarethere,howtodesigntheirproperorder.2.2InterProcessesCommunica2.2.1Racecondition（竞争条件）…..…..abcProg.cProg.n4567ProcessAProcessBOut=4In=7SpoolerToProcessA:readIn,write7toNext-free-slot(local);Interruption:Ablocked,andBcamein;BreadIn,got7,thensavenametoslot7;In+1=8,Bwillthinkhisjobisfinished;Acameback,andreadlocalnext-free-slot,savenametoslot7,andnext-free-slot+1=8,save8toIn.Bwillneverbeprint.打印机假脱机系统2.2.1Racecondition（竞争条件）…..…2.2.2Criticalregion-CriticalsectionMutualexclusion（互斥）:

anyshareresource(memory、file…)mayhappenthesimilarerrors(spooler),wehavetotakethismeasuretopreventtherace.Whentheracewillhappen? Iftheracehappensbetweentwoprocesses,theywon’tracefromthebeginningtotheend.Onlywhentheyvisitthesamememoryareaorthesamefile,theracewillhappen. Here,ifaprogramsegmentcouldvisitthesharedmemory,wecalledtheprogramsegmentcriticalregionorcriticalsection.(临界区或临界段）2.2.2Criticalregion-临界区的定义：假如两个或更多的进程需要访问一个不可共享的资源（打印机），在执行过程中，每个进程都给该I/O设备发送命令，接受状态信息，发送数据，接收数据。我们把这类资源称作临界资源，使用临界资源的那一部分程序称作成程序的临界区。

一次只允许有一个程序在临界区中。互斥的定义： 用某种手段，避免多个进程访问同一个临界区的操作叫做互斥。临界区的定义：假如两个或更多的进程需要访问一个进程的交互关系：可以按照相互感知的程度来分类互斥，指多个进程不能同时使用同一个共享资源；死锁，指多个进程互不相让，都得不到足够的资源；饥饿，指一个进程一直得不到资源（其他进程可能轮流占用资源）相互感知的程度

交互关系

一个进程对其他进程

的影响

潜在的控制问题

相互不感知(完全不了解其它进程的存在)

竞争(competition)

一个进程的操作对其他进程的结果无影响

互斥，死锁（可释放的资源），饥饿

间接感知(双方都与第三方交互，如共享资源)

通过共享进行协作

一个进程的结果依赖于从其他进程获得的信息

互斥，死锁（可释放的资源），饥饿，数据一致性

直接感知(双方直接交互，如通信)

通过通信进行协作

一个进程的结果依赖于从其他进程获得的信息

死锁，饥饿

进程的交互关系：可以按照相互感知的程度来分类互斥，指多个进程Howtosolveit? ifwecouldsettletheprocessesverywell,toavoidtheprocessesvisitthesharedmemoryatthesametime,thentheracewillbesolved.Toanygoodplans,weshouldmakesurethat:!!Anytwoprocessescan’tstayedinthecriticalareaatthesametime;!!Weshouldn’tdoanysuppositiontoCPU’sspeedandnumber;!!Theprocessoutofcriticalareacan’tblockotherprocess;!!Weshouldn’tlettheprocesskeeponwaitingoutofthecriticalarea.Howtosolveit?2.2.3Exclusionofbusywaiting忙等待形式的互斥**Closeinterrupt（关中段） thesimplestway,whentheprocessenteredthecriticalarea.Itwillclosetheinterrupt,whenitisfinished,itwillopentheinterruptagain;Shortage: itisfooltolettheuserhasrighttostartorcloseinterrupt. andtomulti-processorPC,closeinterruptiseffectedtooneprocessor,andtootherprocessors,thevisitofthesharedmemorywillcontinue.2.2.3Exclusionofbusywaitin**锁变量

对于某一个临界区，在它之外设置一个锁，每个进程要进入临界区的时候，首先要测试这把锁，如果锁打开着的（锁的值为0），则该进程可以进入（并将锁置1），如果关闭着的（锁的值为1）

，则该进程不能够进入；同样，一个进程进入了临界区后就把这把锁给锁上，当它出来后再打开这把锁，这样会对这个临界区有很好的保护作用，实现了互斥。临界区锁Process1Process2Process3但是矛盾依然有，跟Spooler目录一样。**锁变量 对于某一个临界区，在它之外设置一个锁，每个进程严格轮换法（交替法）严格轮换法是指几个进程轮换进入某一临界区，且顺序不能紊乱。While(TRUE){ while(turn!=0);/*wait*/ critical_region(); turn=1; noncritical_region();}While(TRUE){ while(turn!=1);/*wait*/ critical_region(); turn=0; noncritical_region();}初始值：turn=0;忙等待：进程不断地读turn的值，只是他没有做任何有意义的事（等待），而且浪费了cpu的时间（忙）。故称作忙等待busywaiting

turn==1严格轮换法（交替法）严格轮换法是指几个进程轮换进正常情况假如两个进程： 首先A进程进入，使用临界区后，修改turn的值，然后进入非临界区，然后B进程进入，根据判断，发觉可以进入，就进入临界区，执行完后，修改临界区的值，在然后进入自己的非临界区。依次A、B轮换执行。异常:(此时虽然不会竞争，但浪费了资源)如果进程A的非临界区很快能执行完，而进程B的非临界区却非常慢，则会：turn=1turn=0turn=1Waiting(turn)=1ABttt正常情况假如两个进程：turn=1turn=0turn=1W此时，两个进程的完成时间的衡量就应该按照慢的那个来衡量，而且，如果任何一个进程死掉了，则进程则会永远堵塞下去，不管是在临界区内还是在临界区外。荷兰数学家T.Dekker通过设置加警告变量的方法来回避这种情况的发生，但警告的同时也必须能够监测其他进程此时对临界区的使用情况，即出现了Dekker算法。参考别的书籍。（操作系统内核与设计原理P154）此时，两个进程的完成时间的衡量就应该按照慢的那个Dekker’sAlgorithmProcess0 Process1…. …..flag[0]=true; flag[1]=true;while(flag[1]==true) while(flag[0]==true){ {if(turn==1) if(turn==0){ { flag[0]=false; flag[1]=false; while(turn==1); while(turn==0); flag[0]=true; flag[1]=true;} }} }<criticalsection>; <criticalsection>;turn=1; turn=0;flag[0]=false; flag[1]=false;…. …...Dekker’sAlgorithmProcess0 Peterson算法-(两个进程的Peterson算法)Booleanflag[2]:数组元素intturn;VoidP0(){while(TRUE){flag[0]=TRUE;turn=0;while(flag[1]&&turn==0)/*wait*//*criticalarea*/flag[0]=false;/*noncriticalarea*/}}VoidP1(){while(TRUE){flag[1]=TRUE;

turn=1;while(flag[0]&&turn==1)/*wait*//*criticalarea*/flag[1]=false;/*noncriticalarea*/}} Flag[0]Flag[1]初始值为falsePeterson算法-(两个进程的Peterson算法)BPeterson算法是正确的算法turn=j;描述可进入的进程（同时修改标志值）检查对方flag，如果不在临界区则自己进入－－空闲则入；否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入－－先到先入，后到等待。Peterson算法是正确的算法硬件手段(TSL----testandsetlock)

原子操作：这种操作在运行的过程中，是不能也不允许被打断的，它是操作的最底层的部分，是不可分割的，称其为原子操作。TSL工作原理：将一个存储器字读到寄存器当中，然后在这个内存中存一个非零的值。这个读写的过程是个原子操作，是不可分割的。Enter_region: tslregister,lock cmpregister,#0 jneenter_region retLeave_region: movelock,#0 ret硬件手段(TSL----testandsetloc硬件方法的优点适用于任意数目的进程，在单处理器或多处理器上简单，容易验证其正确性可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量硬件方法的缺点等待要耗费CPU时间，不能实现"让权等待"可能"饥饿"：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上可能死锁（见下页）硬件方法的优点2.2.4睡眠和唤醒的引入对于Peterson和TSL问题，都能够很好地实现互斥，但也都同时存在问题：**忙等待，浪费CPU的资源。**进程的优先级有差别：当有两个进程，A、B，A的优先级高，处于就绪状态，而此时，B在临界区内，由于优先级低，故无法被调度，也就无法离开临界区，那A就只能够在临界区外等待。解决的途径就是引入新的概念：睡眠唤醒睡眠：对应着在临界区外的不停判断和等待；唤醒：对应着触发另一个满足条件的进程进入临界区。2.2.4睡眠和唤醒的引入对于Peterson和TSL问生产者和消费者问题：问题描述：若干进程通过有限的共享缓冲区交换数据。其中，"生产者"进程不断写入，而"消费者"进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。等待使用资源的消费者共享的缓冲区生产者生产者和消费者问题：问题描述：等待使用资源的消费者共享的缓冲#defineN100intcount=0;voidproducer(void){while(TRUE){produce_item();if(count==N)sleep();enter_item();count=count+1;if(count==1)wakeup(consumer)}}

voidconsumer(void){while(TRUE){remove_item();if(count==0)sleep();enter_item();count=count-1;if(count==N-1)wakeup(producer)}}

#defineN100对于生产者：只有当缓冲区里为零的时候，这时候消费者才有可能睡觉；对于消费者：只有当缓冲区里装满的时候，这时候生产者才有可能睡觉。导致的问题：类Spooler目录问题缓冲区为空，消费者检查，得到count=0,但未睡觉的时候，被调度程序挂起，此时它将保留一个局部变量来存储count的值，此时生产者开始工作并向缓冲区内放入资源，当资源等于1后，向消费者发送唤醒信号，而此时消费者没有睡眠，等消费者被恢复以后，检查自己存储过的count，发觉它等于零，则开始睡眠，而生产者则不停生产，当缓冲区满了以后自己也开始睡眠，这时候他们就都处于睡眠状态。对于生产者：2.2.5信号量1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)），是一种卓有成效的进程同步机制。原理：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一个位置停止，直到他接受到一个特定的信号。为了发信号，需要一个特殊的变量---信号量s为了通过信号量s传送信号，进程可执行原语signal(s);为了通过信号量s接收信号，进程可执行原语wait(s);2.2.5信号量1965年，由荷兰学者Dijkstra提对信号量的操作1.一个信号量可以初始化为非负数2.Wait操作是信号量减一，如果值变为了负数，则执行wait的进程被阻塞；Signal操作是信号量加一，如果值不是正数，则被wait操作阻塞的进程被解除阻塞。 除了以上三种操作以外，没有任何其他地方可以检查或操作信号量。 Wait==P Signal==V对信号量的操作1.一个信号量可以初始化为非负数多元信号量的PV操作Structsemaphore{intcount;queueTypequeue;

}Voidwait(semaphores){s.count--;if(s.count<0){placethisprocessins.queue;blockthisprocess;}}Voidsignal(semaphores){s.count++;if(s.count<=0){removeaprocessPfroms.queue;placeprocessPonready

list;}}此处的wait和signal都是原子操作，不会被中断影响。多元信号量的PV操作Structsemaphore{此二元信号量的PV操作VoidwaitB(binary_semaphores){if(s.value==1)s.value=0;else{placethisprocessins.queue;blockthisprocess;}}VoidsignalB(binary_semaphores){if(s.queue.is_empty())s.value=1;else{removeaprocessPfroms.queue;placeprocessPonreadylist;}}Structbinary_semaphore{enmu(zero,one)value;queueTypequeuw;}二元信号量的PV操作VoidwaitB(binary_P原语wait(s)s.count--; //表示申请一个资源;if(s.count<0) //表示没有空闲资源;{

调用进程进入等待队列s.queue;

阻塞调用进程;}P原语wait(s)s.count--; //表示申请一V原语signal(s)s.count++; //表示释放一个资源；if(s.count<=0) //表示有进程处于阻塞状态；{

从等待队列s.queue中取出一个进程P;

进程P进入就绪队列;}V原语通常唤醒进程等待队列中的头一个进程V原语signal(s)s.count++; //表示释利用信号量实现互斥为临界资源设置一个互斥信号量mutex(MUTualExclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏利用信号量实现互斥为临界资源设置一个互斥信号量mutex(#defineN100//缓冲区内槽数Typedefintsemaphore;semaphoremutex=1;semaphorefull=0;semaphoreempty=N;Voidproducer(void){intitem;while(TRUE){produce_item(&item);down(&empty);down(&mutex);enter_item(item);up(&mutex);up(&full);}}Voidconsumer(void){intitem;while(TRUE){down(&full);down(&mutex);remove_item(item);up(&mutex);up(&empty);consumer_item(item);}}#defineN100//缓冲区内槽数Voidp上面程序是利用信号量互斥来解决生产者---消费者问题的。其中： 信号量mutex用于互斥，保证任意时刻只能有一个进程读写缓冲区和相关的变量，保证了临界区、临界资源的合理安全使用。 信号量full和empty用来保证一定的时间顺序发生或不发生，它用来通知生产者和消费者，保证了当缓冲区满的时候生产者停止运行，以及当缓冲区空的时候消费者停止运行。上面程序是利用信号量互斥来解决生产者---消费者问题的。2.2.6管程信号量同步的缺点同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏）易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序；不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误；2.2.6管程信号量同步的缺点2.管程的引入1973年，Hoare和Hanson所提出；其基本思想是把信号量及其操作原语封装在一个对象内部。即：将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。管程的定义：管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。管程可增强模块的独立性：系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性引入管程可提高代码的可读性，便于修改和维护，正确性易于保证：采用集中式同步机制。一个操作系统或并发程序由若干个这样的模块所构成，一个模块通常较短，模块之间关系清晰。2.管程的引入3.管程的主要特性模块化：一个管程是一个基本程序单位，可以单独编译；抽象数据类型：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码信息封装：管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的.3.管程的主要特性4.管程的实现要素管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量；为了保证管程共享变量的数据完整性，规定管程互斥进入；管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作；4.管程的实现要素5.条件变量(condition)由于管程通常是用于管理资源的，因而在管程内部，应当存在某种等待机制。当进入管程的进程因资源被占用等原因不能继续运行时使其等待。为此在管程内部可以说明和使用一种特殊类型的变量----条件变量。每个表示一种等待原因，并不取具体数值－－相当于每个原因对应一个队列。5.条件变量(condition)6.管程的格式（类Pascal）TYPEmonitor_name=MONITOR;共享变量说明define本管程内所定义、本管程外可调用的过程（函数）名字表use本管程外所定义、本管程内将调用的过程（函数）名字表PROCEDURE过程名（形参表）； 过程局部变量说明；

BEGIN

语句序列；

END;......6.管程的格式（类Pascal）7.管程的的组成名称：为每个共享资源设立一个管程数据结构说明：一组局部于管程的控制变量操作原语：对控制变量和临界资源进行操作的一组原语过程（程序代码），是访问该管程的唯一途径。这些原语本身是互斥的，任一时刻只允许一个进程去调用，其余需要访问的进程就等待。初始化代码：对控制变量进行初始化的代码7.管程的的组成生产者—消费者的管程实现MonitorProducerConsumerconditionfull,empty;integercount;

procedureenter;beginifcount=Nthenwait(full);enter_item;count:=count+1;ifcount=1thensignal(empty)end

procedureremove;beginifcount=0thenwait(empty);remove_item;count:=count-1;ifcount=N-1thensignal(full)endcount:=0;Endmonitor;生产者—消费者的管程实现MonitorProducerProcedureproducer;beginwhiletruedobeginproduce_item;

ProducerConsumer.enterendend;Procedureconsumer;beginwhiletruedobeginProducerConsumer.remove;

consume_item;endend;Procedureproducer;Procedurec

管程与信号量的比较由于管程的机制，在某个时刻，只能有一个管程过程是活跃的，就类似于原语操作一样，也能够很好地解决Spooler目录的问题，而且更为简洁，在使用的过程中，能够直接分析代码，更容易理解使用。而且它的互斥操作是由编译器所支持的，更为安全，不宜出错。用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程。管程可以函数库的形式实现。相比之下，管程比信号量好控制。管程与信号量的比较弊端，支持管程的编程语言太少，因为它要求编译器的支持，而信号量对于一个操作系统来说是很容易添加的；他们都是用来解决访问同一个公共存储器的一个或多个CPU的互斥问题。通过将信号量放入共享内存中并用TSL指令来保护他们，可以避免竞争。但对于一个具有多个CPU，且每个CPU有自己的内存，有一个局域网相连的分布式系统来说，这些原语将完全失败。而管程由于编程语言的限制很难被实际应用。所以这两种都不是很实际的解决方法。

需要新的解决方法。弊端，支持管程的编程语言太少，因为它要求编译器的支2.2.7消息传递1.消息的原语形式Send(destination,&message)Receive(source,&message)都属于系统调用2.消息传递中的要点----针对与通信进程位于网络中不同机器上的情况1）由于进程发送了消息以后，接受者才能接收，故**对于一个执行send的进程**对于一个执行receive的进程发送被阻塞，等回复发送没有阻塞，做别的接受消息，继续执行等待消息a)等，直到接收到

b)放弃接收2.2.7消息传递1.消息的原语形式都属于系统调用2.消息2）消息接收的处理发送者发送消息，接收者收到后发送一个应答，这时：**应答信息被发送者收到，则继续发送新的消息；**应答信息丢失，则重发刚才的信息，此时，接收者需要区分消息的新旧，利用给消息加上连续序号来解决；3）消息系统设计的其他注意事项**系统需要解决进程命名的问题，保证消息的正确发送和接收；**效率的提升：严格控制系统中所用信息的长度，保证能够送入寄存器。2）消息接收的处理3.阻塞的处理及实用性阻塞可以对于send方发生，也可以对receive方发生，一般有三种组合：1）阻塞send，阻塞receive：发送和接收者都被阻塞，一直到完成信息的交付，通常称为“会合”，属于进程间的紧密同步。2）无阻塞send，阻塞receive，发送方尽管发送，接收者会阻塞，直到自己等到自己需要的信息来为止。类似于一个服务器进程给其他进程提供服务或资源。3）无阻塞send，无阻塞receive，不要求任何一方等待。3.阻塞的处理及实用性使用消息的互斥constintn=/*进程数目*/VoidP(inti){messagemsg;while(true){receive(mutex,msg);/*临界区*/send(mutex,msg);

/*其余部分*/

}}Voidmain(){create_mailbox(mutex);send(mutex，null);parbegin(P(1),P(2),…,P(n));}此处的mailbox表示一种数据结构，它是用来对一定数量的消息进行缓冲的地方，一般在信箱创建时确定消息的数量。使用消息的互斥constintn=/*进程数目*/Voi描述：

这里使用的是阻塞receive原语和无阻塞send原语，一组并发进程共享一个信箱mutex，它可以供所有的进程在发送和接收时使用，该信箱被初始化成一个无内容的消息。希望进入临界区的进程首先试图接收一条消息，如果信箱为空，则该进程被阻塞，一旦进程获得消息，它执行它的临界区，然后把该消息放回信箱。消息函数可以看成是在进程之间传递的一个令牌。对上述方案假设如果有多个进程并发执行接收操作，则：**如果有一条消息，它仅仅被传递给一个进程，其他进程被阻塞。**如果消息队列为空，所有进程被阻塞，当有一条消息可用时，只有一个阻塞进程被激活并得到这条消息。描述：生产者—消费者问题的解决Voidproducer(void){intitem;messagem;/*消息缓冲区*/while(TRUE){produce_item(&item);/*产生数据放入缓冲区*/receive(consumer,&item);/*等待空消息到达了，进入*/build_message(&m,item);/*构造消息供发送*/send(consumer,&m);/*向消费者发送一个数据项*/}}生产者—消费者问题的解决Voidproducer(voVoidconsumer(void){intitemi;messagem;for(i=0;i<N;i++)send(producer,&m);/*发送N条空消息*/while(TRUE){receive(producer,&m);/*收到一条包含数据的消息*/

extract_item(&m,&item);/*从消息中提取数据*/send(producer,&m);/*回送空消息作为应答*/consume_item(item);/*使用数据项进行操作*/}}Voidconsumer(void)这里的互斥由消息的发送原语send和receive来解决，而这里的缓冲区（信箱）实际上是容纳那些被发送而未被目标进程接收的消息。如果说，这个缓冲区内始终没有东西，而消息的发送和接收仍在运行，则说明这是处于会合态，即消息的发送和接收是同时的，没有迟延。这里的互斥由消息的发送原语send和receive来2.3经典IPC问题2.3.1哲学家进餐问题#defineN5/*哲学家的人数*/voidphilosopher(inti)/*给哲学家编号*/{while(TRUE){think();/*思考*/takefork(i);/*取叉子*/takefork((i+1)%N);/*取右边叉子*/eat();/*进餐*/putfork(i);/*放下左边叉子*/putfork((i+1)%N);/*放下右边叉子*/}}2.3经典IPC问题2.3.1哲学家进餐问题上述算法的局限与改进极限阻塞：当5个哲学家同时拿起叉子时，就会同时处于阻塞，然后同时放下，再同时拿起….------饥饿态解决办法1：加随机数，使哲学家们拿叉子的时间错开，可以解决问题。缺陷：太不可靠解决办法2：在think后加上一个mutex,使哲学家都要首先访问临界区，才能进餐，可以解决问题。缺陷：浪费，因为实际上可以有2个同时进餐，但实际上加了互斥后，只能有一个进餐，其4人都要等待。上述算法的局限与改进#defineN5/*哲学家的人数*/#defineLEFT(i-1)%N /*某个哲学家左边人的号码*/#defineRIGHT(i+1)%N /*某个哲学家右边人的号码*/#defineTHINKING0 /*思考*/#defineHUNGRY1 /*想取叉子*/#defineEATING2 /*哲学家在进餐*/typedefintsemaphore; /*信号量*/intstate[N]; /*记录每个人状态的数组*/Semaphoremutex=1; /*临界区的互斥*/semaphores[N]; /*各个哲学家的信号量*/voidphilosopher(inti) /*i:哲学家的号码,从0到N-1*/{ while(TRUE){ /*循环*/ think(); /*思考*/ takeforks(i); /*想取两个叉子，有可能阻塞*/ eat(); /*进餐*/ putforks(i); /*放回两只叉子*/}}#defineN5/*哲学家的人数*/voidtakeforks(inti) /*i:某个哲学家的编号,从0到N-1*/{down(&mutex); /*进入临界区*/state[i]=HUNGRY; /*记录下第i个哲学家饥饿*/test(i); /*尝试去拿两个叉子*/up(&mutex); /*退出临界区

*/down(&s[i]); /*得不到就阻塞*/}voidputforks(i) /*i:某个哲学家的编号,从0到N-1

*/{down(&mutex); /*进入临界区*/state[i]=THINKING; /*记录下第i个哲学家已经完成进餐

*/test(LEFT); /*测试左侧是否能进餐*/test(RIGHT); /*测试右侧是否能进餐

*/up(&mutex); /*退出临界区

*/}voidtest(i) /*i:某个哲学家的编号,从0到N-1

*/{if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING){state[i]=EATING;up(&s[i]); /*唤醒阻塞*/}}voidtakeforks(inti) /*i:如果第一个进入，通过test来表示自己的状态，表示可以进餐，如果他完成以后，通过test标识可以进餐的人的标号，在test函数里将阻塞的进程唤醒，即每个哲学家放下叉子之后，再去判断两侧的是否有阻塞，如果有，将它唤醒，之后，放开对临界区的控制，让两侧的哲学家进餐。函数只以philosopher为主函数，其余的均为被调用的函数。不是单独的进程。属于多个进程访问有限资源类问题。如果第一个进入，通过test来表示自己的状态，表示可以进餐2.3.2读者--写者问题问题描述：有一个许多进程共享的数据区，这个数据区可以是一个文件或者主存的一块空间，甚至可以是一组处理器寄存器，有一些只读取这个数据区的进程，和一些只向数据区中写数据的进程。此外，还需要满足：1.任意多的读进程可以同时读这个文件;2.一次只有一个写进程可以往文件中写；3.如果一个写进程正在往文件中写，禁止任何读进程读文件。数据库的访问模型2.3.2读者--写者问题typedefintsemaphore; /*根据需要自定义*/semaphoremutex=1; /*控制对’rc’的访问*/semaphoredb=1; /*控制对数据库的访问*/intrc=0; /*正在读或准备读的进程数*/voidreader(void){ while(TRUE){ /*无限循环*/ down(&mutex); /*禁止对’rc’的访问

*/ rc=rc+1; /*读者进入*/ if(rc==1)down(&db); /*如果是第一个读者...*/ up(&mutex); /*恢复允许访问’rc’*/ read_data_base(); /*访问数据*/ down(&mutex); /*禁止对’rc’的访问*/ rc=rc-1; /*读者离开*/ if(rc==0)up(&db);/*如果是最后一个读者...*/ up(&mutex); /*恢复允许访问’rc’*/ use_data_read(); /*非临界区*/}}typedefintsemaphore; /*根据voidwriter(void){ while(TRUE){ /*无限循环*/ think_up_data(); /*非临界区*/ down(&db); /*锁定临界区—数据库*/ write_data_base(); /*更新数据*/ up(&db); /*释放对临界区的控制—数据库*/}}局限性：只要有一个读者在，则就可以允许更多的读者进入，而此时如果有更新数据的需求，但也会被无限制的挂起。故此种解法为读者优先。voidwriter(void)局限性：只要有一个读者在写进程优先解决读者—写者问题问题描述：由于采用读者优先时。只要至少一个读进程在读，就为读保留了数据区的控制权，所以写进程可能会被饿死。故需要增加如下限制信息：为了保证一个写进程声明想写时，不允许新的读进程访问该数据区，需要增加额外的信号量和变量：**信号量rsem:当至少有一个写进程准备访问数据区时，用来禁止所有的读进程；**变量writecount:控制rsem的设置；**信号量y:控制writecount的更新。一个额外的信号量z，为了写进程优先，不要多余的读进程在rsem里等待，将多余的读进程放入z中，在那里排队。写进程优先解决读者—写者问题进程中的队列状态系统中只有读进程a)设置db；b)没有队列系统中只有写进程a)设置db和rsem；b)写进程在db上排队系统中既有读进程又有写进程,读优先系统中即有读进程又有写进程,写优先a)读进程设置db;b)写进程设置rsem；c)所有写进程在db上排队；d)一个读进程在rsem上排队；e)其他读进程在z上排队。a)写进程设置db;b)写进程设置rsem；c)写进程在db上排队；d)一个读进程在rsem上排队；e)其他读进程在z上排队。进程中的队列状态系统中只有读进程a)设置db；b)没有intreadcount,writecountSemaphoremutex=1,y=1,z=1,db=1,rsem=1;Voidreader(){while(TRUE){down(z);down(rsem);down(mutex);readcount++;if(readcount==1){down(db);}up(mutex);up(rsem);up(z);

READUNIT();down(mutex);intreadcount,writecountREAVoidwriter(){while(TRUE){down(y);writecount++;if(writecount==1){down(rsem);}/*阻塞新的读进程进入*/up(y);down(db);WRITEUNIT();