第五章-存儲(chǔ)管理課件

第五章存儲(chǔ)管理主存的管理1.第五章存儲(chǔ)管理主存的管理1.第五章存儲(chǔ)管理5.1存儲(chǔ)管理的功能5.2分區(qū)存儲(chǔ)管理5.3覆蓋和交換5.4頁(yè)式管理5.5段式與段頁(yè)式管理5.6局部性原理與抖動(dòng)問(wèn)題2.第五章存儲(chǔ)管理5.1存儲(chǔ)管理的功能2.5.1存儲(chǔ)管理的功能5.1.1虛擬存儲(chǔ)器5.1.2地址變換5.1.3內(nèi)外存數(shù)據(jù)傳輸?shù)目刂?.1.4內(nèi)存的分配與回收5.1.5內(nèi)存信息的共享與保護(hù)3.5.1存儲(chǔ)管理的功能5.1.1虛擬存儲(chǔ)器3.5.1.1虛擬存儲(chǔ)器內(nèi)存由順序編址的塊組成，內(nèi)存的每個(gè)存儲(chǔ)單元都有一個(gè)編號(hào)，這種編號(hào)稱為內(nèi)存地址（或稱為物理地址，絕對(duì)地址）。內(nèi)存地址的集合稱為內(nèi)存空間（或物理地址空間）。4.5.1.1虛擬存儲(chǔ)器內(nèi)存由順序編址的塊組成，內(nèi)存的每個(gè)存5.1.1虛擬存儲(chǔ)器用戶編程所用的地址稱為邏輯地址（或虛地址）。由邏輯地址組成的空間稱為邏輯地址空間（或虛擬地址空間）。5.5.1.1虛擬存儲(chǔ)器用戶編程所用的地址稱為邏輯地址（或虛5.1.1虛擬存儲(chǔ)器源程序——〉目標(biāo)代碼地址安排？按照物理存儲(chǔ)器中的位置賦予實(shí)際物理地址。優(yōu)點(diǎn)：CPU執(zhí)行目標(biāo)代碼時(shí)的執(zhí)行速度高。缺點(diǎn)：能裝入內(nèi)存并發(fā)執(zhí)行的進(jìn)程數(shù)大大減少，對(duì)于某些較大的進(jìn)程可能會(huì)無(wú)法執(zhí)行；編譯程序?qū)⒎浅?fù)雜，編譯程序必須知道內(nèi)存的當(dāng)前空閑部分及其地址，并且把一個(gè)進(jìn)程的不同程序段連續(xù)地存放起來(lái)6.5.1.1虛擬存儲(chǔ)器源程序——〉目標(biāo)代碼地址安排？

由編譯鏈接程序編譯后鏈接（靜態(tài)、動(dòng)態(tài)）到一個(gè)以0地址為始地址的線性或多維虛擬地址空間（邏輯地址空間）。每個(gè)進(jìn)程都擁有一個(gè)虛擬地址空間。每個(gè)指令或數(shù)據(jù)單元都在這個(gè)虛擬空間中擁有確定的地址，把這個(gè)地址稱為虛擬地址（virtualaddress）(邏輯地址)。地址轉(zhuǎn)換LoadA2003456。。1200物理地址空間LoadAdata1data13456源程序LoadA20034560100200編譯鏈接虛擬地址空間BA=10007.由編譯鏈接程序編譯后鏈接（靜態(tài)、動(dòng)態(tài)）到一個(gè)以0地址為始地5.1.1虛擬存儲(chǔ)器虛擬存儲(chǔ)器：進(jìn)程中的目標(biāo)代碼、數(shù)據(jù)等的虛擬地址組成的虛擬空間稱為虛擬存儲(chǔ)器。8.5.1.1虛擬存儲(chǔ)器虛擬存儲(chǔ)器：進(jìn)程中的目標(biāo)代碼、數(shù)據(jù)等實(shí)現(xiàn)虛擬內(nèi)存的基本原理將程序正在使用的部分內(nèi)容放在內(nèi)存，而暫時(shí)不用的部分放在外存，在需要時(shí)由系統(tǒng)調(diào)入內(nèi)存，并將不需要（或暫不需要）的部分調(diào)出內(nèi)存。由于程序在執(zhí)行時(shí)，在一段時(shí)間內(nèi)一般僅使用它的程序的一部分（或一小部分），所以程序僅有部分裝入內(nèi)存完全能夠正確執(zhí)行。要由操作系統(tǒng)結(jié)合相關(guān)硬件來(lái)完成上述工件，這樣計(jì)算機(jī)好象為用戶提供了一個(gè)容量遠(yuǎn)大于內(nèi)存的存儲(chǔ)器，這個(gè)存儲(chǔ)器稱為虛擬存儲(chǔ)器。

9.實(shí)現(xiàn)虛擬內(nèi)存的基本原理將程序正在使用的部分內(nèi)容放在內(nèi)存，而暫5.1.1虛擬存儲(chǔ)器虛擬存儲(chǔ)器呈現(xiàn)在用戶面前的是一個(gè)在物理上只受內(nèi)存和外存總?cè)萘肯拗频拇鎯?chǔ)系統(tǒng)，這要求存儲(chǔ)管理系統(tǒng)只把進(jìn)程執(zhí)行時(shí)頻繁使用和立即需要的指令與數(shù)據(jù)等存放在內(nèi)存中，而把那些暫時(shí)不需要的部分存放在外存中，待需要時(shí)自動(dòng)調(diào)入，以提高內(nèi)存的利用率和并行執(zhí)行的作業(yè)道數(shù)。虛擬存儲(chǔ)器不考慮物理存儲(chǔ)器的大小和信息存放的實(shí)際位置，只規(guī)定每個(gè)進(jìn)程中互相關(guān)聯(lián)的信息的相對(duì)位置。每個(gè)進(jìn)程都擁有自己的虛擬存儲(chǔ)器，且虛擬存儲(chǔ)器的容量是由計(jì)算機(jī)的地址結(jié)構(gòu)和尋址方式確定的。10.5.1.1虛擬存儲(chǔ)器虛擬存儲(chǔ)器呈現(xiàn)在用戶面前的是一個(gè)在物5.1.2地址變換地址重定位：從虛擬地址到內(nèi)存地址的轉(zhuǎn)換稱為地址重定位，或稱為地址映射。地址映射的方式：1、靜態(tài)地址重定位2、動(dòng)態(tài)地址重定位11.5.1.2地址變換地址重定位：從虛擬地址到內(nèi)存地址的轉(zhuǎn)1、靜態(tài)地址重定位在虛擬空間程序執(zhí)行之前由裝配程序完成地址映射的工作。不能實(shí)現(xiàn)虛擬存儲(chǔ)器假定程序裝入內(nèi)存的首地址為BA，程序地址為VA，內(nèi)存地址為MA，則地址映射按下式進(jìn)行：MA=(BA)+(VA)。12.1、靜態(tài)地址重定位在虛擬空間程序執(zhí)行之前由裝配程序完成地址映例程序裝入內(nèi)存的首地址為1000，則裝配程序就按MA=1000+VA對(duì)程序中所有地址部分進(jìn)行修改，修改后指令LoadA，200就變?yōu)長(zhǎng)oadA，120013.例程序裝入內(nèi)存的首地址為1000，則裝配程序就按MA=100靜態(tài)地址重定位的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：不需要硬件的支持。缺點(diǎn)：程序必須占用連續(xù)的內(nèi)存空間，程序和數(shù)據(jù)不能共享；程序一旦裝入內(nèi)存之后就不能再移動(dòng)，并且必須在程序執(zhí)行之前將有關(guān)部分全部裝入。14.靜態(tài)地址重定位的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：不需要硬件的支持。14.2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位是在程序執(zhí)行的過(guò)程中，在CPU訪問(wèn)內(nèi)存之前，將要訪問(wèn)的程序地址轉(zhuǎn)換為內(nèi)存地址。一般來(lái)說(shuō)這種轉(zhuǎn)換是由專門的硬件機(jī)構(gòu)來(lái)完成的。在地址重定位機(jī)構(gòu)中，有一個(gè)基地址寄存器BR和一個(gè)程序地址寄存器VR，一個(gè)內(nèi)存地址寄存器MR。MA=(BR)+(VR)15.2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位是在程序執(zhí)行的過(guò)程中，在CP2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位的具體過(guò)程：程序裝入內(nèi)存后，它所占用的內(nèi)存區(qū)的首地址由系統(tǒng)送入基地址寄存器BR中。在程序執(zhí)行的過(guò)程中，若要訪問(wèn)內(nèi)存，將訪問(wèn)的邏輯地址送入程序地址寄存器VR中。地址轉(zhuǎn)換機(jī)構(gòu)把VR和BR中的內(nèi)容相加，并將結(jié)果送入MR中，作為實(shí)際訪問(wèn)的物理地址。16.2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位的具體過(guò)程：16.圖5.3動(dòng)態(tài)地址重定位17.17.2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位的優(yōu)點(diǎn)可以對(duì)內(nèi)存進(jìn)行非連續(xù)分配。程序占用的內(nèi)存空間是動(dòng)態(tài)可變的，當(dāng)程序從某個(gè)存儲(chǔ)區(qū)移到另一個(gè)區(qū)域時(shí)，只需要修改相應(yīng)的寄存器BR的內(nèi)容即可。提供了實(shí)現(xiàn)虛擬存儲(chǔ)器的基礎(chǔ)。一個(gè)程序不一定要求占用一個(gè)連續(xù)的內(nèi)存空間?？梢圆糠值匮b入程序運(yùn)行。便于多個(gè)進(jìn)程共享同一個(gè)程序的代碼。18.2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位的優(yōu)點(diǎn)18.2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位的代價(jià)：需要硬件的支持。實(shí)現(xiàn)存儲(chǔ)管理的軟件算法較為復(fù)雜。19.2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位的代價(jià)：19.5.1.3內(nèi)外存數(shù)據(jù)傳輸?shù)目刂苾?nèi)外存數(shù)據(jù)傳輸?shù)目刂疲河脩舫绦蜃约嚎刂疲焊采w技術(shù)——用戶負(fù)擔(dān)很大，程序段的最大長(zhǎng)度受內(nèi)存容量限制，不能實(shí)現(xiàn)虛擬存儲(chǔ)器。操作系統(tǒng)控制：交換(swapping)方式：不同的進(jìn)程或作業(yè)之間請(qǐng)求調(diào)入(ondemand)方式和預(yù)調(diào)入(onprefetch)方式20.5.1.3內(nèi)外存數(shù)據(jù)傳輸?shù)目刂苾?nèi)外存數(shù)據(jù)傳輸?shù)目刂疲?05.1.4內(nèi)存的分配與回收要完成內(nèi)存的分配和回收工作，要求設(shè)計(jì)者選擇和確定以下幾種策略和結(jié)構(gòu)：分配結(jié)構(gòu)調(diào)入策略放置策略交換策略回收策略21.5.1.4內(nèi)存的分配與回收要完成內(nèi)存的分配和回收工作，5.1.4內(nèi)存的分配與回收分配結(jié)構(gòu)—分配結(jié)構(gòu)是用來(lái)登記內(nèi)存使用情況的數(shù)據(jù)結(jié)構(gòu)。如空閑區(qū)表、空閑區(qū)隊(duì)列等。調(diào)入策略—用戶程序在何時(shí)、怎樣調(diào)入內(nèi)存的策略。放置策略—用戶程序調(diào)入內(nèi)存時(shí)，確定將其放置在何處的策略。22.5.1.4內(nèi)存的分配與回收分配結(jié)構(gòu)—分配結(jié)構(gòu)是用來(lái)登記5.1.4內(nèi)存的分配與回收交換策略—當(dāng)需要將某個(gè)用戶程序調(diào)入內(nèi)存而內(nèi)存空間又不夠時(shí)，就要確定哪個(gè)或哪些程序可以從內(nèi)存中移走?；厥詹呗浴_定回收的時(shí)機(jī)和對(duì)所回收的內(nèi)存空閑區(qū)和已存在的內(nèi)存空閑區(qū)進(jìn)行調(diào)整。23.5.1.4內(nèi)存的分配與回收交換策略—當(dāng)需要將某個(gè)用戶程5.1.5內(nèi)存信息的共享與保護(hù)保證在內(nèi)存中的多道程序只能在給定的存儲(chǔ)區(qū)域內(nèi)活動(dòng)并互不產(chǎn)生干擾。包括：防止地址越界防止越權(quán)(對(duì)共享區(qū)有訪問(wèn)權(quán))24.5.1.5內(nèi)存信息的共享與保護(hù)保證在內(nèi)存中的多道程序只能5.1.5內(nèi)存信息的共享與保護(hù)內(nèi)存保護(hù)的方法：硬件法、軟件法和軟硬件法。上下界保護(hù)法：硬件法1、在CPU中設(shè)置一對(duì)下限寄存器和上限寄存器存放用戶作業(yè)在主存中的下限和上限地址2、每當(dāng)CPU要訪問(wèn)主存，硬件自動(dòng)將被訪問(wèn)的主存地址與界限寄存器的內(nèi)容進(jìn)行比較，以判斷是否越界3、如果未越界，則按此地址訪問(wèn)主存，否則將產(chǎn)生程序中斷——越界中斷（存儲(chǔ)保護(hù)中斷）25.5.1.5內(nèi)存信息的共享與保護(hù)內(nèi)存保護(hù)的方法：硬件法、軟圖5.4上、下界寄存器保護(hù)法26.26.5.1.5內(nèi)存信息的共享與保護(hù)保護(hù)鍵法：軟件法

