操作系統(tǒng)講稿-5-2013

第五章存儲(chǔ)管理存儲(chǔ)管理基礎(chǔ)

存儲(chǔ)管理的基本概念

覆蓋與交換技術(shù)連續(xù)存儲(chǔ)空間管理非連續(xù)分配管理方式虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器的基本概念請(qǐng)求分頁(yè)存儲(chǔ)管理頁(yè)面置換算法頁(yè)面分配策略抖動(dòng)請(qǐng)求分段管理方式存儲(chǔ)管理基礎(chǔ)

1.存儲(chǔ)管理的基本概念內(nèi)存管理的功能存儲(chǔ)分配問(wèn)題。重點(diǎn)是研究存儲(chǔ)共享和各種主存空間的分配與回收。地址再定位問(wèn)題。研究各種地址變換機(jī)構(gòu)，將邏輯地址轉(zhuǎn)換為物理地址。存儲(chǔ)保護(hù)問(wèn)題。研究保護(hù)各類(lèi)程序、數(shù)據(jù)區(qū)的方法。由硬件和軟件配合完成存儲(chǔ)擴(kuò)充問(wèn)題。主要研究虛擬存儲(chǔ)器問(wèn)題及其各種調(diào)度算法。從邏輯上擴(kuò)充內(nèi)存容量。（1）物理地址與邏輯地址

物理地址與物理地址空間內(nèi)存中的每個(gè)物理存儲(chǔ)單元都有一個(gè)編號(hào)，這個(gè)編號(hào)稱為內(nèi)存地址，即物理地址（也稱絕對(duì)地址）。存地址從0開(kāi)始編號(hào)，最大值取決于內(nèi)存的大小和地址寄存器所能表示的最大值物理地址的集合稱為物理空間，也稱存儲(chǔ)空間邏輯地址與邏輯地址空間用戶的源程序一旦編譯之后，每個(gè)目標(biāo)模塊都以0為基地址進(jìn)行編址，這種地址稱為邏輯地址或相對(duì)地址。邏輯地址的集合形成了一個(gè)地址范圍，這個(gè)范圍稱為邏輯地址空間，也稱為地址空間。（2）用戶程序的處理過(guò)程

用戶作業(yè)的程序通常用高級(jí)語(yǔ)言編寫(xiě)，稱為源程序。源程序是不能被計(jì)算機(jī)直接執(zhí)行的，需要經(jīng)過(guò)編譯、鏈接和裝入和執(zhí)行幾個(gè)步驟才能在內(nèi)存中執(zhí)行，如圖所示。源程序裝入模塊庫(kù)編譯程序……目標(biāo)模塊鏈接程序裝入程序內(nèi)存圖5.1用戶程序處理過(guò)程示意圖（3）主存空間的保護(hù)

計(jì)算機(jī)中使用的存儲(chǔ)保護(hù)主要有界地址、存儲(chǔ)鍵等保護(hù)方式。

上下界保護(hù)和地址檢查機(jī)構(gòu)

（3）主存空間的保護(hù)（續(xù)）基址、限長(zhǎng)寄存器和動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)

（4）地址重定位地址重定位用戶程序放在邏輯地址空間（在外存），運(yùn)行時(shí)裝入內(nèi)存，這就存在邏輯地址與物理地址的轉(zhuǎn)換。將用戶使用的邏輯地址轉(zhuǎn)換成內(nèi)存空間中的物理地址的過(guò)程就稱為地址轉(zhuǎn)換（映像），也稱為地址重定位。（4）地址重定位(續(xù))重定位類(lèi)型靜態(tài)地址重定位在裝入一個(gè)作業(yè)時(shí)，把作業(yè)中的指令地址全部轉(zhuǎn)換為絕對(duì)地址（地址轉(zhuǎn)換工作是在作業(yè)執(zhí)行前集中一次完成的）在作業(yè)執(zhí)行過(guò)程中就無(wú)須再進(jìn)行地址轉(zhuǎn)換工作。動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位是在程序執(zhí)行過(guò)程中，在CPU訪問(wèn)內(nèi)存之前,才將要訪問(wèn)的程序或數(shù)據(jù)地址轉(zhuǎn)換成內(nèi)存地址.動(dòng)態(tài)重定位依靠硬件地址變換機(jī)構(gòu)完成。（4）地址重定位(續(xù))80KB50KB030KOSOS作業(yè)A地址空間作業(yè)A地址空間030KB0110KB主存主存80KB靜態(tài)地址重定位（4）地址重定位(續(xù))L1,50012345作業(yè)地址空間0100500600L1,50012345010001100150016001000500處理機(jī)一側(cè)存儲(chǔ)器一側(cè)+BR有效地址再定位寄存器600LR界限寄存器主存動(dòng)態(tài)地址重定位

2.覆蓋與交換技術(shù)為什么引入？

在多道環(huán)境下擴(kuò)充內(nèi)存的方法，解決在較小的存儲(chǔ)空間中運(yùn)行較大程序時(shí)遇到的矛盾覆蓋技術(shù)主要用在早期的操作系統(tǒng)中交換技術(shù)被廣泛用于小型分時(shí)系統(tǒng)中，交換技術(shù)的發(fā)展導(dǎo)致了虛存技術(shù)的出現(xiàn)交換技術(shù)與覆蓋技術(shù)共同點(diǎn)：進(jìn)程的程序和數(shù)據(jù)主要放在外存，當(dāng)前需要執(zhí)行的部分放在內(nèi)存，內(nèi)外存之間進(jìn)行信息交換2.覆蓋與交換技術(shù)（續(xù)）覆蓋技術(shù)指一個(gè)作業(yè)的某些程序段，或幾個(gè)作業(yè)的某些部分輪流使用某一段存儲(chǔ)空間。基本思想是把內(nèi)存中同一區(qū)域，靜態(tài)地分配給一道程序的若干個(gè)子程序或數(shù)據(jù)段，在開(kāi)始時(shí)只讓一部分程序裝入內(nèi)存，根據(jù)運(yùn)行的情況，交替輪流使用。和單用戶連續(xù)區(qū)分配、分區(qū)分配技術(shù)配合使用。用戶需要小心設(shè)計(jì)程序的數(shù)據(jù)結(jié)構(gòu)，使其覆蓋模塊具有相對(duì)獨(dú)立性。例2.覆蓋與交換技術(shù)（續(xù)）缺點(diǎn)：對(duì)用戶不透明，增加了用戶負(fù)擔(dān)例子：目前這一技術(shù)用于小型系統(tǒng)中的系統(tǒng)程序的內(nèi)存管理上，MS-DOS的啟動(dòng)過(guò)程中，多次使用覆蓋技術(shù)；啟動(dòng)之后，用戶程序區(qū)的高端部分與COMMAND.COM暫駐模塊也是一種覆蓋結(jié)構(gòu)2.覆蓋與交換技術(shù)（續(xù)）交換技術(shù)當(dāng)內(nèi)存空間緊張時(shí)，系統(tǒng)將內(nèi)存中某些進(jìn)程暫時(shí)移到外存，把外存中某些進(jìn)程換進(jìn)內(nèi)存，占據(jù)前者所占用的區(qū)域，這種技術(shù)是進(jìn)程在內(nèi)存與外存之間的動(dòng)態(tài)調(diào)度多用于分時(shí)系統(tǒng)中使用外存做緩存，通過(guò)不斷換出換入而運(yùn)行大作業(yè)分進(jìn)程交換和部分交換（頁(yè)面交換和分段交換）提高內(nèi)存利用率，增加并發(fā)進(jìn)程數(shù)，提高系統(tǒng)效率交換使用的技術(shù)較多：換出進(jìn)程的選擇、交換時(shí)機(jī)的確定、需要一個(gè)盤(pán)交換區(qū)及管理、換入回內(nèi)存時(shí)位置的確定等3.連續(xù)存儲(chǔ)空間管理（1）單一連續(xù)存儲(chǔ)管理基本原理

將內(nèi)存劃分為系統(tǒng)區(qū)和用戶區(qū)；內(nèi)存中僅駐留一道程序，整個(gè)系統(tǒng)資源和用戶區(qū)只為一個(gè)用戶所獨(dú)占；僅適用于單用戶、單任務(wù)操作系統(tǒng)。

優(yōu)缺點(diǎn)簡(jiǎn)單、易實(shí)現(xiàn)僅適合單道程序，處理機(jī)和內(nèi)存不能充分利用（1）單一連續(xù)存儲(chǔ)管理（續(xù)1）主存空間的分配與回收主存空間的分配：系統(tǒng)區(qū)和用戶區(qū)

主存空間的回收：運(yùn)行結(jié)束，釋放主存空間

地址轉(zhuǎn)換與存儲(chǔ)保護(hù)：?jiǎn)斡脩暨B續(xù)存儲(chǔ)管理的地址轉(zhuǎn)換可以采用靜態(tài)重定位和動(dòng)態(tài)重定位兩種方法。

（1）單一連續(xù)存儲(chǔ)管理（續(xù)1）采用靜態(tài)重定位方法采用靜態(tài)重定位，程序執(zhí)行之前由裝入程序完成邏輯地址到物理地址的轉(zhuǎn)換。如圖所示。主要優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，無(wú)需硬件地址轉(zhuǎn)換機(jī)構(gòu)支持。

