1、NO：1 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理1. 存儲管理的功能及有關概念存儲管理的功能及有關概念 主存儲器主存儲器又稱內存，是計算機中最重要的資源，用戶的程又稱內存，是計算機中最重要的資源，用戶的程序和數據在運行時都要放在內存中，再由序和數據在運行時都要放在內存中，再由CPU訪問。訪問。 內存的容量是有限的，因此如何對內存進行管理和有效使內存的容量是有限的，因此如何對內存進行管理和有效使用是操作系統最重要的內容。用是操作系統最重要的內容。 存儲管理分為兩大類：存儲管理分為兩大類：實存儲管理實存儲管理和和虛擬存儲管理虛擬存儲管理。 實存管理實存管理：作業運行時整

2、個作業的地址空間必須全部作業運行時整個作業的地址空間必須全部裝入內存的一個連續空間。裝入內存的一個連續空間。 虛存管理虛存管理：用軟件辦法來擴充存儲器，提供給用戶一用軟件辦法來擴充存儲器，提供給用戶一個比實際內存大得多的存儲空間。個比實際內存大得多的存儲空間。NO：2 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理(1) (1) 存儲器的分級結構存儲器的分級結構高速緩沖存儲器（高速緩沖存儲器（cache）：又稱緩存，速度快、容量小、：又稱緩存，速度快、容量小、價格貴，用來存放使用最頻繁的信息，以及緩沖價格貴，用來存放使用最頻繁的信息，以及緩沖CPU與內與內存之間的速度差。存

3、之間的速度差。 主存儲器：主存儲器：又稱內存，是程序運行時存放系統和用戶的又稱內存，是程序運行時存放系統和用戶的指令及數據的設備。指令及數據的設備。 外部存儲器：外部存儲器：又稱外存，如硬盤、磁盤、光盤等；存取又稱外存，如硬盤、磁盤、光盤等；存取速度慢、容量大、價格便宜；可以存放大量的系統和用速度慢、容量大、價格便宜；可以存放大量的系統和用戶的程序及數據；不能由戶的程序及數據；不能由CPU直接讀取。直接讀取。NO：3 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理分級存儲機構示意圖分級存儲機構示意圖 外存外存主存主存程序和數據可以直程序和數據可以直接被接被CPU訪問訪問程序

4、和數據必須交換程序和數據必須交換到內存后才能被到內存后才能被CPU訪問訪問寄存器寄存器NO：4 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 存儲管理的功能主要分為存儲管理的功能主要分為內存分配內存分配、地址轉換地址轉換、存儲存儲保護保護和和內存擴充內存擴充四部分。四部分。 內存分配內存分配 內存分為內存分為系統區系統區和和用戶區用戶區兩大部分。由于多道程序出兩大部分。由于多道程序出現，內存中需要存放多個用戶作業，因此內存分配要解決如現，內存中需要存放多個用戶作業，因此內存分配要解決如何何合理分配內存空間合理分配內存空間以保證各作業以保證各作業互不沖突互不沖突，而且系統要

5、提，而且系統要提供適當的內存分配算法，提高內存的供適當的內存分配算法，提高內存的利用率利用率和和運行效率運行效率。NO：5 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 地址轉換或重定位地址轉換或重定位 地址空間地址空間 為了程序的獨立性，用戶編制的程序是由符號指令、數為了程序的獨立性，用戶編制的程序是由符號指令、數據說明和輸入輸出操作所組成的。我們把程序中的各種符號據說明和輸入輸出操作所組成的。我們把程序中的各種符號元素的集合所限定的空間叫做元素的集合所限定的空間叫做符號名字空間符號名字空間。 經編譯程序處理后，源程序中的各種符號元素轉換成機經編譯程序處理后，源程序中的

6、各種符號元素轉換成機器指令和數據組成的目標程序，并用實際地址碼替換符號地器指令和數據組成的目標程序，并用實際地址碼替換符號地址。經編譯后目標代碼所限定的地址叫做該程序址。經編譯后目標代碼所限定的地址叫做該程序地址空間地址空間。 地址空間中各個地址叫做地址空間中各個地址叫做相對地址相對地址或或邏輯地址邏輯地址，這是因，這是因為編譯程序對一個源程序編譯時，總是以為編譯程序對一個源程序編譯時，總是以0號單元作為參考號單元作為參考地址，其他所有的地址都是以地址，其他所有的地址都是以0號單元為起始地址順序編碼號單元為起始地址順序編碼 mov r1, 5000100500599123邏輯地址空間邏輯地址空

7、間mov r1, datadata123 名空間名空間NO：6 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 存儲空間存儲空間：內存中一系列存儲信息的物理單元的集合，：內存中一系列存儲信息的物理單元的集合，是由字或字節組成的一個大陣列，每個字或字節都有它自己是由字或字節組成的一個大陣列，每個字或字節都有它自己的編號地址，這些編號地址叫做的編號地址，這些編號地址叫做物理地址物理地址或或絕對地址絕對地址。mov r1, 500010050059912301000mov r1, 500123110015001599邏輯地址空間邏輯地址空間物理空間物理空間 例：例：在一個程序的地

8、址空間中在一個程序的地址空間中100號單元處有一條指令號單元處有一條指令 mov r1, 500。如果該程序僅僅是簡單裝入到內存。如果該程序僅僅是簡單裝入到內存10001599號單元，當執號單元，當執行到行到1100號單元中的指令時，則將號單元中的指令時，則將500號單元的內容送到號單元的內容送到1號寄存器，號寄存器，這顯然時錯誤的。必須修改這顯然時錯誤的。必須修改1100號單元指令中的地址部分，即把邏號單元指令中的地址部分，即把邏輯地址輯地址500改為絕對地址改為絕對地址1500。NO：7 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 重定位重定位 CPU執行用戶程序，

