第十章記憶體管理實作

1作業系統第十章記憶體管理實作2記憶體管理實作硬體上的支援不可或缺Linux使用Intel的分頁式分段功能來轉換邏輯位址與實體位址跨平台：讓Linux能在其他非Intel平台上執行，記憶體管理模型須不受處理器差異影響主記憶體分配：核心：用來儲存核心程式碼與靜態核心資料結構動態記憶體：其他的部分稱之。可動態給使用者行程或核心使用動態記憶體的管理影響系統效能甚巨3第十章記憶體管理實作記憶體定址硬體分段支援Linux上的分段硬體分頁支援Linux上的分頁頁框管理記憶體區域管理摘要4記憶體定址（1）Intel80x86提供分頁式分段的功能

3種記憶體定址的方式：實體位址：記憶體中實際的位址線性位址：一塊4GB大小的虛擬空間；系統利用此空間作分段與分頁透過邏輯位址：可選擇到線性位址空間中一個分段裡的任一個位元組透過分段單元的硬體電路：把邏輯位址轉換成線性位址若轉換成功，再透過分頁單元把線性位址轉換成實體位址5邏輯位址轉換分段單元分頁單元線性位址邏輯位址實體位址6記憶體定址（2）Intel架構下，記憶體架構分為2部分分段：將程式分割成程式碼、資料與堆疊等模組，使多個工作互不干擾，在同一個處理器上執行分頁：需求分頁，虛擬記憶體分段的做法：將程式的分段劃分在線性位址空間裡分段描述器：記錄此分段起始線性位址及分段的大小可以找到分段的線性位址；避免存取超出此分段以外的空間7記憶體定址（3）邏輯位址由分段選擇器和段偏移組成透過分段選擇器，可從描述器表（如GDT）中找到此分段的分段描述器

得到分段的起始線性位址配合邏輯位址中的段偏移，就能定址到此分段在線性位址空間的位址分頁的做法：將線性位址空間中的分段再細分成許多分頁這些分頁可存放在記憶體或磁碟內作業系統透過分頁目錄和分頁表格，可得分頁在實體記憶體或磁碟中的實際位址8硬體分段支援（1）Intel微處理器以真實模式與保護模式進行位址轉換保護模式下，Intel架構提供4G位元組的實體位址空間（因處理器的位址匯流排為32位元）真實模式下的硬體分段沒有作用保護模式下的硬體分段支援分段暫存器分段描述器分段選擇器9硬體分段支援（2）分段暫存器：儲存分段選擇器的內容，計有6個，分別為cs、ss、ds、es、fs與gscs暫存器：指向一個包含程式碼的分段

ss暫存器：指向目前的程式堆疊分段

