第五章 存儲管理課件

第五章存儲管理第五章存儲管理第五章存儲管理提綱5.1存儲管理的功能5.2分區(qū)存儲管理5.3覆蓋與交換技術(shù)5.4頁式管理5.5段式與段頁式管理5.6局部性原理和抖動問題第五章存儲管理存儲器:內(nèi)存（primarysrotage）：本章討論的重點外存（secondarystorage）主要內(nèi)容幾種常用的內(nèi)存管理方法內(nèi)存的分配和釋放算法虛擬存儲器的概念控制主存和外存之間的數(shù)據(jù)流動方法地址變換技術(shù)內(nèi)存數(shù)據(jù)保護與共享技術(shù)第五章存儲管理5.1存儲管理的功能1.存儲管理的功能(1)內(nèi)存的分配與釋放如何分配內(nèi)存，以保證系統(tǒng)及各用戶程序的存儲區(qū)互不沖突；程序運行結(jié)束后歸還占用的內(nèi)存空間。(2)存儲保護與存儲共享保證程序在執(zhí)行過程中不會有意或無意地破壞另一道程序，保證用戶程序不會破壞系統(tǒng)程序；不同作業(yè)之間相同的內(nèi)容(代碼)只在內(nèi)存中裝入一個副本。第五章存儲管理(3)內(nèi)存擴充當用戶作業(yè)所需要的內(nèi)存量超過計算機系統(tǒng)所提供的內(nèi)存容量時，把內(nèi)部存儲器和外部存儲器結(jié)合起來管理，為用戶提供一個容量比實際內(nèi)存大得多的虛擬存儲器。(4)地址重定位完成從相對地址（虛擬地址）到絕對地址（物理地址）的轉(zhuǎn)換。第五章存儲管理物理地址物理存儲器中的位置。虛擬地址編譯鏈接程序把用戶源程序編譯后鏈接到一個以0地址為起始地址的線性地址空間中，每個進程都擁有這樣一個虛擬空間。每條指令或數(shù)據(jù)單元都在這個虛擬空間中擁有確定的地址，把這個地址稱為虛擬地址（virtualaddress）。虛存空間的容量是由計算機的地址結(jié)構(gòu)和尋址方式確定的。例如cpu的有效地址長度為16位，則其尋址范圍為0~64kB第五章存儲管理地址變換第五章存儲管理用戶程序虛擬空間LOADR120ADDR122STORER124210110024202224內(nèi)存物理地址0241000102010221024地址重定位示意LOADR120ADDR122STORER124210110第五章存儲管理2地址重定位靜態(tài)地址重定位（staticaddressrelocation）在虛擬空間程序執(zhí)行之前由裝配程序完成地址映射工作。假定分配程序已分配了一塊首地址為BA的內(nèi)存區(qū)給虛擬空間內(nèi)的程序段，若某條指令或數(shù)據(jù)的虛擬地址為VA，那么，該指令或數(shù)據(jù)對應的內(nèi)存地址為MA，從而完成程序中所有地址部分的修改，以保證CPU的正確執(zhí)行。MA＝BA＋VA第五章存儲管理用戶程序虛擬空間LOADR11020ADDR11022STORER11024210110024202224內(nèi)存物理地址0241000102010221024靜態(tài)地址重定位示意LOADR11020ADDR11022STORER11024210110第五章存儲管理靜態(tài)重定位的優(yōu)點:

不需要硬件支持,程序運行速度快。靜態(tài)重定位的缺點:

（1）靜態(tài)重定位方法將程序一旦裝入內(nèi)存之后就不能再移動。（2）必須占用連續(xù)的內(nèi)存空間，這就難以做到程序和數(shù)據(jù)的共享。第五章存儲管理動態(tài)地址重定位(dynamicaddressrelocation)在程序執(zhí)行過程中，完成地址轉(zhuǎn)換。需要硬件地址變換機構(gòu)完成。需要一個(或多個)基地址寄存器BR和一個(或多個)程序虛擬地址寄存器VR。指令或數(shù)據(jù)的內(nèi)存地址MA與虛地址的關(guān)系為:MA=(BR)+(VR)(BR)與(VR)分別表示寄存器BR與VR中的內(nèi)容。第五章存儲管理動態(tài)地址重定位第五章存儲管理動態(tài)重定位的主要優(yōu)點有:(1)可以對內(nèi)存進行非連續(xù)分配。

(2)動態(tài)重定位提供了實現(xiàn)虛擬存儲器的基礎(chǔ)。

(3)有利于程序段的共享。

(4)程序在內(nèi)存中可以移動。動態(tài)重定位的主要缺點有:(1)進程運行速度慢。

