夢想的天空

tpcat · DS - 中級顧問 註冊時間: 2003-03-11 文章: 7308 來自: 貓窩

Linux Kernel核心中文手冊
Chapter 1
　
Hardware Basic(硬體基礎知識)
　
一個作業系統必須和作為它的基礎的硬體系統緊密配合。作業系統需要使用一些只有硬體才能提供的功能。為了完整的瞭解Linux，你需要瞭解底層硬體的基礎知識。本章對於現代PC的硬體進行了。
1975年1月“Popular Electronics”雜誌封面上印出了Altair 8080的圖片，一場革命開始了。
Altair 8080，跟隨早期的“Star Trek epsode”命名，只需要$397，就可由個人電子愛好者自己組裝。它擁有Intel 8080處理器和256位元組記憶體，但是沒有螢幕和鍵盤。以今天的標準來衡量，它太簡陋了。它的發明者，Ed Roberts，製造了名詞“personal computer“來命名他的發明，但現在，PC這個名詞已經用來命名幾乎所有你可以不依靠幫助就可以自己運行起來的電腦。用這個定義，甚至一些十分強大的Alpha AXP系統也是PC。
愛好者們看到了Altair的潛力，開始為它寫軟體，製造硬體。對於這些早期的先驅來講，它代表著自由：從被神職人員控制和運行的大型批次處理的主機系統中逃脫出來的自由。你可以在自己家裏甚至廚桌上擁有電腦，這使學院的退學生為此著迷並通宵達旦。與此同時出現大量硬體，在一定程度上各自不同，而軟體專家則樂於為這些新機器撰寫軟體。有諷刺意味的是，IBM在1981年發佈了IBM PC並於1982年早期供貨，從此定義了現代PC的模型。它擁有Intel 8088處理器，64K記憶體（可以擴充到256K），兩個軟盤機和一個80x25的彩色圖卡(CGA)，用今天的標準衡量，它功能不算很強，但是它銷售的不錯。1983年，緊接著推出的IBM PC-XT，則擁有一個豪華的10M硬碟。不久大批公司如Compaq開始製造IBM PC的複製品，PC的結構成為了事實的標準。這個事實的標準使大批硬體公司可以在這個不斷增長的市場上一起競爭，反過來，可以遏制價格，讓用戶滿意。現代PC承襲了早期PC的許多系統體系特徵。甚至基於最強大的Intel Pentium Pro的系統也可以運行Intel 8086的定址模式。當Linus Torvalds開始開發後來的Linux時，他選擇了當時最常見和價格最合理的硬體平臺：一台Intel 80386 PC。
從PC的外面看，最明顯的部件就是機箱、鍵盤、滑鼠和顯示器。在機箱的前面有一些按鈕，一個小螢幕顯示一些數位，還有一個軟盤機。現在的大多數系統還有一個CD-ROM期、驅動器。如果你需要保護你的資料，那麼還會有一個備份用的磁帶機。這些設備一律被看作外設。
雖然CPU管理整個系統，但它並不是唯一的智慧設備。所有的外設控制器，例如IDE控制器，也都擁有一定程度的智慧。在PC內部（圖1.1），你可以看到一個主板，包括CPU或微處理器、記憶體和一些ISA或PCI外設控制卡的槽位。其中一些控制器，如IDE磁片控制器可能內置在系統主板上。
　
1. CPU
　
CPU，或者說微處理器，是所有電腦系統的心臟。微處理器進行數學運算，邏輯操作並從記憶體中讀取指令並執行指令，進而控制資料流程向。電腦發展的早期，微處理器的各種功能模組是由相互分離（並且尺寸上十分巨大）的單元構成。這也是名詞“中央處理單元”的起源。現代的微處理器將這些功能模組集中在一塊非常小的矽晶片製造的積體電路上。在本書，名詞CPU、微處理器和處理器交替使用。
微處理器處理二進位資料：這些資料由1和0組成。這些1和0對應電氣開關的開或關。就好像42代表4個10和2個單元，二進位數字字由一系列代表2的冪數的數字組成。這裏，冪數意味著一個數字用自身相乘的次數。10 的一次冪是10，10的2次冪是10x10，10的3次冪是10x10x10，依此類推。二進位0001是十進位1是十進位2，二進位0011是十進位3，二進位0100是十進位4，等等。所以，十進位42是二進位101010或者（2+8+32或21+23+25）。在電腦程式除了使用二進位表示數位之外，另一種基數，16進制，也經常用到。在這種進制中，每一位元數字表示16的冪數。因為十進位數字字只是從0到9，在十六進位中10到15分別用字母A，B，C，D，E，F表示。例如，十六進位的E是十進位的14，而十六進位的2A是十進位的42（2個16+10）。用C語言的表示法（本書一直使用），十六進位數位使用首碼“0x”：十六進位的2A寫做0x2A。
　