作業(yè)1裝入程序操作系統(tǒng)區(qū)作業(yè)1的程序和數(shù)據(jù)界限地址界限地址+邏輯地址（1）單一連續(xù)存儲(chǔ)管理（續(xù)1）采用動(dòng)態(tài)重定位方法設(shè)置一個(gè)定位寄存器，既用來(lái)指出主存中的系統(tǒng)區(qū)和用戶區(qū)的地址界限，又作為用戶區(qū)的基地址；通過(guò)裝入程序把程序裝入到從界限地址開(kāi)始的區(qū)域，但此時(shí)并不進(jìn)行地址轉(zhuǎn)換；程序執(zhí)行過(guò)程中動(dòng)態(tài)地將邏輯地址與定位寄存器中的值相加就可得到物理地址。

基本原理

預(yù)先把可分配的內(nèi)存空間分割成若干個(gè)連續(xù)區(qū)域，每一區(qū)域稱為分區(qū)每個(gè)分區(qū)的大小可以相同也可以不同，分區(qū)大小固定不變，每個(gè)分區(qū)裝一個(gè)且只能裝一個(gè)作業(yè)存儲(chǔ)分配：如果有一個(gè)空閑區(qū)，則分配給進(jìn)程（2）固定分區(qū)存儲(chǔ)管理（2）固定分區(qū)存儲(chǔ)管理（續(xù)1）主存空間的分配與回收

數(shù)據(jù)結(jié)構(gòu)與主存分區(qū)分配表(a)分區(qū)說(shuō)明表(b)存儲(chǔ)空間分配表分區(qū)號(hào)大小（K）起址地址（K）狀態(tài)1816Job121624031640Job243256Job3操作系統(tǒng)Job10Job2Job3016K24K40K56K（2）固定分區(qū)存儲(chǔ)管理（續(xù)2）固定式分區(qū)表

(a)分區(qū)號(hào)12345大小8

KB32

KB32

KB120

KB520

KB起始地址312

KB320

KB352

KB384

KB504

KB狀態(tài)在使用在使用在使用未用未用(b)操作系統(tǒng)504KB384KB352KB320KB312KB0520KB120KB32KB32KB8KB312KB固定式分區(qū)舉例固定式分區(qū)舉例

分區(qū)號(hào)分區(qū)容量作業(yè)容量剩余容量123458KB32KB32KB120KB520KB1KB9KB9KB33KB121KB7KB23KB23KB87KB399KB合計(jì)712KB173KB539KB操作系統(tǒng)504KB384KB352KB320KB312KB0520KB120KB32KB32KB8KB312KBJ1J2J3J4J5內(nèi)存利用率不高（2）固定分區(qū)存儲(chǔ)管理（續(xù)2）地址轉(zhuǎn)換與存儲(chǔ)保護(hù)采用靜態(tài)重定位方式。系統(tǒng)設(shè)置兩個(gè)寄存器：上界寄存器和下界寄存器。上界寄存器用來(lái)存放分區(qū)的低地址，即起始地址；下界寄存器用來(lái)存放分區(qū)的高地址，即末址。裝入程序在進(jìn)行地址轉(zhuǎn)換時(shí)，將CPU獲得的邏輯地址首先與上下界寄存器的值進(jìn)行比較，若超出上、下界寄存器的值，產(chǎn)生“地址越界”中斷信號(hào)，由相應(yīng)的中斷處理程序處理。運(yùn)行的作業(yè)在讓出處理器時(shí)，調(diào)度程序選擇另一個(gè)可運(yùn)行的作業(yè)，同時(shí)修改當(dāng)前運(yùn)行作業(yè)的分區(qū)號(hào)和上、下界寄存器的內(nèi)容，以保證處理器能控制作業(yè)在所在的分區(qū)內(nèi)正常運(yùn)行

（2）固定分區(qū)存儲(chǔ)管理（續(xù)3）管理特點(diǎn)

一個(gè)作業(yè)只能裝入一個(gè)分區(qū)。當(dāng)一個(gè)分區(qū)的大小不能滿足一個(gè)作業(yè)的要求時(shí)，該作業(yè)暫時(shí)不能裝入。通過(guò)對(duì)“分區(qū)分配表”的改寫(xiě)，來(lái)實(shí)現(xiàn)主存的分配與回收。簡(jiǎn)單、易行，適合多道程序設(shè)計(jì)。當(dāng)分區(qū)較大而作業(yè)較小時(shí)，容易形成碎片，造成主存空間的浪費(fèi)。這種方式分區(qū)總數(shù)固定，也限制了并發(fā)執(zhí)行的作業(yè)數(shù)目。

定義：在存儲(chǔ)分配過(guò)程中，分配給用戶而未被利用的那部分內(nèi)存，稱為內(nèi)存的“內(nèi)零頭”或“內(nèi)碎片”

（3）可變分區(qū)存儲(chǔ)管理基本原理內(nèi)存不是預(yù)先劃分好分區(qū)的，而是根據(jù)裝入作業(yè)的實(shí)際需要?jiǎng)討B(tài)地劃分存儲(chǔ)空間。分區(qū)的個(gè)數(shù)和大小是不固定的作業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來(lái)決定是否分配若有足夠的空間，則按需要分割一部分分區(qū)給該進(jìn)程；否則令其等待內(nèi)存空間（3）可變分區(qū)存儲(chǔ)管理（續(xù)1）主存空間的分配數(shù)據(jù)結(jié)構(gòu)已分配分區(qū)表未分配（空閑）分區(qū)表主存空間分配動(dòng)態(tài)分配三種分配算法：首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法（3）可變分區(qū)存儲(chǔ)管理（續(xù)2）分區(qū)號(hào)起址（K）大?。↘）狀態(tài)分區(qū)號(hào)起址（K）大?。↘）狀態(tài)118601162Job12346022410Job235632034016job34………4………5………5………圖5.8未分配分區(qū)表圖5.9已分配分區(qū)表分區(qū)表格式：申請(qǐng)分配一個(gè)xKB大小的分區(qū)置空閑區(qū)號(hào)f=1f大于最后一個(gè)空閑區(qū)號(hào)？空閑區(qū)可用？保存空閑區(qū)的起始地址空閑區(qū)f的大小≥xKB空閑區(qū)的狀態(tài)=空項(xiàng)修改空閑區(qū)的大小和起始地址在已分配表中找一個(gè)狀態(tài)=空項(xiàng)的分區(qū)號(hào)

P置分區(qū)P的大小為

xKB置分區(qū)起始地址置分區(qū)狀態(tài)為已分配返回一個(gè)分區(qū)號(hào)此次無(wú)法分配f+1fYYNN<>=可變分區(qū)中請(qǐng)求一個(gè)分區(qū)的流程首次（最先）適應(yīng)分配算法：未分配分區(qū)表按地址遞增的順序排列，每次分配時(shí)，從空閑分區(qū)表的第一個(gè)表目開(kāi)始順序查找空閑分區(qū)表，找到第一個(gè)能滿足作業(yè)長(zhǎng)度要求的空閑區(qū)，分割這個(gè)空閑區(qū)，把能夠滿足要求的空閑區(qū)分配給作業(yè)。該算法簡(jiǎn)單，盡可能地利用了低地址空間，把較大的空閑分區(qū)留在內(nèi)存高端，有利于大作業(yè)的分配。但低端分區(qū)產(chǎn)生過(guò)多的小地址碎片，每次分配時(shí)查找時(shí)間開(kāi)銷(xiāo)增大，降低了主存空間的利用率。該算法改進(jìn)后稱為首次循環(huán)適應(yīng)算法，它的分配和釋放的時(shí)間性能較好，使空閑分區(qū)分布得更均勻，但不易保留較大的空閑分區(qū)。（3）可變分區(qū)存儲(chǔ)管理（續(xù)3）（3）可變分區(qū)存儲(chǔ)管理（續(xù)4）最佳適應(yīng)分配算法未分配分區(qū)表按照分區(qū)的大小從小到大進(jìn)行排列，分配時(shí)，自表頭順序開(kāi)始查找到第一個(gè)滿足要求的空閑分區(qū)。保證不去分割更大的區(qū)域，使裝入大作業(yè)時(shí)比較容易得到滿足。該算法的特點(diǎn)是可以解決大作業(yè)的分配問(wèn)題；但是容易產(chǎn)生不可利用的小空閑區(qū)，降低了主存空間的利用率。最差（壞）適應(yīng)分配算法未分配分區(qū)表按照分區(qū)的大小從大到小進(jìn)行排列，分配時(shí)，只看第一個(gè)分區(qū)能否滿足作業(yè)要求，若可以，將該分區(qū)分配給作業(yè)使用，否則作業(yè)不能執(zhí)行。該算法的優(yōu)點(diǎn)是查找效率很高；可使剩下的空閑區(qū)不至于太小，對(duì)中、小作業(yè)有利，對(duì)于大作業(yè)不利。（3）可變分區(qū)存儲(chǔ)管理（續(xù)5）可變分區(qū)的分配和回收示例（3）可變分區(qū)存儲(chǔ)管理（續(xù)6）主存空間回收合并

