操作系統(tǒng)原理memory.pptx

1、第5章 存儲管理15.1 存儲管理的功能內(nèi)存是現(xiàn)代計(jì)算機(jī)系統(tǒng)的中心，是指CPU能直接存取指令和數(shù)據(jù)的存儲器，CPU和I/O設(shè)備都要和內(nèi)存打交道。內(nèi)存由很大的一組字或字節(jié)所組成，每個字或字節(jié)都有它們自己的編號，稱為內(nèi)存地址。對內(nèi)存的訪問是通過一系列對指定地址單元進(jìn)行讀寫來實(shí)現(xiàn)的。25.1 存儲管理的功能5.1.1 存儲空間的分配和回收 內(nèi)存的分配與回收是內(nèi)存管理的主要功能之一。用戶程序通常以文件的形式保存在計(jì)算機(jī)外存上，為了執(zhí)行用戶程序，用戶程序必須全部或部分裝入內(nèi)存，因此在內(nèi)外存之間必須不斷交換數(shù)據(jù)。能否把外存中的數(shù)據(jù)和程序調(diào)入內(nèi)存，取決于能否在內(nèi)存中為它們安排合適的位置。因此，存儲管理模塊要

2、為每一個并發(fā)執(zhí)行的進(jìn)程分配內(nèi)存空間。另外，當(dāng)進(jìn)程執(zhí)行結(jié)束之后，存儲管理模塊又要及時(shí)回收該進(jìn)程所占用的內(nèi)存資源，以便給其他進(jìn)程分配空間。35.1 存儲管理的功能5.1.2 地址轉(zhuǎn)換（映射）內(nèi)存的每個存儲單元都有一個編號，這種編號稱為內(nèi)存地址（或稱為物理地址，絕對地址）。內(nèi)存地址的集合稱為內(nèi)存空間（或物理地址空間）。源程序經(jīng)過匯編或編譯后，形成目標(biāo)程序，每個目標(biāo)程序都是以0為基址順序進(jìn)行編址的，原來用符號名訪問的單元用具體的數(shù)據(jù)單元號取代。這樣生成的目標(biāo)程序占據(jù)一定的地址空間，稱為作業(yè)的邏輯地址空間，簡稱邏輯空間。在邏輯空間中每條指令的地址和指令中要訪問的操作數(shù)地址統(tǒng)稱為邏輯地址。45.1 存儲管

3、理的功能地址映射Load A 200 3456 。 。1200物理地址空間Load A data1data1 3456源程序Load A 200 34560100200編譯連接邏輯地址空間BA=100055.1 存儲管理的功能我們把用戶程序裝入內(nèi)存時(shí)對有關(guān)指令的地址部分的修改定義為從程序地址到內(nèi)存地址的地址映射，或稱為地址重定位。地址映射的方式： 1、靜態(tài)地址重定位程序被裝入內(nèi)存時(shí)由操作系統(tǒng)的連接裝入程序完成程序的邏輯地址到內(nèi)存地址的轉(zhuǎn)換。假定程序裝入內(nèi)存的首地址為BR，程序地址為VR，內(nèi)存地址為MR，則地址映射按下式進(jìn)行：MR=BR+VR 。65.1 存儲管理的功能2、動態(tài)重定位動態(tài)地址重定

4、位是在程序執(zhí)行的過程中，每次訪問內(nèi)存之前，將要訪問的程序地址轉(zhuǎn)換為內(nèi)存地址。動態(tài)重定位依靠硬件地址變換機(jī)構(gòu)完成。地址重定位機(jī)構(gòu)需要一個(或多個)基地址寄存器BR和一個(或多個)程序虛擬地址寄存器VR。指令或數(shù)據(jù)的內(nèi)存地址MA與邏輯地址的關(guān)系為： MA=(BR)+ (VR) 這里，(BR)與(VR)分別表示寄存器BR與VR中的內(nèi)容。 75.1 存儲管理的功能85.1 存儲管理的功能5.1.3 主存空間的共享和保護(hù) 在多道程序設(shè)計(jì)環(huán)境下，內(nèi)存中的許多用戶或系統(tǒng)程序和數(shù)據(jù)段可供不同的用戶進(jìn)程共享。這種資源共享將會提高內(nèi)存的利用率。但是，反過來說，除了被允許共享的部分之外，又要限制各進(jìn)程只在自己的存儲

