1、1北華大學北華大學.計算機科學技術學院計算機科學技術學院操作系統原理操作系統原理 課程課程 管管 理理 第第 4 章章操作系統原理操作系統原理 課程 第2張今天雖然主存價格已相當便宜，但主存容量仍然是計今天雖然主存價格已相當便宜，但主存容量仍然是計算機四大硬件資源中最關鍵而又最緊張的算機四大硬件資源中最關鍵而又最緊張的“瓶頸瓶頸”資源。資源。因此對主存的管理和有效使用仍然是今天操作系統十分重因此對主存的管理和有效使用仍然是今天操作系統十分重要的內容。要的內容。許多操作系統之間最明顯的區別特征之一往往是所使許多操作系統之間最明顯的區別特征之一往往是所使用的存儲管理方法不同。如用的存儲管理方法不同

2、。如OS/360-MFTOS/360-MFT采用采用固定分區固定分區存儲存儲管理技術，管理技術，OS/360-MTVOS/360-MTV是采用是采用可變分區可變分區存儲管理技術，存儲管理技術，OS/2OS/2，WindowsNT, WindowsNT, 是采用是采用虛擬存儲虛擬存儲管理技術。管理技術。主存儲器管理技術可分為兩大類：主存儲器管理技術可分為兩大類： 實存儲器實存儲器管理和管理和虛擬存儲器虛擬存儲器管理。管理。操作系統原理操作系統原理 課程 第3張本章目標本章目標熟悉三級存儲器結構：熟悉三級存儲器結構：CPU寄存器、內存、外存。寄存器、內存、外存。記住用戶程序的主要處理階段：編輯、編

3、譯、鏈接、裝入、記住用戶程序的主要處理階段：編輯、編譯、鏈接、裝入、運行。運行。理解存儲器管理的功能（內存分配與回收、地址映射、內存理解存儲器管理的功能（內存分配與回收、地址映射、內存保護與共享、虛擬存儲）和虛擬存儲器的基本特征（離散分保護與共享、虛擬存儲）和虛擬存儲器的基本特征（離散分配、多次性、對換性、虛擬性）。配、多次性、對換性、虛擬性）。牢固掌握概念：邏輯地址、物理地址、重定位、碎片、虛擬牢固掌握概念：邏輯地址、物理地址、重定位、碎片、虛擬存儲器、抖動、程序局部性原理等。存儲器、抖動、程序局部性原理等。掌握分區、分頁、分段存儲管理技術的實現思想，如何實現掌握分區、分頁、分段存儲管理技術

4、的實現思想，如何實現從邏輯地址到物理地址的轉換。從邏輯地址到物理地址的轉換。掌握虛擬頁式存儲中的頁面置換算法：先進先出法掌握虛擬頁式存儲中的頁面置換算法：先進先出法（FIFO）、最佳置換法（）、最佳置換法（OPT）、最近最少使用法（）、最近最少使用法（LRU） 操作系統原理操作系統原理 課程 第4張存存儲儲器器管管理理 本章結構本章結構基礎知識、程序的裝入和鏈接基礎知識、程序的裝入和鏈接連續分配方式連續分配方式分頁存儲管理方式分頁存儲管理方式分段存儲管理方式分段存儲管理方式段頁式存儲管理方式段頁式存儲管理方式固定分區固定分區動態分區動態分區基本頁式基本頁式虛擬頁式虛擬頁式基本段式基本段式虛擬段

5、式虛擬段式操作系統原理操作系統原理 課程 第5張4.1 存儲器管理的基礎知識存儲器管理的基礎知識 一一. .存儲器的層次結構：存儲器的層次結構：（ 過去常見為三級結構劃分，教材中為較細的劃分過去常見為三級結構劃分，教材中為較細的劃分） CPU寄存器寄存器 用戶程序在運行時應存放在用戶程序在運行時應存放在中，以便處理機訪問。但是由中，以便處理機訪問。但是由于主存容量有限。所以把那些不馬上使用的程序、數據放在外部于主存容量有限。所以把那些不馬上使用的程序、數據放在外部存儲器中，當用到時再把它們讀入主存。存儲器中，當用到時再把它們讀入主存。如如IBM的緩存最大傳輸速度為的緩存最大傳輸速度為每雙字每雙

6、字120225毫微秒毫微秒，主存的傳輸速度，主存的傳輸速度每字每字1微秒微秒。操作系統原理操作系統原理 課程 第6張1.CPU寄存器寄存器： 訪問速度最快，可與訪問速度最快，可與CPU協調工作、少量的、昂貴，用于加快協調工作、少量的、昂貴，用于加快存儲器的訪問速度，如存放操作數或作為地址寄存器。存儲器的訪問速度，如存放操作數或作為地址寄存器。 2.主主（內內）存存RAM： 處理機能直接訪問的存儲器處理機能直接訪問的存儲器。用來存放系統和用戶的程序和數。用來存放系統和用戶的程序和數據，其特點是存取速度快，存儲方式是以新換舊，斷電信息丟據，其特點是存取速度快，存儲方式是以新換舊，斷電信息丟失。失。

7、 3.輔存輔存（磁盤磁盤）： 處理機不能直接訪問的存儲器。用來存放用戶的各種信息，存處理機不能直接訪問的存儲器。用來存放用戶的各種信息，存取速度相對內存而言要慢得多，但它可用來長期保存用戶信息。取速度相對內存而言要慢得多，但它可用來長期保存用戶信息。4.1 存儲器管理的基礎知識存儲器管理的基礎知識 操作系統原理操作系統原理 課程 第7張. .教材中的教材中的多級多級層次結構：層次結構：寄存器寄存器高速緩存高速緩存主主 存存磁盤緩存磁盤緩存磁磁 盤盤 可移動存儲介質可移動存儲介質4.1 存儲器管理的基礎知識存儲器管理的基礎知識 操作系統原理操作系統原理 課程 第8張1： 物理地址是主存的真實地址

