操作系統(tǒng)原理

會(huì)計(jì)學(xué)1操作系統(tǒng)原理2存儲(chǔ)器可分為：內(nèi)存儲(chǔ)器和外存儲(chǔ)器；內(nèi)存儲(chǔ)器：可以被CPU直接訪問。外存儲(chǔ)器：不可以被CPU直接訪問，外存與CPU之間只能夠在輸入輸出控制系統(tǒng)的管理下，進(jìn)行信息交換。第1頁/共170頁32.1存儲(chǔ)管理基礎(chǔ)2.1.1虛擬地址與物理地址第2頁/共170頁4內(nèi)存儲(chǔ)器是由一個(gè)個(gè)存儲(chǔ)單元組成，一個(gè)存儲(chǔ)單元可存放若干個(gè)二進(jìn)制的位（bit），8個(gè)二進(jìn)制位被稱為一個(gè)字節(jié)（Byte）。內(nèi)存中的存儲(chǔ)單元按一定順序進(jìn)行編號(hào)，每個(gè)單元所對應(yīng)的編號(hào)，稱為該單元的單元地址。物理地址（絕對地址，實(shí)地址）：內(nèi)存中存儲(chǔ)單元的地址。物理地址可直接尋址。邏輯地址（相對地址，虛地址）：用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對地址的形式。其首地址為0，其余指令中的地址都相對于首地址來編址。不能用邏輯地址在內(nèi)存中讀取信息。第3頁/共170頁5第4頁/共170頁6地址重定位地址重定位（地址映射）：將用戶程序中的邏輯地址轉(zhuǎn)換為運(yùn)行時(shí)由機(jī)器直接尋址的物理地址。當(dāng)程序裝入內(nèi)存時(shí),操作系統(tǒng)要為該程序分配一個(gè)合適的內(nèi)存空間，由于程序的邏輯地址與分配到內(nèi)存物理地址不一致,而CPU執(zhí)行指令時(shí)，是按物理地址進(jìn)行的，所以要進(jìn)行地址轉(zhuǎn)換。第5頁/共170頁72.1.2地址定位方式1.固定定位方式

由程序員在編寫程序時(shí)或由編譯連接程序?qū)υ闯绦蜻M(jìn)行編譯連接時(shí)，直接指定程序在執(zhí)行時(shí)訪問的實(shí)際存儲(chǔ)器地址的方式稱為固定定位方式。此種定位方式一般只適合于單板機(jī)或單用戶系統(tǒng)。在多道程序環(huán)境下，應(yīng)保證各個(gè)作業(yè)的地址互不重疊，這就比較困難了。第6頁/共170頁8第7頁/共170頁92.靜態(tài)重定位方式

源程序經(jīng)編譯和連接后生成目標(biāo)代碼中的地址是以0為起始地址的相對地址。當(dāng)需要執(zhí)行時(shí)，由裝入程序運(yùn)行重定位程序模塊，根據(jù)作業(yè)在本次分配到的內(nèi)存起始地址，將可執(zhí)行目標(biāo)代碼裝到指定內(nèi)存地址中，并修改所有有關(guān)地址部分的值。修改的方式是對每一個(gè)邏輯地址的值加上內(nèi)存區(qū)首地址（或稱基地址）值。第8頁/共170頁10第9頁/共170頁11靜態(tài)重定位的特點(diǎn)（1）靜態(tài)重定位是在程序運(yùn)行之前完成地址重定位工作的；（2）靜態(tài)重定位由軟件實(shí)現(xiàn)，無須硬件提供支持；（3）實(shí)行靜態(tài)重定位時(shí)，地址重定位工作是在程序裝入時(shí)被一次集中完成的；（4）絕對地址空間里的目標(biāo)程序與原相對地址空間里的目標(biāo)程序面目已不相同，因?yàn)榍罢哌M(jìn)行了地址調(diào)整；（5）實(shí)施靜態(tài)重定位后，若用戶程序在內(nèi)存中做了移動(dòng)，那么程序指令中的地址就不再反映所在的存儲(chǔ)位置了，除非重新進(jìn)行地址重定位。第10頁/共170頁123.動(dòng)態(tài)重定位方式

采用動(dòng)態(tài)重定位方式，將程序在裝入內(nèi)存時(shí)，不必修改程序的邏輯地址值，程序執(zhí)行期間在訪問內(nèi)存之前，再實(shí)時(shí)地將邏輯地址變換成物理地址。動(dòng)態(tài)重定位要靠硬件地址變換機(jī)構(gòu)實(shí)現(xiàn)。①當(dāng)程序開始執(zhí)行時(shí)，系統(tǒng)將程序在內(nèi)存的起始地址送入地址變換機(jī)構(gòu)中的基地址寄存器BR中。②在執(zhí)行指令時(shí)，若涉及到邏輯地址，則先將該地址送入虛擬地址寄存器VR，再將BR和VR中的值相加后送入地址寄存器MR，并按MR中的值訪問內(nèi)存。（MR）=（BR）+（VR）第11頁/共170頁13第12頁/共170頁142.2基本存儲(chǔ)管理方法2.2.1單一連續(xù)分區(qū)存儲(chǔ)管理基本思想：內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。應(yīng)用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。最簡單，適用于單用戶、單任務(wù)的OS；單用戶系統(tǒng)在一段時(shí)間內(nèi)，只有一個(gè)進(jìn)程在內(nèi)存。第13頁/共170頁15特點(diǎn)（1）系統(tǒng)總是把整個(gè)用戶區(qū)分配給一個(gè)用戶使用。（2）實(shí)際上，內(nèi)存用戶區(qū)又被分為“使用區(qū)”和“空閑區(qū)”兩部分。

在操作系統(tǒng)中，把分配給用戶、但又未使用的區(qū)域稱為“內(nèi)部碎片”。（3）由于任何時(shí)刻內(nèi)存的用戶區(qū)中只有一個(gè)作業(yè)運(yùn)行，因此這種系統(tǒng)只使用于單用戶的情況。（4）進(jìn)入內(nèi)存的作業(yè)，獨(dú)享系統(tǒng)中的所有資源，包括內(nèi)存中的整個(gè)用戶區(qū)。第14頁/共170頁16特點(diǎn)（5）由于整個(gè)用戶區(qū)都分配給了一個(gè)用戶使用，因此作業(yè)進(jìn)入用戶區(qū)后，沒有移動(dòng)的必要。采用這種存儲(chǔ)分配策略時(shí)，將對用戶程序?qū)嵭徐o態(tài)重定位。（6）實(shí)行靜態(tài)重定位，并不能阻止用戶有意無意地通過不恰當(dāng)?shù)刂噶铌J入操作系統(tǒng)所占用的存儲(chǔ)區(qū)域，如何阻止對操作系統(tǒng)的侵?jǐn)_，就是所謂的“存儲(chǔ)保護(hù)”問題。

用于存儲(chǔ)保護(hù)的專用寄存器－“界限寄存器”第15頁/共170頁17存儲(chǔ)保護(hù)過程：在用戶態(tài)下，對內(nèi)存的每一次訪問，都要在硬件的控制下，與界限寄存器中的內(nèi)容進(jìn)行比較。一旦發(fā)現(xiàn)該訪問的地址小于界限寄存器中的地址，就會(huì)產(chǎn)生“地址越界”中斷，阻止這次訪問的進(jìn)行。優(yōu)點(diǎn)：易于管理，便于用戶的了解和使用。缺點(diǎn)：由于每次只能有一個(gè)作業(yè)進(jìn)入內(nèi)存，故它不適用于多道程序設(shè)計(jì)，整個(gè)系統(tǒng)的工作效率不高，資源利用率底下。只要作業(yè)比用戶區(qū)小，那么在用戶區(qū)里就會(huì)形成碎片，造成內(nèi)存儲(chǔ)器資源的浪費(fèi)。若用戶作業(yè)的相對地址空間比用戶區(qū)大，那么該作業(yè)就無法運(yùn)行。第16頁/共170頁182.2.2固定分區(qū)存儲(chǔ)管理把內(nèi)存區(qū)固定地劃分為若干個(gè)大小相等（和不等）的連續(xù)分區(qū)。每個(gè)分區(qū)裝一個(gè)且只能裝一個(gè)作業(yè)，分區(qū)的劃分原則一般由系統(tǒng)操作員或操作系統(tǒng)決定，分區(qū)一旦劃分結(jié)束，在整個(gè)執(zhí)行過程中每個(gè)分區(qū)的長度和內(nèi)存的總分區(qū)個(gè)數(shù)將保持不變。分區(qū)大小相等：只適合于多個(gè)相同程序的并發(fā)執(zhí)行（處理多個(gè)類型相同的對象）。分區(qū)大小不等：多個(gè)小分區(qū)、適量的中等分區(qū)、少量的大分區(qū)。根據(jù)程序的大小，分配當(dāng)前空閑的、適當(dāng)大小的分區(qū)。第17頁/共170頁19固定分區(qū)(大小相同)固定分區(qū)(多種大小)第18頁/共170頁20內(nèi)存分配

