操作系統(tǒng)原理課件

操作系統(tǒng)原理課件第一頁(yè)，共171頁(yè)。第二章存儲(chǔ)管理2.1存儲(chǔ)管理基礎(chǔ)2.2基本存儲(chǔ)管理方法2.3可變分區(qū)存儲(chǔ)管理方法2.4內(nèi)存擴(kuò)充技術(shù)2.5純分頁(yè)的存儲(chǔ)管理2.6請(qǐng)求分頁(yè)系統(tǒng)2.7段式存儲(chǔ)管理2.8段頁(yè)式存儲(chǔ)管理2.9Linux存儲(chǔ)管理2第二頁(yè)，共171頁(yè)。存儲(chǔ)器可分為：內(nèi)存儲(chǔ)器和外存儲(chǔ)器；內(nèi)存儲(chǔ)器：可以被CPU直接訪問(wèn)。外存儲(chǔ)器：不可以被CPU直接訪問(wèn)，外存與CPU之間只能夠在輸入輸出控制系統(tǒng)的管理下，進(jìn)行信息交換。3第三頁(yè)，共171頁(yè)。2.1存儲(chǔ)管理基礎(chǔ)2.1.1虛擬地址與物理地址4第四頁(yè)，共171頁(yè)。內(nèi)存儲(chǔ)器是由一個(gè)個(gè)存儲(chǔ)單元組成，一個(gè)存儲(chǔ)單元可存放若干個(gè)二進(jìn)制的位（bit），8個(gè)二進(jìn)制位被稱(chēng)為一個(gè)字節(jié)（Byte）。內(nèi)存中的存儲(chǔ)單元按一定順序進(jìn)行編號(hào)，每個(gè)單元所對(duì)應(yīng)的編號(hào)，稱(chēng)為該單元的單元地址。物理地址（絕對(duì)地址，實(shí)地址）：內(nèi)存中存儲(chǔ)單元的地址。物理地址可直接尋址。邏輯地址（相對(duì)地址，虛地址）：用戶(hù)的程序經(jīng)過(guò)匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對(duì)地址的形式。其首地址為0，其余指令中的地址都相對(duì)于首地址來(lái)編址。不能用邏輯地址在內(nèi)存中讀取信息。5第五頁(yè)，共171頁(yè)。6第六頁(yè)，共171頁(yè)。地址重定位地址重定位（地址映射）：將用戶(hù)程序中的邏輯地址轉(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)換。7第七頁(yè)，共171頁(yè)。2.1.2地址定位方式1.固定定位方式由程序員在編寫(xiě)程序時(shí)或由編譯連接程序?qū)υ闯绦蜻M(jìn)行編譯連接時(shí)，直接指定程序在執(zhí)行時(shí)訪問(wèn)的實(shí)際存儲(chǔ)器地址的方式稱(chēng)為固定定位方式。此種定位方式一般只適合于單板機(jī)或單用戶(hù)系統(tǒng)。在多道程序環(huán)境下，應(yīng)保證各個(gè)作業(yè)的地址互不重疊，這就比較困難了。8第八頁(yè)，共171頁(yè)。9第九頁(yè)，共171頁(yè)。2.靜態(tài)重定位方式源程序經(jīng)編譯和連接后生成目標(biāo)代碼中的地址是以0為起始地址的相對(duì)地址。當(dāng)需要執(zhí)行時(shí)，由裝入程序運(yùn)行重定位程序模塊，根據(jù)作業(yè)在本次分配到的內(nèi)存起始地址，將可執(zhí)行目標(biāo)代碼裝到指定內(nèi)存地址中，并修改所有有關(guān)地址部分的值。修改的方式是對(duì)每一個(gè)邏輯地址的值加上內(nèi)存區(qū)首地址（或稱(chēng)基地址）值。10第十頁(yè)，共171頁(yè)。11第十一頁(yè)，共171頁(yè)。靜態(tài)重定位的特點(diǎn)（1）靜態(tài)重定位是在程序運(yùn)行之前完成地址重定位工作的；（2）靜態(tài)重定位由軟件實(shí)現(xiàn)，無(wú)須硬件提供支持；（3）實(shí)行靜態(tài)重定位時(shí)，地址重定位工作是在程序裝入時(shí)被一次集中完成的；（4）絕對(duì)地址空間里的目標(biāo)程序與原相對(duì)地址空間里的目標(biāo)程序面目已不相同，因?yàn)榍罢哌M(jìn)行了地址調(diào)整；（5）實(shí)施靜態(tài)重定位后，若用戶(hù)程序在內(nèi)存中做了移動(dòng)，那么程序指令中的地址就不再反映所在的存儲(chǔ)位置了，除非重新進(jìn)行地址重定位。12第十二頁(yè)，共171頁(yè)。3.動(dòng)態(tài)重定位方式采用動(dòng)態(tài)重定位方式，將程序在裝入內(nèi)存時(shí)，不必修改程序的邏輯地址值，程序執(zhí)行期間在訪問(wèn)內(nèi)存之前，再實(shí)時(shí)地將邏輯地址變換成物理地址。動(dòng)態(tài)重定位要靠硬件地址變換機(jī)構(gòu)實(shí)現(xiàn)。①當(dāng)程序開(kāi)始執(zhí)行時(shí)，系統(tǒng)將程序在內(nèi)存的起始地址送入地址變換機(jī)構(gòu)中的基地址寄存器BR中。②在執(zhí)行指令時(shí)，若涉及到邏輯地址，則先將該地址送入虛擬地址寄存器VR，再將BR和VR中的值相加后送入地址寄存器MR，并按MR中的值訪問(wèn)內(nèi)存。（MR）=（BR）+（VR）13第十三頁(yè)，共171頁(yè)。14第十四頁(yè)，共171頁(yè)。2.2基本存儲(chǔ)管理方法2.2.1單一連續(xù)分區(qū)存儲(chǔ)管理基本思想：內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)，用戶(hù)區(qū)。應(yīng)用程序裝入到用戶(hù)區(qū)，可使用用戶(hù)區(qū)全部空間。最簡(jiǎn)單，適用于單用戶(hù)、單任務(wù)的OS；單用戶(hù)系統(tǒng)在一段時(shí)間內(nèi)，只有一個(gè)進(jìn)程在內(nèi)存。15第十五頁(yè)，共171頁(yè)。特點(diǎn)（1）系統(tǒng)總是把整個(gè)用戶(hù)區(qū)分配給一個(gè)用戶(hù)使用。（2）實(shí)際上，內(nèi)存用戶(hù)區(qū)又被分為“使用區(qū)”和“空閑區(qū)”兩部分。

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

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

