# Process Syncronization
---
## Cooperative vs Independent
- Cooperative processes share state
- The actions of cooperative processes depends on the actions of the others
- But all the processes are independent and isolated
---
## Producer-consumer problem
- It is a recurring problem in computing.
- It is necessary to synchronize the consumer process and the production process in order to
- Avoid consumption if there is nothing to consume
- Avoid overproduction, in case there is no space in the buffer.
Note:
Decouple activities from each other, independent activities that may have different temporal requirements, so that they admit different configurations in terms of the number of producers and consumers.
We can speak here by way of introduction of PUB/SUB architectures
---
## Producer code
```cpp=
do {
...
produce_a_new_element(thing)
...
while (counter == MAX_PLACES) do_nothing();
buffer[producer_pointer] = thing;
producer_pointer = (producer_pointer + 1) % MAX_ELEMENT;
counter = counter + 1;
} while (TRUE);
```
:::spoiler What does `do_nothing()` means?
It is called **busy wait**. It will still take some time before we can solve that.
:::
---
## Consumer code
```cpp=
do
{
while (counter == 0) do_nothing();
thing = buffer[consumer_pointer];
consumer_pointer = (consumer_pointer + 1) % MAX_ELEMENT;
counter = counter - 1;
...
use_produced_element(thing)
...
} while (TRUE);
```
:::spoiler What happens if both producer and consumer simultaneously do `counter + 1` and `counter - 1` respectively?
It is a non-deterministic situation called **race condition**
:::
---
## Race conditions
| `counter + 1` | `counter - 1` |
| ---- | --- |
| `load r0, counter` | `load r0, counter` |
| `add r0, 1` | `sub r0, 1` |
| `store r0, counter` | `store r0, counter` |
---
## Why there are race conditions?
- They happend because of the different relative speed between two processes when operating on shared data.
- Depending on that speed we obtain different results (not deterministic)
- The increase or decrease operation is not atomic
:::danger
An atomic operation is one that is either fully executed or not executed at all.
:::
- We need parts of the code to be executed exclusively: **critical sections**
---
## Critical section
- Code section in which shared variables are updated
- The **mutual exclusion** is a mechanism that ensures that only one process accesses a critical section exclusively.
---
## Critical section requirements
- Mutual exclusion must be ensured
- Progress must be ensured
- Limited waiting time must be guaranteed
Note:
- Progress: a process that is outside the critical section should not prevent another from entering the critical section (This is well illustrated by an example below)
- Limited wait: a process that wants to enter the critical section must be able to do so in a finite time
---
## How to provide critical sections
- Control variables
- Specific machine instructions (`test_and_set`, `swap`)
- Operating system primitives (semaphores)
- Solutions provided by third parties (language, external services, etc.)
Note:
- All solutions assume that programmes advance (progress) and that the relative speed of some cannot be assumed with respect to others (the effects of OS CPU schedulling)
---
## Control variables (first try)
- We assume that load and store machine operations are atomic
- Two threads $T_i$ y $T_j$ share the `turn` variable
```cpp=
do {
while (turn != i) do_nothing();
// CRITICAL SECTION
turn = j;
....
} while (TRUE);
```
- :heavy_check_mark: mutual exclusion
- :negative_squared_cross_mark: progress
- :negative_squared_cross_mark: finite wait
Note:
El mismo proceso no puede entrar dos veces seguidas, incluso si el otro proceso no necesita entrar. Eso viola la condición de progreso.
---
## Control variables (second try)
```cpp=
flag[i] = false
flag[j] = false
```
`flag` variable signals the intention of a process `i` to enter the critical section
```cpp=
do {
while (flag[j]) do_nothing();
flag[i] = true;
// CRITICAL SECTION
flag[i] = FALSE;
...
} while (true);
```
- :negative_squared_cross_mark: mutual exclusion
- :heavy_check_mark: progress
- :heavy_check_mark: finite wait
---
## Control variables (third try)
```cpp=
flag[i] = false
flag[j] = false
```
`flag` variable signals the intention of a process `i` to enter the critical section
```cpp=
do {
flag[i] = true;
while (flag[j]) do_nothing();
// CRITICAL SECTION
flag[i] = FALSE;
...
} while (true);
```
- :heavy_check_mark: mutual exclusion
- :negative_squared_cross_mark: progress
- :negative_squared_cross_mark: finite wait
---
## Control variables (The Dekker's Algorithm)
```cpp=
flag[i] = false
flag[j] = false
turno = i
```
```cpp=
do {
flag[i] = true;
turn = j;
while (flag[j] && (turn == j)) do_nothing();
// CRITICAL SECTION
flag[i] = false;
resto de la sección
} while (true);
```
- :heavy_check_mark: mutual exclusion
- :heavy_check_mark: progress
- :heavy_check_mark: finite wait
---
## How does `test_and_set` work?
```
test_and_set(&memory)
```
**pseudocode in C**
```cpp=
int test_and_set (int *memory_position) {
int aux;
aux = *dest;
*dest = TRUE;
return (aux);
}
```
```cpp=
do {
while (test_and_set (&lock)) do_nothing();
// CRITICAL SECTION
lock = false;
...
} while (TRUE);
```
---
## Critical sections with `test_and_set`
- :heavy_check_mark: mutual exclusion
- :heavy_check_mark: progress
- :heavy_check_mark: finite wait
- :heavy_check_mark: easy to extend to many processes
- :negative_squared_cross_mark: require shared memory
- :negative_squared_cross_mark: uses busy wait
---
## Semaphores
- They are objects managed by the kernel
- It is a special type of variable that allows two operations
- `P(S)` Wait until the semaphore is positive, and then decrease it.
- `V(S)` Increase the semaphore by one.
- Both operations `P` and `V` are atomic
Note:
- It is the operating system that guarantees that operations are atomic.
- Please note that how the operating system is able to guarantee atomic execution will be explained later.
---
### The producer-consumer problem with semaphores
- The consumer waits if there is nothing to consume
- The producer waits if there is no room left in the buffer
- All the operations have to be done in mutual exclusion
```
smf_full <- 0 ; Counts the number of elements in the buffer
smf_empty <- N; Counts the number of free positions in the buffer
mutex <- 1; to provide mutual exclusion
```
---
#### Producer code
```cpp=
data = produce()
P(sem_empty)
P(mutex)
push(data)
V(mutex)
V(sem_full)
```
#### Consumer code
```cpp=
P(sem_full)
P(mutex)
data = pop()
V(mutex)
V(sem_empty)
```
---
### Some open questions?
- Does the order of operations `P` and `V` matter?
- What if there were two producers or two consumers?
- If one participant had to wait, would it be a busy wait?
- What are the implications in CPU schedulling?
---
## Semaphore implementation
- `P` and `V` are software constructions
- Both of them involve and rely on the kernel to:
- Avoid race conditions :arrow_right: mutual exclusion
- Avoid busy-waiting :arrow_right: synchronization and state of a process
```clike!
typedef struct {
int counter;
queue q;
}
```
---
### Implementation guidelines: `P(sem)`
```clike!
P (Semaphore sem) {
CLI; //Disable interrupts
if (sem.counter >0) {
sem.counter --;
STI; //Enable interrupts
return;
}
sem.q.add(calling_process);
set_to_sleep(calling_process);
call_scheduler();
}
```
---
### Implementation guidelines: `V(sem)`
```clike!
V (Semaphore sem) {
CLI; //Disable interrupts
if (is_empty(sem.q) {
sem.counter ++;
} else {
sem.q.pop(calling_process);
wake_up(calling_process);
}
STI; //Enable interrupts
call_scheduler(); // Depending on the scheduling policy
}
```
---
## Synchronization examples
- The producer and consumers problem.
- The sleeping barber problem.
- The Readers–writers problem.
- The dining philosophers problem.
<div style="padding-top: 1em; text-align: left; font-size: small">Andrew S. Tanenbaum (2001). Modern Operating Systems (PDF) (2nd ed.). Upper Saddle River, NJ: Pearson. p. 129. ISBN 9780130313584</div>
---
### The sleeping barber problem
A barbershop with one barber, one barber chair, and a waiting room with n chairs for waiting customers.
- If no customers, the barber falls asleep in the chair.
- A customer must wake the barber if he is asleep.
- If a customer arrives while the barber is working, the customer leaves if all chairs are occupied otherwise sits and wait.
- When the barber finishes a haircut, he inspects the waiting room to see if there are any waiting customers and falls asleep if there are none
<div style="padding-top: 1em; text-align: left; font-size: small">Wikipedia contributors. "Sleeping barber problem." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 20 Aug. 2024. Web. 11 Nov. 2024.</div>
----
#### The barber
```clike!
do {
P(clients);
P(mutex);
// Critical region
clients_waiting --;
V(barbers);
V(mutex);
// Cut the hair
} while (true);
```
----
#### The client
```clike!
do {
P(mutex);
if (clients_waiting < CHAIR_COUNT) {
clients_waiting ++;
V(clients);
V(mutex);
P(barbers);
// Cut the hair
} else {
V(mutex);
// Leave, as there are no chairs
}
} while (true);
```
---
### The readers-writer problem
- Writers only enter while no other writer or reader is in the DB. Writers have priority over readers.
- Readers only enter if no writer is accessing or waiting.
Data structures:
- `writers` semaphore
- `readers` semaphore
- `mutex` semaphore
- `RA`, `WA`, `RW`, `WW`: readers accessing, writers accessing, readers waiting, writers waiting.
----
#### Readers
```clike!
P(mutex)
if (WA+WW ==0) {
// No writers accessing or waiting
RA++;
V(readers);
} else {
RW++;
}
V(mutex);
P(readers);
// Access the DB to read
P(mutex);
RA--;
if (RA==0 && WW>0) {
// No more readers and writers waiting
// Unlock one writer
V(writers)
WW--;WA++;
}
V(mutex);
```
----
#### Writers
```clike!
P(mutex)
if (WA+RA+WW ==0) {
// No writers accessing or waiting
// No readers accessing
V(writers);
WA++;
} else {
WW++;
}
V(mutex);
P(writers);
// Access the DB to write data
P(mutex);
WA--;
if (WW>0){
// There are writers waiting
V(writers);
WA++; WW--;
} else {
while (RW>0) {
V(readers);
RA++; RW--;
}
}
V(mutex)
```
{"metaMigratedAt":"2023-06-15T17:14:56.839Z","metaMigratedFrom":"YAML","title":"Sincronización de Procesos","breaks":true,"slideOptions":"{\"transition\":\"slide\",\"theme\":\"solarized\"}","description":"Cooperative processes share state","contributors":"[{\"id\":\"93855254-5bcf-438a-b2d1-f9f805e036e4\",\"add\":12725,\"del\":1932}]"}