ch4計(jì)算機(jī)存儲(chǔ)器管理課件

第四章存儲(chǔ)器管理4.0準(zhǔn)備知識(shí)4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3根本分頁(yè)存儲(chǔ)管理方式4.4根本分段存儲(chǔ)管理方式4.5虛擬存儲(chǔ)器的根本概念4.6請(qǐng)求分頁(yè)存儲(chǔ)管理方式4.7頁(yè)面置換算法4.8請(qǐng)求分段存儲(chǔ)管理方式第四章存儲(chǔ)器管理4.0準(zhǔn)備知識(shí)1近年來(lái)，微電子技術(shù)及大規(guī)模集成電路取得了長(zhǎng)足的進(jìn)步，以半導(dǎo)體芯片組成的存儲(chǔ)器，其容量由過(guò)去的幾百、幾千字節(jié)擴(kuò)大到幾十兆字節(jié)，甚至更大容量的存儲(chǔ)器已經(jīng)問(wèn)世。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的拓寬，目前不少企事業(yè)部門(mén)要求應(yīng)用計(jì)算機(jī)來(lái)實(shí)現(xiàn)管理現(xiàn)代化，建立綜合的管理信息系統(tǒng)，其要求存儲(chǔ)的數(shù)據(jù)量愈來(lái)愈大；另外軟件資源也愈來(lái)愈豐富，系統(tǒng)軟件和應(yīng)用軟件在種類(lèi)、功能及其所需存儲(chǔ)空間等都在急劇增加。存儲(chǔ)器作為計(jì)算機(jī)系統(tǒng)的重要組成局部，雖然其容量一直在不斷的擴(kuò)大，價(jià)格已相當(dāng)廉價(jià)，但主存容量仍然是計(jì)算機(jī)硬件資源中最關(guān)鍵而又最緊張的“瓶頸〞資源，仍然滿(mǎn)足不了現(xiàn)代化軟件開(kāi)展的需要。4.0準(zhǔn)備知識(shí)近年來(lái)，微電子技術(shù)及大規(guī)模集成電路取得了長(zhǎng)足2因此，存儲(chǔ)器仍然是計(jì)算機(jī)系統(tǒng)中珍貴且緊俏的資源。它們?nèi)绾魏侠矶行У厥褂盟?，在很大程度上反映了OS的性能，并直接影響到整個(gè)計(jì)算機(jī)系統(tǒng)性能的發(fā)揮。所以，存儲(chǔ)器管理仍是目前人們研究OS的中心問(wèn)題之一，對(duì)主存的管理和有效使用仍然是今天OS十分重要的內(nèi)容。許多OS之間最明顯的區(qū)別特征之一往往是所使用的存儲(chǔ)管理方法不同。如OS/360-MFT采用固定分區(qū)存儲(chǔ)管理技術(shù)，OS/360-MTV是采用可變分區(qū)存儲(chǔ)管理技術(shù)，OS/2，WindowsNT,是采用虛擬存儲(chǔ)管理技術(shù)。由于對(duì)外存的管理與對(duì)內(nèi)存的管理有許多相似之處，只是兩者用途不同，加之外存主要用來(lái)存儲(chǔ)文件，故對(duì)外存的管理放在文件管理一章中介紹，存儲(chǔ)器管理討論的對(duì)象是內(nèi)存。因此，存儲(chǔ)器仍然是計(jì)算機(jī)系統(tǒng)中珍貴且緊俏的資源。它們?nèi)绾魏?本章主要介紹各種實(shí)存儲(chǔ)分配和管理方案，虛擬存儲(chǔ)器的概念及實(shí)現(xiàn)不同虛擬存儲(chǔ)器的技術(shù)的討論。操作系統(tǒng)之所以有那么多種類(lèi)，甚至一種型號(hào)的計(jì)算機(jī)配置假設(shè)干種操作系統(tǒng)，其主要原因之一是為了適應(yīng)各種用途而采用了不同的存儲(chǔ)器管理策略。在介紹各種存儲(chǔ)器管理技術(shù)方案之前，首先指出存儲(chǔ)器管理的主要目的及其應(yīng)提供的主要功能，并說(shuō)明在存儲(chǔ)器管理中幾個(gè)十分重要的概念。例如：存儲(chǔ)器的層次、存儲(chǔ)分配、地址重定位等概念。本章主要介紹各種實(shí)存儲(chǔ)分配和管理方案，虛擬存儲(chǔ)器的概念及實(shí)4高速緩存主存外存cpu可訪n十k~幾百knM~幾百M(fèi)nGM~n十G(G=1km)高速緩存Cache：K字節(jié)、高速、昂貴、易變的內(nèi)存RAM：M字節(jié)、中速、中等價(jià)格、易變的磁盤(pán)：G或T字節(jié)、低速、價(jià)廉、不易變的

為能更多的存放并更快地處理用戶(hù)信息，目前許多計(jì)算機(jī)把存儲(chǔ)器分為三級(jí)。4.0.1存儲(chǔ)器的層次構(gòu)造高速緩存主存外存cpu可訪n十k~幾百knM~幾百M(fèi)5圖中的三級(jí)存儲(chǔ)器，從高速緩沖存儲(chǔ)器(簡(jiǎn)稱(chēng)緩存)到外部存儲(chǔ)器(以后簡(jiǎn)稱(chēng)外存)，其容量愈來(lái)愈大，而訪問(wèn)數(shù)據(jù)的速度那么愈來(lái)愈慢，價(jià)格也愈來(lái)愈廉價(jià)。如現(xiàn)在的緩存的最大傳輸速度為幾十分之一至幾百分之一ns，主存的傳輸速度幾ns級(jí)。用戶(hù)的程序在運(yùn)行時(shí)應(yīng)存放在主存中，以便處理機(jī)訪問(wèn)。其中直接存取要求內(nèi)存速度盡量快到與CPU取指速度相匹配，大到能裝下當(dāng)前運(yùn)行的程序與數(shù)據(jù)，否那么CPU執(zhí)行速度就會(huì)受到內(nèi)存速度和容量的影響而得不到充分發(fā)揮。但是由于主存容量和速度有限。所以把那些不馬上使用的程序、數(shù)據(jù)放在外部存儲(chǔ)器(又稱(chēng)輔存)中。當(dāng)用到時(shí)再把它們讀入主存。由操作系統(tǒng)協(xié)調(diào)這些存儲(chǔ)器的使用4.0.1存儲(chǔ)器的層次構(gòu)造圖中的三級(jí)存儲(chǔ)器，從高速緩沖存儲(chǔ)器(簡(jiǎn)稱(chēng)緩存)到外部存儲(chǔ)器6為了便于對(duì)主存儲(chǔ)器進(jìn)展有效的管理，我們把存儲(chǔ)器分成假設(shè)干個(gè)區(qū)域。即使在最簡(jiǎn)單的單用戶(hù)系統(tǒng)中，至少也要把它分成兩個(gè)區(qū)域：在一個(gè)存儲(chǔ)區(qū)域內(nèi)存放系統(tǒng)軟件，如操作系統(tǒng)本身；而另一個(gè)存儲(chǔ)區(qū)域那么用于安置用戶(hù)作業(yè)。顯然，在多用戶(hù)系統(tǒng)中，為了提高系統(tǒng)的利用率，需要將存儲(chǔ)器劃分成更多的區(qū)域，以便同時(shí)存放多個(gè)用戶(hù)作業(yè)。這就引起了存儲(chǔ)器分配問(wèn)題及隨之產(chǎn)生的其它問(wèn)題。4.0.2存儲(chǔ)器管理的目的和功能為了便于對(duì)主存儲(chǔ)器進(jìn)展有效的管理，我們把存儲(chǔ)7存儲(chǔ)器管理的主要目的和功能如下：1.主存儲(chǔ)器的分配和管理：按用戶(hù)要求把適當(dāng)?shù)拇鎯?chǔ)空間分配給相應(yīng)的作業(yè)。一個(gè)有效的存儲(chǔ)分配機(jī)制，應(yīng)在用戶(hù)請(qǐng)求時(shí)能作出快速的響應(yīng)，分配相應(yīng)的存儲(chǔ)空間；在用戶(hù)不再使用它時(shí)，應(yīng)立即回收，以供其他用戶(hù)使用。為此，這個(gè)存儲(chǔ)分配機(jī)制應(yīng)具有如下功能〔3個(gè)〕：(1)記住每個(gè)存儲(chǔ)區(qū)域的狀態(tài)：哪些是已分配的，哪些是可以用作分配的。(2)實(shí)施分配：在系統(tǒng)程序或用戶(hù)提出申請(qǐng)時(shí)，按所需的量給予分配；修改相應(yīng)的分配記錄表。(3)承受系統(tǒng)或用戶(hù)釋放的存儲(chǔ)區(qū)域：并相應(yīng)地修改分配記錄表。4.0.2存儲(chǔ)器管理的目的和功能存儲(chǔ)器管理的主要目的和功能如下：4.0.2存儲(chǔ)器管理的82.提高主存儲(chǔ)器的利用率：使多道程序能動(dòng)態(tài)地共享主存，最好能共享主存中的信息。3.“擴(kuò)大〞主存容量：這是借助于提供虛擬存儲(chǔ)器或其它自動(dòng)覆蓋技術(shù)來(lái)到達(dá)的。即為用戶(hù)提供比主存的存儲(chǔ)空間還大的地址空間，之后，用戶(hù)可以想象把他的程序或數(shù)據(jù)裝入到這樣的地址空間內(nèi)。4.存儲(chǔ)保護(hù)：確保各道用戶(hù)作業(yè)都在所分配的存儲(chǔ)區(qū)內(nèi)操作，互不干擾。即要防止一道作業(yè)由于發(fā)生錯(cuò)誤而損害其它作業(yè)，特別需要防止破壞其中的系統(tǒng)程序。這個(gè)問(wèn)題不能用特權(quán)指令來(lái)加以解決。而必須由硬件提供保護(hù)功能，并由軟件配合實(shí)現(xiàn)。4.0.2存儲(chǔ)器管理的目的和功能2.提高主存儲(chǔ)器的利用率：使多道程序能動(dòng)態(tài)地共享主存，最好能9所謂存儲(chǔ)分配，主要是討論和解決多道作業(yè)之間共享主存的存儲(chǔ)空間問(wèn)題。前面已講到現(xiàn)代計(jì)算機(jī)系統(tǒng)都采用多級(jí)存儲(chǔ)體系構(gòu)造。因此，存儲(chǔ)分配所要解決的問(wèn)題是：要確定什么時(shí)候，以什么方式，或是把一個(gè)作業(yè)的全部信息還是把作業(yè)運(yùn)行時(shí)首先需要的信息分配到主存中，并使這些問(wèn)題對(duì)用戶(hù)來(lái)說(shuō)盡可能是“透明〞的。解決存儲(chǔ)分配問(wèn)題有三種方式：1.直接指定方式：程序員在編程序時(shí)，或編譯程序(匯編程序)對(duì)源程序進(jìn)展編譯(匯編)時(shí)，所用的是實(shí)際存儲(chǔ)地址。例如，在多道程序環(huán)境下，應(yīng)保證各作業(yè)所用的地址互不重疊。4.0.3存儲(chǔ)分配的三種方式所謂存儲(chǔ)分配，主要是討論和解決多道作業(yè)之間共10

