存儲(chǔ)器管理第五章

第五章存儲(chǔ)器管理

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

存儲(chǔ)管理的功能內(nèi)存分配、回收存儲(chǔ)保護(hù)地址變換存儲(chǔ)共享存儲(chǔ)擴(kuò)充第五章存儲(chǔ)器管理

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

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

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

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

編譯多個(gè)目標(biāo)模塊

鏈接一個(gè)裝入模塊

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

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

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

…Moveah,[300]4789……0100300400

程序

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

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

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

…Moveah,[300]4789……0100300400

程序

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

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

重定位寄存器—存放程序在內(nèi)存的起始地址

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

對相對地址進(jìn)行修改;變換外部調(diào)用符號;二、程序的鏈接5.1程序的裝入和鏈接2.裝入時(shí)動(dòng)態(tài)鏈接

3.運(yùn)行時(shí)動(dòng)態(tài)鏈接

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

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

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

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

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

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

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

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

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

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

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

示意圖克服外部碎片的一種技術(shù)是壓縮（緊湊）。移動(dòng)進(jìn)程，使零散的小空閑空間連成一片。

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

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

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

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

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

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

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

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

n頁用戶進(jìn)程3頁0頁

1頁

2頁

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

分頁存儲(chǔ)管理的基本方法基本思想5.3.1

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

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

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

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