操作系統(tǒng),第3章存儲管理

1、第3章 存儲管理 v 本章學(xué)習(xí)目標(biāo) v3.1 存儲管理概述 v3.2 連續(xù)分配存儲管理方式 v3.3 頁式存儲器管理 v3.4 段式存儲管理v3.5 段頁式存儲管理v3.6 虛擬存儲器v3.7 請求分頁存儲管理v3.8 請求分段存儲管理本章目標(biāo)本章目標(biāo) v理解與掌握存儲管理的功能。v理解與掌握單用戶連續(xù)、固定分區(qū)和可變分區(qū)存儲管理方式。v理解與掌握頁式存儲管理方式。v了解段式、段頁式存儲管理方式。v理解請求頁式虛擬存儲管理方式。本章學(xué)習(xí)目標(biāo) v本章首先介紹了存儲管理的研究對象和目的，明確了存儲管理的基本功能和有關(guān)的基本概念；然后從實(shí)存和虛存兩個(gè)角度，分別介紹了常用的幾種存儲管理方案；最后對各種

2、存儲管理方案存在的問題，主要是碎片和抖動問題進(jìn)行了總結(jié)。 本章的主要內(nèi)容如下：v(1)存儲管理的目的和四大基本功能。 v(2)實(shí)存管理中講述了固定分區(qū)存儲管理、可變式分區(qū)存儲管理、純分頁存儲管理三種存儲管理方案的實(shí)現(xiàn)原理v(3)虛存管理以請求式分頁存儲管理為重點(diǎn) v(4)總結(jié)各種存儲管理方案中存在的碎片和抖動問題及解決方法3.1 存儲管理的概述 v3.1.1 存儲器的層次結(jié)構(gòu) v3.1.2 存儲管理的功能v3.1.3 地址重定位 多級存儲器體系示意圖多級存儲器體系示意圖3.1.1 存儲器的層次結(jié)構(gòu)內(nèi)存空間的分配和保護(hù)。內(nèi)存儲器中允許同時(shí)容納各種軟件和多個(gè)用戶程序時(shí)，必須解決內(nèi)存空間如何分配以及

3、各存儲區(qū)域內(nèi)的信息如何保護(hù)等問題。內(nèi)存空間的重定位。配合硬件做好地址轉(zhuǎn)換工作，把一組邏輯地址空間轉(zhuǎn)換成絕對地址空間，以保證處理器的正確執(zhí)行。內(nèi)存空間的共享。在多道程序設(shè)計(jì)的系統(tǒng)中，同時(shí)進(jìn)入內(nèi)存儲器執(zhí)行的作業(yè)可能要調(diào)用共同的程序。內(nèi)存空間的擴(kuò)充。提供虛擬存儲器，使用戶編制程序時(shí)不必考慮內(nèi)存儲器的實(shí)際容量，使計(jì)算機(jī)系統(tǒng)似乎有一個(gè)比實(shí)際內(nèi)存儲器容量大的多的內(nèi)存空間。 3.1.2 存儲器的功能1程序的裝入v（1）絕對裝入方式。也稱直接分配方式。這種方式指程序在編寫程序或編譯程序?qū)υ闯绦蚓幾g時(shí)采用實(shí)際存儲地址。采用這種方式，必須事先劃定作業(yè)的可用空間，因此這種絕對裝入方式的存儲分配，存儲空間的利用率不高

4、，對用戶使用也不方便。v（2）可重定位方式。也稱靜態(tài)分配方式。在將作業(yè)裝入內(nèi)存時(shí)才確定它們在內(nèi)存中的位置。也就是說，存儲空間的分配是在作業(yè)裝入內(nèi)存時(shí)實(shí)現(xiàn)的。采用這種裝入方式，在一個(gè)作業(yè)裝入時(shí)必須分配其要求的全部存儲量；如果沒有足夠的存儲空間，就不能裝入該作業(yè)。此外，作業(yè)一旦進(jìn)入內(nèi)存后，在整個(gè)運(yùn)行過程中不能在內(nèi)存中移動，也不能再申請內(nèi)存空間。這種裝入方式實(shí)際上就是靜態(tài)重定位靜態(tài)重定位。v（3）動態(tài)運(yùn)行時(shí)裝入方式。 3.1.3 地址重定位2地址重定位基本概念地址重定位基本概念（1）邏輯地址）邏輯地址 一個(gè)應(yīng)用程序經(jīng)編譯后，通常會形成若干個(gè)目標(biāo)程序，這些目標(biāo)程序再經(jīng)過連接而形成可裝入程序。這些程序的

