1第四章諶衛軍清華大學操作系統2第四章存儲管理單道程序存儲管理分區存儲管理頁式和段式存儲管理覆蓋技術與交換技術虛擬存儲技術3即使是簡單的、老的存儲管理方案仍然有必要掌握。有些老的概念仍然有用使用何種存儲管理方案取決于硬件平臺有些方案需要硬件支持；手持設備和嵌入式系統等新的硬件平臺可能只有基本的硬件支持。4理想中的存儲器：更大、更快、更便宜的非易失性存儲器。實際中的存儲器：存儲器層次結構（本圖摘自AndrewS.Tanenbaum：“ModernOperatingSystems”）實際中的存儲器：存儲管理？5我們主要考察內存（MainMemory）的管理。64.1單道程序存儲管理內存分為兩個區域：系統區，用戶區。

每次把一個應用程序裝入到用戶區運行，

由它和操作系統來共享內存。當它運行

結束后，操作系統再裝入一個新的程序

把它覆蓋；優點：簡單、開銷小，易于管理；適合于單用戶、單任務的OS。7BIOS（本圖摘自AndrewS.Tanenbaum：“ModernOperatingSystems”）三種實現方式單道程序存儲管理的缺點？？8每次只能運行一個程序內存資源的使用效率不高程序較小時，會浪費大量的內存空間OS的保護應用程序的bug會破壞OS地址空間有限即為物理內存的大小9如何實現多道存儲管理，即在內存中同時有多個進程運行，有哪些問題需要考慮？10內存空間的管理整個內存區域如何劃分？用什么數據結構來管理內存？如何在有限的內存空間中容納盡可能多的進程？內存的分配新進程到達時，如何給它分配內存？內存的回收進程運行結束時，如何回收其內存？11地址重定位程序員不知道當他的程序被執行時，將會被放在內存的什么位置；當一個程序正在執行時，可能被交換到磁盤上，后來再返回內存時，可能存放在不同的位置；對內存的訪問必須轉換為實際的物理內存地址。12內存保護一個進程不能未經許可去訪問其他進程或OS的內存地址；內存共享允許多個進程訪問相同的一段內存空間；最好允許每個進程訪問一個程序的同一份拷貝，而不是每個進程都有自己獨立的一份拷貝。13邏輯組織程序的編寫是以模塊為單位；每個模塊的保護級別可能是不同的（只讀、只可執行、可讀寫等）；模塊的共享。物理組織分配給一個程序（包括其數據）的內存空間可能不夠用；磁盤存儲器更便宜、容量更大、且永久保存。14Now，如何實現多道存儲管理？內存的分配；內存的回收；內存的管理（數據結構）。154.2分區存儲管理內存分為兩大區域：系統區，用戶區。

又把用戶區劃分為若干分區(partition)，

分區大小可以相等，也可以不等。一個

進程占用一個分區。特點：適合于多道程序系統和分時系統，

支持多個程序并發執行；164.2.1固定分區存儲管理各個用戶分區的個數、位置和大小一旦確定以后，就固定不變。為了滿足不同程序的存儲需要，各分區的大小可相等，也可不等。分區大小相等：只適合于多個相同程序的并發執

行（處理多個類型相同的對象）；分區大小不等：多個小分區、適量的中等分區、

少量的大分區；當進程到來時，根據它的大小，把它放置到相應

的輸入隊列當中，等待合適的空閑分區。兩種實

現方式：多個輸入隊列和單個輸入隊列。17多個輸入隊列分區4分區3分區2分區1操作系統700K400K100K0200K800K對于每一個用戶分區，都有一個輸入隊列。當一個新的進程到來時，把它加入到某個輸入隊

列當中，該輸入隊列所對應的分區，是能夠裝下該進程的最小分區。缺點：可能出現小分區的輸入隊列是滿的，而大分區的輸入隊列卻空著（如分區1和分區3的的情形），從而造成資源的浪費。180K…18單個輸入隊列分區4分區3分區2分區1操作系統700K400K100K0200K800K對于所有的用戶分區，只有一個統一的輸入隊列。當一個新進程到來時，把它加入到該輸入隊列當中，然后當某個分區空閑時：離隊首最近的、

能裝入該分區的

進程被選中；搜索整個隊列，

選擇能裝入該分

區的最大進程。19如何實現固定分區存儲管理？

數據結構、分配、回收。20固定分區的實現數據結構：設置內存分配表內存分配：先放入輸入隊列，然后采用

最先匹配法、最佳匹配法

等算法。內存回收：簡單分區號起始地址長度狀態進程名21固定分區的缺點：內存利用率不高，內碎片造成很大浪費。

所謂內碎片，即進程所占用分區之內的未

被利用的空間（再小的進程都要占用一整個分區）。分區的總數固定，限制了并發執行的程序

個數，不夠靈活。進程的保護（應用程序可能破壞OS和其他應用程序）固定分區的優點：易于實現，開銷小。22地址空間的大小有限：不能超過物理內存的大小。如何提高內存的利用效率？如何確定分區的大小？分區太小怎么辦？分區太大怎么辦（內碎片）？為此，人們又提出了可變分區（動態分區）的存儲管理技術。234.2.2可變分區存儲管理分區不是預先劃分好的固定區域，而是動態創建的。在裝入一個程序時，根據它的需求和內存空間的使用情況來決定是否分配。具體來說，系統生成后，操作系統會占用內存的一部分（一般在內存地址低端），其余空間為一個完整的大空閑區。當一個程序要求裝入內存運行時，系統從這個空閑區中劃分一塊分配給它，當程序完成后釋放所占用的存儲區。隨著一系列的內存分配和回收，原來的一整塊大空閑區就形成了若干占用區和空閑區相間的布局。24操作系統128K01024K128K空閑區896K操作系統128K01024K128K空閑區576K進程1320K448K25操作系統128K01024K128K空閑區352K進程1320K448K進程2224K672K操作系統128K01024K128K空閑區64K進程1320K448K進程2224K672K進程3288K960K空閑區224K250K？26操作系統128K01024K128K空閑區64K進程1320K448K進程4128K672K進程3288K960K576K空閑區96K空閑區320K可變分區的特點：在可變分區當中，分區的個

