存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)中最重要的資源之一。因?yàn)槿魏纬绦蚝蛿?shù)據(jù)以及各種控制用的數(shù)據(jù)結(jié)構(gòu)都必須占有一定的存儲(chǔ)空間，因此，存儲(chǔ)管理直接影響系統(tǒng)性能。

存儲(chǔ)器由內(nèi)存和外存組成。內(nèi)存是由系統(tǒng)實(shí)際提供的存儲(chǔ)單元（常指字節(jié)）組成的一個(gè)連續(xù)地址空間，處理器可直接存取。外存（輔存）是指軟盤、硬盤、光盤和磁帶等一些外部存儲(chǔ)部件，常用來(lái)存放暫不執(zhí)行的程序和數(shù)據(jù)。處理器不能直接訪問(wèn)外存，需通過(guò)啟動(dòng) I/O（Input/Output，輸入/輸出）設(shè)備才能進(jìn)行內(nèi)存、外存交換，其訪問(wèn)速度慢，但價(jià)格便宜， 常用作內(nèi)存的后援設(shè)備。

內(nèi)存大小由系統(tǒng)硬件決定，存儲(chǔ)容量受到實(shí)際存儲(chǔ)單元的限制。虛擬存儲(chǔ)器（簡(jiǎn)稱虛存）不考慮實(shí)際內(nèi)存的大小和數(shù)據(jù)存取的實(shí)際地址，只考慮相互有關(guān)的數(shù)據(jù)之間的相對(duì)位置，其容量由計(jì)算機(jī)地址的位數(shù)決定。

系統(tǒng)中內(nèi)存的使用一般分成兩部分，一部分為系統(tǒng)空間，存放操作系統(tǒng)本身及相關(guān)的系統(tǒng)程序；另一部分為用戶空間，存放用戶的程序和數(shù)據(jù)。

存儲(chǔ)管理主要是指對(duì)內(nèi)存儲(chǔ)器的管理，負(fù)責(zé)對(duì)內(nèi)存的分配和回收、內(nèi)存的保護(hù)和內(nèi)存的擴(kuò)充。

存儲(chǔ)管理的目的是盡量提高內(nèi)存的使用效率。

1 地址變換

由進(jìn)程中的目標(biāo)代碼 、 數(shù)據(jù)等的虛擬地址組成的虛擬空間稱為虛擬存儲(chǔ)器，虛擬存儲(chǔ)器允許用戶用比內(nèi)存容量大得多的地址空間來(lái)編程，以運(yùn)行比內(nèi)存實(shí)際容量大得多的程序。用戶編程所用的地址稱為邏輯地址 ( 虛地址 ) ，而實(shí)際的內(nèi)存地址則稱為物理地址 ( 實(shí)地址 ) 。每次訪問(wèn)內(nèi)存時(shí)都要進(jìn)行邏輯地址到物理地址的轉(zhuǎn)換，這種轉(zhuǎn)換是由硬件完成的，而內(nèi)存和外存之間的信息動(dòng)態(tài)調(diào)度是由硬件和操作系統(tǒng)兩者配合完成的。

靜態(tài)重定位 : 靜態(tài)重定位是在虛空間程序執(zhí)行之前由裝配程序完成地址映射工作。靜態(tài)重定位的優(yōu)點(diǎn)是不需要硬件的支持。 缺點(diǎn)是無(wú)法實(shí)現(xiàn)虛擬存儲(chǔ)器，必須占用連續(xù)的內(nèi)存空間，且難以做到程序和數(shù)據(jù)的共享。

動(dòng)態(tài)重定位 : 動(dòng)態(tài)重定位是在程序執(zhí)行過(guò)程中，在 CPU 訪問(wèn)內(nèi)存之前，將要訪問(wèn)的程序或數(shù)據(jù)地址轉(zhuǎn)換為內(nèi)存地址。動(dòng)態(tài)重定位依靠硬件地址變換機(jī)構(gòu)完成，其優(yōu)點(diǎn)主要有 : 可以對(duì)內(nèi)存進(jìn)行非連續(xù)分配，提供了虛擬存儲(chǔ)器的基礎(chǔ)，有利于程序段的共享 。