(2)動態(tài)重定位需要硬件支持。第五章存儲管理3內(nèi)外存數(shù)據(jù)傳輸?shù)目刂疲▋?nèi)存擴充）原因：物理內(nèi)存不夠用最基本的控制辦法:用戶程序自己控制覆蓋（以程序段為單位，手動）操作系統(tǒng)控制交換(s)方式（以進程為單位）請求調(diào)入(ondemand)方式（以程序/數(shù)據(jù)段為單位）預調(diào)入(onprefetch)方式（以程序/數(shù)據(jù)段為單位）第五章存儲管理4內(nèi)存的分配與回收主要功能：進程創(chuàng)建時把外存中的數(shù)據(jù)和程序調(diào)入內(nèi)存，安排合適的位置（為進程分配內(nèi)存空間）。進程執(zhí)行結(jié)束后及時收回該進程所占用的內(nèi)存資源，以便給其他進程分配空間。第五章存儲管理考慮因素：（1）分配結(jié)構(gòu)：登記內(nèi)存使用情況，共分配程序使用的表格與鏈表。例如，內(nèi)存空閑區(qū)表，空閑區(qū)隊列。（2）放置策略：確定調(diào)入內(nèi)存的程序和數(shù)據(jù)在內(nèi)存中的位置。選擇內(nèi)存空閑區(qū)的策略。第五章存儲管理（3）交換策略：在需要將某個程序段和數(shù)據(jù)段調(diào)入內(nèi)存時，如果內(nèi)存中沒有足夠的空閑區(qū)，由交換策略來確定把內(nèi)存中的哪些程序段和數(shù)據(jù)段調(diào)出內(nèi)存，以便騰出足夠的空間。（4）調(diào)入策略：外存中的程序段和數(shù)據(jù)段什么時間按正么樣的控制方式進入內(nèi)存。（5）回收策略：包括回收的時機和回收的內(nèi)存空閑區(qū)和已經(jīng)存在的空閑區(qū)的調(diào)整。第五章存儲管理5內(nèi)存信息的共享與保護原因：多道程序設(shè)計環(huán)境內(nèi)存中有系統(tǒng)進程以及多個用戶的進程要限制各進程只在自己的存儲區(qū)活動各進程不能對別的進程的產(chǎn)生干擾和破壞常用的內(nèi)存信息保護方法：硬件法——上下界保護法軟件法——保護鍵法軟硬件結(jié)合——界限寄存器與CPU狀態(tài)結(jié)合第五章存儲管理上下界保護法思想：為每個進程設(shè)置一對上下界寄存器上界寄存器——被保護程序和數(shù)據(jù)段的起始地址下界寄存器——被保護程序和數(shù)據(jù)段的終止地址檢查經(jīng)過重定位的內(nèi)存地址是否在上下屆寄存器所規(guī)定的范圍內(nèi)在規(guī)定的范圍內(nèi)，則訪問是合法的否則是非法的，并產(chǎn)生訪址越界中斷第五章存儲管理上、下界寄存器保護法第五章存儲管理保護鍵法思想：為每一個被保護存儲塊分配一個單獨的保護鍵在程序狀態(tài)字中則設(shè)置相應的保護鍵開關(guān)字段對不同的進程賦予不同的開關(guān)代碼和與被保護的存儲塊中的保護鍵匹配保護鍵可設(shè)置成對讀寫同時保護的或只對讀，寫進行單項保護的第五章存儲管理保護鍵保護法PSW對A塊：不能讀、不能寫對B塊：能讀、能寫對C塊：能讀、不能寫