基本思想：

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

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

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

頁(yè)號(hào)P位移量D3112110虛擬地址字的頁(yè)內(nèi)偏移部分占據(jù)低n個(gè)二進(jìn)制位，使2n剛好等于頁(yè)的大小，這樣安排便于硬件直接截取高位部分的頁(yè)號(hào)和低位部分的頁(yè)內(nèi)偏移值。64第六十四頁(yè)，共171頁(yè)。例：某系統(tǒng)的地址結(jié)構(gòu)長(zhǎng)為16位，相對(duì)地址3000的二進(jìn)制位表示如下：00011101110100001514131211109876543210塊尺寸1KB，對(duì)應(yīng)數(shù)對(duì)（2，952）；塊尺寸256字節(jié)，對(duì)應(yīng)數(shù)對(duì)（11，184）。65第六十五頁(yè)，共171頁(yè)。程序的虛擬地址空間是連續(xù)的，但程序的虛頁(yè)可以分配到主存中不連續(xù)的空閑頁(yè)架中；故分頁(yè)系統(tǒng)需要在主存中開(kāi)辟一個(gè)頁(yè)表區(qū)域來(lái)建立每一個(gè)作業(yè)的虛頁(yè)號(hào)到內(nèi)存的頁(yè)架號(hào)之間的映射關(guān)系。系統(tǒng)還需要建立一個(gè)總頁(yè)表來(lái)記錄各個(gè)作業(yè)頁(yè)表的起始地址和長(zhǎng)度，并將當(dāng)前運(yùn)行進(jìn)程的頁(yè)表起始地址和長(zhǎng)度存放在頁(yè)表控制寄存器中。66第六十六頁(yè)，共171頁(yè)。每一個(gè)作業(yè)的頁(yè)表空間可以是連續(xù)的，也可以是不連續(xù)的，但連續(xù)的頁(yè)表空間管理方便，存取速度也快。連續(xù)的頁(yè)表要分配的空間本身又相當(dāng)于一個(gè)小分區(qū)，故可采用前面討論的分區(qū)分配和釋放算法。連續(xù)的頁(yè)表空間同時(shí)也帶來(lái)了頁(yè)表分區(qū)之間的存儲(chǔ)區(qū)碎片問(wèn)題，但由于一個(gè)作業(yè)的頁(yè)表空間比作業(yè)本身的程序和數(shù)據(jù)空間小得多，故這個(gè)問(wèn)題相對(duì)來(lái)說(shuō)并不嚴(yán)重67第六十七頁(yè)，共171頁(yè)?；镜牡刂纷儞Q機(jī)構(gòu)頁(yè)表保存在內(nèi)存中；硬件設(shè)置一個(gè)專(zhuān)用寄存器：“頁(yè)表寄存器”每當(dāng)進(jìn)程調(diào)度時(shí)，把調(diào)度到進(jìn)程的頁(yè)表起始地址和頁(yè)表長(zhǎng)度（即頁(yè)表表項(xiàng)的數(shù)目）放入寄存器中。68第六十八頁(yè)，共171頁(yè)。地址轉(zhuǎn)換過(guò)程1）由硬件自動(dòng)將虛擬地址字分成虛頁(yè)號(hào)和頁(yè)內(nèi)偏移兩部分；2）由頁(yè)表控制寄存器中頁(yè)表起始地址和虛擬地址字中的虛頁(yè)號(hào)查找頁(yè)表，對(duì)應(yīng)虛頁(yè)號(hào)的頁(yè)表表項(xiàng)地址為：頁(yè)表起始地址+虛頁(yè)號(hào)*頁(yè)表表項(xiàng)長(zhǎng)度；3）將頁(yè)表中取出的頁(yè)架號(hào)和虛擬地址字中的頁(yè)內(nèi)偏移值裝入地址寄存器，根據(jù)地址寄存器中的地址值訪問(wèn)主存。頁(yè)表控制寄存器中的“長(zhǎng)度”起到存儲(chǔ)保護(hù)的作用，每個(gè)相對(duì)地址中的頁(yè)號(hào)都不能大于該長(zhǎng)度，否則出錯(cuò)。69第六十九頁(yè)，共171頁(yè)。70第七十頁(yè)，共171頁(yè)。例若在分頁(yè)式存儲(chǔ)管理中，建立了某個(gè)作業(yè)的頁(yè)，塊對(duì)應(yīng)關(guān)系為：第0頁(yè)放在第0塊，第1頁(yè)放在第3塊，第2頁(yè)放在第1塊，如下所示。已知塊的尺寸為1KB/塊。求相對(duì)地址1023、1024、3000、所對(duì)應(yīng)的絕對(duì)地址。虛頁(yè)號(hào)頁(yè)架號(hào)001321解：1023－>10231024－>30723000－>197671第七十一頁(yè)，共171頁(yè)。缺點(diǎn)（1）頁(yè)表放在內(nèi)存，增加了系統(tǒng)在存儲(chǔ)上的開(kāi)銷(xiāo)；（2）降低了CPU的訪問(wèn)速度。因?yàn)槊看螌?duì)某一地址的訪問(wèn)，首先要訪問(wèn)內(nèi)存中的頁(yè)表，形成絕對(duì)地址后，才能進(jìn)行所需要的真正訪問(wèn)。72第七十二頁(yè)，共171頁(yè)。2.5.3具有快表的地址變換機(jī)構(gòu)考慮到大多數(shù)程序在一次調(diào)度運(yùn)行時(shí)，傾向于在少數(shù)頁(yè)面中進(jìn)行頻繁的訪問(wèn)（這被稱(chēng)為程序的“局部性”原理），因此實(shí)際系統(tǒng)中的做法是采用內(nèi)存頁(yè)表與快速寄存器組相結(jié)合的解決方案，并且利用程序局部性原理，只用極少數(shù)幾個(gè)快速寄存器來(lái)構(gòu)成快速寄存器組，這時(shí)把快速寄存器組單獨(dú)起名為“快表”，主存中的頁(yè)表有時(shí)也稱(chēng)為慢表。73第七十三頁(yè)，共171頁(yè)?？毂碛蒀PU中的高速cache或聯(lián)想寄存器構(gòu)成。聯(lián)想寄存器是一種按內(nèi)容進(jìn)行并行查找的一組快速寄存器，當(dāng)在其輸入端有一個(gè)輸入值頁(yè)號(hào)p時(shí)，在聯(lián)想寄存器中存放頁(yè)號(hào)為p的那一項(xiàng)就立即選中，并輸出其變換值頁(yè)架號(hào)b。由于訪問(wèn)聯(lián)想寄存器比訪問(wèn)主存快得多，故極大地提高了地址變換速度。74第七十四頁(yè)，共171頁(yè)。地址的映射快表中存放的是頁(yè)表內(nèi)容的一部分。在進(jìn)行地址變換時(shí)，變換機(jī)構(gòu)根據(jù)虛擬地址字中的頁(yè)號(hào)同時(shí)查找快表和慢表;一旦在快表中查到虛頁(yè)號(hào)，就用輸出的頁(yè)架號(hào)和虛擬地址字中的偏移地址構(gòu)造主存物理地址；否則，就用慢表中查到的頁(yè)架號(hào)構(gòu)造主存物理地址，同時(shí)還用慢表的該表項(xiàng)更新快表，這就可能需要按某一算法淘汰快表中某一表項(xiàng)，以便下次再訪問(wèn)該頁(yè)的過(guò)程能在快表中進(jìn)行。75第七十五頁(yè)，共171頁(yè)。p’頁(yè)表地址越界

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

