第3章 进程和处理机管理.ppt

《第3章 进程和处理机管理.ppt》由会员分享，可在线阅读，更多相关《第3章 进程和处理机管理.ppt（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章章 进程和处理机管理进程和处理机管理3.1进程的概念和定义进程的概念和定义3.2进程的状态和进程控制块进程的状态和进程控制块3.3进程控制进程控制3.4进程的互斥与同步进程的互斥与同步3.5进程通信进程通信3.6进程调度进程调度3.7线程线程本章学习目标本章学习目标在在多多道道程程序序环环境境下下，程程序序不不能能独独立立运运行行。作作为为资资源源分分配配和和独独立立运运行行的的基基本本单单位位是是进进程程。操操作作系系统统所所有有的的特特征征都都是是基基于进程而体现的。所以，本章的主要问题是：于进程而体现的。所以，本章的主要问题是：进程的概念进程的概念进程的实体、状态及状态的演变进程

2、的实体、状态及状态的演变进程的控制与调度进程的控制与调度进程之间的关系协调进程之间的关系协调进程的通信进程的通信3.1进程的概念和定义进程的概念和定义3.1.1 进程的引入进程的引入1程序的顺序执行及其特性程序的顺序执行及其特性在单道程序工作环境中，我们把一个在单道程序工作环境中，我们把一个“程序程序”理理解为解为“一个在时间上按严格次序前后相继的操作一个在时间上按严格次序前后相继的操作序列序列”。顺序执行的特征：顺序执行的特征：顺序性顺序性：每执行一条指令，系统就从上一个执行状态转：每执行一条指令，系统就从上一个执行状态转移到下一个执行状态，且上一条指令的执行结束是下一移到下一个执行状态，且

3、上一条指令的执行结束是下一条指令执行开始的充分必要条件；条指令执行开始的充分必要条件；封闭性封闭性：程序执行得到的结果由给定的初始条件决定，程序执行得到的结果由给定的初始条件决定，不受外界因素的影响；不受外界因素的影响；可再现性可再现性：顺序执行的最终结果可再现是说它与执行：顺序执行的最终结果可再现是说它与执行速度无关。只要输入的初始条件相同，则无论何时重复速度无关。只要输入的初始条件相同，则无论何时重复执行该程序都会得到执行该程序都会得到相同的结果。相同的结果。2程序的并行执行及其特性程序的并行执行及其特性 失去程序的封闭性失去程序的封闭性例如：例如：程序A程序BN：=N+1；PRINT（N

4、）；N：=0；N：=0AB：输出：1N：=0B-A：输出：0N：=1B-A-B：输出：0N：=0并行程序执行时相互制约并行程序执行时相互制约程序的制约方式有如下两种程序的制约方式有如下两种：（1）间接制约方式。）间接制约方式。这是由于这是由于竞争相同资源竞争相同资源而引起的，得到资源的程序而引起的，得到资源的程序段可以投入运行，而得不到资源的程序段就是暂时等待，段可以投入运行，而得不到资源的程序段就是暂时等待，直至获得可用资源时再继续运行直至获得可用资源时再继续运行。（2）直接制约方式。）直接制约方式。这通常是在那些逻辑上相关的程序段之间发生的。一般是这通常是在那些逻辑上相关的程序段之间发生的

5、。一般是由于各种程序段要求由于各种程序段要求共享信息共享信息引起的引起的。3.1.2 进程的定义进程的定义 进程：一个具有一定独立功能的程序在一个数据集合进程：一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。上的一次动态执行过程。进程与程序的区别和相互关系进程与程序的区别和相互关系：（1）进程是动态的，程序是静态的。）进程是动态的，程序是静态的。（2）从结构上看每个进程的实体都是由程序段和相应的数据段两）从结构上看每个进程的实体都是由程序段和相应的数据段两部分构成的，这一特征与程序的含义相近。部分构成的，这一特征与程序的含义相近。（3）一个进程至少对应一段程序；一个程序可以对应多

6、个进程，）一个进程至少对应一段程序；一个程序可以对应多个进程，（4）进程具有并发性，程序没有。）进程具有并发性，程序没有。（5）进程具有创建其他进程的功能。）进程具有创建其他进程的功能。（6）操作系统中的每一个程序都是在一个进程现场中运行的。）操作系统中的每一个程序都是在一个进程现场中运行的。3.2进程的状态和进程控制块进程的状态和进程控制块 3.2.1进程的状态进程的状态（1）运运行行状状态态：进进程程正正在在处处理理机机上上运运行行的的状状态态，该该进进程程已已获获得得必必要的资源，也获得了处理机，用户程序正在处理机上运行。要的资源，也获得了处理机，用户程序正在处理机上运行。（2）阻阻塞塞