5、地址都從“0”開始的，程序中的其他地址都是相對于起始地址計(jì)算；由這些地址所形成的地址范圍稱為地址空間，其中的地址稱為邏輯地址邏輯地址或相對地址。（2）絕對地址）絕對地址 當(dāng)用戶把作業(yè)交給計(jì)算機(jī)執(zhí)行時(shí)，存儲管理就為其分配一個(gè)合適的內(nèi)存空間，這個(gè)分配到的內(nèi)存空間可能是從“A”單元開始的一個(gè)連續(xù)地址空間，稱為“絕對地址”空間，其中的地址稱為物理地址或絕對地址。（3）地址重定位）地址重定位 由于邏輯地址經(jīng)常與分到的內(nèi)存空間的絕對地址不一致，而且對于每個(gè)邏輯地址在內(nèi)存儲器中也沒有一個(gè)固定的絕對地址與之對應(yīng)。因此，不能根據(jù)邏輯地址直接到內(nèi)存儲器中去存取信息。由于處理器執(zhí)行指令是按絕對地址進(jìn)行的，為了保證作

6、業(yè)的正確執(zhí)行，必須根據(jù)分配到的內(nèi)存區(qū)域?qū)λ闹噶詈蛿?shù)據(jù)進(jìn)行重定位，即把邏輯地址轉(zhuǎn)換成絕對地址。把邏輯地址轉(zhuǎn)換成絕對地址的工作稱為地址轉(zhuǎn)地址轉(zhuǎn)換換或地址重定位地址重定位或地址映射地址映射。 3靜態(tài)、動態(tài)重定位靜態(tài)、動態(tài)重定位 重定位的方式可以有靜態(tài)定位靜態(tài)定位和動態(tài)定位動態(tài)定位兩種。（1）靜態(tài)重定位）靜態(tài)重定位 靜態(tài)重定位在裝入一個(gè)作業(yè)時(shí)，把作業(yè)中的指令地址和數(shù)據(jù)地址全部轉(zhuǎn)換成絕對地址。由于地址轉(zhuǎn)換工作是在作業(yè)執(zhí)行前集中一次完成的，所以在作業(yè)執(zhí)行過程中就無需進(jìn)行地址轉(zhuǎn)換工作。這種定位方式稱靜態(tài)重定位靜態(tài)重定位。 （2）動態(tài)重定位）動態(tài)重定位 動態(tài)重定位是在程序執(zhí)行過程中，每當(dāng)訪問指令或數(shù)據(jù)時(shí)，將

7、要訪問的程序或數(shù)據(jù)的邏輯地址轉(zhuǎn)換成物理地址。由于重定位過程是在程序執(zhí)行期間隨著指令的執(zhí)行逐步完成的，故稱為動態(tài)重定位動態(tài)重定位。 150011001250作業(yè)地址空間存儲地址空間0LOAD 1,25031002505001000LOAD 1,12503圖3.3 動態(tài)重定位過程重定位寄存器具+邏輯地址作業(yè)地址空間存儲地址空間0LOAD 1,25031002505001000LOAD 1,125031100125015002501000（b）采用動態(tài)重定位時(shí)內(nèi)存空間及地址重定位示意圖 （a）采用靜態(tài)重定位后的內(nèi)存空間 靜態(tài)地址重定位和動態(tài)地址重定位示意圖靜態(tài)地址重定位和動態(tài)地址重定位示意圖3.2

