第一部分 基礎(chǔ)內(nèi)容

1.操作系統(tǒng)基礎(chǔ)

    操作系統(tǒng)是計算機(jī)硬件系統(tǒng)與用戶程序間重要環(huán)節(jié)，理解操作系統(tǒng)的原理是編寫優(yōu)秀代碼的基礎(chǔ)。教課書中闡述的操作系統(tǒng)一般由5部分組成。

一個最簡單的操作系統(tǒng)，可以不需要文件，不需要網(wǎng)絡(luò)，只要實現(xiàn)多進(jìn)程，且進(jìn)程間也不需要通信，相互獨立。那么這樣一個簡單的OS僅需要兩塊內(nèi)容：進(jìn)程管理、內(nèi)存管理。這兩方面內(nèi)容是相輔相成，不可分割的，因為現(xiàn)在計算機(jī)系統(tǒng)的基本架構(gòu)仍是指令存儲-執(zhí)行。內(nèi)存管理很大程度上依賴處理器的硬件支持，而進(jìn)程管理則是在這個基礎(chǔ)上，用軟件的方式虛擬化出的一套機(jī)制，使得多個程序能同時使用計算機(jī)。

    下面先介紹一些與操作系統(tǒng)相關(guān)的基礎(chǔ)知識。

1.1操作系統(tǒng)的啟動簡介

    計算機(jī)中最初始的是硬件，理解操作系統(tǒng)的啟動雖不難，但卻可以讓人去除對操作系統(tǒng)的敬畏之情，給我印象最深的就是《自己動手寫操作系統(tǒng)》開篇講的，10分鐘寫出一個OS，也正是這個才鼓勵我學(xué)習(xí)了下面的內(nèi)容。

一般PC機(jī)的啟動過程如下：

1. 上電自檢，當(dāng)電壓穩(wěn)定后，釋放reset，控制權(quán)交給CPU（一般由一些特定的控制芯片完成）；
2. CPU的地址指針首先指向BIOS，由BIOS執(zhí)行一些必要的檢查和初始化，BIOS最后把啟動盤中的第一個扇區(qū)加載到0x7C00處（即boot.bin），并跳轉(zhuǎn)到此處執(zhí)行；
3. Boot.bin主要是把loader.bin加載到0x9000：0x200處，并跳轉(zhuǎn)到此處執(zhí)行；
4. Loader.bin讀出內(nèi)存信息，并把kernel.bin加載到0x8000：0處，然后進(jìn)入保護(hù)模式，在保護(hù)模式下初始化頁目錄頁表，并啟動分頁機(jī)制，然后把kernel.bin按照elf頭信息以及l(fā)d –Text xx的參數(shù)移到正確的位置，并跳入內(nèi)核起始點；
5. 操作系統(tǒng)內(nèi)核開始工作。

b)是計算機(jī)轉(zhuǎn)由軟件控制的關(guān)鍵，可以直接寫一個顯示的小例子，然后dd到硬盤的引導(dǎo)扇區(qū)（即第一個扇區(qū)），重啟計算機(jī)就會發(fā)現(xiàn)屏幕上顯示你所要的字符。

    至于boot.bin為什么要加載一個loader.bin進(jìn)來，主要是boot.bin只有512byte，太小了，做不了太多事。Loader.bin則沒有限制，可以做很多工作，把kernel.bin加載到內(nèi)存中，利用BOIS中斷服務(wù)獲得系統(tǒng)的一些硬件信息，如內(nèi)存大小、硬盤信息等，并存放在內(nèi)存相應(yīng)位置，供OS以后使用。然后最重要的就是使計算機(jī)進(jìn)入保護(hù)模式，做一些初始化工作：gdt，idt，A20線，分頁等， 并把控制權(quán)交給kernel.bin。

    注意進(jìn)保護(hù)模式前，內(nèi)存中主要是BOIS（固化在ROM中）及BOIS初始化出來的一些數(shù)據(jù)結(jié)構(gòu)，如實模式下的中斷向量表等。因此在進(jìn)保護(hù)模式前，BOIS服務(wù)（即軟中斷int xx）仍是可用的，事實上啟動過程中加載、顯示兩大操作正是利用的BOIS的int 13和int 10中斷服務(wù)例程，另外初始化硬件，獲得諸如內(nèi)存信息、硬盤信息等都是通過BOIS服務(wù)完成的。

    進(jìn)入保護(hù)模式后，中斷向量的方式和實模式完全不一樣了，此時BOIS不再有用，而是真正要靠OS來接管一切，從頭開始。

1.2保護(hù)模式下的存儲機(jī)制

    在實模式下，采用分段的存儲機(jī)制，尋址以seg：offset方式尋址。其中seg是段描述符16bit，offset為16bit，總地址為seg<<4+offset，最大地址為1M。

    在保護(hù)模式下，尋址也采用seg：offset方式，seg仍為16bit，但offset為32bit，且實現(xiàn)的機(jī)制也大不相同。其中最關(guān)鍵的是GDT表，如下圖所示

