第4章存儲(chǔ)器管理

2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院1第四章存儲(chǔ)器管理4.1存儲(chǔ)器的層次結(jié)構(gòu)4.2程序的裝入和鏈接4.3連續(xù)分配存儲(chǔ)管理方式4.4對(duì)換4.5分頁(yè)存儲(chǔ)管理方式4.6分段存儲(chǔ)管理方式核心考點(diǎn)：1.程序執(zhí)行的完整過程，靜態(tài)裝入與動(dòng)態(tài)裝入、物理地址與邏輯地址2.連續(xù)和離散分配方式、內(nèi)部和外部碎片、段式與頁(yè)式分配的區(qū)別3.分頁(yè)管理方式中的邏輯地址結(jié)構(gòu)、頁(yè)表、訪存過程以及防存有效時(shí)間、快表與多級(jí)頁(yè)表2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院24.2

程序的裝入和鏈接編譯鏈接裝入2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院34.2

程序的裝入和鏈接4.2.1程序的裝入

將一個(gè)裝入模塊裝入內(nèi)存時(shí)，有三種方式：絕對(duì)裝入方式可重定位裝入方式與靜態(tài)重定位動(dòng)態(tài)運(yùn)行時(shí)裝入方式與動(dòng)態(tài)重定位2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院44.2.1程序的裝入1.絕對(duì)裝入方式裝入模塊裝入內(nèi)存后，程序中的邏輯地址與實(shí)際內(nèi)存地址完全相同，不須對(duì)程序和數(shù)據(jù)的地址進(jìn)行修改。優(yōu)點(diǎn)：裝入過程簡(jiǎn)單。缺點(diǎn)：過于依賴于硬件結(jié)構(gòu)，不適于多道程序系統(tǒng)。2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院5在裝入時(shí)（程序執(zhí)行之前）由重定位裝配程序一次性實(shí)現(xiàn)地址轉(zhuǎn)換，以后不再改變。優(yōu)點(diǎn)：不需硬件支持，可以裝入有限多道程序。缺點(diǎn)：一個(gè)程序通常需要占用連續(xù)的內(nèi)存空間，程序裝入內(nèi)存后不能移動(dòng)。2.可重定位裝入方式(靜態(tài)重定位)4.2.1程序的裝入2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院64.2.1程序的裝入365LOAD1,2500365LOAD1,12500

~~

~~010002500500010000110001250015000作業(yè)地址空間內(nèi)存空間

在裝入時(shí)對(duì)目標(biāo)程序中指令和數(shù)據(jù)的修改過程稱為重定位。地址變換在裝入時(shí)一次完成，以后不再改變，稱為靜態(tài)重定位。2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院73.動(dòng)態(tài)運(yùn)行時(shí)裝入方式（動(dòng)態(tài)重定位）

把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。應(yīng)設(shè)置一個(gè)重定位寄存器。優(yōu)點(diǎn)：OS可以將一個(gè)程序分散存放于不連續(xù)的內(nèi)存空間，可以移動(dòng)程序。缺點(diǎn)：需要硬件支持，OS實(shí)現(xiàn)較復(fù)雜。2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院80100200300.........LOADA，2003456邏輯地址空間110012001300物理地址空間200相對(duì)地址+1000重定位寄存器地址映射LOADA,20034562023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院94.2程序的裝入和鏈接4.2.2程序的鏈接靜態(tài)鏈接：在程序運(yùn)行前，將目標(biāo)模塊及所需的庫(kù)函數(shù)鏈接成一個(gè)完整的裝入模塊，以后不再拆開。裝入時(shí)動(dòng)態(tài)鏈接：指將用戶源程序編譯后所得的一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接的鏈接方式。運(yùn)行時(shí)動(dòng)態(tài)鏈接：指對(duì)某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要該目標(biāo)模塊時(shí)，才對(duì)它進(jìn)行鏈接。2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院104.3連續(xù)分配方式單一連續(xù)分配固定分區(qū)分配動(dòng)態(tài)分區(qū)分配可重定位分區(qū)分配2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院114.3連續(xù)分配方式4.3.1單一連續(xù)分配在內(nèi)存中僅駐留一道程序，整個(gè)用戶區(qū)為一用戶獨(dú)占。把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，用戶區(qū)是指除系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間。用戶程序操作系統(tǒng)0xFFF...0單一連續(xù)區(qū)存儲(chǔ)管理2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院124.3.2固定分區(qū)分配