顯然，采用直接指定方式分配的前提是：存儲(chǔ)器的可用容量(空間)已經(jīng)給定或可以指定，這對(duì)單用戶(hù)計(jì)算機(jī)系統(tǒng)是不成問(wèn)題的。在多道程序開(kāi)展的初期，通常把存儲(chǔ)空間劃分成假設(shè)干個(gè)固定的不同大小分區(qū)，并對(duì)不同的作業(yè)指定相應(yīng)的分區(qū)。因此，對(duì)算題人員或?qū)幾g程序而言，存儲(chǔ)器的可用空間是可知的。這種分配方式的實(shí)質(zhì)是：由算題人員在編程序時(shí)，或由編譯程序編譯源程序時(shí)，對(duì)一個(gè)作業(yè)的所有信息確定了在主存存儲(chǔ)空間中的位置。因此，這種直接指定方式的存儲(chǔ)分配方案，不僅用戶(hù)感到不便，而且存儲(chǔ)空間的利用也不那么有效?！踩秉c(diǎn)〕4.0.3存儲(chǔ)分配的三種方式顯然，采用直接指定方式分配的前提112.靜態(tài)分配(StaticAllocation)采用這種靜態(tài)存儲(chǔ)分配方案，用戶(hù)在編程時(shí)，或由編譯程序產(chǎn)生的目的程序，均可從其地址空間的零地址開(kāi)場(chǎng)；它們是當(dāng)裝配程序?qū)ζ溥M(jìn)展連接裝入時(shí)才確定它們?cè)谥鞔嬷械南鄳?yīng)位置，從而生成可執(zhí)行程序。也就是說(shuō)，存儲(chǔ)分配是在裝入時(shí)實(shí)現(xiàn)的。這種靜態(tài)存儲(chǔ)分配方式的特點(diǎn)是：(1)在一個(gè)作業(yè)裝入時(shí)必須分配其要求的全部存儲(chǔ)量；(2)如果沒(méi)有足夠的存儲(chǔ)空間，就不能裝入該作業(yè)；(3)一旦一個(gè)作業(yè)進(jìn)入內(nèi)存后，在其退出系統(tǒng)之前，它一直占用著分配給它的全部存儲(chǔ)空間；(4)在作業(yè)的整個(gè)運(yùn)行過(guò)程中不能在內(nèi)存中“搬家〞、也不能再申請(qǐng)存儲(chǔ)量。這種靜態(tài)分配策略的存儲(chǔ)管理很簡(jiǎn)單，但在多道程序系統(tǒng)中不能有效地共享存儲(chǔ)器資源。4.0.3存儲(chǔ)分配的三種方式2.靜態(tài)分配(StaticAllocat123.動(dòng)態(tài)分配(DynamicAllocation)：動(dòng)態(tài)分配是一種更加有效的使用主存儲(chǔ)器的方法。這種動(dòng)態(tài)存儲(chǔ)分配方式的特點(diǎn)是：(1)作業(yè)在存儲(chǔ)空間中的位置，也是在其裝入時(shí)確定的；(2)在其執(zhí)行過(guò)程中可根據(jù)需要申請(qǐng)附加的存儲(chǔ)空間；(3)一個(gè)作業(yè)已占用的局部存儲(chǔ)區(qū)域不再需要時(shí)，可以要求歸還給系統(tǒng)。即：這種存儲(chǔ)分配機(jī)制能承受不可預(yù)測(cè)的分配和釋放存儲(chǔ)區(qū)域的請(qǐng)求，實(shí)現(xiàn)個(gè)別存儲(chǔ)區(qū)域的分配和回收；(4)存儲(chǔ)區(qū)域的大小是可變的；要求這個(gè)區(qū)域必須是單個(gè)連續(xù)的存儲(chǔ)區(qū)域，以便和提出存儲(chǔ)請(qǐng)求之作業(yè)的虛擬地址空間相對(duì)應(yīng)。(5)它允許作業(yè)在內(nèi)存中“搬家〞。目前，絕大多數(shù)計(jì)算機(jī)系統(tǒng)都采用靜態(tài)或動(dòng)態(tài)存儲(chǔ)分配策略，所以，在本章只討論這兩種存儲(chǔ)分配的實(shí)現(xiàn)技術(shù)，重點(diǎn)放在各種動(dòng)態(tài)存儲(chǔ)分配技術(shù)的實(shí)現(xiàn)上。4.0.3存儲(chǔ)分配的三種方式3.動(dòng)態(tài)分配(DynamicAlloca13我們首先要分清幾個(gè)不同概念：1.地址空間：是指由目標(biāo)程序所限定的地址范圍。即：地址空間僅僅是指程序用來(lái)訪問(wèn)信息所用的一系列地址單元的集合。這些單元的編號(hào)稱(chēng)為邏輯地址。一個(gè)用高級(jí)語(yǔ)言編制的源程序，我們說(shuō)它存在于由程序員建立的符號(hào)名字空間〔簡(jiǎn)稱(chēng)名空間〕。通常，編譯程序在對(duì)一個(gè)源程序編譯時(shí)，總是從零號(hào)單元開(kāi)場(chǎng)為其分配地址，其它所有地址都是從這個(gè)開(kāi)場(chǎng)地址順序排下來(lái)的，因此，地址空間中的所有地址都是相對(duì)于起始地址的，因而稱(chēng)它們?yōu)橄鄬?duì)地址，所以，邏輯地址也就是相對(duì)地址。2.存儲(chǔ)空間：所謂存儲(chǔ)空間是指主存中一系列存儲(chǔ)信息的物理單元的集合。這些單元的編號(hào)稱(chēng)物理地址或絕對(duì)地址。因此，存儲(chǔ)空間的大小是由主存的實(shí)際容量決定的。4.0.4幾個(gè)根本概念我們首先要分清幾個(gè)不同概念：4.0.414符號(hào)指令

數(shù)據(jù)說(shuō)明

I/O說(shuō)明0

目標(biāo)程序x

0

A

作業(yè)JA+x

512K

名空間地址空間(作業(yè)J的源程序)存儲(chǔ)空間裝入編譯簡(jiǎn)言之，地址空間是邏輯地址的集合；存儲(chǔ)空間是物理地址的集合。一個(gè)是“虛〞的概念，一個(gè)是“實(shí)〞的物體。一個(gè)編譯好的目標(biāo)程序存在于它自己的地址空間中，當(dāng)要它在計(jì)算機(jī)上運(yùn)行時(shí)，才把它裝入存儲(chǔ)空間，上圖說(shuō)明一個(gè)作業(yè)在編譯、裝入前后存在于不同空間的情況。關(guān)于三個(gè)空間的定義可以通過(guò)下面的圖示來(lái)理解。4.0.4幾個(gè)根本概念名空間地址空間(作業(yè)J的源程序)存儲(chǔ)空間裝入編譯154.1程序的裝入和鏈接在多道程序環(huán)境下，程序要運(yùn)行必須為之創(chuàng)立進(jìn)程，而創(chuàng)立進(jìn)程的第一件事情就是要把用戶(hù)編寫(xiě)好的源程序和數(shù)據(jù)裝入內(nèi)存。如何將一個(gè)用戶(hù)源程序變?yōu)橐粋€(gè)可在內(nèi)存中執(zhí)行的程序，通常要經(jīng)過(guò)以下幾步：⑴編譯(Compiler)：一般說(shuō)來(lái)，源程序模塊是用高級(jí)語(yǔ)言(如pascal、fortran、cobol)或匯編語(yǔ)言寫(xiě)的一組程序語(yǔ)句。計(jì)算機(jī)不能直接執(zhí)行源語(yǔ)句，它們要首先被編譯程序或解釋程序翻譯成機(jī)器級(jí)代碼。編譯程序承受完整的源一級(jí)的程序，并以類(lèi)似于成批的方式生成完整的目標(biāo)一級(jí)的模塊。4.1程序的裝入和鏈接在多道程序環(huán)境下，16⑵鏈接(Linker)：目標(biāo)模塊是純二進(jìn)制的機(jī)器級(jí)代碼。計(jì)算機(jī)可以執(zhí)行目標(biāo)級(jí)代碼，但是典型的目標(biāo)模塊是不完備的，它包含對(duì)其它目標(biāo)模塊〔諸如存取方法或子例程〕的引用。因此，目標(biāo)模塊通常是不能裝入計(jì)算機(jī)并執(zhí)行的。所以，一些目標(biāo)模塊必須首先鏈接成一個(gè)裝入模塊，它是能被裝入并執(zhí)行的完備的機(jī)器級(jí)程序。這個(gè)使目標(biāo)模塊鏈接成裝入模塊的過(guò)程，在IBM系統(tǒng)中是由稱(chēng)為鏈接編輯程序的系統(tǒng)程序?qū)崿F(xiàn)的。⑶裝入(Loader)：由裝入程序?qū)⒀b入模塊裝入內(nèi)存并執(zhí)行⑵鏈接(Linker)：目標(biāo)模塊是純二進(jìn)制17圖4-1對(duì)用戶(hù)程序的處理步驟源程序編譯程序目標(biāo)模塊鏈接程序裝入模塊應(yīng)用程序系統(tǒng)源語(yǔ)句庫(kù)私有源語(yǔ)句庫(kù)私有目標(biāo)庫(kù)系統(tǒng)目標(biāo)庫(kù)裝入程序裝入內(nèi)存圖4-1對(duì)用戶(hù)程序的處理步驟源編譯程序目標(biāo)鏈接程序裝入184.1.1程序的裝入根據(jù)存儲(chǔ)空間的分配方式，將一個(gè)裝入模塊裝入內(nèi)存時(shí)，可采用三種方式：一、絕對(duì)裝入方式(AbsoluteLoadingMode)：程序員在編程序時(shí)，或編譯程序〔匯編程序〕對(duì)源程序進(jìn)展編譯〔匯編〕時(shí)，如果知道程序?qū)Ⅰv留在內(nèi)存的具體位置，那么將產(chǎn)生的符號(hào)地址程序JUMPiLOADjDATAijab程序JUMP1424LOAD2224DATA14242224絕對(duì)地址1024是實(shí)際存儲(chǔ)地址〔絕對(duì)地址〕。但在由程序員直接給出絕對(duì)地址時(shí)，不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號(hào)地址，然后在編譯或匯編時(shí)，再將這些符號(hào)地址轉(zhuǎn)換為絕對(duì)地址。如右圖所示：4.1.1程序的裝入根據(jù)存儲(chǔ)空間的分配方19二、可重定位裝入方式(RelocationLoadingMode)：在多道程序環(huán)境下，由于事先并不知曉目標(biāo)程序在內(nèi)存的具體位置，為了實(shí)現(xiàn)靜態(tài)或動(dòng)態(tài)存儲(chǔ)分配策略，需要采用下述兩個(gè)技術(shù)手段：〔1〕把邏輯地址和物理地址分開(kāi)；〔2〕對(duì)邏輯地址實(shí)施地址重定位。

什么叫重定位：在一般情況下，一個(gè)作業(yè)在裝入時(shí)分配到的存儲(chǔ)空間和它的地址空間是不一致的。因此，作業(yè)在CPU上運(yùn)行時(shí)，其所要訪問(wèn)的指令和數(shù)據(jù)的實(shí)際地址與地址空間中的相對(duì)地址是不同的。如右圖所示：地址空間0

