os04-1

1、第四章 存儲(chǔ)器管理,4.1 程序的裝入和鏈接 4.2 連續(xù)分配方式 4.3 基本分頁存儲(chǔ)管理方式 4.4 基本分段存儲(chǔ)管理方式 4.5 虛擬存儲(chǔ)器的基本概念 4.6 請(qǐng)求分頁存儲(chǔ)管理方式 4.7 頁面置換算法 4.8 請(qǐng)求分段存儲(chǔ)管理方式,第四章 存儲(chǔ)器管理,存儲(chǔ)器的層次結(jié)構(gòu),,,容量、價(jià)格,速度、價(jià)格,第四章 存儲(chǔ)器管理,存儲(chǔ)器管理的目的主存的分配和管理：當(dāng)用戶需要內(nèi)存時(shí),系統(tǒng)為之分配相應(yīng)的存儲(chǔ)

2、空間；不需要時(shí)，及時(shí)回收，以供其它用戶使用。提高主存儲(chǔ)器的利用率：不僅能使多道程序動(dòng)態(tài)地共享主存，提高主存利用率，最好還能共享主存中某個(gè)區(qū)域的信息。,第四章 存儲(chǔ)器管理,存儲(chǔ)器管理的目的主存的分配和管理：當(dāng)用戶需要內(nèi)存時(shí),系統(tǒng)為之分配相應(yīng)的存儲(chǔ)空間；不需要時(shí)，及時(shí)回收，以供其它用戶使用。提高主存儲(chǔ)器的利用率：不僅能使多道程序動(dòng)態(tài)地共享主存，提高主存利用率，最好還能共享主存中某個(gè)區(qū)域的信息。,第四章 存儲(chǔ)器管理,存儲(chǔ)器管理的目的

3、“擴(kuò)充”主存容量：為用戶提供比主存物理空間大得多的地址空間，以至使用戶感覺他的作業(yè)是在這樣一個(gè)大的存儲(chǔ)器中運(yùn)行。存儲(chǔ)保護(hù)：確保多道程序都在各自分配到存儲(chǔ)區(qū)域內(nèi)操作，互不干擾，防止一道程序破壞其它作業(yè)或系統(tǒng)文件的信息。,第四章 存儲(chǔ)器管理,存儲(chǔ)器管理的目的“擴(kuò)充”主存容量：為用戶提供比主存物理空間大得多的地址空間，以至使用戶感覺他的作業(yè)是在這樣一個(gè)大的存儲(chǔ)器中運(yùn)行。存儲(chǔ)保護(hù)：確保多道程序都在各自分配到存儲(chǔ)區(qū)域內(nèi)操作，互不干擾，防

4、止一道程序破壞其它作業(yè)或系統(tǒng)文件的信息。,第四章 存儲(chǔ)器管理,基本概念邏輯地址（相對(duì)地址，虛地址） ：用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對(duì)地址的形式，其首地址為0，其余指令中的地址都相對(duì)于首地址而編址。不能用邏輯地址在內(nèi)存中讀取信息。物理地址（絕對(duì)地址，實(shí)地址）：內(nèi)存中存儲(chǔ)單元的地址，可直接尋址。,第四章 存儲(chǔ)器管理,基本概念邏輯地址（相對(duì)地址，虛地址） ：用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代

5、碼通常采用相對(duì)地址的形式，其首地址為0，其余指令中的地址都相對(duì)于首地址而編址。不能用邏輯地址在內(nèi)存中讀取信息。物理地址（絕對(duì)地址，實(shí)地址）：內(nèi)存中存儲(chǔ)單元的地址，可直接尋址。,第四章 存儲(chǔ)器管理,基本概念地址空間程序用來訪問信息所用地址單元的集合邏輯（相對(duì)）地址的集合由編譯程序生成存儲(chǔ)空間主存中物理單元的集合物理（絕對(duì)）地址的集合由裝配程序等生成,第四章 存儲(chǔ)器管理,基本概念地址空間程序用來訪問信息所用地址單元

6、的集合邏輯（相對(duì)）地址的集合由編譯程序生成存儲(chǔ)空間主存中物理單元的集合物理（絕對(duì)）地址的集合由裝配程序等生成,地址映射,Load A 200 3456 。 。,1200,Load A data1data1 3456,源程序,,Load A 200 3456,0,100,200,編譯連接,邏輯地址空間,,,,BA=1000,地址空間 存儲(chǔ)空間,第四章 存儲(chǔ)器管理,基

7、本概念定位（存儲(chǔ)分配）：為具體的程序和數(shù)據(jù)等分配存儲(chǔ)單元或存儲(chǔ)區(qū)工作。映射：把邏輯地址轉(zhuǎn)換為相應(yīng)的物理地址的過程。,第四章 存儲(chǔ)器管理,基本概念定位（存儲(chǔ)分配）：為具體的程序和數(shù)據(jù)等分配存儲(chǔ)單元或存儲(chǔ)區(qū)工作。映射：把邏輯地址轉(zhuǎn)換為相應(yīng)的物理地址的過程。,4.1 程序的裝入和鏈接,對(duì)用戶程序的處理步驟,4.1 程序的裝入和鏈接,程序的裝入絕對(duì)裝入方式編譯程序產(chǎn)生絕對(duì)地址的目標(biāo)代碼，即代碼的邏輯地址和物理地址相同裝入程序

