chap进程管理

1、3.1 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理第三章第三章: : 进程管理进程管理为什么要引入进程的概念为什么要引入进程的概念进程的表示和调度状态进程的表示和调度状态进程的控制进程的控制进程调度进程调度进程通讯进程通讯死锁死锁3.2 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3.1 3.1 为什么要进入进程的概念为什么要进入进程的概念前趋图的定义前趋图的定义顺序程序顺序程序程序的并发执行和资源共享程序的并发执行和资源共享程序并发执行的特性程序并发执行的特性进程概念的引入进程概念的引入3.3 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理一、

2、前趋图的定义一、前趋图的定义 前趋图前趋图(procedence graph)是一个有向无环图是一个有向无环图dag (directed acyclic graph)。图中的每一个顶点可。图中的每一个顶点可表示一条语句、一个程序段或进程表示一条语句、一个程序段或进程, 弧则表示两顶点弧则表示两顶点之间的偏序之间的偏序 (partial order) 或前趋关系或前趋关系 (procedence relation)。无前趋的顶点为初始顶点。无前趋的顶点为初始顶点, 无后继的顶点无后继的顶点称为终止顶点称为终止顶点, 每个顶点还有一个权值每个顶点还有一个权值, 它表示顶点它表示顶点执行所需的时间。

3、如执行所需的时间。如1352467 它的每一种拓扑排序都是顺序执行时正确得到它的每一种拓扑排序都是顺序执行时正确得到结果的顺序结果的顺序,有路经的两顶点必须按前趋关系顺序执有路经的两顶点必须按前趋关系顺序执行行,无路经的两顶点则可以并发执行。无路经的两顶点则可以并发执行。3.4 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理程序顺序执行：程序顺序执行： 程序执行时程序执行时, 必须按某种先后次序必须按某种先后次序, 只有当前操作只有当前操作完成后才能执行后继操作完成后才能执行后继操作, 它体现了某种算法。如：它体现了某种算法。如：s1: a:=x+y;s2: b:=a-5;s3:

4、 c:=b+1; 各程序段与此相同各程序段与此相同, 以以 i c p分别代表输入计算和输出分别代表输入计算和输出, 则前趋图：则前趋图：前趋图前趋图s1s2s3i1c1p1i2c2p2二、程序顺序执行二、程序顺序执行3.5 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理顺序环境：顺序环境：在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响特征：特征：程序执行的顺序性程序执行的封闭性独占资源，执行过程中不受外界影响程序结果的可再现性程序运行结果与程序执行速度无关，只要初始状态相同，结果应相同3.6 计算机操作系统计算机操作系统 第三章第三章 进程管理

5、进程管理三、程序的并发执行和资源共享三、程序的并发执行和资源共享程序的并发执行程序的并发执行在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的并发执行是指两个程序的执行在时间上是重叠的3.7 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理多个程序的并发执行：多个程序的并发执行： 在一定时间内物理机器上有两个或两个以上在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的。宏观上同时处于运行状态次序不是事先确定的。宏观上同时处于运行状态微观上各程序交

6、替地间断运行。微观上各程序交替地间断运行。i1i2i3i4c1c2c3c4p1p2p3p4前趋关系前趋关系:iici , pipi+1 cipi , iiii+1 cici+1ii+1, ci, pi-1是重叠的是重叠的3.8 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理 举例说明举例说明: 假如系统中有两道程序假如系统中有两道程序aa和和bb：program aa; program bb;begin begin an bn n:=n+1; aa+1 n:=n+1; bb+1 na nb end; end;int n=1; 是是aa和和bb都能访问的外部公共变量都能访问的外部公

7、共变量,这两这两个程序在并发执行个程序在并发执行, n:=n+1;可分解为可分解为3条机器指令条机器指令,它们的执行顺序不同有可能导致它们的执行顺序不同有可能导致n的值结果不同。的值结果不同。3.9 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理时间时间 t0 t1 t2 t3 t4 t5t0 t1 t2 t3 t4 t5程序程序a aa an na aa+1a+1n na a程序程序b bb bn nb bb+1b+1n nb bn n的值的值 1 1 2 2 2 31 1 2 2 2 3 (a)顺序顺序执行执行时间时间 t0 t1 t2 t3 t4 t5t0 t1 t2 t3

8、 t4 t5程序程序a a程序程序b bn n的值的值 1 1 1 1 2 21 1 1 1 2 2 (b)交叉交叉执行执行时间时间 t0 t1 t2 t3 t4 t5t0 t1 t2 t3 t4 t5程序程序a a程序程序b bn n的值的值 1 1 1 1 2 21 1 1 1 2 2 (c)交叉交叉执行执行n nb bb bb+1b+1b bn na an na aa+1a+1n na aa an nn na aa aa+1a+1n nb bb bb+1b+1b bn n3.10 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理资源共享系统中硬件和软件资源不再为单个用户程序所

