第三章存儲器管理學習目標1.理解計算機系統的存儲體系，掌握操作系統存儲管理的目的和任務。2.理解并掌握各種存儲管理方法的管理思想和手段，熟練掌握相應的地址重定位方法、辨析其優缺點。3.了解覆蓋與對換技術的原理。學習目標4.理解虛擬存儲管理技術的原理，熟練掌握頁式虛擬存儲管理的管理思想和手段、地址重定位機構及計算方法、常用頁面置換策略及其效率分析。5.理解虛擬存儲管理中相關的軟件策略。目錄3.1存儲器管理概述3.2重定位3.3存儲器管理技術3.4分區管理技術3.5分頁存儲管理3.6分段存儲管理3.7段頁式存儲管理3.8虛擬存儲器管理3.9常用的頁面置換算法3.10虛擬存儲管理中的軟件策略3.1.1存儲器管理的目的3.1.2存儲器管理的任務3.1存儲器管理概述計算機的用戶對存儲器的需求歸納起來只有兩點，一是夠用，二是安全。從操作系統的資源管理者角度來看，存儲器管理的目的是有效地組織和管理存儲空間、提高存儲器的利用率。3.1.1存儲器管理的目的1.主存分配與回收2.地址映射3.主存保護4.信息共享5.主存擴充3.1.2存儲器管理的任務為充分利用主存空間，尤其是在多道程序設計的環境中，最關鍵的工作之一就是選取適當的存儲劃分原則，不同的劃分原則下，主存分配和回收方法以及為具體實現時系統所要維護的數據結構也不同，如分頁、分段或段頁結合的存儲方案。1.主存分配與回收地址映射也稱地址變換，或重定位。存儲管理要完成用戶地址空間中的地址與主存存儲空間地址的變換，地址變換可以在程序執行前就完成，也可以一邊執行根據需要再進行變換，即靜態重定位和動態重定位，不同的方法所需的系統硬件結構和軟件方法也不同。2.地址映射在多道程序設計環境中，主存中同時駐留多道作業或者說多個進程，為了確保它們彼此之間在空間訪問上不互相干擾，或是出現非法訪問造成不可預知的錯誤，要求系統必須具備主存保護的功能。主存保護的方法主要有上下界保護法和鍵保護法。3.主存保護也稱為界地址法，是利用2個專門寄存器分別保存當前進程的主存起始地址（上界）和結束地址（下界），當有地址訪問發生時，主存保護機構自動進行合法性檢查。（1）上下界保護法（1）上下界保護法100K500K受保護的程序或數據……100K500K上界寄存器下界寄存器內存合法訪問100K≤訪問地址﹤500K鍵保護法是指作業裝入主存的同時就根據它的權限賦予一個鍵值，當地址訪問發生時，主存保護機構對作業持有的鍵值與其欲訪問的主存區域的鍵值相比較，相同則是合法的，否則將拒絕。（2）鍵保護法（2）鍵保護法鍵2K6K4K……0RW2W內存…2…當前PSW正確訪問

LOAD15000STORE25200非法訪問

