对于Linux0.11内核版本调度与睡眠机制的一些见解
主流开源系统调度机制对比笔记
——谭佳棋
系统调度主要包含的无外乎如下几个方面：
1.系统滴答时钟中断
2.任务调度及任务切换
3.睡眠或延时
接下来我们来看看Linux内核0.11版本，小编我这里参考的是赵炯的《Linux内核完全注释》
System_call.s
这里Linux的时钟中断函数_timer_interrupt是在System_call.s中定义的，它所完成的工作如下：
(1)ds/es/fs/edx/ecx/ebx/eax依次入栈保存，置ds/es指向内核数据段，而fs指向局部数据段.
(2)全局时钟计数变量_jiffies计数值加1.
(3)发送指令使中断控制芯片结束硬件中断，即关闭中断源.
(4)从cs段寄存器中取出特权级RPL信息，并压栈作为参数传递给Sched.c中的_do_timer函数.
(5)跳过初始压入的RPL信息，跳转至ret_from_sys_call，执行系统调用返回后处理
(6)在系统调用返回处理函数中，判断当前任务若是任务0，或不是用户任务则直接弹出入栈信息并做中断返回处理，否则，还要根据信号位图和信号屏蔽码取出最小(优)信号值，先复位该信号位，再将该值加1后压栈作为参数，传递给_do_signal函数处理，之后再弹出入栈信息并做中断返回处理。
Sched.c
Linux的任务调度函数schedule在Sched.c中定义，这似乎合情合理，而它所完成的工作如下：
(1)搜索所有有效任务中，Alarm超时的任务，置其SIGALRM信号位，并复位其Alarm值。同时搜索所有已经接收到非屏蔽信号（或SIGKILL/SIGSTOP），且处于可中断状态的任务，将这些任务置为就绪态。
(2)在While(1)循环中搜索所有有效的就绪任务中，counter值最大的一个任务，并保存其索引值在next变量中，继而切换至该任务，若此时没有一个就绪的任务，则c值为-1，next值为0，将切换到任务0，若此时所有搜到的就绪任务的counter值均为0，则刷新所有任务的counter，这里注意刷新的不仅仅只是就绪任务的counter。
(3)通过调用switch_to执行任务切换操作。
Linux的不可中断睡眠函数sleep_on在Sched.c中定义，这里小编我先引述一篇****上的博文：
http://m.blog.****.net/fukai555/article/details/42169885
小编我这里先不评论上面这篇博文的观点，我先讲述一下自己对这段代码的理解：
(1)若传入的睡眠队列头指针参数无效则直接返回，若当前需要睡眠的任务是初始任务0，则直接当机。
(2)函数中定义临时任务结构指针变量tmp，由于sleep_on函数在当前任务的进程中被调用，因此，该tmp变量则被定义到了当前任务的局部数据段上，将原睡眠队列头指向的地址信息保存在该tmp变量中，然后将睡眠队列头重新指向当前任务，即在头部插入。
(3)置当前任务状态为不可中断状态，并重新触发调度，由于退出了就绪态，根据前面关于调度函数的分析，这个任务也就暂时放弃了执行权，因为只有就绪态的任务才有资格在schedule的循环中参与比较counter值。
(4)这里赵炯老师似乎认为需要加入一行*p=tmp；但小编我却也不这么认为，因为我认为这么做违背了这段代码设计者的原初衷，原因主要有以下几点：
[1]首先，排开*p我们暂时先不考虑，我们先来分析临时变量tmp，从调度函数返回后，我们做的第一件事就是将队列中紧跟当前任务后的tmp所指的任务（暂且将该任务称为任务B，将当前任务称为任务A）置为就绪态，当任务A释放cpu控制权并通过调度（可能多次）进入任务B后，又会以同样的方法就绪任务B后的任务C，从而产生链式反应下去，直到整个队列中的任务依次就绪完毕。而加入*p=tmp;能为链式反应带来什么帮助呢，除了可以记录下一个被置为就绪态的任务结构地址，似乎没有其他作用了，且这么做对wake_up过程来说是会出问题的。
[2]接下来说说wake_up函数，从函数的内部实现来看，这个函数应当是编码者用来唤醒资源等待队列头指针所指的整个休眠任务链的，因此它的传入参数必须且仅能是某个休眠队列头指针，当然，如果你把记录这个队列中的某个tmp地址的变量作为参数传递进去，似乎也能触发一部分链式反应，继而你再传入p又能触发剩余部分的链式反应，但这与一次唤醒整个休眠任务队列的初衷相悖。另外，p这个队列头指针的单次有效周期，小编我觉得是相对于整个休眠任务链而言的，因此，它在调用wake_up唤醒而触发链式反应的那一刻起，即结束了，故将p置为NULL。为什么呢？请试想这样一种情况，当我们通过p来唤醒其对应的休眠任务链的过程中，假设任务A此时获得了已经被释放的唯一的一个资源，但链式反应还在继续，这时由于调度的随机性，cpu被切换到了另一个不在任务链中的任务Z，且在其执行过程中由于申请资源又在p上进行了休眠操作，则它将被插入到p的队列中，这时如果p已经被置为NULL，那么它将与原来正在执行链式唤醒的队列脱离关系，但是如果加入了*p=tmp;，这一切就会乱了套，任务Z可能与原来队列中的任务建立不可预知的连接关系，又或是指向任务Z的*p有可能被抹掉。而若没有这句，则链式反应继续的过程中，后续任务会由于没有资源申请，再次正常的被接入到p所指的队列中。
[3]然后小编我再来讲讲下面的可中断休眠函数interruptible_sleep_on，由于是可中断的休眠操作，因此是可以不只通过被wake_up这一种受控渠道来唤醒的，休眠任务链中的任务完全有可能从中间被某个信号或中断唤醒，为了保证与不可中断休眠操作的统一性，这里内核编码者，就通过一段跳转代码，使其自动切换到休眠任务链的头部来依次进行唤醒操作，从而保证了与不可中断休眠操作的统一性。
Linux的可中断睡眠函数interruptible_sleep_on在Sched.c中定义，它所完成的工作如下：
(1)若传入的睡眠队列头指针参数无效则直接返回，若当前需要睡眠的任务是初始任务0，则直接当机。
(2)函数中定义临时任务结构指针变量tmp，由于interruptible_sleep_on函数在当前任务的进程中被调用，因此，该tmp变量则被定义到了当前任务的局部数据段上，将原睡眠队列头指向的地址信息保存在该tmp变量中，然后将睡眠队列头重新指向当前任务，即在头部插入。
(3)置当前任务状态为可中断状态，并重新触发调度，由于退出了就绪态，根据前面关于调度函数的分析，这个任务也就暂时放弃了执行权，因为只有就绪态的任务才有资格在schedule的循环中参与比较counter值。
(4)关于这个部分（179-182行）小编我在前面已经提到过，通过这个判断和跳转指令，实际上是实现了重新定位到当前唤醒的队列的头部，然后再依序唤醒队列中的所有任务，而这里后面将*p置为NULL，则也应该是编码者出于与wake_up函数一致的考量，但是这么做小编我认为确实是有bug存在的，也正如赵炯老师说的，仅仅只加入一行*p=tmp；就可以解决。下面就让小编我来讲讲我的一些理解：
[1]首先我们看看，按照赵炯老师说的改为*p=tmp；后会如何运行，我们假定现在等待队列中依次休眠有ABC三个任务，即有*p->A;A(tmp)->B;B(tmp)->C;C(tmp)->NULL;，我们再假定现在由于某种原因，资源得到了部分释放，B优先通过中断或信号获得了执行权，则B将由于当前任务与*p不等的条件判断，就绪*p所指的A任务，并将自己重置为可中断状态。此时由于A的继续执行，*p指向了B，并就绪了B，这里我们假定A获得了这个唯一的资源，并在时间轮转中，先于B进入了D任务，而在D任务中也发起了对该资源的申请，由于唯一的资源被A占用了，于是D取代A成为了新的头部，此时链表的序列如下：*p->D;D(tmp)->B;B(tmp)->C;C(tmp)->NULL;，接下来D休眠了，回到了B中运行，由于在B中同样的条件判断结果被触发，执行权再一次回到了处于队列头部的D，但由于没有资源可用，在将*p移到了B后，D又就绪了B，通过资源检查，D再度调用休眠函数休眠，同时它将自己再度插入到p的头部，然后，B再度执行，由于B不是p的头部，它又将回到D，进而产生一个循环。而这在没有资源可用的情况下，应属正常。
[2]然后我们再看看*p=NULL；的情况。同样假定现在等待队列中依次休眠有ABC三个任务，即有*p->A;A(tmp)->B;B(tmp)->C;C(tmp)->NULL;，且由于某种原因，资源得到了部分释放，B优先通过中断或信号获得了执行权，则B将由于当前任务与*p不等的条件判断，就绪*p所指的A任务，并将自己重置为可中断状态。此时由于A的继续执行，*p指向了NULL，并就绪了B，这里我们假定A获得了这个唯一的资源，并在时间轮转中，先于B进入了D任务，而在D任务中也发起了对该资源的申请，由于唯一的资源被A占用了，于是D取代A成为了新的头部，此时链表的序列如下：*p->D;D(tmp)->NULL;B(tmp)->C;C(tmp)->NULL;，接下来D休眠了，回到了B中运行，由于在B中同样的条件判断结果被触发，执行权再一次回到了处于队列头部的D，在将*p置为NULL后，由于D中的tmp也指向NULL，B已经不能再被就绪了，除非再次发生中断或产生相应信号，而这显然是不对的。
Linux的唤醒函数wake_up在Sched.c中定义，它所完成的工作很简单，就是置等待队列头指针所指任务为就绪态，同时清除*p。对于不可中断睡眠的任务队列，我们已经分析过了，用它来唤醒是没有问题的，而对于可中断睡眠的任务队列，用它来唤醒呢？由于*p在睡眠函数中会被*p=tmp;重置，因此，也是没有问题的。
Linux的时钟处理函数do_timer在Sched.c中定义，它由System_call.s中的_timer_interrupt调用，所完成的工作内容如下：
(1)根据beepcount值控制扬声器。
(2)根据传入参数RPL，累加用户运行时间或内核运行时间，以作记录。
(3)处理定时器，对定时器计数值进行递减操作，如果超时，则调用定时器超时函数。
(4)进行软盘定时器控制。
(5)对当前任务时间片计数值进行递减操作，若时间片未到0，则直接返回。
(6)对时间片已到0，但处于内核态的进程不做处理，直接返回，对用户态的进程，则执行调度。
接下来小编我想先聊聊其他几个实时系统，比如uCos3/FreeRTOS.