《计算机操作系统》课件第4章 (2).ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《《计算机操作系统》课件第4章 (2).ppt》由用户(momomo)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机操作系统 计算机操作系统课件第4章 2 计算机 操作系统 课件
- 资源描述:
-
1、第 4 章进程同步与通信4.1 与时间有关的错误4.2 进程的互斥4.3 信号量与PV操作4.4 进程同步4.5 进程通信4.6 进程同步实现举例4.7 进程通信的实现举例习题第 4 章进程同步与通信在采用多道程序设计技术的系统中,若干个作业可以同时执行,而每一个作业又需要由多个进程的协作来完成。因此,系统中会同时存在许多进程来竞争处理机。另外,在一个进程运行过程中,由于自身或外界的原因,该进程可能被中断,且断点是不固定的。一个进程被中断后,哪个进程可以运行,被中断的进程什么时候再去占用处理机,这些问题是与进程调度策略有关的,所以,进程的执行速度是不能由自己来控制的。4.1 与时间有关的错误与
2、时间有关的错误第 4 章进程同步与通信若系统中存在一组进程的执行在时间上是重叠的,就称该组进程具有并发性,这组进程就被称为“并发进程”。并发进程相互之间可能是无关的,也可能是有交往的。如果一个进程的执行不影响其他进程的执行,且与其他进程的进展情况无关,即它们是各自独立的,则称这些并发进程相互之间是无关的。如果一个进程的执行可能影响其他进程的执行结果,则称这些并发进程相互之间是有交往的。对于有交往的并发进程来说,可能有若干并发进程同时使用共享资源,即一个进程一次使用未结束,另一进程就开始使用,形成交替使用共享资源。如果对这种情况不加控制,在共享资源时就会出错。第 4 章进程同步与通信其中观察者进
3、程能识别卡车,并对通过的卡车计数,报告者进程定时将观察者的计数值打印输出,每次打印后把计数值清“0”。两个进程的并发执行可完成对每小时中卡车流量的统计,两个进程的功能描述如下:main()int count=0;/*用于计数*/cobegin Process Observer while(1)observe a lorry;count=count+1;第 4 章进程同步与通信 Process Reporter while(1)printf(%d,count);count=0;coend 第 4 章进程同步与通信在cobegin 和coend之间的进程为可并发执行的进程。观察者进程和报告者进程并
4、发执行时可能有如下两种情况:(1)报告者进程执行时无卡车通过。这种情况下,报告者进程把上一小时通过的卡车数打印输出后将计数器清“0”,完成了一次任务后,当有卡车通过时,观察者进程重新开始对一个新时间段内的流量进行统计。第 4 章进程同步与通信(2)报告者进程执行时有卡车通过。当报告者进程工作时,启动了打印机,在等待打印机打印输出时恰好有一辆卡车通过,这时,观察者进程工作将计数器count的值又增加“1”。报告者进程在打印完成后继续执行count=0,将计数器上新增加的“1”也清除了。如果在打印输出期间有多个卡车通过,观察者进程虽然将它们记录到计数器上,但都因报告者进程执行count=0而把计数
5、值丢失了,导致了统计结果的错误。第 4 章进程同步与通信可见,由于并发进程执行的随机性,其中一个进程对另一个进程的影响是不可预知的。关键是它们都涉及到共享变量count,当在不同时刻交替地修改了count的值就会造成结果的不正确。导致不正确的原因与进程占用处理机的时间、执行的速度以及外界的影响有关。这些因素都与时间有关,所以称为“与时间有关的错误”。第 4 章进程同步与通信4.2.1 临界资源临界资源有交往的并发进程执行时出现与时间有关的错误,其根本原因是对共享资源的使用不受限制,当进程交叉使用了共享资源就造成了错误。例如,进程A,B共享一台打印机,若让它们任意使用,那么可能发生的情况是:两个
6、进程的输出结果将交织在一起,很难区分。解决这一问题的办法是:进程A要使用打印机时应先提出申请,一旦系统把资源分配给它,就一直为它所独占。这时,即使进程B要使用打印机,也必须等待,直到进程A用完并释放后,系统才把打印机分配给进程B使用。4.2 进进程程的的互互斥斥第 4 章进程同步与通信由此可见,虽然系统中可同时存在许多进程,它们共享着各种资源,然而有许多资源一次只能为一个进程使用。通常把一次仅允许一个进程使用的资源称为临界资源。许多物理设备,如输入机、打印机、磁带机等都具有这种性质。除了物理设备外,还有一些软件资源,如变量、数据、表格、队列等也都具有这一特点。第 4 章进程同步与通信允许若干进
7、程均能访问和修改的存储单元称为公共变量。并发进程对公共变量进行访问和修改时,必须作某种限制,否则就会产生与时间有关的错误。例如,在一个机票预订系统中,某一机座的订购情况由一个确定的内存单元的内容表示,假设把若干个订票处看成为若干个访问这一内存单元的进程。如果一次有两个或n个进程同时存取该变量,那么就有可能使两家或几家订票处同时帮顾客订到相同的机座。第 4 章进程同步与通信所以,当两个(或n个)进程可能异步地改变公共数据区内容时,必须防止两个(或n个)进程同时存取或改变数据。如果两个进程共用一个变量,则它们必须顺序地使用,即一个进程对公共变量操作完毕后,另一个进程才能去访问和修改这一变量。综上所
8、述,对公共变量这样的临界资源的共享有这样的限制:共享的各方不能同时读写同一数据区,只有当一方读写完成后,另一方才能读写。到底哪一方先读写,要根据问题的性质和设计人员的意图而定。第 4 章进程同步与通信4.2.2 临界区临界区在每个进程中,访问临界资源的那段程序能够从概念上分离出来,因而称为临界区或临界段。它就是进程中对公共变量进行访问与修改的程序段,称为相对于该公共变量的临界区。例如,前面提到的自动计数系统中,观察者进程的临界区是“count=count+1”,报告者进程的临界区是“printf(%d,count);count=0;”。第 4 章进程同步与通信如果有进程在相关临界区执行,不让另
9、一个进程进入相关的临界区执行,就不会形成多个进程对共享变量交叉访问,于是就可以避免出现与时间有关的错误。在观察者和报告者进程并发执行时,当报告者进程启动打印机后,在执行count=0之前,虽然观察者进程发现有卡车通过,但应该限制观察者进程进入相关临界区(即暂不执行count=count+1),直到报告者进程执行了count=0退出临界区,观察者进程才可以执行,否则就可能在观察者进程执行完count=count+1后,报告者进程执行了count=0,而导致数据丢失。当报告者进程退出临界区后,观察者进程再进入临界区执行,第 4 章进程同步与通信这样就不会交替地修改count的值,观察到的卡车数被统
10、计在下一个时间段内,不会出现数据丢失。对若干进程共享某一变量的相关临界区的管理应满足如下三个要求:(1)每次最多有一个进程处于临界区。(2)任何一个进入临界区执行的进程必须在有限的时间内退出临界区。(3)当有若干进程欲进入它的临界区时,应在有限时间内使进程进入临界区。需要注意的一点是,临界区是对某一资源而言的,对于不同资源的临界区,它们之间是不相交的,不必互斥执行。第 4 章进程同步与通信4.2.3 互斥的概念互斥的概念在操作系统中,当一个进程进入临界区使用临界资源时,另一个进程必须等待,当占用临界资源的进程退出临界区后,另一进程才被允许去访问此临界资源。进程之间的这种相互制约关系被称为互斥。
11、下面几节将列出处理互斥问题的几种方法。第 4 章进程同步与通信4.2.4 上锁和解锁操作上锁和解锁操作在大多数同步机构中,必须用一个标志来代表某一资源的状态。比如,标志为“0”表示未被使用,标志为“1”表示已被使用。这一标志经常被称为锁或信号量。对于每一共享数据块或设备都要有一个单位的锁位。常用的锁位值为“0”表示资源可用,为“1”表示资源已被占用。第 4 章进程同步与通信进程在使用某一共享资源之前必须完成下列操作:(1)考察锁位的值。(2)如果原来的值为0,将锁位置1。(3)如果原来的值为1,则返回第一步再考察。系统提供在一个锁位W上的两个原语操作:上锁原语LOCK(W)和开锁原语UNLOC
12、K(W),其功能可描述如下:LOCK(W)UNLOCK(W)L:if W=1 then GOTO LW=0;else W=1;第 4 章进程同步与通信4.2.5 利用上锁和解锁操作实现进程互斥利用上锁和解锁操作实现进程互斥使用上锁原语和开锁原语可以解决并发进程的互斥问题,任何欲进入临界区的进程,必须先执行上锁原语,若上锁原语顺利通过,则进程可进入临界区,当完成对临界资源的访问后再执行开锁原语,释放该临界资源。第 4 章进程同步与通信对两个进程关于临界资源的操作可描述为:进程 P1 进程 P2 LOCK(W);LOCK(W);CS1 CS2 UNLOCK(W);UNLOCK(W);其中,CS1和
13、 CS2代表两个进程所对应的临界区。第 4 章进程同步与通信4.3.1 信号量的概念信号量的概念信号量是一个确切的二元组(S,Q),S是一个具有非负初值的整型变量,Q是一个初始状态为空的队列。整型变量S代表资源的实体,操作系统利用它的状态对并发进程、共享资源进行管理。信号量的值只能通过P,V操作来改变,其可能的取值范围是负整数、零、正整数。信号量是操作系统中实现进程间同步和通信的常用工具。一个信号量的建立必须经过说明,即应该准确说明S的意义和初值。每个信号量都有相应的一个队列,在建立信号量时,队列为空。4.3 信号量和信号量和PV操作操作第 4 章进程同步与通信4.3.2 PV操作操作信号量的
14、数值仅能由P,V操作加以改变。对信号量的P操作记为P(S),对信号量的V操作记为V(S),它们都是不可分割的原语操作。它们的主要操作过程如下:1.P操作过程操作过程(1)S值减1。(2)若相减结果大于或等于0,则进程继续执行。(3)若相减结果小于0,则该进程被阻塞,并将它插入到该信号量的等待队列中,然后转进程调度。第 4 章进程同步与通信2.V操作过程操作过程(1)S值加1。(2)若相加结果大于0,则进程继续执行。(3)若相加结果小于或等于0,则从该信号量的等待队列中移出一个进程,解除它的等待状态,然后返回本进程继续执行。第 4 章进程同步与通信4.3.3 利用信号量实现进程互斥利用信号量实现
15、进程互斥为了实现对相关临界区的管理要求,先分析一下P,V操作的两个过程,如果把信号量S的初值定为“1”,此时有若干个进程都要调用P(S),则只有第一个调用P(S)的进程不会处于等待而可以继续执行下去。P(S)被调用一次后S的值变为“0”,以后其他进程调用P(S)时,在执行S=S-1后,S的值总是小于“0”,于是这些进程均被置成等待信号量S的状态。直到有进程调用一次V(S),将信号量S加“1”,若其结果不大于“0”,说明有进程正处于等待信号量S的状态,这时V(S)将释放其中的一个进程,每调用一次V(S)就可释放一个等待信号量S的进程。第 4 章进程同步与通信因此,用PV操作能够实现对相关临界区的
16、管理要求。只要用一个信号量与一组涉及共享变量的相关临界区联系起来,信号量的初值定为“1”,任何一个进程要进入临界区前先调用P操作,执行完临界区的操作后,退出临界区时调用V操作。第 4 章进程同步与通信例如,设两个并发进程A和B,具有相对于变量N的临界段CSA和CSB,用信号量实现它们的互斥情况可描述如下:进程 A 进程 B P(S);P(S);CSA;CSB;V(S);V(S)第 4 章进程同步与通信对于两个并发进程,互斥信号量的值仅取1、0、-1三个值。若S=1,表示没有进程进入临界区;若S=0,表示有一个进程进入临界区;若S=-1,表示一个进程进入临界区,另一个进程等待进入。下面请大家思考
17、这样一个问题,如果N个并发进程共用一个公共变量Q,用信号量和PV操作实现这N个进程的互斥,信号量的取值范围如何呢?第 4 章进程同步与通信首先要把信号量的初值定为“1”,当N个进程中有一个进程进入临界区时,由于调用了P(S),则信号量的值将变为“0”。其余N-1个进程也要调用P(S),而且第一个进程没有退出临界区,导致了N-1个进程均被置成等待信号量S的状态,当第二个进程置成等待状态时,信号量的值为-2,依次类推,-3、-4,直到信号量的值为-(N-1),此时N-1个进程都入了等待队列。所以,信号量的取值范围为-(N-1),1。第 4 章进程同步与通信前面曾讨论过交通路口的自动计数系统中出现的
18、与时间有关的错误,现在可以用PV操作来解决这个问题,具体过程描述如下:main()int count=0;int s=1;/*互斥信号量*/cobegin Process Observer 第 4 章进程同步与通信 while(1)observe a lorry;P(S);count=count+1;V(S);Process Reporter 第 4 章进程同步与通信 while(1)P(S);printf(%d,count);count=0;V(S);coend 第 4 章进程同步与通信4.3.4 哲学家进餐问题哲学家进餐问题哲学家问题是描述有5个哲学家,它们的生活方式是交替地进行思考和进餐
19、。哲学家们共用一张圆桌,分别坐在周围的5把椅子上。在圆桌上有5个碗和5支筷子,平时一个哲学家进行思考,饥饿时便试图取用其左右最靠近他的筷子,只有在他拿到两支筷子时才能进餐。进餐毕,放下筷子又继续思考。请用信号量和PV操作说明这五位哲学家的同步过程。第 4 章进程同步与通信经过分析可以知道,相邻的两个哲学家是不能同时拿起它们中间的筷子的,在使用这个筷子的时候,哲学家们必须互斥使用。由于每个哲学家之间的筷子都不能同时拿起,因此,需要设置5个互斥信号量,下面是具体的实现过程:main()int chopstick1=1;int chopstick2=1;int chopstick3=1;int ch
20、opstick4=1;int chopstick5=1;cobegin 第 4 章进程同步与通信 Process Ph1 while(1)P(chopstick1);进餐;V(chopstick2);讨论问题;第 4 章进程同步与通信 Process Ph2 while(1)P(chopstick2);进餐;V(chopstick3);讨论问题;第 4 章进程同步与通信 Process Ph3 while(1)P(chopstick3);进餐;V(chopstick4);讨论问题;第 4 章进程同步与通信第 4 章进程同步与通信 Process Ph5 while(1)P(chopstick5
21、);进餐;V(chopstick1);讨论问题;coend 第 4 章进程同步与通信4.3.5 读者写者问题读者写者问题在计算机系统中,有些文件是可以供若干进程共享的。假定有某个共享文件F,系统允许进程对文件F读或者修改,但规定:(1)多个进程可以同时读文件F。(2)任一个进程在对文件F进行修改时不允许其他进程对文件进行读或者修改。(3)当有进程在读文件时不允许任何进程去修改文件。第 4 章进程同步与通信在这个问题中,可以把想读文件的进程称为读者,把想修改文件的进程称为写者。当有多个读者和写者都要对文件读或写时,按规定每次只允许一个进程执行写操作且有进程执行写时不允许进程去读文件。显然,写者和
22、写者之间要互斥,写者和读者之间也要互斥,但多个读者之间可同时读。下面用PV操作实现“读者和写者”问题。第 4 章进程同步与通信main()int rc=0;/*记录读者的个数*/int s=1;/*互斥信号量,用于读者和写者之间的互斥*/int sr=1;/*互斥信号量,用于对访问公共变量 rc 的互斥*/cobegin Process Readeri(i=1,2,)第 4 章进程同步与通信 while(1)P(sr);if(rc=1)then P(S);rc=rc+1;V(sr);read file F;P(sr);rc=rc-1;if(rc=0)then V(S);V(sr);第 4 章进
23、程同步与通信 Process Writerj(j=1,2,)while(1)P(S);write file F;V(S);coend 第 4 章进程同步与通信4.4.1 同步的概念同步的概念利用信号量可以解决进程的互斥问题,互斥主要解决并发进程对临界区的使用问题。这种基于临界区控制的交互作用是比较简单的,只要各进程对临界区的执行时间互斥,每个进程就可忽略其他进程的存在和作用。4.4 进进 程程 同同 步步第 4 章进程同步与通信在计算机系统中,还会存在一组相互合作的进程实现一个共同的任务的情况。在这组相互合作的并发进程中,每一个进程都以各自独立、不可预知的速度向前推进,它们之间要协作,就要交换
展开阅读全文