操作系統(tǒng)第13講new

1、第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院第十三講第十三講存儲(chǔ)器管理（一）存儲(chǔ)器管理（一）第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院本次課程主要內(nèi)容本次課程主要內(nèi)容存儲(chǔ)器管理的層次結(jié)構(gòu)存儲(chǔ)器管理的層次結(jié)構(gòu)（1 1）多級(jí)存儲(chǔ)器結(jié)構(gòu)）多級(jí)存儲(chǔ)器結(jié)構(gòu) （2 2）主存儲(chǔ)器與寄存器）主存儲(chǔ)器與寄存器（3 3）高速緩存和磁盤(pán)緩存）高速緩存和磁盤(pán)緩存程序的裝入和鏈接程序的裝入和鏈接（1 1）程序的裝入（）程序的裝入（2 2）程序的鏈接）程序的鏈接連續(xù)分配方式連續(xù)分配方式（1 1）單一連續(xù)分配）單一連續(xù)分配 （2 2）固定分區(qū)分配）固定分區(qū)分配 （3 3）動(dòng)態(tài)）動(dòng)態(tài)分區(qū)分區(qū)分配分配

2、（4 4）伙伴系統(tǒng)伙伴系統(tǒng)（5 5）哈希算法哈希算法 （6 6）可重可重定位分區(qū)分配定位分區(qū)分配（7 7）對(duì)換對(duì)換第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院3高速緩存是容量大于或遠(yuǎn)大于寄存器，而比內(nèi)存約小兩到三個(gè)數(shù)量級(jí)左右，從幾十KB到幾MB，訪問(wèn)速度快于主存儲(chǔ)器。根據(jù)程序執(zhí)行的局部性原理(即程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律，在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分)，將主存中一些經(jīng)常訪問(wèn)的信息存放在高速緩存中，減少訪問(wèn)主存儲(chǔ)器的次數(shù)，可大幅度提高程序執(zhí)行速度。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院4第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院5由

3、于目前磁盤(pán)的I/O速度遠(yuǎn)低于對(duì)主存的訪問(wèn)速度，因此將頻繁使用的一部分磁盤(pán)數(shù)據(jù)和信息，暫時(shí)存放在磁盤(pán)緩存中，可減少訪問(wèn)磁盤(pán)的次數(shù)。磁盤(pán)緩存本身并不是一種實(shí)際存在的存儲(chǔ)介質(zhì)，它依托于固定磁盤(pán)，提供對(duì)主存儲(chǔ)器存儲(chǔ)空間的擴(kuò)充，即利用主存中的存儲(chǔ)空間，來(lái)暫存從磁盤(pán)中讀出(或?qū)懭?的信息。主存也可以看做是輔存的高速緩存，因?yàn)?，輔存中的數(shù)據(jù)必須復(fù)制到主存方能使用；反之，數(shù)據(jù)也必須先存在主存中，才能輸出到輔存。 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院6寄存器高速緩存主存磁盤(pán)緩存磁盤(pán)可移動(dòng)存儲(chǔ)介質(zhì)CPU寄存器主存輔存第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院7一個(gè)文件的數(shù)據(jù)可能出

4、現(xiàn)在存儲(chǔ)器層次的不同級(jí)別一個(gè)文件的數(shù)據(jù)可能出現(xiàn)在存儲(chǔ)器層次的不同級(jí)別中，例如，一個(gè)文件數(shù)據(jù)通常被存儲(chǔ)在輔存中中，例如，一個(gè)文件數(shù)據(jù)通常被存儲(chǔ)在輔存中( (如如硬盤(pán)硬盤(pán)) )，當(dāng)其需要運(yùn)行或被訪問(wèn)時(shí)，就必須調(diào)入主，當(dāng)其需要運(yùn)行或被訪問(wèn)時(shí)，就必須調(diào)入主存，也可以暫時(shí)存放在主存的磁盤(pán)高速緩存中。大存，也可以暫時(shí)存放在主存的磁盤(pán)高速緩存中。大容量的輔存常常使用磁盤(pán)，磁盤(pán)數(shù)據(jù)經(jīng)常備份到磁容量的輔存常常使用磁盤(pán)，磁盤(pán)數(shù)據(jù)經(jīng)常備份到磁帶或可移動(dòng)磁盤(pán)組上，以防止硬盤(pán)故障時(shí)丟失數(shù)據(jù)。帶或可移動(dòng)磁盤(pán)組上，以防止硬盤(pán)故障時(shí)丟失數(shù)據(jù)。有些系統(tǒng)自動(dòng)地把老文件數(shù)據(jù)從輔存轉(zhuǎn)儲(chǔ)到海量存有些系統(tǒng)自動(dòng)地把老文件數(shù)據(jù)從輔存轉(zhuǎn)儲(chǔ)到海

