操作系统课件第3章 处理机调度（调度）.pptVIP

Eg：进程 到达时间 服务时间 P1 0 7 P2 2 4 P3 4 1 P4 5 4SPF(非抢占式)平均周转时间=((7-0)+(12-2)+(8-4)+(16-5))/4=8平均等待时间=((0-0)+(8-2)+(7-4)+(12-5))/4=4SPF（非抢占式）调度73160812P1P3P2P4SPF抢占式调度 进程 到达时间 服务时间 P1 0 7 P2 2 4 P3 4 1 P4 5 4SPF(抢占式)平均周转时间=((16-0)+(7-2)+(5-4)+(11-5))/4=7平均等待时间=((11-2)+(5-4)+(4-4)+(7-5))/4=3P1P3P242110P457P2P116FCFS先来先服务调度 进程 到达时间 服务时间 P1 0 7 P2 2 4 P3 4 1 P4 5 4FCFS平均周转时间=((7-0)+(11-2)+(12-4)+(16-5))/4=8.75平均等待时间=(0+(7-2)+(11-4)+(12-5))/4=4.75P142110P257P41612P3SPF与FCFS的比较FCFS非抢占SPF抢占SPF吞吐量0-7ms112平均周转时间8.7587平均等待时间4.7543SJF/SPF短作业/进程优先调度的优缺点优点：1）能有效降低作业的平均等待时间；2）提高吞吐量；3）能有效缩短进程的周转时间；缺点：1）对长作业不利；2）不考虑作业的紧迫程度；3）作业执行时间、剩余时间只能估计*；SJ(P)F算法虽然是优化的，但在CPU调度中很难实现。返回三、时间片轮转调度算法RR将所有就绪进程按FCFS的原则，排成一个队列，依次调度，把CPU分配给队首进程，并令其执行一个时间片/CPU时间，通常为10-100ms。时间片用完后，该进程将被抢占并插入就绪队列末尾。应用于分时OS中，能保证及时响应用户的请求，是早期采用的一种调度算法；进入90年代后，广泛采用多级反馈队列调度算法。三、时间片轮转调度算法RR（1）保证了就绪队列中的所有进程在给定的时间内，均能获得一时间片来执行，即系统在给定的时间内，响应所有用户的请求。（2）若进程的执行时间少于时间片，则自愿释放CPU。（3）时间片长度将影响：调度算法（太长---FCFS）；上下文切换（太短---上下文切换频繁）；平均周转时间。短时间片增加上下文切换频率周转时间随时间片变化三、时间片轮转调度算法—例(1)EG： 进程 到达时间 服务时间 P1 0 7 P2 2 4 P3 4 1 P4 5 4RR（时间片为1）平均周转时间=((15-0)+(12-2)+(6-4)+(16-5))/4=9.5平均等待时间=(8+6+1+7)/4=5.5P1P2P2012345678910111213141516P4P1P1P1P3P2P1P4P2P4P1P4实验内容：编程实现多种处理机调度算法在以下处理及调度算法中任选一种实现：先来先服务（FCFS）调度算法、短进程优先（SPF）调度算法、时间片轮转调度算法（时间片可以设定）、优先权调度算法（静态优先权、可抢占）、高响应比优先调度算法第三章处理机调度与死锁

第3章处理机调度与死锁处理机调度处理机调度的基本概念调度算法实时调度死锁产生死锁的原因和必要条件预防死锁的方法死锁的检测与解除3.1处理机调度的基本概念调度的层次调度队列模型选择调度方式和算法的若干准则返回目录一、调度的层次作业调度中级调度运行就绪阻塞进程调度挂起阻塞挂起就绪创建退出一、调度的层次 一个作业从提交开始，往往要经历三级调度：高级调度、低级调度、中级调度。1、高级调度（长程/作业/宏观调度）定义：根据某种算法，把外存上处于后备队列中的作业调入内存。说明：(1)在批处理系统中,大多配有作业调度,但在分时系统及实时系统中,一般不配置。(2)作业调度执行频率很低,通常为几分钟一次,甚至更久。一、调度的层次高级调度需解决的问题（1）从外存后备队列中选择多少作业进入就绪队列或挂起就绪，即