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