第四章存儲器管理4.1存儲器的層次結構4.2程序的裝入和鏈接4.3連續分配方式4.4基本分頁存儲管理方式4.5基本分段存儲管理方式4.6虛擬存儲器的基本概念4.7請求分頁存儲管理方式4.8頁面置換算法4.9請求分段存儲管理方式

存儲器是計算機系統的重要組成部分，操作系統中的存儲管理是指對內存的管理，它是操作系統的重要功能之一。充分利用內存，為多道程序并發執行提供存儲基礎盡可能方便用戶使用自動裝入用戶程序用戶程序中不必考慮硬件細節系統能夠解決程序空間比實際內存空間大的問題存儲器管理的目的：程序的長度在執行時可以動態伸縮內存存取速度快存儲保護與安全共享與通信及時了解有關資源的使用狀況實現的性能和代價要合理內存空間的管理、分配與回收內存共享--代碼共享，數據共享通過代碼共享節省內存空間，提高內存利用率通過數據共享實現進程通信存儲保護防止地址越界防止操作越權擴充內存容量

用戶在編制程序時，不應該受內存容量限制，所以要采用一定技術來“擴充”內存的容量，使用戶得到比實際內存容量大的多的內存空間，通過虛擬存儲技術實現地址映射（重定位）存儲器管理的功能：存儲系統設計三個問題：容量、速度和成本容量：需求無止境速度：能匹配處理器的速度成本問題：成本和其它部件相比應在合適范圍之內解決方案：采用層次化的存儲體系結構當沿著層次下降時每比特的價格將下降，容量將增大速度將變慢，處理器的訪問頻率也將下降4.1存儲器的層次結構4.1.1多級存儲器結構容量愈來愈大訪問數據的速度愈來愈慢價格愈來愈便宜寄存器高速緩存主存磁盤緩存磁盤可移動存儲介質CPU寄存器主存輔存提高存儲系統效能關鍵點：程序存儲訪問局部性原理程序執行時，有很多的循環和子程序調用，一旦進入這樣的程序段，就會重復存取相同的指令集合對數據存取也有局部性，在較短的時間內，穩定地保持在一個存儲器的局部區域,處理器主要和存儲器的局部打交道,在經過一段時間以后，使用的代碼和數據集合會改變設計多級存儲的體系結構原則：訪問級別較低存儲器比率小于級別較高存儲器比率例：假設兩級存儲器： 第I級包含1KB，存取時間為0.1μs 第II級包含1MB，存取時間為1μs存取I級中的內容，直接存取存取II級，首先被轉移到I級，然后再存取假設確定內容所在位置時間可以忽略若在I級存儲器中發現存取對象的概率是95%，則平均訪問時間為：結果非常接近I級存儲的存取時間存儲保護設施對主存中的信息加以嚴格的保護，使操作系統及其它程序不被破壞，是其正確運行的基本條件之一.

問題：多個程序同時在同一臺機器上運行怎樣才能互不侵犯？為了保證軟件程序只影響程序的內部硬件可提供如下功能：界地址寄存器（界限寄存器）存儲鍵1.界地址寄存器（界限寄存器）在CPU中設置一對界限寄存器來存放該用戶作業在主存中的下限和上限地址每當CPU要訪問主存，硬件自動將被訪問的主存地址與界限寄存器的內容進行比較，以判斷是否越界如果未越界，則按此地址訪問主存，否則將產生程序中斷——越界中斷（存儲保護中斷）10005000OSUser1

Jump6000User2將6000與上限地址5000比較，越界則越界中斷10006000下界上界2.存儲鍵每個存儲塊有一個由二進位組成的存儲保護鍵一用戶作業被允許進入主存，OS分給它一個唯一的存儲鍵號并將分配給該作業各存儲塊存儲鍵也置成同樣鍵號當OS挑選該作業運行時，OS將它的存儲鍵號放入程序狀態字PSW存儲鍵（“鑰匙”）域中每當CPU訪問主存時，都將該主存塊的存儲鍵與PSW中的“鑰匙”進行比較A塊B塊C塊001010100101000存儲鍵取保護位0－不保護1－保護…………001007鑰

Key11只要鍵匹配，存取均可鍵不匹配，則不可存是否可取要看保護位舉例：存A，取A，均可以(鍵Key匹配)存B，取B，均不可以(鍵不匹配，且取保護)存C，不可以(鍵不匹配)

取C，可以，因取保護位為0，即不保護取程序狀態字4.1程序的裝入和鏈接

在多道程序環境下，要使程序運行，必須創建進程，而創建進程第一件事就是將程序和數據裝入內存。一個用戶源程序要變為在內存中可執行的程序，通常要進行以下處理：（1）編譯：由編譯程序將用戶源程序編譯成若干個目標模塊；（2）鏈接：由鏈接程序將目標模塊和相應的庫函數鏈接成裝入模塊；（3）裝入：由裝入程序將裝入模塊裝入內存。庫目標程序塊1目標程序塊2第一步鏈接程序裝入模塊第二步裝入程序第三步用戶源程序編譯程序……內存1.絕對裝入方式如果在編譯時，事先知用戶程序在內存的駐留位置，則編譯程序在編譯時就產生絕對地址的目標代碼。裝入程序就直接把裝入模塊中的程序和數據裝入到指定的位置，（不需進行地址轉換）。程序中所使用的絕對地址，既可在編譯或匯編時給出，也可由程序員直接賦予。但在由程序員直接給出絕對地址時，不僅要求程序員熟悉內存的使用情況，而且一旦程序或數據被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號地址，然后在編譯或匯編時，再將這些符號地址轉換為絕對地址。

4.2.1程序的裝入1.名空間、地址空間和存儲空間在我們用匯編語言或高級語言編寫程序時，總是通過符號名來訪問某一單元。我們把程序中由符號名組成的空間稱為名空間。源程序經過匯編或編譯形成的程序，通常是以0為基址進行順序編址，這樣的地址表示形式稱為相對地址,也叫做邏輯地址或虛地址，把該程序邏輯地址組成的集合叫做程序的邏輯地址空間(簡稱地址空間)。存儲器中每個具體存儲單元都有不同的編號，每個編號就是一個物理地址，整個程序在內存中存儲后所占用的物理地址的集合形成程序的物理地址空間(簡稱存儲空間)。2.重定位（地址映射）裝入方式名空間、地址空間和存儲空間的關系GotoL1L1：…源程序編譯Goto2…目標代碼0123名空間地址空間裝入Gotoa＋2…內存(運行程序)aa＋1存儲空間…a＋22.地址映射邏輯地址是一個“虛”的概念，處理機不能直接訪問邏輯地址，而物理地址則是“實”的。因而，操作系統必須提供這樣的功能，把程序執行時要訪問的地址空間中的邏輯地址變換成內存空間中對應的物理地址。這種把虛地址變換成實地址的過程稱作地址映射。若用A表示地址空間，用M表示內存空間，則地址映射可表示成：f：Ａ→Ｍ(1)靜態映射：當用戶程序被裝入內存時，一次性實現邏輯地址到物理地址的轉換，以后不再轉換。由重定位