把內(nèi)存分為一些大小相等或不等的分區(qū)，每個(gè)應(yīng)用進(jìn)程占用一個(gè)分區(qū)。操作系統(tǒng)占用其中一個(gè)分區(qū)。特點(diǎn)：適用于多道程序系統(tǒng)和分時(shí)系統(tǒng);

支持多個(gè)程序并發(fā)執(zhí)行問題：可能存在內(nèi)碎片1.基本原理及技術(shù)2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院132.劃分分區(qū)的方法

把內(nèi)存劃分為若干個(gè)固定大小的連續(xù)分區(qū)

分區(qū)大小相等：只適合于多個(gè)相同程序的并發(fā)執(zhí)行（處理多個(gè)類型相同的對(duì)象）；缺乏靈活性。分區(qū)大小不等：劃分成含多個(gè)小分區(qū)、適量的中等分區(qū)、少量的大分區(qū)。4.3.2固定分區(qū)分配2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院143.內(nèi)存分配

為便于內(nèi)存分配，通常將分區(qū)按大小進(jìn)行排隊(duì)，并為之建立一張分區(qū)使用表，其中各表項(xiàng)包括每個(gè)分區(qū)的起始地址、大小及狀態(tài)（是否已分配）。優(yōu)點(diǎn)：易于實(shí)現(xiàn)，開銷小。缺點(diǎn)：內(nèi)碎片造成浪費(fèi)，分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目。4.3.2固定分區(qū)分配已分配1281284未分配64643已分配32322已分配20121狀態(tài)起址(K)大小(K)分區(qū)號(hào)分區(qū)使用表作業(yè)C作業(yè)B作業(yè)A操作系統(tǒng)20K32K64K128K256K存儲(chǔ)空間分配情況采用的數(shù)據(jù)結(jié)構(gòu)：

分區(qū)使用表－－記錄分區(qū)的大小和使用情況2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院15

動(dòng)態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。在實(shí)現(xiàn)過程中涉及三個(gè)問題：（1）分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)（2）分區(qū)分配算法（3）分區(qū)分配操作4.3.3動(dòng)態(tài)分區(qū)分配2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院16

空閑分區(qū)表：記錄尚未分配出去的分區(qū)情況，包含分區(qū)序號(hào)、起始地址、大小

空閑分區(qū)鏈：實(shí)現(xiàn)對(duì)空閑分區(qū)的分配鏈接。在分區(qū)起始部分設(shè)置分配信息：分區(qū)大小和狀態(tài)并設(shè)置前向指針，同時(shí)在分區(qū)尾部設(shè)置后向指針1.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院17分配內(nèi)存設(shè)請(qǐng)求的分區(qū)大小為u.size，表中每個(gè)空閑分區(qū)的大小表示為m.size，若m.size-u.sizesize(規(guī)定的不再切割的分區(qū)大小)，將整個(gè)分區(qū)分配給請(qǐng)求者，否則從分區(qū)中按請(qǐng)求的大小劃出一塊u.size大小的內(nèi)存空間分配出去，余下部分留在空閑鏈中，將分配區(qū)首址返回給調(diào)用者。2.分區(qū)分配操作2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院18回收內(nèi)存當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)首址，在空閑分區(qū)鏈(表)中找到相應(yīng)插入點(diǎn)，此時(shí)可能有四種情況：2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院19(1)首次適應(yīng)算法FF(2)

循環(huán)首次適應(yīng)算法(3)最佳適應(yīng)算法(4)最差適應(yīng)算法4.3.4順序搜索算法2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院20(1)首次適應(yīng)算法FF（最先匹配法（first-fit））

首址遞增排列；查找第一個(gè)滿足要求的空閑分區(qū)(2)循環(huán)首次適應(yīng)算法（下次匹配法（next-fit），又稱鄰近適應(yīng)算法）由FF算法演變；為實(shí)現(xiàn)算法需要：設(shè)置一起始查尋指針、采用循環(huán)查找方式4.3.4順序搜索算法2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院21(3)最佳適應(yīng)算法（最佳匹配法(best-fit)）空閑區(qū)大小遞增排列；查找既能滿足要求、又是最小的空閑分區(qū)(4)最差適應(yīng)算法（最壞匹配法(worst-fit)

)

4.3.4順序搜索算法2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院22例題1：

