1、第二章 存 儲 管 理 1第二章第二章 存儲管理存儲管理 2.1 2.1 存儲管理基礎存儲管理基礎 2.2 2.2 基本存儲管理方法基本存儲管理方法 2.3 2.3 可變分區存儲管理方法可變分區存儲管理方法 2.4 2.4 內存擴充技術內存擴充技術 2.5 2.5 純分頁的存儲管理純分頁的存儲管理 2.6 2.6 請求分頁系統請求分頁系統 2.7 2.7 段式存儲管理段式存儲管理 2.8 2.8 段頁式存儲管理段頁式存儲管理 2.9 Linux2.9 Linux存儲管理存儲管理第二章 存 儲 管 理 2存儲器可分為：內存儲器和外存儲器；存儲器可分為：內存儲器和外存儲器；內存儲器：可以被內存儲器

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

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

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

5、 而而CPUCPU執行指令時，是按物理地址進行執行指令時，是按物理地址進行的，所以要進行地址轉換。的，所以要進行地址轉換。第二章 存 儲 管 理 72.1.2 地址定位方式地址定位方式1. 固定定位方式固定定位方式 由程序員在編寫程序時或由編譯連接程序對源程序進由程序員在編寫程序時或由編譯連接程序對源程序進行編譯連接時，直接指定程序在執行時訪問的實際存儲器行編譯連接時，直接指定程序在執行時訪問的實際存儲器地址的方式稱為固定定位方式。此種定位方式一般只適合地址的方式稱為固定定位方式。此種定位方式一般只適合于單板機或單用戶系統。在多道程序環境下，應保證各個于單板機或單用戶系統。在多道程序環境下，應

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

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

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

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

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

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

12、特點特點（5）由于整個用戶區都分配給了一個用戶使用，因此作業由于整個用戶區都分配給了一個用戶使用，因此作業進入用戶區后，沒有移動的必要。采用這種存儲分配策進入用戶區后，沒有移動的必要。采用這種存儲分配策略時，將對用戶程序實行略時，將對用戶程序實行靜態重定位靜態重定位。（6）實行靜態重定位，并不能阻止用戶有意無意地通過不實行靜態重定位，并不能阻止用戶有意無意地通過不恰當地指令闖入操作系統所占用的存儲區域，如何阻止恰當地指令闖入操作系統所占用的存儲區域，如何阻止對操作系統的侵擾，就是所謂的對操作系統的侵擾，就是所謂的“存儲保護存儲保護”問題。問題。用于存儲保護的專用寄存器用于存儲保護的專用寄存器“

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

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

15、裝一個一個作業，分區作業，分區的劃分原則一般由系統操作員或操作系統決定，分區的劃分原則一般由系統操作員或操作系統決定，分區一旦劃分結束，在整個執行過程中每個分區的一旦劃分結束，在整個執行過程中每個分區的長度長度和和內存的總分區內存的總分區個數個數將將保持不變保持不變。 分區大小相等分區大小相等：只適合于多個相同程序的并發執行：只適合于多個相同程序的并發執行（處理多個類型相同的對象）。（處理多個類型相同的對象）。 分區大小不等：分區大小不等：多個小分區、適量的中等分區、少量多個小分區、適量的中等分區、少量的大分區。根據程序的大小，分配當前空閑的、適當的大分區。根據程序的大小，分配當前空閑的、適當

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

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

18、實行靜態重定位靜態重定位。 在固定分區存儲管理中，不僅要防止用戶程序對操作在固定分區存儲管理中，不僅要防止用戶程序對操作系統形成的侵擾，也要防止用戶程序與用戶程序之間系統形成的侵擾，也要防止用戶程序與用戶程序之間形成侵擾。因此必須在形成侵擾。因此必須在CPU中設置一對專用的寄存器，中設置一對專用的寄存器，用于存儲保護。將兩個專用寄存器分別起名為用于存儲保護。將兩個專用寄存器分別起名為“下下界界寄存器寄存器”和和“上界寄存器上界寄存器”第二章 存 儲 管 理 23存儲保護過程存儲保護過程 當進程調度程序調度某個作業進程運行時，就把該作當進程調度程序調度某個作業進程運行時，就把該作業所在分區的低邊

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

