1、精選課件第第7章章 存儲器管理存儲器管理n存儲器管理的主要目標(biāo)是為用戶提供方便、安全和充分大的存儲器。n存儲器即主存、內(nèi)存，分為兩大部分：n系統(tǒng)區(qū)：供操作系統(tǒng)使用n用戶區(qū)：劃分為一個或多個區(qū)域，供用戶進程使用。精選課件存儲器管理的功能存儲器管理的功能n存儲空間的分配和回收：n地址變換：將邏輯地址變換為物理地址n存儲保護：防止因用戶程序錯誤破壞系統(tǒng)或其他用戶，防止程序之間的相互干擾n存儲擴充：在邏輯上為用戶提供一個比實際內(nèi)存更大的存儲空間精選課件7.1 存儲器管理的基本概念存儲器管理的基本概念n邏輯地址：用戶編程時所使用的地址。又稱相對地址、虛地址。n地址空間：邏輯地址的集合。n物理地址：內(nèi)存中

2、的地址。又稱絕對地址、實地址。n主存空間：物理地址的集合。精選課件地址變換n地址變換：將邏輯地址轉(zhuǎn)換為物理地址。又稱地址映射、重定位。 n地址變換分為兩類：n靜態(tài)地址變換n動態(tài)地址變換精選課件靜態(tài)地址變換n靜態(tài)地址變換：又稱靜態(tài)地址重定位，地址變換在程序裝入時一次完成，以后不再改變。n特點：不需硬件支持，但程序運行時不能在內(nèi)存移動，程序需要連續(xù)存儲空間，難以共享。精選課件靜態(tài)地址變換示意圖 mov ax,500 mov ax,500 54321 54321 mov ax,1000+500 mov ax,1000+500 54321 54321 0100500999 0 1000 1100 15

3、00 19991M-1作業(yè)的地址空間主存空間重定位裝入程序精選課件動態(tài)地址變換n動態(tài)地址變換：又稱動態(tài)重定位，在程序執(zhí)行過程中，每次訪問內(nèi)存之前將要訪問程序地址轉(zhuǎn)換成內(nèi)存地址。n特點：需要硬件支持，不需連續(xù)空間，可以實現(xiàn)虛擬存儲。 精選課件動態(tài)地址變換示意圖 mov ax,500mov ax,500 54321 54321 mov ax,500mov ax,500 54321 54321 0100500999 0 1000 1100 1500 19991M-1作業(yè)的地址空間存儲空間5001000邏輯地址重定位寄存器精選課件7.2 分區(qū)存儲管理分區(qū)存儲管理n分區(qū)存儲管理是多道程序系統(tǒng)中采用的一種

4、最簡單的方法。它把系統(tǒng)的內(nèi)存劃分為若干大小不等的區(qū)域，操作系統(tǒng)占一個區(qū)域，其他區(qū)域由并發(fā)進程共享，每個進程占一個區(qū)域。n分區(qū)存儲管理分為：n固定分區(qū)n動態(tài)分區(qū)精選課件7.2.1 固定分區(qū)存儲管理固定分區(qū)存儲管理n固定分區(qū)存儲管理方法將內(nèi)存空間劃分為若干個固定大小的分區(qū)，每個分區(qū)中可以裝入一道程序。分區(qū)的位置及大小在運行期間不能改變。n為了便于管理內(nèi)存，系統(tǒng)需要建立一張分區(qū)使用表，其中記錄系統(tǒng)中的分區(qū)數(shù)目、分區(qū)大小、分區(qū)起始地址及狀態(tài)。精選課件分區(qū)使用表例 操作系統(tǒng) 用戶作業(yè) 用戶作業(yè)分區(qū)號 大小 起始地址 狀態(tài) 1 8KB 20KB 已分配 2 32KB 28KB 已分配 3 32KB 60K

5、B 未分配 4 120KB 92KB 未分配 5 300KB 212KB 已分配 用戶作業(yè) 0 20KB 28KB 60KB 92KB 212KB512KB-1精選課件固定分區(qū)的內(nèi)存分配n分區(qū)分配：當(dāng)有用戶程序要裝入時，由內(nèi)存分配程序檢索分區(qū)使用表，從中找出一個能滿足要求的空閑分區(qū)分配給該程序，然后修改分區(qū)說明表中相應(yīng)表項的狀態(tài)；若找不到大小足夠的分區(qū)，則拒絕分配內(nèi)存。n分區(qū)回收：當(dāng)程序執(zhí)行完畢不再需要內(nèi)存資源時，釋放程序占用的分區(qū)，管理程序只需將對應(yīng)分區(qū)的狀態(tài)置為未分配即可。n特點：最早的多道程序存儲管理方式，不能充分利用內(nèi)存，存在內(nèi)存碎片。精選課件7.2.2 動態(tài)分區(qū)存儲管理動態(tài)分區(qū)存儲管