8、物理地址是主存的真實地址 ，是存儲控制部件能夠識別的主存，是存儲控制部件能夠識別的主存單元編號。把內存分成若干個大小相等的存儲單元，每個單元給單元編號。把內存分成若干個大小相等的存儲單元，每個單元給一個編號，這個編號稱為一個編號，這個編號稱為內存地址內存地址（物理地址物理地址、絕對地址絕對地址、實地實地址址），存儲單元占），存儲單元占8位，稱作字節（位，稱作字節（byte）。）。2.： 物理地址的集合稱為物理地址空間（主存地址空間），它是一物理地址的集合稱為物理地址空間（主存地址空間），它是一個一維的線性空間。個一維的線性空間。 內存內存014.1 存儲器管理的基礎知識存儲器管理的基礎知識 操

9、作系統原理操作系統原理 課程 第9張1.： 用戶編程序時所用的地址（或稱用戶編程序時所用的地址（或稱邏輯地址邏輯地址 、相對地址相對地址、虛地址虛地址 ），），是指相對于某個基準量編址時所使用的地址，常用于程序編寫和是指相對于某個基準量編址時所使用的地址，常用于程序編寫和編譯過程中。基本單位可與內存的基本單位相同，也可以不相同。編譯過程中。基本單位可與內存的基本單位相同，也可以不相同。（用戶的程序經過匯編或編譯后形成目標代碼，目標代碼通常采用相對地址的（用戶的程序經過匯編或編譯后形成目標代碼，目標代碼通常采用相對地址的形式，其首地址為形式，其首地址為0 0，其余指令中的地址都相對于首地址而編址

10、。），其余指令中的地址都相對于首地址而編址。）2.（邏輯地址空間、虛地址空間）（邏輯地址空間、虛地址空間）： 用戶的程序地址的集合稱為邏輯地址空間，它的編址總是從用戶的程序地址的集合稱為邏輯地址空間，它的編址總是從0開開始的，可以是一維線性空間，也可以是多維空間。始的，可以是一維線性空間，也可以是多維空間。 4.1 存儲器管理的基礎知識存儲器管理的基礎知識 虛地址空間虛地址空間010124.2 程序的裝入和鏈接程序的裝入和鏈接 程序和數據程序和數據裝入內存裝入內存創建進程創建進程運行程序運行程序源程序源程序轉換為可執行文件轉換為可執行文件編譯編譯 將源代碼編譯成若干將源代碼編譯成若干obj模塊

11、模塊;鏈接鏈接 由鏈接程序將由鏈接程序將obj模塊鏈接在一起模塊鏈接在一起,形成裝入模塊形成裝入模塊;裝入裝入 裝入程序將裝入模塊裝入內存裝入程序將裝入模塊裝入內存如何將一個用戶源程序變為一個可在內存中執行的程序？如何將一個用戶源程序變為一個可在內存中執行的程序？源程序源程序目標模塊目標模塊裝入程序裝入程序裝入模塊裝入模塊編譯編譯鏈接鏈接裝入裝入4.2 程序的裝入和鏈接程序的裝入和鏈接 庫鏈接程序裝入模塊裝入程序編譯程序產生的目標模塊第一步第二步第三步內存操作系統原理操作系統原理 課程 第12張4.2.1 程序的裝入程序的裝入1. 絕對裝入方式絕對裝入方式(Absolute Loading M

12、ode) 程序中所使用的程序中所使用的絕對地址絕對地址，既可在編譯或匯編時給出，既可在編譯或匯編時給出， 也可由程序員直接賦予。也可由程序員直接賦予。 但在由程序員直接給出絕對地址時，但在由程序員直接給出絕對地址時， 不僅要求程序員熟悉內存的使用情況，而且一旦程序或數據被不僅要求程序員熟悉內存的使用情況，而且一旦程序或數據被修改后，可能要改變程序中的所有地址。因此，通常是寧可在修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號地址，然后在編譯或匯編時，再將這些符號地程序中采用符號地址，然后在編譯或匯編時，再將這些符號地址轉換為絕對地址。址轉換為絕對地址。 由于程序中的邏輯地址

13、與實際內存地址完全相同，故不須對由于程序中的邏輯地址與實際內存地址完全相同，故不須對程序和數據地址進行修改。但這種情況很少，一般只適于程序和數據地址進行修改。但這種情況很少，一般只適于單道單道環境環境。操作系統原理操作系統原理 課程 第13張2. 可重定位裝入方式可重定位裝入方式4.2.1 程序的裝入程序的裝入 由裝入程序由裝入程序根據內存當時的實際使用情況根據內存當時的實際使用情況，將裝入模塊裝，將裝入模塊裝入到入到內存的適當地方內存的適當地方。由于編譯程序不能預知所編譯的目標。由于編譯程序不能預知所編譯的目標模塊在內存的什么位置，因此，會使裝入模塊中的所有模塊在內存的什么位置，因此，會使裝

14、入模塊中的所有邏輯邏輯地址與實際地址不同。地址與實際地址不同。 在裝入時，將根據實際裝入的起始位置，相應調整所有的相在裝入時，將根據實際裝入的起始位置，相應調整所有的相對地址。在裝入時對目標程序中的指令和數據地址的修改過程對地址。在裝入時對目標程序中的指令和數據地址的修改過程稱為稱為重定位重定位。又因為地址交換只是在裝入時一次完成，以后不。又因為地址交換只是在裝入時一次完成，以后不在改變，故稱為在改變，故稱為靜態重定位靜態重定位。 圖圖 4-2重定位方式重定位方式作業裝入內存時的情況作業裝入內存時的情況 LOAD 1,2500365LOAD 1,250036510000110001250015

15、0005000250010000作業地址空間內存空間操作系統原理操作系統原理 課程 第15張3. 動態運行時裝入方式動態運行時裝入方式 (Denamle Run-time Loading) 動態運行時的裝入程序，在把裝入模塊裝入內存后，并動態運行時的裝入程序，在把裝入模塊裝入內存后，并不立即把裝入模塊中的相對地址轉換為絕對地址，而是把這不立即把裝入模塊中的相對地址轉換為絕對地址，而是把這種地址轉換推遲到種地址轉換推遲到程序真正要執行時程序真正要執行時才進行。因此，才進行。因此， 裝入內裝入內存后的所有地址都仍是相對地址。存后的所有地址都仍是相對地址。 4.2.1 程序的裝入程序的裝入為使地址轉

