計算機(jī)操作系統(tǒng)許曰濱版第五章

1、計算機(jī)操作系統(tǒng)原理存儲管理概述 存儲管理必須實現(xiàn)的4大功能 存儲管理用到的數(shù)據(jù)結(jié)構(gòu) 連續(xù)存儲管理方法（單分區(qū)、多分區(qū)）離散存儲管理方法（分頁、分段、段頁）存儲器外存儲器永久存放信息容量大速度慢內(nèi)存儲器容量有限速度快內(nèi)存儲器是一種隨機(jī)存儲器，各種程序只有裝入內(nèi)存儲器才能運行需要解決什么問題？如何分配？如何回收？如何共享？如何擴(kuò)充？5.1 概述內(nèi)存儲器（Memory），簡稱內(nèi)存由存儲體和輔助電路組成存儲體中包含若干存儲單元，每個存儲單元可存放一條獨立信息讀、寫數(shù)據(jù)以存儲單元為基本單位存儲單元也成為“內(nèi)存地址”SDRAM時代DDR時代DDR2時代DDR3時代DDR4時代7內(nèi)存儲器的組成內(nèi)存儲器的組成

2、內(nèi)內(nèi)存存儲儲器器的的組組成成圖圖 85.1.2 5.1.2 存儲管理的主要功能存儲管理的主要功能存儲管理模塊的功能是對內(nèi)存用戶區(qū)的存儲管存儲管理模塊的功能是對內(nèi)存用戶區(qū)的存儲管理，主要概括為以下理，主要概括為以下4 4個方面?zhèn)€方面：1.1. 地址重定位地址重定位2.2.內(nèi)存分配與回收內(nèi)存分配與回收3.3.內(nèi)存共享與保護(hù)內(nèi)存共享與保護(hù)4.4.內(nèi)存容量擴(kuò)充內(nèi)存容量擴(kuò)充 9邏輯地址：邏輯地址：是用戶在其程序中使用的一種地址。由邏輯地址構(gòu)成的地址空間稱邏輯地址空間，其首地址是0號地址，其它指令的地址都是相對于0號地址排定的。物理地址：是存儲單元的實際物理單元地址。一、一、地址重定位地址重定位 將邏輯地

3、址轉(zhuǎn)換成內(nèi)存的物理地址的過程，稱為地址地址“重定位重定位”，地址重定位可分為靜態(tài)重定位靜態(tài)重定位和動態(tài)重定位動態(tài)重定位兩種方式。靜態(tài)重定位這是在程序運行前，由“裝載”過程實現(xiàn)的重定位。當(dāng)把一個程序裝入內(nèi)存時，對用戶代碼中使用的邏輯地址作適當(dāng)調(diào)整，轉(zhuǎn)換成內(nèi)存的物理地址轉(zhuǎn)換完成后，再將用戶代碼裝載到該物理空間中其后，程序使用的地址空間將不再改變動態(tài)重定位采用這種方式的硬件結(jié)構(gòu)中專門設(shè)置一個“重定位寄存器”，當(dāng)存儲管理系統(tǒng)為作業(yè)分配了一個內(nèi)存區(qū)域后，就把該區(qū)的起始地址放到重定位寄存器中程序的物理地址將是邏輯地址和重定位寄存器的內(nèi)容之和12動態(tài)重定位需要硬件支持允許執(zhí)行過程中實現(xiàn)操作數(shù)的地址轉(zhuǎn)換保持原

4、有邏輯空間關(guān)系可以在內(nèi)存中浮動靜態(tài)重定位無需硬件支持 不允許。需要修改用戶程序原有的邏輯關(guān)系被破壞要求程序放在連續(xù)的存儲空間中二、內(nèi)存分配與回收 在多道程序環(huán)境下，當(dāng)系統(tǒng)需要裝載一個用戶作業(yè)時，作業(yè)調(diào)度程序?qū)⒋鎯芾砟K啟動起來，按某種方式分配存儲空間，并將程序代碼裝入。內(nèi)存的分配有靜態(tài)分配和動態(tài)分配兩種方式。靜態(tài)分配在進(jìn)程執(zhí)行前實施的內(nèi)存空間分配。在這之后，系統(tǒng)不再接受進(jìn)程的申請，也不允許進(jìn)程在內(nèi)存中移動（變更所占空間）動態(tài)分配進(jìn)程在運行過程中實施的內(nèi)存空間分配。也就是說，系統(tǒng)允許進(jìn)程在運行過程中隨時申請內(nèi)存空間三、內(nèi)存的共享與保護(hù) 多道程序環(huán)境中，多個用戶作業(yè)都對內(nèi)存空間提出申請，為提高內(nèi)