每個存儲塊設(shè)置4位的存儲鍵、1位取保護位；每個作業(yè)進入系統(tǒng)時分配唯一的鍵號（1～15）；作業(yè)占用哪個存儲塊，該存儲塊的存儲鍵置為該作業(yè)號。第五章存儲管理界限寄存器與CPU的用戶態(tài)或核心態(tài)工作方式相結(jié)合的保護方式思想；用戶態(tài)進程只能訪問那些在界限寄存器所規(guī)定范圍內(nèi)的內(nèi)存部分核心態(tài)進程則可以訪問整個內(nèi)存地址空間UNIX系統(tǒng)就是采用的這種內(nèi)存保護方式第五章存儲管理5.2分區(qū)管理基本原理把內(nèi)存劃分成若干個大小不等的區(qū)域操作系統(tǒng)占用一個區(qū)域其余區(qū)域由各并發(fā)進程共享為每個進程劃分一塊適當大小的存儲區(qū)，連續(xù)存儲進程的程序和數(shù)據(jù)。按分區(qū)的時機，可分為：固定分區(qū)動態(tài)分區(qū)第五章存儲管理1.固定分區(qū)法思想把內(nèi)存區(qū)固定地劃分為若干個大小不等的區(qū)域。劃分的原則由系統(tǒng)操作員或操作系統(tǒng)決定。分區(qū)一旦劃分結(jié)束，在整個執(zhí)行過程中每個分區(qū)的長度和內(nèi)存的總分區(qū)個數(shù)將保持不變。所需數(shù)據(jù)結(jié)構(gòu)——分區(qū)說明表說明各分區(qū)號、分區(qū)大小、起始地址和是否是空閑區(qū)(分區(qū)狀態(tài))內(nèi)存的分配釋放、存儲保護以及地址變換第五章存儲管理固定分區(qū)法第五章存儲管理缺點浪費現(xiàn)象：即使是小作業(yè)也要占據(jù)大分區(qū)第五章存儲管理2.動態(tài)分區(qū)法思想在系統(tǒng)初啟時，除操作系統(tǒng)中常駐內(nèi)存之外，只有一個空閑分區(qū)。隨后，分配程序?qū)⒃搮^(qū)依次劃分給調(diào)度選中的進程在進程執(zhí)行前并不建立分區(qū)分區(qū)的建立在進程的處理過程中進行分區(qū)大小可隨進程對內(nèi)存的要求而改變優(yōu)點改變了固定分區(qū)法中那種即使是小作業(yè)也要占據(jù)大分區(qū)的浪費現(xiàn)象，從而提高了內(nèi)存的利用率第五章存儲管理內(nèi)存初始分配情況第五章存儲管理內(nèi)存分配變化過程第五章存儲管理所需的數(shù)據(jù)結(jié)構(gòu)分區(qū)說明表可用分區(qū)表每個表目記錄一個空閑區(qū)（區(qū)號、長度和起始地址）需額外內(nèi)存或可用分區(qū)自由鏈利用每個內(nèi)存空閑區(qū)的頭幾個單元存放本空閑區(qū)的大小及下個空閑區(qū)的起始地址，從而把所有的空閑區(qū)鏈接起來。系統(tǒng)再設(shè)置一自由鏈首指針讓其指向第一個空閑區(qū)不需額外內(nèi)存內(nèi)存資源請求表每個表目描述請求內(nèi)存資源的進程號以及所請求的內(nèi)存大小第五章存儲管理可用表、自由鏈及請求表第五章存儲管理3分區(qū)的分配與回收固定分區(qū)分配當用戶程序要裝入執(zhí)行時，通過請求表提出內(nèi)存分配要求和所要求的內(nèi)存空間大小。存儲管理程序根據(jù)請求表查詢分區(qū)說明表，從中找出一個滿足要求的空閑分區(qū)，并將其分配給申請者?；厥债斶M程執(zhí)行完畢，不再需要內(nèi)存資源時，管理程序?qū)姆謪^(qū)狀態(tài)置為未使用即可。第五章存儲管理固定分區(qū)法第五章存儲管理固定分區(qū)分配算法第五章存儲管理動態(tài)分區(qū)主要解決三個問題:(1)對于請求表中的要求內(nèi)存長度，從可用表或自由鏈中尋找出合適的空閑區(qū)分配程序。(2)分配空閑區(qū)之后，更新可用表或自由鏈。(3)進程或作業(yè)釋放內(nèi)存資源時，和相鄰的空閑區(qū)進行鏈接合并，更新可用表或自由鏈。第五章存儲管理分配的三種常用方法:最先適應法(firstfitalgorithm)最佳適應法(bestfitalgorithm)最壞適應法(worstfitalgoriathm)第五章存儲管理(1)最先適應法可用表或自由鏈按起始地址遞增的次序排列。一旦找到大于或等于所要求內(nèi)存長度的分區(qū)，則結(jié)束探索。從所找到的分區(qū)中劃出所要求的內(nèi)存長度分配給用戶把余下的部分進行合并(如果有相鄰空閑區(qū)存在)后留在可用表中，但要修改其相應的表項。第五章存儲管理最先適應算法第五章存儲管理(2)最佳適應算法

從小到大的次序組成空閑區(qū)可用表或自由鏈。從表頭開始查找，當找到第一個滿足要求的空閑區(qū)時，停止查找。如果該空閑區(qū)大于請求表中的請求長度，將減去請求長度后的剩余空閑區(qū)部分留在可用表中。第五章存儲管理(3)最壞適應算法空閑區(qū)按其大小遞減的順序組成空閑區(qū)可用表或自由鏈。先檢查空閑區(qū)可用表或自由鏈的第一個空閑可用區(qū)的大小是否大于或等于所要求的內(nèi)存長度，若可用表或自由鏈的第一個項長度小于所要求的，則分配失敗否則從空閑區(qū)可用表或自由鏈中分配相應的存儲空間給用戶修改和調(diào)整空閑區(qū)可用表或自由鏈。第五章存儲管理