16、換不影響指令的運行速度，需要為使地址轉換不影響指令的運行速度，需要重定位寄存器重定位寄存器支持。支持。操作系統原理操作系統原理 課程 第16張4.2.2 程序的鏈接程序的鏈接 1. 靜態鏈接方式靜態鏈接方式(Static Linking) 模塊 ACALL B；Return；0L1模塊 BCALL C；Return；0M1模塊 CReturn；0N10模塊 AJSR“L”Return；L1模塊 BJSR“LM”Return；LLM1LMLMN1模塊 CReturn；(a) 目標模塊(b) 裝入模塊操作系統原理操作系統原理 課程 第17張 在將這幾個目標模塊裝配成一個裝入模塊時，須解在將這幾個目

17、標模塊裝配成一個裝入模塊時，須解決以下兩個問題：決以下兩個問題： (1) 對相對地址進行修改對相對地址進行修改。 (2) 變換外部調用符號變換外部調用符號。 4.2.2 程序的鏈接程序的鏈接 操作系統原理操作系統原理 課程 第18張2. 裝入時動態鏈接裝入時動態鏈接(Loadtime Dynamic Linking) 裝入時動態鏈接方式有以下優點：裝入時動態鏈接方式有以下優點： （1） 便于修改和更新便于修改和更新。 （2）便于實現對目標模塊的共享便于實現對目標模塊的共享。 4.2.2 程序的鏈接程序的鏈接 在裝入目標模塊時，若在裝入目標模塊時，若發現一個外部模塊調用事件發現一個外部模塊調用事

18、件，由裝入程序找出相應的模塊。由裝入程序找出相應的模塊。 操作系統原理操作系統原理 課程 第19張 近幾年流行起來的運行時動態鏈接方式，是對上述在近幾年流行起來的運行時動態鏈接方式，是對上述在裝入時鏈接方式的一種改進。這種鏈接方式是將裝入時鏈接方式的一種改進。這種鏈接方式是將對某些模對某些模塊的鏈接推遲到執行時才執行塊的鏈接推遲到執行時才執行，亦即，在執行過程中，當，亦即，在執行過程中，當發現一個被調用模塊尚未裝入內存時，立即由發現一個被調用模塊尚未裝入內存時，立即由OS去找到該去找到該模塊并將之裝入內存，模塊并將之裝入內存， 把它鏈接到調用者模塊上。凡在執把它鏈接到調用者模塊上。凡在執行過程

19、中未被用到的目標模塊，都不會被調入內存和被鏈行過程中未被用到的目標模塊，都不會被調入內存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節省大量的內存空間。可節省大量的內存空間。 4.2.2 程序的鏈接程序的鏈接 操作系統原理操作系統原理 課程 第20張1.地址映射地址映射將程序地址空間中使用的將程序地址空間中使用的邏輯地址邏輯地址變換成變換成主存中的地址主存中的地址的過程的過程稱為稱為地址映射地址映射。有時也稱為。有時也稱為地址重定位地址重定位 。補補：存儲管理的功能存儲管理的功能 2.主存分配與回收主存分配與回收按照一定的算法把某

20、一空閑的主存區分配給作業或進程。按照一定的算法把某一空閑的主存區分配給作業或進程。在多道程序設計的環境中，內存分配的功能包括：在多道程序設計的環境中，內存分配的功能包括：制定分配策略制定分配策略、構造分配用的數據結構構造分配用的數據結構、響應系統的內存分配響應系統的內存分配的請求的請求和和回收系統釋放的內存區回收系統釋放的內存區。操作系統原理操作系統原理 課程 第21張內存管理策略內存管理策略有三種有三種:1）放置策略放置策略 決定內存中放置信息的區域（或位置），即如何在若干個決定內存中放置信息的區域（或位置），即如何在若干個空閑區中選擇一個或幾個空閑區的原則；空閑區中選擇一個或幾個空閑區的原

21、則；2）調入策略調入策略 決定信息裝入內存的時機，有兩種：在用戶請求時調入，稱決定信息裝入內存的時機，有兩種：在用戶請求時調入，稱為為請調請調；根據某種算法，確定系統將要使用的信息，并在執行；根據某種算法，確定系統將要使用的信息，并在執行前預先調入內存，稱為前預先調入內存，稱為預調預調 ；3）淘汰策略淘汰策略 當內存不足時，決定將某些信息調出內存的策略當內存不足時，決定將某些信息調出內存的策略 。操作系統原理操作系統原理 課程 第22張3.存儲保護與共享存儲保護與共享保證用戶程序保證用戶程序(或進程映象或進程映象)在各自存儲區域內操作，互不干擾。在各自存儲區域內操作，互不干擾。補：補：存儲管理

22、的功能存儲管理的功能 常用的存儲保護有兩種常用的存儲保護有兩種:上下界保護上下界保護下界寄存器下界寄存器: 存放程序裝入內存后的開始地址（首址）存放程序裝入內存后的開始地址（首址）上界寄存器上界寄存器: 存放程序裝入內存后的末地址存放程序裝入內存后的末地址判別式：判別式： 下界寄存器下界寄存器 物理地址物理地址 上界寄存器上界寄存器基址、限長寄存器保護基址、限長寄存器保護基址寄存器基址寄存器: 存放程序裝入內存后的開始地址（首址）存放程序裝入內存后的開始地址（首址）限長寄存器限長寄存器: 存放限制訪問的最大相對長度存放限制訪問的最大相對長度判別式：判別式：基址寄存器基址寄存器 物理地址物理地址

