第三章进程管理(1)介绍

1操作系统原理PrinciplesofOperatingSystem第三章进程管理2第三章进程管理3.1进程的概念3.2进程的描述3.3进程状态及其转换3.4进程控制3.5进程互斥3.6进程同步3.7进程通信3.8死锁问题3.9线程的概念3.10线程分类与执行进程是OS最基本最重要的概念，进程管理是OS的重点和难点。33.1进程的概念3.1.1程序的并发执行3.1.2进程的定义43.1.1程序的并发执行1.程序(program)2.程序的顺序执行3.多道程序系统中程序执行环境的变化4.程序的并发(concurrent)执行51.程序(program)程序完成独立的功能，是在时间上按严格次序前后相继的操作序列的集合，是一个静态的概念。程序的执行分：顺序执行并发执行62.程序的顺序执行程序的顺序执行：一个具有独立功能的程序独占处理机直至最终结束的过程称为程序的顺序执行。顺序执行是单道批处理系统的执行方式，也用于简单的单片机系统。72.程序的顺序执行程序的顺序执行C1P1I1I2C2P2I为输入操作；C为计算操作；P为打印操作。程序1程序2一个程序由若干程序段组成，这些程序段的执行必须是顺序的；同时程序与程序之间也必须顺序执行。82.程序的顺序执行计算机CPU是通过时序脉冲来控制顺序执行指令的。其执行过程可以描述为：RepeatIR←M［pc］pc←pc+1〈Execute(instructioninIR)〉UntilCPUhalt程序的顺序性和计算机硬件的顺序性一致92.程序的顺序执行程序顺序执行的特点：(1)顺序性：处理机的操作严格按照程序规定的顺序（可能有分支或循环）执行，即只有前一操作结束后，才能启动后一操作的执行；程序和机器执行程序的活动严格一一对应，即程序的顺序性和计算机硬件的顺序性一致。(2)封闭性：执行的最终结果不受外界因素的影响。一个程序在机器中执行时，它独占全机资源，除了初始状态外，只有程序本身规定的动作才能改变这些资源的状态。(3)可再现性：初始条件相同则结果相同，结果不受执行速度的影响。103.多道程序系统中程序执行环境的变化多道程序系统中，计算机能够同时处理多个具有独立功能的程序。多道程序系统的执行环境的特点：(1)独立性：每道程序都是逻辑上独立的，它们之间不存在逻辑上的制约关系。(2)随机性：多用户随机使用系统，程序、数据的输入随机，执行开始时间随机，客观上要求操作系统能同时处理多道程序。(3)资源共享：系统中的软硬件资源不再为单个用户程序所独占，而由几道用户程序共同使用。于是，这些资源的状态不再取决于一道程序，而是由多道程序的活动所决定。从根本上打破了一道程序封闭于一个系统中执行的局面。114.程序的并发执行(1)程序的并发执行并发执行的目的：为了增强计算机系统的处理能力和提高资源利用率。124.程序的并发执行程序的并发执行分为两种：a)多道程序系统的程序执行环境变化所引起的多道程序的并发执行；b)在某道程序的几个程序段中，包含着一部分可以同时执行或顺序颠倒执行的代码。例：read(a)；read(b)；既可以同时执行，也可颠倒次序执行。134.程序的并发执行程序的并发执行可总结为：一组在逻辑上互相独立的程序段在执行过程中，其执行时间在客观上互相重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始的这种执行方式。程序的并行执行是指一组程序按独立的、异步的速度执行。并行执行不等于时间上的重叠。14程序段并发执行的有向图I1I2I3I4C1C2C3C4P1P2P3P4例中：I1先于C1和I2;C1先于P1和C2;P1先于P2;I2先于C2和I3，说明了某些程序段必须在其它程序段之前完成，此外从图中可以看出：I2和C1;I3和C2和P1;I4和C3和P2是重叠的。154.程序的并发执行程序的并发执行过程可描述为：S0CobeginP1；P2；...PnCoendSnS0，Sn分别表示并发程序段P1，P2，…，Pn开始执行前和并发执行结束后的语句。P1，P2，…，Pn也可以由同一程序段中的不同语句组成。16相邻语句可以并发执行的条件（1）Bernstein条件：将程序中任一语句Si划分为两个变量的集合:R(Si))={a1,a2,…,an}，aj(j=1，…，m)是语句Si在执行期间必须对其进行读的变量；W(Si))={b1,b2,…,bn}，bj(j=1，…，n)是语句Si在执行期间必须对其进行修改的变量。17相邻语句可以并发执行的条件（2）对于语句S1和S2，如果有1）R(S1)∩W(S2)={∮}2)W(S1)∩R(S2)={∮}3)W(S1)∩W(S2)={∮}同时成立，则语句S1和S2可以并发执行在两个语句中不能对同一个变量进行读、写操作在两个语句中不能对同一个变量进行写操作18例子在一个程序中语句S1要对变量m、n在执行期间进行读操作，对变量a、b在执行期间进行修改操作；语句S2要对变量x、y在执行期间进行读操作，对变量i、j在执行期间进行修改操作。判断语句S1和S2是否能并发执行？19例子解：R(S1)={m、n}W(S1)={a、b}R(S2)={x、y}W(S2)={i、j}利用Bernstein条件可得1)R(S1)∩W(S2)={m、n}∩{i、j}={∮}2)W(S1)∩R(S2)={a、b}∩{x、y}={∮}3)W(S1)∩W(S2)={a、b}∩{i、j}={∮}所以语句S1和S2可以并发执行。20例：S1:C=X+Y+ZS2:D=C+XR(S1)={X,Y,Z}R(S2)={C,X}W(S1)={C}W(S2)={D}S1：x=x1+x2S2：y=x1*x2S3：z=(x+y)/2S4：w=z+5S5：m=w+1S6：m=m+1不能并发！！！214.程序的并发执行(2)程序的并发执行所带来的影响程序的并发执行充分地利用了系统资源，从而提高了系统的处理能力；程序的并发执行必然导致了资源共享和资源竞争，“走走停停”，一个程序可能走到中途停下来，失去原有的时序关系；从而改变程序的执行速度；224.程序的并发执行(2)程序的并发执行所带来的影响如果并发执行的各程序段中语句或指令满足Bernstein的三个条件，则认为并发执行不会对执行结果的封闭性和可再现性产生影响。如果并发执行的程序段不按照特定的规则和方法进行资源共享和竞争，则其执行结果将不可避免地失去封闭性和可再现性。23例子设有堆栈S，栈指针top，栈中存放内存中相应数据块地址，设有两个程序段getaddr(top)和reladdr(blk)，其中getaddr(top)从给定的top所指栈中取出相应的内存数据块地址，而reladdr(blk)则将内存数据块地址blk放入堆栈S中。24例子出栈：proceduregetaddr(top)beginlocalrr←(top)top←top-1return(r)endratoptop-1toptop25例子进栈：procedurereladdr(blk)begintop←top+1(top)←blkendcC=blk26图3.1堆栈的取数和存数过程274.程序的并发执行程序的并发执行，由于资源的共享和竞争使得：使得其执行结果不再具有封闭性和可再现性，且可能造成程序出现错误。为了控制和协调各程序段执行过程中的软、硬件资源的共享和竞争，必须有一个描述各程序段执行过程和共享资源的基本单位，这个基本单位被称为进程（或任务）。283.1.2进程的定义进程的概念是60年代初期，首先在MIT的Multics系统和IBM的TSS/360系统中引用的。(1)进程是可以并行执行的计算部分（S.E.Madnick，J.T.Donovan）；(2)进程是一个独立的可以调度的活动（E.Cohen，D.Jofferson）；(3)进程是一抽象实体，当它执行某个任务时，将要分配和释放各种资源（P.Denning）；293.1.2进程的定义(4)行为的规则叫程序，程序在处理机上执行时的活动称为进程（E.W.Dijkstra）；(5)一个进程是一系列逐一执行的操作。进程是一个动态的执行过程进程的定义：并发执行的程序在执行过程中分配和管理资源的基本单位。30进程和程序的区别和关系程序是构成进程的组成部分之一，一个进程的运行目标是执行它所对应的程序，如果没有程序，进程就失去了其实际存在的意义。从静态的角度看，进程是由程序、数据结构集和进程控制块三部分组成的。31进程和程序的区别和关系(1)进程是一个动态概念，而程序则是一个静态概念。程序是指令的有序集合，没有任何执行的含义。而进程则强调执行过程。(2)进程具有并发特征，而程序没有。独立性：指进程是一个能独立运行、独立分配资源和独立调度的基本单位。只有进程有资格向系统提出申请资源并获得系统提供的服务。异步性：进程按各自独立的、不可预知的速度向前推进，或说进程按异步方式运行。32进程和程序的区别和关系(3)进程是竞争计算机系统资源的基本单位，从而其并发性（独立性、异步性）受到系统自己的制约。(4)不同的进程可以包含同一程序，只要该程序所对应的数据集不同，即同一程序在执行中可以产生多个进程。通过调用，同一进程可包含多个程序。33作业和进程的区别一个进程是一个程序对某个数据集的执行过程，是分配资源的基本单位。作业是用户需要计算机完成某项任务时要求计算机所作工作的集合。一个作业的完成要经过作业提交、作业收容、作业执行和作业完成4个阶段。而进程是已提交完毕的程序所执行过程的描述。其主要区别如下：34进程与作业的区别作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业之后，系统将它放入外存中的作业等待队列中等待执行。进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在于内存中。一个作业可由多个进程组成。且必须至少由一个进程组成，但反过来不成立。作业的概念主要用在批处理系统中。而进程的概念则用在几乎所有的多道系统中。353.2进程的描述系统中描述进程存在和能够反映其变化的物理实体，称为进程的静态描述。进程的静态描述由三部分组成：程序：描述了进程所要完成的功能，是进程执行时不可修改的部分。数据结构集合：程序执行时所需要的数据和工作区，为一个进程专用，可修改。进程控制块PCB(ProcessControlBlock)：包含进程的描述信息、控制信息、资源信息，是进程动态特征的集中反映。一个进程的PCB结构都是全部或部分常驻内存的。363.2.1进程控制块进程控制块PCB(ProcessControlBlock)：为了对进程进行有效的控制和管理，系统为每一进程设置一个进程控制块，PCB其是进程存在的唯一标志，PCB纪录了进程的有关信息。通常PCB包含以下几类信息：1.进程描述信息：2.进程控制信息：3.资源管理信息：4.CPU现场保护结构：373.2.1进程控制块1.描述信息进程名或进程标识号：用来唯一标识一个进程，进程标识号通常是一个整数。用户名或用户标识号：利于资源共享与保护。家族关系：383.2.1进程控制块2.控制信息进程当前状态：进程在活动期间可分为初始态、就绪态、执行态、等待状态和终止状态。进程优先级：进程需要处理的缓急程度标识，是选取进程占有处理机的重要依据。程序、数据开始地址：程序、数据所在的内存或外存地址。各种计时信息：给出进程占有和利用资源的有关情况。通信信息：用来说明该进程在执行过程中与别的进程所发生的信息交换情况。393.2.1进程控制块3.资源管理信息：包括有关存储器的信息、使用输入输出设备的信息、有关文件系统的信息等。这些信息有：①占用内存大小及其管理用数据结构指针，如内存管理中所用到的进程页表指针等。②在某些复杂系统中，还有对换或覆盖用的有关信息，如对换程序段长度，对换外存地址等。在进程申请、释放内存中使用。403.2.1进