第4章存儲器管理

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

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

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

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

~~

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

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

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

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

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

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

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

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

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

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

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

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

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

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

)

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

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

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

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

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

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

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

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

解決方法：將內(nèi)存中的所有作業(yè)進行移動，使它們?nèi)苦徑?，這樣可把原來分散的小分區(qū)拼接成大分區(qū)，這種方法稱為“拼接”或“緊湊”。缺點：用戶程序在內(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阜陽師范學(xué)院計算機與信息學(xué)院302.動態(tài)重定位的實現(xiàn)

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

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

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

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

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

頁面邏輯空間分頁：將一個進程的邏輯地址空間分成若干個大小相等的片稱為頁面或頁，并為各頁加以編號，從0開始。

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

內(nèi)存分配原則

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

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

2023/2/4阜陽師范學(xué)院計算機與信息學(xué)院42補充題

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

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

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

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

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

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

(λ+t)ⅹα+（

λ+t+

t）（1-α）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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