5、量存儲(chǔ)器中，如磁帶上，這樣做還能降低存儲(chǔ)價(jià)格。儲(chǔ)器中，如磁帶上，這樣做還能降低存儲(chǔ)價(jià)格。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院84.24.2程序的裝入和鏈接程序的裝入和鏈接 在多道程序環(huán)境下，要使程序運(yùn)行，必須先在多道程序環(huán)境下，要使程序運(yùn)行，必須先為之創(chuàng)建進(jìn)程。而創(chuàng)建進(jìn)程的第一件事，便是將程為之創(chuàng)建進(jìn)程。而創(chuàng)建進(jìn)程的第一件事，便是將程序和數(shù)據(jù)裝入內(nèi)存。序和數(shù)據(jù)裝入內(nèi)存。庫(kù)鏈接程序裝入模塊裝入程序編譯程序產(chǎn)生的目標(biāo)模塊第一步第二步第三步內(nèi)存第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院94.2.14.2.1程序的裝入程序的裝入1 1絕對(duì)裝入方式絕對(duì)裝入方式(Abso

6、lute Loading Mode)(Absolute Loading Mode)在編譯時(shí)，如果知道程序?qū)Ⅰv留在內(nèi)存的什么位置，在編譯時(shí)，如果知道程序?qū)Ⅰv留在內(nèi)存的什么位置，那么，編譯程序?qū)a(chǎn)生絕對(duì)地址的目標(biāo)代碼。例如，事那么，編譯程序?qū)a(chǎn)生絕對(duì)地址的目標(biāo)代碼。例如，事先已知用戶程序先已知用戶程序( (進(jìn)程進(jìn)程) )駐留在從駐留在從R R處開(kāi)始的位置，則編處開(kāi)始的位置，則編譯程序所產(chǎn)生的目標(biāo)模塊譯程序所產(chǎn)生的目標(biāo)模塊( (即裝入模塊即裝入模塊) )便從便從R R處開(kāi)始向處開(kāi)始向上擴(kuò)展。絕對(duì)裝入程序按照裝入模塊中的地址，將程序上擴(kuò)展。絕對(duì)裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存。裝入模

7、塊被裝入內(nèi)存后，由于程序中和數(shù)據(jù)裝入內(nèi)存。裝入模塊被裝入內(nèi)存后，由于程序中的邏輯地址與實(shí)際內(nèi)存地址完全相同，故不須對(duì)程序和的邏輯地址與實(shí)際內(nèi)存地址完全相同，故不須對(duì)程序和數(shù)據(jù)的地址進(jìn)行修改。數(shù)據(jù)的地址進(jìn)行修改。 思考：有何缺點(diǎn)？現(xiàn)在這種裝入方式適用于什么樣的程序？第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院102 2可重定位裝入方式可重定位裝入方式(Relocation Loading Mode) (Relocation Loading Mode) 絕對(duì)裝入方式只能將目標(biāo)模塊裝入到內(nèi)存中事先指絕對(duì)裝入方式只能將目標(biāo)模塊裝入到內(nèi)存中事先指定的位置。在多道程序環(huán)境下，編譯程序不可能預(yù)知

8、所定的位置。在多道程序環(huán)境下，編譯程序不可能預(yù)知所編譯的目標(biāo)模塊應(yīng)放在內(nèi)存的何處，因此，絕對(duì)裝入方編譯的目標(biāo)模塊應(yīng)放在內(nèi)存的何處，因此，絕對(duì)裝入方式只適用于單道程序環(huán)境。在多道程序環(huán)境下，所得到式只適用于單道程序環(huán)境。在多道程序環(huán)境下，所得到的目標(biāo)模塊的起始地址通常是從的目標(biāo)模塊的起始地址通常是從0 0開(kāi)始的，程序中的其開(kāi)始的，程序中的其它地址也都是相對(duì)于起始地址計(jì)算的。此時(shí)應(yīng)采用可重它地址也都是相對(duì)于起始地址計(jì)算的。此時(shí)應(yīng)采用可重定位裝入方式，根據(jù)內(nèi)存的當(dāng)前情況，將裝入模塊裝入定位裝入方式，根據(jù)內(nèi)存的當(dāng)前情況，將裝入模塊裝入到內(nèi)存的適當(dāng)位置。到內(nèi)存的適當(dāng)位置。 第四章 存儲(chǔ)器管理東北大學(xué)秦皇

9、島分校計(jì)算機(jī)與通信工程學(xué)院11LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作業(yè)地址空間內(nèi)存空間第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院123 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)存中任何允許的位置，故可用于多道程序環(huán)境；但這種方式并不允許的位置，故可用于多道程序環(huán)境；但這種方式并不允許程序運(yùn)行時(shí)在內(nèi)存中移動(dòng)位置。因?yàn)椋?/p>

10、程序在內(nèi)存允許程序運(yùn)行時(shí)在內(nèi)存中移動(dòng)位置。因?yàn)椋绦蛟趦?nèi)存中的移動(dòng)，意味著它的物理位置發(fā)生了變化，這時(shí)必須中的移動(dòng)，意味著它的物理位置發(fā)生了變化，這時(shí)必須對(duì)程序和數(shù)據(jù)的地址對(duì)程序和數(shù)據(jù)的地址( (是絕對(duì)地址是絕對(duì)地址) )進(jìn)行修改后方能運(yùn)行。進(jìn)行修改后方能運(yùn)行。然而，實(shí)際情況是，在運(yùn)行過(guò)程中它在內(nèi)存中的位置可然而，實(shí)際情況是，在運(yùn)行過(guò)程中它在內(nèi)存中的位置可能經(jīng)常要改變，此時(shí)就應(yīng)采用動(dòng)態(tài)運(yùn)行時(shí)裝入的方式。能經(jīng)常要改變，此時(shí)就應(yīng)采用動(dòng)態(tài)運(yùn)行時(shí)裝入的方式。 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院134.2.24.2.2程序的鏈接程序的鏈接根據(jù)鏈接時(shí)間的不同，可把鏈接分成如下三種：根

11、據(jù)鏈接時(shí)間的不同，可把鏈接分成如下三種：(1) (1) 靜態(tài)鏈接。在程序運(yùn)行之前，先將各目標(biāo)模塊及它靜態(tài)鏈接。在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需的庫(kù)函數(shù)，鏈接成一個(gè)完整的裝配模塊，以后不再拆們所需的庫(kù)函數(shù)，鏈接成一個(gè)完整的裝配模塊，以后不再拆開(kāi)。我們把這種事先進(jìn)行鏈接的方式稱為靜態(tài)鏈接方式。開(kāi)。我們把這種事先進(jìn)行鏈接的方式稱為靜態(tài)鏈接方式。(2) (2) 裝入時(shí)動(dòng)態(tài)鏈接。這是指將用戶源程序編譯后所得裝入時(shí)動(dòng)態(tài)鏈接。這是指將用戶源程序編譯后所得到的一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接的鏈到的一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接的鏈接方式。接方式。(3) (3) 運(yùn)行時(shí)動(dòng)態(tài)鏈

