操作系統(tǒng)課件-第4章

第四章 器管理Memory

Management第4章

主要內容4.1

器的層次結構管理方式程序的裝入和連續(xù)分配對換分頁分段管理方式管理方式2021/11/63主要內容4.1

器的層次結構管理方式程序的裝入和連續(xù)分配對換分頁分段管理方式

管理方式2021/11/644.1

器的層次結構從用戶的角度來看，

器的主要指標是？容量，速度，價格(每位價格)多級器結構相互速度容量價格最高

最小

最高最低最大最低2021/11/6體系高速緩存Cache：少量、非常快速、昂貴、易變的內存RAM：若干兆字節(jié)、中等速度、中等價格、易變的磁盤：數(shù)百兆或數(shù)千兆字節(jié)、低速、價廉、不易變的由操作系統(tǒng)協(xié)調這些

器的使用.2021/11/664.1.2

主

器與寄存器主

器（內存，主存，可執(zhí)行

器）用于保存進程運行時的程序和數(shù)據(jù)。CPU的控制部件只能從主存中取得指令和數(shù)據(jù)到CPU寄存器，同樣，CPU寄存器中的數(shù)據(jù)可存入主存。CPU與外設交換數(shù)據(jù)必須依托于主存。寄存器寄存器 速度最快，與CPU協(xié)調工作。2021/11/674.1.3

高速緩存與磁盤緩存1.高速緩存CPU對高速緩存的

，其速度比問寄存器慢。主存快，比訪根據(jù)程序執(zhí)行的局部性原理，將主存中一些經常的數(shù)據(jù)存放在高速緩存中，減少

主存的次數(shù)，提高程序的執(zhí)行速度。內存一級高速緩存二級高速緩存磁盤2021/11/68高速緩存與磁盤緩存2.磁盤緩存內存中一塊

區(qū)，對應于某固定磁盤，臨時

磁盤數(shù)據(jù)（如，數(shù)據(jù)預?。?021/11/69管理的功能分配和回收地址變換共享和保護器擴充2021/11/610基本概念邏輯地址（相對地址，虛地址）：用戶的程序經過匯編或編譯后形成目標代碼，目標代碼通常采用相對地址的形式，其首地址為0，其余指令中的地址都相對于首地址而編址。不能用邏輯地址在內存中 信息物理地址（絕對地址，實地址）內存中 單元的地址，可直接尋址地址空間程序用來信息所用地址單元的集合，是邏輯（相對）地址的集合，由編譯程序生成。空間：主存中物理單元的集合。2021/11/611符號地址、相對地址和絕對地址地址1200Load

A

2003456。。物理地址空間Loata1data1

3456源程序編譯連接Load

A

20034560100200邏輯地址空間BA=1000相對地址絕對地址符號地址2021/11/612§4.2

程序的裝入和源程序編譯目標模塊庫…..程序裝入模塊裝入程序內存2021/11/613一.程序的裝入絕對裝入方式可重定位裝入方式動態(tài)運行時裝入方式2021/11/614絕對裝入方式(Absolu oading

Mode)

：編譯時，編譯程序產生的目標代碼是絕對地址。裝入程序按裝入模塊中的地址將程序、數(shù)據(jù)裝入

內存，不需修改地址。絕對地址可直接由程序員給出，或在編譯或匯編時給出。程序的裝入（續(xù)）優(yōu)點：裝入過程簡單。缺點：過于依賴于硬件結構，適用于單道程序系統(tǒng)。2021/11/615程序的裝入（續(xù)）可重定位裝入方式(Relocation

Loading

Mode)重定位（地址

/地址變換）：經編譯得到的目標模塊中為相對地址（通常從0開始），即地址都是相對于0開始的。裝入模塊中的邏輯地址與實際裝入內存的物理地址不同。裝入內存時，相對地址（數(shù)據(jù)、指令地址）要作出相應的修改以得到正確的物理地址，這個修改的過程稱為重定位。2021/11/616可重定位裝入方式重定位：根據(jù)地址變換進行的時間及采用技術

不同，分為：靜態(tài)重定位動態(tài)重定位2021/11/617可重定位裝入方式2021/11/618靜態(tài)重定位

地址變換是在裝入內存時一次完成的，且以后不能移動。

一般情況下,物理地址=相對地址+內存中的起始地址

適用于多道程序環(huán)境，可以將裝入模塊裝入到內存中任何允許的位置。優(yōu)點：不需硬件支持，可以裝入有限多道程序。

缺點：一個程序通常需要占用連續(xù)的內存空間，程序裝入內存后不能移動，不易實現(xiàn)共享。250011000MOV

ax,[2500]365程序空間0100001000內存空間0[12500]1250012500

＝

10000址 相對地址物理地址/11/6193、動態(tài)運行時裝入方式（動態(tài)重定位，Dynamic

Run-time

