第二章 習(xí)題解答.ppt

某系統(tǒng)采用動態(tài)分區(qū)存儲管理技術(shù) 某時刻內(nèi)存中有三個空閑區(qū) 它們的首地址和大小分別為 空閑區(qū)1 100KB 10KB 空閑區(qū)2 200KB 30KB 空閑區(qū)3 300KB 15KB 1 畫出該時刻內(nèi)存分配圖 2 用首次適應(yīng)法和最佳適應(yīng)法畫出此時的空閑分區(qū)鏈 3 有如下作業(yè)序列 作業(yè)1需求15KB 作業(yè)2需求16KB 作業(yè)3需求10KB 用哪種算法能將該作業(yè)序列裝入內(nèi)存 給出簡要分配過程 100K 1 110K 200K 230K 300K 315K 2 首次適應(yīng)法 最佳適應(yīng)法 3 首次適應(yīng)法 最佳適應(yīng)法 若在一分頁存儲管理系統(tǒng)中 某作業(yè)的頁表如下所示 已知頁面大小為1024字節(jié) 試將邏輯地址1011 2148 3000 5012轉(zhuǎn)化為相應(yīng)的物理地址 注 此處塊號即為頁面號 為了描述方便 設(shè)頁號為P 頁內(nèi)位移為W 邏輯地址為A 內(nèi)存地址為M 頁面大小為L 則P int A L W AmodL對于邏輯地址1011P int 1011 1024 0W 1011mod1024 1011A 1101 0 1101 查頁表第0頁在第2塊 所以物理地址為M 1024 2 1101 3059 對于邏輯地址為2148P 2148 1024 2W 2148mod1024 100A 2148 2 100 查頁表第2頁在第1塊 所以物理地址為M 1024 1 100 1124 對于邏輯地址為3000P 3000 1024 2W 3000mod1024 952A 3000 2 952 查頁表第2頁在第1塊 所以物理地址為M 1024 1 952 1976對于邏輯地址5012P 5012 1024 4W 5012mod1024 916因頁號超過頁表長度 該邏輯地址非法 某段式存儲管理系統(tǒng)中 有一作業(yè)的段表 SMT 如下表所示 求邏輯地址 0 65 1 55 2 90 3 20 對應(yīng)的主存地址 按十進(jìn)制 其中方括號中的第一個元素為段號 第二個元素為段內(nèi)地址 邏輯地址 0 65 對應(yīng)的主存地址為600 65 665 邏輯地址 1 55 因段內(nèi)地址超過段長 所以產(chǎn)生段地址越界中斷 邏輯地址 2 90 對應(yīng)的主存地址為1000 90 1090 邏輯地址 3 20 因為狀態(tài)位為0 即該段在輔存中 所以產(chǎn)生缺段中斷 考慮一個由8個頁面 每頁1K字節(jié)組成的邏輯空間 把它映射到由32個物理塊組成的存儲器 問 1 有效的邏輯地址有多少位 2 有效的物理地址有多少位 解此題的關(guān)鍵是要知道在分頁管理中 頁 和 塊 是一樣大小的 這樣才知道物理存儲器是32K 1 邏輯地址有13位 2 物理地址有15位 考慮一個分頁存儲器 其頁表存放在內(nèi)存 1 若內(nèi)存的存取周期為0 6us 則CPU從內(nèi)存取一條指令 或一個操作數(shù) 需多少時間 2 若使用快表且快表的命中率為75 則內(nèi)存的平均存取周期為多少 1 因為頁表放在內(nèi)存 故取一條指令 或一個操作數(shù) 須訪問兩次內(nèi)存 所以需0 6us 2 1 2us的時間 2 這里假定訪問快表的時間可以忽略不計 命中快表時取數(shù)只要一次訪存 故此時的平均存取周期為0 6us 0 75 1 2us 1 0 75 0 75us關(guān)鍵 要知道訪問快表的時間可以忽略不計和平均存取周期的概念 有一計算機(jī)系統(tǒng) 內(nèi)存容量為512K 輔存容量為2G 邏輯地址形式為 段號29 20bit段內(nèi)地址19 0bit求其虛擬存儲器的實際容量 虛擬內(nèi)存的實際大小由系統(tǒng)的邏輯地址結(jié)構(gòu) 主存輔存容量共同決定 虛擬內(nèi)存容量的理論值是210 220 1G 最大段內(nèi)地址為220 1M 遠(yuǎn)大于內(nèi)存容量 其段長超過512K的內(nèi)存容量 故最大實際段長為512k而不是1M 所以可計算虛擬存儲容量為210 512K 210 0 5M 0 5G 0 5G 2G 因此虛擬存儲器的實際容量是0 5G 有一計算機(jī)系統(tǒng) 內(nèi)存容量為512K 輔存容量為2G 邏輯地址形式為 段號29 20bit段內(nèi)地址19 0bit 求其虛擬存儲器的實際容量 在分頁存儲管理系統(tǒng)中 存取一次內(nèi)存的時間是8us 查詢一次快表的時間是1us 缺頁中斷的時間是20us 假設(shè)頁表的查詢與快表的查詢同時進(jìn)行 當(dāng)查詢頁表時 如果該頁在內(nèi)存但快表中沒有頁表項 系統(tǒng)將自動把該頁頁表項送入快表 求對某一數(shù)據(jù)進(jìn)行一次存取可能需要的時間 現(xiàn)連續(xù)對同一頁面上的數(shù)據(jù)進(jìn)行4次連續(xù)讀取 求每次讀取數(shù)據(jù)可能需要的時間 當(dāng)系統(tǒng)對數(shù)據(jù)進(jìn)行存取時 有3種可能性 1 所存取的數(shù)據(jù)的頁面在內(nèi)存 其頁表項已經(jīng)存儲到快表 此時存取數(shù)據(jù)的時間是 查詢快表的時間 存取內(nèi)存數(shù)據(jù)的時間 1us 8us 9us2 所存取的數(shù)據(jù)的頁面在內(nèi)存 但是其頁表項沒有存儲到快表 沒有命中快表 此時存取數(shù)據(jù)的時間是 查詢頁表的時間 存取內(nèi)存數(shù)據(jù)的時間 8us 8us 16us3 所存取的數(shù)據(jù)的頁面不在內(nèi)存 發(fā)生缺頁中斷 此時存取數(shù)據(jù)的時間是 查詢頁表的時間 缺頁中斷的時間 查詢頁表的時間 存取內(nèi)存數(shù)據(jù)的時間 8us 20us 8us 8us 44us 當(dāng)對某一數(shù)據(jù)進(jìn)行4次連續(xù)讀取時 第1次可能的時間為 1us 8us 9us 8us 8us 16us 8us 20us 8us 8us 44us 第2次時 對應(yīng)頁面的頁表項已經(jīng)交換到快表中 因為存取是連續(xù)的 不存在頁面被淘汰的可能性 所以第2次 第3次 第4次的存取時間是一樣的 消耗的時間為1us 8us 9us 某虛擬存儲器的用戶空間共有32個頁面 每頁1KB 主存16KB 試問 1 邏輯地址的有效位是多少 2 物理地址需要多少位 3 假定某時刻系統(tǒng)用戶的第0 1 2 3頁分別分配的物理塊號為5 10 4 7 試將虛地址0A5C和093C變換為物理地址 1 程序空間的大小為32KB 因此邏輯地址的有效位數(shù)是15位 2 內(nèi)存儲空間的大小是16KB 因此物理地址至少需要14位 3 當(dāng)頁面為1KB時 虛地址0A5C表示頁號為00010 頁內(nèi)地址是1001011100 該頁在內(nèi)存的第4塊 即塊號為0100 因此0A5C的物理地址是01001001011100 即125CH 4 用同樣的方法可以求得 093C的物理地址是113CH 考慮一個有快表的請求分頁系統(tǒng) 設(shè)內(nèi)存的讀寫周期為1us 內(nèi)外存之間傳送一個頁面的平均時間為5ms 快表的命中率為80 頁面失效率為10 求內(nèi)存的有效存取時間 內(nèi)存的有效存取時間EAT EfficentAccessTime 也叫平均存取時間AAT AverageAccessTime 其計算公式如下 EAT 命中快表時的存取時間 快表命中率 命中內(nèi)存時的存取時間 內(nèi)存命中率 頁面失效時的存取時間 頁面失效率將題中的已知條件代入可得EAT 1us 80 2us 10 5000us 2us 10 0 8us 0 2us 500 2us 501 2us說明 解此題除了要了解 有效存取時間 的計算公式外 還應(yīng)了解在命中快表 命中內(nèi)存和頁面失效三種情況下存取時間的計算方法 特別是 當(dāng)頁面失效時 除了頁面?zhèn)魉蜁r間 還應(yīng)加上2次訪問內(nèi)存的時間 因為頁面失效的前提是不命中快表 對于一個使用快表的頁式虛存 設(shè)快表的命中率為70 內(nèi)存的存取周期為1us 缺頁處理時 若內(nèi)存有可用空間或被置換的頁面在內(nèi)存未被修改過 則處理一個缺頁中斷需8ms 否則需20ms 假定被置換的頁面60 是屬于后一種情況 則為了保證有效存取時間不超過2us 問可接受的最大缺頁率是多少 設(shè)可接受的最大缺頁率為p 則有1us 0 7 2us 1 0 7 p 0 4 8ms 0 6 20ms p 2us即0 7 0 6 2p 3200p 1200p 215198p 0 7p 0 000046 在某分頁虛存系統(tǒng)中 測得CPU和磁盤的利用率如下 試指出每種情況下的問題和措施 1 CPU的利用率為15 盤利用率為95 2 CPU的利用率為88 盤利用率為3 3 CPU的利用率為13 盤利用率為5 1 可能已出現(xiàn)了抖動現(xiàn)象 應(yīng)減少系統(tǒng)的進(jìn)程數(shù) 2 系統(tǒng)比較正常 可考慮適當(dāng)增加進(jìn)程數(shù)以提高資源利用率 3 CPU和磁盤的利用率都較低 必須增加并發(fā)進(jìn)程數(shù) 在分頁存儲管理系統(tǒng)中 存取一次內(nèi)存的時間是8us 查詢一次快表的時間是1us 缺頁中斷的時間是20us 假設(shè)頁表的查詢與快表的查詢同時進(jìn)行 當(dāng)查詢頁表時 如果該頁在內(nèi)存但快表中沒有頁表項 系統(tǒng)將自動把該頁頁表項送入快表 一個作業(yè)最多可保留3個頁面在內(nèi)存 現(xiàn)開始執(zhí)行一作業(yè) 系統(tǒng)連續(xù)對作業(yè)的 5 7 6 4 2各頁面的數(shù)據(jù)進(jìn)行1次存取 如分別采用FIFO算法和最優(yōu)頁面置換算法 求每種算法下存取這些數(shù)據(jù)需要的總時間 LRU第2頁面 20 8 3第4頁面 20 8 3第5頁面 20 8 3第2頁面 8 1第7頁面 20 8 3第6頁面 20 8 3第4頁面 20 8 3第8頁面 20 8 3因此總的時間是 20 8 3 7 8 1 OPT第2頁面 20 8 3第4頁面 20 8 3第5頁面 20 8 3第2頁面 8 1第7頁面 20 8 3第6頁面 20 8 3第4頁面 8 1第8頁面 8 1因此總的時間是 20 8 3 5 8 1 3 為什么要引入邏輯地址 1 使用物理地址的程序只有裝入程序所規(guī)定的內(nèi)存空間上才能正確執(zhí)行 如果程序所規(guī)定內(nèi)存空間不空閑或不存在 程序都無法執(zhí)行 2 使用物理地址編程意味著由程序員分配內(nèi)存空間 程序員無法事先協(xié)商每個程序所應(yīng)占的內(nèi)存空間的位置 這在多道程序系統(tǒng)中 勢必造成程序所占內(nèi)存空間的相互沖突 3 在多道程序系統(tǒng)中 系統(tǒng)無法保證程序執(zhí)行時 它所需的內(nèi)存空間都空閑 基于上述原因 必須引入一個統(tǒng)一的 在編程時使用的地址 它能夠在程序執(zhí)行時根據(jù)所分配的內(nèi)存空間將其轉(zhuǎn)換為對應(yīng)的物理地址 這個地址就是邏輯地址 邏輯地址的引入為內(nèi)存的共享 保護(hù)和擴(kuò)充提供方便 試比較靜態(tài)重定位和動態(tài)重定位 重定位 實際上指的是相互聯(lián)系的兩件事情 一是確定一個待執(zhí)行程序在內(nèi)存中的位置 二是將程序中的邏輯地址轉(zhuǎn)換成物理地址 后一件事情是由前一件事情決定的 試比較靜態(tài)重定位和動態(tài)重定位 靜態(tài)重定位的特點實現(xiàn)容易 無需增加硬件地址變換機(jī)構(gòu) 一般要求為每個程序分配一個連續(xù)的存儲區(qū) 在重定位過程中 裝入內(nèi)存的代碼發(fā)生了改變 在程序執(zhí)行期間不再發(fā)生地址的變換 在程序執(zhí)行期間不能移動 且難以做到程序和數(shù)據(jù)的共享 其內(nèi)存利用率低 動態(tài)重定位特點 實現(xiàn)要依靠硬件地址變換機(jī)構(gòu) 且存儲管理軟件算法較復(fù)雜 程序代碼是按原樣裝入內(nèi)存的 在重定位的過程中也不發(fā)生變化 重定位產(chǎn)生的物理地址存放在內(nèi)存地址寄存器中 同一代碼中的同一邏輯地址 每執(zhí)行一次都要重定位一次 只要改變基地址 就可以很容易地實現(xiàn)代碼在內(nèi)存中的移動 動態(tài)重定位可以將程序分配到不連續(xù)的存儲區(qū)中 所以 盡管動態(tài)重定位需要硬件支持 但支持程序浮動 便于利用零散的內(nèi)存空間 利于實現(xiàn)信息共享和虛擬存儲 所以現(xiàn)代計算機(jī)大都采用動態(tài)重定位 另外 實現(xiàn)虛擬存儲器需要動態(tài)重定位技術(shù)的支持 在實存管理上 管理方法主要分成哪兩種類型 實存管理的方法主要分成 1 連續(xù) 用戶程序需要占用連續(xù)的內(nèi)存空間 如分區(qū)存儲管理 2 離散 用戶程序不需要占用連續(xù)的內(nèi)存空間 如分頁 分段 段頁等管理 一個用戶程序在內(nèi)存可能是不連續(xù)的 如果它有不只一頁或一段的話 為什么在分頁和分段管理下取一條指令或一個操作數(shù)通常需兩次訪存 如何解決這一問題 因為用于地址變換的頁表或段表也是存放在內(nèi)存的 為了將CPU給出的邏輯地址變成物理地址 首先就要訪問內(nèi)存的頁表和段表 然后 根據(jù)形成的物理地址再取指令或數(shù)據(jù) 這就要兩次訪存 解決這一問題的辦法是提供一個稱之為 快表 的硬件 用以存放當(dāng)前運行進(jìn)程的頁表或段表的部分內(nèi)容 快表 的訪問時間很快 因此可以節(jié)約訪問頁表和段表的時間 存儲器訪問具有時間和空間的 局部性 因此快表的命中率一般可達(dá)70 到90 頁表和段表是在系統(tǒng)執(zhí)行過程中 每時每刻都需要訪問的 因此 訪問時間的微小縮短 其累計節(jié)約的時間卻可以達(dá)到很大 段頁式存儲系統(tǒng)中 為了獲得一條指令或數(shù)據(jù) 需幾次訪問內(nèi)存 在段頁式系統(tǒng)中 為了獲得一條指令或數(shù)據(jù) 需三次訪問內(nèi)存 第一次訪問 是訪問內(nèi)存中的段表 從中取得頁表始址 第二次訪問 是訪問內(nèi)存中的頁表 從中取出邏輯頁面對應(yīng)的內(nèi)存物理塊號 并將該塊號與頁內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址 第三次訪問 才是真正從第二次訪問所得的地址中 取出指令或數(shù)據(jù) 為什么分段管理下的程序共享和保護(hù)比分頁管理更有意義 因為段是一個有意義的邏輯整體 如主程序 子程序 數(shù)據(jù)表格 工作空間等 就如書本上的一章或一個自然段 而頁只是一個物理尺寸 不一定有完整的意義 如書本上的一頁 程序共享當(dāng)然希望被共享的對象是一個有意義的整體 如一個子程序 至于程序保護(hù) 指的是每個進(jìn)程都應(yīng)按所擁有的存取權(quán)訪問不同的程序 而存取權(quán) R W E等 當(dāng)然對一個有完整意義的對象才更有意義 所以就共享和保護(hù)而言 分段管理比分頁管理更有意義 說明什么是置換算法的異常現(xiàn)象 解頁面置換算法的異?，F(xiàn)象 也叫Belady異常 是在局部置換前提下的一種現(xiàn)象 所謂局部置換 指的是當(dāng)一進(jìn)程創(chuàng)建時 分給其一定數(shù)量的頁面 例如8頁 然后 在運行過程中 若該進(jìn)程需調(diào)入新頁且須置換一個頁面時 則只能置換其自己的一個頁面而不能置換別的進(jìn)程的頁面 頁面置換的異?，F(xiàn)象 是指在一定置換算法和一定頁面走向下 分給進(jìn)程的頁面數(shù)增多其頁面失效率反而增加這樣一種情況 這種異常 只在一定的算法和一定的頁面走向下才會出現(xiàn) 許多算法 如OPT和LRU 在任何情況下都不會有異?，F(xiàn)象 LRU之所以不會有 異常 是因為最近的過去使用的n個頁面一定在最近的過去使用的n 1個頁面之中 什么是抖動現(xiàn)象 如何消除這種現(xiàn)象 抖動現(xiàn)象 是在虛存管理下 用于頁面 在內(nèi) 外存之間 對換的時間比程序的有效運行時間還要多的這樣一種現(xiàn)象 它可以是一進(jìn)程內(nèi)部的局部性抖動 也可以是整個系統(tǒng)的全局性抖動 造成這種情況固然與置換算法和頁面走向有關(guān) 但其根本原因是多道系統(tǒng)內(nèi)的進(jìn)程數(shù)太多 從而分給每個進(jìn)程的頁面數(shù)太少 因此 解決這一問題的最有效的辦法是減少系統(tǒng)內(nèi)的進(jìn)程數(shù) Denning于1980年提出了 L S準(zhǔn)則 即調(diào)整系統(tǒng)內(nèi)的進(jìn)程數(shù) 使得產(chǎn)生缺頁的平均間隔時間 L 等于系統(tǒng)處理進(jìn)程缺頁的平均時間 S 理論和實踐表明 此時的CPU利用率最高 在內(nèi)存管理中 內(nèi)零頭 和 外零頭 各指的是什么 在固定式分區(qū)分配 可變式分區(qū)分配 頁式虛擬存儲系統(tǒng) 段式虛擬存儲系統(tǒng)中 各會存在何種零頭 為什么 內(nèi)零頭 又稱內(nèi)部碎片 給一個作業(yè)分配的存儲塊長度為n 在其中存儲的作業(yè)長度為m 則剩下的長度為 n m 的空間 成為該存儲塊的內(nèi)部碎片 若存儲塊長度為n 在該系統(tǒng)所采用的調(diào)度算法下 較長時間內(nèi)無法選出一道長度不超過該塊的作業(yè) 則稱該塊為外零頭 外部碎片 在固定式分區(qū)分配中兩種零頭均會存在 因為空間劃分是固定的 無論作業(yè)長短 存儲單元均不會隨之變化 若作業(yè)短而存儲塊長則產(chǎn)生內(nèi)零頭 若作業(yè)長而存儲塊短則產(chǎn)生外零頭 在可變式分區(qū)分配中只有外零頭而無內(nèi)零頭 因為空間劃分是依作業(yè)長度進(jìn)行的 是要多少給多少 但剩下的部分太短而無法再分 則稱為外零頭 頁式虛存中會存在內(nèi)零頭而無外零頭 因存儲空間與作業(yè)均分為等長單元 所以不存在無法分配的單元 但作業(yè)長度并不剛好為頁面大小的整數(shù)倍 因此在最后一頁會有剩余空間 即為內(nèi)零頭 段式虛存中會存在外零頭而無內(nèi)零頭 因段式的空間劃分類似于可變分區(qū)分配 根據(jù)段長分配 要多少給多少 但會剩余小空間無法分配 則為外零頭 覆蓋技術(shù)的基