內存的管理與演算法

㈠ 計算機管理內存的方法有哪些優缺點是什麼

內存管理是操作系統最重要的一部分，它決定了操作系統的性能。為了說明如何進行內存訪問的操作，有必要先介紹有關內存管理的一些術語及背景。

2.1 虛擬內存

所謂虛擬內存就是用硬碟空間來彌補計算機物理內存不足的技術。Windows操作系統用虛擬內存來動態管理運行時的交換文件。為了提供比實際物理內存還多的內存容量，Windows操作系統佔用了硬碟上的一部分空間作為虛擬內存。當CPU有要求時，首先會讀取內存中的資料。當內存容量不夠用時，Windows就會將需要暫時存儲的數據寫入硬碟。所以，計算機的內存大小等於實際物理內存容量加上「分頁文件」（就是交換文件）的大小。Windows 98中分頁文件名採用Win386.swp形式，而Windows 2K/XP/2003中採用pagefile.sys，默認位於系統分區的根目錄下，具有隱藏屬性。如果需要的話，「分頁文件」會動用硬碟上所有可以使用的空間。

安裝好Windows以後，系統採用默認的設置自動處理虛擬內存，為了優化系統的 工作性能，根據Windows操作系統中虛擬內存的設置方法，可以自己動手設置內存管理參數。

2.2 CPU工作模式

計算機系統有不同的工作模式，在不同的模式下，CPU的定址方式是不一樣的，通常見到的CPU工作模式如下所述。

2.2.1．實模式

實模式是為了Pentium處理器與8086／8088兼容而設置的。8086和8088隻能工作於實模式，而80286及以上的處理器可工作於實模式或者保護模式下。實模式操作方式只允許微處理器定址第一個1MB的存儲空間，從0x00000～0xFFFFF。在實模式下的存儲器定址是段地址＋偏移地址。例如段寄存器的內容是0x1000，則它定址開始於0x10000的段，偏移量大小從0x0000～0xFFFF，即偏移量的空間大小是216=64KB。

2.2.2．保護地址模式

保護地址模式又稱為虛擬地址存儲管理方式。保護模式下主要有兩種特徵。
（1）內存分段管理
在保護模式下，各個16位的段寄存器裡面放置的是選擇符。各項任務共享的內存空間由全局選擇符來索引；而某個任務獨立使用的內存空間由局部選擇符來索引。由選擇符的高13位作為偏移量，再以CPU內部事先初始化好的GDTR（全局描述符表寄存器）中的32位基地址為基，可以獲得相應的描述符。由描述符中的線性地址決定段的基地址。再利用指令（或其他方式）給出的偏移量，便可以得到線性地址，即
線性地址=段線性基地址+偏移量
保護模式採用上面介紹的分段管理，可以實現的存儲器定址范圍為4GB，通常把通過段變換獲得的地址稱為線性地址。這種線性地址是同32位物理地址對應的，為了獲得更大的定址范圍，還可以對線性地址實行分頁管理。在保護模式下，處理器通過CRO控制寄存器的PG（page）位進行管理，當PG=0時，由段變換獲得的線性地址可直接作為物理地址使用；若PG=1，則進一步進行頁變換。
（2）內存分頁管理

分頁管理的基本思想是將內存分為大小固定為4KB或者1MB的若干頁，通過一定機制對內存進行管理。與前面的分段管理類似，程序或數據將根據其長度分配若干頁。為了進行頁面管理，在分頁管理機制中採用了頁表、頁目錄對線性地址作頁變換。

2.3 邏輯、線性和物理地址

在保護地址模式下，經常遇到三種地址：邏輯地址（Logical Address）、線性地址（Linear Address）和物理地址（Physical Address）。CPU通過分段機制將邏輯地址轉換為線性地址，再通過分頁機制將線性地址轉換為物理地址。
（1）邏輯地址
這是內存地址的精確描述，通常表示為十六進制：xxxx:YYYYYYYY，這里xxxx為selector（選擇器），而YYYYYYYY是針對selector所選擇的段地址的線性偏移量。除了指定xxxx的具體數值外，還可使用具體的段寄存器的名字來替代，如CS（代碼段），DS（數據段），ES（擴展段），FS（附加數據段#1），GS（附加數據段#2）和SS（堆棧段）。這些符號都來自舊的「段：偏移量」風格，在 8086 實模式下使用此種方式來指定「far pointers」（遠指針）。
（2）線性地址
線性地址是邏輯地址到物理地址變換之間的中間層，是處理器可定址的內存空間（稱為線性地址空間）中的地址。程序代碼會產生邏輯地址，或者說是段中的偏移地址，加上相應段的基地址就生成了一個線性地址。
如果啟用了分頁機制，那麼線性地址可以再經變換以產生一個物理地址。若沒有啟用分頁機制，那麼線性地址直接就是物理地址。不過，在開啟分頁功能之後，一個線性地址可能沒有相對映的物理地址，因為它所對應的內存可能被交換到硬碟中。32位線性地址可用於定位4GB存儲單元。
（3）物理地址

所謂物理地址，就是指系統內存的真正地址。對於32 位的操作系統，它的范圍為0x00000000～0xFFFFFFFF，共有4GB。只有當CPU工作於分頁模式時，此種類型的地址才會變得非常「有趣」。本質上，一個物理地址是CPU插腳上可測量的電壓。操作系統通過設立頁表將線性地址映射為物理地址。Windows 2K/XP所用頁表布局的某些屬性對於調試軟體開發人員非常有用。

