1、計算機操作系統第四章 存儲器管理9/19/202219/19/202229/19/20223第四章 存儲器管理 4.1 程序的裝入和鏈接 4.2 連續分配方式 4.3 基本分頁存儲管理方式 4.4 基本分段存儲管理方式 4.5 虛擬存儲器的基本概念 4.6 請求分頁存儲管理方式 4.7 頁面置換算法 4.8 請求分段存儲管理方式 存儲管理研究的課題 存儲分配問題。 重點是研究存儲共享和各種分 配算法。 地址再定位問題。 研究各種地址變換機構， 以 及靜態和動態再定位方法。 存儲保護問題。 研究保護各類程序、 數據區的 方法。 存儲擴充問題。 主要研究虛擬存儲器問題及其各 種調度算法。存儲器管理

2、主要研究三方面的問題： 取（fetch） 放（placement） 替換（replacement）請調、預調連續、非連續存儲層次結構9/19/20227外存(secondary storage)DOS核心命令處理程序內存(primary storage)高速緩存(cache)寄存器(register)速度容量小大低高本章主要研究內容主存管理的功能 地址映射(地址重定位) 主存分配和回收 存儲保護和共享 主存擴充(虛擬內存) 9/19/20228 二. 主存分配與回收 要完成內存的分配和回收工作，要求設計者選擇和確定以下幾種策略和結構：調入策略放置策略置換策略分配結構9/19/20229調入策略

3、用戶程序在何時調入內存的策略。目前有請調和預調兩種9/19/202210放置策略用戶程序調入內存時，確定將其放置在何處的策略。9/19/202211置換策略當需要將某個用戶程序調入內存而內存空間又不夠時，就要確定哪個或哪些程序可以從內存中移走。9/19/202212分配結構分配結構是用來登記內存使用情況的數據結構。如空閑區表、空閑區隊列等。9/19/202213引起內存分配和回收的原因進程的開始和結束。進程運行的過程中，它所占用的內存也可能發生變化。如棧的變化。進程映像在內存和外存之間傳遞。由于內存有限，系統中不可能容納所有進程，有些進程的映像可以存放在外存，當要運行這些進程時，必須把它們調入

4、內存。系統為了充分利用內存空間，有時可能對內存空間進行調整。9/19/202214三.存儲保護保證在內存中的多道程序只能在給定的存儲區域內活動并互不產生干擾。 包括：防止地址越界防止越權(對共享區有訪問權)9/19/202215存儲保護的硬件支持界地址寄存器（界限寄存器）界地址寄存器被廣泛使用的一種存儲保護技術機制比較簡單，易于實現9/19/202216實現方法在CPU中設置一對下限寄存器和上限寄存器存放用戶作業在主存中的下限和上限地址也可將一個寄存器作為基址寄存器，另一寄存器作為限長寄存器（指示存儲區長度）每當CPU要訪問主存，硬件自動將被訪問的主存地址與界限寄存器的內容進行比較，以判斷是否

5、越界如果未越界，則按此地址訪問主存，否則將產生程序中斷越界中斷（存儲保護中斷）9/19/202217圖示9/19/202218四.主存擴充(虛擬內存)為了使程序員在編程時不受內存的結構和容量的限制，系統為用戶構造一種存儲器，其結構可能與內存結構不同，容量可能遠遠超過內存的實際容量。這種面向編程的存儲器稱為虛擬存儲器。由虛存構成的存儲空間稱為虛存空間。或稱虛地址空間。9/19/202219實現虛擬內存的基本原理將程序正在使用的部分內容放在內存，而暫時不用的部分放在外存，在需要時由系統調入內存，并將不需要（或暫不需要）的部分調出內存。由于程序在執行時，在一段時間內一般僅使用它的程序的一部分（或一小

6、部分），所以程序僅有部分裝入內存完全能夠正確執行。要由操作系統結合相關硬件來完成上述工件，這樣計算機好象為用戶提供了一個容量遠大于內存的存儲器，這個存儲器稱為虛擬存儲器。 9/19/2022204.1 程序的裝入和鏈接將用戶源程序變為可在內存中執行的程序的步驟：編譯：由編譯程序將用戶源代碼編譯成若干個目標模塊鏈接：由鏈接程序將編譯后形成的一組目標模塊，以及它們所需要的庫函數鏈接在一起，形成一個完整的裝入模塊裝入：由裝入程序將裝入模塊裝入內存，構造PCB，形成進程(使用物理地址)9/19/2022214.1 程序的裝入和鏈接9/19/202222庫鏈接程序裝入模塊裝入程序編譯程序產生的目標模塊第

7、一步第二步第三步內存一.地址映射(地址重定位)物理地址（內存地址，絕對地址，實地址）：內存的每個存儲單元都有一個編號，這個編號稱為物理地址；內存地址的集合稱為內存空間（或物理地址空間）；物理地址可直接尋址9/19/202223一.地址映射(地址重定位)邏輯地址（程序地址，相對地址，虛地址）：用戶的程序經過匯編或編譯后形成目標代碼，目標代碼通常采用相對地址的形式；由邏輯地址組成的空間稱為邏輯地址空間（或程序地址空間）其首地址為0，其余指令中的地址都相對于首地址來編址。不能用邏輯地址在內存中讀取信息。9/19/2022249/19/202225 地址映射（地址重定位）：用戶程序裝入內存時對有關指令

