1、第13章 一個(gè)小型操作系統(tǒng)的實(shí)現(xiàn)本章知識(shí)點(diǎn)：13.1 MINIX概述13.2 進(jìn)程13.3 I/O任務(wù)13.4 內(nèi)存管理13.5 文件系統(tǒng)1在本章中，為了使讀者了解到一個(gè)“真正”的操作系統(tǒng)是怎樣一步步構(gòu)造出來的，我們將以MINIX操作系統(tǒng)為例，對(duì)其設(shè)計(jì)方法進(jìn)行介紹,并對(duì)其源代碼進(jìn)行簡(jiǎn)單分析。因?yàn)镸INIX的源代碼是公開的，有興趣的讀者還可以自己動(dòng)手加以改造。213.1 MINIX概述 MINIX操作系統(tǒng)最早出現(xiàn)于20世紀(jì)80年代，由美國著名學(xué)者A.S.Tanenbaum用c語言編制。它從外部看來和UNIX非常相似，但實(shí)際上，MINIX的內(nèi)部完全是經(jīng)過重新設(shè)計(jì)的。它的主體部分設(shè)計(jì)為幾個(gè)相對(duì)獨(dú)立的

2、模塊，模塊間依賴消息進(jìn)行通訊，這樣的模塊化結(jié)構(gòu)使得對(duì)它的理解和修改都更方便。本章中將介紹基于POSIX（國際標(biāo)準(zhǔn)9945-1）的MINIX2.0版本，它可以運(yùn)行于基于80 x86結(jié)構(gòu)的兼容機(jī)系列。313.1.1 MINIX的組成結(jié)構(gòu)1MINIX的四層結(jié)構(gòu)MINIX的整個(gè)系統(tǒng)被分為4個(gè)層次：413.1.1 MINIX的組成結(jié)構(gòu)需要特別介紹的是位于用戶進(jìn)程層次的MINIX的命令解釋器shell。命令解釋器并不是操作系統(tǒng)的一部分，它本身就是一個(gè)計(jì)算機(jī)程序，用C語言編寫，為協(xié)助用戶與操作系統(tǒng)之間通訊而設(shè)計(jì)，管理用戶與核心(kernel)之間的對(duì)話，并把操作系統(tǒng)指令換成機(jī)器代碼。 513.1.1 MIN

3、IX的組成結(jié)構(gòu)Shell通常利用終端作為標(biāo)準(zhǔn)輸入輸出設(shè)備。但是我們也可以利用以下的命令改變輸入輸出：ver fileb ,這條命令的意思是調(diào)用程序ver，從filea文件取輸入，送輸出到fileb文件。如果再利用管道，則可以將一個(gè)程序的輸出作為另一個(gè)程序的輸入，例如： ver /dev/lp，是將執(zhí)行ver程序的結(jié)果從/dev/lp文件上輸出。啟動(dòng)shell將首先顯示系統(tǒng)提示符$,然后等待，假設(shè)用戶輸入命令move，shell讀取該命令后，自動(dòng)創(chuàng)建一個(gè)新進(jìn)程來執(zhí)行這個(gè)命令。命令執(zhí)行完畢后，它再執(zhí)行一個(gè)系統(tǒng)調(diào)用來終止這個(gè)進(jìn)程，繼續(xù)等待用戶的下一個(gè)輸入。 613.1.1 MINIX的組成結(jié)構(gòu)she

4、ll還可以用來進(jìn)行程序設(shè)計(jì)，它定義了各種變量和參數(shù)，并提供了包括循環(huán)與分支在內(nèi)的，許多在高級(jí)語言中才具有的控制結(jié)構(gòu)。使用shell編程類似于編輯DOS中的批處理文件，我們可以將一組我們想要執(zhí)行的命令放在一個(gè)文件中，然后像執(zhí)行其他程序一樣運(yùn)行這個(gè)文件。這個(gè)文件就被稱為shell程序或shell命令文件，又被稱為shell script。當(dāng)這個(gè)文件被運(yùn)行時(shí)，shell就會(huì)像執(zhí)行輸入命令那樣一條條的自動(dòng)執(zhí)行文件里保存的命令。 713.1.1 MINIX的組成結(jié)構(gòu)2. 源代碼組織方式MINIX的源代碼在邏輯上一般分為兩個(gè)目錄/usr/include和/usr/src/(為敘述方便，將簡(jiǎn)記為includ

5、e/和src/) 。813.1.1 MINIX的組成結(jié)構(gòu)程序在內(nèi)存中運(yùn)行時(shí)，各個(gè)模塊的分布情況:913.1.2 頭文件 在編程的過程中，有許多常量、宏以及結(jié)構(gòu)類型的定義會(huì)經(jīng)常被不同文件用到，通常把這些定義按照某種規(guī)則或需要組織在一起，于是就構(gòu)成了頭文件（header）,以后綴.h標(biāo)識(shí)。1 公共頭文件在頭文件中，有一些是完全通用的，它們不是被源文件直接引用，而是被其它的頭文件引用。MINIX中的三個(gè)主要部分：內(nèi)核、文件系統(tǒng)和內(nèi)存管理分別對(duì)應(yīng)有三個(gè)主控頭文件src/kernel/kernel.h、src/mm/mm.h和src/fs/fs.h。 1013.1.2 頭文件 在include/目錄下，

