操作系統(tǒng)ch3-new.ppt

1、第三章 存儲(chǔ)器管理,3.1 存儲(chǔ)管理的功能,3.1.1 計(jì)算機(jī)系統(tǒng)的多級(jí)存儲(chǔ)結(jié)構(gòu) 目前許多計(jì)算機(jī)把存儲(chǔ)器分為三級(jí)：外部存儲(chǔ)器、主存儲(chǔ)器和高速緩沖存儲(chǔ)器。 本章主要介紹主存儲(chǔ)器空間的管理原理和實(shí)現(xiàn)技術(shù)。,3.1.1計(jì)算機(jī)系統(tǒng)的多級(jí)存儲(chǔ)結(jié)構(gòu),大多數(shù)計(jì)算機(jī)把存儲(chǔ)器分為三級(jí)： 1、外部存儲(chǔ)器（外存或輔存） 2、主存儲(chǔ)器（主存或內(nèi)存） 3、高速緩沖存儲(chǔ)器,用來存放不立即使用的程序和數(shù)據(jù)，當(dāng)用戶的程序運(yùn)行需要它們時(shí)，再從外存把它們讀入到主存儲(chǔ)器。,程序的運(yùn)行總是存放在主存中，以便處理器的訪問。,處理機(jī)取指令和存取數(shù)據(jù)就在高速緩沖存儲(chǔ)器中進(jìn) 行。,速度越來越快，容量越來越小，價(jià)格越來越昂貴。,多級(jí)存儲(chǔ)之間的

2、關(guān)系,3.1.2 存儲(chǔ)管理的任務(wù)和功能,存儲(chǔ)管理的主要任務(wù)如下： （1）為多道程序的并發(fā)執(zhí)行提供良好的環(huán)境。 （2）提高存儲(chǔ)器利用率，盡量減少空閑及不可利用的主存儲(chǔ)器區(qū)域。 （3）邏輯上擴(kuò)充主存空間，使大程序能在小主存中運(yùn)行。 （4）方便用戶使用存儲(chǔ)器，用戶無需考慮存儲(chǔ)器的分配、回收和保護(hù)等工作，這些工作完全由操作系統(tǒng)進(jìn)行管理。,存儲(chǔ)管理的功能：,1.存儲(chǔ)空間的分配和回收 1)記住每個(gè)存儲(chǔ)區(qū)域的狀態(tài) 2)實(shí)施分配 3)接收系統(tǒng)或用戶釋放的存儲(chǔ)區(qū)域，并相應(yīng)地修改主存分配記錄表 2. 地址映射和重定位：程序地址空間中的邏輯地址轉(zhuǎn)換為主存空間中對(duì)應(yīng)的物理地址 3. 存儲(chǔ)共享與保護(hù) 存儲(chǔ)共享兩種含義：

3、1）共同使用存儲(chǔ)空間，各自使用不同的存儲(chǔ)區(qū)域；2）共同使用主存中的某些程序和數(shù)據(jù)區(qū)共享區(qū)。 保護(hù)各存儲(chǔ)區(qū)中的信息不被破壞和偷竊 及共享區(qū)信息的完整性和一致性 。 4. 主存擴(kuò)充：主存單元邏輯上的擴(kuò)充 。,3.2 存儲(chǔ)分配的幾種形式與重定位,3.2.1 存儲(chǔ)分配的幾種形式 ： 1. 直接存儲(chǔ)分配方式 2. 靜態(tài)存儲(chǔ)分配方式 3. 動(dòng)態(tài)存儲(chǔ)分配方式,程序員在編寫程序或編譯程序?qū)υ闯绦蚓幾g時(shí)采用內(nèi)存物理地址。,在將作業(yè)裝入內(nèi)存時(shí)才確定它們?cè)趦?nèi)存中的位置。運(yùn)行中固定不變。,不是一次性將程序全部裝入主存，而是根據(jù)執(zhí)行需要?jiǎng)討B(tài)裝入和回收，也可動(dòng)態(tài)申請(qǐng)存儲(chǔ)空間。 常采用覆蓋與交換技術(shù)實(shí)現(xiàn)。,3.2.2 重定

4、位,3.2.2.1 地址空間和存儲(chǔ)空間 相對(duì)地址 ：編譯系統(tǒng)總是從零號(hào)地址單元開始，為目標(biāo)程序指令順序分配地址。這些地址被稱為相對(duì)地址。 邏輯地址空間 ：相對(duì)地址的集合。 存儲(chǔ)空間：主存中一系列存儲(chǔ)信息的物理單元的集合。 物理（絕對(duì)）地址：物理單元的編號(hào)。 3.2.2.2 重定位的概念 重定位：相對(duì)地址轉(zhuǎn)化為存儲(chǔ)空間中的絕對(duì)地址的地址變換過程，稱為地址重定位，也稱地址映射。 地址重定位的方式：靜態(tài)地址重定位和動(dòng)態(tài)地址重定位,靜態(tài)地址重定位：裝配程序一次完成,0 0 1K 1124 LOAD 1,1524 100 LOAD 1,500 1524 12345 500 12345 2K 1K 程序

5、主存 圖3-2 程序由地址空間裝入存儲(chǔ)空間,動(dòng)態(tài)地址重定位：執(zhí)行中，硬件地址轉(zhuǎn)換機(jī)構(gòu)完成,MA（BR）（VR）,1. 靜態(tài)地址重定位的缺點(diǎn)： 1)用戶程序必須分配一個(gè)連續(xù)的存儲(chǔ)空間。 2)難以實(shí)現(xiàn)程序和數(shù)據(jù)的共享。 2.動(dòng)態(tài)地址重定位的優(yōu)點(diǎn)是： 1)有利于提高主存的利用率和存儲(chǔ)空間使用的靈 活性。 2)有利于程序段的共享實(shí)現(xiàn)。 3)為實(shí)現(xiàn)虛擬存儲(chǔ)管理提供了基礎(chǔ)。 3.動(dòng)態(tài)地址重定位的缺點(diǎn)是： 1)實(shí)現(xiàn)存儲(chǔ)器管理的軟件比較復(fù)雜。 2)需要附加的硬件支持。,3.2.3 覆蓋與交換,1. 覆蓋技術(shù) 把程序劃分為若干個(gè)功能相互獨(dú)立的程序段，讓那些不會(huì)同時(shí)被CPU執(zhí)行的程序段共享同一個(gè)主存區(qū)。通常，這些

6、程序段被保存在外存中，當(dāng)CPU要求某一程序段執(zhí)行時(shí)，才將該程序段裝入主存中覆蓋以前的某一的程序段。對(duì)于用戶看來，主存好像擴(kuò)大了，這便是覆蓋技術(shù)。,覆蓋與交換是從邏輯上擴(kuò)充主存的兩種方法，解決在較小主存空間中如何執(zhí)行大程序的問題。,例： main( ) 10k B(30k) A(40k) C(30k) D(30k) E(40k) 利用覆蓋技術(shù)總共只需 10+40+40=90k內(nèi)存即可,2. 交換技術(shù) 交換技術(shù)指將系統(tǒng)暫時(shí)不用的程序或數(shù)據(jù)部分或全部從主存中調(diào)出，以騰出更大的存儲(chǔ)空間，同時(shí)將系統(tǒng)要求使用的程序和數(shù)據(jù)調(diào)入主存中，并將控制權(quán)轉(zhuǎn)交給它，讓其在系統(tǒng)上運(yùn)行。,交換技術(shù)與覆蓋技術(shù)的區(qū)別： 交換不