8、的地址部分的修改定義為從程序地址到內存地址的地址映射，或稱為地址重定位創建進程時，由于程序的邏輯地址與分配到內存物理地址不一致, 而CPU執行指令時，是按物理地址進行的，所以要進行地址映射。為何要進行地址映射？一.地址映射(地址重定位)地址映射的方式靜態地址映射（靜態重定位）動態地址映射（動態重定位）9/19/2022261、靜態地址映射靜態地址映射（靜態重定位）：程序被裝入內存時由操作系統的鏈接裝入程序完成程序的邏輯地址到內存地址的轉換。9/19/202227映射方法假定程序裝入內存的首地址為BR，程序地址為VR，內存地址為MR，則地址映射按下式進行：MR=BR+VR 。例如，程序裝入內存的

9、首地址為1000，則裝配程序就按MR=1000+VR對程序中所有地址部分進行修改9/19/2022289/19/202229地址映射BR=1000Load A 1200 3456 。 。1200物理地址空間Load A data1data1 3456源程序Load A 200 34560100200編譯邏輯地址空間邏輯地址、物理地址和地址映射名空間地址空間存儲空間優缺點優點：不需要硬件的支持，可以裝入有限多道程序。缺點：一個程序通常需要占用連續的內存空間，程序裝入內存后不能移動。不易實現共享。9/19/2022302、動態地址映射動態地址映射（動態重定位）：是在程序執行的過程中，每次訪問內存之

10、前，將要訪問的程序地址轉換為內存地址；一般來說這種轉換是由專門的硬件機構來完成的。9/19/202231映射方法最簡單的硬件機構是重定位寄存器；在地址重定位機構中，有一個基地址寄存器BR和一個程序地址寄存器VR，一個內存地址寄存器MR。9/19/2022329/19/20223303456.LOAD A 200.0100200300.LOAD A 2003456110012001300200VR+1000BR1200MR地址映射的具體過程程序裝入內存后，它所占用的內存區的首地址由系統送入基地址寄存器BR中。在程序執行的過程中，若要訪問內存，將訪問的邏輯地址送入程序地址寄存器VR中。 地址轉換機

11、構把VR和BR中的內容相加，并將結果送入內存地址寄存器MR中，作為實際訪問的地址。9/19/202234動態地址映射的優缺點優點：OS可以將一個程序分散存放于不連續的內存空間可以移動程序有利于實現共享缺點：需要硬件支持OS實現較復雜9/19/202235虛擬存儲的基礎4.1.2 程序的鏈接靜態鏈接：在程序運行前，將目標模塊及所需的庫函數鏈接成一個完整的裝配模塊，以后不再拆開。裝入時動態鏈接：指將用戶源程序編譯后所得的一組目標模塊，在裝入內存時，采用邊裝入邊鏈接的鏈接方式。運行時動態鏈接：指對某些目標模塊的鏈接，是在程序執行中需要該目標模塊時，才對它進行鏈接。9/19/2022361、靜態鏈接(

12、static-linking)9/19/202237返回靜態鏈接是在生成可執行文件時進行的。在目標模塊中記錄符號地址(symbolic address)，而在可執行文件中改寫為指令直接使用的數字地址。4.1.2 程序的和鏈接9/19/202238靜態鏈接方式：事先進行鏈接，以后不再拆開模塊ACALL B;Return;0L-1模塊BCALL C;Return;0M-1模塊CReturn;0N-1模塊AJSR “L”Return;0L-1模塊BJSR “L+M”Return;LL+M-1模塊CReturn;L+ML+M+N-1目標模塊裝入模塊將目標模塊裝配成裝入模塊時需解決的兩個問題：(1)變換

13、外部調用符號(2)對相對地址進行修改對相對地址進行修改變換外部調用符號2. 裝入時動態鏈接 (Load-time Dynamic Linking) 邊裝入邊鏈接。優點：(1) 便于修改和更新(2) 便于實現對目標模塊的共享9/19/202239動態鏈接(dynamic-linking)在裝入或運行時進行鏈接。通常被鏈接的共享代碼稱為動態鏈接庫(DLL, Dynamic-Link Library)或共享庫(shared library)。3. 運行時動態鏈接(Run-time Dynamic Linking)邊執行邊鏈接！優點： 加快裝入過程、節省內存空間9/19/2022409/19/2022

14、414.2 連續分配方式 特點： 為每個用戶程序分配連續的內存空間 方法 單一連續分配 固定分區分配 動態分區分配 可重定位分區分配9/19/2022424.2.1 單一連續分配 最簡單的一種存儲分配管理方法只能用于單用戶、單任務的操作系統中把內存分為兩部分系統區：提供給OS使用，內存的低址部分用戶區：提供給用戶使用。 內存系統區（OS）用戶區0100k進程A進程B9/19/2022434.2.2 固定分區分配 1. 劃分分區的方法 分區大小相等， 即使所有的內存分區大小相等。 (2) 分區大小不等。 9/19/2022442. 內存分配 內存OS作業A作業B作業C作業D分區號大小(K)起址(

15、K)狀態11224已分配22436已分配33060未分配43590已分配540125未分配650165已分配7297215未分配0K24K90K36K60K165K125K215K進程F(70K)已分配進程G(70K)分區使用表內存分配程序9/19/2022454.2.3 動態分區分配 1. 分區分配中的數據結構 空閑分區表。 (2) 空閑分區鏈。 內存OS42K作業B20K作業C15K作業D30K0K35K111K77K91K151K136K226K分區號大小(K)始址(K)24235420916151368302263542912022630151369/19/2022462. 分區分配算

