第2章 进程和处理机管理

第２章进程和处理机管理要求学生掌握顺序程序和并发程序；进程的定义、特点及状态变迁；进程管理；进程间的同步与互斥；进程通信；死锁产生的原因与解除方法。第２章进程和处理机管理

2.1进程及其有关概念

2.2进程管理

2.3进程的同步与互斥

2.4进程通信

2.5死锁

2.6小结2.1.1顺序程序

1.顺序程序：程序中若干操作必须按照某种先后次序来执行，并且每次操作前和操作后的状态之间都有一定的关系。2.1进程及其有关概念2.顺序程序的基本特征

(1)程序执行的顺序性(2)资源利用的独占性，又叫程序执行的封闭性(3)执行结果的确定性2.1.2并发程序

1.并发执行：如果有多个程序段同时在系统中运行且执行时间是重叠的，即使重叠很小，我们也称这几个程序段是并发执行的。

2.要求：两个或两个程序处于运行状态2.1进程及其有关概念图2-1三个并发程序段示意图2.1.2并发程序

3.用语句形式描述并发程序（执行如图2-2）

s0;cobegins1;s2;…sn;coend sn+1; 2.1进程及其有关概念图2-2并发程序执行的优先图2.1.2并发程序

4.并发执行和并行执行的区别：

前者是在一段时间内，从宏观上看好象它们是在同时执行，而实际上CPU是按照一定的策略在轮流执行它们，在任一时刻，实际上只有一个程序段在执行。而并行执行需要多CPU的支持，在任一时刻，可以实现多个程序段的真正同时执行。5.引入并发程序的目的：主要是为了提高资源利用率，从而提高系统效率2.1进程及其有关概念6.比较顺序程序和并发执行

举例：假设有A和B两个程序段，它们各自的执行过程如图2.3所示。2.1进程及其有关概念图2-3顺序程序举例如果这两个程序段是顺序执行，则CPU利用率=40/80=50%DEV1利用率=15/80=18.75%DEV2利用率=25/80=31.25%6.比较顺序程序和并发执行2.1进程及其有关概念图2-4并发程序举例如果这两个程序段按照如图2-4的顺序并发执行，那么CPU利用率=40/45=89%DEV1利用率=15/45=33%DEV2利用率=25/45=56%2.1.2并发程序

