第五章存儲管理存儲管理基礎

存儲管理的基本概念

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

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

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

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

計算機中使用的存儲保護主要有界地址、存儲鍵等保護方式。

上下界保護和地址檢查機構

（3）主存空間的保護（續）基址、限長寄存器和動態地址轉換機構

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

2.覆蓋與交換技術為什么引入？

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

將內存劃分為系統區和用戶區；內存中僅駐留一道程序，整個系統資源和用戶區只為一個用戶所獨占；僅適用于單用戶、單任務操作系統。

優缺點簡單、易實現僅適合單道程序，處理機和內存不能充分利用（1）單一連續存儲管理（續1）主存空間的分配與回收主存空間的分配：系統區和用戶區

主存空間的回收：運行結束，釋放主存空間

地址轉換與存儲保護：單用戶連續存儲管理的地址轉換可以采用靜態重定位和動態重定位兩種方法。

（1）單一連續存儲管理（續1）采用靜態重定位方法采用靜態重定位，程序執行之前由裝入程序完成邏輯地址到物理地址的轉換。如圖所示。主要優點：實現簡單，無需硬件地址轉換機構支持。

作業1裝入程序操作系統區作業1的程序和數據界限地址界限地址+邏輯地址（1）單一連續存儲管理（續1）采用動態重定位方法設置一個定位寄存器，既用來指出主存中的系統區和用戶區的地址界限，又作為用戶區的基地址；通過裝入程序把程序裝入到從界限地址開始的區域，但此時并不進行地址轉換；程序執行過程中動態地將邏輯地址與定位寄存器中的值相加就可得到物理地址。

基本原理

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

數據結構與主存分區分配表(a)分區說明表(b)存儲空間分配表分區號大小（K）起址地址（K）狀態1816Job121624031640Job243256Job3操作系統Job10Job2Job3016K24K40K56K（2）固定分區存儲管理（續2）固定式分區表

(a)分區號12345大小8

KB32

KB32

KB120

KB520

KB起始地址312

KB320

KB352

KB384

KB504

KB狀態在使用在使用在使用未用未用(b)操作系統504KB384KB352KB320KB312KB0520KB120KB32KB32KB8KB312KB固定式分區舉例固定式分區舉例

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

（2）固定分區存儲管理（續3）管理特點

一個作業只能裝入一個分區。當一個分區的大小不能滿足一個作業的要求時，該作業暫時不能裝入。通過對“分區分配表”的改寫，來實現主存的分配與回收。簡單、易行，適合多道程序設計。當分區較大而作業較小時，容易形成碎片，造成主存空間的浪費。這種方式分區總數固定，也限制了并發執行的作業數目。

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

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

P置分區P的大小為

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

當某一塊歸還后，前后空間合并，修改內存空閑塊表

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

造成存儲資源的浪費

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

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

通過在內存移動程序，將所有小的空閑區域合并為大的空閑區域。見下圖。（又稱：緊縮技術，緊致技術，浮動技術，搬家技術）

問題：系統開銷大移動時機最好定在內存某一分區不能滿足分配需求，但空閑區總和能滿足時（3）可變分區存儲管理（續9）（3）可變分區存儲管理（續10）地址轉換與存儲保護

地址轉換

采用動態重定位方式裝入作業，需設置硬件地址轉換機構，包括基址寄存器和限長寄存器。地址轉換步驟如下：當作業占用處理器時，進程調度程序把該作業所占分區的起始地址送入基址寄存器，把作業所占分區的最大長度送入限長寄存器。作業執行過程由硬件地址轉換機構把邏輯地址轉換成物理地址。即當取出一條指令后，把該指令中的邏輯地址與基址寄存器內容相加得到物理地址。

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

當處理器執行該作業的指令時必須核對表達式“始址<=絕對地址<=末址”是否成立。若成立，就執行該指令，否則就產生“地址越界”中斷事件，停止執行該指令。

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

表5.1連續存儲空間分配算法比較分配方式有無內碎片有無外碎片優

點缺

點單一連續分配有無簡單只能用在單用戶、單任務、單道或專用的操作系統固定分區分配有無用于多道程序系統的最簡單的分配方案存儲空間浪費較多首次適應算法無有分區分配中最簡單的方案，利于空白區合并低地址部分用得太多，高地址部分相對空閑，導致查找效率低循環首次適應算法無有查找時間很少，內存空間分布均勻會導致缺少大的空閑分區最佳適應算法無有使得外部碎片都很小，對于一次分配來說是最佳的。長時間來看可能留下了很多難以利用的小空閑區最差適應算法無有使得留下來的空閑區較大，便于下次利用過早用掉大的空閑區會導致以后難以找到足夠大的空閑區來滿足進程動態可重定位無有通過移動，內存利用率很高需要硬件支持地址轉換浪費時間

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

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

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

（1）分頁存儲管理（續4）主存空間的分配與回收采用的數據結構

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

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

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

（1）分頁存儲管理（續8）地址轉換機構由硬件實現，操作系統配合。關鍵在于頁號到物理塊號的轉換系統設置一對寄存器頁表始址寄存器

用于保存正在運行進程的頁表的始址頁表長度寄存器

