操作系統(tǒng)原理課件

1、第二章 存 儲 管 理 1第二章第二章 存儲管理存儲管理 2.1 2.1 存儲管理基礎(chǔ)存儲管理基礎(chǔ) 2.2 2.2 基本存儲管理方法基本存儲管理方法 2.3 2.3 可變分區(qū)存儲管理方法可變分區(qū)存儲管理方法 2.4 2.4 內(nèi)存擴充技術(shù)內(nèi)存擴充技術(shù) 2.5 2.5 純分頁的存儲管理純分頁的存儲管理 2.6 2.6 請求分頁系統(tǒng)請求分頁系統(tǒng) 2.7 2.7 段式存儲管理段式存儲管理 2.8 2.8 段頁式存儲管理段頁式存儲管理 2.9 Linux2.9 Linux存儲管理存儲管理第二章 存 儲 管 理 2存儲器可分為：內(nèi)存儲器和外存儲器；存儲器可分為：內(nèi)存儲器和外存儲器；內(nèi)存儲器：可以被內(nèi)存儲器

2、：可以被CPU直接訪問。直接訪問。外存儲器：不可以被外存儲器：不可以被CPU直接訪問，外存與直接訪問，外存與CPU之之間只能夠在輸入輸出控制系統(tǒng)的管理下，進行信息間只能夠在輸入輸出控制系統(tǒng)的管理下，進行信息交換。交換。第二章 存 儲 管 理 32.1 2.1 存儲管理基礎(chǔ)存儲管理基礎(chǔ) 庫鏈接程序裝入模塊裝入程序編譯程序產(chǎn)生的目標模塊第一步第二步第三步內(nèi)存2.1.1 2.1.1 虛擬地址與物理地址虛擬地址與物理地址第二章 存 儲 管 理 4內(nèi)存儲器是由一個個存儲單元組成，一個存儲單元可存放內(nèi)存儲器是由一個個存儲單元組成，一個存儲單元可存放若干個二進制的位（若干個二進制的位（bit），），8個二進

3、制位被稱為一個字節(jié)個二進制位被稱為一個字節(jié)（Byte）。）。內(nèi)存中的存儲單元按一定順序進行編號，每個單元所對應(yīng)內(nèi)存中的存儲單元按一定順序進行編號，每個單元所對應(yīng)的編號，稱為該單元的單元地址。的編號，稱為該單元的單元地址。物理地址物理地址（絕對地址，實地址）：內(nèi)存中存儲單元的地址。（絕對地址，實地址）：內(nèi)存中存儲單元的地址。物理地址可直接尋址。物理地址可直接尋址。邏輯地址邏輯地址（相對地址，虛地址）：用戶的程序經(jīng)過匯編或（相對地址，虛地址）：用戶的程序經(jīng)過匯編或編譯后形成目標代碼，目標代碼通常采用相對地址的形式。編譯后形成目標代碼，目標代碼通常采用相對地址的形式。其首地址為其首地址為0 0，其余

4、指令中的地址都相對于首地址來編，其余指令中的地址都相對于首地址來編址。址。不能用邏輯地址在內(nèi)存中讀取信息。不能用邏輯地址在內(nèi)存中讀取信息。第二章 存 儲 管 理 5第二章 存 儲 管 理 6地址重定位地址重定位 地址重定位（地址映射）地址重定位（地址映射）：將用戶程序中的邏輯地址：將用戶程序中的邏輯地址轉(zhuǎn)換為運行時由機器直接尋址的物理地址。轉(zhuǎn)換為運行時由機器直接尋址的物理地址。 當程序裝入內(nèi)存時當程序裝入內(nèi)存時, , 操作系統(tǒng)要為該程序分配一個合操作系統(tǒng)要為該程序分配一個合適的內(nèi)存空間，由于適的內(nèi)存空間，由于程序的邏輯地址與分配到內(nèi)存物程序的邏輯地址與分配到內(nèi)存物理地址不一致理地址不一致, ,

5、 而而CPUCPU執(zhí)行指令時，是按物理地址進行執(zhí)行指令時，是按物理地址進行的，所以要進行地址轉(zhuǎn)換。的，所以要進行地址轉(zhuǎn)換。第二章 存 儲 管 理 72.1.2 地址定位方式地址定位方式1. 固定定位方式固定定位方式 由程序員在編寫程序時或由編譯連接程序?qū)υ闯绦蜻M由程序員在編寫程序時或由編譯連接程序?qū)υ闯绦蜻M行編譯連接時，直接指定程序在執(zhí)行時訪問的實際存儲器行編譯連接時，直接指定程序在執(zhí)行時訪問的實際存儲器地址的方式稱為固定定位方式。此種定位方式一般只適合地址的方式稱為固定定位方式。此種定位方式一般只適合于單板機或單用戶系統(tǒng)。在多道程序環(huán)境下，應(yīng)保證各個于單板機或單用戶系統(tǒng)。在多道程序環(huán)境下，應(yīng)

6、保證各個作業(yè)的地址互不重疊，這就比較困難了。作業(yè)的地址互不重疊，這就比較困難了。第二章 存 儲 管 理 8第二章 存 儲 管 理 92. 靜態(tài)重定位方式靜態(tài)重定位方式 源程序經(jīng)編譯和連接后生成目標代碼中的地址是以源程序經(jīng)編譯和連接后生成目標代碼中的地址是以0為起始地址的相對地址。為起始地址的相對地址。 當需要執(zhí)行時，由裝入程序運行重定位程序模塊，當需要執(zhí)行時，由裝入程序運行重定位程序模塊，根據(jù)作業(yè)在本次分配到的內(nèi)存起始地址，將可執(zhí)行目標根據(jù)作業(yè)在本次分配到的內(nèi)存起始地址，將可執(zhí)行目標代碼裝到指定內(nèi)存地址中，代碼裝到指定內(nèi)存地址中，并修改所有有關(guān)地址部分的并修改所有有關(guān)地址部分的值值。 修改的方

7、式是對每一個邏輯地址的值加上內(nèi)存區(qū)首修改的方式是對每一個邏輯地址的值加上內(nèi)存區(qū)首地址（或稱基地址）值。地址（或稱基地址）值。第二章 存 儲 管 理 10第二章 存 儲 管 理 11靜態(tài)重定位的特點靜態(tài)重定位的特點（1 1）靜態(tài)重定位是在程序運行之前完成地址重定位工作的；靜態(tài)重定位是在程序運行之前完成地址重定位工作的；（2 2）靜態(tài)重定位由軟件實現(xiàn)，無須硬件提供支持；靜態(tài)重定位由軟件實現(xiàn)，無須硬件提供支持；（3 3）實行靜態(tài)重定位時，地址重定位工作是在程序裝入時被實行靜態(tài)重定位時，地址重定位工作是在程序裝入時被一次集中完成的；一次集中完成的；（4 4）絕對地址空間里的目標程序與原相對地址空間里的

8、目標絕對地址空間里的目標程序與原相對地址空間里的目標程序面目已不相同，因為前者進行了地址調(diào)整；程序面目已不相同，因為前者進行了地址調(diào)整；（5 5）實施靜態(tài)重定位后，若用戶程序在內(nèi)存中做了移動，那實施靜態(tài)重定位后，若用戶程序在內(nèi)存中做了移動，那么程序指令中的地址就不再反映所在的存儲位置了，除非么程序指令中的地址就不再反映所在的存儲位置了，除非重新進行地址重定位。重新進行地址重定位。第二章 存 儲 管 理 123. 動態(tài)重定位方式動態(tài)重定位方式 采用動態(tài)重定位方式，將程序在裝入內(nèi)存時，不必修采用動態(tài)重定位方式，將程序在裝入內(nèi)存時，不必修改程序的邏輯地址值，程序執(zhí)行期間在訪問內(nèi)存之前，改程序的邏輯地