9、所要訪問的指令和數據必須執行用戶程序，所要訪問的指令和數據必須是實際的物理地址。因此必須把是實際的物理地址。因此必須把 邏輯地址邏輯地址 絕對地址絕對地址。這。這種使程序裝入到與其地址空間不一致的存儲空間所引起的，種使程序裝入到與其地址空間不一致的存儲空間所引起的，對有關地址部分的調整過程稱為對有關地址部分的調整過程稱為 地址重定位地址重定位。重定位的方式有重定位的方式有靜態重定位靜態重定位和和動態重定位動態重定位兩種。兩種。 靜態重定位靜態重定位：在程序裝入時進行，由：在程序裝入時進行，由裝入程序裝入程序把用戶程序把用戶程序中的指令地址和數據地址全部轉換成存儲空間的絕對地址。中的指令地址和數

10、據地址全部轉換成存儲空間的絕對地址。 地址轉換工作在程序執行前一次性完成，在程序執行時就地址轉換工作在程序執行前一次性完成，在程序執行時就無須再進行地址轉換工作。無須再進行地址轉換工作。NO：8 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理mov r1, 50001005005991230BRBRmov r1, BR+500123BR+100BR+500BR+599靜態重定位過程靜態重定位過程重定位裝入程重定位裝入程序序 假定程序裝入內存的首地址為假定程序裝入內存的首地址為BRBR，程序地址為程序地址為VRVR，內內存地址為存地址為MRMR，則地址映射按下式進行：則地址映

11、射按下式進行：MR=BR+VR MR=BR+VR 。NO：9 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理靜態地址重定位優缺點：靜態地址重定位優缺點： 優點：優點： a) 無需增加硬件地址變換機構，可在一般機器上實現；無需增加硬件地址變換機構，可在一般機器上實現； b) 利用重定位裝入程序即可對若干程序段進行靜態鏈接，利用重定位裝入程序即可對若干程序段進行靜態鏈接， 實現起來比較簡單。實現起來比較簡單。 缺點：缺點： a) 要求分配一片連續的存儲空間，且在執行期間必須限定要求分配一片連續的存儲空間，且在執行期間必須限定在這個區域內。就是說程序運行期間不能移動，因而不能實在

12、這個區域內。就是說程序運行期間不能移動，因而不能實現重新分配主存，對提高主存利用率不利現重新分配主存，對提高主存利用率不利 b) 用戶必須事先確定所需的存儲量用戶必須事先確定所需的存儲量NO：10 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 動態重定位：動態重定位：在程序在程序執行過程中執行過程中進行，當進行，當CPU訪問內存訪問內存指令時由指令時由硬件的地址轉換機構硬件的地址轉換機構實現。通常的辦法是設置一個實現。通常的辦法是設置一個重定位寄存器重定位寄存器。在存儲管理為程序分配一個主存區域后，裝。在存儲管理為程序分配一個主存區域后，裝入程序直接把程序和數據裝入到分配

13、的存儲區中，然后把這入程序直接把程序和數據裝入到分配的存儲區中，然后把這個存儲區的個存儲區的起始地址起始地址送入重定位寄存器中。在程序執行時，送入重定位寄存器中。在程序執行時，對于每一個存儲區的訪問，都要將相對地址轉換成主存的絕對于每一個存儲區的訪問，都要將相對地址轉換成主存的絕對地址。由于這種定位方式是在指令執行過程中進行的，所對地址。由于這種定位方式是在指令執行過程中進行的，所以叫做以叫做動態重定位動態重定位。NO：11 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理mov r1, 500010050059912301000mov r1, m+5001231100150

14、01599+1000重定位寄存器重定位寄存器相對地址相對地址絕對地址絕對地址動態重定位過程動態重定位過程上述的地址轉換是動態的，即每執行一條指令，就進行一次上述的地址轉換是動態的，即每執行一條指令，就進行一次地址轉換。程序運行過程中要執行多少條指令，系統就要進地址轉換。程序運行過程中要執行多少條指令，系統就要進行多少次地址轉換。行多少次地址轉換。NO：12 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理動態地址重定位優點動態地址重定位優點：a) 主存使用更加靈活、有效，用戶程序不一定要分配在一片主存使用更加靈活、有效，用戶程序不一定要分配在一片連續的存儲區內，對應每一個存儲

15、空間重新設置相應的重定連續的存儲區內，對應每一個存儲空間重新設置相應的重定位寄存器即可；位寄存器即可；b) 可能向用戶提供一個比主存空間大得多的地址空間，并無可能向用戶提供一個比主存空間大得多的地址空間，并無需由用戶來考慮覆蓋，而由系統來負責全部的存儲管理。需由用戶來考慮覆蓋，而由系統來負責全部的存儲管理。c) 便于多用戶共享存儲器中的同一程序便于多用戶共享存儲器中的同一程序 即使動態重定位需要額外的硬件支持，增加系統的成本，即使動態重定位需要額外的硬件支持，增加系統的成本，且實現存儲管理的算法也比較復雜，但現代計算機系統都廣且實現存儲管理的算法也比較復雜，但現代計算機系統都廣泛采用了這一技術

16、。泛采用了這一技術。NO：13 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 3) 存儲保護：存儲保護： 確保多道程序都在各自分配到存儲區域內操作，互不確保多道程序都在各自分配到存儲區域內操作，互不干擾，防止一道程序破壞其它作業或系統文件的信息。干擾，防止一道程序破壞其它作業或系統文件的信息。 主要包含二部分內容：主要包含二部分內容：1) 防止地址越界防止地址越界; 2) 防止操作防止操作越權越權。存儲保護只能在進程執行過程中動態的進行。存儲保護只能在進程執行過程中動態的進行。 4) 內存擴充：內存擴充： 當作業的當作業的地址空間地址空間大于大于分配到的分配到的存儲空間存