Loading)裝入模塊中的為相對地址，在裝入內存時，并不立即改變?yōu)槲锢淼刂罚ń^對地址），即裝入后仍為相對地址。只有在程序真正執(zhí)行到某一步時才對它進行地址轉換。優(yōu)點：OS可以將一個程序分散存放于不連續(xù)的內存空間，可以移動程序，有利用實現(xiàn)共享。缺點：該方式需要一定特殊硬件的支持，OS實現(xiàn)較復雜，是虛擬 的基礎。程序的裝入（續(xù)）2021/11/620二、程序的

是指將編譯或匯編后得到的一組目標模塊以及所需庫函數(shù)裝配成一個完整的裝入模塊(執(zhí)行文件)。目標模塊使用的地址是相對的，都是從0開始,

形成

地址空間的裝入模塊的過程——

。0000裝入模塊目標模塊階段產生的可執(zhí)行目標程序在不運行時，通常作為一個二進制可執(zhí)行文件駐留在硬盤上。2021/11/621程序的–根據(jù)時間的不同，可把分成如下三種：靜態(tài)裝入時動態(tài)運行時動態(tài)2021/11/622程序的1、靜態(tài)–

在裝入內存之前進行，且 后形成一固定的裝入模塊（也稱為可執(zhí)行程序），不再拆開的方式。Module

Acall

"function1"0L-1Module

B0M-1...}"function1"F

function1(){Module

Acall

L+F0L-1Module

BL...L+M-1

}"function1"L+F

