《计算机操作系统教程之三》第3章 进程管理

(共84张PPT)
第3章 进程管理
3.1 引言
3.2 进程的引入和定义
3.3 进程的状态和进程控制块
3.4 进程控制
3.5 线程的基本概念
3.6 进程调度
3.7 进程通信
3.8 死锁问题
开 始
本章学习目标
在多道程序环境下，程序不能独立运行。作为资源分配和独立运行的基本单位是进程。操作系统所有的特征都是基于进程而体现的。所以，本章的主要问题是：
进程的概念
进程的实体、状态及状态的演变
进程的控制与调度
进程之间的关系协调
进程的通信
死锁问题及解决
返回本章首页
3.1 引言
处理机管理是操作系统的基本管理功能之一，它所关心的是处理机的分配问题。也就是说把CPU（中央处理机）的使用权分给某个程序，通常把这个正准备进入内存的程序称为作业，当这个作业进入内存后我们把它称为进程。处理机管理分为作业管理和进程管理两个阶段去实现处理机的分配，常常又把直接实行处理机时间分配的进程调度工作作为处理机管理的主要内容。
进程通常具有三种状态：运行状态（正在使用CPU）、阻塞状态（等待输入/输出）和就绪状态（等待分配CPU）。
返回本章首页
3.2 进程的引入和定义
3.2.1 进程的引入
3.2.2 进程的定义
返回本章首页
3.2.1 进程的引入
1．程序的顺序执行及其特性
2．资源共享
3．程序的并发执行及其特性
下一页
1．程序的顺序执行及其特性
由于各类软件的出现及日益复杂化，使得程序设计的概念和方法有了很大的发展，在单道程序工作环境中，我们把一个“程序”理解为“一个在时间上按严格次序前后相继的操作序列”。
下一页
一切顺序执行的程序都具有下列特性：
（1）顺序性。
（2）资源独占。
（3）结果的无关性。
下一页
2．资源共享
操作系统提供了两种实现资源共享的方法。
（1）由操作系统统一管理和分配。
（2）由进程自行使用。
下一页
3．程序的并发执行及其特性
无论是操作系统自身的程序还是用户程序，通常总是存在一些相对独立、但又能并发执行的程序段。由于这些程序段可以被多个用户作业调用，因此可在同一时间间隔内发生。这样一来，某个程序段可能对应多个“计算”，于是程序与“计算”已不具有一一对应关系了。这些“并发程序”就构成了一个“并发环境”。
下一页
图3.2 并行计算的先后次序
下一页
程序的制约方式有如下两种 ：
（1）间接制约方式。
这是由于竞争相同资源而引起的，得到资源的程序段可以投入运行，而得不到资源的程序段就是暂时等待，直至获得可用资源时再继续运行 。
（2）直接制约方式。
这通常是在那些逻辑上相关的程序段之间发生的。一般是由于各种程序段要求共享信息引起的 。
返回本节目录
3.2.2 进程的定义
进程与程序的区别和相互关系 ：
（1）动态性和静态性。
（2）从结构上看每个进程的实体都是由程序段和相应的数据段两部分构成的，这一特征与程序的含义相近。
（3）一个进程可以涉及到一个或几个程序的执行；反之一程序可以对应多个进程，即同一程序段可在不同数据集合上运行，可构成不同的进程 。
（4）并发性。
（5）进程具有创建其他进程的功能。
（6）操作系统中的每一个程序都是在一个进程现场中运行的。
返回本节目录
3.3 进程的状态和进程控制块
3.3.1 进程的状态及状态变化图
3.3.2 进程控制块
返回本章首页
3.3.1 进程的状态及状态变化图
（1）运行状态：进程正在处理机上运行的状态，该进程已获得必要的资源，也获得了处理机，用户程序正在处理机上运行。
（2）阻塞状态：进程等待某种事件完成（例如，等待输入/输出操作的完成）而暂时不能运行的状态，处于该状态的进程不能参加竞争处理机，此时，即使分配给它处理机，它也不能运行。
（3）就绪状态：该进程运行所需的一切条件都得到满足，但因处理机资源个数少于进程个数，所以该进程不能运行，而必须等待分配处理机资源，一旦获得处理机就立即投入运行。
下一页
图3.3 典型的进程状态演变图
下一页
状态变化 ：
（1）就绪状态变化到运行状态 。
（2）运行状态变化到就绪状态。
（3）运行状态变化到阻塞状态。
（4）阻塞状态变化到就绪状态。
返回本节目录
3.3.2 进程控制块
为了刻画进程的动态变化，通常把进程表示为由程序段、私有数据块和进程控制块组成，如图3.4（a）所示。程序部分描述进程本身所要完成的功能，而“私有数据块”是接受程序规定操作的一组存储单元的内容，是操作的对象。进程控制块是在进程创建时产生的，当进程存在于系统时（运行），进程控制块就标识了这个进程。如图3.4（b）所示。
下一页
下一页
进程控制块是进程存在的标志，当系统或父进程创建一个进程时，实际上就是为其建立一个进程控制块。
进程控制块既能标识进程的存在，又能刻画出进程的动态特征，它是一个进程仅有的被系统真正感知的部分。对操作系统而言，所有进程控制块将构成并发执行控制和维护系统工作的依据。
进程控制块的作用：
返回本节目录
3.4 进程控制
3.4.1 原语
3.4.2 进程控制原语
返回本章首页
3.4.1 原语
在操作系统中，某些被进程调用的操作，例如队列操作、对信号灯的操作、检查启动外设操作等，一旦开始执行就不能被中断，否则就会出现操作错误，造成系统混乱。原语就是为实现这些操作而设置的。
下一页
图3.5 进程家族示例
返回本节目录
3.4.2 进程控制原语
1．创建原语
2．撤消原语
3．阻塞原语
4．唤醒原语
返回本节目录
3.5 线程的基本概念
3.5.1 线程的引入
3.5.2 线程与进程的比较
3.5.3 用户级线程和内核支持线程
返回本章首页
3.5.1 线程的引入
（1）创建进程。系统在创建进程时，必须为之分配其所必需的、除处理机以外的所有资源。如内存空间、I/O设备以及建立相应的PCB结构。
（2）撤消进程。系统在撤消进程时，又必须先对这些资源进行回收操作，然后再撤消PCB结构。
（3）进程切换。在对进程进行切换时，由于要保留当前进程的CPU环境和设置新选中进程的CPU环境，为此需花费不少处理机时间。
返回本节目录
3.5.2 线程与进程的比较
1．调度：在传统的操作系统中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。
2．并发性：在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。
3．拥有资源：不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。
4．系统开销：由于在创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等。因此，操作系统所付出的开销将明显地大于在创建或撤消线程时的开销。
返回本节目录
3.5.3 用户级线程和内核支持线程
比较两种线程的优缺点 ：
1．线程的调度与切换速度：内核支持线程的调度和切换与进程的调度和切换十分相似。
2．系统功能调用：当传统的用户进程调用一个系统功能调用时，要由用户态进入核心态，用户进程将被阻塞。当内核完成系统调用而返回时，才将该进程唤醒，继续执行。
3．线程执行时间 ：对于只设置了用户级线程的系统，调度是以进程为单位进行的。在采用轮转调度算法时，各个进程轮流执行一个时间片，这对诸进程而言似乎是公平的。
返回本节目录
3.6 进程调度
3.6.1 进程调度的职能
3.6.2 进程调度算法
3.6.3 调度用的进程状态切换图
返回本章首页
3.6.1 进程调度的职能
（1）记录系统中所有进程的有关情况。
（2）确定分配处理机的原则。
（3）分配处理机给进程。
（4）从进程收回处理机。
返回本节目录
3.6.2 进程调度算法
1．先来先服务
2．轮转调度
3．分级轮转法
4．优先数法
下一页
1．先来先服务
这种调度算法按照进程进入就绪队列的先后顺序来调度进程，到达得越早，其优先数越高。获得处理机的进程，未遇到其他情况时，一直运行下去，系统只需具备一个先进先出的队列，在管理优先数的就绪队列时，这种方法是一种最常见策略，并且在没有其他信息时，也是一种最合理的策略。
下一页
2．轮转调度
先来先服务的一个重要变形，就是轮转规则。轮转调度算法是系统把所有就绪进程按先后次序排队，处理机总是优先分配给就绪队列中的第一个就绪进程，并分配它一个固定的时间片（如100毫秒）。当该运行进程用完规定的时间片时，被迫释放处理机给下一个处于就绪队列中的第一个进程，分给这个进程相同的时间片，每个运行完时间片的进程，当未遇到任何阻塞时，就回到就绪队列的尾部，并等待下次转到它时再投入运行。于是，只要是处于就绪队列中的进程，按此种算法迟早总可以分得处理机投入运行。
下一页
3．分级轮转法
所谓分级轮转法就是将先前的一个就绪队列。根据进程的优先数不同划分两个或两个以上的就绪队列，并赋给每个队列不同的优先数。以两个就绪队列为例，一个具有较高优先数，另一个具有较低优先数，前者称为前台队列，后者称为后台队列。
下一页
4．优先数法
根据已占有处理 机的进程是否可被剥夺而分为优先占有法和优先剥夺法两种 。
优先占有法的原理是：一旦某个最高优先数的就绪进程分得处理机之后，只要不是其自身的原因被阻塞（如要求I/O操作）而不能继续运行时，就一直运行下去，直至运行结束。
优先剥夺法的原理是：当一个正在运行的进程即使其时间片未用完，无论什么时候，只要就绪队列中有一个比它的优先数高的进程，优先数高的进程就可以取代以前正在运行的进程，投入运行 。
下一页
确定进程的优先数通常应考虑如下几个因素：
（1）进程类型。
（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 进程的通信方式之二——消息缓冲
返回本章首页
3.7.1 临界资源和临界区
在计算机中有许多资源只允许一个进程使用，如果有多个进程同时去使用这类资源就会产生严重的错误。
几个进程若共享同一临界资源，它们必须以互斥的方式使用这个临界资源，即当一个进程正在使用临界资源且尚未使用完毕时，则其他进程必须推迟对该资源的进一步操作，在当前进程的使用完成之前，不能从中插进去使用这个临界资源，否则将会造成信息混乱和操作出错。
系统中同时存在有许多进程，它们共享各种资源，然而有些资源每次只能让一个进程所使用。
返回本节目录
3.7.2 进程的通信方式之一 —— 同步与互斥
同步：我们把进程间的这种必须互相合作的协同工作关系，称为进程同步。
互斥：两个并行的进程A、B，如果当A进行某个操作时，B不能做这一操作，进程间的这种限制条件称为进程互斥，这是引起资源不可共享的原因。
lock和unlock
大部分同步方案均采用某个物理实体（如锁、信号灯等）实现通信，进程通信原语中关锁（lock）和开锁（unlock）是最简单的原语。在这两个原语中设置一个公共变量x代表某个临界资源的状态。如：x=0，表示资源可用，x=1，表示资源正在使用。
关锁原语1ock（x）：
L：if x＝1 then goto L
else x：=1；
开锁原语unlock（x）：
x：=0；
图3.7 开锁和关锁程序流程图
返回本节目录
3.7.3 两个经典的同步/互斥问题
1．生产者与消费者问题
2．读者与写者问题
1．生产者与消费者问题
Dijkstra把广义同步问题抽象成一种“生产者与消费者问题”（Producer-consumer-relationship）的抽象模型。事实上，计算机系统中的许多问题都可归结为生产者与消费者问题，生产者与消费者可以通过一个环形缓冲池（见图3.8）联系起来，环形缓冲池由几个大小相等的缓冲块组成，每个缓冲块容纳一个产品。每个生产者可不断地每次往缓冲池中送一个生产产品，而每个消费者则可不断地每次从缓冲池中取出一个产品。
下一页
图3.8 环形缓冲池
下一页
下面给出基于环形缓冲区的生产者与消费者关系的形式描述，设：
（1）公用信号量mutex：初值为1，用于实现临界区互斥。
（2）生产者私用信号量empty：初值为n，指示空缓冲块数目。
（3）消费者私用信号量full：初值为0，指示满缓冲块数目。
（4）整型量i和j初值均为0，i指示首空缓冲块序号，j指示首满缓冲块序号。
模块 设计如下：
下一页
Var mutex，empty，full：semaphore;
i,j:integer；buffer：array [0…n一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 product;
end
下一页
end;
begin
seminitial ;
i:＝j:＝0;
cobegin
producer；
consumer；
coend
end
下一页
2．读者与写者问题
设某航空公司有2个售票处，它们通过远程终端访问设在公司总部的航空订票系统，并要查询或修改系统中记录所有班机当前订票数的数据库B。设Bi为某班机的当前订票数，P1和P2分别代表2个售票处的售票进程，R1和R2为进程执行时使用的工作寄存器。由于售票进程并发执行，且各自访问数据库B的时间是随机的，故有可能出现下面的访问序列（假定Bi的当前值为x）：
下一页
P1:R1:=Bi;
R1:=R1+1
P2:R2=Bi;
R2:=R2+1;
P1:Bi:=R1;
P2:Bi:=R2
可见，Bi的新值是X+1，而不是X+2。这里的P1和P2均为写者，显然，对于写者Bi为临界资源，因此写者应该互斥。
下一页
下面给出读者进程与写者进程的一般结构。
var mutex, wrt: semaphore;
readcount: integer;
begin
seminit ;
readcount:=0
cobegin
procedure reader;
begin
P(mutex);
Readcount:=readcount+1;
If readcount=1 then P (wrt);
V(mutex);
Reading is performing;
下一页
P(mutex);
readcount:=readcount-1
if readcount=0 then V(wrt);
V (mutex);
End
Procedure writer;
Begin
P(wrt);
writing is performing;
V(wrt);
End
Coend
End;
返回本节目录
3.7.4 结构化的同步/互斥机制——管程
建立管程的基本理由是：由于对临界区的执行分散在各进程中，这样不便于系统对临界资源的控制和管理，也很难发现和纠正分散在用户程序中的对同步原语的错误使用等问题。为此，应把分散的各同类临界区集中起来。并为每个可共享资源设立一个专门的管程来统一管理各进程对该资源的访问。这样既便于系统管理共享资源，又能保证互斥访问。
下一页
管程主要由两部分组成：
（1）局部于该管程的共享数据，这些数据表示了相应资源的状态。
（2）局部于该管程的若干过程，每个过程完成关于上述数据的某种规定操作。
为了实现对临界资源的互斥访问，管程每次只允许一个进程进入其内（即访问管程内的某个过程），这是由编译系统保证的。
下一页
monitor ringbuffer;
var rbuffer：array[0．．n-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:=(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;
begin
k:=0;
nextempty:=0;nextfull:=0;
end;
下一页
在利用管程解决生产者、消费者问题时，其中的生产者和消费者可描述为：
producer：begin repeat
produce an item；
ringbuffer. put(item)；
until false；
end
consumer：begin
repeat
ringbuffer. get (item)；
consume the item；
end
返回本节目录
3.7.5 进程的通信方式之二——消息缓冲
1．SEND(A)（发送消息）原语
2．READ（A）（读取消息）原语
下一页
1．SEND(A)（发送消息）原语
发送消息原语被进程用于把消息发送到存放消息的缓冲区。A是原语的参数，表示发送区的地址。其工作原理是：首先调用“寻找目标进程的PCB”的程序查找接收进程的PCB，如果接收进程存在，申请一个存放消息的缓冲区，消息缓冲区为空时，接收此消息的进程因等待此消息的到来而处于阻塞状态，则唤醒此进程，并把消息的内容、发送原语的进程名和消息等，复制到预先申请的存放消息的缓冲区，且将存放消息的缓冲区连接到接收进程的PCB上；如果接收进程不存在，则由系统给出一个“哑”回答；最后控制返回到发送消息的进程继续执行，或转入进程调度程序重新分配处理机。如果消息缓冲区已满，则返回到非同步错误处理程序入口进行特殊处理。如图3.9所示。
下一页
图3.9 发送消息过程流图
下一页
2．READ（A）（读取消息）原语
READ(A)原语用来读取消息，接收进程读取消息之前，在自己的空间中确定一个接收区。当接收进程想要读取消息时，使用READ(A)原语，A是接收进程提供的接收区开始地址。如图3.10所示。
下一页
图3.10 读取消息
返回本节目录
3.8 死锁问题
3.8.1 死锁产生的原因和必要条件
3.8.2 预防死锁
3.8.3 发现死锁
3.8.4 解除死锁
返回本章首页
3.8.1 死锁产生的原因和必要条件
死锁产生的原因 ：
当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继续运行，这就产生了一种特殊的现象——死锁。
在许多实时应用中，比如计算机控制运输和监视系统方面，死锁问题也极为重要。
下一页
死锁产生例子1：
我们先来看一个申请不同类型资源的死锁例子，假定有两个进程Pl和P2都要修改文件F，修改时都需要一条暂时存放信息的磁带，而只有一台磁带机T可用。又假定由于某种原因，在进行修改之前，P2需要一暂存磁带（例如为了修改，要重新组织输入数据）。设F和T都是可重用资源，它们分别表示允许更新文件和允许使用磁带机。于是Pl和P2。可有如下形式：
下一页
分析：从上面的申请-释放过程可以看出，进程Pl和P2有可能“同时”分别到达rl和r2处，例如，P2首先得到T，然后Pl得到F，接着Pl到达r1，最后P2到达r2，此时，若Pl继续运行，则占有F的进程Pl将阻塞在T上，若P2继续运行，则占有T的进程P2将阻塞在F上，如果P2不能前进，则P1也不能继续下去，反之亦然。我们说这两个进程处在死锁状态。
下一页
图3.11 简单的死锁例子
下一页
死锁产生例子2：
现在我们再来看一个关于相同类型资源共享的死锁例子，假设有一类可再使用资源R，例如主存或外存，它包含有m个页面或扇区，由n个进程P1，P2…，Pn（2≤m≤n）共享。假定每个进程按右图顺序申请和释放页面（或扇区）：
下一页
分析：这里每次申请和释放只涉及R的一个分配单元（页或扇区）。因此，当把所有单元全部分配完毕时，便很容易发生死锁；占有R的单元的所有进程（前m个进程）会永远阻塞在第二次申请上，而有些进程（n~m个进程）类似地会阻塞在它们的第一次申请上，在图3.12中说明了n＝3，m＝2时这种系统的状态，这类死锁是相当普遍的。
下一页
图3.12 同类资源共享时的死锁现象
下一页
产生死锁有四个必要条件：
产生死锁有四个必要条件：
（1）互斥条件。
（2）不剥夺条件。
（3）请求和保持条件。
（4）环路等待条件。
返回本节目录
3.8.2 预防死锁
1．破坏“请求与保持条件”
2．破坏环路条件
3．资源受控动态分配
1．破坏“请求与保持条件”
这种方法的基本思想是：每个进程在运行之前，必须预先提出自己所要使用的全部资源，调度程序在该进程所需要的资源末得到满足之前，不让它们投入运行，并且当资源一旦分配给某个进程之后，那么在该进程的整个运行期间相应资源一直被它占有，这就破坏了产生死锁的请求与保持条件。
下一页
2．破坏环路条件
这种方法的基本思想是：对系统提供的每一项资源，由系统设计者将它们按类型进行线性排队，并赋予不同的序号。例如，设卡片输入机为1，打印机为2，磁带机为3，磁盘机为4，……。所有的进程都只能严格地按照编号递增（或递减）的次序去请求资源，亦即，只有低编号的资源要求满足后，才能对高编号资源提出要求；释放资源时，应按编号递减的次序进行。由此可以看出，对资源请求采取了这种限制之后，所形成的进程—资源图不可能再产生环路。如图3.13所示 .
下一页
图3.13 资源申请和释放顺序图
下一页
3．资源受控动态分配
为了避免死锁发生，操作系统必须根据预先掌握的关于资源用法的信息控制资源分配，使得共同进展路径的下一步不致于进入危险区，即只要有产生死锁的可能性，就避免把一种资源分配给一个进程。
返回本节目录
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（或队列）。

下一页
表3.1 资源分配表S
下一页
表3.2 进程等待表W
下一页
其发现死锁的算法如下：
（1）把末阻塞（Ci＝0）的进程Pi记录在L表中（其全部资源请求已得到满足的进程）。
（2）从L表中选择一进程，根据资源分配表S释放分配给该进程的所有资源。
（3）由进程等待表W依次检查和修改需要该进程释放资源的每一个进程的等待计数器Cj。
（4）若Cj＝0，则表示该进程所请求的资源已得到满足，不再阻塞，将Pj记入L表中。
（5）再从L表中选取另一进程，重复上述操作。
（6）若所有的进程都记入L表中，则系统初始状态为非死锁状态，否则为死锁状态。
返回本节目录
3.8.4 解除死锁
1．资源剥夺法
（1）还原算法。即恢复计算结果和状态。
（2）建立检查点主要是用来恢复分配前的状态。
2．撤消进程法
（1）程序的优先数，即被撤消进程的优先数。
（2）作业类的外部代价
（3）运行代价
返回本节目录
THANK YOU VERY MUCH！
本章到此结束，
谢谢您的光临！
返回本章首页
结 束