哈工大李治军老师操作系统笔记【13】：一个实际的schedule函数（Learning OS Concepts By Coding Them !）

0 回顾

• 实际的schedule是多种基本算法的融合，综合考虑各种情况，但也要求算法本身尽可能的简单

---

---

• 总之就是要找到一个next，这个schedule()函数再加上switch_to(next)函数，整个操作系统核心的多进程拨转的样子就有了

1 linux0.11的schedule()

---

---

• p=&task [NR TASKS];，PCB作为数组，这个放在数组的末尾
• 放在数组的末尾，然后从后往前移动while(--i)
• 并且每次进行状态的判断*p->state = TASK RUNNING
• 发现如果是就绪的并且(*p)->counter > c，然后c = (*p)->counter, next = i;
• 这样循环一遍，做了些什么事？
• 求最大的counter（时间片），每次调度给最大counter的那个进程，然后跳出去，switch_to
• 这就是典型的优先级算法
• 所以这就是既用了counter时间片轮转的，又基于counter优先级的
• counter怎么修改？
• 就是c都是为0的，所有就绪态进程的时间片都用完了，非就绪态执行IO阻塞了
• 所以当所有就绪态进程的时间片都用完了，counter = 0了，就执行for(p=&LAST TASK;P>&FIRST_TASK;--P) { (*p)->counter = ((*p)->counter >> 1) + (*p)->priority; }

1. 当不存在就绪态进程后，c=-1，执行for循环，那个移位操作就是除以2
2. for循环，使就绪态进程（counter = 0）= priority，而阻塞态进程counter > priority，所以当阻塞态进程变成就绪态，这个阻塞态进程的优先级肯定更大
3. 当阻塞态就绪后，将会立即获得高优先级
4. counter的两个作用，第一个是时间片；第二个是优先级

sched.c 是内核中有关任务调度函数的程序，其中包括有关调度的基本函数(sleep_on、 wakeup、schedule 等)以及一些简单的系统调用函数（比如 getpid()）。另外 Linus 为了编程的方便，考虑到软盘驱动器程序定时的需要，也将操作软盘的几个函数放到了这里。这几个基本函数的代码虽然不长，但有些抽象，比较难以理解。这里仅对调度函数 schedule()作一些说明。schedule()函数首先对所有任务（进程）进行检测，唤醒任何一个已经得到信号的任务。

