2.2 CPU调度

1
2
我在年青时候也曾经做过许多梦，后来大半忘却了，但自己也并不以为可惜。
所谓回忆者，虽说可以使人欢欣，有时也不免使人寂寞，使精神的丝缕还牵着已逝的寂寞的时光，又有什么意味呢。

一 . 处理机调度概念、层次

image-20260401164042037

“调度”概念

假设一堆人需要服务，就需要有某种规则（先后，VIP等）来决定谁先谁后。

三个层次

image-20260401165206476

高级调度

  • 又称作业调度。

  • 按照某种规则，把作业从外存调入内存，并创建进程。

    • 每个作业只会调入一次，调出一次。作业调入时建立PCB，调出时撤销PCB。

image-20260401164400135

低级调度

  • 又称进程调度（处理机调度）
  • 按照某种算法进行 – 进程间的调度。
  • 进程调度的频率最高。

image-20260401164521825

中级调度

  • 又称内存调度。

  • 按照某种策略，把暂存到外存的、挂起状态 的进程，重新调回 内存。

    • 存在原因：内存不够时，一些进程的数据会被调出外存。
    • 一个进程可能会被多次调入调出，所以中级调度发生的频率比高级调度高。

image-20260401164736766

进程状态的补充

挂起态

  • 挂起态：暂时调到外存等待的进程的状态。

  • 有两种挂起态：就绪挂起和阻塞挂起

image-20260401165008693

回顾

image-20260401165311766

二 . 进程调度的时机，切换与过程，调度调度方式

image-20260401165411398

**进程调度的时机 **

​ –什么时候 需要进行进程调度？（当前运行的进程 主动或被动 放弃处理机时候）

​ –什么时候 不能进行进程调度？（中断，原子操作，进程在OS内核程序临界区）

image-20260401194503598

临界资源：一个时间段内只允许一个进程使用的资源。（所以各进程需要互斥地访问临界资源）。

临界区：访问临界资源的那段代码。

内核临界区一般是用来访问某种内核数据结构的（eg进程的就绪队列）

  • 进程处于操作系统内核临界区中，不能进行调度与切换。

  • VS对比：进程在普通临界区中是可以进行调度、切换的。

进程调度的方式

非抢占式：只允许进程主动放弃处理机。即即使有紧迫的任务，依旧不管，只执行现在的进程（till进程终止或主动进入阻塞态）。

  • 不可以处理紧迫任务。实现简单，开销小。适合早期的批处理系统。

抢占式：允许进程被动放弃处理机。有更紧迫的任务，新任务可以抢占当前的进程的处理机（BY OS），当前进程暂停。

  • 可以处理紧迫任务。适合分时操作系统，实时操作系统。

进程的切换与过程

狭义的 进程调度：只包括从就绪队列选出一个要运行的进程。（这个进程可以是当前的进程，也可以是别的进程 – 此时就需要进程切换。

广义的 进程调度：包括选一个进程和进程切换两个步骤。

进程切换的过程：

①对原来的进程进行数据保护

②对新进程进行数据恢复

  • 数据的保护和恢复都在PCB进行。

  • 进程调度和切换是有代价的，所以不是调度越频繁并发度越高。

回顾

image-20260401200302122

三 . 调度程序、闲逛进程

image-20260401202553950

调度程序

调度就绪态和运行态的进程的程序。

  • 需要调度算法（让谁运行）
  • 需要确定时间片大小（运行多久）

什么时候触发“调度程序”：

  • ①创建新进程
  • ②进程退出
  • ③运行的进程阻塞
  • ④IO中断发生（唤醒某些阻塞进程）

抢占式策略，每（k）个时钟中断都会触发调度程序工作。

非抢占式策略，运行进程阻塞或退出才触发调度程序工作。

注：

不支持内核级线程的OS，调度程序的处理对象是进程

支持内核级线程的OS，调度程序的处理对象是内核线程

闲逛进程idle

就绪队列没有别的进程的时候，调度程序就会调度闲逛进程工作。

优先级是最低的。

四 . 调度算法的评价指标

image-20260401203004520

CPU利用率

让CPU尽可能工作。

利用率 = 工作时间 / 总时间

系统吞吐量

单位时间完成作业的数量。

系统吞吐量 = 总共完成的作业数 / 总时间

周转时间

作业被提交给系统开始，到作业完成结束之间的时间。

周转时间 =

​ 作业在外存后备队列等待作业调度（高级调度）的时间 + （一次）

​ 进程在就绪队列上等待进程调度（低级调度）的时间 + （多次）

​ 进程在CPU上执行的时间 + （多次）

​ 进程等待IO操作的时间 （多次）

​

周转时间 = 作业完成时间 - 作业提交时间

平均周转时间 = 各个作业周转时间之和 / 作业数 （OS更关心的）

（周转时间并不能很好地代表时间，有的运行时间短，但是等待时间很长。所以提出了带权周转时间）

带权周转时间 = 作业周转时间 / 作业实际运行时间

等待时间

进程 / 作业 处于等待处理机状态时间的和。

进程等待时间 = 周转时间-运行时间-IO操作时间。 不包括等待IO完成的时间。

作业等待时间 = 作业在外存等待调度时间 + 进程等待时间。

（一个作业被CPU服务多久的，被IO设备服务多久一般是确定不变的，因此调度算法只会影响作业/进程的等待时间）

响应时间

用户提交请求到首次相应的时间。

回顾

image-20260401205128981

五 . 调度算法

image-20260401211532707

先来先服务FCFS

first come first serve

image-20260401214853733

image-20260401212401278

短作业优先SJF

shortest job first

image-20260401214003465

image-20260401213005195

image-20260401213422333

注：题目没提及，默认是非抢占式的。

  • 抢占式的短作业/进程优先调度算法的评价等待时间、平均周转时间最少。
  • 在所有进程几乎同时到达时，采用SJF调度算法的评价等待时间、平均周转时间最少。（题目选项没有别的很明显错误的话，只能选它了）

image-20260401214053251

高响应比优先HRRN

image-20260401214639111

image-20260401214540407

回顾

image-20260401214756669

image-20260401220828943

时间片轮转RR

image-20260401222500740

image-20260401222510511

image-20260401221928682

image-20260401221959446

image-20260401222126309

image-20260401222331247

优先级算法

image-20260401225036452

image-20260401222815510

image-20260401223025137

image-20260401223410991

多级反馈队列调度算法

image-20260401225838655

image-20260401225420493

image-20260401225509475

image-20260401225631237

回顾

image-20260401230112455