1/29/2024遼東學(xué)院信息技術(shù)學(xué)院1第四章存儲(chǔ)器管理4.1存儲(chǔ)器的層次結(jié)構(gòu)4.2程序的裝入和鏈接

4.3

連續(xù)分配方式4.4基本分頁存儲(chǔ)管理方式4.5基本分段存儲(chǔ)管理方式4.6虛擬存儲(chǔ)器的基本概念4.7請求分頁存儲(chǔ)管理方式4.8頁面置換算法4.9請求分段存儲(chǔ)管理方式

1/29/20242速度容量小大低高4.1存儲(chǔ)器的層次結(jié)構(gòu)圖4-1計(jì)算機(jī)系統(tǒng)存儲(chǔ)層次示意

4.1.1多級(jí)存儲(chǔ)器結(jié)構(gòu)CPU的控制部件只能從主存儲(chǔ)器中取得指令和數(shù)據(jù)主存儲(chǔ)器的訪問速度遠(yuǎn)低于CPU執(zhí)行指令的速度1/29/202434.1.2主存儲(chǔ)器與寄存器4.1.3高速緩存和磁盤緩存主存中一些經(jīng)常訪問的信息存放在高速緩存中，減少訪問主存儲(chǔ)器的次數(shù)，可大幅度提高程序執(zhí)行速度磁盤的I/O速度遠(yuǎn)低于對主存的訪問速度，因此將頻繁使用的一部分磁盤數(shù)據(jù)和信息，暫時(shí)存放在磁盤緩存中，可減少訪問磁盤的次數(shù)(利用主存)將用戶源程序變?yōu)榭稍趦?nèi)存中執(zhí)行的程序的步驟：編譯：由編譯程序?qū)⒂脩粼创a編譯成若干個(gè)目標(biāo)模塊鏈接：由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊，以及它們所需要的庫函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存，構(gòu)造PCB，形成進(jìn)程(使用物理地址)1/29/202444.2程序的裝入和鏈接1/29/20245庫鏈接程序裝入模塊裝入程序…編譯程序產(chǎn)生的目標(biāo)模塊第一步第二步第三步內(nèi)存4.2.1程序的裝入

1．絕對裝入方式(AbsoluteLoadingMode)在編譯時(shí)，編譯程序?qū)a(chǎn)生絕對地址的目標(biāo)代碼-絕對裝入。2．可重定位裝入方式(RelocationLoadingMode)在多道程序環(huán)境下，所得到的目標(biāo)模塊的起始地址通常是從0開始的，程序中的其它地址也都是相對于起始地址0計(jì)算的。此時(shí)應(yīng)采用可重定位裝入方式。

1/29/202460100025005000LOAD1,25003651000011000LOAD1,125001250036515000地址變換在裝入時(shí)一次完成，以后不再改變3．動(dòng)態(tài)運(yùn)行時(shí)裝入方式(DynamicRun-timeLoading)

在運(yùn)行過程中它在內(nèi)存中的位置可能經(jīng)常要改變，此時(shí)就應(yīng)采用動(dòng)態(tài)運(yùn)行時(shí)裝入的方式。裝入內(nèi)存的所有地址都仍是相對地址，地址變換在運(yùn)行時(shí)才執(zhí)行BR=100001/29/2024703456......LOADA200......0100200300.........LOADA2003456110012001300200VR+1000BR4.2.2程序的鏈接(一組目標(biāo)模塊)靜態(tài)鏈接：在程序運(yùn)行前，將目標(biāo)模塊及所需的庫函數(shù)鏈接成一個(gè)完整的裝配模塊，以后不再拆開。裝入時(shí)動(dòng)態(tài)鏈接：指將用戶源程序編譯后所得的一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接的鏈接方式。運(yùn)行時(shí)動(dòng)態(tài)鏈接：指對某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要該目標(biāo)模塊時(shí)，才對它進(jìn)行鏈接。81、靜態(tài)鏈接(static-linking)9返回

*對相對地址進(jìn)行修改;

*變換外部調(diào)用符號(hào)事先進(jìn)行鏈接所形成的一個(gè)完整的裝入模塊，又稱為可執(zhí)行文件。通常都不再拆開它，要運(yùn)行時(shí)可直接將它裝入內(nèi)存模塊ACALLB;Return;0L-1模塊BCALLC;Return;0M-1模塊CReturn;0N-1模塊AJSR“L”Return;0L-1模塊BJSR“L+M”Return;LL+M-1模塊CReturn;L+ML+M+N-1目標(biāo)模塊裝入模塊對相對地址進(jìn)行修改變換外部調(diào)用符號(hào)2.裝入時(shí)動(dòng)態(tài)鏈接

(Load-timeDynamicLinking)

邊裝入邊鏈接。優(yōu)點(diǎn)：(1)便于修改和更新(2)便于實(shí)現(xiàn)對目標(biāo)模塊的共享103.運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-timeDynamicLinking)部分模塊運(yùn)行,邊執(zhí)行邊鏈接！優(yōu)點(diǎn)：加快裝入過程、節(jié)省內(nèi)存空間,未用到的模塊不會(huì)調(diào)入內(nèi)存114.3連續(xù)分配方式

特點(diǎn)：

為每個(gè)用戶程序分配連續(xù)的內(nèi)存空間

方法

單一連續(xù)分配

固定分區(qū)分配

動(dòng)態(tài)分區(qū)分配

可重定位分區(qū)分配124.3.1單一連續(xù)分配最簡單的一種存儲(chǔ)分配管理方法只能用于單用戶、單任務(wù)的操作系統(tǒng)中把內(nèi)存分為兩部分系統(tǒng)區(qū)：提供給OS使用，內(nèi)存的低址部分用戶區(qū)：提供給用戶使用。內(nèi)存系統(tǒng)區(qū)（OS）用戶區(qū)0100k進(jìn)程A進(jìn)程B134.3.2固定分區(qū)分配(多道)

1.劃分分區(qū)的方法分區(qū)大小相等，即使所有的內(nèi)存分區(qū)大小相等。(2)分區(qū)大小不等。內(nèi)存劃分為若干個(gè)固定大小的區(qū)域每個(gè)分區(qū)1個(gè)作業(yè)142.內(nèi)存分配內(nèi)存OS作業(yè)A作業(yè)B作業(yè)C作業(yè)D分區(qū)號(hào)大小(K)起址(K)狀態(tài)11224已分配22436已分配33060未分配43590已分配540125未分配650165已分配7297215未分配0K24K90K36K60K165K125K215K進(jìn)程F(70K)已分配進(jìn)程G(70K)分區(qū)說明表內(nèi)存分配程序154.3.3動(dòng)態(tài)分區(qū)分配(根據(jù)實(shí)際需要)

1.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表。

(2)空閑分區(qū)鏈(可以雙向鏈)。內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K0K35K111K77K91K151K136K226K分區(qū)號(hào)大小(K)始址(K)2423542091615136830226912022630151361/29/2024遼東學(xué)院信息技術(shù)學(xué)院162.分區(qū)分配算法首次適應(yīng)算法FF

(2)循環(huán)首次適應(yīng)算法NF