回收與拼接工作：當進程執(zhí)行結(jié)束時，要收回已使用完畢的空閑區(qū)，并將其插入空閑區(qū)可用表或自由鏈把不連續(xù)的零散空閑區(qū)集中起來第五章存儲管理空閑區(qū)的合并第五章存儲管理4分區(qū)管理的其他問題虛存的實現(xiàn)無法實現(xiàn)用戶進程所需內(nèi)存容量只受內(nèi)存和外存容量之和限制的虛擬存儲器。如果不采用內(nèi)存擴充技術(shù)，每個用戶進程所需內(nèi)存容量是受到分區(qū)大小限制的。內(nèi)存擴充可使用覆蓋或交換技術(shù)來擴充內(nèi)存。第五章存儲管理地址變換應采用動態(tài)重定位方法空閑區(qū)的拼接會移動內(nèi)存中的程序和數(shù)據(jù)一對硬件寄存器基址寄存器BR——進程在內(nèi)存分區(qū)的起始地址限長寄存器VR——進程在內(nèi)存分區(qū)的長度第五章存儲管理內(nèi)存保護設(shè)CPU指令所要訪問的虛擬地址為D若D>(VR)(限長寄存器中的限長值)：地址越界產(chǎn)生保護中斷系統(tǒng)轉(zhuǎn)去進行出錯處理若D<=(VR)：地址合法由硬件完成對該虛擬地址的動態(tài)重定位保護鍵法也可用來對內(nèi)存各分區(qū)提供保護第五章存儲管理5.分區(qū)存儲管理的主要優(yōu)缺點優(yōu)點(1)實現(xiàn)了多道程序設(shè)計，提高了資源利用率(2)需求硬件少，管理算法簡單，實現(xiàn)容易缺點(1)內(nèi)存利用率仍然不高。存在著嚴重的碎小空閑區(qū)(碎片)不能利用的問題。(2)進程的大小受分區(qū)大小控制，除非配合采用覆蓋和交換技術(shù)。(3)難以實現(xiàn)各分區(qū)間的信息共享。第五章存儲管理5.3覆蓋與交換技術(shù)是在多道環(huán)境下用來擴充內(nèi)存的兩種方法覆蓋技術(shù)主要用在早期的操作系統(tǒng)中交換技術(shù)在現(xiàn)代操作系統(tǒng)中仍具有較強的生命力第五章存儲管理1覆蓋技術(shù)思想一個程序并不需要一開始就把它的全部指令和數(shù)據(jù)都裝入內(nèi)存后再執(zhí)行。把程序劃分為若干個功能上相對獨立的程序段，按照程序的邏輯結(jié)構(gòu)讓那些不會同時執(zhí)行的程序段共享同一塊內(nèi)存區(qū)。通常，這些程序段都被保存在外存中，當有關(guān)程序段的先頭程序段已經(jīng)執(zhí)行結(jié)束后，再把后續(xù)程序段調(diào)入內(nèi)存覆蓋前面的程序段。第五章存儲管理覆蓋示例第五章存儲管理缺點:要求程序員提供一個清楚的覆蓋結(jié)構(gòu)程序員必須完成把一個程序劃分成不同的程序段，并規(guī)定好它們的執(zhí)行和覆蓋順序的工作。對操作系統(tǒng)的虛空間和內(nèi)部結(jié)構(gòu)很熟悉的程序員才會使用。第五章存儲管理2交換技術(shù)思想先將內(nèi)存某部分的程序或數(shù)據(jù)寫入外存交換區(qū)，再從外存交換區(qū)中調(diào)入指定的程序或數(shù)據(jù)到內(nèi)存中來，并讓其執(zhí)行。把處于等待狀態(tài)的進程換出內(nèi)存。優(yōu)點不要求程序員給出程序段之間的覆蓋結(jié)構(gòu)。與覆蓋的不同點交換主要是在進程或作業(yè)之間進行，而覆蓋則主要在同一個作業(yè)或進程內(nèi)進行。覆蓋只能覆蓋那些與覆蓋程序段無關(guān)的程序段。第五章存儲管理交換過程換出(s)過程把內(nèi)存中的數(shù)據(jù)和程序換到外存交換區(qū)換入(s)過程把外存交換區(qū)中的數(shù)據(jù)和程序換到內(nèi)存分區(qū)中第五章存儲管理由交換進程發(fā)送給設(shè)備進程的消息m中應包含:分區(qū)的分區(qū)號i該分區(qū)的基址basei長度sizei方向外存交換區(qū)中分區(qū)起始地址第五章存儲管理

S(i): beginlocalm m.base←basei; m.ceiling←basei+sizei; m.direction←"out"; m.destination←baseoffreeareaons; backupstorebasei←m.destination; send((m，i)，devicequeue); end第五章存儲管理 SWAPIN(i): beginlocalm m.base←basei; m.ceiling←basei+sizei; m.direction←"in"; m.source←backupstorebasei; send((m,i)，devicequeue); end第五章存儲管理5.4頁式管理分區(qū)式管理的缺點存在著嚴重的碎片問題，內(nèi)存的利用率不高進程的大小受分區(qū)大小或內(nèi)存可用空間的限制不利于程序段和數(shù)據(jù)的共享第五章存儲管理1.頁式管理的基本原理目的減少碎片，提高內(nèi)存利用率只在內(nèi)存存放那些反復執(zhí)行或即將執(zhí)行的程序段與數(shù)據(jù)部分把那些不經(jīng)常執(zhí)行的程序段和數(shù)據(jù)存放于外存待執(zhí)行時調(diào)入第五章存儲管理1、等分內(nèi)存：內(nèi)存空間被劃分成若干個長度相等的頁面(2m)

一般每個頁長大約為1-4K2、進程虛擬空間的分頁：劃分成與內(nèi)存頁長度相等的頁。3、虛地址的表示：虛地址由頁號p與頁內(nèi)地址w所組成。例如，某系統(tǒng)，地址長度位20位，每一頁的大小為1KB。頁號（P）頁內(nèi)地址（W）19 109 04、內(nèi)存分配：進程的各頁，分配到內(nèi)存可以不相鄰的頁面中。5、頁表：系統(tǒng)為每個進程在內(nèi)存設(shè)立一張頁表。頁式管理的基本原理：第五章存儲管理2靜態(tài)頁面管理思想在作業(yè)或進程開始執(zhí)行之前，把該作業(yè)或進程的程序段和數(shù)據(jù)全部裝入內(nèi)存的各個頁面中通過頁表(pagemappingtable)和硬件地址變換機構(gòu)實現(xiàn)虛擬地址到內(nèi)存物理地址的地址映射第五章存儲管理內(nèi)存頁面的分配與回收數(shù)據(jù)結(jié)構(gòu)頁表請求表存儲頁面表第五章存儲管理(1)頁表每個進程至少擁有一個頁表。頁表在內(nèi)存中占有一塊固定的存儲區(qū)。頁表的大小由進程或作業(yè)的長度決定。頁號頁面號第五章存儲管理(2)請求表請求表整個系統(tǒng)一張。用來確定作業(yè)或進程的虛擬空間的各頁在內(nèi)存中的實際對應位置。第五章存儲管理(3)存儲頁面表整個系統(tǒng)一張指出內(nèi)存各頁面是否已被分配出去,以及未分配頁面的總數(shù)位示圖法：內(nèi)存中劃分一塊固定區(qū)域，每個單元的每個比特代表一個頁面。如果該頁面已被分配，則對應比特位置1，否則置0。