12、接。這是指對(duì)某些目標(biāo)模塊的鏈接，運(yùn)行時(shí)動(dòng)態(tài)鏈接。這是指對(duì)某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要該是在程序執(zhí)行中需要該( (目標(biāo)目標(biāo)) )模塊時(shí)，才對(duì)它進(jìn)行的鏈接。模塊時(shí)，才對(duì)它進(jìn)行的鏈接。 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院141 1靜態(tài)鏈接方式靜態(tài)鏈接方式(Static Linking)(Static Linking)模塊 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)

13、 目標(biāo)模塊(b) 裝入模塊第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院152 2裝入時(shí)動(dòng)態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接(Load-time Dynamic Linking)(Load-time Dynamic Linking)用戶源程序經(jīng)編譯后所得的目標(biāo)模塊，是在裝用戶源程序經(jīng)編譯后所得的目標(biāo)模塊，是在裝入內(nèi)存時(shí)邊裝入邊鏈接的，即在裝入一個(gè)目標(biāo)模塊入內(nèi)存時(shí)邊裝入邊鏈接的，即在裝入一個(gè)目標(biāo)模塊時(shí)，若發(fā)生一個(gè)外部模塊調(diào)用事件，將引起裝入程時(shí)，若發(fā)生一個(gè)外部模塊調(diào)用事件，將引起裝入程序去找出相應(yīng)的外部目標(biāo)模塊，并將它裝入內(nèi)存：序去找出相應(yīng)的外部目標(biāo)模塊，并將它裝入內(nèi)存：第四章 存儲(chǔ)器管理東北大學(xué)秦

14、皇島分校計(jì)算機(jī)與通信工程學(xué)院16裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)：裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)： (1) (1) 便于修改和更新。對(duì)于經(jīng)靜態(tài)鏈接裝配在便于修改和更新。對(duì)于經(jīng)靜態(tài)鏈接裝配在一起的裝入模塊，如果要修改或更新其中的某個(gè)目一起的裝入模塊，如果要修改或更新其中的某個(gè)目標(biāo)模塊，則要求重新打開(kāi)裝入模塊。這不僅是低效標(biāo)模塊，則要求重新打開(kāi)裝入模塊。這不僅是低效的，而且有時(shí)是不可能的。若采用動(dòng)態(tài)鏈接方式，的，而且有時(shí)是不可能的。若采用動(dòng)態(tài)鏈接方式，由于各目標(biāo)模塊是分開(kāi)存放的，所以要修改或更新由于各目標(biāo)模塊是分開(kāi)存放的，所以要修改或更新各目標(biāo)模塊是件非常容易的事。各目標(biāo)模塊是件非常容易的事。第四章 存

15、儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院17(2) (2) 便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。在采用靜態(tài)鏈接便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。在采用靜態(tài)鏈接方式時(shí)，每個(gè)應(yīng)用模塊都必須含有其目標(biāo)模塊的拷方式時(shí)，每個(gè)應(yīng)用模塊都必須含有其目標(biāo)模塊的拷貝，無(wú)法實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。但采用裝入時(shí)動(dòng)貝，無(wú)法實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。但采用裝入時(shí)動(dòng)態(tài)鏈接方式，態(tài)鏈接方式，OSOS則很容易將一個(gè)目標(biāo)模塊鏈接到幾則很容易將一個(gè)目標(biāo)模塊鏈接到幾個(gè)應(yīng)用模塊上，實(shí)現(xiàn)多個(gè)應(yīng)用程序?qū)υ撃K的共享。個(gè)應(yīng)用模塊上，實(shí)現(xiàn)多個(gè)應(yīng)用程序?qū)υ撃K的共享。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院183 3運(yùn)行時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接

16、(Run-time Dynamic Linking)(Run-time Dynamic Linking)在許多情況下，應(yīng)用程序在運(yùn)行時(shí)，每次要運(yùn)行的在許多情況下，應(yīng)用程序在運(yùn)行時(shí)，每次要運(yùn)行的模塊可能是不相同的。但由于事先無(wú)法知道本次要運(yùn)行模塊可能是不相同的。但由于事先無(wú)法知道本次要運(yùn)行哪些模塊，故只能是將所有可能要運(yùn)行到的模塊都全部哪些模塊，故只能是將所有可能要運(yùn)行到的模塊都全部裝入內(nèi)存，并在裝入時(shí)全部鏈接在一起。顯然這是低效裝入內(nèi)存，并在裝入時(shí)全部鏈接在一起。顯然這是低效的，因?yàn)橥鶗?huì)有些目標(biāo)模塊根本就不運(yùn)行。比較典型的，因?yàn)橥鶗?huì)有些目標(biāo)模塊根本就不運(yùn)行。比較典型的例子是作為錯(cuò)誤處理用的

17、目標(biāo)模塊，如果程序在整個(gè)的例子是作為錯(cuò)誤處理用的目標(biāo)模塊，如果程序在整個(gè)運(yùn)行過(guò)程中都不出現(xiàn)錯(cuò)誤，則顯然就不會(huì)用到該模塊。運(yùn)行過(guò)程中都不出現(xiàn)錯(cuò)誤，則顯然就不會(huì)用到該模塊。 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院19動(dòng)態(tài)鏈接方式，是對(duì)上述在裝入時(shí)鏈接方式的一種動(dòng)態(tài)鏈接方式，是對(duì)上述在裝入時(shí)鏈接方式的一種改進(jìn)。這種鏈接方式是將對(duì)某些模塊的鏈接推遲到改進(jìn)。這種鏈接方式是將對(duì)某些模塊的鏈接推遲到程序執(zhí)行時(shí)才進(jìn)行鏈接，亦即，在執(zhí)行過(guò)程中，當(dāng)程序執(zhí)行時(shí)才進(jìn)行鏈接，亦即，在執(zhí)行過(guò)程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由OSOS去去找到該模塊并將