為每一個(gè)被保護(hù)的存儲(chǔ)塊分配一個(gè)單獨(dú)的保護(hù)鍵。在程序狀態(tài)字中設(shè)置相應(yīng)的保護(hù)鍵開(kāi)關(guān)字段，訪問(wèn)過(guò)程中比較保護(hù)開(kāi)關(guān)字段的內(nèi)容和保護(hù)鍵是否匹配，匹配則允許訪問(wèn)，否則產(chǎn)生訪問(wèn)出錯(cuò)中斷。27.5.1.5內(nèi)存信息的共享與保護(hù)保護(hù)鍵法：軟件法27.圖5.5保護(hù)鍵保護(hù)法28.28.5.1.5內(nèi)存信息的共享與保護(hù)界限寄存器與CPU的用戶態(tài)或核心態(tài)工作方式相結(jié)合的保護(hù)方式。軟硬件法用戶態(tài)進(jìn)程只能訪問(wèn)那些在界限寄存器所規(guī)定范圍內(nèi)的內(nèi)存部分，而核心態(tài)進(jìn)程則可以訪問(wèn)整個(gè)內(nèi)存地址空間。29.5.1.5內(nèi)存信息的共享與保護(hù)界限寄存器與CPU的用戶態(tài)5.2分區(qū)存儲(chǔ)管理把整個(gè)內(nèi)存劃分為若干大小不等的區(qū)域，操作系統(tǒng)占用一個(gè)區(qū)域，其它區(qū)域供系統(tǒng)中的多個(gè)進(jìn)程共享，這種方法稱為分區(qū)存儲(chǔ)管理。5.2.1分區(qū)存儲(chǔ)管理的基本原理5.2.2分區(qū)的分配與回收5.2.3有關(guān)分區(qū)管理其他問(wèn)題討論30.5.2分區(qū)存儲(chǔ)管理把整個(gè)內(nèi)存劃分為若干大小不等的區(qū)域，5.2.1分區(qū)存儲(chǔ)管理的基本原理基本原理：給每一個(gè)內(nèi)存中的進(jìn)程劃分一塊適當(dāng)大小的存儲(chǔ)區(qū),以連續(xù)存儲(chǔ)各進(jìn)程的程序和數(shù)據(jù)，使各進(jìn)程得以并發(fā)執(zhí)行。這是最簡(jiǎn)單的一種存儲(chǔ)管理，按分區(qū)劃分的時(shí)機(jī)可分為：

1、固定分區(qū)2、動(dòng)態(tài)分區(qū)31.5.2.1分區(qū)存儲(chǔ)管理的基本原理基本原理：給每一個(gè)內(nèi)存中的1、固定分區(qū)固定分區(qū)：把內(nèi)存固定地劃分為若干個(gè)大小不等的區(qū)域。分區(qū)的劃分由計(jì)算機(jī)的操作員或者由操作系統(tǒng)給出，并給出分區(qū)說(shuō)明表。在調(diào)度作業(yè)時(shí)，由存儲(chǔ)管理根據(jù)所需量在分區(qū)說(shuō)明表中找出一個(gè)單元分配給它。32.1、固定分區(qū)固定分區(qū)：把內(nèi)存固定地劃分為若干個(gè)大小不等的區(qū)域1、固定分區(qū)分區(qū)說(shuō)明表分區(qū)號(hào)大小(KB)始址狀態(tài)1820已分配23228已分配36460已分配4132124未分配33.1、固定分區(qū)分區(qū)說(shuō)明表分區(qū)號(hào)大小(KB)始址狀態(tài)1820已分圖5.6固定分區(qū)法34.34.1、固定分區(qū)在作業(yè)大小和出現(xiàn)頻率均已知的情況下，固定分區(qū)是合適的。在這種情況下分區(qū)的大小選擇與作業(yè)大小相當(dāng)，這樣內(nèi)存的使用效率較高。但是若作業(yè)的大小和出現(xiàn)的頻率不知道時(shí)，勢(shì)必造成分區(qū)的大小和作業(yè)的大小相差甚遠(yuǎn)，這樣就會(huì)造成存儲(chǔ)空間的浪費(fèi)，從而影響整個(gè)系統(tǒng)的效率。35.1、固定分區(qū)在作業(yè)大小和出現(xiàn)頻率均已知的情況下，固定分區(qū)是合2、動(dòng)態(tài)分區(qū)動(dòng)態(tài)分區(qū)：在系統(tǒng)運(yùn)行的過(guò)程中建立分區(qū)，并使分區(qū)的大小剛好與作業(yè)的大小相等。這種存儲(chǔ)管理的方法解決了固定分區(qū)嚴(yán)重浪費(fèi)內(nèi)存的問(wèn)題。是一種較為實(shí)用的存儲(chǔ)管理方法。36.2、動(dòng)態(tài)分區(qū)動(dòng)態(tài)分區(qū)：在系統(tǒng)運(yùn)行的過(guò)程中建立分區(qū)，并使分區(qū)的圖5.7動(dòng)態(tài)分區(qū)內(nèi)存初始分配情況37.37.2、動(dòng)態(tài)分區(qū)在實(shí)現(xiàn)動(dòng)態(tài)分區(qū)分配的時(shí)候需要涉及到以下三個(gè)方面的問(wèn)題：動(dòng)態(tài)分配中所用到的數(shù)據(jù)結(jié)構(gòu)；分區(qū)的分配算法；分區(qū)的分配和回收操作。38.2、動(dòng)態(tài)分區(qū)在實(shí)現(xiàn)動(dòng)態(tài)分區(qū)分配的時(shí)候需要涉及到以下三個(gè)方面2、動(dòng)態(tài)分區(qū)實(shí)現(xiàn)動(dòng)態(tài)分區(qū)的數(shù)據(jù)結(jié)構(gòu)：在動(dòng)態(tài)分區(qū)存儲(chǔ)管理中，要有相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來(lái)登記空閑區(qū)的說(shuō)明信息，它包括空閑區(qū)的大小和位置。其數(shù)據(jù)結(jié)構(gòu)有：分區(qū)說(shuō)明表、可用分區(qū)表（或自由鏈）、請(qǐng)求表。分區(qū)說(shuō)明表可用分區(qū)表：用于為內(nèi)存中每個(gè)還沒(méi)有分區(qū)設(shè)置一個(gè)表項(xiàng)，每個(gè)分區(qū)表項(xiàng)包含分區(qū)序號(hào)、分區(qū)起始地址以及分區(qū)大小。（占用內(nèi)存）39.2、動(dòng)態(tài)分區(qū)實(shí)現(xiàn)動(dòng)態(tài)分區(qū)的數(shù)據(jù)結(jié)構(gòu)：39.2、動(dòng)態(tài)分區(qū)實(shí)現(xiàn)動(dòng)態(tài)分區(qū)的數(shù)據(jù)結(jié)構(gòu)：自由鏈：利用每個(gè)內(nèi)存空閑區(qū)的頭幾個(gè)單元存放本空閑區(qū)的大小和下個(gè)空閑區(qū)的起始地址，將所有空閑區(qū)組成一條鏈。（不占用內(nèi)存）

