1、v 5.1 虛擬存儲器概述虛擬存儲器概述v 5.2 請求分頁存儲管理方式請求分頁存儲管理方式v 5.3 頁面置換算法頁面置換算法v 5.4 “抖動抖動”與工作集與工作集v 5.5 請求分段存儲管理方式請求分段存儲管理方式1v 物理存儲器的結構是個一維的線性空間，容量是有限的。物理存儲器的結構是個一維的線性空間，容量是有限的。v 物理存儲器管理方式的特征：物理存儲器管理方式的特征： 一次性一次性：程序要全部一次性裝入內存后才能運行：程序要全部一次性裝入內存后才能運行 駐留性駐留性：程序裝入內存后，一直駐留在內存中，直至作：程序裝入內存后，一直駐留在內存中，直至作業(yè)運行結速。業(yè)運行結速。v 用戶程

2、序的大小，可能比內存容量小，也可能比內存容用戶程序的大小，可能比內存容量小，也可能比內存容量大，有時候要大得多。量大，有時候要大得多。v 如何將大于物理內存容量的用戶程序裝入運行？這就是如何將大于物理內存容量的用戶程序裝入運行？這就是提出研究虛擬存儲器的原因，或稱為虛擬存儲技術發(fā)展提出研究虛擬存儲器的原因，或稱為虛擬存儲技術發(fā)展的原動力。的原動力。2 指程序在執(zhí)行過程中的一個較短時間內，所執(zhí)行指程序在執(zhí)行過程中的一個較短時間內，所執(zhí)行的指令地址或操作數(shù)地址分別局限于一定的存儲區(qū)域的指令地址或操作數(shù)地址分別局限于一定的存儲區(qū)域中。又可細分時間局部性和空間局部性。中。又可細分時間局部性和空間局部性

3、。v時間局限性時間局限性 一條指令被執(zhí)行了，則在不久的將來它可能再被一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行。執(zhí)行。v空間局限性空間局限性 若某一存儲單元被使用，則在一定時間內，與該若某一存儲單元被使用，則在一定時間內，與該存儲單元相鄰的單元可能被使用。存儲單元相鄰的單元可能被使用。3v 虛擬存儲器虛擬存儲器 是采用是采用請求調入功能請求調入功能和和置換功能置換功能，把內存與外存把內存與外存有機的結合起來使用，從邏輯上有機的結合起來使用，從邏輯上為用戶提供一個比物為用戶提供一個比物理主存容量大得多的，可尋址的一種理主存容量大得多的，可尋址的一種“主存儲器主存儲器” ，這就是虛存。這就是虛

4、存。v 虛擬存儲器的容量虛擬存儲器的容量 是有限的；是有限的； 由內存容量和外存容量之和所決定，受計算機的由內存容量和外存容量之和所決定，受計算機的地址結構限制。地址結構限制。 以以CPU時間和外存空間換取昂貴內存空間，這是時間和外存空間換取昂貴內存空間，這是操作系統(tǒng)中的資源轉換技術。操作系統(tǒng)中的資源轉換技術。4v常規(guī)存儲器的特征常規(guī)存儲器的特征 一次性一次性 駐留性駐留性v虛擬存儲器特征虛擬存儲器特征 多次性多次性 對換性對換性 虛擬性虛擬性5v實現(xiàn)虛擬存儲器必須解決好以下有關問題實現(xiàn)虛擬存儲器必須解決好以下有關問題 主存輔存統(tǒng)一管理問題主存輔存統(tǒng)一管理問題 邏輯地址到物理地址的轉換問題邏輯

5、地址到物理地址的轉換問題 部分裝入和部分對換問題部分裝入和部分對換問題v虛擬存儲管理主要采用以下技術實現(xiàn)虛擬存儲管理主要采用以下技術實現(xiàn) 請求分頁存儲管理請求分頁存儲管理 請求分段存儲管理請求分段存儲管理6v 基本原理基本原理 在進程開始運行之前，不是裝入全部頁面，而是裝在進程開始運行之前，不是裝入全部頁面，而是裝入部分頁面，之后根據進程運行的需要，動態(tài)裝入其它入部分頁面，之后根據進程運行的需要，動態(tài)裝入其它頁面。頁面。 當內存空間已滿，而又需要裝入新的頁面時，則根當內存空間已滿，而又需要裝入新的頁面時，則根據某種算法淘汰某個頁面，以便裝入新的頁面。據某種算法淘汰某個頁面，以便裝入新的頁面。

