操作系統(tǒng)第四章復(fù)習(xí)

1、v 靜態(tài)鏈接靜態(tài)鏈接v 動態(tài)鏈接動態(tài)鏈接 裝入時動態(tài)鏈接裝入時動態(tài)鏈接 運(yùn)行時動態(tài)鏈接運(yùn)行時動態(tài)鏈接v 絕對裝入絕對裝入v 可重定位裝入可重定位裝入v 動態(tài)重定位裝入動態(tài)重定位裝入 FF,CFF,BF,WF 各種算法是如何來進(jìn)行內(nèi)存的分配和回收的？各種算法是如何來進(jìn)行內(nèi)存的分配和回收的？ 緊湊或拼接緊湊或拼接 掌握分頁系統(tǒng)邏輯地址的結(jié)構(gòu)，為了進(jìn)行邏輯地址到物理地址的掌握分頁系統(tǒng)邏輯地址的結(jié)構(gòu)，為了進(jìn)行邏輯地址到物理地址的轉(zhuǎn)換，分頁系統(tǒng)必須為每個作業(yè)配置什么樣的數(shù)據(jù)結(jié)構(gòu)并提供哪些硬轉(zhuǎn)換，分頁系統(tǒng)必須為每個作業(yè)配置什么樣的數(shù)據(jù)結(jié)構(gòu)并提供哪些硬件支持？如何實(shí)現(xiàn)地址轉(zhuǎn)換？為什么引進(jìn)快表可以加快分頁系統(tǒng)

2、存取件支持？如何實(shí)現(xiàn)地址轉(zhuǎn)換？為什么引進(jìn)快表可以加快分頁系統(tǒng)存取指令和數(shù)據(jù)的速度。指令和數(shù)據(jù)的速度。 了解由分頁發(fā)展為分段，并近一步發(fā)展為段頁式存儲管理方式的了解由分頁發(fā)展為分段，并近一步發(fā)展為段頁式存儲管理方式的主要推動力是什么？分段和段頁式系統(tǒng)是如何管理作業(yè)的地址空間和主要推動力是什么？分段和段頁式系統(tǒng)是如何管理作業(yè)的地址空間和內(nèi)存空間的？它們的地址變換是如何完成的？并應(yīng)注意對分段系統(tǒng)和內(nèi)存空間的？它們的地址變換是如何完成的？并應(yīng)注意對分段系統(tǒng)和分頁系統(tǒng)的比較。為什么分段比分頁更容易保護(hù)和共享。分頁系統(tǒng)的比較。為什么分段比分頁更容易保護(hù)和共享。v 常規(guī)存儲管理方式的特征（一次性和駐留性）常

3、規(guī)存儲管理方式的特征（一次性和駐留性）v 局部性原理局部性原理了解每種特征的具體含義，以及它們相互之間存在的關(guān)系？了解每種特征的具體含義，以及它們相互之間存在的關(guān)系？和和，這些技術(shù)的實(shí)現(xiàn)需要，這些技術(shù)的實(shí)現(xiàn)需要得到哪些硬件和軟件支持。得到哪些硬件和軟件支持。 （一定容量的內(nèi)存和較大容量的外存、（一定容量的內(nèi)存和較大容量的外存、頁（段）表、缺頁（段）中斷機(jī)構(gòu)和地址變換機(jī)構(gòu)）頁（段）表、缺頁（段）中斷機(jī)構(gòu)和地址變換機(jī)構(gòu)） （1）頁表機(jī)制）頁表機(jī)制 （2）地址變換機(jī)構(gòu)和過程）地址變換機(jī)構(gòu)和過程 （3）頁面分配和置換策略）頁面分配和置換策略v 固定分配局部置換固定分配局部置換v可變分配全局置換可變分配

