第三章+处理机调度与死锁2

1、第三章第三章 处理机调处理机调度与死锁度与死锁第三章第三章 处理机调度与死锁处理机调度与死锁3.1 3.1 处理机调度的基本概念处理机调度的基本概念 1)1)调度类型调度类型 高级调度高级调度：即作业调度，选择后备作业进入内存，为其建立进程,分配资源并排在就绪队列。 中级调度中级调度：即对换调度，将暂不运行的进程调到外存等待，从而提高内存利用率和系统吞吐量 低级调度低级调度：即进程调度进程调度，决定哪个进程可以占用CPU，进入运行状态。输入程序输入程序就就绪绪阻阻塞塞就就绪绪运运行行完完成成阻阻塞塞后后备备外存外存中级调度中级调度对换对换低级调度低级调度作业调度作业调度2)2)进程调度方式进程

2、调度方式 调度方式是指当某一个进程正在处理机上执行时如果有个更重要更紧迫的进程需要处理此时应该如何分配处理机。n非抢占方式非抢占方式 进程一旦被调度执行，除非进程完成或发生某事件被阻塞，否则不允许其他进程抢夺其执行权。n抢占方式抢占方式 允许按某种策略（原则）剥夺正在执行的进程的执行权 -优先权原则-短作业(进程)优先原则-时间片原则3)3)调度类型与调度类型与O.SO.S类型的关系类型的关系多道批处理系统：存在作业调度、进程调度分时/实时系统：只有进程调度 共同点：均存在进程调度（分配共同点：均存在进程调度（分配CPUCPU）4) 4) 调度队列模型调度队列模型( (三种三种) )就就队队

3、列列绪绪CPUCPU进程调度进程调度进程完成进程完成时间片完时间片完阻阻队队 列列塞塞交互用户交互用户等待事件等待事件事事件件出出现现n具有高级和低级的调度队列模型后后队队 列列备备1 1阻阻队队 列列塞塞作作业业调调度度就就队队 列列绪绪CPUCPU进程调度进程调度进程完成进程完成时间片完时间片完等待事件等待事件1 1事件事件1 1出现出现2 2阻阻队队 列列塞塞n n阻阻队队 列列塞塞等待事件等待事件2 2等待事件等待事件n n事件事件2 2出现出现事件事件n n出现出现n具有三级调度的调度队列模型作作业业调调度度就就队队 列列绪绪CPUCPU进程调度进程调度进程完成进程完成时间片完时间片

4、完事件出现事件出现阻阻 塞塞列列、起起 队队挂挂阻阻队队 列列塞塞等待事件等待事件就绪、挂起队列就绪、挂起队列事件出现事件出现挂起挂起中级调度中级调度后后队队 列列备备交互型作业交互型作业批量作业批量作业挂起挂起5) 5) 调度性能评价调度性能评价 作业调度算法的评价因素 CPUCPU利用率利用率：越高越好 吞吐量吞吐量：单位时间内CPU完成作业的数量 周转时间周转时间：通常与带权周转时间一起作为评价批处理系统的性能指标，定义如下：,1,2,.,/,1,2,.,ioisiiiriTttinWT tin n个作业的平均周转时间T和平均周转系数W分别为1111niniTTinWW inn 对于每个

5、用户来说，总是希望作业提交后立即执行，这样周转时间等于执行时间；而对于一个计算机系统来说，不可能满足每个用户的这种要求，只能使系统的平均周转时间最短。对于分时系统常把响应时间的长短作为评价标准； 对于实时系统常把截止时间作为评价标准。3.2 3.2 调度算法调度算法l 先来先服务调度算法先来先服务调度算法l 短作业（进程）优先调度算法短作业（进程）优先调度算法l 高优先权者优先调度算法高优先权者优先调度算法l 时间片轮转调度算法时间片轮转调度算法l 多队列反馈轮转调度算法多队列反馈轮转调度算法l 实时调度算法实时调度算法1 1）先来先服务调度算法）先来先服务调度算法策略：策略：先进入后备队列（

6、就绪队列）的作业（进 程）先被调度优点：优点：算法简单易实现缺点：缺点：不分轻重缓急，对短作业（进程）不利2 2）短作业（进程）优先调度算法）短作业（进程）优先调度算法策略：策略：启动要求运行时间最短的作业。优点：优点：有效降低作业平均等待时间提高系统的吞 吐量缺点：缺点：长作业（进程）可能长期得不到服务3 3）高优先权者优先调度算法）高优先权者优先调度算法 优先权：优先权：反映作业（进程）重要性和调度级别的权值，又称优先数。通常分为：静态优先数静态优先数：进程创建时确定运行过程中不会改变。一般根据进程的类型，资源需求情况，估计的运行时间等因素确定。动态优先数动态优先数：创建进程时确定一个优先

