1、第第3章章 进程管理进程管理n3.1 引言引言n3.2 进程的引入和定义进程的引入和定义n3.3 进程的状态和进程控制块进程的状态和进程控制块n3.4 进程控制进程控制n3.5 线程的基本概念线程的基本概念n3.6 进程调度进程调度n3.7 进程通信进程通信n3.8 死锁问题死锁问题本章学习目标本章学习目标n进程的概念进程的概念n进程的实体、状态及状态的演变进程的实体、状态及状态的演变n进程的控制与调度进程的控制与调度n进程之间的关系协调进程之间的关系协调n进程的通信进程的通信n死锁问题及解决死锁问题及解决3.1 引言引言n处理机管理是操作系统的基本管理功能之一，它处理机管理是操作系统的基本管
2、理功能之一，它所关心的是处理机的分配问题。也就是说把所关心的是处理机的分配问题。也就是说把CPU（中央处理机）的使用权分给某个程序，通常把中央处理机）的使用权分给某个程序，通常把这个正准备进入内存的程序称为作业，当这个作这个正准备进入内存的程序称为作业，当这个作业进入内存后我们把它称为进程。处理机管理分业进入内存后我们把它称为进程。处理机管理分为作业管理和进程管理两个阶段去实现处理机的为作业管理和进程管理两个阶段去实现处理机的分配，常常又把直接实行处理机时间分配的进程分配，常常又把直接实行处理机时间分配的进程调度工作作为处理机管理的主要内容。调度工作作为处理机管理的主要内容。n进程管理的主要功
3、能是把处理机分配给进程以及进程管理的主要功能是把处理机分配给进程以及协调各个进程之间的相互关系。它是由进程调度协调各个进程之间的相互关系。它是由进程调度程序和进程控制（控制进程状态转换）程序这两程序和进程控制（控制进程状态转换）程序这两部分内容组成的。部分内容组成的。返回首页返回首页3.2 进程的引入和定义进程的引入和定义n3.2.1 进程的引入进程的引入n3.2.2 进程的定义进程的定义 返回首页返回首页3.2.1 进程的引入进程的引入n1程序的顺序执行及其特性程序的顺序执行及其特性n2资源共享资源共享n3程序的并发执行及其特性程序的并发执行及其特性1程序的顺序执行及其特性程序的顺序执行及其
4、特性图图3.1表示每次仅能调度一个用户作业进行操作的先表示每次仅能调度一个用户作业进行操作的先后次序。输入、计算和打印输出工作只能串行执后次序。输入、计算和打印输出工作只能串行执行，我们可以把程序的执行过程看作是一系列状行，我们可以把程序的执行过程看作是一系列状态转变过程，每执行一个操作，系统就从一种状态转变过程，每执行一个操作，系统就从一种状态变成另一种状态。图中态变成另一种状态。图中I表示输入操作，表示输入操作，P表示处表示处理操作，理操作，O表示输出操作。表示输出操作。图图3.1 顺序处理操作的先后次序顺序处理操作的先后次序n由上述顺序程序的执行情况可以看出，一切顺序执行的程序由上述顺序
5、程序的执行情况可以看出，一切顺序执行的程序都具有下列特性：都具有下列特性：n（1）顺序性。程序在处理机上执行时，其操作只能严格地）顺序性。程序在处理机上执行时，其操作只能严格地按照所规定的顺序执行，后继操作只有在前一操作执行完毕按照所规定的顺序执行，后继操作只有在前一操作执行完毕之后方能执行，否则就会发生程序逻辑错误。之后方能执行，否则就会发生程序逻辑错误。n（2）资源独占。程序在执行过程中独占全部资源，资源状）资源独占。程序在执行过程中独占全部资源，资源状态的改变只与程序本身有关，而与外界环境无关。态的改变只与程序本身有关，而与外界环境无关。n（3）结果的无关性。第一，指程序执行的结果与其执
6、行速）结果的无关性。第一，指程序执行的结果与其执行速度无关。第二，是指只要程序的初始条件不变，当重复执行度无关。第二，是指只要程序的初始条件不变，当重复执行时，一定能得到相同的结果。时，一定能得到相同的结果。2资源共享资源共享操作系统是用来实现对计算机资源进行管理的一个操作系统是用来实现对计算机资源进行管理的一个大型系统程序，其基本特征之一就是资源共享。大型系统程序，其基本特征之一就是资源共享。这里的资源就是指计算机处理一个任务或一个作这里的资源就是指计算机处理一个任务或一个作业时的所有硬设备（处理机、内存、外存、输入业时的所有硬设备（处理机、内存、外存、输入/输出设备等）和软设备（文件、程序
7、、数据、信输出设备等）和软设备（文件、程序、数据、信息等）的总称。所谓资源共享，就是指计算机中息等）的总称。所谓资源共享，就是指计算机中并发执行的多个程序交替使用计算机硬件和软件并发执行的多个程序交替使用计算机硬件和软件资源。资源。操作系统提供了两种实现资源共享的方法操作系统提供了两种实现资源共享的方法。（1）由操作系统统一管理和分配。）由操作系统统一管理和分配。（2）由进程自行使用。）由进程自行使用。I1P1O1I2P2O2I3P3O3作作业业1图3.2 并行计算的先后次序3程序的并发执行及其特性程序的并发执行及其特性n在大多数计算问题中，仅要求操作在时间上是部在大多数计算问题中，仅要求操作
8、在时间上是部分有序的。有些操作必须在其他操作之后执行，分有序的。有些操作必须在其他操作之后执行，另外有些操作却可以并行地执行。如图另外有些操作却可以并行地执行。如图3.2所示，所示，其先后次序是：其先后次序是：I1先于先于P1和和I2；P1先于先于O1、P2和和I3；O1先于先于O2，P3部分有序使某些操作的并行部分有序使某些操作的并行执行成为可能，如执行成为可能，如I2和和P1，I3，P2与与O1等操作的执等操作的执行可以在时间上互相重叠。行可以在时间上互相重叠。n通常，程序的制约方式有如下两种。通常，程序的制约方式有如下两种。n（1）间接制约方式。）间接制约方式。n（2）直接制约方式。）直
9、接制约方式。n无论是操作系统自身的程序还是用户程序无论是操作系统自身的程序还是用户程序，通常总是存在一些相对独立、但又能并，通常总是存在一些相对独立、但又能并发执行的程序段。发执行的程序段。n为了合理利用系统资源，更好地发挥各种为了合理利用系统资源，更好地发挥各种资源的效益，使各种物理设备之间的时间资源的效益，使各种物理设备之间的时间性限制条件减少到最低限度，最大限度地性限制条件减少到最低限度，最大限度地提高系统的效率，因而引出了多道程序方提高系统的效率，因而引出了多道程序方法。其实质是减少程序的顺序性，提高系法。其实质是减少程序的顺序性，提高系统的并行性。统的并行性。返回本节返回本节3.2.
10、2 进程的定义进程的定义n。进程是现代操作系统的一个基本概念，是并发。进程是现代操作系统的一个基本概念，是并发程序出现后出现的一个重要概念，它是指程序在程序出现后出现的一个重要概念，它是指程序在一个数据集合上运行的过程，是系统进行资源分一个数据集合上运行的过程，是系统进行资源分配和调度运行的一个独立单位，有时也称为活动配和调度运行的一个独立单位，有时也称为活动、路径或任务。、路径或任务。n进程，作为程序执行的过程，至少有两个方面的进程，作为程序执行的过程，至少有两个方面的性质：一是它的活动性，即进程是动态变化的，性质：一是它的活动性，即进程是动态变化的，且总有一个从创建到消亡的过程；二是它的并
11、发且总有一个从创建到消亡的过程；二是它的并发性，即多道程序中每个进程的执行过程，总是与性，即多道程序中每个进程的执行过程，总是与其他执行过程并发执行的。其他执行过程并发执行的。n进程与程序的区别和相互关系进程与程序的区别和相互关系：n（1）动态性和静态性。）动态性和静态性。n（2）从结构上看每个进程的实体都是由程序段和相）从结构上看每个进程的实体都是由程序段和相应的数据段两部分构成的，这一特征与程序的含义相应的数据段两部分构成的，这一特征与程序的含义相近。近。n（3）一个进程可以涉及到一个或几个程序的执行）一个进程可以涉及到一个或几个程序的执行。n（4）并发性。）并发性。n（5）进程具有创建其
12、他进程的功能。）进程具有创建其他进程的功能。n（6）操作系统中的每一个程序都是在一个进程现场）操作系统中的每一个程序都是在一个进程现场中运行的。中运行的。n进程通常分为两类，一类是系统进程，另一类是用进程通常分为两类，一类是系统进程，另一类是用户进程。它们的区别是：户进程。它们的区别是：n（1）系统进程是操作系统用来管理系统资源并行活）系统进程是操作系统用来管理系统资源并行活动的并发软件。动的并发软件。n（2）系统进程之间的关系由操作系统自己负责。）系统进程之间的关系由操作系统自己负责。n（3）系统进程直接管理有关的软、硬设备的活动。）系统进程直接管理有关的软、硬设备的活动。n（4）在进程调度
13、中，系统进程的优先级高于用户进）在进程调度中，系统进程的优先级高于用户进程。程。返回本节返回本节3.3 进程的状态和进程控制块进程的状态和进程控制块n3.3.1 进程的状态及状态变化图进程的状态及状态变化图n3.3.2 进程的结构、进程控制块及组织方式进程的结构、进程控制块及组织方式 返回首页返回首页3.3.1 进程的状态及状态变化图进程的状态及状态变化图n（1）运行状态：进程正在处理机上运行的状态，）运行状态：进程正在处理机上运行的状态，该进程已获得必要的资源，也获得了处理机，用该进程已获得必要的资源，也获得了处理机，用户程序正在处理机上运行。户程序正在处理机上运行。n（2）阻塞状态：进程等
14、待某种事件完成（例如，）阻塞状态：进程等待某种事件完成（例如，等待输入等待输入/输出操作的完成）而暂时不能运行的状输出操作的完成）而暂时不能运行的状态，处于该状态的进程不能参加竞争处理机，此态，处于该状态的进程不能参加竞争处理机，此时，即使分配给它处理机，它也不能运行。时，即使分配给它处理机，它也不能运行。n（3）就绪状态：该进程运行所需的一切条件都得）就绪状态：该进程运行所需的一切条件都得到满足，但因处理机资源个数少于进程个数，所到满足，但因处理机资源个数少于进程个数，所以该进程不能运行，而必须等待分配处理机资源以该进程不能运行，而必须等待分配处理机资源，一旦获得处理机就立即投入运行。，一旦
15、获得处理机就立即投入运行。运行运行就绪就绪阻塞阻塞进程因某事件（如等待进程因某事件（如等待I/O完完成）变成阻塞状态成）变成阻塞状态某事件被解除某事件被解除（I/O完成）完成）时间片已时间片已用完用完进程调度程序把处理进程调度程序把处理机分配给进程机分配给进程（1）（2）（3）（4）图图3.3 典型的进程状态演变图典型的进程状态演变图n在具有挂起和激活的系统中，又增加了两种基本在具有挂起和激活的系统中，又增加了两种基本的进程状态：静止就绪和静止阻塞。的进程状态：静止就绪和静止阻塞。（1）静止就）静止就绪：它是活动就绪进程由其自身或其他进程调用绪：它是活动就绪进程由其自身或其他进程调用挂起原语而
16、进入的一种状态。处于静止就绪状态挂起原语而进入的一种状态。处于静止就绪状态的进程没有资格争用的进程没有资格争用CPU，只有其他进程调用激只有其他进程调用激活原语将其激活才行。活原语将其激活才行。n（2）静止阻塞：它是活动阻塞进程由其自身或其）静止阻塞：它是活动阻塞进程由其自身或其他进程调用挂起原语而进入的一种状态。处于静他进程调用挂起原语而进入的一种状态。处于静止阻塞状态的进程，在其挂起期间并不影响其等止阻塞状态的进程，在其挂起期间并不影响其等待事件的发生。图待事件的发生。图3.4是具有静止状态的进程状态是具有静止状态的进程状态变迁图。变迁图。运行活动就绪活动阻塞进程因某事件（如等待I/O完成
17、）变成阻塞状态某事件被解除（如I/O完成）时间片已用完进程调度程序把处理机分配给进程静止阻塞静止就绪挂起挂起激活激活某事件被解除（如I/O完成）创建图图3.4 具有静止状态的进程状态变迁图具有静止状态的进程状态变迁图返回本节返回本节3.3.2 进程的结构、进程控制块及组织方式进程的结构、进程控制块及组织方式n1进程的结构进程的结构n进程都是由一系列操作（动作）所组成，通过这进程都是由一系列操作（动作）所组成，通过这些操作来完成其任务。因此，不同的进程，其内些操作来完成其任务。因此，不同的进程，其内部操作也不相同。在操作系统中，描述一个进程部操作也不相同。在操作系统中，描述一个进程除了需要程序和
18、私有数据之外，最主要的是需要除了需要程序和私有数据之外，最主要的是需要一个与动态过程相联系的数据结构，该数据结构一个与动态过程相联系的数据结构，该数据结构用来描述进程的外部特性（名字、状态等）以及用来描述进程的外部特性（名字、状态等）以及与其他进程的联系（通信关系）等信息，该数据与其他进程的联系（通信关系）等信息，该数据结构称为进程控制块（结构称为进程控制块（PCB，Process Control Block）。）。PCB程程序序段段私有私有数据块数据块图图3.5 进程的结构进程的结构n2进程控制块进程控制块PCB及组织方式及组织方式n（1）进程控制块）进程控制块PCBn进程控制块跟踪程序执行
19、过程中的状态，它们表进程控制块跟踪程序执行过程中的状态，它们表达了进程在当前时刻的状态以及它与其他进程和达了进程在当前时刻的状态以及它与其他进程和资源的关系。资源的关系。n进程控制块是进程存在的标志，当系统或父进程进程控制块是进程存在的标志，当系统或父进程创建一个进程时，实际上就是为其建立一个进程创建一个进程时，实际上就是为其建立一个进程控制块。控制块。n进程控制块不但指出了进程的名字，而且也标志进程控制块不但指出了进程的名字，而且也标志出程序和数据集合的物理位置出程序和数据集合的物理位置。进程名进程名当前状态当前状态优先数优先数现场保留区现场保留区指示处于同一状态进程的链指针指示处于同一状态
20、进程的链指针资源清单资源清单进程起始地址进程起始地址家族关系家族关系其他其他图图3.6 进程控制块的基本内容进程控制块的基本内容n（2）进程控制块）进程控制块PCB的组织方式的组织方式 n1）线性表方式：不论进程的状态如何，将所有的）线性表方式：不论进程的状态如何，将所有的PCB连续地存放在内存的系统区。这种方式适用于连续地存放在内存的系统区。这种方式适用于系统中进程数目不多的情况。系统中进程数目不多的情况。n 2）索引表方式：该方式是线性表方式的改进，系）索引表方式：该方式是线性表方式的改进，系统按照进程的状态分别建立就绪索引表、阻塞索统按照进程的状态分别建立就绪索引表、阻塞索引表等。引表等
21、。n3）链接表方式：系统按照进程的状态将进程的）链接表方式：系统按照进程的状态将进程的PCB组成队列，从而形成就绪队列、阻塞队列、运组成队列，从而形成就绪队列、阻塞队列、运行队列等。行队列等。返回本节返回本节3.4 进程控制进程控制n3.4.1 原语原语n3.4.2 进程控制原语进程控制原语 返回首页返回首页3.4.1 原语原语n原语通常由若干条指令所组成，用来实现原语通常由若干条指令所组成，用来实现某个特定的操作。通过一段不可分割的或某个特定的操作。通过一段不可分割的或不可中断的程序实现其功能。原语是操作不可中断的程序实现其功能。原语是操作系统核心，它不是由进程而是由一组程序系统核心，它不是
22、由进程而是由一组程序模块所组成，是操作系统的一个组成部分模块所组成，是操作系统的一个组成部分，它必须在管态（一种机器状态，管态下，它必须在管态（一种机器状态，管态下执行的程序可以执行特权和非特权两类指执行的程序可以执行特权和非特权两类指令，通常把它定义为操作系统的状态）下令，通常把它定义为操作系统的状态）下执行，并且常驻内存，而个别系统有一部执行，并且常驻内存，而个别系统有一部分不在管态下运行。分不在管态下运行。图图3.7 进程家族示例进程家族示例返回本节返回本节3.4.2 进程控制原语进程控制原语n1创建原语创建原语n2撤消原语撤消原语n3阻塞原语阻塞原语n4唤醒原语唤醒原语n5挂起原语挂起
23、原语n6激活原语激活原语返回本节返回本节3.5 线程的基本概念线程的基本概念n3.5.1 线程的引入线程的引入n3.5.2 线程与进程的关系线程与进程的关系 n3.5.3 线程的类型线程的类型 返回首页返回首页3.5.1 线程的引入线程的引入n（1）创建进程。系统在创建进程时，必须为之分配）创建进程。系统在创建进程时，必须为之分配其所必需的、除处理机以外的所有资源。如内存空其所必需的、除处理机以外的所有资源。如内存空间、间、I/O设备以及建立相应的设备以及建立相应的PCB结构。结构。n（2）撤消进程。系统在撤消进程时，又必须先对这）撤消进程。系统在撤消进程时，又必须先对这些资源进行回收操作，然
24、后再撤消些资源进行回收操作，然后再撤消PCB结构。结构。n（3）进程切换。在对进程进行切换时，由于要保留）进程切换。在对进程进行切换时，由于要保留当前进程的当前进程的CPU环境和设置新选中进程的环境和设置新选中进程的CPU环境环境，为此需花费不少处理机时间。，为此需花费不少处理机时间。返回本节返回本节3.5.2 线程与进程的关系线程与进程的关系n1调度调度n2并发性并发性n3拥有资源拥有资源n4系统开销系统开销返回本节返回本节3.5.3 线程的类型线程的类型n1线程的调度与切换速度线程的调度与切换速度n2系统功能调用系统功能调用n3线程执行时间线程执行时间n线程已在许多系统中实现，但实现的方式
25、线程已在许多系统中实现，但实现的方式并不完全相同。在有的系统中，特别是一并不完全相同。在有的系统中，特别是一些数据库管理系统如些数据库管理系统如Informix，实现的是用实现的是用户级线程（户级线程（User-Level-Threads），），这种线这种线程不依赖于内核。而另一些系统（如程不依赖于内核。而另一些系统（如Mach和和OS/2操作系统）实现的是内核支持线程操作系统）实现的是内核支持线程（Kernel-Supported-Threads），），这种线这种线程依赖于内核。还有一些系统如程依赖于内核。还有一些系统如Solaris操操作系统，则同时实现了这两种类型的线程作系统，则同时实现
26、了这两种类型的线程。返回本节返回本节3.6 进程调度进程调度n3.6.1 进程调度的职能进程调度的职能n3.6.2 进程调度所用的主要数据结构进程调度所用的主要数据结构n3.6.3 进程调度的方式进程调度的方式n3.6.4 进程调度算法进程调度算法 n3.6.5 综合的调度策略综合的调度策略调度用的进程状调度用的进程状态切换图态切换图返回首页返回首页3.6.1 进程调度的职能进程调度的职能n（1）记录系统中所有进程的有关情况。）记录系统中所有进程的有关情况。n（2）确定分配处理机的原则。）确定分配处理机的原则。n（3）分配处理机给进程。）分配处理机给进程。n（4）从进程收回处理机。）从进程收回
27、处理机。n引起进程调度的原因不仅与操作系统的类型有着引起进程调度的原因不仅与操作系统的类型有着密切的关系，而且还与下列因素有关：正在运密切的关系，而且还与下列因素有关：正在运行的进程运行完毕；运行中的进程要求行的进程运行完毕；运行中的进程要求I/O；执行某种原语操作；一个比正在运行进程优先执行某种原语操作；一个比正在运行进程优先数更高的进程申请运行（在可剥夺调度方式下）数更高的进程申请运行（在可剥夺调度方式下）；分配给运行进程的时间片已经用完等。；分配给运行进程的时间片已经用完等。返回本节返回本节3.6.2 进程调度所用的主要数据结构进程调度所用的主要数据结构n通过通过3.3.2节的学习我们知
28、道操作系统对进节的学习我们知道操作系统对进程的管理具体体现在对进程的程的管理具体体现在对进程的PCB的管理的管理。同时也了解到进程控制块。同时也了解到进程控制块PCB的几种组的几种组织方式：线性表方式、索引表方式和链接织方式：线性表方式、索引表方式和链接表方式。一般情况下，进程控制块表方式。一般情况下，进程控制块PCB的的组织方式采用的是链接表方式。因此，在组织方式采用的是链接表方式。因此，在进程调度中所用的主要数据结构是队列（进程调度中所用的主要数据结构是队列（PCB的链接方式在这里就不详细介绍了，的链接方式在这里就不详细介绍了，若需要请详见若需要请详见3.3.2节）节）返回本节返回本节3.
29、6.3 进程调度的方式进程调度的方式n进程调度的方式可分为非剥夺式和剥夺式。进程调度的方式可分为非剥夺式和剥夺式。n剥夺式调度是指当系统按照某种原则发现一个比剥夺式调度是指当系统按照某种原则发现一个比现运行进程更合适、更应该占用现运行进程更合适、更应该占用CPU的进程时，的进程时，系统将强迫处于运行状态的进程将系统将强迫处于运行状态的进程将CPU的使用权的使用权交给这个更适合的进程。交给这个更适合的进程。n非剥夺式调度是指一旦某个进程占用了非剥夺式调度是指一旦某个进程占用了CPU，除除非是由于它自身原因自动放弃非是由于它自身原因自动放弃CPU，否则它将一否则它将一直运行下去直到完成。直运行下去
30、直到完成。返回本节返回本节3.6.4 进程调度算法进程调度算法n1先来先服务先来先服务n2轮转调度轮转调度n3分级轮转法分级轮转法n4优先数法优先数法n进程调度的主要问题就是采用某种算法合进程调度的主要问题就是采用某种算法合理有效地把处理机分配给进程，其调度算理有效地把处理机分配给进程，其调度算法应尽可能提高资源的利用率，减少处理法应尽可能提高资源的利用率，减少处理机的空闲时间。对于用户作业采用较合理机的空闲时间。对于用户作业采用较合理的平均响应时间，以及尽可能地增强处理的平均响应时间，以及尽可能地增强处理机的处理能力，避免有些作业长期不能投机的处理能力，避免有些作业长期不能投入运行。这些入运
31、行。这些“合理的原则合理的原则”往往是互相往往是互相制约的，甚至是矛盾的，难以全部达到要制约的，甚至是矛盾的，难以全部达到要求。求。n进程的优先数是根据什么条件确定的，这是一个进程的优先数是根据什么条件确定的，这是一个很重要的问题，通常应考虑如下几个因素：很重要的问题，通常应考虑如下几个因素：n（1）进程类型。根据不同类型的进程确定其优先）进程类型。根据不同类型的进程确定其优先数。数。n（2）运行时间。通常规定进程优先数与进程所需）运行时间。通常规定进程优先数与进程所需运行时间成反比，即运行时间长的（一般占用内运行时间成反比，即运行时间长的（一般占用内存也较多）大作业，分配给它的优先数就越低，
32、存也较多）大作业，分配给它的优先数就越低，反之则越高。反之则越高。n（3）作业的优先数。根据作业的优先数来决定其）作业的优先数。根据作业的优先数来决定其所属进程的优先数。所属进程的优先数。n（4）动态优先数。）动态优先数。n时间片的长短由如下四个因素决定：时间片的长短由如下四个因素决定：n（1）系统的响应时间。当进程数目一定时，时间）系统的响应时间。当进程数目一定时，时间片的长短直接影响系统的响应时间。片的长短直接影响系统的响应时间。n（2）就绪队列中进程的数目。这与前面的问题正）就绪队列中进程的数目。这与前面的问题正好相反，即当系统对响应时间要求一定时，时间好相反，即当系统对响应时间要求一定
33、时，时间片长则就绪队列中进程数应少，反之亦然。片长则就绪队列中进程数应少，反之亦然。n（3）进程状态转换（即进程由就绪到运行，由运）进程状态转换（即进程由就绪到运行，由运行到就绪）的时间开销。行到就绪）的时间开销。n（4）计算机本身的处理能力。执行速度和可运行）计算机本身的处理能力。执行速度和可运行作业的道数。作业的道数。返回本节返回本节3.6.5 综合的调度策略综合的调度策略调度用的进程状调度用的进程状态切换图态切换图n我们采用进程状态我们采用进程状态切换切换图来帮助大家进一步了解图来帮助大家进一步了解进程调度算法。以分级轮转法为例，将就绪进程进程调度算法。以分级轮转法为例，将就绪进程分成高
34、优先数和低优先数两个队列。如果进程运分成高优先数和低优先数两个队列。如果进程运行中超过了规定的时间片就进入低优先数队列，行中超过了规定的时间片就进入低优先数队列，而而I/O操作完成的进程，即由阻塞状态进入高优先操作完成的进程，即由阻塞状态进入高优先数就绪队列。如图数就绪队列。如图3.8所示，其调度算法是：首先所示，其调度算法是：首先从高优先就绪队列中选择一个进程来运行，如果从高优先就绪队列中选择一个进程来运行，如果在高优先数就绪队列中没有进程，则从低优先数在高优先数就绪队列中没有进程，则从低优先数就绪队列中选择一个进程运行。就绪队列中选择一个进程运行。低优先数低优先数就绪就绪运行运行高优先数高
35、优先数就绪就绪因等待因等待I/O而而阻塞阻塞首先选择首先选择I/O完成完成其次选其次选择择超过时间超过时间片片请求请求I/O图图3.8 调度用的进程状态切换图调度用的进程状态切换图返回本节返回本节3.7 进程通信进程通信n3.7.1 进程互斥进程互斥n3.7.2 互斥用的硬件机制互斥用的硬件机制n3.7.3 进程同步进程同步n3.7.4 用信号量实现进程同步用信号量实现进程同步 n3.7.5 两个经典的同步两个经典的同步/互斥问题互斥问题 n3.7.6 结构化的同步结构化的同步/互斥机制互斥机制管程管程n3.7.7 进程的通信方式之二进程的通信方式之二消息缓冲消息缓冲 返回首页返回首页3.7.
36、1 进程互斥进程互斥n几个进程若共享同一临界资源，它们必须以互斥几个进程若共享同一临界资源，它们必须以互斥的方式使用这个临界资源，即当一个进程正在使的方式使用这个临界资源，即当一个进程正在使用临界资源且尚未使用完毕时，则其他进程必须用临界资源且尚未使用完毕时，则其他进程必须推迟对该资源的进一步操作，在当前进程的使用推迟对该资源的进一步操作，在当前进程的使用完成之前，不能从中插进去使用这个临界资源，完成之前，不能从中插进去使用这个临界资源，否则将会造成信息混乱和操作出错。否则将会造成信息混乱和操作出错。n系统中同时存在有许多进程，它们共享各种资源系统中同时存在有许多进程，它们共享各种资源，然而有
37、些资源每次只能让一个进程所使用。，然而有些资源每次只能让一个进程所使用。n临界区是一个进程访问临界资源的那段程序代码临界区是一个进程访问临界资源的那段程序代码。有了临界资源和临界区的概念，进程间的互斥。有了临界资源和临界区的概念，进程间的互斥可以描述为禁止两个或两个以上的进程同时进入可以描述为禁止两个或两个以上的进程同时进入访问同一临界资源的临界区。访问同一临界资源的临界区。返回本节返回本节3.7.2 互斥用的硬件机制互斥用的硬件机制下面我们不局限于某特定系统，定义下面我们不局限于某特定系统，定义TS指令为：指令为：function TS（var lock：boolean）：）：boolean
38、；begin TS：=lock；lock：=true；end用用TS指令实现互斥的循环进程可描述如下：指令实现互斥的循环进程可描述如下：repeat while TS(lock)do skip；critical section；lock：=false；remainder section；until false返回本节返回本节3.7.3 进程同步进程同步n并发执行的多个进程，看起来好像是异步前进的并发执行的多个进程，看起来好像是异步前进的，彼此之间都可以互不相关的速度向前推进，而，彼此之间都可以互不相关的速度向前推进，而实际上每一个进程在其运行过程中并非相互隔绝实际上每一个进程在其运行过程中并非
39、相互隔绝。一方面它们相互协作以达到运行用户作业所预。一方面它们相互协作以达到运行用户作业所预期的目的，另一方面它们又相互竞争使用系统中期的目的，另一方面它们又相互竞争使用系统中有限的资源。有限的资源。n两个并行的进程两个并行的进程A、B，如果当如果当A进行某个操作时进行某个操作时，B不能做这一操作，进程间的这种限制条件称为不能做这一操作，进程间的这种限制条件称为进程互斥，引起资源不可共享的原因：一是资源进程互斥，引起资源不可共享的原因：一是资源的物理特性所致；二是某些资源如果同时被几个的物理特性所致；二是某些资源如果同时被几个进程使用，则一个进程的动作可能会干扰其他进进程使用，则一个进程的动作
40、可能会干扰其他进程的动作。程的动作。返回本节返回本节3.7.4 用信号量实现进程同步用信号量实现进程同步n1lock和和unlock大部分同步方案均采用某个物理实体（如锁、信号大部分同步方案均采用某个物理实体（如锁、信号灯等）实现通信，进程通信原语中关锁（灯等）实现通信，进程通信原语中关锁（lock）和和开锁（开锁（unlock）是最简单的原语。在这两个原语中是最简单的原语。在这两个原语中设置一个公共变量设置一个公共变量x代表某个临界资源的状态。代表某个临界资源的状态。进程使用临界资源必须作如下三个不可分割的操作进程使用临界资源必须作如下三个不可分割的操作：（1）检查检查x的值。的值。（2）进
41、入临界区，访问临界区资源。进入临界区，访问临界区资源。（3）释放临界区资源，置）释放临界区资源，置x为为0（开锁）。（开锁）。Y退出退出C并开锁并开锁置置X=0进入临界区进入临界区C关锁则置关锁则置X=1测试测试 X=0?返回继续测试返回继续测试N图图3.9 开锁和关锁程序流程图开锁和关锁程序流程图n2P/V操作操作n设设s1、s2初值为初值为0，用，用PV操作实现上述操作实现上述同步模型如下：同步模型如下：返回本节返回本节3.7.5 两个经典的同步两个经典的同步/互斥问题互斥问题n1生产者与消费者问题生产者与消费者问题nDijkstra把广义同步问题抽象成一种把广义同步问题抽象成一种“生产者
42、与消生产者与消费者问题费者问题”（Producer-consumer-relationship）的的抽象模型。抽象模型。n2读者与写者问题读者与写者问题n一个数据对象（比如一个文件或记录）若被多个一个数据对象（比如一个文件或记录）若被多个并发进程所共享，且其中一些进程只要求读该数并发进程所共享，且其中一些进程只要求读该数据对象的内容，而另一些进程则要求修改它，对据对象的内容，而另一些进程则要求修改它，对此，可把那些只想读的进程称之为此，可把那些只想读的进程称之为“读者读者”；而；而把要求修改的进程称为把要求修改的进程称为“写者写者”。n下面给出基于环形缓冲区的生产者与消费者关系下面给出基于环形
43、缓冲区的生产者与消费者关系的形式描述，设：的形式描述，设：n（1）公用信号量）公用信号量mutex：初值为初值为1，用于实现临界，用于实现临界区互斥。区互斥。n（2）生产者私用信号量）生产者私用信号量empty：初值为初值为n，指示空指示空缓冲块数目。缓冲块数目。n（3）消费者私用信号量）消费者私用信号量full：初值为初值为0，指示满缓，指示满缓冲块数目。冲块数目。n（4）整型量）整型量i和和j初值均为初值均为0，i指示首空缓冲块序号指示首空缓冲块序号，j指示首满缓冲块序号。指示首满缓冲块序号。Var mutex，empty，full：semaphore;i,j:integer；buffer
44、：array 0n一一1 of item；Procedure producer;生产者进程生产者进程 begin while true do begin produce a product;P(empty);P(mutex);Buffer(i)：Product;i：(i+1)mod n;V(mutex);V(full);end end;procedure consumer;消费者进程消费者进程 begin while true do begin P(full);P(mutex);goods：buffer(j);j：(j+1)mod n;V(mutex);V(empty);Consume a p
45、roduct;end end;beginseminitial;i:j:0;cobeginproducer;consumer;Coendend下面给出读者进程与写者进程的一般结构。下面给出读者进程与写者进程的一般结构。var mutex,wrt:semaphore;readcount:integer;begin seminit;readcount:=0cobeginprocedure reader;beginP(mutex);readcount:=readcount+1;If readcount=1 then P(wrt);V(mutex);reading is performing;P(mut
46、ex);readcount:=readcount-1if readcount=0 then V(wrt);V(mutex);end procedure writer;begin P(wrt);writing is performing;V(wrt);endcoendend;返回本节返回本节3.7.6 结构化的同步结构化的同步/互斥机制互斥机制管程管程n建立管程的基本理由是：由于对临界区的建立管程的基本理由是：由于对临界区的执行分散在各进程中，这样不便于系统对执行分散在各进程中，这样不便于系统对临界资源的控制和管理，也很难发现和纠临界资源的控制和管理，也很难发现和纠正分散在用户程序中的对同步原语
47、的错误正分散在用户程序中的对同步原语的错误使用等问题。为此，应把分散的各同类临使用等问题。为此，应把分散的各同类临界区集中起来。并为每个可共享资源设立界区集中起来。并为每个可共享资源设立一个专门的管程来统一管理各进程对该资一个专门的管程来统一管理各进程对该资源的访问。这样既便于系统管理共享资源源的访问。这样既便于系统管理共享资源，又能保证互斥访问。，又能保证互斥访问。n管程主要由两部分组成：管程主要由两部分组成：n（1）局部于该管程的共享数据，这些数据）局部于该管程的共享数据，这些数据表示了相应资源的状态。表示了相应资源的状态。n（2）局部于该管程的若干过程，每个过程）局部于该管程的若干过程，
48、每个过程完成关于上述数据的某种规定操作。完成关于上述数据的某种规定操作。例如，对并发例如，对并发PASCAL编译程序在编译源程序时，编译程序在编译源程序时，对每一个形如：对每一个形如：monitorname.procedure/functionentryname的调用语句，都将自动保证其按如下方式执行：的调用语句，都将自动保证其按如下方式执行：P(mutex)；执行相应的过程或函数：执行相应的过程或函数：V(mutex)；其中，其中，mutex是关于相应管程的互斥信号灯，初值为是关于相应管程的互斥信号灯，初值为1。n前面我们曾给出了利用信号灯及其前面我们曾给出了利用信号灯及其P、V操作实现的生
49、产者与操作实现的生产者与消费者共享环形缓冲池的同步模型，这里再以环形缓冲池为消费者共享环形缓冲池的同步模型，这里再以环形缓冲池为例，给出环形缓冲池的管程结构。例，给出环形缓冲池的管程结构。monitor ringbuffer;var rbuffer：array0n-1 of item；k,nextempty,nextfull:integer;empty,full:condition;procedure entry put(var product:item);begin if k=n wait(empty);rbuffer nextempty:product;k:=k+1；nextempty:=
50、(nextempty+1)mod n;signal(full);end;procedure entry get(var goods:item);begin if k=0 wait(full);goods:=rbuffer nextfull;k:=k-1;nextfull:=(nextfull+1)mod n;signal(empty);end;begink:=0;nextempty:=0;nextfull:=0;end;n管程管程ringbuffer包含两个局部过程：过程包含两个局部过程：过程put负责执负责执行将数据写入某个缓冲块的操作；过程行将数据写入某个缓冲块的操作；过程get负责执负责
