在使用早期的計算機上撰寫程式時，有關資料存盤在什么位置等這樣的問題都是需要程式員自己來給資料分配記憶體，
而現在的高級語言，大大的減少了程式員的作業，不需要直接和存盤空間打交道，程式在編譯時由編譯程式去合理地分配空間，
本文重點解決的問題是：
? 對于用戶向系統提出的申請空間的請求，系統如何分配記憶體？
? 當用戶不在使用之前申請的記憶體空間后，系統又如何回收？
這里的用戶，不是普通意義上的用戶，可能是一個普通的變數，一個應用程式，一個命令等等，只要是向系統發出記憶體申請的，都可以稱之為用戶，
占用塊和空閑塊
對于計算機中的記憶體來說，稱已經分配給用戶的的記憶體區統稱為“占用塊”；還未分配出去的記憶體區統稱為“空閑塊”或者“可利用空間塊”，
系統的記憶體管理
對于初始狀態下的記憶體來說，整個空間都是一個空閑塊（在編譯程式中稱為“堆”），但是隨著不同的用戶不斷地提出存盤請求，系統依次分配，
整個記憶體區就會分割成兩個大部分：低地址區域會產生很多占用塊；高地址區域還是空閑塊，如下圖所示：
但是當某些用戶運行結束，所占用的記憶體區域就變成了空閑塊，如下圖所示：
此時，就形成了占用塊和空閑塊犬牙交錯的狀態，當后續用戶請求分配記憶體時，系統有兩種分配方式：
1、系統繼續利用高地址區域的連續空閑塊分配給用戶，不去理會之前分配給用戶的記憶體區域的狀態，直到分配無法進行，也就是高地址的空閑塊不能滿足用戶的需求時，系統才會去回收之前的空閑塊，重新組織繼續分配；
2、當用戶運行一結束，系統馬上將其所占空間進行回收，當有新的用戶請求分配記憶體時，系統遍歷所有的空閑塊，從中找出一個合適的空閑塊分配給用戶，
合適的空閑塊指的是能夠滿足用戶要求的空閑塊，具體的查找方式有多種，后續會介紹，
可利用空間表
當采用第 2 種方式時，系統需要建立一張記錄所有空閑塊資訊的表，表的形式有兩種：目錄表和鏈表，各自的結構如下圖所示：
目錄表：表中每一行代表一個空閑塊，由三部分組成：
? 初始地址：記錄每個空閑塊的起始地址，
? 空閑塊大小：記錄每個空閑塊的記憶體大小，
? 使用情況：記錄每個空閑塊是否存盤被占用的狀態，
鏈表：表中每個結點代表一個空閑塊，每個結點中需要記錄空閑塊的使用情況、大小和連接下一個空閑塊的指標域，
由于鏈表中有指標的存在，所以結點中不需要記錄各記憶體塊的起始地址，
————————
系統在不同的環境中運行，根據用戶申請空間的不同，存盤空閑塊的可利用空間表有以下不同的結構：
1、如果每次用戶請求的存盤空間大小相同，對于此類系統中的記憶體來說，在用戶運行初期就將整個記憶體存盤塊按照所需大小進行分割，然后通過鏈表鏈接，當用戶申請空間時，從鏈表中摘除一個結點歸其使用；用完后再鏈接到可利用空間表上，
2、每次如果用戶申請的都是若干種大小規格的存盤空間，針對這種情況可以建立若干個可利用空間表，每一個鏈表中的結點大小相同，當用戶申請某一規格大小的存盤空間時，就從對應的鏈表中摘除一個結點供其使用；用完后鏈接到相同規格大小的鏈表中，
3、用戶申請的記憶體的大小不固定，所以造成系統分配的記憶體塊的大小也不確定，回收時，鏈接到可利用空間表中每個結點的大小也各不一樣，
第 2 種情況下容易面臨的問題是：如果同用戶申請空間大小相同的鏈表中沒有結點時，就需要找結點更大的鏈表，從中取出一個結點，一部分給用戶使用，剩余部分插入到相應大小的鏈表中；回收時，將釋放的空閑塊插入到大小相同的鏈表中去，如果沒有比用戶申請的記憶體空間相等甚至更大的結點時，就需要系統重新組織一些小的連續空間，然后給用戶使用，
分配存盤空間的方式
通常情況下系統中的可利用空間表是第 3 種情況，如圖 3(C) 所示，由于鏈表中各結點的大小不一，在用戶申請記憶體空間時，就需要從可利用空間表中找出一個合適的結點，有三種查找的方法：
? 首次擬合法：在可利用空間表中從頭開始依次遍歷，將找到的第一個記憶體不小于用戶申請空間的結點分配給用戶，剩余空間仍留在鏈表中；回收時只要將釋放的空閑塊插入在鏈表的表頭即可，
? 最佳擬合法：和首次擬合法不同，最佳擬合法是選擇一塊記憶體空間不小于用戶申請空間，但是卻最接近的一個結點分配給用戶，為了實作這個方法，首先要將鏈表中的各個結點按照存盤空間的大小進行從小到大排序，由此，在遍歷的程序中只需要找到第一塊大于用戶申請空間的結點即可進行分配；用戶運行完成后，需要將空閑塊根據其自身的大小插入到鏈表的相應位置，
? 最差擬合法：和最佳擬合法正好相反，該方法是在不小于用戶申請空間的所有結點中，篩選出存盤空間最大的結點，從該結點的記憶體空間中提取出相應的空間給用戶使用，為了實作這一方法，可以在開始前先將可利用空間表中的結點按照存盤空間大小從大到小進行排序，第一個結點自然就是最大的結點，回收空間時，同樣將釋放的空閑塊插入到相應的位置上，
以上三種方法各有所長：
? 最佳擬合法由于每次分配相差不大的結點給用戶使用，所以會生成很多存盤空間特別小的結點，以至于根本無法使用，使用程序中，鏈表中的結點存盤大小發生兩極分化，大的很大，小的很小，該方法適用于申請記憶體大小范圍較廣的系統
? 最差擬合法，由于每次都是從存盤空間最大的結點中分配給用戶空間，所以鏈表中的結點大小不會起伏太大，依次適用于申請分配記憶體空間較窄的系統，
? 首次擬合法每次都是隨機分配，在不清楚用戶申請空間大小的情況下，使用該方法分配空間，
同時，三種方法中，最佳擬合法相比于其它兩種方式，無論是分配程序還是回收程序，都需要遍歷鏈表，所有最費時間，
空間分配與回收程序產生的問題
無論使用以上三種分配方式中的哪一種，最終記憶體空間都會成為一個一個特別小的記憶體空間，對于用戶申請的空間的需求，單獨拿出任何一個結點都不能夠滿足，
但是并不是說整個記憶體空間就不夠用戶使用，在這種情況下，就需要系統在回收的程序考慮將地址相鄰的空閑塊合并，
最后，不管你是轉行也好，初學也罷，進階也可，如果你想學編程~
【值得關注】我的 C/C++編程學習交流俱樂部【點擊進入】
問題答疑，學習交流，技術探討，還有超多編程資源大全，零基礎的視頻也超棒~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261655.html
標籤：其他
上一篇：「NOTE」進階多項式小札