8、按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存，不進(jìn)行地址的修改只適用于單道程序環(huán)境,4.1 程序的裝入和鏈接,程序的裝入絕對(duì)裝入方式編譯程序產(chǎn)生絕對(duì)地址的目標(biāo)代碼，即代碼的邏輯地址和物理地址相同裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存，不進(jìn)行地址的修改只適用于單道程序環(huán)境,4.1 程序的裝入和鏈接,程序的裝入絕對(duì)裝入方式編譯程序產(chǎn)生絕對(duì)地址的目標(biāo)代碼，即代碼的邏輯地址和物理地址相同裝入程序按照裝入模塊中的地址，將

9、程序和數(shù)據(jù)裝入內(nèi)存，不進(jìn)行地址的修改只適用于單道程序環(huán)境,4.1 程序的裝入和鏈接,程序的裝入可重定位裝入方式目標(biāo)模塊的起始地址從0開始，程序中其他地址相對(duì)于起始地址計(jì)算，裝入程序根據(jù)內(nèi)存的當(dāng)前情況，將裝入模塊裝入內(nèi)存的適當(dāng)位置。,作業(yè)裝入內(nèi)存時(shí)的情況,4.1 程序的裝入和鏈接,程序的裝入可重定位裝入方式重定位：在裝入時(shí)對(duì)目標(biāo)程序中指令和數(shù)據(jù)地址的修改過程?；蛘哒f：把作業(yè)地址空間中使用的邏輯地址變換成內(nèi)存空間中的物理地址的過程

10、。又稱地址映射。地址變換在裝入時(shí)一次完成，以后不再改變，故稱為靜態(tài)重定位。,4.1 程序的裝入和鏈接,程序的裝入可重定位裝入方式重定位：在裝入時(shí)對(duì)目標(biāo)程序中指令和數(shù)據(jù)地址的修改過程稱?；蛘哒f：把作業(yè)地址空間中使用的邏輯地址變換成內(nèi)存空間中的物理地址的過程。又稱地址映射。地址變換在裝入時(shí)一次完成，以后不再改變，故稱為靜態(tài)重定位。,4.1 程序的裝入和鏈接,程序的裝入可重定位裝入方式優(yōu)點(diǎn)：無需增加硬件地址變換機(jī)構(gòu)；實(shí)現(xiàn)簡單；適用

11、于多道程序環(huán)境。缺點(diǎn)：不允許程序運(yùn)行時(shí)在內(nèi)存中移動(dòng)位置；程序在存儲(chǔ)空間中只能連續(xù)分配；多個(gè)用戶難以共享存于內(nèi)存中的同一程序。,4.1 程序的裝入和鏈接,程序的裝入可重定位裝入方式優(yōu)點(diǎn)：無需增加硬件地址變換機(jī)構(gòu)；實(shí)現(xiàn)簡單；適用于多道程序環(huán)境。缺點(diǎn)：不允許程序運(yùn)行時(shí)在內(nèi)存中移動(dòng)位置；程序在存儲(chǔ)空間中只能連續(xù)分配；多個(gè)用戶難以共享存于內(nèi)存中的同一程序。,4.1 程序的裝入和鏈接,程序的裝入動(dòng)態(tài)運(yùn)行時(shí)裝入方式裝入程序把裝入模塊裝入內(nèi)

12、存后，不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。裝入內(nèi)存后的所有地址都仍是相對(duì)地址。允許程序在內(nèi)存中移動(dòng)；需要重定位寄存器的支持優(yōu)點(diǎn)：可對(duì)內(nèi)存進(jìn)行非連續(xù)分配；提供了實(shí)現(xiàn)虛存的基礎(chǔ)；有利于程序段的共享。,4.1 程序的裝入和鏈接,程序的裝入動(dòng)態(tài)運(yùn)行時(shí)裝入方式裝入程序把裝入模塊裝入內(nèi)存后，不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。

13、裝入內(nèi)存后的所有地址都仍是相對(duì)地址。允許程序在內(nèi)存中移動(dòng)；需要重定位寄存器的支持優(yōu)點(diǎn)：可對(duì)內(nèi)存進(jìn)行非連續(xù)分配；提供了實(shí)現(xiàn)虛存的基礎(chǔ)；有利于程序段的共享。,4.1 程序的裝入和鏈接,程序的裝入動(dòng)態(tài)運(yùn)行時(shí)裝入方式裝入程序把裝入模塊裝入內(nèi)存后，不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。裝入內(nèi)存后的所有地址都仍是相對(duì)地址。允許程序在內(nèi)存中移動(dòng)；需要重定位寄存器的支持優(yōu)點(diǎn)：可對(duì)

14、內(nèi)存進(jìn)行非連續(xù)分配；提供了實(shí)現(xiàn)虛存的基礎(chǔ)；有利于程序段的共享。,4.1 程序的裝入和鏈接,程序的裝入動(dòng)態(tài)運(yùn)行時(shí)裝入方式裝入程序把裝入模塊裝入內(nèi)存后，不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。裝入內(nèi)存后的所有地址都仍是相對(duì)地址。允許程序在內(nèi)存中移動(dòng)；需要重定位寄存器的支持優(yōu)點(diǎn)：可對(duì)內(nèi)存進(jìn)行非連續(xù)分配；提供了實(shí)現(xiàn)虛存的基礎(chǔ)；有利于程序段的共享。,4.1 程序的裝入和鏈接,程序的裝