某基于動(dòng)態(tài)分區(qū)存儲(chǔ)管理的計(jì)算機(jī)，其主存容量為55MB（為初始空間），采用最佳適應(yīng)（BestFit）算法，分配和釋放的順序?yàn)椋悍峙?5MB，分配30MB，釋放15MB，分配8MB，分配6MB，此時(shí)主存中最大空閑分區(qū)的大小9MB2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院23(5)快速適應(yīng)算法(6)伙伴系統(tǒng)(7)哈希算法4.3.5索引式搜索算法2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院24(5)快速適應(yīng)算法（分類搜索法（quickfit））空閑分區(qū)的分類根據(jù)進(jìn)程常用的空間大小進(jìn)行劃分每一類具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)一個(gè)空閑分區(qū)鏈表搜索空閑分區(qū)分兩步：①根據(jù)進(jìn)程長(zhǎng)度，從索引表中尋找到能容納它的最小空閑區(qū)鏈表②從鏈表中取下第一塊進(jìn)行分配即可不會(huì)對(duì)任何分區(qū)產(chǎn)生分割4.3.5索引式搜索算法2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院25（6）伙伴系統(tǒng)固定分區(qū)方式：限制了活動(dòng)進(jìn)程的數(shù)目，當(dāng)進(jìn)程大小與空閑分區(qū)大小不匹配時(shí)，內(nèi)存空間利用率很低。動(dòng)態(tài)分區(qū)方式：算法復(fù)雜，回收空閑分區(qū)時(shí)需要進(jìn)行分區(qū)合并等，系統(tǒng)開銷較大?；锇橄到y(tǒng)是一種動(dòng)態(tài)存儲(chǔ)管理方法，也是對(duì)以上兩種內(nèi)存方式的一種折衷方案。4.3.5索引式搜索算法2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院26伙伴系統(tǒng)規(guī)定：無論已分配區(qū)或空閑分區(qū)，其大小均為2的k次冪，k為整數(shù)（1≤k≤m）其中21表示分配的最小分區(qū)的大小，2m表示分配的最大分區(qū)的大小。何謂“伙伴”：在分配時(shí)經(jīng)常需要將一個(gè)大的空閑分區(qū)2i+1

分裂成兩個(gè)大小相等的存儲(chǔ)區(qū)2i，這兩個(gè)由同一大分區(qū)分裂出來的小分區(qū)就稱為“一對(duì)伙伴”或“互為伙伴”（6）

伙伴系統(tǒng)2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院27若分配時(shí)，將其中的一個(gè)用于分配，而把另一個(gè)加入2i

的空閑分區(qū)鏈表中在回收空閑分區(qū)時(shí)，只當(dāng)其伙伴為空閑分區(qū)時(shí)才歸并為大空閑分區(qū)。優(yōu)點(diǎn)：算法簡(jiǎn)單、速度快缺點(diǎn)：由于只歸并伙伴，而容易產(chǎn)生碎片（6）

伙伴系統(tǒng)2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院28（7）

哈希算法為了選擇合適的空閑鏈表建立哈希函數(shù)，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，該表的每個(gè)表項(xiàng)記錄了一個(gè)對(duì)應(yīng)的空閑分區(qū)鏈表表頭指針。當(dāng)進(jìn)行分配時(shí)，根據(jù)所需空閑分區(qū)大小，通過哈希函數(shù)計(jì)算，得到哈希表中的位置，從而得到相應(yīng)的空閑鏈表，實(shí)現(xiàn)最佳分配策略2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院294.3.6動(dòng)態(tài)重定位分區(qū)分配1.動(dòng)態(tài)重定位的引入

在連續(xù)分配方式中，必須把一個(gè)系統(tǒng)程序或用戶程序裝入到一個(gè)連續(xù)的內(nèi)存空間中。如果在系統(tǒng)中有若干個(gè)小的分區(qū)，其總?cè)萘看笥谝b入的程序，但由于它們不相鄰接，使該程序不能裝入內(nèi)存

解決方法：將內(nèi)存中的所有作業(yè)進(jìn)行移動(dòng)，使它們?nèi)苦徑?，這樣可把原來分散的小分區(qū)拼接成大分區(qū)，這種方法稱為“拼接”或“緊湊”。缺點(diǎn)：用戶程序在內(nèi)存中的地址發(fā)生變化，必須重定位。20KB