9、独占，而由几个用户程序共同使用。程序并发执行和资源共享是现代操作系统的基本特性，它们之间互为依存。并发的特征1.程序结果的不可再现性：并发程序执行的结果与其执行的相对速度有关，是不确定的2.在并发环境下程序的执行是间断性的：执行停执行3.程序和机器执行程序的活动不再一一对应4.并发程序间的相互制约3.11 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理四、进程概念的引入四、进程概念的引入进程概念的引入“程序”这个静态概念已不能如实反映程序并发执行过程中的特征。进程的定义从不同的角度对进程的各种定义 进程是程序的一次执行 进程是可以和别的计算并发执行的计算 进程是一个数据结构及能在

10、其上进行操作的程序 进程是程序及其数据在处理机上顺序执行的活动 进程是程序在某一数据集合上的运行过程程序的一次执行，该程序可与其它程序并发执行。（可程序的一次执行，该程序可与其它程序并发执行。（可并发执行的程序在一个数据集合上的执行过程并发执行的程序在一个数据集合上的执行过程.).) 3.12 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理 结构性：结构性：由程序由程序+数据数据+进程控制块组成了进程实体进程控制块组成了进程实体, 称之为称之为进程映像。进程控制块是进程存在的标志。进程映像。进程控制块是进程存在的标志。 动态性动态性进程是进程实体的执行过程进程是进程实体的执行过程

11、, 它由创建而产生它由创建而产生, 由由调度而执行调度而执行,因某事件而暂停因某事件而暂停, 由撤销而消亡。在生由撤销而消亡。在生命周期内命周期内, 进程在三种基本状态之间动态转换进程在三种基本状态之间动态转换 并发性并发性 多个进程同时存于内存中多个进程同时存于内存中,一起向前推进一起向前推进,并发执行并发执行 独立性独立性 进程是独立获得资源和独立调度的基本单位进程是独立获得资源和独立调度的基本单位 异步性异步性 各进程都各自独立的不可预知的速度向前推进各进程都各自独立的不可预知的速度向前推进进程的特征进程的特征3.13 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理程序与进

12、程之间的区别：程序与进程之间的区别： 进程更能真实地描述并发，而程序不能进程更能真实地描述并发，而程序不能 进程是由程序、数据和进程控制块三部分组成的进程是由程序、数据和进程控制块三部分组成的 程序是静态的，进程是动态的程序是静态的，进程是动态的 进程有生命周期，有诞生有消亡，短暂的；而程进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的序是相对长久的 一个程序可对应多个进程，反之亦然一个程序可对应多个进程，反之亦然 进程具有创建其他进程的功能，而程序没有进程具有创建其他进程的功能，而程序没有3.14 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3.2 3.2 进程的表示

13、和调度状态进程的表示和调度状态进程的表示进程的表示进程的组成进程控制块调度状态调度状态进程的基本调度状态细分的进程调度状态3.15 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理一、进程的组成一、进程的组成进程由程序、数据集合和进程由程序、数据集合和pcbpcb三部分组成三部分组成程序部分描述了进程所要完成的功能。数据集合包括程序在执行时所需要的数据和工作区进程控制块（pcb）：用来描述进程当前状态的数据结构，是进程的动态特性的集中反映。随着进程的创建而产生，进程的撤销而被收回。3.16 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3.17 计算机操作系统计算机操

14、作系统 第三章第三章 进程管理进程管理二、进程控制块二、进程控制块pcbpcbpcbpcb应包含如下一些信息：应包含如下一些信息：1.进程表示名或标示数2.位置信息3.状态信息 4.进程的优先级5.现场保护区6.资源清单7.队列指针或链接字8.进程同步和通信等其它信息3.18 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理三、进程的调度状态三、进程的调度状态进程的三种基本状态：进程的三种基本状态：运行状态：进程占有cpu，并在cpu上运行就绪状态：一个进程已经具备运行条件，但由于无cpu暂时不能运行的状态（当调度给其cpu时，立即可以运行）阻塞状态：指进程因等待某种事件的发生而暂

15、时不能运行的状态 （即使cpu空闲，该进程也不可运行）进程在生命消亡前处于且仅处于三种基本状态之一进程在生命消亡前处于且仅处于三种基本状态之一3.19 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理进程状态转换：进程状态转换： 在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换就绪就绪 - - 运行运行时间一到，调度程序选择一个新的进程运行运行运行 - - 就绪就绪运行进程用完了时间片运行进程被中断，因为一高优先级进程处于就绪状态运行运行 - - 阻塞阻塞当一进程所需的东西必须等待时os尚未完成服务对一资源的访问尚不能进行初始化i/o

16、 且必须等待结果等待某一进程提供输入 (ipc)阻塞阻塞 - - 运行运行当所等待的事件发生时3.20 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理运行运行就绪就绪阻塞阻塞进程的状态及其转换进程的状态及其转换调度调度超时超时i/o请求请求i/o完成完成3.21 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理静止静止就绪就绪静止静止阻塞阻塞挂挂起起挂起挂起挂起挂起超超时时执行执行活动活动就绪就绪活动活动阻塞阻塞调调度度等待事件等待事件,请求请求i/o事件发生事件发生i/o完成完成激活激活激活激活事件发生事件发生i/o完成完成七状态进程模型七状态进程模型终止终止创建创