數、位置和大小都是隨進程

的進出而動態變化的，非常

靈活，避免了在固定分區中

因分區大小不當所造成的內

碎片，提高了內存利用率。有外碎片，即各個占用分區

之間難以利用的空閑分區

（通常是小空閑分區）；使得內存的分配、回收和管

理更為復雜。27如何實現可變分區的存儲管理技術？內存管理的數據結構；內存的分配算法內存的回收方法碎片問題4.2.3可變分區的實現281.分區鏈表系統維護一個有序的分區鏈表，來跟蹤記錄每一個內存分區的情況，包括該分區的狀態（已分配或空閑）

起始地址、長度等信息。ABCDE058141820262932占05空53占86占144空182占206占263空293X空閑起始長度占用292.分區分配算法分區分配算法：當一個新的進程來到時，需為它尋找某個空閑分區，其大小必須大于或等于該進程的要求。若是大于要求，則將該分區分割成兩個分區，其中一個分區為要求的大小并標記為“占用”，而另一個分區為余下部分并標記為“空閑”。分區的先后次序通常是從內存低端到高端。分區分配算法主要有：最先匹配法、下次匹配法、最佳匹配法、最壞匹配法。30最先匹配法

(first-fit)：假設新進程對內存大小的要求為M，那么從分區鏈表的首結點開始，將每一個“空閑”結點的長度與M進行比較，看是否大于或等于它，直到找到第一個符合要求的結點。然后把它所對應的空閑分區分割為二個小分區，一個用于裝入該進程，另一個仍然空閑。與之相對應，把該結點也一分為二，并修改相應內容。查找的結點很少，因而速度快；算法的實質是盡可能利用低地址部分的空閑區，而盡量地保證高地址部分的大空閑區，使其不被分割成小的區，這樣當以后有大的進程到來時，有足夠大的空閑區來滿足它。31下次匹配法

(next-fit)：與最先匹配法的思路是相似的，只不過每一次當它找到一個合適的結點（分區）時，就把當前的位置記錄下來。然后等下一次新進程到來的時候，就從這個位置開始繼續往下找（到鏈表結尾時再回到開頭），直到找到符合要求的第一個分區。而不是象最先匹配法那樣，每次都是從鏈表的首結點開始找。查找的結點很少，因而速度快；該算法使空閑分區分布得更均勻，但較大的空閑分區不易保留。從性能上略遜于最先匹配法。32最佳匹配法

(best-fit)：將申請內存的進程裝入到與其大小最接近的空閑分區當中。算法的性能最差，最大缺點是分割后剩余的空閑分區將會很小，直至無法使用，從而造成浪費（與固定分區是不同的）。最壞匹配法(worst-fit)：每次分配時，總是將最大的空閑區切去一部分分配給請求者，其依據是當一個很大的空閑區被切割了一部分后可能仍是一個較大的空閑區，從而避免了空閑區越分越小的問題。這種算法基本不留下小的空閑分區，但較大的空閑分區也不被保留。3316K16K16KWorstFit地址低端地址高端16K新進程343.分區回收算法分區回收算法：當一個進程運行結束，釋放它所占用的分區后，需要將相鄰的幾個空閑分區合并為一個大的空閑分區。具體來說，可分以下四種情況：在分區回收后，可以很方便地更新分區鏈表。35占05占53占86(a)進程A進程X進程B空空閑區50占35占68空(b)進程A進程X空閑區50占95空進程A空閑區50空35占68空(d)空閑區進程X空閑區140空空閑區(c)略…364.碎片問題經過一段時間的分配與回收后，內存中存在著很多

不連續的很小的空閑分區（外碎片）。當一個新進

程到來時，這些小的空閑區都不足以滿足分配要求，

但其總和滿足分配要求。這就是（外）碎片問題。內存緊縮（Compaction）：把所有的進程盡可能

地往地址低端移動，相應的，那些空閑的小分區就

會往地址的高端移動，從而形成一個大的空閑區。所有進程的移動需要大量的CPU時間；如何解決程序移動后，地址的重定位問題？374.2.5內存中的程序執行進程執行時的內存分區布局棧動態堆空間(malloc)數據代碼低地址高地址PCSP38變量的存儲與作用域/*全局變量，固定地址，其他源文件可見*/intglobal_static;/*靜態全局變量，固定地址，但只在本文件中可見*/staticintfile_static;/*函數參數：位于棧幀當中，動態創建，動態釋放*/intfoo(intauto_param) //代碼{/*靜態局部變量，固定地址，只在本函數中可見*/staticintfunc_static;/*普通局部變量，位于棧幀當中，只在本函數可見*/intauto_i,auto_a[10];/*動態申請的內存空間，位于堆當中*/double*auto_d=malloc(sizeof(double)*5);returnauto_i;}394.2.5重定位和存儲保護1.地址映射（重定位）1）物理地址也叫內存地址、絕對地址，實地址；把內存分成很多個大小相等的存儲單元，每個

單元給一個編號，這個編號稱為物理地址；物理地址可以直接尋址；物理地址的集合稱為物理地址空間（內存地址

空間），它是一個一維的線性空間。402）邏輯地址也叫相對地址，虛地址；用戶程序經過匯編或編譯后形成目標代碼，目

標代碼通常采用相對地址的形式，其首地址為

0，其余指令中的地址都是相對首地址來編址；不能用邏輯地址在內存中讀取信息。3）地址映射為了保證CPU執行指令時可正確訪問存儲單元，

需要將用戶程序中的邏輯地址轉換為運行時由