23、 基址寄存器基址寄存器+限長寄存器限長寄存器操作系統原理操作系統原理 課程 第23張1）常規存儲器管理方式的特征常規存儲器管理方式的特征 一次性。一次性。 (2) 駐留性。駐留性。 4.提供虛擬存儲技術提供虛擬存儲技術補：補：存儲管理的功能存儲管理的功能 早在早在1968年，年， Denning.P就曾指出：就曾指出： (1) 程序執行時，程序執行時， 除了少部分的轉移和過程調用指令外，除了少部分的轉移和過程調用指令外， 在大多數情況在大多數情況下仍是順序執行的。下仍是順序執行的。 (2) 過程調用將會使程序的執行軌跡由一部分區域轉至另一部分區域，過程調用將會使程序的執行軌跡由一部分區域轉至另

24、一部分區域， 但經研究看出，過程調用的深度在大多數情況下都不超過但經研究看出，過程調用的深度在大多數情況下都不超過5。 (3) 程序中存在許多循環結構，程序中存在許多循環結構， 這些雖然只由少數指令構成，這些雖然只由少數指令構成， 但是它們但是它們將多次執行。將多次執行。 (4) 程序中還包括許多對數據結構的處理，程序中還包括許多對數據結構的處理， 如對數組進行操作，如對數組進行操作， 它們往它們往往都局限于很小的范圍內。往都局限于很小的范圍內。 2）局部性原理局部性原理 操作系統原理操作系統原理 課程 第24張 (1) 時間局限性時間局限性。如果程序中的某條指令一旦執行，。如果程序中的某條指

25、令一旦執行， 則不久以則不久以后該指令可能再次執行；如果某數據被訪問過，后該指令可能再次執行；如果某數據被訪問過， 則不久以后該則不久以后該數據可能再次被訪問。產生時間局限性的典型原因，是由于在數據可能再次被訪問。產生時間局限性的典型原因，是由于在程序中存在著大量的循環操作。程序中存在著大量的循環操作。 (2) 空間局限性空間局限性。一旦程序訪問了某個存儲單元，在不久之后，。一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也將被訪問，即程序在一段時間內所訪問的其附近的存儲單元也將被訪問，即程序在一段時間內所訪問的地址，可能集中在一定的范圍之內，其典型情況便是程序的順地址，可能集中在一定

26、的范圍之內，其典型情況便是程序的順序執行。序執行。 局限性又表現在下述兩個方面：局限性又表現在下述兩個方面：操作系統原理操作系統原理 課程 第25張 使用戶程序的大小和結構使用戶程序的大小和結構不受主存容量和結構的限制不受主存容量和結構的限制，即使在，即使在用戶程序比實際主存容量還要大的情況下，程序也能正確運行。用戶程序比實際主存容量還要大的情況下，程序也能正確運行。問題的提出問題的提出物理存儲器物理存儲器的結構是個的結構是個一維一維的線性空間，容量是的線性空間，容量是有限有限的。的。用戶程序用戶程序結構：結構：一維空間一維空間： 一個用戶程序就是一個程序，并且程序和數據是不分離的；一個用戶程

27、序就是一個程序，并且程序和數據是不分離的；二維空間二維空間： 程序由主程序和若干個子程序（或函數）組成，并且程序程序由主程序和若干個子程序（或函數）組成，并且程序 與數據是分離的；與數據是分離的； n n維空間維空間： 即一個大型程序，由一個主模塊和多個子模塊組成，其中，即一個大型程序，由一個主模塊和多個子模塊組成，其中，各各 子模塊又由主程序和子程序（或函數）組成。子模塊又由主程序和子程序（或函數）組成。 用戶程序的大小，可能比內存容量小，也可能比內存容量大，有時候要大用戶程序的大小，可能比內存容量小，也可能比內存容量大，有時候要大得多。得多。 虛擬存儲技術虛擬存儲技術操作系統原理操作系統原

28、理 課程 第26張 虛擬存儲概念虛擬存儲概念 為用戶提供一種不受物理存儲器結構和容量限制的存儲器的技術為用戶提供一種不受物理存儲器結構和容量限制的存儲器的技術稱為虛擬存儲技術。稱為虛擬存儲技術。 所謂所謂虛擬存儲器虛擬存儲器，是指具有，是指具有請求調入請求調入功能和功能和置換置換功能，能從邏輯功能，能從邏輯上對內存容量加以擴充的一種存儲器系統，其邏輯容量由內、外存上對內存容量加以擴充的一種存儲器系統，其邏輯容量由內、外存容量之和來決定，其運行速度接近內存，成本接近外存。容量之和來決定，其運行速度接近內存，成本接近外存。 虛擬存儲器的特征：虛擬存儲器的特征： 多次性多次性對換性對換性虛擬性虛擬性

29、 0. 離散分配離散分配 虛擬存儲技術虛擬存儲技術操作系統原理操作系統原理 課程 第27張回顧：回顧：4.3 連續分配方式連續分配方式1.存儲管理的基本功能：存儲管理的基本功能：內存分配與回收內存分配與回收地址映射地址映射內存保護與共享內存保護與共享虛擬存儲虛擬存儲（內存擴充內存擴充）2.程序的虛擬地址空間（程序的虛擬地址空間（邏輯地址邏輯地址） 內存的物理地址空間（內存的物理地址空間（物理地址物理地址）操作系統原理操作系統原理 課程 第28張4.3 連續分配方式連續分配方式4.3.1 單一連續分配單一連續分配 分區存儲管理分區存儲管理 OS系統區系統區占用區占用區空閑區空閑區 用用 戶戶 區

30、區 低址低址高址高址用于用于單用戶單用戶、單任務單任務的的OSOS中中 操作系統原理操作系統原理 課程 第29張4.3.2 固定分區分配固定分區分配 2. 劃分分區的方法劃分分區的方法： 分區大小分區大小相等相等 4.3 連續分配方式連續分配方式1.原理原理：OS區用用戶戶區區OS區用用戶戶區區(2) 分區大小分區大小不等不等分區分區1分區分區2分區分區3分區分區4分區分區2分區分區1分區分區3分區分區4操作系統原理操作系統原理 課程 第30張3.3.涉及的數據結構涉及的數據結構分區說明表分區說明表（內存分配表）（內存分配表） 4.3.2 固定分區分配固定分區分配 4.3 連續分配方式連續分配