8、連續(xù)分配存儲管理方式 v3.2.1 單用戶連續(xù)存儲管理v3.2.2 固定分區(qū)存儲管理v3.2.3 可變分區(qū)存儲管理1. 單用戶連續(xù)存儲管理單用戶連續(xù)存儲管理 單用戶連續(xù)存儲管理方式是一種最簡單的存儲管理方式，它只能用于單用戶、單任務(wù)的操作系統(tǒng)中。在這種管理方式下操作系統(tǒng)占了一部分內(nèi)存空間，其余剩下的內(nèi)存空間都分配給一個(gè)作業(yè)使用，即在任何時(shí)刻內(nèi)存儲器中最多只有一個(gè)作業(yè)。 3.2.1 單用戶連續(xù)存儲管理單用戶連續(xù)存儲管理示意圖用戶區(qū)作業(yè)隊(duì)列cb0aOS區(qū)用戶作業(yè)空閑區(qū)CPU界限寄存器a作業(yè)1 作業(yè)2覆蓋技術(shù)示意圖cb0aOS區(qū)覆蓋區(qū)1駐留區(qū)用戶區(qū)D可覆蓋的段覆蓋區(qū)2主程序段DCAB2. 覆蓋（覆蓋

9、（Overly）技術(shù)）技術(shù) 所謂覆蓋覆蓋就是指一個(gè)作業(yè)中的若干程序段和數(shù)據(jù)段共享內(nèi)存的某個(gè)區(qū)域。其實(shí)現(xiàn)的方法是將一個(gè)大的作業(yè)劃分成一系列的覆蓋（程序段），每個(gè)覆蓋是一個(gè)相對獨(dú)立的程序單位，執(zhí)行時(shí)并不要求同時(shí)裝入內(nèi)存的覆蓋組成一組，并稱其為覆蓋段，將一個(gè)覆蓋段分配到同一存儲區(qū)域。 3.交換（交換（Swapping）技術(shù)）技術(shù) 交換（對換）技術(shù)就是把暫時(shí)不用的某個(gè)程序或數(shù)據(jù)部分（或全部）從內(nèi)存移到外存中去， 以便騰出必要的內(nèi)存空間；或把指定的程序或數(shù)據(jù)從外存讀到相應(yīng)的內(nèi)存中，并將控制權(quán)轉(zhuǎn)給它，讓其在系統(tǒng)上運(yùn)行的一種內(nèi)存擴(kuò)充技術(shù) 。 內(nèi)存外存交換交換示意圖 固定分區(qū)存儲管理是在作業(yè)裝入前，內(nèi)存用戶區(qū)

10、被劃分成若干個(gè)大小不等連續(xù)區(qū)域，每一個(gè)連續(xù)區(qū)稱為一個(gè)分區(qū)，每個(gè)分區(qū)可以存放一個(gè)作業(yè)。一旦劃分好后，內(nèi)存儲器中分區(qū)的個(gè)數(shù)就固定了。各個(gè)分區(qū)的大小可以相同，也可以不同，每個(gè)分區(qū)的大小固定不變，因此，也把固定分區(qū)稱為靜態(tài)分區(qū)。各分區(qū)的使用情況，用“分區(qū)分配表”來說明 。3.2.2 固定分區(qū)存儲管理固定分區(qū)存儲管理示意圖e作業(yè)隊(duì)列b0aOS區(qū)CPU上限寄存器d作業(yè)1 作業(yè)2c3下限寄存器正運(yùn)行作業(yè)分區(qū)分區(qū)1分區(qū)2分區(qū)3空閑區(qū)d分區(qū)號起始地址長度占用標(biāo)志1aL102bL203cL31分區(qū)分配表分區(qū)分配表 下限地址絕對地址塊號 頁內(nèi)地址p頁表始址 頁表長度bmnbd物理地址越界中斷頁號 頁內(nèi)地址邏輯地址p

11、dCPU+3.3.3 快表具有快表地址變換機(jī)構(gòu)示意圖快表頁號 塊號b頁表塊號 頁內(nèi)地址p頁表始址 頁表長度頁表寄存器bmnbd物理地址越界中斷頁號 頁內(nèi)地址邏輯地址pd輸入寄存器內(nèi)存 分頁式存儲管理把內(nèi)存儲器的可分配區(qū)域按頁面大小分成若干塊，分配內(nèi)存空間按塊為單位?？捎靡粡垉?nèi)存分配表來記錄已分配的塊和尚未分配的塊以及當(dāng)前剩余的空閑塊數(shù)。由于塊的大小是固定的，所以可以用一張“位示圖”來構(gòu)成內(nèi)存分配表。 3.3.4 分頁式存儲空間的分配與回收0310/10/1 0/1 0/1 0/10/1 0/1 0/1 0/1 0/1剩余塊數(shù)0/10/10/10/10/10/1分頁存儲管理內(nèi)存分配表 分頁存儲管