7、级，进程运行过程中可以根据情况的变化调整优先级，调整一般是根据进程占用的CPU的时间长短、进程等待CPU时间长短来进行。 高响应比优先调度算法（高响应比优先调度算法（HRPHRP）：）：优先调度响应比高的作业 响应比响应比R RP P（等待时间（等待时间+ +要求服务时间）要求服务时间）/ /要求服务时间要求服务时间 响应时间响应时间/ /要求服务时间要求服务时间 1 + 1 + 等待时间等待时间/ /要求服务时间要求服务时间 优点：既照顾短作业又考虑作业到达的先后 次序，而且不会使长作业长期得不到 服务。 缺点：每次调度前都要进行响应比计算增加 系统开销 类型非抢占式优先权调度非抢占式优先权

8、调度：处理机一旦分配给就绪队列中优先权最高的进程后，该进程就一直运行下去直到自动放弃或完成，这时才可把处理机分配给另一优先级最高的进程。抢占式优先权调度抢占式优先权调度：进程在运行时一旦出现了另一个优先级更高的进程，调度程序就停止该进程而把处理机分配给新出现的高优先权进程。4 4）时间片轮转调度算法（适合于分时系统）时间片轮转调度算法（适合于分时系统） 策略：策略：各作业（进程）轮流运行（执行）一个时间片 优、缺点：优、缺点：简单易实现，但不分轻重缓急 关键：关键：时间片大小的选择5 5）多级队列反馈轮转调度算法）多级队列反馈轮转调度算法 策略：将时间片策略：将时间片与优先级优先级调度相结合。

9、 -设置多个就绪队列，分别赋予不同的优先级。 优先级越低则时间片越长 -新进程进入内存后，先投入第一队列的末尾， 按FCFS算法调度；若按第一队列一个时间片未能 执行完，则降低投入到第二队列的末尾，同样按 FCFS算法调度；如此下去，降低到最后的队列， 则按“时间片轮转”算法调度直到完成 -仅当较高优先级的队列为空，才调度较低优先级 的队列中的进程执行。如果进程执行时有新进程 进入较高优先级的队列，则抢先执行新进程，并 把被抢先的进程投入原队列的末尾就绪队列就绪队列1 1S1至至 CPU就绪队列就绪队列2 2 S2至至CPU 就绪队列就绪队列3 3 S3至至 CPU就绪队列就绪队列n n Sn

10、至至CPU 调度算法性能分析调度算法性能分析设有四个作业，其提交时刻、执行时间如下表所示，分别采用FCFS、SJF、FPF调度方法，计算平均周转时间T和平均周转系数W。作业号提交时刻运行时间18.002.0028.500.5039.000.1049.500.20先来先服务调度算法：先来先服务调度算法： 顺序为1 2 3 4，平均周转时间和平均周转系数的计算结果如下表所示： 作业 提交时间 执行时间开始时间完成时间周转时间周转系数 1 8.00 2.00 2 8.50 0.50 3 9.00 0.10 4 9.50 0.208.0010.002.001.0010.0010.502.004.001

11、0.5010.601.6016.0010.6010.801.306.506.9027.50 平均周转时间平均周转时间T1.725小时，平均周转系数小时，平均周转系数W6.875 最短作业优先调度算法最短作业优先调度算法：由于在8.00开始执行作业，当时仅有1，而作业2，3，4尚未到达，故作业1是最短作业。作业1执行完成后是10.00，此时作业2，3，4均已经到达，故选最短作业3，然后是4，2。所以顺序为1,3,4,2。平均周转时间和平均周转系数的计算结果如下表所示： 作业 提交时间执行时间开始时间 完成时间 周转时间 周转系数 1 8.00 2.00 2 8.50 0.50 3 9.00 0.

12、10 4 9.50 0.208.0010.002.001.0010.0010.101.1011.0010.1010.300.804.0010.3010.802.304.606.2020.60 平均周转时间平均周转时间T1.55小时，平均周转系数小时，平均周转系数W5.15响应比高者优先算法：响应比高者优先算法：在作业1执行完成，计算作业2，3，4的响应比分别为：4，11，3.5，因此作业1执行完成后选中作业3完成。执行顺序为1，3，2，4。按此算法求得的平均周转时间和平均周转系数如下表所示： 作业 提交时间执行时间开始时间 完成时间 周转时间 周转系数 1 8.00 2.00 2 8.50 0

