操作系統(tǒng)第5章講存儲管理1連續(xù)分配

主要研究三方面的問題：放（Placement）?。‵etch）換（Replacement）存儲管理研究的內(nèi)容第五章存儲管理概述第一個問題：放（Placement），如何放入內(nèi)存？存儲管理研究的內(nèi)容連續(xù)不連續(xù)多道固定分區(qū)存放多道可變分區(qū)存放單道連續(xù)存放分頁存放分段存放段頁式存放放第二個問題是：?。‵etch），即如何從外存調(diào)入內(nèi)存。存儲管理研究的內(nèi)容預(yù)調(diào)：訪問前預(yù)先調(diào)入內(nèi)存請調(diào)：因空間不足，訪問時請求調(diào)入內(nèi)存單道連續(xù)一次調(diào)入分頁式請求調(diào)入分段式請求調(diào)入段頁式請求調(diào)入取多道固定分區(qū)一次調(diào)入多道可變分區(qū)一次調(diào)入第三個的問題：換（Replacement），即請求從外存調(diào)入的頁或段與內(nèi)存中的哪些塊或哪個存儲區(qū)對換？存儲管理研究的內(nèi)容換先進先出算法FIFO時鐘算法CLOCK最優(yōu)算法OPT最近最少使用算法LRU頁式策略5.1程序的裝入和鏈接一、源程序裝入內(nèi)存的三個步驟編譯鏈接裝入第五講存儲管理之一----連續(xù)空間分配一、源程序裝入內(nèi)存的三個步驟如：有一作業(yè)A，有4個程序段，裝入過程如下：主程序段子主程序段數(shù)據(jù)段堆棧段編譯主程序段子主程序段數(shù)據(jù)段堆棧段040K030K020K010K鏈接主程序段子主程序段數(shù)據(jù)段堆棧段0100K裝入OS用戶可用空間地址重定位0800K4096K作業(yè)A的源程序----名空間作業(yè)A的目標(biāo)模塊----邏輯地址空間作業(yè)A重定位后的物理地址空間作業(yè)A的目標(biāo)程序(可執(zhí)行文件)----邏輯地址空間二、鏈接方式

1、靜態(tài)鏈接----程序運行之前就事先將外部目標(biāo)模塊鏈接成可執(zhí)行文件，稱為靜態(tài)鏈接。例：如下作業(yè)B有三個目標(biāo)程序模塊。

鏈接裝入OS用戶可用空間地址重定位0800K4096K模塊ACallBReturn模塊BCallCReturn模塊CReturn0L-10M-10N-1模塊AJSR“L”Return模塊BJSR“L+M”Return模塊CReturn0L-1LL+M-1L+ML+M+N-1作業(yè)B的目標(biāo)模塊----邏輯地址空間作業(yè)B的目標(biāo)程序(可執(zhí)行文件)----邏輯地址空間二、鏈接方式

2、裝入時動態(tài)鏈接----程序在裝入內(nèi)存時才將外部目標(biāo)模塊鏈接成完整的可執(zhí)行的目標(biāo)模塊。

裝入時鏈接地址重定位4096K模塊ACallBReturn模塊BCallCReturn模塊CReturn0L-10M-10N-1OS用戶可用內(nèi)存空間0800K模塊AJSR“L”Return模塊BJSR“L+M”Return模塊CReturn0L-1LL+M-1L+ML+M+N-1作業(yè)B的目標(biāo)模塊----邏輯地址空間基址寄存器二、鏈接方式

3、運行時動態(tài)鏈接----由于程序在每次運行時，可能運行的程序模塊可能不同，在程序得到運行時才將用到的目標(biāo)模塊鏈接成完整的可執(zhí)行的目標(biāo)模塊。

三、重定位----完成相對（邏輯）地址轉(zhuǎn)換成內(nèi)存物理（絕對）地址的工作。分為靜態(tài)重定位和動態(tài)重定位。如下圖示：相對地址操作系統(tǒng)-50KB050K80K130K190K256K作業(yè)1-20KB作業(yè)2-40KB作業(yè)3-50KB作業(yè)4-60KB作業(yè)1-20KB作業(yè)2-40KB作業(yè)3-50KB作業(yè)4-60KB020K40K050K60K00內(nèi)存物理地址重定位5.2連續(xù)空間分配