7、状状态态：进进程程等等待待某某种种事事件件完完成成（例例如如，等等待待输输入入/输输出出操操作作的的完完成成）而而暂暂时时不不能能运运行行的的状状态态，处处于于该该状状态态的的进进程程不不能能参参加加竞竞争处理机，此时，即使分配给它处理机，它也不能运行。争处理机，此时，即使分配给它处理机，它也不能运行。（3）就就绪绪状状态态：该该进进程程运运行行所所需需的的一一切切条条件件都都得得到到满满足足，但但因因处处理理机机资资源源个个数数少少于于进进程程个个数数，所所以以该该进进程程不不能能运运行行，而而必必须须等等待待分分配处理机资源，一旦获得处理机就立即投入运行。配处理机资源，一旦获得处理机就立即

8、投入运行。（4）先先出出现现的的是是就就绪绪状状态态然然后后是是运运行行状状态态，在在运运行行状状态态中中可可能能出出现阻塞状态，或者正常完成。现阻塞状态，或者正常完成。典型的进程状态演变图典型的进程状态演变图3.2.2进程状态的演变进程状态的演变状态变化状态变化：（1）就绪状态变化到运行状态）就绪状态变化到运行状态。（2）运行状态变化到就绪状态。）运行状态变化到就绪状态。（3）运行状态变化到阻塞状态。）运行状态变化到阻塞状态。（4）阻塞状态变化到就绪状态。）阻塞状态变化到就绪状态。3.2.3进进程控制程控制块块 为为了刻画了刻画进进程的程的动态变动态变化，通常把化，通常把进进程表示程表示为为

9、由程序段、私由程序段、私有数据有数据块块和和进进程控制程控制块组块组成。成。程序部分描述程序部分描述进进程本身所要完成的功能程本身所要完成的功能“私有数据私有数据块块”是接受程序是接受程序规规定操作的一定操作的一组组存存储单储单元的内容，元的内容，是操作的是操作的对对象。象。进进程控制程控制块块是在是在进进程程创创建建时产时产生的，当生的，当进进程存在于系程存在于系统时统时（运行），（运行），进进程控制程控制块块就就标识标识了了这这个个进进程。程。进程控制块是进程存在的标志，当系统或父进程进程控制块是进程存在的标志，当系统或父进程创建一个进程时，实际上就是为其建立一个进程创建一个进程时，实际上

10、就是为其建立一个进程控制块。控制块。进进程程控控制制块块既既能能标标识识进进程程的的存存在在，又又能能刻刻画画出出进进程程的的动动态态特特征征，它它是是一一个个进进程程仅仅有有的的被被系系统统真真正正感感知知的的部部分分。对对操操作作系系统统而而言言，所所有有进进程程控控制制块块将构成并发执行控制和维护系统工作的依据。将构成并发执行控制和维护系统工作的依据。进程控制块的作用：进程控制块的作用：进程队列进程队列为了实现对进程的管理为了实现对进程的管理,系统将所有系统将所有进程的进程的PCB排成若干个队列排成若干个队列,称为进程称为进程队列。队列。进程队列通常系统中分成三类：就绪进程队列通常系统中

11、分成三类：就绪队列，队列，等待队列，等待队列，运行队列。运行队列。3.3进程控制进程控制3.3.1进程家族进程家族父进程创建的进程形成树型结构。父进程创建的进程形成树型结构。3.3.2原语原语进程和处理机管理的一个重要任务是进进程和处理机管理的一个重要任务是进程控制。程控制。进程控制，系统使用一些具有特定功能进程控制，系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各的程序段来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。执行和协调、实现资源共享的目的。我们把系统态下执行的某些具有持定功我们把

12、系统态下执行的某些具有持定功能的程序段称为原语。原语是不被分割或不能的程序段称为原语。原语是不被分割或不被中断执行的操作序列。被中断执行的操作序列。3.3.3进进程控制原程控制原语语1创创建原建原语语2撤消原撤消原语语3阻塞原阻塞原语语4唤唤醒原醒原语语创建创建进进程原程原语语流流图图互斥关系（亦称间接制约关系）互斥关系（亦称间接制约关系）进程间因相互竞争使用独占型资源（互斥资源）所产生的制进程间因相互竞争使用独占型资源（互斥资源）所产生的制约关系。约关系。同步关系（亦称直接制约关系）同步关系（亦称直接制约关系）指完成同一任务的伙伴进程间，因需要在某些位置上协调它们指完成同一任务的伙伴进程间，

