1、第四章 存儲(chǔ)器管理第十五講第十五講存儲(chǔ)器管理（三）存儲(chǔ)器管理（三）-虛擬存儲(chǔ)器虛擬存儲(chǔ)器第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院本次課程主要內(nèi)容本次課程主要內(nèi)容虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的實(shí)現(xiàn)方式虛擬存儲(chǔ)器的實(shí)現(xiàn)方式虛擬存儲(chǔ)器的特征虛擬存儲(chǔ)器的特征請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)請(qǐng)求分頁(yè)的硬件支持請(qǐng)求分頁(yè)的硬件支持內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法調(diào)調(diào)頁(yè)策略頁(yè)策略第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院3存儲(chǔ)管理存儲(chǔ)管理（內(nèi)存）（內(nèi)存） 連續(xù)分配連續(xù)分配固定分區(qū)分配固定分區(qū)分配單一連續(xù)單一連續(xù)等大小等大小不等大小不等大小

2、動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配首次適應(yīng)首次適應(yīng)循環(huán)首次適應(yīng)循環(huán)首次適應(yīng)最佳適應(yīng)最佳適應(yīng)最壞適應(yīng)最壞適應(yīng)快速適應(yīng)快速適應(yīng)伙伴系統(tǒng)伙伴系統(tǒng)離散分配離散分配一次性一次性基本分頁(yè)基本分頁(yè)基本分段基本分段段頁(yè)式段頁(yè)式多次性多次性請(qǐng)求分頁(yè)請(qǐng)求分頁(yè)請(qǐng)求分段請(qǐng)求分段第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院44.64.6虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的基本概念 (1) (1) 有的作業(yè)很大，其所要求的內(nèi)存空間超過(guò)有的作業(yè)很大，其所要求的內(nèi)存空間超過(guò)了內(nèi)存總?cè)萘?，作業(yè)不能全部被裝入內(nèi)存，致使該了內(nèi)存總?cè)萘?，作業(yè)不能全部被裝入內(nèi)存，致使該作業(yè)無(wú)法運(yùn)行。作業(yè)無(wú)法運(yùn)行。(2) (2) 有大量作業(yè)要求運(yùn)行，但由

3、于內(nèi)存容量不有大量作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將少數(shù)作業(yè)足以容納所有這些作業(yè)，只能將少數(shù)作業(yè) 裝入內(nèi)裝入內(nèi)存讓它們先運(yùn)行，而將其它大量的作業(yè)留在外存上存讓它們先運(yùn)行，而將其它大量的作業(yè)留在外存上等待。等待。 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院54.6.14.6.1虛擬存儲(chǔ)器的引入虛擬存儲(chǔ)器的引入1 1常規(guī)存儲(chǔ)器管理方式的特征常規(guī)存儲(chǔ)器管理方式的特征(1) (1) 一次性。在前面所介紹的幾種存儲(chǔ)管理方一次性。在前面所介紹的幾種存儲(chǔ)管理方式中，都要求將作業(yè)全部裝入內(nèi)存后方能運(yùn)行，即式中，都要求將作業(yè)全部裝入內(nèi)存后方能運(yùn)行，即作業(yè)在運(yùn)行前需一次性地全

4、部裝入內(nèi)存，而正是這作業(yè)在運(yùn)行前需一次性地全部裝入內(nèi)存，而正是這一特征導(dǎo)致了上述兩種情況的發(fā)生。此外，還有許一特征導(dǎo)致了上述兩種情況的發(fā)生。此外，還有許多作業(yè)在每次運(yùn)行時(shí)，并非其全部程序和數(shù)據(jù)都要多作業(yè)在每次運(yùn)行時(shí)，并非其全部程序和數(shù)據(jù)都要用到。如果一次性地裝入其全部程序，也是一種對(duì)用到。如果一次性地裝入其全部程序，也是一種對(duì)內(nèi)存空間的浪費(fèi)。內(nèi)存空間的浪費(fèi)。 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院6 (2) (2) 駐留性。作業(yè)裝入內(nèi)存后，便一直駐留在駐留性。作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至作業(yè)運(yùn)行結(jié)束。盡管運(yùn)行中的進(jìn)程會(huì)內(nèi)存中，直至作業(yè)運(yùn)行結(jié)束。盡管運(yùn)行中的進(jìn)程會(huì)因