17、儲空間時需采取內時需采取內存擴充技術，將內外存聯合起來擴大存儲空間，常采用存擴充技術，將內外存聯合起來擴大存儲空間，常采用的內存擴充技術有的內存擴充技術有覆蓋覆蓋、交換交換和和虛擬存儲虛擬存儲技術。技術。NO：14 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理2. 實存儲管理實存儲管理(1) 分區分配分區分配(2) 可重定位分區分配可重定位分區分配(3) 覆蓋技術覆蓋技術(4) 交換技術交換技術 實存儲管理的特點是當作業要求調入內存時，存儲管實存儲管理的特點是當作業要求調入內存時，存儲管理要提供一個理要提供一個不小于不小于作業地址空間的連續存儲空間，當空作業地址空間的連續

18、存儲空間，當空間間不夠時不夠時，常采用，常采用覆蓋覆蓋或或交換交換技術來擴充內存。技術來擴充內存。 幾種常用的實存儲管理方法：幾種常用的實存儲管理方法：NO：15 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理(1) 分區分配分區分配 分區分配是滿足多道程序的最簡單的存儲管理方案。它分區分配是滿足多道程序的最簡單的存儲管理方案。它的基本思想是將內存劃分成若干個連續區域，稱為分區。每的基本思想是將內存劃分成若干個連續區域，稱為分區。每個分區分配給一個作業，用個分區分配給一個作業，用靜態重定位靜態重定位方式進行地址轉換，方式進行地址轉換，提供必要的保護手段，保證各作業互不干擾。

19、在分區的劃分提供必要的保護手段，保證各作業互不干擾。在分區的劃分方式上有方式上有固定分區固定分區和和可變分區可變分區兩種。兩種。 a) 固定分區分配固定分區分配：存儲器事先被劃分為若干個：存儲器事先被劃分為若干個大小不大小不等等的分區，系統為每個分區設置一個目錄，說明該分區的大的分區，系統為每個分區設置一個目錄，說明該分區的大小、起始位置、分配狀況等信息，所有分區目錄構成一個小、起始位置、分配狀況等信息，所有分區目錄構成一個內內存狀態表存狀態表；用戶為每個作業規定所需的最大存儲量，存儲管；用戶為每個作業規定所需的最大存儲量，存儲管理程序負責找出一個足夠大的分區分配給此作業。理程序負責找出一個足

20、夠大的分區分配給此作業。NO：16 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理：分區的分配和回收算法簡單；：分區的分配和回收算法簡單； 缺點缺點: 內存利用不充足，有內存利用不充足，有“碎片碎片”，即作業所需空間和，即作業所需空間和分區大小不一定恰好相等。分區大小不一定恰好相等。區號區號容量容量起始位置起始位置狀態狀態18kB312kB已分配已分配232kB320kB已分配已分配332kB352kB未未 用用4120kB384kB未未 用用5520kB504kB已分配已分配O S8kB32kB32kB120kB520kB312kB320kB352kB384kB504kB

21、1024kBNO：17 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理b) 可變分區分配：可變分區分配：又稱又稱動態存儲管理動態存儲管理，內存不是預先劃分，內存不是預先劃分好的，而是當作業裝入時，根據作業的需求和內存空間的使好的，而是當作業裝入時，根據作業的需求和內存空間的使用情況來決定是否分配。若有足夠的空間，則按需要分割一用情況來決定是否分配。若有足夠的空間，則按需要分割一部分分區給該進程；否則令其等待主存空間。當作業執行完部分分區給該進程；否則令其等待主存空間。當作業執行完后又釋放此空間。采用鏈結構來構造分區目錄。后又釋放此空間。采用鏈結構來構造分區目錄。 空間分配：

22、空間分配：由于多作業調入內存運行，有些作業運行結由于多作業調入內存運行，有些作業運行結束后釋放所占空間，內存區呈現占用塊與空閑塊交叉存在的束后釋放所占空間，內存區呈現占用塊與空閑塊交叉存在的狀態。狀態。 P8P6P4P3P1 占用塊占用塊空閑塊空閑塊 如果此時又有用戶作業進入系統，在系統必須在現有如果此時又有用戶作業進入系統，在系統必須在現有的空閑塊中為新作業分配空間。的空閑塊中為新作業分配空間。NO：18 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理L linktagsizeR linktagUp linkL link和和 R link為鏈表左右指針，為鏈表左右指針，

23、tag=0表示空閑塊，表示空閑塊， tag=1表表示占用塊，示占用塊， size 是本塊的大小，是本塊的大小，Up link 為本塊的起始地址為本塊的起始地址 當空閑區分配出去以后，把狀態位當空閑區分配出去以后，把狀態位tag由由“0”改為改為1，此，此時鏈表左右指針已無意義。時鏈表左右指針已無意義。 為了對空閑塊進行有效的管理，在每塊開始與結束的幾為了對空閑塊進行有效的管理，在每塊開始與結束的幾個字節中存放有關本塊狀態的信息，稱為個字節中存放有關本塊狀態的信息，稱為控制信息區控制信息區，并把，并把所有的空閑塊鏈成一個雙向鏈表所有的空閑塊鏈成一個雙向鏈表NO：19 第四章第四章 操作系統操作系

