搜索
第二章进程管理第二章进程管理2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5进程通信2.6线程第二章进程管理*对处理机进行分配，并对其运行进行有效的控制管理。主要任务：多道程序环境下，处理机管理可归结为对进程的管理，所以，处理机管理主要研究进程的调度管理。*进程控制：主要功能：*进程同步：*进程通信：*调度：第二章进程管理第二章进程管理2.1进程的基本概念2.1.1程序的顺序执行及其特征1、程序的顺序执行仅当前一操作(程序段)执行完后，才能执行后继操作。图2-1程序的顺序执行第二章进程管理2、程序顺序执行时的特征(1)顺序性(2)封闭性(3)可再现性S1:a:=x+y;S2:b:=a-5;S3:c:=b+1;第二章进程管理2.1.2前趋图前趋图是一个有向无环图，有向边表示结点间的偏序或前趋关系。直接前趋直接后继初始结点终止结点重量或权值互不依赖的结点可并发执行第二章进程管理2.1.2前趋图Ii→Ci→PiS1→S2→S3第二章进程管理2.1.2前趋图P1P3P8P9P4P2P5P6P7(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.1.2前趋图S1S2S3(b)具有循环的非前驱图前趋图中必须不存在循环！如果系统中存在循环，则可能发生死锁。S2→S3,S3→S2第二章进程管理2.1.3程序的并发执行及其特征1、程序的并发执行图2-3并发执行时的前趋图Ii→Ci，Ii→Ii+1,Ci→Pi,Ci→Ci+1，Pi→Pi+1其中互不依赖部分可以并发执行。P1P2P3P4I1I2I3I4C1C2C3C4第二章进程管理程序段及其前驱图：S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+b图2-4四条语句的前趋关系S1S2S3S4第二章进程管理2、程序并发执行时的特征例：A、B两程序段并发执行，共享存储变量N，试分析其运行结果和特点。A：…N：=N+1…PrintN…B：…PrintN…N：=0…N的可能值：n+1、n+1、0n、n+1、0n、0、1？第二章进程管理2、程序并发执行时的特征1）间断性2）失去封闭性3）不可再现性程序顺序执行时的特征：(1)顺序性(2)封闭性(3)可再现性第二章进程管理3、程序并发执行的条件Bernstain条件：R（P1）∩W（P2）∪R（P2）∩W（P1）∪W（P1）∩W（P2）={}即：两进程P1、P2它们的读集与写集之间或写集与写集之间没有公共变元，则两进程可并发执行。第二章进程管理1、进程的定义：(1)进程是程序的一次执行。(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。2.1.4进程的特征与状态第二章进程管理2.1.4进程的特征与状态2、进程的特征和定义1）结构特征2）动态性3）并发性45）异步性*进程是可并发执行的程序在一个数据集合上的运行过程。*进程是进程实体的运行过程。*进程实体由程序段、数据段、进程控制块（PCB）构成。第二章进程管理注：进程与程序的主要区别*程序是指令的集合，本身没有任何运行的含义，是一个静态概念；而进程是程序在处理机上的一次执行过程，是一个动态概念。*程序的存在是永久的；而进程是有生命期的，它因创建而产生，因调度而执行，因缺少资源而暂停，因撤消而消亡。*程序仅是指令的有序集合；而进程则由程序段、数据段、进程控制块组成。*进程与程序之间不是一一对应的，即同一程序可同时运行于若干个不同的数据集合上，它将属于不同的进程；而一个进程也可以执行多个程序。第二章进程管理3、进程的三种基本状态图2-5进程的三种基本状态及其转换第二章进程管理进程的五种基本状态*就绪状态*执行状态*阻塞状态*新状态*终止状态新进程结束接纳完成第二章进程管理两种状态的进程模型第二章进程管理五种状态的进程模型第二章进程管理进程阻塞队列第二章进程管理进程阻塞队列第二章进程管理4、1)引入挂起状态的原因(1)终端用户的请求(2)父进程请求(3)负荷调节的需要(4)操作系统的需要(5)对换的需要2)进程状态的转换(1)活动就绪→静止就绪(2)活动阻塞→静止阻塞(3)静止就绪→活动就绪(4)静止阻塞→活动阻塞第二章进程管理图2-6具有挂起状态的进程状态图活动就绪静止就绪执行挂起激活释放挂起活动阻塞静止阻塞挂起激活释放请求I/O挂起实际上是将相应状态再降低一级2)进程状态的转换第二章进程管理进程的挂起状态第二章进程管理进程的挂起状态第二章进程管理1、PCB的作用和特点*PCB是操作系统中最重要的数据结构，是进程存在的唯一标志；*PCB的作用是使一个在多道环境下不能独立运行的程序（含数据）成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程；*PCB常驻内存，可以被操作系统中的多个模块读或修改；*PCB是进程实体的一部分，同进程一样具有一定的生命期，且与进程保持一致。2.1.5进程控制块PCB第二章进程管理2、PCB中的信息1）①②外部标识符2）①通用寄存器②指令计数器③程序状态字PSW④堆栈指针3）①进程状态②进程优先级③调度相关信息④阻塞事件4）进程控制信息①程序和数据的地址②进程同步和通信机制③资源清单④链接指针第二章进程管理2、PCB中的信息第二章进程管理3、PCB的组织方式1）链接方式图2-7PCB链接队列示意图PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901执行指针就绪队列指针阻塞队列指针空闲队列指针…第二章进程管理2）索引方式图2-8按索引方式组织PCB执行指针就绪索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就绪表指针阻塞表指针第二章进程管理2.2进程控制*为了确保系统的安全性，常将处理机的执行状态分为系统态和用户态。*进程控制由操作系统内核实现，运行于系统态。OS内核是计算机硬件的第一次扩充，由一些与硬件紧密相关的模块和运行频率较高的模块构成。内核常驻内存，受特殊保护。*原语（Primitive）是由若干条指令组成的，用于完成特定功能的一个特殊过程。它与一般过程的区别在于：它们是原子操作（ActionOperation）。第二章进程管理2.2进程控制操作系统内核的功能*支撑功能：*资源管理功能：*中断管理*时钟管理*原语操作*进程管理*存储器管理*设备管理第二章进程管理*进程图：用于描述进程家族关系的有向图；反映创建与被创建或父与子的关系。1、进程图（ProcessGraph2.2进程控制2.2.1进程的创建第二章进程管理2、引起创建进程的事件(1)用户登录(2)作业调度(3)提供服务(4)应用请求2.2进程控制2.2.1进程的创建由系统内核创建新进程由应用程序创建新进程第二章进程管理3、进程的创建（CreationofProgress）(1)申请空白PCB。(2)为新进程分配资源。(3)初始化进程控制块。(4)将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。第二章进程管理2.2.2进程的终止1、引起进程终止的事件1）3）①越界错误②保护错③非法指令④特权指令错⑤运行超时⑥等待超时⑦算术运算错⑧I/O故障。2）①操作员或系统干预②父进程请求③父进程终止第二章进程管理2、进程的终止过程(1)从PCB集合中检索出该进程的PCB，读出相应(2)终止该进程的执行，(3)(4)将其全部资源，(5)将该进程（即它的PCB）从所在队列（或链表）中移出。第二章进程管理2.2.3进程的阻塞与唤醒1、引起进程阻塞和唤醒的事件1)请求系统服务2)启动某种操作3)新数据尚未到达4)第二章进程管理2、（1）进程通过调用阻塞原语block把自己阻塞。进程的阻塞是进程自身的一种主动行为。（2）把PCB中的现行状态改为阻塞；（3）将PCB插入阻塞队列；（4）将处理机分配给另一就绪进程。第二章进程管理3、当被阻塞进程所期待的事件出现时，则由有关进程调用唤醒原语wakeup，将等待该事件的进程唤醒。唤醒原语执行的过程：（1）把该进程从阻塞队列中移出；（2）将其PCB中的现行状态改为就绪；（3）将该进程的PCB插入就绪队列。第二章进程管理2.2.4进程的挂起与激活1、当出现了引起进程挂起的事件时，系统利用挂起原语suspend将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程：活动就绪静止就绪活动阻塞静止阻塞执行状态重新调度（静止就绪）第二章进程管理2、系统将利用激活原语active将指定进程激活。激活原语先将进程从外存调入内存，检查该进程的现行状态：静止就绪活动就绪静止阻塞活动阻塞思考：阻塞队列的位置？活动就绪静止就绪执行挂起激活活动阻塞静止阻塞挂起激活第二章进程管理2.3进程同步进程同步：指对多个相关进程在执行次序上的协调。这些进程相互合作，在一些关键点上可能需要互相等待或互通消息。进程同步的主要任务：使并发执行的诸进程间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。第二章进程管理2.3.1进程同步的基本概念1、两种形式的制约关系（并发进程间的关系）*资源共享关系*相互合作关系（间接相互制约）（直接相互制约）进程间彼此无关，进程同步要确保诸进程互斥的访问临界资源。进程间存在先后次序关系，进程同步要确保诸进程在执行次序上的协调，时间上无差错。第二章进程管理2.3.1进程同步的基本概念2、临界资源一段时间内只允许一个进程访问的资源；临界资源要求互斥的被访问。实例：生产者消费者问题第二章进程管理2.3.1进程同步的基本概念实例：生产者消费者问题同步规则：不允许消费者进程到一个空缓冲区去取消息；也不允许生产者进程向一个已装有消息且尚未取走消息的缓冲池投放消息。producerconsumer第二章进程管理2.3.1进程同步的基本概念实例：生产者消费者问题解决方案：1）数组buffer，表示具有n个缓冲区的缓冲池；输入指针in，指示下一个可投放消息的缓冲区；输出指针out，指示下一个可获取消息的缓冲区。2）采用循环缓冲方式：投放消息时：in=(in+1)modn获取消息时：out=(out+1)modn缓冲池空：in=out缓冲池满：(in+1)modn=out3）引入整形变量counter,表示当前缓冲中的消息数：投放消息时：counter=counter+1获取消息时：counter=counter-1第二章进程管理生产者/消费者问题的有界循环缓冲第二章进程管理producer:repeat…produceaniteminnextp;…whilecounter=ndono-op;buffer[in]:=nextp;in:=in+1modn;counter:=counter+1;untilfalse;consumer:repeatwhilecounter=0dono-op;nextc:=buffer[out];out:=(out+1)modn;counter∶=counter-1;…consumertheiteminnextc;…untilfalse;Varn,integer;typeitem=…;varbuffer:array［0,1,…,n-1］ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;第二章进程管理生产者程序和消费者程序都是正确的，而且顺序执行时其结果也是正确的。但在并发执行时，就会出现差错，问题就在于这两个进程共享变量counter。程序执行时，可简化描述如下：register1:=coun