## 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(); // <--
}
}
```
>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
* moniter
>進度 : [Deadlock (L22)](/AO3MgAd2R6eZUcCF0GFJZQ)
Sign in with Wallet
Connect another wallet