12、理能方便地實(shí)現(xiàn)多個(gè)作業(yè)共享程序和數(shù)據(jù)。 頁的共享可節(jié)省內(nèi)存空間，但實(shí)現(xiàn)信息共享必須解決共享信息的保護(hù)問題。通常的辦法是在頁表中增加一些標(biāo)志，指出該頁的信息可讀/寫、只讀、只可執(zhí)行等等。3.3.5 頁的共享與保護(hù)第100塊第200塊內(nèi)存作業(yè)1頁表頁號標(biāo)志塊號0只執(zhí)行 1001讀/寫2002讀/寫3003只讀30作業(yè)2頁表頁號標(biāo)志塊號0只執(zhí)行 1001讀/寫2322讀/寫4243讀/寫5684只讀200共享程序共享數(shù)據(jù) 目前，大多數(shù)計(jì)算機(jī)系統(tǒng)都支持非常大的邏輯地址空間。在這樣的環(huán)境下，頁表就變得非常大，要占用很大的內(nèi)存空間。而且頁表還要求存放在連續(xù)的存儲空間中，顯然這是不現(xiàn)實(shí)的，可以采用以下兩種途

13、徑解決這一問題。 （1）對頁表所需的內(nèi)存空間，采用離散的分配方式； （2）只將當(dāng)前需要的部分頁表項(xiàng)調(diào)入內(nèi)存，其余的頁表項(xiàng)當(dāng)需要時(shí)再調(diào)入。 3.3.6 兩級和多級頁表v兩級頁表：兩級頁表：對于支持32位邏輯地址空間的計(jì)算機(jī)系統(tǒng)可以采用兩級頁表。就是將頁表再分頁，形成兩級頁表，。比如當(dāng)一個(gè)32位系統(tǒng)的頁大小為4KB，那么邏輯地址被分為20bit的頁號和12bit頁內(nèi)地址。如果采用兩級頁表結(jié)構(gòu)，對頁表進(jìn)行再分頁，使每個(gè)頁中包含1024個(gè)頁表項(xiàng)，最多允許有1024個(gè)頁表分頁，或者說，外層頁表中的外層頁內(nèi)地址p2為10位，外層頁號p1也為10位。v多級頁表多級頁表：兩級頁表結(jié)構(gòu)適合32位的機(jī)器，但是對于

14、64位機(jī)器，兩級頁表結(jié)構(gòu)就不再合適了。 外層頁號外層頁內(nèi)地址頁內(nèi)地址31 2221 1211 0p1p2d兩級頁表地址結(jié)構(gòu)3.4 段式存儲管理 v3.4.1 引入的原因v3.4.2 段式存儲管理基本思想v3.4.3 地址變換機(jī)構(gòu)與存儲保護(hù)3.4.1 引入的原因 在分頁存儲管理中，用戶程序的地址空間是從0開始編址的單一連續(xù)的邏輯地址。雖然操作系統(tǒng)可把程序劃分成若干個(gè)頁面，但是頁面與源程序無邏輯關(guān)系，也就難以實(shí)現(xiàn)對源程序以模塊為單位進(jìn)行分配、共享和保護(hù)。 在段式存儲管理中，段是一組邏輯信息（獨(dú)立信息段）的集合。在單純的分頁存儲管理中，這些信息都混在一起，并統(tǒng)一編址，顯然，分頁系統(tǒng)并不是編程人員愿意