為了便于內(nèi)存分配，通常將分區(qū)按大小進(jìn)行排隊(duì)，并為之建立一張分區(qū)說明表，其中各表項(xiàng)包括每個(gè)分區(qū)的起始地址、大小及狀態(tài)（是否已分配）。當(dāng)有一用戶程序要裝入時(shí)，由內(nèi)存分配程序檢索該表，從中找出一個(gè)能滿足要求的、尚未分配的分區(qū)，將之分配給該應(yīng)用程序，然后將該表項(xiàng)中的狀態(tài)置為“已分配”；若未找到大小足夠的分區(qū)，則拒絕為該用戶程序分配內(nèi)存。第19頁/共170頁21第20頁/共170頁22地址重定位與存儲(chǔ)保護(hù)固定分區(qū)存儲(chǔ)管理中，每個(gè)分區(qū)只允許裝入一個(gè)作業(yè)，作業(yè)在運(yùn)行期間沒有必要移動(dòng)自己的位置，因此，應(yīng)該對程序?qū)嵭徐o態(tài)重定位。在固定分區(qū)存儲(chǔ)管理中，不僅要防止用戶程序?qū)Σ僮飨到y(tǒng)形成的侵?jǐn)_，也要防止用戶程序與用戶程序之間形成侵?jǐn)_。因此必須在CPU中設(shè)置一對專用的寄存器，用于存儲(chǔ)保護(hù)。將兩個(gè)專用寄存器分別起名為“下界寄存器”和“上界寄存器”第21頁/共170頁23存儲(chǔ)保護(hù)過程當(dāng)進(jìn)程調(diào)度程序調(diào)度某個(gè)作業(yè)進(jìn)程運(yùn)行時(shí)，就把該作業(yè)所在分區(qū)的低邊界地址裝入到低界限寄存器，高邊界地址裝入到高界限寄存器。作業(yè)運(yùn)行時(shí)，對內(nèi)存的每一次訪問，都要在硬件的控制下，與兩個(gè)界限寄存器中的內(nèi)容進(jìn)行比較。一旦發(fā)現(xiàn)該訪問的地址小于界限寄存器中的地址，就會(huì)產(chǎn)生“地址越界”中斷，阻止這次訪問的進(jìn)行。第22頁/共170頁24固定分區(qū)存儲(chǔ)管理的特點(diǎn)（1）它是最簡單的、具有“多道”色彩的存儲(chǔ)管理方案。（2）當(dāng)把一個(gè)分區(qū)分配給某個(gè)作業(yè)時(shí)，該作業(yè)的程序?qū)⒁淮涡缘娜勘谎b入到分配給它的連續(xù)分區(qū)里。第23頁/共170頁25優(yōu)點(diǎn)：易于實(shí)現(xiàn)，開銷小。缺點(diǎn)：內(nèi)碎片造成浪費(fèi)（小作業(yè)不能有效地利用分區(qū)空間。分區(qū)總數(shù)在系統(tǒng)生成時(shí)確定（固定），限制了并發(fā)執(zhí)行的程序數(shù)目。如果到達(dá)作業(yè)的尺寸比任何一個(gè)分區(qū)的長度都大，那么它就無法得到運(yùn)行。固定分區(qū)方式的評價(jià)第24頁/共170頁262.3可變分區(qū)存儲(chǔ)管理

基本思想：

