操作系統第13講new

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

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

3、于目前磁盤的I/O速度遠低于對主存的訪問速度，因此將頻繁使用的一部分磁盤數據和信息，暫時存放在磁盤緩存中，可減少訪問磁盤的次數。磁盤緩存本身并不是一種實際存在的存儲介質，它依托于固定磁盤，提供對主存儲器存儲空間的擴充，即利用主存中的存儲空間，來暫存從磁盤中讀出(或寫入)的信息。主存也可以看做是輔存的高速緩存，因為，輔存中的數據必須復制到主存方能使用；反之，數據也必須先存在主存中，才能輸出到輔存。 第四章 存儲器管理東北大學秦皇島分校計算機與通信工程學院6寄存器高速緩存主存磁盤緩存磁盤可移動存儲介質CPU寄存器主存輔存第四章 存儲器管理東北大學秦皇島分校計算機與通信工程學院7一個文件的數據可能出

4、現在存儲器層次的不同級別一個文件的數據可能出現在存儲器層次的不同級別中，例如，一個文件數據通常被存儲在輔存中中，例如，一個文件數據通常被存儲在輔存中( (如如硬盤硬盤) )，當其需要運行或被訪問時，就必須調入主，當其需要運行或被訪問時，就必須調入主存，也可以暫時存放在主存的磁盤高速緩存中。大存，也可以暫時存放在主存的磁盤高速緩存中。大容量的輔存常常使用磁盤，磁盤數據經常備份到磁容量的輔存常常使用磁盤，磁盤數據經常備份到磁帶或可移動磁盤組上，以防止硬盤故障時丟失數據。帶或可移動磁盤組上，以防止硬盤故障時丟失數據。有些系統自動地把老文件數據從輔存轉儲到海量存有些系統自動地把老文件數據從輔存轉儲到海

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

6、lute Loading Mode)(Absolute Loading Mode)在編譯時，如果知道程序將駐留在內存的什么位置，在編譯時，如果知道程序將駐留在內存的什么位置，那么，編譯程序將產生絕對地址的目標代碼。例如，事那么，編譯程序將產生絕對地址的目標代碼。例如，事先已知用戶程序先已知用戶程序( (進程進程) )駐留在從駐留在從R R處開始的位置，則編處開始的位置，則編譯程序所產生的目標模塊譯程序所產生的目標模塊( (即裝入模塊即裝入模塊) )便從便從R R處開始向處開始向上擴展。絕對裝入程序按照裝入模塊中的地址，將程序上擴展。絕對裝入程序按照裝入模塊中的地址，將程序和數據裝入內存。裝入模

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

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

9、島分校計算機與通信工程學院11LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作業(yè)地址空間內存空間第四章 存儲器管理東北大學秦皇島分校計算機與通信工程學院123 3動態(tài)運行時裝入方式動態(tài)運行時裝入方式(Dynamic Run-time Loading)(Dynamic Run-time Loading)可重定位裝入方式可將裝入模塊裝入到內存中任何可重定位裝入方式可將裝入模塊裝入到內存中任何允許的位置，故可用于多道程序環(huán)境；但這種方式并不允許的位置，故可用于多道程序環(huán)境；但這種方式并不允許程序運行時在內存中移動位置。因為，

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

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

12、接。這是指對某些目標模塊的鏈接，運行時動態(tài)鏈接。這是指對某些目標模塊的鏈接，是在程序執(zhí)行中需要該是在程序執(zhí)行中需要該( (目標目標) )模塊時，才對它進行的鏈接。模塊時，才對它進行的鏈接。 第四章 存儲器管理東北大學秦皇島分校計算機與通信工程學院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、 目標模塊(b) 裝入模塊第四章 存儲器管理東北大學秦皇島分校計算機與通信工程學院152 2裝入時動態(tài)鏈接裝入時動態(tài)鏈接(Load-time Dynamic Linking)(Load-time Dynamic Linking)用戶源程序經編譯后所得的目標模塊，是在裝用戶源程序經編譯后所得的目標模塊，是在裝入內存時邊裝入邊鏈接的，即在裝入一個目標模塊入內存時邊裝入邊鏈接的，即在裝入一個目標模塊時，若發(fā)生一個外部模塊調用事件，將引起裝入程時，若發(fā)生一個外部模塊調用事件，將引起裝入程序去找出相應的外部目標模塊，并將它裝入內存：序去找出相應的外部目標模塊，并將它裝入內存：第四章 存儲器管理東北大學秦

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

15、儲器管理東北大學秦皇島分校計算機與通信工程學院17(2) (2) 便于實現對目標模塊的共享。在采用靜態(tài)鏈接便于實現對目標模塊的共享。在采用靜態(tài)鏈接方式時，每個應用模塊都必須含有其目標模塊的拷方式時，每個應用模塊都必須含有其目標模塊的拷貝，無法實現對目標模塊的共享。但采用裝入時動貝，無法實現對目標模塊的共享。但采用裝入時動態(tài)鏈接方式，態(tài)鏈接方式，OSOS則很容易將一個目標模塊鏈接到幾則很容易將一個目標模塊鏈接到幾個應用模塊上，實現多個應用程序對該模塊的共享。個應用模塊上，實現多個應用程序對該模塊的共享。第四章 存儲器管理東北大學秦皇島分校計算機與通信工程學院183 3運行時動態(tài)鏈接運行時動態(tài)鏈接

