操作系統筆記（七）進程同步

• 相互隔絕：兩個進程不會同時進入critical section
• progress: critical section之外的進程不會阻止其他進程進入他們的critical section
• bounded waiting: 每個進程等待有限時間即可進入critical section
• speed: 解決方案不包括對cpu數量和速度的設定

 1 int turn = 0;
 2 bool flag[2] = {false, false};
 3 
 4 do {
 5     
 6     flag[i] = true;
 7     turn = j;
 8     while(flag[j] && turn == j);// j未執行完臨界區 且 j不准備進入臨界區 ==》 j在臨界區
 9 
10     CRITICAL SECTION
11     
12     flag[i] = false;
13 } while(1);

多個進程的bakry 演算法：

 1 bool choosing[n] = {false, ..., false};
 2 int number[n] = {0,...0};
 3 do{
 4     choosing[i] = true;
 5     number[i] = max(number[0],..,number[n-1]) + 1; // large number
 6     choosing[i] = false; // number settled
 7     for(int j = 0; j < n; j++){
 8         while(choosing[j]); // j have not settled number 
 9         while( (number[j] != 0) && ( (number[j] < number[i]) || (number[j] == number[i] && j < i) ));
10         // j 未離開臨界區，number[j] 小於 number[i] 或者number[j] = number[i] 但j < i。
11     }
12     
13     CRITICAL SECTION
14     
15     number[i] = 0;
16 }while(1);

硬體同步：

• 關閉中斷：進程關閉中斷，僅受時鐘周期影響。缺點：用戶進程不應該關中斷；無法適應多核情況。

• 特殊指令：TSL（Test and Set Lock設置為true，返回舊值），SWAP。原子操作。缺點：忙等待，自旋鎖，進入臨界區之前一直處於檢查階段；僅適合於多核（context switch 少）。

 1 typedef struct{
 2     int value; 
 3     struct PCB* L; // blocked processes       
 4 } semaphore;
 5 
 6 void P(semaphor* S)
 7 {
 8     S -> value --;
 9     if( S -> value < 0)
10     {
11           add currProc to S -> L;
12           currProc -> state = WAITING;
13           scheduler();   
14      }       
15 }
16 
17 void V(semaphor* S)
18 {
19      S -> value ++;
20      if(S -> value <= 0)
21      {
22            get procA from S -> L;
23            procA -> state = READY; 
24      }
25 }

• 生產者和消費者問題：empty（BSIZE）， full（0）同步生產者和消費者；mutex控制臨界區（1）。

•  1 // producer
   2 do {
   3   ...produce an item
   4   P(&empty); // < 0 -> 沒資源，滿，等待
   5   P(&mutex); // < 0 -> 沒資源，在臨界區，等待
   6  ...
   7   add item to buffer
   8  ...
   9   V(&mutex);// <= 0 -> 有等待，叫醒
  10   V(&full);// <=0 -> 有等待，  叫醒
  11 }
  12 
  13 // consumer
  14 do {
  15   P(&full); // < 0 -> 沒資源，空，等待
  16   P(&mutex); // < 0 -> 沒資源，在臨界區，等待
  17  ...
  18   consume an item from buffer
  19  ...
  20   V(&mutex);// <= 0 -> 有等待，叫醒
  21   V(&empty);// <=0 -> 有等待，  叫醒
  22 }

  讀寫問題： wrt保護共用對象（1），整數readcount（0）記錄讀者數目，mutext（1）保護readcount。

二元信號量

• 上述信號量取值範圍很大，而二元信號量僅僅取值0,1。因此，可以採用硬體優化。