Linux下的內(nèi)存管理方式

1 如何在保護模式下實現(xiàn)對物理內(nèi)存的管理
保護模式在硬件上為實現(xiàn)虛擬存儲創(chuàng)造了條件，但是內(nèi)存的管理還是要由軟件來做。操作系統(tǒng)作為
資源的管理者，當然要對內(nèi)存的管理就要由他來做了。
在386 保護模式下，對任何一個物理地址的訪問都要通過頁目錄表和頁表的映射機制來間接訪問，
而程序提供的任何地址信息都會被當成線性地址進行映射，這就使得地址提供者不知道他所提供的線性
地址最后被映射到了哪個具體的物理地址單元。這樣的措施使得用戶程序不能隨意地操作物理內(nèi)存，提
高了系統(tǒng)的安全性，但是也給操作系統(tǒng)管理物理內(nèi)存造成了障礙。而操作系統(tǒng)必須要了解物理內(nèi)存的使
用情況才談得上管理。
要能夠在保護模式下感知物理內(nèi)存，也就是說要能夠避開保護模式下線性地址的影響，直接對物理
內(nèi)存進行操作。如何避開呢？正如前面所說：在保護模式下對任何一個物理地址的訪問都要通過對線性
地址的映射來實現(xiàn)。
不可能繞過這個映射機制，那只有讓他對內(nèi)核失效。如果讓內(nèi)核使用的線性地址和物理地址重合，比如：
當內(nèi)核使用0x0000 1000 這個線性地址時訪問到的就是物理內(nèi)存中的0x00001000 單元。問題不就解決
了嗎！linux0.11 中采用的正是這種方法。
在進入保護模式之前，要初始化頁目錄表和頁表，以供在切換到保護模式之后使用，要實現(xiàn)內(nèi)核線
性地址和物理地址的重合，必須要在這個時候在頁目錄表和頁表上做文章。
在看代碼之前首先說明幾點：
由于linus 當時編寫程序時使用的機器只有16M 的內(nèi)存，所以程序中也只處理了16M 物理內(nèi)存的
情況，而且只考慮了4G 線性空間的情況。一個頁表可以尋址4M 的物理空間，所以只需要4 個頁表，
一個頁目錄表可以尋址4G 的線性空間，所以只需要1 個頁目錄表。
程序?qū)㈨撃夸洷矸旁谖锢淼刂穇pg_dir＝0x0000 處，4 個頁表分別放在pg0＝0x1000, pg1＝0x2000,
pg2＝0x3000, pg3＝0x4000 處
下面是最核心的幾行代碼：在linux/boot/head.s 中
首先對5 頁內(nèi)存清零
198 setup_paging:
199 movl $1024*5,%ecx /* 5 pages - pg_dir+4 page tables */
#設置填充次數(shù)ecx=1024*5
200 xorl %eax,%eax #設置填充到內(nèi)存單元中的數(shù)eax=0
201 xorl %edi,%edi /* pg_dir is at 0x000 */
#設置填充的起始地址0，也是頁目錄表的起始位置
202 cld;rep;stosl
下面填寫頁目錄表的頁目錄項
對于4 個頁目錄項，將屬性設置為用戶可讀寫，存在于物理內(nèi)存，所以頁目錄項的低12 位是0000 0000
0111B
以第一個頁目錄項為例，$ pg0+7=0x0000 1007
表示第一個頁表的物理地址是0x0000 1007&0xffff f000=0x0000 1000;
權(quán)限是0x0000 1007&0x0000 0fff=0x0000 0007
203 movl $pg0+7,_pg_dir /* set present bit/user r/w */
204 movl $pg1+7,_pg_dir+4 /* --------- " " --------- */
205 movl $pg2+7,_pg_dir+8 /* --------- " " --------- */
206 movl $pg3+7,_pg_dir+12 /* --------- " " --------- */
接著便是對頁表的設置:
4 個頁表×1024 個頁表項×每個頁表項尋址4K 物理空間：4*1024*4*1024=16M
每個頁表項的內(nèi)容是：當前項所映射的物理內(nèi)存地址 + 該頁的權(quán)限
其中該頁的屬性仍然是用戶可讀寫，存在于物理內(nèi)存，即0x0000 0007
具體的操作是從16M 物理空間的最后一個頁面開始逆序填寫頁表項：
最后一個頁面的起始物理地址是0x0xfff000，加上權(quán)限位便是0x fff007,以后每減0x1000（一個頁面
的大?。┍闶窍乱粋€要填寫的頁表項的內(nèi)容。
207 movl $pg3+4092,%edi # edi 指向第四個頁表的最后一項4096-4。
208 movl $0xfff007,%eax /* 16Mb - 4096 + 7 (r/w user,p) */
#把第四個頁表的最后一項的內(nèi)容放進eax
209 std # 置方向位，edi 值以4 字節(jié)的速度遞減。
210 1: stosl /* fill pages backwards - more efficient :-) */
211 subl $0x1000,%eax # 每填寫好一項，物理地址值減0x1000。
212 jge 1b # 如果eax 小于0 則說明全填寫好了。
# 使頁目錄表基址寄存器cr3 指向頁目錄表。
213 xorl %eax,%eax /* pg_dir is at 0x0000 */
令eax=0x0000 0000(頁目錄表基址)
214 movl %eax,%cr3 /* cr3 - page directory start */
# 設置cr0 的PG 標志（位31），啟動保護模式
215 movl %cr0,%eax
216 orl $0x80000000,%eax # 添上PG 標志位。
217 movl %eax,%cr0 /* set paging (PG) bit */
在分析完這段代碼之后，應該對初始化后的頁目錄表和頁表有了一個大概的了解了，當這段代
碼運行完后內(nèi)存中的映射關系應該如圖所示：
接下來將內(nèi)核代碼段描述符gdt 設置為
0x00c09a0000000fff /* 16Mb */ # 代碼段最大長度16M。
這樣線性地址就和物理地址重合了。
下面用兩個例子驗證一下：
（1） 要尋找pg_dir 的第15 項的內(nèi)容
這個地址應該是在頁目錄表的(15-1)*4=0x38 位置，把它寫成32 為地址使0x0000 0038，當內(nèi)
核使用這個地址時，仍然要通過映射：首先取高10 位，0000 0000 00B，根據(jù)203 行的代碼，
頁目錄表第0 項的內(nèi)容是$pg0+7，得到頁表地址是pg0=0x0000 1000,CPU 將用這個地址加上偏
移量找到對應的頁表項，偏移量＝線性地址中間10 位*4＝0，根據(jù)203～221 行執(zhí)行的結(jié)果，
在pg0 中偏移量為0 的頁表項為0x0000 0007, CPU 得到頁表地址是0x0000 0000 加上線性地址
的最后12 位，將找到0x0000 0038 單元的內(nèi)容。
（2）尋找任意物理單元0x00f5 9f50
與第一個例子一樣，用這個地址作為線性地址尋址，先用高10 位尋找頁表，頁目錄表第0000
0000 11B 項指向pg3，根據(jù)線性地址中間10 位11 0101 1001B 尋找頁表項，pg3 的第11 0101
1001B 應該是0x00f5 9007，
取得頁表基址0x00f5 9000，加上頁內(nèi)偏移量0x f50，最后得到的就是物理地址0x00f5 9f50 的
內(nèi)容。
從上面兩個例子可以看出：內(nèi)核中使用的線性地址實際上已經(jīng)是物理地址，這樣從現(xiàn)象上
看386 的地址映射機制對內(nèi)核失效了:-)
明白了這一點之后，對后面內(nèi)存管理方面的的分析就容易得多了
2 內(nèi)存初始化
當操作系統(tǒng)啟動前期實現(xiàn)對于物理內(nèi)存感知之后，接下來要做的就是對物理內(nèi)存的管理，要合理的
使用。對于Linux 這樣一個操作系統(tǒng)而言，內(nèi)存有以下一些使用：面向進程，要分配給進程用于執(zhí)行所必
要的內(nèi)存空間；面向文件系統(tǒng)，要為文件緩沖機制提供緩沖區(qū)，同時也要為虛擬盤機制提供必要的空
間。這三種對于內(nèi)存的使用相對獨立，要實現(xiàn)這一些，就決定了物理內(nèi)存在使用時需要進行劃分，而最
簡單的方式就是分塊，將內(nèi)存劃分為不同的塊，各個塊之間各司其職，互不干擾。linux0.11 中就是這樣
作的。
Linux0.11 將內(nèi)存分為內(nèi)核程序、高速緩沖、虛擬盤、主內(nèi)存四個部分（黑色部分是頁目錄表、幾個
頁表，全局描述符表，局部描述符表。一般將他們看作內(nèi)核的一部分）。為什么要為內(nèi)核程序單獨劃出一
個塊來呢？主要是為了實現(xiàn)上簡單。操作系統(tǒng)作為整個計算機資源的管理者，內(nèi)核程序起著主要的作
用，它的代碼在操作系統(tǒng)運行時會經(jīng)常被調(diào)用，需要常駐內(nèi)存。所以將這部分代碼與一般進程所使用的
空間區(qū)分開，為他們專門化出一塊內(nèi)存區(qū)域。專門劃出一塊區(qū)域還有一個好處，對于內(nèi)核程序來說， 對
于自己的的管理就簡單了，內(nèi)核不用對自己代碼進行管理。比如：當內(nèi)核要執(zhí)行一個系統(tǒng)調(diào)用時，發(fā)現(xiàn)
相應的代碼沒有在內(nèi)存，就必須調(diào)用相關的內(nèi)核代碼去將這個系統(tǒng)調(diào)用的代碼加載到內(nèi)存，在這個過程
中，有可能出現(xiàn)再次被調(diào)用的相關內(nèi)核代碼不在內(nèi)存中的情況，最后就可能會導致系統(tǒng)崩潰。操作系統(tǒng)
為了避免這種情況，在內(nèi)核的設計上就變得復雜了。如果將內(nèi)核代碼專門劃一個塊出來，將內(nèi)核代碼全
部載入這個塊保護起來，就不會出現(xiàn)上面講的情況了。
在linux0.11 中內(nèi)存管理主要是對主內(nèi)存塊的管理。
要實現(xiàn)對于這一塊的管理，內(nèi)核就必須對這一塊中的每一個物理頁面的狀態(tài)很清楚。一個物理頁面
應該有以下基本情況：是否被分配，對于它的存取權(quán)限（可讀、可寫），是否被訪問過, 是否被寫過，被
多少個不同對象使用。對于linux0.11 來說，后面幾個情況可以通過物理頁面的頁表項的D、A、XW 三項
得到，所以對于是否被分配，被多少個對象使用就必須要由內(nèi)核建立相關數(shù)據(jù)結(jié)構(gòu)來記錄。在linux0.11
定義了一個字符數(shù)組mem_map [ PAGING_PAGES ] 用于對主內(nèi)存區(qū)的頁面分配和共享信息進行記錄。
以下代碼均在/mm/memory.c 中
43 #define LOW_MEM 0x100000 // 主內(nèi)存塊可能的最低端（1MB）。
44 #define PAGING_MEMORY (15*1024*1024) // 主內(nèi)存區(qū)最多可以占用15M。
45 #define PAGING_PAGES (PAGING_MEMORY>>12) // 主內(nèi)存塊最多可以占用的物理頁面數(shù)
46 #define MAP_NR(addr) (((addr)-LOW_MEM)>>12) // 將指定物理內(nèi)存地址映射為映射數(shù)組標號。
47 #define USED 100 // 頁面被占用標志
57 static unsigned char mem_map [ PAGING_PAGES ] = {0,}; // 主內(nèi)存塊映射數(shù)組
mem_map 中每一項的內(nèi)容表示物理內(nèi)存被多少個的對象使用，所以對應項為0 就表示對應物理內(nèi)存
頁面空閑。
可以看出當內(nèi)核在定義映射數(shù)組時是以主內(nèi)存塊最大可能大小mem_map 15M 來定義的，最低起始地
址為LOW_MEM，mem_map 的第一項對應于物理內(nèi)存的地址為LOW_MEM，所以就有了第46 行的映射
關系MAP_NR。而當實際運行時主內(nèi)存塊卻不一定是這么大，這就需要根據(jù)實際主內(nèi)存塊的大小對mem
_map 的內(nèi)容進行調(diào)整。對于不是屬于實際主內(nèi)存塊的物理內(nèi)存的對應項清除掉，linux0.11 采用的做法是
在初始化時將屬于實際屬于主內(nèi)存塊的物理內(nèi)存的對應項的值清零，將不屬于的置為一個相對較大的值
USED。這樣在作管理時這些不屬于主內(nèi)存塊的頁面就不會通過主內(nèi)存塊的管理程序被分配出去使用了。
下面就是主內(nèi)存塊初始化的代碼：
/init/main.c
當系統(tǒng)初啟時，啟動程序通過BIOS 調(diào)用將1M 以后的擴展內(nèi)存大?。↘B）讀入到內(nèi)存0x90002 號單元
58 #define EXT_MEM_K (*(unsigned short *)0x90002)
下面是系統(tǒng)初始化函數(shù)main() 中的內(nèi)容
112 memory_end = (1<<20) + (EXT_MEM_K<<10); // 內(nèi)存大小=1Mb 字節(jié)+ 擴展內(nèi)存(k)*1024 字節(jié)。
113 memory_end &= 0xfffff000; // 以頁面為單位取整。
114 if (memory_end > 16*1024*1024) // linux0.11 最大支持16M 物理內(nèi)存
115 memory_end = 16*1024*1024;
116 if (memory_end > 12*1024*1024) // 根據(jù)內(nèi)存大小設置緩沖區(qū)末端的位置
117 buffer_memory_end = 4*1024*1024;
118 else if (memory_end > 6*1024*1024)
119 buffer_memory_end = 2*1024*1024;
120 else
121 buffer_memory_end = 1*1024*1024;
122 main_memory_start = buffer_memory_end; // 主內(nèi)存起始位置= 緩沖區(qū)末端；
123 #ifdef RAMDISK // 如果定義了虛擬盤，重新設置主內(nèi)存塊起始位置
//rs_init() 返回虛擬盤的大小
124 main_memory_start += rd_init(main_memory_start, RAMDISK*1024);
125 #endif
126 mem_init(main_memory_start,memory_end); // 初始化主內(nèi)存塊
下面就是mem_init 的代碼。
399 void mem_init(long start_mem, long end_mem)
400 {
401 int i;
402
403 HIGH_MEMORY = end_mem; // 設置物理內(nèi)存最高端。
404 for (i=0 ; i<PAGING_PAGES ; i++) // 將主內(nèi)存塊映射數(shù)組所有項置為USED
405 mem_map[i] = USED;
406 i = MAP_NR(start_mem); // 計算實際主內(nèi)存塊物理地址起始位置對應的映射項
407 end_mem - = start_mem; // 計算實際主內(nèi)存塊大小
408 end_mem >>= 12; // 計算需要初始化的映射項數(shù)目
409 while (end_mem-->0) 將實際主內(nèi)存塊對// 應的映射項置為0（空閑）
410 mem_map[i++]=0;
411 }
通過以上的操作之后，操作系統(tǒng)便可以了解主內(nèi)存塊中物理內(nèi)存頁面的使用情況了。
3 內(nèi)存的分配與回收
分配
當內(nèi)核本身或者進程需要一頁新的物理頁面時，內(nèi)核就要給他分配一個空閑的物理頁面。內(nèi)核需要
查詢相關信息，以盡量最優(yōu)的方案分配一個空閑頁面，尤其是在有虛存管理機制的操作系統(tǒng)中對于空閑
頁面的選取方案非常重要，如果選取不當將導致系統(tǒng)抖動。linux0.11 沒有實現(xiàn)虛存管理，也就不用考慮
這些，只需要考慮如何找出一個空閑頁面。
知道了內(nèi)核對主內(nèi)存塊中空閑物理內(nèi)存頁面的映射結(jié)構(gòu)mem_map，查找空閑頁面的工作就簡單了。
只需要在mem_map 找出一個空閑項，并將該項映射為對應的物理頁面地址。算法如下：
算法：get_free_page
輸入：無
輸出：空閑頁面物理地址
{
從最后一項開始查找mem_map 空閑項；
if( 沒有空閑項)
renturn 0；
將空閑項內(nèi)容置1，表示已經(jīng)被占用；
將空閑項對應的下標轉(zhuǎn)換為對應的物理頁面的物理地址＝
( 數(shù)組下標<<12 ＋ LOW_MEM)
將該物理頁內(nèi)容清零
return 對應的物理地址；
}
get_free_page 的源碼如下：
/mm/memory.c
59 /*
60 * Get physical address of first (actually last :-) free page, and mark it
61 * used. If no free pages left, return 0.
62 */
/*
* 獲取首個(實際上是最后1 個:-) 空閑頁面，并標記為已使用。如果沒有空閑頁面，
* 就返回0。
*/
// 輸入：%1與%0 相同表示eax，初值為0；%2 表示直接操作數(shù)(LOW_MEM)；
%3 表示ecx，初值為PAGING PAGES；搜索次數(shù)
%4 表示edi 初值為映射數(shù)組最后一項地址mem_map+PAGING_PAGES-1。
// 輸出：返回%0, 表示eax 頁面起始地址。eax 即__res
63 unsigned long get_free_page(void)
64 {
65 register unsigned long __res asm( "ax");
66
67 __asm__( "std ; repne ; scasb/n/t" // 置方向位，將al(0) 與(edi) 開始的反相ecx 個字節(jié)的內(nèi)容比較
68 "jne 1f/n/t" // 如果沒有等于0 的字節(jié)，則跳轉(zhuǎn)結(jié)束（返回0）。
69 "movb $1,1(%%edi)/n/t // 將該內(nèi)存映射項置1。
70 "sall $12,%%ecx/n/t" 相對于// LOW_MEM 的頁面起始地址。
71 "addl %2,%%ecx/n/t" // 加上LOW_MEM ＝ > 頁面實際物理起始地址。
72 "movl %%ecx,%%edx/n/t" // 保存頁面實際物理起始地址。
73 "movl $1024,%%ecx/n/t" // 置計數(shù)值1024
74 "leal 4092(%%edx),%%edi/n/t" // 使edi 指向該物理頁末端
75 "rep ; stosl/n/t" // 沿反方向?qū)⒃擁撉辶恪?br />76 "movl %%edx,%%eax/n" // 將頁面實際物理起始地址放入eax（返回值）。
77 "1:"
78 : "=a" (__res)
79 : "" (0), "i" (LOW_MEM), "c" (PAGING_PAGES),
80 "D" (mem_map+PAGING_PAGES-1)
81 : "di", "cx", "dx");
82 return __res; // 返回空閑頁面實際物理起始地址（如果無空閑也則返回0）。
83 }
84
這個函數(shù)返回的只是物理頁面的物理地址，下一節(jié)將具體講如何將物理地址映射為線性地址。
回收：
當內(nèi)核使用完一個物理頁面或者進程退出時內(nèi)核歸還申請了的物理頁面。這時就需要更改相應的信
息，以便下一次使用。在歸還頁面時可能會出現(xiàn)下面幾種情況：
1）頁面物理地址低于主內(nèi)存塊可能的最低端，這種情況不需要處理直接退出，因為這部分內(nèi)存空
間被用于內(nèi)核程序和緩沖，沒有作為分配頁面的內(nèi)存空間。還有一種情況會出現(xiàn)這種情況，當內(nèi)存操作
失敗時，會調(diào)用回收頁面過程回收已經(jīng)分配了的物理頁，如果因為內(nèi)存分配失敗造成的，就不需要真正
的回收操作，調(diào)用回收過程時會以0 為輸入?yún)?shù)。
2）頁面物理地址高于實際物理內(nèi)存最高地址。這種情況是不允許的，內(nèi)核將使調(diào)用對象進入死循
環(huán)，這是一種簡單而有效的方法，因為這種情況要判斷出錯原因是很困難的。
3）調(diào)用對象試圖釋放一塊空閑物理內(nèi)存。出現(xiàn)這種情況可能是因為多個對象共享該物理頁，在釋
放時出現(xiàn)了重復釋放。比如：進程A、B共享物理頁170，由于系統(tǒng)的原因A將該頁釋放了兩次，當B
釋放該頁時就會出現(xiàn)這種情況。這種情況也是不允許的，一般意味著內(nèi)核出錯，內(nèi)核將使調(diào)用對象進入
死循環(huán)以避免錯誤擴散。
4）要釋放的頁面正確。因為可能是共享內(nèi)存，所以要將該頁對應的映射項的值減1，表示減少了
一個引用對象。如果引用數(shù)減到0了，并不對物理頁面的內(nèi)容清0，等到被分配時再做，因為可能這個頁
面不會在被使用，同時在分配時用匯編代碼來做效率會很高。
這樣下面的代碼就很好理解了：
85 /*
86 * Free a page of memory at physical address 'addr'. Used by
87 * 'free_page_tables()'
88 */
/*
* 釋放物理地址'addr' 開始的一頁內(nèi)存。用于函數(shù)'free_page_tables()'。
*/
89 void free_page(unsigned long addr)
90 {
91 if (addr < LOW_MEM) return; 如果物理地址小于// addr 主內(nèi)存塊可能的最低端，則返回。
92 if (addr >= HIGH_MEMORY)
// 如果物理地址addr>= 實際內(nèi)存大小，則顯示出錯信息，調(diào)用對象死機。
93 panic( "trying to free nonexistent page");
94 addr - = LOW_MEM; // 將物理地址換算為對應的內(nèi)存映射數(shù)組下標。
95 addr >>= 12;
96 if (mem_map[addr]--) return; // 如果對應內(nèi)存映射數(shù)組項不等于0，則減1，返回
97 mem_map[addr]=0; // 否則置對應映射項為0，并顯示出錯信息，調(diào)用對象死機。
98 panic( "trying to free free page");
99 }
100

