【正文】 號(hào) 。 由此構(gòu)成二級(jí)頁表 。也就是說頁地址變換不會(huì)造成進(jìn)程運(yùn)行速度的下降。 快表表項(xiàng)： 頁號(hào)；內(nèi)存塊號(hào)；標(biāo)識(shí)位；淘汰位 87 2022/8/17 第六章 存儲(chǔ)管理 p’ 頁表 地址越界 L 比較 P=L p p’ . . . 快表 b + 頁號(hào) p 頁內(nèi)地址 d P’ d 物理地址 頁表地址寄存器 頁表長(zhǎng)度寄存器 邏輯地址 地址映射機(jī)制 88 2022/8/17 第六章 存儲(chǔ)管理 分析 ? 當(dāng)調(diào)度合理時(shí)，可以達(dá)到 97％的效率。 86 2022/8/17 第六章 存儲(chǔ)管理 ? 實(shí)際上我們并不需要一個(gè)很大的快速存儲(chǔ)器 ， 有一個(gè)能存放 16個(gè)頁表表目的快速存儲(chǔ)器就夠了 。 ? 快表又叫 相聯(lián) (聯(lián)想 )存儲(chǔ)器 （ associative memory） 或 TLB（ Translation lookaside buffers） 85 2022/8/17 第六章 存儲(chǔ)管理 討論 深入一點(diǎn)的討論： 一個(gè)程序可能會(huì)很大 ， 如 1M， 若頁長(zhǎng)為 1K， 則該程序有 1000個(gè)頁 ， 則該程序的頁表就需要 1000個(gè)表項(xiàng) ， 當(dāng)程序更大時(shí) ， 頁表會(huì)更大 ， 那么我們應(yīng)該有一個(gè)多大的快速存儲(chǔ)器才能滿足要求呢 ？ 這會(huì)遇到兩個(gè)問題： ? 可能快速存儲(chǔ)器多大都是不夠的 ， 因?yàn)槌绦蚩赡軙?huì)更大 。 84 2022/8/17 第六章 存儲(chǔ)管理 ? 解決這個(gè)問題的一種方法是把頁表放在一組快速存儲(chǔ)器中 （ Cache） ， 從而加快訪問內(nèi)存的速度 。（ 主要用來判斷訪問是否越權(quán) ） 83 2022/8/17 第六章 存儲(chǔ)管理 快表和聯(lián)想存儲(chǔ)器 ? 在前述的頁地址變換過程中有一個(gè)嚴(yán)重的問題 ， 那就是每一次對(duì)內(nèi)存的訪問都要訪問頁表 ， 頁表是放在內(nèi)存中的 ， 也就是說每一次訪問內(nèi)存的指令至少要訪問兩次內(nèi)存 ， 運(yùn)行速度要下降一半 。 一 、 在分離程序地址字的頁號(hào)和頁內(nèi)地址時(shí)判別訪問是否合法 ， 若產(chǎn)生的頁號(hào)滿足下式為合法： 0=頁號(hào) 程序地址空間的頁數(shù) 上述判斷由硬件自動(dòng)做 ， 若不合法 ， 硬件產(chǎn)生 越界中斷 ， 由操作系統(tǒng)的越界中斷處理程序進(jìn)行處理 。 如程序地址為 8457， 頁長(zhǎng)為 4KB， 則8457/4096可得：商為 2，余數(shù)為 256。 如頁長(zhǎng)為 2K， 程序地址字為 16位 ， 則高 5位為頁號(hào) ， 低 11位為頁內(nèi)地址 。 系統(tǒng)就以 MR中的地址訪問內(nèi)存 硬件能自動(dòng)分離出頁號(hào)和頁內(nèi)地址 ， 但我們只能通過計(jì)算才能得到 。 78 2022/8/17 第六章 存儲(chǔ)管理 ? 根據(jù)頁號(hào) P=2， 硬件自動(dòng)查該進(jìn)程的頁表 ， 找到第 2頁對(duì)應(yīng)的塊號(hào)為 7， 將塊號(hào)送到內(nèi)存地址寄存器 MR的高 10位中 。 77 2022/8/17 第六章 存儲(chǔ)管理 說明 ? 在執(zhí)行指令 MOV r1， [2500]時(shí) ， 地址轉(zhuǎn)換步驟如下： ? 取出程序地址字 2500送虛地址寄存器 VR， 然后由硬件分離出頁號(hào) P和頁內(nèi)地址 W， 實(shí)際上分離出頁號(hào)和頁內(nèi)地址是一件很簡(jiǎn)單的事 ， 因?yàn)轫撻L(zhǎng)為 1K， 所以頁內(nèi)地址占 10位 （ 09位 ） ， 頁號(hào)占 6位 （ 1015位 ） ，所以硬件只要簡(jiǎn)單地取出 VR寄存器中的高 6位即為頁號(hào) ， 低 10 位即為頁內(nèi)地址 。 ? 在現(xiàn)代計(jì)算機(jī)系統(tǒng)中 ， 由系統(tǒng)提供的地址映射硬件來完成地址映射工作 。 ? IBM AS/400 VAX NS32032 ： 512字節(jié) ? Intel 80386 Motorola 68030 4096字節(jié) 頁的大小是 2K ， k： 912。 頁號(hào) 塊號(hào) 其它 0 5 … 1 65 … 2 13 … 73 2022/8/17 第六章 存儲(chǔ)管理 例 ? 如圖 ， 作業(yè) 1有 2頁分別裝入內(nèi)存的第 6塊；作業(yè) 2有 3頁裝入內(nèi)存的第 7塊；作業(yè) 3有 1 頁裝入內(nèi)存的第 8塊 。 72 2022/8/17 第六章 存儲(chǔ)管理 頁表內(nèi)容 ? 頁表包含以下幾個(gè)表項(xiàng)： ? 頁號(hào)：登記程序地址空間的頁號(hào) 。 71 2022/8/17 第六章 存儲(chǔ)管理 ? 系統(tǒng)為 每個(gè)進(jìn)程建立一個(gè)頁表 ， 頁表的長(zhǎng)度和首地址存放在該進(jìn)程的進(jìn)程控制塊 （ PCB） 中 。邏輯上相鄰的頁，物理上不一定相鄰 68 2022/8/17 第六章 存儲(chǔ)管理 . . . 0 1 2 3 4 5 6 0 1 2 3 4 5 6 作業(yè)的 地址空間 頁框 （物理塊） 頁號(hào) 頁表 主存中頁框（物理塊） . . . . 69 2022/8/17 第六章 存儲(chǔ)管理 頁地址映射 ? 頁表 ? 頁大小的選擇 ? 頁地址映射 ? 分頁存儲(chǔ)管理中的信息保護(hù) ? 快表和聯(lián)想存儲(chǔ)器 ? 兩級(jí)頁表和多級(jí)頁表 70 2022/8/17 第六章 存儲(chǔ)管理 頁表 ? 將頁號(hào)和頁內(nèi)地址轉(zhuǎn)換成內(nèi)存地址 ， 必須要有一個(gè)數(shù)據(jù)結(jié)構(gòu) ， 用來登記頁號(hào)和塊的對(duì)應(yīng)關(guān)系和有關(guān)信息 。 從 0開始編制頁號(hào) ，頁內(nèi)地址是相對(duì)于 0編址 65 2022/8/17 第六章 存儲(chǔ)管理 ? 邏輯地址 用戶程序的劃分是由系統(tǒng)自動(dòng)完成的，對(duì)用戶是透明的。 這種技術(shù)對(duì)操作系統(tǒng)的發(fā)展產(chǎn)生了深遠(yuǎn)影響 。雖然采用壓縮存儲(chǔ)區(qū)的方法可以解決碎片問題 ， 但系統(tǒng)開銷太大 ， 而無實(shí)用價(jià)值 ， 必須尋求新的技術(shù)來解決這一問題 ， 于是分頁技術(shù)產(chǎn)生了 。 ? 定期壓縮存儲(chǔ)空間，將所有空閑區(qū)集中到內(nèi)存的一端，但這種方法的系統(tǒng)開銷太大。 碎片的出現(xiàn)造成了存儲(chǔ)空間的浪費(fèi) 。 60 2022/8/17 第六章 存儲(chǔ)管理 碎片問題 ? 由于空閑區(qū)的大小與申請(qǐng)內(nèi)存的大小相等的情況是很少的 ， 絕大多數(shù)情況是從一個(gè)空閑區(qū)中切去一塊 ， 剩下的部分作為一個(gè)空閑區(qū)仍留在空閑區(qū)表中 ， 隨著時(shí)間的推移 ， 空閑區(qū)的發(fā)展趨勢(shì)是越來越小 ， 直至不能滿足任何用戶要求 。 系統(tǒng)中空閑區(qū)按三種算法組成的空閑區(qū)隊(duì)列 ? 經(jīng)分析可知：最佳適應(yīng)法對(duì)這個(gè)作業(yè)序列是合適的 ， 而其它兩種對(duì)該作業(yè)序列是不合適的 。 ? 對(duì)于某一算法而言，如它不能立即滿足某一要求，而其它算法卻可以滿足此要求，則 這一算法對(duì)該作業(yè)序列是不合適的 。 57 2022/8/17 第六章 存儲(chǔ)管理 三種策略比較 ? 上述三種放置策略各有利弊 ， 到底哪種最好不能一概而論 ， 而應(yīng)針對(duì)具體作業(yè)序列來分析 。 56 2022/8/17 第六章 存儲(chǔ)管理 分析 最壞適應(yīng)法看起來公似乎有些荒唐 ， 但在更加嚴(yán)密地考察后 ， 還是有它的優(yōu)點(diǎn)： ? 當(dāng)程序裝入內(nèi)存中最大的空閑區(qū)后 ， 剩下的空閑區(qū)還可能相當(dāng)大 ， 還能裝下較大的程序 。 55 2022/8/17 第六章 存儲(chǔ)管理 ? 回收：按釋放區(qū)的首址 ， 查詢空閑區(qū)表 （ 隊(duì)列 ） ， 若有與釋放區(qū)相鄰的空閑區(qū) ， 則合并到相鄰的空閑區(qū)中 ， 并修改該區(qū)的大小和首址 ， 否則 ， 把釋放區(qū)作為一個(gè)空閑區(qū)插入空閑區(qū)表 （ 隊(duì)列 ） 。 54 2022/8/17 第六章 存儲(chǔ)管理 ? 分配：進(jìn)程申請(qǐng)一個(gè)大小為 SIZE的存儲(chǔ)區(qū)時(shí)，總是檢查空閑區(qū)表的第一個(gè)空閑區(qū)的大小是否大于或等于 SIZE。隨著時(shí)間的推移，系統(tǒng)中的小空閑區(qū)會(huì)越來越多，從而造成存儲(chǔ)區(qū)的大量浪費(fèi)。 ? 若系統(tǒng)中不存在與申請(qǐng)分區(qū)大小相等的空閑區(qū) ， 則選中的空閑區(qū)是滿足要求的最小空閑區(qū) ， 而不致于毀掉較大的空閑區(qū) 。 ? 分配和回收后要對(duì)空閑區(qū)表 （ 隊(duì)列 ） 重新排序 。 ? 所謂最佳即選中的空閑區(qū)是滿足要求的最小空閑區(qū)。 49 2022/8/17 第六章 存儲(chǔ)管理 最佳適應(yīng)法 ? 要求按 空閑區(qū)大小從小到大 的次序組成空閑區(qū)表（隊(duì)列）。 首次適應(yīng)法的優(yōu)點(diǎn)： ? 釋放某一存儲(chǔ)區(qū)時(shí) ， 若與空閑區(qū)相鄰則合并到相鄰空閑分區(qū)中去 ， 這種情況并不改變?cè)搮^(qū)在表中的位置 ， 只要修改其大小或首址 。 47 2022/8/17 第六章 存儲(chǔ)管理 ? 回收：按釋放區(qū)的首址 ， 查詢空閑區(qū)表 ， 若有與釋放區(qū)相鄰的空閑區(qū) ， 則合并到相鄰的空閑區(qū)中 ， 并修改該區(qū)的大小和首址 ， 否則 ，把釋放區(qū)作為一個(gè)空閑區(qū) ， 將其大小和首址按照首地址大小遞增 的順序插入到空閑區(qū)表的適當(dāng)位置 。 46 2022/8/17 第六章 存儲(chǔ)管理 ? 分配：當(dāng)進(jìn)程申請(qǐng)大小為 SIZE的內(nèi)存時(shí) ， 系統(tǒng)從空閑區(qū)表的第一個(gè)表目開始查詢 ， 直到首次找到等于或大于 SIZE的空閑區(qū) 。 ? 釋放區(qū)不與任何空閑區(qū)相鄰：將釋放區(qū)作為一個(gè)空閑區(qū)，將其大小和首址插入到空閑區(qū)表的適當(dāng)位置。 ? 釋放區(qū)與前后兩個(gè)空閑區(qū)相鄰：將這三個(gè)區(qū)合為一個(gè)空閑區(qū) ， 其首址為前空閑區(qū)首址 ， 大小為這三個(gè)區(qū)大小之和 ， 并取消原后空閑區(qū)表目 。 41 2022/8/17 第六章 存儲(chǔ)管理 釋放區(qū)與空閑區(qū)相鄰的四種情況 42 2022/8/17 第六章 存儲(chǔ)管理 說明 ? 釋放區(qū)與前空閑區(qū)相鄰：將釋放區(qū)與前空閑區(qū)合并為一個(gè)空閑區(qū) 。 一般常采用第二種辦法 ， 因?yàn)檫@樣劃分時(shí) ，余下的部分在空閑區(qū)表中的首地址不變 ， 只需要修改一下大小就行了 。 39 2022/8/17 第六章 存儲(chǔ)管理 ? 其三是空閑區(qū)大于 SIZE， 這時(shí)將空閑區(qū)一分為二 。 38 2022/8/17 第六章 存儲(chǔ)管理 分配時(shí)的三種情況 ? 其一是系統(tǒng)中無滿足要求的空閑區(qū) ， 則分配失敗 。 分區(qū)的分配是指系統(tǒng)根據(jù)用戶的請(qǐng)求 ， 在空閑區(qū)表或空閑區(qū)隊(duì)列中尋找一個(gè)滿足用戶要求的空閑區(qū) ，把這個(gè)空閑區(qū)分配給用戶 。 36 2022/8/17 第六章 存儲(chǔ)管理 空閑區(qū)表和空閑區(qū)隊(duì)列舉例 37 2022/8/17 第六章 存儲(chǔ)管理 動(dòng)態(tài)分區(qū)的分配和回收 分區(qū)的分配 在采用分區(qū)存儲(chǔ)管理的系統(tǒng)中 ， 系統(tǒng)初啟后 。 常用的有 表結(jié)構(gòu)和隊(duì)列結(jié)構(gòu) 。 35 2022/8/17 第六章 存儲(chǔ)管理 實(shí)現(xiàn)動(dòng)態(tài)分區(qū)需要的數(shù)據(jù)結(jié)構(gòu) ? 在動(dòng)態(tài)分區(qū)存儲(chǔ)管理中 ， 要有相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來登記空閑區(qū)的說明信息 ， 它包括空閑區(qū)的大小和位置 。 這種存儲(chǔ)管理的方法解決了固定分區(qū)嚴(yán)重浪費(fèi)內(nèi)存的問題 。 ? 但是若作業(yè)的大小和出現(xiàn)的頻率不知道時(shí) ， 勢(shì)必造成分區(qū)的大小和作業(yè)的大小相差甚遠(yuǎn) ， 這樣就會(huì)造成存儲(chǔ)空間的浪費(fèi) ， 從而影響整個(gè)系統(tǒng)的效率 。 如下圖 31 2022/8/17 第六章 存儲(chǔ)管理 圖示 32 2022/8/17 第六章 存儲(chǔ)管理 分區(qū)說明表 分區(qū)號(hào) 大小(KB) 始址 狀態(tài) 1 8 20 已分配 2 32 28 已分配 3 64 60 已分配 4 132 124 未分配 33 2022/8/17 第六章 存儲(chǔ)管理 固定分區(qū)性能分析 ? 在作業(yè)大小和出現(xiàn)頻率均已知的情況下 ， 固定分區(qū)是合適的 。 ? 早期的 IBM的 OS/360MFT（ 具有固定任務(wù)數(shù)的多道程序系統(tǒng) ） 采用了這種固定分區(qū)的方法 。 這是最簡(jiǎn)單的一種存儲(chǔ)管理 ,按分區(qū)劃分的時(shí)機(jī)可分為 ? 、固定分區(qū) ? 、動(dòng)態(tài)分區(qū) 29 2022/8