第4章存儲器管理(1)

1、12022-5-24第第4章章 存儲器管理存儲器管理n計算機(jī)系統(tǒng)中的存儲器可以分為兩種：內(nèi)存儲器計算機(jī)系統(tǒng)中的存儲器可以分為兩種：內(nèi)存儲器和輔助存儲器。前者可被和輔助存儲器。前者可被CPU直接訪問，后者不直接訪問，后者不能。輔助存儲器與能。輔助存儲器與CPU之間只能夠在輸入輸出控之間只能夠在輸入輸出控制系統(tǒng)的管理下，進(jìn)行信息交換。制系統(tǒng)的管理下，進(jìn)行信息交換。n既然內(nèi)存儲器可被既然內(nèi)存儲器可被CPU直接訪問，因此它是計算直接訪問，因此它是計算機(jī)系統(tǒng)中的一種極為重要的資源。在操作系統(tǒng)中，機(jī)系統(tǒng)中的一種極為重要的資源。在操作系統(tǒng)中，把管理內(nèi)存儲器的部分稱為把管理內(nèi)存儲器的部分稱為“存儲器管理存儲器

2、管理”。能。能否合理地使用內(nèi)存，會在很大程度上影響到整個否合理地使用內(nèi)存，會在很大程度上影響到整個計算機(jī)系統(tǒng)的性能。計算機(jī)系統(tǒng)的性能。22022-5-24存儲器管理的主要任務(wù)存儲器管理的主要任務(wù) n存儲管理的主要任務(wù)是盡可能方存儲管理的主要任務(wù)是盡可能方便用戶和提高內(nèi)存儲器的使用效便用戶和提高內(nèi)存儲器的使用效率，使內(nèi)存儲器在成本、速度和率，使內(nèi)存儲器在成本、速度和規(guī)模之間獲得較好的權(quán)衡。規(guī)模之間獲得較好的權(quán)衡。 32022-5-244.1存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu) n多級存儲器結(jié)構(gòu)多級存儲器結(jié)構(gòu)n一般計算機(jī)，存儲層次至少應(yīng)具有三級：最高層為一般計算機(jī)，存儲層次至少應(yīng)具有三級：最高層為CP

3、U寄存寄存器，中間為主存，最底層是輔存。較高檔計算機(jī)中，根據(jù)具器，中間為主存，最底層是輔存。較高檔計算機(jī)中，根據(jù)具體功能分為體功能分為6層，如圖層，如圖4.1寄存器高速緩存主存磁盤緩存磁盤可移動存儲介質(zhì)42022-5-244.1存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu) n多級存儲器結(jié)構(gòu)多級存儲器結(jié)構(gòu)n在存儲層次中越往上，存儲介質(zhì)的訪問速度在存儲層次中越往上，存儲介質(zhì)的訪問速度越快，價格越高，相對存儲容量也越小。寄越快，價格越高，相對存儲容量也越小。寄存器、高速緩存、主存儲器和磁盤緩存屬于存器、高速緩存、主存儲器和磁盤緩存屬于操作系統(tǒng)存儲管理的管轄范疇。操作系統(tǒng)存儲管理的管轄范疇。52022-5-244

4、.1存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu) n主存儲器與寄存器主存儲器與寄存器 n（1）主存儲器（又稱內(nèi)存和主存）是計算機(jī)系統(tǒng)）主存儲器（又稱內(nèi)存和主存）是計算機(jī)系統(tǒng)中一個主要部分，用于保存進(jìn)程運(yùn)行時的程序數(shù)據(jù)。中一個主要部分，用于保存進(jìn)程運(yùn)行時的程序數(shù)據(jù)。CPU本身讀取指令和數(shù)據(jù)與外圍設(shè)備的數(shù)據(jù)交換都本身讀取指令和數(shù)據(jù)與外圍設(shè)備的數(shù)據(jù)交換都需要通過主存儲器。由于主存儲器的訪問速度遠(yuǎn)低需要通過主存儲器。由于主存儲器的訪問速度遠(yuǎn)低于于CPU執(zhí)行指令的速度，為緩和這一矛盾，計算機(jī)執(zhí)行指令的速度，為緩和這一矛盾，計算機(jī)系統(tǒng)中引入了寄存器和高速緩存。系統(tǒng)中引入了寄存器和高速緩存。n（2）寄存器訪問速度最快，

5、但價格昂貴。）寄存器訪問速度最快，但價格昂貴。62022-5-244.1存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu) n高速緩存與磁盤緩存高速緩存與磁盤緩存 n（1）高速緩存介于主存與寄存器之間，速度）高速緩存介于主存與寄存器之間，速度比主存快，比寄存器慢，價格比寄存器要低。比主存快，比寄存器慢，價格比寄存器要低。n（2）磁盤緩存用于緩和磁盤的）磁盤緩存用于緩和磁盤的I/O速度遠(yuǎn)低速度遠(yuǎn)低于對主存的訪問速度的矛盾，磁盤緩存實際于對主存的訪問速度的矛盾，磁盤緩存實際上是從主存空間中劃出一塊區(qū)域，用來暫存上是從主存空間中劃出一塊區(qū)域，用來暫存頻繁使用的一部分磁盤數(shù)據(jù)和信息。頻繁使用的一部分磁盤數(shù)據(jù)和信息。72

6、022-5-24習(xí)題習(xí)題 n在計算機(jī)系統(tǒng)存儲層次中，屬于操作系統(tǒng)存在計算機(jī)系統(tǒng)存儲層次中，屬于操作系統(tǒng)存儲管理的管理范疇的有（）。儲管理的管理范疇的有（）。n在計算機(jī)系統(tǒng)存儲層次中，訪問速度最快的在計算機(jī)系統(tǒng)存儲層次中，訪問速度最快的是（）。是（）。 A. 高速緩存高速緩存 B. 主存主存 C. 磁盤緩存磁盤緩存 D.寄存器寄存器 n磁盤緩存實際上占用了（）空間。磁盤緩存實際上占用了（）空間。 A.高速緩存高速緩存 B.主存主存 C.磁盤磁盤 D.可移動存可移動存儲介質(zhì)儲介質(zhì)82022-5-244.2 程序的裝入與鏈接程序的裝入與鏈接 n4.2.1程序的裝入程序的裝入n4.2.2程序的鏈接程序

7、的鏈接 92022-5-24程序的裝入和鏈接程序的裝入和鏈接 n在多道程序環(huán)境下，要使程序運(yùn)行，在多道程序環(huán)境下，要使程序運(yùn)行，必須先為之創(chuàng)建進(jìn)程。而創(chuàng)建進(jìn)程的必須先為之創(chuàng)建進(jìn)程。而創(chuàng)建進(jìn)程的第一件事，就是將程序和數(shù)據(jù)裝入內(nèi)第一件事，就是將程序和數(shù)據(jù)裝入內(nèi)存。存。102022-5-24源程序的執(zhí)行過程源程序的執(zhí)行過程 n將一個用戶源程序變?yōu)橐粋€可在內(nèi)存中執(zhí)行將一個用戶源程序變?yōu)橐粋€可在內(nèi)存中執(zhí)行的程序，通常要經(jīng)過編譯、鏈接和裝入幾個的程序，通常要經(jīng)過編譯、鏈接和裝入幾個步驟步驟n（1）編譯。由編譯程序?qū)⒂脩粼创a編譯成）編譯。由編譯程序?qū)⒂脩粼创a編譯成若干個目標(biāo)模塊。若干個目標(biāo)模塊。n（2）