4 頁面映射
如果進程請求一頁空閑內(nèi)存，或者頁失效錯誤時，會出現(xiàn)頁面請求。在這個時候請求是以線性地址
的形式提出來的。因為對于一個進程來說，它感知不到其他進程的存在，對它自己，覺得獨占了所有資
源。操作系統(tǒng)在控制物理內(nèi)存的同時又要控制進程的虛擬空間，這就需要在內(nèi)存線性地址與物理地址之
間作轉(zhuǎn)換工作。比如：進程在線性地址0x0104 F380 處 產(chǎn)生了缺頁中斷，內(nèi)核將進行一系列的處理，最
后分配一個物理頁面，但是并不能這樣返回進程執(zhí)行，因為進程仍然需要從線性地址0x0104 F380 處讀取
數(shù)據(jù)，就像沒有發(fā)生過缺頁中斷一樣。操作系統(tǒng)就必須要做這個工作，將物理頁面映射到線性地址上。
要將物理頁面映射到線性地址上，就應該修改頁目錄表和頁表的相關內(nèi)容，這樣進程才能通過線性
地址找到相應的物理頁面?；仡櫼幌?86 頁面映射機制，cpu 通過線性地址的高10 位尋找到相應的頁
表，再通過中間10 位尋找到物理頁面，最后通過低12 位在物理頁面中尋找到相應的內(nèi)存單元。所以要
讓進程找到物理頁面，就必須根據(jù)線性地址設置頁目錄項和頁表項。linux0.11 使用put_page 來作這個處
理，其算法如下：
算法：put_page
輸入：物理頁面地址page
線性地址address
輸出：如果成功，返回page；如果失敗，返回0
{
if ( 物理頁面地址低于LOW_MEM 或者不小于HIGH_MEMORY)
顯示出錯信息，返回0；
if ( 物理頁面地址對應的內(nèi)存映射數(shù)組映射項的值！＝ 1)
顯示出錯信息，返回0；
根據(jù)線性地址高10 位找到對應的頁目錄表項；
if ( 頁目錄表項對應的頁表在內(nèi)存中)
根據(jù)頁目錄表項的到頁表的物理地址；
else{
分配新的物理頁面作為新的頁表；
初始化頁目錄表項，使它指向新的頁表；
根據(jù)頁目錄表項的到頁表的物理地址；
}
根據(jù)線性地址中間10 位找到對應的頁表項；
if( 對應的頁表項已經(jīng)被使用)
顯示出錯信息，返回0；
設置對應的頁表項，使它指向物理頁面；
return 物理頁面地址；
}
put_page 操縱的是由get_free_page（）分配得到的物理頁面，所以物理頁面地址應該是在主內(nèi)存塊
中，如果不在，就應該終止映射，返回失敗。然后調(diào)用put_page 函數(shù)的對象根據(jù)自身的特性作相關處
理。同樣是因為put_page 操縱的是新分配的物理頁面，所以物理頁面地址對應的內(nèi)存映射數(shù)組映射項的
值應該是1。如果不是1，也應該終止映射，返回失敗。如果前面的檢查通過了，就應改進行映射了。首
先在頁目錄表中找到對應頁目錄項，如果頁目錄項有效，即對應頁表在內(nèi)存中，就直接尋找頁表項。否
則就必須先分配一個物理頁作為頁表。從理論上講，在設置對應的頁表項之前應該檢查一下該頁表項是
否已經(jīng)被使用。從而確保映射的一致性，因為如果頁表項已經(jīng)被使用，對其的第二次賦值會使原來的映
射關系失效。但是由于linux 在總體設計上的特點，而且新分配的頁表被全部清零，所以不會出現(xiàn)這個問
題。隨著對代碼分析的深入，將體會到這一點。
下面就是的put_page 代碼：
/mm/memory.c
190
191 /*
192 * This function puts a page in memory at the wanted address.
193 * It returns the physical address of the page gotten, 0 if
194 * out of memory (either when trying to access page-table or
195 * page.)
196 */
/*
* 下面函數(shù)將一內(nèi)存頁面放置在指定地址處。它返回頁面的物理地址，如果
* 內(nèi)存不夠(在訪問頁表或頁面時)，則返回0。
*/
197 unsigned long put_page(unsigned long page,unsigned long address)
198 {
199 unsigned long tmp, *page_table;
200
201 /* NOTE !!! This uses the fact that _pg_dir=0 */
/* 注意!!! 這里使用了頁目錄基址_pg_dir=0 的條件 */
202
203 if (page < LOW_MEM || page >= HIGH_MEMORY) // 判斷是否在主內(nèi)存塊中
204 printk( "Trying to put page %p at %p/n",page,address);
205 if (mem_map[(page-LOW_MEM)>>12] != 1) // 判斷對應映射項的值是否為1
206 printk( "mem_map disagrees with %p at %p/n",page,address);
207 page_table = (unsigned long *) ((address>>20) & 0xffc); // 根據(jù)線性地址找到對應的頁目錄表項；
208 if ((*page_table)&1) // 判斷頁表是否存在
209 page_table = (unsigned long *) (0xfffff000 & *page_table); // 取對應頁表物理地址
210 else {
211 if (!(tmp=get_free_page())) // 申請新物理頁作為頁表
212 return 0;
213 *page_table = tmp|7; // 設置頁目錄項
214 page_table = (unsigned long *) tmp;
215 }
216 page_table[(address>>12) & 0x3ff] = page | 7; // 頁面設置為用戶權(quán)限、可寫、有效
217 /* no need for invalidate */
/* 不需要刷新頁變換高速緩沖 */
218 return page; // 返回物理頁面地址。
219 }
220
在這個代碼中，如果第一個判斷為真時，只是打印出錯信息，并沒有返回。這將導致第二個判斷時
數(shù)組溢出，由于語言并不對數(shù)組溢出進行出錯處理。這里將可能出現(xiàn)錯誤。而且mem_map c 第二個判斷
也沒有在打印錯誤信息之后返回，這將導致錯誤蔓延。不過幸運的是，linux0.11 中不會以這種參數(shù)調(diào)用
put_page，所以這里只是作一個算法上的說明。
看了put_page 之后，那么get_empty_page 的代碼就很好理解了。get_empty_page 以線性地址為參數(shù)，
申請新的物理頁面并完成映射過程。
/mm/memory.c
274 void get_empty_page(unsigned long address)
275 {
276 unsigned long tmp;
277
278 if (!(tmp=get_free_page()) || !put_page(tmp,address)) {
279 free_page(tmp); /* 0 is ok - ignored */
280 oom();
281 }
282 }
283
其中oom() 是用于內(nèi)存使用完后的處理，顯示完信息之后使調(diào)用進程退出。
/mm/memory.c
33 static inline volatile void oom(void)
34 {
35 printk( "out of memory/n/r");
36 do_exit(SIGSEGV); // 進程退出，出錯碼：SIGSEGV（資源暫時不可用）
37 }
38