微處理器可以執行算術運算如加、乘和除，也可以執行邏輯操作例如“X是否大於Y”。
處理器的執行由外部時鐘控制。這個時鐘，即系統時鐘，對處理器產生穩定的時鐘脈衝，在每一個時鐘脈衝裏，處理器執行一些工作。例如，處理器可以在每一個時鐘脈衝裏執行一條指令。處理器的速度用系統時鐘的頻率來描述。一個100Mhz的處理器每秒鐘接受到100，000，000次時鐘脈衝。用時鐘頻率來描述CPU的能力是一種誤解，因為不同的處理器在每一次時鐘脈衝中執行的工作量不同。雖然如此，如果所有的條件同等，越快的時鐘頻率表示處理器的能力越強。處理器執行的指令非常簡單，例如：“把記憶體位置X的內容讀到寄存器Y中“。寄存器是微處理器的內部存儲空間，用來存儲資料並進行操作。執行的操作可能使處理器停止當前操作而轉去執行記憶體中其他地方的指令。正是這些微小的指令集合在一起，賦予現代的微處理器幾乎無限的能力，因為它每秒可以執行數百萬甚至數十億的指令。
　
執行指令時必須從記憶體中提取指令，指令自身也可能引用記憶體中的資料，這些資料也必須提取到記憶體中並在需要的時候保存到記憶體中去。
　
一個微處理器內部寄存器的大小、數量和類型完全決定於它的類型。一個Intel 80486處理器和一個Alpha AXP處理器的寄存器組完全不同。另外，Intel是32位寬而Alpha AXP是64位寬。但是，一般來講，所有特定的處理器都會有一些通用目的的寄存器和少量專用的寄存器。大多數處理器擁有以下特殊用途的專用的寄存器：
　
Program Counter（PC）程式計數器
這個寄存器記錄了下一條要執行的指令的位址。PC的內容在每次取指令的時候自動增加。
Stack Pointer（SP）堆疊指標
處理器必須能夠存取用於臨時存儲資料的大容量的外部讀寫隨機存取記憶體（RAM）。堆疊是一種用於在外部記憶體中存放和恢復臨時資料的方法。通常，處理器提供了特殊的指令用於將資料壓在堆疊中，並在以後需要是取出來。堆疊使用LIFO（後進先出）的方式。換句話說，如果你壓入兩個值x和y到堆疊中，然後從堆疊中彈出一個值，那麼你會得到y的值。
一些處理器的堆疊向記憶體頂部增長，而另一些向記憶體的底部增長。還有一些處理器兩種方式都可以支援，例如：ARM。
　
Processor Status（PS）
指令可能產生結果。例如：“X寄存器的內容是否大於Y寄存器的內容？“可能產生真或假的結果。PS寄存器保留這些結果以及處理器當前狀態的其他資訊。多數處理器至少有兩種模式：kernel（核心態）和user（用戶態），PS寄存器會紀錄能夠確定當前模式的那些資訊。
　
2. Memory(記憶體)
　
所有系統都具有分級的記憶體結構，由位於不同級別的速度和容量不同的記憶體組成。
最快的記憶體是快取記憶體記憶體，就象它的名字暗示的一樣-用於臨時存放或緩存主記憶體的內容。這種記憶體非常快但是比較昂貴，因此多數處理器晶片上內置有少量的高速緩衝記憶體，而大多數快取記憶體記憶體放在系統主板上。一些處理器用一塊緩存記憶體同時緩存指令和資料，而另一些處理器有兩塊緩存記憶體-一個用於指令，另一個用於資料。Alpha AXP處理器有兩個內置的記憶體快取記憶體記憶體：一個用於資料（D-Cache），另一個用於指令（I-Cache）。它的外部高速緩衝記憶體（或B-Cache）將兩者混在一起。
最後一種記憶體是主記憶體。相對於外部快取記憶體記憶體而言速度非常慢，對於CPU內置的快取記憶體記憶體，主記憶體簡直是在爬。
快取記憶體記憶體和主記憶體必須保持同步（一致）。換句話說，如果主記憶體中的一個字保存在快取記憶體記憶體的一個或多個位置，那麼系統必須保證快取記憶體記憶體和主記憶體的內容一樣。使高速緩衝記憶體同步的工作一部分是由硬體完成，另一部分則是由作業系統完成的。對於其他一些系統的主要任務，硬體和軟體也必須緊密配合。
　
3. Buses（匯流排）
系統板的各個組成部分由被稱為匯流排的連接系統互連在一起。系統匯流排分為三種邏輯功能：位址匯流排、資料匯流排和控制匯流排。位址匯流排指定了資料傳輸的記憶體位置（位址），資料匯流排保存了傳輸的資料。資料匯流排是雙向的，它允許CPU讀取，也允許CPU寫。控制匯流排包含了各種信號線用於在系統中發送時鐘和控制信號。有許多種不同的匯流排類型，ISA和PCI匯流排是系統用於連接外設的常用方式。
　
4. Controllers and Peripherals （控制器和外設）
　
外設指實在的設備，如由系統板或系統板插卡上的控制晶片所控制的圖形卡或磁片。IDE控制晶片控制IDE磁片，而SCSI控制晶片控制SCSI磁片。這些控制器通過不同的匯流排連接到CPU並相互連接。現在製造的大多數系統都是用PCI或ISA匯流排將系統的主要部件連接在一起。控制器本身也是象CPU一樣的處理器，它們可以看作CPU的智慧助手，CPU擁有系統的最高控制權。
　
所有的控制器都是不同的，但是通常它們都有用於控制它們的寄存器。CPU上運行的軟體必須能夠讀寫這些控制寄存器。一個寄存器可能包含描述錯誤的狀態碼，另一個寄存器可能用於控制用途，改變控制器的模式。一個匯流排上的每一個控制器都可以分別被CPU定址，這樣軟體設備驅動程式就可以讀寫它的寄存器進而控制它。IDE電纜是一個好例子，它給了你分別存取匯流排上每一個驅動器的能力。另一個好例子是PCI匯流排，允許每一個設備（如圖形卡）被獨立存取。
　
5. Address Spaces（定址空間）
　
連接CPU和主記憶體的系統匯流排以及連接CPU和系統硬體外設的匯流排是分離的。硬體外設所擁有的記憶體空間稱為I/O空間。I/O空間本身可以再進一步劃分，但是我們現在先不討論。CPU可以訪問系統記憶體空間和I/O空間，而控制器只能通過CPU間接訪問系統記憶體。從設備的角度來看，比如軟盤機控制器，它只能看到它的控制寄存器所在的位址空間（ISA），而非系統記憶體。一個CPU用不同的指令去訪問記憶體和I/O空間。例如，可能有一條指令是“從I/O位址0x3f0讀取一個位元組到X寄存器“。這也是CPU通過讀寫系統硬體外設處於I/O位址空間的寄存器從而控制外設的方法。在位址空間中，普通外設（如IDE控制器，序列埠，軟盤機控制器等等）的寄存器在PC外設的多年發展中已經成了定例。I/O空間的位址0x3f0正是串列口（COM1）的控制寄存器的位址。
　
有時控制器需要直接從系統記憶體讀取大量記憶體，或直接寫大量資料到系統記憶體中去。比如將用戶資料寫到硬碟上去。在這種情況下，使用直接記憶體存取（DMA）控制器，允許硬體設備直接存取系統記憶體，當然，這種存取必須在CPU的嚴格控制和監管下進行。
　
6. Timer(時鐘)
所有作業系統需要知道時間，現代PC包括一個特殊的外設，叫做即時時鐘（RTC）。它提供了兩樣東西：可靠的日期和精確的時間間隔。RTC有自己的電池，所以即使PC沒有加電，它仍在運行。這也是為什麼PC總是“知道”正確的日期和時間。時間間隔計時允許作業系統精確地調度基本工作。
　
　
Chapter 2
　
Software Basic(軟體基礎)
程式是用於執行特定任務的電腦指令組合。程式可以用組合語言，一種非常低級的電腦語言來編寫，也可以使用和機器無關的高階語言，比如C語言編寫。作業系統是一個特殊的程式，允許用戶通過它運行應用程式，比如電子錶和文字處理等等。本章介紹了基本的編程原理，並簡介作業系統的目的和功能。
　
2.1 Computer Languages(電腦語言)
　
2.1.1.組合語言
　
CPU從記憶體中讀取和執行的指令對於人類來講無法理解。它們是機器代碼，精確的告訴電腦要做什麼。比如十六進位數0x89E5，是Intel 80486的指令，將寄存器ESPEBP中。早期電腦中最初的軟體工具之一是組合語言程式，它讀入人類可以閱讀的原始檔案，將其裝配成機器代碼。組合語言明確地處理對寄存器和對資料的操作，而這種操作對於特定的微處理器而言是特殊的。Intel X86微處理器的組合語言和Alpha AXP微處理器的組合語言完全不同。以下Alpha AXP彙編代碼演示了程式可以執行的操作類型：
　
Ldr r16, (r15) ; 第一行
Ldr r17, 4(r15) ; 第二行
Beq r16,r17,100; 第三行
Str r17, (r15); 第四行
100: ; 第五行
　
第一條語句（第一行）將寄存器15指定的位址中的內容載入到寄存器16中。第二條指令將緊接著的記憶體中的內容載入到寄存器17中。第三行比較寄存器16和寄存器17，如果相等，分支到標號100，否則，繼續執行第四行，將寄存器17的內容存到記憶體中。如果記憶體中的資料相同，就不必存儲資料。編寫彙編級的程式需要技巧而且十分冗長，容易出錯。Linux系統的核心很少的一部分是用組合語言編寫，而這些部分之所以使用組合語言只是為了提高效率，並且和具體的微處理器相關。
　
2.1.2 The C Programming Language and Compiler (C語言和編譯器)
　
使用組合語言編寫大型程式十分困難，消耗時間，容易出錯而且生成的程式不能移植，只能束縛在特定的處理器家族。更好的選擇是使用和機器無關的語言，例如C。C允許你用邏輯演算法描述程式和要處理的資料。被稱為編譯程序（compiler）的特殊程式讀入C程式，並將它轉換為組合語言，進而產生機器相關的代碼。好的編譯器生成的彙編指令可以和好的組合語言程式員編寫的程式效率接近。大部分Linux核心是用C語言編寫的。以下的C片斷：
if (x != y)
x = y;
執行了和前面示例中彙編代碼完全一樣的操作。如果變數x的內容和變數y的內容不一樣，變數y的內容被拷貝到變數x。C代碼用常式（routine）進行組合，每一個常式執行一項任務。常式可以返回C所支援的任意的數值或資料類型。大型程式比如Linux核心分別由許多的C語言模組組成，每一個模組有自己的常式和資料結構。這些C源代碼模組共同構成了邏輯功能比如檔系統的處理代碼。
　
C支援多種類型的變數。一個變數是記憶體中的特定位置，可用符號名引用。上述的C片斷中，x和y引用了記憶體中的位置。程式師不需要關心變數在記憶體中的具體位置，這是連接程式（下述）必須處理的。一些變數包含不同的資料例如整數、浮點數等和另一些則包含指針。
　
指標是包含其他資料在記憶體中的位址的變數。假設一個變數x，位於記憶體位址0x80010000，你可能有一個指標px，指向x。 Px可能位於位址0x80010030。Px的值則是變數x的位址，0x80010000。
　
C允許你將相關的變數集合成為結構。例如：
Struct {
Int I;
Char b;
} my_struct;
是一個叫做my_struct的資料結構，包括兩個元素：一個整數（32位元）I和一個字元（8位元資料）b。
　
2.1.3 Linkers（連接程式）
　
連接程式將幾個目的模組和庫檔連接在一起成為一個單獨的完整程式。目的模組是組合語言程式或編譯程序的機器碼輸出，它包括機器碼、資料和供連接程式使用的連接資訊。比如：一個目的模組可能包括程式的所有資料庫功能，而另一個目的模組則包括處理命令行參數的函數。連接程式確定目的模組之間的引用關係，即確定一個模組所引用的常式和資料在另一個模組中的實際位置。Linux核心是由多個目的模組連接而成的獨立的大程式。
　
2.2 What is an Operating System（什麼是作業系統？）
　
沒有軟體，電腦只是一堆發熱的電子元件。如果說硬體是電腦的心臟，則軟體就是它的靈魂。作業系統是允許用戶運行應用程式的一組系統程式。作業系統將系統的硬體抽象，呈現在用戶和應用程式之前的是一個虛擬的機器。是軟體造就了電腦系統的特點。大多數PC可以運行一到多個作業系統，而每一個作業系統從外觀和感覺上都大不相同。Linux由不同功能的部分構成，這些部分總體組合構成了Linux作業系統。Linux最明顯的部分就是Kernel自身，但是如果沒有shell或libraries一樣沒有用處。
　
為了瞭解什麼是作業系統，看一看在你輸入最簡單的命令時發生了什麼：
　
$ls
Mail c images perl
Docs tcl
$
這裏的$是登錄的shell輸出的提示符（此例是bash）：表示shell在等候你（用戶）輸入命令。輸入ls引發鍵盤驅動程式識別輸入的字元，鍵盤驅動程式將識別的字元傳遞給shell去處理。shell先查找同名的可執行映象，它找到了/bin/ls, 然後調用核心服務將ls執行程式載入到虛擬記憶體中並開始執行。ls執行程式通過執行核心的檔子系統的系統調用查找檔。檔系統可能使用緩存的檔系統資訊或通過磁片設備驅動程式從磁片上讀取檔資訊,也可能是通過網路設備驅動程式同遠端主機交換資訊而讀取本系統所訪問的遠端檔的詳細資訊（檔系統可以通過NFS網路檔系統遠端安裝）。不管檔資訊是如何得到的，ls都將資訊輸出，通過顯示驅動程式顯示在螢幕上。
　
以上的過程看起來相當複雜，但是它說明了即使是最簡單的命令也是作業系統各個功能模組之間共同協作的結果，只有這樣才能提供給你（用戶）一個完整的系統視圖。
　
2.2.1 Memory management（記憶體管理）
　
如果擁有無限的資源，例如記憶體，那麼作業系統所必須做的很多事情可能都是多餘的。所有作業系統的一個基本技巧就是讓少量的實體記憶體工作起來好像有相當多的記憶體。這種表面看起來的大記憶體叫做虛擬記憶體，就是當軟體運行的時候讓它相信它擁有很多記憶體。系統將記憶體分為容易處理的頁，在系統運行時將這些頁交換到硬碟上。而應用軟體並不知道，因為作業系統還使用了另一項技術：多進程。
　
2.2.2 Processes (進程)
　
進程可以看作一個在執行的程式，每一個進程都是正在運行的特定的程式的獨立實體。如果你觀察一下你的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上運行。不幸的是，只有一個，所以作業系統又使用技巧，在短時間內依次運行每一個進程。這個時間段叫做時間片。這種技巧叫做多進程或調度，它欺騙了每一個進程，好像它們是唯一的進程。進程相互之間受到保護，所以如果一個進程崩潰或不能工作，不會影響其他進程。作業系統通過給每一個進程一個獨立的位址空間來實現保護，進程只能訪問它自己的位址空間。
　
2.2.3 Device Drivers（設備驅動程式）
　
設備驅動程式組成了Linux核心的主要部分。象作業系統的其他部分一樣，它們在一個高優先順序的環境下工作，如果發生錯誤，可能會引發嚴重問題。設備驅動程式控制了作業系統和它控制的硬體設備之間的交互。比如：檔系統向IDE磁片寫資料塊是使用通用塊設備介面。驅動程式控制細節，並處理和設備相關的部分。設備驅動程式和它驅動的具體的控制器晶片相關，所以，如果你的系統有一個NCR810的SCSI控制器，那麼你需要NCR810的驅動程式。
　
2.2.4 The Filesystems（檔系統）
　
象Unix一樣，在Linux裏，系統對獨立的檔系統不是用設備標示符來存取（比如驅動器編號或驅動器名稱），而是連接成為一個樹型結構。Linux在安裝新的檔系統時，把它安裝到指定的安裝目錄，比如/mnt/cdrom，從而合併到這個單一的檔系統樹上。Linux的一個重要特徵是它支援多種不同的檔系統。這使它非常靈活而且可以和其他作業系統良好共存。Linux最常用的檔系統是EXT2，大多數Linux發佈版都支援。
　
檔系統將存放在系統硬碟上的檔和目錄用可以理解的統一的形式提供給用戶，讓用戶不必考慮檔系統的類型或底層物理設備的特性。Linux透明的支援多種檔系統（如MS-DOS和EXT2），將所有安裝的檔和檔系統集合成為一個虛擬的檔系統。所以，用戶和進程通常不需要確切知道所使用的檔所在的檔系統的類型，用就是了。
　
塊設備驅動程式掩蓋了物理塊設備類型的區別（如IDE和SCSI）。對於檔系統來講，物理設備就是線性的資料塊的集合。不同設備的塊大小可能不同，如軟盤機一般是512位元組，而IDE設備通常是1024位元組，同樣，對於系統的用戶，這些區別又被掩蓋。EXT2檔系統不管它用什麼設備，看起來都是一樣的。
　
2.3 Kernet Data Structures（核心資料結構）
　
作業系統必須紀錄關於系統當前狀態的許多資訊。如果系統中發生了事情，這些資料結構就必須相應改變以反映當前的實際情況。例如：用戶登錄到系統中的時候，需要創建一個新的進程。核心必須相應地創建表示此新進程的資料結構，並和表示系統中其他進程的資料結構聯繫在一起。
　
這樣的資料結構多數在實體記憶體中，而且只能由核心和它的子系統訪問。資料結構包括資料和指標（其他資料結構或常式的位址）。乍一看，Linux核心所用的資料結構可能非常混亂。其實，每一個資料結構都有其目的，雖然有些資料結構在多個的子系統中都會用到，但是實際上它們比第一次看到時的感覺要簡單的多。
　
理解Linux核心的關鍵在於理解它的資料結構和核心處理這些資料結構所用到的大量的函數。本書以資料結構為基礎描述Linux核心。論及每一個核心子系統的演算法，處理的方式和它們對核心資料結構的使用。
　
2.3.1 Linked Lists（連接表）
　
Linux使用一種軟體工程技術將它的資料結構連接在一起。多數情況下它使用鏈表資料結構。如果每一個資料結構描述一個物體或者發生的事件的單一的實例，比如一個進程或一個網路設備，核心必須能夠找出所有的實例。在鏈表中，根指標包括第一個資料結構或單元的位址，列表中的每一個資料結構包含指向列表下一個元素的指標。最後元素的下一個指標可能使0或NULL，表示這是列表的結尾。在雙向鏈表結構中，每一個元素不僅包括列表中下一個元素的指標，還包括列表中前一個元素的指標。使用雙向鏈表可以比較容易的在列表中間增加或刪除元素，但是這需要更多的記憶體存取。這是典型的作業系統的兩難情況：記憶體存取數還是CPU的週期數。
　
2.3.2 Hash Tables
　
鏈結表是常用的資料結構，但是遊歷鏈結表的效率可能並不高。如果你要尋找指定的元素，可能必須查找完整個表才能找到。Linux使用另一種技術：Hashing 來解決這種局限。Hash table是指標的陣列或者說向量表。陣列或向量表是在記憶體中依次存放的物件。書架可以說是書的陣列。陣列用索引來訪問，索引是陣列中的偏移量。再來看書架的例子，你可以使用在書架上的位置來描述每一本書：比如第5本書。
　
Hash table是一個指向資料結構的指標的陣列，它的索引來源於資料結構中的資訊。如果你用一個資料結構來描述一個村莊的人口，你可以用年齡作為索引。要找出一個指定的人的資料，你可以用他的年齡作為索引在人口散列表中查找，通過指標找到包括詳細資訊的資料結構。不幸的是，一個村莊中可能很多人年齡相同，所以散列表的指標指向另一個鏈表資料結構，每一個元素描述同齡人。即使這樣，查找這些較小的鏈表仍然比查找所有的資料結構要快。
　
Hash table可用於加速常用的資料結構的訪問，在Linux裏常用hash table來實現緩衝。緩衝是需要快速存取的資訊，是全部可用資訊的一個子集。資料結構被放在緩衝區並保留在那裏，因為核心經常訪問這些結構。使用緩衝區也有副作用，因為使用起來比簡單鏈表或者散列表更加複雜。如果資料結構可以在緩衝區找到（這叫做緩衝命中），那麼一切很完美。但是如果資料結構不在緩衝區中，那麼必須查找所用的相關的資料結構，如果找到，那麼就加到緩衝區中。增加新的資料結構到緩衝區中可能需要廢棄一個舊的緩衝入口。Linux必須決定廢棄那一個資料結構，風險在於廢棄的可能使Linux下一個要訪問的資料結構。
　
2.3.3 Abstract Interfaces（抽象介面）
　
Linux核心經常將它的介面抽象化。介面是以特定方式工作的一系列常式和資料結構。比如：所有的網路設備驅動程式都必須提供特定的常式來處理特定的資料結構。用抽象介面的方式可以用通用的代碼層來使用底層特殊代碼提供的服務（介面）。例如網路層是通用的，而它由底層符合標準介面的同設備相關的代碼提供支援。
通常這些底層在啟動時向高一層登記。這個登記過程常通過在鏈結表中增加一個資料結構來實現。例如，每一個連結到核心的檔系統在核心啟動時進行登記（或者如果你使用模組，在檔系統第一次使用時向核心登記）。你可以查看檔/proc/filesystems來檢查那些檔系統進行了登記。登記所用的資料結構通常包括指向函數的指標。這是執行特定任務的軟體函數的位址。再一次用檔系統登記的例子，每一個檔系統登記時傳遞給Linux核心的資料結構都包括一個和具體檔系統相關的常式位址，在安裝檔系統時必須調用。
　
　
Chapter 3
Memory Management （記憶體管理）
　
記憶體管理子系統是作業系統的重要部分。從電腦發展早期開始，就存在對於大於系統中物理能力的記憶體需要。為了克服這種限制，開發了許多種策略，其中最成功的就是虛擬記憶體。虛擬記憶體通過在競爭進程之間共用記憶體的方式使系統顯得擁有比實際更多的記憶體。
虛擬記憶體不僅僅讓你的電腦記憶體顯得更多，記憶體管理子系統還提供：
　
Large Address Spaces（巨大的位址空間）作業系統使系統顯得擁有比實際更大量的記憶體。虛擬記憶體可以比系統中的實體記憶體大許多倍。
Protection（保護）系統中的每一個進程都有自己的虛擬位址空間。這些虛擬的位址空間是相互完全分離的，所以運行一個應用程式的進程不會影響另外的進程。另外，硬體的虛擬記憶體機制允許對記憶體區防寫。這可以防止代碼和資料被惡意的程式覆蓋。
Memory Mapping（記憶體映射）記憶體映射用來將映射和資料映射到進程的位址空間。用記憶體映射，檔的內容被直接連結到進程的虛擬位址空間。
Fair Physics Memory Allocation（公平分配實體記憶體）記憶體管理子系統允許系統中每一個運行中的進程公平地共用系統的實體記憶體
Shared Virtual Memory（共用虛擬記憶體）雖然虛擬記憶體允許進程擁有分離（虛擬）的位址空間，有時你也需要進程之間共用記憶體。例如，系統中可能有多個進程運行命令解釋程式bash。雖然可以在每一個進程的虛擬位址空間都擁有一份bash的拷貝，更好的是在實體記憶體中只擁有一份拷貝，所有運行bash的進程共用代碼。動態連接庫是多個進程共用執行代碼的另一個常見例子。共用記憶體也可以用於進程間通訊(IPC)機制，兩個或多個進程可以通過共同擁有的記憶體交換資訊。Linux系統支援系統V的共用記憶體IPC機制。
　
3.1 An Abstract Model of Virtual Memory（虛擬記憶體的抽象模型）
　
在考慮Linux支持虛擬記憶體的方法之前，最好先考慮一個抽象的模型，以免被太多的細節搞亂。
　
在進程執行程式的時候，它從記憶體中讀取指令並進行解碼。解碼指令也許需要讀取或者存儲記憶體特定位置的內容，然後進程執行指令並轉移到程式中的下一條指令。進程不管是讀取指令還是存取資料都要訪問記憶體。
　
在一個虛擬記憶體系統中，所有的位址都是虛擬位址而非物理位址。處理器通過作業系統保存的一組資訊將虛擬位址轉換為物理位址。
　
為了讓這種轉換更簡單，將虛擬記憶體和實體記憶體分為適當大小的塊，叫做頁（page）。頁的大小一樣。（當然可以不一樣，但是這樣一來系統管理起來比較困難）。Linux在Alpha AXP系統上使用8K位元組的頁，而在Intel x86系統上使用4K位元組的頁。每一頁都賦予一個唯一編號：page frame number(PFN 頁編號)。在這種分頁模型下，虛擬位址由兩部分組成：虛擬頁號和頁內偏移量。假如頁大小是4K，則虛擬位址的位元11到0包括頁內偏移量，位12和以上的位是頁編號。每一次處理器遇到虛擬位址，它必須提取出偏移和虛擬頁編號。處理器必須將虛擬頁編號轉換到物理的頁，並訪問物理頁的正確偏移處。為此，處理器使用了頁表（page tables）。
圖3.1顯示了兩個進程的虛擬位址空間，進程X和進程Y，每一個進程擁有自己的頁表。這些頁表將每一個進程的虛擬頁映射到記憶體的物理頁上。圖中顯示進程X的虛擬頁號0映射到物理頁號1，而進程Y的虛擬頁編號1映射到物理頁號4。理論上頁表每一個條目包括以下資訊：
　
有效標誌表示頁表本條目是否有效
本頁表條目描述的物理頁編號
訪問控制資訊描述本頁如何使用：是否可以寫？是否包括執行代碼？
　
頁表通過虛擬頁標號作為偏移來訪問。虛擬頁編號5是表中的第6個元素（0是第一個元素）
要將虛擬位址轉換到物理位址，處理器首先找出虛擬位址的頁編號和頁內偏移量。使用2的冪次的頁尺寸，可以用遮罩或移位簡單地處理。再一次看圖3.1，假設頁大小是0x2000（十進位8192），進程Y的虛擬位址空間的位址是0x2194，處理器將會把位址轉換為虛擬頁編號1內的偏移量0x194。
　

　
處理器使用虛擬頁編號作為索引在進程的頁表中找到它的頁表的條目。如果該條目有效，處理器從該條目取出物理的頁編號。如果本條目無效，就是進程訪問了它的虛擬記憶體中不存在的區域。在這種情況下，處理器無法解釋位址，必須將控制權傳遞給作業系統來處理。
處理器具體如何通知作業系統進程在訪問無法轉換的無效的虛擬位址，這個方式是和處理器相關的。處理器將這種資訊（page fault）進行傳遞，作業系統得到通知，虛擬位址出錯，以及出錯的原因。
　
假設這是一個有效的頁表條目，處理器取出物理頁號並乘以頁大小，得到了實體記憶體中本頁的基礎地址。最後，處理器加上它需要的指令或資料的偏移量。
　
再用上述例子，進程Y的虛擬頁編號1映射到了物理頁編號4（起始於0x8000 ， 4x 0x2000），加上偏移0x194，得到了最終的物理位址0x8194。
　
通過這種方式將虛擬位址映射到物理位址，虛擬記憶體可以用任意順序映射到系統的實體記憶體中。例如，圖3.1 中，虛擬記憶體X的虛擬頁編號映射到了物理頁編號1而虛擬頁編號7雖然在虛擬記憶體中比虛擬頁0要高，卻映射到了物理頁編號0。這也演示了虛擬記憶體的一個有趣的副產品：虛擬記憶體頁不必按指定順序映射到實體記憶體中。
　
3.1.1 Demand Paging
　
因為實體記憶體比虛擬記憶體少得多，作業系統必須避免無效率地使用實體記憶體。節省實體記憶體的一種方法是只載入執行程式正在使用的虛擬頁。例如：一個資料庫程式可能正在資料庫上運行一個查詢。在這種情況下，並非所有的資料必須放到記憶體中，而只需要正被檢查的資料記錄。如果這是個查找型的查詢，那麼載入程式中增加記錄的代碼就沒什麼意義。這種進行訪問時才載入虛擬頁的技術叫做demand paging。
　
當一個進程試圖訪問當前不在記憶體中的虛擬位址的時候處理器無法找到引用的虛擬頁對應的頁表條目。例如：圖3.1中進程X的頁表中沒有虛擬頁2 的條目，所以如果進程X試圖從虛擬頁2中的位址讀取時，處理器無法將位址轉換為物理位址。這時處理器通知作業系統發生page fault。
　
如果出錯的虛擬位址無效意味著進程試圖訪問它不應該訪問的虛擬位址。也許是程式出錯，例如向記憶體中任意位址寫。這種情況下，作業系統會中斷它，從而保護系統中其他的進程。
如果出錯的虛擬位址有效但是它所在的頁當前不在記憶體中，作業系統必須從磁片映射中將相應的頁載入到記憶體中。相對來講磁片存取需要較長時間，所以進程必須等待直到該頁被取到記憶體中。如果當前有其他系統可以運行，作業系統將選擇其中一個運行。取到的頁被寫到一個空閒的頁面，並將一個有效的虛擬頁條目加到進程的頁表中。然後這個進程重新運行發生記憶體錯誤的地方的機器指令。這一次虛擬記憶體存取進行時，處理器能夠將虛擬位址轉換到物理位址，所以進程得以繼續運行。
　
Linux使用demand paging技術將可執行映射載入到進程的虛擬記憶體中。當一個命令執行時，包含它的檔被打開，它的內容被映射到進程的虛擬記憶體中。這個過程是通過修改描述進程記憶體映射的資料結構來實現，也叫做記憶體映射（memory mapping）。但是，實際上只有映射的第一部分真正放在了實體記憶體中。映射的其餘部分仍舊在磁片上。當映射執行時，它產生page fault，Linux使用進程的記憶體映射表來確定映射的那一部分需要載入到記憶體中執行。
　
3.1.2 Swapping（交換）
　
如果進程需要將虛擬頁放到實體記憶體中而此時已經沒有空閒的物理頁，作業系統必須廢棄物理空間中的另一頁，為該頁讓出空間。
　
如果實體記憶體中需要廢棄的頁來自磁片上的映射或者資料檔案，而且沒有被寫過所以不需要存儲，則該頁被廢棄。如果進程又需要該頁，它可以從映射或資料檔案中再次載入到記憶體中。
但是，如果該頁已經被改變，作業系統必須保留它的內容以便以後進行訪問。這種也叫做dirty page，當它從實體記憶體中廢棄時，被存到一種叫做交換檔的特殊檔中。因為訪問交換檔的速度和訪問處理器以及實體記憶體的速度相比很慢，作業系統必須判斷是將資料頁寫到磁片上還是將它們保留在記憶體中以便下次訪問。
　
如果決定哪些頁需要廢棄或者交換的演算法效率不高，則會發生顛簸（thrashing）。這時，頁不斷地被寫到磁片上，又被讀回，作業系統過於繁忙而無法執行實際的工作。例如在圖3.1中，如果物理頁號1經常被訪問，那麼就不要將它交換到硬碟上。進程正在使用的也叫做工作集(working set)。有效的交換方案應該保證所有進程的工作集都在實體記憶體中。
　
Linux使用LRU（Least Recently Used最近最少使用）的頁面技術來公平地選擇需要從系統中廢棄的頁面。這種方案將系統中的每一頁都賦予一個年齡，這個年齡在頁面存取時改變。頁面訪問越多，年紀越輕，越少訪問，年紀越老越陳舊。陳舊的頁面是交換的好候選。
　
3.1.3 Shared Vitual Memory（共用虛擬記憶體）
　
虛擬記憶體使多個進程可以方便地共用記憶體。所有的記憶體訪問都是通過頁表，每一個進程都有自己的頁表。對於兩個共用一個實體記憶體頁的進程，這個物理頁編號必須出現在兩個進程的頁表中。
圖3.1顯示了兩個共用物理頁號4的進程。對於進程X虛擬頁號是4，而對於進程Y虛擬頁號是6。這也表明了共用頁的一個有趣的地方：共用的物理頁不必存在共用它的進程的虛擬記憶體空間的同一個地方。
　
3.1.4 Physical and Vitual Addressing Modes（物理和虛擬定址模式）
　
對於作業系統本身而言，運行在虛擬記憶體中沒有什麼意義。如果作業系統必須維護自身的頁表，這將會是一場噩夢。大多數多用途的處理器同時支援物理位址模式和虛擬位址模式。物理定址模式不需要頁表，處理器在這種模式下不需要進行任何位址轉換。Linux核心運行在物理位址模式。
　
Alpha AXP處理器沒有特殊的物理定址模式。它將記憶體空間分為幾個區，將其中兩個指定為物理映射位址區。核心的位址空間叫做KSEG位址空間，包括從0xfffffc0000000000向上的所有位址。為了執行連接在KSEG的代碼（核心代碼）或者訪問那裏的資料，代碼必須在核心態執行。Alpha 上的Linux核心連接到從位址0xfffffc0000310000執行。
　