6、有三個(gè)被主控目錄包含的頭文件：ansi.h：用來測(cè)試編譯器是否符合標(biāo)準(zhǔn)c的規(guī)定。整個(gè)文件的構(gòu)造以#ifndef_ANSI_H為開始，并以#endif結(jié)束；limits.h:定義了一些基本的數(shù)據(jù)值的大小，比如：數(shù)據(jù)類型中的整形數(shù)所占位數(shù)的值等；errno.h:包含了全局變量errno返回的錯(cuò)誤碼，用于系統(tǒng)調(diào)用失敗時(shí)通知用戶程序。1113.1.2 頭文件 下面來看看include/sys目錄下有哪些主要的頭文件。由于同一種數(shù)據(jù)類型在16位和32位處理器上所占的字長可能存在差異，因而可能因錯(cuò)誤理解在特定情況下使用的基本數(shù)據(jù)結(jié)構(gòu)而引發(fā)問題。在文件types.h中定義了許多MINIX使用的數(shù)據(jù)類型及其相

7、關(guān)的數(shù)值，從而可以避免這種情況的發(fā)生。通常緊跟在types.h之后的是ansi.h頭文件，它們都被所有主控頭文件包含。1213.1.2 頭文件 2專有頭文件 除了公共頭文件之外，在include/minix中存放的是在任何平臺(tái)上實(shí)現(xiàn)MINIX都需要的頭文件，而include/ibm中則存放了在IBM兼容機(jī)上實(shí)現(xiàn)MINIX所需的數(shù)據(jù)結(jié)構(gòu)和宏的定義。在include/ibm目錄中主要有兩個(gè)文件：diskparm.h文件由軟盤系統(tǒng)任務(wù)使用；partition.h定義了IBM兼容機(jī)上的硬盤分區(qū)表和有關(guān)常量。在/minix/目錄中首先要注意到的是config.h文件，它被所有主控頭文件所包含，且必須列在

8、第一位。第三個(gè)要提到的頭文件是type.h，它被主控頭文件所包含，定義了很多重要的類型及其數(shù)量值。 1313.1.2 頭文件 消息由如下幾個(gè)部分組成：m-source域：用于指明消息的發(fā)送進(jìn)程；m-type域：用于標(biāo)識(shí)出消息的類型；數(shù)據(jù)域：包括定義為整型(int)或長型(long)的整數(shù)、字符、字符串、字符數(shù)組、指針以及函數(shù)等。 1413.2 進(jìn)程13.2.1 概述計(jì)算機(jī)中的所有軟件，被組織成一定的順序運(yùn)行，這就形成了進(jìn)程的概念。在MINIX和進(jìn)程有關(guān)的部分主要負(fù)責(zé)解決以下的問題：怎樣創(chuàng)建和終止一個(gè)進(jìn)程，并使之處于合適的隊(duì)列中（進(jìn)程管理）；怎樣有效調(diào)度眾多進(jìn)程，使之在兼顧充分利用資源和進(jìn)程特權(quán)

9、級(jí)、優(yōu)先級(jí)要求的同時(shí)保證有序運(yùn)行（進(jìn)程調(diào)度），這里也包括了對(duì)中斷引起的進(jìn)程狀態(tài)改變的處理（中斷處理）；進(jìn)程之間怎樣交互（進(jìn)程通信）等等。1513.2.1 概述1 進(jìn)程管理整體來看所有用戶進(jìn)程構(gòu)成一棵大的進(jìn)程樹，初始化進(jìn)程init是它們的根節(jié)點(diǎn):計(jì)算機(jī)開機(jī)以后，固化在硬件的程序從引導(dǎo)盤（可以是硬盤或軟盤）上將第一道第一扇區(qū)（也就是所謂的0磁道）中的內(nèi)容讀入內(nèi)存并從開始執(zhí)行。在系統(tǒng)裝入完成前，所有涉及磁盤I/O的操作都要由boot完成。 裝入完成后，boot的使命就結(jié)束了。接下來就由內(nèi)核啟動(dòng)各項(xiàng)任務(wù)，然后就是MM、FS以及位于第三層的其它服務(wù)紛紛登場(chǎng)。 在用戶成功登錄以后，可執(zhí)行文件login將執(zhí)

10、行用戶命令解釋器shell， shell負(fù)責(zé)接收用戶命令，為每一條命令的執(zhí)行創(chuàng)建一個(gè)子進(jìn)程。 1613.2.1 概述Shell接收命令創(chuàng)建進(jìn)程的大概框架如下所示： 1713.2.1 概述2. 進(jìn)程調(diào)度中斷在操作系統(tǒng)中具有特殊的意義，它保證多道程序系統(tǒng)能夠連續(xù)工作。MINIX的底層軟件采用將中斷轉(zhuǎn)換為消息的方法來隱藏中斷。每次處理中斷時(shí)，都需要通過進(jìn)程調(diào)度來確定哪一個(gè)進(jìn)程重新獲得運(yùn)行機(jī)會(huì)。MINIX中的進(jìn)程調(diào)度采用三級(jí)排隊(duì)系統(tǒng)，分別對(duì)應(yīng)第2、3、4層。進(jìn)程所處層次越低其優(yōu)先級(jí)越高，2、3層的進(jìn)程可以一直運(yùn)行到其自己阻塞，而第四層的用戶進(jìn)程則采用時(shí)間片輪轉(zhuǎn)調(diào)度。1813.2.1 概述3. 進(jìn)程通信