20、多道”色彩的存儲管理方色彩的存儲管理方案。案。 （2）當把一個分區分配給某個作業時，該作業的程序）當把一個分區分配給某個作業時，該作業的程序將一次性的全部被裝入到分配給它的連續分區里。將一次性的全部被裝入到分配給它的連續分區里。第二章 存 儲 管 理 25 優點：易于實現，開銷小。優點：易于實現，開銷小。 缺點：缺點： 內碎片造成浪費（小作業不能有效地利用分區空間。內碎片造成浪費（小作業不能有效地利用分區空間。 分區總數在系統生成時確定（固定），限制了并發分區總數在系統生成時確定（固定），限制了并發執行的程序數目。執行的程序數目。 如果到達作業的尺寸比任何一個分區的長度都大，如果到達作業的尺寸

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

22、 存 儲 管 理 27外部碎片問題外部碎片問題操作系統操作系統20KB0256KB作業作業A(16KB)A(16KB)空閑區空閑區(236KB)空閑區空閑區(220KB)作業作業B(100KB)B(100KB)空閑區空閑區(120KB)(120KB)作業作業C(70KB)C(70KB)空閑區空閑區(50KB)(50KB)空閑區空閑區(100KB)(100KB)作業作業D(75KB)D(75KB)空閑區空閑區(25KB)(25KB)第二章 存 儲 管 理 282.3.1 空閑存儲區表空閑存儲區表 管理空閑內存區的數據結構可采用鏈接法和連續線性表管理空閑內存區的數據結構可采用鏈接法和連續線性表格法

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

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

25、的區域，l存儲區表和實際存儲區表和實際的內存空間就可能的內存空間就可能變成如圖所示的情變成如圖所示的情況。況。第二章 存 儲 管 理 312.3.2 首次適應算法首次適應算法 1. 分配算法分配算法。u采用首次適應法為作業分配大小為采用首次適應法為作業分配大小為size的內存空間時，的內存空間時，總是從表的起始端的低地址部分開始查找。總是從表的起始端的低地址部分開始查找。u當第一次找到大于或等于申請大小的空閑區時，就按當第一次找到大于或等于申請大小的空閑區時，就按所需大小分配給作業。所需大小分配給作業。u如果分配后原空閑區還有剩余空間，就修改原存儲區如果分配后原空閑區還有剩余空間，就修改原存儲

26、區表項的表項的 m_size 和和 m_addr，使它記錄余下的，使它記錄余下的“零頭零頭”。u如果作業所需空間正好等于該空閑區大小，那么該空如果作業所需空間正好等于該空閑區大小，那么該空閑區表項的閑區表項的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當某一作業釋放以前所分配到的內存時，就要將該內當某一作業釋放以前所分配到的內存時，就要將該內存區歸還給系統，使其成為空閑區而可被其他作業使存區歸還給系統，使其成為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

43、空閑區修改有關的數修改有關的數據結構據結構無法分配無法分配返回返回否否否否是是是是第二章 存 儲 管 理 462.3.6 多重分區多重分區u有些系統采用多重分區技術，在作業的運行過程中有些系統采用多重分區技術，在作業的運行過程中可以申請附加的分區，以裝入一個或多個子程序。可以申請附加的分區，以裝入一個或多個子程序。新申請的空閑分區也無需與作業的現有分區相鄰接。新申請的空閑分區也無需與作業的現有分區相鄰接。u采用多重分區技術可以提高外部碎片的利用率，也采用多重分區技術可以提高外部碎片的利用率，也便于多個作業共享分區的代碼和數據，這只要在共便于多個作業共享分區的代碼和數據，這只要在共享的作業中包含

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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