# 第一題：第六章第七章同步工具的整理與比較

## Lock

Lock是一種同步機制，旨在確保在多線程(multi thread)的環境中，同一時間只能有一個thread訪問該資源

鎖的使用可以避免data race(不同的thread同時讀寫共享變數)，從而保證程式的正確性。


## Mutex Lock

用於確保同一時間只有一個process可以進入臨界區（critical section）。

acquire(){
    while (!available) 
          ; /* busy wait */ 
       available = false;
    } 
release(){ 
       available = true; 
    }
    
 do{ 
    acquire()
       critical section
    release() 
       remainder section 
 }while(true); 

**缺點**
* 會有**busy waiting**的情況發生(process一直檢查condition是否為true)

## Semaphore

實作了 **wait()** 和 **signal()**，並把process分成**waiting, ready state(queue)**

* ready state(queue)
* 接著要被執行的process
* waiting state(queue)
* 等待中的process
* wait()
* 確保只有一個process可以修改該資料
* **block**
* 將process放至waiting queue
* signal()
* **wakeup**
* 將一個process從waiting queue放至ready queue

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


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

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

**缺點**
* 可能會有deadlock發生

### semaphore種類

* Counting semaphore
* 用於多個process
* Binary semaphore
* 只有0, 1，適用於2個porcess(概念類似Mutex lock)

## Monitor

### Abstract Data Type (ADT)
* Encapsulates **data** with a set of **functions** to operate on that data that are independent of any specific implementation of the ADT

### Monitor

* Monitor會將要共享資源和訪問這些資源的方法封裝在一個對象(ADT)中。
* 每次只有一個process可以訪問Monitor內部的資源
* 條件變量（Condition Variable）
* Monitor常配合條件變量使用，允許process在等待某個條件時進入waiting queue。


## Hardware Support for Synchronization

### Memory barriers

Memory barriers用於**強制** CPU 和編譯器**按照特定順序執行記憶體操作**，從而避免因記憶體重排序（Memory Reordering）導致的問題。

**記憶體重排序**
* 現代 CPU 和編譯器為了優化性能，可能會重新排序讀/寫操作。
在多執行緒環境中，**重排序可能導致資料一致性問題**。

**Memory model**
* Strongly ordered
* 硬體或編譯器**不會改變**讀寫**指令的順序**
* Weakly ordered
* 處理器和編譯器**可以自由地重新排序記憶體操作**，只要這些操作不違反程式執行結果

### Atomic variables

Atomic variables是一種變數類型，保證在多執行緒環境中對該變數的操作是不可分割的（atomic），不會再分給其他的thread，可以避免data race

### hardware instructions(Atomic operation)

類似Atomic variables的概念，Atomic operation不會被其他thread打斷，用於保證多線程環境中的同步。

**test_and_set**
* 用途
* 表示lock是否已經被佔用
* 回傳值
* 返回變數的原始值，並將其設置為新值

boolean test_and_set (boolean *target)
          {
               boolean rv = *target;
               *target = TRUE;
               return rv:
          }

do {
    while (test_and_set(&lock)) ; /* do nothing */ 
            //只有當lock是false時才能進入critical section
             
                 /* critical section */ 
          lock = false; 
                 /* remainder section */ 
       } while (true); 

**compare_and_swap**
* 用途
* 用於實現無鎖(lock-free)操作，**實現比較並交換**的操作
* compare_and_swap()不會被其他線程打斷，因此在不使用lock的情況下保證操作的正確性。
* 回傳值
* 返回變數的原始值，並指示操作是否成功
* lock初始值為0

int compare_and_swap(int *value, int expected, int new_value) { 
         int temp = *value; 

         if (*value == expected) 
            *value = new_value; 
          return temp; 
     } 

do {
    while (compare_and_swap(&lock, 0, 1) != 0) ; /* do nothing */ 
            //只有當lock是0時才能進入critical section
            
          /* critical section */ 
       lock = 0; 
          /* remainder section */ 
      } while (true); 

> 來源:https://hackmd.io/@2020OS/ryMVc6u9L

### Transactional Memory

Transactional Memory旨在簡化多線程程序中的同步問題，尤其是當多個線程需要操作共享資源時，他會把一段的operations都變成atomic operations，要麼全部執行成功，要麼全部回滾(rolled back)

* Transactional Memory會透過update()修改shared data
* 如果有operations執行失敗，則會需要在全部重做一次(rolled back)

void update ( )
{
	atomic 
	{
	// modify shared data
	}
}

# 第二題：bounded buffer 不同版本的解法

我們也可以透過Monitor來解決bounded buffer的問題

Mointor可以控制當進入或結束一個process的時候:
* 進入一個process時:
* 發現buffer剩下一個則signal(empty)，wakeup consumer use source
* 發現buffer滿了則wait(full)，block producer release source
* 結束一個process時:
* 發現buffer為空則wait(empty)，block consumer use source
* 發現buffer差一個就滿了則signal(full)，wakeup producer release source

**程式碼範例:**

  monitor ProducerConsumer
    condition full, empty;
    int count;
  
  procedure enter();
  {
    if (count == N) wait(full);        // if buffer is full, block
    put_item(widget);                  // put item in buffer
    count = count + 1;                 // increment count of full slots
    if (count == 1)  signal(empty);    // if buffer was empty, wake consumer
  }

  procedure remove();
  {
    if (count == 0)  wait(empty);      // if buffer is empty, block
    remove_item(widget);               // remove item from buffer
    count = count - 1;                 // decrement count of full slots
    if (count == N-1)  signal(full);   // if buffer was full, wake producer
  }

  count = 0;
  end monitor;

  Producer();
  {
    while (TRUE)
   {
      make_item(widget);               // make a new item
      ProducerConsumer.enter;          // call enter function in monitor
   }
  }

  Consumer();
  {
    while (TRUE)
    {
      ProducerConsumer.remove;         // call remove function in monitor
      consume_item;                    // consume an item
   }
  }

> 來源:https://denninginstitute.com/modules/ipc/purple/prodmon.html