計(jì)算機(jī)操作系統(tǒng)第5章PPT課件_第1頁
計(jì)算機(jī)操作系統(tǒng)第5章PPT課件_第2頁
計(jì)算機(jī)操作系統(tǒng)第5章PPT課件_第3頁
計(jì)算機(jī)操作系統(tǒng)第5章PPT課件_第4頁
計(jì)算機(jī)操作系統(tǒng)第5章PPT課件_第5頁
已閱讀5頁,還剩117頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

.,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)槊看畏峙浜笏懈钕碌氖S嗖糠?,總是最小的,在存?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)不再被訪問的頁面。采用最佳置換算法通??杀WC獲得最低的缺頁率。但由于人們目前還無法預(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è)互相矛盾的因

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論