操作系統(tǒng)-第4章(1)(第四版)

1、第四章存儲(chǔ)器管理 第四章存儲(chǔ)器管理 4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu) 4.2程序的裝入和鏈接程序的裝入和鏈接 4.3連續(xù)分配存儲(chǔ)管理方式連續(xù)分配存儲(chǔ)管理方式4.4 對(duì)換對(duì)換4.4分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式4.5分段存儲(chǔ)管理方式分段存儲(chǔ)管理方式第四章存儲(chǔ)器管理 4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu) 一、多級(jí)存儲(chǔ)器結(jié)構(gòu)一、多級(jí)存儲(chǔ)器結(jié)構(gòu) 在現(xiàn)代計(jì)算機(jī)系統(tǒng)在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，存儲(chǔ)器是信息中，存儲(chǔ)器是信息的來源與歸宿，占據(jù)重的來源與歸宿，占據(jù)重要位置。但是，在現(xiàn)有要位置。但是，在現(xiàn)有技術(shù)條件下，任何一種技術(shù)條件下，任何一種存儲(chǔ)裝置，都無法同時(shí)存儲(chǔ)裝置，都無法同時(shí)從速度與容量?jī)煞矫妫瑥?/p>

2、速度與容量?jī)煞矫妫瑵M足用戶的需求。實(shí)際滿足用戶的需求。實(shí)際上它們組成了一個(gè)速度上它們組成了一個(gè)速度由快到慢，容量由小到由快到慢，容量由小到大的存儲(chǔ)裝置層次。大的存儲(chǔ)裝置層次。 寄存器高速緩存主存磁盤緩存磁盤可移動(dòng)存儲(chǔ)介質(zhì)CPU寄存器主存輔存圖圖4-1 計(jì)算機(jī)系統(tǒng)存儲(chǔ)層次示意計(jì)算機(jī)系統(tǒng)存儲(chǔ)層次示意 速速度度快快慢慢小小大大容容量量OS管理管理設(shè)備管理設(shè)備管理第四章存儲(chǔ)器管理 二、各種存儲(chǔ)器二、各種存儲(chǔ)器1 1主存儲(chǔ)器主存儲(chǔ)器簡(jiǎn)稱內(nèi)存、主存、簡(jiǎn)稱內(nèi)存、主存、可執(zhí)行存儲(chǔ)器；可執(zhí)行存儲(chǔ)器；主要部件，保存進(jìn)程運(yùn)行時(shí)的程主要部件，保存進(jìn)程運(yùn)行時(shí)的程序和數(shù)據(jù)，序和數(shù)據(jù)，若干兆字節(jié)、中等速度、中等價(jià)格。若干兆

3、字節(jié)、中等速度、中等價(jià)格。 主存儲(chǔ)器的訪問速度遠(yuǎn)低于主存儲(chǔ)器的訪問速度遠(yuǎn)低于CPU執(zhí)行指令的速度，為緩和這一矛盾，執(zhí)行指令的速度，為緩和這一矛盾，在計(jì)算機(jī)系統(tǒng)中引入了寄存器和高速緩存。在計(jì)算機(jī)系統(tǒng)中引入了寄存器和高速緩存。 2 2寄存器寄存器速度最快，價(jià)格昂貴，容量小。以字速度最快，價(jià)格昂貴，容量小。以字(word)為單位。寄存器用于加為單位。寄存器用于加速存儲(chǔ)器的訪問速度，如：用寄存器存放操作數(shù)。速存儲(chǔ)器的訪問速度，如：用寄存器存放操作數(shù)。3高速緩存高速緩存 少量的、容量?。◣资倭康摹⑷萘啃。◣资甂B幾幾MB ）、非?？焖?、昂貴。）、非?？焖佟嘿F。 主存中常訪問的信息存放在高速緩存中，減

4、少訪主次數(shù)。主存中常訪問的信息存放在高速緩存中，減少訪主次數(shù)。第四章存儲(chǔ)器管理 4 4磁盤緩存磁盤緩存目前磁盤的目前磁盤的I/OI/O速度遠(yuǎn)低于對(duì)主存的訪問速度，將速度遠(yuǎn)低于對(duì)主存的訪問速度，將頻繁使用頻繁使用的一部分的一部分磁盤數(shù)據(jù)和信息，暫時(shí)存放在磁盤緩存中，可減少訪問磁盤的次數(shù)。磁盤數(shù)據(jù)和信息，暫時(shí)存放在磁盤緩存中，可減少訪問磁盤的次數(shù)。 即利用主存中的存儲(chǔ)空間，來暫存從磁盤中讀出即利用主存中的存儲(chǔ)空間，來暫存從磁盤中讀出( (或?qū)懭牖驅(qū)懭? )的信息。的信息。 掉電則丟失。掉電則丟失。文件文件硬盤硬盤存放存放內(nèi)存內(nèi)存調(diào)入調(diào)入磁盤磁盤緩沖緩沖備備份份磁帶磁帶文件出文件出現(xiàn)于不現(xiàn)于不同的存

5、同的存儲(chǔ)層次儲(chǔ)層次中中第四章存儲(chǔ)器管理 三、存儲(chǔ)管理的目的三、存儲(chǔ)管理的目的 1) 1) 主存的分配和管理主存的分配和管理 當(dāng)用戶需要內(nèi)存時(shí)，系統(tǒng)為之分配相應(yīng)的存儲(chǔ)空間；不需要時(shí)，及時(shí)回收，當(dāng)用戶需要內(nèi)存時(shí)，系統(tǒng)為之分配相應(yīng)的存儲(chǔ)空間；不需要時(shí)，及時(shí)回收，以供其它用戶使用。以供其它用戶使用。 2) 2) 提高主存儲(chǔ)器的利用率提高主存儲(chǔ)器的利用率 不僅能使多道程序動(dòng)態(tài)地共享主存，提高主存利用率，最好還能共享主存不僅能使多道程序動(dòng)態(tài)地共享主存，提高主存利用率，最好還能共享主存中某個(gè)區(qū)域的信息。中某個(gè)區(qū)域的信息。 3) 3) “擴(kuò)充擴(kuò)充”主存容量主存容量 為用戶提供比為用戶提供比主存物理空間主存物理

6、空間大得多的大得多的地址空間地址空間，以至使用戶感覺他的作業(yè)，以至使用戶感覺他的作業(yè)是在這樣一個(gè)大的存儲(chǔ)器中運(yùn)行。是在這樣一個(gè)大的存儲(chǔ)器中運(yùn)行。 4) 4) 存儲(chǔ)保護(hù)存儲(chǔ)保護(hù) 確保多道程序都在各自分配到存儲(chǔ)區(qū)域內(nèi)操作，互不干擾，防止一道程序確保多道程序都在各自分配到存儲(chǔ)區(qū)域內(nèi)操作，互不干擾，防止一道程序破壞其它作業(yè)或系統(tǒng)文件的信息。破壞其它作業(yè)或系統(tǒng)文件的信息。第四章存儲(chǔ)器管理 四、預(yù)備知識(shí)（補(bǔ)充）四、預(yù)備知識(shí)（補(bǔ)充）1.1.定位（存儲(chǔ)分配）定位（存儲(chǔ)分配） 為具體的程序和數(shù)據(jù)等為具體的程序和數(shù)據(jù)等分配分配存儲(chǔ)單元或存儲(chǔ)區(qū)工作。存儲(chǔ)單元或存儲(chǔ)區(qū)工作。2.2.映射映射 把邏輯地址轉(zhuǎn)換為相應(yīng)的物理

7、地址的過程。把邏輯地址轉(zhuǎn)換為相應(yīng)的物理地址的過程。3.3.隔離隔離 按按存取權(quán)限存取權(quán)限把合法區(qū)與非法區(qū)分隔，實(shí)現(xiàn)存儲(chǔ)保護(hù)。把合法區(qū)與非法區(qū)分隔，實(shí)現(xiàn)存儲(chǔ)保護(hù)。第四章存儲(chǔ)器管理 4.名空間名空間程序員在程序中定義的標(biāo)識(shí)符程序員在程序中定義的標(biāo)識(shí)符程序符號(hào)集合程序符號(hào)集合由程序員自定義由程序員自定義沒有地址的概念沒有地址的概念符號(hào)指令符號(hào)指令數(shù)據(jù)說明數(shù)據(jù)說明I/OI/O說明說明第四章存儲(chǔ)器管理 5、邏輯地址、邏輯地址空間、邏輯地址、邏輯地址空間邏輯地址邏輯地址 (相對(duì)地址、虛地址相對(duì)地址、虛地址) 用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相

