2

Consider this possible implementation of a synchronization mechanism, the goal being that only one thread is in the critical section (CS) at a time:

if (lock)
      wait
else
     lock=1
      CS
     lock=0

Will this work for a multiprocessor system?

1

1 Answer 1

4

No. This won't even work on a single-processor system. Suppose you have two threads doing this. They could be scheduled this way:

thread1                     thread2
if (lock) /*false*/
                            if (lock) /*false*/
                            lock=1
lock=1
/*CS*/
                            /*CS*/
/*CS continues*/
                            /*CS continues*/
                            lock=0
lock=0

You can't implement a lock this way. One of the ways to implement a lock is with a processor instructions that atomically checks the current value of the variable and assigns to it, such as test-and-set. (There are many other possible ways, different CPUs provide different methods and sometimes more than one.)

2
  • Can you tell a way in which we can rectify this code for a uni-processor system? test-and-set will only make it work for multiprocessor systems, right?
    – Gaurav
    Jan 15, 2014 at 3:41
  • @Gaurav Test-and-set is a building block for a spinlock, a lock implementations which is suitable for locks that are taken for a very short time. You need to ensure that the other threads can run while a thread is doing wait. There is little use for a spinlock on a single-processor system except as a building block for a mutex with a wait queue, but it works regardless of the number of processors. Jan 15, 2014 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.