夥伴演算法思想

❶ 求編程領域上一些經典演算法同時也是程序員必須掌握的演算法

這是我在一個論壇里看到的，你也參考參考吧。C++的虛函數
======================
C++使用虛函數實現了其對象的多態，C++對象的開始四個位元組是指向虛函數表的指針，其初始化順序是先基類後派生類，所以該虛函數表永遠指向最後一個派生類，從而實現了相同函數在不同對象中的不同行為，使得對象既有共性，又有其個性。

內存池分配、回收之夥伴演算法
=======================
夥伴演算法是空閑鏈表法的一個增強演算法，依次建立2^0\2^1\2^2\2^3...2^n大小的 內存塊空閑鏈表，利用相鄰內存塊的夥伴性質，很容易將互為夥伴的內存塊進行合並移到相應的空閑鏈表或將一塊內存拆分成兩塊夥伴內存，一塊分配出去，另一塊掛入相應空閑鏈表，使得內存的分配和回收變得高效。

AVL樹
=======================
AVL樹是一個平衡二叉樹，其中序遍歷是從小到大排序的，該結構插入節點和檢索非常高效，被廣泛應用

快速排序
=======================
通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。效率非常高

密碼學之非對稱加密協議（公鑰、私鑰加密協議）
======================
非對稱加密演算法需要兩個密鑰，用其中一個加密產生的密文，只能通過另外一個密鑰解密，密鑰持有者A可以將其中一個公開，稱為公用密鑰，另外一個秘密保存稱為私鑰，這樣當某人B想給A傳一封秘信時，只要將密信使用A的公鑰加密後，就可以放心使用各種信道將迷信傳給A了，因為該密信只有A可以解密，第三者截取因為無法解密而毫無意義。
該演算法很好地解決了密鑰的安全傳遞的問題，因為公鑰和加密演算法都是公開的，私鑰不需要傳輸。

密碼學之數字簽名協議（身份鑒別、防抵賴）
======================
數字簽名也是建立在非對稱加密基礎之上的，如果A君用它的私鑰將文件加密後在發布，A君就無法抵賴該文件是其發布的，因為其他人能通過A君的公鑰將文件解密就說明，如果演算法可靠，該文件一定是A君用其私鑰加密的。
由於非對稱加密演算法的加密和解密很慢，現在的數字簽名並非是將其要發布的信息用其私鑰加密，而是先用一個單項散列演算法如（MD5）產生一個該信息的比較短的指紋（hash值），對其指紋用其私鑰加密後和信息一並發布，同樣達到了防抵賴的作用。

無回溯字元串模式匹配-kmp演算法
======================
他是根據子串的特徵，當匹配失敗時，不需要回溯，而是直接將字串向後滑動若干個位元組，繼續匹配，極大提高了匹配速度。該演算法被廣泛使用。詳細請參考數據結構教程。

最小路徑選路-迪傑斯特拉演算法、弗洛伊德演算法
======================
學習數據結構的時候，印象最深的就要算kmp演算法和最小路徑演算法了，因為理解他們比較費腦子，我是不可能發明這些演算法了，發明他們的都是天才，呵呵。
使用最短路徑的演算法曾經幫人寫過一個小東西，還是很有效的，記得是使用的弗洛伊德演算法的一個變種，要詳細了解的朋友可以查找相關資料，想將他們使用在你的項目中，代碼直接從教科書上抄就可以了，不需要理解。

tcp協議之-nagle演算法
======================
tcp、ip中令人叫絕的想法很多，印象最深的要算nagle演算法了。
tcp出於效率和流量控制的考慮，發送端的數據不是產生多少就馬上發送多少，一般是等到數據集聚到發送緩沖區長度的一半或者數據達到最大tcp數據包數據部分長度（好像是65515）才啟動發送，而且還要看接受端可用緩沖區的大小，如果接受端產生一個回應報文通知發送端沒有接受空間了，發送端哪怕緩沖區已經滿了，也不會啟動發送，直到接受端通告發送端其已經有了接受數據的空間了。
這樣就有一個問題，假如發送端就是要發送一個小報文（比如10個位元組），然後等待對方的回應。按照上面的方案，tcp會一直等數據收集到一定量才發送，於是矛盾就產生了。應用層不再發數據，tcp等不到足夠的數據不會將10個字的數據發送到網卡，接收端應用層收不到數據就不會回應發送端。
你也可能說，可以讓修改發送端發送條件，不一定要等到足夠的數據再發送，為了效率考慮，可以考慮延時一定的時間，比如說1秒，如果上層還沒有數據到來，就將發送緩沖中的數據發出去。當然這樣也是可行的，盡管應用端白白等了1秒鍾啥也沒干，呵呵。
其實nagle演算法很好解決了該問題，它的做發是鏈接建立後的第一次發送不用等待，直接將數據組裝成tcp報文發送出去，以後要麼等到數據量足夠多、要麼是等到接受方的確認報文，演算法及其簡單，而且很好解決了上面的矛盾。

