只有程序员才能读懂的三国演义（一）

这是通过三国演义串起操作系统的原理，之前写过五篇小马创业篇，这次改编为三国演义篇。

用一个创业故事串起操作系统原理(一)

用一个创业故事串起操作系统原理（二）

用一个创业故事串起操作系统原理（三）

用一个创业故事串起操作系统原理（四）

用一个创业故事串起操作系统原理（五）

回：宴桃园豪杰三结义，开放平台启动内核

话说天下大势，分久必合，合久必分。IT江湖起起伏伏，风云变化。

19世纪80年代，AT&T开始经营长途电话业务，在20世纪30年代，一统有线通信市场，却终在2000年后跌落神坛。

20世纪30年代Motorola摩托罗拉诞生，台摩托罗拉牌汽车收音机问世，20世纪90年代登上无线通信宝座，却终在201X年痛失江山。

20世纪90年代，互联网行业开始崛起，先是网景，微软，雅虎，后是谷歌，Facebook，至今仍然风光无限。

在计算机领域内，也经历着同样的变化，孕育着一代又一代英雄，刘备就是其中的一员。

本来大一统的日子里面，刘备是没有机会的，在相当漫长的一段时间内，IBM作为大型计算机的巨无霸，从20世纪50年代，一直独领风骚到70年代，才遭遇到苹果公司在PC机上的小股骚扰。

终于在1980年，IBM开始稍微重视一下个人计算机市场，但由于可能还是不太重视的缘故(因为大型机照样能够让IBM赚很多很多钱)，IBMPC的研发并没有让华生实验室来完成，而是单独成立一个团队，要求一年内研制成功IBMPC，然而时间紧，任务重，为了快地研制出一台 PC ，这个只有十几人的小组不得不打破以前自己开发计算机全部软硬件的习惯，采用了英特尔公司 8088 芯片作为该电脑的处理器，使用MS-DOS作为其操作系统，从而缔造了日后的微软和英特尔两大帝国。1981年，款IBMPC问世，一经推出就抢掉了apple四分之三的市场。IBM仍然无敌。

但是1982年，事情发生了一些变化，IBM陷入美国司法部反垄断官司，IBM 必须公开一些技术，从而导致了后来无数 IBM-PC 兼容机公司的出现。

从而惠普，康柏，戴尔，联想等兼容机相继推出，从而进入了诸侯混战的阶段，这就是开放的X86时代。

这让刘备感到，机会来了。

刘备自幼熟读兵书，通晓历史，他知道，要想在这乱世立足，要有两样东西，一是人，也即兵，二是地，也即战场。

同理在开放的X86时代，兵也即执行命令的CPU，地也即兵驰骋的战场，也即CPU指令所操作的内存。

招募的兵（CPU）要有三方面的能力：

• 控制单元：兵不需要有太多的思想，而是要服从命令，指哪儿打哪儿

• 运算单元：兵的执行力要强，杀人速度要快

• 数据单元：兵要能够抢占地盘，在战场快速移动，机动灵活

刘备知道，在乱世（X86平台），要会用兵，要会打仗抢地盘（要熟悉X86平台上CPU和内存的合作模式），虽然他现在还没有兵，但是这个场景他已经在梦中重复了N次了。

兵（CPU）是没有思想的，需要他去指挥才能作战。每次作战，他都应该先制定好作战计划（写好程序），作战计划既包括宏观的兵法，例如围魏救赵，欲擒故纵等（多进程，多线程协作模式），也包括微观的阵型，例如蛇形阵，八门金锁阵（一个个函数），当这些都准备好了，就可以交给部队去执行（创建进程）。同一个兵法和阵型，可以用在不同的战斗中，例如兵分两路，一路进攻A城市，一路进攻B城市，可以使用相同的兵法和阵型（一个程序可以创建多个进程）。

对于每次作战，战场（内存）都分为两部分，一部分为中军大营，发号施令的元帅在这部分（代码段），一部分是前方战场，拼杀发生在这部分（数据段）。士兵（CPU）通过不断的从中军大营（代码段）获取指令执行，指令一般包含两部分（CPU指令也包含两部分），部分是操作，例如攻击，防守，移动（CPU指令部分是操作，例如加法，减法，位移），第二部分是目标，例如战场上的某个高地，某个洼地（CPU指令第二部分是操作哪些数据）。

只要作战计划制定完善，士兵们执行得力，在战场上就无往而不胜。（CPU会通过指令指针寄存器不断的从代码段获取指令，交给运算单元执行，从内存读取数据到数据单元，用指令操作数据，将结果写回数据单元并终写回内存，当所有的指令都执行完毕，进程就成功运行完毕了）。

