<P ALIGN="JUSTIFY">PID TTY STAT TIME COMMAND</P>
<P ALIGN="JUSTIFY">158 pRe 1 0:00 -bash</P>
<P ALIGN="JUSTIFY">174 pRe 1 0:00 sh /usr/X11R6/bin/startx</P>
<P ALIGN="JUSTIFY">175 pRe 1 0:00 xinit /usr/X11R6/lib/X11/xinit/xinitrc --</P>
<P ALIGN="JUSTIFY">178 pRe 1 N 0:00 bowman</P>
<P ALIGN="JUSTIFY">182 pRe 1 N 0:01 rxvt -geometry 120x35 -fg white -bg black</P>
<P ALIGN="JUSTIFY">184 pRe 1 &lt; 0:00 xclock -bg grey -geometry -1500-1500 -padding 0</P>
<P ALIGN="JUSTIFY">185 pRe 1 &lt; 0:00 xload -bg grey -geometry -0-0 -label xload</P>
<P ALIGN="JUSTIFY">187 pp6 1 9:26 /bin/bash</P>
<P ALIGN="JUSTIFY">202 pRe 1 N 0:00 rxvt -geometry 120x35 -fg white -bg black</P>
<P ALIGN="JUSTIFY">203 ppc 2 0:00 /bin/bash</P>
<P ALIGN="JUSTIFY">1796 pRe 1 N 0:00 rxvt -geometry 120x35 -fg white -bg black</P>
<P ALIGN="JUSTIFY">1797 v06 1 0:00 /bin/bash</P>
<P ALIGN="JUSTIFY">3056 pp6 3 &lt; 0:02 emacs intro/introduction.tex</P>
<P ALIGN="JUSTIFY">3270 pp6 3 0:00 ps</P>
<P ALIGN="JUSTIFY">$</P>
</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">如果我的系統(tǒng)擁有多個(gè)</FONT><FONT SIZE=3>CPU</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>那么每個(gè)進(jìn)程可能（至少在理論上如此）都在不同的</FONT><FONT SIZE=3>CPU</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>上運(yùn)行。不幸的是，只有一個(gè)，所以操作系統(tǒng)又使用技巧，在短時(shí)間內(nèi)依次運(yùn)行每一個(gè)進(jìn)程。這個(gè)時(shí)間段叫做時(shí)間片。這種技巧叫做多進(jìn)程或調(diào)度，它欺騙了每一個(gè)進(jìn)程，好像它們是唯一的進(jìn)程。進(jìn)程相互之間受到保護(hù)，所以如果一個(gè)進(jìn)程崩潰或不能工作，不會(huì)影響其他進(jìn)程。操作系統(tǒng)通過給每一個(gè)進(jìn)程一個(gè)獨(dú)立的地址空間來實(shí)現(xiàn)保護(hù)，進(jìn)程只能訪問它自己的地址空間。</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">2.2.3 Device Drivers</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>（設(shè)備驅(qū)動(dòng)程序）</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">設(shè)備驅(qū)動(dòng)程序組成了</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>核心的主要部分。象操作系統(tǒng)的其他部分一樣，它們?cè)谝粋€(gè)高優(yōu)先級(jí)的環(huán)境下工作，如果發(fā)生錯(cuò)誤，可能會(huì)引發(fā)嚴(yán)重問題。設(shè)備驅(qū)動(dòng)程序控制了操作系統(tǒng)和它控制的硬件設(shè)備之間的交互。比如：文件系統(tǒng)向</FONT><FONT SIZE=3>IDE</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>磁盤寫數(shù)據(jù)塊是使用通用塊設(shè)備接口。驅(qū)動(dòng)程序控制細(xì)節(jié)，并處理和設(shè)備相關(guān)的部分。設(shè)備驅(qū)動(dòng)程序和它驅(qū)動(dòng)的具體的控制器芯片相關(guān)，所以，如果你的系統(tǒng)有一個(gè)</FONT><FONT SIZE=3>NCR810</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>的</FONT><FONT SIZE=3>SCSI</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>控制器，那么你需要</FONT><FONT SIZE=3>NCR810</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>的驅(qū)動(dòng)程序。</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">2.2.4 The Filesystems</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>（文件系統(tǒng)）</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">象</FONT><FONT SIZE=3>Unix</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>一樣，在</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>里，系統(tǒng)對(duì)獨(dú)立的文件系統(tǒng)不是用設(shè)備標(biāo)示符來存?。ū热珧?qū)動(dòng)器編號(hào)或驅(qū)動(dòng)器名稱），而是連接成為一個(gè)樹型結(jié)構(gòu)。</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>在安裝新的文件系統(tǒng)時(shí)，把它安裝到指定的安裝目錄，比如</FONT><FONT SIZE=3>/mnt/cdrom</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>，從而合并到這個(gè)單一的文件系統(tǒng)樹上。</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>的一個(gè)重要特征是它支持多種不同的文件系統(tǒng)。這使它非常靈活而且可以和其他操作系統(tǒng)良好共存。</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>最常用的文件系統(tǒng)是</FONT><FONT SIZE=3>EXT2</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>，大多數(shù)</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>發(fā)布版都支持。</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">文件系統(tǒng)將存放在系統(tǒng)硬盤上的文件和目錄用可以理解的統(tǒng)一的形式提供給用戶，讓用戶不必考慮文件系統(tǒng)的類型或底層物理設(shè)備的特性。</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>透明的支持多種文件系統(tǒng)（如</FONT><FONT SIZE=3>MS-DOS</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>和</FONT><FONT SIZE=3>EXT2</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>），將所有安裝的文件和文件系統(tǒng)集合成為一個(gè)虛擬的文件系統(tǒng)。所以，用戶和進(jìn)程通常不需要確切知道所使用的文件所在的文件系統(tǒng)的類型，用就是了。</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">塊設(shè)備驅(qū)動(dòng)程序掩蓋了物理塊設(shè)備類型的區(qū)別（如</FONT><FONT SIZE=3>IDE</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>和</FONT><FONT SIZE=3>SCSI</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>）。對(duì)于文件系統(tǒng)來講，物理設(shè)備就是線性的數(shù)據(jù)塊的集合。不同設(shè)備的塊大小可能不同，如軟驅(qū)一般是</FONT><FONT SIZE=3>512</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>字節(jié)，而</FONT><FONT SIZE=3>IDE</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>設(shè)備通常是</FONT><FONT SIZE=3>1024</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>字節(jié)，同樣，對(duì)于系統(tǒng)的用戶，這些區(qū)別又被掩蓋。</FONT><FONT SIZE=3>EXT2</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>文件系統(tǒng)不管它用什么設(shè)備，看起來都是一樣的。</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">2.3 Kernet Data Structures</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>（核心數(shù)據(jù)結(jié)構(gòu)）</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">操作系統(tǒng)必須紀(jì)錄關(guān)于系統(tǒng)當(dāng)前狀態(tài)的許多信息。如果系統(tǒng)中發(fā)生了事情，這些數(shù)據(jù)結(jié)構(gòu)就必須相應(yīng)改變以反映當(dāng)前的實(shí)際情況。例如：用戶登錄到系統(tǒng)中的時(shí)候，需要?jiǎng)?chuàng)建一個(gè)新的進(jìn)程。核心必須相應(yīng)地創(chuàng)建表示此新進(jìn)程的數(shù)據(jù)結(jié)構(gòu)，并和表示系統(tǒng)中其他進(jìn)程的數(shù)據(jù)結(jié)構(gòu)聯(lián)系在一起。</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">這樣的數(shù)據(jù)結(jié)構(gòu)多數(shù)在物理內(nèi)存中，而且只能由核心和它的子系統(tǒng)訪問。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)和指針（其他數(shù)據(jù)結(jié)構(gòu)或例程的地址）。乍一看，</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>核心所用的數(shù)據(jù)結(jié)構(gòu)可能非?；靵y。其實(shí)，每一個(gè)數(shù)據(jù)結(jié)構(gòu)都有其目的，雖然有些數(shù)據(jù)結(jié)構(gòu)在多個(gè)的子系統(tǒng)中都會(huì)用到，但是實(shí)際上它們比第一次看到時(shí)的感覺要簡(jiǎn)單的多。</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">理解</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>核心的關(guān)鍵在于理解它的數(shù)據(jù)結(jié)構(gòu)和核心處理這些數(shù)據(jù)結(jié)構(gòu)所用到的大量的函數(shù)。本書以數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)描述</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>核心。論及每一個(gè)核心子系統(tǒng)的算法，處理的方式和它們對(duì)核心數(shù)據(jù)結(jié)構(gòu)的使用。</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">2.3.1 Linked Lists</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>（連接表）</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>使用一種軟件工程技術(shù)將它的數(shù)據(jù)結(jié)構(gòu)連接在一起。多數(shù)情況下它使用鏈表數(shù)據(jù)結(jié)構(gòu)。如果每一個(gè)數(shù)據(jù)結(jié)構(gòu)描述一個(gè)物體或者發(fā)生的事件的單一的實(shí)例，比如一個(gè)進(jìn)程或一個(gè)網(wǎng)絡(luò)設(shè)備，核心必須能夠找出所有的實(shí)例。在鏈表中，根指針包括第一個(gè)數(shù)據(jù)結(jié)構(gòu)或單元的地址，列表中的每一個(gè)數(shù)據(jù)結(jié)構(gòu)包含指向列表下一個(gè)元素的指針。最后元素的下一個(gè)指針可能使</FONT><FONT SIZE=3>0</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>或</FONT><FONT SIZE=3>NULL</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>，表示這是列表的結(jié)尾。在雙向鏈表結(jié)構(gòu)中，每一個(gè)元素不僅包括列表中下一個(gè)元素的指針，還包括列表中前一個(gè)元素的指針。使用雙向鏈表可以比較容易的在列表中間增加或刪除元素，但是這需要更多的內(nèi)存存取。這是典型的操作系統(tǒng)的兩難情況：內(nèi)存存取數(shù)還是</FONT><FONT SIZE=3>CPU</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>的周期數(shù)。</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">2.3.2 Hash Tables</P>
</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">鏈接表是常用的數(shù)據(jù)結(jié)構(gòu)，但是游歷鏈接表的效率可能并不高。如果你要尋找指定的元素，</FONT><FONT SIZE=3> </FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>可能必須查找完整個(gè)表才能找到。</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>使用另一種技術(shù)：</FONT><FONT SIZE=3>Hashing  </FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>來解決這種局限。</FONT><FONT SIZE=3>Hash table</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>是指針的數(shù)組或者說向量表。數(shù)組或向量表是在內(nèi)存中依次存放的對(duì)象。書架可以說是書的數(shù)組。數(shù)組用索引來訪問，索引是數(shù)組中的偏移量。再來看書架的例子，你可以使用在書架上的位置來描述每一本書：比如第</FONT><FONT SIZE=3>5</FONT><FONT FACE="宋體" LANG="ZH-CN" SIZE=3>本書。</P>