2.4 存儲器分頁管理機制

程序代碼和數據必須駐留在內存中才能得以運行，然而系統內存量很有限，往往不能容納一個完整程序的所有代碼和數據，特別是在多任務系統中，如Windows，可能需要同時打開多個執行程序，如畫圖程序，瀏覽器等，想讓內存駐留所有這些程序顯然不大可能，因此首先能想到的就是將程序分割成小部分，只讓當前系統運行它所有需要的那部分留在內存，其他部分都留在硬碟（虛擬內存）。當系統處理完當前任務片段後，再從外存中調入下一個待運行的任務片段。於是，存儲器分頁管理機制隨之而被發明。
如前所述，在保護模式下，控制寄存器CR0中的最高位PG位控制分頁管理機制是否生效。如果PG=1，分頁機制生效，把線性地址轉換為物理地址。如果PG=0，分頁機制無效，線性地址就直接作為物理地址。必須注意，只有在保護方式下分頁機制才可能生效。只有在保證使PE位為1的前提下，才能夠使PG位為1，否則將引起通用保護 故障。

分頁機制把線性地址空間和物理地址空間分別劃分為大小相同的塊。這樣的塊稱為頁。通過在線性地址空間的頁與物理地址空間的頁之間建立映射，分頁機制可以實現線性地址到物理地址的轉換。線性地址空間的頁與物理地址空間的頁之間的映射可根據需要來確定。線性地址空間的任何一頁，可以映射為物理地址空間中的任何一頁。

2.5 線性地址到物理地址的轉換

線性地址空間的頁到物理地址空間的頁之間的映射用表來描述。目前所見到的有4KB和1MB大小的物理分頁，對於4KB頁面的分頁，線性地址到物理地址的轉換過程如圖所示。對於1MB頁面分頁，線性地址到物理地址的轉換與4KB的基本相似，不同的是線性地址的低22位對應一個物理頁面。

對於4KB頁面的線性地址到物理地址的轉換示意圖

對於4KB頁面分頁，頁映射表的第一級稱為頁目錄表，存儲在一個物理頁中。頁目錄表共有1024個頁目錄項（PDE，page directory entry），其中，每個PDE為4位元組長，包含對應第二級表所在物理地址空間頁的頁碼。頁映射表的第二級稱為頁表，每張頁表也被存儲在一個物理頁中。每張頁表有1024個頁表項（PTE，page table entry），每個PTE為4位元組長，其中PTE的低12位用來存放諸如「頁是否存在於內存」或「頁的許可權」等信息。

一個線性地址大小為4個位元組（32bit），包含著找到物理地址的信息，分為3個部分：第22位到第31位這10位（最高10位）是頁目錄中的索引，第12位到第21位這10位是頁表中的索引，第0位到第11位這12位（低12位）是頁內偏移。在把一個線性地址轉換成物理地址時，CPU首先根據CR3中的值，找到頁目錄所在的物理頁。然後根據線性地址的第22位到第31位這10位（最高的10bit）的值作為索引，找到相應的PDE，其中含有這個虛擬地址所對應頁表的物理地址。有了頁表的物理地址，再把虛擬地址的第12位到第21位這10位的值作為索引，找到該頁表中相應的PTE，其中就有這個虛擬地址所對應物理頁的物理地址。最後用線性地址的最低12位，也就是頁內偏移，加上這個物理頁的物理地址，就得到了該線性地址所對應的物理地址。

㈡ 可變分區管理內存分配演算法有那些,各有什麼有缺點

連續分配： 首次適應演算法（較快，簡單，碎片多），最大適應分配演算法（以期不留下小碎片）， 最佳適應分配演算法（慢，復雜，碎片少）。 都需要碎片整理。
離散分配：分段管理（邏輯性好），分頁管理，段頁式管理（最好，當然也復雜）。

㈢ 一個完整單例所涉及的內存管理方法都有哪些

好像是求命中率和重新調用率啊,應該要畫圖的
題目意思是1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5有這樣一個進程頁面序列的請求,裡面的數字是頁號,而內存里只能存放3頁,然後採用先來先服務的原則,畫個圖,橫坐標是那個序列,縱坐標表示那能放的3個頁,然後比如前三個是1,2,3然後就在上面畫上3個叉,表示沒有被內存命中(因為剛開始內存為空,所以都要調如內存),然後這是初始化(調滿三個頁),然後縱的畫一跟線,表示初始化完了開始正式作業,比如第4個請求是4,但內存里分別是1,2,3這三個頁,所以要重調,根據先來先走的原則,內存清掉1這個頁面來存放4這個頁面,然後在在4上面畫個叉怠骸壁忌撰渙辯惟菠隸,再處理下一個第五個請求又是1,於是就要把2換掉變成1,依次類推.....當作到第8個請求是1這個頁面時,內存里應該是1,2,5這幾個頁面,於是這時就不用再重調了,因為內存里有,這個就叫命中了,在這個1頁面上畫圈,這個樣子做完以後,就是數數了,要求替換率就是用叉的數目除以總的頁面請求數
LRU好像是最近最久未使用演算法,就是把用的多的留下,也是畫個圖,然後比較2種演算法
雖然我們上課是用的中文,沒做過這類英文題,但應該是這個意思了

