Mutual-exclusion implementation with test and set() instruction.

If a process is executing in its critical section, then no other process is allowed to execute in the critical
section. This is called Mutual exclusion.

Mutual exclusion conditions:

• No two processes simultaneously in the critical region
• No assumptions made about speeds or numbers of CPUs
• No process running outside its critical region may block another process
• No process must wait forever to enter its critical region
• Critical regions with mutual exclusion:

Mutual Exclusion using test and set instruction

What the test-and-set instruction does is as follows. It returns the old value pointed to by the old ptr,
and simultaneously updates said value to new. The key, of course, is that this sequence of operations
is performed atomically. The reason it is called “test and set” is that it enables you to “test” the old
value (which is what is returned) while simultaneously “setting” the memory location to a new value;
as it turns out, this slightly more powerful instruction is enough to build a simple spin lock.

Test-and-Set Instruction:

• It is an instruction that returns the old value of a memory location and sets the memory location value to 1 as a single atomic operation.
• If one process is currently executing a test-and-set, no other process is allowed to begin anothertest-and-set until the first process test-and-set is finished.

 

Implementation:

Initially, lock value is set to 0.

• Lock value = 0 means the critical section is currently vacant and no process is present inside it.
• Lock value = 1 means the critical section is currently occupied and a process is present inside it.

Working:

Step 1:

Process P0 arrives. It executes the test-and-set(Lock) instruction. Since lock value is set to 0, so it returns value 0 to the while loop and sets the lock value to 1. The returned value 0 breaks the while loop condition. Process P0 enters the critical section and executes. Now, even if process P0 gets preempted in the middle, no other process can enter the critical section. Any other process can enter only after process P0 completes and sets the lock value to 0.

Step 2:

Another process P1 arrives. It executes the test-and-set(Lock) instruction. Since lock value is now 1, so it returns value 1 to the while loop and sets the lock value to 1. The returned value 1 does not break the while loop condition. The process P1 is trapped inside an infinite while loop. The while loop keeps the process P1 busy until the lock value becomes 0 and its condition breaks.

Step 3:

Process P0 comes out of the critical section and sets the lock value to 0. The while loop condition breaks. Now, process P1 waiting for the critical section enters the critical section. Now, even if process P1 gets preempted in the middle, no other process can enter the critical section. Any other process can enter only after process P1 completes and sets the lock value to 0.