操作系統(tǒng)內存管理-課件

內存管理內存管理1目的詳細描述內存硬件的各種組織方法討論各種內存管理技術，包括分頁和分段詳細描述IntelPentium芯片，它支持純分段和帶分頁的分段目的詳細描述內存硬件的各種組織方法2背景為了運行程序必須把程序從磁盤載入到內存內存和寄存器是CPU唯一能直接訪問的存儲器寄存器的訪問時間vs內存的訪問時間緩存為了確保正常運行必須保護內存背景為了運行程序必須把程序從磁盤載入到內存3首先討論：符號內存地址到實際物理地址的綁定邏輯地址與物理地址的區(qū)別動態(tài)裝載、動態(tài)鏈接代碼及共享庫首先討論：4在計算機科學中，庫是用于開發(fā)軟件的子程序集合。庫和可執(zhí)行文件的區(qū)別是，庫不是獨立程序，他們是向其他程序提供服務的代碼。庫鏈接是指把一個或多個庫包括到程序中，有兩種鏈接形式：靜態(tài)鏈接和動態(tài)鏈接，相應的，前者鏈接的庫叫做靜態(tài)庫后者的叫做動態(tài)庫。在計算機科學中，庫是用于開發(fā)軟件的子程序集合。庫和可5靜態(tài)鏈接是由鏈接器在鏈接時將庫的內容加入到可執(zhí)行程序中的做法。鏈接器是一個獨立程序，將一個或多個庫或目標文件（先前由編譯器或匯編器生成）鏈接到一塊生成可執(zhí)行程序。靜態(tài)鏈接的最大缺點是生成的可執(zhí)行文件太大，需要更多的系統(tǒng)資源，在裝入內存時也會消耗更多的時間。靜態(tài)鏈接是由鏈接器在鏈接時將庫的內容加入到可執(zhí)行程序中的做法6動態(tài)鏈接，在可執(zhí)行文件裝載時或運行時，由操作系統(tǒng)的裝載程序加載庫。大多數操作系統(tǒng)將解析外部引用（比如庫）作為加載過程的一部分。動態(tài)鏈接，在可執(zhí)行文件裝載時或運行時，由操作系統(tǒng)的裝載程序加7基地址寄存器和界限地址寄存器一個進程使用的內存地址范圍是由一對基地址寄存器和界限地址寄存器來定義基地址寄存器和界限地址寄存器一個進程使用的內存地址范圍是由一8一個用戶程序的多步驟處理一個用戶程序的多步驟處理9地址綁定地址綁定是從一個地址空間到另一個地址空間的映射將指令與數據綁定到內存，有以下幾種情況不知道駐留地址地址綁定地址綁定是從一個地址空間到另一個地址空間的映射不知道10邏輯地址空間和物理地址空間邏輯地址：CPU所生成的地址–(虛擬地址)物理地址：從內存單元所看到的地址綁定內存管理單元(MMU)邏輯地址空間和物理地址空間邏輯地址：CPU所生成的地址–(11內存管理單元（MMU）映射虛擬地址為物理地址的硬件設備

用戶進程所生成的地址在送交內存之前，都將加上重定位寄存器（基地址寄存器）的值

用戶程序決不會看到真正的物理地址內存管理單元（MMU）映射虛擬地址為物理地址的硬件設備

12庫的鏈接及加載靜態(tài)鏈接動態(tài)鏈接（dynamiclink）動態(tài)加載（dynamicloading）庫的鏈接及加載靜態(tài)鏈接13動態(tài)加載直到被調用之前，程序不會被載入到內存，即加載延遲到運行時優(yōu)點不使用的程序不會載入到內存，既而內存使用率高適合用戶用大量代碼來操作不常發(fā)生事件時不需要操作系統(tǒng)的特別支持，由程序員來設計動態(tài)加載直到被調用之前，程序不會被載入到內存，即加載延遲到運14動態(tài)鏈接鏈接延遲到執(zhí)行時小程序,stub（存根）,用來定位適當的內存駐留庫程序，或如果該程序不在內存時應如何裝入庫存根會用子程序地址來替換自己，并開始子程序存根首先檢查所需子程序是否在內存中，如果不在，就將子程序裝入內存。動態(tài)鏈接通常適用于系統(tǒng)庫需要操作系統(tǒng)的幫助動態(tài)鏈接鏈接延遲到執(zhí)行時152.交換（swapping)進程可以暫時從內存中交換到備份存儲(backingstore)上，當需要再次執(zhí)行時再調回到內存backingstore–通常是快速磁盤優(yōu)先級調度算法中使用滾出（rollout）,滾入（rollin）交換時間轉移時間，而轉移時間與交換內存空間量成正比問：將交換出的進程再交換（調回）回來的時候，應調回哪個內存空間（編譯時，加載時，執(zhí)行時）2.交換（swapping)進程可以暫時從內存中交換到備份16操作系統(tǒng)內存管理-課件17連續(xù)分配內存通常分為兩個區(qū)域：一個用于駐留操作系統(tǒng)，常與中斷向量一起放在低內存另一個用于用戶進程，常放在高內存。單分區(qū)分配方法（Single-partitionallocation）重定位寄存器方案用來保護用戶進程之間，用戶進程與操作系統(tǒng)之間不會相互修改代碼與數據重定位寄存器包含了最小的物理地址；界限寄存器包含了邏輯地址的范圍，每個邏輯地址必須小于界限寄存器連續(xù)分配內存通常分為兩個區(qū)域：18重定位和界限寄存器的硬件支持重定位和界限寄存器的硬件支持19多分區(qū)分配方法孔（Hole）：一塊可用內存稱為孔。不同大小的孔分布在內存的不同地方。當有新進程需要內存時，為該進程查找足夠大的孔。操作系統(tǒng)維護的信息包括：已分配分區(qū)空閑分區(qū)（hole）多分區(qū)分配方法20動態(tài)存儲分配問題根據一組空閑孔來分配大小為n的請求。首次適應（First-fit）最佳適應（Best-fit）最差適應（Worst-fit）First-fit和best-fit在分配速度及存儲效率上優(yōu)于Worst-fit動態(tài)存儲分配問題根據一組空閑孔來分配大小為n的請求。21碎片（Fragmentation）外部碎片內部碎片緊縮（compaction）：用來降低外部碎片移動內存內容，以便所有空閑空間合并成一整塊。如果重定位是動態(tài)的，是在運行時進行的，那么就能采用緊縮另一種可能解決外部碎片問題的方法是允許物理地址空間為非連續(xù)，這樣只要有物理內存就可為進程分配。分頁分段碎片（Fragmentation）外部碎片22分頁(Paging)一個進程的物理地址可以是非連續(xù)的將物理內存分成固定大小的塊，稱為幀（frame）將邏輯內存分為同樣大小的塊，稱為頁（page）跟蹤所有的空閑幀建立頁表用來將邏輯地址轉換為物理地址。內部碎片分頁(Paging)一個進程的物理地址可以是非連續(xù)的23地址轉換方法CPU生成的地址分成以下兩部分頁號(p)：頁號作為頁表中的索引。頁表中包含每頁所在物理內存的基地址。頁偏移(d)：與頁的基地址組合就形成了物理地址，就可送交物理單元。地址轉換方法CPU生成的地址分成以下兩部分24地址轉換體系結構地址轉換體系結構25邏輯內存和物理內存的分頁模型邏輯內存和物理內存的分頁模型26分頁示例分頁示例27空閑幀空閑幀28頁表的實現頁表保存在內存中頁表基寄存器（PTBR）指向頁表頁表長度寄存器（PTLR）指示頁表的大小在這種方式下，每次數據/指令的訪問需要訪問兩次內存。一次訪問頁表，另一次訪問數據/指令兩次內存訪問問題可以用特別的快速查找硬件緩沖（稱為關聯(lián)內存或翻譯后備緩沖器）來解決。頁表的實現頁表保存在內存中29關聯(lián)存儲關聯(lián)內存－并行搜索當關聯(lián)內存根據給定值查找時，它會同時與所有鍵進行比較。如果找到條目，那么就得到相應的值域地址轉換（A’,A’’）如果A’在關聯(lián)寄存器中，則直接取出其對應的frame#否則從內存中的頁表當中得到frame#Page#Frame#關聯(lián)存儲關聯(lián)內存－并行搜索Page#Frame#30帶TLB的分頁硬件帶TLB的分頁硬件31內存保護內存保護通過與每個幀關聯(lián)有保護位來實現?？勺x、可寫、只可讀還有一位與頁表中的每一條目相關聯(lián)，稱為有效－無效位一個進程很少會使用其所有的地址空間。事實上，許多進程只使用一小部分可用的地址空間。如對于14位地址空間（0-16383）的系統(tǒng)，有一個程序，其地址空間為0-10648該位有效時表示相關的頁在進程的邏輯地址空間內，因此是合法的頁。該位無效時表示相關的頁不在進程的邏輯地址空間內。內存保護內存保護通過與每個幀關聯(lián)有保護位來實現。32頁表中的有效－無效位頁表中的有效－無效位33頁表結構層次化分頁Hash頁表反向頁表頁表結構層次化分頁34層次化分頁將邏輯地址空間分成多個頁表一種簡單的方法是兩層分頁法層次化分頁將邏輯地址空間分成多個頁表35兩層分頁方法實例邏輯地址（32位機器，頁大小為4K）分成以下兩部分：頁號（20位）頁偏移（12位）頁表又分成頁，所以頁號又進一步分成：10位頁號10位頁偏移因此，邏輯地址表示如下兩層分頁方法實例邏輯地址（32位機器，頁大小為4K）分成以下36操作系統(tǒng)內存管理-課件37兩級頁表方法示意兩級頁表方法示意38地址轉換方法地址轉換方法39Hash頁表處理超過32位地址空間的常用方法是使用Hash頁表。虛擬地址中的虛擬頁號被放入hash頁表中。hash頁表的每一條目都包括一個鏈接組的元素，這些元素hash成同一位置（碰撞）。虛擬頁號與鏈表中的每一個元素的第一個域相比較。如果匹配，那么對應的幀碼就用來形成位置地址。如果不匹配，那么就對鏈表中的下一個域進行頁碼比較。Hash頁表處理超過32位地址空間的常用方法是使用Hash頁40Hash頁表實例Hash頁表實例41反向頁表反向頁表對于每個真正的內存頁或幀才有一個條目。每個條目包含保存在真正內存位置的頁的虛擬地址，以及擁有該頁的進程的信息。雖然這種方案減低了存儲每個頁表所需要的內存空間，但是當引用頁時它增加了查找頁表所需要的時間?？墒褂胔ash表來減少查找的次數反向頁表反向頁表對于每個真正的內存頁或幀才有一個條目。42反向頁表結構反向頁表結構43共享頁共享代碼可以在進程之間共享共同代碼（只讀的，可重入的）（如文本編輯器、編譯器、Windows系統(tǒng)）共享代碼必須出現在所有進程邏輯地址的同一位置私有代碼和數據每個進程保留了代碼與數據的獨立的拷貝私有代碼和數據頁可以出現在邏輯地址空間的任何地方。共享頁共享代碼44共享分頁實例共享分頁實例45分段支持用戶觀點的內存管理方法程序是若干段的集合主程序子程序函數方法對象局部變量，全局變量堆棧符號表，數組分段支持用戶觀點的內存管理方法46用戶角度的程序用戶角度的程序47段的邏輯視角段的邏輯視角48段的體系結構邏輯地址由兩個元素組成<段號，偏移>段表：將二維的用戶定義地址映射為一維物理地址。段表的每個條目都有段基地址和段界限?；刂罚喊蔚钠鹗嫉刂方缦蓿褐付ǘ蔚拈L度段表基地址寄存器（STBR）指向內存中的段表的位置段表長度寄存器（STLR）指示程序所用的段的個數段號S小于STLR的時候才是有效的段的體系結構邏輯地址由兩個元素組成49段硬件段硬件50分段實例分段實例51段共享段共享52問題外部碎片問題外部碎片53帶分頁的分段MULTICS采用帶分頁的分段方法來解決外部碎片的問題與純粹的分段式內存管理不同，段表的條目包含的不是段的基地址，而是該段的頁表的基地址帶分頁的分段MULTICS采用帶分頁的分段方法來解決外部碎片54內存管理內存管理55目的詳細描述內存硬件的各種組織方法討論各種內存管理技術，包括分頁和分段詳細描述IntelPentium芯片，它支持純分段和帶分頁的分段目的詳細描述內存硬件的各種組織方法56背景為了運行程序必須把程序從磁盤載入到內存內存和寄存器是CPU唯一能直接訪問的存儲器寄存器的訪問時間vs內存的訪問時間緩存為了確保正常運行必須保護內存背景為了運行程序必須把程序從磁盤載入到內存57首先討論：符號內存地址到實際物理地址的綁定邏輯地址與物理地址的區(qū)別動態(tài)裝載、動態(tài)鏈接代碼及共享庫首先討論：58在計算機科學中，庫是用于開發(fā)軟件的子程序集合。庫和可執(zhí)行文件的區(qū)別是，庫不是獨立程序，他們是向其他程序提供服務的代碼。庫鏈接是指把一個或多個庫包括到程序中，有兩種鏈接形式：靜態(tài)鏈接和動態(tài)鏈接，相應的，前者鏈接的庫叫做靜態(tài)庫后者的叫做動態(tài)庫。在計算機科學中，庫是用于開發(fā)軟件的子程序集合。庫和可59靜態(tài)鏈接是由鏈接器在鏈接時將庫的內容加入到可執(zhí)行程序中的做法。鏈接器是一個獨立程序，將一個或多個庫或目標文件（先前由編譯器或匯編器生成）鏈接到一塊生成可執(zhí)行程序。靜態(tài)鏈接的最大缺點是生成的可執(zhí)行文件太大，需要更多的系統(tǒng)資源，在裝入內存時也會消耗更多的時間。靜態(tài)鏈接是由鏈接器在鏈接時將庫的內容加入到可執(zhí)行程序中的做法60動態(tài)鏈接，在可執(zhí)行文件裝載時或運行時，由操作系統(tǒng)的裝載程序加載庫。大多數操作系統(tǒng)將解析外部引用（比如庫）作為加載過程的一部分。動態(tài)鏈接，在可執(zhí)行文件裝載時或運行時，由操作系統(tǒng)的裝載程序加61基地址寄存器和界限地址寄存器一個進程使用的內存地址范圍是由一對基地址寄存器和界限地址寄存器來定義基地址寄存器和界限地址寄存器一個進程使用的內存地址范圍是由一62一個用戶程序的多步驟處理一個用戶程序的多步驟處理63地址綁定地址綁定是從一個地址空間到另一個地址空間的映射將指令與數據綁定到內存，有以下幾種情況不知道駐留地址地址綁定地址綁定是從一個地址空間到另一個地址空間的映射不知道64邏輯地址空間和物理地址空間邏輯地址：CPU所生成的地址–(虛擬地址)物理地址：從內存單元所看到的地址綁定內存管理單元(MMU)邏輯地址空間和物理地址空間邏輯地址：CPU所生成的地址–(65內存管理單元（MMU）映射虛擬地址為物理地址的硬件設備