當(dāng)某一塊歸還后，前后空間合并，修改內(nèi)存空閑塊表

考慮：上鄰、下鄰、上下相鄰、上下不相鄰情況1情況2情況3情況4…………作業(yè)B回收區(qū)P上鄰空閑區(qū)f1作業(yè)B上鄰空閑區(qū)f1下鄰空閑區(qū)f1回收區(qū)P回收區(qū)P回收區(qū)P作業(yè)A下鄰空閑區(qū)f1作業(yè)A…………圖5.10可變式分區(qū)回收的四種情況請(qǐng)求釋放一個(gè)分區(qū)P保存分區(qū)P的大小和起始地址置分區(qū)的狀態(tài)為空項(xiàng)分區(qū)P有鄰接的空閑區(qū)?修改新空閑區(qū)的大小起始地址和狀態(tài)返回修改空閑區(qū)的狀態(tài)修改新空閑區(qū)的大小和起始地址在未分配表中找一空表目置新空閑區(qū)大小和起始地址置空閑區(qū)狀態(tài)為可用在兩個(gè)空白區(qū)之間有一個(gè)空白區(qū)N可變分區(qū)中釋放一個(gè)分區(qū)的流程（3）可變分區(qū)存儲(chǔ)管理（續(xù)7）“碎片”問(wèn)題經(jīng)過(guò)一段時(shí)間的分配回收后，內(nèi)存中存在很多小的空閑塊。它們每一個(gè)都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為外碎片。

造成存儲(chǔ)資源的浪費(fèi)

注意：內(nèi)部碎片是指已經(jīng)被分配出去（能明確指出屬于哪個(gè)進(jìn)程）卻不能被利用的內(nèi)存空間；外碎片是指還沒(méi)有被分配出去（不屬于任何進(jìn)程），但由于太小以至無(wú)法將它分配給申請(qǐng)內(nèi)存的新進(jìn)程。

（3）可變分區(qū)存儲(chǔ)管理（續(xù)8）“碎片”問(wèn)題解決使用緊湊技術(shù)：

通過(guò)在內(nèi)存移動(dòng)程序，將所有小的空閑區(qū)域合并為大的空閑區(qū)域。見(jiàn)下圖。（又稱：緊縮技術(shù)，緊致技術(shù)，浮動(dòng)技術(shù)，搬家技術(shù)）

問(wèn)題：系統(tǒng)開(kāi)銷(xiāo)大移動(dòng)時(shí)機(jī)最好定在內(nèi)存某一分區(qū)不能滿足分配需求，但空閑區(qū)總和能滿足時(shí)（3）可變分區(qū)存儲(chǔ)管理（續(xù)9）（3）可變分區(qū)存儲(chǔ)管理（續(xù)10）地址轉(zhuǎn)換與存儲(chǔ)保護(hù)

地址轉(zhuǎn)換

采用動(dòng)態(tài)重定位方式裝入作業(yè)，需設(shè)置硬件地址轉(zhuǎn)換機(jī)構(gòu)，包括基址寄存器和限長(zhǎng)寄存器。地址轉(zhuǎn)換步驟如下：當(dāng)作業(yè)占用處理器時(shí)，進(jìn)程調(diào)度程序把該作業(yè)所占分區(qū)的起始地址送入基址寄存器，把作業(yè)所占分區(qū)的最大長(zhǎng)度送入限長(zhǎng)寄存器。作業(yè)執(zhí)行過(guò)程由硬件地址轉(zhuǎn)換機(jī)構(gòu)把邏輯地址轉(zhuǎn)換成物理地址。即當(dāng)取出一條指令后，把該指令中的邏輯地址與基址寄存器內(nèi)容相加得到物理地址。

（3）可變分區(qū)存儲(chǔ)管理（續(xù)11）存儲(chǔ)保護(hù)把新作業(yè)所占分區(qū)的始址和總長(zhǎng)度存入“基址寄存器”和“限長(zhǎng)寄存器”，這兩個(gè)專用寄存器中。

當(dāng)處理器執(zhí)行該作業(yè)的指令時(shí)必須核對(duì)表達(dá)式“始址<=絕對(duì)地址<=末址”是否成立。若成立，就執(zhí)行該指令，否則就產(chǎn)生“地址越界”中斷事件，停止執(zhí)行該指令。

（3）可變分區(qū)存儲(chǔ)管理（續(xù)12）管理特點(diǎn)可變式分區(qū)存儲(chǔ)管理方式有如下特點(diǎn)：有助于多道程序設(shè)計(jì)分區(qū)的長(zhǎng)度不是預(yù)先固定的，而是按作業(yè)的實(shí)際需求來(lái)劃分的。分區(qū)的個(gè)數(shù)也不是預(yù)先確定的，而是由裝入的作業(yè)數(shù)來(lái)決定的分區(qū)的大小由作業(yè)的大小確定，提高了主存的使用效率在主存分配過(guò)程中，會(huì)產(chǎn)生許多主存“碎片”，這種在所有分區(qū)之外新增的“碎片”稱作外部“碎片”，使主存空間仍有一定的浪費(fèi)

表5.1連續(xù)存儲(chǔ)空間分配算法比較分配方式有無(wú)內(nèi)碎片有無(wú)外碎片優(yōu)

點(diǎn)缺

點(diǎn)單一連續(xù)分配有無(wú)簡(jiǎn)單只能用在單用戶、單任務(wù)、單道或?qū)Ｓ玫牟僮飨到y(tǒng)固定分區(qū)分配有無(wú)用于多道程序系統(tǒng)的最簡(jiǎn)單的分配方案存儲(chǔ)空間浪費(fèi)較多首次適應(yīng)算法無(wú)有分區(qū)分配中最簡(jiǎn)單的方案，利于空白區(qū)合并低地址部分用得太多，高地址部分相對(duì)空閑，導(dǎo)致查找效率低循環(huán)首次適應(yīng)算法無(wú)有查找時(shí)間很少，內(nèi)存空間分布均勻會(huì)導(dǎo)致缺少大的空閑分區(qū)最佳適應(yīng)算法無(wú)有使得外部碎片都很小，對(duì)于一次分配來(lái)說(shuō)是最佳的。長(zhǎng)時(shí)間來(lái)看可能留下了很多難以利用的小空閑區(qū)最差適應(yīng)算法無(wú)有使得留下來(lái)的空閑區(qū)較大，便于下次利用過(guò)早用掉大的空閑區(qū)會(huì)導(dǎo)致以后難以找到足夠大的空閑區(qū)來(lái)滿足進(jìn)程動(dòng)態(tài)可重定位無(wú)有通過(guò)移動(dòng)，內(nèi)存利用率很高需要硬件支持地址轉(zhuǎn)換浪費(fèi)時(shí)間

4.非連續(xù)分配管理方式（1）分頁(yè)存儲(chǔ)管理基本原理頁(yè)面在分頁(yè)存儲(chǔ)管理中，將用戶作業(yè)的地址空間分成若干個(gè)大小相同的區(qū)域，稱為頁(yè)面或頁(yè)，頁(yè)面是從“0”開(kāi)始編號(hào)，每個(gè)頁(yè)內(nèi)地址也是相對(duì)于0編址。物理塊內(nèi)存空間也劃分為與頁(yè)的大小相等的若干個(gè)存儲(chǔ)塊，稱為物理塊或頁(yè)框（frame），并且采用同樣的方式為它們進(jìn)行編號(hào)，整個(gè)主存的塊是從0開(kāi)始編號(hào)，分別稱為0塊，1塊，…，n-1塊，塊內(nèi)地址也是相對(duì)于0編址。

（1）分頁(yè)存儲(chǔ)管理（續(xù)1）邏輯地址的表示用戶的邏輯地址從基址0開(kāi)始編址，即是相對(duì)地址。每個(gè)相對(duì)地址用一個(gè)數(shù)對(duì)（p,w）表示，其中：p是頁(yè)號(hào)w是頁(yè)內(nèi)地址，是該頁(yè)內(nèi)的偏移量210=1K211=2K212=4K