6、例例v 怎樣才能發(fā)現(xiàn)頁面不在內存中呢怎樣才能發(fā)現(xiàn)頁面不在內存中呢? ?怎樣處理這種情況呢怎樣處理這種情況呢? ? 采用的辦法是：擴充頁表的內容，增加駐留標志位采用的辦法是：擴充頁表的內容，增加駐留標志位和頁面輔存的地址等信息。通過產生缺頁中斷來處理和頁面輔存的地址等信息。通過產生缺頁中斷來處理. .7前進前進82022-5-8151413121110987654321060K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K28K-

7、32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K虛地址空間虛地址空間物理地址空間物理地址空間 虛頁虛頁頁框頁框返回返回v 頁號、內存塊號、狀態(tài)位、外存地址、訪問位、修改位頁號、內存塊號、狀態(tài)位、外存地址、訪問位、修改位 狀態(tài)位（中斷位）：表示該頁是在內存還是在外存狀態(tài)位（中斷位）：表示該頁是在內存還是在外存 訪問位：根據訪問位來決定淘汰哪頁（由不同的算法訪問位：根據訪問位來決定淘汰哪頁（由不同的算法決定）決定） 修改位：查看此頁是否在內存中被修改過修改位：查看此頁是否在內存中被修改過9頁號頁號狀態(tài)位狀態(tài)位輔存地址輔存地址訪問位訪問位 修改位修

8、改位物理塊號物理塊號101 11 10 00 01 11 11 10 00 00 00 00 00 01 11 1狀態(tài)位狀態(tài)位 在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內存，則產生在內存，則產生缺頁中斷缺頁中斷。操作系統(tǒng)接到此中斷信號。操作系統(tǒng)接到此中斷信號后，就調出缺頁中斷處理程序，根據頁表中給出的外后，就調出缺頁中斷處理程序，根據頁表中給出的外存地址，準備將該頁調入內存。存地址，準備將該頁調入內存。此時應將缺頁的進程掛起（調頁完成喚醒）此時應將缺頁的進程掛起（調頁完成喚醒）如果內存中有空閑塊，則分配一個塊，將要調入的如果內存中有空閑塊，則分

9、配一個塊，將要調入的頁裝入該塊，并修改頁表中相應頁表項目的駐留位頁裝入該塊，并修改頁表中相應頁表項目的駐留位及相應的內存塊號及相應的內存塊號若此時內存中沒有空閑塊，則要淘汰某頁（若被淘若此時內存中沒有空閑塊，則要淘汰某頁（若被淘汰頁在內存期間被修改過，則要將其寫回外存）汰頁在內存期間被修改過，則要將其寫回外存）11 缺頁中斷和一般中斷都是中斷。缺頁中斷和一般中斷都是中斷。v 相同點：相同點： 保護現(xiàn)場保護現(xiàn)場 、中斷處理、中斷處理、 恢復現(xiàn)場恢復現(xiàn)場v 不同點：不同點： 一般中斷是一般中斷是一條指令完成后一條指令完成后檢查和處理中斷信號，缺頁檢查和處理中斷信號，缺頁中斷是中斷是一條指令執(zhí)行時一

10、條指令執(zhí)行時產生和處理中斷信號。產生和處理中斷信號。 缺頁中斷缺頁中斷返回到該指令的開始返回到該指令的開始重新執(zhí)行該指令，而一般重新執(zhí)行該指令，而一般中斷返回到該指令的中斷返回到該指令的下一條指令下一條指令執(zhí)行。執(zhí)行。 一條指令執(zhí)行時可能產生多個缺頁中斷。如指令可能訪一條指令執(zhí)行時可能產生多個缺頁中斷。如指令可能訪問多個內存地址，這些地址在不同的頁中。問多個內存地址，這些地址在不同的頁中。 12v 內存分配策略分為兩種內存分配策略分為兩種 進程保持頁框數(shù)固定不變，稱進程保持頁框數(shù)固定不變，稱固定分配固定分配; ;進程分得進程分得的頁框數(shù)可變，稱的頁框數(shù)可變，稱可變分配可變分配。v 固定分配固定