ds暫存器：指向靜態或是外部資料分段其他3分段暫存器可指向任何分段cs暫存器另一重要功能：包含2個CPL位元（定義CPU目前權限等級）若CPL數值為0，表示最高等級若CPL數值為3，表示最低等級以Linux系統為例，利用CPL的數值為0或3來表示目前是處於核心模式或使用者模式10硬體分段支援（3）分段描述器：每個分段都用一個8位元組的分段描述器來描述該分段的特徵，如分段大小、分段所在位置、存取控制權及狀態等資訊儲存在GDT（全域描述器表）或LDT（區域描述器表）中作業系統通常只定義一個GDT，但每個行程都有各自的LDT主記憶體中，GDT的位址會存放在gdtr暫存器；目前正在使用的LDT的位址存在ldtr暫存器11分段描述器格式6362616059585756555453525150494847464544434241403938373635343332313029282726252423222120191817161514131211100123456789LIMIT(0-15)BASE(0-15)BASE(16-23)TYPESDPL1BASE(24-31)GD/B0AVLLIMIT(16-19)12硬體分段支援（4）分段描述器中的各項欄位：G旗標：設定分段的單位大小當G旗標設定為1，分段單位為4K位元組；否則分段單位為1位元組LIMIT欄位：描述分段的長度CPU把分段描述器中第0到15位元與第48到51位元合併成20個位元的分段界限，且依據G旗標的設定形成不同的分段界限範圍如果G旗標設定為0，分段大小會介於1B（位元組）到1MB；否則分段大小會介於4KB到4GBBASE欄位：描述分段的基底位址CPU把分段描述器中的第16到39位元與第56到63位元共計32位元合併成分段開始的線性位址S旗標：若此旗標是0，表示此分段用來儲存核心資料結構的系統分段；否則代表它是一般的程式碼或資料分段13硬體分段支援（5）TYPE欄位：表示分段的型態與存取權限DPL（描述器權限）欄位：設定存取該分段的權限範圍由0到3，數值為0時表示權限最大D/B旗標：表示分段包含程式碼或資料兩者定義上不同，設定為1時表示段偏移的位址為32位元，否則只有16位元P旗標：設定為1時表示該分段在主記憶體中第53個位元：是一個保留位元，通常被設定為0AVL欄位：可由作業系統自行定義使用；Linux沒有使用此欄位14硬體分段支援（6）分段選擇器：加速邏輯位址與線性位址間的轉換額外特殊的暫存器都包含8位元組大小的分段描述器當分段選擇器的內容載入到分段暫存器中，該對應的分段描述器也從記憶體載入到對應的特殊暫存器邏輯位址轉換可不透過GDT或LDT；CPU直接存取非程式控制暫存器的內容只有在分段暫存器的內容改變時才需對GDT或LDT作讀取15分段選擇器與分段描述器分段選擇器分段描述器分段暫存器分段描述器非程式控制暫存器分段描述器表16硬體分段支援（7）分段選擇器的各項欄位：分段索引：13位元當成描述器表的索引TI旗標：指示分段描述器在GDT（TI為0）或在LDT（TI為1）中RPL（要求者權限）欄位：2位元的欄位，指示CPU目前的權限等級（要求CPU作記憶體存取的使用者權限）欲得分段描述器在GDT或LDT中的相對位址

利用分段選擇器中最高13個位元的數值乘上817硬體分段支援（8）把邏輯位址轉成線性位址的步驟：檢查TI欄位，確定對應的分段描述器在GDT或LDT中索引欄位的數值乘以8再加上gdtr或ldtr中的數值

分段描述器的位址把邏輯位址的段偏移加上分段描述器中的基底位址欄位，就可以得到線性位址當分段暫存器內容改變時才需要執行前面步驟18分段選擇器與邏輯位址轉換gdtr或ldtr

＋＋線性位址3233343531分段索引(35-47)TIRPL段偏移(0-31)47邏輯位址分段選擇器分段描述器gdt或ldt0819Linux上的分段（1）Linux中採用分頁式分段之原因：當行程共用相同線性位址，記憶體管理變方便，易達分段共用Linux在設計上想適用於目前各種常用架構

可將所有的分段描述器都儲存在GDT中Linux中的GDT是以gdt_table陣列來實作，用變數gdt指向該陣列核心中不使用區域描述器表（LDT），但允許行程透過系統呼叫建立LDTLinux下使用多個分段，如核心程式碼分段、核心資料分段、使用者程式碼分段、使用者資料分段、TSS分段、與LDT分段等20Linux上的分段（2）TSS分段：存放每個行程暫存器與I/O位元映射的內容分段大小的分段界限欄位設定為0xebTYPE欄位設定為9或11使用者模式下不允許行程存取TSS分段，故DPL設為0Linux核心2.4中，所有行程的TSS分段不存在，改由指向存放原先每個行程TSS分段內容的指標來代替21Linux上的分段（3）LDT分段：儲存在變數default_ldt中，預設是給所有的行程所共用每個行程都有自己的分段描述器，指到預設的共用LDT分段，分段裡的基底位址欄位設定為default_ldt的位址，分段大小的分段界限設定為7若行程需要一個真正的LDT，會建立一個長度為4096位元組的分段，該分段最多包含511個分段描述器，該行程所屬的預設LDT分段描述器則被放置到GDT中22Linux上的分段（4）對每個行程而言，GDT可以放入TSS分段或LDT分段2種不同的分段描述器GDT中最大可儲存的欄位數目為12+2×NR_TASKS（NR_TASKS：系統裡行程最大的數目）行程被建立時TSS與LDT分段描述器被加到GDT中核心初始化時trap_init()函式利用set_tss_desc(0,&init_task.tss)把第一個行程的TSS分段描述器加到GDT中第一個行程再利用copy_thread()建立其他子行程，該函式喚起clone()與fork()的系統呼叫，也執行set_tss_desc(nr,&(task[nr]->tss))函式設定新行程的TSS分段23Linux上的分段（5）CPU的特權等級代表一個行程在使用者模式或是核心模式目前的特權等級可由儲存在cs暫存器之分段選擇器內的RPL欄位決定當目前的特權等級改變，所對應的分段暫存器也必須修改