6、理n動態(tài)分區(qū)存儲管理又稱為可變分區(qū)存儲管理，這種存儲管理方法的實現(xiàn)思想是根據(jù)作業(yè)大小動態(tài)地建立分區(qū)，并使分區(qū)的大小正好適應(yīng)作業(yè)的需要。因此系統(tǒng)中分區(qū)的大小是可變的，分區(qū)的數(shù)目也是可變的。精選課件動態(tài)分區(qū)中的數(shù)據(jù)結(jié)構(gòu)n在動態(tài)分區(qū)中常用的數(shù)據(jù)結(jié)構(gòu)有：n空閑分區(qū)表。用一個空閑分區(qū)表來登記系統(tǒng)中的空閑分區(qū)。其表項類似于固定分區(qū)。n空閑分區(qū)鏈。將內(nèi)存中的空閑分區(qū)以鏈表方式鏈接起來，構(gòu)成空閑分區(qū)鏈。精選課件空閑分區(qū)表示意圖分區(qū)號 大小 起始地址 1 8KB 24KB 2 12KB 128KB 3 8KB 248KB 4 5 操作系統(tǒng) 空閑 (8K) 已分 (96K) 空閑 (12K) 已分 (108K)

7、空閑 (8K) 0 24KB 32KB 128KB 140KB 248KB256KB-1精選課件空閑分區(qū)鏈?zhǔn)疽鈭D 操作系統(tǒng) 空閑 (8K) 已分 (96K) 空閑 (12K) 已分 (108K) 空閑 (8K) 0 24KB 32KB 128KB 140KB 248KB256KB-1 操作系統(tǒng) 空閑 (8K) 已分 (96K) 空閑 (12K) 已分 (108K) 空閑 (8K) 0 24KB 32KB 128KB 140KB 248KB256KB-1表頭指針精選課件分區(qū)分配算法n目前常用的分區(qū)分配算法有以下幾種：n首次適應(yīng)算法n循環(huán)首次適應(yīng)算法n最佳適應(yīng)算法n最壞適應(yīng)算法精選課件首次適應(yīng)算法

8、n首次適應(yīng)算法又稱最先適應(yīng)算法，該算法要求空閑分區(qū)按地址遞增的次序排列。n在進行內(nèi)存分配時，從空閑分區(qū)表（或空閑分區(qū)鏈）首開始順序查找，直到找到第一個能滿足其大小要求的空閑分區(qū)為止。n然后，再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍然留在空閑分區(qū)表（或空閑分區(qū)鏈）中。精選課件首次適應(yīng)算法的特點n特點：優(yōu)先利用內(nèi)存低地址端，高地址端有大空閑區(qū)。但低地址端有許多小空閑分區(qū)時會增加查找開銷。精選課件循環(huán)首次適應(yīng)算法n循環(huán)首次適應(yīng)算法又稱下次適應(yīng)算法，它是首次適應(yīng)算法的變形。n該算法在為進程分配內(nèi)存空間時，從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到第一個能滿足

9、其大小要求的空閑分區(qū)為止。n然后，再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍然留在空閑分區(qū)表（或空閑分區(qū)鏈）中。精選課件循環(huán)首次適應(yīng)算法的特點n特點：使存儲空間的利用更加均衡，但會使系統(tǒng)缺乏大的空閑分區(qū)。精選課件最佳適應(yīng)算法n最佳適應(yīng)算法要求空閑分區(qū)按容量大小遞增的次序排列。n在進行內(nèi)存分配時，從空閑分區(qū)表（或空閑分區(qū)鏈）首開始順序查找，直到找到第一個能滿足其大小要求的空閑分區(qū)為止。n如果該空閑分區(qū)大于作業(yè)的大小，則從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，將剩余空閑區(qū)仍然留在空閑分區(qū)表（或空閑分區(qū)鏈）中。精選課件最佳適應(yīng)算法的特點n按最佳適應(yīng)算法為作業(yè)分配內(nèi)存，就

10、能把既滿足作業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)。n特點：保留了大的空閑區(qū)。但分割后的剩余空閑區(qū)很小。精選課件最壞適應(yīng)算法n最壞適應(yīng)算法要求空閑分區(qū)按容量大小遞減的次序排列。n在進行內(nèi)存分配時，先檢查空閑分區(qū)表（或空閑分區(qū)鏈）中的第一個空閑分區(qū)，若第一個空閑分區(qū)小于作業(yè)要求的大小，則分配失敗；n否則從該空閑分區(qū)中劃出與作業(yè)大小相等的一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍然留在空閑分區(qū)表（或空閑分區(qū)鏈）中。精選課件最壞適應(yīng)算法的特點n特點：剩下的空閑區(qū)比較大，但當(dāng)大作業(yè)到來時，其存儲空間的申請往往得不到滿足。精選課件如何衡量分配算法的好壞n對于某一個作業(yè)序列來說，若某種分配算法能將該