5 釋放頁表：
內(nèi)核使用了內(nèi)存，自然就會有釋放的時候。當進程創(chuàng)建時，需要獲得大量的內(nèi)存，也會釋放大量的
內(nèi)存空間；當進程退出時，肯定有大量的內(nèi)存需要釋放。而伴隨這種大量的內(nèi)存釋放工作，這些空間對
應的頁表也會變成無用的。如果不進行回收，將是巨大的浪費。
內(nèi)核如果要做這種釋放（見算法free_page_tables），至少需要釋放一個頁表所映射的4M 的線性空
間，所以釋放空間起始地址應該是以4M 為邊界的。要釋放的空間不可以是低16M 的空間。
算法：free_page_tables
輸入：要釋放空間起始線性地址from
要釋放空間大小size
輸出：如果成功，返回0；如果失敗，使調(diào)用對象進入死循環(huán)
{
if( 要釋放的空間不是以4M 為邊界)
顯示出錯信息，調(diào)用對象死循環(huán)；
if( 要釋放的空間是用于內(nèi)核控制物理內(nèi)存的低16M 空間)
顯示出錯信息，調(diào)用對象死循環(huán)；
計算要釋放的空間所占的頁表數(shù)；
for( 每個要釋放的頁表){
for( 每個頁表項)
if( 頁表項映射有物理頁面)
釋放物理頁面free_page()；
將該頁表項設為空閑；
}
釋放頁表使用的物理頁；
將該頁表對應的頁目錄項設為空閑；
}
刷新頁變換高速緩沖；
return 0；
}
因為這個線性空間是用于內(nèi)核對物理內(nèi)存的控制，不可以被釋放。接下來要做的就很明顯了。整個操作
將導致頁目錄表的變化。由于cpu 為了提高內(nèi)存訪問速度，會將頁目錄表和部分頁表加載到cpu 頁變換高
速緩存中，我們修改了頁目錄表就必須使cpu 頁變換高速緩存中的內(nèi)容同我們修改后的相同，所以必須刷
新頁變換高速緩沖。通過重新對頁目錄表寄存器cr3 賦值就可以使cpu 刷新頁變換高速緩沖。具體代碼見
下：
/mm/memory.c
39 #define invalidate() /
40 __asm__( "movl %%eax,%%cr3":: "a" (0)) // 寄存器eax 中存放0，即頁目錄表起始地址
41
101 /*
102 * This function frees a continuos block of page tables, as needed
103 * by 'exit()'. As does copy_page_tables(), this handles only 4Mb blocks.
104 */
/*
* 下面函數(shù)釋放頁表連續(xù)的內(nèi)存塊，'exit()' 需要該函數(shù)。與copy_page_tables()
* 類似，該函數(shù)僅處理4Mb 的內(nèi)存塊。
*/
105 int free_page_tables(unsigned long from,unsigned long size)
106 {
107 unsigned long *pg_table;
108 unsigned long * dir, nr;
109
110 if (from & 0x3fffff) 要釋放// 空間線性地址應該以4M 為邊界。
111 panic( "free_page_tables called with wrong alignment");
112 if (!from) // 這里只對低4M 空間的釋放進行限制，BUG
113 panic( "Trying to free up swapper memory space");
114 size = (size + 0x3fffff) >> 22; // 計算要釋放的頁表數(shù)
115 dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */ // 第一個要釋放頁表對應的頁目錄項
116 for ( ; size-->0 ; dir++) {
117 if (!(1 & *dir)) // 該目錄項是否有效
118 continue;
119 pg_table = (unsigned long *) (0xfffff000 & *dir); // 計算頁表起始地址。
120 for (nr=0 ; nr<1024 ; nr++) {
121 if (1 & *pg_table) // 頁表項有效，則釋放對應頁。
122 free_page(0xfffff000 & *pg_table);
123 *pg_table = 0; // 將對應頁表項置為空閑
124 pg_table++;
125 }
126 free_page(0xfffff000 & *dir); // 釋放頁表使用的物理頁；
127 *dir = 0; // 將對應頁目錄表項置為空閑
128 }
129 invalidate(); // 刷新頁變換高速緩沖。
130 return 0;
131 }
132
6 內(nèi)存共享
在一個系統(tǒng)中，內(nèi)存往往是最緊張的資源，為了將這種資源合理的利用，就必須搞清楚內(nèi)存是如何
被使用的，只有這樣才能進行合理而且高效的分配。
進程有時需要讀內(nèi)存，有時需要寫內(nèi)存，這個過程似乎是隨機的。但是對于每一個進程來說，有一
個段是不會被寫的，那就是代碼段。這個段的內(nèi)容由進程的可執(zhí)行文件決定，不會改變，進程運行時，
也不能修改這個段的內(nèi)容。如果兩個進程使用的是同一個可執(zhí)行文件，比如：打開兩個try.exe 文件（假
定該可執(zhí)行文件不支持多線程），這時如果讓兩個進程在內(nèi)存中分別使用兩份代碼，將造成不必要的內(nèi)存
浪費，所以這種情況下，內(nèi)核會讓這兩個進程使用同一個代碼段的內(nèi)存空間。
其實數(shù)據(jù)段也是可以共享的，同樣是使用同一可執(zhí)行文件的多個進程，他們在進程還沒有開始執(zhí)行
時，數(shù)據(jù)段是相同的，隨著進程的運行，數(shù)據(jù)段的內(nèi)容可能會被改變。內(nèi)存的訪問具有局部性，在一段
時間內(nèi)可能不會有對數(shù)據(jù)段的某些區(qū)間修改，這個時間段可能很短，如果進程的數(shù)據(jù)操作完全靠堆棧來
實現(xiàn)，這個時間段就可能是進程的整個生命周期。但是如何預測進程的數(shù)據(jù)操作是在哪里，如何預測數(shù)
據(jù)段哪些區(qū)間可以共享，哪些不行，從而安排內(nèi)存的使用？答案是否定的，對于現(xiàn)代操作系統(tǒng)而言， 這
種預測是不現(xiàn)實的，或者代價相當大。與其花費大量精力去做預測，為什么不采用以逸待勞的辦法呢？
先將空間共享，等到進程對共享空間進行寫操作時再取消對該頁的共享。liunx 采用了一種稱為寫時復制
(copy on write) 的機制。這種機制必須要有硬件的支持，在386 頁面映射機制中，有一個讀寫權(quán)限標志位
XW，將這一位設為只讀（0）方式
之后，如果進程試圖對該頁進行寫操
作，cpu 將出現(xiàn)頁面異常中斷，調(diào)用
內(nèi)核設定的頁面異常中斷處理程序，在這里內(nèi)核將原來的頁面復制一份，再取消對該頁面的共享，這樣
就互不干擾了。有了這個保障，內(nèi)核在進行內(nèi)存共享操作時就可以放心了。
當內(nèi)核使用fork 創(chuàng)建一個進程時，子進程將使用和父進程的同樣代碼段和數(shù)據(jù)段，然后根據(jù)fork 返
回的不同的值作為判斷，運行不同的代碼。見示例程序：
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
void main(){
int childpid.data=100;
childpid=fork();
if(childpid==0){
printf("I'm child!/n");
printf("My father have a data ,it's %d!/n",data);
exit(0);
}
printf("I'm father!I have a child %d/n",childpid);
exit(0);
}
創(chuàng)建一個進程后，父進程和子進程使用同樣的代碼。但是他們中childpid 的值不同，如果是子進
程，childpid 的值是0；如果是父進程，childpid 的值是子進程的進程號。在這以后，子進程可能會使用父
進程中的一些數(shù)據(jù)。如果子進程不調(diào)用另一個可執(zhí)行文件作為其執(zhí)行代碼，子進程將一直使用父進程的
代碼。

