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

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

存儲管理的基本概念

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

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

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

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

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

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

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

（4）地址重定位地址重定位用戶程序放在邏輯地址空間（在外存），運(yùn)行時(shí)裝入內(nèi)存，這就存在邏輯地址與物理地址的轉(zhuǎn)換。將用戶使用的邏輯地址轉(zhuǎn)換成內(nèi)存空間中的物理地址的過程就稱為地址轉(zhuǎn)換（映像），也稱為地址重定位。（4）地址重定位(續(xù))重定位類型靜態(tài)地址重定位在裝入一個(gè)作業(yè)時(shí)，把作業(yè)中的指令地址全部轉(zhuǎn)換為絕對地址（地址轉(zhuǎn)換工作是在作業(yè)執(zhí)行前集中一次完成的）在作業(yè)執(zhí)行過程中就無須再進(jìn)行地址轉(zhuǎn)換工作。動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位是在程序執(zhí)行過程中，在CPU訪問內(nèi)存之前,才將要訪問的程序或數(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è)存儲器一側(cè)+BR有效地址再定位寄存器600LR界限寄存器主存動(dòng)態(tài)地址重定位

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

在多道環(huán)境下擴(kuò)充內(nèi)存的方法，解決在較小的存儲空間中運(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è)的某些部分輪流使用某一段存儲空間?；舅枷胧前褍?nèi)存中同一區(qū)域，靜態(tài)地分配給一道程序的若干個(gè)子程序或數(shù)據(jù)段，在開始時(shí)只讓一部分程序裝入內(nèi)存，根據(jù)運(yùn)行的情況，交替輪流使用。和單用戶連續(xù)區(qū)分配、分區(qū)分配技術(shù)配合使用。用戶需要小心設(shè)計(jì)程序的數(shù)據(jù)結(jié)構(gòu)，使其覆蓋模塊具有相對獨(dú)立性。例2.覆蓋與交換技術(shù)（續(xù)）缺點(diǎn)：對用戶不透明，增加了用戶負(fù)擔(dān)例子：目前這一技術(shù)用于小型系統(tǒng)中的系統(tǒng)程序的內(nèi)存管理上，MS-DOS的啟動(dòng)過程中，多次使用覆蓋技術(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)中使用外存做緩存，通過不斷換出換入而運(yùn)行大作業(yè)分進(jìn)程交換和部分交換（頁面交換和分段交換）提高內(nèi)存利用率，增加并發(fā)進(jìn)程數(shù)，提高系統(tǒng)效率交換使用的技術(shù)較多：換出進(jìn)程的選擇、交換時(shí)機(jī)的確定、需要一個(gè)盤交換區(qū)及管理、換入回內(nèi)存時(shí)位置的確定等3.連續(xù)存儲空間管理（1）單一連續(xù)存儲管理基本原理

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

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

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

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

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

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

基本原理

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

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

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

KB32

KB32

KB120

KB520

KB起始地址312

KB320

KB352

KB384

KB504

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

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

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

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

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

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

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

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

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

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

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

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

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

地址轉(zhuǎn)換

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

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

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

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

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

點(diǎn)缺

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

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

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

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

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

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

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

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

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

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

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

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

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

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

01011100

2查表得：4

0100拼接得：0001001001011100125C(H)

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

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

見下圖

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

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

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

（2）段式存儲管理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

塊2

塊3

塊4

塊5

塊6塊7

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

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

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

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

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

3.頁面置換算法

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

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

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

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

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

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

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

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

44444444444444

2666777666666是否缺頁√√√√

√

√

√

表5.3FIFO性能分析（M=3）頁面訪問次序342643743634846

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

44226377466384

3442633744638是否缺頁√√√√

√√√

√√

√√√表5.4LRU性能分析（M=3）頁面訪問次序342643743634846

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

34264374363484

3426437446338是否缺頁√√√√

√√

√

√

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

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

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