軟件技術(shù)存儲管理復習課程

第九章

存儲管理本章基本內(nèi)容與要求基本內(nèi)容存儲器層次結(jié)構(gòu)存儲管理任務(wù)實存儲管理虛擬存儲管理要求掌握存儲管理任務(wù)掌握存儲管理、實存儲管理、虛擬存儲管理了解存儲器層次結(jié)構(gòu)第一節(jié)存儲器層次結(jié)構(gòu)

存儲管理目的1、充分利用內(nèi)存，為多道程序并發(fā)執(zhí)行提供存儲基礎(chǔ)2、盡可能方便用戶使用自動裝入用戶程序用戶程序中不必考慮硬件細節(jié)3、系統(tǒng)能夠解決程序空間比實際內(nèi)存空間大的問題4、存儲保護與安全1.主存空間分配

合理分配，避免沖突；算法得當，提高效率；及時回收，循環(huán)利用。2.地址映射目標程序內(nèi)存地址空間存儲空間0x0640k系統(tǒng)區(qū)存放操作系統(tǒng)目標程序用戶區(qū)存放用戶作業(yè)絕對地址：主存儲器以字節(jié)為編址單位，容量為n的主存儲器中，每個單元有唯一的編號，從0到n-1，這個唯一的編號就是主存儲器的絕對地址(物理地址)。絕對地址邏輯地址:在多道程序設(shè)計的系統(tǒng)中，操作系統(tǒng)為了方便用戶，就允許每個用戶都認為自己的作業(yè)的程序和數(shù)據(jù)存放在地址是0開始的連續(xù)空間中。這樣用戶程序中使用的地址就是邏輯地址(相對地址)。相對地址重定位:當用戶程序調(diào)入內(nèi)存時，必須把邏輯地址轉(zhuǎn)換成絕對地址，同時包括對程序中與地址有關(guān)的指令進行修改，這一過程叫“重定位”或“地址轉(zhuǎn)換”。重定位的方式有兩種:靜態(tài)重定位動態(tài)重定位地址轉(zhuǎn)換靜態(tài)重定位在裝入一個程序時，把程序中的指令地址和數(shù)據(jù)地址全部轉(zhuǎn)換成絕對地址。這種轉(zhuǎn)換工作是在程序開始前集中完成的，在程序執(zhí)行過程中無需再進行地址轉(zhuǎn)換。所以稱為“靜態(tài)重定位”。使用一對界地址寄存器，分別存放該程序的起始和終止地址.x邏輯地址空間LD上界下界界地址寄存器Dx'L物理地址空間x'=x+D物理地址邏輯地址下界地址D<=x'<L動態(tài)重定位在裝入一個程序時，不進行地址轉(zhuǎn)換，而是直接把程序裝到分配的主存區(qū)域中。在程序執(zhí)行過程中，每當執(zhí)行一條指令時都由硬件的地址轉(zhuǎn)換機構(gòu)轉(zhuǎn)換成絕對地址。這種方式的地址轉(zhuǎn)換是在程序執(zhí)行時動態(tài)完成的，所以稱為動態(tài)重定位。動態(tài)重定位由軟件（操作系統(tǒng)）和硬件（地址轉(zhuǎn)換機構(gòu)）相互配合來實現(xiàn)。2.地址映射

程序的起始地址都是從“0”開始的，程序中的其它地址都是相對于起始地址計算的，該地址被稱為邏輯地址（或相對地址）。由這些地址所形成的地址范圍稱為（作業(yè)）地址空間。主存單元的編號稱為物理地址（或絕對地址）由主存中的一系列單元所限定的地址范圍稱為存儲空間。相對地址到絕對地址的轉(zhuǎn)換，同時程序中與地址有關(guān)的指令的修改，這一過程叫做地址重定位。靜態(tài)重定位在程序裝入時進行,由裝配程序進行地址轉(zhuǎn)換動態(tài)重定位是在程序的執(zhí)行過程中,當CPU訪問指令或數(shù)據(jù)前，由地址變換機構(gòu)進行地址變換。3.內(nèi)存保護

靜態(tài)重定位系統(tǒng)中：用界地址寄存器判斷程序是否在規(guī)定的上下界內(nèi)動態(tài)重定位系統(tǒng)中：與存儲方式有關(guān)保護系統(tǒng)程序區(qū)不被用戶侵犯。不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù)4.內(nèi)存“擴充”

