1、Chapter 8: 內(nèi)存管理,Objectives本章目標(biāo),To provide a detailed description of various ways of organizing memory hardware 背景知識：描述內(nèi)存硬件的組織方法 To discuss various memory-management techniques, including paging and segmentation 討論各種內(nèi)存管理技術(shù)，其中包括分頁與分段 To provide a detailed description of the Intel Pentium, which suppor

2、ts both pure segmentation and segmentation with paging 詳細描述Intel奔騰系列芯片，著重闡述它對分段以及段頁式內(nèi)存管理機制的支持（內(nèi)存管理的硬件支持）,Chapter 8: Memory Management,8.1 Background 8.2 Swapping 8.3 Contiguous Memory Allocation Paging Structure of the Page Table Segmentation Example: The Intel Pentium,8.1 Background背景介紹,Execution o

3、f a program 程序執(zhí)行過程 取指/解碼/執(zhí)行（Fetch/Decode/Execute） Fetch an instruction 從內(nèi)存中讀取一條指令 Decode the instruction 將指令放入指令寄存器（IR）中，然后對其進行解碼（解碼后可能還要從內(nèi)存中取操作數(shù)） Instruction Cycle 一個單條指令處理過程稱為一個指令周期 程序的執(zhí)行由不斷地取指、解碼和執(zhí)行的指令周期組成 當(dāng)程序的全部指令執(zhí)行完畢時，程序停止,開始,取指,解碼,執(zhí)行指令,停止,8.1 Background背景介紹,前一個slide中所講的CPU執(zhí)行指令的流程，是從CPU的角度來看程序執(zhí)

4、行流程的 而如果我們換一個角度，從內(nèi)存硬件的角度來這個執(zhí)行過程時，看到的應(yīng)該是另一番景象 內(nèi)存所面對的就是一個地址流 這些地址流是由于CPU對內(nèi)存的讀寫訪問而形成的 對于物理內(nèi)存而言，這些地址是怎么產(chǎn)生的它不用關(guān)心 所以，在后面進行內(nèi)存管理的時候，內(nèi)存資源都被視為一個線性的數(shù)組（Linear Array） = 線性的地址空間 內(nèi)存管理算法所關(guān)心的主要事情是如何將這個線性的數(shù)組進行有效的劃分，并進行合理地分配,8.1 Background背景介紹,Main memory and registers are only storage CPU can access directly 只有主存和寄存器

5、這兩種存儲介質(zhì)是可以被CPU所直接訪問的 Program must be brought (from disk) into memory and placed within a process for it to be run 因此，程序必須從外存中讀到進程所管理的內(nèi)存中來執(zhí)行,8.1.1 基本內(nèi)存硬件,Register access in one CPU clock (or less) CPU對于寄存器的訪問在一個CPU時鐘周期內(nèi)就可以完成 Main memory can take many cycles 主存訪問可能需要多個周期（比訪問寄存器要慢） Cache sits between m

6、ain memory and CPU registers 高速緩存（Cache）介乎寄存器與主存之間,8.1 Background背景介紹,8.1.1 基本內(nèi)存硬件,操作系統(tǒng)在進行內(nèi)存管理的時候，除了保證訪問物理內(nèi)存的相對速度，還必須對操作系統(tǒng)與用戶進程之間，以及用戶進程與用戶進程之間必須被有效的隔離 Protection of memory required to ensure correct operation 對于存儲的有效保護，是保證程序正確執(zhí)行的基礎(chǔ),8.1 Background背景介紹,8.1.1 基本內(nèi)存硬件,進程需要獨立的私人空間 - 進程的地址空間,8.1 Backgroun

7、d背景介紹,Early Single-Programming 早期的單道程序的內(nèi)存分布 特點： 沒有內(nèi)存管理硬件的支持 操作系統(tǒng)(Operating System)與應(yīng)用程序(Application)之間可以相互訪問對方的內(nèi)存 實例：MS-DOS,操作系統(tǒng),應(yīng)用程序,1M,0,8.1 Background背景介紹,單道程序中的內(nèi)存組織的問題,操作系統(tǒng),應(yīng)用程序,1M,0,物理存儲空間分配不當(dāng)，產(chǎn)生了重疊，那么可能存在內(nèi)存使用沖突,8.1 Background背景介紹,Multi-Programming 多道程序 特點： 多道程序同時駐留在內(nèi)存,操作系統(tǒng),應(yīng)用程序2,xxxM,0,應(yīng)用程序1,操

