**The entire code and discussion ideas for this post have been taken from Galvin. The slides of this book helped me immensely during GATE preparation and I think they are really great, so are the ones of the book by Korth for DBMS. Whenever I happen to remember some other ones, I will jot them down in some un-related posts :P
So far, we have seen a few software solutions to the 2-process synchronization problem. Now, we have more than 2 processes, Let us assume that we have n processes. Before designing software solutions for this situation, let us diverge a bit.
Till now, in the software solutions we have seen, before entering its critical section, each process acquires some kind of a lock on the shared data item, enters the critical section, and after it has finished, releases the lock on that data item.
But what if we have a situation where a process is not allowed to interrupt while it executes so that there is no question of mutual exclusion being violated? For one, this approach of disabling interrupts will be problematic on multi-processor environments because disabling interrupts on 1 processor won't suffice because a thread on another processor may violate mutual exclusion. So, we have to disable and re-enable interrupts on all processors which is difficult. Also, there will be issues with timing if we disable the clock interrupt.
What if the hardware supports atomic instructions? Operations which give a guarantee that there will be no interrupt while they are executing? One such operation is known as "Test, Set and Lock", abbreviated as TSL.
TSL can be implemented as a function which returns a boolean value. Let us look at its code first.
Before analyzing what is happening inside this piece of code, let us see how to implement Mutual Exclusion using TSL.
So, let us see how to implement Mutual Exlcusion using TSL.
So, when a process wants to enter the critical section, it will execute the code given just above. It is now time to explain what exactly is meant by the fact that TSL is atomic. It means that from the time the TSL is function is invoked by a process, and until the return value of the TSL function is received by the process inside its while loop, the process cannot be pre-empted.
Analysis
Till now, we have discussed the following posts on Process Synchronization. Before reading this post, please read the following post on Process Synchronization:-
- Part 1: The Critical Section Problem
- Part 2: Turn Variable Solution
- Part 3: Flag Array Solution
- Part 4: Peterson's Solution
So far, we have seen a few software solutions to the 2-process synchronization problem. Now, we have more than 2 processes, Let us assume that we have n processes. Before designing software solutions for this situation, let us diverge a bit.
Till now, in the software solutions we have seen, before entering its critical section, each process acquires some kind of a lock on the shared data item, enters the critical section, and after it has finished, releases the lock on that data item.
But what if we have a situation where a process is not allowed to interrupt while it executes so that there is no question of mutual exclusion being violated? For one, this approach of disabling interrupts will be problematic on multi-processor environments because disabling interrupts on 1 processor won't suffice because a thread on another processor may violate mutual exclusion. So, we have to disable and re-enable interrupts on all processors which is difficult. Also, there will be issues with timing if we disable the clock interrupt.
What if the hardware supports atomic instructions? Operations which give a guarantee that there will be no interrupt while they are executing? One such operation is known as "Test, Set and Lock", abbreviated as TSL.
TSL can be implemented as a function which returns a boolean value. Let us look at its code first.
Before analyzing what is happening inside this piece of code, let us see how to implement Mutual Exclusion using TSL.
So, let us see how to implement Mutual Exlcusion using TSL.
So, when a process wants to enter the critical section, it will execute the code given just above. It is now time to explain what exactly is meant by the fact that TSL is atomic. It means that from the time the TSL is function is invoked by a process, and until the return value of the TSL function is received by the process inside its while loop, the process cannot be pre-empted.
Analysis
- Lock is a boolean variable which can hold either true or false.
- In the funtion TSL, the address of the lock variable is being passed which is accepted inside the formal parameter of TSL function in a variable ptr which is a pointer to the variable lock.
- If there is some other process currently executing inside its critical section, the value of lock will be already true.
- In the TSL function, the current value of the variable lock is saved in a local variable and returned to the calling process. Before returning, the value of lock is set to true by its pointer variable. This is a win-win situation. If there is no process currently within the critical section and this process is getting chance to enter, it claims its chance by setting lock to true so that no other process can enter their critical sections. If on the other hand, there is already some other process inside the critical section, then setting lock to true won't do any harm as its already true.
- If lock was false at the time TSL was called which means there was no other process inside the critical section, then this process will get chance to enter its critical section by exiting the waiting while loop.
- After exiting its critical section, this process sets lock to false so that other (waiting) processes can now enter.
- The above code implements mutual exclusion and satisfies progress as well but does not satisfy bounded waiting as there is no guarantee which of the waiting processes will get chance to enter its critical section once a process sets lock to false. It may happen that a slow process always lags behind and concedes the chance to other processes.
No comments:
Post a Comment