17、建释放释放许可许可3.22 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3.3 3.3 进程的控制进程的控制创建、撤消进程以及完成进程各状态之间的转换。由具有特定功能的原语完成。内核的各项功能是通过执行原语来实现的原语的定义是指若干条机器指令构成的并用以完成特定功能的一段程序，这段程序在执行期间是不可分割的 由以下原语完成：进程创建原语进程创建原语进程撤消原语进程撤消原语阻塞原语、唤醒原语阻塞原语、唤醒原语挂起原语、激活挂起原语、激活( (解挂解挂) )原语原语( (选学选学) )3.23 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理1.1.进程图进程图 进程图

18、是用于描述进程家族关系的有向图，子进程可以进程图是用于描述进程家族关系的有向图，子进程可以继承父进程所拥有的资源。继承父进程所拥有的资源。一、进程的创建一、进程的创建a ab bc cd df fg gh he ei ij j3.24 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理2.进程何时创建进程何时创建? 引起创建进程的事件：引起创建进程的事件： 用户登录、作业调度、提供服务、应用请求用户登录、作业调度、提供服务、应用请求1) 用户登录时用户登录时, 由由os为合法终端创建一个进程为合法终端创建一个进程2) 调度到某个批处理作业时调度到某个批处理作业时,由作业调度程序创建由

19、作业调度程序创建3) 运行程序请求提供服务运行程序请求提供服务(如如:打印文件打印文件),由由os创建创建 4) 运行中进程因自己的需要运行中进程因自己的需要,由它自己创建子进程由它自己创建子进程3.25 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3.3.进程的创建过程进程的创建过程 一旦发现了要求创建新进程的事件一旦发现了要求创建新进程的事件,os,os便调用创建原便调用创建原语语, , 按以下过程创建新进程。按以下过程创建新进程。1)1) 分配一个唯一的进程标识符分配一个唯一的进程标识符, ,索取一个空白索取一个空白pcbpcb2)2) 为新进程的程序和数据分配内存空间为

20、新进程的程序和数据分配内存空间3)3) 初始化进程控制块初始化进程控制块 初始化标识符信息初始化标识符信息( (填入填入) )、处理机的状态信息、处理机的状态信息( (指令指指令指针针, , 栈指针栈指针) )和控制信息和控制信息( (状态状态, ,优先级优先级.).)1)1) 设置相应的链接设置相应的链接如如: : 把新进程加到就绪队列的链表中把新进程加到就绪队列的链表中3.26 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理1. 1. 进程何时终止进程何时终止? ?1)1) 正常结束正常结束批处理系统中批处理系统中, ,进程已运行完成遇到进程已运行完成遇到 halt halt

21、 指令指令分时系统中分时系统中, , 用户退出登录用户退出登录2)2) 异常结束异常结束本进程发生出错和故障事件本进程发生出错和故障事件存储区越界、保护性错存储区越界、保护性错( (如如: :写只读文件写只读文件) )、特权、特权指令错、非法指令指令错、非法指令( (如如: :程序错转到数据区程序错转到数据区) )、算、算术运算错、运行超时、等待超过时、术运算错、运行超时、等待超过时、i/o i/o 失败、失败、3)3) 外界干预外界干预操作系统干预、父进程请求、父进程终止操作系统干预、父进程请求、父进程终止二、二、 进程的终止进程的终止( (撤消撤消) )3.27 计算机操作系统计算机操作系

22、统 第三章第三章 进程管理进程管理2. 进程的进程的终终止过程止过程 一旦发生终止进程的事件一旦发生终止进程的事件,os便调用撤消原语便调用撤消原语,按以下过程终止该进程。按以下过程终止该进程。1) 从从pcb中读取进程的状态中读取进程的状态2) 若进程处于执行态若进程处于执行态, 应立即终止该进程的执行应立即终止该进程的执行,并置调度标志为真并置调度标志为真(以便该进程终止后系统重新以便该进程终止后系统重新进行调度进行调度,将处理机分配给新选择的进程将处理机分配给新选择的进程)3) 若有子孙进程则将它们全部终止若有子孙进程则将它们全部终止,以防它们失控以防它们失控4) 将该进程所占有的全部资

23、源还给父进程或系统将该进程所占有的全部资源还给父进程或系统5) 将该进程的将该进程的pcb从所在队列中移出从所在队列中移出3.28 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理三、三、 进程的阻塞、唤醒、挂起与激活进程的阻塞、唤醒、挂起与激活1.进程的阻塞进程的阻塞 处于运行状态的进程处于运行状态的进程, 在其运行过程中期待某一事在其运行过程中期待某一事件发生件发生, 如如:请求系统服务、等待键盘输入、等待数据请求系统服务、等待键盘输入、等待数据传输完成、等待其它进程发送消息传输完成、等待其它进程发送消息, 当被等待的事件未当被等待的事件未发生时发生时, 由进程调用阻塞原语由进

