湘潭大學(xué)操作系統(tǒng)第5章課件ppt

1、1計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)第第5章章 內(nèi)存管理內(nèi)存管理2目目 錄錄l5.1 概述概述l5.2 地址重定位地址重定位l5.3 分區(qū)存儲(chǔ)管理分區(qū)存儲(chǔ)管理l5.4 頁(yè)式存儲(chǔ)管理頁(yè)式存儲(chǔ)管理 l5.5 段式與段頁(yè)式存儲(chǔ)管理段式與段頁(yè)式存儲(chǔ)管理l5.6 內(nèi)存擴(kuò)充技術(shù)內(nèi)存擴(kuò)充技術(shù) l5.7 虛擬存儲(chǔ)管理虛擬存儲(chǔ)管理3學(xué)習(xí)目標(biāo)l了解存儲(chǔ)管理的目的與功能，熟悉各種存儲(chǔ)器管理的方式及其實(shí)現(xiàn)方法。l了解重定位、虛擬存儲(chǔ)器的概念以及其技術(shù)。l掌握分區(qū)、頁(yè)式、段式與段頁(yè)式存儲(chǔ)管理的實(shí)現(xiàn)原理和實(shí)現(xiàn)方法。 l掌握虛擬存儲(chǔ)器中的頁(yè)面置換算法及請(qǐng)求分頁(yè)系統(tǒng)性能分析。45.1.1 存儲(chǔ)層次結(jié)構(gòu)l第一層次是高速、昂貴而容量很

2、小的高速緩沖存高速緩沖存儲(chǔ)器（儲(chǔ)器（Cache）和寄存器）和寄存器；l第二層次是速度快、價(jià)格高而數(shù)據(jù)易丟失的內(nèi)存內(nèi)存和磁盤緩存和磁盤緩存；l第三層次是速度較低、價(jià)格低廉、容量極大而存儲(chǔ)內(nèi)容不易丟失的外存和可移動(dòng)磁盤介質(zhì)外存和可移動(dòng)磁盤介質(zhì)，如硬盤、光盤、U盤等。5圖 5.1 存儲(chǔ)層次結(jié)構(gòu)5.1.1 存儲(chǔ)層次結(jié)構(gòu)65.1.1 存儲(chǔ)層次結(jié)構(gòu)1內(nèi)存內(nèi)存 主存儲(chǔ)器簡(jiǎn)稱內(nèi)存或主存內(nèi)存或主存，是計(jì)算機(jī)系統(tǒng)中的主要部件，用于保存進(jìn)程運(yùn)行時(shí)的程序和數(shù)據(jù)，也稱可執(zhí)行存儲(chǔ)器。2寄存器寄存器 寄存器具有與處理機(jī)相同的速度，故對(duì)寄存器的訪問(wèn)寄存器的訪問(wèn)速度最快速度最快，完全能與CPU協(xié)調(diào)工作，但價(jià)格卻十分昂貴，因此容

3、量不可能做得很大。 75.1.1 存儲(chǔ)層次結(jié)構(gòu)3高速緩沖存儲(chǔ)器高速緩沖存儲(chǔ)器高速緩存是現(xiàn)代計(jì)算機(jī)結(jié)構(gòu)中的一個(gè)重要部件，它是介于寄存器和存儲(chǔ)器之間的存儲(chǔ)器介于寄存器和存儲(chǔ)器之間的存儲(chǔ)器，主要用于備份主存中較常用的數(shù)據(jù)，以備份主存中較常用的數(shù)據(jù)，以減少處理機(jī)對(duì)主減少處理機(jī)對(duì)主存儲(chǔ)器的訪問(wèn)次數(shù)存儲(chǔ)器的訪問(wèn)次數(shù)，這樣可大幅度地提高程序執(zhí)，這樣可大幅度地提高程序執(zhí)行速度行速度。高速緩存容量遠(yuǎn)大于寄存器，而比內(nèi)存約小兩到三個(gè)數(shù)量級(jí)左右，從幾十KB到幾MB，訪問(wèn)速度快于主存儲(chǔ)器。 85.1.1 存儲(chǔ)層次結(jié)構(gòu)4磁盤緩存磁盤緩存由于目前磁盤的I/O速度遠(yuǎn)低于對(duì)主存的訪問(wèn)速度，為了緩和兩者之間在速度上的不匹配，而

4、設(shè)置了磁盤緩存，磁盤緩存，主要用于暫時(shí)存放頻繁使用的一部分磁盤數(shù)據(jù)和信息主要用于暫時(shí)存放頻繁使用的一部分磁盤數(shù)據(jù)和信息，以以減少訪問(wèn)磁盤的次數(shù)減少訪問(wèn)磁盤的次數(shù)。但磁盤緩存與高速緩存不同，它本身并不是一種實(shí)際存在的存儲(chǔ)器，而是利用主存中的部分存儲(chǔ)空間暫時(shí)存放從磁盤中讀出(或?qū)懭?的信息。主存也可以看作是輔存的高速緩存，因?yàn)?，輔存中的數(shù)據(jù)必須復(fù)制到主存方能使用，反之，數(shù)據(jù)也必須先存在主存中，才能輸出到輔存。95.1.2 存儲(chǔ)管理目的和任務(wù) l操作系統(tǒng)的存儲(chǔ)管理機(jī)構(gòu)必須盡可能方便用戶和提高內(nèi)存的使用效率，使內(nèi)存在成本、速度和規(guī)模之間獲得較好的權(quán)衡1內(nèi)存分配內(nèi)存分配 2地址映射地址映射 3內(nèi)存共享與

5、保護(hù)內(nèi)存共享與保護(hù) 4內(nèi)存擴(kuò)充內(nèi)存擴(kuò)充 105.1.2 存儲(chǔ)管理目的和任務(wù) 1內(nèi)存分配內(nèi)存分配 l各個(gè)作業(yè)裝入內(nèi)存時(shí)，必須按照規(guī)定的方式向操作系統(tǒng)提出申請(qǐng)，由存儲(chǔ)管理進(jìn)行統(tǒng)一分配。l存儲(chǔ)管理設(shè)置一張表格記錄存儲(chǔ)空間的分配情況，根據(jù)申請(qǐng)的要求按一定的策略分析存儲(chǔ)空間的使用情況，找出足夠的空閑區(qū)域進(jìn)行分配。l當(dāng)內(nèi)存中某個(gè)作業(yè)撤離或主動(dòng)歸還內(nèi)存資源時(shí)，存儲(chǔ)管理要收回它所占用的全部或部分存儲(chǔ)空間，使它們成為空閑區(qū)域，同時(shí)還要修改表格的相關(guān)項(xiàng)。l收回存儲(chǔ)區(qū)域的工作也稱釋放存儲(chǔ)空間。115.1.2 存儲(chǔ)管理目的和任務(wù) 2地址映射地址映射 l內(nèi)存中往往同時(shí)存放多個(gè)作業(yè)程序，而這些程序在內(nèi)存中的位置是不能預(yù)先

6、知道的，所以用戶在編寫程序時(shí)不能使用絕對(duì)地址。l計(jì)算機(jī)的指令中地址部分所指示的地址通常是邏輯地址，用戶按邏輯地址編寫程序。當(dāng)要把程序裝入運(yùn)行時(shí)，操作系統(tǒng)要為其分配一個(gè)合適的內(nèi)存空間，必須把邏輯地址轉(zhuǎn)換成物理地址才能得到信息的真實(shí)存放處。把邏輯地址轉(zhuǎn)換成物理地址的工作稱為地址轉(zhuǎn)換地址轉(zhuǎn)換。125.1.2 存儲(chǔ)管理目的和任務(wù) 3內(nèi)存共享與保護(hù)內(nèi)存共享與保護(hù)l所謂內(nèi)存空間共享，一方面是指采用多道程序設(shè)計(jì)技術(shù)使若干個(gè)程序同時(shí)進(jìn)入內(nèi)存，各自占用一定數(shù)量的存儲(chǔ)空間，即共享內(nèi)存資源，共同使用一個(gè)內(nèi)存共享內(nèi)存資源，共同使用一個(gè)內(nèi)存；l另一方面是指若干個(gè)作業(yè)有共同的程序段或數(shù)據(jù)段時(shí)，可將這些共同的程序段或數(shù)據(jù)段