socket之io模型設計
======================
windows下socket有兩種工作方式：
1）同步方式
2）非同步方式

同步socket又有兩種工作模式：
1）阻塞模式
2）非阻塞模式

阻塞模式是最簡單的工作模式，以tcp的發送數據為例，如果發送緩沖區沒有空間，send調用就不會返回，一直要等到能夠發出一點數據為止，哪怕是一個位元組，但是send返回並不表示我要發送的數據已經全部提交給了tcp，所以send返回時要檢查這次發送的數量，調整發送緩沖指針，繼續發送，直到所有數據都提交給了系統。
由於其阻塞的特性，會阻塞發送線程，所以單線程的程序是不適合使用阻塞模式通信的，一般使用一個連接一個線程的方法，但是這種方式對於要維護多個連接的程序，是個不好的選擇，線程越多，開銷越大。

同步非阻塞模式的socket不會阻塞通信線程，如果發送緩沖區滿，send調用也是立刻返回，接受緩沖區空，recv也不會阻塞，所以通信線程要反復調用send或recv嘗試發送或接收數據，對cpu是很大的浪費。
針對非阻塞的尷尬，介面開發人員發明了三種io模型來解決該問題：
1）選擇模型（select）
2）非同步選擇模型（AsyncSelect）
3）事件選擇模型（EventSeselect）
其思想是根據io類型，預先查看1個或n個socket是否能讀、寫等。
其select本身來說，select是阻塞的，可以同時監視多個socket，只要所監視的其中一個socket可以讀、寫，secect調用才返回
非同步選擇模型其select是非同步的（非同步是不會阻塞的），是將監視任務委託給系統，系統在socket可讀、寫時通過消息通知應用程序。有一點需要說明，假如應用程序已經有很多數據需要發送，當收到可寫通知時，一定要盡量多地發送數據，直到發送失敗，lasterror提示「將要阻塞」，將來才可能有新的可寫通知到來，否則永遠也不會有。
事件選擇模型也是將監視socket狀態的工作委託給系統，系統在適當的時候通過事件通知應用程序socket可以的操作。

除了同步工作方式外，還有一種叫非同步工作方式
非同步工作方式是不會阻塞的，因為是將io操作本身委託給系統，系統在io操作完成後通過回調常式或事件或完成包通知應用程序
非同步工作方式有兩種io模型和其對應，其實這兩種模型是window是非同步io的實現：
1）重疊模型
2）完成埠

重疊模型通過事件或回調常式通知應用程序io已經完成
完成埠模型比較復雜，完成埠本身其實是一個io完成包隊列。
應用程序一般創建若干個線程用來監視完成埠，這些線程試圖從完成埠移除一個完成包，如果有，移除成功，應用程序處理該完成包，否則應用程序監視完成埠的線程被阻塞。

select模型是從UNIX上的Berkeley Software Distribution(BSD)版本的套接字就實現了的，其它四種io模型windows發明的，在windows中完成埠和非同步選擇模型是使用比較廣泛的，一般分別用於服務端和客戶端開發。
這五種io模型設計還是比較巧妙的：三種選擇模型很好解決了「同步非阻塞」模式編程的不足；重疊模型和完成埠是windows非同步io的經典實現，不局限於網路io，對文件io同樣適用。

說點題外話，socket的send完成僅僅是將數據（可能是部分）提交給系統，而不是已經發送到了網卡上，更不是已經發送到了接收端。所以要知道你的數據已經發送到了對方的應用層的唯一方法是，讓對方給你發送一個應對包。
發送數據要注意，對應tcp，要防止發送和接收的亂序，對於發送，一般應該為每一個鏈接建立一個發送隊列，採用類似nagle的演算法啟動數據發送。
一次發送可能是你提交數據的一部分，一定要當心，否則出問題沒處找去。

❷ Netty內存管理

ByteBuf底層是一個位元組數組，內部維護了兩個索引：readerIndex與writerIndex。其中0 --> readerIndex部分為可丟棄位元組，表示已被讀取過，readerIndex --> writerIndex部分為可讀位元組，writerIndex --> capacity部分為可寫位元組。ByteBuf支持動態擴容，在實例化時會傳入maxCapacity，當writerIndex達到capacity且capacity小於maxCapacity時會進行自動擴容。

ByteBuf子類可以按照以下三個緯度進行分類：

在進入內存分配核心邏輯前，我們先對Netty內存分配相關概念做下了解。Netty內存管理借鑒jemalloc思想，為了提高內存利用率，根據不同內存規格使用不同的分配策略，並且使用緩存提高內存分配效率。