16、法 首次適應算法FF (2) 最佳適應算法(3) 最壞適應算法 首次適應法要求空閑區按首址遞增的次序組成空閑區表（鏈）。 內存OS42K作業B20K作業C15K作業D30K9/19/2022470K35K111K77K91K151K136K226K354291202263015136內存OS42K作業B20K作業C15K作業D30K9/19/2022480K35K111K77K91K151K136K226K429135201361522630首次適應算法FF1）作業1請求內存空間25K（分配）2）作業D完成（回收）思考：作業1完成（回收）作業117K6017120K12030K作業作業A作業2

17、0K9/19/202249（1）（2）30K作業A作業20K作業（3）作業30K作業作業A20K（4）作業30K作業A20K作業1003050020100305002010030500201003018020回收內存的四種情況20050首址200大小50K大小50K大小50K首址450大小50K80回收作業A45070100分析優點：優先利用低地址空間，從而保證高址空間有較大的空閑區缺點：低址部分被不斷劃分，留下許多難以利用的、很小的空閑分區每次都從低址開始，查找開銷大9/19/202250返回最佳適應法每次把能滿足作業要求，并且是最小的空閑分區分配給作業要求按空閑區大小從小到大的次序組成空閑

18、區表（鏈）。內存OS42K作業B20K作業C15K作業D30K9/19/2022510K35K111K77K91K151K136K226K136159120354230226內存OS42K作業B20K作業C15K作業D30K9/19/2022520K35K111K77K91K151K136K226K最佳適應算法1）作業1請求內存空間25K（分配）2）作業D完成（回收）思考：作業1完成（回收）作業15K90K136159120226303542251590分析優點：在系統中若存在一個與申請分區大小相等的空閑區，必定會被選中，而首次適應法則不一定。若系統中不存在與申請分區大小相等的空閑區，則選中的

19、空閑區是滿足要求的最小空閑區，而不致于毀掉較大的空閑區。缺點：空閑區的大小一般與申請分區大小不相等，因此將其一分為二，留下來的空閑區總是最小的，以致無法使用。隨著時間的推移，系統中的小空閑區會越來越多，從而造成存儲區的大量浪費。 9/19/202253返回最壞適應法每次把能滿足作業要求，并且是最大的空閑分區分配給作業要求空閑區按大小遞減的順序組織空閑區表（或鏈）。 內存OS42K作業B20K作業C15K作業D30K9/19/2022540K35K111K77K91K151K136K226K354222630136152091內存OS42K作業B20K作業C15K作業D30K9/19/20225

20、50K35K111K77K91K151K136K226K最壞適應算法1）作業1請求內存空間25K（分配）2）作業D完成（回收）思考：作業1完成（回收）作業117K120K3542226309120136156017136120分析最壞適應法看起來似乎有些荒唐，但在嚴密地考察后，還是有它的優點：當程序裝入內存中最大的空閑區后，剩下的空閑區還可能相當大，還能裝下較大的程序。另一方面分配時每次僅作一次查詢工作。9/19/202256三種策略比較上述三種放置策略各有利弊，到底哪種最好不能一概而論，而應針對具體作業序列來分析。對于某一作業序列來說，某種算法能將該作業序列中所有作業安置完畢，那么我們說該算

21、法對這一作業序列是合適的。對于某一算法而言，如它不能立即滿足某一要求，而其它算法卻可以滿足此要求，則這一算法對該作業序列是不合適的。 9/19/202257舉例例1：有作業序列：作業A要求18K；作業B要求25K，作業C要求30K。畫出空閑區鏈并分析一下哪個算法最合適此序列？9/19/202258經分析可知：最佳適應法對這個作業序列是合適的，而其它兩種對該作業序列是不合適的。OS30作業20作業5作業46首次最佳最壞20501001201601652100203010020210465160160510020210463020210462030160520100練習有作業序列：作業A要求21K

22、；作業B要求30K，作業C要求25K。9/19/202259思考 用動態分區分配方式管理主存時,假定主存中按地址順序依次有5個空閑區,空閑區的大小依次為32K,10K,5K,228K和100K,現有5個作業A,B,C,D,E.它們各需主存1K,10K,108K,28K和115K.若采用首次適應算法能把這5個作業按順序全部裝入主存嗎?你認為怎樣的次序裝入這5個作業可使主存的利用率最高?9/19/2022609/19/2022614.2.4 可重定位分區分配OS作業110作業230作業314作業426分區號起址大小35010512030716514923026 空閑分區表 205060120150

