软件技术基础 (10)处理器管理1

第四章操作系统4.2处理器管理一、基本概念与术语

在多道程序系统中，处理器数小于程序数，于是处理器就在各程序间进行切换，因此在一个处理器上要交叉运行若干道程序。处理器管理就是要解决用户递交的作业何时调入内存，在调入内存的各个作业程序间如何分配处理器，以达到各道程序能协调一致运行，而系统资源又能得到最大程度的利用。

基本概念与术语

★作业和进程

★特权指令、处理器状态

★处理器管理1第四章操作系统4.2处理器管理★作业和进程

⑴作业、作业步作业是用户在一次算题过程中或一个事务处理中要求计算机系统所作工作的集合。一个作业由一系列的作业步组成。一个作业步运行的结果产生下一个作业步所需的文件。例如一个C语言程序要经历编辑、编译、连接、运行四个作业步。2第四章操作系统4.2处理器管理⑵进程和程序在多道程序系统中，多道程序并发运行，为了竞争有限的资源，相互间存在依赖与制约关系，它们在系统中的状态是不断变化的，即时而运行，时而停顿。因此引入新的概念---进程。一旦操作系统接受了某用户的作业，并把它调入内存执行，系统就为此作业创建一个或多个进程。因此进程可以看成是程序的一次执行，即是在指定内存区域中的一组指令序列的执行过程。多个进程可以并发进行，并可能由于各种原因随时中断。

3第四章操作系统4.2处理器管理

从对进程的描述来看，进程既与程序有关，又与程序不同，它们的区别是：①进程是程序的执行，因此属于动态的概念；而程序是一组指令的集合，属于静态的概念。②进程既然是程序的执行，因此它是有生命过程的，进程有诞生（创建进程）和死亡（撤消进程），应此进程的存在是暂时的，而程序的存在是永久的。4第四章操作系统4.2处理器管理

★

特权指令、处理器状态 每个处理器都有自己的指令系统，在多道程序环境中为了保证系统正常工作，将指令系统中的指令分为两类：

1.特权指令：只能由操作系统使用。

2.非特权指令：供一般用户使用。对应两种不同的指令，处理器有两种执行状态。

◆管态：又称主态、执行状态,此时处理器执行特权指令。

◆目态：又称算态、题目状态，此时处理器处于用户执行状态。5第四章操作系统4.2处理器管理★

从Intel80386开始，出于安全性和稳定性的考虑，该系列的CPU可以运行于ring0（0级环）至ring3(3级环)从高到低四个不同的权限级，对数据也提供相应的四个保护级别。运行于较低级别的代码不能随意调用高级别的代码和访问较高级别的数据，只有ring0层的代码才可以对物理硬件直接进行访问。6第四章操作系统4.2处理器管理

★处理器管理

在大型通用系统中，可能有数百个作业等待处理，处理器管理又称处理器调度，就是解决如何从这些作业中挑选一些进入主存运行，又如何在主存各进程间分配处理器。它一般分为两级：作业调度：又称高级调度或宏观调度。它的主要功能是按照某种调度原则，选取某些作业进入内存，为它们分配必要的资源，建立相应的进程，并当作业完成后做好一切善后工作。进程调度：又称低级调度或微观调度。它的主要功能是按照某种调度原则，实现处理器在各进程间的转换。7第四章操作系统4.2处理器管理二、作业调度1.作业状态转换及作业控制块 一个作业从进入系统到运行结束，一般要经历以下四种状态:提交收容执行完成。提交收容完成去分配作业管理设备管理辅存执行内存作业的四种状态8第四章操作系统4.2处理器管理提交收容完成去分配作业管理设备管理辅存执行内存作业的四种状态提交状态：用户向机房提交作业或通过终端键盘将作业输入，其作业所处的状态为提交状态。收容状态：作业的全部信息已经输入外存等待运行，又称为后备状态。9第四章操作系统4.2处理器管理提交收容完成去分配作业管理设备管理辅存执行内存作业的四种状态执行状态：作业被作业调度程序选中进入内存，称为执行状态。完成状态：作业执行完毕，释放其占用的全部资源，准备退出系统。10第四章操作系统4.2处理器管理为了管理和调度作业，系统为每个作业建立一个作业控制块（JCB-JobControlBlock），是作业存在的标志。它详细记录每个作业的有关信息。不同系统的JCB不完全相同，取决于系统对作业调度的要求。主要有：作业名：用户作业的名称。状态：输入/收容/执行。优先数：根据作业的重要程度，由系统或用户确定。运行时间：用户根据经验估计完成本作业所需时间。位置：本作业在外存中的起始地址。11第四章操作系统4.2处理器管理长度：作业的地址空间。外设申请：作业运行时要求的外部设备。所有的JCB可按作业的优先数大小或作业到达系统的时间顺序构成一个作业队列，如下图所示作业名现在状态优先数时间估计位置长度外设申请…指向下一个JCB指针JCB1作业控制块与作业队列JCB2JCBn12第四章操作系统4.2处理器管理2.作业调度的功能按照某种调度算法，从所有处于后备状态的作业队列中挑选作业进入主存。调用存储管理和设备管理程序，为被选中的作业分配内存和外设，做好运行前的准备为选中的作业建立相应的进程。作业运行完毕时回收该作业占用的资源，输出必要的信息，撤消该作业的JCB与相应的进程。13第四章操作系统4.2处理器管理3.作业调度算法