Netty有四種內存規格，tiny表示16B ~ 512B之間的內存塊，samll表示512B ~ 8K之間的內存塊，normal表示8K ~ 16M的內存塊，Huge表示大於16M的內存塊。

Chunk是Netty向操作系統申請內存的單位，默認一次向操作系統申請16M內存，Netty內部將Chunk按照Page大小劃分為2048塊。我們申請內存時如果大於16M，則Netty會直接向操作系統申請對應大小內存，如果申請內存在8k到16M之間則會分配對應個數Page進行使用。如果申請內存遠小於8K，那麼直接使用一個Page會造成內存浪費，SubPage就是對Page進行再次分配，減少內存浪費。

如果申請內存小於8K，會對Page進行再次劃分為SubPage，SubPage大小為Page大小/申請內存大小。SubPage又劃分為tiny與small兩種。

負責管理從操作系統中申請到的內存塊，Netty為了減少多線程競爭arena，採用多arena設計，arena數量默認為2倍CPU核心數。線程與arena關系如下：

線程本地緩存，負責創建線程緩存PoolThreadCache。PoolThreadCache中會初始化三種類型MemoryRegionCache數組，用以緩存線程中不同規格的內存塊，分別為：tiny、small、normal。tiny類型數組緩存的內存塊大小為16B ~ 512B之間，samll類型數組緩存的內存塊大小為512B ~ 8K之間的內存塊，normal類型數組緩存的內存塊大小受DEFAULT_MAX_CACHED_BUFFER_CAPACITY配置影響，默認只緩存8K、16K、32K三種類型內存塊。

內存塊緩存容器，負責緩存tiny、small、normal三種內存塊。其內部維護一個隊列，用於緩存同種內存大小的內存塊。

負責管理從操作系統申請的內存，內部採用夥伴演算法以Page為單位進行內存的分配與管理。

負責管理Chunk列表，根據內存使用率，分為：qInit、q000、q025、q050、q075、q100六種。每個PoolChunkList中存儲內存使用率相同的Chunk，Chunk以雙向鏈表進行關聯，同時不同使用率的PoolChunkList也以雙向列表進行關聯。這樣做的目的是因為隨著內存的分配，Chunk使用率會發生變化，以鏈表形式方便Chunk在不同使用率列表進行移動。

PoolSubpage負責tiny、small類型內存的管理與分配，實現基於SLAB內存分配演算法。PoolArena中有兩種PoolSubpage類型數組，分別為：tinySubpagePools、smallSubpagePools。tinySubpagePools負責管理tiny類型內存，數組大小為512/16=32種。smallSubpagePools負責管理small類型內存，數組大小為4。

PoolSubpage數組中存儲不同內存大小的PoolSubpage節點，相同大小節點以鏈表進行關聯。PoolSubpage內部使用點陣圖數組記錄內存分配情況。

Netty通過ByteBufAllocator進行內存分配，ByteBufAllocator有兩個實現類：PooledByteBufAllocator與UnpooledByteBufAllocator，其中，是否在堆內存或者直接內存分配與是否使用unsafe進行讀寫操作都封裝在其實現類中。

我們先看下ByteBufAllocator類圖：

PooledByteBufAllocator與UnpooledByteBufAllocator內存分配類似，可以通過newHeapBuffer與newDirectBuffer進行分配內存，我們以PooledByteBufAllocator為例分析下內存分配流程：

以PooledByteBufAllocator為例來分析下內存分配器實例化過程。首先調用PooledByteBufAllocator#DEFAULT方法實例化PooledByteBufAllocator

PooledByteBufAllocator實例化時會初始化幾個比較重要的屬性：

最終會調用PooledByteBufAllocator如下構造方法：

PooledByteBufAllocator構造方法主要做了兩件事情，一是：初始化PoolThreadLocalCache屬性，二是：初始化堆內存與直接內存類型PoolArena數組，我們進入PoolArena.DirectArena構造方法，來分析下PoolArena初始化時主要做了哪些事情：

DirectArena構造方法會調用其父類PoolArena構造方法，在PoolArena構造方法中會初始化tiny類型與small類型PoolSubpage數組，並初始化六種不同內存使用率的PoolChunkList，每個PoolChunkList以雙向鏈表進行關聯。

以分配直接內存為例，分析內存分配的主要流程：

PooledByteBufAllocator#directBuffer方法最終會調用如下構造方法，其中maxCapacity為Integer.MAX_VALUE：

該方法主要分三步，第一步：獲取線程緩存，第二步：分配內存，第三步：將ByteBuf轉為具有內存泄漏檢測功能的ByteBuf，我們來分析下每一步具體做了哪些事情：

