操作系統——分區存儲管理
- 2019 年 10 月 16 日
- 筆記
分區存儲管理是把主存儲器中的用戶區作為一個連續區或分成若干個連續區進行管理，每個連續區中可裝入一個作業。
多道程序系統一般都採用多個分區的存儲管理，具體可分為固定分區和可變分區兩種方式。
一、固定分區存儲管理
把主存中可分配的用戶區域預先劃分成若干個連續的分區，每個連續區的大小可以相同，也可以不同。但是，一旦劃分好分區之後，主存中分區的個數就固定了，且每個分區的大小也固定不變。這是一種靜態分區法。
在固定分區方式管理下，每個分區用來裝入一個作業。由於主存中有多個分區，就可同時在每個分區中裝入一個作業。所以，這種存儲管理方式適用於多道程序系統。
1、主存空間的分配與釋放
為了管理主存空間的使用，必須設置一張“主存分配表”（分區說明表），以說明各分區的分配情況。主存分配表中應指出各分區的起始地址和長度，並為每個分區設一個標誌位。當標誌位為“0”時，表示對應的分區是空閑分區，當標誌位為非“0”時，表示對應的分區已被某作業佔用。空閑分區可以用來裝作業。
當作業隊列中有作業要裝入主存時，存儲管理可採用“順序分配算法”進行主存空間的分配。
順序查看主存分配表，找到一個標誌為“0”的並且長度大於或等於欲裝入作業的地址空間長度的分區，則把此分區分配給該作業，相應表目的標誌位改成作業名的標識；若找不到一個這樣的空閑分區，則該作業暫時不能裝入主存。
主存空間的釋放很簡單。某作業執行結束後必須歸還所佔的分區，這時存儲管理根據作業名查看主存分配表，找到相應的表目後，把其中的標誌位重新置成“0”即可。
2、地址轉換
固定分區管理方式下作業的地址轉換常採用靜態重定位技術。
3、存儲保護
固定分區管理方式下只考慮判斷其物理地址即可。常採用“界限寄存器對”法。
If 下限地址<=物理地址<=上限地址
Then 繼續
Else 產生“越界中斷” ，轉越界中斷的處理子程序
4．內存擴充
採用覆蓋技術
5．固定分區的優缺點
優點：實現簡單，無外部碎片
缺點：
a.當用戶程序太大時，可能所有的分區都不能滿足需求，此時不得不採用覆蓋技術解決，但這又會降低性能
b.會產生內部碎片，碎片大，存在小分區佔用大作業的情況，內存利用率低。
解決辦法：採用可變分區存儲管理
二、可變分區存儲管理
內存管理的可變分區模式，又稱變長分區模式、動態分區分配模式。這種分配方式不會預先劃分內存分區，而是在進程裝入內存時，根據進程的大小動態地建立分區，並使分區的大小正好適合進程的需要。因此系統分區的大小和數目是可變的。
與固定分區的區別就是：動態的劃分分區。
克服固定分區管理的“內碎片”問題。
1.可變分區模式下，剛開始，OS就緒，但任何用戶程序未進入內存前整個用戶內存區是一大空間。已佔用區和空閑分區並不是絕對的。
2.必須有表來記錄分區的情況。
3.程序進入內存時的例行工作就是分配空閑區和裝入程序，並修改相應的空閑表和已分配區表。
4.一旦一個內存分區被分配給一個進程，該進程可以被裝入該塊中執行，裝入時需重定位。
可變分區分配的數據結構
系統要使用什麼樣的數據結構來記錄內存的使用情況？
可變分區分配算法
把一個新作業裝入內存時，需要按照一定的可變分區分配算法，從空閑分區表（或空閑分區鏈）中選出一個分區分配給該作業。
在可變分區分配方式中，當有很多空閑分區都滿足需求時，應該使用哪個分區進行分配?
這裡介紹三種可變分區分配算法
最先適應分配算法
算法思想：每次都從低地址開始查找，找到第一個能滿足大小的空閑分區。
實現步驟：
空閑區地址由低到高排序
=>1.順序查找各個空閑區，把第一個找到能容納申請要求的內存區分配給申請者.（若空閑區比作業長度大，則分割該空閑區。一部分分配給作業一部分空閑。）
=>2.調整相應的空閑分區表和已分配分區表。
評價：性能一般但實現比較簡單直接，易於釋放時合併相鄰空間分區。比較容易的滿足大作業的需要。完成一次分配平均需要的搜索次數較大，影響了工作效率。
儘可能地利用存儲器中低地址的空閑區，而盡量保存高地址的空閑區。
最佳適應算法
算法思想：由於可變分區分配是一種連續分配方式，為各進程分配的空間必須是連續的一整片區域。因此為了保證當“大進程”到來時能有連續的大片空間，優先使用更小的空閑區。
實現步驟：
空閑分區按容量遞增次序鏈接。每次分配內存時順序查找空閑分區表，找到大小能夠滿足要求的第一個空閑分區。
評價：儘可能地保留了較大的空間。 產生大量的不能被使用的很小的空閑區。因此這種方法會產生很多的外部碎片。所以該算法分配效果不一定是最佳的。
儘可能地利用存儲器中小的空閑區，而盡量保存大的空閑區。
最壞適應算法
算法思想：為了解決最佳適應算法的問題——即留下太多難以利用的小碎片，可以在每次分配時，優先使用最大的連續空閑區，這樣分配後的空閑區就不會太小，更方便使用。
實現步驟：
空閑分區按照容量遞減次序鏈接。每次分配內存時順序查找空閑分區表，找到大小能滿足要求的第一個空閑分區。
評價：分割後產生的空閑區一般仍可以供以後分配使用。工作一段時間後，不能滿足大作業對空閑區的請求。
儘可能地利用存儲器中大的空閑區。
三種算法的比較：
可變分區內存回收
只比固定分區管理增加了合併相鄰空閑區的操作。
主要是為了及時減少“外碎片”，利於今後大作業的到來。
實現回收內存空間，關鍵是修改空閑分區表和已分配分區表。
回收內存分區時可能會遇到的四種情況：
(a)若釋放區R既有上鄰空閑區，又有下鄰空閑區。將三個空閑區合併成一個大空閑區。
先將R與F2合併記為F2,
再將F2與F1合併記為F1,並將F2從鏈中刪除。
IF (B+H1=C) AND (C+L2=D)
THEN 修改空閑表，分配表。
(b)若釋放區R只有上鄰空閑區F1。
則只修改空閑區F1大小即可。
IF (D+H2=E)
THEN 修改空閑表，分配表。
(c)只有下鄰空閑區
修改空閑區F2的首地址。
F2的大小＝F2的大小＋R的大小
(d)既無上鄰又無下鄰空閑區
Else 修改釋放區的首地址為空閑區的起始地址
地址轉換
動態重定位
分區的存儲保護
If 下限地址<=物理地址<=上限地址
Then 繼續
Else 產生“越界中斷” ，轉越界中斷的處理子程序
內存擴充
消除了固定分區管理造成的“內碎片”，但是不可避免的在內存空間造成“外碎片”。
採用移動（緊縮）技術。定時的或在內存緊張時，將內存中所有作業移到內存的一端，使其相鄰。
經過緊縮後的進程在內存中的位置發生了變化，若不對程序和數據的地址進行修改，在進程就無法運行。
要使其運行，必須進行“動態重定位”
注意：
＝》緊縮的時機：
（1）一旦有歸還的分區便進行緊縮，系統開銷大。
（2）分配算法發現各空閑區不夠用，但其和夠用時。此法緊縮開銷小，更實用。因此，實際的可變分區分配算法比固定分區分配算法主要增加了“緊縮”操作