16、(Run-time Dynamic Linking)(Run-time Dynamic Linking)在許多情況下，應用程序在運行時，每次要運行的在許多情況下，應用程序在運行時，每次要運行的模塊可能是不相同的。但由于事先無法知道本次要運行模塊可能是不相同的。但由于事先無法知道本次要運行哪些模塊，故只能是將所有可能要運行到的模塊都全部哪些模塊，故只能是將所有可能要運行到的模塊都全部裝入內存，并在裝入時全部鏈接在一起。顯然這是低效裝入內存，并在裝入時全部鏈接在一起。顯然這是低效的，因為往往會有些目標模塊根本就不運行。比較典型的，因為往往會有些目標模塊根本就不運行。比較典型的例子是作為錯誤處理用的

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

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

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

20、性，即當程序太小時，會造成內存空其缺點是缺乏靈活性，即當程序太小時，會造成內存空間的浪費；當程序太大時，一個分區(qū)又不足以裝入該程間的浪費；當程序太大時，一個分區(qū)又不足以裝入該程序，致使該程序無法運行。盡管如此，這種劃分方式仍序，致使該程序無法運行。盡管如此，這種劃分方式仍被用于利用一臺計算機去控制多個相同對象的場合，因被用于利用一臺計算機去控制多個相同對象的場合，因為這些對象所需的內存空間是大小相等的。例如，爐溫為這些對象所需的內存空間是大小相等的。例如，爐溫群控系統，就是利用一臺計算機去控制多臺相同的冶煉群控系統，就是利用一臺計算機去控制多臺相同的冶煉爐。爐。第四章 存儲器管理東北大學秦皇島

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

22、并為之建立一張分區(qū)使用表，其中各表項包括每個分區(qū)的起始地址、大小及狀態(tài)的起始地址、大小及狀態(tài)( (是否已分配是否已分配) )。當有一用戶程。當有一用戶程序要裝入時，由內存分配程序檢索該表，從中找出一個序要裝入時，由內存分配程序檢索該表，從中找出一個能滿足要求的、尚未分配的分區(qū)，將之分配給該程序，能滿足要求的、尚未分配的分區(qū)，將之分配給該程序，然后將該表項中的狀態(tài)置為然后將該表項中的狀態(tài)置為“已分配已分配”；若未找到大小；若未找到大小足夠的分區(qū)，則拒絕為該用戶程序分配內存。足夠的分區(qū)，則拒絕為該用戶程序分配內存。第四章 存儲器管理東北大學秦皇島分校計算機與通信工程學院24操作系統作業(yè)A作業(yè)B作業(yè)

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

24、題?；厥詹僮鬟@樣三個問題。1 1分區(qū)分配中的數據結構分區(qū)分配中的數據結構為了實現分區(qū)分配，系統中必須配置相應的數據結為了實現分區(qū)分配，系統中必須配置相應的數據結構，用來描述空閑分區(qū)和已分配分區(qū)的情況，為分配提構，用來描述空閑分區(qū)和已分配分區(qū)的情況，為分配提供依據。常用的數據結構有以下兩種形式：供依據。常用的數據結構有以下兩種形式： 第四章 存儲器管理東北大學秦皇島分校計算機與通信工程學院26(1)(1)空閑分區(qū)表。在系統中設置一張空閑分區(qū)表，用于空閑分區(qū)表。在系統中設置一張空閑分區(qū)表，用于記錄每個空閑分區(qū)的情況。每個空閑分區(qū)占一個表目，記錄每個空閑分區(qū)的情況。每個空閑分區(qū)占一個表目，表目中包括

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

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

27、塊內存空間分配給請求者，余下的空閑分區(qū)仍留在空閑鏈中。若從鏈首直請求者，余下的空閑分區(qū)仍留在空閑鏈中。若從鏈首直至鏈尾都不能找到一個能滿足要求的分區(qū)，則此次內存至鏈尾都不能找到一個能滿足要求的分區(qū)，則此次內存分配失敗，返回。分配失敗，返回。第四章 存儲器管理東北大學秦皇島分校計算機與通信工程學院29 該算法傾向于優(yōu)先利用內存中低址部分的空閑該算法傾向于優(yōu)先利用內存中低址部分的空閑分區(qū)，從而保留了高址部分的大空閑區(qū)。這給為以分區(qū)，從而保留了高址部分的大空閑區(qū)。這給為以后到達的大作業(yè)分配大的內存空間創(chuàng)造了條件。其后到達的大作業(yè)分配大的內存空間創(chuàng)造了條件。其缺點是低址部分不斷被劃分，會留下許多難以利

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

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

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

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

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

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

34、多余部分超過余部分超過size)size)，從該分區(qū)中按請求的大小劃分出一塊內，從該分區(qū)中按請求的大小劃分出一塊內存空間分配出去，余下的部分仍留在空閑分區(qū)鏈存空間分配出去，余下的部分仍留在空閑分區(qū)鏈( (表表) )中。然中。然后，將分配區(qū)的首址返回給調用者。后，將分配區(qū)的首址返回給調用者。第四章 存儲器管理東北大學秦皇島分校計算機與通信工程學院35從頭開始查表檢索完否？m.sizeu.size?m.size-u.sizesize?從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)分配給請求者修改有關數據結構返回返回繼續(xù)檢索下一個表項將該分區(qū)從鏈中移出YNNYYN第四章 存儲器管理東北大學秦皇島分校計

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

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

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

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

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

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

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

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

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

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

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