請(qǐng)求表：表的每個(gè)表目描述請(qǐng)求內(nèi)存資源的作業(yè)或進(jìn)程號(hào)以及所請(qǐng)求的內(nèi)存大小。40.2、動(dòng)態(tài)分區(qū)實(shí)現(xiàn)動(dòng)態(tài)分區(qū)的數(shù)據(jù)結(jié)構(gòu)：40.圖5.9可用表、自由鏈及請(qǐng)求表41.41.圖5.8內(nèi)存分配變化過(guò)程42.42.5.2.2分區(qū)的分配與回收1、固定分區(qū)的分配與回收2、動(dòng)態(tài)分區(qū)時(shí)的分配與回收3、動(dòng)態(tài)分區(qū)時(shí)的回收與拼接4、幾種分配算法的比較43.5.2.2分區(qū)的分配與回收1、固定分區(qū)的分配與回收43.1、固定分區(qū)的分配與回收分配：當(dāng)用戶程序要裝入執(zhí)行時(shí)，通過(guò)請(qǐng)求表提出內(nèi)存分配要求和所要求的內(nèi)存空間大小。存儲(chǔ)管理程序根據(jù)請(qǐng)求表要求查詢分區(qū)說(shuō)明表，從中找出一個(gè)滿足要求的空閑分區(qū)，將其分配給申請(qǐng)者。P117圖回收：回收時(shí)管理程序只需將對(duì)應(yīng)的分區(qū)狀態(tài)置為未使用即可。

44.1、固定分區(qū)的分配與回收分配：當(dāng)用戶程序要裝入執(zhí)行時(shí)，通過(guò)請(qǐng)2、動(dòng)態(tài)分區(qū)時(shí)的分配與回收主要解決的三個(gè)問(wèn)題:(1)對(duì)于請(qǐng)求表中的要求內(nèi)存長(zhǎng)度，從可用表或自由鏈中尋找出合適的空閑區(qū)分配程序。(2)分配空閑區(qū)之后，更新可用表或自由鏈。(3)進(jìn)程或作業(yè)釋放內(nèi)存資源時(shí)，和相鄰的空閑區(qū)進(jìn)行鏈接合并，更新可用表或自由鏈。45.2、動(dòng)態(tài)分區(qū)時(shí)的分配與回收主要解決的三個(gè)問(wèn)題:45.2、動(dòng)態(tài)分區(qū)時(shí)的分配與回收從可用表或自由鏈中尋找空閑區(qū)的常用的三種方法：最先適應(yīng)法(firstfitalgorithm)最佳適應(yīng)法(bestfitalgorithm)最壞適應(yīng)法(worstfitalgoriathm)這三種方法要求可用表或自由鏈按不同的方式排列。46.2、動(dòng)態(tài)分區(qū)時(shí)的分配與回收從可用表或自由鏈中尋找空閑區(qū)的常用最先適應(yīng)法要求可用表或自由鏈按起始地址遞增的次序排列。分配：當(dāng)進(jìn)程申請(qǐng)大小為SIZE的內(nèi)存時(shí)，存儲(chǔ)管理程序從空閑區(qū)表的第一個(gè)表目開(kāi)始查詢，直到首次找到等于或大于SIZE的空閑區(qū)。從該區(qū)中劃出大小為SIZE的分區(qū)分配給進(jìn)程，余下的部分仍作為一個(gè)空閑區(qū)留在空閑區(qū)表中，但要修改其首址和大小。47.最先適應(yīng)法要求可用表或自由鏈按起始地址遞增的次序排列。47.最先適應(yīng)法回收：按釋放區(qū)的首址，查詢空閑區(qū)表，若有與釋放區(qū)相鄰的空閑區(qū)，則合并到相鄰的空閑區(qū)中，并修改該區(qū)的大小和首址，否則，把釋放區(qū)作為一個(gè)空閑區(qū)，將其大小和首址按照首地址大小遞增的順序插入到空閑區(qū)表的適當(dāng)位置。48.最先適應(yīng)法回收：按釋放區(qū)的首址，查詢空閑區(qū)表，若有與釋放區(qū)相最先適應(yīng)法的優(yōu)點(diǎn)釋放某一存儲(chǔ)區(qū)時(shí)，若與空閑區(qū)相鄰則合并到相鄰空閑分區(qū)中去，這種情況并不改變?cè)搮^(qū)在表中的位置，只要修改其大小或首址。這種算法是盡可能地利用低地址空間，從而保證高地址空間有較大的空閑區(qū)。49.最先適應(yīng)法的優(yōu)點(diǎn)釋放某一存儲(chǔ)區(qū)時(shí)，若與空閑區(qū)相鄰則合并到相鄰最佳適應(yīng)法要求按空閑區(qū)大小從小到大的次序組成空閑區(qū)表（隊(duì)列）。分配：當(dāng)用戶作業(yè)或進(jìn)程申請(qǐng)一個(gè)存儲(chǔ)區(qū)時(shí)，存儲(chǔ)管理程序從表頭開(kāi)始查找，當(dāng)找到第一個(gè)滿足要求的空閑區(qū)時(shí)，停止查找，并且這個(gè)空閑區(qū)是最佳的空閑區(qū)（選中的空閑區(qū)是滿足要求的最小空閑區(qū)）。如果該空閑區(qū)大于請(qǐng)求表中的請(qǐng)求長(zhǎng)度，則與最先適應(yīng)法時(shí)相同，將減去請(qǐng)求長(zhǎng)度后的剩余空閑區(qū)部分留在可用表中。50.最佳適應(yīng)法要求按空閑區(qū)大小從小到大的次序組成空閑區(qū)表（隊(duì)列）最佳適應(yīng)法回收：按釋放區(qū)的首址，查詢空閑區(qū)表（隊(duì)列），若有與釋放區(qū)相鄰的空閑區(qū)，則合并到相鄰的空閑區(qū)中，并修改該區(qū)的大小和首址，否則，把釋放區(qū)作為一個(gè)空閑區(qū)插入空閑區(qū)表（隊(duì)列）。分配和回收后要對(duì)空閑區(qū)表（隊(duì)列）重新排序。51.最佳適應(yīng)法回收：按釋放區(qū)的首址，查詢空閑區(qū)表（隊(duì)列），若有最佳適應(yīng)算法的優(yōu)點(diǎn)在系統(tǒng)中若存在一個(gè)與申請(qǐng)分區(qū)大小相等的空閑區(qū)，必定會(huì)被選中，而最先適應(yīng)法則不一定。若系統(tǒng)中不存在與申請(qǐng)分區(qū)大小相等的空閑區(qū)，則選中的空閑區(qū)是滿足要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。52.最佳適應(yīng)算法的優(yōu)點(diǎn)在系統(tǒng)中若存在一個(gè)與申請(qǐng)分區(qū)大小相等的空閑最佳適應(yīng)算法的缺點(diǎn)空閑區(qū)的大小一般與申請(qǐng)分區(qū)大小不相等，因此將其一分為二，留下來(lái)的空閑區(qū)一般情況下是很小的，以致無(wú)法使用。隨著時(shí)間的推移，系統(tǒng)中的小空閑區(qū)會(huì)越來(lái)越多，從而造成存儲(chǔ)區(qū)的大量浪費(fèi)。