24、統4.3 4.3 存儲器管理存儲器管理例：設某系統用戶區大小為例：設某系統用戶區大小為5000字節，地址為字節，地址為1 5000，初，初始狀態如下圖始狀態如下圖a所示，依次分配給所示，依次分配給5個作業個作業P1 P5, 作業占用作業占用區大小分別為區大小分別為1000，300，600，900，700。 P0 為余下的空閑為余下的空閑塊，各占用塊和空閑塊情況如下頁圖塊，各占用塊和空閑塊情況如下頁圖b和和c所示。所示。P1P2P3P4P5P01000 3006009007001500圖圖 aNO：20 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理NO：21 第四章第四章

25、操作系統操作系統4.3 4.3 存儲器管理存儲器管理右鄰居左鄰居P-1 PP+nn 空間回收空間回收 當作業執行完畢后，系統將空間當作業執行完畢后，系統將空間收回收回，插入到，插入到空空閑塊鏈表閑塊鏈表中，但插入時還要判斷中，但插入時還要判斷左右相鄰塊左右相鄰塊是否空閑，若是則是否空閑，若是則合并成一個較大的空間，它可通過每一塊中頭尾的控制信息區合并成一個較大的空間，它可通過每一塊中頭尾的控制信息區的的tag標志來判斷。設當前回收塊起始地址為標志來判斷。設當前回收塊起始地址為p,大小為大小為n,則應判則應判斷它左鄰居斷它左鄰居p-1和右鄰居和右鄰居p+n的的tag是否為是否為0，若不為，若不為

26、0則將當前回則將當前回收塊插入到空閑塊鏈表中。若出現有收塊插入到空閑塊鏈表中。若出現有tag為為0的相鄰塊，則應修的相鄰塊，則應修改原空閑塊的大小，將本回收塊和相鄰塊合并。如下圖。改原空閑塊的大小，將本回收塊和相鄰塊合并。如下圖。NO：22 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理在空間分配例題中，當作業在空間分配例題中，當作業P4完成后，應回收完成后，應回收P4分區到空閑塊分區到空閑塊鏈表中，見圖鏈表中，見圖a；當；當P5作業完成后，回收使由于其左右鄰居均作業完成后，回收使由于其左右鄰居均為空閑塊，因此應進行合并，見圖為空閑塊，因此應進行合并，見圖b所示。所示。NO

27、：23 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理空閑區分配算法：空閑區分配算法：由于空閑鏈表中各空閑塊的大小不同，由于空閑鏈表中各空閑塊的大小不同，在分配是有一個在分配是有一個如何分配如何分配的問題。通常有三種分配策略。的問題。通常有三種分配策略。 首次適應法首次適應法: 從空閑塊鏈表的表頭指針從空閑塊鏈表的表頭指針av開始，將找到開始，將找到的第一個大小的第一個大小不小于不小于所需大小所需大小n的空閑塊，將其一部分分配給的空閑塊，將其一部分分配給用戶。這種空閑塊鏈表既不按結點的初始地址有序排列，也用戶。這種空閑塊鏈表既不按結點的初始地址有序排列，也不按結點大小有序排

28、列，在回收時，只要將釋放的空閑塊插不按結點大小有序排列，在回收時，只要將釋放的空閑塊插入到鏈表的表頭即可。入到鏈表的表頭即可。 最佳適應法：最佳適應法：將空閑塊鏈表中一個不小于將空閑塊鏈表中一個不小于n而最接近而最接近n的的空閑塊的一部分分配給用戶。要求系統在內存分配前首先將空閑塊的一部分分配給用戶。要求系統在內存分配前首先將空閑塊鏈表中的結點按空閑塊大小空閑塊鏈表中的結點按空閑塊大小自小到大有序排列自小到大有序排列。 NO：24 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 最差適應法最差適應法：將空閑塊鏈表中：將空閑塊鏈表中不小于不小于n且且是鏈表中是鏈表中最大最大空

29、空閑塊的一部分分配給用戶，并將剩余部分作為一個新結點插閑塊的一部分分配給用戶，并將剩余部分作為一個新結點插入到鏈表的相應位置。要求空閑塊鏈表的結點按空閑塊大小入到鏈表的相應位置。要求空閑塊鏈表的結點按空閑塊大小由大到小由大到小排列，每次分配從鏈表中刪除第一個結點，將其一排列，每次分配從鏈表中刪除第一個結點，將其一部分分配給用戶，剩余部分作為一個新結點插入到鏈表的相部分分配給用戶，剩余部分作為一個新結點插入到鏈表的相應位置。應位置。NO：25 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 最佳適應法最佳適應法適用于請求分配內存大小范圍較廣的系統；適用于請求分配內存大小范圍較

30、廣的系統；最差適最差適應算法應算法每次都從內存中取最大的結點進行分配，從而使鏈表中每次都從內存中取最大的結點進行分配，從而使鏈表中結點大小趨于均勻，適用于請求分配內存較均勻的系統；結點大小趨于均勻，適用于請求分配內存較均勻的系統；首次首次適應法適應法通常適用于實現不能掌握運行時可能出現的分配情況。通常適用于實現不能掌握運行時可能出現的分配情況。 從從時間時間上比較，上比較，首次適應法首次適應法分配時需查詢空閑塊鏈表，但分配時需查詢空閑塊鏈表，但回收時只要插入到表頭即可；回收時只要插入到表頭即可；最差適應算法最差適應算法分配時不需查詢鏈分配時不需查詢鏈表，而回收時要將剩余部分插入鏈表適當位置；表