5、因I/OI/O而長(zhǎng)期等待，或有的程序模塊在運(yùn)行過(guò)一次而長(zhǎng)期等待，或有的程序模塊在運(yùn)行過(guò)一次后就不再需要后就不再需要( (運(yùn)行運(yùn)行) )了，但它們都仍將繼續(xù)占用寶了，但它們都仍將繼續(xù)占用寶貴的內(nèi)存資源。貴的內(nèi)存資源。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院72 2局部性原理局部性原理早在早在19681968年，年，Denning.PDenning.P就曾指出：程序在執(zhí)就曾指出：程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律，即在一較短的時(shí)間內(nèi)，行時(shí)將呈現(xiàn)出局部性規(guī)律，即在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分；相應(yīng)地，它所訪(fǎng)問(wèn)程序的執(zhí)行僅局限于某個(gè)部分；相應(yīng)地，它所訪(fǎng)問(wèn)的存儲(chǔ)空間也局限于某個(gè)

6、區(qū)域。他提出了下述幾個(gè)的存儲(chǔ)空間也局限于某個(gè)區(qū)域。他提出了下述幾個(gè)論點(diǎn)：論點(diǎn)：第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院8 (1) (1) 程序執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過(guò)程調(diào)用指程序執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過(guò)程調(diào)用指令外，在大多數(shù)情況下仍是順序執(zhí)行的。該論點(diǎn)也在后令外，在大多數(shù)情況下仍是順序執(zhí)行的。該論點(diǎn)也在后來(lái)的許多學(xué)者對(duì)高級(jí)程序設(shè)計(jì)語(yǔ)言來(lái)的許多學(xué)者對(duì)高級(jí)程序設(shè)計(jì)語(yǔ)言( (如如FORTRANFORTRAN語(yǔ)言、語(yǔ)言、PASCALPASCAL語(yǔ)言語(yǔ)言) )及及C C語(yǔ)言規(guī)律的研究中被證實(shí)。語(yǔ)言規(guī)律的研究中被證實(shí)。 (2) (2) 過(guò)程調(diào)用將會(huì)使程序的執(zhí)行軌跡由一部分區(qū)域過(guò)程調(diào)

7、用將會(huì)使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域，但經(jīng)研究看出，過(guò)程調(diào)用的深度在轉(zhuǎn)至另一部分區(qū)域，但經(jīng)研究看出，過(guò)程調(diào)用的深度在大多數(shù)情況下都不超過(guò)大多數(shù)情況下都不超過(guò)5 5。這就是說(shuō)，程序?qū)?huì)在一段。這就是說(shuō)，程序?qū)?huì)在一段時(shí)間內(nèi)都局限在這些過(guò)程的范圍內(nèi)運(yùn)行。時(shí)間內(nèi)都局限在這些過(guò)程的范圍內(nèi)運(yùn)行。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院9 (3) (3) 程序中存在許多循環(huán)結(jié)構(gòu)，這些雖然只由程序中存在許多循環(huán)結(jié)構(gòu)，這些雖然只由少數(shù)指令構(gòu)成，但是它們將多次執(zhí)行。少數(shù)指令構(gòu)成，但是它們將多次執(zhí)行。(4) (4) 程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，如程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理