LOAD13000保護鍵在多道環境中各作業之間有存儲區被保護的需求，也有共享的需求，即當多個作業需要使用相同的一部分程序或數據時，只存儲同一個副本支持共享地使用它，顯然比為每個作業存儲一個副本更合理，存儲管理部分必須在不破壞存儲保護機制的基礎上，授權相關作業對主存共享區域進行訪問。4.信息共享主存容量有限并不意味著系統中運行的用戶作業要絕對受制于主存的容量，已經實現了多種存儲管理技術向用戶呈現比實際主存要大得多的地址空間，這些技術都是借助了大容量的輔助存儲器，如覆蓋、對換和虛擬存儲器等，必須相應地解決主輔存之間的信息傳輸，特別是虛擬存儲管理中，涉及讀取、放置、替換、駐留集管理等多種策略的設計問題。5.主存擴充3.2.1絕對地址與相對地址3.2.2地址空間與重定位3.2重定位1.絕對地址主存儲器的每個存儲單元的地址稱為絕對地址，也稱為物理地址和主存地址。3.2.1絕對地址與相對地址2.相對地址對于高級語言的程序員來說沒有地址的概念，而處理器必須知道它的指令從哪里取、數據從哪里讀再往哪里寫，即必須有明確的地址這種名空間到地址空間的轉換由編譯程序完成，因為此時并不能知道它將被裝入主存的哪個位置，地址的上限由該文件自身的需要決定，所以稱為相對地址，也稱為邏輯地址3.2.1絕對地址與相對地址目標文件再經過鏈接形成可執行程序，以后備作業的形式等待被調度裝入主存中以便運行，所以將目標文件的相對地址空間稱為作業地址空間，而主存儲器中的絕對地址空間稱為存儲空間。3.2.2地址空間與重定位這種將作業地址空間中要訪問的地址變換為實際訪問的存儲空間中地址的過程就叫地址重定位，簡稱重定位，也稱為地址映射。3.2.2地址空間與重定位作業A的地址空間是0~1KB，而它被裝入到主存空間中1K~2K的位置上，因此，作業地址空間中的地址都要加上1KB才是正確的。3.2.2地址空間與重定位作業A的地址空間1K115212802K內存的存儲空間…LOAD1,2560128256X1K………LOAD1,256X……LA（256）+BA（1024）＝PA（1280）圖3-3地址重定位示例如果作業被裝入主存時立即進行相對地址到絕對地址的變換，則稱為靜態重定位。參考圖3-3中的示例，實施靜態重定位就是將作業地址空間中的邏輯地址LA，依次增加該作業裝入主存后所分得的空間首地址BA，得到實際要訪問的物理地址PA。1.靜態重定位靜態重定位的優點就是方法簡便，不需要額外的硬件支持，不影響作業的執行速度。但缺點也是很明顯的，首先，它必須要求程序在執行前完成全部的鏈接工作，否則無法得到正確的物理地址。其次作業在裝入后不允許再移動，無法實現虛擬存儲等主存擴充技術，不利于多道程序設計。1.靜態重定位動態重定位是指作業裝入主存時并不立即進行邏輯地址到物理地址的變換，而是CPU執行到具體的指令時，再把該指令中訪問的邏輯地址修改為實際的物理地址，并繼續執行，因此地址的重定位是在程序執行過程中動態完成的。2.動態重定位這種重定位的方法會延誤指令的執行，因此通常要增加硬件機構，如一個或多個基址寄存器、邏輯地址寄存器、加法器等，在較復雜的系統中還可能開辟有多個緩沖以提高定位的速度。2.動態重定位優點：更有利于多道程序設計（1）程序執行前不要求全部裝入主存，因為計算物理地址的工作是在執行某一指令時才做的，這是主存擴充技術實現的基礎；（2）允許作業在主存中改變位置，甚至是多次在主、輔存間交換。（3）更適于實現不連續的存儲分配。2.動態重定位3.3.1覆蓋技術3.3.2對換技術3.3存儲器管理技術先來看一個基本的程序結構示例，它包含有5個模塊，相互調用關系及占用空間大小如圖3-4所示。3.3.1覆蓋技術M0(20KB)M2(20KB)M1(15KB)M1.1(20KB)M1.2(30KB)M2.1(40KB)20K存儲空間M0M1M1.1…覆蓋區1(20K)…覆蓋區2(40K)從圖3-4中所示的實例可以看出，利用覆蓋技術后，在主存中占用80K的空間可以運行總大小145K的程序，節省了主存空間，也就能夠使得更多的程序在主存中的同時駐留，從用戶的角度來看，就達到了主存擴充的效果。3.3.1覆蓋技術覆蓋技術有一定的缺點。第一，覆蓋的順序要由程序員來設計，這意味著程序員必須完全清楚整個程序的結構，這不單單是增加了程序員的工作負擔，對于開發較大型軟件系統來說做到這點是非常困難的；另一方面覆蓋方法不能靈活地適應程序自身的變化，如果程序發生變化，比如模塊間的調用順序更換或模塊本身需要更多的空間時往往要全部重新設計。3.3.1覆蓋技術對換技術是另一種主存管理技術，與覆蓋技術以程序自身的邏輯模塊為單位進行主輔存之間的交流不同，對換是以進程為單位，當有新的進程請求進入主存又沒有空閑空間可供使用時，則選擇主存中不活躍的進程將其換出到輔存中專門開辟的對換區。3.3.2對換技術如圖3-5所示，主存中依次進入了P1、P2、P3、P4，當P5要求進入時無可供分配的空間，此時P2進程處于非活躍狀態（阻塞或是由于某種原因而掛起），則將P2換出（非活躍進程可能有多個，選擇時還要考慮空間等因素），允許P5進入，P6的情形與P5相同，隨著進程的推進，其他進程結束或進入非活躍狀態后，還可以將P2、P3等再換入回主存繼續執行。3.3.2對換技術主存P2P7P3P8P1P5P4P6………輔存對換區對換技術的優點：（1）利用對換技術實現了主存擴充，因為存放進程的區域擴展到了輔存的對換區中。（2）加快了作業的周轉，提高了處理器的利用率。雖然進程仍然要被裝入主存才能夠執行，但輔存對換區的幫助使得主存中可以“集中精力”存放活躍進程，使它們能夠更快地被調度執行。3.3.2對換技術（3）置換范圍是全局的，適應性更好。對進程換入換出的選擇范圍不是單個程序的局部區域，而是整個系統的全局范圍。（4）利用對換技術最突出的優點在于進程的換入與換出是由系統根據進程和存儲空間的狀態自動完成的，對于程序員來說是不可見的。3.3.2對換技術但是對換技術對作業周轉速度的提升并不總是一致的，從單個進程的角度看，進程在執行過程中不能始終處于主存中，被換出到輔存后再次進入必須經過一段時間的排隊等候，將會推遲進程的下一步操作；3.3.2對換技術從系統效率的角度看，如果選擇換入/換出的進程不當，可能導致進程的頻繁進出主存，出現所謂的“抖動”現象，即處理器消耗了過多的時間解決換入/換出操作，相對地減少了供給進程本身執行所需的服務時間，處理器的效率反而下降。3.3.2對換技術3.4.1固定式分區管理3.4.2可變式分區管理3.4.3可重定位分區分配3.4分區管理技術固定式分區管理是指將主存空間預先劃分成若干邊界固定，但大小不等的區域，每個區域供一個作業占用。系統建立一張分區表，記錄分區的使用情況，如圖3-6所示。3.4分區管理技術3.4分區管理技術主存J1OS占用區J2空閑空閑…分區號起始地址空閑/占用大小032K116K148K016K264K132K作業號J1J2396K032K分區表32K48K64K96K……由于每一個分區可以裝入一個作業，所以，固定式分區管理方案支持了多道程序運行，但是這種簡單的管理方案有如下的缺點：（1）主存儲器的內部碎片較多，降低了主存利用率。3.4分區管理技術由于作業獨占一個分區，當分區大小超過作業大小時剩余的空間也不能再被利用，稱為內部碎片，平均看來每個分區將有一半的碎片，整個主存中碎片量約為：（2）可同時運行的作業道數受分區個數限制。（3）大作業（超過最大分區容量的）無法運行。3.4分區管理技術可變式分區管理方案仍然是以分區為基礎，每一個分區存放一個作業，但與固定式分區不同的是，不再事先對主存進行區域的劃分，而是當有作業申請進入主存時，由系統根據當時主存的使用情況劃分一個與作業大小相等的空閑區域供其使用3.4.2可變式分區管理3.4.2可變式分區管理進程A（8K）進程B（32K）進程C（16K）進程隊列OS主存（ABC進入后）進程A（8K）進程C（16K）OS進程A（8K）進程B（32K）進程C（16K）進程B（32K）空閑…OS主存（初始）進程A（8K）進程C（16K）OS進程A（8K）進程B（32K）進程C（16K）進程B（32K）空閑為完成對主存空間的管理和分區分配，系統維護一個數據結構稱為空閑分區表，表中記錄空閑分區的起始地址和大小，空閑分區表可以按照以下兩種方式組織。1.分區的分配（1）最先適應（FirstFit）分區分配算法此時，空閑分區表以空閑區的起始地址由低到高排序，有新的作業申請空間時，從頭開始查找，找到第一個可以滿足新作業空間需要的則分配之。1.分區的分配（2）最佳適應（BestFit）分區分配算法空閑分區表以空閑區容量的大小由小到大排序，從空閑分區表的起始處開始查找，最先找到的能夠滿足作業要求的空閑區也是所有空閑區中最適合的，因此稱為最佳適應分區分配。1.分區的分配最先適應法空閑分區表分區始址分區大小32K16K126K2K是否否是是否查找空閑分區表當前表項長度滿足要求分配，并將此項從空閑分區表中移除分區表結束當前表項長度等于申請量無法分配下一項截取所需大小，并將剩余部分插回空間分區表結束開始……最佳適應法空閑分區表分區大小分區始址32K16K126K2K……(a)(b)(c)當作業完成要釋放出所占用的空間，操作系統完成回收工作。對分區的回收有4種不同的情況，具體的操作也有所不同1.回收分區既無上鄰空閑分區也無下鄰空閑分區。此時空閑分區表（以最先適應分區分配算法為例，下同）增加一項，記錄新回收分區起始地址和大小。2.分區的回收2.回收分區有上鄰空閑分區但無下鄰空閑分區。此時需要將新回收分區與其上鄰合并，修改空閑分區表中上鄰空閑分區的大小即可。2.分區的回收3.回收分區有下鄰空閑分區但無上鄰空閑分區此時的合并操作有兩步，一是用新回收分區的起始地址更新空閑分區表中該下鄰空閑區的起始地址，二是更新該下鄰空閑區的大小。2.分區的回收4.回收分區既有上鄰空閑分區也有下鄰空閑分區，此時的合并操作將致使空閑分區表減少一項，留用新回收分區的上鄰起始地址，并將其大小更新為三者之和。2.分區的回收2.分區的回收(a)(b)(c)(d)占用空閑toptoptoptop…X……X……X……X…sizesizesizesize[例3-1]已知在某一時刻，系統內有J1（8K）、J2（24K）、J3（16K）、J4（12K）、J5（12K）等5道作業同時駐留，主存的分配情況如圖3-10a所示（分區中無作業編號的為空閑分區），從此時刻開始，相繼出現如下事件：J2完成、J4完成、J3完成、J6（8K）申請進入、J7（64K）申請進入，試完成相應的主存空間分配與回收操作。2.分區的回收J18KJ18KJ18KJ18KJ224K24K24K68KJ316KJ316KJ316K16K16K28KJ412KJ412KJ512KJ512KJ512KJ512K8K8K8K8K圖3-10可變分區存儲管理示例過程模擬1最先適應法（FF）最佳適應法（BF）起點分區始址分區大小分區大小分區始址48168888881648J2完成分區始址分區大小分區大小分區始址82488848161648888248J4完成分區始址分區大小分區大小分區始址82488848282488882848J3完成分區始址分區大小分區大小分區始址868888888688圖3-11可變分區分配示例之分區表變化1在這一階段來看，最先適應和最佳適應的區別不是很明顯，但已經可以體會出，最優適應法在尋找鄰接分區和調整分區表時要比最先適應開銷大。接下來，再陸續發生J6（8K）申請進入、J7（64K）申請進入兩個事件，此時主存分配和分區表變化如圖3-12和圖3-13所示。2.分區的回收J18KJ18KJ18KJ18KJ68K68KJ68KJ764K60K60K4KJ512KJ512KJ512KJ512K8KJ68K8KJ68K(a)J6申請進入(b)J7申請進入FF成功BF成功FF失敗BF成功圖3-12可變分區存儲管理示例過程模擬2在這一階段，兩種分配方法出現了顯著的不同，J6請求進入時，雖然它只要求8K的空間，但根據最先適應法的算法規則，它也會從低地址端尋找適合的分區，剩余部分則會調整填入空閑分區表，最優適應法則會尋求尺寸上更適合的一個；而當J7請求進入時，最先適應法會報告無法分配，最優適應則可以接收。2.分區的回收最先適應法（FF）最優適應法（BF）J6請求進入分區始址分區大小分區大小分區始址860688888

