操作系統(tǒng)概念復(fù)習(xí)資料【8-10章.ppt

操作系統(tǒng)原理課程總結(jié),軟件學(xué)院 2011.6.2,第8章 內(nèi)存管理,明確邏輯地址和物理地址 明確動態(tài)加載和動態(tài)鏈接的各自作用 明確連續(xù)內(nèi)存分配方法和內(nèi)存映射和保護方法。 明確非連續(xù)內(nèi)存分配方法 （分頁機制、分段機制，保護方法、共享方法等） 明確頁表的結(jié)構(gòu)有哪幾種形式，各自的方法,編譯程序在對一個源程序進行編譯時，總是從0號單元開始為其分配地址，其他所有地址都是從這個開始地址順序排下來的，這樣的地址稱為邏輯地址。地址空間是邏輯地址的集合。 一個編譯好的程序采用的是邏輯地址，當(dāng)他在計算機上運行時，要將“虛”的邏輯地址轉(zhuǎn)換為“實”的物理地址，這個轉(zhuǎn)換叫地址轉(zhuǎn)換，也叫地址映射。物理地址的集合叫做存儲空間。,一個編輯好的程序執(zhí)行的過程有編譯，鏈接，加載，運行。 編譯是將高級語言翻譯成為低級語言。但我們知道，一個程序，通常有多個模塊，這多個模塊在編譯后生成多個目標(biāo)模塊； 鏈接的作用是將這多個目標(biāo)模塊整合到一起，同時，在整合的過程中，將各目標(biāo)模塊之間的引用轉(zhuǎn)化為邏輯地址。 加載的作用將鏈接后的加載模塊中的邏輯地址轉(zhuǎn)化為物理地址，得到一個新的加載模塊，這個新的加載模塊已經(jīng)可以直接運行了。,關(guān)于加載：加載的實質(zhì)就是給程序分配物理地址空間， 因此加載又被稱為裝入。 裝入有三種方式：絕對裝入方式，可重定位方式，動態(tài)運行時裝入方式 不妨將鏈接的結(jié)果叫做A,將A加載的結(jié)果叫B，把加載的過程叫C. 1）絕對裝入方式:A中已經(jīng)是物理地址，因此過程C不需要進行地址轉(zhuǎn)換。 2）可重定位方式：A中是邏輯地址，當(dāng)A被裝入內(nèi)存后，過程C將邏輯地址轉(zhuǎn)化為物理地址。這種轉(zhuǎn)換只在程序加載時執(zhí)行一次，其后不在改變。,3）動態(tài)運行時裝入方式：在A中為邏輯地址，在B中仍為邏輯地址，加載的過程知識將程序放入內(nèi)存中而已。那么邏輯地址到物理地址的轉(zhuǎn)換在何時進行呢？在程序真正執(zhí)行時才進行地址轉(zhuǎn)換。,內(nèi)存保護：分為地址保護和權(quán)限保護 地址保護：沒有特別的許可，一個進程的程序只能在自己的地址空間上訪問，而不能到其他進程的地址空間上訪問。 權(quán)限保護：對于不同的進程有不同的存儲權(quán)限，對于一個只具有執(zhí)行權(quán)限的進程進行些操作是違法的。,我們知道作業(yè)的運行是要在內(nèi)存中進行的，這就涉及到了內(nèi)存的管理，即如何為程序在內(nèi)存中劃分內(nèi)存空間。方法有二：連續(xù)分配方式，離散分配方式 1）連續(xù)分配方式：為一個程序分配連續(xù)的內(nèi)存空間。連續(xù)分配方式又可分為：單一連續(xù)分配，固定分區(qū)分配，動態(tài)分區(qū)分配，動態(tài)可重定位分區(qū)分配； a)單一連續(xù)分配：任意時刻只有一個程序在內(nèi)存中，該程序使用整個內(nèi)存； b)固定分區(qū)分配：把內(nèi)存區(qū)分成若干個分區(qū)（可以均分或不均分），為每個程序分配一個內(nèi)存分區(qū)。存在內(nèi)碎片問題。 c)動態(tài)分區(qū)分配：不劃分分區(qū)的大小，根據(jù)進程的大小動態(tài)的為它分配內(nèi)存空間。存在外碎片問題。,d)可重定位分區(qū)分配：在動態(tài)分區(qū)分配的基礎(chǔ)上，加入內(nèi)存緊湊技術(shù)。 所謂內(nèi)存緊湊技術(shù)就是通過移動各程序在內(nèi)存中的位置，將外碎片集中到一起成為一個可用的大的空閑分區(qū)。內(nèi)存緊湊有份完全緊湊和部分緊湊。P206 2)關(guān)于離散分配方式： a)基本分頁分配方式：程序是要裝入內(nèi)存的，將程序的邏輯地址分成一系列同等大小的部分，稱為頁。同樣的，將內(nèi)存分成一系列同等大小的部分，稱為頁框或幀。頁的大小與幀的大小相同。,當(dāng)程序要裝入內(nèi)存時，將程序的所有頁放入空閑的頁框中即可。但這也導(dǎo)致了同一程序的不同頁不在連續(xù)的空間上，因此我們使用頁表來幫助一個進程記住這些頁，可以看到：頁表具有從邏輯地址到物理地址映射的作用。其實，頁表中存的就是表示邏輯地址的頁號和表示物理地址的塊號。 對于給定邏輯地址A=3096,頁面大小L=1K,則改地址位于（A/L）3頁，頁偏移量為(A%L)24.,b)基本分段分配方式：分段方式與分頁方式都是非連續(xù)的分配方式。 分頁是將作業(yè)機械的分成若干個頁，放到與之等大的幀中。同時用頁表記錄 頁與幀 的對應(yīng)關(guān)系。 分段是將作業(yè)按照其本身的邏輯分成若干個段（每個段的大小可以不同），然后將內(nèi)存分為若干個等大的段框，將段放到段框中，同時用段表記錄 段與段框 的對應(yīng)關(guān)系。 （#）注意，由于頁與幀等大，因此頁表是一維結(jié)構(gòu)。但段與段框的大小不一定相同，因此段表不僅需要記錄段號和段框號，還需要記錄段的大小。因此段表是二維結(jié)構(gòu)。,c)段頁式分配方式：先為作業(yè)按邏輯進行分段，再在每個段內(nèi)機械分頁。 我們來看一下三種方式的地址結(jié)構(gòu)： 頁號/頁內(nèi)偏移量 段號/段內(nèi)地址 段號/段內(nèi)頁號/頁內(nèi)偏移量,分頁管理與分段管理有很多異同： 1）頁是信息的物理單位，分頁是為了減少外碎片，提高內(nèi)存利用率，是系統(tǒng)的需求。段是信息的邏輯單位，分段是為了程序的完整性，是用戶的需求。 2）頁的大小固定，取決于系統(tǒng)。塊的大小不固定，可以不斷變化。 3）分頁的地址空間是一維的，程序員只需利用一個記憶符就可以標(biāo)識一個地址。分段的地址空間是二維的，程序員標(biāo)識一個地址時，既要給出段號，又要給出段內(nèi)地址。,頁表的結(jié)構(gòu)有三種方式：說白了就是邏輯地址與物理地址的對應(yīng)方式。 1）層次頁表：由于頁表很大，不可能直接放入內(nèi)存中，因此使用多級頁表方式。即為頁表再建立頁表。 2）哈希頁表： 3）反向頁表：,填空題,1.頁表的作用是實現(xiàn)從頁號到物理快號的地址映射。 2.在頁式管理系統(tǒng)中，用戶程序中使用的地址稱為 邏輯地址 ，實際訪問主存時由系統(tǒng)將它轉(zhuǎn)化為 物理地址 。 3.分頁管理是把內(nèi)存分為大小相等的區(qū)，每個區(qū)稱為頁幀或頁框，而把程序的邏輯空間分為若干頁，頁的大小與頁框的大小 相等 。 4.在分頁存儲管理中，為了加快地址變換速度，頁面大小的值常取2的整數(shù)次冪。,5.在請求式分頁系統(tǒng)中，被調(diào)出的頁面又立刻被調(diào)入，這種頻繁的調(diào)頁現(xiàn)象稱為顛簸。 6.分段管理中，若邏輯地址中的段內(nèi)地址大于段表中該段的段長，則發(fā)生 地址越界中斷。 7.段頁式存儲管理中，每道程序都有一個 段 表和若干個 頁 表。 8.頁式管理系統(tǒng)的邏輯地址結(jié)構(gòu)由 頁號 和 頁內(nèi)偏移量 組成。,9分段管理中的地址映射過程是：首先找到該作業(yè)段表的 起始地址 ，然后根據(jù)邏輯地址中的 段號 去查找段表得到該段的內(nèi)存起始地址，再與邏輯地址中的 段內(nèi)偏移量 相加得到物理地址。 10.請求分頁存儲管理也稱為動態(tài)頁面管理，不是把一個進程映象的所有頁面一次性全部裝入內(nèi)存，而只裝入一部分，其余部分在執(zhí)行中動態(tài)調(diào)入。 11.在段頁式管理中，邏輯地址分解為段號、頁號、頁內(nèi)偏移量 三部分。,選擇題,1.下面關(guān)于存儲管理的敘述中正確的是 。 A. 先現(xiàn)在操作系統(tǒng)中，允許用戶干預(yù)內(nèi)存的分配 B. 固定分區(qū)存儲管理是針對單道系統(tǒng)的內(nèi)存管理方案 C. 可變分區(qū)存儲管理可以對作業(yè)分配不連續(xù)的內(nèi)存單元 D. 頁式存儲管理中，頁面大小是在硬件設(shè)計時確定的 D,2.在存儲管理中，把目標(biāo)程序中的邏輯地址轉(zhuǎn)換成主存空間的物理地址的過程稱為 。 A. 存儲分配 B. 地址重定位 C. 地址保護 D. 程序移動 B 3.作業(yè)在執(zhí)行中發(fā)生了缺頁中斷，經(jīng)操作系統(tǒng)處理后，應(yīng)讓其執(zhí)行 指令。 A被中斷的前一條 B被中斷的 C被中斷的后一條 D啟動時的第一條 B,簡答題,1. 為什么要引入動態(tài)重定位？如何實現(xiàn)？ 答： （1）系統(tǒng)在內(nèi)存管理中經(jīng)常需要將進程浮動，以整理出較大的存儲空間。為了適應(yīng)進程的這種地址變化，需要對進程的地址進行變換，即動態(tài)重定位。 （2）硬件上設(shè)置“重定位寄存器”，專門存放進程的首地址。程序執(zhí)行時的內(nèi)存物理地址是由重定位寄存器中的地址和相對地址相加得到的。當(dāng)進程從內(nèi)存的某處移動到另一處時，不需對程序做任何修改，只要將進程的新地址替換原來的舊地址即可。,2.試比較分段式和分頁式存儲管理方式的主要差別。 答：它們的差別主要表現(xiàn)在以下幾個方面： （1）頁面是信息的物理單位，分頁是為了實現(xiàn)非連續(xù)分配，以便解決內(nèi)存碎片問題，或者說分頁是由于系統(tǒng)管理的需要。段是信息的邏輯單位，它含有一組意義相對完整的信息，分段的目的是為了更好地實現(xiàn)共享，滿足用戶的需要。 （2）頁面的大小固定且由系統(tǒng)確定，將邏輯地址劃分為頁號和頁內(nèi)地址是由機器硬件實現(xiàn)的。而段的長度卻不固定，它取決于用戶所編寫的程序，通常由編譯程序在對源程序進行編譯時根據(jù)信息的性質(zhì)來劃分。 （3）分頁式存儲管理的作業(yè)地址空間是一維的，分段式存儲管理的作業(yè)地址空間是二維的。,綜合分析計算題,1.某段表內(nèi)容如下： 一邏輯地址為(2，154)的實際物理地址為多少？ 答：邏輯地址（2，154）表示段號為2，即段首地址為480k，154為單元號，則實際物理地址為480k+154。,2.在采用頁式存儲管理的系統(tǒng)中，某作業(yè)J的邏輯地址空間為4頁（每頁2KB），且已知該作業(yè)的頁面映像表（即頁表）如下所示。,試借助地址變換圖（即要求畫出地址變換圖）求出有效邏輯地址4865所對應(yīng)的物理地址。,解：在本題中，一頁大小為2KB，即2048字節(jié)，則邏輯地址4865的頁號及頁內(nèi)位移為： 頁號： 4865/2048=2 頁內(nèi)位移： 4865-2048*2=769 通過頁表可知頁面2存放在物理塊6中，將物理塊號與邏輯地址中的頁內(nèi)位移進行拼接，形成物理地址，即：6*2048+769=13057,3.在一分頁存儲管理系統(tǒng)，頁面大小為4KB。已知某進程的第0、1、2、3、4頁依次存在內(nèi)存中的6、8、10、14、16物理塊號,現(xiàn)有邏輯地址為12138 B, 3A5CH B ，分別求其所在的頁號、頁內(nèi)相對地址、對應(yīng)的物理塊號以及相應(yīng)的物理地址。 解：（1）已知頁面大小4KB=4096B，頁號p=INT12138/4096=2, 頁內(nèi)位移d=12138MOD4096=3946B 查頁表可知頁號2對應(yīng)物理塊號為10。由地址轉(zhuǎn)換原理可得：塊內(nèi)位移等于頁內(nèi)位移。 故物理地址=10*4096+3946=44906B,（2）解法一： 已知頁面大小4KB=4096 B，邏輯地址3A5CH B=14940 B。頁號p=INT14940/4096=3, 頁內(nèi)位移d=14940MOD4096=2652 B，查頁表可知頁號3對應(yīng)物理塊號為14。由地址轉(zhuǎn)換原理可得：塊內(nèi)位移等于頁內(nèi)位移。 故物理地址=14*4096+2652=59996 B=EA5CH B,第9章 虛擬內(nèi)存,明確按需調(diào)頁的機制和過程 明確常用的頁面置換算法及各自優(yōu)缺點 了解幀分配的方法及最小幀數(shù)目的決定因素 明確系統(tǒng)顛簸的原因和現(xiàn)象 明確系統(tǒng)顛簸解決方法（工作集模型和頁錯誤頻率） 明確內(nèi)存映射文件機制和內(nèi)存映射I/O 了解內(nèi)核內(nèi)存分配的方法 了解虛擬內(nèi)存管理中影響性能的其他因素（預(yù)調(diào)頁、頁大小、TLB范圍、程序結(jié)構(gòu)等）,按需調(diào)頁也叫請求分頁，他是虛擬存儲器的一種實現(xiàn)方法，所謂請求分頁，就是在基本分頁的基礎(chǔ)上增加請求調(diào)頁和頁面置換兩個功能的一種存儲分配策略。 我們知道，在第8章的內(nèi)存管理中，程序在執(zhí)行過程中會被全部調(diào)入內(nèi)存，事實上，這是不現(xiàn)實的，有很多程序本身比內(nèi)存大，而我們使用虛擬存儲管理可以很好地解決這一個問題。 虛擬存儲管理即在開始時只將程序的一部分頁裝入內(nèi)存中，其余的頁放在外存。在程序的執(zhí)行過程中，若要訪問某一個外存中的頁（缺頁），那么就通過缺頁中斷向系統(tǒng)發(fā)出一個請求，請求把外存中的頁調(diào)入內(nèi)存（請求調(diào)頁）。此時，若內(nèi)存中有空閑區(qū)，則直接掉入需要的頁。否則采用頁面置換調(diào)入需要的頁，調(diào)出不需要的頁。 實現(xiàn)虛存管理必須要有相應(yīng)硬件的支持,當(dāng)需要向內(nèi)存中調(diào)入頁，而內(nèi)存已經(jīng)沒有空間時，就需要使用頁面置換算法： 1）最優(yōu)頁面置換算法：在內(nèi)存中存在的這幾頁，有的可能已經(jīng)不再需要了，把他們置換出去最好。如果內(nèi)存中存在的這幾頁每一個頁都要使用，那么把最后使用的頁置換出去。P225 該算法缺頁率低，但在每次選擇調(diào)出的頁時，需要掃描所有的頁以判斷哪個頁使用，哪個頁不使用，哪個頁最后使用，開銷大，不可能使用。,2）先進先出置換算法：把最早進入內(nèi)存的那一頁置換出去，該算法開銷比較小，但“把最早進入內(nèi)存的那一頁置換出去”不科學(xué)，很少使用。 對于所有的置換算法，分配給進程的物理塊越多，卻也率越少。但有一個特殊，就是先進先出置換算法，對于先進先出置換算法，物理塊數(shù)越多，缺頁率越多； 這個現(xiàn)象被稱為Belady異常。,3）最近最久未使用算法：將內(nèi)存所有頁面中沒有被使用時間最久的那一頁換出。 Least Resently Used,LRU是依照程序的局部性原理來設(shè)計的。為了能在缺頁時做出正確的選擇，該算法必須記錄對駐留頁面所有引用的相對順序。P227 4）由于LRU算法對計算機的硬件要求很大，因此出現(xiàn)了“近似LRU算法” a)用軟件模擬LRU算法（附加引用位算法）：比如為每個頁表保留一個八位的字節(jié)，操作系統(tǒng)把每個頁的引用位轉(zhuǎn)移到其八位字節(jié)的高位，而將其他為向有移一位，拋棄最低位。 因此這個八位寄存器中記錄了該頁在最近8個周期內(nèi)的使用情況，從右向左。將這8位數(shù)作為無符號數(shù)的話，數(shù)值最小的頁，就是最近最少使用的頁，就是該被換掉的頁。,b)時鐘算法（二次機會算法）：時鐘算法給每個頁增加一個附加位u。當(dāng)某個頁面首次裝入內(nèi)存，該頁面的附加位置1，當(dāng)該頁面被使用時，該頁面的附加位也置為1。對于該頁面算法，把所有頁組成一個循環(huán)緩沖區(qū)，并有一個指針與之關(guān)聯(lián)。 當(dāng)需要進行頁面置換時，如果指針?biāo)诘捻撁鎢=0,則進行置換，如果指針?biāo)诘捻撁鎢=1,則不進行置換，但要將u置為0,然后指針+。這相當(dāng)于給頁面一個不被換出的機會，因此叫做二次機會算法（時鐘算法）。,c)增強的二次機會算法（改進的clock算法）：clock算法只考慮了每一頁的使用頻率，并沒有考慮該頁是否被修改過。如果某一頁被修改過，在被置換出內(nèi)存之前，要重新寫回外存。因此， 該算法設(shè)置兩個附加位u,w,前者用于標(biāo)記最近是否被使用，后者用于標(biāo)記是否被修改過。因此有四種情況： u=0,v=0; u=0,v=1; u=1,v=0; u=1,v=1; 算法如下： 1）對循環(huán)頁進行第一次掃描，此次掃描不做任何更改，若存在u=0,v=0;的頁，直接替換；否則2）； 2）對循環(huán)頁進行第一次掃描，此次掃描尋找u=0,v=1;的頁。同時在掃描過程中把u=1的頁置為u=0; 3)如果2）失敗，繼續(xù)執(zhí)行1）2），一定會找到合適的置換頁。,幀的分配會受到很多限制，如最大值受到物理內(nèi)存的限制，最小值由計算機體系結(jié)構(gòu)和性能決定。 當(dāng)進程的幀的數(shù)量很少時，缺頁率會增加，不利于性能的提高。 同時，要知道，每個進程必須有足夠的幀來容納單個指令所用到的頁（最大值）；指令的頁數(shù)是由計算機體系結(jié)構(gòu)決定的；,幀（頁框或塊）的分配可以有如下算法： a)不管進程大小與優(yōu)先級，平均分配 b)依據(jù)大小比例進行分配 c)依據(jù)優(yōu)先級進行分配 d)依據(jù)優(yōu)先級和大小比例進行分配 幀的分配的另一個重要因素是頁置換，全局置換和局部置換； 全局置換：允許一個進程從另一個進程中置換幀 局部置換：僅允許一個進程從自己的進程中置換幀,當(dāng)一個進程的幀數(shù)少于其要求的最小數(shù)量，就會導(dǎo)致缺頁一而再，再而三的發(fā)生，這種頻繁的頁調(diào)度行為稱為顛簸。如果一個進程在換頁上用的時間多于在執(zhí)行上用的時間，那么這個系統(tǒng)就存在顛簸。 為了防止顛簸，必須提供給進程所需的足夠多的幀。但如何知道進程需要多少幀呢？有工作集合策略，缺頁（頁錯誤）頻率策略。,根據(jù)程序的局部性原理，可以得到一個進程的工作集，工作集就是“進程在最近的時間內(nèi)引用的頁的集合”。有了工作集，來看工作集策略解決顛簸的算法： 1)操作系統(tǒng)為每個進程分配大于其工作集的禎。 2)如果還有空閑幀，那么可以啟動另外的進程. 3)如果所有工作集的總數(shù)操過了可用幀的個數(shù)，則暫停一些進程，并將該進程占有的頁分配給其他進程；,缺頁頻率策略：為了充分提高CPU的使用率，為缺頁頻率設(shè)置上限和下限。 當(dāng)缺頁頻率高于上限時，說明進程的禎不夠，這為其分配更多的幀，若無可用幀，則暫停一個進程。 當(dāng)缺頁頻率低于下限時，說明進程的幀太多，則從該進程中移走幀。,對文件進行操作有兩種方法，一種是直接通過系統(tǒng)調(diào)用來實現(xiàn)，費時費力。另外一種是內(nèi)存映射文件。 所謂內(nèi)存映射文件，就是進程不去對處于外存的文件進行操作，而是將要處理的文件放入內(nèi)存，而后再進行讀寫。至于內(nèi)存中的文件與外存中的文件的同步問題，交給操作系統(tǒng)來完成。同時，允許多個進程將同一文件映射到各自進程的虛擬地址中，以實現(xiàn)數(shù)據(jù)共享。,內(nèi)存映射I/O:將I/O設(shè)備映射到內(nèi)存中，這樣進程對I/O設(shè)備的訪問就不需要訪問I/O空間，而只需要訪存即可。,對于虛擬內(nèi)存管理，置換算法和分配策略是影響其性能的主要問題，然而含有一些其他因素要考慮。 預(yù)調(diào)頁、頁大小、TLB范圍、程序結(jié)構(gòu)等。,選擇題,1. 下面關(guān)于存儲管理的敘述中正確的是 。 A. 存儲保護的目的是限制內(nèi)存分配 B. 在內(nèi)存為M，由N個用戶的分時系統(tǒng)中，每個用戶占有M/N的內(nèi)存空間 C. 在虛擬系統(tǒng)中，只要磁盤空間無限大，程序就成擁有任意大的編址空間 D. 實現(xiàn)虛存管理必須要有相應(yīng)硬件的支持 D,2. 在虛擬頁式存儲管理方案中，下面哪一部分完成將頁面調(diào)入內(nèi)存的工作？ A. 缺頁中斷處理 B. 頁面淘汰過程 C. 工作集模型應(yīng)用 D. 緊縮技術(shù)利用 A 3. 在虛擬頁式存儲管理方案中，當(dāng)查找的頁面不在那里時，會產(chǎn)生缺頁中斷？ A. 外存 B. 虛存 C. 內(nèi)存 D. 地址空間 C,4. 在虛擬頁式存儲管理方案中，所謂最近最少使用頁面淘汰算法是指 。 A. 將駐留在內(nèi)存中的頁面隨即挑選一頁淘汰 B. 將駐留在內(nèi)存中時間最長的一頁淘汰 C. 將駐留在內(nèi)存中使用次數(shù)最少的一頁淘汰 D. 將駐留在內(nèi)存中最后一次訪問時間距離當(dāng)前時間間隔最長的一頁淘汰 D,5. 在虛擬頁式存儲管理方案中，先進先出頁面置換算法是指 。 A. 將駐留在內(nèi)存中的頁面隨即挑選一頁淘汰 B. 將駐留在內(nèi)存中時間最長的一頁淘汰 C. 將駐留在內(nèi)存中使用次數(shù)最少的一頁淘汰 D. 將駐留在內(nèi)存中最后一次訪問時間距離當(dāng)前時間間隔最長的一頁淘汰 B,簡答題,1.什么是顛簸？產(chǎn)生顛簸的原因是什么？ 答： （1）顛簸是由于內(nèi)存空間競爭引起的。當(dāng)需要將一個新頁面調(diào)入內(nèi)存時，因內(nèi)存空間緊張，不得不將一個舊頁面置換出去，而剛剛置換出去的舊頁面可能又要被使用，因此需要重新將它調(diào)入。若一個進程頻繁地進行頁面調(diào)入調(diào)出，勢必加大系統(tǒng)的開銷，使系統(tǒng)運行效率降低。通常稱這種現(xiàn)象為該進程發(fā)生了顛簸。 （2）產(chǎn)生顛簸的原因主要有：系統(tǒng)內(nèi)的進程數(shù)量太多，系統(tǒng)采取的置換算法不夠合理。,2.常見的頁面置換算法 答：最優(yōu)頁面置換算法，先進先出算法，最近最長時間未使用（LRU）算法，近似的LRU算法（附加引用位算法，二次機會算法，增強的二次機會算法）,3.缺頁的概念，頁表的含義 缺頁：要訪問的頁面不在主存，需要操作系統(tǒng)將其調(diào)入主存后再進行訪問。 頁表：用來將虛擬地址空間映射到物理地址空間的數(shù)據(jù)結(jié)構(gòu)稱為頁表。 4.實現(xiàn)虛擬存儲器需要哪些硬件支持 a. 對于為實現(xiàn)請求分頁存儲管理方式的系統(tǒng)，除了需要一臺具有一定容量的內(nèi)存及外存的計算機外，還需要有頁表機制，缺頁中斷機構(gòu)以及地址變換機構(gòu)； b. 對于為實現(xiàn)請求分段存儲管理方式的系統(tǒng)，除了需要一臺具有一定容量的內(nèi)存及外存的計算機外，還需要有段表機制，缺段中斷機構(gòu)以及地址變換機構(gòu)；,綜合分析計算題,1個請求分頁系統(tǒng)中，采用FIFO、最近最久未使用、最佳頁面置換算法時，假如一個作業(yè)的頁面走向為4、3、2、1、4、3、5、4、3、2、1、5，當(dāng)分配給該作業(yè)的物理塊數(shù)M分別為3和4時，試計算在訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率。并比較所得結(jié)果。,解： (1)分配給該作業(yè)3個物理塊時，采用FIFO頁面替換算法，進程執(zhí)行過程中頁面置換如下表: 上表中，第一行為進程執(zhí)行時要訪問的頁面次序，第二行為最先調(diào)入主存的頁面，最后一行為發(fā)生缺頁中斷時替換的頁面。 缺頁次數(shù)為9，缺頁中斷率為：9/12。,（2）分配給該作業(yè)4個物理塊時，采用FIFO頁面替換算法，進程執(zhí)行過程中頁面置換如下表: 上表中，第一行為進程執(zhí)行時要訪問的頁面次序，第二行為最先調(diào)入主存的頁面，最后一行為發(fā)生缺頁中斷時替換的頁面。缺頁次數(shù)為10，缺頁中斷率為：10/12。 結(jié)果分析：多分配一個物理塊沒有減少缺頁次數(shù)。,(3)分配給該作業(yè)3個物理塊時，采用LRU頁面替換算法，進程執(zhí)行過程中頁面置換如下表: 缺頁次數(shù)為10，缺頁中斷率為：10/12。,分配給該作業(yè)4個物理塊時，采用LRU頁面替換算法，進程執(zhí)行過程中頁面置換如下表: 缺頁次數(shù)為8，缺頁中斷率為：8/12。 結(jié)果分析：多分配一個物理塊可有效減少缺頁次數(shù)。,(3)分配給該作業(yè)3個物理塊時，采用最佳頁面替換算法，進程執(zhí)行過程中頁面置換如下表: 缺頁次數(shù)為7，缺頁中斷率為：7/12。,分配給該作業(yè)4個物理塊時，采用最佳頁面替換算法，進程執(zhí)行過程中頁面置換如下表: 缺頁次數(shù)為6，缺頁中斷率為：6/12。 結(jié)果分析：多分配一個物理塊可減少缺頁次數(shù)。,第10章 文件系統(tǒng)接口,明確文件系統(tǒng)提供的功能 明確文件的訪問方法 明確目錄的作用 明確常用的目錄結(jié)構(gòu)及各自優(yōu)缺點 明確符號鏈接和硬鏈接的區(qū)別,文件系統(tǒng)是指 在操作系統(tǒng)中對文件進行管理的有關(guān)軟件和數(shù)據(jù)的集合，說白了，就是操作系統(tǒng)管理文件的方法。 文件系統(tǒng)主要有5個功能： 1）對文件進行按名存取 2）為用戶提供統(tǒng)一和友好的接口 3）對文件和文件目錄進行管理 4）對文件存儲空間進行分配和管理 5）文件的共享與保護,一個文件是由多個物理記錄組成的，而對文件進行訪問時就是去找到這些物理記錄并對其進行讀寫。說白了，文件訪問的過程就是對文件內(nèi)部的物理記錄進行查找的過程。 文件的訪問方法有3種： 1）順序訪問 2）直接訪問 3）其他訪問方式：比如為文件中的物理記錄創(chuàng)建索引。 其實就是對文件內(nèi)的物理記錄的不同查找方式,文件目錄就是一個數(shù)據(jù)結(jié)構(gòu)，在這個數(shù)據(jù)結(jié)構(gòu)中，記錄了文件與其對應(yīng)的物理地址。 文件目錄與文件的關(guān)系就相當(dāng)于文件與其內(nèi)部物理記錄的關(guān)系，說白了，我們是對物理記錄進行讀寫的，但在讀寫前，我們要通過文件目錄到文件的映射A找到需要的文件，然后再通過文件到物理記錄的映射B找到要操作的物理記錄。 對于映射B的實現(xiàn)方法，我們已經(jīng)介紹完畢，即文件的訪問方法。對于映射A的實現(xiàn)方法，就是下面要介紹的目錄結(jié)構(gòu)。,一般來講，目錄管理的要求如下：實現(xiàn)“按名存取”，提高檢索速度，允許文件同名（允許不同目錄中存在相同名稱），允許文件共享（允許多用戶共享）。 目錄結(jié)構(gòu)有三種形式： 1）單層目錄結(jié)構(gòu)：在整個文件系統(tǒng)中，只有一個目錄，所有文件全部在該目錄中。 優(yōu)點：易于實現(xiàn)，便于管理 缺點：不允許文件同名，文件查找速度慢，不便于文件共享。只滿足了目錄管理的第一點要求。,2）雙層目錄結(jié)構(gòu)：將文件目錄分為主文件目錄（MFD）和用戶文件目錄（UFD）兩級。 優(yōu)點：按名存取，比單層提高了檢索速度（但當(dāng)文件較多時，速度仍然很慢），在不同的用戶目錄下允許同名，允許不同用戶間共享文件。 缺點：由于隔離了不同的用戶，所以各個用戶之間不便于共享文件。 3）多級目錄結(jié)構(gòu)：對于大型文件系統(tǒng)，采用三級或三級以上的目錄結(jié)構(gòu)。分為 a）樹狀目錄結(jié)構(gòu)：是最常用的目錄結(jié)構(gòu)。 絕對路徑與相對路徑名,b）無環(huán)圖目錄結(jié)構(gòu)：樹形結(jié)構(gòu)禁止共享文件和目錄，而無環(huán)圖目錄結(jié)構(gòu)允許共享子目錄和文件，他是樹形結(jié)構(gòu)的擴展。 不同文件名可能表示同一文件。對于查找與統(tǒng)計來說可能會帶來一定的問題 刪除問題,常用目錄結(jié)構(gòu),62,c)通用圖結(jié)構(gòu)：在樹結(jié)構(gòu)上增加鏈接。 如何確保無環(huán) 只允許鏈接發(fā)生在文件，而非子目錄上。 每當(dāng)新鏈接建立的時候，就采用相應(yīng)的算法進行檢測，以避免環(huán)的出現(xiàn)。 刪除問題 垃圾收集 由于自我引用的文件，其引用計數(shù)不等于0； 垃圾收集涉及遍歷整個文件系統(tǒng)，并標(biāo)記所有可訪問的空間。然后，第二次將所有沒有標(biāo)記的部分收集到空閑空間鏈表上。 。,鏈接就是在共享文件和訪問它的用戶的目錄項之間建立聯(lián)系的一種方法；分為軟鏈接和硬鏈接。,硬鏈接就是源文件的一個別名，對任何一個硬鏈接進行操作（非刪除操作），都是對源文件的操作；而且當(dāng)刪除一個或幾個硬鏈接時，不會刪除源文件。只有當(dāng)源文件的所有硬鏈接都被刪除時，才刪除源文件； 軟鏈接（符號鏈接）是建立實實在在的文件，但該文件里寫入的是源文件的地址路徑，因此，對任何一個軟鏈接進行操作（非刪除操作），系統(tǒng)會自動把該操作轉(zhuǎn)換為對源文件的操作。但刪除軟鏈接時，只刪除軟鏈接對應(yīng)的文件而不刪除源文件。,硬鏈接，只能應(yīng)用于文件，而不能應(yīng)用于目錄，而且不能跨文件系統(tǒng)（即分區(qū)）； 符號鏈接，既可以應(yīng)用于文件，又可以應(yīng)用于目錄，而且可跨文件系統(tǒng)（分區(qū)）； 由于符號鏈接的優(yōu)越性，所以其常被使用。,選擇題,1.文件系統(tǒng)采用多級目錄結(jié)構(gòu)后，對于不同用戶的文件，其文件名 。 A應(yīng)該相同 B應(yīng)該不同 C可以相同也可以不同 D受系統(tǒng)約束 C 2.文件的邏輯組織將文件分為記錄式和（）文件。 A）索引文件 B）流式文件 C）字符文件 D）讀寫文件 B,3.為了對文件系統(tǒng)中的文件進行安全管理，任何一個用戶在進入系統(tǒng)時都必須進行注冊，這一級的安全是（）級的安全管理。 A）系統(tǒng)級 B）目錄級 C）用戶級 D）文件級 A 4系統(tǒng)采用二級目錄結(jié)構(gòu)，目的是（）。 A）縮短訪問文件的時間 B）實現(xiàn)共享 C）節(jié)省內(nèi)存 D）解決文件重名問題 D 5.件系統(tǒng)中，要求物理塊必須連續(xù)的物理文件是（）。 A）索引文件 B）順序文件 C）鏈接文件 D）串連文件 B,簡答題,1. 文件管理有哪些主要功能？其主要任務(wù)是什么？ 答：文件管理的主要功能和主要任務(wù)有以下四個方面： （1）外存空間管理