---
# System prepended metadata

title: Semaphore (L20)
tags: [OS, 10501 資訊工程學系 作業系統]

---

## Semaphores L20_B 15:32

* A tool to generalize the synchronization problem.
    (**easier to solve, but no guarantee for correctness**)
* More specifically
    * A record of **how many units** of a particular resource are avilable
        * If # record = 1 -> **binary semaphore, mutex lock**
        * If # record > 1 -> **counting semaphore**
    * Accessed only through 2 **atomic** ops: **wait \(P\) & signal (V)**
* **Spinlock** implementation:
    * Semaphore is an **integer variable**
```c=
wait(S) {
    while(S <= 0);
    S--;
}

signal(S) {
    S++;
}
```

* record : 有多少資源是可以取用的。
* 當 record = 0，thread 就要進入 wait。
* Spinlock 缺點 : 浪費 cpu 資源 (while loop)

## POSIX Semphone

* Semaphone is part of **POSIX standard** BUT it is **not belonged to Pthread**
  * **It can be used with or without thread**
* POSIX Semaphone routines:
  * ***sem_init(sem_t \*sem, int pshared, unsigned int value)***
    * ***value*** -> Initial value of the semaphore
  * ***sem_wait(sen_t \*sem)***
  * ***sem_post(sem_t \*sem)***
  * ***sem_getvalue(sem_t \*sem, int \*valptr)***
    * ***\*valptr*** -> Current value of the semaphore
  * ***sem_destory(sem_t \*sem)***
  
```c=
// Example
#include <semaphore.h>
sem_t sem;
sem_init(&sem);
sem_wait(&sem);
    // critical section
sem_post(&sem);
sem_destory(&sem);
```
## n-Process Cirtical Section Problem
* shared data:
```c=
semaphore mutex; // initailly mutex = 1
```
* Process $P_i$
```c=
do {
    wait(mutex);            // pthread_mutex_lock(&mutex)
    critical_section();
    signal(mutex);
    remainder_section();    // pthread_mutex_unlock(&mutex)
} while(1);
```
:::success
* Progress ? **Yes**
* Bounded waiting ? **Depends on the implementation of *wait()***
:::

## [Non-busy waiting Implementation](https://youtu.be/r0h26ioGeG0?t=182)
* Semaphore is **data strust with a queue**
  * may use any queuing strategy (FIFO, FILO, etc)
```c=
typedef struct {
    int value;         // init to 0
    struct process *L; // "PCB" queue
} semaphore
```
* ***wait()*** and ***signal()***
  * use system calls: ***block()*** and ***wakeup()***
  * must be executed **atomically**
```c=
void wait(semaphore S) {
    S.value--;
    if(S.value < 0) {
        add_this_process_to_S_L(S.L);
        sleep();
    }
}

void signal(semaphore S) {
    S.value++;
    if(S.value <= 0) {
        remove_a_process_P_from_S_L(S.L);
        wakeup(P);
    }
}
```
* Spin lock v.s. non busy waiting
* 如果**等待時間**不長，會選擇用 spin lock。因為 non-busy waiting 需要 call syscall，會花比較多的時間。

### Atomic Operation (確保 semaphore)