13、因需要在某些位置上协调它们的工作而等待、传递信息所产生的制约关系。的工作而等待、传递信息所产生的制约关系。3.4进程的互斥与同步进程的互斥与同步3.4.1临临界区界区临界资源：一次只允许一个进程使用的资源称为临界资源。临界资源：一次只允许一个进程使用的资源称为临界资源。几个进程若共享同一临界资源，它们必须以互斥的方式使用几个进程若共享同一临界资源，它们必须以互斥的方式使用这个临界资源，即当一个进程正在使用临界资源且尚未使用这个临界资源，即当一个进程正在使用临界资源且尚未使用完毕时，则其他进程必须推迟对该资源的进一步操作，在当完毕时，则其他进程必须推迟对该资源的进一步操作，在当前进程的使用完成之

14、前，不能从中插进去使用这个临界资源，前进程的使用完成之前，不能从中插进去使用这个临界资源，否则将会造成信息混乱和操作出错。否则将会造成信息混乱和操作出错。临临界区界区：访问临界资源的：访问临界资源的程序段。程序段。A:beginN:=count;N:=N+100;count:=N;end;B:beginM:=count;M:=M-200;count:=M;end;3.4.2进程互斥进程互斥 信号量信号量S为一整型变量：为一整型变量：P、V操作是两条原语操作是两条原语P操作操作P(S):S=S1;IfS0then进程阻塞，将本进程挂入等待队列。进程阻塞，将本进程挂入等待队列。V操作操作 V(S)

15、:S:=S+1；IfS0then从等待队列取一进程，挂入就绪队列从等待队列取一进程，挂入就绪队列。用信号量实现进程互斥用信号量实现进程互斥 设置一个公用信号量设置一个公用信号量mutex，初值为，初值为1，每个进程可，每个进程可以对它进行以对它进行P操作或操作或V操作。用于操作。用于n个进程的临界区互个进程的临界区互斥，任一进程斥，任一进程Pi的结构为：的结构为：P(mutex)V(mutex)临界区临界区非临界区非临界区读者与写者问题读者与写者问题设设F为共享文件，各进程可对为共享文件，各进程可对F进行读和修改。进行读和修改。要求：要求：多个进程可同时读多个进程可同时读F。一个进程对一个进程

16、对F修改时，其他进程不能读或修改。修改时，其他进程不能读或修改。有进程读有进程读F时，其他进程不能修改。时，其他进程不能修改。下面给出读者进程与写者进程的一般结构。下面给出读者进程与写者进程的一般结构。begins,sr:semaphore;rc:integer;S:=1；sr:=1;rc:=0cobeginprocedurereader;beginP(sr);Rc:=rc+1;Ifrc=1thenP(s);V(sr);Reading;P(sr);rc:=rc-1;ifrc=0thenV(s);V(sr);end;procedurewriter;beginP(s);writing;V(s);e

17、nd;Coend;end;3.4.2进程同步进程同步用信号量实现进程同步：用信号量实现进程同步：设置一组私用信号量设置一组私用信号量，初值为，初值为0或正整数，仅允许拥或正整数，仅允许拥有它的进程对它进行有它的进程对它进行P操作。用于操作。用于n个进程的同步。个进程的同步。例：计算进程和打印进程通过单缓冲区的同步。例：计算进程和打印进程通过单缓冲区的同步。计算进程把计算结果存入缓冲区，打印进程从缓冲区计算进程把计算结果存入缓冲区，打印进程从缓冲区中取出数据打印。它们对缓冲区的操作构成同步。中取出数据打印。它们对缓冲区的操作构成同步。而缓冲区作为共享资源，当一个进程对它的操作还没而缓冲区作为共享

18、资源，当一个进程对它的操作还没有结束时，不允许另一个进程对它进行操作，故对它有结束时，不允许另一个进程对它进行操作，故对它的操作是互斥的。的操作是互斥的。设置两个私用信号量设置两个私用信号量SC和和SP。S1初值为初值为1，S2初值为初值为0，信号量，信号量S1表示缓冲区是否有卡片信息，表示缓冲区是否有卡片信息，S2表示缓表示缓冲区信息是否被取走。利用冲区信息是否被取走。利用P、V操作实现进程操作实现进程A、B的同步算法如下：的同步算法如下：分别表示缓冲区满和空的个分别表示缓冲区满和空的个数，数，Mutex为公用信号量。为公用信号量。3.5.1 线程的引入线程的引入（1 1）创创建建进进程程。

19、系系统统在在创创建建进进程程时时，必必须须为为之之分分配配其其所所必必需需的的、除除处处理理机机以以外外的的所所有有资资源源。如如内内存空间、存空间、I/OI/O设备以及建立相应的设备以及建立相应的PCBPCB结构。结构。（2 2）撤撤消消进进程程。系系统统在在撤撤消消进进程程时时，又又必必须须先先对对这些资源进行回收操作，然后再撤消这些资源进行回收操作，然后再撤消PCBPCB结构。结构。（3 3）进进程程切切换换。在在对对进进程程进进行行切切换换时时，由由于于要要保保留留当当前前进进程程的的CPUCPU环环境境和和设设置置新新选选中中进进程程的的CPUCPU环环境，为此需花费不少处理机时间。