把內(nèi)外存聯(lián)合起來，向用戶提供一個容量比實際容量大的多的存儲空間。技術(shù)：覆蓋交換虛擬存儲擴充內(nèi)存方法-覆蓋技術(shù)A20kBB50kBC20kBF30kBD20kBE40kB共180kBABCFDE020k21k70k71k110k共110kB作業(yè)必須滿足樹狀的模塊結(jié)構(gòu)要由用戶寫出覆蓋文件ROOTA-(B-F,C-(D,E))擴充內(nèi)存方法-交換技術(shù)以整個作業(yè)為單位進行內(nèi)外存交換（滾進滾出）缺點：移動會增加系統(tǒng)開銷。第三節(jié)實存儲管理單一連續(xù)分區(qū)(單道環(huán)境)固定分區(qū)動態(tài)分區(qū)為調(diào)入內(nèi)存的程序提供一個不小于作業(yè)地址空間的存儲空間，當存儲空間不夠時，采用覆蓋或交換技術(shù)擴充內(nèi)存1.單一連續(xù)分區(qū)

在單道環(huán)境下，不管是單用戶系統(tǒng)還是單道批處理系統(tǒng)，進程（作業(yè)）執(zhí)行時除了系統(tǒng)占用一部分主存外，剩下的主存區(qū)域全部歸它占用。2.固定分區(qū)分配區(qū)號容量起始位置狀態(tài)作業(yè)名18k16k占用作業(yè)1216k24k占用作業(yè)2332k40k空閑456k72k占用作業(yè)3操作系統(tǒng)區(qū)作業(yè)1作業(yè)2作業(yè)3016k24k40k72k128k內(nèi)存狀態(tài)表內(nèi)存基本原理：預(yù)先把可分配的主存儲器空間分割成若干個連續(xù)區(qū)域，每個區(qū)域的大小可以相等，也可以不等。固定分區(qū)的優(yōu)缺點優(yōu)點實現(xiàn)多個作業(yè)共享分區(qū)的分配和回收算法簡單缺點內(nèi)存利用不充分，因為每個分區(qū)中都會有一部分空間被浪費了。操作系統(tǒng)區(qū)作業(yè)1作業(yè)2作業(yè)3016k24k40k72k128k內(nèi)存碎片3.動態(tài)分區(qū)

主存不是預(yù)先劃分好的，而是當作業(yè)裝入時，根據(jù)作業(yè)的需求和主存空間的使用情況來動態(tài)決定是否分配。進程5OS進程9進程10進程2進程5OS進程9進程2進程5OS進程2進程5OS進程8進程2占用塊進程5OS進程10進程2空閑塊3.動態(tài)分區(qū)

分區(qū)分配空閑分區(qū)分配算法分區(qū)的回收可重定位的動態(tài)分區(qū)3.動態(tài)分區(qū)

分區(qū)分配采用分區(qū)表（或者分區(qū)鏈表）來實現(xiàn)空閑分區(qū)表:表示空閑分區(qū)的信息已分區(qū)分配表:已使用分區(qū)的信息3.動態(tài)分區(qū)

分區(qū)分配3.動態(tài)分區(qū)

2.空閑分區(qū)分配算法

1）首次適應(yīng)算法（FirstFit）

2）下次適應(yīng)算法（NextFit）

3）最壞適應(yīng)算法（WorstFit）

4）最佳適應(yīng)算法（BestFit）3.動態(tài)分區(qū)

2.空閑分區(qū)分配算法

1）首次適應(yīng)算法（FirstFit）在分區(qū)表中順序查找，找到夠大的空閑區(qū)就分配。特點：簡單、快速分配缺點:可能形成許多不連續(xù)的空閑區(qū)，造成許多“碎片”，使主存空間利用率降低。3.動態(tài)分區(qū)

2.空閑分區(qū)分配算法

2）下次適應(yīng)算法（NextFit）

類似首次適應(yīng)法，總是從上次查找結(jié)束的地方開始，只要找到一個足夠大的空白區(qū)，就把它劃分后分配出去。特點：解決了低地址區(qū)會產(chǎn)生很多碎片的問題，使內(nèi)存中空閑分區(qū)分布比較均勻，缺點:大的空閑分區(qū)在內(nèi)存中不易保留。3.動態(tài)分區(qū)

2.空閑分區(qū)分配算法