4、全局置換v可變分配局部置換可變分配局部置換 （4）頁面置換算法（）頁面置換算法（，計(jì)算，計(jì)算）vOPT置換算法置換算法vFIFO置換算法置換算法vLRU置換算法及其近似算法置換算法及其近似算法Clock算法算法 和缺頁率有關(guān)的因素有哪些？和缺頁率有關(guān)的因素有哪些？發(fā)生抖動的現(xiàn)象是什么？產(chǎn)生抖動的原因有發(fā)生抖動的現(xiàn)象是什么？產(chǎn)生抖動的原因有哪些？消除抖動的方法？哪些？消除抖動的方法？1. 什么情況下需要進(jìn)行重定位？為什么要引入動態(tài)重定位？什么情況下需要進(jìn)行重定位？為什么要引入動態(tài)重定位？2. 2. 考慮一個由考慮一個由256256個頁面、每頁由個頁面、每頁由40964096字節(jié)組成的邏輯空間，字

5、節(jié)組成的邏輯空間，把它裝入到有把它裝入到有3232個物理塊的存儲器中，問：個物理塊的存儲器中，問： （1 1）邏輯地址需要多少位二進(jìn)制來表示？）邏輯地址需要多少位二進(jìn)制來表示？ （2 2）物理地址需要多少位二進(jìn)制來表示？）物理地址需要多少位二進(jìn)制來表示？3. 對一個將頁表存放在內(nèi)存中的分頁系統(tǒng)：對一個將頁表存放在內(nèi)存中的分頁系統(tǒng)： 1）如果內(nèi)存需要）如果內(nèi)存需要0.2us，有效訪問時間為多少？，有效訪問時間為多少？ 2）如果加一快表，且假定在快表中找到頁表項(xiàng)的幾率高達(dá)）如果加一快表，且假定在快表中找到頁表項(xiàng)的幾率高達(dá)90，則有效訪問時間又是多少（假定查快表需花的時間為，則有效訪問時間又是多少（

6、假定查快表需花的時間為0）？）？4.4. 在虛擬內(nèi)存管理中，地址變換機(jī)構(gòu)將邏輯地址轉(zhuǎn)換為物理在虛擬內(nèi)存管理中，地址變換機(jī)構(gòu)將邏輯地址轉(zhuǎn)換為物理地址，形成該邏輯地址的階段是（地址，形成該邏輯地址的階段是（ ）。）。 5. 采用段式存儲管理的系統(tǒng)中，若地址用采用段式存儲管理的系統(tǒng)中，若地址用24位表示，其中位表示，其中8位位表示段號，則允許每段的最大長度是表示段號，則允許每段的最大長度是_ 6. 作業(yè)在執(zhí)行中發(fā)生了缺頁中斷，經(jīng)操作系統(tǒng)處理后，應(yīng)讓其作業(yè)在執(zhí)行中發(fā)生了缺頁中斷，經(jīng)操作系統(tǒng)處理后，應(yīng)讓其執(zhí)行執(zhí)行_指令。指令。 7、某基于動態(tài)分區(qū)存儲管理的計(jì)算機(jī)，其主存容量為、某基于動態(tài)分區(qū)存儲管理的計(jì)

7、算機(jī)，其主存容量為55MB（初始為空），采用最佳適配（初始為空），采用最佳適配（Best fit）算法，分配和釋放的）算法，分配和釋放的順序?yàn)椋悍峙漤樞驗(yàn)椋悍峙?5MB，分配，分配30MB，釋放，釋放15MB，分配，分配6MB，此，此時主存中最大空閑分區(qū)的大小是（時主存中最大空閑分區(qū)的大小是（ ）頁目編號頁目編號頁號頁號頁內(nèi)偏移量頁內(nèi)偏移量邏輯地址空間大小為邏輯地址空間大小為216頁，則表示整個邏輯地址空間的頁頁，則表示整個邏輯地址空間的頁目錄表中包含表項(xiàng)的個數(shù)至少是（目錄表中包含表項(xiàng)的個數(shù)至少是（ ）DB 8、某計(jì)算機(jī)采用二級頁表的分頁存儲管理方式，按字節(jié)編、某計(jì)算機(jī)采用二級頁表的分頁存儲管

