前面2-11用thread舉例有提到過共享記憶體可能會發生Race Condition，而Process可以分成兩大類

• independent process(獨立行程)： 該Process無法影響其它Process的執行，同時它也不受其他Process影響，獨立的Process之間不會有任何共享資料。
• cooperating process(合作行程)：Process之間會有共享的資料，藉由共用相同的 memory space達到彼此間溝通 (Multi-processing)，那這樣也會一樣可能有race condition狀況。

Race Condition 競爭情況

相同的運作. 因執行順序不同, 造成處理的結果不同。舉例：
以下情境有兩個thread同時在對同一個變數進行存取，我故意在中間加一些sleep模擬可能因為各種因素影響執行花費時間

 fun main() {
 // 此變數是共享的記憶體
 var n = 0
 // 原本預期t1執行結果 n 是1, t2執行結果 n 是2，但結果兩個都是1，原因是t1和t2在存取變數n的時間並不是由上而下先走完t1在走t2，為了不讓cpu閒置，可能因為t1在等待過程中就先讓t2執行
 
 // thread 1
 thread {
     sleep(200)
     val temp = n
     println("thread 1 run")
     sleep(800)
     n = temp+1//
     println("thread 1 n $n")
 }
 
 // thread 2
 thread {
     val temp = n
     println("thread 2 run")
     sleep(500)
     n = temp+1//
     println("thread 2 n $n")
 }
}

執行結果
thread 2 run
thread 1 run
thread 2 sum 1
thread 1 sum 1

圖片連結

再舉一個例子，以下t1和t2各跑100圈，每一次都對n進行加一，由於t1和t2過程中取n時可能會取到相同的值(像上述狀況)，各自加1後存回給n，因此會造成結果可能不是200的情況

fun main() {
    var n = 0
    val t1 = thread {
        println("t1 start")
        (1..100).forEach {// 跑100圈
            n++
        }
        println("t1 end")
    }
    val t2 = thread {
        println("t2 start")
        (1..100).forEach {// 跑100圈
            n++
        }
        println("t2 end")
    }
    t1.join()// 等待t1執行完畢
    t2.join()// 等待t2執行完畢
    println("n $n")// 預期應該是200，實際上每次print出來結果會不同
}

執行結果
t1 start
t2 start
t1 end
t2 end
n 110

臨界區間 Critical Section

要解決RaceConditon就可以使用臨界區間(簡稱C.S)的概念，他有三大特性

1. 互斥性 - 同時間只能一個Procress進入C.S
2. 可進行性 - 不執行的Process待在剩餘區間Remainder Section(R.S)不可以妨礙其他Procress進入C.S
3. 有限性等待 - n個Procress最多等待n-1次(避免starvation)

概念其實就是很像設計了一間廁所(C.S)，對應三大特性

1. 一次只能有一個人(procress)進去
2. 其他人只能在廁所外乖乖排隊等
3. 你最多要等的人就是排在你前面的所有人

以下介紹針對兩個process(會用i和j標示)和多個procress進行臨界區間設計的演算法

2個procress_演算法_1

第一種演算法很像在廁所加了一道鎖，turn就像一把鑰匙，有鑰匙的才能開門進去，可能會發生鑰匙在我手上但我不想上廁所讓別人乾等的情況（所謂占著茅坑不拉屎最佳典範）

• 程式碼說明
  如果鑰匙在不在我手上我就不做事等他（<>是不等於的意思）
  否則我就進入C.S開始執行
  出C.S，將鑰匙給另一個procress
  走進R.S

分析：

• 滿足 mutual exclusion (互斥)
  說明：
  當 Pi, Pj 皆欲進入 C.S., 又 turn 不會同時為 i, j (因為 i 不等於 j), 故只能一個 process 進入 C.S.

• 違反 progress (可進行性)
  說明：
  當 Pj 於 R.S. 中 (因為 j 就是不想上廁所), 但 turn = j　鑰匙在j手上, 此時若 Pi 想進入 C.S., 將被卡在 while loop 中無法進入 (因為違反 progress)

2個procress_演算法_2

第二種像是每個人都有一個立牌(flag)可以舉，想上廁所的就舉牌，但你要進去之前要先看另一個人有沒有舉牌，有的話就要等他，所以就會發生兩個人同時都舉著牌子在等對方進去僵持不下

• 程式碼說明
  建一個flag array來記錄現在process想不想進去C.S，初始值都是false
  假設我現在是i，我想進去廁所，首先先把我的flag設成true(flag[i] = true)
  如果j也是true那我就不做動作
  j是false的話我就會進C.S
  出來後就把flag[i] = flase
  進入R.S

分析：

• 滿足 mutual exclusion (互斥)
  說明：
  若欲使 Pi, Pj 同時進入 C.S., 則 flag[i] = flag[j] = false, 但一開始 flag會改為 true, 因此上述情況不可能存在

• 不滿足 progress (可進行性)
  說明：
  當 Pi, Pj 皆欲進入 C.S.，則 flag[i] = flag[j] = true，此時 2 者皆會卡在 while loop 中 => deadlock，故違反 progress
  上一個範例是拿到鑰匙那個人不想進廁所，這次是兩個都想上廁所的卡在門外等對方先進去，做人好難．．．

2個procress_演算法_3(結合了1和2)

同時可以有鑰匙(turn)和知道誰想進c.s(flag)，這個我們要讓i和j執行過程表示出來會比較清楚:

分析：

• 滿足 mutual exclusion (互斥)
  說明：
  當 2 process 皆欲進入 C.S., 則 flag[i] = flag[j] = true, 但 turn 不會同時為 i, j (因為 i 不等於 j), 故只有一 process 可進入 C.S.

• 滿足 progress (可進行性)
  說明：
  當 Pj 不想進入 C.S., 又 turn = j, 且此時 flag[j] = false, 故當 Pi 想進入, 可以順利通過 while loop
  當 2 process 皆欲進入 C.S., 此時視 turn 的值為 i 或 j, 指向者可進入 C.S., 所以 No deadlock

• 滿足 Bounded Waiting (有限性等待)
  說明：
  當 Pi, Pj 皆欲進入 C.S., 而 turn = j時, 則 Pj 可進入, 若 Pj 離開後立即再度欲進入 C.S., 則：
  flag[j] = true;
  turn = i
  因為 turn = i, 故下次必由 Pj 進入 C.S. 中

明天再看多個procress進行臨界區間設計的演算法好了。

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

以下參考連結在學習過程中覺得非常有幫助：
-Chapter3-作業系統-程序間的溝通
-[OS] 作業系統筆記-Process間的溝通