6.1 共享空間
有了386 對頁面共享的支持，共享空間的方法就很容易想到了。將被共享的空間的頁目錄表和頁表復
制一份，并且將所有頁表項的訪問屬性設為只讀，并修改頁面映射表中的頁面引用信息即可。具體算法
如下：
算法：copy_page_tables
輸入：共享源頁面起始地址from
共享目的空間頁面起始地址to
被共享空間的大小size
輸出：如果成功，返回0
{
if(from 或者to 不是以4M 為邊界)
顯示出錯信息，使調(diào)用對象進入死循環(huán)；
for( 共享源空間的每一個頁目錄項){
if( 對應共享目的空間的頁表已經(jīng)存在)
顯示出錯信息，死循環(huán)；
if( 共享源空間的頁目錄項不存在)
continue；
為對應共享目的空間分配空閑頁作為頁表；
設置該空閑頁屬性（可寫、用戶、有效）
if( 共享源空間本次復制的是前4M 的內(nèi)核空間)
本次共享空間只是前640K；
for( 每個要共享空間的頁表項){
復制頁表項；
if( 對應頁不存在)
continue；
if( 被共享頁在主內(nèi)存塊映射表映射范圍內(nèi) ){
將兩個頁表項都置為只讀；
對應頁面映射項內(nèi)容加1；
}
else
只將復制的頁表項置為只讀；
}
}
刷新頁變換高速緩沖；
}
對于帶有頁表復制，和帶有頁表的釋放一樣，必須保證被共享的空間和被共享到的空間起始地址是
以4M 為邊界的；每次共享4M 的空間，像以前一樣，對于內(nèi)核空間必須作特殊處理。640K 到1M 的空
間本來是高速緩沖塊的空間，但是被顯存和BIOS 占用了，所以這部分空間是不共享的；因為linus 當初
使用的計算機有16M 的內(nèi)存，高速緩沖空間結(jié)束位置是4M（見啟動后內(nèi)存分配），所以可能是由于這個
原因，1M 到3,071K 這個空間也是不共享的，對高速緩沖共享是沒有意義的，這樣內(nèi)核的前4M 空間就
只共享640K。如果被共享頁不在主內(nèi)存塊映射表范圍內(nèi)，共享的就是這640K 的空間，是內(nèi)核使用的，
在共享時，源頁表項不被置為只讀。
/mm/memory.c
132
133 /*
134 * Well, here is one of the most complicated functions in mm. It
135 * copies a range of linerar addresses by copying only the pages.
136 * Let's hope this is bug-free, 'cause this one I don't want to debug :-)
137 *
138 * Note! We don't copy just any chunks of memory - addresses have to
139 * be divisible by 4Mb (one page-directory entry), as this makes the
140 * function easier. It's used only by fork anyway.
141 *
142 * NOTE 2!! When from==0 we are copying kernel space for the first
143 * fork(). Then we DONT want to copy a full page-directory entry, as
144 * that would lead to some serious memory waste - we just copy the
145 * first 160 pages - 640kB. Even that is more than we need, but it
146 * doesn't take any more memory - we don't copy-on-write in the low
147 * 1 Mb-range, so the pages can be shared with the kernel. Thus the
148 * special case for nr=xxxx.
149 */
/*
好了，下面是內(nèi)存管理中最為復雜的程序之* mm 一。它通過只復制內(nèi)存頁面
* 來拷貝一定范圍內(nèi)線性地址中的內(nèi)容。希望代碼中沒有錯誤，因為我不想
* 再調(diào)試這塊代碼了.。
*
* 注意！我們并不是僅復制任何內(nèi)存塊 - 內(nèi)存塊的地址需要是4Mb 的倍數(shù)（正好
* 一個頁目錄項對應的內(nèi)存大?。驗檫@樣處理可使函數(shù)很簡單。不管怎樣，
* 它僅被fork() 使用（fork.c 第56 行）。
*
* 注意2！！當from==0 時，是在為第一次fork() 調(diào)用復制內(nèi)核空間。此時我們
* 不想復制整個頁目錄項對應的內(nèi)存，因為這樣做會導致內(nèi)存嚴重的浪費 - 我們
* 只復制頭160 個頁面 - 對應640kB。即使是復制這些頁面也已經(jīng)超出我們的需求，
* 但這不會占用更多的內(nèi)存 - 在低1Mb 內(nèi)存范圍內(nèi)我們不執(zhí)行寫時復制操作，所以
* 這些頁面可以與內(nèi)核共享。因此這是nr=xxxx 的特殊情況（nr 在程序中指頁面數(shù)）。
*/
150 int copy_page_tables(unsigned long from,unsigned long to,long size)
151 {
152 unsigned long * from_page_table;
153 unsigned long * to_page_table;
154 unsigned long this_page;
155 unsigned long * from_dir, * to_dir;
156 unsigned long nr;
157
158 if ((from&0x3fffff) || (to&0x3fffff)) // 判斷是否以4M 為邊界
159 panic( "copy_page_tables called with wrong alignment");
160 from_dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */ 計// 算起始頁目錄項
161 to_dir = (unsigned long *) ((to>>20) & 0xffc);
162 size = ((unsigned) (size+0x3fffff)) >> 22; // 計算要共享的頁表數(shù)
163 for( ; size-->0 ; from_dir++,to_dir++) {
164 if (1 & *to_dir) // 被共享到的頁表已經(jīng)存在
165 panic( "copy_page_tables: already exist");
166 if (!(1 & *from_dir)) // 被共享的頁表不存在
167 continue;
168 from_page_table = (unsigned long *) (0xfffff000 & *from_dir); // 取源頁表地址
169 if (!(to_page_table = (unsigned long *) get_free_page()))
170 return -1; /* Out of memory, see freeing */
171 *to_dir = ((unsigned long) to_page_table) | 7; // 設置該頁屬性（可寫、用戶、有效）
172 nr = (from==0)?0xA0:1024; // 如果是前4M 空間，只共享640K(160 頁)
173 for ( ; nr-- > 0 ; from_page_table++,to_page_table++) {
174 this_page = *from_page_table;
175 if (!(1 & this_page)) // 如果當前源頁表項沒有使用，則不用復制
176 continue;
177 this_page &= ~2; // 將目的頁表項設為只讀
178 *to_page_table = this_page;
179 if (this_page > LOW_MEM) { // 如果被共享頁在主內(nèi)存塊映射表映射范圍內(nèi)
180 *from_page_table = this_page; // 源頁表項設為只讀
181 this_page -= LOW_MEM;
182 this_page >>= 12;
183 mem_map[this_page]++; // 共享數(shù)加一
184 }
185 }
186 }
187 invalidate(); // 刷新頁變換高速緩沖。
188 return 0;
189 }
190
6.2 共享進程空間
6.2.1 早期共享
當內(nèi)核使用fork 創(chuàng)建一個進程時，子進程將使用和父進程的進程空間進行完全的拷貝。子進程除了
要與父進程共享內(nèi)存空間外，如果要在這個內(nèi)存空間上運行還需要根據(jù)父進程的數(shù)據(jù)段描述符和代碼段
描述符設置子進程的自己的數(shù)據(jù)段描述符和代碼段描述符。算法如下：
算法：copy_mem
輸入：子進程進程號nr
子進程進程控制塊p
輸出：如果成功，返回0
{
取得父進程的數(shù)據(jù)段、代碼段的段限長和基地址；
if（數(shù)據(jù)段和代碼段段限長和基地址不合法）
顯示出錯信息，死循環(huán)；
設置子進程的數(shù)據(jù)段、代碼段的段限長和基地址；
共享代碼段和數(shù)據(jù)段內(nèi)存空間（copy_page_tables）
if（共享失?。﹞
釋放子進程共享內(nèi)存空間時申請的頁面；
return 共享失敗；
}
return 0；
}
由于linux0.11 只支持數(shù)據(jù)段和代碼段基址相同的進程，所以判斷數(shù)據(jù)段和代碼段的合法性首先應
該檢測兩者是否相同；又由于代碼段在數(shù)據(jù)段之前，所以代碼段限長一定要小于數(shù)據(jù)段限長；
/kernel/fork.c
// 當前進程即父進程
39 int copy_mem(int nr,struct task_struct * p)
40 {
41 unsigned long old_data_base,new_data_base,data_limit;
42 unsigned long old_code_base,new_code_base,code_limit;
43
44 code_limit=get_limit(0x0f); // 取當前進程代碼段和數(shù)據(jù)段段限長
45 data_limit=get_limit(0x17);
46 old_code_base = get_base(current->ldt[1]); // 取原代碼段和數(shù)據(jù)段段基址
47 old_data_base = get_base(current->ldt[2]);
48 if (old_data_base != old_code_base)
49 panic( "We don't support separate I&D");
50 if (data_limit < code_limit)
51 panic( "Bad data_limit");
52 new_data_base = new_code_base = nr * 0x4000000; // 子進程基址= 進程號*64Mb( 進程線性空間)
53 p->start_code = new_code_base;
54 set_base(p->ldt[1],new_code_base); // 設置代碼段、數(shù)據(jù)段基址
55 set_base(p->ldt[2],new_data_base);
56 if (copy_page_tables(old_data_base,new_data_base,data_limit)) { // 共享代碼段和數(shù)據(jù)段內(nèi)存空間
57 free_page_tables(new_data_base,data_limit); 釋// 放共享內(nèi)存空間時申請的頁面
58 return -ENOMEM;
59 }
60 return 0;
61 }
62

