操作系統(tǒng)第5章_1剖析

1、1第五章、存儲(chǔ)管理第五章、存儲(chǔ)管理5.15.1存儲(chǔ)管理的功能存儲(chǔ)管理的功能5.25.2分區(qū)存儲(chǔ)管理分區(qū)存儲(chǔ)管理5.35.3覆蓋與交換技術(shù)覆蓋與交換技術(shù)5.45.4頁(yè)式管理頁(yè)式管理 5.55.5段式管理與段頁(yè)式管理段式管理與段頁(yè)式管理5.65.6局部性原理和抖動(dòng)問(wèn)題局部性原理和抖動(dòng)問(wèn)題25.1存儲(chǔ)管理的功能存儲(chǔ)管理的功能 內(nèi)存：與內(nèi)存：與CPU直接交換數(shù)據(jù)的場(chǎng)所。直接交換數(shù)據(jù)的場(chǎng)所。存儲(chǔ)器存儲(chǔ)器外存：與內(nèi)存交換信息。外存：與內(nèi)存交換信息。存儲(chǔ)管理存儲(chǔ)管理 內(nèi)存管理內(nèi)存管理文件管理文件管理 外存管理外存管理3存儲(chǔ)管理的重要性存儲(chǔ)管理的重要性直接存取要求直接存取要求: :1 1、內(nèi)存速度盡量快到與、

2、內(nèi)存速度盡量快到與CPUCPU取指速度相匹配；取指速度相匹配；2 2、大到能裝下當(dāng)前運(yùn)行的程序與數(shù)據(jù)；、大到能裝下當(dāng)前運(yùn)行的程序與數(shù)據(jù)；否則，否則，CPUCPU執(zhí)行速度就會(huì)受到內(nèi)存速度和容執(zhí)行速度就會(huì)受到內(nèi)存速度和容量的影響而得不到充分發(fā)揮。量的影響而得不到充分發(fā)揮。 4存儲(chǔ)管理的功能存儲(chǔ)管理的功能一、內(nèi)存的分配和回收一、內(nèi)存的分配和回收二、內(nèi)存信息的保護(hù)二、內(nèi)存信息的保護(hù)三、提高內(nèi)存的利用率三、提高內(nèi)存的利用率 四、四、“擴(kuò)充擴(kuò)充”內(nèi)存容量?jī)?nèi)存容量 虛擬存儲(chǔ)器虛擬存儲(chǔ)器5一、內(nèi)存的分配和回收一、內(nèi)存的分配和回收1 1、對(duì)內(nèi)存分區(qū)（系統(tǒng)區(qū)、對(duì)內(nèi)存分區(qū)（系統(tǒng)區(qū)/ /用戶(hù)區(qū)），記住每個(gè)存儲(chǔ)區(qū)狀態(tài)用

3、戶(hù)區(qū)），記住每個(gè)存儲(chǔ)區(qū)狀態(tài)（已分配（已分配/ /空閑），空閑區(qū)表空閑），空閑區(qū)表/ /隊(duì)列；隊(duì)列； 靜態(tài)數(shù)據(jù)結(jié)構(gòu)靜態(tài)數(shù)據(jù)結(jié)構(gòu)2 2、實(shí)施分配，把數(shù)據(jù)放入哪段內(nèi)存，放置后修改分配、實(shí)施分配，把數(shù)據(jù)放入哪段內(nèi)存，放置后修改分配/ /空閑空閑記錄；記錄； 放置、交換、調(diào)入策略放置、交換、調(diào)入策略3 3、回收一段存儲(chǔ)區(qū)域，修改空閑記錄。、回收一段存儲(chǔ)區(qū)域，修改空閑記錄。 回收策略回收策略6二、內(nèi)存信息的保護(hù)二、內(nèi)存信息的保護(hù)目標(biāo)：目標(biāo)：1、保證各道程序只在自己存儲(chǔ)區(qū)內(nèi)執(zhí)行，互不干擾，、保證各道程序只在自己存儲(chǔ)區(qū)內(nèi)執(zhí)行，互不干擾，防止越界破壞；防止越界破壞；2、多道程序合法地共享系統(tǒng)或用戶(hù)程序、數(shù)據(jù)。、