7.并发执行的特征：(1)并发性(2)程序结果的不可再现性（见下页例子）(3)在并发环境下程序的执行是间断性的，即程序“执行---暂停---执行”(4)开放性⑸独立性⑹制约性：分为间接制约和直接制约(7)程序和计算不在一一对应2.1进程及其有关概念例如，A向某帐号存钱，B从某帐号取钱。程序如右：①先执行A，后执行B，即先存钱，后取钱，其结果为s=900。②t1时刻：执行A中的n=s;n=n+100;t2时刻：执行B中的m=s;m=m-200;s=m;t3时刻：执行A中的s=n;则结果为s=1100。程序结果的不可再现性举例main(){ints=1000；//最初余额cobeginwhile(A未完成){n=s;n=n+100;s=n;}while{m=s;m=m-200;s=m;}coend}2.1.3进程的定义及其特征

1.进程定义最能反映进程实质的定义有：1）进程是程序的一次执行2）进程是可以和别的计算并发执行的计算3）进程可定义为一个数据结构及能在其上进行操作的一个程序。4）进程是一个程序及其数据在处理机上顺序执行所发生的活动。2.1进程及其有关概念5）进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。进程的一个正式的定义是：：进程是在自身的虚拟地址空间运行的一个单独的程序，是系统进行资源分配和调度的一个独立单位

这个定义包含的含义是：1）进程一个动态的概念，而程序是一个静态的概念。

3.1进程的基本概念2）进程包含了一个数据集合和运行其上的程序。3）同一程序运行于若干个不同的数据集合上时，它将属于若干个不同的进程，或者说，两个不同的进程可包含相同的程序。4）系统分配资源是以进程为单位的，所以只有进程才可能在不同的时刻处于几种不同的状态，例如，等待，就绪，运行。5）从微观上看，进程是轮换地占有处理机而运行的；从宏观上看，进程是并发运行的2.1进程及其有关概念2.1.3进程的定义及其特征

2.进程和程序的区别:

⑴进程是程序的一次运行，属于动态概念；程序是指令的集合，是静态概念。⑵进程包含数据和运行其上的程序，这样静态地观察进程与程序含义相近。⑶同一程序运行于若干个不同的集合上时，它将属于若干个不同的进程。或者说，两个不同的进程可以包含相同的程序。2.1进程及其有关概念2.1.3进程的定义及其特征

2.进程和程序的区别:

⑷进程能逼真的描述并发活动，而程序不明显。⑸微观上，进程是轮流抢占处理机而运行的，宏观上，进程是并发运行的。⑹程序存储需要介质，进程执行要处理。⑺进程是由程序和数据两部分组成的。⑻进程可以创建其他进程，可以处于等待、就绪、运行等几种不同的状态。2.1进程及其有关概念2.1.3进程的定义及其特征

3.进程和作业的区别:一个正在执行的进程称为一个作业，而且作业可以包含一个或多个进程，尤其是当使用了管道和重定向命令时。4.进程的特征⑴动态⑵并发⑶独立⑷交互⑸异步

2.1进程及其有关概念2.1.4进程的类型1、系统进程和用户进程，两者的区别:⑴系统进程被分配一个初始资源集，这些资源可以独占，也可被拥有更高优先权的系统进程优先使用。用户进程要通过系统服务请求手段竞争系统资源。⑵用户进程不能直接做I／O操作，而系统进程可以直接进行。⑶系统进程在管态下活动，用户进程在目态下活动。2.1进程及其有关概念2.1.4进程的类型2、父进程和子进程系统或用户首先创建的进程称父进程；在父进程下面的进程称子进程。进程图如图2-5所示：进程图：是一棵包含一个根结点有向树，Pi到结点Pj的一条边表示进程Pj是由进程Pi创建的2.1进程及其有关概念图2.5进程图2.1.4进程的类型2、父进程和子进程进程图反映了进程间的父子关系：创建与被创建、控制与被控制关系，体现了进程间的层次关系。

父子进程间的关系主要为：⑴进程控制：父创建或删除子⑵运行方式：同时运行或最后运行⑶资源共享：全部或部分共享资源2.1进程及其有关概念2.2.1进程的状态及其转换1、进程的三个基本状态⑴运行状态⑵就绪状态

⑶等待状态。也叫阻塞状态、挂起状态、封锁状态、冻结状态、睡眠状态。2、引起进程状态转换的原因大致如下：⑴CPU调度；⑵进程在运行过程中需要等待某一事件；⑶如果进程所等待的事件发生变化；⑷一个具体的进程在任何一个指定的时刻必须而且只能处于一种状态。2.2进程管理2.2进程管理图2-6进程状态变迁图2.2.2进程的组成1、进程的组成

进程由三部分组成：程序、数据集合和进程控制块(ProcessControlBlok，PCB)前两者称为进程的实体，用PCB描述实体的存在和变化。2.2进程管理PCB数据程序图2-7进程的组成2.2.2进程的组成2、进程控制块PCB1)PCB的作用：标识进程存在的唯一实体2）进程控制块PCB常用的信息如表2-13）PCB中的内容主要分为如下3大部分：进程标识符、处理器状态信息、进程控制信息

2.2进程管理进程标识符进程当前状态当前队列指针总链指针程序开始地址进程优先级CPU现场保护区进程通信家族联系占有资源清单表2-1PCB的一般结构2.2.2进程的组成3、PCB表的两种组织方式

1）线性表；2）链接表。如图2-8所示

2.2进程管理(a)PCB的线性表Next0Next1Next2

∧PCB1PCB2PCBnReady-head高低(b)按优先级排列的就绪队列链接表priority2.2.2进程的组成3、PCB表的两种组织方式

2.2进程管理Next0Next1Next2

∧PCB1PCB2PCBnReady-head先后(c)按先来先服务排列的就绪队列链接表FCFS图2-8PCB表的组织方式4、进程的状态转换用PCB队列来表示