2 存儲(chǔ)組織

虛擬存儲(chǔ)器可以分為單一連續(xù)分區(qū) 、 固定分區(qū) 、 可變分區(qū) 、 可重定位分區(qū) 、 頁(yè)式 、 段式 、 段頁(yè)式 7 種 。

單一連續(xù)分區(qū)。把所有用戶區(qū)都分配給唯一的用戶作業(yè)，當(dāng)作業(yè)被調(diào)度時(shí)，進(jìn)程全部進(jìn)入內(nèi)存，一旦完成，所有內(nèi)存恢復(fù)空閑，因此，它不支持多道程序設(shè)計(jì) 。

固定分區(qū)。這是支持多道程序設(shè)計(jì)的最簡(jiǎn)單的存儲(chǔ)管理方法，它把內(nèi)存劃分成若干個(gè)固定的和大小不同的分區(qū)，每個(gè)分區(qū)能夠裝入一個(gè)作業(yè)，分區(qū)的大小是固定的，算法簡(jiǎn)單，但是容易生成較多的存儲(chǔ)器碎片 。

可變分區(qū)。引入可變分區(qū)后雖然內(nèi)存分配更靈活，也提高了內(nèi)存利用率，但是由于系統(tǒng)在不斷地分配和回收中，必定會(huì)出現(xiàn)一些不連續(xù)的小的空閑區(qū)，盡管這些小的空閑區(qū)的總和超過(guò)某一個(gè)作業(yè)要求的空間，但是由于不連續(xù)而無(wú)法分配， 產(chǎn)生了碎片解決碎片的方法是拼接 ( 緊湊 ) ，即向一個(gè)方向 ( 如向低地址端 ) 移動(dòng)已分配的作業(yè)，使那些零散的小空閑區(qū)在另一方向連成一片。分區(qū)的拼接技術(shù)，一方面是要求能夠?qū)ψ鳂I(yè)進(jìn)行重定位，另一方面系統(tǒng)在拼接時(shí)要耗費(fèi)較多的時(shí)間。

可重定位分區(qū)。這是克服固定分區(qū)碎片問(wèn)題的一種存儲(chǔ)分配方法，它能夠把相鄰的空閑存儲(chǔ)空間合并成一個(gè)完整的空區(qū)，還能夠整理存儲(chǔ)器內(nèi)各個(gè)作業(yè)的存儲(chǔ)位置，以達(dá)到消除存儲(chǔ)碎片和緊縮存儲(chǔ)空間的目的。緊縮工作需要花費(fèi)大量的時(shí)間和系統(tǒng)資源。

另外還有三種存儲(chǔ)組織方式：頁(yè)式 、 段式 、 段頁(yè)式，下面我們將詳細(xì)解讀段頁(yè)式存儲(chǔ)管理。

2.1 頁(yè)式存儲(chǔ)管理

分頁(yè)的基本思想是把程序的邏輯空間和內(nèi)存的物理空間按照同樣的大小劃分成若干頁(yè)面，并以頁(yè)面為單位進(jìn)行分配。在頁(yè)式存儲(chǔ)管理中，系統(tǒng)中虛地址是一個(gè)有序?qū)Γ?yè)號(hào)，位移）。系統(tǒng)為每一個(gè)進(jìn)程建立一個(gè)頁(yè)表，其內(nèi)容包括進(jìn)程的邏輯頁(yè)號(hào)與物理頁(yè)號(hào)的對(duì)應(yīng)關(guān)系、狀態(tài)等。

頁(yè)式系統(tǒng)的動(dòng)態(tài)地址轉(zhuǎn)換是這樣進(jìn)行的：當(dāng)進(jìn)程運(yùn)行時(shí)，其頁(yè)表的首地址已在系統(tǒng)的動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)中的基本地址寄存器中。執(zhí)行的指令訪問(wèn)虛存地址（ p， d）時(shí)，首先根據(jù)頁(yè)號(hào) p 查頁(yè)表，由狀態(tài)可知，這個(gè)頁(yè)是否已經(jīng)調(diào)入內(nèi)存。若已調(diào)入內(nèi)存，則得到該頁(yè)的內(nèi)存位置 p2，然后，與頁(yè)內(nèi)相對(duì)位移 d 組合，得到物理地址 r。如果該頁(yè)尚未調(diào)入內(nèi)存，則產(chǎn)生缺頁(yè)中斷，以裝入所需的頁(yè)，如圖 1 所示。