3）最壞適應(yīng)算法（WorstFit）總是挑一個最大的空閑區(qū)分給作業(yè)使用，使剩下的空間不至于太小。適用于請求分配內(nèi)存大小較均勻的系統(tǒng)要求:空白塊自大至小排列3.動態(tài)分區(qū)

2.空閑分區(qū)分配算法

4）最佳適應(yīng)算法（BestFit）接到內(nèi)存申請時，在空閑塊表中找到一個能滿足要求的最小空塊進行分配特點：用最小空間滿足要求缺點:可能形成一些極小的空閑區(qū)，以致無法使用，這也會影響主存利用率。要求:空白塊自小至大排列3.動態(tài)分區(qū)

3.分區(qū)的回收

當進程結(jié)束或終止時，要進行內(nèi)存回收。如果回收的分區(qū)與其它的分區(qū)相鄰，則合并成一個較大的分區(qū)，修改空閑分區(qū)表，并檢查是否滿足阻塞在內(nèi)存空間的等待進程的需求。

3.動態(tài)分區(qū)

4.可重定位的動態(tài)分區(qū)使用緊湊技術(shù)，為了消除外部碎片，進一步提高主存的利用率，定時地（或者在主存空間緊張時）把主存中的作業(yè)“搬家”集中在主存的一端，使另一端產(chǎn)生一個大的空閑區(qū)，這種技術(shù)稱為存儲器的“緊湊”。緊湊僅僅在動態(tài)重定位時才可以用，并且在運行時執(zhí)行。P1P2P3P4P5P6占用塊空閑塊P1P2P3P5動態(tài)重定位…Load1,1000…0289001001000地址空間…Load1,1000…02890100231012311023+10023存儲空間定位寄存器每讀一條指令，都要變換一次地址。變換要靠硬件支持.第四節(jié)虛擬存儲管理1.虛擬存儲器的原理2.請求分頁存儲管理3.請求分段存儲管理虛擬存儲管理工作原理：首先把作業(yè)信息保留在磁盤上，當作業(yè)請求裝入時，只將其中一部分先裝入主存，作業(yè)執(zhí)行中若要訪問的信息不在主存中，則再設(shè)法將這些信息裝入主存。用軟件方法擴充內(nèi)存。邏輯上擴充了內(nèi)存空間。虛擬地址空間的大小受指令中地址長度的限制和外存儲容量的限制；需解決什么時候把哪部分程序裝入內(nèi)存、放在內(nèi)存什么地方、淘汰策略問題。內(nèi)存分頁1.虛擬存儲器的原理——程序局部性原理

在一段時間內(nèi)一個程序的執(zhí)行往往呈現(xiàn)出高度的局部性，表現(xiàn)在時間與空間兩方面時間局部性：一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行空間局部性：若某一存儲單元被使用，則在一定時間內(nèi)，與該存儲單元相鄰的單元可能被使用2.請求分頁存儲管理