7、要求給出覆蓋結(jié)構(gòu)，主要是在進(jìn)程或作業(yè)之間進(jìn)行，而覆蓋則主要是在同一個(gè)進(jìn)程或作業(yè)之間進(jìn)行。交換可以在較小的存儲(chǔ)空間中運(yùn)行較多的作業(yè)或進(jìn)程，覆蓋可以在較小的存儲(chǔ)空間中運(yùn)行比其容量大的作業(yè)或進(jìn)程。,3.3 單道環(huán)境下的存儲(chǔ)管理,單道環(huán)境下的存儲(chǔ)管理: 任一時(shí)刻主存只有一個(gè)用戶程序，且該程序占有的用戶區(qū)域是連續(xù)的。如果系統(tǒng)資源能夠滿足用戶程序要求，則系統(tǒng)分配主存資源給該用戶程序，否則系統(tǒng)無法執(zhí)行該程序，同時(shí)給出相應(yīng)的提示信息。 單道環(huán)境下，一般采用單一連續(xù)存儲(chǔ)管理。 單一連續(xù)存儲(chǔ)管理方式是靜態(tài)存儲(chǔ)分配方式。,系統(tǒng)區(qū) 用戶區(qū) 剩余空閑區(qū) 圖3-5 單一連續(xù)區(qū)管理主存分配,單一連續(xù)存儲(chǔ)管理的算法：,入口

8、挑選一個(gè)作業(yè) N 作業(yè)大小=用戶可用空間？ Y 裝入該作業(yè) 執(zhí)行 結(jié)束,優(yōu)點(diǎn)：管理簡(jiǎn)單，只需很少的軟硬件支持。 缺點(diǎn)： (1)系統(tǒng)的存儲(chǔ)空間浪費(fèi)較大。 (2)當(dāng)正在執(zhí)行的程序因出現(xiàn)等待，處理器就處于空閑狀態(tài)。 (3)主存中的程序和數(shù)據(jù)不能被共享。 (4)系統(tǒng)的外圍設(shè)備也只有一個(gè)程序使用，因此外部設(shè)備利用率低。,3.4 分區(qū)存儲(chǔ)管理,3.4.1 固定分區(qū)法 固定分區(qū)是指系統(tǒng)在初始化時(shí)，將主存空間劃分為若干個(gè)固定大小的區(qū)域。用戶程序在執(zhí)行過程中，不允許改變劃分區(qū)域的大小，只能夠根據(jù)各自的要求，由系統(tǒng)分配一個(gè)存儲(chǔ)區(qū)域。 下圖表示在某一時(shí)刻，進(jìn)程A和B分別被分配到2和3兩個(gè)分區(qū)中，第1和4分區(qū)尚未分配

9、。,分區(qū)說明表: 分區(qū)號(hào)大小 起始 狀態(tài) 116KB 20KB 未分配 264KB 36KB 已分配 380KB 100KB 已分配 4128B 180KB 未分配 固定分區(qū)的存儲(chǔ)分配存儲(chǔ)空間分配情況: 0KB 操作系統(tǒng) 20KB 第1分區(qū) 36KB 進(jìn)程A（10KB） 第2分區(qū) 100KB 進(jìn)程B（28KB） 第3分區(qū) 180KB 第4分區(qū),0KB 操作系統(tǒng) 20KB 第1分區(qū) 36KB 進(jìn)程A（10KB） 第2分區(qū) 100KB 進(jìn)程B（28KB） 第3分區(qū) 180KB 第4分區(qū) 圖3-7 固定分區(qū)的存儲(chǔ)分配存儲(chǔ)空間分配情況,作業(yè)zy請(qǐng)求dk內(nèi)存：,I=0 I=I+1 查看第I個(gè)分區(qū) Y N

10、 占用標(biāo)志是否為0 N N 長(zhǎng)度=d k? 是否為最后一個(gè)分區(qū) Y Y 裝入作業(yè) 暫時(shí)無法裝入,固定分區(qū)的優(yōu)缺點(diǎn)：,優(yōu)點(diǎn)：簡(jiǎn)單。 缺點(diǎn)：雖然可以使多個(gè)作業(yè)在同一時(shí)刻共享存儲(chǔ)區(qū)，但它不能充分利用存儲(chǔ)器資源。 “碎片”或“內(nèi)零頭”：在已分配的分區(qū)中，通常都有一部分未被進(jìn)程占用而浪費(fèi)的主存空間，這一部分空間稱作為存儲(chǔ)器的“碎片”或“內(nèi)零頭”。,3.4.2 動(dòng)態(tài)分區(qū)法,1. 動(dòng)態(tài)分區(qū)的基本概念 動(dòng)態(tài)分區(qū)分配方式，在系統(tǒng)初啟時(shí)，除了操作系統(tǒng)常駐主存部分以外，只存在一個(gè)空閑分區(qū)。隨后，分配程序?qū)⒃搮^(qū)依次劃分給調(diào)度程序選中的進(jìn)程，并且分配的大小可隨用戶進(jìn)程對(duì)主存的要求而改變，這種分配方式不會(huì)產(chǎn)生“碎片”現(xiàn)象

11、，從而大大提高了主存的利用率。,A（10KB） B（8KB） C（16KB） D（64KB） 進(jìn)程隊(duì)列 操作系統(tǒng) 操作系統(tǒng) 操作系統(tǒng) 操作系統(tǒng) 主存變化 進(jìn)程A 進(jìn)程A 進(jìn)程A 進(jìn)程A 進(jìn)程B 進(jìn)程B 進(jìn)程B 進(jìn)程C 進(jìn)程C 進(jìn)程D 圖3-8 主存分配情況,采用數(shù)據(jù)結(jié)構(gòu),可用分區(qū)表 區(qū)號(hào) 分區(qū)長(zhǎng)度 起始地址 自由鏈表 請(qǐng)求表 作業(yè)(進(jìn)程)號(hào) 請(qǐng)求長(zhǎng)度,2. 動(dòng)態(tài)分區(qū)的分配方式,（1）最先適應(yīng)法 ：將作業(yè)分配到主存的第一個(gè)足夠裝入它的可用空閑區(qū)中。 這種算法的缺點(diǎn)是可能將大的空閑區(qū)分割成一個(gè)小區(qū)，不利于大作業(yè)的裝入與運(yùn)行。 （2）最佳適應(yīng)法：將作業(yè)分配到主存中與它所需大小最接近的一個(gè)可用空閑區(qū)中

