操作系統(tǒng)課件第四版第四章

1、 4.1 4.1 存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu) 4.2 4.2 程序的裝入和鏈接程序的裝入和鏈接 4.3 4.3 連續(xù)分配存儲管理方式連續(xù)分配存儲管理方式 4.4 4.4 對換對換4.5 4.5 分頁存儲管理方式分頁存儲管理方式 4.6 4.6 分段存儲管理方式分段存儲管理方式 n微機中的存儲層次組織：微機中的存儲層次組織：n訪問速度越慢，容量越大，價格越便宜；訪問速度越慢，容量越大，價格越便宜；n最佳狀態(tài)應(yīng)是最佳狀態(tài)應(yīng)是各層次的存儲器各層次的存儲器都處于都處于均衡的繁忙狀均衡的繁忙狀態(tài)態(tài)（如：緩存命中率正好使主存讀寫保持繁忙）。（如：緩存命中率正好使主存讀寫保持繁忙）。外存(second

2、ary storage)DOS核心命令處理程序內(nèi)存(primary storage)快速緩存(cache)寄存器(register)n快速緩存：快速緩存：Data CacheData Cachen內(nèi)存：內(nèi)存：DRAM, SDRAMDRAM, SDRAM等等n外存：軟盤、硬盤、光盤、磁帶等外存：軟盤、硬盤、光盤、磁帶等4.1 4.1 存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu) 操作系統(tǒng)課程主要介紹以下兩類存儲器的管理：操作系統(tǒng)課程主要介紹以下兩類存儲器的管理：內(nèi)存儲器內(nèi)存儲器（簡稱內(nèi)存、（簡稱內(nèi)存、主存、物理存儲器）主存、物理存儲器）n處理機能直接訪問的處理機能直接訪問的存儲器。用來存放系存儲器。用來存放

3、系統(tǒng)和用戶的程序和數(shù)統(tǒng)和用戶的程序和數(shù)據(jù)，其特點是存取速據(jù)，其特點是存取速度快，存儲方式是以度快，存儲方式是以新?lián)Q舊，斷電信息丟新?lián)Q舊，斷電信息丟失。失。外存儲器外存儲器（簡稱外存、（簡稱外存、輔助存儲器）輔助存儲器）n處理機不能直接訪問處理機不能直接訪問的存儲器。用來存放的存儲器。用來存放用戶的各種信息，存用戶的各種信息，存取速度相對內(nèi)存而言取速度相對內(nèi)存而言要慢得多，但它可用要慢得多，但它可用來長期保存用戶信息。來長期保存用戶信息。將在設(shè)備管理一章中將在設(shè)備管理一章中介紹。介紹。* 存儲器管理目的和存儲器管理目的和功能：功能：1.1.主存儲器的分配與回收主存儲器的分配與回收 為每一道程序分

4、配內(nèi)存空間，使它們?yōu)槊恳坏莱绦蚍峙鋬?nèi)存空間，使它們“各得其所各得其所”；在；在用戶作業(yè)不再需要它時，及時回收，以供其它用戶使用。用戶作業(yè)不再需要它時，及時回收，以供其它用戶使用。2.2.提高主存儲器的利用率提高主存儲器的利用率 允許允許多道程序多道程序動態(tài)共享主存，并共享內(nèi)存中某個區(qū)域的動態(tài)共享主存，并共享內(nèi)存中某個區(qū)域的信息。信息。3.3.存儲保護存儲保護 確保每道程序都在自己的內(nèi)存空間運行，互不干擾。確保每道程序都在自己的內(nèi)存空間運行，互不干擾。4.4.內(nèi)存擴充內(nèi)存擴充 從邏輯上來擴充內(nèi)存容量，使用戶認(rèn)為系統(tǒng)所擁有的內(nèi)從邏輯上來擴充內(nèi)存容量，使用戶認(rèn)為系統(tǒng)所擁有的內(nèi)存空間遠(yuǎn)比其實際的內(nèi)存空

5、間（硬件存空間遠(yuǎn)比其實際的內(nèi)存空間（硬件RAMRAM）大的多。）大的多。5.5.地址映射地址映射 將程序地址空間中使用的邏輯地址變換成主存中的地址將程序地址空間中使用的邏輯地址變換成主存中的地址的過程。的過程。4.2 4.2 程序的裝入和鏈接程序的裝入和鏈接 將一個用戶源程序變?yōu)橐粋€可在內(nèi)存中執(zhí)行將一個用戶源程序變?yōu)橐粋€可在內(nèi)存中執(zhí)行的程序（進程），需要以下準(zhǔn)備工作：的程序（進程），需要以下準(zhǔn)備工作：編輯編輯 編譯編譯 鏈接鏈接 裝入裝入 源文件源文件 目標(biāo)模塊目標(biāo)模塊 可執(zhí)行文件可執(zhí)行文件 進程進程在這個過程中，原程序的地址將產(chǎn)生變化：在這個過程中，原程序的地址將產(chǎn)生變化： （1）編輯編輯：

6、使用符號地址使用符號地址 （2）編譯編譯：模塊內(nèi)符號地址模塊內(nèi)符號地址解析解析 （3）鏈接鏈接：模塊間符號地址模塊間符號地址解析解析 （4）裝入裝入：使用物理地址使用物理地址符號地址：符號地址：在源程序中，是通過符號名來訪問子程序和在源程序中，是通過符號名來訪問子程序和數(shù)據(jù)的，把程序中符號名的集合稱為數(shù)據(jù)的，把程序中符號名的集合稱為“名字空間名字空間”。邏輯地址邏輯地址（相對地址，虛地址）：源程序經(jīng)過匯編或編（相對地址，虛地址）：源程序經(jīng)過匯編或編譯后，形成目標(biāo)程序，每個目標(biāo)程序都是以譯后，形成目標(biāo)程序，每個目標(biāo)程序都是以0為基址順為基址順序進行編址的，原來用序進行編址的，原來用符號名符號名訪

7、問的單元用具體的數(shù)訪問的單元用具體的數(shù)據(jù)據(jù) 單元號取代。把邏輯地址的集合稱為單元號取代。把邏輯地址的集合稱為“邏輯地邏輯地址空間址空間”或簡稱為或簡稱為“地址空間地址空間”。物理地址物理地址（絕對地址，實地址）：把內(nèi)存分成若干個大（絕對地址，實地址）：把內(nèi)存分成若干個大小相等的存儲單元，每個單元給一個編號，這個編號稱小相等的存儲單元，每個單元給一個編號，這個編號稱為物理地址。物理地址可直接尋址。存儲單元占為物理地址。物理地址可直接尋址。存儲單元占8位，位，稱作字節(jié)（稱作字節(jié)（byte）。）。當(dāng)程序裝入內(nèi)存時當(dāng)程序裝入內(nèi)存時, 操作系統(tǒng)要為該程序分配一操作系統(tǒng)要為該程序分配一個合適的內(nèi)存空間，由

8、于個合適的內(nèi)存空間，由于程序的邏輯地址與分配到內(nèi)程序的邏輯地址與分配到內(nèi)存物理地址不一致存物理地址不一致, 而而CPU執(zhí)行指令時，是按物理地執(zhí)行指令時，是按物理地址進行的，所以要進行地址轉(zhuǎn)換。址進行的，所以要進行地址轉(zhuǎn)換。地址重定位地址重定位：將用戶程序中的邏輯地址轉(zhuǎn)換為運行時：將用戶程序中的邏輯地址轉(zhuǎn)換為運行時由機器直接尋址的物理地址。這個過程也稱為由機器直接尋址的物理地址。這個過程也稱為地址映地址映射射（map）。）。 地址空間的程序和數(shù)據(jù)經(jīng)過地址重定位處理后，地址空間的程序和數(shù)據(jù)經(jīng)過地址重定位處理后，就變成了可由就變成了可由CPU直接執(zhí)行的物理地址程序。把這一直接執(zhí)行的物理地址程序。把這