內(nèi)存不是預(yù)先劃分好的，而是當(dāng)作業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配。若有足夠的空間，則按需要分割一部分分區(qū)給該進(jìn)程否則令其等待主存空間優(yōu)點(diǎn)：沒有內(nèi)碎片。缺點(diǎn)：有外碎片。第25頁/共170頁27外部碎片問題操作系統(tǒng)20KB0256KB作業(yè)A(16KB)空閑區(qū)(236KB)空閑區(qū)(220KB)作業(yè)B(100KB)空閑區(qū)(120KB)作業(yè)C(70KB)空閑區(qū)(50KB)空閑區(qū)(100KB)作業(yè)D(75KB)空閑區(qū)(25KB)內(nèi)碎片：占用分區(qū)之內(nèi)未被利用的空間外碎片：占用分區(qū)之間難以利用的空閑分區(qū)（通常是小空閑分區(qū)）。第26頁/共170頁282.3.1空閑存儲(chǔ)區(qū)表管理空閑內(nèi)存區(qū)的數(shù)據(jù)結(jié)構(gòu)可采用鏈接法和連續(xù)線性表格法。下面舉一個(gè)連續(xù)線性表格管理空閑內(nèi)存的方法，如采用鏈接法，就需要在表項(xiàng)中增加一個(gè)指向下一個(gè)空閑區(qū)的指針。每一個(gè)空閑分區(qū)用一個(gè)map結(jié)構(gòu)管理：structmap{unsignedm_size;//空閑分區(qū)的長度

char*m_addr;//空閑分區(qū)的起始地址

};structmapcoremap[N];各個(gè)空閑分區(qū)按起始地址由低到高順次登記在空閑存儲(chǔ)區(qū)表中，m_size為0的表項(xiàng)是空白表項(xiàng)，它們集中在表的后部第27頁/共170頁29在系統(tǒng)初始階段，擁有一塊很大的內(nèi)存空白區(qū)，這時(shí)空閑存儲(chǔ)區(qū)表coremap中只需有一項(xiàng)登記該空閑區(qū)。其余的coremap表項(xiàng)為空白項(xiàng)，即m_size皆為零。第28頁/共170頁30以后隨著很多作業(yè)的不斷申請內(nèi)存和釋放內(nèi)存，整個(gè)存儲(chǔ)空間將出現(xiàn)許多大小不等的區(qū)域，存儲(chǔ)區(qū)表和實(shí)際的內(nèi)存空間就可能變成如圖所示的情況。第29頁/共170頁312.3.2首次適應(yīng)算法1.分配算法。采用首次適應(yīng)法為作業(yè)分配大小為size的內(nèi)存空間時(shí)，總是從表的起始端的低地址部分開始查找。當(dāng)?shù)谝淮握业酱笥诨虻扔谏暾埓笮〉目臻e區(qū)時(shí)，就按所需大小分配給作業(yè)。如果分配后原空閑區(qū)還有剩余空間，就修改原存儲(chǔ)區(qū)表項(xiàng)的m_size和m_addr，使它記錄余下的“零頭”。如果作業(yè)所需空間正好等于該空閑區(qū)大小，那么該空閑區(qū)表項(xiàng)的m_size就成為0。接下來要?jiǎng)h除表中這個(gè)“空洞”，即將隨后的各非零表項(xiàng)依次上移一個(gè)位置第30頁/共170頁32char*malloc(mp,size)structmap*mp;unsignedsize;{registerchar*a;registerstructmap*bp;for(bp=mp;bp->m_size;bp++){if(bp->m_size>=size){a=bp->m_addr;bp->m_addr+=size;if((bp->m_size-=size)==0)do{bp++;(bp-1)->m_addr=bp->m_addr;}while((bp-1)->m_size=bp->m_size);return(a);}}return(0);}第31頁/共170頁332.回收算法當(dāng)某一作業(yè)釋放以前所分配到的內(nèi)存時(shí)，就要將該內(nèi)存區(qū)歸還給系統(tǒng)，使其成為空閑區(qū)而可被其他作業(yè)使用。釋放區(qū)與原空閑區(qū)相鄰情況可歸納為如圖所示的4種情況。第32頁/共170頁34①僅與前空閑區(qū)相連：合并前空閑區(qū)和釋放區(qū)構(gòu)成一塊大的新空閑區(qū)，并修改空閑區(qū)表項(xiàng)。該空閑區(qū)的m_addr不變，仍為原前空閑區(qū)的首地址，修改表項(xiàng)的長度域m_size為原m_size與釋放區(qū)長度之和。②與前空閑區(qū)和后空閑區(qū)都相連：將三塊空閑區(qū)合并成一塊空閑區(qū)。修改空閑區(qū)表中前空閑區(qū)表項(xiàng)，其起始地址m_addr仍為原前空閑區(qū)起始地址，其大小m_size等于三個(gè)空閑區(qū)長度之和，這塊大的空閑區(qū)由前空閑區(qū)表項(xiàng)登記。接下來還要在空閑區(qū)表中刪除后項(xiàng)，方法是將后項(xiàng)以下的非空白表項(xiàng)順次上移一個(gè)位置。第33頁/共170頁35③僅與后空閑區(qū)相連：與后空閑區(qū)合并，使后空閑區(qū)表項(xiàng)的m_addr為釋放區(qū)的起始地址，m_size為釋放區(qū)與后空閑區(qū)的長度之和。④與前、后空閑區(qū)皆不相連：在前、后空閑區(qū)表項(xiàng)中間插入一個(gè)新的表項(xiàng)，其m_addr為釋放區(qū)的起始地址，m_size為釋放區(qū)的長度。為此，先要將后項(xiàng)及以下表項(xiàng)都下移一個(gè)位置第34頁/共170頁36若采用首次適應(yīng)法，則其分配算法簡單且合并相鄰空閑區(qū)也很容易。該算法的實(shí)質(zhì)是盡可能利用存儲(chǔ)區(qū)低地址部分的空閑區(qū)，而盡量在高地址部分保存較大的空閑區(qū)，以便一旦有分配大的空閑區(qū)的要求時(shí)，容易得到滿足。其缺點(diǎn)是由于查找總是從表首開始，前面的空閑區(qū)往往被分割得很小，能滿足分配要求的可能性較小，查找次數(shù)就較多。系統(tǒng)中作業(yè)越多，這個(gè)問題就越嚴(yán)重。第35頁/共170頁372.3.3循環(huán)首次適應(yīng)算法把空閑表設(shè)計(jì)成順序結(jié)構(gòu)或鏈接結(jié)構(gòu)的循環(huán)隊(duì)列，各空閑區(qū)仍按地址從低到高的次序登記在空閑區(qū)的管理隊(duì)列中。同時(shí)需要設(shè)置一個(gè)起始查找指針，指向循環(huán)隊(duì)列中的一個(gè)空閑區(qū)表項(xiàng)。循環(huán)首次適應(yīng)法分配時(shí)總是從起始查找指針?biāo)傅谋眄?xiàng)開始查找。第一次找到滿足要求的空閑區(qū)時(shí)，就分配所需大小的空閑區(qū)，修改表項(xiàng)，并調(diào)整起始查找指針，使其指向隊(duì)列中被分配的后面的那塊空閑區(qū)。下次分配時(shí)就從新指向的那塊空閑區(qū)開始查找。第36頁/共170頁382.3.3循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)法的實(shí)質(zhì)是起始查找指針?biāo)傅目臻e區(qū)和其后的空閑區(qū)群常為較長時(shí)間未被分割過的空閑區(qū)，它們已合并成為大的空閑區(qū)可能性較大。比起首次適應(yīng)法來，在沒有增加多少代價(jià)的情況下卻明顯地提高了分配查找的速度。釋放算法基本同首次適應(yīng)法一樣。首次適應(yīng)法和循環(huán)首次適應(yīng)法不僅可用于內(nèi)存的分配和釋放，也可用于進(jìn)程圖像交換的輔存空間的分配和釋放，其管理空閑區(qū)的數(shù)據(jù)結(jié)構(gòu)也相同。第37頁/共170頁392.3.4最佳適應(yīng)算法所謂最佳適應(yīng)算法就是在所有大于或等于要求分配長度的空閑分區(qū)中挑選一個(gè)最小的分區(qū)，在分割后，所余下的剩余存儲(chǔ)區(qū)最小或等于零。因此，該算法的空閑區(qū)利用率高，較大的空閑區(qū)被保存下來。空閑存儲(chǔ)區(qū)管理表的組織方法可以采用順序結(jié)構(gòu)，也可采用鏈接結(jié)構(gòu)。如采用順序結(jié)構(gòu)，空閑分區(qū)按地址由小到大的順序登記在表中，分配時(shí)需要搜索所有的空閑分區(qū)，以在其中挑出一個(gè)滿足分配大小的最小的分區(qū)。此種管理結(jié)構(gòu)的釋放算法可用順序結(jié)構(gòu)的首次適應(yīng)法。第38頁/共170頁402.3.4最佳適應(yīng)算法當(dāng)采用鏈接結(jié)構(gòu)時(shí)，空閑區(qū)也可按由小到大的非遞減次序排列。分配時(shí)總是從最小的第一項(xiàng)開始，這樣第一次找到的滿足條件的空閑區(qū)必定是最合適的。平均而言，只要搜索一半數(shù)目的空閑區(qū)表項(xiàng)就能找到最佳配合的空閑區(qū)，但尋找較大空閑區(qū)比較費(fèi)時(shí)。采用按存儲(chǔ)區(qū)大小排序的鏈接表會(huì)降低釋放算法的效率。由于空閑區(qū)是按大小而不是按地址序號(hào)排序的，因此釋放回收空閑區(qū)時(shí)要在整個(gè)鏈表上尋找地址相鄰的前、后空閑區(qū)，合并后又要插入到合適的位置，因此釋放算法比前兩種算法耗時(shí)得多。第39頁/共170頁412.3.5最差適應(yīng)算法最差適應(yīng)法所分割的空閑存儲(chǔ)區(qū)是所有空閑分區(qū)中的最大的一塊。在實(shí)施最差適應(yīng)法時(shí)，空閑區(qū)管理表項(xiàng)一般以m_size由大到小的次序組織成一個(gè)鏈接表，因此查找分割的總是最大的第一個(gè)空閑存儲(chǔ)區(qū)。實(shí)現(xiàn)最差適應(yīng)法時(shí)的空閑存儲(chǔ)區(qū)表的組織方法一般都是采用按空閑塊由大到小排序的鏈接表。采用按存儲(chǔ)區(qū)大小順序排列的鏈接表的形式雖然釋放一個(gè)空閑塊時(shí)速度較慢，但分配效率是一切算法中最高的一種。第40頁/共170頁42可變分區(qū)存儲(chǔ)管理的特點(diǎn)（1）作業(yè)一次性的全部裝入到一個(gè)連續(xù)的存儲(chǔ)分區(qū)中。（2）分區(qū)是按照作業(yè)對存儲(chǔ)的需求劃分的，因此在可變分區(qū)管理中，不會(huì)出現(xiàn)內(nèi)部碎片這樣的存儲(chǔ)浪費(fèi)。（3）為了確保作業(yè)能夠在內(nèi)存中移動(dòng)，要由硬件支持，實(shí)行指令地址的動(dòng)態(tài)重定位。第41頁/共170頁43可變分區(qū)存儲(chǔ)管理的缺點(diǎn)（1）仍然沒有解決小內(nèi)存運(yùn)行大作業(yè)的問題。（2）雖然避免了內(nèi)部碎片造成的存儲(chǔ)浪費(fèi)，但有可能出現(xiàn)極小的分區(qū)暫時(shí)分配不出去的情形，引起外部碎片。（3）為了形成大的分區(qū)，可變分區(qū)存儲(chǔ)管理通過移動(dòng)程序來達(dá)到分區(qū)合并的目的，然而程序的移動(dòng)是很花費(fèi)時(shí)間的，增加了系統(tǒng)在這方面的開銷。第42頁/共170頁442.3.6多重分區(qū)可變分區(qū)存儲(chǔ)管理算法是按作業(yè)對存儲(chǔ)的需求分配存儲(chǔ)區(qū)的，因而消除了固定分區(qū)內(nèi)部的剩余碎片，但隨著存儲(chǔ)區(qū)的分配和釋放過程的進(jìn)行，在各個(gè)被分配出去的分區(qū)之間會(huì)存在很多的空閑區(qū)，這就是“外部碎片”。有時(shí)，當(dāng)一個(gè)作業(yè)要裝入運(yùn)行，但分配不到一個(gè)夠用的空閑分區(qū)，盡管這時(shí)內(nèi)存中所有外部碎片的總和遠(yuǎn)大于作業(yè)所申請的空間。如采用“緊湊”技術(shù)重新安排內(nèi)存中各個(gè)作業(yè)的位置，以使零碎的空閑區(qū)集中起來，這是一個(gè)極其耗時(shí)的過程，一般很少采用這種策略。第43頁/共170頁45請求分配u.size分區(qū)檢索空閑分區(qū)鏈（表）找到大于u.size的可用區(qū)否按動(dòng)態(tài)分區(qū)方式進(jìn)行分配修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號(hào)及首地址空閑分區(qū)總和>=u.size進(jìn)行緊湊形成連續(xù)空閑區(qū)修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)無法分配返回否否是是第44頁/共170頁462.3.6多重分區(qū)有些系統(tǒng)采用多重分區(qū)技術(shù)，在作業(yè)的運(yùn)行過程中可以申請附加的分區(qū)，以裝入一個(gè)或多個(gè)子程序。新申請的空閑分區(qū)也無需與作業(yè)的現(xiàn)有分區(qū)相鄰接。采用多重分區(qū)技術(shù)可以提高外部碎片的利用率，也便于多個(gè)作業(yè)共享分區(qū)的代碼和數(shù)據(jù)，這只要在共享的作業(yè)中包含某個(gè)共享的分區(qū)即可。多重分區(qū)系統(tǒng)應(yīng)當(dāng)采用動(dòng)態(tài)重定位技術(shù)，但存儲(chǔ)管理的復(fù)雜性也增加了。為了實(shí)現(xiàn)存儲(chǔ)保護(hù)，在多重分區(qū)系統(tǒng)中要設(shè)置多對界地址寄存器，以使現(xiàn)運(yùn)行作業(yè)對每一個(gè)分區(qū)的訪問都不會(huì)越界。第45頁/共170頁472.4內(nèi)存擴(kuò)充技術(shù)在基本的存儲(chǔ)管理系統(tǒng)中，當(dāng)一個(gè)作業(yè)的程序地址空間大于內(nèi)存可用空間時(shí)，該作業(yè)就不能裝入運(yùn)行；當(dāng)并發(fā)運(yùn)行作業(yè)的程序地址空間總和大于內(nèi)存可用空間時(shí)，多道程序設(shè)計(jì)的實(shí)現(xiàn)就會(huì)碰到很大的困難。內(nèi)存擴(kuò)充技術(shù)就是借助大容量的輔存在邏輯上實(shí)現(xiàn)內(nèi)存的擴(kuò)充，以解決內(nèi)存容量不足的問題。第46頁/共170頁482.4.1覆蓋(overlay)引入：其目標(biāo)是在較小的可用內(nèi)存中運(yùn)行較大的程序。原理：覆蓋技術(shù)就是將一個(gè)大程序按程序的邏輯結(jié)構(gòu)劃分成若干個(gè)程序（或數(shù)據(jù)）段，并將不會(huì)同時(shí)執(zhí)行，從而就不必同時(shí)裝入內(nèi)存的程序段分在一組內(nèi)，該組稱為覆蓋段。這個(gè)覆蓋段可分配到同一個(gè)稱為覆蓋區(qū)的存儲(chǔ)區(qū)域。將程序的必要部分（常用功能）的代碼和數(shù)據(jù)常駐內(nèi)存；可選部分（不常用功能）在其他程序模塊中實(shí)現(xiàn)，平時(shí)存放在外存中（覆蓋文件），在需要用到時(shí)才裝入到內(nèi)存；不存在調(diào)用關(guān)系的模塊不必同時(shí)裝入到內(nèi)存，從而可以相互覆蓋。(即不同時(shí)用的模塊可共用一個(gè)分區(qū))第47頁/共170頁49注：另一種覆蓋方法：(100K)A(20K)占一個(gè)分區(qū)：20K；B(50K)、D(20K)和E(40K)共用一個(gè)分區(qū)：50K；F(30K)和C(30K)共用一個(gè)分區(qū)：30K；第48頁/共170頁50缺點(diǎn)：對用戶不透明，增加了用戶負(fù)擔(dān)。編程時(shí)必須劃分程序模塊和確定程序模塊之間的覆蓋關(guān)系，增加編程復(fù)雜度。從外存裝入覆蓋文件，以時(shí)間延長來換取空間節(jié)省。覆蓋不需要任何來自操作系統(tǒng)的特殊支持，由用戶程序自己控制所以，覆蓋通常限于用在微機(jī)和其他內(nèi)存容量有限的或缺乏對更先進(jìn)技術(shù)的硬件支持的系統(tǒng)中第49頁/共170頁512.4.2交換(swapping)引入：讓單一連續(xù)分區(qū)存儲(chǔ)管理能具有“多道”的效果。中心思想：將作業(yè)信息都存放在輔存上，根據(jù)單一連續(xù)分區(qū)存儲(chǔ)管理的分配策略，每次只讓其中一個(gè)進(jìn)入內(nèi)存投入運(yùn)行，當(dāng)運(yùn)行中提出輸入輸出請求或分配的時(shí)間片用完時(shí)，就把這個(gè)程序從內(nèi)存儲(chǔ)器“換出”到輔存，把輔存里的另一個(gè)作業(yè)“換入”內(nèi)存運(yùn)行。這樣從宏觀上看，系統(tǒng)中同時(shí)就有幾個(gè)作業(yè)處在運(yùn)行之中。為了減少在主存和輔存間傳輸?shù)臄?shù)據(jù)量，可以只將原作業(yè)的一部分保存到輔存中去，只要釋放的主存空間剛好夠裝入下一個(gè)運(yùn)行作業(yè)就行。在以后的適當(dāng)時(shí)間，作業(yè)移出的部分可裝入到原來的存儲(chǔ)區(qū)中繼續(xù)運(yùn)行下去。這種技術(shù)稱之為交換技術(shù)，也叫“滾進(jìn)滾出”第50頁/共170頁52第51頁/共170頁53優(yōu)點(diǎn)：增加并發(fā)運(yùn)行的程序數(shù)目，并且給用戶提供適當(dāng)?shù)捻憫?yīng)時(shí)間；編寫程序時(shí)不影響程序結(jié)構(gòu)缺點(diǎn)：對換入和換出的控制增加處理機(jī)開銷；程序整個(gè)地址空間都進(jìn)行傳送，沒有考慮執(zhí)行過程中地址訪問的統(tǒng)計(jì)特性。交換技術(shù)的優(yōu)缺點(diǎn)第52頁/共170頁54交換與覆蓋的比較與覆蓋技術(shù)相比，交換技術(shù)不要求用戶給出程序段之間的邏輯覆蓋結(jié)構(gòu)。交換發(fā)生在進(jìn)程或作業(yè)之間，而覆蓋發(fā)生在同一進(jìn)程或作業(yè)內(nèi)。覆蓋只能覆蓋那些與覆蓋段無關(guān)的程序段。第53頁/共170頁552.4.3虛擬存儲(chǔ)器在現(xiàn)代的計(jì)算機(jī)系統(tǒng)中，一個(gè)作業(yè)即使不全部裝入主存，也同樣能正確運(yùn)行，因?yàn)椋骸谝粋€(gè)程序中一般都有相當(dāng)數(shù)量的出錯(cuò)處理子程序，在正常的運(yùn)行過程中很少執(zhí)行到這些程序；—程序中一般都含有類似then和else的彼此互斥的部分，在程序的一次執(zhí)行中往往只選擇其中的一條路徑執(zhí)行；—程序中的初始化部分一般只執(zhí)行一次，初始化工作完成后，這些代碼就沒有存放在主存中的必要；第54頁/共170頁562.4.3虛擬存儲(chǔ)器—從運(yùn)行的時(shí)間角度來分析，在一段時(shí)間內(nèi)，作業(yè)一般不會(huì)執(zhí)行到所有程序段的指令和存取絕大部分?jǐn)?shù)據(jù)，它往往相對集中地訪問某些區(qū)域中的指令和數(shù)據(jù)，這就是程序運(yùn)行的“局部性原理”。在主存中可只裝入最近經(jīng)常要訪問的某些區(qū)域的指令和數(shù)據(jù)，剩余部分就暫時(shí)不必裝入，等到以后要訪問到它們時(shí)再調(diào)入內(nèi)存。如果主存較緊張，必要時(shí)可將已不大訪問的信息調(diào)出內(nèi)存，再執(zhí)行調(diào)入操作。這樣，程序運(yùn)行時(shí)所需要的實(shí)際內(nèi)存就可以遠(yuǎn)小于程序的虛擬地址空間。第55頁/共170頁57由于作業(yè)的指令和數(shù)據(jù)可以存放在外存中，用戶的程序就不受實(shí)際內(nèi)存大小的限制，好像計(jì)算機(jī)系統(tǒng)向用戶系統(tǒng)提供了容量極大的“主存”，而這個(gè)大容量的“主存”是靠存儲(chǔ)管理的軟件和硬件通過大容量的輔存作為后援存儲(chǔ)器擴(kuò)充而獲得的，是程序設(shè)計(jì)員感覺到的，而實(shí)際上并不存在的存儲(chǔ)器，故稱虛擬存儲(chǔ)器。采用虛擬存儲(chǔ)器技術(shù)究竟可運(yùn)行多大的程序呢？當(dāng)然也不能無限大，它受到以下兩個(gè)條件的限制。第56頁/共170頁58①指令地址字長的限制。地址字長決定了程序所能訪問的虛擬地址空間的大小，如對于32位字長的地址字可構(gòu)成4GB的虛擬地址空間。②存放程序指令和數(shù)據(jù)的外存儲(chǔ)器的大小，這種外存叫做交換設(shè)備，存放程序指令和數(shù)據(jù)的外存區(qū)域稱為交換區(qū)。采用虛擬存儲(chǔ)管理策略，在作業(yè)運(yùn)行時(shí)就要由地址映像機(jī)構(gòu)將程序的邏輯地址轉(zhuǎn)換成內(nèi)存的物理地址。此外，還要決定將虛擬地址空間中的哪一部分裝入主存，裝入主存的位置以及當(dāng)主存中的空閑區(qū)不夠時(shí)將哪一部分空間的內(nèi)容調(diào)至交換區(qū)中。這些都是虛擬存儲(chǔ)管理中要解決的新的技術(shù)問題。第57頁/共170頁592.5純分頁的存儲(chǔ)管理可變分區(qū)存儲(chǔ)管理：連續(xù)分配存儲(chǔ)空間。分頁式存儲(chǔ)管理：打破了“連續(xù)”的禁錮，把對存儲(chǔ)的管理大大推進(jìn)了一步。分頁式存儲(chǔ)管理是將固定分區(qū)方法與動(dòng)態(tài)重定位技術(shù)結(jié)合在一起的一種存儲(chǔ)管理方案，它需要硬件的支持。第58頁/共170頁602.5.1分頁存儲(chǔ)管理的基本思想作業(yè)的虛擬地址空間劃分成若干長度相等的頁（page），也稱虛頁，每一個(gè)作業(yè)的虛頁都從0開始編號(hào)。主存也劃分成若干與虛頁長度相等的頁架（frame），也稱頁框或?qū)嶍?，主存的頁架也?開始編號(hào)。程序裝入時(shí)，每一個(gè)虛頁裝到主存中的一個(gè)頁架中，這些頁架可以是不連續(xù)的。需要CPU的硬件支持。第59頁/共170頁61例：第60頁/共170頁62

