电子科技大学计算机操作系统―第2章 进程管理

LOGO第二章2进程管理进程是操作系统最重要，最基本的概念之一，这个概念对操作系统的理解，描述和设计都具有极其重要的意义。本章讨论的主要问题1.什么是进程？如何描述进程？2.进程具哪些状态？如何控制进程状态的转换？3.进程的同步问题；进程的同步机制。4.进程通信及实现进程通信的机制。一、程序的顺序执行及特征如：有三条语句：s1：a：=x+ys2：b：=a-5s3：c：=b+1程序顺序执行的特征：执行顺序用有向图表示:s1s2s31.顺序性:处理机操作严格按照程序所规定的顺序执行。2.封闭性:程序独占资源,除初始状态外,只有程序本身规定的操作才能够改变资源状况,即程序在封闭环境下运行。3.可再现性:程序的运行结果与它执行的速度无关。一个具有独立功能的程序独占CPU直到完成的过程称为程序的顺序执行。2.1程序的执行与特征2.1程序的执行与特征1.前趋图（PrecedenceGraph）用前趋图来描述并发执行的程序的特征。前趋图DAG（DirectedAcyclicGraph）结点—表示一条语句，一段程序或进程。有向边—表示两结点间的偏序或前趋关系。二、程序的并发执行及特征其中：Pi称为Pj的直接前趋。PiPj前趋定义：{（Pi,Pj)}记为：PiPj2.程序的并发执行程序的并发执行是指在逻辑上相互独立的一组程序在执行时间上的相互重叠，即一个程序段的执行尚未结束，另一程序段的执行已经开始。2.1程序的执行与特征例：有三类程序并发执行：Ii—输入程序Ci—计算程序Pi—打印程序分析各程序之间的执行关系。2.1程序的执行与特征I1I2I3I4C1C2C3C4P1P2P3P4IiCiPiIiCiCiPi前趋关系：Pi-1，Ci，Ii+1可并发执行。IiIi+1CiCi+1PiPi+12.程序的并发执行多个程序同时申请同一资源，带来了资源的动态分配和共享。资源状态由多道程序共同决定。因此，并发程序的执行结果与其执行的相对速度有关。(1)并发执行的程序间相互约束，相互依赖显然，程序的并发执行与程序的顺序执行具有完全不同的特征，主要表现在：各并发执行的程序共享资源，使并无逻辑关系的程序间产生了相互制约的关系。而需共同协作完成同一任务的程序间相互依赖又相互制约。(2)对系统资源争夺与共享2.1程序的执行与特征3、程序并发执行的特征程序顺序执行程序并发执行顺序性间断性封闭性无封闭性可再现性不可再现性2.1程序的执行与特征2.1程序的执行与特征不可再现性是程序并发执行时的间断性及失去封闭性的必然结果，即程序的执行结果与其执行速度有关。例：程序A程序B....N:=N+1PRINT(N).N:=0....（1）执行顺序：(a），（b），（c）N值：n+1，n+1，0（2）执行顺序：（b），（a），（c）（3）执行顺序：（b），（c），（a）并发执行的程序P1,P2保持“可再现性”的Bernstein条件：Ｒ(P1)∩Ｗ(P2)∪Ｒ(P2)∩Ｗ(P1)∪Ｗ(P1)∩Ｗ(P2)={}（a）（b）（c）N值：n，n+1，0N值：n，0，1本节讨论关于进程的基本概念进程的定义进程的特征进程的状态进程控制块2.2进程的描述2.2进程的描述进程是可并发执行的程序在给定数据集合上的一次执行过程，是系统进行资源分配和调度的一个独立的基本单位和实体，是执行一个映象程序的总环境，是一个动态的概念。一.进程的定义进程的引入是为了更好地描述程序并发执行的动态特征。1.定义2.2进程的描述进程是执行程序的动态过程——动态概念。程序是进程运行的静态文本——静态概念。一个进程可以执行一个或多个程序。一个程序可以被多个进程执行。程序可以作为一种资源以文件的形式长期保存。进程只是一次执行过程，具有生命期。2.进程与程序的区别、联系2.2进程的描述进程是程序的一次执行过程具有生命期；它可以由系统创建并独立地执行，直至完成而被撤消。进程是可以并发执行的基本单位,从宏观上看,它们可以“同时”执行。由于共享资源进程间相互约束,相互依赖。动态性并发性独立性异步性各个进程之间相互独立,是系统分配资源和能够被处理机调度的基本单位。各个进程按照各自独立的、不可预知的速度异步向前推进。即进程按异步方式执行。二、进程的特征2.2进程的描述阻塞状态就绪状态执行状态调度I/O请求进程释放时间片到开始结束后备队列新状态结束状态三、进程的基本状态1.三种基本状态：执行状态(Executing)就绪状态(Ready)阻塞状态(Blocked)或等待(Wait)2.2进程的描述2.进程状态的细化挂起状态（Suspend）：对正在执行的进程，则停止执行。对就绪状态的进程，则停止调度，并回收资源。对阻塞状态的进程，则停止条件的发生。称被挂起的进程是静止的{静止就绪（Readys）静止阻塞（Blockeds）未称被挂起的进程是活动的{活动就绪（Readya）活动阻塞（Blockeda）将进程挂起的原因：1.系统工作负荷达到高峰，调整负荷，使系统正常运行。2.人为挂起，停止某进程执行，以便研究分析。3.系统需要，如系统故障，系统检测需要。2.2进程的描述3.细化的进程状态图活动阻塞执行状态活动就绪静止就绪静止阻塞调度释放I/O请求激活激活挂起挂起挂起释放2.2进程的描述1.进程的描述对进程的描述应该反映进程的存在及其变化，反映进程的动态特性。进程的程序—静态文本，描述进程所要完成的功能。数据集合—程序运行时所需的数据和工作区。静态描述动态描述进程控制块—PCB（ProcessControlBlock）记录和描述进程的动态特性,描述进程的执行情况和状态变化。四、进程控制块进程标识信息外部标识信息内部标识信息进程家族标识处理机状态信息通用寄存器指令计数器程序状态字（PSW）用户栈指针进程调度信息进程状态进程优先级其他调度信息等待事件进程控制信息程序数据地址进程同步及通信资源清单链接指针2.PCB块包含的信息2.2进程的描述2.2进程的描述不同操作系统，PCB所包含的信息类型及数量可能有所不同，但一般包括两类信息。1）调度信息描述进程的当前状况，供进程调度使用。2）现场信息刻划了进程运行的情况；记录在进程运行过程中会改变的信息，以便进程中断后，再次被调度时能够继续运行。PCB块是一个进程存在的唯一标志，当系统创建一个进程时，为该进程设置一个PCB，再利用PCB对进程进行控制和管理。当进程撤消时，系统回收它的PCB。3.PCB块的组织方式•链接方式链接成各种就绪，阻塞及空白等各种队列。•索引方式建立不同状态的索引表。2.2进程的描述2.3进程控制操作系统中，为了防止用户进程对OS及PCB等关键信息的破坏。一个进程在其生命期中有两种机器运行状态：系统态(核心态,管态)具有较高的访问权，可访问核心模块。用户态(目态)限制访问权。是机器指令的延伸,是非进程模块,不能并发执行。执行过程不可中断，用微代码实现。2.原语（primitive）一、操作系统的内核1.进程运行状态内核是OS的控制和协调中心，由它组织，启动和协调系统中各种活动。通常由各种原语构成。操作系统内核内核是OS中最重要最核心的部分。OS的内核紧靠硬件，由那些使用频率高，与硬件紧密相关的模块构成；如中断处理程序，设备驱动程序等。2.3进程控制2.3进程控制1.中断处理中断是OS内核最重要的功能之一。所有中断都由内核响应,中断是进程并发执行的基础，OS是由中断驱动的。2.原语操作原语操作包括涉及CPU管理，存储管理，设备管理，文件管理的各种基本操作。3.时钟管理OS的许多重要·操作，如：按时间片轮转调度,实时系统的截止时间控制等,都依赖于时钟管理。二.内核的功能2.3进程控制中断源—引起中断的异步事件（如：系统调用，I/O请求，进程调度，设备驱动，文件处理等）。中断请求—向CPU发出中断信号。中断响应—CPU停止执行当前进程,分辨中断请求的类型。中断处理—CPU将请求交相关的中断处理程序处理。中断返回—众多处理结束，返回断点。内核对中断的有限处理方式中断源中断请求中断响应转中断处理程序退出中断向CPU保护CPU现场识别中断源恢复CPU现场2.3进程控制创建原语create（）撤消原语destroy（）阻塞原语block（）唤醒原语wakeup（）挂起原语suspend（）激活原语active（）三、进程控制原语2.3进程控制创建进程有两种方式：由系统程序模块创建，或由父进程创建。算法步骤：1.向PCB集合申请一个空闲的PCB，并获取其内部标识；2.将有关信息填入PCB；3.将该进程置为就绪状态，并插入就绪队列。创建原语create（）对进程的控制一般通过原语操作实现。2.3进程控制创建原语(create)创建原语算法查PCB集有空PCBN创建失败Y取空表PCB（i）将参数填入PCB（i）将PCB（i）插入就绪队列2.3进程控制算法步骤：1.根据外部标识检索PCB集，找到要撤消的PCB；2.从队列中撤消该进程及其子孙进程，通常在一个递归过程中实现；3.释放被撤消进程所占有的资源，撤消进程控制块。撤消原语destroy（）当进程完成或产生异常中断时，应立即撤消，并释放其所有资源。2.3进程控制撤消原语(destroy）撤消原语算法查PCB集和进程家族有此PCB？N出错处理Y释放进程所占资源释放PCB（i）结构该PCB有子进程？YN2.3进程控制进程在执行过程中，需要等待某些条件发生时，由该进程调用阻塞原语把进程从执行状态转换为阻塞状态。算法步骤：1.中断CPU执行，将CPU的当前状态保存到PCB的现场信息。2.将进程的当前状态置为阻塞状态；3.将进程的PCB插入到该事件的阻塞队列中。阻塞原语block（）算法步骤：1.在等待队列中找到该进程，将其PＣＢ的当前状态置为就绪；2.将进程从等待队列中撤消，并插入到就绪队列中。唤醒原语wakeup（）当处于阻塞状态的进程所等待的事件发生后，使用唤醒原语将进程从等待状态转换为就绪状态。2.3进程控制进程在执行过程中，根据用户或系统的某种需要，调用挂起原语将进程从活动状态转换为静止状态。算法步骤：1.根据外部标识检索PCB集，找到要挂起的PCB块；2.检查被挂进程的当前状态：◆执行态静止就绪，插入静止就绪队列，并转调度程序，重新调度。◆活动就绪静止就绪，插入静止就绪队列。◆活动阻塞静止阻塞，插入静止阻塞队列。挂起原语suspend（）2.3进程控制激活原语active（）当处于静止状态的进程所等待的激活事件发生后，使用激活原语将进程从静止状态转换为活动状态。算法步骤：1.确定要激活的进程；2.检查被挂进程的当前状态：3.将进程从相应的静止状态活动状态。2.3进程控制进程管理讨论的主要问题1.如何控制和协调并发进程异步执行的时序？进程的同步机制2.进程之间如何互相联系，传递信息？进程的通信2.4进程同步的概念并发执行的进程之间，通常有两种关系：互斥关系进程之间彼此无关，但是由于竞争使用同一共享资源而产生了相互约束的关系。称为进程的互斥。—间接相互制约关系同步关系多个并发执行的进程，在共同协作完成一项任务的过程中，相互约束，进程之间通过在执行时序上的某种限制而达到相互合作。这种约束关系称为进程的同步—直接相互制约关系一、并发进程间的约束关系同步问题缓冲区键盘计算缓冲区缓冲区B进程A进程A进程只有当缓冲区为空时，才能将数据输入缓冲区B进程只有当缓冲区有数据时，才能从缓冲区取数进行计算。进程的同步与互斥虽然是两个既有区别又有联系的概念，但从本质上看并发进程的异步执行都必须按一定的相互约束的时序进行，因此统称为“进程同步”。显然，必须解决好进程的同步问题，才能保证并发进程的正常执行。2.4进程同步的概念二、临界资源（criticalsource）1.什么是临界资源凡是以互斥方式使用的共享资源都称为临界资源。临界资源具有一次只允许一个进程使用的属性。2.临界区（criticalsection）每个进程互斥访问临界资源的那段代码称为临界区。代码构成如下：repeatentrysection进入区—申请进入临界区crit