进程控制块（什么是进程控制块）

进程管理也称处理机管理。在多道程序批处理系统和分时系统中有多个并发执行的程序，为了描述系统中程序执行时动态变化的过程引入了进程。进程是资源分配和独立运行的基本单位。进程管理重点需要研究诸进程之间的并发特性，以及进程之间相互合作与资源竞争产生的问题。

前趋图是一个有向无循环图，由结点和有向边组成，结点代表各程序段的操作，而结点间的有向边表示两个程序段操作之间存在的前趋关系（→）。程序段 $P_i$ 和 $P_j$ 的前趋关系表示成 $P_i$ → $P_j$ ，其中， $P_i$ 是 $P_j$ 的前趋， $P_j$ 是 $P_i$ 的后继，其含义是 $P_i$ 执行结束后 $P_j$ 才能执行。例如，下图为3个程序段，其中输入是计算的前驱（计算是输入的后继），输入结束才能进行计算，计算是输出的前驱，计算结束才能进行输出。

程序顺序执行时的主要特征包括顺序性、封闭性和可再现性。

若在计算机系统中采用多道程序设计技术，则主存中的多道程序可处于并发执行状态。对于上述有3个程序段的作业类，虽然每个作业有前趋关系的各程序段不能在CPU和输入/输出各部件并行执行，但是同一个作业内没有前趋关系的程序段或不同作业的程序段可以分别在CPU和各输入/输出部件上并行执行。例如，某系统中有一个CPU、一台输入设备和一台输出设备，每个作业具有3个程序段输入 $I_i$ 、计算 $C_i$ 和输出 $P_i (i = 1, 2, 3)$ 。下图为3个作业的各程序段并发执行的前驱图。

从上图中可以看出， $I_2$ 与 $C_1$ 并行执行： $I_3$ 、 $C_2$ 与 $P_1$ 并行执行； $C_3$ 与 $P_2$ 并行执行。其中， $I_2$ 、 $I_3$ 受到 $I_1$ 的间接制约， $C_2$ 、 $C_3$ 受到 $C_1$ 的间接制约， $P_2$ 、 $P_3$ 受到 $P_1$ 的间接制约，而 $C_1$ 、 $P_1$ 受到 $I_1$ 的直接制约，等等。

程序并发执行时的特征如下。

（1）失去了程序的封闭性。
（2）程序和机器的执行程序的活动不再一一对应。
（3）并发程序间的相互制约性。

例如，两个并发执行的程序段完成交通流量的统计，其中，“观察者” $P_1$ 识别通过的车辆数，“报告者” $P_2$ 定时将观察者的计数值清零，程序实现如下。

【P1】

L1:if 有车通过 then COUNT := COUNT + 1;
 GOTO L1;

【P2】

L2: 
PRINT COUNT;
COUNT := 0
GOTO L2;

对于上例，由于程序可并发执行，所以可能有以下3种执行序列。

① COUNT := COUNT + 1; PRINT COUNT; COUNT := 0
② PRINT COUNT; COUNT := 0; COUNT := COUNT + 1
③ PRINT COUNT; COUNT := COUNT + 1; COUNT := 0

假定COUNT的某个循环的初值为n，那么这3种执行序列得到的COUNT结果不同，如下表所示。

执行序列	COUNT打印的值	COUNT执行后的值
①	n + 1	0
②	n	1
③	n	0

这种不正确结果的发生是因为两个程序 $P_1$ 和 $P_2$ 共享变量COUNT引起的，即程序并发执行破坏了程序的封闭性和可再现性，使得程序和执行程序的活动不再一一对应。为了解决这一问题，需要研究进程间的同步与互斥问题。

进程是程序的一次执行，该程序可以和其他程序并发执行。进程通常是由程序、数据和进程控制块（Process Control Block，PCB）组成的。

（1）PCB。PCB是进程存在的唯一标志，其主要内容如下表所示。

信息	含义
进程标识符	标明系统中的各个进程
状态	说明进程当前的状态
位置信息	指明程序及数据在主存或外存的物理位置
控制信息	参数、信号量、消息等
队列指针	链接同一状态的进程
优先级	进程调度的依据
现场保护区	将处理机的现场保护到该区域，以便再次调度时能继续正确运行
其他	因不同的系统而异

