计算机操作系统许曰滨版第三章.ppt

1,第3章 进程管理,2,本章主要内容,进程管理的基本概念 进程控制块 进程控制 进程调度 实时系统的进程调度 线程（Thread） 关于调度讨论,3,要点之一,操作系统为什么要引进“进程”？ 到底什么是进程？ 进程有哪些特征？ 进程与程序、作业的关联与区别？ 进程管理模块要实现哪些功能？,4,3.1 进程管理的基本概念 3.1.1 程序的运行方式,顺序运行 顺序运行方式是一种最容易实现的方式，常见于早期的单道批处理系统中。这种方式具有以下基本特征： l 顺序特征。 l 独占特征。 l 确定性特征 l 可重现性特征,5,2. 并发运行 并发运行是多道程序系统中的一种运行方式。它允许多个程序共享CPU，以并发方式进行运算。在这种方式下，系统的资源不再被某一个程序独占，而是由多个程序共享。 多道程序并发运行: 指的是内存中同时活跃着多个用户进程，它们以CPU共享方式投入运行。,6,并发运行方式的基本特征,异步特征 资源共享特征 相互制约特征 不可重现性特征,7,3.1.2 进程概念,进程：是程序的运行过程，是可以独立申请并获 得系统资源，能够与其他进程并发运行的基本单位。 进程具有以下5个特征： （1）动态特征 （2）并发特征 （3）独立特征 （4）异步特征 （5）结构特征,8,3.1.3 进程管理的主要功能,进程管理，是操作系统中最重要的组成部分，它的功能可大体分为两个方面：进程控制和进程调度。 1. 进程控制 创建新进程，撤消已结束的进程。 阻塞或唤醒一个进程，挂起或激活一个进程。 进程同步与通信控制。 2. 进程调度 根据进程当前状态决定哪个进程获得CPU，以及 占用多长时间。 将CPU分给进程。,9,一般用户如何感知到进程？ 举例：,10,/ex1.c #include #include #include int main() int pid; pid=fork(); printf(“Hellon“); ,11,要点之二,操作系统如何管理进程？ PCB、进程状态、状态转换 进程管理模块如何实现管理功能？ 进程控制原语 进程调度 进程的同步与互斥（第四章）,12,进程控制块,一个进程在其生命周期中，需要经历多个发展阶段。每个阶段进程的推进位置、资源占有情况都在发生不断变化。为了描述不断变化的进程，系统引入一种与进程相联系的数据结构进程控制块PCB。 进程控制块PCB的内容包括以下4部分： 进程标识 调度信息 处理机信息 进程控制信息,13,1进程标识 进程标识是系统识别进程的标志。不同进程，其标识也不同。进程标识可分为外部标识和内部标识两部分。其中，外部标识（也称作进程的外部名），是进程的创建者提供的进程名字，通常由字符串组成。内部标识（也称作进程的内部名，简记为Pid）是系统为进程命名的一个代码，通常是一个整型数。,14,2调度信息 （1）进程优先数，描述进程紧迫性的信息。 （2）进程状态信息，描述进程当前处于何种状态。 （3）其它调度信息。这部分信息有：进程在系统中等待的时间有多久，已在CPU上运行的时间是多少，剩余的运行时间有多少等。这些信息可帮助系统选择一个最迫切、最具运行条件的进程投入运行。,15,3. 处理机信息 当一个进程运行过程中发生某些事件，使该进程运行不下去时，系统将剥夺它的CPU，交给别的进程使用。则，该进程的CPU现场信息可以保存在它自己的PCB内，以便该进程重新获得CPU时可以从此处恢复现场信息，继续运行。 （1）通用寄存器的内容：包括数据寄存器、段寄存器等。 （2）程序状态字PSW（Program Status Word）及程序计数器PC（Program Count）值。 （3）进程的堆栈指针。,16,4.进程控制信息 这部分内容是系统对进程实施控制的依据，主要包括程序代码及数据集的相关说明： （1）程序代码和数据集所在的内存地址。 （2）资源清单，记载进程请求资源的情况和已经占有资源的情况。 （3）同步与通信信息。 （4）外存地址。 （5）家族信息。 （6）链接指针。,17,如Linux中PCB类型定义 struct task_struct unsigned short uid; int pid; int processor; volatile long state; long priority; unsigned long rt_priority; long counter; unsigned long flags; unsigned long policy; struct task_struct *next_task, *prev_task ; struct task_struct *next_run, *prev_run ; struct task_struct *p_opptr, *p_pptr, *p_cptr, *p_ysptr, *p_ptr ; ;,18,3.2.2 进程基本状态及状态变迁,一、进程的3种基本状态 就绪（Ready）状态 这是进程尚未获得CPU使用权的一种状态。在这一状态下，进程已经拥有除CPU外其它全部所需资源，因此该状态是一种“备运行”状态。 运行（Running）状态 这是进程获得CPU并投入运行的一种状态。事实上，在通常的单CPU系统中，每个瞬间最多只能有一个进程在运行。 阻塞状态（Blocked Status） 这也是进程尚未获得CPU使用权的一种状态。在这一状态下，进程因某种要求得不到满足，只好等待，我们称之为运行“受阻”。处于阻塞状态的进程是无权获得CPU的。,19,进程的三种基本状态,20,（1）后备就绪 当作业调度程序选中一个作业时，该作业就由外存装入内存，并被创建为进程。在大多数系统中，进程创建后的第1个状态是就绪状态。此刻进程已拥有所需的全部资源，只要获得CPU就可以运行。 （2）就绪运行 当进程调度程序按照某种算法，选中一个处于就绪状态的进程时，该进程就获得了CPU使用权，进程状态由“就绪”改为“运行”。,21,(3) 运行阻塞 一个正在运行的进程，因需要系统的某种支持，比如，等待输入输出或者等待系统的资源，那么该进程已无法继续运行下去，只好主动放弃CPU，将自己阻塞起来等待所需的事件发生。 (4) 运行就绪 在一个按时间片进行轮转调度的系统中，当正在运行的进程使用完自己的时间片时，系统将中断该进程的运行，使它由“运行”状态转为“就绪”状态。显然，该进程已充分用完自己的时间片，剩余的运行只好等到下一个调度周期到来。在一个可抢占式调度系统中，如果有一个更高优先级的进程到来，系统将剥夺当前进程的CPU，交给更高优先级进程运行。当前进程只好由运行状态转为阻塞状态。,22,(5) 阻塞就绪 当一个阻塞的进程遇到自己等待的事件发生，该进程便具有了运行的条件，进程控制模块将它由“阻塞”状态转为“就绪”状态。等待的事件包括：请求的资源已获得；等待的I/O操作已完成；其它进程发来“唤醒”消息，及其它一些原因。 (6) 运行完成 当正在运行的进程已经运行完自己的程序后，管理程序将收回它所占用的资源。比如，通过调用“存储管理模块”回收它所占用的内存空间，调用“设备管理模块”回收它所占用的外部设备。若当前进程的状态转为“完成”后，系统需要将CPU重新分配给他人使用。,23,3.2.3 扩展状态,挂起 将内存中当前某个尚不能运行的进程调到外存上去，腾出来的空间接纳更多的进程。这一处理称作进程“挂起”（Suspend）。 挂起状态 挂起阻塞（S-Blocked）状态 挂起就绪（S-Ready）状态,24,为什么要引入挂起状态？,举一个例子。 若系统的内存用户区有20M空间，收到的作业平均长度500K。每时刻可容纳的作业数量最多为40个。若每个作业平均执行104条指令将产生一次I/O，相当于每次使用CPU运行0.1ms就需要等待20ms的I/O时间。因此，CPU的利用率p可粗略地估算为： 可以看出，处理机有近80%的时间是闲置的。,25,加入挂起状态的进程状态转换图,26,Linux2.4版本中进程的6种状态,27,PCB队列结构,28,3.3 进程控制,进程从产生到消亡的整个过程中都是由操作系统来控制的。操作系统中的一些功能程序来实现进程控制的使命。通常，这些离散的小程序块处于操作系统的底层，运行时不允许中断。我们习惯上称它们为“原语”。,29,原语（Primitive），是用机器指令构成的一种实现特定功能的小程序，它的运行具有不可分割性。 l 进程控制用的原语。这是一类实现进程管理和状态切换的原语，如，进程创建原语、进程撤消原语、阻塞原语、唤醒原语、进程挂起原语、进程激活原语、进程调度原语等。 l 进程通信用的原语。这类原语是用于实现进程之间通信的，如，消息发送原语、消息接收原语等。 l 资源互斥与同步用的原语。系统中的许多资源一次只能供一个进程使用，为了达到资源互斥访问的目的，系统需要设一组解决此类问题的原语。其中主要有P操作原语和V操作原语。 l 资源管理用的原语。主要有请求资源的原语和释放资源的原语。,30,下面讨论各个控制进程状态装换的原语 （1）何时执行？ （2）如何执行？,31,3.3.1 进程创建与撤消原语,进程创建原语 何时？有以下4种事件会导致创建原语运行 ： 批作业调度。批处理系统中，当系统准备增加新进程时，一个处于磁盘上的后备作业有可能被作业调度程序选中，将它创建为进程 交互作业提交。在分时系统中，一个终端用户登录到系统。操作系统将创建一个与该终端相关联的终端进程。 系统提供服务。操作系统创建一些为用户服务的进程，比如I/O进程。这类进程的优先级要高于一般应用进程。 用户需求创建子进程。现有进程根据运行需要创建一些子进程，使系统中形成了父子进程并发运行的格局。,32,如何？进程创建原语Create_Process（）： (1) 索取一个空白PCB块。 (2) 填入进程信息： (2)-1 填入进程标识。 (2)-2 PCB（优先级）赋予优先级或将JCB（优先级）填入。 (2)-3 PCB（内存地址）请求分配内存或JCB（内存地址）或父进程的内存地址填入。 (2)-4 PCB（资源清单）请求分配设备或JCB（资源清单）或父进程资源填入。 (2)-5 PCB（家族信息）用户名或父进程名。 (2)-6 PCB（现场信息）初始状态数据。 (2)-7 PCB（进程状态）“就绪”。 (3) 挂入就绪队列。 (4) 若需要将程序代码和数据集装入内存，可启动加载程序。,33,2. 进程撤销原语 何时？进程撤销是进程创建的反过程。通常，有下列事件会导致进程撤消。 （1）进程自行终止。 （2）用户或父进程的原因使进程终止。 （3）运行超时而终止 （4）运行出错而终止。,34,如何？进程终止原语Destroy（id_name）： （1） 根据id_name查找被终止进程的进程控制块PCB。 (2) 若该进程的状态是“运行”，则置调度标志 为TRUE。 (3) 回收PCB（资源清单）中登记的全部资源。 (4) 将进程的PCB从所在队列摘下来，等待其它程 序来搜集信息。 （5）对于该进程的所有子进程Sub，递归调用 End_Process（Sub），将子进程终止。 (6) 如果调度标志=TRUE，启动进程调度程序。,35,3.3.2 阻塞与唤醒原语 1. 进程阻塞原语 何时？ 当处于运行状态的进程需要等待某一事件时，由于运行受阻无法继续下去，该进程需要通过中断服务请求进入系统。系统按照进程的需求进行适当处理后，启动“进程阻塞原语”将该进程阻塞起来。 引起进程阻塞（也就是运行受阻）的原因： 等待I/O 请求资源得不到满足 进程同步约束 服务进程无服务任务,36,如何？ 阻塞原语Block（）可以描述为下述过程： j := GetInternalname()； Remove(RunQueue, j)； /从运行队列上摘下j j (进程上下文) := CPU现场信息； j (状态) := “Blocked”； Insert(BlockQueue, j)； /将j插入阻塞队列上 Scheduler()； /运行调度程序 结束,37,2进程唤醒原语,何时？当系统发生某一个事件时，正在等待该事件的进程需要立即被唤醒，由“阻塞”状态转为“就绪”状态。 引起进程唤醒的原因源自进程的阻塞原因有： 所等的I/O操作已完成。 请求的资源得到了满足。 进程同步约束已撤消。 服务进程收到新的任务。,38,如何？唤醒原语Wake_up（）的功能过程： (1) 将当前进程的上下文保存到系统栈中。 (2) 从阻塞队列上查找等待该事件的进程PCB。 (3) 将PCB从阻塞队列上摘下来。 (4) 将其状态置为“就绪”。 (5) 将PCB挂入就绪队列。 (6) 弹出系统栈中的进程上下文，置入CPU，让被中断的进程恢复运行。 (7) 结束。,39,3.3.3 挂起与激活原语,1. 挂起原语 何时？挂起的原因主要有： 虚拟存储管理方式中，当前进程的内存空间太少 根据操作系统的需要，将部分进程挂起，以便改善运行性能 应用户的要求，将用户进程挂起 应父进程要求，将其子进程挂起,40,如何？挂起原语Suspend（）的功能过程： (1) 找到被挂起进程的PCB。 (2) 将PCB从所在队列上摘下来。 (3) 从中获得其内存空间地址,将内存空间归还给存储管理模块。 (4) 若进程状态为阻塞，则将PCB状态置为“挂起阻塞”，插入“挂起阻塞队列”；若进程为就绪，则将进程状态置为“挂起就绪”，插入“挂起就绪队列”。 (5) 申请外存交换区空间，将进程写到交换区上。并将交换区地址写入PCB。 (6) 结束。,41,二、激活原语,何时？当内存空间宽裕时，为了保证处理机将部分被挂起的进程激活。激活原因主要有： 当一个进程运行完毕，若当前内存空间并不紧张，需要增加进程数量 应用户要求，将其进程激活 应父进程的要求，将将其子进程激活；或者进程自身设定的挂起周期已完成,42,如何？激活原语Active（）可以描述为下述过程： (1) 扫描“挂起就绪队列”找到被激活进程的PCB。 (2) 将PCB从所在队列上摘下来。 (3) 按PCB登记的空间需求，申请内存。 (4) 将该进程加载到内存中。 (5) 归还外存交换区空间。 (6) 若进程状态为“挂起就绪”，则置为“就绪”，插入就绪队列；否则，置为“阻塞”，插入阻塞队列。 (7) 结束。,43,/ex1.c #include #include #include int main() int pid; pid=fork(); printf(“Hellon“); if(pid=0) printf(“I am childn“); else printf(“I am parentn”); ,44,3.5 进程调度 3.1.1 进程调度分类,从调度方式上看，进程调度有两种类型：一种是非抢占式调度，另一种是抢占式调度。 非抢占调度 可能引起当前进程主动放弃处理机控制权的情况有两个: l 进程运行完毕退出或遇到不可挽回的故障。 l 运行受阻。,45,非抢占式调度运行示例,46,2. 抢占调度,抢占调度也称作剥夺调度，主要指的是，在系统正常运转期间，如果某种事件出现，系统将迫使正在运行的进程停下来，将CPU控制权交给其它进程。 抢占调度的思想源自对高紧迫度作业的响应。当一个紧迫性较高的进程到来，要求在限定的时间内做出响应，管理程序应及时停止正在运行的程序。将控制权交给紧迫性较高的进程。,47,抢占式调度运行示例,表3-1 4个进程的创建数据,48,3. 进程调度算法,l FCFS算法，先进入就绪队列的进程先调度。 l SPF（Shortest Process First）算法，最短进程优先调度。 l HPF（Highest Process First）算法，最高优先级调度。 l HRF（Highest Response First）算法，最高响应比优先调度。 l RR（Round Robin）算法，轮转调度。 l 多队列调度算法。 l 多级反馈队列调度算法。 l 最短剩余时间（SRT,Shortest Remain Time）优先算法。,49,RR算法,这是一种按时间片进行轮转调度的算法。当正在运行的进程用完自己的时间片后，管理程序停止它的运行，并将它转入就绪队列尾部，然后重新分配CPU。在这种情况下，进程失去CPU不是自愿的，而是被剥夺的。 轮转算法的启动时机： 一个时间片运行结束; 当前进程运行结束; 或者正在运行的进程因运行受阻主动放弃了CPU控制权。,50,RR算法,51,时间片的选取,时间片的确定通常有下面几个原则： （1） 进程的道数较多时，q就选得小一些；反之，可选得大些。 （2） 系统要求的响应时间比较苛刻的时候，q就选得小一些；反之，可选得大些。 （3） 计算机的运算速度较慢的时候，q就选得小一些；反之，可选得大些。,52,多就绪队列组织形式,53,多级反馈队列调度,54,多级反馈队列调度,1）设置n个队列Q1，Q2， Qn。 2）记Qi的优先级为Pi，有P1P2 Pn。 3）记Qi的优先级为qi，有q1q2 qn。 4）新建进程进入Q1队。 5）只有Qi为空时，才调度Qi+1中的进程。 6）进程 p在Qi中被调度执行，若时间片qi已到但尚未结束，则进程p转为就绪状态进入Qi+1队；进程 p在Qn中被调度执行，若时间片已到但尚未结束，则进程转为就绪状态仍入Qn队。,55,终端型用户满意。系统收到的终端型作业都是交互型的，通常比较小。当作业进入第1队列后，如果系统为第1队列规定的时间片比较合理，一般只要一个时间片就可完成。因而，会得到这部分终端用户的认可。 短的批处理作业用户满意。对于短的批处理作业来说，开始时与终端作业一样首先进入第1个队列，得到与终端作业相同的响应时间。若轮转一周不能完成的话，通常只需在第2乃至第3队列上各执行一个时间片就可能完成，作业的周转时间仍比较短。因而，持有短的批处理作业的用户对系统的处理也是可以接受的。 长的批处理作业用户满意。一个长批处理作业进入系统后，将依此在第1，2，n-1队列中各运行一个时间片，最后进入第n队列进行轮转运行，一般不必担心“受冷落”现象发生。,56,3.5 实时系统的进程调度,实时任务是一类对时间要求较为严格的任务，支持这类任务运行的系统称为实时处理系统。当此类任务到达系统后，系统应当按照任务的时间要求及时调度它。 实时系统中的调度方式一般是剥夺式的。,57,3.5.1 实时任务的分类及其调度方法,紧迫型实时任务调度 普通型的实时任务调度 宽松型的实时任务调度 非抢占的HPF调度算法 RR算法,58,紧迫型实时任务调度,紧迫性强的任务多见于一些专用的、响应时间要求特别苛刻的数据采集和控制系统中，所要求的响应时间很短，一般是微秒量级的。解决的方法就是，采用“立即抢占的HPF”调度算法。,普通型的实时任务调度,目前，大多数自动控制系统对响应时间的要求都不是太高，一般是毫秒量级的。由于它允许的响应时间长度与时钟中断的周期基本吻合，所以可采用 “基于时钟中断抢占的高优先级调度”算法。,59,60,宽松型的实时任务调度,宽松型实时任务要求的响应时间比较长，一般可达数百毫秒，甚至数秒钟。比如信息查询系统就属于此类任务。由于这类任务的要求差异很大，通常又有很多不同的处理。常见的算法有： （1）非抢占的HPF调度算法 （2）RR算法 此类任务既可以进入批处理系统按上面说的高优先级算法进行调度，也可以作为交互型的任务，通过终端提交给系统。按时间片实行RR调度,61,3.5.2 周期性任务调度,在一些信号检测和过程控制系统中，有许多任务呈现周期性的运行规律。比如，气象信息检测中每隔2小时要读取一次数据，我们将这类任务称为周期性任务。 一个周期任务A第i次运行前的剩余时间FA（i）的计算公式是： 式中，TA为任务A的周期长度；TSA为任务A的每次执行时间长度；t为系统的当前时间。 FA（i）越小，说明任务的截止时间离当前时间越近，就越迫切。系统可以按照最小FA（i）者优先原则进行调度，相应的算法称为SRT（最小剩余时间）调度算法。,62,下面来看一个例子。周期任务A的周期长度为50ms，执行时间为10ms/次，松弛时间为40ms。任务B的周期长度为80ms，执行时间为20ms/次，松弛时间为60ms。,63,两个周期任务的调度结果,64,周期任务的调度定理,对于单机系统中接收的n（n0）个周期任务，每个任务的周期长度为Ti，执行时间为Tsi。只有当下式成立时，系统有望实现调度： 该定理明，在只有1台处理机的系统中，所有任务的运行时间与滞留时间之比的总和不能大于等于1。推而广之，在包含N台处理机的系统中，所有任务的这种比例之和不能大于等于N。,65,3.6 线程（Thread）,3.1.1 为什么引入线程 在现代操作系统中，进程是一种庞大的结构型实体。其PCB结构包含的内容相当多。每当创建一个进程，系统无论在时间上或空间上都要花费较大开支。在管理和维护这些进程时，系统花费也不可忽视。另外，从运行角度看，当父进程将其子进程唤醒后，希望其子进程能立即运行，以