5、區(qū)活動，各進(jìn)程不能對別的進(jìn)程的程序和數(shù)據(jù)段產(chǎn)生干擾和破壞，因此須對內(nèi)存中的程序和數(shù)據(jù)段采取保護(hù)措施。 95.1 存儲管理的功能內(nèi)存保護(hù)的方式：（1）上、下界存儲保護(hù)：上、下界保護(hù)是一種簡單的存儲保護(hù)技術(shù)。系統(tǒng)可為每個作業(yè)設(shè)置一對上、下界寄存器，分別用來存放當(dāng)前運(yùn)行作業(yè)在內(nèi)存空間的上、下邊界地址，用它們來限制用戶程序的活動范圍。 （2）基址限長存儲保護(hù)：上、下界保護(hù)的一個變種是采用基址限長存儲保護(hù)。105.1 存儲管理的功能115.1 存儲管理的功能5.1.4 主存空間的擴(kuò)充對內(nèi)存進(jìn)行邏輯上的擴(kuò)充，現(xiàn)在普遍采用虛擬存儲管理技術(shù)。 虛擬存儲技術(shù)的基本思想是把有限的內(nèi)存空間與大容量的外存統(tǒng)一管理起來

6、，構(gòu)成一個遠(yuǎn)大于實(shí)際內(nèi)存的、虛擬的存儲器。此時(shí)，外存是作為內(nèi)存的直接延伸，用戶并不會感覺到內(nèi)、外存的區(qū)別，即把兩級存儲器當(dāng)作一級存儲器來看待。一個作業(yè)運(yùn)行時(shí)，其全部信息裝入虛存，實(shí)際上可能只有當(dāng)前運(yùn)行的必需一部分信息存入內(nèi)存，其他則存于外存，當(dāng)所訪問的信息不在內(nèi)存時(shí)，系統(tǒng)自動將其從外存調(diào)入內(nèi)存。 125.2 連續(xù)內(nèi)存分配5.2.1 分區(qū)管理的基本原理分區(qū)管理的基本原理是給每一個內(nèi)存中的進(jìn)程劃分一塊適當(dāng)大小的存儲區(qū),以連續(xù)存儲各進(jìn)程的程序和數(shù)據(jù)，使各進(jìn)程得以并發(fā)執(zhí)行。按分區(qū)的時(shí)機(jī)，分區(qū)管理可以分為固定分區(qū)和動態(tài)分區(qū)兩種方法。1、固定分區(qū)法：把內(nèi)存區(qū)固定地劃分為若干個大小不等的區(qū)域。劃分的原則由系

7、統(tǒng)操作員或操作系統(tǒng)決定。分區(qū)一旦劃分結(jié)束，在整個執(zhí)行過程中每個分區(qū)的長度和內(nèi)存的總分區(qū)個數(shù)將保持不變。135.2 連續(xù)內(nèi)存分配某系統(tǒng)的內(nèi)存容量為256K，操作系統(tǒng)占用低地址的20K，其余空間劃分成4個固定大小的分區(qū)。如下圖：145.2 連續(xù)內(nèi)存分配2、動態(tài)分區(qū)法動態(tài)分區(qū)法在作業(yè)執(zhí)行前并不建立分區(qū)，分區(qū)的建立是在作業(yè)的處理過程中進(jìn)行的，且其大小可隨作業(yè)或進(jìn)程對內(nèi)存的要求而改變。這就改變了固定分區(qū)法中那種即使是小作業(yè)也要占據(jù)大分區(qū)的浪費(fèi)現(xiàn)象，從而提高了內(nèi)存的利用率。 采用動態(tài)分區(qū)法，在系統(tǒng)初啟時(shí)，除了操作系統(tǒng)中常駐內(nèi)存部分之外，只有一個空閑分區(qū)。隨后，分配程序?qū)⒃搮^(qū)依次劃分給調(diào)度選中的作業(yè)或進(jìn)程。

8、155.2 連續(xù)內(nèi)存分配165.2 連續(xù)內(nèi)存分配在動態(tài)分區(qū)存儲管理中，要有相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來登記空閑區(qū)的說明信息，它包括空閑區(qū)的大小和位置。不同系統(tǒng)根據(jù)設(shè)計(jì)要求采用不同的結(jié)構(gòu)。常用的有表結(jié)構(gòu)和隊(duì)列結(jié)構(gòu)?？臻e區(qū)表的每個表目記錄一個空閑區(qū)，主要參數(shù)包括區(qū)號、長度和起始地址?？臻e區(qū)隊(duì)列則是利用每個內(nèi)存空閑區(qū)的頭幾個單元存放本空閑區(qū)的大小及下個空閑區(qū)的起始地址，從而把所有的空閑區(qū)鏈接起來。 175.2 連續(xù)內(nèi)存分配185.2 連續(xù)內(nèi)存分配5.2.2 分區(qū)的分配和回收1.固定分區(qū)的分配和回收 當(dāng)用戶程序要裝入執(zhí)行時(shí)，存儲管理程序根據(jù)用戶程序的大小查詢分區(qū)說明表，從中找出一個滿足要求的空閑分區(qū)，并將其分配給