23、165179230作業A(40)80重定位寄存器作業120作業260作業3150作業4179306015512050110125176 9 216 409/19/2022624.2.5 對換(Swapping) 1. 對換的引入 所謂“對換”， 是指把內存中暫時不能運行的進程或者暫時不用的程序和數據，調出到外存上，以便騰出足夠的內存空間，再把已具備運行條件的進程或進程所需要的程序和數據，調入內存。對換是提高內存利用率的有效措施。 9/19/2022632. 對換空間的管理 為了能對對換區中的空閑盤塊進行管理，在系統中應配置相應的數據結構，以記錄外存的使用情況。其形式與內存在動態分區分配方式中所

24、用數據結構相似，即同樣可以用空閑分區表或空閑分區鏈。在空閑分區表中的每個表目中應包含兩項， 即對換區的首址及其大小，它們的單位是盤塊號和盤塊數。 9/19/2022643. 進程的換出與換入 (1) 進程的換出。 每當一進程由于創建子進程而需要更多的內存空間，但又無足夠的內存空間等情況發生時，系統應將某進程換出。 其過程是：系統首先選擇處于阻塞狀態且優先級最低的進程作為換出進程，然后啟動盤塊，將該進程的程序和數據傳送到磁盤的對換區上。若傳送過程未出現錯誤，便可回收該進程所占用的內存空間，并對該進程的進程控制塊做相應的修改。 9/19/202265 (2) 進程的換入。 系統應定時地查看所有進程

25、的狀態，從中找出“就緒”狀態但已換出的進程，將其中換出時間(換出到磁盤上)最久的進程作為換入進程，將之換入，直至已無可換入的進程或無可換出的進程為止。 9/19/2022664.3 基本分頁存儲管理方式 4.3.1 分頁存儲管理的基本方法 將程序的邏輯地址空間和物理內存劃分為固定大小的頁或頁面(page or page frame)，程序加載時，分配其所需的所有頁，這些頁不必連續。基本分頁存儲管理方式9/19/2022679/19/2022684.3.1 分頁存儲管理的基本方法優點：沒有外碎片，每個內碎片不超過頁大小。一個程序不必連續存放。便于改變程序占用空間的大小。即隨著程序運行而動態生成的

26、數據增多，地址空間可相應增長。缺點：程序全部裝入內存。9/19/2022694.3.1 分頁存儲管理的基本方法基本分頁存儲管理方式9/19/2022704.3.1 分頁存儲管理的基本方法所需表目：(1)頁表，每個進程一個 塊號 頁號:152216320123所需寄存器(1) 頁表寄存器：bl系統一個(2) 快表：系統一組： 頁號塊號.fp頁表首址 頁表長度9/19/202271進程頁表4.3.1 分頁存儲管理的基本方法基本分頁存儲管理方式9/19/2022721. 頁面頁面和物理塊 分頁存儲管理是將一個進程的邏輯地址空間分成若干個大小相等的片稱為頁面或頁，并為各頁加以編號，從0開始。 同時把內

27、存空間分成與頁面相同大小的若干個存儲塊，稱為塊或頁框。 在為進程分配內存時，以塊為單位將進程的若干個頁分別裝入到多個可以不相鄰的物理塊中。 進程的最后一頁經常裝不滿而形成“頁內碎片”。4.3.1 分頁存儲管理的基本方法基本分頁存儲管理方式9/19/202273頁面大小頁面大小應選地適中，應是2的冪，通常是512B8KB。9/19/2022742. 地址結構位移量W頁號P31 12 11 0地址長度32位:011位為位移量(頁內地址)，即每頁的大小為4KB12 31位為頁號，地址空間最多允許有1M頁基本分頁存儲管理方式 若給定一個邏輯地址空間中的地址為A，頁面大小為L，則: 頁號P=INTA/L

28、 頁內地址d=A MOD L 例如：系統頁面大小為1KB，設A=2170B，則: P=2，d=1229/19/202275基本分頁存儲管理方式9/19/202276n頁5頁4頁3頁2頁1頁0頁用戶程序59483623120頁號塊號頁表內存203456789101頁表的作用：基本分頁存儲管理方式4.3.1 地址變換機構1. 基本的地址變換機構 頁表可以由一組專門的寄存器來實現，一個頁表項用一個寄存器。但寄存器成本高，系統頁表可能很大，所以頁表大多常駐內存。 在系統中只設置一個頁表寄存器PTR，在其中存放頁表在內存中的始址和頁表的長度。9/19/202277基本分頁存儲管理方式9/19/20227

29、8頁表長度頁表始址頁表寄存器頁內地址頁號(3)邏輯地址L物理地址b1塊號頁號01234+越界中斷頁表分頁系統的地址變換機構：邏輯地址1023：1023/1K得頁號為0，頁內地址為1023，查頁表找到對應得物理塊為2，故物理地址為2*1K+1023=3071。邏輯地址2500：2500/1K得頁號為2，頁內地址為452，查頁表找到對應得物理塊為6，故物理地址為6*1K+452=6596。邏輯地址4500：4500/1K得頁號為4，頁內地址為404，頁號大于頁表長度，產生越界中斷 某分頁系統，主存容量為64K，頁面大小為1K，對一個4頁大的作業，其0、1、2、3頁分別被分配到主存的2、4、6、7塊