b+頁(yè)號(hào)p頁(yè)內(nèi)地址dP’d物理地址頁(yè)表地址寄存器頁(yè)表長(zhǎng)度寄存器邏輯地址76第七十六頁(yè)，共171頁(yè)。由于成本關(guān)系，快表不可能做的很大，通常只存放16－512個(gè)頁(yè)表項(xiàng)，這對(duì)于中、小型作業(yè)來(lái)說(shuō)，已有可能把全部頁(yè)表項(xiàng)放在快表中，但對(duì)于大型作業(yè)，則只能將其一部分頁(yè)表項(xiàng)放入其中。據(jù)統(tǒng)計(jì)，快表中如含有8個(gè)表項(xiàng)時(shí)，平均命中率為85%，含有16個(gè)表項(xiàng)時(shí)，平均命中率為97%，因此在配備聯(lián)想寄存器的頁(yè)式管理系統(tǒng)中，多一級(jí)地址變換不會(huì)明顯減慢程序的執(zhí)行速度。77第七十七頁(yè)，共171頁(yè)。2.5.4空閑內(nèi)存頁(yè)的管理在頁(yè)式管理系統(tǒng)中，需要一張表記錄主存中每個(gè)頁(yè)的使用情況和當(dāng)前空閑頁(yè)的總數(shù)。由于主存頁(yè)總數(shù)很多，且頁(yè)的大小相等，故可用位圖描述各頁(yè)的狀態(tài)。在位圖中用一個(gè)二進(jìn)制位對(duì)應(yīng)于主存中的一個(gè)頁(yè)，該位為0表示對(duì)應(yīng)頁(yè)空閑，為1表示對(duì)應(yīng)頁(yè)已分配。位圖中每一個(gè)字節(jié)可表示8頁(yè)的狀態(tài)，如設(shè)頁(yè)面大小為4KB，對(duì)于32MB的主存空間，只需要1KB大小的位表78第七十八頁(yè)，共171頁(yè)。位圖空閑塊總數(shù)：60111100100101111位號(hào)01234567字節(jié)號(hào)01頁(yè)框號(hào)＝字節(jié)號(hào)×8＋位號(hào)字節(jié)號(hào)＝頁(yè)框號(hào)/8；位號(hào)＝頁(yè)框號(hào)％879第七十九頁(yè)，共171頁(yè)。在分配空閑頁(yè)時(shí)，可一次取出位圖中的一個(gè)字，如該字內(nèi)容非全1，即表示其中必對(duì)應(yīng)有空閑頁(yè)，接下來(lái)就可確定空閑頁(yè)的位置。為了提高在位圖上檢索空閑頁(yè)的速度，可在表頭增設(shè)一個(gè)起始查找位置指針，位圖中在起始查找指針之前的所有字（或字節(jié)）都不含有空閑位。另外，設(shè)置一個(gè)循環(huán)查找指針的算法也不錯(cuò)。釋放算法很簡(jiǎn)單，只要在位圖中的對(duì)應(yīng)位上置0即可，但如設(shè)置起始查找指針，則可能要修改指針值。也可使用順序或鏈接結(jié)構(gòu)的棧來(lái)管理空閑頁(yè)，棧中每一個(gè)單元指示一個(gè)空閑頁(yè)。采用這種方法所需的存儲(chǔ)空間比位圖大許多，但分配空閑頁(yè)時(shí)速度快很多。80第八十頁(yè)，共171頁(yè)。分頁(yè)式存儲(chǔ)管理的特點(diǎn)（1）內(nèi)存事先被劃分成相等尺寸的頁(yè)框，它是進(jìn)行存儲(chǔ)分配的單位；（2）用戶(hù)作業(yè)的相對(duì)地址空間按照頁(yè)框的尺寸劃分成頁(yè)。（3）由于相對(duì)地址空間中的頁(yè)可以進(jìn)入內(nèi)存中的任何一個(gè)空閑頁(yè)框，并且分頁(yè)式存儲(chǔ)管理實(shí)行的是動(dòng)態(tài)重定位，因此它打破了一個(gè)作業(yè)必須占據(jù)連續(xù)存儲(chǔ)空間的限制，作業(yè)在不連續(xù)的存儲(chǔ)區(qū)里，也能夠得到正確的運(yùn)行。81第八十一頁(yè)，共171頁(yè)。（1）平均每個(gè)作業(yè)要浪費(fèi)半頁(yè)大小的存儲(chǔ)頁(yè)。（2）作業(yè)雖然可以不占據(jù)連續(xù)的存儲(chǔ)區(qū)，但是每次仍然要求一次全部進(jìn)入內(nèi)存。因此，如果作業(yè)很大，其存儲(chǔ)需求大于內(nèi)存，那么仍然存在小內(nèi)存不能運(yùn)行大作業(yè)的問(wèn)題。缺點(diǎn)82第八十二頁(yè)，共171頁(yè)。（補(bǔ)充）兩級(jí)和多級(jí)頁(yè)表現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。在這樣的環(huán)境下，頁(yè)表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。例如，對(duì)于一個(gè)具有32位邏輯地址空間的分頁(yè)系統(tǒng)，規(guī)定頁(yè)面大小為4KB即212B，則在每個(gè)進(jìn)程頁(yè)表中的頁(yè)表項(xiàng)可達(dá)1兆個(gè)之多。又因?yàn)槊總€(gè)頁(yè)表項(xiàng)占用一個(gè)字節(jié)，故每個(gè)進(jìn)程僅僅其頁(yè)表就要占用1MB的內(nèi)存空間，而且還要求是連續(xù)的。83第八十三頁(yè)，共171頁(yè)。（補(bǔ)充）兩級(jí)和多級(jí)頁(yè)表可以采用這樣兩個(gè)方法來(lái)解決這一問(wèn)題：①采用離散分配方式來(lái)解決難以找到一塊連續(xù)的大內(nèi)存空間的問(wèn)題：②只將當(dāng)前需要的部分頁(yè)表項(xiàng)調(diào)入內(nèi)存，其余的頁(yè)表項(xiàng)仍駐留在磁盤(pán)上，需要時(shí)再調(diào)入。84第八十四頁(yè)，共171頁(yè)。1.兩級(jí)頁(yè)表(Two-LevelPageTable)對(duì)于要求連續(xù)的內(nèi)存空間來(lái)存放頁(yè)表的問(wèn)題，可利用將頁(yè)表進(jìn)行分頁(yè)，并離散的將各個(gè)頁(yè)面分別存放在不同的物理塊中的辦法來(lái)加以解決，同樣也要為離散分配的頁(yè)表再建立一張頁(yè)表，稱(chēng)為外層頁(yè)表（OuterPageTable），在每個(gè)頁(yè)表項(xiàng)中記錄了頁(yè)表頁(yè)面的物理塊號(hào)。85第八十五頁(yè)，共171頁(yè)。邏輯地址結(jié)構(gòu)可描述如下：86第八十六頁(yè)，共171頁(yè)。兩級(jí)頁(yè)表結(jié)構(gòu)87第八十七頁(yè)，共171頁(yè)。88第八十八頁(yè)，共171頁(yè)。上述對(duì)頁(yè)表施行離散分配的方法，雖然解決了對(duì)大頁(yè)表無(wú)需大片存儲(chǔ)空間的問(wèn)題，但并未解決用較少的內(nèi)存空間去存放大頁(yè)表的問(wèn)題。換言之，只用離散分配空間的辦法并未減少頁(yè)表所占用的內(nèi)存空間。解決方法是把當(dāng)前需要的一批頁(yè)表項(xiàng)調(diào)入內(nèi)存，以后再根據(jù)需要陸續(xù)調(diào)入。在采用兩級(jí)頁(yè)表結(jié)構(gòu)的情況下，對(duì)于正在運(yùn)行的進(jìn)程，必須將其外層頁(yè)表調(diào)入內(nèi)存，而對(duì)頁(yè)表則只需調(diào)入一頁(yè)或幾頁(yè)。89第八十九頁(yè)，共171頁(yè)。2.多級(jí)頁(yè)表對(duì)于32位的機(jī)器，采用兩級(jí)頁(yè)表結(jié)構(gòu)是合適的；但對(duì)于64位的機(jī)器，如果頁(yè)面大小仍采用4KB即212B，那么還剩下52位，假定仍按物理塊的大小(212位)來(lái)劃分頁(yè)表，則將余下的42位用于外層頁(yè)號(hào)。此時(shí)在外層頁(yè)表中可能有4096G個(gè)頁(yè)表項(xiàng)，要占用16384GB的連續(xù)內(nèi)存空間。必須采用多級(jí)頁(yè)表，將外層頁(yè)表再進(jìn)行分頁(yè)，也是將各分頁(yè)離散地裝入到不相鄰接的物理塊中，再利用第2級(jí)的外層頁(yè)表來(lái)映射它們之間的關(guān)系。對(duì)于64位的計(jì)算機(jī)，如果要求它能支持2６４(=1844744TB)規(guī)模的物理存儲(chǔ)空間，則即使是采用三級(jí)頁(yè)表結(jié)構(gòu)也是難以辦到的；而在當(dāng)前的實(shí)際應(yīng)用中也無(wú)此必要。90第九十頁(yè)，共171頁(yè)。2.6請(qǐng)求分頁(yè)系統(tǒng)虛擬存儲(chǔ)器的引入1.常規(guī)存儲(chǔ)器管理方式的特征一次性。作業(yè)在運(yùn)行前一次性的全部裝入內(nèi)存。(2)

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

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

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

