# Operating system -- classic process synchronization problem

## Producer and consumer issues

### 2. Synchronization relationship: only when the buffer pool is not full can producers put products into it; Consumers can only take products out of the buffer pool if it is not empty.

#### 1. Use recording semaphore to solve the problem

```semaphore mutex = 1, empty = n, full = 0; // Represents the mutually exclusive access to the buffer pool, the number of empty buffers and the number of full buffers in the buffer pool
cobegin
producer() {
while(true){
Produce a product
Swait(empty, mutex);
Put a product into the buffer pool
Ssignal(mutex, full);
}
}
consumer() {
while(true){
Swait(full, mutex);
Remove a product from the buffer pool
Ssignal(mutex, empty);
Consume a product
}
}
coend
```

#### 2. Use AND semaphore to solve

```semaphore mutex = 1, empty = n, full = 0;// Represents the mutually exclusive access to the buffer pool, the number of empty buffers and the number of full buffers in the buffer pool
cobegin
producer() {
while(true){
Produce a product
wait(empty);
wait(mutex);
Put a product into the buffer pool
signal(mutex);
signal(full);
}
}
consumer() {
while(true){
wait(full);
wait(mutex);
Remove a product from the buffer pool
signal(mutex);
signal(empty);
Consume a product
}
}
coend
```

## the dining philosophers problem

### Three solutions

1. At most 4 people are allowed to pick up the chopsticks on the left at the same time to ensure that at least one person can eat;
2. Only when the left and right chopsticks can be used, it is allowed to pick up chopsticks for dinner;
3. Odd numbered philosophers take the left chopsticks first and then the right chopsticks, and even numbered philosophers take the right chopsticks first and then the left chopsticks;

#### At most 4 people pick up the left chopsticks at the same time

```semaphore chopstick = {1, 1, 1, 1, 1}; // Each chopstick corresponds to a mutually exclusive semaphore
semaphore count = 4; // At most 4 people pick up the left chopsticks at the same time
cobegin
Pi() {
while(true) {
reflection
wait(count); // No more than 4 people can pick up the left chopsticks at the same time
wait(chopstick[i]); // Pick up the chopsticks on the left
wait(chopstick[(i+1)%5]); //Pick up the chopsticks on the right
having dinner
signal(chopstick[(i+1)%5]);
signal(chopstick[i);
signal(count);
}
}
coend
```

#### Only when the left and right chopsticks can be used, it is allowed to pick up chopsticks for dinner

```semaphore chopstick = {1, 1, 1, 1, 1}; // Each chopstick corresponds to a mutually exclusive semaphore
cobegin
Pi() {
while(true){
reflection
Swait(chopstick[i], chopstick[(i+1)%5]);
having dinner
Ssignal( chopstick[(i+1)%5], chopstick[i]);
}
}
coend
```

#### Odd numbered philosophers take the left chopsticks first and then the right chopsticks. Even numbered philosophers operate the opposite

```semaphore chopstick = {1, 1, 1, 1, 1}; // Each chopstick corresponds to a mutually exclusive semaphore
cobegin
Pi() {
while(true){
reflection
if (i % 2 == 1) { // Odd scientists left first and then right
wait(chopstick[i]);
wait(chopstick[(i+1)%5];
having dinner
signal(chopstick[(i+1)%5];
signal(chopstick[i]);
}
else {// Odd scientists first right then left
wait(chopstick[(i+1)%5];
wait(chopstick[i]);
having dinner
signal(chopstick[i]);
signal(chopstick[(i+1)%5];
}
}
}
coend
```

### Mutex: read / write mutex and writer mutex

We also need an rcount shaping variable to record the number of readers to maintain read-write mutual exclusion. In order to achieve mutually exclusive access, we also need a mutually exclusive semaphore.

#### Recording semaphore

```int rcount = 0; // Record the number of readers
semaphore rmutex = 1, wmutex = 1; // Mutually exclusive access semaphore for rcount, mutually exclusive semaphore for writer
cobegin
while(true){
wait(rmutex);
if (rcount == 0) {
wait(wmutex);
}
rcount += 1;
signal(rmutex);
wait(rmutex);
rcount -= 1;
if (rcount == 0) {
signal(wmutex);
}
signal(rmutex);
}
}
Writer() {
while(true){
wait(wmutex);
Write operation
signal(wmutex);
}
}
coend
```

Introduce a new semaphore l with an initial value of RN. When there are readers entering, reduce L by 1 through wait(L,1,1). When there are RN readers entering, l is 0 and cannot enter.

```int RN;
semaphore L = RN, mx = 1; // L records the number of readers that can be entered, mx realizing mutual exclusion between reading and writing and between writers
cobegin
while(true){
Swait(L, 1, 1); // L minus one
Swait(mx, 1, 0); // Switch. When mx is 1, it can be read, and mx is 0, it means writing
Ssignal(L,1);
}
}
Writer(){
while(true){
Swait(mx, 1, 1; L, RN, 0); // Write operations can only be performed when there is no writer operation (mx=1) and no reader operation (L=RN)
Write operation
Ssignal(mx, 1);
}
}
coend
```
##### Three special semaphore sets
1. SWAT (S, D, d) has only one semaphore S, and only D resources are allowed to be applied each time. If the number of resources is less than D, it will not be allocated;
2. SWAT (s, 1,1), when s > 1, it is equivalent to a general recording semaphore; When S=1, it is equivalent to mutually exclusive semaphore;
3. SWAT (s, 1,0) is equivalent to a switch. When s > = 1, multiple processes (Readers) are allowed to enter the critical area; when S=0, any process is prevented from entering the critical area;

Keywords: Operating System

Added by Pigmaster on Sun, 19 Dec 2021 16:33:03 +0200