11、MINIX以消息來實(shí)現(xiàn)進(jìn)程間的通信，并且對(duì)消息的發(fā)送存在一些限制：每個(gè)進(jìn)程(任務(wù))可以和同層或下一層中的進(jìn)程(任務(wù))通信，但用戶進(jìn)程不能直接和I/O任務(wù)通信。MINIX中發(fā)送和接收消息主要通過三條原語：send(a,&message):向進(jìn)程a發(fā)送一條消息；receive(b,&message):從進(jìn)程b處接收一條消息；send_rec(c,&message):發(fā)送消息給進(jìn)程c，并等待它的回答。這些原語都可以通過c庫函數(shù)來調(diào)用，第二個(gè)參數(shù)&message表示的是消息數(shù)據(jù)的內(nèi)存地址，消息將從發(fā)送者復(fù)制到接收者，對(duì)于第三條原語來說，應(yīng)答的消息將覆蓋在原消息的地址上。1913.2.2 具體實(shí)現(xiàn)1.

12、系統(tǒng)啟動(dòng)與初始化開機(jī)后，硬件（實(shí)際上指的ROM中的一個(gè)程序）讀取引導(dǎo)盤的第一個(gè)扇區(qū)，執(zhí)行其中的代碼，這部分代碼又引導(dǎo)boot程序的執(zhí)行。執(zhí)行boot的目的是得到操作系統(tǒng)的映象。這個(gè)映象保存在位于/minix/目錄下的文件中，是由內(nèi)核、MM、FS和init被分別編譯后，再將它們鏈接在一起得到的。Boot本身并不是操作系統(tǒng)的組成部分，在操作系統(tǒng)被裝入后，控制權(quán)即被轉(zhuǎn)移給內(nèi)核的有關(guān)代碼。2013.2.2 具體實(shí)現(xiàn)系統(tǒng)啟動(dòng)和初始化流程: 2113.2.2 具體實(shí)現(xiàn)2. 中斷處理中斷處理是由硬件和軟件共同完成的，為了避免對(duì)于煩瑣硬件細(xì)節(jié)（主要是CPU的內(nèi)部工作原理）的過多涉及，我們只簡(jiǎn)單介紹硬件完成的工

13、作，主要側(cè)重于軟件的處理過程。2213.2.2 具體實(shí)現(xiàn)硬件中斷和軟件中斷的處理流程: 2313.2.2 具體實(shí)現(xiàn)3. 進(jìn)程調(diào)度進(jìn)程的調(diào)度相對(duì)來說比較簡(jiǎn)單，對(duì)照第2、3、4層建立了三個(gè)運(yùn)行進(jìn)程隊(duì)列。在頭文件proc.h中定義了兩個(gè)數(shù)組rdy_head和rdy_tail,它們的作用就是分別指向隊(duì)列的隊(duì)首進(jìn)程和隊(duì)尾進(jìn)程。只有就緒進(jìn)程才參與排隊(duì)，而被阻塞的和取消的進(jìn)程，則不會(huì)出現(xiàn)在這三個(gè)運(yùn)行進(jìn)程隊(duì)列中。2413.2.2 具體實(shí)現(xiàn)4.進(jìn)程通信因?yàn)橹袛嗵幚淼搅俗詈?，也歸結(jié)到進(jìn)程間通過消息傳遞信息，所以我們將從處理中斷的兩個(gè)函數(shù)開始，了解MINIX中的進(jìn)程間通信過程。在3.6.2節(jié)中曾經(jīng)介紹過三種進(jìn)程間利

14、用消息通信時(shí)所采用的同步機(jī)制，MINIX中采用的第一種組合方法，“阻塞發(fā)送，阻塞接收”，也就是所謂的會(huì)合原理。 2513.2.2 具體實(shí)現(xiàn)與進(jìn)程通信有關(guān)的函數(shù)和過程都在文件proc.c中。interrupt函數(shù)負(fù)責(zé)將硬件中斷轉(zhuǎn)換成消息，并把這條消息發(fā)送給與該設(shè)備對(duì)應(yīng)的系統(tǒng)任務(wù)，它將按順序完成以下工作：通過判斷變量k_reenter，來檢查在接收當(dāng)前中斷時(shí)是否有中斷正在處理。若是，則將當(dāng)前中斷放入中斷隊(duì)列排隊(duì)，等待以后調(diào)用unhold操作處理；檢查目標(biāo)任務(wù)是否正在等待中斷，若是則發(fā)送消息，否則就將該任務(wù)的p_int_blocked標(biāo)志設(shè)置為1；完成消息的發(fā)送：向目標(biāo)任務(wù)消息緩沖區(qū)中的resour