第五章存儲管理分配算法(1)請求表給出進程或作業(yè)要求的頁面數(shù)。(2)由存儲頁面表檢查是否有足夠的空閑頁面，如果沒有，則本次無法分配。(3)如果有則首先分配設(shè)置頁表，并填寫請求表中的相應表項后，按一定的查找算法、搜索出所要求的空閑頁面，并將對應的頁面號填入頁表中。第五章存儲管理頁面分配算法流圖第五章存儲管理回收算法當進程執(zhí)行完畢時(1)把頁表中的各頁面插入存儲頁面表(2)拆除對應的頁表第五章存儲管理地址變換在一個作業(yè)或進程的頁表中，連續(xù)的頁號對應于不連續(xù)的頁面號。例如，設(shè)一個3頁長的進程具有頁號0，1，2，但其對應的頁面號則為2，3，8。頁號頁面號021328第五章存儲管理設(shè)每個頁面長度為1K，指令LOAD1，2500的虛地址為100，怎樣通過頁表來找到該指令所對應的物理地址呢?第五章存儲管理注意：地址變換過程由硬件地址變換機構(gòu)自動完成，屬于動態(tài)重定位。取一個數(shù)據(jù)或指令至少要訪問內(nèi)存兩次一次訪問頁表，另一次是根據(jù)地址取數(shù)據(jù)或指令改善方法：（1）把頁表放在寄存器中而不是內(nèi)存中，但由于寄存器價格太貴，這樣做是不可取的。（2）增設(shè)一個高速聯(lián)想存儲器，構(gòu)成一張快表。在快表中，存入那些當前執(zhí)行進程中最常用的頁號與所對應的頁面號，從而以提高查找速度。虛擬存儲器內(nèi)存＋外存第五章存儲管理優(yōu)點解決了分區(qū)管理時的碎片問題缺點要求進程或作業(yè)在執(zhí)行前全部裝入內(nèi)存，如果可用頁面數(shù)小于用戶要求時，只好等待作業(yè)或進程的大小仍受內(nèi)存可用頁面數(shù)的限制第五章存儲管理3動態(tài)頁式管理思想：在作業(yè)或進程開始執(zhí)行之前，只裝入被認為是經(jīng)常反復執(zhí)行和調(diào)用的工作區(qū)部分。其他部分則在執(zhí)行過程中動態(tài)裝入。分類：預調(diào)入頁式管理請求頁式管理第五章存儲管理預調(diào)入頁式管理方法對那些在外存中的頁進行調(diào)入順序計算估計這些頁中指令和數(shù)據(jù)的執(zhí)行和被訪問的順序按此順序?qū)⑺鼈円来握{(diào)入和調(diào)出內(nèi)存第五章存儲管理請求頁式管理方法當要執(zhí)行某條指令而又發(fā)現(xiàn)它不在內(nèi)存時或當執(zhí)行某條指令需要訪問其他數(shù)據(jù)時這些數(shù)據(jù)不在內(nèi)存時，從而發(fā)生缺頁中斷系統(tǒng)將外存中相應的頁面調(diào)入內(nèi)存第五章存儲管理請求頁式管理的地址變換與靜態(tài)頁式管理時的相同頁表查出相應的頁面號頁面號與頁內(nèi)相對地址相加得到實際物理地址會出現(xiàn)某些虛頁不在內(nèi)存中的問題第五章存儲管理請求頁式管理必須解決的兩個基本問題(1)怎樣發(fā)現(xiàn)不在內(nèi)存中虛頁?(2)當要訪問的頁不在內(nèi)存怎樣處理?第五章存儲管理(1)怎樣發(fā)現(xiàn)不在內(nèi)存中虛頁?可以用擴充頁表的方法解決加入中斷處理后的頁表頁號頁面號中斷位外存始址012345第五章存儲管理(2)當要訪問的頁不在內(nèi)存怎樣處理?采用何種方式把所缺的頁調(diào)入內(nèi)存外存地址如果內(nèi)存中沒有空閑頁面時，采用什么樣的策略來淘汰已占據(jù)內(nèi)存的頁置換算法某一頁被淘汰，且該頁曾因程序的執(zhí)行而被修改，該頁應重新寫到外存上加以保存改變位－dirtybit第五章存儲管理加改變位頁號頁面號中斷位外存始址改變位012345第五章存儲管理抖動(thrashing)現(xiàn)象：如果置換算法選擇不當，有可能產(chǎn)生剛被調(diào)出內(nèi)存的頁又要馬上被調(diào)回內(nèi)存，調(diào)回內(nèi)存不久又馬上被調(diào)出內(nèi)存，如此反復的局面。這使得整個系統(tǒng)的頁面調(diào)度非常頻繁，以致大部分時間都花費在主存和輔存之間的來回調(diào)入調(diào)出上。這種現(xiàn)象被稱為抖動(thrashing)現(xiàn)象。第五章存儲管理

動態(tài)頁式管理流圖第五章存儲管理4請求頁式管理中的置換算法(1)隨機淘汰算法思想在無法確定哪些頁被訪問的概率較低時，隨機地選擇某個用戶的頁面并將其換出。第五章存儲管理(2)先進先出算法(FIFO)思想基于CPU按線性順序訪問地址空間的這個假設(shè)上，選擇最先調(diào)入內(nèi)存的頁換出。缺點：效率不高CPU不一定是按線性順序訪問地址空間的例如循環(huán)語句具有Belady奇異分配的內(nèi)存頁面數(shù)增多，缺頁次數(shù)反而增加第五章存儲管理Belady奇異第五章存儲管理例:設(shè)進程P共有8頁，且已在內(nèi)存中分配有3個頁面，程序訪問內(nèi)存的順序(訪問串)為7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1。70120304230321201777222244400000000000333222221111111100033333222依次淘汰：701230423

進程在一個執(zhí)行過程中，實際上發(fā)生了12次缺頁。如果設(shè)缺頁率為缺頁次數(shù)與訪問串的訪問次數(shù)之比則該例中的缺頁率為12/17=70.5%。第五章存儲管理如果給進程P分配4個頁面共發(fā)生9次缺頁，其缺頁率為9/17=52.9%。以上是使用FIFO算法正常換頁時的例子。7012030423032120177777333333333222000000444444444411111111000000022222222221111依次淘汰：70123第五章存儲管理改進的寫法：如果給進程P分配4個頁面共發(fā)生9次缺頁，其缺頁率為9/17=52.9%。70120304230321201701234012701234017012340701234依次淘汰：70123第五章存儲管理123412512345123412534123412531234125

另外一個訪問串。設(shè)進程P，訪問串為1，2，3，4，1，2，5，1，2，3，4，5。當進程P分得3個頁面時，執(zhí)行過程。進程P在執(zhí)行過程中共缺頁9次，其缺頁率為9/12=75%。如果為進程P分配4個內(nèi)存頁面，執(zhí)行過程。1234125123451234512345123451234123451231234512缺頁次數(shù)為10次。即缺頁率=10/12=83.3%。依次淘汰：123412依次淘汰：123451第五章存儲管理(3)最近最久未使用頁面置換算法(LRU:LeastRecentlyUsed)思想:如果某頁被訪問了，則它可能馬上還要被訪問如果某頁很長時間未被訪問，則它在最近一段時間也不會被訪問當需要淘汰某一頁時，選擇離當前時間最近的一段時間內(nèi)最久沒有使用過的頁先淘汰第五章存儲管理如果給進程P分配4個頁面，采用LRU算法共發(fā)生7次缺頁，其缺頁率為7/17=41.2%。701203042303212017777333000000111412222依次淘汰：714第五章存儲管理比較常用的LRU近似算法有:a)最不經(jīng)常使用頁面淘汰算法LFU(leastfrequentlyused)。思想：在需要淘汰某一頁時，首先淘汰到當前時間為止，被訪問次數(shù)最少的那一頁。實現(xiàn)在頁表中給每一頁增設(shè)一個訪問計數(shù)器每當該頁被訪問時，訪問計數(shù)器加1而發(fā)生一次缺頁中斷時，則淘汰計數(shù)值最小的那一頁，并將所有的計數(shù)器清零。第五章存儲管理如果給進程P分配3個頁面，