裝入程序完成，它把分配給目標程序的內存區的起始地址B作為基地址，在把該程序裝入指定內存區的同時，將程序中的所有邏輯地址翻譯成相對于基地址B的物理地址，即ｆ（ａ）＝Ｂ＋ａ優點:容易實現，無需硬件支持，地址重定位由專門設計的程序來完成。在早期的操作系統中大多數都采用這種方法。缺點:程序經地址重定位后就不能移動了，因而不能重新分配內存，不利于內存的有效利用。

0：B=10000

100：

LOAD1，2500

10100：

LOAD1，12500

2500：

365

12500：

365

2600：12600：

邏輯地址空間物理地址空間例如：LOAD1，2500這條指令是把相對地址為2500的存儲單元的內容365裝入1號累加器。而這時內容為365的存儲單元的實際物理地址為12500（起始地址10000+相對地址2500），所以LOAD1，2500這條指令中的直接地址碼要作相應的修改，即改為LOAD1，12500。

(2)動態映射：指在程序執行過程中進行地址重定位，即在每次訪問內存單元前才進行地址變換。動態重定位可使程序不加任何修改就裝入內存，但是它需要硬件—重定位寄存器的支持。對每一個有效地址都要加上重定位寄存器中的內容，以形成絕對地址。優點:程序在內存中的搬移不會對程序的正確執行造成影響，使內存得以被充分利用。缺點:需要附加的硬件支持，實現存儲管理的軟件算法比較復雜。03456......LOAD1200......0100200300.........LOAD12003456邏輯地址空間110012001300物理地址空間200有效地址+1000BR10004.2.2程序的鏈接一種事先鏈接方式，即在程序運行之前，先將各目標模塊及它們所需的庫函數，鏈接成一個完整的裝入模塊(執行文件)，以后不再拆開。實現靜態鏈接應解決:1）相對地址的修改2）變換外部調用符號存在問題：1）不便于對目標模塊的修改和更新。2）無法實現對目標模塊的共享。模塊ACALLB;RETURN;模塊BCALLC;RETURN;模塊CRETURN;0L-10M-10N-1目標模塊0L-1LL+M-1L+ML+M+N-1模塊CReturn；模塊BJSR“L+M”Return；模塊AJSR“L”Return；裝入模塊1.靜態鏈接方式指將一組目標模塊在裝入內存時，邊裝入邊鏈接的方式。具有便于修改和更新、便于實現對目標模塊的共享。存在問題：

由于程序運行所有可能用的目標模塊在裝入時均全部鏈接在一起，所以將會把一些不會運行的目標模塊也鏈接進去。如程序中的錯誤處理模塊。2.裝入時動態鏈接方式在程序運行中需要某些目標模塊時，才對它們進行鏈接的方式。具有高效且節省內存空間的優點。3.運行時動態鏈接方式單一用戶(連續)分配是一種簡單的存儲分配方案，主要用于單用戶單任務操作系統。它的實現方案如下：(1)內存分配：整個內存劃分為系統區和用戶區。系統區是操作系統專用區，不允許用戶程序直接訪問，一道用戶程序獨占用戶區.

4.3.1單一用戶存儲管理方案注意:我們所涉及的內存分配與回收一般都指用戶區的分配與回收。進程1OS系統區用戶區4.3連續分配方式地址錯界限寄存器重定位寄存器(基址)CPU<內存邏輯地址YN物理地址+(3)內存保護：通過基址寄存器保證用戶程序不會從系統區開始；另外系統需要一個界限寄存器，里邊存儲程序邏輯地址范圍，若需要進行映射的邏輯地址超過了界限寄存器中的值，則產生一個越界中斷信號。(2)地址映射：物理地址=用戶區基地址+邏輯地址。單一連續分配方案的優點是方法簡單，易于實現；缺點是它僅適用于單道程序，因而不能使處理機和內存得到充分利用。例：一個容量為256KB的內存，操作系統占用32KB，剩下224KB全部分配給用戶作業，如果一個作業僅需64KB，那么就有160KB的存儲空間被浪費。操作系統作業0KB32KB96KB256KB-1分配給用戶的空間4.3.2固定分區分配作業裝入之前，內存就被劃分成若干個分區。劃分工作可以由系統管理員完成或由操作系統實現。一旦劃分完成，在系統運行期間不再重新劃分，即分區的個數不可變，分區的大小不可變，且每個分區裝一個且只能裝一個作業。可將內存的用戶區域劃分成大小相等或不等的分區。分區大小相等：只適合于多個相同程序的并發執行（處理多個類型相同的對象）。分區大小不等：多個小分區、適量的中等分區、少量的大分區。根據程序的大小，分配當前空閑的、適當大小的分區。系統有一張分區說明表，每個表目說明一個分區的大小、起始地址和是否已分配的使用標志。

固定分區示例例：在某系統中，采用固定分區分配管理方式，內存分區（單位字節）情況如圖所示，現有大小為1K、9K、33K、121K的多個作業要求進入內存，試畫出它們進入內存后的空間分配情況，并說明主存浪費多大？10k20k28k60k180k511k234內存分區圖OS區號大小起址狀態18k20k未分配232k28k未分配3120k60k未分配4331k180k未分配分區說明表區號大小起址狀態18k20k已分配232k28k已分配3120k60k已分配4331k180k已分配（2）分區說明表(3)主存浪費空間=(8-1)+(32-9)+(120-33)+(331-121)=7+23+87+210=327(k)解：根據分區說明表，將4個分區依次分配給4個作業，同時修改分區說明表，其內存分配和分區說明表如下所示：0k20k28k60k180k511k23(1)內存分配圖1K9K33K121K4.3.3動態（可變）分區分配作業裝入內存時，從可用的內存中劃出一塊連續的區域分配給它，且分區大小正好等于該作業的大小。可變式分區中分區的大小和分區的個數都是可變的，而且是根據作業的大小和多少動態地劃分。在分配時，首先找到一個足夠大的空閑分區，即這個空閑區的大小比作業要求的要大，系統則將這個空閑分區分成兩部分：一部分成為已分配的分區，剩余的部分仍作為空閑區。在回收撤除作業所占領的分區時，要檢查回收的分區是否與前后空閑的分區相領接，若是，則加以合并，使之成為一個連續的大空間。常用的數據結構有內存分配表（由已分配區表和空閑區表組成）和空閑分區鏈兩種。0K15K38K48K68K80K110K120K空閑區表已分配區表始址長度標志15K23K未分配48K20K未分配80K30K未分配空空始址長度標志0K15KJ138K10KJ268K12KJ3110K10KJ4空空J1J2J3J40K15K38K48K68K80K110K120K空閑區表已分配區表始址長度標志15K23K未分配48K20K未分配98K12K未分配空空始址長度標志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98KJ1J2J3J4J5J6可變分區示例2.分區分配算法為了將一個作業裝入內存，應按照一定的分配算法從空閑分區表（鏈）中選出一個滿足作業需求的分區分配給作業，如果這個空閑分區的容量比作業申請的空間要大，則將該分區一分為二，一部分分配給作業，剩下的部分仍然留在空閑分區表（鏈）中，同時修改空閑分區表（鏈）中相應的信息。目前常用分配算法有：首次適應算法循環首次適應算法最佳適應算法最壞適應算法快速適應法首次適應算法（最先適應算法）算法