18、之裝入內(nèi)存，把它鏈接到調(diào)用者模找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過(guò)程中未被用到的目標(biāo)模塊，都不塊上。凡在執(zhí)行過(guò)程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過(guò)程，而且可節(jié)省大量的內(nèi)存空間。加快程序的裝入過(guò)程，而且可節(jié)省大量的內(nèi)存空間。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院204.34.3連續(xù)分配方式連續(xù)分配方式 4.3.14.3.1單一連續(xù)分配單一連續(xù)分配這是最簡(jiǎn)單的一種存儲(chǔ)管理方式，但只能用于這是最簡(jiǎn)單的一種存儲(chǔ)管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。采用這種

19、存儲(chǔ)管理單用戶、單任務(wù)的操作系統(tǒng)中。采用這種存儲(chǔ)管理方式時(shí)，可把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系方式時(shí)，可把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給統(tǒng)區(qū)僅提供給OSOS使用，通常是放在內(nèi)存的低址部分；使用，通常是放在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間，提供給用戶區(qū)是指除系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間，提供給用戶使用。用戶使用。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院214.3.24.3.2固定分區(qū)分配固定分區(qū)分配1 1劃分分區(qū)的方法劃分分區(qū)的方法 (1) (1) 分區(qū)大小相等，即使所有的內(nèi)存分區(qū)大小相等。分區(qū)大小相等，即使所有的內(nèi)存分區(qū)大小相等。其缺點(diǎn)是缺乏靈活

20、性，即當(dāng)程序太小時(shí)，會(huì)造成內(nèi)存空其缺點(diǎn)是缺乏靈活性，即當(dāng)程序太小時(shí)，會(huì)造成內(nèi)存空間的浪費(fèi)；當(dāng)程序太大時(shí)，一個(gè)分區(qū)又不足以裝入該程間的浪費(fèi)；當(dāng)程序太大時(shí)，一個(gè)分區(qū)又不足以裝入該程序，致使該程序無(wú)法運(yùn)行。盡管如此，這種劃分方式仍序，致使該程序無(wú)法運(yùn)行。盡管如此，這種劃分方式仍被用于利用一臺(tái)計(jì)算機(jī)去控制多個(gè)相同對(duì)象的場(chǎng)合，因被用于利用一臺(tái)計(jì)算機(jī)去控制多個(gè)相同對(duì)象的場(chǎng)合，因?yàn)檫@些對(duì)象所需的內(nèi)存空間是大小相等的。例如，爐溫為這些對(duì)象所需的內(nèi)存空間是大小相等的。例如，爐溫群控系統(tǒng)，就是利用一臺(tái)計(jì)算機(jī)去控制多臺(tái)相同的冶煉群控系統(tǒng)，就是利用一臺(tái)計(jì)算機(jī)去控制多臺(tái)相同的冶煉爐。爐。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島

21、分校計(jì)算機(jī)與通信工程學(xué)院22 (2) (2) 分區(qū)大小不等。為了克服分區(qū)大小相等而分區(qū)大小不等。為了克服分區(qū)大小相等而缺乏靈活性的這個(gè)缺點(diǎn)，可把內(nèi)存區(qū)劃分成含有多缺乏靈活性的這個(gè)缺點(diǎn)，可把內(nèi)存區(qū)劃分成含有多個(gè)較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。個(gè)較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。這樣，便可根據(jù)程序的大小為之分配適當(dāng)?shù)姆謪^(qū)。這樣，便可根據(jù)程序的大小為之分配適當(dāng)?shù)姆謪^(qū)。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院232 2內(nèi)存分配內(nèi)存分配為了便于內(nèi)存分配，通常將分區(qū)按大小進(jìn)行排隊(duì)，為了便于內(nèi)存分配，通常將分區(qū)按大小進(jìn)行排隊(duì)，并為之建立一張分區(qū)使用表，其中各表項(xiàng)包括每個(gè)分區(qū)

22、并為之建立一張分區(qū)使用表，其中各表項(xiàng)包括每個(gè)分區(qū)的起始地址、大小及狀態(tài)的起始地址、大小及狀態(tài)( (是否已分配是否已分配) )。當(dāng)有一用戶程。當(dāng)有一用戶程序要裝入時(shí)，由內(nèi)存分配程序檢索該表，從中找出一個(gè)序要裝入時(shí)，由內(nèi)存分配程序檢索該表，從中找出一個(gè)能滿足要求的、尚未分配的分區(qū)，將之分配給該程序，能滿足要求的、尚未分配的分區(qū)，將之分配給該程序，然后將該表項(xiàng)中的狀態(tài)置為然后將該表項(xiàng)中的狀態(tài)置為“已分配已分配”；若未找到大?。蝗粑凑业酱笮∽銐虻姆謪^(qū)，則拒絕為該用戶程序分配內(nèi)存。足夠的分區(qū)，則拒絕為該用戶程序分配內(nèi)存。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院24操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)

23、C24 KB32 KB64 KB128 KB256 KB分區(qū)號(hào)大小/KB 起址/KB狀態(tài)11220已分配23232已分配36464已分配4128128未分配(b) 存儲(chǔ)空間分配情況(a) 分區(qū)說(shuō)明表第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院254.3.34.3.3動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之動(dòng)態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。在實(shí)現(xiàn)可變分區(qū)分配時(shí)，將涉及到分區(qū)分配內(nèi)存空間。在實(shí)現(xiàn)可變分區(qū)分配時(shí)，將涉及到分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法和分區(qū)的分配與分配中所用的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法和分區(qū)的分配與回收操作這樣三個(gè)問(wèn)