頁(yè)表012351261471626……快表幀號(hào)物理地址頁(yè)內(nèi)位移缺頁(yè)異常地址變換機(jī)構(gòu)99第九十九頁(yè)，共171頁(yè)。開(kāi)始頁(yè)號(hào)>頁(yè)表長(zhǎng)度檢索快表？命中訪問(wèn)頁(yè)表頁(yè)在內(nèi)存？修改快表修改訪問(wèn)位和修改位形成物理地址地址變換結(jié)束地址越界保留CPU現(xiàn)場(chǎng)？?jī)?nèi)存滿(mǎn)選擇一頁(yè)換出OS命令CPU從外存讀缺頁(yè)啟動(dòng)I/O硬件缺頁(yè)中斷處理是是是是否否否否該頁(yè)是否修改過(guò)？從外存找到缺頁(yè)將該頁(yè)寫(xiě)回外存將一頁(yè)從外存換入內(nèi)存修改頁(yè)表100第一百頁(yè)，共171頁(yè)。2.6.2頁(yè)面淘汰頁(yè)面淘汰問(wèn)題（頁(yè)面置換）：要從輔存上把需要的頁(yè)面調(diào)入內(nèi)存，但內(nèi)存中已沒(méi)有空閑頁(yè)框可供分配使用，那么就必須從內(nèi)存中選擇一頁(yè)，然后把它調(diào)出內(nèi)存，以便為即將調(diào)入的頁(yè)面讓出塊空間。頁(yè)面置換是由缺頁(yè)中斷引起的，但是缺頁(yè)中斷不一定都引起頁(yè)面置換。101第一百零一頁(yè)，共171頁(yè)。頁(yè)淘汰在內(nèi)存中選中了一個(gè)淘汰的頁(yè)面，如果該頁(yè)面在內(nèi)存時(shí)未被修改過(guò)，那么就可以直接用調(diào)入的頁(yè)面將其覆蓋掉；如果該頁(yè)面在內(nèi)存時(shí)被修改過(guò)，那么就必須把它寫(xiě)回到磁盤(pán)。以便更新該頁(yè)在輔存上的副本。一個(gè)頁(yè)面的內(nèi)容在內(nèi)存時(shí)是否被修改過(guò)，這樣的信息可以通過(guò)頁(yè)表表目反映出來(lái)。102第一百零二頁(yè)，共171頁(yè)?！岸秳?dòng)”或“顛簸”現(xiàn)象抖動(dòng)－進(jìn)程塊頻繁的換入換出當(dāng)操作系統(tǒng)取進(jìn)一頁(yè)時(shí)，它必須扔出一頁(yè)。如果一塊正好在將要被用到之前扔出，操作系統(tǒng)又不得不幾乎立即把它取回來(lái)，太多的這類(lèi)操作會(huì)導(dǎo)致“系統(tǒng)抖動(dòng)”，處理器的大多數(shù)時(shí)間都用于交換頁(yè)，而不是執(zhí)行指令。改進(jìn)抖動(dòng)的許多復(fù)雜但有效的算法，從本質(zhì)上看是，操作系統(tǒng)試圖根據(jù)最近的歷史來(lái)猜測(cè)在不遠(yuǎn)的將來(lái)最可能用到的頁(yè)。103第一百零三頁(yè)，共171頁(yè)。頁(yè)面淘汰算法功能：需要調(diào)入頁(yè)面時(shí)，選擇內(nèi)存中哪個(gè)物理頁(yè)面被置換。目標(biāo)：把未來(lái)不再使用的或短期內(nèi)較少使用的頁(yè)面調(diào)出，通常只能在局部性原理指導(dǎo)下依據(jù)過(guò)去的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行預(yù)測(cè)。104第一百零四頁(yè)，共171頁(yè)。頁(yè)面走向一個(gè)程序執(zhí)行過(guò)程中頁(yè)面的變化序列稱(chēng)為“頁(yè)面走向”。Load1#,1120Add1#,2410Store1#,1124200030001000第0頁(yè)第1頁(yè)第2頁(yè)01KB2KB3KB100104108112011242410虛地址頁(yè)面走向100（0，100）01120（1，96）1104（0，104）02410（2，354）2108（0，108）01124（1，100）1105第一百零五頁(yè)，共171頁(yè)。缺頁(yè)中斷率假定一個(gè)作業(yè)運(yùn)行的頁(yè)面走向中涉及到的頁(yè)面總數(shù)為A，其中有F次缺頁(yè)，必須通過(guò)缺頁(yè)中斷把它們調(diào)入內(nèi)存。我們定義：f＝F/A稱(chēng)f為“缺頁(yè)中斷率”106第一百零六頁(yè)，共171頁(yè)。1.最佳(Optimal)置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁(yè)面，將是以后永不使用的，或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。采用最佳置換算法，通常可保證獲得最低的缺頁(yè)率。107第一百零七頁(yè)，共171頁(yè)。假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁(yè)面號(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è)頁(yè)面裝入內(nèi)存。以后，當(dāng)進(jìn)程要訪問(wèn)頁(yè)面2時(shí)，將會(huì)產(chǎn)生缺頁(yè)中斷。此時(shí)OS根據(jù)最佳置換算法，將選擇頁(yè)面7予以淘汰。108第一百零八頁(yè)，共171頁(yè)。2.先進(jìn)先出(FIFO)頁(yè)面置換算法選擇建立最早的頁(yè)面被置換?？梢酝ㄟ^(guò)鏈表來(lái)表示各頁(yè)的建立時(shí)間先后。性能較差。較早調(diào)入的頁(yè)往往是經(jīng)常被訪問(wèn)的頁(yè)，這些頁(yè)在FIFO算法下被反復(fù)調(diào)入和調(diào)出。并且有Belady現(xiàn)象。109第一百零九頁(yè)，共171頁(yè)。舉例：123412512345123412555344123412225331234111255×××××××××頁(yè)面走向3個(gè)內(nèi)存塊缺頁(yè)計(jì)數(shù)缺頁(yè)中斷率：f＝9/12＝75％FIFO算法著眼點(diǎn)：認(rèn)為隨時(shí)間推移，在內(nèi)存中呆得最長(zhǎng)得頁(yè)面，被訪問(wèn)得可能性最小。110第一百一十頁(yè)，共171頁(yè)。如果在內(nèi)存中分配4個(gè)頁(yè)面，則缺頁(yè)情況如下：12次訪問(wèn)中有缺頁(yè)10次；111第一百一十一頁(yè)，共171頁(yè)。2.最近最少使用(LRU)置換算法

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