空閑分區（鏈）按地址遞增的次序排列。在進行內存分配時,從空閑分區表/鏈首開始順序查找,直到找到第一個滿足其大小要求的空閑分區為止。然后再按照作業大小，從該分區中劃出一塊內存空間分配給請求者，余下的空閑分區仍留在空閑分區表（鏈）中。區號大小起址132k20k28k52k3120k60k4331k180k空閑分區表解：按首次適應算法，

申請作業100k，分配3號分區，剩下分區為20k，起始地址160K；

申請作業30k，分配1號分區，剩下分區為2k，起始地址50K；

申請作業7k，分配2號分區，剩下分區為1k，起始地址59K；其內存分配圖及分配后空閑分區表如下：例：系統中的空閑分區表如下，現有三個作業分配申請內存空間100K、30K及7K。給出按首次適應算法的內存分配情況及分配后空閑分區表。區號大小起址12k50k21k59k320k160k4331k180k(2)該算法分配后的空閑分區表0k20k50k52k59k60k160k180k511k(1)內存分配圖首次適應算法的特點

優先利用內存低地址部分的空閑分區,從而保留了高地址部分的大空閑區。但由于低地址部分不斷被劃分,致使低地址端留下許多難以利用的很小的空閑分區(碎片或零頭),而每次查找又都是從低地址部分開始,這無疑增加了查找可用空閑分區的開銷。循環首次適應算法算法要求

又稱為下次適應算法，由首次適應算法演變而來。在為作業分配內存空間時,不再每次從空閑分區表/鏈首開始查找,而是從上次找到的空閑分區的下一個空閑分區開始查找,直到找到第一個能滿足其大小要求的空閑分區為止。然后，再按照作業大小，從該分區中劃出一塊內存空間分配給請求者，余下的空閑分區仍留在空閑分區表/鏈中。區號大小起址132k20k28k52k3120k60k4331k180k空閑分區表解：按循環首次適應算法，申請作業100k，分配3號分區，剩下分區為20k,起始地址160K；

申請作業30k，分配4號分區，剩下分區為301k，起始地址210K；申請作業7k，分配1號分區，剩下分區為25k，起始地址27K；其內存分配圖及分配后空閑分區表如下:例：系統中的空閑分區表如下，現有三個作業分配申請內存空間100K、30K及7K。給出按循環首次適應算法的內存分配情況及分配后空閑分區表。區號大小起址12k27k21k52k320k160k4131k210k(2)該算法分配后的空閑分區表算法特點

使存儲空間的利用更加均衡，不致使小的空閑區集中在存儲區的一端，但這會導致缺乏大的空閑分區。

0k20k27k52k60k160k180k210k511k(1)內存分配圖最佳適應算法算法要求：

總是把滿足要求的、又是最小的空閑分區分給作業。為了加速尋找，空閑分區表/鏈按容量大小遞增的次序排列。在進行內存分配時，從空閑分區表/鏈的首開始順序查找，直到找到第一個滿足其大小要求的空閑分區為止。按這種方式為作業分配內存，就能把既滿足作業要求又與作業大小最接近的空閑分區分配給作業。如果該空閑分區大于作業的大小，則與首次適應算法相同，將剩余空閑分區仍留在空閑分區表/鏈中。例：系統中的空閑分區表如下，現有三個作業分配申請內存空間100K、30K及7K。給出按最佳適應算法的內存分配情況及分配后空閑分區表。區號大小起址18k52k232k20k3120k60k4331k180k分配前的空閑分區表內存分區

0k20k52k60k180k511k2134解：按最佳適應算法，分配前的空閑分區表如上表。

申請作業100k，分配3號分區，剩下分區為20k,起始地址160K；

申請作業30k，分配2號分區，剩下分區為2k，起始地址50K；

申請作業7k，分配1號分區，剩下分區為1k，起始地址59K；其內存分配圖及分配后空閑分區表如下：區號大小起址18k52k320k160k232k20k4331k180k作業100K分配后的空閑分區表區號大小起址22k50k18k52k320k160k4331k180k作業30K分配后的空閑分區表區號大小起址11k59k22k50k320k160k4331k180k作業7K分配后的空閑分區表(2)該算法分配后的空閑分區表0k20k52k60k180k511k(1)內存分配圖50K59K160K180K區號大小起址11k59k22k50k320k160k4331k180k算法特點

若存在與作業大小一致的空閑分區,則它必然被選中，若不存在與作業大小一致的空閑分區，則只劃分比作業稍大的空閑分區，,從而保留了大的空閑分區,但空閑區一般不可能正好和它申請的內存空間大小一樣,因而將其分割成兩部分時,往往使剩下的空閑區非常小,從而在存儲器中留下許多難以利用的小空閑區（碎片或零頭）。最壞適應算法算法要求

總是挑選一個最大的空閑區分割給作業使用，空閑分區表/鏈按容量大小遞減的次序排列。在進行內存分配時，從空閑分區表/鏈的首開始順序查找，直到找到第一個比之大的空閑分區為止。剩下的空閑仍留在空閑分區表/鏈中。區號大小起址1331k180k2120k60k332k20k48k52k空閑分區表例：系統中的空閑分區表如下，現有三個作業分配申請內存空間100K、30K及7K。給出按最壞適應算法的內存分配情況及分配后空閑分區表。區號大小起址1231k280k2120k60k332k20k48k52k作業100K分配后的空閑分區表區號大小起址1201k310k2120k60k332k20k48k52k作業30K分配后的空閑分區表區號大小起址1194k317k2120k60k332k20k48k52k作業7K分配后的空閑分區表解：按最壞適應算法，分配前的空閑分區表如上表。