4、多道程序合法地共享系統(tǒng)或用戶(hù)程序、數(shù)據(jù)。保護(hù)方法：保護(hù)方法：1、上下界保護(hù)法：、上下界保護(hù)法： （硬件法）（硬件法）2、保護(hù)鍵法：、保護(hù)鍵法： （軟件法）（軟件法）3、界限寄存器與、界限寄存器與CPU用戶(hù)態(tài)和核心態(tài)工作方式結(jié)合：用戶(hù)態(tài)和核心態(tài)工作方式結(jié)合：71、上下界保護(hù)法：、上下界保護(hù)法： （硬件法）（硬件法）為每一進(jìn)程設(shè)置一對(duì)上下界寄存器，裝入被保護(hù)為每一進(jìn)程設(shè)置一對(duì)上下界寄存器，裝入被保護(hù)程序的起始、終止地址；程序的起始、終止地址；每次訪問(wèn)均檢查是否在此地址范圍內(nèi)，若越界，每次訪問(wèn)均檢查是否在此地址范圍內(nèi)，若越界，產(chǎn)生越界中斷。產(chǎn)生越界中斷。82、保護(hù)鍵法：、保護(hù)鍵法： （軟件法）（軟件

5、法）1 1）為每個(gè)被保護(hù)存儲(chǔ)區(qū)分配一個(gè)單獨(dú)的保護(hù)鍵，可）為每個(gè)被保護(hù)存儲(chǔ)區(qū)分配一個(gè)單獨(dú)的保護(hù)鍵，可同時(shí)配以保護(hù)級(jí)別（讀寫(xiě)、讀、寫(xiě)保護(hù)）；同時(shí)配以保護(hù)級(jí)別（讀寫(xiě)、讀、寫(xiě)保護(hù)）；2 2）每個(gè)進(jìn)程的程序狀態(tài)字中設(shè)一開(kāi)關(guān)字節(jié)存儲(chǔ)與其）每個(gè)進(jìn)程的程序狀態(tài)字中設(shè)一開(kāi)關(guān)字節(jié)存儲(chǔ)與其能訪問(wèn)的存儲(chǔ)區(qū)保護(hù)鍵一致的開(kāi)關(guān)代碼；能訪問(wèn)的存儲(chǔ)區(qū)保護(hù)鍵一致的開(kāi)關(guān)代碼；3 3）進(jìn)程訪問(wèn)存儲(chǔ)區(qū)時(shí)，若開(kāi)關(guān)代碼與其保護(hù)鍵匹配，）進(jìn)程訪問(wèn)存儲(chǔ)區(qū)時(shí)，若開(kāi)關(guān)代碼與其保護(hù)鍵匹配，可以以規(guī)定的方式進(jìn)行訪問(wèn)?？梢砸砸?guī)定的方式進(jìn)行訪問(wèn)。不匹配：不匹配：R/W：不允許訪問(wèn)：不允許訪問(wèn)W：只讀不寫(xiě)只讀不寫(xiě)93、界限寄存器與、界限寄存器與CPU用戶(hù)態(tài)

6、和核心態(tài)工作方式結(jié)合用戶(hù)態(tài)和核心態(tài)工作方式結(jié)合 （軟硬結(jié)合）（軟硬結(jié)合）用戶(hù)態(tài)進(jìn)程只能訪問(wèn)界限寄存器規(guī)定范圍的區(qū)域；用戶(hù)態(tài)進(jìn)程只能訪問(wèn)界限寄存器規(guī)定范圍的區(qū)域；核心態(tài)進(jìn)程可以訪問(wèn)整個(gè)內(nèi)存。核心態(tài)進(jìn)程可以訪問(wèn)整個(gè)內(nèi)存。10三、提高內(nèi)存的利用率三、提高內(nèi)存的利用率1、減少碎片的產(chǎn)生避免浪費(fèi)、減少碎片的產(chǎn)生避免浪費(fèi) 是否支持非連續(xù)裝入？是否支持非連續(xù)裝入？2、使內(nèi)存始終保存較忙的進(jìn)程加快周轉(zhuǎn)、使內(nèi)存始終保存較忙的進(jìn)程加快周轉(zhuǎn)1）覆蓋覆蓋：邏輯上獨(dú)立不會(huì)同時(shí)執(zhí)行的多個(gè)程序段共享一段存儲(chǔ)空間；邏輯上獨(dú)立不會(huì)同時(shí)執(zhí)行的多個(gè)程序段共享一段存儲(chǔ)空間；2）交換交換：內(nèi)存等待狀態(tài)的進(jìn)程換出，外存就緒狀態(tài)的調(diào)入；內(nèi)