9、一地址集合稱為地址集合稱為“物理地址空間物理地址空間”或或“存儲空間存儲空間”。 程序的名字空間、地址空間和存儲空間程序的名字空間、地址空間和存儲空間之間的關(guān)系如圖所示：之間的關(guān)系如圖所示： 匯編匯編/編譯編譯 地址重定位地址重定位 鏈鏈 接接 裝裝 入入 名字空間名字空間 地址空間地址空間 存儲空間存儲空間 （相對地址（相對地址/ （絕對地址（絕對地址/ 邏輯地址空間）邏輯地址空間） 物理地址空間）物理地址空間） 符符 號號源源 程程 序序相對目標(biāo)相對目標(biāo)程序程序（裝配模塊）（裝配模塊）絕對目標(biāo)絕對目標(biāo)程序程序如果事先知道程序?qū)Ⅰv留在內(nèi)存的什么位置，在編如果事先知道程序?qū)Ⅰv留在內(nèi)存的什么位置

10、，在編譯時，編譯程序?qū)a(chǎn)生物理地址?；蛴沙绦騿T直接按物譯時，編譯程序?qū)a(chǎn)生物理地址?；蛴沙绦騿T直接按物理地址編程，但這種程序在系統(tǒng)中是不能做任何移動的，理地址編程，但這種程序在系統(tǒng)中是不能做任何移動的，否則就會出錯。否則就會出錯。即在程序的即在程序的編輯或編譯時期編輯或編譯時期確定確定地址映射地址映射關(guān)系，裝關(guān)系，裝入時直接定位在上述入時直接定位在上述(即文件中記錄的地址即文件中記錄的地址)物理地址。物理地址。n優(yōu)點：裝入過程簡單。優(yōu)點：裝入過程簡單。n缺點：過于依賴于硬件結(jié)構(gòu)，不適于多道程序系統(tǒng)。缺點：過于依賴于硬件結(jié)構(gòu)，不適于多道程序系統(tǒng)。一、程序的裝入一、程序的裝入1. 1. 絕對裝入方

11、式絕對裝入方式2.2.可重定位裝入方式（也稱為靜態(tài)重定位或靜可重定位裝入方式（也稱為靜態(tài)重定位或靜態(tài)地址映射）態(tài)地址映射） 是在程序執(zhí)行之前進行重定位。它根據(jù)裝配模是在程序執(zhí)行之前進行重定位。它根據(jù)裝配模塊將要裝入的內(nèi)存起始地址，直接修改裝配模塊中塊將要裝入的內(nèi)存起始地址，直接修改裝配模塊中的有關(guān)使用地址的指令。即當(dāng)用戶的有關(guān)使用地址的指令。即當(dāng)用戶程序被裝入內(nèi)存程序被裝入內(nèi)存時時，一次性，一次性實現(xiàn)實現(xiàn)邏輯地址到物理邏輯地址到物理地址的轉(zhuǎn)換地址的轉(zhuǎn)換，以后，以后不再轉(zhuǎn)換（一般在裝入內(nèi)存時由軟件完成）。不再轉(zhuǎn)換（一般在裝入內(nèi)存時由軟件完成）。 例如在例如在圖中以圖中以“0”作為參考地址的裝配模

12、塊，作為參考地址的裝配模塊，要裝入以要裝入以10000為起始地址的存儲空間。顯然在裝入為起始地址的存儲空間。顯然在裝入程序之前，程序必須做一些修改才能正確運行。程序之前，程序必須做一些修改才能正確運行。 0 0： 1000010000： 100： LOAD 1，2500 10100： LOAD 1，12500 2500： 365 12500： 365 2600： 12600： 程序的地址空間程序的地址空間 內(nèi)存的地址空間內(nèi)存的地址空間靜態(tài)重定位雖然有無須硬件支持的優(yōu)點，但是也靜態(tài)重定位雖然有無須硬件支持的優(yōu)點，但是也存在明顯的存在明顯的缺點缺點：一一是程序重定位以后就不能在內(nèi)存是程序重定位以后

13、就不能在內(nèi)存中移動；中移動；二二是要求程序的存儲空間是連續(xù)的，不能把是要求程序的存儲空間是連續(xù)的，不能把程序存儲到若干個不連續(xù)的區(qū)域中。程序存儲到若干個不連續(xù)的區(qū)域中。3.3.動態(tài)運行時裝入方式（也稱為動態(tài)重定位或動動態(tài)運行時裝入方式（也稱為動態(tài)重定位或動態(tài)地址映射）態(tài)地址映射）是指在是指在程序執(zhí)行過程程序執(zhí)行過程中進行中進行地址重定位地址重定位，即在每，即在每次訪問內(nèi)存單元前才進行地址變換。動態(tài)重定位可使次訪問內(nèi)存單元前才進行地址變換。動態(tài)重定位可使裝配模塊不加任何修改就裝入內(nèi)存，裝配模塊不加任何修改就裝入內(nèi)存，但是它需要硬但是它需要硬件件 重定位寄存器的支持。重定位寄存器的支持。n優(yōu)點：優(yōu)

14、點：nOS可以移動程序，有利用實現(xiàn)共享?？梢砸苿映绦颍欣脤崿F(xiàn)共享。n能夠支持程序執(zhí)行中產(chǎn)生的地址引用，如指針變量（而能夠支持程序執(zhí)行中產(chǎn)生的地址引用，如指針變量（而不僅是生成可執(zhí)行文件時的地址引用）。不僅是生成可執(zhí)行文件時的地址引用）。n缺點：缺點： 需要硬件支持，需要硬件支持，OS實現(xiàn)較復(fù)雜。實現(xiàn)較復(fù)雜。n它是虛擬存儲的基礎(chǔ)。它是虛擬存儲的基礎(chǔ)。 0 0： 1000010000： 100： LOAD 1，2500 10100： LOAD 1，2500 2500： 365 12500： 365 2600： 12600： 程序的地址空間程序的地址空間 內(nèi)存的地址空間內(nèi)存的地址空間10000重

15、定位寄存器重定位寄存器動態(tài)重定位的示意圖動態(tài)重定位的示意圖二、程序的鏈接二、程序的鏈接1.1.靜態(tài)鏈接方式靜態(tài)鏈接方式（1）對相對地址進行修改）對相對地址進行修改（2）變換外部調(diào)用符號）變換外部調(diào)用符號模塊ACALL B；Return模塊BCALL C；Return;模塊CReturn;模塊AJSR“L”Return;模塊BJSR“L+M”Return;模塊CReturn;LL+M-10L-1L+ML+M+N-10M-10L-10N-1目標(biāo)模塊目標(biāo)模塊裝入模塊裝入模塊2.2.裝入時動態(tài)鏈接裝入時動態(tài)鏈接 目標(biāo)模塊在裝入內(nèi)存時，邊裝入邊鏈接。目標(biāo)模塊在裝入內(nèi)存時，邊裝入邊鏈接。優(yōu)點優(yōu)點：（1）便