把用戶程序按邏輯頁劃分成大小相等的部分，稱為頁。從0開始編制頁號(hào)，頁內(nèi)地址是相對于0編址邏輯地址頁號(hào)頁內(nèi)地址用戶程序劃分例：頁的大小為4K相對地址5188，對應(yīng)數(shù)對（1，1092）；相對地址9200，對應(yīng)數(shù)對（2，1008）。第61頁/共170頁632.5.2地址變換

在分頁系統(tǒng)中，頁的大小都是2的整數(shù)次冪，這樣分頁地址中的地址結(jié)構(gòu)如下：

頁號(hào)P位移量D3112110

虛擬地址字的頁內(nèi)偏移部分占據(jù)低n個(gè)二進(jìn)制位，使2n剛好等于頁的大小，這樣安排便于硬件直接截取高位部分的頁號(hào)和低位部分的頁內(nèi)偏移值。第62頁/共170頁64例：某系統(tǒng)的地址結(jié)構(gòu)長為16位，相對地址3000的二進(jìn)制位表示如下：00011101110100001514131211109876543210塊尺寸1KB，對應(yīng)數(shù)對（2，952）；塊尺寸256字節(jié)，對應(yīng)數(shù)對（11，184）。第63頁/共170頁65程序的虛擬地址空間是連續(xù)的，但程序的虛頁可以分配到主存中不連續(xù)的空閑頁架中；故分頁系統(tǒng)需要在主存中開辟一個(gè)頁表區(qū)域來建立每一個(gè)作業(yè)的虛頁號(hào)到內(nèi)存的頁架號(hào)之間的映射關(guān)系。系統(tǒng)還需要建立一個(gè)總頁表來記錄各個(gè)作業(yè)頁表的起始地址和長度，并將當(dāng)前運(yùn)行進(jìn)程的頁表起始地址和長度存放在頁表控制寄存器中。第64頁/共170頁66每一個(gè)作業(yè)的頁表空間可以是連續(xù)的，也可以是不連續(xù)的，但連續(xù)的頁表空間管理方便，存取速度也快。連續(xù)的頁表要分配的空間本身又相當(dāng)于一個(gè)小分區(qū)，故可采用前面討論的分區(qū)分配和釋放算法。連續(xù)的頁表空間同時(shí)也帶來了頁表分區(qū)之間的存儲(chǔ)區(qū)碎片問題，但由于一個(gè)作業(yè)的頁表空間比作業(yè)本身的程序和數(shù)據(jù)空間小得多，故這個(gè)問題相對來說并不嚴(yán)重第65頁/共170頁67基本的地址變換機(jī)構(gòu)頁表保存在內(nèi)存中；硬件設(shè)置一個(gè)專用寄存器：“頁表寄存器”每當(dāng)進(jìn)程調(diào)度時(shí)，把調(diào)度到進(jìn)程的頁表起始地址和頁表長度（即頁表表項(xiàng)的數(shù)目）放入寄存器中。第66頁/共170頁68地址轉(zhuǎn)換過程1）由硬件自動(dòng)將虛擬地址字分成虛頁號(hào)和頁內(nèi)偏移兩部分；2）由頁表控制寄存器中頁表起始地址和虛擬地址字中的虛頁號(hào)查找頁表，對應(yīng)虛頁號(hào)的頁表表項(xiàng)地址為：頁表起始地址+虛頁號(hào)*頁表表項(xiàng)長度；3）將頁表中取出的頁架號(hào)和虛擬地址字中的頁內(nèi)偏移值裝入地址寄存器，根據(jù)地址寄存器中的地址值訪問主存。頁表控制寄存器中的“長度”起到存儲(chǔ)保護(hù)的作用，每個(gè)相對地址中的頁號(hào)都不能大于該長度，否則出錯(cuò)。第67頁/共170頁69第68頁/共170頁70例