53.最佳適應(yīng)算法的缺點(diǎn)空閑區(qū)的大小一般與申請(qǐng)分區(qū)大小不相等，因最壞適應(yīng)算法要求空閑區(qū)按由大至小遞減的順序組織空閑區(qū)表（或隊(duì)列）。分配：進(jìn)程申請(qǐng)一個(gè)大小為SIZE的存儲(chǔ)區(qū)時(shí)，總是檢查空閑區(qū)表的第一個(gè)空閑區(qū)的大小是否大于或等于SIZE。若空閑區(qū)小于SIZE，則分配失敗；否則從空閑區(qū)中分配SIZE的存儲(chǔ)區(qū)給用戶，然后修改和調(diào)整空閑區(qū)表。54.最壞適應(yīng)算法要求空閑區(qū)按由大至小遞減的順序組織空閑區(qū)表（或最壞適應(yīng)算法回收：按釋放區(qū)的首址，查詢空閑區(qū)表（隊(duì)列），若有與釋放區(qū)相鄰的空閑區(qū)，則合并到相鄰的空閑區(qū)中，并修改該區(qū)的大小和首址，否則，把釋放區(qū)作為一個(gè)空閑區(qū)插入空閑區(qū)表（隊(duì)列）。分配和回收后要對(duì)空閑區(qū)表（隊(duì)列）重新排序。55.最壞適應(yīng)算法回收：按釋放區(qū)的首址，查詢空閑區(qū)表（隊(duì)列），若有最壞適應(yīng)算法的優(yōu)點(diǎn)當(dāng)程序裝入內(nèi)存中最大的空閑區(qū)后，剩下的空閑區(qū)還可能相當(dāng)大，還能裝下較大的程序。每次僅作一次查詢工作。56.最壞適應(yīng)算法的優(yōu)點(diǎn)當(dāng)程序裝入內(nèi)存中最大的空閑區(qū)后，剩下的空閑3、動(dòng)態(tài)分區(qū)時(shí)分區(qū)的回收當(dāng)某個(gè)進(jìn)程釋放某存儲(chǔ)區(qū)時(shí)，系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰，若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)中去，否則把釋放區(qū)作為一個(gè)空閑區(qū)插入到空閑區(qū)表的適當(dāng)位置。

57.3、動(dòng)態(tài)分區(qū)時(shí)分區(qū)的回收當(dāng)某個(gè)進(jìn)程釋放某存儲(chǔ)區(qū)時(shí)，系統(tǒng)首先檢圖5.12空閑區(qū)的合并58.58.空閑區(qū)的合并釋放區(qū)與上下兩空閑區(qū)相鄰：將三個(gè)空閑區(qū)合并為一個(gè)空閑區(qū)。新空閑區(qū)的起始地址為上空閑區(qū)的起始地址，大小為三個(gè)空閑區(qū)之和?？臻e區(qū)合并后，取消可用表或自由鏈中下空閑區(qū)的表目項(xiàng)或鏈指針，修改上空閑區(qū)的對(duì)應(yīng)項(xiàng)。釋放區(qū)只與上空閑區(qū)相鄰：將釋放區(qū)與上空閑區(qū)合并為一個(gè)空閑區(qū)，其起始地址為上空閑區(qū)的起始地址，大小為上空閑區(qū)與釋放區(qū)之和。合并后，修改上空閑區(qū)對(duì)應(yīng)的可用表的表目項(xiàng)或自由鏈指針。59.空閑區(qū)的合并釋放區(qū)與上下兩空閑區(qū)相鄰：將三個(gè)空閑區(qū)合并為一個(gè)空閑區(qū)的合并釋放區(qū)與下空閑區(qū)相鄰：將釋放區(qū)與下空閑區(qū)合并，并將釋放區(qū)的起始地址作為合并區(qū)的起始地址。合并區(qū)的長(zhǎng)度為釋放區(qū)與下空閑區(qū)之和。合并后修改可用表或自由鏈中相應(yīng)的表目項(xiàng)或鏈指針。釋放區(qū)不與任何空閑區(qū)相鄰：釋放區(qū)作為一個(gè)新可用區(qū)插入可用表或自由鏈。60.空閑區(qū)的合并釋放區(qū)與下空閑區(qū)相鄰：將釋放區(qū)與下空閑區(qū)合并，并4、三種分配算法的比較三種算法的優(yōu)缺點(diǎn)比較搜索速度：最先適應(yīng)算法具有最佳性能，最佳適應(yīng)算法和最壞適應(yīng)算法都要求把不同大小的空閑區(qū)按大小進(jìn)行排隊(duì)；回收過(guò)程：最先適應(yīng)算法具有最佳性能，因?yàn)樽罴堰m應(yīng)算法和最壞適應(yīng)算法都必須重新調(diào)整空閑區(qū)的位置；空閑區(qū)利用：最佳適應(yīng)法找到的空閑區(qū)是最佳的，但是會(huì)造成內(nèi)存碎片較多，影響內(nèi)存利用率，而最壞適用法的內(nèi)存碎片最少，但是對(duì)內(nèi)存的請(qǐng)求較多的進(jìn)程有可能分配失敗。總之，三種算法各有所長(zhǎng)，針對(duì)不同的請(qǐng)求隊(duì)列，它們的效率和功能是不一樣的。61.4、三種分配算法的比較三種算法的優(yōu)缺點(diǎn)比較61.4、三種分配算法的比較上述三種放置策略各有利弊，到底哪種最好不能一概而論，而應(yīng)針對(duì)具體作業(yè)序列來(lái)分析。對(duì)于某一作業(yè)序列來(lái)說(shuō)，某種算法能將該作業(yè)序列中所有作業(yè)安置完畢，那么我們說(shuō)該算法對(duì)這一作業(yè)序列是合適的。對(duì)于某一算法而言，如它不能立即滿足某一要求，而其它算法卻可以滿足此要求，則這一算法對(duì)該作業(yè)序列是不合適的。62.4、三種分配算法的比較上述三種放置策略各有利弊，到底哪種最好例題例1：有作業(yè)序列：作業(yè)A要求18K；作業(yè)B要求25K，作業(yè)C要求30K。系統(tǒng)中空閑區(qū)按三種算法組成的空閑區(qū)隊(duì)列，現(xiàn)在請(qǐng)你分析哪種算法適合該作業(yè)序列？

OS30作業(yè)作業(yè)2046作業(yè)5205010012016016016521025663.例題例1：有作業(yè)序列：作業(yè)A要求18K；作業(yè)B要求25K，作例題最先分配前內(nèi)存分配前內(nèi)存自由鏈作業(yè)請(qǐng)求長(zhǎng)度A18B25C30請(qǐng)求表64.例題最先分配前內(nèi)存例題經(jīng)分析可知：最佳適應(yīng)法對(duì)這個(gè)作業(yè)序列是合適的，而其它兩種對(duì)該作業(yè)序列是不合適的。因?yàn)樽钕冗m應(yīng)算法和最壞適應(yīng)算法對(duì)于作業(yè)C來(lái)說(shuō)都不能為它分配所需要的內(nèi)存空間。65.例題經(jīng)分析可知：最佳適應(yīng)法對(duì)這個(gè)作業(yè)序列是合適的，而其它兩種練習(xí)如果現(xiàn)在作業(yè)序列變?yōu)橐韵虑闆r，分析哪種算法適合于這個(gè)作業(yè)序列？作業(yè)A要求21K，作業(yè)B要求30K，作業(yè)C要求25K。66.練習(xí)如果現(xiàn)在作業(yè)序列變?yōu)橐韵虑闆r，分析哪種算法適合于這個(gè)5.2.3有關(guān)分區(qū)管理其他問(wèn)題的討論1、關(guān)于虛存的實(shí)現(xiàn)2、關(guān)于內(nèi)存擴(kuò)充3、關(guān)于地址變換和內(nèi)存保護(hù)4、分區(qū)存儲(chǔ)管理的主要優(yōu)缺點(diǎn)67.5.2.3有關(guān)分區(qū)管理其他問(wèn)題的討論1、關(guān)于虛存的實(shí)現(xiàn)61、關(guān)于虛存的實(shí)現(xiàn)無(wú)法實(shí)現(xiàn)那種用戶進(jìn)程所需內(nèi)存容量只受內(nèi)存和外存容量之和限制的虛擬存儲(chǔ)器。如果不采用內(nèi)存擴(kuò)充技術(shù)，每個(gè)用戶進(jìn)程所需內(nèi)存容量是受到分區(qū)大小限制的。68.1、關(guān)于虛存的實(shí)現(xiàn)無(wú)法實(shí)現(xiàn)那種用戶進(jìn)程所需內(nèi)存容量只受內(nèi)存和2、關(guān)于內(nèi)存擴(kuò)充可以使用覆蓋或交換技術(shù)來(lái)擴(kuò)充內(nèi)存69.2、關(guān)于內(nèi)存擴(kuò)充可以使用覆蓋或交換技術(shù)來(lái)擴(kuò)充內(nèi)存69.3、關(guān)于地址變換和內(nèi)存保護(hù)靜態(tài)地址重定位和動(dòng)態(tài)地址重定位技術(shù)，都可用來(lái)完成分區(qū)式內(nèi)存管理的地址變換。不能使用靜態(tài)地址重定位的方法來(lái)完成動(dòng)態(tài)分區(qū)時(shí)的地址變換。動(dòng)態(tài)地址重定位中的一對(duì)硬件寄存器除了完成動(dòng)態(tài)地址重定位的功能之外，還具有保護(hù)內(nèi)存中數(shù)據(jù)和程序的功能。保護(hù)鍵法也可用來(lái)對(duì)內(nèi)存各分區(qū)提供保護(hù)。70.3、關(guān)于地址變換和內(nèi)存保護(hù)靜態(tài)地址重定位和動(dòng)態(tài)地址重定位技術(shù)4、分區(qū)存儲(chǔ)管理的主要優(yōu)缺點(diǎn)優(yōu)點(diǎn)：實(shí)現(xiàn)了多個(gè)作業(yè)或進(jìn)程對(duì)內(nèi)存的共享，提高了系統(tǒng)的資源利用率。該方法要求的硬件支持少，管理算法簡(jiǎn)單，實(shí)現(xiàn)容易。缺點(diǎn)：內(nèi)存利用率仍然不高，因?yàn)橐廊淮嬖谥樾〉目臻e區(qū)不能利用的問(wèn)題。作業(yè)或進(jìn)程的大小受分區(qū)大小的影響。除非配合覆蓋和交換技術(shù)。難以實(shí)現(xiàn)各分區(qū)的信息共享。71.4、分區(qū)存儲(chǔ)管理的主要優(yōu)缺點(diǎn)優(yōu)點(diǎn)：71.5.3覆蓋與交換技術(shù)在多道環(huán)境下擴(kuò)充內(nèi)存的方法，用以解決在較小的存儲(chǔ)空間中運(yùn)行較大程序時(shí)遇到的矛盾。覆蓋技術(shù)主要用在早期的操作系統(tǒng)中；交換技術(shù)被廣泛用于小型分時(shí)系統(tǒng)中，交換技術(shù)的發(fā)展導(dǎo)致了虛存技術(shù)的出現(xiàn)。72.5.3覆蓋與交換技術(shù)在多道環(huán)境下擴(kuò)充內(nèi)存的覆蓋技術(shù)與交換技術(shù)異同點(diǎn)：共同點(diǎn)：進(jìn)程的程序和數(shù)據(jù)主要放在外存，當(dāng)前需要執(zhí)行的部分放在內(nèi)存，內(nèi)外存之間進(jìn)行信息交換。不同點(diǎn)：如何控制交換？73.覆蓋技術(shù)與交換技術(shù)異同點(diǎn)：共同點(diǎn)：73.覆蓋技術(shù)把程序劃分為若干個(gè)功能上相對(duì)獨(dú)立的程序段，按照其自身的邏輯結(jié)構(gòu)將那些不會(huì)同時(shí)執(zhí)行的程序段共享同一塊內(nèi)存區(qū)域。程序段先保存在磁盤(pán)上，當(dāng)有關(guān)程序段的前一部分執(zhí)行結(jié)束，把后續(xù)程序段調(diào)入內(nèi)存，覆蓋前面的程序段（內(nèi)存“擴(kuò)大”了）。一般要求作業(yè)各模塊之間有明確的調(diào)用結(jié)構(gòu)，程序員要向系統(tǒng)指明覆蓋結(jié)構(gòu)，然后由操作系統(tǒng)完成自動(dòng)覆蓋。74.覆蓋技術(shù)把程序劃分為若干個(gè)功能上相對(duì)獨(dú)立的程序段，按照其自身A8KB8KC10KD12KE4KF10K覆蓋區(qū)0（10K）覆蓋區(qū)1（12K）