9、址值，程序執(zhí)行期間在訪問內(nèi)存之前，再實時地將邏輯地址變換成物理地址。動態(tài)重定位要靠再實時地將邏輯地址變換成物理地址。動態(tài)重定位要靠硬件地址變換機構(gòu)實現(xiàn)。硬件地址變換機構(gòu)實現(xiàn)。 當程序開始執(zhí)行時，系統(tǒng)將程序在內(nèi)存的起始地址送當程序開始執(zhí)行時，系統(tǒng)將程序在內(nèi)存的起始地址送入地址變換機構(gòu)中的入地址變換機構(gòu)中的基地址寄存器基地址寄存器BR中。中。 在執(zhí)行指令時，若涉及到邏輯地址，則先將該地址送在執(zhí)行指令時，若涉及到邏輯地址，則先將該地址送入入虛擬地址寄存器虛擬地址寄存器 VR，再將，再將BR 和和 VR 中的值相加后送中的值相加后送入地址寄存器入地址寄存器 MR，并按，并按 MR 中的值訪問內(nèi)存。中的

10、值訪問內(nèi)存。（MR）=（BR）+（VR）第二章 存 儲 管 理 13第二章 存 儲 管 理 142.2 2.2 基本存儲管理方法基本存儲管理方法2.2.1 單一連續(xù)分區(qū)存儲管理單一連續(xù)分區(qū)存儲管理 基本思想基本思想：內(nèi)存分為兩個區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。：內(nèi)存分為兩個區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。應(yīng)用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。應(yīng)用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。 最簡單，適用于單用戶、單任務(wù)的最簡單，適用于單用戶、單任務(wù)的OS；單用戶系單用戶系統(tǒng)在一段時間內(nèi)，只有一個進程在內(nèi)存。統(tǒng)在一段時間內(nèi)，只有一個進程在內(nèi)存。第二章 存 儲 管 理 15特點特點（1）系統(tǒng)總是把整個用戶區(qū)分配給一

11、個用戶使用。系統(tǒng)總是把整個用戶區(qū)分配給一個用戶使用。（2）實際上，內(nèi)存用戶區(qū)又被分為實際上，內(nèi)存用戶區(qū)又被分為“使用區(qū)使用區(qū)”和和“空閑區(qū)空閑區(qū)”兩部分。兩部分。在操作系統(tǒng)中，把分配給用戶、但又未使用的區(qū)域稱為在操作系統(tǒng)中，把分配給用戶、但又未使用的區(qū)域稱為“內(nèi)部碎片內(nèi)部碎片”。（3）由于任何時刻內(nèi)存的用戶區(qū)中只有一個作業(yè)運行，因由于任何時刻內(nèi)存的用戶區(qū)中只有一個作業(yè)運行，因此這種系統(tǒng)只使用于單用戶的情況。此這種系統(tǒng)只使用于單用戶的情況。（4）進入內(nèi)存的作業(yè)，獨享系統(tǒng)中的所有資源，包括內(nèi)存進入內(nèi)存的作業(yè)，獨享系統(tǒng)中的所有資源，包括內(nèi)存中的整個用戶區(qū)。中的整個用戶區(qū)。第二章 存 儲 管 理 16

12、特點特點（5）由于整個用戶區(qū)都分配給了一個用戶使用，因此作業(yè)由于整個用戶區(qū)都分配給了一個用戶使用，因此作業(yè)進入用戶區(qū)后，沒有移動的必要。采用這種存儲分配策進入用戶區(qū)后，沒有移動的必要。采用這種存儲分配策略時，將對用戶程序?qū)嵭新詴r，將對用戶程序?qū)嵭徐o態(tài)重定位靜態(tài)重定位。（6）實行靜態(tài)重定位，并不能阻止用戶有意無意地通過不實行靜態(tài)重定位，并不能阻止用戶有意無意地通過不恰當?shù)刂噶铌J入操作系統(tǒng)所占用的存儲區(qū)域，如何阻止恰當?shù)刂噶铌J入操作系統(tǒng)所占用的存儲區(qū)域，如何阻止對操作系統(tǒng)的侵擾，就是所謂的對操作系統(tǒng)的侵擾，就是所謂的“存儲保護存儲保護”問題。問題。用于存儲保護的專用寄存器用于存儲保護的專用寄存器“

13、界限寄存器界限寄存器”第二章 存 儲 管 理 17 存儲保護過程存儲保護過程：在：在用戶態(tài)用戶態(tài)下，對內(nèi)存的每一次訪問，都下，對內(nèi)存的每一次訪問，都要要在硬件的控制在硬件的控制下，與界限寄存器中的內(nèi)容進行比較。下，與界限寄存器中的內(nèi)容進行比較。一旦發(fā)現(xiàn)該訪問的地址小于界限寄存器中的地址，就會一旦發(fā)現(xiàn)該訪問的地址小于界限寄存器中的地址，就會產(chǎn)生產(chǎn)生“地址越界地址越界”中斷，阻止這次訪問的進行。中斷，阻止這次訪問的進行。 優(yōu)點優(yōu)點：易于管理，便于用戶的了解和使用。：易于管理，便于用戶的了解和使用。 缺點缺點： 由于每次只能有一個作業(yè)進入內(nèi)存，故它不適用于多由于每次只能有一個作業(yè)進入內(nèi)存，故它不適用

14、于多道程序設(shè)計，整個系統(tǒng)的工作效率不高，資源利用率道程序設(shè)計，整個系統(tǒng)的工作效率不高，資源利用率底下。底下。 只要作業(yè)比用戶區(qū)小，那么在用戶區(qū)里就會形成碎片，只要作業(yè)比用戶區(qū)小，那么在用戶區(qū)里就會形成碎片，造成內(nèi)存儲器資源的浪費。造成內(nèi)存儲器資源的浪費。 若用戶作業(yè)的相對地址空間比用戶區(qū)大，那么該作業(yè)若用戶作業(yè)的相對地址空間比用戶區(qū)大，那么該作業(yè)就無法運行。就無法運行。第二章 存 儲 管 理 182.2.2 固定分區(qū)存儲管理固定分區(qū)存儲管理 把內(nèi)存區(qū)把內(nèi)存區(qū)固定固定地劃分為若干個大小相等（和不等）的地劃分為若干個大小相等（和不等）的連續(xù)分區(qū)。連續(xù)分區(qū)。每個分區(qū)裝一個且只能裝每個分區(qū)裝一個且只能

15、裝一個一個作業(yè)，分區(qū)作業(yè)，分區(qū)的劃分原則一般由系統(tǒng)操作員或操作系統(tǒng)決定，分區(qū)的劃分原則一般由系統(tǒng)操作員或操作系統(tǒng)決定，分區(qū)一旦劃分結(jié)束，在整個執(zhí)行過程中每個分區(qū)的一旦劃分結(jié)束，在整個執(zhí)行過程中每個分區(qū)的長度長度和和內(nèi)存的總分區(qū)內(nèi)存的總分區(qū)個數(shù)個數(shù)將將保持不變保持不變。 分區(qū)大小相等分區(qū)大小相等：只適合于多個相同程序的并發(fā)執(zhí)行：只適合于多個相同程序的并發(fā)執(zhí)行（處理多個類型相同的對象）。（處理多個類型相同的對象）。 分區(qū)大小不等：分區(qū)大小不等：多個小分區(qū)、適量的中等分區(qū)、少量多個小分區(qū)、適量的中等分區(qū)、少量的大分區(qū)。根據(jù)程序的大小，分配當前空閑的、適當?shù)拇蠓謪^(qū)。根據(jù)程序的大小，分配當前空閑的、適當