0

os

作業(yè)1

作業(yè)3

作業(yè)4

52KB116KB166KB256KB1主存20KB

os

作業(yè)1

作業(yè)3

作業(yè)4

52KB66KB130KB230KB256KB1主存180KB

02023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院302.動(dòng)態(tài)重定位的實(shí)現(xiàn)

地址變換過程是在程序執(zhí)行過程期間，隨著對(duì)每條指令的訪問自動(dòng)進(jìn)行的，稱為動(dòng)態(tài)重定位。4.3.4動(dòng)態(tài)重定位分區(qū)分配movr1,[500]123

movr1,[500]123010050059901000256k-1作業(yè)地址空間存儲(chǔ)空間重定位寄存器1100150016005001000相對(duì)地址+2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院313.動(dòng)態(tài)重定位分區(qū)分配算法

動(dòng)態(tài)重定位分區(qū)分配算法與動(dòng)態(tài)分區(qū)分配算法基本相同，差別在于增加了緊湊的功能。4.3.6動(dòng)態(tài)重定位分區(qū)分配2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院32對(duì)換的引入多道程序環(huán)境下存在的問題：阻塞進(jìn)程占據(jù)大量?jī)?nèi)存空間許多作業(yè)在外存而不能進(jìn)入內(nèi)存運(yùn)行對(duì)換是提高內(nèi)存利用率的有效措施4.4對(duì)換(Swapping)2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院334.4.1對(duì)換的引入

分類：整體對(duì)換(或進(jìn)程對(duì)換)：以整個(gè)進(jìn)程為單位頁(yè)面對(duì)換或分段對(duì)換：以頁(yè)或段為單位實(shí)現(xiàn)進(jìn)程對(duì)換，系統(tǒng)必須具備的功能：對(duì)換空間的管理進(jìn)程的換出進(jìn)程的換入2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院344.4.2對(duì)換空間的管理存儲(chǔ)內(nèi)容駐留時(shí)間主要目標(biāo)分配方式文件區(qū)文件較長(zhǎng)久提高文件存儲(chǔ)空間的利用率離散對(duì)換區(qū)從內(nèi)存換出的進(jìn)程短暫提高進(jìn)程換入和換出的速度連續(xù)

在系統(tǒng)中設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)以記錄外存的使用情況；對(duì)換空間的分配與回收，與動(dòng)態(tài)分區(qū)方式時(shí)的內(nèi)存分配與回收雷同。2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院35進(jìn)程的換出系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，然后啟動(dòng)盤塊，將該進(jìn)程的程序和數(shù)據(jù)傳送到磁盤的對(duì)換區(qū)上。進(jìn)程的換入系統(tǒng)應(yīng)定時(shí)查看所有進(jìn)程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進(jìn)程，將換出最久的進(jìn)程作為換入進(jìn)程，將之換入，直至已無可換入的進(jìn)程或無可換出的進(jìn)程為止。4.4.3進(jìn)程的換出與換入2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院36第四章存儲(chǔ)器管理4.5基本分頁(yè)存儲(chǔ)管理方式4.6基本分段存儲(chǔ)管理方式2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院374.5.1分頁(yè)存儲(chǔ)管理的基本方法

頁(yè)面邏輯空間分頁(yè)：將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片稱為頁(yè)面或頁(yè)，并為各頁(yè)加以編號(hào)，從0開始。

物理塊內(nèi)存空間分塊：把內(nèi)存空間分成與頁(yè)面相同大小的若干個(gè)存儲(chǔ)塊，稱為（物理）塊或頁(yè)框。也從0開始編號(hào)

內(nèi)存分配原則