11、作業(yè)序列中所有作業(yè)安置完畢，則稱該分配算法對這一作業(yè)序列合適，否則稱為不合適。精選課件例n下表給出了某系統(tǒng)的空閑分區(qū)表，系統(tǒng)采用可變式分區(qū)存儲管理策略。現(xiàn)有以下作業(yè)序列：96K、20K、200K。若用首次適應(yīng)算法和最佳適應(yīng)算法來處理這些作業(yè)序列，試問哪一種算法可以滿足該作業(yè)序列的請求?分區(qū)號 大小起始地址132K100K210K150K35K200K4218K220K596K530K精選課件例-采用最佳適應(yīng)算法分配1n申請96K，n選中5號分區(qū)，5號分區(qū)大小與申請空間大小一致，應(yīng)從空閑分區(qū)表中刪去該表項；分區(qū)號 大小起始地址132K100K210K150K35K200K4218K220K596

12、K530K分區(qū)號 大小起始地址132K100K210K150K35K200K4218K220K精選課件例-采用最佳適應(yīng)算法分配2n申請20K，n選中1號分區(qū)，分配后1號分區(qū)還剩下12K；分區(qū)號 大小起始地址132K100K210K150K35K200K4218K220K分區(qū)號 大小起始地址112K100K210K150K35K200K4218K220K精選課件例-采用最佳適應(yīng)算法分配3n申請200K，n選中4號分區(qū)，分配后剩下18K。分區(qū)號 大小起始地址112K100K210K150K35K200K4218K220K分區(qū)號 大小起始地址112K100K210K150K35K200K418K22

13、0K精選課件例-采用首次適應(yīng)算法分配1n申請96K，n選中4號分區(qū)，進行分配后4號分區(qū)還剩下122K；分區(qū)號 大小起始地址132K100K210K150K35K200K4218K220K596K530K分區(qū)號 大小起始地址132K100K210K150K35K200K4122K220K596K530K精選課件例-采用首次適應(yīng)算法分配2n申請20K，n選中1號分區(qū)，分配后剩下12K；分區(qū)號 大小起始地址132K100K210K150K35K200K4122K220K596K530K分區(qū)號 大小起始地址112K100K210K150K35K200K4122K220K596K530K精選課件例-采用

14、首次適應(yīng)算法分配3n申請200K，n現(xiàn)有的五個分區(qū)都無法滿足要求，該作業(yè)等待。n顯然采用首次適應(yīng)算法進行內(nèi)存分配，無法滿足該作業(yè)序列的需求。分區(qū)號 大小起始地址112K100K210K150K35K200K4122K220K596K530K精選課件分區(qū)分配n以首次適應(yīng)算法及空閑鏈表為例，申請分區(qū)大小為x， e是規(guī)定的不再分割的剩余區(qū)大小。將該分區(qū)從鏈中移出開始查表是鏈表尾？本次無法分配，返回YN空閑區(qū)容量x?N繼續(xù)檢查下一項容量xe?YYN從該分區(qū)中劃出x大小將分區(qū)分配給請求者，修改數(shù)據(jù)結(jié)構(gòu)精選課件程序示例1void cmalloc(node *head,int x)node *p, *q,