8、鏈接。由鏈接程序?qū)⒕幾g后形成的目標(biāo)）鏈接。由鏈接程序?qū)⒕幾g后形成的目標(biāo)模塊以及它們所需要的庫函數(shù)，鏈接在一起，模塊以及它們所需要的庫函數(shù)，鏈接在一起，形成一個裝入模塊。形成一個裝入模塊。n（3）裝入。由裝入程序?qū)⒀b入模塊裝入主存）裝入。由裝入程序?qū)⒀b入模塊裝入主存的過程。的過程。112022-5-24源程序的執(zhí)行過程源程序的執(zhí)行過程 n通常要經(jīng)過編譯、鏈接和裝入幾個步驟通常要經(jīng)過編譯、鏈接和裝入幾個步驟庫鏈接程序裝入模塊裝入程序編譯程序產(chǎn)生的目標(biāo)模塊第一步第二步第三步內(nèi)存122022-5-244.1.1程序的裝入程序的裝入n程序的裝入就是把程序裝入內(nèi)存空間。以無需程序的裝入就是把程序裝入內(nèi)存空

9、間。以無需進(jìn)行鏈接的單目標(biāo)模塊的裝入過程為例。進(jìn)行鏈接的單目標(biāo)模塊的裝入過程為例。n采用采用三種三種方式方式 u（1）絕對裝入方式：是由裝入程序根據(jù)裝入模塊中）絕對裝入方式：是由裝入程序根據(jù)裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存。的地址，將程序和數(shù)據(jù)裝入內(nèi)存。 u（2）可重定位方式）可重定位方式 ：是由裝入程序根據(jù)內(nèi)存當(dāng)前的：是由裝入程序根據(jù)內(nèi)存當(dāng)前的實際使用情況，將裝入模塊裝入到內(nèi)存適當(dāng)?shù)牡胤?。實際使用情況，將裝入模塊裝入到內(nèi)存適當(dāng)?shù)牡胤健?u（3）動態(tài)運(yùn)行時裝入方式：動態(tài)運(yùn)行時的裝入程序，）動態(tài)運(yùn)行時裝入方式：動態(tài)運(yùn)行時的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的在把裝入模塊

10、裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序要真正執(zhí)行時才進(jìn)行。到程序要真正執(zhí)行時才進(jìn)行。 132022-5-24程序的裝入程序的裝入n絕對裝入方式：是由裝入程序根據(jù)裝入模絕對裝入方式：是由裝入程序根據(jù)裝入模塊中的地址，將程序和數(shù)據(jù)裝入主存塊中的地址，將程序和數(shù)據(jù)裝入主存u若知道程序在內(nèi)存的位置，編譯程序?qū)a(chǎn)生若知道程序在內(nèi)存的位置，編譯程序?qū)a(chǎn)生絕對地址目標(biāo)模塊絕對地址目標(biāo)模塊u絕對地址一般由編譯程序給出絕對地址一般由編譯程序給出u程序被裝入內(nèi)存后，由于程序中的邏輯地址程序被裝入內(nèi)存后，由于程序中的邏輯地

11、址與實際內(nèi)存地址完全相同，所以不允許改變與實際內(nèi)存地址完全相同，所以不允許改變程序和數(shù)據(jù)的地址程序和數(shù)據(jù)的地址u只適于單道環(huán)境只適于單道環(huán)境142022-5-24程序的裝入程序的裝入u絕對裝入方式只能將目標(biāo)模塊裝入到內(nèi)絕對裝入方式只能將目標(biāo)模塊裝入到內(nèi)存中事先指定的位置。在多道程序環(huán)境存中事先指定的位置。在多道程序環(huán)境下，編譯程序不可能預(yù)知所編譯的目標(biāo)下，編譯程序不可能預(yù)知所編譯的目標(biāo)模塊應(yīng)放在內(nèi)存的什么地方，因此在多模塊應(yīng)放在內(nèi)存的什么地方，因此在多道程序環(huán)境下，所得到的目標(biāo)模塊的起道程序環(huán)境下，所得到的目標(biāo)模塊的起始地址通常是從始地址通常是從0開始的，程序中的其開始的，程序中的其它地址都是

12、相對于起始地址計算的。因它地址都是相對于起始地址計算的。因此采用重定位裝入方式。此采用重定位裝入方式。152022-5-24程序的裝入程序的裝入u可重定位方式可重定位方式 ：是由裝入程序根據(jù)主存當(dāng)是由裝入程序根據(jù)主存當(dāng)前的實際使用情況，將裝入模塊裝入到主存前的實際使用情況，將裝入模塊裝入到主存適當(dāng)?shù)牡胤?。適當(dāng)?shù)牡胤健?F重定位：在裝入時對目標(biāo)程序中指令重定位：在裝入時對目標(biāo)程序中指令和數(shù)據(jù)的修改過程。會使裝入模塊中和數(shù)據(jù)的修改過程。會使裝入模塊中的所有邏輯地址與實際裝入內(nèi)存的物的所有邏輯地址與實際裝入內(nèi)存的物理地址不同理地址不同162022-5-24程序的裝入程序的裝入u可重定位方式可重定位方

13、式 ：Load 1,6Add 1,8Store 1,10ABLoad 1,6Add 1,8Store 1,10ABLoad 1,106Add 1,108Store 1,110AB172022-5-24可重定位裝入方式可重定位裝入方式(Relocation Loading Mode) 圖 4-2 作業(yè)裝入內(nèi)存時的情況 LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作業(yè)地址空間內(nèi)存空間12500182022-5-24程序的裝入程序的裝入u可重定位方式可重定位方式F把在裝入時對目標(biāo)程序中指令和數(shù)據(jù)把在裝入時對目標(biāo)程序中指令和

14、數(shù)據(jù)的修改過程稱為重定位的修改過程稱為重定位F地址變換通常是在裝入時一次完成，地址變換通常是在裝入時一次完成，以后不再改變，故稱為靜態(tài)重定位以后不再改變，故稱為靜態(tài)重定位F適于多道環(huán)境但不允許程序在內(nèi)存中適于多道環(huán)境但不允許程序在內(nèi)存中移動移動192022-5-24程序的裝入程序的裝入u動態(tài)運(yùn)行時裝入方式：動態(tài)運(yùn)行時的裝動態(tài)運(yùn)行時裝入方式：動態(tài)運(yùn)行時的裝入程序，在把裝入模塊裝入內(nèi)存后，并入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序要真正執(zhí)行時才進(jìn)行。程序要真正執(zhí)行時

15、才進(jìn)行。 F適于多道環(huán)境F允許程序移動，如切換F動態(tài)重定位F需要特殊硬件支持（重定位寄存器）202022-5-24程序的裝入程序的裝入u動態(tài)運(yùn)行時裝入方式：動態(tài)運(yùn)行時裝入方式：LOAD1,25003650100250050002500相對地址10000重定位寄存器LOAD1,250036510000101001250015000作業(yè)J處理機(jī)一側(cè) 存儲器一側(cè)主存212022-5-244.2.2程序的鏈接程序的鏈接 n鏈接程序的功能是將經(jīng)過編譯或匯編后所得到鏈接程序的功能是將經(jīng)過編譯或匯編后所得到的一組目標(biāo)模塊以及它們所需要的庫函數(shù)，裝的一組目標(biāo)模塊以及它們所需要的庫函數(shù)，裝配成一個完整的裝入模塊

16、。配成一個完整的裝入模塊。n實現(xiàn)鏈接的方法有實現(xiàn)鏈接的方法有三種三種u靜態(tài)鏈接：事先進(jìn)行鏈接，以后不再拆開的鏈接方式靜態(tài)鏈接：事先進(jìn)行鏈接，以后不再拆開的鏈接方式u裝入時動態(tài)鏈接：用戶源程序經(jīng)編譯后所得到的目標(biāo)裝入時動態(tài)鏈接：用戶源程序經(jīng)編譯后所得到的目標(biāo)模塊，是在裝入內(nèi)存時，邊裝入邊鏈接的。模塊，是在裝入內(nèi)存時，邊裝入邊鏈接的。 u運(yùn)行時動態(tài)鏈接：某些目標(biāo)模塊的鏈接，是在程序執(zhí)運(yùn)行時動態(tài)鏈接：某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要該（目標(biāo)）模塊時，才對它進(jìn)行鏈接行中需要該（目標(biāo)）模塊時，才對它進(jìn)行鏈接222022-5-244.2.2程序的鏈接程序的鏈接 u靜態(tài)鏈接：事先進(jìn)行鏈接，以后不再拆開