7、存放在某個(gè)存儲(chǔ)區(qū)域內(nèi)，各作業(yè)執(zhí)行時(shí)都可訪問(wèn)它們，即共享內(nèi)存的某些區(qū)域共享內(nèi)存的某些區(qū)域。l內(nèi)存共享使得內(nèi)存中不僅有系統(tǒng)程序，而且還有若干道用戶程序。為了避免內(nèi)存中的多道程序相互干擾，必須對(duì)內(nèi)存中的程序和數(shù)據(jù)進(jìn)行保護(hù)程序和數(shù)據(jù)進(jìn)行保護(hù)。135.1.2 存儲(chǔ)管理目的和任務(wù) 3內(nèi)存共享與保護(hù)內(nèi)存共享與保護(hù)l最基本的保護(hù)措施是規(guī)定各道程序只能訪問(wèn)屬于自己的那些存儲(chǔ)區(qū)域內(nèi)的信息，對(duì)公共區(qū)域的訪問(wèn)可以加以限制，一般地說(shuō)，一個(gè)程序執(zhí)行時(shí)可能有以下三種情況：對(duì)屬于自己的內(nèi)存區(qū)域內(nèi)的數(shù)據(jù)既可讀又可寫；對(duì)公共區(qū)域中允許共享的信息或可使用的別的用戶的信息可讀而不可寫；對(duì)未獲得授權(quán)的信息，既不可讀又不可寫。145.1

8、.2 存儲(chǔ)管理目的和任務(wù) 4內(nèi)存擴(kuò)充內(nèi)存擴(kuò)充 l為方便用戶編寫程序，使用戶編寫程序時(shí)不受內(nèi)存實(shí)際容量的限制，可以采用一定的技術(shù)擴(kuò)充內(nèi)存容量，得到比實(shí)際容量更大的內(nèi)存空間。l這里的擴(kuò)充不是對(duì)物理內(nèi)存容量的擴(kuò)充，而是指利用存儲(chǔ)管理技術(shù)為程序的運(yùn)行提供一個(gè)比實(shí)際內(nèi)存更大的邏輯存邏輯存儲(chǔ)空間儲(chǔ)空間，即所謂的虛擬存儲(chǔ)管理技術(shù)虛擬存儲(chǔ)管理技術(shù)。l當(dāng)一個(gè)大型的程序要裝入內(nèi)存時(shí)，可先把其中的一部分裝入內(nèi)存，其余部分存放在磁盤上，如果程序執(zhí)行中需要用到不在內(nèi)存中的信息時(shí)，則由操作系統(tǒng)采用覆蓋技術(shù)將其調(diào)入內(nèi)存。155.2 地址重定位一個(gè)邏輯地址空間的程序裝入到物理地址空間時(shí)，由于兩個(gè)空間不一致，需要進(jìn)行地址變換，

9、稱為地址重定位地址重定位。此時(shí)，相對(duì)地址空間相對(duì)地址空間（也稱為邏輯地址空間邏輯地址空間）通過(guò)地址重定位機(jī)構(gòu)轉(zhuǎn)換到絕對(duì)地址空間（也稱為物理地址空間物理地址空間）。165.2 地址重定位地址空間是邏輯地址的集合，存儲(chǔ)空間是物理地址的集合。名字空間、地址空間和存儲(chǔ)空間的關(guān)系如圖5.2所示圖 5.2 名字空間、地址空間和存儲(chǔ)空間程序的裝入和鏈接程序的裝入和鏈接 用戶程序要在系統(tǒng)中運(yùn)行，必須先將它裝入內(nèi)存，然后再將其轉(zhuǎn)變?yōu)橐粋€(gè)可以執(zhí)行的程序，通常都要經(jīng)過(guò)以下幾個(gè)步驟：(1) 編譯，由編譯程序(Compiler)對(duì)用戶源程序進(jìn)行編譯，形成若干個(gè)目標(biāo)模塊(Object Module)；(2) 鏈接，由鏈接

10、程序(Linker)將編譯后形成的一組目標(biāo)模塊以及它們所需要的庫(kù)函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊(Load Module)；(3) 裝入，由裝入程序(Loader)將裝入模塊裝入內(nèi)存。圖a給出了這樣的三步過(guò)程程序的裝入和鏈接程序的裝入和鏈接圖a對(duì)用戶程序的處理步驟程序的裝入程序的裝入1. 1. 絕對(duì)裝入方式絕對(duì)裝入方式(Absolute Loading Mode)(Absolute Loading Mode)編譯時(shí)，若知道程序?qū)Ⅰv留在內(nèi)存的某位置，則編譯程序?qū)a(chǎn)生絕對(duì)地址的目標(biāo)代碼，絕對(duì)裝入程序按照裝入模塊的地址，將程序和數(shù)據(jù)直接裝入指定內(nèi)存。該地址既可在編譯和匯編時(shí)給出，也可以由程序員

11、直接賦予。程序程序員直接給出絕對(duì)地址，使得程序修改時(shí)很可能要修改所有員直接給出絕對(duì)地址，使得程序修改時(shí)很可能要修改所有地址。因此寧可在程序中采用符號(hào)地址，在編譯時(shí)再去轉(zhuǎn)地址。因此寧可在程序中采用符號(hào)地址，在編譯時(shí)再去轉(zhuǎn)換成絕對(duì)地址換成絕對(duì)地址。單道程序環(huán)境下，可用此種方式。 而在多道程序環(huán)境下，目標(biāo)模塊的起始地址通常從0開始，程序中的其他地址，都相對(duì)于起始地址計(jì)算。這樣的模塊稱為相對(duì)裝入模塊。程序程序JUMP iLOAD jDATAJUMP 400LOAD 1200JUMP 1424LOAD 2224符號(hào)地址絕對(duì)地址相對(duì)地址ij10241424222404001200絕對(duì)和可重定位裝入模塊絕對(duì)

12、和可重定位裝入模塊（a）目標(biāo)模塊（b）絕對(duì)裝入模塊（c）相對(duì)裝入模塊程序的裝入程序的裝入2. 2. 可重定位裝入方式可重定位裝入方式(Relocation Loading Mode)(Relocation Loading Mode) 把在裝入時(shí)對(duì)目標(biāo)程序中的指令和數(shù)據(jù)地址的修改過(guò)程稱為重定位重定位。 對(duì)于相對(duì)裝入模塊，應(yīng)采用可重定位裝入方式來(lái)把裝入模塊裝入內(nèi)存。 裝入相對(duì)裝入模塊時(shí)，裝入程序要將模塊的起始地址與裝入程序要將模塊的起始地址與內(nèi)存某位置的地址相加，才能將模塊定位到正確的物理地址內(nèi)存某位置的地址相加，才能將模塊定位到正確的物理地址，同樣，模塊中的指令地址和數(shù)據(jù)地址都要相應(yīng)修改。 因地

13、址變換只是在裝入時(shí)一次完成，以后不再改變，故稱為靜態(tài)重定位靜態(tài)重定位。LOAD 1,2500365 01000 2500 5000作業(yè)地址空間LOAD 1,1250036511000 1250015000內(nèi)存空間作業(yè)裝入內(nèi)存時(shí)的情況10000程序的裝入程序的裝入3. 3. 動(dòng)態(tài)運(yùn)行時(shí)的裝入方式動(dòng)態(tài)運(yùn)行時(shí)的裝入方式(Dynamic Run-time Loading)(Dynamic Run-time Loading)多道程序環(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)存后，