13、.50 3 9.00 0.10 4 9.50 0.208.0010.002.001.0010.0010.101.1011.0010.1010.602.104.2010.6010.801.306.506.5022.70 平均周转时间平均周转时间T1.625小时，平均周转系数小时，平均周转系数W5.675总结：就其平均周转时间和平均周转系数总结：就其平均周转时间和平均周转系数来说，最短作业优先算法最小，先来先服务来说，最短作业优先算法最小，先来先服务算法最大，响应比高者优先算法居中。算法最大，响应比高者优先算法居中。6 6）两种常见的实时调度算法）两种常见的实时调度算法n最早截止时间优先算法最早截

14、止时间优先算法(EDF)(EDF) 选择就绪队列中开始截止时间最早的实时任务对应的进程先执行（一般非抢占方式）n最低松弛度优先算法最低松弛度优先算法(LLF)(LLF)松弛度松弛度= =规定完成时间规定完成时间- -所需执行时间所需执行时间- -当前时间当前时间选择松弛度最小的实时任务对应的就绪进程先执行，一般采用抢占方式，当某进程松弛度为零时，必须立即抢占执行。EDF例例：进程到达时刻执行所需时间 开始截止时间P1042P22310P3324P4537t=0只有P1进程，P1执行4个单位时间t=4P2、P3均到达，P3截止时间早于P2截止时间 P3执行两个单位时间t=6P2和P4就绪，P4截

15、止时间早于P2，P4执行t=9只剩P2，P2执行LLFLLF例例：两个周期性实时任务A和B， A：每20ms执行一次，每次执行时间为10ms B：每50ms执行一次，每次执行时间为25mst (ms)0102030405060708090100110120A1A2A3A4A5A6B1B2调度调度（执行）（执行）抢占抢占抢占抢占松弛度松弛度t (ms)0102030405060708090100110120A1(10)A2(10)A3(10)A4(10)A5(10)B1(20)B2(10)B1(5)B2(15)A1=10未进入未进入A2A2=0A3=10 A3=5未进入未进入A4A4=0A5=1

16、0B1=25 B1=15B1=15B1=5未进入未进入B2B2=20 B2=20 B2=10A1B1A2B1A3B2A4B23.3 3.3 死锁死锁 死锁：多个进程竞争竞争系统资源资源，造成一种僵局僵局，使得这些进程在无外力的作用下，均无法无法继续向前推进推进。 讨论问题n死锁的产生原因n产生死锁的必要条件n死锁的预防n死锁的避免n死锁的检测和解除1 1）产生死锁的原因死锁主要是由两个或多个进程对资源需求的冲突引起的进程A请求资源R2进程B请求资源R1请求资源R1请求资源R2R1分配R2分配（阻塞）（阻塞）死锁产生的原因：p 资源竞争资源竞争p 进程推进顺序不当进程推进顺序不当n资源竞争引起死

17、锁情况独占资源分为可剥夺式和不可剥夺式，死锁与不 可剥夺式有关。P1P2R1Rn进程的推进顺序不当导致死锁请求打印机请求读卡机释放打印机释放读卡机进程P1请求读卡机请求打印机释放读卡机释放打印机进程P2打印机读卡机Req(R1)Req(R2)Rel(R1)Rel(R2)Req(R2)Req(R1)Rel(R2)Rel(R1)进程的推进顺序非法将导致死锁（续）P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2) 进程推进顺序合法进程的推进顺序非法将导致死锁（续）P2Rel(R1)P2Rel(R2)P2Re

18、q(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2) 进程推进顺序合法进程的推进顺序非法将导致死锁（续）P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2) 进程推进顺序合法进程的推进顺序非法将导致死锁（续）P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2) 进程推进顺序不合法D:不安全区2 2）死锁产生的四个必要条件）死锁产生的四个必要条件n 互斥条件互斥条件n

19、 请求和保持条件请求和保持条件n 不剥夺条件不剥夺条件n 环路等待条件环路等待条件上述条件是产生死锁的必有条件，并非充分条件。如果破坏上述4个条件之一，就可以预防死锁的产生。3.4 3.4 死锁的处理死锁的处理用于处理死锁的主要方法：n预防预防死锁：通过设置限制条件破坏死锁的四个必要条件 中的一个或几个来防止死锁发生n避免避免死锁：资源分配过程中用某种方法防止系统进入不 安全状态来防止死锁发生n检测检测死锁：通过系统的检测机构来检测死锁发生n解除解除死锁：通过撤销或挂起一些进程恢复系统正常运行1 1）预防死锁）预防死锁策略：策略：从破坏死锁的必要条件入手从破坏死锁的必要条件入手, ,破坏（摒弃