(3)最佳適應(yīng)算法BF(4)最壞適應(yīng)算法WF(5)快速適應(yīng)算法QF首次適應(yīng)法要求空閑區(qū)按首址遞增的次序組成空閑區(qū)表（鏈）,頭開始查找。

內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K170K35K111K77K91K151K136K226K354291202263015136內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K1/29/2024180K35K111K77K91K151K136K226K429135201361522630首次適應(yīng)算法FF1）作業(yè)1請求內(nèi)存空間25K（分配）2）作業(yè)D完成（回收）思考：作業(yè)1完成（回收）作業(yè)117K6017120K12030K作業(yè)作業(yè)A作業(yè)20K1/29/202419（1）（2）30K作業(yè)A作業(yè)20K作業(yè)（3）作業(yè)30K作業(yè)作業(yè)A20K（4）作業(yè)30K作業(yè)A20K作業(yè)10030100305002010030500201003018020回收內(nèi)存的四種情況20050首址200大小50K大小50K大小50K首址450大小50K80回收作業(yè)A4507010050020優(yōu)點(diǎn)：優(yōu)先利用低地址空間，從而保證高址空間有較大的空閑區(qū)缺點(diǎn)：低址部分被不斷劃分，留下許多難以利用的、很小的空閑分區(qū)每次都從低址開始，查找開銷大20分析

基于首次使用算法FF為進(jìn)程分配內(nèi)存,從上次找到的空閑區(qū)的下一個(gè)空閑區(qū)開始查找.A18,B101/29/2024遼東學(xué)院信息技術(shù)學(xué)院21循環(huán)首次適應(yīng)算法NF17913520136922610922363331023最佳適應(yīng)法要求按空閑區(qū)大小從小到大的次序組成空閑區(qū)表（鏈）。每次把能滿足作業(yè)要求，并且是最小的空閑分區(qū)分配給作業(yè)內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K220K35K111K77K91K151K136K226K136159120354230226內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K230K35K111K77K91K151K136K226K最佳適應(yīng)算法1）作業(yè)1請求內(nèi)存空間25K（分配）2）作業(yè)D完成（回收）思考：作業(yè)1完成（回收）作業(yè)15K90K136159120226303542251590優(yōu)點(diǎn)：在系統(tǒng)中若存在一個(gè)與申請分區(qū)大小相等的空閑區(qū)，必定會(huì)被選中，而首次適應(yīng)法則不一定。若系統(tǒng)中不存在與申請分區(qū)大小相等的空閑區(qū)，則選中的空閑區(qū)是滿足要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。缺點(diǎn)：空閑區(qū)的大小一般與申請分區(qū)大小不相等，因此將其一分為二，留下來的空閑區(qū)總是最小的，以致無法使用。隨著時(shí)間的推移，系統(tǒng)中的小空閑區(qū)會(huì)越來越多，從而造成存儲(chǔ)區(qū)的大量浪費(fèi)。

24分析返回最壞適應(yīng)法每次把能滿足作業(yè)要求，并且是最大的空閑分區(qū)分配給作業(yè)要求空閑區(qū)按大小遞減的順序組織空閑區(qū)表（或鏈）。

內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K250K35K111K77K91K151K136K226K354222630136152091內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K0K35K111K77K91K151K136K226K最壞適應(yīng)算法1）作業(yè)1請求內(nèi)存空間25K（分配）2）作業(yè)D完成（回收）思考：作業(yè)1完成（回收）作業(yè)117K120K3542226309120136156017136120最壞適應(yīng)法看起來似乎有些荒唐，但在嚴(yán)密地考察后，還是有它的優(yōu)點(diǎn)：當(dāng)程序裝入內(nèi)存中最大的空閑區(qū)后，剩下的空閑區(qū)還可能相當(dāng)大，還能裝下較大的程序。另一方面分配時(shí)每次僅作一次查詢工作。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院27分析上述三種放置策略各有利弊，到底哪種最好不能一概而論，而應(yīng)針對具體作業(yè)序列來分析。對于某一作業(yè)序列來說，某種算法能將該作業(yè)序列中所有作業(yè)安置完畢，那么我們說該算法對這一作業(yè)序列是合適的。對于某一算法而言，如它不能立即滿足某一要求，而其它算法卻可以滿足此要求，則這一算法對該作業(yè)序列是不合適的。

1/29/2024遼東學(xué)院信息技術(shù)學(xué)院28三種策略比較對于相同容量的空閑區(qū),單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表,2k,4k算法優(yōu)點(diǎn):(1)查找效率高，僅需要根據(jù)進(jìn)程的長度，尋找到能容納它的最小空閑區(qū)鏈表，并取下第一塊進(jìn)行分配即可。(2)另外該算法在進(jìn)行空閑分區(qū)分配時(shí)，不會(huì)對任何分區(qū)產(chǎn)生分割，所以能保留大的分區(qū)，滿足對大空間的需求，也不會(huì)產(chǎn)生內(nèi)存碎片

缺點(diǎn)：歸還分區(qū)算法復(fù)雜1/29/2024遼東學(xué)院信息技術(shù)學(xué)院29快速適應(yīng)算法(分類搜索)

1)分配內(nèi)存設(shè)請求的分區(qū)大小為u.size，表中每個(gè)空閑分區(qū)的大小可表示為m.size。若m.size-u.size≤size(size是事先規(guī)定的不再切割的剩余分區(qū)的大小)，說明多余部分太小，可不再切割，將整個(gè)分區(qū)分配給請求者；否則(即多余部分超過size)，從該分區(qū)中按請求的大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑分區(qū)鏈(表)中。然后，將分配區(qū)的首址返回給調(diào)用者。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院303．分區(qū)分配操作2)回收內(nèi)存當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈(表)中找到相應(yīng)的插入點(diǎn)，此時(shí)可能出現(xiàn)以下四種情況之一：(1)回收區(qū)與插入點(diǎn)的前一個(gè)空閑分區(qū)F1相鄰接(2)回收分區(qū)與插入點(diǎn)的后一空閑分區(qū)F2相鄰接。

(3)回收區(qū)同時(shí)與插入點(diǎn)的前、后兩個(gè)分區(qū)鄰接(4)回收區(qū)既不與F1鄰接，又不與F2鄰接。這時(shí)應(yīng)為回收區(qū)單獨(dú)建立一新表項(xiàng)，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈中的適當(dāng)位置。

1/29/2024遼東學(xué)院信息技術(shù)學(xué)院31例1：有作業(yè)序列：作業(yè)A要求18K；作業(yè)B要求25K，作業(yè)C要求30K。畫出空閑區(qū)鏈并分析一下哪個(gè)算法最合適此序列？1/29/2024遼東學(xué)院信息技術(shù)學(xué)院32舉例經(jīng)分析可知：最佳適應(yīng)法對這個(gè)作業(yè)序列是合適的，而其它兩種對該作業(yè)序列是不合適的。OS30作業(yè)20作業(yè)5作業(yè)46首次最佳最壞20501001201601652100203010020210465160160510020210463020210462030160520100有作業(yè)序列：作業(yè)A要求21K；作業(yè)B要求30K，作業(yè)C要求25K。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院33練習(xí)

