第二章 进程管理刘.docx
《第二章 进程管理刘.docx》由会员分享，可在线阅读，更多相关《第二章 进程管理刘.docx（54页珍藏版）》请在冰点文库上搜索。
第二章进程管理刘
第二章进程管理
为了描述程序在并发执行时对系统资源的共享，我们需要一个描述程序执行时动态特征的概念，这就是进程。
在本章中，我们将利用大约16个学时的时间来讨论进程概念、进程控制和进程间关系。
2.1进程（PROCESS）的概念
2.2进程控制
2.3进程互斥和同步
2.4经典进程的同步问题
2.5管程机制
2.6进程间通信（IPC,INTER-PROCESSCOMMUNICATION）
2.7线程
本章的教学要求：
◆掌握进程的基本概念、基本状态；掌握临界资源。
互斥与同步的概念，信号量机制和信号量、信号量机制的原理及用信号量解决同步与互斥问题，经典的生产者一消费者问题的实现；
◆理解进程状态变迁；理解经典的IPC问题（读者与写者、哲学家用餐）；理解进程通信的概念及主要方式，理解消息缓冲通信机制；理解线程的基本概念、
◆了解内核与进程控制过程；了解管程机制的原理，了解内核级和用户级线程、线程的同步与线程控制。
2.1进程（PROCESS）的概念
2.1.1前驱图和程序执行
2.1.2进程的定义和描述
2.1.3进程的基本状态
2.1.4进程模型实现机制
2.1.1前驱图和程序执行
2.1.1.1前驱图的定义
♦定义：
前驱图是一个有向无环图，不能存在循环。
图中
每个结点：
用于表示一条语句、一个程序段或一个进程；
每个有向边表示两个结点间存在的前驱关系”－>”；
－>＝{（Pi，Pj）|Pi必须先完成，Pj才能开始}
♦若（Pi，Pj）∈－>，则Pi－>Pj，称Pi是Pj的前驱，Pj是Pi的直接后继。
♦初始结点：
前驱图中没有前驱的结点；
♦终止结点：
前驱图中没有后继的结点；
♦结点的权重（Weight）：
该结点包含的程序量或结点的执行时间；
例如：
下图是包含7个结点的前驱图，P1是初始结点，P7是终止结点，存在如下的前驱关系：
P1－>P2,P1－>P3,P1－>P4,P2－>P5,P3－>P5,P4－>P6,P5－>P7,P6－>P7;
前驱图清楚地体现出了进程之间的先后顺序，可以很好地描述多进程的并发，以及合作进程之间严格的同步关系。
2.1.1.2程序顺序执行
程序是一个在时间上严格按先后次序操作的指令序列，顺序的各程序段之间、各指令之间，如果用前驱图描述，是一个简单的线性关系：
在单道程序设计环境下，程序运行时独占全机资源，计算机严格按程序规定的操作顺序执行，顺序程序具有如下基本特征：
1、顺序性：
CPU的操作严格按程序规定顺序执行，程序与机器执行程序的操作一一对应；
2、封闭性：
程序运行时，独占全机资源，程序运行结果仅由初始条件和程序本身决定，而不受任何外界因素影响；
3、可再现性：
程序顺序执行的结果与其执行速度无关，只要初始条件相同，无论是连续，还是断断续续执行，结果总是相同的。
2.1.1.3程序的并发执行
在硬件引入通道和中断机构后，就使得CPU与外部设备之间，外部设备与外部设备之间可以并行操作，在多道程序环境下，多个程序进入内存，并发执行。
什么叫并发执行呢？
内存的多个程序在操作系统的统一管理下，有的程序占用CPU，有的程序通过外设传递数据，从宏观上看是多道程序同时运行，从微观上看它们是交替执行（交替占用CPU），我们称这种多个程序在时间上重叠的执行为并发执行。
用前驱图可以很好地描述多个程序地并发执行，假设有N个程序并发，每个程序有输入段、计算段、打印段，分别记为Ii、Ci、Pi，则程序地前驱图如下：
前驱图中，存在如下五个前驱关系：
Ii－>Ci；Ii－>Ii+1；Ci－>Pi；Ci－>Ci+1；Pi－>Pi+1；即第i个程序必须按输入、计算、输出的顺序进行；输入完第一个，再输入第二个；计算完第一个，再计算第二个，输出完第一个，再输出第二个。
实际过程远比这个模型复杂。
上图实际上是多个作业的批处理情况。
前驱图中，重叠关系为：
Ii-1与Ci与Pi+1；
即第i－1个程序的输入、第i个程序的计算与第i+1个程序的打印输出，可以并发执行。
由于在多道程序环境下，计算机的资源已不再是被一个程序独占，而是由多个并发执行的程序所共享，共享提高了资源利用率，但由此带来的对资源的竞争，使得多道程序环境下程序的并发执行具有了与单道程序环境时的不同特征。
1、制约性：
由于多个程序对资源的竞争性共享，程序并发执行时存在互斥关系；当多个程序共同完成某个任务时，相互之间存在协调推进速度与步调的同步问题；两种情况下，程序间都存在相互制约的关系。
2、失去了封闭性
程序并发执行以资源共享为依据，由于资源的竞争性共享，因此，资源状态的改变不再依赖于某一个程序，而是由并发执行的多个程序共同决定，因此程序的执行失去了封闭性。
3、不可再现性
由于程序的执行失去了封闭性，因此，对一个程序来说，即使初始条件相同，但在程序每一次执行中，因资源状态受其它并发程序的影响每次并不相同，所以每次运行的结果可能不同。
例如：
设有公共变量N，进程A和进程B分别对N进行操作。
进程A进程B
N=N+1（a）print（N）（b）
N=0（c）
由于进程A和进程B各自以不可预测的速度推进，则可能出现以下几种情形：
（设某时刻N的值为n）
（1）（a）、（b）、（c），则N的值为n+1，n+1，n=0
（2）b、c、a，则N的值为n，0，1
（3）b、a、c，则N的值为n，n+1，0
因此，程序的并发执行不但于程序本身有关，而且于程序巡行时所处的运行环境有关，并发程序的活动已不再是静态的和封闭的，并发程序的运行结果可能与并发程序的执行速度、推进顺序有关，程序与机器执行指令间没有了一一对应的关系。
此时，传统的、静态的“程序”概念用于描述多道程序环境下的并发执行，已经不合适了，需要一个新的概念来描述与反映并发程序的执行。
这个概念就是“进程”。
另一方面，程序的不可再现性是无法容忍的，而不可再现性的出现，是由于不恰当的并发造成的，为此，必须研究在哪种条件下，允许程序并发而仍能保持其可再现性。
2.1.1.4程序并发执行的条件（Bernstein条件）
首先，引进两个概念：
读集：
程序Pi在执行期间所要读取的所有变量的集合，称为该程序的“读集”，记为
R（Pi）={a1、a2、a3、…am}
写集：
程序Pi在执行期间所要改变的所有变量的集合，称为该程序的“写集”，记为
W（Pi）={b1、b2、b3、…bm}
Bernstein条件：
若两个程序p1和p2能满足如下条件，则p1、p2可以在满足可再现性的前提下并发执行：
R（p1）∩W（p2）∪R（p2）∩W（p1）∪W（p1）∩W（p2）={}
例子：
设有如下四条语句：
读集写集
S1:
a＝x+yR（S1）={x,y}W（S1）={a}
S2:
b=z+1R（S2）={z}W（S2）={b}
S3:
c=a–bR（S3）={a,b}W（S3）={c}
S4:
d=c+1R（S4）={c}W（S4）={d}
据此判断S1和S2之间的Bernstein条件：
R（S1）∩W（S2）＝{}；R（S2）∩W（S1）＝{}；W（S1）∩W（S2）={};
S1和S3之间的Bernstein条件：
R（S1）∩W（S3）＝{}；R（S3）∩W（S1）＝{a}；不为{};
S1和S4之间的Bernstein条件：
R（S1）∩W（S4）＝{}；R（S4）∩W（S1）＝{}；W（S1）∩W（S4）={};
S2和S3之间的Bernstein条件：
R（S2）∩W（S3）＝{}；R（S3）∩W（S2）＝{b}；不为{};
S2和S4之间的Bernstein条件：
R（S2）∩W（S4）＝{}；R（S4）∩W（S2）＝{}；W（S2）∩W（S4）={};
S3和S4之间的Bernstein条件：
R（S3）∩W（S4）＝{}；R（S4）∩W（S3）＝{c}；不为{};
结论：
S1与S2、S1与S4、S2与S4、可以并发执行；
S1与S3、S2与S3、S3与S4不能并发执行，存在着前驱后继关系，必须用同步机制，限制它们的执行顺序。
2.1.2进程的定义及描述
为了能够描述多道程序环境下程序的并发执行，需要：
a）能描述并发程序的执行过程——“计算”；
b）能反映并发程序“执行——暂停——执行”的活动规律；
c）能协调多个并发程序的运行及资源共享；
这个新的概念就是进程（Process）。
所谓进程，是指一个可并发执行的程序在其一次运算所需数据集合上运行的过程。
多道程序环境下，计算机上所有可运行的软件，通常包括操作系统，被组织成若干进程，从概念上说，每个进程拥有自己的虚拟CPU、可执行的程序代码、程序数据和栈、程序计数器、栈指针、寄存器和所有运行时需要的信息。
但实际上，对CPU的占有是通过在进程之间快速切换实现的。
下图是有四个进程的多道程序环境概念模型。
进程与程序的区别非常重要，可以用做蛋糕来比喻：
一个计算机科学家正做蛋糕，他有做蛋糕的食谱（程序，用适当形式描述的算法，具有静态特征）、面粉、鸡蛋、糖等原料（数据），此时，计算机科学家就是处理机（CPU）。
科学家阅读食谱、取来原料，按步骤开始做蛋糕，这一系列行为，就是进程（动态性）。
此时，科学家的儿子哭着跑进来，说他的手被蜜蜂蛰了（另一个更高优先级的事件发生），科学家停下手中的活，并记下他照着食谱做到哪里了（保存当前进程的现场），然后拿出一本急救手册（另一个程序），按里面的程序取来急救用品（另一程序的数据），开始处理蛰伤（处理机从低优先级进程切换到高优先级进程）。
处理完毕后，科学家回到刚才停下来的地方（恢复现场）继续做蛋糕（再次调度刚才的进程）。
来看看进程与程序的区别，其具体区别如下：
◆进程是动态的，程序是静态的；
◆程序仅仅是外存中的可执行代码文件，进程不仅包括程序代码，还包括所处理的数据（数据区、CPU寄存器值、堆栈及指针等）与管理信息（进程控制块）
◆多个进程可以执行同一个程序（处理不同的数据）；
◆一个进程中不能同时执行多个程序，进程内的执行是顺序、串行的。
（相应的，进程间是可以并发的）
◆只有多任务、采用并发技术的系统中，才有进程的概念，单道、单任务环境下，不讲进程。
相应的，进程具有如下特性：
◆动态性：
进程是程序的一次执行，具有生命期，有“诞生——执行——消亡”的过程；
◆并发性：
这是引进进程概念的初衷，并发能有效提高系统资源利用率；
◆独立性：
进程是可以独立运行的基本单位，也是系统进行资源分配和调度的独立单位；
◆异步性：
各进程按各自独立的、不可预知的速度向前推进，由于单CPU系统中，任一时刻只有一个进程在运行，其它进程或等待I/O、或等待运行，系统按照某种调度算法，使CPU在各个进程之间切换，因此，进程具有”走走停停”的特征；
◆结构性：
为了描述和记录进程的运动变化过程，满足进程独立运行的要求，反映并控制并发进程的活动，系统为每个进程配置了一个进程控制块（PCB——ProcessControlBlock），于是，进程由程序段、数据段和PCB三部分组成。
2.1.3进程的基本状态
进程在其存在期间，由于各进程的并发执行以及相互制约而处于停停走走之中，进程的状态在不断发生着变化，进程的基本状态有三种，某些操作系统又增加两种，变成五种，还有第六种。
首先讨论基本三态及其转换。
一、
三种基本态及其转换
1、就绪态
进程获得了除CPU之外的所有资源，一旦得到CPU就立即可以运行。
多道程序环境下，处于就绪态的进程可能有多个，通常将它们组成一个就绪队列。
2、执行态
进程获得所有资源并正在CPU上运行。
在单CPU环境下，只能有一个进程处于执行态。
3、阻塞态（等待态）
正在CPU上运行的进程，由于某种原因（如等待I/O）不再具备运行条件而放弃CPU，暂停运行。
处于阻塞态的进程也可能有多个，组成阻塞队列。
分析基本的状态转换：
1、运行——》等待态：
因等待某事件发生，而无法进行；当前进程被排入等待队列（进程切换）；从就绪队列中选中一个就绪进程调度执行（进程调度）。
2、等待态——》就绪态：
当前等待的事件发生了（如I/O完成），一般由中断导致；该进程改为就绪态，并排入就绪态队列。
由于该进程已失去活动能力，无法改变自己的状态，一般在阻塞态进程被阻塞的事件解除时，由当前正运行的进程响应该事件，唤醒对应的阻塞态进程并将其状态改变为就绪态。
3、就绪态——》运行态：
该进程被调度选中；进程状态改为运行态，并从就绪队列中去掉；此种情况或者因目前处于运行态的进程时间片到，或因运行态进程因等待某事件而阻塞。
4、运行态——》就绪态：
仅在分时操作系统中出现，当系统分配的时间片用完，该进程将CPU的使用权让给下一个就绪进程使用，该进程除了CPU外，仍具备运行的所有条件，所以直接进入就绪队列。
5、等待态——》运行态：
从等待态一般不能直接进入运行态，因为就绪队列可能有多个，需要根据调度算法确定下一个运行的进程；但在一些现代操作系统中，允许高优先级进程直接进入运行态，这属于抢先式调度，引起该次状态转换的中断称为抢先式中断，相应地，从等待态进入就绪队列地转换方式属于非抢先式调度和非抢先式中断。
二、
五种状态及其转换（增加了新状态和终止状态）
除基本三态外，很多实际系统对进程状态有更细的划分，如建立态、终止态、睡眠态、活动态、长时间等待态、挂起态等。
下面研究五态模型，此模型在三态基础上又增加了两态：
1、新状态（建立状态）：
一个新进程刚刚建立，但还未进入就绪态的情形。
当建立新进程时，CPU上当前正在运行哪个进程？
——新进程的父进程。
2、终止状态（结束状态）一个进程已正常或非正常结束，但尚未撤销时的状态。
相应地，状态转换增加了下面两种：
1、新（建立）——》就绪、新——》运行
类似于等待——》运行时的情形，一般新进程直接进入就绪队列，但在抢先式调度中，可以直接进入运行态。
2、运行——》结束
无论正常还是非正常结束，都将把控制返回给操作系统，由操作系统进行进程结束的收尾工作。
对于一些系统态也可以中断的系统（如实时系统），为了防止将正在结束的进程又排入调度队列，将此时的进程设置为终止态，又叫僵尸进程，僵尸进程具有很高的优先级，以尽快结束并收回资源。
三、六种状态及其转换（增加了挂起状态）
此模型中，增加挂起状态，最常见的挂起状态有：
1、程序调试；
2、对换（内存中阻塞进程对换到外存）调整系统负荷；
3、
父进程协调作用，有时候父进程希望挂起某个子进程；
4、操作系统性能检查、记帐等工作。
相应地，状态转换增加如下几种：
a）活动就绪——》静止就绪；Suspend原语
b）活动阻塞——》静止阻塞：
Suspend原语
c）静止就绪——》活动就绪：
Active原语
d）静止阻塞——》活动阻塞；Active原语
2.1.4进程模型实现机制
为了实现进程模型，首先需要中断机制，其次是一组用于进程控制的子程序，然后还需要在内存中保持进程描述表（进程控制块表），
如图所示：
由于进程模型的实现是在操作系统核心实现的，因此，有必要首先介绍操作系统的内核和处理机的执行状态，然后介绍中断机制，再介绍进程管理功能及其实现。
一、操作系统内核与处理机执行状态
传统的操作系统采用分层结构，分层式操作系统的简略示意图如下：
◆系统态与用户态
为了防止操作系统关键数据被用户程序破坏，处理机的执行状态分成系统态和用户态。
系统态（核心态、管态）：
具有较高特权，能执行一切指令，访问所有寄存器。
用户态：
特权较低，只能执行规定的指令，访问指定的寄存器和存储区。
在一些实际系统中，系统被划分成更细的态，如Intel处理器的保护方式下，系统划分成4种特权级别0——3，以提供更细的保护机制。
微内核及客户机/服务器操作系统中，进程调度、进程控制等功能都以服务器进程形式运行于用户态，这是与传统操作系统不同的。
◆内核功能简介
内核功能分为两类：
一类是支撑功能，包括最重要的中断处理功能、作为运行调度基础的时间管理功能、以及实现原子操作的原语功能。
中断处理：
内核最基本的功能，是操作系统赖以活动的基础，如系统调用、键盘录入、进程调度、设备驱动以及文件管理等，都依赖于中断。
时钟管理：
操作系统的各种活动都需要，如时间片轮转。
原语操作：
原语（Primitive）：
由若干条机器指令构成的实现某特定功能的一段程序，原语本身是一条特殊的广义指令，其特殊性表现在原语的执行具有不可分割性，并以这种不可分割性保证操作的正确。
另一类是操作系统作为资源管理者实现的资源管理功能，包括进程管理、存储器管理、文件管理、设备管理功能。
与进程相关的有：
中断机制、原语操作、进程管理等。
下图是UNIX系统核心示意图。
二、处理机中断机制
所谓中断，是指计算机在执行程序过程中，当遇到需要立即处理的事件时，暂停当前程序的执行，转而去执行有关服务程序，处理完后自动返回原程序。
中断机制，是由处理机提供的，而中断后执行的功能，是由操作系统以中断处理程序的形式提供的。
操作系统中，把所有中断处理程序的地址集中在一张表中，称为中断向量表，以便快速查找并转向相应中断处理程序。
Intel体系结构的中断向量表共有256项，实方式下，每个向量4字节，前两个为IP，后两个字节为CS，占用物理内存低1KB。
保护方式下，中断向量表称为中断描述符表（IDT——InterruptDiscriptorTable），大小为2KB，通常位于内存前1MB，其基址由IDTR（InterruptDiscriptorTableRegister——中断描述符寄存器）指定。
每个中断描述符占8KB。
操作系统中的系统调用都是通过中断机制实现的，在操作系统内部，由系统调用分支程序通过系统调用分支表将调用功能号转换为相应的指令地址，系统调用分支程序的地址放在中断向量表中，在系统调用指令的内部执行过程中借用硬件中断机制自动转向该地址。
系统调用的内部实现过程如图所示：
系统通常在每两条指令执行之间检测是否有中断发生，若无，继续执行下一条指令，若有，则保存当前PC和PSW值，转向执行中断处理程序。
三、进程控制块表（PCB表）及其组织
◆PCB表
进程实体由进程控制块（PCB）、程序及数据集合三部分组成。
一个系统有一张进程控制块表（ProcessControlBlockTable——PCB表），每个进程占一行，称为该进程的进程控制块（PCB）。
每个PCB体现为C语言中的一个结构，PCB表体现为一个结构数组。
PCB:
是进程存在的唯一标志。
记录了操作系统所需的，用于描述进程情况及控制进程运行所需的全部信息，是进程并发执行的依据。
每个进程在创建时建立PCB，结束时回收PCB。
PCB中包含如下信息：
（1）进程标识符：
进程ID；
（2）处理机状态信息：
也就是本进程被中断时，处理机中各寄存器的当前值。
（3）进程调度信息：
包括进程状态、进程优先级。
引起进程阻塞的事件等等。
（4）进程控制信息：
包括进程中程序和数据的地址、进程同步与通信机制、资源清单等。
◆PCB表的组织
PCB表处在内存中，由操作系统统一管理，并随着进程的建撤而动态变化。
为了对PCB表进行有效管理，必须以一定的方式对其进行组织管理。
常用组织方式有以下几种：
◆线性表方式：
不论进程状态如何，将所有的PCB连续存放在内存的系统区。
这种方式管理简单，适用于系统中进程数量不多的情况，其缺点是检索速度慢，调度进程可能需哟阿查找整个PCB表。
◆链接表方式：
将处于相同状态的PCB组织成队列，从而形成运行队列、就绪队列和阻塞队列。
链接表方式要求每个PCB项（PCB表中的一行）增加一个指向同一队列中下一个PCB项的链指针，系统相应地为每个队列增加一个头指针（运行队列头指针。
就绪队列头指针、阻塞队列头指针）。
就绪队列的排队原则与进程的调度策略有关，而阻塞队列则可以根据阻塞原因排成几个阻塞队列，也可统一为一个阻塞队列。
◆索引方式：
将所有PCB组成一个表，根据进程状态建立几个相应的索引表（就绪索引表、阻塞索引表等），并将每个索引表的首地址记录于内存中专用单元中，由此提高检索速度。
2.2进程控制
为实现对进程的有效控制，操作系统必须具有创建一个新进程、撤销一个已运行结束的进程以及具有改变进程状态、实现进程间通信的能力，这些功能通过执行各种原语，由操作系统内核实现。
2.2.1进程的创建
进程创建由以下几种事件引起：
⏹用户登录，此时，外壳（shell）是新创建进程的父进程；
⏹作业调度：
批处理系统中，被调度的作业立即创建进程；
⏹提供服务：
如打印；
⏹应用请求：
由用户进程创建子进程，以完成特定的任务。
进程创建的过程：
1）申请空白PCB;
2）为新进程分配资源；
3）初始化PCB：
将有关参数（进程优先级、CPU的初始状态、内存大小、资源清单等）填入新PCB相应项中，并置新进程的状态为“就绪”；
4）将新PCB插入到进程的就绪队列中。
2.2.2进程的终止
当一个进程完成其规定的任务后应予以撤销，此时，程序正常结束，若发生异常则可能非正常结束。
程序结束时，都要将控制返回给操作系统，并作结束处理工作。
正常结束，就是程序按本身的逻辑有效地完成预定功能后结束（包括发生预料之中的错误并由用户的错误处理程序正常处理并返回用户程序的情况），此时，程序的最后一条语句——是一条“程序结束”系统调用指令，由用户态返回到核心态，由用户程序将控制返回到操作系统；
非正常结束，指发生了某些预料之外的错误导致程序在没有完成预定功能时提前结束，如被零除、地址越界、非法指令、硬件错误、I/O故障等。
此时，由硬件中断机制进入操作系统。
另一类非正常结束属于外界干预，如操作系统的干预、父进程请求终止等。
若父进程结束，子进程不一定结束，例如，UNIX的第一个进程是init系统进程，它是一切后继进程的父进程，UNIX规定，若一个进程结束，则它的所有未结束的子孙进程，将被init进程收养，作为init的子孙进程。
2.2.3进程的阻塞与唤醒
一、可以由如下事件引起运行态进程的阻塞：
请求系统服务：
往往由于访问系统临界资源而被阻塞，如对打印机的请求，这属于互斥。
只有当该资源被释放时，释放资源的进程发出唤醒信号将等待该资源的阻塞态进程唤醒；
等待某事件发生或完成：
或等待I/O完成，或等待协作进程完成某个操作，这属于同步。
此时，本进程被阻塞，I/O操作完成时，中断处理程序或写作进程唤醒该进程。
系统进程无工作可做时，自动阻塞，如发送进程。
二、阻塞原语block与唤醒原语wakeup
进程的阻塞是由进程自己调用进程控制原语block阻塞自己。
该原语的执行过程如下：
进程的唤醒是由释放该I/O的那个进程，或完成了被阻塞进程等待的任务的协作进程，在释放I/O或完成等待的任务时执行唤醒原语wakeup，将该阻塞进程唤醒。
该原语的执行过程如下：
2.2.4进程的挂起与激活
挂起原语
进程在执行过程中，根据用户或系统的某种需要，调用挂起原语将进程从活动状态转换为静止状态。
算法步骤：
1.根据外部标识检索PCB集，找到要挂起的PCB块；
2.检查
升级会员 