function1(){

完整的包含所有的目標模塊后裝入2021/11/61.靜態(tài)這種方式需要解決：對相對地址進行修改。即將各個模塊中的相對地址為相對于一個起始地址0的相對地址；變換外部調用符號。即將各個模塊中用到的外部調用符號轉換為相對地址。2021/11/624目標模塊是在裝入內存時邊裝入邊

的。由系統(tǒng)裝入操作在裝入的同時找到需要的其它模塊，并

。優(yōu)點：便于目標模塊的修改和更新；便于多個應用程序對目標模塊的共享。缺點：每次都要 裝入所有的模塊，不論是否用到。2.裝入時動態(tài)2021/11/6253、運行時動態(tài)一開始只

裝入部分模塊;在運行過程中，若發(fā)現(xiàn)被調用模塊不在內存，則發(fā)出請求，由OS查找、裝入并

到調用模塊上,再執(zhí)行。裝入后具有高效且節(jié)省內存空間的優(yōu)點。2021/11/626靜態(tài)例例1庫模塊目標模塊100call

1200H1200Hprintf(

“

OK”

);void

printf(…){{}裝入模塊0靜態(tài)2021/11/627裝入時動態(tài)

例例2主模塊庫模塊00void

printf(…){}0

裝入模塊裝入時動態(tài)call

1200H裝入printf(

“

OK”

);call

1200Hvoid

printf(…){}1200H21200Hcall

21200H20000H2021/11/628運行時動態(tài)

例call

33600H內存主模塊庫模塊00例3裝入模塊void

printf(…){裝入printf(

“

OK”

);

printf(“OK”);

執(zhí)行33600H運行時動態(tài)}2021/11/629§4.3

連續(xù)分配方式程序空間本來就是連續(xù)的用連續(xù)的內存裝入連續(xù)的程序，減少管理工作的難度連續(xù)分配指為用戶程序分配續(xù)的內存空間。2021/11/6302021/11/631連續(xù)分配方式分類：單一連續(xù)分配方式固定分區(qū)分配(fixed

Partitioning)動態(tài)分區(qū)分配(DynamicPartitioning)伙伴系統(tǒng)動態(tài)重定位分區(qū)分配(Relacation

Partitioning)4.3.1單一連續(xù)分配內存中僅駐留一道用戶程序，整個用戶區(qū)為一個用戶獨占。內存分為兩個區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。應用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。最簡單，適用于單用戶、單任務的OS。優(yōu)點：易于管理。缺點：對要求內存空間少的程序，造成內存浪費；例程序全部裝入，很少使用的程序部分也占用內存。例如：DOS2.0以下的DOS操作系統(tǒng)采用單一連續(xù)區(qū)域主存管理方法。2021/11/632單一連續(xù)分配早期大型機使用的內存管理方式少數(shù)掌上電腦和系統(tǒng)使用的內存管理方式早期PC使用的內存管理方式（MS-DOS)ROM：DEV用戶程序RAM中的OS用戶程序RAM中的OS用戶程序ROM中的OS2021/11/633例：一個容量為256KB的內存，操作系統(tǒng)占用32KB，剩下224KB全部分配給用戶作業(yè)，如果一個作業(yè)僅需64KB，那么就有160KB的空間被浪費。0KB操作系統(tǒng)作業(yè)32KB96KB分配給用戶的空間256KB-1返回2021/11/634將內存空間分為若干個固定大小的區(qū)域，每個分區(qū)中可裝入一道作業(yè)。劃分通常是在系統(tǒng)初使化時執(zhí)行。1、劃分分區(qū)的方法分區(qū)大小相同(Equal-sizepartitions)：主要用于控制多個相同對象的場合。程序太大？程序太??？分區(qū)大小不同(Unequal-sizepartitions)：一般可劃分多個小分區(qū)，適量中等分區(qū)，少量大分區(qū)。可適應多種類型的作業(yè)。2021/11/6354.3.2固定分區(qū)分配Operating

System8

M2

M4

M6

M8

M8

M12

M2021/11/636固定分區(qū)(大小相同)固定分區(qū)(多種大小)固定分區(qū)分配（續(xù)）2、內存分配：將分區(qū)按大小順序排列，并建立一張分區(qū)使用表（可包括分區(qū)起址、大小、狀態(tài)等）。有內容需要裝入時，在分區(qū)使用表中查找大小能滿足且未分配出去的分區(qū)，若能找到，則實施分配且修改分區(qū)表中的狀態(tài)。否則，分配。2021/11/637分區(qū)號大小(KB)始址(K)狀態(tài)11530未分配23045已分配35075已分配4100125未分配內存中已分配給用戶但未被利用的區(qū)域稱為“內零頭”（內碎片）固定分區(qū)分配有內零頭產生。若到來作業(yè)A，大小為30K，查找該表，找到分區(qū)2為滿足大小要求的第一個分區(qū)。進行分配且修改分區(qū)說明表。到來作業(yè)B，大小也為30K，查找該表，將分區(qū)3分配到來作業(yè)C，大小為110K，不進行分配2021/11/638固定分區(qū)分配（續(xù)）Advantages

：易于實現(xiàn)，開銷小。Disadvantages

：–內碎片造成浪費–分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目。采用的數(shù)據(jù)結構：分區(qū)表－記錄分區(qū)的大小和使用情況2021/11/6394.3.3動態(tài)分區(qū)分配思想：根據(jù)進程的實際需要，動態(tài)地為之分配連續(xù)的內存空間。即進程需要多少內存空間，就劃分給它多少。如：在實現(xiàn)動態(tài)分區(qū)分配

管理方式時，必須解決下述三個問題：分區(qū)分配中的數(shù)據(jù)結構；分區(qū)分配算法；分區(qū)的分配和回收。2021/11/640動態(tài)分區(qū)分配（續(xù)）1、分區(qū)分配中的數(shù)據(jù)結構1）空閑分區(qū)表：用表的方式記錄內存中的所有空閑分區(qū)。每一分區(qū)占一表目?？砂ㄐ蛱?、分區(qū)大小、始址等。分區(qū)號大小KB起始地址KB狀態(tài)132352空閑2……空表目3520504空閑4……空表目5………2021/11/6動態(tài)分區(qū)分配（續(xù)）2）空閑分區(qū)鏈：用鏈的方式記錄每一空閑分區(qū)。鏈上的每一分區(qū)中需

指向前后分區(qū)的指針及本分區(qū)的大小、狀態(tài)（0表示可用，1表示已用）。352KB32KB504KB520KBNIL空閑分區(qū)鏈頭指針狀態(tài)大小前一塊狀態(tài)大小后一塊狀態(tài)大小前一塊狀態(tài)大小后一塊352KB504KB2021/11/6422、分區(qū)分配算法Dynamic

Partitioning

Placement

Algorithm考慮將作業(yè)裝入內存時，選擇什么樣的內存分區(qū)進行分配。2021/11/643動態(tài)分區(qū)分配（續(xù)）分區(qū)分配算法首次適應算法（FF，

－Fit）要求：空閑分區(qū)以地址遞增的次序

。

分配：從鏈首順序查找，直至找到一個能滿足大小的空閑分區(qū)為止。從選中的分區(qū)中分出所需的大小，其余部分仍留在空白分區(qū)鏈表里。傾向：利用低址分區(qū)。優(yōu)點：分區(qū)組織簡單；高址部分可容納大作業(yè)。缺點：低址處外零頭多，查找越來越

。2021/11/644作業(yè)1作業(yè)2作業(yè)3作業(yè)4外零頭2343540

00

10112在低地址部分會積累大量外零頭2021/11/645內零頭與外零頭內存分配性能評價的一類重要指標內零頭(Internal

Fragment):分配給用戶但用戶沒有使用的空間“多分配的空間”外零頭(External

Fragment

)：沒有分配但無法分配的空間太小而無法分配，“分不出去的空間”單一連續(xù)分配有較大的內零頭分區(qū)分配有小于一個分區(qū)的內零頭2021/11/6462）循環(huán)首次適應(Next-fit)

在首次適應算法的基礎上，均衡利用整個內存空間

實現(xiàn)：將空白區(qū)鏈表首尾相接形成環(huán)形，設置一個查找指針每次查找從上一次停留的位置開始

特點可以均衡利用高址和低址內存減慢了外零頭形成的速度外零頭雖然不集中在低址部分，但未得到有效解決?！帮灨稍疥剿椤?021/11/6473）最佳適應算法(BF,Best－Fit)。要求：空閑分區(qū)按大小遞增的順序進行分配：從鏈表頭進行順序查找，直至第一個大小能滿足的分區(qū)。則為能滿足且最接近需要大小的分區(qū)。劃分。優(yōu)點：避免“大材小用”缺點：外零頭嚴重；分區(qū)組織、空閑分區(qū)的回收復雜。2021/11/6484）

適應算法(WorstFit)

要求：空閑分區(qū)按從大到小.

分配：從頭順序查找，找到大小能滿足的。則為能滿足且劃分后剩余空間最大的分區(qū)。劃分。

優(yōu)點：外零頭較少。

缺點：難以滿足大作業(yè)的要求；分區(qū)組織、空閑分區(qū)的回收復雜X2021/11/649OS30K使用20K使用5K使用46K020K100K160K210K255K首次適應算法空閑分區(qū)表分區(qū)號大小起始地址15K160K220K

2K100K

118K330K20K446K210K最佳適應算法空閑分區(qū)表分區(qū)號大小起始地址130K

12K20K

38K220K100K35K160K446K210K分區(qū)號大小起始地址146K

28K210K

228K230K20K320K100K45K160K適應算法空閑分區(qū)表30KOS使用20K使用5K使用46K020K100K160K210K255K020K作業(yè)A-18K作業(yè)序列作業(yè)A-18K20KOS30K使用使用5K使用46K100K160K210K255K020K作業(yè)序列160K210K255KOS30K使用20K使用5K使用46K100K作業(yè)A-18K作業(yè)序列例1:2021/11/650例2：有作業(yè)序列：作業(yè)A要求18K；作業(yè)B要求25K，作業(yè)C要求30K。系統(tǒng)中空閑區(qū)按三種算法組成的空閑區(qū)隊列2021/11/6512021/11/652思考用可變分區(qū)(動態(tài)重定位)方式管理主存時,假

定主存中按地址順序依次有5個空閑區(qū),空閑

區(qū)的大小依次為32K,10K,5K,228K和100K?，F(xiàn)有5個作業(yè)A,B,C,D,E.它們各需主存1K,10K,108K

,28K和115K.若采用首次適應算法能把這5個作業(yè)按順序全部裝入主存嗎?5)快速適應算法(Quick

Fit)又稱分類搜索法;系統(tǒng)中設多個空閑分區(qū)鏈表，每個鏈表中存放容量相同的所有空閑分區(qū)；內存中設一張管理索引表，每一個表項對應一種空閑分區(qū)類型，用于記錄鏈表表頭指針。空閑分區(qū)的分類是根據(jù)進程常用的空間大小進行劃分，如2