6.2.2 后期共享
當子進程被fork 出來后，就會和父進程分道揚鑣，獨立地被內(nèi)核調(diào)度執(zhí)行，在這個過程中父進程和子
進程的執(zhí)行是獨立的，互不影響。如果父進程因為缺頁新申請了物理頁面，子進程是不知道的。示例如
下：
當子進程產(chǎn)生缺頁時，子進程還是要盡量地“偷懶”，除了在被fork 出來時可以與父進程共享內(nèi)存
外，父進程新申請的物理頁也是可以被共享的。只要申請頁被讀入之后還沒有被改變過就可以共享。
其實上面說的例子中，如果是子進程申請了新的物理頁，父進程同樣可以拿來用，如果子進程還fork
了孫進程，孫進程申請的頁面子進程和父進程都可以使用。因為分道揚鑣之后各個進程是平等的，只要
大家都使用同一個可執(zhí)行程序，誰先申請新物理頁都是一樣的。
試圖共享內(nèi)存的算法如下：
算法：share_page
輸入：共享地址address
輸出：如果成功，返回1
{
if ( 要求共享的進程A 沒有對應的可執(zhí)行文件)
return 0；
if (A 對應的可執(zhí)行文件沒有被多個進程使用)
return 0；
for( 每個存在的進程P)
{
if (P 就是要求共享的進程本身)
continue；
if (P 對應可執(zhí)行文件與要求共享的進程的不同)
continue；
if (P 進程共享地址對應的物理頁不存在或不干凈)
continue；
if ( 對應物理頁不屬于主內(nèi)存塊 )
continue；
if ( 進程A 共享地址對應的頁表不存在 )
{
為頁表分配新的物理頁；
設置頁目錄項；
}
if ( 進程A 對應的頁表項已經(jīng)存在 )
顯示錯誤信息，死循環(huán)；
將進程P 對應的頁表項屬性設為只讀；
設置進程A 對應地址的頁表項；
物理頁引用數(shù)加1；
刷新頁變換高速緩沖。
return 1；
}
return 0；
}
對于每一個進程都應該對應一個可執(zhí)行文件，當進程處于某些特定時刻（如：正在作進行初始化設
置）時沒有對應的可執(zhí)行文件，當然也就不應該作共享處理。如果對應的可執(zhí)行文件應用數(shù)不大于1，則
表示沒有進程與要求共享的進程共享對應的可執(zhí)行文件，也不會有共享對象。
接下來的任務就是找到一個符合要求的共享物理頁，條件有：1，進程對應可執(zhí)行文件相同；2，對
應物理頁在被讀入之后沒有被修改過。如果要求共享進程對應地址的頁表項存在，但是原來是因為缺頁
才進入共享操作的，肯定系統(tǒng)出現(xiàn)了嚴重錯誤。
最后進程P 對應的頁表項屬性修改為只讀，設置進程A 對應地址的頁表項，使它指向共享物理頁，
屬性為只讀，物理頁對應主內(nèi)存塊映射數(shù)組項加1；因為頁表發(fā)生了變化，所以要刷新頁變換高速緩沖。
下面是具體代碼：
/mm/memory.c
335
336 /*
337 * share_page() tries to find a process that could share a page with
338 * the current one. Address is the address of the wanted page relative
339 * to the current data space.
340 *
341 * We first check if it is at all feasible by checking executable->i_count.
342 * It should be >1 if there are other tasks sharing this inode.
343 */
/*
* share_page() 試圖找到一個進程，它可以與當前進程共享頁面。參數(shù)address 是
* 當前數(shù)據(jù)空間中期望共享的某頁面地址。
*
* 首先我們通過檢測executable->i_count 來查證是否可行。如果有其它任務已共享
* 該inode，則它應該大于1。
*/
344 static int share_page(unsigned long address)
345 {
346 struct task_struct ** p;
347
348 if (!current->executable) 沒// 有對應的可執(zhí)行文件
349 return 0;
350 if (current->executable->i_count < 2) // 不是多進程共享可執(zhí)行文件
351 return 0;
352 for (p = &LAST_TASK ; p > &FIRST_TASK ; --p) { // 搜索每個進程控制塊指針
353 if (!*p) // 沒有對應進程
354 continue;
355 if (current == *p) // 就是指向當前任務
356 continue;
357 if ((*p)->executable != current->executable) // 不是與當前任務使用同一個可執(zhí)行文件
358 continue;
359 if (try_to_share(address,*p)) // 試圖共享頁面
360 return 1;
361 }
362 return 0;
363 }
364
下面是try_to_share(address,*p) 的代碼：
/mm/memory.c
283
284 /*
285 * try_to_share() checks the page at address "address" in the task "p",
286 * to see if it exists, and if it is clean. If so, share it with the current
287 * task.
288 *
289 * NOTE! This assumes we have checked that p != current, and that they
290 * share the same executable.
291 */
/*
* try_to_share() 在任務"p" 中檢查位于地址"address" 處的頁面，看頁面是否存在，是否干凈。
* 如果是干凈的話，就與當前任務共享。
*current 共享p 已有的物理頁面
* 注意！這里我們已假定p != 當前任務，并且它們共享同一個執(zhí)行程序。
*/
// address 是線性地址，是一個相對于code_start 的偏移量，在執(zhí)行完這個函數(shù)后，p 和current 偏移是
// address 的位置共享物理內(nèi)存!!!
292 static int try_to_share(unsigned long address, struct task_struct * p)
293 {
294 unsigned long from;
295 unsigned long to;
296 unsigned long from_page;
297 unsigned long to_page;
298 unsigned long phys_addr;
299
300 from_page = to_page = ((address>>20) & 0xffc); 計算相// 對于起始代碼偏移的頁目錄項數(shù)
// 加上自身的start_code 的頁目錄項，得到address 分別在p 和current 中對應的頁目錄項
301 from_page += ((p->start_code>>20) & 0xffc);
302 to_page += ((current->start_code>>20) & 0xffc);
303 /* is there a page-directory at from? */
/* 在from 處是否存在頁目錄？*/
304 from = *(unsigned long *) from_page; // 取頁目錄項的內(nèi)容
305 if (!(from & 1)) // 對應頁表是否存在
306 return 0;
// 取對應的頁表項
307 from &= 0xfffff000;
308 from_page = from + ((address>>10) & 0xffc);
309 phys_addr = *(unsigned long *) from_page;
310 /* is the page clean and present? */
/* 頁面干凈并且存在嗎？*/
311 if ((phys_addr & 0x41) != 0x01)
312 return 0;　　　
313 phys_addr &= 0xfffff000;
314 if (phys_addr >= HIGH_MEMORY || phys_addr < LOW_MEM) // 是否在主內(nèi)存塊中
315 return 0;
// 取頁目錄項內(nèi)容..to。如果該目錄項無效(P=0)，則取空閑頁面，并更新to_page 所指的目錄項?！?br />316 to = *(unsigned long *) to_page; // 取目標地址的頁目錄項
317 if (!(to & 1)) // 如果對應頁表不存在
318 if (to = get_free_page()) // 分配新的物理頁
319 *(unsigned long *) to_page = to | 7;
320 else
321 oom();
322 to &= 0xfffff000; // 取目標地址的頁表項
323 to_page = to + ((address>>10) & 0xffc);
324 if (1 & *(unsigned long *) to_page) // 如果對應頁表項已經(jīng)存在，則出錯，死循環(huán)
325 panic( "try_to_share: to_page already exists");
326 /* share them: write-protect */
/* 對它們進行共享處理：寫保護. */
327 *(unsigned long *) from_page &= ~2;
328 *(unsigned long *) to_page = *(unsigned long *) from_page; 共享物理內(nèi)存
// 　刷新頁變換高速緩沖。　
329 invalidate();
// 共享物理頁引用數(shù)加1
330 phys_addr -= LOW_MEM;
331 phys_addr >>= 12;
332 mem_map[phys_addr]++;
333 return 1;
334 }
335

