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

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

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

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

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

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

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

基本思想：

內(nèi)存不是預先劃分好的，而是當作業(yè)裝入時，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配。若有足夠的空間，則按需要分割一部分分區(qū)給該進程否則令其等待主存空間優(yōu)點：沒有內(nèi)碎片。缺點：有外碎片。第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空閑存儲區(qū)表管理空閑內(nèi)存區(qū)的數(shù)據(jù)結(jié)構(gòu)可采用鏈接法和連續(xù)線性表格法。下面舉一個連續(xù)線性表格管理空閑內(nèi)存的方法，如采用鏈接法，就需要在表項中增加一個指向下一個空閑區(qū)的指針。每一個空閑分區(qū)用一個map結(jié)構(gòu)管理：structmap{unsignedm_size;//空閑分區(qū)的長度

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

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

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

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

頁號P位移量D3112110

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

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

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

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

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

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

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

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

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

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

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

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

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

頁表012351261471626……快表幀號物理地址頁內(nèi)位移缺頁異常地址變換機構(gòu)第97頁/共170頁99開始頁號>頁表長度檢索快表？命中訪問頁表頁在內(nèi)存？修改快表修改訪問位和修改位形成物理地址地址變換結(jié)束地址越界保留CPU現(xiàn)場？內(nèi)存滿選擇一頁換出OS命令CPU從外存讀缺頁啟動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)存中選中了一個淘汰的頁面，如果該頁面在內(nèi)存時未被修改過，那么就可以直接用調(diào)入的頁面將其覆蓋掉；如果該頁面在內(nèi)存時被修改過，那么就必須把它寫回到磁盤。以便更新該頁在輔存上的副本。一個頁面的內(nèi)容在內(nèi)存時是否被修改過，這樣的信息可以通過頁表表目反映出來。第100頁/共170頁102“抖動”或“顛簸”現(xiàn)象抖動－進程塊頻繁的換入換出當操作系統(tǒng)取進一頁時，它必須扔出一頁。如果一塊正好在將要被用到之前扔出，操作系統(tǒng)又不得不幾乎立即把它取回來，太多的這類操作會導致“系統(tǒng)抖動”，處理器的大多數(shù)時間都用于交換頁，而不是執(zhí)行指令。改進抖動的許多復雜但有效的算法，從本質(zhì)上看是，操作系統(tǒng)試圖根據(jù)最近的歷史來猜測在不遠的將來最可能用到的頁。第101頁/共170頁103頁面淘汰算法功能：需要調(diào)入頁面時，選擇內(nèi)存中哪個物理頁面被置換。目標：把未來不再使用的或短期內(nèi)較少使用的頁面調(diào)出，通常只能在局部性原理指導下依據(jù)過去的統(tǒng)計數(shù)據(jù)進行預測。第102頁/共170頁104頁面走向一個程序執(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缺頁中斷率

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

f＝F/A

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

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

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

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

最近最久未使用算法的著眼點是在要進行頁面淘汰時，檢查這些淘汰對象的被訪問時間，總是把最長時間未被訪問過的頁面淘汰出去。選擇內(nèi)存中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳算法。但由于需要記錄頁面使用時間的先后關(guān)系，硬件開銷太大。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t，當必須淘汰一個頁面時，選擇現(xiàn)有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰。第110頁/共170頁112舉例：123412512345123412512345123412512341234125123××××××××××頁面走向3個內(nèi)存塊缺頁計數(shù)缺頁中斷率：f＝10/12＝83％第111頁/共170頁113可以設置一個從中間可以出隊的非嚴格意義上的隊列，隊列中的每一個單元對應于一個內(nèi)存頁，每次訪問一個頁面時將對應單元從隊列中抽出，重新排到隊尾去，淘汰的頁從隊列頭取。這樣，經(jīng)常要訪問的頁總是排在靠近隊列的尾部，而排在隊首位置上的頁就是最長時間沒有被訪問過的頁。第112頁/共170頁114假定現(xiàn)有一進程所訪問的頁面的頁面號序列為：4，7，0，7，1，0，1，2，1，2，6第113頁/共170頁115實現(xiàn)該算法的主要困難是如果每執(zhí)行一條訪問主存的指令時都要執(zhí)行隊列的操作，并且該操作是用軟件實現(xiàn)的話，其時間開銷是不可忍受的。減少算法時間復雜性的方法之一是用硬件實現(xiàn)隊列結(jié)構(gòu)和操作，方法之二是不必在每一條訪問內(nèi)存指令都執(zhí)行隊列操作，可以每過一個時間間隔（如時鐘中斷）執(zhí)行一次。第114頁/共170頁116另一種全部用硬件實現(xiàn)的LRU算法是對于n個頁面設置一個n*n的矩陣，矩陣初始時全為0。當k頁被訪問時，硬件置k行的所有位為1，再置k列的所有位為0。任何時刻，二進制值為最小的一行所對應的頁是最近最久不用的頁。圖2-15為含有4個頁面，訪問序列是0123210323的情況下，每訪問一頁后矩陣的狀態(tài)第115頁/共170頁117訪問序列是0123210323第116頁/共170頁1184.最近未使用淘汰算法NUR（NotUsedRecently）是一種低開銷的近似于LRU的淘汰算法。其主要思想是淘汰最近一段時間內(nèi)未曾訪問過的某一頁面。該算法的一個實施不僅能考慮最近未曾訪問過的頁，還能優(yōu)先挑選頁面數(shù)據(jù)未曾修改過的頁，這樣可減少將淘汰頁寫回輔存的開銷。如采用這種算法，要為每一項增設兩個硬件位——訪問位和修改位。當該頁未訪問過或沒修改過時對應位為0，反之為1。訪問位和修改位不一定要設在頁表中。初始時所有頁的訪問位和修改位都清0。當訪問某頁時，該頁的訪問位置1，當某頁的數(shù)據(jù)被修改后，將該頁的訪問位和修改位都置1。第117頁/共170頁119系統(tǒng)將主存中各個使用頁組織成一個循環(huán)隊列，并設置一個循環(huán)檢測指針。當需要淘汰一頁時，從指針指向的頁開始，順次考察各頁的使用情況，如其訪問位為1，則將該位清0；如訪問位為0，但修改位為1，則將修改位置0（還應當更新輔存對應頁）；不斷重復這個過程，直到找到訪問位和修改位都為0的頁，將其作為淘汰頁。按照這個算法，最新讀過的頁在第一輪的循環(huán)檢測中不會被選中，最近寫過的頁在第一、二輪循環(huán)檢測中不會被選中，這樣不僅實現(xiàn)了NUR算法，而且給予修改過的頁兩次機會第118頁/共170頁120NUR算法的另一種實現(xiàn)是不在檢測時清0，而是系統(tǒng)每過一個適當?shù)臅r間，將所有頁的訪問位置0。這樣在兩次清0之前，內(nèi)存中各頁的使用狀態(tài)可能有4種（即序號訪問位修改位）：序號訪問位修改位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)缺頁中斷率的主要因素是分配給一個作業(yè)的頁面數(shù)目。雖然在主存中運行的作業(yè)數(shù)越多，每個作業(yè)分配到的頁架越多，系統(tǒng)的運行性能就越好但內(nèi)存并不總是充足有余的廉價資源。實踐證明，工作集中頁面少于某一個數(shù)時，作業(yè)的缺頁中斷次數(shù)會急劇增加，即會發(fā)生頁面抖動現(xiàn)象；而高于這個數(shù)，作業(yè)的缺頁中斷次數(shù)不會明顯減少，這個頁面數(shù)范圍稱為頁面的工作集。第121頁/共170頁123工作集不僅與作業(yè)的特征，如程序大小、結(jié)構(gòu)、訪問數(shù)據(jù)的規(guī)律有關(guān)，也與作業(yè)運行的時間段有關(guān)。系統(tǒng)可根據(jù)一個進程的缺頁中斷率估計出合適的工作集大小，并根據(jù)運行情況給予調(diào)整。如在某一段時間內(nèi)，系統(tǒng)中很多作業(yè)所能分配到的頁面數(shù)小于工作集時，應當掛起某些作業(yè)，將其所占用的主存空間分配給優(yōu)先級高的作業(yè)，以避免抖動現(xiàn)象的發(fā)生第122頁/共170頁124按淘汰頁面的選擇范圍分，有兩種淘汰策略：一種是淘汰的頁從整個主存也即所有的作業(yè)所占用的頁面中選擇，這稱為全局淘汰算法；另一種是從本作業(yè)所占用的頁面中選擇，稱為局部淘汰法。在討論頁面淘汰算法時，還未曾考慮淘汰頁的選擇范圍，淘汰頁的選擇范圍對選擇不同的淘汰算法和硬件的配置影響很大。全局算法一般工作得比局部算法好，因為這種算法可以在很多進程之間動態(tài)地分配頁面，但支持全局算法的硬件開銷較大，算法運行的時間也較大。有些算法，如采用n*n位矩陣的NUR算法，就不大可能在采用全局淘汰策略時被采用第123頁/共170頁125（補充）內(nèi)存分配策略和分配算法物理塊的分配策略

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

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

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

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

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

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

當進程在運行中需要訪問某部分程序和數(shù)據(jù)時，若發(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ū)的高。這樣，每當發(fā)生缺頁請求時，系統(tǒng)應從何處將缺頁調(diào)入內(nèi)存，可分成如下三種情況：

(1)

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

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

(3)

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

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

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

（1）依次訪問上述三個虛擬地址，各需要多少時間？給出計算過程。

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

０８１１１１０００

１５１００３０００

２７１１０５０００

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

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

1)方便編程

2)信息共享

3)信息保護

4)動態(tài)增長

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

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

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

每個段都從0開