刘备对这些战法了然于胸，但是还处于纸上谈兵的状态，属于通用的知识，真正干起来还需要结合实际情况，不过一旦有了这个创业思想，便是创业的开端了（通用的知识就像BIOS，对于任何一个系统来讲都是一样的，不像将来计算机启动之后的操作系统，可以根据用户的输入进行相应的处理，但是BIOS的启动是整个系统启动的步）。

带着这个思想，刘备虽孑身一人，便开始四处寻找创业伙伴。终于在招兵告示那里，遇到了关羽和张飞。

兄弟三人一见如故，相谈甚欢，刘备说：我自幼熟读兵书，创业想法已久，但是一没钱，二没人。

张飞说：“吾颇有资财，当招募乡勇，与公同举大事，如何。”于是三人桃园结义，祭罢天地，复宰牛设酒，聚乡中勇士，得三百余人。这家创业公司就这样成立了。

这就像系统启动初始，只有有1M的内存空间。在1M空间上面的0xF0000到0xFFFFF这64K映射给ROM，通过读这部分地址，可以访问这个BIOS里面的指令。BIOS要检查一些系统的硬件是不是都好着呢，然后建立基本的中断向量表和中断服务程序，至少要能够使用键盘和鼠标。

接下来，刘备就要带着关羽和张飞以及这仅有的三百人，开始闯荡江湖了。（接下来，BIOS就要开始寻找和加载内核，启动系统了）

第二回：战吕布陶谦让徐州，保护模式空间更大

刘备首先建立的功业是帮助平定黄巾起义，从而被封为安喜县县尉，也即县公安局长，这是刘备事业起步的跃。（在启动盘的个扇区，512K的大小，我们通常称为MBR，Master Boot Record，主引导记录/扇区。这里保存了boot.img，BIOS手册会将他加载到内存中的0x7c00来运行）

在安喜县，刘备并没有实现自己的抱负，反而受督邮欺压，从而鞭打督邮后投奔公孙瓒，因军功封为平原县县令，事业再上升一步。（boot.img做不了太多的事情。他能做的重要的一个事情，就是加载grub2的另一个镜像core.img。core.img由lzma_decompress.img、diskboot.img、kernel.img和一系列的模块组成，boot.img将控制权交给diskboot.img后，diskboot.img的任务就是将core.img的其他部分加载进来，先是解压缩程序lzma_decompress.img，再往下是kernel.img，后是各个模块module对应的映像。）

这个阶段，刘备依旧是小打小闹，但是很快，情况就有了改观。（从diskboot.img到lzma_decompress.img，系统一直处于实模式，在1M的内存空间里面打转，但是从lzma_decompress.img开始，他会调用real_to_prot，切换到保护模式，这样就能在更大的寻址空间里面）

关羽先是温酒斩华雄，后来三兄弟更是三英战吕布，这下在诸侯里面算是打出了名声。

刘备得知陶谦有难，从公孙瓒处借得两千人马与勇将赵云，会同本部三千人，随北海太守孔融一起去救徐州。陶谦为保徐州，见刘备乃汉室宗亲，才德兼备，欲将徐州让与刘备。经三辞三让，终刘备答应权领徐州，终于得到了创业路上的块大的军事重镇，从此摆脱了小打小闹。（系统进入保护模式后，可访问的内存空间增大，对于32位系统可达4G，对于64位系统可达256TB的空间）

在徐州，刘备还得到了几个内部管理的文臣人才，孙乾口才好，擅长外交，

糜竺曾经大力资助刘备，并将妹妹许配给刘备，就是糜夫人，你不要小看糜竺，以为此人在三国演义上低位不高，在历史上，取西川后，糜竺爵位在诸葛亮之上，深得刘备器重。

从此刘备有文有武，就像他对水镜先生说的一样，“备虽不才，文有孙乾、糜竺、简雍之辈，武有关、张、赵云之流，竭忠辅相，颇赖其力。”，从而有了内外的分别，整个班子才算完整。（系统进入保护模式后，开始区分内核态和用户态，用户态不能随便访问内核态，需要通过系统调用）

在徐州的三辞三让，使得刘备进一步确认了自己的创业公司的文化内核——仁义。这个内核是刘备将来成功的根基，就像他自己说的，“今与吾水火相敌者，曹操也。操以急，吾以宽；操以暴，吾以仁；操以谲，吾以忠：每与操相反，事乃可成。若以小利而失信义于天下，吾不忍也。”，从而也奠定了他的失败根源。（kernel.img里面的grub_main会给展示操作系统的列表，让用户进行选择。无论是枭雄的内核，还是仁义的内核，就在这一刻选定了，以后不会再变了）