J7請求進入分區始址分區大小分區大小分區始址860472888

圖3-13可變分區分配示例的分區表變化2可變分區存儲管理方案與固定分區方式相比，雖然管理上增加了一定的復雜性，但取得三方面的優勢：1.不會產生內部碎片，因為各作業所占用的空間就是它所需要的大小；2.可同時運行的作業的道數不再有分區個數的限制，更有利于多道程序設計；3.較大作業也有了運行的機會。2.分區的回收問題：隨著作業的進入和退出，本來連續的大空閑區很快被分割成了多個分散的小的空閑區，有些甚至不能滿足任何新作業在空間上的要求，而無法分配出去，把這種不能分配給任何作業的存儲“零頭”稱為外部碎片。2.分區的回收[例3-2]假設某系統主存容量128K，操作系統占用32K，初啟狀態時的空閑分區表如圖3-14a所示，設作業最小為8K，試運用最先適應分區分配算法模擬事件序列：J1（16K）進入、J2（48K）進入、J3（30K）進入、J1完成、J4（10K）進入的主存分配與回收過程。2.分區的回收在模擬作業進入和退出的過程中，主要是對空閑分區表進行更新，如題意按照最先適應分配算法，空間分區表按空閑區始地址由小到大排序，其變化過程如圖3-14a~f所示，全部事件結束后主存區域的狀態如圖3-15a所示。2.分區的回收（b）J1進入分區編號分區始址分區大小132K96KFirstFit空閑分區表更新過程分區編號分區始址分區大小148K80K（a）初始狀態（c）J2進入分區編號分區始址分區大小196K32K（d）J3進入分區編號分區始址分區大小1126K2K（e）J1完成分區編號分區始址分區大小132K16K2126K2K（f）J4進入分區編號分區始址分區大小142K6K2126K2K圖3-14可變分區產生外部碎片的示例(b)空閑(a)“壓縮”后J4OS占用區J2J36K2KJ4OS占用區J2J38K圖3-15外部碎片與壓縮外部碎片的存在是可變分區管理的主要弊端，可以使用“壓縮”技術進行改進，即由操作系統不斷調整作業的位置，使其始終連續地占據主存的一端，而另一端則整理成整塊的空閑區（如圖3-15b所示），這樣作業在裝入主存后是可以移動的，因此也將這種改進的可變分區管理方法稱為可重定位的分區分配。3.4.3可重定位分區分配以上的三種分區管理方案在地址映射方面都比較簡單，即作業地址空間中要訪問邏輯地址只需加上其裝入主存時所占用的物理分區的首地址就是實際訪問的物理地址。此外，可重定位的分區分配方案比較適合采用動態重定位方法，因為作業裝入后可能多次移動，不適宜用靜態重定位的方法一次性完成全部地址轉換工作，而另外兩種分區方案則沒有要求。3.4.3可重定位分區分配3.5.1基本原理3.5.2存儲空間的分配與回收3.5.3分頁系統中的地址映射3.5.4頁的共享與保護3.5分頁存儲管理采用分頁存儲管理是指將作業地址空間和存儲空間按相同的尺寸進行相等大小的劃分（大小一般為2的方冪），對作業地址空間劃分后稱為邏輯頁，簡稱頁。3.5.1基本原理對存儲空間進行劃分后形成一個個相等大小的物理塊，簡稱塊，從0開始編號，主存儲器件的容量是確定的，所以塊的數量也是一定的。當有作業裝入主存時，一頁裝入一個空閑塊中，但不要求連續的頁也占用連續的塊。3.5.1基本原理主存…12340678951234010作業A5個邏輯頁1234001234圖3-16分頁存儲管理原理圖頁式存儲管理時存儲空間的分配以塊為單位，操作系統為每一個作業維護一張頁表，記錄作業頁裝入哪一個物理塊，如圖3-17所示。由于頁與塊大小相等，因此消除了外部碎片，僅在作業的最后一頁才可能存在約為頁尺寸一半大小的頁內碎片，對存儲空間的浪費已經大大減少。3.5.2存儲空間的分配與回收此外，主存空間的管理開銷也很低，僅需以塊號作索引，記錄其分配狀態，作業完成釋放物理塊后，將其狀態置為空閑，不需要再對空閑區域的大小及始址進行管理3.5.2存儲空間的分配與回收3.5.2存儲空間的分配與回收頁號塊號07142833頁表46圖3-17作業A的頁表分頁式存儲管理方案提高了主存的利用率，而且分配與回收工作的開銷也較小，但是在進行地址映射時要比分區式管理復雜得多。分頁式系統的地址映射機構由硬件和軟件兩部分構成。軟件部分即作業的頁表，作業裝入時也將其頁表存放在主存中，其入口保存在頁表基址寄存器中；硬件部分除頁表基址寄存器外還有地址轉換硬件。3.5.3分頁系統中的地址映射3.5.3分頁系統中的地址映射PBPb頁表頁表起址寄存器頁表始址b頁號P偏移W邏輯地址LA塊號B偏移W物理地址PAb+P圖3-18頁式存儲管理地址映射機構及過程作業地址空間中任一邏輯地址LA變換為物理地址PA的過程為：（1）將LA拆分為頁號P和頁內偏移量W：P=LA/SIZE

