CPU调度

CPU运行

最简单的CPU运行方式：单核，单个程序，取指执行，好大一部分MCU裸机程序。

单核CPU也想处理好几个问题，跳转执行。

提高CPU利用率的问题，让CPU做更多的有效运算，充分压榨CPU的能力，多线程。

多线程遇到的问题：跳转时候，切换，数据的问题。（中断现场保护。）

用户态和内核态的问题。

有了这个想法，就要去实现一下，内核里输出A和输出B两个程序。

Linus在搞0.11之前搞得是0.01，做的就是在屏幕上交替输出AB，再扩充扩充，就是个小系统了。

在MCU上，经典的操作系统入门实验是两个LED闪烁。

最上层的代码

// AB.c

int main()
{
    if(!fork())
    {
        wihie(1)
            printf("A");
    }
    if(!fork())
    {
        wihie(1)
            printf("B");
    }
}

如何实现的问题。两个线程的切换，相当于在切换的时候把CPU拍了个照，然后切换，换回来的时候，把这个照片再放在CPU上继续。

还有个最核心的，调度的问题。调度点。

CPU调度的含义

使用

需要进入内核，进入内核靠的是中断，使用时钟中断。

一些调度策略

实时性很强的，比如安装在导弹上的操作系统。

但是这里只是拿出一个点来说。

一些直观想法

FIFO：先来先执行，简单

Priority：优先

优先有个问题，任务段可以适当优先，但是不知道这个任务将来会执行多长时间。

进程调度方法也是一个很大话题

对于不同的方法，要考虑的一些东西：

• 周转时间：尽快结束任务

• 响应时间短：用户的操作尽快响应

• 吞吐量：系统内耗时间少

做调度，需要折中综合，

吞吐量和响应时间之间有矛盾。响应时间小会使得切换次数多、系统内耗大、吞吐量小。

前台任务和后台任务的关注点不同，前台任务关注响应时间、后台任务关注周转时间。

IO约束型任务和CPU约束型任务有各自的特点。CPU约束的意思是大部分时间在运算；IO约束是大多数在操作IO。IO约束很像是前台任务，比如鼠标键盘的输入要及时的表现在屏幕上。

折中综合让操作系统调度变得复杂，但有效的系统又要求尽量简单。调度算法毕竟是个算法，也是需要花费CPU时间的。

一些调度算法

FCFS(first come first service)：先来先服务。

SJF(shortest job first)：最短作业优先

实际情况下，有些作业时间是不知道的，而且任务不是在0时刻一起来的。因此实际使用的算法：

SRTF(shortest remaining time first)：最短剩余时间优先，每次新任务到达，选择当前剩余时间最短的执行。这是一种可抢占式的调度，不是任务自己让出CPU，只要有新任务就有可能抢占当前CPU。

此外，还有个问题是，如果比较长的作业时间又鼠标的输入，还得等前面完事了才会有响应，这是不行的。

因此，有了一个新的算法

RR(round-robin)：按照时间片来轮转调度。每个任务都能照顾到。

每个时间片10-100ms，切换时间0.1-1ms。

此外，word惯性响应时间，gcc关注周转时间，两类任务同时存在，要让两个都满意，一个直观想法：定义前台任务和后台任务，前台RR，后台SJF，定义前台优先级高于后台。

想法是好的，但是1973年关闭的MIT的IBM7094发现有个进程在1967年提交但是一直没运行。也出问题了。

因此后台任务优先级应该动态升高，但后台任务一旦执行，前台的响应时间又有问题了。如果前后台都用时间片，又退化成了RR了，又没有优先级的概念了。因此要在RR的基础上考虑到优先级和前后台。

此外还有许多其他问题：

gcc也是需要交互的，word也会执行批处理，SJF短作业优先如何体现？作业长度是未来的信息该如何判断？

因此，调度机制应该要能认出来这些东西。

一个schedule()的实现

一个实际的schedule()函数，导弹上的调度算法要实时调度，家用手持设备各方面比较均衡，这里主要考虑通用PC机，一个实际系统实现的把多个调度算法糅合在一起，考虑到各方面的一个调度方法。

Linux-0.11/kernel/sched.c

while (1) 
{
    c = -1;
    next = 0;
    i = NR_TASKS;
    p = &task[NR_TASKS];
    while (--i) {
        if (!*--p)
            continue;
        if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
            c = (*p)->counter, next = i;
    }
    if (c) break;
    for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
        if (*p)
            (*p)->counter = ((*p)->counter >> 1) +
                    (*p)->priority;
}

switch_to(next);

counter保证了响应时间的界，所以，代码里右移一位相当于除以2，是很有讲究的。

$c(\infty) = \sum_{n=1}^{\infty} \frac{p}{n} = 2p$

经过IO后，counter会变大，IO时间约上，counter越大，照顾了IO进程，变相照顾了前台进程

后台进程一直按照counter轮转，近似了SJF调度

每个进程只需要维护一个counter变量，简单、高效

这是个很强的实际工作的schedule函数。