現代作業系統-記憶體管理

記憶體管理

地址空間

概念

地址空間是，一個程序可用於定址記憶體的，一套地址，的集合。每個程序都有自己的地址空間，並且這個地址空間獨立於其他程序的地址空間（除非有共享）。

在這裡介紹一下基址暫存器和界限暫存器。他們的主要作用是給出實際地址的地址偏移量和地址範圍。程式的起始物理地址裝載進基址暫存器中，程式的長度放在界限暫存器裡。缺點在於，每次訪問記憶體都需要進行加法和比較運算。

交換技術

主要原理就是：把一個程序完整的調入記憶體，執行一段時間，再存回磁碟，空閒程序主要在磁碟上。

但是交換空間可能出現多個小記憶體空閒區的情況，這時可以使用記憶體壓縮技術，這個技術比較吃CPU。

程序需要增長，所以可以透過把它移動到更大的空間來實現，或者移除它相鄰的程序。如果一個程序在記憶體中不能增長，並且磁碟空間也滿了，那麼只能把它掛起直到有可用空間。

不過，可以預先分配足夠大的記憶體，供後期增長；在移出時，僅僅移除已使用的記憶體。

在一個程序中，具體來說一般都是堆疊和資料會增長，正文一般不會動，那麼可以把堆疊放程式空間的上面，資料放下面，中間是可以供增長使用的空閒空間。

空閒記憶體管理

使用點陣圖的儲存管理。這種方式類似鄰接矩陣，用0和1記錄某個記憶體塊是否被佔用。分割的記憶體塊的大小決定了點陣圖的大小。缺點很明顯，在記憶體很大時，需要很大的點陣圖來儲存，這本身就很佔用記憶體；而且在查詢可用的位置時，需要遍歷整個圖，這是一個耗時的操作。

使用連結串列的儲存管理。簡單來說就是，每個節點包含一個指向前面節點的指標和指向後面節點的指標，一個記錄當前位置是空閒還是使用的標誌，起始地址（記憶體塊的地址，但記憶體塊是好幾個位元組組成的，這個起始地址就是這個記憶體塊最左邊的地址），長度（此記憶體塊多大）。

對於改變某個節點狀態，會產生四種結果，如果當前節點被置為空閒且相鄰節點也是空閒的，可以把他們合併，所以四種操作如下所示：

那麼如何找到需要大小的記憶體呢？來看幾個演算法：

首次適配演算法

，會沿著連結串列一直找，直到找到足夠的空閒區。

下次適配演算法

，在首次適配的基礎上記錄一下位置，方便下次使用，看起來很好，可是實際效能還不如首次適配。

最佳適配演算法

，遍歷整個連結串列，找到最小可用空閒區，雖然其本意在於減小記憶體使用，但實際上，它會產生大量小的空閒區，反而浪費了記憶體。

最差適配演算法

，每次找最大可用的空閒區，但實際使用也不咋地。

如果分離程序和空閒區，分出兩個連結串列，各自維護，可能會高效，但是代價是增加了複雜度和記憶體釋放（兩個連結串列均實行了操作）。

還可以對連結串列排序；或者，打表，就是為那些常用大小的空閒區維護一個連結串列，每次需要直接獲取。這個叫

快速適配演算法

這些演算法都有一個缺點，就是在程序換出或終止時，需要程序合併操作，這是一件耗時的事。

虛擬記憶體

虛擬記憶體的基本思想是，每個程式都有自己的地址空間，這些地址空間被分割成許多塊，每一塊被稱為頁面（頁），每一頁有連續的地址範圍，但是頁與頁之間不一定；這些頁被對映到物理記憶體中，但是不是全部頁都被對映到了。當程式訪問未對映的頁時，會觸發缺頁中斷，此時有系統進行建立對映（包括找到另一個頁框，備份，寫入新資料，建立對映關係），然後重新執行剛剛被中斷的指令。

當一個程序等待它的一部分讀入記憶體中時，可以把CPU交給別的程序使用。

注意，程式向作業系統申請記憶體，作業系統派給記憶體（虛擬記憶體），一般情況下都是作業系統為當前程序選定一大塊區域給它用，程序不知道這個事情，他只管要，系統封裝了細節。一般來說，申請來的記憶體都是那一大塊記憶體裡的（雖然這一大塊也是虛擬的，不過透過對映，對程式來說那就是真實的記憶體）

