內存管理

操作系統與內存 (RAM)

操作系統的內存管理主要負責內存的分配與回收 (malloc 函數: 申請內存, free 函數: 釋放內存),地址轉換也就是將邏輯地址轉換成相應的物理地址等功能也是屬于內存管理的範疇。

CPU 尋址

現代 CPU 使用的是一種稱為虛擬尋址 (virtual addressing)的尋址方式。使用虛擬尋址,CPU需要將虛擬地址翻譯成物理地址,這樣才能訪問到真實物理內存。實際上完成虛擬地址到物理地址的轉換工作的硬件是 CPU 中的內存管理單元 (Memory Management Unit, MMU)。如下圖所示:

MMU Principle

地址空間 (虛擬地址)

如果把物理地址曝露給進程 (早期大型計算機並無物理內存的抽象) 會引發幾個嚴重問題:

  1. 如果用戶程序可以尋址內存的每個字節,它們就可以很容易地破壞操作系統,使系統慢慢停止運行。
  2. 想要同時運行 (如果只有一個 CPU 就輪流運行) 多個程序是很困難的。

要使多個應用程序同時處于內存中並且不互相影響,需要解決兩個問題: 保護 and 重定位。就像進程的概念創造了一類抽象的 CPU 以運行程序一樣,地址空間為程序創造了一種抽象的內存,該空間是一個進程可用于尋址內存的一套地址集合。每個進程都有一個自己的地址空間,並且這個地址空間獨立于其他進程的地址空間 (除了在一些特殊情況下進程需要共享它們的地址空間)。

基指寄存器 & 界限寄存器

地址空間的問題是必須給每個程序一個自己獨有的地址空間,使得一個程序中的地址24所對應的物理地址與另一個程序中的地址24所對應的物理地址不同。這個問題的解決辦法是使用動態重定位,簡單地把每個進程的地址空間映射到物理內存的不同部份。該方法是給每疙 CPU 配置基址寄存器界限寄存器。當使用基址寄存器和界限寄存器時,程序裝載到內存中連續的空閑位置且裝載期間無需重定位。當一個進程運行時,程序的起始物理地址裝載到基址寄存器中,程序的長度裝載到界限寄存器中。舉例如下:

當第一個程序運行時,裝載到這些硬件寄存器中的基址和界限值分別是0和16384。當第二個程序運行時,這些值分別是16384和32768。 如果第三個16KB 的程序被直接裝載在第二個程序的地址之上並且運行,這時基址寄存器和界限寄存器裏的值會是32768和16384。

每次一個進程訪問內存,取一條指令,讀或寫一個數據字,CPU 硬件會把地址發送到內存總線前,自動把基址值加到進程發出的地址值上。同時,它檢查程序提供的地址是否大于等于界限寄存器裏的值。如果訪問的地址超過了界限,會産生錯誤並終止訪問。

使用基址寄存器和界限寄存器重定位的缺點是,每次訪問內存都需要進行加法和比較運算。比較運算可以做得很快,但是加法運算由于進位傳遞時間的問題,在沒有使用特殊電路的情況下會顯得很慢。

操作系統內存管理機制

分塊 (塊式) 存儲管理

遠古時代的操作系統內存管理方式。將內存分為幾個固定大小的塊,每個塊中止包含一個進程。如果程序運行需要內存的話,操作系統就分配給它一塊,如果程序運行只需要很小的空間的話,分配的這塊內存很大一部份會被浪費。這些在塊中未被利用的空間,稱之為碎片

分頁 (頁式) 存儲管理

即把程序分成等長的頁 (Page),同樣內存頁被分成了和頁面同樣大小的頁框 (page frame)。一個頁可以裝到一個頁框裏。在執行程序的時後我們根據一個頁表去查找某個頁面再內存的那個頁框中,由此完成邏輯到物理的映射。相比于塊式管理的劃分力度更大,提高了內存利用率,減少了碎片。