（式3-1）W=LA%SIZE

（式3-2）其中SIZE代表頁尺寸。3.5.3分頁系統中的地址映射（2）查詢頁表，即頁號P與頁表基址相加，得到該頁的頁表項，若發生越界錯誤則執行第4步；若為合法頁號，則從對應頁表項中取出物理塊號B，計算該塊的起始地址BA：BA=B*SIZE

（式3-3）3.5.3分頁系統中的地址映射（3）計算物理地址PA并返回：PA＝BA+W

（式3-4）（4）報告非法地址錯誤，轉相應處理，返回。3.5.3分頁系統中的地址映射通過上面的描述可見，在頁式存儲管理時為完成一次指令或數據的讀取，要兩次訪問主存：第一次查詢頁表第二次才是真正的取指令或數據，為了加快地址變換的速度，常常加入聯想頁表。3.5.3分頁系統中的地址映射聯想頁表是一種硬存儲器件，查找速度快，所以也稱為快表，相對地，原頁表稱為慢表。加入快表后，地址映射工作的過程在上述第2步時有變化，不再單一地查詢慢表，而是同時查詢快表，快表如果未命中（未有記錄當前被轉換地址相應的P、B），則按原過程執行，并將該慢表項存入快表，如果快表命中，則直接執行第3步形成物理地址。3.5.3分頁系統中的地址映射圖3-19加入快表的頁式存儲管理地址映射過程

BPBPb頁表頁表起址寄存器頁表始址b頁號P偏移W邏輯地址LAPB聯想頁表塊號B偏移W物理地址PAb+P[例3-3]若在一分頁存儲管理系統中，某作業的頁表如圖3-17所示，已知頁面大小為1024B，試將邏輯地址2148轉化為相應的物理地址。3.5.3分頁系統中的地址映射解答：步驟①運用（式3-1）和（式3-2），由邏輯地址2148得到頁號和頁內偏移量：

P=2148/1024=2W=2148%1024=100步驟②查頁表，頁號為2時，有對應的塊號為8，運用（式3-3）計算該物理塊的始址：

BA=8*1024=8192步驟③運用（式3-4），則待求的物理地址為

