Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Suppose I have an application with two threads, which both use the same resource. Normally, a synchronized block keeps these threads from messing with the resource in a way the user doesn't expect. I understand why you do this, but I need an explanation how it is done, especially on the following part.

How come acquiring the lock never results in a race condition? For Example: Let t1,t2 be threads that are synchronized on some object obj.

t1 checks if obj has a lock
it doesn't.

                         t2 checks if obj has a lock.
                         it still doesn't.
t1 locks obj.

                         t2 locks obj (which it should not be able to)

How is this prevented?

share|improve this question
    
I know how to use it, my question is why the synchronized command doesn't have an internal problem itself! –  RunOrVeith Aug 9 at 18:21
    
The solution is to use a command that will simply go ahead and try to lock, and fail if it couldn't be done. This doesn't apply only to locking but also to e.g. reading or writing files. –  reinierpost Aug 11 at 7:46

1 Answer 1

up vote 4 down vote accepted

Almost every modern processor has special memory instructions built in specifically to deal with this problem.

For example, many processors have a swap instruction. This atomically swaps a value between a local variable in a thread and a global variable that is shared between threads. (Under the covers the "local variable" will be stored in a machine register and the "global variable" will be stored in memory.)

Suppose the "lock" is stored in the global variable global_lock_var and a value of 0 means "unlocked" and a value of 1 means "locked. Then you do a critical section by:

do:
  local_var = 1
  swap global_lock_var <-> local_var
while local_var == 1
# Critical Section
#   (you only get here if the value of global_lock_var was originally 0, so you have
#    acquired the lock)
global_lock_var = 0  # release the lock

It is also possible to solve the locking problem even on a machine that doesn't have atomic instructions, just load and store instructions, but it is a little bit more complicated. One well known way to do it is by using something called Peterson's algorithm. This requires 3 variables, flagA (used to indicate thread A is trying to acquire the lock), flagB (used to indicate thread B is trying to acquire the lock), and turn (used to indicate who has priority if both are trying to acquire the lock).

# initialization:
flagA = false
flagB = false
turn = 'A'

# thread A:                    # thread B:
flagA = true                   flagB = true     # "I want the lock"
turn  = 'B'                    turn  = 'A'      # "But I'll be polite and give you priority"
while ((flagB == true) &&      while ((flagA == true) &&
       (turn  == 'B')):               (turn  == 'A')):
  # busy wait (do nothing)       # busy wait (do nothing)
# critical section             # critical section
flagA = false                  flagB = false    # "I'm done"

Even though there are "races" all over the place, the algorithm is accounting for the possibilities. If only one of the threads wants to get into the critical section, then the other thread's flag variable will be false (so the turn variable doesn't even get checked.) But if both threads try to acquire the critical section simultaneously then whichever one sets the turn variable last will lose.

share|improve this answer
2  
I especially appreciate the inclusion of Peterson's algorithm showing that atomic read-modify-write is helpful but not strictly necessary. (I would have included more example instructions — test-and-set, compare-and-swap, linked load/store condition — and noted the difference between transactional-memory-like ll/sc and the hard atomic instructions, but the latter is probably going too far down the rabbit hole.) –  Paul A. Clayton Aug 9 at 19:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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