20、境，为此需花费不少处理机时间。返回本节目录返回本节目录3.5.2 线程与进程的比较线程与进程的比较1调调度度：在在传传统统的的操操作作系系统统中中，拥拥有有资资源源的的基基本本单单位位和和独独立立调调度度、分派的基本单位都是进程。分派的基本单位都是进程。2并并发发性性：在在引引入入线线程程的的操操作作系系统统中中，不不仅仅进进程程之之间间可可以以并并发发执执行行，而而且且在在一一个个进进程程中中的的多多个个线线程程之之间间亦亦可可并并发发执执行行，因因而而使使操操作作系系统统具具有有更更好好的的并并发发性性，从从而而能能更更有有效效地地使使用用系系统统资资源源和和提提高系统吞吐量。高系统吞吐量

21、。3拥拥有有资资源源：不不论论是是传传统统的的操操作作系系统统，还还是是设设有有线线程程的的操操作作系系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。4系系统统开开销销：由由于于在在创创建建或或撤撤消消进进程程时时，系系统统都都要要为为之之分分配配或或回回收收资资源源，如如内内存存空空间间、I/O设设备备等等。因因此此，操操作作系系统统所所付付出出的的开开销将明显地大于在创建或撤消线程时的开销。销将明显地大于在创建或撤消线程时的开销。返回本节目录返回本节目录3.5.3 用户级线程和内核支持线程用户级线程和内核支持线程比较两种

22、线程的优缺点比较两种线程的优缺点：1线程的调度与切换速度：线程的调度与切换速度：内核支持线程的调度和切换与进内核支持线程的调度和切换与进程的调度和切换十分相似。程的调度和切换十分相似。2系统功能调用：系统功能调用：当传统的用户进程调用一个系统功能调用当传统的用户进程调用一个系统功能调用时，要由用户态进入核心态，用户进程将被阻塞。当内核完成时，要由用户态进入核心态，用户进程将被阻塞。当内核完成系统调用而返回时，才将该进程唤醒，继续执行。系统调用而返回时，才将该进程唤醒，继续执行。3线程执行时间线程执行时间：对于只设置了用户级线程的系统，调度是对于只设置了用户级线程的系统，调度是以进程为单位进行的

23、。在采用轮转调度算法时，各个进程轮流以进程为单位进行的。在采用轮转调度算法时，各个进程轮流执行一个时间片，这对诸进程而言似乎是公平的。执行一个时间片，这对诸进程而言似乎是公平的。返回本节目录返回本节目录3.6进程调度进程调度 3.6.1进程调度的职能进程调度的职能 3.6.2进程调度算法进程调度算法 3.6.3调度用的进程状态切换图调度用的进程状态切换图 返回本章首页返回本章首页3.6.1进程调度的职能进程调度的职能（1）记录系统中所有进程的有关情况。）记录系统中所有进程的有关情况。（2）确定分配处理机的原则。）确定分配处理机的原则。（3）分配处理机给进程。）分配处理机给进程。（4）从进程收回

24、处理机。）从进程收回处理机。返回本节目录返回本节目录3.6.2进程调度算法进程调度算法 1先来先服务先来先服务 2轮转调度轮转调度 3分级轮转法分级轮转法4优先数法优先数法 下一页下一页1先来先服务先来先服务 这这种种调调度度算算法法按按照照进进程程进进入入就就绪绪队队列列的的先先后后顺顺序序来来调调度度进进程程，到到达达得得越越早早，其其优优先先数数越越高高。获获得得处处理理机机的的进进程程，未未遇遇到到其其他他情情况况时时，一一直直运运行行下下去去，系系统统只只需需具具备备一一个个先先进进先先出出的的队队列列，在在管管理理优优先先数数的的就就绪绪队队列列时时，这这种种方方法法是是一一种种最

25、最常常见见策策略略，并并且且在在没没有有其其他他信信息息时时，也也是是一一种种最最合合理理的的策略。策略。下一页下一页2轮转调度轮转调度 先先来来先先服服务务的的一一个个重重要要变变形形，就就是是轮轮转转规规则则。轮轮转转调调度度算算法法是是系系统统把把所所有有就就绪绪进进程程按按先先后后次次序序排排队队，处处理理机机总总是是优优先先分分配配给给就就绪绪队队列列中中的的第第一一个个就就绪绪进进程程，并并分分配配它它一一个个固固定定的的时时间间片片（如如100毫毫秒秒）。当当该该运运行行进进程程用用完完规规定定的的时时间间片片时时，被被迫迫释释放放处处理理机机给给下下一一个个处处于于就就绪绪队队

