存儲器管理第五章

第五章存儲器管理

5.1程序的裝入和鏈接5.2連續(xù)分配存儲管理方式5.3分頁存儲管理方式5.4分段存儲管理第五章存儲器管理

存儲管理的功能內存分配、回收存儲保護地址變換存儲共享存儲擴充第五章存儲器管理

存儲管理的功能內存分配、回收存儲保護確保每道用戶進程都在自己的內存空間中運行，互不干擾，沖突和破壞;多道：用戶進程不允許訪問OS的程序和數(shù)據(jù)；而且用戶進程不允許訪問其他用戶進程的程序和數(shù)據(jù)空間。第五章存儲器管理

存儲管理的功能存儲保護每個進程都分別有一個上界限地址寄存器和一個下界限地址寄存器，每次訪問內存時都與這兩個界限寄存器比較，判斷是否越界。程序A0100H01FFH0100H01FFH下界限地址寄存器上界限地址寄存器內存需要硬件來實現(xiàn):第五章存儲器管理

存儲管理的功能地址變換將邏輯地址轉化為物理地址程序1程序20000H0FFFH0000H08FFHOS區(qū)程序10000H0FFFH程序20000H08FFH1000H1FFFH2000H28FFHJMP0421H×JMP2421H第五章存儲器管理

存儲管理的功能存儲共享多個進程共用同一系統(tǒng)軟件，如編譯程序，存放編譯程序的內存區(qū)即為共享內存區(qū);在邏輯上擴充內存容量，采用虛擬存儲器技術。存儲擴充一個用戶源程序變?yōu)榭稍趦却嬷袌?zhí)行的程序，步驟：用戶源程序

編譯多個目標模塊

鏈接一個裝入模塊

裝入裝入內存(可在內存中執(zhí)行的程序)第五章存儲器管理

5.1程序的裝入和鏈接一、程序的裝入1.絕對裝入方式

由裝入程序根據(jù)裝入模塊中的地址,將程序和數(shù)據(jù)裝入內存。邏輯地址：源程序經過編譯后形成的目標模塊或裝配鏈接程序的地址編碼。物理地址：程序在主存儲器中的地址編碼。邏輯地址=物理地址5.1程序的裝入和鏈接一、程序的裝入2.可重定位裝入方式

…Moveah,[300]4789……0100300400

程序

內存裝入并進行靜態(tài)地址重定位1000…Moveah,[1300]4789……110013001400裝入位置內存中代碼的地址部分已經被修改5.1程序的裝入和鏈接一、程序的裝入2.可重定位裝入方式

物理地址=邏輯地址+本程序在內存中的起始地址---靜態(tài)重定位

在程序執(zhí)行之前進行的重定位，在程序裝入內存時一次性完成指令中地址的修改。靜態(tài)重定位無需硬件的支持，由裝入模塊負責完成;缺點：程序裝入內存后，不允許移動在內存中的位置;5.1程序的裝入和鏈接一、程序的裝入3.動態(tài)運行時裝入方式

…Moveah,[300]4789……0100300400

程序

內存1000…Moveah,[300]4789……110013001400裝入位置原封不動裝入執(zhí)行到語句時，進行地址重定位1000重定位寄存器加法器30010001300動態(tài)重定位的實現(xiàn)5.1程序的裝入和鏈接一、程序的裝入3.動態(tài)運行時裝入方式

裝入主存的程序仍然保持原來的邏輯地址，由邏輯地址到物理地址的轉換在程序真正執(zhí)行時進行。---動態(tài)重定位動態(tài)重定位必須有硬件的支持

重定位寄存器—存放程序在內存的起始地址

加法器—將起始地址與相對地址相加獲得物理地址優(yōu)點：裝入內存后，代碼可以移動二、程序的鏈接5.1程序的裝入和鏈接1.靜態(tài)鏈接

對相對地址進行修改;變換外部調用符號;二、程序的鏈接5.1程序的裝入和鏈接2.裝入時動態(tài)鏈接

3.運行時動態(tài)鏈接

對某些模塊的鏈接推遲到執(zhí)行時才執(zhí)行;優(yōu)點:加快程序的裝入過程，而且可節(jié)省大量的內存空間。

優(yōu)點：便于修改和更新。(2)便于實現(xiàn)對目標模塊的共享。

