1、12本章內容本章內容5.1 存儲管理概述存儲管理概述5.2 程序的裝入和鏈接程序的裝入和鏈接5.3 連續分配方式連續分配方式5.4 基本分頁存儲管理方式基本分頁存儲管理方式 5.5 基本分段存儲管理方式基本分段存儲管理方式5.6 基本段頁式存儲管理方式基本段頁式存儲管理方式35.1 存儲管理概述存儲管理概述5.1.1 存儲器層次45.1.2 存儲存儲管理管理任務任務v操作系統須占用內存一部分存儲空間存放自身的操作系統須占用內存一部分存儲空間存放自身的程序、數據、管理信息以及與硬件接口信息等，程序、數據、管理信息以及與硬件接口信息等，一般稱這部分內存空間為系統區。系統區外的其一般稱這部分內存空間

2、為系統區。系統區外的其余內存空間存放用戶的程序和數據，稱為用戶區。余內存空間存放用戶的程序和數據，稱為用戶區。存儲管理主要是對用戶區進行管理，它包括以下存儲管理主要是對用戶區進行管理，它包括以下4 4項任務項任務。 （1 1）內存分配和回收）內存分配和回收 （2 2）地址變換）地址變換 （3 3）內存保護）內存保護 （4 4）內存擴充）內存擴充55.1.3 存儲存儲管理管理目標目標(1)內存結構細節對于用戶和用戶程序要透明。在高內存結構細節對于用戶和用戶程序要透明。在高級程序設計語言和匯編語言中將源程序和目標程級程序設計語言和匯編語言中將源程序和目標程序進行分離，源程序獨立于內存物理地址。序進

3、行分離，源程序獨立于內存物理地址。(2)提高內存的利用率，解決大程序和小內存之間的提高內存的利用率，解決大程序和小內存之間的矛盾。通過對存儲空間采取不同的管理方式，解矛盾。通過對存儲空間采取不同的管理方式，解決內存管理中的碎片問題，提高內存利用率。決內存管理中的碎片問題，提高內存利用率。(3)為用戶程序完成程序裝入。編譯程序產生可執行為用戶程序完成程序裝入。編譯程序產生可執行程序時，在可執行目標程序中生成地址重定位所程序時，在可執行目標程序中生成地址重定位所需信息，例如程序長度、數據區長度等。需信息，例如程序長度、數據區長度等。65.1.3 存儲存儲管理管理目標目標(4)解決內存速度與解決內存

4、速度與CPU速度不匹配問題。為了解決速度不匹配問題。為了解決內存速度與內存速度與CPU速度不匹配問題，引入了高速緩速度不匹配問題，引入了高速緩存。存。(5)實現內存保護和共享。內存保護是確保并發執行實現內存保護和共享。內存保護是確保并發執行的各個進程在所分配的存儲區內操作，互不干擾，的各個進程在所分配的存儲區內操作，互不干擾，通常由軟硬件結合方式實現。通常由軟硬件結合方式實現。75.2 程序的裝入和鏈接程序的裝入和鏈接鏈接程序裝入模塊第二步第三步裝入程序內存第一步庫編譯程序產生的目標模塊85.2.1 幾個幾個基本概念基本概念1.相對地址與相對地址空間相對地址與相對地址空間v在用匯編語言或高級語

5、言編寫的程序中，數據和在用匯編語言或高級語言編寫的程序中，數據和子程序通常用符號名進行訪問。程序中各種符號子程序通常用符號名進行訪問。程序中各種符號名集合所限定的空間稱作程序名字空間。名集合所限定的空間稱作程序名字空間。v經匯編或編譯程序處理后，源程序中的各種符號經匯編或編譯程序處理后，源程序中的各種符號名轉換成由機器指令和數據組成的目標程序，用名轉換成由機器指令和數據組成的目標程序，用相對地址替換符號地址。相對地址替換符號地址。v相對地址：相對于程序首指令相對地址：相對于程序首指令(通常為通常為0)的地址。的地址。v目標程序中的邏輯地址集合稱作該程序的相對地目標程序中的邏輯地址集合稱作該程序

6、的相對地址空間，又稱作邏輯地址空間。址空間，又稱作邏輯地址空間。95.2.1 幾個幾個基本概念基本概念2.絕對地址與絕對地址空間絕對地址與絕對地址空間v程序在內存空間中的實際存儲單元地址稱做物理程序在內存空間中的實際存儲單元地址稱做物理地址或絕對地址。內存空間是指物理內存中全部地址或絕對地址。內存空間是指物理內存中全部存儲單元的集合所限定的空間。物理地址的總體存儲單元的集合所限定的空間。物理地址的總體構成運行用戶程序的物理地址空間，又稱絕對地構成運行用戶程序的物理地址空間，又稱絕對地址空間。址空間。vCPU直接使用物理地址存取空間中的指令和數據，直接使用物理地址存取空間中的指令和數據，完成用戶

7、程序或系統程序。相對地址空間的大小完成用戶程序或系統程序。相對地址空間的大小由源程序決定，絕對地址空間的大小由系統硬件由源程序決定，絕對地址空間的大小由系統硬件配置決定。一個程序只有從相對地址空間裝入絕配置決定。一個程序只有從相對地址空間裝入絕對地址空間后才能運行。對地址空間后才能運行。105.2.1 幾個幾個基本概念基本概念3.地址重定位地址重定位v當一個程序的相對地址裝入到與其邏輯地址空間當一個程序的相對地址裝入到與其邏輯地址空間不一致的絕對地址空間中時，為了保證程序的正不一致的絕對地址空間中時，為了保證程序的正確運行，必須把指令和數據的邏輯地址轉換為物確運行，必須把指令和數據的邏輯地址轉

