第2章处理机管理-3

上页下页退出第2章处理机管理第2章处理机管理-3【学习目标掌握：处理机的调度算法、进程调度【学习重点、难点进程的调度与管理1、掌握原语的概念。2、掌握进程调度算法的基本思想。上页下页退出第2章处理机管理2．3进程的调度与管理2．3．1进程调度算法常用的进程调度算法有：先来先服务、时间片轮转、优先数多级队列上页下页退出第2章处理机管理1．先来先服务调度算法先来先服务调度算法的基本思想是：以到达就绪队列的先后次序为标准来选择占用处理机的进程。一个进程一旦占有处理机，就一直使用下去，直至正常结束或因等待某事件的发生而让出处理机。就绪队列：到达的进程的PCB总是排在就绪队列末尾；调度程序总是把CPU分配给就绪队列中的第一个进程使用。上页下页退出第2章处理机管理就绪队列上页下页退出第2章处理机管理先来先服务调度算法的示意图。上页下页退出第2章处理机管理先来先服务可能是最为简单的一种调度算法。从次序的角度看，它对在就绪队列中的任何进程不偏不倚，因此是公平的。但从周转的角度看，对要求CPU时间短的进程或I/O请求频繁的进程来讲，就显得不公平了。例如，现在就绪队列中依次来了3个进程A、B、C，A进程需要运行24ms，B和C各需要运行3ms。假定换一种调度顺序，比如是B、C、A，那么3个的平均等待时间多少。按照先来先服务的顺序，进程A、B、C。计算它们3个的平均等待时间是多少。上页下页退出第2章处理机管理按照先来先服务的顺序，进程A、B、C。于是B要在24ms后才能得到运行，C要在27ms后才能得到运行，显然B和C等待的时间太长。按照这种调度顺序，它们H个的平均等待时间是：（0＋24＋27）/3＝17ms。ABC2427300上页下页退出第2章处理机管理假定换一种调度顺序，比如是B、C、A，那么3个的平均等待时间是：（0＋3＋6）／3＝3ms。ABC36300上页下页退出第2章处理机管理2．时间片轮转调度算法基本思想是：为就绪队列中的每一个进程分配一个称为“时间片”的时间段。在使用完一个时间片后，即使进程还没有运行完毕，也要强迫其释放处理机，让给另一个进程使用。它自己则返回到就绪队列末尾，排队等待下一次调度的到来。采用这种调度算法时，对就绪队列的管理与先来先服务完全相同。主要区别是进程每次占用处理机的时间由时间片决定。上页下页退出第2章处理机管理图2－9是时间片轮转调度算法的示意图。上页下页退出第2章处理机管理时间片轮转调度算法经常用在分时操作系统中用户通过终端设备与计算机系统进行交互会话。时间片大小的设定是一个影响系统效率发挥的重要因素：时间片如果设定得太大，大到一个进程足以完成其全部工作所需要的时间，则该算法就退化为先来先服务；若时间片设定得太小，则调度程序的执行频率上升，系统耗费在调度上的时间增加，用于运行用户程序的时间就减少了。粗略地看，时间片值应略大于大多数分时用户的询问时间。即当一个交互式终端在工作时，给每个进程的时间片情应能使它足以产生一个输入／输出要求为最好。上页下页退出第2章处理机管理例2.2有一个分时系统，允许10个终端用户同时工作，时间片设定为100ms。若对用户的每一个请求，CPU将耗费300ms的时间进行处理，做出回答。试问终端用户提出两次请求的时间间隔最少是多少？一解：因为时间片长度是100ms，有10个终端用户同时工作，所以轮流一次需要花费1s。这就是说在1S内，一个用户可以获得100ms的CPU时间。又因为对终端用户的每一次请求，CPU都要耗费300ms进行处理后才能做出应答，于是终端用户要获得3个时间片，才能得到系统做出的回应。所以，终端用户两次请求的时间间隔最少应为3S，在此期间内提出的情求，系统就无暇顾及，不可能予以处理。上页下页退出第2章处理机管理3．优先数调度算法优先数调度算法的基本思想是：为系统中的每个进程规定一个优先数，就绪队列中具有最高优先数的进程有优先获得处理机的权利；如果几个进程的优先数相同，则对它们实行先来先服务的调度。采用这种调度算法时，就绪队列应该按照过程的优先数大小来排列。新到达就绪队列进程的PCB，应该根据它的优先数插入到队列的适当位置。进行调度时，总是把CPU分配给就绪队列中的第1个进程，优先级是由优先数确定的。在操作系统中，常是优先数越小者优先级越大。上页下页退出第2章处理机管理如何确定进程的优先数（也就是进程的优先级）从如下5个方面考虑：1）根据进程的类型。比如，系统进程和用户进程。系统进程完成的任务是提供系统服务，因此，给予系统进程较高的优先数，也能够提高系统的工作效率。2）根据进程执行任务的重要性和紧迫性。3）根据进程程序的性质。一个CPU繁忙的进程，由于需要占用较长的运行时间，影响系统整体效率的发挥，因此只能给予较低的优先数。一个I/O繁忙的进程，给予它较高的优先数后，就能充分发挥CPU和外部设备之间的并行工作能力。上页下页退出第2章处理机管理4）根据对资源的要求。系统资源有处理机、内存储器和外部设备等。可以按照一个进程所需资源的类型和数量，确定它的优先数。比如给予占用CPU时间短或内存容量少的进程以较高的优先数，这样可以提高系统的吞吐量。5）根据用户的请求。系统可以根据用户的请求，给予它的作业及其相应进程很高的优先数，作“加急”处理。上页下页退出第2章处理机管理进程的优先数可以分为静态和动态两类。所谓静态，即指在进程的整个生命期内优先数保持不变。其优点是实现简单，但欠灵活。所谓动态，是指在进程的整个生命期内可随时修正它的优先级别，以适应系统环境和条件的变化。有名的UNIX操作系统就是一个采用动态优先数算法的操作系统。上页下页退出第2章处理机管理4．多级队列调度算法-1上页下页退出第2章处理机管理4．多级队列调度算法-2在第1级到第n－l级队列中的进程，如果在分配给它的时间片内完成了全部工作，那么就撤离系统；如果在时间片没有用完时提出了I/O请求，那么就进入相应的阻塞队列里等待。在所等待的事件、出现时，仍回到原队列末尾，等待下一轮调度（每个队列实行先来先服务调度算法）；如果用完了时间片还没有完成自己的工作，那么只能放弃对CPU的使用，降到低一级队列的末尾。对位于最后一个队列里的进程，实行时间片轮转调度算法。整个系统最先调度1级就绪队列；只有在上一级就绪队列为空时，才去下一级队列调度。当比运行进程更高级别的队列中到达一个进程时，系统将立即停止当前运行进程的运行，让它回到自己队列的末尾，转去运行级别高的那个进程。上页下页退出第2章处理机管理可以看出，多级队列调度算法优先照顾I/O繁忙的进程。I／O繁忙的进程在获得一点CPU时间后就会提出I／O请求，因此它们总是被保持在l、2级等较前面的队列中，总能获得较多的调度机会。对于CPU繁忙的进程，它们需要较长的CPU时间，因此会逐渐地由级别高的队列往下降，以获得更多的CPU时间，它们“沉”得越深，被调度到的机会就越少。但是，一旦被调度到，就会获得更多的CPU时间，所以，多级调度算法采用的是“你要得越多，你就必须等待越久”的原则来分配处理机的。上页下页退出第2章处理机管理例2-3图2－11通过进程状态变迁图描述了一个进程调度算法。试分析该图，说明该调度算法的基本思想。解：从图中可以看出，该系统维持了两个就绪队列：一个是高优先级的就绪队列，一个是低优先级就绪队列。系统总是把CPU优先分配给位于高优先级就绪队列中的进程使用，只有在高优先级就绪队列为空时，才把CPU分配给位于低优先级就绪队列中的进程。上页下页退出第2章处理机管理当一个进程未用完时间片时产生了I/O请求，就进入阻塞队列等待。当I/O完成后，该进程就进入高优先级就绪队列参与对处理机的竞争；在一个进程用完一个时间片而被迫放弃处理机时，它进入的是低优先级就绪队列，参与对处理机的竞争。由此可见，在高优先级就绪队列中的都是I/O繁忙的进程，它们不需要很多的CPU时间；在低优先级就绪队列中的都是CPU繁忙的进程，它们需要很多的CPU时间。于是，通过该调度程序的调度，试图将I/O繁忙和CPU繁忙的进程分开，总是尽量地优先照顾I/O繁忙的进程。通过这种调度，可以使CPU尽可能地与外部设备并行工作，达到提高系统工作效率的目的。上页下页退出第2章处理机管理有人把进程调度程序比作是一个多路开关，通过它把一个CPU分配给多个过程使用，产生出有多个逻辑CPU的空幻印象，只是每个逻辑CPU的运行速度要比真正的物理CPU来得慢一些。多个进程竞争一个物理的CPU造成每个进程都有一个CPU使用的空幻印象上页下页退出第2章处理机管理进程调度程序应该具有以下4个方面的主要功能：1）记录系统中所有进程的有关情况，比如进程的当前状态，优先数等。2）确定分配处理机的算法，这是它的一项主要工作。3）完成处理机的分配。要注意，在操作系统中，是进程调度程序实施处理机的具体分配的。4）完成处理机的回收。可以看出，由于进程调度程序负责具体的处理机分配，完成进程间的切换工作，因此它的执行频率是相当高的，是一个操作系统的真正核心。上页下页退出第2章处理机管理在发生什么情况时，会引起进程调度程序的工作？1）一个进程从运行状态变成了阻塞状态（如请求进行输入／输出操作）。2）一个进程从运行状态变成了就绪状态（如在分时系统中，已经运行满一个时间片）。3）一个进程从阻塞状态变成了就绪状态（如等待的I／O操作完成）。4）一个进程正常运行结束后被撤消。注意1、4两种情形肯定会引起进程调度程序工作，它将从就绪队列里选择一个进程占用处理机，完成过程间的切换；2、3两种情形可能会引起进程调度，也可能是继续运行原进程，这与系统所采用的调度算法有关。上页下页退出第2章处理机管理把处理机分配给进程后，还有一个允许它占用多长时间的问题，具体有两种处理方式：不可剥夺（或不可抢占）方式剥夺（或抢占）方式不可剥夺方式：即只能由占用处理机的进程自己自愿放弃处理机。•比如进程运行结束，自动归还处理机；•进程由于某种原因被阻塞，暂时无法运行而交出处理机。•在进程调度算法中，先来先服务调度算法属于不可剥夺方式。上页下页退出第2章处理机管理剥夺方式：即当系统中出现某种条件时，就立即从当前运行进程手中抢夺过处理机，重新进行分配。时间片轮转调度算法属于剥夺方式。当一个进程耗费一个时间片还没有运行结束时，就强抢处理机，回到就绪队列的末尾，处理机分配给就其他进程。优先数调度算法，既可以设计成是剥夺方式的，也可以设计成是不可剥夺方式的。如果在有比当前运行进程更高级别的进程抵达就绪队列时，允许它把处理机抢夺过来，那么这就是可剥夺方式的优先数调度算法，否则就是不可剥夺方式的优先数调度算法。上页下页退出第2章处理机管理2．3．2进程管理的基本原语操作系统提供若干基本的操作对进程进行有效的管理和控制，以便能创建进程、撤消进程、阻塞进程和唤醒过程。为了保证执行时的绝对正确，要求它们以一个整体出现，不可分割。具有这种特性的程序被称为“原语”。为了保证原语操作的不可分割性，通常总是利用屏蔽中断的方法。下面简略描述对这四个原语的功能：上页下页退出第2章处理机管理1．“创建进程”原语通过调用“创建进程”原语建立一个新的进程，调用该原语的进程被称为父进程，新进程被称为子进程。主要功能有三项。（1）为新建过程申请一个进程控制块PCB：（2）将创建者提供的信息填入PCB中，比如程序入口地址、优先数等，系统给它一个编号，作为标识；（3）将新建进程设置为就绪状态，并按照所采用的调度算法，把PCB排入就绪队列中。上页下页退出第2章处理机管理2．撤消进程原语撤消进程原语的主要功能是收回该进程占用的资源，将该进程的PCB从所在队列里摘下，将PCB所占用的存储区归还给系统。可以看到，当创建一个进程时，为它申请一个PCB；当撤消一个进程时，就收回它的PCB。正是如此，才表明操作系统确实是通过进程的PCB来“感知”一个进程的存在的。一般，总是由父进程或更上一级的进程通过调用撤消进程原语，来完成对进程的撤消工作。上页下页退出第2章处理机管理3