16、大小的分區(qū)。大小的分區(qū)。第二章 存 儲 管 理 198 M8 M8 M8 M8 MOperating SystemOperating System8 M12 M8 M8 M6 M4 M2 M第二章 存 儲 管 理 20內(nèi)存分配內(nèi)存分配 為了便于內(nèi)存分配，通常將分區(qū)按大小進行排隊，為了便于內(nèi)存分配，通常將分區(qū)按大小進行排隊，并為之建立一張分區(qū)說明表，其中各表項包括每個分區(qū)并為之建立一張分區(qū)說明表，其中各表項包括每個分區(qū)的起始地址、大小及狀態(tài)（是否已分配）。的起始地址、大小及狀態(tài)（是否已分配）。 當有一用戶程序要裝入時，由內(nèi)存分配程序檢索該當有一用戶程序要裝入時，由內(nèi)存分配程序檢索該表，從中找出一

17、個能滿足要求的、尚未分配的分區(qū)，將表，從中找出一個能滿足要求的、尚未分配的分區(qū)，將之分配給該應(yīng)用程序，然后將該表項中的狀態(tài)置為之分配給該應(yīng)用程序，然后將該表項中的狀態(tài)置為“已已分配分配”；若未找到大小足夠的分區(qū)，則拒絕為該用戶程；若未找到大小足夠的分區(qū)，則拒絕為該用戶程序分配內(nèi)存。序分配內(nèi)存。第二章 存 儲 管 理 21第二章 存 儲 管 理 22地址重定位與存儲保護地址重定位與存儲保護 固定分區(qū)存儲管理中，每個分區(qū)只允許裝入一個作業(yè)，固定分區(qū)存儲管理中，每個分區(qū)只允許裝入一個作業(yè)，作業(yè)在運行期間沒有必要移動自己的位置，因此，應(yīng)作業(yè)在運行期間沒有必要移動自己的位置，因此，應(yīng)該對程序?qū)嵭性搶Τ绦?/p>

18、實行靜態(tài)重定位靜態(tài)重定位。 在固定分區(qū)存儲管理中，不僅要防止用戶程序?qū)Σ僮髟诠潭ǚ謪^(qū)存儲管理中，不僅要防止用戶程序?qū)Σ僮飨到y(tǒng)形成的侵擾，也要防止用戶程序與用戶程序之間系統(tǒng)形成的侵擾，也要防止用戶程序與用戶程序之間形成侵擾。因此必須在形成侵擾。因此必須在CPU中設(shè)置一對專用的寄存器，中設(shè)置一對專用的寄存器，用于存儲保護。將兩個專用寄存器分別起名為用于存儲保護。將兩個專用寄存器分別起名為“下下界界寄存器寄存器”和和“上界寄存器上界寄存器”第二章 存 儲 管 理 23存儲保護過程存儲保護過程 當進程調(diào)度程序調(diào)度某個作業(yè)進程運行時，就把該作當進程調(diào)度程序調(diào)度某個作業(yè)進程運行時，就把該作業(yè)所在分區(qū)的低邊

19、界地址裝入到低界限寄存器，高邊業(yè)所在分區(qū)的低邊界地址裝入到低界限寄存器，高邊界地址裝入到高界限寄存器。作業(yè)運行時，對內(nèi)存的界地址裝入到高界限寄存器。作業(yè)運行時，對內(nèi)存的每一次訪問，都要每一次訪問，都要在硬件的控制在硬件的控制下，與兩個界限寄存下，與兩個界限寄存器中的內(nèi)容進行比較。一旦發(fā)現(xiàn)該訪問的地址小于界器中的內(nèi)容進行比較。一旦發(fā)現(xiàn)該訪問的地址小于界限寄存器中的地址，就會產(chǎn)生限寄存器中的地址，就會產(chǎn)生“地址越界地址越界”中斷，阻中斷，阻止這次訪問的進行。止這次訪問的進行。第二章 存 儲 管 理 24固定分區(qū)存儲管理的特點固定分區(qū)存儲管理的特點 （1）它是最簡單的、具有）它是最簡單的、具有“多道

20、多道”色彩的存儲管理方色彩的存儲管理方案。案。 （2）當把一個分區(qū)分配給某個作業(yè)時，該作業(yè)的程序）當把一個分區(qū)分配給某個作業(yè)時，該作業(yè)的程序?qū)⒁淮涡缘娜勘谎b入到分配給它的連續(xù)分區(qū)里。將一次性的全部被裝入到分配給它的連續(xù)分區(qū)里。第二章 存 儲 管 理 25 優(yōu)點：易于實現(xiàn)，開銷小。優(yōu)點：易于實現(xiàn)，開銷小。 缺點：缺點： 內(nèi)碎片造成浪費（小作業(yè)不能有效地利用分區(qū)空間。內(nèi)碎片造成浪費（小作業(yè)不能有效地利用分區(qū)空間。 分區(qū)總數(shù)在系統(tǒng)生成時確定（固定），限制了并發(fā)分區(qū)總數(shù)在系統(tǒng)生成時確定（固定），限制了并發(fā)執(zhí)行的程序數(shù)目。執(zhí)行的程序數(shù)目。 如果到達作業(yè)的尺寸比任何一個分區(qū)的長度都大，如果到達作業(yè)的尺寸

21、比任何一個分區(qū)的長度都大，那么它就無法得到運行。那么它就無法得到運行。固定分區(qū)方式的評價固定分區(qū)方式的評價第二章 存 儲 管 理 262.3 2.3 可變分區(qū)存儲管理可變分區(qū)存儲管理 基本思想：基本思想： 內(nèi)存不是預(yù)先劃分好的，而是當作業(yè)裝入內(nèi)存不是預(yù)先劃分好的，而是當作業(yè)裝入時，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是時，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配。否分配。 若有足夠的空間，則按需要分割一部分分區(qū)給該進若有足夠的空間，則按需要分割一部分分區(qū)給該進程程 否則令其等待主存空間否則令其等待主存空間 優(yōu)點優(yōu)點：沒有內(nèi)碎片。：沒有內(nèi)碎片。 缺點缺點：有外碎片。：有外碎片。第二章

22、 存 儲 管 理 27外部碎片問題外部碎片問題操作系統(tǒng)操作系統(tǒng)20KB0256KB作業(yè)作業(yè)A(16KB)A(16KB)空閑區(qū)空閑區(qū)(236KB)空閑區(qū)空閑區(qū)(220KB)作業(yè)作業(yè)B(100KB)B(100KB)空閑區(qū)空閑區(qū)(120KB)(120KB)作業(yè)作業(yè)C(70KB)C(70KB)空閑區(qū)空閑區(qū)(50KB)(50KB)空閑區(qū)空閑區(qū)(100KB)(100KB)作業(yè)作業(yè)D(75KB)D(75KB)空閑區(qū)空閑區(qū)(25KB)(25KB)第二章 存 儲 管 理 282.3.1 空閑存儲區(qū)表空閑存儲區(qū)表 管理空閑內(nèi)存區(qū)的數(shù)據(jù)結(jié)構(gòu)可采用鏈接法和連續(xù)線性表管理空閑內(nèi)存區(qū)的數(shù)據(jù)結(jié)構(gòu)可采用鏈接法和連續(xù)線性表格法

23、。下面舉一個連續(xù)線性表格管理空閑內(nèi)存的方法，格法。下面舉一個連續(xù)線性表格管理空閑內(nèi)存的方法，如采用鏈接法，就需要在表項中增加一個指向下一個空如采用鏈接法，就需要在表項中增加一個指向下一個空閑區(qū)的指針。閑區(qū)的指針。每一個空閑分區(qū)用一個每一個空閑分區(qū)用一個map結(jié)構(gòu)管理：結(jié)構(gòu)管理：struct map unsigned m_size; /空閑分區(qū)的長度空閑分區(qū)的長度 char *m_addr; /空閑分區(qū)的起始地址空閑分區(qū)的起始地址 ;struct map coremapN;各個空閑分區(qū)按起始地址由低到高順次登記在空閑存儲區(qū)各個空閑分區(qū)按起始地址由低到高順次登記在空閑存儲區(qū)表中，表中，m_size