17、的鏈接方式靜態(tài)鏈接：事先進(jìn)行鏈接，以后不再拆開的鏈接方式 F對相對地址進(jìn)行修改對相對地址進(jìn)行修改F變換外部調(diào)用符號變換外部調(diào)用符號模塊 ACALL B；Return；0L1模塊 BCALL C；Return；0M1模塊 CReturn；0N10模塊 AJSR“L”Return；L1模塊 BJSR“LM”Return；LLM1LMLMN1模塊 CReturn；(a) 目標(biāo)模塊(b) 裝入模塊JSR：保：保存返回存返回地址，地址，跳轉(zhuǎn)到跳轉(zhuǎn)到新地址新地址232022-5-24程序的鏈接程序的鏈接 u裝入時動態(tài)鏈接：用戶源程序經(jīng)編譯后所得到的目裝入時動態(tài)鏈接：用戶源程序經(jīng)編譯后所得到的目標(biāo)模塊，是在

18、裝入主存時，邊裝入邊鏈接的。標(biāo)模塊，是在裝入主存時，邊裝入邊鏈接的。 F改變相對地址的方式如方法一F便于修改和更新F便于實現(xiàn)目標(biāo)模塊共享模塊 ACALL B；Return；0L1模塊 BCALL C；Return；0M1模塊 CReturn；0N10模塊 AJSR“L”Return；L1模塊 BJSR“LM”Return；LLM1LMLMN1模塊 CReturn；(a) 目標(biāo)模塊(b) 裝入模塊模塊模塊A模塊模塊B模塊模塊CACBBACA靜態(tài)鏈接靜態(tài)鏈接BCA動態(tài)鏈接動態(tài)鏈接242022-5-24程序的鏈接程序的鏈接 u運(yùn)行時動態(tài)鏈接：可將某些目標(biāo)模運(yùn)行時動態(tài)鏈接：可將某些目標(biāo)模塊的鏈接，推遲

19、到執(zhí)行時才進(jìn)行。塊的鏈接，推遲到執(zhí)行時才進(jìn)行。F便于實現(xiàn)目標(biāo)模塊的修改、更新和共享F加快程序的裝入過程 F提高內(nèi)存利用率252022-5-24練習(xí)練習(xí) u靜態(tài)重定位是在作業(yè)的（）中進(jìn)行靜態(tài)重定位是在作業(yè)的（）中進(jìn)行的，動態(tài)重定位是在作業(yè)（）中進(jìn)的，動態(tài)重定位是在作業(yè)（）中進(jìn)程的程的F編譯過程F裝入過程F修改過程F執(zhí)行過程262022-5-24練習(xí)練習(xí) u把作業(yè)裝入內(nèi)存中隨即進(jìn)行地址變把作業(yè)裝入內(nèi)存中隨即進(jìn)行地址變換的方式稱為（），而在作業(yè)執(zhí)行換的方式稱為（），而在作業(yè)執(zhí)行期間期間,當(dāng)訪問到指令或數(shù)據(jù)時才進(jìn)行當(dāng)訪問到指令或數(shù)據(jù)時才進(jìn)行地址變換的方式稱為（）地址變換的方式稱為（） 。272022-

20、5-24練習(xí)練習(xí) u靜態(tài)鏈接是在（）中進(jìn)行的，而動靜態(tài)鏈接是在（）中進(jìn)行的，而動態(tài)鏈接是在（）或（）中進(jìn)行的，態(tài)鏈接是在（）或（）中進(jìn)行的，其中在（）進(jìn)行鏈接，可使得內(nèi)存其中在（）進(jìn)行鏈接，可使得內(nèi)存利用率最高利用率最高F編譯某段程序時F裝入某段程序時F調(diào)用某段程序時F緊湊時F裝入程序之前282022-5-244.3連續(xù)分配方式連續(xù)分配方式 u連續(xù)分配方式：為一個用戶程序分連續(xù)分配方式：為一個用戶程序分配一個連續(xù)的內(nèi)存空間配一個連續(xù)的內(nèi)存空間F單一連續(xù)分配F固定分區(qū)分配 F動態(tài)分區(qū)分配F動態(tài)重定位分區(qū)分配292022-5-244.3連續(xù)分配方式連續(xù)分配方式 u單一連續(xù)分配單一連續(xù)分配F只能用于

21、單用戶，單任務(wù)的操作系統(tǒng)。F把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分 F系統(tǒng)區(qū)給OS使用，通常在低址部分F用戶區(qū)給用戶使用。在主存中僅駐留一道程序，整個用戶區(qū)為一用戶獨(dú)占。當(dāng)用戶作業(yè)空間大于用戶區(qū)時，該作業(yè)不能裝入。302022-5-244.3連續(xù)分配方式連續(xù)分配方式 u單一連續(xù)分配單一連續(xù)分配312022-5-244.3連續(xù)分配方式連續(xù)分配方式 u固定分區(qū)分配固定分區(qū)分配F將內(nèi)存中的用戶空間劃分為若干個固定大小將內(nèi)存中的用戶空間劃分為若干個固定大小的區(qū)域的區(qū)域 F每個分區(qū)中只裝入一道作業(yè)，一個作業(yè)也只每個分區(qū)中只裝入一道作業(yè)，一個作業(yè)也只能裝入一個分區(qū)中，這樣可以裝入多個作業(yè)，能裝入一個分區(qū)中，這樣可

22、以裝入多個作業(yè)，使它們并發(fā)執(zhí)行。當(dāng)有一個空閑分區(qū)時，便使它們并發(fā)執(zhí)行。當(dāng)有一個空閑分區(qū)時，便可從外存的后備隊列中，選擇一個適當(dāng)大小可從外存的后備隊列中，選擇一個適當(dāng)大小的作業(yè)裝入該分區(qū)；當(dāng)該作業(yè)運(yùn)行完時，又的作業(yè)裝入該分區(qū)；當(dāng)該作業(yè)運(yùn)行完時，又可從后備隊列中選擇另一個作業(yè)裝入該分區(qū)可從后備隊列中選擇另一個作業(yè)裝入該分區(qū)（分區(qū)大小可以相同也可以不同）。（分區(qū)大小可以相同也可以不同）。 322022-5-244.3連續(xù)分配方式連續(xù)分配方式 u固定分區(qū)分配固定分區(qū)分配F可運(yùn)行多道程序的存儲管理方式可運(yùn)行多道程序的存儲管理方式F要求把作業(yè)全部裝入主存，且裝入一個連續(xù)要求把作業(yè)全部裝入主存，且裝入一個連

23、續(xù)的存儲空間。的存儲空間。332022-5-24固定分區(qū)分配固定分區(qū)分配 u劃分分區(qū)的方法劃分分區(qū)的方法F分區(qū)大小相等分區(qū)大小相等 缺點：缺乏靈活性缺點：缺乏靈活性 可被用于利用一臺計算機(jī)去控制多個相同可被用于利用一臺計算機(jī)去控制多個相同對象的場合對象的場合F分區(qū)大小不等。分區(qū)大小不等。342022-5-24固定分區(qū)分配固定分區(qū)分配 u內(nèi)存分配內(nèi)存分配 為了記錄各個分區(qū)的基本情況和使用情況，方便主存為了記錄各個分區(qū)的基本情況和使用情況，方便主存空間的分配與回收操作，設(shè)置了一張分區(qū)使用表?？臻g的分配與回收操作，設(shè)置了一張分區(qū)使用表。分區(qū)使用表的內(nèi)容包括：分區(qū)序號、起始地址、大小、分區(qū)使用表的內(nèi)容

