第5章 存儲(chǔ)管理2

操作系統(tǒng)原理PrinciplesofOperatingSystem,主講：孔憲君,5.4分段存儲(chǔ)管理方式,5.4.1分段存儲(chǔ)管理方式的引入一個(gè)程序由多個(gè)程序段和數(shù)據(jù)段組成，程序通過(guò)分段劃分為多個(gè)模塊，如代碼段、數(shù)據(jù)段、共享段。分段(segment)就是支持這種用戶觀點(diǎn)的內(nèi)存管理方案。每個(gè)程序都有由一組段組成。每個(gè)段都有名稱和長(zhǎng)度。邏輯地址空間是二維的地址空間。邏輯地址由兩個(gè)元素組成：段號(hào)s|段內(nèi)偏移d。,5.4.2分段存儲(chǔ)管理系統(tǒng)的基本原理,進(jìn)程的地址空間被劃分成若干段，每個(gè)段定義一個(gè)完整邏輯意義的信息，段號(hào)從0開始編號(hào)。進(jìn)程加載時(shí)，操作系統(tǒng)為所有段分配其所需內(nèi)存，段與段之間不必連續(xù)，物理內(nèi)存的管理采用分區(qū)式存儲(chǔ)管理方法。,分段存儲(chǔ)管理具體如下：邏輯分段段是一組邏輯信息的集合。將一個(gè)進(jìn)程按照其不同的功能，分成若干個(gè)相對(duì)獨(dú)立的段，為每個(gè)段命名，并編排段號(hào)。內(nèi)存分配管理方法段為內(nèi)存分配的基本單位，為每段分配連續(xù)的內(nèi)存儲(chǔ)存空間，每段的邏輯地址由0地址開始連續(xù)編址，段與段之間是離散的，物理內(nèi)存的管理采用分區(qū)式存儲(chǔ)管理方法。段表為了實(shí)現(xiàn)分段管理，系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)段表，用于描述組成進(jìn)程地址空間的各個(gè)段在內(nèi)存的物理位置，來(lái)實(shí)現(xiàn)進(jìn)程的邏輯地址空間到內(nèi)存存儲(chǔ)空間的映射。段表的表項(xiàng)稱為段描述子，一般包括：段號(hào)s、段長(zhǎng)、段基址(baseaddress)等。,5.4.3分段存儲(chǔ)管理地址變換機(jī)構(gòu),如圖所示，為了完成進(jìn)程邏輯地址到物理地址的映射，CPU會(huì)查找內(nèi)存中的段表，由段號(hào)得到段的基址，加上段內(nèi)偏移，得到實(shí)際的物理地址。,5.4.4段的共享,5.4.5分段與分頁(yè)系統(tǒng)的區(qū)別,頁(yè)幀是信息的物理單位，分頁(yè)是系統(tǒng)管理的需要，以解決內(nèi)存的外碎片問(wèn)題；段是信息的邏輯單位，分段的目的是為了更好地滿足用戶的需要，但分段存儲(chǔ)管理存在外碎片問(wèn)題。頁(yè)的大小是固定的，由系統(tǒng)硬件決定；段的長(zhǎng)度是不固定的，大小由用戶決定。分頁(yè)系統(tǒng)進(jìn)程的地址空間是一維的，即該地址空間是單一的線性地址空間，程序員只需利用一個(gè)標(biāo)識(shí)符，即可表示一個(gè)地址；分段系統(tǒng)進(jìn)程的地址空間是二維的，程序員在標(biāo)識(shí)一個(gè)地址時(shí)，既需給出段名，又需給出段內(nèi)偏移。分頁(yè)對(duì)于用戶是透明，它僅僅用于對(duì)內(nèi)存的管理；分段則對(duì)用戶是可見的。分段存儲(chǔ)管理可以利用段的共享來(lái)實(shí)現(xiàn)內(nèi)存共享；分頁(yè)存儲(chǔ)管理較難實(shí)現(xiàn)內(nèi)存共享。,5.4.6段頁(yè)式存儲(chǔ)管理,分頁(yè)管理和分段管理各有所長(zhǎng)，將分頁(yè)與分段結(jié)合形成段頁(yè)式存儲(chǔ)管理技術(shù)。在段頁(yè)式系統(tǒng)中，一個(gè)進(jìn)程的地址空間被分成若干段，每段又被分成若干固定大小的頁(yè)面。,9,段頁(yè)式存儲(chǔ)管理基本原理如下：進(jìn)程按其邏輯意義分段。段內(nèi)分頁(yè)。內(nèi)存實(shí)施分頁(yè)存儲(chǔ)管理，以頁(yè)幀為單位分配內(nèi)存。邏輯地址結(jié)構(gòu)為三元組：段號(hào)s，頁(yè)號(hào)p，偏移量d，V（s|p|d）,實(shí)現(xiàn)段頁(yè)式存儲(chǔ)管理需要兩個(gè)重要的數(shù)據(jù)結(jié)構(gòu)，即段表和頁(yè)表。系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)段表。其段描述子如下：段號(hào)、頁(yè)表始址、頁(yè)表大小、存取控制、狀態(tài)等。每個(gè)段建立一個(gè)頁(yè)表。其頁(yè)描述子如下：頁(yè)號(hào)、幀號(hào)、訪問(wèn)位、修改位等。,2.段頁(yè)式存儲(chǔ)管理地址變換過(guò)程,如圖所示段頁(yè)式存儲(chǔ)管理地址變換過(guò)程如下：從段表寄存器讀取段表始址，找到段表。段號(hào)段表始址，得到段描述子地址。從段描述子讀取頁(yè)表始址，頁(yè)號(hào)頁(yè)表始址，得到頁(yè)描述子地址。從頁(yè)描述子讀取幀號(hào)。由幀號(hào)f和偏移量拼成物理地址。在段頁(yè)式存儲(chǔ)管理中,CPU每次訪問(wèn)一個(gè)在內(nèi)存中的操作數(shù)，需要要三次訪問(wèn)內(nèi)存，第一次訪問(wèn)內(nèi)存段表取得頁(yè)表始址，第二次訪問(wèn)頁(yè)表取得幀號(hào)，形成物理地址，第三次訪問(wèn)內(nèi)存中的操作數(shù)。,12,段頁(yè)式存儲(chǔ)管理地址變換過(guò)程,5.5虛擬存儲(chǔ)器,CPU執(zhí)行的指令和數(shù)據(jù)必須在物理內(nèi)存中第一種方法是將整個(gè)程序放進(jìn)內(nèi)存中第二種方法是將正在執(zhí)行的部分程序放進(jìn)內(nèi)存中。覆蓋技術(shù)允許程序部分裝入，但是需要程序員做一些額外的工作。虛擬存儲(chǔ)器（virtualmemory）技術(shù)允許程序部分裝入內(nèi)存，這種方案的一個(gè)很大的優(yōu)點(diǎn)就是程序的邏輯地址空間可以比物理內(nèi)存大。而且，虛擬存儲(chǔ)器將內(nèi)存抽象成一個(gè)巨大的、統(tǒng)一的存儲(chǔ)空間，將用戶看到的邏輯內(nèi)存與物理內(nèi)存分開，這種技術(shù)允許程序員不受內(nèi)存存儲(chǔ)的限制。,14,5.5.1局部性原理,時(shí)間局部性，一條指令的一次執(zhí)行和下次執(zhí)行，一個(gè)數(shù)據(jù)的一次訪問(wèn)和下次訪問(wèn)都集中在一個(gè)較短時(shí)期內(nèi)。空間局部性，當(dāng)前執(zhí)行的指令和其鄰近的幾條指令，當(dāng)前訪問(wèn)的數(shù)據(jù)和鄰近的數(shù)據(jù)都集中在一個(gè)較小區(qū)域內(nèi)。進(jìn)程中有些部分是彼此互斥的，不是每次運(yùn)行時(shí)都能執(zhí)行到。,15,5.5.2虛擬存儲(chǔ)器的基本原理,在進(jìn)程裝入時(shí)，不必將其全部裝入內(nèi)存，而只要將當(dāng)前需要執(zhí)行的部分頁(yè)或段裝入內(nèi)存，就可以讓進(jìn)程執(zhí)行。在進(jìn)程執(zhí)行過(guò)程中，如果需要執(zhí)行的指令或訪問(wèn)的數(shù)據(jù)尚未在內(nèi)存(稱為缺頁(yè)或缺段)，則由操作系統(tǒng)將相應(yīng)的頁(yè)或段調(diào)入內(nèi)存，然后繼續(xù)執(zhí)行進(jìn)程。操作系統(tǒng)可以將內(nèi)存中暫時(shí)不使用的頁(yè)或段調(diào)出，保存在外存上，從而騰出空間存放將要裝入的進(jìn)程以及將要調(diào)入的頁(yè)或段。,所謂虛擬存儲(chǔ)器就是將用戶邏輯內(nèi)存與物理內(nèi)存分離，具有請(qǐng)求調(diào)入功能和置換功能，為用戶提供了一個(gè)存儲(chǔ)容量比實(shí)際內(nèi)存大得多的存儲(chǔ)器管理系統(tǒng)。,5.5.3虛擬存儲(chǔ)器的分類虛擬存儲(chǔ)器技術(shù)一般可以分為三類：請(qǐng)求分頁(yè)存儲(chǔ)管理請(qǐng)求分頁(yè)存儲(chǔ)管理在分頁(yè)存儲(chǔ)管理的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)等功能。與分頁(yè)存儲(chǔ)管理不同，請(qǐng)求分頁(yè)管理系統(tǒng)只需進(jìn)程的部分頁(yè)面調(diào)入內(nèi)存即可以運(yùn)行。請(qǐng)求分段存儲(chǔ)管理請(qǐng)求分段存儲(chǔ)管理在分段存儲(chǔ)管理的基礎(chǔ)上，增加了請(qǐng)求調(diào)段或段的動(dòng)態(tài)鏈接等功能。地址空間中各程序段在運(yùn)行時(shí)并不全部裝入內(nèi)存，而是調(diào)入一個(gè)或少數(shù)幾個(gè)程序段運(yùn)行，在運(yùn)行過(guò)程中需要調(diào)用到哪段時(shí)，就根據(jù)該段長(zhǎng)度在內(nèi)存分配一個(gè)連續(xù)的分區(qū)給它使用。若內(nèi)存中沒(méi)有足夠大的空閑分區(qū)，則考慮進(jìn)行段的緊湊或?qū)⒛扯翁蕴鋈?。這種存儲(chǔ)管理技術(shù)稱為請(qǐng)求分段存儲(chǔ)管理。請(qǐng)求段頁(yè)式存儲(chǔ)管理。請(qǐng)求段頁(yè)式存儲(chǔ)管理是請(qǐng)求分頁(yè)和請(qǐng)求分段存儲(chǔ)管理的結(jié)合。請(qǐng)求段頁(yè)式存儲(chǔ)管理的內(nèi)存分配單位是幀。邏輯地址是由段號(hào)、段內(nèi)頁(yè)號(hào)、頁(yè)內(nèi)偏移地址三部分組成的。在地址變換的過(guò)程中會(huì)產(chǎn)生缺段中斷和缺頁(yè)中斷兩種不同類型的中斷。,5.5.4虛擬存儲(chǔ)器的容量,一個(gè)虛擬存儲(chǔ)器的容量由以下兩個(gè)因素決定：虛擬存儲(chǔ)器的容量受CPU的尋址能力的限制，CPU的尋址能力由計(jì)算機(jī)CPU地址總線結(jié)構(gòu)確定的，它是影響虛擬存儲(chǔ)器最大容量的重要參數(shù)。例如：某計(jì)算機(jī)CPU的地址總線長(zhǎng)度為32位，則CPU可以尋址范圍是0232-1，即4G。一般來(lái)說(shuō)，虛擬存儲(chǔ)器的容量由內(nèi)存和外存對(duì)換區(qū)容量之和所確定；有些虛擬存儲(chǔ)器技術(shù)還要考慮加上進(jìn)程文件區(qū)的容量。很多教材認(rèn)為“虛擬存儲(chǔ)器的容量由內(nèi)存和外存之和所確定”，這種說(shuō)法是不正確的，外存的容量可能很大（如200G），不可能全部作為外存對(duì)換區(qū)，同時(shí)虛擬存儲(chǔ)器的容量也受CPU的尋址能力的限制。,5.5.5虛擬存儲(chǔ)器的特征,一次性和駐留性并非是進(jìn)程運(yùn)行所必需的條件，虛擬存儲(chǔ)器主要特征如下：離散性。虛擬存儲(chǔ)器必須建立在離散分配的基礎(chǔ)上，在分頁(yè)、分段、段頁(yè)式存儲(chǔ)管理的基礎(chǔ)上才能實(shí)現(xiàn)虛擬存儲(chǔ)器。多次性?；诰植啃栽?，虛擬存儲(chǔ)器將一個(gè)進(jìn)程分成多次調(diào)入內(nèi)存，多次性是虛擬存儲(chǔ)器最重要的特征。對(duì)換性。虛擬性。,20,5.5.6交換區(qū)策略、換入策略和置換策略,1.交換區(qū)策略2.頁(yè)面換入策略請(qǐng)求換頁(yè)(demandpaging)。預(yù)換頁(yè)(prepaging)。3.置換策略固定分配局部置換(fixedallocation，localreplacement)?？勺兎峙淙种脫Q(variableallocation，globalreplacement)?？勺兎峙渚植恐脫Q(variableallocation，localreplacement)。,5.6請(qǐng)求分頁(yè)存儲(chǔ)管理,5.6.1請(qǐng)求分頁(yè)存儲(chǔ)管理的實(shí)現(xiàn)原理內(nèi)存按分頁(yè)管理。虛擬地址結(jié)構(gòu)為：虛頁(yè)號(hào)p|偏移量d。根據(jù)局部性原理，進(jìn)程的部分頁(yè)面裝入內(nèi)存即可運(yùn)行，進(jìn)程的全部頁(yè)面均有機(jī)會(huì)獲得到內(nèi)存執(zhí)行的機(jī)會(huì)。即將要訪問(wèn)的頁(yè)面不在內(nèi)存，由缺頁(yè)中斷機(jī)構(gòu)就立即產(chǎn)生中斷信號(hào)，將缺頁(yè)裝入內(nèi)存。缺頁(yè)中斷機(jī)構(gòu)由硬件和軟件組成。進(jìn)程運(yùn)行需要內(nèi)存頁(yè)幀，如果內(nèi)存沒(méi)有空閑幀時(shí)，由頁(yè)面置換算法將一些老頁(yè)從內(nèi)存中淘汰出局，為即將被調(diào)入的新頁(yè)騰出空位。即老頁(yè)與新頁(yè)在內(nèi)外存的對(duì)換。,5.6.2請(qǐng)求分頁(yè)存儲(chǔ)管理的實(shí)現(xiàn)機(jī)制,1頁(yè)描述子的擴(kuò)充在請(qǐng)求分頁(yè)系統(tǒng)中，一般對(duì)頁(yè)描述子進(jìn)行如下擴(kuò)充，除了頁(yè)號(hào)對(duì)應(yīng)的幀號(hào)外，還增加了狀態(tài)位、修改位、訪問(wèn)字段、存取控制、外存地址等。狀態(tài)位用于指示該頁(yè)是否已經(jīng)調(diào)入了內(nèi)存，“1”表示該頁(yè)在內(nèi)存中，“0”該頁(yè)不在內(nèi)存中。若不在內(nèi)存之中，則產(chǎn)生缺頁(yè)中斷。修改位表示該頁(yè)調(diào)入內(nèi)存后是否被修改過(guò)?！?”表示該頁(yè)被修改過(guò)，“0”相反。訪問(wèn)字段用于記錄本頁(yè)在一定時(shí)間內(nèi)被訪問(wèn)的次數(shù)，或記錄最近已經(jīng)有多長(zhǎng)時(shí)間未被訪問(wèn)。存取控制審定訪問(wèn)權(quán)限。外存地址用于指出該頁(yè)在外存對(duì)換區(qū)中的地址，供調(diào)入該頁(yè)時(shí)使用。,2缺頁(yè)中斷機(jī)制在請(qǐng)求分頁(yè)系統(tǒng)中，CPU硬件一定要提供對(duì)缺頁(yè)中斷的支持，根據(jù)頁(yè)描述子中的狀態(tài)位判斷是否產(chǎn)生缺頁(yè)中斷。缺頁(yè)中斷是一個(gè)比較特殊的中斷，這主要體現(xiàn)在以下兩方面：在指令的執(zhí)行期間產(chǎn)生和處理缺頁(yè)中斷信號(hào)。通常的CPU外部中斷是在每條指令執(zhí)行完畢后檢查是否有中斷請(qǐng)求到達(dá)。而缺頁(yè)中斷是在一條指令的執(zhí)行期間發(fā)現(xiàn)要訪問(wèn)的指令和數(shù)據(jù)不在內(nèi)存時(shí)產(chǎn)生和處理的。一條指令可以產(chǎn)生多個(gè)缺頁(yè)中斷。例如，有一條雙操作數(shù)的指令，每個(gè)操作數(shù)都不在內(nèi)存中，當(dāng)這條指令執(zhí)行時(shí)，將產(chǎn)生多個(gè)中斷。CPU提供的硬件支持還要體現(xiàn)在當(dāng)從中斷處理進(jìn)程返回時(shí)，能夠正確執(zhí)行產(chǎn)生缺頁(yè)中斷的指令。,3請(qǐng)求分頁(yè)存儲(chǔ)管理的地址變換流程圖,4.6.3頁(yè)面置換算法,頁(yè)面在內(nèi)外存之間來(lái)回替換叫抖動(dòng)，抖動(dòng)會(huì)引起不必要的額外開銷。1先進(jìn)先出算法先進(jìn)先出算法（FIFO）的基本思想是先進(jìn)入內(nèi)存的頁(yè)面，先被換出，總是先淘汰那些駐留在內(nèi)存時(shí)間最長(zhǎng)的頁(yè)面。理由是：最先進(jìn)入內(nèi)存的頁(yè)面不再被訪問(wèn)的可能性最大。可以通過(guò)隊(duì)列來(lái)表示各頁(yè)的裝入時(shí)間先后。,2最佳置換算算法,最佳頁(yè)面置換算法(Optimal，OPT)是淘汰永不使用的或是在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。就是說(shuō)從內(nèi)存中移出以后不再使用的頁(yè)面，如無(wú)這樣的頁(yè)面，則選擇以后最長(zhǎng)時(shí)間內(nèi)不需要訪問(wèn)的頁(yè)，這就是最佳置換法。,3最近最久未使用置換算法,最近最久未使用置換算法(LeastRecentlyUsed，LRU)的基本思想是根據(jù)局部性原理，如果某一頁(yè)被訪問(wèn)了，那么它很可能馬上又被訪問(wèn)。反之，如果某一頁(yè)很長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)，那么最近也不太可能會(huì)被訪問(wèn)。其實(shí)質(zhì)是，當(dāng)需要置換一頁(yè)時(shí)，選擇在最近一段時(shí)間最久未使用的頁(yè)面予以淘汰。,5.頁(yè)面緩沖算法,頁(yè)面緩沖算法(pagebuffering)是對(duì)FIFO算法的發(fā)展.通過(guò)建立置換頁(yè)面的緩沖，從而有機(jī)會(huì)找回剛被置換的頁(yè)面，從而減少系統(tǒng)I/O的開銷。頁(yè)面緩沖算法用FIFO算法選擇被置換頁(yè)，把被置換的頁(yè)面放入兩個(gè)鏈表之一。如果頁(yè)面未被修改，就將其歸入到空閑頁(yè)面鏈表的末尾，否則將其歸入已修改頁(yè)面鏈表。,空閑頁(yè)面和已修改頁(yè)面仍在內(nèi)存中停留一段時(shí)間，如果這些頁(yè)面被再次訪問(wèn)，只需較小開銷，就可以返還被訪問(wèn)的頁(yè)面作為進(jìn)程的內(nèi)存頁(yè)。需要調(diào)入新的物理頁(yè)面時(shí)，將新頁(yè)面內(nèi)容讀入到空閑頁(yè)面鏈表的第一項(xiàng)所指的頁(yè)面，然后將第一項(xiàng)刪除。當(dāng)已修改頁(yè)面達(dá)到一定數(shù)目后，再將他們一起調(diào)出到外存，然后將他們歸入空閑頁(yè)面鏈表，這樣能大大減少I/O操作的次數(shù)。該方法容易實(shí)現(xiàn)，性能較好，WindowNT內(nèi)核系列操作系統(tǒng)就使用該方法。,6.時(shí)鐘置換算法,時(shí)鐘置換算法(ClockAlgorithm)需要為每一個(gè)裝入內(nèi)存的頁(yè)面設(shè)置一個(gè)使用位(UseBit，簡(jiǎn)稱為U位)，當(dāng)某個(gè)頁(yè)面被裝入內(nèi)存時(shí)，其U位被置為0，每當(dāng)某個(gè)頁(yè)面被進(jìn)程引用時(shí)，相應(yīng)的U位將被置為1。同時(shí)，系統(tǒng)還把置換范圍內(nèi)的所有頁(yè)面通過(guò)鏈接指針組織成一個(gè)循環(huán)隊(duì)列，并為該隊(duì)列設(shè)置一個(gè)掃描指針。掃描指針用于記錄上一次進(jìn)行頁(yè)面置換時(shí)被置換頁(yè)面所在位置的下一個(gè)位置。當(dāng)需要進(jìn)行頁(yè)面置換時(shí)，系統(tǒng)將移動(dòng)掃描指針查找置換范圍內(nèi)一個(gè)U位為0的頁(yè)面，即自上次置換以來(lái)未被使用過(guò)的頁(yè)面。,31,如果當(dāng)前掃描指針?biāo)赶虻捻?yè)面的U位為0，那么系統(tǒng)將把該頁(yè)面作為被置換頁(yè)面。并將掃描指針移到下一個(gè)頁(yè)面位置，停止搜索。如果當(dāng)前掃描指針?biāo)赶虻捻?yè)面的U位為1，那么系統(tǒng)將把該頁(yè)面的U位設(shè)置為0，掃描指針移到下一個(gè)位置，繼續(xù)搜索。如果該循環(huán)隊(duì)列中所有頁(yè)面的U位都為1，那么，掃描指針將移動(dòng)一圈以后回到原處。這時(shí)，循環(huán)隊(duì)列中的所有頁(yè)面的U位都為0，選擇淘汰掃描指針最初指向的頁(yè)面，算法終止?？梢?，該算法中的掃描指針類似于時(shí)鐘指針，進(jìn)行頁(yè)面置換時(shí)，該指針在頁(yè)面組成的環(huán)行隊(duì)列中逐位地移動(dòng)，故形象地稱之為Clock置換算法。,5.6.4工作集模型,1.工作集一個(gè)進(jìn)程在時(shí)間t的工作集可以形式化的定義為：對(duì)于給定的訪問(wèn)序列選取定長(zhǎng)的區(qū)間，落在工作集窗口中的頁(yè)面集合稱為工作集。WS（t）=在時(shí)間t-到t之間所訪問(wèn)的一串頁(yè)面的集合其中，為工作集窗口尺寸。如圖所示，工作集模型的例子中，=10