Hardware Solution to Synchronization: (Test & Set)

The critical problem can be solved in a single-processor system at hardware level. We can stop interrupts to occur during modification of a shared variable so that the instruction can be executed without preemption. This solution is not applicable in multi-processor system because disabling of interrupts is time-consuming.


Many machines provide hardware instruction to test and modify a word and swap the contents of words atomically without any interruption. The TestAndSet instruction is executed atomically.


The definition of TestAndSet is as follows:


boolean TestAndSet (boolean &target)


{


boolean rv = target;


target = true;


return rv;


}


A machine that supports TestAndSet instruction, can implement mutual exclusion by using a Boolean variable lock, initialized to false. The structure of such implementation is as follows:


while (1)


{


while (TestAndSet(Iock));


critical section;


lock = false;


remainder section;


}


The Swap instruction is also executed atomically and operates on two word to interchange their contents.


The definition of Swap is as follows:
void Swap(boolean &a, boolean &b)


{


boolean temp = a;


a = b;


b = temp;


}


The implementation of TestAndSet is as follows:


while (1)


{


waiting[I] = true;


key = true;


while (waiting[l] && key)


key = TestAndSet(lock);


waiting[I] = false;


critical section;


j = (I+1) % n;


while ((j != I) && !waiting[j]) j = (j+1)% n;


if(j==I)


lock = false;


else


waiting[j] = false;


}


Proof


Mutual Exclusion: Here, Pi can enter its critical section only if either waiting[i] is true or key is false. The value of key can be false only if TestAndSet instruction is executed. When a process executes, it will find key = false. The remaining processes will have to wait. The value of waiting[i] can be false only if another process leaves its critical section: In this way, only one waiting[i] is false, which maintains mutual exclusion.

Progress: A process that leaves its critical section either sets lock to false or sets Waiting[j] to false. It allows a waiting process to enter its critical section.

Bounded Waiting: A process that leaves its critical section, visits the array in a cycle and finds out any process with waiting[j] = true. It designates that process to enter its critical section. The selected process will also do so when leaving its critical section.

Leave a Reply

Subscribe to Posts | Subscribe to Comments

Blog Archive

Powered by Blogger.

- Copyright © 2013 Taqi Shah Blogspot -Metrominimalist- Powered by Blogger - Designed by Johanes Djogan -