2.2进程管理图2.9状态转换2.2.3进程控制

原语：程序、我们把系统态下执行的某些具有特定功能的程序段。原语可以是机器指令集的扩充，其特点是执行期间不允许中断，它是一个不可分割的基本单位。用于进程控制的原语有：创建原语、撤消原语、阻塞原语、唤醒原语等2.2进程管理2.2.3进程控制

1、创建进程创建进程原语，操作系统主要完成以下几项工作：1)创建一个PCB。2)赋予一个统一的进程标识符。3)为进程映象分配空间。4)初始化进程控制块。5)设置相应的链接,如把新进程加到就绪队列的链表中。2.2进程管理假设我们用n表示进程名（外部标识符），CPU的初始状态为S，优先数为K，内存始址为M，资源清单为R，申请的PCB的内部标识符为i，则创建进程原语可描述为：创建原语Create(n,S,K,M,R,acc){i=getnewinternalname(n)；∥为n申请一个PCB，标号送入iid[i]=n；∥进程外部标识符登记第i个PCB相应域

priority[i]=K；∥置优先数

cpustate[i]=S；∥置CPU状态

mainstore[i]=M；∥置内存始址

resourcesp[i]=R；∥置资源表

status[i]=“readys”；∥置该进程为就绪状态

sdata[i]=RL；∥指向就绪队列

parent[i]=*；∥置创建它的父进程名insert(progeny(*),i)；∥插入进程簇中

setaccountingdata；∥建立记帐信息

insert(RL,i)∥将PCB插入就绪队列}2、删除进程又称撤消进程删除进程的3种情形：1）正常终止；2）由于错误非正常终止；3）祖先进程要求撤销

