【正文】 K36K 28K32K 24K28K 20K24K 16K20K 12K16K 8K12K 4K8K 0K4K 28K32K 24K28K 20K24K 16K20K 12K16K 8K12K 4K8K 0K4K 虛地址空間 物理地址空間 } 虛頁 頁框 127 2022/8/17 第六章 存儲(chǔ)管理 頁表表項(xiàng) 頁號(hào) 、 內(nèi)存塊號(hào)、 駐留位、 外存地址 、訪問位、修改位 ? 駐留位（中斷位）：表示該頁是在內(nèi)存還是在外存 ? 訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法決定） ? 修改位：查看此頁是否在內(nèi)存中被修改過 頁號(hào) 中斷位 內(nèi)存塊號(hào) 外存地址 訪問位 修改位 128 2022/8/17 第六章 存儲(chǔ)管理 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 000 0 000 0 000 0 000 0 111 1 000 0 101 1 000 0 000 0 000 0 011 1 100 1 000 1 110 1 001 1 010 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 110 在 /不在內(nèi)存 頁表 虛地址 8196 物理地址 24580 129 2022/8/17 第六章 存儲(chǔ)管理 缺頁中斷（ Page Fault） 處理 ? 在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生 缺頁中斷 。 ? 段式技術(shù)中程序地址空間是二維的 ， 分頁技術(shù)中程序地址空間是一維的 。 每一進(jìn)程有個(gè)段表 ， 程序的每一個(gè)段在段表中占用一個(gè)表目 。也就是說頁地址變換不會(huì)造成進(jìn)程運(yùn)行速度的下降。 84 2022/8/17 第六章 存儲(chǔ)管理 ? 解決這個(gè)問題的一種方法是把頁表放在一組快速存儲(chǔ)器中 （ Cache） ， 從而加快訪問內(nèi)存的速度 。 如頁長為 2K， 程序地址字為 16位 ， 則高 5位為頁號(hào) ， 低 11位為頁內(nèi)地址 。 ? 在現(xiàn)代計(jì)算機(jī)系統(tǒng)中 ， 由系統(tǒng)提供的地址映射硬件來完成地址映射工作 。 71 2022/8/17 第六章 存儲(chǔ)管理 ? 系統(tǒng)為 每個(gè)進(jìn)程建立一個(gè)頁表 ， 頁表的長度和首地址存放在該進(jìn)程的進(jìn)程控制塊 （ PCB） 中 。雖然采用壓縮存儲(chǔ)區(qū)的方法可以解決碎片問題 ， 但系統(tǒng)開銷太大 ， 而無實(shí)用價(jià)值 ， 必須尋求新的技術(shù)來解決這一問題 ， 于是分頁技術(shù)產(chǎn)生了 。 系統(tǒng)中空閑區(qū)按三種算法組成的空閑區(qū)隊(duì)列 ? 經(jīng)分析可知：最佳適應(yīng)法對(duì)這個(gè)作業(yè)序列是合適的 ， 而其它兩種對(duì)該作業(yè)序列是不合適的 。 55 2022/8/17 第六章 存儲(chǔ)管理 ? 回收：按釋放區(qū)的首址 ， 查詢空閑區(qū)表 （ 隊(duì)列 ） ， 若有與釋放區(qū)相鄰的空閑區(qū) ， 則合并到相鄰的空閑區(qū)中 ， 并修改該區(qū)的大小和首址 ， 否則 ， 把釋放區(qū)作為一個(gè)空閑區(qū)插入空閑區(qū)表 （ 隊(duì)列 ） 。 ? 分配和回收后要對(duì)空閑區(qū)表 （ 隊(duì)列 ） 重新排序 。 47 2022/8/17 第六章 存儲(chǔ)管理 ? 回收：按釋放區(qū)的首址 ， 查詢空閑區(qū)表 ， 若有與釋放區(qū)相鄰的空閑區(qū) ， 則合并到相鄰的空閑區(qū)中 ， 并修改該區(qū)的大小和首址 ， 否則 ，把釋放區(qū)作為一個(gè)空閑區(qū) ， 將其大小和首址按照首地址大小遞增 的順序插入到空閑區(qū)表的適當(dāng)位置 。 41 2022/8/17 第六章 存儲(chǔ)管理 釋放區(qū)與空閑區(qū)相鄰的四種情況 42 2022/8/17 第六章 存儲(chǔ)管理 說明 ? 釋放區(qū)與前空閑區(qū)相鄰：將釋放區(qū)與前空閑區(qū)合并為一個(gè)空閑區(qū) 。 分區(qū)的分配是指系統(tǒng)根據(jù)用戶的請(qǐng)求 ， 在空閑區(qū)表或空閑區(qū)隊(duì)列中尋找一個(gè)滿足用戶要求的空閑區(qū) ，把這個(gè)空閑區(qū)分配給用戶 。 這種存儲(chǔ)管理的方法解決了固定分區(qū)嚴(yán)重浪費(fèi)內(nèi)存的問題 。 這是最簡單的一種存儲(chǔ)管理 ,按分區(qū)劃分的時(shí)機(jī)可分為 ? 、固定分區(qū) ? 、動(dòng)態(tài)分區(qū) 29 2022/8/17 第六章 存儲(chǔ)管理 固定分區(qū) ? 固定分區(qū)就是把內(nèi)存固定地劃分為若干個(gè)大小不等的區(qū)域 。 包括： ? 防止地址越界 ? 防止越權(quán) (對(duì)共享區(qū)有訪問權(quán) ) 22 2022/8/17 第六章 存儲(chǔ)管理 存儲(chǔ)保護(hù)的硬件支持 ? 界地址寄存器（界限寄存器） ? 存儲(chǔ)鍵 23 2022/8/17 第六章 存儲(chǔ)管理 界地址寄存器（界限寄存器） ? 界地址寄存器被廣泛使用的一種存儲(chǔ)保護(hù)技術(shù) ? 機(jī)制比較簡單，易于實(shí)現(xiàn) 24 2022/8/17 第六章 存儲(chǔ)管理 實(shí)現(xiàn)方法 ? 在 CPU中設(shè)置一對(duì)下限寄存器和上限寄存器存放用戶作業(yè)在主存中的下限和上限地址 ? 也可將一個(gè)寄存器作為基址寄存器，另一寄存器作為限長寄存器（指示存儲(chǔ)區(qū)長度） ? 每當(dāng) CPU要訪問主存，硬件自動(dòng)將被訪問的主存地址與界限寄存器的內(nèi)容進(jìn)行比較，以判斷是否越界 ? 如果未越界，則按此地址訪問主存，否則將產(chǎn)生程序中斷 —— 越界中斷 （存儲(chǔ)保護(hù)中斷） 25 2022/8/17 第六章 存儲(chǔ)管理 圖示 26 2022/8/17 第六章 存儲(chǔ)管理 主存擴(kuò)充 (虛擬內(nèi)存 ) ? 為了使程序員在編程時(shí)不受內(nèi)存的結(jié)構(gòu)和容量的限制 ， 系統(tǒng)為用戶構(gòu)造一種存儲(chǔ)器 ， 其結(jié)構(gòu)可能與內(nèi)存結(jié)構(gòu)不同 ， 容量可能遠(yuǎn)遠(yuǎn)超過內(nèi)存的實(shí)際容量 。如 空閑區(qū)表、空閑區(qū)隊(duì)列等 。 ? 可以部分地裝入程序運(yùn)行 。一般來說這種轉(zhuǎn)換是由專門的硬件機(jī)構(gòu)來完成的。 5 2022/8/17 第六章 存儲(chǔ)管理 地址映射 Load A 200 3456 。 ? 用戶編程所用的地址稱為 邏輯地址（或程序地址，或虛地址） ，由邏輯地址組成的空間稱為 邏輯地址空間（或程序地址空間） 。 10 2022/8/17 第六章 存儲(chǔ)管理 動(dòng)態(tài)地址映射 ? 動(dòng)態(tài)地址重定位是在程序執(zhí)行的過程中，每次訪問內(nèi)存之前，將要訪問的程序地址轉(zhuǎn)換為內(nèi)存地址。 ? 一個(gè)程序不一定要求占用一個(gè)連續(xù)的內(nèi)存空間 。 19 2022/8/17 第六章 存儲(chǔ)管理 分配結(jié)構(gòu) ? 分配結(jié)構(gòu)是用來登記內(nèi)存使用情況的數(shù)據(jù)結(jié)構(gòu)。 21 2022/8/17 第六章 存儲(chǔ)管理 存儲(chǔ)保護(hù) 保證在內(nèi)存中的多道程序只能在給定的存儲(chǔ)區(qū)域內(nèi)活動(dòng)并互不產(chǎn)生干擾 。 28 2022/8/17 第六章 存儲(chǔ)管理 分區(qū)存貯管理 把整個(gè)內(nèi)存劃分為若干大小不等的區(qū)域 ， 操作系統(tǒng)占用一個(gè)區(qū)域 ， 其它區(qū)域供系統(tǒng)中的多個(gè)進(jìn)程共享 ， 這種方法稱為 分區(qū)存儲(chǔ)管理 。 34 2022/8/17 第六章 存儲(chǔ)管理 動(dòng)態(tài)分區(qū) ? 動(dòng)態(tài)分區(qū)是指在系統(tǒng)運(yùn)行的過程中建立分區(qū) ，并使分區(qū)的大小剛好與作業(yè)的大小相等 。 除操作系統(tǒng)占用一個(gè)分區(qū)外 ， 其余存儲(chǔ)區(qū)為一個(gè)大的空閑區(qū) 。 40 2022/8/17 第六章 存儲(chǔ)管理 分區(qū)的回收 當(dāng)某個(gè)進(jìn)程釋放某存儲(chǔ)區(qū)時(shí) ， 系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰 ， 若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)中去 ， 否則把釋放區(qū)作為一個(gè)空閑區(qū)插入到空閑區(qū)表的適當(dāng)位置 。 從該區(qū)中劃出大小為 SIZE的分區(qū)分配給進(jìn)程 ， 余下的部分仍作為一個(gè)空閑區(qū)留在空閑區(qū)表中 ，但要修改其首址和大小 。 51 2022/8/17 第六章 存儲(chǔ)管理 ? 回收：按釋放區(qū)的首址 ， 查詢空閑區(qū)表 （ 隊(duì)列 ） ， 若有與釋放區(qū)相鄰的空閑區(qū) ， 則合并到相鄰的空閑區(qū)中 ， 并修改該區(qū)的大小和首址 ， 否則 ， 把釋放區(qū)作為一個(gè)空閑區(qū)插入空閑區(qū)表 （ 隊(duì)列 ） 。 若空閑區(qū)小于 SIZE， 則分配失??；否則從空閑區(qū)中分配 SIZE的存儲(chǔ)區(qū)給用戶，然后修改和調(diào)整空閑區(qū)表。 58 2022/8/17 第六章 存儲(chǔ)管理 舉例 ? 例 1：有作業(yè)序列：作業(yè) A要求 18K； 作業(yè) B要求 25K， 作業(yè)C要求 30K。 62 2022/8/17 第六章 存儲(chǔ)管理 分頁存儲(chǔ)管理 ? 分頁存儲(chǔ)管理基本思想 ? 頁地址映射 ? 頁式存儲(chǔ)管理方案小結(jié) 63 2022/8/17 第六章 存儲(chǔ)管理 分頁存儲(chǔ)管理基本思想 ? 在分區(qū)存儲(chǔ)管理中 ， 不論采用什么辦法都會(huì)出現(xiàn)碎片問題 ， 從而降低了內(nèi)存的利用率 。 ? 這樣的數(shù)據(jù)結(jié)構(gòu)稱為 頁表 。 75 2022/8/17 第六章 存儲(chǔ)管理 頁地址映射 ? 分頁中的地址映射其實(shí)與通常的地址映射的概念是一樣的 ， 即把 程序地址轉(zhuǎn)換成內(nèi)存地址 ， 這個(gè)轉(zhuǎn)換過程是在程序執(zhí)行過程中完成的 ， 是 動(dòng)態(tài)地址映射 。 79 2022/8/17 第六章 存儲(chǔ)管理 計(jì)算時(shí)要注意： 若給出的地址字為 16進(jìn)制 ， 則將其轉(zhuǎn)換為二進(jìn)制 ， 然后 ， 根據(jù)頁長及程序地址字的長度 ，分別取出程序地址字的高幾位和低幾位就得到頁號(hào)及頁內(nèi)地址 。 ? 若不解決這一問題是不能令人忍受的 。也就是說訪問頁表的速度大致相當(dāng)了訪問快表的速度，考慮到快表的速度是內(nèi)存速度的數(shù)倍或數(shù)十倍，那么相對(duì)于內(nèi)存速度，訪問頁表的時(shí)間可以忽略不計(jì)。 段表一般包括有段的長度 、 段的首址和存取狀態(tài)等信息 。 103 2022/8/17 第六章 存儲(chǔ)管理 Cl Cb + 段號(hào) S 段內(nèi)地址 d 比較 比較 b + d 段 表 S= Cl 快表 物理地址 段表始址寄存器 段表長度寄存器 邏輯地址 L b . . . S L b 地址越界 d=L d=L 地址映射及存儲(chǔ)保護(hù)機(jī)制 地址越界 地址越界 比較 104 2022/8/17 第六章 存儲(chǔ)管理 分段與分頁技術(shù)的比較 分段與分頁主要有以下差別： ? 段是依據(jù)程序的邏輯結(jié)構(gòu)劃分的 ， 頁是按內(nèi)存線性空間物理劃分的 。 121 2022/8/17 第六章 存儲(chǔ)管理 換入回內(nèi)存時(shí)位置的確定 換出后再換入的內(nèi)存位置一定要在換出前的原來位置上嗎？ 受地址映射技術(shù)的影響，即絕對(duì)地址產(chǎn)生時(shí)機(jī)的限制 122 2022/8/17 第六章 存儲(chǔ)管理 分析 ? 與覆蓋技術(shù)相比，交換技術(shù)不要求用戶給出程序段之間的邏輯覆蓋結(jié)構(gòu)； ? 交換發(fā)生在進(jìn)程或作業(yè)之間，而覆蓋發(fā)生在同一進(jìn)程或作業(yè)內(nèi)。但系統(tǒng)硬件成本也就越高。 138 2022/8/17 第六章 存儲(chǔ)管理 ? 最不經(jīng)常使用（ LFU） 選擇訪問次數(shù)最少的頁面淘汰之 與 LRU的硬件解法類似。 內(nèi)存分配一頁，初始時(shí)矩陣數(shù)據(jù)均不在內(nèi)存； 頁面大小為 128個(gè)整數(shù)；矩陣 A128X128按行存放。 頁號(hào) 塊號(hào) 0 5 1 3 2 7 3 6 165 2022/8/17 第六章 存儲(chǔ)管理 3 1 6 3 7 2 5 0 塊號(hào) 頁號(hào) 01000011011 00010 01000011011 00111 頁表首址 + 0 10 物理地址為： 14875