24、包括：分區(qū)序號、起始地址、大小、狀態(tài)。狀態(tài)。狀態(tài)欄的值為狀態(tài)欄的值為“0”表示分區(qū)空閑，可以裝入作業(yè)；當(dāng)表示分區(qū)空閑，可以裝入作業(yè)；當(dāng)裝入作業(yè)后，其值改為已分配裝入作業(yè)后，其值改為已分配352022-5-24固定分區(qū)分配固定分區(qū)分配 u內(nèi)存分配內(nèi)存分配 20圖 4-4 固定分區(qū)使用表 未未362022-5-24區(qū)號 大小 起始地址 狀態(tài) 0 20K 40K 未分配 1 40K 60K 已分配 2 80K 100K 已分配 3 160K 180K 未分配 4 320K 340K 已分配 ： ： ： ： 作業(yè)號 大小 區(qū)號 0 55K 2 1 10K 0 2 150K 4 ： ： ： 作業(yè)表 內(nèi)存

25、分區(qū)表 OS 作業(yè) 1 作業(yè) 0 ： ： 作業(yè) 2 ： ： ： 0 區(qū) 1 區(qū) 2 區(qū) 5 區(qū) 4 區(qū) 內(nèi)存 區(qū)號 大小 起始地址 狀態(tài) 0 20K 40K 未分配 1 40K 60K 已分配 2 80K 100K 已分配 3 160K 180K 未分配 4 320K 340K 已分配 ： ： ： ： 作業(yè)號 大小 區(qū)號 0 55K 2 1 10K 0 2 150K 4 ： ： ： 作業(yè)表 內(nèi)存分區(qū)表 OS 作業(yè) 1 作業(yè) 0 ： ： 作業(yè) 2 ： ： ： 0 區(qū) 1 區(qū) 2 區(qū) 5 區(qū) 4 區(qū) 內(nèi)存 固定分區(qū)分配固定分區(qū)分配描述內(nèi)存中每一個區(qū)描述內(nèi)存中每一個區(qū)域的情況域的情況描述存放于區(qū)域中

26、的描述存放于區(qū)域中的作業(yè)作業(yè) 3 3 3區(qū)號 大小 起始地址 狀態(tài) 0 20K 40K 未分配 1 40K 60K 已分配 2 80K 100K 已分配 3 160K 180K 未分配 4 320K 340K 已分配 ： ： ： ： 作業(yè)號 大小 區(qū)號 0 55K 2 1 10K 0 2 150K 4 ： ： ： 作業(yè)表 內(nèi)存分區(qū)表 OS 作業(yè) 1 作業(yè) 0 ： ： 作業(yè) 2 ： ： ： 0 區(qū) 1 區(qū) 2 區(qū) 5 區(qū) 4 區(qū) 內(nèi)存 未未已已 將內(nèi)存空間由小到大劃將內(nèi)存空間由小到大劃分為若干個分為若干個位置固定大小不位置固定大小不等等的區(qū)域，每個區(qū)域可以存的區(qū)域，每個區(qū)域可以存放一個作業(yè)，存放

27、于不同區(qū)放一個作業(yè)，存放于不同區(qū)域的域的作業(yè)可以并行作業(yè)可以并行。 用戶邏輯地址空間依然用戶邏輯地址空間依然是一個連續(xù)的整體，在作業(yè)是一個連續(xù)的整體，在作業(yè)申請進(jìn)入內(nèi)存時申請進(jìn)入內(nèi)存時一次性裝入一次性裝入。 372022-5-24固定分區(qū)分配固定分區(qū)分配 u內(nèi)存分配內(nèi)存分配 例：某系統(tǒng)的內(nèi)存容量為例：某系統(tǒng)的內(nèi)存容量為256256K K，操作系統(tǒng)占用低地址的操作系統(tǒng)占用低地址的2020K K，其余空間劃分成其余空間劃分成4 4個固定大小的分區(qū)。如下圖個固定大小的分區(qū)。如下圖382022-5-24固定分區(qū)分配的管理特點固定分區(qū)分配的管理特點 n（1）一個作業(yè)只能裝入一個分區(qū)，不能裝入兩個）一個作

28、業(yè)只能裝入一個分區(qū)，不能裝入兩個或多個相鄰的分區(qū)。一個分區(qū)只能裝入一個作業(yè)，或多個相鄰的分區(qū)。一個分區(qū)只能裝入一個作業(yè)，當(dāng)分區(qū)大小不能滿足作業(yè)的要求時，該作業(yè)暫時不當(dāng)分區(qū)大小不能滿足作業(yè)的要求時，該作業(yè)暫時不能裝入。能裝入。n（2）通過對）通過對“分區(qū)使用表分區(qū)使用表”的改寫，來實現(xiàn)主存的改寫，來實現(xiàn)主存的分配與回收。作業(yè)在執(zhí)行時，不會改變存儲區(qū)域，的分配與回收。作業(yè)在執(zhí)行時，不會改變存儲區(qū)域，所以采用靜態(tài)地址重定位方式。此方法易于實現(xiàn)，所以采用靜態(tài)地址重定位方式。此方法易于實現(xiàn)，系統(tǒng)開銷小。系統(tǒng)開銷小。n（3）當(dāng)分區(qū)較大作業(yè)較小時，仍然浪費(fèi)許多主存）當(dāng)分區(qū)較大作業(yè)較小時，仍然浪費(fèi)許多主存空間

29、空間(內(nèi)零頭）。并且分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)內(nèi)零頭）。并且分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的作業(yè)數(shù)目。行的作業(yè)數(shù)目。 392022-5-24固定分區(qū)存儲管理舉例固定分區(qū)存儲管理舉例 n例例u在某系統(tǒng)中采用固定分區(qū)分配管理方式，主存分在某系統(tǒng)中采用固定分區(qū)分配管理方式，主存分區(qū)（單位字節(jié)）情況如圖所示。現(xiàn)有大小為區(qū)（單位字節(jié)）情況如圖所示?，F(xiàn)有大小為1KB、9KB、33KB、121KB的多個作業(yè)要求進(jìn)入主存，的多個作業(yè)要求進(jìn)入主存，試畫出它們進(jìn)入主存后的空間分配情況，并說明試畫出它們進(jìn)入主存后的空間分配情況，并說明主存浪費(fèi)有多大？主存浪費(fèi)有多大？ 402022-5-24000 0操作系統(tǒng)操作系統(tǒng)（

30、20k）作業(yè)作業(yè)17KB作業(yè)作業(yè)223KB作業(yè)作業(yè)331KB作業(yè)作業(yè)412KB412022-5-24固定分區(qū)性能分析固定分區(qū)性能分析n在作業(yè)大小和出現(xiàn)頻率均已知的情況下，固定在作業(yè)大小和出現(xiàn)頻率均已知的情況下，固定分區(qū)是合適的。在這種情況下分區(qū)的大小選擇分區(qū)是合適的。在這種情況下分區(qū)的大小選擇與作業(yè)大小相當(dāng)，這樣內(nèi)存的使用效率較高與作業(yè)大小相當(dāng)，這樣內(nèi)存的使用效率較高（控制系統(tǒng)）。（控制系統(tǒng)）。n但是若作業(yè)的大小和出現(xiàn)的頻率不知道時，勢但是若作業(yè)的大小和出現(xiàn)的頻率不知道時，勢必造成分區(qū)的大小和作業(yè)的大小相差甚遠(yuǎn)，這必造成分區(qū)的大小和作業(yè)的大小相差甚遠(yuǎn)，這樣就會造成存儲空間的浪費(fèi)，從而影響整個系

