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

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