计算机操作系统-第四章.

第4章处理器调度一、操作系统中的调度1.什么是调度调度(Scheduling)是管理的一种方法、是一种决策，资源（如工作、人力、车辆等）经过管理得到合理、有效地利用。调度的目标是找出一种合理的、有效的安排方法，提高资源的利用率。2.操作系统中的调度作业调度进程调度交换调度设备调度3.调度的性能指标周转时间和平均周转时间Ti=作业Ji的完成时刻-作业Ji的提交时刻nTiTni/)(1响应时间R=请求处理过程第1次得到结果的时刻-请求提交的时刻评价调度性能的其他指标公平合理提高资源利用率吞吐量二、作业调度1.作业状态2.批处理系统为什么需要作业调度？3.作业调度的主要功能设计数据结构，登记调度所需要的参数执行指定的算法，从作业的后备队列中选择一个作业为选中的作业分配资源，创建进程作业完成时的资源回收4.作业调度算法先来先服务算法(FCFS)•思想：排队•特点•公平合理•算法简单，容易实现•服务质量欠佳(有于大作业，不利于小作业)例子：假定在某单道批处理系统中，一批作业A、B、C和D在同一时间先后几乎同时到达。已知它们都是纯计算性的简单任务，运行时需要占用处理器时间分别是10、3、2和5。把到达时间(提交时间)设为0。TA=10，TB=13，TC=15，TD=20；T=(TA+TB+TC+TD)/4=(10+13+15+20)/4=14.5TA=20，TB=3，TC=5，TD=10；T=(TA+TB+TC+TD)/4=(20+3+5+10)/4=9.5短作业优先算法(SJF)•一个作业运行时所需的处理器时间总和，简称为作业大小•SJF思想•SJF特点•算法思想简单，但实现困难•拥有最小平均周转时间,吞吐量大•存在“饥饿”现象高响应比优先算法(HRN)•一个作业的响应比R是•HRN思想•HRN特点•综合了先来先服务算法(FCFS)和短作业优先算法(SJF)•响应比R与作业的大小成反比，体现SJF算法•响应比R与作业的等待时间成正比，体现FCFS算法4.作业调度算法例子作业大小作业等待时间其中，作业等待时间=系统当前时间-作业提交时刻例1假定在某脱机单道批处理系统中，有一批作业，它们的提交时刻和作业大小如表4-1所示，假定在10:00时开始调度，求分别采用FCFS、SJF、HRN作业调度算法时的调度顺序、各作业的周转时间、各算法的平均周转时间。表4-1例1的作业信息作业号提交时刻作业大小(小时）J19:000.8J29:101J39:450.6J410:000.4例2在某联机单道批处理系统中，有一批作业，它们的提交时刻和作业大小如表4-5所示。分别采用FCFS、SJF、HRN作业调度算法时的调度顺序、各作业的周转时间、各算法的平均周转时间。表4-5例2的作业信息作业号提交时刻作业大小(小时）J19:000.8J29:101J39:450.6J410:000.4三、进程调度1.进程调度含义2.进程调度功能进程调度方式：运行状态的进程何时以什么方式停止或暂时停止运行进程调度算法：从就绪队列中按照指定的算法选择一个进程，准备执行处理器切换进程结束时资源回收3.进程调度方式非抢占方式(NonpreemptiveScheduling)抢占方式(PreemptiveScheduling)常见的原则有：时间片原则、优先级原则、任务紧迫性、重要性原则等等。进程调度方式实现进程之间的轮流交替的一个方面。4.进程调度算法先来先服务算法(FCFS)时间片轮转算法(RR)RR算法需要设计一个定时器，定时器的值为0时将产生一个中断。系统用分配给进程的时间片设置定时器的初值，之后进程开始执行。进程运行过程有三种可能情况：例子：假定某分时系统有3个同时依次到达的进程A、B和C，它们的任务如下：进程A：进程B：进程C：2msCPU10msI/O2msCPU9msCPU5msI/O2msCPU8msCPU在采用简单RR算法，时间片为3ms时，请画出RR算法的调度图。响应时间简单RR算法，假设就绪队列中的进程数为n，时间片为T，那么，响应时间R，则R=T*n优先级算法(Priority)思想实现关键静态优先级/动态优先级非抢占优先级/抢占优先级优先数的确定多级队列算法四、实时系统的进程调度算法1.实时系统中的任务通常分为周期性任务和非周期性的任务2.实时系统的时间参数任务就绪时限任务开始时限任务完成时限任务处理时间UNIX系统为用户设置两个典型的队列：前台队列和后台队列3.实时系统的可调度一组事件或进程是可调度的(Schedulable)系统是可调度的设λ是单位时间内到达的请求数，μ是处理器单位时间可处理的请求数(处理器的处理能力)，那么，系统是可调度的必要条件是μ≥λ某实时系统要求处理n个周期性的任务，它们的时间周期分别是P1、P2、…、Pn，而处理时间分别是C1、C2、…、Cn，那么，在不考虑系统开销的理想情况下，如果满足那么，这n个任务是可调度的。11niPiCi假定系统只有一个周期性任务，任务的周期为P，处理时间为C，那么1PC那么，系统是可调度的。4.时限调度算法例如，有2个周期性任务A、B，它们的周期分别是20ms和56ms，处理时间分别是8ms和32ms。以完成时限为调度参数，那么，如何画出采用时限进程调度算法的调度图呢？表4-9任务A和B的事件产生时间表任务A发生时间完成时限任务B发生时间完成时限A1020B1056A22040B256112A34060B3112162A46080…A580100A6100120…五、死锁1.死锁(Deadlock)的含义例子死锁的含义死锁与程序设计中死循环有什么区别死循环死锁产生必然性偶然性状态执行状态阻塞状态原因程序设计不当或编写错误操作系统的管理、控制2.死锁产生的根本原因系统拥有的资源数量小于各进程对资源的需求总数3.死锁的四个必要条件互斥条件不剥夺条件请求与保持条件环路等待条件死锁解决方法有：预防、避免、检测与恢复等三种4.死锁预防(DeadlockPrevention)含义方法互斥条件原则上不能被破坏，打印等个别资源可以采取虚拟技术不剥夺条件原则上不能被破坏。请求与保持条件静态分配：具有一般性，但事先很难准确地估计进程运行所要全部资源，且降低了资源的利用率资源暂时释放：仅限于个别资源的操作；进程不稳定，环路等待条件按序分配：具有一般性，但存在与静态分配的问题，且编号管理困难。单请求方式：不适用于复杂任务的进程例1进程P运行过程依次申请编号为：A2、A3、A5和A4。则采用按序分配时，进程P的资源应该怎样申请资源？例2[经典同步问题]哲学家用餐问题：有5位哲学家围坐在一张桌子周围共同讨论一问题。他们各自独立地或拿起筷子用餐或独自思考问题。假定桌上的每两位相邻的哲学家之间放一支筷子，每位哲学家在用餐时需要得到左右两边的筷子，然后才能用餐，用餐后放下筷子，又开始独立思考问题。如此反复。由于两位哲学家共享他们之间的一支筷子，哲学家们用餐和思考问题又具有随机性，那么，如何用信号量机制实现5个哲学家进程的并发执行。表4-10哲学家进程并发程序设计P1(){思考；p(s1)；拿右边筷子f1；p(s2)；拿左边筷子f2；用餐；v(s2)；放下左边筷子f2；v(s1);放下右边筷子f1；}P2(){思考；p(s2)；拿右边筷子f2；p(s3)；拿左边筷子f3；用餐；v(s3)；放下左边筷子f3；v(s2);放下右边筷子f2；}P3(){思考；p(s3)；拿右边筷子f3；p(s4)；拿左边筷子f4；用餐；v(s4)；放下左边筷子f4；v(s3);放下右边筷子f3；}P4(){思考；p(s4)；拿右边筷子f4；p(s5)；拿左边筷子f5；用餐；v(s5)；放下左边筷子f5；v(s4);放下右边筷子f4；}P5(){思考；p(s5)；拿右边筷子f5；p(s1)；拿左边筷子f1；用餐；v(s1)；放下左边筷子f1；v(s5);放下右边筷子f5；}main(){cobegin{repeatP1()；repeatP2()；repeatP3()；repeatP4()；repeatP5()；}}4.死锁避免(DeadlockAvoidance)安全状态和安全序列系统不安全状态：此时系统不存在进程安全序列。死锁避免的含义银行家算法(theBanker’sAlgorithm)例2某系统有4类资源A、B、C、D，数量分别为8、10、9、12。当前有5个进程P1、P2、P3、P4、P5，已经最大需求矩阵Max和当前分配矩阵Used如图4-11所示。问：1)当前系统是否为安全状态？2)在图4-11状态下，如果进程P1申请request=(1，0，1，0)，系统能否分配？3)在图4-11状态下，如果进程P3申请request=(1，0，0，1)，系统能否分配？表4-10例子的安全序列查找的初始状态进程MaxUsedNeedAvailableFinishedABCDABCDABCD2122P1463811013537P233522241111143631P3660905016108P4348711152372P5432520222303638524.死锁检测与恢复(DeadlockDetectionandRecovery)死锁检测的含义资源分配图资源分配图定义如下：资源分配图G=(V，E)，其中V为结点集，E为边集。V=P∪R，这里，P是进程结点子集，R是资源结点子集；边eij=(pi，rj)表示申请边，即进程pi申请一个单位的资源rj，边eij=(ri，pj)表示分配边，即已经分配一个单位的资源ri给进程pj。在画图时，用圆“○”表示进程结点，用正方形“□”表示资源结点，如果某类资源的数量有多个，则在对应的正方形“□”内用实心圆点表示其数量。资源分配图的简化边消除操作的条件：当前结点Pi不是孤立点，同时，不存在含有Pi结点的申请边，或者存在Pi结点的申请边但其资源申请都能得到满足。例子系统拥有的资源有R1、R2、R3、R4、R5和R6数量分别为2、1、1、1、1和2，当前进程有A、B、C、D和E，已知当前进程和资源的申请、分配关系，如表4-14所示。请画出当前系统的资源分配图，并给出简化过程。表4-14系统当前的进程和资源的申请、分配关系进程分配得到的资源申请的资源A2个单位的R11个单位的R3B1个单位的R51个单位的R1C1个单位的R21个单位的R4D1个单位的R3，1个单位的R61个单位的R5E1个单位的R41个单位的R6死锁恢复(DeadlockRecovery)剥夺资源撤销进程重新启动系统例子假设某一道程序运行时需要访问临界资源R，该程序可供多个用户同时运行，如果系统拥有资源R的数量为k，而程序申请使用资源R的数量为x(假定程序每次只申请1个，先后分x次申请)，有n个用户同时运行该程序。那么，k、x和n满足什么条件下，可以保证用户运行时不会产生进程死锁？鸵鸟算法：死锁的预防、避免，还是检测与恢复，都还没有找到简单、实用的有效方法。在考虑到死锁产生的可能性很小，与平常的机器硬件故障、系统死机等其他错误相比，死锁还是微不足道，因此，现有的操作系统通常不处理死锁问题，由程序员在设计开发软件过程根据实际应用自行处理，或由其他系统软件、开发平台等进行死锁检测。本章作业•3，5，6，8，11，13，15