操作系统（四）处理机调度

处理机调度的层次

1. 高级调度(High Level Scheduling)：长程调度或作业调度，对象是作业。主要用于多道批处理系统，在分时系统和实时系统中不设置高级调度。（几分钟一次）
2. 中级调度(Intermediate Scheduling) 内存调度，就是存储器管理中的对换功能提高内存利用率和系统吞吐率。
   3 . 低级调度(Low Level Scheduling) 进程调度或短程调度，对象是进程。是最基本的一种调度，三种OS中都必须配置此种调度。（10-100ms一次）

进程调度方式

• 不可剥夺方式
  不可剥夺方式也被称为非抢占方式。采用这种调度方式时，一旦把处理机分配给某个进程，该进程将一直执行下去，直到运行完毕或因某种原因不能运行，才把处理机分配给其它进程，决不允许其它进程强占正在运行进程占有的处理机。
• 可剥夺方式
  可剥夺方式也被称为抢占方式。在这种方式下，允许一个进程按照某种原则，抢占其它进程占有的处理机。抢占采用优先权原则的比较多，也就是说，如果一个进程比正在运行进程的优先级高，则它可以抢占处理机而运行。
  抢占主要原则： 优先权原则、 短进程优先原则 、 时间片原则
• 进程调度时机:进程退出 、进程阻塞、新进程创建、中断发生、时钟中断

处理机调度算法的目标

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

  • 资源利用率 ：$CPU利用率=\frac{CPU有效工作时间} {CPU有效工作时间+等待时间}$CPU利用率=CPU有效工作时间+等待时间CPU有效工作时间​
  • 公平性：使诸进程都获得合理的CPU 时间
  • 平衡性：使系统中的CPU和各种外部设备都能经常处于忙碌状态
  • 策略强制执行 ：必须予以准确地执行

• 批处理系统的目标

  • 平均周转时间短：
    周转时间包括：外存上等待时间，进程在就绪队列上等待时间，CPU上执行时间，等待I/O时间
    平均周转时间:$\frac{1}{n}\sum\limits_{i=1}^{n}T$n1​i=1∑n​T
  • 带权周转时间 $\frac{1}{n}\sum\limits_{i=1}^{n}\frac{T}{T_s}，T_s$n1​i=1∑n​Ts​T​，Ts​：CPU提供服务的时间
  • 系统吞吐量高
  • 处理机利用率高

• 分时系统的目标

  • 响应时间快
  • 均衡性

• 实时系统的目标

  • 截止时间的保证
  • 可预测性

作业

• 作业(Job)： 批处理系统中，任务是以作业为单位从外存调入内存的。
• 作业步(Job Step)： 在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤得到结果。
• 作业控制块(Job Control Block，JCB)
• 三个阶段： （1）收容 （2）运行 （3）完成
• 作业状态：(1) 后备状态　　(2) 运行状态　　(3) 完成状态
• 多道程序度（Degree of Multiprogramming)：即允许多少个作业同时在内存中运行

作业调度算法

• 先来先服务(first-come first-served，FCFS)调度算法
• 短作业优先(short job first，SJF)的调度算法
• 优先级调度算法(priority-scheduling algorithm，PSA)
• 高响应比优先调度算法(Highest Response Ratio Next，HRRN)
  优先权 = $\frac{等待时间+要求服务时间}{要求服务时间}$要求服务时间等待时间+要求服务时间​

进程调度

• 轮转调度算法：时间片大小的确定
• 优先级调度算法：静态优先级、动态优先级
• 多队列调度算法：
• 多级反馈队列(multileved feedback queue)调度算法
  

实时调度

• 最早截止时间优先EDF(Earliest Deadline First)算法
• 最低松弛度优先LLF(Least Laxity First)算法：根据的是任务的紧急(或松弛)程度。任务紧急程度愈高，赋予该任务的优先级就愈高，以使之优先执行
  假如在一个实时系统中有两个周期性实时任务A和B，任务A要求每20 ms执行一次，执行时间为10 ms，任务B要求每50 ms执行一次，执行时间为25 ms。
  
• 问题：优先级倒置，高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞。
• 优先级倒置的解决方法：采用动态优先级继承，共享临界资源时，占有资源的低优先级进程
  继承等待资源的高优先级进程的优先级。