调度算法的考虑因素很多，但这些因素应和主观上的目标一致。通常调度算法应达到的目标为：运行尽可能多的作业使处理器保持忙碌状态使I/O设备得到充分利用对所有作业公平合理上述这些目标往往存在冲突，要想同时满足是不可能的，只能根据需要兼顾某些目标。14第四章操作系统4.2处理器管理考虑的因素越多、算法就越复杂，从而增加系统的开销，对资源的利用反而不利。因此，大多数操作系统往往采用比较简单的调度算法。下面介绍几种常用的作业调度算法：先来先服务算法：这是一种最简单的调度算法。它按作业录入的先后次序建成进行调度。这种算法优先考虑等待时间最长的作业，忽视它要求运行时间的长短。效率低，对短作业不利，容易被大作业垄断。短作业优先调度算法：以每个作业JCB中提供的运行时间为依据，总是选取运行时间最短的作业。对短作业有利，但可能使长作业得不到运行的机会。15第四章操作系统4.2处理器管理

响应比高者优先：是介于先来先服务和短作业优先算法之间的一种折中算法。兼顾了运行时间短和等待时间长的作业。

响应比=作业响应时间/估计运行时间

=1+作业等待时间/作业估计运行时间计算后备作业队列中每个作业的响应比，然后挑选响应比最高的投入运行。它实际上优先考虑短作业，但也兼顾等待时间长的作业。16第四章操作系统4.2处理器管理

优先数调度算法：选取优先数最高作业首先运行.优先数的确定可由用户指定，也可根据作业运行时间的长短和对资源要求的多少来规定。如：每当作业调度程序挑选作业时，要遍访后备队列，为每个作业算出一个优先数，然后根据优先数大小挑选作业。17第四章操作系统4.2处理器管理例题1：在多道操作系统控制下，作业反复运行多次，它的运行时间都相同吗？例题2：现有2道作业同时执行，一道以计算为主，另一道以输入输出为主，怎样赋予作业进程占有处理器的优先级，使作业作业的平均周转周期最短？作业周转时间=作业完成时刻–作业递交时刻

