小林coding 《图解系统：调度算法》笔记

参考：

geeksforgeeks: CPU Scheduling in Operating Systems

uic：CPU Scheduling

进程调度

TIP

我知道很多人会问，线程不是操作系统的调度单位吗？为什么这里参与调度的是进程？

先提前说明，这里的进程指只有主线程的进程，所以调度主线程就等于调度了整个进程。

那为什么干脆不直接取名线程调度？主要是操作系统相关书籍，都是用进程调度这个名字，所以我也沿用了这个名字。

如果硬件时钟提供某个频率的周期性中断，那么可以根据如何处理时钟中断 ，把调度算法分为两类：

• 非抢占式调度算法挑选一个进程，然后让该进程运行直到被阻塞，或者直到该进程退出，才会调用另外一个进程，也就是说不会理时钟中断这个事情。
• 抢占式调度算法挑选一个进程，然后让该进程只运行某段时间，如果在该时段结束时，该进程仍然在运行时，则会把它挂起，接着调度程序从就绪队列挑选另外一个进程。这种抢占式调度处理，需要在时间间隔的末端发生时钟中断，以便把 CPU 控制返回给调度程序进行调度，也就是常说的时间片机制。

 什么时候会发生 CPU 调度呢？

1.非抢占式调度（红色箭头）：必须选择一个新进程

• 从运行状态到结束状态。
• 从运行状态到阻塞状态。例如针对 I/O 请求或调用 wait() 系统调用。

2.抢占式调度（黄色箭头）

• 从运行状态到就绪状态。例如时间片用完（响应时钟中断）
• 从阻塞状态到就绪状态。例如 I/O 完成或从 wait() 返回时。

调度原则 

• CPU 利用率 高：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率；
• 系统吞吐量 大：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；
• 周转时间 短：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好；
• 等待时间 短：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；
• 响应时间 短：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

非抢占式：

1. 先来先服务（First Come First Severd, FCFS）：每次从就绪队列选择最先进入队列的进程来运行。利于长作业，不利于短作业。
2. 最短作业优先（Shortest Job First, SJF ）：每次从就绪队列选择运行时间最短的进程来运行。这显然对长作业不利，很容易造成一种极端现象：长作业长期不会被运行。
3. 高响应比优先 （Highest Response Ratio Next, HRRN）：选择响应比最高的：（已等待的时间+服务时间）/服务时间
   • 等待时间相同：服务时间越短越容易被调度。短作业容易被选中
   • 服务时间相同：已等待时间越长越容易被调度。这样不至于使长作业等待时间过长。

抢占式：

最高优先级（Highest Priority First，HPF）

从就绪队列中选择最高优先级的进程进行运行

进程的优先级可以分为，静态优先级或动态优先级：

• 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
• 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级。

两种处理优先级高的方法，非抢占式和抢占式：

• 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，或当前进程发生阻塞。再选择优先级高的进程。
• 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。

时间片轮转（Round Robin, RR）

每个进程被分配一个固定的时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。

• 如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配另外一个进程；
• 如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换；

另外，时间片的长度就是一个很关键的点：

• 如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率；
• 如果设得太长又可能引起对短作业进程的响应时间变长。

通常时间片设为 20ms~50ms 通常是一个比较合理的折中值。

多级反馈队列（Multilevel Feedback Queue）

• 设置了多个队列，赋予每个队列不同的优先级，同时优先级越高时间片越短（新进程进入的第一级，优先级最高，时间片最短）；
• 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾（时间片更长），以此类推，直至完成；
• 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；

可以发现，对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也会更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。

Linux 调度 - （Completely Fair Scheduler - CFS） 

旧版 Linux 2.6 内核中使用的之前的 O(1) 调度。 CFS 在 Linux 内核 2.6.23（2007 年 10 月）版本之后，并且是 SCHED_NORMAL 类任务的默认调度程序

cfs定义了一种新调度模型，它给cfs_rq（cfs的run queue）中的每一个进程都设置一个虚拟时钟-virtual runtime(vruntime)。如果一个进程得以执行，随着执行时间的不断增长，其vruntime也将不断增大，没有得到执行的进程vruntime将保持不变。
而调度器将会选择最小的vruntime那个进程来执行（红黑树）。这就是所谓的“完全公平”。不同优先级的进程其vruntime增长速度不同，优先级高的进程vruntime增长得慢，所以它可能得到更多的运行机会。

线程的权重即该线程 用户设置的静态优先级。权重比是nice 0 的权重和线程权重的比值，nice 0即为系统默认的线程权限，该权重默认为1024。

。。。。。待完成