GDT表放在內(nèi)存中，其地址有GDTR寄存器標(biāo)識。Seg中存放的為一個索引值，指向GDT表中的某一項。GDT表中的每一項稱為描述符DESCRIPTOR，它里面包含了該段的base基址即該段的limit。其中base為32bit的，加上offset即為所要尋址的線性地址。

    GDT表只有一個，光靠它來實現(xiàn)多進(jìn)程的地址空間分割還不夠，處理器還提供LDT機(jī)制，如下圖所示：

    寄存器GDTR是一個32bit的，標(biāo)識了GDT表的地址，LDTR寄存器是16bit的，其中存放的卻是一個選擇子SELECTOR，索引GDT表中的某一項。Seg中的TI=1，則表明這是一個LDT尋址，根據(jù)LDTR中的索引值找到GDT表中的相應(yīng)項，得到LDT表的基址base。Seg中的索引值在LDT表中索引到相應(yīng)項，得到實際base，加上offset就是線性地址了。

    GDT表只有一個，LDT表卻可以有很多，事實上是每個進(jìn)程都有自己的LDT表，且它們都在GDT表中有相應(yīng)項對應(yīng)。在切換進(jìn)程時，只要改變LDTR寄存器的值，就可以輕易實現(xiàn)各個進(jìn)程使用自己的LDT表。這樣就可以實現(xiàn)多進(jìn)程的地址空間分割了，因為各個進(jìn)程可以使用相同的seg段，但所指向的實際地址卻可不同，不相沖突，就好像每個進(jìn)程都獨享了所有地址段。

    上面說了分段機(jī)制得到的是線性地址，要變?yōu)閷嶋H的物理地址，還需要分頁機(jī)制。如果說GDT+LDT方式的分段，使得多進(jìn)程在表面上實現(xiàn)了地址空間分割，那么分頁機(jī)制則在表面上是地址空間分割的情況下，實現(xiàn)了物理地址并不需要分割，不需要連續(xù)，甚至可以重疊。

    如上圖所示，內(nèi)存中有一個頁目錄表，其地址有CR3寄存器標(biāo)識，頁目錄表中有1024項PDE，由線性地址的高10bit索引；每個PDE為32bit，指向一個頁表，每個頁表中有1024項PTE，有線性地址的中間10bit索引；每個PTE為32bit，指向該頁框的基址，每個頁框有4KB大小，由線性地址的低12bit尋址。

    分段機(jī)制使得各個進(jìn)程使用相同的段，但由于各個進(jìn)程的LDT表項所指的基址base不同，從而實現(xiàn)了線性空間的分割。但分頁機(jī)制使得分割的線性空間可以隨意映射到任意物理地址。這在后面詳講。

1.3特權(quán)級與堆棧問題

X86架構(gòu)的CPU分了4個特權(quán)級，linux只用了0級作內(nèi)核級，3級作用戶級。一般情況下，jmp和call的轉(zhuǎn)移，代碼段數(shù)據(jù)段的訪問遵循以下規(guī)則：

    特權(quán)級的表現(xiàn)形式有3種，所有光說低、高還不夠明確，而且上述的只是一般的轉(zhuǎn)移，必要時還可以通過調(diào)用門來實現(xiàn)不同特權(quán)級間的切換。更為確切的比較方法將在下面講述，首先看一下特權(quán)級的3種表現(xiàn)形式。

CPL：正在執(zhí)行的程序或任務(wù)的特權(quán)級，有CS、SS的1～0bit體現(xiàn)；

DPL：段或門的特權(quán)級，被存儲在段描述符或門描述符的DPL字段中；

RPL：由段選擇子的1～0bit體現(xiàn)。

    下面主要關(guān)心在不同特權(quán)級間切換時，堆棧的情況。代碼在相同特權(quán)級間跳轉(zhuǎn)時，堆棧不變，在不同特權(quán)級間跳轉(zhuǎn)時，則會用到兩個不同的堆棧。

如上圖所示，無特權(quán)級變化的情況主要發(fā)生在內(nèi)核態(tài)的進(jìn)程被中斷時，而用戶態(tài)下的進(jìn)程被中斷則會發(fā)生特權(quán)級變化。

    從低優(yōu)先級切換到高優(yōu)先級，會使用另一個堆棧，并把之前的ss、esp壓入新的堆棧，以便返回時可以直接找到以前的堆棧。但是怎么找到高優(yōu)先級的堆棧的呢？這就需要用到TSS段，每個進(jìn)程都有自己的TSS段，和LDT一樣，TSS段在GDT表中也有相應(yīng)的描述項，該項由TR寄存器索引，所以進(jìn)程切換時，和LDTR寄存器一樣，TR寄存器也要相應(yīng)地改。

1.4中斷

進(jìn)程間的切換當(dāng)然要各種各樣的中斷來支持。中斷一般指程序執(zhí)行過程中因硬件而隨機(jī)發(fā)生，通常用來處理外部事件，當(dāng)然軟件通過執(zhí)行int n指令也可以產(chǎn)生中斷；異常一般指處理器執(zhí)行過程中檢測到錯誤，如除零等?？傊鼈兌际浅绦驁?zhí)行過程中的強(qiáng)制性轉(zhuǎn)移，轉(zhuǎn)移到相應(yīng)的處理程序。

保護(hù)模式下，x86處理器支持共256個中斷異常處理。

首先看看機(jī)器的中斷異常的實現(xiàn)機(jī)制。異常及軟件中斷int n，都是程序執(zhí)行時，遇到相應(yīng)的指令就跳轉(zhuǎn)，與硬件無關(guān)。另外，機(jī)器提供兩個引腳，實現(xiàn)外部中斷，一個是NMI，不可屏蔽中斷，一般用作災(zāi)難性的處理，如斷電等，另一個是INTR引腳，一般連接中斷處理芯片8259A來實現(xiàn)外部中斷。

然后看中斷向量表IDT，里面有256項，每一項定義了該號中斷發(fā)生時，應(yīng)執(zhí)行的內(nèi)容。在實模式下，中斷向量表中沒一項可能就是一條跳轉(zhuǎn)指令，跳到中斷處理程序處。而在保護(hù)模式下，中斷向量表IDT里有256個門描述符，即中斷門。每一個中斷對應(yīng)一個中斷門描述符，從而找到相應(yīng)的處理程序，中斷門的結(jié)構(gòu)功能與前面講的調(diào)用門幾乎是一樣的。

所有的中斷處理程序都是內(nèi)核態(tài)下的函數(shù)，所以我們這里所有的selector都指向唯一的代碼段描述符SELECTOR_KERNEL_CS = 0x8，只要設(shè)置好每項的offset，指向各個中斷處理程序的函數(shù)入口。

2.linux0.11內(nèi)核運行框架

    這里致力于弄清楚內(nèi)核是如何運轉(zhuǎn)起來的，先不關(guān)心以什么策略使它運轉(zhuǎn)得更高效。內(nèi)核運轉(zhuǎn)的關(guān)鍵就是多進(jìn)程，理清楚進(jìn)程的幾方面是關(guān)鍵。

1. 由哪些部分構(gòu)成

1. 何時切換（哪些機(jī)制使它切換）
2. 怎么切換并保證空間地址、數(shù)據(jù)不發(fā)生錯誤

進(jìn)程運行離不開內(nèi)存，或者說是建立在內(nèi)存管理之上的，那么內(nèi)存的情況是怎么樣的？針對這兩方面，總結(jié)出下面這張圖。

    針對這張圖需要說明的幾點是：