機器直接尋址的物理地址，這一過程稱為地址

映射。41intx,y;x=5;y=x+3;源程序編譯鏈接裝入分區0100200300......str5,[200]

ldrR1,[200]

addR2,R1,3

strR2,[204]邏輯地址空間204xy1000......110012001300物理地址空間str5,[200]

ldrR1,[200]

addR2,R1,3

strR2,[204]1204xy有無問題？42為了保證CPU執行指令時可正確訪問存儲單元，在裝入程序時必須進行地址映射，將程序中的邏輯地址轉換為物理地址。這主要有兩種方式：靜態地址映射（靜態重定位）：當用戶程序

被裝入內存時，直接對指令代碼進行修改，

一次性實現邏輯地址到物理地址的轉換，以

后不再轉換。在可執行文件中，需列出各個需要重定位

的地址單元的位置。在裝入時，由一個裝

入程序（加載程序）來完成；實現簡單，不需要硬件的支持；程序裝入內存后不能移動。43裝入分區0100200300......str5,[200]

ldrR1,[200]

addR2,R1,3

strR2,[204]邏輯地址空間204xy1000......110012001300物理地址空間str5,[1200]

ldrR1,[1200]

addR2,R1,3

strR2,[1204]1204xy44動態地址映射（動態重定位）：當用戶程序被裝

入內存時，不對指令代碼做任何修改。而是在程

序運行過程中，當需要訪問內存單元時再來進行

地址轉換（即在逐條執行指令時完成轉換）。為提高效率，此工作一般由硬件地址映射機

制來完成，通常的做法是設置一個基地址寄

存器（重定位寄存器），并把進程所在分區的起始地址裝入到該寄存器當中；在程序運行過程中，當需要訪問內存單元時,硬件就自動地將其中的相對地址加上基地址

寄存器的內容，形成實際的物理地址，然后按該地址去執行。45裝入分區0100200300......str5,[200]

ldrR1,[200]

addR2,R1,3

strR2,[204]邏輯地址空間204xy1000......110012001300物理地址空間str5,[200]

ldrR1,[200]

addR2,R1,3

strR2,[204]1204xy+基地址寄存器相對地址10002001.基地址寄存器

在哪？2.何時填入1000？46為了防止一個用戶程序去訪問其他用戶程序的內存分區，保護操作系統免受用戶程序的破壞，須進行存儲保護。如何實現？能否與動態地址映射集成在一起？2.存儲保護47最簡單的做法：在基地址寄存器的基礎上，再增加一個限長寄存器，記錄分區的長度。這兩者在一起，就定義了進程所在的分區（寄存器的值存放在哪？）進程B進程A操作系統100K100K基地址寄存器限長寄存器邏輯地址必須

小于限長寄存

器的值。硬件

保護這兩個寄

存器，用戶程

序不能修改。0100K200K300K48CPUMMU內存磁盤控制器總線CPU組件存儲管

理單元CPU發送邏輯地址給MMUMMU發送物理地址給內存動態地址映射494.3頁式和段式存儲管理頁式存儲管理段式存儲管理頁式管理與段式管理的比較段頁式存儲管理504.3.1頁式存儲管理分區存儲管理方案的一個特性是連續性，這將會導致碎片問題（內碎片和外碎片）。為有效地解決這些問題，人們又提出了頁式存儲管理方案，其基本出發點是打破存儲分配的連續性，使得一個程序的邏輯地址空間可以分布在若干個離散的內存塊上，從而達到充分利用內存，提高內存利用率的目的。511.基本原理把物理內存劃分為許多個固定大小的內存塊，稱

為物理頁面，或頁框（pageframe）；把邏輯地址空間劃分為大小相同的塊，稱為邏輯

頁面，或簡稱頁面（page）；頁面大小為2n，一般在512字節到8K字節之間；當一個用戶程序裝入內存時，以頁面為單位進行分配。若要運行一個大小為n個頁面的程序，需要有n個空閑的物理頁面把它裝入，這些頁面不必是連續的。生活中的例子…52進程3第0頁進程2第2頁進程1第1頁進程1第0頁進程2第1頁進程2第0頁操作系統操作系統0K1K2K3K4K5K6K7K8K9K10K0K1K2K進程1地址空間進程2地址空間0K1K2K3K0K1K進程3地址空間內存53用于存儲管理的數據結構是什么？當一個進程到來時，如何給它分配內存？當一個進程運行結束，釋放它所占用的內存空間后，如何回收內存？當一個進程被加載到內存以后，它如何正確運行（地址重定位）？頁式存儲管理要解決如下問題：542.數據結構頁表：系統為每一個進程都建立了一個頁表，頁表給出了邏輯頁面號和具體內存塊號（物理頁面號）之間的對應關系。邏輯頁號內存塊號頁表01n-1如何實現頁表？55（本圖摘自Silberschatz,GalvinandGagne：“OperatingSystemConcepts”）

邏輯

地址空間頁表物理內存物理頁面號56物理頁面表：在系統中設立一張物理頁面表，用來描述內存空間當中，各個物理頁面的分配使用狀況。具體實現：位示圖，空閑頁面鏈表。0310/10/10/10/10/1017……空閑頁數……位示圖內存中共有

256個物理

頁面，可以

用字長為32

位的8個字

來構成位示

圖。573.內存的分配與回收內存的分配與回收算法與物理頁面表的具體實現方法有關。這里以位示圖為例。內存的分配：計算一個進程所需要的頁面數N，并查看位示圖，看是否還有N個空閑頁面；若有，則申請一個頁表，其長度為N，并把頁表的起始地址填入PCB；分配N個空閑的物理頁面，將其編號填入頁表；修改位示圖（0→1，空閑頁面數－N）58內存的回收：當一個進程運行結束，釋放它所占用的內存空間后，需要對這些物理頁面進行回收。對于每一個物理頁面，根據它的編號計算出它在位示圖當中的相應位置，并將相應位的值從1改成0；修改位示圖中的空閑頁面數：加上N。594.地址映射為什么要進行地址映射？一個進程的各個連續的邏輯頁面，被分散地