頁(yè)式虛擬存儲(chǔ)管理是在頁(yè)式存儲(chǔ)管理的基礎(chǔ)上實(shí)現(xiàn)虛擬存儲(chǔ)器的。首先把作業(yè)信息作為副本存放在磁盤上，作業(yè)執(zhí)行時(shí)，把作業(yè)信息的部分頁(yè)面裝入內(nèi)存儲(chǔ)器，作業(yè)執(zhí)行時(shí)若所訪問(wèn)的頁(yè)面已在內(nèi)存中，則按頁(yè)式存儲(chǔ)管理方式進(jìn)行地址轉(zhuǎn)換，得到欲訪問(wèn)的內(nèi)存絕對(duì)地址，若欲訪問(wèn)的頁(yè)面不在內(nèi)存中，則產(chǎn)生一個(gè)“缺頁(yè)中斷”，由操作系統(tǒng)把當(dāng)前所需的頁(yè)面裝入內(nèi)存。

為此，在裝入作業(yè)時(shí)，就應(yīng)在該作業(yè)的頁(yè)表中指出哪些頁(yè)已在內(nèi)存中，哪些頁(yè)還沒(méi)有裝入內(nèi)存?？捎靡粋€(gè)標(biāo)志位來(lái)指示對(duì)應(yīng)頁(yè)是否在內(nèi)存中，比如假設(shè)標(biāo)志位為 1 表示該頁(yè)在內(nèi)存，而標(biāo)志位為 0 表示該頁(yè)尚未裝入內(nèi)存。為了能方便地從磁盤上找到作業(yè)信息的副本，故在頁(yè)表中還可指出每一頁(yè)副本在磁盤上的位置。

當(dāng)要裝入一個(gè)當(dāng)前需要的頁(yè)面時(shí)，如果內(nèi)存儲(chǔ)器中無(wú)空閑塊，則可選擇一個(gè)已在內(nèi)存中的頁(yè)面，把它暫時(shí)調(diào)出內(nèi)存。若在執(zhí)行中該頁(yè)面被修改過(guò)，則把該頁(yè)信息重新寫回到磁盤上，否則不必重新寫回磁盤。當(dāng)一頁(yè)被暫時(shí)調(diào)出內(nèi)存后，讓出的內(nèi)存空間用來(lái)存放當(dāng)前需要使用的頁(yè)面。以后再使用被調(diào)出的頁(yè)面時(shí)，可用同樣的方法調(diào)出另一個(gè)頁(yè)面而將其再裝入內(nèi)存。頁(yè)面被調(diào)出或裝入之后都要對(duì)頁(yè)表中的相應(yīng)表目做修改。

2.2 段式存儲(chǔ)管理

段式存儲(chǔ)管理與頁(yè)式存儲(chǔ)管理類似。分段的基本思想是把用戶作業(yè)按邏輯上有完整意義的段來(lái)進(jìn)行劃分，并以段為單位作為內(nèi)外存交換的空間尺度。

一個(gè)作業(yè)是由若干個(gè)具有邏輯意義的段（如主程序、子程序、數(shù)據(jù)段等）組成。分段系統(tǒng)中，容許程序（作業(yè)）占據(jù)內(nèi)存中許多分離的分區(qū)。每個(gè)分區(qū)存儲(chǔ)一個(gè)程序分段。這樣，每個(gè)作業(yè)需要幾對(duì)界限地址寄存器來(lái)判定訪問(wèn)地址是否越界，實(shí)現(xiàn)復(fù)雜。在分段存儲(chǔ)系統(tǒng)中常常利用存儲(chǔ)保護(hù)鍵實(shí)現(xiàn)存儲(chǔ)保護(hù)。分段系統(tǒng)中虛地址是一個(gè)有序?qū)Γǘ翁?hào)，位移）。系統(tǒng)為每個(gè)作業(yè)建立一個(gè)段表，其內(nèi)容包括段號(hào)、段長(zhǎng)、內(nèi)存起始地址和狀態(tài)等。狀態(tài)指出這個(gè)段是否已調(diào)入內(nèi)存，即內(nèi)存起始地址指出這個(gè)段，狀態(tài)指出這個(gè)段的訪問(wèn)權(quán)限。