7、存等待狀態(tài)的進(jìn)程換出，外存就緒狀態(tài)的調(diào)入；3）請(qǐng)求請(qǐng)求/預(yù)先調(diào)入預(yù)先調(diào)入：把馬上需要把馬上需要/預(yù)測(cè)不久會(huì)訪問(wèn)的的信息調(diào)入預(yù)測(cè)不久會(huì)訪問(wèn)的的信息調(diào)入；11四、四、“擴(kuò)充擴(kuò)充”內(nèi)存容量?jī)?nèi)存容量 虛擬存儲(chǔ)器虛擬存儲(chǔ)器物理存儲(chǔ)器物理存儲(chǔ)器 = 內(nèi)存（價(jià)高、容量小）內(nèi)存（價(jià)高、容量?。?+ 外存（速度慢）外存（速度慢）局限：局限：1）大作業(yè)的長(zhǎng)度）大作業(yè)的長(zhǎng)度 內(nèi)存的容量?jī)?nèi)存的容量2）內(nèi)存只能裝入有限的幾個(gè)進(jìn)程，制約了并發(fā)進(jìn)程的數(shù)量。）內(nèi)存只能裝入有限的幾個(gè)進(jìn)程，制約了并發(fā)進(jìn)程的數(shù)量。解決辦法：解決辦法：將內(nèi)存、外存以某種方式統(tǒng)一起來(lái)，通過(guò)地址變換和信息的調(diào)將內(nèi)存、外存以某種方式統(tǒng)一起來(lái)，通過(guò)地址變換

8、和信息的調(diào)入調(diào)出，實(shí)現(xiàn)以小的內(nèi)存運(yùn)行更大、更多的程序。入調(diào)出，實(shí)現(xiàn)以小的內(nèi)存運(yùn)行更大、更多的程序。 目的：目的：使用戶(hù)在編制程序時(shí)不受內(nèi)存容量的限制。使用戶(hù)在編制程序時(shí)不受內(nèi)存容量的限制。121、存儲(chǔ)空間與地址空間：、存儲(chǔ)空間與地址空間：存儲(chǔ)空間存儲(chǔ)空間：內(nèi)存中存儲(chǔ)信息的物理單元的集合。內(nèi)存中存儲(chǔ)信息的物理單元的集合。單元的編號(hào)稱(chēng)為單元的編號(hào)稱(chēng)為物理地址（絕對(duì)地址）物理地址（絕對(duì)地址）。地址空間地址空間：目標(biāo)出現(xiàn)所限定的地址范圍，是程序和數(shù)據(jù)要使用目標(biāo)出現(xiàn)所限定的地址范圍，是程序和數(shù)據(jù)要使用 的的單元地址集合，由單元地址集合，由0開(kāi)始順序編號(hào)，反映了持續(xù)指令的執(zhí)行順序。開(kāi)始順序編號(hào)，反映了持續(xù)

9、指令的執(zhí)行順序。單元的編號(hào)稱(chēng)為單元的編號(hào)稱(chēng)為邏輯地址（相對(duì)地址）邏輯地址（相對(duì)地址）。13 作業(yè)A的邏輯地址空間作業(yè)B的邏輯地址空間作業(yè)B的物理地址空間作業(yè)A的物理地址空間142、重定位、重定位將作業(yè)由其地址空間裝入存儲(chǔ)空間時(shí)的地址調(diào)整過(guò)程，將作業(yè)由其地址空間裝入存儲(chǔ)空間時(shí)的地址調(diào)整過(guò)程，邏輯地址變換為物理地址的過(guò)程。邏輯地址變換為物理地址的過(guò)程。1）靜態(tài)重定位：靜態(tài)重定位：一次性完成全部裝載的地址變換方式。一次性完成全部裝載的地址變換方式。優(yōu)點(diǎn)：優(yōu)點(diǎn)：地址變換機(jī)構(gòu)簡(jiǎn)單、開(kāi)銷(xiāo)小。地址變換機(jī)構(gòu)簡(jiǎn)單、開(kāi)銷(xiāo)小。缺點(diǎn)：缺點(diǎn)：1、為作業(yè)分配連續(xù)存儲(chǔ)區(qū)域，執(zhí)行期不能移動(dòng)，難以有效利用內(nèi)存；、為作業(yè)分配連續(xù)