* How to ensure atomic wait & signal ops ?
  * Single-processor: disable interrupts
  * Multi-processor:
    * HW support (e.g. [Test-And-Set](https://hackmd.io/QDScaLawTNOdUcHcphDTdg#Atomic-TestAndSet), Swap)
    * SW solution ([Peterson's solution](https://hackmd.io/QDScaLawTNOdUcHcphDTdg#Peterson%E2%80%99s-2-thread-scenario), [Bakery algorithm](https://hackmd.io/QDScaLawTNOdUcHcphDTdg#Bakery-Algotithm-n-processes))

## Semaphore with Critical Section

```c=
void wait(semaphore S) {
    entry_section();       // <--
    S.value--;
    if(S.value < 0) {
        add_this_process_to_S_L(S.L);
        exit_section();    // <--
        sleep()
    } else {
        exit_section();    // <--
    }
}

void signal(semaphore S) {
    entry_section();       // <--
    S.value++;
    if(S.value <= 0) {
        remove_a_process_P_from_S_L(S.L);
        exit_section();    // <--
        wakeup(P);
    } else {
        exit_section();    // <--
    }
}
```
![](https://i.imgur.com/PfNHeAO.png)
>starvation : 某程式一直無法執行

## Classical Synchronization Problems

### Bounded-Buffer
* A pool of n buffers, each capable of holding one item
* Producer:
    * grab an empty buffer
    * place an item into the buffer
    * waits if no empty buffer is available
* Consumer:
    * grab a buffer and retracts the item
    * place the buffer back to the free pool
    * waits of all buffers are empty

### [Readers-Writers Problem](https://medium.com/algorithm-solving/os-synchronization-2-semaphore-and-classical-problems-of-synchronization-fdbbcb027b79)

- 一個 writer 跟多個 reader 的問題
  - Writer 跟 reader 不能同時存取 CS
  - 多個 reader 可以同時存取 CS
- A set of shared data objects
- A group of processes
    - reader processes (read shared objects)
    - writer processes (updare shared objects)
    - **a writer process has exclusive access to a shared object**
- Different variations involving priority
    - **First RW problem**: no reader will be kept waiting unless a writer is updating a shared object
    - **Second RW problem**: once a writer is ready, it performs the updates as soon as the shared object is released
    -> writer has higher priority than reader
    -> once a writer is ready, no new reader may start reading

#### First Reader-Writer Algorithm
---

```c=
// mutual exclusion for write
semaphore wrt = 1;
// mutual exclusion for readcount
semaphore mutex = 1;
int readcount = 0;
```

```c=
Writer() {
    while(1) {
        wait(wrt);
        // Writer Code
        signal(wrt);
    }
}
```

```c=
Reader() {
    while(1) {
        wait(mutex);
          readcount++;
          if(readcount == 1) wait(wrt);    // Acquire write lock 
        signal(mutex);                     // if reads haven't
        // Reader Code
        wait(mutex);
         readcount--;
         if(readcount == 0) signal(wrt);   // release write lock
        signal(mutex);                     // if no more reads
    }
}
```

* Readers share a single wrt lock
* Writer may have **starvation problem**

#### Third Reader-Writer Problem
---

- **resource** : 讀寫的 buffer，全部 reader 都 read 完才可以換 writer
- **rmutex** : 保證 readcount 不會發生 race condition
- **serviceQueue** : 有點像 Queue 的概念，確保沒有 **starvation problem** (write 沒辦法執行的問題)

:::info
- 其中 reader 在 serviceQueue 跟 rmutex 的順序是鎖 A 鎖 B，解 A 解 B。這樣速度會比較快。
- Writer 在 serviceQueue 跟 resource 也是一樣。
:::

```c=
// controls access (read/write) to the resource
semaphore resource = 1;
// for syncing changes to shared variable readcount
semaphore rmutex = 1;
// FARNESS: preserves ordering of requests (signaling must be FIFO)
semaphore serviceQueue = 1;
int readcount = 0;
```

```c=
Writer() {
    P(serviceQueue);
    P(resource);
    V(serviceQueue);
    
    Write();
    
    V(resource);
}
```

```c=
Reader() {
    P(serviceQueue);    // wait in line to be serviced
    P(rmutex);
    readcount++;
    if(readcount == 1) {
        // for the first reader, request resource access for readers 
        // (writers blocked)
        P(resource);
    }
    V(serviceQueue);    // let next in line be serviced
    V(rmutex);
    
    Read();
    
    P(rmutex);
    readcount--;
    if(readcount == 0) {
        V(resource);
    }
    V(rmutex);
}
```

### Dining-Philosophers Problem
* 5 persons sitting on 5 chiars with 5 chopsticks
* A person is either thinking or eating
    * thinking: no interaction with the rest 4 persons
    * eating: need 2 chopsticks at hand
    * a person picks up 1 chopstick at a time
![](https://i.imgur.com/hIryVPm.png)
![](https://i.imgur.com/WQDv6az.png)
* moniter
![](https://i.imgur.com/ojVtInr.png)
![](https://i.imgur.com/udP5Yh3.jpg)
![](https://i.imgur.com/htx4mGr.png)
![](https://i.imgur.com/QN6zPnS.png)
![](https://i.imgur.com/BFubDaJ.png)

>進度 : [Deadlock (L22)](/AO3MgAd2R6eZUcCF0GFJZQ)