9、申請者。 195.2 連續(xù)內(nèi)存分配2、動態(tài)分區(qū)的分配和回收（1）分區(qū)的分配當(dāng)用戶要求一個大小為SIZE的存儲空間時(shí)，系統(tǒng)查詢空閑區(qū)表或空閑分區(qū)隊(duì)列，找一個大于或等于SIZE的空閑區(qū)。分配時(shí)會出現(xiàn)以下三種情況：一是系統(tǒng)中無滿足要求的空閑區(qū)，則分配失敗。二是空閑區(qū)大小與SIZE相等，則修改空閑區(qū)表相應(yīng)表目，向用戶返回該空閑區(qū)首址。三是空閑區(qū)大于SIZE，這時(shí)將空閑區(qū)一分為二。將一個空閑區(qū)分成二部分有兩種辦法：一是從空閑區(qū)的上部開始劃出SIZE大小的空閑區(qū)給用戶；二是從空閑區(qū)的底部開始向上劃出SIZE大小的空閑區(qū)給用戶。205.2 連續(xù)內(nèi)存分配分配算法：（1）首次適應(yīng)算法： 要求空閑區(qū)按首址遞增的次

10、序組織空閑區(qū)表（隊(duì)列）。（2）最佳適應(yīng)算法： 要求按空閑區(qū)大小從小到大的次序組成空閑區(qū)表（隊(duì)列）。（3）最壞適應(yīng)算法 要求空閑區(qū)按大小遞減的順序組織空閑區(qū)表（或隊(duì)列）。215.2 連續(xù)內(nèi)存分配例5-1：有作業(yè)序列：作業(yè)A要求18K；作業(yè)B要求25K，作業(yè)C要求30K。系統(tǒng)中空閑區(qū)按三種算法組成的空閑區(qū)隊(duì)列.225.2 連續(xù)內(nèi)存分配（2）動態(tài)分區(qū)的內(nèi)存回收 當(dāng)某一個用戶作業(yè)完成釋放所占分區(qū)時(shí)，系統(tǒng)應(yīng)進(jìn)行回收。在可變式分區(qū)中，應(yīng)該檢查回收區(qū)與內(nèi)存中前后空閑區(qū)是否相鄰，若相鄰，則應(yīng)進(jìn)行合并，形成一個較大的空閑區(qū)，并對相應(yīng)的鏈表指針進(jìn)行修改；若不相鄰，應(yīng)將空閑區(qū)插入到空閑區(qū)鏈表的適當(dāng)位置。235.2

11、連續(xù)內(nèi)存分配245.2 連續(xù)內(nèi)存分配5.2.3 碎片問題在連續(xù)內(nèi)存分配中，必須把一個系統(tǒng)程序或用戶程序裝入一個連續(xù)的內(nèi)存空間中。由于各個進(jìn)程不但的申請和釋放內(nèi)存，導(dǎo)致在內(nèi)存中出現(xiàn)大量的分散的小空閑區(qū)。內(nèi)存中這種容量太小、無法利用的小分區(qū)稱做“碎片”或“零頭”。根據(jù)碎片出現(xiàn)的位置，可以分為內(nèi)部碎片和外部碎片兩種。在一個分區(qū)內(nèi)部出現(xiàn)的碎片（即被浪費(fèi)的空間）稱做內(nèi)部碎片。在所有分區(qū)之外新增的碎片稱做外部碎片。解決碎片問題最簡單的方法是定時(shí)或在分配內(nèi)存時(shí)把所有碎片合并為一個連續(xù)區(qū)。實(shí)現(xiàn)的方法是移動某些已分配區(qū)的內(nèi)容，使所有進(jìn)程的分區(qū)緊挨在一起，而把空閑區(qū)留在另一端，這種技術(shù)稱為緊縮（或拼湊）。255.

12、2 連續(xù)內(nèi)存分配例題5-2:某操作系統(tǒng)采用可變分區(qū)分配存儲管理方法,用戶區(qū)大小為512K且初始值為0,用空閑分區(qū)表管理空閑分區(qū)。若分配時(shí)采用分配空閑區(qū)低地址部分的方案，且初始時(shí)用戶區(qū)的512K空間空閑，對于下列申請序列： 申請300K，申請100K，釋放300K，申請150K，申請30K，申請40K，申請60K，釋放30K 回答下列問題： （1）請分別畫出采用首次適應(yīng)算法、最佳適應(yīng)算法進(jìn)行內(nèi)存分配和回收后的內(nèi)存使用狀態(tài)。 （2）如果再申請100K，針對上述兩種算法會有什么結(jié)果？26例題5-2解答如下：150K作業(yè)40K作業(yè)60K作業(yè)100K作業(yè)0150K180K220K280K300K400K

