您好,欢迎访问三七文档
当前位置:首页 > 电子/通信 > 综合/其它 > Windows操作系统-处理机管理(中)解析
1•进程和进程控制•线程•进程互斥和同步•死锁问题•进程间通信•处理器调度第三章处理机管理(中)2进程互斥和同步•问题的提出•互斥算法•信号量(semaphore)•经典进程同步问题•管程(monitor)•Windows的进程互斥和同步进程互斥和同步3进程间临界资源访问冲突共享变量的修改冲突操作顺序冲突临界资源:计算机系统中的硬件或软件(如外设、共享代码段、共享数据结构)资源,各个进程在对其进行访问时(关键是进行写入或修改),必须互斥地进行并非所有共享资源都是临界资源,如只读数据可以同时访问在多道程序环境中,进程之间存在相互制约的关系,这种制约关系主要是由对共享资源的竞争使用而引起的。进程互斥和同步问题的提出4共享变量的修改冲突进程互斥和同步临界资源问题的提出一个飞机订票系统,两个终端,运行T1、T2进程T1:T2:......Read(x);Read(x);ifx=1thenifx=1thenx:=x-1;x:=x-1;write(x);write(x);......53个进程:get,process和print进程互斥和同步操作顺序冲突临界资源getprocessprint问题的提出Buf1Buf2磁带打印机6临界资源的访问过程进程互斥和同步entrysectionexitsectioncriticalsectionremaindersection临界区entrysectionexitsectioncriticalsectionremaindersection临界区为了保证临界资源的正确访问,必须采取一定的协调措施临界区(criticalsection):进程中访问临界资源的一段代码。进入区(entrysection):在进入临界区之前,检查可否进入临界区的一段代码。如果可以进入临界区,通常设置相应“正在访问临界区”标志。退出区(exitsection):用于将正在访问临界区标志清除。剩余区(remaindersection):代码中的其余部分。问题的提出7同步机制应遵循的准则①空闲则入:当没有进程处于临界区时,若有一个进程要求进入临界区,则应该允许;②无空等待:已有进程处于其临界区,其他要求进入临界区的进程必须;③有限等待:等待进入临界区的进程应该在有限的时间内得到满足;④让权等待:不能进入临界区的进程,应释放CPU(如转换到阻塞状态)进程互斥和同步目的:避免死锁和饥饿死锁指多个进程互不相让,都得不到足够的资源;饥饿指某一个进程一直得不到资源问题的提出8进程互斥和同步互斥算法——基于进程间平等协商的互斥算法解决进程互斥的方法:基于进程间平等协商的互斥方法软件方法硬件方法由操作系统协调互斥问题的方法9进程互斥的软件方法有两个进程Pi,Pj,其中的Pi算法1:单标志while(turn!=i);criticalsectionturn=j;remaindersection设立一个公用整型变量turn:描述允许进入临界区的进程标识在进入区循环检查是否允许本进程进入:turn为i时,进程Pi可进入;在退出区修改允许进入进程标识:进程Pi退出时,改turn为进程Pj的标识j;缺点:强制轮流进入临界区,没有考虑进程的实际需要。容易造成资源利用不充分:在Pi出让临界区之后,Pj使用临界区之前,Pi不可能再次使用临界区;进程互斥和同步互斥算法10算法2:双标志、先检查设立一个标志数组flag[]:描述进程是否在临界区,初值均为FALSE。先检查,后修改:在进入区检查另一个进程是否在临界区,不在时修改本进程在临界区的标志;在退出区修改本进程在临界区的标志;优点:不用交替进入,可连续使用;缺点:Pi和Pj可能同时进入临界区。while(flag[j]);aflag[i]=TRUE;bcriticalsectionflag[i]=FALSE;remaindersection进程互斥和同步进程互斥的软件方法互斥算法11算法3:双标志、后检查类似于算法2,与互斥算法2的区别在于先修改后检查。可防止两个进程同时进入临界区。flag[i]=TRUE;bwhile(flag[j]);acriticalsectionflag[i]=FALSE;remaindersection缺点:Pi和Pj可能都进入不了临界区。进程互斥和同步进程互斥的软件方法互斥算法12算法4:先修改、后检查、后修改者等待结合算法1和算法3,满足空闲则入和无空等待要求turn=j;描述可进入的进程(同时修改标志时)在进入区先修改后检查,并检查并发修改的先后:检查对方flag,如果不在临界区则自己进入--空闲则入否则再检查turn:保存的是较晚的一次赋值,则较晚的进程等待,较早的进程进入--先到先入,后到等待flag[i]=TRUE;turn=j;while(flag[j]&&turn==j);criticalsectionflag[i]=FALSE;remaindersection进程互斥和同步进程互斥的软件方法互斥算法13信号量(semaphore)•信号量和P、V原语•信号量集前面的互斥算法是进程间的一种平等协商机制,不能满足进程同步机制准则的全部要求。另一种进程互斥的解决方法是引如一个地位高于进程的管理者来解决临界资源的使用问题。操作系统可从进程管理者的角度来处理互斥的问题,信号量就是OS提供的管理临界资源的有效手段。信号量代表可用资源实体的数量。进程互斥和同步14信号量和P、V原语1965年,由荷兰学者Dijkstra提出(P、V分别是荷兰语的proberen=test和verhogen=increment的首字母),是一种卓有成效的进程同步机制。每个信号量s包含一个整数值s.count(计数)和一个进程等待队列s.queue,其中是阻塞在该信号量的各个进程的标识信号量只能通过初始化和两个标准的原语来访问——作为OS核心代码执行,不受进程调度的打断初始化指定一个非负整数值,表示空闲资源总数(又称为“资源信号量”)——若为非负值表示当前的空闲资源数,若为负值其绝对值表示当前等待临界区的进程数进程互斥和同步信号量15P原语P(s){--s.count;//表示申请一个资源;if(s.count0)//表示没有空闲资源;{调用进程进入等待队列s.queue;阻塞调用进程;}}进程互斥和同步信号量16V原语V(s){++s.count;//表示释放一个资源;if(s.count=0)//表示有进程处于阻塞状态;{从等待队列s.queue中取出一个进程P;进程P进入就绪队列;}}进程互斥和同步信号量17利用信号量实现互斥为临界资源设置一个互斥信号量mutex(MUTualExclusion),其初值为1;在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语:遗漏P原语则不能保证互斥访问,遗漏V原语则不能在使用临界资源之后将其释放(给其他等待的进程);P、V原语不能次序错误、重复或遗漏V(mutex);criticalsectionremaindersectionP(mutex);进程互斥和同步信号量18利用信号量可以实现进程间的同步前趋关系:并发执行的进程P1和P2中,分别有代码C1和C2,要求C1在C2开始前完成;为每个前趋关系设置一个互斥信号量S12,其初值为0P2P1C1C2V(S12);P(S12);进程互斥和同步信号量19经典进程同步问题1.生产者-消费者问题(theproducer-consumerproblem)问题描述:若干进程通过有限的共享缓冲区交换数据。其中,生产者进程不断写入,而消费者进程不断读出;共享缓冲区共有n个;任何时刻只能有一个进程可对共享缓冲区进行操作。共享缓冲区生产指针消费指针Producer1Producer2...ProducerMConsumer1Consumer2...ConsumerN满空指针移动方向进程互斥和同步20采用信号量机制:full是“满”数目,初值为0,empty是“空”数目,初值为n。full和empty存在关系:full+empty==nmutex用于访问缓冲区时的互斥,初值是1每个进程中各个P操作的次序是重要的:先检查资源数目,再检查是否互斥――否则可能死锁(为什么?)ConsumerProducerP(empty);P(mutex);//进入区oneunit--buffer;V(mutex);V(full);//退出区P(full);P(mutex);//进入区oneunit--buffer;V(mutex);V(empty);//退出区进程互斥和同步经典进程同步问题1.生产者-消费者问题(theproducer-consumerproblem)212.读者-写者问题(thereaders-writersproblem)问题描述:对共享资源的读写操作,任一时刻“写者”最多只允许一个,而“读者”则允许多个“读-写”互斥,“写-写”互斥,读-读允许进程互斥和同步经典进程同步问题22采用信号量机制:Wmutex表示允许写,初值是1。公共变量Rcount表示“正在读”的进程数,初值是0;Rmutex表示对Rcount的互斥操作,初值是1。进程互斥和同步2.读者-写者问题经典进程同步问题P(Rmutex);if(Rcount==0)P(Wmutex);++Rcount;V(Rmutex);read;P(Rmutex);--Rcount;if(Rcount==0)V(Wmutex);V(Rmutex);ReaderP(Wmutex);write;V(Wmutex);Writer23信号量同步的缺点同步操作分散:信号量机制中,同步操作分散在各个进程中,使用不当就可能导致各进程死锁(如P、V操作的次序错误、重复或遗漏)易读性差:要了解对于一组共享变量及信号量的操作是否正确,必须通读整个系统中并发执行的各个程序;不利于修改和维护:各模块的独立性差,任一组变量或一段代码的修改都可能影响全局;正确性难以保证:操作系统或并发程序通常很大,很难保证这样一个复杂的系统没有逻辑错误;进程互斥和同步管程用信号量可实现进程间的同步,但由于信号量的控制分布在整个程序中,其正确性分析很困难。24管程的引入1973年,由Hoare和Hanson提出管程的基本思想是把信号量及其操作原语封装在一个对象内部。即:将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。管程的定义:管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。引入管程可提高代码的可读性,便于修改和维护,正确性易于保证。进程互斥和同步管程25管程的主要特性模块化:一个管程是一个基本程序单位,可以单独编译;抽象数据类型:管程是一种特殊的数据类型,其中不仅有数据,而且有对数据进行操作的代码信息封装:管程是半透明的,进程可调用管程中实现了某些功能(函数),至于这些功能是怎样实现的,在其外部则是不可见的;进程互斥和同步管程26管程作为一个模块,它的结构定义如下:monitor_name=MONITOR;共享变量说明;define本管程内部定义、外部可调用的函数名表;use本管程外部定义、内部可调用的函数名表;内部定义的函数说明和函数体{共享变量初始化语句;}进程互斥和同步管程27进程互斥和同步管程bulletin=MONITOR;r,w:condition;//r控制读者使用黑板,w控制写者;writing:boolean;//当前是否写者使用黑板read_account:integer;definestart_read,end_read,start_write,end_write;usemonitor.wait,monitor.signal;procedurestart_read();{if(writing)monitor.wait(r);read_account++;monitor.signal(r);}procedureend_read();{read_account--;if(read_a
本文标题:Windows操作系统-处理机管理(中)解析
链接地址:https://www.777doc.com/doc-5002154 .html