31、方式操作系統原理操作系統原理 課程 第31張3.3.內存分配內存分配4.3.2 固定分區分配固定分區分配 4.3 連續分配方式連續分配方式 由由內存分配程序內存分配程序對對分區說明表分區說明表進行檢索，如果有一個空閑區符進行檢索，如果有一個空閑區符合用戶要求的大小合用戶要求的大小, 則分配給進程。即則分配給進程。即將將寫入寫入PCB，并，并置該分區的狀態為已分置該分區的狀態為已分“1”。4.4.內存回收內存回收 將對應分區的狀態設為空將對應分區的狀態設為空閑，即閑，即“0”。操作系統原理操作系統原理 課程 第32張5.5.地址轉換地址轉換4.3.2 固定分區分配固定分區分配 4.3 連續分配方

32、式連續分配方式 系統采用系統采用“技術，將作業裝入所分配的分區中，技術，將作業裝入所分配的分區中，且在執行過程中不會被改變存放區域，由裝入程序按如下計算得且在執行過程中不會被改變存放區域，由裝入程序按如下計算得出物理地址。出物理地址。操作系統原理操作系統原理 課程 第33張6.6.存儲保護存儲保護4.3.2 固定分區分配固定分區分配 4.3 連續分配方式連續分配方式常采用常采用“基址、限長寄存器保護法基址、限長寄存器保護法”操作系統原理操作系統原理 課程 第34張4.3.3 動態分區分配動態分區分配 4.3 連續分配方式連續分配方式1）內存空間劃分內存空間劃分： 將內存空間除將內存空間除OS區

33、外，區外，。當一個作。當一個作業裝入時，根據作業的需求和內存空間的使用情況來決定是否分業裝入時，根據作業的需求和內存空間的使用情況來決定是否分配。（若有足夠的空間，則按需要配。（若有足夠的空間，則按需要一部分分區給該進程；否一部分分區給該進程；否則令其等待主存空間）則令其等待主存空間）分區，分區，。1.原理原理：2）虛擬空間劃分：虛擬空間劃分：空間空間 3）分配原則：分配原則： 尋找一個滿足大小的空閑區，按程序大小分割后，程序尋找一個滿足大小的空閑區，按程序大小分割后，程序，。操作系統原理操作系統原理 課程 第35張4.3.3 動態分區分配動態分區分配 2. 分配中的數據結構分配中的數據結構

34、(1) 空閑分區表空閑分區表前向指針N20N個字節可用后向指針N20區號區號長度長度始址始址(2) 空閑分區鏈空閑分區鏈 (3) 資源請求表資源請求表 進程號進程號請求內存長度請求內存長度P113kP220k分區號分區號 分區大小分區大小 后繼指針后繼指針分區號分區號 分區大小分區大小 后繼指針后繼指針操作系統原理操作系統原理 課程 第36張3. 內存分配適應（配）算法內存分配適應（配）算法4.3.3 動態分區分配動態分區分配 適適應應法法適適應應法法適適應應法法適適應應法法適適應應法法操作系統原理操作系統原理 課程 第37張3. 內存分配適應（配）算法內存分配適應（配）算法(1) 首次適應算

35、法首次適應算法FF最先適配法最先適配法 4.3.3 動態分區分配動態分區分配 (2) 最佳適應算法最佳適應算法BF 當接到內存申請時，查空閑塊表，找到當接到內存申請時，查空閑塊表，找到起始地址最小起始地址最小的不小于請求的的不小于請求的空塊，將其分割并分配。該算法要求空閑塊空塊，將其分割并分配。該算法要求空閑塊按起始地址按起始地址遞增遞增排序排序。 評價評價：簡單，傾向于優先利用內存簡單，傾向于優先利用內存低址低址部分的空閑區，后期查找低速。部分的空閑區，后期查找低速。 當接到內存申請時，在空閑塊表中找到一個不小于請求的當接到內存申請時，在空閑塊表中找到一個不小于請求的最小空閑塊最小空閑塊進進

36、行行 分配。該算法要求空閑塊分配。該算法要求空閑塊按長度遞增排序按長度遞增排序。評價評價：用最小空間滿足要求用最小空間滿足要求 ，避免，避免“大材小用大材小用”，但會存在切割后無法，但會存在切割后無法再利用的再利用的“碎片碎片”。操作系統原理操作系統原理 課程 第38張3. 內存分配適應（配）算法內存分配適應（配）算法(3) 最差適應算法最差適應算法WF4.3.3 動態分區分配動態分區分配 (4) 循環首次適應算法循環首次適應算法NF 當接到內存申請時，在空閑塊表中找到一個不小于請求的當接到內存申請時，在空閑塊表中找到一個不小于請求的最大空閑塊最大空閑塊進進行分配。該算法要求空閑塊行分配。該算

37、法要求空閑塊按長度按長度遞減遞減排序排序。評價評價：當分割后空閑塊仍為較大空塊，可再次利用；但同時會造成無大當分割后空閑塊仍為較大空塊，可再次利用；但同時會造成無大 的空閑區情況。的空閑區情況。 首次適應法的改進，區別在于搜索時不是每次都從鏈首開始，而是從上首次適應法的改進，區別在于搜索時不是每次都從鏈首開始，而是從上次找到的下一個空閑區開始查找。需設置一個尋查指針，用以指示下一次次找到的下一個空閑區開始查找。需設置一個尋查指針，用以指示下一次查詢的分區。查詢的分區。(5) 快速適應算法快速適應算法QF 將空閑分區按容量大小分類，相同容量空閑分區單獨成一個鏈表，并設將空閑分區按容量大小分類，相

38、同容量空閑分區單獨成一個鏈表，并設立管理索引表，索引表每一項對應一類鏈表，并記錄每類空閑鏈的指針。立管理索引表，索引表每一項對應一類鏈表，并記錄每類空閑鏈的指針。操作系統原理操作系統原理 課程 第39張3.內存分配分配過程內存分配分配過程 從頭開始查表檢索完否？m.size u.size?m.size u.sizesize?從該分區中劃出u.size大小的分區將該分區分配給請求者修改有關數據結構返回返回繼續檢索下一個表項將該分區從鏈中移出YNNYYN操作系統原理操作系統原理 課程 第40張F1回收區4.內存的回收內存的回收4.3.3 動態分區分配動態分區分配 視情況進行釋放區與其前、后空閑空間

