调度
我个人一直都觉得调度是操作系统做重要的一环。
调度优化策略
这里主要从响应时间和吞吐量两个角度来衡量。
这里说多一点：
对于不同的系统，不同的任务，这两者都会有优先级上的不同。
比如计算任务，有些是 I/O 密集型，那么它的瓶颈就主要在吞吐量上。有些是在计算性能上，那么合理的并行调度就更加重要。
调度策略
大部分操作系统的课程和书都会介绍这些。
FCFS (first come,first serve)
Robin Robin(RR)
这里说了一个未来一直会伴随开发的问题，上下文切换是需要代价的，频繁的上下文切换会导致性能下降。
优先级调度
主要问题有两个：
- 完全按照优先级调度，那么低优先级任务存在饥饿情况。
- 对于优先级反转，可能存在低优先级任务持有锁，高优先级任务申请锁的问题。解决办法：Priority donation
Lottery Scheduling
** 对于不同的场景，不同的算法得到的结果也是不同的。因此算法和场景的匹配度可能更加重要。（这也是 ai 落地里非常重要的一环）
STRF（Shortest Remaining Time First）：
STRF 是一个比较优秀的算法。
但是也必须看到其缺点：
- 如果有大量的任务，会存在饥饿现象。大任务无法调度。
- 任务执行时间预测，如何给，给的对不对都存在问题。
多级反馈调度
针对这种设计，可以加入诸如 printf 的语句增加 i/o 请求，提升自己调度的优先级。（有点东西😄）
Linux 调度实例
Linux O(1)
看上去着实有点乱，先理解 Linux 调度有实时和非实时的区别吧。（暂时也没功夫读源码，有空读源码的话，也会优先去扫 TVM）
Linux CFS
CFS 的理念和 Lottery Scheduling 相似。每个任务都会分到时间片。
去掉了 O(1) 计算 sleep 时间和各种启发示的动态调整方法。
CFS 中优先级实时性要求高的任务，会增加其占用的时间片。具体方法：
还是有点抽象。
有兴趣的去读https://www.jianshu.com/p/673c9e4817a8cfs，这篇理解.
Linux RTS
对实时调度来说，性能虽然重要，但是可预测性更加重要。
EDF（Earliest Deadline First）
多说一句，leetcode 里是有 EDF 和 STRF 的题目的。
L10 总结：
PS：2020 春的第一次期中考试平均分 47.8。。。怪不得号称 UCB CS 本科最难的课，没有之一。
调度总结：
也必须看到当 CPU 到达一定的利用率后，性能会呈现指数级的下降。这和队列有很大的关系。
因此超高的 CPU 利用率不等同于高效的性能。（我个人理解这里不仅是 CPU，包括缓存，内存，I/O 在极限条件下不仅稳定性会下降，性能可能也会下降）
饥饿和死锁
说到调度一定绕不过饥饿和死锁。si
饥饿只是得不到调度，但是是有可能结束的。死锁在没有外部干预的情况下那是真的 game over 了。
死锁示例
Thread 申请资源的时候如果不注意的话很容易出现死锁：
内存申请死锁示例：
这里使用虚存也可以避免死锁。
哲学家问题
死锁的必要条件
死锁检测
资源分配图
例子不错，不是所有的资源环路都会造成死锁，如最后一个例子。由于 T2 可以先结束，T2 申请的 R1 资源可以释放，所以 T1 也可以执行。所以不会造成死锁。
使用的算法：
解决死锁的方法：
现代操作系统很多情况下遇到死锁，还是只有 “重启” 一种解决方法，使用所谓的 “鸵鸟算法”
死锁 preventing
- 无限资源。如虚拟内存，假设无限磁盘。
- 不使用共享资源，这个不现实。
- 不允许等待。如：电话忙音，禁止接入。常用于网络，如果连接失败，通知发起方进行重连。
- 同时申请所有需要的资源
- 按规则顺序申请资源
这里有两个例子供参考：
释放资源的顺序不会影响执行。
死锁恢复
回滚是常用的方法，在数据库的实现中经常使用。
死锁 avoiding
这个方案是不行的。
死锁的对应的状态有：1.安全状态 2.不安全状态 3.死锁状态
不安全状态会不可避免的进入死锁状态，因此该算法修改为：
银行家算法
给个中文链接吧。
https://blog.csdn.net/qq_36260974/article/details/84404369
优先级翻转
利用 Priority donate 的方法提升优先级。
调度相关概念数量中等，涉及的算法比较多。
