第三章调度与死锁修改2014-10-21用.

进程调度的核心是调度算法。进程调度是实现多道程序系统的关键，直接影响到操作系统的性能，是本章讨论的主要问题。第三章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4产生死锁的原因和必要条件3.5预防死锁的方法3.6死锁的检测与解除引言:处理机调度即进程调度。在多道程序环境中，进程数往往多于处理机数（如单处理机多道环境），这必然引起多个程序对处理机的竞争问题，分配处理机的任务是由处理机调度程序完成的。如何提高处理机的利用率，在很大程度上取决于调度算法性能的好坏。§3.1调度的基本概念(一）一个批处理型作业从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历三级调度过程：一、调度的类型和模型1、高级调度又称为作业调度，作用：把外存上处于后备队列中的作业调入内存，并为他们创建进程、分配资源、排在就绪队列上，准备执行，因此，有时把它称为接纳调度。分时系统、实时系统中通常不具备作业调度。2、低级调度又称为进程调度，它决定就绪队列中哪个进程将获得处理机，然后由分派程序执行把处理机分配给进程的操作。在OS中都必须配置。3、中级调度目的：提高内存利用率和系统吞吐量。作用：使暂时不能运行的进程从内存调至外存，进入就绪驻外存状态或挂起状态。把外存上又具备运行条件的就绪进程，重新调入内存，并修改为就绪状态，挂在就绪队列上。又称对换。阻塞状态就绪状态执行状态调度I/O请求进程释放时间片到后备作业队列§3.1调度的基本概念(二）CPU就绪队列内存外存阻塞队列作业调度等待事件中级调度即交换调度交换文件就绪队列阻塞队列三级调度的模型§3.1调度的基本概念(三）作业调度是确定哪些作业可以被调入内存。进程调度是确定哪个进程可以占有CPU并执行。作业调度是进程调度的基础，作业被调入内存后，是以进程的形式执行的。在一个OS中进程调度与作业调度的算法是一致的。？问题？1。进程调度与作业调度之间（功能、调度算法）有何区别和联系？2。三级调度中，最核心的是那一级调度？为什么？各级调度间的关系§3.1调度的基本概念(四）作业步—将一个作业划分为若干个顺序处理的步骤，作业步相互独立又相互关联。作业—是用户请求计算机系统执行的一次独立的上机任务，是能够共享公共资源区域的一族有关进程（家族）。从静态观点看，作业由作业说明书、程序集、数据集三部分构成。补充：关于作业的概念作业控制块—JCB（JobControlBlock）用于描述作业。定义为记录类型（作业名、优先级、建立时间、状态外存地址、大小等）。作业状态—作业在其生命期中，共有四种状态：关于作业的状态作业状态—作业在其生命期中，共有四种状态：进入、后备、运行、完成完成执行就绪阻塞进入后备内存运行提交作业调度完成问题：引起进程调度的原因有哪些？引起进程调度的原因有以下几类:(1)正在执行的进程执行完毕。(2)执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等状态。(3)执行中进程调用了P原语操作，从而因资源不足而被阻塞；或调用了v原语操作激活了等待资源的进程队列。(4)执行中进程提出I/O请求后被阻塞。(5)在分时系统中时间片已经用完。(6)在执行完系统调用等系统程序后返回用户进程时，这时可看作系统进程执行完毕，从而可调度选择一新的用户进程执行。以上都是在不可剥夺方式下的引起进程调度的原因。在CPU执行方式是可剥夺时．还有(7)就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度。§3.1调度的基本概念(五）非抢占式（非剥夺式）进程一旦被调度，就一直占有CPU，直到完成或因发生某事件而被阻塞（I/O请求）。非抢占方式引起进程调度的因素1.进程执行完毕，或因发生某事件而不能再继续执行2.执行中的进程因提出I/O请求而暂停执行3.在进程通信或同步过程中执行了某种原语操作，如P操作（wait操作）、block原语，wakeup原语等。在OS中，进程调度的方式分为两类。二、进程调度的方式§3.1调度的基本概念(五）抢占式（剥夺式）允许暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。抢占原则（1）优先权原则。优先权高的进程抢占处理机。（2）短作业优先原则。短作业（进程）抢占当前较长作业（进程）的处理机。（3）时间片原则。各进程按时间片运行，当一个时间片用完后重新调度。在OS中，进程调度的方式分为两类。二、进程调度的方式§3.1调度的基本概念(六）仅有进程调度的调度队列模型有高级和低级调度的调度队列模型同时有三级调度的调度队列模型三、调度队列模型•通常，把就绪进程组织成FIFO队列，每当创建新进程时排在就绪队列的末尾，按时间片轮转方式运行仅有进程调度的调度队列模型进程在执行时，出现三种情况：[1]任务在时间片内完成，进程便在释放处理机后进入完成状态；[2]任务在时间片内未完成，OS便将该任务再放入就绪队列的末尾；[3]在执行期间，进程因为某事件而被阻塞后，被OS放入阻塞队列。就绪队列阻塞队列cpu进程调度等待事件时间片完进程完成用户事件出现有高级和低级调度的调度队列模型与前一模型的差别：（1）就绪队列的形式。批处理系统中最常用的是优先权队列。也可采用无序链表方式。（2）设置多个阻塞队列。就绪队列阻塞队列cpu进程调度等待事件时间片完进程完成作业调度后备队列有三级调度的调度队列模型•调出时，可使进程状态由内存就绪转变为外存就绪，由内存阻塞转变为外存阻塞；•在中级调度使外存就绪转变为内存就绪。§3.1调度的基本概念(七）四.选择调度方式与调度算法准则调度算法应该尽可能提高资源利用率，减少CPU空闲时间,公平服务。1.面向用户的准则周转时间短响应时间快截止时间的保证优先权准则2.系统吞吐量高。处理机利用率好。各类资源的平衡利用。（1）周转时间。周转时间是指一个作业从提交开始到完成为止这段时间间隔。具体包括：①作业在外存后备队列等待时间；②作业在就绪队列等待调度的时间；③作业在CPU上的执行时间；④作业等待I/O操作完成的时间。§3.1调度的基本概念(七）可把平均周转时间描述为：niiTnT11niSiiTTnW11作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间，而平均带权周转时间则可表示为:—§3.1调度的基本概念(七）作业提交时间/时运行时间/h110.002210.101310.250.25例:有如下三道作业。系统为它们服务的顺序是：1、2、3。求平均周转时间和平均带权周转时间。§3.1调度的基本概念(七）作业提交时间运行时间开始时间完成时间周转时间带权周转时间110.002210.101310.250.25解：§3.1调度的基本概念(七）作业提交时间运行时间开始时间完成时间周转时间带权周转时间110.0021012.0022/2210.1011213.002.92.9/1310.250.251313.2533/0.25§3.1调度的基本概念(七）平均周转时间：T=(2+2.9+3)/3=2.63h平均带权周转时间：W=(2+2.9+12)/3=5.3h。（2）响应时间。响应时间是衡量分时系统调度性能的一个重要指标。响应时间是指用户通过键盘提交一个请求开始到首次产生响应为止这段时间间隔。包括：①请求信号从键盘传输到计算机的时间；②计算机对请求处理时间；③再将响应送回终端的时间。§3.1调度的基本概念(七）（3）截止时间。是衡量实时系统调度性能的一个重要指标。截止时间是指某任务必须开始的最迟时间或必须完成的最迟时间。包括开始截止时间和完成截止时间。§3.1调度的基本概念(七）（4）优先权准则（优先级准则）。在各种系统中，进行调度算法选择时，让某些紧急的作业能得到及时处理。可以运用剥夺式调度方式，保证紧急作业得到及时处理。§3.1调度的基本概念(七）(5)吞吐量吞吐量指单位时间内系统所完成的作业数。评价批处理系统性能的重要指标。与作业的平均长度有关。对于大型作业，一般吞吐量约为每小时一道作业对于中、小型作业，其吞吐量则可达到数十道作业。§3.1调度的基本概念(七）§3.2调度算法（一）先来先服务（FCFS）算法短作业（进程）优先（SJ(P)F）算法最高优先权（HPF）算法高相应比优先调度(HRN)算法时间片轮转（RR）算法多级反馈队列算法思考题1、各种调度算法的特点、性能如何？适宜于哪类OS？2。最高优先权算法中，动态优先权有何实际意义？常用调度算法§3.2调度算法（二）一.、先来先服务（FCFS）算法FCFS（FirstComeFirstServer）法，又称为先进先出（FIFO）算法，就绪进程按照进入的先后次序排列，调度程序总是选择队首的进程执行。这是一种非剥夺式的调度算法，简单、易实现。对短进程易出现等待时间长，服务质量差。该算法有利于CPU繁忙型的进程，不利于I/O繁忙型的进程。该算法只能用于辅助算法。进程到达时间运行时间开始时间完成时间周转时间带权周转时间A01B1100C21D3100决定服务顺序§3.2调度算法（二）一.、先来先服务（FCFS）算法进程到达时间运行时间开始时间完成时间周转时间带权周转时间A010B11001C21101D3100102开始+运行§3.2调度算法（二）一.、先来先服务（FCFS）算法进程到达时间运行时间开始时间完成时间周转时间带权周转时间A0101B11001101C21101102D3100102202开始+运行§3.2调度算法（二）一.、先来先服务（FCFS）算法进程到达时间运行时间开始时间完成时间周转时间带权周转时间A0101B11001101C21101102D3100102202完成-到达§3.2调度算法（二）一.、先来先服务（FCFS）算法进程到达时间运行时间开始时间完成时间周转时间带权周转时间A01011B11001101100C21101102100D3100102202199周转/运行§3.2调度算法（二）一.、先来先服务（FCFS）算法进程到达时间运行时间开始时间完成时间周转时间带权周转时间A010111/1B11001101100100/100C21101102100100/1D3100102202199199/100§3.2调度算法（二）一.、先来先服务（FCFS）算法进程到达时间运行时间开始时间完成时间周转时间带权周转时间A010111/1B11001101100100/100C21101102100100/1D3100102202199199/100§3.2调度算法（二）一.、先来先服务（FCFS）算法§3.2调度算法（二）二、短作业（进程）优先（SJ(P)F）算法SJ(P)F（1）对长作业不利。如果有一长作业进入系统的后备队列，由于总是优先调度那些短作业（进程），将导致长作业长期不被调度。（2）完全未考虑作业的紧迫程度，不能保证紧迫性作业（进程）会被及时处理。（3）作业（进程）的长短根据用户所提供的估计执行时间而定的不一定能真正做到短作业优先调度。短作业优先（SJF）调度算法:是从后备队列中选择一个或若干个估计运行时间最短作业，将它们调入内存运行。而短进程则是从就绪队列中选择估计时间最短的进程，把处理机分配给它。图3-4FCFS和SJF调度算法的性能进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间周转时间带权周转时间SJF完成时间周转时间带权周转时间作业算法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF完成时间周转时间带权周转时间作业算法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF完成时间4周转时间4带权周转时间作业算法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225