戳藍字「CSDN雲計算」關注我們哦！
作者 | popsuper1982
責編｜阿禿
這是通過三國演義串起作業系統的原理。
第一回：宴桃園豪傑三結義，開放平台啟動內核
話說天下大勢，分久必合，合久必分。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文件系統。
至此，劉備集團從戰略，到戰術，到管理體系才算完全建立，下一篇，我們來看一下劉備是如何建立基業的吧。
福利