裝入到內存的各個物理頁面當中，在這種情

形下，怎樣才能保證程序能夠正確地運行？能否采用靜態地址映射方法？能否采用動態地址映射方法？如何實現？60對于給定的邏輯地址，找到邏輯頁面號和頁內偏移地址；查找頁表，找到相應的物理頁面號；計算最終的物理地址。61邏輯地址的劃分把邏輯地址劃分為兩部分：邏輯頁面號和頁內偏移地址。這種劃分是由系統自動完成的，對用戶是透明的。由于頁面的大小一般為2的整數次冪，因此，地址的高位部分即為頁號，低位部分即為頁內偏移地址。例如，頁面大小為4KB。頁號頁內地址62邏輯地址為十六進制的形式63邏輯地址為十進制的形式計算方法： 頁號＝虛地址/頁大小 位移量＝虛地址%頁大小例如：假設頁面大小為2KB，計算邏輯地址7145和3412的邏輯頁面號和頁內偏移地址。頁號：3412/2048＝1頁內偏移：3412%2048＝1364頁號：7145/2048＝3頁內偏移：7145%2048＝1001Why?64頁表保存在內存當中（用戶/內核空間?）;設置一個頁表基地址寄存器（tablebaseregister，PTBR），用來指向頁表的起始地址；設置一個頁表長度寄存器（tablelengthregister，PTLR），用來指示頁表的大小。頁表的具體實現硬件寄存器位于什么地方？其內容何時更新？誰更新？如何更新？65頁式地址映射疊加1.需訪問幾次內存？2.頁表頁表？66頁式地址映射舉例頁號頁內偏移量67在現有的方案中，每一次訪問內存（數據/指令）時，都要做兩次訪問內存的工作。這樣，降低了存取速度，將會影響整個系統的使用效率。為縮短頁表的查找時間，可以采用一種特殊的快速查找硬件：TLB(TranslationLookasideBuffer)或稱associativememory,用來存放那些最常用的頁表項。如何加快頁表的查詢速度？68帶有TLB的頁式地址映射（本圖摘自Silberschatz,GalvinandGagne：“OperatingSystemConcepts”）先后為什么管用？695.優缺點優點：沒有外碎片，內碎片的大小不超過頁面的大小；一個程序不必連續存放；便于管理；缺點：程序必須全部裝入內存；系統必須為每個進程維護一張頁表。704.3.2段式存儲管理 Why段式存儲管理？頁式存儲管理（和分區存儲管理）只有一個邏輯地址空間，即一維的線性連續空間，從0到某個最大的邏輯地址。但是從程序員或系統管理的角度來說，一個程序是由一組模塊（片段）所組成的，每個片段是一個邏輯單元，如：主程序、全局變量、棧、庫函數等。71存儲保護：代碼段：一條條指令組成，只讀，可執行，無需寫回磁盤；數據段：全局變量，可修改，可讀寫，需寫回磁盤；棧：行參、局部變量、CPU寄存器、返回地址，可讀寫，是否可執行？存儲共享：在多個進程之間，共享代碼和數據。721.基本原理對于程序當中的每一個邏輯單元，設立一個完全獨立的地址空間，稱為“段”。在每個段的內部，是一維的線性連續地址，從0一直到某個最大的地址。每個段的大小一般是不相等的，它所包含的內容也是不一樣的；對于物理內存來說，采用可變分區（動態分區）的管理方法；當一個程序需要裝入內存時，以段為單位進行分配，把每一個段裝入到一個內存分區當中，這些內存分區不必是連續的。731423物理內存空間用戶空間1324子函數主函數棧符號表0n742.具體實現在段式存儲管理中，用戶空間的地址為二元地址：(段號，段內偏移)。實現方式：(1)地址高端為段號、低端為偏移；(2)指令中顯式地給出段號和段內偏移。段表：系統為每一個進程都建立了一個段表，它給出了進程當中的每一個段與它所對應的內存分區之間的映射關系。75所對應內存分區的起始地址段長度1400100063004004300400段號012段表比較頁表76段表的具體實現：段表保存在內存當中；設置一個段表基地址寄存器（Segment-tablebaseregister，STBR），用來指向內存當中段表的起始地址；設置一個段表長度寄存器（Segment-tablelengthregister，STLR），用來指示段表的大小，即程序當中的段的個數；77段式地址映射PhysicalAddress與頁式地址映射的區別？78段式地址映射舉例79邏輯地址32位：16位段號＋16位段內偏移;整數為32位；地址以16進制描述。段式存儲管理舉例16位16位段號 段內偏移80段基地址長度保護01000018C0只讀1119003FF只讀211D001FF讀－寫300禁止訪問411F001000讀－寫500禁止訪問600禁止訪問713000FFF讀－寫mainSin240pushX[10108]360mov4(sp),r2244callSin364pushr2248…366…488ret段表代碼段8182X在哪？（Sin函數的參數）棧指針的當前地址是70FF0，物理地址是多少？第一條指令在哪？PushX指令：將SP減4，然后存儲X的值，那么X被存儲在什么地方？CallSin指令：(1)當前PC值入棧；(2)在PC內裝入目標PC值。哪個值被壓入棧了？新的棧指針的值是多少？新的PC值是多少？“mov4+(sp),r2”的功能是什么？833.優缺點優點：程序通過分段來劃分多個模塊，每個模塊可以分別編寫和編譯，可以針對不同類型的段采取不同的保護，可以按段為單位來進行共享；一個程序不必連續存放，沒有內碎片。缺點：程序必須全部裝入內存、外碎片等。84854.3.3頁式管理與段式管理的比較分頁與分段的出發點不同頁式：為減少碎片，提高內存的使用效率，因此把內存劃分為許多個固定大小的物理頁面。相應的，把邏輯地址空間也劃分為大小相同的邏輯頁面；段式：為了實現程序當中的各個邏輯單元的獨立性，便于它們的共享、保護和修改，從而為每一個邏輯單元設立一個單獨的“段”。相應的，在物理內存的分配和回收上，采用可變分區的存儲管理方法。86程序員對所采用的存儲管理技術的關注：頁式：對于程序員而言，頁式存儲管理完全是透明的，不必關心。對邏輯地址空間的分頁，是由系統自動完成的。程序員甚至不知道分頁的發生。段式：程序員知道各個邏輯單元的存在，因此可以對它們進行不同的處理。87從邏輯地址的表示來看：頁式：邏輯地址是一維的線性連續地址，各模塊在鏈接時必須組織成同一個地址空間；段式：邏輯地址是二維的，即段號和段內的偏移地址，各個模塊在鏈接時可以為每個段組織一個地址空間。從退化形式來看：頁式：如果頁面比較大，能裝下整個程序，那么就退化為一種的方法；段式：如果段的個數為1，那么就退化為一種