ss暫存器中也相同：當系統從使用者模式切換到核心模式時，必須確定ss暫存器包含核心資料區段的分段選擇器24硬體分頁支援（1）分頁單元：把線性位址轉成實體位址檢查存取的類型是否與線性位址提供的存取型態不一致若記憶體存取不合法

分頁錯誤視主記憶體為許多固定長度的頁框集合（頁框又稱為實體頁）每個頁框包含一個分頁分頁代表一個區塊的資料，可儲存在頁框中或磁碟中25硬體分頁支援（2）分頁表：將線性位址轉換實體位址的資料結構儲存在主記憶體中分頁單元啟動時，核心會初始化分頁表Intel處理器中，藉由設定cr0暫存器中的PG旗標啟動分頁功能當PG數值未設定（其值為0），表示線性位址會直接被當成實體位址解譯（分頁功能未啟動）26硬體分頁支援（3）分頁：Intel處理器中的分頁單元可處理4KB大小的分頁

32位元的線性位址分成3個欄位：最高10個位元為目錄；中間10個位元為表格；最低的12個位元為頁偏移線性位址轉換有兩步驟，每個步驟都需要一個轉換表格，第一：分頁目錄，第二：分頁表分頁目錄：起始實體位址儲存在cr3行程暫存器目錄欄位：決定參考分頁目錄中的哪一個項目表格欄位：決定要參考分頁表中的哪一個項目，包含某個頁框的實體位址頁偏移欄位：決定在頁框中的相對位置因為頁偏移有12個位元，故每個分頁可含4096個位元組27Intel80x86下的分頁法＋cr3＋＋分頁分頁表分頁目錄目錄表格頁偏移線性位址0111221223128硬體分頁支援（4）目錄與表格欄位都使用10個位元，故分頁目錄與分頁表可含1024個項目一個分頁目錄可以定址1024×1024×4096=232

記憶體儲存格分頁目錄與分頁表具有相同的結構，包含下列欄位：出現旗標：旗標為1：表示此分頁已載入到主記憶體旗標為0：表示此分頁不在主記憶體中存取旗標：分頁單元存取過某頁框後，存取旗標會被設定分頁單元不能對此旗標作重設，只能透過作業系統29硬體分頁支援（5）修改旗標：只在分頁表中使用當頁框被寫入，會設定此旗標；在作業系統選擇某頁進行替換時，會使用到此旗標分頁單元不能對此旗標作重設，只能透過作業系統讀寫旗標：指定分頁或分頁表的存取權限（讀取／寫入或讀取）權限旗標：指定存取分頁或分頁表所需的權限等級30硬體分頁支援（6）PCD和PWT旗標：用在硬體快取PCD指示存取頁框中的資料時是否使用快取PWT指示用何種策略將資料分頁寫入頁框策略：寫回或寫穿當PCD與PWT都設為0，表示快取啟動且採用寫回策略分頁大小旗標：只在分頁目錄中使用此旗標設為1：在分頁目錄中參考到4MB大小的分頁31硬體分頁支援（7）延伸分頁：Intel從Pentium處理器開始支援允許頁框的大小為4KB或4MB延伸分頁的模式下，分頁單元把32位元的線性位址分成兩欄位最高的10個位元為目錄，剩餘22個位元為頁偏移使延伸分頁與一般分頁共存，可設定cr4暫存器中的PSE旗標使用大塊區域的線性位址對應到實體位址核心不需要再透過中間層的分頁表，可節省中間分頁表的空間；但可能增加內部斷裂32延伸分頁0＋cr3＋分頁目錄分頁目錄頁偏移線性位址2122314MB的分頁33硬體分頁支援（8）硬體保護機制：