若在分頁式存儲(chǔ)管理中，建立了某個(gè)作業(yè)的頁，塊對應(yīng)關(guān)系為：第0頁放在第0塊，第1頁放在第3塊，第2頁放在第1塊，如下所示。已知塊的尺寸為1KB/塊。求相對地址1023、1024、3000、所對應(yīng)的絕對地址。虛頁號(hào)頁架號(hào)001321解：1023－>10231024－>30723000－>1976第69頁/共170頁71缺點(diǎn)（1）頁表放在內(nèi)存，增加了系統(tǒng)在存儲(chǔ)上的開銷；（2）降低了CPU的訪問速度。因?yàn)槊看螌δ骋坏刂返脑L問，首先要訪問內(nèi)存中的頁表，形成絕對地址后，才能進(jìn)行所需要的真正訪問。第70頁/共170頁722.5.3具有快表的地址變換機(jī)構(gòu)

考慮到大多數(shù)程序在一次調(diào)度運(yùn)行時(shí)，傾向于在少數(shù)頁面中進(jìn)行頻繁的訪問（這被稱為程序的“局部性”原理），因此實(shí)際系統(tǒng)中的做法是采用內(nèi)存頁表與快速寄存器組相結(jié)合的解決方案，并且利用程序局部性原理，只用極少數(shù)幾個(gè)快速寄存器來構(gòu)成快速寄存器組，這時(shí)把快速寄存器組單獨(dú)起名為“快表”，主存中的頁表有時(shí)也稱為慢表。第71頁/共170頁73

快表由CPU中的高速cache或聯(lián)想寄存器構(gòu)成。聯(lián)想寄存器是一種按內(nèi)容進(jìn)行并行查找的一組快速寄存器，當(dāng)在其輸入端有一個(gè)輸入值頁號(hào)p時(shí)，在聯(lián)想寄存器中存放頁號(hào)為p的那一項(xiàng)就立即選中，并輸出其變換值頁架號(hào)b。由于訪問聯(lián)想寄存器比訪問主存快得多，故極大地提高了地址變換速度。第72頁/共170頁74地址的映射快表中存放的是頁表內(nèi)容的一部分。在進(jìn)行地址變換時(shí)，變換機(jī)構(gòu)根據(jù)虛擬地址字中的頁號(hào)同時(shí)查找快表和慢表;一旦在快表中查到虛頁號(hào)，就用輸出的頁架號(hào)和虛擬地址字中的偏移地址構(gòu)造主存物理地址；否則，就用慢表中查到的頁架號(hào)構(gòu)造主存物理地址，同時(shí)還用慢表的該表項(xiàng)更新快表，這就可能需要按某一算法淘汰快表中某一表項(xiàng)，以便下次再訪問該頁的過程能在快表中進(jìn)行。第73頁/共170頁75p’頁表地址越界

l比較P>=1pp’...快表

b+頁號(hào)p頁內(nèi)地址dP’d物理地址頁表地址寄存器頁表長度寄存器邏輯地址第74頁/共170頁76由于成本關(guān)系，快表不可能做的很大，通常只存放16－512個(gè)頁表項(xiàng)，這對于中、小型作業(yè)來說，已有可能把全部頁表項(xiàng)放在快表中，但對于大型作業(yè)，則只能將其一部分頁表項(xiàng)放入其中。據(jù)統(tǒng)計(jì)，快表中如含有8個(gè)表項(xiàng)時(shí)，平均命中率為85%，含有16個(gè)表項(xiàng)時(shí)，平均命中率為97%，因此在配備聯(lián)想寄存器的頁式管理系統(tǒng)中，多一級地址變換不會(huì)明顯減慢程序的執(zhí)行速度。第75頁/共170頁772.5.4空閑內(nèi)存頁的管理在頁式管理系統(tǒng)中，需要一張表記錄主存中每個(gè)頁的使用情況和當(dāng)前空閑頁的總數(shù)。由于主存頁總數(shù)很多，且頁的大小相等，故可用位圖描述各頁的狀態(tài)。在位圖中用一個(gè)二進(jìn)制位對應(yīng)于主存中的一個(gè)頁，該位為0表示對應(yīng)頁空閑，為1表示對應(yīng)頁已分配。位圖中每一個(gè)字節(jié)可表示8頁的狀態(tài)，如設(shè)頁面大小為4KB，對于32MB的主存空間，只需要1KB大小的位表第76頁/共170頁78位圖空閑塊總數(shù)：60111100100101111位號(hào)

01234567字節(jié)號(hào)01頁框號(hào)＝字節(jié)號(hào)×8＋位號(hào)字節(jié)號(hào)＝頁框號(hào)/8；位號(hào)＝頁框號(hào)％8第77頁/共170頁79在分配空閑頁時(shí)，可一次取出位圖中的一個(gè)字，如該字內(nèi)容非全1，即表示其中必對應(yīng)有空閑頁，接下來就可確定空閑頁的位置。為了提高在位圖上檢索空閑頁的速度，可在表頭增設(shè)一個(gè)起始查找位置指針，位圖中在起始查找指針之前的所有字（或字節(jié)）都不含有空閑位。另外，設(shè)置一個(gè)循環(huán)查找指針的算法也不錯(cuò)。釋放算法很簡單，只要在位圖中的對應(yīng)位上置0即可，但如設(shè)置起始查找指針，則可能要修改指針值。也可使用順序或鏈接結(jié)構(gòu)的棧來管理空閑頁，棧中每一個(gè)單元指示一個(gè)空閑頁。采用這種方法所需的存儲(chǔ)空間比位圖大許多，但分配空閑頁時(shí)速度快很多。第78頁/共170頁80分頁式存儲(chǔ)管理的特點(diǎn)（1）內(nèi)存事先被劃分成相等尺寸的頁框，它是進(jìn)行存儲(chǔ)分配的單位；（2）用戶作業(yè)的相對地址空間按照頁框的尺寸劃分成頁。（3）由于相對地址空間中的頁可以進(jìn)入內(nèi)存中的任何一個(gè)空閑頁框，并且分頁式存儲(chǔ)管理實(shí)行的是動(dòng)態(tài)重定位，因此它打破了一個(gè)作業(yè)必須占據(jù)連續(xù)存儲(chǔ)空間的限制，作業(yè)在不連續(xù)的存儲(chǔ)區(qū)里，也能夠得到正確的運(yùn)行。第79頁/共170頁81（1）平均每個(gè)作業(yè)要浪費(fèi)半頁大小的存儲(chǔ)頁。（2）作業(yè)雖然可以不占據(jù)連續(xù)的存儲(chǔ)區(qū)，但是每次仍然要求一次全部進(jìn)入內(nèi)存。因此，如果作業(yè)很大，其存儲(chǔ)需求大于內(nèi)存，那么仍然存在小內(nèi)存不能運(yùn)行大作業(yè)的問題。缺點(diǎn)第80頁/共170頁82（補(bǔ)充）兩級和多級頁表現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。在這樣的環(huán)境下，頁表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。例如，對于一個(gè)具有32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4KB即212B，則在每個(gè)進(jìn)程頁表中的頁表項(xiàng)可達(dá)1兆個(gè)之多。又因?yàn)槊總€(gè)頁表項(xiàng)占用一個(gè)字節(jié)，故每個(gè)進(jìn)程僅僅其頁表就要占用1MB的內(nèi)存空間，而且還要求是連續(xù)的。第81頁/共170頁83（補(bǔ)充）兩級和多級頁表可以采用這樣兩個(gè)方法來解決這一問題：①采用離散分配方式來解決難以找到一塊連續(xù)的大內(nèi)存空間的問題：②只將當(dāng)前需要的部分頁表項(xiàng)調(diào)入內(nèi)存，其余的頁表項(xiàng)仍駐留在磁盤上，需要時(shí)再調(diào)入。第82頁/共170頁841.兩級頁表(Two-LevelPageTable)

對于要求連續(xù)的內(nèi)存空間來存放頁表的問題，可利用將頁表進(jìn)行分頁，并離散的將各個(gè)頁面分別存放在不同的物理塊中的辦法來加以解決，同樣也要為離散分配的頁表再建立一張頁表，稱為外層頁表（OuterPageTable），在每個(gè)頁表項(xiàng)中記錄了頁表頁面的物理塊號(hào)。第83頁/共170頁85邏輯地址結(jié)構(gòu)可描述如下：第84頁/共170頁86兩級頁表結(jié)構(gòu)第85頁/共170頁87第86頁/共170頁88

上述對頁表施行離散分配的方法，雖然解決了對大頁表無需大片存儲(chǔ)空間的問題，但并未解決用較少的內(nèi)存空間去存放大頁表的問題。換言之，只用離散分配空間的辦法并未減少頁表所占用的內(nèi)存空間。解決方法是把當(dāng)前需要的一批頁表項(xiàng)調(diào)入內(nèi)存，以后再根據(jù)需要陸續(xù)調(diào)入。在采用兩級頁表結(jié)構(gòu)的情況下，對于正在運(yùn)行的進(jìn)程，必須將其外層頁表調(diào)入內(nèi)存，而對頁表則只需調(diào)入一頁或幾頁。第87頁/共170頁892.多級頁表對于32位的機(jī)器，采用兩級頁表結(jié)構(gòu)是合適的；但對于64位的機(jī)器，如果頁面大小仍采用4KB即212B，那么還剩下52位，假定仍按物理塊的大小(212位)來劃分頁表，則將余下的42位用于外層頁號(hào)。此時(shí)在外層頁表中可能有4096G個(gè)頁表項(xiàng)，要占用16384GB的連續(xù)內(nèi)存空間。必須采用多級頁表，將外層頁表再進(jìn)行分頁，也是將各分頁離散地裝入到不相鄰接的物理塊中，再利用第2級的外層頁表來映射它們之間的關(guān)系。對于64位的計(jì)算機(jī)，如果要求它能支持2６４(=1844744TB)規(guī)模的物理存儲(chǔ)空間，則即使是采用三級頁表結(jié)構(gòu)也是難以辦到的；而在當(dāng)前的實(shí)際應(yīng)用中也無此必要。第88頁/共170頁902.6請求分頁系統(tǒng)虛擬存儲(chǔ)器的引入1.常規(guī)存儲(chǔ)器管理方式的特征一次性。作業(yè)在運(yùn)行前一次性的全部裝入內(nèi)存。(2)