3.1.5 Access Control（訪問控制）
　
頁表條目也包括訪問控制資訊。當處理器使用頁表條目將進程的虛擬位址映射到物理位址的時候，它很容易利用訪問控制資訊控制進程不要用不允許的方式進行訪問。
　
有很多原因你希望限制對於記憶體區域的訪問。一些記憶體，比如包含執行代碼，本質上是唯讀的代碼，作業系統應該禁止進程寫它的執行代碼。反過來，包括資料的頁可以寫，但是如果試圖執行這段記憶體應該失敗。大多數處理器有兩種執行狀態：核心態和用戶態。你不希望用戶直接執行核心態的代碼或者存取核心資料結構，除非處理器運行在核心態。
　
訪問控制資訊放在PTE（page table entry）中，而且和具體處理器相關。圖3.2顯示了Alpha AXP的PTE。各個位意義如下：
　
V 有效，這個PTE是否有效
FOE “Fault on Execute” 試圖執行本頁代碼時，處理器是否要報告page fault，並將控制權傳遞給作業系統。
ＦＯＷ　“Fault on Write” 如上，在試圖寫本頁時產生page fault
FOR “fault on read” 如上，在試圖讀本頁時產生page fault
ASM 位址空間匹配。用於作業系統清除轉換緩衝區中的部分條目
KRE 核心態的代碼可以讀本頁
URE 用戶態的代碼可以讀本頁
GII 間隔因數，用於將一整塊映射到一個轉換緩衝條目而非多個。
KWE 核心態的代碼可以寫本頁
UWE 用戶態的代碼可以寫本頁
Page frame number 對於V位有效的PTE，包括了本PTE的物理頁編號；對於無效的PTE，如果不是0，包括了本頁是否在交換檔的資訊。
　
以下兩位由Linux定義並使用
_PAGE_DIRTY 如果設置，本頁需要寫到交換檔中。
_PAGE_ACCESSED Linux 使用，標誌一頁已經訪問過
　
3.2 Caches（快取記憶體）
如果你用以上理論模型來實現一個系統，它可以工作，但是不會太高效率。作業系統和處理器的設計師都盡力讓系統性能更高。除了使用更快的處理器、記憶體等，最好的方法是維護有用資訊和資料的快取記憶體，這會使一些操作更快。Linux使用了一系列和快取記憶體相關的記憶體管理技術：
　
Buffer Cache： Buffer cache 包含了用於塊設備驅動程式的資料緩衝區。這些緩衝區大小固定（例如512位元組），包括從塊設備讀出的資料或者要寫到塊設備的資料。塊設備是只能通過讀寫固定大小的資料塊來訪問的設備。所有的硬碟都是塊設備。塊設備用設備識別字和要訪問的資料塊編號作為索引，用來快速定位資料塊。塊設備只能通過buffer cache存取。如果資料可以在buffer cache中找到，那就不需要從物理塊設備如硬碟上讀取，從而使訪問加快。
參見fs/buffer.c
Page Cache 用來加快對磁片上映射和資料的訪問。它用於緩存檔的邏輯內容，一次一頁，並通過檔和檔內的偏移來訪問。當資料頁從磁片讀到記憶體中時，被緩存到page cache中。
參見mm/filemap.c
Swap Cache 只有改動過的（或髒dirty）頁才存在交換檔中。只要它們寫到交換檔之後沒有再次修改，下一次這些頁需要交換出來的時候，就不需要再寫到交換檔中，因為該頁已經在交換檔中了，直接廢棄該頁就可以了。在一個交換比較厲害的系統，這會節省許多不必要和高代價的磁片操作。
參見mm/swap_state.c mm/swapfile.c
　
　