7 頁面異常
當cpu 在進行內(nèi)存訪問時，可能因為缺頁或者試圖對一個只讀頁面進行寫操作而產(chǎn)生頁面異常，cpu
進入相應的頁面異常中斷處理程序。
由于異?？赡苡扇表摶蛘邔懼蛔x頁面產(chǎn)生，兩種情況的處理也是不同的，所以中斷處理程序首先應該
區(qū)分產(chǎn)生本次異常的原因，進入不同的處理過程。算法如下：
算法：page_fault
輸入：出錯碼error_code
出錯線性地址address
輸出：無
{
保存現(xiàn)場；
根據(jù)出錯碼判斷出錯原因；
if ( 缺頁)
作缺頁處理do_no_page(error_code, address);
else
作寫保護出錯處理do_wp_page(error_code, address)；
恢復現(xiàn)場；
return；
}
在x86 處理器中error_code 由cpu 產(chǎn)生并在保存了中斷點的相關內(nèi)容之后將其壓入堆棧，出錯碼的
最低位指示出錯原因（1：寫出錯；0：缺頁）。address 則是由一個專門的32 位寄存器cr2 保存。具體代
碼如下：
/mm/page.s
11
12 .globl _page_fault
13
14 _page_fault:
15 xchgl %eax,(%esp) // 交換eax 與esp 所指向空間的內(nèi)容=>1. 保存eax; 2. 取出error_code
16 pushl %ecx // 保存現(xiàn)場
17 pushl %edx
18 push %ds
19 push %es
20 push %fs
21 movl $0x10,%edx //(21～24行)使ds、es、fs指向系統(tǒng)數(shù)據(jù)段
22 mov %dx,%ds
23 mov %dx,%es
24 mov %dx,%fs
25 movl %cr2,%edx // 取出錯線性地址
26 pushl %edx // 將出錯地址和出錯碼壓入堆棧，作為處理函數(shù)的輸入?yún)?shù)
27 pushl %eax
28 testl $1,%eax // 判斷出錯碼最低位，決定調(diào)用函數(shù)
29 jne 1f 為// 1，調(diào)用寫保護出錯處理函數(shù)
30 call _do_no_page // 為0，調(diào)用缺頁處理函數(shù)
31 jmp 2f
32 1: call _do_wp_page
33 2: addl $8,%esp // 丟棄輸入?yún)?shù)error_code 和address
34 pop %fs // 恢復現(xiàn)場
35 pop %es
36 pop %ds
37 popl %edx
38 popl %ecx
39 popl %eax
40 iret
在這段代碼中，我們可以充分領略到系統(tǒng)程序員對匯編編程知識的要求。 在第15行xchgl %eax,(%
esp) ，必須非常清楚壓棧過程。當cpu 執(zhí)行壓棧操作時，是先執(zhí)行esp=esp-4; 再將數(shù)據(jù)送入esp 所指向
的單元。cpu 在進入異常中斷處理程序之前，將error_code 壓入了堆棧，當前esp 指向的單元存放的就是
error_code，所以第15 行的命令，取出了error_code 又將eax 保存了，如果要用其他方法實現(xiàn)應該是
pushl eax
movl (esp+4),eax
相比之下，15行的程序?qū)ax 放在了error_code 原來存放的空間，節(jié)約了堆棧空間，同時也節(jié)約指令
數(shù)，可謂是一箭四雕。在33 行 2: addl $8,%esp 對于輸入?yún)?shù)的丟棄，不是用兩次popl 操作，而是直接將
esp 加8，又省了一條指令。可見高水平的系統(tǒng)程序員為了提高效率是多么的摳門。這樣的程序雖然效率
高，但是對于理解會有一定的障礙，不過換個方向來想，畢竟這種底層代碼不是人人都會去仔細讀的。
7.1 缺頁中斷
在對進行進程初始設置時，內(nèi)核并不是將進程可能用到的所有內(nèi)存一次性分配給進程，而是在進程
要訪問該地址時分配，將內(nèi)存分配給一定會被訪問的空間，這樣就提高內(nèi)存資源的使用率。這樣作就不
可避免地會出現(xiàn)缺頁中斷。當cpu 訪問一個內(nèi)存單元時，如果該單元所在的頁面不在內(nèi)存中，cpu 將產(chǎn)生
頁面異常，進一步進入缺頁處理程序，算法如下：
算法：do_no_page
輸入：出錯碼error_code
出錯線性地址address
輸出：無
{
if ( 出錯進程沒有對應的可執(zhí)行文件
|| 出錯地址不在代碼和數(shù)據(jù)段)
{
分配物理頁面并映射到出錯線性地址( 使用get_empty_page())；
return；
}
試圖共享頁面( 使用share_page())；
if ( 共享頁面成功)
return ；
分配新的物理頁面(get_free_page())；
從可執(zhí)行文件中將頁面對應的內(nèi)容讀入內(nèi)存；
將頁面中不屬于代碼段和數(shù)據(jù)段的內(nèi)容清零；
將新的物理頁面映射到出錯線性地址(put_page())；
if ( 映射失敗)
{
釋放新申請的物理頁面；
顯示出錯，死循環(huán)；
}
return；
}
進程在不同的時刻會處于不同的狀態(tài)，如果進程此時還處于初始化時期，就可能還沒有設置對應的
可執(zhí)行文件，這個時候的內(nèi)存使用請求可能是與其設置有關的，所以需要為其分配內(nèi)存。
對于進程的可執(zhí)行文件，在這里只是說一下它的基本結(jié)構(gòu)：
進程對應的可執(zhí)行文件包含有進程的代碼段和數(shù)據(jù)段的內(nèi)容，進程的線性地址與可執(zhí)行文件內(nèi)容的
邏輯地址是對應的，如果出錯是在代碼段和數(shù)據(jù)段，應該先試圖共享內(nèi)存，共享不成功就應該分配內(nèi)存
并從可執(zhí)行文件中讀取相應內(nèi)容，；如果不是在這兩個段，就直接分配內(nèi)存。
可執(zhí)行文件存儲在磁盤上，磁盤的存儲基本單位是1KB，所以要讀取一個頁面的內(nèi)容就要讀取四個
磁盤塊。從可執(zhí)行文件中讀取內(nèi)容由bmap 和bread_page 兩個函數(shù)來作，首先將出錯線性地址所在頁面換
算成可執(zhí)行文件對應的邏輯盤塊號，bmap 用于將邏輯盤塊號換算成物理盤塊號，最后由bread_page 將四
個物理盤塊讀入內(nèi)存。
在讀入過程中，可能出現(xiàn)這種情況，由于線性地址太大，對應頁面換算得到的邏輯盤塊號過大，對
應可執(zhí)行文件卻沒有這么大（如下所示，這時后兩塊邏輯盤塊將不會被讀入），多余的邏輯盤將不會被讀
入。
另外，讀入一頁內(nèi)存之后，該頁的結(jié)束地址可能會超過end_data。
由于上述兩種情況，應該對多出來的內(nèi)存清零。
最后就是映射頁面，put_page 只有在申請新的頁表空間失敗的情況會返回0，這時就應該將已經(jīng)申請
了的物理頁面釋放，然后調(diào)用oom() 報錯。
具體代碼如下：
/mm/memory.c
365 void do_no_page(unsigned long error_code,unsigned long address)
366 {
367 int nr[4];
368 unsigned long tmp;
369 unsigned long page;
370 int block,i;
371
372 address &= 0xfffff000; 取// 頁面起始地址
373 tmp = address - current->start_code; // 換算出相對于進程代碼起始地址的相對地址
374 if (!current->executable || tmp >= current->end_data) { // 沒有對應可執(zhí)行文件或不在代碼和數(shù)據(jù)段
375 get_empty_page(address);
376 return;
377 }
// 到此處時一定是代碼和數(shù)據(jù)長度范圍內(nèi)
378 if (share_page(tmp)) // 嘗試共享內(nèi)存
379 return;
380 if (!(page = get_free_page())) // 分配新的物理內(nèi)存
381 oom();
382 /* remember that 1 block is used for header */
/* 記住，（程序）頭要使用1 個數(shù)據(jù)塊 */
383 block = 1 + tmp/BLOCK_SIZE; // 換算邏輯塊起始塊號
384 for (i=0 ; i<4 ; block++,i++) // 將邏輯塊號換算成物理塊號
385 nr[i] = bmap(current->executable,block);
386 bread_page(page,current->executable->i_dev,nr); // 讀入一個頁的四個磁盤塊
387 i = tmp + 4096 - current->end_data; // 對超出數(shù)據(jù)段的內(nèi)容清零
388 tmp = page + 4096;
389 while (i-- > 0) {
390 tmp--;
391 *(char *)tmp = 0;
392 }
393 if (put_page(page,address)) // 頁面映射
394 return;
395 free_page(page);
396 oom();
397 }
398