具体方法是针对任务数组中的每个任务，检查其报警定时值 alarm。如果任务的 alarm 时间已经过期(alarm

随后是调度函数的核心处理部分。这部分代码根据进程的时间片和优先权调度机制，来选择随后要执行的任务。它首先循环检查任务数组中的所有任务，根据每个就绪态任务剩余执行时间的值 counter，选取该值最大的一个任务，并利用 switch_to()函数切换到该任务。若所有就绪态任务的该值都等于零，表示此刻所有任务的时间片都已经运行完，于是就根据任务的优先权值 priority，重置每个任务的运行时间片值 counter，再重新执行循环检查所有任务的执行时间片值。

另一个值得一提的函数是 sleep_on()，该函数虽然很短，却要比schedule()函数难理解。这里用图示的方法加以解释。简单地说， sleep_on()函数的主要功能是当一个进程（或任务）所请求的资源正忙或不在内存中时暂时切换出去，放在等待队列中等待一段时间。当切换回来后再继续运行。放入等待队列的方式是利用了函数中的 tmp 指针作为各个正在等待任务的联系。函数中共牵涉到对三个任务指针操作： *p、 tmp 和 current， *p 是等待队列头指针，如文件系统内存i 节点的 i_wait 指针、内存缓冲操作中的 buffer_wait 指针等； tmp 是临时指针； current 是当前任务指针。对于这些指针在内存中的变化情况我们可以用下面的示意图说明。图中的长条表示内存字节序列。

void schedule(void)
{
    int i,next,c;
    struct task_struct ** p;    // 任务结构指针的指针。

/* 检测 alarm（进程的报警定时值），唤醒任何已得到信号的可中断任务 */
// 从任务数组中最后一个任务开始检测 alarm。
    for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
        if (*p) {
// 如果任务的 alarm 时间已经过期(alarm
// jiffies 是系统从开机开始算起的滴答数（10ms/滴答）。定义在 sched.h 第 139 行。
            if ((*p)->alarm && (*p)->alarm < jiffies) {
                    (*p)->signal |= (1<<(SIGALRM-1));
                    (*p)->alarm = 0;
                }
// 如果信号位图中除被阻塞的信号外还有其它信号，并且任务处于可中断状态，则置任务为就绪状态。
 // 其中'~(_BLOCKABLE & (*p)->blocked)'用于忽略被阻塞的信号，但 SIGKILL 和 SIGSTOP 不能被阻塞。
            if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
            (*p)->state==TASK_INTERRUPTIBLE)
                (*p)->state=TASK_RUNNING;    //置为就绪（可执行）状态。
        }

/* 这里是调度程序的主要部分 */
    while (1) {
        c = -1;
        next = 0;
        i = NR_TASKS;
        p = &task[NR_TASKS];
// 这段代码也是从任务数组的最后一个任务开始循环处理，并跳过不含任务的数组槽。比较每个就绪
// 状态任务的 counter（任务运行时间的递减滴答计数）值，哪一个值大，运行时间还不长，next 就
// 指向哪个的任务号。
        while (--i) {
            if (!*--p)
                continue;
            if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
                c = (*p)->counter, next = i;
        }
        // 如果比较得出有 counter 值大于 0 的结果，则退出 124 行开始的循环，执行任务切换（141 行）。
        if (c) break;
// 否则就根据每个任务的优先权值，更新每一个任务的 counter 值，然后回到 125 行重新比较。
// counter 值的计算方式为 counter = counter /2 + priority。[右边 counter=0??]
        for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
            if (*p)
                (*p)->counter = ((*p)->counter >> 1) +
                        (*p)->priority;
    }
    switch_to(next);    // 切换到任务号为 next 的任务，并运行之。
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

1.1 counter的作用

• counter的作用：时间片
• 在时钟中断的时候，会让当前进程的counter–，如果当前进程的counter减到了0，就调用schedule()，典型的时间片轮转
• 因为还有找counter最大的进行调度，这就是典型的找优先级的任务，所以counter的另一个作用：优先级（这个优先级还会进行动态调整，比如之前阻塞的IO的优先级会升高，另IO时间越长，将来优先级升高的可能性越大）（即counter是所有对于那些未执行的任务来说是一直增加的，而只有运行的任务的counter才会减少）（所以经过IO（前台进程）的进程肯定会比只执行CPU（后台进程）的进程优先级高）

综上，首先是找到所有就绪态任务的最大counter，大于零则切过去，否则更新所有任务的counter，即右移一位（移位操作，右移一位是除以2）再加priority，然后进入下一次的找最大counter大于零则切否则更新counter，所以说那些没在就绪态的counter就一直在更新，数学证明出等的时间越长counter越大，等他们变成就绪态了，由于counter大，也就可以优先切过去了

• schedule中，next找的是counter最大的就绪任务，所以counter同时也代表了优先级
• 如果所有就绪任务的counter都等于0，就会重置所有任务的counter，包括非就绪的任务
  • 就绪任务的counter=0，所以重置以后，counter = priority
  • 非就绪任务的counter一般都是>0，所以重置以后，priority
  • 每个任务的priority是不一样的，不同任务的priority应该怎么设置比较合理？
  • 如果一个任务长期进行IO，那么在它的生命周期中，可能会经历多次counter重置，counter会越来越大，无穷接近于2*priority，所以这就达到了IO任务动态升高优先级的效果

---

---

2 总结

---

• 经过IO，counter就会变大，优先级就会变大，所以照顾了前台进程

---

---

• 每个进程最长时间片是2P，所以刚刚的移位除以2是很有讲究的
• 除以3,4都是可以的，但是代码除2写的很漂亮，并且执行起来快