1、1存儲管理存儲管理2概述概述n如果讓計算機同時運行多道程序，比如：搜索文件、檢如果讓計算機同時運行多道程序，比如：搜索文件、檢查病毒、錄入數據以及運行計算程序等，就要把這些可查病毒、錄入數據以及運行計算程序等，就要把這些可執行程序放入內存。執行程序放入內存。n若讓用戶指定各程序安放的具體位置不僅麻煩，而且會若讓用戶指定各程序安放的具體位置不僅麻煩，而且會出現內存位置沖突、內存利用率低、內存管理混亂等諸出現內存位置沖突、內存利用率低、內存管理混亂等諸多問題。所以，多問題。所以，存儲空間必須由操作系統統一安排存儲空間必須由操作系統統一安排，這，這就形成了操作系統的內存管理模塊。就形成了操作系統的內

2、存管理模塊。n操作系統管理存儲器要從輔存中取進或換出數據塊，但操作系統管理存儲器要從輔存中取進或換出數據塊，但相對而言，相對而言，存儲器存儲器I/O是一個很慢的操作是一個很慢的操作。n為保持處理器或多個處理器處于忙狀態以保證效率，操為保持處理器或多個處理器處于忙狀態以保證效率，操作系統必須很聰明地作系統必須很聰明地安排換入和換出的時機安排換入和換出的時機，以減少存，以減少存儲器儲器I/O對性能的影響。對性能的影響。3存儲器的層次存儲器的層次R高速緩存高速緩存主存儲器主存儲器磁盤緩存磁盤緩存固定磁盤固定磁盤可移動存儲介質可移動存儲介質某臺計算機存儲器層次配置某臺計算機存儲器層次配置1CPU中的寄

3、存器中的寄存器100個字；高個字；高速緩存速緩存512KB，存取周期，存取周期15ns；1主存儲器主存儲器128MB，存取周期，存取周期60ns；1磁盤容量磁盤容量20GB，存取，存取周期毫秒級；周期毫秒級；1后援存儲容量后援存儲容量1TB，存取周期秒級。存取周期秒級。4存儲管理的功能存儲管理的功能n存儲管理主要是指對主存儲器存儲管理主要是指對主存儲器(內存內存)的管理，要求操作的管理，要求操作系統的存儲管理機構必須解決系統的存儲管理機構必須解決u內存分配內存分配。多個進程同時運行，內存空間如何合理分配。多個進程同時運行，內存空間如何合理分配,決定決定了內存是否能得到充分利用；了內存是否能得到

4、充分利用；u存儲保護存儲保護。運行時必須保證多個進程之間不能沖突、干擾和。運行時必須保證多個進程之間不能沖突、干擾和破壞；破壞；u地址變換地址變換。程序是在連續區域中，還是劃分成若干塊放在不。程序是在連續區域中，還是劃分成若干塊放在不同區域中？是事先還是動態劃分？多種存儲分配方案與軟件同區域中？是事先還是動態劃分？多種存儲分配方案與軟件和硬件的地址變換技術及其機制緊密相關；和硬件的地址變換技術及其機制緊密相關；u存儲共享存儲共享。多個進程共用同一系統軟件，如編譯程序，存放。多個進程共用同一系統軟件，如編譯程序，存放編譯程序的內存區即為共享內存區；編譯程序的內存區即為共享內存區；u存儲擴充存儲擴