㈣ 簡述內存管理中buddy演算法和slab機制的區別

1、Buddy演算法
linux對空閑內存空間管理採取buddy演算法，
Buddy演算法：
把內存中所有頁面按照2^n劃分，其中n=0~5，每個內存空間按1個頁面、2個頁面、4個頁面、8個頁面、16個頁面、32個頁面進行六次劃分。劃分後形成了大小不等的存儲塊，稱為頁面塊，簡稱頁塊，包含一個頁面的頁塊稱為1頁塊，包含2個頁面的稱為2頁塊，依次類推。
每種頁塊按前後順序兩兩結合成一對Buddy「夥伴」。系統按照Buddy關系把具有相同大小的空閑頁面塊組成頁塊組，即1頁塊組、2頁塊組……32頁塊組。 每個頁塊組用一個雙向循環鏈表進行管理，共有6個鏈表，分別為1、2、4、8、16、32頁塊鏈表。分別掛到free_area[] 數組上。
點陣圖數組
用於標記內存頁面使用情況，第0組每一位表示單個頁面使用情況，1表示使用，0表示空閑，第二組每一位表示比鄰的兩個頁面使用情況，一次類推。默認為10個數組，當一對Buddy的兩個頁面中有一個事空閑的，而另一個全部或部分被佔用時，該位置1.兩個頁面塊都是空閑，對應位置0.
內存分配和釋放過程
內存分配時，系統按照Buddy演算法，根據請求的頁面數在free_area[]對應的空閑頁塊組中搜索。 若請求頁面數不是2的整數次冪，則按照稍大於請求數的2的整數次冪的值搜索相應的頁面塊組。
當相應頁塊組中沒有可使用的空閑頁面塊時就查詢更大一些的頁塊組，在找到可用的頁塊後分配所需要的頁面。當某一空閑頁面被分配後，若仍有剩餘的空閑頁面，則根據剩餘頁面的大小把他們加入到相應頁面組中。
內存頁面釋放時，系統將其作為空閑頁面看待，檢查是否存在與這些頁面相鄰的其他空閑頁塊，若存在，則合為一個連續的空閑區按Buddy演算法重新分組。

2、Slab演算法
採用buddy演算法，解決了外碎片問題，這種方法適合大塊內存請求，不適合小內存區請求。如：幾十個或者幾百個位元組。Linux2.0採用傳統內存分區演算法，按幾何分布提供內存區大小，內存區以2的冪次方為單位。雖然減少了內碎片，但沒有顯著提高系統效率。
Linux2.4採用了slab分配器演算法，該演算法比傳統的分配器演算法有更好性能和內存利用率，最早在solaris2.4上使用。
Slab分配器思想
1）小對象的申請和釋放通過slab分配器來管理。
2）slab分配器有一組高速緩存，每個高速緩存保存同一種對象類型，如i節點緩存、PCB緩存等。
3）內核從它們各自的緩存種分配和釋放對象。
4）每種對象的緩存區由一連串slab構成，每個slab由一個或者多個連續的物理頁面組成。這些頁面種包含了已分配的緩存對象，也包含了空閑對象。

㈤ linux 內核物理內存管理有哪些常用演算法

/proc/meminfo 能反映每進程內存使用
些東西/proc/xxxx/statm maps memmap 體現
需要查看些虛擬文件linux內核實現即

例cat /proc/1/statm ,7組數據第二組進程1物理內存使用量單位前內核PAGE_SIZE
具體說明詳見 Documentation/filesystems/proc.txt

具體實現fs/proc/array.c

C/C++ code?123456789101112131415int proc_pid_statm(struct seq_file *m, struct pid_namespace *ns, struct pid *pid, struct task_struct *task){ unsigned long size = 0, resident = 0, shared = 0, text = 0, data = 0; struct mm_struct *mm = get_task_mm(task); if (mm) { size = task_statm(mm, &shared, &text, &data, &resident); mmput(mm); } seq_printf(m, "%lu %lu %lu %lu 0 %lu 0\n", size, resident, shared, text, data); return 0;}
函數改需要結難點根據pid應 task_struct
知道沒現api遍歷查找全局 task_struct鏈表應該難解決

㈥ 幾種提高內存的使用效率和優化內存管理方法

