Linux Kemel - 軟體基礎

軟件基礎

程序就是一組執行特定任務的計算機指令。程序既可以用非常低級的計算機語言--匯編語言，也可以用高級的、獨立于機器的語言如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時必須調用。