（2）程序。程序部分描述了进程需要完成的功能。假如一个程序能被多个进程同时共享执行，那么这一部分就应该以可再入（纯）码的形式编制，它是程序执行时不可修改的部分。

（3）数据。数据部分包括程序执行时所需的数据及工作区。该部分只能为一个进程所专用，是进程的可修改部分。

在多道程序系统中，进程在处理器上交替运行，状态也不断地发生变化，因此进程一般有3种基本状态：运行、就绪和阻塞。下图显示了进程基本状态及其转换，也称三态模型。

（1）运行。当一个进程在处理机上运行时，则称该进程处于运行状态。显然，对于单处理机系统，处于运行状态的进程只有一个。
（2）就绪。一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态。
（3）阻塞。阻塞也称等待或睡眠状态，一个进程正在等待某一事件发生（例如请求I/O等待I/O完成等）而暂时停止运行，这时即使把处理机分配给进程也无法运行，故称该进程处于阻塞状态。

事实上，对于一个实际的系统，进程的状态及其转换更复杂。例如，引入新建态和终止态构成了进程的五态模型，如下图所示。

其中，新建态对应于进程刚刚被创建时没有被提交的状态，并等待系统完成创建进程的所有必要信息。因为创建进程时分为两个阶段，第一个阶段为一个新进程创建必要的管理信息，第二个阶段让该进程进入就绪状态。由于有了新建态，操作系统往往可以根据系统的性能和主存容量的限制推迟新建态进程的提交。

类似地，进程的终止也可分为两个阶段，第一个阶段等待操作系统进行善后处理，第二个阶段释放主存。

由于进程的不断创建，系统资源特别是主存资源已不能满足进程运行的要求。这时，就必须将某些进程挂起，放到磁盘对换区，暂时不参加调度，以平衡系统负载。或者是系统出现故障，或者是用户调试程序，也可能需要将进程挂起检查问题。下图是具有挂起状态的进程状态及其转换。

（1）活跃就绪。活跃就绪是指进程在主存并且可被调度的状态。
（2）静止就绪。静止就绪是指就绪进程被对换到辅存时的状态，它是不能被直接调度的状态，只有当主存中没有活跃就绪态进程，或者是挂起态进程具有更高的优先级时，系统将把挂起就绪态进程调回主存并转换为活跃就绪。
（3）活跃阻塞。活跃阻塞是指进程在主存，一旦等待的事件产生便进入活跃就绪状态。
（4）静止阻塞。静止阻塞是指阻塞进程对换到辅存时的状态，一旦等待的事件产生便进入静止就绪状态。

进程控制就是对系统中的所有进程从创建到消亡的全过程实施有效的控制。为此，操作系统设置了一套控制机构，该机构的主要功能包括创建一个新进程，撤销一个已经运行完的进程，改变进程的状态，实现进程间的通信。进程控制是由操作系统内核（Kernel）中的原语实现的。内核是计算机系统硬件的首次延伸，是基于硬件的第一层软件扩充，它为系统对进程进行控制和管理提供了良好的环境。

原语（Primitive）是指由若干条机器指令组成的，用于完成特定功能的程序段。原语的特点是在执行时不能被分割，即原子操作要么都做，要么都不做。内核中所包含的原语主要有进程控制原语、进程通信原语、资源管理原语以及其他方面的原语。属于进程控制方面的原语有进程创建原语、进程撤销原语、进程挂起原语、进程激活原语、进程阻塞原语以及进程唤醒原语等。不同的操作系统内核所包含的功能不同，但大多数操作系统的内核都包含支撑功能和资源管理的功能。

在多道程序环境的系统中存在多个可以并发执行的进程，故进程间必然存在资源共享和相互合作的问题。进程通信是指各个进程交换信息的过程。

同步是合作进程间的直接制约问题，互斥是申请临界资源进程间的间接制约问题。