申請作業100k，分配1號分區，剩下分區為231k,起始地址280K；

申請作業30k，分配1號分區，剩下分區為201k，起始地址310K；

申請作業7k，分配1號分區，剩下分區為194k，起始地址317K；其內存分配圖及分配后空閑分區表如下：區號大小起址1194k317k2120k60k332k20k48k52k(2)該算法分配后的空閑分區表30k20k52k60k180k511k(1)內存分配圖20K52K60K280K310K317K算法特點總是挑選滿足作業要求的最大的分區分配給作業。這樣使分給作業后剩下的空閑分區也較大，可裝下其它作業。但由于最大的空閑分區總是因首先分配而劃分，當有大作業到來時，其存儲空間的申請往往會得不到滿足。快速適應算法（分類搜索法）算法要求

將空閑分區根據其容量大小進行分類，每一類相同容量的所有空閑分區，單獨設立一個空閑分區鏈表，同時在內存中設立一張管理索引表，每一表項對應了一種空閑分區類型，并記錄頭指針。進程根據自己的長度，尋找能容納它的最小空閑區鏈表，取下第一塊進行分配即可。3.分區分配操作_分配內存和回收內存（1）分配內存系統利用某種分配算法，從空閑分區表/鏈中找到所需大小的分區。分區的切割：設請求的分區大小為u.size，空閑分區的大小為m.size,若m.size-u.sizesize(size是事先規定的不再切割的剩余分區的大小)，說明多余部分大小，可不再切割，將整個分區分配給請求者；否則，從該分區中按請求的大小劃分出一塊內存空間分配出去，余下的部分仍留在空閑分區表/鏈中，然后，將分配區的首址返回給調用者。

分配流程圖如下：從頭開始查表從該分區中劃出u.size大小的分區檢索完否？返回m.size>u.sizem.size-u.sizesize將該分區分配給請求者，修改有關數據結構返回將該分區從分區表/鏈中移出繼續檢索下一個表項YYYNNN內存分配流程圖（2）回收內存當作業執行結束時，應回收已使用完畢的分區。系統根據回收分區的大小及首地址，在空閑分區表中檢查是否有鄰接的空閑分區，如有，則合成為一個大的空閑分區，然后修改有關的分區狀態信息。回收分區與已有空閑分區的相鄰情況有以下四種：1）回收分區上鄰接一個空閑分區,合并后首地址為空閑分區的首地址,大小為二者之和。2）回收分區下鄰接一個空閑分區,合并后首地址為回收分區的首地址,大小為二者之和。3）回收分區上下鄰接空閑分區,合并后首地址為上空閑分區的首地址,大小為三者之和。4）回收分區不鄰接空閑分區，這時在空閑分區表中新建一表項，并填寫分區大小等信息。4.3.6可重定位分區分配1.動態重定位的引入

在分區存儲管理方式中，必須把作業裝入到一片連續的內存空間。如果系統中有若干個小的分區，其總容量大于要裝入的作業，但由于它們不相鄰接，也將致使作業不能裝入內存。例：如圖所示系統中有四個小空閑分區，不相鄰，但總容量為90KB，如果現有一作業要求分配40KB的內存空間，由于系統中所有空閑分區的容量均小于40KB，故此作業無法裝入內存。這種內存中無法被利用的存儲空間稱為“零頭”或“碎片”。根據碎片出現的情況分為以下兩種：操作系統作業A20KB作業B30KB作業C15KB作業D25KB系統中的碎片os用戶程序p4p1p20k20k56k65k125k135k內部碎片內部碎片內部碎片25KB作業D15KB作業C30KB作業B20KB作業A操作系統外部碎片外部碎片外部碎片外部碎片內部碎片外部碎片內部碎片：指分配給作業的存儲空間中未被利用的部分。如固定分區中存在的碎片。外部碎片：指系統中無法利用的小的空閑分區。如動態分區中存在的碎片。碎片問題的解決方法拼接或緊湊或緊縮技術將內存中所有作業移到內存一端（作業在內存中的位置發生了變化，這就必須對其地址加以修改或變換即稱為重定位），使本來分散的多個小空閑分區連成一個大的空閑區。如圖所示。這種通過移動作業從把多個分散的小分區拼接成一個大分區的方法稱為拼接或緊湊或緊縮。拼接時機：分區回收時；當找不到足夠大的空閑分區且總空閑分區容量可以滿足作業要求時。操作系統作業A作業B作業C作業D20KB30KB90KB15KB25KB2.動態重定位的實現動態重定位可使程序不加任何修改就裝入內存，但是它需要硬件—重定位寄存器的支持。對每一個有效地址都要加上重定位寄存器中的內容，以形成絕對地址。03456......LOAD1200......0100200300.........LOAD12003456邏輯地址空間110012001300物理地址空間200有效地址+1000BR1000動態重定位分區分配算法流程圖有大于x的空閑分區嗎？返回分區號空閑分區總和大于x嗎？拼接并修改相應數據結構返回修改有關數據結構按動態分區分配方式進行分配YYNN無法分配，返回請求分配一個大小為x的分區3.動態重定位分區分配算法

在動態分區分配算法中增加拼接功能，在找不到足夠大的空閑分區來滿足作業要求，而系統中總空閑分區容量可以滿足作業要求時，進行拼接。可重定位分區分配方式主要特點