7.2 頁面寫保護錯誤
由于進程的fork 和share_page 操作，會出現(xiàn)多個進程共享一個物理頁面的情況，這個物理頁面被置
為只讀方式，如果其中一個進程想對這個頁面進行寫操作，cpu 就會產(chǎn)生頁面異常中斷，并進一步進入寫
保護出錯處理。
在寫保護出錯處理中，將會根據(jù)情況復制被共享的頁或者取消對頁面的寫保護。
算法：do_wp_page
輸入：出錯碼error_code
出錯線性地址address
輸出：無
{
if ( 出錯地址屬于進程的代碼段)
將進程終止；
if ( 出錯頁面屬于主內(nèi)存塊且共享計數(shù)為1)
{
取消寫保護；
刷新頁變換高速緩沖；
return；
}
申請一個新的物理頁；
if ( 出錯頁面屬于主內(nèi)存塊)
共享計數(shù)減1；
使出錯時的頁表項指向新的物理頁；
刷新頁變換高速緩沖；
復制共享頁的內(nèi)容到新的物理頁；
return；
}
對于一般情況，對代碼段的寫操作是違法的，肯定是進程本身代碼有問題，為了不進一步引起錯
誤，系統(tǒng)將會把該進程終止。但是estdio 庫（后來不再為linux 所使用）支持對代碼段的寫操作，linus 當
時由于沒有得到這個庫的具體資料，所以也只是預留了操作。
一個頁面被多個進程共享，每當一個進程產(chǎn)生一次寫保護 錯誤，內(nèi)核將給進程分配一個新的物理頁
面，將共享頁面的內(nèi)容復制過來，新的頁面將設置為可讀寫，而共享頁面仍然是只讀的，只是共享計數(shù)
減小了。當其他共享進程都產(chǎn)生了一次寫保護錯誤后，共享頁面的共享計數(shù)減成了1，其實就是被一個進
程獨占了，但此時該共享頁面仍然是只讀的，如果獨占它的進程對它進行寫操作仍然會產(chǎn)生寫保護出
錯。為什么不在共享計數(shù)減成了1 之后就將共享頁面置為可寫呢？原因很簡單，因為系統(tǒng)并不知道最后
是哪個頁表項指向這個共享頁，如果要把它查找出來會有很大的系統(tǒng)開銷，這是中斷處理程序應當盡量
避免的，所以采用了以逸待勞的辦法。
如果當初共享的頁面不屬于主內(nèi)存塊，在共享時就沒有作共享計數(shù)的處理，就不存在共享計數(shù)的問
題，直接復制就可以了。
/mm/memory.c
239
240 /*
241 * This routine handles present pages, when users try to write
242 * to a shared page. It is done by copying the page to a new address
243 * and decrementing the shared-page counter for the old page.
244 *
245 * If it's in code space we exit with a segment error.
246 */
/*
* 當用戶試圖往一個共享頁面上寫時，該函數(shù)處理已存在的內(nèi)存頁面，（寫時復制）
它是通過將頁面復制到一個新地址上并遞減* 原頁面的共享頁面計數(shù)值實現(xiàn)的。
*
* 如果它在代碼空間，我們就以段錯誤信息退出。
*/
247 void do_wp_page(unsigned long error_code,unsigned long address)
248 {
249 #if 0
250 /* we cannot do this yet: the estdio library writes to code space */
251 /* stupid, stupid. I really want the libc.a from GNU */
/* 我們現(xiàn)在還不能這樣做：因為estdio 庫會在代碼空間執(zhí)行寫操作 */
/* 真是太愚蠢了。我真想從GNU 得到libc.a 庫。*/
252 if (CODE_SPACE(address)) // 出錯地址屬于進程的代碼段，則終止當前程序
253 do_exit(SIGSEGV);
254 #endif
// 處理取消頁面保護。
// 輸入?yún)?shù)指向出錯頁的頁表項的指針
// 計算方法：
// 頁表偏移量+ 頁表起始地址
255 un_wp_page((unsigned long *)
256 (((address>>10) & 0xffc) + (0xfffff000 &*((unsigned long *) ((address>>20) &0xffc)))));
257
258
259 }
260
un_wp_page 的具體代碼也在/mm/memory.c 中
220
221 void un_wp_page(unsigned long * table_entry)
222 {
223 unsigned long old_page,new_page;
224
225 old_page = 0xfffff000 & *table_entry; // 取出錯頁面對應的物理地址
// 如果屬于主內(nèi)存塊且共享計數(shù)為1
226 if (old_page >= LOW_MEM && mem_map[MAP_NR(old_page)]==1) {
227 *table_entry |= 2; // 共享頁置為可寫
228 invalidate();
229 return;
230 }
231 if (!(new_page=get_free_page())) // 申請一個空閑物理頁面
232 oom();
233 if (old_page >= LOW_MEM) 如果在// 主內(nèi)存塊中，將共享數(shù)減1
234 mem_map[MAP_NR(old_page)]--;
235 *table_entry = new_page | 7; // 改變table_entry 的指向從而實現(xiàn)共享的分離
236 invalidate();
237 copy_page(old_page,new_page); // 拷貝共享頁
238 }
239
8 桶結(jié)構(gòu)
8.1 桶結(jié)構(gòu)定義與初始化
在C 語言中，malloc（int size）用于在用戶空間為某個大小為size 的結(jié)構(gòu)申請一塊相應的內(nèi)存空間，
在內(nèi)核中很多時候也需要為內(nèi)核的數(shù)據(jù)結(jié)構(gòu)分配內(nèi)存空間。對于內(nèi)核來說，用戶進程分配內(nèi)存空間的操
作與用戶的普通的內(nèi)存訪問操作并沒有區(qū)別，在用戶分配空間時，內(nèi)核只需要關心是否超出了用戶的虛
擬地址空間就行了。內(nèi)核給自己分配內(nèi)存空間就不同了，內(nèi)核要對物理內(nèi)存進行管理，對這種小量的內(nèi)
存分配尤其需要仔細管理。
要管理，干脆就將將一部分內(nèi)存頁分成指定大小的塊，大小是1、2、3、4、5 ⋯，當內(nèi)核申請時就
從含有對應大小塊的內(nèi)存中取出一塊分配出去，比如：當內(nèi)核申請一個大小為3 的空間時，就從被分成
了大小為3 的塊的內(nèi)存頁中取一個塊來分配。這就是桶結(jié)構(gòu)結(jié)構(gòu)的基本思想。將內(nèi)存頁看成是桶，桶里
面裝的是相同大小的內(nèi)存塊。
如果使用1、2、3、4 ⋯這樣的內(nèi)存塊大小進行管理，頁面的利用率會很低，可能一個頁面只會被申
請很少幾個結(jié)構(gòu)，這樣將造成很大的內(nèi)存浪費。塊的分配很大程度決定了桶結(jié)構(gòu)的空間使用效率，經(jīng)過
理論計算和長期的實際運行證明，采用2 的冪次作為塊的大小具有理想的效果。linux0.11 采用的就是這
種分塊方式，根據(jù)實際情況，從16、32、64 ⋯一直到一個頁的大小4096 B，在分配時分配能滿足需求的
最小的塊。
對于每個桶，應該有一個結(jié)構(gòu)記錄它的信息，以及與其他桶之間的關系。linux0.11 中定義了一個叫
桶描述符的結(jié)構(gòu)，具體結(jié)構(gòu)如下：
/lib/malloc.c
52 struct bucket_desc { /* 16 bytes */ /* 本結(jié)構(gòu)占16 個字節(jié)*/
53 void *page; // 對應頁面起始地址
54 struct bucket_desc *next; // 指向下一個描述符的指針
55 void *freeptr; // 指向本桶中空閑內(nèi)存塊鏈表的指針
56 unsigned short refcnt; // 引用計數(shù)
57 unsigned short bucket_size; // 本描述符對應內(nèi)存塊的大小
58 };
為了方便查找，內(nèi)核分別將相同塊大小的桶串成一條鏈，鏈表頭結(jié)構(gòu)如下：
60 struct _bucket_dir { /* 8 bytes */ /* 本結(jié)構(gòu)占8 個字節(jié)*/
61 int size; // 本鏈中桶對應的內(nèi)存塊的大小( 字節(jié)數(shù))
62 struct bucket_desc *chain; // 本鏈中的桶描述符鏈表頭指針
63 };
同時還有一個數(shù)組用于保存所有的鏈表頭：
77 struct _bucket_dir bucket_dir[] = {
78 { 16, (struct bucket_desc *) 0}, // 16 字節(jié)長度的內(nèi)存塊。
79 { 32, (struct bucket_desc *) 0}, // 32 字節(jié)長度的內(nèi)存塊。
80 { 64, (struct bucket_desc *) 0}, // 64 字節(jié)長度的內(nèi)存塊。
81 { 128, (struct bucket_desc *) 0}, // 128 字節(jié)長度的內(nèi)存塊。
82 { 256, (struct bucket_desc *) 0}, // 256 字節(jié)長度的內(nèi)存塊。
83 { 512, (struct bucket_desc *) 0}, // 512 字節(jié)長度的內(nèi)存塊。
84 { 1024, (struct bucket_desc *) 0}, // 1024 字節(jié)長度的內(nèi)存塊。
85 { 2048, (struct bucket_desc *) 0}, // 2048 字節(jié)長度的內(nèi)存塊。
86 { 4096, (struct bucket_desc *) 0}, // 4096 字節(jié)(1 頁) 內(nèi)存。
87 { 0, (struct bucket_desc *) 0}
}; /* End of list marker */
88
這幾級結(jié)構(gòu)關聯(lián)的結(jié)果如圖：
在初始化時，系統(tǒng)并不分配任何內(nèi)存作為桶，而是在請求發(fā)生時才分配內(nèi)存。在分配內(nèi)存作為桶
時，也要分配一個 bucket_desc 結(jié)構(gòu)，如果這個結(jié)構(gòu)的分配與一般的內(nèi)核分配請求一樣，就有可能進入一
個死循環(huán)：分配函數(shù)自身也在請求分配。所以 對于bucket_desc 結(jié)構(gòu)需要獨立的分配機制。
專門分配一個頁用于存放bucket_desc，當需要時就從這個頁面中分配一個bucket_desc 結(jié)構(gòu)。在初始
化時，將所有結(jié)構(gòu)利用他們自身的next 指針連成一個鏈表，用一個指針指向鏈表頭。這個指針的定義
為：
92 struct bucket_desc *free_bucket_desc = (struct bucket_desc *) 0;
這樣就連成了下圖的結(jié)構(gòu)：
bucket_desc 專用頁的初始化函數(shù)的算法為：
算法： init_bucket_desc
輸入：無
輸出：無
{
申請一個空閑頁（get_free_page）；
for（每一個bucket_desc 結(jié)構(gòu)）
{
if（不是最后一個bucket_desc 結(jié)構(gòu)）
next 指向下一個bucket_desc 結(jié)構(gòu)；
}
使最后一項的next 指針指向free_bucket_desc 指向的內(nèi)容；
使free_bucket_desc 指向第一個bucket_desc 結(jié)構(gòu)；
return ；
}
一般情況下，這個初始化程序是在鏈表為空，即free_bucket_desc 為NULL 時才會被調(diào)用。內(nèi)核中的
數(shù)據(jù)結(jié)構(gòu)，尤其是鏈表，需要考慮多任務調(diào)度可能造成內(nèi)核數(shù)據(jù)結(jié)構(gòu)不一致的情況，對于get_free_page
這種操作，如果系統(tǒng)引入了虛擬內(nèi)存管理之后，很可能會導致當前執(zhí)行進程進入睡眠等待內(nèi)存，在這個
進程被激活之前，在其他進程執(zhí)行時，內(nèi)核可能會因為結(jié)構(gòu)分配而再次調(diào)用到init_bucket_desc，如果這
時順利執(zhí)行了，專用頁被分配了，在睡眠的進程重新運行時，仍然會去改變bucket_desc 鏈表。為了避免
出錯，在程序結(jié)構(gòu)上要特別處理。一種方案是：在改變鏈表前檢查free_bucket_desc 是否還是NULL，如
果不是，就成功退出，如果是，就該進行對鏈表的操作；linux0.11 并沒有采用這種方案，而是繼續(xù)對鏈
表操作，最后并不是直接的對free_bucket_desc 賦值，而是向鏈表頭部加入內(nèi)容的操作，這樣就避免內(nèi)核
數(shù)據(jù)結(jié)構(gòu)的不一致。
我們假設進程A 執(zhí)行時系統(tǒng)進入init_bucket_desc，并在申請頁面（get_free_page）時被阻塞。之后進
程B 運行，系統(tǒng)又進入 init_bucket_desc，順利執(zhí)行完后退出，這時內(nèi)核中空閑bucket_desc 鏈表如下：
進程A 恢復執(zhí)行后，從get_free_page 中返回，繼續(xù)執(zhí)行完 init_bucket_desc 函數(shù)，經(jīng)過最后兩個操作
（向鏈表頭部加入內(nèi)容的操作）之后將兩個頁面連接到了一起：
當讀到后面8.2 的代碼后，會發(fā)現(xiàn)這些考慮在linux0.11 中并不需要，這正是體現(xiàn)了linux 設計的嚴
謹。
/lib/malloc.c
93
94 /*
95 * This routine initializes a bucket description page.
96 */
/*
下面的* 程序用于初始化一頁桶描述符頁面。
*/
97 static inline void init_bucket_desc()
98 {
99 struct bucket_desc *bdesc, *first;
100 int i;
101
102 first = bdesc = (struct bucket_desc *) get_free_page(); // 申請一頁內(nèi)存,first 指向頁基址
103 if (!bdesc)
104 panic( "Out of memory in init_bucket_desc()");
105 for (i = PAGE_SIZE/sizeof(struct bucket_desc); i > 1; i--) { // 將頁中的bucket_desc 結(jié)構(gòu)連成鏈表
106 bdesc->next = bdesc+1;
107 bdesc++;
108 }
109 /*
110 * This is done last, to avoid race conditions in case
111 * get_free_page() sleeps and this routine gets called again....
112 */
/*
* 這是在最后處理的，目的是為了避免在get_free_page() 睡眠時該子程序又被
* 調(diào)用而引起的競爭條件。
*/
// 將新頁的鏈表連入系統(tǒng)的空閑bucket_desc 鏈表
113 bdesc->next = free_bucket_desc;
114 free_bucket_desc = first;
115 }
116
在桶頁面內(nèi)部，所有的空閑內(nèi)存塊也是串成了
一個鏈表，桶描述符中的freeptr 指向鏈表頭。使用
下面的代碼初始化桶頁面就有了右圖所示的結(jié)構(gòu)：
(void *) cp = get_free_page();
160 for (i=PAGE_SIZE/bdir->size; i > 1; i--) {
161 *((char **) cp) = cp + bdir->size;
162 cp += bdir->size;
163 }
164 *((char **) cp) = 0;