方法一：調整高速緩存區域的大小
可以在計算機的主要用途選項卡中設置系統利用高速緩存的比例(針對Windows 98)。如果系統的內存較多，可選擇網路伺服器，這樣系統將用較多的內存作為高速緩存。在CD-ROM標簽中，可以直接調節系統用多少內存作為CD-ROM光碟讀寫的高速緩存。
方法二：監視內存
系統的內存不管有多大，總是會用完的。雖然有虛擬內存
，但由於硬碟的讀寫速度無法與內存的速度相比，所以在使用內存時，就要時刻監視內存的使用情況。Windows操作系統中提供了一個系統監視器，可以監視內存的使用情況。一般如果只有60%的內存資源可用，這時你就要注意調整內存了，不然就會嚴重影響電腦的運行速度和系統性能。
方法三：及時釋放內存空間
如果你發現系統的內存不多了，就要注意釋放內存。所謂釋放內存，就是將駐留在內存中的數據從內存中釋放出來。釋放內存最簡單有效的方法，就是重新啟動計算機。另外，就是關閉暫時不用的程序。還有要注意剪貼板中如果存儲了圖像資料，是要佔用大量內存空間的。這時只要剪貼幾個字，就可以把內存中剪貼板上原有的圖片沖掉，從而將它所佔用的大量的內存釋放出來。
方法四：優化內存中的數據
在Windows中，駐留內存中的數據越多，就越要佔用內存資源。所以，桌面上和任務欄中的快捷圖標不要設置得太多。如果內存資源較為緊張，可以考慮盡量少用各種後台駐留的程序。平時在操作電腦時，不要打開太多的文件或窗口。長時間地使用計算機後，如果沒有重新啟動計算機，內存中的數據排列就有可能因為比較混亂，從而導致系統性能的下降。這時你就要考慮重新啟動計算機。
方法五：提高系統其他部件的性能
計算機其他部件的性能對內存的使用也有較大的影響，如匯流排類型、CPU、硬碟和顯存等。如果顯存太小，而顯示的數據量很大，再多的內存也是不可能提高其運行速度和系統效率的。

㈦ 如何熟悉Linux內存管理機制

Linux內存管理機制：
一 物理內存和虛擬內存
我們知道，直接從物理內存讀寫數據要比從硬碟讀寫數據要快的多，因此，我們希望所有數據的讀取和寫入都在內存完成，而內存是有限的，這樣就引出了物理內存與虛擬內存的概念。
物理內存就是系統硬體提供的內存大小，是真正的內存，相對於物理內存，在linux下還有一個虛擬內存的概念，虛擬內存就是為了滿足物理內存的不足
Linux的內存管理採取的是分頁存取機制，為了保證物理內存能得到充分的利用，內核會在適當的時候將物理內存中不經常使用的數據塊自動交換到虛擬內存中，而將經常使用的信息保留到物理內存。
要深入了解linux內存運行機制，需要知道下面提到的幾個方面：
Linux系統會不時的進行頁面交換操作，以保持盡可能多的空閑物理內存，即使並沒有什麼事情需要內存，Linux也會交換出暫時不用的內存頁面。這可以避免等待交換所需的時間。
Linux 進行頁面交換是有條件的，不是所有頁面在不用時都交換到虛擬內存，linux內核根據」最近最經常使用「演算法，僅僅將一些不經常使用的頁面文件交換到虛擬 內存，有時我們會看到這么一個現象：linux物理內存還有很多，但是交換空間也使用了很多。其實，這並不奇怪，例如，一個佔用很大內存的進程運行時，需 要耗費很多內存資源，此時就會有一些不常用頁面文件被交換到虛擬內存中，但後來這個佔用很多內存資源的進程結束並釋放了很多內存時，剛才被交換出去的頁面 文件並不會自動的交換進物理內存，除非有這個必要，那麼此刻系統物理內存就會空閑很多，同時交換空間也在被使用，就出現了剛才所說的現象了。關於這點，不 用擔心什麼，只要知道是怎麼一回事就可以了。
交換空間的頁面在使用時會首先被交換到物理內存，如果此時沒有足夠的物理內存來容納這些頁 面，它們又會被馬上交換出去，如此以來，虛擬內存中可能沒有足夠空間來存儲這些交換頁面，最終會導致linux出現假死機、服務異常等問題，linux雖 然可以在一段時間內自行恢復，但是恢復後的系統已經基本不可用了。
因此，合理規劃和設計Linux內存的使用，是非常重要的.
二 內存的監控
作為一名Linux系統管理員，監控內存的使用狀態是非常重要的，通過監控有助於了解內存的使用狀態，比如內存佔用是否正常，內存是否緊缺等等，監控內存最常使用的命令有free、top等

㈧ 內存管理的頁面置換演算法有哪些

收藏推薦在多道程序的正常運行過程中,屬於不同進程的頁面被分散存放在主存頁框中,當正在運行的進程所訪問的頁面不在內存時,系統會發生缺頁中斷,在缺頁中斷服務程序中會將所缺的頁面調入內存,如內存已無空閑頁框,缺頁中斷服務程序就會調用頁面置換演算法,頁面置換演算法的目的就是選出一個被淘汰的頁面.把內存和外存統一管理的真正目的是把那些被訪問概率非常高的頁存放在內存中.因此,置換演算法應該置換那些被訪問概率最低的頁,將它們移出內存.1最佳置換演算法基本原理:淘汰以後不再需要的或最遠的將來才會用到的頁面.這是1966年Belady提出的理想演算法,但無法實現,主要用於評價其他置換演算法.例:分配給某進程的內存頁面數是3頁,頁面地址流如下:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,其內存動態分配過程如下:先進先出置換(本文共計2頁)如何獲取本文>>

㈨ linux中使用了什麼內存管理方法,為什麼

「事實勝於雄辯」，我們用一個小例子（原形取自《User-Level Memory Management》）來展示上面所講的各種內存區的差別與位置。

進程的地址空間對應的描述結構是「內存描述符結構」,它表示進程的全部地址空間，——包含了和進程地址空間有關的全部信息，其中當然包含進程的內存區域。

進程內存的分配與回收