可以充分利用存儲區中的“零頭/碎片”，提高主存的利用率。但若“零頭/碎片”過多，則拼接頻率過高會使系統開銷加大。4.3.7覆蓋技術與交換技術1.覆蓋技術引入：其目標是在較小的可用內存中運行較大的程序。常用于多道程序系統，與分區存儲管理配合使用。原理：一個程序的幾個代碼段或數據段，按照時間先后來占用公共的內存空間。將程序的必要部分（常用功能）的代碼和數據常駐內存；可選部分（不常用功能）在其他程序模塊中實現，平時存放在外存中（覆蓋文件），在需要用到時才裝入到內存；不存在調用關系的模塊不必同時裝入到內存，從而可以相互覆蓋。(即不同時用的模塊可共用一個分區)缺點：編程時必須劃分程序模塊和確定程序模塊之間的覆蓋關系，增加編程復雜度。從外存裝入覆蓋文件，以時間延長來換取空間節省。A20KD20KE40KC30KB50KF30K作業X的調用結構作業X的常駐區A（20K）覆蓋區0（50K）覆蓋區1（40K）BCDEF注：另一種覆蓋方法：(100K)A(20K)占一個分區：20K；B(50K)、D(20K)和E(40K)共用一個分區：50K；F(30K)和C(30K)共用一個分區：30K；Total:190KTotal:110K2.交換技術引入：多個程序并發執行，可以將暫時不能執行的程序送到外存中，從而獲得空閑內存空間來裝入新程序，或讀入保存在外存中而目前到達就緒狀態的進程。交換單位為整個進程的地址空間。常用于多道程序系統或小型分時系統中，與分區存儲管理配合使用。又稱作"對換"或"滾進/滾出(roll-in/roll-out)"；程序暫時不能執行的可能原因：處于阻塞狀態，低優先級（確保高優先級程序執行）；原理：暫停執行內存中的進程，將整個進程的地址空間保存到外存的交換區中（換出swapout），而將外存中由阻塞變為就緒的進程的地址空間讀入到內存中，并將該進程送到就緒隊列（換入swapin）。返回優點：增加并發運行的程序數目，并且給用戶提供適當的響應時間；編寫程序時不影響程序結構缺點：對換入和換出的控制增加處理機開銷；程序整個地址空間都進行傳送，沒有考慮執行過程中地址訪問的統計特性。考慮的問題：程序換入時的重定位；減少交換中傳送的信息量，特別是對大程序；對外存交換區空間的管理：如動態分區方法；4.4基本分頁存儲管理方式我們把邏輯地址空間劃分為一些相等的片，這些片稱為頁或頁面。物理地址空間也被劃分為同樣大小的片，稱為塊。這樣用戶程序進入內存時，就可以一頁對應存入到一個塊中。對整個程序來說，只有可能在最后一塊存在碎片（稱為頁內碎片），而且碎片大小不會超過一塊，所以內存利用率可以大大提高。用戶程序的邏輯地址:4.4.1頁面與頁表頁號頁內地址頁面(或塊)的大小由系統硬件地址結構規定，通常是2的冪，例如512B，1KB、2KB等。這樣的規定可以使地址映射容易實現。頁面不能過大，也不能過小。過小會造成頁面過多，增加了系統開銷；過大又會造成頁內碎片太大，內存利用率不高。早期的頁面大小一般都在512B～4KB，隨著計算機性能的提高，現在一般在2KB～8KB，甚至有的系統支持多種頁面大小。例：對于一個32位的地址結構，如果頁面大小為4KB，則頁內地址由0～11這12位表示，剩余12～31在表示頁號（頁內地址）例：在頁面大小為4KB的系統中，若邏輯地址為28024，則可求得頁號為6，頁內偏移量為3448。而計算機內部如何得到頁號和頁內地址呢？28024的二進制用32位表示為：(00000000000000000110110101111000)2，因為頁面大小為4KB，則取低12位為頁內地址，剩余高位是頁號。把這兩部分換算為十進制，我們可以驗算出通過上述公式計算的結果的正確性。000000000000000001101101011110002802463448系統為每個進程建立一個頁表，記錄了進程每個頁號及其對應的存儲塊號。整個系統一張存儲分塊表，記錄每個存儲塊及其狀態（已分配或空閑）。當有一個進程進入系統時，為頁表分配一個存儲區，然后搜索存儲分塊表，查看有哪些存儲塊是空閑的，如有空閑的存儲塊，則將存儲塊號填入頁表。當該進程所需的塊數都分配完后，系統便可按照頁表的內容對該進程進行處理。當某個進程因為結束或者其它一些原因退出系統，則歸還原來所占用的物理塊。首先修改存儲分塊表，將歸還的物理塊塊號在表中的狀態欄改為空閑標志，然后釋放該進程頁表所占用的空間。管理上的考慮頁表、存儲分塊表及其關系頁號012塊號103920號頁表1號頁表頁號01塊號953…塊號0…狀態0…31……91101……存儲分塊表由于頁和塊大小是一致的，每頁的頁內地址與物理塊的塊內單元地址也完全一致，所以在邏輯地址到物理地址的映射中，主要從一個頁找到對應的內存塊，而這種頁與塊的對應關系是頁表記錄的。每個進程調度時，從該進程PCB中取得頁表始址和頁表長度（頁表長度指頁表的項數），裝入到系統中設置的頁表寄存器內。4.4.2地址變換機構1．動態地址映射機構分頁式地址變換過程例：頁大小為1024B，給定邏輯地址3795，即得出頁號為3，頁內地址為723。頁表始址頁表長度＋頁表寄存器＞頁號3頁內地址723越界中斷①①②②11×1024＋723頁號塊號01615425311……RR＋iR＋3i……365……物理地址11987④11987內存內存中的頁表邏輯地址3795③③①頁號3與頁表寄存器中的頁表長度比較判斷是否越界，如果越界，則轉錯誤中斷處理，否則轉②；②頁表中該項在內存中的對應地址=頁表始地址R+頁號3×頁表項長度i，訪問該地址R+3i，得到物理塊號11；③11(頁號)×1024(頁大小)+723(頁內地址)=11987(物理地址)；④訪問內存11987單元，得到需要的數據365。頁表存放在內存中，每條指令都必須兩次訪問內存儲器，增加了指令執行的機器時間，影響了計算機的速度。一次是訪問頁表，由頁號找到對應的物理塊號；另一次是在物理地址中實際存取所要的數據或指令。為了加快查表速度，在地址映射機構中加入一組高速寄存器(8個或16個)，構成了一個容量較小的存儲器，稱之為聯想存儲器（也稱快表）。在聯想存儲器中，存放正在運行進程的當前最常用的頁號和相應塊號，這個聯想存儲器具有并行查詢能力，使地址轉換時間大大下降。2.快表的引入(聯想存儲器)引入快表的地址映射頁表始址頁表長度＋頁表寄存器＞頁號頁內地址越界中斷①①⑥③b…365……物理地址④內存邏輯地址頁號塊號b…內存⑥頁號塊號b…⑦②⑦快表⑤由于對程序和數據的訪問往往帶有局限性，所以快表的命中率可以達到90%左右。例:假設檢索聯想存儲器的時間為20ns，訪問內存的時間為100ns，訪問聯想存儲器的的命中率為85%，則CPU存取一個數據的平均時間為T=0.85*120+0.15*200=132ns，如果不引入聯想存儲器，訪問2次主存，將達200ns。問題

若邏輯地址空間很大，則劃分的頁就很多，頁表就很大，其占用的存儲空間（要求連續）就大，實現較難。解決問題的方法

1、只將當前需用的部分頁表項調入內存，其余的需用時再調入。

2、多級頁表二級頁表

(1)將頁表再進行分頁，并離散地將各個頁表頁面存放在不同的物理塊中，同時也再建立一張頁表（外層頁表）用以記錄頁表頁面對應的物理塊號。