10、存儲(chǔ)區(qū)域，執(zhí)行期不能移動(dòng)，難以有效利用內(nèi)存；2、需實(shí)現(xiàn)確定存儲(chǔ)量，若超過(guò)內(nèi)存容量，要考慮覆蓋技術(shù)；、需實(shí)現(xiàn)確定存儲(chǔ)量，若超過(guò)內(nèi)存容量，要考慮覆蓋技術(shù)；3、對(duì)共享的程序段，需一個(gè)作業(yè)一個(gè)副本，浪費(fèi)空間。、對(duì)共享的程序段，需一個(gè)作業(yè)一個(gè)副本，浪費(fèi)空間。15162）動(dòng)態(tài)重定位：動(dòng)態(tài)重定位：在程序的執(zhí)行過(guò)程中，在訪問(wèn)指令或數(shù)據(jù)之前，由附加的硬在程序的執(zhí)行過(guò)程中，在訪問(wèn)指令或數(shù)據(jù)之前，由附加的硬件地址變換機(jī)構(gòu)確定其存儲(chǔ)地址并調(diào)入內(nèi)存的方式。件地址變換機(jī)構(gòu)確定其存儲(chǔ)地址并調(diào)入內(nèi)存的方式。重定位寄存器重定位寄存器BR：進(jìn)程存儲(chǔ)空間的起始地址進(jìn)程存儲(chǔ)空間的起始地址 訪問(wèn)信息的內(nèi)存實(shí)際地址訪問(wèn)信息的內(nèi)存實(shí)際地址

11、= 訪問(wèn)信息的邏輯地址訪問(wèn)信息的邏輯地址 + 重定位寄存器重定位寄存器BR優(yōu)點(diǎn)：優(yōu)點(diǎn)：1、支持程序的非連續(xù)分配，分散程序段分別擁有一個(gè)、支持程序的非連續(xù)分配，分散程序段分別擁有一個(gè)BR；2、程序不必在執(zhí)行前全部裝入內(nèi)存，根據(jù)執(zhí)行情況階段性地裝入相應(yīng)內(nèi)容，、程序不必在執(zhí)行前全部裝入內(nèi)存，根據(jù)執(zhí)行情況階段性地裝入相應(yīng)內(nèi)容，“擴(kuò)充擴(kuò)充”內(nèi)存。內(nèi)存。3、幾個(gè)作業(yè)可共享一個(gè)程序段的單個(gè)副本。、幾個(gè)作業(yè)可共享一個(gè)程序段的單個(gè)副本。缺點(diǎn)：缺點(diǎn)：需要硬件的支持，軟件支持也較復(fù)雜。需要硬件的支持，軟件支持也較復(fù)雜。173、虛擬存儲(chǔ)器、虛擬存儲(chǔ)器將內(nèi)存、外存統(tǒng)一編址，并在統(tǒng)一的地址空間編程，運(yùn)行時(shí)通過(guò)自將內(nèi)存、外

12、存統(tǒng)一編址，并在統(tǒng)一的地址空間編程，運(yùn)行時(shí)通過(guò)自動(dòng)地址變換和調(diào)入調(diào)出功能，完成由邏輯地址道內(nèi)存實(shí)際地址的對(duì)應(yīng)，動(dòng)地址變換和調(diào)入調(diào)出功能，完成由邏輯地址道內(nèi)存實(shí)際地址的對(duì)應(yīng)，使程序最終在內(nèi)存中得以運(yùn)行，實(shí)現(xiàn)以小的內(nèi)存運(yùn)行更大、更多的程序。使程序最終在內(nèi)存中得以運(yùn)行，實(shí)現(xiàn)以小的內(nèi)存運(yùn)行更大、更多的程序。 由于這個(gè)過(guò)程由系統(tǒng)自動(dòng)完成，由于這個(gè)過(guò)程由系統(tǒng)自動(dòng)完成，使用戶(hù)感覺(jué)擁有一個(gè)比實(shí)際存儲(chǔ)量大的使用戶(hù)感覺(jué)擁有一個(gè)比實(shí)際存儲(chǔ)量大的多的內(nèi)存。多的內(nèi)存。1 1）對(duì)內(nèi)存容量的邏輯上的擴(kuò)充，非物理擴(kuò)充，）對(duì)內(nèi)存容量的邏輯上的擴(kuò)充，非物理擴(kuò)充，“虛擬虛擬”；2 2）虛擬存儲(chǔ)器的容量與內(nèi)存無(wú)關(guān)，與內(nèi)存、外存之和有