內(nèi)存的分配以塊為單位，并允許將一個(gè)進(jìn)程的若干頁(yè)分別裝入到多個(gè)不相鄰接的物理塊中。頁(yè)表系統(tǒng)為每個(gè)進(jìn)程建立了一張頁(yè)面映射表——頁(yè)表；其作用就是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射?！?9483623120頁(yè)號(hào)塊號(hào)頁(yè)表29105內(nèi)存0346781頁(yè)面大小頁(yè)面（和塊）的大小是由硬件確定的，應(yīng)是2的冪，通常是1KB8KBn頁(yè)1頁(yè)…5頁(yè)4頁(yè)3頁(yè)2頁(yè)0頁(yè)用戶進(jìn)程2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院382.地址結(jié)構(gòu)位移量/頁(yè)內(nèi)地址d頁(yè)號(hào)P3112110公式A－邏輯地址頁(yè)號(hào)：P=INT[A/L]L－頁(yè)面大小頁(yè)內(nèi)地址：d=[A]MODL4.5.1分頁(yè)存儲(chǔ)管理的基本方法地址長(zhǎng)度32位:011位為位移量(頁(yè)內(nèi)地址)，即每頁(yè)的大小為4KB1231位為頁(yè)號(hào)，地址空間最多允許有1M頁(yè)2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院393.頁(yè)表頁(yè)表是系統(tǒng)為每個(gè)進(jìn)程建立的一張頁(yè)面映像表，用來記錄相應(yīng)頁(yè)面在內(nèi)存中對(duì)應(yīng)的物理塊號(hào)。頁(yè)表的作用就是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射。頁(yè)表項(xiàng)包含頁(yè)號(hào)、塊號(hào)和存取控制字段(讀/寫、只讀、只執(zhí)行)

4.5.1分頁(yè)存儲(chǔ)管理的基本方法n頁(yè)…5頁(yè)4頁(yè)3頁(yè)2頁(yè)1頁(yè)0頁(yè)用戶程序……59483623120頁(yè)號(hào)塊號(hào)頁(yè)表內(nèi)存203456789101頁(yè)表的作用：2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院401.基本的地址變換機(jī)構(gòu)頁(yè)表可以由一組專門的寄存器來實(shí)現(xiàn)，一個(gè)頁(yè)表項(xiàng)用一個(gè)寄存器。但寄存器成本高，系統(tǒng)頁(yè)表可能很大，所以頁(yè)表大多常駐內(nèi)存。在系統(tǒng)中只設(shè)置一個(gè)頁(yè)表寄存器PTR，在其中存放頁(yè)表在內(nèi)存中的始址和頁(yè)表的長(zhǎng)度。4.5.2地址變換機(jī)構(gòu)2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院414.5基本分頁(yè)存儲(chǔ)管理方式頁(yè)表長(zhǎng)度頁(yè)表始址頁(yè)表寄存器①頁(yè)內(nèi)地址頁(yè)號(hào)(3)邏輯地址A②<越界中斷③頁(yè)表+4b32110塊號(hào)頁(yè)號(hào)④物理地址塊內(nèi)地址塊號(hào)⑤某分頁(yè)系統(tǒng)，主存容量為64K，頁(yè)面大小為1K，對(duì)一個(gè)4頁(yè)大的作業(yè)，其0、1、2、3頁(yè)分別被分配到主存的2、4、6、7塊中。將十進(jìn)制的邏輯地址1023、2500、4500轉(zhuǎn)換為物理地址★邏輯地址1023：1023/1K得頁(yè)號(hào)為0，頁(yè)內(nèi)地址為1023，查頁(yè)表找到對(duì)應(yīng)得物理塊為2，故物理地址為2*1K+1023=3071?！镞壿嫷刂?500：2500/1K得頁(yè)號(hào)為2，頁(yè)內(nèi)地址為452，查頁(yè)表找到對(duì)應(yīng)得物理塊為6，故物理地址為6*1K+452=6596?！镞壿嫷刂?500：4500/1K得頁(yè)號(hào)為4，頁(yè)內(nèi)地址為404，頁(yè)號(hào)大于頁(yè)表長(zhǎng)度，產(chǎn)生越界中斷

2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院42補(bǔ)充題

假定某頁(yè)式管理系統(tǒng)，主存為64KB，分成16塊，塊號(hào)為0，1，2，3，4，…15。設(shè)某作業(yè)有4頁(yè)，其頁(yè)號(hào)為0，1，2，3，被分別裝入主存的2、4、1、6塊。試問（計(jì)算結(jié)果按十進(jìn)制表示）：（1）該作業(yè)的總長(zhǎng)度是多少字節(jié)？（2）寫出該作業(yè)每一頁(yè)在主存中的起始地址；（3）對(duì)多個(gè)邏輯地址100、4146、8192、16384，試計(jì)算出相應(yīng)的內(nèi)存地址2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院43例題2設(shè)某計(jì)算機(jī)的邏輯地址空間為64KB，按字節(jié)編址。若某進(jìn)程最多需要6頁(yè)數(shù)據(jù)存儲(chǔ)空間，頁(yè)的大小為1KB，當(dāng)進(jìn)程要訪問邏輯地址為17CAH的數(shù)據(jù)，請(qǐng)問該邏輯地址對(duì)應(yīng)的頁(yè)號(hào)是（）52023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院442.具有快表的地址變換機(jī)構(gòu)