Hardware Cache:硬體快取記憶體的常見的實現方法是在處理器裏面：PTE的快取記憶體。這種情況下，處理器不需要總是直接讀頁表，而在需要時把頁轉換表放在緩存區裏。CPU裏有轉換表緩衝區(TLB Translation Look-aside Buffers)，放置了系統中一個或多個進程的頁表條目的緩存的拷貝。
　
當引用虛擬位址時，處理區試圖在TLB中尋找。如果找到了，它就直接將虛擬位址轉換到物理位址，進而對資料執行正確的操作。如果找不到，它就需要作業系統的幫助。它用信號通知作業系統，發生了TLB missing。一個和系統相關的機制將這個異常轉到作業系統相應的代碼來處理。作業系統為這個位址映射生成新的TLB條目。當異常清除之後，處理器再次嘗試轉換虛擬位址，這一次將會成功因為TLB中該位址有了一個有效的條目。
　
快取記憶體的副作用（不管是硬體或其他方式的）在於Linux必須花大量時間和空間來維護這些快取記憶體區，如果這些快取記憶體區崩潰，系統也會崩潰。
　
3.3 Linux Page Tables（Linux頁表）
　
Linux假定了三級頁表。訪問的每一個頁表包括了下一級頁表的頁編號。圖3.3顯示了一個虛擬位址如何分為一系列欄位：每一個欄位提供了在一個頁表中的偏移量。為了將虛擬位址轉換為物理位址，處理器必須取得每一級欄位的內容，轉換為包括該頁表的物理頁內的偏移，然後讀取下一級頁表的頁編號。重複三次直到包括虛擬位址的物理位址的頁編號找到為止。然後用虛擬位址中的最後一個欄位：位元組偏移量，在頁內查找資料。
　
Linux運行的每一個平臺都必須提供轉換宏，讓核心處理特定進程的頁表。這樣，核心不需要知道頁表條目的具體結構或者如何組織。通過這種方式，Linux成功地使用了相同的頁表處理程式用於Alpha和Intel x86處理器，其中Alpha使用三級頁表，而Intel使用二級頁表。
參見include/asm/pgtable.h
　
3.4 Page Allocation and Deallocation (頁的分配和回收)
　
系統中對於物理頁有大量的需求。例如，當程式映射載入到記憶體中的時候，作業系統需要分配頁。當程式結束執行並卸載時需要釋放這些頁。另外為了存放核心相關的資料結構比如頁表自身，也需要物理頁。這種用於分配和回收頁的機制和資料結構對於維護虛擬記憶體子系統的效率也許是最重要的。
　
系統中的所有的物理頁都使用mem_map資料結構來描述。這是一個mem_map_t結構的鏈表，在啟動時進行初始化。每一個mem_map_t（容易混淆的是這個結構也被稱為page 結構）結構描述系統中的一個物理頁。重要的欄位（至少對於記憶體管理而言）是：
參見include/linux/mm.h
　
count 本頁用戶數目。如果本頁由多個進程共用，計數器大於1。
Age 描述本頁的年齡。用於決定本頁是否可以廢棄或交換出去。
Map_nr mem_map_t描述的物理頁編號。
　
頁分配代碼使用free_area向量來查找空閒的頁。整個緩衝管理方案用這種機制來支持。只要用了這種代碼，處理器使用的頁的大小和物理頁的機制就可以無關。
　
每一個free_area單元包括頁塊的資訊。陣列中的第一個單元描述了單頁，下一個是2頁大小的塊，下一個是4頁大小的塊，以此類推，依次向上都是2的倍數。這個鏈表單元用作佇列的開頭，有指向mem_map陣列中頁的資料結構的指標。空閒的頁塊在這裏排隊。Map是一個跟蹤這麼大小的頁的分配組的點陣圖。如果頁塊中的第N塊空閒，則點陣圖中的第N位置位。
　
圖3.4顯示了free_area結構。單元0有一個空閒頁（頁編號0），單元2有2個4頁的空閒塊，第一個起始於頁編號4，第二個起始於頁編號56。
　
3.4.1 Page Allocation (頁分配)
參見mm/page_alloc.c get_free_pages()
　
Linux使用Buddy演算法有效地分配和回收頁塊。頁分配代碼試圖分配一個由一個或多個物理頁組成的塊。頁分配使用2的冪數大小的塊。這意味著可以分配1頁大小，2頁大小，4頁大小的塊，依此類推。只要系統有滿足需要的足夠的空閒頁（nr_free_pages > min_free_pages），分配代碼就會在free_area中查找滿足需要大小的一個頁塊。Free_area中的每一個單元都有描述自身大小的頁塊的佔用和空閒情況的點陣圖。例如，陣列中的第2個單元擁有描述4頁大小的塊的空閒和佔用的分配圖。
　
這個演算法首先找它請求大小的記憶體頁塊。它跟蹤free_area資料結構中的list單元佇列中的空閒頁的鏈表。如果請求大小的頁塊沒有空閒，就找下一個尺寸的塊（2倍於請求的大小）。繼續這一過程一直到遍曆了所有的free_area或者找到了空閒頁塊。如果找到的頁塊大於請求的頁塊，則該塊將被分開成為合適大小的塊。因為所有的塊都是2的冪次的頁數組成，所以這個分割的過程比較簡單，你只需要將它平分就可以了。空閒的塊則放到適當的佇列，而分配的頁塊則返回給調用者。
　

　
例如在圖3.4中，如果請求2頁的資料塊，第一個4頁塊（起始於頁編號4）將會被分為兩個2頁塊。起始於頁號4的第一個2頁塊將會被返回給調用者，而第二個2頁塊（起始於頁號6）將會排在free_area陣列中的單元1中2頁空閒塊的佇列中。
　
3.4.2 Page Deallocation（頁回收）
　
分配頁塊的過程中將大的頁塊分為小的頁塊，將會使記憶體更為零散。頁回收的代碼只要可能就把頁聯成大的頁塊。其實頁塊的大小很重要（2的冪數），因為這樣才能很容易將頁塊組成大的頁塊。
　
只要一個頁塊回收，就檢查它的相鄰或一起的同樣大小的頁塊是否空閒。如果是這樣，就把它和新釋放的頁塊一起組成以一個新的下一個大小的空閒頁塊。每一次兩個記憶體頁塊組合成為更大的頁塊時，頁回收代碼都要試圖將頁塊合併成為更大的塊。這樣，空閒的頁塊就會盡可能的大。
例如，在圖3.4，如果頁號1釋放，那麼它會和已經空閒的頁號0一起組合並放在free_area的單元1中空閒的2頁塊佇列中。
　
3.5 Memory Mapping （記憶體映射）
　
當一個映射執行時，執行映射的內容必須放在進程的虛擬位址空間中。對於執行映射連接到的任意共用庫，情況也是一樣。執行檔實際並沒有放到實體記憶體，而只是被連接到進程的虛擬記憶體。這樣，只要運行程式引用了映射的部分，這部分映射就從執行檔中載入到記憶體中。這種映射和進程虛擬位址空間的連接叫做記憶體映射。
　
每一個進程的虛擬記憶體用一個mm_struct 資料結構表示。這包括當前執行的映射的資訊（例如bash）和指向一組vm_area_struct結構的指標。每一個vm_area_struct的資料結構都描述了記憶體區域的起始、進程對於記憶體區域的訪問許可權和對於這段記憶體的操作。這些操作是一組常式，Linux用於管理這段虛擬記憶體。例如其中一種虛擬記憶體操作就是當進程試圖訪問這段虛擬記憶體時發現（通過page fault）記憶體不在實體記憶體中所必須執行的正確操作，這個操作叫做　nopage 操作。Linux請求把執行映射的頁載入到記憶體中的時候用到nopage操作。
當一個執行映射映射到進程的虛擬位址空間時，產生一組vm_area_struct資料結構。每一個vm_area_struct結構表示執行映射的一部分：執行代碼、初始化資料（變數）、未初始化資料等等。Linux支援一系列標準的虛擬記憶體操作，當vm_area_struct資料結構創建時，一組正確的虛擬記憶體操作就和它們關聯在一起。
　
3.6 Demand Paging
　
只要執行映射映射到進程的虛擬記憶體中，它就可以開始運行。因為只有映射的最開始的部
分是放在實體記憶體中，很快就會訪問到還沒有放在實體記憶體的虛擬空間區。當進程訪問沒有有效頁表條目的虛擬位址的時候，處理器向Linux報告page fault。Page fault描述了發生page fault的虛擬位址和記憶體訪問類型。
　
Linux必須找到page fault 發生的空間區所對應的vm_area_struct資料結構（用Adelson-Velskii and Landis AVL樹型結構連接在一起）。如果找不到這個虛擬位址對應的vm_area_struct結構，說明進程訪問了非法的虛擬位址。Linux將向該進程發信號，發送一個SIGSEGV信號，如果進程沒有處理這個信號，它就會退出。
參見 handle_mm_fault() in mm/memory.c
　
Linux然後檢查page faul的類型和該虛擬記憶體區所允許的訪問類型。如果進程用非法的方式訪問記憶體，比如寫一個它只可以讀的區域，也會發出記憶體錯的信號。
　
現在Linux確定page fault是合法的，它必須進行處理。Linux必須區分在交換檔和磁片映射中的頁，它用發生page fault的虛擬位址的頁表條目來確定。
參見do_no_page() in mm/memory.c
　
如果該頁的頁表條目是無效的但非空，此頁是在交換檔中。對於Alpha AXP頁表條目來講，有效位置位但是PFN域非空。這種情況下PFN域存放了此頁在交換檔（以及那一個交換檔）中的位置。頁在交換文件中如何處理在本章後面討論。
　
並非所有的vm_area_struct資料結構都有一整套虛擬記憶體操作，而且那些有特殊的記憶體操作的也可能沒有nopang操作。因為缺省情況下，對於nopage操作，Linux會分配一個新的物理頁並創建有效的頁表條目。如果這一段虛擬記憶體有特殊的nopage操作，Linux會調用這個特殊的代碼。
　
通常的Linux nopage操作用於對執行映射的記憶體映射，並使用page cache將請求的映射頁載入到實體記憶體中。雖然在請求的頁調入的實體記憶體中以後，進程的頁表得到更新，但是也許需要必要的硬體動作來更新這些條目，特別是如果處理器使用了TLB。既然page fault得到了處理，就可以扔在一邊，進程在引起虛擬記憶體訪問錯誤的指令那裏重新運行。
參見mm/filemap.c 中filemap_nopage()
　

　