分頁技術

由程式產生的這些地址稱為虛擬地址，他們構成了一個虛擬地址空間，在使用虛擬記憶體的計算機上，虛擬地址被送到記憶體管理單元（MMU）中，進行解析得到物理地址或進行重新對映。虛擬地址空間按照固定大小劃分成一個個的頁面，而在物理記憶體中，與頁面大小一致且與頁面對應的，是叫頁框的東西。那便是頁面對映的目標了。

頁表

頁表就像一個函式一樣，可以把虛擬地址對映到具體的（精確到位元組的）物理記憶體地址。它定義了頁面與頁框的一一對應的對映關係。

MMU內部大概如下所示，裡面有一個頁表，指出了頁面如何對映到頁框：

對於輸入，假設是一個16位數，那麼前4位作為頁號（頁表的下標），後12位作為偏移量，得出的地址為定位到的頁表項的值（新的4位）+偏移量。

一個頁表包含很多項，每項的大概結構如下所示：

來看一下具體各項引數的意義：

頁框號

用來定位實際的地址。

在/不在位

用來標識此項是否可用。

保護位

用來指出可進行的操作，是讀還是寫還是執行。

修改位

記錄調入記憶體後頁面是否被修改過。

訪問位

記錄被訪問的次數。

快取記憶體禁止位

指出是否開啟快取記憶體。

關於快取記憶體位，如果是即時IO操作，最好關掉，不然可能會造成讀取失敗。關於訪問位，那是給作業系統看的，用來決定置換哪個頁面。

加速分頁過程

轉換檢測緩衝區 TLB，又稱快表，用來記錄常使用的對映關係，這樣在需要的時候直接查表就可以了，而不需要透過MMU進行轉換。TLB中含有頁表項的大多數，除了虛擬頁號外（它在頁表中起到索引的作用，而在TLB中，整個虛擬地址就是索引（陣列下標），故不再需要虛擬頁號的存在），幾乎都有。

如果某次執行匹配，發現TLB沒有此項，會在MMU查詢之後從TLB中淘汰一個，並進行替換。

軟體TLB管理 在記憶體中申請一塊地址，儲存TLB表，剛剛的那種方式是透過硬體實現的；這種軟體的方式是交付給OS來實現。此時的OS不僅進行TLB維護，還進行TLB更新，頁面替換，缺頁中斷處理等。不過要記得在TLB中固定這個軟體TLB的地址，防止被替換，那就是“我殺我自己”了，就很尷尬。

來看看軟失效和硬失效。

軟失效

查詢的頁面不在TLB但在記憶體中，這種不需要磁碟IO操作。

硬失效

需要硬碟IO操作，並置換頁面，更新對映關係，進行頁表遍歷（在頁表結構中查詢相應的對映）這個操作是軟失效的百萬倍耗時。

次要缺頁錯誤

指的是需要的資料已經被其他某個程序調入記憶體，此時重新整理對映關係就好。

嚴重缺頁錯誤

指的是需要從磁碟調入某個資料到記憶體中並建立對映關係。

針對大記憶體的頁表

把整個頁表儲存在記憶體裡不一定可以，尤其是在記憶體很大的情況下，那就一點都不現實了。來看兩個解決方法。

多級頁表

使用兩個或多個頁表進行對映，為什麼這麼設計呢？因為對一個程式來說，給它分配的記憶體，尤其是中間的空閒區（用來增長的）根本沒必要加進去，而這些空閒區往往還佔了很大的空間，所以採用分級的方法，就能減少表的大小。

比方說在頂級頁表的第0級，儲存程式正文，倒數第一級，儲存堆疊，倒數第二級儲存資料，中間都是不用的。然後剛剛的三級分別指向三個二級頁表，每個二級頁表再對映到頁框上，這樣，只需要四個頁表就能儲存了。

對於頂級頁表中間的，把他們的在/不在位設為0，禁止程式訪問，這樣可以監控程式的行為。

倒排頁表 剛剛那種都是頁面對映頁框，注意，在實際上可能是多個頁面對映一個頁框（當前是A程序對映頁框A，過會可能是B程序對映頁框A，但是頁表都記下來了），但是實際執行只有一個頁面和一個頁框在對映。所以可以設計某種方式，讓一個頁框對應多個頁面，這樣就節省很多空間了。