Intel處理器中允許分段利用權限旗標來設定4種存取權限等級只有2種用在分頁與分頁表中若權限旗標為1：該頁可隨時被存取若為0，只有在CPL小於3的權限下才能存取分段有3種存取權限（讀取、寫入與執行）分頁只有2種存取權限（讀取與寫入）假設分頁目錄或分頁表裡的讀寫旗標為0，表示對應的分頁表或分頁只能讀取；否則可讀取或寫入34硬體分頁支援（9）三層式分頁：32位元的架構，採用兩層式分頁法64位元的架構，採用三層式分頁分頁大小為16KB，可定址214

個位址頁偏移欄位用14個位元，剩餘50個位元分配給目錄欄位與表格欄位；不該浪費如此大空間儲存分頁目錄與分頁表Compaq’sAlpha處理器

64位元的架構，採用三層式分頁每個頁框大小為8KB，頁偏移欄位為13個位元系統只用最低的43個位元，剩餘的21個較高位元被設為0剩下的30個位元可平均分配成三個10位元的欄位（全域目錄、中間目錄與表格）35Linux中分頁的模式＋cr3＋＋＋分頁全域目錄全域目錄中間目錄表格頁偏移線性位址分頁中間目錄分頁表分頁36Linux上的分頁（1）Linux採用三層式分頁全域分頁目錄、中間分頁目錄與分頁表也適用64位元的架構全域分頁目錄：包含多個中間分頁目錄的位址中間分頁目錄：包含多個分頁表的位址分頁表中的項目均會指到一個頁框故線性位址被分成4個欄位每個欄位使用多少位元，必須視電腦的硬體架構而定37Linux上的分頁（2）行程擁有各自的全域分頁目錄與數個分頁表行程發生內文切換，核心把cr3暫存器的內容儲存到TSS分段中載入另一個TSS分段的內容到cr3中當新的行程恢復執行，分頁單元才能指到正確的分頁表Linux應用在32位元的架構上，不使用中間分頁目錄，但仍保留它

使得相同的程式碼可以在32位元或64位元的架構下執行核心設計把中間分頁目錄的大小設為1，使記憶體模型設計與處理器無關38Linux上的分頁（3）分頁表的處理：Linux核心原始碼中的asm/page.h與asm/pgtable.h中定義讀取及修改分頁表與分頁目錄時所需的資料結構、函式與巨集，供分頁表進行處理，如型態轉換、讀取或修改分頁表中的項目、查詢分頁表中某項目的旗標狀態或數值、從分頁表的項目中取出分頁位址等全域分頁目錄、中間分頁目錄與分頁表內的項目都是32位元的資料型態還有一個32位元的資料型態用來表示某個單一項目的保護旗標39Linux上的分頁（4）分頁表會儲存在頁框中；每個行程會使用多個分頁表頁框的分配與釋放耗時當核心用完一個分頁表後，會把分頁表所使用的頁框加入到一個軟體快取中當核心下次要建立新的分頁表時，直接由從軟體快取中取得一個頁框只在軟體快取為空，才向系統要求配置一個新頁框40Linux上的分頁（5）分頁表快取採用是軟體快取，沒有硬體空間的限制核心必須實作一機制來限定快取所使用的空間，並設定快取使用的上限與下限在系統閒置、或核心釋放一個行程所擁有的分頁表時，系統會檢查每個快取所使用的空間是否超過上限，若超過便會釋放快取中的頁框，直到快取所使用的空間達下限為止41Linux上的分頁（6）保留頁框：核心程式碼與資料結構儲存於此不能被動態地分配或置換到磁碟中Linux核心會被安裝在實體記憶體位址為0x00100000處核心所需要的頁框總數會少於2MB核心不載入到0x00100000之前的記憶體空間之因？考慮個人電腦結構上的特性：BIOS使用第0個頁框來儲存系統硬體上的設定從0x000a0000到0x000fffff的實體位址保留給BIOS函式使用有些特殊的電腦硬體會使用到第一個可用的1MB空間為了避免將核心載入到不連續的頁框，Linux不用記憶體中第一個1MB的空間42記憶體中前