KB、4

KB、8

KB等，對于其它大小的分區(qū)，如7

KB這樣的空閑區(qū)，既可以放在8

KB的鏈表中，也可以放在一個特殊的空閑區(qū)鏈表中。2021/11/653快速適應算法（續(xù)）優(yōu)點：查找效率高；分配時不對空閑區(qū)進行分割，因此不會產生碎片。缺點：在分區(qū)歸還主存時算法復雜，系統(tǒng)開銷較大。2021/11/654總

結從查找速度，速度、空閑區(qū)利用面進行比較:首次適應算法：搜索速度，回收速度快，同時盡可能地利用了低地址空間，保證了高地址端有較大的空閑區(qū)來放置要求內存較多的進程作業(yè)。最佳適應算法：找到的空閑區(qū)最佳，產生了大量碎片。適應算法：克服了碎片問題，但大作業(yè)往往無法運行。2021/11/6552021/11/6563、分區(qū)分配操作1）分配步驟：①按某種算法根據(jù)請求的大小，在表或鏈中進行查找；②找不到則結束；找到進行劃分。為減少外零頭，可設定一下限。若劃分后零頭小于該下限，則不劃分直接分配③修改相應的數(shù)據(jù)結構。動態(tài)分區(qū)分配（續(xù)）從空白分區(qū)鏈表中選取適當分區(qū)mm.size

–

u.size<minsizeu：用戶裝入模塊

minsize：最小分區(qū)從m中劃出u.size大小的分區(qū)給用戶m.size

=

m.size

–u.size將分區(qū)從鏈表中移出NY可能形成將分區(qū)分配給用戶外零頭存在內零頭分配過程的流程圖2021/11/657動態(tài)分區(qū)分配（續(xù)）2）分區(qū)回收：根據(jù)回收區(qū)的首址在相應的數(shù)據(jù)結構中查找點.分為四種情況：①回收區(qū)與點的前一分區(qū)相鄰：合并、改大小大小前狀態(tài)大小前一塊狀態(tài)大小后一塊大小后相鄰狀態(tài)大小一塊塊塊狀態(tài)大小一塊2021/11/658分區(qū)回收②回收區(qū)與點的后一分區(qū)相鄰：合并、改始址、大?、刍厥諈^(qū)與

點的前、后分區(qū)相鄰：合并、共用前分區(qū)首址、改大小、取消后分區(qū)④回收區(qū)與

點的前、后分區(qū)不相鄰：單獨建一表項2021/11/6回收區(qū)F1……F1回收區(qū)F2…F1回收區(qū)F2…4.3.4伙伴系統(tǒng)(

)固定分區(qū)和動態(tài)分區(qū)方案存在的問題？算法復雜，回收分區(qū)時系統(tǒng)開銷大；21表示分配的最小塊的尺寸；2m表示分配的最大塊的尺寸，通常是可供分配的整個內存空間的大小。對空閑區(qū)按照大小分類，相同大小的分區(qū) 為一個雙向空閑鏈表；最多可形成k（0≤k≤m