方式：單道連續(xù)、多道固定、多道可變5.2.1單道連續(xù)分配單道:指任一時刻內(nèi)存只有一道作業(yè)，該作業(yè)連續(xù)存放于內(nèi)存中。特點：易于理解，訪問效率高、空間利用率低。（1）內(nèi)存空間安排：內(nèi)存除存在OS外，余下的空間只供一個用戶程序使用。一、管理方法操作系統(tǒng)用戶程序0aa+1n界地址寄存器（2）設(shè)置越界檢查機構(gòu)：用戶程序每訪問一次主存，越界檢查機構(gòu)將訪問的地址與界地址寄存器中的值比較。若越界，則終止其執(zhí)行。false界地址寄存器A＞aCPUtrue地址A終止程序運行操作系統(tǒng)用戶程序0ana（3）覆蓋（overlap）技術(shù)

引入原因：因內(nèi)存小于作業(yè)的程序空間而引入覆蓋。方法：將用戶空間劃分成一個固定區(qū)和多個覆蓋區(qū)。主程序放固定區(qū)，依次調(diào)用的子程序則放在同一個覆蓋區(qū)。操作系統(tǒng)提供覆蓋系統(tǒng)調(diào)用函數(shù)，由用戶編程序時考慮調(diào)用。操作系統(tǒng)固定區(qū)(4kB)覆蓋區(qū)(6kB)覆蓋區(qū)(10kB)A(4kB)E(10kB)D(6kB)C(4kB)B(6kB)F(8kB)例:下圖的調(diào)用關(guān)系中,B不會調(diào)用C,C也不會調(diào)用B,所以過程B,C不必同時調(diào)入主存,同樣D、E之間，D、E與F之間也有同樣的關(guān)系。多道：任一時刻內(nèi)存可有多道作業(yè)，每道作業(yè)連續(xù)存放于內(nèi)存.5.2.2多道固定劃分法一、固定劃分管理方法

（1）將用戶內(nèi)存空間分成長度固定的若干塊。每塊分區(qū)的大小不一定相等。操作系統(tǒng)U1...Un用戶空間

例如:某存儲系統(tǒng)共256KB采用固定分區(qū)法，0-50K為OS使用。50K-80K為分區(qū)1，80K-130K為分區(qū)2，130K-190K為分區(qū)3，190K-256K為分區(qū)4。見圖示操作系統(tǒng)-50KB分區(qū)1-30KB分區(qū)2-50KB分區(qū)4-66KB050K80K130K分區(qū)3-60KB190K256K

這樣，內(nèi)存就可以同時裝入四個作業(yè)，分區(qū)1可裝入小于30KB的作業(yè)，分區(qū)2可裝入小于50KB的作業(yè)，分區(qū)3可裝入小于60KB的作業(yè)，分區(qū)4可裝入小于66KB的作業(yè)。操作系統(tǒng)-50KB050K80K130K190K256K作業(yè)1-20KB作業(yè)2-40KB作業(yè)3-50KB作業(yè)4-60KB

1.上下界寄存器的地址檢查機構(gòu)。當(dāng)作業(yè)被調(diào)度運行時，作業(yè)在內(nèi)存中的上下界地址送上下界寄存器，每次內(nèi)存訪問時，地址檢查機構(gòu)作越界檢查。（2）地址訪問保護技術(shù)的第一種方式操作系統(tǒng)-50KB050K80K130K190K256K作業(yè)1-20KB作業(yè)2-40KB作業(yè)3-50KB作業(yè)4-60KB（1）上下界寄存器和地址檢查機構(gòu)。CPU下界寄存器上界寄存器><TrueTrue地址Afalse false程序性中斷OS作業(yè)1作業(yè)2作業(yè)3作業(yè)4

