1、第第7章章 存儲器管理存儲器管理7。1 有關概念有關概念n這里所說的存儲器指的是主存（內存、隨機存儲器（這里所說的存儲器指的是主存（內存、隨機存儲器（RAM：Random Access Memory）；）；n主存空間分為兩大部分：主存空間分為兩大部分：n系統區：用以存放操作系統及其工作區；系統區：用以存放操作系統及其工作區；n用戶區：由多個進程分配使用；用戶區：由多個進程分配使用；n系統區不存在管理問題，存儲管理的對象是用戶區；系統區不存在管理問題，存儲管理的對象是用戶區；n存儲器管理的目的是要使內存空間得到充分有效和安全有存儲器管理的目的是要使內存空間得到充分有效和安全有序的使用。序的使用。

2、系統區用戶區存儲管理的對象是主存的用戶區存儲器管理的功能存儲器管理的功能n空間分配：空間分配：在多個進程之間分配和回收存儲空間；n地址變換：地址變換：將邏輯地址變換為物理地址；n存儲保護：存儲保護：防止因用戶程序錯誤破壞系統或其他用戶，防止程序之間的相互干擾；n存儲擴充：存儲擴充：在邏輯上為用戶提供一個比實際內存更大的存儲空間。地址及地址變換地址及地址變換n地址（地址（Address），），是存儲空間中某個可訪問單元的編號，它又分邏輯地址和物理地址； 邏輯地址：邏輯地址：編程時所使用的地址，又稱相對地址、虛地址； 邏輯空間：邏輯空間：邏輯地址的集合，有時就叫地址空間； 物理地址：物理地址：內存

3、中的地址，又稱絕對地址、實地址； 物理空間：物理空間：物理地址的集合，也叫存儲空間，主存空間；n地址變換：地址變換：將邏輯地址轉換為物理地址，又稱地址映射、地址重定位。 地址變換分為兩類：n靜態地址變換；n動態地址變換；靜態地址變換靜態地址變換 mov ax,500 mov ax,500 54321 54321 mov ax,1000+500 mov ax,1000+500 54321 54321 0100500999 0 1000 1100 1500 19991M-1程序的地址空間主存空間重定位裝入程序在程序裝入時一次完在程序裝入時一次完成，以后不再改變。成，以后不再改變。靜態重定位時只須修

4、改指令內部的地址；修改后靜態重定位時只須修改指令內部的地址；修改后CPU以物理地址執行程序。以物理地址執行程序。動態地址變換動態地址變換 mov ax,500mov ax,500 54321 54321 mov ax,500mov ax,500 54321 54321 0100500999 0 1000 1100 1500 19991M-1作業的地址空間存儲空間5001000邏輯地址重定位寄存器在程序執行的過在程序執行的過程中動態地進行。程中動態地進行。CPU以邏輯地址執行程序，在執行中動態地將邏輯地址轉換成物理地址。以邏輯地址執行程序，在執行中動態地將邏輯地址轉換成物理地址。7.2 分區存儲

5、管理分區存儲管理n本章講述的存儲管理方法包括分區管理、分頁管理、分段管理和段頁式管理等。這里先說分區管理；n分區存儲管理是多道程序系統中采用的一種最簡單的存儲管理方法。它把內存的用戶空間劃分為若干大小不等的區域，每個進程（每道程序）占用一個區域；n分區存儲管理又分為：n固定分區管理；n動態分區管理；7。2。1 固定分區存儲管理固定分區存儲管理n方法：方法：固定分區存儲管理方法將內存空間劃分為若干個固定大小的分區，每個分區中可以裝入一道程序。分區的個數及每個分區的位置和大小在運行期間不能改變；n管理：管理：系統需要建立一張分區使用表，以記錄系統中的分區數目、分區大小、分區起始地址及狀態；n分配：

6、分配：當有用戶程序要裝入時，由內存分配程序檢索分區使用表，從中找出一個能滿足要求的空閑分區分配給該程序，然后修改分區說明表中相應表項的狀態；若找不到大小足夠的分區，則拒絕分配內存；n回收：回收：當某程序執行完畢時，釋放程序占用的分區，管理程序只需將對應分區的狀態置為未分配即可；n特點：特點：管理簡單但存儲空間利用率較低。固定分區管理舉例 操作系統 分區號 大小 起始地址 狀態 1 8KB 20KB 已分配 2 32KB 28KB 已分配 3 32KB 60KB 未分配 4 120KB 92KB 未分配 5 300KB 212KB 已分配 0 20KB 28KB 60KB 92KB 212KB5