1. 內(nèi)核kernel本身不會運行，它包含一組內(nèi)核函數(shù)庫，為所有進(jìn)程所共享。系統(tǒng)中時刻都有一個進(jìn)程在運行，或運行于用戶態(tài)，或運行于內(nèi)核態(tài)，在內(nèi)核態(tài)下時可用內(nèi)核函數(shù)庫。大部分內(nèi)核函數(shù)會設(shè)計成可重入的（只有局部變量、堆棧實現(xiàn)），所以允許多個進(jìn)程同時運行在內(nèi)核態(tài)；但有些函數(shù)不可避免的用到全局變量，這時有兩種方法，一是運行這些函數(shù)的進(jìn)程不允許被搶占，二是精心設(shè)計同步方法。
2. GDT表中有K_CS/K_DS，供進(jìn)程在內(nèi)核態(tài)下時使用。因為進(jìn)程進(jìn)入內(nèi)核態(tài)只有一種可能，就是發(fā)生中斷，1.4節(jié)已經(jīng)說明了IDG表中所有門描述符的SELECTOR都是SELECTOR_KERNEL_CS = 0x8，因此K_CS/K_DS是被所有進(jìn)程共用的內(nèi)核態(tài)描述符（基址），即整個內(nèi)核函數(shù)空間是所有進(jìn)程共享的。
3. 內(nèi)核為每個進(jìn)程維護(hù)了一個task_struct和k_stack，它們通常放在一個頁框內(nèi)，有union結(jié)構(gòu)生成。k_stack則供進(jìn)程在內(nèi)核態(tài)時用（1.3節(jié)已說明不同特權(quán)級間的切換會造成堆棧的切換）。Task_struct為進(jìn)程管理用，主要包含了進(jìn)程所管理的資源如文件、IO、信號等；還包含了各種運行時的變量屬性如優(yōu)先級、時間片、進(jìn)程號組等；與運行框架最緊密相關(guān)的是LDT表段、TSS段，GDT表中還為每個進(jìn)程準(zhǔn)備了一個LDTn描述符，和一個TSSn描述符，與這兩個私有段對應(yīng)。
4. 進(jìn)程創(chuàng)建時，就在GDT表中為它初始化好LDTn和TSSn，且基址分別指向task_struct中的LDT表段和TSS段。
5. TSS段是支持進(jìn)程運行、切換的關(guān)鍵，它主要包含3部分關(guān)鍵的內(nèi)容：1）進(jìn)程的運行狀態(tài)（各種寄存器），當(dāng)要切換到一個進(jìn)程時，通過ljmp tss_sel指令，tss_sel是TSSn在GDT表中的索引，這可以由進(jìn)程組號直接得到，處理器首先將該tss_sel裝入TR寄存器，然后由GDT表中TSSn找到進(jìn)程task_struct中的TSS段，彈出TSS段中保存的狀態(tài)；2）ldt_sel選擇子，它是LDTn在GDT表中的索引，ljmp tss_sel指令也會將它裝載到LDTR寄存器中，從而使進(jìn)程正確尋址；3）ss0、esp0指向進(jìn)程的內(nèi)核棧頂，若進(jìn)程在內(nèi)核態(tài)時被中斷，堆棧不會切換，用不到esp0，當(dāng)進(jìn)程要從內(nèi)核態(tài)切回用戶態(tài)時，一定保證內(nèi)核棧中為空了，下次再切到內(nèi)核態(tài)時，仍有esp0指向內(nèi)核棧頂，所有esp0不需要變化。
6. LDT表段為進(jìn)程提供正確的線性基址。如一共64個進(jìn)程，所有進(jìn)程共享一個頁目錄表，每個可有16項PDE，16個頁表，16*1024項PTE，指向16*1024個頁框，共64M的線性地址空間。這樣就將線性空間有效分割開了，互不相關(guān)，用戶程序編譯時只需關(guān)心offset地址。
7. 上述方案共用一個頁目錄表，從而限制每個進(jìn)程只有64M線性空間，目前的linux系統(tǒng)通常是每個進(jìn)程有自己的頁目錄表，即每個進(jìn)程完全有一套自己的線性空間，這才是真正的分割、互補相關(guān)。此時每個進(jìn)程可有4G空間，但每次切換進(jìn)程時應(yīng)改變CR3寄存器的值（它應(yīng)該會保存在task_struct中），LDT將不再需要。事實上，目前的linux系統(tǒng)進(jìn)程狀態(tài)采用軟件保存，TSS段也是不需要的，只要僅一個全局TSS段，用于用戶態(tài)內(nèi)核態(tài)切換時堆棧的切換，可想而知，每次切換到一個新進(jìn)程，該全局TSS段的esp0應(yīng)修改為該進(jìn)程的k_stack。
8. 各個進(jìn)程有自己的線性空間，但他們對應(yīng)的物理空間卻可以重合。事實上fork出新進(jìn)程時，它的數(shù)據(jù)段和代碼段是完全父進(jìn)程重合的（是完全復(fù)制了所有頁表項）。對于共用的代碼，重合當(dāng)然沒有問題，但對于要寫的數(shù)據(jù)段（如堆棧），共享當(dāng)然不行了，linux采取了寫時復(fù)制（copy on write）技術(shù)，即fork時復(fù)制的所有頁表項的屬性都設(shè)為了只讀RD，若一個進(jìn)程試圖寫時，會發(fā)生頁故障中斷，中斷處理程序（參加page.s）會尋找一個新的物理頁，修改頁表項使其映射到新的物理頁，同時把原頁中的數(shù)據(jù)復(fù)制到新頁上來（這比較耗時的）。
9. 如何管理物理頁。有K_CS/K_DS可見（基址為0，且limit為整個內(nèi)存空間），內(nèi)核態(tài)下線性空間和物理空間是一樣的，可以用一個數(shù)組，記錄每個線性頁框（實際也對應(yīng)物理頁框）被映射了幾次，每次分配頁及撤銷頁時都要維護(hù)這個數(shù)組。若一個頁框被映射了0次，那么它就是空閑的，可用。

上述是我讀了一遍代碼后，總結(jié)而成的。在這探尋過程，實際上是按照一個路徑來的，重點看懂幾個關(guān)鍵函數(shù)后，就能對內(nèi)核運行框架有一個很好的理解。下面主要來闡述這幾個函數(shù)。