=作业运行时间+作业等待时间18第四章操作系统4.2处理器管理例题3：有5个批处理作业(A,B,C,D,E)几乎同时到达一个计算中心，估计运行的时间分别为2,4,6,8,10分钟，它们的优先数分别为1,2,3,4,5。对下面的每种调度算法，分别计算作业的平均周转时间。(1)最高优先级优先(2)时间片轮转（时间片为2分钟）(3)FIFO（作业到达的顺序为C,D,B,E,A）(4)短作业优先19第四章操作系统4.2处理器管理作业执行次序优先数运行时间等待时间周转时间E510010D481018C361824B242428A122830作业平均周转时间T=22(分钟)(a)优先级调度算法20第四章操作系统4.2处理器管理作业运行时间等待时间周转时间A202B4812C61420D81826E102030作业平均周转时间T=18(分钟)(b)时间片轮转法调度21第四章操作系统4.2处理器管理作业执行次序运行时间等待时间周转时间C606D8614B41418E101828A22830作业平均周转时间T=19.2(分钟)(c)先来先服务法调度22第四章操作系统4.2处理器管理作业执行次序运行时间等待时间周转时间E202D426C6612B81220A102030作业平均周转时间T=14(分钟)(d)短作业优先法调度23第四章操作系统4.2处理器管理三、进程调度当作业管理程序将在用户作业调入内存后，作业即以进程形式出现。进程数目总是大于CPU数目。各进程必将为争夺CPU而竞争，得到CPU的运行，得不到的只有等待。在内存中的多个进程具有不同的状态，他们随着系统运行而不断改变。进程调度的任务就是控制、协调各进程对CPU的竞争，按照一定的调度算法，使某一就绪进程得到CPU，转换成运行状态。

进程是系统并发活动的体现。用动态的观点看，操作系统是进程的动态和并发执行。进程并发执行：在一定时间内系统内2个或2个以上的进程同时处于开始运行但尚未结束的状态，并且次序不是事先确定的。24第四章操作系统4.2处理器管理1.进程的定义进程有很多各式各样的定义，如：

程序在处理机上的运行进程是这样的计算部分，它可以与别的进程并行运行在自身的虚拟地址空间运行的一个单独的程序.一个具有一定独立功能的程序关于某个数据集合的一次运行活动进程既和程序有关，又与程序不同25第四章操作系统4.2处理器管理原来程序的概念已经难以刻画和反映系统中的情况※

程序概念反映不了动态性，系统中的程序实际上是处于不断变化的状态※

程序反映不了系统中的并行特性(运行于不同的集合上，将属于不同的进程)进程的特征：①动态性：进程是程序的执行，进程有生命过程，是短暂的②并发性：多个进程可同存于内存中，能在一段时间内同时

运行③独立性：独立运行的基本单位，独立获得资源和调度的基

本单位完成某个功能的指令的集合26第四章操作系统4.2处理器管理④异步性：各进程按各自独立的不可预知的速度向前推进进程的组成包括程序和数据，以及进程控制块。一个程序可对应多个进程，

一个进程可包含多个程序(调用其他程序，共同组成一个”运行的活动”)2.进程的状态转换进程有三种基本状态：就绪、运行、阻塞

进程在生命消亡前处于且仅处于三种基本状态之一，并且在单处理器系统中，任何时刻只有一个进程处于运行状态，其他进程分别处于就绪和阻塞状态。

不同操作系统设置的进程状态数目不同27第四章操作系统4.2处理器管理（1）就绪状态：进程已具备各种必要的资源，只等待获得CPU。(得到CPU即可运行)（2）运行状态：系统根据调度算法，将CPU分配给某一个就绪进程使之运行，该进程就处于运行状态。当运行的进程由于分配的CPU时间已到或是由于I/O要求，则必须交出CPU就转入就绪或阻塞状态。（3）阻塞(等待)状态：进程在运行中由于要等待I/O设备或发生其它错误时，就转入阻塞状态。待到阻塞原因消除后，重新回到就绪状态。(即使CPU空闲，它也不能运行)进程的三种基本状态：28进程各状态之间转换的示意图状态变化：就绪状态－>运行状态运行状态－>就绪状态运行状态－>阻塞状态阻塞状态－>就绪状态等待－>运行就绪－>等待不具有下列转换：29第四章操作系统4.2处理器管理引起进程状态转换的原因：1)CPU调度：从就绪队列中调度一个进程到CPU上运行，该进程就从就绪状态变为运行状态；与此同时，原运行进程从运行状态变为就绪状态2)进程在运行过程中需要等待某一事件，如等待分配某一资源，等待IO操作完成等。这时进程主动推出CPU，并使自己处于阻塞状态3)进程所等待的事件发生了变化，如I/O完成了，进程就解除阻塞状态，变为就绪状态4)任何一个指定时刻必须且只能处于一种状态。30五状态进程模型