7、12KB-1進程A（6K）進程B（24K）進程C（128K）1 2 3 4 57。2。2 動態分區存儲管理動態分區存儲管理n動態分區存儲管理又稱為可變分區存儲管理，這種管理方法是在系統的運行過程中動態地產生和回收分區。系統初啟時，整個用戶空間就是一個分區，然后根據運行的需要，在分配和回收的過程中逐漸產生和合并新的分區。因此，在這種方法下，系統內分區的個數及每個分區的大小都是動態變化的。系統空間用戶空間系統初啟時，整個用戶空間就是一個分區。動態分區管理中的數據結構動態分區管理中的數據結構n在動態分區管理中常用的數據結構有：n空閑分區表：空閑分區表：用一個空閑分區表來登記系統中的空閑分區，表項內容

8、包括分區的大小和起始地址；n空閑分區鏈：空閑分區鏈：在空閑分區內部拿出一點空間用以建立鏈表，將所有的空閑分區鏈接起來，構成空閑分區鏈，供空間分配和回收時查詢；n比較而言，空閑分區表查詢起來速度較快，但需要額外的空間開銷；空閑分區鏈查詢起來較慢，但不需要額外的空間開銷，其用以建立鏈表的空間也可以供分配?？臻e分區表示意圖空閑分區表示意圖分區號 大小 起始地址 1 8KB 24KB 2 12KB 128KB 3 8KB 248KB 4 5 操作系統 空閑 (8K) 已分 (96K) 空閑 (12K) 已分 (108K) 空閑 (8K) 0 24KB 32KB 128KB 140KB 248KB256

9、KB-1空閑分區鏈示意圖空閑分區鏈示意圖 操作系統 空閑 (8K) 已分 (96K) 空閑 (12K) 已分 (108K) 空閑 (8K) 0 24KB 32KB 128KB 140KB 248KB256KB-1 操作系統 空閑 (8K) 已分 (96K) 空閑 (12K) 已分 (108K) 空閑 (8K) 0 24KB 32KB 128KB 140KB 248KB256KB-1表頭指針分區分配算法分區分配算法n目前常用的分區分配算法有以下幾種：目前常用的分區分配算法有以下幾種：n首次適應算法（FF：First Fit）；n循環首次適應算法（RFF：Round First Fit）；n最佳適

10、應算法（BF：Best Fit）；n最壞適應算法（WF：Worst Fit）；首次適應算法首次適應算法n首次適應算法又稱最先適應算法，該算法要求空閑分區按首地址遞增的次序排列；n在進行內存分配時，從空閑分區表（或空閑分區鏈）頭開始順序查找，直到找到第一個能滿足其大小要求的空閑分區為止；n然后，再按照作業大小，從該分區中劃出一塊內存空間分配給請求者，余下的空間，要么作為新的空閑分區仍然留在空閑分區表（或空閑分區鏈）中，要么作為碎片丟掉；n首次適應法的特點首次適應法的特點：優先利用內存低地址端，以便高地址端逐漸形成大的空閑區；但低地址端有許多小空閑分區時會增加查找開銷。循環首次適應算法循環首次適應

11、算法n循環首次適應算法又稱下次適應算法，它是首次適應算法的變形；n該算法在為進程分配內存空間時，從上次停下的位置開始查找，直到找到第一個能滿足其大小要求的空閑分區為止；n然后，再按照作業大小，從該分區中劃出一塊內存空間分配給請求者，余下的空間要么作為新的空閑分區仍然留在空閑分區表（或空閑分區鏈）中，要么作為碎片丟掉；n循環首次適應法的特點：循環首次適應法的特點：使存儲空間的利用更加均衡，但會使系統缺乏大的空閑分區。最佳適應算法最佳適應算法n最佳適應算法要求空閑分區按容量大小遞增的次序排列；n在進行內存分配時，從空閑分區表（或空閑分區鏈）頭開始順序查找，直到找到第一個能滿足其大小要求的空閑分區為