14、把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是等到程序真正要執(zhí)行時(shí)才進(jìn)行地址轉(zhuǎn)換等到程序真正要執(zhí)行時(shí)才進(jìn)行地址轉(zhuǎn)換(轉(zhuǎn)換時(shí)機(jī)的把握轉(zhuǎn)換時(shí)機(jī)的把握)。因此，裝入內(nèi)存后的所有地址仍是相對(duì)地址。為使地址轉(zhuǎn)換不影響指令的執(zhí)行速度，這種方式需要一定的特殊硬件的支持。程序的鏈接程序的鏈接 實(shí)現(xiàn)鏈接的方法有三種：靜態(tài)鏈接、裝入時(shí)動(dòng)態(tài)鏈接和運(yùn)行時(shí)動(dòng)態(tài)鏈接。1、靜態(tài)鏈接：模塊模塊A CALL B:RETURN模塊模塊B CALL C:RETURN模塊模塊C RETURN模塊模塊A JSR “L”RETURN模塊模塊B JSR “L+M”

15、RETURN模塊模塊C RETURN0L-10M-10N-10L-1LL+M-1L+ML+M+N-1需要解決的需要解決的兩個(gè)問(wèn)題：兩個(gè)問(wèn)題：1、對(duì)相對(duì)地、對(duì)相對(duì)地址進(jìn)行修改址進(jìn)行修改2、變換外部、變換外部調(diào)用符號(hào)調(diào)用符號(hào)目標(biāo)模塊目標(biāo)模塊裝入模塊裝入模塊圖b 程序鏈接示意圖程序的鏈接程序的鏈接2. 2. 裝入時(shí)動(dòng)態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接(Load-time Dynamic Linking)(Load-time Dynamic Linking)這是指將用戶源程序編譯后所得到的一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接的鏈接方式在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接的鏈接方式。即在裝入一個(gè)目標(biāo)模塊時(shí)，若發(fā)生一

16、個(gè)外部模塊調(diào)用事件，將引起裝入程序去找出相應(yīng)的外部目標(biāo)模塊，并將它裝入內(nèi)存，還要按照?qǐng)Db所示的方式修改目標(biāo)模塊中的相對(duì)地址。裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)：(1) 便于修改和更新。(2) 便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。 程序的裝入程序的裝入3. 3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-time Dynamic Linking)(Run-time Dynamic Linking)這種鏈接方式，可將某些目標(biāo)模塊的鏈接，推遲到可將某些目標(biāo)模塊的鏈接，推遲到執(zhí)行時(shí)才進(jìn)行執(zhí)行時(shí)才進(jìn)行。即在執(zhí)行過(guò)程中，若發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，由OS去找到該模塊，將它裝入內(nèi)存，并把它鏈接到調(diào)用者模塊上。 275.

17、3 分區(qū)存儲(chǔ)管理5.3.1 單一連續(xù)分區(qū)存儲(chǔ)管理單一連續(xù)分區(qū)存儲(chǔ)管理 這是最簡(jiǎn)單的一種存儲(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ù)分配方式。285.3 分區(qū)存儲(chǔ)管理5.3.2 固定分區(qū)管理固定分區(qū)管理l固定分區(qū)式分配是最簡(jiǎn)單的一種可運(yùn)行多道程序的存儲(chǔ)管理方式。這是將內(nèi)存用戶空間劃分為若干個(gè)固定內(nèi)存用戶空間劃分為若干個(gè)固定大小的區(qū)域大小的區(qū)域，在每個(gè)分區(qū)中只裝

18、入一道作業(yè)在每個(gè)分區(qū)中只裝入一道作業(yè)，這樣，把用戶空間劃分為幾個(gè)分區(qū)，便允許有幾道作業(yè)并發(fā)運(yùn)行。l當(dāng)某一分區(qū)空閑時(shí)，便可以從外存的后備作業(yè)隊(duì)列中選擇一個(gè)適當(dāng)大小的作業(yè)裝入該分區(qū)，當(dāng)該作業(yè)結(jié)束時(shí)，又可再?gòu)暮髠渥鳂I(yè)隊(duì)列中找出另一作業(yè)調(diào)入該分區(qū)。295.3 分區(qū)存儲(chǔ)管理5.3.2 固定分區(qū)管理固定分區(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)(是否已分配)，

19、如圖5.5所示。 305.3 分區(qū)存儲(chǔ)管理圖 5.5 固定分區(qū)分配315.3 分區(qū)存儲(chǔ)管理5.3.3 可變分區(qū)管理（動(dòng)態(tài)分區(qū)管理）可變分區(qū)管理（動(dòng)態(tài)分區(qū)管理）l固定分區(qū)分配是最早的多道程序存儲(chǔ)管理方式，由于每個(gè)分區(qū)的大小固定，必然會(huì)造成存儲(chǔ)空間的浪費(fèi)。l可變分區(qū)分配是指在系統(tǒng)運(yùn)行的過(guò)程中根據(jù)作業(yè)對(duì)內(nèi)存的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間的一種分區(qū)方法。l可變分區(qū)分配是在作業(yè)裝入和處理過(guò)程中建立的分區(qū)，并使分區(qū)的大小與作業(yè)的大小相等。l分區(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ū)表空閑

20、分區(qū)表，在系統(tǒng)中設(shè)置一張空閑分區(qū)表，用于記錄每個(gè)空閑分區(qū)的情況。每個(gè)空閑分區(qū)占一個(gè)表目，表目每個(gè)空閑分區(qū)占一個(gè)表目，表目中包括分區(qū)號(hào)、分區(qū)大小和分區(qū)始址等數(shù)據(jù)項(xiàng)中包括分區(qū)號(hào)、分區(qū)大小和分區(qū)始址等數(shù)據(jù)項(xiàng)。 空閑分區(qū)鏈空閑分區(qū)鏈。為了實(shí)現(xiàn)對(duì)空閑分區(qū)的分配和鏈接，在每個(gè)分區(qū)的起始部分設(shè)置一些用于控制分區(qū)分配的信息控制分區(qū)分配的信息，以及用于鏈接各分區(qū)所用的前向指針前向指針，在分區(qū)尾部則設(shè)置一后向指針后向指針。通過(guò)前、后向鏈接指針，可將所有的空閑分區(qū)鏈接成一個(gè)雙向鏈雙向鏈。 5.3.3 可變分區(qū)管理2. 分區(qū)分配操作1) 分配內(nèi)存系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈(表)中找到所需大小的分區(qū)。設(shè)請(qǐng)求的

21、分區(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)單獨(dú)建立一個(gè)新表項(xiàng)，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈中的適當(dāng)位置。365.3.

22、4 分區(qū)分配算法可變分區(qū)分配常采用的幾種分配算法：l1.首次適應(yīng)算法首次適應(yīng)算法l2.最優(yōu)適應(yīng)算法最優(yōu)適應(yīng)算法l3.最差適應(yīng)算法最差適應(yīng)算法l4.循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法l5.快速適應(yīng)算法快速適應(yīng)算法371.首次適應(yīng)算法 該算法要求分區(qū)鏈以地址遞增的次序鏈接。內(nèi)存分配內(nèi)存分配時(shí)，從鏈?zhǔn)组_始順序查找，直至找到一個(gè)能滿足其大小要時(shí)，從鏈?zhǔn)组_始順序查找，直至找到一個(gè)能滿足其大小要求的空閑區(qū)為止求的空閑區(qū)為止。然后，再按照作業(yè)的大小，從該區(qū)中劃出一塊內(nèi)存分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑鏈中。 該算法傾向于優(yōu)先利用內(nèi)存中低址部分的空閑區(qū)，傾向于優(yōu)先利用內(nèi)存中低址部分的空閑區(qū)，高址部分的很少