11、分配 進程創(chuàng)建時，根據進程類型和程序員的要求決定進程創(chuàng)建時，根據進程類型和程序員的要求決定頁框數(shù)，只要有一個缺頁中斷產生，進程就會有一頁頁框數(shù)，只要有一個缺頁中斷產生，進程就會有一頁被替換。即使內存中有空閑的物理塊，也不分配給該被替換。即使內存中有空閑的物理塊，也不分配給該進程。進程。v 可變分配可變分配 先為每個進程分配一定數(shù)目的物理塊，進程執(zhí)行先為每個進程分配一定數(shù)目的物理塊，進程執(zhí)行的某階段缺頁率較高，說明目前局部性較差，系統(tǒng)可的某階段缺頁率較高，說明目前局部性較差，系統(tǒng)可多分些頁框以降低缺頁率，反之說明進程目前局部性多分些頁框以降低缺頁率，反之說明進程目前局部性較好，可減少分給進程的頁

12、框數(shù)。較好，可減少分給進程的頁框數(shù)。13v 固定分配缺少靈活性，而可變分配的性能會更好些，固定分配缺少靈活性，而可變分配的性能會更好些，被許多操作系統(tǒng)采用。被許多操作系統(tǒng)采用。v 采用可變分配策略的困難在于操作系統(tǒng)要經常監(jiān)視采用可變分配策略的困難在于操作系統(tǒng)要經常監(jiān)視活動進程的行為和進程缺頁中斷率的情況，會增加活動進程的行為和進程缺頁中斷率的情況，會增加系統(tǒng)的開銷。系統(tǒng)的開銷。14v全局置換全局置換 如果頁面置換算法的作用范圍是整個系統(tǒng)，稱全局如果頁面置換算法的作用范圍是整個系統(tǒng)，稱全局頁面置換算法，它可以在運行進程間動態(tài)地分配頁頁面置換算法，它可以在運行進程間動態(tài)地分配頁框。被置換的頁可以是

13、內存中任一進程的頁?？颉１恢脫Q的頁可以是內存中任一進程的頁。v局部置換局部置換 如果頁面置換算法的作用范圍局限于本進程，稱為如果頁面置換算法的作用范圍局限于本進程，稱為局部頁面置換算法，它實際上需要為每個進程分配局部頁面置換算法，它實際上需要為每個進程分配固定的頁框。始終保持分配給該進程的物理塊數(shù)不固定的頁框。始終保持分配給該進程的物理塊數(shù)不變。變。15v 固定分配局部置換策略固定分配局部置換策略 進程分得的頁框數(shù)不變，發(fā)生缺頁中斷，只能從進程分得的頁框數(shù)不變，發(fā)生缺頁中斷，只能從進程的頁面中選頁置換，保證進程的頁框總數(shù)不變。進程的頁面中選頁置換，保證進程的頁框總數(shù)不變。v 策略難點策略難點

14、應給每個進程分配多少頁框應給每個進程分配多少頁框? ? 給少了，缺頁中斷率給少了，缺頁中斷率高；給多了，使內存中能同時執(zhí)行的進程數(shù)減少，進高；給多了，使內存中能同時執(zhí)行的進程數(shù)減少，進而造成處理器和其它設備空閑。而造成處理器和其它設備空閑。v 采用固定分配算法，系統(tǒng)把頁框分配給進程，采用采用固定分配算法，系統(tǒng)把頁框分配給進程，采用 平均分配平均分配 按比例分配按比例分配 優(yōu)先權分配優(yōu)先權分配16v 先每個進程分配一定數(shù)目頁框，先每個進程分配一定數(shù)目頁框，osos保留若干空閑頁保留若干空閑頁框，進程發(fā)生缺頁中斷時，從系統(tǒng)空閑頁框中選一框，進程發(fā)生缺頁中斷時，從系統(tǒng)空閑頁框中選一個給進程，這樣產生