15、c域和type域?qū)懭雰?nèi)容，并將該任務(wù)的receive標(biāo)志復(fù)位，解除該任務(wù)的阻塞，當(dāng)消息復(fù)制完成后，任務(wù)就被調(diào)度執(zhí)行。2613.2.2 具體實(shí)現(xiàn)處理軟中斷的工作是由sys_call完成的。和硬件中斷不同，軟中斷的消息來源和去向更加復(fù)雜，因此要利用proc.h中提供的兩個(gè)宏isoksrc_dest和isokprocn協(xié)同工作，檢查并保證消息的源進(jìn)程和目標(biāo)進(jìn)程都是合法的。檢查通過后，若需要發(fā)送消息，則調(diào)用mini_send,需要接收消息則調(diào)用mini_rec。這兩個(gè)負(fù)責(zé)發(fā)/收的進(jìn)程是MINIX消息傳遞機(jī)制的核心，Mini_send的參數(shù)主要有三個(gè)：調(diào)用的進(jìn)程名、目標(biāo)進(jìn)程名以及消息地址的指針。在發(fā)送之

16、前，它還需要先進(jìn)行以下的測(cè)試：宏isuserp測(cè)試參數(shù)caller_ptr；檢查確認(rèn)目標(biāo)進(jìn)程不是一個(gè)空進(jìn)程，否則就報(bào)錯(cuò)；進(jìn)行死鎖測(cè)試；上述測(cè)試通過后將進(jìn)行最重要的測(cè)試：檢驗(yàn)?zāi)繕?biāo)進(jìn)程表項(xiàng)中p_flags域中的receiving標(biāo)志，以判斷該進(jìn)程是否在等待消息. 27 13.3 I/O任務(wù)13.3.1 I/O任務(wù)概述I/O系統(tǒng)在MINIX中是必不可少的，它要為I/O設(shè)備配備驅(qū)動(dòng)程序（實(shí)際上是一個(gè)通信程序）以實(shí)現(xiàn)設(shè)備與上層之間的通信和交互，同時(shí)負(fù)責(zé)處理由I/O操作引起的中斷。此外，由于有些I/O設(shè)備是一種獨(dú)占性的資源，對(duì)它的使用有可能引起死鎖，這也是I/O系統(tǒng)要考慮的。 2813.3.1 I/O任務(wù)

17、概述I/O層次及其功能:進(jìn)程利用消息實(shí)現(xiàn)數(shù)據(jù)讀取: 2913.3.1 I/O任務(wù)概述前面我們多次提到進(jìn)程通過消息通訊，但用戶進(jìn)程是不能直接和I/O進(jìn)程通信的。進(jìn)程向FS發(fā)送消息請(qǐng)求一個(gè)文件，而FS則向設(shè)備驅(qū)動(dòng)程序（磁盤驅(qū)動(dòng)）發(fā)送消息來請(qǐng)求該文件的數(shù)據(jù)塊，F(xiàn)S也是唯一向設(shè)備驅(qū)動(dòng)程序發(fā)送消息的進(jìn)程。 3013.3.1 I/O任務(wù)概述MINIX中對(duì)死鎖的處理比較簡(jiǎn)單，即忽略它。但是，這不意味著放任死鎖的發(fā)生。MINIX中，除了FS啟動(dòng)時(shí)可以向MM發(fā)送“請(qǐng)求”消息報(bào)告RAM盤大小而外，其它任何情況下都不允許FS向MM發(fā)送“請(qǐng)求”消息。因?yàn)橛锌赡艽嬖谶@樣的情況：執(zhí)行EXEC調(diào)用時(shí)，MM向FS發(fā)送消息試圖

18、執(zhí)行可執(zhí)行文件，若此時(shí)FS忙，則MM阻塞，此后若FS也試圖向MM發(fā)送消息，則FS也阻塞，形成循環(huán)等待從而發(fā)生死鎖。3113.3.2 設(shè)備驅(qū)動(dòng)程序的實(shí)現(xiàn)1塊設(shè)備塊設(shè)備主要包括硬盤、軟盤等存儲(chǔ)設(shè)備，前面已經(jīng)提到過，塊設(shè)備驅(qū)動(dòng)程序有一部分是相同的，不同的主要是真正的I/O操作的那部分。設(shè)備驅(qū)動(dòng)程序一共可能有6種操作： OPEN: 驗(yàn)證設(shè)備是否可用；CLOSE:確保把采用延遲寫方式處理的數(shù)據(jù)真正寫到設(shè)備上；READ: 將數(shù)據(jù)從設(shè)備讀到調(diào)用進(jìn)程所在的內(nèi)存區(qū)域；WRITE:與READ執(zhí)行的操作相反；IOCTL:負(fù)責(zé)對(duì)I/O設(shè)備的操作參數(shù)進(jìn)行檢查和修改；SCATTERED_IO:允許執(zhí)行同時(shí)讀寫多個(gè)塊的操作