在任何分頁系統中都需要考慮兩個主要問題以及提供解決方案:

  1. 虛擬地址倒物理地址的映射必須非常快 (加速分頁):

    • 轉換檢測緩衝區 (Translation Lookaside Buffer, TLB, 又稱為快表): 為了解決虛擬地址到物理地址的轉換速度,操作系統在頁表方案基礎之上引入了快表來加速虛擬地址到物理地址的轉換。我們可以把快表理解為一種特殊的高速緩衝存儲器 (Cache), 其中的內容是頁表的一部份或者全部內容。作為頁表的 Cache, 它的作用與頁表相似,但是提高了訪問效率。由于采用頁表做地址轉換,讀寫內存數據時 CPU 要訪問兩次內存。有了快表,有時只要訪問一次高速緩衝存儲器和一次內存,這樣可加速查找並提高指令執行速度。使用快表之後的地址轉換流程如下:
      1. 根據虛擬地址中的頁號查快表。
      2. 如果該頁在快表中,直接從快表中讀取相應的物理地址。
      3. 如果該頁不在快表中,就訪問內存中的頁表,再從頁表中得到物理地址,同時將頁表中的該映射表項添加到快表中。
      4. 當快表填滿後,又要登記新頁時,就按照一定的淘汰策略淘汰掉塊表中的一個頁。
  2. 如果虛擬地址空間很大,頁表也會很大 (處裏大虛擬地址空間):

    • 多級頁表: 引入多級頁表的主要目的是為了避免把全部頁表一直放在內存中占用過多空間,特別是那些根本就不需要的頁表就不需要保留在內存中。多級頁表屬于時間換空間的典型場景。
    • 倒排頁表: 實際內存中的每個頁框對應一個表象,而不是每個虛擬頁面對應一個表象。表像記錄了哪一個 <進程, 虛擬頁面> 對則定位于該頁框。雖然到排頁表節省了大量空間,但它會使從虛擬地址到物理地址的轉換變得困難。當進程n訪問虛擬頁面p時,硬件不再能通過把p當做只像頁表的一個索引來查找物理頁框。取而代之的是,它必須搜索整個倒排頁表來查找某一個表項 <n, p>。此外,該搜索必須對每一個內存訪問操作都要執行一次,而不僅僅是在發生缺頁中斷時執行。走出這種局面的辦法是使用 TLB。如果 TLB 能夠記錄所有頻繁使用頁面,地址轉換就可能變得像普通的頁表一樣快。但是,當發生 TLB 失效時,需要用軟件搜索整個倒排頁表 (建立一張散列表,用虛擬地址來散列)。

分段 (段式) 存儲管理

存在一個程序中變量的數量遠比其他部份的數量多時的情況,導致地址空間中分給符號表的塊可能會被裝滿,但這時其他表中可能還有大量的空間,需要一種能令程序員不用管理表擴張和收縮的方法。頁式管理雖然提高了內存利用率,但是頁的概念並無任何實際意義。段式管理提供多個互相獨立的稱為段 (segment) 的地址空間,其占用的空間要比頁小很多。段與頁的最大不同是,段是有實際意義的,每個段定義了一組邏輯信息(e.g. 主程序段 MAIN, 子程序段 X, 數據段 D 和堆棧段 S)。分段管理通過段表對應邏輯地址 (e.g. 指針裏面存儲的數值就可以理解為內存裏的一個地址,由操作系統決定) 與物理地址 (內存地址寄存器中的地址),有助于在幾個進程之間共享過程和數據。

分段 v.s. 分頁

考察點 分頁 分段
需要程序員了解正在使用這種技術嗎
存在多少線性地址空間 1 許多
整個地址空間可以超出物理存儲器的大小嗎
過程和數據可以被區分並分別被保護嗎
其大小浮動的表可以很容易提供嗎
用戶間過程的共享方便嗎
為什麽發明這種技術 為了得到大的線性地址空間而不必購買更大的物理存儲器 為了使程序和數據可以被劃分為邏輯上獨立的地址空間並且有助于共享和保護

分頁分段結合(段頁式)存儲管理

該管理機制結合了段式管理和頁式管理的優點,簡單來說段頁式管理機制就是把內存先分成若幹段,每個段又分成若幹頁,頁就是說段頁式管理機制中,段與段之間以及段的內部都是離散的。

內存超載

有兩種處裏內存超載 (內存無法存下所有進程的情況) 的通用方法,分別是使用交換 (swapping) 技術虛擬內存(virtual memory)

交換技術