8、換為物理地址，這項工作稱為地址重定位。理地址，這項工作稱為地址重定位。v地址重定位通常有靜態地址重定位和動態地址重地址重定位通常有靜態地址重定位和動態地址重定位兩種方式。定位兩種方式。 靜態地址重定位靜態地址重定位 動態地址重定位動態地址重定位115.2.2 程序程序的裝入的裝入v程序的程序的裝入裝入指給程序的指令和數據分配物指給程序的指令和數據分配物理內存空間，也常被稱為理內存空間，也常被稱為加載加載。一個程序。一個程序要運行必須得裝入內存，這需要將指令和要運行必須得裝入內存，這需要將指令和數據的邏輯地址轉換為物理地址，即需要數據的邏輯地址轉換為物理地址，即需要進行地址變換。進行地址變換。v

9、根據地址變換發生時機，裝入方式分為絕根據地址變換發生時機，裝入方式分為絕對裝入方式、可重定位裝入方式和動態運對裝入方式、可重定位裝入方式和動態運行時裝入方式三種。行時裝入方式三種。125.2.2 程序程序的裝入的裝入1 1、絕對裝入方式、絕對裝入方式v 在可執行文件中記錄內存地址，裝入時直接定位在上述在可執行文件中記錄內存地址，裝入時直接定位在上述( (即文件中記錄的地址即文件中記錄的地址) )內存地址。內存地址。v 優點：裝入過程簡單。優點：裝入過程簡單。v 缺點：過于依賴于缺點：過于依賴于硬件結構，不適于多道硬件結構，不適于多道程序系統。程序系統。135.2.2 程序程序的裝入的裝入2、可

10、重定位裝入方式、可重定位裝入方式v當一個地址裝入與其地址空間不一致的存儲當一個地址裝入與其地址空間不一致的存儲空間中，就得要進行地址變換。也就是說將空間中，就得要進行地址變換。也就是說將虛地址映射為內存地址，把這種作法叫做虛地址映射為內存地址，把這種作法叫做地地址重定位或地址映射。址重定位或地址映射。v在在裝入裝入一個作業時，把作業中的指令相對地一個作業時，把作業中的指令相對地址址全部轉換全部轉換為絕對地址（地址轉換工作是在為絕對地址（地址轉換工作是在作業執行前集中一次完成的）在作業執行過作業執行前集中一次完成的）在作業執行過程中就無須再進行地址轉換工作。又稱程中就無須再進行地址轉換工作。又稱

11、靜態靜態重定位裝入方式。重定位裝入方式。145.2.2 程序程序的裝入的裝入2、可重定位裝入方式、可重定位裝入方式v優點：不需硬件支持，優點：不需硬件支持，可以裝入有限多道程序可以裝入有限多道程序（如（如MS DOS中的中的TSR）。）。v缺點：一個程序通常需缺點：一個程序通常需要占用連續的要占用連續的 內存空內存空間，程序裝間，程序裝 入內存后入內存后不能移動。不能移動。 不易實現不易實現共享。共享。155.2.2 程序程序的裝入的裝入3、動態運行時裝入方式、動態運行時裝入方式v可重定位裝入方式雖然可用于可重定位裝入方式雖然可用于多道程序系統多道程序系統，但程，但程序執行期間如果在內存中發生

12、移動，則程序的物理序執行期間如果在內存中發生移動，則程序的物理地址都發生改變，須修改全部物理地址，否則程序地址都發生改變，須修改全部物理地址，否則程序將無法正確執行。所以，采用可重定位方式把程序將無法正確執行。所以，采用可重定位方式把程序裝入內存后，程序在內存中一般不再移動。裝入內存后，程序在內存中一般不再移動。v但實際應用中，程序在內存中的位置可能經常需要但實際應用中，程序在內存中的位置可能經常需要改變。改變。v動態運行時裝入方式是在動態運行時裝入方式是在CPU執行訪問指令執行訪問指令時，時，才將要訪問的程序或數據的邏輯地址轉換為物理地才將要訪問的程序或數據的邏輯地址轉換為物理地址。址。16

13、5.2.2 程序程序的裝入的裝入3、動態運行時裝入方式、動態運行時裝入方式v動態運行時裝入方式的優點是操作系統可將一個動態運行時裝入方式的優點是操作系統可將一個程序離散地存放在內存空間。程序離散地存放在內存空間。v在在程序的整個執行期間，允許程序在內存中改變程序的整個執行期間，允許程序在內存中改變位置位置。v這種加載方式有利于提高內存利用率，也為實現這種加載方式有利于提高內存利用率，也為實現虛擬存儲器提供了基礎。虛擬存儲器提供了基礎。v動態運行時裝入方式的缺點是需要硬件支持，操動態運行時裝入方式的缺點是需要硬件支持，操作系統實現較為復雜。作系統實現較為復雜。17動態地址重定位示意圖動態地址重定

14、位示意圖 1500 12345Load A 500 內存空間內存空間5001000+ VR BR500100 12345Load A 500 0 虛擬空間（作業地址空間）虛擬空間（作業地址空間）.3動態運行時裝入方式動態運行時裝入方式185.2.3 程序程序的鏈接的鏈接v根據鏈接時間的不同，可把鏈接分成如下三根據鏈接時間的不同，可把鏈接分成如下三種：種：(1) 靜態鏈接靜態鏈接(2) 裝入時動態鏈接裝入時動態鏈接(3) 運行時動態鏈接運行時動態鏈接191靜態鏈接方式靜態鏈接方式(Static Linking)p在程序運行之前，先將各目標模塊及它們在程序運行之前，先將各目標模塊及它們所需的庫函數