24、題。回收操作這樣三個(gè)問(wèn)題。1 1分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)為了實(shí)現(xiàn)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)的數(shù)據(jù)結(jié)為了實(shí)現(xiàn)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用來(lái)描述空閑分區(qū)和已分配分區(qū)的情況，為分配提構(gòu)，用來(lái)描述空閑分區(qū)和已分配分區(qū)的情況，為分配提供依據(jù)。常用的數(shù)據(jù)結(jié)構(gòu)有以下兩種形式：供依據(jù)。常用的數(shù)據(jù)結(jié)構(gòu)有以下兩種形式： 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院26(1)(1)空閑分區(qū)表。在系統(tǒng)中設(shè)置一張空閑分區(qū)表，用于空閑分區(qū)表。在系統(tǒng)中設(shè)置一張空閑分區(qū)表，用于記錄每個(gè)空閑分區(qū)的情況。每個(gè)空閑分區(qū)占一個(gè)表目，記錄每個(gè)空閑分區(qū)的情況。每個(gè)空閑分區(qū)占一個(gè)表目，表目中包括

25、分區(qū)序號(hào)、分區(qū)始址及分區(qū)的大小等數(shù)據(jù)表目中包括分區(qū)序號(hào)、分區(qū)始址及分區(qū)的大小等數(shù)據(jù)項(xiàng)。項(xiàng)。(2) (2) 空閑分區(qū)鏈。為了實(shí)現(xiàn)對(duì)空閑分區(qū)的分配和鏈接，空閑分區(qū)鏈。為了實(shí)現(xiàn)對(duì)空閑分區(qū)的分配和鏈接，在每個(gè)分區(qū)的起始部分，設(shè)置一些用于控制分區(qū)分配在每個(gè)分區(qū)的起始部分，設(shè)置一些用于控制分區(qū)分配的信息，以及用于鏈接各分區(qū)所用的前向指針；在分的信息，以及用于鏈接各分區(qū)所用的前向指針；在分區(qū)尾部則設(shè)置一后向指針，通過(guò)前、后向鏈接指針，區(qū)尾部則設(shè)置一后向指針，通過(guò)前、后向鏈接指針，可將所有的空閑分區(qū)鏈接成一個(gè)雙向鏈可將所有的空閑分區(qū)鏈接成一個(gè)雙向鏈第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院27前

26、向指針0N個(gè)字節(jié)可用后向指針0N+2N+2圖4-6空閑鏈結(jié)構(gòu) 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院282 2分區(qū)分配算法分區(qū)分配算法1) 1) 首次適應(yīng)算法首次適應(yīng)算法(first fit)(first fit)以空閑分區(qū)鏈為例。以空閑分區(qū)鏈為例。FFFF算法要求空閑分區(qū)鏈以地址算法要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內(nèi)存時(shí)，從鏈?zhǔn)组_(kāi)始順序查找，遞增的次序鏈接。在分配內(nèi)存時(shí)，從鏈?zhǔn)组_(kāi)始順序查找，直至找到一個(gè)大小能滿足要求的空閑分區(qū)為止；然后再直至找到一個(gè)大小能滿足要求的空閑分區(qū)為止；然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給按照作業(yè)的大小，從該分區(qū)中劃出一

27、塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑鏈中。若從鏈?zhǔn)字闭?qǐng)求者，余下的空閑分區(qū)仍留在空閑鏈中。若從鏈?zhǔn)字敝伶溛捕疾荒苷业揭粋€(gè)能滿足要求的分區(qū)，則此次內(nèi)存至鏈尾都不能找到一個(gè)能滿足要求的分區(qū)，則此次內(nèi)存分配失敗，返回。分配失敗，返回。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院29 該算法傾向于優(yōu)先利用內(nèi)存中低址部分的空閑該算法傾向于優(yōu)先利用內(nèi)存中低址部分的空閑分區(qū)，從而保留了高址部分的大空閑區(qū)。這給為以分區(qū)，從而保留了高址部分的大空閑區(qū)。這給為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。其后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。其缺點(diǎn)是低址部分不斷被劃分，會(huì)留下許多難以利

28、用缺點(diǎn)是低址部分不斷被劃分，會(huì)留下許多難以利用的、很小的空閑分區(qū)，而每次查找又都是從低址部的、很小的空閑分區(qū)，而每次查找又都是從低址部分開(kāi)始，這無(wú)疑會(huì)增加查找可用空閑分區(qū)時(shí)的開(kāi)銷(xiāo)。分開(kāi)始，這無(wú)疑會(huì)增加查找可用空閑分區(qū)時(shí)的開(kāi)銷(xiāo)。 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院302) 2) 循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法(next fit)(next fit)該算法是由首次適應(yīng)算法演變而成的。在為進(jìn)該算法是由首次適應(yīng)算法演變而成的。在為進(jìn)程分配內(nèi)存空間時(shí)，不再是每次都從鏈?zhǔn)组_(kāi)始查找，程分配內(nèi)存空間時(shí)，不再是每次都從鏈?zhǔn)组_(kāi)始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始而是從上次找

29、到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找，直至找到一個(gè)能滿足要求的空閑分區(qū)，從中查找，直至找到一個(gè)能滿足要求的空閑分區(qū)，從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)。劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)。思考：有何優(yōu)缺點(diǎn)？第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院313) 3) 最佳適應(yīng)算法最佳適應(yīng)算法(best fit)(best fit)所謂所謂“最佳最佳”是指每次為作業(yè)分配內(nèi)存時(shí)，總是指每次為作業(yè)分配內(nèi)存時(shí)，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免避免“大材小用大材小用”。為了加速尋找，該算法要求將。為了加速尋找