15、入動(dòng)態(tài)運(yùn)行時(shí)裝入方式裝入程序把裝入模塊裝入內(nèi)存后，不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。裝入內(nèi)存后的所有地址都仍是相對(duì)地址。允許程序在內(nèi)存中移動(dòng)；需要重定位寄存器的支持優(yōu)點(diǎn)：可對(duì)內(nèi)存進(jìn)行非連續(xù)分配；提供了實(shí)現(xiàn)虛存的基礎(chǔ)；有利于程序段的共享。,4.1 程序的裝入和鏈接,程序的鏈接靜態(tài)鏈接方式在程序運(yùn)行之前，先將各目標(biāo)模塊以及所需的庫函數(shù)，鏈接成一個(gè)完整的裝配模塊。在將

16、這幾個(gè)目標(biāo)模塊裝配成一個(gè)裝入模塊時(shí)，須解決以下兩個(gè)問題： (1) 對(duì)相對(duì)地址進(jìn)行修改。 (2) 變換外部調(diào)用符號(hào)。,4.1 程序的裝入和鏈接,程序的鏈接靜態(tài)鏈接方式在程序運(yùn)行之前，先將各目標(biāo)模塊以及所需的庫函數(shù)，鏈接成一個(gè)完整的裝配模塊。在將這幾個(gè)目標(biāo)模塊裝配成一個(gè)裝入模塊時(shí)，須解決以下兩個(gè)問題： (1) 對(duì)相對(duì)地址進(jìn)行修改。 (2) 變換外部調(diào)用符號(hào)。,4.1 程序的裝入和鏈接,程序的鏈接裝入時(shí)

17、動(dòng)態(tài)鏈接方式采用邊裝入邊鏈接的方式優(yōu)點(diǎn)：便于修改和更新；便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。 缺點(diǎn)：程序每次要運(yùn)行的模塊可能不相同，但無法知道本次要運(yùn)行哪些模塊，故只能將所有可能要運(yùn)行的模塊都全部裝入內(nèi)存并鏈接。,4.1 程序的裝入和鏈接,程序的鏈接裝入時(shí)動(dòng)態(tài)鏈接方式采用邊裝入邊鏈接的方式優(yōu)點(diǎn)：便于修改和更新；便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。 缺點(diǎn)：程序每次要運(yùn)行的模塊可能不相同，但無法知道本次要運(yùn)行哪些模塊，故只能將所有可能要運(yùn)行的模塊

18、都全部裝入內(nèi)存并鏈接。,4.1 程序的裝入和鏈接,程序的鏈接裝入時(shí)動(dòng)態(tài)鏈接方式采用邊裝入邊鏈接的方式優(yōu)點(diǎn)：便于修改和更新；便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。 缺點(diǎn)：程序每次要運(yùn)行的模塊可能不相同，但無法知道本次要運(yùn)行哪些模塊，故只能將所有可能要運(yùn)行的模塊都全部裝入內(nèi)存并鏈接。,4.1 程序的裝入和鏈接,程序的鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接方式對(duì)某些目標(biāo)模塊的鏈接，在程序執(zhí)行中需要該模塊時(shí)，才對(duì)它進(jìn)行的鏈接。優(yōu)點(diǎn)：凡在執(zhí)行過程中未被用到的目標(biāo)模

19、塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。,4.1 程序的裝入和鏈接,程序的鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接方式對(duì)某些目標(biāo)模塊的鏈接，在程序執(zhí)行中需要該模塊時(shí)，才對(duì)它進(jìn)行的鏈接。優(yōu)點(diǎn)：凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。,4.2 連續(xù)分配方式,單一連續(xù)分配最簡單的一種存儲(chǔ)管理方式，但只能用于單用

20、戶、單任務(wù)的操作系統(tǒng)中。內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間， 提供給用戶使用。優(yōu)點(diǎn)：管理簡單，不要求專用的硬件支持；為防止破壞OS ，設(shè)置界限寄存器；易于實(shí)現(xiàn)。缺點(diǎn)：存儲(chǔ)器利用率低；信息不共享；CPU 利用率低，周轉(zhuǎn)時(shí)間長。,4.2 連續(xù)分配方式,單一連續(xù)分配最簡單的一種存儲(chǔ)管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)

21、兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間， 提供給用戶使用。優(yōu)點(diǎn)：管理簡單，不要求專用的硬件支持；為防止破壞OS ，設(shè)置界限寄存器；易于實(shí)現(xiàn)。缺點(diǎn)：存儲(chǔ)器利用率低；信息不共享；CPU 利用率低，周轉(zhuǎn)時(shí)間長。,4.2 連續(xù)分配方式,單一連續(xù)分配最簡單的一種存儲(chǔ)管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的

22、低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間， 提供給用戶使用。優(yōu)點(diǎn)：管理簡單，不要求專用的硬件支持；為防止破壞OS ，設(shè)置界限寄存器；易于實(shí)現(xiàn)。缺點(diǎn)：存儲(chǔ)器利用率低；信息不共享；CPU 利用率低，周轉(zhuǎn)時(shí)間長。,4.2 連續(xù)分配方式,單一連續(xù)分配最簡單的一種存儲(chǔ)管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，

