OS - mutual exclusion

Question 1

What is a mutual exclusion?

Answer 1

No two processes are at the critical section at the same time. ()

Question 2

What is a deadlock

Answer 2

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.

Question 3

what is starvation?

Answer 3

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

Question 4

How the mutual exclusion problem can be solved?

Answer 4

By an object that guarantees mutually exclusive access by processes to a shared resource - the mutex.

Question 5

What problems do we expect the mutex to solve?

Answer 5

1. mutual exclusion 2. deadlock 3. starvation

Question 6

What is a brute force solution?

Answer 6

exhaustive search method in which you try all the possibilities to reach the solution of a problem.

Question 7

Why not instead of mutex we disable interrupts?

Answer 7

• If we disable interrupts preemption would not happen! we can disable interrupts, do our job and then enable interrupts. Well:*
• 1. user processes are not allowed to disable interrupts*
• 2. Disabling interrupts must be done for a very short period of time*
• 3. does not solve the problem in a multi-processor system.*

Question 8

Why not use a simple lock?

Answer 8

• 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.*

Question 9

Why not use strict alternation?

Answer 9

• 1. It is designed for only two processes*
• 2. Mutual exclusion works good.*
• 3. 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.*

Question 10

Why not use flag array?

Answer 10

• 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*

Question 11

Why not use Peterson’s algorithm?

Answer 11

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.

Question 12

What is the idea behind Peterson’s 2 algorithm?

Answer 12

• Two fields help us achieve all the three goals of the mutex:*
• 1. 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)
• 2. turn - to settle a race. The first to announce its turn is the first to enter the CS. (deadlock-free)*

Question 13

• Tournament tree.*
• What is the relation between Peterson’s 2 and the tournament tree?*

Answer 13

• 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.*

Question 14

Bakery Algorithm:

Answer 14

• 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.

Question 15

How the mutual exclusion problem is solved in the Bakery Algorithm?

Answer 15

• 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.*

Question 16

What is the test and set instruction?

Answer 16

• 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.*

Question 17

Decide.

• mutual exclusion?
• deadlock freedom?
• starvation freedom?
• initially: w = 0;*
• Program for process i:*
• while(test and set(w)!=0); CS w=0*

Answer 17

• 1. yes - because the condition is atomic, only one might enter.*
• 2. yes - no theoretical situation in which threads are blocked forever*
• 3. no - some process might wait very long for his turn if a lot are trying to access the CS non-stop.*

Question 18

How is test and set can help us solve the starvation problem?

Answer 18

• 1. show you are interest*
• 2. If there is not race - enter the CS(test&set)*
• 3. 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.*