第3课-进程调度.ppt

本课内容 2.3 进程的调度与管理 2.4 作业调度 复习: 1.进程概念 2.进程的组成内容 3.进程控制块内容 4.进程的状态与转换(三态模型/五态模型) 5.相关英文专业术语: 进程 进程控制块 描述进程状态: 运行态 就绪态 阻塞/等待态 2.3 进程的调度与管理 2.3.1 进程调度算法 当系统中有多个进程就绪时，必须决定先执行哪一个,决定把CPU分配给谁使用。操作系统中做出这一决定的程序称为“进程调度程序”，该程序中采用的调度方法，称为进程调度算法。 2.3.1 进程调度算法 1．先来先服务调度算法 先来先服务调度算法的基本思想是：以到达就绪队列的先后次序为标准来选择占用处理机的进程。 先来先服务算法的特点: 一个进程一旦占有处理机，就一直使用下去，直至正常结束或因等待某事件的发生而让出处理机。 例2-1: 设就绪队列中的三个进程所需运行时间如下, 进程A 24 ms 进程B 3ms 进程C 3ms 若进程调度顺序为 A B C , 则平均等待时间为: 若进程调度顺序为 B A C , 则平均等待时间为: 时间片轮转调度算法的基本思想是：为就绪队列中的每一个进程分配一个称为“时间片”的时间段，它是允许该进程运行的时间长度。 在使用完一个时间片后，即使进程还没有运行完毕，也要强迫其释放处理机，让给另一个进程使用。它自己则返回到就绪队列末尾，排队等待下一次调度的到来。 时间片轮转调度算法经常用在分时操作系统中，在时间片轮转调度算法中，时间片大小的设定是一个影响系统效率发挥的重要因素。 例2-2 假定有一个分时系统，允许10个终端用户同时工作，时间片设定为100ms。若对用户的每一个请求，CPU将耗费300ms的时间进行处理才能做出回答,试问终端用户提出两次请求的时间间隔最少是多少才能及时响应？ 3．优先数调度算法 优先数调度算法的基本思想是：为系统中的每个进程规定一个优先数，就绪队列中具有最高优先数的进程有优先获得处理机的权利。即队列按进程的优先数大小进行排队. 如果几个进程的优先数相同，则对它们实行先来先服务的调度。 新到达就绪队列的进程将按其优先数插入到就绪队列中. 确定进程的优先数（也就是进程的优先级）可以从如下几个方面考虑: 4．多级队列调度算法 多级队列调度算法也称多级反馈队列调度算法，它是时间片调度算法与优先数调度算法的结合。 实行这种调度算法时，系统中将维持多个就绪队列，每个就绪队列具有不同的调度级别，可以获得不同长度的时间片. 一般的,优先级高的队列分配小的时间片,而优先级低的进程分配大的时间片. 多级队列具体调度算法: 1.创建新进程时,其PCB进入1级(高)就绪队列末尾; 2.对于优先数为1~n-1 运行态的进程: 如果在分配给它的时间片内完成了全部工作,则撤消该进程; 如果用完时间片仍未完成工作,则该进程进入低一级的就绪队列对； 如果因输入/输出或等待某事件进入阻塞状态,则事件满足时进程仍回原来的就绪队列; 3.对于最低一级(n)的进程,实行时间片轮转调度 4.进程调度时由1级开始,只有当高优先级就绪队列为空时,才去调度低一级的队列中的进程. 小结: 常用的四个进程调度算法: 1.先来先服务 2.时间片轮转 3.优先数调度算法 4.多级队列调度算法 例2-3 如图2-11所示，通过进程状态变迁图描述了一个进程调度算法。试分析该图，说明该调度算法的基本思想。 应该具有以下几个方面的主要功能: （1）记录系统中所有进程的有关情况，比如进程的当前状态，优先数等。 （2）确定分配处理机的算法，这是它的一项主要工作。 （3）完成处理机的分配。要注意，在操作系统中，是进程调度程序实施处理机的具体分配的。 （4）完成处理机的回收。 可以看出，进程调度程序负责具体的处理机分配，完成进程间的切换工作，因此它的执行频率是相当高的，是一个操作系统的真正核心。 通常，在发生下述情况时，会引起进程调度程序的工作: （1）一个进程从运行状态变成了阻塞状态（如请求进行输入/输出操作）。 （2）一个进程从运行状态变成了就绪状态（如在分时系统中，已经运行满一个时间片）。 （3）一个进程从阻塞状态变成了就绪状态（如等待的输入/输出操作完成）。 （4）一个进程正常运行结束后被撤销。 把处理机分配给进程后，还有一个允许它占用多长时间的问题，具体有两种处理方式，一种是不可剥夺（或不可抢占）方式，另一种是剥夺（或抢占）方式。 所谓不可剥夺方