5、充。即虛擬存儲管理技術。即虛擬存儲管理技術。5內存分配與回收內存分配與回收n管理內存分配表管理內存分配表n制定分配策略制定分配策略u放置策略u調入策略u淘汰策略n內存區域劃分內存區域劃分u劃分為大小相等的塊u劃分為大小不等的塊n回收回收6主存空間的共享主存空間的共享n 兩方面的含義：兩方面的含義：u共享主存資源；u共享主存的某些區域的信息。存儲保護存儲保護1屬于自己區域的信息，可讀可寫；屬于自己區域的信息，可讀可寫；1公共區域共享信息或獲得授權信息，可讀不可寫；公共區域共享信息或獲得授權信息，可讀不可寫；1未獲授權信息，不可讀不可寫。未獲授權信息，不可讀不可寫。7地址映射地址映射(重定位重定位

6、)n地址空間地址空間u一個目標程序所限定的一個目標程序所限定的相對地址相對地址范圍。范圍。n存儲空間存儲空間u主存的實際空間，是主存中一系列物理存儲單元的集合。主存的實際空間，是主存中一系列物理存儲單元的集合。n虛空間虛空間u采用以零為基準地址的相對地址采用以零為基準地址的相對地址/邏輯地址邏輯地址u此時的空間稱為虛空間此時的空間稱為虛空間n絕對地址空間絕對地址空間u物理地址空間，是真實地址空間物理地址空間，是真實地址空間n重定位重定位u把邏輯地址轉換成絕對地址的過程稱為重定位或地址轉換。把邏輯地址轉換成絕對地址的過程稱為重定位或地址轉換。n重定位的方式重定位的方式u靜態定位、動態定位靜態定位

7、、動態定位8典型的地址空間示意圖典型的地址空間示意圖一個進程的尋址要求一個進程的尋址要求進程控制塊進程控制塊程序程序數據數據棧棧進程控制信息進程控制信息程序的入口點程序的入口點分支指令分支指令訪問數據訪問數據當前棧頂當前棧頂地址值增加地址值增加9典型的地址空間示意圖典型的地址空間示意圖n該圖描述了一個進程映像該圖描述了一個進程映像u假設這個進程映像占據了主存中的一段相鄰的區域；假設這個進程映像占據了主存中的一段相鄰的區域；u操作系統需要知道進程控制信息和執行棧，以及為這個進程操作系統需要知道進程控制信息和執行棧，以及為這個進程開始執行程序的入口點的位置；開始執行程序的入口點的位置；u由于操作系

8、統管理存儲器并負責把該進程取進主存，因而可由于操作系統管理存儲器并負責把該進程取進主存，因而可以很容易地得到這些地址。此外，處理器必須處理程序內部以很容易地得到這些地址。此外，處理器必須處理程序內部的存儲器訪問；的存儲器訪問；u分支指令包含下一步將要執行的指令的地址，數據訪問指令分支指令包含下一步將要執行的指令的地址，數據訪問指令包含被訪問數據的字節或字的地址。包含被訪問數據的字節或字的地址。n處理器硬件和操作系統軟件必須能夠處理器硬件和操作系統軟件必須能夠把程序代碼中的存把程序代碼中的存儲器訪問轉換成實際的物理存儲器地址儲器訪問轉換成實際的物理存儲器地址，以反映出程序，以反映出程序在主存中的

9、當前位置。在主存中的當前位置。10重定位示例重定位示例進程控制塊進程控制塊程序程序數據數據棧棧基址寄存器基址寄存器界限寄存器界限寄存器比較器比較器加法器加法器給操作系統的中斷給操作系統的中斷相對地址相對地址絕對地址絕對地址主存中的進程映像主存中的進程映像11靜態重定位靜態重定位n程序在被裝入到內存的過程中實現重定位，在程程序在被裝入到內存的過程中實現重定位，在程序序運行過程中不再改變運行過程中不再改變。n例：例：0邏輯地址空間LOAD 1，500256100500600裝入裝入程序程序主存02561000110015001600nLOAD 1，50012動態重定位動態重定位n程序程序執行過程中

10、執行過程中進行重定位進行重定位n依靠硬件地址轉換機構完成依靠硬件地址轉換機構完成0邏輯地址空間LOAD 1，5001 2 3 4 5100500600主存11001500LOAD 1，5001 2 3 4 55001000邏輯地址邏輯地址重定位寄存器重定位寄存器13主存空間的擴充主存空間的擴充n目的：解決小內存運行大作業的問題。目的：解決小內存運行大作業的問題。n借助于虛擬存儲技術或其它自動覆蓋技術實現。借助于虛擬存儲技術或其它自動覆蓋技術實現。14存儲管理技術存儲管理技術15n分區式分配分區式分配u固定分區固定分區/靜態分區靜態分區u可變分區可變分區/動態分區動態分區n可重定位分區分配可重定