8、，如對(duì)數(shù)組進(jìn)行操作，它們往往都局限于很小的范圍內(nèi)。對(duì)數(shù)組進(jìn)行操作，它們往往都局限于很小的范圍內(nèi)。 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院10局限性還表現(xiàn)在下述兩個(gè)方面：局限性還表現(xiàn)在下述兩個(gè)方面：(1) (1) 時(shí)間局限性。如果程序中的某條指令一旦執(zhí)行，時(shí)間局限性。如果程序中的某條指令一旦執(zhí)行，則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪(fǎng)問(wèn)過(guò)，則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪(fǎng)問(wèn)過(guò)，則不久以后該數(shù)據(jù)可能再次被訪(fǎng)問(wèn)。產(chǎn)生時(shí)間局限性的則不久以后該數(shù)據(jù)可能再次被訪(fǎng)問(wèn)。產(chǎn)生時(shí)間局限性的典型原因是由于在程序中存在著大量的循環(huán)操作。典型原因是由于在程序中存在著大量的循環(huán)操作。(

9、2) (2) 空間局限性。一旦程序訪(fǎng)問(wèn)了某個(gè)存儲(chǔ)單元，空間局限性。一旦程序訪(fǎng)問(wèn)了某個(gè)存儲(chǔ)單元，在不久之后，其附近的存儲(chǔ)單元也將被訪(fǎng)問(wèn)，即程序在在不久之后，其附近的存儲(chǔ)單元也將被訪(fǎng)問(wèn)，即程序在一段時(shí)間內(nèi)所訪(fǎng)問(wèn)的地址，可能集中在一定的范圍之內(nèi)，一段時(shí)間內(nèi)所訪(fǎng)問(wèn)的地址，可能集中在一定的范圍之內(nèi)，其典型情況便是程序的順序執(zhí)行其典型情況便是程序的順序執(zhí)行第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院113 3虛擬存儲(chǔ)器的定義虛擬存儲(chǔ)器的定義基于局部性原理，應(yīng)用程序在運(yùn)行之前，沒(méi)有基于局部性原理，應(yīng)用程序在運(yùn)行之前，沒(méi)有必要全部裝入內(nèi)存，僅須將那些當(dāng)前要運(yùn)行的少數(shù)必要全部裝入內(nèi)存，僅須將那些當(dāng)前

10、要運(yùn)行的少數(shù)頁(yè)面或段先裝入內(nèi)存便可運(yùn)行，其余部分暫留在磁頁(yè)面或段先裝入內(nèi)存便可運(yùn)行，其余部分暫留在磁盤(pán)上。程序在運(yùn)行時(shí)，如果它所要訪(fǎng)問(wèn)的頁(yè)盤(pán)上。程序在運(yùn)行時(shí)，如果它所要訪(fǎng)問(wèn)的頁(yè)( (段段) )已已調(diào)入內(nèi)存，便可繼續(xù)執(zhí)行下去；但如果程序所要訪(fǎng)調(diào)入內(nèi)存，便可繼續(xù)執(zhí)行下去；但如果程序所要訪(fǎng)問(wèn)的頁(yè)問(wèn)的頁(yè)( (段段) )尚未調(diào)入內(nèi)存尚未調(diào)入內(nèi)存( (稱(chēng)為稱(chēng)為缺頁(yè)或缺段缺頁(yè)或缺段) )，此，此時(shí)程序應(yīng)利用時(shí)程序應(yīng)利用OSOS所提供的所提供的請(qǐng)求調(diào)頁(yè)請(qǐng)求調(diào)頁(yè)( (段段) )功能，將功能，將它們調(diào)入內(nèi)存，以使進(jìn)程能繼續(xù)執(zhí)行下去。它們調(diào)入內(nèi)存，以使進(jìn)程能繼續(xù)執(zhí)行下去。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與

11、通信工程學(xué)院12如果此時(shí)內(nèi)存已滿(mǎn)，無(wú)法再裝入新的頁(yè)如果此時(shí)內(nèi)存已滿(mǎn)，無(wú)法再裝入新的頁(yè)( (段段) )，則還，則還須再利用須再利用頁(yè)頁(yè)( (段段) )的置換的置換功能，將內(nèi)存中暫時(shí)不用功能，將內(nèi)存中暫時(shí)不用的頁(yè)的頁(yè)( (段段) )調(diào)至盤(pán)上，騰出足夠的內(nèi)存空間后，再將調(diào)至盤(pán)上，騰出足夠的內(nèi)存空間后，再將要訪(fǎng)問(wèn)的頁(yè)要訪(fǎng)問(wèn)的頁(yè)( (段段) )調(diào)入內(nèi)存，使程序繼續(xù)執(zhí)行下去。調(diào)入內(nèi)存，使程序繼續(xù)執(zhí)行下去。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院134.6.24.6.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器的實(shí)現(xiàn)方法1 1分頁(yè)請(qǐng)求系統(tǒng)分頁(yè)請(qǐng)求系統(tǒng)這是在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了這是在分頁(yè)系統(tǒng)的基礎(chǔ)上，