LRU算法 LFU算法212123422

221

14

33212123422

221

11

34淘汰：

13第五章存儲管理b)最近沒有使用頁面淘汰算法NUR。思想在需要淘汰某一頁時，從那些最近一個時期內(nèi)未被訪問的頁中任選一頁淘汰。實現(xiàn)在頁表中增設(shè)一個訪問位當某頁被訪問時，訪問位置1，否則，訪問位置0系統(tǒng)周期性地對所有引用位清零當需淘汰一頁時，從那些訪問位為零的頁中選一頁進行淘汰第五章存儲管理c）二次機會（SecondChance）實現(xiàn)以FIFO算法進行選擇，當某頁面被選擇，考察其“訪問位”若為0，則淘汰；若為1則將訪問位清0，并將該頁面放到隊列末尾，選擇下一頁，直到選到“訪問位”若為0的頁面。第五章存儲管理(4)理想型淘汰算法OPT(OPTimalreplacementalgorithm)。思想淘汰在訪問串中將來再也不出現(xiàn)的或是在離當前最遠的位置上出現(xiàn)的頁淘汰掉該頁將不會造成因需要訪問該頁又立即把它調(diào)入的現(xiàn)象注意這種算法無法實現(xiàn)它要求必須預先知道每一個進程的訪問串第五章存儲管理如果給進程P分配4個頁面，采用OPT算法共發(fā)生7次缺頁，其缺頁率為7/17=41.2%。該算法不具有Belady現(xiàn)象。701203042303212017777333000000111412222依次淘汰：714或3第五章存儲管理頁面置換作業(yè)一個請求分頁系統(tǒng)中，假如一個進程的頁面走向為

12342156212376321236

當分配給該進程的內(nèi)存頁面數(shù)為4時，采用FIFO、LRU和OPT頁面調(diào)度算法時，請計算訪問過程中所發(fā)生幾次缺頁中斷，寫出按先后順序淘汰的頁號。FIFO（14），LRU（10），OPT（8）