用動(dòng)態(tài)分區(qū)分配方式管理主存時(shí),假定主存中按地址順序依次有5個(gè)空閑區(qū),空閑區(qū)的大小依次為32K,10K,5K,228K和100K,現(xiàn)有5個(gè)作業(yè)A,B,C,D,E.它們各需主存1K,10K,108K,28K和115K.若采用首次適應(yīng)算法能把這5個(gè)作業(yè)按順序全部裝入主存嗎?你認(rèn)為怎樣的次序裝入這5個(gè)作業(yè)可使主存的利用率最高?1/29/2024遼東學(xué)院信息技術(shù)學(xué)院34思考分區(qū)大小均為2的k次冪，k為整數(shù)，l≤k≤m.相同大小的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)雙向鏈表。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院354.3.4伙伴系統(tǒng)

1.分配一個(gè)長度為n的存儲(chǔ)空間時(shí)，首先計(jì)算一個(gè)i值，使2i－1<n≤2i，然后在空閑分區(qū)大小為2i的空閑分區(qū)鏈表中查找。若找到，即把該空閑分區(qū)分配給進(jìn)程;

2.否則，則在分區(qū)大小為2i＋1的空閑分區(qū)鏈表中尋找。若存在2i＋1的一個(gè)空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個(gè)分區(qū)，這兩個(gè)分區(qū)稱為一對伙伴，其中的一個(gè)分區(qū)用于分配，而把另一個(gè)加入分區(qū)大小為2i的空閑分區(qū)鏈表中;3.若大小為2i＋1的空閑分區(qū)也不存在，則需要查找大小為2i＋2的空閑分區(qū)，若找到則對其進(jìn)行兩次分割;…2i+k

分割K次.

1/29/2024遼東學(xué)院信息技術(shù)學(xué)院364.3.5哈希算法哈希算法就是利用哈?？焖俨檎业膬?yōu)點(diǎn)，以及空閑分區(qū)在可利用空間表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，該表的每一個(gè)表項(xiàng)記錄了一個(gè)對應(yīng)的空閑分區(qū)鏈表表頭指針。當(dāng)進(jìn)行空閑分區(qū)分配時(shí)，根據(jù)所需空閑分區(qū)大小，通過哈希函數(shù)計(jì)算，即得到在哈希表中的位置，從中得到相應(yīng)的空閑分區(qū)鏈表，實(shí)現(xiàn)最佳分配策略。

374.3.6可重定位分區(qū)分配

OS作業(yè)110作業(yè)230作業(yè)314作業(yè)426分區(qū)號(hào)起址大小35010512030716514923026

空閑分區(qū)表205060120150165179230作業(yè)A(40)80長度重定位寄存器作業(yè)120作業(yè)260作業(yè)3150作業(yè)41793060155120501101251769 21640緊湊/拼接:分散小分區(qū)拼接成一個(gè)大分區(qū)方法1/29/2024382．動(dòng)態(tài)重定位的實(shí)現(xiàn)

必須有硬件地址變換機(jī)構(gòu)的支持-重定位寄存器，用它來存放程序(數(shù)據(jù))在內(nèi)存中的起始地址。程序在執(zhí)行時(shí)，真正訪問的內(nèi)存地址=相對地址+重定位寄存器中的地址.動(dòng)態(tài)重定位:地址變換過程是在程序執(zhí)行期間，隨著對每條指令或數(shù)據(jù)的訪問自動(dòng)進(jìn)行的，故稱為動(dòng)態(tài)重定位。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院394.3.7對換(Swapping)1.對換的引入

所謂“對換”，是指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。對換是提高內(nèi)存利用率的有效措施。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院402.對換空間的管理

為了能對對換區(qū)中的空閑盤塊進(jìn)行管理，在系統(tǒng)中應(yīng)配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個(gè)表目中應(yīng)包含兩項(xiàng)，即對換區(qū)的首址及其大小，它們的單位是盤塊號(hào)和盤塊數(shù)。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院413.進(jìn)程的換出與換入(1)進(jìn)程的換出。系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，然后啟動(dòng)盤塊，將該進(jìn)程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。(2)進(jìn)程的換入。系統(tǒng)應(yīng)定時(shí)地查看所有進(jìn)程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進(jìn)程，將其中換出時(shí)間(換出到磁盤上)最久的進(jìn)程作為換入進(jìn)程，將之換入，直至已無可換入的進(jìn)程或無可換出的進(jìn)程為止。424.4基本分頁存儲(chǔ)管理方式

1．頁面和塊定義

1)頁面和物理塊分頁存儲(chǔ)管理是將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片，稱為頁面或頁，并為各頁加以編號(hào)，從0開始，如第0頁、第1頁等。

相應(yīng)地，也把內(nèi)存空間分成與頁面相同大小的若干個(gè)存儲(chǔ)塊，稱為(物理)塊或頁框(frame)，也同樣為它們加以編號(hào)，如0#塊、1#塊等等。

在為進(jìn)程分配內(nèi)存時(shí)，將進(jìn)程中的若干個(gè)頁分別裝入到多個(gè)可以不相鄰接的物理塊中。由于進(jìn)程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內(nèi)碎片”。

4.4.1

頁面與塊頁面大小頁面大小應(yīng)選地適中，應(yīng)是2的冪，通常是512B8KB。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院432.地址結(jié)構(gòu)位移量W頁號(hào)P3112110地址長度32位:011位為位移量(頁內(nèi)地址)，即每頁的大小為4KB1231位為頁號(hào)，地址空間最多允許有1M頁基本分頁存儲(chǔ)管理方式

若給定一個(gè)邏輯地址空間中的地址為A，頁面大小為L，則:

頁號(hào)P=INT[A/L]

頁內(nèi)地址d=[A]MODL

例如：系統(tǒng)頁面大小為1KB，設(shè)A=2170B，則:P=2，d=1221/29/2024遼東學(xué)院信息技術(shù)學(xué)院44基本分頁存儲(chǔ)管理方式1/29/202445

3．頁表

系統(tǒng)又為每個(gè)進(jìn)程建立了一張頁面映像表，稱頁表。記錄了相應(yīng)頁在內(nèi)存中對應(yīng)的物理塊號(hào)

。在配置了頁表后，進(jìn)程執(zhí)行時(shí)，通過查找該表，即可找到每頁在內(nèi)存中的物理塊號(hào)?？梢姡摫淼淖饔檬菍?shí)現(xiàn)從頁號(hào)到物理塊號(hào)的地址映射。

4.4.2地址變換機(jī)構(gòu)1.基本的地址變換機(jī)構(gòu)

頁表可以由一組專門的寄存器來實(shí)現(xiàn)，一個(gè)頁表項(xiàng)用一個(gè)寄存器。但寄存器成本高，系統(tǒng)頁表可能很大，所以頁表大多常駐內(nèi)存。

