第二章 軟件基
第二章 軟件基礎
程序是執行某個特定任務的計算機指令集合。程序可以用多種程序語言來編寫：從低級計算機語言-匯編語言到高級的、與機器本身無關的語言入C程序語言。操作系統是一個允許用戶運行如電子表格或者字處理軟件等應用程序的特殊程序。本章將介紹程序設計的基本原則，同時給出操作系統設計目標與功能的概述。
2.1 計算機編程語言
2.1.1 匯編語言
那些CPU從主存讀取出來執行的指令對人類來說是根本不可理解的。它們是告訴計算機如何准確動作的機器代碼。在Intel 80486指令中16進制數0x89E5表示將ESP寄存器的內容拷入EBP寄存器。為最早的計算機設計的工具之一就是匯編器，它可以將人們可以理解的源文件匯編成機器代碼。匯編語言需要顯式的操作寄存器和數據，並且與特定處理器相關。比如說Intel X86微處理器的匯編語言與Alpha A
XP微處理器的匯編語言決然不同。以下是一段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核心中只有很少一部分是用匯編語言編寫，並且這些都是為了提高效率或者是需要兼容不同的CPU。
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支持許多類型的變量，變量是一個通過符號名稱引用的內存位置。在以上的例子中，X和Y都是內存中的位置。
程序員並不關心變量放在什麼地方，這些工作由連接程序來完成。有些變量包含不同類型的數據，整數和浮點數，以及指針。 指針是那些包含其他數據內存位置或者地址的變量。假設有變量X，位於內存地址0x80010000處。你可以使用指針變量px來指向X，則px的值為0x80010000。 C語言允許相關變量組合起來形成數據結構，例如：
struct {
int i ;
char b ;
} my_struct ;
這是一個叫做my_struct的結構，它包含兩個元素，一個是32位的整數i,另外一個是8位的字符b。
2.1.3 連接程序
連接程序是一個將幾個目標模塊和庫過程連接起來形成單一程序的應用。目標模塊是從匯編器或者編譯器中產生的機器代碼，它包含可執行代碼和數據，模塊結合在一起形成程序。例如一個模塊可能包含程序中所有的
數據庫函數而另一個主要處理命令行參數。連接程序修改目標模塊之間的引用關系，使得在某一模塊中引用的數據或者子程序的確存在於其他模塊中。Linux核心是由許多目標模塊連接形成的龐大程序。
2.2 操作系統概念
如果沒有軟件，計算機只不過是一堆發熱的電子器件。如果將硬件比做計算機的心髒則軟件就是它的靈魂。操作系統是一組系統程序的集合，它提供給用戶運行應用軟件的功能。操作系統對系統硬件進行抽象，它提供給系統用戶一台虛擬的機器。大多數PC可以運行一種或者多種操作系統，每個操作系統都有不同的外觀。Linux由許多獨立的功能段組成。比如Linux內核，如果沒有庫函數和外殼程序，內核是沒有什麼用的。 為了理解操作系統到底是什麼，思考一下當你敲入一個簡單命令時，系統中發生了什麼：
$ ls
Mail c images perl
docs tcl
$
$符號是由用戶登錄外殼(這裡指Bash)提供的提示符。它表示正在等待用戶敲入一些命令。敲入ls命令，首先鍵盤驅動程序識別出敲入的內容。然後鍵盤驅動將它們傳遞給外殼程序，由外殼程序來負責查找同名的可執行程序(ls)。 如果在/bin/ls目錄中找到了ls，則調用核心服務將ls的可執行映象讀入虛擬內存並開始執行。ls調用核心的文件子系統來尋找那些文件是可用的。文件系統使用緩沖過的文件系統信息，或者調用磁盤設備驅動從磁盤上讀取信息。當然ls還可能引起網絡驅動程序和遠程機器來交換信息以找出關於系統要訪問的遠程文件系統信息(文件系統可以通過網絡文件系統或者NFS進行遠程安裝)。當得到這些信息後，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一樣，系統中的獨立文件系統不是通過設備標志符來訪問，而是通過表示文件系統的層次樹結構來訪問。當Linux添加一個新的文件系統到系統中時，會將它mount到一個目錄下，比如說/mnt/cdrom。 Linux的一個重要特征就是支持多種文件系統。這使得它非常靈活並且可與其他操作系統並存。Linux中最常用的文件系統是EXT2文件系統，它在大多數Linux分發版本中都得到了支持。 文件系統提供給用戶一個關於系統的硬盤上文件和目錄的總體映象，而不管文件的類型和底層物理設備的特性。 Linux透明地支持多種文件系統並將當前安裝的所有文件和文件系統集成到虛擬文件系統中去。所以，用戶和進程一般都不知道某個文件位於哪種文件系統中，他們只是使用它。 塊設備驅動將物理塊設備類型（例如IDE和SCSI）和文件系統中的差別隱藏起來，物理設備只是數據塊的線性存儲集合。設備的不同導致塊大小的不同，從軟盤設備的512字節到IDE磁盤的1024字節。這些都隱藏了起來，對系統用戶來說這都是不可見的。不管設備類型如何，EXT2文件系統看起來總是一樣。
2.3 核心數據結構
操作系統可能包含許多關於系統當前狀態的信息。當系統發生變化時，這些數據結構必須做相應的改變以反映這些情況。例如，當用戶登錄進系統時將產生一個新的進程。核心必須創建表示新進程的數據結構，同時 將它和系統中其他進程的數據結構連接在一起。 大多數數據結構存在於物理內存中並只能由核心或者其子系統來訪問。數據結構包括數據和指針；還有其他數據結構的地址或者子程序的地址。它們混在一起讓Linux核心數據結構看上去非常混亂。盡管可能被幾個核心子系統同時用到，每個數據結構都有其專門的用途。理解Linux核心的關鍵是理解它的數據結構以及Linux核心中操縱這些數據結構的各種函數。本書把Linux核心的 描敘重點放在數據結構上，主要討論每個核心子系統的算法，完成任務的途徑以及對核心數據結構的使用。
2.3.1 連接列表
Linux使用的許多
軟件工程的技術來連接它的數據結構。在許多場合下，它使用linked或者chained數據結構。 每個數據結構描敘某一事物，比如某個進程或網絡設備，核心必須能夠訪問到所有這些結構。在鏈表結構中，個根節點指針包含第一個結構的地址，而在每個結構中又包含表中下一個結構的指針。表的最後一項必須是0或者NULL，以表明這是表的尾部。在雙向鏈表中，每個結構包含著指向表中前一結構和後一結構的指針。使用雙向鏈表的好處在於更容易在表的中部添加與刪除節點，但需要更多的內存操作。這是一種典型的操作系統開銷與CPU循環之間的折中。
2.3.2 散列表
鏈表用來連接數據結構比較方便，但鏈表的操作效率不高。如果要搜尋某個特定內容，我們可能不得不遍歷整個鏈表。Linux使用另外一種技術:散列表來提高效率。散列表是指針的數組或向量，指向內存中連續的相鄰數據集合。散列表中每個指針元素指向一個獨立鏈表。如果你使用數據結構來描敘村子裡的人，則你可以使用年齡作為索引。為了找到某個人的數據，可以在人口散列表中使用年齡作為索引，找到包含此人特定數據的數據結構。但是在村子裡有很多人的年齡相同，這樣散列表指針變成了一個指向具有相同年齡的人數據鏈表的指針。搜索這個小鏈表的速度顯然要比搜索整個數據鏈表快得多。 由於散列表加快了對數據結構的訪問速度，Linux經常使用它來實現Caches。Caches是保存經常訪問的信息的子集。經常被核心使用的數據結構將被放入Cache中保存。Caches的缺點是比使用和維護單一鏈表和散列表更復雜。尋找某個數據結構時，如果在Cache中能夠找到（這種情況稱為cache 命中），這的確很不錯。但是如果沒有找到，則必須找出它，並且添加到Cache中去。如果Cache空間已經用完則Linux必須決定哪一個結構將從其中拋棄，但是有可能這個要拋棄的數據就是Linux下次要使用的數據。
2.3.3 抽象接口
Linux核心常將其接口抽象出來。接口指一組以特定方式執行的子程序和數據結構的集合。例如，所有的網絡設備驅動必須提供對某些特定數據結構進行操作的子程序。通用代碼可能會使用底層的某些代碼。例如網絡層代碼是通用的，它得到遵循標准接口的特定設備相關代碼的支持。 通常在系統啟動時，底層接口向更高層接口注冊(Register)自身。這些注冊操作包括向鏈表中加入結構節點。例如，構造進核心的每個文件系統在系統啟動時將其自身向核心注冊。文件/proc/filesysems中可以看到已經向核心注冊過的文件系統。注冊數據結構通常包括指向函數的指針，以文件系統注冊為例，它向Linux核心注冊時必須將那些mount文件系統連接時使用的一些相關函數的地址傳入。
