Ancient CS 61 Content Warning!!!!!1!!!
This is not the current version of the class.
This site was automatically translated from a wiki. The translation may have introduced mistakes (and the content might have been wrong to begin with).

Implementing synchronization

Deadlock

Deadlock is a synchronization bug that involves an infinite wait. This makes it rather easy to detect. Deadlock occurs when the following four conditions are met.

If any one of these conditions does not hold, there will not be deadlock.

Wait Graph

A wait graph is a representation of resource and thread dependencies that can be used to detect deadlock.

Lock Ordering

Threads I and II are trying to execute the exch instruction. Thread I wants to execute exch a b and thread II is trying to execute exch b a. Access to a and b are protected with mutexes. The locks involved in this scenario are as follows:

Executing these instructions in the order 1, 2, 3, 4 will result in no deadlock.

Executing these instructions in the order 1, 3, 2, 4 will result in a cycle in the waitgraph and thus deadlock.

Acquiring locks in different orders can lead to cycles in the wait graph. One way to avoid deadlock is to ensure that all code acquires locks in a predefinied order. Lock ordering defines a property such that if a thread holds more than one mutex, then there is a single order in which they were acquired.

Implementing a Bank

Imagine that you have a bank that supports the following transactions.

Two people are trying to withdraw funds from a shared bank account. Person A and Person B both issue a get request and see that the bank account has $10 in it. Then, Person A and Person B both withdraw $5 from the bank account and set the balance to $5. Theoretically, the bank account should be left with $0 inside it. However, in this scenario the bank account is left with $5 in the account.

The problem here is that the increment and decrement operations are not atomic. Between the time person B checks their account balance and the time person B executes a set request to withdraw $5, the bank account balance has changed.

Compare and Swap

The compare and swap (CAS) instruction allows us to perform computations atomically. The compare and swap instruction is atomic but it can be decomposed in the following way.

 int compare_and_swap(unsigned *value, unsigned expected, unsigned desired) { 
   if (*value == expected) { 
     *value = desired; 
     return 1;
   }
   else { 
     return 0; 
   }
 }

Compare and swap will only succeed if the value to be edited matches the expected value. If the expected value does not match the current value, the call will fail. Typically, compare and swap is called in a loop because after a failed call, the solution is to update the value parameter and try again.

Referring back to the bank example, we can replace the set instruction with a CAS instruction.

At this point, another get request should be issued to update the balance and call CAS again with a new balance value.

Atomic instructions

This section concerns the behavior of an x86-64 processor, not the C abstract machine.