2.1創(chuàng)建進(jìn)程fork()

    創(chuàng)建進(jìn)程這樣的工作應(yīng)該是在用戶控件調(diào)用的，所以這里就不得不提到sys_call系統(tǒng)調(diào)用。下面就以fork為例，說明系統(tǒng)調(diào)用的工作機(jī)制。

    如上圖所示，首先將調(diào)用號寫入eax，比如fork的調(diào)用號為NR_fork=2，然后int 80h進(jìn)入軟中斷，IGDT表的對應(yīng)項會指示程序運行到system_call函數(shù)；

    system_call函數(shù)首先判斷調(diào)用是否在范圍內(nèi)，如linux 0.11版系統(tǒng)調(diào)用總數(shù)為72；

把ds，es的值設(shè)為0x10，即KERNEL_DS。要注意的是，此時的cs已經(jīng)是0x08（即KERNEL_CS）了，因為IDT表中的所有SELECTOR都是0x08；

根據(jù)調(diào)用號，從sys_call_table中選擇相應(yīng)的函數(shù)執(zhí)行；

因為系統(tǒng)調(diào)用很可能是該進(jìn)程變?yōu)橹袛酄顟B(tài)（如資源的問題），因此必須判斷是否要schedule一下。若真schedule了，則會切到另一個進(jìn)程去執(zhí)行。當(dāng)該進(jìn)程再次被執(zhí)行時，是從schedule的switch_to函數(shù)末尾開始執(zhí)行的（參見switch_to），它要返回的是ret_from_sys_call，所以事先把該返回地址壓棧；

最后還要看一下該進(jìn)程是否收到信號（查看task_struct中的signal項），若有信號，就去執(zhí)行do_signal，這是進(jìn)程間通信的基礎(chǔ)，以后再講。

好了，了解了系統(tǒng)調(diào)用，現(xiàn)在來看_sys_fork，它首先找一個空任務(wù)，linux0.11最多允許64個進(jìn)程，內(nèi)核中維護(hù)一個task[64]數(shù)組，標(biāo)示某個task是否存在了。

然后把任務(wù)號壓棧（注意任務(wù)號和進(jìn)程號的區(qū)別），然后調(diào)用最關(guān)鍵的函數(shù)copy_process。由名字就可知，創(chuàng)建進(jìn)程實際上是復(fù)制了父進(jìn)程。

    首先獲得一個新物理頁作為新進(jìn)程的task_struct，然后其內(nèi)容完全復(fù)制current的；

    修改屬性值，包括pid，utime等；

    修改運行狀態(tài)值（tss段），主要是esp0指向新進(jìn)程的內(nèi)核棧，而且以后都不用變，前面講過，另外就是ldt_sel，應(yīng)索引到該進(jìn)程在GDT中的ldt_sel，其它的如寄存器之類的基本不用改，不過要注意的是eax需改為0，即子進(jìn)程fork返回的是0；

    復(fù)制進(jìn)程空間，這里不是復(fù)制內(nèi)容，而只是復(fù)制PDE和頁表，使新進(jìn)程的地址空間與父進(jìn)程映射到相同的物理頁，還有一個很重要的工作就是修改p中LDT段的內(nèi)容，使其指向新進(jìn)程空間的基址。

    設(shè)置gdt表中對應(yīng)該進(jìn)程的TSS,LDT描述符，使其指向task_struct中的TSS段和LDT段；

    最后設(shè)置state為RUNNING，子進(jìn)程就可以被調(diào)度執(zhí)行了。

    關(guān)鍵來看一下copy_mem(nr,p)的工作：

    首先獲得源基址和段長，新基址為nr*64M，然后修改task_struct中l(wèi)dt段為新基址。此時新基址有了，但新進(jìn)程尋址所需的PDE和頁表還沒有，下面就創(chuàng)建；

    獲得源PDE和新PDE的地址，注意了這里是內(nèi)核空間，頁目錄表的基址為0，base/4M即為第幾項，每項大小為4Byte。

    獲得PDE的總項數(shù)，一般就為16項（每項4M，共64M），對每一項，若為空則跳過（可能為空的），若不為空，則：

    獲得該PDE項對應(yīng)的頁表from_table，新頁表需重新獲取物理頁（每個頁表的大小也為一個頁框4K），并使新PDE項指向該新頁表，但屬性設(shè)置為只讀，為的是寫時復(fù)制；

    新頁表中的1024項全部復(fù)制源頁表的內(nèi)容，即映射到相同地址空間；

    最后，對每個PTE項映射的物理頁，都要維護(hù)其mem_page[*to_table]，即使該物理頁的映射次數(shù)++。

2.2執(zhí)行用戶程序execve()

    execve()函數(shù)也要進(jìn)行一次系統(tǒng)調(diào)用，來打造一個全新的進(jìn)程空間，執(zhí)行新的程序，它執(zhí)行完之后，新進(jìn)程就和原父進(jìn)程完全不相干了，就連父進(jìn)程原先為子進(jìn)程安排在execve()調(diào)用之后的那些代碼頁不存在了。那么首先看看一個新打造出來的進(jìn)程空間是什么樣的呢？主要包括

1. code代碼；
2. data全局?jǐn)?shù)據(jù)；
3. bss未初始化的全局?jǐn)?shù)據(jù)；
4. stack堆棧供進(jìn)程內(nèi)函數(shù)調(diào)用參數(shù)、局部變量用；
5. 參數(shù)即該進(jìn)程運行的參數(shù)，包括程序名，附加參數(shù)argv，參數(shù)個數(shù)argc等。