15、，鏈接成一個完整的裝配模所需的庫函數，鏈接成一個完整的裝配模塊，以后塊，以后不再拆開不再拆開。我們把這種。我們把這種事先事先進行進行鏈接的方式稱為靜態鏈接方式。鏈接的方式稱為靜態鏈接方式。p鏈接時需要進行下面的修改：鏈接時需要進行下面的修改：201靜態鏈接方式靜態鏈接方式(Static Linking)(1) 對相對地址進行修改。在由編譯程序所產生的所對相對地址進行修改。在由編譯程序所產生的所有目標模塊中，使用的都是相對地址，其起始地有目標模塊中，使用的都是相對地址，其起始地址都為址都為0，每個模塊中的地址都是相對于起始地址，每個模塊中的地址都是相對于起始地址計算的。計算的。 (2) 變換外部

16、調用符號。將每個模塊中所用的外部調變換外部調用符號。將每個模塊中所用的外部調用符號也都變換為相對地址，如下圖所示。這種用符號也都變換為相對地址，如下圖所示。這種先進行鏈接所形成的一個完整的裝入模塊，又稱先進行鏈接所形成的一個完整的裝入模塊，又稱為為可執行文件可執行文件。通常都不再拆開它，要運行時可。通常都不再拆開它，要運行時可直接將它裝入內存。這種事先進行鏈接，以后不直接將它裝入內存。這種事先進行鏈接，以后不再拆開的鏈接方式，稱為再拆開的鏈接方式，稱為靜態鏈接靜態鏈接方式。方式。21模塊模塊ACALL B；Return；0L-15.2.3 程序程序的鏈接的鏈接模塊模塊BCALL C；Retur

17、n；0M-1模塊模塊CReturn；0N-1(a) 目標模塊目標模塊模塊模塊AJMP L；Return；0L-1模塊模塊BJMP L+M；Return；LL+M-1模塊模塊CReturn；L+ML+M+N-1(b) 裝入模塊裝入模塊222裝入時動態鏈接裝入時動態鏈接(Load-time Dynamic Linking)v這是指將用戶源程序編譯后所得到的一組目標模這是指將用戶源程序編譯后所得到的一組目標模塊，在裝入內存時，采用塊，在裝入內存時，采用邊裝入邊鏈接邊裝入邊鏈接的鏈接方的鏈接方式。式。v用戶源程序經編譯后所得的目標模塊，是在裝入用戶源程序經編譯后所得的目標模塊，是在裝入內存時邊裝入邊鏈

18、接的，即在裝入一個目標模塊內存時邊裝入邊鏈接的，即在裝入一個目標模塊時，若發生一個外部模塊調用事件，將引起裝入時，若發生一個外部模塊調用事件，將引起裝入程序去找出相應的外部目標模塊，并將它裝入內程序去找出相應的外部目標模塊，并將它裝入內存，還要修改目標模塊中的相對地址。存，還要修改目標模塊中的相對地址。v裝入時動態鏈接方式有以下優點：裝入時動態鏈接方式有以下優點：(1) 便于修改和更新。便于修改和更新。(2) 便于實現對目標模塊的共享。便于實現對目標模塊的共享。233運行時動態鏈接運行時動態鏈接(Run-time Dynamic Linking)v在許多情況下，應用程序在運行時，每次要運行在許

19、多情況下，應用程序在運行時，每次要運行的模塊可能是不相同的。的模塊可能是不相同的。v但由于事先無法知道本次要運行哪些模塊，故只但由于事先無法知道本次要運行哪些模塊，故只能是將所有可能要運行到的模塊都全部裝入內存能是將所有可能要運行到的模塊都全部裝入內存，并在裝入時全部鏈接在一起。，并在裝入時全部鏈接在一起。v顯然這是低效的。顯然這是低效的。v運行時動態鏈接運行時動態鏈接方式，是將對某些目標模塊的鏈方式，是將對某些目標模塊的鏈接推遲到程序執行時需要該接推遲到程序執行時需要該(目標目標)模塊時，才對模塊時，才對它進行的鏈接，亦即，在執行過程中，當發現一它進行的鏈接，亦即，在執行過程中，當發現一個被

20、調用模塊尚未裝入內存時，立即由個被調用模塊尚未裝入內存時，立即由OS去找到去找到該模塊并將之裝入內存，把它鏈接到調用者模塊該模塊并將之裝入內存，把它鏈接到調用者模塊上。上。245.3 連續分配方式連續分配方式 連續分配方式是指為用戶進程分配連連續分配方式是指為用戶進程分配連續內存空間的內存管理方式。早期操作系續內存空間的內存管理方式。早期操作系統都是采用連續分配方式管理內存。連續統都是采用連續分配方式管理內存。連續分配方式通常分為：單一連續分配、固定分配方式通常分為：單一連續分配、固定分區分配、可變分區分配、動態可重定位分區分配、可變分區分配、動態可重定位分區分配等分區分配等255.3.1 單

21、一連續分配單一連續分配v單一連續分配方式是最簡單的一種存儲管理方式，單一連續分配方式是最簡單的一種存儲管理方式，只能用于單用戶、單任務的操作系統中。在此方只能用于單用戶、單任務的操作系統中。在此方式中，把內存分為系統區和用戶區兩部分。式中，把內存分為系統區和用戶區兩部分。v系統區僅提供給操作系統使用；用戶區是指除系系統區僅提供給操作系統使用；用戶區是指除系統區之外的全部內存空間，提供給用戶作業使用，統區之外的全部內存空間，提供給用戶作業使用，一次只允許一個作業進入內存。作業往往只占用一次只允許一個作業進入內存。作業往往只占用戶區的一部分，其余部分空閑，內存利用率較低。戶區的一部分，其余部分空閑