100Load1,500

500Y

1K存儲(chǔ)空間

01K1124Load1,5001524Y

2K

512K裝入二、可重定位裝入方式(RelocationLoading20顯然，如果在作業(yè)裝入時(shí)或在其執(zhí)行時(shí)，不對(duì)有關(guān)的地址局部加以相應(yīng)的修改，那么將導(dǎo)致錯(cuò)誤的結(jié)果。這種由于把一個(gè)作業(yè)裝入到與其地址空間不一致的存儲(chǔ)空間所引起的對(duì)地址局部調(diào)整的過(guò)程，稱(chēng)為地址重定位。實(shí)質(zhì)上，地址重定位是一個(gè)地址變換過(guò)程，是把作業(yè)地址空間中使用的邏輯地址變換成內(nèi)存空間中的物理地址的過(guò)程。這種地址變換就是前面所說(shuō)的地址映射。根據(jù)對(duì)地址變換進(jìn)展的時(shí)間及采用技術(shù)手段的不同，把重定位分為靜態(tài)重定位和動(dòng)態(tài)重定位兩類(lèi)?？芍囟ㄎ谎b入方式采用的的是靜態(tài)重定位技術(shù)。顯然，如果在作業(yè)裝入時(shí)或在其執(zhí)行時(shí)，不對(duì)有關(guān)的地址局21靜態(tài)重定位：是指作業(yè)在裝入過(guò)程中由裝配程序進(jìn)展的地址變換方式。它要求程序本身是可重定位的，即要求編譯程序?qū)ψ鳂I(yè)的目標(biāo)程序中那些要修改的地址局部給出相應(yīng)的標(biāo)識(shí)。這種重定位之所以稱(chēng)為靜態(tài)的，是因?yàn)榈刂纷儞Q只在作業(yè)執(zhí)行前集中一次完成的。主要優(yōu)點(diǎn)：無(wú)需增加硬件地址變換機(jī)構(gòu)，因而可在一般計(jì)算機(jī)上實(shí)現(xiàn)。主要缺點(diǎn)：①要求給每個(gè)作業(yè)分配一個(gè)連續(xù)的存儲(chǔ)區(qū)域，且在其整個(gè)執(zhí)行期間必須限定在這個(gè)區(qū)域內(nèi)。也就是說(shuō)，在作業(yè)執(zhí)行期間不能把它移動(dòng)，因而也就不能實(shí)現(xiàn)重新分配主存。這對(duì)提高主存的利用率是不利的。②用戶(hù)必須事先確定所需的存儲(chǔ)量，假設(shè)所需的存儲(chǔ)量超過(guò)可用存儲(chǔ)空間時(shí)，用戶(hù)必須考慮覆蓋構(gòu)造。③用戶(hù)之間難以共享主存中的同一程序。假設(shè)要共享一程序，那么每個(gè)用戶(hù)應(yīng)各自使用一個(gè)分開(kāi)的副本。靜態(tài)重定位：是指作業(yè)在裝入過(guò)程中由裝配程序進(jìn)22例：0LOAD1,25003651000作業(yè)地址空間25005000LOAD1,2500365

內(nèi)存空間011000125001500010000例：01000作業(yè)地址空間25005000內(nèi)存空間01123三、動(dòng)態(tài)運(yùn)行時(shí)裝入方式(DenamleRun-timeLoading)：采用的的是動(dòng)態(tài)重定位技術(shù)。動(dòng)態(tài)重定位：是指在作業(yè)執(zhí)行過(guò)程中，當(dāng)訪問(wèn)指令或數(shù)據(jù)時(shí)，由附加的地址變換機(jī)構(gòu)進(jìn)展的地址變換方式。動(dòng)態(tài)重定位是靠硬件地址變換機(jī)構(gòu)實(shí)現(xiàn)的。最簡(jiǎn)單的方法是利用一個(gè)重定位存放器(RR)。該存放器的值是由進(jìn)程調(diào)度程序(或另派程序)根據(jù)作業(yè)分配到的存儲(chǔ)空間起始地址來(lái)設(shè)定的。在具有這種地址變換機(jī)構(gòu)的計(jì)算機(jī)系統(tǒng)中，當(dāng)執(zhí)行作業(yè)時(shí)，不是根據(jù)CPU給出的有效地址去訪問(wèn)主存，而是將有效地址與重定位存放器中的內(nèi)容相加后得到的地址作為訪問(wèn)主存的地址。以以下圖給出了地址變換過(guò)程。三、動(dòng)態(tài)運(yùn)行時(shí)裝入方式(DenamleRun-timeL2403456......LOADA200......0100200300.........LOADA2003456邏輯地址空間110012001300物理地址空間VR200+1000BR由于這種地址變換是在作業(yè)執(zhí)行期間隨著每條指令的數(shù)據(jù)自動(dòng)地、連續(xù)地進(jìn)展，所以稱(chēng)之為動(dòng)態(tài)重定位。03456LOADA20025采用動(dòng)態(tài)重定位技術(shù)后，程序中所有指令和數(shù)據(jù)的實(shí)際地址是在運(yùn)行過(guò)程中最后訪問(wèn)的時(shí)刻確定的。因此，計(jì)算機(jī)系統(tǒng)采用了動(dòng)態(tài)存儲(chǔ)分配策略。也就是說(shuō)，在作業(yè)運(yùn)行過(guò)程中臨時(shí)申請(qǐng)分配附加的存儲(chǔ)區(qū)域或釋放已占用的局部存儲(chǔ)空間是允許的。主要優(yōu)點(diǎn)：①主存的使用更加靈活有效。這里，一個(gè)用戶(hù)的作業(yè)不一定要分配在一個(gè)連續(xù)的存儲(chǔ)區(qū)，因而可以使用較小的分配單位。而且，在作業(yè)開(kāi)場(chǎng)之前也不一定把它的地址空間全部裝入主存，而可以在作業(yè)執(zhí)行期間響應(yīng)請(qǐng)求動(dòng)態(tài)地進(jìn)展分配。②幾個(gè)作業(yè)共享一程序段的單個(gè)副本比較容易。③有可能向用戶(hù)提供一個(gè)比主存的存儲(chǔ)空間大得多的地址空間。因而無(wú)需用戶(hù)來(lái)考慮覆蓋構(gòu)造，而由系統(tǒng)來(lái)負(fù)責(zé)全部的存儲(chǔ)管理。主要缺點(diǎn)：①需要附加硬件支持；②實(shí)現(xiàn)存儲(chǔ)器管理的軟件比較復(fù)雜。采用動(dòng)態(tài)重定位技術(shù)后，程序中所有指令和數(shù)據(jù)的264.1.2程序的鏈接鏈接程序的功能，是將經(jīng)過(guò)編譯或匯編后所得到的一組目標(biāo)模塊以及它們所需要的庫(kù)函數(shù)，裝配成一個(gè)完整的裝入模塊。實(shí)現(xiàn)鏈接的方法有三種：一、靜態(tài)鏈接：(StaticLinking)

事先將幾個(gè)目標(biāo)鏈接裝配成一個(gè)裝入模塊，以后不再拆開(kāi)的鏈接方式，稱(chēng)為靜態(tài)鏈接方式。如右圖：模塊ACALLB;Return;0L-1模塊BCALLC;Return;0M-1模塊C

Return;0N-10L-1模塊AJSR“L”Return;LL+M-1模塊BJSR“L+M”;Return;模塊C

Return;L+ML+M+N-14.1.2程序的鏈接鏈接程序的功能，是27說(shuō)明：將幾個(gè)目標(biāo)鏈接裝配成一個(gè)裝入模塊時(shí)，需解決以下兩個(gè)問(wèn)題：1.將相對(duì)地址進(jìn)展修改。即將除第一個(gè)模塊外的相對(duì)地址修改成裝入模塊中的相應(yīng)的相對(duì)地址。2.變換外部調(diào)用符號(hào)。即將每個(gè)模塊中所用的外部調(diào)用符號(hào)，都變換為相對(duì)地址。這種先進(jìn)展鏈接所形成的一個(gè)完整的裝入模塊，又稱(chēng)為可執(zhí)行文件。說(shuō)明：將幾個(gè)目標(biāo)鏈接裝配成一個(gè)裝入模塊時(shí)，需28二、裝入時(shí)動(dòng)態(tài)鏈接(Load-TimeDynamicLinking)用戶(hù)源程序經(jīng)編譯后所得到的目標(biāo)模塊，是在裝入內(nèi)存時(shí)，邊裝入邊鏈接的。即在裝入一個(gè)目標(biāo)模塊時(shí)，假設(shè)發(fā)生一個(gè)外部模塊調(diào)用，將引起裝入程序去找出相應(yīng)的外部目標(biāo)模塊，并將之裝入內(nèi)存。裝入時(shí)動(dòng)態(tài)鏈接有如下優(yōu)點(diǎn)：1.便于軟件版本的修改和更新。只需修改各個(gè)目標(biāo)模塊，不必將裝入模塊拆開(kāi)，非常方便。2.便于實(shí)現(xiàn)目標(biāo)模塊共享。即可以將一個(gè)目標(biāo)模塊鏈接到幾個(gè)應(yīng)用模塊中，從而實(shí)現(xiàn)多個(gè)應(yīng)用程序?qū)υ撃K的共享。二、裝入時(shí)動(dòng)態(tài)鏈接(Load-TimeDynamicLi29SEQAMSUBR1MAIN系統(tǒng)目標(biāo)庫(kù)當(dāng)前生成的目標(biāo)庫(kù)私有目標(biāo)庫(kù)MAIN

…...callSEQAM…...callSURB1…...

查找引用讀入查找引用裝入模塊SEQAM

……RETURNSURB1

……RETURNSEQAMSUBR1MAIN系統(tǒng)目標(biāo)庫(kù)當(dāng)前生成的目標(biāo)30三、運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-TimeDynamicLinking)采用裝入時(shí)動(dòng)態(tài)鏈接方式，雖然可將一個(gè)裝入模塊裝入到內(nèi)存的任何地方，但裝入模塊的構(gòu)造是靜態(tài)的，表現(xiàn)在：1.進(jìn)程〔程序〕在整個(gè)執(zhí)行期間，裝入模塊是不改變的；2.每次運(yùn)行時(shí)的裝入模塊是一樣的。并且事先無(wú)法知道本次要運(yùn)行哪些模塊，只能將所有可能要運(yùn)行的模塊在裝入時(shí)全部鏈接在一起，而實(shí)際上往往有些目標(biāo)模塊根本不會(huì)運(yùn)行。采用運(yùn)行時(shí)動(dòng)態(tài)鏈接可將某些目標(biāo)模塊的鏈接推遲到執(zhí)行時(shí)才進(jìn)展，即在執(zhí)行過(guò)程中，假設(shè)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，由OS去找到該模塊，將它裝入內(nèi)存，并鏈接到調(diào)用模塊上。三、運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-TimeDynamicLin314.2連續(xù)分配方式連續(xù)分配是指為一個(gè)用戶(hù)程序分配一個(gè)連續(xù)的內(nèi)存空間。有兩種方式：1.單一用戶(hù)〔連續(xù)區(qū)〕存儲(chǔ)管理：?jiǎn)斡脩?hù)系統(tǒng)在一段時(shí)間內(nèi)，只有一個(gè)進(jìn)程在內(nèi)存，故內(nèi)存分配管理十分簡(jiǎn)單，內(nèi)存利用率低。內(nèi)存分為兩個(gè)區(qū)域，一個(gè)供操作系統(tǒng)使用，一個(gè)供用戶(hù)使用.2.分區(qū)式分配方式：系統(tǒng)把內(nèi)存用戶(hù)區(qū)劃分為假設(shè)干分區(qū)，分區(qū)大小可以相等，也可以不等。一個(gè)進(jìn)程占據(jù)一個(gè)分區(qū)。這是早期用于多道程序的一種較簡(jiǎn)單的存儲(chǔ)管理方式。它又可以分為：⑴固定分區(qū)⑵動(dòng)態(tài)〔可變〕分區(qū)4.2連續(xù)分配方式連續(xù)分配是指為一個(gè)用324.2.1單一連續(xù)分配這是最簡(jiǎn)單的存儲(chǔ)器管理，因?yàn)椴僮飨到y(tǒng)只為一個(gè)用戶(hù)效勞。它將內(nèi)存分為兩個(gè)區(qū)域，即系統(tǒng)區(qū)與用戶(hù)區(qū)。如以以下圖所示：駐留的OS既可放在存儲(chǔ)器的低址局部，如圖(a)；也可放在存儲(chǔ)器的高址局部，如圖(b)；甚至可以放在存儲(chǔ)器的兩端，如圖(c)。系統(tǒng)區(qū)