31、樣就會造成存儲空間的浪費(fèi)，從而影響整個系統(tǒng)的效率。統(tǒng)的效率。 n早期的早期的IBMIBM的的OS/360MFTOS/360MFT（具有固定任務(wù)數(shù)的多（具有固定任務(wù)數(shù)的多道程序系統(tǒng)）采用了這種固定分區(qū)的方法。道程序系統(tǒng)）采用了這種固定分區(qū)的方法。422022-5-244.3.3 動態(tài)分區(qū)分配動態(tài)分區(qū)分配n固定分區(qū)存儲管理中的固定分區(qū)存儲管理中的“固定固定”有兩層含義，有兩層含義，一是分區(qū)數(shù)目固定，一是每個分區(qū)的尺寸固定。一是分區(qū)數(shù)目固定，一是每個分區(qū)的尺寸固定。采用這種內(nèi)存管理技術(shù)時，分配出去的分區(qū)總可采用這種內(nèi)存管理技術(shù)時，分配出去的分區(qū)總可能會有一部分成為內(nèi)部碎片而浪費(fèi)掉。究其原因，能會有一

32、部分成為內(nèi)部碎片而浪費(fèi)掉。究其原因，是因為進(jìn)入分區(qū)的作業(yè)大小，不可能剛好等于該是因為進(jìn)入分區(qū)的作業(yè)大小，不可能剛好等于該分區(qū)的尺寸。那么能否不事先劃分好分區(qū)，而是分區(qū)的尺寸。那么能否不事先劃分好分區(qū)，而是按照進(jìn)入作業(yè)的相對地址空間的大小來分配存儲，按照進(jìn)入作業(yè)的相對地址空間的大小來分配存儲，從而避免固定式分區(qū)所產(chǎn)生的存儲浪費(fèi)，這實際從而避免固定式分區(qū)所產(chǎn)生的存儲浪費(fèi)，這實際上就是上就是可變分區(qū)可變分區(qū)（動態(tài)分區(qū)）（動態(tài)分區(qū)）存儲管理考慮問題存儲管理考慮問題的出發(fā)點。的出發(fā)點。432022-5-24n動態(tài)分區(qū)存儲管理的基本思想是：動態(tài)分區(qū)存儲管理的基本思想是：在作業(yè)要求裝入內(nèi)存儲器時，如果當(dāng)在作

33、業(yè)要求裝入內(nèi)存儲器時，如果當(dāng)時內(nèi)存儲器中有足夠的存儲空間滿足時內(nèi)存儲器中有足夠的存儲空間滿足該作業(yè)的需求，那么就劃分出一個與該作業(yè)的需求，那么就劃分出一個與作業(yè)相對地址空間同樣大小的分區(qū)分作業(yè)相對地址空間同樣大小的分區(qū)分配給它。配給它。442022-5-24452022-5-24n上圖是動態(tài)分區(qū)存儲管理思想的示意圖。上圖是動態(tài)分區(qū)存儲管理思想的示意圖。n圖圖(a)是系統(tǒng)維持的后備作業(yè)隊列，作業(yè)是系統(tǒng)維持的后備作業(yè)隊列，作業(yè)A需要內(nèi)存需要內(nèi)存15KB，作業(yè)作業(yè)B需要需要20KB，作業(yè)，作業(yè)C需要需要10KB，等等；，等等；n圖圖(b)表示系統(tǒng)初啟時的情形，整個系統(tǒng)里因為沒有作業(yè)運(yùn)表示系統(tǒng)初啟時的

34、情形，整個系統(tǒng)里因為沒有作業(yè)運(yùn)行，因此用戶區(qū)就是一個空閑分區(qū)；行，因此用戶區(qū)就是一個空閑分區(qū)；n圖圖(c)表示將作業(yè)表示將作業(yè)A裝入內(nèi)存時，為它劃分了一個分區(qū)，尺裝入內(nèi)存時，為它劃分了一個分區(qū)，尺寸為寸為15KB，此時的用戶區(qū)被分為兩個分區(qū)，一個是已經(jīng)分，此時的用戶區(qū)被分為兩個分區(qū)，一個是已經(jīng)分配的，一個是空閑區(qū)；配的，一個是空閑區(qū)；n圖圖(d)表示將作業(yè)表示將作業(yè)B裝入內(nèi)存時，為它劃分了一個分區(qū)，尺裝入內(nèi)存時，為它劃分了一個分區(qū)，尺寸為寸為20KB，此時的用戶區(qū)被分為三個分區(qū)；，此時的用戶區(qū)被分為三個分區(qū)；n圖圖(e) 表示將作業(yè)表示將作業(yè)C裝入內(nèi)存時，為它劃分了一個分區(qū)，尺裝入內(nèi)存時，為它

35、劃分了一個分區(qū)，尺寸為寸為10KB，此時的用戶區(qū)被分為四個分區(qū)。，此時的用戶區(qū)被分為四個分區(qū)。由此可見，動由此可見，動態(tài)分區(qū)存儲管理中的態(tài)分區(qū)存儲管理中的“動態(tài)動態(tài)”也有兩層含義，一是分區(qū)的也有兩層含義，一是分區(qū)的數(shù)目隨進(jìn)入作業(yè)的多少可變，一是分區(qū)的邊界劃分隨作業(yè)數(shù)目隨進(jìn)入作業(yè)的多少可變，一是分區(qū)的邊界劃分隨作業(yè)的需求可變。的需求可變。462022-5-24n由于實施動態(tài)分區(qū)存儲管理時，分區(qū)的劃分是按由于實施動態(tài)分區(qū)存儲管理時，分區(qū)的劃分是按照進(jìn)入作業(yè)的尺寸進(jìn)行的，因此在這個分區(qū)里不照進(jìn)入作業(yè)的尺寸進(jìn)行的，因此在這個分區(qū)里不會出現(xiàn)內(nèi)部碎片。這就是說，動態(tài)分區(qū)存儲管理會出現(xiàn)內(nèi)部碎片。這就是說，動

36、態(tài)分區(qū)存儲管理消滅了內(nèi)部碎片，消滅了內(nèi)部碎片，不會出現(xiàn)由于內(nèi)部碎片不會出現(xiàn)由于內(nèi)部碎片而引起而引起的存儲浪費(fèi)現(xiàn)象。的存儲浪費(fèi)現(xiàn)象。472022-5-24動態(tài)分區(qū)動態(tài)分區(qū) n動態(tài)分區(qū)存儲管理方式是在作業(yè)要求裝入主動態(tài)分區(qū)存儲管理方式是在作業(yè)要求裝入主存時，根據(jù)作業(yè)的大小動態(tài)地劃分分區(qū)，使存時，根據(jù)作業(yè)的大小動態(tài)地劃分分區(qū)，使分區(qū)的大小正好適應(yīng)作業(yè)的要求。各分區(qū)的分區(qū)的大小正好適應(yīng)作業(yè)的要求。各分區(qū)的大小是不定的，主存中分區(qū)的數(shù)目也是不定大小是不定的，主存中分區(qū)的數(shù)目也是不定的。的。n動態(tài)分區(qū)存儲管理方式必須解決三個問題：動態(tài)分區(qū)存儲管理方式必須解決三個問題：u一是分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)。一是分

37、區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)。u二是分區(qū)的分配算法。二是分區(qū)的分配算法。u三是分區(qū)的分配和回收。三是分區(qū)的分配和回收。482022-5-241采用的數(shù)據(jù)結(jié)構(gòu)采用的數(shù)據(jù)結(jié)構(gòu) n為了實現(xiàn)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)為了實現(xiàn)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用來記錄內(nèi)存的使用情況。的數(shù)據(jù)結(jié)構(gòu)，用來記錄內(nèi)存的使用情況。比如空閑分區(qū)的情況，為作業(yè)分配內(nèi)存空比如空閑分區(qū)的情況，為作業(yè)分配內(nèi)存空間提供依據(jù)。常用的有空閑分區(qū)表和空閑間提供依據(jù)。常用的有空閑分區(qū)表和空閑分區(qū)鏈。分區(qū)鏈。492022-5-241. 采用的數(shù)據(jù)結(jié)構(gòu)采用的數(shù)據(jù)結(jié)構(gòu) 自由分區(qū)表 起始地址 大小 作業(yè)號 40K 55K 0 95K 10K

