操作系统原理第4章.ppt

第4章 处理机调度 4.1 分级调度 4.2 作业调度 4.3 进程调度 4.4 调度算法 4.5 算法评价 4.6 实时系统调度方法 第4章 处理机调度 4.1 分级调度 4.1.1 作业的状态及其转换 4.1.2 调度的层次 (1) 作业调度——宏观调度或高级调度 (2) 交换调度——中级调度 (3) 进程调度——微观调度或低级调度 (4) 线程调度 4.1.3 作业与进程的关系 第4章 处理机调度 进程状态及其转换 第4章 处理机调度 作业状态及其转换 第4章 处理机调度 4.2 作业调度 4.2.1 作业调度功能 4.2.2 作业调度目标与性能衡量 调度目标： (1) 对所有的作业应该是公平合理的； (2) 应使设备有高的利用率； (3) 执行尽可能多的作业（吞吐量大）； (4) 有快的响应时间。 性能衡量： 1. 周转时间Ti=Tei?Tsi或Ti=Twi+Tri (Tsi—作业的提交时间，Tei—作业的完成时间) 2. 带权周转时间Wi=Ti/Tri 第4章 处理机调度 4.3 进程调度 4.3.1 进程调度的功能 4.3.2 进程调度的时机 4.3.3 进程上下文切换 4.3.4 进程调度性能评价 第4章 处理机调度 4.4 调度算法 1. 先来先服务FCFS——First Come First Serve 2. 轮转法RR——Round Robin 3. 多级反馈轮转法——Round Robin with multiple feedback 4. 优先级法——静态法和动态法 [例] 线性优先级调度策略 第4章 处理机调度 新创建进程队列中进程的优先级P=a*t (a0) 享受服务进程队列中进程的优先级P=b*t (ab0) P(t)=a*(t?t1) 进程在时刻t1被创建 P(t)=a*(t1?t1)+b*(t?t1) 进程在时刻t1转入享受服务队列 若ba0，则为FCFS； 若ab=0，则为RR法。 线性优先级调度策略介于FCFS和RR法之间。 第4章 处理机调度 4.4 调度算法 5. 最短作业优先法SJF——Shortest Job First 6. 最高响应比优先法HRN——Highest Response-ratio Next 响应比=等待时间/运行时间 [例] 9:30开始调度：作业A的响应比=40/90，作业B的响应比=30/24，作业C的响应比=0/60。 9:54调度：作业A的响应比=64/90，作业C的响应比=24/60。 调度次序：B、A、C。 第4章 处理机调度 常用的作业调度算法 (1) 先来先服务(FCFS——First Come First Serve) (2) 短作业优先(SJF——Shortest Job First) (3) 响应比高者优先(HRN——Highest Response-ratio Next) 响应比=等待时间/运行时间 (4) 优先级调度 (5) 均衡调度算法(资源调度算法) 第4章 处理机调度 试题6 （90） 从供选择的答案中，选出应填入下列叙述中__n__内的正确答案，把编号写在答卷的对应栏内。 假设某多道程序设计系统有供用户使用的主存空间100K，磁带机2台，打印机1台，系统采用可变分区方式管理主存，对磁带机和打印机采用静态分配，并假设输入输出操作的时间忽略不计。现有一作业序列如下： 第4章 处理机调度 假设作业调度采用先来先服务算法，优先分配主存的低地址区域且不准移动已在主存中的作业，在主存中的作业平分CPU时间，则作业调度选中作业的次序是__A__，如果把一个作业从进入输入井到得到计算结果的时间定义为周转时间，则在忽略系统工作时间的情况下，最大的作业周转时间是__B__，最小的作业周转时间是__C__，作业的平均周转时间是__D__，作业全部执行结束的时间是__E__。 供选择的答案 A：① (1, 3, 2, 4, 5) ② (1, 2, 3, 4, 5) ③ (1, 3, 4, 2, 5) ④ (1, 2, 4, 3, 5) B~D：① 30分钟 ② 36分钟 ③ 40分钟 ④ 44分钟 ⑤ 55分钟 ⑥ 64分钟 E：① 9:20 ② 9:30 ③ 9