1.獲取線程緩存，從PoolThreadLocalCache中獲取PoolThreadCache，首次調用會先進行進行初始化，並將結果緩存下來：

初始化方法在PoolThreadLocalCache中，首先會循環找到使用最少的PoolArena，然後調用PoolThreadCache構造方法創建PoolThreadCache：

PoolThreadCache構造方法中會初始化tinySubPageDirectCaches、smallSubPageDirectCaches、normalDirectCaches這三種MemoryRegionCache數組：

createSubPageCaches方法中會創建並初始化MemoryRegionCache數組，其中tiny類型數組大小為32，small類型數組大小為4，normal類型數組大小為3：

最終會調用MemoryRegionCache構造方法進行創建，我們看下MemoryRegionCache結構：

2.分配內存，首先會獲取PooledByteBuf，然後進行內存分配：

newByteBuf方法會嘗試從對象池裡面獲取pooledByteBuf，如果沒有則進行創建。allocate方法為內存分配核心邏輯，主要分為兩種分配方式：page級別內存分配（8k _{16M）、subPage級別內存分配（0} 8K）、huge級別內存分配（>16M）。page與subPage級別內存分配首先會嘗試從緩存上進行內存分配，如果分配失敗則重新申請內存。huge級別內存分配不會通過緩存進行分配。我們看下allocate方法主要流程：

首先嘗試從緩存中進行分配：

cacheForTiney方法先根據分配內存大小定位到對應的tinySubPageDirectCaches數組中MemoryRegionCache，如果沒有定位到則不能在緩存中進行分配。如果有則從MemoryRegionCache對應的隊列中彈出一個PooledByteBuf對象進行初始化，同時為了復用PooledByteBuf對象，會將其緩存下來。

如果從緩存中分配不成功，則會從對應的PoolSubpage數組上進行分配，如果PoolSubpage數組對應的內存大小下標中有可分配空間則進行分配，並對PooledByteBuf進行初始化。

如果在PoolSubpage數組上分配不成功，則表示沒有可以用來分配的SubPage，則會嘗試從Page上進行分配。先嘗試從不同內存使用率的ChunkList進行分配，如果仍分配不成功，則表示沒有可以用來分配的Chunk，此時會創建新的Chunk進行內存分配。

進入PoolChunk#allocate方法看下分配流程：

allocateRun方法用來分配大於等於8K的內存，allocateSubpage用來分配小於8K的內存，進入allocateSubpage方法：

內存分配成功後會調用initBuf方法初始化PoolByteBuf：

Page級別內存分配和SubPage級別類似，同樣是先從緩存中進行分配，分配不成功則嘗試從不同內存使用率的ChunkList進行分配，如果仍分配不成功，則表示沒有可以用來分配的Chunk，此時會創建新的Chunk進行內存分配，不同點在allocate方法中：

因為大於16M的內存分配Netty不會進行緩存，所以Huge級別內存分配會直接申請內存並進行初始化：

調用ByteBuf#release方法會進行內存釋放，方法中會判斷當前byteBuf 是否被引用，如果沒有被引用, 則調用deallocate方法進行釋放：

進入deallocate方法看下內存釋放流程：

free方法會把釋放的內存加入到緩存，如果加入緩存不成功則會標記這段內存為未使用：

recycle方法會將PoolByteBuf對象放入到對象池中：

❸ 使用malloc和free有哪些注意事項

free 不管指針指向多大的空間,均可以正確地進行釋放，這一點釋放比 delete/delete [] 要方便。不過，必須注意，如果在分配指針時，用的是new或new[]。當在釋放內存時，並不能圖方便而使用free來釋放。反過來，用malloc 分配的內存，也不能用delete/delete[] 來釋放。一句話，new/delete、new[]/delete[]、malloc/free 三對均需配套使用，不可混用.
1 分配內存 malloc 函數
需要包含頭文件：
and
函數聲明(函數原型)
void *malloc(int size);
說明：malloc 向系統申請分配指定size個位元組的內存空間。返回類型是 void* 類型。void* 表示未確定類型的指針。C,C++規定，void* 類型可以強制轉換為任何其它類型的指針。
從函數聲明上可以看出。malloc 和 new 至少有兩個不同: new 返回指定類型的指針，並且可以自動計算所需要大小。比如：
int *p;
p = new int; //返回類型為int* 類型(整數型指針)，分配大小為 sizeof(int);
或：
int* parr;
parr = new int [100]; //返回類型為 int* 類型(整數型指針)，分配大小為 sizeof(int) * 100;
而 malloc 則必須由我們計算要位元組數，並且在返回後強行轉換為實際類型的指針。
int* p;
p = (int *) malloc (sizeof(int));
第一、malloc 函數返回的是 void * 類型，如果你寫成：p = malloc (sizeof(int)); 則程序無法通過編譯，報錯：「不能將 void* 賦值給 int * 類型變數」。所以必須通過 (int *) 來將強制轉換。
第二、函數的實參為 sizeof(int) ，用於指明一個整型數據需要的大小。如果你寫成：
int* p = (int *) malloc (1);
代碼也能通過編譯，但事實上只分配了1個位元組大小的內存空間，當你往裡頭存入一個整數，就會有3個位元組無家可歸，而直接「住進鄰居家」！造成的結果是後面的內存中原有數據內容全部被清空。
malloc 也可以達到 new [] 的效果，申請出一段連續的內存，方法無非是指定你所需要內存大小。
比如想分配100個int類型的空間：
int* p = (int *) malloc ( sizeof(int) * 100 ); //分配可以放得下100個整數的內存空間。
另外有一點不能直接看出的區別是，malloc 只管分配內存，並不能對所得的內存進行初始化，所以得到的一片新內存中，其值將是隨機的。
除了分配及最後釋放的方法不一樣以外，通過malloc或new得到指針，在其它操作上保持一致。