12、。,優(yōu)點(diǎn):可保證不會(huì)去分割一個(gè)更大的空閑區(qū)，便于今后大作業(yè)的裝入運(yùn)行。 缺點(diǎn):由于空閑區(qū)通常不可能正好和作業(yè)所要求的大小相等，往往分割后剩下的空閑區(qū)非常小，以至幾乎無法使用。造成了主存空間的浪費(fèi)。 （3）最壞適應(yīng)法：把一個(gè)作業(yè)分配到主存中最大的空閑區(qū)中。 優(yōu)點(diǎn):在大空閑區(qū)中裝入作業(yè)后，剩下的空閑區(qū)常常也很大，于是也能滿足以后較大的作業(yè)的要求。該算法對(duì)中、小作業(yè)的運(yùn)行是很有利的。,3. 動(dòng)態(tài)分區(qū)的回收,分區(qū)的回收有四種情況： （1）釋放區(qū)與上下兩個(gè)空閑區(qū)相鄰。 （2）釋放區(qū)與上空閑區(qū)相鄰。 （3）釋放區(qū)與下空閑區(qū)相鄰。 （4）釋放區(qū)與上下兩個(gè)空閑區(qū)都不相鄰。,操作系統(tǒng) 操作系統(tǒng) 操作系統(tǒng) 操作系

13、統(tǒng) A（10KB）作業(yè)B完成 A（10KB） A（10KB） A（10KB） B（8KB） C（16KB）釋放存儲(chǔ)空間 C（16KB）作業(yè)D完成 C（16KB） C（16KB） D（64KB） D（64KB） 釋放存儲(chǔ)空間 合并 圖3-10 動(dòng)態(tài)分區(qū)方式中存儲(chǔ)區(qū)的釋放和回收,4. 地址轉(zhuǎn)換與存儲(chǔ)保護(hù),限長(zhǎng)寄存器 基址寄存器 作業(yè) 主存 OS 邏輯地址 邏輯地址 + 絕對(duì)地址 限長(zhǎng)？ 是 地址錯(cuò) 基址寄存器存放分配給作業(yè)使用的分區(qū)的最小絕對(duì)地址值；限長(zhǎng)寄存器存放作業(yè)占用的連續(xù)存儲(chǔ)空間的長(zhǎng)度。 基址寄存器、限長(zhǎng)寄存器內(nèi)容屬于保護(hù)的現(xiàn)場(chǎng)。,5. 分區(qū)的共享,1）系統(tǒng)提供多對(duì)基址/限長(zhǎng)寄存器 2）規(guī)定

14、某些對(duì)基址/限長(zhǎng)寄存器指定的區(qū)為共享區(qū) 3）規(guī)定對(duì)共享區(qū)的信息只執(zhí)行或讀，不能寫,6. 移動(dòng)技術(shù),當(dāng)存儲(chǔ)分配程序找不到一個(gè)足夠大的空閑區(qū)來裝入作業(yè)時(shí)，可以采用移動(dòng)技術(shù)改變主存中的作業(yè)存放區(qū)域，同時(shí)修改它們的基址/限長(zhǎng)值，從而使分散的小空閑區(qū)匯集成一個(gè)大的空閑區(qū)，有利于作業(yè)的裝入。,圖3-12 移動(dòng)分配示例,移動(dòng)技術(shù)的優(yōu)缺點(diǎn),優(yōu)點(diǎn)： 可使分散的“碎片”或小空閑區(qū)匯集成大的空閑區(qū)； 為作業(yè)執(zhí)行過程中擴(kuò)充主存提供了方便。 缺點(diǎn)： 增加了系統(tǒng)的開銷； 不是隨時(shí)可移動(dòng)； 作業(yè)動(dòng)態(tài)申請(qǐng)主存會(huì)出現(xiàn)“死鎖”。解決的辦法：撤出部分死鎖作業(yè)，讓一些作業(yè)獲得主存運(yùn)行，后歸還主存，再將送出的作業(yè)調(diào)回運(yùn)行。,7. 分區(qū)

15、存儲(chǔ)管理的優(yōu)缺點(diǎn),(1) 主要優(yōu)點(diǎn) 實(shí)現(xiàn)了多道程序設(shè)計(jì)，從而提高了系統(tǒng)資源的利用率。 系統(tǒng)要求的硬件支持少，管理簡(jiǎn)單。 (2) 主要缺點(diǎn) 作業(yè)在裝入時(shí)的連續(xù)性使主存的利用率不高。 主存的擴(kuò)充只能采用覆蓋與交換技術(shù)，無法真正實(shí)現(xiàn)虛擬存儲(chǔ)。,3.5 頁式存儲(chǔ)管理,3.5.1概述 一、引入： 分區(qū)管理的一系列問題： (1) 當(dāng)連續(xù)空閑區(qū)不能滿足進(jìn)程的要求時(shí)，即使系統(tǒng)中所有空閑區(qū)之和大于進(jìn)程對(duì)主存的要求，但仍然不能裝入進(jìn)程。 (2) 存儲(chǔ)區(qū)中仍然存在“碎片”的現(xiàn)象，使主存利用率不高，采用移動(dòng)技術(shù)將分散的“碎片”合并成一個(gè)較大的可用區(qū)域，但“碎片”的合并需要占用CPU的時(shí)間，并且合并也不是隨時(shí)都能進(jìn)行的

16、。 (3) 分區(qū)管理方式無法有效地實(shí)現(xiàn)虛擬存儲(chǔ)技術(shù)，即：使進(jìn)程的邏輯地址空間大于實(shí)際的主存物理空間，從而使有限的主存運(yùn)行較大、較多的程序。,二、分頁管理的基本思想： 將作業(yè)分配在不連續(xù)的大小相同存儲(chǔ)區(qū)域中（見縫插針分配），同時(shí)又要保證作業(yè)的連續(xù)執(zhí)行。每個(gè)區(qū)稱為一塊（頁框），與此對(duì)應(yīng)，編制程序的邏輯地址也分為頁（頁面），頁的大小與塊的大小相等 ，通常頁的大小總是2的整數(shù)次冪。 分配的考慮：將進(jìn)程的頁分配到主存的塊中。 三、分頁存儲(chǔ)器的邏輯地址格式： 頁號(hào) 單元號(hào),三、優(yōu)越性 1、實(shí)現(xiàn)了連續(xù)存儲(chǔ)到非連續(xù)存儲(chǔ)的飛躍，為實(shí)現(xiàn)虛擬存儲(chǔ)打下了基礎(chǔ)； 2、解決了主存中的“碎片”問題，任意一個(gè)“內(nèi)碎片”或“內(nèi)

17、零頭”都不會(huì)大于整個(gè)頁框的大小，從而提高了主存的利用率。 四、分類 根據(jù)作業(yè)裝入主存的時(shí)機(jī)不同，一般分為： 1，靜態(tài)分頁管理 2，虛擬分頁管理。,3.5.2 靜態(tài)分頁管理,1、基本思想 用戶作業(yè)在開始執(zhí)行以前，將該作業(yè)的程序和數(shù)據(jù)全部裝入到主存中，然后，操作系統(tǒng)通過頁表和硬件地址變換機(jī)構(gòu)實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，從而執(zhí)行用戶程序的。,1主存頁框的分配與回收 為要求主存的作業(yè)或進(jìn)程分配足夠的頁框。這就需要系統(tǒng)建立存儲(chǔ)頁框表、請(qǐng)求表和頁表等數(shù)據(jù)結(jié)構(gòu)，依據(jù)這些數(shù)據(jù)結(jié)構(gòu)完成主存的分配和回收工作。,（1）頁表 動(dòng)態(tài)重定位 ： 在執(zhí)行每條指令時(shí)，將程序中的邏輯地址變換為物理地址 。 頁表 ： 在頁式管