新状态:

一个进程刚刚建立，但尚未将其送入就绪队列时的状态；

终止状态：一个进程已经正常或异常结束，OS已将它从就绪队列移

出，但尚未撤销。31第四章操作系统4.2处理器管理3.进程控制块(PCB)为了刻画进程的动态变化，通常把进程表示为由程序段、私有数据块和进程控制块组成。程序部分描述进程本身所要完成的功能，而“私有数据块”是接受程序规定操作的一组存储单元的内容，是操作的对象。为了描述一个进程和其它进程以及系统资源的关系，以及一个进程在各个不同时期所处的状态，采用了一个与进程相联系的数据块，称为进程控制块（PCB）。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的32第四章操作系统4.2处理器管理PCB中的内容：进程描述信息：

♦进程标识符(processID)，唯一，通常是一个整数

♦进程名，通常基于可执行文件名（不唯一）

♦用户标识符(userID)；进程组关系进程控制信息：♦当前状态

♦优先级(priority)

♦代码执行入口地址

♦程序的外存地址

♦运行统计信息（执行时间、页面调度）33第四章操作系统4.2处理器管理♦进程的队列指针♦进程的消息队列指针所拥有的资源和使用情况：♦虚拟地址空间的现状♦打开文件列表CPU现场保护信息：♦寄存器值（通用、程序计数器PC、状态PSW，地址包括栈指针）♦指向赋予该进程的段/页表的指针34第四章操作系统4.2处理器管理PCB表的组织方式：1)

索引方式：有着相同状态的进程的PCB组织在一个表格中，就绪/运行/等待进程表，系统中有一些固定单元分别指出各表的起始地址;35第四章操作系统4.2处理器管理2)

队列方式：把具有相同状态的所有进程的PCB按优先数排成一个或多个(每个优先级一个)队列采集队列形式时，每个进程的PCB中要增加一个链指针的表目项，以指向队列的下一个进程的PCB地址36第四章操作系统4.2处理器管理PCB的主要作用：记录进程的有关信息标识信息，状态信息，调度信息，通讯信息，已占用资源信息标志进程的存在

操作系统根据系统中是否存在进程的PCB来知道该进程存在与否，PCB是进程存在的具体物理标志和体现，是进程调度的主要数据基。37第四章操作系统4.2处理器管理OS根据PCB来对并发执行的进程，进行控制和管理♦调度前，要从各进程的PCB中知道现行的状态及优先级；♦调度时，根据PCB中保存的CPU状态信息恢复现场，并根据指令和数据的内存地址，找到程序和数据；♦进程执行过程中，当需要与其他进程同步、通信时，也需要访问PCB♦当进程因某种原因暂停执行时，需要保存CPU环境38第四章操作系统Linux中的PCB

在linux中每一个进程都由structtask_struct

数据结构来定义，这就是通常所说的PCB，它相当大。/usr/src/linux-2.4/include/linux/sched.h

...pid_tpid;

进程IDvolatilelong

state;

进程状态unsignedlong

policy;

调度策略(FIFO,roundrobin...)int

prio;

进程优先级structthread_structthread;CPU寄存器状态信息structtask_struct*next_task,*prev_task;

构成一循环的双向链表，通过它可以遍历执行所有的现存进程。...有关详细，参考UnderstandingLinuxKernel--byrtsys.pdf39第四章操作系统Linux中进程信息察看UID

进程属主的用户ID号。PID

进程ID号。

PPID父进程的ID号。

C

进程最近使用CPU的估算。

STIME

进程开始时间,以“小时:分:秒”的形式给出。

TTY

该进程建立时所对应的终端,“?”表示该进程不占用终端。

TIME

报告进程累计使用的CPU时间。CMD

是command(命令)的缩写，往往表示进程所对应的命令名。40第四章操作系统4.2处理器管理P0P1P2P4P5P6P3P7进程控制对系统中全部进程实施有效的管理，即它应具有创建进程、撤消进程、改变进程状态的功能。进程控制一般有原语来实现在树型结构系统中，一个进程能够创建一个或多个进程，前者称为父进程，后者称为子进程。这样就形成了一个进程家族。如下图所示。41第四章操作系统4.2处理器管理原语是机器指令的延伸，由若干条机器指令构成，用以完成某一特定功能的程序段。它与一般过程的区别在于：它们是属于“原子操作