PA=8192+100=82923.5.3分頁系統中的地址映射[例3-4]設某頁式存儲系統頁大小為2K，主存64K，現有作業A（8K）裝入主存，頁表見圖3-20中所示，試將邏輯地址0x0ABC轉換為實際訪問的物理地址。3.5.3分頁系統中的地址映射3.5.3分頁系統中的地址映射1315141211109876543210000010101011110011位頁內偏移W2位頁號P頁號塊號07142833作業A的頁表001000101011110011位頁內偏移W5位塊號BLA＝0x0ABCPA=0x22BC①②③圖3-20頁式存儲管理地址映射實例模擬分析：本題中，作業總長度為8K，包含213個地址單元，即有效的邏輯地址由13位二進制數構成，其中，頁大小為2K（211），即頁內編址由11位二進制數表示，作業共分4頁（22），即頁號由2位二進制數構成。3.5.3分頁系統中的地址映射解答：預先的處理工作：將十六進制表示的邏輯地址轉換成二進制地址，即0x0ABC(16)=0000101010111100(2)地址映射工作：步驟①通過邏輯地址拆分出頁內偏移和頁號，即邏輯地址的0~10位（低位起為0位）為頁內偏移量W（也稱頁內地址），11~12位為邏輯頁號P。3.5.3分頁系統中的地址映射步驟②查頁表，即從頁表基址寄存器中獲得頁表首項地址，與頁號P相加，找到第P項，得到對應的物理塊號B。步驟③將塊號與頁內偏移相“加”，即物理地址的0~10位對應頁內偏移量，11~15位對應塊號。最后將二進制地址轉換為十六進制表示，故實際訪問的物理地址為0x22BC。3.5.3分頁系統中的地址映射1.頁的共享2.頁的保護3.5.4頁的共享與保護允許作業用共享的方式使用公共部分有利于主存利用率的提高。在共享的要求上需要注意區分數據頁共享和程序頁共享的問題。對于數據頁，各作業可以各自編排不同的頁號；但是程序頁則不同，程序頁中各指令存在順序執行或跳轉到某處執行的相對定位問題，為確保可以映射到正確的物理地址，必須要求各作業用相同的頁號共享程序段。1.頁的共享頁號塊號071429363作業A的頁表48頁號塊號07142933作業B的頁表46…BAB_SP21…AB_SD主存AB_SP1AAB_SP3…3號塊4號塊5號塊6號塊7號塊9號塊10號塊8號塊圖3-21頁的共享（A：作業A占用；B：作業B占用；SP：共享的程序段；SD：共享的數據段）由于作業被分為多頁且裝入主存的互不連續的區域中，所以對頁的保護適用保護鍵（見3.1.2所述）方法，即同一個作業所分配的物理塊賦予相同的數字鎖，“鑰匙”被存儲于該作業（實際上是進程）的程序狀態字里，這里不再贅述。2.頁的保護3.6.1基本原理3.6.2存儲空間的分配與回收3.6.3地址轉換與存儲保護3.6分段存儲管理分頁的存儲管理首先實現了將作業分割、靈活地占用主存的思想，大大減少了碎片的數量，但是由于分頁操作由系統自動地、機械地完成分割，沒有考慮指令與指令之間可能存在的邏輯連續性固定大小的頁面使得程序發生變化時，頁與頁之間相互影響很大。鑒于分頁方式存在的不足，考慮從程序自身的結構特征出發，出現了分段的存儲管理。3.6分段存儲管理在分段管理系統中，對作業地址空間的看法不再是一維線性的，而是先從程序自身的結構特征出發，每一組在邏輯上緊密相關的信息，如子程序、數據區等各形成一個分段，分別編號，從段號0開始到作業結束，而分段內部再從0開始按字節編址，到本段結束，即整個作業地址空間是二維地址[段號S，段內地址D]。3.6.1基本原理3.6.2存儲空間的分配與回收L1-10段0段1段3段2長度L3長度L1長度L2長度L0…主存作業A子程序1子程序2主程序數據集合A子程序1子程序2主程序數據集合A………子程序1的段內編址1…圖3-22段式存儲管理原理圖1.地址轉換系統為每一個作業維護一個數據結構稱為段表，隨作業裝入主存，段表結構中要記錄段號、段長和該段分配得到的主存空間的起始地址。3.6.3地址轉換與存儲保護任一邏輯地址LA的重定位過程如下。（1）從邏輯地址中提取段號S和段內地址D；（2）查找段表，得到S段的物理主存起始地址SA；（3）段內地址D與S段長L比較，超出L為非法地址，結束，否則執行第4步；（4）物理主存起始地址SA與段內地址D相加，得到實際要訪問的物理地址PA，結束。段表的形式和地址映射過程如圖3-23所示。3.6.3地址轉換與存儲保護3.6.3地址轉換與存儲保護SSASb段表段表起址寄存器段表始址b段號S段內地址D邏輯地址LA內存始址SA段內地址D物理地址PAb+S段號S段長L內存始址SA圖3-23分段存儲管理的地址映射過程2.存儲保護和共享段式存儲管理系統通常采用界地址保護方法（參見3.1.2）實現主存保護，但無需另設上下限寄存器，因為作業段表中主存始地址和段長就起到了定界的功能。此外，一個分段集中存放，也有利于實現共享。3.6.3地址轉換與存儲保護[例3-5]設某分段存儲管理系統中，作業X的段表如表3-2所列，試計算邏輯地址[2,560]和[0,218]的物理地址。3.6.3地址轉換與存儲保護段號段長主存始址0200300015006402800125033202400分析：分段存儲管理中邏輯地址為2維，即[段號，段內地址]，因此在地址映射時首先將段號與段表基址相加得到對應的段表項目，進而取得該段在主存的起始地址，接下來，若段內地址未越界（通過比較段內地址和段長來判斷），則可以直接將主存始址和段內地址相加得到物理地址。3.6.3地址轉換與存儲保護解答：1.第一個待求邏輯地址[2,560]由段表可知，2號段的主存始址為1250，段內地址560不超過段長800，未越界，則所求物理地址為560+1250＝1810。2.第二個待求邏輯地址[0,218]由段表可知，0號段的主存始址為3000，但段內地址218超過段長200，即該地址為非法地址，地址映射中止。3.6.3地址轉換與存儲保護3.7.1基本原理3.7.2存儲空間的分配與回收3.7.3地址映射3.7段頁式存儲管理簡要回顧分頁和分段的優缺點。兩種技術都實現了作業分割、化整為零裝入主存，提高了存儲分配的靈活性、有利于主存利用率的提升。分頁的方法消除了外部碎片，但機械分割的方式破壞了程序的天然邏輯結構，不便支持程序的動態變化、不便共享和保護；分段的方法克服了分頁的缺點，但又出現了外部碎片。考慮取二者之長、并彌補其不足，出現了段頁式存儲管理。3.7段頁式存儲管理主存儲空間按相同大小等分為物理塊，作業地址空間首先按其邏輯特征劃分為段，再將段內劃分為等大小的邏輯頁，頁尺寸與物理塊的尺寸相同，段內地址若不是頁尺寸的整數倍，最后剩余的不足一頁的部分仍然按一頁處理，這樣作業地址空間中形成了三維的邏輯地址[段號，段內頁號，頁內偏移]。3.7.1基本原理在進行存儲空間的分配時，首先以段為單位為其分配主存，再以頁為單位裝入物理塊。因此，從作業的角度看，采用的是分段技術，滿足邏輯上的結構關系要求、動態變化要求、便于保護和共享的要求，再從主存的角度看，則采用了分頁技術，滿足了消除碎片、提高主存利用率的要求。3.7.2存儲空間的分配與回收段頁式存儲管理的地址映射需要由系統維護2張表：段表和頁表，硬件部分設有段表基址寄存器、聯想頁表和地址轉換硬件，其映射過程如圖3-24所示。3.7.3地址映射3.7.3地址映射②②’BPSb段表頁表段表起址寄存器段表地址b段號S頁號P偏移D邏輯地址LA＝（S,P,D）SPB聯想頁表物理塊號B偏移D物理地址PAb+S①③④⑤③’圖3-24段頁式存儲管理的地址映射過程3.8.1虛擬存儲器的概念與特征3.8.2請求分頁式虛擬存儲管理技術3.8虛擬存儲器管理3.8虛擬存儲器管理覆蓋對換優點缺點優點缺點作業不要求完全進入主存，節省空間人工操作，工作量大作業可重入，并由系統自行完成整個作業為單位進出主存，開銷大虛擬存儲器＋＋－－圖3-25主存擴充技術的革新虛擬存儲器的實現有一個重要的理論前提，那就是局部性原理。我們可以分析程序執行中處理器取指令和數據時的各種情況，比如：（1）除了分支和調用指令外，程序執行通常是順序的，而這兩類控制指令在所有程序指令中只占了一小部分，即大多數情況下，處理器要取的下一條指令都是緊跟在上一條指令之后；3.8.1虛擬存儲器的概念與特征（2）在較短的時間內，程序中過程調用的深度不會很大（過于頻繁且長度極小的過程調用本身就是不合理的），此時，指令的引用也局限在很少的幾個過程中；（3）在循環結構中，處理器的執行范圍被限制在程序的一個小局部內；（4）程序中涉及到處理數組、記錄序列之類的數據結構時，對它們的引用往往也是在相鄰的或較連續的一段相對位置中。3.8.1虛擬存儲器的概念與特征通過以上分析，說明了在一段時間主存儲器訪問表現出集簇性，稱為局部性原理。在局部性原理的支持下，為用戶作業分配主存空間時可以不必一次性滿足其全部要求，只要保證當前及最近的將來處理器需要的部分（稱為常駐工作集）駐留在主存中即可，而其余部分則是借助輔存存儲。3.8.1虛擬存儲器的概念與特征由于這些工作對用戶是不可見的，所以從用戶作業的角度來看，無論其需求如何，系統都為其分配了與其作業地址空間一致的存儲空間，因此稱為虛擬存儲器。虛擬存儲器的實現由硬件和系統軟件兩部分共同完成。3.8.1虛擬存儲器的概念與特征從以上虛擬存儲器的基本概念可見，虛擬存儲器有以下特征：（1）虛擬擴充（2）部分安裝（3）離散分配（4）多次對換3.8.1虛擬存儲器的概念與特征1.請頁式虛存管理的基本原理請求分頁是最典型的虛擬存儲管理方案，在基本的分頁管理基礎上，做了一些改進。（1）作業執行前不一次性分配所需全部主存，而只裝入初啟所需的一個或幾個頁面；（2）增加缺頁中斷機構，當訪問的頁面不在主存時報告缺頁錯誤；并由缺頁中斷處理例程進行調頁；在不再增加分配給作業的物理塊數時，要選用某種頁面置換算法進行淘汰；