18、理系統(tǒng)中實(shí)現(xiàn)地址變換的數(shù)據(jù)結(jié)構(gòu)稱為頁面映像表，簡(jiǎn)稱頁表。 在主存的固定區(qū)域中。每進(jìn)程一張。 頁表中的信息： 一、頁號(hào)。 二、頁面對(duì)應(yīng)的頁框，記錄著該進(jìn)程的每個(gè)頁面分配到主存的哪些頁框中。,（2）請(qǐng)求表,請(qǐng)求表： 用來確定作業(yè)或進(jìn)程的虛擬地址空間的各頁表在主存中的實(shí)際對(duì)應(yīng)位置。,（3）存儲(chǔ)頁框表,存儲(chǔ)頁框表： 指出主存各頁框是否已被分配，以及未被分配的頁框總數(shù)。 形式 ： 1、位示圖：在主存中劃分出一個(gè)固定的區(qū)域，該區(qū)域中每個(gè)單元的每個(gè)位表示一個(gè)頁框的分配或空閑狀況，若該位為1，代表所對(duì)應(yīng)的頁框已分配，若該位為0，代表所對(duì)應(yīng)的頁框空閑。 2、空閑頁框鏈：在空閑頁框鏈中，隊(duì)首頁框的第一單元和第二單

19、元分別存放空閑頁框的總數(shù)和指向下一個(gè)空閑頁框的指針，其它頁框的第一單元?jiǎng)t分別存放指向下一個(gè)空閑頁框的指針。,（4）頁框分配與回收算法,-、分配： 1、從請(qǐng)求表中查出作業(yè)或進(jìn)程所要求的頁框數(shù)。 2、由存儲(chǔ)頁框表檢查是否足夠有空閑頁框（塊），若沒有，則本次無法分配。如果有，則分配并設(shè)置頁表，并填寫請(qǐng)求表中的相應(yīng)表項(xiàng)（頁表始址、頁表長(zhǎng)度和狀態(tài)）。 3、再按一定的查找算法，搜索出所要求的空閑頁框（塊），并將對(duì)應(yīng)的頁框（塊）號(hào)填入頁表中。 二、回收： 當(dāng)進(jìn)程執(zhí)行完畢時(shí)，根據(jù)進(jìn)程頁表中登記的頁框（塊）號(hào)，將這些頁框（塊）插入到存儲(chǔ)頁框表中，使之成為空閑頁框（塊）。最后，拆除該進(jìn)程所對(duì)應(yīng)的頁表即可。,2.

20、頁式地址變換,首先用戶作業(yè)提出存儲(chǔ)分配的要求，此時(shí)操作系統(tǒng)根據(jù)主存頁框的大?。?KB）將進(jìn)程要求的存儲(chǔ)空間分成相應(yīng)的頁面。 (1) 根據(jù)主存的實(shí)際情況，將進(jìn)程的每個(gè)頁面分配到主存空閑頁框中，同時(shí)，系統(tǒng)分配并設(shè)置頁表的內(nèi)容（通常一個(gè)進(jìn)程具備一個(gè)頁表）。此時(shí)，系統(tǒng)完成用戶進(jìn)程的存儲(chǔ)器分配。 (2) 當(dāng)用戶進(jìn)程開始執(zhí)行時(shí)，系統(tǒng)首先設(shè)置控制寄存器的內(nèi)容，控制寄存器包括頁表長(zhǎng)度和頁表起始地址兩項(xiàng)。 (3) 為了對(duì)邏輯地址進(jìn)行變換，由硬件組成的地址變換機(jī)構(gòu)必須將其分成兩部分：頁號(hào)和頁內(nèi)偏移（即2和452）。 (4) 根據(jù)邏輯地址中提供的頁號(hào)在頁表中找到相對(duì)應(yīng)的頁框號(hào)（2 8）。 (5) 將頁表中的頁框號(hào)和

21、邏輯地址中的頁內(nèi)偏移分別寫入絕對(duì)地址中的相應(yīng)位置上（即8和452）。 然后根據(jù)絕對(duì)地址提供的頁框號(hào)和頁內(nèi)偏移計(jì)算出存儲(chǔ)空間的物理地址（1KB=1024，810244528644）。此時(shí)，用戶進(jìn)程便可以訪問主存中的絕對(duì)地址，取出數(shù)據(jù)或取出指令執(zhí)行。,3、快表,一、引入： 執(zhí)行一條訪問主存的指令都要訪問主存兩次 ，為了盡量減少訪問主存的次數(shù)，提高地址變換的速度，可在地址變換機(jī)構(gòu)中增設(shè)一個(gè)具有并行查尋能力的特殊高速緩沖存儲(chǔ)器，用來存放頁表的一部分。 二、概念： 快表：存放在高速緩沖存儲(chǔ)器中的頁表 相聯(lián)存儲(chǔ)器(Association Memory)：高速緩沖存儲(chǔ)器,圖3-18 快表實(shí)現(xiàn)地址變換,三、

22、快表的組織與管理,1 填寫：慢地址翻譯找空項(xiàng)填寫 2 淘汰：無空項(xiàng)時(shí)，淘汰一舊項(xiàng)。 方法： FIFO, LRU等。 3 快表的大?。?4-256個(gè)頁表項(xiàng)。 保持命中率90% 4 進(jìn)程切換時(shí)的快表管理： 1）用特定指令將相聯(lián)存儲(chǔ)器有效位清0； 2）在相聯(lián)存儲(chǔ)器增加一個(gè)進(jìn)程標(biāo)識(shí)符域，CPU增加一個(gè)寄存器存當(dāng)前進(jìn)程標(biāo)識(shí)符，查快表時(shí)也進(jìn)行標(biāo)識(shí)符核對(duì)。增加硬件開銷，但可提高命中率，省去上下文切換。,4. 頁的共享與保護(hù),頁的共享：提高主存空間的利用率。 共享的實(shí)現(xiàn) （1）實(shí)現(xiàn)數(shù)據(jù)共享 作業(yè)對(duì)共享數(shù)據(jù)頁可使用不同的頁號(hào)，只要相應(yīng)頁表項(xiàng)指到同一主存塊即可。 （2）實(shí)現(xiàn)程序共享 對(duì)共享程序必須規(guī)定一個(gè)統(tǒng)一的頁

