操作系統(tǒng)第五章課件

練習題:某程序在邏輯地址100處有一條取數(shù)指令LOAD1，500，而500單元內(nèi)存放數(shù)據(jù)51888。假設程序被分配到內(nèi)存起始地址5000單元時，試用圖示意，采用下述各種方式下的該指令及數(shù)據(jù)地址的物理地址及相應地址的變換過程。（1）靜態(tài)重定位（2）采用重定位寄存器實現(xiàn)動態(tài)重定位（3）采用頁表映象方式，假定頁面大小為100單元，其頁表各頁映射到50，51，52，53，54，55，…,59物理頁上。練習題:13.解（1）如圖0…100LOAD1,500…50051888…地址空間…5000…5100Load1,5500…5500518885999…內(nèi)存說明：靜態(tài)重定位是在該程序裝入內(nèi)存時,由裝入程序進行地址重定位，因此，程序指令中的地址在裝入過程中加以修改，以適應程序裝在與原地址空間不一致的物理空間。3.解（1）如圖0…100LOAD1,500…50051882（2）如圖0…100LOAD1,500…50051888999…地址空間……51888……內(nèi)存5000+5005500（2）如圖0…100LOAD1,500…50051888993（3）如圖所示……51888……內(nèi)存頁表首址頁表長550050151252353454555656757858959+邏輯地址：500500頁號頁內(nèi)位移55×100+0=5500頁面大小為100單元（3）如圖所示……51888……內(nèi)存頁表首址頁表長5500545.5.1.3請求分頁存儲管理頁式管理是將程序全部裝入內(nèi)存；請求分頁存儲管理是可以將程序按照頁全部鏈接后，部分裝入內(nèi)存，頁表將進行擴充；余下的部分如何安排呢？余下的部分是以文件的形式存入作為輔存的磁盤上。通過中斷采用置換算法，將其調(diào)入。當調(diào)入時需要建立一個輔助頁表5.5.1.3請求分頁存儲管理頁式管理是將程序全部裝入內(nèi)存；5練習：某計算機系統(tǒng)采用請求頁式存儲管理方法，其提供給用戶一個容量為221B的虛存，實存（內(nèi)存）容量為218B。頁面大小為210B，如果一個進程訪問一個數(shù)據(jù)，其地址為（0123456）8（八進制表示的地址），請你給出該虛擬地址對應的物理地址（實地址）。假設此數(shù)據(jù)所在的虛頁號對應的實頁面物理塊號為8頁面，要求也用八進制表示。練習：6解：頁的劃分為0123456對應的2進制為00001010011100101110實頁號為（00001000110010111019頁號P109頁內(nèi)地址W0021456該數(shù)據(jù)的實地址為（021456）8解：頁的劃分為19頁號P1097練習:設有一個采用請求分頁存儲管理的系統(tǒng)，其內(nèi)存容量為512KB，虛存容量為2048KB,頁面大小為2KB。試問（1）內(nèi)存物理地址應設多少位（2）內(nèi)存中有多少物理塊（3）最大塊號是多少（4）虛存地址應設多少位（5）地址空間最多可有多少頁（6）頁內(nèi)最大的位移量是多少（7）最小的位移是多少？練習:設有一個采用請求分頁存儲管理的系統(tǒng)，其內(nèi)存容8解：（1）19位219=512K（2）256塊512/2=256（3）255（4）21位221=2048（5）1024頁2048k/2k=1024（6）1023（7）0解：9練習:

分頁管理，頁面大小100B，下面一道程序中的邏輯地址是多少？請用頁號和頁內(nèi)位移來表示，并用二進制數(shù)。（1）從263中取數(shù)（2）寫數(shù)到264（3）寫數(shù)到265（4）寫數(shù)到901（5）從902中區(qū)數(shù)（6）Halt練習:分頁管理，頁面大小100B，下面一道10解：263=2(頁號)×100+63(位移量)63=00111111（1）（0010，00111111）。（2）（0010，01000000）。（3）（0010，01000001）。（4）（1001，00000001）。（5）（1001，00000010）。（6）無需操作數(shù)，故無需地址。解：263=2(頁號)×100+63(位移量)11一個由4個頁面（頁號為0-3）、每頁由1024個字節(jié)組成的程序，把它裝入一個由8個物理塊（塊號為0-7）組成的存儲器中，裝入情況如表1-7-3所示。己知下面的邏輯地址（其中方括號中的第一個元素為頁號，第二個元素為頁內(nèi)地址），請按頁表求出對應的物理地址。（1）[0，100]；（2）[1，179]；（3）[2，785]；（4）[3，1010]。表1-7-3邏輯頁號內(nèi)存塊號03152632一個由4個頁面（頁號為0-3）、每頁由1024個字節(jié)組成的程12解：因為每頁有1024B，所以內(nèi)存中每塊也有1024B。故內(nèi)存中每塊的起始地址為（每塊起始地址＝塊號X塊長）：0塊：00001塊：10242塊：20483塊：30724塊：40965塊：51206塊：61447塊：7168（1）的物理地址為：3072+100=3172；（2）的物理地址為：5120+179=5299；頁面首址頁表長

（3）的物理地址為：6144+785=6929；（4）的物理地址為2048+1010=3058。解：因為每頁有1024B，所以內(nèi)存中每塊也有1024B。135.5.1.4置換算法功能：需要調(diào)入頁面時，選擇內(nèi)存中哪個物理頁面被置換。稱為replacementpolicy。目標：把未來不再使用的或短期內(nèi)較少使用的頁面調(diào)出，通常只能在局部性原理指導下依據(jù)過去的統(tǒng)計數(shù)據(jù)進行預測；頁面鎖定(framelocking)：用于描述必須常駐內(nèi)存的操作系統(tǒng)的關鍵部分或時間關鍵(time-critical)的應用進程。實現(xiàn)方法為在頁表中加上鎖定標志位(lockbit)。返回5.5.1.4置換算法功能：需要調(diào)入頁面時，選擇內(nèi)存中哪個14最佳算法(OPT,optimal)最近最久未使用算法(LRU,LeastRecentlyUsed)先進先出算法(FIFO)輪轉(zhuǎn)算法(clock)最不常用算法(LFU,LeastFrequentlyUsed)頁面緩沖算法(pagebuffering)最佳算法(OPT,optimal)151.最佳算法(OPT,optimal)選擇“未來不再使用的”或“在離當前最遠位置上出現(xiàn)的”頁面被置換。這是一種理想情況，是實際執(zhí)行中無法預知的，因而不能實現(xiàn)?？捎米餍阅茉u價的依據(jù)。1.最佳算法(OPT,optimal)選擇“未來不再使用162.最近最久未使用算法

(LRU,LeastRecentlyUsed)一個特殊的棧：把被訪問的頁面移到棧頂，于是棧底的是最久未使用頁面。每個頁面設立移位寄存器：被訪問時左邊最高位置1，定期右移并且最高位補0，于是寄存器數(shù)值最小的是最久未使用頁面。選擇內(nèi)存中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳算法。但由于需要記錄頁面使用時間的先后關系，硬件開銷太大。硬件機構(gòu)如：2.最近最久未使用算法

