162 lines
5.7 KiB
Markdown
162 lines
5.7 KiB
Markdown
15/10/20
|
||
|
||
## Peterson's Solution
|
||
|
||
**Peterson's solution** is a **software based** solution which worked well on **older machines**
|
||
|
||
Two **shared variables** are used
|
||
|
||
1. *turn* - indicates which process is next to enter its critical section.
|
||
2. *Boolean flag [2]* - indicates that a process is ready to enter its critical section
|
||
|
||
* Peterson's solution can be used over multiple processes or threads
|
||
* Peterson's solution for two processes satisfies all **critical section requirements** (mutual exclusion, progress, fairness)
|
||
|
||
`````c
|
||
do {
|
||
flag[i] = true; // i wants to enter critical section
|
||
turn = j; // allow j to access first
|
||
while (flag[j] && turn == j);
|
||
// whilst j wants to access critical section
|
||
// and its j’s turn, apply busy waiting
|
||
// CRITICAL SECTION
|
||
counter++
|
||
flag[i] = false;
|
||
// remainder section
|
||
} while (...);
|
||
`````
|
||
|
||
**Figure**: *Peterson's solution for process i*
|
||
|
||
```c
|
||
do {
|
||
flag[j] = true; // j wants to enter critical section
|
||
turn = i; // allow i to access first
|
||
while (flag[i] && turn == i);
|
||
// whilst i wants to access critical section
|
||
// and its i’s turn, apply busy waiting
|
||
// CRITICAL SECTION
|
||
counter++
|
||
flag[j] = false;
|
||
// remainder section
|
||
} while (...);
|
||
```
|
||
|
||
**Figure**: *Peterson's solution for process j*
|
||
|
||
Even when these two processes are interleaved, its unbreakable as there is always a check to see if the other process is in the critical section.
|
||
|
||
### Mutual exclusion requirement:
|
||
|
||
The variable turn can have at most one value at a time.
|
||
|
||
* Both `flag[i]` and `flag[j]` are *true* when they want to enter their critical section
|
||
* Turn is a **singular variable** that can store only one value
|
||
* Hence `while (flag[i] && turn == i);` or `while (flag[j] && turn == j);` is true and at most one process can enter its critical section (mutual exclusion)
|
||
|
||
**Progress**: any process must be able to enter its critical section at some point in time
|
||
|
||
> Processes/threads in the **remaining code** do not influence access to critical sections
|
||
>
|
||
> If a process *j* does not want to enter its critical section
|
||
>
|
||
> * `flag[j] == false`
|
||
> * `white (flag[j] && turn == j)` will terminate for process *i*
|
||
> * *i* enters critical section
|
||
|
||
### Fairness/bounded waiting
|
||
|
||
Fairly distributed waiting times/process cannot be made to wait indefinitely.
|
||
|
||
> If P<sub>i</sub> and P<sub>j</sub> both want to enter their critical section
|
||
>
|
||
> * `flag[i] == flag[j] == true`
|
||
> * `turn` is either *i* or *j* assuming that `turn == i` *i* enters it's critical section
|
||
> * *i* finishes critical section `flag[i] = false` and then *j* enters its critical section.
|
||
|
||
Peterson's solution works when there is two or more processes. Questions on Peterson's solution with more than two solutions is not in the spec.
|
||
|
||
|
||
**Disable interrupts** whilst **executing a critical section** and prevent interruptions from I/O devices etc.
|
||
|
||
For example we see `counter ++` as one instruction however it is three instructions in assembly code. If there is an interrupt somewhere in the middle of these three instructions bad things happen.
|
||
|
||
```c
|
||
register = counter;
|
||
register = register + 1;
|
||
counter = register;
|
||
```
|
||
|
||
Disabling interrupts may be appropriate on a **single CPU machine**, not on a multi-core processor though. This means multiple cores can take a value from memory, manipulate that value (in this example iterating it) whilst not knowing the value has already changed on a different core and write back the wrong value to memory. This can lead to `1+1+1=2`.
|
||
|
||
### Atomic Instructions
|
||
|
||
> Implement `test_and_set()` and `swap_and_compare()` instructions as a **set of atomic (uninterruptible) instructions**
|
||
>
|
||
> * Reading and setting the variables is done as **one complete set of instructions**
|
||
> * If `test_and_set()` / `sawp_and_compare()` are called **simultaneously** they will be executed sequentially.
|
||
>
|
||
> They are used in combination with **global lock variables**, assumed to be `true (1) ` is the lock is in use.
|
||
|
||
#### Test_and_set()
|
||
|
||
```c
|
||
// Test and set method
|
||
boolean test_and_set(boolean * bIsLocked) {
|
||
boolean rv = *bIsLocked;
|
||
*bIsLocked = true;
|
||
return rv;
|
||
}
|
||
|
||
// Example of using test and set method
|
||
do {
|
||
// WHILE the lock is in use, apply busy waiting
|
||
while (test_and_set(&bIsLocked));
|
||
// Lock was false, now true
|
||
// CRITICAL SECTION
|
||
...
|
||
bIsLocked = false;
|
||
...
|
||
// remainder section
|
||
} while (...)
|
||
```
|
||
|
||
* `test_and_set()` must be **atomic**.
|
||
* If two processes are using `test_and_set()` and are interleaved, it can lead to two processes going into the critical section.
|
||
|
||
```c
|
||
// Compare and swap method
|
||
int compare_and_swap(int * iIsLocked, int iExpected, int iNewValue) {
|
||
int iTemp = *iIsLocked;
|
||
if(*iIsLocked == iExpected)
|
||
*iIsLocked = iNewValue;
|
||
return iTemp;
|
||
}
|
||
|
||
// Example using compare and swap method
|
||
do {
|
||
// While the lock is in use (i.e. == 1), apply busy waiting
|
||
while (compare_and_swap(&iIsLocked, 0, 1));
|
||
// Lock was false, now true
|
||
// CRITICAL SECTION
|
||
...
|
||
iIsLocked = 0;
|
||
...
|
||
// remainder section
|
||
} while (...);
|
||
```
|
||
|
||
|
||
|
||
`test_and_set()` and `swap_and_compare()` are **hardware instructions** and **not directly accessible** to the user.
|
||
|
||
**Disadvantages**:
|
||
|
||
* **Busy waiting** is used. When the process is doing **nothing** just sitting in a loop, the process is still eating up processor time. If I know the process won't be **waiting for long busy waiting is beneficial** however if it is a long time a blocking signal will be sent to the process.
|
||
* **Deadlock** is possible e.g when two locks are requested in opposite orders in different threads.
|
||
|
||
The OS uses the hardware instructions to implement higher level mechanisms/instructions for mutual exclusion i.e. **mutexes** and **semaphores**.
|
||
|
||
|
||
|