2MB的空間分佈i386_endbase_text_etext_end_edata可使用頁框核心程式碼初始化核心資料未初始化核心資料010x1000x1ff不可使用頁框43第十章記憶體管理實作記憶體定址頁框管理頁框運作對偶式系統演算法

記憶體區域管理摘要44頁框管理Linux中採用的頁框大小單位是4KB硬體分頁電路在進行位址轉換時，會自動檢查頁框中是否有分頁存在；每個頁框透過分頁表中的各種旗標來達到硬體保護4KB是大部分磁碟區塊大小的倍數，選擇4KB作為頁框大小，容易知道分頁單元在位址轉換的過程中哪裡發生分頁錯誤在主記憶體與磁碟間傳輸資料時較有效率45頁框運作（1）頁框管理：核心須記錄每個頁框目前的狀態；核心也須知道在動態記憶體中的頁框是否在使用狀態資訊保存在描述器陣列中；每個頁框對應到一個陣列元素頁框描述器結構如下：

count變數設為0：表示對應的頁框未被使用；如果數值大於0，表示此頁框被分配給一個以上的行程、或是用來儲存核心資料結構46頁框運作（2）list為一環狀雙向鏈結串列變數flags：表示目前頁框的狀態指標next_hash與pprev_hash：參考在雜湊串列表page_hash_table中的相對分頁當行程要讀取某個檔案的分頁，系統先檢查雜湊表，確定該分頁是否已在快取中buffer指標：指向此分頁所在的快取緩衝區47頁框運作（3）typedefstructpage{structlist_headlist;/*對應到一環狀雙向鏈結串列*/structaddress_space*mapping;/*記錄此分頁儲存在哪個

inode裡*/structpage*next_hash;atomic_tcount;/*記錄使用該分頁的行程數目*/unsignedlongflags;structlist_headlru;/*記錄要置換出去的分頁串列*/structpage**pprev_hash;structbuffer_head*buffers;}mem_map_t;48描述頁框狀態的旗標（1）PG_locked表示此分頁需要被鎖定在記憶體中進行磁碟

I/O。當

I/O開始時此位元會被設定為

1，I/O結束後此旗標會被清為

0。PG_error表示此分頁有磁碟

I/O錯誤發生。PG_referenced此旗標表示此分頁被配置並曾被存取。PG_uptodate除非磁碟的

I/O發生錯誤，不然此旗標會在完成磁碟讀取操作後被設定為

1。PG_dirty此旗標用來表示此分頁是否需要被寫回磁碟。PG_unused未使用。PG_lru此旗標表示此分頁目前被存放在系統的

activelist

或是inactivelist之中。49描述頁框狀態的旗標（2）PG_active此旗標表示此分頁正被行程所使用（存放在系統的activelist之中）。PG_slab表示此分頁正被

slaballocator所使用。PG_skip此旗標用在

sparc/sparc64架構下已忽略部分的位址空間。PG_highmem表示此分頁被載入到高核心位址空間。PG_checked表示此分頁只能被

EXT2檔案系統所使用。PG_arch_1硬體結構上特定的分頁狀態旗標，當此分頁首次加入快取時，該旗標會被設為