駐留OS

用戶(hù)區(qū)

用戶(hù)程序（未用部分）

0512K(a)系統(tǒng)區(qū)

系統(tǒng)中斷向量等用戶(hù)區(qū)用戶(hù)程序

（未用部分）系統(tǒng)區(qū)駐留OS本身

0

512512K(b)

0

15K490K512K系統(tǒng)區(qū)

駐留OS(1)用戶(hù)區(qū)用戶(hù)程序（未用部分）系統(tǒng)區(qū)駐留OS(2)(c)4.2.1單一連續(xù)分配這是最簡(jiǎn)單的存儲(chǔ)器33存儲(chǔ)管理:連續(xù)分配000020KB100KB256KBOS用戶(hù)程序需80KB存儲(chǔ)空間空閑區(qū)一次只能裝入一個(gè)作業(yè)存儲(chǔ)管理:連續(xù)分配0000OS用戶(hù)程序空閑區(qū)一次只能裝入一個(gè)34單一連續(xù)分配〔1〕系統(tǒng)總是把整個(gè)用戶(hù)區(qū)分配給一個(gè)用戶(hù)使用?！?〕實(shí)際上，內(nèi)存用戶(hù)區(qū)又被分為“使用區(qū)〞和“空閑區(qū)〞?？臻e區(qū)被成為〞內(nèi)存碎片“?！?〕由于任何時(shí)刻內(nèi)存儲(chǔ)器的用戶(hù)區(qū)中只有一個(gè)作業(yè)運(yùn)行，因此這種系統(tǒng)只適用于單用戶(hù)的情況。單一連續(xù)分配〔1〕系統(tǒng)總是把整個(gè)用戶(hù)區(qū)分配給一個(gè)用戶(hù)使用。35單一連續(xù)分區(qū)存儲(chǔ)管理有如下缺點(diǎn)：〔1〕由于每次只能有一個(gè)作業(yè)進(jìn)入內(nèi)存，故它不適用于多道程序設(shè)計(jì)，整個(gè)系統(tǒng)的工作效率不高，資源利用率低下?！?〕只要作業(yè)比用戶(hù)區(qū)小，那么在用戶(hù)區(qū)里就會(huì)形成碎片，造成內(nèi)存儲(chǔ)器資源的浪費(fèi)。如果用戶(hù)作業(yè)很小，那么這種浪費(fèi)是巨大的?！?〕假設(shè)用戶(hù)作業(yè)的相對(duì)地址空間比用戶(hù)區(qū)大，那么該作業(yè)就無(wú)法運(yùn)行。即大作業(yè)無(wú)法在小內(nèi)存上運(yùn)行。單一連續(xù)分區(qū)存儲(chǔ)管理有如下缺點(diǎn)：36存儲(chǔ)分配只有在實(shí)施了存儲(chǔ)保護(hù)后都有意義。單用戶(hù)系統(tǒng)中，存儲(chǔ)保護(hù)只要求對(duì)操作系統(tǒng)區(qū)域加以保護(hù)。通常，要實(shí)施存儲(chǔ)保護(hù)必須配置相應(yīng)的硬件機(jī)構(gòu)才可行。但單用戶(hù)系統(tǒng)中并不配置這種硬件機(jī)構(gòu)，其原因是這些單用戶(hù)的存儲(chǔ)保護(hù)問(wèn)題并不嚴(yán)重，即使操作系統(tǒng)遭到破壞，受影響的只是單個(gè)用戶(hù)所做的工作，而操作系統(tǒng)可以通過(guò)系統(tǒng)再啟動(dòng)重新把操作系統(tǒng)裝入主存。所以，最多只是用戶(hù)使用上的不便，卻使硬件本錢(qián)得到降低。在大多數(shù)較新的系統(tǒng)構(gòu)造中，存儲(chǔ)保護(hù)是作為綜合的地址變換機(jī)構(gòu)的一局部而獲得的。但在一些較老的系統(tǒng)中，一般采用簡(jiǎn)單的硬件以提供有限的保護(hù)。下面介紹其中的三種。存儲(chǔ)分配只有在實(shí)施了存儲(chǔ)保護(hù)后都有意義。371.自動(dòng)地址修改：例：設(shè)存儲(chǔ)器地址空間為12K，操作系統(tǒng)占4K。這樣系統(tǒng)可以提供給用戶(hù)8K(213)的地址空間。

b1b130

用戶(hù)地址+(4K)得實(shí)際要訪問(wèn)的存儲(chǔ)地址

b1b130

用戶(hù)地址b1b13

要訪問(wèn)的存儲(chǔ)地址整除8K假設(shè)OS占高址端的4K，那么：假設(shè)OS占低址端的4K，那么：從而實(shí)現(xiàn)了對(duì)OS的保護(hù)。1.自動(dòng)地址修改：b1382.0頁(yè)，1頁(yè)尋址：是自動(dòng)地址修改的一種變異。假定操作系統(tǒng)與用戶(hù)各占存儲(chǔ)器的一半，它們的區(qū)分可以通過(guò)對(duì)每個(gè)用戶(hù)生成的地址左端拼接上一位1來(lái)實(shí)現(xiàn)。如以以下圖動(dòng)畫(huà)所示。用戶(hù)地址12.0頁(yè)，1頁(yè)尋址：用戶(hù)地址1393.界限存放器：上述兩種技術(shù)都要求預(yù)先確定用戶(hù)區(qū)與系統(tǒng)區(qū)的大小。這個(gè)條件可以通過(guò)使用一界限存放器或隔離存放器來(lái)消除。這兩個(gè)區(qū)域相對(duì)大小改變時(shí)，只要改變這個(gè)界限存放器的值即可。如以以下圖：系統(tǒng)區(qū)域

用戶(hù)區(qū)域

界限存放器顯然，此方法增加了系統(tǒng)開(kāi)銷(xiāo)，因?yàn)橛脩?hù)每次存儲(chǔ)訪問(wèn)都要作一次比較，而不是象前面那樣直接快速的地址修改。3.界限存放器：系統(tǒng)區(qū)域用戶(hù)區(qū)404.2.2固定分區(qū)分配實(shí)現(xiàn)多用戶(hù)系統(tǒng)的存儲(chǔ)器管理，一個(gè)最早的想法是：當(dāng)系統(tǒng)初始化時(shí)，把存儲(chǔ)空間劃分成假設(shè)干個(gè)任意大小的區(qū)域；然后，把這些區(qū)域分配給每個(gè)用戶(hù)作業(yè)。由于這些存儲(chǔ)區(qū)域是在系統(tǒng)啟動(dòng)時(shí)劃定的，在用戶(hù)作業(yè)裝入及運(yùn)行過(guò)程中，其區(qū)域的大小和邊界是不能改變的。所以，稱(chēng)這種存儲(chǔ)器的劃分方式為固定式分區(qū)或靜態(tài)存儲(chǔ)區(qū)域定義。固定式分區(qū)的劃分方法有兩種：(1)分區(qū)大小相等(2)分區(qū)大小不等4.2.2固定分區(qū)分配實(shí)現(xiàn)多用戶(hù)系統(tǒng)41存儲(chǔ)管理:連續(xù)分配000020KB28KB44KB76KB140KB256KBOS分區(qū)大小不等分區(qū)大小相等000020KB40KB60KB80KB100KB120KB...256KBOS16KB8KB作業(yè)1需14KB32KB64KB作業(yè)2需60KB116KB存儲(chǔ)管理:連續(xù)分配0000OS分區(qū)大小不等分區(qū)大小相等00042為了實(shí)現(xiàn)這種固定分區(qū)的分配，系統(tǒng)需要建立一張分區(qū)說(shuō)明表，如右圖。這個(gè)分區(qū)說(shuō)明表指出可用于分配的分區(qū)數(shù)以及每個(gè)的大小、起始地址及狀態(tài)。分區(qū)號(hào)大小始址狀態(tài)

112K20K已分配232K32K已分配364K64K已分配4128K128K未分配（分區(qū)說(shuō)明表）在調(diào)度時(shí)作業(yè)時(shí)，由存儲(chǔ)管理根據(jù)所需量在分區(qū)說(shuō)明表中找出一個(gè)足夠大的未分配分區(qū)分配給它，然后用重定位裝配程序裝入之。如果找不到適宜的分區(qū)，那么通知作業(yè)調(diào)度模塊，從作業(yè)后備隊(duì)中另外選擇一個(gè)作業(yè)來(lái)裝入。為了實(shí)現(xiàn)這種固定分區(qū)的分配，系統(tǒng)需要建立一張432.多道固定分區(qū)管理(續(xù))存儲(chǔ)管理:連續(xù)分配000020KB28KB44KB76KB140KB256KBOS16KB8KB32KB64KB116KB需建立固定分區(qū)說(shuō)明表分區(qū)號(hào)起始地址長(zhǎng)度狀態(tài)作業(yè)名120KB8KB0228KB16KB0344KB32KB0476KB64KB05140KB116KB0作業(yè)J1需14KB1J11J2內(nèi)零頭(碎片)問(wèn)題作業(yè)J2需60KB作業(yè)J114KB作業(yè)J260KB作業(yè)J114KB作業(yè)J260KB物理內(nèi)存2.多道固定分區(qū)管理(續(xù))存儲(chǔ)管理:連續(xù)分配0000OS1644固定分區(qū)分配算法流程圖要求xK大小的分區(qū)取分區(qū)說(shuō)明表的第一項(xiàng)該分區(qū)空閑嗎？分區(qū)大小xK表完畢嗎？返回分區(qū)號(hào)狀態(tài)位置1無(wú)法分配取下一項(xiàng)NYYYNN固定分區(qū)分配算法流程圖要求xK大小的分區(qū)取分區(qū)說(shuō)明表的該分區(qū)45分區(qū)號(hào)大小始址狀態(tài)