23、號(hào)。,共享信息的保護(hù)： （1）頁表中增加一個(gè)保護(hù)權(quán)限域 指出該頁的信息為：可讀/寫、只讀、只執(zhí)行和不可訪問等，指令執(zhí)行時(shí)進(jìn)行操作權(quán)限核對(duì) 。 （2）保護(hù)鍵法 系統(tǒng)為每道作業(yè)設(shè)置一個(gè)保護(hù)鍵，為作業(yè)分配主存時(shí)，根據(jù)它的保護(hù)鍵在相應(yīng)的頁表中建立鍵標(biāo)志。程序執(zhí)行時(shí)將程序狀態(tài)字中的鍵和訪問頁的保護(hù)鍵進(jìn)行核對(duì)，相符時(shí)才可訪問該頁框。,絕對(duì)地址=塊號(hào)*塊長(zhǎng)+單元號(hào)例：假設(shè)一塊為0.5k，作業(yè)為4.1k ，一頁為0.5k，邏輯地址為1568，求絕對(duì)地址。,頁表為： 頁號(hào) 塊號(hào) 0 3 1 2 2 5 3 4 4 1 5 10 解：1568/512=3 所以該頁處在第4塊 所求=1024*0.5*4 + (15

24、68%512)=2080,3.5.3 虛擬頁式存儲(chǔ)管理,3.5.2.1 虛擬存儲(chǔ)的基本思想 1. 常規(guī)存儲(chǔ)管理方式的特征 1) 整體特性 整體性是指用戶作業(yè)在運(yùn)行以前，必須將全部的內(nèi)容一次裝到主存中，這必然會(huì)導(dǎo)致主存容量不夠；而且在大多數(shù)情況下，系統(tǒng)運(yùn)行時(shí)并不要求使用用戶作業(yè)的全部程序，因而造成了主存空間的浪費(fèi)。 2) 駐留特性 用戶作業(yè)在裝入主存運(yùn)行過程中，將一直占據(jù)著主存的部分空間，即使是等待資源分配（例如因?yàn)镮O而長(zhǎng)期等待），或有些程序只運(yùn)行一次，但它并不會(huì)釋放所占據(jù)的主存空間，一直要等到用戶作業(yè)運(yùn)行結(jié)束。,時(shí)間局部性表現(xiàn)在如果程序中某一條指令一旦執(zhí)行，則在不久以后還可能被繼續(xù)執(zhí)行；同樣

25、，若某一個(gè)數(shù)據(jù)被訪問后不久，還可能被繼續(xù)訪問。其典型的情況是程序中存在著大量的循環(huán)。 空間局部性表現(xiàn)在如果程序訪問了某一個(gè)存儲(chǔ)單元，其附近的存儲(chǔ)單元?jiǎng)t在不久也會(huì)被訪問。即程序在一段時(shí)間內(nèi)訪問的地址，可能集中在一定的范圍內(nèi)。其典型的情況是程序順序執(zhí)行。,2. 局部性原理,概念： 在一較短的時(shí)間里，程序的執(zhí)行僅局限在某個(gè)部分，相應(yīng)地，它訪問的存儲(chǔ)空間也局限在某個(gè)區(qū)域。 理由： (1) 程序在執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，在大多數(shù)情況下仍是順序執(zhí)行的。 (2) 過程調(diào)用將會(huì)使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域，但是經(jīng)研究可看出，過程調(diào)用的深度在大多數(shù)情況下并不是很遠(yuǎn)。這就是說，程

26、序?qū)?huì)在一段時(shí)間內(nèi)都局限于某一范圍內(nèi)運(yùn)行。 (3) 程序中存在許多循環(huán)結(jié)構(gòu)，它們雖由少數(shù)指令構(gòu)成，但多次執(zhí)行。 (4) 程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，如對(duì)數(shù)組進(jìn)行操作，它們都往往局限于很小范圍內(nèi)。,時(shí)間局部性和空間局部性,局部性又表現(xiàn)為時(shí)間局部性和空間局部性 時(shí)間局部性: 如果程序中某一條指令一旦執(zhí)行，則在不久以后還可能被繼續(xù)執(zhí)行；同樣，若某一個(gè)數(shù)據(jù)被訪問后不久，還可能被繼續(xù)訪問。其典型的情況是程序中存在著大量的循環(huán)。 空間局部性 如果程序訪問了某一個(gè)存儲(chǔ)單元，其附近的存儲(chǔ)單元?jiǎng)t在不久也會(huì)被訪問。即程序在一段時(shí)間內(nèi)訪問的地址，可能集中在一定的范圍內(nèi)。其典型的情況是程序順序執(zhí)行。,3. 虛擬

27、存儲(chǔ)器的基本思想,當(dāng)用戶作業(yè)要求的存儲(chǔ)空間很大，不能被裝入主存時(shí)，基于局部性原理，系統(tǒng)可以把當(dāng)前要用的程序和數(shù)據(jù)裝入主存中啟動(dòng)程序運(yùn)行，而暫時(shí)不用的程序和數(shù)據(jù)駐留在外存中。在執(zhí)行中需要用到不在主存中的信息時(shí)，可將暫時(shí)不用的程序和數(shù)據(jù)調(diào)出主存，騰出主存空間讓系統(tǒng)調(diào)入要用的程序和數(shù)據(jù)。從用戶角度上看，系統(tǒng)具備了比實(shí)際主存容量大得多的存儲(chǔ)器，人們把這樣的存儲(chǔ)器稱為虛擬存儲(chǔ)器。,4虛擬存儲(chǔ)器的特征,1）多次性 用戶程序在運(yùn)行前，并不是一次將全部?jī)?nèi)容裝入到主存中，而是在程序的運(yùn)行過程中，系統(tǒng)不斷地對(duì)程序和數(shù)據(jù)部分地調(diào)入、調(diào)出，完成程序的多次裝入工作。 2）對(duì)換性 程序在運(yùn)行期間，允許將暫時(shí)不用的程序和數(shù)

28、據(jù)調(diào)出主存（換出），放入外存的對(duì)換區(qū)中，待以后需要時(shí)再將它調(diào)入主存中（換入），這便是虛擬存儲(chǔ)器的換入、換出操作，即對(duì)換性。 虛擬存儲(chǔ)的多次性和對(duì)換性必須建立在離散分配的基礎(chǔ)上。,3.5.3.2 用分頁技術(shù)實(shí)現(xiàn)虛擬存儲(chǔ)器,1. 數(shù)據(jù)結(jié)構(gòu) (1) 狀態(tài)位 用于指示該頁是否已調(diào)入主存，如用1表示在主存，0表示不在主存。 (2) 訪問字段 用于記錄本頁在一段時(shí)間內(nèi)被訪問的情況，提供給置換機(jī)構(gòu)參考。 (3) 修改位 表示該頁在調(diào)入主存后是否被修改過，由于主存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時(shí)就不需將該頁寫回到外存上；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的

29、始終是最新副本。 (4) 保護(hù)權(quán)限：說明該頁允許什么類型的訪問。它指出了該頁的信息可能為：可讀/寫、只讀、只執(zhí)行和不可訪問等 (5) 外存地址：指出該頁在外存上的地址，供調(diào)入該頁時(shí)使用。,二級(jí)頁表的地址變換,三次訪問主存: 一次訪問頁目錄，一次訪問頁表，最后才訪問數(shù)據(jù)所在的物理地址。,反向頁表,概念： 頁表的第i個(gè)表項(xiàng)記錄著當(dāng)前占用頁框i的頁面信息，表中的表項(xiàng)號(hào)與物理主存的頁框號(hào)相等，而與虛存的頁號(hào)無關(guān)，該頁表稱為反向頁表(inverted page table)。 重定位： 當(dāng)進(jìn)程給出虛地址后，存儲(chǔ)管理單元(MMU)通過一個(gè)哈希函數(shù)轉(zhuǎn)換為一個(gè)哈希值，以該值為索引指向反向頁表中的一個(gè)表目，若表

