进程管理c语言.docx
《进程管理c语言.docx》由会员分享，可在线阅读，更多相关《进程管理c语言.docx（118页珍藏版）》请在冰点文库上搜索。
进程管理c语言
第2章进程管理
教学要点：
本章主要内容是程序的并发执行及进程的概念，进程的状态及其转换，进程的同步与互斥，进程通信与调度，进程死锁的概念及解决死锁的方法，线程的概念及其实现，Linux中进程的实现。
读者应重点掌握进程及线程的概念及其状态转换，实现进程同步与互斥的方法以及进程的各种调度策略。
掌握进程通信、死锁的概念及其解决方法，了解Linux中进程的实现技术。
操作系统中最核心的概念是进程，进程是对正在运行的程序的一种抽象，是资源分配和独立运行的基本单位，操作系统的所有内容都是围绕进程展开的，操作系统的四大特征也是基于进程而形成的。
所以操作系统的学习者和设计者都要尽早地理解进程。
本章就来阐述有关进程的问题
2.1进程的概念
2.1.1程序的并发执行
现在所有的计算机都能同时做几件事情。
在我们使用计算机运行程序的时候，时常会一边听着光盘上的音乐，一边从网上下载着软件，一边还编辑着文本文件。
在某一时段同时发生几件事的现象称为并发。
我们知道，计算机为我们自动地做某事，实际上是CPU自动执行存放在内存中的程序，同时做几件事就是同时执行几道不同的程序。
如果这几道程序同时在不同的CPU上执行，则称之为“并行”，如果它们分时地运行在同一个CPU上则称之为“并发”。
在单CPU条件下同时运行几道程序，从宏观上看，这几道程序是同时向前推进，但从微观上观察则是由单CPU按照时间段轮流执行每个程序的一小段，使每个程序都运行到程序的开始与结束之间的某一处。
从逻辑上讲，这几道程序都在运行，但从CPU的执行轨迹上观察，却是轮流地为每个程序执行一段时间，循环往复，直到所有程序依次完成。
我们目前使用的计算机几乎都是单CPU的机器，但是都能为我们同时完成几件不同的工作，就是采用的CPU分时原理。
因此，逻辑上的并行称为“并发”。
程序的并发执行是在多道程序环境下完成的，而在单道程序工作环境中，程序是顺序执行的。
程序的这两种不同的执行方式，体现出不同的特性。
1.程序的顺序执行及其特性
一个具有独立功能的程序独占CPU运行，直至得到最终结果的过程称为程序的顺序执行。
例如，用户要求计算机完成一道程序的运行时，通常先输入用户的程序和数据，然后运行程序进行计算，最后将结果打印出来。
假设系统中有2个程序，而每个程序都由三个程序段I、C、P组成，其中，I表示从输入机上读入程序的信息，C表示执行程序的计算过程，P表示在打印机上打印出程序的计算结果。
在单道环境下，每一程序的这三个程序只能是一个接一个地顺序执行，也就是输入、计算和打印三者串行工作，并且前一个程序结束后，才能执行下一个程序。
执行顺序如图2.1所示。
图2.1程序的顺序执行
由上述顺序程序的执行情况可以看出，程序的顺序执行具有如下特点：
①顺序性。
当顺序程序在CPU上执行时，CPU严格地顺序执行程序规定的动作，每个动作都必须在前一动作结束后才能开始。
除了人为的干预造成机器暂时停顿外，前一动作的结束就意味着后一动作的开始。
程序和计算机执行程序的活动严格一一对应。
②独占资源。
程序在执行过程中，独占全部资源，除了初始状态外，只有程序本身规定的动作才能改变这些资源的状态。
③结果无关性。
程序的执行结果与其执行速度无关。
也就是说，CPU在执行程序的两个动作之间如有停顿不会影响程序的执行结果，如果程序的初始条件不变，当重复执行时，一定能得到相同的结果。
上述特点概括起来就是程序的顺序性、封闭性和可再现性。
所谓顺序性指的是程序的各部分能够严格地按程序所确定的逻辑次序顺序地执行。
所谓封闭性指的是程序一旦开始执行，其计算结果就只取决于程序本身，除了人为改变机器运行状态或机器故障外，不受外界因素的影响。
所谓可再现性是指当该程序重复执行时，必将获得相同的结果。
这给程序的调试带来了很大的方便。
2.程序的并发执行及其特性
现代计算机在物理设计和逻辑设计中采用并行操作技术，使多种硬件设备能并行工作。
硬件的并行操作技术为程序的并发执行提供了物质基础。
在多道程序操作系统支持下，不但在多机系统中它可同时执行多个不同的程序，即使是在单机系统中，从逻辑上或宏观上看，多个程序也能并发执行。
对于任何一个程序i，其输入操作Ii、计算操作Ci、打印操作Pi这三者必须顺序执行，但对n个程序来说，则有可能并发执行。
例如：
输入程序在完成第i个程序的输入操作后，计算程序在对第i个程序进行计算的同时，可再启动输入程序，进行第i+1个程序的输入操作，这就使得第i+1个程序的输入操作和第i个程序的计算操作能并发执行。
图2.2给出了输入、计算、打印程序对一批程序进行处理的执行顺序。
在该例中I1先于Cl和I2，Cl先于Pl和C2，Pl先于P2，I2先于C2和I3，……。
这说明有些操作必须在其它操作之后执行，另外有些操作却可以并行地执行。
此外从图中可以看出：
I2与Cl、I3与C2与P1、I4与C3与P2是重叠的。
多道程序的并发执行大大地提高了系统的处理能力，改善了系统资源的利用效率。
图2.2程序的并发执行
程序的并发执行，是否还能保持顺序执行时的特性呢？
下面我们通过例子来说明程序并发执行时的特性。
设有观察者和报告者并行工作。
在一条单向行驶的公路上经常有卡车通过。
观察者不断观察并对通过的卡车计数，报告者定时地将观察者的计数值打印出来，然后将计数器重新清“0”。
此时我们可以写出如下程序，其中parbegin表示多个程序可以并发执行。
intn=0;
voidobserver（void）
{
while
（1）
{
…
n=n+1；
remainderofobserver；
}
}
voidreporter（void）
{
while（TRUE）
{
…
print（n）；
n=0；
remainderofreporter；
}
}
voidmain（）
{
parbegin（observer（）,reporter（））;
}
由于观察者和报告者各自独立地并行工作，n=n+1的操作，既可以在报告者的print（n）和n=0操作之前，也可以在其后，还可以在print（n）和n=0之间，即可能出现以下三种执行序列：
①n=n+1；print（n）；n=0；
②print（n）；n=0；n=n+1；
③print（n）；n=n+1；n=0；
假设在开始某个循环之前，n的值为s，则在完成一个循环后，对上述三个执行序列打印机打印的n值和执行后的n值如下表所示：
表2.1
执行序列
①
②
③
打印的值
s+1
s
s
执行后的值
0
1
0
由上表可见，由于观察者和报告者的执行速度不同，导致了计算结果的不同，这就是说，程序并发执行已丧失了顺序执行所保持的封闭性和可再现性。
而产生了如下一些新的特征：
①间断性
如果并发执行的程序与其它程序竞争资源失败而阻塞，或运行到一个时间片结束，它都会放弃CPU，使自己无法继续运行下去，但是当别的程序释放资源，使它能获得申请的资源并再次被调度选中时，它又能继续运行下去。
这就使并发执行的程序具有"执行—暂停—执行"的活动规律。
②失去封闭性
程序在并发执行时，多个程序共享系统中的所有资源，因此这些资源的使用状态将由多个程序改变，使程序运行失去了封闭性。
③不可再现性
由于程序的并发执行，打破了由某一道程序独占系统资源时的封闭性，也必将导致失去程序执行的可再现性。
程序的并发执行所表现出的特性说明以下两个问题：
⑴程序和计算机执行程序的活动不再一一对应
程序和计算机执行程序的活动是两个概念，程序是指令的有序集合，是静态的概念；而计算机执行程序的活动是指令序列在CPU上的执行过程，或CPU按照程序执行指令序列的过程。
通常把计算机执行程序的活动，称为“计算”，显然，“计算”是一个动态的概念。
如前所述，程序在顺序执行时，程序和“计算”之间保持一一对应的关系，但在并发执行时，一个并发程序可为多个用户作业调用，而使该程序处于多个“执行”过程中，从而形成了多个“计算”，这就是说，多个“计算’可能是在不同数据集上执行同一程序，所以程序和“计算”不再一一对应。
例如在分时系统中，内存中一个编译程序的副本同时为几个用户作业编译时，该编译程序的几次执行，便对应了几个“计算”。
⑵并发程序间存在相互制约关系
资源共享和程序的并发执行使得系统的工作情况变得错综复杂，尤其表现在系统中并发程序间的相互依赖和制约方面。
系统中各个并发程序的活动都有一定的独立性，它们分别提供一种用户或系统功能，如各用户作业的活动各提供一种用户需要的功能，它们之间相互独立，而又有相互依赖和制约关系。
像上例中的观察者与报告者程序，它们各自完成独立的工作，通过共享变量n又建立了相互依赖与制约关系。
又如，操作系统中对CPU的调度和对各种外部设备的控制活动，两者之间基本上也是独立的，各自提供一种系统功能。
这就是说，系统中各个并发程序活动具有独立性的一面，但在两个并发程序活动之间有时也会有相互依赖和相互制约关系。
程序之间的制约关系有两种：
直接制约关系和间接制约关系。
①直接制约关系通常是在彼此之间有逻辑关系的两个并发执行的程序之间发生的，一般是由于各个程序段要求共享信息引起的。
例如，一个正在执行的程序段需要另一程序段的计算结果，只有当另一程序段在某一时刻送来计算结果时，正在执行的程序段才能继续执行下去，否则它就一直等待，无法执行。
②间接制约关系是由于两个并发程序段由于竞争使用同一资源引起的，得到资源的程序段可以继续执行，得不到资源的程序段就只好暂停等待，直至获得可用资源时再继续运行。
正是因为在这些可以并发执行的程序段之间，存在着某种相互制约的关系，所以每个程序段的运行都与运行环境密切相关，它不仅要受到其它程序段活动的制约，而且还要依赖当时系统资源的分配情况。
因此，每个可以并发执行的程序段，都可能会因外界条件的限制而不能运行，被迫处于阻塞状态。
这样，对于这些可以并发执行的程序段，只用“程序”这一概念就不能说明问题的本质。
使用程序这一概念只能是简单、孤立、静止地研究分析它们，而不能深刻地揭示它们之间的内在活动、相互联系及状态变化。
因此，必须从变化的角度，动态地分析研究这些可以并发执行的程序段，真实地反映出系统的独立性、并发性、动态性和相互制约性。
为了准确地描述程序的执行过程，设计出高质量的操作系统，就不能再用静态的观点，而应该用动态的观点来刻画程序。
为此，在操作系统中引入了“进程”的概念。
2.1.2进程定义
如上所述，在多道程序的环境下，程序的并发执行代替了程序的顺序执行，它破坏了程序的封闭性和可再现性，使得程序和计算不再一一对应，而且由于资源共享和程序的并发执行导致在各个程序活动之间可能存在相互制约关系。
总之，程序活动不再处于一个封闭系统中，而出现了许多新的特征，即：
独立性、并发性、动态性和相互制约性。
在这种情况下，程序这个静态概念已经不能如实地反映程序活动的这些特征。
为此，20世纪60年代中期MULTICS系统的设计者和以E.W.Dijkstra为首的T.H.E系统的设计者开始广泛使用“进程”（process）这一新概念来描述系统和用户的程序活动。
进程是现代操作系统中的一个最基本也是最重要的概念，掌握这个概念对于理解操作系统实质，分析、设计操作系统都有其非常重要的意义。
但是，迄今为止，对这一概念尚无一个非常确切的、令人满意的、统一的定义，不同的人，站在不同的角度，对进程进行了不同的描述，下面列举几个操作系统的权威人士对“进程”所下的定义：
①行为的一个规则叫做程序，程序在CPU上执行时所发生的活动称为进程（Dijkstra）。
②一个进程是一系列逐一执行的操作，而操作的确切含义则有赖于我们以何种详尽程度来描述进程（Brinch.Hansen）。
③进程是这样的计算部分，它可以与别的进程并发执行（MadniekandDonovan）。
④顺序进程（有时称为任务）是一个程序与其数据集一道顺序通过CPU的执行所发生的活动（AlanC.Shaw）。
⑤一个进程是由伪CPU执行的一个程序（J.H.Saltzer）。
上述这些从不同角度对进程所做的解释或所下的定义，有些是近似的，有些则侧重某一方面，这说明进程这一概念尚未完全统一，但长期以来却巳广泛而成功地用于许多系统之中，成为构造操作系统的不可缺少的强有力的工具。
为了强调进程的并发性和动态性，我们给进程作如下定义：
进程是可并发执行的程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。
2.1.3进程状态及其转换
1.进程的三种基本状态及其转换
有了进程的概念，就可以用动态的观点分析进程的状态变化及相互制约关系。
由于进程执行时的间断性，决定了进程可能具有多种状态。
运行中的进程具有三种基本状态：
运行、阻塞、就绪，这三种状态构成了最简单的进程生命周期模型，进程在其生命周期内处于这三种状态之一，其状态将随着自身的推进和外界环境的变化而变化，由一种状态变迁到另一种状态。
①运行状态。
进程正在CPU上运行的状态，该进程已获得必要的资源，包括CPU，该程序正在CPU上运行。
在单CPU系统中，只有一个进程处于运行状态；在多CPU系统中，可以有多个进程处于运行状态。
②阻塞状态。
进程等待某种事件完成（例如，等待输入/输出操作的完成）而暂时不能运行的状态。
处于该状态的进程不能参加竞争CPU，因为此时即使分配给它CPU，它也不能运行。
③就绪状态。
等待CPU的状态。
该进程运行所需的一切资源，除CPU以外，都得到满足，但因CPU个数少于进程个数，所以该进程不能运行，而必须等待分配CPU资源，一旦获得CPU就立即投入运行。
在一个系统中，处于就绪状态的进程可能有多个，统称排成一个队列，称为就绪队列。
进程的各个状态变迁如图2.3。
就绪
I/O完成时间片完
进程调度
执行
阻塞
I/O请求
图2.3进程状态变迁图
①就绪→运行。
处于就绪状态的进程，已具备了运行的条件，但由于未能获得CPU，故仍然不能运行。
对于单CPU系统而言，因为处于就绪状态的进程往往不止一个，同一时刻只能有一个就绪进程获得CPU。
进程调度程序根据调度算法把CPU分配给某个就绪进程，建立该进程运行状态标记，并把控制转到该进程，把它由就绪状态变为运行状态，这样进程就投入运行。
即就绪状态的进程，一旦被调度进程选中，获得CPU，便发生此状态变迁。
②运行→阻塞。
处于运行状态的进程申请新资源而又不能立即被满足时，进程状态由运行变成阻塞。
如，运行中的进程需要等待文件的输入，系统便自动转入系统控制程序，进行文件输入，在文件输入过程中，该进程进入阻塞状态，而系统将控制转给进程调度程序，进程调度程序根据调度算法把CPU分配给处于就绪状态的其它进程。
即运行进程遇I/O请求时，发生此状态变迁。
③阻塞→就绪。
被阻塞的进程在其被阻塞的原因获得解除后，并不能立即投人运行，需要通过进程调度程序统一调度才能获得CPU，于是将其状态由阻塞状态变成就绪状态继续等待CPU。
仅当进程调度程序把CPU再次分配给它时，才可恢复曾被中断的现场继续运行。
即阻塞进程的I/O请求完成时，发生此状态变迁。
④运行→就绪。
这种状态变化通常出现在分时操作系统中。
一个正在运行的进程，由于规定运行时间片用完而使系统发出超时中断请求，超时中断处理程序把该进程的状态修改为就绪状态，并根据其自身的特征而插入就绪队列的适当位置，保存进程现场信息，收回CPU并转入进程调度程序。
于是，正在运行的进程就由运行状态变为就绪状态。
即运行进程时间片用完时，发生此状态变迁。
2.具有挂起状态的进程状态转换
在许多系统中，进程除了具有上述三种基本状态以外，又增加了一些新状态，其中最重要的是挂起状态，引入挂起状态的主要原因是内存资源不足。
另外当有终端用户请求、父进程请求、负荷调节需要等情况时，也要用到挂起状态。
引入挂起状态后，又将增加从挂起状态（又称为静止状态）到非挂起状态（又称为活动状态）的转换：
或者相反。
可有以下几种情况：
①活动就绪→静止就绪。
当进程处于未被挂起的就绪状态时，称此为活动就绪状态，当用挂起原语将该进程挂起后，该进程便转变为静止就绪状态，处于静止就绪状态的进程不再被调度执行。
②活动阻塞→静止阻塞。
当进程处于未被挂起的阻塞状态时，称它是处于活动阻塞状态，当用挂起原语将它挂起后，进程便转变为静止阻塞状态，处于静止阻塞状态的进程在其所期待的事件出现后，将从静止阻塞变为静止就绪。
③静止就绪→活动就绪。
处于静止就绪状态的进程，若用激活原语激活后，该进程将转变为活动就绪状态。
④静止阻塞→活动阻塞。
处于静止阻塞状态的进程，若用激活原语激活后，该进程将转变为活动阻塞状态。
具有挂起状态的进程状态变迁过程如图2.4。
2.1.4进程控制块
由于多个程序并发执行，各程序需要轮流使用CPU，当某程序不在CPU上运行时，必须保留其被中断的程序的现场，包括：
断点地址、程序状态字、通用寄存器的内容、堆栈内容、程序当前状态、程序的大小、运行时间等信息，以便程序再次获得CPU时，能够正确执行。
为了保存这些内容，需要建立—个专用数据结构，我们称这个数据结构为进程控制块PCB（ProcessControlBlock）。
进程控制块是进程存在的惟一标志，它跟踪程序执行的情况，表明了进程在当前时刻的状态以及与其它进程和资源的关系。
当创建一个进程时，实际上就是为其建立一个进程控制块。
执行
调度
请求I/O
挂起
时间片到
活动
就绪
静止
就绪
激活
挂起
释放
静止
阻塞
活动
阻塞
激活释放
挂起
图2.4具有挂起状态的进程状态变迁图
在通常的操作系统中，PCB应包含如下一些信息：
①进程标识信息。
为了标识系统中的各个进程，每个进程必须有惟一的标识名或标识数。
进程标识名，通常用字母和数字组成的“串”表示，进程标识数则是在一定数值范围内的进程编号。
有的系统用进程标识名作为进程的外部标识，它通常由创建者给出；用进程标识数作为进程的内部标识，通常由系统给出。
有的系统只用其中之一。
②位置信息。
指出进程的程序和数据部分在内存或外存中的物理位置。
③状态信息。
指出进程当前所处的状态，作为进程调度、分配CPU的依据。
④进程的优先级。
一般根据进程的轻重缓急程度为进程指定一个优先级，优先级用优先数表示。
进程调度程序根据优先数的大小，确定优先级的高低，并把CPU控制权交给优先级最高的进程。
⑤进程现场保护区。
当进程状态变化时（例如一个进程放弃使用CPU），它需要将当时的CPU现场保护到内存中，以便再次占用CPU时恢复正常运行，有的系统把要保护的CPU现场放在进程的工作区中，而PCB中仅给出CPU现场保护区起始地址。
⑥资源清单。
每个进程在运行时，除了需要内存外，还需要其它资源，如I/O设备、外存、数据区等。
这一部分指出资源需求、分配和控制信息。
⑦队列指针或链接字。
它用于将处于同一状态的进程链接成一个队列，在该单元中存放下一进程PCB首址。
⑧其它信息。
这里给出的只是一般操作系统中PCB所应具有的内容，不同操作系统的PCB结构是不同的，我们将在2.8节介绍Linux系统的PCB结构。
在一个系统中，通常可能有若干个进程同时存在，所以就拥有若干个PCB，为了能对PCB进行有效的管理，就要用适当的方法把这些PCB组织起来。
目前常用的PCB的组织方式有以下三种：
①线性表方式：
不论进程的状态如何，将所有的PCB连续地存放在内存的系统区。
这种方式适用于系统中进程数目不多的情况。
按线性方式组织PCB的情况如图2.5。
②链接表方式：
系统按照进程的状态将进程的PCB链接成队列，从而形成就绪队列、阻塞队列、运行队列等。
按链接方式组织PCB的情况如图2.6。
③索引表方式：
系统按照进程的状态分别建立就绪索引表、阻塞索引表等，通过索引表来管理系统中的进程。
按索引方式组织PCB的情况如图2.7。
PCB1
PCB2
PCB3
……
PCBn
图2.5线性方式组织PCB的示意图
PCB1
4
PCB2
3
PCB3
0
PCB4
8
PCB5
PCB6
7
PCB7
9
PCB8
0
PCB9
1
……
执行指针
就绪队列指针
阻塞队列指针
空闲队列指针
图2.6链接方式组织PCB的示意图
PCB1
PCB2
PCB3
PCB4
PCB5
PCB6
PCB7
PCB8
PCB9
……
执行指针
就绪索引表
3
9
……
就绪表指针
阻塞索引表
5
7
……
阻塞表指针
图2.7索引方式组织PCB的示意图
2.1.5进程的特性
前面我们通过程序并发执行时所产生的问题引出了进程的概念，并描述了进程、进程状态以及进程状态之间的转换，现在，我们对进程的特征进行梳理，以便更好地理解进程。
①进程具有动态性。
进程是程序的一次执行过程，一个进程可以看成是一组动作序列，而每个动作则是由执行一段指令序列来实现的，其结果是实现某种功能。
进程的动态性不仅表现在“程序的执行”，而且还表现在它由创建而产生，由调度而执行，由撤销而消亡的生命周期。
而程序是一组有序静态指令和数据的集合，用来指示CPU的操作，本身并不具有运动含义，是一种静态概念。
②进程具有并发性。
多个进程实体同存于内存中，在一段时间内可以同时运行。
并发性是进程的重要特性，也是操作系统的重要特性。
引入进程概念的目的，也正是为了描述和实现并发执行。
③进程具有结构特性。
从结构上看，进程是由程序段和相应的数据段及进程控制块构成的，程序只包含指令代码及相应数据。
④进程具有独立性。
进程是操作系统进行调度和分配资源的独立单位。
⑤进程具有异步性（不确定性）。
系统中的进程，按照各自的、不可预知的速度向前推进。
进程通常分为两类，一类是系统进程，另一类是用户进程。
它们的区别是：
①系统进程是操作系统用来管理系统资源并行活动的并发软件；用户进程是可以独立执行的用户程序段，它是操作系统提供服务的对象，是系统资源的实际使用者。
②系统进程之间的关系由操作系统自己负责，这样有利于增加系统的并行性，提高资源的利用率；用户进程之间的关系主要由用户自己负责，为了便于用户管理自己的任务，操作系统提供一套简便的任务调用命令作为协调手段，并在用户区根据用户作业的性质（是单任务还是多任务）装入相应的任务调度程序。
③系统进程直接管理有关的软、硬设备的活动；用户进程只能间接地和系统资源发生关系，当用户进程需要某种资源时，它必须向系统提出请求，由系统调度和分配。
④在进程调度中，系统进程的优先级高于用户进程。
无论是系统进程还是用户进程，对核心层来说它们都是基本的活动单位。
2.2进程控制
进程有由创建而产生，由调度而执行，由撤销而消亡的生命周期，因此操作系统要有对进程生命周期的各个环节进行控制的功能，这就是进程控制。
进程控制的职能是对系统中的全部进程实行有效的管理，其主要是对一个进程进行创建、撤销以及在某些进程状态间的转换控制。
通常允许一个进程创建和控制另一个进程，前者称为父进程，后者称为子进程，子进程又可创建其子进程，从而形成了一个树形结构的进程家族，如图2.8所示。
采用这种树形结构的方式，使得进程控制更为灵活方便。
进程的控制通常由原语完成。
所谓“原语”一般是指由若干条指令所组成，用来实现某个特定功能，在执行过程中不可被中断的
升级会员 