38、 1 210K 150K 2 ： ： ： 已使用分區(qū)表 OS 作業(yè) 0 40K 作業(yè) 0 作業(yè) 2 80 內(nèi)存 60K 40K 95K 105K 210K 150K 360K 起始地址 大小 105K 40K 150K 60K 360K 80K ： ： 40K 80 60K 自由分區(qū)鏈 根據(jù)作業(yè)對內(nèi)存空間根據(jù)作業(yè)對內(nèi)存空間的申請來劃分主存區(qū)的申請來劃分主存區(qū)域，區(qū)域的域，區(qū)域的大小可變大小可變、位置可變位置可變、數(shù)量也數(shù)量也可變可變 描述已被分配的區(qū)域描述已被分配的區(qū)域 描述內(nèi)存中的自由區(qū)域描述內(nèi)存中的自由區(qū)域 為每一個為每一個自由分區(qū)自由分區(qū)設(shè)置一設(shè)置一個個鏈接鏈接指針來指向下一個指針來指向

39、下一個自由分區(qū)，使所有的自由自由分區(qū)，使所有的自由分區(qū)形成一個鏈表分區(qū)形成一個鏈表 1502022-5-241采用的數(shù)據(jù)結(jié)構(gòu)采用的數(shù)據(jù)結(jié)構(gòu) n空閑分區(qū)表。記錄主存中空閑分區(qū)的情況，空閑分區(qū)表。記錄主存中空閑分區(qū)的情況，包括空閑分區(qū)序號、起始地址和大小。為包括空閑分區(qū)序號、起始地址和大小。為了便于處理，一般情況下空閑分區(qū)表中的了便于處理，一般情況下空閑分區(qū)表中的空閑分區(qū)記錄以地址遞增的順序排列?？臻e分區(qū)記錄以地址遞增的順序排列。512022-5-24n空閑分區(qū)鏈空閑分區(qū)鏈在每個分區(qū)的起始部分，設(shè)置一些用于控制分區(qū)分在每個分區(qū)的起始部分，設(shè)置一些用于控制分區(qū)分配的信息，以及用于鏈接各分區(qū)的前向指針

40、，在分配的信息，以及用于鏈接各分區(qū)的前向指針，在分區(qū)尾部設(shè)置一個后向指針，這樣將所有的空閑分區(qū)區(qū)尾部設(shè)置一個后向指針，這樣將所有的空閑分區(qū)鏈接成雙向鏈表。也就是說，每個空閑分區(qū)中，除鏈接成雙向鏈表。也就是說，每個空閑分區(qū)中，除了存放下一個空閑區(qū)起址了存放下一個空閑區(qū)起址next外，還存放它的上一外，還存放它的上一個空閑區(qū)起址（個空閑區(qū)起址（prior）的信息，如圖）的信息，如圖(a)所示。這樣，所示。這樣，通過空閑區(qū)的雙向鏈表，就可以方便地由通過空閑區(qū)的雙向鏈表，就可以方便地由next找到找到一個空閑區(qū)的下一個空閑區(qū)，也可以由一個空閑區(qū)的下一個空閑區(qū)，也可以由prior找到一找到一個空閑區(qū)的上

41、一個空閑區(qū)。個空閑區(qū)的上一個空閑區(qū)。522022-5-24532022-5-242分區(qū)分配算法分區(qū)分配算法 n（1）首次適應(yīng)分配算法（）首次適應(yīng)分配算法（FF） n（2）循環(huán)首次適應(yīng)分配算法（）循環(huán)首次適應(yīng)分配算法（NF）n（3）最優(yōu)適應(yīng)分配算法（）最優(yōu)適應(yīng)分配算法（BF） n（4）最壞適應(yīng)分配算法（）最壞適應(yīng)分配算法（WF） n（5）快速適應(yīng)分配算法（）快速適應(yīng)分配算法（QF）542022-5-24空閑區(qū)表或隊列的排序空閑區(qū)表或隊列的排序n按空閑區(qū)按空閑區(qū)首址首址遞增的次序歸類組織空閑區(qū)表遞增的次序歸類組織空閑區(qū)表或空閑區(qū)隊列或空閑區(qū)隊列n按空閑區(qū)按空閑區(qū)大小大小的遞增或遞減次序組織空閑區(qū)的

42、遞增或遞減次序組織空閑區(qū)表或隊列表或隊列 552022-5-24(1)(1)首次適應(yīng)法首次適應(yīng)法n要求空閑區(qū)按要求空閑區(qū)按首址遞增的次序組織的次序組織空閑區(qū)表（隊列）?？臻e區(qū)表（隊列）。 562022-5-24n分配：當(dāng)進(jìn)程申請大小為分配：當(dāng)進(jìn)程申請大小為SIZESIZE的內(nèi)存時，系的內(nèi)存時，系統(tǒng)從空閑區(qū)鏈的鏈?zhǔn)组_始查詢，直到首次找統(tǒng)從空閑區(qū)鏈的鏈?zhǔn)组_始查詢，直到首次找到等于或大于到等于或大于SIZESIZE的空閑區(qū)。從該區(qū)中劃出的空閑區(qū)。從該區(qū)中劃出大小為大小為SIZESIZE的分區(qū)分配給進(jìn)程，余下的部分的分區(qū)分配給進(jìn)程，余下的部分仍作為一個空閑區(qū)留在空閑區(qū)鏈中，但要修仍作為一個空閑區(qū)留在空

43、閑區(qū)鏈中，但要修改其首址和大小。改其首址和大小。n若找不到滿足要求的，則分配失敗，返回。若找不到滿足要求的，則分配失敗，返回。572022-5-24分析分析n注意：每次分配和回收后空閑區(qū)鏈都要按首址遞增的次序排序。首次適應(yīng)法的優(yōu)點：首次適應(yīng)法的優(yōu)點：n這種算法是盡可能地利用低地址空間，從這種算法是盡可能地利用低地址空間，從而保證高地址空間有較大的空閑區(qū)。而保證高地址空間有較大的空閑區(qū)。 582022-5-24n缺點缺點u容易產(chǎn)生過多的小地址碎片；降低了主存空間容易產(chǎn)生過多的小地址碎片；降低了主存空間利用率。利用率。u每次查找都是從低址開始，增加了查找的開銷每次查找都是從低址開始，增加了查找的開

44、銷 n改進(jìn)改進(jìn)u采用循環(huán)首次適應(yīng)算法。采用循環(huán)首次適應(yīng)算法。 592022-5-24（2 2）循環(huán)首次適應(yīng)算法）循環(huán)首次適應(yīng)算法n不是每次都從鏈?zhǔn)组_始找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到一個能滿足要求的空閑分區(qū)。n設(shè)置查尋指針；n循環(huán)查找方式n使內(nèi)存中的空閑分區(qū)分布得更均勻，減少了查找時的開銷，但會缺乏大的空閑分區(qū)。602022-5-24（3 3）最佳適應(yīng)法）最佳適應(yīng)法n所謂最佳就是每次為作業(yè)分配內(nèi)存時，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免大材小用。n要求按空閑區(qū)大小從小到大的次序組成空閑區(qū)鏈。612022-5-24n分配：當(dāng)進(jìn)程申請一個存儲區(qū)時，系統(tǒng)

