搜索
第2章进程管理第2章进程管理2.1进程的引入2.2进程定义与控制2.3进程调度2.4进程间的相互作用2.5进程通信2.6线程2.7UNIX进程模型习题第2章进程管理2.1进程的引入2.1.1顺序程序顺序程序是指程序在计算机上严格按照写入的顺序执行。顺序程序设计也就是指不同程序的按序执行。顺序程序设计具有以下主要特征：(1)顺序性：当多个程序在处理机上运行时，处理机严格按照程序结构所指定的顺序执行，程序的每一步都必须在上一步执行后才能开始。(2)资源独占性：一个程序在执行时，独占全部资源。(3)可再现性：如果程序的初始条件相同，则其执行的结果相同，与程序的执行速度无关，即在同一数据集上执行的结果均相同。第2章进程管理程序顺序执行的特征程序的顺序执行特征：–顺序性、封闭性、可再现性I1C1P1I2C2P2语句1语句2语句3语句4语句5第2章进程管理前趋图与前趋关系前趋图(PrecedenceGraph)–一个有向无循环图–描述程序或程序段之间执行的前后关系前趋关系“”–如果：(Pi,Pj)∈，也可以写成：PiPj–则称：Pi是Pj的直接前趋,Pj是Pi的直接后继–初始节点：没有前趋–终止节点：没有后继P1P2P3P8P6P5P7P4P9第2章进程管理2.1.2多道程序设计在第1章的内容里我们讲述了操作系统具有并发性、共享性、虚拟性和不确定性等特征。形成这些特征的原因就是引入了多道程序设计。采用多道程序设计技术，计算机中的CPU和外围设备的利用率得到了很大提高。第2章进程管理举一个“统筹方法”的例子，任务是沏一壶茶，清洗水壶需1分钟，烧开水需12分钟，拿茶叶需1分钟，洗茶壶需2分钟。如图2.1所示，如果按照上述顺序执行，总共花费16分钟。第2章进程管理16烧开水洗水壶拿茶叶洗茶壶130116烧开水洗水壶拿茶叶1301洗茶壶14图2.1统筹方法第2章进程管理为了更好地理解这种系统，我们来看一看图2.2。图2.2(a)描述了在一个多道程序的环境中，内存存放的四道程序顺序执行的情况。在这种情况下，四道程序总的运行时间为每个程序运行时间之和。在图2.2(b)中，将四道程序抽象成为四个各自拥有自己控制流程的独立运行单位(进程)，每个运行单位都有自己的运行环境。第2章进程管理AD程序顺序执行进程切换DBCCBA时间(a)(b)图2.2四道程序的执行(a)顺序执行；(b)四道程序并发执行的时间关系第2章进程管理程序的并发执行并发执行时的特征–间断性、失去封闭性、不可再现性I1C1P1I2C2P2I3C3P3I4C4P4第2章进程管理2.1.3程序并发执行的特性(1)程序结果的不可再现性。并发程序执行时，结果随执行的相对速度不同而变化，在不同的时间运行，结果各不相同。(2)独立性和制约性。独立性是指每一个程序都是一个相对独立的实体，用以实现不同的功能。(3)程序执行的间断性。并发执行的程序之间存在着相互制约的关系，这就意味着程序执行时间会不连贯。第2章进程管理(4)资源共享。多个程序可以使用同一资源。多道程序的引入就是为了提高资源利用率和系统效率，因此，如果程序不能并发执行，多道程序也就是失去了它存在的意义。(5)程序和计算的不一致。在顺序执行的程序中，程序和计算始终保持一一对应的关系，但在程序的并发执行中，程序执行的环境不同，这种对应关系将不复存在。第2章进程管理多道程序设计的特点如下：(1)多道。主存中有多道程序，它们在任一时刻必须处于就绪、运行、阻塞三种状态之一。(2)宏观上并行。从宏观上看，它们在同时执行。(3)微观上串行。从微观上看，它们在交替、穿插地执行。其主要优点是：(1)CPU的利用率高。(2)设备利用率高。(3)系统吞吐量大。第2章进程管理2.1.4与时间有关的错误在多道程序的执行当中，不可避免地会发生程序之间相互制约的情况。为了便于理解，我们先来看一个实际生活中遇到的例子——飞机订票系统。一个飞机订票系统可以有多个订票处的n个订票终端。如图2.3所示，现假设n=2，公共数据区为Hi(i=1,2,…,n)，分别存放各次班机的现存票数，T1和T2表示售票终端的进程，。T1和T2进程的程序如下：第2章进程管理T1:T2:公共数据区为Hi(i=1,2,…,n)，分别存放各次班机的现存票数，T1T2表示售票终端的进程，BeginBegin按乘客需要查找到Hi;按乘客需要查找到Hi;R1:=Hi;R2:=Hi;ifR1=1thenifR2=1thenBeginbeginR1:=R1-1;R2:=R2-1;Hi:=R1;Hi:=R2;售出一张票;售出一张票;endendelse{提示“票已售完”}；else{提示票已售完}；end;end;第2章进程管理HiT1T2…图2.3飞机订票系统模型第2章进程管理2.2进程定义与控制2.2.1进程的概念1．进程的定义许多科学家给进程下过定义，其中有些很相似，有些侧重的方面各异。其中，能够反映进程实质的定义有：(1)进程是程序的一次执行。(2)进程是可以和别的计算并发执行的计算。(3)进程是定义在一个数据结构上并能在其上进行操作的一个程序。(4)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。第2章进程管理2．进程的组成进程是在一个上下文的执行环境中运行的，这个执行环境称为进程的映像，或称进程图像，它包括处理机中各个通用寄存器的值、进程的内存映像、打开文件的状态和进程占用资源的信息等。进程映像的主要部分是存储映像。第2章进程管理进程的存储映像由以下几部分组成：进程控制块(ProcessControlBlock，即进程状态信息)、进程执行的程序、执行时所需要的数据和进程执行时使用的工作区，如图2.4所示。程序数据区工作区PCB图2.4进程的组成第2章进程管理2.2.2进程控制块进程控制块记录了进程的标识信息、状态信息和控制信息。不同的操作系统中，PCB包含的内容各不相同，大致有以下三类。(1)标识信息：惟一地标识一个进程，主要有：进程标识：为了标识系统中的各个进程，每个进程必须有一个且只有一个标识名或标识数，也就是在创建进程时系统分配的惟一的代码，它只能在操作系统内部使用，如一些数字标识符或表索引号。用户标识：指明一个进程的所有者，如登录的名称。父进程标识：是指创建该进程的进程标识。第2章进程管理(2)现场信息：记录进程使用处理器时的各种现场信息，主要有CPU通用寄存器的内容，CPU状态寄存器的内容以及栈指针等。(3)控制信息：操作系统对进程进行调度管理时用到的信息，主要有：进程状态：标识进程当前处于运行、就绪或阻塞三种状态中的哪一种，是进程调度的主要依据。调度信息：标识进程的优先级，进程正在等待的事件等。数据结构信息：标识进程间的联系，如指向该进程的父进程控制块的指针，指向该进程的子进程列表的指针等。第2章进程管理队列指针：在该单元存放下一个进程的PCB的块首址，将处于同一状态的进程链接成一个队列，便于对进程实施管理。位置信息：记录进程在内存中的位置和大小信息，如程序段指针，数据段指针。通信信息：指进程相互通信时所需的信息，如消息队列(记录可消费资源的列表)指针，进程间的互斥和同步机制。特权信息：记录进程访问内存的权限。存储信息：记录进程在辅存中的位置及大小。资源占有使用信息：标识进程的可重用资源和可消费资源，是对进程占有和使用CPU及I/O设备的情况记录。第2章进程管理进程的创建有以下几个基本步骤：(1)创建进程标识。即在主进程表中为新进程添加一个表项，进程就得到了一个惟一的标识符，并被分配进程控制块空间。(2)分配内存和其他资源。操作系统根据程序、数据的大小，为进程分配合理的内存空间。(3)初始化进程控制块。这一步是初始化进程的控制信息，包括与调度相关的信息，进程间通信的信息及进程的优先级信息等。(4)将创建的进程置于就绪队列。进程创建工作结束后，还要负责把进程放入就绪队列，等待系统根据一定的算法调度执行。于进程创建原语处着重讨论第2章进程管理2.2.3进程的基本状态及其转换1．进程的基本状态进程因创建而存在，因撤消而消亡，此期间是进程的生命期。进程在它的生命期内，由于内因和外因的影响，会呈现不同的状态，每一种状态都有各自的特征。一般地，进程具有三种基本状态：运行态、就绪态和阻塞态。第2章进程管理运行态(Running)：进程已获得必要的资源，并占有处理机，处理机正在执行该进程的程序。就绪态(Ready)：进程等待系统为其分配CPU，而CPU被其他进程占用，所以暂时不能运行，但此时进程已经具备了执行的所有条件。阻塞态(Blocked)：也可称为等待态、挂起态或睡眠态等，此时进程因等待某个事件而暂时不能运行，例如等待某个I/O事件的完成，或等待使用某个资源等。运行就绪被调度时间片用完等待资源或事件资源释放或事件完成阻塞第2章进程管理2．进程状态转换原因运行—阻塞：进程出让CPU，等待系统分配资源或某些事件的发生，如暂时不能访问某一资源，操作系统尚未完成服务，系统正在初始化I/O设备，等待用户的输入信息等。运行—就绪：进程分配的时间片已用完，或者在中断机制下，有更高优先级的进程进入系统，这时进程进入就绪队列等待下一次被选中而占用CPU。当进程创建成功时处于就绪态。阻塞—就绪：处于阻塞队列中的进程，当其等待的事件已经发生或等待的资源可用时，此进程将进入就绪队列竞争CPU。就绪—运行：进程被调度程序选中占用CPU。第2章进程管理图2.6五种进程状态转换以上是进程的基本状态转换关系。实际的操作系统中进程的状态及转换要更为复杂，引入了五种状态，即运行、就绪、新建、阻塞和终止。运行选中时间片用完结束等待等待事件创建完毕结束执行终止阻塞就绪新建第2章进程管理对于有部分进程存在于外存中的情况，进程又增加了挂起就绪态(存在于外存可以执行的进程状态)和挂起阻塞态(存在于外存等待某事件的进程状态)，其状态转换图如图2.7所示。创建完毕解挂结束等待时间片用完选中结束执行结束等待等待事件新建挂起就绪挂起阻塞终止就绪运行挂起挂起阻塞挂起解挂创建完毕图2.7七种进程状态转换第2章进程管理3.进程队列在系统中存在有许多不同状态的进程，为了便于对诸多进程进行管理和调度，必须将各进程的PCB按照某种方法组织起来，队列就是其中一种比较常用的方法。系统将同种状态的PCB排成一个队列，利用指针组成单向链表或双向链表，方便查找和调度。当进程状态变化时，它就要被排到另外的队列中，引起进程的出队和入队。处理器有专门管理出队和入队工作的模块，简称队列管理。图2.8描述了队列管理的过程。第2章进程管理执行指针就绪队列指针阻塞队列指针空闲队列指针PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB918……图2.8队列管理(1)数目一个系统中，数十个、数百个甚至数千个•链接组织方式把具有同一状态的PCB链接成一个队列;就绪队列、若干个阻塞队列、空队列.第2章进程管理PCB等待队列1结束就绪队列时间片用完入队…执行完成等待PCBPCBPCB0CPUPCBPCB0…PCBPCB…等待队列n完成等待PCBPCB0…PCBPCB图2.8队列管理(2)第2章进程管理PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9……执行指针就绪队列指针阻塞队列指针数目一个系统中，数十个、数百个甚至数千个•索引组织方式建立相应的索引表就绪索引表、阻塞索引表第2章进程管理2.2.4进程控制进程控制的主要任务是创建和撤消进程以及实现进程的状态转换。为了对进程进行有效的控制，操作系统必须设置一套控制机构，它具有以下功能：创建一个新进程，撤消一个已经运行完的进程，改变进程状态，实现进程间的通信，这就是操作系统内核(kernel)的功能。原语(primitive)是指由机器指令构成的可完成特定功能的程序段。它是一个机器指令的集合，在执行时不能中断，是一个不可分割的整体。在现代操作系统中，原语的执行多采用屏蔽中断的方法。随着计算机硬件的发展，还可以将原语固