駐留性。作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直到作業(yè)運(yùn)行結(jié)束。第89頁/共170頁912.6.1請求分頁的基本原理其基本思想是對于每一個(gè)運(yùn)行作業(yè)，只裝入當(dāng)前運(yùn)行需要的一部分頁面集合，該集合又稱“工作集”。當(dāng)作業(yè)運(yùn)行時(shí)需要訪問其他不在主存中的虛頁時(shí)，硬件產(chǎn)生“缺頁中斷”，如主存資源緊張，可在原先裝入主存的頁面中選擇一個(gè)或多個(gè)頁，將其換出到輔存中，再把所需的頁調(diào)入主存。請求式分頁系統(tǒng)將主存和輔存這兩級存儲(chǔ)器融合成邏輯上統(tǒng)一的整體，故在這種系統(tǒng)中能運(yùn)行比可用主存更大的作業(yè)或在相同容量的主存中并發(fā)運(yùn)行更多的作業(yè)第90頁/共170頁92與分頁式存儲(chǔ)管理的比較相同點(diǎn)：(1)內(nèi)存分成頁框；(2)作業(yè)虛地址空間分虛頁；(3)任一頁可裝入任一空閑頁框；不同點(diǎn)：

(1)作業(yè)全部進(jìn)入外存，運(yùn)行時(shí)，并不把整個(gè)作業(yè)全部裝入，而是只裝入目前要用的若干頁；

(2)運(yùn)行過程中，虛地址轉(zhuǎn)換為數(shù)對（頁號(hào)，頁內(nèi)位移），根據(jù)頁號(hào)查頁表時(shí)，如果該頁在內(nèi)存，那么有真實(shí)的頁框號(hào)與之對應(yīng)，運(yùn)行就能夠進(jìn)行下去。第91頁/共170頁93與分頁式存儲(chǔ)管理的比較（續(xù)）

如果該頁不在內(nèi)存，那么無真實(shí)塊號(hào)與之對應(yīng)，表明“缺頁”，運(yùn)行無法繼續(xù)下去，此時(shí)，就要根據(jù)該頁的地址把它從外存調(diào)入，以保證程序運(yùn)行。請求分頁式：當(dāng)程序運(yùn)行中需要某一頁時(shí)，再把它從輔存調(diào)入內(nèi)存。第92頁/共170頁94請求分頁機(jī)構(gòu)在請求分頁系統(tǒng)中控制這種能在主存和輔存間自動(dòng)交換頁面、對用戶透明的機(jī)構(gòu)稱為虛擬存儲(chǔ)系統(tǒng)的請求分頁機(jī)構(gòu)，該機(jī)構(gòu)的主要功能如下。①執(zhí)行地址變換操作，將程序虛擬地址轉(zhuǎn)化為物理地址，這部分工作由硬件實(shí)施。②缺頁時(shí)自動(dòng)觸發(fā)頁面中斷機(jī)構(gòu)。缺頁中斷與普通的外設(shè)中斷不同，一般中斷只能在一條完整的指令執(zhí)行結(jié)束后才能得到響應(yīng)，而缺頁中斷可以發(fā)生在一條指令的執(zhí)行中間，如果一條指令要訪問多個(gè)頁面（如對于間接訪問指令和數(shù)據(jù)傳送指令），還能引起多個(gè)缺頁中斷。③缺頁中斷處理子程序，其中包括頁面的調(diào)出和調(diào)入，這部分工作在軟件控制下完成第93頁/共170頁95在請求分頁系統(tǒng)中，由于作業(yè)的虛頁可能駐留在主存中，也可能駐留在輔存中。因此在頁表中要擴(kuò)充表項(xiàng)的內(nèi)容，使之包含輔存地址，以便在發(fā)生缺頁時(shí)請求分頁機(jī)構(gòu)可以將輔存中的虛頁調(diào)入主存。這樣，每一個(gè)頁表項(xiàng)結(jié)構(gòu)為：虛頁號(hào)、內(nèi)存頁架號(hào)、輔存地址和狀態(tài)。其中狀態(tài)字段含有該頁當(dāng)前是在主存還是在輔存的標(biāo)志。此外，在該字段中還可包括訪問位和修改位等地址變換第94頁/共170頁96頁表機(jī)制頁號(hào)物理塊號(hào)狀態(tài)位P訪問字段A修改位M外存地址（1）狀態(tài)位P：用于指示該頁是否已調(diào)入內(nèi)存。（2）訪問字段A：用于記錄本頁再一段時(shí)間內(nèi)被訪問的次數(shù)，或記錄本頁最近已有多長時(shí)間未被訪問，供選擇換出頁面時(shí)參考。（3）修改位M：表示該頁在調(diào)入內(nèi)存后是否被修改過。（4）外存地址：用于指出該頁在外存的地址。第95頁/共170頁97缺頁中斷機(jī)構(gòu)在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號(hào)后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，將該頁調(diào)入內(nèi)存，使作業(yè)繼續(xù)運(yùn)行下去。如果內(nèi)存中有空閑頁框，則分配一頁，將新調(diào)入頁裝入內(nèi)存，并修改頁表中相應(yīng)頁表項(xiàng)目的駐留位及相應(yīng)的內(nèi)存頁框號(hào)。若此時(shí)內(nèi)存中沒有空閑頁框，則要淘汰某頁，若該頁在內(nèi)存期間被修改過，則要將其寫回外存。第96頁/共170頁98CPU頁表始址長度頁號(hào)狀態(tài)修改幀號(hào)輔存0111215100－22200－34310545…頁表控制寄存器內(nèi)存<越界中斷+頁號(hào)頁內(nèi)位移邏輯地址

頁表012351261471626……快表幀號(hào)物理地址頁內(nèi)位移缺頁異常地址變換機(jī)構(gòu)第97頁/共170頁99開始頁號(hào)>頁表長度檢索快表？命中訪問頁表頁在內(nèi)存？修改快表修改訪問位和修改位形成物理地址地址變換結(jié)束地址越界保留CPU現(xiàn)場？內(nèi)存滿選擇一頁換出OS命令CPU從外存讀缺頁啟動(dòng)I/O硬件缺頁中斷處理是是是是否否否否該頁是否修改過？從外存找到缺頁將該頁寫回外存將一頁從外存換入內(nèi)存修改頁表第98頁/共170頁1002.6.2頁面淘汰頁面淘汰問題（頁面置換）：要從輔存上把需要的頁面調(diào)入內(nèi)存，但內(nèi)存中已沒有空閑頁框可供分配使用，那么就必須從內(nèi)存中選擇一頁，然后把它調(diào)出內(nèi)存，以便為即將調(diào)入的頁面讓出塊空間。頁面置換是由缺頁中斷引起的，但是缺頁中斷不一定都引起頁面置換。第99頁/共170頁101頁淘汰在內(nèi)存中選中了一個(gè)淘汰的頁面，如果該頁面在內(nèi)存時(shí)未被修改過，那么就可以直接用調(diào)入的頁面將其覆蓋掉；如果該頁面在內(nèi)存時(shí)被修改過，那么就必須把它寫回到磁盤。以便更新該頁在輔存上的副本。一個(gè)頁面的內(nèi)容在內(nèi)存時(shí)是否被修改過，這樣的信息可以通過頁表表目反映出來。第100頁/共170頁102“抖動(dòng)”或“顛簸”現(xiàn)象抖動(dòng)－進(jìn)程塊頻繁的換入換出當(dāng)操作系統(tǒng)取進(jìn)一頁時(shí)，它必須扔出一頁。如果一塊正好在將要被用到之前扔出，操作系統(tǒng)又不得不幾乎立即把它取回來，太多的這類操作會(huì)導(dǎo)致“系統(tǒng)抖動(dòng)”，處理器的大多數(shù)時(shí)間都用于交換頁，而不是執(zhí)行指令。改進(jìn)抖動(dòng)的許多復(fù)雜但有效的算法，從本質(zhì)上看是，操作系統(tǒng)試圖根據(jù)最近的歷史來猜測在不遠(yuǎn)的將來最可能用到的頁。第101頁/共170頁103頁面淘汰算法功能：需要調(diào)入頁面時(shí)，選擇內(nèi)存中哪個(gè)物理頁面被置換。目標(biāo)：把未來不再使用的或短期內(nèi)較少使用的頁面調(diào)出，通常只能在局部性原理指導(dǎo)下依據(jù)過去的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行預(yù)測。第102頁/共170頁104頁面走向一個(gè)程序執(zhí)行過程中頁面的變化序列稱為“頁面走向”。Load1#,1120Add1#,2410Store1#,1124200030001000第0頁第1頁第2頁01KB2KB3KB100104108112011242410虛地址頁面走向100（0，100）01120（1，96）1104（0，104）02410（2，354）2108（0，108）01124（1，100）1第103頁/共170頁105缺頁中斷率

假定一個(gè)作業(yè)運(yùn)行的頁面走向中涉及到的頁面總數(shù)為A，其中有F次缺頁，必須通過缺頁中斷把它們調(diào)入內(nèi)存。我們定義：

f＝F/A

稱f為“缺頁中斷率”第104頁/共170頁1061.最佳(Optimal)置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時(shí)間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。第105頁/共170頁107

假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁面號(hào)引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

進(jìn)程運(yùn)行時(shí)，先將7，0，1三個(gè)頁面裝入內(nèi)存。以后，當(dāng)進(jìn)程要訪問頁面2時(shí)，將會(huì)產(chǎn)生缺頁中斷。此時(shí)OS根據(jù)最佳置換算法，將選擇頁面7予以淘汰。第106頁/共170頁1082.先進(jìn)先出(FIFO)頁面置換算法

選擇建立最早的頁面被置換?？梢酝ㄟ^鏈表來表示各頁的建立時(shí)間先后。性能較差。較早調(diào)入的頁往往是經(jīng)常被訪問的頁，這些頁在FIFO算法下被反復(fù)調(diào)入和調(diào)出。并且有Belady現(xiàn)象。第107頁/共170頁109舉例：123412512345123412555344123412225331234111255×××××××××頁面走向3個(gè)內(nèi)存塊缺頁計(jì)數(shù)缺頁中斷率：f＝9/12＝75％FIFO算法著眼點(diǎn)：認(rèn)為隨時(shí)間推移，在內(nèi)存中呆得最長得頁面，被訪問得可能性最小。第108頁/共170頁110如果在內(nèi)存中分配4個(gè)頁面，則缺頁情況如下：12次訪問中有缺頁10次；第109頁/共170頁1112.最近最少使用(LRU)置換算法