3)可變分配局部置換(VariableAllocation,LocalReplacemen126第一百二十六頁(yè)，共171頁(yè)。1)固定分配局部置換(FixedAllocation,LocalReplacement)

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

在采用這種策略時(shí)，先為系統(tǒng)中的每個(gè)進(jìn)程分配一定數(shù)目的物理頁(yè)架，而OS自身也保持一個(gè)空閑頁(yè)架隊(duì)列。當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁(yè)時(shí)，由系統(tǒng)從空閑頁(yè)架隊(duì)列中，取出一個(gè)頁(yè)架分配給該進(jìn)程，并將欲調(diào)入的（缺）頁(yè)裝入其中。這樣，凡產(chǎn)生缺頁(yè)（中斷）的進(jìn)程，都將獲得新的頁(yè)架。僅當(dāng)空閑頁(yè)架隊(duì)列中的頁(yè)架用完時(shí)，OS才能從內(nèi)存中選擇一頁(yè)調(diào)出，該頁(yè)可能是系統(tǒng)中任一進(jìn)程的頁(yè)，這樣自然又會(huì)使那個(gè)進(jìn)程的頁(yè)架減少，進(jìn)而使其缺頁(yè)率增加。128第一百二十八頁(yè)，共171頁(yè)。3)可變分配局部置換(VariableAllocation,LocalReplacemen)它同樣是基于進(jìn)程的類(lèi)型或根據(jù)程序員的要求，為每個(gè)進(jìn)程分配一定數(shù)目的頁(yè)架，但當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁(yè)時(shí)，只允許從該進(jìn)程在內(nèi)存的頁(yè)面中選出一頁(yè)換出，這樣就不會(huì)影響其它進(jìn)程的運(yùn)行。如果進(jìn)程在運(yùn)行中頻繁發(fā)生缺頁(yè)中斷，則系統(tǒng)須再為該進(jìn)程分配若干附加的頁(yè)架，直至該進(jìn)程的缺頁(yè)率減少到適當(dāng)程度為止；反之，若一個(gè)進(jìn)程在運(yùn)行過(guò)程中的缺頁(yè)中斷率特別低，則此時(shí)可適當(dāng)減少分配給該進(jìn)程的頁(yè)架數(shù)，但不應(yīng)引起其缺頁(yè)率的明顯增加。129第一百二十九頁(yè)，共171頁(yè)。（補(bǔ)充）調(diào)頁(yè)策略1.何時(shí)調(diào)入頁(yè)面預(yù)調(diào)頁(yè)策略如果進(jìn)程的許多頁(yè)是存放在外存的一個(gè)連續(xù)區(qū)域中，則一次調(diào)入若干個(gè)相鄰的頁(yè)，會(huì)比一次調(diào)入一頁(yè)更高效些?？刹捎靡环N以預(yù)測(cè)為基礎(chǔ)的預(yù)調(diào)頁(yè)策略，將那些預(yù)計(jì)在不久以后便會(huì)被訪問(wèn)的頁(yè)面，預(yù)先調(diào)入內(nèi)存。2)請(qǐng)求調(diào)頁(yè)策略