分段系統(tǒng)的動(dòng)態(tài)地址轉(zhuǎn)換是這樣進(jìn)行的：進(jìn)程執(zhí)行時(shí)，其段表的首地址已在基本地址寄存器中，執(zhí)行的指令訪問(wèn)虛存（s， d）（取指令或取操作數(shù)）時(shí)，首先根據(jù)段號(hào) s 查段表，若段已經(jīng)調(diào)入內(nèi)存，則得到該段的內(nèi)存起始地址，然后與段內(nèi)相對(duì)地址（段內(nèi)偏移量 d）相加，得到實(shí)際地址。如果該段尚未調(diào)入內(nèi)存，則產(chǎn)生缺段中斷，以裝入所需要的段。段式存儲(chǔ)與頁(yè)式存儲(chǔ)的地址轉(zhuǎn)換方式類似。

段式虛擬存儲(chǔ)管理仍然以段式存儲(chǔ)管理為基礎(chǔ)，為用戶提供比內(nèi)存實(shí)際容量大的虛擬空間。段式虛擬存儲(chǔ)管理把作業(yè)中的各個(gè)分段信息都保留在磁盤上，當(dāng)作業(yè)可以投入執(zhí)行時(shí)，做如下操作：

首先把當(dāng)前需要的一段或幾段裝入內(nèi)存。

作業(yè)執(zhí)行時(shí)，如果要訪問(wèn)的段已經(jīng)在內(nèi)存，則按照“段式存儲(chǔ)管理” 中的方式進(jìn)行地址轉(zhuǎn)換；如果要訪問(wèn)的段不在內(nèi)存中，則產(chǎn)生一個(gè)“缺段中斷”，由操作系統(tǒng)把當(dāng)前需要的段裝入內(nèi)存。

因此，在段表中應(yīng)增設(shè)段是否在內(nèi)存的標(biāo)志以及各段在磁盤上的位置，已在內(nèi)存中的段仍要指出該段在內(nèi)存中的起始地址和占用內(nèi)存區(qū)長(zhǎng)度。

作業(yè)執(zhí)行要訪問(wèn)的段時(shí)，由硬件的地址轉(zhuǎn)換模塊查段表。若該段在內(nèi)存中，則立即把邏輯地址轉(zhuǎn)換成絕對(duì)地址；若該段不在內(nèi)存中，則形成“缺段中斷”，由操作系統(tǒng)處理這個(gè)中斷。

處理的辦法是，查內(nèi)存分配表，找出一個(gè)足夠大的連續(xù)區(qū)以容納該分段，如果找不到足夠大的連續(xù)區(qū)則檢查空閑區(qū)的總和，若空閑區(qū)總和能滿足該段要求，那么進(jìn)行適當(dāng)移動(dòng)將分散的空閑區(qū)集中起來(lái)；若空閑區(qū)總和不能滿足該段要求，可把內(nèi)存中的一段或幾段調(diào)出，然后把當(dāng)前要訪問(wèn)的段裝入內(nèi)存中。段被移動(dòng)、調(diào)出和裝入后都要對(duì)段表中的相應(yīng)屬性進(jìn)行修改。新的段被裝入后應(yīng)讓作業(yè)重新執(zhí)行被中斷的指令，這時(shí)就能找到要訪問(wèn)的段，也可以繼續(xù)執(zhí)行下去。

2.3 段頁(yè)式存儲(chǔ)管理