1).分頁管理的基本概念2).地址變換機構(gòu)3).頁面置換算法4).分頁存儲管理的優(yōu)缺點飯店房間和內(nèi)存分頁0頁1頁2頁…n頁0213263449……用戶程序頁表頁號塊號內(nèi)存塊號01234567分頁存儲管理頁:將作業(yè)的地址空間劃分成一系列大小相等的塊，稱為頁，所有頁按順序編號為0、1、2、·…¨。頁內(nèi)地址:每個頁內(nèi)的內(nèi)容也都從0開始順序編號，這個編號稱為頁內(nèi)地址。塊（頁框）:內(nèi)存空間也劃分成與頁一樣大的塊，所有的塊從低地址到高地址順序編號為0、1、2、·…¨。頁表:系統(tǒng)為作業(yè)建立一個頁號與塊號的對照表。頁表(PMT表)頁號與塊號的對照表，稱為頁表。頁號塊號狀態(tài)0:該頁不在內(nèi)存1:該頁在內(nèi)存在多道程序設(shè)計系統(tǒng)中，進入主存的每個作業(yè)都有一張頁表，由一個硬件“頁表地址寄存器”來記錄每個作業(yè)的頁表所在位置和長度以便作業(yè)轉(zhuǎn)換時同時轉(zhuǎn)換頁表。分頁系統(tǒng)中的邏輯地址頁號p頁內(nèi)地址d邏輯地址可用一個數(shù)對表示p=INTAL邏輯地址頁面大小d=AMODL例:設(shè)某系統(tǒng)頁面大小位1024字節(jié)，若邏輯地址為:2500,則p=INT(2500/1024)=2d=2500MOD1024=452即2500處于第2頁,第452位置上2).分頁管理中的地址轉(zhuǎn)換訪問某個邏輯地址時，分頁地址變換機構(gòu)自動將邏輯地址分為頁號和頁內(nèi)地址兩部分，再以頁號為索引去檢索頁表。從頁表中查到相應(yīng)頁的目錄，將該頁對應(yīng)的塊號與頁內(nèi)地址合并構(gòu)成物理地址將頁號與頁表長進行比較，若頁號超過了表長，產(chǎn)生越界中斷2).分頁管理中的地址轉(zhuǎn)換Load,1,250023285…地址空間…內(nèi)存塊號0181010002500300003110281頁號塊號狀態(tài)Lb+頁表長頁表起始地址頁表地址寄存器24528452232858644PMT表pdp'd'地址變換機構(gòu)8*1024+452=8644絕對地址=塊號*頁面大小+頁內(nèi)地址作業(yè)(要求寫出計算過程）：在請求分頁系統(tǒng)中，設(shè)每頁512字節(jié)，某時刻系統(tǒng)給用戶程序第0、1、2、3頁分配的物理塊號依次為6、11、3、17，則用戶程序中邏輯地址1200經(jīng)變換后得到的物理地址為

，該地址所在的物理塊號為

。分頁式虛擬存儲器的實現(xiàn)

首先把作業(yè)信息作為副本存放在磁盤上，作業(yè)執(zhí)行時，把作業(yè)信息的部分頁面裝入主存儲器，作業(yè)執(zhí)行時若所訪問的頁面已經(jīng)在主存中，則進行地址轉(zhuǎn)換，得到絕對地址，否則產(chǎn)生“缺頁中斷”由操作系統(tǒng)把當前所需的頁面裝入主存。

XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K虛地址空間物理地址空間}虛頁分頁虛擬存儲管理缺頁中斷（PageFault）在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，將該頁調(diào)入內(nèi)存，使作業(yè)繼續(xù)運行下去如果內(nèi)存中有空閑塊，則分配一頁，將新調(diào)入頁裝入內(nèi)存，并修改頁表中相應(yīng)頁表項目的狀態(tài)位及相應(yīng)的內(nèi)存塊號若此時內(nèi)存中沒有空閑塊，則要淘汰某頁，若該頁在內(nèi)存期間被修改過，則要將其寫回外存3).頁面置換算法

當主頁中無空閑塊時，為了裝入一個頁面，就必須按某種算法將主存中某個頁調(diào)出，調(diào)入所需裝入的頁面。這就是頁面調(diào)度。算法有：先進先出調(diào)度算法(FIFO)、最近最少使用調(diào)度算法(LRU)最近未使用頁面置換算法（NRU）最佳頁面置換算法(OPT)

(1)先進先出算法(FIFO)

當需要淘汰一頁時，選擇在主存中駐留時間最長的那頁被淘汰掉。思想:最先進入內(nèi)存的頁面,不再被使用的可能性最大適用于按線性順序訪問的程序

先進先出算法(FIFO)設(shè)一用戶程序共分5頁,分配給它的內(nèi)存塊數(shù)為3頁面走向P為

432143543215其頁面淘汰過程:432143543215432143555211432143335224321444355+++++++++缺頁中斷9次FIFO頁面淘汰算法會產(chǎn)生異?，F(xiàn)象，即：當分配給進程的物理頁面數(shù)增加時，缺頁次數(shù)反而增加。例如：假設(shè)作業(yè)共有5個虛頁，其頁面訪問蹤跡為：0，1，2，3，0，1，4，0，1，2，3，4。計算當分配3個和4個實頁時的缺頁中斷次數(shù)。頁面訪問蹤跡012301401234三個實頁的分配與淘汰012301444233

01230111422

01230001449次缺頁中斷√√√√√√√

√√

頁面訪問蹤跡012301401234四個實頁的分配與淘汰012333401234

01222340123

0111234012

00012340110次缺頁中斷√√√√

√√√√√√(2)最近最少使用算法(LRU)