（1）分頁(yè)存儲(chǔ)管理（續(xù)2）注意:邏輯地址與頁(yè)號(hào)及頁(yè)內(nèi)偏移地址之間的關(guān)系PageNo=INT[Addr/PageLength]PageOffset=AddrMODPageLength舉例：對(duì)于1KB頁(yè)面，若給定邏輯地址2170B，則PageNo=2，PageOffset=122頁(yè)的劃分是由系統(tǒng)自動(dòng)完成的，對(duì)用戶是透明的。一頁(yè)的大小為2的整數(shù)次冪，地址的高位部分為頁(yè)號(hào)，低位部分為頁(yè)內(nèi)地址頁(yè)面大小選擇由機(jī)器的地址結(jié)構(gòu)所決定頁(yè)面大/小各有利弊210-212KB之間（1）分頁(yè)存儲(chǔ)管理（續(xù)3）實(shí)現(xiàn)的基本思想作業(yè)的邏輯地址是連續(xù)的。用戶在編制程序時(shí)只須使用順序的地址，而不必考慮如何去分頁(yè)。由地址轉(zhuǎn)換機(jī)構(gòu)和操作系統(tǒng)來(lái)決定頁(yè)面和主存塊的大小。用戶程序裝入主存時(shí)是按頁(yè)裝入，頁(yè)與頁(yè)之間的地址可以不連續(xù)，但頁(yè)內(nèi)地址是連續(xù)的。存儲(chǔ)地址由連續(xù)到離散的變化，即分配時(shí)，邏輯上相鄰的頁(yè)，物理上不一定相鄰的快邏輯地址空間計(jì)算舉例設(shè)一個(gè)邏輯地址空間有8頁(yè)，每頁(yè)1024字節(jié)，映射到32塊的物理內(nèi)存上。試問(wèn)：（1）邏輯地址空間需要多少位來(lái)表示？（2）物理地址空間需要多少位來(lái)表示？（1）邏輯地址空間需要13位來(lái)表示。其中頁(yè)號(hào)需要3位，因?yàn)?3=8；頁(yè)內(nèi)地址需要10位，因?yàn)?10=1024。（2）物理地址空間需要15位來(lái)表示。其中塊號(hào)需要5位，因?yàn)?5=32；塊內(nèi)地址需要10位，因?yàn)?10=1024。

（1）分頁(yè)存儲(chǔ)管理（續(xù)4）主存空間的分配與回收采用的數(shù)據(jù)結(jié)構(gòu)

頁(yè)表：系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)頁(yè)表，頁(yè)表給出邏輯頁(yè)號(hào)和具體內(nèi)存塊號(hào)相應(yīng)的關(guān)系。頁(yè)表放在內(nèi)存，屬于進(jìn)程的現(xiàn)場(chǎng)信息作業(yè)表：也叫主存分配表，包括作業(yè)名，作業(yè)對(duì)應(yīng)頁(yè)表的起始地址和頁(yè)表的長(zhǎng)度。內(nèi)存中的每個(gè)作業(yè)在作業(yè)表中有一個(gè)登記項(xiàng)。整個(gè)系統(tǒng)只有一張作業(yè)表。位示圖：空閑塊管理。頁(yè)式存儲(chǔ)管理以塊為單位分配主存空間，由于塊的大小是固定的，所以只要在主存分配表中指出哪些塊已分配和哪些塊未分配以及當(dāng)前剩余的空閑塊數(shù)。最簡(jiǎn)單的辦法是用一張“位示圖”構(gòu)成主存分配表。（1）分頁(yè)存儲(chǔ)管理（續(xù)5）（1）分頁(yè)存儲(chǔ)管理（續(xù)6）

（1）分頁(yè)存儲(chǔ)管理（續(xù)7）主存空間的分配系統(tǒng)初啟時(shí)，系統(tǒng)初始化位示圖，把操作系統(tǒng)已占用的物理塊的對(duì)應(yīng)位置成“1”，其余位全部置為“0”，空閑塊數(shù)置為當(dāng)前可用的空閑塊總數(shù)。

主存空間分配步驟如下：計(jì)算一個(gè)進(jìn)程所需要的總塊數(shù)N查位示圖：是否還有N個(gè)空閑塊如有足夠的空閑塊，則頁(yè)表長(zhǎng)度設(shè)為N，可填入作業(yè)表中；申請(qǐng)頁(yè)表區(qū)，把頁(yè)表始址填入作業(yè)表依次分配N(xiāo)個(gè)空閑塊，將塊號(hào)和頁(yè)號(hào)填入頁(yè)表修改位示圖在一個(gè)分頁(yè)存儲(chǔ)管理系統(tǒng)中，頁(yè)的大小為2KB。設(shè)主存容量為512KB，描述主存分配的位示圖如圖所示，0表示未分配，l表示已分配，此時(shí)系統(tǒng)要將一個(gè)9KB的作業(yè)裝入內(nèi)存，回答以下問(wèn)題：為作業(yè)分配內(nèi)存后，請(qǐng)給出該作業(yè)的頁(yè)表（分配內(nèi)存時(shí)首先分配內(nèi)存的低地址端）。分頁(yè)存儲(chǔ)管理有無(wú)碎片存在？若有，會(huì)存在什么碎片？為該作業(yè)分配內(nèi)存后，會(huì)產(chǎn)生零頭嗎？如果產(chǎn)生，碎片大小為多少？11111101111111111101110011100110000010111111111110000000000000001111100000101010…頁(yè)號(hào)塊號(hào)06118222323427分頁(yè)存儲(chǔ)管理有碎片存在，分頁(yè)存儲(chǔ)管理存在內(nèi)部碎片，為該作業(yè)分配內(nèi)存會(huì)產(chǎn)生大小為IKB的內(nèi)部碎片。

（1）分頁(yè)存儲(chǔ)管理（續(xù)8）地址轉(zhuǎn)換機(jī)構(gòu)由硬件實(shí)現(xiàn)，操作系統(tǒng)配合。關(guān)鍵在于頁(yè)號(hào)到物理塊號(hào)的轉(zhuǎn)換系統(tǒng)設(shè)置一對(duì)寄存器頁(yè)表始址寄存器

用于保存正在運(yùn)行進(jìn)程的頁(yè)表的始址頁(yè)表長(zhǎng)度寄存器

用于保存正在運(yùn)行進(jìn)程的頁(yè)表的長(zhǎng)度地址轉(zhuǎn)換過(guò)程見(jiàn)下圖地址轉(zhuǎn)換過(guò)程位移量進(jìn)程地址轉(zhuǎn)換機(jī)構(gòu)內(nèi)存邏輯地址頁(yè)表寄存器塊號(hào)頁(yè)框頁(yè)號(hào)塊號(hào)頁(yè)號(hào)塊號(hào)位移量+頁(yè)表始址頁(yè)表長(zhǎng)度頁(yè)表物理地址塊號(hào)位移量PCB頁(yè)表始址頁(yè)表長(zhǎng)度>越界中斷12345紅線部分的工作在進(jìn)程被調(diào)度時(shí)由調(diào)度程序完成絕對(duì)地址計(jì)算：塊號(hào)×塊長(zhǎng)＋位移量地址變換舉例1

某分頁(yè)系統(tǒng)的邏輯地址為16位，其中高6位為頁(yè)號(hào)，低10位為頁(yè)內(nèi)地址。請(qǐng)問(wèn)：（1）這樣的地址結(jié)構(gòu)一頁(yè)有多少字節(jié)？邏輯地址可有多少頁(yè)？一個(gè)作業(yè)最大的使用空間是多少？（2）邏輯地址2318、4096、850對(duì)應(yīng)的頁(yè)號(hào)、頁(yè)內(nèi)地址分別是多少？地址變換舉例1【解】（1）由于低10位為頁(yè)內(nèi)地址，尋址能力為：210=1024于是一頁(yè)有1024個(gè)字節(jié)（或1KB）。邏輯地址共有頁(yè)面26=64。一個(gè)作業(yè)最大的使用空間是：641024=64KB。（2）每頁(yè)大小為1KB，所以邏輯地址除以頁(yè)面大小，商為頁(yè)號(hào)，余數(shù)為頁(yè)內(nèi)地址。于是：邏輯地址2318：頁(yè)號(hào)為2，頁(yè)內(nèi)地址為270；邏輯地址4096：頁(yè)號(hào)為4，頁(yè)內(nèi)地址為0；邏輯地址850：頁(yè)號(hào)為0，頁(yè)內(nèi)地址為850。地址轉(zhuǎn)換舉例2頁(yè)式存儲(chǔ)系統(tǒng)的邏輯地址是由頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分組成，地址轉(zhuǎn)換過(guò)程如圖所示。假定頁(yè)面的大小為8K，計(jì)算圖中所示的十進(jìn)制邏輯地址9612經(jīng)過(guò)地址轉(zhuǎn)換后，形成的物理地址a應(yīng)為多少？

地址轉(zhuǎn)換舉例2【解】計(jì)算邏輯地址9612的頁(yè)號(hào)和頁(yè)內(nèi)位移為：頁(yè)號(hào)：9612/（8*1024）=1（取整）頁(yè)內(nèi)位移：9612－8*1024=1420通過(guò)頁(yè)表查詢，知1頁(yè)的內(nèi)容存放在3號(hào)物理塊中，根據(jù)題意頁(yè)面的大小為8K，將物理塊號(hào)與邏輯地址中的頁(yè)內(nèi)位移拼接，形成物理地址：

3*（8*1024）+1420=25996所以，十進(jìn)制邏輯地址9612經(jīng)過(guò)地址轉(zhuǎn)換后，形成的物理地址a是25996。地址變換舉例3某虛擬存儲(chǔ)器的用戶編程空間共32個(gè)頁(yè)面，每頁(yè)為1KB，內(nèi)存為16KB。假定某時(shí)刻一用戶頁(yè)表中已調(diào)入內(nèi)存的頁(yè)面的頁(yè)號(hào)和物理塊號(hào)的對(duì)照表如下：則邏輯地址0A5C（H）所對(duì)應(yīng)的物理地址是什么？頁(yè)號(hào)物理塊號(hào)051102437地址變換舉例3【解】0A5C(H)：00001010

01011100

2查表得：4