31、，而回收時要將剩余部分插入鏈表適當位置；最佳適應法最佳適應法無無論分配和回收，均需查找鏈表，最費時間。論分配和回收，均需查找鏈表，最費時間。NO：26 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理(2) 可重定位分區分配可重定位分區分配 a) 碎片問題和存儲區的緊縮碎片問題和存儲區的緊縮：在可變分區分配中，內存區：在可變分區分配中，內存區由于各作業的多次請求和釋放出現大量的由于各作業的多次請求和釋放出現大量的碎片碎片，浪費了，浪費了大量的內存空間。為了把分散的碎片集中起來成為一個大量的內存空間。為了把分散的碎片集中起來成為一個大分區，需大分區，需移動移動各用戶程序，使它們

32、集中在主存的一端，各用戶程序，使它們集中在主存的一端，稱為存儲器的稱為存儲器的“緊縮緊縮”。 b) 程序浮動和重定位程序浮動和重定位：將主存中用戶程序進行移動稱為：將主存中用戶程序進行移動稱為程序浮動程序浮動；程序浮動需對程序中所有與地址有關的項重；程序浮動需對程序中所有與地址有關的項重新進行定位，此工作是在程序運行過程中進行的，也就新進行定位，此工作是在程序運行過程中進行的，也就是在是在CPU每次訪問內存單元前進行的，又稱每次訪問內存單元前進行的，又稱動態重定位動態重定位。經過一段時間的分配回收后，內存中存經過一段時間的分配回收后，內存中存在很多很小的空閑塊。它們每一個都很在很多很小的空閑塊

33、。它們每一個都很小，不足以滿足分配要求；但其總和滿小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為足分配要求。這些空閑塊被稱為碎片碎片。NO：27 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理動態重定位實現過程：動態重定位實現過程： 先將用戶作業的目標程序先將用戶作業的目標程序原封不動原封不動的裝入主存某一分區，的裝入主存某一分區，即用戶程序中與地址有關的各項均保持原來的即用戶程序中與地址有關的各項均保持原來的相對地址相對地址，例如，例如下頁圖下頁圖 b中中 Load 1,1000 指令（指令（1000為相對地址）。為相對地址）。 當該用戶程序被調度到處理器

34、上執行時，操作系統自動當該用戶程序被調度到處理器上執行時，操作系統自動將該用戶將該用戶作業區的起始地址作業區的起始地址（圖（圖b中的中的10023）減去用戶目標程）減去用戶目標程序的相對起始地址（圖序的相對起始地址（圖a 為為0），然后將減得的值裝入定位寄），然后將減得的值裝入定位寄存器中。存器中。 當處理器要訪問主存時，操作系統將程序中的當處理器要訪問主存時，操作系統將程序中的相對地相對地址址與與定位寄存器定位寄存器中的內容相加，得到主存的絕對地址去訪問數中的內容相加，得到主存的絕對地址去訪問數據，如圖據，如圖b中絕對地址為中絕對地址為11023。NO：28 第四章第四章 操作系統操作系統4

35、.3 4.3 存儲器管理存儲器管理NO：29 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 動態重定位時程序在內存中任意浮動而不影響其正確的動態重定位時程序在內存中任意浮動而不影響其正確的執行，容易進行存儲器緊縮；但需硬件支持，包括定位寄存執行，容易進行存儲器緊縮；但需硬件支持，包括定位寄存器、加法器等。器、加法器等。存儲器緊縮的兩種解決方法存儲器緊縮的兩種解決方法： 在某個分區釋放后在某個分區釋放后立即緊縮立即緊縮，這樣系統中始終存在一個，這樣系統中始終存在一個連續的自由分區而無碎片。這對于分區的連續的自由分區而無碎片。這對于分區的分配分配管理十分管理十分容易容易，但緊

36、縮工作進行頻繁，花費時間較多。但緊縮工作進行頻繁，花費時間較多。 在請求分配分區在請求分配分區找不到找不到足夠大的自由分區時再進行緊縮。足夠大的自由分區時再進行緊縮。這樣緊縮的次數大大減少，但分配管理較復雜。這樣緊縮的次數大大減少，但分配管理較復雜。NO：30 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理(3) 覆蓋技術覆蓋技術 當用戶作業的地址空間大于主存可用空間時，各作業就當用戶作業的地址空間大于主存可用空間時，各作業就無法運行。為了能在較小的空間中運行較大的作業，許多機無法運行。為了能在較小的空間中運行較大的作業，許多機器采用了器采用了覆蓋技術覆蓋技術。 要進行覆蓋

37、的作業必須滿足要進行覆蓋的作業必須滿足樹狀樹狀的模塊結構，如圖的模塊結構，如圖a所示，所示，其中其中根部根部為為常駐內存常駐內存部分，稱為根段，其余部分均為部分，稱為根段，其余部分均為覆蓋部覆蓋部分分，同層模塊為一個覆蓋段，在，同層模塊為一個覆蓋段，在同一時間同一時間只有只有其中一個其中一個模塊模塊被調用，因此它們可以共享一個內存空間，其大小按本覆蓋被調用，因此它們可以共享一個內存空間，其大小按本覆蓋段中最大的模塊分配。如圖段中最大的模塊分配。如圖b所示所示NO：31 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理NO：32 第四章第四章 操作系統操作系統4.3 4.3 存

38、儲器管理存儲器管理(4) 交換技術交換技術 交換技術交換技術同樣是為了解決同樣是為了解決內存不足內存不足的矛盾，它在分時、實的矛盾，它在分時、實時及批處理系統中均有應用。它的基本思想是只允許一個或時及批處理系統中均有應用。它的基本思想是只允許一個或幾個用戶作業保留在主存中。作業在出讓幾個用戶作業保留在主存中。作業在出讓CPU的同時還要釋的同時還要釋放出占有的主存空間，以文件形式保存在外存上。放出占有的主存空間，以文件形式保存在外存上。 覆蓋和交換技術作為擴充內存的方法，通常與分區分配方覆蓋和交換技術作為擴充內存的方法，通常與分區分配方法結合使用。但仍存在不足，例如覆蓋技術要求用戶按模塊法結合使