atomicopertation”，即一个操作中的所有动作，要么全做，要么全不做。原语在执行期间是不允许被中断的。常用的进程控制原语♦创建原语♦终止原语♦阻塞原语、唤醒原语42第四章操作系统4.2处理器管理创建进程原语1）申请空白PCB：为新进程分配唯一的标识符，并从PCB集合中索取一空白的PCB2）为新进程分配资源，如内存3）初始化进程控制块：

a)初始化标识符信息：将系统分配的标识符、父进程标识符填入新的PCB；

b)初始化处理器状态信息：使程序计数器指向程序入口地址，栈指针指向栈顶

c)初始化处理器控制信息：设置进程状态和优先级4）设置对应的链接，如把新进程加到就绪队列的链表中43第四章操作系统4.2处理器管理终止进程原语1)根据被终止进程的标识符，从PCB集合中检索出该进程的

PCB，从中读出该进程的状态2)回收进程所占的全部资源3)递归删除其所有子进程，以妨它们成为不可控4)删除PCB5)若删除的是正在运行的进程，则请求重新调度44第四章操作系统4.2处理器管理进程的阻塞与唤醒阻塞：正在执行的进程，当所期待的某一事件尚未出现时，该进程便通过调用阻塞原语（block）将自己阻塞，并插入到具有相同事件的阻塞队列。进程阻塞是进程的自身的一种主动行为。唤醒：当被阻塞进程所期待的事件出现时，如I/O操作完成，则由合作进程调用唤醒原语（wakeup）将其唤醒。

处于阻塞状态的进程是绝不可能叫醒它自己的。45第四章操作系统4.2处理器管理5.线程的引入进程的两个基本属性※进程是一个可拥有资源的基本单位。※进程同时又是一个可独立调度和分派的基本单位。

进程作为一个资源拥有者，在创建、撤消、切换中，系统必须为之付出较大时空开销。1）创建进程：系统在创建进程时，必须为之分配其所必需的、除处理机以外的所有资源。如内存空间、I/O设备以及建立相应的PCB结构46第四章操作系统4.2处理器管理2）撤消进程。系统在撤消进程时，又必须先对这些资源进行回收操作，然后再撤消PCB结构。3）进程切换。在对进程进行切换时，由于要保留当前进程的CPU环境和设置新选中进程的CPU环境，为此需花费不少处理机时间。

由此可见，由于在进程的创建、撤销、切换中，系统必须为之付出较大的时空开销，导致了系统中进程的数量不宜过多，进程切换的频率不宜过高，但这也就限制了并发程度的进一步提高。47第四章操作系统4.2处理器管理

为解决此问题，人们想到将进程的上述两个属性分开，即对作为调度和分派的基本单位，不同时作为独立分配资源的单位；对拥有资源的单位，不对之进行频繁切换。线程因而产生♦在引入线程的OS中，线程是进程中的一个实体，是被系统独立调度和分派的基本单位。♦线程自己基本不拥有系统资源，只拥有少量必不可少的资源：程序计数器、一组寄存器、栈。48第四章操作系统4.2处理器管理♦线程可与同属一个进程的其它线程共享进程所拥有的全部资源。♦一个线程可以创建和撤消另一个线程；同一进程中的多个线程之间可以并发执行。由于线程之间的相互制约，导致了线程在运行过程中也呈现间断性，相应的，线程也同样有就绪、阻塞、执行三种基本状态。49第四章操作系统4.2处理器管理线程与进程的比较：1．调度♦在传统的操作系统中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。在引入线程的系统中，线程是调度和分派的基本单位，而进程是拥有资源的基本单位。♦在同一个进程内线程切换不会产生进程切换，由一个进程内的线程切换到另一个进程内的线程时，将会引起进程切换。

2．并发性

在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。