8、對(duì)地址的形式，其首地址目標(biāo)代碼通常采用相對(duì)地址的形式，其首地址為為0，其余指令中的地址都相對(duì)于首地址而編，其余指令中的地址都相對(duì)于首地址而編址。址。用戶的程序地址用戶的程序地址(指令地址或操作數(shù)地址指令地址或操作數(shù)地址)均為均為邏輯地址。邏輯地址。不能用邏輯地址在內(nèi)存中讀取信息。不能用邏輯地址在內(nèi)存中讀取信息。(why)作業(yè)地址空間（作業(yè)邏輯地址空間、作業(yè)虛空間）作業(yè)地址空間（作業(yè)邏輯地址空間、作業(yè)虛空間） 用戶程序所有的邏輯地址集合對(duì)應(yīng)的空間。用戶程序所有的邏輯地址集合對(duì)應(yīng)的空間。由編譯程序生成由編譯程序生成作業(yè)地址空間作業(yè)地址空間01 n-1 指令、數(shù)據(jù)指令、數(shù)據(jù)mov r1,500123

9、0100500599作業(yè)地址空間作業(yè)地址空間第四章存儲(chǔ)器管理 6、物理地址、物理地址空間、物理地址、物理地址空間物理地址物理地址 (絕對(duì)地址、實(shí)地址絕對(duì)地址、實(shí)地址) 物理地址是計(jì)算機(jī)主存單元的真物理地址是計(jì)算機(jī)主存單元的真實(shí)地址，又稱為絕對(duì)地址或?qū)嵉貙?shí)地址，又稱為絕對(duì)地址或?qū)嵉刂?。址?可直接尋址。可直接尋址。主存空間（物理地址空間、存儲(chǔ)空主存空間（物理地址空間、存儲(chǔ)空間）間） 物理地址的集合所對(duì)應(yīng)的空間組物理地址的集合所對(duì)應(yīng)的空間組成了主存空間。成了主存空間。主存空間主存空間01 n-1 第四章存儲(chǔ)器管理 地址映射地址映射Load A 200 3456 。 。1200物理地址空間物理地址空

10、間Load A data1data1 3456名空間名空間Load A 200 34560100200編譯編譯連接連接邏輯地址空間邏輯地址空間BA=1000圖圖: : 名空間、地址空間、存儲(chǔ)空間名空間、地址空間、存儲(chǔ)空間源程序源程序目標(biāo)程序目標(biāo)程序可執(zhí)行程序可執(zhí)行程序第四章存儲(chǔ)器管理 7.7.存儲(chǔ)共享存儲(chǔ)共享內(nèi)存共享：內(nèi)存共享： 兩個(gè)或多個(gè)進(jìn)程共用內(nèi)存中相同區(qū)。兩個(gè)或多個(gè)進(jìn)程共用內(nèi)存中相同區(qū)。目的：目的： 節(jié)省內(nèi)存空間，提高內(nèi)存利用率。節(jié)省內(nèi)存空間，提高內(nèi)存利用率。實(shí)現(xiàn)進(jìn)程通信：實(shí)現(xiàn)進(jìn)程通信： 數(shù)據(jù)共享。數(shù)據(jù)共享。共享內(nèi)容：共享內(nèi)容：代碼共享。代碼共享。 數(shù)據(jù)共享。數(shù)據(jù)共享。第四章存儲(chǔ)器管理

11、8.8.存儲(chǔ)保護(hù)與安全存儲(chǔ)保護(hù)與安全1) 1) 保護(hù)目的保護(hù)目的為多個(gè)程序共享內(nèi)存提供保障為多個(gè)程序共享內(nèi)存提供保障, ,使在內(nèi)存中的各道程序使在內(nèi)存中的各道程序, , 只能訪只能訪問它自己的區(qū)域，避免各道程序間相互干攏，特別是當(dāng)一道程序發(fā)問它自己的區(qū)域，避免各道程序間相互干攏，特別是當(dāng)一道程序發(fā)生錯(cuò)誤時(shí)生錯(cuò)誤時(shí), , 不致于影響其他程序的運(yùn)行。不致于影響其他程序的運(yùn)行。通常由硬件完成保護(hù)功能，通常由硬件完成保護(hù)功能，由軟件輔助實(shí)現(xiàn)。由軟件輔助實(shí)現(xiàn)。特權(quán)指令不能完成存儲(chǔ)保護(hù)。特權(quán)指令不能完成存儲(chǔ)保護(hù)。2) 2) 存儲(chǔ)保護(hù)存儲(chǔ)保護(hù).保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯。保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯。（有意或

12、無意的）（有意或無意的）.不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù)。不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù)。 （系統(tǒng)區(qū)地址空間，其他用戶程序的地址空間）（系統(tǒng)區(qū)地址空間，其他用戶程序的地址空間）3) 3) 保護(hù)過程保護(hù)過程-防止地址越界防止地址越界每個(gè)進(jìn)程都有自己獨(dú)立的進(jìn)程空間，如果一個(gè)進(jìn)程在運(yùn)行時(shí)所產(chǎn)每個(gè)進(jìn)程都有自己獨(dú)立的進(jìn)程空間，如果一個(gè)進(jìn)程在運(yùn)行時(shí)所產(chǎn)生的地址在其地址空間之外，則發(fā)生地址越界。即當(dāng)程序要訪問某生的地址在其地址空間之外，則發(fā)生地址越界。即當(dāng)程序要訪問某個(gè)內(nèi)存單元時(shí)，由個(gè)內(nèi)存單元時(shí)，由硬件檢查硬件檢查是否允許，如果允許則執(zhí)行，否則產(chǎn)生是否允許，如果允許則執(zhí)行，否則產(chǎn)生地

13、址越界中斷，由操作系統(tǒng)進(jìn)行相應(yīng)處理。地址越界中斷，由操作系統(tǒng)進(jìn)行相應(yīng)處理。第四章存儲(chǔ)器管理 9.9.內(nèi)存內(nèi)存“擴(kuò)充擴(kuò)充” 通過虛擬存儲(chǔ)技術(shù)實(shí)現(xiàn)通過虛擬存儲(chǔ)技術(shù)實(shí)現(xiàn) 用戶在編制程序時(shí)，不應(yīng)該用戶在編制程序時(shí)，不應(yīng)該受內(nèi)存容量限制受內(nèi)存容量限制，所以要采用一定技術(shù)來，所以要采用一定技術(shù)來“擴(kuò)充擴(kuò)充”內(nèi)存的容量，使用戶得到比實(shí)際內(nèi)存容量大的多的內(nèi)存空間。內(nèi)存的容量，使用戶得到比實(shí)際內(nèi)存容量大的多的內(nèi)存空間。具體實(shí)現(xiàn)是在硬件支持下，軟硬件相互協(xié)作，將內(nèi)存和外存結(jié)合起來具體實(shí)現(xiàn)是在硬件支持下，軟硬件相互協(xié)作，將內(nèi)存和外存結(jié)合起來統(tǒng)一使用。通過這種方法把內(nèi)存擴(kuò)充，使用戶在編制程序時(shí)不受內(nèi)存統(tǒng)一使用。通過這