2 釋放內存 free 函數
需要包含頭文件(和 malloc 一樣)：
函數聲明：
void free(void *block);
即： void free(指針變數)；
之所以把形參中的指針聲明為 void* ，是因為free必須可以釋放任意類型的指針，而任意類型的指針都可以轉換為void *。
舉例：
int* p = (int *) malloc(4);
*p = 100;
free(p); //釋放 p 所指的內存空間
或者：
int* p = (int *) malloc ( sizeof(int) * 100 ); //分配可以放得下100個整數的內存空間。
……
free(p);

❹ C語言編寫程序，將一個字元串中的大寫字母轉換為對應的小寫字母，小寫字母轉換為對應的大寫字母，並統計數

在 C 語言中區分字母的大小寫，利用 ASCII 碼中大寫字母和小寫字母之間的轉換關系（差值為 32），可以將小寫字母轉換為大寫字母。編寫程序實現，從鍵盤上輸入一個小寫字母，按回車鍵，程序將該小寫字母轉換為大寫字母，並輸出其 ASCII 值。
演算法思想

由於大寫字母與小寫字母之間的差值為 32，因此小寫字母轉換為大寫字母的方法就是將小寫字母的 ASCII 碼值減去 32，便可得到與之對應的大寫字母。

利用 getchar 函數從鍵盤上輸入一個小寫字母，並將其賦給一個字元變數 a；然後將 a—32 的值賦給字元變數 b；最後進行輸出，輸出時先輸出字母，再將字母以整數形式輸出。其具體步驟如下：

① 定義兩個字元變數 a、b；
② a=get char()；
③ b=a—32；

❺ 簡述內存管理中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由一個或者多個連續的物理頁面組成。這些頁面種包含了已分配的緩存對象，也包含了空閑對象。

❻ 操作系統第四章【2】內存空間管理---連續

  內存分為系統區和用戶區兩部分：

系統區：僅提供給OS使用，通常放在內存低址部分

用戶區：除系統區以外的全部內存空間，提供給用戶使用。

最簡單的一種存儲管理方式，只能用於單用戶、單任務的操作系統中。

優點：易於管理。

缺點：對要求內存空間少的程序，造成內存浪費；程序全部裝入，很少使用的程序部分也佔用內存。

把內存分為一些大小相等或不等的分區(partition)，每個應用進程佔用一個分區。操作系統佔用其中一個分區。

u提高：支持多個程序並發執行，適用於多道程序系統和分時系統。最早的多道程序存儲管理方式。

劃分為幾個分區，便只允許幾道作業並發

  1如何劃分分區大小：

n分區大小相等：只適合於多個相同程序的並發執行（處理多個類型相同的對象）。缺乏靈活性。

n分區大小不等：多個小分區、適量的中等分區、少量的大分區。根據程序的大小，分配當前空閑的、適當大小的分區。

  2需要的數據結構

建立一記錄相關信息的分區表（或分區鏈表），表項有: 起始位置 大小  狀態

分區表中，表項值隨著內存的分配和釋放而動態改變

3程序分配內存的過程：

也可將分區表分為兩個表格：空閑分區表/佔用分區表。從而減小每個表格長度。

檢索演算法：空閑分區表可能按不同分配演算法採用不同方式對表項排序(將分區按大小排隊或按分區地址高低排序)。

過程：檢索空閑分區表；找出一個滿足要求且尚未分配的分區，分配給請求程序；若未找到大小足夠的分區，則拒絕為該用戶程序分配內存。

固定分配的不足：

