Mr Process的一生Linux内核的社会视角Word文件下载.docx
《Mr Process的一生Linux内核的社会视角Word文件下载.docx》由会员分享，可在线阅读，更多相关《Mr Process的一生Linux内核的社会视角Word文件下载.docx（13页珍藏版）》请在冰点文库上搜索。
为了让大家都有机会去工作（避免有的人没钱拿，饿死，i.e.starvetodeath），所以公司出了条规定，每个人每次工作的时间不能超过公司分给自己的时间片（timeslice）。
时间片的大小由此人的职称决定。
职称（也就是内核中的priority）：
职称有两种，一种是静态职称（staticpriority），一种是动态职称（dynamicpriority）。
静态职称是先天的，由此人的老爸决定（富二代有先天优势！
）。
动态优先级是看在公司里的工作表现的。
职称是很重要的东西，职称越高，你到办公桌上赚钱的机会越大。
默认时间片长点好还是短点好？
自然是不长不短好（世界上的事情都是这样）。
如果太短了，比如说某职员时间片是1分钟（对应的Linux里的时间片应该差不多是0.1ms吧，可能还得少点），这个人在办公桌前屁股没坐热就要走了，从起身到回到休息室，再到下一个人起身走到办公桌前坐下，这也得要一分钟。
如果这样的话，这公司将有一半的时间花在走路上。
这样搞是不行的，在资本主义社会，大家都要努力搞高生产率。
那是不是时间片长了就好？
也不是。
比如时间片是一个小时，当两个客户（对应Linux中的两个用户）同时要和此公司展开业务（对应Linux中的启动进程），有两个职员会分别处理这两个业务。
A职员一上去就占着办公室一个小时，B职员在这一个小时结束前没法子处理他的客户的业务，所以B职员的客户就得在寒风中等一个小时！
资本主义社会里的公司是不能让他们的财神爷不高兴的。
所以，还是不长不短的好。
回到真实的Linux内核中:
很多人认为时间片过长会导致程序的响应（比如字处理程序的I/O响应）变慢，因为要等时间片用完才能处理。
其实不然，字处理程序等交互性强的程序,他们的优先级高，可以抢占当前正在运行的进程，从而得到执行。
在公司里，就比如B职员的职称高，他可以把A职员从办公桌上踢走。
事实上，从后面对动态优先级的讨论我们可以看到，要是A职员一直霸占着办公桌不走，他/她的动态职称会变低的，结果是，在休息室里的其他职员的职称就自然而然地可能比A高了。
职员目录（Processlist）：
公司有个目录，在这个目录中，列出了所有公司的职员。
这对应Linux里的ProcessList，里面存有所有进程的信息。
下面以Mr.P的经历为例说明
PersonalHistoryStatementofMr.Process（Mr.Pinshort）
出生
这是世界上最怪异的公司，职员都是单性的，都是男的。
并且不要交配，自己调用系统调用fork（），就可以生了。
生出来的小孩子也都是男的。
在这里为了问题的简化，就只讨论与调度的关系比较紧密的内容。
图：
详细的公司平面图
如上图所示，在休息室里其实还有两个沙发。
一个沙发叫做活动队列（往后我们叫它活动沙发吧），一个沙发叫做过期队列（往后我们叫它过期沙发）。
坐在活动沙发上的职员都还有时间片没有用完，坐在过期沙发上的职员的时间片刚刚被用完了（但他们手上都拿着新分配到的时间片，这个是2.5版内核新引入的O
（1）调度，后面再讲）。
Mr.P的父亲在办公桌旁边工作的时候，突然fork（）了一下，就生出了Mr.P。
一出生，Mr.P就拥有和父亲一样的静态职称（staticpriority）。
他一出生就坐在了活动沙发上，拿走了父亲一半的时间片。
比如生MR.P之前，MR.P的父亲有10ms的时间片，MR.P出生后，他父亲有5ms，Mr.P有5ms。
这样的机制是为了防止有人以生子来抢夺时间片：
试想，有一人，自己有10ms的时间片，他一直生啊生，生了100个孩子，那么这个程序就有了10+10*100ms的时间片了。
然后他的孩子断续生啊生，那么有可能系统中绝大部分的时间片都是他家的了，那他的街坊邻居还要不要活啊，没时间片等于不能做事，等于没工资，等于没食物，等于饿死。
另外，不幸的是，即使是在发达的资本主义社会，孩子也是有可能挂掉的（由于各种原因，在第一次到办公桌上工作之前就挂掉了）。
在这种情况下，公司会把孩子没用的时间片还给他父亲。
多么人性化的公司…
开始工作
像其他所有孩子一样，Mr.P一生下来就能工作了，他坐在活动沙发上等着做事。
他人事部的同事MissSchedule（以下简称MissS）会在每个tick（内核的时间单位，时间很短）结束时检查一下以下两种情况有没有发生：
1.在办公桌前工作的那个职员是不是已经用完自己的时间片了。
2.是不是有更高动态职称（dynamicpriority）的职员在活动沙发上等着。
其中一种情况成立，这个在办公桌前工作的那个职员就要被赶出来，换在活动沙发上坐着的动态职称最高的职员进去工作。
假设经过一段时间后，没有人的动态职称比Mr.P高了。
在一个时间tick结束时，MissS到休息室检查大家当前的职称。
他能轻松地找到动态职称最高的职员（sched_find_first），因为职员们都是按动态职称来坐的（在活动沙发上），动态职称相同的职员坐在一起（参考structprio_array）。
MissS只要按顺序找下去，第一个在沙发上找到的职员就是职称最高的。
当MissS用上面的方法发现Mr.P当前的动态职称是最高的时，在办公桌前工作的是职员C，MissS把C从办公桌前拉到休息室。
如果此时C的时间片已经用完了，他就会被安排坐在过期沙发上（这也就是expired的含义）；
如果此时C的时间片没有用完，他就会被安排坐在活动沙发上。
C被拉到休息室时，他的工作用具，笔啊纸啊什么的，都要从办公桌上拿走（这是关于进程上下文切换的问题）。
C走了之后，Mr.P带着他的东西到办公桌前坐下，整理好办工用品（进程上下文切换）。
好的，Mr.P可以开始工作了。
评定动态职称
公司里的两类人：
交际花（I/O消耗型进程）：
这类人常常与外部的客户打交道，而客户的反应总是不怎么快。
所以，交际花常常要等客户做出反应。
公司为了不让交际花在等客户反应的时候也占用着办公桌，所以，当交际花要等待客户的响应时，他就会被移到寝室去睡觉（Sleep）。
工作狂（处理器消耗型）：
这类人就是传说中的苦干王，很少和外界打交道，就知道在办工桌上做事。
这种工作狂给公司造成一些困扰，如果他们老占着办公桌，交际花就没法做事了。
要知道，一个公司还是需要人去跑跑业务的。
公司有一套机制，这一套机制能很好的区分这两类人，并且给他们评定职称。
判断的标准就是他们的平均睡眠时间（averagesleeptime）。
睡眠时间包括在寝室里的时间（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的时间片用完了，该离开了。
这时他该被MissS带到过期沙发上了，在从办公桌走到过期沙发的路上，MissS会帮他重新算时间片（依照动态职称来决定时间片的长短）。
事实上，每个职员被带到过期沙发上坐着的时候，MissS都会帮他算好时间片。
这样，过期沙发上的所有职员手中都拿着时间片。
这样做的好处是，当活动沙发空了的时间，只要把活动沙发和过期沙发上贴着的“活动沙发”和“过期沙发”的标签互换一下，原来的过期沙发就变成了活动沙发，原来的活动沙发就变成了过期沙发。
这样，MissS就又可以从活动沙发上叫人去工作了。
而这个“互换标签”的动作的时间复杂度是O
（1）。
这就是2.5版内核所引入的O
（1）调度。
试想一下没有这个O
（1）调试之前是什么情况：
每次所有进程的时间片都用完时，要重新计算所有TASK_RUNNING状态的进程的时间片。
当一个系统中只有几个进程的情况还好，但是对于有成千上万个进程的大型系统，这是相关耗时的。
对交际花的优惠政策
在一个公司来说，交际花是非常重要的，他们的表现直接关系到客户的满意度和公司的形象。
所以，Linux公司有一些专门针对交际花的优惠政策。
假设Mr.P就是一个十足的交际花：
上班打扮得花枝招展（虽然是个男的），见人说人话见鬼说鬼话，关键是，他有一些客户特别爱和他把交道。
当Mr.P用完一个时间片的时候，照常理，他是应该被MissS带到过期沙发上去等待下一次工作的。
但这样的等待有可能太久了－要等到所有活动沙发上的职员都用完时间片。
所以，MissS为了客户的满意度（如果等太久，客户是不满意的），就在重新计算Mr.P的时间片之后，让他留在了活动沙发上。
这样，Mr.P就能更快地处理客户的IO事件。
这看起来是对交际花的特权，其实这是为了公司的长远利益着想。
如果客户的需求得不到及时的满足，客户不满意，就不会有人用这公司的产品了，即使工作狂们的工作做得很好。
公司里的超级特权阶级－小霸王（real-timeprocess）
交际花是有一些特权，但权利再大也大不过小霸王。
公司有时会有一些时间很紧的项目要做，这些项目有deadline。
为了能完成这些重要的项目，公司里发展了一种特权阶级，就是小霸王。
他们的职称高于其他所有普通员工，除非他们完成了自己的工作，否则其他职工不能去工作。
这些小霸王的工作方式有两种：
FIFO（FirstInFirstOut）：
当一个小霸王完成自己工作的时间，其他小霸王才能去工作。
但是当有职称更高的小霸王到来时，职称更高的小霸王能抢占当前的小霸王的办公桌。
RR（RouteRobin）：
相同优先级的小霸王转着用办公桌，每人用一段时间。
总结：
在这篇文章里，以Mr.P的工作经历来说明了Linux调度的一些比较重要的机制。
介绍了IO消耗型进程和处理器消耗型的进程，O
（1）调度等等。
这些是比较大的方面，当大的方面理解了之后，那些世界顶尖高手写的源码也就更容易看懂一些了。
其实这才应该是这一系列文章的第一节，因为这篇文章讲的是盘古开天地的事。
话说Mr.Process是一个现代人，但是，只要是人，总该有个祖先。
人们总想知道自己从哪来，然后才可以估摸算一下自己将去向何方。
所以咱也要了解一下Linux的世界里人类的起源。
图1：
从上电到BIOS
按下电源开关的那个真实的人就是Linux世界里的上帝，他创造了Linux世界的一切。
当他按下机箱上的电源开关时，主板开始供电，CPU上的ResetPin被拉高，这会引起CPU的一系列动作，这些动作是芯片设计时就决定的。
CPU中的一些寄存器被置为固定的值，因为这些寄存器可能在启动的过程中要使用，比如CS（代码段寄存器）和EIP（指针指令寄存器）。
这一步完成之后，CPU就可开执行地址为0xfffffff0里的ROM中的程序。
这段程序就是BIOS（BasicInputOutputSystem）。
BIOS完成下面的功能：
1.POST（Power-OnSelfTest）：
顾名思名，就是查查有什么设备，这些设备是不是正常。
要是CPU有AdvancedConfigurationandPowerInterface（ACPI）的支持，也在这个时候进行。
ACPI是用来对电源进行管理的，用来节电之类的。
2.初始化设备：
确保没有IRQ和IO冲突。
3.寻找OS/Bootloader。
这一步后面点再细说
我们在BIOS的设置菜单里能够设置从何处启动，比如软盘，硬盘，光驱…BIOS会按我们设定的顺序搜索OS。
4.把Bootloader复制到RAM里（地址为0x00007c00），然后那个地址开始执行。
什么是Bootloader？
现在，我们只要关心的是：
bootloader会找到OS，把OS内核COPY到RAM中。
图2：
bootloader的加载
如上图所示，在硬盘的第一个sector，有一个分区表（记录了哪些分区上有操作系统）和一个小版的Bootloader。
当这个BIOS被设置为从这里启动时，这个小版的bootloader被复制到RAM的0x00007c00。
然后它会把自己又移动到0x00096a00。
在这之后，它再把另一段Bootloader从硬盘上复制到0x00096c00，然后从那里开始执行。
分作两段的原因是因为现在的bootloader太大了，在MBR上存不完那么多。
Bootloader会把OS的内核映像复制到RAM中。
Bootloader的工作
1.调用BIOS以显示“LoadingImage”的消息。
2.调用BIOS，把内核映像的前512字节复制到0×
00090000，setup（）函数在0×
00090200。
3.调用BIOS，把剩下的内核映像加载到0×
00010000（小内核zImage）或0×
00100000（大内核bzImage）
4.跳到setup（）开始执行。
Setup（）的工作
setup（）用来初始化设备。
虽然BIOS已经做了一些初始化的工作，但是Linux关不依赖于他。
setup（）会初始化键盘，FPU等设备，并设置一些寄存器。
在Setup（）的最后，会调用startup_32（）。
startup_32（）
Linux里有两个startup_32（）。
首先会执行的是arch/i386/boot/compressed/head.S里的那个。
这个startup_32（）的作用主要是解压内核。
第二个startup_32（）是在arch/i386/kernel/head.S的。
这个startup_32（）的工作就是为Linux的第一个进程（就是Mr.Process的祖先）设置生存环境。
最后跳到start_kernel（）中去。
在UnderstandingtheLinuxKernel3rd
中的描述如下
1.Initializesthesegmentationregisterswiththeirfinalvalues.
2.Fillsthebsssegmentofthekernel（seethesection“ProgramSegmentsandProcessMemoryRegions”inChapter20）withzeros.
3.InitializestheprovisionalkernelPageTablescontainedin
swapper_pg_dir
and
pg0
toidenticallymapthelinearaddressestothesamephysicaladdresses,asexplainedinthesection“KernelPageTables”inChapter2.
4.StorestheaddressofthePageGlobalDirectoryinthe
cr3
register,andenablespagingbysettingthe
PG
bitinthe
cr0
register.
5.SetsuptheKernelModestackforprocess0（seethesection“KernelThreads”inChapter3）.
6.Onceagain,thefunctionclearsallbitsinthe
eflags
7.Invokes
setup_idt（）
tofilltheIDTwithnullinterrupthandlers（seethesection“PreliminaryInitializationoftheIDT”inChapter4）.
8.PutsthesystemparametersobtainedfromtheBIOSandtheparameterspassedtotheoperatingsystemintothefirstpageframe（seethesection“PhysicalMemoryLayout”inChapter2）.
9.Identifiesthemodeloftheprocessor.
10.
Loadsthe
gdtr
idtr
registerswiththeaddressesoftheGDTandIDTtables.
11.
Jumpstothe
start_kernel（）
function.
start_kernel（）的工作
完成所有组件的初始化工作。
UnderstandingtheLinuxKernel对这一段工作的描述如下：
¨
Theschedulerisinitializedbyinvokingthesched_init（）function（seeChapter7）.
Thememoryzonesareinitializedbyinvokingthebuild_all_zonelists（）function（seethesection“MemoryZones”inChapter8）.
TheBuddysystemallocatorsareinitializedbyinvokingthepage_alloc_init（）andmem_init（）functions（seethesection“TheBuddySystemAlgorithm”inChapter8）.
ThefinalinitializationoftheIDTisperformedbyinvokingtrap_init（）（seethesection“ExceptionHandling”inChapter4）andinit_IRQ（）（seethesection“IRQdatastructures”inChapter4）.
TheTASKLET_SOFTIRQandHI_SOFTIRQareinitializedbyinvokingthesoftirq_init（）function（seethesection“Softirqs”inChapter4）.
Thesystemdateandtimeareinitializedbythetime_init（）function（seethesection“TheLinuxTimekeepingArchitecture”inChapter6）.
Theslaballocatorisinitializedbythekmem_cache_init（）function（seethesection“GeneralandSpecificCaches”inChapter8）.
ThespeedoftheCPUclockisdeterminedbyinvokingthecalibrate_delay（）function（seethesection“DelayFunctions”inChapter6）.
Thekernelthreadforprocess1iscreatedbyinvokingthekernel_thread（）function.Inturn,thiskernelthreadcreatestheotherkernelthreadsandexecutesthe/sbin/initprogram,asdescribedinthesection“KernelThreads”inChapter3.
以上几个函数的执行过程如下图：
图3：
启动函数的执行过程
第二个startup_32（）和start_kernel（）揭示了Linux一生的真谛。
从这里面咱看到了Mr.Process（一个普通的进程）所拥有的一切是怎么得到的。
弄清楚了这些，也就弄清楚了Linux。
Really清楚。
BTW，我做的图怎么那么好看~美感天生在那里，你挡都挡不住，怎么搞怎么好看加专业！
升级会员 