OS第3章进程管理(MR)

计算机操作系统第三章进程管理本章教学内容3.1进程的概念3.2进程的描述3.3进程状态及其转换3.4进程控制3.5进程互斥3.6进程同步3.7进程通信3.8死锁问题3.9线程的概念3.10线程分类与执行本章学习目标进程的概念进程的描述、状态及转换进程控制的实现进程的互斥与同步进程的通信进程死锁问题的解决线程3.1进程的概念程序的并发执行进程的定义程序的顺序执行(1)程序的顺序执行程序是人们要计算机完成的一些指令序列，是一个按严格次序、顺序执行的操作序列，是一个静态的概念。我们把一个具有独立功能的程序独占处理机，直到最后结束的过程称为程序的顺序执行。3.1进程的概念I1I1O1P1I2P2O2程序顺序执行程序的顺序执行(2)程序顺序执行时的特征①顺序性。②封闭性。③可再现性。3.1进程的概念多道程序系统中的程序执行环境的变化需要计算机能够同时处理多个具有独立功能的程序;特点:独立性随机性资源共享3.1进程的概念程序的并发执行(1)什么是程序的并发执行:所谓程序的并发执行是指多道程序在同一时间间隔内同时发生。程序的并发执行可总结为：一组在逻辑上互相独立的程序或程序段在执行过程中，其执行时间在客观上互相重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始的一种执行方式。3.1进程的概念I1I2I3I4C1C4P1P4C2C3P2P3输入、计算、打印程序对一批程序进行处理的执行顺序程序的并发执行顺序执行与并发执行的比较3.1进程的概念顺序执行并发执行程序顺序执行程序具有封闭性独享资源具有可再现性间断执行，多个程序各自在“走走停停”中进行程序失去封闭性共享资源失去其可再现性有直接和间接的相互制约程序的并发执行(2)程序并发执行的判断方法：Bernstein条件解释：运算的读集是指在运算执行期间引用的所有变量的集合；记作R(Si)运算的写集是指在运算执行期间要改变的所有变量的集合。记作W(Si)3.1进程的概念程序的并发执行原理：不同运算（或程序）的读集与写集的交集和写集与写集的交集的并集为空集时，这几个运算（或程序）可以并发执行。如果两个程序P1和P2满足下述条件，它们便并发执行，否则不能．R(P1)∩W(P2)∪W(P1)∩R(P2)∪W(P1)∩W(P2)={Φ}3.1进程的概念例：下面有四条语句：语句读集写集P1:a=x+y;R(P1)={x,y}W(P1)={a}P2:b=z+1;R(P2)={z}W(P2)={b}P3:c=a+b;R(P3)={a,b}W(P3)={c}P4:d=c-2;R(P4)={c}W(P4)={d}试问P1和P2是否可以并发执行?P1和P3是否可以并发执行?程序的并发执行3.1进程的概念程序的并发执行(3)程序并发执行所带来的影响：如果并发执行的程序段不按照特定的规则和方法进行资源共享和竞争，则其执行结果将不可避免地失去封闭性和可再现性。例（P41）3.1进程的概念程序的并发执行3.1进程的概念proceduregetaddr(top)beginlocalrr←(top)top←top-1returnrendprocedurereladdr(blk)begintop←top+1(top)←blkend进程的定义⒊1.2人们对进程下过许多定义。现列举其中的几种：（1）进程是一个独立的可以调度的活动。（2）进程是可以并行执行的计算部分。（3）进程是一个抽象实体，当它执行某个任务时，将要分配和释放各种资源。（4）行为的规则叫程序，程序在处理机上执行时的活动称为进程。（5）一个进程是一系列逐一执行的操作，而操作的确切含义则有赖于以何种详尽程度来描述进程。进程：一个具有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基本单位。(1978年全国操作系统会议)3.1进程的概念进程与程序进程和程序是两个完全不同的概念，但又有密切的联系。它们之间的主要区别是：（1）程序是静态的概念；而进程则是程序的一次执行过程。它是动态的概念。（2）进程是一个能独立运行的单位，能与其它进程并发执行；而程序是不能作为一个独立运行的单位而并发执行的。（3）进程是竞争计算机资源的基本单位，从而其并发性受到系统自己的制约。（4）不同的进程可以包含同一程序，只有该程序所对应的数据集不同。进程的特性从进程与程序的区别可以看出，进程具有如下特征：动态性:是进程最基本的特性。进程由创建而产生，由调度而执行，因得不到资源而暂停执行，以及因撤消而消亡。并发性:这是指多个进程实体，同存于内存中，能在一段时间段内同时执行。并发性是进程的重要特征，同时也是操作系统的重要特征。提高并发性，可以提高系统的效率。独立性:进程是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。异步性:这是指进程按各自独立的、不可预知的速度向前推进；或者说，进程按异步方式运行。结构特征:从结构上看，进程实体是由程序段、数据段及进程控制块三部分组成，也称这三部分为进程映像。3.1进程的概念3.2进程的描述进程控制块PCB进程上下文进程空间进程的描述进程实体通常是由程序、数据集合和PCB这三部分构成，也称为“进程映象”。进程的一般组成模型3.2进程的描述PCB程序段数据段进程控制块PCBPCB集中反映一个进程的动态特征，当系统创建了一个新进程时，就为它建立一个PCB；当进程终止后，系统回收其PCB，该进程在系统中就不存在了。所以，PCB是进程存在的惟一标志。PCB分成四个组成部分：描述信息、控制信息、资源管理信息、CPU现场保护结构。3.2进程的描述描述信息①进程名或进程标识号②用户名或用户标识号③家族关系进程控制块PCBPCB控制信息描述信息资源管理信息CPU现场保护结构控制信息①进程当前状态②进程优先级③程序开始地址④各种计时信息⑤通信信息资源管理信息①占用内存大小及其管理用数据结构指针②主存的对换或覆盖用的有关信息③共享程序段大小及起始地址④使用输入输出设备的信息⑤指向文件系统的指针及有关标识等。CPU现场保护结构记录重要的寄存器及时钟等内容进程上下文进程上下文是进程执行活动全过程的静态描述。进程上下文是一个与进程切换和处理机状态发生交换有关的概念。其中:上文:已执行过的进程指令和数据在相关寄存器与堆栈中的内容正文:正在执行的进程指令和数据在相关寄存器与堆栈中的内容下文:待执行的进程指令和数据在相关寄存器与堆栈中的内容3.2进程的描述进程上下文进程上下文包括计算机系统中与执行该进程有关的各种寄存器的值、程序段在经过编译之后形成的机器指令代码集、数据集及各种堆栈的值和ＰＣＢ结构。3.2进程的描述图3.2进程上下文结构进程上下文切换3.2进程的描述图3.4进程上下文的切换过程进程空间与大小任一进程，都有一个自己的地址空间，把该空间称为进程空间或虚空间。进程空间的大小只与处理机的位数有关。如一个16位长处理机的进程空间大小为216，一个32位长处理机的进程空间大小为232。3.2进程的描述图3.5进程空间示例进程与程序进程程序动态静态暂时永久并发执行顺序执行PCB-------多个一个一个多个3.3进程状态及其转换进程状态进程状态转换进程状态进程通常有五种基本状态：初始状态:当一个新进程刚刚建立，还未将其放入就绪队列时的状态，称为新状态。就绪状态（ready）:进程运行所需的外部条件满足，但因为其它进程已占用CPU，所以暂时不能运行。执行状态(running):外部条件满足进程已获得CPU，其程序正在执行。在单处理机系统中只有一个进程处于执行状态。等待（阻塞）状态(blocked):进程因等待某种事件发生，而暂时不能运行的状态，称为等待状态，也称为阻塞状态。系统中处于这种状态的进程可能有多个，通常将它们排成一个队列，也有的系统则根据阻塞原因的不同将这些进程排成多个队列。终止状态:当一个进程已经正常结束或异常结束，操作系统已将其从系统队列中移出，但尚未撤消，这时称为终止状态。3.3进程状态及其转换进程状态转换3.3进程状态及其转换图3.6进程状态转换进程状态转换3.3进程状态及其转换原状态转换后的状态初始执行就绪等待终止初始××OS准备运行新的进程××执行××超时；OS响应具有更高优先级的进程等OS服务请求；资源请求进程完成；进程夭折就绪×被分派程序选择为下一个即将执行的进程××被父进程终止等待××事件发生×被父进程终止进程状态转换3.3进程状态及其转换内存进程γ进程α进程β分派程序例：在内存中有３个进程，有一个分派程序负责把处理器分配给进程。（如图１）图2列举了3个独立进程的执行轨迹。其中有进程α和γ开始的12条指令，以及进程β的6条指令，并假设进程β的第4条指令包括I/O操作。（假设操作系统在每个进程连续执行6个指令周期后会产生中断）α+0β+0γ+0α+1β+1γ+1α+2β+2γ+2α+3β+3γ+3α+4β+4γ+4α+5β+5γ+5α+6γ+6α+7γ+7α+8γ+8α+9γ+9α+10γ+10α+11γ+11进程α进程β进程γ图2进程的轨迹例：图１内存中有三个进程的例子3.４进程控制进程创建与撤销进程的阻塞与唤醒进程控制所谓进程控制，是系统使用一些引起具有特定功能的程序段来创建、撤销进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。3.４进程控制原语原语：把系统态下执行的某些具有特定功能的程序段称为原语。机器指令级:特点是执行期间不允许被中断功能级:特点是不允许并发执行。(原语本身由若干条指令组成，要么全做，要么全不做)用于进程控制的原语有：创建原语撤销原语阻塞原语唤醒原语3.４进程控制进程创建进程创建方式有：①由系统程序模块统一创建②由父进程创建3.４进程控制进程创建创建原语创建一个进程的过程:（1）申请空白PCB。（2）为新进程分配资源。（3）初始化进程控制块。（4）将新建进程插入就绪态队列。3.４进程控制图3.7创建原语流图进程撤销以下几种情况导致进程被撤销：①进程已完成所要求的功能而正常终止②由于某种错误导致非正常终止③祖先进程要求撤销某个子进程3.４进程控制进程撤销撤销过程如下：（1）根据被终止进程的标识符，从PCB队列中检索出该进程的PCB，从中读出该进程的状态。。（2）若被终止进程正处于执行状态，应立即终止该进程的执行，该进程被终止后应重新进程调度。（3）检查该进程有无子孙进程，若有，则应将其所有子孙进程终止。（4）释放终止的进程所占有的资源，将其归还它的父进程或者系统。（5）释放它的PCB结构本身。3.４进程控制图3.8撤销原语流图进程阻塞引起进程阻塞的事件①请求系统服务②启动某种操作③④3.４进程控制进程阻塞进程的阻塞：当一个进程所等待的某一事件尚未发生时，该进程调用阻塞原语block()将自己阻塞，转换为等待状态。3.４进程控制图3.9阻塞原语图进程的唤醒唤醒一个进程有两种方法，分别是由系统进程唤醒和由事件发生进程唤醒。处于等待状态的进程，只有当该进程所等待的外部事件发生时，才调用唤醒原语wakeup()将它唤醒。3.４进程控制图3.10唤醒原语3.５进程互斥资源共享所引起的制约互斥的加锁实现信号量和Ｐ，Ｖ原语用Ｐ，Ｖ原语实现进程互斥临界资源临界资源：在系统中有许多硬件或软件资源，在一段时间内只允许一个进程访问或使用，这种资源称为临界资源。临界资源可能是一些独占设备，如打印机、磁带机等；也可能是一些共享变量、表格、链表等。3.5进程互斥临界资源3.5进程互斥图3.11多进程共享内存栈区示例getspace:begin1:localg2:g←stack[top]3:top←top-1endrelease(ad):begin4:top←top+15:stack[top]←adend临界区不论是硬件临界资源,还是软件临界资源,多个进程必须互斥地对它进行访问。我们把在每个进程中访问临界资源的那段程序称为临界区。