第三回：领徐州刘备初创业，启内核模块初始化

占据徐州之后，刘备有了自己的领地，可以开始规划作为一个创业公司的“主公”应该做哪些事情了。（内核的启动）

首先，天下还不太平，不免要打仗，仗怎么打，如果保障作战过程中部队的有序管理，要有一个作战管理体系。

由于前期打仗的时候，都是刘备亲自上的，由于关羽张飞尚无经验，所以刘备制定个作战管理的模板（0号进程），但是是虚拟的，不对应一个真实的战斗（操作系统的0号进程init_task是进程列表的个，不对应任何一个运行中的进程）。

如果是大一些的战役，可能由多次战斗组成，还需要刘备居中协调，所以一个作战调度系统也是需要的。（sched_init进程调度初始化）

兵马未动粮草先行，为了让前方的将士可以很好的请求后方的资源，需要有一个作战请求响应体系，只要关羽张飞给后方发一个信号，后方的糜竺，孙乾就可以开始拨发粮草。（操作系统trap_init设置了很多中断门Interrupt Gate，用于处理各种中断，以便快速响应突发事件；还可以提供系统调用，方便进程请求内核资源。）

终于有了徐州城，这个的地盘要好好的规划管理起来。（mm_init用于初始化内存管理系统）

这一切都规划完毕，接下来兄弟们就要干起来，外部的事情就交给关羽张飞，内部的事情就交给糜竺，孙乾。（内核初始化后调用rest_init，里面

件事情是调用kernel_init运行1号进程。这个1号进程会在用户态运行init进程。这是个以用户态运行的进程，之所以叫init，就是做初始化的工作，他是将来所有用户态进程的祖先进程。第二件事情是调用kthreadd运行2号进程。这个2号项目是内核进程的祖先。将来所有的进程都有父进程、祖先进程，会形成一棵进程树。）

第四回：攻袁术中计失徐州，建立进程管理体系

占据徐州以后，刘备接到的个作战任务是攻打袁术，其实是曹操的

驱虎吞狼之计。

糜竺曰：“此又是曹操之计。”玄德曰：“虽是计，王命不可违也。”遂点军马，克日起程，孙乾曰：“可先定守城之人。”玄德曰：“二弟之中，谁人可守？”关公曰：“弟愿守此城。”玄德曰：“吾早晚欲与尔议事，岂可相离？”张飞曰：“小弟愿守此城。”玄德曰：“你守不得此城：你一者酒后刚强，鞭挞士卒；二者作事轻易，不从人谏。吾不放心。”张飞曰：“弟自今以后，不饮酒，不打军士，诸般听人劝谏便了。”

刘备托付完张飞，便和关羽一起商议攻打袁术的作战计划。由于两人都是读过兵书的，所以比较容易达成一致，但是必须要变成士兵们比较容易理解的指令，于是二人对着阵图敲定细节后，方才出发。（C/C++语言都是接近人类的语言，CPU无法执行，需要通过编译，转换为CPU可以听懂的二进制语言。编译好的文件有固定的格式，ELF格式。代码的执行从父进程fork一个子进程，然后在子进程中，调用exec系统调用， 然后到了内核里面，通过load_elf_binary将ELF二进制执行文件加载到子进程内存中，交给CPU执行。）

虽然前方作战还算顺利，然后后方出了篓子。张飞在戒酒宴上，劝吕布岳父曹豹饮酒，曹豹不饮，被张飞鞭打。曹豹连夜差人送信与吕布，约布袭取徐州。张飞因醉后不能力战，只得抛下刘备家眷，出东门而去。徐州为吕布所有，刘备无奈，只好向吕布求和，暂屯小沛。

这次失败，让刘备意识到，前面都是小打小闹，可以通过兄弟情义治军，如果将来治理大的地盘，还是需要军法严明，靠制度而非人治。（应该建立进程管理系统）

所有进程都放在一个task_struct列表中，对于每一个进程，都非常详细地登记了他方方面面的信息。

每一个进程都应该有一个ID，作为这个进程的标识。到时候调度啊、发送信号啊等等，都按ID来，就不会产生歧义。

 

进程应该有运行中的状态，TASK_RUNNING并不是说进程正在运行，而是表示进程在时刻准备运行的状态。这个时候，要看CPU有没有空，有空就运行他，没空就得等着。

有时候，进程运行到一半，需要等待某个条件才能运行下去，这个时候只能睡眠。睡眠状态有两种。一种是TASK_INTERRUPTIBLE，可中断的睡眠状态。这是一种浅睡眠的状态，也就是说，虽然在睡眠，等条件成熟，进程可以被唤醒。

 