12、增加了請(qǐng)求調(diào)頁(yè)功能請(qǐng)求調(diào)頁(yè)功能和和頁(yè)面置換功能頁(yè)面置換功能所形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)。它允許所形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)。它允許只裝入少數(shù)頁(yè)面的程序只裝入少數(shù)頁(yè)面的程序( (及數(shù)據(jù)及數(shù)據(jù)) )，便啟動(dòng)運(yùn)行。以后，便啟動(dòng)運(yùn)行。以后，再通過(guò)調(diào)頁(yè)功能及頁(yè)面置換功能，陸續(xù)地把即將要運(yùn)行再通過(guò)調(diào)頁(yè)功能及頁(yè)面置換功能，陸續(xù)地把即將要運(yùn)行的頁(yè)面調(diào)入內(nèi)存，同時(shí)把暫不運(yùn)行的頁(yè)面換出到外存上。的頁(yè)面調(diào)入內(nèi)存，同時(shí)把暫不運(yùn)行的頁(yè)面換出到外存上。置換時(shí)以頁(yè)面為單位。為了能實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)和置換功能，置換時(shí)以頁(yè)面為單位。為了能實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)和置換功能，系統(tǒng)必須提供必要的硬件支持和相應(yīng)的軟件。系統(tǒng)必須提供必要的硬件支持和相應(yīng)的軟件。

13、 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院14硬件硬件支持支持 請(qǐng)求分請(qǐng)求分頁(yè)的頁(yè)表頁(yè)的頁(yè)表機(jī)制機(jī)制 缺頁(yè)中缺頁(yè)中斷機(jī)構(gòu)斷機(jī)構(gòu) 地址變地址變換機(jī)構(gòu)換機(jī)構(gòu)1) 1) 硬件支持硬件支持第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院152) 2) 實(shí)現(xiàn)請(qǐng)求分頁(yè)的軟件實(shí)現(xiàn)請(qǐng)求分頁(yè)的軟件這里包括有用于實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)的軟件和實(shí)現(xiàn)頁(yè)這里包括有用于實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)的軟件和實(shí)現(xiàn)頁(yè)面置換的軟件。它們?cè)谟布闹С窒?，將程序正在面置換的軟件。它們?cè)谟布闹С窒?，將程序正在運(yùn)行時(shí)所需的頁(yè)面運(yùn)行時(shí)所需的頁(yè)面( (尚未在內(nèi)存中的尚未在內(nèi)存中的) )調(diào)入內(nèi)存，再調(diào)入內(nèi)存，再將內(nèi)存中暫時(shí)不用的頁(yè)面從內(nèi)存置換

14、到磁盤(pán)上。將內(nèi)存中暫時(shí)不用的頁(yè)面從內(nèi)存置換到磁盤(pán)上。 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院162 2請(qǐng)求分段系統(tǒng)請(qǐng)求分段系統(tǒng)這是在分段系統(tǒng)的基礎(chǔ)上，增加了這是在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段請(qǐng)求調(diào)段及及分段置換分段置換功能后所形成的段式虛擬存儲(chǔ)系統(tǒng)。功能后所形成的段式虛擬存儲(chǔ)系統(tǒng)。它允許只裝入少數(shù)段它允許只裝入少數(shù)段( (而非所有的段而非所有的段) )的用戶(hù)程序和的用戶(hù)程序和數(shù)據(jù)，即可啟動(dòng)運(yùn)行。以后再通過(guò)調(diào)段功能和段的數(shù)據(jù)，即可啟動(dòng)運(yùn)行。以后再通過(guò)調(diào)段功能和段的置換功能將暫不運(yùn)行的段調(diào)出，同時(shí)調(diào)入即將運(yùn)行置換功能將暫不運(yùn)行的段調(diào)出，同時(shí)調(diào)入即將運(yùn)行的段。置換是以段為單位進(jìn)