程序是在連續(xù)區(qū)域中，還是劃分成若干塊放在不同區(qū)域中？內存是事先還是動態(tài)劃分？對于不同的內存分配方案，采用的地址變換技術也不同。5.2連續(xù)分配存儲管理方式5.2連續(xù)分配存儲管理方式連續(xù)分配：是指為一個用戶程序分配一個連續(xù)的內存空間。分類：單一連續(xù)分配方式分區(qū)式分配方式固定分區(qū)式動態(tài)分區(qū)(可變分區(qū))5.2.1單一連續(xù)分配適用于單用戶、單任務的操作系統(tǒng)中;內存分為兩個區(qū)域：系統(tǒng)區(qū)，用戶區(qū)在DOS中就采用了這種方法。

系統(tǒng)區(qū)僅提供給OS使用，通常放在內存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內存空間，提供給用戶使用。5.2連續(xù)分配存儲管理方式5.2.2固定分區(qū)分配一、劃分分區(qū)的方法5.2連續(xù)分配存儲管理方式缺點:缺乏靈活性。任何程序，無論多小，都要占據(jù)一個分區(qū)，造成內存空間的浪費;程序太大，不能放到分區(qū)中;內部碎片：分配給進程的分區(qū)中，進程沒有使用的部分1.分區(qū)大小相等

示意圖2.分區(qū)大小不等

示意圖優(yōu)點:克服分區(qū)大小相等而缺乏靈活性的缺點，可根據(jù)程序的大小為之分配適當?shù)姆謪^(qū)。缺點:還是有內部碎片；仍然存在作業(yè)太大不能運行的問題；內存分配§6.2分區(qū)式存儲管理程序132k程序250k內存分成大小相等的分區(qū)64k64k64k64k64k程序3120k沒有足夠大的分區(qū)程序1程序2空閑空間稱為內部碎片內部碎片1.分區(qū)大小相等

2.分區(qū)大小不等

程序132k程序250k內存分成大小不等的分區(qū)16k32k64k128k程序3120k32k程序1程序2程序3程序4180k

作業(yè)太大內部碎片5.2.2固定分區(qū)分配二、內存分配5.2連續(xù)分配存儲管理方式

分區(qū)使用表：分區(qū)由小到大進行排隊，記錄分區(qū)的大小，起始地址，是否已分配等信息20未分配5.2.3動態(tài)分區(qū)分配5.2連續(xù)分配存儲管理方式

分區(qū)的個數(shù)和大小不是固定不變的，而是可變的，隨裝入的作業(yè)動態(tài)劃分；且不會產生內部碎片。動態(tài)分區(qū)(可變分區(qū))

示意圖克服外部碎片的一種技術是壓縮（緊湊）。移動進程，使零散的小空閑空間連成一片。

必須采用動態(tài)重定位—可重定位分區(qū)分配（5.2.4）外部碎片：若存儲塊長度為n，在該系統(tǒng)所采用的調度算法下較長時間內無法選出一道長度不超過該塊的進程，則稱該塊為外部碎片。5.2.3動態(tài)分區(qū)分配5.2連續(xù)分配存儲管理方式

實現(xiàn)動態(tài)分區(qū)(可變分區(qū))分配時，須解決的問題一、分區(qū)分配中的數(shù)據(jù)結構二、分區(qū)分配算法三、分區(qū)分配、回收操作020OS程序18k程序232k2860程序4120k92程序332k212512程序6256k程序524k8446832k128k44k程序18k程序524k程序n206k程序730k程序848k程序m40k外部碎片外部碎片5.2.3動態(tài)分區(qū)分配一、分區(qū)分配中的數(shù)據(jù)結構1.空閑分區(qū)表