3.8.2請求分頁式虛擬存儲管理技術（3）作業頁表增加了描述頁面狀態的信息位，如存在位和修改位。當頁面存在位為1時表示在主存中，反之將發生缺頁中斷；當頁面修改位為1時表示在其裝入主存后被修改，因此該頁被置換時要重新寫出輔存，相反則不需此項操作。3.8.2請求分頁式虛擬存儲管理技術在作業執行過程中，究竟裝入哪些頁，裝入多少頁呢？工作集模型理論解釋了這個問題。工作集模型認為，每個作業在任何一個時間段△t，都存在一個頁面子集H(t)，其中包含了作業當前需要頻繁訪問的一組頁面。根據局部性原理，這個子集不會很大。但是如果這個子集不全部在主存，將會發生頻繁的調頁。這個子集就稱為該進程在時刻t的工作集。頁式虛擬存儲管理系統應該時時力圖積累并保持進程的工作集在主存中。3.8.2請求分頁式虛擬存儲管理技術顯然，工作集的大小是隨著時間變化著的，因此分配給作業的物理塊數應該也是可變的，這里稱其為頁框數M，它恰好能夠容納當時的工作集。3.8.2請求分頁式虛擬存儲管理技術①裝入作業的第一頁，讓作業運行。②發生頁面故障時，增大M，調入新頁，積累工作集。③當缺頁率趨于穩定（比如小于某個閾值）時，便完成了這一時段的工作集積累。此時主存的頁面便是這一時段的工作集。④此后若繼續有頁面故障，不再增加頁框數，而要先淘汰某個頁后再調入。同時不斷地計算缺頁率。3.8.2請求分頁式虛擬存儲管理技術⑤當頁面故障率超過某個閾值時，繼續增大分配的頁框數，以便調整工作集尺寸，積累新的工作集。從以上的敘述可見，請頁式的虛擬存儲方案實現起來是比較復雜的，為了獲得局部性原理支持下的工作集維護，以及由此帶來的諸多好處，需要硬件和軟件共同完成，如圖3-26所示，所幸的是這些工作都是系統完成的。3.8.2請求分頁式虛擬存儲管理技術是否是否是否啟動當前指令提取頁號查頁表完成該指令存在位為1？執行頁面淘汰算法有空閑塊？取輔存中的頁更新頁表報告缺頁中斷處理完成，重啟被中斷的指令更新頁表取下一條指令修改位為1？寫出輔存硬件機制軟件策略圖3-26請頁式虛擬存儲管理下指令的執行過程[例3-6]某虛擬存儲器的用戶空間共有32個頁面，每頁1K，主存16K。假定某時刻系統為用戶的第0、1、2、3頁分配的物理塊號為5、10、4、7。而該用戶作業的長度為6頁，試將十六進制的虛擬地址0A5C、103C、1A5C轉換成物理地址。3.8.2請求分頁式虛擬存儲管理技術分析：由題意可知，作業共6頁，即作業地址空間合法范圍為0x0000~0x1800，并且作業前4頁已經裝入主存，即邏輯地址0x0000~0x1000（16進制）可以按照基本分頁管理地址映射方法計算物理地址。頁大小1K，由10位2進制數表示頁內偏移量，頁數6，由3位2進制數表示。3.8.2請求分頁式虛擬存儲管理技術解答：LA1：0x0A5C(16)=0000101001011100(2)，PA1＝0x125C，過程如圖3-27所示。LA2：邏輯地址0x103C所在頁尚未裝入主存，無法計算。LA3：邏輯地址0x1A5C超出有效的作業地址空間，是非法地址，不計算。3.8.2請求分頁式虛擬存儲管理技術3.8.2請求分頁式虛擬存儲管理技術1315141211109876543210000010100101110010位頁內偏移W3位頁號P頁號塊號051102437作業A的頁表000100100100110010位頁內偏移W6位塊號BLA＝0x0A5CPA=0x125C圖3-27例3-6請頁式虛擬存儲管理地址映射實例模擬請頁式的虛擬存儲管理是在缺頁中斷的驅動之下實現的，因此也可以說它存在一個缺點，就是當要訪問的頁不在主存時去依次執行中斷、處理和恢復工作，對指令的執行是一種延誤，而另外一種基于分頁的虛擬存儲管理——預約式頁式存儲管理方案，則力圖避免這種不足。3.8.2請求分頁式虛擬存儲管理技術預約式與請頁式的區別在于，由系統估計最近的將來作業執行所需的頁面集，將其事先調入，這樣要訪問的頁是永遠在主存中的，只是這種方案實現起來意義不大，因為對未來的估計往往是不準確，反而造成更大的開銷。3.8.2請求分頁式虛擬存儲管理技術2.二級頁表結構對于大型作業，頁表本身也可以按照分頁管理的方式進行存儲。如一個支持32位尋址的系統，頁尺寸為4KB，那么4GB的作業由220頁組成，每個頁表項占4B，則該作業頁表需要222B即4MB的空間，可分210頁，在虛存管理技術下，這個龐大的頁表不必要完全裝入主存，而是像作業一樣，將頁表自身也劃分為頁后，每一頁映射到一個頁表項上，則只需212（4KB），1頁的空間，如圖3-28所示。3.8.2請求分頁式虛擬存儲管理技術3.8.2請求分頁式虛擬存儲管理技術……一級頁表4KB二級頁表4MB作業4GB圖3-28二級頁表結構另外還有兩種虛擬存儲管理方案：請求分段和段頁式虛存。請求分段是在基本的分段式存儲管理的基礎上的改進，利用局部性原理，工作集的維護是以作業的邏輯段為單位的。段頁式虛存管理則是請頁式和請段式的綜合，是現代操作系統中使用比較廣泛的方案。3.8.2請求分頁式虛擬存儲管理技術3.9.1先進先出置換法3.9.2最近最久未使用置換法3.9.3最近未使用置換法3.9.4最佳置換法3.9常用的頁面置換算法頁面置換，也稱頁面淘汰，是指在頁式虛擬存儲系統中發生缺頁中斷時，在不增加分配給作業的頁框數的情況下，選擇由新調入頁去替換掉已經裝入主存中的哪一頁的操作，它也是實現虛擬存儲管理的關鍵環節之一，本節介紹主要的置換算法，為比較不同算法的性能，引入缺頁率作為指標（見公式3-5所示）。

