-
Linux 内核与人类社会
-
公司平面图
-
时间片和职称
-
Mr. P的经历
-
评定动态职称
-
现在我们回来讨论Mr. P
-
O(1)调度
-
对交际花的优惠政策
-
公司里的超级特权阶级－小霸王
-
总结
在研究 Linux 进程调度的时候，看到这样一篇文章，写的很幽默，分享给大家！
为了提高阅读体验，我把一些关键词加了颜色。
ce编辑器" style="margin-top: 30px;margin-bottom: 15px;font-weight: bold;color: black;border-bottom: 2px solid rgb(239, 112, 96);font-size: 1.3em;">Linux 内核与人类社会
Linux 内核是一个无比复杂的系统，要想看清大致的脉络也非易事。其实，可以把运行中的Linux想像成一个人类的社会，当中的进程就是社会中的人。
人有生老病死，进程有
创建、异常、终止。
人有各种各样的财产，进程有对应的
地址空间、设备等等。
人被各种各样的东西限制着，被人管着，进程也是。
内核无比巨大，从哪着手？我想，从进程的视角来看是个好办法。
并且，在学习Linux内核的同时，类比人类社会来看，会有更深刻的印象，理解得更透彻。
本来也应该从进程的创建开始写的，但是最近在看调度的相关论文，就又把Linux调度的东西看了一下。
所以，就先写调度相关的东西吧。
公司平面图
首先介绍与进程所在环境对应的人类场景：
这是一个公司，公司里有很多人（
进程），每个人都有其对应的职称（
优先级）。
这个公司很奇怪，只有一张办公桌（
CPU），在任意时刻，只能有一个人在工作(TASK_RUNNING正在运行状态)。
其他人呢，要么在休息室时
短暂地休息（对应TASK_RUNNING就绪状态），要么就在
寝室Sleep(对应TASK_INTERRUPTABLE或TASK_UNINTERRUPTABLE)，要么就是死人了，在停尸间（TASK_ZOMBIE）。
是的，这是真的，这个公司就是个血汗工厂，干活累死了，就直接丢进停尸间，惨绝人寰！
以下是此公司的平面图：
图解：
“推门”是
单向的：比如连接工作室和太平间的是推门，职员只能从工作室走到太平间，不能从太平间走到工作室（这太吓人了）。
“凹槽门”是
双向的：比如连接工作室和休息室的门是凹槽门，职员可以走来走去。
时间片和职称
时间片(time slice)：这个公司的工资特别高，按工作的小时数计算。工作者得钱，不工作者不得钱。
所以，
所有的人都特想去办公桌那里工作，争着抢着要去。为了让大家都有机会去工作（避免有的人没钱拿，饿死，i.e. starve to death），所以公司出了条规定，每个人每次工作的时间不能超过公司分给自己的时间片（time slice）。时间片的大小由此人的
职称(优先级)决定。
职称（也就是内核中的priority）：职称有两种，一种是
静态职称（static priority），一种是动态职称（dynamic priority）。
静态职称是先天的，由此人的老爸决定（富二代有先天优势！）。
动态优先级是看在公司里的工作表现的。
职称是很重要的东西，职称越高，你到办公桌上赚钱的机会越大。
默认时间片长点好还是短点好？
自然是
不长不短好（世界上的事情都是这样）。
如果太短了，比如说某职员时间片是1分钟（对应的Linux里的时间片应该差不多是0.1ms吧，可能还得少点），这个人在办公桌前
屁股没坐热就要走了，从起身到回到休息室，再到下一个人起身走到办公桌前坐下，这也得要一分钟。
如果这样的话，这公司将有
一半的时间花在走路上。这样搞是不行的，在资本主义社会，大家都要努力搞高生产率。
那是不是时间片长了就好？也不是。
比如时间片是
一个小时，当两个客户（对应Linux中的两个用户）同时要和此公司展开业务（对应Linux中的启动进程），有两个职员会分别处理这两个业务。
A职员一上去就占着办公室一个小时，B职员在这一个小时结束前没法子处理他的客户的业务，所以B职员的客户就得在寒风中等一个小时！
资本主义社会里的公司是不能让他们的财神爷不高兴的。所以，还是
不长不短的好。
回到真实的Linux内核中:很多人认为时间片过长会导致程序的响应（比如字处理程序的I/O响应）变慢，因为要等时间片用完才能处理。
其实不然，字处理程序等交互性强的程序,他们的
优先级高，可以
抢占当前正在运行的进程，从而得到执行。
在公司里，就比如B职员的职称高，他可以把A职员从办公桌上踢走。
事实上，从后面对动态优先级的讨论我们可以看到，要是A职员一直霸占着办公桌不走，他/她的动态职称会
变低的，结果是，在休息室里的其他职员的职称就自然而然地可能比A高了。
职员目录(Process list)：公司有个目录，在这个目录中，列出了所有公司的职员。这对应Linux里的
Process List，里面存有所有进程的信息。
Mr. P的经历
Mr. P 的出生
这是世界上最怪异的公司，职员都是单性的，都是男的。
并且不要交配，自己调用系统调用fork()，就可以生了。生出来的小孩子也都是男的。
在这里为了问题的简化，就只讨论与调度的关系比较紧密的内容。
如上图所示，在休息室里其实还有两个沙发。一个沙发叫做
活动队列（往后我们叫它活动沙发吧），一个沙发叫做
过期队列（往后我们叫它过期沙发）。
坐在活动沙发上的职员都还有时间片没有用完，坐在过期沙发上的职员的时间片刚刚被用完了（但他们手上都拿着新分配到的时间片，这个是2.5版内核新引入的O(1)调度，后面再讲）。
Mr. P的父亲在办公桌旁边工作的时候，突然fork()了一下，就生出了Mr.P。
一出生，Mr. P就拥有
和父亲一样的静态职称（static priority）。
他一出生就坐在了活动沙发上，拿走了父亲
一半的时间片。比如生MR. P之前，MR. P的父亲有10ms的时间片，MR.P出生后，他父亲有5ms，Mr. P有5ms。
：试想，有一人，自己有10ms的时间片，他一直生啊生，生了100个孩子，那么这个程序就有了10 10*100ms的时间片了。
然后他的孩子断续生啊生，那么有可能系统中绝大部分的时间片都是他家的了，那他的街坊邻居还要不要活啊，没时间片等于不能做事，等于没工资，等于没食物，等于饿死。
另外，不幸的是，即使是在发达的资本主义社会，孩子也是有可能
夭折的（由于各种原因，在第一次到办公桌上工作之前就死掉了）。在这种情况下，公司会把孩子没用的时间片还给他父亲。多么人性化的公司…
开始工作
像其他所有孩子一样，Mr. P一生下来就能工作了，他坐在活动沙发上等着做事。
他人事部的同事Miss Schedule (以下简称Miss S)会在
每个tick(内核的时间单位，时间很短)结束时检查一下以下两种情况有没有发生：
-
在办公桌前工作的那个职员是不是已经用完自己的时间片了。
-
是不是有更高动态职称（dynamic priority）的职员在活动沙发上等着。
其中一种情况成立，这个在
办公桌前工作的那个职员就要被赶出来，换在活动沙发上坐着的动态职称最高的职员进去工作。
假设经过一段时间后，没有人的动态职称比Mr. P高了。在一个时间tick结束时，Miss S到休息室检查大家当前的职称。
他能轻松地找到动态职称最高的职员(sched_find_first)，因为职员们都是
按动态职称来坐的（在活动沙发上），动态职称相同的职员坐在一起（参考struct prio_array）。
Miss S只要按顺序找下去，第一个在沙发上找到的职员就是职称最高的。
当Miss S用上面的方法发现Mr. P当前的动态职称是最高的时，在办公桌前工作的是职员C，Miss S把C从办公桌前拉到休息室。
如果此时C的时间片已经
用完了，他就会被安排坐在
过期沙发上（这也就是expired的含义）；如果此时C的时间片
没有用完，他就会被安排坐在
活动沙发上。
C被拉到休息室时，他的工作用具，笔啊纸啊什么的，都要从办公桌上拿走（这是关于
进程上下文切换的问题）。
C走了之后，Mr. P带着他的东西到办公桌前坐下，整理好办工用品（进程上下文切换）。好的，Mr. P可以开始工作了。
评定动态职称
公司里的
两类人：
交际花（I/O消耗型进程）：这类人常常与外部的客户打交道(
IO操作比较多)，而客户的反应总是不怎么快。所以，交际花常常要
等客户做出反应。公司为了不让交际花在等客户反应的时候也占用着办公桌，所以，当交际花要等待客户的响应时，他就会被移到寝室去睡觉(Sleep)。
工作狂（处理器消耗型）：这类人就是传说中的苦干王，很少和外界打交道（
IO操作比较少），就知道在办工桌上做事。这种工作狂给公司造成一些困扰，如果他们老占着办公桌，交际花就没法做事了。要知道，一个公司还是需要人去跑跑业务的。
公司有一套机制，这一套机制能很好的区分这两类人，并且给他们
评定职称（调整优先级）。
判断的标准就是他们的
平均睡眠时间（average sleep time）。
睡眠时间包括在寝室里的时间（TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE）和在休息室时等待的时间。
但平均睡眠时间的计算并不是加和再求平均那么简单。在TASK_INT和TASK_UNINT两种状态下，平均睡眠时间的增长情况是不一样的。
在运行的时间，平均睡眠时间是在减少的。具体的平均睡眠时间的算法在recalc_task_prio()中。
-
当一个职员常常睡觉，公司就知道这人是交际花了，因为他常常因为等客户的响应而睡觉。
-
当一个职员很少睡觉，公司就知道这人是个工作狂了，因为他很少因为等客户的响应而睡觉。
现在我们回来讨论Mr. P
假设Mr. P在工作的时候要
等待一个客户给数据给他(比如说键盘数据)，他就把自己的加入一个等待队列里，将自己设为TASK_INT，这样他就进入了
寝室（休眠）里。
Mr. P在那里苦苦地
等待他要的数据到来。
终于，客户敲下了键盘，给出了数据。然后键盘事件的管理者调用wake_up()函数，将Mr. P
唤醒。
-
如果Mr. P的动态职称高于当前正在工作的职员的动态职称，那么Mr. P就会抢掉这个职员的办公桌。
-
如果不高于的话，Mr. P就只是先到休息室里坐着。
我们假设Mr. P的动态职称很高，所以，现在Mr. P又抢到了办公桌。
O(1)调度
又过了一段时间，Mr. P的
时间片用完了，该离开了。
这时他该被Miss S带到
过期沙发上了，在从办公桌走到过期沙发的路上，Miss S会帮他重新算时间片（依照动态职称来决定时间片的长短）。
事实上，每个职员被带到过期沙发上坐着的时候，Miss S都会帮他算好时间片。
这样，过期沙发上的所有职员手中都拿着时间片。这样做的好处是，当活动沙发空了的时间，只要把活动沙发和过期沙发上贴着的“活动沙发”和“过期沙发”的
标签互换 一下，原来的过期沙发就变成了活动沙发，原来的活动沙发就变成了过期沙发。
这样，Miss S就又可以从活动沙发上叫人去工作了。而这个“互换标签”的动作的时间复杂度是O(1)。这就是2.5版
内核所引入的O(1)调度。
试想一下没有这个O(1)调试之前是什么情况?
每次所有进程的时间片都用完时，要
重新计算所有TASK_RUNNING状态的进程的时间片。
当一个系统中只有几个进程的情况还好，但是对于有成千上万个进程的大型系统，这是相关耗时的。
对交际花的优惠政策
在一个公司来说，交际花是
非常重要的，他们的表现直接关系到客户的满意度和公司的形象。所以，Linux公司有一些专门针对交际花的
优惠政策。
假设Mr. P就是一个十足的交际花：上班打扮得花枝招展（虽然是个男的），见人说人话见鬼说鬼话，关键是，他有一些客户特别爱和他把交道。
当Mr. P用完一个时间片的时候，照常理，他是应该被Miss S带到过期沙发上去等待下一次工作的。
但这样的等待有可能太久了－要等到
所有活动沙发上的职员都用完时间片。所以，Miss S
为了客户的满意度（如果等太久，客户是不满意的），就在重新计算Mr. P的时间片之后，让他留在了活动沙发上。这样，Mr. P就能更快地处理客户的IO事件。
这看起来是对交际花的
特权，其实这是为了公司的
长远利益着想。
如果客户的需求得不到及时的满足，客户不满意，就不会有人用这公司的产品了，即使工作狂们的工作做得很好。
公司里的超级特权阶级－小霸王(real-time process)
交际花是有一些特权，但
权利再大也大不过小霸王。
公司有时会有一些时间很紧的项目要做，这些项目有deadline。为了能完成这些重要的项目，公司里发展了一种特权阶级，就是小霸王。
他们的职称
高于其他所有普通员工，除非他们完成了自己的工作，否则其他职工不能去工作。
这些小霸王的工作方式有两种：
-
FIFO(First In First Out)：当一个小霸王完成自己工作的时间，其他小霸王才能去工作。但是当有职称更高的小霸王到来时，职称更高的小霸王能抢占当前的小霸王的办公桌。
-
RR(Route Robin)：相同优先级的小霸王转着用办公桌，每人用一段时间。
总结
在这篇文章里，以Mr. P的工作经历来说明了
Linux调度的一些比较重要的机制。
介绍了
IO消耗型进程和处理器消耗型的进程，O(1)调度等等。
这些是比较大的方面，当大的方面理解了之后，那些世界顶尖高手写的源码也就更容易看懂一些了。
免责声明：本文转自网络文章，转载此文章仅为个人收藏，分享知识，如有侵权，请联系我进行删除。
下载文档