另一种睡眠是TASK_UNINTERRUPTIBLE，不可中断的睡眠状态。这是一种深度睡眠状态，不可被唤醒，只能死等条件满足。有了一种新的进程睡眠状态，TASK_KILLABLE，可以终止的新睡眠状态。进程处于这种状态中，他的运行原理类似TASK_UNINTERRUPTIBLE，只不过可以响应致命信号，也即虽然在深度睡眠，但是可以被干掉。

 

一旦一个进程要结束，先进入的是EXIT_ZOMBIE状态，但是这个时候他的父进程还没有使用wait()等系统调用来获知他的终止信息，此时进程就成了僵尸进程。

 

EXIT_DEAD是进程的终状态。

另外，进程运行的统计信息也非常重要。例如，有的CPU很长时间都在执行一个进程，这个时候你就需要特别关注一下；再如，有的时候进程切换过于频繁，这会大大影响他的工作效率。

 

在进程的运行过程中，会有一些统计量，例如进程在用户态和内核态消耗的时间、上下文切换的次数等等。

 

进程之间的亲缘关系也需要维护，任何一个进程都有父进程。所以，整个进程其实就是一棵进程树。而拥有同一父进程的所有进程都具有兄弟关系。

另外，对于进程来讲，权限的控制也很重要。例如，我这个进程能否访问某个文件，能否访问其他的进程，以及我这个进程能否被其他进程访问等等

 

另外，进程运行过程中占用的资源，例如内存、文件系统也需要在进程管理系统里面登记。

 

刘备下令，以后所有的作战任务都要按军法来，才能保证战斗的胜利。

但是此次失败，让刘备丢了来之不易的徐州。后来虽然白门楼计除了吕布，但是生活在曹操和袁绍的夹缝之中，先投奔曹操被煮酒论英雄吓了个半死，后来投奔袁绍兄弟三人分离，险些被杀害，直到关羽千里走单骑，兄弟三人古城相会，事业又重新回到了起点。

经此一劫，刘备也深深感到，自己虽然熟读兵书，但是在兵法方面还是欠缺，需要觅得贤士相助，才能成就大业。

第五回：觅贤才玄德得徐庶，多进程调度有秘方

在荆州，经过司马徽指点，刘备决定去寻找一个可以运筹帷幄的人才。

水镜问曰：“吾久闻明公大名，何故至今犹落魄不偶耶？”玄德曰：“命途多蹇，所以至此。”水镜曰：“不然。盖因将军左右不得其人耳。”玄德曰：“备虽不才，文有孙乾、糜竺、简雍之辈，武有关、张、赵云之流，竭忠辅相，颇赖其力。”水镜曰：“关、张、赵云，皆万人敌，惜无善用之之人。若孙乾、糜竺辈，乃白面书生，非经纶济世之才也。”玄德急问曰：“奇才安在？果系何人？”水镜曰：“伏龙、凤雏，两人得一，可安天下。”

刘备得到的个人才，既不是卧龙，也非凤雏，而是徐庶，这是刘备的个军师，从此刘备才有了复杂的战场运筹调度机制。

徐庶辅佐刘备，初次用兵，连败曹操，使赵云一举破了八门金锁阵，关羽也取了樊城。并破解了曹仁的劫寨。

却说单福正与玄德在寨中议事，忽信风骤起。福曰：“今夜曹仁必来劫寨。”玄德曰：“何以敌之？”福笑曰：“吾已预算定了。”遂密密分拨已毕。至二更，曹仁兵将近寨，只见寨中四围火起，烧着寨栅。曹仁知有准备，急令退军。赵云掩杀将来。仁不及收兵回寨，急望北河而走。将到河边，才欲寻船渡河，岸上一彪军杀到：为首大将，乃张飞也。曹仁死战，李典保护曹仁下船渡河。曹军大半淹死水中。曹仁渡过河面，上岸奔至樊城，令人叫门。只见城上一声鼓响，一将引军而出，大喝曰：“吾已取樊城多时矣！”众惊视之，乃关云长也。仁大惊，拨马便走。云长追杀过来。曹仁又折了好些军马，星夜投许昌。于路打听，方知有单福为军师，设谋定计。

在遇到徐庶之前，刘备的战场调度都是单线的，和谁打，如何打之类的。有了徐庶，战场调度就变成了多线配合的，将一场战役分为多个战斗，多个将领配合完成，互相接应。

在Linux里面，无论是进程，还是线程，到了内核里面，我们统一都叫任务，由一个统一的结构task_struct进行管理。

对于操作系统来讲，他面对的CPU的数量是有限的，干活儿都是他们，但是进程数目远远超过CPU的数目，因而就需要进行进程的调度，有效地分配CPU的时间，既要保证进程的快响应，也要保证进程之间的公平。