15、行的。的段。置換是以段為單位進(jìn)行的。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院17硬件硬件支持支持 請(qǐng)求分請(qǐng)求分段段的的段段表表機(jī)制機(jī)制 缺缺段段中中斷機(jī)構(gòu)斷機(jī)構(gòu) 地址變地址變換機(jī)構(gòu)換機(jī)構(gòu)第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院18多次多次性性對(duì)換對(duì)換性性虛擬虛擬性性4.6.34.6.3虛擬存儲(chǔ)器的特征虛擬存儲(chǔ)器的特征第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院191 1多次性多次性多次性是指一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行，亦多次性是指一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行，亦即在作業(yè)運(yùn)行時(shí)沒(méi)有必要將其全部裝入，只需將當(dāng)前要即在作業(yè)運(yùn)行時(shí)沒(méi)有必要將其全部裝入，

16、只需將當(dāng)前要運(yùn)行的那部分程序和數(shù)據(jù)裝入內(nèi)存即可；以后每當(dāng)要運(yùn)運(yùn)行的那部分程序和數(shù)據(jù)裝入內(nèi)存即可；以后每當(dāng)要運(yùn)行到尚未調(diào)入的那部分程序時(shí)，再將它調(diào)入。多次性是行到尚未調(diào)入的那部分程序時(shí)，再將它調(diào)入。多次性是虛擬存儲(chǔ)器最重要的特征，任何其它的存儲(chǔ)管理方式都虛擬存儲(chǔ)器最重要的特征，任何其它的存儲(chǔ)管理方式都不具有這一特征。因此，不具有這一特征。因此，我們也可以認(rèn)為虛擬存儲(chǔ)器是我們也可以認(rèn)為虛擬存儲(chǔ)器是具有多次性特征的存儲(chǔ)器系統(tǒng)。具有多次性特征的存儲(chǔ)器系統(tǒng)。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院202 2對(duì)換性對(duì)換性對(duì)換性是指允許在作業(yè)的運(yùn)行過(guò)程中進(jìn)行換進(jìn)、對(duì)換性是指允許在作業(yè)的運(yùn)行過(guò)

17、程中進(jìn)行換進(jìn)、換出，亦即，在進(jìn)程運(yùn)行期間，允許將那些暫不使換出，亦即，在進(jìn)程運(yùn)行期間，允許將那些暫不使用的程序和數(shù)據(jù)，從內(nèi)存調(diào)至外存的對(duì)換區(qū)用的程序和數(shù)據(jù)，從內(nèi)存調(diào)至外存的對(duì)換區(qū)( (換出換出) )，待以后需要時(shí)再將它們從外存調(diào)至內(nèi)存待以后需要時(shí)再將它們從外存調(diào)至內(nèi)存( (換進(jìn)換進(jìn)) )；甚；甚至還允許將暫時(shí)不運(yùn)行的進(jìn)程調(diào)至外存，待它們重至還允許將暫時(shí)不運(yùn)行的進(jìn)程調(diào)至外存，待它們重又具備運(yùn)行條件時(shí)再調(diào)入內(nèi)存。換進(jìn)和換出能有效又具備運(yùn)行條件時(shí)再調(diào)入內(nèi)存。換進(jìn)和換出能有效地提高內(nèi)存利用率。可見(jiàn)，虛擬存儲(chǔ)器具有對(duì)換性地提高內(nèi)存利用率。可見(jiàn)，虛擬存儲(chǔ)器具有對(duì)換性特征。特征。 第四章 存儲(chǔ)器管理東北大學(xué)

18、秦皇島分校計(jì)算機(jī)與通信工程學(xué)院213 3虛擬性虛擬性虛擬性是指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用虛擬性是指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶(hù)所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。這是虛戶(hù)所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。這是虛擬存儲(chǔ)器所表現(xiàn)出來(lái)的最重要的特征，也是實(shí)現(xiàn)虛擬存儲(chǔ)器所表現(xiàn)出來(lái)的最重要的特征，也是實(shí)現(xiàn)虛擬存儲(chǔ)器的最重要的目標(biāo)。擬存儲(chǔ)器的最重要的目標(biāo)。 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院22虛虛 擬性擬性對(duì)換性對(duì)換性多次性多次性離散分配離散分配第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院234.74.7請(qǐng)求分頁(yè)存儲(chǔ)管理方式請(qǐng)求分頁(yè)存儲(chǔ)管理方式 4.7.14.