16、于修改和更新）便于修改和更新（2）便于實現(xiàn)對目標(biāo)模塊的共享）便于實現(xiàn)對目標(biāo)模塊的共享3.3.運行時動態(tài)鏈接運行時動態(tài)鏈接 對某些模塊的鏈接推遲到執(zhí)行時才進行。對某些模塊的鏈接推遲到執(zhí)行時才進行。優(yōu)點優(yōu)點： 既可加快程序的裝入過程，又可節(jié)省大量的內(nèi)存既可加快程序的裝入過程，又可節(jié)省大量的內(nèi)存空間?？臻g。4.3 4.3 連續(xù)分配存儲管理方式連續(xù)分配存儲管理方式一、單一連續(xù)分配一、單一連續(xù)分配 這是一種最簡單的存儲管理方式，但只能用于這是一種最簡單的存儲管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)，如在單用戶、單任務(wù)的操作系統(tǒng)，如在8位和位和16位微機上位微機上的的CP/M和和MS-DOS操作系統(tǒng)。

17、它將內(nèi)存分為兩個區(qū)：操作系統(tǒng)。它將內(nèi)存分為兩個區(qū)： 系統(tǒng)區(qū)系統(tǒng)區(qū)：僅供操作系統(tǒng)使用，通常設(shè)置在內(nèi)存的：僅供操作系統(tǒng)使用，通常設(shè)置在內(nèi)存的低段；低段； 用戶區(qū)用戶區(qū)：指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供：指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給用戶使用。給用戶使用。 采用這種管理方式時，處理器中設(shè)置一個采用這種管理方式時，處理器中設(shè)置一個界限界限寄存器寄存器，寄存器中的內(nèi)容為當(dāng)前可供用戶使用的主，寄存器中的內(nèi)容為當(dāng)前可供用戶使用的主存區(qū)域的起始地址。存區(qū)域的起始地址。作業(yè)作業(yè)2作業(yè)作業(yè)1.CPU界限寄存器界限寄存器a作業(yè)隊列作業(yè)隊列操作系統(tǒng)操作系統(tǒng)空閑區(qū)空閑區(qū)主存主存0abc用戶區(qū)用戶區(qū)注：注：(1)

18、不管空閑區(qū)有多大，都不用來裝另一個作業(yè)。不管空閑區(qū)有多大，都不用來裝另一個作業(yè)。 (2)通常采用覆蓋技術(shù)來運行比內(nèi)存空間大的作業(yè)。通常采用覆蓋技術(shù)來運行比內(nèi)存空間大的作業(yè)。二、固定分區(qū)分配二、固定分區(qū)分配 固定式分區(qū)固定式分區(qū)是在作業(yè)裝入之前，內(nèi)存就被劃分成是在作業(yè)裝入之前，內(nèi)存就被劃分成若干個分區(qū)。一旦劃分完成，在系統(tǒng)運行期間不再重若干個分區(qū)。一旦劃分完成，在系統(tǒng)運行期間不再重新劃分，即分區(qū)的個數(shù)不可變，分區(qū)的大小不可變，新劃分，即分區(qū)的個數(shù)不可變，分區(qū)的大小不可變，所以，固定式分區(qū)又稱為所以，固定式分區(qū)又稱為靜態(tài)分區(qū)靜態(tài)分區(qū)。(注：注：操作系統(tǒng)操作系統(tǒng)占用其中一個分區(qū)。）占用其中一個分區(qū)。

19、） 1.1.劃分分區(qū)的方法劃分分區(qū)的方法 （1）分區(qū)大小相等：）分區(qū)大小相等： 只適合于多個相同程序的并發(fā)執(zhí)行（處理多個類只適合于多個相同程序的并發(fā)執(zhí)行（處理多個類型相同的對象）。型相同的對象）。 （2）分區(qū)大小不等：）分區(qū)大小不等： 多個小分區(qū)、適量的中等分區(qū)、少量的大分區(qū)。多個小分區(qū)、適量的中等分區(qū)、少量的大分區(qū)。根據(jù)程序的大小，分配當(dāng)前空閑的、適當(dāng)大小的分區(qū)。根據(jù)程序的大小，分配當(dāng)前空閑的、適當(dāng)大小的分區(qū)。2.2.內(nèi)存分配內(nèi)存分配 將分區(qū)按大小進行排隊，并在系統(tǒng)中建立一張分區(qū)將分區(qū)按大小進行排隊，并在系統(tǒng)中建立一張分區(qū)說明表，每個表目說明一個分區(qū)的大小、起始地址和是說明表，每個表目說明一

20、個分區(qū)的大小、起始地址和是否已分配的使用標(biāo)志。分區(qū)說明表和內(nèi)存分配圖如下所否已分配的使用標(biāo)志。分區(qū)說明表和內(nèi)存分配圖如下所示。示。區(qū)號區(qū)號 大小大小 起址起址 標(biāo)志標(biāo)志 1 16KB 20K 已分配已分配 2 32KB 36K 已分配已分配 3 64KB 68K 已分配已分配 4 124KB 132K 未分配未分配 (a) 分區(qū)說明表分區(qū)說明表0k： 20k： 第第1分區(qū)（分區(qū)（16kb）36k： 第第2分區(qū)（分區(qū)（32kb） （已分配）（已分配） 68k： 第第3分區(qū)（分區(qū)（64kb） （已分配）（已分配）132k： 第第4分區(qū)分區(qū)(124kb) （未分配）（未分配） 256k： （b）內(nèi)存

21、分配圖）內(nèi)存分配圖操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)A（16k）作業(yè)作業(yè)B（26k）作業(yè)作業(yè)C（56k） n優(yōu)點：優(yōu)點：固定式分區(qū)實現(xiàn)技術(shù)簡單，適用于作業(yè)的大固定式分區(qū)實現(xiàn)技術(shù)簡單，適用于作業(yè)的大小和多少事先都比較清楚的系統(tǒng)。它用于小和多少事先都比較清楚的系統(tǒng)。它用于6060年代的年代的IBM-360IBM-360的的MFTMFT操作系統(tǒng)中。操作系統(tǒng)中。n缺點：缺點：內(nèi)存的利用率不高，內(nèi)存的利用率不高，“零頭零頭”空間不能充分空間不能充分利用。此管理方法已基本被淘汰了。利用。此管理方法已基本被淘汰了。三、動態(tài)分區(qū)分配三、動態(tài)分區(qū)分配 在分配時，首先找到一個足夠大的空閑分區(qū)，在分配時，首先找到一個足夠大的

22、空閑分區(qū)，即這個空閑區(qū)的大小比作業(yè)要求的要大，系統(tǒng)則將即這個空閑區(qū)的大小比作業(yè)要求的要大，系統(tǒng)則將這個空閑分區(qū)分成兩部分：一部分成為已分配的分這個空閑分區(qū)分成兩部分：一部分成為已分配的分區(qū)，剩余的部分仍作為空閑區(qū)。區(qū)，剩余的部分仍作為空閑區(qū)。1.1.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表空閑分區(qū)表 空閑分區(qū)表為每個尚未分配的分區(qū)設(shè)置一個表項，空閑分區(qū)表為每個尚未分配的分區(qū)設(shè)置一個表項，包括分區(qū)的包括分區(qū)的序號序號、大小大小、始址始址和和狀態(tài)狀態(tài)。 空閑分區(qū)鏈空閑分區(qū)鏈 為了實現(xiàn)對空閑分區(qū)的分配和鏈接，在每個分區(qū)為了實現(xiàn)對空閑分區(qū)的分配和鏈接，在每個分區(qū)的的起始部分起始部分，設(shè)置一些