0。PG_reserved表示此頁框會保留給核心程式碼使用、或是根本不能使用，此旗標被設定的分頁不能被換出記憶體。PG_launder當某分頁要被換出記憶體時此旗標將被設定，表示此分頁正被虛擬記憶體寫回。50頁框運作（4）所有頁框描述器均儲存在mem_map陣列中每個頁框描述器均小於64位元組，1MB的記憶體需4個頁框來儲存mem_map陣列MAP_NR巨集以頁框位址當參數去計算頁框的號碼，用此號碼當mem_map陣列的索引系統透過free_area_init()函式初始頁框描述器此函式2個參數start_mem：在核心保留動態記憶體的起始線性位址end_mem：為動態記憶體最終的線性位址加1利用i386_endbase變數儲存保留頁框的初始位址；分配適當大小的記憶體區塊給mem_map陣列使用除了PG_reserved與PG_DMA旗標外，陣列中所有的欄位初始皆設為051記憶體分佈0x10000硬體保留核心保留i386_enbasestart_memend_mem動態記憶體52頁框運作（5）men_init()函式：將頁框中的PG_reserved旗標設為0，之後這些頁框可當成動態記憶體使用將所有實體位址大於或等於0x1000000分頁中的PG_DMA旗標設為0（因ISADMA處理器只能存取第一個16MB的記憶體空間）計算系統中共有多少頁框，並把數值存在變數num_physpages中；計算旗標是PG_reserved的保留頁框數編譯核心的過程中，計算保留給硬體頁框的數目、核心程式碼頁框的數目、核心資料頁框的數目、與用來初始化核心且成功釋放的頁框數目將在動態記憶體中每個頁框的count欄位設定1，並呼叫free_page()函式來漸增變數nr_free_pages的值

獲得動態記憶體中所有的頁框數53頁框運作（6）系統透過以下4個不同的函式或巨集來配置頁框__get_free_pages(gfp_mask,order)：向系統要求2order

個連續頁框__get_dma_pages(gfp_mask,order)：向系統取得適用於DMA的頁框，此巨集會再呼叫__get_free_pages(gfp_mask|GFP_DMA，order)巨集__get_free_page(gfp_mask)：配置一個頁框，相當於__get_free_pages(gfp_mask,0)get_free_page(gfp_mask)：再呼叫__get_free_page(gfp_mask)，並在頁框中填滿0gfp_mask參數：指定如何找尋一個可用頁框54函式__get_free_pages()中

gfp_mask常用參數值名稱說明GFP_ATOMIC此旗標表示呼叫者需要馬上處理、而且不可被中斷。中斷處理函式使用此旗標要求頁框配置，以避免被中斷或是進行

I/O。GFP_NOIO此旗標表示所要求的頁框不能進行

I/O，可供已經在進行

I/O的呼叫者使用，以避免發生更多的

I/O動作。GFP_NOHIGHIO此旗標僅供

alloc_bounce_page()使用。GFP_NOFS此旗標表示不能使用檔案系統，供緩衝區快取及檔案系統使用以避免遞迴呼叫。GFP_NFS在

2.0的核心中表示保留的分頁數目從

20個減到

5個，如此可加快

NFS運算的執行。但在

2.4的核心中已不支援。GFP_KERNEL此旗標表示呼叫者可以對分頁進行任何的動作，但是可以被中斷。GFP_USER在

2.4的核心中與

GFP_KERNEL相同。GFP_HIGHUSER與GFP_USER的不同在於會優先由高記憶體配置頁框。GFP_KSWAPD在

2.4的核心中與

