linux-0.11中的调度函数

一、程序

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, pnext = *p;
}
if (c) break;
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p)
(*p)->counter = ((*p)->counter >> 1) +
(*p)->priority;
}
switch_to(next);

二、作用

while (--i)

从任务数组最后开始遍历。

if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
c = (*p)->counter, next = i, pnext = *p;

TASK_RUNNING表示就绪态,counter为时间片,上述两行程序用于寻找所有就绪任务中时间片最大的任务。**counter又表示了进程的优先级**。

if (c) break;

如果找到了,退出while循环,并switch_to(next)

for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p)
(*p)->counter = ((*p)->counter >> 1) +
(*p)->priority;

如果没有找到下一个任务,则调整每个任务的时间片:当前任务时间片除2,再加基本时间片长度。若就绪态任务时间片为0,重新初始化为priority;非就绪态即IO程序的时间片会更高。

  • 当有新任务时,整个调度程序会优先调度之前的任务,因为每次未被调度的任务都会增加counter,IO时间越长,counter越高,优先级越大
  • 假设一个任务一直没有被调度,counter最高也就$2p$

$$
c(0)=p,
c(t)=c(t-1)/2+p
\Rightarrow c(\infty)=p+2/p+4/p+…\le2p
$$