39、的視情況進行釋放區與其前、后空閑空間的合并合并 a) 回收區回收區F的前一個區的前一個區F1也為空閑區。也為空閑區。F1回收區FF1b) 回收區回收區F的后一個區的后一個區F2也為空閑區。也為空閑區。F2回收區FF2回收區FF2“二合一二合一”不必新增空閑區表項，只修改不必新增空閑區表項，只修改F1即可。即可。 F1的大小為的大小為F1和和F之和之和 其余分量不變其余分量不變“二合一二合一”不必新增空閑區表項，只修改不必新增空閑區表項，只修改F2即可。即可。將將F的首地址作為新空閑區的首地址的首地址作為新空閑區的首地址新區的大小為新區的大小為F2和和F之和之和 其余分量不變其余分量不變操作系統

40、原理操作系統原理 課程 第41張4.內存的回收內存的回收4.3.3 動態分區分配動態分區分配 c) 回收區回收區F的前后兩個區的前后兩個區F1、F2都為空閑區。都為空閑區。b) 回收區回收區F的前后兩個區都不是空閑區。的前后兩個區都不是空閑區。回收區FF1回收區FF2F1回收區FF2F1回收區FF“三合一三合一”使用使用F1的表項，刪除的表項，刪除F2的表項。的表項。F1的大小為的大小為F1、F和和F2之和之和F1后繼指針改為后繼指針改為F2的后繼指針的后繼指針新增空閑區表項，新增空閑區表項，填寫空閑區首地址和大小，填寫空閑區首地址和大小，并插入到空閑鏈的適當位置并插入到空閑鏈的適當位置1.1

41、.空閑區個數變化？空閑區個數變化？2.2.碎片問題？碎片問題？操作系統原理操作系統原理 課程 第42張 通過在內存移動程序，將所有小的空閑區域合并為大的空通過在內存移動程序，將所有小的空閑區域合并為大的空閑區域。（緊縮技術，緊致技術，浮動技術，搬家技術）閑區域。（緊縮技術，緊致技術，浮動技術，搬家技術） 碎片問題的解決碎片問題的解決緊湊技術緊湊技術碎片問題：碎片問題： 經過一段時間的分配回收后，內存中存在很多很小的空閑經過一段時間的分配回收后，內存中存在很多很小的空閑塊。它們每一個都很小，不足以滿足分配要求；但其總和滿足塊。它們每一個都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊

42、被稱為分配要求。這些空閑塊被稱為碎片碎片（內內、外外）。）。 問題問題：開銷大；移動時機：開銷大；移動時機有關碎片有關碎片操作系統原理操作系統原理 課程 第43張4.3.6 可重定位分區分配可重定位分區分配 1. 動態重定位的引入動態重定位的引入 用戶程序用戶程序1用戶程序用戶程序6用戶程序用戶程序310KB30KB14KB用戶程序用戶程序926KBa)緊湊前緊湊前用戶程序用戶程序1用戶程序用戶程序6用戶程序用戶程序3用戶程序用戶程序980KBb)緊湊后緊湊后操作系統原理操作系統原理 課程 第44張2. 動態重定位的實現動態重定位的實現 “設置一個設置一個重定位寄存器重定位寄存器，存放內存的初

43、始地址，存放內存的初始地址 ” LOAD1,25003650100250050002500相對地址10000重定位寄存器LOAD1,250036510000101001250015000作業J處理機一側 存儲器一側主存4.3.6 可重定位分區分配可重定位分區分配 操作系統原理操作系統原理 課程 第45張3. 動態重定位分區分配算法動態重定位分區分配算法 請求分配u.size分區檢索空閑分區鏈(表)找到大于u.size的可用區否?按動態分區方式進行分配修改有關的數據結構返回分區號及首批空閑分區總和u.size?進行緊湊形成連續空閑區修改有關的數據結構否是無法分配返回否4.3.6 可重定位分區分配

44、可重定位分區分配 操作系統原理操作系統原理 課程 第46張4.3.7 覆蓋與對換技術覆蓋與對換技術1. 覆蓋技術覆蓋技術 它是基于這樣一種思想提出來的，即一個程序并不需要一開它是基于這樣一種思想提出來的，即一個程序并不需要一開始就把它的全部指令和數據都裝入內存后再執行。始就把它的全部指令和數據都裝入內存后再執行。 覆蓋是指一個作業的若干程序段，或幾個作業的某些部分共覆蓋是指一個作業的若干程序段，或幾個作業的某些部分共享某一個存儲空間。享某一個存儲空間。把程序劃分為若干個功能上相對獨立的程把程序劃分為若干個功能上相對獨立的程序段，按照其自身的邏輯結構將那些不會同時執行的程序段共序段，按照其自身的

45、邏輯結構將那些不會同時執行的程序段共享同一塊內存區域。享同一塊內存區域。操作系統原理操作系統原理 課程 第47張4.3.7 覆蓋與對換技術覆蓋與對換技術1. 覆蓋技術覆蓋技術 程序段先保存在磁盤上，當有關程序段的先頭部分執行結束，程序段先保存在磁盤上，當有關程序段的先頭部分執行結束，把后續程序段調入內存，覆蓋前面的程序段（內存把后續程序段調入內存，覆蓋前面的程序段（內存“擴大擴大”了）。了）。 一般要求作業各模塊之間有明確的調用結構，程序員要向系一般要求作業各模塊之間有明確的調用結構，程序員要向系統指明覆蓋結構，然后由由操作系統完成自動覆蓋。統指明覆蓋結構，然后由由操作系統完成自動覆蓋。 缺點

