Ch6 Hardware Support for Synchronization

6.4 Hardware Support for Synchronization

6.4.1 Memory Barriers

現在的電腦為了提升效能，有可能會做reorder instructions。重新排序在單執行緒的系統下是可以的，但在多執行緒的系統中，會造成資料不一致的問題。因此，電腦架構必須定義一組規則，來說明：

記憶體讀寫在多執行緒環境中，什麼情況下是「保證可見的」、以及哪些重新排序是允許的。

這叫做 Memory Model。

Memory model 有兩種

1. Strongly ordered;：在 A processor 更新的記憶體 會 上被其他的 processor 看到
2. Weakly ordered：在 A processor 更新的記憶體 不會 上被其他的 processor 看到

現在的 Memory 有很多種類，所以不知道會是哪一種。為了解決問題，電腦提供一些instruction可以強迫把更改的資訊傳送給所有processor，這些指令也被稱為memory barrier或是memory fence。這些指令是atomic的指令，意思就是不可分割的。具體是這樣實作：

do {
  acquire lock;
    critical section;
  release lock;
    remainder section;
}while(true);

6.4.2 Hardware instructions

為了使用方便，現在的電腦提供一些指令可以使用。

test_and_set

bool test and set(boolean *target) {
  boolean rv = *target;
  *target = true;
  return rv;
}

do {
  while (test and set(&lock));
    /* do nothing */
    
  /* critical section */
  
  lock = false;
  
  /* remainder section */
} while (true);

• 它是atomic。所以如果兩個同時(parallelism)，他們會被以一個任意的順序執行。
• 可以藉由控制lock達到mutual exclusion的目的。
• 初始值lock = false。

compare_and_swap (CAS)

int compare and swap(int *value, int expected, int new value) {
  int temp = *value;
  if (*value == expected)
    *value = new value;
  }

  return temp;
}

CAS 是一個atomic的指令，所以如果兩個同時(parallelism)，他們會被以一個任意的順序執行。操作需要三個參數：

1. *value: 要修改的變數
2. expected: 原本變數的值
3. new_value: 要設成的新值

只有當*value == expected的時候，才會把值更改。

CAS用於mutual exclusion，設定lock的初始值為0。

