回顧：

• 并行用餐哲學家
• 讀者/作者問題

哲學家進餐問題

方案三：最大化并行

需要一個更復雜的解決方案來實現最大的并行性
解決方案使用：

state[N]：每個哲學家的當前狀態（THINKING， HUNGRY， EATING）

phil[N]：每個哲學家（不是forks）專用的阻塞信號量，初值為0。哲學家需要等待叉子時在此睡眠，被鄰座喚醒時再?sem_post。

• 如果他/她的鄰座正在吃飯，哲學家就會睡覺
• 如果鄰座已經完成了同步：一個信號量/互斥鎖來強制臨界區的互斥（同時更新狀態），則喚醒哲學家。

sync：一個信號量/互斥鎖強制臨界區互斥（同時更新狀態）

---

1. 思考 → 饑餓：哲學家想吃面時，先把 state[i] = HUNGRY，然后嘗試拿叉子。

2. 拿叉子條件：只有當 左右鄰居都不是 EATING 時，才能把 state[i] 設為 EATING，否則就在 phi[i] 上睡眠。

3. 吃完 → 思考：吃完后把 state[i] = THINKING，并檢查 左右鄰居 現在是否能吃（即它們是否處于 HUNGRY 且兩邊都沒人吃），如果可以就 sem_post 喚醒對應鄰居。

4. 所有對 state[] 的讀寫 都必須先拿 sync 鎖，保證一致性。

哲學家只有在他/她的鄰座不吃東西的時候才能開始吃東西

全局數據結構

#define N 5
#define THINKING 1
#define HUNGRY 2
#define EATING 3int state[N] = {THINKING, THINKING, THINKING, THINKING, THINKING};
sem_t phil[N]; // sends philosopher to sleep
sem_t sync; // 互斥鎖，保護對 state[] 的讀寫

哲學家主循環