12、止；n如果該空閑分區大于作業的大小，則從該分區中劃出一塊內存空間分配給請求者，將剩余空間要么作為新的空閑區仍然留在空閑分區表（或空閑分區鏈）中，要么作為碎片丟掉；n最佳適應算法的特點：最佳適應算法的特點：按最佳適應算法為作業分配內存，就能把既滿足要求又與作業大小最接近的空閑分區分配給作業，這樣就可以保留大的空閑區以備大作業使用，但分割后的剩余空閑區很小，往往會被作為碎片丟掉。最壞適應算法最壞適應算法n最壞適應算法要求空閑分區按容量大小遞減的次序排列；n在進行內存分配時，只檢查空閑分區表（或空閑分區鏈）中的第一個空閑分區，若第一個空閑分區小于作業要求的大小，則分配失??；n否則從該空閑分區中劃出與

13、作業大小相等的一塊內存空間分配給請求者，余下的空間要么作為新的空閑分區仍然留在空閑分區表（或空閑分區鏈）中，要么作為碎片丟掉；n最壞適應法的特點：最壞適應法的特點：剩下的空閑區比較大，但當大作業到來時，其存儲空間的申請往往得不到滿足。舉例舉例n下表給出了某系統的空閑分區表，系統采用可變式分區存儲管理策略。現有以下作業序列：96K、20K、200K。若用首次適應算法首次適應算法和最佳適應算法最佳適應算法來處理這些作業序列，試問哪一種算法可以滿足該作業序列的請求?分區號 大小起始地址132K100K210K150K35K200K4218K220K596K530K采用最佳適應算法分配采用最佳適應算法

14、分配1n申請96K，n選中4號分區，4號分區大小與申請空間大小一致，應從空閑分區表中刪去該表項 ，5號記錄順序上移；分區號 大小起始地址15K200K210K150K332K100K496K530K5218K220K分區號 大小起始地址15K200K210K150K332K100K4218K220K采用最佳適應算法分配采用最佳適應算法分配2n申請20K，n選中3號分區，分配后還剩下12K；分區號 大小起始地址15K200K210K150K332K100K4218K220K分區號 大小起始地址15K200K210K150K312K100K4218K220K采用最佳適應算法分配采用最佳適應算法分配

15、3n申請200K,n選中4號分區，分配后剩下18K；n可見，采用最佳適應法是可以滿足分配要求的。分區號 大小起始地址15K200K210K150K312K100K4218K220K分區號 大小起始地址15K200K210K150K312K100K418K220K采用首次適應算法分配采用首次適應算法分配1n申請96K，n選中4號分區，進行分配后還剩下122K；分區號 大小起始地址132K100K210K150K35K200K4218K220K596K530K分區號 大小起始地址132K100K210K150K35K200K4122K220K596K530K采用首次適應算法分配采用首次適應算法分配

16、2n申請20K，n選中1號分區，分配后剩下12K；分區號 大小起始地址132K100K210K150K35K200K4122K220K596K530K分區號 大小起始地址112K100K210K150K35K200K4122K220K596K530K采用首次適應算法分配采用首次適應算法分配3n申請200K，n現有的五個分區都無法滿足要求，該作業等待；n顯然采用首次適應算法顯然采用首次適應算法進行內存分配，無法滿進行內存分配，無法滿足該作業序列的需求。足該作業序列的需求。分區號 大小起始地址112K100K210K150K35K200K4122K220K596K530K空間分配程序空間分配程序n

17、以首次適應以首次適應算法及空閑算法及空閑鏈表為例，鏈表為例，申請分區大申請分區大小為小為x， e是是“碎片碎片”大大小的閥值。小的閥值。將剩余量作為“碎片”丟掉開始查表是鏈表尾？本次無法分配，返回YN空閑區容量x?N繼續檢查下一項容量xe?YYN將剩余量作為新的分區留在鏈表中將空間分配給請求者，修改鏈表分配舉例分配舉例n假設x=40k，e=2k，t為分得空間的始地址；操作系統用戶空間20K42K24Khead40k注意注意:本程序是將高地址部分本程序是將高地址部分的的40K分出去，為什么分出去，為什么要這樣做呢？要這樣做呢？2KP=head=16KP指向的分區為20K，不夠分；Q=P=16K；