30、，該算法要求將所有的空閑分區(qū)按其容量以從小到大的順序形成一所有的空閑分區(qū)按其容量以從小到大的順序形成一空閑分區(qū)鏈。這樣，第一次找到的能滿足要求的空空閑分區(qū)鏈。這樣，第一次找到的能滿足要求的空閑區(qū)，必然是最佳的。閑區(qū)，必然是最佳的。思考：有何優(yōu)缺點(diǎn)？第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院324) 4) 最壞適應(yīng)算法最壞適應(yīng)算法(worst fit)(worst fit)最壞適應(yīng)分配算法要掃描整個(gè)空閑分區(qū)表或鏈最壞適應(yīng)分配算法要掃描整個(gè)空閑分區(qū)表或鏈表，總是挑選一個(gè)最大的空閑區(qū)分割給作業(yè)使用，表，總是挑選一個(gè)最大的空閑區(qū)分割給作業(yè)使用，其優(yōu)點(diǎn)是可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片

31、其優(yōu)點(diǎn)是可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小，對(duì)中、小作業(yè)有利，同時(shí)最壞適應(yīng)分的幾率最小，對(duì)中、小作業(yè)有利，同時(shí)最壞適應(yīng)分配算法查找效率很高。該算法要求將所有的空閑分配算法查找效率很高。該算法要求將所有的空閑分區(qū)按其容量以從大到小的順序形成一空閑分區(qū)鏈，區(qū)按其容量以從大到小的順序形成一空閑分區(qū)鏈，查找時(shí)只要看第一個(gè)分區(qū)能否滿足作業(yè)要求。查找時(shí)只要看第一個(gè)分區(qū)能否滿足作業(yè)要求。思考：有何缺點(diǎn)？第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院335) 5) 快速適應(yīng)算法快速適應(yīng)算法(quick fit)(quick fit)該算法又稱為分類(lèi)搜索法，是將空閑分區(qū)根據(jù)該算法又稱為分類(lèi)

32、搜索法，是將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類(lèi)，對(duì)于每一類(lèi)具有相同容量的其容量大小進(jìn)行分類(lèi)，對(duì)于每一類(lèi)具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表，這樣，所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表，這樣，系統(tǒng)中存在多個(gè)空閑分區(qū)鏈表，同時(shí)在內(nèi)存中設(shè)立系統(tǒng)中存在多個(gè)空閑分區(qū)鏈表，同時(shí)在內(nèi)存中設(shè)立一張管理索引表，該表的每一個(gè)表項(xiàng)對(duì)應(yīng)了一種空一張管理索引表，該表的每一個(gè)表項(xiàng)對(duì)應(yīng)了一種空閑分區(qū)類(lèi)型，并記錄了該類(lèi)型空閑分區(qū)鏈表表頭的閑分區(qū)類(lèi)型，并記錄了該類(lèi)型空閑分區(qū)鏈表表頭的指針。指針。思考：有何缺點(diǎn)？第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院343 3分區(qū)分配操作分區(qū)分配操作1) 1) 分

33、配內(nèi)存分配內(nèi)存系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈( (表表) )中找到所中找到所需大小的分區(qū)。設(shè)請(qǐng)求的分區(qū)大小為需大小的分區(qū)。設(shè)請(qǐng)求的分區(qū)大小為u.sizeu.size，表中每個(gè)空閑，表中每個(gè)空閑分區(qū)的大小可表示為分區(qū)的大小可表示為m.sizem.size。若。若m.size-u.sizesize(sizem.size-u.sizesize(size是事先規(guī)定的不再切割的剩余分區(qū)的大小是事先規(guī)定的不再切割的剩余分區(qū)的大小) )，說(shuō)明多余部分，說(shuō)明多余部分太小，可不再切割，將整個(gè)分區(qū)分配給請(qǐng)求者；否則太小，可不再切割，將整個(gè)分區(qū)分配給請(qǐng)求者；否則( (即多即

34、多余部分超過(guò)余部分超過(guò)size)size)，從該分區(qū)中按請(qǐng)求的大小劃分出一塊內(nèi)，從該分區(qū)中按請(qǐng)求的大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑分區(qū)鏈存空間分配出去，余下的部分仍留在空閑分區(qū)鏈( (表表) )中。然中。然后，將分配區(qū)的首址返回給調(diào)用者。后，將分配區(qū)的首址返回給調(diào)用者。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院35從頭開(kā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第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)

35、算機(jī)與通信工程學(xué)院362) 2) 回收內(nèi)存回收內(nèi)存當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈的首址，從空閑區(qū)鏈( (表表) )中找到相應(yīng)的插入點(diǎn)，此中找到相應(yīng)的插入點(diǎn)，此時(shí)可能出現(xiàn)以下四種情況之一：時(shí)可能出現(xiàn)以下四種情況之一：(1) (1) 回收區(qū)與插入點(diǎn)的前一個(gè)空閑分區(qū)回收區(qū)與插入點(diǎn)的前一個(gè)空閑分區(qū)F1F1相鄰相鄰接。此時(shí)應(yīng)將回收區(qū)與插入點(diǎn)的前一分區(qū)合并，不接。此時(shí)應(yīng)將回收區(qū)與插入點(diǎn)的前一分區(qū)合并，不必為回收分區(qū)分配新表項(xiàng)，而只需修改其前一分區(qū)必為回收分區(qū)分配新表項(xiàng)，而只需修改其前一分區(qū)F1F1的大小。的大小。第四章 存儲(chǔ)器管理東北大學(xué)