26、列列中中的的第第一一个个进进程程，分分给给这这个个进进程程相相同同的的时时间间片片，每每个个运运行行完完时时间间片片的的进进程程，当当未未遇遇到到任任何何阻阻塞塞时时，就就回回到到就就绪绪队队列列的的尾尾部部，并并等等待待下下次次转转到到它它时时再再投投入入运运行行。于于是是，只只要要是是处处于于就就绪绪队队列列中中的的进进程程，按按此此种种算算法法迟迟早早总总可可以以分分得得处处理理机机投投入入运运行。行。下一页下一页3分级轮转法分级轮转法所谓分级轮转法就是将先前的一个就绪队列。根所谓分级轮转法就是将先前的一个就绪队列。根据进程的优先数不同划分两个或两个以上的就绪据进程的优先数不同划分两个或

27、两个以上的就绪队列，并赋给每个队列不同的优先数。以两个就队列，并赋给每个队列不同的优先数。以两个就绪队列为例，一个具有较高优先数，另一个具有绪队列为例，一个具有较高优先数，另一个具有较低优先数，前者称为前台队列，后者称为后台较低优先数，前者称为前台队列，后者称为后台队列。队列。下一页下一页4优先数法优先数法 根据已占有处理根据已占有处理机的进程是否可被剥夺而分为优先占有机的进程是否可被剥夺而分为优先占有法和优先剥夺法两种法和优先剥夺法两种。优先占有法的原理是：一旦某个最高优先数的就绪进程分优先占有法的原理是：一旦某个最高优先数的就绪进程分得处理机之后，只要不是其自身的原因被阻塞（如要求得处理机

28、之后，只要不是其自身的原因被阻塞（如要求I/O操作）而不能继续运行时，就一直运行下去，直至运操作）而不能继续运行时，就一直运行下去，直至运行结束。行结束。优先剥夺法的原理是：当一个正在运行的进程即使其时间优先剥夺法的原理是：当一个正在运行的进程即使其时间片未用完，无论什么时候，只要就绪队列中有一个比它的片未用完，无论什么时候，只要就绪队列中有一个比它的优先数高的进程，优先数高的进程就可以取代以前正在运优先数高的进程，优先数高的进程就可以取代以前正在运行的进程，投入运行行的进程，投入运行。下一页下一页确定进程的优先数通常应考虑如下确定进程的优先数通常应考虑如下几个因素：几个因素：（1）进程类型。

29、）进程类型。（2）运行时间。）运行时间。（3）作业的优先数。）作业的优先数。（4）动态优先数。）动态优先数。返回本节目录返回本节目录3.6.3调度用的进程状态切换图调度用的进程状态切换图 图图3.6调度用的进程状态切换图调度用的进程状态切换图返回本节目录返回本节目录3.7进程通信进程通信 3.7.1临界资源和临界区临界资源和临界区 3.7.2进程的通信方式之一进程的通信方式之一同步与互斥同步与互斥 3.7.3两个经典的同步两个经典的同步/互斥问题互斥问题 3.7.4结构化的同步结构化的同步/互斥机制互斥机制管程管程 3.7.5进程的通信方式之二进程的通信方式之二消息缓冲消息缓冲 返回本章首页返

30、回本章首页1生产者与消费者问题生产者与消费者问题 Dijkstra把广义同步问题抽象成一种把广义同步问题抽象成一种“生产者与消费者问生产者与消费者问题题”（Producer-consumer-relationship）的抽象模型。事的抽象模型。事实上，计算机系统中的许多问题都可归结为生产者与消费实上，计算机系统中的许多问题都可归结为生产者与消费者问题，生产者与消费者可以通过一个环形缓冲池（见图者问题，生产者与消费者可以通过一个环形缓冲池（见图3.8）联系起来，环形缓冲池由几个大小相等的缓冲块组）联系起来，环形缓冲池由几个大小相等的缓冲块组成，每个缓冲块容纳一个产品。每个生产者可不断地每次成，每

31、个缓冲块容纳一个产品。每个生产者可不断地每次往缓冲池中送一个生产产品，而每个消费者则可不断地每往缓冲池中送一个生产产品，而每个消费者则可不断地每次从缓冲池中取出一个产品。次从缓冲池中取出一个产品。下一页下一页图图3.8环形缓冲池环形缓冲池下一页下一页下下面面给给出出基基于于环环形形缓缓冲冲区区的的生生产产者者与与消消费费者者关关系系的的形式描述，设：形式描述，设：（1）公公用用信信号号量量mutex：初初值值为为1，用用于于实实现现临临界界区区互斥。互斥。（2）生生产产者者私私用用信信号号量量empty：初初值值为为n，指指示示空空缓缓冲块数目。冲块数目。（3）消消费费者者私私用用信信号号量量