如何调度呢？一种方式就是排队。一个CPU上有一个队列，队列里面是一系列sched_entity，每个sched_entity都属于一个task_struct，代表进程或者线程。

调度要解决的个问题是，每一个CPU每过一段时间，都要想一下，CPU的队列里面有这么多的进程或者线程，应该取出哪一个来执行？这就是调度规则或者调度算法的问题。

在Linux里面，讲究的公平可不是一般的公平，而是CFS调度算法，CFS全称是Completely Fair Scheduling，完全公平调度。这个算法主要由fair_sched_class实现，fair就是公平的意思。

CPU会提供一个时钟，过一段时间就触发一个时钟中断。就像咱们的表滴答一下，这个我们叫Tick。CFS会为每一个进程安排一个虚拟运行时间vruntime。如果一个进程在运行，随着时间的增长，也就是一个个Tick的到来，进程的vruntime将不断增大。没有得到执行的进程vruntime不变。

 

显然，那些vruntime少的，原来受到了不公平的对待，需要给他补上，所以会优先运行这样的进程。

 

这有点儿像让你把一筐球平均分到N个口袋里面，你看着哪个少，就多放一些；哪个多了，就先不放。这样经过多轮，虽然不能保证球完全一样多，但是也差不多公平。

 

有时候，进程会分优先级，如何给优先级高的进程多分时间呢？

 

这个简单，就相当于N个口袋，优先级高的袋子大，优先级低的袋子小。这样球就不能按照个数分配了，要按照比例来，大口袋的放了一半和小口袋放了一半，里面的球数目虽然差很多，也认为是公平的。

函数update_curr用于更新进程运行的统计量vruntime ，CFS还需要一个数据结构来对vruntime进行排序，找出小的那个。在这里使用的是红黑树。红黑树的的节点是sched_entity，里面包含vruntime。

 

调度算法的本质就是解决下一个进程应该轮到谁运行的问题，这个逻辑在fair_sched_class.pick_next_task中完成。

 

调度要解决的第二个问题是，什么时候切换任务？也即，什么时候，CPU应该停下一个进程，换另一个进程运行？

 

主要有两种方式。

 

方式一，A进程做着做着，里面有一条指令sleep，也就是要休息一下，或者等待某个I/O事件。那没办法了，要主动让出CPU，然后可以开始做B进程。主动让出CPU的进程，会主动调用schedule()函数。

 

在schedule()函数中，会通过fair_sched_class.pick_next_task，在红黑树形成的队列上取出下一个进程，然后调用context_switch进行进程上下文切换。

 

进程上下文切换主要干两件事情，一是切换进程空间，也即进程的内存。二是切换寄存器和CPU上下文，记录下来，方便以后接着干。

 

方式二，A进程做着做着，旷日持久，实在受不了了。是时候切换到B进程了。这个时候叫作A进程被被动抢占。

 

抢占还要通过CPU的时钟Tick，来衡量进程的运行时间。时钟Tick一下，是很好查看是否需要抢占的时间点。时钟中断处理函数会调用scheduler_tick()，他会调用fair_sched_class的task_tick_fair，在这里面会调用update_curr更新运行时间。当发现当前进程应该被抢占，不能直接把他踢下来，而是把他标记为应该被抢占，打上一个标签TIF_NEED_RESCHED。

 

另外一个可能抢占的场景发生在，当一个进程被唤醒的时候。一个进程在等待一个I/O的时候，会主动放弃CPU。但是，当I/O到来的时候，进程往往会被唤醒。这个时候是一个时机。当被唤醒的进程优先级高于CPU上的当前进程，就会触发抢占。如果应该发生抢占，也不是直接踢走当然进程，而也是将当前进程标记为应该被抢占，打上一个标签TIF_NEED_RESCHED。

 

真正的抢占还是需要上下文切换，也就是需要那么一个时刻，让正在运行中的进程有机会调用一下schedule。调用schedule有以下四个时机。

• 对于用户态的进程来讲，从系统调用中返回的那个时刻，是一个被抢占的时机。

• 对于用户态的进程来讲，从中断中返回的那个时刻，也是一个被抢占的时机。

• 对内核态的执行中，被抢占的时机一般发生在preempt_enable()中。在内核态的执行中，有的操作是不能被中断的，所以在进行这些操作之前，总是先调用preempt_disable()关闭抢占。再次打开的时候，就是一次内核态代码被抢占的机会。

• 在内核态也会遇到中断的情况，当中断返回的时候，返回的仍然是内核态。这个时候也是一个执行抢占的时机。

可是好景不长，徐庶被曹操用计骗取了。但是徐庶回马荐诸葛，推荐了一个新的调度人才。