4.4.3多級頁表兩級頁表結構174210781011…6411151141468……012n012102301210230121023第0頁頁表第1頁頁表第n頁頁表0121141151468內存空間外部頁表(2)邏輯地址：(3)地址轉換p1p2d頁表頁面號頁號頁內偏移地址dp2p1頁表頁面號頁號頁內地址外部頁表寄存器…

…

外部頁表++頁表bd物理地址多級頁表

將外層頁表再進行分頁，也將各外層頁表頁面離散地存放在不同的物理塊中，再利用第2級的外層頁表來記錄它們之間的對應的關系。邏輯地址：p1p2d外層頁表頁面號頁表頁面號頁號頁內偏移地址p3便于多道程序設計，提高了內存的利用率，而不必像動態分區分配那樣執行緊湊操作。分頁存儲管理的優缺點優點：采用動態地址映射會增加計算機成本和降低處理機的速度。各種表格要占用一定容量的內存空間，而且還要花費一部分處理機時間來建立和管理這些表格。雖然消除了大量碎片，但每個作業的最后一頁一般都有不能充分利用的空白區存儲擴充問題仍未得到解決。當沒有足夠空間能裝下整個作業地址空間時，該作業還是無法運行。缺點：1．把作業地址空間中使用的邏輯地址變成內存中物理地址稱為（）。A.加載B.重定位C.物理化D.邏輯化3．在內存分配的“最佳適應法”中，空閑塊是按（）。A.始地址從小到大排序B.始地址從大到小排序C.塊的大小從小到大排序D.塊的大小從大到小排序4．分區管理和分頁管理的主要區別是（）。A.分區管理中的塊比分頁管理中的頁要小B.分頁管理有地址映射而分區管理沒有C.分頁管理有存儲保護而分區管理沒有D.分區管理要求一道程序存放在連續的空間內而分頁管理沒有這種要求。2．在可變分區存儲管理中的緊湊技術可以()。A.集中空閑區B.增加主存容量C.縮短訪問時間D.加速地址轉換BACD5．設內存的分配情況如下圖所示。若要申請一塊40K字節的內存空間，若采用最佳適應算法，則所得到的分區首址為（）。A.100KB.190KC.330KD.410K占用

占用

占用

占用

┇000K100K180K190K280K330K390K410K512K-1C一個用戶作業的程序按其邏輯結構可劃分為若干段，例如主程序段、子程序段、數據段、堆棧段等。這些段中的每一段在邏輯上都是完整的，因此每一段都是一組邏輯信息，有自己的名字，且都有一段連續的地址空間。在分段式存儲管理中，段名用段號代替，段地址從0開始編址，因為各段的邏輯信息內容不同，所以段長度不同。這樣用段號和段內地址構成用戶程序的邏輯地址。當一個用戶程序裝入內存時，系統為每個段分配一個連續的內存區域，而各個段之間可以離散存放。4.5.2分段系統的基本原理段號段內地址4.5基本分段存儲管理方式地址映射機構段表分段式地址變換過程段表始址段表長度段表寄存器＞段號3段內地址723越界中斷①①邏輯地址＋②②段號段長2000段基址16K400154K15025K90038K……8K＋723…365………③④8K8915物理地址內存中的段表內存3號段③例：給定邏輯地址中段號為3，段內地址為723分頁和分段的主要區別分頁是出于系統管理的需要，分段是出于用戶應用的需要。一條指令或一個操作數可能會跨越兩個頁的分界處，而不會跨越兩個段的分界處。頁大小是系統固定的，而段大小則通常不固定。邏輯地址表示：分頁是一維的，各個模塊在鏈接時必須組織成同一個地址空間；分段是二維的，各個模塊在鏈接時可以每個段組織成一個地址空間。通常段比頁大，因而段表比頁表短，可以縮短查找時間，提高訪問速度。返回4.5.3信息共享分頁系統中共享editor的示意圖例:一個多用戶系統可同時容納40個用戶，都執行一個文本編輯程序（160KB代碼和40KB數據區），代碼是可重入的假定頁面大小為4KB。分段系統中共享editor的示意圖editor進程1data1進程2editordata2段表段長基址16080402401608040380editordata1…data280240280380420方便了用戶編程。多個邏輯段形成作業這種組織方式，使用戶可以清晰地設計和了解程序的結構。便于實現程序和數據的共享與保護。程序的動態鏈接實現方便。通常一個源程序經過編譯后所形成的若干個目標程序，還需再經過鏈接，形成可執行代碼后才能運行，這種在裝入時進行的鏈接稱為靜態鏈接。動態鏈接是指在作業運行之前，并不把幾個目標程序段都鏈接起來，而是先將主程序對應的目標程序裝入內存并啟動運行，當運行過程中又需要調用某段時，再將該段（目標程序）調入內存并鏈接起來。所以，動態鏈接是以段為基礎的。應用中會發生數據動態增長的情況，而且這種增長是無法預知的，采用分段管理可以很好地解決這個問題。分段存儲管理的優缺點優點：缺點：有碎片問題。4.5.4段頁式存儲管理方式在段頁式存儲管理系統中，處理機給出的有效地址被劃分為三部分：段號、段內頁號和頁內地址。段頁式存儲管理中，記錄邏輯地址到物理地址的映射表包括段表和頁表。它們的結構和映射功能如圖所示。段號S段內頁號P頁內位移量W

段號頁表長度頁表始址03122段表頁號0塊號120段的頁表頁號0塊號11段的頁表內存系統區例:給定某個邏輯地址中，段號為2，段內地址為6015，若系統規定塊大小為1KB，則采用段頁式管理，該邏輯地址表示：段號為2，段內頁號為5，頁內地址為895。其地址變換過程如圖所示。段表始址段表長度段表寄存器＞越界中斷①①＋②②段號頁表長度0頁表始址12③內存＋16頁號塊號…頁表段號2頁號5頁內地址895…③16895……365…物理地址17279內存內存邏輯地址④⑤①段號2與段表寄存器中存放的段表長度比較以判斷是否越界，如果越界，則轉錯誤中斷處理，否則轉②；②段表始地址+段號×段表項長度，就得到屬于該段的頁表始地址和頁表長度；③頁號與頁表長度進行越界檢查，頁表始地址+頁號×頁表項長度，就得到內存頁表中記錄的該頁對應的物理塊號16；④16(塊號)×1024(塊大小)+895(頁內地址)=17279(一個物理地址號)；⑤訪問內存17279單元，得到需要的數據365。采用段頁式存儲管理，從邏輯地址到物理地址的變換過程中要三次訪問內存，一次是訪問段表，一次是訪問頁表，再一次是訪問內存物理地址。這就是說，當訪問內存中的一條指令或數據時，至少要訪問內存三次，這將使程序的執行速度大大降低。為此，可以像在分頁存儲管理中那樣，使用聯想存儲器的方法來加快查表速度。4.6虛擬存儲器的基本概念常規存儲管理方式的共同點：要求一個作業全部裝入內存后方能運行。問題：