內碎片（一個分區內的剩餘空間）造成浪費

分區總數固定，限制並發執行的程序數目。

（3）動態分區分配

分區的大小不固定：在裝入程序時根據進程實際需要，動態分配內存空間，即——需要多少劃分多少。

空閑分區表項：從1項到n項：

內存會從初始的一個大分區不斷被劃分、回收從而形成內存中的多個分區。

動態分區分配

優點：並發進程數沒有固定數的限制，不產生內碎片。

缺點：有外碎片（分區間無法利用的空間）

1）數據結構

①空閑分區表：

•記錄每個空閑分區的情況。

•每個空閑分區對應一個表目，包括分區序號、分區始址及分區的大小等數據項。

②空閑分區鏈：

•每個分區的起始部分，設置用於控制分區分配的信息，及用於鏈接各分區的前向指針；

•分區尾部則設置一後向指針，在分區末尾重復設置狀態位和分區大小表目方便檢索。

2）分區分配演算法

  動態分區方式，分區多、大小差異各不相同，此時把一個新作業裝入內存，更需選擇一個合適的分配演算法，從空閑分區表/鏈中選出一合適分區

①首次適應演算法FF

②循環首次適應演算法

③最佳適應演算法

④最差適應演算法

⑤快速適應演算法

①首次適應演算法FF(first-fit)

1.空閑分區排序：以地址遞增的次序鏈接。

2.檢索：分配內存時，從鏈首開始順序查找直至找到一個大小能滿足要求的空閑分區；

3.分配：從該分區中劃出一塊作業要求大小的內存空間分配給請求者，餘下的空閑分區大小改變仍留在空閑鏈中。

u若從頭到尾檢索不到滿足要求的分區則分配失敗

優點：優先利用內存低址部分，保留了高地址部分的大空閑區；

缺點：但低址部分不斷劃分，會產生較多小碎片；而且每次查找從低址部分開始，會逐漸增加查找開銷。

②循環首次適應演算法(next-fit)

1.空閑分區排序：按地址

2.檢索：從上次找到的空閑分區的下一個空閑分區開始查找，直到找到一個能滿足要求的空閑分區。為實現演算法，需要：

©設置一個起始查尋指針

©採用循環查找方式

3.分配：分出需要的大小

優點：空閑分區分布均勻，減少查找開銷

缺點：缺乏大的空閑分區

③最佳適應演算法 (best-fit)

  總是把能滿足要求、又是最小的空閑分區分配給作業，避免「大材小用」。

1.空閑分區排序：所有空閑分區按容量從小到大排序成空閑分區表或鏈。

2.檢索：從表或鏈的頭開始，找到的第一個滿足的就分配

3.分配：分出需要的大小

  缺點：每次找到最合適大小的分區割下的空閑區也總是最小，會產生許多難以利用的小空閑區（外碎片）

④最差適應演算法/最壞匹配法(worst-fit)： 基本不留下小空閑分區，但會出現缺乏較大的空閑分區的情況。

⑤快速適應演算法

n根據進程常用空間大小進行劃分，相同大小的串成一個鏈，需管理多個各種不同大小的分區的鏈表。進程需要時，從最接近大小需求的鏈中摘一個分區。類似的：夥伴演算法

n能快速找到合適分區，但鏈表信息會很多；實際上是空間換時間。

3）分區分配操作

分配內存

找到滿足需要的合適分區，劃出進程需要的空間

s<=size，將整個分區分配給請求者

s> size，按請求的大小劃出一塊內存空間分配出去，餘下部分留在空閑鏈中，將分配區首址返回給調用者。

回收內存

進程運行完畢釋放內存時，系統根據回收區首址a，在空閑分區鏈(表)中找到相應插入點，根據情況修改空閑分區信息，可能會進行空閑分區的合並：

（4）動態重定位分區分配

——有緊湊功能的動態分區分配

用戶程序在內存中移動，將空閑空間緊湊起來提高空間利用率。但必然需要地址變化，增加「重定位」工作。

（5）內存空間管理之對換

當內存空間還是滿足不了需求時，引入「對換」思想：

  把內存中暫時不能運行、或暫時不用的程序和數據調到外存上，以騰出足夠的內存；把已具備運行條件的進程和進程所需要的程序和數據，調入內存。

u按對換單位分類：

Ø整體對換(或進程對換)：以整個進程為單位（連續分配）

Ø頁面對換或分段對換：以頁或段為單位（離散分配）

❼ 【我的筆記】內存管理（二）分區方法（靜態、動態、夥伴、Slab）

由操作系統或系統管理員預先將內存劃分成若干個分區。在系統運行過程中，分區的邊界不再改變。分配時，找一個空閑且足夠大的分區。如沒有合適的分區：①讓申請者等待。②先換出某分區的內容，再將其分配出去。