while (true) {
  while (compare and swap(&lock, 0, 1) != 0); 
    /* do nothing */
    
  /* critical section */
  lock = 0;
  /* remainder section */

進入critical section前把lock改成1。 這樣其他的process就無法進入 critical section。但是這樣會有無法滿足bounded-waiting的問題，舉個例子：

1. P0 在臨界區結束，把 lock = 0

2. P1, P2 都在 busy-wait
3. CPU 偏好給 P2 執行 CAS，P2 成功，P1 繼續失敗
4. 下次又可能 P3 搶先，P1 永遠被跳過，無限等待(starvation)

這就是 bounded waiting 不成立，所以我們要建立一個機制讓他排隊。

while (true) {
  waiting[i] = true;
  key = 1;
  while (waiting[i] && key == 1)
    key = compare and swap(&lock,0,1);
  waiting[i] = false;
  
  /* critical section */
  ---

## 重點整理
- **Priority inversion**：高優先權行程被低優先權間接阻擋
- 問題原因：lock / semaphore + 多優先權排程
- 常見解法：**Priority inheritance protocol**
- 目的：確保高優先權行程不會被不必要地延遲

  j = (i + 1) % n;
  while ((j != i) && !waiting[j])
    j = (j + 1) % n;
  if (j == i)
    lock = 0;
  else
    waiting[j] = false;
    /* remainder section */
}

用一個bool waiting[n]表示正在等待的process，預設全部都是false(沒有等待)，用lock表示現在能不能進去，預設是0（沒有鎖，可以進去）。如果有一個process $P_i$ 想要進入critical section,那就必須滿足waiting[i] == true && lock == 1，表示現在等待中且可以進去。如果已經有其他process在裡面，lock == 1。可以保證其他的process進不來，滿足mutual exclusion。之後在循序搜尋有沒有process在等待,滿足bounded waiting。

但通常不會用CAS實做spinlock，因為容易starvation。

6.4.3 Atomic Variables

在做運算的時候，寫一行不代表只有一行。比如說：c++;，在`RISC-V中

ld x20, x21
addi x20, 1
sw x20, x21

變成三行指令，其中如果發生interrupt就會造成資料儲存不完全。因此提供一種變數讓他的改變過程是atomic的，滿足mutual exclusion，通常使用CAS來實作。

void increment(atomic int *v)
{
  int temp;
  do {
  temp = *v;
  }
  while (temp != compare_and_swap(v, temp, temp+1));
}

但這個方法不能解決所有問題，至於為什麼就看原文吧。

It is important to note that although atomic variables provide atomic updates, they do not entirely solve race conditions in all circumstances. For example, in the bounded-buffer problem described in Section 6.1, we could use an atomic integer for count. This would ensure that the updates to count were atomic. However, the producer and consumer processes also have while loops whose condition depends on the value of count. Consider a situation in which the buffer is currently empty and two consumers are looping while waiting for count > 0. If a producer entered one item in the buffer, both consumers could exit their while loops (as count would no longer be equal to 0) and proceed to consume, even though the value of count was only set to 1.

6.5 Mutex Locks

The hardware-based solutions to the critical-section problem presented in Section 6.4 are complicated as well as generally inaccessible to application programmers.

剛剛提過解決crtical-section的方法有點複雜，對於應用工程師來說通常無法使用。所以系統提供一個高階一點的工具mutex lock給他們用。

while (true) {
  acquire_lock();
  
    /*critical section*/
    
  release_lock();
  
    /*remainder section*/
}

acquire() {
  while (!available); 
    /* busy wait */
  available = false;
}

release() {
  available = true;
}

acquire與release的過程都必須是atomic，一樣可以用CAS實做出來。 但有缺點，process在等待的時候會卡在迴圈裡面，也就是busy waiting。對於一個multiprogramming的系統來說很浪費資源（雖然只是在等，但是還是會佔用CPU的時間。）

6.6 Semaphores

這邊提供另外一種作法。S 當成一個變數，只會被兩個atomic的函數改變：wait 跟 signal。

wait(S) {
  while (S <= 0);
    // busy wait
  S--;
}

signal(S) {
  S++;
}

6.6.1 Semaphores Usage

通常分成兩種Semaphore。

• Counting Semaphore : range沒有限制。
• Binary Semaphore ：range 只能01。 Semaphores用法：

//P1
S1 ;
signal(synch);

//P2
wait(synch);
S2 ;

這樣就一定要等P1做完發出signal，P2才能開始動作。也就是說不能調換執行順序。

6.6.2 Semaphore Implementation

typedef struct {
  int value;
  struct process *list;
} semaphore;

wait(semaphore *S) {
  S->value--;
  if (S->value < 0) {
    add this process to S->list;
    sleep();
  }
}

signal(semaphore *S) {
  S->value++;
  if (S->value <= 0) {
    remove a process P from S->list;
    wakeup(P);
  }
}

每個Semaphore都有一個整數值和一個等待清單。當一個process必須等待Semaphore時，它會被加入到等待清單中。signal() 操作會從等待清單中移除一個process，啟動那個process。在這邊Semaphore可以是負數，他的大小等於目前有多少process在等待。而等待清單可以透過PCB來實現，且為了確保bounded waiting，通常使用FIFO。

Semaphore必須是atomic的，我們必須保證沒有兩個process可以同時call wait()和 signal()。在單核心的情況下可以把wait()和signal()設定成atomic，但這種方法只能用在單核心。在多核的系統中，要斷用全部的interrupt，不同的process的instruction可能會混亂。

Monitors

就算有了好工具，還是有人會寫錯。所以又出現了更方便的東西。

就是一個Abstract data type (ADT)，把所有要用的功能包在一起，保證只有一個process在monitor裡面執行。如果覺得我講的太抽象請看原文

An abstract data type—or ADT —encapsulates data with a set of functions to operate on that data that are independent of any specific implementation of the ADT. A monitor type is an ADT that includes a set of programmer-defined operations that are provided with mutual exclusion within the monitor. The monitor type also declares the variables whose values define the state of an instance of that type, along with the bodies of functions that operate on those variables. The syntax of a monitor type is shown in Figure 6.11. The representation of a monitor type cannot be used directly by the various processes. Thus, a function defined within a monitor can access only those variables declared locally within the monitor and its formal parameters. Similarly, the local variables of a monitor can be accessed by only the local functions.

6.7.1 Monitor Usage

monitor monitor name
{
    /* shared variable declarations */
    function P1 ( . . . ) {
    . . .
    }
    function P2 ( . . . ) {
    . . .
    }
    .
    .
    .
    function Pn ( . . . ) {
    . . .
    }
    initialization code ( . . . ) {
    . . .
}
}

反正就是包的有模有樣。 裡面會有一些Condition Variable，就是monitor提供的等待機制。

condition x ,y;

有兩個基本操作

1. x.wait()：這個process會被暫停直到有人呼叫他。
2. x.signal()：呼叫process的，但如果沒有人在wait()就不會有作用。

那當一個process P 呼叫 x.signal() 喚醒一個等待中的process Q 時，如何保持 monitor 的mutual exclusion呢？

1. signal and wait：P 等待，直到 Q 離開
2. signal and continue：P 執行，直到 Q 離開

6.7.2 Implementing a Monitor Using Semaphores

這邊會用signal and wait來實作。

wait(mutex);
    ...
    body of F
    ...
    if (next count > 0)
        signal(next);
    else
        signal(mutex);

這樣就可以時做出一個mutual exclusion的monitor。

x.wait(){
    x count++;
    if (next count > 0)
        signal(next);
    else
        signal(mutex);
    wait(x sem);
    x count--;
}

x.signal(){
    if (x count > 0) {
        next count++;
        signal(x sem);
        wait(next);
        next count--;
    }
    
monitor ResourceAllocator
{
    boolean busy;
    condition x;
    void acquire(int time) {
        if (busy)
            x.wait(time);
        busy = true;
    }
        
    void release() {
        busy = false;
        x.signal();
    }
    
    initialization code() {
        busy = false;
    }
}

6.7.3 Resuming Processes within a Monitor

有很多 process 在 condition x ,x和x.signal上面等在執行，誰先？

1. FCFS 通常不行
2. 設定一個 x.wait(c)，c 是一個priority number，數字最小的先執行。

每個process在請求資源的時候，都要給定可能會使用多久。monitor會先分配給時間最少的process。但不能保證會遵守前面的順序，因為可能有以下情況：

• 一個process可能在沒有權限的情況下訪問資源。
• 一個process可能在拿到資源後，永遠不釋放資源。
• 一個process可能嘗試釋放一個從未請求過的資源。
• 一個process可能在未先釋放資源的情況下重新請求同一資源。

為了修正這個問題,要確定兩件事：

1. user process必須始終以正確的順序呼叫monitor。
2. 保證所有的process都是經由monitor使用資源。

6.8 Liveness

6.8.1 Deadlock

使用semaphore實作waiting queue的時候，兩個或多個process可能無限期等待某個事件發生，而這個事件只能由這些正在等待的行程之一來觸發。然後就Deadlock了。舉例：

P0:
wait(S);
wait(Q);
.
.
.
signal(S);
signal(Q);

P1:
wait(Q);
wait(S);
.
.
.
signal(Q);
signal(S);

6.8.2 Priority Inversion

在作業系統中，kernel data通常會被 lock / semaphore 保護。當高優先權行程需要存取某個資源，而該資源正被低優先權行程使用時，高優先權行程必須等待低優先權行程釋放資源。若此時低優先權行程又被「中等優先權行程」搶佔，問題就會變得更嚴重。假設有三個行程：

• L：低優先權
• M：中優先權
• H：高優先權

優先權順序為：L < M < H

情境如下：

1. 行程 L 正在使用資源 S（semaphore）
2. 行程 H 需要資源 S，但必須等待 L 釋放
3. 此時行程 M 變成 runnable，並搶佔了 L
4. 結果：
   • H 必須等待更久
   • 但延遲卻是由 優先權比 H 低的 M 所造成

低優先權的行程影響了高優先權行程的執行時間，這就是Priority Inversion。定義：

高優先權行程因為資源被低優先權行程持有，並且該低優先權行程又被中優先權行程搶佔，導致高優先權行程無法執行的現象。

• 只會發生在 兩種以上優先權等級的系統
• 屬於一種 liveness（活性）問題
• 可能導致即時系統嚴重失效

為了解決這個問題，我們需要Priority Inheritance Protocol

當低優先權行程持有高優先權行程需要的資源時，低優先權行程暫時繼承高優先權，避免被中優先權行程搶佔

例如：

1. 行程 L 使用資源 S
2. 行程 H 需要資源 S
3. L 暫時繼承 H 的高優先權
4. 行程 M 無法搶佔 L
5. L 快速完成並釋放 S
6. L 優先權恢復原本等級
7. H 取得資源並執行（而不是 M）