第2章 进程管理(part1)

第二章进程管理HebNomalUniversityDepartmentofComputerScience1第二章进程管理2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5管程机制2.6进程通信2.7线程第二章进程管理HebNomalUniversityDepartmentofComputerScience22.1进程的基本概念2.1.1程序的顺序执行及其特征1.程序的顺序执行仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。S1:a∶=x+y;S2:b∶=a-5;S3:c∶=b+1;第二章进程管理HebNomalUniversityDepartmentofComputerScience3图2-1程序的顺序执行(a)程序的顺序执行(b)三条语句的顺序执行I1C1P1I2C2P2S1S2S3第二章进程管理HebNomalUniversityDepartmentofComputerScience42.程序顺序执行时的特征(1)顺序性：(2)封闭性：(3)可再现性：第二章进程管理HebNomalUniversityDepartmentofComputerScience52.1.2前趋图前趋图(PrecedenceGraph)是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(PartialOrder)或前趋关系(PrecedenceRelation)“→”。→={(Pi,Pj)|PimustcompletebeforePjmaystart},如果(Pi,Pj)∈→,可写成Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(InitialNode)，把没有后继的结点称为终止结点(FinalNode)。第二章进程管理HebNomalUniversityDepartmentofComputerScience6每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。Ii→Ci→Pi和S1→S2→S3前面的图2-1中，存在着前驱关系：(a)程序的顺序执行(b)三条语句的顺序执行I1C1P1I2C2P2S1S2S3第二章进程管理HebNomalUniversityDepartmentofComputerScience7图2-2对于图2-2所示的图，试判断是否前趋图：P1P3P8P9P4P2P5P6P7S1S2S3(a)具有九个结点的前趋图(b)具有循环的前趋图图第二章进程管理HebNomalUniversityDepartmentofComputerScience8对于图2-2(a)所示的前趋图，存在下述前趋关系：P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P4→P7,P5→P8,P6→P8,P7→P9,P8→P9P={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-2(b)中却有着下述的前趋关系：S2→S3,S3→S2P1P3P8P9P4P2P5P6P7S1S2S3(a)具有九个结点的前趋图(b)具有循环的前趋图图第二章进程管理HebNomalUniversityDepartmentofComputerScience92.1.3程序的并发执行及其特征1.程序的并发执行图2-3并发执行时的前趋图P1P2P3P4I1I2I3I4C1C2C3C4第二章进程管理HebNomalUniversityDepartmentofComputerScience10Ii→Ci，Ii→Ii+1,Ci→Pi,Ci→Ci+1，Pi→Pi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。P1P2P3P4I1I2I3I4C1C2C3C4S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+bS1S2S3S4图2-4四条语句的前趋关系第二章进程管理HebNomalUniversityDepartmentofComputerScience112.程序并发执行时的特征1)间断性2)失去封闭性3)不可再现性例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N∶=N+1操作；程序B每执行一次时，都要执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。(1)N∶=N+1在Print(N)和N∶=0之前，此时得到的N值分别为n+1,n+1,0。(2)N∶=N+1在Print(N)和N∶=0之后，此时得到的N值分别为n,0,1。(3)N∶=N+1在Print(N)和N∶=0之间，此时得到的N值分别为n,n+1,0。第二章进程管理HebNomalUniversityDepartmentofComputerScience122.1.4进程的特征与状态1.进程的特征和定义1)结构特征2)动态性3)并发性4)5)异步性第二章进程管理HebNomalUniversityDepartmentofComputerScience13程序与进程之间的区别•进程更能真实地描述并发，而程序不能•进程是由程序，数据和控制块三部分组成的•程序是静态的，进程是动态的•进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的•一个程序可对应多个进程，反之亦然•进程具有创建其他进程的功能，而程序没有第二章进程管理HebNomalUniversityDepartmentofComputerScience14(1)进程是程序的一次执行。(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。在引入了进程实体的概念后，我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。第二章进程管理HebNomalUniversityDepartmentofComputerScience152.进程的三种基本状态1)就绪(Ready)状态一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行）2)进程占有CPU，并在CPU上运行3)阻塞状态又叫等待态、封锁态、睡眠态指进程因等待某种事件的发生而暂时不能运行的状态（即使CPU空闲，该进程也不可运行）图2-5进程的三种基本状态及其转换就绪阻塞执行时间片完进程调度I/O完成I/O请求第二章进程管理HebNomalUniversityDepartmentofComputerScience16进程的状态及其转换运行就绪等待在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换•就绪--运行–调度程序选择一个新的进程运行•运行--就绪–运行进程用完了时间片–运行进程被中断，因为一高优先级进程处于就绪状态•运行--等待–当一进程必须等待时–OS尚未完成服务–对一资源的访问尚不能进行–初始化I/O且必须等待结果–等待某一进程提供输入(IPC)•等待--就绪–当所等待的事件发生时就绪阻塞执行时间片完进程调度I/O完成I/O请求第二章进程管理HebNomalUniversityDepartmentofComputerScience17增加:创建状态，终止状态三种进程状态-五状态进程模型创建(新new)状态–OS已完成为创建一进程所必要的工作•已构造了进程标识符•已创建了管理进程所需的表格–但还没有允许执行该进程(尚未同意)•因为资源有限•终止（退出exit)状态–中止后进程移入该状态–它不再有执行资格–表格和其它信息暂时由辅助程序保留–一旦其他进程完成了对终止态进程的信息抽取之后，系统将删除该进程。第二章进程管理HebNomalUniversityDepartmentofComputerScience18五状态进程模型•NULL→新建态：创建一个子进程。•新建态→就绪态：系统完成了进程创建操作，且当前系统的性能和内存的容量均允许。•运行态→终止态：一个进程到达自然结束点，或出现了无法克服的错误，或被操作系统所终结，或被其他有终止权的进程所终结。•终止态→NULL：完成善后操作。•就绪态→终止态：某些操作系统允许父进程终结子进程。•等待态→终止态：某些操作系统允许父进程终结子进程。第二章进程管理HebNomalUniversityDepartmentofComputerScience193.1)引入挂起状态的原因由于进程的不断创建，系统资源已不能满足进程运行的要求，就必须把某些进程挂起（suspend），对换到磁盘镜像区中，暂时不参与进程调度，起到平滑系统操作负荷的目的。(1)终端用户的请求。(2)父进程请求。(3)负荷调节的需要。(4)操作系统的需要。第二章进程管理HebNomalUniversityDepartmentofComputerScience202)进程状态的转换(1)活动就绪→静止就绪。(2)活动阻塞→静止阻塞。(3)静止就绪→活动就绪。(4)静止阻塞→活动阻塞。图2-6具有挂起状态的进程状态图执行→静止就绪。挂起激活•就绪状态(Ready)：进程在内存且可立即进入运行状态•阻塞状态(Blocked)：进程在内存并等待某事件的出现•静止阻塞/阻塞挂起状态（Blocked,suspend）：进程在外存并等待某事件的出现•静止就绪/就绪挂起状态（Ready,suspend）：进程在外存，但只要进入内存，即可运行第二章进程管理HebNomalUniversityDepartmentofComputerScience21七状态进程模型活动挂起事件发生事件发生等待事件挂起调度超时释放活动挂起•挂起（Suspend）：把一个进程从内存转到外存可能有以下几种情况–活动阻塞→静止阻塞：没有进程处于就绪状态或就绪进程要求更多内存资源时，发生这种转换，以提交新进程或运行就绪进程–活动就绪→静止就绪：当有高优先级阻塞（系统认为会很快就绪的）进程和低优先级就绪进程时，系统会选择挂起低优先级就绪进程–运行→静止就绪：对抢占式系统，当有高优先级静止阻塞进程因事件出现而进入静止就绪时，系统可能会把运行进程转到静止就绪状态第二章进程管理HebNomalUniversityDepartmentofComputerScience22七状态进程模型活动挂起事件发生事件发生等待事件挂起调度超时释放活动挂起•激活（Activate）：把一个进程从外存转到内存；可能有以下几种情况：–静止就绪→活动就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程时，发生转换–静止阻塞→活动阻塞：当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起（系统认为会很快出现所等待的事件）进程转换为阻塞状态。第二章进程管理HebNomalUniversityDepartmentofComputerScience23•进程程序•进程数据•栈–用于过程调用和参数传递•进程控制块PCB(进程属性)–处于核心段–用户进程不能直接访问、修改自己的PCB*进程要素第二章进程管理HebNomalUniversityDepartmentofComputerScience242.1.5进程控制块1.进程控制块的作用进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。系统为了管理进程设