15、接受的信息組織方式。因此按照信息原有的方式組織數(shù)據(jù)是必要的，也是支持高級語言必要的。 3.4.2 段式存儲管理基本思想 在編制程序時(shí)每一段都可獨(dú)立編制，每一段的邏輯地址都是從“0”開始編址，每段的長度不一定相同，形成了段內(nèi)地址是連續(xù)段內(nèi)地址是連續(xù)的，而段與段之間的地址是不連續(xù)段與段之間的地址是不連續(xù)的。 當(dāng)作業(yè)被裝入內(nèi)存儲器時(shí)，以段為單位為作業(yè)的每一段分配一個(gè)連續(xù)的內(nèi)存區(qū)域 ，各段之間也可不必連續(xù) ，分配方法同可變分區(qū)方式 。 裝入作業(yè)時(shí)，用一張段表記錄該作業(yè)每個(gè)分段在內(nèi)存中起始地址和長度 。31 16 15 0段號S段內(nèi)地址d段式存儲管理地址結(jié)構(gòu)段式存儲管理原理圖作業(yè)空間040K120K16

16、0K200K210段長 基址8KB10KB5KB18KB120K160K200K40KS0段號3S1S2S3內(nèi)存空間S0 18KBS2 10KBS3 5KBS1 8KB段表3.4.3 地址變換機(jī)構(gòu)與存儲保護(hù)1.地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)段式地址變換過程0段號 段長 基址pp-1段表內(nèi)存段表始址 段表長度段表寄存器m fsn物理地址越界中斷段號 段內(nèi)地址邏輯地址pdCPU2.共享與保護(hù)共享與保護(hù) 段是信息的邏輯單位，段式存儲管理方式可以方便地實(shí)現(xiàn)內(nèi)存的信息共享，并進(jìn)行有效的內(nèi)存保護(hù)。 段式存儲管理的保護(hù)主要有地址越界保護(hù)和存取方式控制保護(hù)。 段的共享200K400K100K200K內(nèi)存作業(yè)1段表段

17、長標(biāo)志始址200K 只執(zhí)行 100K100K 讀/寫 200K300K 讀/寫 300K400K只讀50K作業(yè)2段表段長標(biāo)志始址200K 只執(zhí)行 100K200K 讀/寫 232K320K 讀/寫 424K100K 讀/寫 568K400K只讀200K共享程序共享數(shù)據(jù)始址 段長v（1）頁是信息的物理單位，分頁是由于系統(tǒng)管理的需要。段是信息的邏輯單位，它含有意義相對完整的信息（程序段或數(shù)據(jù)段等）。分段的目的是為了更好的滿足用戶的需要；v（2）頁的大小是固定并且由系統(tǒng)決定，段的長度不定，取決于用戶所編寫的程序，通常由編譯程序在對源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來劃分；v（3）頁式在存儲管理中的邏輯

18、地址空間是一維的，段的邏輯地址空間是二維的；v（4）頁式存儲管理的優(yōu)點(diǎn)是在管理內(nèi)存空間上，而段式存儲管理的優(yōu)點(diǎn)是在管理邏輯地址空間上。3.段式與頁式存儲的區(qū)別段式與頁式存儲的區(qū)別 3.5 段頁式存儲管理 v3.5.1 段頁式存儲管理原理v3.5.2 地址變換3.5.1 段頁式存儲管理原理段頁式存儲管理原理 段頁式存儲管理基本原理是分段和分頁相結(jié)合。內(nèi)存采用分頁存儲管理方式，將內(nèi)存劃分成大小相等的物理塊，用戶程序的邏輯地址空間采用分段方式，按程序的邏輯關(guān)系把地址空間分成若干個(gè)邏輯段，每一段不是按單一的連續(xù)整體存放到內(nèi)存中，而是把每段再分成若干個(gè)頁面，每一段不必占據(jù)連續(xù)的內(nèi)存空間，可把它按頁存放在

19、不連續(xù)的內(nèi)存塊中，每一段中的所有頁必須在其所在每一段中的所有頁必須在其所在的段內(nèi)，即段內(nèi)的頁是離散分配的的段內(nèi)，即段內(nèi)的頁是離散分配的。 段號s段內(nèi)地址d段頁式存儲管理邏輯地址格式段內(nèi)頁號p內(nèi)存段表段表寄存器段表長度 段表始址段號 狀態(tài) 頁表長度 頁表始址0123頁號 狀態(tài)0123塊號頁號 狀態(tài)0123塊號操作系統(tǒng)段頁式存儲管理的地址映射 3.5.2 地址變換地址變換圖3.32 段頁式地址變換過程塊號 塊內(nèi)地址p0121ss-1頁表內(nèi)存段表始址 段表長度段表寄存器mn物理地址越界中斷段號 頁號 頁內(nèi)地址邏輯地址CPUspd 頁表長度頁表始址3.6 虛擬存儲器 v3.6.1 局部性原理v3.6.