13、512K-1首次適應(yīng)算法150K作業(yè)60K作業(yè)100K作業(yè)40K作業(yè)0150K210K300K400K430K470K512K-1最佳適應(yīng)算法275.3 內(nèi)存不足的管理5.3.1 覆蓋 覆蓋技術(shù)是基于這樣一種思想提出來的：一個程序并不需要一開始就把它的全部指令和數(shù)據(jù)都裝入內(nèi)存后再執(zhí)行。在單CPU系統(tǒng)中，每一時(shí)刻事實(shí)上只能執(zhí)行一條指令。因此，不妨把程序劃分為若干個功能上相對獨(dú)立的程序段，按照程序的邏輯結(jié)構(gòu)讓那些不會同時(shí)執(zhí)行的程序段共享同一塊內(nèi)存區(qū)。通常，這些程序段都被保存在外存中，當(dāng)有關(guān)程序段的先頭程序段已經(jīng)執(zhí)行結(jié)束后，再把后續(xù)程序段調(diào)入內(nèi)存覆蓋前面的程序段。這使得用戶看來，好像內(nèi)存擴(kuò)大了，從而

14、達(dá)到了內(nèi)存擴(kuò)充的目的。285.3 內(nèi)存不足的管理 例如，設(shè)某進(jìn)程的程序正文段由A，B，C，D，E和F等6個程序段組成。它們之間的調(diào)用關(guān)系如下圖所示，程序段A調(diào)用程序段B和C，程序段B又調(diào)用程序段F,程序段C調(diào)用程序段D和E。295.3 內(nèi)存不足的管理5.3.2 交換技術(shù) 交換是指先將內(nèi)存某部分的程序或數(shù)據(jù)寫入外存交換區(qū)，再從外存交換區(qū)中調(diào)入指定的程序或數(shù)據(jù)到內(nèi)存中來，并讓其執(zhí)行的一種內(nèi)存擴(kuò)充技術(shù) 。305.4 分頁管理5.4.1 分頁管理的基本原理把用戶程序的地址空間劃分成若干大小相等的區(qū)域，每個區(qū)域稱作頁面或頁。每個頁都有一個編號，叫做頁號。頁號一般從0開始編號，如0，1，2，等。把內(nèi)存空間

15、劃分成若干和頁大小相同的物理塊，這些物理塊叫“幀”(frame)或內(nèi)存塊。同樣，每個物理塊也有一個編號，塊號從0開始依次順序排列。 以頁為單位進(jìn)行內(nèi)存分配，并按作業(yè)的頁數(shù)多少來分配。邏輯上相鄰的頁，物理上不一定相鄰。315.4 分頁管理325.4 分頁管理在分頁系統(tǒng)中，頁面的大小是由硬件的地址結(jié)構(gòu)所決定的。機(jī)器確定、頁面大小便確定了。一般來說，頁面的大小選擇為2的若干次冪，根據(jù)計(jì)算機(jī)結(jié)構(gòu)的不同，其大小從512B到16MB不等。 在分頁系統(tǒng)中，由CPU生成的每個地址被硬件分成兩個部分：頁號（p）和頁內(nèi)偏移（w）。通常，如果邏輯地址空間為2m，且頁的大小為2n單元（字節(jié)或詞），那么邏輯地址的高mn

16、位表示頁號，而低n位表示頁偏移。這樣，一個地址長度為20位的計(jì)算機(jī)系統(tǒng)，如果每頁的大小為1KB(210) ，那么可以有210個頁。335.4 分頁管理0111231頁號P頁內(nèi)位移量W編號01048575相對地址04095 對于某臺具體機(jī)器來說，其地址結(jié)構(gòu)是一定的。如果給定的邏輯地址是A，頁面的大小為L，則頁號p和頁內(nèi)地址w可按下式求得： p=INTA/L，w=A MOD L 其中，INT是向下整除的函數(shù)，MOD是取余函數(shù)。例如，設(shè)系統(tǒng)的頁面大小為1KB,A=3456,則p=INT(3456/1024)=3，w= 3456 MOD 1024=384。345.4 分頁管理在分頁系統(tǒng)中，允許將進(jìn)程的