為申請者分配指定的分區或任選一個分區。如果沒有空閑分區，可將一個分區的內容換出。可能需要重定位。

會出現內部碎片，無法滿足大內存的需求。

可減少內部碎片。減少對大內存需求的限制。

①固定分配：只分配某種尺寸的特定分區，如分區已被使用，申請者必須等待。

可能出現不公平等待：雖有更大尺寸的空閑分區，卻必須等待。

②最佳適應分配：分配能滿足需要的最小尺寸的空閑分區，只有當所有分區都已用完時，申請者才需要等待。靈活，但可能產生較大的內部碎片。

3、靜態分區：內存利用率低，產生內部碎片；尺寸和分區數量難以確定。

1、不預先確定分區的大小和數量，將分區工作推遲到實際分配內存時進行。  Lazy

初始情況下，把所有的空閑內存看成一個大分區。分配時，按申請的尺寸，找一塊足夠大的空閑內存分區，臨時從中劃出一塊構成新分區。新分區的尺寸與申請的大小相等，不會出現內部碎片。回收時，盡可能與鄰近的空閑分區合並。在內存緊缺時，可將某個選定的分區換出。

2、會產生外部碎片，如下圖（內部碎片是指 eg：要 1M，分了 8M，產生 7M 的碎片）：

移動內存中的進程，將碎片集中起來，重新構成大的內存塊。需要運行時的動態重定位，費時。

（1）緊縮方向：向一頭緊縮，向兩頭緊縮。

（2）緊縮時機：①在釋放分區時，如果不能與空閑分區合並，則立刻進行緊縮。

好處是不存在外部碎片，壞處是費時。

②在內存分配時，如果剩餘的空閑空間總量能滿足要求但沒有一個獨立的空閑塊能滿足要求，則進行緊縮。

好處是減少緊縮次數。Lazy。

①最先適應演算法（First fit）：從頭開始，在滿足要求的第一個空閑塊中分配。

分區集中在內存的前部，大內存留在後面，便於釋放後的合並。

②最佳適應演算法（Best fit）：遍歷空閑塊，在滿足要求的最小空閑塊中分配。

留下的碎片最小，基本無法再用，需要更頻繁地緊縮。

③下一個適應演算法（Next fit）：從上次分配的位置開始，在滿足要求的下一個空閑塊中分配。

對內存的使用較平均，不容易留下大的空閑塊。

④最差適應演算法（Worst Fit）：遍歷空閑塊，在滿足要求的最大空閑塊中分配。

留下的碎片較大，但不會剩餘大內存。

最先適應演算法較優，最佳適應演算法較差。

夥伴演算法：將動態分區的大小限定為 2^k  位元組，分割方式限定為平分，分區就會變得較為規整，分割與合並會更容易，可以減少一些外部碎片。平分後的兩塊互稱夥伴。

1、

分配時可能要多次平分，釋放時可能要多次合並。舉例：

記錄大小不同的空閑頁：

示意圖：

2、

夥伴演算法是靜態分區和動態分區法的折中，比靜態分區法靈活，不受分區尺寸及個數的限制；比動態分區法規范，不易出現外部碎片。會產生內部碎片，但比靜態分區的小。

Linux、Windows、Ucore等都採用夥伴演算法管理物理內存。

一般情況下，將最小尺寸定為 2^12 位元組（1頁，4K=4096B），最大尺寸定為1024頁，11個隊列。

Linux、Windows、Ucore 等都將夥伴的最小尺寸限定為1頁。

ucore 用 page，在內存初始化函數 page_init 中為系統中的每個物理頁建立一個 page 結構。

頁塊（pageblock）是一組連續的物理頁。

5、

（1）判斷夥伴關系/尋找夥伴

最後兩行是指，B1和B2隻有第i位相反。

（2）判斷夥伴是否空閑：

ucore 用 free_area[ ]數組定義空閑頁塊隊列。

（3）確定夥伴是否在 order 隊列中：

7、

（1）解決內部碎片過大問題（eg：申請5頁，分配8頁，浪費3頁）：

ucore 在前部留下需要的頁數，釋放掉尾部各頁。每次釋放1頁，先劃分成頁塊，再逐個釋放。

（2） 解決切分與合並過於頻繁的問題：

用得較多的是單個頁。位於處理器Cache中頁稱為熱頁（hot page），其餘頁稱為冷頁（cold page）。處理器對熱頁的訪問速度要快於冷頁。

可建一個熱頁隊列（per_cpu_page），暫存剛釋放的單個物理頁，將合並工作向後推遲 Lazy。總是試圖從熱頁隊列中分配單個物理頁。分配與釋放都在熱頁隊列的隊頭進行。

