操作系統(tǒng)---虛擬存儲器管理.ppt

1 請同學(xué)們將手機(jī)關(guān)閉或置于振動保持課堂安靜 第二篇存儲器管理 第一部分基本存儲器管理第二部分內(nèi)存擴(kuò)充技術(shù) 3 內(nèi)存是處理機(jī)可以直接存取指令和數(shù)據(jù)的關(guān)鍵性存儲資源 內(nèi)存容量是計算機(jī)硬件中最關(guān)鍵而又最緊張的 瓶頸 資源 合理而有效地分配和使用內(nèi)存資源 對計算機(jī)系統(tǒng)性能影響很大 為使多道程序能夠在內(nèi)存中有條不紊的存在 存儲器管理的主要任務(wù)是 為多道程序的運(yùn)行提供良好的環(huán)境 方便用戶使用存儲器 提高存儲器的利用率 以及能從邏輯上來擴(kuò)充內(nèi)存 4 在基本的存儲管理系統(tǒng)中 當(dāng)一個作業(yè)的程序地址空間大于內(nèi)存可用空間時 該作業(yè)就不能裝入運(yùn)行 當(dāng)并發(fā)運(yùn)行作業(yè)的程序地址空間總和大于內(nèi)存可用空間時 多道程序設(shè)計的實(shí)現(xiàn)就會碰到很大的困難 內(nèi)存擴(kuò)充技術(shù)就是借助于大容量的外存在邏輯上實(shí)現(xiàn)內(nèi)存的擴(kuò)充 以解決內(nèi)存容量不足的問題 5 虛擬存儲空間 采用軟件技術(shù) 借助于外存從邏輯上對內(nèi)存容量進(jìn)行擴(kuò)充 使用戶感覺到好象在使用一個比實(shí)際容量大得多的內(nèi)存空間 這個經(jīng)過擴(kuò)充的存儲空間稱為虛擬存儲空間 存儲器稱為虛擬存儲器 特征 離散性 采用離散的分配方式 多次性 一個作業(yè)被分成多次調(diào)入內(nèi)存 對換性 作業(yè)在運(yùn)行的過程中被換進(jìn) 換出 虛擬性 從邏輯上擴(kuò)充內(nèi)存容量 6 內(nèi)存擴(kuò)充技術(shù) 授課內(nèi)容 覆蓋技術(shù) 對換技術(shù) 虛擬存儲技術(shù) 7 通過本講的學(xué)習(xí) 學(xué)生將能夠 了解內(nèi)存擴(kuò)充技術(shù) 描述常規(guī)存儲管理方式的特征和程序局部性原理 給出虛擬存儲器的定義 并理解虛擬存儲器的特征 了解請求分頁存儲管理方式及實(shí)現(xiàn) 了解請求分段存儲管理方式及實(shí)現(xiàn) 了解請求段頁存儲管理方式及實(shí)現(xiàn) 了解LINUX系統(tǒng)的存儲器管理策略 教學(xué)目的和要求 8 虛擬存儲器的概念 虛擬存儲中地址映射的實(shí)現(xiàn) 請求分頁系統(tǒng)的基本原理 請求分段系統(tǒng)的基本原理 重點(diǎn) 難點(diǎn) 9 即是將一個大程序按邏輯結(jié)構(gòu)劃分成若干個程序 或數(shù)據(jù) 段 將不必同時裝入內(nèi)存的邏輯段分在一組 覆蓋段 同一組的邏輯段可以同時進(jìn)入內(nèi)存 而不同組的邏輯段公用一個存儲區(qū) 覆蓋區(qū) 舉例 覆蓋技術(shù) 10 一個程序調(diào)用結(jié)構(gòu) 11 實(shí)現(xiàn)覆蓋對程序員是不透明的 為了提高覆蓋效果 用戶在編制程序時就要精心安排好程序的覆蓋結(jié)構(gòu) 并用覆蓋描述語言描述覆蓋和覆蓋段 應(yīng)用在單用戶系統(tǒng)中 為了能在較小的內(nèi)存空間中運(yùn)行大作業(yè) 一些計算機(jī) 如IBM PC 采用 覆蓋 技術(shù) 覆蓋技術(shù) 12 1 單用戶系統(tǒng)中 當(dāng)一個作業(yè)的時間片用完或因等待某一事件而不能繼續(xù)運(yùn)行時 系統(tǒng)就調(diào)選下一個作業(yè)進(jìn)入內(nèi)存運(yùn)行 2 多用戶系統(tǒng)中 將一個進(jìn)程換出內(nèi)存 舉例 對換技術(shù) 13 連續(xù)存儲分配系統(tǒng)中實(shí)現(xiàn)對換技術(shù)的過程 空閑區(qū) 14 實(shí)現(xiàn)在采用可變分區(qū)存儲管理技術(shù)的多道程序設(shè)計中 當(dāng)要運(yùn)行一個高優(yōu)先的作業(yè)而又沒有足夠的空閑內(nèi)存時 可按某一算法從內(nèi)存中換出一個或多個進(jìn)程 騰出空間裝入高優(yōu)先權(quán)的作業(yè) 使之能夠運(yùn)行 應(yīng)用1 單用戶系統(tǒng) 美國麻省理工學(xué)院的兼容分時系統(tǒng)CTSS 2 多用戶系統(tǒng) Windows UNIX等操作系統(tǒng)中 對換技術(shù) 15 課堂練習(xí) 對換 16 一 選擇題1 對外存對換區(qū)的管理應(yīng)以 A 為主要目標(biāo) 對外存文件區(qū)的管理應(yīng)以 B 為主要目標(biāo) A B 1 提高系統(tǒng)吞吐量 2 提高存儲空間的利用率 3 降低存儲費(fèi)用 4 提高換入換出速度 二 問答題1 在系統(tǒng)中引入對換會帶來哪些好處 2 為實(shí)現(xiàn)對換 系統(tǒng)應(yīng)具備哪幾方面的功能 17 要求 以透明的方式提供給用戶一個比實(shí)際內(nèi)存大的多的作業(yè)地址空間 虛擬存儲空間 處理器利用用戶作業(yè)提供的邏輯地址訪問虛擬空間 解決方案 運(yùn)行一個作業(yè)時 并不要求把該作業(yè)的全部程序和數(shù)據(jù)都裝入內(nèi)存 可以只把目前要執(zhí)行的一部分調(diào)入內(nèi)存的空閑區(qū)域中 其余仍保留在外存中 以后根據(jù)作業(yè)的需要再調(diào)入內(nèi)存 當(dāng)作業(yè)運(yùn)行時 需要訪問不在內(nèi)存中的部分時 發(fā)出請求 如內(nèi)存資源緊張 可在原先裝入內(nèi)存的部分中選出一個或多個區(qū)域 將其換出到輔存中 再把所需的部分調(diào)入內(nèi)存 虛擬存儲技術(shù) 18 可以采用虛擬存儲技術(shù)的內(nèi)存管理策略 19 實(shí)現(xiàn)虛擬存儲技術(shù)所需解決的問題 20 課堂練習(xí) 虛擬存儲器 21 一 選擇題1 虛擬存儲器最基本的特征是 A 該特征主要是基于 B 實(shí)現(xiàn)虛擬存儲器最關(guān)鍵的技術(shù)是 C A 1 一次性 2 多次性 3 交換性 4 離散性 5 駐留性 B 1 計算機(jī)的高速性 2 大容量的內(nèi)存 3 大容量的硬盤 4 循環(huán)性原理 5 局部性原理 C 1 內(nèi)存分配 2 置換算法 3 請求調(diào)頁 段 4 對換空間管理 2 虛擬存儲器管理系統(tǒng)的基礎(chǔ)是程序的局部性理論 此理論的基本含義是 A 局部性有兩種表現(xiàn)形式 時間局部性和 B 它們的意義分別是 C 和 D 根據(jù)局部性理論 Denning提出了 E 22 A B 1 代碼的順序執(zhí)行 2 程序執(zhí)行時對主存的訪問是不均勻的 3 數(shù)據(jù)的局部性 4 變量的連續(xù)訪問 5 指令的局部性 6 空間的局部性 C D 1 最近被訪問的單元 很可能在不久的將來還要被訪問 2 最近被訪問的單元 很可能它附近的單元也即將被訪問 3 結(jié)構(gòu)化程序設(shè)計 很少出現(xiàn)轉(zhuǎn)移語句 4 程序中循環(huán)語句的執(zhí)行時間一般很長 5 程序中使用的數(shù)據(jù)局部于各子程序 E 1 Cache結(jié)構(gòu)的思想 2 先進(jìn)先出 FIFO 頁面置換算法 3 工作集理論 4 最近最久未用 LRU 頁面置換算法 3 一個計算機(jī)系統(tǒng)的虛擬存儲器的最大容量是由 A 確定的 其實(shí)際容量是由 B 確定的 A B 1 計算機(jī)字長 2 內(nèi)存容量 3 硬盤容量 4 內(nèi)存和硬盤容量之和 5 計算機(jī)的地址結(jié)構(gòu) 23 二 問答題1 虛擬存儲器有哪些特征 其中最本質(zhì)的特征是什么 2 實(shí)現(xiàn)虛擬存儲器需要哪些硬件支持 3 一個計算機(jī)系統(tǒng)的虛擬存儲器 其最大容量和實(shí)際容量分別由什么決定 24 請求分頁存儲管理方式 一 基本思想運(yùn)行一個作業(yè)時 并不要求把該作業(yè)的全部程序和數(shù)據(jù)都裝入內(nèi)存 可以只把目前要執(zhí)行的幾頁調(diào)入內(nèi)存的空閑物理塊中 其余仍保留在外存中 以后根據(jù)作業(yè)的需要再調(diào)入內(nèi)存 當(dāng)作業(yè)運(yùn)行時 需要訪問其他不在內(nèi)存中的虛頁時 硬件產(chǎn)生 缺頁 信號 若內(nèi)存資源不夠 可在原先已在內(nèi)存的頁面中選擇一個或多個頁 將其換出到外存中 再把所需的頁調(diào)入內(nèi)存 25 請求分頁存儲管理的實(shí)現(xiàn) 問題一 如何知道作業(yè)中的某一部分所在的位置 解答 修改數(shù)據(jù)結(jié)構(gòu) 頁表 需要在頁表中添加相應(yīng)的字段 若頁面在內(nèi)存 給出物理塊號 若頁面在外存 應(yīng)給出在外存中的位置 為每個作業(yè)設(shè)置新的頁表 記錄作業(yè)中的某一頁在虛擬存儲空間的位置 如圖所示 外存地址 頁號 物理塊號 狀態(tài)位 26 問題二 如何發(fā)出請求 使系統(tǒng)能夠根據(jù)需要把在外存上的部分調(diào)入內(nèi)存以保障作業(yè)的連續(xù)運(yùn)行 解答 設(shè)置硬件 缺頁中斷 機(jī)構(gòu) 引起中斷的事件當(dāng)作業(yè)在運(yùn)行過程中試圖訪問一個未在內(nèi)存的頁面時 就產(chǎn)生一個缺頁中斷 轉(zhuǎn)向進(jìn)入缺頁中斷處理子程序 這部分由硬件負(fù)責(zé)實(shí)施 執(zhí)行過程頁表中的狀態(tài)位為中斷請求位 在地址變換過程中 由邏輯地址的頁號查找頁表 求其在內(nèi)存中的物理塊號時 由于此頁不在內(nèi)存 相應(yīng)的狀態(tài)位為1 由機(jī)器硬件自動發(fā)出缺頁中斷信號 引導(dǎo)CPU轉(zhuǎn)去執(zhí)行操作系統(tǒng)的缺頁中斷處理程序 缺頁 中斷的特征1 缺頁中斷可以發(fā)生在一條指令的執(zhí)行中間 2 如果一條指令要訪問多個頁面 如對于間接訪問指令和數(shù)據(jù)傳送指令 還能引起多個缺頁中斷 27 問題三 外存中的部分怎樣能夠放入內(nèi)存 解答 采用適當(dāng)?shù)拇鎯Ψ峙洳呗院驼{(diào)入策略 存儲分配策略1 每個作業(yè)在內(nèi)存中駐留的最小物理塊數(shù)需要給出在內(nèi)存中駐留的最小物理塊數(shù) 否則 隨著為每個進(jìn)程分配的物理塊數(shù)的減少 將使進(jìn)程執(zhí)行中缺頁率提高 確定原則與計算機(jī)的硬件結(jié)構(gòu)相關(guān) 2 頁面分配和置換策略 頁面調(diào)入策略1 調(diào)入時機(jī)2 從何處調(diào)入3 調(diào)入過程 28 頁面分配和置換策略實(shí)現(xiàn) 29 固定分配局部置換策略 基于進(jìn)程的類型 交互型或批處理型等 或根據(jù)程序員 系統(tǒng)管理員的建議 為每個進(jìn)程分配一固定頁數(shù)的內(nèi)存空間 在整個運(yùn)行期間都不再改變 存儲分配過程實(shí)現(xiàn)1 分配過程2 分配算法平均分配算法 按比例分配算法 考慮優(yōu)先權(quán)的分配算法 30 P在內(nèi)存 查找頁表 已分配的物理塊數(shù)n 20 從該作業(yè)A分到的20塊物理塊中剩余的20 n個空閑物理塊中選擇一個分配之 作業(yè)A要進(jìn)入系統(tǒng)中執(zhí)行 采用固定分區(qū)局部置換存儲分配策略 系統(tǒng)為其固定分配20塊內(nèi)存物理塊 當(dāng)前作業(yè)A在內(nèi)存中的頁數(shù)為n頁 系統(tǒng)分析邏輯地址找出頁號P 直接映射為物理地址 由于20塊全占滿 則從中選擇一頁換出 裝入新頁 作業(yè)A讀下一條指令 31 固定分配局部置換策略 性能分析難以確定每個進(jìn)程應(yīng)分配多少個頁面的內(nèi)存空間少 會頻繁地出現(xiàn)缺頁中斷多 駐留于內(nèi)存的作業(yè)數(shù)目減少同時進(jìn)程切換時會浪費(fèi)時間和空間 32 可變分配全局置換策略 一 基本思想先為系統(tǒng)中的每個進(jìn)程分配一定數(shù)目的物理塊 而OS自身也保持一個空閑物理塊隊列 當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁時 由系統(tǒng)從空閑物理塊隊列中取出物理塊分配給該進(jìn)程并將欲調(diào)入的缺頁裝入其中 二 性能分析當(dāng)空閑物理塊隊列中的物理塊用完時 OS才能從內(nèi)存中選擇一頁調(diào)出 該頁可能是系統(tǒng)中任一進(jìn)程的頁 這樣 自然又會使那個進(jìn)程的物理塊減少 進(jìn)而使該進(jìn)程缺頁率增加 33 可變分配局部置換策略 一 基本思想基于進(jìn)程的類型或根據(jù)程序員的要求 為每個進(jìn)程分配一定數(shù)目的內(nèi)存空間 當(dāng)某進(jìn)程發(fā)生缺頁時 只允許從該進(jìn)程在內(nèi)存的頁面中選出一頁換出 但如果進(jìn)程在運(yùn)行中頻繁地發(fā)生缺頁中斷 則系統(tǒng)需再為該進(jìn)程分配附加的物理塊 直至進(jìn)程的缺頁率降低到適當(dāng)程度為止 反之 若一個進(jìn)程在運(yùn)行過程中的缺頁率特別低 則此時可適當(dāng)減少分配給該進(jìn)程的物理塊 但不應(yīng)引起其缺頁率的明顯增加 二 性能分析不會影響其它進(jìn)程的運(yùn)行 34 調(diào)入時機(jī)的選擇 一 預(yù)調(diào)頁策略1 引入原因在外存上查找所缺的頁 需經(jīng)歷較長的時間 如果進(jìn)程的許多頁是存放在外存的一個連續(xù)區(qū)域中 一次調(diào)入若干個相鄰的頁 會比每次調(diào)入一頁更高效 2 基本思想將那些預(yù)計在不久之后便會被訪問的程序或數(shù)據(jù)所在頁面預(yù)先調(diào)入內(nèi)存 3 性能分析如果調(diào)入的一批頁面中的大多數(shù)都未被訪問 則是低效的 目前只應(yīng)用于首次調(diào)入進(jìn)程 35 調(diào)入時機(jī)的選擇 二 請求調(diào)頁策略1 基本思想當(dāng)進(jìn)程在運(yùn)行中需要訪問某部分的程序和數(shù)據(jù)時 發(fā)現(xiàn)其所在的頁面不在內(nèi)存 需立即提出請求 由系統(tǒng)將其所需頁面調(diào)入內(nèi)存 2 性能分析由該策略所確定調(diào)入的頁 是一定會被訪問的 且較易于實(shí)現(xiàn) 目前一般采用此種技術(shù) 但是 在調(diào)頁時 需花費(fèi)較大的系統(tǒng)開銷 增加了磁盤I O的啟動頻率 36 問題四 當(dāng)內(nèi)存空間緊張的情況下 怎樣騰出空間 解答 空間夠用 直接為其分配所需空間 空間緊張 采用適當(dāng)?shù)乃惴ㄟx擇一個或幾個頁面淘汰出內(nèi)存 置換到外存上 1 需要淘汰內(nèi)存中頁面的時機(jī)根據(jù)頁面存儲分配和置換策略 2 淘汰的方法預(yù)測程序執(zhí)行的軌跡 選擇那些今后不會再被訪問或最長的時間里不會被訪問的頁 根據(jù)程序執(zhí)行的局部性原理 3 頁面淘汰算法 37 頁面淘汰算法 38 最近最久未使用LRU算法 一 算法來源 最近最少使用算法1 基本思想 比較最近一段時間里對各個頁面的訪問頻率 淘汰訪問頻率最低的頁面 2 實(shí)現(xiàn) 為內(nèi)存中每一頁設(shè)置一個訪問計數(shù)器 通過比較所有頁面的計數(shù)器值來確定淘汰頁 3 性能分析 這樣的算法實(shí)現(xiàn)起來空間和時間的代價都比較大 同時那些剛調(diào)入的頁也可能訪問次數(shù)少而被淘汰掉 4 改進(jìn) 很多系統(tǒng)都將該算法實(shí)現(xiàn)為淘汰 最近一段時間內(nèi)最久沒有訪問 的頁面 二 算法依據(jù)根據(jù)很多事物和現(xiàn)象的延續(xù)性原理 在最近一段時間內(nèi)不曾訪問過的頁在不久的將來訪問的可能性也較少 39 LRU算法實(shí)現(xiàn) 一 問題分析若一頁剛被訪問過 很可能最近還要被訪問 相反 若一頁最近很長時間都未被訪問過 則最近被訪問的可能性極小 因此 每次訪問一個頁面時都要留下一個 郵戳 淘汰時選擇一個訪問時間最早的頁 也即最后依次訪問離現(xiàn)在最久的頁 二 算法的實(shí)現(xiàn)方法一 設(shè)置隊列單純用軟件實(shí)現(xiàn) 方法二 用硬件實(shí)現(xiàn)隊列結(jié)構(gòu)和操作方法三 硬件支持實(shí)現(xiàn) 郵戳 40 方法1 設(shè)置隊列單純用軟件實(shí)現(xiàn) 基本思想 1 數(shù)據(jù)結(jié)構(gòu)設(shè)置一個非嚴(yán)格意義上的隊列 數(shù)據(jù)對象 qi qi表示隊列中的結(jié)點(diǎn) 每個結(jié)點(diǎn)對應(yīng)一個內(nèi)存頁 基本操作 對隊列的基本操作均可使用 特殊之處在于該隊列可以從中間出隊 2 算法實(shí)現(xiàn)每次訪問到一個頁面之后 將該頁面對應(yīng)的結(jié)點(diǎn)從隊列中抽出 重新排到隊尾 這樣隊首元素即為最長時間沒有訪問到的頁 經(jīng)常要訪問的頁總是排在靠近隊列的尾部 每次只須選擇隊首元素對應(yīng)的頁面淘汰即可 性能分析 實(shí)現(xiàn)該算法的主要困難是如果每執(zhí)行一條訪問內(nèi)存的指令時都要執(zhí)行隊列的操作 并且該操作若是單純用軟件實(shí)現(xiàn)的話 其時間開銷也是難以忍受的 41 方法2 硬件支持實(shí)現(xiàn) 郵戳 需要解決的問題1 一個進(jìn)程在內(nèi)存中的各個頁面各有多久未被訪問 2 如何快速地知道哪一頁是最近最久未使用的頁面 算法實(shí)現(xiàn)1 使用硬件寄存器實(shí)現(xiàn) 數(shù)據(jù)結(jié)構(gòu)為每一個在內(nèi)存中的頁面設(shè)置一個寄存器 用于記錄某進(jìn)程在內(nèi)存中的各頁面的使用情況 42 方法2 硬件支持實(shí)現(xiàn) 郵戳 算法實(shí)現(xiàn)利用寄存器的各數(shù)據(jù)位 R Rn 1Rn 2Rn 3 R1R0當(dāng)CPU訪問頁面所在內(nèi)存物理塊時 相應(yīng)的寄存器的最高位Rn 1置1 每隔一段時間 將寄存器的數(shù)據(jù)位右移1位 因此 寄存器的值記錄了訪問對應(yīng)頁面的次數(shù) 在一定的時間間隔內(nèi) 對應(yīng)寄存器值最小的頁面定是被訪問次數(shù)最少的 將此頁調(diào)出 2 使用硬件棧實(shí)現(xiàn)類似于方法一 只不過設(shè)置棧來保存當(dāng)前使用的各個頁面的頁面號 43 CLOCK置換算法 44 查看第i頁的訪問位 訪問位 1 表示該頁剛被訪問過 暫不換出 由于本次沒訪問 則置該頁訪問位為0 i 表示該頁在最近一段時間內(nèi)未被訪問 換出該頁 簡單CLOCK置換算法工作流程 訪問字段 45 46 有可能再被訪問 最佳淘汰頁 并不是很好的淘汰頁 改進(jìn)CLOCK置換算法的四種組合情況 訪問字段 修改位 47 方法1 系統(tǒng)將內(nèi)存中的各個使用頁組織成一個循環(huán)隊列 并設(shè)置一個循環(huán)檢測指針 工作流程 方法2 不再檢測時清0 而是在系統(tǒng)每過一個適當(dāng)時間 將所頁的 訪問位 置0 當(dāng)需要淘汰一個頁面時 可選擇序號最小 二進(jìn)制值最小 的一頁 方法3 將兩者結(jié)合起來 48 問題五 如何實(shí)現(xiàn)地址映射機(jī)構(gòu) 解答 在基本分頁存儲管理系統(tǒng)的地址變換機(jī)構(gòu)的基礎(chǔ)上 再為實(shí)現(xiàn)虛擬存儲技術(shù)增加 缺頁中斷 處理功能和頁面置換策略功能而實(shí)現(xiàn) 問題要求邏輯地址 物理地址 問題分析邏輯地址 頁號 頁長度 頁內(nèi)偏移量物理地址 物理塊號 塊長度 塊內(nèi)偏移量 實(shí)現(xiàn)通過查找頁表 實(shí)現(xiàn)邏輯地址向物理地址的映射 工作流程 49 啟動要執(zhí)行的指令 保護(hù)中斷現(xiàn)場 該頁在內(nèi)存中 準(zhǔn)備執(zhí)行下條指令 硬件 軟件 內(nèi)存中有空閑塊 取塊號 形成物理地址 完成這條訪內(nèi)指令 修改頁表和MBT 恢復(fù)被中斷現(xiàn)場 準(zhǔn)備執(zhí)行被中斷指令 把該頁寫回外存 修改MBT 使該頁的內(nèi)存塊變?yōu)榭臻e塊 選擇一頁準(zhǔn)備淘汰 該頁被修改過 根據(jù)外存地址把缺頁讀入 計算頁號 50 請求分頁存儲管理方式的主要功能 1 執(zhí)行地址變換操作 將程序虛擬地址轉(zhuǎn)換為物理地址 2 缺頁時自動觸發(fā)頁面中斷機(jī)構(gòu) 3 缺頁中斷之后 能夠根據(jù)需要將外存上的頁面調(diào)入內(nèi)存來保障作業(yè)的連續(xù)運(yùn)行 51 一 缺頁率對有效訪問時間的影響有效訪問時間 1 p ma p 缺頁中斷時間其中 p 缺頁率 ma 存儲器的訪問時間 缺頁中斷時間 缺頁中斷服務(wù)時間 將缺頁讀入的時間 進(jìn)程重新執(zhí)行的時間 有效訪問時間直接比例于缺頁率 請求分頁存儲管理的性能分析 52 二 工作集1 工作集概念的引入 缺頁率與物理塊數(shù)的關(guān)系程序在運(yùn)行時對頁面的訪問是不均勻的 往往在某段時間內(nèi)的訪問僅局限于較少的若干個頁面 而在另一段時間內(nèi) 則又可能僅局限于另一些較少的頁面進(jìn)行訪問 如果能預(yù)知程序在某段時間間隔內(nèi)要訪問哪些頁面 并能將它們提前調(diào)入內(nèi)存 將會大大地降低缺頁率 從而減少置換工作 提高CPU的利用率 2 工作集 在某段時間間隔 里 進(jìn)程實(shí)際要訪問的頁面的集合 請求分頁存儲管理的性能分析 53 三 抖動產(chǎn)生的原因和預(yù)防方法1 抖動產(chǎn)生的原因運(yùn)行進(jìn)程的大部分時間都用于進(jìn)行頁面的換入 換出 而幾乎不能完成任何有效的工作 我們稱這時的進(jìn)程是處于 抖動 狀態(tài) 2 抖動的預(yù)防 采用局部置換策略 在CPU調(diào)度程序中引入工作集算法 L S準(zhǔn)則 掛起若干進(jìn)程 請求分頁存儲管理的性能分析 54 課堂練習(xí) 請求分頁存儲管理方式 55 一 選擇題1 在請求分頁系統(tǒng)的頁表中增加了若干項 其中狀態(tài)位供 A 參考 修改位供 B 時參考 訪問位供 C 時參考 A B C 1 分配頁面 2 置換算法 3 程序訪問 4 換出頁面 5 調(diào)入頁面 2 在請求調(diào)頁系統(tǒng)中 若邏輯地址中的頁號超過頁表控制寄存器中頁表長度 則會引起 A 否則 若所需的頁不在內(nèi)存中 則會引起 B A B 1 輸入 輸出中斷 2 時鐘中斷 3 越界中斷 4 缺頁中斷 3 在請求調(diào)頁系統(tǒng)中 內(nèi)存分配有 A 和 B 兩種策略 A 的缺點(diǎn)是可能導(dǎo)致頻繁地出現(xiàn)缺頁中斷而造成CPU利用率下降 A B 1 首次適應(yīng) 2 最佳適應(yīng) 3 固定分配 4 可變分配 56 3 在請求調(diào)頁系統(tǒng)中有多種置換算法 1 選擇最先進(jìn)入內(nèi)存的頁面予以淘汰的算法稱為 A 2 選擇在以后不再使用的頁面予以淘汰的算法稱為 B 3 選擇自上次訪問以來所經(jīng)歷時間最長的的頁面予以淘汰的算法稱為 C 4 選擇自某時刻開始以來 訪問次數(shù)最少的頁面予以淘汰的算法稱為 D A B C D 1 FIFO算法 2 OPT算法 3 LRU算法 4 NRU算法 5 LFU算法 4 在請求調(diào)頁系統(tǒng)中 凡未裝入過內(nèi)存的頁都應(yīng)從 A 調(diào)入 已運(yùn)行過的頁主要是從 B 調(diào)入 有時也從 C 調(diào)入 A B C 1 系統(tǒng)區(qū) 2 文件區(qū) 3 對換區(qū) 4 頁面緩沖池 57 5 某虛擬存儲器的用戶編程空間共32個頁面 每頁1K 主存為16K 假定某時刻用戶頁表中已調(diào)入主存的頁面的虛頁號和物理塊號對照表如下表所示 則與下面十六進(jìn)制虛地址相對應(yīng)的物理地址為 如果主存中找不到 即為頁失效 58 A B 1 頁失效 2 1E5C 3 2A5C 4 165C 6 125C C 1 硬件 2 軟件 3 硬軟件結(jié)合 D 1 高速輔助存儲器 2 高速光盤存儲器 3 快速通道 4 高速緩沖存儲器 E 1 連接編輯 2 虛空間分配 3 動態(tài)地址翻譯 4 動態(tài)鏈接 59 6 測定某個請求調(diào)頁系統(tǒng)的計算機(jī)系統(tǒng)部分狀態(tài)數(shù)據(jù)為 CPU利用率20 用于對換空間的硬盤的利用率97 7 其他設(shè)備利用率5 由此斷定系統(tǒng)出現(xiàn)異常 此種情況下 A 或 B 能提高CPU利用率 A 1 安裝一個更快的硬盤 2 通過擴(kuò)大硬盤容量 增加對換空間 3 增加運(yùn)行進(jìn)程數(shù) 4 減少運(yùn)行的進(jìn)程數(shù) B 1 加內(nèi)存條 增加物理空間容量 2 增加一個更快速的CPU 3 增加其他更快的I O設(shè)備 4 使用訪問速度更快的內(nèi)存條 60 7 在UNIX系統(tǒng)中 請求調(diào)頁是采用 A 算法 對物理塊的分配采用 B 策略 如果被換出的頁的內(nèi)容并未被修改 但對換區(qū)中尚無拷貝 此時應(yīng)將它 C 若被換出的頁的內(nèi)容已被修改 應(yīng)將它 D A 1 LFU 2 FIFO 3 NRU 4 LRU 5 OPT B 1 固定分配局部置換 2 可變分配全局置換 3 可變分配局部置換 4 固定分配全局置換 C D 1 換出到對換區(qū) 2 換出到文件區(qū) 3 送回用戶區(qū) 4 送空閑頁表鏈中 既不必?fù)Q出 61 二 問答題1 在請求分頁系統(tǒng)中 頁表應(yīng)包含哪些數(shù)據(jù)項 每項的作用是什么 2 在請求分頁系統(tǒng)中 通常應(yīng)采用哪種頁面分配方式 為什么 3 在請求分頁系統(tǒng)中 應(yīng)從何處將所需頁面調(diào)入內(nèi)存 4 在請求分頁系統(tǒng)中 常采用哪幾種頁面置換算法 62 5 試說明請求分頁系統(tǒng)中的缺頁中斷處理過程 6 假定占有m塊 初始為空 的進(jìn)程有一個頁訪問串 這個訪問串的長度為p 其中涉及到n個不同的頁號 請問 在訪問過程中缺頁中斷次數(shù)的下界為多少 缺頁中斷次數(shù)的上界又為多少 7 試說明改進(jìn)Clock置換算法的基本原理 8 什么是抖動 產(chǎn)生抖動的原因是什么 63 請求分段存儲管理方式 基本思想運(yùn)行一個作業(yè)時 并不要求把該作業(yè)的全部程序和數(shù)據(jù)都裝入內(nèi)存 可以只把目前要執(zhí)行的幾段調(diào)入內(nèi)存的空閑分區(qū)中 其余仍保留在外存中 以后根據(jù)作業(yè)的需要再調(diào)入內(nèi)存 當(dāng)作業(yè)運(yùn)行時 需要訪問其他不在內(nèi)存中的邏輯段時 硬件產(chǎn)生 缺段 信號 若內(nèi)存資源不夠 可在原先已在內(nèi)存的邏輯段中選擇一個或多個段 將其換出到外存中 再把所需的段調(diào)入內(nèi)存 實(shí)現(xiàn) 64 請求分段存儲管理的實(shí)現(xiàn) 問題一 如何知道作業(yè)中的某一部分所在的位置 解答 修改數(shù)據(jù)結(jié)構(gòu) 段表 需要在段表中添加相應(yīng)的字段 若邏輯段在內(nèi)存 給出該段在內(nèi)存中的起始地址 若邏輯段在外存 給出該段在外存中的起始地址 為每個作業(yè)設(shè)置新的段表 記錄作業(yè)中的某一邏輯段在虛擬存儲空間的位置 如圖所示 外存基址 段名 段長 段的基址 存在位 65 問題二 如何發(fā)出請求 使系統(tǒng)能夠根據(jù)需要把在外存上的部分調(diào)入內(nèi)存以保障作業(yè)的連續(xù)運(yùn)行 解答 設(shè)置硬件 缺段中斷 機(jī)構(gòu) 引起中斷的事件當(dāng)作業(yè)在運(yùn)行過程中試圖訪問一個未在內(nèi)存的邏輯段時 就產(chǎn)生一個缺段中斷 轉(zhuǎn)向進(jìn)入缺段中斷處理子程序 這部分由硬件負(fù)責(zé)實(shí)施 執(zhí)行過程段表中的存在位為中斷請求位 缺段 中斷的特征1 缺段中斷可以發(fā)生在一條指令的執(zhí)行中間 2 如果一條指令要訪問多個邏輯段 如對于間接訪問指令和數(shù)據(jù)傳送指令 還能引起多個缺段中斷 66 問題三 外存中的部分怎樣能夠放入內(nèi)存 解答 采用適當(dāng)?shù)拇鎯Ψ峙洳呗院驼{(diào)入策略 問題四 當(dāng)內(nèi)存空間緊張的情況下 怎樣騰出空間 解答 采用適當(dāng)?shù)乃惴ㄟx擇一個或幾個邏輯段淘汰 問題五 如何實(shí)現(xiàn)地址映射機(jī)構(gòu) 解答 在基本分段系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上加入 缺段中斷 機(jī)制和邏輯段的調(diào)入和淘汰策略 67 課堂練習(xí) 請求分段存儲管理方式 68 一 選擇題1 從下面關(guān)于請求分段存儲器管理的敘述中 選出一條正確的敘述 1 分段的尺寸受內(nèi)存空間的限制 且作業(yè)總的尺寸也受內(nèi)存空間的限制 2 分段的尺寸受內(nèi)存空間的限制 但作業(yè)總的尺寸不受內(nèi)存空間的限制 3 分段的尺寸不受內(nèi)存空間的限制 且作業(yè)總的尺寸不受內(nèi)存空間的限制 4 分段的尺寸不受內(nèi)存空間的限制 但作業(yè)總的尺寸受內(nèi)存空間的限制 二 問答題1 請說明段的置換與頁的置換有什么區(qū)別 69 第二篇作業(yè) 4 虛擬存儲器 70 1 本題使用十進(jìn)制值 頁大小為2000字節(jié) 頁表如下 下列哪些虛擬地址將產(chǎn)生缺頁 對于那些不產(chǎn)生缺頁的 轉(zhuǎn)換后的物理地址是什么 1 10451 2 5421 3 14123 4 9156 71 2 某系統(tǒng)使用請求分頁存儲管理 如果頁在內(nèi)存中 滿足一個內(nèi)存請求需要200ms 如果頁不在內(nèi)存 如有空閑的頁框或沒有修改換出的頁 則請求需要7ms 如果替換出的頁已被修改則需15ms 如果缺頁率是5 并且60 的時間用于修改要換出的頁 問有效訪問時間是多長 假設(shè)系統(tǒng)只運(yùn)行一個進(jìn)程且頁交換時CPU空閑 3 舉例說明訪問程序內(nèi)的變量 指令 會導(dǎo)致時間和局部性 4 給出一個FIFO替換算法的引用串 使得當(dāng)頁框數(shù)從3個增加到4個時 造成Belady異?，F(xiàn)象 72 5 給定一個4頁框的系統(tǒng) 下面的表表示頁號 裝入時間 最后訪問時間 頁面重寫標(biāo)志位和訪問位 1 FIFO算法將替換哪一頁 2 LRU算法將替換哪一頁 3 NRU算法將替換哪一頁 4 CLOCK將替換哪一頁 73 6 有一個請求分頁系統(tǒng) 整數(shù)占4字節(jié) 頁大小為256字節(jié) 使用LRU頁面替換算法 每個進(jìn)程分配3個頁框 一個進(jìn)程執(zhí)行下列代碼 inta newint 200 200 inti 0 j 0 while i 200 j 0 while j 200 a i j 0 這段代碼占用第0頁 由于每條指令都訪問第0頁 所以第0頁總是被換入 變量i和j都存儲在快速寄存器里 1 假設(shè)數(shù)據(jù)的所有元素都存儲在連續(xù)的內(nèi)存區(qū)域中 那么數(shù)據(jù)需要多少頁 2 這個程序?qū)a(chǎn)生多少個缺頁 74 75 7 某系統(tǒng)使用請求分頁段式管理 有16位的虛地址空間 每個進(jìn)程有2個段 頁的大小為212 段頁表的內(nèi)容說明如下 均為二進(jìn)制 段長是頁大小的增量 對于以下二進(jìn)制虛地址 求它們轉(zhuǎn)換后的物理地址 或說明它們是否產(chǎn)生缺頁或段故障 1 0001010001010111 2 1110010011111111 3 1111010011000111 4 0011001011000111 76 課堂練習(xí) 綜合性練習(xí) 77 一 選擇題1 從下列關(guān)于存儲器管理功能的論述中 選出兩條正確的論述 1 即使在多道程序設(shè)計的環(huán)境下 用戶也能設(shè)計用物理地址直接訪問內(nèi)存的程序 2 內(nèi)存分配最基本的任務(wù)是為每道程序分配內(nèi)存空間 其所追求的主要目標(biāo)是提高存儲空間的利用率 3 為了提高內(nèi)存保護(hù)的靈活性 內(nèi)存保護(hù)通常由軟件實(shí)現(xiàn) 4 交換技術(shù)已不是現(xiàn)代操作系統(tǒng)中常用的技術(shù) 5 地址映射是指將程序空間中的邏輯地址變?yōu)閮?nèi)存空間的物理地址 6 虛擬存儲器是物理上擴(kuò)充內(nèi)存容量 78 2 提高內(nèi)存利用率主要是通過 A 功能實(shí)現(xiàn)的 A 的基本任務(wù)是為每道程序做 B 使每道程序能在不受干擾的環(huán)境下運(yùn)行 主要是通過 C 功能實(shí)現(xiàn)的 A C 1 內(nèi)存分配 2 內(nèi)存保護(hù) 3 地址映射 4 對換 5 內(nèi)存擴(kuò)充 B 1 邏輯地址到物理地址的變換 2 內(nèi)存到外存間交換 3 允許用戶程序的地址空間大于內(nèi)存空間 4 分配內(nèi)存 3 由連續(xù)分配方式發(fā)展為分頁存儲管理方式的主要推動力是 A 由分頁系統(tǒng)發(fā)展為分段系統(tǒng) 進(jìn)而又發(fā)展為段頁式系統(tǒng)的主要動力是 B 和