17、各頁離散地裝入內(nèi)存的任何空閑塊中，這樣就出現(xiàn)進(jìn)程頁號連續(xù)，而塊號不連續(xù)的情況。為了找到每個頁面在內(nèi)存中對應(yīng)的物理塊，系統(tǒng)為每個進(jìn)程設(shè)立一張頁面映射表，簡稱頁表。進(jìn)程的所有頁依次在頁表中有一個頁表項(xiàng)，其中記載了相應(yīng)頁面在內(nèi)存中對應(yīng)的物理塊號。進(jìn)程執(zhí)行時(shí)，按照邏輯地址中的頁號查找頁表中對應(yīng)的項(xiàng)，找到該頁在內(nèi)存中物理塊號。頁表的作用就是實(shí)現(xiàn)頁號到物理塊號的地址映射。355.4 分頁管理5.4.2 地址映射設(shè)頁長為1K，程序地址字長為16位，用戶程序空間和頁表如圖。365.4 分頁管理例題與習(xí)題：例5-1：設(shè)有8頁的邏輯地址空間，每頁有1024個字節(jié)，它們被映射到32塊的的物理存儲區(qū)，那么邏輯地址的有

18、效為是多少，物理地址至少多少位？例5-2：在一分頁系統(tǒng)中，邏輯地址的長度為16位，頁面大小為4096字節(jié)，現(xiàn)有一邏輯地址2F6AH，且第0、1、2頁依次存放在物理塊5、10、11中，問相應(yīng)的物理地址是多少？例5-3：在某分頁系統(tǒng)，主存的容量為64K，頁面的大小為1K，對于一個4頁大的作業(yè)，其0、1、2、3頁分別被分配到主存的2、4、6、7塊中，試將十進(jìn)制的邏輯地址1023、2500、3500和4500轉(zhuǎn)化成物理地址。375.4 分頁管理快表和聯(lián)想寄存器由于頁表是駐留在內(nèi)存的某個固定區(qū)域中，而取數(shù)據(jù)或指令又必須經(jīng)過頁表變換才能得到實(shí)際物理地址。因此，取一個數(shù)據(jù)或指令至少要訪問內(nèi)存兩次以上。一次訪

19、問頁表以確定所取數(shù)據(jù)或指令的物理地址，另一次是根據(jù)地址取數(shù)據(jù)或指令，這比通常執(zhí)行指令的速度慢了一倍。 解決這個問題的一種方法是把頁表放在一組快速存儲器中（Cache），從而加快訪問內(nèi)存的速度。我們把這種快速存儲器組成的頁表稱為快表，把存放在內(nèi)存中的頁表稱為慢表?？毂碛纸邢嗦?lián)(聯(lián)想)存儲器（associative memory）。385.4 分頁管理關(guān)于聯(lián)想寄存器的討論: 一個程序可能會很大，如1M，若頁長為1K，則該程序有1000個頁，則該程序的頁表就需要1000個表項(xiàng)，當(dāng)程序更大時(shí)，頁表會更大，那么我們應(yīng)該有一個多大的快速存儲器才能滿足要求呢？這會遇到兩個問題：可能快速存儲器多大都是不夠的，

20、因?yàn)槌绦蚩赡軙蟆？焖俅鎯ζ魇欠浅７浅０嘿F的。 實(shí)際上我們并不需要一個很大的快速存儲器，有一個能存放16個頁表表目的快速存儲器就夠了。395.4 分頁管理 例題: 假定訪問主存時(shí)間為100毫微秒，訪問相聯(lián)存儲器時(shí)間為20毫微秒，相聯(lián)存儲器為32個單元時(shí)快表命中率可達(dá)90%，按邏輯地址存取的平均時(shí)間為：（10020）90%(100+100+20)(1-90%)130毫微秒 比兩次訪問主存的時(shí)間100毫微秒2200毫微秒下降了四成多。40p頁表地址越界 l比較P=1pp.快表 b+頁號p 頁內(nèi)地址dPd物理地址頁表地址寄存器頁表長度寄存器邏輯地址415.4 分頁管理5.4.3 頁表的結(jié)構(gòu)CPU具

21、有32位地址時(shí) ,使用232邏輯地址空間的分頁系統(tǒng),規(guī)定頁面4KB時(shí),每個進(jìn)程頁表的表項(xiàng)有1兆(220)個,若表項(xiàng)占用4個字節(jié),則每個進(jìn)程需要占用4KB連續(xù)內(nèi)存空間存放頁表。多級頁表概念：頁表和頁面一樣也進(jìn)行分頁，內(nèi)存僅存放當(dāng)前使用的頁表,暫時(shí)不用部分放在磁盤上,待用到時(shí)再行調(diào)進(jìn)。具體做法：把整個頁表進(jìn)行分頁,分成一張張小頁表(稱為頁表頁) ,小頁表的大小與頁框相同，為進(jìn)行索引查找,應(yīng)該為這些小頁表建一張頁目錄表,其表項(xiàng)指出小頁表所在頁框號及相關(guān)信息。425.4 分頁管理系統(tǒng)為每個進(jìn)程建一張頁目錄表,它的每個表項(xiàng)對應(yīng)一個頁表頁,而頁表頁的每個表項(xiàng)給出了頁面和頁框的對應(yīng)關(guān)系,頁目錄表是一級頁表,