22、，內存利用率較低。v單一連續分配存儲管理方式只適用于程序的絕對單一連續分配存儲管理方式只適用于程序的絕對裝入。裝入。265.3.2 固定分區分配固定分區分配v 基本思想：基本思想：把內存劃分成若干個把內存劃分成若干個大小固定，個數固定大小固定，個數固定的存儲區域，每個存的存儲區域，每個存儲區域稱為一個分區，儲區域稱為一個分區，每個分區中裝入一道每個分區中裝入一道作業，每個作業只裝作業，每個作業只裝入一個分區中。入一個分區中。20K28K60K124K256KOS進程進程A（6K）進程進程B（25K）進程進程C（36K）內存狀態內存狀態275.3.2 固定分區分配固定分區分配1. 劃分分區的方法

23、劃分分區的方法 分區大小相等，即所有內存分區大小相等。其缺分區大小相等，即所有內存分區大小相等。其缺點是當分區太大時，會造成內存空間浪費；當點是當分區太大時，會造成內存空間浪費；當分區太小時，會造成大作業無法運行。它主要分區太小時，會造成大作業無法運行。它主要適用于一臺計算機控制多個相同對象的場合。適用于一臺計算機控制多個相同對象的場合。 分區大小不等，即所有內存分區大小不等。可以分區大小不等，即所有內存分區大小不等。可以把內存劃分成多個較小分區、適量中等分區及把內存劃分成多個較小分區、適量中等分區及少量大分區，以適應不同程序的需求。少量大分區，以適應不同程序的需求。285.3.2 固定分區分

24、配固定分區分配2. 內存的分配與回收內存的分配與回收v為了便于內存分配，通常將分區按為了便于內存分配，通常將分區按大小進行排隊大小進行排隊，并為之建立一張分區使用表，其中各表項包括，并為之建立一張分區使用表，其中各表項包括每個分區的起始地址、大小及狀態每個分區的起始地址、大小及狀態(是否已分配是否已分配)，見下圖，見下圖a所示。所示。v當有一用戶程序要裝入時，由內存分配程序檢索當有一用戶程序要裝入時，由內存分配程序檢索該表，從中找出一個能滿足要求的、尚未分配的該表，從中找出一個能滿足要求的、尚未分配的分區，將之分配給該程序，然后將該表項中的狀分區，將之分配給該程序，然后將該表項中的狀態置為態置

25、為“已分配已分配”；v若未找到大小足夠的分區，則拒絕為該用戶程序若未找到大小足夠的分區，則拒絕為該用戶程序分配內存。存儲空間分配情況如下圖分配內存。存儲空間分配情況如下圖b所示。所示。2920K28K60K124K256K5.3.2 固定分區分配固定分區分配OS進程進程A（6K）進程進程B（25K）進程進程C（36K）（a）分區說明表）分區說明表（b）內存狀態）內存狀態區號區號分區長度分區長度起始地起始地址址狀態狀態1 18K8K20K20K已分配已分配2 232K32K28K28K已分配已分配3 364K64K60K60K已分配已分配4 4132K132K124K124K未分配未分配圖圖 固

26、定分區使用表固定分區使用表 305.3.2 固定分區分配固定分區分配v當用戶程序要裝入執行時當用戶程序要裝入執行時,通過請求表通過請求表提出內存分配要求和所要求的內存空提出內存分配要求和所要求的內存空間大小。從分區說明表中查詢，從中間大小。從分區說明表中查詢，從中找出一個大小滿足要求的空閑分區，找出一個大小滿足要求的空閑分區，并將其分配給申請者。并將其分配給申請者。v 固定分區的回收，只需將對應的分區固定分區的回收，只需將對應的分區狀態置為未使用即可。狀態置為未使用即可。31要求要求Xk大小分區大小分區取分區說明表第一項取分區說明表第一項狀態位置正在使用狀態位置正在使用取下一表項取下一表項無法

27、分配無法分配該分區空閑？該分區空閑？分區長度分區長度Xk?表結束？表結束？返回分區號返回分區號否否否否否否是是是是是是圖圖5.10 5.10 固定分區分配算法固定分區分配算法325.3.2 固定分區分配固定分區分配3. 地址變換地址變換v 固定分區存儲的地址變換即可采用靜態重固定分區存儲的地址變換即可采用靜態重定位，也可采用動態重定位。定位，也可采用動態重定位。335.3.2 固定分區分配固定分區分配v優點：優點： 實現簡單、開銷小實現簡單、開銷小v 缺點：缺點： 必須預先能夠估計作業要占用的空間，必須預先能夠估計作業要占用的空間，分區總數固定，限制了并發作業的的數分區總數固定，限制了并發作業

28、的的數目；目； 內碎片（占用分區之內未被利用的空間內碎片（占用分區之內未被利用的空間）造成浪費）造成浪費345.3.3 可變分區分配可變分區分配1.1. 可變分區的原理可變分區的原理v固定分區主存利用率不高，使用起來不靈活，固定分區主存利用率不高，使用起來不靈活，所以出現了可變分區的管理技術。所以出現了可變分區的管理技術。v動態分區原則：存儲空間的劃分是在作業裝入動態分區原則：存儲空間的劃分是在作業裝入時進行的。從可用的自由存儲空間內，劃出一時進行的。從可用的自由存儲空間內，劃出一個大小正好等于作業大小的存儲區，并分配給個大小正好等于作業大小的存儲區，并分配給這一作業。這一作業。v動態分區，在