14、種方法把內(nèi)存擴(kuò)充，使用戶在編制程序時(shí)不受內(nèi)存限制。限制。第四章存儲(chǔ)器管理 4.2 4.2 程序的裝入和鏈接程序的裝入和鏈接 在多道程序環(huán)境下，要使在多道程序環(huán)境下，要使程序運(yùn)行，必須創(chuàng)建進(jìn)程，而程序運(yùn)行，必須創(chuàng)建進(jìn)程，而創(chuàng)建進(jìn)程第一件事就是將程序創(chuàng)建進(jìn)程第一件事就是將程序和數(shù)據(jù)裝入內(nèi)存。一個(gè)用戶源和數(shù)據(jù)裝入內(nèi)存。一個(gè)用戶源程序要程序要變?yōu)樽優(yōu)樵趦?nèi)存中可執(zhí)行的在內(nèi)存中可執(zhí)行的程序，通常要進(jìn)行以下處理程序，通常要進(jìn)行以下處理： （1 1）編譯：編譯：由編譯程序?qū)⒂删幾g程序?qū)⒂脩粼闯绦蚓幾g成若干個(gè)目標(biāo)用戶源程序編譯成若干個(gè)目標(biāo)模塊模塊 （2 2）鏈接鏈接：由鏈接程序?qū)⒂涉溄映绦驅(qū)⒛繕?biāo)模塊和相應(yīng)的庫函

15、數(shù)鏈接目標(biāo)模塊和相應(yīng)的庫函數(shù)鏈接成裝入模塊成裝入模塊 （3 3）裝入裝入：由裝入程序?qū)⒂裳b入程序?qū)⒀b入模塊裝入內(nèi)存裝入模塊裝入內(nèi)存庫目標(biāo)程序塊1目標(biāo)程序塊2第一步鏈接程序裝入模塊(.exe)第二步裝入程序第三步用戶源程序(.c;.c+)編譯程序.obj第四章存儲(chǔ)器管理 一、程序的裝入一、程序的裝入( (由裝入程序?qū)⒀b入模塊由裝入程序?qū)⒀b入模塊(exe(exe文件文件) )裝入內(nèi)存裝入內(nèi)存) )1 1絕對(duì)裝入方式絕對(duì)裝入方式(Absolute Loading Mode)(Absolute Loading Mode)（早期）（早期）如果在編譯時(shí)，如果在編譯時(shí)，事先知事先知用戶程序在內(nèi)存的駐留位置，

16、則編譯程序用戶程序在內(nèi)存的駐留位置，則編譯程序在編譯時(shí)就產(chǎn)生絕對(duì)地址的目標(biāo)代碼。裝入程序就直接把裝入模塊中在編譯時(shí)就產(chǎn)生絕對(duì)地址的目標(biāo)代碼。裝入程序就直接把裝入模塊中的程序和數(shù)據(jù)裝入到指定的位置，（不需進(jìn)行地址轉(zhuǎn)換）的程序和數(shù)據(jù)裝入到指定的位置，（不需進(jìn)行地址轉(zhuǎn)換） 該裝入方式只適用于該裝入方式只適用于單道程序環(huán)境單道程序環(huán)境。第四章存儲(chǔ)器管理 2可重定位裝入方式可重定位裝入方式(Relocation Loading Mode) 在多道程序環(huán)境下，目標(biāo)模塊中的其它地址都是相對(duì)于在多道程序環(huán)境下，目標(biāo)模塊中的其它地址都是相對(duì)于0 0編址。應(yīng)根據(jù)編址。應(yīng)根據(jù)內(nèi)存的當(dāng)前情況，將裝入模塊裝入到內(nèi)存的適

17、當(dāng)位置。內(nèi)存的當(dāng)前情況，將裝入模塊裝入到內(nèi)存的適當(dāng)位置。 通常是把通常是把在裝入時(shí)在裝入時(shí)對(duì)目標(biāo)程序中指令和數(shù)據(jù)的修改過程稱為對(duì)目標(biāo)程序中指令和數(shù)據(jù)的修改過程稱為重定位重定位。 圖圖4-3作業(yè)裝入內(nèi)存時(shí)的情況作業(yè)裝入內(nèi)存時(shí)的情況LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作業(yè)地址空間內(nèi)存空間修改指令地址修改指令地址修改數(shù)據(jù)地址修改數(shù)據(jù)地址指令中的相對(duì)指令中的相對(duì)地址是否要修改？地址是否要修改？ 裝入模裝入模塊中所有塊中所有的邏輯地的邏輯地址與實(shí)際址與實(shí)際裝入內(nèi)存裝入內(nèi)存的物理地的物理地址不同。址不同。從此裝入從此裝入

18、第四章存儲(chǔ)器管理 物理地址物理地址基地址基地址相對(duì)地址相對(duì)地址地址變換在裝入地址變換在裝入時(shí)一次完成，以時(shí)一次完成，以后不改變，靜態(tài)后不改變，靜態(tài)再定位。再定位。是否允許程序是否允許程序運(yùn)行時(shí)在內(nèi)存運(yùn)行時(shí)在內(nèi)存中移動(dòng)位置？中移動(dòng)位置？第四章存儲(chǔ)器管理 3 3動(dòng)態(tài)運(yùn)行時(shí)裝入方式動(dòng)態(tài)運(yùn)行時(shí)裝入方式(Dynamic Run-time Loading)(Dynamic Run-time Loading)可重定位裝入方式可重定位裝入方式: : 裝入模塊裝入到內(nèi)存中任何允許的位置。裝入模塊裝入到內(nèi)存中任何允許的位置。不允許程序運(yùn)行時(shí)在內(nèi)存中不允許程序運(yùn)行時(shí)在內(nèi)存中移動(dòng)位置移動(dòng)位置。 實(shí)際情況：實(shí)際情況：程

19、序程序在運(yùn)行過程中它在內(nèi)存中的位置在運(yùn)行過程中它在內(nèi)存中的位置可能經(jīng)常要改變可能經(jīng)常要改變。 動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并不不立即把立即把裝入模塊中的裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序，而是把這種地址轉(zhuǎn)換推遲到程序真正要真正要執(zhí)行時(shí)執(zhí)行時(shí)才進(jìn)行。因此，才進(jìn)行。因此， 裝入內(nèi)存后的所有地址都仍是相對(duì)地址。裝入內(nèi)存后的所有地址都仍是相對(duì)地址。 第四章存儲(chǔ)器管理 二、程序的鏈接二、程序的鏈接根據(jù)鏈接時(shí)間的不同，程序鏈接分成三種：根據(jù)鏈接時(shí)間的不同，程序鏈接分成三種：(1) (1)

20、靜態(tài)鏈接。靜態(tài)鏈接。(2) (2) 裝入時(shí)動(dòng)態(tài)鏈接。裝入時(shí)動(dòng)態(tài)鏈接。 (3) 運(yùn)行時(shí)動(dòng)態(tài)鏈接。運(yùn)行時(shí)動(dòng)態(tài)鏈接。第四章存儲(chǔ)器管理 1 1靜態(tài)鏈接方式靜態(tài)鏈接方式(Static Linking)(Static Linking)圖圖 4-4程序鏈接示意圖程序鏈接示意圖 模塊 ACALL B；Return；0L-1模塊 BCALL C；Return；0M-1模塊 CReturn；0N-10模塊 AJSR“L”Return；L-1模塊 BJSR“LM”Return；LL+M-1L+ML+M+N-1模塊 CReturn；(a) 目標(biāo)模塊(b ) 裝入模塊 是一種是一種事先鏈接方式事先鏈接方式，即在程序運(yùn)行

21、之前，先將各目標(biāo)模塊及它們，即在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需的庫函數(shù)，鏈接成一個(gè)完整的裝入模塊所需的庫函數(shù)，鏈接成一個(gè)完整的裝入模塊( (執(zhí)行文件執(zhí)行文件) )，以后不再拆開。，以后不再拆開。 實(shí)現(xiàn)靜態(tài)鏈接應(yīng)解決的問題：實(shí)現(xiàn)靜態(tài)鏈接應(yīng)解決的問題： （1 1）相對(duì)地址的修改）相對(duì)地址的修改 （2 2）變換外部調(diào)用符號(hào)）變換外部調(diào)用符號(hào) 存在問題：存在問題：（1 1）不便于對(duì)目標(biāo)模塊的修改和更新。）不便于對(duì)目標(biāo)模塊的修改和更新。 如要更新其中一個(gè)模塊，如要更新其中一個(gè)模塊， 需要打開裝入模塊。需要打開裝入模塊。（2 2）無法實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。）無法實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。PPAB靜態(tài)靜