39、用。但仍存在不足，例如覆蓋技術要求用戶按模塊化結構編制程序，并要寫出覆蓋文件；交換技術是以整個作化結構編制程序，并要寫出覆蓋文件；交換技術是以整個作業為單位進行內外存交換，當作業較大時花費的代價較大。業為單位進行內外存交換，當作業較大時花費的代價較大。由此引發了由此引發了虛擬存儲技術虛擬存儲技術的出現。的出現。NO：33 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理3 虛擬存儲管理虛擬存儲管理 在前述的各種分區管理技術中，其共同的特點是作業在前述的各種分區管理技術中，其共同的特點是作業運行時整個作業的地址空間必須運行時整個作業的地址空間必須全部裝入全部裝入內存的一個連續空

40、內存的一個連續空間中，反之作業就無法運行。這類存儲管理技術統稱為間中，反之作業就無法運行。這類存儲管理技術統稱為“實實存存”。 “虛存虛存”（虛擬存儲管理）（虛擬存儲管理）技術是用技術是用軟件方法軟件方法來擴充來擴充存儲器，虛擬存儲器的概念是指一種存儲器，虛擬存儲器的概念是指一種實際上并不存在實際上并不存在的虛假的虛假存儲器，它能提供給用戶一個存儲器，它能提供給用戶一個比實際內存大的多比實際內存大的多的存儲空間，的存儲空間，使用戶在編制程序時可以不必考慮存儲空間的限制。使用戶在編制程序時可以不必考慮存儲空間的限制。NO：34 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理基

41、本概念：基本概念： 虛擬地址虛擬地址：程序訪問的邏輯地址。：程序訪問的邏輯地址。 實在地址實在地址：處理器可直接訪問的主存地址。：處理器可直接訪問的主存地址。 虛擬地址空間虛擬地址空間：虛擬地址的集合。：虛擬地址的集合。 實在地址空間實在地址空間：計算機主存。：計算機主存。注：注： 程序和數據所在的虛擬地址必須放入主存的實在地程序和數據所在的虛擬地址必須放入主存的實在地址中才能運行。因此要建立虛擬地址和實在地址的對址中才能運行。因此要建立虛擬地址和實在地址的對應關系，這種地址轉換由應關系，這種地址轉換由動態地址映像機構動態地址映像機構來完成。來完成。NO：35 第四章第四章 操作系統操作系統4

42、.3 4.3 存儲器管理存儲器管理虛擬的前提虛擬的前提 大多數程序運行時，在大多數程序運行時，在一段時間一段時間內僅使用它的程序編碼的內僅使用它的程序編碼的一部分一部分，即并不需要在全部時間內將該程序的全部指令和數據，即并不需要在全部時間內將該程序的全部指令和數據都放在主存中，所以，程序的地址空間都放在主存中，所以，程序的地址空間部分裝入部分裝入主存中，它還主存中，它還是能正確運行。是能正確運行。 那么當一個作業程序的地址空間比主存可用空間大時，操那么當一個作業程序的地址空間比主存可用空間大時，操作系統可將這個程序的地址空間的一部分放入內存，作系統可將這個程序的地址空間的一部分放入內存，其余其

43、余部分部分放在放在輔存輔存中。當所訪問的信息不在主存時，再由操作系統負責中。當所訪問的信息不在主存時，再由操作系統負責調入所需要的部分。這樣計算機系統好像為用戶提供了一個其調入所需要的部分。這樣計算機系統好像為用戶提供了一個其存儲容量比實際主存大得多的存儲器。存儲容量比實際主存大得多的存儲器。 NO：36 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理實際上用戶的虛擬地址空間并不可能是無限大，它受到實際上用戶的虛擬地址空間并不可能是無限大，它受到以下以下兩個條件兩個條件制約：制約： 1. 指令中指令中地址場長度地址場長度的限制。的限制。 2. 外存儲器外存儲器容量的限制容量

44、的限制。虛擬存儲管理技術需要解決的問題：虛擬存儲管理技術需要解決的問題： （1）什么時候什么時候把哪部分程序把哪部分程序裝入裝入內存。內存。 （2）放在內存）放在內存什么位置什么位置。 （3）當內存空間不足時，把哪部分程序）當內存空間不足時，把哪部分程序淘汰淘汰出內存。出內存。常用的虛擬存儲技術有：常用的虛擬存儲技術有：分頁存儲管理分頁存儲管理、分段存儲管理分段存儲管理、段頁存儲管理段頁存儲管理。NO：37 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理(1) 分頁存儲管理分頁存儲管理 在分區存儲管理中，不論采用什么辦法都會出現碎片問題在分區存儲管理中，不論采用什么辦法都會

45、出現碎片問題，從而降低了內存的利用率。雖然采用壓縮存儲區的方法可，從而降低了內存的利用率。雖然采用壓縮存儲區的方法可以解決碎片問題，但系統開銷太大，而無實用價值，必須尋以解決碎片問題，但系統開銷太大，而無實用價值，必須尋求新的技術來解決這一問題，于是分頁技術產生了。求新的技術來解決這一問題，于是分頁技術產生了。NO：38 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理a) 分頁管理的基本概念分頁管理的基本概念 頁面、頁架（塊）頁面、頁架（塊） 在分頁存儲管理中，把每個作業的地址空間分成一些在分頁存儲管理中，把每個作業的地址空間分成一些大大小相等小相等的片，稱為的片，稱為“頁