5、存利用率，應(yīng)該對內(nèi)存空間實現(xiàn)共享。共享包括兩個方面的含義：共享內(nèi)存儲器資源，讓多個進(jìn)程同時進(jìn)入內(nèi)存區(qū)域，共享同一個存儲器共享內(nèi)存儲器的某些區(qū)域，即允許兩個或多個進(jìn)程訪問內(nèi)存中的同一段程序或數(shù)據(jù) 內(nèi)存保護(hù)上下界存儲保護(hù)技術(shù)保護(hù)鍵法上下界存儲保護(hù)技術(shù)CPU中設(shè)有一對上下界寄存器，登記當(dāng)前進(jìn)程所占內(nèi)存空間的上下界地址對內(nèi)存進(jìn)行訪問時，首先做地址碼的合法性檢查。若程序中訪問的地址碼，不超出上下界寄存器所規(guī)定的范圍，則訪問是合法的；否則視為非法。對于程序的非法地址訪問，硬件將轉(zhuǎn)入“越界中斷”處理每個進(jìn)程的PCB中設(shè)置上下界寄存器保護(hù)域，存放進(jìn)程的上下界地址。當(dāng)該進(jìn)程被調(diào)度時，此兩項地址將與其它現(xiàn)場保護(hù)信

6、息（如程序狀態(tài)字PSW、程序計數(shù)器PC等）一起置入CPU中四、內(nèi)存容量擴(kuò)充內(nèi)存容量是有限的內(nèi)存擴(kuò)充不是硬件上的擴(kuò)充，而是用存儲管理軟件來實現(xiàn)的邏輯擴(kuò)充例如，當(dāng)有一個比內(nèi)存容量還要大的程序要求運行時，內(nèi)存不能一下子存儲作業(yè)的全部程序，操作系統(tǒng)可采用“虛擬存儲”技術(shù)，在外存的輔助下實現(xiàn)內(nèi)存容量擴(kuò)充覆蓋技術(shù)，對換技術(shù)，虛擬存儲技術(shù)等（第6章） 5.1.3 存儲管理的數(shù)據(jù)結(jié)構(gòu)設(shè)置一些數(shù)據(jù)結(jié)構(gòu)等級內(nèi)存的使用情況常見的數(shù)據(jù)結(jié)構(gòu)有：內(nèi)存分配表、空閑區(qū)表和位示圖等內(nèi)存分配表MAT，Memory Allocation Table內(nèi)容包括各分區(qū)的分區(qū)號、起始地址、長度和占用標(biāo)志等分區(qū)號：每個分區(qū)都有一個編號，用以

7、區(qū)別不同分區(qū)起始地址：分區(qū)的起始地址，即首地址長度：分區(qū)的總長，一般以KB為單位占用標(biāo)志：記錄分區(qū)的使用狀態(tài)。0為空閑，非0位占用空閑區(qū)表/鏈記錄內(nèi)存空閑區(qū)狀況為什么有了分配表了，還需要空閑區(qū)表？空閑區(qū)和分配區(qū)交叉在一起查找空閑區(qū)就得從頭逐一掃描，費時將空閑區(qū)組成一個鏈表，一個結(jié)點代表一個空閑區(qū) 空閑區(qū)表中各空閑區(qū)可按地址順序來排列，也可按尺寸大小來組織。當(dāng)系統(tǒng)進(jìn)行內(nèi)存分配時，進(jìn)行的處理是：通過空閑區(qū)表/鏈，快速搜索內(nèi)存的空閑區(qū)從中找出最合適的分區(qū)分配出去將該結(jié)點從鏈上刪除當(dāng)需要回收某塊被釋放的區(qū)域時，系統(tǒng)處理過程為：按其地址或者大小在鏈中找到合適的位置插入一個新結(jié)點如果存在相鄰的空閑區(qū)，則需

8、要的話可將相鄰空閑區(qū)合并位示圖 位示圖是存儲器的一種存儲空間映像，系統(tǒng)可以根據(jù)位圖來進(jìn)行存儲空間的管理5.1.4 存儲管理的主要方法單一連續(xù)區(qū)方式 - 內(nèi)存全部空間只存放一個作業(yè)分區(qū)方式 - 內(nèi)存被分成多個分區(qū)，每個分區(qū)放一個作業(yè)，每瞬間可有多個作業(yè)駐留內(nèi)存分頁方式 - 內(nèi)存被劃分成多個等長的存儲塊，可有多個作業(yè)駐留內(nèi)存分段方式 按照段的長度分別分配內(nèi)存空間，可有多個作業(yè)駐留內(nèi)存。配合分頁式，構(gòu)成段頁式管理模式分配的內(nèi)存空間是連續(xù)的分配的內(nèi)存空間是連續(xù)的分配的內(nèi)存空間是離散的分配的內(nèi)存空間是離散的5.2 單一連續(xù)區(qū)管理單連續(xù)區(qū)存儲管理方式，把內(nèi)存的用戶區(qū)視為一個獨立的連續(xù)存儲區(qū)，任何時刻只將它