0100拼接得：0001001001011100125C(H)

邏輯地址0A5C（H）所對(duì)應(yīng)的物理地址是125C（H）

（1）分頁(yè)存儲(chǔ)管理（續(xù)9）相聯(lián)存儲(chǔ)器——快表快表（聯(lián)想存儲(chǔ)器）用途：為了提高地址映射速度(兩次讀內(nèi)存)保存正在運(yùn)行進(jìn)程的頁(yè)表的子集（部分頁(yè)表項(xiàng)）特點(diǎn)：按內(nèi)容并行查找快表表項(xiàng)：頁(yè)號(hào)；內(nèi)存塊號(hào)；具有塊表地址轉(zhuǎn)換過(guò)程

見(jiàn)下圖

（1）分頁(yè)存儲(chǔ)管理（續(xù)10）頁(yè)表始址頁(yè)表長(zhǎng)度邏輯地址L頁(yè)表寄存器頁(yè)表頁(yè)號(hào)頁(yè)內(nèi)地址頁(yè)號(hào)>頁(yè)表長(zhǎng)度+頁(yè)號(hào)塊號(hào)快表輸入寄存器物理地址db越界中斷b頁(yè)號(hào)塊號(hào)b圖5.17具有快表的地址轉(zhuǎn)換是否（1）分頁(yè)存儲(chǔ)管理（續(xù)11）層次化（多級(jí)）頁(yè)表現(xiàn)代計(jì)算機(jī)系統(tǒng)支持非常大的邏輯地址空間(232-264)，頁(yè)表變得龐大。例如，對(duì)于具有32位邏輯地址空間的分頁(yè)系統(tǒng)，規(guī)定頁(yè)面大小為4KB即212B，則每個(gè)進(jìn)程頁(yè)表的頁(yè)表項(xiàng)可達(dá)1M個(gè)；若同時(shí)設(shè)定頁(yè)表項(xiàng)大小為4B，則每個(gè)進(jìn)程僅頁(yè)表便需占用4MB內(nèi)存空間，且要求是連續(xù)的。解決方案多級(jí)頁(yè)表(將頁(yè)表本身也以頁(yè)面為單位進(jìn)行分頁(yè)，分成一張張的頁(yè)表頁(yè)

)或反置頁(yè)表一個(gè)簡(jiǎn)單的解決方法是使用兩層分頁(yè)方法，就是將頁(yè)表再分頁(yè)，如下圖所示。多級(jí)頁(yè)表舉例某計(jì)算機(jī)采用二級(jí)頁(yè)表的分頁(yè)存儲(chǔ)管理方式，按字節(jié)編址，頁(yè)的大小為210字節(jié)，頁(yè)表項(xiàng)大小為2字節(jié)，邏輯地址結(jié)構(gòu)為：頁(yè)目錄號(hào)頁(yè)號(hào)頁(yè)內(nèi)偏移量邏輯地址空間大小為216頁(yè)，則表示整個(gè)邏輯地址空間的頁(yè)目錄表中包含頁(yè)目錄表項(xiàng)的個(gè)數(shù)至少是（）。A、64B、128C、256D、512每個(gè)頁(yè)表中最多頁(yè)表項(xiàng)數(shù)=210/2=29，頁(yè)目錄表中最多項(xiàng)數(shù)=216/29=27=128分頁(yè)存儲(chǔ)管理特點(diǎn)

（1）程序和數(shù)據(jù)存放在不連續(xù)的主存空間，不必通過(guò)緊湊來(lái)解決“碎片”問(wèn)題。（2）通過(guò)位示圖和頁(yè)表來(lái)記錄主存的使用情況和每個(gè)作業(yè)的分配情況，當(dāng)主存很大，并且作業(yè)也很大時(shí)，位示圖和頁(yè)表都有可能占用較大的存儲(chǔ)空間。（3）要求有相應(yīng)的硬件支持，增加了系統(tǒng)成本，也增加了系統(tǒng)開(kāi)銷(xiāo)。如需要地址轉(zhuǎn)換機(jī)構(gòu)、快表等。（4）仍然存在不可利用的空間，最后一頁(yè)沒(méi)有放滿（頁(yè)內(nèi)碎片）等。頁(yè)的大小固定，不能隨程序的大小而變，對(duì)程序的共享和使用造成了許多困難。

（2）段式存儲(chǔ)管理

段式存儲(chǔ)管理方式的引入主要是為了滿足程序員在編程和使用上的要求?；舅枷胗脩舫绦騽澐职闯绦蜃陨淼倪壿嬯P(guān)系劃分為若干個(gè)程序段，每個(gè)程序段都有一個(gè)段名，且有一個(gè)段號(hào)。段號(hào)從0開(kāi)始，每一段也從0開(kāi)始編址，段內(nèi)地址是連續(xù)的邏輯地址表示實(shí)現(xiàn)可以基于可變分區(qū)存儲(chǔ)管理的原理，但是以段為單位，不是以作業(yè)為單位。

（2）段式存儲(chǔ)管理（續(xù)1）主存空間的分配與回收

采用的數(shù)據(jù)結(jié)構(gòu)

空閑分區(qū)表：整個(gè)主存設(shè)置一張空閑分區(qū)表,用于記錄主存中空閑區(qū)的序號(hào)、起始地址和大小。段表：系統(tǒng)為每個(gè)進(jìn)入內(nèi)存的作業(yè)建一張段表，記錄了段號(hào)，段的首（地）址和長(zhǎng)度之間的關(guān)系，放在內(nèi)存屬于進(jìn)程的現(xiàn)場(chǎng)信息（2）段式存儲(chǔ)管理（續(xù)2）作業(yè)表

整個(gè)系統(tǒng)設(shè)置一張作業(yè)表，記錄主存中各作業(yè)的作業(yè)名、段表始址和段表長(zhǎng)度，段表長(zhǎng)度為段表中的最大序號(hào)。（2）段式存儲(chǔ)管理（續(xù)3）主存空間的分配作業(yè)分配時(shí)用作業(yè)的長(zhǎng)度與空閑分區(qū)表的所有記錄的長(zhǎng)度之和進(jìn)行比較。若大于則不能裝入。否則，裝入該作業(yè)，為該作業(yè)創(chuàng)建一張段表。根據(jù)每個(gè)作業(yè)段的大小在空閑分區(qū)表中查找滿足其大小的空閑塊，把該段裝入，并在段表中填入該段的段長(zhǎng)和段的起始地址；如果此空閑塊可以分割，則剩余部分仍作為空閑分區(qū)登記在空閑分區(qū)表中，直至所有段分配完畢。若找不到足夠大的空閑分區(qū)，可以采用緊湊技術(shù)，合并分散的空閑區(qū)后，再裝入該作業(yè)段。最后，在主存分配表中，登記該作業(yè)段表的起始地址和段表的長(zhǎng)度。（2）段式存儲(chǔ)管理（續(xù)4）主存空間的回收當(dāng)作業(yè)運(yùn)行結(jié)束時(shí)，根據(jù)該作業(yè)段表的每一條記錄，去修改空閑分區(qū)表。修改的方式與可變分區(qū)回收主存空間相同。然后刪除該作業(yè)的段表和主存分配表中該作業(yè)的記錄。

（2）段式存儲(chǔ)管理（續(xù)5）地址轉(zhuǎn)換機(jī)構(gòu)系統(tǒng)設(shè)置一對(duì)寄存器段表始址寄存器：

用于保存正在運(yùn)行進(jìn)程的段表的始址段表長(zhǎng)度寄存器

用于保存正在運(yùn)行進(jìn)程的段表的長(zhǎng)度地址變換見(jiàn)下圖相聯(lián)存儲(chǔ)器——快表

快表項(xiàng)目：段號(hào)；段始址；段長(zhǎng)度地址越界段號(hào)>段表長(zhǎng)度段號(hào)S段內(nèi)位移W段表始址段表長(zhǎng)度邏輯地址段表寄存器+段表B+W+段號(hào)0Sn段長(zhǎng)基址W>C...:...............主存......C............B......物理地址0:B+W圖5.23段式管理地址轉(zhuǎn)換過(guò)程地址越界是是否否S（2）段式存儲(chǔ)管理（續(xù)6）分段管理舉例1某段表內(nèi)容如下：

試問(wèn)：[2,154],[3,2049]的實(shí)際物理地址為多少？段號(hào)段首地址段長(zhǎng)度0120k40k1760k30k2480k20k3370k2k分段管理舉例1【解】由[2,154]表示可知，訪問(wèn)地址為2段，段內(nèi)地址為154。根據(jù)題意，2段的段首地址為480K，段長(zhǎng)20K，故[2,154]訪問(wèn)地址為：480K+154=480×1024＋154。由[3,2049]表示可知，訪問(wèn)地址為3段，段內(nèi)地址2049。根據(jù)題意，3段的段首地址為370K，段長(zhǎng)2K，[3,2049]的段內(nèi)地址為2049，超過(guò)段表中規(guī)定的段長(zhǎng)2K（2048），故產(chǎn)生越界中斷。

（2）段式存儲(chǔ)管理（續(xù)7）段的共享與保護(hù)段的共享