在系統(tǒng)中只設(shè)置一個(gè)頁表寄存器PTR，在其中存放頁表在內(nèi)存中的始址和頁表的長度。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院46基本分頁存儲(chǔ)管理方式47CPU邏輯地址頁表基址寄存器頁表地址頁表長度pd<越界中斷+頁表01…pb…物理地址主存儲(chǔ)器bd×頁面大小物理地址=頁框號(hào)(塊號(hào))×頁面大小+頁內(nèi)位移某分頁系統(tǒng)，主存容量為64K，頁面大小為1K，對一個(gè)4頁大的作業(yè)，其0、1、2、3頁分別被分配到主存的2、4、6、7塊中。將十進(jìn)制的邏輯地址1023、2500、4500轉(zhuǎn)換為物理地址★邏輯地址1023：1023/1K得頁號(hào)為0，頁內(nèi)地址為1023，查頁表找到對應(yīng)得物理塊為2，故物理地址為2*1K+1023=3071。★邏輯地址2500：2500/1K得頁號(hào)為2，頁內(nèi)地址為452，查頁表找到對應(yīng)得物理塊為6，故物理地址為6*1K+452=6596。★邏輯地址4500：4500/1K得頁號(hào)為4，頁內(nèi)地址為404，頁號(hào)大于頁表長度，產(chǎn)生越界中斷48頁式地址變換舉例頁表始址頁表長度頁表寄存器頁號(hào)頁面號(hào)有效地址02132821C4物理地址81C4基本分頁存儲(chǔ)管理方式例：設(shè)頁長為1K，程序地址字長為16位，用戶程序空間和頁表如圖，求用戶程序中Move指令中相對地址對應(yīng)的絕對地址。

49用戶程序Mover1,[2500]01001K2K25003K-1頁表頁號(hào)塊號(hào)021427內(nèi)存01K2K3K4K5K6K7K8K9K10K-1課堂練習(xí)1/29/2024遼東學(xué)院信息技術(shù)學(xué)院50

假定某頁式管理系統(tǒng)，主存為64KB，分成16塊，塊號(hào)為0，1，2，…15。設(shè)某作業(yè)有4頁，其頁號(hào)為0，1，2，3，被分別裝入主存的2、4、1、6塊。試問：該作業(yè)的總長度是多少字節(jié)？寫出該作業(yè)每一頁在主存中的起始地址；對多個(gè)邏輯地址[0，100]、[1，50]、[2，0]、[3，60]，試計(jì)算出相應(yīng)的內(nèi)存地址。課堂練習(xí)1/29/2024遼東學(xué)院信息技術(shù)學(xué)院51例：設(shè)虛地址為(357101)8

每一塊為128字節(jié)，求出頁號(hào)及頁內(nèi)地址（偏移量）128＝27(357101)8＝(011,101,111,001,000,001

)21 6 7 4 1 0 1偏移為(101)8,頁號(hào)為(1674)8塊號(hào)由頁表指定，偏移不變2.具有快表的地址變換機(jī)構(gòu)CPU在每存取一個(gè)數(shù)據(jù)時(shí)，需要兩次訪問內(nèi)存：第一次：訪問頁表，找到指定頁的物理塊號(hào)，將塊號(hào)與頁內(nèi)偏移量拼接形成物理地址。第二次：從第一次所得地址中獲得所需數(shù)據(jù)，或向此地址中寫入數(shù)據(jù)。處理速度降低！解決方法：在地址變換機(jī)構(gòu)中，增設(shè)一個(gè)具有并行查尋能力的特殊高速緩沖寄存器，稱為“聯(lián)想存儲(chǔ)器”或“快表”。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院52基本分頁存儲(chǔ)管理方式1/29/2024遼東學(xué)院信息技術(shù)學(xué)院53頁表長度頁表始址頁表寄存器頁內(nèi)地址頁號(hào)(3)邏輯地址Ldb物理地址<+越界中斷b1塊號(hào)頁號(hào)頁表具有快表的分頁系統(tǒng)的地址變換機(jī)構(gòu)：b塊號(hào)頁號(hào)快表輸入寄存器1/29/2024遼東學(xué)院信息技術(shù)學(xué)院54假定快表的命中率為98%,快表的訪問時(shí)間為20ns,內(nèi)存的一次訪問時(shí)間為100ns,則有效訪問時(shí)間為:課堂練習(xí)EAT(EffectiveAccessTime)=98%(20+100)+2%(20+200)=122ns基本分頁存儲(chǔ)管理方式4.4.3兩級(jí)和多級(jí)頁表

現(xiàn)代計(jì)算機(jī)系統(tǒng)都支持非常大的邏輯地址空間(232

264)，頁表就非常大，需占用較大的地址空間。例如：一個(gè)具有32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4KB即212B，則每個(gè)進(jìn)程頁表的頁表項(xiàng)可達(dá)1M個(gè)，若每個(gè)頁表項(xiàng)占用4個(gè)字節(jié)，則每個(gè)進(jìn)程的頁表就要占據(jù)4MB的內(nèi)存空間，而且要求連續(xù)存放。55基本分頁存儲(chǔ)管理方式1.兩級(jí)頁表

1/29/2024遼東學(xué)院信息技術(shù)學(xué)院56例如：32位邏輯地址空間，頁面大小為4KB(即12位)，若采用一級(jí)頁表機(jī)構(gòu)，應(yīng)有20位頁號(hào)，即頁表項(xiàng)應(yīng)有1M個(gè)；在采用兩級(jí)頁表機(jī)構(gòu)時(shí)，再對頁表進(jìn)行分頁，使每頁包含210(即1024)個(gè)頁表項(xiàng)，最多允許有210個(gè)頁表分頁。即頁內(nèi)地址外層頁內(nèi)地址外層頁號(hào)dp2p131222112110基本分頁存儲(chǔ)管理方式1/29/2024遼東學(xué)院信息技術(shù)學(xué)院57………012345671141151468內(nèi)存空間…641第0頁頁表012…1023115114第1頁頁表012…10231468第n頁頁表012…1023174210781011012n外部頁表兩級(jí)分頁結(jié)構(gòu)1/29/2024遼東學(xué)院信息技術(shù)學(xué)院58外部頁表寄存器外部頁表頁表db物理地址++dP2P1邏輯地址外部頁號(hào)外部頁內(nèi)地址頁內(nèi)地址具有兩級(jí)頁表的地址變換機(jī)構(gòu)：外層頁號(hào)p1,外層頁內(nèi)地址p2，頁內(nèi)地址d三部分構(gòu)成，若給定一個(gè)邏輯地址空間的地址為A,系統(tǒng)頁面大小為L，頁表項(xiàng)的長度為N。在采用二級(jí)頁表結(jié)構(gòu)時(shí)：p1=INT[INT[A/L]/N]p2=MOD[INT[A/L]/N]d=MOD[A/L]

上述方法用離散分配空間解決了大頁表無需大片存儲(chǔ)空間的問題，但并未減少頁表所占的內(nèi)存空間。

解決方法是把當(dāng)前需要的一批頁表項(xiàng)調(diào)入內(nèi)存，以后再根據(jù)需要陸續(xù)調(diào)入。2.多級(jí)頁表

兩級(jí)頁表對32位機(jī)器適用，64位呢？

頁面大小為4KB即212B，還剩52位，按物理塊大小212位來劃分頁表，則剩余40位用于外層頁號(hào)，此時(shí)外層頁表可能有1024G個(gè)頁表項(xiàng)，要占用4096GB的連續(xù)存儲(chǔ)空間