24、為為0的表項是空白表項，它們集中在表的的表項是空白表項，它們集中在表的后部后部第二章 存 儲 管 理 29l在系統(tǒng)初始階段，在系統(tǒng)初始階段，擁有一塊很大的內(nèi)擁有一塊很大的內(nèi)存空白區(qū)，這時空存空白區(qū)，這時空閑存儲區(qū)表閑存儲區(qū)表coremapcoremap中只需有一項登記中只需有一項登記該空閑區(qū)。該空閑區(qū)。l其余的其余的coremapcoremap表表項為空白項，即項為空白項，即m_sizem_size皆為零。皆為零。第二章 存 儲 管 理 30l以后隨著很多作以后隨著很多作業(yè)的不斷申請內(nèi)存業(yè)的不斷申請內(nèi)存和釋放內(nèi)存，整個和釋放內(nèi)存，整個存儲空間將出現(xiàn)許存儲空間將出現(xiàn)許多大小不等的區(qū)域，多大小不等

25、的區(qū)域，l存儲區(qū)表和實際存儲區(qū)表和實際的內(nèi)存空間就可能的內(nèi)存空間就可能變成如圖所示的情變成如圖所示的情況。況。第二章 存 儲 管 理 312.3.2 首次適應(yīng)算法首次適應(yīng)算法 1. 分配算法分配算法。u采用首次適應(yīng)法為作業(yè)分配大小為采用首次適應(yīng)法為作業(yè)分配大小為size的內(nèi)存空間時，的內(nèi)存空間時，總是從表的起始端的低地址部分開始查找?？偸菑谋淼钠鹗级说牡偷刂凡糠珠_始查找。u當?shù)谝淮握业酱笥诨虻扔谏暾埓笮〉目臻e區(qū)時，就按當?shù)谝淮握业酱笥诨虻扔谏暾埓笮〉目臻e區(qū)時，就按所需大小分配給作業(yè)。所需大小分配給作業(yè)。u如果分配后原空閑區(qū)還有剩余空間，就修改原存儲區(qū)如果分配后原空閑區(qū)還有剩余空間，就修改原存儲

26、區(qū)表項的表項的 m_size 和和 m_addr，使它記錄余下的，使它記錄余下的“零頭零頭”。u如果作業(yè)所需空間正好等于該空閑區(qū)大小，那么該空如果作業(yè)所需空間正好等于該空閑區(qū)大小，那么該空閑區(qū)表項的閑區(qū)表項的m_size就成為就成為0。u接下來要刪除表中這個接下來要刪除表中這個“空洞空洞”，即將隨后的各非零，即將隨后的各非零表項依次上移一個位置表項依次上移一個位置第二章 存 儲 管 理 32char *malloc(mp,size)struct map *mp;unsigned size; register char *a; register struct map *bp; for (bp =

27、 mp; bp-m_size; bp+) if(bp-m_size = size) a = 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(a); return(0);第二章 存 儲 管 理 332. 回收算法回收算法 l當某一作業(yè)釋放以前所分配到的內(nèi)存時，就要將該內(nèi)當某一作業(yè)釋放以前所分配到的內(nèi)存時，就要將該內(nèi)存區(qū)歸還給系統(tǒng)，使其成為空閑區(qū)而可被其他作業(yè)使存區(qū)歸還給系統(tǒng)，使其成為

28、空閑區(qū)而可被其他作業(yè)使用。用。l釋放區(qū)與原空閑區(qū)相鄰情況可歸納為如圖所示的釋放區(qū)與原空閑區(qū)相鄰情況可歸納為如圖所示的4種情種情況。況。第二章 存 儲 管 理 34u 僅與前空閑區(qū)相連僅與前空閑區(qū)相連：合并前空閑區(qū)和釋放區(qū)構(gòu)成一：合并前空閑區(qū)和釋放區(qū)構(gòu)成一塊大的新空閑區(qū)，并修改空閑區(qū)表項。該空閑區(qū)的塊大的新空閑區(qū)，并修改空閑區(qū)表項。該空閑區(qū)的m_addr不變，仍為原前空閑區(qū)的首地址，修改表項的不變，仍為原前空閑區(qū)的首地址，修改表項的長度域長度域m_size為原為原m_size 與釋放區(qū)長度之和。與釋放區(qū)長度之和。u 與前空閑區(qū)和后空閑區(qū)都相連與前空閑區(qū)和后空閑區(qū)都相連：將三塊空閑區(qū)合并：將三塊空

29、閑區(qū)合并成一塊空閑區(qū)。修改空閑區(qū)表中前空閑區(qū)表項，其起成一塊空閑區(qū)。修改空閑區(qū)表中前空閑區(qū)表項，其起始地址始地址m_addr仍為原前空閑區(qū)起始地址，其大小仍為原前空閑區(qū)起始地址，其大小m_size等于三個空閑區(qū)長度之和，這塊大的空閑區(qū)由等于三個空閑區(qū)長度之和，這塊大的空閑區(qū)由前空閑區(qū)表項登記。接下來還要在空閑區(qū)表中刪除后前空閑區(qū)表項登記。接下來還要在空閑區(qū)表中刪除后項，方法是將后項以下的非空白表項順次上移一個位項，方法是將后項以下的非空白表項順次上移一個位置。置。第二章 存 儲 管 理 35u 僅與后空閑區(qū)相連僅與后空閑區(qū)相連：與后空閑區(qū)合并，使后空閑區(qū)：與后空閑區(qū)合并，使后空閑區(qū)表項的表項的

30、m_addr為釋放區(qū)的起始地址，為釋放區(qū)的起始地址，m_size為釋放區(qū)為釋放區(qū)與后空閑區(qū)的長度之和。與后空閑區(qū)的長度之和。u 與前、后空閑區(qū)皆不相連與前、后空閑區(qū)皆不相連：在前、后空閑區(qū)表項中：在前、后空閑區(qū)表項中間插入一個新的表項，其間插入一個新的表項，其 m_addr為釋放區(qū)的起始地址，為釋放區(qū)的起始地址，m_size為釋放區(qū)的長度。為此，先要將后項及以下表為釋放區(qū)的長度。為此，先要將后項及以下表項都下移一個位置項都下移一個位置第二章 存 儲 管 理 36u若采用首次適應(yīng)法，則其分配算法簡單且合并若采用首次適應(yīng)法，則其分配算法簡單且合并相鄰空閑區(qū)也很容易。相鄰空閑區(qū)也很容易。u該算法的實

31、質(zhì)是盡可能利用存儲區(qū)低地址部分該算法的實質(zhì)是盡可能利用存儲區(qū)低地址部分的空閑區(qū)，而盡量在高地址部分保存較大的空的空閑區(qū)，而盡量在高地址部分保存較大的空閑區(qū)，以便一旦有分配大的空閑區(qū)的要求時，閑區(qū)，以便一旦有分配大的空閑區(qū)的要求時，容易得到滿足。容易得到滿足。u其缺點是由于查找總是從表首開始，前面的空其缺點是由于查找總是從表首開始，前面的空閑區(qū)往往被分割得很小，能滿足分配要求的可閑區(qū)往往被分割得很小，能滿足分配要求的可能性較小，查找次數(shù)就較多。系統(tǒng)中作業(yè)越多，能性較小，查找次數(shù)就較多。系統(tǒng)中作業(yè)越多，這個問題就越嚴重。這個問題就越嚴重。第二章 存 儲 管 理 372.3.3 循環(huán)首次適應(yīng)算法循環(huán)