19、7.1請(qǐng)求分頁(yè)中的硬件支持請(qǐng)求分頁(yè)中的硬件支持1 1頁(yè)表機(jī)制頁(yè)表機(jī)制 其基本作用仍然是將用戶(hù)地址空間中的邏輯地其基本作用仍然是將用戶(hù)地址空間中的邏輯地址變換為內(nèi)存空間中的物理地址。由于只將應(yīng)用程址變換為內(nèi)存空間中的物理地址。由于只將應(yīng)用程序的一部分調(diào)入內(nèi)存，還有一部分仍在盤(pán)上，故須序的一部分調(diào)入內(nèi)存，還有一部分仍在盤(pán)上，故須在頁(yè)表中再增加若干項(xiàng)，供程序在頁(yè)表中再增加若干項(xiàng)，供程序( (數(shù)據(jù)數(shù)據(jù)) )在換進(jìn)、換在換進(jìn)、換出時(shí)參考。出時(shí)參考。頁(yè)號(hào) 物理塊號(hào) 狀態(tài)位 P 訪(fǎng)問(wèn)字段 A 修改位 M 外存地址 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院24狀態(tài)位用于指示該頁(yè)是否已調(diào)入內(nèi)存，

20、供程序訪(fǎng)問(wèn)時(shí)參考。訪(fǎng)問(wèn)字段A記錄頁(yè)在一段時(shí)間內(nèi)被訪(fǎng)問(wèn)的次數(shù)，或記錄本頁(yè)最近已有多長(zhǎng)時(shí)間未被訪(fǎng)問(wèn)，供選擇換出頁(yè)面時(shí)參考。 修改位M表示該頁(yè)在調(diào)入內(nèi)存后是否被修改過(guò)。M位供置換頁(yè)面時(shí)參考。外存地址用于指出該頁(yè)在外存上的地址，通常是物理塊號(hào)，供調(diào)入該頁(yè)時(shí)參考。 頁(yè)號(hào) 物理塊號(hào) 狀態(tài)位 P 訪(fǎng)問(wèn)字段 A 修改位 M 外存地址 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院252 2缺頁(yè)中斷機(jī)構(gòu)缺頁(yè)中斷機(jī)構(gòu)在請(qǐng)求分頁(yè)系統(tǒng)中，每當(dāng)所要訪(fǎng)問(wèn)的頁(yè)面不在在請(qǐng)求分頁(yè)系統(tǒng)中，每當(dāng)所要訪(fǎng)問(wèn)的頁(yè)面不在內(nèi)存時(shí)，便產(chǎn)生一缺頁(yè)中斷，請(qǐng)求內(nèi)存時(shí)，便產(chǎn)生一缺頁(yè)中斷，請(qǐng)求OSOS將所缺之頁(yè)調(diào)將所缺之頁(yè)調(diào)入內(nèi)存。缺頁(yè)中斷作

21、為中斷，它們同樣需要經(jīng)歷諸入內(nèi)存。缺頁(yè)中斷作為中斷，它們同樣需要經(jīng)歷諸如如保護(hù)保護(hù)CPUCPU環(huán)境環(huán)境、分析中斷原因分析中斷原因、轉(zhuǎn)入缺頁(yè)中斷處轉(zhuǎn)入缺頁(yè)中斷處理程序進(jìn)行處理理程序進(jìn)行處理、恢復(fù)恢復(fù)CPUCPU環(huán)境環(huán)境等幾個(gè)步驟。但缺等幾個(gè)步驟。但缺頁(yè)中斷又是一種特殊的中斷，它與一般的中斷相比，頁(yè)中斷又是一種特殊的中斷，它與一般的中斷相比，有著明顯的區(qū)別有著明顯的區(qū)別第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院26主要表現(xiàn)在下面兩個(gè)方面：主要表現(xiàn)在下面兩個(gè)方面：(1) (1) 在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。通在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。通常，常，CPUCPU都是在一條指令執(zhí)