第五章存儲管理5頁式管理的存儲保護地址越界保護可由地址變換機構(gòu)中的控制寄存器的值——頁表長度和所要訪問的虛地址相比較來完成。存取控制保護在頁表中增加相應的保護位即可。第五章存儲管理0123P101234P201頁號頁面號…0105110723100101102103104105106107108109110頁號頁面號…01051107234P1頁表P2頁表頁面共享第五章存儲管理6頁式管理的優(yōu)缺點優(yōu)點:(1)由于它不要求作業(yè)或進程的程序段和數(shù)據(jù)在內(nèi)存中連續(xù)存放，從而有效地解決了碎片問題。(2)動態(tài)頁式管理提供了內(nèi)存和外存統(tǒng)一管理的虛存實現(xiàn)方式，使用戶可以利用的存儲空間大大增加。這既提高了主存的利用率，又有利于組織多道程序執(zhí)行。第五章存儲管理缺點:(1)要求有相應的硬件支持。例如地址變換機構(gòu)，缺頁中斷的產(chǎn)生和選擇淘汰頁面等都要求有相應的硬件支持。這增加了機器成本。(2)增加了系統(tǒng)開銷，例如缺頁中斷處理等。(3)請求調(diào)頁的算法如選擇不當，有可能產(chǎn)生抖動現(xiàn)象。(4)雖然消除了碎片，但每個作業(yè)或進程的最后一頁內(nèi)總有一部分空間得不到利用。如果頁面較大，則這一部分的損失仍然較大。第五章存儲管理5.5段式與段頁式管理1、段式管理的基本思想分區(qū)式管理和頁式管理的缺點(1)不便于共享分區(qū)式管理和頁式管理時的進程地址空間結(jié)構(gòu)都是線性的，這使得不同作業(yè)或進程之間共享公用子程序和數(shù)據(jù)變得非常困難。一個頁面中可能裝有兩個不同子程序段的指令代碼，因此，通過頁面共享來達到共享一個邏輯上完整的子程序或數(shù)據(jù)塊是不可能的。第五章存儲管理(2)段之間只能靜態(tài)鏈接分區(qū)管理和頁式管理只能采用靜態(tài)鏈接。從減少CPU開銷和存儲空間浪費的角度來看，靜態(tài)鏈接是不合適的。第五章存儲管理段式管理的基本思想：把程序按內(nèi)容或過程(函數(shù))關(guān)系分成段，每段有自己的名字。一個用戶作業(yè)或進程所包含的段對應于一個二維線性虛擬空間，也就是一個二維虛擬存儲器。段式管理程序以段為單位分配內(nèi)存，然后通過地址映射機構(gòu)把段式虛擬地址轉(zhuǎn)換成實際的內(nèi)存物理地址。第五章存儲管理2段式管理的實現(xiàn)原理（1）段式虛存空間段式管理把一個進程的虛地址空間設(shè)計成二維結(jié)構(gòu)，即段號s與段內(nèi)相對地址w。頁式管理中，被劃分的頁號按順序編號遞增排列，屬一維空間。每個段是一個首地址為零的、連續(xù)的一維線性空間，對應一組邏輯完整的程序或數(shù)據(jù)，段的長度是不固定的。對段式虛地址空間的訪問包括兩個部分:段名和段內(nèi)地址。第五章存儲管理例如，某進程，它在段式管理系統(tǒng)中的地址空間：進程中的地址結(jié)構(gòu)：CALL[1]|<24>轉(zhuǎn)向段1的子程序的入口點24。LOAD1,[2]|<6>將段2的入口點6的值讀到寄存器1中。STORE1,[2]|<18>將寄存器1的內(nèi)容存入段2的18單元中。

011160段

01981段

011282段第五章存儲管理(2)段式管理的內(nèi)存分配與釋放段式管理中以段為單位分配內(nèi)存，每段分配一個連續(xù)的內(nèi)存區(qū)。由于各段長度不等，所以這些存儲區(qū)的大小不一。同一進程所包含的各段之間不要求連續(xù)。第五章存儲管理(3)段式管理的內(nèi)存分配與釋放動態(tài)分配過程：首先，段式管理為進程或作業(yè)分配部分內(nèi)存，以作為該進程的工作區(qū)和放置即將執(zhí)行的程序段。隨著進程的執(zhí)行，進程根據(jù)需要隨時申請調(diào)入新段和釋放老段。進程對內(nèi)存區(qū)的申請和釋放可分為兩種情況：一種是當進程要求調(diào)入某一段時，內(nèi)存中有足夠的空閑區(qū)滿足該段的內(nèi)存要求另一種是內(nèi)存中沒有足夠的空閑區(qū)滿足該段的內(nèi)存要求。第五章存儲管理除了初始分配之外，段的動態(tài)分配是在CPU所要訪問的指令和數(shù)據(jù)不在內(nèi)存時產(chǎn)生缺段中斷的情況下發(fā)生的。因此，段的淘汰或置換算法實際上是缺段中斷處理過程的一部分。第五章存儲管理

缺段中斷處理過程第五章存儲管理(4)段式管理的地址變換段表(segmentmappingtable)和頁式管理方案類似，段式管理程序在進行初始內(nèi)存分配之前，首先根據(jù)用戶要求的內(nèi)存大小為一個作業(yè)或進程建立一個段表。與頁式管理時一樣，段式管理也是通過段表來進行內(nèi)存管理。第五章存儲管理圖5.30段表段號始址內(nèi)外存取方式訪問位長度第五章存儲管理