（式3-5）

3.9常用的頁面置換算法先進先出（FIFO）的置換方法即選擇最先進入主存的頁面進行置換（或稱淘汰）。實現時，系統將作業的常駐頁面集維護成先進先出的隊列，新調入的頁加在隊尾，需要置換時取隊頭頁面。3.9.1先進先出置換法[例3-7]作業A在某一時間段內的頁面訪問序列為P（2，3，2，1，5，2，4，5，3，2，5，2），頁框數為3，則頁面訪問過程中缺頁率、頁面工作集隊列更新過程如圖3-29所示。3.9.1先進先出置換法3.9.1先進先出置換法23215245325223315244335222315224435231552243×××××××××缺頁次數9總頁面訪問次數12缺頁率為75%圖3-29FIFO置換算法示例先進先出的置換方法實現起來簡便，但是它的推論是最先進入主存的頁面不會再用到，沒有考慮到有些“先期”進入的頁面可能在將來還會頻繁使用到，因此它存在一個嚴重的缺陷就是有的情況下，增加分配給作業的頁框數，缺頁率反而更大，稱為先進先出異常（比萊迪異常Belady’sanomaly）。3.9.1先進先出置換法[例3-8]某作業頁面訪問序列為P（4，3，2，1，4，3，5，4，3，2，1，5），當頁框數為3和4時，頁面集隊列的變化過程和缺頁次數如圖3-30所示。3.9.1先進先出置換法3.9.1先進先出置換法頁框數為3時：432143543215432143555211432143335224321444355×××××××××缺頁次數9總頁面訪問次數12缺頁率為75%

3.9.1先進先出置換法頁框數為4時：432143543215432111543215432221543214333215432444321543××××××××××從本例可以看出，在頁框數為3時，作業A的缺頁率為75%，而頁框數增加到4時，缺頁率反而變大，為83%，即出現先進先出異常現象。