36、秦皇島分校計(jì)算機(jī)與通信工程學(xué)院37 (2) (2) 回收分區(qū)與插入點(diǎn)的后一空閑分區(qū)回收分區(qū)與插入點(diǎn)的后一空閑分區(qū)F2F2相鄰相鄰接。此時(shí)也可將兩分區(qū)合并，形成新的空閑分區(qū)，接。此時(shí)也可將兩分區(qū)合并，形成新的空閑分區(qū)，但用回收區(qū)的首址作為新空閑區(qū)的首址，大小為兩但用回收區(qū)的首址作為新空閑區(qū)的首址，大小為兩者之和。者之和。 (3) (3) 回收區(qū)同時(shí)與插入點(diǎn)的前、后兩個(gè)分區(qū)鄰回收區(qū)同時(shí)與插入點(diǎn)的前、后兩個(gè)分區(qū)鄰接。此時(shí)將三個(gè)分區(qū)合并，使用接。此時(shí)將三個(gè)分區(qū)合并，使用F1F1的表項(xiàng)和的表項(xiàng)和F1F1的首的首址，取消址，取消F2F2的表項(xiàng)，大小為三者之和。的表項(xiàng)，大小為三者之和。第四章 存儲(chǔ)器管理東北

37、大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院38 (4) (4) 回收區(qū)既不與回收區(qū)既不與F1F1鄰接，又不與鄰接，又不與F2F2鄰接。這鄰接。這時(shí)應(yīng)為回收區(qū)單獨(dú)建立一新表項(xiàng)，填寫(xiě)回收區(qū)的首時(shí)應(yīng)為回收區(qū)單獨(dú)建立一新表項(xiàng)，填寫(xiě)回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈中的適當(dāng)位址和大小，并根據(jù)其首址插入到空閑鏈中的適當(dāng)位置。置。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院394.3.44.3.4伙伴系統(tǒng)伙伴系統(tǒng) 伙伴系統(tǒng)規(guī)定，無(wú)論已分配分區(qū)或空閑分區(qū)，伙伴系統(tǒng)規(guī)定，無(wú)論已分配分區(qū)或空閑分區(qū)，其大小均為其大小均為2 2的的k k次冪，次冪，k k為整數(shù)，為整數(shù)，lkmlkm，其中：，其中：2

38、21 1表示分配的最小分區(qū)的大小，表示分配的最小分區(qū)的大小，2 2m m表示分配的最大表示分配的最大分區(qū)的大小，通常分區(qū)的大小，通常2 2m m是整個(gè)可分配內(nèi)存的大小。是整個(gè)可分配內(nèi)存的大小。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院40 假設(shè)系統(tǒng)的可利用空間容量為假設(shè)系統(tǒng)的可利用空間容量為2 2m m個(gè)字，則系統(tǒng)個(gè)字，則系統(tǒng)開(kāi)始運(yùn)行時(shí)，整個(gè)內(nèi)存區(qū)是一個(gè)大小為開(kāi)始運(yùn)行時(shí)，整個(gè)內(nèi)存區(qū)是一個(gè)大小為2 2m m的空閑分的空閑分區(qū)。在系統(tǒng)運(yùn)行過(guò)程中，由于不斷的劃分，可能會(huì)區(qū)。在系統(tǒng)運(yùn)行過(guò)程中，由于不斷的劃分，可能會(huì)形成若干個(gè)不連續(xù)的空閑分區(qū)，將這些空閑分區(qū)根形成若干個(gè)不連續(xù)的空閑分區(qū)，將

39、這些空閑分區(qū)根據(jù)分區(qū)的大小進(jìn)行分類(lèi)，對(duì)于每一類(lèi)具有相同大小據(jù)分區(qū)的大小進(jìn)行分類(lèi)，對(duì)于每一類(lèi)具有相同大小的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)雙向鏈表。的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)雙向鏈表。這樣，不同大小的空閑分區(qū)形成了這樣，不同大小的空閑分區(qū)形成了k(0km)k(0km)個(gè)空個(gè)空閑分區(qū)鏈表。閑分區(qū)鏈表。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院41 當(dāng)需要為進(jìn)程分配一個(gè)長(zhǎng)度為當(dāng)需要為進(jìn)程分配一個(gè)長(zhǎng)度為n n的存儲(chǔ)空間時(shí)，首的存儲(chǔ)空間時(shí)，首先計(jì)算一個(gè)先計(jì)算一個(gè)i i值，使值，使2 2i i1 1n2n2i i，然后在空閑分區(qū)大小，然后在空閑分區(qū)大小為為2 2i i的空閑分區(qū)鏈

40、表中查找。若找到，即把該空閑分區(qū)的空閑分區(qū)鏈表中查找。若找到，即把該空閑分區(qū)分配給進(jìn)程。否則，表明長(zhǎng)度為分配給進(jìn)程。否則，表明長(zhǎng)度為2 2i i的空閑分區(qū)已經(jīng)耗盡，的空閑分區(qū)已經(jīng)耗盡，則在分區(qū)大小為則在分區(qū)大小為2 2i i1 1的空閑分區(qū)鏈表中尋找。若存在的空閑分區(qū)鏈表中尋找。若存在2 2i i1 1的一個(gè)空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個(gè)分的一個(gè)空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個(gè)分區(qū)，這兩個(gè)分區(qū)稱為一對(duì)伙伴，其中的一個(gè)分區(qū)用于分區(qū)，這兩個(gè)分區(qū)稱為一對(duì)伙伴，其中的一個(gè)分區(qū)用于分配，而把另一個(gè)加入分區(qū)大小為配，而把另一個(gè)加入分區(qū)大小為2 2i i的空閑分區(qū)鏈表中。的空閑分區(qū)鏈表中。第四