23、 提供給用戶使用。優(yōu)點(diǎn)：管理簡單，不要求專用的硬件支持；為防止破壞OS ，設(shè)置界限寄存器；易于實(shí)現(xiàn)。缺點(diǎn)：存儲(chǔ)器利用率低；信息不共享；CPU 利用率低，周轉(zhuǎn)時(shí)間長。,4.2 連續(xù)分配方式,固定分區(qū)分配運(yùn)行多道程序的存儲(chǔ)管理方式。內(nèi)存用戶被劃分為若干個(gè)固定大小的區(qū)域，每個(gè)分區(qū)中只裝入一道作業(yè)。內(nèi)存利用率低。允許幾道作業(yè)并發(fā)。劃分分區(qū)的方法： 分區(qū)大小相等；分區(qū)大小不等。,4.2 連續(xù)分配方式,固定分區(qū)分配運(yùn)行多道程序

24、的存儲(chǔ)管理方式。內(nèi)存用戶被劃分為若干個(gè)固定大小的區(qū)域，每個(gè)分區(qū)中只裝入一道作業(yè)。內(nèi)存利用率低。允許幾道作業(yè)并發(fā)。劃分分區(qū)的方法： 分區(qū)大小相等；分區(qū)大小不等。,4.2 連續(xù)分配方式,固定分區(qū)分配運(yùn)行多道程序的存儲(chǔ)管理方式。內(nèi)存用戶被劃分為若干個(gè)固定大小的區(qū)域，每個(gè)分區(qū)中只裝入一道作業(yè)。內(nèi)存利用率低。允許幾道作業(yè)并發(fā)。劃分分區(qū)的方法： 分區(qū)大小相等；分區(qū)大小不等。,4.2 連續(xù)分配方式,固定分區(qū)分配運(yùn)行多道程序

25、的存儲(chǔ)管理方式。內(nèi)存用戶被劃分為若干個(gè)固定大小的區(qū)域，每個(gè)分區(qū)中只裝入一道作業(yè)。內(nèi)存利用率低。允許幾道作業(yè)并發(fā)。劃分分區(qū)的方法： 分區(qū)大小相等；分區(qū)大小不等。,4.2 連續(xù)分配方式,固定分區(qū)分配運(yùn)行多道程序的存儲(chǔ)管理方式。內(nèi)存用戶被劃分為若干個(gè)固定大小的區(qū)域，每個(gè)分區(qū)中只裝入一道作業(yè)。內(nèi)存利用率低。允許幾道作業(yè)并發(fā)。劃分分區(qū)的方法： 分區(qū)大小相等；分區(qū)大小不等。,4.2 連續(xù)分配方式,固定分區(qū)分配內(nèi)存分配分

26、區(qū)使用表：各表項(xiàng)包括每個(gè)分區(qū)的起始地址，大小和狀態(tài)。用戶程序需要裝入時(shí)，內(nèi)存分配程序檢索該表，找出一個(gè)能滿足要求尚未分配的分區(qū)，分配給該程序，并將其表項(xiàng)中的狀態(tài)置為“已分配”。若未找到大小足夠的分區(qū)，則拒絕為用戶程序分配內(nèi)存。,4.2 連續(xù)分配方式,固定分區(qū)分配內(nèi)存分配分區(qū)使用表：各表項(xiàng)包括每個(gè)分區(qū)的起始地址，大小和狀態(tài)。用戶程序需要裝入時(shí)，內(nèi)存分配程序檢索該表，找出一個(gè)能滿足要求尚未分配的分區(qū)，分配給該程序，并將其表項(xiàng)中的

27、狀態(tài)置為“已分配”。若未找到大小足夠的分區(qū)，則拒絕為用戶程序分配內(nèi)存。,4.2 連續(xù)分配方式,固定分區(qū)分配內(nèi)存分配分區(qū)使用表：各表項(xiàng)包括每個(gè)分區(qū)的起始地址，大小和狀態(tài)。用戶程序需要裝入時(shí)，內(nèi)存分配程序檢索該表，找出一個(gè)能滿足要求尚未分配的分區(qū)，分配給該程序，并將其表項(xiàng)中的狀態(tài)置為“已分配”。若未找到大小足夠的分區(qū)，則拒絕為用戶程序分配內(nèi)存。,4.2 連續(xù)分配方式,動(dòng)態(tài)分區(qū)分配（可變分區(qū)分配）按作業(yè)的實(shí)際大小來劃分分區(qū)，且

28、分區(qū)個(gè)數(shù)也是隨機(jī)的,實(shí)現(xiàn)多個(gè)作業(yè)對(duì)內(nèi)存的共享，進(jìn)一步提高內(nèi)存資源利用率分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表，一個(gè)空閑分區(qū)占一個(gè)表目，表目包括：分區(qū)序號(hào)、分區(qū)始址、分區(qū)大小空閑分區(qū)鏈。,4.2 連續(xù)分配方式,動(dòng)態(tài)分區(qū)分配（可變分區(qū)分配）按作業(yè)的實(shí)際大小來劃分分區(qū)，且分區(qū)個(gè)數(shù)也是隨機(jī)的,實(shí)現(xiàn)多個(gè)作業(yè)對(duì)內(nèi)存的共享，進(jìn)一步提高內(nèi)存資源利用率分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表，一個(gè)空閑分區(qū)占一個(gè)表目，表目包括：分區(qū)序號(hào)、分區(qū)始址、分區(qū)大小空

29、閑分區(qū)鏈。,,4.2 連續(xù)分配方式,動(dòng)態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配算法首次適應(yīng)算法（First Fit）把主存中所有空閑區(qū)按其物理地址遞增的次序排列。在為作業(yè)分配存儲(chǔ)空間時(shí)，從低址空閑區(qū)開始查找,直到找到第一個(gè)能滿足要求的空閑區(qū)后，從中劃出與請(qǐng)求的大小相等的存儲(chǔ)空間分配給作業(yè)，余下的空閑區(qū)仍留在空閑鏈中；優(yōu)先利用內(nèi)存中低址部分的空閑分區(qū)，保留了高址部分的大空閑區(qū)；低址部分不斷被分割，形成很多難以利用的碎片。,4.2