23、用于控制分區(qū)分配的信息（如，設(shè)置一些用于控制分區(qū)分配的信息（如分區(qū)的大小和狀態(tài)位），以及用于鏈接其它分區(qū)的前分區(qū)的大小和狀態(tài)位），以及用于鏈接其它分區(qū)的前向指針；在向指針；在分區(qū)尾部分區(qū)尾部，設(shè)置了一個后向指針，為了檢，設(shè)置了一個后向指針，為了檢索方便也設(shè)置了控制分區(qū)分配的信息。然后，通過前、索方便也設(shè)置了控制分區(qū)分配的信息。然后，通過前、后向指針將所有的分區(qū)鏈接成一個后向指針將所有的分區(qū)鏈接成一個雙向鏈表雙向鏈表。 0k0k： 20k20k： 52k52k： 116k116k： 164k164k： 260k260k： 512k512k： （c c）內(nèi)存分配圖）內(nèi)存分配圖N N個字節(jié)個字節(jié)可可

24、 用用序號序號P P 大小大小起址起址狀態(tài)狀態(tài) 1 148k48k116k116k空閑空閑 2 2252k252k260k260k空閑空閑 3 3空表目空表目 4 4空表目空表目 5 5空表目空表目 （a a）空閑分區(qū)表）空閑分區(qū)表 操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)1 1（32k32k）作業(yè)作業(yè)2 2（64k64k）空閑區(qū)（空閑區(qū)（48k48k）作業(yè)作業(yè)4 4（96k96k）空閑區(qū)（空閑區(qū)（252k252k）（b b）空空閑閑鏈鏈結(jié)結(jié)構(gòu)構(gòu)前向前向指針指針N+20后向后向指針指針N+202.2.分區(qū)分配算法分區(qū)分配算法 由于內(nèi)存分配算法對系統(tǒng)性能有很大的影響，所由于內(nèi)存分配算法對系統(tǒng)性能有很大的影響，所

25、以人們進行了廣泛深入的研究，產(chǎn)生了許多動態(tài)分區(qū)以人們進行了廣泛深入的研究，產(chǎn)生了許多動態(tài)分區(qū)分配算法。分配算法。 下一節(jié)將詳細(xì)介紹。下一節(jié)將詳細(xì)介紹。3.3.分區(qū)分配操作分區(qū)分配操作1）分配內(nèi)存）分配內(nèi)存YNNNY申請分配一個申請分配一個u.size大小的分區(qū)大小的分區(qū)從頭開始查表從頭開始查表是否檢索完畢？是否檢索完畢？本次無法分配本次無法分配m.sizeu.size m.size-u.sizesize？從該分區(qū)中劃出從該分區(qū)中劃出u.size大小的分區(qū)大小的分區(qū)繼續(xù)檢索下一繼續(xù)檢索下一個表項個表項將該表目以上的所有將該表目以上的所有表目下移一格表目下移一格將該分區(qū)分配給申請者，將該分區(qū)分配給

26、申請者，修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)修改有關(guān)的數(shù)據(jù)結(jié)構(gòu) 返返 回回2）回收內(nèi)存）回收內(nèi)存 當(dāng)一個作業(yè)運行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)釋當(dāng)一個作業(yè)運行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)釋放區(qū)的首地址，從空閑區(qū)說明表中找到相應(yīng)的插入放區(qū)的首地址，從空閑區(qū)說明表中找到相應(yīng)的插入點，此時可能出現(xiàn)下列四種情況（如下圖點，此時可能出現(xiàn)下列四種情況（如下圖所示，其所示，其中中F1F1，F(xiàn)2F2表示回收區(qū)的前、后空閑區(qū)）表示回收區(qū)的前、后空閑區(qū)）：n 當(dāng)回收區(qū)既不與當(dāng)回收區(qū)既不與F1F1鄰接，又不與鄰接，又不與F2F2鄰接時（如鄰接時（如A A），應(yīng)為回收區(qū)單獨建立一項新表目，填寫回收區(qū)的起應(yīng)為回收區(qū)單獨建立一項新表目，填寫回收區(qū)的

27、起址和大小，并根據(jù)其起址，插入到空閑區(qū)說明表的址和大小，并根據(jù)其起址，插入到空閑區(qū)說明表的適當(dāng)位置。適當(dāng)位置。n 當(dāng)回收區(qū)只與插入點的前一個分區(qū)當(dāng)回收區(qū)只與插入點的前一個分區(qū)F1F1相鄰接時相鄰接時（如（如B B），應(yīng)將回收區(qū)與插入點的前一個分區(qū)合并，），應(yīng)將回收區(qū)與插入點的前一個分區(qū)合并，不再為回收區(qū)分配新的表目，而只需修改不再為回收區(qū)分配新的表目，而只需修改F1分區(qū)表分區(qū)表目的大小即可。目的大小即可。n當(dāng)回收區(qū)只與插入點的后一個分區(qū)當(dāng)回收區(qū)只與插入點的后一個分區(qū)F2F2相鄰接時相鄰接時（如（如C C），將把兩個空閑區(qū)合并，把回收區(qū)的起址作為），將把兩個空閑區(qū)合并，把回收區(qū)的起址作為新空閑區(qū)

28、的起址，大小為兩個分區(qū)之和。新空閑區(qū)的起址，大小為兩個分區(qū)之和。n當(dāng)回收區(qū)與插入點的前、后兩個分區(qū)（當(dāng)回收區(qū)與插入點的前、后兩個分區(qū)（F1F1和和F2F2）都相鄰接時（如都相鄰接時（如D D），合并三個分區(qū)，用），合并三個分區(qū)，用F1F1表目的起址表目的起址作為新空閑區(qū)的起址，修改其大小為三塊分區(qū)之和，作為新空閑區(qū)的起址，修改其大小為三塊分區(qū)之和，最后取消最后取消F2F2的表目。的表目。A A B B C C D D F1 回收區(qū)回收區(qū) F2 回收區(qū)回收區(qū) F2 回收區(qū)回收區(qū) F1 回收區(qū)回收區(qū)n首次適應(yīng)算法（首次適應(yīng)算法（First FitFirst Fit）：）： 從從空閑分區(qū)表空閑分區(qū)表

29、的第一個表目起查找該表的第一個表目起查找該表，把最，把最先能夠滿足要求的空閑區(qū)分配給作業(yè)，這種方法目先能夠滿足要求的空閑區(qū)分配給作業(yè)，這種方法目的在于減少查找時間。為適應(yīng)這種算法，空閑分區(qū)的在于減少查找時間。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要表（空閑區(qū)鏈）中的空閑分區(qū)要按按地址地址由低到高進由低到高進行排序行排序。 特點：特點：該算法的分配和釋放的時間性能較好，較大的該算法的分配和釋放的時間性能較好，較大的空閑分區(qū)可以被保留在內(nèi)存高端?？臻e分區(qū)可以被保留在內(nèi)存高端。 如果找出的自由區(qū)長度恰好等于申請的長度則如果找出的自由區(qū)長度恰好等于申請的長度則是最合適的了；如果比申請的長度

30、略大，則分割后是最合適的了；如果比申請的長度略大，則分割后剩下的自由區(qū)就很小，這種自由區(qū)不但不能被再度剩下的自由區(qū)就很小，這種自由區(qū)不但不能被再度使用，而且還白白占用自由區(qū)鏈表的一個結(jié)點。當(dāng)使用，而且還白白占用自由區(qū)鏈表的一個結(jié)點。當(dāng)小自由區(qū)結(jié)點過多時，本算法的性能急劇下降。小自由區(qū)結(jié)點過多時，本算法的性能急劇下降。 四、基于順序搜索的動態(tài)分區(qū)分配算法四、基于順序搜索的動態(tài)分區(qū)分配算法n循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法(Next Fit)： 該算法是首次適應(yīng)算法的變種。在分配內(nèi)存空該算法是首次適應(yīng)算法的變種。在分配內(nèi)存空間時，不再每次從表頭（鏈?zhǔn)祝╅_始查找，而是從間時，不再每次從表頭（鏈?zhǔn)祝╅_

