Understanding the TestAndSet() Instruction and its Effects

[Peon666]

I understand that the purpose of the TestAndSet() instruction is to test and contents of the register and set new values. (returning the old value). I have a question regarding this instruction:

function TestAndSet(boolean lock) {
    boolean initial = lock
    lock = true
    return initial
}

-Wikipedia.

In this code, initial is the old value, and lock is the new one. The instruction:

boolean initial = lock

replaces the old value with the new one. And the instruction:

 return initial

returns the modified value. But what does this instruction do?:

  lock = true

I'd be really thankful if someone explains this a bit.

 

[Filip Larsen]

The function implements a simple swap operation. It stores the old value (so it can return it), sets the new value to true, and returns the old value. To understand it in a concurrent context you should consider the entire function body executing like in a critical region, meaning that only one of many concurrent invocations of the function (on the same lock) will be running at a time.

Assuming the lock initially is released (value false) a bunch of concurrent calls to TestAnd Set will only allow one of the calls (namely the first to get access) to return false whereas all the rest will return true indicating the lock has already been taken. Callers can then busy-wait until they get false from TestAndSet and then assume they have the lock until they clear the lock by assigning it false.

 

[rcgldr]

Depending on the cpu and hardware architecture, test and set is usually implemented as a "indivisible" (also described as atomic or non-interruptable) operation, where both the read and write take place without the possibility of another task or cpu intervening between the read and write. For memory operations, it's implemented via a bus "lock" during the "read modify write" cycle. (The memory operation also invalidates any cached images of that memory location in other cpus).

The purpose is to provide multiple tasks and/or cpu's a means of synchronization.

For Intel X86 cpu's XCHG is always indivisible, and a few other instrutions can be made indivisible by using the "LOCK" prefix. For Motorola 68000 family, TAS (test and set) is indivisible.

 

[Peon666]

Thanks for the response, both of you. I understand the purpose behind TestAndLock(), but I'm having problems understanding a code given in the textbook related to it. Here's the code:

boolean waiting[n];
boolean lock;
do{
    waiting[i]=TRUE;
    key=TRUE;
    while (waiting[i] && 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;

    // Remainder Section.

}while(TRUE)

The Book says:

"These data structures are initialized to false" (about: boolean waiting[n]; and boolean lock;)

-> Why are they initialized to false? Does this mean that they are NOT occupied as initially?

"P(i) can enter it's critical section only if waiting==FALSE or key=FALSE"

-> I understand the waiting part but what does key=FALSE part mean? (key is a local variable for each process.)

"The value of key can becomes false only if TestAndSet() is executed"

-> How does that happen? Doesn't TestAndSet return TRUE?

Finally, I have serious problem understanding this code more specifically (it's a part of the above code):

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

Besides, in the code initially:

do{
    waiting[i]=TRUE;
    key=TRUE;

Why are the values initially TRUE?

And in the end of the code why do we use:

while(TRUE)

I tried to find explanations online but couldn't find them of much help. I'd highly appreciate if anyone would take some time to help me clarify these concepts. If alternatively, I'd be thankful if you provide me some online resource explaining these problems in detail.

Thanks.

 

[rcgldr]

I have no idea what the rest of the code is trying to accomplish. A better example would be these functions:

volatile int lock;

void Lock(int * lock)
{
    while(0 != testandset(&lock));
}

void Unlock(int *lock)
{
    *lock = 0;    // may require some means to force a cache flush
}

Assume testandset(&lock) always sets lock to 1. At start up, lock needs to be initialized to zero. When testandset() is called, if lock is currently set to 1, then it returns a 1 and re-writes a 1 to lock, with no effective change to lock (although the write operation may invalidate any cached values for it). If lock is currently set to 0, then it's changed to a 1 without possiblity of any other task or cpu reading lock before that instance of testandset() changes lock to a 1, and testandset() will return a 0, indicating that lock was not set before the call.

The issue with this crude implemenation is that any cpu waiting for "lock" to be freed is stuck in a tight loop, rather than running other tasks. Normally stuff like this is incoported into an multi-tasking OS with multi-cpu support. In the case of Windows, semaphores and mutex's are the common means to synchronize multiple threads and/or tasks.

 

[Filip Larsen]

Why are they initialized to false? Does this mean that they are NOT occupied as initially?

Yes. From what I can gather from the code you quoted, the lock variable is used to create a critical section in which the waiting flags (and possibly other stuff in the section marked "remaining code") can be updated without race condition, so it has to start out false. If it was initialized to true (or if a process forgot to set lock to false when exiting its critical region) the lock will no longer be obtainable for any process.

I understand the waiting part but what does key=FALSE part mean? (key is a local variable for each process.)

The key variable is just used to hold the result of the TestAndSet call. As the code appears here where key only seems to be used in the initial wait for lock, the code could be rewritten without use of that variable by testing directly on the return value from TestAndSet.

Doesn't TestAndSet return TRUE?

This is what I tried explain earlier. The TestAndSet method returns false to the caller who obtains the lock. Every other caller will get a true value, which means that they must try again "later" to obtain the lock.

Finally, I have serious problem understanding this code more specifically (it's a part of the above code):

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

Besides, in the code initially:

do{
    waiting[i]=TRUE;
    key=TRUE;

Why are the values initially TRUE?

The loop finds another process who is also waiting and if it does, marks that process as no longer waiting, and if it doesn't it releases the lock early (I assume the process also releases the lock in some of the code not shown). Note that only one process at a time can do this search as it is guarded by the lock.

The process looks like a variation of the dining philosophers, so I assume waiting means waiting for a fork

And in the end of the code why do we use:

while(TRUE)

It is a common idiom and is simply used to make the process loop forever.

I tried to find explanations online but couldn't find them of much help. I'd highly appreciate if anyone would take some time to help me clarify these concepts. If alternatively, I'd be thankful if you provide me some online resource explaining these problems in detail.

I am not aware of any on-line resources on this, but I assume there must be plenty. I got my training long time ago reading Principles of Concurrent and Distributed Programming: Algorithms and Models, Ben-Ari, Prentice-Hall International Series in Computer Science, 1982.

 

[rcgldr]

I don't have an example similar to your text, but did I write an example Windows multi-threaded program that just copies a file. One thread reads a file, the other thread writes a file. It shows how to use mutexes and semphores, using them to support inter-thread communication via single linked list fifo messages. One key aspect of this is WaitForMultipleObjects(), which combines wait for mutex lock, wait for non-zero semaphore count, and decrement semaphore count, into one indivisible operation, eliminating any priority issues between threads using the messaging functions I wrote.

Although there's a significant coding overhead to set the messaging system up, the two main threads that use the messaging functions, ThreadFile0() and ThreadFile1(), are very simple and small.

http://jeffareid.net/misc/mtcopy.zip

 

[Peon666]

Thanks a lot again, both of you. This really helped me understand the problem more clearly. And thanks for the resources as well. I guess I need more practice.

Regards.