例如：CPU訪問上例中作業(yè)2的地址A，則檢查過程如下：false falseCPU下界130K上界80K><TrueTrue地址A程序性中斷操作系統(tǒng)-50KB050K80K130K190K256K作業(yè)1-20KB作業(yè)2-40KB作業(yè)3-50KB作業(yè)4-60KB靜態(tài)重定位：指用戶代碼中使用的相對地址,連接程序?qū)⑵溲b配成絕對地址。（即：在裝入一個作業(yè)時，把該作業(yè)中的程序和數(shù)據(jù)地址一次全部轉(zhuǎn)換成絕對地址。)（2）上下界寄存器和地址檢查機構(gòu)要求作業(yè)采用靜態(tài)重定位技術(shù)。100500::MOVR1,(500)1230≈≈≈≈≈≈700例：程序A的邏輯地址空間如圖，將其裝入內(nèi)存。內(nèi)存起始地址為5000號單元。用靜態(tài)重定位法畫出其裝入內(nèi)存后的情況。

MOVR1，(500)表示：將500號單元（地址）的數(shù)據(jù)123送入1號寄存器。靜態(tài)重定位裝入內(nèi)存后的情況：100500::MOVR1,(500)1230≈≈≈≈≈≈7005100550057005000邏輯地址::MOVR1,(5500)1230≈≈≈≈≈≈≈≈內(nèi)存物理地址2.基址寄存器、長度寄存器的動態(tài)地址轉(zhuǎn)換機構(gòu)。當(dāng)作業(yè)被調(diào)度運行時，將作業(yè)所占內(nèi)存基址及長度送基址、長度寄存器，每次內(nèi)存訪問時，先看訪問地址是否小于長度，然后+基址進行訪存。見下圖。操作系統(tǒng)-50KB050K80K130K190K256K作業(yè)1-20KB作業(yè)2-40KB作業(yè)3-50KB作業(yè)4-60KB（2）地址訪問保護技術(shù)的第二種方式CPU基地址寄存器長度寄存器<+True地址Afalse 程序性中斷OS作業(yè)1作業(yè)2作業(yè)3作業(yè)4例：CPU要訪問上例作業(yè)2的A地址時的檢查過程CPU基地址80K限長40K<+True地址Afalse 程序性中斷操作系統(tǒng)-50KB050K80K130K190K256K作業(yè)1-20KB作業(yè)2-40KB作業(yè)3-50KB作業(yè)4-60KB動態(tài)重定位：指用戶代碼中的相對地址先原封不動地裝入內(nèi)存指定地址，在執(zhí)行期間才被動態(tài)地轉(zhuǎn)換成絕對地址.（2）基址寄存器、長度寄存器和動態(tài)地址轉(zhuǎn)換機構(gòu)要求作業(yè)采用動態(tài)重定位技術(shù)100500::MOVR1,(500)1230≈≈≈≈≈≈700::MOVR1,(500)1230≈≈≈≈≈≈≈≈

內(nèi)存絕對地址5000510055005700+5000

基址寄存器相對地此<700?長度寄存器700YN程序性中斷又例動態(tài)重定位的實現(xiàn)過程。指令MOVR1,(3000)（即把相對地址為3000的單元中的123取到1號寄存器） （3）多道固定劃分法的作業(yè)調(diào)度技術(shù)OS4kB6kB12kB...3kB4kB1kB2kB...5kB6kB...7kB10kB11kB8kB（1）多隊列法OS4kB6kB12kB...7kB3kB4kB5kB（2）單隊列法（4）固定分區(qū)法存在碎片問題

內(nèi)部碎片：內(nèi)存某存儲區(qū)間大于其存放作業(yè)空間的部分。如：作業(yè)只有3KB時，而某內(nèi)存固定分區(qū)有4KB。有1KB內(nèi)部碎片。OS12KB固定4KB3KB內(nèi)部碎片外部碎片：內(nèi)存某存儲區(qū)間容不下要運行的作業(yè)時。如：作業(yè)長度為：5KB，8KB，12KB時，若內(nèi)存固定分區(qū)只剩下4KB，則存在外部碎片。OS4KB6KB12KB外部碎片

一、管理方法5.2.3多道連續(xù)可變劃分法特點：多道、連續(xù)、但不固定劃分內(nèi)存。