9、分配給一個作業(yè)使用。這種存儲管理非常簡單，適用于單用戶單任務(wù)系統(tǒng)（如，MS-DOS操作系統(tǒng)的早期版本）。單一連續(xù)區(qū)的內(nèi)存分配如果內(nèi)存的用戶區(qū)小于請求的存儲空間n，將分配失敗信息反饋給申請者結(jié)束將程序加載到內(nèi)存用戶區(qū)中將分配成功的信息反饋給申請者單一連續(xù)區(qū)的內(nèi)存回收將內(nèi)存中的程序和數(shù)據(jù)調(diào)出去對用戶區(qū)進(jìn)行必要的清理和初始化操作單一連續(xù)區(qū)管理的缺點CPU的利用率不高。因為任何時刻最多只有一個程序獨占內(nèi)存，無論在該程序執(zhí)行過程中，還是CPU等待I/O時都不能讓其他用戶使用。內(nèi)存空間浪費嚴(yán)重。進(jìn)入系統(tǒng)運行的大多數(shù)用戶作業(yè)的尺寸不可能正好等于整個內(nèi)存用戶區(qū)的大小，當(dāng)作業(yè)所要求的存儲空間較小時，剩余較大的空

10、白區(qū)未被利用，只能白白浪費。外設(shè)利用率較低。計算機(jī)的外部設(shè)備（比如，輸入/輸出設(shè)備）均被單個用戶所占用，因此利用率不高。不論該用戶是否使用，其它用戶都無法使用。5.3 分區(qū)管理建立在單一連續(xù)區(qū)的基礎(chǔ)上適用于多道程序運行環(huán)境思想：將內(nèi)存用戶區(qū)劃分成多個存儲分區(qū)（除操作系統(tǒng)所占空間外），每一個分區(qū)可以裝入一個進(jìn)程，內(nèi)存中就可以同時容納多個進(jìn)程固定分區(qū)思想：將內(nèi)存用戶區(qū)劃分成若干固定長度的存儲塊進(jìn)行分配。分區(qū)的劃分過程通常在系統(tǒng)生成時完成。各分區(qū)長度不要相等一、內(nèi)存的分配與回收分區(qū)號分區(qū)號起始地址起始地址長度長度占用標(biāo)志占用標(biāo)志0 04k4k6k6k未分未分1 110k10k2k2k已分已分2 21

11、2k12k15k15k已分已分3 327k27k34k34k未分未分分配從頭到尾掃描內(nèi)存分配表，找到滿足需求的分區(qū)將標(biāo)志設(shè)為“已分”將分區(qū)的起始地址返回給用戶回收從頭到尾掃描內(nèi)存分配表，找到該分區(qū)在表中的位置將其占用標(biāo)志設(shè)為“未分”二、內(nèi)存保護(hù)設(shè)置“上界寄存器”和“下界寄存器”某個進(jìn)程運行時，系統(tǒng)將該進(jìn)程所占的物理存儲區(qū)的上限和下限地址分別送入這兩個寄存器上三、固定分區(qū)的缺點浪費存儲空間，產(chǎn)生很多內(nèi)碎片內(nèi)碎片：作業(yè)獲得的空間大于需求的空間時多出來的一小部分用戶根本不需要的空閑區(qū)動態(tài)分區(qū)思想：系統(tǒng)不預(yù)先劃分固定分區(qū)，而是在裝入一個作業(yè)時，根據(jù)該用戶作業(yè)的實際需求量劃分出一個分區(qū)給它使用。若無足夠

12、大的連續(xù)空閑區(qū)供作業(yè)使用，則該作業(yè)只好等待一、內(nèi)存的分配與回收動態(tài)分區(qū)分配算法可描述如下：（1）從頭到尾掃描空閑分區(qū)表，找到一個能滿足需求的空閑分區(qū)MATi。（2）若MATi（長度）= L，則：MATi（占用標(biāo)志）=“已分”，轉(zhuǎn)（4）。（3）若MATi（長度）L，則：-1 L0 =MATi（長度）-L。 -2 MATi（長度）=L；MATi（占用標(biāo)志）=“已分”。 -3 在內(nèi)存分配表的下一個位置插入新行MATi+1。 -4 MATi+1（起始地址）=MATi（起始地址）+L。 -5 MATi+1（長度）=L0。 -6 MATi+1（占用標(biāo)志）=“未分”。（4）結(jié)束。 當(dāng)用戶歸還一個起始地址為M