CPU在每存取一個(gè)數(shù)據(jù)時(shí)，需要兩次訪問內(nèi)存：第一次：訪問頁(yè)表，找到指定頁(yè)的物理塊號(hào)，將塊號(hào)與頁(yè)內(nèi)偏移量拼接形成物理地址。第二次：從第一次所得地址中獲得所需數(shù)據(jù)，或向此地址中寫入數(shù)據(jù)。解決方法：在地址變換機(jī)構(gòu)中，增設(shè)一個(gè)具有并行查尋能力的特殊高速緩沖寄存器，稱為“聯(lián)想存儲(chǔ)器”或“快表”。4.5.2地址變換機(jī)構(gòu)頁(yè)表長(zhǎng)度頁(yè)表始址頁(yè)表寄存器頁(yè)內(nèi)地址頁(yè)號(hào)(3)邏輯地址Adb物理地址<+越界中斷b1塊號(hào)頁(yè)號(hào)頁(yè)表具有快表的分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)：b

塊號(hào)頁(yè)號(hào)快表輸入寄存器4.5.3訪問內(nèi)存的有效時(shí)間內(nèi)存的有效訪問時(shí)間EAT（EffectiveAccessTime）從進(jìn)程發(fā)出指定邏輯地址的訪問請(qǐng)求，經(jīng)過地址變換，到在內(nèi)存中找到對(duì)應(yīng)的實(shí)際物理地址單元并取出數(shù)據(jù)，所需要花費(fèi)的總時(shí)間基本分頁(yè)存儲(chǔ)管理方式，訪問的頁(yè)在主存中，則EAT=查找頁(yè)表時(shí)間+形成物理地址并訪問內(nèi)存數(shù)據(jù)時(shí)間假設(shè)訪問一次內(nèi)存的時(shí)間為t，EAT=t+t=2t2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院454.5.3訪問內(nèi)存的有效時(shí)間具有快表的分頁(yè)存儲(chǔ)管理方式訪問的頁(yè)在主存中，且訪問頁(yè)的頁(yè)表項(xiàng)在快表中。則

EAT=查找快表時(shí)間+形成物理地址并訪問內(nèi)存數(shù)據(jù)時(shí)間訪問的頁(yè)在主存中，但訪問頁(yè)的頁(yè)表項(xiàng)不在快表中。則

EAT=查找快表時(shí)間+查找頁(yè)表時(shí)間+更新快表時(shí)間+形成物理地址并訪問內(nèi)存數(shù)據(jù)時(shí)間。

假設(shè)訪問一次內(nèi)存的時(shí)間為t，λ表示查找快表所需時(shí)間，α表示命中率：EAT=

(λ+t)ⅹα+（

λ+t+

t）（1-α）

2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院46所謂命中率：

是指使用快表并在其中成功查找到所需頁(yè)面的表項(xiàng)的比率。2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院47例題4某一個(gè)頁(yè)式存儲(chǔ)系統(tǒng)具有快表，多數(shù)活動(dòng)頁(yè)表項(xiàng)都可以存在其中。如果頁(yè)表存放在內(nèi)存中，內(nèi)存訪問時(shí)間是1us，檢索快表的時(shí)間為0.2us，若快表的命中率是85%，則有效存取時(shí)間是多少？解答：EAT=（0.2+1）ⅹ85%+（0.2+1+1）（1-85%）

=1.35us2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院48練習(xí)2某一頁(yè)式系統(tǒng)，其頁(yè)表存放在主存中：1）若對(duì)主存的一次存取需要1.5us，試問實(shí)現(xiàn)一次頁(yè)面訪問時(shí)存取時(shí)間是多少？2）若系統(tǒng)有快表且其平均命中率為85%，而頁(yè)表項(xiàng)在快表中查找時(shí)間可忽略不計(jì)，試問此時(shí)的存取時(shí)間為多少？2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院494.5.4兩級(jí)和多級(jí)頁(yè)表