但是這種方式有一個弊端，就是想找到頁面對應的頁框時，得全部遍歷，即使有TLB，這也不是個好辦法，於是乎，可以使用雜湊表，獲取虛擬地址的雜湊值，再使用連結法，把他們連結起來，注意，此時連結的是一個個的小結構體，它們由頁面和頁框組成，所以還是可以找到頁面對應的頁框的。

此方法在64位機裡很常見。

頁面置換演算法

在執行頁面置換之前，記得進行備份頁框的資料。如果準備換出的頁面在記憶體上被修改過，記得備份到硬碟，否則直接覆蓋。

最優頁面置換演算法

透過某種神奇的方式獲取最不常用的頁面並置換，可是不可能實現。

最近未使用頁面置換演算法

對於頁面，定期的把它的R位（訪問位）清零，以區別最近沒有被訪問的頁面和被訪問的頁面。

當發生缺頁中斷時，作業系統檢查R位和M位（修改位）的值，並把頁面分為四類：

第0類：沒有被訪問，沒有被修改； 第1類：沒有被訪問，已被修改； 第2類：已被訪問，沒有被修改； 第3類：已被訪問，已被修改；

當準備置換時，從編號最小且非空類裡選一個頁面出來。

先進先出頁面置換演算法

排個隊，每次把新加入的頁面排到隊尾，替換時優先選擇隊首的。

第二次機會頁面置換演算法

在先進先出演算法的基礎上，檢查R位，如果是0，就置換，否則置0並加到隊尾。

時鐘頁面置換演算法

類似第二次機會演算法，但是是環形連結串列形式的。

當發生缺頁中斷時，首先檢查當前指標指向的頁面R位，是0就替換，並前移指標，否則置0前移指標。

最近最少使用頁面置換演算法

此方法要求有一個硬體計數器，在每條指令執行完後自增，然後訪問頁面時自動加到頁面上去，這個值代表頁面的上次使用時間，越小說明頁面越舊，最後替換就行，可是難點在於，不好實現。

用軟體模擬LRU

在這裡，為每個頁面新增程式計數器，然後使用一種老化演算法，首先，在R位被加到計數器之前，右移一位計數器，再把R加到左邊，這樣就完成了更新。這樣就能保證計數器越大，頁面被訪問越頻繁。

該演算法和LRU的區別是老化計數器只有有限位數，所以沒法更細緻的區分頁面。

工作集頁面置換演算法

首先明確幾個概念。一個執行緒當前正在使用的頁面的集合被稱為

工作集

。若每執行幾條指令就發生一次缺頁中斷，那麼成這個程式發生了

顛簸

。

在多道程式設計系統中，經常把程序轉移到磁碟上（移走全部頁面），但是再轉換回來就很容易發生缺頁中斷，遂引入

工作集模型

，確保程序在執行前，它的工作集就已經在記憶體中了。在程式執行前預先裝入其工作集頁面也稱為

預先調頁

。

工作集是隨時間變化的，設在任意時刻t都存在一個集合，它包含最近k次記憶體訪問所訪問過的全部頁面，這個集合w（k， t）就是工作集，因為最近k=1次訪問的頁面必定屬於k>1次所訪問的頁面。所以w（k， t）是k的單調非遞減函式。當然，w（k， t）並不能無限增大，所以得到這樣的影象：

k的值有一個很大的範圍，它處在這個範圍中時，工作集不會變，因為工作集隨時間變化很慢。預先調頁就是在程式執行之前預先推測出工作集（根據上次執行結果推測）並裝入記憶體。OS還可以根據推斷出的工作集，決定淘汰哪些個頁面。

實際實現比較困難，於是選用近似方法，考慮執行時間，什麼意思呢？程序的工作集可以定義為在過去的t秒的

實際執行時間

所訪問過的頁面的集合。然後在頁表上新增一個時間屬性。

工作過程：在時鐘中斷時，會清空R位。每次發生缺頁中斷時，就掃描頁表來找尋合適的頁面，此時檢查每個頁表的R位；

如果是1，就把當前時間寫入到頁表項的“上次使用時間”域，說明這個頁面在當前時鐘滴答（上一次時鐘中斷到現在時鐘中斷這個時間內）中已經被訪問過；

如果R是0，則可以作為候選者，然後計算它的生存時間，與t比較，如果大於t就替換它，然後繼續掃描以更新剩餘的項。