段頁(yè)式管理是段式和頁(yè)式兩種管理方法結(jié)合的產(chǎn)物，綜合了段式組織與頁(yè)式組織的特點(diǎn)，根據(jù)程序模塊分段，段內(nèi)再分頁(yè)，內(nèi)存被分劃成定長(zhǎng)的頁(yè)。段頁(yè)式系統(tǒng)中虛地址形式是（段號(hào)、 頁(yè)號(hào)、頁(yè)內(nèi)偏移），如圖 2 所示。系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)段表，為每個(gè)段建立一個(gè)頁(yè)表。段頁(yè)式管理采用段式分配、頁(yè)式使用的方法，便于動(dòng)態(tài)連接和存儲(chǔ)的動(dòng)態(tài)分配。這種存儲(chǔ)管理能提高內(nèi)存空間的利用率。

段式虛擬管理還是以段為單位分配內(nèi)存空間，整段的調(diào)出、裝入，有時(shí)還要移動(dòng)，這些都增加了系統(tǒng)的開銷。如果按段頁(yè)式存儲(chǔ)管理的方式，把每一段再分成若干頁(yè)面，那么，每一段不必占用連續(xù)的存儲(chǔ)空間；甚至當(dāng)內(nèi)存塊不夠時(shí)，可只將一段中的部分頁(yè)面裝入內(nèi)存，這種管理方式稱為“段頁(yè)式虛擬存儲(chǔ)管理”。

段頁(yè)式虛擬存儲(chǔ)管理為每一個(gè)裝入內(nèi)存的作業(yè)建立一張段表，還要為每一段建立頁(yè)表。段表中指出該段的頁(yè)表存放位置及長(zhǎng)度，頁(yè)表中應(yīng)指出該段的各頁(yè)在磁盤上的位置以及頁(yè)是否在內(nèi)存中。若在內(nèi)存中，則填上占用的內(nèi)存塊號(hào)。作業(yè)執(zhí)行時(shí)按段號(hào)查段表，找到相應(yīng)的頁(yè)表再根據(jù)頁(yè)號(hào)查頁(yè)表，由標(biāo)志位判定該頁(yè)是否已在內(nèi)存，若是，則進(jìn)行地址轉(zhuǎn)換；否則進(jìn)行頁(yè)面調(diào)度。地址轉(zhuǎn)換過(guò)程如圖 3 所示。

段頁(yè)式虛擬存儲(chǔ)管理結(jié)合了段式和頁(yè)式的優(yōu)點(diǎn)，但增加了設(shè)置表格（段表、頁(yè)表）和查表等開銷，段頁(yè)式虛擬存儲(chǔ)器一般只在大型計(jì)算機(jī)系統(tǒng)中使用。

常見的虛存組織比較說(shuō)明如下：

3 存儲(chǔ)管理

在虛擬存儲(chǔ)器的管理中，涉及載入 ( 調(diào)入 ) 、 放置 ( 放入分區(qū) ) 和置換 ( swapping ) 等管理內(nèi)容。

調(diào)入策略 : 即何時(shí)將一頁(yè)或一段從外存中調(diào)入內(nèi)存，通常有兩種策略，一種是請(qǐng)求調(diào)入法，即需要使用時(shí)才調(diào)入；另一種是先行調(diào)入法，即將預(yù)計(jì)要使用的頁(yè) / 段先行調(diào)入內(nèi)存。

放置策略 : 也就是調(diào)入后，放在內(nèi)存中的什么位置，這與內(nèi)存管理基本上是一致的。

置換策略 : 由于實(shí)際內(nèi)存是小于虛存的，因此可能會(huì)發(fā)生內(nèi)存已滿，但需要使用的頁(yè)并不在內(nèi)存中的情況 ( 稱為缺頁(yè)中斷 ) 。這時(shí)就需要進(jìn)行置換，即將一些內(nèi)存中的某些頁(yè)放到外存中，騰出空間。這一過(guò)程稱為 swapping 。

當(dāng)內(nèi)存中無(wú)空閑塊時(shí)，為了裝入一個(gè)頁(yè)面而必須按某種算法從已在內(nèi)存的頁(yè)中選擇一頁(yè)，將它暫時(shí)調(diào)出內(nèi)存，讓出內(nèi)存空間以存放所需裝入的頁(yè)面，這個(gè)工作稱為“頁(yè)面調(diào)度”。

