記錄學習內容。
以下內容大多引用大大們的文章，加上一些自己的筆記。
自己的筆記部分，內容可能有錯誤。

【小黑馬作業系統教室】(15) (Ch6)什麼是「同步化」議題的超完整解說

【小黑馬作業系統教室】(16) (Ch6)Critical section problem的各種解法

OS - Ch6 同步問題 Synchronization

臨界區段（Critical section）

https://zh.wikipedia.org/wiki/%E8%87%A8%E7%95%8C%E5%8D%80%E6%AE%B5

臨界區段（Critical section）指的是一個存取共用資源（例如：共用裝置或是共用記憶體）的程式片段，而這些共用資源有無法同時被多個執行緒存取的特性。

只能被單一執行緒存取的裝置，例如：印表機。
一次只能有一個人列印程式? 不然 每個人檔案會混再一起

process (程序) 、或執行緒 可能有部分程式 ， 只能允許一人進入 。這段程式 稱為 臨界區段（Critical section） 簡稱 cs 。

不是臨界區段（Critical section） 的程式 ，稱為 剩餘區(remainder section) 簡稱rs

所以這個要記:

Critical section -- > cs 
remainder section -- >rs

都以執行緒來想 ，畢竟寫程式都寫thread，這樣比較容易

有critical section 的 執行緒 ，希望他能滿足這三個東西:

mutual exclusion: 若執行緒在執行「critical section」，
其它執行緒都不該進入它們的「critical section」。
(並不是其它執行緒不能進入CPU哦，只是其他執行緒 在 cs外面 無窮迴圈)

progress: 不想進入 critical section 的執行緒 不可以阻礙其它 執行緒 進入 critical section，
即不可參與進入 critical section 的決策過程。

bounded waiting: 若一個執行緒想執行CS，等待的執行緒數量必須是有限的，不能無限被插隊 。
即若有 n 個 執行緒，則任一 執行緒 至多等待 n-1 次(n-1個執行緒)即可進入，隱含 No starvation (沒有人餓肚子，每個執行緒都要吃東西)。

文章先講了一個例子

Only Turn

i執行緒

repeat
 while(turn!=i)do no-op
  C.S.
 turn = j;
  R.S.
until False

j執行緒

repeat
 while(turn!=j)do no-op
  C.S.
 turn = i;
  R.S.
until False

或是這樣寫:
i執行緒

do{
    while(turn!=i);
        critical section
    turn = j;
        remainder section
}while(1)

j執行緒

do{
    while(turn!=j);
        critical section
    turn = i;
        remainder section
}while(1)

while(1)相當於 while(true) 相當於 until False {直到false停止迴圈}

這個程式違反:

違反 Progress (違反條件1)：假設目前 turn 值為 i ，但 Pi 不想進入 critical section。若此時 Pj 想進critical section ，Pj 卻無法進入，因為被 Pi 阻礙，因為只有 Pi 才有資格將 turn 值改為 j。

不想進入 critical section 的意思是 在cs外面遊蕩
就是說 j執行緒 想進入cs了 ，但是j執行緒 還要請 i 執行緒先 進入cs，把turn改成j

java的 synchronized

Android ，存圖片到SQLite，process、thread、ByteArrayOutputStream
https://ithelp.ithome.com.tw/articles/10228684

之前紀錄的:

class Main {
 static private int num = 0;
 static Object obj1 = new Object();
 //Object obj2 = new Object();
 static class ThreadTestAdd implements Runnable {
  public void run() {
   synchronized(obj1) {
    for (int i = 0; i < 3; i++) {
     System.out.println(Thread.currentThread().getName() + "num:" + ++num);
    }
   }
  }
 }
 static class ThreadTestSub implements Runnable {
  public void run() {
   synchronized(obj1) {
    for (int i = 0; i < 3; i++) {
     System.out.println(Thread.currentThread().getName() + "num:" + --num);
    }
   }
  }
 }


 public static void main(String[] args) {
  ThreadTestAdd t1 = new ThreadTestAdd();
  ThreadTestSub t2 = new ThreadTestSub();
  Thread ta = new Thread(t1, "A");
  Thread tb = new Thread(t2, "B");
  ta.start();
  tb.start();
 }
}

static Object obj1 = new Object(); 就想成共用變數，turn值 。