29、系統初啟時，除了操作系統中常動態分區，在系統初啟時，除了操作系統中常駐內存部分之外，只有一個空閑分區。駐內存部分之外，只有一個空閑分區。355.3.3 可變分區分配可變分區分配進程進程 A A（8K8K）進程進程 D D（124K124K）進程進程 B B（16K16K）進程進程 C C（64K64K）OSOS進程進程A(8K)A(8K)進程進程B(16K)B(16K)進程進程C(64K)C(64K)進程進程D(124K)D(124K)OSOS進程進程A(8K)A(8K)進程進程B(16K)B(16K)進程進程C(64K)C(64K)OSOS進程進程A(8K)A(8K)進程進程B(16K)B(

30、16K)OSOS進程進程A(8K)A(8K)36內存分配變化過程內存分配變化過程OSA（8K）8K空閑區空閑區B（16K）E（50K）D（124K）14K空閑區空閑區F（16K）OSA（8K）8K空閑區空閑區空閑區空閑區16KE（50K）F（16K）空閑合并空閑合并124+14=138K進程進程E（50K）進程進程F（16K）進入內存進入內存進程進程B（16K）進程進程D（124K）完成完成OSA（8K）24K空閑區空閑區B（16K）C完成（完成（64K）空閑區空閑區D（124K）375.3.3 可變分區分配可變分區分配2. 可變分區分配的數據結構可變分區分配的數據結構為了便于內存的分配與回收

31、，需設置用于記錄為了便于內存的分配與回收，需設置用于記錄分區使用情況的數據結構。分區使用情況的數據結構。 空閑分區表。系統設置一張空閑分區表，記錄內空閑分區表。系統設置一張空閑分區表，記錄內存中每個空閑分區的序號、大小和起始地址，存中每個空閑分區的序號、大小和起始地址，每個空閑分區在空閑分區表中占一個表目。每個空閑分區在空閑分區表中占一個表目。385.3.3 可變分區分配可變分區分配2. 可變分區分配的數據結構可變分區分配的數據結構 空閑分區鏈。為了實現對空閑分區的分配和鏈接，空閑分區鏈。為了實現對空閑分區的分配和鏈接，在每個空閑分區的起始單元中存儲兩個值，一在每個空閑分區的起始單元中存儲兩個

32、值，一個是空閑分區的大小，另一個是指向下一空閑個是空閑分區的大小，另一個是指向下一空閑分區的指針。分區的指針。395.3.3 可變分區分配可變分區分配2. 2. 可變分區分配的數據可變分區分配的數據結構結構已分配分區表。已分配分區表。系統設置系統設置一張已分配分區表，記一張已分配分區表，記錄內存中每個已分配分錄內存中每個已分配分區的大小、起始地址和區的大小、起始地址和狀態（記錄存放的作業狀態（記錄存放的作業名），每個已分配分區名），每個已分配分區在已分配分區表中占一在已分配分區表中占一個表目。個表目。起始地址起始地址 長度長度狀態狀態0K0K15K15KJ1J138K38K10K10KJ2J2

33、68K68K12K12KJ3J3110K110K10K10KJ4J4已分配分區表已分配分區表405.3.3 可變分區分配可變分區分配3.常用的空閑分區分配算法有以下四種：常用的空閑分區分配算法有以下四種： 首次適應（首次適應（first fit）算法）算法 循環首次適應（循環首次適應（next fit）算法）算法 最佳適應（最佳適應（best fit）算法）算法 最差適應（最差適應（worst fit）算法）算法413動態分區分配算法動態分區分配算法 首次適應算法首次適應算法(FF,FirstFit)v要求可用表或自由鏈按起始要求可用表或自由鏈按起始地址遞增地址遞增的次的次序排列。序排列。v從

34、表頭查詢，一旦找到大小滿足的分區就從表頭查詢，一旦找到大小滿足的分區就結束探索。結束探索。v例題：如圖所示是某一個時刻例題：如圖所示是某一個時刻J1、J2、J3、J4在在內存中的分配情況、空閑區表和已分區表，它們內存中的分配情況、空閑區表和已分區表，它們的長度分別是的長度分別是15KB、10KB、12KB、10KB。J5和和J6兩個新作業的長度分別為兩個新作業的長度分別為5KB和和13KB。按照。按照最先適應算法進行內存分配，描述分配后內存、最先適應算法進行內存分配，描述分配后內存、空閑區表以及已分區表的情況。空閑區表以及已分區表的情況。423動態分區分配算法動態分區分配算法最先適應算法分配前

35、的狀態最先適應算法分配前的狀態起始地址起始地址 長度長度狀態狀態0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J4已分區表已分區表0J1J4J3J21538486880110120起始地址起始地址 長度長度狀態狀態15K15K23K23K未分配未分配48K48K20K20K未分配未分配80K80K30K30K未分配未分配空閑區表空閑區表J5J5和和J6J6兩個新作業的長度分別為兩個新作業的長度分別為5KB5KB和和13KB13KB。433動態分區分配算法動態分區分配算法最先適應算法分配后的狀態最先適應算法分配后的狀態

36、起始地址起始地址長度長度狀態狀態0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J415K15K5K5KJ5J520K20K13K13KJ6J6已分區表起始地址起始地址長度長度狀態狀態33K33K5K5K未分配未分配48K48K20K20K未分配未分配80K80K30K30K未分配未分配空閑區表3848110J6J1J4J3J20156880120J533J5J5和和J6J6兩個新作業的長度分別為兩個新作業的長度分別為5KB5KB和和13KB13KB。44重點回顧重點回顧v死鎖的避免：銀行家算法死鎖的避免：銀行家算法v

37、死鎖的檢測與解除死鎖的檢測與解除45重點回顧重點回顧v相對地址與相對地址空間相對地址與相對地址空間v絕對地址與絕對地址空間絕對地址與絕對地址空間v地址重定位地址重定位46重點回顧重點回顧v程序程序的裝入的裝入 絕對裝入方式絕對裝入方式 可重定位裝入方式可重定位裝入方式 動態運行時裝入方式動態運行時裝入方式v程序鏈接程序鏈接 (1) (1) 靜態鏈接靜態鏈接 (2) (2) 裝入時動態鏈接裝入時動態鏈接(3) (3) 運行時動態鏈接運行時動態鏈接47重點回顧重點回顧v連續分配方式：是指為用戶進程分配連續連續分配方式：是指為用戶進程分配連續內存空間的內存管理方式。內存空間的內存管理方式。 單一連續

