Test and Set

Copies the current value of lock into register and stores values of '1' into the lock in a single atomic instruction cycle without any preemption.

 

Initially Lock = 0

 

Code 1 is suffered from mutual exclusion

Test and Set Pseudocode – 

//Shared variable lock initialized to false

boolean lock;

boolean TestAndSet (boolean &target){

    boolean rv = target;

    target = true;

    return rv;

}

while(1){

    while (TestAndSet(lock));

    critical section

    lock = false;

    remainder section

}

Now check Mutual Exclusion for Test and Set Instruction 

 

Example:

 

 

# P0 executes step1, it run TSL instruction. Now load the value of lock (where lock = 0) to R0, now R0 = 0 and assign lock = 1. Then P0 is preempted after execution of line 1.

 

# Now P1 executes step1 (TSL instruction) where loads value of lock (where lock = 1) to R0, now R0 = 1 and assign lock = 1 again as per instruction.

 

# After that P1 execute step2 (CMP R0, #0) compare statement where it will true when R0 = 0. But as per the last instruction value of R0 is 1.

 

# Now when P1 executes step3 (JNZ Step1), then it is true and goes to step 1 again (because the previous compare statement is false i.e R0 ≠ 0). 

 

# Then P1 again will execute step1 and the same phenomenon will happen. And process P1 will be stuck in a loop of steps (step: 1, 2, 3, 1, 2, 3, 1, 2, 3…..) until R0 = 0. This is called busy waiting.

 

So, it is assured that TSL is mutual exclusion.

 

# Now when P0 will be in ready state and will execute the rest of the steps: 2, 3, CS, and 4. Then again lock = 0.

 

# And P1  will break its unwanted loop (busy waiting) because in that case, R0 will be 0.

 

But bounded waiting is not confirmed at TSL.

 

TSL is not portable because TSL is OS instruction.

 

Test and Set Instructions 

1. Mutual Exclusion: Yes

2. Progress: Yes

3. Bounded waiting: No

4. Portability: No