32、full：初初值值为为0，指指示示满满缓缓冲冲块数目。块数目。（4）整型量）整型量i和和j初值均为初值均为0，i指示首空缓冲块序号，指示首空缓冲块序号，j指示首满缓冲块序号。指示首满缓冲块序号。v模块模块设计如下：设计如下：下一页下一页Varmutex，empty，full：semaphore;i,j:integer；buffer：array0n一一1ofitem；Procedureproducer;生产者进程生产者进程beginwhiletruedobeginproduceaproduct;P(empty);下一页下一页P(mutex);Buffer(i)：Product;i：(i+1)mo

33、dn；V(mutex);V(full)endend;procedureconsumer;消费者进程消费者进程下一页下一页beginWhiletruedobeginP(full)；P(mutex)goods：buffer(j);j：(j+1)modn;V(mutex);V(empty);Consumeaproduct;end下一页下一页end;beginseminitial;i:j:0;cobeginproducer；consumer；coendend下一页下一页3.7.4结构化的同步结构化的同步/互斥机制互斥机制管程管程 建建立立管管程程的的基基本本理理由由是是：由由于于对对临临界界区区的的执

34、执行行分分散散在在各各进进程程中中，这这样样不不便便于于系系统统对对临临界界资资源源的的控控制制和和管管理理，也也很很难难发发现现和和纠纠正正分分散散在在用用户户程程序序中中的的对对同同步步原原语语的的错错误误使使用用等等问问题题。为为此此，应应把把分分散散的的各各同同类类临临界界区区集集中中起起来来。并并为为每每个个可可共共享享资资源源设设立立一一个个专专门门的的管管程程来来统统一一管管理理各各进进程程对对该该资资源源的的访访问问。这这样样既既便便于于系系统统管管理理共共享享资资源源，又又能能保证互斥访问。保证互斥访问。下一页下一页管程主要由两部分组成：管程主要由两部分组成：（1）局局部部于

35、于该该管管程程的的共共享享数数据据，这这些些数数据据表表示了相应资源的状态。示了相应资源的状态。（2）局局部部于于该该管管程程的的若若干干过过程程，每每个个过过程程完完成关于上述数据的某种规定操作。成关于上述数据的某种规定操作。为了实现对临界资源的互斥访问，管程每次为了实现对临界资源的互斥访问，管程每次只允许一个进程进入其内（即访问管程内的只允许一个进程进入其内（即访问管程内的某个过程），这是由编译系统保证的。某个过程），这是由编译系统保证的。下一页下一页monitorringbuffer;varrbuffer：array0n-1ofitem；k,nextempty,nextfull:inte

36、ger;empty,full:condition;procedureentryput(varproduct:item);beginifk=nwait(empty);rbuffernextempty:product;k:=k+1；nextempty:=(nextempty+1)modn;signal(full);end;例：以环形缓冲池为例，给出环形缓冲池的管程结构例：以环形缓冲池为例，给出环形缓冲池的管程结构下一页下一页procedureentryget(vargoods:item);beginifk=0wait(full);goods:=rbuffernextfull;k:=k-1;next

37、full:=(nextfull+1)modn;signal(empty);end;begink:=0;nextempty:=0;nextfull:=0;end;下一页下一页在利用管程解决生产者、消费者问题时，其中在利用管程解决生产者、消费者问题时，其中的生产者和消费者可描述为：的生产者和消费者可描述为：producer：beginrepeatproduceanitem；ringbuffer.put(item)；untilfalse；endconsumer：beginrepeatringbuffer.get(item)；consumetheitem；end返回本节目录返回本节目录3.7.5进程的

38、通信方式之二进程的通信方式之二消息缓冲消息缓冲 1SEND(A)（发送消息）原语发送消息）原语 2READ（A）（）（读取消息）原语读取消息）原语 下一页下一页1SEND(A)（发送消息）原语发送消息）原语 发发送送消消息息原原语语被被进进程程用用于于把把消消息息发发送送到到存存放放消消息息的的缓缓冲冲区区。A是是原原语语的的参参数数，表表示示发发送送区区的的地地址址。其其工工作作原原理理是是：首首先先调调用用“寻寻找找目目标标进进程程的的PCB”的的程程序序查查找找接接收收进进程程的的PCB，如如果果接接收收进进程程存存在在，申申请请一一个个存存放放消消息息的的缓缓冲冲区区，消消息息缓缓冲冲