相比較這個模型而言，其實execve()所做的事情非常少。

    如上圖所示，call sys_call_table[]選擇了sys_execve執(zhí)行，首先把內(nèi)核棧中存放返回eip值的地址賦給eax，并壓棧作為參數(shù)調(diào)用do_execve()；

    do_execve()首先根據(jù)文件名，找到該文件，并獲得它的執(zhí)行頭ex；

    釋放該進(jìn)程的原地址空間，包括使相應(yīng)的PDE項清零，相應(yīng)的頁表釋放；

    獲取32個物理頁，把程序的運行參數(shù)賦值到這些頁中，一般而言肯定是綽綽有余的，需注意的是，這里是在內(nèi)核態(tài)，把數(shù)據(jù)復(fù)制到用戶態(tài)的頁表中，需一定的技巧。然后把這32頁安排在該進(jìn)程空間的末尾，這里當(dāng)然就會填寫相應(yīng)的PDE項，并重新分配頁表來指向這些頁框；

    末尾32頁，最末存放的是運行參數(shù)，多余的部分作為stack，且此時p指針指向該stack的頭。create_table(p)把各運行參數(shù)argv，argc的地址寫入該stack中，并使p指針相應(yīng)前移；

    最后是神奇的一步，是內(nèi)核棧中返回eip的值為ex.entry程序入口，esp值為p，即用戶態(tài)堆棧中。然后該系統(tǒng)調(diào)用返回后，就會去執(zhí)行新的程序了。

    可見，execve執(zhí)行完之后，只是提供了程序的執(zhí)行入口，并讓該進(jìn)程eip指向該入口處開始執(zhí)行，但實際的程序卻并未加載到進(jìn)程空間內(nèi)。執(zhí)行時，當(dāng)然會發(fā)生缺頁錯誤，這是再到磁盤中的文件中去找所缺的部分加載。這里就要提高linux下可執(zhí)行文件的格式了，0.11版時用的是a.out格式，現(xiàn)在已經(jīng)不用了，現(xiàn)在普遍用的是elf格式，它把整個文件分為多個段program，并有一個elf頭標(biāo)示所有這些段頭，每個段頭又會標(biāo)識該段應(yīng)被加載到進(jìn)程空間中的偏移地址，這些都是編譯器自動完成的。所以缺頁中斷程序只要根據(jù)所缺頁的偏移地址去文件中找相應(yīng)的program來加載即可，對于有些沒有執(zhí)行的分支，就不會加載，這樣也提高了效率。堆棧也一樣，當(dāng)末128K用完后，會分配新的物理頁作為堆棧。

2.3進(jìn)程退出exit()及等待wait()

    進(jìn)程的退出也是一個系統(tǒng)調(diào)用，最終調(diào)用的函數(shù)實體為do_exit()。在我們寫應(yīng)用程序的時候，有時候中間判斷出現(xiàn)異常時，會調(diào)用exit(-1)這樣的函數(shù)來終止進(jìn)程，但往往我們的main程序不會調(diào)用exit，而只是在最后return 1。但實際上，編譯器編譯時運自動為每個應(yīng)用程序的末尾加上glibc運行時庫中的exit函數(shù)來執(zhí)行exit的系統(tǒng)調(diào)用。另外一般父進(jìn)程會等待子進(jìn)程的結(jié)束，利用wait系統(tǒng)調(diào)用。

    do_exit()函數(shù)比較簡單，首先使該進(jìn)程的PDE清零，釋放其占用的頁表；

    第二步比較關(guān)鍵，遍歷所有進(jìn)程，找到它的所有子進(jìn)程，將其父重設(shè)為task[1]，即init進(jìn)程。若該子進(jìn)程還在運行，則不用管，它exit時會自動發(fā)信號，若該子進(jìn)程已經(jīng)處于ZOMBIE狀態(tài)（但還沒有銷毀，可能是該父親并未調(diào)用wait），則應(yīng)重新向新父親init進(jìn)程發(fā)送SIGCHLD信號（它之前可能已經(jīng)發(fā)過了，但是發(fā)給原父親的），可見init進(jìn)程會處理所有沒被處理的ZOMBIE進(jìn)程；

    釋放該進(jìn)程占用的文件、tty等系統(tǒng)資源，并將其狀態(tài)設(shè)為ZOMBIE；

    最后通知父進(jìn)程，即向父進(jìn)程發(fā)送SIGCHLD信號，由上面可知，父進(jìn)程至少為init進(jìn)程，然后執(zhí)行調(diào)度。

    有do_exit()的實現(xiàn)來看，有兩點需注意：

1. 作為子進(jìn)程，它調(diào)用exit后，其實并未真正銷毀，而是變?yōu)榱薢OMBIE狀態(tài)，不會再次被調(diào)用，等待其父進(jìn)程來銷毀；
2. 作為父進(jìn)程，它調(diào)用exit時，要么其所有子進(jìn)程都被他調(diào)用wait時銷毀了，而若還沒全銷毀，或壓根它就沒調(diào)用wait去處理它的子進(jìn)程，那么它在exit是也至少會將這些子進(jìn)程的父親指向init進(jìn)程。

父進(jìn)程一般調(diào)用waitpid來等待子進(jìn)程結(jié)束，并銷毀其task_struct。其工作情況如上圖所示，這段代碼有點別扭。

首先置flag=0，根據(jù)pid值找相應(yīng)的進(jìn)程，或者是一個特定的子進(jìn)程、或是一組、或pid=-1時就找所有的進(jìn)程；

若該進(jìn)程的狀態(tài)為ZOMBIE了，則releas它的task_struct，并返回其pid。這里可見它只要銷毀一個進(jìn)程就會返回，所以一般父進(jìn)程有多個子進(jìn)程時，會循環(huán)調(diào)用wait直到銷毀了它想要銷毀的那個；

若該進(jìn)程還沒終止，則置flag=1，然后執(zhí)行下面的if()框架：置自己的state為中斷狀態(tài)，即掛起自己，然后調(diào)用執(zhí)行其它進(jìn)程；

直到它再次被喚醒時（是被信號喚醒的），它繼續(xù)從schedule()下面開始執(zhí)行，若僅是被SIGCHLD喚醒，則繼續(xù)回去尋找子進(jìn)程來銷毀，否則就返回-1。這里也說明，父進(jìn)程中需循環(huán)調(diào)用wait。

2.4初始函數(shù)main()

    前面講了進(jìn)程的創(chuàng)建、打造、終止，任何事物都要有個最原始的，那么最原始的進(jìn)程哪來的呢？上面多次提到的init進(jìn)程又是怎么回事呢？那就要去看main函數(shù)，它是內(nèi)核執(zhí)行完head.s代碼后就開始執(zhí)行的，事實上我是先看它，再尋這看完上面的那些函數(shù)的，看完之后再回頭來看它，會發(fā)現(xiàn)結(jié)構(gòu)更加清晰了。

    main()之前是head.s代碼，整個系統(tǒng)還是串行控制，還不存在多進(jìn)程。進(jìn)行一些初始化initial()后，執(zhí)行關(guān)鍵的一步mov_to_user_model()，它假裝push了esp、eip等值到堆棧中，然后iret，彈出堆棧中的數(shù)據(jù)到相應(yīng)寄存器中，注意這里的ss、cs都是LDT選擇子，LDT段應(yīng)該在task_struct中，task[0]的task_struct在initial中就準(zhǔn)備好了，其中的LDT段的base都為0。這里就有幾點需注意的地方了：