如果R=0同時生存時間小於等於t，那麼臨時留下來，但是要記錄生存時間最長的頁面，然後繼續，最後如果找到了多個R=0的頁面，那麼淘汰生存時間最長的頁面。

最最最後，如果R都為1，那隨機淘汰一個，最好淘汰一個乾淨的頁面。

工作集時鐘頁面置換演算法

此演算法類似時鐘演算法，簡述其工作流程：

首先檢查指向的頁面，如果R=1，置0移動到下一個頁面；

如果R=0且生存時間大於t且頁面乾淨，申請此頁框；如果被修改過，為了避擴音前的IO操作，指標繼續向前走；

如果回到起點，那麼肯定發生二者之一的情況：至少排程了一次寫操作；沒有排程過寫操作。

第一種情況，是我們需要的，沒話說，置換遇到的第一個乾淨的頁面；第二種，隨便選一個乾淨的頁面，所以需要遍歷途中記錄乾淨的頁面，如果這也滿足不了，那就替換當前頁面

小結

實際使用中，軟體模擬LRU頁面置換演算法和工作集時鐘頁面置換演算法比較可行。

分頁系統中的設計問題

區域性分配策略與全域性分配策略

來看一個實際的問題，如果程序進行新的對映，那麼問題來了，是替換整個虛擬空間的最合適的頁面呢？還是僅僅替換當前程序的虛擬空間的合適的頁面呢？前者叫

全域性策略

，後者叫

區域性策略

。全域性策略動態的分配程序的空間，區域性策略則是固定了程序的記憶體空間大小。

使用區域性策略需要在一開始指定合適的大小。如果使用全域性策略，那就需要PFF（缺頁中斷率）演算法來動態的更改分配給某個程序的頁面數。此演算法會計算每秒的缺頁中斷數，或者使用過去某些秒內的資料為參考，然後得出一個結果，如果缺頁中斷率過低，甚至可能剝奪某些程序的頁面（程序口吐芬芳）。如下圖所示：中斷率應保持在A和B之間。橫座標是時間。

對於某些演算法，只有區域性策略才有意義，比如兩個工作集演算法。

負載控制

如果某個程序發生了顛簸，且一直不好解決，那麼可以嘗試把一些程序移除記憶體，交換到硬碟，完全讓出空間。如果還是不行，繼續交換程序。但是並不收回他們的頁面，不過在換出時，要記得考慮程序型別（IO密集型還是計算密集型），以及程序的特性。

頁面大小

頁面大小的選擇也很重要，選擇大了，會造成浪費，選擇小了，會增加頁表大小，以及管理的複雜度。小的頁面還會佔用更多的TLB，要知道，TLB對效能而言，異常重要。傳輸一個大的頁面到硬碟和傳輸一個小的頁面差不多。最後，設程序平均大小是s位元組，頁面大小是p位元組，每個頁表項需要p位元組，我們來看看記憶體開銷：

開銷=se/p+p/2

求導得當p=（2se）^（1/2）時，開銷最小。

現在常見的頁面大小是4KB或8KB。

分離的指令空間和資料空間

在這種模式下，兩個空間分別有自己的頁表，自己的對映，自己的物理空間，分離的意義是為了更好地利用空間。程式放程式空間，資料放資料空間。

共享頁面

為了減少記憶體空間地重複，更好地增加程序間傳輸能力。

有一點，當A程序結束時，應該可以注意到A程序的某些頁面是否被共享了，是否被B程序所使用。所以需要一個專門的資料結構記錄共享介面。

當然，還要記得加上

寫時複製

，如果某個程序試圖更新共享頁面，則立馬生成此頁面地副本，這樣每個程序都有自己的副本了，記得，只有實際修改的資料頁面需要複製，這樣就能保證每個程序的獨立性了。

共享庫

如果某個程式已經裝載了某個庫在記憶體中的話，新的程序就不需要再次匯入；共享庫是以頁面為單位裝載的，需要多少便載入多少。除了實現了更好地節約記憶體，更快的效能，另一點就是更新方便，不會牽一髮而動全身，僅僅更新部分的庫就可以，而不需要整個重載入。

為了解決共享庫的地址重定位問題，在程式碼中使用相對指令的地址，這樣就可以做到與具體的位置無關了。

記憶體對映檔案