BCEFD作業(yè)X的常駐區(qū)

A（8K）

75.ABCDEF覆蓋區(qū)0覆蓋區(qū)1BCEFD作業(yè)X的常駐區(qū)

交換技術(shù)為什么引入交換技術(shù)？當(dāng)內(nèi)存空間緊張時(shí)，系統(tǒng)將內(nèi)存中某些進(jìn)程暫時(shí)移到外存，把外存中某些進(jìn)程換進(jìn)內(nèi)存，占據(jù)前者所占用的區(qū)域，這種技術(shù)是進(jìn)程在內(nèi)存與外存之間的動(dòng)態(tài)調(diào)度。

多用于分時(shí)系統(tǒng)中76.交換技術(shù)為什么引入交換技術(shù)？多用于分時(shí)系統(tǒng)中76.交換進(jìn)程包括兩個(gè)過(guò)程：換出—把內(nèi)存中的數(shù)據(jù)和程序換到外存交換區(qū)。換入—把外存交換區(qū)的數(shù)據(jù)和程序換到內(nèi)存分區(qū)中。何時(shí)需發(fā)生交換？只要不用就換出（或很少再用）只在內(nèi)存空間不夠或有不夠的危險(xiǎn)時(shí)換出77.交換進(jìn)程包括兩個(gè)過(guò)程：何時(shí)需發(fā)生交換？只要不用就換出（或很少覆蓋技術(shù)與交換技術(shù)的分析比較與覆蓋技術(shù)相比，交換技術(shù)不要求用戶給出程序段之間的邏輯覆蓋結(jié)構(gòu)；交換發(fā)生在進(jìn)程或作業(yè)之間，而覆蓋發(fā)生在同一進(jìn)程或作業(yè)內(nèi)。覆蓋只能覆蓋那些與覆蓋段無(wú)關(guān)的程序段。78.覆蓋技術(shù)與交換技術(shù)的分析比較與覆蓋技術(shù)相比，交換技術(shù)不要求用第五章存儲(chǔ)管理主存的管理79.第五章存儲(chǔ)管理主存的管理1.第五章存儲(chǔ)管理5.1存儲(chǔ)管理的功能5.2分區(qū)存儲(chǔ)管理5.3覆蓋和交換5.4頁(yè)式管理5.5段式與段頁(yè)式管理5.6局部性原理與抖動(dòng)問(wèn)題80.第五章存儲(chǔ)管理5.1存儲(chǔ)管理的功能2.5.1存儲(chǔ)管理的功能5.1.1虛擬存儲(chǔ)器5.1.2地址變換5.1.3內(nèi)外存數(shù)據(jù)傳輸?shù)目刂?.1.4內(nèi)存的分配與回收5.1.5內(nèi)存信息的共享與保護(hù)81.5.1存儲(chǔ)管理的功能5.1.1虛擬存儲(chǔ)器3.5.1.1虛擬存儲(chǔ)器內(nèi)存由順序編址的塊組成，內(nèi)存的每個(gè)存儲(chǔ)單元都有一個(gè)編號(hào)，這種編號(hào)稱為內(nèi)存地址（或稱為物理地址，絕對(duì)地址）。內(nèi)存地址的集合稱為內(nèi)存空間（或物理地址空間）。82.5.1.1虛擬存儲(chǔ)器內(nèi)存由順序編址的塊組成，內(nèi)存的每個(gè)存5.1.1虛擬存儲(chǔ)器用戶編程所用的地址稱為邏輯地址（或虛地址）。由邏輯地址組成的空間稱為邏輯地址空間（或虛擬地址空間）。83.5.1.1虛擬存儲(chǔ)器用戶編程所用的地址稱為邏輯地址（或虛5.1.1虛擬存儲(chǔ)器源程序——〉目標(biāo)代碼地址安排？按照物理存儲(chǔ)器中的位置賦予實(shí)際物理地址。優(yōu)點(diǎn)：CPU執(zhí)行目標(biāo)代碼時(shí)的執(zhí)行速度高。缺點(diǎn)：能裝入內(nèi)存并發(fā)執(zhí)行的進(jìn)程數(shù)大大減少，對(duì)于某些較大的進(jìn)程可能會(huì)無(wú)法執(zhí)行；編譯程序?qū)⒎浅?fù)雜，編譯程序必須知道內(nèi)存的當(dāng)前空閑部分及其地址，并且把一個(gè)進(jìn)程的不同程序段連續(xù)地存放起來(lái)84.5.1.1虛擬存儲(chǔ)器源程序——〉目標(biāo)代碼地址安排？

由編譯鏈接程序編譯后鏈接（靜態(tài)、動(dòng)態(tài)）到一個(gè)以0地址為始地址的線性或多維虛擬地址空間（邏輯地址空間）。每個(gè)進(jìn)程都擁有一個(gè)虛擬地址空間。每個(gè)指令或數(shù)據(jù)單元都在這個(gè)虛擬空間中擁有確定的地址，把這個(gè)地址稱為虛擬地址（virtualaddress）(邏輯地址)。地址轉(zhuǎn)換LoadA2003456。。1200物理地址空間LoadAdata1data13456源程序LoadA20034560100200編譯鏈接虛擬地址空間BA=100085.由編譯鏈接程序編譯后鏈接（靜態(tài)、動(dòng)態(tài)）到一個(gè)以0地址為始地5.1.1虛擬存儲(chǔ)器虛擬存儲(chǔ)器：進(jìn)程中的目標(biāo)代碼、數(shù)據(jù)等的虛擬地址組成的虛擬空間稱為虛擬存儲(chǔ)器。86.5.1.1虛擬存儲(chǔ)器虛擬存儲(chǔ)器：進(jìn)程中的目標(biāo)代碼、數(shù)據(jù)等實(shí)現(xiàn)虛擬內(nèi)存的基本原理將程序正在使用的部分內(nèi)容放在內(nèi)存，而暫時(shí)不用的部分放在外存，在需要時(shí)由系統(tǒng)調(diào)入內(nèi)存，并將不需要（或暫不需要）的部分調(diào)出內(nèi)存。由于程序在執(zhí)行時(shí)，在一段時(shí)間內(nèi)一般僅使用它的程序的一部分（或一小部分），所以程序僅有部分裝入內(nèi)存完全能夠正確執(zhí)行。要由操作系統(tǒng)結(jié)合相關(guān)硬件來(lái)完成上述工件，這樣計(jì)算機(jī)好象為用戶提供了一個(gè)容量遠(yuǎn)大于內(nèi)存的存儲(chǔ)器，這個(gè)存儲(chǔ)器稱為虛擬存儲(chǔ)器。