22、頁表頁是二級頁表。邏輯地址結(jié)構(gòu)有三部分組成：頁目錄、頁表頁和位移。435.4 分頁管理在具有兩級頁表結(jié)構(gòu)的系統(tǒng)中，地址轉(zhuǎn)換的方法是：利用外層頁號p1檢索外層頁表，從中找到相應(yīng)內(nèi)層頁表的基址，在利用p2作為該內(nèi)層頁表的索引，找到該頁面在內(nèi)存的塊號，用該塊號和頁內(nèi)地址d拼接起來形成訪問物塊內(nèi)存的物理地址。 445.4 分頁管理5.4.4 頁面的共享設(shè)想一下這樣的系統(tǒng)，有40個用戶，每個用戶都執(zhí)行一個文本編輯器。如果文本編輯器有150KB代碼段和50KB數(shù)據(jù)段，需要8000KB來支持40個用戶。如果代碼是可重入代碼，那么就可以共享?？芍厝氪a（或純代碼）是在其執(zhí)行過程中本身不做任何修改的代碼，通常由

23、指令和常數(shù)組成。共享頁面時(shí)只需要在物理內(nèi)存中保存一個編輯器的拷貝。每個用戶的頁表映射到編輯器的同一物理拷貝，而數(shù)據(jù)頁映射到不同的幀。 455.4 分頁管理465.5 分段存儲管理5.5.1 分段存儲管理的基本原理用戶程序劃分：按程序自身的邏輯關(guān)系劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。段號從0開始，每一段段內(nèi)也從0開始編址，段內(nèi)地址是連續(xù)的。邏輯地址：段號 段內(nèi)地址內(nèi)存劃分：內(nèi)存空間被動態(tài)的劃分為若干個長度不相同的區(qū)域，稱為物理段，每個物理段由起始地址和長度確定。內(nèi)存分配：以段為單位分配內(nèi)存，每一個段在內(nèi)存中占據(jù)連續(xù)空間（內(nèi)存隨機(jī)分割，需要多少分配多少），但各段之間可以不連續(xù)

24、存放。475.5 分段存儲管理.0S工作區(qū)段B主程序段M.0EP子程序段X0K.CALL X E.CALL Y FCALL A 116.0FL子程序段Y0116N數(shù)組A12345.485.5 分段存儲管理5.5.2 分段存儲管理的地址映射495.5 分段存儲管理分段存儲存儲管理的地址轉(zhuǎn)換過程： 一個邏輯地址由兩部分組成：段號s和段內(nèi)地址d。系統(tǒng)根據(jù)段表地址寄存器的內(nèi)容（表示段表的起始地址）找到進(jìn)程的段表，以段號為索引查找相應(yīng)的表項(xiàng)，得出該段的長度limit及該段在內(nèi)存的起始地址base。將段內(nèi)地址d與段長limit進(jìn)行比較。如果d不小于limit，這表示地址越界，系統(tǒng)發(fā)出地址越界中斷，終止程序

25、的執(zhí)行；如果d小于limit，則表示地址合法，將段內(nèi)地址d與該段的內(nèi)存始址base相加，得到所要訪問單元的內(nèi)存地址。505.5 分段存儲管理例題：在一分段存儲系統(tǒng)中，其段表如下：段號內(nèi)存起始地址段長01234210235010013501938500209059095試求下列邏輯地址對應(yīng)的物理地址是什么？（1）0：430；（2）1：10；（3）2：500；（4）3：400；（5）4：112；（6）5：32515.5 分段存儲管理5.5.3 段的共享和保護(hù)525.5 分段存儲管理分段和分頁的比較： （1）頁是信息的物理單位，而段是信息的邏輯單位。分頁時(shí)為了實(shí)現(xiàn)離散分配方式，以減少內(nèi)存碎片，提高內(nèi)

26、存利用率?；蛘哒f，分頁僅僅是由于系統(tǒng)管理的需要，而不是用戶的需要。段則是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好地滿足用戶的需要。（2）頁的大小是由系統(tǒng)確定的，由系統(tǒng)把邏輯地址劃分成頁號和頁內(nèi)地址兩部分，整個系統(tǒng)只能有一種大小的頁面；而段的長度卻不固定，決定于用戶的程序。通常由編譯程序在對源碼進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來劃分。（3）分頁的進(jìn)程地址空間是一維的，即單一的線性空間；而分段的進(jìn)程地址空間是二維的，有段號和段內(nèi)地址兩部分組成。535.5 分段存儲管理5.5.4 段頁式存儲管理1.基本思想:（1）作業(yè)地址空間進(jìn)行段式管理。（2）每段內(nèi)再分成若干大小固定的頁，