22、態(tài)鏈接鏈接第四章存儲(chǔ)器管理 2 2裝入時(shí)動(dòng)態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接(Load-time Dynamic Linking)(Load-time Dynamic Linking) 將用戶源程序編譯后所得到的將用戶源程序編譯后所得到的一組目標(biāo)模塊一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，采，在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接的鏈接方式。用邊裝入邊鏈接的鏈接方式。 優(yōu)點(diǎn)：優(yōu)點(diǎn)： (1) (1) 便于修改和更新。便于修改和更新。各目標(biāo)模塊是分開存放的各目標(biāo)模塊是分開存放的;修改容易；修改容易； (2) (2) 便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。PPAB靜態(tài)靜態(tài)鏈接鏈接PAB裝入裝入時(shí)動(dòng)時(shí)動(dòng)態(tài)鏈態(tài)鏈接接存在問

23、題：存在問題： 由于程序運(yùn)行所有由于程序運(yùn)行所有可能用的目標(biāo)模塊可能用的目標(biāo)模塊在裝入時(shí)均全部鏈接在裝入時(shí)均全部鏈接在一起，所以將會(huì)把一些不會(huì)運(yùn)行的目標(biāo)模塊也鏈接進(jìn)去。如在一起，所以將會(huì)把一些不會(huì)運(yùn)行的目標(biāo)模塊也鏈接進(jìn)去。如程序中的錯(cuò)誤處理模塊。程序中的錯(cuò)誤處理模塊。第四章存儲(chǔ)器管理 3 3運(yùn)行時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-time Dynamic Linking)(Run-time Dynamic Linking) 定義：定義： 對(duì)某些模塊的鏈接對(duì)某些模塊的鏈接推遲到程序執(zhí)行推遲到程序執(zhí)行時(shí)才進(jìn)行鏈接。時(shí)才進(jìn)行鏈接。 在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即在執(zhí)行過程中，當(dāng)

24、發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。凡在凡在執(zhí)行過程中未被用到的目標(biāo)模塊，執(zhí)行過程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。 第四章存儲(chǔ)器管理 三、重定位三、重定位 地址映射：地址映射： 把作業(yè)地址空間中使用的把作業(yè)地址空間中使用的邏輯地址邏輯地址變換成內(nèi)存空間中的變換成內(nèi)存空間中的物理地址物理地址的的過程。如下圖，

25、作業(yè)過程。如下圖，作業(yè)i i經(jīng)過重定位，把地址集合映射到以經(jīng)過重定位，把地址集合映射到以10001000為始址的為始址的內(nèi)存中，作為作業(yè)內(nèi)存中，作為作業(yè)i i的存儲(chǔ)空間。的存儲(chǔ)空間。作業(yè)作業(yè)i第四章存儲(chǔ)器管理 1. 重定位的類型重定位的類型 1) ) 靜態(tài)重定位靜態(tài)重定位 當(dāng)用戶程序被裝入內(nèi)存時(shí)，當(dāng)用戶程序被裝入內(nèi)存時(shí)，一次性一次性實(shí)現(xiàn)邏輯地址到物理實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換（一般在裝入內(nèi)存時(shí)由軟件完地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換（一般在裝入內(nèi)存時(shí)由軟件完成），成），作業(yè)作業(yè)i在執(zhí)行前在執(zhí)行前一次變址，直到該作業(yè)完成退出內(nèi)存為一次變址，直到該作業(yè)完成退出內(nèi)存為止。止。 第四章存儲(chǔ)器管

26、理 動(dòng)態(tài)重定位動(dòng)態(tài)重定位 在程序運(yùn)行過程中要在程序運(yùn)行過程中要訪問數(shù)據(jù)時(shí)訪問數(shù)據(jù)時(shí)再進(jìn)行地址變換。由地址變換再進(jìn)行地址變換。由地址變換機(jī)構(gòu)進(jìn)行的地址變換，硬件上需要重定位寄存器的支持。機(jī)構(gòu)進(jìn)行的地址變換，硬件上需要重定位寄存器的支持。 重定位寄存器：重定位寄存器：在執(zhí)行一條指令取操作數(shù)時(shí)，要將指令給出的有效在執(zhí)行一條指令取操作數(shù)時(shí)，要將指令給出的有效地址地址(500)(500)與重定位寄存器中的內(nèi)容（與重定位寄存器中的內(nèi)容（10001000）相加，得訪問地址）相加，得訪問地址（15001500），從而實(shí)現(xiàn)了地址動(dòng)態(tài)修改。），從而實(shí)現(xiàn)了地址動(dòng)態(tài)修改。裝入裝入時(shí)未時(shí)未修改修改第四章存儲(chǔ)器管理 4.

27、3連續(xù)分配存儲(chǔ)管理方式連續(xù)分配存儲(chǔ)管理方式 一、單一連續(xù)分配方式一、單一連續(xù)分配方式 最簡(jiǎn)單的一種存儲(chǔ)管理方式，但只最簡(jiǎn)單的一種存儲(chǔ)管理方式，但只能用于能用于單用戶、單任務(wù)的單用戶、單任務(wù)的OSOS中。中。存儲(chǔ)管理方法存儲(chǔ)管理方法：將內(nèi)存分為：將內(nèi)存分為系統(tǒng)區(qū)系統(tǒng)區(qū)（內(nèi)存（內(nèi)存低端，分配給低端，分配給OSOS用）和用）和用戶區(qū)用戶區(qū)（內(nèi)存高端，（內(nèi)存高端，分配給用戶用）。采用靜態(tài)分配方式，即分配給用戶用）。采用靜態(tài)分配方式，即作業(yè)一旦進(jìn)入內(nèi)存，就要等待它運(yùn)行結(jié)束作業(yè)一旦進(jìn)入內(nèi)存，就要等待它運(yùn)行結(jié)束后才能釋放內(nèi)存。后才能釋放內(nèi)存。主要特點(diǎn)主要特點(diǎn)：管理簡(jiǎn)單，只需小量的軟件和管理簡(jiǎn)單，只需小量的軟

28、件和硬件支持，便于用戶了解和使用。但因內(nèi)硬件支持，便于用戶了解和使用。但因內(nèi)存中只裝入一道作業(yè)運(yùn)行，內(nèi)存空間浪費(fèi)存中只裝入一道作業(yè)運(yùn)行，內(nèi)存空間浪費(fèi)大，各類資源的利用率也不高。大，各類資源的利用率也不高。系統(tǒng)區(qū)-os用戶區(qū)用戶程序第四章存儲(chǔ)器管理 工作流程工作流程 單一連續(xù)區(qū)分配采用單一連續(xù)區(qū)分配采用靜態(tài)重定位方式靜態(tài)重定位方式，即作業(yè)或進(jìn)程一旦進(jìn)入主，即作業(yè)或進(jìn)程一旦進(jìn)入主存，就一直等到它運(yùn)行結(jié)束后才能釋放主存。下圖所示的主存分配與存，就一直等到它運(yùn)行結(jié)束后才能釋放主存。下圖所示的主存分配與回收法。并且由回收法。并且由裝入程序檢查裝入程序檢查其絕對(duì)地址是否越界，即可達(dá)到保護(hù)系其絕對(duì)地址是否越

29、界，即可達(dá)到保護(hù)系統(tǒng)的目的。統(tǒng)的目的。缺點(diǎn)：缺點(diǎn)： 不支持多道。不支持多道。 主存利用率不高。主存利用率不高。 程序的運(yùn)行受主存容量限制。程序的運(yùn)行受主存容量限制。第四章存儲(chǔ)器管理 分區(qū)分配方式存儲(chǔ)管理分區(qū)分配方式存儲(chǔ)管理 分區(qū)分配方式分區(qū)分配方式是滿足是滿足多道多道程序設(shè)計(jì)需要的一種最簡(jiǎn)單的存儲(chǔ)程序設(shè)計(jì)需要的一種最簡(jiǎn)單的存儲(chǔ)管理方法。管理方法。存儲(chǔ)管理方法存儲(chǔ)管理方法 將內(nèi)存分成若干個(gè)分區(qū)（大小相等將內(nèi)存分成若干個(gè)分區(qū)（大小相等/ /不相等），除不相等），除OSOS占一區(qū)外，占一區(qū)外，其余的每一個(gè)分區(qū)容納一個(gè)用戶程序。按分區(qū)的變化情況，可將其余的每一個(gè)分區(qū)容納一個(gè)用戶程序。按分區(qū)的變化情況，