87.實(shí)現(xiàn)虛擬內(nèi)存的基本原理將程序正在使用的部分內(nèi)容放在內(nèi)存，而暫5.1.1虛擬存儲(chǔ)器虛擬存儲(chǔ)器呈現(xiàn)在用戶面前的是一個(gè)在物理上只受內(nèi)存和外存總?cè)萘肯拗频拇鎯?chǔ)系統(tǒng)，這要求存儲(chǔ)管理系統(tǒng)只把進(jìn)程執(zhí)行時(shí)頻繁使用和立即需要的指令與數(shù)據(jù)等存放在內(nèi)存中，而把那些暫時(shí)不需要的部分存放在外存中，待需要時(shí)自動(dòng)調(diào)入，以提高內(nèi)存的利用率和并行執(zhí)行的作業(yè)道數(shù)。虛擬存儲(chǔ)器不考慮物理存儲(chǔ)器的大小和信息存放的實(shí)際位置，只規(guī)定每個(gè)進(jìn)程中互相關(guān)聯(lián)的信息的相對(duì)位置。每個(gè)進(jìn)程都擁有自己的虛擬存儲(chǔ)器，且虛擬存儲(chǔ)器的容量是由計(jì)算機(jī)的地址結(jié)構(gòu)和尋址方式確定的。88.5.1.1虛擬存儲(chǔ)器虛擬存儲(chǔ)器呈現(xiàn)在用戶面前的是一個(gè)在物5.1.2地址變換地址重定位：從虛擬地址到內(nèi)存地址的轉(zhuǎn)換稱為地址重定位，或稱為地址映射。地址映射的方式：1、靜態(tài)地址重定位2、動(dòng)態(tài)地址重定位89.5.1.2地址變換地址重定位：從虛擬地址到內(nèi)存地址的轉(zhuǎn)1、靜態(tài)地址重定位在虛擬空間程序執(zhí)行之前由裝配程序完成地址映射的工作。不能實(shí)現(xiàn)虛擬存儲(chǔ)器假定程序裝入內(nèi)存的首地址為BA，程序地址為VA，內(nèi)存地址為MA，則地址映射按下式進(jìn)行：MA=(BA)+(VA)。90.1、靜態(tài)地址重定位在虛擬空間程序執(zhí)行之前由裝配程序完成地址映例程序裝入內(nèi)存的首地址為1000，則裝配程序就按MA=1000+VA對(duì)程序中所有地址部分進(jìn)行修改，修改后指令LoadA，200就變?yōu)長(zhǎng)oadA，120091.例程序裝入內(nèi)存的首地址為1000，則裝配程序就按MA=100靜態(tài)地址重定位的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：不需要硬件的支持。缺點(diǎn)：程序必須占用連續(xù)的內(nèi)存空間，程序和數(shù)據(jù)不能共享；程序一旦裝入內(nèi)存之后就不能再移動(dòng)，并且必須在程序執(zhí)行之前將有關(guān)部分全部裝入。92.靜態(tài)地址重定位的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：不需要硬件的支持。14.2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位是在程序執(zhí)行的過(guò)程中，在CPU訪問(wèn)內(nèi)存之前，將要訪問(wèn)的程序地址轉(zhuǎn)換為內(nèi)存地址。一般來(lái)說(shuō)這種轉(zhuǎn)換是由專門的硬件機(jī)構(gòu)來(lái)完成的。在地址重定位機(jī)構(gòu)中，有一個(gè)基地址寄存器BR和一個(gè)程序地址寄存器VR，一個(gè)內(nèi)存地址寄存器MR。MA=(BR)+(VR)93.2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位是在程序執(zhí)行的過(guò)程中，在CP2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位的具體過(guò)程：程序裝入內(nèi)存后，它所占用的內(nèi)存區(qū)的首地址由系統(tǒng)送入基地址寄存器BR中。在程序執(zhí)行的過(guò)程中，若要訪問(wèn)內(nèi)存，將訪問(wèn)的邏輯地址送入程序地址寄存器VR中。地址轉(zhuǎn)換機(jī)構(gòu)把VR和BR中的內(nèi)容相加，并將結(jié)果送入MR中，作為實(shí)際訪問(wèn)的物理地址。94.2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位的具體過(guò)程：16.圖5.3動(dòng)態(tài)地址重定位95.17.2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位的優(yōu)點(diǎn)可以對(duì)內(nèi)存進(jìn)行非連續(xù)分配。程序占用的內(nèi)存空間是動(dòng)態(tài)可變的，當(dāng)程序從某個(gè)存儲(chǔ)區(qū)移到另一個(gè)區(qū)域時(shí)，只需要修改相應(yīng)的寄存器BR的內(nèi)容即可。提供了實(shí)現(xiàn)虛擬存儲(chǔ)器的基礎(chǔ)。一個(gè)程序不一定要求占用一個(gè)連續(xù)的內(nèi)存空間。可以部分地裝入程序運(yùn)行。便于多個(gè)進(jìn)程共享同一個(gè)程序的代碼。96.2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位的優(yōu)點(diǎn)18.2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位的代價(jià)：需要硬件的支持。實(shí)現(xiàn)存儲(chǔ)管理的軟件算法較為復(fù)雜。97.2、動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位的代價(jià)：19.5.1.3內(nèi)外存數(shù)據(jù)傳輸?shù)目刂苾?nèi)外存數(shù)據(jù)傳輸?shù)目刂疲河脩舫绦蜃约嚎刂疲焊采w技術(shù)——用戶負(fù)擔(dān)很大，程序段的最大長(zhǎng)度受內(nèi)存容量限制，不能實(shí)現(xiàn)虛擬存儲(chǔ)器。操作系統(tǒng)控制：交換(swapping)方式：不同的進(jìn)程或作業(yè)之間請(qǐng)求調(diào)入(ondemand)方式和預(yù)調(diào)入(onprefetch)方式98.5.1.3內(nèi)外存數(shù)據(jù)傳輸?shù)目刂苾?nèi)外存數(shù)據(jù)傳輸?shù)目刂疲?05.1.4內(nèi)存的分配與回收要完成內(nèi)存的分配和回收工作，要求設(shè)計(jì)者選擇和確定以下幾種策略和結(jié)構(gòu)：分配結(jié)構(gòu)調(diào)入策略放置策略交換策略回收策略99.5.1.4內(nèi)存的分配與回收要完成內(nèi)存的分配和回收工作，5.1.4內(nèi)存的分配與回收分配結(jié)構(gòu)—分配結(jié)構(gòu)是用來(lái)登記內(nèi)存使用情況的數(shù)據(jù)結(jié)構(gòu)。如空閑區(qū)表、空閑區(qū)隊(duì)列等。調(diào)入策略—用戶程序在何時(shí)、怎樣調(diào)入內(nèi)存的策略。放置策略—用戶程序調(diào)入內(nèi)存時(shí)，確定將其放置在何處的策略。100.5.1.4內(nèi)存的分配與回收分配結(jié)構(gòu)—分配結(jié)構(gòu)是用來(lái)登記5.1.4內(nèi)存的分配與回收交換策略—當(dāng)需要將某個(gè)用戶程序調(diào)入內(nèi)存而內(nèi)存空間又不夠時(shí)，就要確定哪個(gè)或哪些程序可以從內(nèi)存中移走?；厥詹呗浴_定回收的時(shí)機(jī)和對(duì)所回收的內(nèi)存空閑區(qū)和已存在的內(nèi)存空閑區(qū)進(jìn)行調(diào)整。101.5.1.4內(nèi)存的分配與回收交換策略—當(dāng)需要將某個(gè)用戶程5.1.5內(nèi)存信息的共享與保護(hù)保證在內(nèi)存中的多道程序只能在給定的存儲(chǔ)區(qū)域內(nèi)活動(dòng)并互不產(chǎn)生干擾。包括：防止地址越界防止越權(quán)(對(duì)共享區(qū)有訪問(wèn)權(quán))102.5.1.5內(nèi)存信息的共享與保護(hù)保證在內(nèi)存中的多道程序只能5.1.5內(nèi)存信息的共享與保護(hù)內(nèi)存保護(hù)的方法：硬件法、軟件法和軟硬件法。上下界保護(hù)法：硬件法1、在CPU中設(shè)置一對(duì)下限寄存器和上限寄存器存放用戶作業(yè)在主存中的下限和上限地址2、每當(dāng)CPU要訪問(wèn)主存，硬件自動(dòng)將被訪問(wèn)的主存地址與界限寄存器的內(nèi)容進(jìn)行比較，以判斷是否越界3、如果未越界，則按此地址訪問(wèn)主存，否則將產(chǎn)生程序中斷——越界中斷（存儲(chǔ)保護(hù)中斷）103.5.1.5內(nèi)存信息的共享與保護(hù)內(nèi)存保護(hù)的方法：硬件法、軟圖5.4上、下界寄存器保護(hù)法104.26.5.1.5內(nèi)存信息的共享與保護(hù)保護(hù)鍵法：軟件法

