程式就是一組執行特定任務的電腦指令。程式既可以用非常低階的電腦語言--組合語言語 言，也可以用高階的、獨立於機器的語言如C來編寫。作業系統是一種特殊的程式，它允 許用戶運行各種應用程式如制表程式和字處理程式。本章介紹基本的程式設計原理，並對 作業系統的目標和功能做一綜述。 2.1 電腦語言 2.1.1 組合語言 CPU從記憶體中取出並運行的指令對人來說根本無法理解。它們是精確指示機器如何操作的 機器程式碼。例如，十六進制數0x89E5是Intel80486的一條指令，把ESP暫存器的內容拷 到EBP暫存器中。組譯器是最早發明的軟體工具之一，它輸入人類可以理解的原始碼， 組合語言為機器程式碼。組合語言外顯地處理暫存器和資料操作，與特定的微處理器相關（應為 與特定的處理器相關--譯者注）。IntelX86微處理器的組合語言就與Alpha AXP微處理器 的組合語言大相徑庭。以下Alpha AXP組合語言程式碼表示了程式可以進行的一種操作： ldr r16, (r15) ; Line 1 ldr r17, 4(r15) ; Line 2 beq r16,r17,100 ; Line 3 str r17, (r15) ; Line 4 100: ; Line 5 第一條指令（見第一行）把暫存器15存放的位址中的內容裝入暫存器16。下一條指令把 記憶體中下一個位置的內容裝入暫存器17。第三行把暫存器16和暫存器17的內容比較，如 果相等，分支轉向標號100。如果兩個暫存器包含數值不等，程式繼續運行第四行，把寄 存器17的內容存到記憶體。如果兩個暫存器包含數值相等，那麼沒有資料需要保存。編寫 組合語言程式枯燥乏味、技巧性強而且易於出錯。Linux核心只有很少的一點用組合語言 編寫，目的是為了效率，這些部份是與特定機器相關的。 2.1.2 C語言和編譯器 用組合語言編寫大型程式十分困難而且消耗大量時間。這樣做易於出錯，得到的程式也無 法移植，限制在特定的處理器族上。用獨立於機器的語言如C，會好得多。C允許你用邏 輯演算法和其操作的資料結構來描述程式。叫作編譯器的特定程式讀入C程式，並把它翻譯 成組合語言，生成相應的機器程式碼。好的編譯器所產生的組合語言指令的效率接近於好的組合語言 語言程式設計師編寫的組合語言程式。大部份Linux核心是用C語言編寫的。以下的C片段： if (x != y) x = y ; 與前一個例子中組合語言程式碼的操作完全相同。如果變數x和y的內容並不完全相同，就把y 的內容拷給x。C程式碼組織為例程，每一個例程執行一個任務。例程可以返回C支援的任 何數值或者資料類型。像Linux核心這樣的大型程式包含很多獨立的C源模組，每個模組 都有自己的例程和資料結構。這些C原始碼模組把像檔案系統處理這樣的邏輯功能組合在 一起。 C支援很多類型的變數。所謂變數，就是記憶體中的一個位置，可以用符號名字來引用。在 以上C片段中，x和y指引了記憶體中的位置。程式設計師不關心變數究竟存放在記憶體中的何 處，這是連接器（見下面所述）的任務。一些變數含有不同類型的資料、整數和浮點數， 另一些則是指標。 指標就是包含位址--其它資料在記憶體中的位置，的變數。考慮叫做x的變數，它可能處於 記憶體位址0x80010000。你可以有一個指標，叫做px，指向x。px可能處於位址 0x80010030，而px的值是0x80010000，變數x的位址。 C允許你把相關的變數綁在一起，形成資料結構。例如， struct { int i ; char b ; } my_struct ; 是一個叫做my_struct的資料結構，它包含兩個元素：叫做i的整數（32位資料）和叫做b 的字元（8位資料）。 2.1.3 連接器 連接器是一種程式，它可以把幾個目標模組和函式庫連接在一起，產生一個獨立的、自洽的程 序。目標模組是組譯器或編譯器生成的機器程式碼輸出，含有可執行的機器程式碼和資料，以 及允許連接器把模組連接起來的信息。例如一個模組可能含有程式中所有的資料函式庫函數， 而另外一個則含有命令行參數處理函數。連接器負責解決目標模組之間的引用，例如一個 模組中引用的例程或資料結構事實上在另外一個模組之中。Linux核心就是一個與很多成 員目標模組連接在一起的獨立大程式。 2.2 什麼是作業系統？ 沒有軟體的電腦就是一堆發熱的電子元件。如果說硬體是電腦的核心，那麼軟體就是 電腦的靈魂。所謂作業系統，就是允許用戶在其上運行應用軟體的一組系統程式。操作 系統對系統的真正硬體進行抽像，向系統的用戶和應用程式給出一個虛擬機。在很現實的 意義上說，軟體提供了系統的特點。絕大部份PC能運行一個或多個作業系統，每一個作業 系統都有一個完全不同的外觀和風格。Linux是由一批功能上分離的部件組成，其中明顯 的一個是核心。但是即使是核心，如果脫離函式庫和外殼程式也是沒有用的。 為了開始理解什麼是作業系統，請考慮當你敲入以下的簡單命令時會發生的情況： $ ls Mail c images perl docs tcl $ 這裡$是由登錄外殼程式（在此例為bash）給出的提示符。這意味著它在等待你--用戶， 敲入命令。敲入ls後，鍵盤驅動程式識別出已經有字元輸入。鍵盤驅動程式把這些字元傳 給外殼程式，外殼程式則通過尋找可執行程式的映像來處理這個命令。它在/bin/ls發現了 映像，於是調用核心服務來把ls可執行程式的映像拖入虛擬記憶體，開始執行。ls的映像調 用核心的檔案子系統，以找出有哪些檔案可以獲得。檔案系統有可能要使用放在cache中 的檔案系統的信息或者用磁碟驅動程式來從磁碟讀出這些信息，甚至可能用網路驅動程式 與遠程機器交換信息，以找出本系統能夠存取的遠程檔案的細節（檔案系統可以通過"網 絡檔案系統"NFS來遠程mount）。無論是用哪種方式定位信息，ls都會把信息寫出來，由 視頻驅動程式把它顯示在螢幕上。 以上看起來很復雜，但是說明了一個道理：即使是最簡單的命令，也需要相當的處理，操 作系統事實上是一組互相合作的函數，它們在整體上給用戶以一個系統的完整印像。（以 上一句是根據譯者理解翻譯的，未必忠實於原文--譯者注） 2.2.1 記憶體管理 如果有無限的資源，例如記憶體，很多作業系統需要做的事情都是多餘的。作業系統的一個 基本技巧是使一小塊記憶體看起來像很多記憶體。這種表面上的大記憶體稱為虛擬記憶體。其思想 是使系統中運行的軟體以為它在很多記憶體上運行。系統把記憶體分成很多容易控制的頁面， 把一些頁面交換到硬碟上。由於另外的一個技巧--多工處理，軟體注意不到這一點。 2.2.2 程序 程序可以想像為一個活動中的程式。每一個程序是一個獨立的實體，在運行一個特定程 序。如果你看看你的Linux系統中的程序，你就會發現一大堆。例如，在我的系統中敲入 ps可以顯示如下程序： $ ps PID TTY STAT TIME COMMAND 158 pRe 1 0:00 -bash 174 pRe 1 0:00 sh /usr/X11R6/bin/startx 175 pRe 1 0:00 xinit /usr/X11R6/lib/X11/xinit/xinitrc -- 178 pRe 1 N 0:00 bowman 182 pRe 1 N 0:01 rxvt -geometry 120x35 -fg white -bg black 184 pRe 1 < 0:00 xclock -bg grey -geometry -1500-1500 -padding 0 185 pRe 1 < 0:00 xload -bg grey -geometry -0-0 -label xload 187 pp6 1 9:26 /bin/bash 202 pRe 1 N 0:00 rxvt -geometry 120x35 -fg white -bg black 203 ppc 2 0:00 /bin/bash 1796 pRe 1 N 0:00 rxvt -geometry 120x35 -fg white -bg black 1797 v06 1 0:00 /bin/bash 3056 pp6 3 < 0:02 emacs intro/introduction.tex 3270 pp6 3 0:00 ps $ 如果我的系統有很多CPU，每個程序（至少在理論上）可以運行在一個不同的CPU上。 不幸的是，我只有一個CPU，所以系統只能求助於讓每個程序輪流運行一小段時間的辦 法。這一小段時間稱為時間片。這種技巧稱為多工處理或者排程，它使得每個程序以為自 己是唯一的程序。在程序之間進行保護，以便當一個程序崩潰或者錯誤時，不會影響其它 程序。作業系統給每個程序一個單獨的、只有它自己能存取的位址空間，以達到這樣的目 的。 2.2.3 設備驅動程式 設備驅動程式構成了Linux核心的主要部份。就像作業系統的其它部份一樣，設備驅動程 序在高優先級的環境下運行，一旦發生錯誤就可能造成危險。設備驅動程式控制作業系統 和其控制的硬體設備之間的互相作用。例如，在把塊寫到IDE硬碟時，檔案系統使用一個 通用區塊設備介面。驅動程式負責細節，控制與設備相關的事情。設備驅動程式是針對其控 制的特定晶片的，所以如果你有一個NCR810 SCSI控制器，那麼你就需要一個NCR810 SCSI驅動程式。 2.2.4 檔案系統 在Linux中，就像在Unix中一樣，系統可以使用的不同的檔案系統並非通過設備標識來 存取（例如磁碟機號或磁碟機名），而是被組織在一個單一的分層樹結構裡，每個檔案系 統用一個實體來表示。檔案系統通過把新的檔案系統mount在某個目錄下--例如 /mnt/cdrom，從而把新的檔案系統加入樹中。Linux的最重要特點之一是支援多個不同的文 件系統，這使得其伸縮性好，易於與其它作業系統共存。最廣為人知的Linux檔案系統是 EXT2，受到所發行的絕大部份的Linux的支援。 檔案系統屏蔽了下層實體設備或檔案系統類型的細節，給予用戶察看硬碟上檔案和目錄的 一個清楚視角。Linux透明地支援多種不同檔案系統（例如MS-DOS和EXT2），把所有 mount上的檔案和檔案系統都組織在一個虛擬檔案系統之中。所以，一般而言，用戶和進 程並不需要知道哪個檔案在哪個檔案系統之中，只需要直接去用它就可以了。 區塊設備驅動程式隱藏了實體區塊設備類型之間的差別（例如IDE和SCSI的差別），從檔案 系統的角度來看，實體設備只是資料塊的線形聚集。不同設備的塊大小不同，例如軟碟通 常是512位元，而IDE設備通常是1024位元，但是系統的用戶是看不到這一點的。無論 放在什麼設備上，EX2檔案系統看起來都一樣。 2.3 核心資料結構 作業系統必須保存關於系統目前狀態的很多信息。在系統中發生了事情之後，這些資料結 構必須修改，以反映目前的真實狀況。例如，在一個用戶登錄到系統之後，可能會創建一 個新的程序。核心必須創建表示新程序的資料結構，並把它和表示系統中所有其它程序的 資料結構連接在一起。 通常這些資料結構存在於實體記憶體之中，只能由核心及其子系統存取。資料結構包括資料 和指標--其它資料結構的位址或例程的位址。總而言之，Linux使用的資料結構看起來很 復雜難懂。雖然其中某些可能為幾個核心子系統所使用，但是每個資料結構都有其目的， 所以這些資料結構事實上比剛看起來要簡單。（以上一句是根據譯者的理解翻譯，未必正 確和符合原文--譯者注） 理解Linux核心依賴於理解其資料結構以及核心中各種函數對資料結構的使用。本書對 Linux核心的描述就是基於其資料結構的。本書討論了每個核心子系統的演算法、完成工作 的方法和對核心資料結構的使用。 2.3.1 鏈結串列 Linux使用一系列軟體工程技術來把資料結構連接起來。在很多情況下要使用鏈結串列。如果 每個資料結構描述某事物的一個實例或一次發生，例如一個程序或一個網路設備，那麼核 心就必須能夠找到所有的實例。在鏈結串列中，根指標含有表中第一個資料結構，或者稱為 “元素”，的位址，而每個資料結構都含有一個指向表中下一個元素的next指標。最後一 個元素的next指標為0或NULL，以示它已經是表尾。在雙向鏈結串列中，每個元素含有指向表 中下一個元素的next指標和指向表中前一個元素的previous指標。使用雙向鏈結串列方便了增加 或刪除表中間的元素，當然，記憶體的存取也增加了。這是一個典型的作業系統中的折衷： 消耗記憶體存取與消耗CPU周期的折衷。 2.3.2 Hash表 鏈結串列可以方便地把資料結構綁在一起，但是瀏覽鏈結串列效率很低。如果你想尋找特定的一個 元素，很可能回不得不看完全表才找到需要的那個。Linux使用Hash技術來避開這個限 制。所謂Hash表，是一個指標的陣列或者向量。這裡說的陣列或者向量，是指記憶體中的 一組順序存放的東西。因此，書架可以說成是書的陣列。陣列使用索引進行存取，而索引 就是陣列中位置的偏移量。把書架的比喻繼續下去，你可以通過在書架上的位置來描述每 本書。例如，你可以要求拿第5本書。 所謂Hash表，是指向資料結構的指標陣列，採用資料結構中的信息作為Hash表的索引。 如果你有描述村庄人口的資料結構，那麼你可以採用人的年齡作為索引。為了尋找某個特 定人的資料，你可以採用年齡作為人口Hash表的索引，然後按照指標找到含有此人細節 的資料結構。（這裡的指標相當於普通教科書上所說的Hash函數：Hash(ad)=*ad，--譯者 注）不幸的是，很可能村中的許多人年齡相同，所以Hash表的指標成了指向一個資料結 構鏈的指標，每個資料結構描述相同年齡的一個人。然而，搜索這些短鏈還是比搜索全部 資料結構要快。 由於Hash表加快了普通資料的存取，Linux經常使用Hash表來實現cache。cache通常是 總體信息的一部份，被抽出來需要加速存取。作業系統常用的資料結構要放在cache中保 存。cache的不利之處在於使用和維護都比簡單鏈結串列或Hash表更加復雜。假如能在cache 中找到資料結構（稱為“命中”），那麼好得很。假如找不到，那麼所有相關資料結構都 要被搜索，如果最終能找到，那麼該資料結構將被加入cache中。把新的資料結構加入 cache 可能會需要擠出一個舊的cache項入口。Linux必須決定到底擠出哪一個才好，以盡 可能避免恰恰擠出下面要用的資料結構。 2.3.3 抽像介面 Linux核心經常對介面進行抽像。所謂介面，是例程和資料結構的集合，它通過某種特定 方式進行操作。例如所有的網路設備驅動程式必須提供操作某些特定資料結構的某些特定 例程。這樣，就能有使用低階特殊程式碼的通用程式碼層。例如網路層是通用的，受到遵循標 准介面的與設備相關的程式碼的支援。 通常這些低階在啟動時註冊到高層。註冊時一般要把一個資料結構加到一個鏈結串列中。例如 核心中內置的每個檔案系統在啟動時或者（如果使用模組的話）首次使用時註冊到核心。 通過查看檔案/proc/filesystems能夠看到哪些檔案系統已經註冊。註冊資料結構通常包含函 數指標。這些都是進行特定任務的軟體函數的位址。再次用檔案系統註冊作為一個例子， 每個檔案系統在註冊時傳給Linux核心的的資料結構包含與檔案系統相關的函數位址，這 些函數在該檔案系統mount時必須調用。