用戶進程所生成的地址在送交內存之前，都將加上重定位寄存器（基地址寄存器）的值

用戶程序決不會看到真正的物理地址內存管理單元（MMU）映射虛擬地址為物理地址的硬件設備

66庫的鏈接及加載靜態(tài)鏈接動態(tài)鏈接（dynamiclink）動態(tài)加載（dynamicloading）庫的鏈接及加載靜態(tài)鏈接67動態(tài)加載直到被調用之前，程序不會被載入到內存，即加載延遲到運行時優(yōu)點不使用的程序不會載入到內存，既而內存使用率高適合用戶用大量代碼來操作不常發(fā)生事件時不需要操作系統(tǒng)的特別支持，由程序員來設計動態(tài)加載直到被調用之前，程序不會被載入到內存，即加載延遲到運68動態(tài)鏈接鏈接延遲到執(zhí)行時小程序,stub（存根）,用來定位適當的內存駐留庫程序，或如果該程序不在內存時應如何裝入庫存根會用子程序地址來替換自己，并開始子程序存根首先檢查所需子程序是否在內存中，如果不在，就將子程序裝入內存。動態(tài)鏈接通常適用于系統(tǒng)庫需要操作系統(tǒng)的幫助動態(tài)鏈接鏈接延遲到執(zhí)行時692.交換（swapping)進程可以暫時從內存中交換到備份存儲(backingstore)上，當需要再次執(zhí)行時再調回到內存backingstore–通常是快速磁盤優(yōu)先級調度算法中使用滾出（rollout）,滾入（rollin）交換時間轉移時間，而轉移時間與交換內存空間量成正比問：將交換出的進程再交換（調回）回來的時候，應調回哪個內存空間（編譯時，加載時，執(zhí)行時）2.交換（swapping)進程可以暫時從內存中交換到備份70操作系統(tǒng)內存管理-課件71連續(xù)分配內存通常分為兩個區(qū)域：一個用于駐留操作系統(tǒng)，常與中斷向量一起放在低內存另一個用于用戶進程，常放在高內存。單分區(qū)分配方法（Single-partitionallocation）重定位寄存器方案用來保護用戶進程之間，用戶進程與操作系統(tǒng)之間不會相互修改代碼與數據重定位寄存器包含了最小的物理地址；界限寄存器包含了邏輯地址的范圍，每個邏輯地址必須小于界限寄存器連續(xù)分配內存通常分為兩個區(qū)域：72重定位和界限寄存器的硬件支持重定位和界限寄存器的硬件支持73多分區(qū)分配方法孔（Hole）：一塊可用內存稱為孔。不同大小的孔分布在內存的不同地方。當有新進程需要內存時，為該進程查找足夠大的孔。操作系統(tǒng)維護的信息包括：已分配分區(qū)空閑分區(qū)（hole）多分區(qū)分配方法74動態(tài)存儲分配問題根據一組空閑孔來分配大小為n的請求。首次適應（First-fit）最佳適應（Best-fit）最差適應（Worst-fit）First-fit和best-fit在分配速度及存儲效率上優(yōu)于Worst-fit動態(tài)存儲分配問題根據一組空閑孔來分配大小為n的請求。75碎片（Fragmentation）外部碎片內部碎片緊縮（compaction）：用來降低外部碎片移動內存內容，以便所有空閑空間合并成一整塊。如果重定位是動態(tài)的，是在運行時進行的，那么就能采用緊縮另一種可能解決外部碎片問題的方法是允許物理地址空間為非連續(xù)，這樣只要有物理內存就可為進程分配。分頁分段碎片（Fragmentation）外部碎片76分頁(Paging)一個進程的物理地址可以是非連續(xù)的將物理內存分成固定大小的塊，稱為幀（frame）將邏輯內存分為同樣大小的塊，稱為頁（page）跟蹤所有的空閑幀建立頁表用來將邏輯地址轉換為物理地址。內部碎片分頁(Paging)一個進程的物理地址可以是非連續(xù)的77地址轉換方法CPU生成的地址分成以下兩部分頁號(p)：頁號作為頁表中的索引。頁表中包含每頁所在物理內存的基地址。頁偏移(d)：與頁的基地址組合就形成了物理地址，就可送交物理單元。地址轉換方法CPU生成的地址分成以下兩部分78地址轉換體系結構地址轉換體系結構79邏輯內存和物理內存的分頁模型邏輯內存和物理內存的分頁模型80分頁示例分頁示例81空閑幀空閑幀82頁表的實現頁表保存在內存中頁表基寄存器（PTBR）指向頁表頁表長度寄存器（PTLR）指示頁表的大小在這種方式下，每次數據/指令的訪問需要訪問兩次內存。一次訪問頁表，另一次訪問數據/指令兩次內存訪問問題可以用特別的快速查找硬件緩沖（稱為關聯(lián)內存或翻譯后備緩沖器）來解決。頁表的實現頁表保存在內存中83關聯(lián)存儲關聯(lián)內存－并行搜索當關聯(lián)內存根據給定值查找時，它會同時與所有鍵進行比較。如果找到條目，那么就得到相應的值域地址轉換（A’,A’’）如果A’在關聯(lián)寄存器中，則直接取出其對應的frame#否則從內存中的頁表當中得到frame#Page#Frame#關聯(lián)存儲關聯(lián)內存－并行搜索Page#Frame#84帶TLB的分頁硬件帶TLB的分頁硬件85內存保護內存保護通過與每個幀關聯(lián)有保護位來實現。可讀、可寫、只可讀還有一位與頁表中的每一條目相關聯(lián)，稱為有效－無效位一個進程很少會使用其所有的地址空間。事實上，許多進程只使用一小部分可用的地址空間。如對于14位地址空間（0-16383）的系統(tǒng)，有一個程序，其地址空間為0-10648該位有效時表示相關的頁在進程的邏輯地址空間內，因此是合法的頁。該位無效時表示相關的頁不在進程的邏輯地址空間內。內存保護內存保護通過與每個幀關聯(lián)有保護位來實現。86頁表中的有效－無效位頁表中的有效－無效位87頁表結構層次化分頁Hash頁表反向頁表頁表結構層次化分頁88層次化分頁將邏輯地址空間分成多個頁表一種簡單的方法是兩層分頁法層次化分頁將邏輯地址空間分成多個頁表89兩層分頁方法實例邏輯地址（32位機器，頁大小為4K）分成以下兩部分：頁號（20位）頁偏移（12位）頁表又分成頁，所以頁號又進一步分成：10位頁號10位頁偏移因此，邏輯地址表示如下兩層分頁方法實例邏輯地址（32位機器，頁大小為4K）分成以下90操作系統(tǒng)內存管理-課件91兩級頁表方法示意兩級頁表方法示意92地址轉換方法地址轉換方法93Hash頁表處理超過32位地址空間的常用方法是使用Hash頁表。虛擬地址中的虛擬頁號被放入hash頁表中。hash頁表的每一條目都包括一個鏈接組的元素，這些元素hash成同一位