）個鏈表。2021/11/660伙伴系統(tǒng)（續(xù)）進程請求大小為n的

空間時，–首先計算一個i

值，使2i－1<

n

≤

2i；–在空閑分區(qū)大小為2i

的空閑分區(qū)鏈表中查找。if

找到，即把該空閑分區(qū)分配給進程。else在分區(qū)大小為2i＋1的空閑分區(qū)鏈表中尋找;//表明長度為2i的空閑分區(qū)已經耗盡if

找到大小為2i＋1

的空閑分區(qū)把該空閑分區(qū)分為相等的兩個分區(qū)（一對伙伴），其中一個用于分配，另一個加入分區(qū)大小為2i

的空閑分區(qū)鏈表中。else

查找大小為2i＋2

的空閑分區(qū)……2021/11/661伙伴系統(tǒng)示例分割及回收合并分區(qū)需要時間開銷，多用于多處理機系統(tǒng)中。2021/11/6624.3.5哈希算法2021/11/663利用哈?？焖俨檎业膬?yōu)點，以及空閑分區(qū)在可利用空間表中的分布規(guī)律，建立哈希函數(shù)，構造一張哈希表，以空閑分區(qū)大小為關鍵字，每一個表項記錄了一個對應的空閑分區(qū)鏈表表頭指針。當進行空閑分區(qū)分配時，根據(jù)所需空閑分區(qū)大小，通過哈希函數(shù)計算，即得到在哈希表中的位置，

從中得到相應的空閑分區(qū)鏈表，實現(xiàn)最佳分配策

略。4.3.6可重定位分區(qū)分配引入在動態(tài)分區(qū)分配中，拼接僅在相鄰空白分區(qū)之間進行，而散布在內存中的外零頭不便拼接?；舅枷耄壕o湊(Compaction

)

將內存中的作業(yè)進行移動，使它們相鄰接，可使分散的小分區(qū)拼接成一個大分區(qū)，從而利于作業(yè)的裝入。例：以時間換空間Compaction技術要求系統(tǒng)具有動態(tài)重定位的能力.2021/11/664可重定位分區(qū)分配圖4-9

緊湊的示意大量消滅外零頭作業(yè)1作業(yè)4作業(yè)2作業(yè)3移動作業(yè)拼接出大分區(qū)2021/11/665可重定位分區(qū)分配（續(xù)）2、動態(tài)重定位的實現(xiàn)為支持作業(yè)在內存中的移動，應采用動態(tài)運行時裝入（動態(tài)重定位）方式硬件地址變換機構的支持:在系統(tǒng)中設置一個重定位寄存器,用于存放作業(yè)在內存中的起始地址。在運行時，有一個相對地址，則執(zhí)行：物理地址=重定位寄存器+相對地址以得到它在內存中的實際地址。2021/11/666.LOAD

A

200.34.56.0.LOAD

A

200..3456.0100200邏輯地址空間11001300物理地址空間200VR+000BR300緊湊時，只需修改相應的重定位寄存器的值，使之存放新的起始地址。2021/11/66751200動態(tài)重定位示意圖5000動態(tài)分區(qū)分配算法流程圖請求分配u.size分區(qū)檢索空閑分區(qū)鏈(表)找到大于u.size的可用區(qū)否?按動態(tài)分區(qū)方式進行分配修改有關的數(shù)據(jù)結構返回分區(qū)號及首批空閑分區(qū)總和≥u.size?進行緊湊形成連續(xù)空閑區(qū)修改有關的數(shù)據(jù)結構否是無法分配返回否2021/11/6682021/11/669可重定位分區(qū)分配可重定位分區(qū)的優(yōu)缺點：解決了可變分區(qū)分配所引入的“外零頭”問題。（優(yōu)點）消除內存碎片，提高內存利用率。（優(yōu)點）提高硬件成本，緊湊時花費CPU時間。（缺點）4.4對換(Swap)對換指把內存中暫不能運行的進程或暫時不用和

程序和數(shù)據(jù)，換到外存上，以騰出足夠的內存空間，把已具備運行條件的進程，或進程所需要的程序和數(shù)據(jù)，換入內存。對換是系統(tǒng)行為，是提高內存的利用率的有效措施。常用于多道程序系統(tǒng)或小型分時系統(tǒng)中，與分區(qū)管理配合使用。實現(xiàn)：可在系統(tǒng)中設一對換進程，以執(zhí)行換進內存、換出至外存操作。2021/11/670Schematic

ViewofSwap2021/11/671分類：“整體對換”（進程對換）：對換以整個進程為單位，用于分時系統(tǒng)，以解決內存緊張的問題；“頁面對換”（分段對換）：對換以“頁”或“段”為單位進行“部分對換”，該方法是實現(xiàn)請求分頁及請求分段