創建進程fork()、程序載入execve()、映射文件mmap()、動態內存分配malloc()/brk()等進程相關操作都需要分配內存給進程。不過這時進程申請和獲得的還不是實際內存，而是虛擬內存，准確的說是「內存區域」。進程對內存區域的分配最終都會歸結到do_mmap（）函數上來（brk調用被單獨以系統調用實現，不用do_mmap()），

內核使用do_mmap()函數創建一個新的線性地址區間。但是說該函數創建了一個新VMA並不非常准確，因為如果創建的地址區間和一個已經存在的地址區間相鄰，並且它們具有相同的訪問許可權的話，那麼兩個區間將合並為一個。如果不能合並，那麼就確實需要創建一個新的VMA了。但無論哪種情況，do_mmap()函數都會將一個地址區間加入到進程的地址空間中－－無論是擴展已存在的內存區域還是創建一個新的區域。

同樣，釋放一個內存區域應使用函數do_ummap()，它會銷毀對應的內存區域。

如何由虛變實！

從上面已經看到進程所能直接操作的地址都為虛擬地址。當進程需要內存時，從內核獲得的僅僅是虛擬的內存區域，而不是實際的物理地址，進程並沒有獲得物理內存（物理頁面——頁的概念請大家參考硬體基礎一章），獲得的僅僅是對一個新的線性地址區間的使用權。實際的物理內存只有當進程真的去訪問新獲取的虛擬地址時，才會由「請求頁機制」產生「缺頁」異常，從而進入分配實際頁面的常式。

該異常是虛擬內存機制賴以存在的基本保證——它會告訴內核去真正為進程分配物理頁，並建立對應的頁表，這之後虛擬地址才實實在在地映射到了系統的物理內存上。（當然，如果頁被換出到磁碟，也會產生缺頁異常，不過這時不用再建立頁表了）

這種請求頁機制把頁面的分配推遲到不能再推遲為止，並不急於把所有的事情都一次做完（這種思想有點像設計模式中的代理模式（proxy））。之所以能這么做是利用了內存訪問的「局部性原理」，請求頁帶來的好處是節約了空閑內存，提高了系統的吞吐率。要想更清楚地了解請求頁機制，可以看看《深入理解linux內核》一書。

這里我們需要說明在內存區域結構上的nopage操作。當訪問的進程虛擬內存並未真正分配頁面時，該操作便被調用來分配實際的物理頁，並為該頁建立頁表項。在最後的例子中我們會演示如何使用該方法。

系統物理內存管理

雖然應用程序操作的對象是映射到物理內存之上的虛擬內存，但是處理器直接操作的卻是物理內存。所以當應用程序訪問一個虛擬地址時，首先必須將虛擬地址轉化成物理地址，然後處理器才能解析地址訪問請求。地址的轉換工作需要通過查詢頁表才能完成，概括地講，地址轉換需要將虛擬地址分段，使每段虛地址都作為一個索引指向頁表，而頁表項則指向下一級別的頁表或者指向最終的物理頁面。

每個進程都有自己的頁表。進程描述符的pgd域指向的就是進程的頁全局目錄。下面我們借用《linux設備驅動程序》中的一幅圖大致看看進程地址空間到物理頁之間的轉換關系。

上面的過程說起來簡單，做起來難呀。因為在虛擬地址映射到頁之前必須先分配物理頁——也就是說必須先從內核中獲取空閑頁，並建立頁表。下面我們介紹一下內核管理物理內存的機制。

物理內存管理（頁管理）

Linux內核管理物理內存是通過分頁機制實現的，它將整個內存劃分成無數個4k（在i386體系結構中）大小的頁，從而分配和回收內存的基本單位便是內存頁了。利用分頁管理有助於靈活分配內存地址，因為分配時不必要求必須有大塊的連續內存[3]，系統可以東一頁、西一頁的湊出所需要的內存供進程使用。雖然如此，但是實際上系統使用內存時還是傾向於分配連續的內存塊，因為分配連續內存時，頁表不需要更改，因此能降低TLB的刷新率（頻繁刷新會在很大程度上降低訪問速度）。

鑒於上述需求，內核分配物理頁面時為了盡量減少不連續情況，採用了「夥伴」關系來管理空閑頁面。夥伴關系分配演算法大家應該不陌生——幾乎所有操作系統方面的書都會提到,我們不去詳細說它了，如果不明白可以參看有關資料。這里只需要大家明白Linux中空閑頁面的組織和管理利用了夥伴關系，因此空閑頁面分配時也需要遵循夥伴關系，最小單位只能是2的冪倍頁面大小。內核中分配空閑頁面的基本函數是get_free_page/get_free_pages，它們或是分配單頁或是分配指定的頁面（2、4、8…512頁）。

注意：get_free_page是在內核中分配內存，不同於malloc在用戶空間中分配，malloc利用堆動態分配，實際上是調用brk()系統調用，該調用的作用是擴大或縮小進程堆空間（它會修改進程的brk域）。如果現有的內存區域不夠容納堆空間，則會以頁面大小的倍數為單位，擴張或收縮對應的內存區域，但brk值並非以頁面大小為倍數修改，而是按實際請求修改。因此Malloc在用戶空間分配內存可以以位元組為單位分配,但內核在內部仍然會是以頁為單位分配的。