24、程调用阻塞原语(block), 将自己阻塞。将自己阻塞。 阻塞原语使处于运行态的进程停止运行阻塞原语使处于运行态的进程停止运行, 将运行将运行现场保存在其现场保存在其 pcb 的的 cpu 现场保护区现场保护区, 然后将然后将 pcb中的现行状态由运行态变为阻塞态中的现行状态由运行态变为阻塞态, 并并将该进程插入将该进程插入到相应事件的阻塞队列中。最后到相应事件的阻塞队列中。最后, 转进程调度程序重转进程调度程序重新调度新调度, 将处理机分配给一个就绪进程将处理机分配给一个就绪进程, 按新进程按新进程 pcb 中的处理机状态设置中的处理机状态设置cpu环境环境, 使它投入运行。使它投入运行。3

25、.29 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理 2. 进程的唤醒进程的唤醒 当被阻塞进程期待的事件到来时当被阻塞进程期待的事件到来时, 由中断处理进程或由中断处理进程或其它产生该事件的进程调用唤醒原语其它产生该事件的进程调用唤醒原语(wakeup), 将期待该将期待该事件的进程事件的进程唤醒。唤醒。 唤醒原语执行时唤醒原语执行时, 将被阻塞进程从相应等队列中移出将被阻塞进程从相应等队列中移出, 并将其并将其 pcb中的现行状态由阻塞改为就绪态中的现行状态由阻塞改为就绪态, 然后将该然后将该进程插入进程插入就绪就绪队列中。队列中。 若事件是等待若事件是等待 i/o 完成完成

26、, 则由硬件提出中断请求则由硬件提出中断请求, cpu响应中断响应中断, 暂停当前进程的执行暂停当前进程的执行, 转去中断处理。检转去中断处理。检查有无等待该查有无等待该 i/o完成的进程。若有完成的进程。若有, 则将它唤醒。然后则将它唤醒。然后结束中断处理。返回被中断进程或重新调度。结束中断处理。返回被中断进程或重新调度。 若事件是等待某进程发一个信息若事件是等待某进程发一个信息, 则由发送进程把该则由发送进程把该等待进程唤醒。等待进程唤醒。3.30 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理 3. 进程的挂起进程的挂起 当进程请求将自己挂起或父进程请求将子进程挂起时当进程

27、请求将自己挂起或父进程请求将子进程挂起时, 调用挂起原语调用挂起原语(suspend), 将指定进程挂起将指定进程挂起。 执行过程执行过程: 检查要挂起进程的状态检查要挂起进程的状态, 若处于活动就绪态若处于活动就绪态就将其改为静止就绪态就将其改为静止就绪态, 对于活动阻塞态的进程则将其改对于活动阻塞态的进程则将其改为静止阻塞态。如果被挂起的进程正在执行则还要转到调为静止阻塞态。如果被挂起的进程正在执行则还要转到调度程序重新调度。度程序重新调度。 4. 进程的激活进程的激活 要激活指定进程时要激活指定进程时,调用激活原语调用激活原语(active)将它激活将它激活 执行过程执行过程: 将要激活

28、的进程调入内存将要激活的进程调入内存, 并检查它的状态并检查它的状态, 若是静止就绪态则将其改为活动就绪态若是静止就绪态则将其改为活动就绪态,若为静止阻塞态就若为静止阻塞态就将其改为活动阻塞态。如果采用的是抢占调度策略将其改为活动阻塞态。如果采用的是抢占调度策略,被激活被激活的进程优先级高则引起重新调度。的进程优先级高则引起重新调度。3.31 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3.4 进程调度进程调度 无论在多道批处理系统还是分时系统中，系统中无论在多道批处理系统还是分时系统中，系统中的用户进程数都远远超过处理机数，除用户进程的用户进程数都远远超过处理机数，除用户进程

29、要占用处理机外，操作系统还要建立若干个系统要占用处理机外，操作系统还要建立若干个系统进程完成系统功能。这么多的进程竞争处理机，进程完成系统功能。这么多的进程竞争处理机，就要求系统提供进程调度功能，以便采用一些策就要求系统提供进程调度功能，以便采用一些策略，将处理机动态地分配给系统中的各个就绪进略，将处理机动态地分配给系统中的各个就绪进程，使之执行。分配处理机的任务是由进程调度程，使之执行。分配处理机的任务是由进程调度程序完成的。处理机是计算机最重要的资源，如程序完成的。处理机是计算机最重要的资源，如何提高处理机的利用率，在很大程度上取决于进何提高处理机的利用率，在很大程度上取决于进程调度。进程

30、调度性能的好坏，直接影响操作系程调度。进程调度性能的好坏，直接影响操作系统的性能。统的性能。3.32 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理一、交通控制程序一、交通控制程序交通控制程序是交通控制程序是j.h.saltzerj.h.saltzer于于19661966年起的名字。年起的名字。主要职能是管理进程状态之间的转变和协调进程主要职能是管理进程状态之间的转变和协调进程间的通讯间的通讯大多数的操作系统并未单独设置交通控制程序，大多数的操作系统并未单独设置交通控制程序，而是将其功能分散到各处，以原语或广义指令的而是将其功能分散到各处，以原语或广义指令的面貌出现。面貌出现。3

