[Operating System] Concurrency Control

• Race Condition:

Race condition occurs when the result of some computation depends on the exact timing of multiple threads of execution, i.e., the order in which the instructions are executed. Code that updates a variable can be broken into several assembly lines. Because the code is not atomic, if multiple threads are updating a variable at the same time, the result is undetermined.

• Consistency:

Ideally, it shouldn't make a difference whether the requests are executed concurrently or not. We need a consistency model that specifies how the system should behave in the presence of consistency.

The strictest model is sequential consistency, which states that the result of any execution is the same as if the operations of all the processors had been executed in a sequential order.

• Mutual Exclusion:

Code has a critical section where accesses from other threads to the same shared resources will cause problems. To solve this problem, we need mutual exclusion. The idea is to enforce restriction that only one thread can execute the critical section at any time.

• CPU-Level Special Instructions to Achieve Mutual Exclusion:
• Test-and-set: reads a bit in memory, then sets it to 1, and finally returns the value it has read.
• Compare-and-swap: compares a memory cell to a value, and writes a new value to the cell if and only if the values are equal.

Both instructions are atomic; no interruptions are possible. This is guaranteed by the hardware (bus lock, etc).

Special instructions are simple and efficient, and they work for multi-core CPUs. But not every CPU has a special instruction. Also, it still requires busy-waiting.

• Semaphore:

A semaphore is an object with an integer value and the following two operations:

• P: if the semaphore's value is greater than zero, decrement it; if the value is zero, wait until it increases, and then decrement it.
• V: increment the value.

Both P and V are atomic.

There are two kinds of semaphores:

• Binary semaphore: value can only be zero or one.
• Counting semaphore: value can be any integer.

For mutual exclusion, a binary semaphore is enough. Initial value has to be one to indicate that the critical section is open. The program invokes P when entering the critical section, and invokes V when leaving it. 

• Mutex vs. Semaphore:

Mutex is a locking mechanism used to synchronize access to a resource. Only one task can acquire the mutex. There is ownership associated with mutex. Once a mutex is taken, only the owner can release the lock.

Semaphore is a signaling mechanism. It's okay for a process A to take it and B to give it. A semaphore is not protecting a resource from access. The semaphore giver simply notifies whoever the taker that what they were waiting for have happened.

• Deadlock:

Deadlock is a situation in which several processes are waiting for each other to proceed. This could happen on more than two processes if there is circular waiting.