的方法。固定分區可變分區884.3.4段頁式存儲管理段式存儲和頁式存儲各有特點：段式存儲管理為用戶提供了一個二維的邏輯地址空間，可以滿足程序和信息的邏輯分段要求，反映了程序的邏輯結構，有利于段的共享、保護和動態增長；頁式存儲管理的特征是等分內存，它有效地克服了碎片問題，提高了內存的利用率。為了保持頁式在存儲管理上的優點和段式在邏輯上的優點，人們又提出了段頁式存儲管理技術。89基本思想：先把程序劃分為段，然后在段內分頁。邏輯地址：段號段內地址頁號頁內地址內存劃分：按頁式存儲管理方案內存分配：以頁面為單位進行分配90具體實現：段表：記錄了每一段的頁表起始地址和頁表長度，而不是該段所在內存分區的起始地址。頁表：記錄了邏輯頁面號與物理頁面號之間的對應關系。（每一段有一個，一個程序可能有多個頁表）需要的硬件支持：段表基地址寄存器

（STBR）和段表長度寄存器（STLR）。91段頁式地址映射（本圖摘自Silberschatz,GalvinandGagne：“OperatingSystemConcepts”）覆蓋（overlay）和交換技術（swaping）分區存儲管理頁式段頁式段頁式都是將整個程序全部裝入內存。這樣在多道程序的環境下可能出現內存不夠用的情況。1.程序太大，超過了空閑的內存容量，使用覆蓋技術。只需把需要的指令和數據保存在內存，其他的在外存。2.若程序的個數太多，他們的總和超過了內存容量，使用交換技術，把暫時不能執行的程序送到外存。3.如果箱子啊有限容量的內存裝入盡可能多的程序，而且每個程序又8K

E4K

F10K

C10K

B8K

D12K作業X的調用結構作業X的常駐區

A（8K）覆蓋區0（10K）覆蓋區1（12K）BCDEF覆蓋技術（續1）

A請計算采用覆蓋技術后，作業X的運行節省了多少內存空間？覆蓋技術的缺點：1.需要程序員手工的把大程序劃分成功能模塊并確定其覆蓋關系，即哪些模塊存在調用關系。2.覆蓋模塊從外存裝入內存，以時間延長來換取空間。交換技術如果有多個進程并發運行，可以將一些暫時不能運行的進程送到外存，從而使新進程可以裝入。交換的單位是進程的整個內存空間。交換技術多用于多道程序系統或者分時系統，和分區存儲管理一起使用。交換技術的原理換出：把整個進程的地址空間保存到外存的一個交換區。換入：將外存中某個進程的地址空間讀入到內存。交換技術的幾個問題交換時機：何時交換？內存不足，或有不足危險。外存中交換區的大小：必須足夠大，能存放所有用戶進程的所有內存影響的復制件。程序換入時的重定位：靜態地址映射必須放在原來的位置動態地址映射無需。