32、首次適應(yīng)算法u把空閑表設(shè)計成順序結(jié)構(gòu)或鏈接結(jié)構(gòu)的循環(huán)隊列，把空閑表設(shè)計成順序結(jié)構(gòu)或鏈接結(jié)構(gòu)的循環(huán)隊列，各空閑區(qū)仍按地址從低到高的次序登記在空閑區(qū)的各空閑區(qū)仍按地址從低到高的次序登記在空閑區(qū)的管理隊列中。管理隊列中。u同時需要設(shè)置一個起始查找指針，指向循環(huán)隊列中同時需要設(shè)置一個起始查找指針，指向循環(huán)隊列中的一個空閑區(qū)表項。的一個空閑區(qū)表項。u循環(huán)首次適應(yīng)法分配時總是從起始查找指針所指的循環(huán)首次適應(yīng)法分配時總是從起始查找指針所指的表項開始查找。表項開始查找。u第一次找到滿足要求的空閑區(qū)時，就分配所需大小第一次找到滿足要求的空閑區(qū)時，就分配所需大小的空閑區(qū)，修改表項，并調(diào)整起始查找指針，使其的空閑區(qū)

33、，修改表項，并調(diào)整起始查找指針，使其指向隊列中被分配的后面的那塊空閑區(qū)。指向隊列中被分配的后面的那塊空閑區(qū)。u下次分配時就從新指向的那塊空閑區(qū)開始查找。下次分配時就從新指向的那塊空閑區(qū)開始查找。第二章 存 儲 管 理 382.3.3 循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法u循環(huán)首次適應(yīng)法的實質(zhì)是起始查找指針所指的空閑循環(huán)首次適應(yīng)法的實質(zhì)是起始查找指針所指的空閑區(qū)和其后的空閑區(qū)群常為較長時間未被分割過的空區(qū)和其后的空閑區(qū)群常為較長時間未被分割過的空閑區(qū)，它們已合并成為大的空閑區(qū)可能性較大。閑區(qū)，它們已合并成為大的空閑區(qū)可能性較大。u比起首次適應(yīng)法來，在沒有增加多少代價的情況下比起首次適應(yīng)法來，在沒有增

34、加多少代價的情況下卻明顯地提高了分配查找的速度。釋放算法基本同卻明顯地提高了分配查找的速度。釋放算法基本同首次適應(yīng)法一樣。首次適應(yīng)法一樣。u首次適應(yīng)法和循環(huán)首次適應(yīng)法不僅可用于內(nèi)存的分首次適應(yīng)法和循環(huán)首次適應(yīng)法不僅可用于內(nèi)存的分配和釋放，也可用于進程圖像交換的輔存空間的分配和釋放，也可用于進程圖像交換的輔存空間的分配和釋放，其管理空閑區(qū)的數(shù)據(jù)結(jié)構(gòu)也相同。配和釋放，其管理空閑區(qū)的數(shù)據(jù)結(jié)構(gòu)也相同。第二章 存 儲 管 理 392.3.4 最佳適應(yīng)算法最佳適應(yīng)算法u所謂最佳適應(yīng)算法就是在所有大于或等于要求分配所謂最佳適應(yīng)算法就是在所有大于或等于要求分配長度的空閑分區(qū)中挑選一個最小的分區(qū)，在分割后，長度

35、的空閑分區(qū)中挑選一個最小的分區(qū)，在分割后，所余下的剩余存儲區(qū)最小或等于零。所余下的剩余存儲區(qū)最小或等于零。u因此，該算法的空閑區(qū)利用率高，較大的空閑區(qū)被因此，該算法的空閑區(qū)利用率高，較大的空閑區(qū)被保存下來。保存下來。u空閑存儲區(qū)管理表的組織方法可以采用順序結(jié)構(gòu)，空閑存儲區(qū)管理表的組織方法可以采用順序結(jié)構(gòu)，也可采用鏈接結(jié)構(gòu)。也可采用鏈接結(jié)構(gòu)。u如采用順序結(jié)構(gòu)，空閑分區(qū)按地址由小到大的順序如采用順序結(jié)構(gòu)，空閑分區(qū)按地址由小到大的順序登記在表中，分配時需要搜索所有的空閑分區(qū)，以登記在表中，分配時需要搜索所有的空閑分區(qū)，以在其中挑出一個滿足分配大小的最小的分區(qū)。此種在其中挑出一個滿足分配大小的最小的分

36、區(qū)。此種管理結(jié)構(gòu)的釋放算法可用順序結(jié)構(gòu)的首次適應(yīng)法。管理結(jié)構(gòu)的釋放算法可用順序結(jié)構(gòu)的首次適應(yīng)法。第二章 存 儲 管 理 402.3.4 最佳適應(yīng)算法最佳適應(yīng)算法u當采用鏈接結(jié)構(gòu)時，空閑區(qū)也可按由小到大的非遞減次當采用鏈接結(jié)構(gòu)時，空閑區(qū)也可按由小到大的非遞減次序排列。序排列。u分配時總是從最小的第一項開始，這樣第一次找到的滿分配時總是從最小的第一項開始，這樣第一次找到的滿足條件的空閑區(qū)必定是最合適的。足條件的空閑區(qū)必定是最合適的。u平均而言，只要搜索一半數(shù)目的空閑區(qū)表項就能找到最平均而言，只要搜索一半數(shù)目的空閑區(qū)表項就能找到最佳配合的空閑區(qū)，但尋找較大空閑區(qū)比較費時。佳配合的空閑區(qū)，但尋找較大空

37、閑區(qū)比較費時。u采用按存儲區(qū)大小排序的鏈接表會降低釋放算法的效率。采用按存儲區(qū)大小排序的鏈接表會降低釋放算法的效率。u由于空閑區(qū)是按大小而不是按地址序號排序的，因此釋由于空閑區(qū)是按大小而不是按地址序號排序的，因此釋放回收空閑區(qū)時要在整個鏈表上尋找地址相鄰的前、后放回收空閑區(qū)時要在整個鏈表上尋找地址相鄰的前、后空閑區(qū)，合并后又要插入到合適的位置，因此釋放算法空閑區(qū)，合并后又要插入到合適的位置，因此釋放算法比前兩種算法耗時得多。比前兩種算法耗時得多。第二章 存 儲 管 理 412.3.5 最差適應(yīng)算法最差適應(yīng)算法u最差適應(yīng)法所分割的空閑存儲區(qū)是所有空閑分區(qū)中最差適應(yīng)法所分割的空閑存儲區(qū)是所有空閑分

38、區(qū)中的最大的一塊。的最大的一塊。u在實施最差適應(yīng)法時，空閑區(qū)管理表項一般以在實施最差適應(yīng)法時，空閑區(qū)管理表項一般以m_size由大到小的次序組織成一個鏈接表，因此查由大到小的次序組織成一個鏈接表，因此查找分割的總是最大的第一個空閑存儲區(qū)。找分割的總是最大的第一個空閑存儲區(qū)。u實現(xiàn)最差適應(yīng)法時的空閑存儲區(qū)表的組織方法一般實現(xiàn)最差適應(yīng)法時的空閑存儲區(qū)表的組織方法一般都是采用按空閑塊由大到小排序的鏈接表。采用按都是采用按空閑塊由大到小排序的鏈接表。采用按存儲區(qū)大小順序排列的鏈接表的形式雖然釋放一個存儲區(qū)大小順序排列的鏈接表的形式雖然釋放一個空閑塊時速度較慢，但分配效率是一切算法中最高空閑塊時速度較慢