13、的分區(qū)時，系統(tǒng)回收應(yīng)做的處理是：如果這個空閑區(qū)與其它空閑區(qū)相鄰，則系統(tǒng)把它們合并成一個連續(xù)的大空閑區(qū)，以適應(yīng)大作業(yè)的存儲需求。下面是回收過程：（1）在內(nèi)存分配表中找到該分區(qū)的位置MATi。（2）MATi（占用標(biāo)志）=“未分”。（3）若MATi-1（占用標(biāo)志）=“未分”&MATi+1（占用標(biāo)志）=“未分” ，則: 3個相鄰空閑區(qū)合并為一個。否則：（4）若MATi-1（占用標(biāo)志）=“未分” ，則: 2個相鄰空閑區(qū)合并為一個。否則：（5）若MATi+1（占用標(biāo)志）=“未分” ，則: 2個相鄰空閑區(qū)合并為一個。（6）結(jié)束。5.3.3 分配算法算法負(fù)責(zé)管理將哪個分區(qū)分配出去：首次適應(yīng)算法（Fir

14、st Fit）循環(huán)首次適應(yīng)算法(CFF, Circle First Fit)最佳適應(yīng)算法(BF, Best Fit)最壞適應(yīng)算法（WF, Worst Fit）首次適應(yīng)算法 首次適應(yīng)算法也稱為最早適應(yīng)算法。系統(tǒng)將內(nèi)存分區(qū)按地址遞增順序登記到內(nèi)存分配表（或其它數(shù)據(jù)結(jié)構(gòu)）中。每次進(jìn)行內(nèi)存分配時，系統(tǒng)根據(jù)進(jìn)程申請空間的大小，從頭到尾順序掃描內(nèi)存分配表（或其它數(shù)據(jù)結(jié)構(gòu)），從中找到的第1個能夠滿足要求的空閑區(qū)，就立即分配出去。首次適應(yīng)算法產(chǎn)生大量碎片每次內(nèi)存分配時，都是從頭到尾順序查找，使地段地址空間使用頻繁，而高端地址空間較少使用循環(huán)首次適應(yīng)算法（CFF）思想：每次存儲分配總是從上次分配的位置開始，向尾

15、部查找。查到的第1個可滿足用戶需求的空閑空間，就立即分配給用戶。當(dāng)查到MAT（或空閑鏈表）的尾部仍然沒有合適的，則轉(zhuǎn)到頭部重新開始46 下面的例子中，MAT有8個分區(qū)，其中帶陰影的分區(qū)是已經(jīng)被占用的。假設(shè)上次分配的是1#分區(qū)，則當(dāng)前的指針位置是2#分區(qū)。如果有一個用戶請求40KB，則系統(tǒng)將按順時針方向，找到5#分區(qū)分配給用戶。 最佳適應(yīng)算法（BF） 在內(nèi)存分配時，從空閑區(qū)表中找到一塊滿足進(jìn)程需求的最小空閑區(qū)分配給它，使剩余空間最小。這種做法減少了將大空閑區(qū)進(jìn)行多次分割造成的空間浪費。但容易形成一些很小的碎片無法使用，同樣不能提高內(nèi)存利用率。另外，每次分配時，都要對整個內(nèi)存區(qū)進(jìn)行從頭到尾的搜索，

16、系統(tǒng)開銷較大。最壞適應(yīng)法（WF） 在進(jìn)行內(nèi)存分配時，從空閑區(qū)表中找到一個滿足長度要求的最大空閑區(qū)進(jìn)行分配，使得剩下來的空閑區(qū)不致太小，還可以利用。這種算法部分地緩解了由外碎片引起的浪費，適合于中小作業(yè)的運行，但對大作業(yè)的運行是不利的。與最佳適應(yīng)算法一樣，每次分配需要搜索一遍內(nèi)存，效率會受到一定影響。5.3.4 可重定位動態(tài)分區(qū)管理 動態(tài)分區(qū)管理方式靈活，缺陷是外碎片帶來的空間浪費。要周期性地清除外碎片將動態(tài)分區(qū)技術(shù)與重定位技術(shù)相結(jié)合就可以解決這一問題。 動態(tài)重定位技術(shù)是允許進(jìn)程在內(nèi)存中浮動的。當(dāng)內(nèi)存中出現(xiàn)一些外部碎片后，可以將各個進(jìn)程進(jìn)行“搬家”，讓它們移動到內(nèi)存的一端，使所有的外部碎片移動到

