A. 【我的筆記】內存管理（二）分區方法（靜態、動態、夥伴、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所屬隊列。
B. 求編程領域上一些經典演算法同時也是程序員必須掌握的演算法
這是我在一個論壇里看到的，你也參考參考吧。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的演算法啟動數據發送。
一次發送可能是你提交數據的一部分，一定要當心，否則出問題沒處找去。
C. 夥伴演算法和slab演算法
內存碎片太小和管理內存碎片的效率問題
原因：分配內存時，不能將相鄰內存合並
解決辦法：
如果申請的內存大小為n，則向上取整為2的冪次數，定位到響應組，到組中(鏈表上)找空閑塊分配出去；若沒有空閑塊，則到上一組找，直到找到為止，並將剩餘的內存放到下面適當的組中。
用完內存需要歸還，根據實際內存塊大小向上取整為2的冪次數，歸入鏈表。
註：夥伴演算法使用點陣圖標記內存塊的使用情況
slab以內存池為思想，解決內部碎片問題，專門解決小內存問題。
D. 外碎片與內碎片
內部碎片
是處於操作系統分配的用於裝載某一進程的內存區域內部的存儲塊。佔有這些區域或頁面的進程並不使用這個存儲塊。而在進程佔有這塊存儲塊時，系統無法利用它。直到進程釋放它，或進程結束時，系統才有可能利用這個存儲塊。
外部碎片
外部碎片指的是還沒有被分配出去（不屬於任何進程），但由於太小了無法分配給申請內存空間的新進程的內存空閑區域。
外部碎片是處於任何兩個已分配區域或頁面之間的空閑存儲塊。這些存儲塊的總和可以滿足當前申請的長度要求，但是由於它們的地址不連續或其他原因，使得系統無法滿足當前申請。
內部碎片的產生 ：因為所有的內存分配必須起始於可被 4、8 或 16 整除（視處理器體系結構而定）的地址或者因為MMU的分頁機制的限制，決定內存分配演算法僅能把預定大小的內存塊分配給客戶。假設當某個客戶請求一個 43 位元組的內存塊時，因為沒有適合大小的內存，所以它可能會獲得 44位元組、48位元組等稍大一點的位元組，因此由所需大小四捨五入而產生的多餘空間就叫內部碎片。
外部碎片的產生 ： 頻繁的分配與回收物理頁面會導致大量的、連續且小的頁面塊夾雜在已分配的頁面中間，就會產生外部碎片。假設有一塊一共有100個單位的連續空閑內存空間，范圍是0 99。如果你從中申請一塊內存，如10個單位，那麼申請出來的內存塊就為0 9區間。這時候你繼續申請一塊內存，比如說5個單位大，第二塊得到的內存塊就應該為10 14區間。如果你把第一塊內存塊釋放，然後再申請一塊大於10個單位的內存塊，比如說20個單位。因為剛被釋放的內存塊不能滿足新的請求，所以只能從15開始分配出20個單位的內存塊。現在整個內存空間的狀態是0 9空閑，10 14被佔用，15 24被佔用，25 99空閑。其中0 9就是一個內存碎片了。如果10 14一直被佔用，而以後申請的空間都大於10個單位，那麼0 9就永遠用不上了，變成外部碎片。
夥伴演算法(buddy)用來解決外碎片
slab演算法用來解決內碎片
E. 操作系統第四章【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按對換單位分類：
Ø整體對換(或進程對換)：以整個進程為單位（連續分配）
Ø頁面對換或分段對換：以頁或段為單位（離散分配）