另外,需要提及的是，物理頁在系統中由頁結構structpage描述，系統中所有的頁面都存儲在數組mem_map[]中，可以通過該數組找到系統中的每一頁（空閑或非空閑）。而其中的空閑頁面則可由上述提到的以夥伴關系組織的空閑頁鏈表（free_area[MAX_ORDER]）來索引。

內核內存使用

Slab

所謂尺有所長，寸有所短。以頁為最小單位分配內存對於內核管理系統中的物理內存來說的確比較方便，但內核自身最常使用的內存卻往往是很小（遠遠小於一頁）的內存塊——比如存放文件描述符、進程描述符、虛擬內存區域描述符等行為所需的內存都不足一頁。這些用來存放描述符的內存相比頁面而言，就好比是麵包屑與麵包。一個整頁中可以聚集多個這些小塊內存；而且這些小塊內存塊也和麵包屑一樣頻繁地生成/銷毀。

為了滿足內核對這種小內存塊的需要，Linux系統採用了一種被稱為slab分配器的技術。Slab分配器的實現相當復雜，但原理不難，其核心思想就是「存儲池[4]」的運用。內存片段（小塊內存）被看作對象，當被使用完後，並不直接釋放而是被緩存到「存儲池」里，留做下次使用，這無疑避免了頻繁創建與銷毀對象所帶來的額外負載。

Slab技術不但避免了內存內部分片（下文將解釋）帶來的不便（引入Slab分配器的主要目的是為了減少對夥伴系統分配演算法的調用次數——頻繁分配和回收必然會導致內存碎片——難以找到大塊連續的可用內存），而且可以很好地利用硬體緩存提高訪問速度。

Slab並非是脫離夥伴關系而獨立存在的一種內存分配方式，slab仍然是建立在頁面基礎之上，換句話說，Slab將頁面（來自於夥伴關系管理的空閑頁面鏈表）撕碎成眾多小內存塊以供分配，slab中的對象分配和銷毀使用kmem_cache_alloc與kmem_cache_free。

Kmalloc

Slab分配器不僅僅只用來存放內核專用的結構體，它還被用來處理內核對小塊內存的請求。當然鑒於Slab分配器的特點，一般來說內核程序中對小於一頁的小塊內存的請求才通過Slab分配器提供的介面Kmalloc來完成（雖然它可分配32到131072位元組的內存）。從內核內存分配的角度來講，kmalloc可被看成是get_free_page（s）的一個有效補充，內存分配粒度更靈活了。

有興趣的話，可以到/proc/slabinfo中找到內核執行現場使用的各種slab信息統計，其中你會看到系統中所有slab的使用信息。從信息中可以看到系統中除了專用結構體使用的slab外，還存在大量為Kmalloc而准備的Slab（其中有些為dma准備的）。

內核非連續內存分配（Vmalloc）

夥伴關系也好、slab技術也好，從內存管理理論角度而言目的基本是一致的，它們都是為了防止「分片」，不過分片又分為外部分片和內部分片之說，所謂內部分片是說系統為了滿足一小段內存區（連續）的需要，不得不分配了一大區域連續內存給它，從而造成了空間浪費；外部分片是指系統雖有足夠的內存，但卻是分散的碎片，無法滿足對大塊「連續內存」的需求。無論何種分片都是系統有效利用內存的障礙。slab分配器使得一個頁面內包含的眾多小塊內存可獨立被分配使用，避免了內部分片，節約了空閑內存。夥伴關系把內存塊按大小分組管理，一定程度上減輕了外部分片的危害，因為頁框分配不在盲目，而是按照大小依次有序進行，不過夥伴關系只是減輕了外部分片，但並未徹底消除。你自己比劃一下多次分配頁面後，空閑內存的剩餘情況吧。

所以避免外部分片的最終思路還是落到了如何利用不連續的內存塊組合成「看起來很大的內存塊」——這里的情況很類似於用戶空間分配虛擬內存，內存邏輯上連續，其實映射到並不一定連續的物理內存上。Linux內核借用了這個技術，允許內核程序在內核地址空間中分配虛擬地址，同樣也利用頁表（內核頁表）將虛擬地址映射到分散的內存頁上。以此完美地解決了內核內存使用中的外部分片問題。內核提供vmalloc函數分配內核虛擬內存，該函數不同於kmalloc，它可以分配較Kmalloc大得多的內存空間（可遠大於128K，但必須是頁大小的倍數），但相比Kmalloc來說,Vmalloc需要對內核虛擬地址進行重映射，必須更新內核頁表，因此分配效率上要低一些（用空間換時間）

與用戶進程相似,內核也有一個名為init_mm的mm_strcut結構來描述內核地址空間，其中頁表項pdg=swapper_pg_dir包含了系統內核空間（3G-4G）的映射關系。因此vmalloc分配內核虛擬地址必須更新內核頁表，而kmalloc或get_free_page由於分配的連續內存，所以不需要更新內核頁表。