第六回：顾茅庐知三分天下，内存空间管理有序

于是刘备三顾茅庐，请诸葛亮出山。

刘备惊喜的发现，诸葛亮可不仅仅是一个战场的调度人才，而是一个更高高度的战略人才，对全局形势了如支撑。

在Linux操作系统中，内存管理包含下面的三个部分。

• ，物理内存的管理，相当于诸葛亮对于整个地盘的规划

• 第二，虚拟地址的管理，也即在某次战斗的视角，相当于诸葛亮对于某次战斗的阵法布局

• 第三，虚拟地址和物理地址如何映射的问题，也即如何通过一次次战斗来赢得整个地盘。

首先，在隆中对里面，诸葛亮先分析了当前的局势。

孔明曰：“自董卓造逆以来，天下豪杰并起。曹操势不及袁绍，而竟能克绍者，非惟天时，抑亦人谋也。今操已拥百万之众，挟天子以令诸侯，此诚不可与争锋。孙权据有江东，已历三世，国险而民附，此可用为援而不可图也。荆州北据汉、沔，利尽南海，东连吴会，西通巴、蜀，此用武之地，非其主不能守；是殆天所以资将军，将军岂有意乎？益州险塞，沃野千里，天府之国，高祖因之以成帝业；今刘璋暗弱，民殷国富，而不知存恤，智能之士，思得明君。将军既帝室之胄，信义著于四海，总揽英雄，思贤如渴，若跨有荆、益，保其岩阻，西和诸戎，南抚彝、越，外结孙权，内修政理；待天下有变，则命一上将将荆州之兵以向宛、洛，将军身率益州之众以出秦 川，百姓有不箪食壶浆以迎将军者乎？诚如是，则大业可成，汉室可兴矣。此亮所以为将军谋者也。惟将军图之。”

诸葛亮将的地盘分成几个块，逐次分析。

Linux对于物理内存的管理，也是同样的思路。

物理内存分节点，每个节点用struct pglist_data表示。

 

每个节点里面再分区域，用于区分内存不同部分的不同用法。ZONE_NORMAL是常用的区域。ZONE_MOVABLE是可移动区域。我们通过将物理内存划分为，可移动分配区域和不可移动分配区域，来避免内存碎片。每个区域用struct zone表示，也放在一个数组里面。

 

每个区域里面再分页。默认的大小为4KB。

 

物理页面分配的时候，使用伙伴系统。

 

空闲页放在struct free_area里面，每一页用struct page表示。

 

把所有的空闲页分组为11个页块链表，每个块链表分别包含很多个大小的页块，有1、2、4、8、16、32、64、128、256、512和1024个连续页的页块。大可以申请1024个连续页，对应4MB大小的连续内存。每个页块的个页的物理地址是该页块大小的整数倍。

例如，要请求一个128个页的页块时，我们要先检查128个页的页块链表是否有空闲块。如果没有，则查256个页的页块链表；如果有空闲块的话，则将256个页的页块分成两份，一份使用，一份插入128个页的页块链表中。如果还是没有，就查512个页的页块链表；如果有的话，就分裂为128、128、256三个页块，一个128的使用，剩余两个插入对应页块链表。

把物理页面分成一块一块大小相同的页，这样带来的另一个好处是，当有的内存页面长时间不用了，可以暂时写到硬盘上，我们称为换出。一旦需要的时候，再加载进来，就叫作换入。这样可以扩大可用物理内存的大小，提高物理内存的利用率。在内核里面，有一个进程kswapd，可以根据物理页面的使用情况，对页面进行换入换出。

另外，诸葛亮在阵法，排兵布阵上，也是相当有一套的。

Linux在虚拟地址管理上，是这样管理的，虚拟空间一切二，一部分用来放内核的东西，称为内核空间；一部分用来放进程的东西，称为用户空间。

用户空间在下，在低地址，我们假设是0号到29号会议室；内核空间在上，在高地址，我们假设是30号到39号会议室。这两部分空间的分界线，因为32位和64位的不同而不同。

对于普通进程来说，内核空间的那部分，虽然虚拟地址在那里，但是不能访问。这就像作为普通员工，你明明知道财务办公室在这个30号会议室门里面，但是门上挂着“闲人免进”，你只能在自己的用户空间里面折腾。

我们从低位开始排起，先是Text Segment、Data Segment和BSS Segment。Text Segment是存放二进制可执行代码的位置，Data Segment存放静态常量，BSS Segment存放未初始化的静态变量。

接下来是堆段。堆是往高地址增长的，是用来动态分配内存的区域，malloc就是在这里面分配的。

 