當(dāng)進(jìn)程在運(yùn)行中需要訪問(wèn)某部分程序和數(shù)據(jù)時(shí)，若發(fā)現(xiàn)其所在的頁(yè)面不在內(nèi)存，便立即提出請(qǐng)求，由OS將其所需頁(yè)面調(diào)入內(nèi)存。130第一百三十頁(yè)，共171頁(yè)。2.從何處調(diào)入頁(yè)面在請(qǐng)求分頁(yè)系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對(duì)換頁(yè)面的對(duì)換區(qū)。通常，由于對(duì)換區(qū)是采用連續(xù)分配方式，而文件區(qū)是采用離散分配方式，故對(duì)換區(qū)的磁盤(pán)I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁(yè)請(qǐng)求時(shí)，系統(tǒng)應(yīng)從何處將缺頁(yè)調(diào)入內(nèi)存，可分成如下三種情況：

(1)系統(tǒng)擁有足夠的對(duì)換區(qū)空間，這時(shí)可以全部從對(duì)換區(qū)調(diào)入所需頁(yè)面，以提高調(diào)頁(yè)速度。為此，在進(jìn)程運(yùn)行前，便須將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對(duì)換區(qū)。131第一百三十一頁(yè)，共171頁(yè)。(2)系統(tǒng)缺少足夠的對(duì)換區(qū)空間，這時(shí)凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁(yè)面時(shí)，由于它們未被修改而不必再將它們換出，以后再調(diào)入時(shí)，仍從文件區(qū)直接調(diào)入。但對(duì)于那些可能被修改的部分，在將它們換出時(shí)，便須調(diào)到對(duì)換區(qū)，以后需要時(shí)，再?gòu)膶?duì)換區(qū)調(diào)入。(3)

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

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

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

