What is a mutual exclusion?
No two processes are at the critical section at the same time. ()
What is a deadlock
Deadlock is a situation where two or more concurrent processes/threads mutually wait for each other to make progress, so that none of them get any further.
what is starvation?
Starvation, in general, means a situation where some process has been denied service for a long time or has been repeatedly denied service. This can happen due to deadlock or scheduling policy
How the mutual exclusion problem can be solved?
By an object that guarantees mutually exclusive access by processes to a shared resource - the mutex.
What problems do we expect the mutex to solve?
- mutual exclusion 2. deadlock 3. starvation
What is a brute force solution?
exhaustive search method in which you try all the possibilities to reach the solution of a problem.
Why not instead of mutex we disable interrupts?
- If we disable interrupts preemption would not happen! we can disable interrupts, do our job and then enable interrupts. Well:*
- user processes are not allowed to disable interrupts*
- Disabling interrupts must be done for a very short period of time*
- does not solve the problem in a multi-processor system.*
Why not use a simple lock?
- We prevent deadlock - if wishes, any process will eventually enter CS.*
- We don’t prevent mutual exclusion - two processes might enter CS.*
- We don’t prevent starvation - some process might try to enter CS but other processes will precede it over and over again.*
Why not use strict alternation?
- It is designed for only two processes*
- Mutual exclusion works good.*
- deadlock and starvation are not satisfied because if one of the processes does not want to enter CS again while the other does, we’ll have deadlock. if the other wishes to enter CS ones in a long time while the other process tries frequently, we’ll have waiting problem.*
Why not use flag array?
- mutual exclusion - yes. The two processes cannot simultaneously enter the CS.*
- deadlock - no, if both processes simultaneously execute line 1, then both deny the other entering the CS.*
- starvation - deadlock -> starvation*
Why not use Peterson’s algorithm?
mutual exclusion: fixed.
turn can have one of two possible values: 0 or 1. thus the two process cannot simultaneously enter the CS.
deadlock - Fixed.
explained in starvation.
starvation - fixed.
b[i] = true means intention. turn = i, means it is i’s turn to enter the CS. Assume i’m process 1 and i want to enter the CS: if process 0 have no intention, b[1]=false and i’m in. If he does have intention, we’re racing. if the value of turn is 0 on my while loop i get in. else, process 1 gets in. once finished, he sets b[1] = false. means he has no intention to enter. then i can enter. moreover, if process 1 wants immediately to enter again he would set turn = 1, thus he’s stuck in the while loop till i enter.
What is the idea behind Peterson’s 2 algorithm?
- Two fields help us achieve all the three goals of the mutex:*
- b[0] - announce the intention of owning the lock*
- once process i finishes, if process (i-1) has intention, the later gets in. (startvation-free)
- turn - to settle a race. The first to announce its turn is the first to enter the CS. (deadlock-free)*
- Tournament tree.*
- What is the relation between Peterson’s 2 and the tournament tree?*
- The tournament tree is based on the idea that every lock is open for a race of exactly two processes.*
- Along the tree, each node represents a lock where two of its children are racing for it. Each rach is implemented using Peterson’s 2 implementation.*
Bakery Algorithm:
- Take a look at the following case:*
- Process 1 and process 2 try to enter the CS: process 1: 1 + max{number[j]} is computed to be the value of X, but X is not yet assigned to number[1].*
- context switch*
- process 2: 1 + max{number[j]} is computed and is assigned to number[2] s.t. number[2]=X. process 2 enters the for loop and because number[1] = 0 he gets out of the loop and then..*
- context switch.*
- process 1 is then back to life, number[1] = X. It enters the loop and gets out because the condition (number[2],2)>(number[1],1) is satisfied.*
both processes are in the CS.
How the mutual exclusion problem is solved in the Bakery Algorithm?
- the choosing array is added.*
- Set to true, it denotes that a new process has an interntion to receive a number and demans other processes running in the loop to wait until the new process gets its number.*
What is the test and set instruction?
- It is an atomic instruction:*
- test and set(w){*
- prev = w*
- w = 1*
- return prev }*
- w might get one of two possible values: 0 or 1.*
Decide.
- mutual exclusion?
- deadlock freedom?
- starvation freedom?
- initially: w = 0;*
- Program for process i:*
- while(test and set(w)!=0); CS w=0*
- yes - because the condition is atomic, only one might enter.*
- yes - no theoretical situation in which threads are blocked forever*
- no - some process might wait very long for his turn if a lot are trying to access the CS non-stop.*
How is test and set can help us solve the starvation problem?
- show you are interest*
- If there is not race - enter the CS(test&set)*
- If there is a race, an order is maintained. The running process will release its consecutive process by setting the latter’s intention to false.*