41、章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院42 若大小為若大小為2 2i i1 1的空閑分區(qū)也不存在，則需要查找大的空閑分區(qū)也不存在，則需要查找大小為小為2 2i i2 2的空閑分區(qū)，若找到則對(duì)其進(jìn)行兩次分割：第的空閑分區(qū)，若找到則對(duì)其進(jìn)行兩次分割：第一次，將其分割為大小為一次，將其分割為大小為2 2i i1 1的兩個(gè)分區(qū)，一個(gè)用于分的兩個(gè)分區(qū)，一個(gè)用于分配，一個(gè)加入到大小為配，一個(gè)加入到大小為2 2i i1 1的空閑分區(qū)鏈表中；第二次，的空閑分區(qū)鏈表中；第二次，將第一次用于分配的空閑區(qū)分割為將第一次用于分配的空閑區(qū)分割為2 2i i的兩個(gè)分區(qū)，一個(gè)的兩個(gè)分區(qū)，一個(gè)用于分配，一個(gè)加入

42、到大小為用于分配，一個(gè)加入到大小為2 2i i的空閑分區(qū)鏈表中。若的空閑分區(qū)鏈表中。若仍然找不到，則繼續(xù)查找大小為仍然找不到，則繼續(xù)查找大小為2 2i i3 3的空閑分區(qū)，以此的空閑分區(qū)，以此類(lèi)推。由此可見(jiàn)，在最壞的情況下，可能需要對(duì)類(lèi)推。由此可見(jiàn)，在最壞的情況下，可能需要對(duì)2 2k k的空的空閑分區(qū)進(jìn)行閑分區(qū)進(jìn)行k k次分割才能得到所需分區(qū)。次分割才能得到所需分區(qū)。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院43 與一次分配可能要進(jìn)行多次分割一樣，一次回與一次分配可能要進(jìn)行多次分割一樣，一次回收也可能要進(jìn)行多次合并，如回收大小為收也可能要進(jìn)行多次合并，如回收大小為2 2i i的空

43、閑的空閑分區(qū)時(shí)，若事先已存在分區(qū)時(shí)，若事先已存在2 2i i的空閑分區(qū)時(shí)，則應(yīng)將其的空閑分區(qū)時(shí)，則應(yīng)將其與伙伴分區(qū)合并為大小為與伙伴分區(qū)合并為大小為2 2i i1 1的空閑分區(qū)，若事的空閑分區(qū)，若事先已存在先已存在2 2i i1 1的空閑分區(qū)時(shí)，又應(yīng)繼續(xù)與其伙伴分的空閑分區(qū)時(shí)，又應(yīng)繼續(xù)與其伙伴分區(qū)合并為大小為區(qū)合并為大小為2 2i i2 2的空閑分區(qū)，依此類(lèi)推。的空閑分區(qū)，依此類(lèi)推。第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院444.3.5 4.3.5 哈希算法哈希算法 哈希算法就是利用哈希快速查找的優(yōu)點(diǎn)，以及哈希算法就是利用哈?？焖俨檎业膬?yōu)點(diǎn)，以及空閑分區(qū)在可利用空間表中的分布規(guī)

44、律，建立哈?？臻e分區(qū)在可利用空間表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，函數(shù)，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，該表的每一個(gè)表項(xiàng)記錄了一個(gè)對(duì)應(yīng)的空閑分區(qū)鏈表該表的每一個(gè)表項(xiàng)記錄了一個(gè)對(duì)應(yīng)的空閑分區(qū)鏈表表頭指針。表頭指針。當(dāng)進(jìn)行空閑分區(qū)分配時(shí)，根據(jù)所需空閑分區(qū)大當(dāng)進(jìn)行空閑分區(qū)分配時(shí)，根據(jù)所需空閑分區(qū)大小，通過(guò)哈希函數(shù)計(jì)算，即得到在哈希表中的位置，小，通過(guò)哈希函數(shù)計(jì)算，即得到在哈希表中的位置，從中得到相應(yīng)的空閑分區(qū)鏈表，實(shí)現(xiàn)最佳分配策略。從中得到相應(yīng)的空閑分區(qū)鏈表，實(shí)現(xiàn)最佳分配策略。 第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院454.3.64.3.

45、6可重定位分區(qū)分配可重定位分區(qū)分配1 1動(dòng)態(tài)重定位的引入動(dòng)態(tài)重定位的引入操作系統(tǒng)用戶程序1用戶程序310 KB30 KB用戶程序614 KB用戶程序926 KB操作系統(tǒng)用戶程序1用戶程序3用戶程序6用戶程序980 KB(a) 緊湊前(b) 緊湊后第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院46 將內(nèi)存中的所有作業(yè)進(jìn)行移動(dòng)，使它們?nèi)枷鄬?nèi)存中的所有作業(yè)進(jìn)行移動(dòng)，使它們?nèi)枷噜徑?，這樣，即可把原來(lái)分散的多個(gè)小分區(qū)拼接成鄰接，這樣，即可把原來(lái)分散的多個(gè)小分區(qū)拼接成一個(gè)大分區(qū)，這時(shí)就可把作業(yè)裝入該區(qū)。這種通過(guò)一個(gè)大分區(qū)，這時(shí)就可把作業(yè)裝入該區(qū)。這種通過(guò)移動(dòng)內(nèi)存中作業(yè)的位置，以把原來(lái)多個(gè)分散的小分移動(dòng)內(nèi)存中作業(yè)的位置，以把原來(lái)多個(gè)分散的小分區(qū)拼接成一個(gè)大分區(qū)的方法，稱為區(qū)拼接成一個(gè)大分區(qū)的方法，稱為“拼接拼接”或或“緊緊湊湊”第四章 存儲(chǔ)器管理東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院472 2動(dòng)態(tài)重定位的實(shí)現(xiàn)動(dòng)態(tài)重定位的實(shí)現(xiàn)LOAD1,25003650100250050002500相對(duì)地址10000重定位寄存器LOAD1,25003651