31、.33 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理二、进程调度程序二、进程调度程序 进程调度的任务是控制协调进程对进程调度的任务是控制协调进程对cpu的竞的竞争即按照一定的调度算法从就绪队列中选中一个争即按照一定的调度算法从就绪队列中选中一个进程，把进程，把cpu的使用权交给被选中的进程。进程的使用权交给被选中的进程。进程调度是通过进程调度程序来完成的。进程调度程调度是通过进程调度程序来完成的。进程调度程序的主要功能可描述如下：序的主要功能可描述如下：1. 记录系统中各进程的执行状况记录系统中各进程的执行状况 为了很好地实现进程调度，进程调度程序首先必为了很好地实现进程调度，

32、进程调度程序首先必须管理系统中各进程的须管理系统中各进程的pcb，将进程的状态变化，将进程的状态变化及资源需求情况及时地记录到及资源需求情况及时地记录到pcb中。通过中。通过pcb变化来准确地掌握系统中所有进程的执行情况和变化来准确地掌握系统中所有进程的执行情况和状态特征。状态特征。3.34 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理2. 选择进程真正占有选择进程真正占有cpu 这是进程调度的实质。即按照系统规定的调度策略这是进程调度的实质。即按照系统规定的调度策略从就绪队列中选择一个进程占有从就绪队列中选择一个进程占有cpu执行。进程调度执行。进程调度依据的算法是与系统的设

33、计目标相一致。对于不同的依据的算法是与系统的设计目标相一致。对于不同的系统，通常采用不同的调度策略。对于批处理系统常系统，通常采用不同的调度策略。对于批处理系统常采用短进程的进程优先，以减少各进程的周转时间。采用短进程的进程优先，以减少各进程的周转时间。对于分时系统，更多地采用时间片轮转。对于分时系统，更多地采用时间片轮转。3. 进行进程上下文的切换进行进程上下文的切换 当进程调度选中一个进程占有当进程调度选中一个进程占有cpu时，进程调度时，进程调度程序要做的主要工作则是进行进程上下文切换：将正程序要做的主要工作则是进行进程上下文切换：将正在执行进程的上下文保留在该进程的在执行进程的上下文保

34、留在该进程的pcb中，以便以中，以便以后该进程恢复执行。将刚选中进程的运行现场恢复起后该进程恢复执行。将刚选中进程的运行现场恢复起来，并将来，并将cpu的控制权交给被选中进程，使其执行。的控制权交给被选中进程，使其执行。3.35 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理三、三、 进程调度方式进程调度方式 (1)非剥夺方式非剥夺方式(non preemptive mode) 在非剥夺方式下在非剥夺方式下, 调度程序一旦把调度程序一旦把cpu分配给某分配给某一进程后便让它一直运行下去一进程后便让它一直运行下去, 直到进程完成或发生直到进程完成或发生某事件而不能运行时，才将某事件

35、而不能运行时，才将cpu分给其它进程。分给其它进程。 这种调度方式通常用在批处理系统中。它的主要这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。优点是简单、系统开销小。 (2)剥夺方式剥夺方式(preemptive mode) 与非剥夺方式不同，这种方式规定，当一个进与非剥夺方式不同，这种方式规定，当一个进程正在执行时，系统可以基于某种策略剥夺程正在执行时，系统可以基于某种策略剥夺cpu给给其它进程。剥夺的情况有：优先级策略和时间片策其它进程。剥夺的情况有：优先级策略和时间片策略。显然这种调度方式通常用在分时系统和实时系略。显然这种调度方式通常用在分时系统和实时系统中，以便及

36、时响应各进程的请求。统中，以便及时响应各进程的请求。3.36 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理四、四、 进程调度的时机进程调度的时机 所谓进程调度的时机，是指什么情况下引起进所谓进程调度的时机，是指什么情况下引起进程调度程序工作。进程调度的时机是与进程调度的程调度程序工作。进程调度的时机是与进程调度的方式有关的。进程调度的时机如下：方式有关的。进程调度的时机如下：1) 正在执行的进程正确完成正在执行的进程正确完成, 或由于某种错误而终止或由于某种错误而终止运行运行(陷阱或中断陷阱或中断) ；2) 执行中的进程提出执行中的进程提出i/o请求请求, 等待等待i/o完成时

37、完成时;3) 在分时系统中在分时系统中, 按照时间片轮转按照时间片轮转, 分给进程的时间分给进程的时间片用完时；片用完时；4) 按照优先级调度时按照优先级调度时, 有更高优先级进程变为就绪时有更高优先级进程变为就绪时(剥夺方式剥夺方式)；5) 在进程通讯中在进程通讯中, 执行中的进程执行了某种原语操作执行中的进程执行了某种原语操作, 如如p操作、阻塞原语和唤醒原语时操作、阻塞原语和唤醒原语时, 都可能引起进都可能引起进程调度。程调度。3.37 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理五、五、 进程控制块的组织方式进程控制块的组织方式pcb表表: 系统把所有系统把所有pcb组

38、织在一起，并把它们放在内组织在一起，并把它们放在内存的固定区域，就构成了存的固定区域，就构成了pcb表表 pcb表的大小决定了系统中最多可同时存在的进程表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度个数，称为系统的并发度（注注: 多道程序中的道数与系统并发度不同）多道程序中的道数与系统并发度不同）pcb表组织方式有两种：表组织方式有两种： 链接方式、索引方式链接方式、索引方式3.38 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理1) 链接方式：链接方式： 对具有相同状态的进程，分别各自链接起来组对具有相同状态的进程，分别各自链接起来组成进程成进程pcb链队列：链