1. 先看esp、eip的值就不難發(fā)現(xiàn)，0號task的進(jìn)程體和內(nèi)核是重合的，用戶態(tài)堆棧就是head.s用的堆棧；
2. 而0號task的內(nèi)核態(tài)堆棧是和其task_struct聯(lián)合union在一起的，而這個union體是認(rèn)為地初始化在內(nèi)核空間的（低1M地址內(nèi)），這是一個特殊，以后所有的進(jìn)程的task_struct都會在主存（高于1M）中分配新頁框；
3. 這以后就不存在串行控制路勁了，即head.s用的那個堆棧卻是不會再被內(nèi)核用了，而只是作為task0的用戶堆棧，以后任意時刻，系統(tǒng)中都是一個進(jìn)程在執(zhí)行，或在用戶態(tài)，或在內(nèi)核態(tài)，整個內(nèi)核空間的函數(shù)是被所有進(jìn)程共享的；

    

然后task0會fork出task1，即為init進(jìn)程，這之后task0就進(jìn)入休眠，循環(huán)執(zhí)行pause()，事實上，一個進(jìn)程執(zhí)行pause()系統(tǒng)調(diào)用后，會變?yōu)閽炱馉顟B(tài)INTERRUPTIBLE，然后調(diào)用schedule(),直到被信號喚醒，而實際上不會有進(jìn)程發(fā)信號給task0，那么task0到底會不會被執(zhí)行呢？會！這就需看schedule()函數(shù)中的一個編程小技巧了，它在調(diào)度時，是從task1開始遍歷的，但最后若發(fā)現(xiàn)沒有可運行的進(jìn)程，則會啟動task0，與task0一直是INTERRUPTIBLE無關(guān)。Task0也不干事，反正就是一直再掛起，再schedule()，直到有可運行的其它進(jìn)程。

再來看init進(jìn)程，它首先fork出一個子進(jìn)程去執(zhí)行/bin/sh程序，然后等待該子進(jìn)程退出，該子進(jìn)程會退出嗎？會的！應(yīng)該執(zhí)行參數(shù)argv1不對，這只是為了初始化一下環(huán)境，詳細(xì)參加sh程序；

然后它重新fork出一個子進(jìn)程，以正確的參數(shù)執(zhí)行/bin/sh程序，然后等待子進(jìn)程的退出，注意了，它用的是wait，實際上是waitpid的一個封轉(zhuǎn)，即參數(shù)pid=-1，找所有的子進(jìn)程。所有失去父親未被銷毀的進(jìn)程都會指向init進(jìn)程，所以它循環(huán)調(diào)用wait來銷毀所有ZOMBIE進(jìn)程，直到它本身的那個子進(jìn)程，即sh程序終止，才退出這個循環(huán)。

Sh程序會終止嗎？會的，輸入命令exit它就終止啦！終止后init進(jìn)程又會進(jìn)while(1)循環(huán)，即再次fork來運行sh程序，那時候還沒有用戶界面，linux反正就是一直運行sh，sh可以創(chuàng)建進(jìn)程來執(zhí)行。

第二部分 內(nèi)核的血肉

    上面講了內(nèi)核的運行框架，有了這個框架，內(nèi)核就可以運轉(zhuǎn)了，上述內(nèi)容闡述了，用戶可以方便地通過內(nèi)核（系統(tǒng)調(diào)用）創(chuàng)建進(jìn)程、打造進(jìn)程、銷毀進(jìn)程。但一個OS內(nèi)核要能被用戶使用，還必須包含一個具體的系統(tǒng)調(diào)用接口，這些接口主要分為幾個大部分，也就是教科書上講的如文件系統(tǒng)、設(shè)備驅(qū)動、網(wǎng)絡(luò)等，另外要使內(nèi)核運轉(zhuǎn)得高效，滿足用戶的需求，還必須為它設(shè)計各種運行策略，如調(diào)度方法、進(jìn)程間通信方法等。

    總的來講，這些內(nèi)容一般都是教課書上津津樂道的內(nèi)容，在前面學(xué)習(xí)內(nèi)容的基礎(chǔ)上，再來看這里的內(nèi)容，會覺得更清晰一點。

    看的也不深入，講的不多。

3.進(jìn)程調(diào)度

    Linux0.11版本的進(jìn)程調(diào)度比較簡單，效率比較低，它實際上就是遍歷所有可運行進(jìn)程，是一個O(n)復(fù)雜度的算法，現(xiàn)代linux的調(diào)度算法已相當(dāng)成熟，引入了等待隊列的思想，利用紅黑樹實現(xiàn)了一種O(1)時間復(fù)雜度的調(diào)度算法。但通過對0.11版的調(diào)度程序的學(xué)習(xí)，可以很好的理解調(diào)度程序時干嘛的，什么時候、怎么樣來完成這樣的事情。

首先看進(jìn)程調(diào)度發(fā)生在那些情況下?？偨Y(jié)一下，主要有3個地方會發(fā)生schedule：1）時鐘中斷，這是最重要的一項，把保證一個進(jìn)程不會永遠(yuǎn)占用CPU；2）在sys_call中，執(zhí)行完相應(yīng)的sys_call_table[]的函數(shù)后，sys_call主體函數(shù)會判斷current->state是否還是RUNNING，因為這過程中可能因為資源、信號等是該進(jìn)程阻塞，若不是了，就schedule；3）一個sys_call_table[]函數(shù)本身就是專門為了調(diào)度的，如pause()、exit()、sleep_on()、waitpid()等，它們往往使該進(jìn)程state變?yōu)榉荝UNNING，然后直接調(diào)用scheduel，注意與第二種稍有區(qū)別。

    進(jìn)程調(diào)度總體上分為兩部分內(nèi)容，一個各進(jìn)程狀態(tài)的轉(zhuǎn)換，二是調(diào)度。