38、分配單一連續分配 固定分區分配：分區大小和個數固定固定分區分配：分區大小和個數固定 可變分區分配：分區大小和個數隨內存的動態可變分區分配：分區大小和個數隨內存的動態分配和回收變化分配和回收變化48重點回顧重點回顧 可變分區分配算法可變分區分配算法 首次適應（首次適應（first fit）算法）算法49從該空閑區中截取所需從該空閑區中截取所需大小，修改調整可用表大小，修改調整可用表從空閑區表第一從空閑區表第一表目順序查找表目順序查找從可用表中移去該從可用表中移去該表目，調整可用表表目，調整可用表取下一表項取下一表項無法分配無法分配該該 空閑區空閑區長度長度SIZE？該該 空閑區空閑區長度長度=S

39、IZE？表目查完？表目查完？返回分配起始地址返回分配起始地址否否否否是是是是是是否否圖圖 最先適應算法最先適應算法請求請求SIZESIZE大小的分區大小的分區503動態分區分配算法動態分區分配算法動態分區存儲管理可采用多動態分區存儲管理可采用多種數據結構對內存進行管理種數據結構對內存進行管理v每個空閑區用每個空閑區用map數據結數據結構構vstrut mapvunsigned m_size;vchar * m_addr;vstruct map cornmapN; m_addrm_addrm_sizem_sizem_addrm_addrm_sizem_size空閑區空閑區已分配已分配空閑區空閑區

40、已分配已分配空閑區空閑區已分配已分配513動態分區分配算法動態分區分配算法 最先適應法最先適應法vChar *malloc(struct map *mp,int size) /空閑表指針，空閑表指針，作業大小作業大小vint regint;vstruct map *bp;v/從從mp開始，只要開始，只要size不等于不等于0，逐個地址檢查，逐個地址檢查 m_addrm_addrm_sizem_sizem_addrm_addrm_sizem_size空閑區空閑區已分配已分配空閑區空閑區已分配已分配空閑區空閑區已分配已分配mp52for(bp=mp;bp-m_size;bp+) if(bp-m_s

41、ize=size) regint=bp-m_addr; bp-m_addr+=size;if(bp-m_size-=size)=0)/賦值并判斷賦值并判斷do bp+; (bp-1)-m_addr=bp-m_addr;while(bp-1)-m_size=bp-m_size);return(regint); return(0); m_addrm_addrm_sizem_sizem_addrm_addrm_sizem_size空閑區空閑區已分配已分配空閑區空閑區已分配已分配空閑區空閑區已分配已分配mp533動態分區分配算法動態分區分配算法 最先適應算法最先適應算法缺點：缺點： 由于查找總是從表首

42、開始，前面的空閑區由于查找總是從表首開始，前面的空閑區被分割的很小時，能滿足分配要求的可能被分割的很小時，能滿足分配要求的可能性就越小，查找次數越多性就越小，查找次數越多 碎片問題碎片問題543動態分區分配算法動態分區分配算法最佳適應算法最佳適應算法(BF,Best Fit)v要求可用表（空閑表）或自由鏈按分區要求可用表（空閑表）或自由鏈按分區大小遞增大小遞增的次序排列。的次序排列。v從表頭查詢，一旦找到大小滿足的分區從表頭查詢，一旦找到大小滿足的分區就結束探索就結束探索。553動態分區分配算法動態分區分配算法分配前的狀態分配前的狀態起始地址起始地址長度長度狀態狀態0K0K15K15KJ1J1

43、38K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J4已分區表起始地址起始地址 長度長度 狀態狀態15K15K23K23K未分配未分配48K48K20K20K未分配未分配80K80K30K30K未分配未分配空閑區表J5J5和和J6J6兩個新作業的長度分別為兩個新作業的長度分別為5KB5KB和和13KB13KB。起始地址起始地址 長度長度 狀態狀態48K48K20K20K未分配未分配15K15K23K23K未分配未分配80K80K30K30K未分配未分配空閑區表0J1J4J3J2153848688011012056 最佳適應算法分配后的狀態最佳適應算

44、法分配后的狀態起始地址起始地址長度長度狀態狀態0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J448K48K5K5KJ5J553K53K13K13KJ6J6已分區表起始地址起始地址長度長度狀態狀態66K66K2K2K未分配未分配15K15K23K23K未分配未分配80K80K30K30K未分配未分配空閑區表J6J3J1J4J201538486880110120J566J5J5和和J6J6兩個新作業的長度分別為兩個新作業的長度分別為5KB5KB和和13KB13KB。3動態分區分配算法動態分區分配算法573動態分區分配算

45、法動態分區分配算法最佳適應法最佳適應法v優點：優點： 分配后所剩余的空白塊會最小分配后所剩余的空白塊會最小 平均而言，只要查找一半的表格便能找到平均而言，只要查找一半的表格便能找到v缺點：缺點： 由于空閑區是按大小而不是按地址排序，因此由于空閑區是按大小而不是按地址排序，因此釋放時，要在整個鏈表上搜索地址相鄰的空閑區釋放時，要在整個鏈表上搜索地址相鄰的空閑區 空閑區分配后剩余部分成為碎片空閑區分配后剩余部分成為碎片583動態分區分配算法動態分區分配算法最差適應算法最差適應算法(WF)v按空閑區按空閑區大小遞減大小遞減的順序組成空閑區可用表的順序組成空閑區可用表或自由鏈。或自由鏈。v最壞適應算法

