作业系统 Critical section

记录学习内容。
以下内容大多引用大大们的文章，加上一些自己的笔记。
自己的笔记部分，内容可能有错误。

【小黑马作业系统教室】(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外