112K20K已分配232K32K已分配364K64K已分配4128K128K未分配（分區(qū)說(shuō)明表）操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C

020K32K64K128K256K≈

≈存儲(chǔ)空間分配情況分區(qū)號(hào)大小始址狀態(tài)（分區(qū)說(shuō)明表）操作系統(tǒng)46采用這種技術(shù)，雖然可以使多個(gè)作業(yè)共享主存，但仍不能充分利用它。因?yàn)?，一個(gè)作業(yè)的大小，只有當(dāng)作業(yè)調(diào)度程序在分析進(jìn)程創(chuàng)立請(qǐng)求時(shí)才能確定；而分區(qū)的大小是在系統(tǒng)初啟時(shí)劃定的。由于作業(yè)的大小不可能剛好等于某個(gè)分區(qū)的大小，所以，在每個(gè)分配的分區(qū)中，通常都有一局部未被作業(yè)占用而浪費(fèi)掉。這種分配給用戶(hù)而未被利用的局部，稱(chēng)作存儲(chǔ)器的“內(nèi)零頭〞(InternaIFragmentation)。實(shí)際上，存儲(chǔ)區(qū)域的內(nèi)零頭主要取決于采用哪一種分配策略，常用的有首次適應(yīng)算法和最正確適應(yīng)算法。這些算法將在下一小節(jié)中介紹。固定分區(qū)方式存儲(chǔ)管理的優(yōu)點(diǎn)是分區(qū)方法特別簡(jiǎn)單，實(shí)現(xiàn)起來(lái)也很容易；缺點(diǎn)是存儲(chǔ)空間的利用率太低?，F(xiàn)在的操作系統(tǒng)幾乎不用它了。采用這種技術(shù)，雖然可以使多個(gè)作業(yè)共享主存，但474.2.3動(dòng)態(tài)分區(qū)分配為了減少存儲(chǔ)區(qū)域的內(nèi)零頭，進(jìn)一步提高主存的利用率，使存儲(chǔ)空間的劃分更加適應(yīng)不同的作業(yè)組合，人們?cè)O(shè)計(jì)了動(dòng)態(tài)〔可變〕式分區(qū)方案。所謂動(dòng)態(tài)式分區(qū)分配是指根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配連續(xù)的內(nèi)存空間。即分區(qū)的邊界可以移動(dòng)，分區(qū)的大小是可變的。動(dòng)態(tài)式分區(qū)又有兩種不同選擇，一種是分區(qū)的數(shù)目固定大小是可變的，而另一種那么允許分區(qū)的數(shù)目和大小都是可變的。為了說(shuō)明它們之間的重要差異，我們考慮一個(gè)具有256K字節(jié)存儲(chǔ)器的系統(tǒng)。4.2.3動(dòng)態(tài)分區(qū)分配為了減少存儲(chǔ)區(qū)域48第一種方案：假定系統(tǒng)初始化時(shí)規(guī)定把存儲(chǔ)空間劃分為8個(gè)分區(qū)。在以以下圖(a)中用問(wèn)號(hào)(?)來(lái)表示它們。在系統(tǒng)運(yùn)行一段時(shí)間后，已有192K存儲(chǔ)空間分配給7個(gè)作業(yè)，剩下64K還未分配，如以以下圖(b)所示?，F(xiàn)在，又有兩個(gè)作業(yè)P和Q準(zhǔn)備調(diào)入，它們每個(gè)需要32K存儲(chǔ)空間。顯然，我們有足夠的存儲(chǔ)空間。卻沒(méi)有足夠數(shù)的存儲(chǔ)區(qū)域(目前只有一個(gè)可用)。因此，只能允許一個(gè)作業(yè)(如：P)被調(diào)入，如以以下圖(c)所示。？？？？？？？？

0

256K(a)已分配的100K

(3個(gè)作業(yè)占用)未分配的64K已分配的92K(4個(gè)作業(yè)占用)

0

256K(b)已分配的100K

(3個(gè)作業(yè)占用)分配給P:32K

(浪費(fèi)掉32K)已分配的92K(4個(gè)作業(yè)占用)

0

256K(c)第一種方案：假定系統(tǒng)初始化時(shí)規(guī)定把存儲(chǔ)空間劃49第二種方案(分區(qū)數(shù)可變的分配方案)：。為了便于比較，把相應(yīng)情況的分配示于圖(a)中。最初，沒(méi)有建立任何分區(qū)，整個(gè)可用的存儲(chǔ)空間用一個(gè)問(wèn)號(hào)來(lái)表示；之后，發(fā)生上述所說(shuō)在系統(tǒng)運(yùn)行一段時(shí)間后，已有192K存儲(chǔ)空間分配給7個(gè)作業(yè)，剩下64K還未分配的情況，如圖(b)；現(xiàn)在，我們?cè)谑Ｏ碌?4K存儲(chǔ)空間中，可以創(chuàng)立兩個(gè)分區(qū)，分別裝入作業(yè)P和Q，如圖(c)。顯然，此方案比第一個(gè)方案更靈活，內(nèi)存利用率更高。已分配的100K

(3個(gè)作業(yè)占用)未分配的64K已分配的92K(4個(gè)作業(yè)占用)

0

256K(b)已分配的100K

(3個(gè)作業(yè)占用)分配給P:32K分配給Q:32K已分配的92K(4個(gè)作業(yè)占用)

0

256K(c)？

0

256K(a)第二種方案(分區(qū)數(shù)可變的分配方案)：。為了便503.多道可變分區(qū)管理(概念)存儲(chǔ)管理:連續(xù)分配內(nèi)存地址000020KB256KBOSJ1需14KBJ2需30KB空閑區(qū)已分配區(qū)J3需60KB區(qū)大小14KB30KB60KB132KBJ4需60KBJ5需20KBJ114KBJ230KBJ360KBJ460KBJ520KB10KB72KB外零頭(碎片)3.多道可變分區(qū)管理(概念)存儲(chǔ)管理:連續(xù)分配內(nèi)存地址OSJ51實(shí)現(xiàn)可變式分區(qū)分配存儲(chǔ)管理，必須解決：一、分區(qū)分配中數(shù)據(jù)構(gòu)造常用的數(shù)據(jù)構(gòu)造有：1.空閑分區(qū)表：始址長(zhǎng)度標(biāo)志15K23K未分配48K20K未分配80K30K未分配空空2.空閑分區(qū)鏈：N個(gè)字節(jié)可用（未分配）狀態(tài)位大小指針

0N+2前向指針

0N+2后向

指針