在计算机系统中，多个进程可以并发执行，每个进程都以各自独立的、不可预知的速度向前推进，但是需要在某些确定点上协调相互合作进程间的工作。例如，进程A向缓冲区送数据，进程B从缓冲区取数据加工，当进程B要取数据加工时，必须是进程A完成了向缓冲区送数据的操作，否则进程B必须停下来等待进程A的操作结束。

可见，所谓进程间的同步是指在系统中一些需要相互合作，协同工作的进程，这样的相互联系称为进程的同步。

进程的互斥是指系统中多个进程因争用临界资源而互斥执行。在多道程序系统环境中，各进程可以共享各类资源，但有些资源一次只能供一个进程使用，称为临界资源（Critical Resource，CR），如打印机、共享变量和表格等。

临界区（Critical Section，CS）是进程中对临界资源实施操作的那段程序。对互斥临界区管理的4条原则如下。

（1）有空即进。当无进程处于临界区时，允许进程进入临界区，并且只能在临界区运行有限的时间。
（2）无空则等。当有一个进程在临界区时，其他欲进入临界区的进程必须等待，以保证进程互斥地访问临界资源。
（3）有限等待。对于要求访问临界资源的进程，应保证进程能在有限的时间进入临界区，以免陷入“饥饿”状态。
（4）让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等状态。

荷兰学者Dijkstra于1965年提出的信号量机制是一种有效的进程同步与互斥工具。目前，信号量机制有了很大的发展，主要有整型信号量、记录型信号量和信号量集机制。

信号量是一个整型变量，根据控制对象的不同被赋予不同的值。信号量分为如下两类：
（1）公用信号量。实现进程间的互斥，初值为1或资源的数目。
（2）私用信号量。实现进程间的同步，初值为0或某个正整数。

信号量S的物理意义： $S \ge 0$ 表示某资源的可用数，若 $S < 0$ ，则其绝对值表示阻塞队列中等待该资源的进程数。

对于系统中的每个进程，其工作的正确与否不仅取决于它自身的正确性，而且与它在执行中能否与其他相关进程正确地实施同步互斥有关。PV操作是实现进程同步与互斥的常用方法：P操作和V操作是低级通信原语，在执行期间不可分割。其中，P操作表示申请一个资源，V操作表示释放一个资源。

P操作的定义：S := S - 1，若 $S \ge 0$ ，则执行P操作的进程继续执行：若 $S < 0$ ，则置该进程为阻塞状态（因为无可用资源），并将其插入阻塞队列。

P操作可用如下过程表示，其中，Semaphore表示所定义的变量是信号量。

procedure P(var S : Semaphore);
 begin
 S := S - 1;
 If S < 0 then W(S); {执行P操作的进程插入等待队列}
 end;

V操作定义：S := S + 1，若 $S >0$ ，则执行V操作的进程继续执行，若 $S \le 0$ ，则从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续。

V操作可用如下过程表示。

procedure V(var S : Semaphore);
 begin
 S := S + 1;
 If S <= 0 then R(S); {从阻塞队列中唤醒一个进程}
 end;

令信号量mutex的初值为1，当进入临界区时执行P操作，退出临界区时执行V操作。这样，利用PV操作实现进程互斥的代码段如下：

P(mutex);临界区V(mutex);

【例4.1】将交通流量统计程序改写如下，可实现 $P_1$ 和 $P_2$ 间的互斥。

【P1】

L1:if 有车通过 then begin
 P(mutex);
 COUNT := COUNT + 1;
 V(mutex);
 end
 GOTO L1;

【P2】

L2: 
begin
 P(mutex);
 PRINT COUNT;
 COUNT := 0
 V(mutex);endGOTO L2;

进程的同步是由于进程间合作引起的相互制约的问题，要实现进程的同步可用一个信号量与消息联系起来，当信号量的值为0时表示希望的消息未产生，当信号量的值为非0时表示希望的消息已经存在。假定用信号量S表示某条消息，进程可以通过调用P操作测试消息是否到达，调用V操作通知消息已准备好。最典型的同步问题是单缓冲区的生产者和消费者的同步问题。