void * philosopher(void * id) {int i = *((int *) id);while(1) {printf("%d is thinking\n", i);take_forks(i); // 試圖拿叉子printf("%d is eating\n", i);put_forks(i); // 吃完放叉子}
}

拿叉子

void take_forks(int i)
{sem_wait(&sync);        // 進入臨界區state[i] = HUNGRY;      // 宣布“我餓了”test(i);                // 檢查現在能不能吃sem_post(&sync);        // 離開臨界區sem_wait(&phil[i]);     // 如果不能吃，就在 phil[i] 上睡眠
}

?放叉子

void put_forks(int i)
{int left  = (i + N - 1) % N;int right = (i + 1) % N;sem_wait(&sync);        // 進入臨界區state[i] = THINKING;    // 吃完，回到思考狀態test(left);             // 看左鄰居現在能不能吃test(right);            // 看右鄰居現在能不能吃sem_post(&sync);        // 離開臨界區
}

?核心輔助函數

void test(int i)
{int left  = (i + N - 1) % N;int right = (i + 1) % N;/* 只有當自己饑餓且左右鄰居都不在吃時，才能開吃 */if (state[i] == HUNGRY &&state[left]  != EATING &&state[right] != EATING) {state[i] = EATING;sem_post(&phil[i]);   // 喚醒等待的哲學家}
}

給每位哲學家配一個“狀態變量 + 專屬信號量”，通過“鄰居吃完后主動叫醒我”的局部喚醒策略，既保證互斥又允許不相鄰的人同時吃，從而無死鎖且達到最大并行度。

讀者-作者問題

描述

1. 場景
   并發進程（數據庫事務、文件訪問、I/O 設備等）分兩類：
   ? 讀者：讀取記錄（變量）——只讀數據，可多線程并行；
   ? 寫者：寫入——要寫數據，必須獨占訪問，需要同步，不能與其他讀者或寫者并發。

2. 三種同步方案
   ? 方案 1：樸素實現
   簡單粗暴地加一把大鎖：任何時候只允許一個讀者或一個寫者訪問，并行度極低。
   ? 方案 2：讀者優先
   只要沒有寫者在寫，新來的讀者都可以立即讀；寫者可能長期挨餓。
   ? 方案 3：寫者優先
   一旦有寫者請求，就盡快讓它寫；讀者可能長期挨餓。

→ 核心權衡：提高并行度 vs. 避免饑餓，不同方案側重不同。

方案 1：無并行

void * reader(void * arg) {while(1) {pthread_mutex_lock(&sync);printf("reading record\n");pthread_mutex_unlock(&sync);}
}

void * writer(void * writer) {while(1) {pthread_mutex_lock(&sync);printf("writing\n");pthread_mutex_unlock(&sync);}
}

• 不管讀者還是寫者，都先對同一把互斥鎖 sync 加鎖
  pthread_mutex_lock(&sync)

• 拿到鎖以后才能 讀 或 寫，然后立即釋放鎖
  pthread_mutex_unlock(&sync)

• 結果：
  任意時刻只有 一個線程（讀者或寫者）在訪問數據，完全沒有并行讀的優勢，并行度最低，但實現最簡單、絕不會出現數據競爭。

方案 2：讀者優先

• 讀者可以并行：只要 iReadCount > 0，新讀者無需再搶 rwSync，直接讀即可。

• 寫者可能餓死：如果讀者源源不斷，寫者將長期拿不到 rwSync。

方案2的正確實現需要：

（1）iReadCount：一個跟蹤讀者數量的整數

• 如果iReadCount > 0: writer被阻塞（sem_wait(rwSync)）
• 如果iReadCount == 0：寫入器被釋放（sem_post(rwSync)）
• 如果已經寫了，讀者必須等待

（2）sync: 對 iReadCount 本身的互斥鎖（初值 1），防止多個讀者并發修改計數。

（3）rwSync：寫者互斥鎖（初值 1）。同步讀者和寫者的信號量，由第一個/最后一個讀者設置。只要 iReadCount > 0 或 正在寫，寫者就得在 rwSync 上阻塞。

① 讀者進入

sem_wait(&sync);      // 鎖住計數器
iReadCount++;         // 又來一個讀者
if (iReadCount == 1)  // 是第一個讀者？sem_wait(&rwSync);// 把寫者擋在外面
sem_post(&sync);      // 釋放計數器printf("reading record");

② 讀者離開

sem_wait(&sync);      // 再次鎖住計數器
iReadCount--;
if (iReadCount == 0)  // 最后一個讀者？sem_post(&rwSync);// 放行一個等待的寫者
sem_post(&sync);

③ 寫者

sem_wait(&rwSync);    // 等所有讀者和別的寫者退出
printf("writing");
sem_post(&rwSync);    // 寫完放行

方案3：寫者優先

它用了 4 個信號量 / 計數器 來確保：

• 一旦有寫者到達，后續讀者必須排隊，正在讀的讀者全部結束后立即讓寫者執行；

• 寫者之間互斥；

• 寫者完成后，讀者再繼續。

優先考慮寫作者和使用者：（以下初值均為1）

• 整數iReadCount和iWriteCount來跟蹤讀/寫的數量。
• 互斥鎖sRead和sWrite來同步讀/寫的臨界區。
• 信號量sReadTry在有寫入器等待時停止讀取器。讀者“入場券”。寫者到來后把它降為 0，阻塞新讀者。
• 信號量sResource用于同步讀/寫資源。真正保護數據區的鎖。讀者或寫者要訪問數據必須先拿到它。

① 讀者

while (1) {sem_wait(&sReadTry);   // ① 先排隊拿“讀者入場券”sem_wait(&sRead);      // ② 鎖計數器iReadCount++;if (iReadCount == 1)   // ③ 第一個讀者搶數據鎖sem_wait(&sResource);sem_post(&sRead);      // ④ 解鎖計數器sem_post(&sReadTry);   // ⑤ 放行下一位讀者printf("reading\n");   // ⑥ 真正讀數據sem_wait(&sRead);      // ⑦ 讀完，更新計數器iReadCount--;if (iReadCount == 0)   // ⑧ 最后一個讀者釋放數據鎖sem_post(&sResource);sem_post(&sRead);
}

② 寫者

while (1) {sem_wait(&sWrite);     // ① 鎖寫者計數器iwriteCount++;if (iwriteCount == 1)  // ② 第一位寫者關閉“讀者入場券”sem_wait(&sReadTry);sem_post(&sWrite);sem_wait(&sResource);  // ③ 真正拿到數據鎖printf("writing\n");   // ④ 寫數據sem_post(&sResource);sem_wait(&sWrite);     // ⑤ 寫完，更新計數器iwriteCount--;if (iwriteCount == 0)  // ⑥ 最后一位寫者重新開放“讀者入場券”sem_post(&sReadTry);sem_post(&sWrite);
}

寫者一旦到達，先把 sReadTry 關閘，新讀者必須排隊；等所有正在讀的讀者走光后，寫者立即拿到 sResource；寫者全部完成后重新開閘，讀者才能繼續。從而實現了 寫者優先，讀者可能饑餓。

---

---

---

---

---

---

---

---

---

---

---

---

---

---

約束:

• 每個人都樂于走進關燈的房間。
• 讀者和作家不喜歡對方。
• 讀者很樂意進入一個亮著綠燈而不是黃燈的房間。
• 作家們很樂意進入一個黃燈而不是綠燈亮著的房間。
• 只有讀者可以使用底部出口