iT邦幫忙

1

【小白馬的OS筆記】(9) Page replacement algorithm 2- 如果有預知未來的超能力

延續【小白馬的OS筆記】(8) Page replacement algorithm的內容,
假設你命中注定接下來12天遇見的人仍是上一篇的「1,2,3,4,1,2,5,1,2,3,4,5」,
現在你的大腦記憶體容量能夠記住四個人了,
若你看到一個人但不認得他,便稱為一次「尷尬」(含初次見面的情況),
目標則是讓「尷尬」的次數愈少愈好。
(還沒看過這個比喻的邦友歡迎先連結至上一篇了解題意)
介紹剩下兩種演算法:

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演算法相同,
都因初次見面需要第一次記住他,「尷尬」不可免。
接下來第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

【清大101年期中考-OS】
Given a reference string 1,2,1,3,1,4,1,2,3,2. (reference string 指的便是剛剛比喻中會遇見的人) Please step-by-step show the references that cause pages faults with 3 memory frames using.
(a)FIFO
(b)Optimal
(c)LRU replacement algorithm

(往下翻以跟小馬核對答案…)




















小馬的答案(這邊給page fault的次數,如對答案有疑惑可於留言區留言):
(a) 7
(b) 5
(c) 6


尚未有邦友留言

立即登入留言