(LRU,LeastRecen173.先進先出算法(FIFO)選擇建立最早的頁面被置換?？梢酝ㄟ^鏈表來表示各頁的建立時間先后。性能較差。較早調(diào)入的頁往往是經(jīng)常被訪問的頁，這些頁在FIFO算法下被反復調(diào)入和調(diào)出。并且有Belady現(xiàn)象。3.先進先出算法(FIFO)選擇建立最早的頁面被置換?？梢?8Belady現(xiàn)象：采用FIFO算法時，如果對一個進程未分配它所要求的全部頁面，有時就會出現(xiàn)分配的頁面數(shù)增多，缺頁率反而提高的異?，F(xiàn)象。Belady現(xiàn)象的描述：一個進程P要訪問M個頁，OS分配N個內(nèi)存頁面給進程P；對一個訪問序列S，發(fā)生缺頁次數(shù)為PE（S,N）。當N增大時，PE(S,N)時而增大，時而減小。Belady現(xiàn)象的原因：FIFO算法的置換特征與進程訪問內(nèi)存的動態(tài)特征是矛盾的，即被置換的頁面并不是進程不會訪問的。Belady現(xiàn)象：采用FIFO算法時，如果對一個進程未分配它19Belady現(xiàn)象的例子進程P有5頁程序訪問頁的順序為：1,2,3,4,1,2,5,1,2,3,4,5；如果在內(nèi)存中分配3個頁面，則缺頁情況如下：12次訪問中有缺頁9次；Belady現(xiàn)象的例子進程P有5頁程序訪問頁的順序為：1,20如果在內(nèi)存中分配4個頁面，則缺頁情況如下：12次訪問中有缺頁10次；如果在內(nèi)存中分配4個頁面，則缺頁情況如下：12次訪問中有缺頁214.輪轉(zhuǎn)算法(clock)每頁有一個使用標志位(usebit)，若該頁被訪問則置userbit=1。置換時采用一個指針，從當前指針位置開始按地址先后檢查各頁，尋找usebit=0的頁面作為被置換頁。指針經(jīng)過的userbit=1的頁都修改userbit=0，最后指針停留在被置換頁的下一個頁。也稱最近未使用算法(NRU,NotRecentlyUsed)，它是LRU(最近最久未使用算法)和FIFO的折衷。4.輪轉(zhuǎn)算法(clock)每頁有一個使用標志位(useb22準備換入準備換入23停留在下一頁停留在下一頁245.最不常用算法(LFU,LeastFrequentlyUsed)選擇到當前時間為止被訪問次數(shù)最少的頁面被置換；每頁設置訪問計數(shù)器，每當頁面被訪問時，該頁面的訪問計數(shù)器加1；發(fā)生缺頁中斷時，淘汰計數(shù)值最小的頁面，并將所有計數(shù)清零；5.最不常用算法(LFU,LeastFrequentl256.頁面緩沖算法(pagebuffering)被置換頁面的選擇和處理：用FIFO算法選擇被置換頁，把被置換的頁面放入兩個鏈表之一。如果頁面未被修改，就將其歸入到空閑頁面鏈表的末尾否則將其歸入到已修改頁面鏈表。它是對FIFO算法的發(fā)展，通過被置換頁面的緩沖，有機會找回剛被置換的頁面；6.頁面緩沖算法(pagebuffering)被置換頁面26需要調(diào)入新的物理頁面時，將新頁面內(nèi)容讀入到空閑頁面鏈表的第一項所指的頁面，然后將第一項刪除?？臻e頁面和已修改頁面，仍停留在內(nèi)存中一段時間，如果這些頁面被再次訪問，只需較小開銷，而被訪問的頁面可以返還作為進程的內(nèi)存頁。當已修改頁面達到一定數(shù)目后，再將它們一起調(diào)出到外存，然后將它們歸入空閑頁面鏈表，這樣能大大減少I/O操作的次數(shù)。需要調(diào)入新的物理頁面時，將新頁面內(nèi)容讀入到空閑頁面鏈表的第一277.置換算法舉例某程序在內(nèi)存中分配三個頁面，初始為空，頁面走向為4，3，2，1，4，3，5，4，3，2，1，5。選擇“未來不再使用的”或“在離當前最遠位置上出現(xiàn)的”頁面被置換。7.置換算法舉例某程序在內(nèi)存中分配三個頁面，初始為空，頁面28選擇內(nèi)存中最久未使用的頁面被置換選擇內(nèi)存中最久未使用的頁面被置換29操作系統(tǒng)第五章ppt課件30操作系統(tǒng)第五章ppt課件315.5.2簡單段式(simplesegmentation)頁式管理是把內(nèi)存視為一維線性空間；而段式管理是把內(nèi)存視為二維空間，與進程邏輯相一致。1.簡單段式管理的基本原理將程序的地址空間劃分為若干個段(segment)，程序加載時，分配其所需的所有段（內(nèi)存分區(qū)），這些段不必連續(xù)；物理內(nèi)存的管理采用動態(tài)分區(qū)。需要CPU的硬件支持。5.5.2簡單段式(simplesegmentation32程序通過分段(segmentation)劃分為多個模塊，如代碼段、數(shù)據(jù)段、共享段。可以分別編寫和編譯可以針對不同類型的段采取不同的保護可以按段為單位來進行共享，包括通過動態(tài)鏈接進行代碼共享優(yōu)點：沒有內(nèi)碎片，外碎片可以通過內(nèi)存緊縮來消除。便于改變進程占用空間的大小。缺點：進程全部裝入內(nèi)存。程序通過分段(segmentation)劃分為多個模塊，如代33B0SA0NY0LX0PM0K邏輯段號01234作業(yè)1的地址空間01234K

3200P1500L6000N8000S5000長度

段地址01234段號10003200500060008000PKSLN主存操作系統(tǒng)B0SA0NY0LX0PM0K邏輯段號01234作業(yè)1的地址342.簡單段式管理的數(shù)據(jù)結(jié)構(gòu)進程段表：描述組成進程地址空間的各段，可以是指向系統(tǒng)段表中表項的索引。每段有段基址(baseaddress)和段長度系統(tǒng)段表：系統(tǒng)內(nèi)所有占用段空閑段表：內(nèi)存中所有空閑段，可以結(jié)合到系統(tǒng)段表中2.簡單段式管理的數(shù)據(jù)結(jié)構(gòu)進程段表：描述組成進程地址空間的353.簡單段式管理的地址變換3.簡單段式管理的地址變換36段式地址變換舉例段式地址變換舉例375.5.3頁式管理和段式管理的比較分頁是出于系統(tǒng)管理的需要，分段是出于用戶應用的需要。一條指令或一個操作數(shù)可能會跨越兩個頁的分界處，而不會跨越兩個段的分界處。頁大小是系統(tǒng)固定的，而段大小則通常不固定。邏輯地址表示：分頁是一維的，各個模塊在鏈接時必須組織成同一個地址空間；分段是二維的，各個模塊在鏈接時可以每個段組織成一個地址空間。通常段比頁大，因而段表比頁表短，可以縮短查找時間，提高訪問速度。返回5.5.3頁式管理和段式管理的比較分頁是出于系統(tǒng)管理的需要38頁式管理與段式管理的比較頁式管理與段式管理的比較395.給出下面的段表，如表所示，已知下面的邏輯地址（第一個為段號，第二個為段內(nèi)地址），求其對應的物理地址（1）[0，430]（2）[3，400]（3）[1，10]（4）[2，2500]（5）[4，42]（6）[1，11]段號段長段首地址06002191142300210090358013274961954解：（1）的物理地址為：219+430=649（2）的物理地址為：1327+400=1727（3）的物理地址為：2300+10=2310（4）的物理地址為：90+2500=2590但是訪問第2段，段內(nèi)位移500，第二段段長為100，位移量超過段長，這時候發(fā)生越界訪問，系統(tǒng)給出出錯信息，并使系統(tǒng)訪問中止而退出系統(tǒng)。（5）的物理地址為：1954+42=1996（6）的物理地址為：2300+11=2311注意段內(nèi)地址后三位為偏移量5.給出下面的段表，如表所示，已知下面的邏輯地址（第一個為段40作業(yè)：1、某系統(tǒng)采用動態(tài)分區(qū)存儲管理方法，某時刻在內(nèi)存中有3個空閑分區(qū)，它們的首地址和大小分別為：空閑區(qū)1（100KB，10KB）、空閑區(qū)2（200KB，30KB）、空閑區(qū)3（300KB，15KB）?，F(xiàn)在有如下的作業(yè)序列：作業(yè)1要求15KB，作業(yè)2要求16KB，作業(yè)3要求10KB。要求：（1）畫出該時刻內(nèi)存分配圖；（2）用首次適應算法和最佳適應算法畫出此時的空閑主隊列結(jié)構(gòu)；（3）哪種算法能將該作業(yè)序列裝入內(nèi)存（給出簡要的分配過程）；作業(yè)：1、某系統(tǒng)采用動態(tài)分區(qū)存儲管理方法，某時刻在內(nèi)存中有341解：（1）該時刻內(nèi)存分配圖10K30K15K0100K200K300K解：（1）該時刻內(nèi)存分配圖10K30K15K0100K20042（2）firstfit和bestfit10K30K15K0100K200K300KFirstfitBestfit（2）firstfit和bestfit10K30K15K43(3)最佳適應算法將該隊列裝入10K30K15K0100K200K300K作業(yè)1作業(yè)2作業(yè)3(3)最佳適應算法將該隊列裝入10K30K15K0100K2442、在某頁式管理中，一個進程在聯(lián)想存儲器中的頁表項如圖所示，不在聯(lián)想存儲器中的頁表項如圖所示。假設該進程體（程序和數(shù)據(jù)）代碼長度為320個字，每頁32個字?，F(xiàn)有邏輯地址（八進制）為：101，204，576。若上述地址能轉(zhuǎn)換成物理地址，則說明轉(zhuǎn)換的過程，并指出具體的物理地址，若上述地址不能轉(zhuǎn)換成物理地址，說明原因。一個進程在聯(lián)想存儲器中的頁表頁號頁幀號0F11F22F33F4不在聯(lián)想存儲器頁表頁號頁幀號4F55F66F77F88F99F102、在某頁式管理中，一個進程在聯(lián)想存儲器中的頁表項如圖所示，45解：解：頁面大小為25=32，邏輯地址的低5位為頁內(nèi)地址，其余高位為頁號。（101）8=（001000001）2，頁號2，頁幀號為F3,物理地址為(F3)1(204）8=（010000100）2，頁號4，不在聯(lián)想存儲器中，到內(nèi)存中去查找，頁幀號為F5,物理地址為(F3)4（576）8=（101111110）2，頁號11，超出頁表范圍,不形成物理地址。解：解：頁面大小為25=32，邏輯地址的低5位為頁內(nèi)地址，其465.6虛擬存儲器(VIRTUALMEMORY)5.6.1局部性原理5.6.2虛擬存儲器的原理5.6.3虛擬存儲技術的種類5.6.4存儲保護和共享5.6.5虛擬存儲的調(diào)入策略、分配策略和清除策略5.6.6置換算法5.6.7常駐集和工作集策略5.6.8虛擬存儲中的負載控制返回5.6虛擬存儲器(VIRTUALMEMORY)5.6.1475.6.1局部性原理局部性原理(principleoflocality)：指程序在執(zhí)行過程中的一個較短時期，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域。還可以表現(xiàn)為：時間局部性：一條指令的一次執(zhí)行和下次執(zhí)行，一個數(shù)據(jù)的一次訪問和下次訪問都集中在一個較短時期內(nèi)；空間局部性：當前指令和鄰近的幾條指令，當前訪問的數(shù)據(jù)和鄰近的數(shù)據(jù)都集中在一個較小區(qū)域內(nèi)。返回5.6.1局部性原理局部性原理(principleof48局部性原理的具體體現(xiàn)程序在執(zhí)行時，大部分是順序執(zhí)行的指令，少部分是轉(zhuǎn)移和過程調(diào)用指令。過程調(diào)用的嵌套深度一般不超過5，因此執(zhí)