3.1進(jìn)程狀態(tài)轉(zhuǎn)換

    進(jìn)程調(diào)度是指，在所有RUNNING狀態(tài)的進(jìn)程中選擇一個最合適的進(jìn)程來執(zhí)行。那其它狀態(tài)的呢？ZOMBIE就不看了，已經(jīng)是將死，不會再被調(diào)度，STOP在0.11版還沒用，另外就是INTERRUPTIBLE和UNINTERRUPTIBLE。

    UNTERRUPTIBLE狀態(tài)是不能被信號喚醒的，它一般是進(jìn)程執(zhí)行時需要用到某個資源如文件IO等，而此時此資源被其它進(jìn)程占用，那它就調(diào)用sleep_on()進(jìn)入UNINTERRUPTIBLE，只有當(dāng)該資源釋放時，才會調(diào)用wake_up()喚醒該進(jìn)程。它不能被信號喚醒。

    INTERRUPTION則是和資源無關(guān)，它更多是為了兼顧多進(jìn)程執(zhí)行的順序安排而設(shè)置的，最簡單的就是前面講的wait()調(diào)用，使父進(jìn)程處于INTERRUPTION狀態(tài)，直到子進(jìn)程終止發(fā)送SIGCHLD信號給它，它才被喚醒。它當(dāng)然可以被wake_up()喚醒。

3.2進(jìn)程調(diào)度

    下面看schedule函數(shù)的總體框架：

    首先遍歷所有進(jìn)程，找出過期進(jìn)程，置SIGALARM信號。Jiffies是內(nèi)核維護(hù)的全局變量，是系統(tǒng)啟動開始所經(jīng)過的滴答數(shù)，10ms/滴答。若一個進(jìn)程預(yù)期在一個時間之前完成，過期的則會進(jìn)行相應(yīng)處理，那就是SIGALARM信號的處理，這里就不多講了。并且還找所有state為INTERRUPTIBLE的進(jìn)程，若它受到信號，則置RUNNING。

    然后遍歷所有進(jìn)程，找出具有最大counter值的進(jìn)程作為下一個執(zhí)行進(jìn)程。若所有task的counter都為0了，就將所有task的counter重置為f(priority)（關(guān)于priority的函數(shù)）。這里的counter就是常常說的動態(tài)優(yōu)先級，進(jìn)程每執(zhí)行一次，counter--，priority就是常說的靜態(tài)優(yōu)先級。

    上面的過程還清楚地顯示出INTERRUPTIBLE進(jìn)程如何被信號喚醒的過程，但對UNINTERRUPTIBLE卻不涉及，那它的狀態(tài)轉(zhuǎn)換又是在哪呢？

    前面也提到UNINTERRUPTIBLE是和資源息息相關(guān)的，原來每個資源如文件（0.11版內(nèi)核所有進(jìn)程的打開文件和<64，由file_table[64]維護(hù)，每個進(jìn)程最多有20個文件，有每個task_struct中的filp[20]維護(hù)），內(nèi)核中都為它維護(hù)一個等待隊列，該隊列對所有進(jìn)程可見（通過file_table[64]）。

    每當(dāng)進(jìn)程去使用一個正被其它進(jìn)程使用的資源時（一定在內(nèi)核態(tài)中），該進(jìn)程就會執(zhí)行到sleep_on()分支上去，變?yōu)閁NINTERRUPTIBLE狀態(tài)。當(dāng)另一個進(jìn)程（在內(nèi)核態(tài)中）釋放了該資源，那么它也會執(zhí)行到一個分支上去，查看該資源的等待隊列，對其中一個調(diào)用wake_up()喚醒。

4進(jìn)程間通信

    前面講了信號的喚醒機(jī)制，而實際上，信號并不是專門為喚醒設(shè)計的，它最主要的設(shè)計意圖是為了實現(xiàn)一套進(jìn)程間通信機(jī)制。比如兩個都是RUNNING狀態(tài)的進(jìn)程，其中一個向另一個發(fā)送一個信號，該進(jìn)程收到信號時，就可以執(zhí)行一段相應(yīng)的功能代碼。

4.1用戶態(tài)執(zhí)行模型分析

首先看用戶怎么使用這套機(jī)制的，一般在linux下多進(jìn)程編程，會使用信號通信。首先要知道的是，信號中最重要的一個數(shù)據(jù)結(jié)構(gòu)時sigaction，它包括一個sa_handler處理函數(shù)和sa_restorer返回函數(shù)；每個進(jìn)程的task_struct中有三項信號相關(guān)的，signal為一個32bit的信號位圖，blocked是阻塞位圖，sigaction[32]對應(yīng)每個信號。

    一般一個進(jìn)程task-receve中需注冊某信號的處理函數(shù)，int sigaction(int sig,struct sigaction)是一個用戶態(tài)函數(shù)，定義在glibc中，它實際上是執(zhí)行一個系統(tǒng)調(diào)用sys_signal，把該sigaction寫到task_struct中。要注意的是這里的sa_handler和sa_restorer是處理函數(shù)的指針，即一個函數(shù)入口地址，且是用戶態(tài)下的地址。在系統(tǒng)調(diào)用中（內(nèi)核態(tài)下），僅是用的這個用戶態(tài)地址（實際上只是把這個地址壓入棧中eip位置，后面會看到），而并不會去執(zhí)行這個用戶態(tài)函數(shù)，所以這里是沒問題的。

    另一個進(jìn)程task-send向該進(jìn)程發(fā)送信號，一般用glibc中的函數(shù)kill(pid,sig)，raise(sig)等，它們最終也是系統(tǒng)調(diào)用sys_kill(),sys_raise()等，并最終會調(diào)用內(nèi)核函數(shù)send_sig(pid,sig)，將pid所指進(jìn)程的task_struct中的signal字段的相應(yīng)bit置位。

    這樣，當(dāng)task-receve發(fā)現(xiàn)收到信號后（一般是在sys_call中發(fā)現(xiàn)的），就會根據(jù)它注冊過的sigaction來對進(jìn)程進(jìn)行一番打造，使得它執(zhí)行一個sa_handler，然后繼續(xù)沿原路徑執(zhí)行。

