计算机操作系统――进程管理

第二章进程管理第二章进程管理本章内容2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5进程通信2.6线程第二章进程管理目的及要求领会程序顺序执行和并发执行的特征；掌握进程的概念和特征、进程的基本状态及转换理解进程控制块PCB的作用、包含信息和组织方式；2.1进程的基本概念2.1.1程序的顺序执行及其特征1.程序的顺序执行一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式就称为程序的顺序执行。2.1进程的基本概念例：讨论单道系统的工作情况对用户作业的处理——首先输入用户的程序和数据Input然后进行计算Caculate最后打印计算结果Print即有三个顺序执行的操作——I：输入操作C：计算操作P：输出操作P2C2I2P1C1I12.1进程的基本概念2.程序顺序执行时的特征(1)顺序性处理机的操作严格按照程序所规定的顺序执行。(2)封闭性程序一旦开始执行，其计算结果不受外界因素的影响。(3)可再现性程序执行的结果与它的执行速度无关(即与时间无关)，而只与初始条件有关。2.1进程的基本概念2.1.2前趋图前趋图是一个有向无循环图(DAG)，用于描述进程之间执行的前后关系结点：描述一个程序段或进程，或一条语句有向边：结点之间的偏序或前序关系“”={(Pi,Pj)PimustcompletebeforePjmaystart}若(Pi,Pj),记为PiPj，则Pi是Pj的直接前趋，Pj是Pi的直接后继2.1进程的基本概念P2P6P5P1P4P3P7P8P9前趋关系：P1P2，P1P3，P1P4，P2P5，P3P5，P4P6，P4P7，P5P8，P6P8，P7P9，P8P9或P={P1，P2，P3，P4，P5，P6，P7，P8，P9}={(P1,P2)，(P1,P3)，(P1,P4)，(P2,P5)，(P3,P5)，(P4,P6)，(P4,P7)，(P5,P8)，(P6,P8)，(P7,P9)，(P8,P9)}名词：初始结点；终止结点；重量2.1进程的基本概念注意：前趋图中禁止存在循环前趋关系：S2S3，S3S2，不可能满足S3S2S12.1进程的基本概念2.1.3程序的并发执行及其特征1.程序的并发执行例：在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即Ii,Ci,Pi(i=1,2,3,...,n)。2.1.3程序的并发执行及其特征......Tt1t2t3t4t5t6例如:I1、C1、P1的执行必须严格按照I1，C1，P1的顺序；而C1与I2，P1与C2、I3是可以同时执行的。S3S2S1S4又如：四个程序段S1：a:=x+2S2：b:=y+4S3：c:=a+bS4：d:=c+b2.程序并发执行时的特征(1)间断性在多道程序设计的环境下，程序的并发执行，以及为完成一项任务而相互合作，这些程序之间要共享系统的资源，形成了相互制约的关系。相互制约导致并发程序具有“执行—暂停—执行”这种间断性的活动规律。2.1.2程序的并发执行及其特征(1)间断性(2)失去封闭性程序在并发执行时，系统的资源状态由多道程序来改变，程序运行失去封闭性。一程序的运行受到其他程序的影响。(3)不可再现性程序在并发执行时，多次运行初始条件相同的同一程序会得出不同的运行结果。例：共享公共变量的两个程序，它们执行时可能产生不同结果。程序顺序执行时的特征(1)顺序性(2)封闭性(3)可再现性2.1.3程序的并发执行及其特征并发程序失去可再现性的例子n:=0例：讨论共享公共变量的两个程序，它们执行时可能产生的不同结果。程序A…n:=n+1;…程序B…print(n);n:=0;…2.1进程的基本概念2.1.4进程的特征与状态1.进程的特征和定义在多道程序设计的环境下，为了描述程序在计算机系统内的执行情况，必须引入新的概念--进程。1）进程的定义进程：程序关于某个数据集合的一次执行过程。2.1进程的基本概念行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan)进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C.Shaw)进程是执行中的程序。（KenThompsonandDennisRitchie)进程的其它定义2）进程的特征（与程序比较）(1)结构特征进程控制块(PCB)+程序+数据=进程实体(2)动态性--最基本特征进程：进程实体的一次执行过程，有生命周期程序：程序是一组有序指令的集合，是静态的概念。(3)并发性(4)独立性(5)异步性进程按各自独立的、不可预知的速度向前推进1.进程的特征和定义2.进程的三种基本状态(1)就绪状态(Ready)进程已获得除CPU之外的所有必需的资源，一旦得到CPU控制权，立即可以运行。(2)运行状态(Running)进程已获得运行所必需的资源，它的程序正在处理机上执行。(3)阻塞状态(Blocked)正在执行的进程由于发生某事件而暂时无法执行时，便放弃处理机而处于暂停状态，称该进程处于阻塞状态或等待状态。就绪队列与阻塞队列2.1.4进程的特征与状态执行阻塞就绪时间片完I/O请求进程调度I/O完成进程的三种基本状态以及各状态之间的转换2.1.4进程的特征与状态3.挂起状态1)引起挂起状态的原因：终端用户的请求父进程请求负荷调节的需要操作系统的需要2)进程状态的转换引入挂起状态后，增加了挂起状态(静止状态)到非挂起状态(活动状态)的转换，或者相反。2.1.4进程的特征与状态请求I/O静止阻塞活动阻塞静止就绪活动就绪执行挂起挂起挂起激活激活释放释放1.活动就绪静止就绪2.活动阻塞静止阻塞3.静止就绪活动就绪4.静止阻塞活动阻塞2.1.4进程的特征与状态readyareadysblockedablockeds2.1进程的基本概念2.1.5进程控制块（PCB）1.进程控制块的作用2.进程控制块中的信息3.进程控制块的组织方式2.1进程的基本概念2.1.5进程控制块（PCB）1.进程控制块的作用存放进程管理和控制信息的数据结构称为进程控制块。它是进程管理和控制的最重要的数据结构，在创建时，建立PCB，并伴随进程运行的全过程，直到进程撤消而撤消。PCB就象我们的户口。PCB是进程存在的唯一标志。系统的所有PCB组织成链表或队列，常驻内存的PCB区。2.1.5进程控制块（PCB）2.进程控制块中的信息1)进程标示符每个进程都必须有一个唯一的标识符内部标示符外部标示符2)处理机状态处理机状态信息主要由处理机的各种寄存器中的内容组成。处理机运行时的信息存放在寄存器中，当被中断时这些信息要存放在PCB中。2.1.5进程控制块（PCB）3)进程调度信息进程状态进程优先级进程调度所需的其他信息事件4)进程控制信息程序和数据的地址进程通信和同步机制资源清单链接指针2.1.5进程控制块（PCB）3.进程控制块的组织方式1)链接方式把具有同一状态的PCB用其中的链接字链接成一个队列。就绪队列；若干个阻塞队列；…1PCB90PCB89PCB77PCB6PCB58PCB40PCB33PCB24PCB1就绪队列指针阻塞队列指针空闲队列指针执行指针PCB的链接组织方式：2.1.5进程控制块（PCB）3.进程控制块的组织方式2)索引方式系统根据所有进程的状态建立几张索引表，把各表的内存首地址记录在内存的专用单元中。索引表的表目中记录了相应状态的某个PCB在PCB表中的地址。PCB7PCB6PCB5PCB4PCB3PCB2PCB1执行指针就绪表指针阻塞表指针就绪索引表阻塞索引表PCB的索引组织方式：第二章进程管理本章内容2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5管程机制2.6进程通信2.7线程2.2进程控制对系统中的全部进程实施有效的管理，包括进程创建、终止、进程阻塞和唤醒。2.2.1进程的创建1.进程图描述进程的家族关系的有向树ABDKEFLMJIHGC进程的创建过程：申请空白PCB为新进程分配资源初始化进程控制块将新进程插入就绪队列2.进程的创建操作系统发现要求创建新进程的事件后，调用进程创建原语Creat()创建新进程。1.引起进程终止的事件1)正常结束2)异常结束越界错误、非法指令等3)外界干预操作员或操作系统干预；父进程请求；父进程终止2.2.2进程的终止2.进程的终止过程2.2.2进程的终止找出被终止进程的PCB若进程状态为运行态，置CPU调度标志为真若其有子孙进程，终止其子孙进程并回收其资源回收终止进程的资源回收终止进程的PCB1.引起进程阻塞和唤醒的事件1)请求系统服务2)启动某种操作3)新数据尚未到达4)无新工作可做2.进程阻塞过程2.2.3进程的阻塞与唤醒调用阻塞原语阻塞自己；将PCB中的状态改为阻塞，并加入阻塞队列；转进程调度。3.进程唤醒过程把阻塞进程从等待该事件的阻塞队列中移出；置进程状态为就绪态，将PCB插入到就绪队列中。阻塞原语与唤醒原语作用相反，成对使用阻塞进程等待的事件发生，有关进程调用唤醒原语wakeup()唤醒等待该事件的进程2.2.4进程的挂起与激活1.进程的挂起过程检查被挂起进程的状态：若处于活动就绪，则改为静止就绪；若处于活动阻塞，则改为静止阻塞；若挂起的进程正在执行，则重新进行进程调度。当出现引起进程挂起的事件时，系统利用挂起原语suspend()将指定进程或处于阻塞的进程挂起。2.2.4进程的挂起与激活2.进程的激活过程1)激活原语先将进程从外存调入内存；2)检查该进程的状态：若为静止就绪，则改为活动就绪；若为静止阻塞，则改为活动阻塞。当发生激活进程的事件时，系统利用激活原语active()将指定进程激活。作业课本P.812、3、5、6第二章进程管理本章内容2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5进程通信2.6线程第二章进程管理目的及要求理解临界资源和临界区的概念；熟练掌握利用信号量机制解决进程同步问题；2.3进程同步2.3.1进程的同步基本概念2.3.2信号量机制2.3.3信号量的应用对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。进程同步的主要任务：2.3.1进程同步的基本概念1.进程间两种形式的制约关系(1)间接相互制约关系---源于资源共享(2)直接相互制约关系---源于进程合作临界资源（CriticalResource）:把一段时间内只允许一个进程访问的资源称为临界资源或独占资源临界区（CriticalSection）:每个进程中访问临界资源的那段代码称为临界区2.临界资源2.临界资源生产者—消费者问题：2.3.1进程同步的基本概念…能存n个数据的BufferP1P2Pl……C1C2Cm生产者进程消费者进程生产者进程和消费者进程都以异步方式运行，但它们之间必须保持同步。2.3进程同步生产者进程和消费者进程共享的变量：Varn,integer;typeitem=……;varbuffer:array[0,1,…,n-1]ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;用数组表示具有n个缓冲区的缓冲池注意：缓冲池组织为循环缓冲，输入指针加1表示为in:=(in+1)modn，输出指针加1表示为out:=(out+1)modn，当(in+1)modn=out时表示缓冲池满，in=out表示缓冲池空。初始值为0，放入产品使其加1，取出产品使其减1输入指针in指示下一个可投放产品的缓冲区，输出指针out指示下一个可从中获取产品的缓冲区，初值均为1。Producer:repeat…produceaniteminnextp;…whilecounter=ndono-op;buffer[in]:=nextp;in:=in+1modn;co