30、 連續(xù)分配方式,動(dòng)態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配算法首次適應(yīng)算法（First Fit）把主存中所有空閑區(qū)按其物理地址遞增的次序排列。在為作業(yè)分配存儲(chǔ)空間時(shí)，從低址空閑區(qū)開始查找,直到找到第一個(gè)能滿足要求的空閑區(qū)后，從中劃出與請(qǐng)求的大小相等的存儲(chǔ)空間分配給作業(yè)，余下的空閑區(qū)仍留在空閑鏈中；優(yōu)先利用內(nèi)存中低址部分的空閑分區(qū)，保留了高址部分的大空閑區(qū)；低址部分不斷被分割，形成很多難以利用的碎片。,4.2 連續(xù)分配方式,動(dòng)態(tài)分

31、區(qū)分配（可變分區(qū)分配）分區(qū)分配算法首次適應(yīng)算法（First Fit）把主存中所有空閑區(qū)按其物理地址遞增的次序排列。在為作業(yè)分配存儲(chǔ)空間時(shí)，從低址空閑區(qū)開始查找,直到找到第一個(gè)能滿足要求的空閑區(qū)后，從中劃出與請(qǐng)求的大小相等的存儲(chǔ)空間分配給作業(yè)，余下的空閑區(qū)仍留在空閑鏈中；優(yōu)先利用內(nèi)存中低址部分的空閑分區(qū)，保留了高址部分的大空閑區(qū)；低址部分不斷被分割，形成很多難以利用的碎片。,4.2 連續(xù)分配方式,動(dòng)態(tài)分區(qū)分配（可變分區(qū)分配）

32、分區(qū)分配算法循環(huán)首次適應(yīng)算法該算法是首次適應(yīng)算法的變形，在為作業(yè)分配存儲(chǔ)空間時(shí)，是從上次所分配的空閑區(qū)的下一個(gè)空閑區(qū)開始查找，直到找到第一個(gè)能滿足要求的空閑區(qū)，從中劃出一塊與請(qǐng)求的大小相等的 一塊存儲(chǔ)區(qū)分配給作業(yè)。若到最后一個(gè)空閑區(qū)的大小仍不能滿足要求時(shí)，應(yīng)再從第一個(gè)空閑區(qū)開始查找；需設(shè)置查詢指針；使空閑分區(qū)分布均勻，但是缺乏大的空閑區(qū)；,4.2 連續(xù)分配方式,動(dòng)態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配算法循環(huán)首次適應(yīng)算法該

33、算法是首次適應(yīng)算法的變形，在為作業(yè)分配存儲(chǔ)空間時(shí)，是從上次所分配的空閑區(qū)的下一個(gè)空閑區(qū)開始查找，直到找到第一個(gè)能滿足要求的空閑區(qū)，從中劃出一塊與請(qǐng)求的大小相等的 一塊存儲(chǔ)區(qū)分配給作業(yè)。若到最后一個(gè)空閑區(qū)的大小仍不能滿足要求時(shí)，應(yīng)再從第一個(gè)空閑區(qū)開始查找；需設(shè)置查詢指針；使空閑分區(qū)分布均勻，但是缺乏大的空閑區(qū)；,4.2 連續(xù)分配方式,動(dòng)態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配算法循環(huán)首次適應(yīng)算法該算法是首次適應(yīng)算法的變形，在為作業(yè)分

34、配存儲(chǔ)空間時(shí)，是從上次所分配的空閑區(qū)的下一個(gè)空閑區(qū)開始查找，直到找到第一個(gè)能滿足要求的空閑區(qū)，從中劃出一塊與請(qǐng)求的大小相等的 一塊存儲(chǔ)區(qū)分配給作業(yè)。若到最后一個(gè)空閑區(qū)的大小仍不能滿足要求時(shí)，應(yīng)再從第一個(gè)空閑區(qū)開始查找；需設(shè)置查詢指針；使空閑分區(qū)分布均勻，但是缺乏大的空閑區(qū)；,4.2 連續(xù)分配方式,動(dòng)態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配算法最佳適應(yīng)算法“最佳”的含義是指每次為作業(yè)分配主存時(shí)，總是把既能滿足要求，又是最小的空閑區(qū)分

35、配給作業(yè)，以免由于“大材小用”而浪費(fèi)主存。為了加速查找，該算法要求將所有的空閑區(qū)按其大小遞增次序排列；第一個(gè)找到能滿足要求的空閑區(qū)一定使最佳的；每次分割的剩余部分都是最小的，因此在存儲(chǔ)器中會(huì)留下很多難以利用的小碎片,4.2 連續(xù)分配方式,動(dòng)態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配算法最佳適應(yīng)算法“最佳”的含義是指每次為作業(yè)分配主存時(shí)，總是把既能滿足要求，又是最小的空閑區(qū)分配給作業(yè)，以免由于“大材小用”而浪費(fèi)主存。為了加速查找，該算法