30、中。將十進制的邏輯地址1023、2500、4500轉換為物理地址 9/19/202279頁式地址變換舉例頁表始址頁表長度控制寄存器頁號頁面號有效地址02132821C4物理地址81C4基本分頁存儲管理方式例：設頁長為1K，程序地址字長為16位，用戶程序空間和頁表如圖，求用戶程序中Move指令中相對地址對應的絕對地址。9/19/202280用戶程序Move r1,250001001K2K25003K-1頁表頁號塊號021427內存01K2K3K4K5K6K7K8K9K10K-1課堂練習9/19/202281 假定某頁式管理系統，主存為64KB，分成16塊，塊號為0，1，2，15。設某作業有4頁，

31、其頁號為0，1，2，3，被分別裝入主存的2、4、1、6塊。試問：該作業的總長度是多少字節？寫出該作業每一頁在主存中的起始地址；對多個邏輯地址0，100、1，50、2，0、3，60，試計算出相應的內存地址。課堂練習9/19/202282例：設虛地址為(357101)8 每一塊為128字節，求出頁號及頁內地址（偏移量）12827(357101)8(011, 101, 111, 00 1, 000, 001)21 6 74101偏移為(101)8, 頁號為(1674)8塊號由頁表指定，偏移不變2. 具有快表的地址變換機構CPU在每存取一個數據時，需要兩次訪問內存：第一次：訪問頁表，找到指定頁的物理塊

32、號，將塊號與頁內偏移量拼接形成物理地址。第二次：從第一次所得地址中獲得所需數據，或向此地址中寫入數據。處理速度降低！解決方法：在地址變換機構中，增設一個具有并行查尋能力的特殊高速緩沖寄存器，稱為“聯想存儲器”或“快表”。9/19/202283基本分頁存儲管理方式9/19/202284頁表長度頁表始址頁表寄存器頁內地址頁號(3)邏輯地址Ldb物理地址+越界中斷b1塊號頁號頁表具有快表的分頁系統的地址變換機構：b塊號頁號快表輸入寄存器9/19/202285假定快表的命中率為98%,快表的訪問時間為20ns,內存的一次訪問時間為100ns,則有效訪問時間為:課堂練習EAT(Effective Acc

33、ess Time)=98%(20+100)+2%(20+200)=122ns基本分頁存儲管理方式4.3.2 兩級和多級頁表 現代計算機系統都支持非常大的邏輯地址空間(232264)，頁表就非常大，需占用較大的地址空間。例如：一個具有32位邏輯地址空間的分頁系統，規定頁面大小為4KB即212B，則每個進程頁表的頁表項可達1M個，若每個頁表項占用4個字節，則每個進程的頁表就要占據4MB的內存空間，而且要求連續存放。9/19/202286基本分頁存儲管理方式1. 兩級頁表 9/19/202287例如： 32位邏輯地址空間，頁面大小為4KB(即12位)，若采用一級頁表機構，應有20位頁號，即頁表項應有

34、1M個；在采用兩級頁表機構時，再對頁表進行分頁，使每頁包含210(即1024)個頁表項，最多允許有210個頁表分頁。即頁內地址外層頁內地址外層頁號dp2p1 31 22 21 12 11 0 基本分頁存儲管理方式9/19/202288012345671141151468內存空間641第0頁頁表0121023115114第1頁頁表01210231468第n頁頁表0121023174210781011012n外部頁表兩級分頁結構9/19/202289外部頁表寄存器外部頁表頁表db物理地址+dP2P1邏輯地址外部頁號外部頁內地址頁內地址具有兩級頁表的地址變換機構： 上述方法用離散分配空間解決了大頁表

35、無需大片存儲空間的問題，但并未減少頁表所占的內存空間。 解決方法是把當前需要的一批頁表項調入內存，以后再根據需要陸續調入。2. 多級頁表 兩級頁表對32位機器適用，64位呢？ 頁面大小為4KB即212B，還剩52位，按物理塊大小212位來劃分頁表，則剩余40位用于外層頁號，此時外層頁表可能有1024G個頁表項，要占用4096GB的連續存儲空間 解決方法：采用多級頁表，將外層頁表再進行分頁。9/19/202290基本分頁存儲管理方式9/19/202291多級頁表地址映射基本分頁存儲管理方式9/19/2022924.4 基本分段存儲管理方式 4.4.1 分段存儲管理方式的引入 引入分段存儲管理方式

36、， 主要是為了滿足用戶和程序員的下述一系列需要： 1) 方便編程Load r1,A,100 Store r2,B,500 2) 信息共享 3) 信息保護 4) 動態增長 5) 動態鏈接 基本分段存儲管理方式9/19/202293頁式管理是把內存視為一維線性空間；而段式管理是把內存視為二維空間，與進程邏輯相一致。將程序的地址空間劃分為若干個段(segment)，程序加載時，分配其所需的所有段（內存分區），這些段不必連續；物理內存的管理采用動態分區。需要硬件支持。4.4.2 分段系統的基本原理基本分段存儲管理方式 程序通過分段(segmentation)劃分為多個模塊，如代碼段、數據段、共享段。可