39、，但分配效率是一切算法中最高的一種。的一種。第二章 存 儲 管 理 42可變分區(qū)存儲管理的特點可變分區(qū)存儲管理的特點u（1）作業(yè)一次性的全部裝入到一個連續(xù)的存）作業(yè)一次性的全部裝入到一個連續(xù)的存儲分區(qū)中。儲分區(qū)中。u（2）分區(qū)是按照作業(yè)對存儲的需求劃分的，）分區(qū)是按照作業(yè)對存儲的需求劃分的，因此在可變分區(qū)管理中，不會出現(xiàn)內(nèi)部碎片這因此在可變分區(qū)管理中，不會出現(xiàn)內(nèi)部碎片這樣的存儲浪費。樣的存儲浪費。u（3）為了確保作業(yè)能夠在內(nèi)存中移動，要由）為了確保作業(yè)能夠在內(nèi)存中移動，要由硬件支持，實行指令地址的動態(tài)重定位。硬件支持，實行指令地址的動態(tài)重定位。第二章 存 儲 管 理 43可變分區(qū)存儲管理的缺點

40、可變分區(qū)存儲管理的缺點u（1）仍然沒有解決小內(nèi)存運行大作業(yè)的問題。）仍然沒有解決小內(nèi)存運行大作業(yè)的問題。u（2）雖然避免了內(nèi)部碎片造成的存儲浪費，但）雖然避免了內(nèi)部碎片造成的存儲浪費，但有可能出現(xiàn)極小的分區(qū)暫時分配不出去的情形，有可能出現(xiàn)極小的分區(qū)暫時分配不出去的情形，引起外部碎片。引起外部碎片。u（3）為了形成大的分區(qū)，可變分區(qū)存儲管理通）為了形成大的分區(qū)，可變分區(qū)存儲管理通過移動程序來達到分區(qū)合并的目的，然而程序的過移動程序來達到分區(qū)合并的目的，然而程序的移動是很花費時間的，增加了系統(tǒng)在這方面的開移動是很花費時間的，增加了系統(tǒng)在這方面的開銷。銷。第二章 存 儲 管 理 442.3.6 多重

41、分區(qū)多重分區(qū)u可變分區(qū)存儲管理算法是按作業(yè)對存儲的需求分配可變分區(qū)存儲管理算法是按作業(yè)對存儲的需求分配存儲區(qū)的，因而消除了固定分區(qū)內(nèi)部的剩余碎片，存儲區(qū)的，因而消除了固定分區(qū)內(nèi)部的剩余碎片，但隨著存儲區(qū)的分配和釋放過程的進行，在各個被但隨著存儲區(qū)的分配和釋放過程的進行，在各個被分配出去的分區(qū)之間會存在很多的空閑區(qū)，這就是分配出去的分區(qū)之間會存在很多的空閑區(qū)，這就是“外部碎片外部碎片”。u有時，當一個作業(yè)要裝入運行，但分配不到一個夠有時，當一個作業(yè)要裝入運行，但分配不到一個夠用的空閑分區(qū)，盡管這時內(nèi)存中所有外部碎片的總用的空閑分區(qū)，盡管這時內(nèi)存中所有外部碎片的總和遠大于作業(yè)所申請的空間。和遠大于

42、作業(yè)所申請的空間。u如采用如采用“緊湊緊湊”技術(shù)重新安排內(nèi)存中各個作業(yè)的位技術(shù)重新安排內(nèi)存中各個作業(yè)的位置，以使零碎的空閑區(qū)集中起來，這是一個極其耗置，以使零碎的空閑區(qū)集中起來，這是一個極其耗時的過程，一般很少采用這種策略。時的過程，一般很少采用這種策略。第二章 存 儲 管 理 45請求分配請求分配u.size分分區(qū)區(qū)檢索空閑分區(qū)鏈（表）檢索空閑分區(qū)鏈（表）找到大于找到大于u.size的可的可用區(qū)否用區(qū)否按動態(tài)分區(qū)方按動態(tài)分區(qū)方式進行分配式進行分配修改有關(guān)的數(shù)修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)據(jù)結(jié)構(gòu)返回分返回分區(qū)號及區(qū)號及首地址首地址空閑分空閑分區(qū)總和區(qū)總和=u.size進行緊湊形成進行緊湊形成連續(xù)空閑區(qū)連續(xù)

43、空閑區(qū)修改有關(guān)的數(shù)修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)據(jù)結(jié)構(gòu)無法分配無法分配返回返回否否否否是是是是第二章 存 儲 管 理 462.3.6 多重分區(qū)多重分區(qū)u有些系統(tǒng)采用多重分區(qū)技術(shù)，在作業(yè)的運行過程中有些系統(tǒng)采用多重分區(qū)技術(shù)，在作業(yè)的運行過程中可以申請附加的分區(qū)，以裝入一個或多個子程序?？梢陨暾埜郊拥姆謪^(qū)，以裝入一個或多個子程序。新申請的空閑分區(qū)也無需與作業(yè)的現(xiàn)有分區(qū)相鄰接。新申請的空閑分區(qū)也無需與作業(yè)的現(xiàn)有分區(qū)相鄰接。u采用多重分區(qū)技術(shù)可以提高外部碎片的利用率，也采用多重分區(qū)技術(shù)可以提高外部碎片的利用率，也便于多個作業(yè)共享分區(qū)的代碼和數(shù)據(jù)，這只要在共便于多個作業(yè)共享分區(qū)的代碼和數(shù)據(jù)，這只要在共享的作業(yè)中包含

44、某個共享的分區(qū)即可。享的作業(yè)中包含某個共享的分區(qū)即可。u多重分區(qū)系統(tǒng)應(yīng)當采用動態(tài)重定位技術(shù)，但存儲管多重分區(qū)系統(tǒng)應(yīng)當采用動態(tài)重定位技術(shù)，但存儲管理的復(fù)雜性也增加了。為了實現(xiàn)存儲保護，在多重理的復(fù)雜性也增加了。為了實現(xiàn)存儲保護，在多重分區(qū)系統(tǒng)中要設(shè)置多對界地址寄存器，以使現(xiàn)運行分區(qū)系統(tǒng)中要設(shè)置多對界地址寄存器，以使現(xiàn)運行作業(yè)對每一個分區(qū)的訪問都不會越界。作業(yè)對每一個分區(qū)的訪問都不會越界。第二章 存 儲 管 理 472.4 2.4 內(nèi)存擴充技術(shù)內(nèi)存擴充技術(shù)u在基本的存儲管理系統(tǒng)中，當一個作業(yè)的程序地址空在基本的存儲管理系統(tǒng)中，當一個作業(yè)的程序地址空間大于內(nèi)存可用空間時，該作業(yè)就不能裝入運行；間大于

45、內(nèi)存可用空間時，該作業(yè)就不能裝入運行；u當并發(fā)運行作業(yè)的程序地址空間總和大于內(nèi)存可用空當并發(fā)運行作業(yè)的程序地址空間總和大于內(nèi)存可用空間時，多道程序設(shè)計的實現(xiàn)就會碰到很大的困難。間時，多道程序設(shè)計的實現(xiàn)就會碰到很大的困難。u內(nèi)存擴充技術(shù)就是借助大容量的輔存在邏輯上實現(xiàn)內(nèi)內(nèi)存擴充技術(shù)就是借助大容量的輔存在邏輯上實現(xiàn)內(nèi)存的擴充，以解決內(nèi)存容量不足的問題。存的擴充，以解決內(nèi)存容量不足的問題。第二章 存 儲 管 理 482.4.1 覆蓋覆蓋(overlay) 引入：引入：其目標是在較小的可用內(nèi)存中其目標是在較小的可用內(nèi)存中運行較大的程序運行較大的程序。 原理：原理：覆蓋技術(shù)就是將一個大程序按程序的邏輯結(jié)