(1)有的作業很大,所需內存空間大于內存總容量,使作業無法運行。

(2)有大量作業要求運行，但內存容量不足以容納下所有作業，只能讓一部分先運行，其它在外存等待。解決方法

（1）增加內存容量。（2）從邏輯上擴充內存容量

----覆蓋

----對換

----虛擬存儲器4.6.1虛擬存儲器的引入常規存儲器管理方式的特征（1）一次性：作業在運行前需一次性地全部裝入內存。將導致上述兩問題。（2）駐留性：作業裝入內存后，便一直駐留內存，直至作業運行結束。局部性原理

指程序在執行時呈現出局部性規律，即在一較短時間內，程序的執行僅限于某個部分，相應地，它所訪問的存儲空間也局限于某個區域。局部性又表現為時間局部性(由于大量的循環操作，某指令或數據被訪問后，則不久可能會被再次訪問)和空間局部性（如順序執行，指程序在一段時間內訪問的地址，可能集中在一定的范圍之內）。虛擬存儲器的概念基于局部性原理，程序在運行之前，沒有必要全部裝入內存，僅須將當前要運行的頁（段）裝入內存即可。運行時，如訪問的頁（段）在內存中，則繼續執行，如訪問的頁未在內存中（缺頁或缺段），則利用OS的請求調頁（段）功能，將該頁（段）調入內存。如內存已滿，則利用OS的頁（段）置換功能，按某種置換算法將內存中的某頁（段）調至外存，從而調入需訪問的頁。

虛擬存儲器是指僅把作業的一部分裝入內存便可運行作業的存儲管理系統，它具有請求頁調入功能和頁置換功能，能從邏輯上對內存容量進行擴充，其邏輯容量由外存容量和內存容量之和決定，其運行速度接近于內存，成本接近于外存。4.6.2虛擬存儲器的實現方法1、分頁請求系統在分頁系統的基礎上，增加了請求調頁功能、頁面置換功能所形成的頁式虛擬存儲器系統。它允許只裝入若干頁的用戶程序和數據，便可啟動運行，以后在硬件支持下通過調頁功能和置換頁功能，陸續將要運行的頁面調入內存，同時把暫不運行的頁面換到外存上，置換時以頁面為單位。

系統須設置相應的硬件支持和軟件：

（1）硬件支持：請求分頁的頁表機制、缺頁中斷機構和地址變換機構。（2）軟件：請求調頁功能和頁置換功能的軟件。2、分段請求系統在分段系統的基礎上，增加了請求調段功能及分段置換功能，所形成的段式虛擬存儲器系統。它允許只裝入若干段的用戶程序和數據，便可啟動運行，以后在硬件支持下通過請求調段功能和分段置換功能，陸續將要運行的段調入內存，同時把暫不運行的段換到外存上，置換時以段為單位。系統須設置相應的硬件支持和軟件：

（1）硬件支持：請求分段的段表機制、缺段中斷機構和地址變換機構

（2）軟件：請求調段功能和段置換功能的軟件4.6.3虛擬存儲器的特征1、多次性多次是虛擬存儲器最重要的特征。指一個作業被分成多次調入內存運行。2、對換性對換性指允許在作業運行過程中進行換進、換出。換進、換出可提高內存利用率。3、虛擬性虛擬性是指能夠從邏輯上擴充內存容量，使用戶所看到的內存容量遠大于實際內存容量。虛擬性是虛擬存儲器所表現出來的最重要的特征，也是實現虛擬存儲器最重要的目標。注：虛擬性以多次性和對換性為基礎，而多次性和對換性又是離散分配為基礎。4.7請求分頁存儲管理方式在簡單頁式存儲管理的基礎上，增加請求調頁和頁面置換功能。1.對頁表的修改狀態位（中斷位）：表示該頁是在內存還是在外存訪問位：根據訪問位來決定淘汰哪頁（由不同的算法決定）修改位：表示該頁在調入內存后是否被修改過。由于內存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時就不需將該頁寫回到外存上，以減少系統的開銷和啟動磁盤的次數；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本頁號塊號狀態位訪問字段修改位外存地址在請求分頁系統中，每當所要訪問的頁面不在內存時，便要產生一缺頁中斷，請求OS將所缺頁調入內存。2．缺頁中斷機構與一般中斷的主要區別在于：缺頁中斷在指令執行期間產生和處理中斷信號，而一般中斷在一條指令執行完后檢查和處理中斷信號。缺頁中斷返回到該指令的開始重新執行該指令，而一般中斷返回到該指令的下一條指令執行。一條指令在執行期間，可能產生多次缺頁中斷。3.地址變換機構開始頁號>頁表長度？CPU檢索快表NNY頁表項在快表中？訪問頁表頁在內存？修改訪問位和修改位修改快表形成物理地址地址變換結束越界中斷程序請求訪問一頁YN缺頁中斷處理Y保留CPU現場內存滿嗎？將一頁從外存換入內存OS命令CPU從外存讀缺頁啟動I/O硬件Y從外存中找到缺頁選擇一頁換出該頁被修改否？將該頁寫回外存修改頁表NYN4.7.2內存分配策略和分配算法在請求分頁系統中，為進程分配內存時，將涉及以下三個問題：1、最小物理塊數的確定最小物理塊數指能保證進程正常運行所需的最小的物理塊數，與計算機的硬件結構有關，取決于指令的格式、功能和尋址方式。2、物理塊的分配策略

（1）固定分配局部置換：為每個進程分配固定數目n的物理塊，在整個運行中都不改變。如出現缺頁，則從中置換一頁。

（2）可變分配全局置換：分配固定數目的物理塊，但OS自留一空閑塊隊列，若發現缺頁，則從空閑塊隊列中分配一空閑塊與該進程，并調入缺頁于其中。當空閑塊隊列用完時，OS才從內存中任選擇一頁置換。

（3）可變分配局部置換：分配一定數目的物理塊，若發現缺頁，則從該進程的頁面中置換一頁，根據該進程缺頁率高低，則可增加或減少物理塊。

3、物理塊分配算法在采用固定分配策略時，將系統中可供分配的所有物理塊分配給各個進程，可采用以下幾種算法：

（1）平均分配算法：平均分配給各個進程。

（2）按比例分配算法：根據進程的大小按比例分配給各個進程。

（3）考慮優先權的分配算法：將系統提供的物理塊一部分根據進程大小先按比例分配給各個進程，另一部分再根據各進程的優先權適當增加物理塊數。4.7.3頁面調入策略