器的基礎，支持虛存系統(tǒng)。對換（續(xù)）2021/11/672對換（續(xù)）面的功能：為實現(xiàn)對換，系統(tǒng)需要對換空間的管理進程的換入換出2021/11/673外存被分為兩

分，文件區(qū)和對換區(qū)文件區(qū)用于存放文件，對它的管理應重在如何提高

空間的利用率。所以對它采取離散分配方式。對換區(qū)存放從內存換出的進程，它們在外存的對換（續(xù)）即一個文件可根據(jù)當前外存的使用情況，二、對換空被分成多塊，分別到不鄰接的多個區(qū)域中，用指針相連。管理應重在提高進用連續(xù)分配方式。存放時間較短，換即把一個換出的進程存放到續(xù)的

空間中。2021/11/6742021/11/675三、進程的換出與換入(由對換進程完成)1、換出（swap

out）1）選擇：首先選擇阻塞或睡眠狀態(tài)的進程，若有多個，按優(yōu)先級由低到高進行選擇。若沒有此狀態(tài)進程，則選擇就緒狀態(tài)的，仍然按優(yōu)先級由低到高進行選擇。為避免某進程被頻繁的換入換出，還應考慮進程在內存中的駐留時間，優(yōu)先選擇駐留時間長的進程。對換（續(xù)）2）換入（swap

in）①從PCB集合中查找“就緒且換出”的進程，有多個，則選擇換出時間最長的。②根據(jù)進程大小申請內存，成功則讀入，否則要先執(zhí)行換出， 入。③若還有可換入進程，則轉向①。直至無“就緒且換出”進程或無法獲得足夠內存空間為止。對換（續(xù)）2021/11/676§4.5分頁管理方式2021/11/677分頁?離散分配方式的引入連續(xù)分配方式會產生內/外零頭為解決零頭問題又要進行緊湊等高開銷活動離散分配程序在內存中不一定連續(xù)存放根據(jù)離散時的基本單位不同，可分為三種：分頁 管理分段

管理段頁式 管理管理方式Paged

Memory

Management2021/11/678分頁管理1.

分頁

管理基本思想1）離散的基礎分頁(Pages)：將程序地址空間分頁分塊(Frames)：將內存空間分塊2）離散分配的體現(xiàn)內存一塊可以裝入程序一頁連續(xù)的多個頁不一定裝入連續(xù)的多個塊中注：系統(tǒng)中頁塊的大小是不變的。012n用戶程序012m內存2021/11/679分頁

管理3）離散分配的優(yōu)點沒有外零頭不受連續(xù)空間限制，每塊都能分出去僅有小于一個頁面的內零頭程序大小一般不是頁大小的整數(shù)倍不支持虛擬

，要求把每個作業(yè)全部裝入內存才能運行，因此又稱為純分頁

管理。2021/11/680分頁

管理的基本方法2.

解決兩個基本問題：

如何進行地址變換從程序邏輯地址到內存物理地址012m程序空間邏輯空間相對地址內存空間物理空間絕對地址內存用戶程序301

m-22

13

m-1

如何建立程序空間與主存空間的頁表頁號塊號01232021/11/681實現(xiàn)分頁

管理的數(shù)據(jù)結構頁表：每個進程對應1個頁表，描述該進程的各頁面在內存中對應的物理塊號。頁表中包括頁號、物理塊號（還可有存取控制字段，對 塊中的內容進行保護）。注意：全部頁表集中存放在主存的系統(tǒng)

區(qū)中，只有系統(tǒng)

頁表，保證安全。作業(yè)表：整個系統(tǒng)1張，記錄作業(yè)的頁表情況，包含進程號、頁表長度、頁表始址等信息?？臻e塊表：整個系統(tǒng)1張，記錄主存當前空閑塊。2021/11/682作業(yè)號頁表大小頁表始址狀態(tài)0已分配1未分配21k40k已分配2k

10000H頁號塊號 存取控制02kR11kW240kRW作業(yè)表（JT）頁表（PT）2021/11/683頁面大小的選擇頁面大小由機器的地址結構決定。某一機器只能采用一種大小的頁面。小頁面大頁面頁面的大小通常在512B~8KB之間。分頁

管理方式（續(xù)）2021/11/6844.地址變換機構地址變換機構的功能是將用戶的邏輯地址轉變?yōu)閮却嬷械奈锢淼刂贰＿壿嫷刂酚身撎柡晚搩任灰屏拷M成。頁的大小和內存物理塊的大小是相同的，所以頁內位移量即為物理塊內位移量。關鍵是頁號到物理塊號的轉換，由頁表完成。續(xù)分頁

管理方式（內存用戶程序2021/11/6地址變換機構在分頁為：頁號+頁內位移量。管理的邏輯地址表示管理方式中，任一個邏輯地址都可轉變?一個32位的邏輯地址，可轉化為如下方式：0～11位表示頁內位移量，則每頁的大小為212

=4KB。12

～

31位表示頁號，220=1M，即最多允許有1M頁。1）分頁12

11