15、*t; p=head;while(p-sizelinkif(p!=null)p-size=p-size-x;if(p-sizelink=p-link;else t=p+p-size-x;elset=0; printf(“本次無法分配！n”);return(t);精選課件分區(qū)回收n回收分區(qū)時，應(yīng)將空閑區(qū)插入適當(dāng)位置，此時有以下四種：n回收分區(qū)r上面鄰接一個空閑分區(qū)n回收分區(qū)r下面鄰接一個空閑分區(qū)n回收分區(qū)r上面、下面各鄰接一個空閑分區(qū)n回收分區(qū)r不與任何空閑分區(qū)相鄰精選課件回收分區(qū)r上鄰接一個空閑分區(qū)n此時應(yīng)將回收區(qū)r與上鄰接分區(qū)F1合并成一個連續(xù)的空閑區(qū)。合并分區(qū)的首地址為空閑區(qū)F1的首地址，

16、其大小為二者之和。F1回收區(qū)精選課件回收分區(qū)r下鄰接一個空閑分區(qū)n此時應(yīng)將回收區(qū)r與下鄰接分區(qū)F2合并成一個連續(xù)的空閑區(qū)。合并分區(qū)的首地址為回收分區(qū)r的首地址，其大小為二者之和。回收區(qū)F2精選課件回收分區(qū)r上下鄰接空閑分區(qū)n此時應(yīng)將回收區(qū)r與上、下鄰接分區(qū)合并成一個連續(xù)的空閑區(qū)。合并分區(qū)的首地址為與r上鄰接空閑區(qū)F1的首地址，其大小為三者之和，且應(yīng)將與r下鄰接的空閑區(qū)F2從空閑分區(qū)表(或空閑分區(qū)鏈)中刪去。F1回收區(qū)F2精選課件回收分區(qū)r不與任何空閑分區(qū)相鄰n這時應(yīng)為回收區(qū)單獨建立一個新表項，填寫分區(qū)大小及起始地址等信息，并將其加入到空閑分區(qū)表(或空閑分區(qū)鏈)中的適當(dāng)位置。n問題：回收分區(qū)的個

17、數(shù)變化情況？精選課件程序示例2 void cfree(node *head, *s) /*head 為空閑鏈表的頭指針，s為釋放區(qū)*/ node *p,*q; int n; p=head; n=s-size; while(p!=null & plink; if(q+q-size=s) & (s+n=p) q-link=p-link; q-size=q-size+p-size+n; else if (s+n = p) s-link=p-link; q-link=s; s-size=p-size+n; else if (q+q-size=s)q-size=q-size+n; els

18、es-link=p; q-link=s;精選課件內(nèi)存保護內(nèi)存保護n存儲保護是防止一個作業(yè)有意或無意破壞操作系統(tǒng)或其他作業(yè)。n常用的存儲保護方法有：n上下界寄存器n基址限長寄存器n除上述保護方案外，還有四種存取權(quán)限：n禁止做任何操作n只能執(zhí)行n只能讀n讀/寫精選課件上下界寄存器方法n上下界寄存器方法：n用上、下界寄存器分別存放作業(yè)存儲空間的結(jié)束地址和開始地址。n在作業(yè)運行過程中，將每一個訪問內(nèi)存的地址都同這兩個寄存器的內(nèi)容進行比較，若超出了上下界寄存器的范圍則產(chǎn)生越界中斷。精選課件基址限長寄存器方法n基址、限長寄存器方法：n用基址和限長寄存器分別存放作業(yè)存儲空間的起始地址及作業(yè)長度。n當(dāng)作業(yè)執(zhí)行

19、時，將每一個訪問內(nèi)存的相對地址和這個限長寄存器比較，若邏輯地址超過限長則產(chǎn)生越界中斷。精選課件7.2.3 碎片問題及拼接技術(shù)碎片問題及拼接技術(shù)n分區(qū)存儲管理中，必須把作業(yè)裝入到一片連續(xù)的內(nèi)存空間中。這種分配方法能滿足多道程序設(shè)計的需要，但存在碎片問題。 n碎片也可稱為零頭，是指內(nèi)存中無法被利用的存儲空間。精選課件內(nèi)部碎片和外部碎片n內(nèi)部碎片是指分配給作業(yè)的存儲空間中未被利用的部分n外部碎片是指系統(tǒng)中無法利用的小存儲塊。n前述分區(qū)存儲管理方法中存在什么碎片？精選課件解決碎片問題的辦法n拼接：解決碎片問題的辦法之一，即通過移動把多個分散的小分區(qū)拼接成一個大分區(qū)，也可稱為緊縮或緊湊。n拼接的不足是要

20、耗費大量處理機時間。精選課件拼接示意圖n拼接前 拼接后 操作系統(tǒng) 進程5 空閑（10KB） 進程4 空閑（30KB） 進程3 空閑（26KB） 0 40KB 90KB 100KB 170KB 200KB 230KB256KB-1 操作系統(tǒng) 進程5 進程4 進程3 空閑（66KB） 0 40KB 90KB 160KB 190KB 256KB-1精選課件拼接需要的技術(shù)支持拼接需要的技術(shù)支持n動態(tài)重定位：拼接后程序在內(nèi)存的位置發(fā)生變化，因此需要動態(tài)重定位技術(shù)支持。n空閑區(qū)放在何處：拼接后的空閑區(qū)放在何處不能一概而論，應(yīng)根據(jù)移動信息量的多少來決定。n拼接的時機：n回收分區(qū)時拼接：只有一個空閑區(qū)，但拼接

21、頻率過高增加系統(tǒng)開銷。n找不到足夠大的空閑區(qū)且系統(tǒng)空閑空間總量能滿足要求：拼接頻率小于前者，空閑區(qū)管理稍復(fù)雜。也可以只拼接部分空閑區(qū)。精選課件7.3 伙伴系統(tǒng)n固定分區(qū)存儲管理限制了內(nèi)存中的進程數(shù)，動態(tài)分區(qū)的拼接需要大量時間，而伙伴系統(tǒng)是一種較為實用的動態(tài)存儲管理辦法。n伙伴系統(tǒng)采用伙伴算法對空閑內(nèi)存進行管理。該方法通過不斷對分大的空閑存儲塊來獲得小的空閑存儲塊。當(dāng)內(nèi)存塊釋放時，應(yīng)盡可能合并空閑塊。精選課件伙伴系統(tǒng)的內(nèi)存分配n設(shè)系統(tǒng)初始時可供分配的空間為2m個單元。n當(dāng)進程申請大小為n的空間時，設(shè)2i-1n2i，則為進程分配大小為2i的空間。n如系統(tǒng)不存在大小為2i的空閑塊，則查找系統(tǒng)中是否存

22、在大于2i的空閑塊，若找到則對其進行對半劃分，直到產(chǎn)生大小為2i的空閑塊為止。精選課件伙伴系統(tǒng)的內(nèi)存回收n當(dāng)一塊被分成兩個大小相等的塊時，這兩塊稱為伙伴。n當(dāng)進程釋放存儲空間時，應(yīng)檢查釋放塊的伙伴是否空閑，若空閑則合并。這個較大的空閑塊也可能存在空閑伙伴，此時也應(yīng)合并。重復(fù)上述過程，直至沒有可以合并的伙伴為止。精選課件伙伴地址公式n設(shè)某空閑塊的開始地址為d，長度為2K，其伙伴的開始地址為：nBuddy（k，d）=d+2k，若d % 2k+1=0n =d-2k，若d % 2k+1= 2kn如果參與分配的2m個單元從a開始，則長度為2K、開始地址為d的塊，其伙伴的開始地址為：nBuddy（k，d）

23、=d+2k，若（d-a）% 2k+1=0n =d-2k，若（d-a）% 2k+1= 2k精選課件伙伴系統(tǒng)分配及回收例n設(shè)系統(tǒng)中初始內(nèi)存空間大小為1MB，進程請求和釋放空間的操作序列為：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初始狀態(tài)A申請200B申請120C申請240D申請100 B釋放 E申請60 C釋放 D釋放 E釋放512K256KAA512K128KBAB256

24、KCAB256KCDA256KCD128KA256KCD64E256KCD64E256KD64256K512KE64256K512K128K128K精選課件伙伴系統(tǒng)的二叉樹表示n可以用二叉樹表示內(nèi)存分配情況。葉結(jié)點表示存儲器中的當(dāng)前分區(qū)，如果兩個伙伴是葉子，則至少有一個被分配。n右圖表示A（200）、B（120）、C（240）、D（100）分配之后的情況。ABDC1M512K256K128K精選課件伙伴系統(tǒng)的不足n分配和回收時需要對伙伴進行分拆及合并。n存儲空間有浪費。精選課件7.4 分頁存儲管理分頁存儲管理n分區(qū)管理中存在碎片，而緊湊技術(shù)開銷太大，若能取消作業(yè)對存儲區(qū)的連續(xù)性要求，則能較好地

25、解決碎片問題。分頁存儲管理就是基于這一思想提出的。精選課件7.4.1 分頁存儲管理的基本原理n在分頁存儲管理中，將進程的邏輯地址空間劃分成若干大小相等的頁（或稱頁面），相應(yīng)地將主存空間也劃分成與頁大小相等的塊（或稱物理塊）。在為進程分配存儲空間時，總是以塊為單位來分配，可以將進程中的某一頁存放到主存的某一空閑塊中。n分頁系統(tǒng)中是否有碎片？n頁內(nèi)碎片：由進程最后一頁未裝滿而形成的碎片。精選課件頁表n為了在內(nèi)存中找到進程的每個頁面所對應(yīng)的物理塊，系統(tǒng)為每個進程建立一張頁面映象表，簡稱頁表。n頁表：記錄頁面在內(nèi)存中對應(yīng)物理塊的數(shù)據(jù)結(jié)構(gòu)。精選課件頁表的作用n頁表的作用是什么？內(nèi)存空間作業(yè)的地址空間頁表

26、 0頁1頁2頁n頁 0 2 1 4 2 7 頁號 塊號01234567精選課件頁面大小的選擇n頁面的大小應(yīng)適中。若頁面太大，以至和一般進程大小相差無幾，則頁面分配退化為：分區(qū)分配，同時頁內(nèi)碎片也較大。若頁面太小，雖然可減少頁內(nèi)碎片，但會導(dǎo)致頁表增長。因此，頁面大小應(yīng)適中，通常為2的冪，一般在512B到4KB之間。n頁表一般存放在內(nèi)存中。也可以在頁表中設(shè)置存取控制字段，以實現(xiàn)存儲保護。精選課件存儲分塊表n存儲分塊表用來記錄內(nèi)存中各物理塊的使用情況及未分配物理塊總數(shù)。n存儲分塊表可用下述方式表示：n位示圖：利用二進制的一位表示一個物理塊的狀態(tài)，1表示一分配，0表示未分配。所有物理塊狀態(tài)位的集合構(gòu)成

27、位示圖。n空閑存儲塊鏈：將所有的空閑存儲塊用鏈表鏈接起來，利用空閑物理塊中的單元存放指向下一個物理塊的指針。精選課件位示圖例n位示圖占用的存儲空間：物理塊數(shù)/8（字節(jié)） 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請求表用來登記每個進程的頁表在內(nèi)存中的物理位置及每個頁表的長度、狀態(tài)等。如下圖所示。進程號 請求頁面數(shù)頁表始址頁表長度狀態(tài)1101

28、02410已分220103420已分315105415已分428未分 精選課件7.4.2 存儲空間的分配及回收n頁面分配：計算進程所需頁面數(shù)，然后在請求表中登記進程號、請求頁面數(shù)等。如存儲分塊表中有足夠的空閑塊可供進程使用，則在系統(tǒng)中取得頁表始址，并在頁表中登記頁號及其對應(yīng)的物理塊號。否則無法分配。n頁面回收：將存儲分塊表中相應(yīng)的物理塊改為未分配，或?qū)⒒厥諌K加入到空閑存儲塊鏈中，并釋放頁表，修改請求表中的頁表始址及狀態(tài)。精選課件7.4.3 地址變換機構(gòu)地址變換機構(gòu)n地址變換機構(gòu)的任務(wù)是實現(xiàn)邏輯地址到物理地址的變換，即將邏輯地址中的頁號轉(zhuǎn)換為內(nèi)存中的物理塊號。精選課件分頁的邏輯地址結(jié)構(gòu)n分頁存儲

29、管理系統(tǒng)中，邏輯地址由頁號和頁內(nèi)位移組成。其結(jié)構(gòu)如下所示：n若A為邏輯地址，L為頁面大小，則：n頁號： P=int(A/L)n頁內(nèi)位移：W=A % L31 12 11 0 頁 號 P 頁 內(nèi) 位 移W精選課件基本地址變換機構(gòu)n頁表通常存放在內(nèi)存中，為了實現(xiàn)方便，系統(tǒng)中設(shè)置了一個頁表寄存器存放頁表在內(nèi)存的起始地址和頁表的長度。n進程未執(zhí)行時，頁表的起始地址和長度存放在PCB中。當(dāng)進程執(zhí)行時，才將頁表始址和長度存入頁表寄存器中。精選課件地址變換過程n分頁地址變換機構(gòu)自動地將邏輯地址分為頁號和頁內(nèi)位移；n將頁號與頁表長度進行比較，如果頁號超過了頁表長度，則表示本次所訪問的地址已超越進程的地址空間，系

30、統(tǒng)產(chǎn)生地址越界中斷；n若未出現(xiàn)越界，則由頁表始址和頁號計算出相應(yīng)頁表項的位置，從中得到該頁的物理塊號；n將物理塊號與邏輯地址中的頁內(nèi)位移拼接在一起，就形成了訪問主存的物理地址。精選課件分頁系統(tǒng)的地址變換機構(gòu)圖n注意這里的頁號字段？頁表寄存器頁表始址 頁表長度越界中斷邏輯地址 頁號（2） 頁內(nèi)位移（452）頁號 塊號2385101234 8 452物理地址頁表精選課件分頁地址變換例1n設(shè)頁面大小為1K字節(jié)，作業(yè)的0、1、2頁分別存放在第2、3、8塊中。則邏輯地址2500的頁號及頁內(nèi)地址為：n2500/1024=2（頁號）；2500 %1024452（頁內(nèi)地址）；n查頁表可知第2頁對應(yīng)的物理塊號為

31、8；n將塊號8與頁內(nèi)地址452拼接得到物理地址為：n810244528644。精選課件地址變換例2n一分頁系統(tǒng)中邏輯地址長度為16位，頁面大小為1KB，現(xiàn)有一邏輯地址0A6FH ，且第0、1、2、3頁依次存放在物理塊3、7、11、10中。n邏輯地址0A6FH的二進制表示如下：頁號 頁內(nèi)地址000010 1001101111 n由此可知邏輯地址0A6FH的頁號為2，該頁存放在第11號物理塊中，用十六進制表示塊號為B，所以物理地址為：n 1011 1001101111 ，即2E6FH。精選課件聯(lián)想存儲器聯(lián)想存儲器n因頁表放在主存中，故存取數(shù)據(jù)時CPU至少要訪問兩次主存。降低了內(nèi)存訪問速度。n為了提

32、高地址變換速度，可在地址變換機構(gòu)中增設(shè)一個具有并行查找能力的高速緩沖存儲器（又稱聯(lián)想存儲器或快表），用以存放當(dāng)前訪問的那些頁表項。 精選課件引入快表后的地址變換過程n地址變換機構(gòu)自動將頁號與快表中的所有頁號進行并行比較，若其中有與此匹配的頁號，則取出該頁對應(yīng)的塊號，與頁內(nèi)地址拼接形成物理地址。n若頁號不在快表中，則再到主存頁表中取出物理塊號，與頁內(nèi)地址拼接形成物理地址。n同時還應(yīng)將這次所查到的頁表項存入快表中，若快表已滿，則必須按某種原則淘汰出一個表項以騰出位置。精選課件具有聯(lián)想存儲器的地址變換n頁表與快表有何不同？頁表寄存器 頁表始址 頁表長度越界中斷邏輯地址 頁號 頁內(nèi)位移頁號 塊號 01

33、234 物理地址頁表頁號 塊號快表精選課件聯(lián)想存儲器的大小n由于成本關(guān)系，快表大小一般由832個表項組成。由于局部性原理，聯(lián)想存儲器的命中率可達80%-90% 。精選課件7.4.4 多級頁表及反向頁表多級頁表及反向頁表n現(xiàn)代計算機系統(tǒng)都支持非常大的邏輯地址空間，致使頁表很大，用連續(xù)空間存放頁表顯然不現(xiàn)實。n如邏輯地址32位，頁面大小4KB，則頁表項為1M，若每個頁表項占4字節(jié)，則頁表共需要4MB內(nèi)存空間。n解決方案：n用離散方式存儲頁表n僅將當(dāng)前需要的部分頁表項放在內(nèi)存，其余放在磁盤上，需要時調(diào)入。精選課件兩級頁表及多級頁表兩級頁表及多級頁表n將頁表再分頁，使每頁與內(nèi)存物理塊大小相同，并為它們

34、進行編號0、1、，同時還為離散存放的頁表建立一張頁表。n例如：32位地址可以劃分為31 22 21 12 11 0 一級頁號p1 二級頁號p2 頁內(nèi)地址w精選課件兩級頁表結(jié)構(gòu)第0頁頁表內(nèi)存空間一級頁表 200020242700 2 7 0123456785901411012n 0 1 2 1023 85 90 第1頁頁表 0 1 21023 1411 0 1 21023第n頁頁表精選課件具有兩級頁表的地址變換過程具有兩級頁表的地址變換過程n利用邏輯地址中的一級頁號作為索引訪問一級頁表，找到第二級頁表的起始地址，n再利用第二級頁號找到指定頁表項，從中取出塊號與頁內(nèi)地址拼接形成物理地址。精選課件具

35、有兩級頁表的地址變換機構(gòu)具有兩級頁表的地址變換機構(gòu) 第一級頁表寄存器邏輯地址+二級頁表一級頁表 b w物理地址一級頁號 二級頁號 頁內(nèi)地址 p1 p2 wb精選課件多級頁表n對兩級頁表進行擴充，便可得到三級、四級或更多級的頁表。n多級頁表的實現(xiàn)方式與兩級頁表類似。精選課件反向頁表n現(xiàn)代操作系統(tǒng)一般允許大邏輯地址空間，如232，這使得頁表太大，為解決頁表占用大量存儲空間的問題，引入了反向頁表。n反向頁表為每個物理塊設(shè)置一個頁表項，并將它們按物理塊號大小排序，表項內(nèi)容為頁號及其隸屬進程的標(biāo)識號。精選課件反向頁表地址變換過程n利用進程標(biāo)識號及頁號檢索反向頁表，若找到相應(yīng)的頁表項，則將其物理塊號與頁內(nèi)

36、地址拼接；否則請求調(diào)入該進程相應(yīng)頁，在無調(diào)頁功能的系統(tǒng)中則出錯。n由于反向頁表中沒有存放進程中尚未調(diào)入頁，因此必須為每個進程建立一張傳統(tǒng)頁表并存放在外存中，當(dāng)所訪問頁不在內(nèi)存時使用這張頁表。頁表中包含各頁在外存的地址。精選課件反向頁表的地址變換邏輯地址邏輯地址進程標(biāo)識號進程標(biāo)識號 頁號頁號反向頁表反向頁表 b w物理地址物理地址 頁號頁號 頁內(nèi)地址頁內(nèi)地址 p w pid ppid p進程標(biāo)識號進程標(biāo)識號pid 0 1 2 bn n精選課件反向頁表的不足n反向頁表查找慢：因為進程號及頁號不能作為索引，查找時必須在整個反向頁表中進行。n解決辦法：n將常用頁表項存入快表n用散列函數(shù)存放反向頁表精選

37、課件7.4.5 存儲保護n分頁存儲管理采用兩種方式保護內(nèi)存：n地址越界保護：頁表長度與邏輯地址中的頁號比較n存取控制保護：在頁表中增加保護位精選課件7.5 分段管理n由于分頁按物理單位進行，沒有考慮程序段的邏輯完整性，給程序段的共享和保護帶來不便，另外動態(tài)鏈接及段的動態(tài)增長也要求以邏輯上完整的程序段為單位管理。精選課件7.5.1 分段管理的原理n在分段存儲管理系統(tǒng)中，作業(yè)的地址空間由若干個邏輯分段組成，每個分段是一組邏輯意義相對完整的信息集合，每個分段都有自己的名字，每個分段都從0開始編址并采用一段連續(xù)的地址空間。n在進行存儲分配時，以段為單位分配內(nèi)存，每段分配一個連續(xù)的內(nèi)存區(qū)，但各段之間不要

38、求連續(xù)。精選課件作業(yè)的地址空間是二維的n作業(yè)的地址空間分為多段，每段都從0開始編址，故地址是二維的。 01K 08000600分段MAIN（主程序）分段X（子程序）分段A（數(shù)據(jù)）精選課件分段系統(tǒng)的邏輯地址結(jié)構(gòu)n該地址結(jié)構(gòu)最多允許多少分段?每段最大長度為多少?n該地址結(jié)構(gòu)允許作業(yè)最多有64K個段，每段的最大長度為64KB。31 16 15 0 段 號 S 段 內(nèi) 位 移 W精選課件7.5.2 分段存儲管理的實現(xiàn)n為了實現(xiàn)從邏輯地址到物理地址的變換，必須為每個進程建立一個段表，用來記錄每段在內(nèi)存的起始地址及相關(guān)信息。其中每個表項描述一個分段的信息，至少包含：n段號n段長n段在內(nèi)存的起始地址n其他信

39、息n段表一般存放在內(nèi)存。精選課件段表的作用內(nèi)存空間作業(yè)的地址空間段表 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為實現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換，在系統(tǒng)中設(shè)置了段表寄存器，用于存放段表始址和段表長度。n為了提高內(nèi)存的訪問速度，也可以使用快表。精選課件地址變換過程n進行地扯變換時，系統(tǒng)將邏輯地址中的段號S與段表長度進行比較，若段號超過了段表

40、長度則產(chǎn)生越界中斷；n否則根據(jù)段表始址和段號計算出該段對應(yīng)段表項的位置，從中讀出該段在內(nèi)存的起始地址，n然后再檢查段內(nèi)地址是否超過該段的段長，若超過則同樣發(fā)出越界中斷信號；n若未越界，則將該段的起始地址與段內(nèi)位移相加，從而得到了要訪問的物理地址。精選課件地址變換機構(gòu)圖段表寄存器 段表始址 段表長度越界中斷邏輯地址 段號（2）段內(nèi)位移（100）段號 段長 始址 1K 6K800 4K600 8K012物理地址段表8292精選課件分段地址變換例n設(shè)作業(yè)分為3段，0、1、2段長度分別為1K、800、600，分別存放在內(nèi)存6K、4K、8K開始的內(nèi)存區(qū)域。n邏輯地址（2，100）的段號為2，段內(nèi)位移為1

41、00。n查段表可知第2段在內(nèi)存的起始地址8K。n將起始地址與段內(nèi)位移相加，8K1008292，物理地址為8292。精選課件分段與分頁的主要區(qū)別分段與分頁的主要區(qū)別n分頁管理與分段管理有許多相似之處，但兩者在概念上也有很多區(qū)別，主要表現(xiàn)在：n頁是信息的物理單位，是為了減少內(nèi)存碎片及提高內(nèi)存利用率，是系統(tǒng)管理的需要。段是信息的邏輯單位，它含有一組意義相對完整的信息，分段的目的是為了更好地滿足用戶的需要。n頁的大小固定且由系統(tǒng)決定，由硬件把邏輯地址劃分為頁號和頁內(nèi)地址兩部分。段的長度不固定且由用戶所編寫的程序決定，通常由編譯系統(tǒng)在對源程序進行編譯時根據(jù)信息的性質(zhì)來劃分。n分頁系統(tǒng)中作業(yè)的地址空間是一維的，分段系統(tǒng)中作業(yè)的地址空間是二維的。精選課件7.5.3