第4章-存儲管理

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

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

由它和操作系統(tǒng)來共享內(nèi)存。當它運行

結(jié)束后，操作系統(tǒng)再裝入一個新的程序

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

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

分區(qū)大小可以相等，也可以不等。一個

進程占用一個分區(qū)。特點：適合于多道程序系統(tǒng)和分時系統(tǒng)，

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

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

少量的大分區(qū)；當進程到來時，根據(jù)它的大小，把它放置到相應

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

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

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

能裝入該分區(qū)的

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

選擇能裝入該分

區(qū)的最大進程。19如何實現(xiàn)固定分區(qū)存儲管理？

數(shù)據(jù)結(jié)構(gòu)、分配、回收。20固定分區(qū)的實現(xiàn)數(shù)據(jù)結(jié)構(gòu)：設置內(nèi)存分配表內(nèi)存分配：先放入輸入隊列，然后采用

最先匹配法、最佳匹配法

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

所謂內(nèi)碎片，即進程所占用分區(qū)之內(nèi)的未

被利用的空間（再小的進程都要占用一整個分區(qū)）。分區(qū)的總數(shù)固定，限制了并發(fā)執(zhí)行的程序

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

數(shù)、位置和大小都是隨進程

的進出而動態(tài)變化的，非常

靈活，避免了在固定分區(qū)中

因分區(qū)大小不當所造成的內(nèi)

碎片，提高了內(nèi)存利用率。有外碎片，即各個占用分區(qū)

之間難以利用的空閑分區(qū)

（通常是小空閑分區(qū)）；使得內(nèi)存的分配、回收和管

理更為復雜。27如何實現(xiàn)可變分區(qū)的存儲管理技術(shù)？內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)；內(nèi)存的分配算法內(nèi)存的回收方法碎片問題4.2.3可變分區(qū)的實現(xiàn)281.分區(qū)鏈表系統(tǒng)維護一個有序的分區(qū)鏈表，來跟蹤記錄每一個內(nèi)存分區(qū)的情況，包括該分區(qū)的狀態(tài)（已分配或空閑）

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

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

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

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

不連續(xù)的很小的空閑分區(qū)（外碎片）。當一個新進

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

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

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

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

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

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

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

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

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

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

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

ldrR1,[200]

addR2,R1,3

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

ldrR1,[200]

addR2,R1,3

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

被裝入內(nèi)存時，直接對指令代碼進行修改，

一次性實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以

后不再轉(zhuǎn)換。在可執(zhí)行文件中，需列出各個需要重定位

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

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

ldrR1,[200]

addR2,R1,3

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

ldrR1,[1200]

addR2,R1,3

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

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

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

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

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

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

寄存器的內(nèi)容，形成實際的物理地址，然后按該地址去執(zhí)行。45裝入分區(qū)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為了防止一個用戶程序去訪問其他用戶程序的內(nèi)存分區(qū)，保護操作系統(tǒng)免受用戶程序的破壞，須進行存儲保護。如何實現(xiàn)？能否與動態(tài)地址映射集成在一起？2.存儲保護47最簡單的做法：在基地址寄存器的基礎上，再增加一個限長寄存器，記錄分區(qū)的長度。這兩者在一起，就定義了進程所在的分區(qū)（寄存器的值存放在哪？）進程B進程A操作系統(tǒng)100K100K基地址寄存器限長寄存器邏輯地址必須

小于限長寄存

器的值。硬件

保護這兩個寄

存器，用戶程

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

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

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

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

邏輯

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

256個物理

頁面，可以

用字長為32

位的8個字

來構(gòu)成位示

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

裝入到內(nèi)存的各個物理頁面當中，在這種情

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

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

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

E4K

F10K

C10K

B8K

D12K作業(yè)X的調(diào)用結(jié)構(gòu)作業(yè)X的常駐區(qū)

A（8K）覆蓋區(qū)0（10K）覆蓋區(qū)1（12K）BCDEF覆蓋技術(shù)（續(xù)1）

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

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

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

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

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

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

設有虛地址訪問序列2362H、1565H、25A5H，請問：（1）依次訪問上述三個虛地址，各需多少時間？給出計算過程。（2）基于上述訪問序列，虛地址1565H的物理地址是多少？請說明理由。141（1）根據(jù)頁式管理的工作原理，應先考慮頁面大小，以便將頁號和頁內(nèi)位移分解出來。頁面大小為4KB，即212，則得到頁內(nèi)位移占虛地址的低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時，產(chǎn)生缺頁中斷，合法駐留集為2，必須從頁表中淘汰一個頁面，根據(jù)題目的置換算法，應淘汰0號頁面，因此1565H的對應頁框號為101H。由此可得1565H的物理地址為101565H。1454.5.5虛擬頁式的設計問題1.頁面的分配策略如何來確定駐留集的大??？固定分配與可變分配。固定分配策略：駐留集大小固定。例如：各進程平均分配，或根據(jù)程序大小按比例分配等。采用局部頁面置換的方式，當發(fā)生一個缺頁中斷時，被置換的頁面局限在本進程內(nèi)部。缺點：分配的物理頁面數(shù)難以確定。進程在運行過程中，工作集的大小可能會不斷地變化，若分配的頁面數(shù)太少，則發(fā)生抖動；若分配的頁面數(shù)太多，則浪費內(nèi)存資源。146可變分配策略：駐留集大小可變。例如：每個進程在剛開始運行的時候，先根據(jù)程序大小給它分配一定數(shù)目的物理頁面，然后在進程運行過程中，再動態(tài)地調(diào)整駐留集的大小?？刹捎萌猪撁嬷脫Q的方式，當發(fā)生一個缺頁中斷時，被置換的頁面可以是在其它進程當中，各個并發(fā)進程競爭地使用物理頁面。優(yōu)缺點：性能較好，但增加了系統(tǒng)開銷。具體實現(xiàn)：可以使用缺頁率算法(PFF,pagefaultfrequency)來動態(tài)調(diào)整駐留集的大小。147缺頁率缺頁率表示“缺頁次數(shù)/內(nèi)存訪問次數(shù)”(比率)或“缺頁的平均時間間隔的倒數(shù)”。影響缺頁率的因素：頁面置換算法分配給進程的物理頁面數(shù)目頁面本身的大小程序的編制方法148若進程的缺頁率過高，則分配更多的物理頁面；若進

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

個進程的缺頁率保持在一個合理的范圍內(nèi)。缺頁率算法149程序的編寫方法對缺頁率的影響：例子：頁面大小為4K，分配給每個進程的物理頁面數(shù)為1。在一個進程中，定義了如下的二維數(shù)組intA[1024][1024]，該數(shù)組按行存放在內(nèi)存，每一行放在一個頁面中。程序編制方法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組共發(fā)生了1024×1024次缺頁中斷解法2：1，1，1，………，2，2，………，3，3，…….共發(fā)生了1024次缺頁中斷1512.頁面大小頁面大小的選擇需要平衡各種相互競爭