# Synchronization Examples

- Apply the tools to several classic synchronization problems

## Classic Problems of Synchronization

### Bounded-Buffer Problem

The structure of the **producer** process:

// 假設有 n 個 buffers, 每個都有資料
// 三個 semaphore 預設值為 mutex = 1, full = 0, empty = n

while (true) {
    ...
  /* produce an item in next produced */
    ...
  wait(empty);
  wait(mutex);
    ...
  /* add next produced to the buffer */
    ...
  signal(mutex);
  signal(full);
}

The structure of the **consumer** process:

while (true) {
  wait(full);
  wait(mutex);
    ...
  /* remove an item from buffer to next consumed */
    ...
  signal(mutex);
  signal(empty);
    ...
  /* consume the item in next consumed */
  ...
}

### Readers–Writers Problem

- Reader 只讀資料所以可以同時 access 同一份 data
- Writer 會修改資料，所以一次只會有 writer 一個人在存取 data

The reader processes share the following data structures:

semaphore rw_mutex = 1; // mutual exclusion semaphore for the writers
semaphore mutex = 1; // ensure mutual exclusion when the variable read_count is updated
int read_count = 0;  // how many processes are currently reading the object

The structure of a **writer** process:

while (true) {
  wait(rw_mutex);
    ...
  /* writing is performed */
    ...
  signal(rw_mutex);
}

The structure of a **reader** process:

while (true) {
  wait(mutex); // 表示我想要修改 read_count
  read_count++;
  if (read_count == 1) // 表示現在是 reader 要讀資料了
    wait(rw_mutex); // 讓 writer 無法修改資料
  signal(mutex); // 結束修改 read_count
    ...
  /* reading is performed */
    ...
  wait(mutex); // 表示我想要修改 read_count
  read_count--;
  if (read_count == 0) // 表示 reader 結束了
    signal(rw_mutex); // writer 可以修改資料了
  signal(mutex); // 結束修改 read_count
}

### Dining-Philosophers Problem


#### Semaphore Solution

Data structure:

semaphore chopstick[5];

The structure of philosopher $i$:

while (true) {
  wait(chopstick[i]);
  wait(chopstick[(i + 1) % 5]);
    ...
  /* eat for a while */
    ...
  signal(chopstick[i]);
  signal(chopstick[(i + 1) % 5]);
    ...
  /* think for awhile */
    ...
}

#### Monitor Solution

Data structure:

enum {THINKING, HUNGRY, EATING} state[5];
condition self[5];

monitor DiningPhilosophers
{
  enum {THINKING, HUNGRY, EATING} state[5];
  condition self[5];

  void pickup(int i) {
    state[i] = HUNGRY;
    test(i);
    if (state[i] != EATING)
      self[i].wait();
  }

  void putdown(int i) {
    state[i] = THINKING;
    test((i + 4) % 5);
    test((i + 1) % 5);
  }

  void test(int i) {
    if ((state[(i + 4) % 5] != EATING) &&
      (state[i] == HUNGRY) &&
      (state[(i + 1) % 5] != EATING)) {
        state[i] = EATING;
        self[i].signal();
    }
  }

  initialization_code() {
    for (int i = 0; i < 5; i++)
    state[i] = THINKING;
  }
}

DiningPhilosophers.pickup(i);
...
eat
...
DiningPhilosophers.putdown(i);

## Alternative Approaches

### Transactional Memory

- A function `update()` that modifies shared data
- This function would be written using mutex locks (or semaphore)
- ```c
void update() {
aquire();

/* modify shared data */

release();
}

- A memory transaction is a sequence of read-write operations that are atomic 
    - If all operations in a transaction are completed, the memory transaction is committed
    - Otherwise, the operations must be aborted and rolled back
- ```c
  void update() {
      atomic {
          /* modify share data */ 
      }
  }