19、。3213.3.2 設(shè)備驅(qū)動(dòng)程序的實(shí)現(xiàn) 塊設(shè)備驅(qū)動(dòng)程序軟件。MINIX在頭文件driver.h中定義了塊設(shè)備驅(qū)動(dòng)程序需要用到的結(jié)構(gòu)定義，它們包括：driver結(jié)構(gòu)：保存各驅(qū)動(dòng)程序執(zhí)行I/O操作所需調(diào)用函數(shù)的地址；device結(jié)構(gòu)：以字節(jié)為單位保存基地址、長度等與分區(qū)相關(guān)的主要信息。3313.3.2 設(shè)備驅(qū)動(dòng)程序的實(shí)現(xiàn) 驅(qū)動(dòng)程序庫可移植性是在MINIX中得到了相當(dāng)?shù)闹匾暎琈INIX的目標(biāo)是當(dāng)它被移植到一臺(tái)機(jī)器上時(shí)，應(yīng)該能夠使用這臺(tái)機(jī)器上原先運(yùn)行的操作系統(tǒng)采用的分區(qū)表格式。在IBM兼容機(jī)上，硬盤分區(qū)的標(biāo)準(zhǔn)由MS-DOS的fdisk命令確定。MINIX包含了支持IBM兼容機(jī)分區(qū)的源代碼，為了方便移植

20、，這些與平臺(tái)有關(guān)但是與具體硬件無關(guān)的代碼沒有被放在driver.c文件中，而是單獨(dú)的放在drvlib.h和drvlib.c文件中。3413.3.2 設(shè)備驅(qū)動(dòng)程序的實(shí)現(xiàn) RAM盤在MINIX中存在一個(gè)RAM盤的概念,簡(jiǎn)而言之就是保留一部分內(nèi)存作為磁盤來使用，對(duì)于用戶來說，它就像一個(gè)磁盤一樣。RAM盤的驅(qū)動(dòng)程序?qū)嶋H上由四個(gè)緊密聯(lián)系的部分組成，也就是具有以下四個(gè)次設(shè)備：0:/dev/ram:真正的RAM盤，它的大小和基址在MINIX啟動(dòng)時(shí)由FS確定；1:/dev/mem:用于讀寫物理內(nèi)存，通常讀出的是起始于內(nèi)存零地址的內(nèi)容，寫操作則會(huì)改寫中斷向量；2:/dev/kmem:用于讀寫內(nèi)核內(nèi)存，與1的功能

21、類似；3:/dev/null:負(fù)責(zé)接收數(shù)據(jù)并把數(shù)據(jù)拋棄掉。3513.3.2 設(shè)備驅(qū)動(dòng)程序的實(shí)現(xiàn)2MINIX的系統(tǒng)任務(wù)MINIX中將文件管理和內(nèi)存管理摒棄在內(nèi)核之外,禁止它們把信息寫入內(nèi)核.所以，如果內(nèi)存管理系統(tǒng)想把消息通知給內(nèi)核時(shí)，就需要借助于一個(gè)第三者對(duì)內(nèi)核表擁有存取權(quán)的內(nèi)核任務(wù)的幫助，這個(gè)任務(wù)一般被稱之為系統(tǒng)任務(wù)。系統(tǒng)任務(wù)和I/O任務(wù)十分類似，它們都實(shí)現(xiàn)了一個(gè)接口，具有相同的權(quán)限，都被鏈入內(nèi)核中，所不同的僅僅是系統(tǒng)任務(wù)不控制具體I/O設(shè)備，它所服務(wù)的對(duì)象是系統(tǒng)中大部分的內(nèi)部組件。 3613.3.2 設(shè)備驅(qū)動(dòng)程序的實(shí)現(xiàn)系統(tǒng)任務(wù)的18種消息: 3713.4 內(nèi)存管理 13.4.1內(nèi)存管理概述由

22、于MINIX是專門設(shè)計(jì)在IBM兼容機(jī)等小型機(jī)上運(yùn)行的操作系統(tǒng)，因此它的內(nèi)存管理(MM)是比較簡(jiǎn)單的：MM保存一張按照地址順序排列的空閑地址列表，當(dāng)系統(tǒng)調(diào)用FORK和EXEC請(qǐng)求內(nèi)存時(shí)，MM利用首次適配算法找到一塊足夠大的空閑內(nèi)存分配給程序使用。而一旦程序裝入內(nèi)存則一直在原位置運(yùn)行到結(jié)束。可以說，內(nèi)存管理的主要工作就是操作進(jìn)程表和空閑地址列表這兩張表格，以及處理系統(tǒng)調(diào)用FORK和EXEC。3813.4.1內(nèi)存管理概述1內(nèi)存的消息處理和I/O相仿，MM在系統(tǒng)初始化以后進(jìn)入自己的主循環(huán)，等待消息，一旦收到消息就進(jìn)行處理并發(fā)送應(yīng)答消息3913.4.1內(nèi)存管理概述與MM通信的消息類型、入口參數(shù)和應(yīng)答:

23、4013.4.1內(nèi)存管理概述2系統(tǒng)調(diào)用下面我們來看看系統(tǒng)調(diào)用FORK、EXEC和BRK的處理過程。 FORK。執(zhí)行FORK的過程很簡(jiǎn)單，收到FORK調(diào)用的請(qǐng)求后，MM就檢查進(jìn)程表中是否存在空閑位置，如果存在,就嘗試為新建立的子進(jìn)程分配內(nèi)存，隨后就將內(nèi)存地址等信息填入一個(gè)空閑的進(jìn)程表項(xiàng)，最后發(fā)出通知公布建立了一個(gè)新進(jìn)程。進(jìn)程的終止則更復(fù)雜一些，當(dāng)進(jìn)程自己退出（或被信號(hào)殺死）并且被父進(jìn)程通過WAIT調(diào)用觀察到以后，該進(jìn)程才會(huì)真正被刪除，如果第二個(gè)條件沒有滿足，子進(jìn)程就會(huì)被掛起，這種狀態(tài)在MINIX中稱為“僵死”。4113.4.1內(nèi)存管理概述 EXEC。這個(gè)調(diào)用負(fù)責(zé)內(nèi)存映像的更新，包括設(shè)置新堆棧，它

24、也是MINIX中最復(fù)雜的系統(tǒng)調(diào)用。EXEC的復(fù)雜主要是由兩個(gè)方面的因素決定的：次數(shù)眾多的檢測(cè)：EXEC執(zhí)行時(shí)十分謹(jǐn)慎，為了保證有足夠內(nèi)存容納新映像，必須進(jìn)行檢測(cè)。設(shè)置初始堆棧：我們通常用庫函數(shù)execve來調(diào)用EXEC，這個(gè)函數(shù)包含三個(gè)參數(shù)：被執(zhí)行文件名的地址指針；一個(gè)指針數(shù)組的地址指針，數(shù)組中的元素分別指向一個(gè)參數(shù)；第三個(gè)參數(shù)同樣是一個(gè)指針數(shù)組的地址指針. 4213.4.1內(nèi)存管理概述 BRK。BRK調(diào)用可以調(diào)整數(shù)據(jù)段的上限。有兩個(gè)過程都可以調(diào)用BRK：brk過程以數(shù)據(jù)段的絕對(duì)長度為參數(shù)；sbrk以當(dāng)前長度的增量為參數(shù)，計(jì)算出絕對(duì)長度后調(diào)用BRK。執(zhí)行BRK所完成的工作就是檢查地址空間是否夠

25、用，并根據(jù)情況調(diào)整表格，然后通知內(nèi)核。4313.4.1內(nèi)存管理概述 3. 內(nèi)存數(shù)據(jù)結(jié)構(gòu)主要了解兩個(gè)關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)：進(jìn)程表和空閑表。 進(jìn)程表。MINIX中，內(nèi)核、FS和MM都擁有各自的進(jìn)程表，每部分的進(jìn)程表包含本部分必需的域，同時(shí)，三張進(jìn)程表是對(duì)應(yīng)的，也就是說，三張表的第n個(gè)表項(xiàng)指的都是同一個(gè)進(jìn)程。也正是由于這個(gè)原因，三張表必須被同步更新。 空閑表。定義在alloc.h文件中的空閑表按照內(nèi)存地址遞增的順序列出空閑塊?？臻e表的表項(xiàng)主要包含三個(gè)域：空閑塊組的基地址、空閑塊組的大小及指向下一個(gè)空閑塊組的指針。表項(xiàng)以單向鏈表的形式鏈接。4413.4.2 實(shí)現(xiàn)1. 頭文件與主程序MM中的table.c文件

26、的主要作用是為全局變量服務(wù)，在table.c被編譯時(shí)，它會(huì)自動(dòng)為下面將介紹到的一些全局變量保留存儲(chǔ)空間。內(nèi)存管理部分有許多自己使用的頭文件，這些頭文件有的和其它部分的頭文件具有相同的名字，但由于它們位于不同的目錄下為不同的部分服務(wù)，所以編譯使用時(shí)不會(huì)出現(xiàn)錯(cuò)誤。4513.4.2 實(shí)現(xiàn) 頭文件。在內(nèi)存管理器MM中存在著一個(gè)私有的頭文件mm.h，可以將它理解為MM范圍內(nèi)的主控頭文件，它囊括了位于/usr/include及其子目錄中的所有頭文件，以及/kernel/kernel.h中包含的大部分頭文件。MM中每個(gè)文件的編譯都需要引用mm.h。 主程序。MM的主程序也位于main.c中，執(zhí)行的過程和I/

27、O任務(wù)的主程序類似。首先調(diào)用mm_init,mm_init通過過程sys_getmap來獲得內(nèi)核的內(nèi)存使用信息，為所有第二層及第三層的進(jìn)程初始化進(jìn)程表項(xiàng)，同時(shí)也為init進(jìn)程初始化進(jìn)程表項(xiàng)。 4613.4.2 實(shí)現(xiàn)2. 系統(tǒng)調(diào)用的實(shí)現(xiàn) FORK。FORK調(diào)用由文件forkexit.c中的do_fork過程來實(shí)現(xiàn)。 EXIT。由過程do_mm_exit接收調(diào)用，然后具體工作交由mm_exit完成。 WAIT。WAIT和WAITPID調(diào)用都由過程do_waitpid完成。 EXEC。過程do_exec負(fù)責(zé)執(zhí)行本調(diào)用。 BRK。BRK調(diào)用的處理代碼位于break.c中，由過程do_brk完成。 47