通過(guò)不同作業(yè)段表中的項(xiàng)指向同一個(gè)段基址來(lái)實(shí)現(xiàn)的。于是，幾道作業(yè)共享的程序可放在一個(gè)段中，供各道作業(yè)共享具有相同的基址/限長(zhǎng)值就行了。段的保護(hù)主要進(jìn)行地址越界保護(hù)和共享段的存取方式控制保護(hù)。地址越界保護(hù)是利用段表中的段長(zhǎng)和邏輯地址中的段內(nèi)相對(duì)地址相比較共享段的存取方式控制保護(hù)主要是用訪問(wèn)權(quán)限進(jìn)行訪問(wèn)共享段。

（2）段式存儲(chǔ)管理（續(xù)8）段式存儲(chǔ)管理的特點(diǎn)消除了碎片。沒(méi)有內(nèi)碎片，仍然存在外碎片，若采用移動(dòng)技術(shù)合并空閑區(qū)，會(huì)增加系統(tǒng)開(kāi)銷(xiāo)。便于兩個(gè)或兩個(gè)以上的作業(yè)共享同一子程序。硬件支持更多，成本較高。另外，段的大小受主存可用空閑區(qū)大小的限制。分頁(yè)和分段存儲(chǔ)管理的比較相似之處實(shí)現(xiàn)機(jī)制（地址映射、離散分配）區(qū)別分頁(yè)是信息的物理單位，與源程序的邏輯結(jié)構(gòu)無(wú)關(guān)，用戶不可見(jiàn)。分段是信息的邏輯單位，由源程序的邏輯結(jié)構(gòu)所決定，用戶可見(jiàn)，段長(zhǎng)可根據(jù)用戶需要來(lái)規(guī)定，段起始地址可以從任何主存地址開(kāi)始。頁(yè)的大小固定且由系統(tǒng)確定，把邏輯地址劃分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分，是由機(jī)器硬件實(shí)現(xiàn)的，因而一個(gè)系統(tǒng)只能有一種大小的頁(yè)面。段的長(zhǎng)度卻不固定，決定于用戶所編寫(xiě)的程序，通常由編譯程序在對(duì)源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來(lái)劃分。分頁(yè)的作業(yè)地址空間是一維的。分段的作業(yè)地址空間是二維的，程序員在標(biāo)識(shí)一個(gè)地址時(shí)，需給出段名和段內(nèi)地址。（3）段頁(yè)式存儲(chǔ)管理段頁(yè)式存儲(chǔ)管理方式的引入分頁(yè)與分段存儲(chǔ)管理各有優(yōu)缺點(diǎn)分頁(yè)系統(tǒng)能有效地提高內(nèi)存利用率分段系統(tǒng)則能很好地滿足用戶需要分頁(yè)與分段存儲(chǔ)管理各取所長(zhǎng)、有機(jī)結(jié)合既具有分段系統(tǒng)便于實(shí)現(xiàn)、分段可共享、易于保護(hù)、可動(dòng)態(tài)鏈接等一系列優(yōu)點(diǎn)；又能像分頁(yè)系統(tǒng)那樣很好地解決內(nèi)存的外部碎片問(wèn)題以及為各個(gè)分段離散地分配內(nèi)存等問(wèn)題

（3）段頁(yè)式存儲(chǔ)管理（續(xù)1）基本思想用戶程序劃分：按段式劃分（對(duì)用戶來(lái)講，按段的邏輯關(guān)系進(jìn)行劃分）；對(duì)系統(tǒng)講，按頁(yè)劃分每一段邏輯地址表示

內(nèi)存劃分：按頁(yè)式存儲(chǔ)管理方案內(nèi)存分配：以頁(yè)為單位進(jìn)行分配主程序段04K8K12K15K16K子程序段04K8K數(shù)據(jù)段04K8K10K12K段號(hào)段內(nèi)頁(yè)號(hào)頁(yè)內(nèi)地址

（3）段頁(yè)式存儲(chǔ)管理（續(xù)2）管理段表：記錄了每一段的頁(yè)表始址和頁(yè)表長(zhǎng)度頁(yè)表：記錄了邏輯頁(yè)號(hào)與內(nèi)存塊號(hào)的對(duì)應(yīng)關(guān)系（每一段有一個(gè)，一個(gè)程序可能有多個(gè)頁(yè)表）空閑塊管理：同頁(yè)式管理分配：同頁(yè)式管理利用段表和頁(yè)表實(shí)現(xiàn)地址映射段號(hào)狀態(tài)頁(yè)表大小頁(yè)表始址0111213041段表第0段頁(yè)表內(nèi)存頁(yè)號(hào)狀態(tài)物理塊號(hào)0111213041第1段頁(yè)表…頁(yè)號(hào)狀態(tài)物理塊號(hào)0111213041段表大小段表始址段表寄存器段頁(yè)式系統(tǒng)的地址變換結(jié)構(gòu)虛擬存儲(chǔ)器管理1.虛擬存儲(chǔ)器的概念問(wèn)題的提出“一次性”全部裝入的問(wèn)題前述各種存儲(chǔ)管理方式均要求在作業(yè)運(yùn)行前將作業(yè)全部裝入內(nèi)存，而實(shí)際上許多作業(yè)在每次運(yùn)行時(shí)，并非用到其全部程序作業(yè)常駐內(nèi)存的問(wèn)題作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存直至作業(yè)運(yùn)行結(jié)束，其中因輸入輸出操作尚未完成而處于長(zhǎng)期等待狀態(tài)的運(yùn)行進(jìn)程或某些一次性運(yùn)行程序?qū)氋F的內(nèi)存資源的占據(jù)來(lái)說(shuō)是不合理的問(wèn)題后果使一些需要運(yùn)行的作業(yè)無(wú)法裝入運(yùn)行，從而嚴(yán)重降低內(nèi)存利用率和減少系統(tǒng)吞吐量。1.虛擬存儲(chǔ)器的概念（續(xù)1）虛擬存儲(chǔ)器技術(shù)要點(diǎn)作業(yè)部分裝入內(nèi)存即可啟動(dòng)運(yùn)行其余部分暫留磁盤(pán)程序執(zhí)行頁(yè)段訪問(wèn)已調(diào)入內(nèi)存則直接訪問(wèn)尚未調(diào)入內(nèi)存則缺頁(yè)/段中斷及請(qǐng)求調(diào)入頁(yè)段置換功能技術(shù)效果大用戶程序在小內(nèi)存空間的運(yùn)行多道程序并發(fā)度的提高1.虛擬存儲(chǔ)器的概念（續(xù)2）虛擬存儲(chǔ)器的定義是指僅把作業(yè)的一部分裝入內(nèi)存便可運(yùn)行作業(yè)的存儲(chǔ)器系統(tǒng)。是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。實(shí)際上，用戶看到的大容量只是一種感覺(jué)，是虛的，故而得名虛擬存儲(chǔ)器。虛擬存儲(chǔ)邏輯容量也不是無(wú)限的，它的最大的容量是由計(jì)算機(jī)的地址結(jié)構(gòu)決定。1.虛擬存儲(chǔ)器的概念（續(xù)3）局部性原理虛擬存儲(chǔ)器的理論依據(jù)是程序的局部性.局部性原理是：在一段時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分；相應(yīng)地，它所訪問(wèn)的存儲(chǔ)空間也局限于某個(gè)區(qū)域內(nèi)。那么程序?yàn)槭裁磿?huì)出現(xiàn)局部性規(guī)律呢？原因可以歸結(jié)為以下幾點(diǎn)：程序在執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過(guò)程調(diào)用指令外，大多數(shù)仍是順序執(zhí)行的。子程序調(diào)用將會(huì)使程序的執(zhí)行由一部分內(nèi)存區(qū)域轉(zhuǎn)至另一部分區(qū)域。但在大多數(shù)情況下，過(guò)程調(diào)用的深度都不超過(guò)5。程序中存在許多循環(huán)結(jié)構(gòu)，循環(huán)體中的指令被多次執(zhí)行。程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，如對(duì)連續(xù)的存儲(chǔ)空間——數(shù)組的訪問(wèn)，往往局限于很小的范圍內(nèi)。1.虛擬存儲(chǔ)器的概念（續(xù)4）局限性表現(xiàn)為：