20、2 虛擬存儲器的定義和特征v3.6.3 虛擬存儲器的實(shí)現(xiàn)方法 早在1968年P(guān).Denning就指出過，程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律，即在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅限于某個(gè)部分；相應(yīng)的它所訪問的存儲空間也局限于某個(gè)區(qū)域。 局部性表現(xiàn)如下。 （1）時(shí)間局部性。如果程序中的某條指令一旦執(zhí)行，則不久以后該指令可能再次被執(zhí)行；如果某個(gè)存儲單元被訪問，則不久以后該存儲單元可能再次被訪問，產(chǎn)生時(shí)間局部性的典型原因是在程序中存在大量的循環(huán)操作。 （2）空間局部性。一旦程序訪問了某個(gè)存儲單元。則不久以后，其附近的存儲單元也將被訪問，即是程序在一段時(shí)間內(nèi)訪問的地址可能集中在一定范圍內(nèi)，引起空間局部性的典型原

21、因是程序的順序執(zhí)行。3.6.1 局部性原理局部性原理3.6.2 虛擬存儲器的定義和特征虛擬存儲器的定義和特征1.虛擬存儲器定義虛擬存儲器定義 ：就是指把用戶的作業(yè)的一部分裝入內(nèi)存便可運(yùn)行作業(yè)的存儲系統(tǒng)。其實(shí)際上用戶看到的大容量只是一種感覺，是虛的，故而稱為虛擬存儲器。2. 虛擬存儲器特征虛擬存儲器特征（1）離散性。指在內(nèi)存分配時(shí)采用離散分配方式。（2）多次性。指一個(gè)作業(yè)運(yùn)行時(shí)分成多次裝入內(nèi)存。（3）對換性。指作業(yè)運(yùn)行過程中在內(nèi)存和外存的對換區(qū)之間換進(jìn)換出。（4）虛擬性。指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶感覺到的存儲器容量遠(yuǎn)遠(yuǎn)大于實(shí)際的內(nèi)存容量。 3.6.3 虛擬存儲器的實(shí)現(xiàn)方法虛擬存儲器的實(shí)現(xiàn)

22、方法（1）請求頁式存儲管理 請求頁式存儲管理是在頁式存儲管理基礎(chǔ)上增加了請求調(diào)頁功能、頁面置換功能所形成的頁式虛擬存儲分配系統(tǒng)。程序啟動運(yùn)行時(shí)裝入部分用戶程序頁和數(shù)據(jù)頁，在以后的運(yùn)行過程中，訪問到其他邏輯頁時(shí)，再陸續(xù)將所需的頁調(diào)入內(nèi)存中。請求調(diào)頁和置換時(shí)，需要頁表機(jī)構(gòu)、缺頁中斷機(jī)構(gòu)、地址變換機(jī)構(gòu)等硬件支持。（2）請求段式存儲管理 請求段式存儲管理是在段式存儲管理方式的基礎(chǔ)上增加了請求調(diào)段和分段置換功能而形成的段式虛擬存儲管理，只需裝入部分程序段和數(shù)據(jù)段即可啟動運(yùn)行，以后出現(xiàn)缺段時(shí)再動態(tài)調(diào)入。實(shí)現(xiàn)請求分段同樣需要分段的段表機(jī)制、缺段中斷機(jī)構(gòu)、地址變換機(jī)構(gòu)等軟硬件支持。3.7 請求分頁存儲管理v3

