計(jì)算機(jī)操作系統(tǒng)第5章PPT課件

.,1,計(jì)算機(jī)操作系統(tǒng),第5章內(nèi)存管理,.,2,目錄,5.1概述5.2地址重定位5.3分區(qū)存儲(chǔ)管理5.4頁式存儲(chǔ)管理5.5段式與段頁式存儲(chǔ)管理5.6內(nèi)存擴(kuò)充技術(shù)5.7虛擬存儲(chǔ)管理,.,3,學(xué)習(xí)目標(biāo),了解存儲(chǔ)管理的目的與功能，熟悉各種存儲(chǔ)器管理的方式及其實(shí)現(xiàn)方法。了解重定位、虛擬存儲(chǔ)器的概念以及其技術(shù)。掌握分區(qū)、頁式、段式與段頁式存儲(chǔ)管理的實(shí)現(xiàn)原理和實(shí)現(xiàn)方法。掌握虛擬存儲(chǔ)器中的頁面置換算法及請求分頁系統(tǒng)性能分析。,.,4,5.1.1存儲(chǔ)層次結(jié)構(gòu),第一層次是高速、昂貴而容量很小的高速緩沖存儲(chǔ)器（Cache）和寄存器；第二層次是速度快、價(jià)格高而數(shù)據(jù)易丟失的內(nèi)存和磁盤緩存；第三層次是速度較低、價(jià)格低廉、容量極大而存儲(chǔ)內(nèi)容不易丟失的外存和可移動(dòng)磁盤介質(zhì)，如硬盤、光盤、U盤等。,.,5,圖5.1存儲(chǔ)層次結(jié)構(gòu),5.1.1存儲(chǔ)層次結(jié)構(gòu),.,6,5.1.1存儲(chǔ)層次結(jié)構(gòu),1內(nèi)存主存儲(chǔ)器簡稱內(nèi)存或主存，是計(jì)算機(jī)系統(tǒng)中的主要部件，用于保存進(jìn)程運(yùn)行時(shí)的程序和數(shù)據(jù)，也稱可執(zhí)行存儲(chǔ)器。2寄存器寄存器具有與處理機(jī)相同的速度，故對寄存器的訪問速度最快，完全能與CPU協(xié)調(diào)工作，但價(jià)格卻十分昂貴，因此容量不可能做得很大。,.,7,5.1.1存儲(chǔ)層次結(jié)構(gòu),3高速緩沖存儲(chǔ)器高速緩存是現(xiàn)代計(jì)算機(jī)結(jié)構(gòu)中的一個(gè)重要部件，它是介于寄存器和存儲(chǔ)器之間的存儲(chǔ)器，主要用于備份主存中較常用的數(shù)據(jù)，以減少處理機(jī)對主存儲(chǔ)器的訪問次數(shù)，這樣可大幅度地提高程序執(zhí)行速度。高速緩存容量遠(yuǎn)大于寄存器，而比內(nèi)存約小兩到三個(gè)數(shù)量級左右，從幾十KB到幾MB，訪問速度快于主存儲(chǔ)器。,.,8,5.1.1存儲(chǔ)層次結(jié)構(gòu),4磁盤緩存由于目前磁盤的I/O速度遠(yuǎn)低于對主存的訪問速度，為了緩和兩者之間在速度上的不匹配，而設(shè)置了磁盤緩存，主要用于暫時(shí)存放頻繁使用的一部分磁盤數(shù)據(jù)和信息，以減少訪問磁盤的次數(shù)。但磁盤緩存與高速緩存不同，它本身并不是一種實(shí)際存在的存儲(chǔ)器，而是利用主存中的部分存儲(chǔ)空間暫時(shí)存放從磁盤中讀出(或?qū)懭?的信息。主存也可以看作是輔存的高速緩存，因?yàn)?，輔存中的數(shù)據(jù)必須復(fù)制到主存方能使用，反之，數(shù)據(jù)也必須先存在主存中，才能輸出到輔存。,.,9,5.1.2存儲(chǔ)管理目的和任務(wù),操作系統(tǒng)的存儲(chǔ)管理機(jī)構(gòu)必須盡可能方便用戶和提高內(nèi)存的使用效率，使內(nèi)存在成本、速度和規(guī)模之間獲得較好的權(quán)衡1內(nèi)存分配2地址映射3內(nèi)存共享與保護(hù)4內(nèi)存擴(kuò)充,.,10,5.1.2存儲(chǔ)管理目的和任務(wù),1內(nèi)存分配各個(gè)作業(yè)裝入內(nèi)存時(shí)，必須按照規(guī)定的方式向操作系統(tǒng)提出申請，由存儲(chǔ)管理進(jìn)行統(tǒng)一分配。存儲(chǔ)管理設(shè)置一張表格記錄存儲(chǔ)空間的分配情況，根據(jù)申請的要求按一定的策略分析存儲(chǔ)空間的使用情況，找出足夠的空閑區(qū)域進(jìn)行分配。當(dāng)內(nèi)存中某個(gè)作業(yè)撤離或主動(dòng)歸還內(nèi)存資源時(shí)，存儲(chǔ)管理要收回它所占用的全部或部分存儲(chǔ)空間，使它們成為空閑區(qū)域，同時(shí)還要修改表格的相關(guān)項(xiàng)。收回存儲(chǔ)區(qū)域的工作也稱釋放存儲(chǔ)空間。,.,11,5.1.2存儲(chǔ)管理目的和任務(wù),2地址映射內(nèi)存中往往同時(shí)存放多個(gè)作業(yè)程序，而這些程序在內(nèi)存中的位置是不能預(yù)先知道的，所以用戶在編寫程序時(shí)不能使用絕對地址。計(jì)算機(jī)的指令中地址部分所指示的地址通常是邏輯地址，用戶按邏輯地址編寫程序。當(dāng)要把程序裝入運(yùn)行時(shí)，操作系統(tǒng)要為其分配一個(gè)合適的內(nèi)存空間，必須把邏輯地址轉(zhuǎn)換成物理地址才能得到信息的真實(shí)存放處。把邏輯地址轉(zhuǎn)換成物理地址的工作稱為地址轉(zhuǎn)換。,.,12,5.1.2存儲(chǔ)管理目的和任務(wù),3內(nèi)存共享與保護(hù)所謂內(nèi)存空間共享，一方面是指采用多道程序設(shè)計(jì)技術(shù)使若干個(gè)程序同時(shí)進(jìn)入內(nèi)存，各自占用一定數(shù)量的存儲(chǔ)空間，即共享內(nèi)存資源，共同使用一個(gè)內(nèi)存；另一方面是指若干個(gè)作業(yè)有共同的程序段或數(shù)據(jù)段時(shí)，可將這些共同的程序段或數(shù)據(jù)段存放在某個(gè)存儲(chǔ)區(qū)域內(nèi)，各作業(yè)執(zhí)行時(shí)都可訪問它們，即共享內(nèi)存的某些區(qū)域。內(nèi)存共享使得內(nèi)存中不僅有系統(tǒng)程序，而且還有若干道用戶程序。為了避免內(nèi)存中的多道程序相互干擾，必須對內(nèi)存中的程序和數(shù)據(jù)進(jìn)行保護(hù)。,.,13,5.1.2存儲(chǔ)管理目的和任務(wù),3內(nèi)存共享與保護(hù)最基本的保護(hù)措施是規(guī)定各道程序只能訪問屬于自己的那些存儲(chǔ)區(qū)域內(nèi)的信息，對公共區(qū)域的訪問可以加以限制，一般地說，一個(gè)程序執(zhí)行時(shí)可能有以下三種情況：對屬于自己的內(nèi)存區(qū)域內(nèi)的數(shù)據(jù)既可讀又可寫；對公共區(qū)域中允許共享的信息或可使用的別的用戶的信息可讀而不可寫；對未獲得授權(quán)的信息，既不可讀又不可寫。,.,14,5.1.2存儲(chǔ)管理目的和任務(wù),4內(nèi)存擴(kuò)充為方便用戶編寫程序，使用戶編寫程序時(shí)不受內(nèi)存實(shí)際容量的限制，可以采用一定的技術(shù)擴(kuò)充內(nèi)存容量，得到比實(shí)際容量更大的內(nèi)存空間。這里的擴(kuò)充不是對物理內(nèi)存容量的擴(kuò)充，而是指利用存儲(chǔ)管理技術(shù)為程序的運(yùn)行提供一個(gè)比實(shí)際內(nèi)存更大的邏輯存儲(chǔ)空間，即所謂的虛擬存儲(chǔ)管理技術(shù)。當(dāng)一個(gè)大型的程序要裝入內(nèi)存時(shí)，可先把其中的一部分裝入內(nèi)存，其余部分存放在磁盤上，如果程序執(zhí)行中需要用到不在內(nèi)存中的信息時(shí)，則由操作系統(tǒng)采用覆蓋技術(shù)將其調(diào)入內(nèi)存。,.,15,5.2地址重定位,一個(gè)邏輯地址空間的程序裝入到物理地址空間時(shí)，由于兩個(gè)空間不一致，需要進(jìn)行地址變換，稱為地址重定位。此時(shí)，相對地址空間（也稱為邏輯地址空間）通過地址重定位機(jī)構(gòu)轉(zhuǎn)換到絕對地址空間（也稱為物理地址空間）。,.,16,5.2地址重定位,地址空間是邏輯地址的集合，存儲(chǔ)空間是物理地址的集合。名字空間、地址空間和存儲(chǔ)空間的關(guān)系如圖5.2所示,圖5.2名字空間、地址空間和存儲(chǔ)空間,.,程序的裝入和鏈接,用戶程序要在系統(tǒng)中運(yùn)行，必須先將它裝入內(nèi)存，然后再將其轉(zhuǎn)變?yōu)橐粋€(gè)可以執(zhí)行的程序，通常都要經(jīng)過以下幾個(gè)步驟：(1)編譯，由編譯程序(Compiler)對用戶源程序進(jìn)行編譯，形成若干個(gè)目標(biāo)模塊(ObjectModule)；(2)鏈接，由鏈接程序(Linker)將編譯后形成的一組目標(biāo)模塊以及它們所需要的庫函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊(LoadModule)；(3)裝入，由裝入程序(Loader)將裝入模塊裝入內(nèi)存。圖a給出了這樣的三步過程,.,程序的裝入和鏈接,圖a對用戶程序的處理步驟,.,程序的裝入,1.絕對裝入方式(AbsoluteLoadingMode)編譯時(shí)，若知道程序?qū)Ⅰv留在內(nèi)存的某位置，則編譯程序?qū)a(chǎn)生絕對地址的目標(biāo)代碼，絕對裝入程序按照裝入模塊的地址，將程序和數(shù)據(jù)直接裝入指定內(nèi)存。該地址既可在編譯和匯編時(shí)給出，也可以由程序員直接賦予。程序員直接給出絕對地址，使得程序修改時(shí)很可能要修改所有地址。因此寧可在程序中采用符號地址，在編譯時(shí)再去轉(zhuǎn)換成絕對地址。單道程序環(huán)境下，可用此種方式。而在多道程序環(huán)境下，目標(biāo)模塊的起始地址通常從0開始，程序中的其他地址，都相對于起始地址計(jì)算。這樣的模塊稱為相對裝入模塊。,.,程序JUMPiLOADjDATA,JUMP400LOAD1200,JUMP1424LOAD2224,符號地址,絕對地址,相對地址,i,j,1024,1424,2224,0,400,1200,絕對和可重定位裝入模塊,（a）目標(biāo)模塊,（b）絕對裝入模塊,（c）相對裝入模塊,.,程序的裝入,2.可重定位裝入方式(RelocationLoadingMode)把在裝入時(shí)對目標(biāo)程序中的指令和數(shù)據(jù)地址的修改過程稱為重定位。對于相對裝入模塊，應(yīng)采用可重定位裝入方式來把裝入模塊裝入內(nèi)存。裝入相對裝入模塊時(shí)，裝入程序要將模塊的起始地址與內(nèi)存某位置的地址相加，才能將模塊定位到正確的物理地址，同樣，模塊中的指令地址和數(shù)據(jù)地址都要相應(yīng)修改。因地址變換只是在裝入時(shí)一次完成，以后不再改變，故稱為靜態(tài)重定位。,.,LOAD1,2500,365,0,1000,2500,5000,作業(yè)地址空間,LOAD1,12500,365,11000,12500,15000,內(nèi)存空間,作業(yè)裝入內(nèi)存時(shí)的情況,10000,.,程序的裝入,3.動(dòng)態(tài)運(yùn)行時(shí)的裝入方式(DynamicRun-timeLoading)多道程序環(huán)境下，程序在內(nèi)存的位置可能要經(jīng)常改變，如進(jìn)程的換入換出，每次換入到內(nèi)存的位置一般是不同的，這樣，就應(yīng)采用動(dòng)態(tài)運(yùn)行時(shí)的裝入方式。動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是等到程序真正要執(zhí)行時(shí)才進(jìn)行地址轉(zhuǎn)換(轉(zhuǎn)換時(shí)機(jī)的把握)。因此，裝入內(nèi)存后的所有地址仍是相對地址。為使地址轉(zhuǎn)換不影響指令的執(zhí)行速度，這種方式需要一定的特殊硬件的支持。,.,程序的鏈接,實(shí)現(xiàn)鏈接的方法有三種：靜態(tài)鏈接、裝入時(shí)動(dòng)態(tài)鏈接和運(yùn)行時(shí)動(dòng)態(tài)鏈接。1、靜態(tài)鏈接：,模塊ACALLB:RETURN,模塊BCALLC:RETURN,模塊CRETURN,模塊AJSR“L”RETURN,模塊BJSR“L+M”RETURN,模塊CRETURN,0,L-1,0,M-1,0,N-1,0,L-1,L,L+M-1,L+M,L+M+N-1,需要解決的兩個(gè)問題：1、對相對地址進(jìn)行修改2、變換外部調(diào)用符號,目標(biāo)模塊,裝入模塊,圖b程序鏈接示意圖,.,程序的鏈接,2.裝入時(shí)動(dòng)態(tài)鏈接(Load-timeDynamicLinking)這是指將用戶源程序編譯后所得到的一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接的鏈接方式。即在裝入一個(gè)目標(biāo)模塊時(shí)，若發(fā)生一個(gè)外部模塊調(diào)用事件，將引起裝入程序去找出相應(yīng)的外部目標(biāo)模塊，并將它裝入內(nèi)存，還要按照圖b所示的方式修改目標(biāo)模塊中的相對地址。裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)：(1)便于修改和更新。(2)便于實(shí)現(xiàn)對目標(biāo)模塊的共享。,.,程序的裝入,3.運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-timeDynamicLinking)這種鏈接方式，可將某些目標(biāo)模塊的鏈接，推遲到執(zhí)行時(shí)才進(jìn)行。即在執(zhí)行過程中，若發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，由OS去找到該模塊，將它裝入內(nèi)存，并把它鏈接到調(diào)用者模塊上。,.,27,5.3分區(qū)存儲(chǔ)管理,5.3.1單一連續(xù)分區(qū)存儲(chǔ)管理這是最簡單的一種存儲(chǔ)管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。在單道程序環(huán)境下，當(dāng)時(shí)的存儲(chǔ)器管理方式是把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，它通常是放在內(nèi)存的低址部分。而在用戶區(qū)內(nèi)存中，僅裝有一道用戶程序，即整個(gè)內(nèi)存的用戶空間由該程序獨(dú)占。這樣的存儲(chǔ)器分配方式被稱為單一連續(xù)分配方式。,.,28,5.3分區(qū)存儲(chǔ)管理,5.3.2固定分區(qū)管理固定分區(qū)式分配是最簡單的一種可運(yùn)行多道程序的存儲(chǔ)管理方式。這是將內(nèi)存用戶空間劃分為若干個(gè)固定大小的區(qū)域，在每個(gè)分區(qū)中只裝入一道作業(yè)，這樣，把用戶空間劃分為幾個(gè)分區(qū)，便允許有幾道作業(yè)并發(fā)運(yùn)行。當(dāng)某一分區(qū)空閑時(shí)，便可以從外存的后備作業(yè)隊(duì)列中選擇一個(gè)適當(dāng)大小的作業(yè)裝入該分區(qū)，當(dāng)該作業(yè)結(jié)束時(shí)，又可再從后備作業(yè)隊(duì)列中找出另一作業(yè)調(diào)入該分區(qū)。,.,29,5.3分區(qū)存儲(chǔ)管理,5.3.2固定分區(qū)管理1.劃分分區(qū)的方法(1)分區(qū)大小相等(指所有的內(nèi)存分區(qū)大小相等)。(2)分區(qū)大小不等。將內(nèi)存劃分出多個(gè)較小的分區(qū)，適量的中等分區(qū)和少量的大分區(qū)。2.內(nèi)存分配為了便于內(nèi)存分配，通常將分區(qū)按其大小進(jìn)行排隊(duì)，并為之建立一張分區(qū)使用表，其中各表項(xiàng)包括每個(gè)分區(qū)的起始地址、大小及狀態(tài)(是否已分配)，如圖5.5所示。,.,30,5.3分區(qū)存儲(chǔ)管理,圖5.5固定分區(qū)分配,.,31,5.3分區(qū)存儲(chǔ)管理,5.3.3可變分區(qū)管理（動(dòng)態(tài)分區(qū)管理）固定分區(qū)分配是最早的多道程序存儲(chǔ)管理方式，由于每個(gè)分區(qū)的大小固定，必然會(huì)造成存儲(chǔ)空間的浪費(fèi)?？勺兎謪^(qū)分配是指在系統(tǒng)運(yùn)行的過程中根據(jù)作業(yè)對內(nèi)存的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間的一種分區(qū)方法。可變分區(qū)分配是在作業(yè)裝入和處理過程中建立的分區(qū)，并使分區(qū)的大小與作業(yè)的大小相等。分區(qū)的個(gè)數(shù)和大小不是固定不變的，而是根據(jù)裝入的作業(yè)動(dòng)態(tài)地劃分。,.,5.3.3可變分區(qū)管理,1.可變分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)常用的數(shù)據(jù)結(jié)構(gòu)有以下兩種形式：空閑分區(qū)表，在系統(tǒng)中設(shè)置一張空閑分區(qū)表，用于記錄每個(gè)空閑分區(qū)的情況。每個(gè)空閑分區(qū)占一個(gè)表目，表目中包括分區(qū)號、分區(qū)大小和分區(qū)始址等數(shù)據(jù)項(xiàng)。空閑分區(qū)鏈。為了實(shí)現(xiàn)對空閑分區(qū)的分配和鏈接，在每個(gè)分區(qū)的起始部分設(shè)置一些用于控制分區(qū)分配的信息，以及用于鏈接各分區(qū)所用的前向指針，在分區(qū)尾部則設(shè)置一后向指針。通過前、后向鏈接指針，可將所有的空閑分區(qū)鏈接成一個(gè)雙向鏈。,.,5.3.3可變分區(qū)管理,2.分區(qū)分配操作1)分配內(nèi)存系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈(表)中找到所需大小的分區(qū)。設(shè)請求的分區(qū)大小為u.size，表中每個(gè)空閑分區(qū)的大小可表示為m.size。,.,內(nèi)存分配流程,size為內(nèi)存中允許存在的最小內(nèi)存空間尺寸,.,5.3.3可變分區(qū)管理,2)回收內(nèi)存當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈(表)中找到相應(yīng)的插入點(diǎn)，此時(shí)可能出現(xiàn)以下四種情況之一：(1)回收區(qū)與插入點(diǎn)的前一個(gè)空閑分區(qū)F1相鄰接。(2)回收分區(qū)與插入點(diǎn)的后一空閑分區(qū)F2相鄰接。(3)回收區(qū)同時(shí)與插入點(diǎn)的前、后兩個(gè)分區(qū)鄰接。(4)回收區(qū)既不與F1鄰接，又不與F2鄰接。這時(shí)應(yīng)為回收區(qū)單獨(dú)建立一個(gè)新表項(xiàng)，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈中的適當(dāng)位置。,.,36,5.3.4分區(qū)分配算法,可變分區(qū)分配常采用的幾種分配算法：1.首次適應(yīng)算法2.最優(yōu)適應(yīng)算法3.最差適應(yīng)算法4.循環(huán)首次適應(yīng)算法5.快速適應(yīng)算法,.,37,1.首次適應(yīng)算法,該算法要求分區(qū)鏈以地址遞增的次序鏈接。內(nèi)存分配時(shí)，從鏈?zhǔn)组_始順序查找，直至找到一個(gè)能滿足其大小要求的空閑區(qū)為止。然后，再按照作業(yè)的大小，從該區(qū)中劃出一塊內(nèi)存分配給請求者，余下的空閑分區(qū)仍留在空閑鏈中。該算法傾向于優(yōu)先利用內(nèi)存中低址部分的空閑區(qū)，高址部分的很少利用，從而保留了高址部分的大空閑區(qū)，為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。但低址部分留下許多難以利用的很小的空閑區(qū)，每次查找又都從低址部分開始，這樣，增加了查找開銷。,.,38,2.循環(huán)首次適應(yīng)算法,由首次適應(yīng)算法演變而來，分配內(nèi)存時(shí)，不再每次從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直到找到第一個(gè)能滿足要求的空閑分區(qū)，從中劃出一塊與請求大小相等的內(nèi)存空間。為實(shí)現(xiàn)該算法，應(yīng)設(shè)置一起始查詢指針，并采用循環(huán)查找方式。該算法能使內(nèi)存中的空閑分區(qū)分布得更均勻，減少查找空閑分區(qū)的開銷，但這會(huì)缺乏大的空閑分區(qū)。,.,39,3.最佳適應(yīng)算法,“最佳”的含義是指每次為作業(yè)分配內(nèi)存時(shí)，總是把既能滿足要求又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。為加速查詢，該算法要求將所有的空閑區(qū)按其大小以遞增的順序鏈接成一空閑區(qū)鏈。這樣，第一次找到的滿足要求的空閑區(qū)，必然是最優(yōu)的。孤立地看，這似乎是最佳的，但從宏觀上看卻不一定。因?yàn)槊看畏峙浜笏懈钕碌氖Ｓ嗖糠?，總是最小的，在存?chǔ)器中會(huì)留下許多難以利用的小空閑區(qū)。,.,40,4.最差適應(yīng)算法,由于最壞適應(yīng)分配算法選擇空閑分區(qū)的策略正好與最佳適應(yīng)算法相反：它在掃描整個(gè)空閑分區(qū)表或鏈表時(shí)，總是挑選一個(gè)最大的空閑區(qū)，從中分割一部分存儲(chǔ)空間給作業(yè)使用，以至于存儲(chǔ)器中缺乏大的空閑分區(qū)，故把它稱為是最壞適應(yīng)算法。該算法要求將所有空閑分區(qū)，按容量從大到小的順序，形成一空閑分區(qū)鏈，查找時(shí)，只要看第一個(gè)分區(qū)能否滿足作業(yè)要求即可。,.,動(dòng)態(tài)分區(qū)示例：請使用下面的算法再分配一個(gè)16M的內(nèi)存空間？1.首次適應(yīng)（Firstfit）2.循環(huán)首次適應(yīng)（Nextfit）3.最佳適應(yīng)（Bestfit）4.最差適應(yīng)（Worstfit）,.,最佳適應(yīng),首次適應(yīng),循環(huán)首次適應(yīng),最差適應(yīng),.,43,5.快速適應(yīng)算法（基于索引）,該算法又稱為分類搜索法，是將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表，這樣，系統(tǒng)中存在多個(gè)空閑分區(qū)鏈表，同時(shí)在內(nèi)存中設(shè)立一張管理索引表，該表的每一個(gè)表項(xiàng)對應(yīng)了一種空閑分區(qū)類型，并記錄了該類型空閑分區(qū)鏈表的表頭指針。該算法在搜索空閑分區(qū)時(shí)分二步：第一步是根據(jù)進(jìn)程長度從索引表中找到能容納它的最小空閑區(qū)鏈表；第二步是從鏈表中取下第一塊進(jìn)行分配。,.,44,5.快速適應(yīng)算法,優(yōu)點(diǎn)：查找效率高。另外在進(jìn)行空閑分區(qū)分配時(shí)，不會(huì)對任何分區(qū)產(chǎn)生分割，能保留大的空閑分區(qū)，同時(shí)也不會(huì)產(chǎn)生內(nèi)存碎片。缺點(diǎn)：在分區(qū)歸還時(shí)算法比較復(fù)雜，系統(tǒng)開銷較大。該算法在分配空閑分區(qū)時(shí)是以進(jìn)程為單位，一個(gè)分區(qū)只屬于一個(gè)進(jìn)程，因此在為進(jìn)程所分配的一個(gè)分區(qū)中，或多或少地存在一定的浪費(fèi)。空閑分區(qū)劃分越細(xì)，浪費(fèi)越嚴(yán)重，整體上會(huì)造成可觀的存儲(chǔ)空間浪費(fèi)，這是典型的以空間換時(shí)間的作法。,.,45,哈希算法,哈希算法是利用哈?？焖俨檎业膬?yōu)點(diǎn)，以及空閑分區(qū)在可利用空閑分區(qū)表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，該表的每一個(gè)表項(xiàng)記錄了一個(gè)對應(yīng)的空閑分區(qū)鏈表表頭指針。進(jìn)行空閑分區(qū)分配時(shí)，根據(jù)所需空閑分區(qū)大小，通過哈希函數(shù)計(jì)算，即得到在哈希表中的位置，從中得到相應(yīng)的空閑分區(qū)鏈表，實(shí)現(xiàn)最佳分配策略。,.,46,伙伴系統(tǒng),該算法規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪(k為整數(shù)，lkm)，其中2l表示分配的最小塊的尺寸，2m表示分配的最大的塊的尺寸。通常，2m是可供分配的整個(gè)內(nèi)存的大小。（1）開始時(shí)，可用于分配的整個(gè)空間被看成是一個(gè)大小為2m的塊；（2）如果請求的大小s滿足2m-1s=2m，則分配整個(gè)空間；否則，該塊被分成兩個(gè)大小相等的伙伴，均為2m-1，如果有2m-2s,2,100,段號S,段號,0,3,2,1,+,+,8292,8K,8292,8692,邏輯地址,物理地址,主存,位移量,段表寄存器,越界,.,79,5.5.1段式存儲(chǔ)管理,2.分頁和分段的主要區(qū)別分頁和分段系統(tǒng)有許多相似之處，但在概念上二者完全不同：(1)頁是信息的物理單位，僅僅是出于系統(tǒng)管理的需要；段是信息的邏輯單位，其目的是滿足用戶的需要。(2)頁的大小固定且由系統(tǒng)確定，一個(gè)系統(tǒng)只能有一種大小的頁面；段的長度不固定，決定于用戶所編寫的程序；(3)分頁的作業(yè)地址空間是一維的；分段的作業(yè)地址空間是二維的。(4)通常分段的段內(nèi)空間會(huì)比分頁的頁面空間大，因此段表會(huì)比頁表短。,.,80,5.5.2段頁式存儲(chǔ)管理,1)基本原理段頁式系統(tǒng)的基本原理是分段和分頁原理的結(jié)合，即先將用戶程序分成若干個(gè)段，再把每個(gè)段分成若干個(gè)頁，并為每一個(gè)段賦予一個(gè)段名。在段頁式系統(tǒng)中，其地址結(jié)構(gòu)由段號、段內(nèi)頁號及頁內(nèi)地址三部分所組成，如下圖所示。為實(shí)現(xiàn)從邏輯地址到物理地址的變換，系統(tǒng)需同時(shí)配置段表和頁表，段表的內(nèi)容是頁表始址和頁表長度，這與分段式系統(tǒng)不同。,段號（S）段內(nèi)頁號（P）頁內(nèi)地址（W）,.,圖5.14利用段表和頁表實(shí)現(xiàn)地址映射,5.5.2段頁式存儲(chǔ)管理,.,82,5.5.2段頁式存儲(chǔ)管理,2)地址變換過程在段頁式系統(tǒng)中，為了便于實(shí)現(xiàn)地址變換，需要配置一個(gè)段表寄存器，其中存放段表始址和段表長度。進(jìn)行地址變換時(shí)按如下步驟進(jìn)行：(1)通過段表寄存器將段號與段表長度進(jìn)行比較，如果未越界則查找段表在內(nèi)存中的位置，否則越界中斷；(2)訪問段表，將頁表長度與頁號進(jìn)行比較，如果未越界則根據(jù)段號查找頁表所在的位置；(3)訪問頁表，根據(jù)頁號查找該頁所在的物理塊號；(4)將物理塊號和地址結(jié)構(gòu)中的頁內(nèi)地址相加，形成內(nèi)存單元的物理地址。,.,圖5.15段頁式地址變換過程,5.5.2段頁式存儲(chǔ)管理,.,84,5.6內(nèi)存擴(kuò)充技術(shù),前面所介紹的各種存儲(chǔ)管理方式都有一個(gè)共同的特點(diǎn)，那就是都要求將一個(gè)作業(yè)的全部裝入內(nèi)存后方能運(yùn)行，于是，出現(xiàn)了這樣兩種情況：一是有的作業(yè)很大，其所要求的內(nèi)存空間超過了內(nèi)存空間的總?cè)萘浚鳂I(yè)不能裝入內(nèi)存，導(dǎo)致其無法運(yùn)行；二是有大量的作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將少數(shù)作業(yè)裝入內(nèi)存運(yùn)行，其它大量作業(yè)留在外存等待。出現(xiàn)這兩種情況的原因，都是由于內(nèi)存容量不夠大。一個(gè)明顯的解決辦法就是增加物理內(nèi)存；另一種方法就是從邏輯上來擴(kuò)充內(nèi)存容量。,.,85,5.6.1覆蓋技術(shù),覆蓋技術(shù)是指一個(gè)程序的若干程序段或幾個(gè)程序的某些部分共享某一個(gè)存儲(chǔ)空間。覆蓋技術(shù)的實(shí)現(xiàn)是把程序劃分為若干個(gè)功能上相對獨(dú)立的程序段，按照其自身的邏輯結(jié)構(gòu)使那些不會(huì)同時(shí)執(zhí)行的程序段共享同一塊內(nèi)存區(qū)域。未執(zhí)行的程序段先保存在磁盤上，當(dāng)有關(guān)程序段的前一部分執(zhí)行結(jié)束后，再把后續(xù)程序段調(diào)入內(nèi)存，覆蓋前面的程序段。,.,86,5.6.1覆蓋技術(shù),覆蓋技術(shù)是早期采用的簡單的擴(kuò)充內(nèi)存技術(shù)，對用戶不透明，它要求用戶清楚地了解程序的結(jié)構(gòu)，并指定各程序段調(diào)入內(nèi)存的先后次序，以及內(nèi)存中可以覆蓋掉的程序段的位置等，增加了用戶的負(fù)擔(dān)。而且程序段的最大長度仍受內(nèi)存容量的限制。覆蓋技術(shù)可以由編譯程序提供支持，此時(shí)被覆蓋的塊是由程序員或編譯程序預(yù)先確定的。,.,87,5.6.2交換技術(shù),交換的引入一方面，在內(nèi)存中的某些進(jìn)程由于某事件尚未發(fā)生而被阻塞運(yùn)行，但它卻占用了大量的內(nèi)存空間，甚至有時(shí)可能出現(xiàn)在內(nèi)存中所有進(jìn)程都被阻塞，而無可運(yùn)行之進(jìn)程，迫使CPU停止下來等待的情況；另一方面，卻又有著許多作業(yè)，因內(nèi)存空間不足，一直駐留在外存上，而不能進(jìn)入內(nèi)存運(yùn)行。所謂交換(對換)，是指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程，或暫時(shí)不用的程序和數(shù)據(jù)，換出到外存上，以騰出足夠的內(nèi)存空間，把已具備運(yùn)行條件的進(jìn)程，或進(jìn)程所需的程序和數(shù)據(jù)，換入內(nèi)存。,.,88,5.6.2交換技術(shù),交換技術(shù)的目的是盡可能快的實(shí)現(xiàn)進(jìn)程在內(nèi)、外存之間的交換，從而提高內(nèi)存利用率。早期的交換技術(shù)多用于分時(shí)系統(tǒng)當(dāng)中，大多數(shù)現(xiàn)代操作系統(tǒng)也都使用交換技術(shù)，交換技術(shù)有力地支持了多道程序設(shè)計(jì)，同時(shí)交換技術(shù)也是虛擬存儲(chǔ)技術(shù)的基礎(chǔ)。交換基礎(chǔ)實(shí)施時(shí)需要考慮如下問題：換出進(jìn)程的選擇交換時(shí)機(jī)的確定交換空間的分配換入進(jìn)程換回內(nèi)存時(shí)位置的確定,.,89,5.7虛擬存儲(chǔ)管理5.7.1基本原理,1.常規(guī)存儲(chǔ)器管理方式的特征(1)一次性。作業(yè)在運(yùn)行前需要一次性的將其全部裝入內(nèi)存。但許多作業(yè)在每次運(yùn)行時(shí)，并非其全部程序和數(shù)據(jù)都使用到了，如果一次性的將其全部裝入，實(shí)際上也是對內(nèi)存空間的一種浪費(fèi)。(2)駐留性。作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至作業(yè)運(yùn)行結(jié)束。盡管運(yùn)行中的進(jìn)程會(huì)因各種事件而長期等待，或有些模塊在運(yùn)行過一次以后就不再需要了，但它們?nèi)詫⒗^續(xù)占用寶貴的內(nèi)存資源。,.,90,5.7.1基本原理,2.局部性原理程序運(yùn)行時(shí)存在的局部性現(xiàn)象，很早就已被人發(fā)現(xiàn)，但直到1968年，P.Denning才真正指出：程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律，即在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分，相應(yīng)地，它所訪問的存儲(chǔ)空間也局限于某個(gè)區(qū)域。局限性又表現(xiàn)在下述兩個(gè)方面：(1)時(shí)間局限性。程序中的某條指令被執(zhí)行，不久后會(huì)再次執(zhí)行；某個(gè)數(shù)據(jù)被訪問，不久后將再次被訪問。產(chǎn)生時(shí)間局限性的典型原因是在程序中存在著大量的循環(huán)操作。(2)空間局限性。程序訪問了某個(gè)存儲(chǔ)單元，不久后，其附近的存儲(chǔ)單元也將被訪問。,.,91,5.7.1基本原理,3.虛擬存儲(chǔ)基于局部性原理可知，應(yīng)用程序在運(yùn)行之前沒有必要將之全部裝入內(nèi)存，而僅須將那些當(dāng)前要運(yùn)行的少數(shù)頁面或段先裝入內(nèi)存便可運(yùn)行，其余部分暫留在盤上。局部性原理是實(shí)現(xiàn)虛擬存儲(chǔ)管理的理論基礎(chǔ)。所謂虛擬存儲(chǔ)器是指僅把作業(yè)的一部分裝入內(nèi)存便可運(yùn)行的存儲(chǔ)器系統(tǒng)，是具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。虛擬存儲(chǔ)器的邏輯容量由系統(tǒng)的尋址能力和外存容量之和所決定，與實(shí)際的內(nèi)存容量無關(guān)。,.,92,5.7.1基本原理,虛擬存儲(chǔ)特征(1)多次性：是指一個(gè)作業(yè)被分成多次來調(diào)入內(nèi)存，即作業(yè)運(yùn)行時(shí)不需將其全部裝入內(nèi)存，只需將當(dāng)前要運(yùn)行的那部分程序和數(shù)據(jù)裝入，以后運(yùn)行到某些部分時(shí)再將其調(diào)入。(2)對換性：是指允許作業(yè)中的程序和數(shù)據(jù)，在作業(yè)運(yùn)行過程中換進(jìn)、換出。(3)虛擬性：是指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。虛擬性以多次性和對換性為基礎(chǔ)，多次性和對換性以離散分配為基礎(chǔ)。,.,93,5.7.2請求分頁存儲(chǔ)管理,請求分頁存儲(chǔ)管理系統(tǒng)是在分頁存儲(chǔ)管理系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能和頁面置換功能后形成的頁式虛擬存儲(chǔ)管理系統(tǒng)。1.請求分頁原理請求分頁存儲(chǔ)是建立在分頁存儲(chǔ)管理基礎(chǔ)之上，從靜態(tài)分頁存儲(chǔ)管理發(fā)展而來的。在作業(yè)或進(jìn)程開始執(zhí)行前，不把作業(yè)或進(jìn)程的程序段和數(shù)據(jù)段一次性的全部裝入內(nèi)存，而只是裝入被認(rèn)為是經(jīng)常使用的那一部分。其他部分則在程序執(zhí)行過程中動(dòng)態(tài)的裝入。請求分頁的地址變換過程與靜態(tài)分頁管理方式相同，都是通過頁表查詢出相應(yīng)的塊號之后，再由塊號與頁內(nèi)地址相加得到實(shí)際的物理地址。,.,94,5.7.2請求分頁存儲(chǔ)管理,請求頁表機(jī)制在請求分頁系統(tǒng)中需要的主要數(shù)據(jù)結(jié)構(gòu)是請求頁表，其基本作用仍然是將用戶地址空間中的邏輯地址映射為內(nèi)存空間中的物理地址。為了滿足頁面換進(jìn)換出的需要，在請求頁表中又增加了四個(gè)字段。這樣，在請求分頁系統(tǒng)中的每個(gè)頁表應(yīng)含以下諸項(xiàng)：,頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址,又稱存在位，用于指示該頁是否已調(diào)入內(nèi)存，供程序訪問時(shí)參考。,用于記錄本頁在一段時(shí)間內(nèi)被訪問的次數(shù)，或最近已有多長時(shí)間未被訪問，提供給置換算法選擇換出頁面時(shí)參考。,指示該頁在調(diào)入內(nèi)存后是否被修改過。若未被修改，在置換該頁時(shí)就不需將該頁回寫到外存，否則，就要回寫到外存。,用于指出該頁在外存上的地址，通常是物理塊號，供調(diào)入該頁時(shí)使用。,.,95,5.7.2請求分頁存儲(chǔ)管理,2.缺頁中斷機(jī)構(gòu)每當(dāng)所要訪問的頁面不在內(nèi)存時(shí)，便要產(chǎn)生一次缺頁中斷，請求OS將所缺之頁調(diào)入內(nèi)存。缺頁中斷雖要經(jīng)歷與一般中斷相同的幾個(gè)步驟，但它是一種特殊的中斷，與一般中斷的區(qū)別主要是：(1)在指令執(zhí)行期間產(chǎn)生和處理中斷信號。通常CPU都是在一條指令執(zhí)行完后去檢查是否有中斷請求到達(dá)。有則響應(yīng)，無則繼續(xù)執(zhí)行下一條指令。而缺頁中斷是在指令執(zhí)行期間，發(fā)現(xiàn)所要訪問的指令和數(shù)據(jù)不在內(nèi)存時(shí)產(chǎn)生和處理的。(2)一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。這時(shí)硬件機(jī)構(gòu)應(yīng)能保存多次中斷時(shí)的狀態(tài)，并保證最后能返回到中斷前產(chǎn)生缺頁中斷的指令處，繼續(xù)執(zhí)行。,.,96,CopyAToB,例如：執(zhí)行COPYATOB指令時(shí)，可能要產(chǎn)生6次缺頁中斷,頁面,.,97,5.7.2請求分頁存儲(chǔ)管理,地址變換過程請求分頁系統(tǒng)中的地址變換機(jī)構(gòu)是在分頁系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上，為實(shí)現(xiàn)虛擬存儲(chǔ)器，再增加了某些功能所形成的，如產(chǎn)生和處理缺頁中斷，以及從內(nèi)存中換出一頁的功能等等。圖5.16示出了請求分頁系統(tǒng)中的地址變換過程。,.,98,圖5.16請求分頁中的地址變換過程,.,99,5.7.3頁面置換算法,缺頁率假設(shè)一個(gè)進(jìn)程的邏輯空間為n頁，系統(tǒng)為其分配的內(nèi)存物理塊數(shù)為m(mn)。如果在進(jìn)程的運(yùn)行過程中，訪問頁面成功(即所訪問頁面在內(nèi)存中)的次數(shù)為S，訪問頁面失敗(即所訪問頁面不在內(nèi)存中，需要從外存調(diào)入)的次數(shù)為F，則該進(jìn)程總的頁面訪問次數(shù)為A=S+F，那么該進(jìn)程在其運(yùn)行過程中的缺頁率即為缺頁率的影響因素:1)頁面大?。?)進(jìn)程分配物理塊的數(shù)目；3)頁面置換算法；4)程序固有特性。,.,100,5.7.3頁面置換算法,在請求分頁存儲(chǔ)管理中，進(jìn)程或作業(yè)執(zhí)行中產(chǎn)生缺頁中斷，需要從外存中調(diào)入對應(yīng)的程序或數(shù)據(jù)到內(nèi)存當(dāng)中，此時(shí)，如果內(nèi)存已經(jīng)滿了，那么應(yīng)該調(diào)出哪一頁以騰出內(nèi)存空間就需要遵循一定的算法。通常把這類算法稱為頁面置換算法。一個(gè)好的算法，應(yīng)具有較低的頁面更換頻率。理論上講，應(yīng)將那些以后不再被訪問的頁面換出，或把那些在較長時(shí)間內(nèi)不會(huì)再訪問的頁面調(diào)出。,.,101,1.最佳置換算法(Optimalreplacement,OPT),最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面將是以后永不使用的，或許是在最長(未來)時(shí)間內(nèi)不再被訪問的頁面。采用最佳置換算法通?？杀ＷC獲得最低的缺頁率。但由于人們目前還無法預(yù)知，一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁面中，哪一個(gè)頁面是未來最長時(shí)間內(nèi)不再被訪問的，因而該算法是無法實(shí)現(xiàn)的，但可以利用該算法去評價(jià)其它算法。,70120304230321201701,7,70,701,201,203,243,203,201,701,頁面的編號,系統(tǒng)為某進(jìn)程分配的三個(gè)物理塊（頁框）,進(jìn)程運(yùn)行時(shí)先后將7，0，1三個(gè)頁面裝入內(nèi)存，此時(shí)內(nèi)存已滿，若進(jìn)程要訪問新的頁面，則需淘汰三者之一,進(jìn)程訪問頁面2，此時(shí)產(chǎn)生缺頁中斷，將頁面2調(diào)入內(nèi)存，但調(diào)入之前須將內(nèi)存中的某頁換出。,OS根據(jù)最佳置換算法，將頁面7淘汰，因頁面0將在第5次被訪問，頁面1在第14次被訪問，而頁面7要在第18次時(shí)被訪問才需調(diào)入。,進(jìn)程訪問訪問頁面3，引起頁面1被淘汰，因在內(nèi)存中的1，2，0三個(gè)頁面中，頁面1將是以后最晚才被訪問的，要在第14次才被訪問。,采用最佳置換算法，只發(fā)生6次頁面置換,進(jìn)程在運(yùn)行過程中共發(fā)生9次缺頁中斷,缺頁中斷和頁面置換次數(shù)分別是多少？,.,102,2.先進(jìn)先出置換算法(Firstinfirstout,FIFO),FIFO算法是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。該算法實(shí)現(xiàn)簡單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁面按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老的頁面。但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁面經(jīng)常被訪問，比如，含有全局變量、常用函數(shù)、例程等的頁面，F(xiàn)IFO算法并不能保證這些頁面不被淘汰。,70120304230321201701,7,70,701,201,231,430,023,013,702,進(jìn)程運(yùn)行時(shí)已先后將7,0,1三個(gè)頁面裝入內(nèi)存，此時(shí)內(nèi)存已滿。,進(jìn)程訪問頁面2，此時(shí)將產(chǎn)生缺頁中斷，將頁面2調(diào)入內(nèi)存，但調(diào)入之前會(huì)將7,0,1三個(gè)頁面中的一個(gè)進(jìn)行置換。,OS根據(jù)FIFO置換算法，將頁面7淘汰，因7,0,1三個(gè)頁面中，頁面7最先進(jìn)入內(nèi)存，其在內(nèi)存中的駐留時(shí)間最長。,230,420,423,012,712,701,進(jìn)程訪問訪問頁面3，引起頁面0被淘汰，因在內(nèi)存中的2，0，1三個(gè)頁面中，頁面0是最先進(jìn)入內(nèi)存，即在內(nèi)存中駐留時(shí)間最長。,總共發(fā)生15次缺頁中斷，12次頁面置換。,.,103,3.最近最久未使用算法(Leastrecentlyused,LRU),FIFO依據(jù)的條件是頁面進(jìn)入內(nèi)存的時(shí)間。LRU依據(jù)的條件是頁面調(diào)入內(nèi)存后的使用情況。LRU置換算法選擇最近最久未使用的頁面予以淘汰。其作法是賦予每個(gè)頁面一個(gè)訪問字段，用來記錄一個(gè)頁面自上次被訪問以來所經(jīng)歷的時(shí)間t，需淘汰一個(gè)頁面時(shí)，選擇現(xiàn)有頁面中t值最大的，即最近最久未使用的頁面予以淘汰。仍以前面的頁面引用串作例。,70120304230321201701,7,70,701,201,這時(shí)淘汰頁面7，換入頁面2。因頁面7是最先進(jìn)入內(nèi)存且被使用，在這之后至今未使用，是最近最久未使用的頁面,進(jìn)程訪問頁面2，但它不在內(nèi)存，系統(tǒng)需將它調(diào)入。,203,403,402,432,032,132,102,107,進(jìn)程訪問頁面3，但它不在內(nèi)存，系統(tǒng)需將它調(diào)入。,進(jìn)程訪問頁面0，但其不在內(nèi)存。淘汰頁面4，換入頁面0。,這時(shí)頁面1是最近最久未使用的頁面，淘汰頁面1，換入頁面3。,共發(fā)生12次缺頁中斷，9次頁面置換,.,104,4.第二次機(jī)會(huì)置換算法(Secondchance,SC),FIFO算法可能會(huì)把經(jīng)常使用的頁面置換出去，為了避免這一問題，對該算法做一個(gè)簡單的修改：檢查最老頁面的R位。如果R位是0，那么這個(gè)頁面既老又沒有被使用過，可以立刻置換掉；如果是1，就將R位清0，并把該頁面放到鏈表的尾端，修改它的裝入時(shí)間使它就像剛裝入的一樣，然后繼續(xù)搜索。,圖5.17第二次機(jī)會(huì)置換算法,.,105,5.時(shí)鐘頁面置換算法(Clock),把所有的頁面都保存在一個(gè)類似鐘面的環(huán)形鏈表中，用一個(gè)表針指向最老的頁面。當(dāng)發(fā)生缺頁中斷時(shí)，算法首先檢查表針指向的頁面，如果它的R位是0就淘汰該頁面，并把新的頁面插入這個(gè)位置，然后把表針前移一個(gè)位置；如果R位是1就清除R位并把表針前移一個(gè)位置，重復(fù)這個(gè)過程直到找到了一個(gè)R位為0的頁面為止。,.,106,6.最近未使用頁面置換算法(Notrecentlyused,NRU),在大部分具有虛擬內(nèi)存的計(jì)算機(jī)中，系統(tǒng)為每一頁面設(shè)置了兩個(gè)狀態(tài)位。當(dāng)頁面被訪問時(shí)設(shè)置R位；當(dāng)頁面被寫入時(shí)設(shè)置M位?？梢杂肦位和M位來構(gòu)造一個(gè)簡單的頁面置換算法：當(dāng)啟動(dòng)一個(gè)進(jìn)程時(shí)，它的所有頁面的兩個(gè)位都由操作系統(tǒng)設(shè)置成0，R位被定期地清零，以區(qū)別最近沒有被訪問的頁面和被訪問的頁面。,.,107,6.最近未使用頁面置換算法(Notrecentlyused,NRU),當(dāng)發(fā)生缺頁中斷時(shí)，操作系統(tǒng)檢查所有的頁面并根據(jù)它們當(dāng)前的R位和M位的值，把它們分為4類：第0類：RM=00，沒有被訪問，沒有被修改。第1類：RM=01，沒有被訪問，已被修改。第2類：RM=10，已被訪問，沒有被修改。第3類：RM=11，已被訪問，已被修改。NRU算法隨機(jī)地從類編號最小的非空類中挑選一個(gè)頁面淘汰之。這個(gè)算法隱含的意思是，在最近一個(gè)時(shí)鐘周期淘汰一個(gè)沒有被訪問的已修改頁面要比淘汰一個(gè)被頻繁使用的“干凈”頁面好。NRU主要優(yōu)點(diǎn)是易于理解和能夠有效地被實(shí)現(xiàn)，雖然它的性能不是最好的，但是已經(jīng)夠用了。,.,108,5.7.4請求分頁系統(tǒng)性能分析,1.缺頁率對訪問時(shí)間的影響假設(shè)使用了“快表”以提高訪問內(nèi)存的速度，則CPU訪問內(nèi)存所花費(fèi)的時(shí)間由以下3個(gè)部分組成：(1)頁面在“快表”時(shí)的存取時(shí)間，只需1個(gè)讀寫周期時(shí)間；(2)頁面不在“快表”而在頁表時(shí)的存取時(shí)間，需要2個(gè)讀寫周期時(shí)間；(3)頁面既不在“快表”也不在頁表時(shí)，發(fā)生缺頁中斷處理的時(shí)間。缺頁中斷處理的時(shí)間又有3個(gè)部分組成：(1)缺頁中斷服務(wù)時(shí)間；(2)頁面?zhèn)魉蜁r(shí)間，包括：尋道時(shí)間、旋轉(zhuǎn)時(shí)間和數(shù)據(jù)傳送時(shí)間。(3)進(jìn)程重新執(zhí)行時(shí)間。,.,109,2.抖動(dòng)現(xiàn)象置換算法的好壞將直接影響系統(tǒng)的性能，不適當(dāng)?shù)乃惴赡軐?dǎo)致進(jìn)程發(fā)生“抖動(dòng)”(Thrash-ing)。即剛被換出的頁很快又被訪問，需重新調(diào)入。為此，又需再選一頁調(diào)出；而此剛被換出的頁，很快又被訪問，因而又需將它調(diào)入。如此頻繁地更換頁面，以至一個(gè)進(jìn)程在運(yùn)行中，將把大部分時(shí)間花在完成頁面置換的工作上，我們稱該進(jìn)程發(fā)生了“抖動(dòng)”。抖動(dòng)現(xiàn)象分為局部抖動(dòng)和全局抖動(dòng)兩種類型。,5.7.4請求分頁系統(tǒng)性能分析,.,110,2.抖動(dòng)現(xiàn)象抖動(dòng)現(xiàn)象如下兩種類型：1)局部抖動(dòng)：進(jìn)程采用局部置換策略，產(chǎn)生缺頁時(shí)，只能置換自身擁有的某個(gè)頁面，而不能置換其它進(jìn)程的頁面2)全局抖動(dòng)：由進(jìn)程之間的相互作用引起的，若進(jìn)程采用的是全局置換策略，當(dāng)一個(gè)進(jìn)程發(fā)生缺頁中斷時(shí)，需要從其它進(jìn)程那里獲取物理塊，從而導(dǎo)致這些進(jìn)程在運(yùn)行中需要物理塊，產(chǎn)生了缺頁中斷時(shí)，又需要從其它進(jìn)程那里獲取物理塊。,5.7.4請求分頁系統(tǒng)性能分析,.,111,3.頁面大小的選擇頁面大小的選擇涉及到內(nèi)部碎片、頁表大小、頁面失效率的高低等諸多問題頁面越小，內(nèi)部碎片就越少，內(nèi)存利用率就越高，但同時(shí)就會(huì)產(chǎn)生較大的頁表，占用較大的內(nèi)存空間；頁面過大，會(huì)導(dǎo)致頁面在內(nèi)外存之間傳輸時(shí)間的增加，從而降低了系統(tǒng)的有效訪問時(shí)間；頁面較小，內(nèi)存中包含的頁面數(shù)就較多，相應(yīng)的，缺頁率就會(huì)較低，但隨著頁面的增大，缺頁率也會(huì)隨之升高，當(dāng)頁面大小超過進(jìn)程的大小時(shí)，缺頁率又開始下降。選擇最優(yōu)的頁面大小需要在這幾個(gè)互相矛盾的因