即把一個進程完整調入內存,使該進程運行一段時間,然後把它存回磁盤。空閑進程主要存儲在磁盤上,所以當它們醭運行時就不會占用內存 (其中一些進程會被周期性地喚醒以完成相關工作,然後又進入睡眠狀態)。交換系統的操作如下所示:

Swapping

交換在內存中産生了多個空閑區 (hole, 也稱為空洞),通過把所有的進程盡可能地向下移動,有可能將這些小的空閑區合成一大塊。該技術稱為內存緊縮 (memory compaction)。通常不進型這個操作,因為會耗費大量 CPU 時間。

這裏需要注意一個問題,即當進程被創建或換入時應該位它分配多大的內存。如果進程大小固定不變,則分配很簡單,如果進程的空間可以增長,就會出現問題。為了減少因內存區域不夠而引起的進程交換和移動所産生的開銷,一種可用的方法是,當換入或移動進程時為它分配一些額外的內存 (為增長預留的空間)。然而,當進程被換出到磁盤時,應該只交換進程實際上使用的內存中的內,將額外的內存交換出去是一種浪費。

如果進程有兩個可增長的段,例如: 作為堆使用以供變量動態分配和釋放的數據段 and 存放普通局部變量與返回地址的堆棧段,則可以使用另一種安排,即在進程所占內存頂端的堆棧段向下增長,以及在底端的數據段向上增長。在這兩者之間的內存可以供兩個段使用。如果用完了,進程必須移動到足夠大的空閑區中 (它可以被交換出內存直到內存中有足夠空間),或者結束該進程。

Swapping (b)

空閑內存管理

在動態分配內存時,操作系統必須對其進行管理。一版友兩種方法跟蹤內存使用清況: 位圖 and 空閑區鏈表

  • 使用位圖的存儲管理: 使用位圖方法時,內存可能被劃分成數個字節的分配單元。每個分配單元對應于位圖中的一位,0表示空閑,1表示占用 (或者相反)。分配單元越小,位圖越大。因為內存的大小和分配單元的大小決定了位圖的大小,所以它提供了一種簡單的利用一塊固定大小的內存區就能對內存使用情況進行記錄的方法。這種方法的主要問題是,在決定把一個占k個分配單元的進程掉如內存時,存儲管理器必須搜索位圖,在位圖中找出有k個連續0的串。這項操作是比較耗時的,也是位圖的缺點。
  • 使用鏈表的存儲管理: 即維護一個記錄已分配內存段空閑內存段的鏈表。其中鏈表中的一個節點包含一個進程或者是兩個進程間的一塊空閑區。當按照地址順序在鏈表中存放進程和空閑區時,有幾種算法可以用來為創建的進程 (或從磁盤換入的進程)分配內存:
    • 首次適配 (first fit):存儲管理器沿著鍛煉表進行搜索,直到找到一個足夠大的空閑區,除非空閑區大小和要分配的空間大小正好一樣,否則將該空閑區分為兩部份,一部份供進程使用,另一部份形成新的空閑區。這是一種速度很快的算法,因為它盡可能少地搜索鏈表節點。
    • 下次適配 (next fit): 該算法的工作方式和首次適配算法相同,不同點是每次找到合適的空閑區時都記錄當時的位置,以便在下次尋找空閑區時從上次結束的地方開始搜索,而不是像首次適配算法那樣每次都從頭開始。其性能稍低于首次適配算法。
    • 最佳適配 (best fit): 該算法搜索整個鏈表 (從開始到結束),找出能夠容納進程的最小空閑區。其試圖找出最接近實際需要的空閑區,已最好的匹配請求和可用空閑區,而不是先拆分一個以後可能會用到的大空閑區。該算法性能低于收次適配算法,而且比首次適配算法和下次適配算法浪配更多的內存 (surprised!),因為它會産生大量無用的小空閑區。一般情況下,首次適配算法生成的空閑區更大一些。
    • 最差適配 (worst fit): 為避免最佳適配訴法所産生的問題,可以考慮該算法。即總是分配最大的可用空閑區,使新的空閑區比較大從而可以繼續使用,但這並非是個好辦法。
    • 快速適配 (quick fit): 該算法為那些常用大小的空閑區維護單獨的鏈表。其性能是十分快速的,但它和所有將空閑區按大小排序的方案一樣,都有一個共同的缺點,即在一個進程中只或被換出時,尋找它的相鄰塊並查看是否可以合並的過程是非常耗時的。如果不進行合並,內存將會很快分裂出大量進程無法利用的小空閑區。