（2）基于上述訪問(wèn)序列，虛地址1565H的物理地址是多少？請(qǐng)說(shuō)明理由。143第一百四十三頁(yè)，共171頁(yè)。例.作業(yè)Ａ的頁(yè)面映象表如下圖所示：（一頁(yè)=一塊=1024字節(jié)）頁(yè)號(hào)塊號(hào)中斷位訪問(wèn)位修改位輔存地址０８１１１１０００１５１００３０００２７１１０５０００３０００８０００問(wèn)：①指出頁(yè)表中中斷位、訪問(wèn)位、修改位、輔存地址的含義？②當(dāng)執(zhí)行到１０００單元的指令“ＬＯＡＤ１，１８００”時(shí)，系統(tǒng)是怎樣進(jìn)行地址變換（即１８００在主存的哪個(gè)單元中）③當(dāng)執(zhí)行到１５００單元指令（ＬＯＡＤ１，３６００）時(shí)，會(huì)發(fā)生什么現(xiàn)象？144第一百四十四頁(yè)，共171頁(yè)。4.4.1分段存儲(chǔ)管理方式的引入引入分段存儲(chǔ)管理方式，主要是為了滿(mǎn)足用戶(hù)和程序員的下述一系列需要：1)方便編程2)信息共享3)信息保護(hù)4)動(dòng)態(tài)增長(zhǎng)5)動(dòng)態(tài)鏈接2.7段式存儲(chǔ)管理145第一百四十五頁(yè)，共171頁(yè)。在段式存儲(chǔ)管理系統(tǒng)中，用戶(hù)可以根據(jù)邏輯結(jié)構(gòu)將程序分成若干段，每一段的虛擬地址空間各自都從0開(kāi)始編址，因此整個(gè)作業(yè)的虛擬地址空間是二維的。146第一百四十六頁(yè)，共171頁(yè)。分段系統(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的硬件支持，然后通過(guò)地址映射機(jī)構(gòu)將段式虛地址轉(zhuǎn)換為實(shí)際的內(nèi)存物理地址。147第一百四十七頁(yè)，共171頁(yè)。1.分段分段地址中的地址具有如下結(jié)構(gòu)：段號(hào)段內(nèi)地址3116150每個(gè)段都從0開(kāi)始編址，并采用一段連續(xù)的地址空間。各段長(zhǎng)度不等。主存分配以段為單位，每一個(gè)段要分配一個(gè)連續(xù)的主存分區(qū)，各個(gè)段之間不必相鄰。在段式存儲(chǔ)系統(tǒng)中，指令的虛擬地址字分為段號(hào)s和段內(nèi)偏移d兩個(gè)部分。148第一百四十八頁(yè)，共171頁(yè)。2.段表149第一百四十九頁(yè)，共171頁(yè)。類(lèi)似于頁(yè)式管理，段式管理要通過(guò)一個(gè)段表來(lái)進(jìn)行地址變換。系統(tǒng)為在主存中的每一個(gè)作業(yè)建立一張段表。在段表中包含作業(yè)中各段的長(zhǎng)度、在主存的起始地址、在輔存中的存放地址及狀態(tài)域。系統(tǒng)還要集中建立一張所有作業(yè)的段表起始地址和長(zhǎng)度的表，并將當(dāng)前作業(yè)的段表起始地址和長(zhǎng)度裝入段表控制寄存器150第一百五十頁(yè)，共171頁(yè)。151第一百五十一頁(yè)，共171頁(yè)。3.地址變換機(jī)構(gòu)152第一百五十二頁(yè)，共171頁(yè)。4.分頁(yè)和分段的主要區(qū)別(1)頁(yè)是信息的物理單位，分頁(yè)是為實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率?；蛘哒f(shuō)，分頁(yè)僅僅是由于系統(tǒng)管理的需要而不是用戶(hù)的需要。段則是信息的邏輯單位，它含有一組其意義相對(duì)完整的信息。分段的目的是為了能更好地滿(mǎn)足用戶(hù)的需要。153第一百五十三頁(yè)，共171頁(yè)。(2)