15、缺頁中斷進程的內存空間會逐個給進程，這樣產生缺頁中斷進程的內存空間會逐漸增大，有助于減少系統(tǒng)的缺頁中斷次數(shù)。漸增大，有助于減少系統(tǒng)的缺頁中斷次數(shù)。v 系統(tǒng)擁有的空閑頁框耗盡時系統(tǒng)擁有的空閑頁框耗盡時 ，會從內存中選擇一，會從內存中選擇一頁淘汰，該頁可以是內存中任一進程的頁面，這樣頁淘汰，該頁可以是內存中任一進程的頁面，這樣又會使那個進程的頁框數(shù)減少，缺頁中斷率上升。又會使那個進程的頁框數(shù)減少，缺頁中斷率上升。17 其實現(xiàn)要點如下其實現(xiàn)要點如下: :v 新進程裝入主存時，根據應用類型、程序要求，新進程裝入主存時，根據應用類型、程序要求，分配給一定數(shù)目頁框。分配給一定數(shù)目頁框。v 產生缺頁中斷時，

16、從該進程駐留集中選一個頁面產生缺頁中斷時，從該進程駐留集中選一個頁面替換。替換。v 不時重新評價進程的分配，增加或減少分配給進不時重新評價進程的分配，增加或減少分配給進程的頁框以改善系統(tǒng)性能。程的頁框以改善系統(tǒng)性能。18v何時頁面裝入主存何時頁面裝入主存 請求調頁策略請求調頁策略: :需要訪問程序和數(shù)據時，才把所在頁面裝需要訪問程序和數(shù)據時，才把所在頁面裝入主存。缺點是每次只調入一頁，處理缺頁中斷和調頁入主存。缺點是每次只調入一頁，處理缺頁中斷和調頁的系統(tǒng)開銷較大，增加磁盤的系統(tǒng)開銷較大，增加磁盤I/OI/O啟動頻率。啟動頻率。 預調頁策略預調頁策略: :系統(tǒng)系統(tǒng)預測預測進程將要使用的頁面，使

17、用前預先進程將要使用的頁面，使用前預先調入主存，每次調入若干頁面，而不是僅調一頁。缺點調入主存，每次調入若干頁面，而不是僅調一頁。缺點是如果調入的一批頁面中多數(shù)未被使用，則效率就很低是如果調入的一批頁面中多數(shù)未被使用，則效率就很低了，可見預調頁要建立在預測的基礎上。了，可見預調頁要建立在預測的基礎上。19v 缺頁中斷率缺頁中斷率 假定作業(yè)假定作業(yè)p p共計共計n n頁，系統(tǒng)分配給它的主存塊只有頁，系統(tǒng)分配給它的主存塊只有m m塊（塊（mnmn）。如果作業(yè)）。如果作業(yè)p p在運行中成功的訪問次數(shù)在運行中成功的訪問次數(shù)為為s s， 不成功的訪問次數(shù)為不成功的訪問次數(shù)為F F，則總的訪問次數(shù)為：，則

18、總的訪問次數(shù)為： A = S + FA = S + F 又定義：又定義：f = F / Af = F / A，稱，稱f f為缺頁中斷率。為缺頁中斷率。v 影響缺頁中斷率影響缺頁中斷率f f的因素有：的因素有： (1)(1)主存物理塊數(shù)主存物理塊數(shù) (2)(2)頁面大小頁面大小 (3)(3)程序的編制方法程序的編制方法 (4)(4)頁面置換算法頁面置換算法20 程序要將程序要將128128的數(shù)組置的數(shù)組置“0”。分給的主存只一塊，頁。分給的主存只一塊，頁面尺寸為每頁面尺寸為每頁128個字，數(shù)組中的元素每行存放在一頁中。若程個字，數(shù)組中的元素每行存放在一頁中。若程序如下：序如下： Var A: a

19、rray1.128 of array 1.128 of integer; for j := 1 to 128 do for i := 1 to 128 do Aij:=0 總共產生（總共產生（128*1281）次缺頁中斷。）次缺頁中斷。 如果重新編制程序如下：如果重新編制程序如下： Var A: array1.128 of array1.128 of integer; for i := 1 to128 do for j:= 1 to 128 do Aij := 0 總共產生（總共產生（1281）次缺頁中斷。）次缺頁中斷。21 當要索取一頁面并送入到全滿的內存中時，必當要索取一頁面并送入到全滿的