8、理方式，按字節(jié)編址，頁大小為址，頁大小為210字節(jié)，頁表項(xiàng)大小為字節(jié)，頁表項(xiàng)大小為2字節(jié)，邏輯地址結(jié)構(gòu)為字節(jié)，邏輯地址結(jié)構(gòu)為9、當(dāng)系統(tǒng)發(fā)生抖動時，可以采取的有效措施是、當(dāng)系統(tǒng)發(fā)生抖動時，可以采取的有效措施是 （ ）、撤銷部分進(jìn)程、撤銷部分進(jìn)程 、增加磁盤交換區(qū)的容量、增加磁盤交換區(qū)的容量 、提高用戶進(jìn)程優(yōu)先級、提高用戶進(jìn)程優(yōu)先級A11、某虛擬存儲器的用戶編程空間共、某虛擬存儲器的用戶編程空間共32個頁個頁面，每頁面，每頁1KB，主存，主存16KB。某戶作業(yè)為某戶作業(yè)為6頁，頁，假定某時刻該作業(yè)頁表如圖。假定某時刻該作業(yè)頁表如圖。試將虛擬地址試將虛擬地址0A5CH、103CH、1A5CH轉(zhuǎn)換為物

9、理地址。轉(zhuǎn)換為物理地址。相應(yīng)的物理地址是否合法？是否產(chǎn)生缺頁？相應(yīng)的物理地址是否合法？是否產(chǎn)生缺頁？ 頁號頁號存儲塊號存儲塊號01235104710、 在缺頁處理過程中，操作系統(tǒng)執(zhí)行的操作可能是（在缺頁處理過程中，操作系統(tǒng)執(zhí)行的操作可能是（ ） 、修改頁表、修改頁表 、磁盤、磁盤I/O 、分配頁框、分配頁框D12、某系統(tǒng)的空閑分區(qū)表如下，系統(tǒng)采用可變分區(qū)存儲管理、某系統(tǒng)的空閑分區(qū)表如下，系統(tǒng)采用可變分區(qū)存儲管理模式，現(xiàn)有一個程序序列：模式，現(xiàn)有一個程序序列：96K、20K、200K。若用首次適。若用首次適應(yīng)算法和最佳適應(yīng)算法來為這些程序分配內(nèi)存，試問哪一種應(yīng)算法和最佳適應(yīng)算法來為這些程序分配內(nèi)

10、存，試問哪一種算法可以滿足所有程序的請求，為什么？算法可以滿足所有程序的請求，為什么？分區(qū)號大小起始地址132K100K210K150K35K200K4218K220K596K530K13、解決大作業(yè)和小內(nèi)存的矛盾有哪些途徑？簡述其實(shí)現(xiàn)思、解決大作業(yè)和小內(nèi)存的矛盾有哪些途徑？簡述其實(shí)現(xiàn)思想。想。14、某段式存儲管理采用如下段表。試計(jì)算（、某段式存儲管理采用如下段表。試計(jì)算（0，430）、）、（3，200）、（）、（1，34）、（）、（2，2500）的主存地址。當(dāng)無）的主存地址。當(dāng)無法進(jìn)行地址變換時，應(yīng)說明產(chǎn)生何種中斷。法進(jìn)行地址變換時，應(yīng)說明產(chǎn)生何種中斷。段號段號段長段長主存起始地址主存起始地

11、址是否在主存是否在主存06002100是是1402800是是23000否否3804000是是15、一個、一個32位地址的計(jì)算機(jī)使用兩級頁表，虛地址被分成位地址的計(jì)算機(jī)使用兩級頁表，虛地址被分成9位位頂級頁表域；頂級頁表域；11位的二級頁表域，其余位為頁內(nèi)偏移，請問：位的二級頁表域，其余位為頁內(nèi)偏移，請問： 1) 頁面長度是多少？頁面長度是多少？ 2) 在邏輯地址空間中，共存在多少頁？在邏輯地址空間中，共存在多少頁？頁面長度為頁面長度為2124K頁數(shù)頁數(shù)22016.請求分頁管理系統(tǒng)中，某頁表如圖請求分頁管理系統(tǒng)中，某頁表如圖 ：l 頁面大小為頁面大小為4KB，l 一次內(nèi)存的訪問時間是一次內(nèi)存的訪