時(shí)間局限性：如果程序中的某條指令一旦執(zhí)行，則不久的將來(lái)該指令可能再次被執(zhí)行；如果某個(gè)存儲(chǔ)單元被訪問(wèn)，則不久以后該存儲(chǔ)單元可能再次被訪問(wèn)。產(chǎn)生時(shí)間局限性的典型原因是在程序中存在著大量的循環(huán)操作?？臻g局限性：一旦程序訪問(wèn)了某個(gè)存儲(chǔ)單元，則在不久的將來(lái)，其附近的存儲(chǔ)單元也最有可能被訪問(wèn)。即程序在一段時(shí)間內(nèi)所訪問(wèn)的地址，可能集中在一定的范圍內(nèi)，其典型原因是程序是順序執(zhí)行的。1.虛擬存儲(chǔ)器的概念（續(xù)5）引入虛擬存儲(chǔ)技術(shù)的好處可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序可在內(nèi)存中容納更多程序并發(fā)執(zhí)行不必影響編程時(shí)的程序結(jié)構(gòu)（與覆蓋技術(shù)比較）提供給用戶可用的虛擬內(nèi)存空間通常大于物理內(nèi)存(realmemory)1.虛擬存儲(chǔ)器的概念（續(xù)6）虛擬存儲(chǔ)技術(shù)的特征離散性：指在內(nèi)存分配時(shí)采用離散的分配方式，它是虛擬存儲(chǔ)器的最基本的特征。多次性：指將一個(gè)作分成多次調(diào)入內(nèi)存。多次性是虛擬存儲(chǔ)器最重要的特征。對(duì)換性：指允許在作業(yè)的運(yùn)行過(guò)程中將暫不使用的程序與數(shù)據(jù)從內(nèi)存調(diào)至對(duì)換區(qū)，待以后需要時(shí)再調(diào)入內(nèi)存。提高內(nèi)存利用率。虛擬性：指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。虛擬存儲(chǔ)器實(shí)現(xiàn)方式請(qǐng)求分頁(yè)系統(tǒng)請(qǐng)求分段系統(tǒng)請(qǐng)求段頁(yè)式系統(tǒng)

2.請(qǐng)求頁(yè)式存儲(chǔ)管理（1）基本思想在進(jìn)程開(kāi)始運(yùn)行之前，不是裝入全部頁(yè)面，而是裝入一個(gè)或零個(gè)頁(yè)面，之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其它頁(yè)面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁(yè)面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁(yè)面，以便裝入新的頁(yè)面

（2）頁(yè)表表項(xiàng)設(shè)計(jì)頁(yè)號(hào)、狀態(tài)位、內(nèi)存塊號(hào)、訪問(wèn)位、修改位等狀態(tài)位P：標(biāo)識(shí)該頁(yè)面是否已調(diào)入內(nèi)存中訪問(wèn)位A：記錄該頁(yè)面最近被訪問(wèn)的情況修改位M：記錄該頁(yè)面內(nèi)容被調(diào)入內(nèi)存后是否被修改過(guò)。外存地址：指出該頁(yè)在外存上的地址狀態(tài)位P訪問(wèn)位A修改位M物理塊號(hào)外存地址頁(yè)號(hào)圖5.27請(qǐng)求分頁(yè)存儲(chǔ)管理的頁(yè)表L1，1KB+aA1，2KB+b006802000塊1

塊2

塊3

塊4

塊5

塊6塊7

塊8塊9塊02KB3KB4KB5KB6KB7KB8KB9KB5060塊號(hào)狀態(tài)204070803090-1-1作業(yè)1作業(yè)2作業(yè)3L1,1KB+aA1,2KB+b00680200006151000101200123作業(yè)4地址空間頁(yè)面變換表塊號(hào)0/1頁(yè)號(hào)狀態(tài)0在內(nèi)存1不在內(nèi)存011121315存儲(chǔ)空間01KB01KB2KB001001041KB1KB+a2KB2KB+b3KB（3）地址變換機(jī)構(gòu)

請(qǐng)求分頁(yè)系統(tǒng)中的地址變換機(jī)構(gòu)，是在分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)的基礎(chǔ)上，再為實(shí)現(xiàn)虛擬存儲(chǔ)器而增加了某些功能所形成的，如產(chǎn)生和處理缺頁(yè)中斷，以及從內(nèi)存中換出一頁(yè)的功能等等，下圖給出了請(qǐng)求分頁(yè)系統(tǒng)的地址變換過(guò)程。

在地址轉(zhuǎn)換中，如果頁(yè)表表項(xiàng)位的值是1，即為pagefault（缺頁(yè)）請(qǐng)求分頁(yè)系統(tǒng)地址變換過(guò)程程序請(qǐng)求訪問(wèn)一頁(yè)CPU檢索快表找到否？訪問(wèn)頁(yè)表是否頁(yè)在內(nèi)存？否產(chǎn)生缺頁(yè)中斷請(qǐng)求調(diào)頁(yè)是修改頁(yè)表對(duì)應(yīng)頁(yè)表項(xiàng)引用位和修改位形成物理地址地址變換結(jié)束頁(yè)號(hào)有效？是否越界中斷修改快表執(zhí)行一條指令形成有效地址計(jì)算頁(yè)號(hào)該頁(yè)在實(shí)存嗎？缺頁(yè)中斷入口有空閑的實(shí)頁(yè)碼？出頁(yè)修改頁(yè)表該頁(yè)修改？復(fù)制到輔存取出保存的頁(yè)號(hào)入頁(yè)找出磁盤(pán)地址修改頁(yè)表重新執(zhí)行被中斷的指令取下一條指令取數(shù)據(jù)完成該指令硬件軟件YNNYYN

（4）缺頁(yè)中斷（PageFault）處理在地址映射過(guò)程中，在頁(yè)表中發(fā)現(xiàn)所要訪問(wèn)的頁(yè)不在內(nèi)存，則產(chǎn)生缺頁(yè)中斷。操作系統(tǒng)接到此中斷信號(hào)后，就調(diào)出缺頁(yè)中斷處理程序，根據(jù)頁(yè)表中給出的外存地址，將該頁(yè)調(diào)入內(nèi)存，使作業(yè)繼續(xù)運(yùn)行下去如果內(nèi)存中有空閑塊，則分配一頁(yè)，將新調(diào)入頁(yè)裝入內(nèi)存，并修改頁(yè)表中相應(yīng)頁(yè)表項(xiàng)目的修改位及相應(yīng)的內(nèi)存塊號(hào)若此時(shí)內(nèi)存中沒(méi)有空閑塊，則要淘汰某頁(yè)，若該頁(yè)在內(nèi)存期間被修改過(guò)，則要將其寫(xiě)回外存

（4）缺頁(yè)中斷處理（續(xù)）缺頁(yè)中斷與一般中斷的區(qū)別：缺頁(yè)中斷在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)，而一般中斷在一條指令執(zhí)行完后檢查和處理中斷信號(hào)。缺頁(yè)中斷返回到該指令的開(kāi)始重新執(zhí)行該指令，而一般中斷返回到該指令的下一條指令執(zhí)行。一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷。654123頁(yè)面copyATOBB:A:

3.頁(yè)面置換算法

頁(yè)面置換—找到內(nèi)存中并沒(méi)有使用的一些頁(yè)，將它換出（1）頁(yè)面調(diào)入策略為能使進(jìn)程運(yùn)行，必須事先將一部分要執(zhí)行的程序和數(shù)據(jù)調(diào)入內(nèi)存。調(diào)入頁(yè)面的時(shí)機(jī)

預(yù)調(diào)頁(yè)策略：是一種主動(dòng)的缺頁(yè)調(diào)入策略，即將那些預(yù)計(jì)在不久的將來(lái)會(huì)被訪問(wèn)的程序或數(shù)據(jù)所在的頁(yè)面，預(yù)先調(diào)入內(nèi)存。由于預(yù)測(cè)的準(zhǔn)確率不高（50%），所以這種策略主要用于進(jìn)程的首次調(diào)入。有的系統(tǒng)將預(yù)調(diào)頁(yè)策略用于請(qǐng)求調(diào)頁(yè)（1）頁(yè)面調(diào)入策略（續(xù)1）請(qǐng)求調(diào)頁(yè)策略：是指當(dāng)進(jìn)程在運(yùn)行中發(fā)生缺頁(yè)時(shí)，就立即提出請(qǐng)求，由系統(tǒng)將缺頁(yè)調(diào)入內(nèi)存。目前的虛擬存儲(chǔ)器中，大多采用此策略。但這種策略在調(diào)頁(yè)時(shí)須花費(fèi)較大的系統(tǒng)開(kāi)銷(xiāo)，如需頻繁啟動(dòng)磁盤(pán)I/O。（1）頁(yè)面調(diào)入策略（續(xù)2）從何處調(diào)入頁(yè)面在虛擬存儲(chǔ)系統(tǒng)中，外存（硬盤(pán)）常常被分成兩部分；文件區(qū)（用于存放文件）和對(duì)換區(qū)（用于存放對(duì)換頁(yè)面）。通常，對(duì)換區(qū)（連續(xù)分配）的磁盤(pán)I/O速度比文件區(qū)（離散分配）要高。每當(dāng)進(jìn)程發(fā)出缺頁(yè)請(qǐng)求時(shí)，系統(tǒng)應(yīng)從何處將缺頁(yè)調(diào)入內(nèi)存呢？在UNIX系統(tǒng)中，對(duì)于從未運(yùn)行過(guò)的頁(yè)面，都應(yīng)從硬盤(pán)文件區(qū)調(diào)入；對(duì)于曾經(jīng)運(yùn)行過(guò)而又被換出的頁(yè)面，可以從對(duì)換區(qū)調(diào)入；對(duì)于共享頁(yè)面，該頁(yè)面可能已由其它進(jìn)程調(diào)入內(nèi)存，此時(shí)就無(wú)須再?gòu)膶?duì)換區(qū)調(diào)入。（2）頁(yè)面置換算法缺頁(yè)率假定作業(yè)Ji共有m頁(yè)，系統(tǒng)分配給它的主存塊為n塊，這里m>n。開(kāi)始時(shí)，主存沒(méi)有裝入任何一頁(yè)的信息。如果作業(yè)Ji在運(yùn)行中成功訪問(wèn)的次數(shù)為S，不成功的訪問(wèn)次數(shù)為F(產(chǎn)生缺頁(yè)中斷的次數(shù))，則作業(yè)執(zhí)行過(guò)程中總的訪問(wèn)次數(shù)為A.A=S（成功訪問(wèn)的次數(shù)）+F（不成功的訪問(wèn)次數(shù)）作業(yè)Ji執(zhí)行過(guò)程中的缺頁(yè)率f=F/A。