50第四章操作系统4.2处理器管理3．拥有资源：不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，线程一般不拥有系统资源，但它可以访问隶属进程的资源。即一个进程的所有资源可供进程内的所有线程共享。4．系统开销：进程的创建和撤消的开销要远大于线程创建和撤消的开销，进程切换时，当前进程的CPU环境要保存，新进程的CPU环境要设置，线程切换时只须保存和设置少量寄存器，并不涉及存储管理方面的操作，可见，进程切换的开销远大于线程切换的开销。同一进程内的各线程由于它们拥有相同的地址空间，它们之间的同步和通信的实现也变得比较容易。51第四章操作系统4.2处理器管理6、进程调度算法由于进程数多于处理器，它们必然竞争处理器。进程调度就是按一定策略，动态地把处理机分配给就绪队列中的某个进程。主要是协调进程对CPU的争夺使用。进程调度与作业调度有相似之处，不过进程调度仅负责CPU分配，而作业调度要负责CPU之外的资源。进程调度算法有些和作业调度相似

52第四章操作系统4.2处理器管理(1)先来先服务调度算法在进程调度中，采用FIFO算法调度时，每次从就绪队列中，选择一个最先进入该队列的进程，把处理器分配给它，使之运行。该进程一直运行到完成或发生某事件阻塞时，才放弃CPU。属于不可抢先策略。

目前已经很少采用，但常被结合在其他调度策略中，如对于具有相同优先级的进程，可使用先来先服务的原则。53第四章操作系统4.2处理器管理(2)优先级调度算法按进程的优先级大小来调度，使高优先级进程得到优先处理，进程的优先级由系统按一定的原则赋给。在实际系统中，通常采用动态优先数策略，即一个进程的优先级不是固定的，而是随许多因素的变化而变化，如进程的等待时间、已使用的处理器时间或其他资源的使用情况等。优先级策略：①非抢占的优先级调度法：一旦某个进程在运行，高优先级进程无法抢占。②可抢先优先级调度算法：任何时刻都严格按照高优先级进程在处理器上运行的原则进行进程的调度。高优先级进程可以抢先于低优先级进程。54第四章操作系统4.2处理器管理(3)时间片轮转算法进程就绪队列按进程到达的时间来排序，也就是按照先来先服务原则。但进程每次只占有一个时间片，完了必须释放重新排队等待运行。此算法对时间片大小的选择十分重要，太大退化为先来先服务，太小增大系统开销。选择时要考虑下面几个因素：1.系统对响应时间的要求2.就绪队列中进程的数目3.系统的处理能力55第四章操作系统4.2处理器管理(4)多级反馈队列调度算法：在轮转法中，加入到就绪队列的进程有如下3种情况：1)分配它的时间片用完，但进程还未完成，就回到就绪队列的末尾等待下一次调度去继续执行；2)分配给该进程的时间片未用完，只是等待IO或由于进程的互斥与同步关系而被阻塞，当阻塞解除后就回到就绪队列；3)新创建的进程进入就绪队列.如果对这些进程区别对待，给予不同的优先级和时间片，可提高系统资源的利用率。56第四章操作系统4.2处理器管理调度方法：可以将就绪队列分为N级，每个就绪队列分配给不同的时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大。各队列按照先进先出调度算法；当一个新进程就绪后进入第一级队列；如果进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列；57第四章操作系统4.2处理器管理当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列的末尾；当第一级队列空时，才去调度第二级队列，依此类推；当时间片到后，进程放弃CPU，回到下一级队列。多级反馈队列调度与优先级法在原理上的区别

一个进程在它执行结束之前，可能需要反复多次通过反馈循环执行，而不是优先级中的一次执行。58第四章操作系统4.2处理器管理课本上的几点说明：①照顾IO型进程是宗旨，目的在于充分利用外设以及对用户交互及时响应；此外，第1级队列的时间片应大于大多数IO型进程产生一个IO请求所需时间②CPU型会降低到低级别的队列，但也得到了较大的时间片，从而减少了进程间转接的次数③有些CPU型进程，偶尔产生一次IO请求，但完成后仍旧需要很长的处理器等待时间，为减少进程的调度次数，就让其回到原来所在队列，而不是从高级队列逐渐下降。59第四章操作系统4.2处理器管理7、多道程序并发运行出现的问题进程的同步与互斥