30、可將分區(qū)存儲(chǔ)管理進(jìn)一步分為：分區(qū)存儲(chǔ)管理進(jìn)一步分為： 固定分區(qū)存儲(chǔ)管理固定分區(qū)存儲(chǔ)管理 動(dòng)態(tài)分區(qū)存儲(chǔ)管理動(dòng)態(tài)分區(qū)存儲(chǔ)管理第四章存儲(chǔ)器管理 二、固定分區(qū)分配二、固定分區(qū)分配（固定分區(qū)存儲(chǔ)管理）固定分區(qū)存儲(chǔ)管理） 是最早使用的一種可運(yùn)行多道程序的存儲(chǔ)管理方法是最早使用的一種可運(yùn)行多道程序的存儲(chǔ)管理方法。 存儲(chǔ)管理方法存儲(chǔ)管理方法 內(nèi)存空間的劃分內(nèi)存空間的劃分：將內(nèi)存空間劃分為若干個(gè)固定大小的分區(qū)，將內(nèi)存空間劃分為若干個(gè)固定大小的分區(qū)，除除OSOS占一區(qū)外，其余的一個(gè)分區(qū)裝入一道程序。分區(qū)的大小占一區(qū)外，其余的一個(gè)分區(qū)裝入一道程序。分區(qū)的大小可以相等，也可以不等，但事先必須確定，在運(yùn)行時(shí)不能改可以相

31、等，也可以不等，但事先必須確定，在運(yùn)行時(shí)不能改變。即變。即分區(qū)大小及邊界在運(yùn)行時(shí)不能改變分區(qū)大小及邊界在運(yùn)行時(shí)不能改變。 系統(tǒng)需系統(tǒng)需建立一張分區(qū)說明表或使用表建立一張分區(qū)說明表或使用表，以記錄分區(qū)號(hào)、分區(qū)以記錄分區(qū)號(hào)、分區(qū)大小、分區(qū)的起始地址及狀態(tài)（已分配或未分配）大小、分區(qū)的起始地址及狀態(tài)（已分配或未分配）。第四章存儲(chǔ)器管理 固定分區(qū)分配方式示意圖固定分區(qū)分配方式示意圖os用戶程序p4p1p20k20k56k65k125k135k區(qū)號(hào)區(qū)號(hào)大小大小起址起址狀態(tài)狀態(tài)136k20k已分配已分配29k56k未分配未分配360k65k已分配已分配410k125k已分配已分配分區(qū)說明表分區(qū)說明表第四章

32、存儲(chǔ)器管理 分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)多個(gè)等待隊(duì)列多個(gè)等待隊(duì)列單個(gè)等待隊(duì)列單個(gè)等待隊(duì)列分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)圖：固定分區(qū)示意圖圖：固定分區(qū)示意圖第四章存儲(chǔ)器管理 內(nèi)存分配內(nèi)存分配 當(dāng)某個(gè)用戶程序要裝入內(nèi)存時(shí)，由內(nèi)存分配程序當(dāng)某個(gè)用戶程序要裝入內(nèi)存時(shí)，由內(nèi)存分配程序檢索分區(qū)說檢索分區(qū)說明表明表，從表中找出一個(gè)滿足要求的尚未分配的分區(qū)分配該程，從表中找出一個(gè)滿足要求的尚未分配的分區(qū)分配該程序，同時(shí)序，同時(shí)修改說明表修改說明表中相應(yīng)分區(qū)的狀態(tài)；若找不到大小足夠中相應(yīng)分區(qū)的狀態(tài)；若找不到大小足夠的分區(qū)，則拒絕為該程序分配內(nèi)存。的分區(qū)，則拒

33、絕為該程序分配內(nèi)存。 當(dāng)程序執(zhí)行完畢，釋放占用的分區(qū)，管理程序?qū)⑿薷恼f明表當(dāng)程序執(zhí)行完畢，釋放占用的分區(qū)，管理程序?qū)⑿薷恼f明表中相應(yīng)分區(qū)的狀態(tài)為未分配，實(shí)現(xiàn)內(nèi)存資源的回收。中相應(yīng)分區(qū)的狀態(tài)為未分配，實(shí)現(xiàn)內(nèi)存資源的回收。主要特點(diǎn)主要特點(diǎn)：管理簡(jiǎn)單，但因作業(yè)的大小并管理簡(jiǎn)單，但因作業(yè)的大小并不一定與某個(gè)分區(qū)大不一定與某個(gè)分區(qū)大小相等小相等，從而使一部分存儲(chǔ)空間被浪費(fèi)。所以主存的利用率不高。，從而使一部分存儲(chǔ)空間被浪費(fèi)。所以主存的利用率不高。例例 題題操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C24 KB32 KB64 KB128 KB256 KB分區(qū)號(hào)大小/KB起址/KB狀態(tài)11220已分配23232已分配3646

34、4已分配4128128未分配(b) 存儲(chǔ)空間分配情況(a) 分區(qū)說明表分配分配回收回收第四章存儲(chǔ)器管理 例：例：在某系統(tǒng)中，采用固定分區(qū)分配管理方式，內(nèi)存分區(qū)（單位字在某系統(tǒng)中，采用固定分區(qū)分配管理方式，內(nèi)存分區(qū)（單位字節(jié)）情況如圖所示，現(xiàn)有大小為節(jié)）情況如圖所示，現(xiàn)有大小為1K1K、9K9K、33K33K、121K121K的多個(gè)作業(yè)要求進(jìn)的多個(gè)作業(yè)要求進(jìn)入內(nèi)存，試畫出它們進(jìn)入內(nèi)存后的空間分配情況，并說明主存浪費(fèi)多大？入內(nèi)存，試畫出它們進(jìn)入內(nèi)存后的空間分配情況，并說明主存浪費(fèi)多大？10k20k28k60k180k511k234（1）內(nèi)存分區(qū)圖內(nèi)存分區(qū)圖os區(qū)號(hào)區(qū)號(hào)大小大小起址起址狀態(tài)狀態(tài)1 1

35、8k8k20k20k未分配未分配2 232k32k28k28k未分配未分配3 3120k120k60k60k未分配未分配4 4331k331k180k180k未分配未分配（2）分區(qū)說明表）分區(qū)說明表第四章存儲(chǔ)器管理 區(qū)號(hào)區(qū)號(hào) 大小大小起址起址狀態(tài)狀態(tài)18k20k已分配已分配232k28k已分配已分配3120k60k已分配已分配4331k180k已分配已分配（2）分區(qū)說明表）分區(qū)說明表0k20k28k60k180k511k23(1)內(nèi)存分配圖內(nèi)存分配圖(3)主存浪費(fèi)空間主存浪費(fèi)空間=(8-1)+(32-9)+(120-33)+(331-121) =7+23+87+210=327(k)解：解：根據(jù)

36、分區(qū)說明表，將根據(jù)分區(qū)說明表，將4個(gè)分區(qū)依次分配給個(gè)分區(qū)依次分配給4個(gè)作業(yè)，同時(shí)個(gè)作業(yè)，同時(shí)修改分區(qū)說明表，其內(nèi)存分配和分區(qū)說明表如下所示：修改分區(qū)說明表，其內(nèi)存分配和分區(qū)說明表如下所示：1K9K33K121K結(jié)論：浪費(fèi)嚴(yán)重；產(chǎn)生內(nèi)部碎片結(jié)論：浪費(fèi)嚴(yán)重；產(chǎn)生內(nèi)部碎片第四章存儲(chǔ)器管理 三、動(dòng)態(tài)分區(qū)分配方式三、動(dòng)態(tài)分區(qū)分配方式 動(dòng)態(tài)分區(qū)分配又稱為動(dòng)態(tài)分區(qū)分配又稱為可變式分區(qū)分配可變式分區(qū)分配，是一種動(dòng)態(tài)劃分存儲(chǔ)器，是一種動(dòng)態(tài)劃分存儲(chǔ)器的分區(qū)方法。的分區(qū)方法。存儲(chǔ)管理方法存儲(chǔ)管理方法 不事先將內(nèi)存劃分成一塊塊的分區(qū)，而是在作業(yè)進(jìn)入內(nèi)存時(shí)，不事先將內(nèi)存劃分成一塊塊的分區(qū)，而是在作業(yè)進(jìn)入內(nèi)存時(shí)，根據(jù)根據(jù)