39、队列： 运行队列、就绪队列、阻塞队列、空闲队列运行队列、就绪队列、阻塞队列、空闲队列空闲指针空闲指针运行指针运行指针就绪指针就绪指针等待等待1指针指针等待等待2指针指针pcb1pcb2pcb3pcb4pcb5pcb6pcb7pcbn.6751821153.39 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理2) 索引方式：索引方式： 对具有相同状态的进程，分别设置各自的对具有相同状态的进程，分别设置各自的pcb索引索引表，表明表，表明pcb在在pcb表中的地址表中的地址空闲指针空闲指针运行指针运行指针就绪指针就绪指针等待等待1指针指针等待等待2指针指针pcb1pcb2pcb3pc

40、b4pcb5pcb6pcb7pcbn.3427653.40 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3.41 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理六、进程调度算法六、进程调度算法1.先进先出进程调度算法先进先出进程调度算法(fifo) (先来先服务先来先服务fcfs)按照进程就绪的先后次序来调度进程按照进程就绪的先后次序来调度进程优点优点:实现简单实现简单缺点缺点:没考虑进程的优没考虑进程的优先级先级,也没考虑作业的长短也没考虑作业的长短2.短作业短作业(进程进程)优先调度算法优先调度算法(sjf spf)选择就绪队列中估计运行时间最短的进程投入运行

41、选择就绪队列中估计运行时间最短的进程投入运行优点优点:平均周转时间平均周转时间,带权平均周转时间都改善带权平均周转时间都改善缺点缺点:对长作业非常不利对长作业非常不利不能保证紧迫性进程得到及时处理不能保证紧迫性进程得到及时处理估计运行时间不准确估计运行时间不准确3.42 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理 把把cpu划分成若干时间片划分成若干时间片,并且按顺序赋给就绪并且按顺序赋给就绪队列中的每一个进程，进程轮流占有队列中的每一个进程，进程轮流占有cpu，当时间，当时间片用完时，即使进程未执行完毕，系统也剥夺该进片用完时，即使进程未执行完毕，系统也剥夺该进程的程的cp

42、u，将该进程排在就绪队列末尾。同时系统，将该进程排在就绪队列末尾。同时系统选择另一个进程运行选择另一个进程运行 分时系统中常用时间片轮转法分时系统中常用时间片轮转法时间片选择问题：时间片选择问题： 固定时间片、可变时间片固定时间片、可变时间片(随随)确定时间片大小的因素：确定时间片大小的因素： 系统响应时间、就绪进程个数、系统响应时间、就绪进程个数、cpu能力能力 3.时间片轮转调度算法时间片轮转调度算法(rrround robin)3.43 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理4. 优先权调度算法优先权调度算法(hpfhighest priority first)优先

43、选择就绪队列中优先权最高的进程投入运行优先选择就绪队列中优先权最高的进程投入运行非抢占式优先权算法非抢占式优先权算法:仅在事件发生放弃处理机时仅在事件发生放弃处理机时抢占式优先权算法抢占式优先权算法: 可将正在运行的运行权剥夺可将正在运行的运行权剥夺 优先权的类型优先权的类型静态优先权静态优先权: 在进程创建时指定优先权在进程创建时指定优先权, 在进程运行在进程运行时优先数不变时优先数不变动态优先权动态优先权: 在进程创建时创立一个优先权，但在在进程创建时创立一个优先权，但在其生命周期内优先数可以动态变化。如等待时间长其生命周期内优先数可以动态变化。如等待时间长优先数可改变优先数可改变 确定优

44、先权的依据确定优先权的依据进程类型、对资源的需求、根据用户要求进程类型、对资源的需求、根据用户要求3.44 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理5. 高响应比优先调度算法：高响应比优先调度算法： 改进短作业改进短作业(进程进程)优先调度算法优先调度算法,优先权用下式动优先权用下式动态计算出来态计算出来 优先权优先权= =上式可看出上式可看出 等待时间相同要求服务的时间越短优先权越高等待时间相同要求服务的时间越短优先权越高, 有利于短作业有利于短作业 要求服务时间相同要求服务时间相同,等待时间越长优先权越高等待时间越长优先权越高,近近似于先来先服务似于先来先服务 长作业的

45、优先权会随等待时间加长而升高长作业的优先权会随等待时间加长而升高,长作长作业也会得到执行业也会得到执行等待时间等待时间+要求服务时间要求服务时间 响应时间响应时间 要求服务时间要求服务时间 要求服务时间要求服务时间3.45 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理6.多队列反馈调度算法：多队列反馈调度算法： 系统按优先级设置多级就绪队列第一级优先级最高系统按优先级设置多级就绪队列第一级优先级最高 各就绪队列分配不同的时间片各就绪队列分配不同的时间片,优先级高的第一级优先级高的第一级队列时间片最小队列时间片最小, 随着队列优先级的降低随着队列优先级的降低, 时间片加时间片加大