46、的思想與最佳適應算法相反，最壞適應算法的思想與最佳適應算法相反，將所有的空白分區按容量遞減的順序排列，最將所有的空白分區按容量遞減的順序排列，最前面的最大的空閑區就是找到的分區。該算法前面的最大的空閑區就是找到的分區。該算法是取所有空閑區中最大的一塊，把剩余的塊再是取所有空閑區中最大的一塊，把剩余的塊再變成一個新小一點的空閑區。變成一個新小一點的空閑區。59分配前的狀態分配前的狀態起始地址起始地址長度長度狀態狀態0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J4已分區表起始地址起始地址長度長度 狀態狀態15K15K2

47、3K23K未分配未分配48K48K20K20K未分配未分配80K80K30K30K未分配未分配空閑區表J5J5和和J6J6兩個新作業的長度分別為兩個新作業的長度分別為5KB5KB和和13KB13KB。起始地址起始地址 長度長度 狀態狀態80K80K30K30K未分配未分配15K15K23K23K未分配未分配48K48K20K20K未分配未分配空閑區表0J1J4J3J2153848688011012060 最壞適應算法分配后的狀態起始地址起始地址長度長度狀態狀態0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J480K8

48、0K5K5KJ5J585K85K13K13KJ6J6已分區表起始地址起始地址長度長度狀態狀態15K15K23K23K未分配未分配48K48K20K20K未分配未分配98K98K12K12K未分配未分配空閑區表J5J5和和J6J6兩個新作業的長度分別為兩個新作業的長度分別為5KB5KB和和13KB13KB。1538486880110120J1J4J3J20J5J6 98613動態分區分配算法動態分區分配算法最壞適應算法最壞適應算法v優點：優點： 分配時只需查找一次就可以成功分配時只需查找一次就可以成功v缺點：缺點：過早用掉大的空閑區，剩余的分區越過早用掉大的空閑區，剩余的分區越來越小來越小 ，無

49、法運行大程序，無法運行大程序623動態分區分配算法動態分區分配算法循環首次適應算法循環首次適應算法(next fit)v該算法是由首次適應算法演變而成的。在為進程該算法是由首次適應算法演變而成的。在為進程分配內存空間時，分配內存空間時，不再是不再是每次都從每次都從鏈首鏈首開始查找開始查找，而是，而是從上次找到從上次找到的空閑分區的的空閑分區的下一個下一個空閑分區空閑分區開始查找，直至找到一個能滿足要求的空閑分區開始查找，直至找到一個能滿足要求的空閑分區。v為實現該算法，應設置一起始查尋指針，用于指為實現該算法，應設置一起始查尋指針，用于指示下一次起始查尋的空閑分區。示下一次起始查尋的空閑分區。

50、v該算法能使內存中的空閑分區分布得更均勻，從該算法能使內存中的空閑分區分布得更均勻，從而減少了查找空閑分區時的開銷，但這樣會缺乏而減少了查找空閑分區時的開銷，但這樣會缺乏大的空閑分區。大的空閑分區。634動態分區時的回收與拼接動態分區時的回收與拼接當某一個用戶作業完成釋放所占分區時，系統當某一個用戶作業完成釋放所占分區時，系統應進行回收。應進行回收。在可變式分區中，應該檢查回收區與內存中前在可變式分區中，應該檢查回收區與內存中前后空閑區是否相鄰，后空閑區是否相鄰，若相鄰，則應進行合并，形成一個較大的空閑若相鄰，則應進行合并，形成一個較大的空閑區，并對相應的鏈表指針進行修改；區，并對相應的鏈表指

51、針進行修改；若不相鄰，應將空閑區插入到空閑區鏈表的適若不相鄰，應將空閑區插入到空閑區鏈表的適當位置。當位置。644動態分區時的回收與拼接動態分區時的回收與拼接654動態分區時的回收與拼接動態分區時的回收與拼接v釋放區鄰接的分區情況可能是：釋放區鄰接釋放區鄰接的分區情況可能是：釋放區鄰接的是另一進程的已分配區，或者是空閑區。的是另一進程的已分配區，或者是空閑區。v下面以首次適應法說明了系統回收該進程占下面以首次適應法說明了系統回收該進程占用區存在的四種可能情況。用區存在的四種可能情況。v設進程的釋放區為設進程的釋放區為R，與，與R相鄰的兩個空閑區相鄰的兩個空閑區分別為分別為F1和和F2。R的首地

52、址送的首地址送LOC，R的尾地的尾地址送址送LOC1，R的大小送的大小送SIZE。66(a)若釋放區若釋放區R與與F1相鄰接，即其低地址部分鄰相鄰接，即其低地址部分鄰接一空閑區。將接一空閑區。將R與與F1合并，合并后的空閑區合并，合并后的空閑區仍記為仍記為F1。4動態分區時的回收與拼接動態分區時的回收與拼接低地址低地址 高地址高地址空閑區空閑區 F1進程進程 P 占用區占用區2低地址低地址 高地址高地址占用區占用區2空閑區空閑區 F1(a)合并后合并后674動態分區時的回收與拼接動態分區時的回收與拼接如何判斷釋放區如何判斷釋放區R 是否與某個空閑區相鄰呢？是否與某個空閑區相鄰呢？只要從鏈首開始

53、查找即可：若只要從鏈首開始查找即可：若F1的首地址的首地址+F1的大小的大小=R的首地址，說明的首地址，說明R與與F1相鄰接。相鄰接。只要修改只要修改F1的大小的大小= F1的大小的大小+LOC，其它參，其它參數不變和在鏈中的位置不變。數不變和在鏈中的位置不變。684動態分區時的回收與拼接動態分區時的回收與拼接(b)若釋放區若釋放區R與與F2相鄰接，即其高地址部分鄰接一空相鄰接，即其高地址部分鄰接一空閑區。將閑區。將R與與F2合并，合并后的空閑區記仍記為合并，合并后的空閑區記仍記為F2。 判斷釋放區判斷釋放區R 是否與是否與F2空閑區相鄰，只要從鏈首開空閑區相鄰，只要從鏈首開始查找。始查找。

