Why do we need synchronization?

A preemptive scheduling algorithm will interrupt and pause a running thread to give another thread a chance to run
If this interruption occurs at an unlucky time, it could result in irreproducible and hard to find bugs known as race conditions

Consider the following C code

counter++;

Although it is a single line of code, it consists of 3 assembly instructions:

LW $t0, counter // load the variable to a register
ADDI $t0, $t0, 1 // increment the value
SW $t0, counter // store the new value back in the variable

Now, consider a system with running threads, t1 and t2, both of which will be attempting to increment counter

Suppose t1 gets there first, and completes the first 2 instructions required for incrementing, but is then interrupted. Now t2 runs the instructions, but, when it loads counter into memory, it still see the old value of 1 since t1 has not yet stored the incremented value. Now both t1 and t2 run the third instruction, but both end up storing 1 in counter. As a result, counter's value is 1, despite being incremented twice.

This bug is know as a race condition the final outcome of the code snippet is non-deterministic and depends on internal decisions made by the OS scheduler. Needles to say, this is an undesirable outcome; we should be able to definitively tell the result of our code regardless of OS decisions.

<aside> 💡

Race condition: A phenomenon in which the behaviour of a program depends on the unpredictable order in which concurrent threads or processes access shared resources, leading to unintended or incorrect outcomes.

</aside>

We’ll refer to any code segment that is susceptible to race conditions as a critical section.

<aside> 💡

Critical section: A section of code in which a shared resource is modified or accessed; usually prone to race conditions

</aside>

Race conditions are the most common bug you will encounter in this project; if you believe your approach is correct but are still getting some unexpected behaviour, it’s probably a race condition.

pintOS offers synchronization primitives that, if used correctly, can prevent race conditions.

How to achieve synchronization?

A synchronization primitive is a tool offered by the OS to help synchronize access to shared resources. There are 3 such primitives offered by pintOS

🔒 Locks

The simplest of the 3 primitives, locks are used to restrict access to a single thread.