23、.7.1 頁表機(jī)制v3.7.2 缺頁中斷v3.7.3 地址變換v3.7.4 頁面分配v3.7.5 頁面淘汰算法3.7.1 頁表機(jī)制頁表機(jī)制 在請求分頁存儲管理的方式中，頁表仍然是重要的數(shù)據(jù)結(jié)構(gòu)，其主要作用是實(shí)現(xiàn)用戶邏輯地址空間中邏輯地址到內(nèi)存空間中的物理地址的變換。在虛擬存儲器中，由于應(yīng)用程序并沒有完全調(diào)入內(nèi)存，所以頁表結(jié)構(gòu)根據(jù)虛擬存儲器的需要增加了若干項(xiàng)，如圖所示。其中：（1）狀態(tài)位P用于該頁是否已調(diào)入內(nèi)存，供程序訪問時(shí)參考；（2）訪問字段A用于記錄本頁在一段時(shí)間內(nèi)被訪問的次數(shù)，或最近多長時(shí)間未被訪問，供轉(zhuǎn)換算法選擇換出頁面時(shí)參考；（3）修改位M表示該頁在調(diào)入內(nèi)存后是否被修改過。（4）外存地

24、址用于指出該頁在外存上的地址，通常是物理塊（簇）號，供調(diào)入該頁時(shí)使用。請求分頁虛擬存儲管理方式的頁表結(jié)構(gòu)頁號塊號狀態(tài)位P 訪問字段A 修改位M外存地址3.7.2 缺頁中斷缺頁中斷 在請求分頁存儲管理中，當(dāng)所要訪問的頁不在內(nèi)存時(shí)，便要產(chǎn)生缺頁中斷，請求操作系統(tǒng)將所缺頁調(diào)入內(nèi)存。缺頁中斷與一般中斷不同，區(qū)別如下。 （1）缺頁中斷是在執(zhí)行一條指令期間時(shí)產(chǎn)生的中斷，并立即轉(zhuǎn)去處理，而一般中斷則是在一條指令執(zhí)行完畢后，當(dāng)發(fā)現(xiàn)有中斷請求時(shí)才去響應(yīng)和處理； （2）缺頁中斷處理完成后，仍返回到原指令去重新執(zhí)行，因?yàn)槟菞l指令并未執(zhí)行。而一般中斷則是返回到下一條指令去執(zhí)行，因?yàn)樯弦粭l指令已經(jīng)執(zhí)行完畢了。3.7.3

25、 地址變換地址變換 請求分頁系統(tǒng)中進(jìn)行地址變換時(shí)，首先要檢測該頁面是否在內(nèi)存，如果該頁面在內(nèi)存中，則地址變換方式與頁式存儲管理方式相同；如果該頁不在內(nèi)存中，則進(jìn)行缺頁中斷處理。進(jìn)行缺頁中斷處理時(shí)首先判斷內(nèi)存空間是否夠用，如果內(nèi)存沒有可用空間，必須進(jìn)行置換以騰出可用空間。越界中斷NNY開始（程序訪問第一頁）頁號頁表長度？訪問頁面Y頁是否在內(nèi)存？調(diào)整頁表形成物理地址地址變換結(jié)束從外存中找到缺頁缺頁中斷處理NY內(nèi)存滿否？淘汰一個(gè)頁面Y該頁是否修改過？N將該頁寫回內(nèi)存將缺頁調(diào)入內(nèi)存調(diào)整頁表請求分頁存儲管理的地址變換過程3.7.4 頁面分配頁面分配 在為進(jìn)程分配物理塊時(shí)，首先考慮的是：保證進(jìn)程能正常運(yùn)行

26、所需要的最少物理塊數(shù)。若系統(tǒng)為某進(jìn)程分配的物理塊數(shù)小于此值時(shí)進(jìn)程將無法運(yùn)行。其次，要考慮的問題是頁面的分配和置換策略。在請求分頁存儲管理中可采用固定和可變兩種分配策略。在進(jìn)程置換時(shí)，也可采用全局置換和局部置換兩種策略。組合成如下三種策略。 （1）固定分配局部置換策略 （2）可變分配全局置換策略 （3）可變分配局部置換策略3.7.5 頁面淘汰算法頁面淘汰算法 發(fā)生缺頁時(shí)，就要從外存上把所需要的頁面調(diào)入到內(nèi)存。如果當(dāng)時(shí)內(nèi)存中有空閑塊，那么頁面的調(diào)入問題就解決了；如果當(dāng)時(shí)內(nèi)存中已經(jīng)沒有空閑塊可供分配使用，那么就必須在內(nèi)存中選擇一頁，然后把它調(diào)出內(nèi)存，以便為即將調(diào)入的頁面讓出塊空間。這就是所謂的“頁面