46、缺點：對用戶不透明，增加了用戶負擔。：對用戶不透明，增加了用戶負擔。操作系統原理操作系統原理 課程 第48張4.3.7 覆蓋與對換技術覆蓋與對換技術2. 對換對換 所謂所謂“對換對換”， 是指把是指把不能運行的進程或者不能運行的進程或者暫時不用的程序和數據，暫時不用的程序和數據，上，以便騰出足夠的內上，以便騰出足夠的內存空間，再把已具備運行條件的進程或進程所需要的程序和存空間，再把已具備運行條件的進程或進程所需要的程序和數據，數據，。對換是提高內存利用率的有效措施。對換是提高內存利用率的有效措施。 操作系統原理操作系統原理 課程 第49張 二者之比較二者之比較 與覆蓋技術相比，交換技術不要求用

47、戶給出程序段之間與覆蓋技術相比，交換技術不要求用戶給出程序段之間的邏輯覆蓋結構。而且，交換發生在進程或作業之間，而的邏輯覆蓋結構。而且，交換發生在進程或作業之間，而覆蓋發生在同一進程或作業內。此外，覆蓋只能覆蓋那些覆蓋發生在同一進程或作業內。此外，覆蓋只能覆蓋那些與覆蓋段無關的程序段。與覆蓋段無關的程序段。4.3.7 覆蓋與對換技術覆蓋與對換技術操作系統原理操作系統原理 課程 第50張4.7 請求分頁存儲管理請求分頁存儲管理 虛擬頁式管理虛擬頁式管理引入引入： 1. 常規存儲器管理方式常規存儲器管理方式(實模式實模式)的特征的特征 一次性。一次性。 (2) 駐留性。駐留性。 (1) 間局限性間

48、局限性(2) 間局限性間局限性2.局部性原理局部性原理操作系統原理操作系統原理 課程 第51張3. 虛擬存儲器虛擬存儲器 是指具有是指具有請求調入請求調入功能和功能和置換置換功能，功能， 能能從邏輯上對內存容量加以從邏輯上對內存容量加以擴充擴充的一種存儲器系統。其邏輯容量由的一種存儲器系統。其邏輯容量由內存容量和外存容量之和內存容量和外存容量之和所決所決定，其運行定，其運行速度接近于內存速度接近于內存速度，而每位的速度，而每位的成本卻又接近于外存成本卻又接近于外存。引入引入： 4.7 請求分頁存儲管理請求分頁存儲管理4. 實現頁式虛擬存儲的硬件支持實現頁式虛擬存儲的硬件支持 請求分頁的頁表機制

49、請求分頁的頁表機制：它是在純分頁的頁表機制上：它是在純分頁的頁表機制上而形成而形成的，作為請求分頁的數據結構。的，作為請求分頁的數據結構。 缺頁中斷機構缺頁中斷機構：即每當用戶程序要訪問的頁面尚未調入內存時便產生：即每當用戶程序要訪問的頁面尚未調入內存時便產生一缺頁中斷，以請求一缺頁中斷，以請求OS將所缺的頁調入內存。將所缺的頁調入內存。 地址變換機構地址變換機構： 它同樣是在純分頁地址變換機構的基礎上發展形成它同樣是在純分頁地址變換機構的基礎上發展形成的的操作系統原理操作系統原理 課程 第52張4.7.1 基本工作原理基本工作原理 在進程開始運行之前，在進程開始運行之前，不是裝入全部頁面不是

50、裝入全部頁面，而是裝入一個，而是裝入一個或零個頁面，之后或零個頁面，之后根據根據進程運行的進程運行的需要需要，動態裝入動態裝入其它其它頁面頁面；當內存空間已滿，而又需要裝入新的頁面時，則根據某種算法當內存空間已滿，而又需要裝入新的頁面時，則根據某種算法淘汰淘汰某個頁面，以便裝入新的頁面。某個頁面，以便裝入新的頁面。 根據頁面調入的時機，又分為根據頁面調入的時機，又分為請請求求調入調入頁式管理和頁式管理和預調入預調入頁頁式管理。式管理。4.7 請求分頁存儲管理請求分頁存儲管理操作系統原理操作系統原理 課程 第53張4.7.2 請求分頁存儲的硬件機制請求分頁存儲的硬件機制4.7 請求分頁存儲管理請

51、求分頁存儲管理狀態位狀態位P：（：（駐留位駐留位、中斷位中斷位）表示該頁是在內存還是在外存）表示該頁是在內存還是在外存訪問位訪問位A：記錄本頁在一段時間內被訪問的次數，以便根據訪問：記錄本頁在一段時間內被訪問的次數，以便根據訪問 位來決定淘汰哪頁（由不同的算法決定）位來決定淘汰哪頁（由不同的算法決定）修改位修改位M：查看此頁是否在內存中被修改過：查看此頁是否在內存中被修改過外存地址外存地址：用于指出該頁在外存中的地址，供調入時參考：用于指出該頁在外存中的地址，供調入時參考 1.頁表機制擴充頁表頁表機制擴充頁表操作系統原理操作系統原理 課程 第54張2.缺頁中斷機構缺頁中斷機構 在地址映射過程中

52、，在頁表中發現所要訪問的頁在地址映射過程中，在頁表中發現所要訪問的頁不在內存不在內存，則則產生缺頁中斷產生缺頁中斷。操作系統接到此中斷信號后，就調出。操作系統接到此中斷信號后，就調出缺頁中缺頁中斷處理程序斷處理程序，根據頁表中給出的外存地址，將該頁，根據頁表中給出的外存地址，將該頁調入內存調入內存，使作業繼續運行下去。使作業繼續運行下去。 如果內存中如果內存中有空閑塊有空閑塊，則分配一頁，將新調入頁，則分配一頁，將新調入頁裝入裝入內存，內存，并修改頁表中相應頁表項目的駐留位及相應的內存塊號。并修改頁表中相應頁表項目的駐留位及相應的內存塊號。 若此時內存中若此時內存中沒有空閑塊沒有空閑塊，則要，