45、從表頭開始查找，當(dāng)找到第一個滿足要求的空閑區(qū)時，停止查找，并且這個空閑區(qū)是最佳的空閑區(qū)。n分配和回收后要對空閑區(qū)表（隊列）重新排分配和回收后要對空閑區(qū)表（隊列）重新排序。序。622022-5-24分析分析優(yōu)點：優(yōu)點：n在系統(tǒng)中若存在一個與申請分區(qū)大小相等的空閑區(qū)，必定會被選中，而首次適應(yīng)法則不一定。n若系統(tǒng)中不存在與申請分區(qū)大小相等的空閑區(qū)，則選中的空閑區(qū)是滿足要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。632022-5-24分析分析缺點：缺點：n空閑區(qū)的大小一般與申請分區(qū)大小不相等，因此將其一分為二，留下來的空閑區(qū)一般情況下是很小的，以致無法使用。隨著時間的推移，系統(tǒng)中的小空閑區(qū)會越來越多，

46、從而造成存儲區(qū)的大量浪費(fèi)。642022-5-24（4 4）最壞適應(yīng)法）最壞適應(yīng)法n將作業(yè)申請大小與內(nèi)存中所有未分配區(qū)的大小進(jìn)行比較，直到找到最大的或等于作業(yè)空間的區(qū)分配給作業(yè)。n要求按空閑區(qū)大小從大到小的次序組成空閑區(qū)鏈。652022-5-24分析分析優(yōu)點：優(yōu)點：n優(yōu)先使用大的自由空間，在進(jìn)行分割后剩余空間還可以被使用。缺點：缺點：n大的自由空間無法保留給需要大空間的作業(yè)。662022-5-242.分區(qū)分配算法分區(qū)分配算法20K 80K 60K 40K 120K 20K 25K 60K 40K 120K 20K 80K 60K 40K 120K 20K 80K 5K 40K 120K 20K

47、80K 60K 40K 120K 20K 80K 60K 40K 65K 55K 作業(yè)空間 （a）最先適應(yīng)算法 （b）最佳適應(yīng)算法 （c）最壞適應(yīng)算法 672022-5-24n對于某一作業(yè)序列來說，某種算法能將該作業(yè)序列中所有作業(yè)安置完畢，那么我們說該算法對這一作業(yè)序列是合適的。n對于某一算法而言，如它不能立即滿足某一要求，而其它算法卻可以滿足此要求，則這一算法對該作業(yè)序列是不合適的。 682022-5-24舉例舉例n例1：有作業(yè)序列：作業(yè)A要求18K；作業(yè)B要求25K，作業(yè)C要求30K。系統(tǒng)中空閑區(qū)按兩種算法組成的空閑區(qū)隊列n經(jīng)分析可知：最佳適應(yīng)法對這個作業(yè)序列是合適的692022-5-24

48、練習(xí)練習(xí)n在動態(tài)分區(qū)式內(nèi)存管理中，傾向于優(yōu)先使用低址部分空閑區(qū)的算法是（），能使內(nèi)存空間中空閑區(qū)分布得較均勻的算法是（），每次分配時，把既能滿足要求，又是最小的空閑區(qū)分配給進(jìn)程的算法是（）。702022-5-24練習(xí)練習(xí)n最佳適應(yīng)算法的空白區(qū)是（）。A、按大小遞減順序連在一起B(yǎng)、按大小遞增順序連在一起C、按地址由小到大排列D、按地址由大到小排列n在固定分區(qū)分配中，每個分區(qū)的大小是（）。在固定分區(qū)分配中，每個分區(qū)的大小是（）。A、相同、相同 B、隨作業(yè)長度變化、隨作業(yè)長度變化C、可以不同但預(yù)先固定、可以不同但預(yù)先固定D、可以不同但根據(jù)作業(yè)長度固定、可以不同但根據(jù)作業(yè)長度固定712022-5-24

49、練習(xí)練習(xí)n某基于動態(tài)分區(qū)存儲管理的計算機(jī)，其主存容量為55Mb（初始為空），采用最佳適應(yīng)分配（Best Fit）算法，分配和釋放的順序為：分配15Mb，分配30Mb，釋放15Mb，分配8Mb，分配6Mb，此時主存中最大空閑分區(qū)的大小是（） (10年考研) A、7Mb B、9Mb C、10Mb D、15Mbn在以下存儲管理方案中，不適用于多道程序設(shè)計系統(tǒng)的是（）。A、單用戶連續(xù)分配 B、固定式分區(qū)分配C、可變式分區(qū)分配 D、頁式存儲管理722022-5-24（5 5）快速適應(yīng)法）快速適應(yīng)法n將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個空閑分區(qū)鏈表，這樣系統(tǒng)

50、中存在多個空閑分區(qū)鏈表，在內(nèi)存中設(shè)立一張管理索引表，該表的每一個表項對應(yīng)了一種空閑分區(qū)類型，并記錄了該類型空閑分區(qū)鏈表表頭的指針。n空閑分區(qū)的分類是根據(jù)進(jìn)程常用的空間大小進(jìn)行劃分的。在分配時根據(jù)進(jìn)程的長度，找到能容納它的最小空閑鏈表，取下第一塊進(jìn)行分配即可。 732022-5-24分析分析優(yōu)點：優(yōu)點：n該算法查找效率高，分配時不對任何分區(qū)產(chǎn)生分割，能保留大的分區(qū)，滿足對大空間的需求。缺點：缺點：n但分區(qū)歸還時算法復(fù)雜，系統(tǒng)開銷大，在分配空閑分區(qū)時以進(jìn)程為單位，也有一定的空間浪費(fèi)。742022-5-24(6)伙伴系統(tǒng)伙伴系統(tǒng)n固定分區(qū)和動態(tài)分區(qū)方式都有不足之處。固固定分區(qū)和動態(tài)分區(qū)方式都有不足之

51、處。固定分區(qū)方式限制了活動進(jìn)程的數(shù)目，當(dāng)進(jìn)程定分區(qū)方式限制了活動進(jìn)程的數(shù)目，當(dāng)進(jìn)程大小與空閑分區(qū)不匹配時，內(nèi)存空間利用率大小與空閑分區(qū)不匹配時，內(nèi)存空間利用率低。動態(tài)分區(qū)方式算法復(fù)雜，回收空閑分區(qū)低。動態(tài)分區(qū)方式算法復(fù)雜，回收空閑分區(qū)時需要進(jìn)行分區(qū)合并等，系統(tǒng)開銷較大。伙時需要進(jìn)行分區(qū)合并等，系統(tǒng)開銷較大?；锇橄到y(tǒng)方式是對以上兩種內(nèi)存方式的一種折伴系統(tǒng)方式是對以上兩種內(nèi)存方式的一種折衷方案。衷方案。752022-5-24 (6)伙伴系統(tǒng)伙伴系統(tǒng)n伙伴系統(tǒng)規(guī)定，無論已分配分區(qū)或空閑分區(qū)，伙伴系統(tǒng)規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為其大小均為2的的K次冪，次冪，K為整數(shù)，為整數(shù)，nlkm,k

52、m,其中其中：2l表示分配的最小分區(qū)的大小，表示分配的最小分區(qū)的大小，2m表示分配的最大分區(qū)的大小，表示分配的最大分區(qū)的大小，762022-5-24 4.3.4伙伴關(guān)系伙伴關(guān)系n假設(shè)存儲空間的大小為假設(shè)存儲空間的大小為2M, M是正整數(shù)?；锇橄到y(tǒng)是正整數(shù)?；锇橄到y(tǒng)得名于它的每一個塊都有一個對應(yīng)的同樣大小的得名于它的每一個塊都有一個對應(yīng)的同樣大小的 “伙伴伙伴”塊。對于一個塊。對于一個N字節(jié)的存儲請求（字節(jié)的存儲請求（N2M），），伙伴系統(tǒng)首先確定使得伙伴系統(tǒng)首先確定使得2k的最小的最小k值。若在空閑區(qū)表值。若在空閑區(qū)表中能找到中能找到2k大小的空閑塊，則進(jìn)行分配，否則就找大小的空閑塊，則進(jìn)行分