23、利用，從而保留了高址部分的大空閑區(qū)，高址部分的很少利用，從而保留了高址部分的大空閑區(qū)，為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。但低低址部分留下許多難以利用的很小的空閑區(qū)址部分留下許多難以利用的很小的空閑區(qū) ，每次查找又每次查找又都從低址部分開始，這樣，增加了查找開銷都從低址部分開始，這樣，增加了查找開銷。382.循環(huán)首次適應(yīng)算法 由首次適應(yīng)算法演變而來(lái)，分配內(nèi)存時(shí)，不再每次從不再每次從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直到找到第一個(gè)能滿足要求的空閑分區(qū)分區(qū)開始查找，

24、直到找到第一個(gè)能滿足要求的空閑分區(qū)，從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間。 為實(shí)現(xiàn)該算法，應(yīng)設(shè)置一起始查詢指針，并采用循環(huán)查找方式。該算法能使內(nèi)存中的空閑分區(qū)分布得更均勻，減少查找空閑分區(qū)的開銷，但這會(huì)缺乏大的空閑分區(qū)。393.最佳適應(yīng)算法 “最佳”的含義是指每次為作業(yè)分配內(nèi)存時(shí)，總是把既能滿足要求又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。為加速查詢，該算法要求將所有的空閑區(qū)按其該算法要求將所有的空閑區(qū)按其大小以遞增的順序鏈接成一空閑區(qū)鏈大小以遞增的順序鏈接成一空閑區(qū)鏈。這樣，第一次找到的滿足要求的空閑區(qū)，必然是最優(yōu)的。 孤立地看，這似乎是最佳的，但從宏觀上看卻不一定。因?yàn)槊看畏峙浜笏?/p>

25、割下的剩余部分，總是最小的，在存儲(chǔ)器中會(huì)留下許多難以利用的小空閑區(qū)。404.最差適應(yīng)算法 由于最壞適應(yīng)分配算法選擇空閑分區(qū)的策略正好與最佳適應(yīng)算法相反：它在掃描整個(gè)空閑分區(qū)表或鏈表時(shí)，總總是挑選一個(gè)最大的空閑區(qū)，從中分割一部分存儲(chǔ)空間給作是挑選一個(gè)最大的空閑區(qū)，從中分割一部分存儲(chǔ)空間給作業(yè)使用業(yè)使用，以至于存儲(chǔ)器中缺乏大的空閑分區(qū)，故把它稱為是最壞適應(yīng)算法。 該算法要求將所有空閑分區(qū)，按容量從大到小的順該算法要求將所有空閑分區(qū)，按容量從大到小的順序，形成一空閑分區(qū)鏈，查找時(shí)，只要看第一個(gè)分區(qū)能否序，形成一空閑分區(qū)鏈，查找時(shí)，只要看第一個(gè)分區(qū)能否滿足作業(yè)要求即可。滿足作業(yè)要求即可。l動(dòng)態(tài)分區(qū)示例

26、：請(qǐng)使用下動(dòng)態(tài)分區(qū)示例：請(qǐng)使用下面的算法再分配一個(gè)面的算法再分配一個(gè)16M的內(nèi)存空間？的內(nèi)存空間？1.首次適應(yīng)（First fit）2.循環(huán)首次適應(yīng)（Next fit）3.最佳適應(yīng)（Best fit）4.最差適應(yīng)（Worst fit）最佳適應(yīng)最佳適應(yīng)首次適應(yīng)首次適應(yīng)循環(huán)首次適應(yīng)循環(huán)首次適應(yīng)最差適應(yīng)最差適應(yīng)435.快速適應(yīng)算法（基于索引） 該算法又稱為分類搜索法，是將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，對(duì)于每一類具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表，這樣，系統(tǒng)中存在多個(gè)空閑分區(qū)鏈表，同時(shí)在內(nèi)存中設(shè)立一張管理索引表，該表的每一個(gè)表項(xiàng)對(duì)應(yīng)了一種空閑分區(qū)類型，并記錄了該類型空閑分區(qū)鏈表的表

27、頭指針。 該算法在搜索空閑分區(qū)時(shí)分二步：第一步是根據(jù)進(jìn)程長(zhǎng)度從索引表中找到能容納它的最小空閑區(qū)鏈表；第二步是從鏈表中取下第一塊進(jìn)行分配。445.快速適應(yīng)算法 優(yōu)點(diǎn)優(yōu)點(diǎn)：查找效率高。另外在進(jìn)行空閑分區(qū)分配時(shí)，不會(huì)對(duì)任何分區(qū)產(chǎn)生分割，能保留大的空閑分區(qū)，同時(shí)也不會(huì)產(chǎn)生內(nèi)存碎片。 缺點(diǎn)缺點(diǎn)：在分區(qū)歸還時(shí)算法比較復(fù)雜，系統(tǒng)開銷較大。該算法在分配空閑分區(qū)時(shí)是以進(jìn)程為單位，一個(gè)分區(qū)只屬于一個(gè)進(jìn)程，因此在為進(jìn)程所分配的一個(gè)分區(qū)中，或多或少地存在一定的浪費(fèi)?？臻e分區(qū)劃分越細(xì)，浪費(fèi)越嚴(yán)重，整體上會(huì)造成可觀的存儲(chǔ)空間浪費(fèi)，這是典型的以空間換時(shí)間的作法。哈希算法哈希算法 哈希算法是利用哈?？焖俨檎业膬?yōu)點(diǎn)，以及空閑分

28、區(qū)在可利用空閑分區(qū)表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)造一張以空閑分區(qū)大小為關(guān)建立哈希函數(shù)，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表鍵字的哈希表，該表的每一個(gè)表項(xiàng)記錄了一個(gè)對(duì)應(yīng)的空閑分區(qū)鏈表表頭指針。 進(jìn)行空閑分區(qū)分配時(shí)，根據(jù)所需空閑分區(qū)大小，通過(guò)哈希函數(shù)計(jì)算，即得到在哈希表中的位置，從中得到相應(yīng)的空閑分區(qū)鏈表，實(shí)現(xiàn)最佳分配策略。4546伙伴系統(tǒng) 該算法規(guī)定，無(wú)論已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪(k為整數(shù)，lkm)，其中2l表示分配的最小塊的尺寸，2m表示分配的最大的塊的尺寸。通常， 2m是可供分配的整個(gè)內(nèi)存的大小。 （1）開始時(shí)，可用于分配的整個(gè)空間被看成是一個(gè)大小為2m的塊； （2）如

29、果請(qǐng)求的大小s滿足2m-1 s = 2m ，則分配整個(gè)空間；否則，該塊被分成兩個(gè)大小相等的伙伴，均為2m-1 ，如果有2m-2 s 2100段號(hào)S段長(zhǎng)基址1K6K6004K5008K2009200段號(hào)0321+82928K82928692邏輯地址物理地址主存位移量段表寄存器越界795.5.1 段式存儲(chǔ)管理 2.分頁(yè)和分段的主要區(qū)別分頁(yè)和分段的主要區(qū)別 分頁(yè)和分段系統(tǒng)有許多相似之處，但在概念上二者完全不同： (1) 頁(yè)是信息的物理單位，僅僅是出于系統(tǒng)管理的需要；段是信息的邏輯單位，其目的是滿足用戶的需要。(2) 頁(yè)的大小固定且由系統(tǒng)確定，一個(gè)系統(tǒng)只能有一種大小的頁(yè)面；段的長(zhǎng)度不固定，決定于用戶所