31、始查找，而是從上次找到的空閑區(qū)的下一個空閑區(qū)開始查找，直到上次找到的空閑區(qū)的下一個空閑區(qū)開始查找，直到找到第一個能滿足要求的的空閑區(qū)為止，并從中劃找到第一個能滿足要求的的空閑區(qū)為止，并從中劃出一塊與請求大小相等的內(nèi)存空間分配給作業(yè)。出一塊與請求大小相等的內(nèi)存空間分配給作業(yè)。 特點：特點： 該算法能使內(nèi)存中的空閑區(qū)分布得比較均勻。該算法能使內(nèi)存中的空閑區(qū)分布得比較均勻。但較大的空閑分區(qū)不易保留。但較大的空閑分區(qū)不易保留。n最佳適應(yīng)算法（最佳適應(yīng)算法（Best Fit）：）： 它從全部空閑區(qū)中找出能滿足作業(yè)要求的、且它從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小

32、。大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要閑分區(qū)要按按大小大小從小到大進行排序從小到大進行排序，自表頭開始查自表頭開始查找到第一個滿足要求的自由分區(qū)分配。找到第一個滿足要求的自由分區(qū)分配。 若系統(tǒng)中有與申請區(qū)大小相等的空閑區(qū)，這種若系統(tǒng)中有與申請區(qū)大小相等的空閑區(qū)，這種算法肯定能將這種空閑區(qū)分配給申請者。（首次適算法肯定能將這種空閑區(qū)分配給申請者。（首次適應(yīng)算法則不一定）。應(yīng)算法則不一定）。 特點：特點：最大的缺點是分割后的空閑區(qū)將會很小，直最大的缺點是分割后的空閑區(qū)將會很小，直至無法使用，而造

33、成浪費。至無法使用，而造成浪費。n最壞適應(yīng)算法（最壞適應(yīng)算法（Worst FitWorst Fit）：）： 從所有未分配的分區(qū)中挑選從所有未分配的分區(qū)中挑選最大的最大的且且大于和等大于和等于于作業(yè)大小的分區(qū)分給要求的作業(yè)；空閑分區(qū)作業(yè)大小的分區(qū)分給要求的作業(yè)；空閑分區(qū)按大按大小由大到小排序小由大到小排序，每次查找從鏈頭開始。，每次查找從鏈頭開始。 特點：特點：由于過多的分割大的自由區(qū)，當(dāng)遇到較大空由于過多的分割大的自由區(qū)，當(dāng)遇到較大空間申請時，無法滿足其申請的可能性較大。本算法間申請時，無法滿足其申請的可能性較大。本算法對中、小作業(yè)比較有利。對中、小作業(yè)比較有利。起址起址 大小大小 狀態(tài)狀態(tài)

34、a a16k16k c c14k14k e e10k10k g g30k30k 空閑分區(qū)表空閑分區(qū)表 *操作系統(tǒng)操作系統(tǒng)16K空閑區(qū)空閑區(qū)14K空閑區(qū)空閑區(qū)10K空閑區(qū)空閑區(qū)30K空閑區(qū)空閑區(qū)abcdefg0Job1 Job1 要求要求 13K13KJob2Job2Job3Job3 作業(yè)隊列作業(yè)隊列首次適應(yīng)算法首次適應(yīng)算法起址起址 大小大小 狀態(tài)狀態(tài) e e10k10k c c14k 14k a a16k 16k g g30k30k 最優(yōu)適應(yīng)算法最優(yōu)適應(yīng)算法例：分配例：分配一個一個13KB分區(qū)分區(qū)起址起址 大小大小 狀態(tài)狀態(tài) g g30k 30k a a16k16k c c14k14k e e

35、10k10k 最壞適應(yīng)算法最壞適應(yīng)算法思考題：思考題：下表給出了某系統(tǒng)中的空閑分區(qū)表，系統(tǒng)采用可變式下表給出了某系統(tǒng)中的空閑分區(qū)表，系統(tǒng)采用可變式分區(qū)存儲管理策略?，F(xiàn)有以下作業(yè)序列：分區(qū)存儲管理策略。現(xiàn)有以下作業(yè)序列：96K、20K、200K，若用首次適應(yīng)算法和最佳適應(yīng)算法來處理這些，若用首次適應(yīng)算法和最佳適應(yīng)算法來處理這些作業(yè)序列，試問哪一種算法可以滿足該作業(yè)的請求，為作業(yè)序列，試問哪一種算法可以滿足該作業(yè)的請求，為什么？什么？分區(qū)號分區(qū)號大小大小 起始地址起始地址132K100K210K150K35K200K4218K220K596K530Kn快速適應(yīng)算法（快速適應(yīng)算法（Quick Fit

36、Quick Fit）：）： 是將空閑分區(qū)根據(jù)其容量大小分類，對于每一是將空閑分區(qū)根據(jù)其容量大小分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設(shè)立一個空類具有相同容量的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表，同時在內(nèi)存中設(shè)立一張管理索引表，閑分區(qū)鏈表，同時在內(nèi)存中設(shè)立一張管理索引表，該表的每一個表項對應(yīng)了一種空閑分區(qū)類型，并記該表的每一個表項對應(yīng)了一種空閑分區(qū)類型，并記錄了該類型空閑鏈表表頭的指針。錄了該類型空閑鏈表表頭的指針。n伙伴系統(tǒng)伙伴系統(tǒng) 性能優(yōu)于快速適應(yīng)算法性能優(yōu)于快速適應(yīng)算法n哈希算法哈希算法五、基于索引搜索的動態(tài)分區(qū)分配算法五、基于索引搜索的動態(tài)分區(qū)分配算法六、動態(tài)可重定位分區(qū)分

37、配六、動態(tài)可重定位分區(qū)分配1.1.緊湊緊湊可變式分區(qū)也有零頭問題。在系統(tǒng)不斷地分配可變式分區(qū)也有零頭問題。在系統(tǒng)不斷地分配和回收中，必定會出現(xiàn)一些不連續(xù)的小的空閑區(qū)，稱和回收中，必定會出現(xiàn)一些不連續(xù)的小的空閑區(qū)，稱為為外零頭外零頭。雖然可能所有零頭的總和超過某一個作業(yè)。雖然可能所有零頭的總和超過某一個作業(yè)的要求，但是由于不連續(xù)而無法分配。的要求，但是由于不連續(xù)而無法分配。操作系統(tǒng)用戶程序 1 用戶程序 3用戶程序 6用戶程序 910KB30KB14KB26KB 如圖所示，如圖所示，雖然當(dāng)前內(nèi)存中雖然當(dāng)前內(nèi)存中的空閑分區(qū)的總的空閑分區(qū)的總?cè)萘窟_(dá)到容量達(dá)到80KB80KB，卻無法裝入一個卻無法裝入

38、一個40KB40KB的作業(yè)。的作業(yè)。 解決零頭的方法是解決零頭的方法是拼接拼接（或稱（或稱緊湊緊湊），即向一個），即向一個方向（例如向低地址端）移動已分配的作業(yè)，使那些方向（例如向低地址端）移動已分配的作業(yè)，使那些零散的小空閑區(qū)在另一方向連成一片。零散的小空閑區(qū)在另一方向連成一片。 分區(qū)的拼接技術(shù)，一方面分區(qū)的拼接技術(shù)，一方面是要求能夠?qū)ψ鳂I(yè)進行重定位，是要求能夠?qū)ψ鳂I(yè)進行重定位，另一方面系統(tǒng)在拼接時要耗費另一方面系統(tǒng)在拼接時要耗費較多的時間。較多的時間。操作系統(tǒng)用戶程序 1用戶程序 3用戶程序 6用戶程序 98 0KB2.2.動態(tài)重定位動態(tài)重定位 允許作業(yè)在運行過程中在內(nèi)存中移動的技術(shù)必須獲

