简介
就绪队列中有很多进程，应该选择执行哪一个进程。
1.FIFO（先来先执行）
2.其它优先级，如时间短的先执行
关心的：进程等待时间少。
指标
(1) 尽快结束
(2) 尽快响应
(3) 吞吐量高
这些指标之间存在矛盾（提升一个指标意味着降低另一个指标），所以我们需要考虑折中的方案，尽量照顾到每一个指标。
其中一个矛盾在于，如果想要尽快响应，那么就意味着切换的次数多。切换次数多，这中间就要花大量时间，那么吞吐量就小。
一般而言，对响应时间要求高的，往往是前台任务，因为它对应着与用户的交互。对于用户而言，我们总是希望得到尽可能快的响应。而对于后台任务而言，它执行的往往是一些用户看不见的CPU运算，所以对响应时间没有那么敏感。
基于这个特点，我们可以把任务分为IO约束型和CPU约束型。而这两类任务中，我们通常更倾向于优先执行IO约束型任务，因为大量的IO计算使得CPU有足够的空余时间可以执行CPU约束型任务，相当于CPU约束型任务可以“见缝插针”，这样就能实现并行执行任务，提升效率。反之，先执行CPU约束型任务，那么将会一直占用CPU，IO约束型任务难以插足。
常用调度思想
1.对于先来先执行，它的周转时间大，所以我们往往考虑短作业优先，这种情况下周转时间是最小的。
这相当于说，虽然总时间是一样的，但是我们还要考虑其它任务的等待时间。把短的任务排在前面，也就意味着总体的等待时间减少。
2.时间片轮转调度。分配时间片，不同时间片执行不同任务。这样就照顾了大部分任务，能够保证响应时间。
3.优先级调度：同时考虑响应时间、周转时间（结合前两者）
一个想法是，既然前台任务关注响应时间，而后台任务更关注周转时间，我们可以维护两个队列，一个是前台任务队列，另一个是后台任务队列。
对于前台任务而言，我们执行轮转调度。
对于后台任务而言，我们对短作业优先。
在这两个队列之间，前台任务优先级高于后台任务
这样的想法虽然很好，但是却存在一个非常严重的问题，也就是可能会产生饥饿现象。如果前台任务一直执行，因为优先级的关系，那么后台任务永远没有执行的机会，只能一直等待。
对于这样的问题，我们给出的解决方案是：
(1) 后台任务优先级动态升高
(2) 前后台任务都使用时间片
当然，很多时候，我们实际上是不知道任务究竟是前台任务还是后台任务的，因为用户并不会很明确的告诉你这一点。从另一个角度来看，前台任务有时也会有大量CPU计算，而后台任务可能会存在一定的IO操作，它们两者并没有非常清晰的界限。这也就意味着，我们有必要引入学习机制，让我们的程序根据任务的表现来确定这个任务的性质。
schedule函数
void Schedule(void)
{
whie(1) {
c = -1;
next = 0;
i = NR_TASKS;
p = &task[NR_TASKS];//把p设为最后一个任务的地址
while(--i) {//从后往前移动
//如果状态为就绪，并且counter>c
if((*p->state == TASK_RUNNING&& (*p)->counter > c)
//c就等于它
c = (*p)->counter, next = i;
}
//求得counter最大的进程
if(c) break;
//对counter进行修改
//对所有进程，令counter等于当前counter除以2加上counter初值。
//如果是就绪态进程，那么counter为0第一项也为0，counter实际上就等于它的初值
//如果是阻塞进程，counter折半再加上初值。阻塞->就绪大于就绪恢复counter
//执行过IO的进程回来后，counter一定会变大，优先级提升
for(p = &LAST_TASK;p>&FIRST_TASK;--p)
(*p)->counter = ((*p)->counter>> 1) + (*p)->priority;
}
//跳转到下一个
switch_to(next);
}
时钟中断：
void do_timer(..)
{
if((--current->counter>0)return;
current->counter= 0;
schedule();
}
_timer_interrupt:
…
call _do_timer
在这个代码中，我们实际上是在寻找counter最大的任务，作为下一个执行的任务。counter也就代表了任务的优先级，而这个优先级是可以变化的。
对于阻塞进程，c = c/2 + p，而对于非阻塞进程，c = p。
此外，可以通过简单的计算得到counter是收敛于2p的：
c(t) = c(t/2) + p
c(0) = p
c(正无穷 ) = p + p/2 + p/4 + 几何级数 <=2p响应时间有上界
可以看出，如果一个进程阻塞后再进入就绪状态，那么它的优先级会高于非阻塞的进程（初始优先级相同）。这是因为，发生阻塞代表着它执行了类IO的操作，说明它具有前台进程的特征，而前台进程是我们需要优先执行的。经过的IO时间越长，counter也会越大。
而后台任务也有秩序的按照counter轮转，这一方面，和轮转调度十分近似。
void sched_init(void) {
set_intr_gate(0x20,&timer_interrupt);
总而言之，我们得到算法的核心目标就是找到next，再跳转到next，它的核心是基于优先级的，也就是找到counter（时间片）大的。
它实现的基础为：
1.基于counter的优先级调度
2.基于counter时间片的轮转
两者使用的是一个变量。