17、另一端。這樣就可使若干零星的碎片合并成一個大的空閑區(qū)了。這一過程也稱進(jìn)程浮動。 進(jìn)程浮動的時機(jī)：若內(nèi)存可用空間總量充足，但因充滿了外部碎片不能滿足一個用戶的需求，可進(jìn)行浮動。5.3.5 伙伴系統(tǒng) 在伙伴系統(tǒng)中，一個內(nèi)存分區(qū)的大小是可變的。系統(tǒng)初始時，整個用戶空間s被看作是一個分區(qū)。當(dāng)有一個用戶請求的空間尺寸為p時，BS的準(zhǔn)則是： （1）若s=p s/2，則將整個分區(qū)分給用戶使用。 （2）否則，將分區(qū)分成大小相等的兩個伙伴，每一個的尺寸為s/2。 （3）若s/2=p s/4，則將兩個伙伴分區(qū)中的一個分給用戶使用。 （4）否則，將一個伙伴再分成大小相等的兩個小伙伴，每個小伙伴的尺寸為s/4。 （5

18、）若s/4=p s/8，則將兩個小伙伴分區(qū)中的一個分給用戶使用。按照這種思想將分區(qū)不斷分裂，直到分配一個適合用戶使用的空間為止?；锇橄到y(tǒng)的分配過程可構(gòu)成一棵二叉樹，樹中的葉結(jié)點表示當(dāng)前的分區(qū)情況。進(jìn)程A需要100K；進(jìn)程B需要50K；進(jìn)程C需要100K；進(jìn)程A釋放所占內(nèi)存進(jìn)程D需要20K；進(jìn)程D釋放所占內(nèi)存伙伴系統(tǒng)的特點允許保留部分內(nèi)碎片分區(qū)尺寸隨用戶需求不斷變化內(nèi)碎片不會太大5.4 分頁存儲管理分頁存儲管理，是按照程序頁面進(jìn)行管理的一種方法。內(nèi)存的用戶空間被劃分為一些大小相等的存儲塊，通常稱為“幀”（frame），或“頁框”。系統(tǒng)把每個進(jìn)程劃分成與幀同樣大小的塊，通常稱為頁面（page）。讓

19、每個頁面存入一個幀中。當(dāng)某個進(jìn)程申請內(nèi)存空間時，系統(tǒng)根據(jù)進(jìn)程的長度計算出它所需要的幀數(shù)，然后，掃描MAT，選擇內(nèi)存中的若干可用幀分配給該進(jìn)程，整個分配一次性完成?？梢詫⑦M(jìn)程的所有頁面分配到互不連續(xù)的若干幀中，因此是一種離散空間分配形式。5.4.1 頁面設(shè)系統(tǒng)的用戶區(qū)有10個幀，幀長度為1K，進(jìn)程A、B、C各需要3K。它們依次進(jìn)入內(nèi)存，占據(jù)9個幀的位置。此后，進(jìn)程B運行結(jié)束釋放所占的內(nèi)存空間，系統(tǒng)接納了進(jìn)程D。D需要4K內(nèi)存，系統(tǒng)將它放在4個幀中。分配過程如圖。提出問題：每一幀分配什么尺寸比較合適？分頁管理和固定分配一樣，存在內(nèi)碎片平均每個進(jìn)程的空間浪費為L/2一般來說，幀的長度為1-4kb，此

20、長度通常與進(jìn)程的平均長度、內(nèi)存空間尺寸以及數(shù)據(jù)交換速度有關(guān)5.4.1 2 頁面劃分 為了使內(nèi)存訪問能夠準(zhǔn)確定位，系統(tǒng)需要將用戶程序代碼劃分為若干頁面，使原本一維的地址空間（也就是線性空間）分成低端地址和高端地址兩部分。低端地址部分，作為頁內(nèi)的偏移量（即頁內(nèi)地址）；高端地址部分作為頁號。 比如，系統(tǒng)規(guī)定頁面的長度為1024個字節(jié)，則頁內(nèi)地址可用10個二進(jìn)制位表示（1024=210）表示。若機(jī)器的地址碼是16位二進(jìn)制數(shù)時，其中高6位代表頁號，低10位代表頁內(nèi)地址。即： 6位位10位位頁號頁號頁內(nèi)地址頁內(nèi)地址5.4.1 3 頁表為了保證程序的正確運行，分頁管理機(jī)制應(yīng)為每個進(jìn)程建立一個數(shù)據(jù)結(jié)構(gòu)頁表PT