39、允許作業(yè)在運行過程中在內(nèi)存中移動的技術(shù)必須獲得硬件支持。只有具有得硬件支持。只有具有動態(tài)重定位硬件機構(gòu)動態(tài)重定位硬件機構(gòu)的計算機系的計算機系統(tǒng)，才有可能采取動態(tài)重定位可變分區(qū)多道管理技術(shù)，統(tǒng)，才有可能采取動態(tài)重定位可變分區(qū)多道管理技術(shù)，系統(tǒng)的硬件包括系統(tǒng)的硬件包括重定位寄存器和加法器重定位寄存器和加法器。* * 動態(tài)重定位地址轉(zhuǎn)換動態(tài)重定位地址轉(zhuǎn)換 程序的目標(biāo)模塊在裝入內(nèi)存時，與地址有關(guān)的指令程序的目標(biāo)模塊在裝入內(nèi)存時，與地址有關(guān)的指令都無須進行修改，如在圖都無須進行修改，如在圖中中LOAD 1，2500這條指令中這條指令中仍保持相對地址仍保持相對地址2 2500。當(dāng)該模塊被操作系統(tǒng)調(diào)度到處理

40、。當(dāng)該模塊被操作系統(tǒng)調(diào)度到處理機上執(zhí)行時，操作系統(tǒng)首先把該模塊裝入的實際起始地機上執(zhí)行時，操作系統(tǒng)首先把該模塊裝入的實際起始地址減去目標(biāo)模塊的相對基地址（圖址減去目標(biāo)模塊的相對基地址（圖中該模塊的基地址為中該模塊的基地址為0），然后將其差值裝入重定位寄存器。），然后將其差值裝入重定位寄存器。 當(dāng)當(dāng)CPU取一條訪問內(nèi)存的指令時，地址變換硬件邏取一條訪問內(nèi)存的指令時，地址變換硬件邏輯自動將指令中的相對地址與重定位寄存器中的值相加，輯自動將指令中的相對地址與重定位寄存器中的值相加，再根據(jù)和值作為內(nèi)存的絕對地址去訪問該單元的數(shù)據(jù)。再根據(jù)和值作為內(nèi)存的絕對地址去訪問該單元的數(shù)據(jù)。 重定位寄存器重定位寄存

41、器 10000 0： 10000： 100：LOAD 1，2500 10100： LOAD 1，2500 2500： 365 12500： 365 2600： 12600： 程序的地址空間程序的地址空間 內(nèi)存的地址空間內(nèi)存的地址空間 由此可見，動態(tài)重定位是在指令執(zhí)行過程中動態(tài)進由此可見，動態(tài)重定位是在指令執(zhí)行過程中動態(tài)進行，這樣可以帶來兩個行，這樣可以帶來兩個好處好處： 目標(biāo)程序裝入內(nèi)存時無需任何修改，所以裝入之后目標(biāo)程序裝入內(nèi)存時無需任何修改，所以裝入之后再移動也不會影響其正確運行，這便于存儲器用緊縮來再移動也不會影響其正確運行，這便于存儲器用緊縮來解決存儲器的碎片問題。解決存儲器的碎片問題

42、。 一個程序由若干個相對獨立的目標(biāo)模塊組成時，也一個程序由若干個相對獨立的目標(biāo)模塊組成時，也可將每個目標(biāo)模塊各裝入一個存儲區(qū)域，這些存儲區(qū)域可將每個目標(biāo)模塊各裝入一個存儲區(qū)域，這些存儲區(qū)域可以不相鄰接，只要各個模塊有自己對應(yīng)的重定位寄存可以不相鄰接，只要各個模塊有自己對應(yīng)的重定位寄存器就可以了。器就可以了。3.3.動態(tài)重定位分區(qū)分配算法動態(tài)重定位分區(qū)分配算法動態(tài)重定位分區(qū)管理中何時進行存儲器緊縮有二種動態(tài)重定位分區(qū)管理中何時進行存儲器緊縮有二種不同的解決辦法：不同的解決辦法：n在某個分區(qū)被釋放后立即進行緊縮，系統(tǒng)總是只有在某個分區(qū)被釋放后立即進行緊縮，系統(tǒng)總是只有一個連續(xù)的分區(qū)而無碎片，此法很

43、花費機時。一個連續(xù)的分區(qū)而無碎片，此法很花費機時。n當(dāng)當(dāng)“請求分配模塊請求分配模塊”找不到足夠大的自由分區(qū)分給找不到足夠大的自由分區(qū)分給用戶時再進行緊縮，這樣緊縮的次數(shù)比上種方法少用戶時再進行緊縮，這樣緊縮的次數(shù)比上種方法少得多，但管理復(fù)雜。采用此法的動態(tài)重定位分區(qū)分得多，但管理復(fù)雜。采用此法的動態(tài)重定位分區(qū)分配算法框圖如下：配算法框圖如下：動態(tài)重定位分區(qū)動態(tài)重定位分區(qū) 分配分配算法框圖算法框圖 N N Y Y 請求分配請求分配u.size分區(qū)分區(qū)檢索空閑分區(qū)鏈（表）檢索空閑分區(qū)鏈（表）無法分無法分配返回配返回空閑分區(qū)總空閑分區(qū)總和和u.size找到大于找到大于u.size的可用的可用區(qū)否？區(qū)

44、否？進行緊湊形成進行緊湊形成連續(xù)空閑區(qū)連續(xù)空閑區(qū) 修改有關(guān)的修改有關(guān)的 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 按動態(tài)分區(qū)方式按動態(tài)分區(qū)方式 進行分配進行分配 修改有關(guān)的修改有關(guān)的 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號及首址返回分區(qū)號及首址 交換技術(shù)交換技術(shù)最早用在麻省理工學(xué)院的兼容分時系最早用在麻省理工學(xué)院的兼容分時系統(tǒng)統(tǒng)CTSS中。中。一、多道程序環(huán)境下的對換技術(shù)一、多道程序環(huán)境下的對換技術(shù)1.1.對換的引入對換的引入 在多道程序環(huán)境下為了提高內(nèi)存和在多道程序環(huán)境下為了提高內(nèi)存和CPU的利用的利用率，增加系統(tǒng)吞吐量，系統(tǒng)中增設(shè)了對換，率，增加系統(tǒng)吞吐量，系統(tǒng)中增設(shè)了對換，把內(nèi)存中把內(nèi)存中暫不能運行的進程（或程序和數(shù)據(jù)）調(diào)

45、出到外存上，暫不能運行的進程（或程序和數(shù)據(jù)）調(diào)出到外存上，以騰出足夠的內(nèi)存空間，把已具備運行條件的進程或以騰出足夠的內(nèi)存空間，把已具備運行條件的進程或進程所需要的程序和數(shù)據(jù)換入內(nèi)存。進程所需要的程序和數(shù)據(jù)換入內(nèi)存。 UNIX系統(tǒng)早期已引入對換功能并一直保留至今，系統(tǒng)早期已引入對換功能并一直保留至今，系統(tǒng)中專門設(shè)置一個對換進程完成以上功能。系統(tǒng)中專門設(shè)置一個對換進程完成以上功能。4.4 4.4 對換對換2.2.對換的類型對換的類型（1）整體對換）整體對換 處理機中級調(diào)度實際上就是存儲器的對換功能。處理機中級調(diào)度實際上就是存儲器的對換功能。（2）頁面（分段）對換）頁面（分段）對換 如果對換是以進程