vmalloc分配的內核虛擬內存與kmalloc/get_free_page分配的內核虛擬內存位於不同的區間，不會重疊。因為內核虛擬空間被分區管理，各司其職。進程空間地址分布從0到3G(其實是到PAGE_OFFSET,在0x86中它等於0xC0000000)，從3G到vmalloc_start這段地址是物理內存映射區域（該區域中包含了內核鏡像、物理頁面表mem_map等等）比如我使用的系統內存是64M(可以用free看到)，那麼(3G——3G+64M)這片內存就應該映射到物理內存，而vmalloc_start位置應在3G+64M附近（說"附近"因為是在物理內存映射區與vmalloc_start期間還會存在一個8M大小的gap來防止躍界）,vmalloc_end的位置接近4G(說"接近"是因為最後位置系統會保留一片128k大小的區域用於專用頁面映射，還有可能會有高端內存映射區，這些都是細節，這里我們不做糾纏)。

上圖是內存分布的模糊輪廓

由get_free_page或Kmalloc函數所分配的連續內存都陷於物理映射區域，所以它們返回的內核虛擬地址和實際物理地址僅僅是相差一個偏移量（PAGE_OFFSET），你可以很方便的將其轉化為物理內存地址，同時內核也提供了virt_to_phys（）函數將內核虛擬空間中的物理映射區地址轉化為物理地址。要知道，物理內存映射區中的地址與內核頁表是有序對應的，系統中的每個物理頁面都可以找到它對應的內核虛擬地址（在物理內存映射區中的）。

而vmalloc分配的地址則限於vmalloc_start與vmalloc_end之間。每一塊vmalloc分配的內核虛擬內存都對應一個vm_struct結構體（可別和vm_area_struct搞混，那可是進程虛擬內存區域的結構），不同的內核虛擬地址被4k大小的空閑區間隔，以防止越界——見下圖）。與進程虛擬地址的特性一樣，這些虛擬地址與物理內存沒有簡單的位移關系，必須通過內核頁表才可轉換為物理地址或物理頁。它們有可能尚未被映射，在發生缺頁時才真正分配物理頁面。

這里給出一個小程序幫助大家認清上面幾種分配函數所對應的區域。

#include<linux/mole.h>

#include<linux/slab.h>

#include<linux/vmalloc.h>

unsignedchar*pagemem;

unsignedchar*kmallocmem;

unsignedchar*vmallocmem;

intinit_mole(void)

{

pagemem = get_free_page(0);

printk("<1>pagemem=%s",pagemem);

kmallocmem = kmalloc(100,0);

printk("<1>kmallocmem=%s",kmallocmem);

vmallocmem = vmalloc(1000000);

printk("<1>vmallocmem=%s",vmallocmem);

}

voidcleanup_mole(void)

{

free_page(pagemem);

kfree(kmallocmem);

vfree(vmallocmem);

}

實例

內存映射(mmap)是Linux操作系統的一個很大特色，它可以將系統內存映射到一個文件（設備）上，以便可以通過訪問文件內容來達到訪問內存的目的。這樣做的最大好處是提高了內存訪問速度，並且可以利用文件系統的介面編程（設備在Linux中作為特殊文件處理）訪問內存，降低了開發難度。許多設備驅動程序便是利用內存映射功能將用戶空間的一段地址關聯到設備內存上，無論何時，只要內存在分配的地址范圍內進行讀寫，實際上就是對設備內存的訪問。同時對設備文件的訪問也等同於對內存區域的訪問，也就是說，通過文件操作介面可以訪問內存。Linux中的X伺服器就是一個利用內存映射達到直接高速訪問視頻卡內存的例子。

熟悉文件操作的朋友一定會知道file_operations結構中有mmap方法，在用戶執行mmap系統調用時，便會調用該方法來通過文件訪問內存——不過在調用文件系統mmap方法前，內核還需要處理分配內存區域（vma_struct）、建立頁表等工作。對於具體映射細節不作介紹了，需要強調的是,建立頁表可以採用remap_page_range方法一次建立起所有映射區的頁表，或利用vma_struct的nopage方法在缺頁時現場一頁一頁的建立頁表。第一種方法相比第二種方法簡單方便、速度快，但是靈活性不高。一次調用所有頁表便定型了，不適用於那些需要現場建立頁表的場合——比如映射區需要擴展或下面我們例子中的情況。

我們這里的實例希望利用內存映射，將系統內核中的一部分虛擬內存映射到用戶空間，以供應用程序讀取——你可利用它進行內核空間到用戶空間的大規模信息傳輸。因此我們將試圖寫一個虛擬字元設備驅動程序，通過它將系統內核空間映射到用戶空間——將內核虛擬內存映射到用戶虛擬地址。從上一節已經看到Linux內核空間中包含兩種虛擬地址：一種是物理和邏輯都連續的物理內存映射虛擬地址；另一種是邏輯連續但非物理連續的vmalloc分配的內存虛擬地址。我們的例子程序將演示把vmalloc分配的內核虛擬地址映射到用戶地址空間的全過程。

程序里主要應解決兩個問題：

第一是如何將vmalloc分配的內核虛擬內存正確地轉化成物理地址？

因為內存映射先要獲得被映射的物理地址，然後才能將其映射到要求的用戶虛擬地址上。我們已經看到內核物理內存映射區域中的地址可以被內核函數virt_to_phys轉換成實際的物理內存地址，但對於vmalloc分配的內核虛擬地址無法直接轉化成物理地址，所以我們必須對這部分虛擬內存格外「照顧」——先將其轉化成內核物理內存映射區域中的地址，然後在用virt_to_phys變為物理地址。

轉化工作需要進行如下步驟：

如下圖所示：