30、目中的內(nèi)容與該進(jìn)程的虛頁號(hào)相一致，即形成絕對(duì)地址，否則再到鏈指針中查找。,2. 分頁式虛擬存儲(chǔ)管理工作流程,硬件環(huán)境 ： (1) 具有一定容量主存，用于存放一個(gè)操作系統(tǒng)，以及每個(gè)進(jìn)程的部分程序、數(shù)據(jù)和相應(yīng)的頁表表項(xiàng)。 (2) 相當(dāng)容量外存，用于存放每個(gè)進(jìn)程未裝入主存的部分、后備作業(yè)以及大量的文件。 (3) 地址變換機(jī)構(gòu)，用于將用戶程序地址空間中的邏輯地址變換為主存的物理地址。 (4) 缺頁中斷機(jī)構(gòu)，當(dāng)發(fā)現(xiàn)所要訪問的頁不在主存時(shí)，應(yīng)立即發(fā)出缺頁中斷信號(hào)，以請(qǐng)求操作系統(tǒng)將所缺之頁調(diào)入主存。,缺頁中斷,缺頁中斷與一般中斷的區(qū)別 在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。通常CPU都是在一條指令執(zhí)行完后檢查是

31、否有中斷請(qǐng)求到達(dá)，若有，便去響應(yīng)，否則繼續(xù)執(zhí)行下一條指令。然而缺頁中斷是在指令執(zhí)行期間發(fā)現(xiàn)所要訪問的指令或數(shù)據(jù)不在主存時(shí)產(chǎn)生和處理的。 一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。如采用多級(jí)頁表時(shí)，頁表也是作為動(dòng)態(tài)調(diào)入的，地址翻譯過程就可能出現(xiàn)訪問頁表的缺頁中斷，最后才產(chǎn)生所要訪問的頁的缺頁中斷。,分頁式虛擬存儲(chǔ)管理工作流程：,按邏輯地址查快表 N 該頁在快表中 Y 有登記嗎？ 查頁表 形成絕對(duì)地址 N Y 該頁在主存？ 繼續(xù)執(zhí)行指令 發(fā)缺頁中斷 形成絕對(duì)地址 （下頁） 將該頁登記入快表,分頁式虛擬存儲(chǔ)管理工作流程（續(xù)）：,缺頁中斷處理,保護(hù)CPU現(xiàn)場(chǎng),從外存中找到缺頁,主存滿否？,從外存調(diào)入所

32、缺的頁,N,修改頁表和存儲(chǔ)頁框表,恢復(fù)現(xiàn)場(chǎng),Y,選擇一頁調(diào)出,該頁被修改否？,將該頁寫回外存,Y,N,3.5.3.3頁面置換,1調(diào)頁策略 1）預(yù)調(diào)頁策略 該策略應(yīng)以預(yù)測(cè)為基礎(chǔ)，只將那些預(yù)計(jì)不久后便會(huì)被訪問的程序或數(shù)據(jù)所在的頁面預(yù)先調(diào)入主存。 2）請(qǐng)求調(diào)頁策略 當(dāng)進(jìn)程運(yùn)行中需要訪問某部分程序和數(shù)據(jù)，而其所在頁面又不在主存時(shí)，立即提出請(qǐng)求，由系統(tǒng)將其所需頁面調(diào)入主存。,2分配策略,1）固定分配策略 概念： 每個(gè)進(jìn)程分配一固定頁數(shù)的主存空間，在整個(gè)運(yùn)行期間不再改變。 缺點(diǎn)：應(yīng)為每個(gè)進(jìn)程分配多少個(gè)頁框的主存難于確定。 2）可變分配策略 概念： 為每個(gè)進(jìn)程分配一定數(shù)量的主存空間，如果該進(jìn)程在運(yùn)行過程中頻

33、繁地發(fā)生缺頁中斷，則系統(tǒng)再為該進(jìn)程分配若干附加的物理頁框，直至進(jìn)程減到適當(dāng)?shù)娜表撀蕿橹?；反之，若一個(gè)進(jìn)程在運(yùn)行過程中的缺頁率特別低，則此時(shí)可適當(dāng)減少分配給該進(jìn)程的物理頁框。,3. 頁面置換算法,概念： 主存已滿，又需裝入新頁時(shí)，將主存中的某些頁調(diào)出去。這一工作稱為頁面調(diào)度或頁面置換。頁面調(diào)度實(shí)質(zhì)上是決定淘汰那一頁。 不合適的調(diào)度算法： 若剛被淘汰的頁面又立即要用到，因此又要把它調(diào)入而調(diào)入不久再被淘汰，淘汰不久又再被調(diào)入。如此反復(fù)，使得整個(gè)系統(tǒng)的頁面置換非常頻繁，以至于大部分時(shí)間都花費(fèi)再來回調(diào)度上。這種現(xiàn)象稱作“抖動(dòng)”或“顛簸”。 缺頁中斷率為：f=F/(S+F),頁面調(diào)度算法：,1）優(yōu)化算法（

34、OPT） 這是一種理論化的算法，其所選擇的被淘汰的頁將是永不使用的頁，或者是在最長(zhǎng)時(shí)間內(nèi)不再訪問的頁。 2）先進(jìn)先出算法（FIFO） 該算法總是淘汰最先進(jìn)入主存的頁面，認(rèn)為最先調(diào)入的頁訪問可能性最大。,缺頁率=缺頁次數(shù)/總的訪問次數(shù)*100%,用FIFO算法求缺頁率： 1 2 3 4 1 2 5 1 2 3 4 5 1 2 3 4 1 2 5 5 5 3 4 5 1 2 3 4 1 2 2 2 5 3 3 1 2 3 4 1 1 1 2 5 5 T T T T T T T F F T T F 缺頁率=9/12*100%=75%,Belady現(xiàn)象,3）最近最少用置換算法（LRU）,該算法要求淘汰

35、的頁面是在最近一段時(shí)間里較久未被訪問的那一頁。根據(jù)是程序執(zhí)行時(shí)所具有的局部性。 為了比較準(zhǔn)確地淘汰最近最少使用的頁面，可以采用堆棧的方法來實(shí)現(xiàn)。棧中存放當(dāng)前主存中的頁號(hào)，每當(dāng)訪問一頁時(shí)就調(diào)整一次棧。于是，發(fā)生缺頁中斷時(shí)總是淘汰棧底所指示的頁。,例：用LRU算法求缺頁率：,4 3 0 4 1 1 2 3 2 4 3 0 4 1 1 2 3 2 4 3 0 4 4 1 2 3 4 3 0 0 4 1 1 T T T F T F T T F 缺頁率=6/9*100%=64.4%,4）最近未用置換算法（NRU） 概念： 該算法要求頁表中有一個(gè)訪問位和一個(gè)修改位。當(dāng)某頁被訪問時(shí)，訪問位被自動(dòng)置1，若執(zhí)行

