iT邦幫忙

0

【小黑馬作業系統教室】(13) (Ch9) Page replacement algorithm- 過目即忘的可憐記憶

嗨嗨,大家好,我是心原一馬,
今天接續上一篇談發生page fault時該如何處理。

上一篇: 【小黑馬作業系統教室】(12) (Ch9)虛擬記憶體(virtual memory),作業系統的「偷天換日大法」

在上一篇中,
我們介紹了虛擬記憶體中非常重要的概念- Page Fault。
Page fault 就是當一支程式(process)要去真實記憶體拿資料時,
發現資料並不在記憶體裡面。
這時,如果真實記憶體已經滿了,
OS只好先把其它process的資料搬回硬碟(disk)裡,
再把該程式要的資料搬進記憶體中。

誰是那個受害者?

注意在上述步驟中,「OS只好先把其它process的資料搬回硬碟(disk)裡」,
我們戲稱那被搬走的資料稱為「受害者」。
那麼OS如何決定由誰來當那個受害者呢?
OS用來決定誰成為「受害者」的策略即稱為「Page replacement algorithm」。
當然,我們希望操作上能夠使Page fault愈低愈好,
畢竟Page fault要把disk的資料搬進memory中,時間的代價實在太高。

比喻- 人的一生中會碰到許多人,人腦記憶體容量卻有限

講「Page replacement」感覺上還是太抽象了,
小馬試著用生動的比喻講這個問題:

  • 人的一生中會碰到許多人(可能在不同時間重複碰到),例如: 1,2,3,4,1,2,5,1,2,3,4,5,每個數字代表一個人(比喻process想去真實記憶體中拿的資料)
  • 但人腦的記憶體容量有限,比如說你只能記住3個人,如果想記住新的人,必須刪除過去的記憶(比喻真實記憶體空間有限)
  • 若你看到一個人但不認得他,便稱為一次「尷尬」(比喻page fault),這也包含初次見面的情況
  • 發生「尷尬」後,你必然會想辦法記住眼前的人(比喻將disk的資料搬到真實記憶體中)
  • 你很害怕「尷尬」,可能的話你希望盡量避免,但你一生中注定遇到的人也許比自己大腦記憶體容量還多…

了解題意了嗎?現在便以這個生動的比喻來分析囉。
假設你命中注定接下來12天遇見的人為「1,2,3,4,1,2,5,1,2,3,4,5」,
你的大腦記憶體容量只能記住三個人。
目標則是讓「尷尬」的次數愈少愈好,
以下有三種常見的記憶策略:

1. 先來先忘記憶法- First in first out(FIFO) algorithm

一個很單純的策略,你的大腦先在進行「遺忘」時,優先忘記最早認識的那個人
以下畫個圖示表示:
https://ithelp.ithome.com.tw/upload/images/20191110/20117114SciCbiQ1P9.png

帶大家讀這張圖:
第0天- 你沒有遇到任何人,大腦記憶體空白
第1天- 你遇到「1號」,初次見面你不認識他,發生一次「尷尬」,然後你記住他了
第2天- 你遇到「2號」,初次見面你不認識他,發生一次「尷尬」,然後你記住他了
第3天- 你遇到「3號」,初次見面你不認識他,發生一次「尷尬」,然後你記住他了
第4天- 你遇到「4號」,初次見面你不認識他,發生一次「尷尬」。可是你大腦記憶體滿了,只好忘記最早認識的「1號人」,以記住「4號人」。(圖示中,愈左邊是你愈早認識的人)

以此類推,帶大家繼續讀完第5~12天發生的事:

https://ithelp.ithome.com.tw/upload/images/20191110/20117114DELeM7Kj99.png
第5天- 你遇到「1號人」,昨天你才剛把他忘了呢,發生一次「尷尬」。然後你忘記稍早認識的「2號人」,重新記住「1號人」。
第6天- 你遇到「2號人」,哎啊,昨天你才剛把他忘了,發生一次「尷尬」。你遺忘稍早認識的「3號人」,重新記住「2號人」。
第7天- 你遇到「5號人」,你不認識他,發生一次「尷尬」。你遺忘稍早認識的「4號人」以記住「5號人」。
第8天- 你遇到「1號人」,你的大腦記憶體有這個人,沒有發生尷尬。

https://ithelp.ithome.com.tw/upload/images/20191110/20117114Oru7fvS6ZK.png

第9天- 你遇到「2號人」,你的大腦記憶體有這個人,沒有發生尷尬。
第10天- 你遇到「3號人」,發生一次「尷尬」。你遺忘稍早認識的「1號人」,重新記住「3號人」。
第11天- 你遇到「4號人」,發生一次「尷尬」。你遺忘稍早認識的「2號人」以記住「4號人」。
第12天- 你遇到「5號人」,你的大腦記憶體有這個人,沒有發生尷尬。

尷尬統計 - 9次

哎呀,這結果看起來並不是很好,短短12天便發生了9次「尷尬」。
在我們繼續介紹其它記憶策略之前,
我們先來看一個不可思議的現象叫做「Belady's anormaly」。

Belady's anormaly- 記住更多人,「尷尬」反而還更多?