37、作業(yè)的大小作業(yè)的大小動(dòng)態(tài)地建立分區(qū)，并使分區(qū)的大小動(dòng)態(tài)地建立分區(qū)，并使分區(qū)的大小正好適應(yīng)正好適應(yīng)作業(yè)的需作業(yè)的需要。因此系統(tǒng)中分區(qū)的大小是要。因此系統(tǒng)中分區(qū)的大小是可變的可變的，分區(qū)的數(shù)目分區(qū)的數(shù)目也是可變的。也是可變的。 主要特點(diǎn)主要特點(diǎn) 管理簡(jiǎn)單，只需小量的軟件和硬件支持，便于用戶了解和使用。管理簡(jiǎn)單，只需小量的軟件和硬件支持，便于用戶了解和使用。進(jìn)程的大小與某個(gè)分區(qū)大小相等，從而主存的利用率有所提高。進(jìn)程的大小與某個(gè)分區(qū)大小相等，從而主存的利用率有所提高。第四章存儲(chǔ)器管理 1 1、分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表空閑分區(qū)表 用來登記系統(tǒng)中的空閑分區(qū)用來登記系統(tǒng)中的空閑

38、分區(qū)( (分區(qū)號(hào)分區(qū)號(hào), ,分區(qū)起始地址分區(qū)起始地址, ,分區(qū)大小及狀態(tài)分區(qū)大小及狀態(tài)). ). 分區(qū)號(hào)分區(qū)號(hào)大小大小KBKB起始地址起始地址KBKB狀態(tài)狀態(tài)1閑空閑2 2空表目空表目3 3520520504504空閑空閑4 4空表目空表目5 5空閑分區(qū)鏈空閑分區(qū)鏈 用用鏈頭指針鏈頭指針將系統(tǒng)中的空閑分區(qū)鏈接起來，構(gòu)成空閑分區(qū)鏈。每個(gè)將系統(tǒng)中的空閑分區(qū)鏈接起來，構(gòu)成空閑分區(qū)鏈。每個(gè)空閑分區(qū)的起始部分存放相應(yīng)的控制信息空閑分區(qū)的起始部分存放相應(yīng)的控制信息( (如大小如大小, ,指向下一空閑分區(qū)的指向下一空閑分區(qū)的指針等指針等).).352KB504KB504KB32KB

39、32KB 520KB520KB空閑分區(qū)鏈頭指針空閑分區(qū)鏈頭指針第四章存儲(chǔ)器管理 2 2、分區(qū)分配算法、分區(qū)分配算法 為了將一個(gè)作業(yè)裝入內(nèi)存，應(yīng)按照一定的分配算法從空閑分區(qū)為了將一個(gè)作業(yè)裝入內(nèi)存，應(yīng)按照一定的分配算法從空閑分區(qū)表（鏈）中選出一個(gè)滿足作業(yè)需求的分區(qū)分配給作業(yè)，如果這個(gè)空表（鏈）中選出一個(gè)滿足作業(yè)需求的分區(qū)分配給作業(yè)，如果這個(gè)空閑分區(qū)的容量比作業(yè)申請(qǐng)的閑分區(qū)的容量比作業(yè)申請(qǐng)的空間要大空間要大，則將該分區(qū)，則將該分區(qū)一分為二一分為二，一部，一部分分配給作業(yè)，剩下的部分仍然留在空閑分區(qū)表（鏈）中，同時(shí)修分分配給作業(yè)，剩下的部分仍然留在空閑分區(qū)表（鏈）中，同時(shí)修改空閑分區(qū)表（鏈）中相應(yīng)的信

40、息。目前常用分配算法有：改空閑分區(qū)表（鏈）中相應(yīng)的信息。目前常用分配算法有：q首次適應(yīng)算法首次適應(yīng)算法q循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法q最佳適應(yīng)算法最佳適應(yīng)算法q最壞適應(yīng)算法最壞適應(yīng)算法第四章存儲(chǔ)器管理 首次適應(yīng)算法（最先適應(yīng)算法）首次適應(yīng)算法（最先適應(yīng)算法）算法算法 空閑分區(qū)（鏈）按地址遞增空閑分區(qū)（鏈）按地址遞增的次序排列。在進(jìn)行內(nèi)存分的次序排列。在進(jìn)行內(nèi)存分配時(shí)配時(shí), ,從空閑分區(qū)表從空閑分區(qū)表/ /鏈?zhǔn)祖準(zhǔn)组_始順序查找開始順序查找, ,直到找到第一個(gè)滿足直到找到第一個(gè)滿足其大小要求的空閑分區(qū)為止。然后再按照作業(yè)大小，從該分其大小要求的空閑分區(qū)為止。然后再按照作業(yè)大小，從該分區(qū)中劃出一

41、塊內(nèi)存空間分配給請(qǐng)求者，區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下余下的空閑分區(qū)仍留的空閑分區(qū)仍留在空閑分區(qū)表（鏈）中。在空閑分區(qū)表（鏈）中。第四章存儲(chǔ)器管理 區(qū)號(hào)區(qū)號(hào)大小大小起址起址132k20k28k52k3120k60k4331k180k空閑分區(qū)表空閑分區(qū)表解：解：按按首次適應(yīng)算法首次適應(yīng)算法， 申請(qǐng)作業(yè)申請(qǐng)作業(yè)100k，分配分配3號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為20k，起始地址，起始地址160K ； 申請(qǐng)作業(yè)申請(qǐng)作業(yè)30k， 分配分配1號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為2k，起始地址，起始地址50K ； 申請(qǐng)作業(yè)申請(qǐng)作業(yè)7k， 分配分配2號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為1k，起始

42、地址，起始地址59K ；其內(nèi)存分配圖及分配后空閑分區(qū)表如下其內(nèi)存分配圖及分配后空閑分區(qū)表如下:例例 ：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30K及及7K。給出按首次適應(yīng)算法的內(nèi)存分配情況及分配后空閑。給出按首次適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。分區(qū)表。第四章存儲(chǔ)器管理 區(qū)號(hào)區(qū)號(hào)大小大小起址起址12k50k21k59k320k160k4331k380k(3)該算法分配后的空閑分區(qū)表該算法分配后的空閑分區(qū)表0k20k52k60k180k511k(1)內(nèi)存分配圖內(nèi)存分配圖50K59K160K380Kv首次適應(yīng)算法的

43、特點(diǎn)首次適應(yīng)算法的特點(diǎn) 優(yōu)先利用優(yōu)先利用內(nèi)存低地址部分的空閑分區(qū)內(nèi)存低地址部分的空閑分區(qū), ,從而保留了高地址部分的大空閑區(qū)。從而保留了高地址部分的大空閑區(qū)。但由于但由于低地址部分不斷被劃分低地址部分不斷被劃分, ,致使低地址端留下許多難以利用的很小的空閑分致使低地址端留下許多難以利用的很小的空閑分區(qū)區(qū)( (碎片或零頭碎片或零頭),),而每次查找又都是從低地址部分開始而每次查找又都是從低地址部分開始, ,這無疑這無疑增加了查找可用增加了查找可用空閑分區(qū)的開銷。空閑分區(qū)的開銷。區(qū)號(hào)區(qū)號(hào)大小大小起址起址132k20k28k52k3120k60k4331k180k(2)分配前空閑分區(qū)表分配前空閑分區(qū)

44、表三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30K及及7K。第四章存儲(chǔ)器管理 循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法算法算法 又稱為又稱為下次適應(yīng)算法下次適應(yīng)算法，由首次適應(yīng)算法演變而來。在為作，由首次適應(yīng)算法演變而來。在為作業(yè)分配內(nèi)存空間時(shí)業(yè)分配內(nèi)存空間時(shí), ,不再每次從空閑分區(qū)表不再每次從空閑分區(qū)表/ /鏈?zhǔn)组_始查找鏈?zhǔn)组_始查找, ,而是而是從從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找開始查找, ,直到找到第直到找到第一個(gè)能滿足其大小要求的空閑分區(qū)為止。然后，再按照作業(yè)大一個(gè)能滿足其大小要求的空閑分區(qū)為止。然后，再按照作業(yè)大小，從該分區(qū)中劃出一

