iT邦幫忙

2022 iThome 鐵人賽

0
自我挑戰組

冒牌工程師上學去系列 第 37

2-14 臨界區間Bakery's algo

  • 分享至 

  • xImage
  •  

前面2-13討論到怎麼避免發生race condition情況,主要是透過臨界區間的概念,並針對2個procress的情況說明3個演算法
今天來聊多個procress時的演算法

Bakery's algo

https://ithelp.ithome.com.tw/upload/images/20221102/20141684uPV5A2GY6r.png

  • 程式說明(假設現在我是i)
    i正在選號碼牌 choosing=true
    i從現在所有process中拿到最大號碼牌+1就是i要拿的號碼牌
    i選完號碼牌 choosing=false
    開始跑迴圈,除了我以外的procress都稱為j
    當j正在挑號碼牌,我就等他不做事
    當j號碼牌不等於0而且j號碼牌小於我的號碼牌,我也等他不做事(號碼牌=0表示不需要進c.s.)
    i進c.s.
    i的號碼牌設成0
    i進r.s.

分析:

  • 滿足 mutual exclusion (互斥)
    說明:
    號碼小的先進C.S.

  • 滿足 progress (可進行性)
    說明:
    沒有要進C.S.號碼牌設成0,不會影響其他procress

  • 滿足 Bounded Waiting (有限性等待)
    說明:
    我只需要等號碼牌比我小的人

分類會依照第一篇介紹的分類架構來進行
由於是將學習過程記錄下來,如果有任何錯誤歡迎糾正

以下參考連結在學習過程中覺得非常有幫助:
-Chapter3-作業系統-程序間的溝通


上一篇
2-13 RaceConditon + 臨界區間(Critical Section)
下一篇
2-15 記憶體分配
系列文
冒牌工程師上學去42
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言