3.7 The Linux Page Cache
　
Linux的page cache的作用是加速對於磁片檔的訪問。記憶體映射檔每一次讀入一頁，這些頁被存放在page cache中。圖3.6顯示了page cache，包括一個指向mem_map_t資料結構的指標向量：page_hash_table。Linux中的每一個檔都用一個VFS inode的資料結構標示（在第9章描述），每一個VFS I節點都是唯一的並可以完全確定唯一的一個檔。頁表的索引取自VFS 的I節點號和檔中的偏移。
參見linux/pagemap.h
　
當一頁的資料從記憶體映射檔中讀出，例如當demand paging時需要放到記憶體中的時候，此頁通過page cache中讀出。如果此頁在緩存中，就返回一個指向mem_map_t資料結構的指標給page fault 的處理代碼。否則，此頁必須從存放此檔的檔系統中載入到記憶體中。Linux分配實體記憶體並從磁片檔中讀出該頁。如果可能，Linux會啟動對檔下一頁的讀。這種單頁的超前讀意味著如果進程從檔中順序讀數據的話，下一頁數據將會在記憶體中等待。
當程式映射讀取和執行的時候page cache 不斷增長。如果頁不在需要，將從緩存中刪除。比如不再被任何進程使用的映射。當Linux使用記憶體的時候，物理頁可能不斷減少，這時Linux可以減小page cache。
　
3.8 Swapping out and Discarding Pages（交換出去和廢棄頁）
　
當實體記憶體缺乏的時候，Linux記憶體管理子系統必須試圖釋放物理頁。這個任務落在核心交換進程上（kswapd）。核心交換守護進程是一種特殊類型的進程，一個核心線程。核心線程是沒有虛擬記憶體的進程，以核心態運行在物理位址空間。核心交換守護進程名字有一點不恰當，因為它不僅僅是將頁交換到系統交換檔上。它的任務是保證系統有足夠的空閒頁，使記憶體管理系統有效地運行。
　
核心交換守護進程（kswapd）在啟動時由核心的init 進程啟動，並等待核心的交換計時器到期。每一次計時器到期，交換進程檢查系統中的空閒頁數是否太少。它使用兩個變數：free_pages_high和free_pages_low來決定是否釋放一些頁。只要系統中的空閒頁數保持在free_pages_high之上，交換進程什麼都不做。它重新睡眠直到它的計時器下一次到期。為了做這種檢查，交換進程要考慮正在向交換檔中寫的頁數，用nr_async_pages來計數：每一次一頁排到佇列中等待寫到交換檔中的時候增加，寫完的時候減少。Free_page_low和free_page_high是系統啟動時間設置的，和系統中的物理頁數相關。如果系統中的空閒頁數小於free_pages_high或者比free_page_low還低，核心交換進程會嘗試三種方法來減少系統使用的物理頁數：
參見mm/vmscan.c 中的kswapd()
　
減少buffer cache 和page cache的大小
將系統V的共用記憶體頁交換出去
交換和廢棄頁
　
如果系統中的空閒頁數低於free_pages_low，核心交換進程將試圖在下一次運行前釋放6頁。否則試圖釋放3頁。以上的每一種方法都要被嘗試直到釋放了足夠的頁。核心交換進程記錄了它上一次使用的釋放物理頁的方法。每一次運行時它都會首先嘗試上一次成功的方法來釋放頁。
　
釋放了足夠的頁之後，交換進程又一次睡眠，直到它的計時器又一次過期。如果核心交換進程釋放頁的原因是系統空閒頁的數量少於free_pages_low，它只睡眠平時的一半時間。只要空閒頁數大於free_pages_low，交換進程就恢復原來的時間間隔進行檢查。
　
3.8.1 Reducing the size of the Page and Buffer Caches
　
page 和buffer cache中的頁是釋放到free_area向量中的好選擇。Page Cache，包含了記憶體映射檔的頁，可能有不必要的資料，占去了系統的記憶體。同樣，Buffer Cache ，包括了從物理設備讀或向物理設備寫的資料，也可能包含了無用的緩衝。當系統中的物理頁將要耗盡的時候，廢棄這些緩存區中的頁相對比較容易，因為它不需要向物理設備寫（不象將頁從記憶體中交換出去）。廢棄這些頁不會產生多少有害的副作用，只不過使訪問物理設備和記憶體映射檔時慢一點。雖然如此，如果公平地廢棄這些緩存區中的頁，所有的進程受到的影響就是平等的。
　
每一次當核心交換進程要縮小這些緩存區時，它要檢查mem_map頁向量中的頁塊，看是否可以從實體記憶體中廢棄。如果系統空閒頁太低（比較危險時）而核心交換進程交換比較厲害，這個檢查的頁塊大小就會更大一些。頁塊的大小進行迴圈檢查：每一次試圖減少記憶體映射時都用一個不同的頁塊大小。這叫做clock演算法，就象鍾的時針。整個mem_map頁向量都被檢查，每次一些頁。
參見mm/filemap.c shrink_map()
　
檢查的每一頁都要判斷緩存在page cache 或者buffer cache中。注意共用頁的廢棄這時不考慮，一頁不會同時在兩個緩存中。如果該頁不在這兩個緩衝區中，則mem_map頁向量表的下一頁被檢查。
緩存在buffer cache　ch中的頁（或者說頁中的緩衝區被緩存）使緩衝區的分配和釋放更有效。縮小記憶體映射的代碼試圖釋放包含檢查過的頁的緩衝區。如果緩衝區釋放了，則包含緩衝區的頁也被釋放了。如果檢查的頁是在Linux的page cache 中，它將從page cache 中刪除並釋放。
參見 fs/buffer.c free_buffer()
　
如果這次嘗試釋放了足夠的頁，核心交換進程就會繼續等待直到下一次被週期性地喚醒。因為釋放的頁不屬於任何進程的虛擬記憶體（只是緩存的頁），因此不需要更新進程的頁表。如果廢棄的緩存頁仍然不夠，交換進程會試圖交換出一些共用頁。
　
3.8.2 Swapping Out System V Shared Memory Pages（交換出系統V的共用記憶體頁）
　
系統V的共用記憶體是一種進程間通訊的機制，通過兩個或多個進程共用虛擬記憶體交換資訊。進程間如何共用記憶體在第5章詳細討論。現在只要講講每一塊系統V共用記憶體都用一個shmid_ds的資料結構描述就足夠了。它包括一個指向vm_area_struct鏈表資料結構的指標，用於共用此記憶體的每一個進程。Vm_area_struct資料結構描述了此共用記憶體在每一個進程中的位置。這個系統V的記憶體中的每一個vm_area_struct結構都用vm_next_shared和vm_prev_shared指標連接在一起。每一個shmid_ds資料結構都有一個頁表條目的鏈表，每一個條目都描述一個共用的虛擬頁和物理頁的對應關係。
　
核心交換進程將系統V的共用記憶體頁交換出去時也用clock演算法。它每一次運行都記錄了上一次交換出去了那一塊共用記憶體的那一頁。它用兩個索引來記錄：第一個是shmid_ds資料結構陣列中的索引，第二個是這塊共用記憶體區的頁錶鏈中的索引。這樣可以共用記憶體區的犧牲比較公平。
參見ipc/shm.c shm_swap()
　
因為一個指定的系統V共用記憶體的虛擬頁對應的物理頁號包含在每一個共用這塊虛擬記憶體的進程的頁表中，所以核心交換進程必須修改所有的進程的頁表來體現此頁已經不在記憶體而在交換檔中。對於每一個交換出去的共用頁，交換進程必須找到在每一個共用進程的頁表中對應的此頁的條目（通過查找每一個vm_area_struct指標）如果在一個進程頁表中此共用記憶體頁的條目有效，交換進程要把它變為無效，並且標記是交換頁，同時將此共用頁的在用數減1。交換出去的系統V共用頁表的格式包括一個在shmid_ds資料結構組中的索引和在此共用記憶體區中頁表條目的索引。
　
如果所有共用的記憶體都修改過，頁的在用數變為0，這個共用頁就可以寫到交換檔中。這個系統V共用記憶體區的shmid_ds資料結構指向的頁表中此頁的條目將會換成交換出的頁表條目。交換出的頁表條目無效但是包含一個指向打開的交換檔的索引和此頁在此檔內的偏移量。這個資訊用於將此頁再取回實體記憶體中。
　
3.3 Swapping Out and Discarding Pages
　
交換進程輪流檢查系統中的每一個進程是否可以用於交換。好的候選是可以交換的進程（有一些不行）並且有可以從記憶體中交換出去或廢棄的一個或多個頁。只有其他方法都不行的時候才會把頁從實體記憶體交換到系統交換檔中。
參見 mm/vmscan.c swap_out()
　
來自於映射檔的執行映射的大部分內容可以從檔中重新讀出來。例如：一個映射的執行指令不會被自身改變，所以不需要寫到交換檔中。這些頁只是被簡單地廢棄。如果再次被進程引用，可以從執行映射再次載入到記憶體中。
　
一旦要交換的進程確定下來，交換進程就查看它的所有虛擬記憶體區域，尋找沒有共用或鎖定的區域。Linux不會把選定進程的所有可以交換出去的頁都交換出去，而只是去掉少量的頁。如果頁在記憶體中鎖定，則不能被交換或廢棄。
參見mm/vmscan.c swap_out_vme() 跟蹤進程mm_struct中排列的vm_area_struct結構中的vm_next　vm_nex指標。
　
Linux的交換演算法使用了頁的年齡。每一個頁都有一個計數器（放在mem_map_t資料結構中），告訴核心交換進程此頁是否值得交換出去。頁不用時變老，訪問時更新。交換進程只交換老的頁。缺省地，頁第一次分配時年齡賦值為3。每一次訪問，它的年齡就增加3，直到20。每一次系統交換進程運行時它將頁的年齡減1使頁變老。這個缺省的行為可以更改，所以這些資訊（和其他相關資訊）都存放在swap_control資料結構中。
如果頁太老(年齡age = 0)，交換進程會進一步處理。髒頁可以交換出去，Linux在描述此頁的PTE中用一個和體系結構相關的位元來描述這種頁（見圖3.2）。但是，並非所有的髒頁都需要寫到交換檔。每一個進程的虛擬記憶體區域都可以擁有自己的交換操作（由vm_area_struct中的vm_ops指標指示），如果這樣，交換進程會用它的這種方式。否則，交換進程會從交換檔中分配一頁，並把此頁寫到該文件中。
　
此頁的頁表條目會用一個無效的條目替換，但是包括了此頁在交換檔的資訊：此頁所在檔內的偏移和所用的交換檔。不管什麼方式交換，原來的物理頁被放回到free_area重釋放。乾淨（或不髒）的頁可以被廢棄，放回到free_area中重用。
　
如果交換或廢棄了足夠的可交換進程的頁，交換進程重新睡眠。下一次喚醒時它會考慮系統中的下一個進程。這樣，交換進程輕咬去每一個進程的物理頁，直到系統重新達到平衡。這種做法比交換出整個進程更公平。
　
3.9 The Swap Cache（交換緩存）
　
當把頁交換到交換檔時，Linux會避免寫不必要寫的頁。有時可能一個頁同時存在於交換檔和實體記憶體中。這發生於一頁被交換出記憶體然後在進程要訪問時又被調入記憶體的情況下。只要記憶體中的頁沒有被寫過，交換檔中的拷貝就繼續有效。
　
Linux用swap cache來記錄這些頁。交換緩存是一個頁表條目或者系統物理頁的鏈表。一個交換頁有一個頁表條目，描述使用的交換檔和它在交換檔中的位置。如果交換緩存條目非0，表示在交換檔中的一頁沒有被改動。如果此頁後來被改動了（被寫），它的條目就從交換緩存中刪除）
當Linux需要交換一個物理頁到交換檔的時候，它查看交換緩存，如果有此頁的有效條目，它不需要把此頁寫到交換檔。因為記憶體中的此頁從上次讀到交換檔之後沒有被修改過。
　
交換緩存中的條目是曾經交換出去的頁表條目。它們被標記為無效，但是包含了允許Linux找到正確交換檔和交換檔中正確頁的資訊。
　
3.10 Swapping Page In（交換進）
　
保存在交換檔中的髒頁可能又需要訪問。例如：當應用程式要向虛擬記憶體中寫資料，而此頁對應的物理頁交換到了交換檔時。訪問不在實體記憶體的虛擬記憶體頁會引發page fault。Page fault是處理器通知作業系統它不能將虛擬記憶體轉換到實體記憶體的信號。因為交換出去後虛擬記憶體中描述此頁的頁表條目被標記為無效。處理器無法處理虛擬位址到物理位址的轉換，將控制轉回到作業系統，告訴它發生錯誤的虛擬位址和錯誤的原因。這個資訊的格式和處理器如何把控制轉回到作業系統是和處理器類型相關的。處理器相關的page faule處理代碼必須定位描述包括出錯虛擬位址的虛擬記憶體區的vm_area_struct的資料結構。它通過查找該進程的vm_area_struct資料結構，直到找到包含了出錯的虛擬位址的那一個。這是對時間要求非常嚴格的代碼，所以一個進程的vm_area_struct資料結構按照特定的方式排列，使這種查找花費時間儘量少。
參見 arch/i386/mm/fault.c do_page_fault()
　
執行了合適的和處理器相關的動作並找到了包括錯誤（發生）的虛擬位址的有效的虛擬記憶體，page fault的處理過程又成為通用的，並可用於Linux能運行的所有處理器。通用的page fault處理代碼查找錯誤虛擬位址的頁表條目。如果它找到的頁表條目是交換出去的頁，Linux必須把此頁交換回實體記憶體。交換出去的頁的頁表條目的格式和處理器相關，但是所有的處理器都將這些頁標為無效並在頁表條目中放進了在交換檔中定位頁的必要資訊。Linux使用這種資訊把此頁調回到實體記憶體中。
參見mm/memory.c do_no_page()
　
這時，Linux知道了錯誤（發生）的虛擬位址和關於此頁交換到哪里去的頁表條目。Vm_area_struct資料結構可能包括一個常式的指標，用於把這塊虛擬記憶體中的頁交換回到實體記憶體中。這是swapin操作。如果這塊記憶體中有swapin操作，Linux會使用它。其實，交換出去的系統V的共用記憶體之所以需要特殊的處理因為交換的系統V的共用記憶體頁的格式和普通交換頁的不同。如果沒有swapin操作，Linux假定這是一個普通頁，不需要特殊的處理。它分配一塊空閒的物理頁並將交換出去的頁從交換檔中讀進來。關於從交換檔哪里（和哪一個交換檔）的資訊取自無效的頁表條目。
參見mm/page_alloc.c swap_in()
　
如果引起page fault的訪問不是寫訪問，頁就留在交換緩存中，它的頁表條目標記為不可寫。如果後來此頁又被寫，會產生另一個page fault，這時，此頁被標誌為髒頁，而它的條目也從交換緩存中刪除。如果此頁沒有被修改而又需要交換出來，Linux就可以避免將此頁寫到交換檔，因為此頁已經在交換檔中了。
　
如果將此頁從交換檔調回的訪問是寫訪問，這個頁就從交換緩存中刪除，此頁的頁表條目頁標記為髒頁和可寫。
　
　
Chapter 4
　
Processes （進程）
本章描述進程是什麼以及Linux如何創建、管理和刪除系統中的進程。
　
進程執行作業系統中的任務。程式是存放在磁片上的包括一系列機器代碼指令和資料的可執行的映射，因此，是一個被動的實體。進程可以看作是一個執行中的電腦程式。它是動態的實體，在處理器執行機器代碼指令時不斷改變。處理程式的指令和資料，進程也包括程式計數器和其他CPU的寄存器以及包括臨時資料（例如常式參數、返回位址和保存的變數）的堆疊。當前執行的程式，或者說進程，包括微處理器中所有的當前的活動。Linux是一個多進程的作業系統。進程是分離的任務，擁有各自的權利和責任。如果一個進程崩潰，它不應該讓系統中的另一個進程崩潰。每一個獨立的進程運行在自己的虛擬位址空間，除了通過安全的核心管理的機制之外無法影響其他的進程。
　
在一個進程的生命週期中它會使用許多系統資源。它會用系統的CPU執行它的指令，用系統的實體記憶體來存儲它和它的資料。它會打開和使用檔系統中的檔，會直接或者間接使用系統的物理設備。Linux必須跟蹤進程本身和它使用的系統資源以便管理公平地管理該進程和系統中的其他進程。如果一個進程獨佔了系統的大部分實體記憶體和CPU，對於其他進程就是不公平的。
　
系統中最寶貴的資源就是CPU。通常系統只有一個。Linux是一個多進程的作業系統。它的目標是讓進程一直在系統的每一個CPU上運行，充分利用CPU。如果進程數多於CPU（多數是這樣），其餘的進程必須等到CPU被釋放才能運行。多進程是一個簡單的思想：一個進程一直運行，直到它必須等待，通常是等待一些系統資源，等擁有了資源，它才可以繼續運行。在一個單進程的系統，比如DOS，CPU被簡單地設為空閒，這樣等待的時間就會被浪費。在一個多進程的系統中，同一時刻許多進程在記憶體中。當一個進程必須等待時作業系統將CPU從這個進程拿走，並將它交給另一個更需要的進程。是調度程式選擇了
下一次最合適的進程。Linux使用了一系列的調度方案來保證公平。
　
Linux支持許多不同的可執行檔格式，ELF是其中之一，Java是另一個。Linux必須透明地管理這些檔，因為進程使用系統的共用的庫。
　
4.1 Linux Processes（Linux的進程）
　
Linux中，每一個進程用一個task_struct（在Linux中task和process互用）的資料結構來表示，用來管理系統中的進程。Task向量表是指向系統中每一個task_struct資料結構的指標的陣列。這意味著系統中最大進程數受task向量表的限制，缺省是512。當新的進程創建的時候，從系統記憶體中分配一個新的task_struct，並增加到task向量表中。為了更容易查找，用current指標指向當前運行的進程。
參見include/linux/sched.h
　
除了普通進程，Linux也支援即時進程。這些進程必須對於外界事件迅速反應（因此叫做“即時”），調度程式必須和普通用戶進程區分對待。雖然task_struct資料結構十分巨大、複雜，但是它的域可以分為以下的功能：
　
State 進程執行時它根據情況改變狀態(state)。Linux進程使用以下狀態：（這裏漏掉了SWAPPING，因為看來沒用到）
Running 進程在運行(是系統的當前進程)或者準備運行（等待被安排到系統的一個CPU上）
Waiting 進程在等待一個事件或資源。Linux區分兩種類型的等待進程：可中斷和不可中斷的（interruptible and uninterruptible）。可中斷的等待進程可以被信號中斷，而不可中斷的等待進程直接等待硬體條件，不能被任何情況中斷。
Stopped 進程停止了，通常是接收到了一個信號。正在調試的進程可以在停止狀態。
Zombie 終止的進程，因為某種原因，在task 向量表重任舊有一個task_struct資料結構的條目。就想聽起來一樣，是一個死亡的進程。
　
Scheduling Information 調度者需要這個資訊用於公平地決定系統中的進程哪一個更應該運行。
Identifiers 系統中的每一個進程都有一個進程識別字。進程識別字不是task向量表中的索引，而只是一個數位。每一個進程也都有用戶和組（user and group）的識別字。用來控制進程對於系統中檔和設備的訪問。
Inter-Process Communication Linux支援傳統的UNIX-IPC機制，即信號，管道和信號燈（semaphores），也支援系統V的IPC機制，即共用記憶體、信號燈和消息佇列。關於Linux支持的IPC機制在第5章中描述。
Links 在Linux系統中，沒有一個進程是和其他進程完全無關的。系統中的每一個進程，除了初始的進程之外，都有一個父進程。新進程不是創建的，而是拷貝，或者說從前一個進程克隆的（cloned）。每一個進程的task_struct中都有指向它的父進程和兄弟進程（擁有相同的父進程的進程）以及它的子進程的的指標。在Linux系統中你可以用pstree命令看到正在運行的進程的家庭關係。
　
init(1)-+-crond(9 Cool

|-emacs(387)
|-gpm(146)
|-inetd(110)
|-kerneld(1 Cool

`-update(166)
　
另外系統中的所有的進程資訊還存放在一個task_struct資料結構的雙向鏈表中，根是init進程。這個表讓Linux可以查到系統中的所有的進程。它需要這個表以提供對於ps或者kill等命令的支援。
Times and Timers 在一個進程的生命週期中，核心除了跟蹤它使用的CPU時間還記錄它的其他時間。每一個時間片（clock tick），核心更新jiffies中當前進程在系統和用戶態所花的時間綜合。Linux也支援進程指定的時間間隔的計數器。進程可以使用系統調用建立計時器，在計時器到期的時候發送信號給自己。這種計時器可以是一次性的，也可是週期性的。
File system 進程可以根據需要打開或者關閉檔，進程的task_struct結構存放了每一個打開的檔描述符的指標和指向兩個VFS I節點（inode）的指標。每一個VFS I節點唯一描述一個檔系統中的一個檔或目錄，也提供了對於底層檔系統的通用介面。Linux下如何支援檔系統在第9章中描述。第一個I節點是該進程的根（它的主目錄），第二個是它的當前或者說pwd目錄。Pwd取自Unix命令：印出工作目錄。這兩個VFS節點本身有計數欄位，隨著一個或多個進程引用它們而增長。這就是為什麼你不能刪除一個進程設為工作目錄的目錄。
Virtual memory 多數進程都有一些虛擬記憶體（核心線程和核心守護進程沒有），Linux核心必須知道這些虛擬記憶體是如何映射到系統的實體記憶體中的。
Processor Specific Context 進程可以看作是系統當前狀態的總和。只要進程運行，它就要使用處理器的寄存器、堆疊等等。當一個進程暫停的時候，這些進程的上下文、和CPU相關的上下文必須保存到進程的task_struct結構中。當調度者重新啟動這個進程的時候，它的上下文就從這裏恢復。
　
4.2 Identifiers （標識）
　
Linux，象所有的Unix，使用用戶和組識別字來檢查對於系統中的檔和映射的訪問許可權。Linux系統中所有的檔都有所有權和許可，這些許可描述了系統對於該檔或目錄擁有什麼樣的許可權。基本的許可權是讀、寫和執行，並分配了3組用戶：檔屬主、屬於特定組的進程和系統中的其他進程。每一組用戶都可以擁有不同的許可權，例如一個檔可以讓它的屬主讀寫，它的組讀，而系統中的其他進程不能訪問。
　
Linux使用組來給一組用戶賦予對檔或者目錄的許可權，而不是對系統中的單個用戶或者進程賦予許可權。比如你可以為一個軟體專案中的所有用戶創建一個組，使得只有他們才能夠讀寫項目的源代碼。一個進程可以屬於幾個組（缺省是32個），這些組放在每一個進程的task_struct結構中的groups向量表中。只要進程所屬的其中一個組對於一個檔有訪問許可權，則這個進程就又對於這個檔的適當的組許可權。
一個進程的task_struct中有4對進程和組識別字。
Uid,gid 該進程運行中所使用的用戶的識別字和組的識別字
Effective uid and gid 一些程式把執行進程的uid和gid 改變為它們自己的（在VFS I節點執行映射的屬性中）。這些程式叫做setuid程式。這種方式有用，因為它可以限制對於服務的訪問，特別是那些用其他人的方式運行的，例如網路守護進程。有效的uid 和gid來自setuid程式，而uid和gid 仍舊是原來的。核心檢查特權的時候檢查有效 uid和gid。
File system uid and gid 通常和有效uid和gid相等，檢查對於檔系統的訪問許可權。用於通過NFS安裝的檔系統。這時用戶態的NFS伺服器需要象一個特殊進程一樣訪問檔。只有檔系統uid和gid改變（而非有效uid和gid）。這避免了惡意用戶向NFS的服務程式發送Kill信號。Kill用一個特別的有效uid和gid發送給進程。
Saved uid and gid 這是POSIX標準的要求，讓程式可以通過系統調用改變進程的uid和gid。用於在原來的uid和gid改變之後存儲真實的uid和gid。
　
4.3 Scheduling （調度）
　
所有的進程部分運行與用戶態，部分運行於系統態。底層的硬體如何支援這些狀態各不相同但是通常有一個安全機制從用戶態轉入系統態並轉回來。用戶態比系統態的許可權低了很多。每一次進程執行一個系統調用，它都從用戶態切換到系統態並繼續執行。這時讓核心執行這個進程。Linux中，進程不是互相爭奪成為當前運行的進程，它們無法停止正在運行的其他進程然後執行自身。每一個進程在它必須等待一些系統事件的時候會放棄CPU。例如，一個進程可能不得不等待從一個檔中讀取一個字元。這個等待發生在系統態的系統調用中。進程使用了庫函數打開並讀檔，庫函數又執行系統調用從打開的檔中讀入位元組。這時，等候的進程會被掛起，另一個更加值得的進程將會被選擇執行。進程經常調用系統調用，所以經常需要等待。即使進程執行到需要等待也有可能會用去不均衡的CPU事件，所以Linux使用搶先式的調度。用這種方案，每一個進程允許運行少量一段時間，200毫秒，當這個時間過去，選擇另一個進程運行，原來的進程等待一段時間直到它又重新運行。這個時間段叫做時間片。
　
需要調度程式選擇系統中所有可以運行的進程中最值得的進程。一個可以運行的進程是一個隻等待CPU的進程。Linux使用合理而簡單的基於優先順序的調度演算法在系統當前的進程中進行選擇。當它選擇了準備運行的新進程，它就保存當前進程的狀態、和處理器相關的寄存器和其他需要保存的上下文資訊到進程的task_struct資料結構中。然後恢復要運行的新的進程的狀態（又和處理器相關），把系統的控制交給這個進程。為了公平地在系統中所有可以運行（runnable）的進程之間分配CPU時間，調度程式在每一個進程的task_struct結構中保存了資訊：
參見 kernel/sched.c schedule()
　
policy 進程的調度策略。Linux有兩種類型的進程：普通和即時。即時進程比所有其他進程的優先順序高。如果有一個即時的進程準備運行，那麼它總是先被運行。即時進程有兩種策略：環或先進先出（round robin and first in first out）。在環的調度策略下，每一個即時進程依次運行，而在先進先出的策略下，每一個可以運行的進程按照它在調度佇列中的順序運行，這個順序不會改變。
Priority 進程的調度優先順序。也是它允許運行的時候可以使用的時間量（jiffies）。你可以通過系統調用或者renice命令來改變一個進程的優先順序。
Rt_priority Linux支援即時進程。這些進程比系統中其他非即時的進程擁有更高的優先順序。這個域允許調度程式賦予每一個即時進程一個相對的優先順序。即時進程的優先順序可以用系統調用來修改
Coutner 這時進程可以運行的時間量（jiffies）。進程啟動的時候等於優先順序（priority），每一次時鐘週期遞減。
　
調度程式從核心的多個地方運行。它可以在把當前進程放到等待佇列之後運行，也可以在系統調用之後進程從系統態返回進程態之前運行。需要運行調度程式的另一個原因是系統時鐘剛好把當前進程的計數器(counter)置成了0。每一次調度程式運行它做以下工作：
參見 kernel/sched.c schedule()
　
kernel work 調度程式運行bottom half handler並處理系統的調度任務佇列。這些羽量級的核心線程在第11章詳細描述
Current pocess 在選擇另一個進程之前必須處理當前進程。
如果當前進程的調度策略是環則它放到運行佇列的最後。
如果任務是可中斷的而且它上次調度的時候收到過一個信號，它的狀態變為RUNNING
如果當前進程超時，它的狀態成為RUNNING
如果當前進程的狀態為RUNNING則保持此狀態
不是RUNNING或者INTERRUPTIBLE的進程被從運行佇列中刪除。這意味著當調度程式查找最值得運行的進程時不會考慮這樣的進程。
Process Selection 調度程式查看運行佇列中的進程，查找最值得運行的進程。如果有即時的進程（具有即時調度策略），就會比普通進程更重一些。普通進程的重量是它的counter，但是對於即時進程則是counter 加1000。這意味著如果系統中存在可運行的即時進程，就總是在任何普通可運行的進程之前運行。當前的進程，因為用掉了一些時間片（它的counter減少了），所以如果系統中由其他同等優先順序的進程，就會處於不利的位置：這也是應該的。如果幾個進程又同樣的優先順序，最接近運行佇列前段的那個就被選中。當前進程被放到運行佇列的後面。如果一個平衡的系統，擁有大量相同優先順序的進程，那麼回按照順序執行這些進程。這叫做環型調度策略。不過，因為進程需要等待資源，它們的運行順序可能會變化。
Swap Processes 如果最值得運行的進程不是當前進程，當前進程必須被掛起，運行新的進程。當一個進程運行的時候它使用了CPU和系統的寄存器和實體記憶體。每一次它調用常式都通過寄存器或者堆疊傳遞參數、保存數值比如調用常式的返回位址等。因此，當調度程式運行的時候它在當前進程的上下文運行。它可能是特權模式：核心態，但是它仍舊是當前運行的進程。當這個進程要掛起時，它的所有機器狀態，包括程式計數器(PC)和所有的處理器寄存器，必須存到進程的task_struct資料結構中。然後，必須載入新進程的所有機器狀態。這種操作依賴於系統，不同的CPU不會完全相同地實現，不過經常都是通過一些硬體的幫助。
　
交換出去進程的上下文發生在調度的最後。前一個進程存儲的上下文，就是當這個進程在調度結束的時候系統的硬體上下文的快照。相同的，當載入新的進程的上下文時，仍舊是調度結束時的快照，包括進程的程式計數器和寄存器的內容。
　
如果前一個進程或者新的當前進程使用虛擬記憶體，則系統的頁表需要更新。同樣，這個動作適合體系結構相關。Alpha AXP處理器，使用TLT（Translation Look-aside Table）或者緩存的頁表條目，必須清除屬於前一個進程的緩存的頁表條目。
　
4.3.1 Scheduling in Multiprocessor Systems（多處理器系統中的調度）
　
在Linux世界中，多CPU系統比較少，但是已經做了大量的工作使Linux成為一個SMP（對稱多處理）的作業系統。這就是，可以在系統中的CPU之間平衡負載的能力。負載均衡沒有比在調度程式中更重要的了。
　
在一個多處理器的系統中，希望的情況是：所有的處理器都繁忙地運行進程。每一個進程都獨立地運行調度程式直到它的當前的進程用完時間片或者不得不等待系統資源。SMP系統中第一個需要注意的是系統中可能不止一個空閒（idle）進程。在一個單處理器的系統中，空閒進程是task向量表中的第一個任務，在一個SMP系統中，每一個CPU都有一個空閒的進程，而你可能有不止一個空閒CPU。另外，每一個CPU有一個當前進程，所以SMP系統必須記錄每一個處理器的當前和空閒進程。
在一個SMP系統中，每一個進程的task_struct都包含進程當前運行的處理器編號（processor）和上次運行的處理器編號（last_processor）。為什麼進程每一次被選擇運行時不要在不同的CPU上運行是沒什麼道理的，但是Linux可以使用processor_mask把進程限制在一個或多個CPU上。如果位元N置位元，則該進程可以運行在處理器N上。當調度程式選擇運行的進程的時候，它不會考慮processor_mask相應位元沒有設置的進程。調度程式也會利用上一次在當前處理器運行的進程，因為把進程轉移到另一個處理器上經常會有性能上的開支。

4.4 Files（文件）
　
圖4.1顯示了描述系統每一個進程中的用於描述和檔系統相關的資訊的兩個資料結構。第一個fs_struct包括了這個進程的VFS I節點和它的umask。Umask是新檔創建時候的缺省模式，可以通過系統調用改變。
參見include/linux/sched.h
　
第二個資料結構，files_struct，包括了進程當前使用的所有檔的資訊。程式從標準輸入讀取，向標準輸出寫，錯誤資訊輸出到標準錯誤。這些可以是檔，終端輸入/輸出或者世紀的設備，但是從程式的角度它們都被看作是檔。每一個檔都有它的描述符，files_struct包括了指向256個file資料結果，每一個描述進程形用的檔。F_mode域描述了檔創建的模式：唯讀、讀寫或者只寫。F_pos記錄了下一次讀寫操作在檔中的位置。F_inode指向描述該檔的I節點，f_ops是指向一組常式位址的指標，每一個位址都是一個用於處理檔的函數。例如寫資料的函數。這種抽象的介面非常強大，使得Linux可以支援大量的檔類型。我們可以看到，在Linux中pipe也是用這種機制實現的。
　
每一次打開一個檔，就使用files_struct中的一個空閒的file指標指向這個新的file結構。Linux進程啟動時有3個檔描述符已經打開。這就是標準輸入、標準輸出和標準錯誤，這都是從創建它們的父進程中繼承過來的。對於檔的訪問都是通過標準的系統調用，需要傳遞或返回檔描述符。這些描述符是進程的fd向量表中的索引，所以標準輸入、標準輸出和標準錯誤的檔描述符分別是0，1和2。對於檔的所有訪問都是利用file資料結構中的檔操作常式和它的VFS I節點一起來實現的。
　
4.5 Virtual Memory（虛擬記憶體）
　
進程的虛擬記憶體包括多種來源的執行代碼和資料。第一種是載入的程式映射，例如ls命令。這個命令，象所有的執行映射一樣，由執行代碼和資料組成。映射檔中包括將執行代碼和相關的程式資料載入到進程地虛擬記憶體中所需要的所有資訊。第二種，進程可以在處理過程中分配（虛擬）記憶體，比如用於存放它讀入的檔的內容。新分配的虛擬記憶體需要連接到進程現存的虛擬記憶體中才能使用。第三中，Linux進程使用通用代碼組成的庫，例如檔處理。每一個進程都包括庫的一份拷貝沒有意義，Linux使用共用庫，幾個同時運行的進程可以共用。這些共用庫裏邊的代碼和資料必須連接到該進程的虛擬位址空間和其他共用該庫的進程的虛擬位址空間。
　
在一個特定的時間，進程不會使用它的虛擬記憶體中包括的所有代碼和資料。它可能包括旨在特定情況下使用的代碼，比如初始化或者處理特定的事件。它可能只是用了它的共用庫中一部分常式。如果把所有這些代碼都載入到實體記憶體中而不使用只會是浪費。把這種浪費和系統中的進程數目相乘，系統的運行效率會很低。Linux改為使用demand paging 技術，進程的虛擬記憶體只在進程試圖使用的時候才調入實體記憶體中。所以，Linux不把代碼和資料直接載入到記憶體中，而修改進程的頁表，把這些虛擬區域標誌為存在但是不在記憶體中。當進程試圖訪問這些代碼或者資料，系統硬體會產生一個page fault，把控制傳遞給Linux核心處理。因此，對於進程位址空間的每一個虛擬記憶體區域，Linux需要直到它從哪里來和如何把它放到記憶體中，這樣才可以處理這些page fault。
　
Linux核心需要管理所有的這些虛擬記憶體區域，每一個進程的虛擬記憶體的內容通過一個它的task_struct指向的一個mm_struct　mm_struc資料結構描述。該進程的mm_struct資料結構也包括載入的執行映射的資訊和進程頁表的指標。它包括了指向一組vm_area_struct資料結構的指標，每一個都表示該進程中的一個虛擬記憶體區域。
　
這個鏈結表按照虛擬記憶體順序排序。圖4.2顯示了一個簡單進程的虛擬記憶體分佈和管理它的核心資料結構。因為這些虛擬記憶體區域來源不同，Linux通過vm_area_struct指向一組虛擬記憶體處理常式（通過vm_ops）的方式抽象了介面。這樣進程的所有虛擬記憶體都可以用一種一致的方式處理，不管底層管理這塊記憶體的服務如何不同。例如，會有一個通用的常式，在進程試圖訪問不存在的記憶體時調用，這就是page fault 的處理。
　
當Linux為一個進程創建新的虛擬記憶體區域和處理對於不在系統實體記憶體中的虛擬記憶體的引

paul · 發表於: 星期六七月 24, 2004 3:39 pm 文章主題:

喔喔~ 這篇文章有空要來研讀一下 ^^~ 謝謝喔! Smile