12、問時間是100ns，l 一次快表（一次快表（TLB）的訪問時間是）的訪問時間是10ns，l 處理一次缺頁的平均時間為處理一次缺頁的平均時間為108ns（已含更新（已含更新TLB和頁表的時間），和頁表的時間），l 進(jìn)程的駐留集大小固定為進(jìn)程的駐留集大小固定為2，l 采用采用LRU算法和局部淘汰策略。算法和局部淘汰策略。假設(shè)假設(shè): TLB初始為空；初始為空； 忽略訪問頁表之后的忽略訪問頁表之后的TLB更新時間；更新時間； 有效位為有效位為0表示頁面不在內(nèi)存，缺頁中斷處理后，返回到產(chǎn)生缺表示頁面不在內(nèi)存，缺頁中斷處理后，返回到產(chǎn)生缺頁中斷的指令處重新執(zhí)行。頁中斷的指令處重新執(zhí)行。 設(shè)有虛地址訪問序列

13、設(shè)有虛地址訪問序列2362H、1565H、25A5H，請問：，請問： （1） 依次訪問上述三個虛地址，各需多少時間？給出計(jì)算過程。依次訪問上述三個虛地址，各需多少時間？給出計(jì)算過程。 （2） 基于上述訪問序列，虛地址基于上述訪問序列，虛地址1565H的的 物理地址是多少？物理地址是多少？ 頁號頁框號有效位0101H11-02254H1解答：解答：頁面頁面4KB，12位，即位，即16進(jìn)制的進(jìn)制的3位，則位，則2362H的最高位就是頁號。的最高位就是頁號。（1）2362H：P=2，訪問快表，訪問快表10ns，因初始為空，因此需訪問頁表，因初始為空，因此需訪問頁表100ns得到頁框號，合成物理地址后

14、訪問主存得到頁框號，合成物理地址后訪問主存100ns，共計(jì)：，共計(jì)： 10ns+100ns+100ns=210ns。 1565H：P=1，訪問快表，訪問快表10ns，落空，訪問頁表，落空，訪問頁表100ns，沒在主存，缺頁，沒在主存，缺頁中斷處理中斷處理108ns（已含更新（已含更新TLB和頁表的時間），合成物理地址后訪問主和頁表的時間），合成物理地址后訪問主存存100ns。10ns+100ns+108ns+100ns318ns。 25A5H：P=2，訪問快表，因第一次訪問已將該頁號放入快表，因此花，訪問快表，因第一次訪問已將該頁號放入快表，因此花費(fèi)費(fèi)10ns便可合成物理地址，訪問主存便可合成

15、物理地址，訪問主存100ns，共計(jì)：，共計(jì)： 10ns+100ns=110ns。（2）當(dāng)訪問虛地址）當(dāng)訪問虛地址1565H時，產(chǎn)生缺頁中斷，合法駐留集為時，產(chǎn)生缺頁中斷，合法駐留集為2，必須從，必須從頁表中淘汰一個頁面，根據(jù)題目的置換算法，應(yīng)淘汰頁表中淘汰一個頁面，根據(jù)題目的置換算法，應(yīng)淘汰0號頁面，因此號頁面，因此1565H的對應(yīng)頁框號為的對應(yīng)頁框號為101H。由此可得。由此可得1565H的物理地址為的物理地址為101565H。 17、設(shè)某計(jì)算機(jī)的邏輯地址空間和物理地址空間均為、設(shè)某計(jì)算機(jī)的邏輯地址空間和物理地址空間均為64KB，按字節(jié)編址。若某進(jìn)程最多需要按字節(jié)編址。若某進(jìn)程最多需要6頁（

