第3章进程管理-计算机操作系统

1/212第3章进程管理3.1进程的概念3.2进程的描述3.3进程状态及其转换3.4进程控制3.5进程互斥3.6进程同步3.7进程通信3.8死锁问题3.9线程2/2123.1进程的概念现代操作系统的中：程序的并发执行;资源被共享;用户随机地使用计算机。它们是互相联系和依赖的，反映独立的用户如何使用有限的计算机系统资源的反映。为了使用户充分、有效地利用系统资源。采用一个什么样的概念，来描述程序的执行过程和作为资源分配的基本单位才能充分反映操作系统的并发执行、资源共享及用户随机的特点呢？这个概念就是进程。3/2123.1.1程序的并发执行1.程序的顺序执行程序是一个静态的概念，是指令的集合。是一个操作的序列。程序只有经过执行才能得到最终结果。而且一般用户在编写程序时不考虑在自己的程序执行过程中和其他用户程序竞争资源这一事实。另外，计算机CPU是通过时序脉冲来控制顺序执行指令的。其执行过程可以描述为：IR指令寄存器RepeatIR←M[pc]M：内存，PC：程序计数器pc←pc+1〈Execute(instructioninIR)〉UntilCPUhalt4/212程序的顺序执行的有向图（前驱，后继）t输入：计算：输出：I1C1P1I2C2P2I3C3P3t0t1t2t3t4t5t6t7t8t9t10Δt程序1：I1C1P1程序2：程序3：I2C2P2I3C3P39个Δt结束5/212我们把程序独占处理机执行，直至最终结束的过程称为程序的顺序执行。程序的顺序执行具有如下特点：(1)顺序性：上一条指令执行的结果是下一条指令开始执行的充分必要条件。(2)封闭性：执行得到的最终结果由给定的初始条件决定，不受外界因素的影响。(3)可再现性:只要输入的初始条件相同，则重复执行该程序都会得到相同的结果。与执行速度无关。问题：执行过程能否再现？6/2122.多道程序系统中程序执行环境的变化该环境，能够同时处理多个具有独立功能的程序。批处理系统、分时系统、实时系统以及网络与分布式系统等都是这样的系统。这样的执行环境具有下述三个特点：(1)程序的并发执行：多个作业或进程的执行在时间上是重叠的。见下图：7/212输入：计算：输出：t0t1t2t3t4t5t6ΔttI1三个程序并发执行的前驱图I2I3C1C2C3P1P2P3时间:5个Δt并行并行并行结束下一步下一步下一步前驱关系执行顺序没有前驱关系的过程可以并发执行(I3，C2，P1)，这是系统的并发性，提高(9-5)/9*100%=44%。8/212(2)随机性在多道程序环境下，特别是在多用户环境下，程序和数据的输入与执行开始时间都是随机的。(3)资源共享资源共享将导致对进程执行速度的制约。有两种方式：A：由系统统一分配。先向系统提出申请，然后按一定的策略统一分配。如硬资源。B：由程序自行分配。如数据表，变量等软资源。但系统应提供协调机构，避免因竞争资源而发生混乱。9/212多道程序的执行tAAΔt等待I/O的时间（6个Δt）（a）单道情况11078BBtAAΔt（b）两道情况1107189tΔt（c）四道情况1107189BBAACDCD2310图3.1单道、两道和四道情况142吞吐率：1/8Δt=0.125道程序/Δt吞吐率：2/9Δt=0.222道程序/ΔtAI/OAI/OBI/O吞吐率：4/11Δt=0.363道程序/Δt下一步A,B,C,D为程序，忽略外设；假定4个程序都需运行2个Δt时间，在期间有6个Δt时间的I/O操作；吞吐率分别为：1/8=0.1252/9=0.2224/11=0.3634道程序情况比单道提高了近3倍。显然不仅使内存充分利用，还带来处理机利用率的提高，使整个系统效率得以提高。下一步结束下一步10/212多道程序环境的特点：（1）独立性：每道程序逻辑上是独立的，执行速度（占用CPU的时间）与其它程序无关，但程序的周转时间延长了。（2）随机性：多个用户的程序和数据的输入，执行的时间都是随机的。（3）资源共享：程序的道数CPU和外设的个数，导致了资源必须共享。11/2123.程序的并发执行(1)什么是程序的并发执行是为了增强计算机系统的处理能力和提高资源利用率所采取的一种同时操作技术（在一段时间内）。或一组在逻辑上独立的程序，在执行的过程中在时间上是重叠的。即一个程序的执行尚未结束，而另一个程序的执行已经开始。可分为两种：第一种:是多道程序系统引起的并发执行（无关程序）。由于资源的有限性，产生资源的共享与竞争。从而制约各道程序的执行速度。因此，尽管多道程序的并发执行在宏观上是同时进行的，但在微观上仍是顺序执行的。12/212第二种：在某道程序内部包含着若干可以同时执行或顺序颠倒执行的代码（相关程序）。例如语句：read(a)；read(b)；它们既可以同时执行，也可颠倒次序执行。对于这样的语句，同时执行不会改变顺序程序所具有的逻辑性质。因此，可以采用并发执行来充分利用系统资源以提高计算机的处理能力。程序的并发执行不同于程序的并行执行。程序的并行执行是指一组程序在一个时间的瞬间同时执行。在时间上不重叠。*只有一个资源的情况。*不同类型资源的情况。*同类型有多个资源的情况。只能并发执行可并行执行可并行执行13/212可以将并发执行过程描述为：S0CobeginP1；P2；...PnCoendSn在S0，Cobegin和Coend，Sn中包含P1；P2；...Pn其中P1，P2，…，Pn是可以并发执行的语句。问题：P1….Pn,哪一个程序先执行？14/212两相邻语句S1，S2可以并发执行的条件：将程序中任一语句Si划分为两个变量的集合R(Si)和W(Si)其中：R(Si)={a1,a2,…am}，aj(j=1，…，m)是语句Si在执行期间必须对其读的变量集合；W(Si)={b1,b2,…bn}，bj(j=1，…，n)是语句Si在执行期间必须对其进行修改变量集合；如果对于语句S1和S2，有①R(S1)∩W(S2)={∮};交运算，空集。②W(S1)∩R(S2)={∮};③W(S1)∩W(S2)={∮}同时成立，则语句S1和S2是可以并发执行的。15/212如有语句c=a-b和w=c+1；能否并发执行（其“读集”和“写集”分别为）：第一条语句的读写集合R(c＝a-b)＝{a，b}；W(c＝a-b)＝{c}第二条语句的读写集合R(w＝c+1)＝{c}；W(w＝c+1)＝{w}交集运算集合R(c＝a-b)∩W(w＝c+1)＝{}R(w＝c+1)∩W(c＝a-b)＝{c}所以：两条语句不能并发执行。16/212(2)程序的并发执行所带来的影响A：充分地利用了系统资源，从而提高了系统的处理能力；B：由于系统资源有限，导致资源共享和资源竞争，作业的周转时间长了。实现并发执行的条件：A：硬件：有多道程序驻留且互不干扰的存储空间；B：软件：有能将源程序编译成并发程序的编译器。在多道环境下，如果并发执行的程序段不按照规定的方法进行资源共享和竞争，则其执行结果将失去封闭性（不受外界因素的影响）和可再现性（程序重复执行会得到相同的结果。与执行速度无关）。17/212例：设有堆栈S，栈指针top，栈中存放内存中相应数据块地址如图，设有两个程序段：getaddr(top)：从给定的top所指栈中取出相应的内存数据块地址（出栈）；reladdr(blk)：则将内存数据块地址blk放入堆栈S中（进栈）。proceduregetaddr(top)取数据（出栈）beginlocalr；定义局部变量r←(top)；取数据top←top-1；移动指针return(r)；返回值endtopabcd18/212procedurereladdr(blk)存数据（进栈）begintop←top+1；移动指针(top)←blk；存放地址end显然，如果getaddr和reladdr程序段按顺序执行，其执行结果具有封闭性和可再现性。但如果对这两个程序段采用并发执行，则在单CPU系统中，将有可能出现下述情况：19/212例子：取数据（出栈）操作先写reladdr(blk)，后读getaddr(top)图3.1堆栈的取数过程20/212这说明了在某些情况下，程序的并发执行使得其执行结果不再具有封闭性和可再现性，使程序出现错误。错误原因是由于两程序段共享资源堆栈S，从而使得执行结果受执行速度影响。为了使并发执行时不出现错误结果，必须采取某些措施来制约、控制各并发程序段的执行速度。为了控制和协调各程序段对资源的共享和竞争，必须有一个描述各程序段执行过程和共享资源的基本单位。用程序作为其执行过程以及共享资源的基本单位是不合适的。这个基本单位被称为进程（或任务）。21/2123.1.2进程的定义进程的概念是60年代初期出现的。进程的定义：(1)进程是可以并行执行的计算部分（S.E.Madnick，J.T.Donovan）；(2)进程是一个独立的可以调度的活动（E.Cohen，D.Jofferson）；(3)进程是一抽象实体，当它执行某个任务时，将要分配和释放各种资源（P.Denning）；(4)行为的规则叫程序，程序在处理机上执行时的活动称为进程（E.W.Dijkstra）；22/212(5)一个进程是一系列逐一执行的操作，而操作的确切含义则有赖于以何种详尽程度来描述进程（BrinchHansen）。(6)一个具有独立功能的程序对某个数据集在处理机上执行的过程和分配资源的基本单位。进程的本质是一个动态的执行过程这一概念。进程的特征：(1)动态性：有创建，运行，消亡的过程（生命周期）。(2)并发性：任何进程都可以同其他进程一起并发执行。23/212(3)异步性：由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进。(4)独立性：进程是一个独立的运行，分配资源，管理，调度的基本单位。(5)结构性：进程由程序、数据和进程控制块(PCB)三部分组成。进程控制块包含：一般信息，资源信息，控制信息等。进程是多道程序和分时系统的需要，也是描述程序并发执行的需要。24/212好处：提高了资源的利用率，提高了系统的吞吐量。不足：(1)空间开销：用于管理进程的数据结构PCB要占用一定的存储空间；(2)时间开销：为了不断地填写，更新系统和进程的数据结构的内容；为了进程的切换，保护现场，都需要占用CPU的时间。25/212进程管理的功能：(1)进程的控制：创建与撤销进程及多个进程状态的转换。(2)进程的协调：出现资源竞争时，如何对进程间的制约进行控制(互斥)。(3)进程的通信：对进程间的信息交换和通信进行管理(同步)。(4)进程的调度：按一定的策略将CPU分配给进程。(5)进程的安全：死锁，多个进程争夺资源陷入僵局。上述工作是由操作系统的内核完成的。26/212操作系统内核的概念：现代操作系统广泛采用了层次结构，为了减少系统本身的开销，在进行层次设计时，往往将一些与硬件紧密相关的模块，运行频率较高的模块，关键性的数据结构，公共的基本操作模块，安排在靠近硬件的层次，并使之常驻内存，以提高操作系统运行的效率。这些模块的集合---内核。内核的基本功能：(1)中断处理：系统活动的基础(系统调用，命令输入，进程调度，设备驱动，文件操作，进程并发执行)。(2)进程管理：对进程各个阶段的管理。(3)系统的基本操作：时钟I/O接口及设备，安全机制，文件系统等。27/212近年来，为了更进一步减少操作系统的运行开销，提出了“微内核”的概念。Microkernel：没有文件系统的内核。进程和程序的区别如下：(1)进程是一个动态概念：进程强调执行过程，它动态地被创建，并被调度执行后消亡。而程序则是一个静态概念。程序是指令的有序集合。(2)进程具有并行特征：表现在两个方面，即独立性和异步性。程序不反映执行过程，所以不具有并行特征。(3)进程是竞争计算机系统资源的基本单位，受到系统资源的制约。制约就是对进程独立性和异步性的限制。(4)同一程序对不同的数据集的执行可产生多个进程。多次对同一个数据集的执行？28/2123.1.3作业和进程