虛擬內存

通過虛擬內存可以讓程序擁有超過系統物理內存大小的可用內存空間。虛擬內存的基本思想是: 每個程序擁有自己的地址空間,它讓每個進程産生了一種自己在獨享內存的錯覺 (每個進程擁有一片連續完整的地址空間)。而實際上,它通常是被分隔成多個物理內存碎片,還有部份占時存儲在外部磁盤上,在需要時進行交換。

局部性原理是虛擬內存技術的基礎,正是因為程序運行具有局部性原理,才可以只裝入部份程序到內存就開始運行。

局部性原理: 在某個較短的時間段內,程序執行局限于某一小部份,程序訪問的存儲空間也局限于某區域。局部性原理表現在以下兩方面:

  1. 時間局部性: 如果程序中的某條指令一旦執行,不久以後該指令可能再次執行; 如果某數據被訪問過,不久後該數據可能再次被訪問産生時間局部性的典型原因,是由于再程序中存在著大量的循環操作。
  2. 空間局部性: 一旦程序訪問了某個存儲單元,在不久之後,其附近的存儲單元也將被訪問,即程序在一段時間內所訪問的地址,可能集中在一定的範圍之內,這是因為指令通常是順序存放、順序執行的,數據也一般是以向量、數組、表等形式簇聚存儲的。

時間局部性是通過將近來使用的指令和數據保存到高速緩存存儲器中,並使用高速緩存的層次結構實現。空間局部性通常是使用較大的高速緩存,並將預取機制集成到高速緩存控制邏輯中實現。虛擬內存技術實際上就是建立了 “內存 – 外存” 的兩級存儲器結構,利用局部性原理實現高速緩存。

虛擬內存的實現需要建立在離散分配的內存管理方式的基礎上。主要有以下三種方式:

  1. 請求分頁存儲管理 (在基本分頁系統基礎上,增加了請求調頁功能和頁面置換功能以支持虛擬內存,較為常用)
  2. 請求分段存儲管理
  3. 請求段頁式存儲管理

不管是哪種實現方式,都需要:

  1. 一定容量的內存和外存: 在載入程序的時候,只需要將程序的一部份裝入內存,而其它部份留在外存,然後程序即可執行。
  2. 缺頁中斷: 如果需執行的指令或訪問的數據尚未在內存中 (稱為缺頁或缺段),則由處裏器通知操作系統將相應的頁面或段調入到內存,然後繼續執行程序。
  3. 虛擬地址空間: 邏輯地址到物理地址的轉換。

頁面置換算法

當發生缺頁中斷時,操作系統必須存中選擇一個頁面將其換出內存以騰出空間。

缺頁中斷就是要訪問的不在內存中,需要操作系統將其調入內存後再進行訪問。在這個時候,被內存映射的文件實際上成了一個分頁交換文件。

用來選擇淘汰哪頁的規則叫做頁面置換算法,可以視作淘汰頁面的規則。

常見頁面置換算法

  • OPT (最佳頁面置換): 理想情況,不可能實現,一般作為衡量其它置換算法的方法。

  • FIFO (先進先出): 總是淘汰最先進入內存的頁面,即選擇在內存中駐留時間最久的頁面進行淘汰,可能造成抛棄重要頁面的問題。

  • LRU (Least Recent Used, 最近最少使用): 該算法賦予每個頁面一個訪問字段,用來記錄一個頁面自上次被訪問以來所經曆的時間T,當需要淘汰一個頁面時,選擇現有頁面中T值最大的,即最近且最久未使用的頁面予以淘汰。

  • LFU (Least Frequently Used, 最少使用頁面排序): 該算法會讓系統維護一個按最近一次訪問時間排序的頁面鏈表,鏈表首節點是最近剛剛使用過的頁面,尾節點是最久未使用的頁面。訪問內存時,找到相應頁面,並把它移到鏈表之手。缺頁時,置換鏈表尾節點的頁面。也就是內存中使用越頻繁的頁面,被保留的時間也相對較長。