操作系统-处理器调度概要.ppt

处理器调度 本章教学目标 理解处理器调度的三个层次 掌握处理器调度算法及其评价方法 处理器调度的目的 作业数量众多，而处理器、内存资源有限 将处理器分配给不同的进程，以提高 响应时间 吞吐能力 处理器效率 调度的层次 长程调度(long-term scheduling) 又称高级调度、作业调度 决定了哪些作业被允许进入系统参与CPU的竞争 高级调度将控制多道程序的道数 中程调度(medium-term scheduling) 又称中级调度、平衡调度 根据主存状态决定主存中所能容纳的进程数目。当主存资源紧缺时，决定将哪些进程交换出内存；而当主存资源空闲时，选择将哪些进程交换回内存。 短程调度(short-term scheduling) 又称低级调度、进程调度/线程调度、CPU调度 决定将就绪队列中的哪个进程/内核级线程分配处理器资源，使其能占用CPU执行。 低级调度是操作系统最核心的部分，执行频繁 长程调度 批处理系统 何时从后备作业队列中创建新进程？ 一个作业运行结束 CPU的空闲时间比例超过某个门限值 选择哪些作业进入主存，使其成为进程？ FCFS, SJF, … 平衡CPU密集型作业和I/O密集型作业 平衡I/O资源的使用 时分系统 所有授权用户都被准入，直至系统饱和 短程调度 又称分派器，执行最为频繁 短程调度的执行时刻 外部中断 系统调用 信号 调度算法 调度算法的准则 调度策略 调度算法的准则 吞吐率 单位时间完成的进程数 响应时间 从请求提交到开始接收到响应的时间，适用于交互型进程 处理器利用率 CPU利用率=CPU有效工作时间/（CPU有效工作时间+CPU空闲等待时间） 周转时间 进程从提交到结束的时间，包括执行时间和等待时间，适用于批处理作业 截止时间 进程必须在给定截止时间前完成，适用于实时任务 公平性 确保每个进程过的合理的CPU份额和其他资源分配，避免出现进程饿死。 批处理系统的调度性能指标 平均作业周转时间 平均带权作业周转时间 短程调度的决策模式 抢占式 系统可以根据所规定的原则剥夺正在运行的进程/线程的处理器资源，将其移入就绪队列，选择其他进程/线程执行； 剥夺原则 高优先级进程/线程剥夺低优先级进程/线程 当前运行进程/线程的时间片用完 非抢占式 进程/线程开始运行后不再让出处理器，除非进程/线程运行结束，或因发生某个事件（如等待I/O操作完成）而不能继续执行。 单处理器调度算法种类 先来先服务(First Come First Served: FCFS) 最短作业优先(Shortest Job First: SJF) 最短剩余时间优先(Shortest Remaining Time First: SRTF) 响应比最高者优先(Highest Response Ratio First: HRRF) 优先级调度 轮转调度(Round Robin: RR) 多级反馈队列调度(Multi-Level Feedback Queue: MLFQ) 彩票调度(Lottery Scheduling) FCFS 机制 每个进程就绪时，加入就绪队列。 当前进程停止执行时，选择在就绪队列中时间最长的进程执行。 优点： 非剥夺式调度算法，易于实现 适用于作业调度和进程调度 缺点： 效率不高 不利于短作业而优待长作业 不利于I/O繁忙作业而有利于CPU繁忙作业 SJF 机制 当前进程停止执行时，选择预计所需的CPU运行时间最小的进程执行。 非抢占式 优点： 有利于短作业 易于实现 缺点 无法准确获知进程所需的CPU运行时间 忽视作业的等待时间，有可能造成长作业饿死 缺乏抢占机制，对分时、实时处理依然不理想。 SJF 估算进程的下一个CPU周期长度 指数衰减算法 SRTF 机制： 调度器总是选择具有最短期望剩余运行时间的进程运行； 当一个新进程加入就绪队列时，它可能具有比当前运行进程更短的剩余运行时间，此时，调度器将让该就绪进程抢占当前运行的进程。 实际上可以看作是支持处理器抢占的SJF 优点 有利于短作业 实现额外代价低 缺点 必须估计进程的处理时间 有可能会造成长作业的饿死 HRRF 机制 R=(w+s)/s；R: 响应比， w：等待处理器的时间，s：服务时间 当前运行进程结束或阻塞时，选择响应比R值最大的进程执行。 非抢占式 优点 考虑了进程的老化，有利于短进程(由于s小，所以R值将比较大)，也不会造成长进程的饿死(等待时间加长会使得其R值增加) 缺点 需要估算进程的服务时间 Round Robin 机制 将时间划分成定长的时间片，当时间片完成后，产生时钟中断。 当时钟中断发生后，当前运行进程被放到就绪队列，按FCFS的原则选取下一个就绪进