53、則要淘汰某頁淘汰某頁，若該頁在內存，若該頁在內存期間被修改過，則要將其寫回外存期間被修改過，則要將其寫回外存 。4.7 請求分頁存儲管理請求分頁存儲管理4.7.2 請求分頁存儲的硬件機制請求分頁存儲的硬件機制操作系統原理操作系統原理 課程 第55張涉涉及及6次次缺缺頁頁中中斷斷的的指指令令 頁面B：A：654321指令copy ATO B操作系統原理操作系統原理 課程 第56張3.地地址址變變換換機機構構 缺頁中斷處理保留CPU現場從外存中找到缺頁內存滿否？選擇一頁換出該頁被修改否？將該頁寫回外存OS命令CPU從外存讀缺頁啟動I/O硬件將一頁從外存換入內存修改頁表否是是否頁表項在快表中？CPU

54、檢索快表訪問頁表否頁在內存？修改訪問位和修改位形成物理地址地址變換結束否頁號頁表長度?開始程序請求訪問一頁產生缺頁中斷請求調頁修改快表是越界中斷是是請求分頁中的地址變換過程請求分頁中的地址變換過程 操作系統原理操作系統原理 課程 第57張4.7.3 內存分配策略和分配算法內存分配策略和分配算法 1. 最小物理塊數的確定最小物理塊數的確定 是指能是指能保證進程正常運行所需的最小物理塊數保證進程正常運行所需的最小物理塊數。當系統為。當系統為進程分配的物理塊數少于此值時，進程將無法運行。進程分配的物理塊數少于此值時，進程將無法運行。 進程應獲得的最少物理塊數與計算機的硬件結構有關，取決進程應獲得的最

55、少物理塊數與計算機的硬件結構有關，取決于指令的格式、于指令的格式、 功能和尋址方式。功能和尋址方式。4.7 請求分頁存儲管理請求分頁存儲管理操作系統原理操作系統原理 課程 第58張2. 物理塊的分配策略物理塊的分配策略 在請求分頁系統中，可采取兩種內存分配策略，即固定和可在請求分頁系統中，可采取兩種內存分配策略，即固定和可變分配策略。在進行置換時，變分配策略。在進行置換時， 也可采取兩種策略，即全局置換也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。和局部置換。于是可組合出以下三種適用的策略。 1) 固定固定分配分配局部局部置換置換(Fixed Allocation,

56、Local Replacement) 2) 可變可變分配分配全局全局置換置換(Variable Allocation, Global Replacement) 3) 可變可變分配分配局部局部置換置換(Variable Allocation, Local Replacemen 4.7.3 內存分配策略和分配算法內存分配策略和分配算法 操作系統原理操作系統原理 課程 第59張3. 物理塊分配算法物理塊分配算法 1) 平均分配算法平均分配算法:這種方式貌似公平，但實際上是不公平的，因這種方式貌似公平，但實際上是不公平的，因為它未考慮到各進程本身的大小。為它未考慮到各進程本身的大小。4.7.3 內存分

57、配策略和分配算法內存分配策略和分配算法 2)按比例分配算法按比例分配算法:根據進程的大小按比例分配物理塊。如果根據進程的大小按比例分配物理塊。如果系統中共有系統中共有n個進程，每個進程的頁面數為個進程，每個進程的頁面數為Si，則系統中各進程頁，則系統中各進程頁面數的總和為：面數的總和為：又假定系統中可用的物理塊總數為又假定系統中可用的物理塊總數為m，則每個進程所能分到的物，則每個進程所能分到的物理塊數為理塊數為bi，將有：，將有：bi應該取整，它必須大于最小物理塊數。應該取整，它必須大于最小物理塊數。niiSS1mSSbii操作系統原理操作系統原理 課程 第60張 3) 考慮優先權的分配算法考

58、慮優先權的分配算法 在實際應用中，為了照顧到重要的、緊迫的作業能盡快地完在實際應用中，為了照顧到重要的、緊迫的作業能盡快地完成，成， 應為它分配較多的內存空間。應為它分配較多的內存空間。通常采取的方法是把內存中通常采取的方法是把內存中可供分配的所有物理塊分成兩部分：可供分配的所有物理塊分成兩部分：一部分按比例一部分按比例地分配給各地分配給各進程；進程；另一部分則根據各進程的優先權另一部分則根據各進程的優先權，適當地增加其相應份，適當地增加其相應份額后，分配給各進程。額后，分配給各進程。 在有的系統中，如重要的實時控制系統，則可能是完全按優在有的系統中，如重要的實時控制系統，則可能是完全按優先權

59、來為各進程分配其物理塊的。先權來為各進程分配其物理塊的。 3. 物理塊分配算法物理塊分配算法 4.7.3 內存分配策略和分配算法內存分配策略和分配算法 操作系統原理操作系統原理 課程 第61張4.7.4 調頁策略調頁策略 1. 何時調入頁面何時調入頁面 預調預調頁策略頁策略 2) 請請求求調調頁策略頁策略 4.7 請求分頁存儲管理請求分頁存儲管理2. 從何處調入頁面從何處調入頁面 在請求分頁系統中的外存分為兩部分：用于存放文件的在請求分頁系統中的外存分為兩部分：用于存放文件的文件區文件區和用于存放對換頁面的和用于存放對換頁面的對換區對換區。通常，由于對換區是。通常，由于對換區是采用連續分配方式

60、，而事件是采用離散分配方式，故對換區采用連續分配方式，而事件是采用離散分配方式，故對換區的磁盤的磁盤I/O速度比文件區的高。速度比文件區的高。操作系統原理操作系統原理 課程 第62張 每當程序所要訪問的頁面未在內存時，便向每當程序所要訪問的頁面未在內存時，便向CPUCPU發出一缺頁中斷，發出一缺頁中斷，中斷處理程序首先保留中斷處理程序首先保留CPUCPU環境，分析中斷原因后，環境，分析中斷原因后， 轉入缺頁中斷轉入缺頁中斷處理程序。該程序通過查找頁表，得到該頁在外存的物理塊后，處理程序。該程序通過查找頁表，得到該頁在外存的物理塊后， 如果此時內存能容納新頁，則啟動磁盤如果此時內存能容納新頁，則