【例4.2】生产者进程 $P_1$ 不断地生产产品送入缓冲区，消费者进程 $P_2$ 不断地从缓冲区中取产品消费。请给出实现进程同步的模型图。

解：为了实现 $P_1$ 与 $P_2$ 进程间的同步问题，需要设置两个信号量 $S_1$ 和 $S_2$ ，但信号量初值不同可有如下两种实现方案。

方案1：信号量 $S_1$ 的初值为1，表示缓冲区空，可以将产品送入缓冲区；信号量 $S_2$ 的初值为0，表示缓冲区有产品。其同步过程如下图所示。

方案2：信号量 $S_1$ 的初值为0，信号量 $S_2$ 的初值为0，此时同步过程如下图所示。

【例4.3】一个生产者和一个消费者，缓冲区中可存放n件产品，生产者不断地生产产品，消费者不断地消费产品，如何用PV操作实现生产者和消费者的同步。可以通过设置3个信号量S、 $S_1$ 、 $S_2$ 和，其中，S是一个互斥信号量，初值为1，因为缓冲区是一个互斥资源，所以需要进行互斥控制； $S_1$ 表示是否可以将产品放入缓冲区，初值为n； $S_2$ 表示缓冲区是否存有产品，初值为0。其同步过程如下图所示。

进程间通信是指进程之间的信息交换，少则一个信息，多则成千上万个信息。根据交换信息量的多少和效率的高低，进程通信的方式分为低级方式和高级方式。PV操作属于低级通信方式，若用PV操作实现进程间通信，则存在如下问题。

为了提高信号通信的效率，传递大量数据，降低程序编制的复杂度，系统引入了高级通信方式。高级通信方式主要分为共享存储模式、消息传递模式和管道通信。

（1）共享存储模式。相互通信的进程共享某些数据结构（或存储区）实现进程之间的通信。
（2）消息传递模式。进程间的数据交换以消息为单位，程序员直接利用系统提供的一组通信命令（原语）来实现通信，如Send(A)、Receive(A)。
（3）管道通信。所谓管道，是指用于连接一个读进程和一个写进程，以实现它们之间通信的共享文件（pipe文件）。向管道（共享文件）提供输入的发送进程（即写进程），以字符流的形式将大量的数据送入管道；而接收进程可从管道接收大量的数据。由于它们通信时采用管道，所以称为管道通信。

若用信号量和P、V操作来解决进程的同步与互斥问题，需要在程序中的适当位置安排P、V操作，否则会造成死锁错误。为了解决分散编程带来的困难，1974年和1975年汉森（Brinch Hansen）和霍尔（Hoare）提出了另一种同步机制——管程（Monitor），其基本思路是采用资源集中管理的方法，将系统中的资源用某种数据结构抽象地表示出来。由于临界区是访问共享资源的代码段，建立一个管程管理进程提出的访问请求。

采用这种方式对共享资源的管理就可以借助数据结构及在其上实施操作的若干过程来进行，对共享资源的申请和释放可以通过过程在数据结构上的操作来实现。

管程由一些共享数据、一组能为并发进程所执行的作用在共享数据上的操作的集合、初始代码以及存取权组成。管程提供了一种可以允许多进程安全、有效地共享抽象数据类型的机制，管程实现同步机制由“条件结构（Condition Construct）”所提供。为实现进程互斥同步，必须定义一些条件变量，例如var notempty, notfull：condition，这些条件变量只能被wait和signal操作所访问。notfull.walt操作意味着调用该操作的进程将被挂起，使另一个进程执行：而notfull.signal操作仅仅是启动一个被挂起的进程，如无挂起进程，则notfull.signal操作相当于空操作，不改变notfull状态，这不同于V操作。

每一个管程都要有一个名字以供标识，用语言来写一个管程的形式如下：

Type <管程名> = monitor
 <管程变量说明>;
 define <（能被其他模块引用的）过程名列表>;
 procedure <过程名>(<形式参数表>)
 begin
 <过程体>;
 end;
 ...
 procedure <过程名>(<形式参数表>)
 begin
 <过程体>;
 end;
 begin
 <管程的局部数据初始化语句>;
 end;