假如先執行到ThreadTestAdd，執行緒，這個執行緒執行到   synchronized(obj1) {
}

，另一個執行緒ThreadTestSub 就得 等ThreadTestAdd 執行完synchronized(obj1) {
}後 ，才能執行synchronized(obj1) {
}

所以synchronized(obj1) {
} 就想成critical section  。

另一個執行緒，在等待的時候 ，就想成他在跑無窮迴圈

然後講到:

Only Flag

Flag 和 turn 是什麼 ?

記法 :

turn 感覺是 作業系統 ，強迫換到誰 。
flag 感覺是 寫程式的人 ，決定換到誰 。

turn -- >輪到我(執行緒)進cs
flag -- >我(執行緒)想進cs

前面是turn ，這邊講到的是flag 。
如果只有flag ，會違法Progress:

i執行緒

repeat
 flag[i] = True
 while( flag[j] ) do no-op;
  C.S.
 flag[i] = False
  R.S.
until False

j執行緒:

repeat
 flag[j] = True
 while( flag[i] ) do no-op;
  C.S.
 flag[j] = False
  R.S.
until False

如果兩個執行緒 ，把變數變成這樣:

 flag[i] = True、 flag[j] = True 

會造成

 while( flag[i] ) do no-op;
 while( flag[j] ) do no-op;
 
 兩個執行緒都在跑無窮迴圈，進不了cs

接著講到

(軟體解)Peterson's solution

turn 和 flag 一起用。

i執行緒

do{
 flag[i] = TRUE; //我想到cs
 turn = j; // 禮讓的概念 ，turn給你

 while ( flag[j] && turn == j); // j想進去且輪到j進去 ，跑無窮迴圈
 // 換句話說: 如果j不想進去，或沒有輪到j ，就換i我進去

 CRITICAL SECTION

 flag[i] = FALSE;  //完成cs後 ，表示我不想進去了

 REMAINDER SECTION

} while (TRUE);

j執行緒

do{
 flag[j] = TRUE; //我想到cs
 turn = i;   //禮讓的概念，turn給你

 while ( flag[i] && turn == i); // i想進去且輪到i進去 ，跑無窮迴圈
 // 換句話說: 如果i不想進去，或沒有輪到i ，就換j進去
 
 CRITICAL SECTION

 flag[j] = FALSE; //完成cs後 ，表示我不想進去了

 REMAINDER SECTION

} while (TRUE);

證明 mutual exclusion:

i會依序執行這3個
 flag[i] = TRUE; //我想到cs
 turn = j; // 禮讓的概念 是turn給你
 while ( flag[j] && turn == j); // j想進去且輪到j進去 ，跑無窮迴圈
 
j會依序執行這3個
 flag[j] = TRUE; //我想到cs
 turn = i;   //禮讓的概念，turn給你
 while ( flag[i] && turn == i); // i想進去且輪到i進去 ，跑無窮迴圈
 // 換句話說: 如果i不想進去，或沒有輪到i ，就換j進去

因為turn 一定 是 i 或 j ，所有一定有一個人可以離開無窮迴圈，進到cs

證明 progress:

在只有trun 的時候 ，如何輪到j執行緒 進cs ? i 執行緒 完成 cs 後 ，把turn 改成 j 。 

所以 要改良的就是 : i 執行緒 就算沒進到cs(不想進cs) ，也要讓j 可以進到cs 。

 while ( flag[i] && turn == i); // i想進去且輪到i進去 ，跑無窮迴圈
 // 換句話說: 如果i不想進去，或沒有輪到i ，就換j進去 。
 //  i不想進去 ，就可以換j進去 了 ，就算輪到i
 

證明 bounded waiting:

因為
j會依序執行這3個
 flag[j] = TRUE; //我想到cs
 turn = i;   //禮讓的概念，turn給你
 while ( flag[i] && turn == i); // i想進去且輪到i進去 ，跑無窮迴圈
 // 換句話說: 如果i不想進去，或沒有輪到i ，就換j進去
 
 就算j一直跑比較快 ，但都會禮讓i ，所以不會讓i一直在無窮迴圈 。
 

目前整理:

mutual exclusion:只有一個人可以進到cs
progress: 不想進cs的 ，不能決定誰進cs  、或是不能deadlock
bounded waiting : 不能讓某個執行緒 ，一直在cs外