實(shí)現(xiàn)可變式分區(qū)分配存儲(chǔ)管理，必須解決：始址長(zhǎng)52二、分區(qū)分配算法系統(tǒng)運(yùn)行一段時(shí)間后，在整個(gè)存儲(chǔ)空間內(nèi)將出現(xiàn)許多大小不等的區(qū)域，有的仍被作業(yè)進(jìn)程占用，有的那么因作業(yè)已退出系統(tǒng)而成為可用于再分配的區(qū)域?，F(xiàn)在假設(shè)有一個(gè)新的作業(yè)需調(diào)入主存，如何為其選擇一個(gè)適宜的區(qū)域？在這種情況。有四種不同的分配算法，它們是：(1)最正確適應(yīng)算法(BestFit)(2)最壞適應(yīng)算法(FirstFit)(3)首次適應(yīng)算法(WorstFit)(4)循環(huán)首次〔下次〕適應(yīng)算法(NextFit)二、分區(qū)分配算法531.最正確適應(yīng)算法(Bestfit:BF)：就是為一作業(yè)選擇分區(qū)時(shí)總是尋找其大小最接近作業(yè)所要求的存儲(chǔ)區(qū)域。即：把作業(yè)放入這樣的分區(qū)后剩下的零頭最小。優(yōu)點(diǎn)：如果存儲(chǔ)空間中具有正好是所要求大小的存儲(chǔ)空白區(qū)，那么必然被選中；如果不存在這樣的空白區(qū)，也只比照要求稍大的空白區(qū)進(jìn)展劃分，而絕不會(huì)去劃分一個(gè)更大的空白區(qū)。因此，其后遇到大作業(yè)到來(lái)時(shí)，作業(yè)要求的存儲(chǔ)區(qū)域就比較容易得到滿(mǎn)足。為了加快查找速度，應(yīng)將存儲(chǔ)空間中所有的空白區(qū)按其大小遞增的順序鏈接起來(lái)，組成一空白區(qū)鏈(FreeList)。1.最正確適應(yīng)算法(Bestfit:B54指針10k60k90k20k例：有四塊空白區(qū)(從低地址→高地址)，來(lái)了一個(gè)作業(yè)需分配19k內(nèi)存。指針10k20k60k90k1k解：指針10k60k90k20k例：有四塊空白區(qū)(從低地址→高地55缺點(diǎn)：采用最正確適應(yīng)算法，在每次分配時(shí)，總是產(chǎn)生最小的空白區(qū)。因此，經(jīng)過(guò)一段時(shí)期后，存儲(chǔ)空間中可能留許多這樣的空白區(qū)，由于其太小而無(wú)法使用。為了改善這種情況，在該算法中設(shè)置一參數(shù)G，用它來(lái)確定最小分區(qū)的大小。中選擇一個(gè)分區(qū)時(shí)，如果選中的空白區(qū)與要求的大小之差小于G，那么不再對(duì)它劃分，而把整個(gè)這個(gè)空白區(qū)分配給申請(qǐng)的作業(yè)。最正確適應(yīng)算法的另一缺點(diǎn)是：在回收一個(gè)分區(qū)時(shí)，為了把它插入到空白區(qū)鏈中適宜的位置上也頗為費(fèi)時(shí)。所以，這種算法乍看起來(lái)是最正確的，其實(shí)那么不然。缺點(diǎn)：采用最正確適應(yīng)算法，在每次分配時(shí)，總是562.最壞適應(yīng)算法(Worstfit:WF)：與最正確適應(yīng)算法相反，它在為作業(yè)選擇存儲(chǔ)區(qū)域時(shí)，總是尋找最大的空白區(qū)。在劃分后剩下的空白區(qū)也是最大的，因而對(duì)以后的分配很可能仍然是有用的，這是該算法的一個(gè)優(yōu)點(diǎn)。但是，由于最大的空白塊總是首先被分配而進(jìn)展劃分，當(dāng)有大的作業(yè)時(shí)，其存儲(chǔ)空間的申請(qǐng)往往得不到滿(mǎn)足，這是該算法的一個(gè)缺點(diǎn)。指針90k60k20k10k71k為了支持這個(gè)算法的實(shí)現(xiàn)，空白塊應(yīng)以大小遞減的順序鏈接起來(lái)。2.最壞適應(yīng)算法(Worstfit:W573.首次適應(yīng)算法(FirstFit:FF)：由上面討論可見(jiàn)，BF和WF各有其利弊。首次適應(yīng)算法是對(duì)它們進(jìn)展折衷考慮后設(shè)計(jì)出來(lái)的。這里，每個(gè)空白區(qū)按其在存儲(chǔ)空間中地址遞增的順序鏈在一起，即每個(gè)后繼空白區(qū)的起始地址總是比前者的大。在為作業(yè)分配存儲(chǔ)區(qū)域時(shí)，從這個(gè)空白區(qū)鏈的始端開(kāi)場(chǎng)查找，選擇第一個(gè)足以滿(mǎn)足請(qǐng)求的空白塊，而不管它終究有多大。和上述算法一樣，這個(gè)選擇的空白區(qū)被分成兩局部。一局部與請(qǐng)求的大小相等，分配給作業(yè)；剩下的局部留在空白區(qū)鏈中。顯然，這個(gè)算法傾向于優(yōu)先利用存儲(chǔ)空間中低址局部的空白區(qū)。3.首次適應(yīng)算法(FirstFit:F58例：指針10k60k90k20k有四塊空白區(qū)(從低地址→高地址)，來(lái)了一個(gè)作業(yè)需分配19k內(nèi)存。指針10k60k90k20k41k解：例：指針10k60k90k20k有四塊空白區(qū)(從低地址→高地59主要優(yōu)點(diǎn)：算法簡(jiǎn)單，查找速度快；留在高址局部的大的空白區(qū)被劃分的時(shí)機(jī)較少，因而在大作業(yè)到來(lái)時(shí)也比較容易得到滿(mǎn)足。主要缺點(diǎn)：這種算法常常利用一個(gè)大的空白區(qū)適應(yīng)小作業(yè)的請(qǐng)求，從而留下一些較小的無(wú)法用的空白區(qū)，存儲(chǔ)空間利用率不高；而且，由于所有的請(qǐng)求都是從空白區(qū)鏈的始端開(kāi)場(chǎng)查找，因而這些小而無(wú)用的空白區(qū)集中在這個(gè)鏈的前端，相應(yīng)地，一些較大空白區(qū)在鏈的尾端才能發(fā)現(xiàn)，這種情況將使找到適宜空白區(qū)的速度降低。主要優(yōu)點(diǎn)：算法簡(jiǎn)單，查找速度快；留在高址局部604.下次適應(yīng)算法(Nextfit:NF)：為了抑制上述缺點(diǎn)，又設(shè)計(jì)了一種稱(chēng)為“下次〞適應(yīng)的算法，它實(shí)際上是首次適應(yīng)算法的一種變形，故也被稱(chēng)為帶旋轉(zhuǎn)指針的首次適應(yīng)算法(NextFitwithRovingPointer)。為此，我們把存儲(chǔ)空間中空白區(qū)構(gòu)成一個(gè)循環(huán)鏈。每次為存儲(chǔ)請(qǐng)求查找適宜的分區(qū)時(shí)，總是從上次查找完畢的地方開(kāi)場(chǎng)，只要找到一個(gè)足夠大的空白區(qū)，就將它劃分后分配出去。顯然，采用這一策略后，存儲(chǔ)空間的利用更加均衡，而不至于使小的空白區(qū)集中于存儲(chǔ)器的一端。但是，在存儲(chǔ)器的另一端也不可能保存大的空白塊，因此，當(dāng)需要獲得相當(dāng)大的空白區(qū)時(shí)，能滿(mǎn)足的可能性減少了。4.下次適應(yīng)算法(Nextfit:NF61關(guān)于分配策略的選擇：從上面對(duì)四種不同分配策略的討論可知，每個(gè)算法各有其優(yōu)缺點(diǎn)。那么，終究如何來(lái)評(píng)價(jià)一個(gè)分配算法并作出最好的選擇呢？對(duì)分配策略的一種有用的度量是，系統(tǒng)對(duì)選定的一組作業(yè)來(lái)運(yùn)行，比較第一次發(fā)生不能滿(mǎn)足存儲(chǔ)請(qǐng)求所經(jīng)歷的時(shí)間。然而，遺憾的是，系統(tǒng)開(kāi)場(chǎng)運(yùn)行時(shí)，對(duì)作業(yè)請(qǐng)求和釋放存儲(chǔ)區(qū)域的順序是不知道的，而且，總是可以設(shè)計(jì)出一個(gè)序列，對(duì)這些策略中任何一個(gè)是最好的。再那么，不管選擇哪一種算法，最終將幾乎不可防止地形成許多小的無(wú)用的分區(qū)，并導(dǎo)致某個(gè)作業(yè)因不能滿(mǎn)足存儲(chǔ)要求而被阻塞。關(guān)于分配策略的選擇：從上面對(duì)四種不同分配策略的討論可62這里，我們把存儲(chǔ)空間中這些小的無(wú)用的分區(qū)稱(chēng)為“外零頭〞(Externa1Fragmentation)。有人對(duì)各種不同的分配策略，廣泛地研究了實(shí)際系統(tǒng)的行為。研究說(shuō)明：就常規(guī)應(yīng)用而言，首次適應(yīng)算法及最正確適應(yīng)算法在延緩阻塞方面有著一樣的記錄。由于首次適應(yīng)算法實(shí)現(xiàn)起來(lái)最簡(jiǎn)單，因而多數(shù)系統(tǒng)選用它；但選用下次適應(yīng)和最正確適應(yīng)算法的存儲(chǔ)管理系統(tǒng)也不少。這里，我們把存儲(chǔ)空間中這些小的無(wú)用的分區(qū)稱(chēng)為63三、分區(qū)分配操作涉及動(dòng)態(tài)分區(qū)的主要操作有分配內(nèi)存和回收內(nèi)存。這些操作是在程序接口中通過(guò)系統(tǒng)調(diào)用發(fā)出的。

1.分配內(nèi)存：向操作系統(tǒng)提出一特定存儲(chǔ)量的請(qǐng)求。通常，它并不要求這個(gè)分配的存儲(chǔ)區(qū)域限于特定的位置，但是，這個(gè)區(qū)域必須是連續(xù)的。也就是說(shuō)，操作系統(tǒng)必須確定一個(gè)適當(dāng)?shù)拇鎯?chǔ)區(qū)域，使其在請(qǐng)求進(jìn)程的地址空間中成為可用的，如果無(wú)適當(dāng)?shù)膮^(qū)域可用，進(jìn)程必須等待，直到該請(qǐng)求能滿(mǎn)足為止。三、分區(qū)分配操作64從頭開(kāi)場(chǎng)查表檢索完否？m.size>u.size?m.size-u.size≤size?從該分區(qū)中劃出將該分區(qū)分配給請(qǐng)求者修改有關(guān)的數(shù)據(jù)構(gòu)造返回返回繼續(xù)檢索下一個(gè)表項(xiàng)將該分區(qū)從鏈中移出YYYNNN從頭開(kāi)場(chǎng)查表檢索完否？m.size>u.size?m.siz652.回收內(nèi)存：回收內(nèi)存是進(jìn)程用于歸還一個(gè)不再需用的存儲(chǔ)區(qū)域。通常，一個(gè)已分配的分區(qū)必須整個(gè)地歸還。操作系統(tǒng)必須回收進(jìn)程釋放了的存儲(chǔ)區(qū)域，并使它們?cè)谝院蠊┯蟹峙湔?qǐng)求時(shí)使用。當(dāng)一個(gè)作業(yè)終止時(shí)，必須回收其未釋放的任何空間。在回收一個(gè)分區(qū)時(shí)，一個(gè)回收的分區(qū)與空白區(qū)鄰接的情況有四種，對(duì)這四種情況分別作如下處理：(1)回收區(qū)僅與上面的空白區(qū)鄰接，合并后仍為空白區(qū)F1，其起始地址不變，只需改變其大小，并按F1中末端的后向指針值設(shè)置在回收區(qū)MCB的后向指針域中，同時(shí)，修改它的狀態(tài)位。如圖(a)2.回收內(nèi)存：回收內(nèi)存是進(jìn)程用于歸還一個(gè)66

F1回收區(qū)作業(yè)X(a)

新的F1作業(yè)X回收區(qū)F2(b)新的F2

(2)回收區(qū)僅與下面的空白區(qū)鄰接(圖b)，合并后仍為空白區(qū)F2，但其起始地址和大小均需改變，因而要相應(yīng)地修改F2的前、后空白區(qū)MCB的指針值，并按F2首部MCB中的指針值來(lái)設(shè)置回收區(qū)中首部的前向指針。F1(a)新的F1作業(yè)X(b)新的F267

F1回收區(qū)F2(c)

新的F1

(3)回收區(qū)與上、下面的空白區(qū)鄰接(圖c)，在這種情況下，撤消空白區(qū)F2，保留空白區(qū)F1，且其起始地址不變，但需改變大小以及原F1的后向指針，設(shè)置為原F2中的相應(yīng)值。

(4)回收區(qū)與上、下面的空白區(qū)均不鄰接，在這種情況下，應(yīng)為回收區(qū)單獨(dú)建立一新表項(xiàng)，填寫(xiě)回收區(qū)的首址和大小，并根據(jù)首地址插入到空閑鏈中的適當(dāng)位置。F1(c)新的F1(3)回收區(qū)與68順序地檢索可用資源表直至找到某表目的m.add>aa或m.size=0不是第一個(gè)表目且與前一可用區(qū)相鄰？與后一可用區(qū)相鄰？返回把所釋放的可用區(qū)與前一分區(qū)合并YY與后一可用區(qū)相鄰且不為空表目？與后一可用區(qū)合并將該表目以上的所有表目下移一格所釋的可用區(qū)的size=0?將該表目以上的所有表目上移一格并插入新釋放的可用區(qū)表目把所釋放的可用區(qū)與后一分區(qū)合并YNNNNY順序地檢索可用資源表直至找到不是第一個(gè)表目且與后一可返回把所694.2.4可重定位分區(qū)分配一、緊湊從前面知，可變式分區(qū)分配策略是在裝入作業(yè)時(shí)根據(jù)其要求量為其劃定相應(yīng)的區(qū)域。這種分配策略，消除了固定式分區(qū)分配造成的“內(nèi)零頭〞，但不可防止地在存儲(chǔ)空間中造成“外零頭〞，為了進(jìn)一步提高存儲(chǔ)器的利用率，必須設(shè)法減少由于外零頭造成的浪費(fèi)。一個(gè)最簡(jiǎn)單而直觀的解決零頭問(wèn)題的方法是，定時(shí)地或者在內(nèi)存緊張時(shí)，把存儲(chǔ)空間中的空白區(qū)合并為一個(gè)大的連續(xù)區(qū)。實(shí)現(xiàn)方法是移動(dòng)某些已分配區(qū)中的信息，使所有的作業(yè)位于存儲(chǔ)器的一端，而把全部空白區(qū)留在另一端。這種技術(shù)稱(chēng)為存儲(chǔ)器的“緊湊〞。4.2.4可重定位分區(qū)分配一、緊湊70操作系統(tǒng)作業(yè)1(18K)12K作業(yè)3(24K)16K作業(yè)4(46K)10K作業(yè)2(40K)12K作業(yè)5(50K)8K

020K256K緊湊前操作系統(tǒng)作業(yè)1(18K)作業(yè)3(24K)作業(yè)4(46K)作業(yè)2(40K)作業(yè)5(50K)空白區(qū)58K

020K256K緊湊后把一個(gè)作業(yè)從一個(gè)存儲(chǔ)區(qū)域移動(dòng)到另一個(gè)存儲(chǔ)區(qū)域所發(fā)生的問(wèn)題，正如把一個(gè)作業(yè)裝入到與它地址空間不一致的存儲(chǔ)空間所引起的問(wèn)題一樣，需要對(duì)作業(yè)中的某些地址局部和地址常數(shù)等進(jìn)展調(diào)整。一個(gè)較實(shí)用且可行的方法是采用動(dòng)態(tài)重定位技術(shù)。一個(gè)作業(yè)在主存中移動(dòng)后，只要改變重定位存放器中的內(nèi)容即可。操作系統(tǒng)0緊湊前操作系統(tǒng)0緊湊后71二、動(dòng)態(tài)重定位〔有關(guān)動(dòng)態(tài)重定位知識(shí)在前面已作了介紹〕動(dòng)態(tài)重定位分區(qū)分配策略是實(shí)現(xiàn)動(dòng)態(tài)分配及動(dòng)態(tài)存儲(chǔ)管理的根底。它允許作業(yè)在運(yùn)行過(guò)程中申請(qǐng)附加的存儲(chǔ)區(qū)域，也可以將不再需要的局部歸還給系統(tǒng)。地址空間

0

100Load1,500

500Y1K存儲(chǔ)空間

01K1124Load1,5001524Y2K

512K有效地址500重定位存放器1K處理機(jī)一側(cè)存儲(chǔ)器一側(cè)二、動(dòng)態(tài)重定位地址空間存儲(chǔ)空間有效地址72三、動(dòng)態(tài)重定位分區(qū)分配算法請(qǐng)求分配一個(gè)大小為xk的分區(qū)有大于xk的空閑區(qū)嗎？空閑區(qū)的總和xk嗎？緊縮存儲(chǔ)并相應(yīng)地修改諸表(得到一個(gè)完整的空閑區(qū)xk)分配分區(qū)并修改諸表此刻已經(jīng)無(wú)法分配一個(gè)分區(qū)返回一個(gè)分區(qū)號(hào)數(shù)是是否否三、動(dòng)態(tài)重定位分區(qū)分配算法請(qǐng)求分配一個(gè)大小為xk的分區(qū)有大于73說(shuō)明：1.動(dòng)態(tài)重定位分區(qū)分配法是利用分區(qū)的“拼接〞(對(duì)空白區(qū)而言)或“緊湊〞(作業(yè)程序而言)技術(shù)解決“零頭〞。2.問(wèn)題—拼湊時(shí)機(jī)的選擇(i)出現(xiàn)相鄰空白區(qū)即拼接；(或某分區(qū)被釋放后即緊縮)緊縮工作大，開(kāi)銷(xiāo)大，但管理簡(jiǎn)單(ii)存貯缺乏(空白分區(qū)不夠大)時(shí)進(jìn)展拼接。緊縮次數(shù)少，但管理(算法)較復(fù)雜。說(shuō)明：(i)出現(xiàn)相鄰空白區(qū)即拼接；(或某分區(qū)744.2.5對(duì)換(Swapping)在早期，為了抑制存儲(chǔ)空間缺乏而采取的另一種措施，稱(chēng)為對(duì)換技術(shù)(Swapping，也稱(chēng)為交換)。廣義地說(shuō)，所謂對(duì)換就是把暫時(shí)不用的某個(gè)(或某些)程序及其數(shù)據(jù)的局部或全部從主存移到輔存中去，以便騰出必要的存儲(chǔ)空間；接著把指定的程序或數(shù)據(jù)從輔存讀到相應(yīng)的主存中，并將控制轉(zhuǎn)給它，讓其在系統(tǒng)上運(yùn)行。這種對(duì)換技術(shù)，最早用在分時(shí)系統(tǒng)UNIX中。在任何時(shí)刻，在該系統(tǒng)的主存中只保存一個(gè)完整的用戶(hù)作業(yè)，當(dāng)其運(yùn)行一段時(shí)間后，或由于分配給它的時(shí)間片已用完，或由于需要其它資源而等待，系統(tǒng)就把它交換到輔存，同時(shí)把另一個(gè)作業(yè)調(diào)入主存讓其運(yùn)行。這樣，可以在存儲(chǔ)容量不大的小型機(jī)上實(shí)現(xiàn)分時(shí)系統(tǒng)。Microsoft公司的WindowsOS也采用這種對(duì)換技術(shù)。4.2.5對(duì)換(Swapping)在75如果對(duì)換是以整個(gè)進(jìn)程為單位的，稱(chēng)為“整體對(duì)換〞或“進(jìn)程對(duì)換〞，主要用于分時(shí)系統(tǒng)中，其目的是用以解決內(nèi)存緊張問(wèn)題，并可進(jìn)一步提高內(nèi)存利用率。如果對(duì)換是以“頁(yè)〞或“段〞為單位的，稱(chēng)為“頁(yè)面對(duì)換〞或“分段對(duì)換〞，統(tǒng)稱(chēng)為“局部對(duì)換〞。這種對(duì)換方法是實(shí)現(xiàn)請(qǐng)求式分頁(yè)及請(qǐng)求式分段存儲(chǔ)管理的根底。其目的是為了支持虛擬存儲(chǔ)器管理系統(tǒng)。本節(jié)簡(jiǎn)單介紹進(jìn)程對(duì)換，有關(guān)分頁(yè)對(duì)換和分段對(duì)換放在后面章節(jié)中介紹。為了實(shí)現(xiàn)進(jìn)程對(duì)換，系統(tǒng)需提供以下三個(gè)方面的功能：1對(duì)換空間的管理2進(jìn)程的換出3進(jìn)程的換入如果對(duì)換是以整個(gè)進(jìn)程為單位的，稱(chēng)為“整體對(duì)761.對(duì)換空間的管理在具有對(duì)換功能的OS，通常把外存分為文件區(qū)和對(duì)換區(qū)。前者用于存放文件，由于通常的文件都是較長(zhǎng)久地駐留在外存上，故對(duì)文件區(qū)管理的主要目標(biāo)，是提高文件存儲(chǔ)空間的利用率，為此，系統(tǒng)采取離散分配方式。后者那么用于存放從內(nèi)存換出的進(jìn)程，由于這些進(jìn)程在對(duì)換區(qū)中駐留的時(shí)間是短暫的，而對(duì)換操作又較頻繁，故對(duì)對(duì)換空間管理的主要目標(biāo)，那么是提高進(jìn)程的換入、換出速度，為此，所應(yīng)采取的管理策略是用連續(xù)分配方式，較少考慮外存中的碎片問(wèn)題1.對(duì)換空間的管理在具有對(duì)換功能的OS，77為了能對(duì)交換區(qū)中的空閑盤(pán)塊進(jìn)展管理，在系統(tǒng)中應(yīng)配置相應(yīng)的數(shù)據(jù)構(gòu)造，以記錄外存的使用情況。其形式與內(nèi)存在動(dòng)態(tài)分區(qū)分配方式中所用數(shù)據(jù)構(gòu)造相似，即同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個(gè)表目應(yīng)包含兩項(xiàng)，即對(duì)換分區(qū)首址和對(duì)換區(qū)長(zhǎng)度，它們的根本單位都是盤(pán)塊。由于對(duì)對(duì)換區(qū)的分配，是采用連續(xù)分配方式，因而對(duì)對(duì)換區(qū)空間的分配與回收，與動(dòng)態(tài)分區(qū)方式時(shí)內(nèi)存的分配與回收方法雷同。其分配算法可以是首次適應(yīng)算法、循環(huán)首次適應(yīng)算法和最正確適應(yīng)算法。對(duì)換區(qū)的回收操作也可分為四種情況(見(jiàn)教材P.148.)。對(duì)這幾種情況的處理方法也與動(dòng)態(tài)分區(qū)分配時(shí)的方法一樣。為了能對(duì)交換區(qū)中的空閑盤(pán)塊進(jìn)展管理，在系統(tǒng)中782.進(jìn)程的換出與換入當(dāng)內(nèi)存執(zhí)行某些操作而發(fā)現(xiàn)內(nèi)存缺乏時(shí)，便調(diào)用對(duì)換程序或喚醒對(duì)換進(jìn)程。它們的主要任務(wù)是實(shí)現(xiàn)進(jìn)程的換入與換出。1)進(jìn)程的換出在進(jìn)程換出時(shí)，是將內(nèi)存中的某些進(jìn)程調(diào)至對(duì)換區(qū)，以騰出內(nèi)存空間。換出過(guò)程分以下兩步：a.選出被換出的進(jìn)程首先選擇處于阻塞或睡眠狀態(tài)的進(jìn)程，當(dāng)有多個(gè)這樣的進(jìn)程時(shí)，應(yīng)選擇其優(yōu)先級(jí)最低的進(jìn)程換出。此外，還應(yīng)考慮進(jìn)程在內(nèi)存的駐留時(shí)間。當(dāng)內(nèi)存中已無(wú)阻塞進(jìn)程，而現(xiàn)在的空閑內(nèi)存空間仍缺乏以滿(mǎn)足需要時(shí)，便選擇優(yōu)先級(jí)最低的就緒進(jìn)程換出。2.進(jìn)程的換出與換入當(dāng)內(nèi)存執(zhí)行某些操作而發(fā)792)進(jìn)程的換入當(dāng)對(duì)換程序或?qū)Q進(jìn)程去執(zhí)行換入操作時(shí)，便去檢查PCB集合中所有進(jìn)程的狀態(tài)。從中找出“就緒且換出〞狀態(tài)的進(jìn)程。當(dāng)有多個(gè)這樣的進(jìn)程時(shí)，首先把其中換出時(shí)間(必須大于規(guī)定時(shí)間，如2s)最久的進(jìn)程作為換入進(jìn)程，再根據(jù)進(jìn)程的大小為其申請(qǐng)內(nèi)存，此時(shí)可能：①申請(qǐng)成功，直接將進(jìn)程換入；②申請(qǐng)失敗，須先將內(nèi)存中的某些進(jìn)程換出，騰出足夠的內(nèi)存后，再將該進(jìn)程換入。在對(duì)換進(jìn)程成功地?fù)Q入一個(gè)進(jìn)程后，假設(shè)還有可換入的進(jìn)程，那么再繼續(xù)執(zhí)行上述的換入過(guò)程，將其余處于“就緒且換出〞狀態(tài)的進(jìn)程陸續(xù)換入，直至所有“就緒且換出〞狀態(tài)的進(jìn)程全部換入，或已無(wú)法獲得足夠大的內(nèi)存來(lái)?yè)Q入進(jìn)程，此時(shí)對(duì)換程序或進(jìn)程才停頓換入工作。2)進(jìn)程的換入804.3根本分頁(yè)存儲(chǔ)管理方式前面介紹的分區(qū)存儲(chǔ)管理，一般都要求把一個(gè)作業(yè)的地址空間裝入到連續(xù)的存儲(chǔ)區(qū)域內(nèi)。因此，在動(dòng)態(tài)分區(qū)的存儲(chǔ)空間中，常常由于存在著一些缺乏以裝入任何作業(yè)的小的分區(qū)而浪費(fèi)掉局部存儲(chǔ)資源，這就是所謂存儲(chǔ)器的零頭問(wèn)題。盡管采用“緊湊〞技術(shù)可以解決這個(gè)問(wèn)題，但要為移動(dòng)大量信息花去不少處理機(jī)時(shí)間，代價(jià)較高。如果我們能取消對(duì)其存儲(chǔ)區(qū)域的連續(xù)性要求，必然會(huì)進(jìn)一步提高主存空間的利用率，又無(wú)需為移動(dòng)信息付出代價(jià)。存儲(chǔ)器的離散分配就是在這個(gè)指導(dǎo)思想下設(shè)計(jì)出來(lái)的。根據(jù)分配時(shí)所用的根本單位的不同，它分為：1.分頁(yè)式存儲(chǔ)管理2.分段式存儲(chǔ)管理3.段頁(yè)式存儲(chǔ)管理4.3根本分頁(yè)存儲(chǔ)管理方式前面介紹的分814.3.1頁(yè)面與頁(yè)表一、頁(yè)面和物理塊〔存儲(chǔ)塊〕在分頁(yè)存儲(chǔ)管理系統(tǒng)中，把每個(gè)進(jìn)程的地址空間分成一些大小相等的片，并稱(chēng)之為頁(yè)面或頁(yè)(Page)。同樣地，把主存的存儲(chǔ)空間也分成與頁(yè)一樣大小的片，這些片稱(chēng)為存儲(chǔ)塊或稱(chēng)為頁(yè)框(PageFrame)。在為進(jìn)程分配存儲(chǔ)空間時(shí)，總是以頁(yè)框?yàn)閱挝弧＠纾阂粋€(gè)作業(yè)的地址空間有m頁(yè)。那么，只要分配給它m個(gè)頁(yè)框，每一頁(yè)分別裝入一個(gè)頁(yè)框內(nèi)即可。這里，并不要求這些頁(yè)框是連續(xù)的。說(shuō)明：⑴從0開(kāi)場(chǎng)編制頁(yè)號(hào)，頁(yè)內(nèi)地址是相對(duì)于0編址；⑵在進(jìn)程調(diào)度時(shí)，必須把它的所有頁(yè)一次裝入到主存的頁(yè)框內(nèi)；如果當(dāng)時(shí)頁(yè)框數(shù)缺乏，那么該進(jìn)程必須等待，系統(tǒng)再調(diào)度另外的進(jìn)程?！布兎猪?yè)方式〕4.3.1頁(yè)面與頁(yè)表一、頁(yè)面和物理塊〔存儲(chǔ)塊〕82二、頁(yè)面大小在分頁(yè)系統(tǒng)中，頁(yè)面大小是由機(jī)器的地址構(gòu)造所決定的。對(duì)于某一機(jī)器只能采用一種大小的頁(yè)面。在確定地址構(gòu)造時(shí)，對(duì)頁(yè)面的大小應(yīng)選擇得適當(dāng)。因?yàn)椋孩偌僭O(shè)選擇的頁(yè)面較小，一方面可使內(nèi)存碎片小，并減少了內(nèi)存碎片的總空間，有利于提高內(nèi)存利用率；但另一方面，也會(huì)使每個(gè)進(jìn)程要求較多的頁(yè)面，從而導(dǎo)致頁(yè)表過(guò)長(zhǎng)，占用大量?jī)?nèi)存；還會(huì)降低頁(yè)面換進(jìn)換出的效率。②假設(shè)選擇的頁(yè)面較大，雖然可減少頁(yè)表長(zhǎng)度，提高換進(jìn)換出效率，但又會(huì)使頁(yè)內(nèi)碎片增大。頁(yè)面的大小通常在512B～4KB選擇，但總是2的冪。二、頁(yè)面大小83三、地址構(gòu)造這樣，允許把虛地址(邏輯地址)劃分為頁(yè)號(hào)和位移量(頁(yè)內(nèi)相對(duì)地址)兩局部。如以下圖。頁(yè)號(hào)P位移量W頁(yè)號(hào)、位移量的劃分是由系統(tǒng)自動(dòng)完成的，對(duì)用戶(hù)是透明的。0101123編號(hào)0~16777216相對(duì)地址0~2047頁(yè)號(hào)P位移量WP=int[A/L]W=AmodL給定一個(gè)邏輯地址A，頁(yè)面大小L，其頁(yè)號(hào)P和位移量W的計(jì)算公式如下：三、地址構(gòu)造這樣，允許把虛地址(邏輯地址84(357101)8＝(011,101,111,001,000,001)2

＝(01,110,1111,001,000,001)2例：設(shè)虛地址為(357101)8每一塊為1K字節(jié)塊〔頁(yè)〕的大?。?K=2101671101位移量為(1101)8,頁(yè)號(hào)為(167)8塊號(hào)由頁(yè)表指定，位移量在變換過(guò)程中不變(357101)8＝(011,101,111,001,00085四、頁(yè)表在分頁(yè)系統(tǒng)中，存儲(chǔ)分配問(wèn)題變得非常簡(jiǎn)單，作業(yè)的一頁(yè)可以分配到存儲(chǔ)空間中任何一個(gè)可用的頁(yè)框。現(xiàn)在的問(wèn)題是：(1)系統(tǒng)怎么知道作業(yè)的哪一頁(yè)分配在存儲(chǔ)空間的哪一頁(yè)框內(nèi)？作業(yè)的地址空間本來(lái)是連續(xù)的，現(xiàn)在把它分頁(yè)后并裝入到不連續(xù)的頁(yè)框內(nèi)，如何保證它仍能正確地運(yùn)行。也就是說(shuō)，(2)如何實(shí)現(xiàn)以及何時(shí)實(shí)現(xiàn)把作業(yè)的邏輯地址變換為主存的物理地址。一個(gè)可行的方法是采用動(dòng)態(tài)重定位技術(shù)。在執(zhí)行每條指令時(shí)進(jìn)展這種地址變換?，F(xiàn)在是以頁(yè)為單位分配的，故實(shí)現(xiàn)地址變換的機(jī)構(gòu)要求為每頁(yè)設(shè)置一個(gè)重定位存放器。這些存放器組成一個(gè)組，通常稱(chēng)為頁(yè)表。四、頁(yè)表86在實(shí)際系統(tǒng)中，為了減少硬件本錢(qián)，將頁(yè)表存在被保護(hù)的系統(tǒng)區(qū)內(nèi)。在頁(yè)表中每頁(yè)有相應(yīng)的表目，分別指出該頁(yè)在主存中的頁(yè)框號(hào)。這張頁(yè)表是在進(jìn)程裝入主存時(shí)，由系統(tǒng)根據(jù)內(nèi)存分配情況建立的。在多道程序系統(tǒng)中，為便于管理和保護(hù)，系統(tǒng)為每個(gè)裝入主存的進(jìn)程建立一張相應(yīng)的頁(yè)表。它的起始地址及大小填入該進(jìn)程的PCB中。一旦這個(gè)進(jìn)程被調(diào)度執(zhí)行，把它的頁(yè)表始址及大小裝入特定的頁(yè)表存放器中。此外，根據(jù)每頁(yè)內(nèi)容的不同，可以設(shè)置不同的存取限制。所以，在這頁(yè)表的表目中除了包含指向所在頁(yè)框的指針外，還包括一個(gè)存取控制手段，這個(gè)表目也稱(chēng)為頁(yè)描述子。頁(yè)框號(hào)Q存取權(quán)限頁(yè)描述子在實(shí)際系統(tǒng)中，為了減少硬件本錢(qián)，將頁(yè)表存在被87圖4-11頁(yè)表的作用圖4-11頁(yè)表的作用88...01234560123456作業(yè)的地址空間頁(yè)框（物理塊）頁(yè)號(hào)頁(yè)表主存中頁(yè)框（物理塊）..........01234560123456作業(yè)的頁(yè)框頁(yè)號(hào)頁(yè)表主存中頁(yè)89例1：某采用分頁(yè)存儲(chǔ)管理的系統(tǒng)中，物理地址占20位，邏輯地址中頁(yè)號(hào)占6位，頁(yè)面大小為1KB，問(wèn)：⑴該系統(tǒng)的內(nèi)存空間大小為多少？每個(gè)存儲(chǔ)塊的大小為多少？邏輯地址共幾位？每個(gè)作業(yè)的最大長(zhǎng)度為多少？⑵假設(shè)第0、1、2頁(yè)分別放在第3、7、9存儲(chǔ)塊中，那么邏輯地址0420H對(duì)應(yīng)的物理地址是多少？例1：某采用分頁(yè)存儲(chǔ)管理的系統(tǒng)中，物理地址占20位，邏輯地址90在分頁(yè)存儲(chǔ)管理系統(tǒng)中，根據(jù)題意：⑴物理地址占20位，所以該系統(tǒng)的內(nèi)存空間大小為：220=1MB存儲(chǔ)塊的大小與頁(yè)面大小一樣，而頁(yè)面大小為1KB，因此存儲(chǔ)塊的大小為：1KB由于頁(yè)面大小為1KB，占10位，而頁(yè)號(hào)占6位，因此邏輯地址共16位，從而該系統(tǒng)中的每個(gè)作業(yè)大小為：216=64KB在分頁(yè)存儲(chǔ)管理系統(tǒng)中，根據(jù)題意：91⑵法1〔全部轉(zhuǎn)換成10進(jìn)制〕：邏輯地址：0420H=1056因?yàn)?K<=1056<2K-1，所以在1號(hào)頁(yè)面內(nèi)，其頁(yè)內(nèi)位移量為：1056-1K=32；而1號(hào)頁(yè)面對(duì)應(yīng)7號(hào)物理塊，所以物理地址為：7×1K+32=7200。法2〔將頁(yè)面轉(zhuǎn)換成16進(jìn)制表示〕：頁(yè)面大?。?K=0400H。因?yàn)?400H<=0420H<07FFH，所以在1號(hào)頁(yè)面內(nèi)，其頁(yè)內(nèi)位移量為：0420H-0400H=20H；而1號(hào)頁(yè)面對(duì)應(yīng)7號(hào)物理塊，所以物理地址為：7×0400H+20H=1C20H。⑵法1〔全部轉(zhuǎn)換成10進(jìn)制〕：92例2：在分頁(yè)存儲(chǔ)系統(tǒng)中地址構(gòu)造的長(zhǎng)度為20位，頁(yè)面大小為2K，作業(yè)地址空間為8K，該作業(yè)各頁(yè)依次存放在1，3，6，7號(hào)物理塊中，相對(duì)地址4000處有一條指令Storel，2500，請(qǐng)給出該作業(yè)的頁(yè)表，并分別指出該指令所在頁(yè)號(hào)和對(duì)應(yīng)的物理單元及數(shù)據(jù)存放所在的頁(yè)號(hào)和物理單元。例2：在分頁(yè)存儲(chǔ)系統(tǒng)中地址構(gòu)造的長(zhǎng)度為20位，頁(yè)面大小為2K93由題意，頁(yè)面大小為2K，該作業(yè)的地址空間為8K，因此該作業(yè)有4頁(yè)，其頁(yè)表為：01132637因?yàn)?K<=4000<4K-1，所以指令在1號(hào)頁(yè)面內(nèi)，其頁(yè)內(nèi)位移量為：4000-2K=1952；又2K<=2500<4K-1，所以數(shù)據(jù)也在1號(hào)頁(yè)面內(nèi)，其頁(yè)內(nèi)位移量為：2500-2K=452。由頁(yè)表知1號(hào)頁(yè)面對(duì)應(yīng)存儲(chǔ)空間的3號(hào)物理塊，故數(shù)據(jù)和指令均存放在3號(hào)物理塊內(nèi)，指令存放的物理單元為：3