031頁號P位移量W2021/11/686地址變換機構分頁 管理的邏輯地址表示設有一邏輯地址A，頁面大小為L，則在分頁管理方式中，它的地址被轉換：頁號

P=INT[A/L]頁內位移量

W=A

MODL邏輯地址為：2170，頁面大小為1KB，則

P=INT[2170/1024]=2；W=2170

MOD1024=122這個地址的變換通常由系統(tǒng)中的某些硬件完成。2021/11/687地址變換機構2）基本的地址變換機構使用寄存器存放頁表

速度快，成本高。特別對于大的系統(tǒng)，頁表很長，不可能都用寄存器實現(xiàn)。一般系統(tǒng)，將頁表 在內存中

設置一個頁表寄存器（PTR），記錄頁表在內存中的始址和頁表長度。（平時存于PCB中，要運行時才裝入PTR中）2021/11/688分頁的地址變換機構邏輯地址址+物理地址頁表始址 頁表大小頁表寄存器（PTR內容）>越界？頁號塊號頁表有效地址寄存器1

1+1

100100

1物理地址寄存器設塊大小為4100*4+1=4012021/11/689例：在采用頁式管理的系統(tǒng)中，作業(yè)J的邏輯空間為4頁（每頁2048字節(jié)），且已知該作業(yè)的頁表為：02142638頁表地址2769頁號 頁內偏移邏輯地址4865物理地址130576769塊號塊內偏移主存頁表寄存器2021/11/6903）具有快表的地址變換機構局部性原理每存取一個數(shù)據(jù)，需

兩次內存。第一次第二次頁表，以得到物理地址；物理地址，以得到數(shù)據(jù)。存取速度幾乎降低了一倍，代價太高。器associative的一些頁–

增設一高速緩沖

器（聯(lián)想memory、快表），用來存放最近表項。地址變換機構2021/11/691快表的頁號頁內地址頁表始址頁表大小頁表寄存器（PTR內容）+塊號 塊內地址物理地址寄存器有效地址寄存器>越界？頁號塊號快表在CPU的高速緩存中進行，在CPU的高速緩存中查不到僅

內存一次頁表內存兩次2021/11/692關于快表的配置快表效果如何，取決于如檢索快表時間為20

ns，快表時

中率。內存為100

ns。若能在快表中檢索到CPU給出的頁號，則CPU存取一個數(shù)據(jù)共需120

ns。否則，需要220

ns的時間。當

快表時時，其有效中率分別為0%，50%，80%，90%，98%時間如下表所示：2021/11/693%有效

時間T=h

t1+

(1-

h)

t2(ns)0T=0

120

+

1

220=22050T=0.50

120

+

0.50

220=17080T=0.80

120

+

0.20

220=14090T=0.90

120

+

0.10

220=13098T=0.98

120

+

0.02

220=122選用8～12項組成的聯(lián)想

器，并采用適當?shù)奶鎿Q策略，在聯(lián)想

器中匹配成功的可能性可達80%～90%?？梢?，由于增設了聯(lián)想

器，而使

數(shù)據(jù)的時間，比單周期的

時間要延長40%~22%。但如果不引想

器，其時間將延長一倍。2021/11/694分頁

管理方式（續(xù)）兩級和多級頁表引入：在系統(tǒng)中，若支持的邏輯地址空間大，則相應的頁表長度會很大。如一個具有32位邏輯地址空間的分頁系統(tǒng)，頁面大小為4KB，則頁表

有232/212=220=1M個。每個頁表項占4B，一共占4MB。且頁表存放在連續(xù)的空間中，占有大量的內存。解決方案：頁表本身采用離散分配方式；只將當前需要的部分頁表項調入內存。2021/11/695兩級頁表(Two-Level

Page

Table)實現(xiàn)：采用兩級頁表把頁表分頁，每個頁面的大小與內存物理塊的大小相同，從0開始進行

。離散地將各個頁表頁面分別放在不同的物理塊中。建立一個外層頁表：實現(xiàn)頁表每一頁的頁號到所存放的物理塊號的

。外層頁表的表項記錄的是某頁表分頁在內存中的始址。內層頁表的表項記錄的是某頁在內存中的物理塊號。如圖2021/11/696??012345671141151468內存空間101110780121742n外部頁表14…114115…146801102310241025204720482049頁表2021/11/697兩級頁表邏輯地址結構：地址變換：設置一個外層頁表寄存器，存放外層頁表的始址。2021/11/698外部頁號 外部頁內地址

頁內地址P1P2d邏輯地址￡?外部頁表寄存器￡?db物理地址外部頁表 頁表……這種方式只是把連續(xù)變?yōu)殡x散，頁表所占的總空間沒有減少甚至增多了。具有兩級頁表的地址變換機構2、多級頁表結構（64位邏輯地址空間）2021/11/699分頁

管理方式小結優(yōu)點：沒有外碎片，每個內碎片不超過頁大小。一個程序不必連續(xù)存放。缺點：程序全部裝入內存。2021/11/6100練

習某虛擬