45、塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑分區(qū)表分區(qū)仍留在空閑分區(qū)表/ /鏈中。鏈中。第四章存儲(chǔ)器管理 區(qū)號(hào)區(qū)號(hào)大小大小起址起址132k20k28k52k3120k60k4331k180k空閑分區(qū)表空閑分區(qū)表解：解：按循環(huán)首次適應(yīng)算法，按循環(huán)首次適應(yīng)算法， 申請(qǐng)作業(yè)申請(qǐng)作業(yè)100k，分配分配3號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為20k,起始地址起始地址160K； 申請(qǐng)作業(yè)申請(qǐng)作業(yè)30k， 分配分配4號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為301k，起始地址，起始地址210K ； 申請(qǐng)作業(yè)申請(qǐng)作業(yè)7k， 分配分配1號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，

46、剩下分區(qū)為25k，起始地址，起始地址27K ；其內(nèi)存分配圖及分配后空閑分區(qū)表如下：其內(nèi)存分配圖及分配后空閑分區(qū)表如下：例例 ：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30K及及7K。給出按循環(huán)首次適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)。給出按循環(huán)首次適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。表。第四章存儲(chǔ)器管理 區(qū)號(hào)區(qū)號(hào)大小大小起址起址125k27k28k52k320k160k4301k210k(3)該算法分配后的空閑分區(qū)表該算法分配后的空閑分區(qū)表v算法特點(diǎn)算法特點(diǎn) 使存儲(chǔ)空間的利用使存儲(chǔ)空間的利用更加均衡更加均衡，不致

47、使小的空閑區(qū)集中在存儲(chǔ)，不致使小的空閑區(qū)集中在存儲(chǔ)區(qū)的一端，但這會(huì)導(dǎo)致區(qū)的一端，但這會(huì)導(dǎo)致缺乏大的空閑分區(qū)缺乏大的空閑分區(qū)。 0k 20k 52k 60k180k511k(1)內(nèi)存分配圖內(nèi)存分配圖27K52K160K210K區(qū)號(hào)區(qū)號(hào)大小大小起址起址132k20k28k52k3120k60k4331k180k(2)分配前空閑分區(qū)表分配前空閑分區(qū)表三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30K及及7K。第四章存儲(chǔ)器管理 最佳適應(yīng)算法最佳適應(yīng)算法算法算法 空閑分區(qū)表空閑分區(qū)表/ /鏈按容量大小遞增鏈按容量大小遞增的次序排列。在進(jìn)行內(nèi)存的次序排列。在進(jìn)行內(nèi)存分配時(shí)，從空閑分區(qū)表分配時(shí)

48、，從空閑分區(qū)表/ /鏈的首開始順序查找，直到找到第一鏈的首開始順序查找，直到找到第一個(gè)滿足其大小要求的空閑分區(qū)為止。個(gè)滿足其大小要求的空閑分區(qū)為止。 按這種方式為作業(yè)分配內(nèi)存，就能把既滿足作業(yè)要求又按這種方式為作業(yè)分配內(nèi)存，就能把既滿足作業(yè)要求又與作業(yè)大小與作業(yè)大小最接近最接近的空閑分區(qū)分配給作業(yè)。如果該空閑分區(qū)大的空閑分區(qū)分配給作業(yè)。如果該空閑分區(qū)大于作業(yè)的大小，則與首次適應(yīng)算法相同，將剩余空閑分區(qū)仍留于作業(yè)的大小，則與首次適應(yīng)算法相同，將剩余空閑分區(qū)仍留在空閑分區(qū)表在空閑分區(qū)表/ /鏈中。鏈中。第四章存儲(chǔ)器管理 0k 20k 52k 60k180k511k2134例例 ：系統(tǒng)中的空閑分區(qū)表

49、如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30K及及7K。給出按最佳適應(yīng)算法的內(nèi)存分配情況及分配后。給出按最佳適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表?？臻e分區(qū)表。區(qū)號(hào)區(qū)號(hào)大小大小起址起址18k52k232k20k3120k60k4331k180k分配前的空閑分區(qū)表分配前的空閑分區(qū)表內(nèi)存分區(qū)內(nèi)存分區(qū)按從小到大排隊(duì)按從小到大排隊(duì)第四章存儲(chǔ)器管理 解：解：按按最佳適應(yīng)算法最佳適應(yīng)算法，分配前的空閑分區(qū)表如上表。，分配前的空閑分區(qū)表如上表。 申請(qǐng)作業(yè)申請(qǐng)作業(yè)100k，分配分配3號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為20k,起始地址起始地址160K；

50、 申請(qǐng)作業(yè)申請(qǐng)作業(yè)30k， 分配分配2號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為2k，起始地址，起始地址50K ； 申請(qǐng)作業(yè)申請(qǐng)作業(yè)7k， 分配分配1號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為1k，起始地址，起始地址59K ；其內(nèi)存分配圖及分配后空閑分區(qū)表如下其內(nèi)存分配圖及分配后空閑分區(qū)表如下區(qū)號(hào)大小起址18k52k320k160k232k20k4331k180k作業(yè)作業(yè)100K分配后的空閑分區(qū)表分配后的空閑分區(qū)表區(qū)號(hào)大小起址22k50k18k52k320k160k4331k180k作業(yè)作業(yè)30K分配后的空閑分區(qū)表分配后的空閑分區(qū)表區(qū)號(hào)大小起址11k59k22k50k320k160k4331k180k作業(yè)

51、作業(yè)7K分配后的空閑分區(qū)表分配后的空閑分區(qū)表區(qū)號(hào)區(qū)號(hào)大小大小起址起址18k52k232k20k3120k60k4331k180k分配前的空閑分區(qū)表分配前的空閑分區(qū)表第四章存儲(chǔ)器管理 (2)該算法分配后的空閑分區(qū)表該算法分配后的空閑分區(qū)表 0k 20k 52k 60k180k511k(1)內(nèi)存分配圖內(nèi)存分配圖50K59K160K180K區(qū)號(hào)區(qū)號(hào)大小大小起址起址11k59k22k50k320k160k4331k180kv算法特點(diǎn)算法特點(diǎn) 若存在與作業(yè)大小一致的空閑分區(qū)若存在與作業(yè)大小一致的空閑分區(qū), ,則它必然被選中，若則它必然被選中，若不存在不存在與與作業(yè)大小一致的空閑分區(qū)，則只劃分比作業(yè)稍大的

52、空閑分區(qū)，作業(yè)大小一致的空閑分區(qū)，則只劃分比作業(yè)稍大的空閑分區(qū)，, ,從而保從而保留了大的空閑分區(qū)留了大的空閑分區(qū), ,但空閑區(qū)一般不可能正好和它申請(qǐng)的內(nèi)存空間大小但空閑區(qū)一般不可能正好和它申請(qǐng)的內(nèi)存空間大小一樣一樣, ,因而將其分割成兩部分時(shí)因而將其分割成兩部分時(shí), ,往往使往往使剩下的空閑區(qū)非常小剩下的空閑區(qū)非常小, ,從而在存從而在存儲(chǔ)器中留下許多難以利用的小空閑區(qū)（碎片或零頭）儲(chǔ)器中留下許多難以利用的小空閑區(qū)（碎片或零頭）。第四章存儲(chǔ)器管理 最壞適應(yīng)算法最壞適應(yīng)算法算法算法 空閑分區(qū)表空閑分區(qū)表/ /鏈按容量大小遞減鏈按容量大小遞減的次序排列。在進(jìn)行的次序排列。在進(jìn)行內(nèi)存分配時(shí)，從空閑

53、分區(qū)表內(nèi)存分配時(shí)，從空閑分區(qū)表/ /鏈的首開始順序查找，直到鏈的首開始順序查找，直到找到第一個(gè)比之大的空閑分區(qū)為止。剩下的空閑仍留在找到第一個(gè)比之大的空閑分區(qū)為止。剩下的空閑仍留在空閑分區(qū)表空閑分區(qū)表/ /鏈中。鏈中。第四章存儲(chǔ)器管理 區(qū)號(hào)區(qū)號(hào)大小大小起址起址1331k180k2120k60k332k20k48k52k空閑分區(qū)表空閑分區(qū)表例例 ：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間間100K、30K及及7K。給出按最壞適應(yīng)算法的內(nèi)存分配情況及分。給出按最壞適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。配后空閑分區(qū)表。按從大到小排隊(duì)按