46、大 各个队列按照先进先出调度算法各个队列按照先进先出调度算法 一个新进程就绪后进入第一级就绪队列一个新进程就绪后进入第一级就绪队列 进程由于等待事件而放弃进程由于等待事件而放弃cpu后后, 进入等待队列进入等待队列, 一一旦等待的事件发生旦等待的事件发生, 则回到原来的就绪队列则回到原来的就绪队列 当有一个优先级更高的进程就绪时当有一个优先级更高的进程就绪时, 可以抢占可以抢占cpu,被抢占进程回到原来一级就绪队列末尾被抢占进程回到原来一级就绪队列末尾 当第一级队列空时当第一级队列空时, 就去调度第二级队列就去调度第二级队列, 如此类推如此类推 时间片用完后进程放弃时间片用完后进程放弃cpu,

47、 进入下一级就绪队列进入下一级就绪队列3.46 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3.6 3.6 进程通讯进程通讯一、进程之间的两种相互制约关系一、进程之间的两种相互制约关系 进程的并发执行虽然提高了资源利用率进程的并发执行虽然提高了资源利用率, 但由于但由于进程的异步性进程的异步性, 会给系统造成混乱。为了使并发执行会给系统造成混乱。为了使并发执行的各进程都能正确执行的各进程都能正确执行, 使它们之间能有效地共享资使它们之间能有效地共享资源和相互合作源和相互合作, 必须研究并发执行的各进程之间的相必须研究并发执行的各进程之间的相互制约关系互制约关系, 采取一定的措施

48、使系统中诸进程有条不采取一定的措施使系统中诸进程有条不紊的紊的同步同步向前推进。进程之间有两种相互制约关系：向前推进。进程之间有两种相互制约关系： 间接相互制约关系间接相互制约关系(资源共享关系资源共享关系) 直接相互制约关系直接相互制约关系(功能合作关系功能合作关系)3.47 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理1) 间接相互制约关系间接相互制约关系(资源共享关系、互斥关系资源共享关系、互斥关系) 由于共享资源由于共享资源, 使得系统中本来没有逻辑关系的进使得系统中本来没有逻辑关系的进程程, 因相互竞争资源而产生了制约关系。因相互竞争资源而产生了制约关系。 例如例如:

49、 进程进程 p1和和p2在运行中都要使用打印机在运行中都要使用打印机, 为了为了保证各进程输出的完整保证各进程输出的完整, 打印机必须互斥访问打印机必须互斥访问 (独占使独占使用用)。即一个进程使用完后。即一个进程使用完后, 另一进程才能使用。这样另一进程才能使用。这样,一旦系统将打印机分配给进程一旦系统将打印机分配给进程 p1, 进程进程p2就必须等待就必须等待, 直到直到p1用完打印机并释放后用完打印机并释放后, p2才能使用。才能使用。 这种因共享资源而使并发执行的各进程之间产生这种因共享资源而使并发执行的各进程之间产生的关系的关系, 叫做叫做间接制约关系间接制约关系, 又叫做又叫做互斥

50、关系互斥关系。这种关。这种关系可以用系可以用“进程进程-资源资源-进程进程”来描述。来描述。 进程的互斥进程的互斥(mutual exclusion) 3.48 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理2)直接制约关系直接制约关系(相互功能合作关系、同步关系相互功能合作关系、同步关系) 通常通常, 一个用户作业要涉及一组并发进程一个用户作业要涉及一组并发进程(输入、输入、计算和输出进程计算和输出进程), 这些进程必须这些进程必须相互协作共同完成相互协作共同完成这项任务。这项任务。 具体说具体说, 在运行过程中在运行过程中, 某进程可能要在某些同某进程可能要在某些同步点上等待

51、另一伙伴步点上等待另一伙伴(协作进程协作进程)为它提供消息为它提供消息, 在未在未获得消息之前获得消息之前, 该进程处于等待状态该进程处于等待状态, 获得消息后被获得消息后被唤醒进入就绪态唤醒进入就绪态, 此后此后, 才能继续运行。进程之间的才能继续运行。进程之间的这种制约关系叫做这种制约关系叫做直接制约关系直接制约关系,又叫又叫同步关系同步关系。这。这种关系可用种关系可用“进程进程-进程进程”来描述。来描述。 3.49 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理进程的同步进程的同步( (synchronism)例例: 司机司机 p1 售票员售票员 p2repeat repe

52、at 启动启动 关门关门 正常行驶正常行驶 售票售票 到站停到站停 开门开门until false until false3.50 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3 3） 临界资源和临界区临界资源和临界区 进程的互斥是由于共享资源而引起的进程的互斥是由于共享资源而引起的, 为了描述为了描述这类情况这类情况, 我们引入临界资源和临界区的概念。我们引入临界资源和临界区的概念。临界资源临界资源(互斥资源互斥资源)：critical resource 系统中一次只允许一个进程访问的资源。这些系统中一次只允许一个进程访问的资源。这些资源既包括资源既包括i/o设备设备, 如打

53、印机等资源如打印机等资源, 也包括软件资也包括软件资源源, 如共享变量、共享文件等。如共享变量、共享文件等。临界区临界区(互斥区互斥区): critical section 并发执行的进程并发执行的进程中中, 访问临界资源的必须互斥执访问临界资源的必须互斥执行的程序段行的程序段叫叫临界区。临界区。 临界区临界区分散在每个要分散在每个要并发执行的并发执行的进程中进程中, 它们都它们都对某个共享的数据结构对某个共享的数据结构(共享资源共享资源)进行访问。进行访问。3.51 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理 变量变量a是临界资源是临界资源 c1、c2、c3是临界区是临界区

54、 对对a应互斥访问应互斥访问p1 :p2 :p3 :c3 )c1 )c2 )a := a +1 print (a)a := a +1 print (a)if a 0then a := a +1else a:= a-13.52 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理共共 享享 变量变量临界区临界区2 2临界区临界区n n临界区临界区2 23.53 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理二、实现临界区互斥的锁操作法二、实现临界区互斥的锁操作法为禁止两个进程同时进入临界区，必须有一相为禁止两个进程同时进入临界区，必须有一相应机构来协调它们，且遵循下述原则：

