iT邦幫忙

0

【小白馬的OS筆記】(8) Page replacement algorithm- 過目即忘的可憐記憶

【小白馬的OS筆記】(7)中,我們介紹了虛擬記憶體中非常重要的概念- 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」。

記住更多人,「尷尬」反而還更多?

延續剛剛的故事,你覺得短短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格的表現還差的話,
那還不如把一格記憶體容量丟掉不用算了…
所幸接下來要介紹的兩個演算法可以避開這種異常現象。
(末完待續…歡迎繼續收看【小白馬的OS筆記】(9))


尚未有邦友留言

立即登入留言