36、要求將所有的空閑區(qū)按其大小遞增次序排列；第一個(gè)找到能滿足要求的空閑區(qū)一定使最佳的；每次分割的剩余部分都是最小的，因此在存儲(chǔ)器中會(huì)留下很多難以利用的小碎片,4.2 連續(xù)分配方式,動(dòng)態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配操作分配內(nèi)存 系統(tǒng)利用某種分配算法，從空閑分區(qū)表（鏈）中找到所需大小的分區(qū)。 分配流程見下圖。,4.2 連續(xù)分配方式,動(dòng)態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配操作回收內(nèi)存 系統(tǒng)根據(jù)回收區(qū)的首地址，從空

37、閑區(qū)鏈中找到插入點(diǎn)后，會(huì)有四種情況出現(xiàn)：（1）回收區(qū)前是空閑分區(qū)（2）回收區(qū)后是空閑分區(qū)（3）回收區(qū)前、后都是空閑分區(qū)（4）回收區(qū)前、后都不是空閑分區(qū),4.2 連續(xù)分配方式,可重定位分區(qū)分配動(dòng)態(tài)重定位的引入碎片問題 經(jīng)過一段時(shí)間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個(gè)都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為“碎片”或“零頭”。碎片問題的解決——“拼接”或“緊湊” 移動(dòng)內(nèi)存

38、中作業(yè)的位置，以把原來多個(gè)分散的小分區(qū)拼接成一個(gè)大分區(qū),4.2 連續(xù)分配方式,可重定位分區(qū)分配動(dòng)態(tài)重定位的引入碎片問題 經(jīng)過一段時(shí)間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個(gè)都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為“碎片”或“零頭”。碎片問題的解決——“拼接”或“緊湊” 移動(dòng)內(nèi)存中作業(yè)的位置，以把原來多個(gè)分散的小分區(qū)拼接成一個(gè)大分區(qū)。,4.2 連續(xù)分配方式,可重定位分區(qū)分配動(dòng)態(tài)

39、重定位的實(shí)現(xiàn)每次“緊湊”后必須對(duì)移動(dòng)了的程序或數(shù)據(jù)進(jìn)行重定位地址變換過程是在程序執(zhí)行期間，隨著對(duì)每條指令或數(shù)據(jù)的訪問自動(dòng)進(jìn)行的，稱為動(dòng)態(tài)重定位。硬件地址變換機(jī)構(gòu)的支持——重定位寄存器內(nèi)存地址＝相對(duì)地址＋重定位寄存器中的地址移動(dòng)程序時(shí)只需修改重定位寄存器中的地址,4.2 連續(xù)分配方式,可重定位分區(qū)分配動(dòng)態(tài)重定位的實(shí)現(xiàn)每次“緊湊”后必須對(duì)移動(dòng)了的程序或數(shù)據(jù)進(jìn)行重定位地址變換過程是在程序執(zhí)行期間，隨著對(duì)每條指令或數(shù)據(jù)的訪問自

40、動(dòng)進(jìn)行的，稱為動(dòng)態(tài)重定位。硬件地址變換機(jī)構(gòu)的支持——重定位寄存器內(nèi)存地址＝相對(duì)地址＋重定位寄存器中的地址移動(dòng)程序時(shí)只需修改重定位寄存器中的地址,4.2 連續(xù)分配方式,可重定位分區(qū)分配動(dòng)態(tài)重定位的實(shí)現(xiàn)每次“緊湊”后必須對(duì)移動(dòng)了的程序或數(shù)據(jù)進(jìn)行重定位地址變換過程是在程序執(zhí)行期間，隨著對(duì)每條指令或數(shù)據(jù)的訪問自動(dòng)進(jìn)行的，稱為動(dòng)態(tài)重定位。硬件地址變換機(jī)構(gòu)的支持——重定位寄存器內(nèi)存地址＝相對(duì)地址＋重定位寄存器中的地址移動(dòng)程序時(shí)只

41、需修改重定位寄存器中的地址,4.2 連續(xù)分配方式,可重定位分區(qū)分配動(dòng)態(tài)重定位的實(shí)現(xiàn)每次“緊湊”后必須對(duì)移動(dòng)了的程序或數(shù)據(jù)進(jìn)行重定位地址變換過程是在程序執(zhí)行期間，隨著對(duì)每條指令或數(shù)據(jù)的訪問自動(dòng)進(jìn)行的，稱為動(dòng)態(tài)重定位。硬件地址變換機(jī)構(gòu)的支持——重定位寄存器內(nèi)存地址＝相對(duì)地址＋重定位寄存器中的地址移動(dòng)程序時(shí)只需修改重定位寄存器中的地址,4.2 連續(xù)分配方式,可重定位分區(qū)分配動(dòng)態(tài)重定位的實(shí)現(xiàn)每次“緊湊”后必須對(duì)移動(dòng)了的程序或

42、數(shù)據(jù)進(jìn)行重定位地址變換過程是在程序執(zhí)行期間，隨著對(duì)每條指令或數(shù)據(jù)的訪問自動(dòng)進(jìn)行的，稱為動(dòng)態(tài)重定位。硬件地址變換機(jī)構(gòu)的支持——重定位寄存器內(nèi)存地址＝相對(duì)地址＋重定位寄存器中的地址移動(dòng)程序時(shí)只需修改重定位寄存器中的地址,4.2 連續(xù)分配方式,可重定位分區(qū)分配動(dòng)態(tài)重定位分區(qū)分配算法 與動(dòng)態(tài)分區(qū)分配算法基本相同，增加了緊湊的功能。見下圖。,4.2 連續(xù)分配方式,對(duì)換(Swapping)對(duì)換的引入所謂“對(duì)換”， 是