46、頁”。同樣，把內存的。同樣，把內存的存儲空間存儲空間也分成也分成大小與頁相同的片，稱為大小與頁相同的片，稱為“頁架頁架”或者或者“塊塊”。系統以。系統以頁架頁架為單位為單位把內存分配給各作業，每個作業占有的內存無須連續，把內存分配給各作業，每個作業占有的內存無須連續，而且作業的所有頁面也不一定同時裝入內存。而且作業的所有頁面也不一定同時裝入內存。NO：39 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 假設系統選擇假設系統選擇頁頁的的大小大小為為1k字節字節，則一個，則一個3k字節的作字節的作業業將被劃分為將被劃分為3頁頁。此時主存有。此時主存有5個空白塊個空白塊（塊（塊

47、2、3、8、9、11）。因此，當作業的三塊裝入內存時可以選擇任意）。因此，當作業的三塊裝入內存時可以選擇任意3個空個空白塊。圖中假定第白塊。圖中假定第0頁裝入主存的塊頁裝入主存的塊2中，第中，第1頁裝入塊頁裝入塊3中，中，第第2 頁裝入塊頁裝入塊8中（主存中塊中（主存中塊9和塊和塊11空閑）?？臻e）。NO：40 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理NO：41 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 分頁系統中的地址結構分頁系統中的地址結構 在分頁系統中，每個虛擬地址用一個數對在分頁系統中，每個虛擬地址用一個數對（p,d）來表示，來表示，

48、其中其中p為為頁號頁號，d是該虛擬地址在頁面號為是該虛擬地址在頁面號為p中的中的相對地址相對地址，稱，稱為頁內地址。為計算方便，規定頁的大小為為頁內地址。為計算方便，規定頁的大小為2的冪的冪。 對某特定機器，其地址結構是一定的。若給定一個邏對某特定機器，其地址結構是一定的。若給定一個邏輯地址空間中的地址為輯地址空間中的地址為A，頁面的大小為，頁面的大小為L，則頁號，則頁號P和頁和頁內地址內地址d可按下式求得：可按下式求得： APINTLdA MOD L頁號頁號 頁內地址頁內地址NO：42 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理規定頁的大小為規定頁的大小為2的冪的冪

49、如果每訪問一個主存單元都要做一次除法運算以得到頁號如果每訪問一個主存單元都要做一次除法運算以得到頁號p和頁內地址和頁內地址d，效率太低。，效率太低。 當頁大小為當頁大小為2的冪后，可用簡單的右移來代替除法，使算的冪后，可用簡單的右移來代替除法，使算法簡化。法簡化。 例如：頁大小為例如：頁大小為1KB，則邏輯地址，則邏輯地址 0 x23A1的頁號和頁內的頁號和頁內地址為：地址為： 0010 00 | 11 1010 0001 0010 00 | 11 1010 0001 p dp d 頁號頁號 p = 0 x8p = 0 x8， 頁內地址頁內地址 d = 0 x3A1d = 0 x3A1NO：4

50、3 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理頁表與頁表地址寄存器頁表與頁表地址寄存器 頁表頁表：將頁號和頁內地址轉換成內存地址，必須要有一個：將頁號和頁內地址轉換成內存地址，必須要有一個數據結構，用來登記頁號和頁架號的對應關系和有關信息，數據結構，用來登記頁號和頁架號的對應關系和有關信息，稱為稱為“頁表頁表” 。頁表中應包括：。頁表中應包括：頁號頁號、頁架號頁架號、狀態狀態。 頁號頁號：登記程序地址空間的頁號，每個作業頁號從零開始。：登記程序地址空間的頁號，每個作業頁號從零開始。 頁架號頁架號：該頁面在內存中的頁架號。：該頁面在內存中的頁架號。 狀態狀態：表示該頁是否

51、在內存中，用：表示該頁是否在內存中，用“0”表示該頁不在內存，表示該頁不在內存，用用“1”表示在內存中。表示在內存中。NO：44 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 當某進程被調度到處理器上運行時，操作系統自動將當某進程被調度到處理器上運行時，操作系統自動將該進程的頁表起始地址（通常位于該進程的該進程的頁表起始地址（通常位于該進程的PCB中）裝入中）裝入頁頁表地址寄存器表地址寄存器中，當中，當CPU執行一條訪問內存指令時，執行一條訪問內存指令時，地址變地址變換機構換機構把邏輯地址分解成把邏輯地址分解成 p 和和 d 兩部分，兩部分， p為為頁號頁號，d為為頁頁內

52、地址內地址。按照。按照p在頁表中找到相應的頁架號和狀態，在頁表中找到相應的頁架號和狀態，若狀態若狀態為為“1”，將頁架號與頁內地址合并為內存實在地址。將頁架號與頁內地址合并為內存實在地址。若狀態若狀態為為“0”，表明此頁不在內存中，系統將產生中斷，停止執行表明此頁不在內存中，系統將產生中斷，停止執行用戶程序，由存儲管理模塊將該頁調入內存。用戶程序，由存儲管理模塊將該頁調入內存。NO：45 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理例：設頁長為例：設頁長為1 1K K，程序地址字長為程序地址字長為1616位，用戶程序空間和頁表如圖。位，用戶程序空間和頁表如圖。NO：46

53、第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理計算時要注意：計算時要注意： 若給出的地址字為若給出的地址字為16進制進制，則將其轉換為二進制，然，則將其轉換為二進制，然后，根據頁長及程序地址字的長度，分別取出程序地址字的后，根據頁長及程序地址字的長度，分別取出程序地址字的高幾位和低幾位就得到頁號及頁內地址。如頁長為高幾位和低幾位就得到頁號及頁內地址。如頁長為2K，程程序地址字為序地址字為16位，則高位，則高5位為頁號，低位為頁號，低11位為頁內地址。位為頁內地址。 若給出的地址字為若給出的地址字為10進制進制，則用公式：，則用公式： 程序地址字程序地址字/頁長頁長 商為頁號