36、的指令是寫指令，則修改位也被置1。系統(tǒng)周期性地將所有訪問位置0。在選擇一頁淘汰時(shí)，總是選擇其訪問位為0且修改位也為0的頁。若無修改位為0的頁，就選訪問位為0且頁號(hào)最小的頁淘汰。 評(píng)價(jià)： 該算法不但希望淘汰的頁是最近未使用的頁，而且還希望被淘汰的頁是在主存駐留期間其頁面內(nèi)容未被修改過。 系統(tǒng)對(duì)訪問位清0的間隔時(shí)間T的確定是很關(guān)鍵的。如果間隔時(shí)間T太大，可能所有頁的訪問位均已成為1，無法選擇淘汰的頁面。如果間隔時(shí)間T太小，則可能很多頁的訪問位均是為0,5）最少使用置換算法（Least Frequently UsedLFU）,概念： 要求為每一頁表項(xiàng)配置一個(gè)一定位數(shù)的計(jì)數(shù)器作為訪問字段，開始時(shí)所有的

37、計(jì)數(shù)器均為0。一旦某頁被訪問時(shí)，其頁表項(xiàng)中的計(jì)數(shù)器值加1。系統(tǒng)每過一段時(shí)間T就將所有的頁表項(xiàng)計(jì)數(shù)器清0。 在需要選擇一頁置換時(shí)，便比較各計(jì)數(shù)器的值，總是選擇其計(jì)數(shù)值最小的頁面淘汰。 評(píng)價(jià)： 該算法實(shí)現(xiàn)也較容易，但代價(jià)較高，而且合適的間隔時(shí)間T的選擇也是難題。,3.5.3.4 分頁式虛擬存儲(chǔ)系統(tǒng)的性能分析,影響缺頁率的因素： 1）程序的局部化 2）頁面的大小 頁面越大，缺頁率越低。 3）程序快數(shù) 同時(shí)運(yùn)行的程序越多，缺頁率越高。 4）內(nèi)存大小 內(nèi)存越大，缺頁率越低。 5）調(diào)度算法,3.5.3 分頁存儲(chǔ)管理優(yōu)缺點(diǎn),優(yōu)點(diǎn)： 1）解決主存的零頭問題，能有效地利用主存。 2）方便多道程序設(shè)計(jì)，并且程序運(yùn)

38、行的道數(shù)增加了。 3）可提供大容量的虛擬存儲(chǔ)器，作業(yè)的地址空間不再受實(shí)際主存大小的限制。 4）更加方便了用戶，特別是大作業(yè)的用戶。當(dāng)某作業(yè)地址空間超過主存空間時(shí)，用戶也無需考慮覆蓋結(jié)構(gòu)。,缺點(diǎn)： 1）要有相應(yīng)的硬件支持，如需要?jiǎng)討B(tài)地址變換機(jī)構(gòu)、缺頁中斷處理機(jī)構(gòu)等。 2）必須提供相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來管理存儲(chǔ)器，它們不僅占用了部分主存空間，同時(shí)還要花費(fèi)CPU時(shí)間。 3）在分頁系統(tǒng)中頁內(nèi)的零頭問題仍然存在。 4）在請(qǐng)求分頁管理中，需要進(jìn)行缺頁中斷處理，還有可能出現(xiàn)抖動(dòng)現(xiàn)象，增加了系統(tǒng)開銷，降低系統(tǒng)效率。,3.6 段式及段頁式存儲(chǔ)管理,3.6.1 段式存儲(chǔ)管理 1.段式存儲(chǔ)管理概述 分頁式 缺點(diǎn)： 1）程

39、序的邏輯地址空間是連續(xù)的 ，裝配好的程序段和數(shù)據(jù)塊的存儲(chǔ)空間是確定的，在執(zhí)行中是無法動(dòng)態(tài)增長(zhǎng)和收縮。 2）無法做到頁與邏輯意義完整的子程序或數(shù)據(jù)段的唯一對(duì)應(yīng)，增大了其信息共享實(shí)現(xiàn)的難度。 3）從連接的角度上看，分區(qū)管理和分頁管理只能采用靜態(tài)連接 ，不僅花費(fèi)了大量的CPU時(shí)間，而且也浪費(fèi)了許多主存空間 。,2 段式存儲(chǔ)管理實(shí)現(xiàn),1）段式存儲(chǔ)管理思想：把程序按邏輯含義或過程（函數(shù)）關(guān)系分成段，每段都有段名。每段邏輯地址均是以0開始進(jìn)行順序編址。用戶作業(yè)或進(jìn)程的地址空間就形成了一個(gè)二維線性地址空間。以段為單位分配主存。執(zhí)行時(shí)通過地址轉(zhuǎn)換機(jī)構(gòu)把段式邏輯地址轉(zhuǎn)換成主存物理地址。 2） 邏輯地址格式： 段

40、號(hào) 單元號(hào) 如：某系統(tǒng)段地址結(jié)構(gòu)為32位，其中段號(hào)占12位，段內(nèi)地址占20位，則在該系統(tǒng)中一個(gè)作業(yè)最多可有4K個(gè)段，每段的長(zhǎng)度可達(dá)1MB。,一個(gè)作業(yè)各段在主存中的分配情況,地址轉(zhuǎn)換過程,段式管理,快表的應(yīng)用： 段式管理的一次訪問也必須經(jīng)過兩次以上訪問主存的操作。為了提高訪問速度，也需要將高速相聯(lián)存儲(chǔ)器引入，把部分段表存入其中，形成段式快表。地址轉(zhuǎn)換時(shí)，先查快表，若快表命中，則立即形成絕對(duì)地址，否則再通過段表進(jìn)行慢地址翻譯，并將該段信息填入快表中。 分段與分頁比較： 分段是信息的邏輯單位，是用戶可見的，段的大小是用戶程序決定。而分頁是信息的物理單位，分頁對(duì)用戶來說是不可見的，頁的大小是事先固定的

41、。,段式管理信息共享和保護(hù),共享： 如果用戶作業(yè)需要共享主存中的某段程序或數(shù)據(jù)時(shí)，只要用戶使用相同的共享段名，系統(tǒng)在建立段表時(shí)，只須在相應(yīng)的段表欄目上填入已在主存的段的始址和長(zhǎng)度，即可實(shí)現(xiàn)段的共享，從而提高系統(tǒng)主存的利用率。 保護(hù)： （1）在段表中增設(shè)一個(gè)存取權(quán)限域。存取權(quán)限可分為：只執(zhí)行（共享程序段）、只讀（共享數(shù)據(jù)段）和可讀/寫（私人段）。訪問段時(shí)，通過存取權(quán)限核對(duì)，即可實(shí)現(xiàn)存取保護(hù)。 （2）通過段表中的長(zhǎng)度信息，在地址轉(zhuǎn)換時(shí)，將長(zhǎng)度與段內(nèi)地址比較，就可進(jìn)行地址越界保護(hù)。,3.6.2 段式虛擬存儲(chǔ)管理,1. 段式虛擬存儲(chǔ)管理實(shí)現(xiàn)原理 基本思想 ： 把作業(yè)的所有分段的副本都存放在外存上，當(dāng)作