2.空閑分區(qū)鏈5.2.3動態(tài)分區(qū)分配二、分區(qū)分配算法1.首次適應算法FF。2.循環(huán)首次適應算法空閑分區(qū)鏈以地址遞增的次序鏈接；進行內存分配時，從鏈首開始順序查找。算法描述：缺點：低址不斷劃分，致使留下許多難以利用的、很小的空閑分區(qū)；每次從低址部分開始，增加查找可用空閑分區(qū)開銷?？臻e分區(qū)鏈以地址遞增的次序鏈接；進行內存分配時，從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找。算法描述：特點：減少查找開銷，空閑分區(qū)分布的更均勻。但缺乏大的空閑分區(qū)。5.2.3動態(tài)分區(qū)分配二、分區(qū)分配算法3.最佳適應算法空閑分區(qū)由小到大形成空閑分區(qū)鏈，每次從鏈首找，找到的第一個，必然是最小的；算法描述：缺點：劃分后剩余的空閑區(qū)最小；每次為作業(yè)分配內存時，總是把滿足要求的、最小的空閑分區(qū)分配給作業(yè)?！白罴选焙x：5.2.3動態(tài)分區(qū)分配二、分區(qū)分配算法例：某操作系統(tǒng)采用可變分區(qū)分配存儲管理方法，用戶區(qū)主存為512K，且始址為0，分配時截取空閑塊的前半部分（小地址部分）。初始時用戶區(qū)的512K空間空閑。在執(zhí)行了如下操作序列后：申請300K，申請100K，釋放300K，申請150K，申請30K，申請40K，申請60K，釋放30K。1.采用首次適應算法，有哪些空閑塊（指出大小及始址）。2.采用最佳適應算法，有哪些空閑塊（指出大小及始址）。3.如再申請100K，針對1、2各有什么結果？說明了什么問題。5.2.3動態(tài)分區(qū)分配二、分區(qū)分配算法例：1.采用首次適應算法，空閑塊有大小起始地址30K150K20K280K112K400K2.采用最佳適應算法，空閑塊有大小起始地址30K400K42K470K90K210K3.如再申請100K，則首次適應算法可滿足，而最佳適應算法不能滿足，說明最佳適應算法并不總優(yōu)于首次適應算法。三、分區(qū)分配、回收操作1.分配內存m.size：空閑區(qū)大小；u.size：請求大??；size：事先規(guī)定的不再切割的剩余分區(qū)的大小。5.2.3動態(tài)分區(qū)分配三、分區(qū)分配、回收操作2.回收內存A空閑釋放分配B空閑釋放分配空閑釋放空閑C分配釋放分配D當進程運行完畢釋放內存時，系統(tǒng)根據(jù)回收區(qū)首址，從空閑分區(qū)鏈中找到相應的插入點。此時出現(xiàn)四種情況：5.2.4動態(tài)重定位分區(qū)分配5.2連續(xù)分配存儲管理方式一、動態(tài)重定位的引入5.2.4動態(tài)重定位分區(qū)分配5.2連續(xù)分配存儲管理方式二、動態(tài)重定位的實現(xiàn)動態(tài)運行時裝入方式示意圖實現(xiàn):不需對程序作任何修改,“緊湊”時修改重定位寄存器內容，用程序在內存的新起始地址，去置換原來的起始地址即可。5.2.4動態(tài)重定位分區(qū)分配三、動態(tài)重定位分區(qū)分配算法

是址5.3分頁存儲管理方式引入：連續(xù)分配產生“碎片”，“緊湊”付出很大開銷；離散分配：

將一個進程直接分散的分配到不相鄰接的分區(qū)中(不必“緊湊”)。分類：分頁存儲管理方式分段存儲管理方式段頁式存儲管理方式5.3.1分頁存儲管理的基本方法5.3.2地址變換機構5.3分頁存儲管理方式5.3.1

分頁存儲管理的基本方法一、頁面和物理塊將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁；頁面：物理塊：內存空間分成與頁面相同大小的若干個存儲塊，稱為(物理)塊或頁框(frame)；在為進程分配內存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。頁內碎片：進程的最后一頁經常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內碎片”；分頁存儲管理的基本思想：示意圖5.3分頁存儲管理方式二、地址結構5.3.1

分頁存儲管理的基本方法位移量W頁號P3112110若給定一個邏輯地址空間中的地址為A，頁面的大小為L，則頁號P和頁內地址d可按下式求得：5.3分頁存儲管理方式三、頁表5.3.1

分頁存儲管理的基本方法頁面映射表。記錄了相應的頁在內存中對應的物理塊號，實現(xiàn)了從頁號到物理塊號的地址映射。示意圖5.3分頁存儲管理方式0頁1頁2頁3頁4頁...

n頁用戶進程3頁0頁

1頁

2頁

內存01234519021421931頁號塊號頁表程序原封不動的裝入內存中，采用動態(tài)重定位頁表5.3.1

分頁存儲管理的基本方法基本思想5.3.1

分頁存儲管理的基本方法四、頁面大小的選擇2.頁面的大小應選擇得適中，通常在29至212之間，即512B至4KB之間。1.頁面大小由機器的地址結構所決定,亦即由硬件決定;一種機器只能采用一種大小的頁面。5.3分頁存儲管理方式5.3.2地址變換機構一、基本任務

實現(xiàn)邏輯地址到物理地址的轉換，借助頁表實現(xiàn)。----分頁存儲管理的動態(tài)重定位5.3分頁存儲管理方式5.3.2地址變換機構二、基本地址變換機構頁表的功能可以由一組專門寄存器實現(xiàn);---適用于較小系統(tǒng)頁表大多駐留在內存中;概念：131924120