21、（Page Table）。頁表中登記進(jìn)程各頁面對應(yīng)的幀號，供地址映射使用。 頁號幀號權(quán)限00R14R25W37R/W5.4.2 頁面分配（1）計算請求者需要的總幀數(shù)N。（2）查位圖，若找不到足夠的空閑幀，編制“分配失敗”報告返回。（3）索取一個空閑頁表PT。（4）從位圖中找出N個為0位，計算出對應(yīng)的幀號，填入PT。（5）將這些位改為1。（6）將PT起始地址填入進(jìn)程的PCB中。（7）結(jié)束。645.4.35.4.3 頁面共享頁面共享 1 1、可重入技術(shù)、可重入技術(shù) 在多道程序運行環(huán)境中，可重入技術(shù)是一項很有用的技術(shù)。它可以幫操作系統(tǒng)解決多任務(wù)共享同一程序的問題。一個可共享程序不能讓指令和變量交織在

22、一起，必須讓程序和變量分開。 讓程序中不發(fā)生變化的部分指令代碼，單獨存入一個程序體中，形成所謂的“純碼”。讓程序的操作對象存放（中間）結(jié)果的變量由各調(diào)用者自備。這樣，多任務(wù)共享同一個程序就成為可能的了。 652 2、共享的實現(xiàn)、共享的實現(xiàn) 頁面共享頁面共享，指的是一個頁面同時供多個進(jìn)程使用。帶來了一個很重要的問題，即用戶訪問權(quán)限問題。 系統(tǒng)中提供的共享頁面，可能具有不同的調(diào)用方式。例如，對于“共享程序”頁面，通常只允許執(zhí)行，不允許寫入；而對于“共享數(shù)據(jù)”頁面，可能既允許一部分進(jìn)程讀出，也允許一部分進(jìn)程寫入。 比如，內(nèi)存中的共享頁有兩個，它們分別存在第3幀和第4幀中。內(nèi)存中的兩個進(jìn)程P1和P2，

23、按下一頁圖的方式共享它們?？偨Y(jié)分頁式存儲管理離散存儲，利于大進(jìn)程裝入只有很少的頁內(nèi)碎片，提高內(nèi)存利用率DS：位示圖、頁表動態(tài)地址重定位 邏輯地址 物理地址 一維、二維 二維、一維頁面共享不易實現(xiàn)5.5 分段管理技術(shù)模塊化和層次化的程序結(jié)構(gòu)逐漸成為設(shè)計的主流應(yīng)用程序中的每個功能模塊有一個獨立的段名，每個段含有若干條命令或數(shù)據(jù)段，指的是一組邏輯信息，如主程序、過程、函數(shù)或者數(shù)組等。例子：project ara和LG G55.5.1 分段管理的基本原理 在結(jié)構(gòu)程序設(shè)計中，用戶的源程序使用的是二維地址。段中訪問一個變量時，地址形式為：。例如，一個進(jìn)程P包括3個程序段：Main（主段）、Sub1（子段1

24、）和Sub2（子段2）。圖給出各個段之間的調(diào)用關(guān)系。分段管理和分頁管理在調(diào)用方式上有差別段的長度不同，為各個段分配等長的存儲空間是不現(xiàn)實的所以，考慮了類似動態(tài)分區(qū)的分配機(jī)制分頁 類似于固定分區(qū)，分段 類似于動態(tài)分區(qū)容易產(chǎn)生段之間的小碎片在分段機(jī)制中，一個進(jìn)程的地址空間可以包含以下不同的段：代碼段數(shù)據(jù)段堆棧段內(nèi)存共享段5.5.2 段表 與分頁管理一樣，分段管理也是一種支持離散空間分配的機(jī)制。為了使程序能夠正常運行，系統(tǒng)也必須能夠定位各個段的物理位置。為此，應(yīng)當(dāng)仿效分頁管理系統(tǒng)的做法，為進(jìn)程建立地址映射的數(shù)據(jù)結(jié)構(gòu)段表。段表ST，是用來記錄各個段地址映射關(guān)系的表格，每個進(jìn)程有一張。各個分段在內(nèi)存空間

25、中的對應(yīng)位置都登記在段表中。 例：一個進(jìn)程含有3個分段：Main、Sub1和Sub2（其中Main是主段），長度分別為2K、4K和1K。系統(tǒng)需要分配3塊的空間分別存放它們。比如分配的3塊不連續(xù)的存儲區(qū)，首地址分別為：14K、3K和7K。一般來說，分段數(shù)量不會很多一般采用大小不等的分段方式分配內(nèi)存空間時，一并為進(jìn)程制作一個段表，駐留在內(nèi)存中那么，內(nèi)存使用情況使用什么數(shù)據(jù)結(jié)構(gòu)比較合適？MAT還是空閑分區(qū)表？這里用的MAT和動態(tài)多分區(qū)中的MAT表有何區(qū)別？一個段相當(dāng)于一個分區(qū)，一個進(jìn)程離散成多個段裝入多個不連續(xù)的分區(qū)中5.5.3 地址變換與分頁管理類似，區(qū)別在于段是信息的邏輯單位，由用戶劃分；頁是信

