Linux 核心--1.前言
原著: 翻譯: Banyan & FIFA (2001-04-27 13:52:07)
原著: David A Rusling
翻譯: Banyan & fifa
--------------------------------------------------------------------------------
本書是為那些想了解Linux內核工作原理的Linux狂熱愛好者而寫。 它並非一本內部手冊。主要描敘了Linux設計的原理與機制；以及Linux內核怎樣工作及其原因。
Linux還在不斷改進；本書基於目前比較流行且性能穩定的2.0.33核心。
Version 0.8-3
David A Rusling
[email protected] --------------------------------------------------------------------------------
前言
Linux是互連網上的獨特現象。雖然它是由學生的業余愛好發展而來，但是現在它已經成為最為流行的免費操作系統。對很多人來說，Linux是一個謎。免費的東西怎麼會變得如此有價值？在個由少數軟件公司統治的世界，由一幫HACKER們編寫的東西是怎樣與那些公司的產品競爭的？ 這些軟件是如何分發給分布在世界各個角落，希望得到穩定產品的人們的？事實上Linux的確穩定而富有競爭力。許多大學與研究機構都使用Linux完成他們的日常計算任務。人們在家用PC上使用Linux,許多公司也在使用它--盡管他們並不總是樂意承認這點。Linux主要用來浏覽WEB，管理WEB站點，撰寫與發送EMAIL，以及玩游戲。Linux絕對不是玩具而是具有專業水平的操作系統，它的愛好者遍及世界。
Linux的源頭要追溯到最古老的UNIX。1969年，Bell實驗室的Ken Thompson開始利用一台閒置的 PDP-7計算機開發了一種多用戶，多任務操作系統。很快，Dennis Richie加入了這個項目，在他們共同努力下誕生了最早的UNIX。Richie受一個更早的項目——MULTICS的啟發，將此操作系統命名為Unix。早期UNIX是用匯編語言編寫的，但其第三個版本用一種嶄新的編程語言C重新設計了。C是Richie設計出來並用於編寫操作系統的程序語言。通過這次重新編寫，Unix得以移植到更為強大的 DEC PDP-11/45與11/70計算機上運行。後來發生的一切，正如他們所說，已經成為歷史。Unix從實驗室走出來並成為了操作系統的主流，現在幾乎每個主要的計算機廠商都有其自有版本的Unix.
Linux起源於一個學生的簡單需求。Linus Torvalds,Linux的作者與主要維護者，在其上大學時所買得起的唯一軟件是Minix. Minix是一個類似Unix，被廣泛用來輔助教學的簡單操作系統。Linus 對Minix不是很滿意，於是決定自己編寫軟件。他以學生時代熟悉的Unix作為原型， 在一台Intel 386 PC上開始了他的工作。他的進展很快，受工作成績的鼓舞，他將這項成果通過互連網與其他同學共享，主要用於學術領域。有人看到了這個軟件並開始分發。每當出現新問題時，有人會立刻找到解決辦法並加入其中，很快的， Linux成為了一個操作系統。值得注意的是Linux並沒有包括Unix源碼。它是按照公開的POSIX標准重新編寫的。Linux大量使用了由麻省劍橋免費軟件基金的GNU軟件，同時Linux自身也是用它們構造而成。
許多人將Linux視作簡單工具並將其放入CDROM中來分發。很多Linux使用者使用它來編寫應用程序或者運行別人編寫的應用程序。這些人熱切的閱讀HOWTO手冊，當系統的一部分被正確的設置時，他們總是激動不已，失敗時則沮喪氣餒。只有少部分人敢於編寫設備驅動程序並將核心的補丁提供給Linus Torvalds，Linus Torvalds從每個志願者那裡接收補充代碼與對核心的修改代碼。
這種情形聽起來象非常混亂，但Linus進行了非常嚴格的質量控制並由他負責將所有的新代碼加入核心。只有少部分人對Linux 核心貢獻了源代碼。 大多數Linux的使用者並不關心系統是如何工作，或者如何組合在一起的。這種情況令人惋惜，因為閱讀Linux源代碼提供了一個學習操作系統的絕好機會。這不僅僅因為它寫得好，還因為它的源碼是可以免費得到的。因為雖然作者們對其軟件保留版權，但是在免費軟件基金的GNU公開授權下源代碼是可以自由分發的。第一眼看去，源碼是非常復雜的。但是通過進一步觀察你可以發現源碼目錄中包含有Kernel,mm以及net的目錄， 不過要想知道這些目錄中包含了那些代碼以及代碼是如何工作的就需要對Linux的總體結構與目標有較深入的理解。簡而言之，這也是本書所希望達到的目標，為讀者提供一個Linux如何工作清晰的印象。當你將文件從一個目錄拷到另一個目錄或者閱讀電子郵件時，不妨在腦海中勾勒一下系統中正在發生什麼事情，我還清楚的記得當我感到第一次認識到操作系統真的在工作時的興奮。這種興奮正是我想將它帶給本書的讀者的。
我第一次接觸Linux在1994年下半年當我拜訪Jim Paradis時，當時他正在致力於將Linux移植到Alpha AXP處理器系統上。從1984年開始，我曾經在DEC公司任職，主要工作是網絡與通訊。1992年我開始為新成立的Digital SemicondUCtor分部工作。此分部的任務是全面進入商用芯片市場並銷售芯片，特別是Alpha AXP系列處理器以及DEC以外的Alpha AXP系統板。當首次聽到Linux時我便立刻意識到了這是一個有趣的機會。Jim的狂熱是鼓惑人心的，我也開始幫他一起工作。在工作中，我越來越喜歡這個操作系統及創造它的工程師團體。
Alpha AXP僅僅是Linux可以運行的多種平台中的一個。大多數Linux核心工作在基於Intel處理器 的系統上，但非Intel系統的Linux用戶也越來越多。它們是Alpha AXP, ARM, MIPS, Sparc與Power PC。 雖然我可以根據上敘任何一種平台來編寫本書的內容，但是我的技術知識與背景讓我主要根據Alpha AXP處理器和ARM處理器來編寫。這是本書有時使用非Intel硬件來描敘一些重要觀點。值得注意的是，不管運行在哪種平台上，95%的Linux核心代碼都是相同的。同樣，本書95%的內容是關於Linux 內核的機器無關部分的討論。
本書對讀者的知識與經驗沒有任何要求。我相信對於某一事物的興趣是鼓勵自學的必要因素。不過對於計算機，或者PC和C程序語言的了解將有助於讀者從有關材料中獲益。
本書的組織
本書並不是特意一本Linux的內部手冊。相反它是對操作系統的介紹，同時以Linux作為示例。書中每一章遵循“從共性到特性”的原則。它們將首先給出核心子系統的概敘，然後進行盡可能的詳細描敘。 我不會用routine_X()調用routine_Y()來增加bar數據結構中foo域的值這種方式來描敘核心算法。 你自己可以通過閱讀代碼發現它。每當需要理解一段代碼時，我總是將其數據結構畫出來。這樣我發現了許多相關的核心數據結構以及它們之間的關系。 每一章都是非常獨立的，就象Linux核心子系統一樣。當然有時它們還是有聯系的，比如說，如果你沒有理解虛擬內存工作原理就無法描敘進程。 硬件基本概念一章對現代PC做了簡要介紹。操作系統必須與硬件系統緊密結合在一起協同工作。操作系統需要一些只能夠由硬件提供的服務。為了全面理解Linux，你必須了解有關硬件的基礎知識。 軟件基本概念一章介紹了軟件基本原理與C程序語言。討論了建立Linux這樣的操作系統的工具並且給出了操作系統的目標與功能的概敘。 內存管理這章描敘了Linux如何處理物理內存以及虛擬存儲技術。 進程管理描敘了進程的概念以及Linux核心是如何創建、管理與刪除系統中的進程。 進程間及進程與核心間通訊以協調它們的活動。Linux支持大量進程間通訊（IPC）機制。信號與管道是 其中的兩種，Linux同時還支持系統V IPC機制。這些進程間通訊機制在IPC一章中描敘。 外部設備互連（PCI）標准已經成為PC上低價位高數傳率的總線標准。PCI一章將描敘Linux核心是如何初始化並使用PCI總線及設備的。 中斷及中斷處理一章將著重於Linux核心對中斷的處理。雖然處理中斷有通用的機制與接口，但某些細節是與硬件及CPU體系結構相關的。 Linux的一個長處是其對現代PC的硬件設備強有力的支持。設備驅動程序一章將描敘Linux核心是如何控制系統中的物理設備。 文件系統一章描敘了Linux核心是如何維護它所支持的文件系統中的文件。同時還描敘了虛擬文件系統（VFS）及Linux核心的每種文件系統是如何得到支持。 網絡與Linux幾乎是同義的。在某種意義上Linux是WWW時代互連網的產物。其開發者通過Web來交換信息及代碼。網絡一章描敘了Linux是如何支持TCP/IP這些網絡協議。 核心機制一章主要討論能使Linux核心其他部分有效工作而由核心所提供的一些通用任務與機制。 動態模塊一章描敘Linux核心是如何僅在需要時動態加載某些模塊，比如文件系統。 處理器一章給出了目前Linux可以在其上運行的一些處理器的簡要介紹。 資源一章則提供了有關Linux核心資源的有用信息。
Linux 核心--2.硬件基礎
原著: David A Rusling 翻譯: Banyan & fifa (2001-04-27 13:53:43)
第一章 硬件基礎
操作系統必須與基本硬件系統密切協作。它需要那些僅僅能夠由硬件提供的服務。為了全面理解Linux操作系統，你必須要懂得一些有關硬件的知識。本章將對硬件：現代PC做一個簡要的介紹。 當1975年一月的"Popular Electronics"雜志以Altair 8080的圖片作為封面時，一場革命開始了。 家用電器愛好者能獨立組裝出來的Altair 8080，當時價格僅僅為397美圓。這種帶有256字節內存的8080處理器還沒有顯示器與鍵盤，以今天的標准來看，它是微不足道的。它的創造者， Ed Roberts，發明了"personal computer"來描敘他的新發明。但現在PC這一術語已被用來稱呼那些自己就可以攜帶的計算機。在這個定義上，非常強勁的計算機如Alpha AXP 也可稱為PC。 狂熱的HACKER們看到了Altair的巨大潛力，於是他們開始為它編寫軟件和設計硬件。對早期的先驅來說這意味者某種自由；一種從頑固的超級批處理主機中解放出來的自由。滾滾而來的財富讓許多著迷於此（一台可以放在廚房餐桌上的計算機）的大學生紛紛退學。許多五花八門的硬件開始出現，軟件 HACKER們忙著為這些新機器編寫軟件。有意思的是IBM首先堅定的進行現代PC的設計和制造並於1982 年推出產品。該產品的構造是：8080 CPU、64K字節主存、兩個軟盤驅動器以及25行80列的彩色CGA 顯示器。雖然以現在觀點看那些都不是多麼先進的東西但當時銷售情況卻很好。緊接著，1983年，帶有昂貴的10MB硬盤驅動器的IBM PC-XT出現了。在IBM PC體系結構成為事實上的標准不久之後，大量仿制者如COMPAQ公司出現了。由於這種事實標准的存在，多個硬件公司在這一快速增長的市場上進行了激烈競爭。 但用戶卻從低價中獲益。許多早期PC中的結構特征還保留在現代PC系統中。比如Intel公司最先進的Pentium Pro處理器還保留著Intel 8086的尋址模式。當Linus Torvalds開始寫Linux時，他選擇了當時最廣泛使用同時價格合理的Intel 80386 PC。 圖1.1 典型的PC主板示意圖。 從PC的外部來看，最引人注目的是機箱，鍵盤，鼠標以及顯示器。在機箱前部有一些按鈕，一個微型顯示器顯示著一些數字，此外還有一個軟驅。今天的大多數機器還包含一個CD ROM，另外，如果想保護你的數據，還可以添加一個磁帶機作為備份用。這些設備統稱為外部設備。 盡管CPU是系統的總管，但是它僅僅是一個智能設備。所有的這些外設控制器都具有某種層度的智能，如IDE控制器。在PC內部，你可以看到一個包括CPU或者微處理器，主存和許多ISA或PCI外設控制器插槽的主板（圖1.1）。有些控制器，如IDE磁盤控制器必須建立在系統板上。
圖 1.1: 典型的PC主板.
1.1 CPU
CPU，或者微處理器，是計算機系統的核心。微處理器進行計算或者邏輯操作並且管理來自主存的指令並執行它。在計算機的早期時代，微處理器的功能部件使用的是分立元件（外型很大）。 這就是中央處理單元這一名詞的由來。現代微處理器將部件結合到小型硅片上的集成電路中。在本書中CPU和微處理器及處理器有相同的意義。 微處理器的操作對象是二進制數據；數據由0和1組成。 1和0對應著電子開關的開路與斷路狀態。正如十進制的42表示有4個10和一個2一樣，一個二進制數是一系列表示2的次冪的二進制數字組成。二進制0001對應十進制的1，二進制的0010對應十進制 的2，二進制的0011表示3，而0100對應4。十進制42的二進制表示為101010。但是在計算機程序中， 人們常用十進制來表示數而不是直接使用二進制。 在需要使用二進制數時，人們往往使用16進制數。如十進制數只能從0到9一樣，16進制數可以從 0疏導15，其中10到15分別用字母A、B、C、D、E及F來表示。這樣16進制的2A的十進制表示為42- 2*16+10=42。在C程序語言中，16進制數的前綴為"0x"；16進制的2A寫成0x2A。 微處理器可以執行如加、乘和除以及象"X是否比Y大"這種邏輯運算。 處理器的執行由外部時鐘來監控。這個時鐘稱為系統時鐘，它每隔相同的時間間隔就向CPU發送一個脈沖。在每個時鐘脈沖上，處理器都會做一些工作。比如，處理器每個時鐘脈沖上執行一條指令。處理器的速度一般以系統時鐘的速率來描敘。一個100MHz的處理器每秒將接收100,000,000 個時鐘滴答。但是用CPU的時鐘頻率來描敘CPU的工作能力是不正確的，因為它們執行的指令不相同。 然而，快速的時鐘可以在某種程度上代表高性能的CPU。處理器執行的指令是非常簡單的；例如"將內存X處的內容讀入寄存器Y"。寄存器是微處理器的內部存儲部件，用來存儲數據並對數據執行某些指令。有些指令有可能使處理器停止當前的工作而跳轉到內存中另外一條指令執行。現代微處理器的緊湊設計使得它有可能每秒執行上百萬甚至億條指令。 指令執行前必須從內存中取出來。指令自身要使用的數據也必須從內存中取出來並放置在適當的地方。 微處理器中寄存器的大小、數量以及類型都取決於微處理器的類型。Intel 80486處理器和Alpha AXP 有迥然不同的寄存器，最明顯的區別在於Intel 寄存器為32位而Alpha AXP為64位。一般來說，任何處理器都有許多通用寄存器和少量專用寄存器。許多微處理器有以下幾種特定的寄存器。
程序計數器(PC)
此寄存器包含下條指令執行的地址。每當取回一條指令時，PC的內容將自動增加。
堆棧指針(SP)
微處理器經常需要訪問存儲臨時數據的外部RAM。堆棧是一種便捷的存放臨時數據的方法，處理器提供了特殊指令來將數值壓入堆棧然後將其從堆棧中彈出。 堆棧以後進先出(LIFO)的方式工作。換句話說，如果你壓入兩個值X和Y，然後執行彈棧操作，你將取到Y的值。 有些處理器的堆棧從內存頂部向下增長而有些相反。但有的處理器同時支持這兩種方式，如ARM。
處理機狀態字(PS)
指令的執行將得到執行結果；比如"寄存器X中的內容要大於寄存器Y中的內容？"將得到正確或錯誤作為結果。PS寄存器包含著這些信息及有關處理器當前狀態的其他信息。例如大多數處理器至少有兩種執行方式，核心（或管態）與用戶方式。PS寄存器包含表示當前執行方式的信息。
1.2 內存
所有計算機系統都有一個由不同速度與大小的存儲器組成的層次結構。最快的的存儲器是高速緩存，它被用來暫存主存中的內容。這種存儲器速度非常快但非常昂貴，大多數處理器都有少量的片上高速緩存或者將其放在主板上。有些處理器的高速緩存既包含數據也包含指令，但有些將其分成兩部分。 Alpha AXP處理器有兩個內部高速緩存，一個用來緩存數據（D-Cache）而另一個用來緩存指令（I- Cache）。而外部高速緩存（B-Cache）將兩者混合。這樣，相對外部高速緩存存儲器，主存的速度非常慢。 高速緩存與主存中的內容必須保持一致。換句話說，對應於地址空間的同一個位置，如果該位置的數據被緩存入高速緩存，則其內容必須和主存中的一致。保證高速緩存一致性的工作由硬件和操作系統共同分擔。 這就是在系統中硬件和軟件必須緊密協作的原因。
1.3 總線
主板上分立的部件通過稱為總線的線路連接在一起。系統總線的功能在邏輯上被劃分為三部分： 地址總線、數據總線和控制總線。地址總線為數據傳輸指明內存位置（地址）。數據總線包含傳輸的數據。數據總線是雙向的；它允許數據讀入CPU也支持從CPU讀出來。控制總線則包含幾條表示路由分時和系統的控制信號。當然還有其他一些總線存在，例如ISA和PCI總線是將外設連接到系統的常用方式。
1.4 控制器與外設
外設是一些物理設備，比如說圖象卡或者磁盤，它們受控於位於主板或者主板上插槽中的控制芯片。 IDE磁盤被IDE控制器芯片控制而SCSI磁盤由SCSI磁盤控制器芯片控制。這些控制器通過各種總線連接到CPU上或相互間互連。目前制造的大多數系統使用PCI和ISA總線來連接主要系統部件。控制器是一些類似CPU的處理器，它們可以看做CPU的智能幫手。CPU則是系統的總控。 雖然所有這些控制器互不相同，但是它們的寄存器的功能類似。運行在CPU上的軟件必須能讀出或者寫入這些控制寄存器。其中有一個寄存器可能包含指示錯誤的狀態碼。另一個則用於控制目的，用來改變控制器的運行模式。在總線上的每個控制器可以被CPU所單獨尋址，這是軟件設備驅動程序能寫入寄存器並能控制這些控制器的原因。
1.5 地址空間
系統總線將CPU與主存連接在一起並且和連接CPU與系統硬件外設的總線隔離開。一般來說，硬件外設存在的主存空間叫I/O空間。I/O空間還可以進一步細分，但這裡我們不再深究。CPU既可以訪問系統內存空間又可以訪問I/O空間內存，而控制器自身只能在CPU協助下間接的訪問系統內存。從設備的角度來看，比如說軟盤控制器，它只能看到在ISA總線上的控制寄存器而不是系統內存。典型的CPU使用不同指令來訪問內存與I/O空間。例如，可能有一條指令"將I/O地址0x3F0的內容讀入到寄存器X"。這正是CPU控制系統硬件設備的方式：通過讀寫I/O地址空間上的外設寄存器。在I/O空間中通用外設(IDE控制器、串行口、軟盤控制器等等)上的寄存器經過多年的PC體系結構發展基本保持不變。I/O地址空間0x3f0是串行口(COM1)的控制寄存器之一。 有時控制器需要直接從系統主存中讀寫大量數據。例如當用戶將數據寫入硬盤時。在這種情況 下，直接內存訪問(DMA)控制器將用來允許硬件外設直接訪問系統主存，不過這將處於CPU的嚴格監控下。
1.6 時鐘
所有的操作系統都必須准確的得到當前時間，所以現代PC包含一個特殊的外設稱為實時時鐘(RTC)。它提供了 兩種服務：可靠的日期和時間以及精確的時間間隔。RTC有其自身的電池這樣即使PC掉電時它照樣可以工作，這就是PC總是"知道"正確時間和日期的原因。而時間間隔定時器使得操作系統能進行准確的調度工作。
Linux 核心--3.軟件基礎
原著: David A Rusling 翻譯: Banyan & fifa (2001-04-27 13:54:15)
第二章 軟件基礎
程序是執行某個特定任務的計算機指令集合。程序可以用多種程序語言來編寫：從低級計算機語言-匯編語言到高級的、與機器本身無關的語言入C程序語言。操作系統是一個允許用戶運行如電子表格或者字處理軟件等應用程序的特殊程序。本章將介紹程序設計的基本原則，同時給出操作系統設計目標與功能的概述。
2.1 計算機編程語言
2.1.1 匯編語言
那些CPU從主存讀取出來執行的指令對人類來說是根本不可理解的。它們是告訴計算機如何准確動作的機器代碼。在Intel 80486指令中16進制數0x89E5表示將ESP寄存器的內容拷入EBP寄存器。為最早的計算機設計的工具之一就是匯編器，它可以將人們可以理解的源文件匯編成機器代碼。匯編語言需要顯式的操作寄存器和數據，並且與特定處理器相關。比如說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中。接下來將鄰接單元內容加載到寄存器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
185 pRe 1
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
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文件系統連接時使用的一些相關函數的地址傳入。
Linux 核心--4.內存管理
原著: David A Rusling 翻譯: Banyan & fifa (2001-04-27 13:54:58)
第三章 存儲管理
存儲管理子系統時操作系統中最重要的組成部分之一。在早期計算時代，由於人們所需要的內存數目遠遠大於物理內存，人們設計出了各種各樣的策略來解決此問題，其中最成功的是虛擬內存技術。它使得系統中為有限物理內存競爭的進程所需內存空間得到滿足。
虛擬內存技術不僅僅可讓我們可以使用更多的內存，它還提供了以下功能：
巨大的尋址空間
操作系統讓系統看上去有比實際內存大得多的內存空間。虛擬內存可以是系統中實際物理空間的許多倍。每個進程運行在其獨立的虛擬地址空間中。這些虛擬空間相互之間都完全隔離開來，所以進程間不會互相影響。同時，硬件虛擬內存機構可以將內存的某些區域設置成不可寫。這樣可以保護代碼與數據不會受惡意程序的干擾。
內存映射
內存映射技術可以將映象文件和數據文件直接映射到進程的地址空間。在內存映射中，文件的內容被直接連接到進程虛擬地址空間上。
公平的物理內存分配
內存管理子系統允許系統中每個運行的進程公平地共享系統中的物理內存。
共享虛擬內存
盡管虛擬內存允許進程有其獨立的虛擬地址空間，但有時也需要在進程之間共享內存。 例如有可能系統中有幾個進程同時運行BASH命令外殼程序。為了避免在每個進程的虛擬內存空間內都存在BASH程序的拷貝，較好的解決辦法是系統物理內存中只存在一份BASH的拷貝並在多個進程間共享。動態庫則是另外一種進程間共享執行代碼的方式。共享內存可用來作為進程間通訊(IPC)的手段，多個進程通過共享內存來交換信息。 Linux支持SYSTEM V的共享內存IPC機制。
3.1 虛擬內存的抽象模型
圖3.1 虛擬地址到物理地址映射的抽象模型
在討論Linux是如何具體實現對虛擬內存的支持前，有必要看一下更簡單的抽象模型。
在處理器執行程序時需要將其從內存中讀出再進行指令解碼。在指令解碼之前它必須向內存中某個位置取出或者存入某個值。然後執行此指令並指向程序中下一條指令。在此過程中處理器必須頻繁訪問內存，要麼取指取數，要麼存儲數據。
虛擬內存系統中的所有地址都是虛擬地址而不是物理地址。通過操作系統所維護的一系列表格由處理器實現由虛擬地址到物理地址的轉換。
為了使轉換更加簡單，虛擬內存與物理內存都以頁面來組織。不同系統中頁面的大小可以相同，也可以不同，這樣將帶來管理的不便。Alpha AXP處理器上運行的Linux頁面大小為8KB，而Intel X86系統上使用4KB頁面。每個頁面通過一個叫頁面框號的數字來標示(PFN) 。
頁面模式下的虛擬地址由兩部分構成：頁面框號和頁面內偏移值。如果頁面大小為4KB，則虛擬地址的 11：0位表示虛擬地址偏移值，12位以上表示虛擬頁面框號。處理器處理虛擬地址時必須完成地址分離工作。在頁表的幫助下，它將虛擬頁面框號轉換成物理頁面框號，然後訪問物理頁面中相應偏移處。
圖3.1給出了兩個進程X和Y的虛擬地址空間，它們擁有各自的頁表。這些頁表將各個進程的虛擬頁面映射到內存中的物理頁面。在圖中，進程X的虛擬頁面框號0被映射到了物理頁面框號4。理論上每個頁表入口應包含以下內容：
有效標記，表示此頁表入口是有效的
頁表入口描敘的物理頁面框號
訪問控制信息。用來描敘此頁可以進行哪些操作，是否可寫？是否包含執行代碼?
虛擬頁面框號是為頁表中的偏移。虛擬頁面框號5對應表中的第6個單元（0是第一個）。
為了將虛擬地址轉換為物理地址，處理器首先必須得到虛擬地址頁面框號及頁內偏移。一般將頁面大小設為2的次冪。將圖3.1中的頁面大小設為0x2000字節（十進制為8192）並且在進程Y的虛擬地址空間中某個地址為0x2194，則處理器將其轉換為虛擬頁面框號1及頁內偏移0x194。
處理器使用虛擬頁面框號為索引來訪問處理器頁表，檢索頁表入口。如果在此位置的頁表入口有效，則處理器將從此入口中得到物理頁面框號。如果此入口無效，則意味著處理器存取的是虛擬內存中一個不存在的區域。在這種情況下，處理器是不能進行地址轉換的，它必須將控制傳遞給操作系統來完成這個工作。
某個進程試圖訪問處理器無法進行有效地址轉換的虛擬地址時，處理器如何將控制傳遞到操作系統依賴於具體的處理器。通常的做法是：處理器引發一個頁面失效錯而陷入操作系統核心，這樣操作系統將得到有關無效虛擬地址的信息以及發生頁面錯誤的原因。
再以圖3.1為例，進程Y的虛擬頁面框號1被映射到系統物理頁面框號4，則再物理內存中的起始位置為 0x8000(4 * 0x2000)。加上0x194字節偏移則得到最終的物理地址0x8194。
通過將虛擬地址映射到物理地址，虛擬內存可以以任何順序映射到系統物理頁面。例如，在圖3.1中，進程X的虛擬頁面框號0被映射到物理頁面框號1而虛擬頁面框號7被映射到物理頁面框號0，雖然後者的虛擬頁面框號要高於前者。這樣虛擬內存技術帶來了有趣的結果：虛擬內存中的頁面無須在物理內存保持特定順序。
3.1.1 請求換頁
在物理內存比虛擬內存小得多的系統中，操作系統必須提高物理內存的使用效率。節省物理內存的一種方法是僅加載那些正在被執行程序使用的虛擬頁面。比如說，某個數據庫程序可能要對某個數據庫進行查詢操作，此時並不是數據庫的所有內容都要加載到內存中去，而只加載那些要用的部分。如果此數據庫查詢是一個搜索查詢而無須對數據庫進行添加記錄操作，則加載添加記錄的代碼是毫無意義的。這種僅將要訪問的虛擬頁面載入的技術叫請求換頁。
當進程試圖訪問當前不在內存中的虛擬地址時，處理器在頁表中無法找到所引用地址的入口。在圖3.1中，對於虛擬頁面框號2，進程X的頁表中沒有入口，這樣當進程X試圖訪問虛擬頁面框號2內容時，處理器不能將此地址轉換成物理地址。這時處理器通知操作系統有頁面錯誤發生。
如果發生頁面錯的虛擬地址是無效的，則表明進程在試圖訪問一個不存在的虛擬地址。這可能是應用程序出錯而引起的，例如它試圖對內存進行一個隨機的寫操作。此時操作系統將終止此應用的運行以保護系統中其他進程不受此出錯進程的影響。
如果出錯虛擬地址是有效的，但是它指向的頁面當前不在內存中，則操作系統必須將此頁面從磁盤映象中讀入到內存中來。由於訪盤時間較長，進程必須等待一段時間直到頁面被取出來。如果系統中還存在其他進程，操作系統就會在讀取頁面過程中的等待過程中選擇其中之一來運行。讀取回來的頁面將被放在一個空閒的物理頁面框中，同時此進程的頁表中將添加對應此虛擬頁面框號的入口。最後進程將從發生頁面錯誤的地方重新開始運行。此時整個虛擬內存訪問過程告一段落，處理器又可以繼續進行虛擬地址到物理地址轉換，而進程也得以繼續運行。
Linux使用請求換頁將可執行映象加載到進程的虛擬內存中。當命令執行時，可執行的命令文件被打開，同時其內容被映射到進程的虛擬內存。這些操作是通過修改描敘進程內存映象的數據結構來完成的，此過程稱為內存映射。然而只有映象的起始部分被調入物理內存，其余部分仍然留在磁盤上。當映象執行時，它會產生頁面錯誤，這樣Linux將決定將磁盤上哪些部分調入內存繼續執行。
3.1.2 交換
如果進程需要把一個虛擬頁面調入物理內存而正好系統中沒有空閒的物理頁面，操作系統必須丟棄位於物理內存中的某些頁面來為之騰出空間。
如果那些從物理內存中丟棄出來的頁面來自於磁盤上的可執行文件或者數據文件，並且沒有修改過則不需要保存那些頁面。當進程再次需要此頁面時，直接從可執行文件或者數據文件中讀出。
但是如果頁面被修改過，則操作系統必須保留頁面的內容以備再次訪問。這種頁面被稱為dirty頁面， 當從內存中移出來時，它們必須保存在叫做交換文件的特殊文件中。相對於處理器和物理內存的速度，訪問交換文件的速度是非常緩慢的，操作系統必須在將這些dirty頁面寫入磁盤和將其繼續保留在內存中做出選擇。
選擇丟棄頁面的算法經常需要判斷哪些頁面要丟棄或者交換，如果交換算法效率很低，則會發生"顛簸"現象。在這種情況下，頁面不斷的被寫入磁盤又從磁盤中讀回來，這樣一來操作系統就無法進行其他任何工作。以圖3.1為例，如果物理頁面框號1被頻繁使用，則頁面丟棄算法將其作為交換到硬盤的侯選者是不恰當的。一個進程當前經常使用的頁面集合叫做工作集。高效的交換策略能夠確保所有進程的工作集保存在物理內存中。
Linux使用最近最少使用（LRU）頁面衰老算法來公平地選擇將要從系統中拋棄的頁面。這種策略為系統中的每個頁面設置一個年齡，它隨頁面訪問次數而變化。頁面被訪問的次數越多則頁面年齡越年輕；相反則越衰老。年齡較老的頁面是待交換頁面的最佳侯選者。
3.1.3 共享虛擬內存
虛擬內存讓多個進程之間可以方便地共享內存。所有的內存訪問都是通過每個進程自身的頁表進行。對於兩個共享同一物理頁面的進程，在各自的頁表中必須包含有指向這一物理頁面框號的頁表入口。
圖3.1中兩個進程共享物理頁面框號4。對進程X來說其對應的虛擬頁面框號為4而進程Y的為6。這個有趣的現象說明：共享物理頁面的進程對應此頁面的虛擬內存位置可以不同。
3.1.4 物理與虛擬尋址模式
操作系統自身也運行在虛擬內存中的意義不大。如果操作系統被迫維護自身的頁表那將是一個令人惡心的方案。多數通用處理器同時支持物理尋址和虛擬尋址模式。物理尋址模式無需頁表的參與且處理器不會進行任何地址轉換。Linux核心直接運行在物理地址空間上。
Alpha AXP處理器沒有特殊的物理尋址模式。它將內存空間劃分為幾個區域並將其中兩個指定為物理映射地址。核心地址空間被稱為KSEG地址空間，它位於地址0xfffffc0000000000以上區域。為了執行位於KSEG的核心代碼或訪問那裡的數據，代碼必須在核心模式下執行。Alpha上的Linux核心從地址0xfffffc0000310000開始執行.
3.1.5 訪問控制
頁表入口包含了訪問控制信息。由於處理器已經將頁表入口作為虛擬地址到物理地址的映射，那麼可以很方便地使用訪問控制信息來判斷處理器是否在以其應有的方式來訪問內存。
諸多因素使得有必要嚴格控制對內存區域的訪問。有些內存，如包含執行代碼的部分，顯然應該是只讀的，操作系統決不能允許進程對此區域的寫操作。相反包含數據的頁面應該是可寫的， 但是去執行這段數據肯定將導致錯誤發生。多數處理器至少有兩種執行方式：核心態與用戶態。任何人都不會允許在用戶態下執行核心代碼或者在用戶態下修改核心數據結構。
圖3.2 Alpha AXP頁表入口
頁表入口中的訪問控制信息是處理器相關的；圖3.2是Alpha AXP處理器的PTE(Page Table Entry)。這些位域的含義如下：
V
有效，如果此位置位，表明此PTE有效
FOE
“執行時失效”，無論合時只要執行包含在此頁面中的指令，處理器都將報告頁面錯誤並將控制傳遞
FOW
“寫時失效”, 除了頁面錯誤發生在對此頁面的寫時，其他與上相同。
FOR
“讀時失效”，除了頁面錯誤發生在對此頁面的讀時，其他與上相同。
ASM
地址空間匹配。被操作系統用於清洗轉換緩沖中的某些入口。
KRE
運行在核心模式下的代碼可以讀此頁面。
URE
運行在用戶模式下的代碼可以讀此頁面。
GH
將整個塊映射到單個而不是多個轉換緩沖時的隱含粒度。
KWE
運行在核心模式下的代碼可以寫此頁面。
UWE
運行在用戶模式下的代碼可以寫此頁面。
page frame number
對於V位置位的PTE，此域包含了對應此PTE的物理頁面框號；對於無效PTE，此域不為0，它包含了頁面在交換文件中位置的信息。
以下兩位由Linux定義並使用。
_PAGE_DIRTY
如果置位，此頁面要被寫入交換文件。
_PAGE_AccessED
Linux用它表示頁面已經被訪問過。
3.2 高速緩沖
如果用上述理論模型來實現一個系統，它可能可以工作，但效率不會高。操作系統設計者和處理器設計者都在努力以提高系統的性能。除了制造更快的CPU和內存外，最好的辦法是在高速緩沖中維護有用信息和數據以加快某些操作。Linux使用了許多與高速緩沖相關的內存管理策略。
Buffer Cache
這個buffer cache中包含了被塊設備驅動使用的數據緩沖。
這些緩沖的單元的大小一般固定(例如說512字節)並且包含從塊設備讀出或者寫入的信息塊。塊設備是僅能夠以固定大小塊進行讀寫操作的設備。所有的硬盤都是塊設備。
利用設備標志符和所需塊號作索引可以在buffer cache中迅速地找到數據。塊設備只能夠通過buffer cache來存取。如果數據在buffer cache中可以找到則無需從物理塊設備(如硬盤)中讀取，這樣可以加速訪問。
Page Cache
用來加速硬盤上可執行映象文件與數據文件的存取。
它每次緩沖一個頁面的文件內容。頁面從磁盤上讀入內存後緩存在page cache中。
Swap Cache
只有修改過的頁面存儲在交換文件中。
只要這些頁面在寫入到交換文件後沒有被修改，則下次此頁面被交換出內存時，就不必再進行更新寫操作，這些頁面都可以簡單的丟棄。在交換頻繁發生的系統中，Swap Cache可以省下很多不必要且耗時的磁盤操作。
Hardware Caches
一個常見的hardware cache是處理器中的頁表入口cache。處理器不總是直接讀取頁表而是在需要時緩存頁面的轉換。這種cache又叫做轉換旁視緩沖(Translation Look-aside Buffers)，它包含系統中一個或多個處理器的頁表入口的緩沖拷貝。
當發出對虛擬地址的引用時，處理器試圖找到相匹配的TLB入口。如果找到則直接將虛擬地址轉換成物理地址並對數據進行處理。如果沒有找到則向操作系統尋求幫助。處理器將向操作系統發出TLB失配信號，它使用一個特定的系統機制來將此異常通知操作系統。操作系統則為此地址匹配對產生新的TLB入口。當操作系統清除此異常時，處理器將再次進行虛擬地址轉換。由於此時在TLB中已經有相應的入口，這次操作將成功。
使用高速緩存的缺點在於Linux必須消耗更多的時間和空間來維護這些緩存，並且當緩存系統崩潰時系統也將崩潰。
3.3 Linux 頁表
圖3.3 Linux的三級頁表結構
Linux總是假定處理器有三級頁表。每個頁表通過所包含的下級頁表的頁面框號來訪問。圖3.3給出了虛擬地址是如何分割成多個域的，每個域提供了某個指定頁表的偏移。為了將虛擬地址轉換成物理地址，處理器必須得到每個域的值。這個過程將持續三次直到對應於虛擬地址的物理頁面框號被找到。最後再使用虛擬地址中的最後一個域，得到了頁面中數據的地址。
為了實現跨平台運行，Linux提供了一系列轉換宏使得核心可以訪問特定進程的頁表。這樣核心無需知道 頁表入口的結構以及它們的排列方式。
這種策略相當成功，無論在具有三級頁表結構的Alpha AXP還是兩級頁表的Intel X86處理器中，Linux總是使 用相同的頁表操縱代碼。
3.4 頁面分配與回收
對系統中物理頁面的請求十分頻繁。例如當一個可執行映象被調入內存時，操作系統必須為其分配頁面。當映象執行完畢和卸載時這些頁面必須被釋放。物理頁面的另一個用途是存儲頁表這些核心數據結構。虛擬內存子系統中負責頁面分配與回收的數據結構和機制可能用處最大。
系統中所有的物理頁面用包含mem_map_t結構的鏈表mem_map來描敘，這些結構在系統啟動時初始化。每個 mem_map_t描敘了一個物理頁面。其中與內存管理相關的重要域如下：
count
記錄使用此頁面的用戶個數。當這個頁面在多個進程之間共享時，它的值大於1。
age
此域描敘頁面的年齡，用於選擇將適當的頁面拋棄或者置換出內存時。
map_nr
記錄本mem_map_t描敘的物理頁面框號。
頁面分配代碼使用free_area數組來尋找和釋放頁面，此機制負責整個緩沖管理。另外此代碼與處理器使用的頁面大小和物理分頁機制無關。
free_area中的每個元素都包含頁面塊的信息。數組中第一個元素描敘1個頁面，第二個表示2個頁面大小的塊而接下來表示4個頁面大小的塊，總之都是2的次冪倍大小。list域表示一個隊列頭，它包含指向mem_map數組中page數據結構的指針。所有的空閒頁面都在此隊列中。map域是指向某個特定頁面尺寸的頁面組分配情況位圖的指針。當頁面的第N塊空閒時，位圖的第N位被置位。
圖free-area-figure畫出了free_area結構。第一個元素有個自由頁面（頁面框號0），第二個元素有4個頁面大小的2個自由塊，前一個從頁面框號4開始而後一個從頁面框號56開始。
3.4.1 頁面分配
Linux使用Buddy算法來有效的分配與回收頁面塊。頁面分配代碼每次分配包含一個或者多個物理頁面的內存塊。頁面以2的次冪的內存塊來分配。這意味著它可以分配1個、2個和4個頁面的塊。只要系統中有足夠的空閒頁面來滿足這個要求(nr_free_pages > min_free_page)，內存分配代碼將在free_area中尋找一個與請求大小相同的空閒塊。free_area中的每個元素保存著一個反映這樣大小的已分配與空閒頁面 的位圖。例如，free_area數組中第二個元素指向一個反映大小為四個頁面的內存塊分配情況的內存映象。
分配算法首先搜尋滿足請求大小的頁面。它從free_area數據結構的list域著手沿鏈來搜索空閒頁面。如果沒有這樣請求大小的空閒頁面，則它搜索兩倍於請求大小的內存塊。這個過程一直將持續到free_area 被搜索完或找到滿足要求的內存塊為止。如果找到的頁面塊大於請求的塊則對其進行分割以使其大小與請求塊匹配。由於塊大小都是2的次冪所以分割過程十分簡單。空閒塊被連進相應的隊列而這個頁面塊被分配給調用者。
圖3.4 free_area數據結構
在圖3.4中，當系統中有大小為兩個頁面塊的請求發出時，第一個4頁面大小的內存塊（從頁面框號4開始）將分成兩個2頁面大小的塊。前一個，從頁面框號4開始的，將分配出去返回給請求者，而後一個，從頁面框號6開始，將被添加到free_area數組中表示兩個頁面大小的空閒塊的元素1中。
3.4.2 頁面回收
將大的頁面塊打碎進行分配將增加系統中零碎空閒頁面塊的數目。頁面回收代碼在適當時機下要將這些頁面結合起來形成單一大頁面塊。事實上頁面塊大小決定了頁面重新組合的難易程度。
當頁面塊被釋放時，代碼將檢查是否有相同大小的相鄰或者buddy內存塊存在。如果有，則將它們結合起來形成一個大小為原來兩倍的新空閒塊。每次結合完之後，代碼還要檢查是否可以繼續合並成更大的頁面。最佳情況是系統的空閒頁面塊將和允許分配的最大內存一樣大。
在圖3.4中，如果釋放頁面框號1，它將和空閒頁面框號0結合作為大小為2個頁面的空閒塊排入free_area的第一個元素中。
3.5 內存映射
映象執行時，可執行映象的內容將被調入進程虛擬地址空間中。可執行映象使用的共享庫同樣如此。然而可執行文件實際上並沒有調入物理內存，而是僅僅連接到進程的虛擬內存。當程序的其他部分運行時引用到這部分時才把它們從磁盤上調入內存。將映象連接到進程虛擬地址空間的過程稱為內存映射。
圖3.5 虛擬內存區域
每個進程的虛擬內存用一個mm_struct來表示。它包含當前執行的映象（如BASH）以及指向vm_area_struct 的大量指針。每個vm_area_struct數據結構描敘了虛擬內存的起始與結束位置，進程對此內存區域的存取權限以及一組內存操作函數。這些函數都是Linux在操縱虛擬內存區域時必須用到的子程序。其中一個負責處理進程試圖訪問不在當前物理內存中的虛擬內存(通過頁面失效)的情況。此函數叫nopage。它用在Linux試圖將可執行映象的頁面調入內存時。
可執行映象映射到進程虛擬地址時將產生一組相應的vm_area_struct數據結構。每個vm_area_struct數據結構表示可執行映象的一部分：可執行代碼、初始化數據(變量)、未初始化數據等等。Linux支持許多標准的虛擬內存操作函數，創建vm_area_struct數據結構時有一組相應的虛擬內存操作函數與之對應。
3.6 請求換頁
當可執行映象到進程虛擬地址空間的映射完成後，它就可以開始運行了。由於只有很少部分的映象調入內存，所以很快就會發生對不在物理內存中的虛擬內存區域的訪問。當進程訪問無有效頁表入口的虛擬地址時，處理器將向Linux報告一個頁面錯誤。
頁面錯誤帶有失效發生的虛擬地址及引發失效的訪存方式。Linux必須找到表示此區域的vm_area_struct結構。對vm_area_struct數據結構的搜尋速度決定了處理頁面錯誤的效率，而所有vm_area_struct結構是通過一種AVL(Adelson-Velskii and Landis) 樹結構連在一起的。如果無法找到vm_area_struct與此失效虛擬地址的對應關系，則系統認為此進程訪問了非法虛擬地址。這時Linux將向進程發送SIGSEGV信號，如果進程沒有此信號的處理過程則終止運行。
如果找到此對應關系，Linux接下來檢查引起該頁面錯誤的訪存類型。如果進程以非法方式訪問內存，比如對不可寫區域進行寫操作，系統將產生內存錯誤的信號。
如果Linux認為頁面出錯是合法的，那麼它需要對這種情況進行處理。
首先Linux必須區分位於交換文件中的頁面和那些位於磁盤上的可執行映象。Alpha AXP的頁表中有可能存在有效位沒有設置但是在PFN域中有非0值的頁表入口。在這種情況下，PFN域指示的是此頁面在交換文件中的位置。如何處理交換文件中的頁面將在下章討論。
不是所有的vm_area_struct數據結構都有一組虛擬內存操作函數，它們有的甚至沒有nopage函數。這是因為 Linux通過分配新的物理頁面並為其創建有效的頁表入口來修正這次訪問。如果這個內存區域存在nopage操作函數，Linux將調用它。
一般Linux nopage函數被用來處理內存映射可執行映象，同時它使用頁面cache將請求的頁面調入物理內存中去。
當請求的頁面調入物理內存時，處理器頁表也必須更新。更新這些入口必須進行相關硬件操作，特別是處理器使用TLB時。這樣當頁面失效被處理完畢後，進程將從發生失效虛擬內存訪問的位置重新開始運行。
3.7 Linux頁面cache
圖3.6 Linux頁面Cache
Linux使用頁面cache的目的是加快對磁盤上文件的訪問。內存映射文件以每次一頁的方式讀出並將這些頁面存儲在頁面cache中。圖3.6表明頁面cache由page_hash_table，指向mem_map_t數據結構的指針數組組成。
Linux中的每個文件通過一個VFS inode（在文件系統一章中講敘）數據結構來標識並且每個VFS inode都是唯一的，它可以並僅可以描敘一個文件。頁表的索引從文件的VFS inode和文件的偏移中派生出來。
從一個內存映射文件中讀出頁面，例如產生換頁請求時要將頁面讀回內存中，系統嘗試從頁面cache來讀出。如果頁面在cache中，則返回頁面失效處理過程一個指向mem_map_t數據結構；否則此頁面將從包含映象的文件系統中讀入內存並為之分配物理頁面。
在映象的讀入與執行過程中，頁面cache不斷增長。當不再需要某個頁面時，即不再被任何進程使用時，它將被從頁面cache中刪除。
3.8 換出與丟棄頁面
當系統中物理內存減少時，Linux內存管理子系統必須釋放物理頁面。這個任務由核心交換後台進程(kswapd )來完成。
核心交換後台進程是一種特殊的核心線程。它是沒有虛擬內存的進程，在物理地址空間上以核心態運行。核心交換後台進程的名字容易使人誤解，其實它完成的工作比僅僅將頁面交換到系統的交換文件中要多得多。其目標是保證系統中有足夠的空閒頁面來維持內存管理系統運行效率。
此進程由核心的init進程在系統啟動時運行，被核心交換定時器周期性的調用。
當定時器到時後，交換後台進程將檢查系統中的空閒頁面數是否太少。它使用兩個變量：free_pages_high 和free_page_low來判斷是否該釋放一些頁面。只要系統中的空閒頁面數大於free_pages_high，核心交換後台進程不做任何工作；它將睡眠到下一次定時器到時。在檢查中，核心交換後台進程將當前被寫到交換文件中的頁面數也計算在內，它使用nr_async_pages來記錄這個數值；當有頁面被排入准備寫到交換文件隊列中時，它將遞增一次，同時當寫入操作完成後遞減一次。如果系統中的空閒頁面數在free_pages_high甚至 free_pages_low以下時，核心交換後台進程將通過三個途徑來減少系統中使用的物理頁面的個數：
減少緩沖與頁面cache的大小，
將系統V類型的內存頁面交換出去，
換出或者丟棄頁面。
如果系統中空閒頁面數低於free_pages_low，核心交換後台進程將在下次運行之前釋放6個頁面。否則它只釋放3個。以上三種方法將依次使用直到系統釋放出足夠的空閒頁面。當核心交換後台進程試圖釋放物理頁面時它將記錄使用的最後一種方法。下一次它會首先運行上次最後成功的算法。
當釋放出足夠頁面後，核心交換後台進程將再次睡眠到下次定時器到時。如果導致核心交換後台進程釋放頁面的原因是系統中的空閒頁面數小於free_pages_low，則它只睡眠平時的一半時間。一旦空閒頁面數大於 free_pages_low則核心交換進程的睡眠時間又會延長。
3.8.1 減少Page Cache和Buffer Cache的大小
Page Cache和Buffer cache中的頁面將被優先考慮釋放到free_area數組中。Page Cache中包含的是內存映射文件的頁面，其中有些可能是不必要的，它們浪費了系統的內存。而Buffer Cache中包含的是從物理設備中讀寫的緩沖數據，有些可能也是不必要的。當系統中物理頁面開始耗盡時，從這些cache中丟棄頁面比較簡單（它不需要象從內存中交換一樣，無須對物理設備進行寫操作）。除了會使對物理設備及內存映射文件的訪問速度降低外，頁面丟棄策略沒有太多的副作用。如果策略得當，則所有進程的損失相同。