37、以分別編寫和編譯可以針對不同類型的段采取不同的保護可以按段為單位來進行共享，包括通過動態鏈接進行代碼共享 優點：沒有內碎片，外碎片可以通過內存緊縮來消除。便于改變進程占用空間的大小。 缺點：進程全部裝入內存。9/19/2022944.4.2 分段系統的基本原理基本分段存儲管理方式9/19/202295段號段表9/19/202296 所需表目(1) 段表：每進程一個段首址段長度100k40k80k60k段號 0: 1: 2: 3:20k200k320k300k(2) 空閑表：系統一個 array of (addr,size)基本分段存儲管理方式9/19/202297 所需寄存器(1) 段表寄存器

38、：bl段表首址 段表長度系統一個(2) 快表：系統一組： 段號 段首址 段長度.ls.b.基本分段存儲管理方式9/19/2022984.4.2 分段系統的基本原理 1. 分段 分段地址中的地址具有如下結構： 段號段內地址31 16 15 0基本分段存儲管理方式該地址結構允許一個作業最長有64K個段，每段的最大長度為64KB。2. 段表 段表可以存放在寄存器中，但更多的是存放在內存中。 段表可以實現從邏輯段到物理內存區的映射。9/19/202299基本分段存儲管理方式9/19/2022100 利用段表實現地址映射 M (0)30KX(1)20KD(2)15KF(3)10K用戶作業作業空間內存空間

39、M (0)30KX(1)20KD(2)15KF(3)10K040K80K120K150K30K40K20K80K15K120K10K150K段表 段長 基址01239/19/2022101分段系統的地址變換過程 3. 地址變換機構 段號S位移量W210K控制寄存器段表始址200K段表長度4越界+30K40K20K80K15K120K10K150K段長 基址+內存040K80K120K150K越界9/19/2022102例: 段表如下：回答下列問題：1計算該作業訪問 0，432，1，10，2，500，3，400 時的絕對地址2總結段式存儲管理的地址轉換過程。段號段長主存起始地址012346601

40、401005809602219330090123719599/19/2022103 段表如下：計算該作業訪問 0，216，1，120，2，210，3，456 時的絕對地址段號段長主存起始地址01234660140100580960221933009012371959課堂練習9/19/2022104 注意：當段表存放在內存中時，每訪問一個數據，都需訪問兩次內存，降低了計算機的速率。 解決方法：設置聯想寄存器，用于保存最近常用的段表項。基本分段存儲管理方式4. 分頁和分段的主要區別相似點：采用離散分配方式，通過地址映射機構實現地址變換不同點：頁是信息的物理單位，分頁是為了滿足系統的需要；段是信息的

41、邏輯單位，含有一組意義相對完整的信息，分段是為了滿足用戶的需要。頁的大小固定且由系統確定，由系統把邏輯地址分為頁號和頁內地址，由機器硬件實現；段的長度不固定，取決于用戶程序，編譯程序對源程序編譯時根據信息的性質劃分。分頁的作業地址空間是一維的；分段的作業地址空間是二維的。9/19/2022105基本分段存儲管理方式9/19/20221064.4.3 信息共享 分頁系統中共享editor的示意圖（頁面大小為1K）兩個進程共享文本編輯程序Editor，程序大小4K，另每個進程自身的數據2K進程1ed1ed2ed3ed4data1data2進程2ed1ed2ed3ed4data1data2頁表202

42、122234041頁表202122235051主存0Ed120Ed221Ed322ed423data140data241data150data251遼東學院信息技術學院9/19/2022107分段系統中共享editor的示意圖進程1editordata1進程2editordata2段表段長基址4K20K2K40K段表段長基址4K20K2K50K主存020editor40data150data2分段系統的一個突出優點是易于實現段的共享，允許若干個進程共享一個或多個分段，且對段的保護十分簡單易行。遼東學院信息技術學院9/19/2022108段的共享段長 段首址 . l b . .段號 si .P1

43、段表：段長 段首址 . l b . .段號 sj .P2段表：共享段.b:l內存空間基本分段存儲管理方式遼東學院信息技術學院9/19/2022109段名 共享記數 段長 段首址 其它 . vi 3 35k 125k ? .共享段表：進程段表(n)共享段表(1)共享段(1)基本分段存儲管理方式9/19/2022110 段的保護 (1) 段表的改進：段長 段首址 . . . l b 1 0 1段號 s .訪問權限R W E . . . 段號 段長 段首址 . . . s l b 1 0 1訪問權限R W E(2) 快表的改進： . . .基本分段存儲管理方式9/19/20221114.4.4 段頁

44、式存儲管理 (segmentation with paging)段式優于頁式便于共享和保護頁式優于段式消除“外碎片”問題段頁式：結合二者優點每個進程包含若干段每個段包含若干頁基本分段存儲管理方式9/19/20221121. 基本原理 圖 4-20 作業地址空間和地址結構 頁基本分段存儲管理方式9/19/2022113 基本原理 內存空間劃分：(同頁式) 靜態等長，2i, 稱為一頁。 物理地址=(塊號,塊內地址)=(f,w) 進程空間劃分： 一個進程若干個段 一個段若干個頁 邏輯地址=(段號, 邏輯頁號, 頁內地址)=(s,p,w)基本分段存儲管理方式9/19/2022114利用段表和頁表實現地