為每一個(gè)被保護(hù)的存儲(chǔ)塊分配一個(gè)單獨(dú)的保護(hù)鍵。在程序狀態(tài)字中設(shè)置相應(yīng)的保護(hù)鍵開(kāi)關(guān)字段，訪問(wèn)過(guò)程中比較保護(hù)開(kāi)關(guān)字段的內(nèi)容和保護(hù)鍵是否匹配，匹配則允許訪問(wèn)，否則產(chǎn)生訪問(wèn)出錯(cuò)中斷。105.5.1.5內(nèi)存信息的共享與保護(hù)保護(hù)鍵法：軟件法27.圖5.5保護(hù)鍵保護(hù)法106.28.5.1.5內(nèi)存信息的共享與保護(hù)界限寄存器與CPU的用戶態(tài)或核心態(tài)工作方式相結(jié)合的保護(hù)方式。軟硬件法用戶態(tài)進(jìn)程只能訪問(wèn)那些在界限寄存器所規(guī)定范圍內(nèi)的內(nèi)存部分，而核心態(tài)進(jìn)程則可以訪問(wèn)整個(gè)內(nèi)存地址空間。107.5.1.5內(nèi)存信息的共享與保護(hù)界限寄存器與CPU的用戶態(tài)5.2分區(qū)存儲(chǔ)管理把整個(gè)內(nèi)存劃分為若干大小不等的區(qū)域，操作系統(tǒng)占用一個(gè)區(qū)域，其它區(qū)域供系統(tǒng)中的多個(gè)進(jìn)程共享，這種方法稱為分區(qū)存儲(chǔ)管理。5.2.1分區(qū)存儲(chǔ)管理的基本原理5.2.2分區(qū)的分配與回收5.2.3有關(guān)分區(qū)管理其他問(wèn)題討論108.5.2分區(qū)存儲(chǔ)管理把整個(gè)內(nèi)存劃分為若干大小不等的區(qū)域，5.2.1分區(qū)存儲(chǔ)管理的基本原理基本原理：給每一個(gè)內(nèi)存中的進(jìn)程劃分一塊適當(dāng)大小的存儲(chǔ)區(qū),以連續(xù)存儲(chǔ)各進(jìn)程的程序和數(shù)據(jù)，使各進(jìn)程得以并發(fā)執(zhí)行。這是最簡(jiǎn)單的一種存儲(chǔ)管理，按分區(qū)劃分的時(shí)機(jī)可分為：

1、固定分區(qū)2、動(dòng)態(tài)分區(qū)109.5.2.1分區(qū)存儲(chǔ)管理的基本原理基本原理：給每一個(gè)內(nèi)存中的1、固定分區(qū)固定分區(qū)：把內(nèi)存固定地劃分為若干個(gè)大小不等的區(qū)域。分區(qū)的劃分由計(jì)算機(jī)的操作員或者由操作系統(tǒng)給出，并給出分區(qū)說(shuō)明表。在調(diào)度作業(yè)時(shí)，由存儲(chǔ)管理根據(jù)所需量在分區(qū)說(shuō)明表中找出一個(gè)單元分配給它。110.1、固定分區(qū)固定分區(qū)：把內(nèi)存固定地劃分為若干個(gè)大小不等的區(qū)域1、固定分區(qū)分區(qū)說(shuō)明表分區(qū)號(hào)大小(KB)始址狀態(tài)1820已分配23228已分配36460已分配4132124未分配111.1、固定分區(qū)分區(qū)說(shuō)明表分區(qū)號(hào)大小(KB)始址狀態(tài)1820已分圖5.6固定分區(qū)法112.34.1、固定分區(qū)在作業(yè)大小和出現(xiàn)頻率均已知的情況下，固定分區(qū)是合適的。在這種情況下分區(qū)的大小選擇與作業(yè)大小相當(dāng)，這樣內(nèi)存的使用效率較高。但是若作業(yè)的大小和出現(xiàn)的頻率不知道時(shí)，勢(shì)必造成分區(qū)的大小和作業(yè)的大小相差甚遠(yuǎn)，這樣就會(huì)造成存儲(chǔ)空間的浪費(fèi)，從而影響整個(gè)系統(tǒng)的效率。113.1、固定分區(qū)在作業(yè)大小和出現(xiàn)頻率均已知的情況下，固定分區(qū)是合2、動(dòng)態(tài)分區(qū)動(dòng)態(tài)分區(qū)：在系統(tǒng)運(yùn)行的過(guò)程中建立分區(qū)，并使分區(qū)的大小剛好與作業(yè)的大小相等。這種存儲(chǔ)管理的方法解決了固定分區(qū)嚴(yán)重浪費(fèi)內(nèi)存的問(wèn)題。是一種較為實(shí)用的存儲(chǔ)管理方法。114.2、動(dòng)態(tài)分區(qū)動(dòng)態(tài)分區(qū)：在系統(tǒng)運(yùn)行的過(guò)程中建立分區(qū)，并使分區(qū)的圖5.7動(dòng)態(tài)分區(qū)內(nèi)存初始分配情況115.37.2、動(dòng)態(tài)分區(qū)在實(shí)現(xiàn)動(dòng)態(tài)分區(qū)分配的時(shí)候需要涉及到以下三個(gè)方面的問(wèn)題：動(dòng)態(tài)分配中所用到的數(shù)據(jù)結(jié)構(gòu)；分區(qū)的分配算法；分區(qū)的分配和回收操作。116.2、動(dòng)態(tài)分區(qū)在實(shí)現(xiàn)動(dòng)態(tài)分區(qū)分配的時(shí)候需要涉及到以下三個(gè)方面2、動(dòng)態(tài)分區(qū)實(shí)現(xiàn)動(dòng)態(tài)分區(qū)的數(shù)據(jù)結(jié)構(gòu)：在動(dòng)態(tài)分區(qū)存儲(chǔ)管理中，要有相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來(lái)登記空閑區(qū)的說(shuō)明信息，它包括空閑區(qū)的大小和位置。其數(shù)據(jù)結(jié)構(gòu)有：分區(qū)說(shuō)明表、可用分區(qū)表（或自由鏈）、請(qǐng)求表。分區(qū)說(shuō)明表可用分區(qū)表：用于為內(nèi)存中每個(gè)還沒(méi)有分區(qū)設(shè)置一個(gè)表項(xiàng)，每個(gè)分區(qū)表項(xiàng)包含分區(qū)序號(hào)、分區(qū)起始地址以及分區(qū)大小。（占用內(nèi)存）117.2、動(dòng)態(tài)分區(qū)實(shí)現(xiàn)動(dòng)態(tài)分區(qū)的數(shù)據(jù)結(jié)構(gòu)：39.2、動(dòng)態(tài)分區(qū)實(shí)現(xiàn)動(dòng)態(tài)分區(qū)的數(shù)據(jù)結(jié)構(gòu)：自由鏈：利用每個(gè)內(nèi)存空閑區(qū)的頭幾個(gè)單元存放本空閑區(qū)的大小和下個(gè)空閑區(qū)的起始地址，將所有空閑區(qū)組成一條鏈。（不占用內(nèi)存）

請(qǐng)求表：表的每個(gè)表目描述請(qǐng)求內(nèi)存資源的作業(yè)或進(jìn)程號(hào)以及所請(qǐng)求的內(nèi)存大小。118.2、動(dòng)態(tài)分區(qū)實(shí)現(xiàn)動(dòng)態(tài)分區(qū)的數(shù)據(jù)結(jié)構(gòu)：40.圖5.9可用表、自由鏈及請(qǐng)求表119.41.圖5.8內(nèi)存分配變化過(guò)程120.42.5.2.2分區(qū)的分配與回收1、固定分區(qū)的分配與回收2、動(dòng)態(tài)分區(qū)時(shí)的分配與回收3、動(dòng)態(tài)分區(qū)時(shí)的回收與拼接4、幾種分配算法的比較121.5.2.2分區(qū)的分配與回收1、固定分區(qū)的分配與回收43.1、固定分區(qū)的分配與回收分配：當(dāng)用戶程序要裝入執(zhí)行時(shí)，通過(guò)請(qǐng)求表提出內(nèi)存分配要求和所要求的內(nèi)存空間大小。存儲(chǔ)管理程序根據(jù)請(qǐng)求表要求查詢分區(qū)說(shuō)明表，從中找出一個(gè)滿足要求的空閑分區(qū)，將其分配給申請(qǐng)者。P117圖回收：回收時(shí)管理程序只需將對(duì)應(yīng)的分區(qū)狀態(tài)置為未使用即可。