43、指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。對(duì)換分類整體對(duì)換、進(jìn)程對(duì)換部分對(duì)換：頁面對(duì)換、分段對(duì)換,4.2 連續(xù)分配方式,對(duì)換(Swapping)對(duì)換的引入所謂“對(duì)換”， 是指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)，調(diào)入

44、內(nèi)存。對(duì)換分類整體對(duì)換、進(jìn)程對(duì)換部分對(duì)換：頁面對(duì)換、分段對(duì)換,4.2 連續(xù)分配方式,對(duì)換(Swapping)OS必須實(shí)現(xiàn)三方面的功能：對(duì)換空間的管理、進(jìn)程的換出、進(jìn)程的換入對(duì)換空間的管理連續(xù)分配方式空閑分區(qū)表或空閑分區(qū)鏈對(duì)換空間的分配與回收，與動(dòng)態(tài)分區(qū)方式時(shí)的內(nèi)存分配與回收方法雷同,4.2 連續(xù)分配方式,對(duì)換(Swapping)OS必須實(shí)現(xiàn)三方面的功能：對(duì)換空間的管理、進(jìn)程的換出、進(jìn)程的換入對(duì)換空間的管理連

45、續(xù)分配方式空閑分區(qū)表或空閑分區(qū)鏈對(duì)換空間的分配與回收，與動(dòng)態(tài)分區(qū)方式時(shí)的內(nèi)存分配與回收方法雷同,4.2 連續(xù)分配方式,對(duì)換(Swapping)進(jìn)程的換出與換入換出過程選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，換出后收回內(nèi)存空間，修改進(jìn)程的PCB相關(guān)信息換入過程找出“就緒”狀態(tài)并已經(jīng)換出的進(jìn)程，將其中換出時(shí)間最久的進(jìn)程作為換入進(jìn)程，將其換入直到已無可換入的進(jìn)程和無可換出的進(jìn)程,4.2 連續(xù)分配方式,對(duì)換(Sw

46、apping)進(jìn)程的換出與換入換出過程選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，換出后收回內(nèi)存空間，修改進(jìn)程的PCB相關(guān)信息換入過程找出“就緒”狀態(tài)并已經(jīng)換出的進(jìn)程，將其中換出時(shí)間最久的進(jìn)程作為換入進(jìn)程，將其換入直到已無可換入的進(jìn)程和無可換出的進(jìn)程,4.2 連續(xù)分配方式,對(duì)換(Swapping)進(jìn)程的換出與換入換出過程選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，換出后收回內(nèi)存空間，修改進(jìn)程的PCB相關(guān)

47、信息換入過程找出“就緒”狀態(tài)并已經(jīng)換出的進(jìn)程，將其中換出時(shí)間最久的進(jìn)程作為換入進(jìn)程，將其換入直到已無可換入的進(jìn)程和無可換出的進(jìn)程,4.3 基本分頁存儲(chǔ)管理方式,連續(xù)分配方式的缺點(diǎn)：形成許多“碎片”；“緊湊”開銷大。離散分配方式：無須“緊湊”，將一個(gè)用戶程序離散地分配到內(nèi)存中的多個(gè)不相連接的區(qū)域中。分頁存儲(chǔ)管理方式－離散的基本單位是“頁”分段存儲(chǔ)管理方式－離散的基本單位是“段”段頁式存儲(chǔ)管理方式在分頁存儲(chǔ)管理方式中，如

48、果不具備頁面對(duì)換功能，就是基本分頁存儲(chǔ)管理方式，即不支持虛擬存儲(chǔ)器的功能,4.3 基本分頁存儲(chǔ)管理方式,連續(xù)分配方式的缺點(diǎn)：形成許多“碎片”；“緊湊”開銷大。離散分配方式：無須“緊湊”，將一個(gè)用戶程序離散地分配到內(nèi)存中的多個(gè)不相連接的區(qū)域中。分頁存儲(chǔ)管理方式－離散的基本單位是“頁”分段存儲(chǔ)管理方式－離散的基本單位是“段”段頁式存儲(chǔ)管理方式在分頁存儲(chǔ)管理方式中，如果不具備頁面對(duì)換功能，就是基本分頁存儲(chǔ)管理方式，即不支持虛擬存儲(chǔ)

49、器的功能,4.3 基本分頁存儲(chǔ)管理方式,連續(xù)分配方式的缺點(diǎn)：形成許多“碎片”；“緊湊”開銷大。離散分配方式：無須“緊湊”，將一個(gè)用戶程序離散地分配到內(nèi)存中的多個(gè)不相連接的區(qū)域中。分頁存儲(chǔ)管理方式－離散的基本單位是“頁”分段存儲(chǔ)管理方式－離散的基本單位是“段”段頁式存儲(chǔ)管理方式在分頁存儲(chǔ)管理方式中，如果不具備頁面對(duì)換功能，就是基本分頁存儲(chǔ)管理方式，即不支持虛擬存儲(chǔ)器的功能,4.3 基本分頁存儲(chǔ)管理方式,頁面與頁表頁面頁面

50、和物理塊頁（頁面）——把每個(gè)作業(yè)(進(jìn)程)邏輯地址空間劃分成若干大小相等的片.第0頁、第1頁 (物理)塊或頁框(frame)——把內(nèi)存空間分成與頁面相同大小的若干個(gè)存儲(chǔ)塊。 0＃塊、1＃塊 頁內(nèi)碎片——由于進(jìn)程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片。,4.3 基本分頁存儲(chǔ)管理方式,頁面與頁表頁面頁面大小太小，可使內(nèi)存碎片減小，有利于提高內(nèi)存利用率；會(huì)使每個(gè)進(jìn)程占用較多的頁面，從而導(dǎo)致進(jìn)程的頁表過長，占用大量