（3）解決內存碎化(有足夠多的空閑頁，但是沒有大頁塊)問題：①將頁塊從一個物理位置移動到另一個物理位置，並保持移動前後邏輯地址不變（拷貝頁塊內容）；②邏輯內存管理器。

（4）滿足大內存的需求：

（5）物理內存空間都耗盡的情況：

在任何情況下，都應該預留一部分空閑的物理內存以備急需。定義兩條基準線low和high，當空閑內存量小於low時，應立刻開始回收物理內存，直到空閑內存量大於high。

（6）回收物理內存：

法一：啟動一個守護進程，專門用於回收物理內存。周期性啟動，也可被喚醒。

法二：申請者自己去回收內存。實際是由內存分配程序回收。回收的方法很多，如釋放緩沖區、頁面淘汰等。

1、

夥伴演算法最小分配內存為頁，對於更小的內存的管理 --> Slab 演算法

內和運行過程中經常使用小內存（小於1頁）eg：建立數據結構、緩沖區

內核對小內存的使用極為頻繁、種類繁多、時機和數量難以預估。所以難以預先分配，只能動態地創建和撤銷

2、

Slab 向夥伴演算法申請大頁塊（批發），將其劃分成小對象分配出去（零售）；將回收的小對象組合成大頁塊後還給夥伴演算法。

Slab 採用等尺寸靜態分區法，將頁塊預先劃分成一組大小相等的小塊，稱為內存對象。

具有相同屬性的多個Slab構成一個Cache，一個Cache管理一種類型（一類應該是指一個大小）的內存對象。當需要小內存時，從預建的Cache中申請內存對象，用完之後再將其還給Cache。當Cache中缺少對象時，追加新的Slab；當物理內存緊缺時，回收完全空閑的Slab。

Slab 演算法的管理結構：

① Cache 管理結構：管理Slab，包括Slab的創建和銷毀。

② Slab 管理結構：管理內存對象，包括小對象的分配與釋放。

（Cache結構和Slab結構合作，共同實現內存對象的管理）

3、

（1）描述各個內存對象的使用情況

可以用點陣圖標識空閑的內存對象。也可以將一個Slab中的空閑內存對象組織成隊列，並在slab結構中記錄隊列的隊頭。

早期的Linux在每個內存對象的尾部都加入一個指針，用該指針將空閑的內存對象串聯成一個真正的隊列。（對象變長、不規范，空間浪費）

改進：將指針集中在一個數組中，用數組內部的鏈表模擬內存對象隊列。

再改進：將數組中的指針換成對象序號，利用序號將空閑的內存對象串成隊列。序號數組是動態創建的。

序號數組可以位於 Slab 內部，也可以位於 Slab 外部

（2）一個Cache會管理多個Slab，可以將所有Slab放在一個隊列中。

Ucore為每個Cache准備了兩個slab結構隊列：全滿的和不滿的。Linux為每個Cache准備了三個slab結構隊列：部分滿的、完全滿的和完全空閑的。

Linux允許動態創建Cache，Ucore不許。Ucore預定了對象大小，分別是32、64、128、256、512、1K、2K（4K、8K、16K、32K、64K、128K）。為每一種大小的對象預建了Cache。

（3）Slab是動態創建的，當Cache中沒有空閑的內存對象時，即為其創建一個新的Slab。

Slab所需要的內存來自夥伴演算法，大小是  2^page_order 個連續頁。

4、小對象的尺寸

如按處理器一級緩存中緩存行（Cache Line）的大小（16、32位元組）取齊，可使對象的開始位置都位於緩存行的邊界處。

在將頁塊劃分成內存對象的過程中，通常會剩餘一小部分空間，位於所有內存對象之外，稱為外部碎片。

Slab演算法選用碎片最小的實現方案。

5、

（1）對象分配 kmalloc

① 根據size確定一個Cache。

② 如果Cache的slabs_notfull為空，則為其創建一個新的Slab。

③ 選中slabs_notfull中第一個Slab，將隊頭的小對象分配出去，並調整隊列。

④ 對象的開始地址是：objp = slabp->s_mem + slabp->free * cachep->objsize;

（2）對象釋放 kfree

① 算出對象所在的頁號，找到它的 Page 結構。

② 根據 Page 找到所屬的 Cache 和 Slab。

③ 算出對象序號：objnr = (objp - slabp->s_mem) / cachep->objsize;

④將序號插入Slab的free隊列。

⑤整Slab所屬隊列。

❽ 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虛擬內存對應的頁表，並尋找到對應的頁表項。

獲取頁表項對應的頁面指針

通過頁面得到對應的內核物理內存映射區域地址。

如下圖所示：

第二是當訪問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文件，將取自內核的信息列印到屏幕上。