【例4.4】建立一个管程Producer-Consumer，它包括两个过程put(item)和get(item)，分别执行将生产的消息放入缓冲池和从缓冲池取出消息的操作，设置变量count表示缓冲池已存消息的数目。管程描述如下：

Type Producer-Consumer = monitor
 var buffer : array[(0, ..., n-1] of item; {定义缓冲区}
 in, out, count : integer; {in/out为存取指针，count为缓冲区产品个数}
 notfull, notempty : condition; {条件变量}

 procedure entry put(item)
 begin
 if count >= n then notfull.wait; {缓冲区已满}
 buffer(in) := nextp;
 in := (in + 1) mod n;
 count := count + 1;
 if notempty.queue then noempty.signal; {唤醒等待者}
 end;
 procedure entry get(item)
 begin
 if count <= 0 then notempty.wait; {缓冲区已空}
 nextc := buffer(out);
 out := (out + l) mod n;
 count := count - 1; {减少一个产品}
 if notfull.queue then notfull.signal; {唤醒等待者}
 end;
 begin
 in := out := 0;
 count := 0;
 end;

利用管程解决生产者-消费者问题，其中生产者和消费者程序如下：

cobegin
 producer : begin
 repeat
 produce an item in nextp;
 Producer-Consumer.put(item);
 until false;
 end;
 consumer : begin
 repeat
 Producer-Consumer.get(item);
 consume the item in nextc;
 until false;
 end;
coend

进程调度方式是指当有更高优先级的进程到来时如何分配CPU。调度方式分为可剥夺和不可剥夺两种。可剥夺式是指当有更高优先级的进程到来时，强行将正在运行进程的CPU分配给高优先级的进程；不可剥夺式是指当有更高优先级的进程到来时，必须等待正在运行进程自动释放占用的CPU，然后将CPU分配给高优先级的进程。

在某些操作系统中，一个作业从提交到完成需要经历高、中、低三级调度。

（1）高级调度。高级调度又称“长调度”“作业调度”或“接纳调度”，它决定处于输入池中的哪个后备作业可以调入主系统做好运行的准备，成为一个或一组就绪进程。在系统中一个作业只需经过一次高级调度。

（2）中级调度。中级调度又称“中程调度”或“对换调度”，它决定处于交换区中的哪个就绪进程可以调入内存，以便直接参与对CPU的竞争。在内存资源紧张时，为了将进程调入内存，必须将内存中处于阻塞状态的进程调出至交换区，以便为调入进程腾出空间。这相当于使处于内存的进程和处于硬盘交换区的进程交换了位置。

（3）低级调度。低级调度又称“短程调度”或“进程调度”，它决定处于内存中的哪个就绪进程可以占用CPU。低级调度是操作系统中最活跃、最重要的调度程序，对系统的影响很大。

常用的进程调度算法有先来先服务、时间片轮转、优先级调度和多级反馈调度算法。

（1）先来先服务（FCFS）。FCFS按照作业提交或进程成为就绪状态的先后次序分配CPU，即进程调度总是将就绪队列队首的进程投入运行。FCFS的特点是比较有利于长作业，而不利于短作业；有利于CPU繁忙的作业，而不利于I/O繁忙的作业。FCFS算法主要用于宏观调度。

（2）时间片轮转。时间片轮转算法主要用于微观调度，其设计目标是提高资源利用率。通过时间片轮转提高进程并发性和响应时间特性，从而提高资源利用率。时间片的长度可以从几毫秒到几百毫秒，选择的方法一般有如下两种。
①固定时间片。分配给每个进程相等的时间片，使所有进程都公平执行，它是一种实现简单且有效的方法。
②可变时间片。根据进程不同的要求对时间片的大小实时修改，可以更好地提高效率。

（3）优先级调度：优先级调度算法是让每一个进程都拥有一个优先数，数值大的表示优先级高，系统在调度时总选择优先数大的占用CPU，优先级调度分为静态优先级和动态优先级两种。
①静态优先级。进程的优先级在创建时确定，直到进程终止都不会改变。通常根据以下因素确定优先级：进程类型（如系统进程优先级较高）、对资源的需求（如对CPU和内存需求较少的进程优先级较高）、用户要求（如紧迫程度和付费多少）。
②动态优先级。在创建进程时赋予一个优先级，在进程运行过程中还可以改变，以便获得更好的调度性能。例如，在就绪队列中，随着等待时间增长，优先级将提高。这样，对于优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行。进程每执行一个时间片，就降低其优先级，从而当一个进程持续执行时，其优先级会降低到让出CPU。

（4）多级反馈调度。多级反馈队列调度算法如下图所示，该算法是时间片轮转算法和优先级算法的综合与发展。其优点有三个方面：第一，照顾了短进程以提高系统吞吐量、缩短了平均周转时间，第二，照顾I/O型进程以获得较好的I/O设备利用率和缩短响应时间；第三不必估计进程的执行时间，动态调节优先级。

多级反馈队列调度算法实现思路如下。
①设置多个就绪队列。队列1，队列2，……，队列n分别赋予不同的优先级， $队列1的优先级 \ge 队列2的优先级 \ge ... \ge 队列n的优先级$ 。每个队列执行时间片的长度也不同，规定优先级越低时间片越长，如逐级加倍。
②新进程进入内存后，先投入队列1的末尾，按FCFS算法调度：若某进程在队列1的一个时间片内未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度：如此下去，当进程降低到最后的队列时，则按“时间片轮转”算法调度直到完成。
③仅当较高优先级的队列为空才调度较低优先级队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。

优先级确定需要考虑如下情况。

（1）对于I/O型进程，让其进入最高优先级队列，以及时响应需要I/O交互的进程。通常执行一个小的时间片，在该时间片内要求可处理完一次I/O请求的数据，然后转入到阻塞队列。
（2）对于计算型进程，每次都执行完时间片后进入更低级队列。最终采用最大时间片来执行，以减少调度次数。
（3）对于I/O次数不多，主要是CPU处理的进程，在I/O完成后，返回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。
（4）为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级。

在计算机系统中有许多互斥资源（如磁带机、打印机和绘图仪等）或软件资源（如进程表、临界区等），若两个进程同时使用打印机，或同时进入临界区必然会出现问题。所谓死锁，是指两个以上的进程互相都要求对方已经占有的资源导致无法继续运行下去的现象。

【例4.5】进程推进顺序不当引起的死锁。设系统中有一台读卡机A，一台打印机B，它们被进程 $P_1$ 和 $P_2$ 共享，两个进程并发执行，它们按下列顺序请求和释放资源。

【P1】...Request(A)<a>; Request(B); Release(B); Release(A);

【P2】...Request(B)<a>; Request(A); Release(A); Release(B);

假如按 $P_1 <a>$ $P_2 <a>$ $P_1 $ $P_2 $ 的次序执行，则系统会发生死锁。因为进程 $P_1 <a>$ 时，由于读卡机未被占用，所以请求可以得到满足；进程 $P_2 <a>$ 时，由于打印机未被占用，所以请求也可以得到满足。接着 $P_1 $ 时，由于打印机被占用，所以请求得不到满足， $P_1$ 等待；进程 $P_2 $ 时，由于读卡机被占用，所以请求得不到满足， $P_2$ 也等待，导致互相在请求对方已占有的资源，系统发生死锁。

【例4.6】同类资源分配不当引起死锁。若系统中有m个资源被个进程共享，当每个进程都要求k个资源，而m < n * k时，即资源数小于进程所要求的总数时，可能会引起死锁。例如，m = 5，n = 3，k = 3，若系统采用的分配策略是轮流地为每个进程分配，则第一轮系统先为每个进程分配一台，还剩下两台；第二轮系统再为两个进程各分配一台，此时，系统中已无可供分配的资源，使得各个进程都处于等待状态导致系统发生死锁。

【例4.7】PV操作使用不当引起的死锁。对于下图，当信号量 $S_1 = S_2 = 0$ 时将发生死锁。

从上图可知， $P_2$ 进程从缓冲区取产品前，先执行 $P(S_2)$ ，由于 $S_2 = -1$ ，故 $P_2$ 等待； $P_1$ 进程将产品送到缓冲区后，执行 $P(S_1)$ ，由于 $S_1 = -1$ ，故 $P_1$ 等待。这样， $P_1$ 、 $P_2$ 进程都无法继续运行下去，导致系统死锁。

从上述例题分析可以看出，产生死锁的原因为竞争资源及进程推进顺序非法。当系统中有多个进程所共享的资源不足以同时满足它们的需求时，将引起它们对资源的竞争导致死锁。进程推进顺序非法，指进程在运行的过程中请求和释放资源的顺序不当，导致进程死锁。产生死锁的4个必要条件是互斥条件、请求保持条件、不可剥夺条件和环路条件。

当发生死锁时，在进程资源有向图中必构成环路，其中每个进程占有了下一个进程申请的一个或多个资源，如下图所示。

死锁的处理策略主要有4种：鸵鸟策略（即不理睬策略）、预防策略、避免策略和检测与解除死锁。

死锁预防是采用某种策略限制并发进程对资源的请求，破坏死锁产生的4个必要条件之一，使系统在任何时刻都不满足死锁的必要条件。预防死锁的两种策略如下。

死锁预防是设法破坏产生死锁的4个必要条件之一，严格防止死锁的产生。死锁避免则不那么严格地限制产生死锁的必要条件。最著名的死锁避免算法是Dijkstra提出的银行家算法，死锁避免算法需要很大的系统开销。

银行家算法对于进程发出的每一个系统可以满足的资源请求命令加以检测，如果发现分配资源后系统进入不安全状态，则不予分配：若分配资源后系统仍处于安全状态，则实施分配。与死锁预防策略相比，它提高了资源的利用率，但检测分配资源后系统是否安全增加了系统开销。

所谓安全状态，是指系统能按某种顺序如 $(P_1, P_2, ..., P_n)$ 来为每个进程分配其所需资源，直到最大需求，使每个进程都可顺序完成。通常称 $(P_1, P_2, ..., P_n)$ 序列为安全序列。若系统不存在这样一个安全序列，则称系统处于不安全状态。

【例4.8】假设系统中有三类互斥资源 $R_1$ 、 $R_2$ 和 $R_3$ ，可用资源数分别为8、7和4。在 $T_0$ 时刻系统中有 $P_1$ 、 $P_2$ 、 $P_3$ 、 $P_4$ 和 $P_5$ 这5个进程，这些进程对资源的最大需求量和已分配资源数如下表所示。

进程	最大需求量R1/R2/R3	已分配资源数R1/R2/R3
P1	6/4/2	1/1/1
P2	2/2/2	2/1/1
P3	8/1/1	2/1/0
P4	2/2/1	1/2/1
P5	3/4/2	1/1/1

若有如下四个执行序列，那么进程按什么序列执行，系统是安全的。
① $P_1 → P_2 → P_4 → P_5 → P_3$

② $P_2 → P_1 → P_4 → P_5 → P_3$

③ $P_4 → P_2 → P_1 → P_5 → P_3$

④ $P_4 → P_2 → P_5 → P_1 → P_3$

解：初始时系统的可用资源数分别为8、7和4，在 $T_0$ 时刻已分配资源数分别为7、6和4，因此系统剩余的可用资源数分别为1、1和0。

由于 $R_3$ 资源为0，系统不能再分配 $R_3$ 资源了，所以不能一开始就运行需要分配 $R_3$ 资源的进程 $P_1$ 和 $P_2$ ，故①和②显然是不安全的。

分析序列③的 $P_4 → P_2 → P_1 → P_5 → P_3$ 是否安全。进程 $P_4$ 可以设置能完成标志True，如下表所示。

进程	可用	需求	已分配	可用+已分配	能否完成标志
P4	1/1/0	1/0/0	1/2/1	2/3/1	True
P2	2/3/1	0/1/1	2/1/1	4/4/2	True
P1	4/4/2	5/3/1	1/1/1

因为系统的可用资源数为（1，1，0），而进程 $P_4$ 只需要一台 $R_1$ 资源。进程 $P_2$ 可以设置能完成标志True，因为 $P_4$ 进程运行完毕将释放所有资源，此时系统的可用资源数应为（2，3，1），而进程 $P_2$ 只需要（0，1，1），进程 $P_2$ 运行完毕将释放所有资源，此时系统的可用资源数应为（4，4，2）。进程 $P_1$ 不能设置能完成标志True，因为进程需要 $R_1$ 资源为5，系统能提供的 $R_1$ 资源为4，所以序列③无法进行下去，因此， $P_4 → P_2 → P_1 → P_5 → P_3$ 为不安全序列。

序列 $P_4 → P_2 → P_5 → P_1 → P_3$ 是安全的，因为所有的进程都能设置完成标志True，如下表所示。

进程	可用	需求	已分配	可用+已分配	能否完成标志
P4	1/1/0	1/0/0	1/2/1	2/3/1	True
P2	2/3/1	0/1/1	2/1/1	4/4/2	True
P5	4/4/2	2/3/1	1/1/1	5/5/3	True
P1	5/5/3	5/3/1	1/1/1	6/6/4	True
P3	6/6/4	6/0/1	2/1/0	8/7/4	True

解决死锁的另一条途径是使用死锁检测方法，这种方法对资源的分配不加限制，即允许死锁产生。但系统定时地运行一个死锁检测程序，判断系统是否发生死锁，若检测到有死锁，则设法加以解除。

死锁解除通常采用如下方法。
（1）资源剥夺法。从一些进程那里强行剥夺足够数量的资源分配给死锁进程。
（2）撤销进程法。根据某种策略逐个地撤销死锁进程，直到解除死锁为止。

传统的进程有两个基本属性：可拥有资源的独立单位；可独立调度和分配的基本单位。引入线程的原因是进程在创建、撤销和切换中，系统必须为之付出较大的时空开销，故在系统中设置的进程数目不宜过多，进程切换的频率不宜太高，这就限制了并发程度的提高。引入线程后，将传统进程的两个基本属性分开，线程作为调度和分配的基本单位，进程作为独立分配资源的单位。用户可以通过创建线程来完成任务，以减少程序并发执行时付出的时空开销。

例如，在文件服务进程中可设置多个服务线程，当一个线程受阻时，第二个线程可以继续运行，当第二个线程受阻时，第三个线程可以继续运行……，从而显著地提高了文件系统的服务质量及系统的吞吐量。

这样，对于拥有资源的基本单位，不用频繁地切换，进一步提高了系统中各程序的并发程度。需要说明的是，线程是进程中的一个实体，是被系统独立分配和调度的基本单位。线程基本上不拥有资源，只拥有一点运行中必不可少的资源（如程序计数器、一组寄存器和栈），它可与同属一个进程的其他线程共享进程所拥有的全部资源。

线程也具有就绪、运行和阻塞3种基本状态。由于线程具有许多传统进程所具有的特性，故称为“轻型进程（Light-Weight Process）”传统进程称为“重型进程（Heavy-Weight Process）”。线程可创建另一个线程，同一个进程中的多个线程可并发执行。

线程分为用户级线程（User-Level Threads）和内核支持线程（Kernel-supported Threads）两类。用户级线程不依赖于内核，该类线程的创建、撤销和切换都不利用系统调用来实现：内核支持线程依赖于内核，即无论是在用户进程中的线程，还是在系统中的线程，它们的创建、撤销和切换都利用系统调用来实现。某些系统同时实现了两种类型的线程。

与线程不同的是，不论是系统进程还是用户进程，在进行切换时，都要依赖于内核中的进程调度。因此，不论是什么进程都是与内核有关的，是在内核支持下进行切换的。尽管线程和进程表面上看起来相似，但它们在本质上是不同的。

到此这篇进程控制块（什么是进程控制块）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！

上一篇：广度优先搜索是什么搜索（广度优先搜索是什么搜索引擎）

下一篇： jfif是什么意思（jlf是什么意思）

版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/70952.html

相关文章：