30、編寫的程序； (3) 分頁(yè)的作業(yè)地址空間是一維的；分段的作業(yè)地址空間是二維的。 (4) 通常分段的段內(nèi)空間會(huì)比分頁(yè)的頁(yè)面空間大，因此段表會(huì)比頁(yè)表短。805.5.2 段頁(yè)式存儲(chǔ)管理1) 基本原理 段頁(yè)式系統(tǒng)的基本原理是分段和分頁(yè)原理的結(jié)合，即即先將用戶程序分成若干個(gè)段，再把每個(gè)段分成若干個(gè)頁(yè)，先將用戶程序分成若干個(gè)段，再把每個(gè)段分成若干個(gè)頁(yè)，并為每一個(gè)段賦予一個(gè)段名并為每一個(gè)段賦予一個(gè)段名。在段頁(yè)式系統(tǒng)中，其地址結(jié)地址結(jié)構(gòu)由段號(hào)構(gòu)由段號(hào)、段內(nèi)頁(yè)號(hào)段內(nèi)頁(yè)號(hào)及頁(yè)內(nèi)地址頁(yè)內(nèi)地址三部分所組成，如下圖所示。 為實(shí)現(xiàn)從邏輯地址到物理地址的變換，系統(tǒng)需同時(shí)配置段表和頁(yè)表，段表的內(nèi)容是頁(yè)表始址和頁(yè)表長(zhǎng)度，這與分

31、段式系統(tǒng)不同。段號(hào)（S） 段內(nèi)頁(yè)號(hào)（P） 頁(yè)內(nèi)地址（W）圖 5.14 利用段表和頁(yè)表實(shí)現(xiàn)地址映射5.5.2 段頁(yè)式存儲(chǔ)管理825.5.2 段頁(yè)式存儲(chǔ)管理2) 地址變換過(guò)程 在段頁(yè)式系統(tǒng)中，為了便于實(shí)現(xiàn)地址變換，需要配置一個(gè)段表寄存器，其中存放段表始址和段表長(zhǎng)度。進(jìn)行地址變換時(shí)按如下步驟進(jìn)行：(1) 通過(guò)段表寄存器將段號(hào)與段表長(zhǎng)度進(jìn)行比較將段號(hào)與段表長(zhǎng)度進(jìn)行比較，如果未越界則查找段表在內(nèi)存中的位置，否則越界中斷；(2) 訪問(wèn)段表訪問(wèn)段表，將頁(yè)表長(zhǎng)度與頁(yè)號(hào)進(jìn)行比較，如果未越界則根據(jù)段號(hào)查找頁(yè)表所在的位置；(3) 訪問(wèn)頁(yè)表訪問(wèn)頁(yè)表，根據(jù)頁(yè)號(hào)查找該頁(yè)所在的物理塊號(hào)；(4) 將物理塊號(hào)和地址結(jié)構(gòu)中的頁(yè)內(nèi)

32、地址相加，形成內(nèi)存單形成內(nèi)存單元的物理地址元的物理地址。圖 5.15 段頁(yè)式地址變換過(guò)程5.5.2 段頁(yè)式存儲(chǔ)管理845.6 內(nèi)存擴(kuò)充技術(shù) 前面所介紹的各種存儲(chǔ)管理方式都有一個(gè)共同的特點(diǎn)，那就是都要求將一個(gè)作業(yè)的全部裝入內(nèi)存后方能運(yùn)行，于是，出現(xiàn)了這樣兩種情況：一是有的作業(yè)很大，其所要求的內(nèi)存空間超過(guò)了內(nèi)存空間的總?cè)萘浚鳂I(yè)不能裝入內(nèi)存，導(dǎo)致其無(wú)法運(yùn)行；二是有大量的作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將少數(shù)作業(yè)裝入內(nèi)存運(yùn)行，其它大量作業(yè)留在外存等待。 出現(xiàn)這兩種情況的原因，都是由于內(nèi)存容量不夠大。 一個(gè)明顯的解決辦法就是增加物理內(nèi)存增加物理內(nèi)存；另一種方法就是從邏輯上來(lái)擴(kuò)充

33、內(nèi)存容量邏輯上來(lái)擴(kuò)充內(nèi)存容量。855.6.1 覆蓋技術(shù) 覆蓋技術(shù)覆蓋技術(shù)是指一個(gè)程序的若干程序段或幾個(gè)程序的某些部分共享某一個(gè)存儲(chǔ)空間。覆蓋技術(shù)的實(shí)現(xiàn)是把程序劃分為若干個(gè)功能上相對(duì)獨(dú)立的程序段，按照其自身的邏輯結(jié)構(gòu)使那些不會(huì)同時(shí)執(zhí)行的程序段共享同一塊內(nèi)存區(qū)域。未執(zhí)行的程序段先保存在未執(zhí)行的程序段先保存在磁盤上，當(dāng)有關(guān)程序段的前一部分執(zhí)行結(jié)束后，再磁盤上，當(dāng)有關(guān)程序段的前一部分執(zhí)行結(jié)束后，再把后續(xù)程序段調(diào)入內(nèi)存，覆蓋前面的程序段把后續(xù)程序段調(diào)入內(nèi)存，覆蓋前面的程序段。865.6.1 覆蓋技術(shù) 覆蓋技術(shù)是早期采用的簡(jiǎn)單的擴(kuò)充內(nèi)存技術(shù)，對(duì)用戶不透明，它要求用戶清楚地了解程序的結(jié)構(gòu)，并指定各程序段調(diào)入

34、內(nèi)存的先后次序，以及內(nèi)存中可以覆蓋掉的程序段的位置等，增加了用戶的負(fù)擔(dān)。而且程序段的最大長(zhǎng)度仍受內(nèi)存容量的限制。覆蓋技術(shù)可以由編譯程序提供支持，此時(shí)被覆蓋的塊是由程序員或編譯程序預(yù)先確定的。875.6.2 交換技術(shù)交換的引入交換的引入 一方面一方面，在內(nèi)存中的某些進(jìn)程由于某事件尚未發(fā)生而被阻塞運(yùn)行，但它卻占用了大量的內(nèi)存空間，甚至有時(shí)可能出現(xiàn)在內(nèi)存中所有進(jìn)程都被阻塞，而無(wú)可運(yùn)行之進(jìn)程，迫使CPU停止下來(lái)等待的情況；另一方面另一方面，卻又有著許多作業(yè)，因內(nèi)存空間不足，一直駐留在外存上，而不能進(jìn)入內(nèi)存運(yùn)行。 所謂交換交換(對(duì)換對(duì)換)，是指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程，或暫時(shí)不用的程序和數(shù)據(jù)，換出到外

35、存上，以騰出足夠的內(nèi)存空間，把已具備運(yùn)行條件的進(jìn)程，或進(jìn)程所需的程序和數(shù)據(jù)，換入內(nèi)存。885.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í)需要考慮如下問(wèn)題：換出進(jìn)程的選擇交換時(shí)機(jī)的確定交換空間的分配換入進(jìn)程換回內(nèi)存時(shí)位置的確定895.7 虛擬存儲(chǔ)管理5.7.1 基本原理1. 常規(guī)存儲(chǔ)器管理方式的特征常規(guī)存儲(chǔ)器管理方式的特征 (1) 一次性。作業(yè)在運(yùn)行前需要一次性的將其全部裝入內(nèi)存。但許多作業(yè)在

36、每次運(yùn)行時(shí)，并非其全部程序和數(shù)據(jù)都使用到了，如果一次性的將其全部裝入，實(shí)際上也是對(duì)內(nèi)存空間的一種浪費(fèi)。 (2) 駐留性。作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至作業(yè)運(yùn)行結(jié)束。盡管運(yùn)行中的進(jìn)程會(huì)因各種事件而長(zhǎng)期等待，或有些模塊在運(yùn)行過(guò)一次以后就不再需要了，但它們?nèi)詫⒗^續(xù)占用寶貴的內(nèi)存資源。905.7.1 基本原理2. 局部性原理局部性原理 程序運(yùn)行時(shí)存在的局部性現(xiàn)象，很早就已被人發(fā)現(xiàn)，但直到1968年，P.Denning才真正指出：程序在執(zhí)行時(shí)將呈程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律，即在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅局現(xiàn)出局部性規(guī)律，即在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分，相應(yīng)地，它所訪問(wèn)的存

