(五)处理器调度

CPU调度

按一定的调度算法从就绪队列中选择一个进程，把CPU的使用权交给被选中的进程。其任务是控制、协调进程对CPU的竞争。

CPU调度要解决的三个问题

1. what：按什么原则选择下一个要执行的进程(调度算法)
   调度算法衡量指标：

• 吞吐量Throughput：每单位时间完成的进程数目
• 周转时间TT(Turnaround Time)：每个进程从提出请求到运行完成的时间
• 响应时间RT(Response Time)：从提出请求到第一次回应的时间
• CPU利用率(CPU Utilization)：CPU做有效工作的时间比例
• 等待时间(Waiting time)：每个进程在就绪队列中等待的时间

2. when：何时进行选择(调度时机)

• 进程正常终止 或 由于某种错误而终止
• 新进程创建 或 一个等待进程变成就绪
• 当一个进程从运行态进入阻塞态
• 当一个进程从运行态变为就绪态

3. how：如何让被选中的进程上CPU运行(调度过程，进程的上下文切换)
   进程切换：是指一个进程让出处理器，由另一个进程占用处理器的过程。主要包括两部分工作：

• 切换全局页目录以加载一个新的地址空间
• 切换内核栈和硬件上下文，其中硬件上下文包括了内核执行新进程需要的全部信息。
  切换过程包括了对原来运行进程各种状态的保存和对新的进程各种状态的恢复。

设计调度算法的要点

1. 需考虑数据结构，进程控制块PCB中，需要记录哪些与CPU调度有关的信息，设计相应的字段
2. 进程优先级及就绪队列的组织
   优先级表现了进程的重要性和紧迫性。优先数是一个数值，反映了某一个优先级。

• 静态优先级
  进程创建时指定，运行过程中不再改变
• 动态优先级
  进程创建时指定了一个优先级，运行过程中可以动态改变。如：等待时间较长的进程可提升其优先级

3. 抢占式调度与非抢占式调度

• 可抢占式(可剥夺式)
  当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用。
• 不可抢占式(不可剥夺式)
  某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去。

4. I/O密集型与CPU密集型进程

• I/O密集型或I/O型
  频繁的进行I/O，通常会花费很多时间等待I/O操作的完成。
• CPU密集型
  需要大量的CPU时间进行计算

5. 时间片
   指一个时间段，分配给调度上CPU的进程，确定了允许该进程运行的时间长度。

批处理系统的调度算法

1. 先来先服务FCFS-First Come First Server
   按照进程就绪的先后顺序使用CPU。使用一个队列就可以实现，新就绪的排在队尾。
   是非抢占的。

• 优点：公平 实现简单
• 缺点：长进程后面的短进程需要等很长时间，不利于用户体验。

FCFS举例

2. 最短作业优先SJF-Shortest Job First
   具有最短完成时间的进程优先执行。
   非抢占式。

• 优点：最短的平均周转时间(在所有进程同时可运行时)

• 缺点：不公平。源源不断的短任务到来，可能使长的任务长时间得不到运行，产生“饥饿”现象。

  
  SJF

3. 最短剩余时间优先SRTN-Shortest Remaining Time Next
   SJF抢占式版本。即当一个新就绪的进程比当前运行进程具有更短的完成时间时，系统抢占当前进程，选择新就绪的进程执行。
4. 最高响应比优先HRRN-Highest Response Ratio Next
   调度时，首先计算每个进程的响应比R，之后总是选择R最高的进程执行。

响应比计算的一种方式

交互式系统中采用的调度算法

1. 时间片轮转调度RR-Round Robin
   目标：为短任务改善平均响应时间
   解决问题的思路：周期性切换；每个进程分配一个时间片；时钟中断-->轮换。

• 优点：公平；有利于交互式计算，响应时间快；
• 缺点：由于进程切换，时间片轮转算法要花费较高的开销。(如果一个进程运行时间为10，时间片为1，则上下文切换次数要9次，开销较大)；RR对不同大小的进程是有利的，但对于相同大小的进程就不一定了。

image.png

2. 最高优先级调度HPF-Highest Priority First
   选择优先级最高的进程投入运行。

• 系统进程优先级 高于 用户进程
• 前台进程优先级 高于 后台进程
• 操作系统更偏好 I/O型进程

3. 多级反馈队列Multiple feedback queue
   是一个综合调度算法。
4. 最短进程优先Shortest Process Next

各种调度算法的比较

典型系统所采用的调度算法

1. UNIX 动态优先数法
2. 5.3BSD 多级反馈队列法
3. Linux 抢占式调度
4. Windows 基于优先级的抢占式多任务调度
5. Solaris 综合调度算法

线程的时间配额

时间配额不是一个时间长度值，而一个称为配额单位的整数。
一个线程用完了自己的时间配额时，如果没有其他相同优先级的线程，Windows将重新给该线程分配一个新的时间配额，让它继续运行。