27、每段都從零開始為自己的各頁依次編寫連續(xù)的頁號。（3）對內(nèi)存空間的管理仍然和分頁存儲管理一樣，將其分成若干個和頁面大小相同的物理塊。（4）作業(yè)的邏輯地址包括3個部分：段號、頁號和頁內(nèi)位移。（5）為實(shí)現(xiàn)地址變換，段頁式系統(tǒng)設(shè)立了段表和頁表。545.5 分段存儲管理555.5 分段存儲管理2.地址轉(zhuǎn)換過程:565.6 虛擬存儲器 前面所介紹的各種存儲管理方式，有一個共同的特點(diǎn)，即它們都要求將一個作業(yè)全部裝入內(nèi)存后才能運(yùn)行，于是，就可能出現(xiàn)以下情況： (1) 有的作業(yè)很大，其所要求內(nèi)存空間超過了內(nèi)存容量，從而導(dǎo)致作業(yè)不能全部被裝入內(nèi)存，以至于該作業(yè)無法運(yùn)行。 (2) 有多個作業(yè)要求運(yùn)行，但可用的內(nèi)存空

28、間不足以容納所有的作業(yè)，只能將少數(shù)的作業(yè)裝入內(nèi)存讓它們先運(yùn)行，而將其他的作業(yè)留在外存等待。575.6 虛擬存儲器 5.6.1 虛擬存儲器的概念 虛擬內(nèi)存（Virtual Memory）是指在具有層次結(jié)構(gòu)存儲器的計(jì)算機(jī)系統(tǒng)中，采用自動實(shí)現(xiàn)部分裝入和部分對換功能，為用戶提供一個比物理主存容量大得多的可尋址的一種“主存儲器”。它使用戶邏輯存儲器與物理存儲器分離，是操作系統(tǒng)給用戶提供的一個比真實(shí)內(nèi)存空間大得多的地址空間 。585.6 虛擬存儲器595.6 虛擬存儲器實(shí)現(xiàn)虛擬存儲器的物質(zhì)基礎(chǔ)是二級存儲器結(jié)構(gòu)和動態(tài)地址轉(zhuǎn)換機(jī)構(gòu)。經(jīng)過操作系統(tǒng)的改造，把計(jì)算機(jī)的內(nèi)存與外存有機(jī)的結(jié)合起來使用，從而得到一個容量很

29、大的“內(nèi)存”，這就是虛存。虛擬存儲器實(shí)質(zhì)上是把用戶地址空間和實(shí)際的存儲空間區(qū)分開來，當(dāng)作兩個不同的概念。它的容量主要受到兩方面的限制：（1）指令中表示地址的字長。一個虛擬存儲器的最大容量是由計(jì)算機(jī)的地址結(jié)構(gòu)確定的。如：若CPU的有效地址長度為32位，則程序可以尋址范圍是0232 -1 ，即虛存容量為 4GB。(2)外存的容量。虛擬存儲器的容量與主存的實(shí)際大小沒有直接的關(guān)系，而是由主存與輔存的容量之和所確定。605.6 虛擬存儲器 5.6.2 虛擬內(nèi)存的特征虛擬性。虛擬內(nèi)存不是擴(kuò)大實(shí)際的物理內(nèi)存，而是擴(kuò)充邏輯內(nèi)存的容量。部分裝入。每個進(jìn)程不是全部裝入內(nèi)存，而是分成若干個部分。當(dāng)進(jìn)程需要執(zhí)行時(shí)，才

30、將當(dāng)前運(yùn)行所需要的程序和數(shù)據(jù)裝入內(nèi)存。對換性。在一個進(jìn)程運(yùn)行期間，它所需要的程序和數(shù)據(jù)可以分多次調(diào)入。每次僅僅調(diào)入一部分，以滿足當(dāng)前程序執(zhí)行的需要。而且，在內(nèi)存中那些暫時(shí)不使用的程序和數(shù)據(jù)可以換到外存的交換區(qū)存放，以騰出盡量多的內(nèi)存空間供可運(yùn)行進(jìn)程使用。615.7 請求分頁技術(shù) 5.7.1 請求分頁存儲管理的基本思想請求式分頁也稱虛擬頁式存儲管理，它的基本思想是：在進(jìn)程開始運(yùn)行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根據(jù)進(jìn)程運(yùn)行的需要，動態(tài)裝入其它頁面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時(shí)，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面。 為了實(shí)現(xiàn)頁式虛存，系統(tǒng)需要解決下面三個問題