系統(tǒng)設(shè)置一個空閑塊隊列，初始狀態(tài)時隊列中只有一個連續(xù)的空閑塊。作業(yè)到達后，作業(yè)有多大就分配多大的空間。作業(yè)撤離時，將釋放的空間加入空閑隊列。例題1：有以下4個作業(yè)，采用多道連續(xù)分配技術(shù)作業(yè)1-20KB作業(yè)2-40KB作業(yè)3-50KB作業(yè)4-60KB020K40K050K60K00操作系統(tǒng)-50KB空閑區(qū)050K70K110K160K256K作業(yè)1-20KB作業(yè)2-40KB作業(yè)3-50KB作業(yè)4-60KB220K例題2：有以下5個作業(yè)，假設(shè)任一時間段內(nèi)，內(nèi)存中每一作業(yè)的運行時間相等，采用FCFS作業(yè)調(diào)度方法。作業(yè)到來次序所需存儲量運行時間J160KB10sJ2100KB5sJ330KB20sJ470KB8sJ550KB15sOS040K256KJ1J2J3J4J5共190K二、可變分區(qū)中的數(shù)據(jù)結(jié)構(gòu)常用的數(shù)據(jù)結(jié)構(gòu)有兩種：空閑分區(qū)表和空閑分區(qū)鏈。