55、应机构来协调它们，且遵循下述原则：当有若干进程要求进入它们的临界区时，应在有限时间内使一个进程进入临界区。每次最多有一个进程处于临界区内。进程在临界区内逗留应在有限时间范围内。3.54 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理用锁操作原语实现互斥用锁操作原语实现互斥关锁执行临界区程序开锁锁有两种状态：w=0表示锁已打开；w=1表示锁被关闭。加锁原语用lock(w)表示；开锁原语用unlock(w)表示。lock(w)原语 l:if w=1 then go to l else w:=1;unlock(w)原语 w:=0;3.55 计算机操作系统计算机操作系统 第三章第三章 进

56、程管理进程管理例：两个进程例：两个进程p1p1，p2p2使用如下程序实施进程的互斥：使用如下程序实施进程的互斥： 进程进程p1 p1 进程进程p2p2 lock(w) lock(w) s1 s2 unlock(w) unlock(w) s1s1和和s2s2分别为进程分别为进程p1p1和和p2p2的临界区。的临界区。特点：用加锁和开锁的方法实现临界区互斥，其效特点：用加锁和开锁的方法实现临界区互斥，其效率很低。率很低。因为只要一个进程进入临界区后，其他企图进入临界区的进程，在执行lock(w)时，因不断测试w造成处理机时间的浪费。3.56 计算机操作系统计算机操作系统 第三章第三章 进程管理进程

57、管理三、信号量和三、信号量和p p、v v操作操作管理和控制铁路交通的重要工具是信号灯。利用管理和控制铁路交通的重要工具是信号灯。利用信号灯的状态信号灯的状态(颜色颜色)控制火车的正常通行。单段铁控制火车的正常通行。单段铁路任何时刻只允许一列火车通行路任何时刻只允许一列火车通行(相当于临界区相当于临界区)，遇到红灯遇到红灯(表示区内有火车表示区内有火车)应等待，变为绿灯时可应等待，变为绿灯时可进入行驶进入行驶(同时红灯亮禁止其它火车进入同时红灯亮禁止其它火车进入)，火车驶，火车驶出临界区绿灯亮允许火车进入。同样出临界区绿灯亮允许火车进入。同样, 为了管理为了管理各并发进程对共享资源的使用各并发

58、进程对共享资源的使用, 引入了信号灯引入了信号灯(信信号量号量)的概念的概念; 将信号量定义为一个将信号量定义为一个整型量整型量 s; s0表示资源可用表示资源可用(无进程在临界区相无进程在临界区相当于绿灯亮当于绿灯亮)。某进程企图进入区时。某进程企图进入区时, s0可以进入。信号量可以进入。信号量 s 只能通过两个标准原只能通过两个标准原子操作子操作(不可中断不可中断) p-v操作来访问。操作来访问。3.57 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理根据用途不同，分为公用信号量公用信号量和私用信私用信号量。号量。公用信号量公用信号量通常用于实现进程之间的互斥，初值为1私用

59、信号量私用信号量通常用于实现进程间的同步，初值为0或为某个正整数n3.58 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理p、v操作原语p p操作原语的定义：操作原语的定义：p（s）：顺序执行下述两个动作：1.信号量的值减1，即s=s-1；2.如果s 0，则该进程继续执行；3.如果s0，则把该进程的状态设置为阻塞态，把它相应的pcb放入相应队列中，并放弃处理机，进行等待（直至其它进程在s上执行v操作，把它释放出来为止） procedure p(var s:semaphore) begin s:=s-1; if s=0，表示资源够用； 等于0表示正好够用； 小于0表示资源不够用，s

60、的绝对值表示等待使用资源的进程个数3、p操作起到了限制一次只有一个进程进入临界区的作用3.60 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理v v操作原语的定义：操作原语的定义：v（s）顺序执行下述两个动作：1.s值加1，即s=s+12.如果s0，则该进程继续运行；3.如果s 0，则唤醒等待信号量s阻塞队列中的头一个进程（把阻塞态改为就绪态），执行v操作的进程继续运行。 procedure v(var s:semaphore) begin s:=s+1; if s=0 then r(s) end;3.61 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理特点：特点：