覆蓋和交換技術的比較覆蓋只能發生在互相沒有調用關系的模塊之間。交換是以進程為單位，無需用戶給出各個模塊之間的邏輯覆蓋結構。即：交換發生在進城之間，而覆蓋發生在同一個進程內部。虛擬存儲技術覆蓋和交換都是擴充內存的方法，但是都有缺點覆蓋：需將整個程序劃分模塊，并確定覆蓋關系。增加程序員的負擔。交換：以進程為單位交換，需要把進程的整個地址空間都換進換出，增加了處理器的開銷，浪費cpu時間。系統設計者不希望這種開銷。有沒有一種技術，即可解決程序員的煩惱，又解決系統設計者的煩惱。虛擬存儲技術。虛擬存儲技術像覆蓋技術那樣，把程序的一部分放入內存，但它想做的更好，將這個過程由系統自動完成。另一方面像交換技術那樣，實現進程在內存與外存間的交換，但是它想做的更好，部分而不是整個地址空間。1014.5虛擬存儲技術4.5.1程序的局部性原理局部性原理(principleoflocality)：程序在執行過程中的一個較短時期，所執行的指令地址和指令的操作數地址，分別局限于一定區域。表現為：時間局部性：一條指令的一次執行和下次執行，一個數據的一次訪問和下次訪問都集中在一個較短時期內；空間局部性：當前指令和鄰近的幾條指令，當前訪問的數據和鄰近的幾個數據都集中在一個較小區域內。forexample…102局部性原理的具體表現：程序在執行時，大部分是順序執行的指令，少部分是轉移和過程調用指令；程序中存在相當多的循環結構，它們由少量指令組成，而被多次執行；程序中存在很多對一定數據結構的操作，如數組操作，往往局限在較小范圍內。103程序的局部性原理表明，從理論上來說，虛擬存儲技術是能夠實現的，而且在實現了以后應該是能夠取得一個滿意的效果的。成功案例：TLB、Cache。1044.5.2虛擬頁式存儲管理大部分虛擬存儲系統都采用虛擬頁式存儲管理技術，即在頁式存儲管理的基礎上，增加請求調頁和頁面置換功能。基本思路：當一個用戶程序要調入內存運行時，不是將該程序的所有頁面都裝入內存，而是只裝入部分的頁面（0個或多個），就可啟動程序運行。在運行的過程中，如果發現要執行的指令或要訪問數據不在內存，則發出缺頁中斷請求，系統在處理這個中斷時，將外存中相應的頁面調入內存，使得該程序能繼續運行。105當內存空間不夠用時，需要把頁面保存在磁盤上（backingstore，后備存儲）；內存物理頁面稱為pageframe，磁盤上的頁面稱為后備頁面（backingframe）；目的：提供一種錯覺，內存的容量好像和磁盤容量一樣大，且速度和內存一樣快（理想狀態）。106MMU磁盤邏輯地址空間物理地址空間107虛擬頁式管理需要解決以下問題：如何發現執行的代碼或訪問的數據不在內存；代碼或數據什么時候調入內存，調入策略；當一些頁調入內存時，內存沒有空閑內存時，將淘汰哪些頁，淘汰策略。1081.頁表表項每個頁表項包含以下信息：邏輯頁號、物理頁號、駐留位、保護位、修改位、訪問位。物理頁號駐留位保護位修改位訪問位邏輯頁號i109駐留位（有效位）：表示該頁是在內存還是在外存。如果該位等于1，表示該頁位于內存當中，即該頁表項是有效的，可以使用；如果該位等于0，表示該頁當前還在外存當中，如果訪問該頁表項，將導致缺頁中斷；保護位：表示允許對該頁做何種類型的訪問，如只讀、可讀寫、可執行等；修改位：表明此頁在內存中是否被修改過。當系統回收該物理頁面時，根據此位來決定是否把它的內容寫回外存；訪問位：如果該頁面被訪問過（包括讀操作或寫操作），則設置此位。用于頁面置換算法。110XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K邏輯地址空間物理地址空間物理頁面頁表16位的邏輯地址，邏輯地址空間64K。物理內存只有