現(xiàn)代計(jì)算機(jī)系統(tǒng)都支持非常大的邏輯地址空間(232264)，頁(yè)表就非常大，需占用較大的地址空間。解決方法：采用離散方式只將當(dāng)前所需頁(yè)表項(xiàng)調(diào)入內(nèi)存2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院501.兩級(jí)頁(yè)表

例如：32位邏輯地址空間，頁(yè)面大小為4KB(即12位)，若采用一級(jí)頁(yè)表機(jī)構(gòu)，應(yīng)有20位頁(yè)號(hào)，即頁(yè)表項(xiàng)應(yīng)有1M個(gè)；在采用兩級(jí)頁(yè)表機(jī)構(gòu)時(shí)，再對(duì)頁(yè)表進(jìn)行分頁(yè)，使每頁(yè)包含210(即1024)個(gè)頁(yè)表項(xiàng)，最多允許有210個(gè)頁(yè)表分頁(yè)。即頁(yè)內(nèi)地址外層頁(yè)內(nèi)地址外層頁(yè)號(hào)dp2p1312221121104.5.4兩級(jí)和多級(jí)頁(yè)表………012345671141151468內(nèi)存空間…641第0頁(yè)頁(yè)表012…1023115114第1頁(yè)頁(yè)表012…10231468第n頁(yè)頁(yè)表012…1023174210781011012n外部頁(yè)表兩級(jí)分頁(yè)結(jié)構(gòu)2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院51

為實(shí)現(xiàn)方便，在地址變換機(jī)構(gòu)中需設(shè)一外層頁(yè)表寄存器，用于存放外層頁(yè)表的始址，并利用邏輯地址中的外層頁(yè)號(hào)，作為外層頁(yè)表的索引，從中找到指定頁(yè)表分頁(yè)的始址，再利用p2作為指定頁(yè)表分頁(yè)的索引，找到指定的頁(yè)表項(xiàng)，其中即含有該頁(yè)在內(nèi)存的物理塊號(hào)，用該塊號(hào)和頁(yè)內(nèi)地址d即可構(gòu)成訪問的內(nèi)存物理地址。外部頁(yè)表寄存器外部頁(yè)表頁(yè)表db物理地址++dP2P1邏輯地址外部頁(yè)號(hào)外部頁(yè)內(nèi)地址頁(yè)內(nèi)地址具有兩級(jí)頁(yè)表的地址變換機(jī)構(gòu)：4.5.4兩級(jí)和多級(jí)頁(yè)表2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院522.多級(jí)頁(yè)表

兩級(jí)頁(yè)表對(duì)32位機(jī)器適用，64位呢？頁(yè)面大小為4KB即212B，還剩52位，按210位來劃分頁(yè)表，則剩余42位用于外層頁(yè)號(hào)，此時(shí)外層頁(yè)表可能有4096G個(gè)頁(yè)表項(xiàng)，要占用16384GB的連續(xù)存儲(chǔ)空間解決方法：采用多級(jí)頁(yè)表，將外層頁(yè)表再進(jìn)行分頁(yè)。4.5.4兩級(jí)和多級(jí)頁(yè)表2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院53例題5某計(jì)算機(jī)采用二級(jí)頁(yè)表的分頁(yè)存儲(chǔ)管理方式，按字節(jié)編址，頁(yè)大小為210B，頁(yè)表項(xiàng)大小為2B，邏輯地址結(jié)構(gòu)為邏輯地址空間大小為216頁(yè)，則表示整個(gè)邏輯地址空間的頁(yè)目錄表中包含表項(xiàng)的個(gè)數(shù)至少是（）頁(yè)目錄號(hào)頁(yè)號(hào)頁(yè)內(nèi)偏移量1284.5.5反置頁(yè)表（InvertedPageTable）為了減少頁(yè)表占用的內(nèi)存空間，引入了反置頁(yè)表。反置頁(yè)表是為每一個(gè)物理塊設(shè)置一個(gè)頁(yè)表項(xiàng)，并將它們按物理塊的編號(hào)排序，其中的內(nèi)容則是頁(yè)號(hào)和其所隸屬進(jìn)程的標(biāo)識(shí)符。地址變換：根據(jù)進(jìn)程標(biāo)識(shí)符和頁(yè)號(hào)，去檢索反置頁(yè)表；若檢索到匹配的頁(yè)表項(xiàng)，則頁(yè)表項(xiàng)的序號(hào)i便是該頁(yè)所在的物理塊號(hào)若未檢索到，則表明此頁(yè)尚未裝入內(nèi)存2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院542023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院554.6基本分段存儲(chǔ)管理方式4.6.1分段存儲(chǔ)管理方式的引入主要是滿足用戶和編程員的多方面要求：方便編程信息共享信息保護(hù)動(dòng)態(tài)增長(zhǎng)動(dòng)態(tài)鏈接2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院56