37、儲(chǔ)空間也局限于某限于某個(gè)部分，相應(yīng)地，它所訪問(wèn)的存儲(chǔ)空間也局限于某個(gè)區(qū)域個(gè)區(qū)域。 局限性又表現(xiàn)在下述兩個(gè)方面：(1) 時(shí)間局限性。程序中的某條指令被執(zhí)行，不久后會(huì)再次執(zhí)行；某個(gè)數(shù)據(jù)被訪問(wèn)，不久后將再次被訪問(wèn)。產(chǎn)生時(shí)間局限性的典型原因是在程序中存在著大量的循環(huán)循環(huán)操作。(2) 空間局限性。 程序訪問(wèn)了某個(gè)存儲(chǔ)單元，不久后，其附近的存儲(chǔ)單元也將被訪問(wèn)。915.7.1 基本原理3. 虛擬存儲(chǔ)虛擬存儲(chǔ) 基于局部性原理可知，應(yīng)用程序在運(yùn)行之前沒(méi)有必要將應(yīng)用程序在運(yùn)行之前沒(méi)有必要將之全部裝入內(nèi)存之全部裝入內(nèi)存，而僅須將那些當(dāng)前要運(yùn)行的少數(shù)頁(yè)面或段當(dāng)前要運(yùn)行的少數(shù)頁(yè)面或段先裝入內(nèi)存便可運(yùn)行先裝入內(nèi)存便可運(yùn)行

38、，其余部分暫留在盤上。 局部性原理是實(shí)現(xiàn)虛擬存儲(chǔ)管理的理論基礎(chǔ)。 所謂虛擬存儲(chǔ)器虛擬存儲(chǔ)器是指僅把作業(yè)的一部分裝入內(nèi)存便可運(yùn)行的存儲(chǔ)器系統(tǒng)，是具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。虛擬存儲(chǔ)器的邏輯容量由系統(tǒng)的尋址能力和外存容量之和所決定，與實(shí)際的內(nèi)存容量無(wú)關(guān)。925.7.1 基本原理虛擬存儲(chǔ)虛擬存儲(chǔ)特征特征(1) 多次性多次性：是指一個(gè)作業(yè)被分成多次來(lái)調(diào)入內(nèi)存，即作業(yè)運(yùn)行時(shí)不需將其全部裝入內(nèi)存，只需將當(dāng)前要運(yùn)行的那部分程序和數(shù)據(jù)裝入，以后運(yùn)行到某些部分時(shí)再將其調(diào)入。 (2) 對(duì)換性對(duì)換性：是指允許作業(yè)中的程序和數(shù)據(jù)，在作業(yè)運(yùn)行過(guò)程中換進(jìn)、換出。 (3) 虛擬

39、性虛擬性：是指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。 虛擬性以多次性和對(duì)換性為基礎(chǔ)，多次性和對(duì)換性以離散分虛擬性以多次性和對(duì)換性為基礎(chǔ)，多次性和對(duì)換性以離散分配為基礎(chǔ)配為基礎(chǔ)。935.7.2 請(qǐng)求分頁(yè)存儲(chǔ)管理 請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)是在分頁(yè)存儲(chǔ)管理系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能后形成的頁(yè)式虛擬存儲(chǔ)頁(yè)式虛擬存儲(chǔ)管理系統(tǒng)管理系統(tǒng)。1. 請(qǐng)求分頁(yè)原理請(qǐng)求分頁(yè)原理 請(qǐng)求分頁(yè)存儲(chǔ)是建立在分頁(yè)存儲(chǔ)管理基礎(chǔ)之上，從靜態(tài)分頁(yè)存儲(chǔ)管理發(fā)展而來(lái)的。在作業(yè)或進(jìn)程開始執(zhí)行前，不把作業(yè)或進(jìn)程的程序段和數(shù)據(jù)段一次性的全部裝入內(nèi)存，而只是裝入被認(rèn)為是經(jīng)常使用的那一部分。其他部分則

40、在程序執(zhí)行過(guò)程中動(dòng)態(tài)的裝入。 請(qǐng)求分頁(yè)的地址變換過(guò)程與靜態(tài)分頁(yè)管理方式相同，都是通過(guò)頁(yè)表查詢出相應(yīng)的塊號(hào)之后，再由塊號(hào)與頁(yè)內(nèi)地址相加得到實(shí)際的物理地址。945.7.2 請(qǐng)求分頁(yè)存儲(chǔ)管理請(qǐng)求頁(yè)表機(jī)制請(qǐng)求頁(yè)表機(jī)制 在請(qǐng)求分頁(yè)系統(tǒng)中需要的主要數(shù)據(jù)結(jié)構(gòu)是請(qǐng)求頁(yè)表，其基本作用仍然是將用戶地址空間中的邏輯地址映射為內(nèi)存空將用戶地址空間中的邏輯地址映射為內(nèi)存空間中的物理地址間中的物理地址。為了滿足頁(yè)面換進(jìn)換出的需要，在請(qǐng)求頁(yè)表中又增加了四個(gè)字段。這樣，在請(qǐng)求分頁(yè)系統(tǒng)中的每個(gè)頁(yè)表應(yīng)含以下諸項(xiàng)：頁(yè)號(hào)頁(yè)號(hào) 物理塊號(hào)物理塊號(hào) 狀態(tài)位狀態(tài)位P P 訪問(wèn)字段訪問(wèn)字段A A 修改位修改位M M 外存地址外存地址又稱存在位

41、，用于指示該頁(yè)是否已調(diào)入內(nèi)存，供程序訪問(wèn)時(shí)參考。用于記錄本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù)，或最近已有多長(zhǎng)時(shí)間未被訪問(wèn)，提供給置換算法選擇換出頁(yè)面時(shí)參考。指示該頁(yè)在調(diào)入內(nèi)存后是否被修改過(guò)。若未被修改，在置換該頁(yè)時(shí)就不需將該頁(yè)回寫到外存，否則，就要回寫到外存。用于指出該頁(yè)在外存上的地址，通常是物理塊號(hào)，供調(diào)入該頁(yè)時(shí)使用。955.7.2 請(qǐng)求分頁(yè)存儲(chǔ)管理2. 缺頁(yè)中斷機(jī)構(gòu)缺頁(yè)中斷機(jī)構(gòu) 每當(dāng)所要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，便要產(chǎn)生一次缺頁(yè)中缺頁(yè)中斷斷，請(qǐng)求OS將所缺之頁(yè)調(diào)入內(nèi)存。缺頁(yè)中斷雖要經(jīng)歷與一般中斷相同的幾個(gè)步驟，但它是一種特殊的中斷，與一般中斷的區(qū)別主要是： (1) 在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)在指

42、令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。通常CPU都是在一條指令執(zhí)行完后去檢查是否有中斷請(qǐng)求到達(dá)。有則響應(yīng)，無(wú)則繼續(xù)執(zhí)行下一條指令。而缺頁(yè)中斷是在指令執(zhí)行期間，發(fā)現(xiàn)所要訪問(wèn)的指令和數(shù)據(jù)不在內(nèi)存時(shí)產(chǎn)生和處理的。 (2) 一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷。這時(shí)硬件機(jī)構(gòu)應(yīng)能保存多次中斷時(shí)的狀態(tài)，并保證最后能返回到中斷前產(chǎn)生缺頁(yè)中斷的指令處，繼續(xù)執(zhí)行。96B:A:Copy ATo B例如：執(zhí)行 COPY A TO B指令時(shí)，可能要產(chǎn)生6次缺頁(yè)中斷654321頁(yè)面975.7.2 請(qǐng)求分頁(yè)存儲(chǔ)管理地址變換過(guò)程地址變換過(guò)程請(qǐng)求分頁(yè)系統(tǒng)中的地址變換機(jī)構(gòu)是在分頁(yè)系統(tǒng)地址變換