16、頁（Page）存儲空間，頁的大小為）存儲空間，頁的大小為1KB。操作系統(tǒng)采用固定分配局部置換策略為此進(jìn)程分配操作系統(tǒng)采用固定分配局部置換策略為此進(jìn)程分配4個頁框。個頁框。頁號頁號頁框號頁框號裝入時刻裝入時刻訪問位訪問位071301142301222001391601當(dāng)該進(jìn)程執(zhí)行到時刻當(dāng)該進(jìn)程執(zhí)行到時刻260時，要訪問邏輯地址為時，要訪問邏輯地址為17CAH的數(shù)據(jù)，請問答的數(shù)據(jù)，請問答下列問題：下列問題：（1）該邏輯地址對應(yīng)的頁號是多少？）該邏輯地址對應(yīng)的頁號是多少？（2）若采用先進(jìn)先出置換算法，該邏輯地址對應(yīng)的物理地址是多少？）若采用先進(jìn)先出置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計(jì)

17、算過程。要求給出計(jì)算過程。（3）若采用時鐘置換算法，該邏輯地址對應(yīng)的物理地址是多少？（設(shè)）若采用時鐘置換算法，該邏輯地址對應(yīng)的物理地址是多少？（設(shè)搜索下一頁的指針沿順時針方向移動，且當(dāng)前指向搜索下一頁的指針沿順時針方向移動，且當(dāng)前指向2號頁框）號頁框）解答：解答： 17CAH=(0001 0111 1100 1010)2（1）頁大小為）頁大小為1K，所以頁內(nèi)偏移地址為，所以頁內(nèi)偏移地址為10位，于是前位，于是前6位是頁號，所以第一問的解為：位是頁號，所以第一問的解為：5（2）FIFO，則被置換的頁面所在頁框?yàn)?，則被置換的頁面所在頁框?yàn)?，所以對應(yīng)，所以對應(yīng)的物理地址為（的物理地址為（0001

18、1111 1100 1010）2 1FCAH（3）CLOCK，則被置換的頁面所在頁框?yàn)椋瑒t被置換的頁面所在頁框?yàn)?，所以對，所以對應(yīng)的物理地址為（應(yīng)的物理地址為（0000 1011 1100 1010）2 0BCAH18. 關(guān)于請求分頁系統(tǒng)的頁面置換策略如下：關(guān)于請求分頁系統(tǒng)的頁面置換策略如下：v 系統(tǒng)從系統(tǒng)從0時刻開始掃描，每隔時刻開始掃描，每隔5個時間單位掃描一輪駐留集（掃描時個時間單位掃描一輪駐留集（掃描時間忽略不計(jì)），本輪沒被訪問過的頁框?qū)⒈幌到y(tǒng)收回，并放入到空間忽略不計(jì)），本輪沒被訪問過的頁框?qū)⒈幌到y(tǒng)收回，并放入到空閑頁框鏈尾，其中內(nèi)容在下一次被分配之前不被清空。閑頁框鏈尾，其中內(nèi)容在下一次被分配之前不被清空。v 當(dāng)發(fā)生缺頁時，如果該頁曾被使用過且還在空閑頁鏈表中，則將其當(dāng)發(fā)生缺頁時，如果該頁曾被使用過且還在空閑頁鏈表中，則將其重新放回進(jìn)程的駐留集中；否則，從空閑頁框鏈表頭部取出一個頁重新放回進(jìn)程的駐留集中；否則，從空閑頁框鏈表頭部取出一個頁框。框。v 忽略其他進(jìn)程的影響和系統(tǒng)開銷。初始時進(jìn)程駐留集為空。忽略其他進(jìn)程的影響和系統(tǒng)開銷。初始時進(jìn)程駐留集為空。v 目前系統(tǒng)空閑頁的頁框號依次為：目前系統(tǒng)空閑頁的頁框號依次為：32、15、21、41，進(jìn)程，進(jìn)程P依次依次訪問的訪問的為為、。 請回