20、內存中時，必須把已在內存中的某一頁淘汰掉。用來選擇淘汰哪須把已在內存中的某一頁淘汰掉。用來選擇淘汰哪一頁的規(guī)則叫做置換算法。一頁的規(guī)則叫做置換算法。v最佳置換算法（最佳置換算法（OPT）v先進先出頁面置換算法（先進先出頁面置換算法（FIFO）v最近最久未使用算法（最近最久未使用算法（LRU）22 基本思想：淘汰以后不再需要的或最遠的將來才會基本思想：淘汰以后不再需要的或最遠的將來才會用到的頁面?？捎脕碜鳛楹饬扛鞣N具體算法的標準。用到的頁面?？捎脕碜鳛楹饬扛鞣N具體算法的標準。 【例例】采用固定分配局部置換策略，某程序在內存采用固定分配局部置換策略，某程序在內存中分配三個塊，訪問頁的走向為中分配三

21、個塊，訪問頁的走向為4，3，2，1，4，3，5，4，3，2，1，5，計算缺頁次數(shù)和，計算缺頁次數(shù)和缺頁中斷率缺頁中斷率，假設開，假設開始時所有頁均不在內存。始時所有頁均不在內存。OPT 4 3 2 1 4 3 5 4 3 2 1 5塊塊1 4 4 4 4 4 4 4 4 4 2 1 1塊塊2 3 3 3 3 3 3 3 3 3 3 3塊塊3 2 1 1 1 5 5 5 5 5 5 x x x x x x x 共缺頁中斷共缺頁中斷7次次缺頁中斷率缺頁中斷率=7/12=58.33%23 基本思想：淘汰最先調入主存的那一頁，或者說在主基本思想：淘汰最先調入主存的那一頁，或者說在主存中駐留時間最長的那

22、一頁（常駐的除外）。存中駐留時間最長的那一頁（常駐的除外）。 【例例】采用固定分配局部置換策略，某程序在內存中采用固定分配局部置換策略，某程序在內存中分配三個塊，訪問頁的走向為分配三個塊，訪問頁的走向為4，3，2，1，4，3，5，4，3，2，1，5，計算缺頁次數(shù)，假設開始時所有頁均不在，計算缺頁次數(shù)，假設開始時所有頁均不在內存。內存。FIFO 4 3 2 1 4 3 5 4 3 2 1 5塊塊1 4 4 4 1 1 1 5 5 5 5 5 5塊塊2 3 3 3 4 4 4 4 4 2 2 2塊塊3 2 2 2 3 3 3 3 3 1 1 x x x x x x x x x 共缺頁中斷共缺頁中斷

23、9次，缺頁中斷率次，缺頁中斷率=9/12=75%24這種算法實現(xiàn)簡單，但會淘汰經常使用的頁面這種算法實現(xiàn)簡單，但會淘汰經常使用的頁面 基本思想：根據程序局部性原理，那些剛被使用過的頁面，可能基本思想：根據程序局部性原理，那些剛被使用過的頁面，可能馬上還要被使用，而在較長時間里未被使用的頁面，可能不會馬上使馬上還要被使用，而在較長時間里未被使用的頁面，可能不會馬上使用到。用到。當需要淘汰某一頁時，算法選擇離當前時間最近的一段時間內當需要淘汰某一頁時，算法選擇離當前時間最近的一段時間內最久沒有使用過的頁先淘汰。最久沒有使用過的頁先淘汰。LRU 4 3 2 1 4 3 5 4 3 2 1 5塊塊1 4 4 4 1 1 1 5 5 5 2 2 2塊塊2 3 3 3 4 4 4 4 4 4 1 1塊塊3 2 2 2 3 3 3 3 3 3 5 x x x x x x x x x x共缺頁中斷共缺頁中斷10次次缺頁中斷率缺頁中斷率=10/12=83.33%25v基本原理基本原理 分段式虛擬存儲系統(tǒng)把作業(yè)的所有分段的副本分段式虛擬存儲系統(tǒng)把作業(yè)的所有分段的副本都存放