4.6.2分段系統(tǒng)的基本原理1.分段

作業(yè)地址空間被劃分為若干個(gè)段，每個(gè)段定義了一組邏輯信息，都有自己的名字。通常用段號(hào)代替段名，每段從0開始編址，并采用一段連續(xù)地址空間。程序加載時(shí)，分配其所需的所有段（內(nèi)存分區(qū)），這些段不必連續(xù)；物理內(nèi)存的管理采用動(dòng)態(tài)分區(qū)。

2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院57地址結(jié)構(gòu)：邏輯地址由段號(hào)(段名)和段內(nèi)地址所組成段內(nèi)地址段號(hào)3116150

該地址結(jié)構(gòu)允許一個(gè)作業(yè)最長(zhǎng)有64K個(gè)段，每段的最大長(zhǎng)度為64KB。4.6.2分段系統(tǒng)的基本原理2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院582.段表

為每個(gè)進(jìn)程建立一張段映射表，簡(jiǎn)稱“段表”。每個(gè)段在表中占有一個(gè)表項(xiàng)，其中記錄了該段在內(nèi)存中的起始地址(基址)和段的長(zhǎng)度。段表可以實(shí)現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。4.6.2分段系統(tǒng)的基本原理2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院594.6.2分段系統(tǒng)的基本原理作業(yè)空間(MAIN)=0030K(X)=1020K(D)=2015K(S)=3010K150K10K120K15K80K20K40K30K0123段號(hào)段長(zhǎng)基址段表(S)=310K(D)=215K(X)=120K(MAIN)=030K內(nèi)存空間040K80K120K150K利用段表實(shí)現(xiàn)地址映射:2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院603.地址變換機(jī)構(gòu)

在系統(tǒng)中設(shè)置段表寄存器，用于存放段表始址和段表長(zhǎng)度，以實(shí)現(xiàn)從進(jìn)程的邏輯地址到物理地址的變換。4.6.2分段系統(tǒng)的基本原理段表長(zhǎng)度段表始址控制寄存器物理地址<+越界中斷分段系統(tǒng)的地址變換機(jī)構(gòu)：1002段號(hào)S位移量W段表92002008K5004K6006K1K段長(zhǎng)基址段號(hào)0123+82928K82928692主存2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院614.分頁(yè)和分段的主要區(qū)別相似點(diǎn)：采用離散分配方式，通過地址映射機(jī)構(gòu)實(shí)現(xiàn)地址變換不同點(diǎn)：頁(yè)是信息的物理單位；段是信息的邏輯單位。頁(yè)的大小固定且由系統(tǒng)確定；段的長(zhǎng)度不固定，取決于用戶程序。分頁(yè)的作業(yè)地址空間是一維的；分段的作業(yè)地址空間是二維的。4.6.2分段系統(tǒng)的基本原理2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院624.6.3信息共享

分段系統(tǒng)的一個(gè)突出優(yōu)點(diǎn)是易于實(shí)現(xiàn)段的共享，允許若干個(gè)進(jìn)程共享一個(gè)或多個(gè)分段，且對(duì)段的保護(hù)十分簡(jiǎn)單易行。分頁(yè)系統(tǒng)中雖然也能實(shí)現(xiàn)程序和數(shù)據(jù)的共享，但遠(yuǎn)不如分段系統(tǒng)方便。data10…data1ed40…ed2ed1進(jìn)程1data10…data1ed40…ed2ed1進(jìn)程270…6160…2221頁(yè)表80…7160…2221頁(yè)表data10…data1data10…data1ed40…ed2ed1…021226061707180主存2023/2/4阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息學(xué)院63

在分段系統(tǒng)中，實(shí)現(xiàn)共享十分容易，只需在每個(gè)進(jìn)程的段表中為共享程序設(shè)置一個(gè)段表項(xiàng)。data1editor進(jìn)程1data2editor進(jìn)程22404080160基址段長(zhǎng)段表3804080160基址段長(zhǎng)段表data2…data1editor80240280380420主存4.6.3信