46、構(gòu)劃分成覆蓋技術(shù)就是將一個大程序按程序的邏輯結(jié)構(gòu)劃分成若干個程序（或數(shù)據(jù)）段，并將不會同時執(zhí)行，從而就不必若干個程序（或數(shù)據(jù)）段，并將不會同時執(zhí)行，從而就不必同時裝入內(nèi)存的程序段分在一組內(nèi)，該組稱為同時裝入內(nèi)存的程序段分在一組內(nèi)，該組稱為覆蓋段覆蓋段。這個。這個覆蓋段可分配到同一個稱為覆蓋段可分配到同一個稱為覆蓋區(qū)覆蓋區(qū)的存儲區(qū)域的存儲區(qū)域。 將程序的將程序的必要部分必要部分（常用功能）的代碼和數(shù)據(jù)常駐內(nèi)存；（常用功能）的代碼和數(shù)據(jù)常駐內(nèi)存； 可選部分可選部分（不常用功能）在其他程序模塊中實現(xiàn)，平時存（不常用功能）在其他程序模塊中實現(xiàn)，平時存放在外存中（覆蓋文件），在需要用到時才裝入到內(nèi)存；放

47、在外存中（覆蓋文件），在需要用到時才裝入到內(nèi)存； 不存在調(diào)用關(guān)系的模塊不必同時裝入到內(nèi)存，從而可以相不存在調(diào)用關(guān)系的模塊不必同時裝入到內(nèi)存，從而可以相互覆蓋?；ジ采w。( (即即不同時用的模塊可共用一個分區(qū)不同時用的模塊可共用一個分區(qū)) )第二章 存 儲 管 理 49A20KB50KC30KF30KD20KE40KResident20KOverlay 050KOverlay 140KTotal: 190KTotal: 110K注：另一種覆蓋方法：注：另一種覆蓋方法：(100K)(100K)A(20K)A(20K)占一個分區(qū)：占一個分區(qū)：20K20K；B(50K)B(50K)、D(20K)D(20

48、K)和和E(40K)E(40K)共用一個分區(qū)：共用一個分區(qū)：50K50K；F(30K)F(30K)和和C(30K)C(30K)共用一個分區(qū)：共用一個分區(qū)：30K30K；第二章 存 儲 管 理 50 缺點：缺點： 對用戶不透明，增加了用戶負擔(dān)。對用戶不透明，增加了用戶負擔(dān)。編程時必須劃編程時必須劃分程序模塊和確定程序模塊之間的覆蓋關(guān)系，增分程序模塊和確定程序模塊之間的覆蓋關(guān)系，增加編程復(fù)雜度。加編程復(fù)雜度。 從外存裝入覆蓋文件，以時間延長來換取空間節(jié)從外存裝入覆蓋文件，以時間延長來換取空間節(jié)省。省。 覆蓋不需要任何來自操作系統(tǒng)的特殊支持，由用覆蓋不需要任何來自操作系統(tǒng)的特殊支持，由用戶程序自己控

49、制戶程序自己控制 所以，覆蓋通常限于用在微機和其他內(nèi)存容量所以，覆蓋通常限于用在微機和其他內(nèi)存容量有限的或缺乏對更先進技術(shù)的硬件支持的系統(tǒng)中有限的或缺乏對更先進技術(shù)的硬件支持的系統(tǒng)中第二章 存 儲 管 理 512.4.2 交換交換(swapping)u引入引入：讓單一連續(xù)分區(qū)存儲管理能具有：讓單一連續(xù)分區(qū)存儲管理能具有“多道多道”的效果。的效果。u中心思想中心思想：將作業(yè)信息都存放在輔存上，根據(jù)單一連續(xù)分區(qū)：將作業(yè)信息都存放在輔存上，根據(jù)單一連續(xù)分區(qū)存儲管理的分配策略，每次只讓其中一個進入內(nèi)存投入運行，存儲管理的分配策略，每次只讓其中一個進入內(nèi)存投入運行，當運行中提出輸入輸出請求或分配的時間片

50、用完時，就把這當運行中提出輸入輸出請求或分配的時間片用完時，就把這個程序從內(nèi)存儲器個程序從內(nèi)存儲器“換出換出”到輔存，把輔存里的另一個作業(yè)到輔存，把輔存里的另一個作業(yè)“換入換入”內(nèi)存運行。這樣從宏觀上看，系統(tǒng)中同時就有幾個內(nèi)存運行。這樣從宏觀上看，系統(tǒng)中同時就有幾個作業(yè)處在運行之中。作業(yè)處在運行之中。u為了減少在主存和輔存間傳輸?shù)臄?shù)據(jù)量，可以只將原作業(yè)的為了減少在主存和輔存間傳輸?shù)臄?shù)據(jù)量，可以只將原作業(yè)的一部分保存到輔存中去，只要釋放的主存空間剛好夠裝入下一部分保存到輔存中去，只要釋放的主存空間剛好夠裝入下一個運行作業(yè)就行。在以后的適當時間，作業(yè)移出的部分可一個運行作業(yè)就行。在以后的適當時間，

51、作業(yè)移出的部分可裝入到原來的存儲區(qū)中繼續(xù)運行下去。這種技術(shù)稱之為裝入到原來的存儲區(qū)中繼續(xù)運行下去。這種技術(shù)稱之為交換交換技術(shù)技術(shù)，也叫，也叫“滾進滾出滾進滾出”第二章 存 儲 管 理 52第二章 存 儲 管 理 53 優(yōu)點優(yōu)點： 增加并發(fā)運行的程序數(shù)目，并且給用戶提供適當增加并發(fā)運行的程序數(shù)目，并且給用戶提供適當?shù)捻憫?yīng)時間；的響應(yīng)時間； 編寫程序時不影響程序結(jié)構(gòu)編寫程序時不影響程序結(jié)構(gòu) 缺點缺點： 對換入和換出的控制增加處理機開銷；程序整個對換入和換出的控制增加處理機開銷；程序整個地址空間都進行傳送，地址空間都進行傳送， 沒有考慮執(zhí)行過程中地址訪問的統(tǒng)計特性。沒有考慮執(zhí)行過程中地址訪問的統(tǒng)計特

52、性。交換技術(shù)的優(yōu)缺點交換技術(shù)的優(yōu)缺點第二章 存 儲 管 理 54交換與覆蓋的比較交換與覆蓋的比較u與覆蓋技術(shù)相比，交換技術(shù)不要求用戶給出程與覆蓋技術(shù)相比，交換技術(shù)不要求用戶給出程序段之間的邏輯覆蓋結(jié)構(gòu)。序段之間的邏輯覆蓋結(jié)構(gòu)。u交換發(fā)生在進程或作業(yè)之間，而覆蓋發(fā)生在同交換發(fā)生在進程或作業(yè)之間，而覆蓋發(fā)生在同一進程或作業(yè)內(nèi)。一進程或作業(yè)內(nèi)。u覆蓋只能覆蓋那些與覆蓋段無關(guān)的程序段。覆蓋只能覆蓋那些與覆蓋段無關(guān)的程序段。第二章 存 儲 管 理 552.4.3 虛擬存儲器虛擬存儲器u在現(xiàn)代的計算機系統(tǒng)中，一個作業(yè)即使不全部裝入主在現(xiàn)代的計算機系統(tǒng)中，一個作業(yè)即使不全部裝入主存，也同樣能正確運行，因為：