51、內(nèi)存； 此外，還會(huì)降低頁面換進(jìn)換出的效率。較大，可以減少頁表的長度，提高頁面換進(jìn)換出的速度，但卻又會(huì)使頁內(nèi)碎片增大。頁面的大小應(yīng)選擇得適中，且頁面大小應(yīng)是2的冪，通常為512 B~8 KB。,4.3 基本分頁存儲(chǔ)管理方式,頁面與頁表地址結(jié)構(gòu),31,12,11,0,220＝1M(頁)每頁大小為：212＝4KB,4.3 基本分頁存儲(chǔ)管理方式,頁面與頁表地址結(jié)構(gòu),對(duì)某特定機(jī)器，其地址結(jié)構(gòu)是一定的。地址為A，頁面的大小為L，則頁號(hào)

52、P和頁內(nèi)地址d可按下式求得：,例：系統(tǒng)頁面大小為１KB，設(shè)A＝2170B，則P=2,d=122,4.3 基本分頁存儲(chǔ)管理方式,頁面與頁表頁表（頁面映象表）頁表的作用是實(shí)現(xiàn)從頁號(hào)到物理塊號(hào)的地址映射由頁號(hào)和塊號(hào)組成，指出邏輯地址中頁號(hào)與主存中物理塊號(hào)的對(duì)應(yīng)關(guān)系 頁號(hào)---作業(yè)地址空間的頁序號(hào) 塊號(hào)---內(nèi)存空間的頁面序號(hào),頁表的作用,4.3 基本分頁存儲(chǔ)管理方式,地址變換機(jī)構(gòu)借助于頁表，實(shí)現(xiàn)從邏輯地址到

53、物理地址的轉(zhuǎn)換基本的地址變換機(jī)構(gòu)頁表駐留在內(nèi)存中進(jìn)程未執(zhí)行時(shí)，頁表的始址和頁表長度存放在PCB中進(jìn)程執(zhí)行時(shí)，頁表的始址和頁表長度裝入頁表寄存器,圖 4-12 分頁系統(tǒng)的地址變換機(jī)構(gòu),例：一個(gè)三頁長的進(jìn)程，每頁長1K。 頁號(hào)頁框號(hào)（塊號(hào)）              

54、 0   2               1 3                2 8

55、 指令：100 LOAD 1，2500的地址變換過程為：根據(jù)控制寄存器找到頁表的始址和長度，該指令地址=2*1024+100 = 2148執(zhí)行： 2500 = 2048+452 P=2 W=452 B= 82500單元的物理地址=1024*8+452 = 8644,4.3 基本分頁存儲(chǔ)管理方式,地址變換機(jī)構(gòu)具有快表的地址變換機(jī)構(gòu)頁表駐留在內(nèi)存中的缺點(diǎn)：每存取一個(gè)數(shù)據(jù)都要兩次訪問內(nèi)存。聯(lián)想

56、寄存器（快表）：存放當(dāng)前訪問的若干個(gè)頁表項(xiàng)具有快表的地址變換機(jī)構(gòu)見下圖。,4.3 基本分頁存儲(chǔ)管理方式,二級(jí)頁表CPU具有32位地址時(shí) ,使用232邏輯地址空間的分頁系統(tǒng),規(guī)定頁面4KB時(shí),每個(gè)進(jìn)程頁表的表項(xiàng)有1M(220)個(gè),若表項(xiàng)占用1個(gè)字節(jié),則每個(gè)進(jìn)程需要占用1MB連續(xù)內(nèi)存空間存放頁表解決辦法：把將頁表進(jìn)行分頁,分成一張張小頁表(稱為頁表頁) ,小頁表的大小與頁框相同，為進(jìn)行索引查找,應(yīng)該為這些小頁表建一張頁目錄表為離散

57、分配的頁表再建一張頁表，稱為：外層頁表或頁目錄表,4.3 基本分頁存儲(chǔ)管理方式,二級(jí)頁表,邏輯地址結(jié)構(gòu)可描述如下：,外層頁表頁表,,兩級(jí)頁表,,1011,,1078,,0,1,2,,,1742,n,第,0,頁頁表,,1,,4,,6,,…,,0,1,2,…,1023,第,1,頁頁表,,114,,115,,,0,1,…,1023,外部頁表,,,,,,,,,0,1,2,3,4,5,6,7,,…,,,,,,…,114,115,1468,,,

58、,,,第,n,頁頁表,,1468,,,,,0,1,2,…,1023,,,,,,,,,,,,,,內(nèi)存空間,兩級(jí)頁表結(jié)構(gòu),具有兩級(jí)頁表的地址變換機(jī)構(gòu),外部頁號(hào),,P,1,,P,2,外部頁內(nèi)地址,頁內(nèi)地址,,d,邏輯地址,,＋,,,,外部頁表寄存器,,,,,外部頁表,,＋,,,,,,,,,,,d,,b,頁表,頁表,物理地址,,,,,,…,,,,,,,,…,,二級(jí)頁表地址變換需三次訪問主存：一次訪問頁目錄、一次訪問頁表頁、一次訪問指令或數(shù)據(jù)，訪