42、業(yè)被調(diào)度投入運(yùn)行時(shí)，首先把當(dāng)前需要用的一段或幾段裝入主存，在執(zhí)行過程中，訪問到不在主存的段時(shí)，再通過缺段中斷機(jī)構(gòu)把它從外存上調(diào)入。,段表,特征位可用兩位表示相應(yīng)的段是否在主存，是否可共享； 存取權(quán)限用兩位表示相應(yīng)段只執(zhí)行、只讀或可讀/寫的權(quán)限； 標(biāo)志位用兩位表示相應(yīng)段是否已被修改過和能否移動(dòng)； 擴(kuò)充位用一位表示相應(yīng)段是固定長(zhǎng)還是可擴(kuò)充； 訪問位用來表示段的活動(dòng)狀況，作為淘汰段時(shí)參考； 外存始址登記該段在外存中副本的起始地址。,段式虛擬存儲(chǔ)管理工作流程：,訪問S段B單元 Y N S段在主存嗎？ N B=S段長(zhǎng)度？ Y 發(fā)缺段中斷 發(fā)越界中斷 N 符合存取權(quán)限？Y 發(fā)保護(hù)中斷 形成絕對(duì)地址 繼續(xù)執(zhí)

43、行命令,可能需移動(dòng)合并或淘汰在調(diào)入,2. 段的動(dòng)態(tài)連接,概念： 動(dòng)態(tài)連接裝配是指在程序運(yùn)行中對(duì)它所用到的子程序段或數(shù)據(jù)段進(jìn)行連接裝配，節(jié)省連接裝配時(shí)間和程序所占的空間。 實(shí)現(xiàn)： 增加兩個(gè)功能：間接編址和連接障礙指示。間接編址是指指令中的地址單元的內(nèi)容仍作為地址。 間接字的格式為：L 直接地址,段式管理優(yōu)缺點(diǎn)：,優(yōu)點(diǎn)： 嚴(yán)格按程序的邏輯結(jié)構(gòu)分配連續(xù)存儲(chǔ)空間，方便程序和數(shù)據(jù)的共享與保護(hù)，同時(shí)也便于程序及數(shù)據(jù)段的擴(kuò)充和動(dòng)態(tài)連接。 缺點(diǎn)： 一個(gè)段的長(zhǎng)度不能大于實(shí)際的主存容量，而且為了解決碎片問題，提高主存的利用率，必須采用移動(dòng)技術(shù)，移動(dòng)主存信息需要較大的系統(tǒng)開銷。,3.6.3 段頁式虛擬存儲(chǔ)管理,基本

44、思想： 每個(gè)作業(yè)按邏輯分段，然后對(duì)每一段又分成若干頁。這樣，每一段不必占用連續(xù)的主存空間，而是按頁存放在不一定連續(xù)的主存頁框中，并且當(dāng)主存頁框不夠時(shí)只將一段的部分頁面放在主存，用到不在主存中的頁面時(shí)再將之調(diào)入。 段頁式的邏輯地址格式： 段號(hào) 頁號(hào) 單元號(hào),段頁式虛擬存儲(chǔ)管理系統(tǒng)的地址結(jié)構(gòu)：,段頁式存儲(chǔ)管理系統(tǒng)地址轉(zhuǎn)換,要存取一次信息，必須經(jīng)歷三次訪問主存操作，一次訪問段表，一次訪問頁表，最后才能按絕對(duì)地址存取信息，這樣就降低了指令執(zhí)行的速度。為了加快地址轉(zhuǎn)換，也采用相聯(lián)存儲(chǔ)器來存放快表，快表中應(yīng)指出段號(hào)、頁號(hào)和主存頁框號(hào)。 硬件在執(zhí)行指令和進(jìn)行地址轉(zhuǎn)換時(shí)，可能會(huì)引起缺段中斷、越界中斷、保護(hù)中斷

45、、缺頁中斷和連接中斷等情形。,段頁式虛擬存儲(chǔ)管理系統(tǒng)中的中斷,處理思想如下： （1） 缺段中斷：為該段建立一張頁表，填寫該段頁表始址和長(zhǎng)度及其它必要的信息。 （2） 越界中斷：當(dāng)該段可擴(kuò)充時(shí)，應(yīng)增加頁表表目，修改段表中的頁表長(zhǎng)度。當(dāng)該段不可擴(kuò)充時(shí)，報(bào)出錯(cuò)信息，停止用戶程序執(zhí)行。 （3） 保護(hù)中斷：報(bào)告存取違法并停止程序執(zhí)行。 （4） 缺頁中斷：找出一個(gè)主存的空閑頁框或調(diào)出一頁，裝入所需的頁面，修改相應(yīng)表格（如頁表、存儲(chǔ)頁框表等）。 （5） 連接中斷：為該段分配一個(gè)段號(hào)，若該段已連接過，則根據(jù)該段的狀況填寫這個(gè)段表表項(xiàng)，否則可按缺段中斷一樣進(jìn)行處理，最后，根據(jù)段號(hào)、頁號(hào)與頁內(nèi)偏移形成無障礙指示的

46、一般間接地址。 除了越界中斷和保護(hù)中斷外，其它這些中斷在處理后，均應(yīng)重新啟動(dòng)被中斷的指令執(zhí)行。,段頁式虛擬存儲(chǔ)管理系統(tǒng)的優(yōu)缺點(diǎn),優(yōu)點(diǎn)： 具有段式和頁式的全部?jī)?yōu)點(diǎn) 缺點(diǎn)： 需要更多的硬件支持和中斷處理，增加了系統(tǒng)的成本和復(fù)雜性 。,本章小結(jié),1.存儲(chǔ)管理的任務(wù)和功能。 2.存儲(chǔ)分配常有三種形式，即：直接存儲(chǔ)分配、靜態(tài)存儲(chǔ)分配和動(dòng)態(tài)存儲(chǔ)分配，動(dòng)態(tài)存儲(chǔ)分配是現(xiàn)代操作系統(tǒng)常用的方式。 3.靜態(tài)重定位是在程序執(zhí)行前由裝配程序一次性完成，而動(dòng)態(tài)重定位是程序執(zhí)行中由硬件地址轉(zhuǎn)換機(jī)構(gòu)完成。,4.覆蓋與交換技術(shù)是從邏輯上擴(kuò)充主存的兩種方法，覆蓋要求程序員提供一個(gè)覆蓋結(jié)構(gòu)，它用于同一進(jìn)程之間，而交換對(duì)程序員無任何要求，它可用于進(jìn)程之間。 5.介紹了單一連續(xù)存儲(chǔ)管理、固定分區(qū)和動(dòng)態(tài)分區(qū)存儲(chǔ)管理。前兩者管理方式簡(jiǎn)單，但存儲(chǔ)利用率低，而動(dòng)態(tài)分區(qū)法存儲(chǔ)利用率可