接下来的区域是Memory Mapping Segment。这块地址可以用来把文件映射进内存用的，如果二进制的执行文件依赖于某个动态链接库，就是在这个区域里面将so文件映射到了内存中。

 

再下面就是栈地址段了，主线程的函数调用的函数栈就是用这里的。

 

如果普通进程还想进一步访问内核空间，是没办法的，只能眼巴巴地看着。如果需要进行更高权限的工作，就需要调用系统调用，进入内核。

 

一旦进入了内核，就换了一副视角。刚才是普通进程的视角，觉着整个空间是它独占的，没有其他进程存在。当然另一个进程也这样认为，因为它们互相看不到对方。这也就是说，不同进程的0号到29号会议室放的东西都不一样。

 

但是，到了内核里面，无论是从哪个进程进来的，看到的是同一个内核空间，看到的是同一个进程列表。虽然内核栈是各用个的，但是如果想知道的话，还是能够知道每个进程的内核栈在哪里的。所以，如果要访问一些公共的数据结构，需要进行锁保护。也就是说，不同的进程进入到内核后，进入的30号到39号会议室是同一批会议室。

 

内核的代码访问内核的数据结构，大部分的情况下都是使用虚拟地址的。虽然内核代码权限很大，但是能够使用的虚拟地址范围也只能在内核空间，也即内核代码访问内核数据结构，只能用30号到39号这些编号，不能用0到29号，因为这些是被进程空间占用的。而且，进程有很多个。你现在在内核，但是你不知道当前指的0号是哪个进程的0号。

 

在内核里面也会有内核的代码，同样有Text Segment、Data Segment和BSS Segment，内核代码也是ELF格式的。

另外，诸葛亮对于如何通过一次一次的战役，终获得整块版图，也是有规划的。

在Linux中，我们需要找到一种策略，实现从虚拟地址到物理地址的转换。

为了能够定位和访问每个页，需要有个页表，保存每个页的起始地址，再加上在页内的偏移量，组成线性地址，就能对于内存中的每个位置进行访问了。

虚拟地址分为两部分，页号和页内偏移。页号作为页表的索引，页表包含物理页每页所在物理内存的基地址。这个基地址与页内偏移的组合就形成了物理内存地址。

32位环境下，虚拟地址空间共4GB。如果分成4KB一个页，那就是1M个页。每个页表项需要4个字节来存储，那么整个4GB空间的映射就需要4MB的内存来存储映射表。如果每个进程都有自己的映射表，100个进程就需要400MB的内存。对于内核来讲，有点大了 。

 

页表中所有页表项必须提前建好，并且要求是连续的。如果不连续，就没有办法通过虚拟地址里面的页号找到对应的页表项了。

 

那怎么办呢？我们可以试着将页表再分页，4G的空间需要4M的页表来存储映射。我们把这4M分成1K（1024）个4K，每个4K又能放在一页里面，这样1K个4K就是1K个页，这1K个页也需要一个表进行管理，我们称为页目录表，这个页目录表里面有1K项，每项4个字节，页目录表大小也是4K。

 

页目录有1K项，用10位就可以表示访问页目录的哪一项。这一项其实对应的是一整页的页表项，也即4K的页表项。每个页表项也是4个字节，因而一整页的页表项是1k个。再用10位就可以表示访问页表项的哪一项，页表项中的一项对应的就是一个页，是存放数据的页，这个页的大小是4K，用12位可以定位这个页内的任何一个位置。

 

这样加起来正好32位，也就是用前10位定位到页目录表中的一项。将这一项对应的页表取出来共1k项，再用中间10位定位到页表中的一项，将这一项对应的存放数据的页取出来，再用后12位定位到页中的具体位置访问数据。

你可能会问，如果这样的话，映射4GB地址空间就需要4MB+4KB的内存，这样不是更大了吗？当然如果页是满的，当时是更大了，但是，我们往往不会为一个进程分配那么多内存。

 

比如说，上面图中，我们假设只给这个进程分配了一个数据页。如果只使用页表，也需要完整的1M个页表项共4M的内存，但是如果使用了页目录，页目录需要1K个全部分配，占用内存4K，但是里面只有一项使用了。到了页表项，只需要分配能够管理那个数据页的页表项页就可以了，也就是说，多4K，这样内存就节省多了。

 

当然对于64位的系统，两级肯定不够了，就变成了四级目录，分别是全局页目录项PGD（Page Global Directory）、上层页目录项PUD（Page Upper Directory）、中间页目录项PMD（Page Middle Directory）和页表项PTE（Page Table Entry）。

第七回：善内政诸葛兴农业，全系统一切皆文件

另外，刘备还发现诸葛亮是个内政天才。