18、P=P-link=64K；P指向的分區夠分，分出40K；P-size=P-size-40K=2K；2K=閥值，作為新的空閑分區留在鏈表內；t=P+P-size=64K+2K=66K，返回給申請者；16K64K128KnVoid cmalloc(node * head, int x)n node *p, *q, *t;n p=head;n while ( p-sizelink; n if ( p!=nil )n p -size= p-size-x;n if (p-size link= p- link;n else t=p+ p-size;n n else t=0; printf （“本次無法分配

19、！”n）；n return (t);n 分區回收程序分區回收程序n回收分區時，如果回收區鄰接空閑區，則應將它們合并，回收分區時，如果回收區鄰接空閑區，則應將它們合并，鄰接有四種情況，見鄰接有四種情況，見P129。找到回收區在鏈表中的位置回收區上、下都鄰接空閑區嗎？三區合并下鄰接嗎？兩區合并上鄰接嗎？兩區合并回收區插入鏈表ynynny返回內存保護內存保護n存儲保護的主要含義是防止程序間的相互干擾和破壞，方法是禁止越界訪問；n常用的存儲保護方法有：n上下界寄存器法；n基址限長寄存器法；n上下界寄存器法：n用上、下界寄存器分別存放作業存儲空間的結束地址和開始地址；n在作業運行過程中，將每一個訪問內存

20、的地址都同這兩個寄存器的內容進行比較，若超出了上下界寄存器的范圍則產生越界中斷；n基址、限長寄存器法：n用基址和限長寄存器分別存放作業存儲空間的起始地址及作業長度；n當作業執行時，將每一個訪問內存的相對地址和這個限長寄存器比較，若邏輯地址超過限長則產生越界中斷。7。2。3 碎片問題及拼接技術碎片問題及拼接技術n分區存儲管理中，必須把作業裝入到一片連續的內存空間中。這種分配方法能滿足多道程序設計的需要，但存在碎片問題； n碎片也可稱為零頭，是指內存中無法被利用的存儲空間；n碎片分內部碎片和外部碎片： 內部碎片是指分配給作業的存儲空間中未被利用的部分；外部碎片是指系統中無法利用的小存儲塊；n解決碎

21、片問題的方法之一，是通過移動把多個分散的小碎片拼接成一個大的空閑區，也可稱為緊縮或緊湊；n拼接的時空開銷較大。拼接示意圖拼接示意圖n拼接前 拼接后 操作系統 進程5 空閑（10KB） 進程4 空閑（30KB） 進程3 空閑（26KB） 0 40KB 90KB 100KB 170KB 200KB 230KB256KB-1 操作系統 進程5 進程4 進程3 空閑（66KB） 0 40KB 90KB 160KB 190KB 256KB-1拼接需要的技術支持拼接需要的技術支持n動態重定位：動態重定位：拼接后程序在內存的位置發生變化，因此需要動態重定位技術支持；n空閑區放在何處：空閑區放在何處：拼接后的

22、空閑區放在何處不能一概而論，應根據移動信息量的多少來決定；n拼接的時機：拼接的時機：n回收分區時拼接：只有一個空閑區，但拼接頻率過高增加系統開銷；n找不到足夠大的空閑區且系統空閑空間總量能滿足要求時：拼接頻率小于前者，空閑區管理稍復雜。也可以只拼接部分空閑區。7.3 伙伴系統伙伴系統n固定分區存儲管理限制了內存中的進程數，動態分區的拼接需要大量時間，而伙伴系統是一種較為實用的動態存儲管理辦法；n伙伴系統采用伙伴算法對空閑內存進行管理。系統初啟時，整個用戶區就是一個空閑塊，然后，在運行的過程中通過不斷對分大的空閑塊來獲得小的空閑塊，對分出來的空閑塊稱為“伙伴”（Buddy），每個空閑塊的大小為2

23、i；n當內存塊釋放時，應盡可能合并它的伙伴空閑塊；n伙伴系統的主要優點是分配和回收空間的時間開銷比最佳適應法和首次適應法要小，其缺點是可能浪費許多存儲空間?；锇橄到y的分配和回收伙伴系統的分配和回收n伙伴系統的存儲分配方法是：伙伴系統的存儲分配方法是： 當進程申請大小為n的空間時，設2i-1n2i，則為進程分配大小為2i的空間；如系統不存在大小為2i的空閑塊，則查找系統中是否存在大于2i的空閑塊，若找到則對其進行對半劃分，直到產生大小為2i的空閑塊為止。n伙伴系統的存儲回收方法是：伙伴系統的存儲回收方法是： 當進程釋放存儲空間時，應檢查釋放塊的伙伴是否空閑，若空閑則合并；這個較大的空閑塊也可能存

24、在空閑伙伴，此時也應合并；重復上述過程，直至沒有可以合并的伙伴為止?；锇榈刂酚嬎愎交锇榈刂酚嬎愎絥設某空閑塊的開始地址為d，長度為2K，其伙伴的開始地址為：nBuddy（k，d）=d+2k，若d % 2k+1=0nBuddy（k，d）=d-2k， 若d % 2k+1= 2kn如果參與分配的2m個單元從a開始，則長度為2K、開始地址為d的塊，其伙伴的開始地址為：nBuddy（k，d）=d+2k，若（d-a）% 2k+1=0nBuddy（k，d）=d-2k， 若（d-a）% 2k+1= 2k伙伴系統分配及回收的舉例伙伴系統分配及回收的舉例n設系統中初始內存空間大小為1MB，進程請求和釋放空間的

25、操作序列為：n進程A申請200KB；B申請120KB；C申請240KB； D申請100KB；n進程B釋放；E申請60KB；n進程A、C釋放；n進程D釋放；進程E釋放。E A釋放分配過程示意圖分配過程示意圖n 0 128K 256K 384K 512K 640K 768K 896K 1M初始狀態A申請200B申請120C申請240D申請100 B釋放 E申請60 C釋放 D釋放 E釋放512K256KAA512K128KBAB256KCAB256KCDA256KCD128KA256KCD64E256KCD64E256KD64256K512KE64256K512K128K128K伙伴系統的二叉樹表

26、示伙伴系統的二叉樹表示n可以用二叉樹表示內存分配情況。葉結點表示存儲器中的當前分區，如果兩個伙伴是葉子，則至少有一個被分配。n右圖表示A（200）、B（120）、C（240）、D（100）分配之后的情況。ABDC1M512K256K128K7.4 分頁存儲管理分頁存儲管理7。4。1 基本原理基本原理n分區管理中，要求將一道程序裝在內存的一片連續的空間，這有可能降低空間的利用率，或者加大緊湊和拼接的時間開銷。為了克服這種缺點，提出了分頁管理的思想和方法；n在分頁存儲管理中，將程序的邏輯地址空間和主存的物理空間按同樣的大小劃分成若干個頁面（塊），為了區分，邏輯空間的叫“頁”（page），物理空間的

27、叫“塊”（block）。然后，以塊（頁）為單位為進程分配空間。這樣，同一道程序就可以裝在若干個不連續的頁面內，從而提高內存空間的利用率。程序邏輯空間內存物理空間012301234567從圖示的分配方法可以看出，一道程序在內存是以頁面為單位存放的，同一道程序的頁面之間可以是不連續的，次序也是隨意的。7。4。2 數據結構數據結構n為了支持分頁存儲管理，虛要建立以下數據結構：為了支持分頁存儲管理，虛要建立以下數據結構： 1，頁表（PT：Page Table）； 2，存儲分塊表（MBT：Memory Blocking Table）； 3，進程請求表（PRT：Process Request Table）

28、； 下面逐一說明。下面逐一說明。頁表（頁表（PT）n頁表每個進程一張，記錄該進程每個頁面所分得的物頁表每個進程一張，記錄該進程每個頁面所分得的物理塊。理塊。內存空間程序的地址空間頁表 0頁1頁2頁n頁 0 2 1 4 2 7 頁號 塊號01234567頁面大小的選擇頁面大小的選擇n頁面的大小應適中。若頁面太大，以至和一般進程大小相差無幾，則頁面分配退化為分區分配，同時頁內碎片也較大。若頁面太小，雖然可減少頁內碎片，但會導致頁表增長。因此，頁面大小應適中，通常為2的冪，一般在512B到4KB之間。n頁表一般存放在內存中。也可以在頁表中設置存取控制字段，以實現存儲保護。存儲分塊表（存儲分塊表（MB

29、T）n存儲分塊表用來記錄內存中各物理塊的使用情況及未分配物理塊總數。n存儲分塊表可用下述方式表示：n位示圖：利用二進制的一位表示一個物理塊的狀態，1表示一分配，0表示未分配。所有物理塊狀態位的集合構成位示圖。n空閑存儲塊鏈：將所有的空閑存儲塊用鏈表鏈接起來，利用空閑物理塊中的單元存放指向下一個物理塊的指針。存儲分塊表（存儲分塊表（MBT）n存儲分塊表用來記錄內存中各物理塊的使用情況及未分配物理塊總數；n存儲分塊表可用下述方式表示：n位示圖：位示圖：利用二進制的一位表示一個物理塊的狀態，1表示已分配，0表示未分配。所有物理塊狀態位的集合構成位示圖；n空閑存儲塊鏈：空閑存儲塊鏈：利用空閑物理塊中的

30、單元存放指向下一個物理塊的指針，將所有的空閑存儲塊用鏈表鏈接起來。 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4進程請求表進程請求表n請求表用來登記每個進程的頁表在內存中的物理位置及每個頁表的長度、狀態等。如下圖所示。進程號 請求頁面數頁表始址頁表長度狀態010102410已分120103420已分215105415已分328未分 7。4。3 存儲空間的分配

31、及回收存儲空間的分配及回收n頁面分配：頁面分配：計算進程所需頁面數，然后在請求表中登記進程號、請求頁面數等。如存儲分塊表中有足夠的空閑塊可供進程使用，則在系統中取得頁表始址，并在頁表中登記頁號及其對應的物理塊號。否則無法分配；（見P138的程序）n頁面回收：頁面回收：將存儲分塊表中相應的物理塊改為未分配，或將回收塊加入到空閑存儲塊鏈中，并釋放頁表，修改請求表中的頁表始址及狀態；7。4。4 地址變換機構地址變換機構n地址變換機構的任務是實現邏輯地址到物理地址的轉地址變換機構的任務是實現邏輯地址到物理地址的轉換，即在程序動態執行的過程中，將換，即在程序動態執行的過程中，將CPU的訪存邏輯的訪存邏輯

32、地址變換成內存的物理地址；地址變換成內存的物理地址；n分頁地址變換機構自動地將邏輯地址分為頁號和頁內分頁地址變換機構自動地將邏輯地址分為頁號和頁內位移，例如，邏輯地址的長度為位移，例如，邏輯地址的長度為20位（邏輯空間的大位（邏輯空間的大小為小為220=1M），頁面大小為），頁面大小為1K，則頁內位移量，則頁內位移量W=10位（位（90，210=1K，注意：頁的大小一定是注意：頁的大小一定是2的整數次方的整數次方），頁號），頁號P=10位（位（1910），如下圖所），如下圖所示：示：19 10 9 019 10 9 0 頁頁 號號 P 頁頁 內內 位位 移移W地址變換過程地址變換過程n將頁號與

33、頁表長度進行比較，如果頁號超過了頁表長度，則表示本次所訪問的地址已超越進程的地址空間，系統產生地址越界中斷；n若未出現越界，則由頁表始址和頁號計算出相應頁表項的位置，從中得到該頁的物理塊號；n將邏輯地址中的頁內位移與上面得到的物理塊號拼接在一起，就形成了訪問主存的物理地址；地址變換示意圖地址變換示意圖n為什么是拼接而不是相加？為什么是拼接而不是相加？頁表寄存器頁表始址 頁表長度越界中斷邏輯地址 頁號（2） 頁內位移（452）頁號 塊號2385101234 8 452物理地址頁表地址變換舉例地址變換舉例n設邏輯地址為20位，頁面大小為1K字節，作業的0、1、2頁分別存放在第2、3、8塊中。則邏輯

34、地址2500的頁號及頁內地址分別為：2500/1024=2（頁號）；2500 %1024452（頁內地址）；n查頁表可知第2頁對應的物理塊號為8；n將塊號8與頁內地址452拼接得到物理地址為： 810244528644；8644就是本次CPU訪存的物理地址。n2500（10）的二進制表示是：的二進制表示是：0000000010 0111000100 P W聯想（相聯）存儲器及快表聯想（相聯）存儲器及快表n因頁表放在主存中，故存取指令或數據時CPU至少要訪問兩次主存。降低了內存訪問速度。n為了提高地址變換速度，可在地址變換機構中增設一個具有并行查找能力的高速緩沖存儲器（又稱聯想存儲器或快表），用

35、以存放當前訪問的那些頁表項；n地址變換機構自動將頁號與快表中的所有頁號進行并行比較，若其中有與此匹配的頁號，則取出該頁對應的塊號，與頁內地址拼接形成物理地址；n若頁號不在快表中，則再到主存頁表中取出物理塊號，與頁內地址拼接形成物理地址；n同時還應將這次所查到的頁表項存入快表中，若快表已滿，則必須按某種原則淘汰出一個表項以騰出位置。具有聯想存儲器（快表）的地址變換具有聯想存儲器（快表）的地址變換n頁表與快表有何不同？快表該多大？頁表與快表有何不同？快表該多大？頁表寄存器 頁表始址 頁表長度越界中斷邏輯地址 頁號 頁內位移頁號 塊號 01234 物理地址頁表頁號 塊號快表7。4。5 多級頁表及反向

36、頁表多級頁表及反向頁表n現代計算機系統都支持非常大的邏輯地址空間，致使頁表很大，用連續空間存放頁表顯然不現實；n如邏輯地址32位，頁面大小4KB，則頁表項為1M，若每個頁表項占4字節，則頁表共需要4MB內存空間；n解決方案：n用離散方式存儲頁表n僅將當前需要的部分頁表項放在內存，其余放在磁盤上，需要時再調入。兩級頁表及多級頁表兩級頁表及多級頁表n將頁表再分頁，使每頁與內存物理塊大小相同，并為它們進行編號0、1、，同時還為離散存放的頁表建立一張頁表。n例如：32位地址可以劃分為31 22 21 12 11 0 一級頁號p1 二級頁號p2 頁內地址w兩級頁表結構兩級頁表結構第0頁頁表內存空間一級頁

37、表 200020242700 2 7 0123456785901411012n 0 1 2 1023 85 90 第1頁頁表 0 1 21023 1411 0 1 21023第n頁頁表具有兩級頁表的地址變換機構具有兩級頁表的地址變換機構 n利用邏輯地址中的一級頁號作為索引訪問一級頁表，找到第二級頁表的起利用邏輯地址中的一級頁號作為索引訪問一級頁表，找到第二級頁表的起始地址；始地址；n再利用第二級頁號找到指定頁表項，從中取出塊號與頁內地址拼接形成物再利用第二級頁號找到指定頁表項，從中取出塊號與頁內地址拼接形成物理地址。理地址。 第一級頁表寄存器邏輯地址+二級頁表一級頁表 b w物理地址一級頁號

38、二級頁號 頁內地址 p1 p2 wb反向頁表及其地址變換反向頁表及其地址變換n為解決頁表占用大量存儲空間的問題，另一種創新思路是引入反向頁表；n反向頁表為每個物理塊設置一個頁表項，并將它們按物理塊號大小排序，表項內容為頁號及其所屬進程的標識號（如果已分配）；n利用進程標識號及頁號檢索反向頁表，若找到相應的頁表項，則將其物理塊號與頁內地址拼接；否則請求調入該進程相應頁，在無調頁功能的系統中則出錯；n由于反向頁表中沒有存放進程中尚未調入頁，因此必須為每個進程建立一張傳統頁表并存放在外存中，當所訪問頁不在內存時使用這張頁表。頁表中包含各頁在外存的地址。反向頁表的地址變換反向頁表的地址變換n反向頁表有

39、什么不足？反向頁表有什么不足？邏輯地址邏輯地址進程標識號進程標識號 頁號頁號反向頁表反向頁表 b w物理地址物理地址 頁號頁號 頁內地址頁內地址 p w pid ppid p進程標識號進程標識號pid 0 1 2 bn n7.4.6 存儲保護存儲保護n分頁存儲管理采用兩種方式保護內存：n地址越界保護：頁表長度與邏輯地址中的頁號比較；n存取控制保護：在頁表中增加保護位；7。5 分段管理分段管理n7。5。1 原理原理n由于分頁按物理單位進行，沒有考慮程序段的邏輯完由于分頁按物理單位進行，沒有考慮程序段的邏輯完整性，給程序段的共享和保護帶來不便，另外動態鏈整性，給程序段的共享和保護帶來不便，另外動態

40、鏈接及段的動態增長也要求以邏輯上完整的程序段為單接及段的動態增長也要求以邏輯上完整的程序段為單位管理，于是提出分段管理；位管理，于是提出分段管理；n在分段存儲管理系統中，作業的地址空間由若干個邏在分段存儲管理系統中，作業的地址空間由若干個邏輯分段組成，每個分段是一組邏輯意義相對完整的信輯分段組成，每個分段是一組邏輯意義相對完整的信息集合，每個分段都有自己的名字，每個分段都從息集合，每個分段都有自己的名字，每個分段都從0開開始編址，每個分段都有一個編號，從而形成一個二維始編址，每個分段都有一個編號，從而形成一個二維的地址空間；的地址空間；n在進行存儲分配時，以段為單位分配內存，每段分在在進行存儲

41、分配時，以段為單位分配內存，每段分在一個連續的內存區，但各段之間不要求連續。一個連續的內存區，但各段之間不要求連續。分段管理的邏輯地址結構和二維空間分段管理的邏輯地址結構和二維空間n在分段管理下，CPU訪存的邏輯地址由段號S和段內位移量W兩部分組成，如下圖所示的邏輯地址，共有64K個段，每個段的長度為64K字節。010101010段1段2段3段代碼段數據段棧段擴展段程序的二維程序的二維地址空間地址空間31 16 15 0 段 號 S 段 內 位 移 W7。5。2 實現實現一一 數據結構數據結構n段表：段表：每個進程建立一個段表，段表的每個表項記錄該進程一段的相關信息，包括：n段號；n段長；n段

42、在內存的起始地址；n其他信息；n空閑塊表或空閑塊鏈：空閑塊表或空閑塊鏈：形式與分區管理相同，用來記錄空閑段的現狀；段表的作用段表的作用內存空間作業的地址空間段表 30K 40K 20K 80K 15K 120K 10K 150K段號 段長 基址040K80K120K150K(MAIN)=0030K(X)=1020K(D)=2015K(S)=3020K0123 (MAIN)=0 30K (X)=1 20K (D)=2 15K (S)=3 15K二二 地址變換地址變換n為實現從邏輯地址到物理地址的轉換，在系統中設置了段表為實現從邏輯地址到物理地址的轉換，在系統中設置了段表寄存器，用于存放段表始址和

43、段表長度；寄存器，用于存放段表始址和段表長度；n為了提高內存的訪問速度，段表也可以存放在快表內；為了提高內存的訪問速度，段表也可以存放在快表內；n進行地扯變換時，系統將邏輯地址中的段號與段表長度進行進行地扯變換時，系統將邏輯地址中的段號與段表長度進行比較，若段號超過了段表長度則產生越界中斷；比較，若段號超過了段表長度則產生越界中斷；n否則根據段表始址和段號計算出該段對應段表項的位置，從否則根據段表始址和段號計算出該段對應段表項的位置，從中讀出該段在內存的起始地址；中讀出該段在內存的起始地址；n然后再檢查段內地址是否超過該段的段長，若超過則同樣發然后再檢查段內地址是否超過該段的段長，若超過則同樣

44、發出越界中斷信號；出越界中斷信號；n若未越界，則將該段的起始地址與段內位移相加，從而得到若未越界，則將該段的起始地址與段內位移相加，從而得到要訪問的內存物理地址。要訪問的內存物理地址。地址變換示意圖地址變換示意圖n設作業分為設作業分為3段，段，0、1、2段長度分別為段長度分別為1K、800、600，分別存放在內存分別存放在內存6K、4K、8K開始的內存區域；開始的內存區域；nCPU訪存的邏輯地址（訪存的邏輯地址（2，100）的段號為）的段號為2，段內位移，段內位移為為100；n查段表可知第查段表可知第2段在內存的起始地址為段在內存的起始地址為8K；n將起始地址與段內位移相加，將起始地址與段內位

45、移相加，8K1008292，得到得到物理地址為物理地址為8292。段表寄存器 段表始址 段表長度越界中斷邏輯地址 段號（2）段內位移（100）段號 段長 始址 1K 6K800 4K600 8K012物理地址8292三三 空間的分配與回收空間的分配與回收n分段管理可以看作是分區管理的擴充，而分區管理可以看作是分段管理的特例。因此，這兩種管理方法的空間分配和回收程序是類似的：分區管理為一道程序只分配和回收一段空間，而分段管理要為一道程序分配和回收多段空間，僅次而已。7。5。3 分段與分頁的主要區別分段與分頁的主要區別n分頁管理與分段管理有許多相似之處，但兩者在概念上也有分頁管理與分段管理有許多相似之處，但兩者在概念上也有很多區別，主要表現在：很多區別，主要表現在：n頁是信息的物理單位，是為了減少內存碎片及提高內存利頁是信息的物理單位，是為了減少內存碎片及提高內存利用率，是系統管理的需要。段是信息的邏輯單位，它含有用率，是系統管理的需要。段是信息的邏輯單位，它含有一組意義相對完整的信息，分段的目的是為了更好地滿足一組意義相對完整的信息，分段的目的是為了更好地滿足用戶編程的需要；用戶編程的需要；n頁的