最近最久未使用算法的著眼點(diǎn)是在要進(jìn)行頁面淘汰時(shí)，檢查這些淘汰對象的被訪問時(shí)間，總是把最長時(shí)間未被訪問過的頁面淘汰出去。選擇內(nèi)存中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳算法。但由于需要記錄頁面使用時(shí)間的先后關(guān)系，硬件開銷太大。該算法賦予每個(gè)頁面一個(gè)訪問字段，用來記錄一個(gè)頁面自上次被訪問以來所經(jīng)歷的時(shí)間t，當(dāng)必須淘汰一個(gè)頁面時(shí)，選擇現(xiàn)有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰。第110頁/共170頁112舉例：123412512345123412512345123412512341234125123××××××××××頁面走向3個(gè)內(nèi)存塊缺頁計(jì)數(shù)缺頁中斷率：f＝10/12＝83％第111頁/共170頁113可以設(shè)置一個(gè)從中間可以出隊(duì)的非嚴(yán)格意義上的隊(duì)列，隊(duì)列中的每一個(gè)單元對應(yīng)于一個(gè)內(nèi)存頁，每次訪問一個(gè)頁面時(shí)將對應(yīng)單元從隊(duì)列中抽出，重新排到隊(duì)尾去，淘汰的頁從隊(duì)列頭取。這樣，經(jīng)常要訪問的頁總是排在靠近隊(duì)列的尾部，而排在隊(duì)首位置上的頁就是最長時(shí)間沒有被訪問過的頁。第112頁/共170頁114假定現(xiàn)有一進(jìn)程所訪問的頁面的頁面號(hào)序列為：4，7，0，7，1，0，1，2，1，2，6第113頁/共170頁115實(shí)現(xiàn)該算法的主要困難是如果每執(zhí)行一條訪問主存的指令時(shí)都要執(zhí)行隊(duì)列的操作，并且該操作是用軟件實(shí)現(xiàn)的話，其時(shí)間開銷是不可忍受的。減少算法時(shí)間復(fù)雜性的方法之一是用硬件實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)和操作，方法之二是不必在每一條訪問內(nèi)存指令都執(zhí)行隊(duì)列操作，可以每過一個(gè)時(shí)間間隔（如時(shí)鐘中斷）執(zhí)行一次。第114頁/共170頁116另一種全部用硬件實(shí)現(xiàn)的LRU算法是對于n個(gè)頁面設(shè)置一個(gè)n*n的矩陣，矩陣初始時(shí)全為0。當(dāng)k頁被訪問時(shí)，硬件置k行的所有位為1，再置k列的所有位為0。任何時(shí)刻，二進(jìn)制值為最小的一行所對應(yīng)的頁是最近最久不用的頁。圖2-15為含有4個(gè)頁面，訪問序列是0123210323的情況下，每訪問一頁后矩陣的狀態(tài)第115頁/共170頁117訪問序列是0123210323第116頁/共170頁1184.最近未使用淘汰算法NUR（NotUsedRecently）是一種低開銷的近似于LRU的淘汰算法。其主要思想是淘汰最近一段時(shí)間內(nèi)未曾訪問過的某一頁面。該算法的一個(gè)實(shí)施不僅能考慮最近未曾訪問過的頁，還能優(yōu)先挑選頁面數(shù)據(jù)未曾修改過的頁，這樣可減少將淘汰頁寫回輔存的開銷。如采用這種算法，要為每一項(xiàng)增設(shè)兩個(gè)硬件位——訪問位和修改位。當(dāng)該頁未訪問過或沒修改過時(shí)對應(yīng)位為0，反之為1。訪問位和修改位不一定要設(shè)在頁表中。初始時(shí)所有頁的訪問位和修改位都清0。當(dāng)訪問某頁時(shí)，該頁的訪問位置1，當(dāng)某頁的數(shù)據(jù)被修改后，將該頁的訪問位和修改位都置1。第117頁/共170頁119系統(tǒng)將主存中各個(gè)使用頁組織成一個(gè)循環(huán)隊(duì)列，并設(shè)置一個(gè)循環(huán)檢測指針。當(dāng)需要淘汰一頁時(shí)，從指針指向的頁開始，順次考察各頁的使用情況，如其訪問位為1，則將該位清0；如訪問位為0，但修改位為1，則將修改位置0（還應(yīng)當(dāng)更新輔存對應(yīng)頁）；不斷重復(fù)這個(gè)過程，直到找到訪問位和修改位都為0的頁，將其作為淘汰頁。按照這個(gè)算法，最新讀過的頁在第一輪的循環(huán)檢測中不會(huì)被選中，最近寫過的頁在第一、二輪循環(huán)檢測中不會(huì)被選中，這樣不僅實(shí)現(xiàn)了NUR算法，而且給予修改過的頁兩次機(jī)會(huì)第118頁/共170頁120NUR算法的另一種實(shí)現(xiàn)是不在檢測時(shí)清0，而是系統(tǒng)每過一個(gè)適當(dāng)?shù)臅r(shí)間，將所有頁的訪問位置0。這樣在兩次清0之前，內(nèi)存中各頁的使用狀態(tài)可能有4種（即序號(hào)訪問位修改位）：序號(hào)訪問位修改位100201310411第119頁/共170頁1211類(A=0,M=0):表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。

2類(A=0,M=1)：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。

3類(A=1,M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問。

4類(A=1,M=1):最近已被訪問且被修改，該頁可能再被訪問。第120頁/共170頁122對于采用同一種淘汰算法，影響系統(tǒng)缺頁中斷率的主要因素是分配給一個(gè)作業(yè)的頁面數(shù)目。雖然在主存中運(yùn)行的作業(yè)數(shù)越多，每個(gè)作業(yè)分配到的頁架越多，系統(tǒng)的運(yùn)行性能就越好但內(nèi)存并不總是充足有余的廉價(jià)資源。實(shí)踐證明，工作集中頁面少于某一個(gè)數(shù)時(shí)，作業(yè)的缺頁中斷次數(shù)會(huì)急劇增加，即會(huì)發(fā)生頁面抖動(dòng)現(xiàn)象；而高于這個(gè)數(shù)，作業(yè)的缺頁中斷次數(shù)不會(huì)明顯減少，這個(gè)頁面數(shù)范圍稱為頁面的工作集。第121頁/共170頁123工作集不僅與作業(yè)的特征，如程序大小、結(jié)構(gòu)、訪問數(shù)據(jù)的規(guī)律有關(guān)，也與作業(yè)運(yùn)行的時(shí)間段有關(guān)。系統(tǒng)可根據(jù)一個(gè)進(jìn)程的缺頁中斷率估計(jì)出合適的工作集大小，并根據(jù)運(yùn)行情況給予調(diào)整。如在某一段時(shí)間內(nèi)，系統(tǒng)中很多作業(yè)所能分配到的頁面數(shù)小于工作集時(shí)，應(yīng)當(dāng)掛起某些作業(yè)，將其所占用的主存空間分配給優(yōu)先級高的作業(yè)，以避免抖動(dòng)現(xiàn)象的發(fā)生第122頁/共170頁124按淘汰頁面的選擇范圍分，有兩種淘汰策略：一種是淘汰的頁從整個(gè)主存也即所有的作業(yè)所占用的頁面中選擇，這稱為全局淘汰算法；另一種是從本作業(yè)所占用的頁面中選擇，稱為局部淘汰法。在討論頁面淘汰算法時(shí)，還未曾考慮淘汰頁的選擇范圍，淘汰頁的選擇范圍對選擇不同的淘汰算法和硬件的配置影響很大。全局算法一般工作得比局部算法好，因?yàn)檫@種算法可以在很多進(jìn)程之間動(dòng)態(tài)地分配頁面，但支持全局算法的硬件開銷較大，算法運(yùn)行的時(shí)間也較大。有些算法，如采用n*n位矩陣的NUR算法，就不大可能在采用全局淘汰策略時(shí)被采用第123頁/共170頁125（補(bǔ)充）內(nèi)存分配策略和分配算法物理塊的分配策略

在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時(shí)，也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。

1)固定分配局部置換(FixedAllocation,LocalReplacement)2)可變分配全局置換(VariableAllocation,GlobalReplacement)

3)可變分配局部置換(VariableAllocation,LocalReplacemen第124頁/共170頁1261)固定分配局部置換(FixedAllocation,LocalReplacement)

這是指基于進(jìn)程的類型（交互型或批處理型等），或根據(jù)程序員、程序管理員的建議，為每個(gè)進(jìn)程分配一定數(shù)目的物理頁架，在整個(gè)運(yùn)行期間都不再改變。采用該策略時(shí)，如果進(jìn)程在運(yùn)行中發(fā)現(xiàn)缺頁，則只能從該進(jìn)程在內(nèi)存的n個(gè)頁面中選出一頁換出，然后再調(diào)入一頁，以保證分配給該進(jìn)程的內(nèi)存空間不變。第125頁/共170頁1272)可變分配全局置換(VariableAllocation,GlobalReplacement)

在采用這種策略時(shí)，先為系統(tǒng)中的每個(gè)進(jìn)程分配一定數(shù)目的物理頁架，而OS自身也保持一個(gè)空閑頁架隊(duì)列。當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁時(shí)，由系統(tǒng)從空閑頁架隊(duì)列中，取出一個(gè)頁架分配給該進(jìn)程，并將欲調(diào)入的（缺）頁裝入其中。這樣，凡產(chǎn)生缺頁（中斷）的進(jìn)程，都將獲得新的頁架。僅當(dāng)空閑頁架隊(duì)列中的頁架用完時(shí)，OS才能從內(nèi)存中選擇一頁調(diào)出，該頁可能是系統(tǒng)中任一進(jìn)程的頁，這樣自然又會(huì)使那個(gè)進(jìn)程的頁架減少，進(jìn)而使其缺頁率增加。第126頁/共170頁1283)可變分配局部置換(VariableAllocation,LocalReplacemen)