011160段

01981段

011282段例如：某進程的地址空間（外存）1段

0段內(nèi)存10003850段號地址內(nèi)外。。。03850111000120該進程段表第五章存儲管理動態(tài)地址變換一般在內(nèi)存中給出一塊固定的區(qū)域放置段表。當某進程開始執(zhí)行時，管理程序首先把該進程的段表始址放入段表地址寄存器。通過訪問段表寄存器，管理程序得到該進程的段表始址從而可開始訪問段表。然后，由虛地址中的段號s為索引，查段表。第五章存儲管理若該段在內(nèi)存，則判斷其存取控制方式是否有錯。如果存取控制方式正確，則從段表相應表目中查出該段在內(nèi)存的起始地址，并將其和段內(nèi)相對地址w相加，從而得到實際內(nèi)存地址。如果該段不在內(nèi)存，則產(chǎn)生缺段中斷將CPU控制權(quán)交給內(nèi)存分配程序。內(nèi)存分配程序首先檢查空閑區(qū)鏈，以找到足夠長度的空閑區(qū)來裝入所需要的段。如果內(nèi)存中的可用空閑區(qū)總數(shù)小于所要求的段長時，則檢查段表中訪問位，以淘汰那些訪問概率低的段并將需要段調(diào)入。第五章存儲管理段式地址變換過程第五章存儲管理與頁式管理時相同，段式管理時的地址變換過程也必須經(jīng)過二次以上的內(nèi)存訪問。

首先訪問段表以計算得到待訪問指令或數(shù)據(jù)的物理地址。然后才是對物理地址進行取數(shù)據(jù)或存數(shù)據(jù)操作。為了提高訪問速度，頁式地址變換時使用的高速聯(lián)想寄存器的方法也可以用在段式地址變換中。如果在聯(lián)想寄存器中找到了所需要的段，則可以大大加快地址變換速度。第五章存儲管理4.段的共享與保護(1)段的共享在多道環(huán)境下，常常有許多子程序和應用程序是被多個用戶所使用的。如果每個用戶進程或作業(yè)都在內(nèi)存保留它們共享程序和數(shù)據(jù)的副本，那就會極大地浪費內(nèi)存空間。最好的辦法是內(nèi)存中只保留一個副本，供多個用戶使用，稱為共享。第五章存儲管理第五章存儲管理

011160段

01981段

011282段例如：段的共享1段

0段內(nèi)存10003850

011160段

01981段

011002段第五章存儲管理一段程序為多個進程共享時(1)要求在執(zhí)行過程中，該段程序的指令和數(shù)據(jù)不能被修改。(2)在段表中設(shè)立相應的共享位來判別該段是否正被某個進程調(diào)用。顯然一個正在被某個進程使用或即將被某個進程使用的共享段是不應該調(diào)出內(nèi)存的。第五章存儲管理(2)段的保護與頁式管理時相同，段式管理的保護主要有兩種：地址越界保護法存取方式控制保護法第五章存儲管理缺點：(1)段式管理要求有硬件支持,提高了機器成本。(2)存在碎片問題，以及為了消除碎片所進行的合并等問題上較分頁式管理要差。再者，允許段的動態(tài)增長也會給系統(tǒng)管理帶來一定的難度和開銷。(3)段式管理的每個段的長度受內(nèi)存大小的限制。(4)段式管理系統(tǒng)也有可能產(chǎn)生抖動現(xiàn)象。第五章存儲管理4段頁式管理的基本思想把段式管理和頁式管理結(jié)合起來第五章存儲管理5段頁式管理的實現(xiàn)原理虛地址的構(gòu)成段頁式管理時，一個進程仍然擁有一個自己的二維地址空間，這與段式管理時相同。一個進程中所包含的具有獨立邏輯功能的程序或數(shù)據(jù)仍被劃分為段，并有各自的段號s。對于段s中的程序或數(shù)據(jù)，則按照一定的大小將其劃分為不同的頁。第五章存儲管理段頁式管理時的進程的虛擬地址空間中的虛擬地址由三部分組成:即段號s，頁號p和頁內(nèi)相對地址d。第五章存儲管理段表和頁表系統(tǒng)為每個作業(yè)或進程建立一張段表：管理內(nèi)存分配與釋放、缺段處理、存儲保護和地址變換等。每個段建立一張頁表：把段中的虛頁變換成內(nèi)存中的實際頁面。頁表中也要有實現(xiàn)缺頁中斷處理和頁面保護等功能的表項。頁表不再是屬于進程而是屬于某個段，因此，段表中應有專項指出該段所對應頁表的頁表始址和頁表長度。第五章存儲管理段頁式管理中段表、頁表與內(nèi)存的關(guān)系第五章存儲管理01

010段01

01

1段01

012段例如：某進程的地址空間（外存）1,01,1

0,00,12,0內(nèi)存段號地址012進程段表22頁號頁面號0104110620段頁表頁號頁面號010011021段頁表頁號頁面號0109122段頁表100101102103104105106107108109第五章存儲管理動態(tài)地址變換過程在段頁式管理系統(tǒng)中，要對內(nèi)存中指令或數(shù)據(jù)進行一次存取的話至少需要訪問三次以上的內(nèi)存：第一次是由段表地址寄存器得到段表始址去訪問段表，由此取出對應段的頁表地址。第二次則是訪問頁表得到所要