54、若若LOC+SIZE=F2的首地址，說明的首地址，說明R與與F2相鄰接。需相鄰接。需修改修改F2的首地址的首地址=LOC，F2的大小的大小= F2的大小的大小+SIZE。694動態分區時的回收與拼接動態分區時的回收與拼接(b)合并后合并后低地址低地址 高地址高地址占用區占用區1 進程進程 P 空閑區空閑區F2低地址低地址 高地址高地址空閑區空閑區F2占用區占用區1704動態分區時的回收與拼接動態分區時的回收與拼接(c) 若釋放區若釋放區R的高、低地址部分都鄰接一個空閑區。的高、低地址部分都鄰接一個空閑區。應將三個分區合并為一個大空閑區，并記為應將三個分區合并為一個大空閑區，并記為F1。 先將先

55、將R與與F2合并，記為合并，記為F2。再將再將F 2與與F1合并，并將合并，并將F2從鏈中刪除。從鏈中刪除。空閑區空閑區F1 釋放區釋放區R空閑區空閑區F2空閑區空閑區F1合并后合并后714動態分區時的回收與拼接動態分區時的回收與拼接(d)若釋放區若釋放區R上下都不鄰接空閑區，將其插入上下都不鄰接空閑區，將其插入空閑區鏈的適當位置即可。空閑區鏈的適當位置即可。725. 地址變換和分區保護地址變換和分區保護 地址變換地址變換 對動態分區可采用動態重定位裝入方式，程序和對動態分區可采用動態重定位裝入方式，程序和數據的地址轉換由硬件完成。數據的地址轉換由硬件完成。 硬件中設置兩個專門控制寄存器：基址

56、寄存器和硬件中設置兩個專門控制寄存器：基址寄存器和限長寄存器。基址寄存器存放分給作業使用的分區限長寄存器。基址寄存器存放分給作業使用的分區的起始地址，限長寄存器存放作業占用的分區的長的起始地址，限長寄存器存放作業占用的分區的長度。當作業占用度。當作業占用CPU 運行時，操作系統把該區的起運行時，操作系統把該區的起始地址和長度存入基址寄存器和限長寄存器。作業始地址和長度存入基址寄存器和限長寄存器。作業執行時，硬件根據基址寄存器進行地址轉換。執行時，硬件根據基址寄存器進行地址轉換。735. 地址變換和分區保護地址變換和分區保護 分區保護分區保護 基址基址/限長保護法限長保護法 保護鍵法保護鍵法 7

57、4動態分區優缺點動態分區優缺點v優點：優點：內存利用率提高，避免了內碎片內存利用率提高，避免了內碎片v 缺點：缺點： 出現了外碎片（分區之間未被利用出現了外碎片（分區之間未被利用的空間）的空間）755.3.4 動態可重定位分區分配動態可重定位分區分配1.緊湊（拼接）技術緊湊（拼接）技術 緊湊（拼接）技術將內存中的所有作業進行緊湊（拼接）技術將內存中的所有作業進行移動，同時修改每個程序的起始地址，使空移動，同時修改每個程序的起始地址，使空閑區全都相鄰接。這樣把分散的多個小分區閑區全都相鄰接。這樣把分散的多個小分區拼接成一個大分區，大作業可裝入該分區。拼接成一個大分區，大作業可裝入該分區。緊湊之后

58、要對被移動作業的物理地址進行相緊湊之后要對被移動作業的物理地址進行相應修改。應修改。765.3.4 動態可重定位分區分配動態可重定位分區分配775.3.4 動態可重定位分區分配動態可重定位分區分配2.動態重定位的實現過程動態重定位的實現過程v動態可重定位分區法中加載程序時采用動態可重定位分區法中加載程序時采用動態運行動態運行時裝入時裝入方式，作業裝入內存后的所有地址仍是邏方式，作業裝入內存后的所有地址仍是邏輯地址，將邏輯地址轉換為物理地址的工作推遲輯地址，將邏輯地址轉換為物理地址的工作推遲到程序指令執行時進行。到程序指令執行時進行。v系統中增設一個重定位寄存器，用它來存放程序系統中增設一個重定

59、位寄存器，用它來存放程序或數據在內存中的起始地址。程序執行時，真正或數據在內存中的起始地址。程序執行時，真正訪問的物理地址是邏輯地址與重定位寄存器中的訪問的物理地址是邏輯地址與重定位寄存器中的地址相加而形成的。地址相加而形成的。785.3.4 動態可重定位分區分配動態可重定位分區分配795.4 基本分頁存儲管理方式基本分頁存儲管理方式5.4.1 基本概念基本概念1頁面頁面v分頁存儲管理是將一個進程的邏輯地址空間分成分頁存儲管理是將一個進程的邏輯地址空間分成大小相等的若干片，這樣的片被稱為頁或頁面。大小相等的若干片，這樣的片被稱為頁或頁面。程序的頁面從程序的頁面從0開始編號，稱為頁號。一般情況下

60、開始編號，稱為頁號。一般情況下，進程長度不會剛好是頁面大小的整數倍，進程，進程長度不會剛好是頁面大小的整數倍，進程的最后一頁往往裝不滿，形成頁內碎片。的最后一頁往往裝不滿，形成頁內碎片。v頁式存儲管理中，頁面大小應適中。若頁面太小頁式存儲管理中，頁面大小應適中。若頁面太小，雖可減小頁內碎片，提高內存利用率，但會使，雖可減小頁內碎片，提高內存利用率，但會使每個進程占用較多頁面，進程的頁表過長，增加每個進程占用較多頁面，進程的頁表過長，增加內存存放頁表的開銷。反之，若頁面太大，雖可內存存放頁表的開銷。反之，若頁面太大，雖可減小頁表長度，但會增大頁內碎片。減小頁表長度，但會增大頁內碎片。805.4.