Test and Set

Test-And-Set

Remember back to 315 when we did H/W solutions to the critical section problem. Test-And-Set is an atomic CPU instruction that read a memory location, set it to 1, and then returned the original value in one indivisible step. By surrounding a critical section like this:

/* initially int lock = 0 */

while( TNS(&lock) );

-- CRITICAL SECTION

lock = 0;

we ensure that only one process can execute the critical section at a time no matter how many processes would like to.

Using Test-And-Set has an advantage over disabling interrupts. Disabling interrupts disables interrupts for the whole system. If a process is in the kernel, no other process can also be in the kernel, even if that other process is in a completely separate part of the kernel. Using Test-And-Set, however, we can create a different lock for every data structure. This way, concurrency is impeded only if two processes want to manipulate the same data structure, not simply because they both want to enter the kernel. Also, this approach allows interrupts to proceed and be responded to even if a process is in the kernel.

So - why doesn't XINU adopt this approach? Because it is more complex. You have to reason more about which routines in the kernel might interfere with one another. You still have to be sure you don't make any blocking calls in the kernel (blocking in a CS is a no-no for the (hopefully) obvious reasons.

Finally, if interrupts are not disabled, you have to do something to avoid being context-switched out. Not because you are worried that another process will enter the CS (none will - you've protected it), but because it is silly for another process to be running some application code while there is a line-up of processes waiting for entry to some part of the O/S. One way to ensure this is to raise the priority of the process in the kernel until it leaves the kernel.

The only drawback to all this is the extra complexity - both in terms of implementation and in terms of execution efficiency.

1