透過把檔案當成記憶體的形式對映到頁面，實現程序間的檔案共享，是檔案操作向記憶體操作一樣簡單易用。

清楚策略

為了保證有足夠的頁框可用，

分頁守護執行緒

會定期執行，使用頁面置換演算法獲取更多的頁框，並進行把原頁框的資料寫會到磁碟（如果有必要的話）。

分頁守護執行緒還可以確保頁框都是“乾淨”的，這樣可以在下次直接寫入。

虛擬記憶體介面

實現程序間的記憶體共享。

有關實現的問題

與分頁有關的工作

與分頁有關的工作，共有四個時期：程序建立時，程序執行時，缺頁中斷時，程序終止時。

程序建立:

OS確定程序需要的空間大小，然後為它們建立一個頁表並初始化並固定到記憶體中。若程序被換出，頁表就可以清除了。還有，OS還要在硬碟中分配出交換空間，用來放置換出的程式。OS還要使用程式正文和資料對交換空間程序初始化，以便進行置換頁面時方便使用。最後，OS把頁表和交換空間的資訊儲存在程序表裡。

程序執行:

當一個程序執行時，必須重置MMU，重新整理TLB（所以看得出MMU TLB僅為當前程序服務，不會記錄前一個程序的資訊）。新程序的頁表必須稱為當前頁表。

缺頁中斷:

OS讀取硬體暫存器，找到是哪個虛擬地址導致了缺頁中斷，並計算出需要的頁面，然後進行頁面置換，把磁碟的資料複製到相應的頁框中；最後，回退程式計數器，重新執行導致中斷的指令。

程序退出:

當一個程序退出時，OS釋放與它有關的頁表，頁面，和頁面所佔用的磁碟空間；當然，如果他們中的某些被共享了，就得等最後一個使用它們的程序退出才能釋放。

缺頁中斷處理的細節

一個具體的缺頁中斷處理過程如下：

硬體陷入核心，儲存程式計數器。大多數機器將當前指令的各種資訊儲存在特殊的CPU暫存器中。

啟動一個彙編程式，儲存通用暫存器和 其他易失資訊。此程式將OS作為一個函式來呼叫。

OS被啟動，讀取某個硬體暫存器，獲得導致失敗的虛擬地址，如果沒有的話，檢索程式計數器，分析計算出需要的地址。

此時OS獲得了虛擬地址，會檢查地址是否有效，存取與保護是否一致，如不一致則發出一個訊號或殺死程序。然後檢查是否有頁框可用，如果沒有就置換；

如果需要置換，那就看是否需要寫回磁碟，如果需要就掛起此程序（因為進行IO操作比較耗時）執行另一個程序，同時把此頁框標記為忙碌，禁止其他程序使用。

當從磁碟寫入頁框時，還要把這個程序掛起，執行其他程序（還是因為磁碟IO操作比較耗時）。

更新頁表，更新頁框狀態為正常

恢復到發生缺頁中斷指令以前的狀態，程式計數器重新指向這條指令。

排程引發缺頁中斷的程序，OS返回彙編程式的呼叫。

彙編指令恢復暫存器等狀態資訊，返回到使用者空間繼續執行，彷彿什麼都沒發生過。

指令備份

用來處理虛擬地址計算問題，有些CPU不好推算出虛擬地址，於是使用第二個隱藏的暫存器儲存指令。

鎖定記憶體中的頁面

確保正在進行IO操作的程序不會被移出記憶體。

後備儲存

Unix系統從檔案系統上劃分出一塊分割槽用於做交換分割槽，當系統啟動時，該交換分割槽為空，並在記憶體中單獨的記錄著它的大小。與每個程序對應的是交換分割槽的磁碟地址，儲存在程序表裡。計算頁面在磁碟中的地址很簡單，虛擬地址的偏移量加上交換空間的起始地址。

對於程序的增長，可以採用正文與資料分離的形式，分別建立交換區。

對於分配方法，有兩種，一種預先分配好，一種用時再分配。前者頁面對應的磁碟位置直接可以獲得，後者需要新的表記錄每個頁面對應的磁碟位置。

策略和機制的分離

旨在降低複雜度，讓儲存管理器作為使用者及程序執行。

分段

概念

用於解決程式增長問題，把空間劃分成一段一段的，用來實現更精細化的增長空間分配和控制

例項研究

檔案系統