本系列博文是《現代作業系統（英文第三版）》（Modern Operating Systems，簡稱MOS）的閱讀筆記，定位是正文精要部分的摘錄了解和課後習題精解，是以不會事無巨細的全面摘抄，僅僅根據個人情況進行記錄和推薦。由于是英文版，部分内容會使用英文原文。
注：本文部分内容需要讀者對頁式、段式、段頁式記憶體管理有基本了解。
交換技術(Swapping)：記憶體緊縮、用于記憶體管理的位圖和連結清單、比對算法：首次比對、下次比對、最佳比對、最壞比對；
虛拟記憶體：前身是手工完成的覆寫技術(overlays)；記憶體管理單元MMU及位址轉換：頁表、TLB（轉換檢測緩沖區，也稱為關聯存儲器，俗稱快表）、多級頁表；
頁面排程算法
共享庫(shared libraries)/動态連結庫(DLL,Dynamic Link Libraries)
段式記憶體管理、段頁式
如果之前學習過國内的作業系統教材，TLB一般被稱為快表，而不是轉換檢測緩沖區（Translation Lookaside Buffer）或關聯存儲器（associative memory）。對于國内常見的稱呼，容易知道它是做為整個頁表的一個部分緩存，進而加快虛位址向實位址轉換的速度。是以，它和頁表的條目結構很類似。具體解釋見于P195~197，另外段式存儲管理中也可以使用TLB加速通路。對于不同地方出現的TLB，它緩沖的内容與其應用場景有關（MULTICS、Pentium等等）。可以看出，這個譯名比較形象，不過原名更具體些。
大學時學習“作業系統”的"基本分頁存儲管理方式"時，對于64位計算機、單個頁面4KB（即212B），兩級頁表已經過大而不能裝入記憶體。湯子瀛版《計算機作業系統》介紹了2種處理方式：使用三級或以上的頁表、将尋址空間降低到45位左右而不是64位。前者仍然比較繁瑣，後者可行性比較高。那時我就對前者心存疑惑：雖然能夠将需要用的頁表調入記憶體，可是它們總大小仍然很大，有沒有更好的實作？接下來看一看《現代作業系統》提供的方式：倒排頁表。下面這部分内容取自原書P200~201的整理。
先簡述下問題所在：64位計算機中，如果頁面大小為4KB，那麼64位尋址空間需要252個頁表項。假設每個頁表項大小為8B，那麼需要30PB的空間，在目前計算機發展階段顯然是不現實的。
倒排頁表是一種解決方案，正如其名所揭示的：普通的頁表是将虛位址映射成實體位址，提供的是将頁号(page number)轉化為頁框号(page frame number)的對應；這個轉化由MMU完成；而倒排頁表正相反，提供的是将頁框号轉化為頁号的對應。頁框号是實際記憶體的大小/頁面大小，是以1GB記憶體隻需要262,144個項即可，遠遠小于252這個數字。
個人認為，這個解決思路的妙處在于：32位下，頁表項總和比較少，至多兩級頁表也已夠用；而64位下，記憶體的大小（也即實體位址空間）與尋址空間（虛位址空間）相比反而顯得小了，這樣幹脆來個倒轉，不失為一個很好的方法。
當然這種解法雖然節約了大量的存儲空間，但是記憶體管理中需要的是将虛位址轉化成實體位址的機制，而不是正相反啊？這種映射是單向的，總不能每次轉化都把這個表周遊一次吧？那樣做的開銷實在是太大了。
一種解決方法是使用TLB，但是TLB也有失效(miss)的時候，這時還是需要進行查找。一個可行的方法是将所有用到的虛位址hash掉，形成一個hash表來加速查找，同樣哈希值的虛位址形成一個鍊。如果hash表的槽數與實體記憶體的頁框數一樣多，那麼哈希表各表項平均長度為1，這樣提高了查找速度。這個解決方法的演變可以見下圖3-14。
LRU，湯子瀛《計算機作業系統》譯為“最近最久未使用”，也即在緩沖的所有頁面中，缺頁中斷發生時，将最久未被使用的頁面置換出去。不過按照字面意思，Least Recently Used似乎應是《現代作業系統》中譯版的“最近最少使用”，似乎是需要統計頁面使用頻率的。這裡有必要先探讨下這個翻譯問題。這個翻譯的差別在于，副詞least修飾的是recently還是used。P206原文：
A good approximation to the optimal algorithm is based on the observation that pages that have been heavily used in the last few instructions will probably be heavily used again in the next few. Conversely, pages that have not been used for ages will probably remain unused for a long time. This idea suggests a realizable algorithm: when a page fault occurs, throw out the page that has been unused for the longest time. This strategy is called LRU (Least Recently Used) paging.
這前半段和後半段意思并不是很一緻。按照前半段的意思，用的最多的(heavily used)最應該保留；而後半段，也即LRU的定義，反而是指“最久未使用”。假設這樣一種情況，記憶體隻能容納兩個頁，如果考察的時間跨度大于2，對于0,0,...,0,1的頁面通路序列，此時通路頁面2，前半段會認為0的使用頻率最高，應該保留0，而後半段認為0是最久未被使用的，應該保留1。這樣就産生了沖突。不過既然是一個近似，按後半段更合适一些，這樣反而顯得“最近最久未使用”是一個更合适的譯法。《現代作業系統》提到的3種算法，其實都是符合定義的：
一種實作是用一個特殊連結清單，将最近最多使用的放在表頭，最近最少使用的放在表尾，每次使用到的頁面如果在連結清單中，就把它取出并放到表頭。不過這個實作一方面很耗時，并且實際上是“最近最久未使用”。
一種硬體實作是使用一個計數器，每次執行指令自增1，每個頁表項中提供一位來容納這個值，每次通路時就把計數器的值存到通路的頁表項中。淘汰頁面時選擇最小的即可。雖然很符合“最近最少使用”的含義，缺點是消耗了很多存儲空間；另外，計數器的溢出也是個問題。同樣是“最近最久未使用”。
另一種硬體實作則比較精巧。對于n個頁框的機器，提供一個n*n的矩陣，初始化為全0。當通路頁框k時，将這個矩陣第k行全設為1，第k列全設為0，此時(k,k)是0。在任意時刻，哪一行的二進制數最小，那麼它就是将被淘汰的頁面。可以發現，這種做法中，最後被通路的頁面會把它所在的行變為最大的（k列全為0，代表此列的大小影響不計；僅有k行全1，必然最大）。同時，頁面的使用頻率越高，那麼它就能“保持”的較大。即使上文中探讨的作為0,0,...0,1這種序列，仍然是保持1替換0，還是“最近最久未使用”。原書對這個實作的圖3-17：
LRU的實作比較複雜，而且可能需要借助特殊的硬體。一種軟體實作被稱為NFU(Not Frequently Used，最不常用)，每個頁面使用一個計數器，每次時鐘中斷時，将頁面的R位（是否被引用，0或1）加到計數器上。缺頁中斷時置換計數器值最小的。
這種實作的壞處是它“從不忘記任何事情”，簡單地說就是在之前計數器值比較高的頁面，即使不再通路，仍然會保持這個值；而别的頁面在後續始終無法超過。對NFU做一個小修改，就可以很好的模拟LRU：将R位增加前先計數器右移、R位增加到計數器左邊的最高位而不是右邊的最低位。修改後的算法稱為老化(aging)算法。圖3-18是一個運作執行個體，其蘊含的特征是：越高位越新，最近的使用權重最大；早期的使用記錄會随着右移而舍棄。
從中也可看出NFU與LRU的第一個差別：對于(e)，LRU隻能從3和5中二選一，3和5都在2個時鐘前通路過，而NFU會明确地喚出3。另一個差別是NFU隻能追蹤有限次（相較于LRU的前兩種實作，要少一些），比如圖中的8次。前第9次和前1000次的通路情況是無關緊要的。
如何确定頁的大小？以前我隻知道應該綜合考慮，但是如何考慮？原書P219~220是一個很好的借鑒。
假設頁面大小為p位元組，記憶體中共有n個段。
首先考慮頁内碎片。平均來看頁内碎片占了頁的1/2大小，那麼一共浪費了np/2的空間。
頁面越小，程序運作時所需記憶體越小，隻需把足夠的頁面裝載如記憶體即可；反之則越大。然而，頁面越小，需要的頁表項越多，頁表也越大。在頁傳輸這個數量級時，磁盤傳輸的時間主要花在尋道和旋轉延遲上，頁面大小不是關鍵因素，比如，裝入64個512B頁面需要64*10ms，而4個8KB可能隻需要4*12ms。
程序切換時，也表也需要重新裝載，頁面越小，裝入頁表越耗時。
最後一點可以用數學分析。如果程序大小平均s位元組，頁面大小p位元組，每個頁表項需要e位元組，那麼程序需要的頁數為s/p，占用了se/p的頁表空間， 頁内碎片在最後一頁浪費的是p/2，那麼由于頁表和頁内碎片一共的全部開銷為：
利用求導的方法，可以解出最小化開銷overhead的p值：
對于s = 1MB和頁表項為8B，最優頁面大小是4KB。
這是我大學時學習作業系統的又一個疑惑。其實從技術角度來說，是可以實作的；讀完《現代作業系統》有了新的體會：頁式更接近于硬體底層，對于程式員是透明的，你很少感受到它的存在；而段這個概念就比較熟悉了，資料段、代碼段、段保護機制這些經常被提起。段是邏輯抽象，更貼近人的思考方式而不是計算機的運作方式。頁式、段式、段頁式都是在現實中常用的，而且《現代作業系統》的作者Andrew提到：Pentium的設計者面對互相沖突的目标：純頁式、純段式、段頁式管理，高效而簡潔的實作，相當值得稱贊（"
All in all, one has to give credit to the Pentium designers. Given the conflicting goals of implementing pure paging, pure segmentation, and paged segments,
while at the same time being compatible with the 286, and doing all of this efficiently, the resulting design is surprisingly simple and clean"，如何使用段頁式管理系統提供純段式和純頁式請參考原書3.7.3節）
可以看出，對于軟體設計，應該讓邏輯層在較高的位置，貼近硬體的機制在較低的位置——這就是段頁式的處理；而不是相反，也就沒有了使用所謂的頁段式的必要了。
譯：
為什麼VAX上的TLB沒有R位？
Answer：
The R bit is never needed in the TLB. The mere presence of a page there means the page has been referenced; otherwise it would not be there. Thus the bit is completely redundant. When the entryis written back to memory, how-ever, the R bit in the memory page table is set.
分析：
題目提到VAX這個機型其實是誤導。一般頁表中都有R位（Referrence，最近是否通路過）和M位（Modified，最近是否修改過），這兩位在一些排程算法中要用到；而TLB中必然儲存的是最近引用過的頁，任何機型的TLB都沒有R位的必要。
對于一個頁面通路序列，會有一個長的重複序列0,1,...,511，末尾一個随機數字，是以這個序列形如0, 1, ... , 511,431, 0, 1, ... , 511, 332, 0, 1, ... 。問題(a)為什麼在負載小于重複序列的時候，标準的頁面置換算法（LRU、FIFO、Clock）對于這種序列非常低效？(b)如果這個程式隻有500個頁框，請描述一種好的頁面置換算法。
Answer:
(a) Every reference will page fault unless the number of page frames is 512,the length of the entire sequence.
(b) If there are 500 frames, map pages 0–498 to fixed frames and vary only one frame.
(a)就不再贅述了，對于(b)，其實是完全與提到的标準算法不一樣的，更接近于最優算法的實作，也即在能夠預計未來的情況下進行頁面管理。
一條機器指令，其功能是把一個32位字的資料裝入寄存器，指令本身包含了要裝入的字所在的32位位址。這個過程最多會引起幾次缺頁中斷？
原文稍有點拗口，需要仔細分析。首先裝載指令時，如果它是跨頁的，會引起兩次缺頁中斷；其次，如果資料所在位址也跨頁了，又将引起兩次。如果資料必須對齊，那麼後者隻有一次中斷；但是32位的指令未必要對齊，包括Pentium上也是這樣。
1.P250習題19，"a 256-KB main memory"應為256-MB，這個推論根據原書答案的計算過程而來。
本文轉自五嶽部落格園部落格，原文連結：http://www.cnblogs.com/wuyuegb2312/p/3418026.html，如需轉載請自行聯系原作者