54、從大到小排隊(duì)第四章存儲(chǔ)器管理 區(qū)號(hào)大小起址1231k280k2120k60k332k20k48k52k作業(yè)作業(yè)100K分配后的空閑分區(qū)表分配后的空閑分區(qū)表區(qū)號(hào)大小起址1201k310k2120k60k332k20k48k52k作業(yè)作業(yè)30K分配后的空閑分區(qū)表分配后的空閑分區(qū)表區(qū)號(hào)大小起址1194k317k2120k60k332k20k48k52k作業(yè)作業(yè)7K分配后的空閑分區(qū)表分配后的空閑分區(qū)表解：解：按按最壞適應(yīng)算法最壞適應(yīng)算法，分配前的空閑分區(qū)表如上表。，分配前的空閑分區(qū)表如上表。 申請(qǐng)作業(yè)申請(qǐng)作業(yè)100k，分配分配1號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為231k,起始地址起始地址280K；

55、申請(qǐng)作業(yè)申請(qǐng)作業(yè)30k， 分配分配1號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為201k，起始地址，起始地址310K ； 申請(qǐng)作業(yè)申請(qǐng)作業(yè)7k， 分配分配1號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為194k，起始地址，起始地址317K ；其內(nèi)存分配圖及分配后空閑分區(qū)表如下：其內(nèi)存分配圖及分配后空閑分區(qū)表如下：區(qū)號(hào)區(qū)號(hào)大小大小起址起址1331k180k2120k60k332k20k48k52k空閑分區(qū)表空閑分區(qū)表第四章存儲(chǔ)器管理 區(qū)號(hào)區(qū)號(hào)大小大小起址起址1194k317k2120k60k332k20k48k52k(2)該算法分配后的空閑分區(qū)表該算法分配后的空閑分區(qū)表3 0k 20k 52k 60k180k51

56、1k(1)內(nèi)存分配圖內(nèi)存分配圖20K52K60K280K310K317Kv算法特點(diǎn)算法特點(diǎn) 總是挑選滿足總是挑選滿足作業(yè)要求的最大作業(yè)要求的最大的分區(qū)分配給作業(yè)。這樣使分給作業(yè)后剩下的分區(qū)分配給作業(yè)。這樣使分給作業(yè)后剩下的空閑分區(qū)也較大，可裝下其它作業(yè)。但由于最大的空閑分區(qū)總是因首先分配的空閑分區(qū)也較大，可裝下其它作業(yè)。但由于最大的空閑分區(qū)總是因首先分配而劃分，當(dāng)有而劃分，當(dāng)有大作業(yè)到來大作業(yè)到來時(shí)，其存儲(chǔ)空間的申請(qǐng)往往會(huì)得不到滿足。時(shí)，其存儲(chǔ)空間的申請(qǐng)往往會(huì)得不到滿足。第四章存儲(chǔ)器管理 3 3分區(qū)分配操作分區(qū)分配操作1) 1) 分配內(nèi)存分配內(nèi)存根據(jù)內(nèi)存分配算法根據(jù)內(nèi)存分配算法圖圖 4-7內(nèi)存

57、分配流程內(nèi)存分配流程 從頭開始查表檢索完否？m.sizeu.size?m.size-u.sizesize?從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)分配給請(qǐng)求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回返回繼續(xù)檢索下一個(gè)表項(xiàng)將該分區(qū)從鏈中移出YNNYYN設(shè)設(shè): : u.size: 請(qǐng)求的分區(qū)大小為；請(qǐng)求的分區(qū)大小為； m.size: 空閑分區(qū)的大??；空閑分區(qū)的大??； size： 規(guī)定不再切割的剩余分規(guī)定不再切割的剩余分區(qū)的大小；區(qū)的大??； 該分區(qū)該分區(qū)整體分整體分配配分成分成兩部?jī)刹糠址终乙粋€(gè)空找一個(gè)空閑區(qū)能滿閑區(qū)能滿足作業(yè)大足作業(yè)大小小第四章存儲(chǔ)器管理 （2 2）回收內(nèi)存）回收內(nèi)存 當(dāng)作業(yè)執(zhí)行結(jié)束時(shí)，應(yīng)回收已使

58、用完畢的分區(qū)。系統(tǒng)根據(jù)當(dāng)作業(yè)執(zhí)行結(jié)束時(shí)，應(yīng)回收已使用完畢的分區(qū)。系統(tǒng)根據(jù)回收分區(qū)的大小及首回收分區(qū)的大小及首地址地址，在空閑分區(qū)表中檢查，在空閑分區(qū)表中檢查是否有鄰接的空閑分區(qū)是否有鄰接的空閑分區(qū)，如有，則合成為一個(gè)大的空閑，如有，則合成為一個(gè)大的空閑分區(qū)，然后修改有關(guān)的分區(qū)狀態(tài)信息。分區(qū)，然后修改有關(guān)的分區(qū)狀態(tài)信息。v 回收分區(qū)與回收分區(qū)與已有空閑分區(qū)已有空閑分區(qū)的相鄰情況有以下四種的相鄰情況有以下四種： 1）回收分區(qū)上鄰接一個(gè)空閑分區(qū)）回收分區(qū)上鄰接一個(gè)空閑分區(qū),合并后首地址為空閑分區(qū)的首地址合并后首地址為空閑分區(qū)的首地址,大小為二者之和。大小為二者之和。 2）回收分區(qū)下鄰接一個(gè)空閑分區(qū)）

59、回收分區(qū)下鄰接一個(gè)空閑分區(qū),合并后首地址為回收分區(qū)的首地址合并后首地址為回收分區(qū)的首地址,大小為二者之和。大小為二者之和。 3）回收分區(qū)上下鄰接空閑分區(qū)）回收分區(qū)上下鄰接空閑分區(qū),合并后首地址為上空閑分區(qū)的首地址合并后首地址為上空閑分區(qū)的首地址,大小為三者之和。大小為三者之和。 4）回收分區(qū)不鄰接空閑分區(qū)，這時(shí)在空閑分區(qū)表中新建一表項(xiàng)，并填寫分區(qū)大小等）回收分區(qū)不鄰接空閑分區(qū)，這時(shí)在空閑分區(qū)表中新建一表項(xiàng)，并填寫分區(qū)大小等信息。信息。回收分區(qū)空閑分區(qū)(a)空閑分區(qū)回收分區(qū)(b)空閑分區(qū)回收分區(qū)空閑分區(qū)(c)內(nèi)存回收情況內(nèi)存回收情況思考：思考： 哪種回收哪種回收情況，回收情況，回收后，空閑分后，

60、空閑分區(qū)數(shù)目要減區(qū)數(shù)目要減少一個(gè)？少一個(gè)？第四章存儲(chǔ)器管理 四、可重定位分區(qū)分配方式四、可重定位分區(qū)分配方式1、碎片問題、碎片問題 在分區(qū)存儲(chǔ)管理方式中，必須把作業(yè)裝入到在分區(qū)存儲(chǔ)管理方式中，必須把作業(yè)裝入到一片連續(xù)的一片連續(xù)的內(nèi)存空間。如果系統(tǒng)中有若干個(gè)小的分區(qū)，其總?cè)萘績(jī)?nèi)存空間。如果系統(tǒng)中有若干個(gè)小的分區(qū)，其總?cè)萘看笥谝笥谝b入的作業(yè)裝入的作業(yè)，但由于它們不相鄰接，也將致使作業(yè)不能裝入，但由于它們不相鄰接，也將致使作業(yè)不能裝入內(nèi)存。內(nèi)存。例例 ：如圖所示系統(tǒng)中有四個(gè)小空閑分區(qū)，不相鄰，但總?cè)萘繛槿鐖D所示系統(tǒng)中有四個(gè)小空閑分區(qū)，不相鄰，但總?cè)萘繛?0KB，如果現(xiàn)有一作業(yè)要求分配，如果現(xiàn)有一