54、，余數為頁內地址。商為頁號，余數為頁內地址。 如程序地址為如程序地址為8457， 頁長為頁長為4KB，則則8457/4096可得：可得：商為商為2，余數為，余數為256。NO：47 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 例，假如某系統頁面大小為（例，假如某系統頁面大小為（512)10字節，即相當于字節，即相當于（1000)8字節，若邏輯地址為字節，若邏輯地址為（1320)8，就可以方便的分，就可以方便的分解得到解得到p=1, d=320. 由由p及頁表起始地址及頁表起始地址b，找到相應的頁，找到相應的頁，將該頁對應的將該頁對應的頁架號頁架號10送入地址變換機構送入

55、地址變換機構p, 與頁內地址與頁內地址d合并合并成內存實在地址號成內存實在地址號10320。NO：48 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理NO：49 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 上述是上述是直接映象直接映象的頁地址轉換，由于的頁地址轉換，由于CPU要訪問二次要訪問二次主存才能存取到所需數據，缺點是主存才能存取到所需數據，缺點是速度速度慢。慢。 為提高速度，還有為提高速度，還有相關映象相關映象頁地址轉換以及頁地址轉換以及相關、直相關、直接相結合的接相結合的頁地址轉換。頁地址轉換。相關映象頁地址轉換：相關映象頁地址轉換：頁表不

56、放在主存中，而是放在高速頁表不放在主存中，而是放在高速半導體存儲器中，稱為快表。（相比一次訪問速度降低半導體存儲器中，稱為快表。（相比一次訪問速度降低10左右），但成本高。左右），但成本高。 靜態靜態RAM是靠雙穩態觸發器來記憶信息的；是靠雙穩態觸發器來記憶信息的； 動態動態RAM是靠是靠MOS電路中的柵極電容來記憶信息的。由于電電路中的柵極電容來記憶信息的。由于電容上的電荷會泄漏，需要定時給與補充，所以動態容上的電荷會泄漏，需要定時給與補充，所以動態RAM需要設需要設置刷新電路。置刷新電路。NO：50 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 一個程序可能會很大，如

57、一個程序可能會很大，如1M，若頁長為若頁長為1K，則該程序則該程序有有1000個頁，則該程序的頁表就需要個頁，則該程序的頁表就需要1000個表項，當程序個表項，當程序更大時，頁表會更大，那么我們應該有一個多大的快速存更大時，頁表會更大，那么我們應該有一個多大的快速存儲器才能滿足要求呢？這會遇到兩個問題：儲器才能滿足要求呢？這會遇到兩個問題：可能快速存儲器多大都是不夠的，因為程序可能會更大?？赡芸焖俅鎯ζ鞫啻蠖际遣粔虻?，因為程序可能會更大?？焖俅鎯ζ魇欠浅７浅０嘿F的?？焖俅鎯ζ魇欠浅７浅０嘿F的。NO：51 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理相關、直接相結合：相關、

58、直接相結合：根據程序局部性特點（時間、空間），根據程序局部性特點（時間、空間），將正在運行的，最常用的部分頁表存放在相關存儲器中。將正在運行的，最常用的部分頁表存放在相關存儲器中。查找時先在相關存儲器中查找，命中率可達查找時先在相關存儲器中查找，命中率可達90。程序局部性原理程序局部性原理 時間局部性時間局部性 一條指令被執行了，則在不久的將來它可能再被執行一條指令被執行了，則在不久的將來它可能再被執行 空間局部性空間局部性 若某一存儲單元被使用，則在一定時間內，與該存儲單若某一存儲單元被使用，則在一定時間內，與該存儲單元相鄰的單元可能被使用元相鄰的單元可能被使用NO：52 第四章第四章 操作

59、系統操作系統4.3 4.3 存儲器管理存儲器管理（3）頁面變換算法）頁面變換算法由于分頁管理中分配給每道程序的由于分頁管理中分配給每道程序的頁架數有限頁架數有限，因此，因此內存中的頁面要隨時進行更換，稱為內存中的頁面要隨時進行更換，稱為頁面淘汰頁面淘汰。頁面更換不。頁面更換不當會導致剛淘汰出內存的頁面又要調入內存，這樣使處理器當會導致剛淘汰出內存的頁面又要調入內存，這樣使處理器大部分時間都用于頁面調度上，稱為大部分時間都用于頁面調度上，稱為“抖動抖動”，從而降低了，從而降低了系統運行的速度。為了避免產生這種現象，需要選擇一種較系統運行的速度。為了避免產生這種現象，需要選擇一種較好的算法進行頁面

60、淘汰。下面介紹兩種常用的算法。好的算法進行頁面淘汰。下面介紹兩種常用的算法。NO：53 第四章第四章 操作系統操作系統4.3 4.3 存儲器管理存儲器管理 先進先出法（先進先出法（FIFOFirst Input First Output） 此算法的主要思想時認為此算法的主要思想時認為最先進入最先進入內存的頁面，內存的頁面，不再被不再被使用使用的可能性最大，所以最先進入內存的頁面，最先被調出內的可能性最大，所以最先進入內存的頁面，最先被調出內存。下面通過一個簡單的例子來說明。存。下面通過一個簡單的例子來說明。 設有一用戶程序共分為設有一用戶程序共分為5頁頁，其執行時頁面變化的規律稱，其執行時頁面