操作系统原理学习笔记（十一）-处理机调度的层次与调度算法的目标

操作系统原理学习笔记目录

这节与下一节讲的有点远，所以比较短。

处理机调度的层次

调度的实质是资源分配。

• 高级调度（High Level Scheduling）/长程调度/作业调度：
  调度对象是作业，根据算法决定哪些作业调入内存，放入就绪队列。
  用于多道批处理系统，在分时系统和实时系统中不设置。
• 低级调度（Low Level Scheduling）/进程调度/短程调度：
  调度对象是进程/内核级线程，决定就绪队列哪些进程获得处理机。
  最基本的调度，在多道批处理、分时系统、实时系统中都必须配置。
• 中级调度（Intermediate Scheduling）/内存调度：
  引入目的是，提高内存利用率与系统吞吐量，中级调度决定哪些将被挂起，但具备运行条件的就绪进程重新调入内存。
  中级调度实际上是存储器管理中的兑换功能。

三种调度中，进程调度运行频率最高，在分时系统中仅10~100ms进行一次，为提高效率，不应使用复杂算法。
作业调度发生在一批作业运行完毕并退出系统，又需要重新调入作业进入内存时，几分钟运行一次，允许使用复杂算法。
中级调度运行频率介于上述两者之间。

处理机调度的算法

处理机调度算法的共同目标

• 资源利用率：提高对系统资源的利用。其中，CPU利用率=CPU有效工作时间/（CPU有效工作时间+CPU空闲等待时间）。
• 公平性：各进程获得合理的CPU时间，不发生进程饥饿。公平性是相对的，相同类型的进程应获得相同的服务，不同进程根据紧急程度或重要性的不同获得不同服务。
• 平衡性：使得系统中CPU与各外部设备都能经常处于忙碌状态。
• 策略强制执行：对所指定的策略包括安全策略，若需要，则必须执行。

批处理系统的目标

• 平均周转时间短：周转时间是指从作业被提交给OS，到作业完成的时间，包括四部分：作业在外存后备队列等待调度的时间，在就绪队列等待进程调度的时间，在CPU上执行时间，进程等待I/O操作完成的时间。
  带权周转时间描述为作业周转时间T与系统为它提供服务的时间T_s之比，即W=T/T_s。
• 系统吞吐量高：吞吐量是单位时间系统完成作业数。
• 处理机利用率高。

分时系统的目标

• 响应时间快：响应时间是从用户通过键盘提交一个请求开始，到屏幕上显示出处理结果的时间间隔。包括三个部分：请求信息从输入到处理机的时间，处理机对其的处理时间，将响应信息送回显示器的时间。
• 均衡性：系统响应时间与用户请求复杂性匹配。

实时系统的目标

• 截止时间的保证：截止时间是指任务最迟执行时间或最迟完成时间。实时系统调度算法的主要目标是保证截止时间。对于HRT任务，截止时间必须保证，对于SRT任务，截止时间基本保证。
• 可预测性：请求可预测性，如电影的连续播放。若使用双缓冲，可对连续两帧并行处理，提高实时性。