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

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

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

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

~~

~~010002500500010000110001250015000作業地址空間內存空間

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

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

把內存分為一些大小相等或不等的分區，每個應用進程占用一個分區。操作系統占用其中一個分區。特點：適用于多道程序系統和分時系統;

支持多個程序并發執行問題：可能存在內碎片1.基本原理及技術2023/2/4阜陽師范學院計算機與信息學院132.劃分分區的方法

把內存劃分為若干個固定大小的連續分區

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

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

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

動態分區分配是根據進程的實際需要，動態地為之分配內存空間。在實現過程中涉及三個問題：（1）分區分配中的數據結構（2）分區分配算法（3）分區分配操作4.3.3動態分區分配2023/2/4阜陽師范學院計算機與信息學院16

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

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

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

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

)

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

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

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

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

的空閑分區鏈表中在回收空閑分區時，只當其伙伴為空閑分區時才歸并為大空閑分區。優點：算法簡單、速度快缺點：由于只歸并伙伴，而容易產生碎片（6）

伙伴系統2023/2/4阜陽師范學院計算機與信息學院28（7）

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

在連續分配方式中，必須把一個系統程序或用戶程序裝入到一個連續的內存空間中。如果在系統中有若干個小的分區，其總容量大于要裝入的程序，但由于它們不相鄰接，使該程序不能裝入內存

解決方法：將內存中的所有作業進行移動，使它們全部鄰接，這樣可把原來分散的小分區拼接成大分區，這種方法稱為“拼接”或“緊湊”。缺點：用戶程序在內存中的地址發生變化，必須重定位。20KB

0

os

作業1

作業3

作業4

52KB116KB166KB256KB1主存20KB

os

作業1

作業3

作業4

52KB66KB130KB230KB256KB1主存180KB

02023/2/4阜陽師范學院計算機與信息學院302.動態重定位的實現

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

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

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

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

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

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

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

內存分配原則

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

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

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

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

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

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

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

EAT=查找快表時間+查找頁表時間+更新快表時間+形成物理地址并訪問內存數據時間。

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

(λ+t)ⅹα+（

λ+t+

t）（1-α）

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

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

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

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

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

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

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

4.6.2分段系統的基本原理1.分段

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

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

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

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

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

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

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