解決方法：采用多級(jí)頁表，將外層頁表再進(jìn)行分頁。59基本分頁存儲(chǔ)管理方式1/29/2024遼東學(xué)院信息技術(shù)學(xué)院60多級(jí)頁表地址映射基本分頁存儲(chǔ)管理方式1/29/2024遼東學(xué)院信息技術(shù)學(xué)院614.5基本分段存儲(chǔ)管理方式4.5.1分段存儲(chǔ)管理方式的引入

引入分段存儲(chǔ)管理方式，主要是為了滿足用戶和程序員的下述一系列需要：

1)方便編程Loadr1,[A,100]Storer2,[B,500]2)信息共享

3)信息保護(hù)

4)動(dòng)態(tài)增長

5)動(dòng)態(tài)鏈接基本分段存儲(chǔ)管理方式1/29/2024遼東學(xué)院信息技術(shù)學(xué)院62頁式管理是把內(nèi)存視為一維線性空間；而段式管理是把內(nèi)存視為二維空間，與進(jìn)程邏輯相一致。將程序的地址空間劃分為若干個(gè)段(segment)，程序加載時(shí)，分配其所需的所有段（內(nèi)存分區(qū)），這些段不必連續(xù)；物理內(nèi)存的管理采用動(dòng)態(tài)分區(qū)。需要硬件支持。4.5.2分段系統(tǒng)的基本原理基本分段存儲(chǔ)管理方式

程序通過分段(segmentation)劃分為多個(gè)模塊，如代碼段、數(shù)據(jù)段、共享段?？梢苑謩e編寫和編譯可以針對不同類型的段采取不同的保護(hù)可以按段為單位來進(jìn)行共享，包括通過動(dòng)態(tài)鏈接進(jìn)行代碼共享優(yōu)點(diǎn)：沒有內(nèi)碎片，外碎片可以通過內(nèi)存緊縮來消除。便于改變進(jìn)程占用空間的大小。缺點(diǎn)：進(jìn)程全部裝入內(nèi)存。634.5.2分段系統(tǒng)的基本原理基本分段存儲(chǔ)管理方式1/29/2024遼東學(xué)院信息技術(shù)學(xué)院64段號(hào)段表65

所需表目(1)段表：每進(jìn)程一個(gè)段首址段長度100k40k80k60k段號(hào)0:1:2:3:20k200k320k300k(2)空閑表：系統(tǒng)一個(gè)

arrayof(addr,size)基本分段存儲(chǔ)管理方式66

所需寄存器(1)段表寄存器：bl段表首址段表長度系統(tǒng)一個(gè)(2)快表：系統(tǒng)一組：

段號(hào)段首址段長度............l’s...b’...基本分段存儲(chǔ)管理方式1/29/2024遼東學(xué)院信息技術(shù)學(xué)院674.5.2分段系統(tǒng)的基本原理1.分段分段地址中的地址具有如下結(jié)構(gòu)：段號(hào)段內(nèi)地址3116150基本分段存儲(chǔ)管理方式該地址結(jié)構(gòu)允許一個(gè)作業(yè)最長有64K個(gè)段，每段的最大長度為64KB。2.段表

段表可以存放在寄存器中，但更多的是存放在內(nèi)存中。

段表可以實(shí)現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院68基本分段存儲(chǔ)管理方式69

利用段表實(shí)現(xiàn)地址映射M(0)30KX(1)20KD(2)15KF(3)10K用戶作業(yè)作業(yè)空間內(nèi)存空間M(0)30KX(1)20KD(2)15KF(3)10K040K80K120K150K30K40K20K80K15K120K10K150K段表段長基址012370分段系統(tǒng)的地址變換過程3.地址變換機(jī)構(gòu)段號(hào)S位移量W210K控制寄存器段表始址200K段表長度4<越界+30K40K20K80K15K120K10K150K段長基址<+內(nèi)存040K80K120K150K越界71例:段表如下：回答下列問題：1．計(jì)算該作業(yè)訪問[0，432]，[1，10]，[2，500]，[3，400]時(shí)的絕對地址2．總結(jié)段式存儲(chǔ)管理的地址轉(zhuǎn)換過程。段號(hào)段長主存起始地址0123466014010058096022193300901237195972

段表如下：計(jì)算該作業(yè)訪問[0，216]，[1，120]，[2，210]，[3，456]時(shí)的絕對地址段號(hào)段長主存起始地址01234660140100580960221933009012371959課堂練習(xí)1/29/2024遼東學(xué)院信息技術(shù)學(xué)院73

注意：當(dāng)段表存放在內(nèi)存中時(shí)，每訪問一個(gè)數(shù)據(jù)，都需訪問兩次內(nèi)存，降低了計(jì)算機(jī)的速率。

解決方法：設(shè)置聯(lián)想寄存器，用于保存最近常用的段表項(xiàng)?；痉侄未鎯?chǔ)管理方式4.分頁和分段的主要區(qū)別相似點(diǎn)：采用離散分配方式，通過地址映射機(jī)構(gòu)實(shí)現(xiàn)地址變換不同點(diǎn)：頁是信息的物理單位，分頁是為了滿足系統(tǒng)的需要；段是信息的邏輯單位，含有一組意義相對完整的信息，分段是為了滿足用戶的需要。頁的大小固定且由系統(tǒng)確定，由系統(tǒng)把邏輯地址分為頁號(hào)和頁內(nèi)地址，由機(jī)器硬件實(shí)現(xiàn)；段的長度不固定，取決于用戶程序，編譯程序?qū)υ闯绦蚓幾g時(shí)根據(jù)信息的性質(zhì)劃分。分頁的作業(yè)地址空間是一維的；分段的作業(yè)地址空間是二維的。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院74基本分段存儲(chǔ)管理方式754.5.3信息共享分頁系統(tǒng)中共享editor的示意圖（頁面大小為1K）兩個(gè)進(jìn)程共享文本編輯程序Editor，程序大小4K，另每個(gè)進(jìn)程自身的數(shù)據(jù)2K進(jìn)程1ed1ed2ed3ed4data1data2進(jìn)程2ed1ed2ed3ed4data1data2頁表202122234041頁表202122235051主存0…Ed120Ed221Ed322ed423…data140data241…data150data251遼東學(xué)院信息技術(shù)學(xué)院76分段系統(tǒng)中共享editor的示意圖進(jìn)程1editordata1進(jìn)程2editordata2段表段長基址4K20K2K40K段表段長基址4K20K2K50K主存0…20editor…40data1…50data2分段系統(tǒng)的一個(gè)突出優(yōu)點(diǎn)是易于實(shí)現(xiàn)段的共享，允許若干個(gè)進(jìn)程共享一個(gè)或多個(gè)分段，且對段的保護(hù)十分簡單易行?？芍厝氪a(純代碼):是一個(gè)允許多個(gè)進(jìn)程同時(shí)訪問的代碼.純代碼不允許任何進(jìn)程對其修改774.5.4段頁式存儲(chǔ)管理

(segmentationwithpaging)段式優(yōu)于頁式便于共享和保護(hù)頁式優(yōu)于段式消除“外碎片”問題段頁式：結(jié)合二者優(yōu)點(diǎn)每個(gè)進(jìn)程包含若干段每個(gè)段包含若干頁基本分段存儲(chǔ)管理方式781.基本原理圖4-20作業(yè)地址空間和地址結(jié)構(gòu)頁基本分段存儲(chǔ)管理方式79