45、址映射主程序段0123子程序段01數據段012段號狀態頁表大小頁表始址041001220023400段表頁號狀態存儲塊#020122223324頁表頁號狀態存儲塊#040142頁表頁號狀態存儲塊#050151252頁表主存020212223244041425051529/19/2022115段表長度段表始址段表寄存器塊內地址塊號b物理地址+段超長2.段頁式系統的地址變換機構：頁內地址頁號P段號Sf1塊號頁號頁表0123+段表0123頁表長度頁表始址9/19/20221164.5 虛擬存儲器的基本概念 4.5.1 引入1.常規存儲管理的特征：一次性（指全部裝入）、駐留性（指駐留在內存不換出）2、

46、局部性原理時間局部性：如循環執行空間局部性：如順序執行。3、虛擬存貯器具有請求調入功能和置換功能，能從邏輯上對內存容量進行擴充的一種存儲系統。實質：以時間換空間，但時間犧牲不大。虛擬大小由_決定。9/19/2022117引入虛擬存儲技術的好處大程序：可在較小的可用內存中執行較大的用戶程序；大的用戶空間：提供給用戶可用的虛擬內存空間通常大于物理內存(real memory)并發：可在內存中容納更多程序并發執行；易于開發：與覆蓋技術比較，不必影響編程時的程序結構9/19/20221184.5.2 虛擬存儲器的實現方法 需要動態重定位一、請求分頁系統以頁為單位轉換需硬件：（1）請求分頁的頁表機制（2

47、）缺頁中斷（3）地址變換機構需實現請求分頁機制的軟件（置換軟件等）二、請求分段系統以段為單位轉換:（1）請求分段的段表結構（2）缺段中斷（3）地址變換機構需實現請求分段機制的軟件（置換軟件等）9/19/20221194.5.3 虛擬存儲器的特征 多次性：一個作業被分成多次調入內存運行對換性：允許在作業的運行過程中進行換進、換出。虛擬性：能夠從邏輯上擴充內存容量，使用戶所看到的內存容量遠大于實際內存容量。遼東學院信息技術學院9/19/20221204.6 請求分頁存儲管理方式 4.6.1 請求分頁中的硬件支持 1. 頁表機制 頁號 物理塊號 狀態位P 訪問字段A 修改位M外存地址 指示該頁是否已

48、調入內存記錄本頁在一段時間內被訪問的次數，或記錄本頁最近已有多長時間未被訪問，供選擇換出頁面時參考該頁在調入內存后是否被修改過，供置換頁面時參考指出該頁在外存上的地址，供調入該頁時參考9/19/20221212. 缺頁中斷機構 TO B指令copy A A: B:頁面6543219/19/20221223. 地址變換機構 9/19/20221234.6.2 內存分配策略和分配算法 1. 最小物理塊數的確定 進程應獲得的最少物理塊數與計算機的硬件結構有關，取決于指令的格式、功能和尋址方式如： Mov A, B允許間接尋址：則至少要求3個物理塊。9/19/20221242. 物理塊的分配策略 內存

49、分配策略：固定和可變分配策略置換策略：全局置換和局部置換 1) 固定分配局部置換(Fixed Allocation, Local Replacement)缺點：難以確定固定分配的頁數(少：置換率高/多：浪費) 2) 可變分配全局置換(Variable Allocation, Global Replacement) 3) 可變分配局部置換(Variable Allocation, Local Replacement）根據進程的缺頁率進行頁面數調整，進程之間相互不會影響9/19/20221253. 物理塊分配算法 1) 平均分配算法 將系統中所有可供分配的物理塊，平均分配給各個進程。缺點：未考慮各

50、進程本身的大小。9/19/20221262) 按比例分配算法 這是根據進程的大小按比例分配物理塊的算法。如果系統中共有n個進程，每個進程的頁面數為Si，則系統中各進程頁面數的總和為： 又假定系統中可用的物理塊總數為m，則每個進程所能分到的物理塊數為bi，將有：b應該取整，它必須大于最小物理塊數。 9/19/20221273) 考慮優先權的分配算法 在實際應用中，為了照顧重要的、急迫的作業盡快完成，應為它分配較多的內存空間。方法：一部分按比例分配給各進程；另一部分則根據各進程的優先權，適當地增加其相應份額后，分配給各進程。9/19/20221284.6.3 調頁策略 1. 何時調入頁面 （1）