13、關(guān)；訪問(wèn)速）虛擬存儲(chǔ)器的容量與內(nèi)存無(wú)關(guān)，與內(nèi)存、外存之和有關(guān)；訪問(wèn)速度接近于內(nèi)存，成本接近于外存；度接近于內(nèi)存，成本接近于外存；3 3）一個(gè)虛擬存儲(chǔ)器的最大容量由計(jì)算機(jī)地址結(jié)構(gòu)和尋址方式?jīng)Q定：）一個(gè)虛擬存儲(chǔ)器的最大容量由計(jì)算機(jī)地址結(jié)構(gòu)和尋址方式?jīng)Q定： 機(jī)器字長(zhǎng)機(jī)器字長(zhǎng)n n位，尋址范圍位，尋址范圍0 02 2n n - 1- 1；4 4）內(nèi)存僅一個(gè)，虛擬存儲(chǔ)器卻是每個(gè)進(jìn)程一個(gè)。）內(nèi)存僅一個(gè)，虛擬存儲(chǔ)器卻是每個(gè)進(jìn)程一個(gè)。18存儲(chǔ)管理的類(lèi)型存儲(chǔ)管理的類(lèi)型1、單一連續(xù)區(qū)存儲(chǔ)管理、單一連續(xù)區(qū)存儲(chǔ)管理2、分區(qū)存儲(chǔ)管理、分區(qū)存儲(chǔ)管理3、分頁(yè)存儲(chǔ)管理、分頁(yè)存儲(chǔ)管理4、分段存儲(chǔ)管理、分段存儲(chǔ)管理195.2分區(qū)

14、存儲(chǔ)管理分區(qū)存儲(chǔ)管理將內(nèi)存劃分為若干區(qū)域，由多個(gè)進(jìn)程分享，實(shí)現(xiàn)并發(fā)執(zhí)行。將內(nèi)存劃分為若干區(qū)域，由多個(gè)進(jìn)程分享，實(shí)現(xiàn)并發(fā)執(zhí)行。一、固定分區(qū)法一、固定分區(qū)法二、動(dòng)態(tài)分區(qū)法二、動(dòng)態(tài)分區(qū)法三、可重定位分區(qū)分配三、可重定位分區(qū)分配四、多重分區(qū)分配四、多重分區(qū)分配20一、固定分區(qū)法一、固定分區(qū)法把內(nèi)存劃分位若干大小固定的區(qū)域把內(nèi)存劃分位若干大小固定的區(qū)域 ，一旦劃定，每個(gè)分區(qū)的長(zhǎng)度、，一旦劃定，每個(gè)分區(qū)的長(zhǎng)度、邊界、分區(qū)個(gè)數(shù)不發(fā)生改變。每個(gè)分區(qū)的大小可相等、可不等。邊界、分區(qū)個(gè)數(shù)不發(fā)生改變。每個(gè)分區(qū)的大小可相等、可不等。1、內(nèi)存分配、內(nèi)存分配 分區(qū)說(shuō)明表分區(qū)說(shuō)明表 ：記錄個(gè)分區(qū)的基本情況，作為分配和回收的

15、依據(jù)。記錄個(gè)分區(qū)的基本情況，作為分配和回收的依據(jù)。區(qū)號(hào)區(qū)號(hào)分區(qū)長(zhǎng)度分區(qū)長(zhǎng)度起始地址起始地址狀態(tài)狀態(tài)18K20K已分已分232K28K已分已分364K60K已分已分4132K124K未分未分212、分區(qū)分配分區(qū)分配3、分區(qū)回收分區(qū)回收釋放分區(qū)的狀態(tài)：釋放分區(qū)的狀態(tài)：已分已分 未分未分4、缺點(diǎn)：缺點(diǎn)：1）內(nèi)零頭多，利用率低；）內(nèi)零頭多，利用率低；2）大作業(yè)無(wú)法運(yùn)行。）大作業(yè)無(wú)法運(yùn)行。適于適于對(duì)作業(yè)大小能明確估計(jì)，對(duì)作業(yè)大小能明確估計(jì)，變動(dòng)不大，或有足夠大內(nèi)存變動(dòng)不大，或有足夠大內(nèi)存的大中型機(jī)。的大中型機(jī)。22二、動(dòng)態(tài)分區(qū)法二、動(dòng)態(tài)分區(qū)法1、原理：原理：內(nèi)存分區(qū)的劃分在裝入作業(yè)時(shí)進(jìn)行，分區(qū)的大小隨作