如何選擇調(diào)出的頁(yè)面是很重要的，如果采用了一個(gè)不合適的算法，就會(huì)出現(xiàn)這樣的現(xiàn)象：剛被調(diào)出的頁(yè)面又立即要用，因而又要把它裝入，而裝入不久又被選中調(diào)出，調(diào)出不久又被裝入，如此反復(fù)，使調(diào)度非常頻繁。這種現(xiàn)象稱為“抖動(dòng)”。

一個(gè)好的調(diào)度算法應(yīng)減少或避免抖動(dòng)現(xiàn)象。常用的頁(yè)面調(diào)度算法（置換算法）有：

最優(yōu)（OPT）算法。選擇不再使用或最遠(yuǎn)的將來(lái)才被使用的頁(yè)，這是理想的算法，但是難以實(shí)現(xiàn)。

隨機(jī)（RAND）算法。隨機(jī)地選擇需要被淘汰的頁(yè)，開銷小，但是可能選中立即就要訪問(wèn)的頁(yè)。

先進(jìn)先出（FIFO ）算法。調(diào)出在內(nèi)存駐留時(shí)間最長(zhǎng)的頁(yè)，但可能淘汰掉頻繁使用的頁(yè)。該算法簡(jiǎn)單，易實(shí)現(xiàn)?？梢园蜒b入內(nèi)存的那些頁(yè)的頁(yè)號(hào)按進(jìn)入的先后順序排成隊(duì)列，每次總是調(diào)出隊(duì)首的頁(yè)，當(dāng)裝入一個(gè)新頁(yè)
后，把新頁(yè)的頁(yè)號(hào)排到隊(duì)尾。

最近最少使用（Least Recently Used， LRU）算法。選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)使用得最少的頁(yè)。這個(gè)算法的主要理論依據(jù)是，如果某個(gè)頁(yè)被訪問(wèn)了，則它可能馬上就要被訪問(wèn)；反之，如果某個(gè)頁(yè)長(zhǎng)時(shí)間未被訪問(wèn)，則它在最近一段時(shí)間也不會(huì)被訪問(wèn)。

另外，使用 FIFO 算法時(shí)，在未給予進(jìn)程分配足夠的頁(yè)面時(shí)，有時(shí)會(huì)出現(xiàn)給予進(jìn)程的頁(yè)面數(shù)越多，缺頁(yè)次數(shù)反而增加的異?，F(xiàn)象，這稱為 Belady 現(xiàn)象。例如，若某個(gè)進(jìn)程訪問(wèn)頁(yè)面的順序 ( 稱頁(yè)面訪問(wèn)序列 ) 是 1,2,3,4,1,2,5,1,2,3,4,5，當(dāng)進(jìn)程擁有3個(gè)主存頁(yè)面時(shí)，發(fā)生缺頁(yè)率比擁有4個(gè)主存頁(yè)面時(shí)要小。

具體分析如下：

當(dāng)要訪問(wèn)頁(yè)面 1 時(shí)，發(fā)生缺頁(yè)中斷，系統(tǒng)載入頁(yè)面 4；

接著，當(dāng)訪問(wèn)頁(yè)面 2 與 3時(shí)，連續(xù)發(fā)生缺頁(yè)中斷，系統(tǒng)載入頁(yè)面 2與頁(yè)面 3；這時(shí)，進(jìn)程所擁有的三個(gè)主存頁(yè)都已占滿。

當(dāng)要訪問(wèn)頁(yè)面 4 時(shí)，應(yīng)用 FIFO 算法，移除最先進(jìn)入主存的頁(yè)面 1，然后載入頁(yè)面 4。

之后的頁(yè)面，都以 FIFO 算法為基礎(chǔ)，進(jìn)行類似處理。表 1 中的紅色，就表示發(fā)生缺頁(yè)中斷時(shí)，載入主存的頁(yè)號(hào)。

表 1 使用 FIFO 算法發(fā)生的缺頁(yè)過(guò)程，進(jìn)程擁有 3 個(gè)主存頁(yè)

可以發(fā)現(xiàn)，訪問(wèn) 12 個(gè)頁(yè)面時(shí)，共發(fā)生 9 次缺頁(yè)中斷，缺頁(yè)率為 9/12=0.75。