基本原理內(nèi)存空間劃分：(同頁式)

靜態(tài)等長，2i,稱為一頁。物理地址=(塊號(hào),塊內(nèi)地址)=(f,w)

進(jìn)程空間劃分：一個(gè)進(jìn)程若干個(gè)段一個(gè)段若干個(gè)頁邏輯地址=(段號(hào),邏輯頁號(hào),頁內(nèi)地址)=(s,p,w)基本分段存儲(chǔ)管理方式80利用段表和頁表實(shí)現(xiàn)地址映射主程序段0123子程序段01數(shù)據(jù)段012段號(hào)狀態(tài)頁表大小頁表始址041001220023400段表頁號(hào)狀態(tài)存儲(chǔ)塊#020122223324頁表頁號(hào)狀態(tài)存儲(chǔ)塊#040142頁表頁號(hào)狀態(tài)存儲(chǔ)塊#050151252頁表主存0…2021222324…404142…505152…1/29/202481段表長度段表始址段表寄存器塊內(nèi)地址塊號(hào)f物理地址<+段超長2.段頁式系統(tǒng)的地址變換機(jī)構(gòu)(3次訪問內(nèi)存)頁內(nèi)地址頁號(hào)P段號(hào)Sf1塊號(hào)頁號(hào)頁表0123+段表0123頁表長度頁表始址1/29/2024遼東學(xué)院信息技術(shù)學(xué)院824.6虛擬存儲(chǔ)器的基本概念4.6.1引入1.常規(guī)存儲(chǔ)管理的特征：一次性（指全部裝入）駐留性（指駐留在內(nèi)存不換出,即使I/O）2、局部性原理早在1968年，Denning.P就曾指出：程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律局限某部分-空間某區(qū)域(1)程序執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，在大多數(shù)情況下仍是順序執(zhí)行的。

1M內(nèi)存:

可以運(yùn)行2M進(jìn)程?3個(gè)作業(yè)共需2.8M內(nèi)存,運(yùn)行?1/29/202483局部性還表現(xiàn)在：時(shí)間局部性：執(zhí)行過的指令不久后可能再被執(zhí)行空間局部性：訪問過的存儲(chǔ)單元,不久后附近存儲(chǔ)單元也會(huì)被訪問。(2)過程調(diào)用將會(huì)使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域，但經(jīng)研究看出，過程調(diào)用的深度在大多數(shù)情況下都不超過5。這就是說，程序?qū)?huì)在一段時(shí)間內(nèi)都局限在這些過程的范圍內(nèi)運(yùn)行。(3)程序中存在許多循環(huán)結(jié)構(gòu)，這些雖然只由少數(shù)指令構(gòu)成，但是它們將多次執(zhí)行。(4)程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理，如對數(shù)組進(jìn)行操作，它們往往都局限于很小的范圍內(nèi)。

1/29/2024843．虛擬存儲(chǔ)器的定義

基于局部性原理，部分裝入。缺頁/段，將它們調(diào)入內(nèi)存。如果此時(shí)內(nèi)存已滿，利用頁(段)的置換功能。虛擬存儲(chǔ)器:具有請求調(diào)入和置換功能,能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng).其容量=內(nèi)存+外存,速度-內(nèi)存,成本-外存1/29/2024遼東學(xué)院信息技術(shù)學(xué)院85引入虛擬存儲(chǔ)技術(shù)的好處大程序：可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序；大的用戶空間：提供給用戶可用的虛擬內(nèi)存空間通常大于物理內(nèi)存(realmemory)并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行；易于開發(fā)：與覆蓋技術(shù)比較，不必影響編程時(shí)的程序結(jié)構(gòu)1/29/2024遼東學(xué)院信息技術(shù)學(xué)院864.6.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方法需要?jiǎng)討B(tài)重定位1、請求分頁系統(tǒng):以頁為單位轉(zhuǎn)換需硬件：（1）請求分頁的頁表機(jī)制（2）缺頁中斷（3）地址變換機(jī)構(gòu)需軟件（置換軟件等）2、請求分段系統(tǒng):以段為單位轉(zhuǎn)換:（1）請求分段的段表結(jié)構(gòu)（2）缺段中斷（3）地址變換機(jī)構(gòu)需實(shí)現(xiàn)請求分段機(jī)制的軟件（置換軟件等）1/29/2024遼東學(xué)院信息技術(shù)學(xué)院874.6.3虛擬存儲(chǔ)器的特征多次性：一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行對換性：允許在作業(yè)的運(yùn)行過程中進(jìn)行換進(jìn)、換出。虛擬性：能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院884.7請求分頁存儲(chǔ)管理方式4.7.1請求分頁中的硬件支持1.頁表機(jī)制頁號(hào)物理塊號(hào)狀態(tài)位P訪問字段A修改位M外存地址指示該頁是否已調(diào)入內(nèi)存記錄本頁在一段時(shí)間內(nèi)被訪問的次數(shù)，或記錄本頁最近已有多長時(shí)間未被訪問，供選擇換出頁面時(shí)參考該頁在調(diào)入內(nèi)存后是否被修改過，供置換頁面時(shí)參考指出該頁在外存上的地址，供調(diào)入該頁時(shí)參考1/29/2024遼東學(xué)院信息技術(shù)學(xué)院892.缺頁中斷機(jī)構(gòu)

在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存時(shí)，便產(chǎn)生一缺頁中斷，請求OS將所缺之頁調(diào)入內(nèi)存缺頁中斷又是一種特殊的中斷，它與一般的中斷相比，有著明顯的區(qū)別，主要表現(xiàn)在下面兩個(gè)方面：(1)在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)

(2)一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。TOB指令copyAA:

B:頁面6543211/29/2024遼東學(xué)院信息技術(shù)學(xué)院903.地址變換機(jī)構(gòu)1/29/2024遼東學(xué)院信息技術(shù)學(xué)院914.7.2內(nèi)存分配策略和分配算法1.最小物理塊數(shù)的確定進(jìn)程應(yīng)獲得的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式如：MovA,[B]允許間接尋址：則至少要求3個(gè)物理塊。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院922.物理塊的分配策略

1)固定分配局部置換(FixedAllocation,LocalReplacement)缺點(diǎn)：難以確定固定分配的頁數(shù)(少：置換率高/多：浪費(fèi))2)可變分配全局置換(VariableAllocation,GlobalReplacement):OS預(yù)留部分空閑塊3)可變分配局部置換(VariableAllocation,LocalReplacement）根據(jù)進(jìn)程的缺頁率進(jìn)行頁面數(shù)調(diào)整，進(jìn)程之間相互不會(huì)影響內(nèi)存分配策略：固定和可變分配策略置換策略：全局置換和局部置換為每個(gè)進(jìn)程分配固定數(shù)目物理塊淘汰頁面只能在自己進(jìn)程空間選擇1/29/2024遼東學(xué)院信息技術(shù)學(xué)院933.物理塊分配算法1)平均分配算法將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。缺點(diǎn)：未考慮各進(jìn)程本身的大小。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院942)按比例分配算法這是根據(jù)進(jìn)程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n個(gè)進(jìn)程，每個(gè)進(jìn)程的頁面數(shù)為Si，則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為：又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個(gè)進(jìn)程所能分到的物理塊數(shù)為bi，將有：b應(yīng)該取整，它必須大于最小物理塊數(shù)。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院953)考慮優(yōu)先權(quán)的分配算法