調入策略決定什么時候將一個頁面由外存調入內存，從何處將頁面調入內存。何時調入頁面

預調頁策略：將那些預計在不久便被訪問的頁預先調入內存。這種調入策略提高了調頁的效率，減少了I/O次數。但由于這是一種基于局部性原理的預測，若預調入的頁面在以后很少被訪問，則造成浪費，故這種方式常用于程序的首次調入。請求調頁策略：當進程運行中訪問的頁出現缺頁時，則發出缺頁中斷，提出請求調頁，由OS將所需頁調入內存。這種策略實現簡單，應用于目前的虛擬存儲器中，但易產生較多的缺頁中斷，且每次調一頁，系統開銷較大，容易產生抖動現象。從何處調入頁面

在請求分頁系統中，通常將外存分成了文件區和對換區，文件區按離散分配方式存放文件，對換區按連續分配方式存放對換頁。

對換區：系統有足夠的對換區空間，運行前可將與進程相關的文件從文件區復制至對換區，以后缺頁時，全部從對換區調頁。文件區：系統沒有足夠的對換區空間，凡是不會被修改的文件，每次都直接從文件區調頁。文件區、對換區：系統沒有足夠的對換區空間，對可能會修改的文件第一次調頁直接從文件區，換出時換至對換區，以后從對換區調頁。UNIX方式：凡未運行過的頁面均從文件區調頁，運行過的頁面和換出的頁面均從對換區調頁。4.8頁面置換算法發生了6次面置換，9次缺頁中斷。4.8.1最佳（OPT:Optimal）置換算法它是一種理想化的算法，性能最好，但在實際上難于實現。即選擇那些永不使用的，或者是在最長時間內不再被訪問的頁面置換出去。但是要確定哪一個頁面是未來最長時間內不再被訪問的，目前來說是很難估計的，所以該算法通常用來評價其它算法。例：假定系統為某進程分配了三個物理塊，并考慮有以下的頁面號引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。頁面引用70120304230321201701777222222222222227770000004440000000000物理塊1111333333331111111缺頁xxxxxxxxx物理塊2物理塊3(2)先進先出（FIFO）置換算法

算法的基本思想是，總是先淘汰那些駐留在內存時間最長的頁面，即先進入內存的頁面先被淘汰。這種算法實現起來比較簡單，性能最差。會出現BeLady異常現象。BeLady異常：一般來說，如果分給進程的頁框數增加，則缺頁的頻率應該減少。但這個結論并不普遍成立，對于某些頁面訪問序列，FIFO有隨著分給的頁框數增加，缺頁頻率也增加的異常現象。利用FIFO算法對上例進行頁面置換的結果如下:發生了12次面置換，15次缺頁中斷。頁面引用70120304230321201701701223042300012227017011230423330111270物理塊1700123042223000127缺頁xxxxxxxxxxxxx物理塊2物理塊3xxBeLady異常現象9104.8.2最近最久未使用置換算法

（LRU：LeastRecentlyUsed）該算法是選擇最近最久未使用的頁面予以淘汰，系統在每個頁面設置一個“計時”標記，用以記錄這個頁面自上次被訪問以來所經歷的時間T，當要淘汰一個頁面時，選擇T最大的頁面。但在實現時需要硬件的支持。利用LRU算法對上例進行頁面置換的結果如下:發生了9次面置換，12次缺頁中斷。頁面引用70120304230321201701701203042303212017017012030423032120170物理塊1701223042203312017缺頁xxxxxxxxx物理塊2物理塊3xxxＮＲＵ是一種最為流行的、低開銷的ＬＲＵ近似算法。它所依據的理由是：在最近一段時間內未使用過的頁在最近的將來不大可能被使用。在具體實現中，系統為每個頁增加兩個硬件位(用軟件模擬)：（4）最近未使用算法ＮＲＵ（NotRecentlyUsed）設置修改位的意義在于，如果被淘汰的頁沒被修改過，由于每頁在外存都有副本，因此不必把它再寫回外存，否則必須寫回外存。顯然最好的選擇是淘汰沒修改過的頁，這樣可以減少系統開銷。初始時，所有實頁的引用位和修改位都置為０，當訪問某頁時，該頁的引用位置為１，一旦修改了某頁，便置其修改位為１。當要淘汰時按下列頁類的次序選擇:首先選擇１類實頁進行淘汰，然后次之。為了避免到某一時刻大多數甚至所有實頁的引用位都為１，從而無法區別哪一頁最應該被淘汰，系統需要周期性地（設周期為ｔ）將所有引用位都置０。１類：未引用過，未修改過２類：未引用過，修改過３類：引用過，未修改過４類：引用過，修改過(1)分配給進程的物理頁面數(2)頁面本身的大小(3)程序的編制方法5.影響缺頁次數的因素(4)頁面淘汰算法例：一程序把128*128的數組置初值0，每個元素為一個字。假定每頁128個字，數組每一行元素存放在一頁中，只有一塊內存，初始時第一頁在內存。程序編制方法1：Forj:=1to128Fori:=1to128A[i,j]:=0;128*128-1次缺頁中斷程序編制方法2：Fori:=1to128Forj:=1to128A[i,j]:=0;128-1次缺頁中斷5.7.4性能問題1.顛簸（抖動）操作系統會對CPU的工作情況進行監督，如果發現CPU出現空閑，它會調入新的進程來增加多道程序度，保持CPU的高利用率。但是在采用全局置換的方式下，它會導致其它進程的某些頁被置換出內存，而該進程執行時會因此產生缺頁，所以它又會置換另外進程的頁，由此造成連鎖反應，使得整個系統中頁面置換頻繁發生。在每次置換過程中，都需要啟動磁盤I/O，這種低速的延遲操作會造成CPU等待，操作系統發現CPU空閑后，又開始增加多道程序度……于是整個系統就在進行頻繁的頁面置換，這種狀況就稱為“抖動”，它會嚴重地影響到系統的性能。抖動的發生CPU利用率抖動多道程序度為了減少抖動的產生，保證系統性能，可以采用局部置換的方法。發生缺頁的進程不能置換其它進程的物理塊，只能從系統為自己所分配的地址空間中置換。這樣當一個進程發生抖動時，不會造成其它進程后繼抖動，將抖動的影響限制在一個小的范圍內。但是，這種方法有一定的局限性，因為發生抖動的進程會因為頻繁進行磁盤I/O而形成一個等待隊列，這個等待隊列也會造成正常的進程置換頁面時間的增加，從而影響CPU的吞吐量。為了預防抖動，應該給進程盡可能提供一段時間所需的所有頁面，但系統又如何得知到底需要哪些頁面呢？有多種技術