26、息的物理單位，長度是固定的，和用戶無關(guān)分段管理的地址變換是在硬件的協(xié)助下完成需要段表基址寄存器STBR和段表長度寄存器STLR76邏輯地址邏輯地址: : 二維二維 段號段號 段內(nèi)地址段內(nèi)地址物理地址物理地址: : 一維物理地址一維物理地址查查段段表表硬件支持硬件支持: : CPUCPU設(shè)設(shè)段表控制寄存器段表控制寄存器，記錄當(dāng)前進(jìn)程的段記錄當(dāng)前進(jìn)程的段表的起始地址和段表的起始地址和段表長度表長度段段起起始始地地址址累加累加程序運行中的地址變換過程如下：(1) 提取邏輯地址中的“段號”。(2) 比較段號與STLR的段長度。如果超出段表長度，則返回“內(nèi)存定位錯誤”，終止進(jìn)程的運行。(3) 從STBR

27、中給出的段表首址開始，以段號為索引查找該進(jìn)程對應(yīng)的段表，得到欲訪問段的首地址。(4) 取出欲訪問段的首地址，加上邏輯地址中的偏移量得到物理地址。5.5.4 分段保護(hù)與分享 分段管理模式下的信息保護(hù)分兩級。第一級是防止進(jìn)程發(fā)生超出存儲空間的訪問，第二級是阻止進(jìn)程超出訪問權(quán)限的讀寫。這里主要介紹一下第一級保護(hù)。共享：分段存儲管理可以方便地實現(xiàn)內(nèi)存信息的共享。由于段具有完整的邏輯意義，因此非常適合按段進(jìn)行訪問。如果多個用戶進(jìn)程需要共享內(nèi)存中的某些代碼段或數(shù)據(jù)段時，可將內(nèi)存中共享段的起始地址及長度，填入這些進(jìn)程的段表當(dāng)中，就可共享一個邏輯上完整的段信息了?！岸巍迸c“頁”分段管理方式中的地址變換與分頁管

28、理方式中的十分相似。不過，段是信息的邏輯單位，是由用戶自己劃分的，其大小是隨機(jī)的；而頁是信息的物理單位，長度是固定的，用戶根本看不到頁的劃分。5.5.5 段頁式管理 這種管理方式可以看作是分段與分頁兩項管理技術(shù)的結(jié)合。系統(tǒng)為一個含有多分段的進(jìn)程分配內(nèi)存時，首先為這些分段建立段表，將各段長度填入表中。接下來為每個段分配地址空間。在這種系統(tǒng)中，各分段有一個頁表，其首地址存放在段表中。比如某個進(jìn)程有3個段，各自對應(yīng)一個頁表。假設(shè)內(nèi)存中的幀長為2K，段表結(jié)構(gòu)和頁表結(jié)構(gòu)可通過圖所示的形式給出。5.5.5 段頁式管理 這種管理方式可以看作是分段與分頁兩項管理技術(shù)的結(jié)合。系統(tǒng)為一個含有多分段的進(jìn)程分配內(nèi)存時

29、，首先為這些分段建立段表，將各段長度填入表中。接下來為每個段分配地址空間。在這種系統(tǒng)中，各分段有一個頁表，其首地址存放在段表中。比如某個進(jìn)程有3個段，各自對應(yīng)一個頁表。假設(shè)內(nèi)存中的幀長為2K，段表結(jié)構(gòu)和頁表結(jié)構(gòu)可通過圖所示的形式給出。84 這種系統(tǒng)的地址變換比較復(fù)雜。系統(tǒng)的硬件支持是，在處理機(jī)內(nèi)部設(shè)有段表控制寄存器及地址生成邏輯。程序中的邏輯地址仍然是二維地址：。其中的偏移量將被分成兩部分：頁號和頁內(nèi)偏移量。這樣一來，地址部分被當(dāng)作三維地址來處理：855.6 關(guān)于分頁討論頁面尺寸 設(shè)某系統(tǒng)中的用戶區(qū)有M個字節(jié)，規(guī)定的頁面尺寸為P個字節(jié)。假定進(jìn)入系統(tǒng)的進(jìn)程長度平均為S個字節(jié)，則 內(nèi)存中可容納的進(jìn)