11、位分區分配n覆蓋與交換覆蓋與交換16分區式分配分區式分配n把內存劃分為若干個大小不等或相等的連續區域，把內存劃分為若干個大小不等或相等的連續區域，稱為稱為分區分區(partition)，操作系統占用其中一個，操作系統占用其中一個分區，其它每個分區裝入一個運行作業。分區，其它每個分區裝入一個運行作業。n特點：適用于多道程序系統和分時系統特點：適用于多道程序系統和分時系統u支持多個程序并發執行支持多個程序并發執行u難以進行內存分區的共享難以進行內存分區的共享n問題：可能存在問題：可能存在碎片碎片(Fragmentation)n分區的數據結構分區的數據結構:分區表分區表(記錄分區的大小和使用記錄分區

12、的大小和使用情況情況)，劃分為兩個表格：空閑分區表，占用分，劃分為兩個表格：空閑分區表，占用分區表。區表。17分區式分配分區式分配n分類：分類：u固定式分區固定式分區u可變式分區可變式分區18固定式分區固定式分區n處理作業前把內存處理作業前把內存劃分為若干固定的分區劃分為若干固定的分區，當作，當作業申請內存資源時為其業申請內存資源時為其選擇一個適當的分區選擇一個適當的分區，并，并將其裝入內存運行。將其裝入內存運行。n分區表分區表區號區號分區長度分區長度起始地址起始地址狀態狀態18K20K已分配已分配232K28K已分配已分配364K60K已分配已分配4132K124K已分配已分配19固定式分區

13、固定式分區優點：易于實現，開銷小。優點：易于實現，開銷小。缺點：缺點：u內碎片造成浪費內碎片造成浪費u分區總數固定，限制了并發分區總數固定，限制了并發執行的程序數目。執行的程序數目。可以和覆蓋、交換技術配合可以和覆蓋、交換技術配合使用。使用。采用的數據結構：分區表采用的數據結構：分區表操作系統進程A(6K)進程B(25K)進程C(36K)第1分區第2分區第3分區第4分區020K28K60K124K256K20可變分區可變分區/動態分區動態分區n在處理作業的過程中建立分區，使分區大小和作在處理作業的過程中建立分區，使分區大小和作業要求的存儲空間相等。業要求的存儲空間相等。n優點：沒有內碎片。優點

14、：沒有內碎片。n缺點：有外碎片；如果大小不是任意的，也可能缺點：有外碎片；如果大小不是任意的，也可能出現內碎片。出現內碎片。n可變分區主存分配表可由兩張表格組成可變分區主存分配表可由兩張表格組成u已分配分區表已分配分區表u未分配分區表未分配分區表21可變分區可變分區/動態分區動態分區jobA 15KjobB 20KjobC 10KjobD 25KjobE 14KjobF 31KjobA 15KOS空閑區jobA 15KOSjobB 20K空閑區jobA 15KOSjobB 20KjobC 10K空閑區jobA 15KOSjobB 20KjobC 10KjobD 25K空閑區jobB、C結束，結

15、束，jobF裝入裝入jobA結束，結束，jobE裝入裝入22可變分區內存分配表可變分區內存分配表已分配分區表已分配分區表未分配分區表未分配分區表序號序號大小大小起始地址起始地址狀態狀態序號序號 大小大小 起始地址起始地址狀態狀態18K20K已分配已分配164K44K可用可用216K28K已分配已分配224K232K可用可用3空表目空表目4124K108K已分配已分配5空表目空表目23動態分配的主要步驟動態分配的主要步驟n查找一個足夠容納作業的可用空閑區；查找一個足夠容納作業的可用空閑區；n若該空閑區比需要的大，則一分為二，并修改若該空閑區比需要的大，則一分為二，并修改分配表信息；分配表信息；n