43、機(jī)構(gòu)的基礎(chǔ)上，為實(shí)現(xiàn)虛擬存儲(chǔ)器，再增加了某些功能所形成的，如產(chǎn)生和處理缺頁(yè)中斷，以及從內(nèi)存中換出一頁(yè)的功能等等。圖5.16示出了請(qǐng)求分頁(yè)系統(tǒng)中的地址變換過(guò)程。98圖 5.16 請(qǐng)求分頁(yè)中的地址變換過(guò)程995.7.3 頁(yè)面置換算法 缺頁(yè)率假設(shè)一個(gè)進(jìn)程的邏輯空間為n頁(yè)，系統(tǒng)為其分配的內(nèi)存物理塊數(shù)為m(mn)。如果在進(jìn)程的運(yùn)行過(guò)程中，訪問(wèn)頁(yè)面成功(即所訪問(wèn)頁(yè)面在內(nèi)存中)的次數(shù)為S，訪問(wèn)頁(yè)面失敗(即所訪問(wèn)頁(yè)面不在內(nèi)存中，需要從外存調(diào)入)的次數(shù)為F，則該進(jìn)程總的頁(yè)面訪問(wèn)次數(shù)為A=S+F，那么該進(jìn)程在其運(yùn)行過(guò)程中的缺頁(yè)率即為 缺頁(yè)率的影響因素: 1) 頁(yè)面大小；2) 進(jìn)程分配物理塊的數(shù)目；3) 頁(yè)面置換算

44、法；4) 程序固有特性。AFf 1005.7.3 頁(yè)面置換算法 在請(qǐng)求分頁(yè)存儲(chǔ)管理中，進(jìn)程或作業(yè)執(zhí)行中產(chǎn)生缺頁(yè)中斷，需要從外存中調(diào)入對(duì)應(yīng)的程序或數(shù)據(jù)到內(nèi)存當(dāng)中，此時(shí)，如果內(nèi)存已經(jīng)滿了，那么應(yīng)該調(diào)出哪一頁(yè)以騰出內(nèi)存空間就需要遵循一定的算法。通常把這類算法稱為頁(yè)面置換算法頁(yè)面置換算法。 一個(gè)好的算法，應(yīng)具有較低的頁(yè)面更換頻率。理論上講，應(yīng)將那些以后不再被訪問(wèn)的頁(yè)面換出，或把那些在較長(zhǎng)時(shí)間內(nèi)不會(huì)再訪問(wèn)的頁(yè)面調(diào)出。1011. 最佳置換算法最佳置換算法(Optimal replacement, OPT)最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁(yè)面將是以后永不使用的

45、，或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。采用最佳置換算法通?？杀ＷC獲得最低的缺頁(yè)率。但由于人們目前還無(wú)法預(yù)知，一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中，哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，因而該算法是無(wú)法實(shí)現(xiàn)的，但可以利用該算法去評(píng)價(jià)其它算法。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1770701201203243203201701頁(yè)面的編號(hào)系統(tǒng)為某進(jìn)程分配的三個(gè)物理塊（頁(yè)框）進(jìn)程運(yùn)行時(shí)先后將7，0，1三個(gè)頁(yè)面裝入內(nèi)存，此時(shí)內(nèi)存已滿，若進(jìn)程要訪問(wèn)新的頁(yè)面，則需淘汰三者之一進(jìn)程訪問(wèn)頁(yè)面2，此時(shí)產(chǎn)生缺頁(yè)中斷，將頁(yè)面2調(diào)入內(nèi)存，但調(diào)入之前須將內(nèi)存中的某頁(yè)換出。OS

46、根據(jù)最佳置換算法，將頁(yè)面7淘汰，因頁(yè)面0將在第5次被訪問(wèn)，頁(yè)面1在第14次被訪問(wèn)，而頁(yè)面7要在第18次時(shí)被訪問(wèn)才需調(diào)入。進(jìn)程訪問(wèn)訪問(wèn)頁(yè)面3，引起頁(yè)面1被淘汰，因在內(nèi)存中的1，2，0三個(gè)頁(yè)面中，頁(yè)面1將是以后最晚才被訪問(wèn)的，要在第14次才被訪問(wèn)。 采用最佳置換算法，只發(fā)生6次頁(yè)面置換進(jìn)程在運(yùn)行過(guò)程中共發(fā)生9次缺頁(yè)中斷缺頁(yè)中斷和頁(yè)面置換次數(shù)分別是多少？編號(hào)頁(yè)面的引用順序（頁(yè)面走向）： 1 2 3 4 5 6 7 8 9 10 11121314 15161718 19201022. 先進(jìn)先出置換算法先進(jìn)先出置換算法(First in first out, FIFO) FIFO算法是最早出現(xiàn)的置換算法

47、。該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老的頁(yè)面。但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁(yè)面經(jīng)常被訪問(wèn)，比如，含有全局變量、常用函數(shù)、例程等的頁(yè)面，F(xiàn)IFO算法并不能保證這些頁(yè)面不被淘汰。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1770701201231430023013702編號(hào)頁(yè)面的引用順序（頁(yè)面走向）： 1 2 3 4 5 6 7 8 9 10 11121314 15161718

48、1920進(jìn)程運(yùn)行時(shí)已先后將7,0,1三個(gè)頁(yè)面裝入內(nèi)存，此時(shí)內(nèi)存已滿。進(jìn)程訪問(wèn)頁(yè)面2，此時(shí)將產(chǎn)生缺頁(yè)中斷，將頁(yè)面2調(diào)入內(nèi)存，但調(diào)入之前會(huì)將7,0,1三個(gè)頁(yè)面中的一個(gè)進(jìn)行置換。OS根據(jù)FIFO置換算法，將頁(yè)面7淘汰，因7,0,1三個(gè)頁(yè)面中，頁(yè)面7最先進(jìn)入內(nèi)存，其在內(nèi)存中的駐留時(shí)間最長(zhǎng)。230420423012712701進(jìn)程訪問(wèn)訪問(wèn)頁(yè)面3，引起頁(yè)面0被淘汰，因在內(nèi)存中的2，0，1三個(gè)頁(yè)面中，頁(yè)面0是最先進(jìn)入內(nèi)存，即在內(nèi)存中駐留時(shí)間最長(zhǎng)?？偣舶l(fā)生15次缺頁(yè)中斷，12次頁(yè)面置換。1033. 最近最久未使用算法最近最久未使用算法(Least recently used, LRU) FIFO依據(jù)的條件是頁(yè)

49、面進(jìn)入內(nèi)存的時(shí)間。LRU依據(jù)的條件是頁(yè)面調(diào)入內(nèi)存后的使用情況。LRU置換算法選擇最近最久未使用的頁(yè)面予以淘汰。 其作法是賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間t，需淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中t值最大的，即最近最久未使用的頁(yè)面予以淘汰。 仍以前面的頁(yè)面引用串作例。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1770701201這時(shí)淘汰頁(yè)面7，換入頁(yè)面2。因頁(yè)面7是最先進(jìn)入內(nèi)存且被使用，在這之后至今未使用，是最近最久未使用的頁(yè)面進(jìn)程訪問(wèn)頁(yè)面2，但它不在內(nèi)存，系統(tǒng)需將它調(diào)入。203403402432032132102107進(jìn)程訪問(wèn)

