操作系统3：CPU调度别再闹了

用“主要业务逻辑”做在哪里来区分。

schedule:调度。scheduler是具有重业务逻辑的，也就是调度算法。例如，linuxkernel从中断出来后，会切入到schedulerroutine，因为这里面的逻辑很多（CFS，RR，FIFO等调度算法），所以叫做调度。

dispatch:分发、派发。dispatcher是轻业务逻辑或者没有业务逻辑，纯粹简单的转发、派发。例如，负载均衡的dispatcher收到请求后，通过哈希表找到responseserver，直接将请求派发下去，本身并不做业务逻辑。

有的操作系统scheduler和dispatcher是分开的，有的是合二为一的，例如后面要讲的linux版本中就是

调度器调度的时机举例：

非抢占式：进程自愿交出CPU资源引起的调度

分配延时应该尽可能减少

两种策略对比：

但是也不是完全不能预估，只不过就是要基于概率模型了，也就是有预估错误的可能性：

HRN是大于等于1的，基准值是1

在PCB中加一个优先数

可以使用堆来每次获得优先级最高的进程

优先权法的一个问题：

举一个例子：

如何设计一个多层反馈队列：

希望调度要很及时，但是不同任务的及时性的要求是不一样的

但是这一点是很难的，特别是通用性的操作系统，几乎不可能实现及时性（因为不同的进程要求不一样，用统一的调度方法当然不可能完全合适）

要设计评估方法，尽量在早期就能对调度算法进行评估，不能依赖实际测试（因为开发周期长），所以下图中的第三种方案一般不靠谱。由于实际情况是非常复杂的，要确定和理论计算非常难，所以确定模型法也一般不靠谱

这种方法的效果还是不错的，理论难度也比较低，是一种偏工程性的方法

内存空间有4G，其中3G是用户空间，1G是内核空间

这是Linux较为早期时候的调度算法

prev指向调度前的进程的PCB，next是将要调度给的进程的PCB，p是一个中间变量

tmp:用于优化用，没有实际含义

this_cpu:当前进程使用的是哪个CPU

c：临时变量，保存进程的优先权

轮转法：

default处理其他状态的情况，从就绪队列中删除，不再继续执行

TASK_INTERRUPTABLE这个是怎么回事呢？它是为了处理这样一种特殊情况：

看算法，就是一次遍历

recalculate:

>>1表示右移一位，也就是除2

由此可见，schedule函数其实还做了dispatch的工作

什么是实时进程


out是什么呢：

mm是进程中管理内存的数据结构

但是有更好的：

创建一个链表数组，数组的每个位置代表一个优先级，就绪状态的进程直接挂到数组的对应位置上。然后设置一个字节，表示当前有进程的最高的优先级是多少，这样调度的时候直接去找就好了。这种方法的复杂度是O(1)的

但是这其实也不是十全十美的，例如它还有公平性的问题：有的应用程序可以开多进程从而有较大的可能性被调度执行，之后版本的Linux在此有了优化