16、業(yè)大小內(nèi)存分區(qū)的劃分在裝入作業(yè)時(shí)進(jìn)行，分區(qū)的大小隨作業(yè)大小而定；初始有一個(gè)分區(qū)，隨分區(qū)的分配和撤消，分區(qū)的個(gè)數(shù)和大而定；初始有一個(gè)分區(qū)，隨分區(qū)的分配和撤消，分區(qū)的個(gè)數(shù)和大小不斷發(fā)生變化。小不斷發(fā)生變化。2、數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：1）請(qǐng)求表：請(qǐng)求表：記錄作業(yè)號(hào)或進(jìn)程號(hào)及其請(qǐng)求內(nèi)存的大小記錄作業(yè)號(hào)或進(jìn)程號(hào)及其請(qǐng)求內(nèi)存的大小描述內(nèi)存空間的空閑分區(qū)情況：描述內(nèi)存空間的空閑分區(qū)情況：2）可用表：可用表：3）自由鏈：自由鏈：每個(gè)空閑區(qū)的前幾個(gè)單元記錄本區(qū)的大小及下一個(gè)空每個(gè)空閑區(qū)的前幾個(gè)單元記錄本區(qū)的大小及下一個(gè)空閑區(qū)的起始地址。閑區(qū)的起始地址。區(qū)號(hào)區(qū)號(hào)長(zhǎng)度長(zhǎng)度起始地址起始地址233、分區(qū)分配算法：、分區(qū)分

17、配算法：按什么原則排列、選擇空閑分區(qū)：按什么原則排列、選擇空閑分區(qū)：1）最先適應(yīng)法：）最先適應(yīng)法：2）最佳適應(yīng)法：）最佳適應(yīng)法：3）最壞適應(yīng)法：）最壞適應(yīng)法：4）循環(huán)首次適應(yīng)算法：）循環(huán)首次適應(yīng)算法：241）最先適應(yīng)法：）最先適應(yīng)法：實(shí)施：實(shí)施：按起始地址遞增順序排列空閑分區(qū)；按起始地址遞增順序排列空閑分區(qū)；實(shí)質(zhì)：實(shí)質(zhì)：用低留高；用低留高；優(yōu)點(diǎn)：優(yōu)點(diǎn)：低零高整，利于大作業(yè)；低零高整，利于大作業(yè)；缺點(diǎn)：缺點(diǎn)：低址碎片多，查找開(kāi)銷(xiāo)大。低址碎片多，查找開(kāi)銷(xiāo)大。252）最佳適應(yīng)法：）最佳適應(yīng)法：實(shí)施：實(shí)施：按空閑區(qū)長(zhǎng)度遞增順序排列；按空閑區(qū)長(zhǎng)度遞增順序排列；實(shí)質(zhì)：實(shí)質(zhì)：才盡其用；才盡其用；優(yōu)點(diǎn)：優(yōu)點(diǎn)：

18、避免大材小用，保存大的空閑區(qū)；避免大材小用，保存大的空閑區(qū)；缺點(diǎn)：缺點(diǎn)：小碎片多，鏈重排。小碎片多，鏈重排。263）最壞適應(yīng)法：）最壞適應(yīng)法：實(shí)施：實(shí)施：按空閑分區(qū)長(zhǎng)度遞減的順序排列；按空閑分區(qū)長(zhǎng)度遞減的順序排列；實(shí)質(zhì)：實(shí)質(zhì)：舍大減殘；舍大減殘；優(yōu)點(diǎn)：優(yōu)點(diǎn)：速知能否分配，減少了小碎片；速知能否分配，減少了小碎片；缺點(diǎn)：缺點(diǎn)：大區(qū)減少，不利于大作業(yè)，鏈重排。大區(qū)減少，不利于大作業(yè)，鏈重排。274）循環(huán)首次適應(yīng)算法：）循環(huán)首次適應(yīng)算法：實(shí)施：實(shí)施：在最先適應(yīng)算法的基礎(chǔ)上，把自由鏈?zhǔn)孜蚕噙B，設(shè)置在最先適應(yīng)算法的基礎(chǔ)上，把自由鏈?zhǔn)孜蚕噙B，設(shè)置一個(gè)查詢(xún)指針，指向下一次查詢(xún)的起始空閑區(qū)，邊查邊一個(gè)查詢(xún)指針