30、程數(shù)為M/S個； 每個進(jìn)程的頁表長度為S/P字節(jié)（設(shè)每一項只占1個字節(jié)）； 系統(tǒng)為了支持分頁管理機(jī)制，需要開辟的頁表區(qū)總?cè)萘繛镾/P*M/S字節(jié)。 另外，每個進(jìn)程平均浪費P/2字節(jié)，全部進(jìn)程總的浪費為M/S*P/2字節(jié)。87這樣，系統(tǒng)額外開銷的總字節(jié)數(shù)為： S/P*M/S + M/S*P/2為了達(dá)到額外開銷比最小，可令： F（P）=（S/P*M/S + M/S*P/2）/ M =（M/P + MP/2 S）/ M = 1/P + P/2 S 對F（P）求導(dǎo)，令一階導(dǎo)數(shù)為0，得： 從該式可以看出，頁面尺寸P是與進(jìn)程平均長度S有關(guān)的參數(shù)。只有滿足上述關(guān)系時，內(nèi)存的額外開銷才會達(dá)到最小。SP288二

31、、多級頁表結(jié)構(gòu)二、多級頁表結(jié)構(gòu) 請計算：一個由32位二進(jìn)制組成的地址空間，頁面長度為4KB，每個頁表項占用4B，則：進(jìn)程的頁面總數(shù)可達(dá) 個。整個頁表占用 。如果高一級的頁表也必須用多個幀來存放，那么還需要建立更高一級的頁表多級頁表那么問題又來了：頁表本身怎么存放？將進(jìn)程的頁表按幀的長度劃分為多個頁面，并建立高一級的頁表來索引它們兩級頁表89計算題計算題1. 1. 一個由32位二進(jìn)制組成的地址空間，頁面長度為4KB，每個頁表項占用4B。 （a）采用一級頁表機(jī)制，所允許的進(jìn)程的最大長度是（ ）。（b）采用兩級級頁表機(jī)制，所允許的進(jìn)程的最大長度是（ ） 。90因頁面長度為4KB，所以頁內(nèi)偏移占12位

32、；余下20位對應(yīng)頁號，所以進(jìn)程的頁面總數(shù)可達(dá)1M個；整個頁表占用4MB，這4MB又劃分為1K個頁面；一個頁面正好可存放1K個頁表項；所以，為了查找這1K個頁面，需建立兩級頁表結(jié)構(gòu)。那么，相對地址被分成a、b、c三個域，a、b用于兩級頁表，c用于頁內(nèi)偏移地址。即：外層頁號a和內(nèi)層頁號b各占10位，偏移量c占12位計算題計算題2：若一個由32位二進(jìn)制組成的地址空間，頁面長度為4KB，每個頁表項占用4B，請問地址結(jié)構(gòu)。9192在多級頁表機(jī)制中，處理機(jī)中要設(shè)有外部頁表寄存器，存放當(dāng)前進(jìn)程的外部頁表首地址。系統(tǒng)根據(jù)指令給出的相對地址進(jìn)行變換，過程為：用邏輯地址中的外層頁號a查外層頁表，得到內(nèi)層頁表首地址

33、。用邏輯地址中的內(nèi)層頁號b查內(nèi)層頁表，得到數(shù)據(jù)幀號。將數(shù)據(jù)幀的首地址加上偏移地址c得到物理地址。93多級頁表機(jī)制的地址變換過程 94 三、快表快表（1）存儲在高速緩存；（2）內(nèi)容為頁表中最近使用的頁表項95 對于對于CPU給出的一個相對地址給出的一個相對地址，引入快表之后的地址變換過程是：引入快表之后的地址變換過程是：（1）硬件邏輯中，將邏輯地址中的頁號P送入高速緩存，與其中的所有頁號進(jìn)行比較。找到相匹配的頁號后，讀出該頁面對應(yīng)的幀號，送物理地址寄存器，與偏移量W共同合成一個訪問內(nèi)存的物理地址。（2）若高速緩存內(nèi)找不到相匹配的頁號，表示欲訪問的頁號不在快表中。系統(tǒng)需要再訪問內(nèi)存中的頁表。找到該頁的幀號，送物理地址寄存器與偏移量W共同合成訪問內(nèi)存的物理地址。同時，將該頁及幀號復(fù)制到快表中。此時，如果高速緩存已沒有空閑位置，應(yīng)找到一個最不常用的頁表項淘汰掉，換入新的頁表項。96下圖給出了轉(zhuǎn)換過程，中間部分是保存快表的高速緩存。97一般地，當(dāng)查詢快表的命中率為一般地，當(dāng)查詢快表的命中率為p，則平均內(nèi)，則平均內(nèi)存有效訪問時間存有效訪問時間T大約為：大約為：)2()1