它同樣是基于進(jìn)程的類型或根據(jù)程序員的要求，為每個(gè)進(jìn)程分配一定數(shù)目的頁架，但當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁時(shí)，只允許從該進(jìn)程在內(nèi)存的頁面中選出一頁換出，這樣就不會(huì)影響其它進(jìn)程的運(yùn)行。如果進(jìn)程在運(yùn)行中頻繁發(fā)生缺頁中斷，則系統(tǒng)須再為該進(jìn)程分配若干附加的頁架，直至該進(jìn)程的缺頁率減少到適當(dāng)程度為止；反之，若一個(gè)進(jìn)程在運(yùn)行過程中的缺頁中斷率特別低，則此時(shí)可適當(dāng)減少分配給該進(jìn)程的頁架數(shù)，但不應(yīng)引起其缺頁率的明顯增加。第127頁/共170頁129（補(bǔ)充）調(diào)頁策略1.何時(shí)調(diào)入頁面預(yù)調(diào)頁策略如果進(jìn)程的許多頁是存放在外存的一個(gè)連續(xù)區(qū)域中，則一次調(diào)入若干個(gè)相鄰的頁，會(huì)比一次調(diào)入一頁更高效些?？刹捎靡环N以預(yù)測為基礎(chǔ)的預(yù)調(diào)頁策略，將那些預(yù)計(jì)在不久以后便會(huì)被訪問的頁面，預(yù)先調(diào)入內(nèi)存。2)請求調(diào)頁策略

當(dāng)進(jìn)程在運(yùn)行中需要訪問某部分程序和數(shù)據(jù)時(shí)，若發(fā)現(xiàn)其所在的頁面不在內(nèi)存，便立即提出請求，由OS將其所需頁面調(diào)入內(nèi)存。第128頁/共170頁1302.從何處調(diào)入頁面

在請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對換頁面的對換區(qū)。通常，由于對換區(qū)是采用連續(xù)分配方式，而文件區(qū)是采用離散分配方式，故對換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁請求時(shí)，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，可分成如下三種情況：

(1)

系統(tǒng)擁有足夠的對換區(qū)空間，這時(shí)可以全部從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。為此，在進(jìn)程運(yùn)行前，便須將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對換區(qū)。第129頁/共170頁131(2)

系統(tǒng)缺少足夠的對換區(qū)空間，這時(shí)凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁面時(shí)，由于它們未被修改而不必再將它們換出，以后再調(diào)入時(shí)，仍從文件區(qū)直接調(diào)入。但對于那些可能被修改的部分，在將它們換出時(shí)，便須調(diào)到對換區(qū)，以后需要時(shí)，再從對換區(qū)調(diào)入。

(3)

UNIX方式。由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁面，都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)運(yùn)行過但又被換出的頁面，由于是被放在對換區(qū)，因此在下次調(diào)入時(shí)，應(yīng)從對換區(qū)調(diào)入。由于UNIX系統(tǒng)允許頁面共享，因此，某進(jìn)程所請求的頁面有可能已被其它進(jìn)程調(diào)入內(nèi)存，此時(shí)也就無須再從對換區(qū)調(diào)入。第130頁/共170頁132補(bǔ)充：頁式管理方式中有效訪問時(shí)間的計(jì)算方法有效訪問時(shí)間（EffectiveAccessTime,EAT），是指給定邏輯地址找到內(nèi)存中對應(yīng)物理地址單元中數(shù)據(jù)所花的總時(shí)間?；痉猪撓到y(tǒng)中，如果沒有快表，訪問內(nèi)存一次需要的時(shí)間為t，有效訪問時(shí)間分為：查頁表找到對應(yīng)的頁表表項(xiàng)所花的時(shí)間t，通過對應(yīng)的物理地址訪問一次內(nèi)存所花時(shí)間t，所以：EAT=t+t=2t。若有快表，設(shè)快表TLB的查找需要時(shí)間為ε，訪問一次內(nèi)存需要的時(shí)間為t，命中率為α，則有效訪問時(shí)間分為：查頁表項(xiàng)的平均時(shí)間為ε*α+(t+ε)(1-α)，通過對應(yīng)的物理地址訪問一次內(nèi)存所花時(shí)間為t。所以EAT=ε*α+(t+ε)(1-α)+t=2t+ε-tα。第131頁/共170頁133典型例題頁面走向?yàn)椋?，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。分配頁面數(shù)為3時(shí)，試計(jì)算FIFO,LRU和OPT頁面淘汰算法的缺頁中斷數(shù)及缺頁中斷率各是多少？

解：第132頁/共170頁13412342156212376321236FIFO1T12T123T234T234341T415T156T562T621T621213T137T376T376762T621T621213T136T缺頁中斷率：16/20＝80％12342156212376321236LRU1T12T123T234T342421T215T156T562T621T612123T237T376T763632T321T312123236T缺頁中斷率：15/20＝75％第133頁/共170頁135123421562123763212360PT1T12T123T124T124124125T126T126126126326T376T376376326T321T321321621T缺頁中斷率：11/20＝55％第134頁/共170頁136

某程序頁面走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5。運(yùn)行時(shí)，分別實(shí)行FIFO和LRU頁面淘汰算法，試就3個(gè)內(nèi)存塊和4個(gè)內(nèi)存塊的情形，求出各自的缺頁中斷率，并分析對于FIFO是否會(huì)發(fā)生異常現(xiàn)象。置換算法舉例第135頁/共170頁137FIFO算法（3個(gè)頁面）432143543215432143555211432143335224321444355×××××××××頁面走向3個(gè)內(nèi)存塊缺頁計(jì)數(shù)缺頁次數(shù)：9；f＝9/12第136頁/共170頁138FIFO算法（4個(gè)頁面）432143543215432111543215432221543214333215432444321543××××××××××頁面走向4個(gè)內(nèi)存塊缺頁計(jì)數(shù)缺頁次數(shù)：10；f＝10/12第137頁/共170頁139LRU算法（3個(gè)頁面）432143543215432143543215432143543214321435432××××××××××頁面走向3個(gè)內(nèi)存塊缺頁計(jì)數(shù)缺頁次數(shù)：10；f＝10/12第138頁/共170頁140LRU算法（4個(gè)頁面）432143543215432143543215432143543214321435432432111543××××××××頁面走向4個(gè)內(nèi)存塊缺頁計(jì)數(shù)缺頁次數(shù)：8；f＝8/12第139頁/共170頁141例題:請求分頁系統(tǒng)中，假設(shè)某進(jìn)程的頁表內(nèi)容如下表所示：頁號(hào)頁框號(hào)有效位（存在位）0101H11--02254H1頁面大小為4KB，一次內(nèi)存的訪問時(shí)間是100ns，一次快表的訪問時(shí)間是10ns，處理一次缺頁的平均時(shí)間為108ns（已含更新TLB和頁表的時(shí)間），進(jìn)程的駐留集大小固定為2，采用最近最少使用置換算法（LRU）和局部淘汰策略。假設(shè)（1）TLB初始的時(shí)候?yàn)榭?；?）地址轉(zhuǎn)換時(shí)先訪問TLB，若TLB未命中，再訪問頁表（忽略訪問頁表之后的TLB更新時(shí)間）；（3）有效為為0表示頁面不在內(nèi)存，產(chǎn)生缺頁中斷，缺頁中斷處理后，返回到產(chǎn)生缺頁中斷的指令處重新執(zhí)行。第140頁/共170頁142設(shè)有虛擬地址訪問序列2362H、1565H、25A5H，請問：

（1）依次訪問上述三個(gè)虛擬地址，各需要多少時(shí)間？給出計(jì)算過程。

（2）基于上述訪問序列，虛地址1565H的物理地址是多少？請說明理由。第141頁/共170頁143例.作業(yè)Ａ的頁面映象表如下圖所示：（一頁=一塊=1024字節(jié)）頁號(hào)塊號(hào)中斷位訪問位修改位輔存地址

０８１１１１０００

１５１００３０００

２７１１０５０００

３０００８０００問：①指出頁表中中斷位、訪問位、修改位、輔存地址的含義？②當(dāng)執(zhí)行到１０００單元的指令“ＬＯＡＤ１，１８００”時(shí)，系統(tǒng)是怎樣進(jìn)行地址變換（即１８００在主存的哪個(gè)單元中）③當(dāng)執(zhí)行到１５００單元指令（ＬＯＡＤ１，３６００）時(shí)，會(huì)發(fā)生什么現(xiàn)象？第142頁/共170頁1444.4.1分段存儲(chǔ)管理方式的引入

引入分段存儲(chǔ)管理方式，主要是為了滿足用戶和程序員的下述一系列需要：

1)方便編程

2)信息共享

3)信息保護(hù)

4)動(dòng)態(tài)增長

5)動(dòng)態(tài)鏈接2.7段式存儲(chǔ)管理第143頁/共170頁145

在段式存儲(chǔ)管理系統(tǒng)中，用戶可以根據(jù)邏輯結(jié)構(gòu)將程序分成若干段，每一段的虛擬地址空間各自都從0開始編址，因此整個(gè)作業(yè)的虛擬地址空間是二維的。第144頁/共170頁146分段系統(tǒng)的基本原理

將程序的地址空間按內(nèi)容或函數(shù)關(guān)系劃分為若干個(gè)段(segment)(按段的邏輯關(guān)系進(jìn)行劃分；），程序加載時(shí)，以段為單位為所有段分配內(nèi)存（內(nèi)存分區(qū)），這些段不必連續(xù)；物理內(nèi)存的管理采用動(dòng)態(tài)分區(qū)。需要CPU的硬件支持，然后通過地址映射機(jī)構(gòu)將段式虛地址轉(zhuǎn)換為實(shí)際的內(nèi)存物理地址。第145頁/共170頁1471.分段分段地址中的地址具有如下結(jié)構(gòu)：段號(hào)段內(nèi)地址3116150

每個(gè)段都從0開