頁號塊號64頁表始址頁表長度頁表項長度頁表項地址=頁表始址+頁號*頁表項長度5.3分頁存儲管理方式§6.3分頁式存儲管理CPU頁表始址頁表長度頁號塊號0417253348頁表寄存器內存>越界中斷+頁號頁內地址邏輯地址塊號頁內地址物理地址二、基本地址變換機構段頁式存儲5.3.2地址變換機構二、基本地址變換機構示意圖存放當前運行進程的頁表始址和頁表長度，每個進程裝入內存時，頁表始址和頁表長度先存放在本進程的PCB中，運行時才放入頁表寄存器;----多道程序環(huán)境中，需一個頁表寄存器頁表寄存器頁表在內存，CPU每存取一個數(shù)據(jù),需兩次訪問內存,使計算機的處理速度降低近1/2。5.3分頁存儲管理方式5.3.2地址變換機構三、具有快表的地址變換機構1.引入基本地址變換機構中，頁表在內存，CPU每存取一個數(shù)據(jù),需兩次訪問內存，使計算機的處理速度降低近1/2。在地址變換機構中，增設具有并行查尋能力的特殊高速緩沖存儲器，又稱“聯(lián)想存儲器”或“快表”?？毂碇写娣抛罱L問的頁表項。5.3分頁存儲管理方式三、具有快表的地址變換機構2.地址變換過程5.3分頁存儲管理方式例題：設有一單純分頁系統(tǒng)，頁的大小為1KB。假定一進程的代碼段長度為10頁，頁表如表一所示，快表如表二所示：

頁號物理塊號08172431049::92頁號物理塊號081724310表一：表二：現(xiàn)進程有如下訪問序列：其邏輯地址為：0AC5H、0EC3H、12C5H、62C3H。試問給定的這些地址能否進行轉換？若能，請說明轉換過程及相應的物理地址；若不能，則說明理由。5.3分頁存儲管理方式答案：頁面大小為1KB，頁內位移為10位，邏輯地址為十六進制，轉換為二進制，右邊10位即為頁內位移d，其余左邊高位為頁號P。OAC5H=0000101011000101Bp=2，d=02C5H，查快表，得物理地址(4)2C5H0EC3H=0000111011000011Bp=3，d=02C3H，查快表，得物理地址(A)2C3H12C5H=0001001011000101Bp=4，d=02C5H，該頁號不在快表，需到主存頁表項中尋找對應物理塊號，得內存物理塊號P=9，d=02C5H，得物理地址(9)2C5H62C3H=0110001011000011Bp=24，d=02C3H，頁號超出頁表范圍，不可轉換，作為越界處理。5.4分段存儲管理5.4.1分段存儲管理方式的引入5.4.2分段系統(tǒng)的基本原理5.4.3段頁式存儲管理方式5.4.1分段存儲管理方式的引入5.4分段存儲管理引入分段存儲管理方式，主要是為了滿足用戶和程序員的下述一系列需要：方便編程信息共享信息保護動態(tài)增長動態(tài)鏈接5.4.2分段系統(tǒng)的基本原理5.4分段存儲管理一、分段作業(yè)的地址空間被劃分成若干個段，離散的分配在內存中不相鄰接的分區(qū)中；每個段有自己的名字，都從0開始編址，定義了一組邏輯信息；放在連續(xù)的存儲區(qū)域上；由于每個段的長度可以不同，因而每個段的內存分配和回收類似于動態(tài)分區(qū)的分配和回收辦法。會產生外部碎片。示意圖5.4分段存儲管理二、地址結構段內地址段號3116150分段的地址空間是二維的。5.4.2分段系統(tǒng)的基本原理三、段表5.4分段存儲管理示意圖每個段表項必須給出相應的段在主存中的起始地址和段的長度，實現(xiàn)由邏輯地址到物理地址的映射，并確保不會使用無效地址。地址變換機構5.4.2分段系統(tǒng)的基本原理圖4-16利用段表實現(xiàn)地址映射分段段表5.4.2分段系統(tǒng)的基本原理四、地址變換機構5.4分段存儲管理四、地址變換機構段表的功能可以由一組專門寄存器實現(xiàn);---適用于較小系統(tǒng)段表大多駐留在內存中;存放當前運行進程的段表始址和段表長度;段表寄存器段表在內存，CPU每存取一個數(shù)據(jù),需兩次訪問內存,使計算機的處理速度降低近1/2。在地址變換機構中，增設“快表”,存放最近訪問的段表項---具有快表的地址變換機構。5.4.2分段系統(tǒng)的基本原理5.4分段存儲管理五、分頁和分段的主要區(qū)別1.