(1)空閑分區(qū)表。為內(nèi)存中每個尚未分配出去的分區(qū)設(shè)置一個表項，每個表項包含分區(qū)序號、分區(qū)起始地址和分區(qū)的大小。例：根據(jù)右圖的內(nèi)存使用情況填寫空閑分區(qū)表。操作系統(tǒng)空閑區(qū)1(26KB)已使用空閑區(qū)2(14KB)已使用空閑區(qū)3(5KB)已使用空閑區(qū)4(30KB)已使用0k40k66k70k84k100k105k150k180k256k空閑分區(qū)表分區(qū)序號分區(qū)起始地址分區(qū)大小140k26kB270k14kB3100k5kB4150k30kB………(2)空閑分區(qū)鏈。在每個空閑分區(qū)中設(shè)置用于控制分區(qū)分配的信息及用于鏈接各個分區(qū)的指針，將內(nèi)存中的空閑分區(qū)鏈接成一個鏈表。不同的分配算法鏈表的組織方式不同。三、可變分區(qū)分配算法(一)首次適應(yīng)(FirstFit)算法。該算法要求空閑分區(qū)以地址遞增的次序排序。如果采用的是鏈表結(jié)構(gòu)，分配時則從鏈表的開始順序進行查找，直到找到一個能夠滿足進程大小要求的空閑分區(qū)為止。然后，按進程的大小，從分區(qū)中“切出”一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍然留在鏈表中。例1：根據(jù)右圖的內(nèi)存使用情況畫出首次適應(yīng)算法的鏈表組織形式及分配一個10KB的作業(yè)后的情況。操作系統(tǒng)空閑區(qū)1(26KB)已使用空閑區(qū)2(14KB)已使用空閑區(qū)3(5KB)已使用空閑區(qū)4(30KB)已使用0k40k66k70k84k100k105k150k180k256k1解：（1）分配一個10KB的作業(yè)前的鏈表組織形式。40k26kB70k14kB100k5kB150k30kB∧70k100k150k（2）分配一個10KB的作業(yè)后的鏈表組織形式。50k16kB70k14kB100k5kB150k30kB∧70k100k150k操作系統(tǒng)空閑區(qū)1(26kB)已使用空閑區(qū)2(14kB)已使用空閑區(qū)3(5kB)已使用空閑區(qū)4(30kB)已使用0k40k66k70k84k100k105k150k180k256k表頭指針表頭指針三、可變分區(qū)分配算法(二)下次適應(yīng)(NextFit)算法。該算法從首次適應(yīng)算法演變而來。為了避免低地址部分小空閑分區(qū)的不斷增加，在給進程分配內(nèi)存空間時，不再每次從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到一個能滿足要求的空閑分區(qū)，并從中“切出”一塊與請求的大小相等的內(nèi)存空間分配出去。例2：根據(jù)右圖的內(nèi)存使用情況畫出下次適應(yīng)算法的鏈表組織形式及分配一個10KB的作業(yè)后的情況。假設(shè)上次找到的空閑分區(qū)是空閑區(qū)1。操作系統(tǒng)空閑區(qū)1(16kB)已使用空閑區(qū)2(14KB)已使用空閑區(qū)3(5KB)已使用空閑區(qū)4(30KB)已使用0k40k66k70k84k100k105k150k180k256k50k已使用2解：（1）分配一個10KB的作業(yè)前的鏈表組織形式。（2）分配一個10KB的作業(yè)后的鏈表組織形式。50k16kB70k14KB100k5KB150k30kB∧70k100k150k50k16KB80k4KB100k5KB150k30KB∧80k100k150k操作系統(tǒng)空閑區(qū)1(16kB)已使用空閑區(qū)2(14kB)已使用空閑區(qū)3(5kB)已使用空閑區(qū)4(30kB)已使用0k40k66k70k84k100k105k150k180k256k50k已使用表頭指針表頭指針三、可變分區(qū)分配算法(三)最佳適應(yīng)(BestFit)算法。最佳的含義是指每次為進程分配內(nèi)存時，總是把與進程大小最匹配的空閑分區(qū)分配出去。該算法若采用的數(shù)據(jù)結(jié)構(gòu)是空閑分區(qū)鏈，首先要求將空閑分區(qū)，按分區(qū)大小遞增的順序形成一空閑分區(qū)鏈。當(dāng)進程要求分配內(nèi)存時，第一次找到的滿足要求的空閑區(qū)，必然是最優(yōu)的。例3：根據(jù)右圖的內(nèi)存使用情況畫出最佳適應(yīng)算法的鏈表組織形式及分配一個10KB的作業(yè)后的情況。操作系統(tǒng)空閑區(qū)1(26KB)已使用空閑區(qū)2(14KB)已使用空閑區(qū)3(5KB)已使用空閑區(qū)4(30KB)已使用0k40k66k70k84k100k105k150k180k256k3解：（1）分配一個10KB的作業(yè)前的鏈表組織形式。100k5KB70k14KB40k26KB150k30KB∧70k40k150k（2）分配一個10KB的作業(yè)后的鏈表組織形式。80k4KB100k5KB40k26KB150k30KB∧100k40k150k操作系統(tǒng)空閑區(qū)1(26KB)已使用空閑區(qū)2(14KB)已使用空閑區(qū)3(5KB)已使用空閑區(qū)4(30KB)已使用0k40k66k70k84k100k105k150k180k256k表頭指針表頭指針三、可變分區(qū)分配算法(四)最壞適應(yīng)(WorstFit)算法。該算法與最佳適應(yīng)算法相反，要求空閑分區(qū)按分區(qū)大小遞減的順序排序，每次分配時，從鏈?zhǔn)渍业阶畲蟮目臻e分區(qū)“切出”一塊進行分配。該算法的特點是基本上不會留下小空閑分區(qū)，不易形成碎片。缺點是大的空閑分區(qū)被切割，當(dāng)有較大的進程需要運行時，系統(tǒng)往往不能滿足要求。例4：根據(jù)右圖的內(nèi)存使用情況畫出最壞適應(yīng)算法的鏈表組織形式及分配一個10KB的作業(yè)后的情況。操作系統(tǒng)空閑區(qū)1(26KB)已使用空閑區(qū)2(14KB)已使用空閑區(qū)3(5KB)已使用空閑區(qū)4(30KB)已使用0k40k66k70k84k100k105k150k180k256k4解：（1）分配一個10KB的作業(yè)前的鏈表組織形式。150k30KB40k26KB70k14KB100k5KB∧40k70k100k（2）分配一個10KB的作業(yè)后的鏈表組織形式。40k26KB160k20KB70k14KB100k5KB∧160k70k100k操作系統(tǒng)空閑區(qū)1(26KB)已使用空閑區(qū)2(14KB)已使用空閑區(qū)3(5KB)已使用空閑區(qū)4(30KB)已使用0k40k66k70k84k100k105k150k180k256k表頭指針表頭指針?biāo)?、可變分區(qū)的作業(yè)分配過程 在找到合適的空閑塊后，從其中將作業(yè)大小的空間分給作業(yè)，而剩余部分掛入空閑隊列。下面F是空閑塊集合;size(k)為塊k的大小;size(u)為用戶所需空間。分配共需5步：