用于保存正在運行進程的頁表的長度地址轉換過程見下圖地址轉換過程位移量進程地址轉換機構內存邏輯地址頁表寄存器塊號頁框頁號塊號頁號塊號位移量+頁表始址頁表長度頁表物理地址塊號位移量PCB頁表始址頁表長度>越界中斷12345紅線部分的工作在進程被調度時由調度程序完成絕對地址計算：塊號×塊長＋位移量地址變換舉例1

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

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

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

01011100

2查表得：4

0100拼接得：0001001001011100125C(H)

邏輯地址0A5C（H）所對應的物理地址是125C（H）

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

見下圖

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

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

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

（2）段式存儲管理

段式存儲管理方式的引入主要是為了滿足程序員在編程和使用上的要求。基本思想用戶程序劃分按程序自身的邏輯關系劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。段號從0開始，每一段也從0開始編址，段內地址是連續的邏輯地址表示實現可以基于可變分區存儲管理的原理，但是以段為單位，不是以作業為單位。

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

采用的數據結構

空閑分區表：整個主存設置一張空閑分區表,用于記錄主存中空閑區的序號、起始地址和大小。段表：系統為每個進入內存的作業建一張段表，記錄了段號，段的首（地）址和長度之間的關系，放在內存屬于進程的現場信息（2）段式存儲管理（續2）作業表

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

（2）段式存儲管理（續5）地址轉換機構系統設置一對寄存器段表始址寄存器：

用于保存正在運行進程的段表的始址段表長度寄存器

用于保存正在運行進程的段表的長度地址變換見下圖相聯存儲器——快表

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

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

（2）段式存儲管理（續7）段的共享與保護段的共享

通過不同作業段表中的項指向同一個段基址來實現的。于是，幾道作業共享的程序可放在一個段中，供各道作業共享具有相同的基址/限長值就行了。段的保護主要進行地址越界保護和共享段的存取方式控制保護。地址越界保護是利用段表中的段長和邏輯地址中的段內相對地址相比較共享段的存取方式控制保護主要是用訪問權限進行訪問共享段。

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

（3）段頁式存儲管理（續1）基本思想用戶程序劃分：按段式劃分（對用戶來講，按段的邏輯關系進行劃分）；對系統講，按頁劃分每一段邏輯地址表示

內存劃分：按頁式存儲管理方案內存分配：以頁為單位進行分配主程序段04K8K12K15K16K子程序段04K8K數據段04K8K10K12K段號段內頁號頁內地址

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

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

2.請求頁式存儲管理（1）基本思想在進程開始運行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根據進程運行的需要，動態裝入其它頁面；當內存空間已滿，而又需要裝入新的頁面時，則根據某種算法淘汰某個頁面，以便裝入新的頁面

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

塊2

塊3

塊4

塊5

塊6塊7

塊8塊9塊02KB3KB4KB5KB6KB7KB8KB9KB5060塊號狀態204070803090-1-1作業1作業2作業3L1,1KB+aA1,2KB+b00680200006151000101200123作業4地址空間頁面變換表塊號0/1頁號狀態0在內存1不在內存011121315存儲空間01KB01KB2KB001001041KB1KB+a2KB2KB+b3KB（3）地址變換機構

請求分頁系統中的地址變換機構，是在分頁系統的地址變換機構的基礎上，再為實現虛擬存儲器而增加了某些功能所形成的，如產生和處理缺頁中斷，以及從內存中換出一頁的功能等等，下圖給出了請求分頁系統的地址變換過程。

在地址轉換中，如果頁表表項位的值是1，即為pagefault（缺頁）請求分頁系統地址變換過程程序請求訪問一頁CPU檢索快表找到否？訪問頁表是否頁在內存？否產生缺頁中斷請求調頁是修改頁表對應頁表項引用位和修改位形成物理地址地址變換結束頁號有效？是否越界中斷修改快表執行一條指令形成有效地址計算頁號該頁在實存嗎？缺頁中斷入口有空閑的實頁碼？出頁修改頁表該頁修改？復制到輔存取出保存的頁號入頁找出磁盤地址修改頁表重新執行被中斷的指令取下一條指令取數據完成該指令硬件軟件YNNYYN

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

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

3.頁面置換算法

頁面置換—找到內存中并沒有使用的一些頁，將它換出（1）頁面調入策略為能使進程運行，必須事先將一部分要執行的程序和數據調入內存。調入頁面的時機

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

需要一個最小的缺頁率！！！（2）頁面置換算法頁面置換算法有：最佳算法(OPT,optimal)先進先出算法(FIFO)Belady現象最近最久未使用算法(LRU,LeastRecentlyUsed)簡單時鐘算法

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

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

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

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

333333333333888內存塊數=3

44444444444444

2666777666666是否缺頁√√√√

√

√

√

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

332663744633846內存塊數=3

44226377466384

3442633744638是否缺頁√√√√

√√√

√√

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

342643743634846內存塊數=3

34264374363484

3426437446338是否缺頁√√√√

√√

√

√

√例2某程序在內存中分配m頁初始為空，頁面走向為P=4,3,2,1,4,3,5,4,3,2,1,5。當m=3，m=4時缺頁中斷分別為多少？用FIFO算法計算缺頁次數及缺頁率FIFO性能分析例(M=3)

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

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