51、請調(demand paging) upon page fault, 發生缺頁中斷時調入（較費系統開銷） （2） 預調(prepaging) before page fault, 將要訪問時調入(根據程序順序行為， 不一定準）（根據空間局部性，目前：成功率50）預調必須輔以請調。9/19/20221292. 從何處調入頁面 外存：文件區、對換區系統擁有足夠的對換區空間：系統缺少足夠的對換區空間：UNIX方式：9/19/2022130缺頁中斷保留CPU環境缺頁中斷處理訪問內存數據3. 頁面調入過程小結1、基本思想在進程開始運行之前，不是裝入全部頁面，而是裝入幾個或零個頁面，之后根據進程運行的需要

52、，動態裝入其它頁面；當內存空間已滿，而又需要裝入新的頁面時，則根據某種算法淘汰某個頁面，以便裝入新的頁面9/19/20221319/19/2022132XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K虛地址空間物理地址空間 虛頁頁框2、頁表表項頁號、物理塊號、狀態位、外存地址、訪問位、修

53、改位狀態位：表示該頁是在內存還是在外存訪問位：根據訪問位來決定淘汰哪頁（由不同的算法決定）修改位：查看此頁是否在內存中被修改過9/19/2022133頁號物理塊號狀態位外存地址訪問位修改位9/19/2022134151413121110 9 8 7 6 5 4 3 2 10000000000000000111100001011000000000000011110010001110100110101 00010000000000100011000000000100110在/不在內存頁表虛地址8196物理地址245803、缺頁中斷（Page Fault）處理在地址映射過程中，在頁表中發現所要訪問的

54、頁不在內存，則產生缺頁中斷。操作系統接到此中斷信號后，就調出缺頁中斷處理程序，根據頁表中給出的外存地址，準備將該頁調入內存此時應將缺頁的進程掛起（調頁完成喚醒）9/19/2022135如果內存中有空閑塊，則分配一個塊，將要調入的頁裝入該塊，并修改頁表中相應頁表項目的狀態位及相應的內存塊號若此時內存中沒有空閑塊，則要淘汰某頁（若被淘汰頁在內存期間被修改過，則要將其寫回外存）9/19/2022136思考缺頁中斷同一般中斷的區別？9/19/2022137缺頁中斷同一般中斷都是中斷，相同點是：保護現場 中斷處理 恢復現場不同點：一般中斷是一條指令完成后接受和處理中斷，缺頁中斷是一條指令執行過程中產生和

55、處理中斷一條指令執行時可能產生多個缺頁中斷。如指令可能訪問多個內存地址，這些地址在不同的頁中。9/19/20221389/19/20221394.7 頁面置換算法 4.7.1 最佳置換算法和先進先出置換算法 1. 最佳(Optimal)置換算法 最佳置換算法是由Belady于1966年提出的一種理論上的算法。 其所選擇的被淘汰頁面，將是以后永不使用的， 或許是在最長(未來)時間內不再被訪問的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。 用于：頁淘汰、段淘汰、快表淘汰。9/19/2022140 假定系統為某進程分配了三個物理塊， 并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4

56、，2，3，0，3，2，1，2，0，1，7，0，1 7F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺頁標志70F701F201F201203F203243F243243203F203203201F201201201701F701701缺頁9次，總訪問次數20次，缺頁率9/2045頁面置換6次，置換率6/20=30%最佳置換算法（OPT）例9/19/20221412. 先進先出(FIFO)頁面置換算法 該算法的實質是：總是選擇作業中在主存駐留時間最長（即最老）的一頁淘汰。即先進入主存的頁先退出主存。其理由是，最早調入主存的頁，其不再被使用的可能性比最近調

57、入主存的頁要大。9/19/20221427F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺頁標志70F701F201F201231F230F430F420F423F023F023023013F012F012012712F702F701F缺頁15次，總訪問次數20次，缺頁率15/2075頁面置換12次，置換率12/20=60%先進先出置換算法（FIFO）例9/19/2022143有一虛擬存儲系統，采用先進先出的頁面淘汰算法。在內存中為每個進程分配3塊。進程執行時使用頁號的順序為 4 3 2 1 4 3 5 4 3 2 1 5(1)該進程運行時總共出現幾次

58、缺頁（假設進程運行前所有頁面均不在內存中）。(2)若每個進程在內存有4塊，又將產生幾次缺頁。(3)如何解釋所出現的現象。例 9/19/20221444 3 2 1 4 3 5 4 3 2 1 5m=3413214214354352352143432共缺頁中斷9次9/19/2022145m=3時，缺頁中斷9次m=4時，缺頁中斷10次FIFO頁面淘汰算法會產生異常現象（Belady現象），即：當分配給進程的物理頁面數增加時，缺頁次數反而增加9/19/2022146 在虛存中，頁面在內存與外存之間頻繁調度，以至于調度頁面所需時間比進程實際運行的時間還多，此時系統效率急劇下降，甚至導致系統崩潰。這種現

59、象稱為顛簸或抖動原因：頁面淘汰算法不合理分配給進程的物理頁面數太少顛簸（抖動）9/19/20221474.7.2 最近最久未使用(LRU)置換算法 1. LRU(Least Recently Used)置換算法的描述 該算法的基本思想是:利用局部性原理，根據一個作業在執行過程中過去的頁訪問的蹤跡來推測未來的行為。它認為過去一段時間里不曾被訪問過的頁，在最近的將來可能也不會再被訪問。所以這種算法的實質是：當需要置換一頁時，選擇在最近一段時間內最久不用的頁予以淘汰。9/19/2022148m=44 3 2 1 4 3 5 4 3 2 1 544321532154215431543214324343

60、21532共缺頁中斷10次9/19/20221497F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺頁標志70F701F201F201203F203403F402F432F032F032032132F132102F102107F107107缺頁12次，總訪問次數20次，缺頁率12/2060頁面置換9次，置換率9/20=45%最近最久未使用置換算法（LRU）例9/19/20221502. LRU置換算法的硬件支持 1) 寄存器 為了記錄某進程在內存中各頁的使用情況，須為每個在內存中的頁面配置一個移位寄存器，可表示為 R=Rn-1Rn-2Rn-3 R2R1