FCFS

谁先来,谁先被CPU调度,不存在抢占
优势:简单
弊端:如果是长作业,需要等待很长时间,其他进程才能分配到CPU资源

SJF

谁的进程时间短,谁先被调度,不存在抢占
优势:整体等待的时间缩短了
弊端:当长时间的进程先到达时,后面的进程需要等待

STCF

谁先完成,谁先被调度,存在抢占
优势:后面来的进程可以抢占前面的进程时间,CPU先调度完成时间短的,再切回去调度完成时间长的
弊端:响应时间太长了(响应时间指的是从用户发出请求到首次产生响应所用时),长作业一直无法获得资源

单处理器分时调度

基本假设
进程是while(1) do_sth()的循环

  • 执行计算,使用CPU
  • 等待I/O返回,不适用CPU(通常时间较长)

随时可能有新的进程被创建/旧的进程退出

上下文切换

CPU通过分配时间片来执行任务,当一个任务的时间片用完,就会切换到另一个任务。在切换之前会保存上一个任务的状态,当下次再切换到该任务,就会加载这个状态。

  • 切出: 一个线程被剥夺处理器的使用权而被暂停运行
  • 切入: 一个线程被系统选中占用处理器开始或继续运行

RR轮转法

将系统中所有的就绪进程按照FCFS原则,排成一个队列。每次调度时将CPU分派给队首进程,让其执行一个时间片。在一个时间片结束时,发生时钟中断。调度程序据此暂停当前进程的执行,将其送到就绪队列的末尾,并通过上下文切换执行当前的队首进程。进程可以未使用完一个时间片,就出让CPU(如阻塞)。假设每个时间片1ms1s内多个进程是并行的。

看似很公平,确实也还行,可这样一定好吗?打个比方,系统里10个进程,其中绝大多数是一个死循环a.out,有一个有用的vi,但是排在最后,所以我们得等所有的a.out用完时间片,才能轮到vi

策略:引入优先级

何为nice
进程nice值,他对别的进程好的程度,如果越nice,越不会抢占CPU,所以nice值越高,优先级越低,能得到CPU的调度的时间越少

nice
nice

其中PRI代表优先级,初始值为80 (0~140),越高优先级越低;NI代表nice(-20~19)
renice
renice

ps -a发现进程中有两个test,分别对应PID1544、1545,初始的nice值为0,使用renice -n分别修改其对应的nice值,由于两个test位于两个处理器上执行,所以CPU的获得情况基本相当,我们可以用taskset -p把进程绑定CPU上
taskset
taskset

由于nice值相差了10,CPU的使用情况也发生了很大变化
屏幕截图 2021-06-28 174852.jpg
屏幕截图 2021-06-28 174852.jpg

策略:多级反馈

假设系统里有两种进程

  • 交互进程(vi、vscode...)大部分时候在等待,优先调度它们能够提高用户体验,减少卡顿(RR)
  • 计算进程(gcc、ld...)在处理器空闲时才执行

设置若干RR队列,每个队列对应一个优先级

  • 优先调度高优先级队列
  • 用完时间片(被中断)
  • 主动让出CPU等待I/O

允许优先级动态调整,因为进程创建之初,优先级是最高的,由于我们不知道它是计算密集型或是I/O密集型,如果是需要交互的进程,赋予高优先级;计算则调低它的优先级

能适应多CPU的多级反馈队列调度

全局队列:操作系统维护一个全局的任务队列,当系统中只有一个CPU核心空闲时,操作系统就从全局任务等待队列中选取就绪任务开始在此核心上执行,CPU核心利用率较高
局部队列:操作系统为每个CPU内核维护一个局部的任务等待队列,当系统中只有一个CPU内核空闲时,便从该核心的任务等待队列中选取恰当的任务执行,基本无需在多个CPU核心间切换,有利于提高CPU核心局部Cache命中率