50、頁(yè)面3，但它不在內(nèi)存，系統(tǒng)需將它調(diào)入。進(jìn)程訪問(wèn)頁(yè)面0，但其不在內(nèi)存。淘汰頁(yè)面4，換入頁(yè)面0。這時(shí)頁(yè)面1是最近最久未使用的頁(yè)面，淘汰頁(yè)面1，換入頁(yè)面3。共發(fā)生12次缺頁(yè)中斷，9次頁(yè)面置換1044. 第二次機(jī)會(huì)置換算法第二次機(jī)會(huì)置換算法(Second chance, SC) FIFO算法可能會(huì)把經(jīng)常使用的頁(yè)面置換出去，為了避免這一問(wèn)題，對(duì)該算法做一個(gè)簡(jiǎn)單的修改：檢查最老頁(yè)面的R位。如果R位是0，那么這個(gè)頁(yè)面既老又沒(méi)有被使用過(guò)，可以立刻置換掉；如果是1，就將R位清0，并把該頁(yè)面放到鏈表的尾端，修改它的裝入時(shí)間使它就像剛裝入的一樣，然后繼續(xù)搜索。圖 5.17第二次機(jī)會(huì)置換算法1055. 時(shí)鐘頁(yè)面置換算

51、法時(shí)鐘頁(yè)面置換算法(Clock) 把所有的頁(yè)面都保存在一個(gè)類似鐘面的環(huán)形鏈表中，用一個(gè)表針指向最老的頁(yè)面。 當(dāng)發(fā)生缺頁(yè)中斷時(shí)，算法首先檢查表針指向的頁(yè)面，如果它的R位是0就淘汰該頁(yè)面，并把新的頁(yè)面插入這個(gè)位置，然后把表針前移一個(gè)位置；如果R位是1就清除R位并把表針前移一個(gè)位置，重復(fù)這個(gè)過(guò)程直到找到了一個(gè)R位為0的頁(yè)面為止。1066. 最近未使用頁(yè)面置換算法最近未使用頁(yè)面置換算法(Not recently used, NRU) 在大部分具有虛擬內(nèi)存的計(jì)算機(jī)中，系統(tǒng)為每一頁(yè)面設(shè)置了兩個(gè)狀態(tài)位。當(dāng)頁(yè)面被訪問(wèn)時(shí)設(shè)置R位；當(dāng)頁(yè)面被寫入時(shí)設(shè)置M位。 可以用R位和M位來(lái)構(gòu)造一個(gè)簡(jiǎn)單的頁(yè)面置換算法：當(dāng)啟動(dòng)一個(gè)

52、進(jìn)程時(shí)，它的所有頁(yè)面的兩個(gè)位都由操作系統(tǒng)設(shè)置成0，R位被定期地清零，以區(qū)別最近沒(méi)有被訪問(wèn)的頁(yè)面和被訪問(wèn)的頁(yè)面。1076. 最近未使用頁(yè)面置換算法最近未使用頁(yè)面置換算法(Not recently used, NRU) 當(dāng)發(fā)生缺頁(yè)中斷時(shí)，操作系統(tǒng)檢查所有的頁(yè)面并根據(jù)它們當(dāng)前的R位和M位的值，把它們分為4類：第0類：RM=00，沒(méi)有被訪問(wèn)，沒(méi)有被修改。第1類：RM=01，沒(méi)有被訪問(wèn)，已被修改。第2類：RM=10，已被訪問(wèn)，沒(méi)有被修改。第3類：RM=11，已被訪問(wèn)，已被修改。 NRU算法隨機(jī)地從類編號(hào)最小的非空類中挑選一個(gè)頁(yè)面淘汰之。這個(gè)算法隱含的意思是，在最近一個(gè)時(shí)鐘周期淘汰一個(gè)沒(méi)有被訪問(wèn)的已修改頁(yè)

53、面要比淘汰一個(gè)被頻繁使用的“干凈”頁(yè)面好。NRU主要優(yōu)點(diǎn)是易于理解和能夠有效地被實(shí)現(xiàn)，雖然它的性能不是最好的，但是已經(jīng)夠用了。1085.7.4 請(qǐng)求分頁(yè)系統(tǒng)性能分析1. 缺頁(yè)率對(duì)訪問(wèn)時(shí)間的影響缺頁(yè)率對(duì)訪問(wèn)時(shí)間的影響 假設(shè)使用了“快表”以提高訪問(wèn)內(nèi)存的速度，則CPU訪問(wèn)內(nèi)存所花費(fèi)的時(shí)間由以下3個(gè)部分組成：(1) 頁(yè)面在“快表”時(shí)的存取時(shí)間，只需1個(gè)讀寫周期時(shí)間；(2) 頁(yè)面不在“快表”而在頁(yè)表時(shí)的存取時(shí)間，需要2個(gè)讀寫周期時(shí)間；(3) 頁(yè)面既不在“快表”也不在頁(yè)表時(shí)，發(fā)生缺頁(yè)中斷處理的時(shí)間。 缺頁(yè)中斷處理的時(shí)間又有3個(gè)部分組成：(1) 缺頁(yè)中斷服務(wù)時(shí)間；(2) 頁(yè)面?zhèn)魉蜁r(shí)間，包括：尋道時(shí)間、旋轉(zhuǎn)

54、時(shí)間和數(shù)據(jù)傳送時(shí)間。(3) 進(jìn)程重新執(zhí)行時(shí)間。1092. 抖動(dòng)現(xiàn)象抖動(dòng)現(xiàn)象 置換算法的好壞將直接影響系統(tǒng)的性能，不適當(dāng)?shù)乃惴赡軐?dǎo)致進(jìn)程發(fā)生“抖動(dòng)” (Thrash-ing)。即剛被換出的頁(yè)很快又被訪問(wèn)，需重新調(diào)入。為此，又需再選一頁(yè)調(diào)出；而此剛被換出的頁(yè)，很快又被訪問(wèn)，因而又需將它調(diào)入。如此頻繁地更換頁(yè)面，以至一個(gè)進(jìn)程在運(yùn)行中，將把大部分時(shí)間花在完成頁(yè)面置換的工作上，我們稱該進(jìn)程發(fā)生了“抖動(dòng)抖動(dòng)”。 抖動(dòng)現(xiàn)象分為局部抖動(dòng)和全局抖動(dòng)兩種類型。5.7.4 請(qǐng)求分頁(yè)系統(tǒng)性能分析1102. 抖動(dòng)現(xiàn)象抖動(dòng)現(xiàn)象 抖動(dòng)現(xiàn)象如下兩種類型： 1) 局部抖動(dòng)：進(jìn)程采用局部置換策略，產(chǎn)生缺頁(yè)時(shí)，只能置換自身?yè)碛械哪硞€(gè)頁(yè)面，而不能置換其它進(jìn)程的頁(yè)面 2) 全局抖動(dòng)：由進(jìn)程之間的相互作用引起的，若進(jìn)程采用的是全局置換策略，當(dāng)一個(gè)進(jìn)程發(fā)生缺頁(yè)中斷時(shí)，需要從其它進(jìn)程那里獲取物理塊，從而導(dǎo)致這些進(jìn)程在運(yùn)行中需要物理塊，產(chǎn)生了缺頁(yè)中斷時(shí)，又需要從其它進(jìn)程那里獲取物理塊。5.7.4 請(qǐng)求分頁(yè)系統(tǒng)性能分析1113. 頁(yè)面大小的選擇頁(yè)面大小的選擇l頁(yè)面大小的選擇涉及到內(nèi)部碎片、頁(yè)表大小、頁(yè)面失效率的高低等諸多問(wèn)題l頁(yè)面越小，內(nèi)部碎片就越少，內(nèi)存利用率就越高，但同時(shí)就會(huì)產(chǎn)生較大的頁(yè)表，占用較大的內(nèi)存空間；l頁(yè)面過(guò)大，會(huì)導(dǎo)致頁(yè)面在內(nèi)外