战场是打完就走的，但是领土是不断积累的，如何发展农业，保障后援，如果管理粮草，诸葛亮也是有一套的。

在《诸葛亮集便宜策》中他指出，“唯劝农业，无夺其时，唯薄赋敛，无尽民财，如此富国安家，不以宜乎？”

同理，在内存中的数据是随着进程执行完毕而消失的，需要长期保存的数据需要写到文件系统上。

规划文件系统的时候，需要考虑以下几点。

 

点，文件系统要有严格的组织形式，使得文件能够以块为单位进行存储。

 

这就像图书馆里，我们会给设置一排排书架，然后再把书架分成一个个小格子。有的项目存放的资料非常多，一个格子放不下，就需要多个格子来进行存放。我们把这个区域称为存放原始资料的仓库区。对于操作系统，硬盘分成相同大小的单元，我们称为块。一块的大小是扇区大小的整数倍，默认是4K，用来存放文件的数据部分。这样一来，如果我们像存放一个文件，就不用给他分配一块连续的空间了。我们可以分散成一个个小块进行存放。这样就灵活得多，也比较容易添加、删除和插入数据。

 

第二点，文件系统中也要有索引区，用来方便查找一个文件分成的多个块都存放在了什么位置。

 

这就好比，图书馆的书太多了，为了方便查找，我们需要专门设置一排书架，这里面会写清楚整个档案库有哪些资料，资料在哪个架子的哪个格子上。这样找资料的时候就不用跑遍整个档案库，只要在这个书架上找到后，直奔目标书架就可以了。

 

在Linux操作系统里面，每一个文件有一个Inode，inode的“i”是index的意思，其实就是“索引”。inode里面有文件的读写权限i_mode，属于哪个用户i_uid，哪个组i_gid，大小是多少i_size_io，占用多少个块i_blocks_io。“某个文件分成几块、每一块在哪里“，这些信息也在inode里面，保存在i_block里面。

第三点，如果文件系统中有的文件是热点文件，近期经常被读取和写入，文件系统应该有缓存层。

 

这就相当于图书馆里面的热门图书区，这里面的书都是畅销书或者是常常被借还的图书。因为借还的次数比较多，那就没必要每次有人还了之后，还放回遥远的货架，我们可以专门开辟一个区域，放置这些借还频次高的图书。这样借还的效率就会提高。

 

第四点，文件应该用文件夹的形式组织起来，方便管理和查询。

 

这就像在图书馆里面，你可以给这些资料分门别类，比如分成计算机类、文学类、历史类等等。这样你也容易管理，项目组借阅的时候只要在某个类别中去找就可以了。

 

在文件系统中，每个文件都有一个名字，我们访问一个文件，希望通过他的名字就可以找到。文件名就是一个普通的文本，所以文件名经常会冲突，不同用户取相同的名字的情况会经常出现的。

 

要想把很多的文件有序地组织起来，我们就需要把他们做成目录或者文件夹。这样，一个文件夹里可以包含文件夹，也可以包含文件，这样就形成了一种树形结构。我们可以将不同的用户放在不同的用户目录下，就可以一定程度上避免了命名的冲突问题。

 

第五点，Linux内核要在自己的内存里面维护一套数据结构，来保存哪些文件被哪些进程打开和使用。

 

这就好比，图书馆里会有个图书管理系统，记录哪些书被借阅了，被谁借阅了，借阅了多久，什么时候归还。

 

这个图书管理系统尤为重要，如果不是很方便使用，以后项目中积累了经验，就没有人愿意往知识库里面放了。

无论哪个进程，都可以通过write系统调用写入知识库。

 

对于每一个进程，打开的文件都有一个文件描述符。files_struct里面会有文件描述符数组。每个一个文件描述符是这个数组的下标，里面的内容指向一个struct file结构，表示打开的文件。这个结构里面有这个文件对应的inode，重要的是这个文件对应的操作file_operation。如果操作这个文件，就看这个file_operation里面的定义了。

 

每一个打开的文件，都有一个dentry对应，虽然我们叫作directory entry，但是他不仅仅表示文件夹，也表示文件。他重要的作用就是指向这个文件对应的inode。

 

如果说file结构是一个文件打开以后才创建的，dentry是放在一个dentry cache里面的。文件关闭了，他依然存在，因而他可以更长期的维护内存中的文件的表示和硬盘上文件的表示之间的关系。

 

inode结构就表示硬盘上的inode，包括块设备号等。这个inode对应的操作保存在inode operations里面。真正写入数据，是写入硬盘上的文件系统，例如ext4文件系统。

至此，刘备集团从战略，到战术，到管理体系才算完全建立，下一篇，我们来看一下刘备是如何建立基业的吧。