20、）四破坏（摒弃）四 个必要条件之一个必要条件之一 摒弃摒弃“互斥条件互斥条件” 由设备的固有属性决定，只能通过某种技术加以利用，但一般来说这种方法不是很有效。 摒弃摒弃“请求和保持条件请求和保持条件” 进程创建时，一次性将全部所需资源均分配给进程，其在运行过程中不会产生新的请求。 摒弃摒弃“不剥夺条件不剥夺条件” 进程因请求新资源而得不到满足，造成阻塞时，暂时释放已占有的所有资源（剥夺）。 摒弃摒弃“环路等待条件环路等待条件” 按序分配资源。系统依据一定的策略给资源由低到高编号，进程必须按从小到大顺序申请资源，并规定进程占有的资源号小于申请的资源号才能得到申请资源。使之资源分配图不会形成环路。

21、2 2）避免死锁）避免死锁 避免死锁避免死锁：用动态方法判断资源的使用情况和系统状态，在分配资源之前，系统将判断如果满足进程的请求是否可能会发生死锁。如果会，就不分配资源，从而避免死锁。系统状态分为安全安全状态状态和不安全状态不安全状态：安全状态：安全状态：存在一个状态序列能够使所有的进程均得到它们所需的资源并执行结束。不安全状态不安全状态：如果不存在一个状态序列能够使所有的进程均执行结束，即为不安全状态。安全状态示例：安全状态示例： 假定系统有三个进程P1、P2和P3，共有12台磁带机。T0时刻资源分配状况为图1，T1时刻P3又申请到了一台磁带机其资源分配状况如图2：进程最大需求已分配可用P

22、1P2P310495223进程最大需求已分配可用P1P2P310495232安安全全不不安安全全安全序列 =?避免死锁的方法：银行家算法避免死锁的方法：银行家算法银行家算法银行家算法(由Dijkstra提出)：在资源分配时进行判断，分析系统状态是否安全。 基本思想：基本思想：将系统资源比作贷款，申请资源的进程比作借款人，操作系统比作银行家。银行家不可能满足所有借款人所要求借款的总额，所以当某借款人提出借款时，银行家必须判断如果将款借出，会不会导致资金周转不灵。若会，则不借；否则，就借。n单项资源的银行家算法假设系统中有10台磁带机，有3个进程A、B、C对磁带机占有及需求情况如下表所示。系统剩余

23、磁带机2台。进程名已分配数尚需申请数最大需求数A224B336C358此时，若A申请1台，或B申请1台，或C申请2台分配不分配不分配银行家算法银行家算法n银行家算法过程：对每一个资源申请进行检查，看如果满足该申请是否会导致不安全状态。若是，则不满足该申请，否则就满足。检查状态是否安全的方法是看是否有足够的资源满足一个距最大需求最近的进程。如果可以，则认为这些资源是可以收回的，然后检查下一个距最大需求最近的进程，如此反复下去。如果所有资源最终都被收回，则该状态是安全的，最初的申请可以满足。银行家算法银行家算法n单项资源的银行家算法系统中某一资源总量为10，4个进程申请，初始状态如下图所示。进程名

24、已有数目最大需求尚需数目a044b055c066d077剩余资源10银行家算法银行家算法n单项资源的银行家算法某一时刻，系统状态如下图所示。进程名已有数目最大需求尚需数目a143b253c165d275剩余资源4先满足进程a银行家算法银行家算法n单项资源的银行家算法满足进程a后，系统状态如下图所示：进程名已有数目最大需求尚需数目a-b253c165d275剩余资源5状态是安全的银行家算法银行家算法n单项资源的银行家算法但如果先满足进程c后，系统状态如下图所示。进程名已有数目最大需求尚需数目a143b253c561d275剩余资源0状态是不安全的银行家算法银行家算法n多项资源的银行家算法：设置资

25、源的已分配矩阵allocation、尚需资源矩阵need以及可分配资源向量available。如果某一进程对某一种资源提出申请，就假定预先分配给它，然后修改已分配矩阵allocation、尚需资源矩阵need和向量available；在矩阵need中找出一行，使该行向量小于等于available。若不存在这样的向量，就说明没有进程能够获得全部资源运行到完成，将会引起死锁；假设被选中的那一行的进程获得资源并运行结束，把它占有的资源全部加入向量available；重复(2)(3)步骤，直到下述情况之一出现：或者所有进程都完成，则系统是安全的，可以分配；或者发生死锁，则预先分配是不安全的，应不予分配。银行家算法银行家算法n多项资源的银行家算法假设系统中有4类资源：打印机5个、手写板7个、扫描仪8个和读卡器9个，分别表示为R1，R2，R3，R4；共有5个进程a，b，c，d，e，某时刻系统状态如下所示：银行家算法银行家算法进程R1R2R3R4a2431b2205c1550d5013e0333(a)最大需求进程R1R2R3R4a0121b1102c0340d2001e0013(b)已分配进程R1R2R3R4a2310b1103c1210d3012e0320(c)尚需资源(d)比较结果available=(2,2