器的用戶編程空間共32個頁面，每頁1KB，主存為16KB。假定某時刻該用戶頁表如下，（主存中只有部分頁）。則與邏輯地址0A5C（H）對應的物理地址為（設

塊從0開始編址）：頁號塊號051102437125C

H2021/11/6101設有一頁式

管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16頁，每頁2048B，內存總共有8個

塊，試問邏輯地址至少應為多少位？內存空間有多大？思考2021/11/61024.6

分段管理方式2021/11/61034.6.1引入分段共享方便編程程序

程序由若干具有完整邏輯

信息段大小不一模塊化設計 意義的信息段組成分頁

以頁為內存分配單位 頁的大小相等如何使內存管理符合程序的模塊化設計思想？2021/11/6104...0S工作區(qū)段[B]...0EP子程序段[X]0K..CALL

[X]

[E]...CALL

[Y]

[F]..LOAD

1,

[A][G].......0FL子程序段[Y]N..123450G數(shù)組[A].12345主程序段[M]2021/11/61054.6.2分段系統(tǒng)的基本原理分段：作業(yè)地址空間按邏輯信息的完整性被劃分為若干個段；每段有段名（或段號），每段從0開始編址；段內的地址空間是連續(xù)的。許多編譯程序支持分段方式，自動根據(jù)源程序的情況產生若干個段。2021/11/6106分段系統(tǒng)的基本原理分段系統(tǒng)中的邏輯地址是二維的，表示為：–

邏輯地址

=(段號，段內地址)

（區(qū)分分頁）如一個32位的邏輯地址：段號段內地址31

16

15

0可知每段最大長度為：216=64KB；最多允許有64K

個段.段長？分段數(shù)？2021/11/6107分段

管理（續(xù)）2.內存分配內存的物理地址空間開始不作劃分.類似于動態(tài)分區(qū)分配方式。以段為基本單位進行連續(xù)區(qū)的分配，各段之間的內存空間可以是不鄰接的。考慮：與動態(tài)分區(qū)分配的不同？不再以進程為單位分配內存。分配：查找滿足某段大小的內存空間，劃分。2021/11/6108分段管理（續(xù)）3.段表包括段號、段長、段起始地址（基址）等。作用：是實現(xiàn)從邏輯段到物理內存區(qū)的

。通常置于內存中。2021/11/6109作業(yè)空間(MAIN)=0030K(X)=1020K(D)=2015K(S)=3010K012330K40K20K80K15K120K10K150K段號 段長 基址段表(MAIN)=030K(X)=120K(D)=215K(S)=310K內存空間040K80K120K150K利用段表實現(xiàn)地址2021/11/6110段表寄存器段表始址

段表長度物理地址>+越界中斷4.分段系統(tǒng)的地址變換機構1002段號S

位移量W段表1K6K6004K5008K2009200段號

段長

基址0123+82928K82928692主存2021/11/6111分段

管理（續(xù)）問：若段表放在內存中，每一個數(shù)據(jù)需要內存兩次?？稍O置聯(lián)想

器（快表），以提高

速度。優(yōu)點：沒有內碎片，外碎片可以通過內存緊縮來消除。便于改變進程占用空間的大小。缺點：進程全部裝入內存。2021/11/6112練

習某作業(yè)的段表：段號址段長021912300142901003580496請給出下列各邏輯地址所對應的物理地址：（0，430）（1，10）（2，88）（3，444）（4，112）2021/11/6113分段

管理（續(xù)）Characteristics

of Paging

and

Segmentation（1）可見與不可見“分頁”是系統(tǒng)活動，用戶無法介入，頁的大小固定；“分段”是用戶可見的，段大小可變。（2）物理單位與邏輯單位頁是信息的物理單位，不是完整的邏輯單位；段是完整的邏輯信息單位。（3）地址空間分頁的作業(yè)空間是一維的，是單一線性空間；分段的作業(yè)空間是二維的。2021/11/61144.6.3信息共享分頁系統(tǒng)實現(xiàn)段的共享較為

。分段易于實現(xiàn)段的共享和段的保護。例：一個多用戶系統(tǒng)可接納40個用戶，它們都執(zhí)行一個文本編輯程序(ED)，ED代碼共160K，每個用戶還有40K的數(shù)據(jù)區(qū)(DA)。–不采用信息共享時需占用的內存空間？(

160K

+

40K

)

*

40

=

8000K2021/11/6115例（續(xù)）分頁系統(tǒng)：設頁面大小為4KB代碼：160KB

→

40個頁面數(shù)據(jù)區(qū):

40KB→

10個頁面–采用信息共享（若ED可共享）后占用的內存空間？160K

+

40K

*

40

=

1760K2021/11/6116-圖419分頁系統(tǒng)中共享editor的示意圖ed1ed2…ed40data1…data10進程1ed1ed2…ed40data1…data10進程22122…6061…70頁表2122…6071…80頁表…ed1ed2…ed40data1…data10data1…data1021226061707180主存02021/11/6117圖4-20分段系統(tǒng)享editor的示意圖data1editor進程1data2editor進程2段長基址1608040240段表