28、13.4.2 實(shí)現(xiàn)3.信號(hào)處理的實(shí)現(xiàn)MINIX中所有信號(hào)及與信號(hào)有關(guān)的系統(tǒng)調(diào)用都被包含在文件signal.c中，具體功能如下所示：ALARM:經(jīng)過一段時(shí)間后向自己發(fā)送ALARM消息；KILL:給別的進(jìn)程發(fā)出信號(hào)指示其下一步的動(dòng)作；PAUSE:在收到下一個(gè)信號(hào)前掛起自己；REBOOT:發(fā)出信號(hào)終止所有的進(jìn)程；SIGACTION:改變調(diào)用進(jìn)程對(duì)將來收到信號(hào)的響應(yīng)方式；SIGPROCMASK:改變阻塞信號(hào)的集合；SIGSUSPEND:改變阻塞信號(hào)集合后執(zhí)行PAUSE調(diào)用；SIGPENDING:對(duì)未處理的阻塞信號(hào)進(jìn)行檢查；SIGRETURN:處理完信號(hào)后進(jìn)行清理工作。4813.4.2 實(shí)現(xiàn)4其它的系統(tǒng)

29、調(diào)用MM還有幾個(gè)很簡(jiǎn)單但是又必需的系統(tǒng)調(diào)用，MINIX把它們單獨(dú)放在一個(gè)文件getset.c中，由過程do_getset執(zhí)行：GETUID：返回有效的用戶標(biāo)號(hào)；GETGID：返回有效的分組號(hào)；GETPID：返回父子進(jìn)程的進(jìn)程號(hào)；SETUID：設(shè)置調(diào)用者有效的用戶號(hào)；SETGID：設(shè)置調(diào)用者的有效分組號(hào)；SETSID：創(chuàng)建新的會(huì)話并返回進(jìn)程號(hào)；GETPGRP：返回進(jìn)程的分組標(biāo)識(shí)。4913.5 文件系統(tǒng) 13.5.1文件系統(tǒng)概述MINIX文件系統(tǒng)(FS)的功能包括兩個(gè)方面的內(nèi)容:站在用戶的角度，文件系統(tǒng)使得用戶可以知道文件由什么組成、如何命名以及可以怎樣操作文件?？梢岳斫鉃槲募到y(tǒng)為用戶和文件間提

30、供了一個(gè)接口。從系統(tǒng)的角度來考慮，文件系統(tǒng)的功能包括：決定以怎樣的方式存儲(chǔ)文件和目錄，包括分配空間和釋放空間的過程；管理磁盤空間，比如是以鏈接表或是以位圖的方式記錄空閑存儲(chǔ)空間等等。本節(jié)中將詳細(xì)介紹以上這些功能怎樣實(shí)現(xiàn)。5013.5.1文件系統(tǒng)概述1.消息MINIX文件系統(tǒng)接收的消息種類比較多，一共有39種，其中兩個(gè)是異常消息。其中下圖列出的前面31種來自用戶進(jìn)程。后面6種來自系統(tǒng)調(diào)用，它們由MM先處理，然后調(diào)用FS完成其余工作。 5113.5.1文件系統(tǒng)概述5213.5.1文件系統(tǒng)概述5313.5.1文件系統(tǒng)概述2. i節(jié)點(diǎn)和位圖在MINIX里為了改進(jìn)順序讀取文件時(shí)的性能，要確保同一文件的所

31、有磁盤塊都位于同一個(gè)柱面上，為此引入了區(qū)段的概念，一個(gè)區(qū)段包含了多個(gè)塊。MINIX中為每個(gè)文件建立了一個(gè)索引表，表中存儲(chǔ)了文件屬性和各個(gè)塊在磁盤上的地址，這個(gè)索引表被稱為i節(jié)點(diǎn)。MINIX使用位圖來記錄空閑的i節(jié)點(diǎn)和區(qū)段，保存位圖的磁盤塊被稱為位圖塊。當(dāng)創(chuàng)建一個(gè)文件時(shí)，F(xiàn)S在位圖塊中查找第一個(gè)空閑的i節(jié)點(diǎn)，在這個(gè)i節(jié)點(diǎn)被分配后，就修改指針指向下一個(gè)節(jié)點(diǎn)。 5413.5.1文件系統(tǒng)概述3. 目錄管理目錄管理是文件系統(tǒng)的一個(gè)重要功能，我們查找一個(gè)文件，實(shí)際上就是先在目錄樹中找到文件名，然后通過對(duì)應(yīng)的i節(jié)點(diǎn)在磁盤上找到文件數(shù)據(jù)。 目錄查找過程: 5513.5.1文件系統(tǒng)概述4管道和設(shè)備文件管道和設(shè)備