當需要淘汰一頁時，選擇在最近一段時間內(nèi)最久未用的頁淘汰掉。UNIX操作系統(tǒng)采用的就是這種算法。方法：設(shè)置記時器:在頁表的每個入口，設(shè)一個“訪問時間”區(qū)域,當一個頁面被訪問時，時鐘寄存器里的內(nèi)容被拷貝到這個區(qū)域。置換時替換最小時間值的頁面。利用堆棧:當頁面被訪問時，將它從堆棧底部移到頂部。棧頂頁面常常是最常用的頁面，而底部的就是LRU頁。

(3)最近未使用頁面置換算法（NRU）

是LRU算法的近似：將內(nèi)存中的頁面組成一循環(huán)鏈表，每一頁面對應(yīng)一訪問位，當某頁面被訪問時，將其訪問位自動置“1”。如果指針指向頁面的訪問位為“0”（代表最近沒有被訪問），則置換該頁；否則，將訪問位置為“0”，頁面繼續(xù)留在內(nèi)存，按照相同規(guī)則替換下一頁。如果一頁經(jīng)常被用到，則它永遠不會被換出。

NRU頁面替換過程入口查詢指針前進一步,指向下一個表目頁面引用位=0?選擇該頁面淘汰返回置頁面訪問位=0是否01240342156507108塊號頁號引用位指針····q第6頁請求進入NRU頁面替換過程入口查詢指針前進一步,指向下一個表目頁面引用位=0?選擇該頁面淘汰返回置頁面訪問位=0是否01240342156507108塊號頁號引用位指針····q611第1頁請求訪問第5頁請求進入NRU頁面替換過程入口查詢指針前進一步,指向下一個表目頁面引用位=0?選擇該頁面淘汰返回置頁面訪問位=0是否01240342156617118塊號頁號引用位指針····q0NRU頁面替換過程入口查詢指針前進一步,指向下一個表目頁面引用位=0?選擇該頁面淘汰返回置頁面訪問位=0是否01240342156617108塊號頁號引用位指針····q15引用位周期性清零NRU頁面替換過程入口查詢指針前進一步,指向下一個表目頁面引用位=0?選擇該頁面淘汰返回置頁面訪問位=0是否01240342056607108塊號頁號引用位指針····q5(4)最佳頁面置換算法(OPT)

該算法思想是從主存中移出永不再用的頁面，至少是選擇很遠的將來才用的頁面淘汰之。其實，這是一個不實用的算法，因為頁面走向是不可預(yù)知的。所以該算法常用做性能評價的依據(jù)。OPT算法具有最低的缺頁率。4).分頁存儲管理的優(yōu)缺點

優(yōu)點分頁存儲管理的優(yōu)點是不需要移動就可解決碎片問題；提高主存的利用率；可提供大容量的多個虛擬存儲器；提高了多道程序運行的程度；對大作業(yè)而言，更加方便用戶。缺點由于采用了動態(tài)地址變換機構(gòu)，增加了計算機的成本，處理速度降低；對于請求分頁系統(tǒng)，為處理頁面中斷增加了系統(tǒng)開銷；在進程的最后一個頁框中可能有內(nèi)部碎片的存在。

從分頁到分段第0頁第1頁第2頁第3頁第4頁第5頁第6頁第7頁第8頁第9頁內(nèi)存作業(yè)邏輯結(jié)構(gòu)主程序段子程序段數(shù)據(jù)區(qū)段工作區(qū)段內(nèi)存作業(yè)邏輯結(jié)構(gòu)主程序段子程序段數(shù)據(jù)區(qū)段工作區(qū)段用戶希望第0段第1段第2段第3段3.請求分段存儲管理分段存儲管理中,作業(yè)的地址空間被劃分為若干個段,每段定義一組邏輯信息,如:主程序段,子程序段,數(shù)據(jù)段等,規(guī)定一個段號,每段地址空間都從0開始.段號s段內(nèi)地址w邏輯地址可用兩部分表示內(nèi)存分配:以段為單位分配內(nèi)存，每一個段在內(nèi)存中占據(jù)連續(xù)空間（內(nèi)存隨機分割，需要多少分配多少），但各段之間可以不連續(xù)存放段表(SMT表)段號段長度起始地址狀態(tài)0:該段不在內(nèi)存1:該段在內(nèi)存

它記錄了段號，段的首（地）址和長度之間的關(guān)系每一個程序設(shè)置一個段表，放在內(nèi)存屬于進程的現(xiàn)場信息分段管理中的地址轉(zhuǎn)換邏輯地址段號s段內(nèi)地址w…內(nèi)存01k6144