（1）同步与互斥现象 “同步”是指系统中多个进程中发生的事件存在某种时序上的关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪状态。例：司机与售票员的配合

60第四章操作系统4.2处理器管理司机售票员启动车辆关车门行驶停车售票开车门售票员关门后司机才能启动车辆，司机停车后售票员才能开门，司机和售票员的行动需要一定的协调。同样，二个进程之间有时也有这样的依赖关系，必须要有一定的同步机制保证它们的执行次序。61第四章操作系统4.2处理器管理“互斥”当各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争这些资源，进程的这种关系为进程的互斥。例如：二个不同的进程同时要求使用打印机，如果不加以控制，打印出的就是不同内容的夹杂

又例如：有两个进程P1,P2都对公共变量count作加1操作P1:R1<－count;P2:R2<－count;P1:R1<－R1+1;count<－R1;P2:R2<－R2+1;count<－R2;Count中只增加162第四章操作系统4.2处理器管理同步互斥进程－进程进程－资源－进程时间次序上受到某种限制竞争某一物理资源时不允许进程工作相互清楚对方的存在及其作用，交换信息不一定清楚其他进程的情况往往指有几个进程共同完成一个任务往往指多个任务多个进程间相互制约举例：生产和消费之间、发送和接收之间、作者和读者之间举例：交通十字路口、单轨火车的拔岔道63第四章操作系统4.2处理器管理临界资源：一次只允许一个进程使用的资源。临界资源可能是硬件，也可能是软件：变量，数据，表格，队列等。临界区：指一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构(共享资源)进行操作。在进程中涉及临界资源的程序段叫临界区。注：临界区是对某一临界资源而言的，对于不同临界资源的临界区，它们之间不存在互斥。如有程序段A、B是关于变量X的临界区，而C、D是关于变量Y的临界区，那么，A、B之间需要互斥执行，C、D之间也要互斥执行，而A与C、B与D之间不用互斥执行。64第四章操作系统4.2处理器管理使用临界区的时候必须遵循以下原则：

有空让进：当无进程在临界区，任何有权使用临界资源的进程可进入

等待：不允许二个及以上的进程同时进入临界区

多中择一：当同时有多个进程要求进入临界区时，只能让其中之一进入临界区，其他进程等待65第四章操作系统4.2处理器管理2解决进程同步与互斥的工具解决同步与互斥的工具有很多，可以由硬件或软件实现。下面介绍一种用同步原语对某信号量进行操作以实现同步与互斥的方法，通常称为P-V操作。

♦1965年，由荷兰学者迪科斯彻(Dijkstra)提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)）♦一种卓有成效的进程同步机制

♦最初提出的是二元信号量（互斥）推广到一般信号量（多值）（同步）

♦P、V操作是原语66第四章操作系统4.2处理器管理信号量(semaphore)是表示资源的物理实体，它只能被二个标准的同步原语(P、V操作)所访问，操作系统利用它的状态对进程和资源进行管理。P操作P(s)s←s-1if(s<0){

status(q)←”blocked”//将进程q置为“阻塞”//

Insert(Q,q)}//将q插入阻塞队列Q中//5.return67第四章操作系统4.2处理器管理P操作P(s)s←s-1if(s<0){

status(q)←”blocked”//将进程q置为“阻塞”//

Insert(Q,q)}//将q插入阻塞队列Q中//5.return当s>0时信号灯数值表示该类资源的可用数，每执行一次就意味着请求分配一个单位的该类资源给执行P操作的进程。因此描述为s=s-1.当s<0表示已经没有此类资源可分配，因此请求资源的进程被阻塞在相应信号灯s的等待队列。68第四章操作系统4.2处理器管理

V操作V(s)s←s+1if(s≤0){

remove(Q,R)//将R移出阻塞队列

status(R)←”ready”//将R置为就绪

Insert(RL,R)}//将R插入就绪队列RL中//6.returnV操作意味着进程释放一个单位的可用资源，故描述为s=s+1，若s≤0表示该信号灯等待队列中有因请求该资源