19、，指向下一次查詢(xún)的起始空閑區(qū)，邊查邊移，直至找到適合的分區(qū)；移，直至找到適合的分區(qū)；實(shí)質(zhì)：實(shí)質(zhì)：碎片分布均勻；碎片分布均勻；優(yōu)點(diǎn)：優(yōu)點(diǎn)：減少了小碎片；減少了小碎片；缺點(diǎn)：缺點(diǎn)：不利于大作業(yè)。不利于大作業(yè)。28算法比較算法比較碎片碎片大空閑區(qū)大空閑區(qū)搜索釋放速度搜索釋放速度最先適應(yīng)法最先適應(yīng)法低址多低址多有有快快（一般不排序）（一般不排序）循環(huán)首次適循環(huán)首次適應(yīng)算法應(yīng)算法分布均勻分布均勻無(wú)無(wú)最佳適應(yīng)法最佳適應(yīng)法 小碎片多小碎片多有有較慢較慢（鏈重排）（鏈重排）最壞適應(yīng)法最壞適應(yīng)法少少無(wú)無(wú)294、分配和回收、分配和回收分配：分配：1）找出空閑區(qū)）找出空閑區(qū)2）分配）分配3）更新可用表）更新可用表/

20、自由鏈自由鏈無(wú)剩：刪除一項(xiàng)無(wú)剩：刪除一項(xiàng)有剩：修改、重排有剩：修改、重排回收：回收：回收區(qū)無(wú)相鄰空閑區(qū)：回收區(qū)無(wú)相鄰空閑區(qū)：插入新表項(xiàng)插入新表項(xiàng)/結(jié)點(diǎn)結(jié)點(diǎn)回收區(qū)有相鄰空閑區(qū)：回收區(qū)有相鄰空閑區(qū)：修改起始地址和分區(qū)長(zhǎng)修改起始地址和分區(qū)長(zhǎng)度，（鏈重排）度，（鏈重排）30局限：局限：碎片碎片 空間浪費(fèi)空間浪費(fèi) 難滿(mǎn)足大作業(yè)難滿(mǎn)足大作業(yè)固定分區(qū)：內(nèi)零頭固定分區(qū)：內(nèi)零頭 不可望不可望動(dòng)態(tài)分區(qū)：外零頭動(dòng)態(tài)分區(qū)：外零頭 可望不可及可望不可及解決：解決：可重定位分區(qū)分配可重定位分區(qū)分配多重分區(qū)分配多重分區(qū)分配31三、可重定位分區(qū)分配三、可重定位分區(qū)分配原理：原理：內(nèi)存緊張時(shí)，采用動(dòng)態(tài)重定位技術(shù)（重定位寄存內(nèi)存

21、緊張時(shí)，采用動(dòng)態(tài)重定位技術(shù)（重定位寄存器），把所有作業(yè)移動(dòng)到存儲(chǔ)器的一端，把空閑區(qū)合器），把所有作業(yè)移動(dòng)到存儲(chǔ)器的一端，把空閑區(qū)合并至另一端。并至另一端。拼接時(shí)機(jī)：拼接時(shí)機(jī)：1、回收區(qū)與空閑區(qū)不相鄰時(shí)：保證僅一個(gè)空閑區(qū)，運(yùn)、回收區(qū)與空閑區(qū)不相鄰時(shí)：保證僅一個(gè)空閑區(qū)，運(yùn)行頻率高；行頻率高；2、滿(mǎn)足不了作業(yè)需求時(shí)：一次移動(dòng)若干作業(yè)，運(yùn)行頻、滿(mǎn)足不了作業(yè)需求時(shí)：一次移動(dòng)若干作業(yè)，運(yùn)行頻率低。率低。優(yōu)點(diǎn)：優(yōu)點(diǎn)：解決碎片問(wèn)題，提高內(nèi)存利用率。解決碎片問(wèn)題，提高內(nèi)存利用率。缺點(diǎn)：缺點(diǎn)：移動(dòng)開(kāi)銷(xiāo)大移動(dòng)開(kāi)銷(xiāo)大32四、多重分區(qū)分配四、多重分區(qū)分配原理：原理：把一個(gè)作業(yè)分為相對(duì)獨(dú)立的程序段和數(shù)據(jù)段，每把一個(gè)作業(yè)分