16、回收時合并相鄰空閑區。回收時合并相鄰空閑區。n解決解決“外零頭外零頭”方法：方法： “拼接拼接”或或“緊湊緊湊”技技術術24可重定位分區分配可重定位分區分配n可變分區中當作業完成時，將回收的分區與未使可變分區中當作業完成時，將回收的分區與未使用的空白區合并組成更大的空白區，叫做用的空白區合并組成更大的空白區，叫做“拼接拼接”或或“緊湊緊湊”n可變分區中剩余的作業分散在內存中，即使可變分區中剩余的作業分散在內存中，即使拼接拼接后，內存中仍有一些因不連續而不能被充分利用后，內存中仍有一些因不連續而不能被充分利用的空白區。的空白區。n采用重定位技術，將作業從一個分區移到另一個采用重定位技術，將作業從

17、一個分區移到另一個分區，將不相鄰的空白區進行合并。分區，將不相鄰的空白區進行合并。n作業從一個分區移到另一個分區，實質上只要作業從一個分區移到另一個分區，實質上只要修修改重定位機制中基址寄存器的值改重定位機制中基址寄存器的值。25可重定位分區分配可重定位分區分配操作系統操作系統作業作業1(10KB)8KB空白區空白區作業作業222KB空白區空白區不連續空白區不連續空白區操作系統操作系統18KB空白區空白區作業作業222KB空白區空白區作業作業1完成后完成后拼接拼接操作系統操作系統40KB空白區空白區作業作業2作業作業2重定位重定位26覆蓋與交換技術覆蓋與交換技術n覆蓋覆蓋(overlay)n交

18、換交換(swapping)27覆蓋覆蓋(overlay)n所謂覆蓋，是指一個作業中的若干程序段或數據所謂覆蓋，是指一個作業中的若干程序段或數據段之間，或段之間，或n個作業的某些部分共享某部分的主個作業的某些部分共享某部分的主存空間。存空間。n原理：原理：一個程序的幾個代碼段或數據段，一個程序的幾個代碼段或數據段，按照時按照時間先后間先后來占用公共的內存空間。來占用公共的內存空間。u將程序的必要部分（常用功能）的代碼和數據常駐將程序的必要部分（常用功能）的代碼和數據常駐內存；內存；u可選部分可選部分(不常用功能不常用功能)在其他程序模塊中實現，平在其他程序模塊中實現，平時存放在外存中時存放在外存

19、中(覆蓋文件覆蓋文件)，在需要用到時才裝入到，在需要用到時才裝入到內存；內存；u不存在調用關系的模塊不必同時裝入到內存，從而不存在調用關系的模塊不必同時裝入到內存，從而可以相互覆蓋。可以相互覆蓋。(即不同時用的模塊可共用一個分區即不同時用的模塊可共用一個分區)28覆蓋覆蓋(overlay)初始段處理段輸出段總控程序公用子程序公用數據區OS非覆蓋區覆蓋區0abc29交換技術交換技術(swapping)n引入：多個程序并發執行，可以將暫時不能執行的程序引入：多個程序并發執行，可以將暫時不能執行的程序送到外存中，從而獲得空閑內存空間來裝入新程序，或送到外存中，從而獲得空閑內存空間來裝入新程序，或讀入

20、保存在外存中而目前到達就緒狀態的進程。交換單讀入保存在外存中而目前到達就緒狀態的進程。交換單位為整個進程的地址空間。位為整個進程的地址空間。n交換交換:就是把主存中的信息以文件的形式寫入輔存，然就是把主存中的信息以文件的形式寫入輔存，然后再將指定的信息從輔存讀入到主存。簡言之，就是后再將指定的信息從輔存讀入到主存。簡言之，就是內、內、外存之間信息的交換外存之間信息的交換。常與分區存儲管理配合使用。又。常與分區存儲管理配合使用。又稱作稱作“對換對換”或或“滾進滾進/滾出滾出(roll-in/roll-out)”。30交換技術交換技術(swapping)n優點：增加并發運行的程序數目，并且給用戶提