46、的一個如果對換是以進程的一個“頁面頁面”或或“分段分段”為為單位進行的，則稱為單位進行的，則稱為“部分對換部分對換”，目的是為了支持，目的是為了支持虛擬存儲系統(tǒng)。虛擬存儲系統(tǒng)。 為了實現(xiàn)進程對換，系統(tǒng)必須能實現(xiàn)對為了實現(xiàn)進程對換，系統(tǒng)必須能實現(xiàn)對對換空間對換空間的管理的管理，進程換入進程換入、換出換出等三項功能。等三項功能。二、對換空間的管理二、對換空間的管理1.1.對換空間管理的主要目標(biāo)對換空間管理的主要目標(biāo) 通常把磁盤空間分為文件區(qū)和對換區(qū)。通常把磁盤空間分為文件區(qū)和對換區(qū)。 文件區(qū)占用磁盤空間的大部分空間，用于存放各類文件區(qū)占用磁盤空間的大部分空間，用于存放各類文件，對文件區(qū)管理目標(biāo)是提

47、高文件存儲空間的利用率，文件，對文件區(qū)管理目標(biāo)是提高文件存儲空間的利用率，為此系統(tǒng)采用為此系統(tǒng)采用離散分配方式離散分配方式； 對換區(qū)只占用磁盤空間的小部分，用于存放從內(nèi)存對換區(qū)只占用磁盤空間的小部分，用于存放從內(nèi)存換出的進程，它的管理目標(biāo)是提高進程換入換出速度，換出的進程，它的管理目標(biāo)是提高進程換入換出速度，為此系統(tǒng)采用連續(xù)分配方式。為此系統(tǒng)采用連續(xù)分配方式。2.2.對換區(qū)空閑盤塊管理中的數(shù)據(jù)結(jié)構(gòu)對換區(qū)空閑盤塊管理中的數(shù)據(jù)結(jié)構(gòu) 與內(nèi)存在動態(tài)分區(qū)分配方式中所用數(shù)據(jù)結(jié)構(gòu)相似。與內(nèi)存在動態(tài)分區(qū)分配方式中所用數(shù)據(jù)結(jié)構(gòu)相似。3.3.對換空間的分配與回收對換空間的分配與回收 對換空間的分配與回收與動態(tài)分區(qū)

48、方式時的內(nèi)對換空間的分配與回收與動態(tài)分區(qū)方式時的內(nèi)存分配與回收方法雷同。存分配與回收方法雷同。三、進程的換出與換入三、進程的換出與換入1.1.進程的換出進程的換出 當(dāng)內(nèi)核發(fā)現(xiàn)內(nèi)存不足時調(diào)用對換進程，對換進當(dāng)內(nèi)核發(fā)現(xiàn)內(nèi)存不足時調(diào)用對換進程，對換進程檢查駐留在內(nèi)存的進程，選擇處于阻塞和睡眠狀程檢查駐留在內(nèi)存的進程，選擇處于阻塞和睡眠狀態(tài)的進程換出，如無，則選擇優(yōu)先級低的駐留內(nèi)存態(tài)的進程換出，如無，則選擇優(yōu)先級低的駐留內(nèi)存時間長的處于就緒狀態(tài)的進程換出。時間長的處于就緒狀態(tài)的進程換出。2.2.進程的換入進程的換入 對換進程將定時執(zhí)行換入操作，在對換區(qū)中選對換進程將定時執(zhí)行換入操作，在對換區(qū)中選擇換出

49、時間長的處于就緒態(tài)的進程調(diào)入。擇換出時間長的處于就緒態(tài)的進程調(diào)入。4.5 4.5 分頁存儲管理方式分頁存儲管理方式連續(xù)分配方式導(dǎo)致了內(nèi)存碎片問題，降低了內(nèi)存連續(xù)分配方式導(dǎo)致了內(nèi)存碎片問題，降低了內(nèi)存資源的利用率，而通過資源的利用率，而通過“緊湊緊湊”方法來拼接碎片，系方法來拼接碎片，系統(tǒng)付出開銷太大，所以提出采用統(tǒng)付出開銷太大，所以提出采用離散分配方式離散分配方式存儲進存儲進程。程。 如果離散分配的基本單位是頁，則稱為分頁存儲如果離散分配的基本單位是頁，則稱為分頁存儲管理方式。管理方式?；痉猪摯鎯芾矸绞交痉猪摯鎯芾矸绞? (或稱純分頁存儲管或稱純分頁存儲管理方式理方式) )，要求把每個

50、作業(yè)全部裝入內(nèi)存后方要運行。，要求把每個作業(yè)全部裝入內(nèi)存后方要運行。一、分頁存儲管理的基本方法一、分頁存儲管理的基本方法1 1頁面和物理塊頁面和物理塊（1 1）頁面）頁面 分頁存儲管理是將一個進程的地址空間劃分成若干分頁存儲管理是將一個進程的地址空間劃分成若干個大小相等的區(qū)域，稱為個大小相等的區(qū)域，稱為頁頁。相應(yīng)地，將內(nèi)存空間劃分。相應(yīng)地，將內(nèi)存空間劃分成與頁相同大小的若干個物理塊，稱為成與頁相同大小的若干個物理塊，稱為塊或頁框塊或頁框。在為。在為進程分配內(nèi)存時，將進程中若干頁分別裝入多個不相鄰進程分配內(nèi)存時，將進程中若干頁分別裝入多個不相鄰接的塊中。接的塊中。 （2 2）頁面大?。╉撁娲笮?

51、小小 內(nèi)碎片小內(nèi)碎片小, ,頁表過長；大頁表過長；大 頁表短，管理開頁表短，管理開銷小，與外存交換時效率高，但頁內(nèi)碎片增大。頁面大銷小，與外存交換時效率高，但頁內(nèi)碎片增大。頁面大小一般是小一般是2 2的冪，通常為的冪，通常為512B-8KB512B-8KB。2.2.地址結(jié)構(gòu)地址結(jié)構(gòu)一個進程的地址空間劃分成若干個大小相等的頁一個進程的地址空間劃分成若干個大小相等的頁后，各個頁面從后，各個頁面從0 0開始依次編號，稱作頁號，每個頁面開始依次編號，稱作頁號，每個頁面內(nèi)也從內(nèi)也從0 0開始編址，稱為頁內(nèi)地址。因此，分頁系統(tǒng)的開始編址，稱為頁內(nèi)地址。因此，分頁系統(tǒng)的地址結(jié)構(gòu)由兩部分組成：前一部分為頁號地

52、址結(jié)構(gòu)由兩部分組成：前一部分為頁號P P；后一部分；后一部分為位移量為位移量W W，即頁內(nèi)地址。，即頁內(nèi)地址。圖中的地址長度為圖中的地址長度為3232位，其中位，其中0 01111位為頁內(nèi)地址位為頁內(nèi)地址（每頁的大小為（每頁的大小為4K4K），），12123131位為頁號，所以允許地位為頁號，所以允許地址空間的大小最多為址空間的大小最多為1M1M個頁。個頁。 頁號頁號 P 位移量位移量W31 12 11 031 12 11 0 若給定一個邏輯地址空間中的地址為若給定一個邏輯地址空間中的地址為A，頁面的大，頁面的大小為小為L，則頁號，則頁號P和頁內(nèi)地址和頁內(nèi)地址d可由下式求得：可由下式求得：PI