8、作系統(tǒng)內(nèi)存組織Organization of Memory,多道程序中的內(nèi)存組織的問題,物理存儲空間分配不當(dāng)，產(chǎn)生了重疊，同樣可能存在內(nèi)存使用沖突,操作系統(tǒng),應(yīng)用程序2,xxxM,0,應(yīng)用程序1,Segmentation Memory Protection段式內(nèi)存保護,把內(nèi)存分成幾段，每段分別劃給一個實體（操作系統(tǒng)代碼、進程1、進程2、）,通過一個段基址base和段的長度limit來規(guī)定歸屬于某個進程的一段內(nèi)存區(qū)間,段機制需要硬件支持， 通常利用硬件寄存器來維護 段機制和段長度，并通過硬件 上的機制來保證對內(nèi)存的訪問 不會越界,在例子中， 訪問地址30005，OK 用30004作為基地址訪問4

9、3000, 不OK,8.1 Background背景介紹,內(nèi)存保護的實現(xiàn)機理，如下圖所示,CPU,基地址,基地址+界限地址,是,內(nèi)存,否,是,否,地址,地址基地址 下界溢出,地址=基地址+界限地址 上界溢出,尋址錯誤，這對操作系統(tǒng)來說， 是致命錯誤，需要立刻陷入內(nèi)核處理,8.1 Background背景介紹,注意到，基于基地址寄存器和界限寄存器的硬件地址保護能夠正確工作的前提是基地址寄存器和界限寄存器的內(nèi)容不能所以被篡改 實際上，上述兩個寄存器都只能由操作系統(tǒng)通過特殊的特權(quán)指令來加載，一般的用戶進程是無法修改他們的 所以，在這樣的前提下，硬件地址保護模式是可以正確工作的,8.1 Backgro

10、und背景介紹,Address Binding 地址綁定的目的 為代碼中的函數(shù)名、變量名等指定地址,8.1.2 地址綁定,8.1 Background背景介紹,地址綁定 將程序中的指令或者數(shù)據(jù)分配到實際的物理內(nèi)存單元 在程序?qū)嶋H執(zhí)行之前，必須處理地址的綁定，因為只有程序知道了執(zhí)行所需的代碼或數(shù)據(jù)在實際物理內(nèi)存的位置，CPU才能夠完成取指-執(zhí)行的基本步驟,8.1.2 地址綁定,程序的活動流程 Compile time Load time Execution time,Binding of Instructions and Data to Memory地址綁定時機,Compile time: 編譯

11、時就完成指令和數(shù)據(jù)地址到絕對內(nèi)存地址的綁定 缺點：如果代碼起始地址發(fā)生變化，代碼需要重新編譯 Load time: Must generate relocatable code if memory location is not known at compile time 編譯期間，不知道代碼和數(shù)據(jù)應(yīng)該放到那個內(nèi)存位置 必須生成可重定位代碼（relocatable code） Execution time: 運行時完成地址綁定 需要重定位硬件支持,地址綁定的3個時機：,8.1 Background,CPU生成的地址，通常稱為邏輯地址（Logical Address） 內(nèi)存硬件所看到的地址（即加

12、載到內(nèi)存地址寄存器Memory Address Register, MAR中的地址），通常稱為物理地址（Physical Address）,8.1.3 邏輯地址空間與物理地址空間,Relocation地址重定位,地址重定位 將用戶程序中出現(xiàn)的邏輯地址轉(zhuǎn)化到程序運行時計算機可以識別的物理地址的過程 實現(xiàn)方法 Static Relocation 靜態(tài)重定位 Dynamic Relocation 動態(tài)重定位,Relocation地址重定位,靜態(tài)地址重定位 在程序編譯或加載的時候完成地址的重定位，也就是說在程序加載的同時進行程序的內(nèi)容,Relocation地址重定位,靜態(tài)重定位實例,Relocatio

13、n地址重定位,動態(tài)重定位 在程序執(zhí)行期間完成邏輯地址到實際地址的轉(zhuǎn)換 需要內(nèi)存管理硬件MMU的支持 頁式/段式虛存管理之下的地址變換，是動態(tài)重定位的典型實例,Relocation地址重定位,動態(tài)重定位實例,8.2 Swapping交換,一個進程可以被操作系統(tǒng)暫時從內(nèi)存換到后備存儲（backing store），而在某個時刻再被從后備存儲換回內(nèi)存執(zhí)行,后備存儲要求： 訪問速度較快 其容量要能夠存放所有用戶的內(nèi)存映像副本 必須提供對這些內(nèi)存鏡像進行直接訪問的操作,8.2 Swapping交換,一個進程可以被操作系統(tǒng)暫時從內(nèi)存換到后備存儲（backing store），而在某個時刻再被從后備存儲換回

