主要理解注释中提到的链表以及缺少几行代码的缘由
何为任务调度?
学过操作系统的筒子们应该有很深刻的理论了,其实说白了就是从现有可运行的任务中选一个最紧急(或者优先级最高)的任务运行,关于如何定义”最紧急”(优先级最高或者说实时进程)才是调度算法去解决的问题,这里先不分析,Linux 0.11内核调度算法也不是很难。
sleep_on()函数
没有源代码的可以参阅这里。这里的代码已经有修复了。Linus原来的代码如下:(中文注释乃赵博士所写~)
1 | // 把当前任务置为不可中断的等待状态,并让睡眠队列指针指向当前任务。 |
调用此函数的地方一般是资源得不到满足(比如等待缓冲区解锁等场景)而致使自身任务运行到这里时候睡眠。但是等待这个资源的可能不止一个进程,一般管理缓冲的数据结构都会设置一个task_struct结构体指针表示当前正在等待本缓冲区的任务。但数据结构中并没有明显定义链表结构呀?注释里怎么说有呢?其实是”潜移默化”地保存在了各个任务的栈空间中去了。
内核代码首先定义一个tmp指针保存已经正在等待本资源的进程(假设叫A),然后将正在等待本资源的进程改变为当前进程(假设叫B),并立即置B进程状态为不可中断地好唤醒,表示只能由wake_up函数来唤醒。之后便进行任务调度,因此B进程会”停止”在任务调度这里,因为如果没有被唤醒(即state置0)是不可能被调度的,调度算法只会选出”状态为0”的进程进行调度运行。假设另外一个进程(假设为C)也需要这个资源,代码也运行到这里(但是它们的进程上下文是不同的),在C进程的栈空间定义一个tmp保存B进程的指针,把C自己的指针赋值到资源等待任务的指针位置,并启用任务调度,同样,C也会”停止”在这里。假设某个时候某个进程手动调用了wake_up函数。此时传递的指针居然是C进程(假设之后没有其他进程需要这个资源了)。好了,C被唤醒了,肯定优先于A和B运行了,貌似不太公平呀,”后来先到”。当调度程序检测到C处于可运行状态的时候并且它的优先级最高,便切换到C运行,而C会从schedule()函数这里继续向后运行,Linus原来的代码仅仅是将tmp任务(这里是B)唤醒,如果在这次之后没有其他任务来竞争这个资源,则也能顺利陆续唤醒(因为B运行完了也会执行到这里,B的tmp保存了A的任务指针…)。但是如果此时有一个任务D也来等待这个资源,D运行到tmp的时候tmp保存的居然还是C的任务指针(因为等待资源任务指针没有被更新)。之后运行完之后继续唤醒C(没啥用,C早就可运行,或者等待其他资源而阻塞,此时唤醒它将会打乱其所在队列…当然一般会有其他策略继续检测)。但是A和B不出意外就永远不能唤醒了。因此赵博士的注释要求增加一行代码*p=tmp
,目的是刷新等待缓冲任务指针。(按照栈的意思也得有借有还吧,前面保存了之后也得会送回去呀)至于为什么Linux 0.11版本内核也看出什么大问题可能是由于”竞争”不够激烈,等待真正遇到业务场景复杂的时候弊端就暴露出来了,因此Linux内核版本一直在前进中。
1 | // 唤醒*p指向的让任务。*p是任务等待队列头指针。由于新等待任务是插入在等待队列头指针处的, |
同样的源代码于interruptible_sleep_on函数。大体思路差不多,只不过此状态可被某些信号唤醒,不必要一定调用wake_up函数来置位。如注释所说,因此必须判断是否当前任务是否为等待头指针才能对头指针进行唤醒而自身又置为TASK_INTERRUPTIBLE状态并重新调度。(由于信号对其会产生影响而并不唯一是其他进程唤醒的)
1 |
|
总结
CS中学会抽象还是非常重要的,无处不在的数据结构:)