32K。頁面大小為4K。151413121110987654321076543210駐留位為0駐留位為1MOVREG,[0]MOVREG,[32780][32786]缺頁中斷1112.缺頁中斷在地址映射過程中，如果所要訪問的邏輯頁面p不在內存，則產生缺頁中斷(pagefault)。中斷處理過程：如果在內存中有空閑的物理頁面，則分配一頁，設為f，然后轉第4步；否則轉第2步；采用某種頁面置換算法，選擇一個將被替換的物理頁面f，它所對應的邏輯頁面為p。如果該頁在內存期間被修改過，則需把它寫回外存；對p所對應的頁表項進行修改，把駐留位置為0；將需要訪問的頁面p裝入到物理頁面f當中（進程被阻塞），并修改p所對應的頁表項的內容，把駐留位置為1，把物理頁面號設置為f；重新運行被中斷的指令（PC不變）。112有空閑頁面嗎？分配一個空閑頁面修改相應的頁表項重新運行被中斷的指令有無否用置換算法選擇一頁把它寫回外存該頁被修改過？是缺頁中斷調入所需頁面缺頁中斷的流程圖113XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K11194501328K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K邏輯地址空間物理地址空間頁表151413121110987654321076543210MOVREG,[32780](32K+12)缺頁中斷置換算法選中物理頁面1把物理頁面1的內容寫回外存調入所需頁面修改相應頁表項的內容8X1114用戶進程感覺不到缺頁中斷的發生（就像進程切換一樣）。addr1,r2,r3mov+(sp),(r2)faultallocpagereadfromdisksetmappingOSUsrprogramresume1154.5.3頁面置換算法功能：當缺頁中斷發生，需要調入新的頁面而內存已滿時，選擇內存當中哪個物理頁面被置換。目標：盡可能地減少頁面的換進換出次數（即缺頁中斷的次數）。具體來說，把未來不再使用的或短期內較少使用的頁面換出。116最優頁面置換算法(OPT,optimal)最近最久未使用算法(LRU,LeastRecentlyUsed)最不常用算法(LFU,LeastFrequentlyUsed)先進先出算法(FIFO)時鐘頁面置換算法(Clock)1171.最優頁面置換算法基本思路：當一個缺頁中斷發生時，對于保存在內存當中的每一個邏輯頁面，計算在它的下一次訪問之前，還需等待多長時間，從中選擇等待時間最長的那個，作為被置換的頁面。這只是一種理想情況，在實際系統中是無法實現的，因為操作系統無從知道每一個頁面要等待多長時間以后才會再次被訪問。可用作其他算法的性能評價的依據（在一個模擬器上運行某個程序，并記錄每次的頁面訪問情況，在第二遍運行時即可使用最優算法）。118OPT123412512345頁0111111111114頁122222222222頁23333333333頁3444455555缺頁XXXXXX進程總共有5個邏輯頁面，在它的運行過程中，對邏輯頁面的訪問順序是：1,2,3,4,1,2,5,1,2,3,4,5。如果在內存中給它分配4個物理頁面，則缺頁情況如下：12次訪問中有缺頁6次。541192.最近最久未使用算法最近最久未使用算法(LeastRecentlyUsed,LRU);基本思路：當一個缺頁中斷發生時，選擇最近最久未使用的那個頁面，并淘汰之。它是對最優頁面置換算法的一個近似，其依據是程序的局部性原理，即在最近一小段時間內，如果某些頁面被頻繁地訪問，那么在將來的一小段時間內，它們還可能會再一次被頻繁地訪問。反之，如果在過去某些頁面長時間未被訪問，那么在將來它們還可能會長時間地得不到訪問。120如何實現LRU算法？可能的實現方法是：系統維護一個頁面鏈表，最近剛剛使用過的頁面作為首結點，最久未使用的頁面作為尾結點。每一次訪問內存時，找到相應的頁面，把它從鏈表中摘下來，再移動到鏈表之首。每次缺頁中斷發生時，淘汰鏈表末尾的頁面。設置一個活動頁面棧，當訪問某頁時，將此頁號壓入棧頂，然后，考察棧內是否有與此頁面相同的頁號，若有則抽出。當需要淘汰一個頁面時，總是選擇棧底的頁面，它就是最久未使用的。在每次內存訪問時，給相應頁面打上時間戳，然后在缺頁中斷時，選擇最老的頁面淘汰出去。121LRU123412512345缺頁鏈首1X鏈首X21鏈尾鏈首X312X312鏈首44231X2415134254211452X2513X3124X4235進程總共有5個邏輯頁面，在它的運行過程中，對邏輯頁面的訪問順序是：1,2,3,4,1,2,5,1,2,3,4,5。如果在內存中給它分配4個物理頁面，則缺頁情況如下：12次訪問中有缺頁8次。1221,2,3,4,1,2,5,1,2,3,4,5111221233123442341134122412554251145122512331234423455123完美的LRU算法并不實用：在每次內存訪問時，都需要去更新該頁面訪問時間（時間戳法）或調整各個頁面的先后順序（鏈表法和棧法），開銷很大；缺乏硬件支持。可行的做法：對LRU算法的近似；在硬件的支持下，使用某種簡單而快速的方法來尋找比較老（而非最老）的頁面。 1243.最不常用算法最不常用算法（LeastFrequentlyUsed,LFU）;基本思路：當一個缺頁中斷發生時，選擇訪問次數最少的那個頁面，并淘汰之。實現方法：對每個頁面設置一個訪問計數器，每當一個頁面被訪問時，該頁面的訪問計數器加1。在發生缺頁中斷時，淘汰計數值最小的那個頁面。LRU和LFU的區別：LRU考察的是多久未訪問,時間越短越好；而LFU考察的是訪問的次數或頻度，訪問次數越多越好。1254.先進先出算法先進先出算法（First-InFirst-Out,FIFO）；基本思路：選擇在內存中駐留時間最長的頁面并淘汰之。具體來說，系統維護著一個鏈表，記錄了所有位于內存當中的邏輯頁面。從鏈表的排列順序來看，鏈首頁面的駐留時間最長，鏈尾頁面的駐留時間最短。當發生一個缺頁中斷時，把鏈首頁面淘汰出局，并把新的頁面添加到鏈表的末尾。性能較差，調出的頁面有可能是經常要訪問的頁面，并且有Belady現象。126Belady現象：在采用FIFO算法時，有時會出現分配的物理頁面數增加，缺頁率反而提高的異常現象；Belady現象的原因：FIFO算法的置換特征與置換算法的目標是不一致的（即替換較少使用的頁面），因此，被它置換出去的頁面并不一定是進程不會訪問的（如1,2,3,1,1,4）。127FIFO123412512345缺頁進程總共有5個邏輯頁面，在它的運行過程中，對邏輯頁面的訪問順序是：1,2,3,4,1,2,5,1,2,3,4,5。如果在內存中給它分配3個物理頁面，則缺頁情況如下：12次訪問中有缺頁9次。鏈首1X鏈首X12鏈尾鏈首X132X243X314X421X152152152X235X543543128FIFO123412512345缺頁如果在內存中給這個進程分配4個物理頁面：鏈首1X鏈首X12鏈尾鏈首X132結論：在12次頁面訪問中，總共缺頁10次（Belady現象）。X243鏈首12431X35422431X4153X5214X1325X2431X35421295.時鐘頁面置換算法時鐘頁面置換算法(Clock)；基本思路（FIFO+跳過訪問過的頁面）：需要用到頁表項當中的訪問位。如果一個頁面被訪問（讀/寫），硬件自動將其訪問位置為1，OS則負責定期清0；把各個頁面組織成環形鏈表（類似鐘表面），把指針指向最老的頁面（最先進來）；當發生一個缺頁中斷時，考察指針所指向的最老頁面，若它的訪問位為0，立即淘汰；若訪問位為1，則把該位置為0，然后指針往下移動一格。如此下去，直到找到被淘汰的頁面，然后把指針移動到它的下一格。130001100110001頁面訪問位頁面置換前000000110001頁面置換后M131什么時候LRU等價于FIFO，舉例？LRU的性能比較好，但是開銷大。FIFO開銷小但是性能差Clock比較折中，不像LRU那樣動態調整順序，只是設置一個訪問位，所以開銷少，并且訪問位是硬件實現。LRU、FIFO和Clock的比較1324.5.4工作集模型前面介紹的各種頁面置換算法，都是基于一個前提,即程序的局部性原理。但是此原理是否成立？若局部性原理不成立，則各種頁面置換算法就沒有區別。例如：若進程對邏輯頁面的訪問順序是1、2、3、4、5、6、7、8、9…，即單調遞增，則在物理頁面數有限的前提下，不管采用何種置換算法，每次的頁面訪問都必然導致缺頁中斷。如果局部性原理是成立的，那么如何來證明它的存在，如何來對它進行定量地分析？133工作集：一個進程當前正在使用的邏輯頁面集合，可以用一個二元函數W(t,)來表示：t是當前的執行時刻；稱為工作集窗口（working-setwindow），即一個定長的頁面訪問窗口；W(t,)＝在當前時刻t之前的窗口當中的所有頁面所組成的集合（隨著t的變化，該集合也在不斷地變化）；|W(t,)|指工作集的大小，即頁面數目。1.工作集134261577775162341234443434441327

如果窗口的長度為10，那么：