32、文件與普通文件的最大不同在于，普通文件的操作通常很快就能完成，而管道有時(shí)則需要等待幾個(gè)小時(shí)才能有進(jìn)程把數(shù)據(jù)寫進(jìn)來。而調(diào)用設(shè)備文件的進(jìn)程，為了等待終端或其它設(shè)備上的I/O，時(shí)間也是不能確定的。 FS通過不發(fā)送信號(hào)的方式使得等待應(yīng)答信號(hào)的調(diào)用進(jìn)程被阻塞，一旦有別的進(jìn)程修改了管道的狀態(tài)使得被掛起的進(jìn)程可以運(yùn)行，F(xiàn)S就會(huì)設(shè)置一個(gè)標(biāo)志。到下一次主循環(huán)時(shí)，F(xiàn)S提取以前保存在進(jìn)程表中的各項(xiàng)參數(shù)，繼續(xù)執(zhí)行先前被掛起的進(jìn)程。5613.5.2 實(shí)現(xiàn)1頭文件及全局變量首先還是來看看FS使用的數(shù)據(jù)結(jié)構(gòu)和表，這些在頭文件中得到定義。const.h:定義了表長、標(biāo)志位等一些文件系統(tǒng)中使用的常量的值；glo.h:和內(nèi)存管理

33、中的glo.h文件一樣，定義了一些全局變量；proto.h:提供了ANSI標(biāo)準(zhǔn)C編譯器所支持的函數(shù)原型；type.h:定義了i節(jié)點(diǎn)在磁盤上的組織結(jié)構(gòu)。 5713.5.2 實(shí)現(xiàn)2表格管理及其使用塊、超級(jí)塊及i節(jié)點(diǎn)是文件系統(tǒng)中最重要的存儲(chǔ)結(jié)構(gòu)，對(duì)它們的管理和使用是通過一系列的過程來實(shí)現(xiàn)的。 用于管理塊的過程有：alloc_zone：用于在區(qū)段位圖中查找空閑區(qū)段，并將其分配給文件；flushall：通常被系統(tǒng)調(diào)用SYNC所調(diào)用，刷新某設(shè)備的緩沖，同時(shí)將其中內(nèi)容寫回設(shè)備；get_block：取要讀寫的塊，先檢查高速緩存，若找到就直接返回指針，否則就將其讀入緩存；put_block：釋放由get_blo

34、ck請(qǐng)求得到的塊；5813.5.2 實(shí)現(xiàn)free_zone：負(fù)責(zé)將不再使用的區(qū)段歸還給空閑區(qū)段位圖，以區(qū)段位圖和位號(hào)為參數(shù)調(diào)用free_bit；rw_block：提供了一個(gè)簡(jiǎn)單的磁盤界面，負(fù)責(zé)在內(nèi)存和磁盤間傳送塊；invalidate：刪除某個(gè)設(shè)備在高速緩存中用過的所有塊；rw_scattered：以設(shè)備標(biāo)志符、緩沖區(qū)指針數(shù)組的指針、數(shù)組長度及讀寫標(biāo)志為參數(shù)，執(zhí)行在設(shè)備上讀/寫分散數(shù)據(jù)的任務(wù)；rm_lru：只被get_block調(diào)用，負(fù)責(zé)從LRU鏈中刪除一個(gè)塊。5913.5.2 實(shí)現(xiàn)用于超級(jí)塊管理的過程略少一些，下面的五個(gè)過程用于超級(jí)塊和位圖的管理：alloc_bit：從區(qū)段位圖或i節(jié)點(diǎn)位圖中

35、分配一位，通常被alloc_inode或alloc_zone以循環(huán)嵌套的方式調(diào)用；free_bit：從區(qū)段位圖或i節(jié)點(diǎn)位圖中釋放一位，首先計(jì)算哪一個(gè)位圖塊包含了要釋放的位，調(diào)用get_block將這個(gè)位圖塊讀入內(nèi)存，將相應(yīng)位置0，再調(diào)用put_block將該塊寫回磁盤；get_super：用于在超級(jí)塊表中搜索特定設(shè)備；mounted：關(guān)閉塊設(shè)備時(shí)調(diào)用，以一個(gè)指向設(shè)備i節(jié)點(diǎn)的指針為參數(shù)，返回報(bào)告這個(gè)i節(jié)點(diǎn)是否在被掛裝的文件系統(tǒng)上。Read_super：在讀超級(jí)塊時(shí)調(diào)用，檢查所讀出的文件系統(tǒng)的版本號(hào)，并進(jìn)行相應(yīng)的轉(zhuǎn)換。6013.5.2 實(shí)現(xiàn)用于管理i節(jié)點(diǎn)的過程有：get_inode：將一個(gè)i節(jié)點(diǎn)讀入內(nèi)存，首先搜索inode表，若找到則將指針返回；若不在內(nèi)存中則調(diào)用rw_inode將其讀入；put_inode：返回不再使用的i節(jié)點(diǎn)，并把計(jì)數(shù)器icount減1；alloc_inode：為新文件分配i節(jié)點(diǎn)；wipe_inode：將i節(jié)點(diǎn)中某些域清除，同時(shí)也負(fù)責(zé)部分初始化i節(jié)點(diǎn)的工作；free_inode：釋放i節(jié)點(diǎn)；update_times：從系統(tǒng)時(shí)鐘獲得時(shí)間，同步修改i節(jié)點(diǎn)中的時(shí)間域；rw_inode：負(fù)責(zé)在內(nèi)存和磁盤間傳送i節(jié)點(diǎn)；old_icopy：轉(zhuǎn)換要執(zhí)行寫操作的i節(jié)點(diǎn)內(nèi)容；new_icopy：對(duì)由i節(jié)