《操作系统：第2章进程管理2》由会员分享，可在线阅读，更多相关《操作系统：第2章进程管理2（59页珍藏版）》请在金锄头文库上搜索。
1、第二章进 程 管 理 2.3.1进程同步的基本概念进程同步的基本概念2.3进进 程程 同同 步步 进程同步的主要任务是对多个相关进程在执行次序上进行进程同步的主要任务是对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效地共享资源和相互合协调，以使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。作，从而使程序的执行具有可再现性。第二章进 程 管 理 例：X = fun1(y)*fun2(Z)X = fun1(y)*fun2(Z)计算fun1(y)进程p2算完fun2(Z)?取用P2计算结果计算fun2(Z)设置计算完成标志终 止YN进程P1进程P2
2、两个协同工作进程的同步第二章进 程 管 理 P1P2P3PmC1C2C3Cn生产者进程P(Sn)P(S)缓冲区 产品V(S)V(S0)消费者进程P(S0)P(S)取产品V(S)V(Sn)S = 1;So=0;Sn=n;第二章进 程 管 理 例：例：生产者生产者-消费者消费者(producer-consumer)问题是一个著名的进程同问题是一个著名的进程同步问题。步问题。它描述的是：有一群生产者进程在生产产品，并将这些产品它描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间
3、设置了一个具有并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。程可从一个缓冲区中取走产品去消费。第二章进 程 管 理 尽管所有的生产者进程和消费者进程都是以异步方式运尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品且空缓冲区去取产品，也不允许生产者进程向一个已装满产品且尚未被取
4、走的缓冲区中投放产品。尚未被取走的缓冲区中投放产品。 同时所有的消费者进程和生产者进程不可以同时访问同时所有的消费者进程和生产者进程不可以同时访问“缓缓冲池冲池”这个共享资源，也就是进程间应通过互斥方式来共享资这个共享资源，也就是进程间应通过互斥方式来共享资源。源。第二章进 程 管 理 1 1并发进程之间的制约关系并发进程之间的制约关系在在多多道道程程序序环环境境下下，当当程程序序并并发发执执行行时时，由由于于资资源源共共享享和和进进程程合合作作，使使同同处处于于一一个个系系统统中中的的诸诸进进程程之之间间可可能能存存在在着着以下两种形式的制约关系。以下两种形式的制约关系。(1) (1) 间接
5、相互制约关系。同处于一个系统中的进程，通间接相互制约关系。同处于一个系统中的进程，通常都共享着某种系统资源，如共享常都共享着某种系统资源，如共享CPUCPU、共享、共享I/OI/O设备等。所设备等。所谓间接相互制约即源于这种资源共享。谓间接相互制约即源于这种资源共享。多个进程不能同时使多个进程不能同时使用同一个资源。应采取互斥的方式实现资源的共享。用同一个资源。应采取互斥的方式实现资源的共享。 (2) (2) 直接相互制约关系。这种制约主要源于进程间的合直接相互制约关系。这种制约主要源于进程间的合作。如生产者作。如生产者- -消费者问题、司机售票员问题。消费者问题、司机售票员问题。应采取同步的
6、应采取同步的方式来协调执行的次序。方式来协调执行的次序。第二章进 程 管 理 2. 2. 临界资源临界资源定义：定义： 临界资源：临界资源：一次只允许一个进程使用的资源，如打印机、一次只允许一个进程使用的资源，如打印机、公共变量等。公共变量等。许多硬件资源如打印机、磁带机等，都属于临界资源许多硬件资源如打印机、磁带机等，都属于临界资源(Critical Resource)，诸进程间应采取互斥方式，实现对这种，诸进程间应采取互斥方式，实现对这种资源的共享。资源的共享。第二章进 程 管 理 *.in公用缓冲池中有n个缓冲区produceriproducer: repeat produce an i
7、tem in nextp；while counter=n do no-op；bufferin:=nextp；in:=(in+1) mod n；counter:=counter+1；untilfalse；consumer: repeatwhile counter=0 do no-op；nextc:=bufferout；out:=(out+1) mod n；counter:=counter-1；consume the item in nextc； until false；consumerj生产者、消费者例生产者、消费者例第二章进 程 管 理 虽然上面的生产者程序和消费者程序在分别看时都是正确虽然上
8、面的生产者程序和消费者程序在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时就会出现差错，执行时就会出现差错，问题就在于这两个进程共享变量问题就在于这两个进程共享变量counter。生产者对它做加生产者对它做加1操作，消费者对它做减操作，消费者对它做减1操作，这操作，这两个操作在用机器语言实现时，两个操作在用机器语言实现时， 常可用下面的形式描述：常可用下面的形式描述：register1:=counter；register2:=counter；register1:=register1+1；register2:=reg
9、ister2-1；counter:=register1；counter:=register2； 解决的办法就是把共享变量共享变量counter作为临界资源来处理，也就是让生产者进程和消费者进程互斥地访问变量counter。第二章进 程 管 理 例：register1:=counter；register1:=register1+1；counter:=register1；临界区临界区进 程 A进 程 Bregister2:=counter；register2:=register2+1；counter:=register2；第二章进 程 管 理 3临界区临界区(CS，Critical Section
10、)临界区（段）定义：临界区（段）定义： 在每个进程中访问临界资源的那段代码称为临界区。在每个进程中访问临界资源的那段代码称为临界区。1.若能保证诸进程互斥地进入自己的临界区，便可实现诸进若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。程对临界资源的互斥访问。2.为此，每个进程在进入临界区之前，应先对欲访问的临界为此，每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问。资源进行检查，看它是否正被访问。3.因此，必须在临界区前面增加一段用于进行上述检查的代因此，必须在临界区前面增加一段用于进行上述检查的代码，把这段代码称为进入区码，把这段代码称为进
11、入区(entry section)。相应地，在临。相应地，在临界区后面也要加上一段称为退出区界区后面也要加上一段称为退出区(exit section)的代码，的代码，用于将临界区正被访问的标志恢复为未被访问的标志。用于将临界区正被访问的标志恢复为未被访问的标志。第二章进 程 管 理 进进程程中中除除上上述述进进入入区区、临临界界区区及及退退出出区区之之外外的的其其它它部部分分的的代代码码，在在这这里里都都称称为为剩剩余余区区。这这样样，可可把把一一个个访访问问临临界界资资源源的的循环进程描述如下：循环进程描述如下：repeatentry sectioncritical section；exit
12、 sectionremainder section；until false；.Request printerprint.Print.Request plotterprintplotprintplotfree plotterprintfree printer.Request plotterplot.Plot.Request printerprintplotprintplotfree printerplotfree plotter.P1P2CS指那一指那一段段？P1，P2若不若不制约，会出现制约，会出现什么问题什么问题？临界区例临界区例第二章进 程 管 理 4同步机制应遵循的规则同步机制应遵循的规
13、则(临界区调度准则）临界区调度准则）为为实实现现进进程程互互斥斥地地进进入入自自已已的的临临界界区区，通通常常是是在在系系统统中中设设置置专专门门的的同同步步机机构构来来协协调调各各进进程程间间的的运运行行。所所有有同同步步机机制制都都应应遵遵循循下述四条准则：下述四条准则：(1) 空空闲闲让让进进。当当无无进进程程处处于于临临界界区区时时，表表明明临临界界资资源源处处于于空空闲闲状状态态，应应允允许许一一个个请请求求进进入入临临界界区区的的进进程程立立即即进进入入自自己己的的临临界界区，以有效地利用临界资源。区，以有效地利用临界资源。(2) 忙则等待。当已有进程进入临界区时，表明临界资源正在
14、忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，因而其它试图进入临界区的进程必须等待，以保证对临被访问，因而其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。界资源的互斥访问。第二章进 程 管 理 (3) 有有限限等等待待。对对要要求求访访问问临临界界资资源源的的进进程程，应应保保证证在在有有限时间内能进入自己的临界区，以免陷入限时间内能进入自己的临界区，以免陷入“死等死等”状态。状态。(4) 让权等待。当进程不能进入自己的临界区时，应立即让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入释放处理机，以免进程陷入“忙等忙等”状态。状态。第二章进 程 管
15、 理 2.3.2信号量机制信号量机制1整型信号量整型信号量最最初初由由Dijkstra把把整整型型信信号号量量定定义义为为一一个个用用于于表表示示资资源源数数目目的的整整型型量量S，它它与与一一般般整整型型量量不不同同，除除初初始始化化外外，仅仅能能通通过过两两个个标标准准的的原原子子操操作作(Atomic Operation) wait(S)和和signal(S)来来访访问问。这这两两个个操操作作被被分分别别称称为为P、V操操作作。Wait(S)和和signal(S)操作可描述为：操作可描述为：wait(S)： while S=0 do no-op；S:=S-1；signal(S)：S:=S
16、+1；有忙等现象有忙等现象第二章进 程 管 理 wait(S)和和signal(S)是两个原子操作，因此，它们在执行是两个原子操作，因此，它们在执行时是不可中断的。亦即，当一个进程在修改某信号量时，没时是不可中断的。亦即，当一个进程在修改某信号量时，没有其他进程可同时对该信号量进行修改。有其他进程可同时对该信号量进行修改。第二章进 程 管 理 2记录型信号量记录型信号量1.在整型信号量机制中的在整型信号量机制中的wait操作，只要是信号量操作，只要是信号量S0，就，就会不断地测试。因此，该机制并未遵循会不断地测试。因此，该机制并未遵循“让权等待让权等待”的的准则，而是使进程处于准则，而是使进程
17、处于“忙等忙等”的状态。的状态。2.为此，在记录型信号量机制中，除了需要一个用于代表为此，在记录型信号量机制中，除了需要一个用于代表资源数目的整型变量资源数目的整型变量value外，还应增加一个进程链表指外，还应增加一个进程链表指针针L，用于链接上述的所有等待进程。，用于链接上述的所有等待进程。第二章进 程 管 理 type semaphore=recordvalue: integer；L: list of process；end 信号量信号量: 有一个整型变量有一个整型变量; 有一个相关的等待队列有一个相关的等待队列; 除了初始化外除了初始化外,只能对其做只能对其做wait,signal 操
18、作（操作（P、V操作）操作）第二章进 程 管 理 相应地，相应地，wait(S)和和signal(S)操作可描述为：操作可描述为： procedure wait(S)var S：semaphore；beginS.value:=S.value-1；if S.value0 then block(S.L)； end procedure signal(S)var S: semaphore；beginS.value:=S.value+1；if S.value=0 then wakeup(S.L)； end 第二章进 程 管 理 1.1.1.1. S.valueS.value的初值表示系统中某类资源的数目
19、，因而又称为资的初值表示系统中某类资源的数目，因而又称为资源信号量。源信号量。对它的每次对它的每次waitwait操作，意味着进程请求一个单位操作，意味着进程请求一个单位的该类资源，的该类资源，使系统中可供分配的该类资源数减少一个，当使系统中可供分配的该类资源数减少一个，当S.value0S.value0，表示可用资源个数；当，表示可用资源个数；当mutexwait(P)-wait(Q)-signal(Q)-signal(P)wait(Q)-wait(P)-signal(Q)-signal(P)=1 and and Sn=1 thenfor i:=1 to n doSi:=Si-1；endfo
20、relseplace the process in the waiting queue associated with the first Si found with Si=t1 and and Sn=tn thenfor i:=1 to n doSi:=Si-di；endforelsePlace the executing process in the waiting queue of the first Si with Si1时时)或互斥信号量或互斥信号量(S=1时时)。(3) Swait(S，1，0)。这是一种很特殊且很有用的信号量。这是一种很特殊且很有用的信号量操作。当操作。当S1时，
21、允许多个进程进入某特定区；当时，允许多个进程进入某特定区；当S变为变为0后，后，将阻止任何进程进入特定区。换言之，它相当于一个可控开将阻止任何进程进入特定区。换言之，它相当于一个可控开关。关。第二章进 程 管 理 2.3.4管程机制管程机制1管程的定义管程的定义 系统中的各种硬件资源和软件资源，均可用数据结构系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性，即用少量信息和对该资源所执行抽象地描述其资源特性，即用少量信息和对该资源所执行的操作来表征该资源，而忽略了它们的内部结构和实现细的操作来表征该资源，而忽略了它们的内部结构和实现细节。节。1.例如，对一台电传机，可用与分配该
22、资源有关的状态信息例如，对一台电传机，可用与分配该资源有关的状态信息(busy或或free)和和对它执行请求与释放的操作，以及等待该资源的进程队列来描述。对它执行请求与释放的操作，以及等待该资源的进程队列来描述。2.又如，一个又如，一个FIFO队列，可用其队长、队首和队尾以及在该队列上执行的队列，可用其队长、队首和队尾以及在该队列上执行的一组操作来描述。一组操作来描述。第二章进 程 管 理 1.利用共享数据结构抽象地表示系统中的共享资源，而把利用共享数据结构抽象地表示系统中的共享资源，而把对该共享数据结构实施的操作定义为一组过程，如资源对该共享数据结构实施的操作定义为一组过程，如资源的请求和释
23、放过程的请求和释放过程request和和release。2.进程对共享资源的申请、释放和其它操作，都是通过这进程对共享资源的申请、释放和其它操作，都是通过这组过程对共享数据结构的操作来实现的，组过程对共享数据结构的操作来实现的，3.这组过程还可以根据资源的情况，或接受或阻塞进程的这组过程还可以根据资源的情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥。以统一管理对共享资源的所有访问，实现进程互斥。第二章进 程 管 理 管管程程定定义义：代代表表共共享享资资源源的的数数据据结结构构
24、，以以及及由由对对该该共共享享数数据据结结构构实实施施操操作作的的一一组组过过程程所所组组成成的的资资源源管管理理程程序序，共共同同构构成成了了一一个个操操作作系系统统的的资资源源管管理理模模块块。管管程程被被请请求求和和释放资源的进程所调用。释放资源的进程所调用。1.Hansan为为管管程程所所下下的的定定义义是是：“一一个个管管程程定定义义了了一一个个数数据据结结构构和和能能为为并并发发进进程程所所执执行行(在在该该数数据据结结构构上上)的的一一组组操操作作，这组操作能同步进程和改变管程中的数据这组操作能同步进程和改变管程中的数据”。2.由上述的定义可知，管程由四部分组成：由上述的定义可知
25、，管程由四部分组成： 管程的名称；管程的名称； 局部于管程内部的共享数据结构说明；局部于管程内部的共享数据结构说明； 对该数据结对该数据结构进行操作的一组过程；构进行操作的一组过程； 对局部于管程内部的共享数据对局部于管程内部的共享数据设置初始值的语句。设置初始值的语句。第二章进 程 管 理 图图2-13管程的示意图管程的示意图 第二章进 程 管 理 管程的语法描述如下：管程的语法描述如下：type monitor_name = MONITOR；define ；use ；procedure ()；beginend; 第二章进 程 管 理 function ()：值类型；：值类型；beginen
26、d； begin ；end 第二章进 程 管 理 1.局局部部于于管管程程内内部部的的数数据据结结构构，仅仅能能被被局局部部于于管管程程内内部部的的过程所访问，任何管程外的过程都不能访问它；过程所访问，任何管程外的过程都不能访问它；2.局部于管程内部的过程也仅能访问管程内的数据结构。局部于管程内部的过程也仅能访问管程内的数据结构。3.管管程程相相当当于于围围墙墙，它它把把共共享享变变量量和和对对它它进进行行操操作作的的若若干干过过程程围围了了起起来来，所所有有进进程程要要访访问问临临界界资资源源时时，都都必必须须经经过过管管程程(相相当当于于通通过过围围墙墙的的门门)才才能能进进入入，而而管管
27、程程每每次次只只准许一个进程进入管程，从而实现了进程互斥。准许一个进程进入管程，从而实现了进程互斥。第二章进 程 管 理 管程主要有以下特性：管程主要有以下特性： (1) 模块化。管程是一个基本程序单位，可以单独编译。模块化。管程是一个基本程序单位，可以单独编译。(2) 抽象数据类型。管程中不仅有数据，而且有对数据的抽象数据类型。管程中不仅有数据，而且有对数据的操作。操作。(3) 信息掩蔽。管程中的数据结构只能被管程中的过程访信息掩蔽。管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，供管程外的进程调用，问，这些过程也是在管程内部定义的，供管程外的进程调用，而管程中的数据结
28、构以及过程而管程中的数据结构以及过程(函数函数)的具体实现外部不可见。的具体实现外部不可见。第二章进 程 管 理 管程和进程区别管程和进程区别(1) 虽虽然然二二者者都都定定义义了了数数据据结结构构，但但进进程程定定义义的的是是私私有有数据结构数据结构PCB，管程定义的是公共数据结构，如消息队列等；，管程定义的是公共数据结构，如消息队列等；(2) 二二者者都都存存在在对对各各自自数数据据结结构构上上的的操操作作，但但进进程程是是由由顺顺序序程程序序执执行行有有关关的的操操作作，而而管管程程主主要要是是进进行行同同步步操操作作和和初初始化操作；始化操作；(3) 设置进程的目的在于实现系统的并发性
29、，而管程的设置进程的目的在于实现系统的并发性，而管程的设置则是解决共享资源的互斥使用问题；设置则是解决共享资源的互斥使用问题；第二章进 程 管 理 (4) 进进程程通通过过调调用用管管程程中中的的过过程程对对共共享享数数据据结结构构实实行行操操作作，该该过过程程就就如如通通常常的的子子程程序序一一样样被被调调用用，因因而而管管程程为为被被动动工工作作方方式，进程则为主动工作方式；式，进程则为主动工作方式；(5) 进程之间能并发执行，而管程则不能与其调用者并发；进程之间能并发执行，而管程则不能与其调用者并发；(6) 进程具有动态性，由进程具有动态性，由“创建创建”而诞生，由而诞生，由“撤销撤销”
30、而消而消亡，而管程则是操作系统中的一个资源管理模块，供进程调用。亡，而管程则是操作系统中的一个资源管理模块，供进程调用。 第二章进 程 管 理 2条件变量条件变量在利用管程实现进程同步时，必须设置同步工具，如在利用管程实现进程同步时，必须设置同步工具，如两个同步操作原语两个同步操作原语wait和和signal。当某进程通过管程请求获。当某进程通过管程请求获得临界资源而未能满足时，管程便调用得临界资源而未能满足时，管程便调用wait原语使该进程原语使该进程等待，并将其排在等待队列上，如图等待，并将其排在等待队列上，如图2-13 所示。仅当另一所示。仅当另一进程访问完成并释放该资源之后，管程才又调
31、用进程访问完成并释放该资源之后，管程才又调用signal原语，原语，唤醒等待队列中的队首进程。唤醒等待队列中的队首进程。第二章进 程 管 理 但是仅仅有上述的同步工具是不够的。考虑一种情况：但是仅仅有上述的同步工具是不够的。考虑一种情况：当一个进程调用了管程，在管程中时被阻塞或挂起，直到阻当一个进程调用了管程，在管程中时被阻塞或挂起，直到阻塞或挂起的原因解除，而在此期间，如果该进程不释放管程，塞或挂起的原因解除，而在此期间，如果该进程不释放管程，则其它进程无法进入管程，被迫长时间地等待。为了解决这则其它进程无法进入管程，被迫长时间地等待。为了解决这个问题，引入了条件变量个问题，引入了条件变量c
32、ondition。通常，一个进程被阻塞。通常，一个进程被阻塞或挂起的条件或挂起的条件(原因原因)可有多个，因此在管程中设置了多个条可有多个，因此在管程中设置了多个条件变量，对这些条件变量的访问，只能在管程中进行件变量，对这些条件变量的访问，只能在管程中进行。第二章进 程 管 理 管管程程中中对对每每个个条条件件变变量量都都须须予予以以说说明明，其其形形式式为为：Var x，y：condition。对对条条件件变变量量的的操操作作仅仅仅仅是是wait和和signal，因因此此条条件件变变量量也也是是一一种种抽抽象象数数据据类类型型，每每个个条条件件变变量量保保存存了了一一个个链链表表，用用于于记
33、记录录因因该该条条件件变变量量而而阻阻塞塞的的所所有有进进程程，同同时时提提供的两个操作即可表示为供的两个操作即可表示为x.wait和和x.signal，其含义为：，其含义为： x.wait：正在调用管程的进程因：正在调用管程的进程因x条件需要被阻塞或条件需要被阻塞或挂起，则调用挂起，则调用x.wait将自己插入到将自己插入到x条件的等待队列上，并释条件的等待队列上，并释放管程，直到放管程，直到x条件变化。此时其它进程可以使用该管程。条件变化。此时其它进程可以使用该管程。第二章进 程 管 理 x.signal：正正在在调调用用管管程程的的进进程程发发现现x条条件件发发生生了了变变化化，则则调调
34、用用x.signal，重重新新启启动动一一个个因因x条条件件而而阻阻塞塞或或挂挂起起的的进进程程。如如果果存存在在多多个个这这样样的的进进程程，则则选选择择其其中中的的一一个个，如如果果没没有有，则则继继续续执执行行原原进进程程，而而不不产产生生任任何何结结果果。这这与与信信号号量量机机制制中中的的signal操操作作不不同同，因因为为后后者者总总是是要要执执行行s:=s+1操操作作，因因而而总总会改变信号量的状态。会改变信号量的状态。如如果果有有进进程程Q因因x条条件件处处于于阻阻塞塞状状态态，当当正正在在调调用用管管程程的的进进程程P执执行行了了x.signal操操作作后后，进进程程Q 被
35、被重重新新启启动动，此此时时两两个个进进程程P和和Q，如如何何确确定定哪哪个个执执行行，哪哪个个等等待待，可可采采用用下下述述两两种种方方式之一进行处理：式之一进行处理：(1) P等待，直至等待，直至Q离开管程或等待另一条件。离开管程或等待另一条件。(2) Q等待，直至等待，直至P离开管程或等待另一条件。离开管程或等待另一条件。第二章进 程 管 理 购物问题。某超级市场，可容纳100人同时购物。入口处备有篮子，每个购物者可持一个篮子入内购物。出口处结帐，并归还篮子（出、入口仅容纳一个人通过，篮子有无限多个）。（1）请用P、V操作解决购物问题。（2）若顾客最多为N个人，写出算法中同步信号量同步信号量值的可能变化范围(2分)（*说明算法中所定义信号量的含义和初值）第二章进 程 管 理 作业一：作业一：用信号量PV操作解决下述进程之间的同步与互斥问题：三个进程P1、P2、P3。P1进程通过计算将产生的整数（可能是奇数或偶数）送到容量为200的缓冲区buff1中，P2从buff1中取出偶数数据加1后送回到缓冲区buff1中，P3负责从buff1中取出奇数数据进行打印。要求：各进程不能同时进入buff1中。请写出每个进程的动作序列。作业二：作业二：两个相对方向的车依次到达一座独木桥的两端。在任一时刻只允许一个方向的车在桥上通行。设计一个交通管制方案，使两个方向的车顺利通过该桥。