39、区区为为空空时时，接接收收此此消消息息的的进进程程因因等等待待此此消消息息的的到到来来而而处处于于阻阻塞塞状状态态，则则唤唤醒醒此此进进程程，并并把把消消息息的的内内容容、发发送送原原语语的的进进程程名名和和消消息息等等，复复制制到到预预先先申申请请的的存存放放消消息息的的缓缓冲冲区区，且且将将存存放放消消息息的的缓缓冲冲区区连连接接到到接接收收进进程程的的PCB上上；如如果果接接收收进进程程不不存存在在，则则由由系系统统给给出出一一个个“哑哑”回回答答；最最后后控控制制返返回回到到发发送送消消息息的的进进程程继继续续执执行行，或或转转入入进进程程调调度度程程序序重重新新分分配配处处理理机机。

40、如如果果消消息息缓缓冲冲区区已已满满，则返回到非同步错误处理程序入口进行特殊处理。如图则返回到非同步错误处理程序入口进行特殊处理。如图3.9所示。所示。下一页下一页图图3.9发发送送消消息息过过程程流流图图下一页下一页2READ（A）（）（读取消息）原语读取消息）原语 READ(A)原语用来读取消息，接收进程原语用来读取消息，接收进程读取消息之前，在自己的空间中确定一读取消息之前，在自己的空间中确定一个接收区。当接收进程想要读取消息时，个接收区。当接收进程想要读取消息时，使用使用READ(A)原语，原语，A是接收进程提供是接收进程提供的接收区开始地址。如图的接收区开始地址。如图3.10所示。所

41、示。下一页下一页图图3.10读取消息读取消息返回本节目录返回本节目录3.8死锁问题死锁问题 3.8.1死锁产生的原因和必要条件死锁产生的原因和必要条件 3.8.2预防死锁预防死锁 3.8.3发现死锁发现死锁 3.8.4解除死锁解除死锁 返回本章首页返回本章首页3.8.1死锁产生的原因和必要条件死锁产生的原因和必要条件 死锁产生的原因死锁产生的原因：当某个进程提出申请资源后，使得有关进程在无当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继外力协助下，永远分配不到必需的资源而无法继续运行，这就产生了一种特殊的现象续运行，这就产生了一种特殊的现象死锁。死锁。在许多

42、实时应用中，比如计算机控制运输和监视在许多实时应用中，比如计算机控制运输和监视系统方面，死锁问题也极为重要。系统方面，死锁问题也极为重要。下一页下一页死锁产生例子死锁产生例子1：我我们们先先来来看看一一个个申申请请不不同同类类型型资资源源的的死死锁锁例例子子，假假定定有有两两个个进进程程Pl和和P2都都要要修修改改文文件件F，修修改改时时都都需需要要一一条条暂暂时时存存放放信信息息的的磁磁带带，而而只只有有一一台台磁磁带带机机T可可用用。又又假假定定由由于于某某种种原原因因，在在进进行行修修改改之之前前，P2需需要要一一暂暂存存磁磁带带（例例如如为为了了修修改改，要要重重新新组组织织输输入入数

43、数据据）。设设F和和T都都是是可可重重用用资资源源，它它们们分分别别表表示示允允许许更更新新文文件件和和允允许许使使用用磁磁带带机机。于于是是Pl和和P2。可有如下形式：可有如下形式：下一页下一页分析：分析：从上面的申请从上面的申请-释放过程可以看出，进程释放过程可以看出，进程Pl和和P2有可能有可能“同时同时”分别到达分别到达rl和和r2处，例如，处，例如，P2首先得到首先得到T，然后然后Pl得到得到F，接着接着Pl到达到达r1，最后最后P2到达到达r2，此时，若此时，若Pl继续运行，则占有继续运行，则占有F的进程的进程Pl将阻塞在将阻塞在T上，若上，若P2继续运行，则占有继续运行，则占有T

44、的进程的进程P2将将阻塞在阻塞在F上，如果上，如果P2不能前进，则不能前进，则P1也不能继续下去，反之亦也不能继续下去，反之亦然。我们说这两个进程处在死锁状态。然。我们说这两个进程处在死锁状态。下一页下一页图图3.11简单的死锁例子简单的死锁例子下一页下一页死锁产生例子死锁产生例子2：现现在在我我们们再再来来看看一一个个关关于于相相同同类类型型资资源源共共享享的的死死锁锁例例子子，假假设设有有一一类类可可再再使使用用资资源源R，例例如如主主存存或或外外存存，它它包包含含有有m个个页页面面或或扇扇区区，由由n个个进进程程P1，P2，Pn（2mn）共共享享。假假定定每每个个进进程程按按右右图图顺顺