53、配，否則就找一個更大的空閑塊，把它均分成兩半，不斷重復(fù)這一個更大的空閑塊，把它均分成兩半，不斷重復(fù)這個分割過程，直到生成個分割過程，直到生成2k大小的空閑塊，并把它分大小的空閑塊，并把它分配出去，因為是均分兩半，所以還會有一個配出去，因為是均分兩半，所以還會有一個2k大小大小的空閑塊，即其的空閑塊，即其“伙伴伙伴”塊?；厥盏臅r候如果其塊?；厥盏臅r候如果其“伙伴伙伴”塊是空閑的就合并成一個大的空閑塊，如塊是空閑的就合并成一個大的空閑塊，如果此空閑塊的果此空閑塊的“伙伴伙伴”塊仍是空閑的，則繼續(xù)合并，塊仍是空閑的，則繼續(xù)合并，直至其直至其“伙伴伙伴”塊不是空閑的。塊不是空閑的。772022-5-2

54、4 (7)哈希算法哈希算法n利用哈希快速查找的優(yōu)點，以及空閑分區(qū)在利用哈?？焖俨檎业膬?yōu)點，以及空閑分區(qū)在可利用空間表中的分布規(guī)律，建立哈希函數(shù)，可利用空間表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，該表的每一個表項記錄了一個對應(yīng)的空閑分該表的每一個表項記錄了一個對應(yīng)的空閑分區(qū)鏈表表頭指針。當(dāng)進(jìn)行空閑分區(qū)分配時，區(qū)鏈表表頭指針。當(dāng)進(jìn)行空閑分區(qū)分配時，根據(jù)所需空閑分區(qū)的大小，通過哈希函數(shù)計根據(jù)所需空閑分區(qū)的大小，通過哈希函數(shù)計算，得到相應(yīng)的空閑分區(qū)鏈表，實現(xiàn)最佳分算，得到相應(yīng)的空閑分區(qū)鏈表，實現(xiàn)最佳分配策略。配策略。782022-5

55、-243. 3. 分區(qū)的分配分區(qū)的分配在采用分區(qū)存儲管理的系統(tǒng)中，系統(tǒng)初啟后。除操作系統(tǒng)占用一個分區(qū)外，其余存儲區(qū)為一個大的空閑區(qū)。 分區(qū)的分配是指系統(tǒng)根據(jù)用戶的請求，在空閑區(qū)表或空閑區(qū)隊列中尋找一個滿足用戶要求的空閑區(qū)，把這個空閑區(qū)分配給用戶。 當(dāng)用戶要求一個大小為SIZE的存儲空間時，系統(tǒng)查詢空閑區(qū)鏈（表），找一個大于或等于SIZE的空閑區(qū)。792022-5-24分配時的三種情況分配時的三種情況n其一是系統(tǒng)中無滿足要求的空閑區(qū)，則分配失敗。n其二是空閑區(qū)大小與SIZE相等，則修改空閑區(qū)表相應(yīng)表目，向用戶返回該空閑區(qū)首址，表示此空閑區(qū)已分給了要求的用戶。802022-5-24 n其三是空閑區(qū)

56、大于SIZE，這時將空閑區(qū)一分為二。將一個空閑區(qū)分成二部分有兩種辦法：一是從空閑區(qū)的上部開始劃出SIZE大小的空閑區(qū)給用戶；二是從空閑區(qū)的底部開始向上劃出SIZE大小的空閑區(qū)給用戶。一般常采用第二種辦法，因為這樣劃分時，余下的部分在空閑區(qū)表中的首地址不變，只需要修改一下大小就行了。812022-5-24 822022-5-24n主存的分配過程如下：主存的分配過程如下：u首先初始化空閑分區(qū)鏈（首先初始化空閑分區(qū)鏈（1個記錄），整個用戶個記錄），整個用戶區(qū)為一個空閑區(qū)，在空閑分區(qū)鏈（表）中填入?yún)^(qū)為一個空閑區(qū)，在空閑分區(qū)鏈（表）中填入用戶區(qū)的始址和大小。用戶區(qū)的始址和大小。u其次，從作業(yè)隊列中取出隊

57、首作業(yè)，在空閑分其次，從作業(yè)隊列中取出隊首作業(yè)，在空閑分區(qū)表中找一個不小于作業(yè)的空閑區(qū)，裝入作業(yè)，區(qū)表中找一個不小于作業(yè)的空閑區(qū)，裝入作業(yè)，在已分分區(qū)表中增加一個記錄，填上作業(yè)所占在已分分區(qū)表中增加一個記錄，填上作業(yè)所占分區(qū)的序號、始址、大小、作業(yè)名，并修改空分區(qū)的序號、始址、大小、作業(yè)名，并修改空閑分區(qū)表相應(yīng)記錄的始址和大小；若找不到一閑分區(qū)表相應(yīng)記錄的始址和大小；若找不到一個空閑區(qū)，則顯示主存不足的信息，刪除該作個空閑區(qū)，則顯示主存不足的信息，刪除該作業(yè)或把作業(yè)放到隊尾，等待大的空閑區(qū)。業(yè)或把作業(yè)放到隊尾，等待大的空閑區(qū)。u然后，再分配下一個作業(yè)，直到所有作業(yè)分配然后，再分配下一個作業(yè)，直

58、到所有作業(yè)分配完畢。完畢。832022-5-24分區(qū)的回收分區(qū)的回收 當(dāng)某個進(jìn)程釋放某存儲區(qū)時，系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰，若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)中去，否則把釋放區(qū)作為一個空閑區(qū)插入到空閑區(qū)表的適當(dāng)位置。842022-5-24釋放區(qū)與空閑區(qū)相鄰的四種情況釋放區(qū)與空閑區(qū)相鄰的四種情況852022-5-24說明說明n釋放區(qū)與前空閑區(qū)相鄰：將釋放區(qū)與前空閑區(qū)合并為一個空閑區(qū)。其首址仍為前空閑區(qū)首址，大小為釋放區(qū)大小與空閑區(qū)大小之和。n釋放區(qū)與后空閑區(qū)相鄰：則把釋放區(qū)合并到后空閑區(qū)，首地址為釋放區(qū)首地址，大小為二者大小之和。n釋放區(qū)與前后兩個空閑區(qū)相鄰：將這三個區(qū)合為一個空閑區(qū)，其首址為前空閑區(qū)首址，大小為這三個區(qū)大小之和，并取消原后空閑區(qū)表項。n釋放區(qū)不與任何空閑區(qū)相鄰：將釋放區(qū)作為一個空閑區(qū)，將其大小和首址插入到空閑區(qū)鏈的適當(dāng)位置。862022-5-24練習(xí)練習(xí)n在可變式分區(qū)分配方案中，某一作業(yè)完成后，系統(tǒng)收回其內(nèi)存空間并與相鄰空閑區(qū)合并，為此需修改空閑區(qū)表，造成空閑區(qū)數(shù)減1的情況是（）。A、無上鄰空閑區(qū)也無下鄰空閑區(qū)B、有上鄰空閑區(qū)但無下鄰空閑區(qū)C、有下鄰空閑區(qū)但無上鄰空閑區(qū)D、有上鄰空閑區(qū)也有下鄰空閑區(qū)872022-5-24 4.3.6動態(tài)可重定位分區(qū)分配動態(tài)可重定位分區(qū)分配 n在連續(xù)分配中，必須把一個系統(tǒng)或用戶程序在連續(xù)分配中，必須把一個系統(tǒng)或用