4.2內(nèi)核態(tài)打造過程分析

    關(guān)鍵就是看進(jìn)程如何發(fā)現(xiàn)信號，并如何讓進(jìn)程插入一段執(zhí)行sa_handler，且不影響原進(jìn)程的控制路徑（即只是在原路徑中插入一段sa_handler）。

    前面講了信號是內(nèi)核控制的task_struct中的組成部分，用戶是不可見的，所以發(fā)現(xiàn)信號一定要進(jìn)程在內(nèi)核態(tài)下，也就是說，用戶進(jìn)程一定要在運行到內(nèi)核態(tài)后才會執(zhí)行信號處理工作，各個能使進(jìn)程進(jìn)入內(nèi)核態(tài)的點，一般稱為陷入點（這個名詞好像不對，記不清了）。實際上在講sys_call的時候，略去了ret_from_sys_call部分的關(guān)于信號處理的部分，現(xiàn)在來看。

    系統(tǒng)調(diào)用sys_call的最后部分首先判斷是否是在內(nèi)核態(tài)下調(diào)用該sys_call的（好像這種情況不存在），是的話就不處理信號，因為信號是要處理用戶態(tài)堆棧的。

    然后判斷有無收到信號，即看task_struct中的位圖有無置位的，有的話則取最低一位的信號，轉(zhuǎn)化成數(shù)型，壓入堆棧，作為參數(shù)調(diào)用do_signal。為什么只取最低一位呢？其它信號就無效了嗎？0.11版貌似這里做的不完善。

    和之前execve函數(shù)一樣，從sys_call到這里的call do_signal，內(nèi)核態(tài)堆棧中的數(shù)據(jù)是固定的，最開頭是返回到用戶態(tài)的（一定是用戶態(tài)，前面提到了內(nèi)核態(tài)下系統(tǒng)調(diào)用是不處理信號的）eip、cs、eflag、esp、ss，它們都作為do_signal的參數(shù)。其中eip是設(shè)為了long型，esp是設(shè)為了long *型，其實都一樣，都是32bit的數(shù)（一個地址），這樣做只是方便c語言的編程。

    Do_signal()函數(shù)首先根據(jù)signr值在task_struct中找到相應(yīng)的sigaction，然后進(jìn)行最重要的兩步：

1. 一是把內(nèi)核棧中eip的值該為sa_handler（函數(shù)入口地址）；
2. 二是把內(nèi)核棧中esp值減去7或8，即在返回后的用戶態(tài)堆棧開辟一小段，并在其中填入一系列數(shù)據(jù)，注意這里是在內(nèi)核態(tài)向用戶態(tài)空間寫數(shù)據(jù)，需要一定的技巧，這里封裝了put_fs_long()。

這樣一打造后，情況如下圖所示：

    可以看到打造之后，從sys_call返回后，eip指向用戶空間的sa_handler函數(shù)體，且esp指向新用戶堆棧的新處，進(jìn)程就開始執(zhí)行sa_handler；

執(zhí)行完之后，返回ret，因為這是在一個空間內(nèi)，是short jmp，所以只需要堆棧中彈出eip值即可，而這個值正是do_signal寫入的sa_restorer的入口地址，那么程序就開始執(zhí)行sa_restorer；

Sa_restorer也是一個用戶態(tài)的函數(shù)，不過一般不需要用戶定義，其功能單一固定，就是讓進(jìn)程回到原來位置處，glibc中已經(jīng)為我們定義好了，如上圖右側(cè)所示。

它彈出先前do_signal中寫入用戶堆棧的一些列數(shù)據(jù)，直到old_eip（那些寫入的數(shù)據(jù)好像沒用到，可能只是linus想測試一下），然后ret，同樣是short jmp，堆棧中的old_eip正好就是指向原進(jìn)程斷點的位置，則進(jìn)程又會回到原地方繼續(xù)執(zhí)行了。

5.文件系統(tǒng)

    Linux0.11版完全借用了minix的文件系統(tǒng)，現(xiàn)代linux的文件系統(tǒng)已有了很大發(fā)展，尤其是加入了虛擬文件系統(tǒng)后，功能更加完善，可以識別多種文件系統(tǒng)。這部分內(nèi)容以后再慢慢學(xué)。不過從minix文件系統(tǒng)還是可以學(xué)到一些最基礎(chǔ)的文件系統(tǒng)方面的內(nèi)容。

在磁盤中，文件系統(tǒng)包括超級快，節(jié)點映射，區(qū)映射，節(jié)點，數(shù)據(jù)等，前幾部分的內(nèi)容固定，且存放在磁盤固定位置，一般是磁盤開始位置，操作系統(tǒng)掛載一個磁盤文件系統(tǒng)時，就是通過讀取這些磁盤塊的內(nèi)容，然后再去索引各個文件的。因此若磁盤的這些關(guān)鍵部分壞了，則文件很可能讀不到，就如引導(dǎo)扇區(qū)壞了則無法引導(dǎo)OS一樣。

    在內(nèi)存中，內(nèi)核長期維護(hù)著每個文件系統(tǒng)的超級塊，另外內(nèi)存中有一塊區(qū)域成為緩存，它有一塊一塊組成，用來存放讀到內(nèi)存中的磁盤塊，且一一對應(yīng)，滿了之后會交換出去。在頻繁對某些文件操作時，這樣做可以提高效率。

    在進(jìn)程級別，每個進(jìn)程的task_struct中有filp[20]，即每個進(jìn)程最多可以打開20個文件，另外整個內(nèi)核維護(hù)一個file_table[64]，即整個系統(tǒng)中最多同時存在64個打開文件，它們之間有映射關(guān)系。對進(jìn)程而言，它自認(rèn)為是獨享20個文件的，每次進(jìn)程要使用文件時，它必是系統(tǒng)調(diào)用進(jìn)入內(nèi)核態(tài)，然后內(nèi)核會在file_table中找到與它對應(yīng)的文件，若發(fā)現(xiàn)該文件正在被其它進(jìn)程使用，則會掛起這個進(jìn)程。前面也提到了，每個文件資源（這里指file_table中的）都有一個和它對應(yīng)的等待隊列。

    另外一點，linux中設(shè)備也被當(dāng)成是特殊文件的，設(shè)備驅(qū)動的編寫。

6.網(wǎng)絡(luò)