53、NT ALdA MOD L 例如例如 L=1000B，設(shè)，設(shè) A=3456，則，則 P=3，d=456。 但每訪問一個主存單元都做一次除法運算以得到頁但每訪問一個主存單元都做一次除法運算以得到頁號號P和頁內(nèi)地址和頁內(nèi)地址 d，效率太低。可根據(jù)頁的大小是，效率太低。可根據(jù)頁的大小是2的幾的幾次冪，將邏輯地址從第幾位分成兩部分，高位部分所表次冪，將邏輯地址從第幾位分成兩部分，高位部分所表示的數(shù)即頁號示的數(shù)即頁號P，低位部分表示的數(shù)即為頁內(nèi)地址，低位部分表示的數(shù)即為頁內(nèi)地址d。 見下圖：見下圖： 3.3.頁表頁表 在將進程的每一頁離散地分配到內(nèi)存的多個物在將進程的每一頁離散地分配到內(nèi)存的多個物理塊中

54、后，系統(tǒng)應(yīng)能保證能在內(nèi)存中找到每個頁面理塊中后，系統(tǒng)應(yīng)能保證能在內(nèi)存中找到每個頁面所對應(yīng)的物理塊。為此，系統(tǒng)為每個進程建立了一所對應(yīng)的物理塊。為此，系統(tǒng)為每個進程建立了一張張頁面映射表頁面映射表，簡稱，簡稱頁表頁表（如下圖（如下圖所示所示）。）。每個頁每個頁在頁表中占一個表項在頁表中占一個表項，記錄該頁在內(nèi)存中對應(yīng)的物，記錄該頁在內(nèi)存中對應(yīng)的物理塊號。進程在執(zhí)行時，通過查找頁表，就可以找理塊號。進程在執(zhí)行時，通過查找頁表，就可以找到每頁所對應(yīng)的物理塊號?？梢?，到每頁所對應(yīng)的物理塊號。可見，頁表的作用頁表的作用是實是實現(xiàn)從頁號到物理塊號（即邏輯地址到物理地址）的現(xiàn)從頁號到物理塊號（即邏輯地址到物

55、理地址）的地址映射。地址映射。頁表一般駐留在內(nèi)存中。頁表一般駐留在內(nèi)存中。頁表的作用頁表的作用.01234560123456作業(yè)的作業(yè)的地址空間地址空間頁框頁框（物理塊）（物理塊）頁號頁號頁表頁表主存中頁框主存中頁框（物理塊）（物理塊）.分頁系統(tǒng)還常在頁表中增加一個存取控制字段，分頁系統(tǒng)還常在頁表中增加一個存取控制字段，表示該頁的存取控制權(quán)限。表示該頁的存取控制權(quán)限。存取控制信息包括：存取控制信息包括： 禁止做任何操作禁止做任何操作 只能執(zhí)行只能執(zhí)行 只能讀只能讀 能讀能讀/寫寫當(dāng)有一程序要訪問某頁時，先判斷該頁的存取控當(dāng)有一程序要訪問某頁時，先判斷該頁的存取控制和存儲保護信息是否允許。制和存

56、儲保護信息是否允許。添加了存取控制信息的頁表表目如下圖所示：添加了存取控制信息的頁表表目如下圖所示： 頁號頁號存取控制存取控制信息信息塊號塊號二、地址變換機構(gòu)二、地址變換機構(gòu)1.1.基本的地址變換機構(gòu)基本的地址變換機構(gòu)地址變換機構(gòu)的基本任務(wù)地址變換機構(gòu)的基本任務(wù)是把用戶程序中的邏輯是把用戶程序中的邏輯地址變換成內(nèi)存中的物理地址。由于頁內(nèi)地址和塊內(nèi)地址變換成內(nèi)存中的物理地址。由于頁內(nèi)地址和塊內(nèi)地址是一一對應(yīng)的，所以地址變換實際上就是利用頁地址是一一對應(yīng)的，所以地址變換實際上就是利用頁表將用戶程序中的頁號變換成內(nèi)存中的物理塊號。表將用戶程序中的頁號變換成內(nèi)存中的物理塊號。 每個進程都有一張頁表，頁

57、表所在內(nèi)存的起始地每個進程都有一張頁表，頁表所在內(nèi)存的起始地址和長度存放在該進程的址和長度存放在該進程的PCB中。為了實現(xiàn)地址變換中。為了實現(xiàn)地址變換功能，在系統(tǒng)中設(shè)置功能，在系統(tǒng)中設(shè)置頁表寄存器頁表寄存器，當(dāng)某進程被調(diào)度時，當(dāng)某進程被調(diào)度時，才將其頁表始址和長度裝入頁表寄存器。才將其頁表始址和長度裝入頁表寄存器。 在單處理機環(huán)境下，也只需要一個頁表寄存器即在單處理機環(huán)境下，也只需要一個頁表寄存器即可?？?。 在進行地址變換時，系統(tǒng)將頁號與頁表長度進行在進行地址變換時，系統(tǒng)將頁號與頁表長度進行比較，如果頁號大于頁表寄存器中的頁表長度，則比較，如果頁號大于頁表寄存器中的頁表長度，則訪訪問越界問越界

58、，產(chǎn)生，產(chǎn)生越界中斷越界中斷。如未出現(xiàn)越界，則根據(jù)頁表。如未出現(xiàn)越界，則根據(jù)頁表寄存器中的頁表始址和頁號計算出寄存器中的頁表始址和頁號計算出該頁在頁表項中的該頁在頁表項中的位置位置，得到該頁的物理塊號，將此物理塊號裝入物理，得到該頁的物理塊號，將此物理塊號裝入物理地址寄存器中。與此同時，將有效地址（邏輯地址）地址寄存器中。與此同時，將有效地址（邏輯地址）寄存器中頁內(nèi)地址直接裝入物理地址寄存器的塊內(nèi)地寄存器中頁內(nèi)地址直接裝入物理地址寄存器的塊內(nèi)地址字段中，這樣便完成了從邏輯地址到物理地址的變址字段中，這樣便完成了從邏輯地址到物理地址的變換。換。地址變換過程地址變換過程 越界中斷越界中斷 頁表寄存

59、器頁表寄存器 邏輯地址邏輯地址2500 頁號頁號 塊塊 號號 0 1 2 頁式地址變換舉例頁式地址變換舉例塊號塊號5 塊內(nèi)地址塊內(nèi)地址452 頁號頁號2 頁內(nèi)地址頁內(nèi)地址452頁表始址頁表始址 頁表長度頁表長度 2 45例題：例題： 借助頁表，將給出的邏輯地址轉(zhuǎn)換成物理地址借助頁表，將給出的邏輯地址轉(zhuǎn)換成物理地址1. 1. 虛地址（邏輯地址、程序地址）以十六進制、八虛地址（邏輯地址、程序地址）以十六進制、八進制、二進制的形式給出進制、二進制的形式給出n將虛地址轉(zhuǎn)換成二進制的數(shù)；將虛地址轉(zhuǎn)換成二進制的數(shù)；n按頁的大小分離出頁號和位移量按頁的大小分離出頁號和位移量（低位部分是位移（低位部分是位移量

60、，高位部分是頁號）；量，高位部分是頁號）；n將位移量直接復(fù)制到內(nèi)存地址寄存器的低位部分；將位移量直接復(fù)制到內(nèi)存地址寄存器的低位部分；n以頁號查頁表，得到對應(yīng)頁裝入內(nèi)存的塊號以頁號查頁表，得到對應(yīng)頁裝入內(nèi)存的塊號，并將，并將塊號轉(zhuǎn)換成二進制數(shù)填入地址寄存器的高位部分，塊號轉(zhuǎn)換成二進制數(shù)填入地址寄存器的高位部分，從而形成內(nèi)存地址。從而形成內(nèi)存地址。例例1 1：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB8KB，頁大小為頁大小為2KB2KB，依次裝入內(nèi)存的第，依次裝入內(nèi)存的第7 7、9 9、A A、5 5塊，試塊，試將虛地址將虛地址0AFEH0AFEH，1