22、行完后，才檢查是否有都是在一條指令執(zhí)行完后，才檢查是否有中斷請(qǐng)求到達(dá)。若有，便去響應(yīng)，否則，繼續(xù)執(zhí)行中斷請(qǐng)求到達(dá)。若有，便去響應(yīng)，否則，繼續(xù)執(zhí)行下一條指令。然而，缺頁(yè)中斷是在指令執(zhí)行期間，下一條指令。然而，缺頁(yè)中斷是在指令執(zhí)行期間，發(fā)現(xiàn)所要訪(fǎng)問(wèn)的指令或數(shù)據(jù)不在內(nèi)存時(shí)所產(chǎn)生和處發(fā)現(xiàn)所要訪(fǎng)問(wèn)的指令或數(shù)據(jù)不在內(nèi)存時(shí)所產(chǎn)生和處理的。理的。 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院27(2) (2) 一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷。一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷。在圖在圖4-244-24中示出了一個(gè)例子。如在執(zhí)行一條指令中示出了一個(gè)例子。如在執(zhí)行一條指令COPY A

23、TO BCOPY A TO B時(shí)，可能要產(chǎn)生時(shí)，可能要產(chǎn)生6 6次缺頁(yè)中斷，其中指次缺頁(yè)中斷，其中指令本身跨了兩個(gè)頁(yè)面，令本身跨了兩個(gè)頁(yè)面，A A和和B B又分別各是一個(gè)數(shù)據(jù)塊，又分別各是一個(gè)數(shù)據(jù)塊，也都跨了兩個(gè)頁(yè)面。基于這些特征，系統(tǒng)中的硬件也都跨了兩個(gè)頁(yè)面?；谶@些特征，系統(tǒng)中的硬件機(jī)構(gòu)應(yīng)能保存多次中斷時(shí)的狀態(tài)，并保證最后能返機(jī)構(gòu)應(yīng)能保存多次中斷時(shí)的狀態(tài)，并保證最后能返回到中斷前產(chǎn)生缺頁(yè)中斷的指令處繼續(xù)執(zhí)行?；氐街袛嗲爱a(chǎn)生缺頁(yè)中斷的指令處繼續(xù)執(zhí)行。 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院28頁(yè)面B：A：654321指令COPY ATO B第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分

24、校計(jì)算機(jī)與通信工程學(xué)院3 3地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)頁(yè)表寄存器頁(yè)表始址頁(yè)表長(zhǎng)度頁(yè)號(hào)頁(yè)內(nèi)地址邏輯地址L越界中斷塊號(hào)b頁(yè)表頁(yè)號(hào)頁(yè)號(hào)輸入寄存器塊號(hào)bb快表d物理地址首先去檢索快表，試圖從中找出所要訪(fǎng)問(wèn)的頁(yè)。若找到，便修改頁(yè)表項(xiàng)中的訪(fǎng)問(wèn)位。對(duì)于寫(xiě)指令，還須將修改位置成“1”，然后利用頁(yè)表項(xiàng)中給出的物理塊號(hào)和頁(yè)內(nèi)地址形成物理地址。地址變換過(guò)程到此結(jié)束。 頁(yè)號(hào) 物理塊號(hào) 狀態(tài)位 P 訪(fǎng)問(wèn)字段 A 修改位 M 外存地址 如果在快表中未找到該頁(yè)的頁(yè)表項(xiàng)時(shí)，應(yīng)到內(nèi)存中去查找頁(yè)表，再?gòu)恼业降捻?yè)表項(xiàng)中的狀態(tài)位P，來(lái)了解該頁(yè)是否已調(diào)入內(nèi)存。若該頁(yè)已調(diào)入內(nèi)存，這時(shí)應(yīng)將此頁(yè)的頁(yè)表項(xiàng)寫(xiě)入快表，當(dāng)快表已滿(mǎn)時(shí)，應(yīng)先調(diào)出按某種算