延續剛剛的故事,你覺得短短12天便發生了9次「尷尬」實在太慘了,
於是你跟老天說:「老天爺,為何你給我一個這麼差的大腦呢?害我碰到這麼多的尷尬。」
於是老天想想好像也對,你會碰到5個人,
可是大腦只能記住3個人,
這樣實在太慘了。
於是上天給了你更好的頭腦,告訴你:「好,你現在能夠記住4個人了。」

我們將時間回溯到第一天
一樣你接下來的12天會遇到這些人「1,2,3,4,1,2,5,1,2,3,4,5」,
但你大腦記憶體容量可以記住四個人了。
完全相同的人,相同的記憶策略
到底會發生什麼事呢?
請看圖示:

https://ithelp.ithome.com.tw/upload/images/20191110/20117114FMiMRhVU29.png
https://ithelp.ithome.com.tw/upload/images/20191110/20117114gukxNW0r7a.png
https://ithelp.ithome.com.tw/upload/images/20191110/20117114jlBKhtgKqr.png

哇,這是什麼道理?
原本大腦記憶體容量只能記住三個人只有9次尷尬,
當大腦記憶體容量升級能記住四個人時竟然有10次尷尬。
這種現象叫做「Belady's anormaly」,
當然,這是我們無法接受的事,
如果記憶體容量有4格比記憶體容量有3格的表現還差的話,
那還不如把一格記憶體容量丟掉不用算了…
所幸接下來要介紹的兩個演算法可以避開這種異常現象(此處不證明)。

2. 最優演算法- Optimal algorithm(其實就是作弊)

要實現這個演算法,
要假設你我有預知未來的超能力
我們以「上帝視角」知道接下來命中注定會遇到的12個人的名字為「1,2,3,4,1,2,5,1,2,3,4,5」。
(這邊你或許會懷疑一下,既然都能「預知未來」了,還需要記憶遇見的人嗎?
小馬給個解釋: 「預知未來」預知的是名字
真正要記的是長相
所以比如說第一天碰到「1號人」,
你仍然需要用一格大腦記憶體記住他,仍然會發生「尷尬」)
刪除記憶的策略為「最久以後再次遇見的對象優先刪除」。
我們看看這樣接下來12天會發生什麼:

https://ithelp.ithome.com.tw/upload/images/20191110/20117114mBd8mBuQef.png
在前4天時,發生的事情與FIFO演算法相同,
都因初次見面需要第一次記住他,「尷尬」不可免。
接著第5, 6天我們是認識「1號」與「2號」的,沒有「尷尬」
接下來第7天的時候是一個關鍵了:
https://ithelp.ithome.com.tw/upload/images/20191110/20117114D4pNTyANae.png

在第7天的時候,我們遇見了「5號」,
怎麼知道應該刪除「1號、2號、3號、4號」哪個人的長相記憶呢?
這時便是「預知未來」的超能力展現了,我們往未來看

  • 我們將於第8天再次遇見1號
  • 我們將於第9天再次遇見2號
  • 我們將於第10天再次遇見3號
  • 我們將於第11天再次遇見4號

「4號」是最久以後才會再次遇見的人,將其刪除,
這樣一來,等一下第8~10天碰到1~3號都不會有「尷尬」。
https://ithelp.ithome.com.tw/upload/images/20191110/20117114ccSdupgcK0.png
一直到第11天,我們再次碰到「4號」,
要決定該刪除「1號、2號、3號、4號」哪個人的長相記憶,
此時再看一次未來:

  • 我們將於第12天再次遇見5號
  • 我們不會再遇見1、2、3號了
    所以第11天時隨便刪除「1、2、3號」的記憶都行。

在超能力的幫助下,
尷尬次數 : 6次
在數學上,可以證明最優演算法的「尷尬次數」必然最少。

3. 最近最少見優先演算法- LRU (least recently used) algorithm

剛剛介紹的「最優演算法」固然好,但不實用,
因為一般來說我們不可能會有未來的資訊。
最優演算法的價值在於計算出尷尬次數的下界。

比起看「未來資訊」,
看「過去資訊」才是實作上做的出來的演算法。
LRU的刪除原則為「最近最少見到的人優先刪除」。
(FIFO則是「最早見到的人優先刪除」,與LRU不一樣)
我們跑實例看看LRU怎麼做,
假設接下來12天會遇見的人仍然是「1,2,3,4,1,2,5,1,2,3,4,5」。

在前4天時,發生的事情與前兩個演算法都相同:
https://ithelp.ithome.com.tw/upload/images/20191110/20117114usSQe9V7TR.png

接下來注意看第5天,因為遇見「1號」,
將「1號」從記憶體中更新到new的位置了。(建議跟FIFO比較以了解其差異)
https://ithelp.ithome.com.tw/upload/images/20191110/20117114qe5rBccyW5.png
接下來看第9~12天:
https://ithelp.ithome.com.tw/upload/images/20191110/20117114xAwVvv1Tjx.png

尷尬次數 : 8次

LRU演算法可說是實務上最常用的演算法,表現普遍也不錯。
以上便是Page replacement algorithm最常見的三大演算法。


尚未有邦友留言

立即登入留言