操作系统-处理器调度

操作系统

CPU调度 概念

1
2
3
4
5
6
控制，协调 多个进程对CPU的竞争：
    即 按一定的调度算法从 就绪队列中 选择一个进程，把CPU使用权交给该进程
    如果没有就绪进程，系统会安排一个 系统空闲进程或idle进程

系统场景： 多个就绪进程，多个CPU
    决策 给哪个进程分配哪个CPU

调度要解决的问题

1
2
3
WHAT:   按什么原则选择下一个执行的进程 -- 调度算法
WHEN： 何时进行选择 -- 调度时机    
HOW:  如何让被选中的进程上CPU运行 -- 调度过程 （进程的上下文切换）
  • 调度时机
1
2
3
4
5
6
1.进程 正常终止 或  异常终止
2.新进程创建 或 等待进程变为就绪进程
3.一个进程从运行态进入阻塞态 
4.一个进程从运行态变为就绪态  (时钟中断： 时间片到了）

即： 内核对 中断/异常/系统调用 处理后返回用户态时， 重新调度
  • 调度过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
是一个进程让出处理器，由另外一个进程占用处理器的过程

包括工作： 
    切换全局页目录以加载一个新的地址空间
    切换内核栈和硬件上下文

切换过程包括了： 对原来运行进程各种状态的保存， 对新的进程各种状态的恢复

上下文切换开销： 
    直接开销： 内核完成切换花费的CPU时间
        保存和恢复寄存器
        切换地址空间（相关指令比较昂贵）
    间接开销：   
        高速缓存（Cache）， 缓冲区缓存（buffer cache）， TLB（translation lookup buffer） 失效
  • CPU调度算法

不同角度有不同的要求

调度算法不同角度的要求

1
2
3
4
5
6
7
调度算法衡量指标： 
    吞吐量： 单位时间完成的进程数量
    周转时间： 每个进程从提出请求到完成运行完成的时间
    响应时间： 从进程提出请求到第一次回应的时间
    其他： 
        CPU利用率： CPU有效工作的时间比率
        等待时间： 每个进程在 就绪队列中 等待的时间

调度算法 考虑的问题

1
2
3
4
5
6
进程控制块PCB： 
    需要记录哪些 与CPU调度相关的 信息
进程优先级 及 就绪队列的组织
抢占式调度 与 非抢占式调度
I/O密集型 与 CPU密集型 进程
时间片
  • 进程优先级
1
2
3
4
5
6
7
优先级，优先数： 
    优先数的大小 在不同操作系统中 表示的优先级高低不同 （可能数字小的高，也可能数字大的高）

静态优先级： 
    进程创建时指定，运行过程中不会改变
动态优先级： 
    运行过程中动态变化，如等待时间长的提升优先级
  • 进程就绪队列组织
1
2
3
4
按优先级排队：
    根据优先级进入不同的就绪队列
其他：     
    创建时进入最高级队列，时间片轮转，动态降低优先级
  • 抢占式 和 非抢占式
1
2
3
占用CPU的方式： 
    抢占式： 有比正在运行的进程 优先级更高的进程进入就绪队列时， 系统可强行剥夺CPU，提供给更高级进程
    不可抢占： 某一个进程被调度运行后，除非自身原因放弃CPU，不然能一直运行
  • I/O密集型 与 CPU密集型 进程
1
2
3
4
5
6
进程执行过程的行为划分：    
    I/O密集型： 频繁进行I/O，通常会花费很多时间等待 I/O 的完成  
        (占用CPU很短的时间就会让出CPU进入I/O等待，所以一般调度系统都会对I/O型进行偏好）
        
    CPU密集型（计算密集型）： 需要大量的CPU时间进行计算 
       （占用CPU时间长）
  • 时间片
1
2
3
4
5
6
7
8
一个时间段： 分配给调度到CPU上的进程，允许进程占用CPU运行的时间长度

如何选择时间片： 
    进程切换的开销
    对响应时间的要求
    就绪进程个数
    CPU能力
    进程的行为

批处理系统 中采用的 调度算法

1
2
3
4
5
6
7
8
9
10
11
12
13
先来先服务 （ FCFS  -- first come first serve ）
    先进先出， 非抢占式  （ 问题： 短的在长的后面 ，周转时间长）
最短作业优先（ SJF  -- shortest job first ）
    具有最短完成时间的进程优先执行， 非抢占式    （ 优化周转时间， 问题：长作业一直得不到执行，饥饿现象）
最短剩余时间优先 （ SRTN  --  shortest remaining time next ）
    变为抢占式，一个就绪进程比正在运行进程具有更短的完成时间，进行抢占 （ 优化周转时间 ）
最高响应比优先 （ HRRN  --  highest response ratio next ） 
    综合算法， 先计算进程响应比R， 选择R最高的进程进行执行
    R = 周转时间 / 处理时间  
      = （等待时间 + 处理时间）/ 处理时间 
      = 1 + （等待时间 / 处理时间）
    所以相同等待时间，处理时间越多，响应比越小。 即优先级低
    然后等待时间变大，响应比就会变大。 即优先级慢慢变高

交互式系统中的调度算法

  • 时间片轮转 （Round Robin）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
为短作业改善平均响应时间
解决思路：
    周期性切换
    每个进程分配一个时间片
    时钟中断 - 轮换
    
时间片分配问题： 
    太长： 降级为先来先服务， 延长了短作业的响应时间
    太短： 进程切换浪费CPU资源， 响应时间变长        
    设计为： CPU开销 进程切换 为 时间片 的1% 
    
优点： 公平，交互式计算，响应时间快
缺点： 进程切换，CPU花费较高。   对不同大小的进程有利，对相同大小的进程响应时间反而会高
  • 最高优先级调度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
系统进程 优先级 高于 用户进程
前台进程 优先级 高于 后台进程
操作系统 更偏好 I/O型进程

优先级 可以是静态不变的， 也可以是动态调整的。 （以 优先数 决定 优先级）
就绪队列按照 优先级 组织
实现简单： 不公平 （优先级低的进程 饥饿）

基于优先级的抢占式： 
    优先级反转问题： 
        一个低优先级进程 持有 高优先级进程需要的资源， 高优先级进程等待低优先级无法执行
    解决方案： 
        设置优先级上限
        优先级继承
        使用中断禁止

  • 多级反馈队列 调度算法 （feedback）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
unix 的一个分支 BSD 5.3版本采用的调用算法
考虑之前的算法之后的一个 择中权衡后的 综合调度算法

思路： 
    设置 多个 就绪队列， 第一级队列优先级最高
    给不同就绪队列中的进程分配不同的时间片，第一队列时间片最小； 随着队列优先级降低，时间片增大
    按优先级从高到低进行调度
    每个队列按 时间片轮转的方式 进行调度
    新创建进程就绪后进入 第一级队列
    进程用完时间片而放弃CPU，则进入下一级队列
    由于阻塞而放弃CPU的进程进入相应的等待队列，等待事件发生，进入原先队列 （队首还是队尾，时间片继续还是重新，可以看情况设计，反应对该类进程的偏好程度）
    
    若是抢占式的： 
        有更高优先级的进行就绪，可抢占CPU，原运行进程进入 原优先级队列

调度算法总结

多处理器调度算法设计考虑

1
2
3
4
5
不仅要选择哪个进程， 还有选择 在哪个处理器上执行
进程在多个CPU之间迁移的开销
    高速缓存实现，TLB失效
    尽可能 让进程在总在同一个CPU上执行
    考虑负载均衡问题 （使所有CPU保持均衡忙碌状态）

典型系统使用的调度算法

1
2
3
4
5
UNIX    动态优先数 算法
BSD5.3  多级反馈队列
LINUX   抢占式调度 (目前是 CFS 完全公平调度算法）
Windows 基于优先级的抢占式多任务调度
Solaris 综合调度算法

Windows 线程调度

1
2
3
4
5
6
7
调度单位是 线程
基于 动态优先级，抢占式调度，结合 时间配额的调整

就绪进程 按照 优先级进入相应队列
系统总是选择 优先级最高的就绪线程 运行
同一优先级的线程， 按时间片轮转进行调度
多CPU系统中， 允许多个线程并行运行

引发线程调度的条件

1
2
3
4
5
6
7
8
9
跟之前进程相同的4个条件
1.线程 正常终止 或  异常终止
2.新线程创建 或 等待线程变为就绪进程
3.一个线程从运行态进入阻塞态 
4.一个线程从运行态变为就绪态  (时钟中断： 时间片到了）

增加条件
5. 线程优先级改变
6. 线程改变了它的 亲和（affinity）处理机集合 - 线程只能在这几个处理机上执行，其他处理机即便空闲了该线程也不能执行

windows 使用 32 个线程优先级 - 分为 三类

1
2
3
4
5
6
1. 实时优先级 （ 31 - 16 ） 
    不会改变优先级
2. 可变优先级 （ 15 - 1 ）     
    优先级可在一定范围内 升高 或 降低。  （可区分  基本优先级 和 当前优先级 ）
3. 系统线程  （ 0 ）    
    零页线程： 用于对系统中空闲物理页面清零

线程的时间配额

1
2
3
4
5
6
一个配额单位的整数
线程用完时间配额后，如果没有相同优先级的其他线程， 系统将重新分配一个时间配额给该线程，让它继续运行

用法： 
    两个线程，CPU型，I/O型，  如果直接提高CPU型线程的优先级，则CPU型线程一直运行，I/O型得不到运行。而提高CPU型进程的时间配置，就可以了

线程调度策略

1
2
3
4
5
6
7
8
9
10
11
1. 主动切换
    线程等待事件，运行态 转为 阻塞态 。 系统调度新的线程运行
2. 抢占
    上面线程事件发生唤醒， 优先级高，抢占CPU， 被抢占线程退回就绪队列队首， 如果是实时优先级，重新分配时间配额，如果是可变优先级，分配剩余时间配额
3. 时间配额用完
    线程优先级没有降低
        同优先级就绪队列有其他线程，调度其他线程运行，该线程到队列队尾
        没有其他线程，分配新的时间配置，继续运行
    线程优先级降低了
        选择更高优先级线程执行

线程优先级提升 和 时间配额调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Windows调度策略
    如何体现对某类线程的倾向性 ？ 
    如何解决饥饿现象 ？
    如何改善 系统吞吐量，响应时间等整体特征？ 

1. 提升线程 优先级 ,针对可变优先级范围 （1-15）
   I/O操作完成  （临时提升，保证更快上CPU运行处理数据）（会把时间配额减1）
   信号量，事件等待结束
   前台进程中的线程， 完成一个等待操作
   窗口活动 唤醒窗口线程
   线程处于就绪态 并超过一定时间没有运行-饥饿  
        （ 系统线程 "平衡集管理器"， 扫描就绪队列，发现等待超300个时钟周期的饥饿线程， 优先级提升为最大的15，分配4倍的时间配额，线程运行完时间配额后，衰减回原来优先级）
    
2. 给线程分配一个很大的时间配额