操作系统高分笔记PV操作.pdf
《操作系统高分笔记PV操作.pdf》由会员分享,可在线阅读,更多相关《操作系统高分笔记PV操作.pdf(27页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、天勤论坛:天勤论坛:天勤论坛天勤论坛专为计算机考研学子打造的专业交流平台专为计算机考研学子打造的专业交流平台期待你的加入!期待你的加入!此文档由天勤论坛总结此文档由天勤论坛总结转载请注明出处!转载请注明出处!天道酬勤,厚德载物!天道酬勤,厚德载物!天勤论坛:第二章第二章 进程管理进程管理大纲要求一、一、进程与线程进程与线程1.进程概念2.进程的状态与转换3.进程控制4.进程组织5.进程通信共享存储系统,消息传递系统,管道通信。6.线程概念与多线程模型二、进程同步二、进程同步1.进程同步的基本概念2.实现临界区互斥的基本方法软件实现方法;硬件实现方法。3.信号量4.管程5.经典同步问题生产者-消
2、费者问题,读者-写者问题,哲学家进餐问题。注:处理机调度以及死锁将在处理机调度与死锁处理机调度与死锁一章讲解。本章知识体系框架图天勤论坛:本章基础要点与核心考点一、核心考点:一、核心考点:1、()进程的定义及特征、进程与程序的异同、进程的状态及引起状态转换的典型原因。2、()临界区的定义及操作原则,进程同步与互斥,用信号量描述进程同步,进程通信。二、基础要点:二、基础要点:1、进程的并发执行是指若干进程在执行时间上是重叠的。2、进程是一个程序对某个数据集的一次运行活动。3、程序并发执行与顺序执行相比产生了一些新特性:间断性、失去封闭性、不可再现性。4、进程的基本特征是:动态性、并发性、独立性、
3、异步性和结构特征。5、程序的顺序执行通常是在单道程序的工作环境中,具有运行结果可再现的特点。6、进程的基本状态有执行、就绪和阻塞。7、进程是动态的概念,而程序是静态的概念。8、进程控制块的初始化工作包括初始化标识符信息、初始化处理机状态信息、初始化处理机控制信息。9、当进程执行的时间片用完时,进程由执行状态转变为就绪状态。10、进程从结构上讲,包括程序段、数据段和进程控制块(PCB)三部分。11、在操作系统中引入线程概念的主要目的是减少程序并发执行时所需付出的时空开销,提高程序执行的并发程度。12、在进程中,访问临界资源的代码段称为临界区。为保证进程互斥访问临界资源,应在进程的临界区之前设置进
4、入区,在临界区后设置退出区。13、访问临界资源应遵循的准则为:空闲让进、忙则等待、有限等待、让权等待。14、信号量的物理意义是当信号量值大于零时表示可用资源的数目:当信号量值小于零时,其绝对值为在该信号量上等待的进程个数。15、用 P、V 操作管理临界区时,任何一个进程在进入临界区之前应调用 P 操作,退出临界区时应调用 V 操作。知识点扩展与深度总结一、一、进程同步基本概念进程同步基本概念1两种形式的制约关系(课本 P38)(1)间接相互制约关系(互斥):这种制约关系源于多个同种进程需要互斥地共享某种系统资源(比如打印机),互斥是设置在同种进程之间以达到互斥地修改资源数的目的(比如在生产者-
5、消费者问题中,生产者与生产者之间需要互斥地访问缓冲池)。(2)直接相互制约关系(同步):这种制约主要源于进程间的合作,同步设置在不同进程之间以达到多种进程间的同步(比如在生产者-消费者问题中,只要缓冲池不满,生产者就可以生产,只要缓冲池不空,消费者就可以消费)。注:只要是同类进程即为互斥关系,不同类进程即为同步关系。2临界资源与临界区(课本 P39-40)天勤论坛:【易错点解析】这是两个比较容易混淆的概念,有人可能会理解为临界区就是临界资源所在地址,这样理解显然是错误的。简单点说,临界资源是一种系统资源,需要不同进程互斥访问,而临界区则是每个进程中访问临界资源的一段代码,是属于对应进程的,临界
6、区前后需要设置进入区和退出区以进行检查和恢复。3同步机制应遵循的规则(课本 P41)所有的同步机制都应遵循这四条准则(空闲让进,忙则等待,有限等待,让权等待),后面将在实现临界区互斥基本方法中举例说明。二、二、实现临界区互斥的基本方法实现临界区互斥的基本方法1软件方法:对临界区互斥访问技术的研究始于 20 世纪 60 年代,早期主要从软件方法上进行研究,下面我们介绍这些软件方法。它们有的是正确的,有的是不正确的。之所以介绍这些方法是为了说明用软件方法解决互斥和同步问题的困难和复杂性。例如有两个进程 P0和 P1,互斥地共享某个资源。P0和 P1是循环进程,它们执行一个无限循环程序,每次使用资源
7、一个有限的时间间隔。注注:临界区互斥的软件实现方法在历年来各学校的操作系统考题中出现过,通常作为选择题出现,用来考察同步机制的四个准则,统考的两年中在 2010 年真题第 27 题以选择题的形式考察过,因此在这里比较详细地介绍一下,帮助大家熟悉和理解四个准则以及同步机制的实现过程。算法算法 1 1:设置一个公用整形变量 turn,用来指示允许进入临界区的进程标识。若 turn为 0,则允许进程 P0进入临界区;否则循环检查该变量,直到 turn 变为本进程标识;在退出区,修改允许进入进程的标识 turn 为 1。进程 P1的算法与此类似。两个进程的程序结构如下:int turn=0;P0:Do
8、While(turn!=0);/当turn不为0时循环检查,直到为 0进入 P0的临界区代码 CS0;turn=1;进入 P0的其他代码;While(true)/循环执行这段代码P1:DoWhile(turn!=1);进入 P1的临界区代码 CS1;turn=0;进入 P1的其他代码;While(true)此方法可以保证互斥访问临界资源,但存在的问题是强制两个进程以交替次序进入临界区,很容易造成资源利用不充分。例如,当进程 P0退出临界区后将 turn 置为 1,以便允许进程 P1进入临界区,但如果进程 P1暂时并未要求访问该临界资源,而 P0又想再次访问临界资源,则它将无法进入临界区。可见,
9、此算法不能保证实现“空闲让进”准则。算法算法 2 2:设置标志数组 flag表示进程是否在临界区中执行,初值均为假。在每个进程访问该临界资源之前,先检查另一个进程是否在临界区中,若不在则修改本进程的临界区标志为真并进入临界区,在退出区修改本进程临界区标志为假。两进程的程序结构如下:enum booleanfalse,true;boolean flag2=false,false;天勤论坛:P0:DoWhile flag1;/flag1为真表示 P1在访问临界区,P0等待。flag0=true;进程 P0的临界区代码 CS0;flag0=false;进程 P0的其他代码;While(true)P1
10、:DoWhile flag0;/flag0为真表示 P0在访问临界区,P1等待。flag1=true;进程 P1的临界区代码 CS1;flag1=false;进程 P1的其他代码;While(true)此算法解决了“空闲让进”的问题,但又出现了新问题。即当两个进程都未进入临界区时,它们各自的访问标志都为 false,若此时刚好两个进程同时都想进入临界区,并且都发现对方的标志值为 false(当两进程交替执行了检查语句后,都满足 flag=false 的条件),于是两个进程同时进入了各自的临界区,这就违背了临界区的访问规则“忙则等待”。算法算法 3 3:本算法仍然设置标志数组 flag,但标志用
11、来表示进程是否希望进入临界区,在每个进程访问临界资源之前,先将自己的标志设置为真,表示进程希望进入临界区,然后检查另一个进程的标志。若另一个进程的标志为真,则进程等待;否则进入临界区。两进程的程序结构如下:enum booleanfalse,true;boolean flag2=false,false;P0:Doflag0=true;While flag1;/flag1为真表示 P1希望访问临界区,P0等待。进程 P0的临界区代码 CS0;flag0=false;进程 P0的其他代码;While(true)P1:Doflag1=true;While flag0;/flag0为真表示 P0希望访
12、问临界区,P1等待。进程 P1的临界区代码 CS1;flag1=false;进程 P1的其他代码;While(true)此算法可以有效地防止两进程同时进入临界区,但存在两个进程都进不了临界区的问题。即当两个进程同时想进入临界区时,它们分别将自己的标志位设置为 true,并且同时去检查对方的状态,发现对方也要进入临界区,于是对方互相谦让,结果都无法进入临界区。造成“死等”现象,违背了“有限等待”的准则。算法算法 4 4:本算法的思想是算法 3 和算法 1 的结合。标志数组 flag表示进程是否希望进入临界区或是否在临界区中执行。此外,还设置了一个 turn 变量,用于指示允许进入临界区的进程标识
13、。两进程的程序结构如下:天勤论坛:enum booleanfalse,true;boolean flag2=false,false;int turn;P0:Doflag0=true;turn=1;/此时 P0未进入临界区,仍然允许 P1进入临界区。While(flag1&turn=1);/flag1为真表示 P1希望访问临界区,turn 为 1 表示 P1可以进入临界区,因此 P0等待。进程 P0的临界区代码 CS0;flag0=false;/表示 P0退出访问临界区。进程 P0的其他代码;While(true)P1:Doflag1=true;turn=0;/此时 P1未进入临界区,仍然允许
14、P0进入临界区。While(flag0&turn=0);/flag0为真表示 P0希望访问临界区,turn 为 0 表示 P0可以进入临界区,因此 P1等待。进程 P1的临界区代码 CS1;flag1=false;/表示 P1退出访问临界区。进程 P1的其他代码;While(true)至此,算法 4 可以完全正常工作。我们从上面的软件实现方法中可以看出,对于两个进程间的互斥,最主要的问题就是标志的检查和修改不能作为一个整体来执行,因此容易导致无法保证互斥访问的问题。2硬件方法:注:注:硬件方法在考题中基本不出现,只需简单了解即可。完全利用软件方法实现进程互斥有很大的局限性,现在已经很少单独采用
15、软件方法。硬件方法的主要思想是用一条指令完成标志的检查和修改两个操作,因而保证了检查操作与修改操作不被打断;或通过中断屏蔽的方式来保证检查和修改作为一个整体执行。硬件方法主要有两种:一种是中断屏蔽,另一种是硬件指令。(在计算机组成原理中会详细讲解中断与指令,操作系统中很少涉及,因此不展开叙述了)三、信号量三、信号量1信号量的分类(课本 P41):整型信号量(引入 PV 操作,存在“忙等”问题)、记录型信号量(引入进程链表)、AND 型信号量(引入多种临界资源的“AND 分配”)、信号量集(对 AND 信号量机制的扩充,可以一次分配多种、多个临界资源)2信号量的应用(课本 P42):实现进程同步
16、与互斥,实现前趋关系。3注意:信号量的初值不能为负数。信号量的引入与发展课本上讲的比较清楚,从整型信号量发展到记录型、AND 型信号量以及之后的信号量集,之前信号量类型存在的问题以及之后信号量类型的引入都有比较详细的介绍,这里就不展开叙述。信号量的应用重点在于进程同步与互斥,这部分将在经典同步问题中详细介绍。四、管程(课本四、管程(课本 P51P51)天勤论坛:为了解决大量分散的同步操作导致管理困难和死锁,因此引入管程概念。管程定义了一个数据结构和能为并发进程所执行的一组操作,这组操作能同步进程和改变管程中的数据。注:注:管程在考题基本不涉及,因此不展开叙述,课本上的内容了解即可。五、经典同步
17、问题五、经典同步问题进程同步问题历来是操作系统考核的重点,基本以三种经典同步问题及其衍生问题为主要考察内容,下面将详细介绍这三种经典同步问题,并在后面的练习中提及一些衍生问题。1 1、生产者、生产者-消费者问题消费者问题生产者-消费者问题是最著名的进程同步问题。它描述了一组生产者向一组消费者提供产品,它们共享一个有界缓冲区,生产者向其中投入产品,消费者从中取走产品。这个问题是许多相互合作进程的一种抽象。例如,在输入时,输入进程是生产者,计算进程是消费者;在输出时,计算进程是生产者,打印进程是消费者。为解决这一问题,应当设置两个同步信号量,一个说明空缓冲区数目,用 empty表示,初值为有界缓冲
18、区大小 n;另一个说明满缓冲区数目(即产品数目),用 full 表示,初值为 0。此外,还需要设置一个互斥信号量 mutex,其初值为 1,以保证多个生产者或者多个消费者互斥访问缓冲池。生产者-消费者问题的同步程序结构描述如下:Semaphore full=0;/*满缓冲单元的数目*/Semaphore empty=n;/*空缓冲单元的数目*/Semaphore mutex=1;/*对有界缓冲区进行操作的互斥信号量*/Buffer array0,.,n-1;/*存放产品的缓冲区*/Integer in=0,out=0;/*缓冲池的指针,指示生产者和消费者进程存取位置*/Main()Cobegi
19、nProducer();Consumer();Coend;Producer()While(true)Produce an item put in nextp;P(empty);P(mutex);Buffer(in)=nextp;/*将产品放入缓冲池*/in=(in+1)mod n;/*指针后移*/V(mutex);V(full);Consumer()天勤论坛:While()P(full);P(mutex);nextc=buffer(out);out=(out+1)mod n;V(mutex);V(empty);Consumer the item in nextc;【易错点解析】1)P(full
20、)/P(empty)与 P(mutex)的顺序不可颠倒,必须先对资源信号量进行 P 操作,再对互斥信号量进行 P 操作,否则会导致死锁。(例如,此时缓冲区已满,而生产者先 P(mutex),取得缓冲池访问权,再 P(empty),此时由于缓冲池已满,empty=0,导致 P(empty)失败,生产者进程无法继续推进,始终掌握缓冲池访问权无法释放,因而消费者进程无法取出产品,导致死锁。)而 V(full)/V(empty)与 V(mutex)的顺序则没有要求,可以颠倒顺序。这个问题可以延伸到几乎所有 PV 操作题中,在有多个信号量同时存在的情况下,P 操作往往是不能颠倒顺序的,必须先对资源信号量
21、进行 P 操作,再对互斥信号量进行P 操作,这样可以保证在占有信号量访问权的时候保证有资源可以使用,不然会导致占用使用权而无资源可用的死等。2)关于 mutex 互斥信号量的设置是否必要的问题。在生产者和消费者都唯一的问题中,生产者与消费者是同步关系(见两种形式的制约关系,课本 P38),生产者与消费者之间使用 empty 与 full 两个资源信号量进行同步,一定满足“放完才能取”的条件,因此此时互斥是多余的,mutex 可以去掉。但在多生产者和多消费者的情况下,需要保证多个生产者或者多个消费者互斥地访问缓冲池,否则会导致出错。例如,两个生产者执行了 P(empty)操作,此时第一个生产者执
22、行 buffer(in):=nextp,这是第二个生产者也执行这条语句,由于第一个生产者没有来得及执行 in:=(in+1)mod n,即没有使指针后移,导致第二个生产者的数据覆盖掉了第一个生产者的数据而不是放在了第一个数据的下一个缓冲区,接下来两个进程分别执行一次后移指针操作,这样就导致了有一个空缓冲区(本来应当放置第二个数据的缓冲区)被当做已有数据缓冲区对待,导致出错。因此在多生产者或多消费者情况下,必须设置 mutex 互斥信号量,以保证对缓冲池的互斥访问。这里可记住一点:只要有多个同类进程,就一定需要互斥信号量,若同类进程只有一个,则记录型信号量即可完成进程同步。2 2、读者、读者-写
23、者问题写者问题有一个许多进程共享的数据区,这个数据区可以是一个文件或者主存的一块空间;有一些只读取这个数据区的进程(读者)和一些只往数据区写数据的进程(写者),此外还需要满足以下条件:(1)任意多个读者可以同时读这个文件;天勤论坛:(2)一次只有一个写者可以往文件中写;(3)如果一个写者正在进行操作,禁止任何读进程读文件。我们需要分两种情况实现该问题:读优先:一个读者试图进行读操作时,如果这时正有其他读者在进行读操作,他可直接开始读操作,而不需要等待。写优先:一个读者试图进行读操作时,如果有其他写者在等待进行写操作或正在进行写操作,他要等待该写者完成写操作后才开始读操作。读者优先算法:课本 P
24、49 中给出的算法即为读者优先算法。写者优先算法:1)多个读者可以同时进行读2)写者必须互斥(只允许一个写者写,也不能读者写者同时进行)3)写者优先于读者(一旦有写者,则后续读者须等待,唤醒时优先考虑写者)如果读者数是固定的,我们可采用下面的算法:rwmutex:用于写者与其他读者/写者互斥的访问共享数据rmutex:该信号量初始值设为 10,表示最多允许 10 个读者同时进行读操作Semaphorerwmutex=1,rmutex=10;procedure reader_i()/第 i 个读者进程(i=1,2,)P(rwmutex);P(rmutex);V(rwmutex);/释放读写互斥信
25、号量,允许其它读、写进程访问读数据;V(rmutex);procedure Writer_j/第 j 个写者进程(j=1,2,)P(rwmutex);for(i=1;i=10;i+)P(rmutex);/禁止新读者,并等待已进入的读者退出写更新;for(i=1;i=10;i+)V(rmutex);/恢复 rmutex 值为 10V(rwmutex);3 3、哲学家进餐问题、哲学家进餐问题5 个不讲卫生的哲学家围绕一张圆桌而坐,桌子上放着 5 支筷子,每两个哲学家之间放一支;哲学家的动作包括思考和进餐,进餐时需要同时拿起他左边和右边的两支筷子,思考时则同时将两支筷子放回原处。解法一:semaph
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统 高分 笔记 PV 操作
限制150内