在實(shí)際應(yīng)用中，為了照顧重要的、急迫的作業(yè)盡快完成，應(yīng)為它分配較多的內(nèi)存空間。方法：一部分按比例分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院964.7.3調(diào)頁策略1.何時(shí)調(diào)入頁面

（1）請調(diào)(demandpaging)uponpagefault,發(fā)生缺頁中斷時(shí)調(diào)入（較費(fèi)系統(tǒng)開銷）（2）預(yù)調(diào)(prepaging)beforepagefault,將要訪問時(shí)調(diào)入(根據(jù)程序順序行為，不一定準(zhǔn)）（根據(jù)空間局部性，目前：成功率≤50％）預(yù)調(diào)必須輔以請調(diào)。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院972.從何處調(diào)入頁面

外存：文件區(qū)(離散分配)、對換區(qū)(連續(xù)分配)足夠的對換區(qū)空間：都從兌換區(qū)調(diào)入。缺少足夠的對換區(qū)空間：不會(huì)被修改頁直接從文件區(qū)調(diào)入,淘汰丟棄;修改過寫回交換區(qū)UNIX方式：1/29/2024遼東學(xué)院信息技術(shù)學(xué)院98★缺頁中斷★保留CPU環(huán)境★缺頁中斷處理★訪問內(nèi)存數(shù)據(jù)3.頁面調(diào)入過程1、基本思想在進(jìn)程開始運(yùn)行之前，不是裝入全部頁面，而是裝入幾個(gè)或零個(gè)頁面，之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其它頁面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁面，以便裝入新的頁面99小結(jié)100XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K虛地址空間物理地址空間}虛頁頁框頁號(hào)、物理塊號(hào)、狀態(tài)位、外存地址、訪問位、修改位 狀態(tài)位：表示該頁是在內(nèi)存還是在外存訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法決定）修改位：查看此頁是否在內(nèi)存中被修改過1012、頁表表項(xiàng)頁號(hào)物理塊號(hào)狀態(tài)位外存地址訪問位修改位102151413121110987654321000000000000000011110000101100000000000001111001000111010011010100010000000000100011000000000100110在/不在內(nèi)存頁表虛地址8196物理地址24580在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號(hào)后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，準(zhǔn)備將該頁調(diào)入內(nèi)存此時(shí)應(yīng)將缺頁的進(jìn)程掛起（調(diào)頁完成喚醒）1/29/2024遼東學(xué)院信息技術(shù)學(xué)院1033、缺頁中斷（PageFault）處理如果內(nèi)存中有空閑塊，則分配一個(gè)塊，將要調(diào)入的頁裝入該塊，并修改頁表中相應(yīng)頁表項(xiàng)目的狀態(tài)位及相應(yīng)的內(nèi)存塊號(hào)若此時(shí)內(nèi)存中沒有空閑塊，則要淘汰某頁（若被淘汰頁在內(nèi)存期間被修改過，則要將其寫回外存）1/29/2024遼東學(xué)院信息技術(shù)學(xué)院104缺頁中斷同一般中斷的區(qū)別？1/29/2024遼東學(xué)院信息技術(shù)學(xué)院105思考

缺頁中斷同一般中斷都是中斷相同點(diǎn)是：保護(hù)現(xiàn)場中斷處理恢復(fù)現(xiàn)場不同點(diǎn)：一般中斷是一條指令完成后接受和處理中斷，缺頁中斷是一條指令執(zhí)行過程中產(chǎn)生和處理中斷一條指令執(zhí)行時(shí)可能產(chǎn)生多個(gè)缺頁中斷。如指令可能訪問多個(gè)內(nèi)存地址，這些地址在不同的頁中。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院1061074.8頁面置換算法4.8.1最佳置換算法和先進(jìn)先出置換算法1.最佳(Optimal)置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時(shí)間內(nèi)不再被訪問的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。用于：頁淘汰、段淘汰、快表淘汰。108

假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁面號(hào)引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，17F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺頁標(biāo)志70F701F201F201203F203243F243243203F203203201F201201201701F701701缺頁9次，總訪問次數(shù)20次，缺頁率9/20＝45％頁面置換6次，置換率6/20=30%最佳置換算法（OPT）例1/29/2024遼東學(xué)院信息技術(shù)學(xué)院1092.先進(jìn)先出(FIFO)頁面置換算法

該算法的實(shí)質(zhì)是：總是選擇作業(yè)中在主存駐留時(shí)間最長（即最老）的一頁淘汰。即先進(jìn)入主存的頁先退出主存。其理由是，最早調(diào)入主存的頁，其不再被使用的可能性比最近調(diào)入主存的頁要大。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院1107F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺頁標(biāo)志70F701F201F201231F230F430F420F423F023F023023013F012F012012712F702F701F缺頁15次，總訪問次數(shù)20次，缺頁率15/20＝75％頁面置換12次，置換率12/20=60%先進(jìn)先出置換算法（FIFO）例

1/29/2024遼東學(xué)院信息技術(shù)學(xué)院111有一虛擬存儲(chǔ)系統(tǒng)，采用先進(jìn)先出的頁面淘汰算法。在內(nèi)存中為每個(gè)進(jìn)程分配3塊。進(jìn)程執(zhí)行時(shí)使用頁號(hào)的順序?yàn)?32143543215(1) 該進(jìn)程運(yùn)行時(shí)總共出現(xiàn)幾次缺頁（假設(shè)進(jìn)程運(yùn)行前所有頁面均不在內(nèi)存中）。(2) 若每個(gè)進(jìn)程在內(nèi)存有4塊，又將產(chǎn)生幾次缺頁。(3) 如何解釋所出現(xiàn)的現(xiàn)象。例

112432143543215m=34×132×142×143×543×523×521×43×432×共缺頁中斷9次113m=44321435432154×4321×5321×5421×5431×5432×1432×43×432×1532×共缺頁中斷10次1/29/2024遼東學(xué)院信息技術(shù)學(xué)院114m=3時(shí)，缺頁中斷9次m=4時(shí)，缺頁中斷10次FIFO算法會(huì)產(chǎn)生異?，F(xiàn)象（Belady現(xiàn)象），即：當(dāng)分配給進(jìn)程的物理頁面數(shù)增加時(shí)，缺頁次數(shù)反而增加1/29/2024遼東學(xué)院信息技術(shù)學(xué)院115顛簸:在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多，此時(shí)系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動(dòng)原因：頁面淘汰算法不合理分配給進(jìn)程的物理頁面數(shù)太少顛簸（抖動(dòng)）1164.8.2最近最久未使用(LRU)置換算法1.LRU(LeastRecentlyUsed)置換算法的描述

算法的實(shí)質(zhì)是：當(dāng)需要置換一頁時(shí)，選擇在最近一段時(shí)間內(nèi)最久不用的頁予以淘汰。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院1177F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺頁標(biāo)志70F701F201F201203F203403F402F432F032F032032132F132102F102107F107107缺頁12次，總訪問次數(shù)20次，缺頁率12/20＝60％頁面置換9次，置換率9/20=45%最近最久未使用置換算法（LRU）例1/29/2024遼東學(xué)院信息技術(shù)學(xué)院1182.LRU置換算法的硬件支持1)寄存器為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存器，可表示為:

R=Rn-1Rn-2Rn-3…R2R1R0

當(dāng)進(jìn)程訪問某物理塊時(shí)，要將相應(yīng)寄存器的Rn-1位(高位)置成1。此時(shí)，定時(shí)信號(hào)將每隔一定時(shí)間(例如100ms)將寄存器右移1位.淘汰算法:最小數(shù)值的寄存器所對應(yīng)的頁面119圖某進(jìn)程具有8個(gè)頁面時(shí)的LRU訪問情況R實(shí)頁R7R6R5R4R3R2R1R0123456789000000000000000000000000000000000000000000000000000000000000000000000000R實(shí)頁R7R6R5R4R3R2R1R0123456789100100100000000000000000000000000000000000000000000000000000000000000000R實(shí)頁R7R6R5R4R3R2R1R01234567890000000001001001000000000000000000000000000000000000000000000000000000001R實(shí)頁R7R6R5R4R3R2R1R01234567890000001001001001000100000011110010000000010011110000000010000010010000001/29/2024遼東學(xué)院信息技術(shù)學(xué)院1202)棧701203042210021302032403707107240用棧保存當(dāng)前使用頁面時(shí)棧的變化情況每當(dāng)進(jìn)程訪問某頁面時(shí)，便將該頁面的頁面號(hào)從棧中移出，將它壓入棧頂4.8.3Clock置換算法1.簡單的Clock置換算法:

每頁設(shè)置一位訪問位(1,0)，內(nèi)存中的所有頁鏈接成一個(gè)循環(huán)隊(duì)列,淘汰頁面過程:循環(huán)檢查各頁面的使用情況，訪問位為“0”，選擇該頁淘汰；訪問位為“1”，置為“0”，查詢指針前進(jìn)一步。最后回到隊(duì)首循環(huán)檢查各頁面使用情況--clock算法.又稱為“最近未使用”置換算法（NRU）1/29/2024122

下一個(gè)頁指針1/29/2024遼東學(xué)院信息技術(shù)學(xué)院1232.改進(jìn)型Clock置換算法

由訪問位A和修改位M可以組合成下面四種類型的頁面：

1類(A=0,M=0):表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。

2類(A=0,M=1)：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。

3類(A=1,M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問。

4類(A=1,M=1):最近已被訪問且被修改，該頁可能再被訪問。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院124

執(zhí)行過程

訪問位A，修改位M共同表示

一個(gè)頁面的狀態(tài)四種狀態(tài)：00011011

三輪掃描：第一輪：淘汰00頁面，未找到，下一步；第二輪：淘汰01頁面，非01頁面-A位復(fù)位為“0”，反復(fù)執(zhí)行第一輪和第二輪1/29/2024遼東學(xué)院信息技術(shù)學(xué)院1254.8.4其它置換算法1）最少使用(LFU：LeastFrequentlyUsed)置換算法選擇到當(dāng)前時(shí)間為止被訪問次數(shù)最少的頁面被置換；每頁設(shè)置訪問計(jì)數(shù)器，每當(dāng)頁面被訪問時(shí)，該頁面的訪問計(jì)數(shù)器加1；發(fā)生缺頁中斷時(shí)，淘汰計(jì)數(shù)值最小的頁面，并將所有計(jì)數(shù)清零；1/29/2024遼東學(xué)院信息技術(shù)學(xué)院1262）頁面緩沖算法(PBA：PageBufferingAlgorithm)它是對FIFO算法的發(fā)展，通過被置換頁面的緩沖，有機(jī)會(huì)找回剛被置換的頁面；被置換頁面的選擇和處理：用FIFO算法選擇被置換頁，把被置換的頁面放入兩個(gè)鏈表之一。如果頁面未被修改，就將其歸入到空閑頁面鏈表的末尾否則將其歸入到已修改頁面鏈表。1/29/2024遼東學(xué)院信息技術(shù)學(xué)院127需要調(diào)入新的物理頁面時(shí)，將新頁面內(nèi)容讀入到空閑頁面鏈表的第一項(xiàng)所指的頁面，然后將第一項(xiàng)刪除（從空閑鏈表摘下）?？臻e頁面和已修改頁面，仍停留在內(nèi)存中一段時(shí)間，如果這些頁面被再次訪問，只需較小開銷，而被訪問的頁面可以返還作為進(jìn)程的內(nèi)存頁。當(dāng)已修改頁面達(dá)到一定數(shù)目后，再將它們一起調(diào)出到外存，然后將它們歸入空閑頁面鏈表，這樣能大大減少I/O操作的次數(shù)。1284.9請求分段存儲(chǔ)管理方式4.9.1請求分段中的硬件支持1.段表機(jī)制段名段長段的基址存取方式訪問字段A修改位M存在位P增補(bǔ)位外存始址標(biāo)志本分段的存取屬性記錄該段被訪問的頻繁程度（與分頁相應(yīng)字段同）該段在調(diào)入內(nèi)存后是否被修改過，供置換時(shí)參考指示本段是否已調(diào)入內(nèi)存，供程序訪問時(shí)參考本段在運(yùn)行過程中，是否做過動(dòng)態(tài)增長本段在外存中的起始地址1/29/2024遼東學(xué)院信息技術(shù)學(xué)院1292.缺段中斷機(jī)構(gòu)

1303.地址變換機(jī)構(gòu)1/29/2024遼東學(xué)院信息技術(shù)學(xué)院1314.9.2分段的共享與保護(hù)1.共享段表1/29/2024遼東學(xué)院信息技術(shù)學(xué)院1322.共享段的分配與回收

1.分配：第一次訪問：分配內(nèi)存

（1）增加共享段表；（2）修改進(jìn)程段表。第二次訪問：

（1）修改共享段表；（2）修改進(jìn)程段表。2.回收：（1）count=0（2）count<>0133越界檢查段表寄存器：段表始址、段表長度段號(hào)<=段表長度、段內(nèi)地址<=段長存取控制檢查存取控制字段（用戶級(jí)別）只讀、只執(zhí)行、讀/寫環(huán)保護(hù)機(jī)構(gòu)可以訪問駐留在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù)；可以調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中的服務(wù)。3.分段保護(hù)重定位是指

；重定位的方式有兩種：134從作業(yè)邏輯地址到內(nèi)存物理地址的轉(zhuǎn)換過程。靜態(tài)重定位和動(dòng)態(tài)重定位。動(dòng)態(tài)重定位的特點(diǎn)是：由硬件實(shí)現(xiàn)，在運(yùn)行過程中進(jìn)行地址變換。若計(jì)算機(jī)CPU給出的有效地址長度為32位,內(nèi)存為32M，則該機(jī)的存儲(chǔ)空間為

M，作業(yè)的地址空間為

；32M，232B。如果一個(gè)程序?yàn)槎鄠€(gè)進(jìn)程所共享，那么該程序的代碼在執(zhí)行的過程中不能被修改即程序應(yīng)該是：可重入碼（純代碼）。本章基礎(chǔ)要點(diǎn)1/29/2