21、優點：增加并發運行的程序數目，并且給用戶提供適當的響應時間；編寫程序時不影響程序結構供適當的響應時間；編寫程序時不影響程序結構n缺點：對換入和換出的控制增加處理機開銷；程缺點：對換入和換出的控制增加處理機開銷；程序整個地址空間都進行傳送，沒有考慮執行過程序整個地址空間都進行傳送，沒有考慮執行過程中地址訪問的統計特性。中地址訪問的統計特性。31分頁存儲管理分頁存儲管理32虛擬存儲器虛擬存儲器n從邏輯上對內存容量進行擴充。從邏輯上對內存容量進行擴充。n基本思想：基本思想：利用大容量的外存來擴充內存。利用大容量的外存來擴充內存。n利用外存自動調度的方法構成一個大空間的存儲利用外存自動調度的方法構成一

22、個大空間的存儲器。器。n實現原理：實現原理：部分裝入、部分交換部分裝入、部分交換n說明說明u虛擬存儲器的最大容量由計算機的地址總線確定；虛擬存儲器的最大容量由計算機的地址總線確定；u實現虛擬存儲器必須有相當容量的外存和動態地實現虛擬存儲器必須有相當容量的外存和動態地址變換機構；址變換機構；u以時間換空間。以時間換空間。33分頁的概念分頁的概念n頁式存儲管理，就是把內存物理空間分成大小相頁式存儲管理，就是把內存物理空間分成大小相等的存儲塊，與之對應，把作業的邏輯空間按照等的存儲塊，與之對應，把作業的邏輯空間按照同樣的尺寸劃分成若干頁。同樣的尺寸劃分成若干頁。n將程序的邏輯地址空間和物理內存劃分為

23、固定大將程序的邏輯地址空間和物理內存劃分為固定大小的頁或頁面小的頁或頁面(page or page frame)，程序加，程序加載時，分配其所需的所有頁，這些頁不必連續。載時，分配其所需的所有頁，這些頁不必連續。需要需要CPU的硬件支持。的硬件支持。34分頁的概念分頁的概念n實現方法：采用動態重定位技術利用實現方法：采用動態重定位技術利用頁表頁表(Page Table)進行地址變換。進行地址變換。n基本思想：部分裝入、部分交換基本思想：部分裝入、部分交換n優點：優點：u沒有外碎片，每個內碎片不超過頁大小。沒有外碎片，每個內碎片不超過頁大小。u一個程序不必連續存放。一個程序不必連續存放。u便于改

24、變程序占用空間的大小。即隨著程序運行而便于改變程序占用空間的大小。即隨著程序運行而動態生成的數據增多，地址空間可相應增長。動態生成的數據增多，地址空間可相應增長。n缺點：程序全部裝入內存。缺點：程序全部裝入內存。35頁的大小頁的大小n通常是：通常是： 512B4KB。u小小內碎片小；大內碎片小；大頁表短，管理開銷小，交換頁表短，管理開銷小，交換時對外存時對外存I/O效率高。效率高。相對頁號P頁內地址D作業邏輯地址存儲塊號頁內地址存儲塊號頁內地址物理地址物理地址塊號塊內地址物理地址物理地址與邏輯地址物理地址與邏輯地址36頁面地址轉換的數據結構頁面地址轉換的數據結構(1)n存儲分塊表存儲分塊表MB

