Operating Systems - Synchronization

Process / Thread Synchronisation

Note: This works the same way for processes and threads, so when I say processes it could equally apply to threads.

Pretend you live in a flat with 2 other people. Maybe you already do (now you don't need to pretend!).

• Flatmate #1 wakes up at 8am, sees that you've run out of pilk (pig's milk), then goes out for the day.


• Flatmate #2 wakes up at 9am, sees that you've run out of pilk, then goes out for the day


• Flatmate #3 (that's you!) wakes up at 10am, sees that you've run out of pilk, then goes out for the day.

~~~~~~~~~~~~ some time passes ~~~~~~~~~~~~~

• Flatmate #1 comes home at 3pm with some more pilk


• Flatmate #2 comes home at 4pm with some pilk


• You come home at 5pm with more pilk

Now you have more pilk than you needed! DISASTER! If only there was some sort of computer science based theory you could follow that would be a metaphor for how processes synchronise..

Ok so enough of this unusual-types-of-milk based scenario.

The flatmates looking in the fridge = processes accessing shared data concurrently

Race conditions

This is a situation where several processes are manipulating the same shared data at the same time, and the outcome of the execution is dependent of the order of what is happening.

Example

// Both processes share i

// Let's say i = 4 to begin with

// Process A

....

i++;

...

R1 = load @i;

R1 = R1 + 1;

and now process B:

// process B
...
i--;
...

R2 = load @i;

R2 = R2 - 1;

So i can either come out as 3, 4 or 5 depending on which thread 'wins'

Some definitions

Synchronisation: Using appropriate policies to make sure that cooperating processes work correctly

Critical section: A section of the code where shared data is accessed and manipulated

Mutual exclusion: If one thread is executing in it's critical section, then no other threads can be. We want to achieve this!

Semaphores

We need to make sure that when a process is executing in it's critical section no other process can be doing the same. So if several requests all come in at once, only one process should proceed while the others wait outside their critical sections.

Dijkstra (who you might remember from A-level maths if you were unfortunate enough to take it) came up with the idea of a semaphore. It's a variable integer, we'll call it S, and it can be accessed by two operations that are indivisible.

Operation one: P(S):

while (S <= 0) do { }
S--;

Operation two: V(S):

s++;

Examples

Ok, I don't fully understand semaphores.. so check out wikipedia for a better example. When I understand them, I will edit this. But for now look here. Sorry..

Deadlock

If two or more processes are waiting for something indefinitely that can only be provided by the other. It's like if you're driving and you get to a roundabout, but there's someone at every exit already. No-one has right of way!

The dining philosopher problem is an example of how deadlock might happen.