W(t1,)={1,2,5,6,7}W(t2,)={3,4}一個例子頁面訪問順序：t1t2135工作集大小的變化：進程開始執行后，隨著訪問新頁面逐步建立較穩定的工作集。當內存訪問的局部性區域的位置大致穩定時，工作集大小也大致穩定；局部性區域的位置改變時，工作集快速擴張和收縮過渡到下一個穩定值。1362.駐留集駐留集是指在當前時刻，進程實際駐留在內存當中的頁面集合。工作集是進程在運行過程中固有的性質，而駐留集取決于系統分配給進程的物理頁面數目，以及所采用的頁面置換算法；如果一個進程的整個工作集都在內存當中，即駐留集工作集，那么進程將很順利地運行，而不會造成太多的缺頁中斷（直到工作集發生劇烈變動，從而過渡到另一個狀態）；當進程駐留集的大小達到某個數目之后，再給它分配更多的物理頁面，缺頁率也不會明顯下降。1373.抖動問題(thrashing)如果分配給一個進程的物理頁面太少，不能包含整個工作集，即駐留集工作集，則進程將會造成很多缺頁中斷，需要頻繁地在內存與外存之間替換頁面，從而使進程的運行速度變得很慢，這種狀態稱為“抖動”(進程總被阻塞，I/O繁忙)。138例題： 請求分頁管理系統中，假設某進程的頁表內容如下表所示。頁號頁框(PageFrame)號有效位0101H11—02254H1139

頁面大小為4KB，一次內存的訪問時間是100ns，一次快表（TLB）的訪問時間是10ns，處理一次缺頁的平均時間為108ns（已含更新TLB和頁表的時間），進程的駐留集大小固定為2，采用最近最少使用置換算法（LRU）和局部淘汰策略。假設①TLB初始為空；②地址轉換時先訪問TLB，若TLB未命中，再訪問頁表（忽略訪問頁表之后的TLB更新時間）；③有效位為0表示頁面不在內存，產生缺頁中斷，缺頁中斷處理后，返回到產生缺頁中斷的指令處重新執行。140

設有虛地址訪問序列2362H、1565H、25A5H，請問：（1）依次訪問上述三個虛地址，各需多少時間？給出計算過程。（2）基于上述訪問序列，虛地址1565H的物理地址是多少？請說明理由。141（1）根據頁式管理的工作原理，應先考慮頁面大小，以便將頁號和頁內位移分解出來。頁面大小為4KB，即212，則得到頁內位移占虛地址的低12位，頁號占剩余高位。可得三個虛地址的頁號P如下：1422362H：P=2，訪問快表10ns，因初始為空，訪問頁表100ns得到頁框號，合成物理地址后訪問主存100ns，共計10ns+100ns+100ns=210ns。1565H：P=1，訪問快表10ns，落空，訪問頁表100ns落空，進行缺頁中斷處理108ns，合成物理地址后訪問主存100ns，10ns+100ns+108ns+10ns+100ns14325A5H：P=2，訪問快表，因第一次訪問已將該頁號放入快表，因此花費10ns便可合成物理地址，訪問主存100ns，共計10ns+100ns=110ns。144（2）當訪問虛地址1565H時，產生缺頁中斷，合法駐留集為2，必須從頁表中淘汰一個頁面，根據題目的置換算法，應淘汰0號頁面，因此1565H的對應頁框號為101H。由此可得1565H的物理地址為101565H。1454.5.5虛擬頁式的設計問題1.頁面的分配策略如何來確定駐留集的大小？固定分配與可變分配。固定分配策略：駐留集大小固定。例如：各進程平均分配，或根據程序大小按比例分配等。采用局部頁面置換的方式，當發生一個缺頁中斷時，被置換的頁面局限在本進程內部。缺點：分配的物理頁面數難以確定。進程在運行過程中，工作集的大小可能會不斷地變化，若分配的頁面數太少，則發生抖動；若分配的頁面數太多，則浪費內存資源。146可變分配策略：駐留集大小可變。例如：每個進程在剛開始運行的時候，先根據程序大小給它分配一定數目的物理頁面，然后在進程運行過程中，再動態地調整駐留集的大小。可采用全局頁面置換的方式，當發生一個缺頁中斷時，被置換的頁面可以是在其它進程當中，各個并發進程競爭地使用物理頁面。優缺點：性能較好，但增加了系統開銷。具體實現：可以使用缺頁率算法(PFF,pagefaultfrequency)來動態調整駐留集的大小。147缺頁率缺頁率表示“缺頁次數/內存訪問次數”(比率)或“缺頁的平均時間間隔的倒數”。影響缺頁率的因素：頁面置換算法分配給進程的物理頁面數目頁面本身的大小程序的編制方法148若進程的缺頁率過高，則分配更多的物理頁面；若進

程的缺頁率過低，則減少它的物理頁面數，力圖使每

個進程的缺頁率保持在一個合理的范圍內。缺頁率算法149程序的編寫方法對缺頁率的影響：例子：頁面大小為4K，分配給每個進程的物理頁面數為1。在一個進程中，定義了如下的二維數組intA[1024][1024]，該數組按行存放在內存，每一行放在一個頁面中。程序編制方法1：for(j=0;j<1024;j++)for(i=0;i<1024;i++)A[i][j]=0;程序編制方法2：for(i=0;i<1024;i++)for(j=0;j<1024;j++)A[i][j]=0;150a0,0a0,1a0,2……..a0,10231a1,0a1,1a1,2……..a1,10232…………….…………….a1023,0a1023,1

…..a1023,10231024訪問頁面的序列為：解法1：1，2，3，………1024，1，2，………，共1024組共發生了1024×1024次缺頁中斷解法2：1，1，1，………，2，2，………，3，3，…….共發生了1024次缺頁中斷1512.頁面大小頁面大小的選擇需要平衡各種相互競爭