# Race Condition 是什麼？

競爭條件 (Race Condition) 兩個或兩個以上的進程或線程在更改 共享資源 (Share Resource) 時會發生的情況。

例如，假設我們有兩個 Process A 和 B，都想要訪問同一個共享變量。
如果 A 和 B 都嘗試在同一時間讀取和修改這個變量，那麼就可能會產生競爭條件。
如果沒有提供互斥存取，我們無法確定 A 和 B 的執行順序，所以最終的結果可能會有所不同。

解決方式:

• 鎖 (Locks)
• 原子變量 (Atomic Variables)

# 同步 (Synchronization)

主要目的是確保多個進程訪問共享資源時不會互相干擾，並防止由於並發訪問而可能產生的數據不一致

為了實現這一點，我們可以使用各種同步技術，

• 信號量（semaphores）
• 監視器（monitors）
• 臨界區（critical sections）

例如，有兩個進程 A 和 B，它們都想要訪問同一個共享變數 (share variable)。

# 信號量（semaphores）

• 我們可以初始化一個信號量並將其設置為 1。
• 當進程 A 想要訪問共享變量時，它會先減少信號量的值。
• 如果信號量的值大於等於 0，那麼 A 可以繼續執行並訪問共享變量。
• 否則，A 將被阻塞並等待。
• 當 A 完成對共享變量的訪問後，它會增加信號量的值，這可能會喚醒等待的進程 B

mutex semaphore = 1;

while(true){

    wait(mutex); // 檢查 > 0 通過並 - 1

        臨界區程式碼...

    signal(mutex); // 離開時 + 1

        臨界區以外程式碼...

}

# 臨界區（critical sections）

// 臨界區指的是有使用共享變數之區塊

while(true){

    (進入區段)

        臨界區程式碼...

    (離開區段)

        臨界區以外程式碼...

}

# Process 和 Thread

程序 (Process) 和 線程 (Thread) 是兩種不同的執行實體，都是 CPU 調度和執行的基本單位。

Process 有 Process Control Block (PCB)。

1. PID
2. 程式計數器 (Program counter)
3. CPU 暫存器內容
4. Stack
5. Code 區段
6. Data 區段
7. Heap

例如，假設我們有一個文字處理器程式。
該程式可能有一個主 Process 負責管理用戶界面，
以及多個線程負責處理後台任務，如保存文件、檢查拼寫和語法等。

# Context Switch 是什麼？

Context Switch（上下文切換）是一種系統事件，使得單個 CPU 能夠被多個進程共享的重要機制，它允許作業系統在多個進程之間進行切換，使得每個進程都有機會使用 CPU 來完成其執行。

1. 保存 A 的當前狀態（包括程序計數器、暫存器的值等），
2. 然後加載 B 的狀態並讓 B 運行。
3. 當要讓 A 再次運行時，作業系統會再次進行上下文切換，恢復 A 的狀態並讓 A 運行。

# DeadLock 需要滿足的 4 個條件

1. Mutual exlusion（互斥存取） :
   資源不能被多個進程同時使用。
2. Hold & Wait（持有和等待）:
   一個 Process 持有至少一個資源，同時在等待獲取額外的資源，而該資源又被其他 Process 持有。
3. No preemption（不搶佔） :
   已被持有的資源在進程使用完之前不能被強制奪取，除非該進程自願釋放資源。
   如果系統可以強制奪取資源，就可以避免死結，但這可能會導致其他問題，如飢餓或優先權反轉。
4. Circular wait（循環等待） :
   存在一個進程集合 {P1, P2, ..., PN}，其中 P1 正在等待 P2 持有的資源，P2 正在等待 P3 持有的資源，以此類推，最後 PN 正在等待 P1 持有的資源，形成一個循環等待的閉鎖環。

這些條件是導致死結的必要條件，但不是充分條件。
也就是說，如果系統中存在這些條件，死結就有可能發生，但不一定會發生。