缺頁次數10總頁面訪問次數12缺頁率為83%圖3-30FIFO置換方法出現的異常最近最久未使用（LRU）置換法是指當有頁面需要被淘汰時，選擇在最久的過去使用過的頁，此時，作業的頁面集被維護為后進先出的棧，新調入頁從棧頂壓入，棧底的頁自動被淘汰。為保證棧底的頁一定是最近最長時間沒被使用的，頁面訪問過程中即使未發生缺頁中斷系統也將調整棧中的頁面順序，以保證最近被使用的頁面在棧頂一側。3.9.2最近最久未使用置換法[例3-9]作業A在某一時間段內的頁面訪問序列為P（2，3，2，1，5，2，4，5，3，2，5，2），頁框數為3，則使用最近最久未使用置換法時頁面訪問過程中缺頁率、頁面工作集更新過程如圖3-31所示。3.9.2最近最久未使用置換法3.9.2最近最久未使用置換法23215245325223215245325223215245325321524533×××××××缺頁次數7總頁面訪問次數12缺頁率為58%圖3-31LRU置換算法示例LRU算法不會出現所謂的先進先出時的異常情況（驗證工作可自行完成），因為此算法置換時推論最近最長時間以來沒被使用的頁面被淘汰，根據局部性原理所說明的集簇傾向，在最近的過去一直被閑置不用的頁通常也是最近的將來最不可能被使用的；但是LRU算法在實現起來開銷要比先進先出大的多。3.9.2最近最久未使用置換法LRU算法獲得了比較好的頁面調度效率，但是它要比FIFO算法復雜且開銷大，最近未使用算法試圖以較小的開銷接近LRU的性能。圖3-32給出了最近未使用算法的示例，該策略也稱為時鐘（Clock）策略，因為頁面集被想像成環狀，關聯的指針在其中順時針轉動。3.9.3最近未使用置換法3.9.3最近未使用置換法...頁8使用位0頁7使用位1頁5使用位1頁1使用位1頁10使用位1頁6使用位0頁12使用位1...頁13使用位1頁7使用位0頁5使用位0頁1使用位1頁10使用位1頁6使用位0頁12使用位1(a)某一時刻發生替換前的狀態(b)發生替換后（8->13）的狀態圖3-32最近未使用（時鐘）算法示意某一時刻，進程A候選頁面集的關聯指針指向主存中的5號頁，當有新頁13要求進入時，當前指針位置的使用位為1則將其置0，指針指向下一位置，下一位置的7號頁使用位也為1則再次置0，再指向下一位置，此時8號頁使用位為0，則將新頁13調入置換8號頁，且13號頁的使用位為1。3.9.3最近未使用置換法[例3-10]某作業的頁面訪問序列為P（2，3，2，1，5，2，4，5，3，2，5，2），通過最近未使用算法獲得的頁面訪問過程中缺頁率、頁面工作集更新過程如圖3-33所示。3.9.3最近未使用置換法3.9.3最近未使用置換法23215245325222225555333333332222222111444455××××××××缺頁次數8總頁面訪問次數12缺頁率為67%圖3-33Clock置換算法示例時鐘算法還有一種改進的方案，即將頁面的使用位U和修改位M同時應用，這樣每個頁面在主存中會有4種狀態：（1）U＝0，M＝0——最近未被訪問，也未被修改；（2）U＝1，M＝0——最近被訪問，但未被修改；（3）U＝0，M＝1——最近未被訪問，但被修改過；（4）U＝1，M＝1——最近被訪問，也被修改過。3.9.3最近未使用置換法此時，時鐘算法可以按下面的步驟執行：①從指針的當前位置開始，掃描候選頁緩沖區。在這次掃描過程中，對U位不做任何修改，選擇遇到的第一個U、M同時為0的頁用于替換。②如果第一步失敗，則重新掃描，查找U＝0、M＝1的頁。選擇遇到的第一個這樣的頁用于替換。在這個過程中，對每個跳過的頁的U位置0。③如果第二步失敗，指針將回到它的最初位置，并且集合中所有頁的使用位均為0。重復第一步，并且，如果有必要，重復第二步。3.9.3最近未使用置換法3.9.3最近未使用置換法頁8U=1,M=1頁15U=1,M=0頁5U=0,M=1頁7U=1,M=0頁22U=1,M=1頁14U=0,M=0頁28U=0,M=0……緩沖區首012345n-1第一個被置換圖3-34增加修改位的時鐘算法在不考慮新裝入頁的情況下，被置換的頁面依次為14，28，5，15，8，7，22。

最佳置換法（OPT）意即獲得最好的頁面置換性能，最佳置換算法在頁面淘汰時選擇主存中永遠不會用到的頁面或者在最久的將來才會用到的頁面，此時的作業頁面集維護為隨機存取的數組，新調入頁直接替換被選中淘汰的頁。3.9.4最佳置換法[例3-11]作業A的頁面訪問序列為P（2，3，2，1，5，2，4，5，3，2，5，2），頁框數為3，使用最佳置換法時頁面訪問過程中缺頁率、頁面工作集更新過程如圖3-35所示。3.9.4最佳置換法3.9.4最佳置換法23215245325222222244444433333333222155555555××××××缺頁次數6總頁面訪問次數12缺頁率為50%圖3-35OPT置換算法示例以上的例3-7、3-9、3-10、3-11是對相同的頁面訪問序列P（2，3，2，1，5，2，4，5，3，2，5，2）采用不同的置換算法，驗證結果會發現，OPT算法的缺頁率是最低的，但問題在于，OPT是一種無法實現的策略，因為要求系統必須知道將來的事件，顯然這是不可能的；因此，OPT算法作為一種標準來衡量其他算法的性能，在相同條件下越接近OPT算法的效率則表示該算法越好3.9.4最佳置換法[例3-12]假設有一系統采用請求分頁的虛擬存儲管理，當有一用戶程序，它訪問其地址空間的字節地址序列為：70、305、215、321、56、140、453、23、187、456、378、401。若主存大小為384B，頁大小為128B，試按FIFO算法和LRU算法，分別計算缺頁率。分析：題中已知的是邏輯地址，故首先要將邏輯地址轉換為邏輯頁號，且已知頁大小為128B，頁框數為3。3.9.4最佳置換法解答：1.由作業地址空間的地址序列，計算相對應的頁號，即“頁號＝邏輯地址/頁尺寸”，得字節訪問序列依次對應于頁號：0、2、1、2、0、1、3、0、1、