需要一個(gè)最小的缺頁(yè)率?。。。?）頁(yè)面置換算法頁(yè)面置換算法有：最佳算法(OPT,optimal)先進(jìn)先出算法(FIFO)Belady現(xiàn)象最近最久未使用算法(LRU,LeastRecentlyUsed)簡(jiǎn)單時(shí)鐘算法

最佳頁(yè)面置換算法理想淘汰算法—最佳頁(yè)面算法（OPT）它是一種理想化的算法，性能最好，但在實(shí)際上難于實(shí)現(xiàn)。即選擇那些永不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面置換出去。但是要確定哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，目前來(lái)說(shuō)是很難估計(jì)的，所以該算法通常用來(lái)評(píng)價(jià)其它算法。實(shí)現(xiàn)？作用？

先進(jìn)先出頁(yè)面淘汰算法先進(jìn)先出頁(yè)面淘汰算法（FIFO）先進(jìn)先出算法的基本思想是，總是先淘汰那些駐留在主存時(shí)間最長(zhǎng)的頁(yè)面，即先進(jìn)入主存的頁(yè)面先被淘汰。其理由是：最早調(diào)入主存的頁(yè)面，其不再被訪問(wèn)的可能性最大，這種算法實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單。

對(duì)照：超市撤換商品替換指針2451（指向最老的一頁(yè)）頁(yè)號(hào)最近最久未使用頁(yè)面淘汰算法最近最久未使用頁(yè)面淘汰算法（LRU——LeastRecentlyUsed）選擇最后一次訪問(wèn)時(shí)間距離當(dāng)前時(shí)間最長(zhǎng)的一頁(yè)并淘汰之即淘汰沒(méi)有使用的時(shí)間最長(zhǎng)的頁(yè)實(shí)現(xiàn)代價(jià)很高

時(shí)間戳或硬件方法簡(jiǎn)單CLOCK算法CLOCK算法是LRU算法的近似算法。CLOCK算法給每個(gè)頁(yè)面設(shè)置一個(gè)訪問(wèn)位，標(biāo)識(shí)該頁(yè)最近有沒(méi)有被訪問(wèn)過(guò)，再將內(nèi)存中的所有頁(yè)面通過(guò)一個(gè)指針鏈接成一個(gè)循環(huán)隊(duì)列。當(dāng)程序需要訪問(wèn)鏈表中存在的頁(yè)面時(shí)，該頁(yè)面的訪問(wèn)位被置為1；若程序要訪問(wèn)的頁(yè)面在鏈表中不存在，那就需要淘汰內(nèi)存中的一個(gè)頁(yè)面，于是一個(gè)指針p就從上次被淘汰頁(yè)面的下一個(gè)位置開(kāi)始順序地去遍歷這個(gè)循環(huán)鏈表，當(dāng)指針p指向的頁(yè)面的訪問(wèn)位為1時(shí)，就重新將它置為0，暫不換出，而給該頁(yè)第二次駐留內(nèi)存的機(jī)會(huì)，指針p再向下移動(dòng)，當(dāng)指針p所指的頁(yè)面的訪問(wèn)位為0時(shí)，就選擇這一頁(yè)面淘汰，若遍歷了一遍鏈表仍沒(méi)有找到可以淘汰的頁(yè)面，則繼續(xù)遍歷下去。由于該算法是循環(huán)地檢查各頁(yè)面的使用情況，故稱為CLOCK算法。實(shí)現(xiàn)流程圖例1在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，假定系統(tǒng)分配給一個(gè)作業(yè)的物理塊數(shù)為3，并且此作業(yè)的頁(yè)面走向依次為3、4、2、6、4、3、7、4、3、6、3、4、8、4、6，根據(jù)上述OPT、FIFO和LRU算法的思想，可分別計(jì)算它們的缺頁(yè)次數(shù)，見(jiàn)表5.2、表5.3和表5.4。表5.2OPT性能分析（M=3）頁(yè)面訪問(wèn)次序342643743634846

333333333333888內(nèi)存塊數(shù)=3

44444444444444

2666777666666是否缺頁(yè)√√√√

√

√

√

表5.3FIFO性能分析（M=3）頁(yè)面訪問(wèn)次序342643743634846

332663744633846內(nèi)存塊數(shù)=3

44226377466384

3442633744638是否缺頁(yè)√√√√

√√√

√√

√√√表5.4LRU性能分析（M=3）頁(yè)面訪問(wèn)次序342643743634846

342643743634846內(nèi)存塊數(shù)=3

34264374363484

3426437446338是否缺頁(yè)√√√√

√√

√

√

√例2某程序在內(nèi)存中分配m頁(yè)初始為空，頁(yè)面走向?yàn)镻=4,3,2,1,4,3,5,4,3,2,1,5。當(dāng)m=3，m=4時(shí)缺頁(yè)中斷分別為多少？用FIFO算法計(jì)算缺頁(yè)次數(shù)及缺頁(yè)率FIFO性能分析例(M=3)

FIFO性能分析例(M=4)m=3時(shí)，缺頁(yè)中斷9次，f=9/12=75%m=4時(shí)，缺頁(yè)中斷10次，f=10/12=83%注：FIFO頁(yè)面淘汰算法會(huì)產(chǎn)生異常現(xiàn)象（Belady現(xiàn)象），即：當(dāng)分配給進(jìn)程的物理頁(yè)面數(shù)增加時(shí)，缺頁(yè)次數(shù)反而增加（3）影響缺頁(yè)次數(shù)的因素缺頁(yè)率是衡量頁(yè)面置換算法的重要指標(biāo)。通常缺頁(yè)率受以下因素的影響：頁(yè)面置換算法：其優(yōu)劣影響缺頁(yè)中斷次數(shù)。主存物理塊的數(shù)目：通常情況下，其數(shù)目越多，缺頁(yè)率越低。頁(yè)面大?。喝绻麆澐猪?yè)面大，缺頁(yè)率就低；反之，缺頁(yè)率就高。程序特性：編程方法對(duì)缺頁(yè)中斷次數(shù)有影響。例3內(nèi)存分配一頁(yè)，初始時(shí)第一頁(yè)在內(nèi)存；頁(yè)面大小為128個(gè)整數(shù)；矩陣A128×128按行存放.程序編制方法1：Forj:=1to128Fori:=1to128A[i,j]:=0;程序編制方法2：Fori:=1to128Forj:=1to128A[i,j]:=0;4.頁(yè)面分配策略每個(gè)進(jìn)程所需要的最少的頁(yè)的數(shù)目根據(jù)不同的系統(tǒng)不一樣1)最少物理塊數(shù)在為進(jìn)程分配物理塊時(shí)，首先應(yīng)該考慮的問(wèn)題是：能保證進(jìn)程能正常運(yùn)行所需的最少物理塊數(shù)（稱為最小物理塊數(shù)）。若系統(tǒng)為某進(jìn)程所分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無(wú)法運(yùn)行，這取決于指令的格式、功能和尋址方式。4.頁(yè)面分配策略（續(xù)1）2)頁(yè)面的分配和置換策略

在請(qǐng)求分頁(yè)系統(tǒng)中，可采取固定和可變分配策略。在進(jìn)行置換時(shí)，也可采取全局置換和局部置換。于是可組合成以下三種策略：固定分配局部置換策略：它基于進(jìn)程的類(lèi)型（交互型或批處理型等），或根據(jù)程序員、系統(tǒng)管理員的建議，為每個(gè)進(jìn)程分配一固定頁(yè)數(shù)的內(nèi)存空間，在整個(gè)運(yùn)行期間都不再改變。如果進(jìn)程在運(yùn)行中發(fā)現(xiàn)缺頁(yè)，則只能從該進(jìn)程在內(nèi)存的固定頁(yè)面中選出一頁(yè)換出，然后再調(diào)入另一頁(yè)，保證分配給該進(jìn)程的內(nèi)存空間不變。4.頁(yè)面分配策略（續(xù)2）可變分配全局置換策略系統(tǒng)為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，而OS本身也保持一個(gè)空閑物理塊隊(duì)列。當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁(yè)時(shí)，由系統(tǒng)從空閑物理塊隊(duì)列中，取出一物理塊分配給該進(jìn)程，并將欲調(diào)入的缺頁(yè)裝入其中。當(dāng)空閑物理塊隊(duì)列中的物理塊用完時(shí)，OS才能從內(nèi)存中選擇一頁(yè)調(diào)出，該頁(yè)可能是系統(tǒng)中任一進(jìn)程的頁(yè)。4.頁(yè)面分配策略（續(xù)2）可變分配局部