8.2 桶內(nèi)存塊的分配
在標準的C 函數(shù)中使用malloc（int len）進行內(nèi)存塊分配，在linux0.11 中使用了一個同名的函數(shù)
malloc（int len）進行內(nèi)核的內(nèi)存塊分配。為了避免混淆，在0.98 版內(nèi)核之后采用了kmalloc（int size）。
相對應的linux0.11 中的內(nèi)核內(nèi)存塊釋放函數(shù)free_s 也改名為kfree_s。
了解了桶的組織結(jié)構(gòu)，分配內(nèi)存塊的算法就不難理解了。
算法：malloc
輸入：申請內(nèi)存塊大小len
輸出：如果成功，返回內(nèi)存塊指針；失敗則返回NULL；
{
查找一個桶鏈表，鏈表中 桶的內(nèi)存塊是能夠滿足要求的最小塊；
if（沒有搜索到符合要求的鏈）
{
打印出錯信息：請求塊過大；
進入死循環(huán)；
}
關中斷；
在鏈表中查詢還有空閑內(nèi)存塊的桶；
if（鏈表中所有桶都沒有空閑的內(nèi)存塊）
{
if（沒有空閑桶描述符）
初始化一個頁面用作桶描述符（init_bucket_desc）；
從空閑桶描述符鏈表中分配一個桶描述符；
分配一個新物理頁面作為桶；
初始化桶頁面；
設置桶描述符指針；
將新桶連入對應的鏈表；
}
從桶中分配一個空閑內(nèi)存塊；
開中斷；
return 空閑內(nèi)存塊指針；
}
桶結(jié)構(gòu)最大能夠分配的內(nèi)存塊的大小是4KB，如果這個大小都還不能滿足要求，那么肯定是出問題
了。內(nèi)核中不可能申請這么大的內(nèi)存塊。
之后的操作是在中斷關閉的狀態(tài)下執(zhí)行的，所以就不會因為進程切換導致數(shù)據(jù)結(jié)構(gòu)不一致的情況。似
乎init_bucket_desc 中關于避免進程切換的安排是多余的，但是使用關中斷作為避免競爭的手段是低效
的，尤其是在中間執(zhí)行過程復雜的情況下。如果以后引入虛存管理之后，可能必須有進程切換，到時就
不能使用關中斷了。所以提前在程序結(jié)構(gòu)上作安排才是正確之道。
/lib/malloc.c
116
117 void *malloc(unsigned int len)
118 {
119 struct _bucket_dir *bdir;
120 struct bucket_desc *bdesc;
121 void *retval;
122
123 /*
124 * First we search the bucket_dir to find the right bucket change
125 * for this request.
126 */
/*
首先我們搜索存儲桶目錄* bucket_dir 來尋找適合請求的桶大小。
*/
127 for (bdir = bucket_dir; bdir->size; bdir++) // 尋找合適的鏈表：(bdir->size)/2<len<=bdir->size
128 if (bdir->size >= len)
129 break;
130 if (!bdir->size) { // 鏈表頭數(shù)組最后一項是NULL
131 printk( "malloc called with impossibly large argument (%d)/n", len);
132
133 panic( "malloc: bad arg");
134 }
135 /*
136 * Now we search for a bucket descriptor which has free space
137 */
/*
* 現(xiàn)在我們來搜索具有空閑空間的桶描述符。
*/
138 cli(); /* Avoid race conditions */ /* 為了避免出現(xiàn)競爭條件 */ // 關中斷
139 for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) // 尋找還有空閑內(nèi)存塊的桶
140 if (bdesc->freeptr)
141 break;
142 /*
143 * If we didn't find a bucket with free space, then we'll
144 * allocate a new one.
145 */
/*
* 如果沒有找到具有空閑空間的桶描述符，那么我們就要新建立一個該目錄項的描述符。
*/
146 if (!bdesc) {
147 char *cp;
148 int i;
149
150 if (!free_bucket_desc) // 沒有空閑桶描述符
151 init_bucket_desc();
152 bdesc = free_bucket_desc; // 取一個空閑桶描述符
153 free_bucket_desc = bdesc->next;
154 bdesc->refcnt = 0; 設// 置新的桶描述符
155 bdesc->bucket_size = bdir->size;
156 bdesc->page = bdesc->freeptr = (void *) cp = get_free_page();
157 if (!cp) // 頁面申請失敗
158 panic( "Out of memory in kernel malloc()");
159 /* Set up the chain of free objects */
/* 在該頁空閑內(nèi)存中建立空閑對象鏈表 */
160 for (i=PAGE_SIZE/bdir->size; i > 1; i--) {
161 *((char **) cp) = cp + bdir->size;
162 cp += bdir->size;
163 }
164 *((char **) cp) = 0; 最后一項的指針為NULL
165 bdesc->next = bdir->chain; /* OK, link it in! */ /* OK，將其鏈入！*/
166 bdir->chain = bdesc;
167 }
// 分配一個空閑內(nèi)存塊
168 retval = (void *) bdesc->freeptr;
169 bdesc->freeptr = *((void **) retval);
170 bdesc->refcnt++;
171 sti(); /* OK, we're safe again */ /* OK，現(xiàn)在我們又安全了*/ // 開中斷
172 return(retval);
173 }
174
8.3 桶內(nèi)存塊的回收
當使用完內(nèi)存塊之后，內(nèi)核將釋放內(nèi)存塊。申請時內(nèi)核知道需要的內(nèi)存塊的大小，在釋放時卻不一
定知道要釋放的這塊內(nèi)存的大小是多少。如果沒有指定要釋放的內(nèi)存塊的大小，怎么確定要釋放內(nèi)存塊
的大小呢？在釋放時必然會指定內(nèi)存塊的地址，這個地址唯一的對應了一個物理頁面，也就是唯一對應
了一個桶，這個桶的描述符中就記錄了內(nèi)存塊的大小。在linux0.11 中使用free_s(void *obj, int size) 來釋
放內(nèi)存塊，如果不指定大小，輸入?yún)?shù)size 是0
算法：free_s
輸入：釋放對象指針obj
釋放對象大小size（如果是0，表示沒有指定大?。?br />輸出：無
{
for（每一個桶鏈表）{
if（鏈表中桶的內(nèi)存塊大小< 釋放對象大小）
continue；
for（每一個桶）
if（是釋放對象對應的桶）
退出搜索；
}
if（搜索桶失?。?br />顯示出錯信息，死循環(huán)；
關中斷；
將要釋放的內(nèi)存塊鏈入桶的空閑鏈表；
修改桶的相關信息；
if（桶中所有的內(nèi)存塊都是空閑的）
{
釋放桶對應的內(nèi)存塊；
釋放桶對應的描述符；
}
開中斷；
return；
}
可以看出在搜索時，如果輸入?yún)?shù)size 為0，將會一次搜索不同size 的桶鏈表。如果指定了size，搜
索速度就會大幅度提高。但在內(nèi)核中仍然提供了對不指定大小的釋放操作：
/include/linux/kernel.h
12 #define free(x) free_s((x), 0)
當正是釋放內(nèi)存塊時，關閉了中斷，仍然是為了避免進程切換造成數(shù)據(jù)結(jié)構(gòu)的不一致。free_s 的代碼
如下：
/lib/malloc.c
174
175 /*
176 * Here is the free routine. If you know the size of the object that you
177 * are freeing, then free_s() will use that information to speed up the
178 * search for the bucket descriptor.
179 *
180 * We will #define a macro so that "free(x)" is becomes "free_s(x, 0)"
181 */
/*
* 下面是釋放子程序。如果你知道釋放對象的大小，則free_s() 將使用該信息加速
* 搜尋對應桶描述符的速度。
*
* 我們將定義一個宏，使得"free(x)" 成為"free_s(x, 0)"。
*/
182 void free_s(void *obj, int size)
183 {
184 void *page;
185 struct _bucket_dir *bdir;
186 struct bucket_desc *bdesc, *prev;
187
188 /* Calculate what page this object lives in */
/* 計算該對象所在的頁面 */
189 page = (void *) ((unsigned long) obj & 0xfffff000);
190 /* Now search the buckets looking for that page */
/* 現(xiàn)在搜索存儲桶目錄項所鏈接的桶描述符，尋找該頁面 */
191 for (bdir = bucket_dir; bdir->size; bdir++) {
192 prev = 0; // 如果是0，則搜索到的桶是鏈表的第一個桶
193 /* If size is zero then this conditional is always false */
/* 如果參數(shù)size 是0，則下面條件肯定是false */
194 if (bdir->size < size)
195 continue;
196 for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) {
197 if (bdesc->page == page)
198 goto found; // 退出搜索
199 prev = bdesc;
200 }
201 }
202 panic( "Bad address passed to kernel free_s()"); // 如果搜索失敗
203 found:
204 cli(); /* To avoid race conditions */ /* 為了避免競爭條件 */
205 *((void **)obj) = bdesc->freeptr; // 鏈入空閑塊鏈表
206 bdesc->freeptr = obj;
207 bdesc->refcnt--;
208 if (bdesc->refcnt == 0) {
209 /*
210 * We need to make sure that prev is still accurate. It
211 * may not be, if someone rudely interrupted us....
212 */
/*
* 我們需要確信prev 仍然是正確的，若某程序粗魯?shù)刂袛嗔宋覀?br />* 就有可能不是了。
*/
213 if ((prev && (prev->next != bdesc)) || (!prev && (bdir->chain != bdesc)))
214
215 for (prev = bdir->chain; prev; prev = prev->next)
216 if (prev->next == bdesc)
217 break;
218 if (prev)
219 prev->next = bdesc->next;
220 else { // prev 如果是0，則搜索到的桶是鏈表的第一個桶
221 if (bdir->chain != bdesc)
222 panic( "malloc bucket chains corrupted");
223 bdir->chain = bdesc->next;
224 }
225 free_page((unsigned long) bdesc->page); 釋// 放對應內(nèi)存頁面
226 bdesc->next = free_bucket_desc; // 將桶描述符鏈入空閑桶描述符鏈表
227 free_bucket_desc = bdesc;
228 } /* 208 if (bdesc->refcnt == 0)*/
229 sti(); // 開中斷
230 return;
231 }
232

內(nèi)存9 使用情況統(tǒng)計
通過前面的介紹，對于linux0.11 內(nèi)存管理機制有了整體的了解。有時候需要對主內(nèi)存塊的使用情況
作統(tǒng)計。統(tǒng)計的項目有：當前主內(nèi)存塊還有多少空閑頁面；分配了的物理頁面在4G 的虛擬內(nèi)存空間中的
分布情況。
對于第一個項目，只需要對 主內(nèi)存塊映射數(shù)組mem_map 的空閑項進行統(tǒng)計。對于第二個項目，需要
對4G 的虛存空間進行查詢，必須查頁目錄表和頁表。通過頁目錄表查每個頁表的所有項，通過判斷每個
頁表項的有效位(P) 統(tǒng)計每個頁表中映射有多少個物理頁面。第一節(jié)曾經(jīng)談到內(nèi)核將16M 的物理內(nèi)存映
射到第0～3個頁表上從而實現(xiàn)對物理內(nèi)存的控制，在這里這幾個頁表是沒有必要查詢的，因為始終是
頁表的1024 項都映射了物理頁面。但是linux0.11 也對2、3 兩個頁表進行了統(tǒng)計，只跳過了0、1 兩個頁
表。以下便是統(tǒng)計函數(shù)calc_mem(void)
/mm/memory.c
// 計算主內(nèi)存塊中空閑頁面數(shù)并統(tǒng)計每個頁表中映射了的物理頁面數(shù)。
413 void calc_mem(void)
414 {
415 int i,j,k,free=0;
416 long * pg_tbl;
417
// 掃描映射數(shù)組mem_map[]，統(tǒng)計主內(nèi)存塊中的空閑頁面數(shù)并顯示。
418 for(i=0 ; i<PAGING_PAGES ; i++)
419 if (!mem_map[i]) free++;
420 printk( "%d pages free (of %d)/n/r",free,PAGING_PAGES);
// 掃描所有頁目錄項（除0，1 項），如果頁目錄項有效，則統(tǒng)計對應頁表中有效頁面數(shù)，并顯示。
421 for(i=2 ; i<1024 ; i++) {
422 if (1&pg_dir[i]) {
423 pg_tbl=(long *) (0xfffff000 & pg_dir[i]);
424 for(j=k=0 ; j<1024 ; j++)
425 if (pg_tbl[j]&1)
426 k++;
427 printk( "Pg-dir[%d] uses %d pages/n",i,k);
428 }
429 }
430 }