删除进程通常需要完成以下工作：1）定位欲删除的进程PCB；2）回收进程所占的全部资源；3）递归地删除其所有“子孙”进程；4）删除PCB，处理记账信息；5）若删除的是正在运行的进程，则请求重新调度，否则返回。2.2进程管理删除进程原语Kill操作如下：Delete(n){Sched=false;//置调度标志为假I=getinternatname(n);//找内部进程号Kill(i);//调删除进程过程If(sched)Scheduler;//若i为运行态，则重新调度}

kill(i){If(status[i]==”Executing”)//若i为运行态{stop(i);//停止i的执行，保存CPU信息sched=true;//置重新调度标志}remove(sdata[i],i);//从队列中删去i进程for(alls∈progency(i))kill(s)//删除i的所有子进程for(allr∈(mainstore(i)∪resoure(i)))ifowned[r]then//如果是i的祖先的资源，则全部归还insert(avail(semaphore(r)),data(r));//给它的祖先for(allR∈creaeresources(i))removeresourcesdescriptot[R];//创建时申请的资源全部归还给系统removepch[i];//释放PCB}2.2.3进程控制

3、挂起进程

进程挂起方式：自身挂起；挂起指定标识符的进程；进程全部或部分子孙进程挂起

在挂起进程控制中主要完成以下工作：1）定位欲挂起的进程PCB；2）将其运行的有关现场信息放至调用者指定的区域；3）将进程变为挂起状态；4）如果进程从运行状态变为挂起状态，则请求重新调度。2.2进程管理假设挂起指定标识符为n的进程，调用者指定区域为a，则挂起进程原语可描述为：2.2进程管理Suspend(n,a){i=get-internal-name(n);//根据指定标识符n获取进程内部号S=status[i];//把状态赋给sIf(s==”Executing”)Stop(i);//若进程为执行态，则中断ＣＰＵA=copy-PCB[i];//保存ＰＣＢ状态到指定区域Status(i)=(s=”Blockeda”?”Blockeds”:”Ready”);//若状态为活动阻塞，则挂起进程为静止阻塞，否则为就绪状态

If(s=”Executing”)Scheduler;//若为执行态，则重新调度}2.2.3进程控制

4、唤醒进程

进程唤醒方法：1）有系统进程唤醒；2）有事件发生进程唤醒

唤醒进程原语完成的主要工作如下：1）定位被唤醒的进程PCB；2）将其改变为就绪状态，插入就绪队列；3）请求重新调度。2.2进程管理假设唤醒指定标识符为n的进程，则唤醒进程原语可描述为：2.2进程管理

Wakeup(n){i=get-internal-name(n);/／找到唤醒进程nRemove(WL[r],i);/／从等待队列中出队Status[i]=”ready”;／/将其变为就绪队列Insert(RL,i);/／插入就绪队列Scheduler;/／重新调度}在以上算法中，WL为等待队列，RL为就绪队列。2.2.4进度调度进程调度（也称CPU调度）:按照某种调度算法从就绪队列中选取进程分配CPU，也叫低调

衡量各种调度算法性能优劣的指标:

1）CPU利用率——主要目标CPU利用率=CPU利用的时间/开机运行的总时间

2）等待时间3）响应时间4）I/O设备的利用率5）“时空”代价2.2进程管理2.2.4进度调度进程调度方式：剥夺调度和非剥夺调度下面介绍几种常见的进程调度方法1.先来先服务（Firstcomefirstservice,FCFS）2.轮转法（RR，RoundRobin）将CPU的处理时间分成固定大小的时间片，进程时间片内轮转执行

关键问题：如何确定时间片的大小

时间片q=RT/Nmax2.2进程管理将考虑下面3个进程，它们按1，2，3的顺序处于就绪队列中：进程下一个CPU周期

P124P23P33

2.2进程管理图2-10执行过程1图2-11执行过程2FCFS调度算法其他调度算法2.轮转法设有如下4个就绪进程：进程下一个CPU周期

P16P23P31P47

则如图2-12所示2.2进程管理01234567qATT图2-12平均周转时间ATT与时间片q之间的关系2.2.4进度调度3.多级反馈轮转法思想：不同级别的就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别降低，时间片加大

例如：考虑由3个队列组成的多级队列调度3个队列的编号分别为0,1,2，如下图2.2进程管理2.2.4进度调度4.优先数法（Priority）思想：按进程的优先级确定调度优先权优先级确定方法：（1）静态法：可按进程类型、资源的要求、用户要求指定（2）动态法：原则是合理地分配CPU时间、紧急的程序优先2.2进程管理实例解释：假设就绪状态有4个进程，每个进程所需运行时间如下所示。进程 所需运行时间

1 62 33147进程到达次序为1，2，3，4。试分别按先来先服务调度算法、短进程优先调度算法和时间片轮转法(时间片分1，3，5，6)给出进程调度顺序，并计算平均等待时间。2.2进程管理解：（1）先来先服务调度算法进程调度顺序为：

平均等待时间：T=1／4×(0+6+9+10)=6.25（2）短进程优先调度算法进程调度顺序为：平均等待时间：T=1／4×(4+1+0+10)=3.75（3）时间片轮转法

2.2进程管理解：·时间片为1，进程调度顺序如下：

平均等待时间：T=1/4×((0+3+2+2+1+1)+(1+3+2)+2+(3+2+2+1+1+1)=1／4×(9+6+2+10)=6.75·时间片为3，进程调度顺序如下：平均等待时间：T=1／4×((0+7)+3+6+(7+3))=1／4×(7+3+6+10)=6.52.2进程管理解：·时间片为5，进程调度顺序如下：平均等待时间：T=1／4×((0+9)+5+8+(9+1))=1／4×(9+5+8+10)=8·时间片为6，相当于先来先服务调度算法。其进程调度顺序和平均等待时间与先来先服务调度算法相同。总结：短进程优先调度算法使进程平均等待时间最小。对于时间片轮转法，进程平均等待时间与时间片的大小有关。

2.2进程管理进程间的两种主要关系：

1、互斥关系，也称间接制约关系：各进程间竞争、互斥使用共享资源

2、同步关系，也称直接制约关系：指多个进程发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。譬如公共汽车上司机与售票员的合作就是一种同步关系。2.3进程的同步与互斥同步与互斥的特点比较如表2-1所示。2.3进程的同步与互斥同

步互

斥进程—进程时间次序上受到某种限制相互清楚对方的存在及其作用，交换信息往往指有几个进程共同完成一个任务举例：生产与消费之间，发送与接受之间，作者与读者之间，供者与用者之间进程—资源—进程竞争到某一物理资源时不允许进程工作不一定清楚其它进程情况往往指多个任务多个进程间通讯制约举例：交通十字路口，单轨火车的拨道岔表2-1同步与互斥的比较2.3.1临界区

临界资源：一次只允许一个进程使用的资源

临界区：在进程中涉及到临界资源的程序段

使用临界区、解决互斥问题应遵守以下原则：

1）有空让进2）等待3）多中择一4）有限等待5）让权等待2.3进程的同步与互斥2.3.1临界区

我们先看一下几个问题：问题1：设进程P1，P2，共享一台打印机问题2：生产者／消费者问题(Producer／Consumer)这里，生产者和消费者进程因为共享使用着一个软件资源――产品系列，若按不恰当的执行顺序，则队列操作就会出现混乱。2.3进程的同步与互斥小结：从以上二个例子可以看到，进程之间若共享互斥资源(共享外设—打印机，共享队列等)，则会出现互斥问题，即存在临界区问题。2.3.2互斥

进程互斥进入方法：

1、用禁止中断实现互斥

2、用锁操作原语实现互斥为共享资源设置一把锁。锁用变量W表示：W=0表示共享资源可用。W=1表示共享资源不可用，已有进程访问

有关锁的基本操作如下：

2.3进程的同步与互斥加锁原语LOCK（W）{while(W);W=1;}开锁原语UNLOCK（W）{W=0;}2.3.2互斥

3、信号量及P、V操作原语实现互斥

信号量(Semaphore)是表示资源的物理实体，是一个与队列有关的整型变量。信号量是一个数据结构,一般定义如下：

strucsemaphore{intvalue; pointer_PCBqueue;}2.3进程的同步与互斥信号量说明：

semaphores;3、信号量及P、V操作原语实现互斥P、V操作是指在信号量上定义的两个操作。设信号量为s，对s的P操作记为P(s)，对它的操作记为V(s)。2.3进程的同步与互斥P操作对应的过程如下：P(s){s.value――;if(s.value<0){该进程状态置为等待状态;

将该进程的PCB插入相应的等待队列末尾s.queue;}}V操作对应的过程如下：V(s){s.value++;if(s.value<=0){唤醒相应等待队列s.queue中等待的一个进程;改变其状态为就绪态;并将其插入就绪队列;

}}3、信号量及P、V操作原语实现互斥P(s)表示申请一个资源，V(s)表示释放一个资源。P.V操作必须成对出现2.3进程的同步与互斥P1P2…………P(s);P(s);使用打印机;使用打印机；V(s);V(s);…………下面通过几个例子进一步说明。例1用PV操作解决打印机共享的问题（如右）s的初值为1，表示打印机是可用的。例2生产者／消费者问题（自行阅读）例3用P、V操作实现如图2-17所示的优先图2.3.3进程同步

1、同步类别：

(1)对系统资源的共享。(2)诸进程合作完成某工作的逻辑顺序。

2、利用信号量机制解决进程同步问题举例设有若干个生产者进程P1，P2，….Pn，若干个消费者进程C1，C2，…Cm，它们通过一个有界缓冲池联系起来。其同步问题是：P进程不能往“满”缓冲区中放产品，C进程不能从“空”缓冲区中取产品。可以采用P.V操作解决。设各生产者使用的信号量为S1，消费者使用的信号量为S2。2.3进程的同步与互斥例1：设只有一个生产者、一个消费者且缓冲区的大小为1。S1初值为1、S2为0。S1=1表示最初有一个缓冲区空间可用，S2=0表示最初没有产品可消费。2.3进程的同步与互斥P：while(true){

生产一个产品;P(s1);

送产品到缓冲区;V(s2);};C：while(true){P(s2);

从缓冲区取产品;V(s1);

消费产品;};例4再看第二种情况：只有一个生产者、一个消费者且缓冲区的大小为n。设S1初值为n，S2初值为0。S1=n表示最初有n个缓冲区空间可用，S2=0表示最初没有产品可消费。2.3进程的同步与互斥P：i=0;while(true){

生产产品;P(S1);

往Buffer[i]放产品;V(S2);i=(i+1)%n;};

C：j=0;while(true){P(S2);

从Buffer[j]取产品;V(S1);

消费产品;j=(j+1)%n;};例5再看第三种情况：有m一个生产者、k个消费者且缓冲区的大小为n。设S1初值为n，S2初值为0，mutex的初值为1（默认值）。2.3进程的同步与互斥P：i=0;while(true){

生产产品;P(S1);P(mutex);

往Buffer[i]放产品;V(mutex);V(S2);i=(i+1)%n;};C：j=0;while(true){P(S2);P(mutex);

从Buffer[j]取产品;V(mutex);V(S1);

消费产品;j=(j+1)%n;};2.4.1进程通信的概念

1、进程通信：是指进程之间的信息交换。2、进程通信类型1)

共享存储器系统2)消息系统进程间的信息交换以消息或者报文为单位消息系统有两种通信方式：a）直接通信方式

原语：send(接收者ID，消息)和receive(发送者ID，消息)2.4进程通信b）间接通信方式如右图，进程间有中间实体（信箱）2.4进程通信发送进程接收进程信箱头信箱1信箱2

间接通信方式3)

利用共享文件（管道）的通信方式

发送进程接收进程图3-12利用共享文件（管道）通信2.4.2消息通信

通信链：是指进程之间进行通信存在的链路连接，通信链有物理通信链和逻辑通信链之分。

通信方式主要有：直接或间接通信；对称或非对称通信。

1、直接通信

直接通信的一个基本原则是：发送/接收消息的每一个进程，通信时都必须明显地指明接收/发送方的名字。2.4进程通信2.4.2消息通信

1、直接通信直接通信通信链的属性主要包括以下方面：1）参加通信的双方；2）每条通信链严格地对应两个进程；3）任意一对进行通信的进程，均严格地存在一条通信链；4）通信链是双向的，可双向传输

其中，send和receive原语定义为：

Send(P,message):发送message给进程P；

Receive(Q,message):接收来自进程Q的message2.4进程通信生产者/消费者问题采用直接通信方式的进程间的通信进程：2.4进程通信typedefitem=…；itemnextp,nextc;cobegin;producer{do{…produceaniteminnextp;…send(consumer,nextp);}while(true);}

consumer{do{receive(producer,nextc);…consumetheiteminnextc;…}while(true);}coend利用消息缓冲区实现直接通讯方式的通讯链：2.4进程通信图2-19消息缓冲区的直接通讯2.4.2消息通信

2、间接通信，又称邮箱(mailbox)通讯方式进程间通过信箱实现通信邮箱是一种数据结构，结构如图2-20

使用信箱的规则：1）若发送信件时邮箱已满，则发送进程被置为“等邮箱”状态，直到信箱有空时才被释放。2）若取信件时信箱中无信，则接收进程被置为“等信件”状态，直到有信件时才被释放。2.4进程通信图2-20邮箱结构2.4.2消息通信

2、间接通信，又称邮箱(mailbox)通讯方式send和receive原语定义如下：send(A,message)：向邮箱A送入message；receive(A,message)：从邮箱A取出message2.4进程通信

send实现步骤如下所示：{查找指定邮箱A；若邮箱未满，则把信件message送入邮箱且释放“等信件”者；若邮箱已满置发送信件进程为“等邮箱”状态；}receive实现步骤如下所示:{查找指定邮箱A；若邮箱中有信，则取出一封信存于message中且释放“等邮箱”者；若邮箱中无信件则置接收信件进程“等信件”状态；}2.4.2消息通信

2、间接通信，又称邮箱(mailbox)通讯方式在间接通讯方式中，通讯链具有如下属性:1)只有当两个进程有了一个可共享的邮箱时，通讯链才在二者之间建立。2)通讯链能够联系两个以上的进程。3)每一对通讯进程之间必须有一组不同的链，每条链对应一个邮箱。4)通讯链可以是单向的，又可以是双向的，如图2-21所示。2.4进程通信2.4进程通信图2-21邮箱通信方式2.5