GFP_KERNEL相同。55對偶式系統演算法（1）配置連續頁框必須有效率；為了提高使用率也須解決外部斷裂的問題，2種方式可避免：利用硬體將非連續的可用區塊對映到連續線性位址發展特別的技術來記錄未使用的頁框，Linux核心使用此法如DMA要求記憶體來做緩衝區，必須要使用連續的頁框Linux使用對偶式系統演算法解決外部斷裂所有未被使用的頁框會被分成10種區塊大小的頁框串列，分別包含了1、2、4、8、16、32、64、128、256及512個連續頁框其中每個區塊中第一個頁框的實體位址一定是區塊大小的倍數56對偶式系統演算法（2）對偶式系統演算法的運作：假設某行程要求128個連續頁框，系統首先檢查在區塊大小為128頁框的串列中是否有未使用的區塊如果沒有找到，再去區塊為256頁框的串列中找尋如果有，系統會分配128個頁框給該行程，剩餘的128個頁框就併入區塊為128頁框的串列中如果在區塊為256頁框的串列中找不到可用區塊，就到區塊為512頁框的串列中找尋如果有，將會分配128個頁框來滿足要求，剩餘的384個頁框，將會分成256與128個頁框，分別擺入區塊為256頁框的串列與區塊為128頁框的串列中如果區塊為512頁框的串列也找不到，演算法將停止並發出錯誤狀況的信號57對偶式系統演算法（3）當行程不再需要部分頁框時，將會釋放核心會將2個大小為b且未使用的對偶區塊合併成一個大小為2b的區塊所謂對偶區塊是指：這2區塊大小相同這2區塊實體位址連續第1個區塊，第1個頁框的實體位址是2×b×212的倍數58對偶式系統演算法（4）Linux使用2種不同對偶式系統一是用來處理ISADMA的頁框另一是處理其他的頁框每個對偶式系統的主要資料結構：使用前述的men_map陣列一個元素型態是free_area_struct的二維陣列free_area，每個元素分別對應一種不同區塊大小的頁框串列變數free_area[0]與free_area[1]都指到一個對偶式系統所使用的陣列，各有10個元素不同處：free_area[0]所對應的頁框不適用於ISADMA，free_area[1]卻適用於ISADMA每個頁框串列都對應一個二位元的位元映像表，每個位元都對應到一個頁框區塊（記錄區塊的配置狀況）59對偶式系統的資料結構20212223242526272829mem_mapfree_area[0]位元映像60對偶式系統演算法（5）free_area[0]與free_area[1]陣列裡的每個元素都具有資料結構是free_area_struct的型別此結構中的前兩欄位會指到相對應的分頁描述器；Linux會利用free_area_struct資料結構來指向一個分頁描述器，該結構定義如下：structfree_area_struct{

structpage*next;

structpage*prev;

unsignedint*map;

unsignedlongcount;};61對偶式系統演算法（6）free_area[0]或free_area[1]陣列中的第k元素free_area[0/1][k]會透過next與prev來實作一個大小為2k的環狀雙向鏈結串列每一個節點都是一個頁框區塊中第一個頁框的描述器count欄位會記錄著對應的串列中有多少個元素map欄位指到一個位元映像表，大小則視有多少個存在的頁框每個位元對應到2個同樣大小的連續區塊若該位元為0，表示這2區塊都沒有被使用、或是都在使用中；若該位元為1，代表這2區塊只有1個在使用中當有2個相同大小的區塊沒有在使用，核心將這2個區塊視為一2倍大的區塊62第十章記憶體管理實作記憶體定址頁框管理記憶體區域管理Slab配置器Slab運作摘要63記憶體區域管理記憶體區域是一塊任意長度且具有連續實體位址的記憶體採用新的資料結構，描述如何從一個頁框中配置小塊的記憶體區域；會產生內部斷裂

Linux中提供許多大小以等比級數成長的記憶體區域（所配置的記憶體區域大小是2的次方）保證內部斷裂小於50%Linux使用Slab配置器，可更有效地利用記憶體空間64Slab配置器頻繁的呼叫對偶式系統使核心效率變差對偶式系統每次最少配置一個頁框，如果資料結構所需記憶體大小只要幾百個位元組，剩下的空間就浪費了Slab配置器將資料視為物件概念：將要求而來的記憶體根據物件的大小等分後，再配置給物件去使用加入快取的概念來增加效能特性：當有物件被釋放掉的時候，空的欄位不會再被初始化；當Slab配置器中都沒有物件，記憶體也不會馬上回收，以此減少額外配置與釋放的負擔65