25、法所確定的頁(yè)的頁(yè)表項(xiàng)，然后再寫(xiě)入該頁(yè)的頁(yè)表項(xiàng)；若該頁(yè)尚未調(diào)入內(nèi)存，這時(shí)應(yīng)產(chǎn)生缺頁(yè)中斷，請(qǐng)求OS從外存把該頁(yè)調(diào)入內(nèi)存。 29第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院30第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院314.7.24.7.2內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法1 1最小物理塊數(shù)的確定最小物理塊數(shù)的確定 這里所說(shuō)的最小物理塊數(shù)，是指能保證進(jìn)程正這里所說(shuō)的最小物理塊數(shù)，是指能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。當(dāng)系統(tǒng)為進(jìn)程分配的常運(yùn)行所需的最小物理塊數(shù)。當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無(wú)法運(yùn)行。進(jìn)程應(yīng)獲物理塊數(shù)少于此值時(shí)，進(jìn)程將無(wú)法運(yùn)行。進(jìn)

26、程應(yīng)獲得的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決得的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。于指令的格式、功能和尋址方式。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院322 2物理塊的分配策略物理塊的分配策略1) 1) 固定分配局部置換固定分配局部置換(Fixed Allocation(Fixed Allocation，Local Local Replacement)Replacement)這是指基于進(jìn)程的類(lèi)型這是指基于進(jìn)程的類(lèi)型( (交互型或批處理型等交互型或批處理型等) )，或，或根據(jù)程序員、程序管理員的建議，為每個(gè)進(jìn)程分配一定根據(jù)程序員、程序管

27、理員的建議，為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，在整個(gè)運(yùn)行期間都不再改變。采用該策數(shù)目的物理塊，在整個(gè)運(yùn)行期間都不再改變。采用該策略時(shí)，如果進(jìn)程在運(yùn)行中發(fā)現(xiàn)缺頁(yè)，則只能從該進(jìn)程在略時(shí)，如果進(jìn)程在運(yùn)行中發(fā)現(xiàn)缺頁(yè)，則只能從該進(jìn)程在內(nèi)存的內(nèi)存的n n個(gè)頁(yè)面中選出一個(gè)頁(yè)換出，然后再調(diào)入一頁(yè)，個(gè)頁(yè)面中選出一個(gè)頁(yè)換出，然后再調(diào)入一頁(yè)，以保證分配給該進(jìn)程的內(nèi)存空間不變。以保證分配給該進(jìn)程的內(nèi)存空間不變。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院332) 2) 可變分配全局置換可變分配全局置換(Variable Allocation(Variable Allocation，Global Global

28、 Replacement)Replacement) 在采用這種策略時(shí)，先為系統(tǒng)中的每個(gè)進(jìn)程分配一在采用這種策略時(shí)，先為系統(tǒng)中的每個(gè)進(jìn)程分配一定數(shù)目的物理塊，而定數(shù)目的物理塊，而OSOS自身也保持一個(gè)空閑物理塊隊(duì)列。自身也保持一個(gè)空閑物理塊隊(duì)列。當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁(yè)時(shí)，由系統(tǒng)從空閑物理塊隊(duì)列中取出當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁(yè)時(shí)，由系統(tǒng)從空閑物理塊隊(duì)列中取出一個(gè)物理塊分配給該進(jìn)程，并將欲調(diào)入的一個(gè)物理塊分配給該進(jìn)程，并將欲調(diào)入的( (缺缺) )頁(yè)裝入其頁(yè)裝入其中。這樣，凡產(chǎn)生缺頁(yè)中。這樣，凡產(chǎn)生缺頁(yè)( (中斷中斷) )的進(jìn)程，都將獲得新的物的進(jìn)程，都將獲得新的物理塊。僅當(dāng)空閑物理塊隊(duì)列中的物理塊用完時(shí)，理塊。僅當(dāng)空閑物理塊隊(duì)列中的物理塊用完時(shí)，OSOS才能才能從內(nèi)存中選擇一頁(yè)調(diào)出，該頁(yè)可能是系統(tǒng)中任一進(jìn)程的從內(nèi)存中選擇一頁(yè)調(diào)出，該頁(yè)可能是系統(tǒng)中任一進(jìn)程的頁(yè)。頁(yè)。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院343) 3) 可變分配局部置換可變分配局部置換(Variable Allocation(Variable Allocation，Local Local R