45、序序申申请和释放页面（或扇区）：请和释放页面（或扇区）：下一页下一页分析：分析：这里每次申请和释放只涉及这里每次申请和释放只涉及R的一个分的一个分配单元（页或扇区）。因此，当把所有单元全配单元（页或扇区）。因此，当把所有单元全部分配完毕时，便很容易发生死锁；占有部分配完毕时，便很容易发生死锁；占有R的的单元的所有进程（前单元的所有进程（前m个进程）会永远阻塞在个进程）会永远阻塞在第二次申请上，而有些进程（第二次申请上，而有些进程（nm个进程）类个进程）类似地会阻塞在它们的第一次申请上，在图似地会阻塞在它们的第一次申请上，在图3.12中说明了中说明了n3，m2时这种系统的状态，这类时这种系统的状

46、态，这类死锁是相当普遍的。死锁是相当普遍的。下一页下一页图图3.12同类资源共享时的死锁现象同类资源共享时的死锁现象下一页下一页产生死锁有四个必要条件：产生死锁有四个必要条件：产生死锁有四个必要条件：产生死锁有四个必要条件：（1）互斥条件。）互斥条件。（2）不剥夺条件。）不剥夺条件。（3）请求和保持条件。）请求和保持条件。（4）环路等待条件。）环路等待条件。返回本节目录返回本节目录3.8.2预防死锁预防死锁 1破坏破坏“请求与保持条件请求与保持条件”2破坏环路条件破坏环路条件 3资源受控动态分配资源受控动态分配 1破坏破坏“请求与保持条件请求与保持条件”这这种种方方法法的的基基本本思思想想是是

47、：每每个个进进程程在在运运行行之之前前，必必须须预预先先提提出出自自己己所所要要使使用用的的全全部部资资源源，调调度度程程序序在在该该进进程程所所需需要要的的资资源源末末得得到到满满足足之之前前，不不让让它它们们投投入入运运行行，并并且且当当资资源源一一旦旦分分配配给给某某个个进进程程之之后后，那那么么在在该该进进程程的的整整个个运运行行期期间间相相应应资资源源一一直直被被它它占占有有，这这就就破破坏坏了了产产生生死死锁锁的的请请求求与与保保持持条件。条件。下一页下一页2破坏环路条件破坏环路条件 这种方法的基本思想是：对系统提供的每一项资源，由系这种方法的基本思想是：对系统提供的每一项资源，由

48、系统设计者将它们按类型进行线性排队，并赋予不同的序号。统设计者将它们按类型进行线性排队，并赋予不同的序号。例如，设卡片输入机为例如，设卡片输入机为1，打印机为，打印机为2，磁带机为，磁带机为3，磁盘，磁盘机为机为4，。所有的进程都只能严格地按照编号递增。所有的进程都只能严格地按照编号递增（或递减）的次序去请求资源，亦即，只有低编号的资源（或递减）的次序去请求资源，亦即，只有低编号的资源要求满足后，才能对高编号资源提出要求；释放资源时，要求满足后，才能对高编号资源提出要求；释放资源时，应按编号递减的次序进行。由此可以看出，对资源请求采应按编号递减的次序进行。由此可以看出，对资源请求采取了这种限制

49、之后，所形成的进程取了这种限制之后，所形成的进程资源图不可能再产生资源图不可能再产生环路。如图环路。如图3.13所示所示.下一页下一页图图3.13资资源源申申请请和和释释放放顺顺序序图图下一页下一页3资源受控动态分配资源受控动态分配 为了避免死锁发生，操作系统必须根据预先掌握为了避免死锁发生，操作系统必须根据预先掌握的关于资源用法的信息控制资源分配，使得共同的关于资源用法的信息控制资源分配，使得共同进展路径的下一步不致于进入危险区，即只要有进展路径的下一步不致于进入危险区，即只要有产生死锁的可能性，就避免把一种资源分配给一产生死锁的可能性，就避免把一种资源分配给一个进程。个进程。返回本节目录返

50、回本节目录3.8.3发现死锁发现死锁 假假定定系系统统有有n个个进进程程P1，P2，Pn和和Pm种种类类型型资资源源Rl，R2，Rm。.建建立立资资源源分分配配表表S和和进进程程等等待待表表W，分分别别如如表表3.1和和表表3.2所所示示，其其中中aij表表示示分分配配给给进进程程Pi的的资资源源Rj的的数数目目，bij表表示示进进程程Pi请请求求资资源源Rj的的数数目目。另另外外为为每每一一个个进进程程设设置置一一个个等等待待资资源源计计数数器器C1，C2，Cn，它它们们表表示示引引起起相相应应进进程程被被阻阻塞塞的的资资源源数数目目，将将末末阻阻塞塞的的进进程程组组成成一一个个表表L（或或