53、存，也同樣能正確運行，因為：u 在一個程序中一般都有相當數(shù)量的出錯處理子程序，在一個程序中一般都有相當數(shù)量的出錯處理子程序，在正常的運行過程中很少執(zhí)行到這些程序；在正常的運行過程中很少執(zhí)行到這些程序；u 程序中一般都含有類似程序中一般都含有類似then和和else的彼此互斥的部分，的彼此互斥的部分，在程序的一次執(zhí)行中往往只選擇其中的一條路徑執(zhí)行；在程序的一次執(zhí)行中往往只選擇其中的一條路徑執(zhí)行；u 程序中的初始化部分一般只執(zhí)行一次，初始化工作程序中的初始化部分一般只執(zhí)行一次，初始化工作完成后，這些代碼就沒有存放在主存中的必要；完成后，這些代碼就沒有存放在主存中的必要；第二章 存 儲 管 理 56

54、2.4.3 虛擬存儲器虛擬存儲器u 從運行的時間角度來分析，在一段時間內(nèi)，作業(yè)一從運行的時間角度來分析，在一段時間內(nèi)，作業(yè)一般不會執(zhí)行到所有程序段的指令和存取絕大部分數(shù)據(jù)，般不會執(zhí)行到所有程序段的指令和存取絕大部分數(shù)據(jù)，它往往相對集中地訪問某些區(qū)域中的指令和數(shù)據(jù)，這它往往相對集中地訪問某些區(qū)域中的指令和數(shù)據(jù)，這就是程序運行的就是程序運行的“局部性原理局部性原理”。u在主存中可只裝入最近經(jīng)常要訪問的某些區(qū)域的指令在主存中可只裝入最近經(jīng)常要訪問的某些區(qū)域的指令和數(shù)據(jù)，剩余部分就暫時不必裝入，等到以后要訪問和數(shù)據(jù)，剩余部分就暫時不必裝入，等到以后要訪問到它們時再調(diào)入內(nèi)存。到它們時再調(diào)入內(nèi)存。u如果主

55、存較緊張，必要時可將已不大訪問的信息調(diào)出如果主存較緊張，必要時可將已不大訪問的信息調(diào)出內(nèi)存，再執(zhí)行調(diào)入操作。這樣，程序運行時所需要的內(nèi)存，再執(zhí)行調(diào)入操作。這樣，程序運行時所需要的實際內(nèi)存就可以遠小于程序的虛擬地址空間。實際內(nèi)存就可以遠小于程序的虛擬地址空間。第二章 存 儲 管 理 57u由于作業(yè)的指令和數(shù)據(jù)可以存放在外存中，用戶的程由于作業(yè)的指令和數(shù)據(jù)可以存放在外存中，用戶的程序就不受實際內(nèi)存大小的限制，好像計算機系統(tǒng)向用序就不受實際內(nèi)存大小的限制，好像計算機系統(tǒng)向用戶系統(tǒng)提供了容量極大的戶系統(tǒng)提供了容量極大的“主存主存”，而這個大容量的，而這個大容量的“主存主存”是靠存儲管理的軟件和硬件通過

56、大容量的輔是靠存儲管理的軟件和硬件通過大容量的輔存作為后援存儲器擴充而獲得的，是程序設(shè)計員感覺存作為后援存儲器擴充而獲得的，是程序設(shè)計員感覺到的，而實際上并不存在的存儲器，故稱到的，而實際上并不存在的存儲器，故稱虛擬存儲器虛擬存儲器。u采用虛擬存儲器技術(shù)究竟可運行多大的程序呢？當然采用虛擬存儲器技術(shù)究竟可運行多大的程序呢？當然也不能無限大，它受到以下兩個條件的限制。也不能無限大，它受到以下兩個條件的限制。第二章 存 儲 管 理 58u 指令地址字長的限制指令地址字長的限制。地址字長決定了程序所能訪問。地址字長決定了程序所能訪問的虛擬地址空間的大小，如對于的虛擬地址空間的大小，如對于32位字長的

57、地址字可構(gòu)位字長的地址字可構(gòu)成成4GB的虛擬地址空間。的虛擬地址空間。u 存放程序指令和數(shù)據(jù)的外存儲器的大小存放程序指令和數(shù)據(jù)的外存儲器的大小，這種外存叫，這種外存叫做交換設(shè)備，存放程序指令和數(shù)據(jù)的外存區(qū)域稱為做交換設(shè)備，存放程序指令和數(shù)據(jù)的外存區(qū)域稱為交換交換區(qū)區(qū)。u采用虛擬存儲管理策略，在作業(yè)運行時就要由地址映像采用虛擬存儲管理策略，在作業(yè)運行時就要由地址映像機構(gòu)將程序的邏輯地址轉(zhuǎn)換成內(nèi)存的物理地址。此外，機構(gòu)將程序的邏輯地址轉(zhuǎn)換成內(nèi)存的物理地址。此外，還要決定將虛擬地址空間中的哪一部分裝入主存，裝入還要決定將虛擬地址空間中的哪一部分裝入主存，裝入主存的位置以及當主存中的空閑區(qū)不夠時將哪一

58、部分空主存的位置以及當主存中的空閑區(qū)不夠時將哪一部分空間的內(nèi)容調(diào)至交換區(qū)中。這些都是虛擬存儲管理中要解間的內(nèi)容調(diào)至交換區(qū)中。這些都是虛擬存儲管理中要解決的新的技術(shù)問題。決的新的技術(shù)問題。第二章 存 儲 管 理 592.5 2.5 純分頁的存儲管理純分頁的存儲管理 可變分區(qū)存儲管理：連續(xù)分配存儲空間?？勺兎謪^(qū)存儲管理：連續(xù)分配存儲空間。分頁式存儲管理：打破了分頁式存儲管理：打破了“連續(xù)連續(xù)”的禁錮，把的禁錮，把對存儲的管理大大推進了一步。對存儲的管理大大推進了一步。分頁式存儲管理是將固定分區(qū)方法與動態(tài)重定分頁式存儲管理是將固定分區(qū)方法與動態(tài)重定位技術(shù)結(jié)合在一起的一種存儲管理方案，它需位技術(shù)結(jié)合在

59、一起的一種存儲管理方案，它需要硬件的支持。要硬件的支持。第二章 存 儲 管 理 602.5.1 分頁存儲管理的基本思想分頁存儲管理的基本思想u作業(yè)的虛擬地址空間劃分成若干長度相等的頁作業(yè)的虛擬地址空間劃分成若干長度相等的頁（page），也稱虛頁，每一個作業(yè)的虛頁都從），也稱虛頁，每一個作業(yè)的虛頁都從 0 開開始編號。始編號。u主存也劃分成若干與虛頁長度相等的頁架主存也劃分成若干與虛頁長度相等的頁架（frame），也稱頁框或?qū)嶍摚鞔娴捻摷芤矎模?，也稱頁框或?qū)嶍?，主存的頁架也?0開始編號。開始編號。u程序裝入時，每一個虛頁裝到主存中的一個頁架程序裝入時，每一個虛頁裝到主存中的一個頁架中，這些頁

60、架可以是不連續(xù)的中，這些頁架可以是不連續(xù)的。需要需要CPUCPU的硬件支的硬件支持持。第二章 存 儲 管 理 61例：第二章 存 儲 管 理 62 把用戶程序按邏輯頁劃分成大小相等的部把用戶程序按邏輯頁劃分成大小相等的部分，稱為頁。從分，稱為頁。從0 0開始編制頁號，頁內(nèi)地址是開始編制頁號，頁內(nèi)地址是相對于相對于0 0編址編址邏輯地址邏輯地址頁號頁號 頁內(nèi)地址頁內(nèi)地址用戶程序劃分用戶程序劃分例：頁的大小為例：頁的大小為4K4K相對地址相對地址51885188，對應(yīng)數(shù)對（，對應(yīng)數(shù)對（1 1，10921092）；）；相對地址相對地址92009200，對應(yīng)數(shù)對（，對應(yīng)數(shù)對（2 2，10081008）