第二是當訪問vmalloc分配區時，如果發現虛擬內存尚未被映射到物理頁，則需要處理「缺頁異常」。因此需要我們實現內存區域中的nopaga操作，以能返回被映射的物理頁面指針，在我們的實例中就是返回上面過程中的內核物理內存映射區域中的地址。由於vmalloc分配的虛擬地址與物理地址的對應關系並非分配時就可確定，必須在缺頁現場建立頁表，因此這里不能使用remap_page_range方法，只能用vma的nopage方法一頁一頁的建立。

程序組成

map_driver.c，它是以模塊形式載入的虛擬字元驅動程序。該驅動負責將一定長的內核虛擬地址(vmalloc分配的)映射到設備文件上。其中主要的函數有——vaddress_to_kaddress（）負責對vmalloc分配的地址進行頁表解析,以找到對應的內核物理映射地址（kmalloc分配的地址）；map_nopage()負責在進程訪問一個當前並不存在的VMA頁時，尋找該地址對應的物理頁，並返回該頁的指針。

test.c它利用上述驅動模塊對應的設備文件在用戶空間讀取讀取內核內存。結果可以看到內核虛擬地址的內容（ok!），被顯示在了屏幕上。

執行步驟

編譯map_driver.c為map_driver.o模塊,具體參數見Makefile

載入模塊：insmodmap_driver.o

生成對應的設備文件

1在/proc/devices下找到map_driver對應的設備命和設備號：grepmapdrv/proc/devices

2建立設備文件mknodmapfilec 254 0（在我的系統里設備號為254）

利用maptest讀取mapfile文件，將取自內核的信息列印到屏幕上。

㈩ linux內核物理內存管理有哪些常用演算法 lru slab

採用夥伴演算法分配內存時，每次至少分配一個頁面。但當請求分配的內存大小為幾十個位元組或幾百個位元組時應該如何處理？如何在一個頁面中分配小的內存區，小內存區的分配所產生的內碎片又如何解決？
Linux2.0採用的解決辦法是建立了13個空閑區鏈表，它們的大小從32位元組到132056位元組。從Linux2.2開始，MM的開發者採用了一種叫做slab的分配模式，該模式早在1994年就被開發出來，用於Sun Microsystem Solaris 2.4操作系統中。Slab的提出主要是基於以下考慮：
· 內核對內存區的分配取決於所存放數據的類型。例如，當給用戶態進程分配頁面時，內核調用get_free_page()函數，並用0填充這個頁面。 而給內核的數據結構分配頁面時，事情沒有這么簡單，例如，要對數據結構所在的內存進行初始化、在不用時要收回它們所佔用的內存。因此，Slab中引入了對象這個概念，所謂對象就是存放一組數據結構的內存區，其方法就是構造或析構函數，構造函數用於初始化數據結構所在的內存區，而析構函數收回相應的內存區。但為了便於理解，你也可以把對象直接看作內核的數據結構。為了避免重復初始化對象，Slab分配模式並不丟棄已分配的對象，而是釋放但把它們依然保留在內存中。當以後又要請求分配同一對象時，就可以從內存獲取而不用進行初始化，這是在Solaris 中引入Slab的基本思想。
實際上，Linux中對Slab分配模式有所改進，它對內存區的處理並不需要進行初始化或回收。出於效率的考慮，Linux並不調用對象的構造或析構函數，而是把指向這兩個函數的指針都置為空。Linux中引入Slab的主要目的是為了減少對夥伴演算法的調用次數。
· 實際上，內核經常反復使用某一內存區。例如，只要內核創建一個新的進程，就要為該進程相關的數據結構（task_struct、打開文件對象等）分配內存區。當進程結束時，收回這些內存區。因為進程的創建和撤銷非常頻繁，因此，Linux的早期版本把大量的時間花費在反復分配或回收這些內存區上。從Linux2.2開始，把那些頻繁使用的頁面保存在高速緩存中並重新使用。
· 可以根據對內存區的使用頻率來對它分類。對於預期頻繁使用的內存區，可以創建一組特定大小的專用緩沖區進行處理，以避免內碎片的產生。對於較少使用的內存區，可以創建一組通用緩沖區（如Linux2.0中所使用的2的冪次方）來處理，即使這種處理模式產生碎片，也對整個系統的性能影響不大。
· 硬體高速緩存的使用，又為盡量減少對夥伴演算法的調用提供了另一個理由，因為對夥伴演算法的每次調用都會「弄臟」硬體高速緩存，因此，這就增加了對內存的平均訪問次數。
Slab分配模式把對象分組放進緩沖區（盡管英文中使用了Cache這個詞，但實際上指的是內存中的區域，而不是指硬體高速緩存）。因為緩沖區的組織和管理與硬體高速緩存的命中率密切相關，因此，Slab緩沖區並非由各個對象直接構成，而是由一連串的「大塊（Slab）」構成，而每個大塊中則包含了若干個同種類型的對象，這些對象或已被分配，或空閑，如圖6.12所示。一般而言，對象分兩種，一種是大對象，一種是小對象。所謂小對象，是指在一個頁面中可以容納下好幾個對象的那種。例如，一個inode結構大約佔300多個位元組，因此，一個頁面中可以容納8個以上的inode結構，因此，inode結構就為小對象。Linux內核中把小於512位元組的對象叫做小對象。