一直以來(lái)，我們都在討論是該學(xué)VC還是 BCB還是 VB 還是JAVA。其實(shí)，對于真正要立志于從事程序設計或信息安全事業(yè)的同志來(lái)說(shuō)，這些討論根本就沒(méi)有意義！我們到底該學(xué)什么？我們 應該從何開(kāi)始？我個(gè)人認為，應該從操作系統開(kāi)始！——去真正的認識操作系統。了解、分析它的工作是怎么樣實(shí)現的。我們可以這樣說(shuō) ，操作系統就是一個(gè)最龐大功能最強的程序。那么，拋開(kāi)各種功利的誘惑，定下心來(lái)認認真真地從操作系統學(xué)起，才能掌握編程的真諦。 在操作統種，幾乎每一個(gè)知識點(diǎn)都被用上了。當你真正研究了它、閱讀了它的代碼后，那么，象算法、數據結構、內存管理、網(wǎng)絡(luò )協(xié)議、 進(jìn)程管理。。。。之類(lèi)編程的核心問(wèn)題也就被你了如指掌了。到那時(shí)，寫(xiě)出高質(zhì)量的代碼不就不在話(huà)下了嗎？（建議裝liunx 或unix)
：（各位初學(xué)者：看不懂也要硬著(zhù)頭皮看下去。切記！切記?。?
一。硬件基礎：
1.1 CPU
CPU，或者微處理器，是計算機系統的核心。微處理器進(jìn)行計算或者邏輯操作并且管理來(lái)自主存的指令并執行它。在計算機的早期時(shí)代 ，微處理器的功能部件使用的是分立元件（外型很大）。 這就是中央處理單元這一名詞的由來(lái)?，F代微處理器將部件結合到小型硅片上的集成電路中。在本書(shū)中CPU和微處理器及處理器有相同 的意義。 微處理器的操作對象是二進(jìn)制數據；數據由0和1組成。 1和0對應著(zhù)電子開(kāi)關(guān)的開(kāi)路與斷路狀態(tài)。正如十進(jìn)制的42表示有4個(gè)10和一個(gè)2一樣，一個(gè)二進(jìn)制數是一系列表示2的次冪的二進(jìn) 制數字組成。二進(jìn)制0001對應十進(jìn)制的1，二進(jìn)制的0010對應十進(jìn)制的2，二進(jìn)制的0011表示3，而0100對應4。十進(jìn) 制42的二進(jìn)制表示為101010。但是在計算機程序中， 人們常用十進(jìn)制來(lái)表示數而不是直接使用二進(jìn)制。
在需要使用二進(jìn)制數時(shí)，人們往往使用16進(jìn)制數。如十進(jìn)制數只能從0到9一樣，16進(jìn)制數可以從0疏導15，其中10到15分別 用字母A、B、C、D、E及F來(lái)表示。這樣16進(jìn)制的2A的十進(jìn)制表示為42-2*16+10=42。在C程序語(yǔ)言中，16進(jìn)制 數的前綴為"0x"；16進(jìn)制的2A寫(xiě)成0x2A。 微處理器可以執行如加、乘和除以及象"X是否比Y大"這種邏輯運算。
處理器的執行由外部時(shí)鐘來(lái)監控。這個(gè)時(shí)鐘稱(chēng)為系統時(shí)鐘，它每隔相同的時(shí)間間隔就向CPU發(fā)送一個(gè)脈沖。在每個(gè)時(shí)鐘脈沖上，處理器 都會(huì )做一些工作。比如，處理器每個(gè)時(shí)鐘脈沖上執行一條指令。處理器的速度一般以系統時(shí)鐘的速率來(lái)描敘。一個(gè)100MHz的處理器 每秒將接收100,000,000 個(gè)時(shí)鐘滴答。但是用CPU的時(shí)鐘頻率來(lái)描敘CPU的工作能力是不正確的，因為它們執行的指令不相同。
然而，快速的時(shí)鐘可以在某種程度上代表高性能的CPU。處理器執行的指令是非常簡(jiǎn)單的；例如"將內存X處的內容讀入寄存器Y"。 寄存器是微處理器的內部存儲部件，用來(lái)存儲數據并對數據執行某些指令。有些指令有可能使處理器停止當前的工作而跳轉到內存中另外 一條指令執行?，F代微處理器的緊湊設計使得它有可能每秒執行上百萬(wàn)甚至億條指令。
指令執行前必須從內存中取出來(lái)。指令自身要使用的數據也必須從內存中取出來(lái)并放置在適當的地方。
微處理器中寄存器的大小、數量以及類(lèi)型都取決于微處理器的類(lèi)型。Intel 80486處理器和Alpha AXP 有迥然不同的寄存器，最明顯的區別在于Intel 寄存器為32位而Alpha AXP為64位。一般來(lái)說(shuō)，任何處理器都有許多通用寄存器和少量專(zhuān)用寄存器。許多微處理器有以下幾種特定的寄存器。
程序計數器(PC)
此寄存器包含下條指令執行的地址。每當取回一條指令時(shí)，PC的內容將自動(dòng)增加。
堆棧指針(SP)
微處理器經(jīng)常需要訪(fǎng)問(wèn)存儲臨時(shí)數據的外部RAM。堆棧是一種便捷的存放臨時(shí)數據的方法，處理器提供了特殊指令來(lái)將數值壓入堆棧然 后將其從堆棧中彈出。
堆棧以后進(jìn)先出(LIFO)的方式工作。換句話(huà)說(shuō)，如果你壓入兩個(gè)值X和Y，然后執行彈棧操作，你將取到Y的值。 有些處理器的堆棧從內存頂部向下增長(cháng)而有些相反。但有的處理器同時(shí)支持這兩種方式，如ARM。
處理機狀態(tài)字(PS)
指令的執行將得到執行結果；比如"寄存器X中的內容要大于寄存器Y中的內容？"將得到正確或錯誤作為結果。PS寄存器包含著(zhù)這些 信息及有關(guān)處理器當前狀態(tài)的其他信息。例如大多數處理器至少有兩種執行方式，核心（或管態(tài)）與用戶(hù)方式。PS寄存器包含表示當前 執行方式的信息。
1.2 內存
所有計算機系統都有一個(gè)由不同速度與大小的存儲器組成的層次結構。最快的的存儲器是高速緩存，它被用來(lái)暫存主存中的內容。這種存 儲器速度非?？斓浅０嘿F，大多數處理器都有少量的片上高速緩存或者將其放在主板上。有些處理器的高速緩存既包含數據也包含指令 ，但有些將其分成兩部分。 Alpha AXP處理器有兩個(gè)內部高速緩存，一個(gè)用來(lái)緩存數據（D-Cache）而另一個(gè)用來(lái)緩存指令（I- Cache）。而外部高速緩存（B-Cache）將兩者混合。這樣，相對外部高速緩存存儲器，主存的速度非常慢。
高速緩存與主存中的內容必須保持一致。換句話(huà)說(shuō)，對應于地址空間的同一個(gè)位置，如果該位置的數據被緩存入高速緩存，則其內容必須 和主存中的一致。保證高速緩存一致性的工作由硬件和操作系統共同分擔。 這就是在系統中硬件和軟件必須緊密協(xié)作的原因。
1.3 總線(xiàn)
主板上分立的部件通過(guò)稱(chēng)為總線(xiàn)的線(xiàn)路連接在一起。系統總線(xiàn)的功能在邏輯上被劃分為三部分：
地址總線(xiàn)、數據總線(xiàn)和控制總線(xiàn)。地址總線(xiàn)為數據傳輸指明內存位置（地址）。數據總線(xiàn)包含傳輸的數據。數據總線(xiàn)是雙向的；它允許數 據讀入CPU也支持從CPU讀出來(lái)?？刂瓶偩€(xiàn)則包含幾條表示路由分時(shí)和系統的控制信號。當然還有其他一些總線(xiàn)存在，例如ISA和 PCI總線(xiàn)是將外設連接到系統的常用方式。
1.4 控制器與外設
外設是一些物理設備，比如說(shuō)圖象卡或者磁盤(pán)，它們受控于位于主板或者主板上插槽中的控制芯片。 IDE磁盤(pán)被IDE控制器芯片控制而SCSI磁盤(pán)由SCSI磁盤(pán)控制器芯片控制。這些控制器通過(guò)各種總線(xiàn)連接到CPU上或相互間 互連。目前制造的大多數系統使用PCI和ISA總線(xiàn)來(lái)連接主要系統部件?？刂破魇且恍╊?lèi)似CPU的處理器，它們可以看做CPU的 智能幫手。CPU則是系統的總控。 雖然所有這些控制器互不相同，但是它們的寄存器的功能類(lèi)似。運行在CPU上的軟件必須能讀出或者寫(xiě)入這些控制寄存器。其中有一個(gè) 寄存器可能包含指示錯誤的狀態(tài)碼。另一個(gè)則用于控制目的，用來(lái)改變控制器的運行模式。在總線(xiàn)上的每個(gè)控制器可以被CPU所單獨尋 址，這是軟件設備驅動(dòng)程序能寫(xiě)入寄存器并能控制這些控制器的原因。
1.5 地址空間
系統總線(xiàn)將CPU與主存連接在一起并且和連接CPU與系統硬件外設的總線(xiàn)隔離開(kāi)。一般來(lái)說(shuō)，硬件外設存在的主存空間叫I/O空間 。I/O空間還可以進(jìn)一步細分，但這里我們不再深究。CPU既可以訪(fǎng)問(wèn)系統內存空間又可以訪(fǎng)問(wèn)I/O空間內存，而控制器自身只能 在CPU協(xié)助下間接的訪(fǎng)問(wèn)系統內存。從設備的角度來(lái)看，比如說(shuō)軟盤(pán)控制器，它只能看到在ISA總線(xiàn)上的控制寄存器而不是系統內存 。典型的CPU使用不同指令來(lái)訪(fǎng)問(wèn)內存與I/O空間。例如，可能有一條指令"將I/O地址0x3F0的內容讀入到寄存器X"。這 正是CPU控制系統硬件設備的方式：通過(guò)讀寫(xiě)I/O地址空間上的外設寄存器。在I/O空間中通用外設(IDE控制器、串行口、軟 盤(pán)控制器等等)上的寄存器經(jīng)過(guò)多年的PC體系結構發(fā)展基本保持不變。I/O地址空間0x3f0是串行口(COM1)的控制寄存器 之一。 有時(shí)控制器需要直接從系統主存中讀寫(xiě)大量數據。例如當用戶(hù)將數據寫(xiě)入硬盤(pán)時(shí)。在這種情況下，直接內存訪(fǎng)問(wèn)(DMA)控制器將用來(lái) 允許硬件外設直接訪(fǎng)問(wèn)系統主存，不過(guò)這將處于CPU的嚴格監控下。
1.6 時(shí)鐘
所有的操作系統都必須準確的得到當前時(shí)間，所以現代PC包含一個(gè)特殊的外設稱(chēng)為實(shí)時(shí)時(shí)鐘(RTC)。它提供了兩種服務(wù)：可靠的日 期和時(shí)間以及精確的時(shí)間間隔。RTC有其自身的電池這樣即使PC掉電時(shí)它照樣可以工作，這就是PC總是"知道"正確時(shí)間和日期的 原因。而時(shí)間間隔定時(shí)器使得操作系統能進(jìn)行準確的調度工作。
二。 軟件基礎
程序是執行某個(gè)特定任務(wù)的計算機指令集合。程序可以用多種程序語(yǔ)言來(lái)編寫(xiě)：從低級計算機語(yǔ)言-匯編語(yǔ)言到高級的、與機器本身無(wú)關(guān) 的語(yǔ)言入C程序語(yǔ)言。操作系統是一個(gè)允許用戶(hù)運行如電子表格或者字處理軟件等應用程序的特殊程序。本章將介紹程序設計的基本原則 ，同時(shí)給出操作系統設計目標與功能的概述。
2.1 計算機編程語(yǔ)言
2.1.1 匯編語(yǔ)言
那些CPU從主存讀取出來(lái)執行的指令對人類(lèi)來(lái)說(shuō)是根本不可理解的。它們是告訴計算機如何準確動(dòng)作的機器代碼。在Intel 80486指令中16進(jìn)制數0x89E5表示將ESP寄存器的內容拷入EBP寄存器。為最早的計算機設計的工具之一就是匯編器， 它可以將人們可以理解的源文件匯編成機器代碼。匯編語(yǔ)言需要顯式的操作寄存器和數據，并且與特定處理器相關(guān)。比如說(shuō)Intel X86微處理器的匯編語(yǔ)言與Alpha AXP微處理器的匯編語(yǔ)言決然不同。以下是一段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
第一行語(yǔ)句將寄存器15所指示的地址中的值加載到寄存器16中。接下來(lái)將鄰接單元內容加載到寄存器17中。 第三行語(yǔ)句比較寄存器16和寄存器17中的值，如果相等則跳轉到標號100處，否則繼續執行第四行語(yǔ)句：將寄存器17的內容存入 內存中。如果寄存器中值相等則無(wú)須保存。匯編級程序一般冗長(cháng)并且很難編寫(xiě)，同時(shí)還容易出錯。 Linux核心中只有很少一部分是用匯編語(yǔ)言編寫(xiě)，并且這些都是為了提高效率或者是需要兼容不同的CPU。
2.1.2 C編程語(yǔ)言和編譯器
用匯編語(yǔ)言編寫(xiě)程序是一件困難且耗時(shí)的工作。同時(shí)還容易出錯并且程序不可移植：只能在某一特定處理器家族上運行。而用C語(yǔ)言這樣 的與具體機器無(wú)關(guān)的語(yǔ)言就要好得多。C程序語(yǔ)言允許用它所提供的邏輯算法來(lái)描敘程序同時(shí)它提供編譯器工具將C程序轉換成匯編語(yǔ)言 并最終產(chǎn)生機器相關(guān)代碼。好的編譯器能產(chǎn)生和匯編語(yǔ)言程序相接近的效率。Linux內核中大部分用C語(yǔ)言來(lái)編寫(xiě)，以下是一段C語(yǔ) 言片段：
if (x != y)
x = y ;
它所執行的任務(wù)和匯編語(yǔ)言代碼示例中相同。如果變量X的值和變量Y的不相同則將Y的內容賦予X。C代碼被組織成子程序，單獨執行 某一任務(wù)。子程序可以返回由C支持的任何數據類(lèi)型的值。較龐大的程序如Linux 核心由許多單獨的C源代碼模塊組成，每個(gè)模塊有其自身的子程序與數據結構。這些C源代碼模塊將相關(guān)函數組合起來(lái)完成如文件處理等 功能。 C支持許多類(lèi)型的變量，變量是一個(gè)通過(guò)符號名稱(chēng)引用的內存位置。在以上的例子中，X和Y都是內存中的位置。程序員并不關(guān)心變量放 在什么地方，這些工作由連接程序來(lái)完成。有些變量包含不同類(lèi)型的數據，整數和浮點(diǎn)數，以及指針。 指針是那些包含其他數據內存位置或者地址的變量。假設有變量X，位于內存地址0x80010000處。你可以使用指針變量px來(lái) 指向X，則px的值為0x80010000。 C語(yǔ)言允許相關(guān)變量組合起來(lái)形成數據結構，例如：
struct {
int i ;
char b ;
} my_struct ;
這是一個(gè)叫做my_struct的結構，它包含兩個(gè)元素，一個(gè)是32位的整數i,另外一個(gè)是8位的字符b。
2.1.3 連接程序
連接程序是一個(gè)將幾個(gè)目標模塊和庫過(guò)程連接起來(lái)形成單一程序的應用。目標模塊是從匯編器或者編譯器中產(chǎn)生的機器代碼，它包含可執 行代碼和數據，模塊結合在一起形成程序。例如一個(gè)模塊可能包含程序中所有的數據庫函數而另一個(gè)主要處理命令行參數。連接程序修改 目標模塊之間的引用關(guān)系，使得在某一模塊中引用的數據或者子程序的確存在于其他模塊中。Linux核心是由許多目標模塊連接形成 的龐大程序。
2.2 操作系統概念
如果沒(méi)有軟件，計算機只不過(guò)是一堆發(fā)熱的電子器件。如果將硬件比做計算機的心臟則軟件就是它的靈魂。操作系統是一組系統程序的集 合，它提供給用戶(hù)運行應用軟件的功能。操作系統對系統硬件進(jìn)行抽象，它提供給系統用戶(hù)一臺虛擬的機器。大多數PC可以運行一種或 者多種操作系統，每個(gè)操作系統都有不同的外觀(guān)。Linux由許多獨立的功能段組成。比如Linux內核，如果沒(méi)有庫函數和外殼程 序，內核是沒(méi)有什么用的。
為了理解操作系統到底是什么，思考一下當你敲入一個(gè)簡(jiǎn)單命令時(shí)，系統中發(fā)生了什么：
$ ls
Mail c images perl
docs tcl
$
$符號是由用戶(hù)登錄外殼(這里指Bash)提供的提示符。它表示正在等待用戶(hù)敲入一些命令。敲入ls命令，首先鍵盤(pán)驅動(dòng)程序識別 出敲入的內容。然后鍵盤(pán)驅動(dòng)將它們傳遞給外殼程序，由外殼程序來(lái)負責查找同名的可執行程序(ls)。 如果在/bin/ls目錄中找到了ls，則調用核心服務(wù)將ls的可執行映象讀入虛擬內存并開(kāi)始執行。ls調用核心的文件子系統來(lái) 尋找那些文件是可用的。文件系統使用緩沖過(guò)的文件系統信息，或者調用磁盤(pán)設備驅動(dòng)從磁盤(pán)上讀取信息。當然ls還可能引起網(wǎng)絡(luò )驅動(dòng) 程序和遠程機器來(lái)交換信息以找出關(guān)于系統要訪(fǎng)問(wèn)的遠程文件系統信息(文件系統可以通過(guò)網(wǎng)絡(luò )文件系統或者NFS進(jìn)行遠程安裝)。當 得到這些信息后，ls將這些信息通過(guò)調用視頻驅動(dòng)寫(xiě)到顯示器屏幕上。
以上這些聽(tīng)起來(lái)十分復雜。這個(gè)非常簡(jiǎn)單命令的處理過(guò)程告訴我們操作系統是一組協(xié)同工作的函數的集合，它們給所有的用戶(hù)對系統有一 致的印象。
2.2.1 內存管理
由于資源的有限，比如內存，操作系統處理事務(wù)的過(guò)程看起來(lái)十分冗長(cháng)。操作系統的一個(gè)基本功能就是使一個(gè)只有少量物理內存的系統工 作起來(lái)象有多得多的內存一樣。這個(gè)大內存叫為虛擬內存。其思想就是欺騙系統中運行的軟件，讓它們認為有大量?jì)却婵捎?。系統將內存 劃分成易于處理的頁(yè)面，在系統運行時(shí)將這些頁(yè)面交換到硬盤(pán)上去。
由于有另外一個(gè)技巧:多處理的存在，這些軟件更加感覺(jué)不到系統中真實(shí)內存的大小。
2.2.2 進(jìn)程
進(jìn)程可以認為是處于執行狀態(tài)的程序，每個(gè)進(jìn)程有一個(gè)特定的程序實(shí)體。觀(guān)察以下Linux系統中的進(jìn)程，你會(huì )發(fā)現有比你想象的要多 得多的進(jìn)程存在。比如，在我的系統中敲入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
$
如果系統有許多個(gè)CPU，則每個(gè)進(jìn)程可以運行在不同的CPU上。不幸的是，大多數系統中只有一個(gè)CPU。這樣操作系統將輪流運行 幾個(gè)程序以產(chǎn)生它們在同時(shí)運行的假象。這種方式叫時(shí)間片輪轉。同時(shí)這種方法還騙過(guò)了進(jìn)程使它們都認為只有自己在運行。進(jìn)程之間被 隔離開(kāi)，以便某個(gè)進(jìn)程崩潰或者誤操作不會(huì )影響到別的進(jìn)程。操作系統通過(guò)為每個(gè)進(jìn)程提供分立的地址空間來(lái)作到這一點(diǎn)。
2.2.3 設備驅動(dòng)
設備驅動(dòng)組成了Linux核心的主要部分。象操作系統的其他部分一樣，它們運行在高權限環(huán)境中且一旦出錯將引起災難性后果。設備 驅動(dòng)控制操作系統和硬件設備之間的相互操作。例如當文件系統通過(guò)使用通用塊設備接口來(lái)對IDE磁盤(pán)寫(xiě)入數據塊。設備驅動(dòng)負責處理 所有設備相關(guān)細節。設備驅動(dòng)與特定的控制器芯片有關(guān)，如果系統中有一個(gè)NCR810 SCSI控制卡則需要有NCR810 SCSI的驅動(dòng)程序。
2.2.4 文件系統
Linux和Unix一樣，系統中的獨立文件系統不是通過(guò)設備標志符來(lái)訪(fǎng)問(wèn)，而是通過(guò)表示文件系統的層次樹(shù)結構來(lái)訪(fǎng)問(wèn)。當Lin ux添加一個(gè)新的文件系統到系統中時(shí)，會(huì )將它mount到一個(gè)目錄下，比如說(shuō)/mnt/cdrom。
Linux的一個(gè)重要特征就是支持多種文件系統。這使得它非常靈活并且可與其他操作系統并存。Linux中最常用的文件系統是E XT2文件系統，它在大多數Linux分發(fā)版本中都得到了支持。文件系統提供給用戶(hù)一個(gè)關(guān)于系統的硬盤(pán)上文件和目錄的總體映象， 而不管文件的類(lèi)型和底層物理設備的特性。
Linux透明地支持多種文件系統并將當前安裝的所有文件和文件系統集成到虛擬文件系統中去。所以，用戶(hù)和進(jìn)程一般都不知道某個(gè) 文件位于哪種文件系統中，他們只是使用它。
塊設備驅動(dòng)將物理塊設備類(lèi)型（例如IDE和SCSI）和文件系統中的差別隱藏起來(lái)，物理設備只是數據塊的線(xiàn)性存儲集合。設備的不 同導致塊大小的不同，從軟盤(pán)設備的512字節到IDE磁盤(pán)的1024字節。這些都隱藏了起來(lái)，對系統用戶(hù)來(lái)說(shuō)這都是不可見(jiàn)的。不 管設備類(lèi)型如何，EXT2文件系統看起來(lái)總是一樣。
2.3 核心數據結構
操作系統可能包含許多關(guān)于系統當前狀態(tài)的信息。當系統發(fā)生變化時(shí)，這些數據結構必須做相應的改變以反映這些情況。例如，當用戶(hù)登 錄進(jìn)系統時(shí)將產(chǎn)生一個(gè)新的進(jìn)程。核心必須創(chuàng )建表示新進(jìn)程的數據結構，同時(shí)將它和系統中其他進(jìn)程的數據結構連接在一起。
大多數數據結構存在于物理內存中并只能由核心或者其子系統來(lái)訪(fǎng)問(wèn)。數據結構包括數據和指針；還有其他數據結構的地址或者子程序的 地址。它們混在一起讓Linux核心數據結構看上去非?；靵y。盡管可能被幾個(gè)核心子系統同時(shí)用到，每個(gè)數據結構都有其專(zhuān)門(mén)的用途 。理解Linux核心的關(guān)鍵是理解它的數據結構以及Linux核心中操縱這些數據結構的各種函數。本書(shū)把Linux核心的描敘重 點(diǎn)放在數據結構上，主要討論每個(gè)核心子系統的算法，完成任務(wù)的途徑以及對核心數據結構的使用。
2.3.1 連接列表
Linux使用的許多軟件工程的技術(shù)來(lái)連接它的數據結構。在許多場(chǎng)合下，它使用linked或者chained數據結構。每個(gè)數 據結構描敘某一事物，比如某個(gè)進(jìn)程或網(wǎng)絡(luò )設備，核心必須能夠訪(fǎng)問(wèn)到所有這些結構。在鏈表結構中，個(gè)根節點(diǎn)指針包含第一個(gè)結構的地 址，而在每個(gè)結構中又包含表中下一個(gè)結構的指針。表的最后一項必須是0或者NULL，以表明這是表的尾部。在雙向鏈表中，每個(gè)結 構包含著(zhù)指向表中前一結構和后一結構的指針。使用雙向鏈表的好處在于更容易在表的中部添加與刪除節點(diǎn)，但需要更多的內存操作。這 是一種典型的操作系統開(kāi)銷(xiāo)與CPU循環(huán)之間的折中。
2.3.2 散列表
鏈表用來(lái)連接數據結構比較方便，但鏈表的操作效率不高。如果要搜尋某個(gè)特定內容，我們可能不得不遍歷整個(gè)鏈表。Linux使用另 外一種技術(shù):散列表來(lái)提高效率。散列表是指針的數組或向量，指向內存中連續的相鄰數據集合。散列表中每個(gè)指針元素指向一個(gè)獨立鏈 表。如果你使用數據結構來(lái)描敘村子里的人，則你可以使用年齡作為索引。為了找到某個(gè)人的數據，可以在人口散列表中使用年齡作為索 引，找到包含此人特定數據的數據結構。但是在村子里有很多人的年齡相同，這樣散列表指針變成了一個(gè)指向具有相同年齡的人數據鏈表 的指針。搜索這個(gè)小鏈表的速度顯然要比搜索整個(gè)數據鏈表快得多。
由于散列表加快了對數據結構的訪(fǎng)問(wèn)速度，Linux經(jīng)常使用它來(lái)實(shí)現Caches。Caches是保存經(jīng)常訪(fǎng)問(wèn)的信息的子集。經(jīng) 常被核心使用的數據結構將被放入Cache中保存。Caches的缺點(diǎn)是比使用和維護單一鏈表和散列表更復雜。尋找某個(gè)數據結構 時(shí)，如果在Cache中能夠找到（這種情況稱(chēng)為cache 命中），這的確很不錯。但是如果沒(méi)有找到，則必須找出它，并且添加到Cache中去。如果Cache空間已經(jīng)用完則Linux必 須決定哪一個(gè)結構將從其中拋棄，但是有可能這個(gè)要拋棄的數據就是Linux下次要使用的數據。
2.3.3 抽象接口
Linux核心常將其接口抽象出來(lái)。接口指一組以特定方式執行的子程序和數據結構的集合。例如，所有的網(wǎng)絡(luò )設備驅動(dòng)必須提供對某 些特定數據結構進(jìn)行操作的子程序。通用代碼可能會(huì )使用底層的某些代碼。例如網(wǎng)絡(luò )層代碼是通用的，它得到遵循標準接口的特定設備相 關(guān)代碼的支持。
通常在系統啟動(dòng)時(shí)，底層接口向更高層接口注冊(Register)自身。這些注冊操作包括向鏈表中加入結構節點(diǎn)。例如，構造進(jìn)核 心的每個(gè)文件系統在系統啟動(dòng)時(shí)將其自身向核心注冊。文件/proc/filesysems中可以看到已經(jīng)向核心注冊過(guò)的文件系統 。注冊數據結構通常包括指向函數的指針，以文件系統注冊為例，它向Linux核心注冊時(shí)必須將那些mount文件系統連接時(shí)使用 的一些相關(guān)函數的地址傳入。
本站僅提供存儲服務(wù)，所有內容均由用戶(hù)發(fā)布，如發(fā)現有害或侵權內容，請
點(diǎn)擊舉報。