31、： （1）系統(tǒng)如何獲知進(jìn)程當(dāng)前所需頁面不在主存。 （2）當(dāng)發(fā)現(xiàn)缺頁時(shí)，如何把所缺頁面調(diào)入主存。 （3）當(dāng)主存中沒有空閑的頁框時(shí)，為了要接受一個新頁，需要把老的一頁淘汰出去，根據(jù)什么策略選擇欲淘汰的頁面。625.7 請求分頁技術(shù)駐留位（中斷位）：表示該頁是在內(nèi)存還是在外存訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法決定）修改位：查看此頁是否在內(nèi)存中被修改過頁號中斷位內(nèi)存塊號外存地址訪問位修改位 頁表的擴(kuò)充635.7 請求分頁技術(shù) 程序在執(zhí)行時(shí)，首先檢查頁表，當(dāng)存在位指示該頁不在主存時(shí)，則引起一個缺頁中斷發(fā)生，相應(yīng)的中斷處理程序把控制轉(zhuǎn)向缺頁中斷子程序。執(zhí)行此子程序，即把所缺頁面裝入主存。然后處

32、理機(jī)重新執(zhí)行缺頁時(shí)打斷的指令。這時(shí)，就將順利形成物理地址。缺頁中斷的處理過程是由硬件和軟件共同實(shí)現(xiàn)的。 缺頁中斷645.7 請求分頁技術(shù)655.7 請求分頁技術(shù)缺頁中斷同一般中斷都是中斷，相同點(diǎn)是： 保護(hù)現(xiàn)場 中斷處理 恢復(fù)現(xiàn)場不同點(diǎn)：一般中斷是一條指令完成后中斷，缺頁中斷是一條指令執(zhí)行時(shí)中斷一條指令執(zhí)行時(shí)可能產(chǎn)生多個缺頁中斷。如指令可能訪問多個內(nèi)存地址，這些地址在不同的頁中。665.7 請求分頁技術(shù) 5.7.2 頁面置換算法1.最佳置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。 其所選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時(shí)間內(nèi)不再被訪問的頁面。采

33、用最佳置換算法，通常可保證獲得最低的缺頁率。假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考慮有以下的頁面號引用串： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 675.7 請求分頁技術(shù)685.7 請求分頁技術(shù)2.先進(jìn)先出(FIFO)頁面置換算法 FIFO算法是最早出現(xiàn)的頁面置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中停留時(shí)間最長（年齡最老）的一頁予以淘汰 。695.7 請求分頁技術(shù) 為了說明FIFO頁面置換算法相關(guān)的可能問題，考慮一下引用串：1，2，3，4，1，2，5，1，2，3，4，5。注意到對4個可用內(nèi)存塊的缺頁次數(shù)（10）比3個內(nèi)存塊的缺頁次數(shù)（

34、9）還要大。這種令人難以相信的結(jié)果稱為Belady異常現(xiàn)象，即缺頁次數(shù)隨內(nèi)存塊增加而增加。 705.7 請求分頁技術(shù)3.最近最久未使用(LRU)置換算法 最近最久未使用置換算以“最近的過去”作為“不久將來”的近似，選擇最近一段時(shí)間內(nèi)最久沒有使用的頁面淘汰掉。它的實(shí)質(zhì)是：當(dāng)需要置換一頁時(shí)，選擇在最近一段時(shí)間里最久沒有使用過的頁面予以淘汰 。715.7 請求分頁技術(shù)4. LRU的近似算法 （1）附加引用位算法通過在規(guī)定時(shí)間間隔里記錄引用位，能獲得額外順序信息?？梢詾槲挥趦?nèi)存中的每個頁表中的每一頁保留一個8 bit的字節(jié)。在規(guī)定的時(shí)間間隔（如，每100ms）內(nèi)，時(shí)鐘定時(shí)器產(chǎn)生中斷并將控制權(quán)交給操作系統(tǒng)。操作系統(tǒng)把每個頁的引用位轉(zhuǎn)移到其8 bit字節(jié)的高位，而將其他位右移，并拋棄最低位。這些8 bit移位寄存器包含著該頁在最近8個時(shí)間周期內(nèi)的使用情況。如果移位寄存器含有，那么該頁在8個時(shí)間周期內(nèi)沒有使用；如果移位寄存器的值為，那么該頁在過去每個周期內(nèi)都至少使用過一次。具有值為的移位寄存器的也要比值為的頁使用更為頻繁。如果將這8 bit字節(jié)作為無符號整數(shù)，那么具有最小值的頁為LRU頁，可以被置換出去。如果這個數(shù)字不惟一，可以置換所有具有最小值的頁或在這些頁之間采用FIF