25、T：塊號、作業號、狀態：塊號、作業號、狀態塊號塊號作業號作業號狀態狀態0os忙忙1J1忙忙2J2忙忙nJk閑閑37頁面地址轉換的數據結構頁面地址轉換的數據結構(2)n頁表頁表PT：每個進程有一個頁表，描述該進程占：每個進程有一個頁表，描述該進程占用的用的物理頁面物理頁面及及邏輯頁面邏輯頁面排列順序；排列順序；n頁表的作用：實現頁號和塊號的對應頁表的作用：實現頁號和塊號的對應P184n說明：說明：u頁表在作業裝入時建立，作業撤消時消失；頁表在作業裝入時建立，作業撤消時消失；u其在內存中的位置由頁表的起始地址和頁表大小所其在內存中的位置由頁表的起始地址和頁表大小所定定(頁表的兩個關鍵參數：頁表始址

26、和頁表長度被裝頁表的兩個關鍵參數：頁表始址和頁表長度被裝入頁表控制寄存器入頁表控制寄存器PTCR) 。38頁面地址轉換的數據結構頁面地址轉換的數據結構(3)n作業表作業表JT：記錄作業的頁表在內存的起始地址、：記錄作業的頁表在內存的起始地址、大小、狀態等信息。大小、狀態等信息。作業號作業號作業大小作業大小頁面始址頁面始址狀態狀態J11610241J21839頁式管理的地址變換頁式管理的地址變換作業號 作業大小 頁面始址 狀態J11610241JT頁表始址1024頁表長度頁號 塊號02132810248452頁號 頁內地址 作業調度作業調度 越界中斷越界中斷 查查PT 形成物理地址形成物理地址8

27、10244528644 40頁式管理的地址變換頁式管理的地址變換n地址轉換機構把地址轉換機構把CPU給出的有效地址自動給出的有效地址自動分成兩部分。分成兩部分。n例如：例如：u執行指令：執行指令： LOAD 1,2500u有效地址有效地址2500=21024+452，因此，因此 頁號頁號P2，頁內地址，頁內地址D452。 （假設頁面大小為（假設頁面大小為1024）41頁式管理的地址變換頁式管理的地址變換n例：在一個頁式存儲管理系統中，頁表內容如下，例：在一個頁式存儲管理系統中，頁表內容如下，若頁的大小為若頁的大小為4k，則地址轉換機構將邏輯地址，則地址轉換機構將邏輯地址0轉換成的物理地址是多少

28、？轉換成的物理地址是多少？解：分解邏輯地址解：分解邏輯地址0=04k+0 故頁號為故頁號為0，查頁表得塊號為，查頁表得塊號為2， 所以物理地址為：所以物理地址為： 24k+0=241024+0=8192頁號塊號021126343742缺頁中斷缺頁中斷工作區入內存填寫頁表中各項進程調度此頁不在主存缺頁中斷保留中斷現場有空閑塊嗎？調入所需虛頁調整頁表及空閑塊恢復被中斷進程現場重新啟動被中斷的指令選擇一頁淘汰把該頁寫回外存修改內存分塊表，置該塊為空閑該頁修改過？有無是否43快表快表n為縮短查找時間，可以將頁表從內存裝入到關聯為縮短查找時間，可以將頁表從內存裝入到關聯存儲器存儲器(TLB, Trans

29、lation Lookaside Buffer)，也稱為快表。也稱為快表。n用來存放當前訪問最頻繁的少數活動頁的頁號。用來存放當前訪問最頻繁的少數活動頁的頁號。44快表地址變換過程快表地址變換過程JT頁表始址 頁表長度頁號 塊號0213288452頁號 頁內地址輸入寄存器2 8 獲取始址及大小獲取始址及大小頁表始址寄存器頁表始址寄存器 越界中斷越界中斷查找快表查找快表 45頁式存儲管理的特點頁式存儲管理的特點n虛擬存儲管理方式虛擬存儲管理方式(請求分頁存儲管理技術請求分頁存儲管理技術)n主要特點如下：主要特點如下：u1）存儲效率高）存儲效率高動態分配，無碎片動態分配，無碎片u2）存儲保護功能強）存儲保護功能強越界檢查越界檢查u3）方便的重定位）方便的重定位u4）易于共享頁面）易于共享頁面u5）開銷較大）開銷較大u6）有）有“抖動抖動”現象現象46段式存儲管理段式存儲管理47基本思想基本思想n頁式管理是把內存視為一維線性空間；而段式管頁式管理是把內存視為一維線性空間；而段式管理是把內存視為理是把內存視為二維空間二維空間。n將程序的地址空間劃分為若干個段將程序