14、內(nèi)存執(zhí)行,基于優(yōu)先級的調(diào)度中可能用到 交換策略： 滾出（Roll out） 如果有一個更高優(yōu)先級的 進程需要服務(wù)，內(nèi)存管理器 可以選擇將某低優(yōu)先級進程P 換出 滾入（Roll in） 高優(yōu)先級的進程執(zhí)行完后， 低優(yōu)先級進程可以再次被 換回內(nèi)存,8.2 Swapping交換,交換的限制： 通常，一個交換出的進程需要交換回它原來所占有的內(nèi)存空間,上述限制是由地址綁定方式?jīng)Q定的。,解釋：,（1） 如果綁定是在匯編或加載時所定的，那么進程換回時不可以移到 不同的位置 （2）如果綁定是在運行時完成的，由于物理地址是在運行期才確定的， 所以在進程換回時可以允許其換到與換出前不同的內(nèi)存位置,8.2 Swap

15、ping交換,在支持交換的系統(tǒng)內(nèi)，調(diào)度是這樣發(fā)生的： 系統(tǒng)的就緒隊列中包括在備份存儲或在內(nèi)存中已經(jīng)處于就緒狀態(tài)的所有進程 當(dāng)CPU決定執(zhí)行進程時，它調(diào)用調(diào)度程序 調(diào)度程序檢查就緒隊列中下一進程P 如果P在內(nèi)存中，那么調(diào)度其執(zhí)行 如果P不在內(nèi)存中，且空閑內(nèi)存空間足夠，將P換入 如果P不在內(nèi)存中，且空閑內(nèi)存空間不夠裝下P，那么選擇一個合適的進程P，將P換出，然后換入P,8.2 Swapping交換,交換系統(tǒng)的上下文切換時間比較長 Major part of swap time is transfer time; 在交換時間中，轉(zhuǎn)移時間占了大部分 total transfer time is dir

16、ectly proportional to the amount of memory swapped轉(zhuǎn)移時間與內(nèi)存需求量成正比 為了有效使用CPU，需要每個進程的時間要比交換時間長,8.2 Swapping交換,交換也受其他因素限制，以下是不可以被換出的進程的一種情況 如果一個進程正在等待I/O操作，而此異步I/O操作需要訪問用戶內(nèi)存的I/O緩沖區(qū)，那么該進程不能被換出,解決方法： 方法一，不允許換出等待I/O的進程 方法二，設(shè)計時，規(guī)定I/O操作的執(zhí)行只能使用操作系統(tǒng)內(nèi)核緩沖區(qū),8.2 Swapping交換,許多操作系統(tǒng)都在使用標(biāo)準(zhǔn)交換系統(tǒng)的變種 UNIX版本的交換 平時并不執(zhí)行； 在系統(tǒng)內(nèi)

17、存空間吃緊時，啟動交換； 當(dāng)系統(tǒng)負荷降低，交換又會暫停 Windows 3.1 交換的時機完全由用戶掌握 換出的進程會一直處于換出狀態(tài)，直到用戶再選擇執(zhí)行該進程為止,8.3 Contiguous Memory Allocation連續(xù)內(nèi)存分配,操作系統(tǒng)內(nèi)核與各種用戶進程，都是占據(jù)內(nèi)存的實體 內(nèi)存管理算法要完成內(nèi)存在各個實體之間的公平有效的分配 這一節(jié)，介紹連續(xù)內(nèi)存分配這一常用的內(nèi)存分配方法,8.3 Contiguous Memory Allocation連續(xù)內(nèi)存分配,內(nèi)存通常被分為兩個區(qū)域 其一用于駐留操作系統(tǒng) 其二用于用戶進程 操作系統(tǒng)可以處于內(nèi)存區(qū)域的高端，也可以在內(nèi)存區(qū)域的低端 決定操作系統(tǒng)位置的一個主要因素，是系統(tǒng)中斷向量的位置 通常，中斷向量是放在內(nèi)存的低地址區(qū) 因此，操作系統(tǒng)也會被放在低地址區(qū),8.3 Contiguous Memory Allocation連續(xù)內(nèi)存分配,重定位寄存器用來對操作系統(tǒng)內(nèi)核和各用戶進程實施內(nèi)存保護 每段區(qū)域的內(nèi)存基地址，保存在基地址寄存器中 內(nèi)存區(qū)域的長度，則由界限寄存器（limit register）記錄 重定位的過程由MMU硬件在程序執(zhí)行期完成,Contiguous Allocation (Cont.),多分區(qū)分配的一個實例 內(nèi)存空洞