22、為相對(duì)獨(dú)立的程序段和數(shù)據(jù)段，每段可以裝入不連續(xù)的存儲(chǔ)區(qū)中，為每段設(shè)置一個(gè)分段段可以裝入不連續(xù)的存儲(chǔ)區(qū)中，為每段設(shè)置一個(gè)分段重定位寄存器，記錄段分區(qū)地址，運(yùn)行時(shí)鏈接尋址。重定位寄存器，記錄段分區(qū)地址，運(yùn)行時(shí)鏈接尋址。優(yōu)點(diǎn)：優(yōu)點(diǎn)：1 1、有效利用碎片，利于大作業(yè)；、有效利用碎片，利于大作業(yè)；2 2、便于共享一段公共的子程序或數(shù)據(jù)。、便于共享一段公共的子程序或數(shù)據(jù)。33五、分區(qū)分配的優(yōu)缺點(diǎn)五、分區(qū)分配的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：優(yōu)點(diǎn)：1 1、實(shí)現(xiàn)了內(nèi)存共享，有助于多道程序設(shè)計(jì)；、實(shí)現(xiàn)了內(nèi)存共享，有助于多道程序設(shè)計(jì)；2 2、易于實(shí)現(xiàn)，數(shù)據(jù)結(jié)構(gòu)、算法簡(jiǎn)單，硬件支持少；、易于實(shí)現(xiàn)，數(shù)據(jù)結(jié)構(gòu)、算法簡(jiǎn)單，硬件支持少；3 3

23、、多重分區(qū)分配實(shí)現(xiàn)信息共享。、多重分區(qū)分配實(shí)現(xiàn)信息共享。缺點(diǎn)：缺點(diǎn)：1 1、內(nèi)存利用率仍不高：、內(nèi)存利用率仍不高：1 1）作業(yè)一次性裝入）作業(yè)一次性裝入2 2）碎片問(wèn)題；）碎片問(wèn)題；2 2、作業(yè)大小受分區(qū)長(zhǎng)度限制，沒(méi)有實(shí)現(xiàn)內(nèi)存、作業(yè)大小受分區(qū)長(zhǎng)度限制，沒(méi)有實(shí)現(xiàn)內(nèi)存“擴(kuò)充擴(kuò)充”；3 3、可重定位分配雖提高內(nèi)存利用率，但拼接技術(shù)開(kāi)銷(xiāo)大，、可重定位分配雖提高內(nèi)存利用率，但拼接技術(shù)開(kāi)銷(xiāo)大，效率不高；效率不高；4 4、難以實(shí)現(xiàn)各分區(qū)之間的信息共享。、難以實(shí)現(xiàn)各分區(qū)之間的信息共享。345.3覆蓋與交換技術(shù)覆蓋與交換技術(shù)一、覆蓋：一、覆蓋：原理：原理：把持續(xù)劃分為若干功能相對(duì)獨(dú)立的程序段，讓不會(huì)把持續(xù)劃分為

24、若干功能相對(duì)獨(dú)立的程序段，讓不會(huì)同時(shí)執(zhí)行的、無(wú)調(diào)用關(guān)系的程序段共享一塊存儲(chǔ)區(qū)。同時(shí)執(zhí)行的、無(wú)調(diào)用關(guān)系的程序段共享一塊存儲(chǔ)區(qū)。實(shí)現(xiàn)：實(shí)現(xiàn)：1、程序員事先提供一個(gè)明確的覆蓋關(guān)系；、程序員事先提供一個(gè)明確的覆蓋關(guān)系；2、根據(jù)覆蓋關(guān)系，分配存儲(chǔ)空間，建立覆蓋目錄表；、根據(jù)覆蓋關(guān)系，分配存儲(chǔ)空間，建立覆蓋目錄表；3、覆蓋的實(shí)施。、覆蓋的實(shí)施。351、程序員事先提供一個(gè)明確的覆蓋關(guān)系：、程序員事先提供一個(gè)明確的覆蓋關(guān)系：若干程序段的調(diào)用關(guān)系、各自占用空間；若干程序段的調(diào)用關(guān)系、各自占用空間；無(wú)關(guān)段為一組，共幾組無(wú)關(guān)段？無(wú)關(guān)段為一組，共幾組無(wú)關(guān)段？362、根據(jù)覆蓋關(guān)系，分配存儲(chǔ)空間，建立覆蓋目錄表；、根據(jù)覆蓋關(guān)系，分配存儲(chǔ)空間，建立覆蓋目錄表；總空間總空間 = 常駐區(qū)常駐區(qū) + 各覆蓋區(qū)之和各覆蓋區(qū)之和覆蓋目錄表覆蓋目錄表：程序員提交，分配后填寫(xiě)。：程序員提交，分配后填寫(xiě)。373、覆蓋的實(shí)施：、覆蓋的實(shí)施：需調(diào)入覆蓋需調(diào)入覆蓋(i , j)時(shí)：時(shí)：1）查覆蓋目錄表）查覆蓋目錄表是否存在？是否存在？（0 = i = N-1 , 0 = j = Ni-1 ）2）是否在內(nèi)存？（）是否在內(nèi)