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

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