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?

  • $\begingroup$ I know how to use it, my question is why the synchronized command doesn't have an internal problem itself! $\endgroup$
    – RunOrVeith
    Commented Aug 9, 2014 at 18:21
  • $\begingroup$ 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. $\endgroup$ Commented Aug 11, 2014 at 7:46

1 Answer 1


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:

  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.

  • 2
    $\begingroup$ 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.) $\endgroup$
    – user4577
    Commented Aug 9, 2014 at 19:33

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.