122.1、固定分區(qū)的分配與回收分配：當(dāng)用戶程序要裝入執(zhí)行時(shí)，通過(guò)請(qǐng)2、動(dòng)態(tài)分區(qū)時(shí)的分配與回收主要解決的三個(gè)問(wèn)題:(1)對(duì)于請(qǐng)求表中的要求內(nèi)存長(zhǎng)度，從可用表或自由鏈中尋找出合適的空閑區(qū)分配程序。(2)分配空閑區(qū)之后，更新可用表或自由鏈。(3)進(jìn)程或作業(yè)釋放內(nèi)存資源時(shí)，和相鄰的空閑區(qū)進(jìn)行鏈接合并，更新可用表或自由鏈。123.2、動(dòng)態(tài)分區(qū)時(shí)的分配與回收主要解決的三個(gè)問(wèn)題:45.2、動(dòng)態(tài)分區(qū)時(shí)的分配與回收從可用表或自由鏈中尋找空閑區(qū)的常用的三種方法：最先適應(yīng)法(firstfitalgorithm)最佳適應(yīng)法(bestfitalgorithm)最壞適應(yīng)法(worstfitalgoriathm)這三種方法要求可用表或自由鏈按不同的方式排列。124.2、動(dòng)態(tài)分區(qū)時(shí)的分配與回收從可用表或自由鏈中尋找空閑區(qū)的常用最先適應(yīng)法要求可用表或自由鏈按起始地址遞增的次序排列。分配：當(dāng)進(jìn)程申請(qǐng)大小為SIZE的內(nèi)存時(shí)，存儲(chǔ)管理程序從空閑區(qū)表的第一個(gè)表目開(kāi)始查詢，直到首次找到等于或大于SIZE的空閑區(qū)。從該區(qū)中劃出大小為SIZE的分區(qū)分配給進(jìn)程，余下的部分仍作為一個(gè)空閑區(qū)留在空閑區(qū)表中，但要修改其首址和大小。125.最先適應(yīng)法要求可用表或自由鏈按起始地址遞增的次序排列。47.最先適應(yīng)法回收：按釋放區(qū)的首址，查詢空閑區(qū)表，若有與釋放區(qū)相鄰的空閑區(qū)，則合并到相鄰的空閑區(qū)中，并修改該區(qū)的大小和首址，否則，把釋放區(qū)作為一個(gè)空閑區(qū)，將其大小和首址按照首地址大小遞增的順序插入到空閑區(qū)表的適當(dāng)位置。126.最先適應(yīng)法回收：按釋放區(qū)的首址，查詢空閑區(qū)表，若有與釋放區(qū)相最先適應(yīng)法的優(yōu)點(diǎn)釋放某一存儲(chǔ)區(qū)時(shí)，若與空閑區(qū)相鄰則合并到相鄰空閑分區(qū)中去，這種情況并不改變?cè)搮^(qū)在表中的位置，只要修改其大小或首址。這種算法是盡可能地利用低地址空間，從而保證高地址空間有較大的空閑區(qū)。127.最先適應(yīng)法的優(yōu)點(diǎn)釋放某一存儲(chǔ)區(qū)時(shí)，若與空閑區(qū)相鄰則合并到相鄰最佳適應(yīng)法要求按空閑區(qū)大小從小到大的次序組成空閑區(qū)表（隊(duì)列）。分配：當(dāng)用戶作業(yè)或進(jìn)程申請(qǐng)一個(gè)存儲(chǔ)區(qū)時(shí)，存儲(chǔ)管理程序從表頭開(kāi)始查找，當(dāng)找到第一個(gè)滿足要求的空閑區(qū)時(shí)，停止查找，并且這個(gè)空閑區(qū)是最佳的空閑區(qū)（選中的空閑區(qū)是滿足要求的最小空閑區(qū)）。如果該空閑區(qū)大于請(qǐng)求表中的請(qǐng)求長(zhǎng)度，則與最先適應(yīng)法時(shí)相同，將減去請(qǐng)求長(zhǎng)度后的剩余空閑區(qū)部分留在可用表中。128.最佳適應(yīng)法要求按空閑區(qū)大小從小到大的次序組成空閑區(qū)表（隊(duì)列）最佳適應(yīng)法回收：按釋放區(qū)的首址，查詢空閑區(qū)表（隊(duì)列），若有與釋放區(qū)相鄰的空閑區(qū)，則合并到相鄰的空閑區(qū)中，并修改該區(qū)的大小和首址，否則，把釋放區(qū)作為一個(gè)空閑區(qū)插入空閑區(qū)表（隊(duì)列）。分配和回收后要對(duì)空閑區(qū)表（隊(duì)列）重新排序。129.最佳適應(yīng)法回收：按釋放區(qū)的首址，查詢空閑區(qū)表（隊(duì)列），若有最佳適應(yīng)算法的優(yōu)點(diǎn)在系統(tǒng)中若存在一個(gè)與申請(qǐng)分區(qū)大小相等的空閑區(qū)，必定會(huì)被選中，而最先適應(yīng)法則不一定。若系統(tǒng)中不存在與申請(qǐng)分區(qū)大小相等的空閑區(qū)，則選中的空閑區(qū)是滿足要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。130.最佳適應(yīng)算法的優(yōu)點(diǎn)在系統(tǒng)中若存在一個(gè)與申請(qǐng)分區(qū)大小相等的空閑最佳適應(yīng)算法的缺點(diǎn)空閑區(qū)的大小一般與申請(qǐng)分區(qū)大小不相等，因此將其一分為二，留下來(lái)的空閑區(qū)一般情況下是很小的，以致無(wú)法使用。隨著時(shí)間的推移，系統(tǒng)中的小空閑區(qū)會(huì)越來(lái)越多，從而造成存儲(chǔ)區(qū)的大量浪費(fèi)。

131.最佳適應(yīng)算法的缺點(diǎn)空閑區(qū)的大小一般與申請(qǐng)分區(qū)大小不相等，因最壞適應(yīng)算法要求空閑區(qū)按由大至小遞減的順序組織空閑區(qū)表（或隊(duì)列）。分配：進(jìn)程申請(qǐng)一個(gè)大小為SIZE的存儲(chǔ)區(qū)時(shí)，總是檢查空閑區(qū)表的第一個(gè)空閑區(qū)的大小是否大于或等于SIZE。若空閑區(qū)小于SIZE，則分配失?。环駝t從空閑區(qū)中分配SIZE的存儲(chǔ)區(qū)給用戶，然后修改和調(diào)整空閑區(qū)表。132.最壞適應(yīng)算法要求空閑區(qū)按由大至小遞減的順序組織空閑區(qū)表（或最壞適應(yīng)算法回收：按釋放區(qū)的首址，查詢空閑區(qū)表（隊(duì)列），若有與釋放區(qū)相鄰的空閑區(qū)，則合并到相鄰的空閑區(qū)中，并修改該區(qū)的大小和首址，否則，把釋放區(qū)作為一個(gè)空閑區(qū)插入空閑區(qū)表（隊(duì)列）。分配和回收后要對(duì)空閑區(qū)表（隊(duì)列）重新排序。133.最壞適應(yīng)算法回收：按釋放區(qū)的首址，查詢空閑區(qū)表（隊(duì)列），若有最壞適應(yīng)算法的優(yōu)點(diǎn)當(dāng)程序裝入內(nèi)存中最大的空閑區(qū)后，剩下的空閑區(qū)還可能相當(dāng)大，還能裝下較大的程序。每次僅作一次查詢工作。134.最壞適應(yīng)算法的優(yōu)點(diǎn)當(dāng)程序裝入內(nèi)存中最大的空閑區(qū)后，剩下的空閑3、動(dòng)態(tài)分區(qū)時(shí)分區(qū)的回收當(dāng)某個(gè)進(jìn)程釋放某存儲(chǔ)區(qū)時(shí)，系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰，若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)中去，否則把釋放區(qū)作為一個(gè)空閑區(qū)插入到空閑區(qū)表的適當(dāng)位置。

135.3、動(dòng)態(tài)分區(qū)時(shí)分區(qū)的回收當(dāng)某個(gè)進(jìn)程釋放某存儲(chǔ)區(qū)時(shí)，系統(tǒng)首先檢圖5.12空閑區(qū)的合并136.58.空閑區(qū)的合并釋放區(qū)與上下兩空閑區(qū)相鄰：將三個(gè)空閑區(qū)合并為一個(gè)空閑區(qū)。新空閑區(qū)的起始地址為上空閑區(qū)的起始地址，大小為三個(gè)空閑區(qū)之和?？臻e區(qū)合并后，取消可用表或自由鏈中下空閑區(qū)的表目項(xiàng)或鏈指針，修改上空閑區(qū)的對(duì)應(yīng)項(xiàng)。釋放區(qū)只與上空閑區(qū)相鄰：將釋放區(qū)與上空閑區(qū)合并為一個(gè)空閑區(qū)，其起始地址為上空閑區(qū)的起始地址，大小為上空閑區(qū)與釋放區(qū)之和。合并后，修改上空閑區(qū)對(duì)應(yīng)的可用表的表目項(xiàng)或自由鏈指針。137.空閑區(qū)的合并釋放區(qū)與上下兩空閑區(qū)相鄰：將三個(gè)空閑區(qū)合并為一個(gè)空閑區(qū)的合并釋放區(qū)與下空閑區(qū)相鄰：將釋放區(qū)與下空閑區(qū)合并，并將釋放區(qū)的起始地址作為合并區(qū)的起始地址。合并區(qū)的長(zhǎng)度為釋放區(qū)與下空閑區(qū)之和。合并后修改可用表或自由鏈中相應(yīng)的表目項(xiàng)或鏈指針。釋放區(qū)不與任何空閑區(qū)相鄰：釋放區(qū)作為一個(gè)新可用區(qū)插入可用表或自由鏈。138.空閑區(qū)的合并釋放區(qū)與下空閑區(qū)相鄰：將釋放區(qū)與下空閑區(qū)合并，并4、三種分配算法的比較三種算法的優(yōu)缺點(diǎn)比較搜索速度：最先適應(yīng)算法具有最佳性能，最佳適應(yīng)算法和最壞適應(yīng)算法都要求把不同大小的空閑區(qū)按大小進(jìn)行排隊(duì)；回收過(guò)程：最先適應(yīng)算法具有最佳性能，因?yàn)樽罴堰m應(yīng)算法和最壞適應(yīng)算法都必須重新調(diào)整空閑區(qū)的位置；空閑區(qū)利用：最佳適應(yīng)法找到的空閑區(qū)是最佳的，但是會(huì)造成內(nèi)存碎片較多，影響內(nèi)存利用率，而最壞適用法的內(nèi)存碎片最少，但是對(duì)內(nèi)存的請(qǐng)求較多的進(jìn)程有可能分配失敗。總之，三種算法各有所長(zhǎng)，針對(duì)不同的請(qǐng)求隊(duì)列，它們的效率和功能是不一樣的。139.4、三種分配算法的比較三種算法的優(yōu)缺點(diǎn)比較61.4、三種分配算法的比較上述三種放置策略各有利弊，到底哪種最好不能一概而論，而應(yīng)針對(duì)具體作業(yè)序列來(lái)分析。對(duì)于某一作業(yè)序列來(lái)說(shuō)，某種算法能將該作業(yè)序列中所有作業(yè)安置完畢，那么我們說(shuō)該算法對(duì)這一作業(yè)序列是合適的。對(duì)于某一算法而言，如它不能立即滿足某一要求，而其它算法卻可以滿足此要求，則這一算法對(duì)該作業(yè)序列是不合適的。140.4、三種分配算法的比