如果進(jìn)程擁有 4 個(gè)主存頁(yè)，那么使用 FIFO 算法發(fā)生的缺頁(yè)過(guò)程，分析方法與之前類似：

表 2 使用 FIFO 算法發(fā)生的缺頁(yè)過(guò)程，進(jìn)程擁有 4 個(gè)主存頁(yè)

可以發(fā)現(xiàn)，訪問(wèn) 12 個(gè)頁(yè)面時(shí)，共發(fā)生 10 次缺頁(yè)中斷，缺頁(yè)率為 10/12=0.833。

也就是說(shuō)，在這個(gè)示例中，給予進(jìn)程的主存頁(yè)面數(shù)越多，缺頁(yè)中斷次數(shù)反而會(huì)增加的異?，F(xiàn)象。

Belady 現(xiàn)象的原因是 FIFO 算法的置換特征與進(jìn)程訪問(wèn)內(nèi)存的動(dòng)態(tài)特征是矛盾的，即被置換的頁(yè)面并不是進(jìn)程不會(huì)訪問(wèn)的，因而 FIFO 并不是一個(gè)好的置換算法。

4 局部性原理

存儲(chǔ)管理策略的基礎(chǔ)是局部性原理，即進(jìn)程往往會(huì)不均勻地高度局部化地訪問(wèn)內(nèi)存。局部性分為時(shí)間局部性和空間局部性。

時(shí)間局部性是指最近訪問(wèn)存儲(chǔ)位置，很可能不久的將來(lái)還要訪問(wèn) ；

空間局部性是指存儲(chǔ)訪問(wèn)有成組的傾向；當(dāng)訪問(wèn)了某個(gè)位置后，很可能也要訪問(wèn)其附近的位置。

根據(jù)局部性原理的特征性， Denning 闡述了程序性能的工作集理論。工作集是進(jìn)程頻繁訪問(wèn)的頁(yè)面的集合。工作集理論指出，為使進(jìn)程有效地運(yùn)行，它的頁(yè)面工作集應(yīng)駐留內(nèi)存中。否則，由于進(jìn)程頻繁地從外存請(qǐng)求頁(yè)面，而出現(xiàn)稱為 “ 顛簸 ” ( 抖動(dòng) ) 的過(guò)度的頁(yè)面調(diào)度活動(dòng)。此時(shí)，處理頁(yè)面調(diào)度的時(shí)間超過(guò)了程序的執(zhí)行時(shí)間。顯然，此時(shí) CPU 的有效利用率會(huì)急速下降。

通常用兩種等價(jià)的方法確定進(jìn)程的工作集，一種是將工作集確定為在定長(zhǎng)的頁(yè)面訪問(wèn)序列 ( 工作集窗口 ) 中的頁(yè)面集合；另一種是將工作集確定為在定長(zhǎng)時(shí)間間隔中涉及頁(yè)面的集合。

工作集的大小依賴于工作集窗口的大小，在進(jìn)程執(zhí)行時(shí)，工作集會(huì)發(fā)生變化。有時(shí)，當(dāng)進(jìn)程進(jìn)入另一個(gè)完全不同的執(zhí)行階段時(shí)，工作集會(huì)出現(xiàn)顯著的變化。不過(guò)在一個(gè)進(jìn)程的執(zhí)行過(guò)程中，工作集的大小處于穩(wěn)定狀態(tài)的時(shí)間基本上占絕大多數(shù)。

另一種控制抖動(dòng)的技術(shù)是控制缺頁(yè)率。操作系統(tǒng)規(guī)定缺頁(yè)率的上下限，當(dāng)一個(gè)進(jìn)程的缺頁(yè)率高于上限時(shí)，表明該進(jìn)程需要更大的內(nèi)存空間，則分配較多的內(nèi)存頁(yè)面給它，當(dāng)進(jìn)程的缺頁(yè)率低于下限時(shí)，表明該進(jìn)程占用的內(nèi)存空間過(guò)大，可以適當(dāng)?shù)厥栈厝舾蓛?nèi)存頁(yè)面。