一篇看懂！操作系統(tǒng)一一分區(qū)存儲管理！
分區(qū)存儲管理是把主存儲器中的用戶區(qū)作為一個連續(xù)區(qū)或分成若干個連續(xù)區(qū)進(jìn)行管理，每個連續(xù)區(qū)中可裝入一個作業(yè)。
多道程序系統(tǒng)一般都采用多個分區(qū)的存儲管理，具體可分為固定分區(qū)和可變分區(qū)兩種方式。
一、固定分區(qū)存儲管理
把主存中可分配的用戶區(qū)域預(yù)先劃分成若干個連續(xù)的分區(qū)，每個連續(xù)區(qū)的大小可以相同，也可以不同。但是，一旦劃分好分區(qū)之后，主存中分區(qū)的個數(shù)就固定了，且每個分區(qū)的大小也固定不變。這是一種靜態(tài)分區(qū)法。
在固定分區(qū)方式管理下，每個分區(qū)用來裝入一個作業(yè)。由于主存中有多個分區(qū)，就可同時在每個分區(qū)中裝入一個作業(yè)。所以，這種存儲管理方式適用于多道程序系統(tǒng)。
1、主存空間的分配與釋放
為了管理主存空間的使用，必須設(shè)置一張“主存分配表”（分區(qū)說明表），以說明各分區(qū)的分配情況。主存分配表中應(yīng)指出各分區(qū)的起始地址和長度，并為每個分區(qū)設(shè)一個標(biāo)志位。當(dāng)標(biāo)志位為“0”時，表示對應(yīng)的分區(qū)是空閑分區(qū)，當(dāng)標(biāo)志位為非“0”時，表示對應(yīng)的分區(qū)已被某作業(yè)占用?？臻e分區(qū)可以用來裝作業(yè)。
當(dāng)作業(yè)隊列中有作業(yè)要裝入主存時，存儲管理可采用“順序分配算法”進(jìn)行主存空間的分配。 順序查看主存分配表，找到一個標(biāo)志為“0”的并且長度大于或等于欲裝入作業(yè)的地址空間長度的分區(qū)，則把此分區(qū)分配給該作業(yè)，相應(yīng)表目的標(biāo)志位改成作業(yè)名的標(biāo)識；若找不到一個這樣的空閑分區(qū)，則該作業(yè)暫時不能裝入主存。
主存空間的釋放很簡單。某作業(yè)執(zhí)行結(jié)束后必須歸還所占的分區(qū)，這時存儲管理根據(jù)作業(yè)名查看主存分配表，找到相應(yīng)的表目后，把其中的標(biāo)志位重新置成“0”即可。
2、地址轉(zhuǎn)換
固定分區(qū)管理方式下作業(yè)的地址轉(zhuǎn)換常采用靜態(tài)重定位技術(shù)。
3、存儲保護(hù)
固定分區(qū)管理方式下只考慮判斷其物理地址即可。常采用“界限寄存器對”法。
If ? ? ? ? ? 下限地址<=物理地址<=上限地址
Then ? ? ?繼續(xù)
Else ? ? ? ?產(chǎn)生“越界中斷” ，轉(zhuǎn)越界中斷的處理子程序
4．內(nèi)存擴(kuò)充
采用覆蓋技術(shù)
5．固定分區(qū)的優(yōu)缺點
優(yōu)點：實現(xiàn)簡單，無外部碎片
缺點：
當(dāng)用戶程序太大時，可能所有的分區(qū)都不能滿足需求，此時不得不采用覆蓋技術(shù)解決，但這又會降低性能
會產(chǎn)生內(nèi)部碎片，碎片大，存在小分區(qū)占用大作業(yè)的情況，內(nèi)存利用率低。
解決辦法：采用可變分區(qū)存儲管理
二、可變分區(qū)存儲管理
內(nèi)存管理的可變分區(qū)模式，又稱變長分區(qū)模式、動態(tài)分區(qū)分配模式。這種分配方式不會預(yù)先劃分內(nèi)存分區(qū)，而是在進(jìn)程裝入內(nèi)存時，根據(jù)進(jìn)程的大小動態(tài)地建立分區(qū)，并使分區(qū)的大小正好適合進(jìn)程的需要。因此系統(tǒng)分區(qū)的大小和數(shù)目是可變的。
與固定分區(qū)的區(qū)別就是：動態(tài)的劃分分區(qū)。
克服固定分區(qū)管理的“內(nèi)碎片”問題。
1.可變分區(qū)模式下，剛開始，OS就緒，但任何用戶程序未進(jìn)入內(nèi)存前整個用戶內(nèi)存區(qū)是一大空間。已占用區(qū)和空 閑分區(qū)并不是絕對的。 2.必須有表來記錄分區(qū)的情況。 3.程序進(jìn)入內(nèi)存時的例行工作就是分配空閑區(qū)和裝入程序，并修改相應(yīng)的空閑表和已分配區(qū)表。 4.一旦一個內(nèi)存分區(qū)被分配給一個進(jìn)程，該進(jìn)程可以被裝入該塊中執(zhí)行，裝入時需重定位。
可變分區(qū)分配的數(shù)據(jù)結(jié)構(gòu)
系統(tǒng)要使用什么樣的數(shù)據(jù)結(jié)構(gòu)來記錄內(nèi)存的使用情況？
可變分區(qū)分配算法
把一個新作業(yè)裝入內(nèi)存時，需要按照一定的可變分區(qū)分配算法，從空閑分區(qū)表（或空閑分區(qū)鏈）中選出一個分區(qū)分配給該作業(yè)。
在可變分區(qū)分配方式中，當(dāng)有很多空閑分區(qū)都滿足需求時，應(yīng)該使用哪個分區(qū)進(jìn)行分配?
這里介紹三種可變分區(qū)分配算法
最先適應(yīng)分配算法
算法思想：每次都從低地址開始查找，找到第一個能滿足大小的空閑分區(qū)。
實現(xiàn)步驟：
空閑區(qū)地址由低到高排序 1.順序查找各個空閑區(qū)，把第一個找到能容納申請要求的內(nèi)存區(qū)分配給申請者.（若空閑區(qū)比作業(yè)長度大，則分割該空閑區(qū)。一部分分配給作業(yè)一部分空閑。） 2.調(diào)整相應(yīng)的空閑分區(qū)表和已分配分區(qū)表。
評價：性能一般但實現(xiàn)比較簡單直接，易于釋放時合并相鄰空間分區(qū)。比較容易的滿足大作業(yè)的需要。完成一次分配平均需要的搜索次數(shù)較大，影響了工作效率。
盡可能地利用存儲器中低地址的空閑區(qū)，而盡量保存高地址的空閑區(qū)。
最佳適應(yīng)算法
算法思想：由于可變分區(qū)分配是一種連續(xù)分配方式，為各進(jìn)程分配的空間必須是連續(xù)的一整片區(qū)域。因此為了保證當(dāng)“大進(jìn)程”到來時能有連續(xù)的大片空間，優(yōu)先使用更小的空閑區(qū)。
實現(xiàn)步驟：
1.空閑分區(qū)按容量遞增次序鏈接。每次分配內(nèi)存時順序查找空閑分區(qū)表，找到大小能夠滿足要求的第一個空閑分區(qū)。
評價：盡可能地保留了較大的空間。 產(chǎn)生大量的不能被使用的很小的空閑區(qū)。因此這種方法會產(chǎn)生很多的外部碎片。所以該算法分配效果不一定是最佳的。
盡可能地利用存儲器中小的空閑區(qū)，而盡量保存大的空閑區(qū)。
最壞適應(yīng)算法
算法思想：為了解決最佳適應(yīng)算法的問題——即留下太多難以利用的小碎片，可以在每次分配時，優(yōu)先使用最大的連續(xù)空閑區(qū)，這樣分配后的空閑區(qū)就不會太小，更方便使用。
實現(xiàn)步驟：
1.空閑分區(qū)按照容量遞減次序鏈接。每次分配內(nèi)存時順序查找空閑分區(qū)表，找到大小能滿足要求的第一個空閑分區(qū)。
評價：分割后產(chǎn)生的空閑區(qū)一般仍可以供以后分配使用。工作一段時間后，不能滿足大作業(yè)對空閑區(qū)的請求。
盡可能地利用存儲器中大的空閑區(qū)。
三種算法的比較：
可變分區(qū)內(nèi)存回收
只比固定分區(qū)管理增加了合并相鄰空閑區(qū)的操作。
主要是為了及時減少“外碎片”，利于今后大作業(yè)的到來。
實現(xiàn)回收內(nèi)存空間，關(guān)鍵是修改空閑分區(qū)表和已分配分區(qū)表。
回收內(nèi)存分區(qū)時可能會遇到的四種情況：
(a)若釋放區(qū)R既有上鄰空閑區(qū)，又有下鄰空閑區(qū)。將三個空閑區(qū)合并成一個大空閑區(qū)。
先將R與F2合并記為F2,
再將F2與F1合并記為F1,并將F2從鏈中刪除。
IF ? ? (B+H1=C) AND (C+L2=D)
THEN ? 修改空閑表，分配表。 (b)若釋放區(qū)R只有上鄰空閑區(qū)F1。則只修改空閑區(qū)F1大小即可。
IF ? ? (D+H2=E)
THEN ? 修改空閑表，分配表。
(c)只有下鄰空閑區(qū)
修改空閑區(qū)F2的首地址。
F2的大?。紽2的大?。玆的大小
(d)既無上鄰又無下鄰空閑區(qū)
Else ? ? ? ? 修改釋放區(qū)的首地址為空閑區(qū)的起始地址
地址轉(zhuǎn)換
動態(tài)重定位
分區(qū)的存儲保護(hù)
If ? ? ? ? ? 下限地址<=物理地址<=上限地址
Then ? ? ? ? ? ? 繼續(xù)
Else ? ? ? ?產(chǎn)生“越界中斷” ，轉(zhuǎn)越界中斷的處理子程序
內(nèi)存擴(kuò)充
消除了固定分區(qū)管理造成的“內(nèi)碎片”，但是不可避免的在內(nèi)存空間造成“外碎片”。 采用移動（緊縮）技術(shù)。定時的或在內(nèi)存緊張時，將內(nèi)存中所有作業(yè)移到內(nèi)存的一端，使其相鄰。 經(jīng)過緊縮后的進(jìn)程在內(nèi)存中的位置發(fā)生了變化，若不對程序和數(shù)據(jù)的地址進(jìn)行修改，在進(jìn)程就無法運行。 要使其運行，必須進(jìn)行“動態(tài)重定位”
注意：
緊縮的時機(jī)： （1）一旦有歸還的分區(qū)便進(jìn)行緊縮，系統(tǒng)開銷大。 （2）分配算法發(fā)現(xiàn)各空閑區(qū)不夠用，但其和夠用時。此法緊縮開銷小，更實用。因此，實際的可變分區(qū)分配算 ?法比固定分區(qū)分配算法主要增加了“緊縮”操作
三、 伙伴系統(tǒng)（buddy system）
伙伴系統(tǒng)可看作固定分區(qū)分配和可變分區(qū)分配的一種折中方案。
采用伙伴系統(tǒng)時，內(nèi)存是以2的冪次個字節(jié)大小的空閑塊為分配單位的。系統(tǒng)初啟時，只有1個最大的2的冪次的空閑塊，它就是整個可用的內(nèi)存空間。當(dāng)1個進(jìn)程申請內(nèi)存時，系統(tǒng)就分給它1個大于或等于進(jìn)程所申請尺寸的最小的2的冪次的空閑塊。
例如，某進(jìn)程提出的50KB的內(nèi)存請求，將首先被系統(tǒng)向上取整，轉(zhuǎn)化為對1個64KB的空閑塊的請求。如果此時不存在如此大小的空閑塊，則此時可獲得的1個最小的比該空閑塊大的空閑塊將被對分成2個“伙伴”單位。對其中1個伙伴單位的對分過程可能還要繼續(xù)下去，直到獲得1個64KB的空閑塊為止。
伙伴系統(tǒng)的內(nèi)存釋放算法考慮將兩個伙伴單位合并成1個大1倍的空閑單位。且這個合并過程會遞歸下去，直到不能繼續(xù)合并為止。
注意觀察下圖，合并后的空閑區(qū)塊也必須是2的冪次個字節(jié)
為了實現(xiàn)伙伴系統(tǒng)，系統(tǒng)要為每一種可能的空閑塊維護(hù)1個空閑塊鏈表。設(shè)系統(tǒng)管理的可用內(nèi)存空間共為2N個字節(jié)，則1個伙伴系統(tǒng)最多需要維護(hù)N個空閑塊鏈表。由于每種尺寸的空閑塊都有一個空閑塊隊列，因此內(nèi)存的分配與釋放可以有效地進(jìn)行。
伙伴系統(tǒng)的最大缺陷是不能有效地利用內(nèi)存，特別是內(nèi)碎片嚴(yán)重。例如，1個257KB的進(jìn)程需要占用1個512KB的分配單位，其中將產(chǎn)生255KB的內(nèi)碎片。另外，每次釋放內(nèi)存時都盡可能地合并伙伴單位的做法也會降低系統(tǒng)性能，因為剛合并好的塊可能馬上又要對分。一種改進(jìn)的做法是延遲合并的時機(jī)。如今Linux用它。