27、淘汰”問題。選擇淘汰對象有很多種策略可以采用，比如： 1.先進(jìn)先出（FIFO）頁面淘汰算法 (first in firstout,FIFO) 2. 最近最久未使用頁面淘汰算法（Least Recently Used，LRU） 3. 最近最少用頁面淘汰算法（Least Frequently Used，LFU） 4. 最佳頁面淘汰算法（Optimal，OPT）1最優(yōu)算法（最優(yōu)算法（OPT算法算法）v最理想的頁面置換算法是：從內(nèi)存中移出以后不再使用的頁面；如無這樣的頁面，則選擇以后最長時(shí)間內(nèi)不需要訪問的頁。這就是最優(yōu)算法的思想。v這種算法本身不是一種實(shí)際的方法，因?yàn)轫撁嬖L問的順序是很難預(yù)知的。但是，

28、可把它作為一種評價(jià)標(biāo)準(zhǔn)，比較其他實(shí)用方法的優(yōu)劣，所以，最優(yōu)算法只具有理論上的意義。2先進(jìn)先出算法（先進(jìn)先出算法（FIFO算法）算法）v這種算法的基本思想是：總是先淘汰那些駐留在內(nèi)存時(shí)間最長的頁面，即先進(jìn)入內(nèi)存的頁面先被置換掉。理由是：最先進(jìn)入內(nèi)存的頁面不再被訪問的可能性最大。 3最久未使用頁面置換算法（最久未使用頁面置換算法（LRU算法）算法）v這種算法的基本思想是，如果某一頁被訪問了，那么它很可能馬上又被訪問；反之，如果某一頁很長時(shí)間沒有被訪問，那么最近也不太可能會被訪問。這種算法考慮了程序設(shè)計(jì)的局部性原理。其實(shí)質(zhì)是，當(dāng)需要置換一頁時(shí)，選擇在最近一段時(shí)間最久未使用的頁面予以淘汰。v實(shí)現(xiàn)這種算

29、法可通過周期性地對“引用位”進(jìn)行檢查，并利用它來記錄一頁面自上次被訪問以來所經(jīng)歷的時(shí)間t，淘汰時(shí)選擇t最大的頁面。 4LRU近似算法近似算法v這種算法，只要在存儲分塊表（或頁表）中設(shè)一個(gè)“引用位”，當(dāng)存儲分塊表中的某一頁被訪問時(shí)，該位由硬件自動置1，并由頁面管理軟件周期性把所有引用位置0。這樣，在一個(gè)時(shí)間周期T內(nèi)，某些被訪問過的頁面其引用位為1，而未被訪問過的頁面其引用位為0。因此，可根據(jù)引用位的狀態(tài)來判別各頁面最近的使用情況。當(dāng)需要置換一頁面時(shí)，選擇其引用位為0的頁，如圖4.21所示的算法 。圖4.22是這種近似算法的一個(gè)例子。 【例題】在請求頁式存儲管理系統(tǒng)中，設(shè)一個(gè)作業(yè)訪問頁面的序列為4

30、，3，2，1，4，3，5，4，3，2，1，5，設(shè)分配給該作業(yè)的存儲空間有4塊，且最初未裝入任何頁。試計(jì)算FIFO和LRU算法的缺頁率。 解： 采用FIFO頁面淘汰算法，該作業(yè)運(yùn)行時(shí)缺頁情況如表所示時(shí)刻123456789101112訪問頁面432143543215內(nèi)存頁面432111543215432221543214333215432444321543缺頁+從表中可以看出，缺頁中斷次數(shù)為10；缺頁率為f=10/12=83% 采用LRU頁面淘汰算法，該作業(yè)運(yùn)行時(shí)缺頁情況如表所示 時(shí)刻123456789101112訪問頁面432143543215內(nèi)存頁面432143543215432143543214321435432432111543缺頁+從表中可以看出，缺頁中斷次數(shù)為8；缺頁率為f=8/12=67% v3.8.1請求分段存儲管理基本思想 v3.8.2 缺段中斷 v3.8.