Process Synchronisation

Question 1

Define an atomicity high level instruction.

Answer 1

Single operations in high level programs are often compiled into several machine instructions (atomic instructions)

Question 2

Explain what is meant by concurrent programming

Answer 2

It is the process of interleaving (running one instruction of the sequential process) sets of sequential atomic instructions (must be correct under all possible intereleavings)

Question 3

Define a race condition.

Answer 3

A race condition occurs when a program output is dependent on the sequence or timing of code execution. The part that is at risk is the critical section (parts of the program where shared resources are accessed)(should never split), only one processor should execute at a time. This leads to undesireable or surprising results.

Question 4

What is a deterministic computation?

Answer 4

Computations that have the same result each time. This is better than indeterminate results. We need a mechanism to control access to shared resources in concurrent code (synchronisation is necessary for any shared data structure). We want critical sections to run with mutual exclusion (only one at a time).

Question 5

What are the 5 properties of a critical section?

Answer 5

Mutual exclusion (one program running at a time)
Guarantee of Progress (processes outside the critical section cannot stop another from entering it)
Bounded waiting (a process waiting to enter a critical section will eventually enter, and leave)
Performance (the overhead of entering/exiting should be small)
Fair (don’t make some processes wait longer than other).

Question 6

What 2 solutions are there to synchronisation?

Answer 6

Atomicity: atomic operations cannot be interrupted (it happens all at once), in order to avoid illogical outcomes. Basic atomicity is provided by the hardware.
Conditional Synchronisation: A mechanism that protects areas of the memory from being modified by two different thread at the same time.

Question 7

A lock is an example of a solution to Mutual exclusion, explain in detail what it is, how to use it, it’s benefits and it’s limitations.

Answer 7

A lock is a token you need to enter a critical section of code. If a process wants to execute a critical section, it needs the lock. The Lock has 2 states (Held or not held), as well as 2 operations (acquire and release).
The lock can be used as a variable. A program could have multiple locks. Some benefits of locks are: only 1 process can execute the critical section at a time, when a process is done another process can enter the critical section and it achieves mutual exclusion. Limitations of a lock are that processes can acquire other locks and you must use the same lock for all critical sections accessing the same data.

Question 8

What are the drawbacks to a spinlock?

Answer 8

Form of busy waiting (burning CPU time). Once acquired they are held until explicitly released (what about other processes?). It is inefficient if the lock is held for long periods.

Question 9

What is a spinlock?

Answer 9

A lock that causes a thread trying to acquire it to simply wait in a loop (“spin”) while repeatedly checking whether the lock is available.

Question 10

What is deadlock?

Answer 10

A situation in which processes block each other due to resource aquisition and none of the processes make any progress as they wait for the resource held by the other process.

Question 11

What protocols should be introduced to avoid a deadlock?

Answer 11

Adding a timer to request lock method.
Adding a new check (lock) method to see if a lock is already held before requesting it.
Avoiding hold and wait protocol.

Question 12

What is livelock?

Answer 12

A situation in which processes block each other with a repeated state change yet make no progress. Each process checks whether the other process is in an active state. If so, then it hands over the resource to the other process. However, both keep on handing over the resource to each other indefinitely.

Question 13

What is starvation?

Answer 13

Starvation is an outcome of a process that is unable to gain regular access to the shared resources it requires to complete a task and thus, unable to make any progress.

Question 14

What is a semaphore?

Answer 14

A type of generalised lock that has a higher level synchronisation primitive. It is implemented with a counter that is manipulated atomically via 2 operations: signal (increments counter) and wait (decrements counter).

Question 15

Why are semaphores used?

Answer 15

To enforce mutual exclusion, avoid race conditions and implement process synchronisation.

Question 16

What is a problem to do with semaphores?

Answer 16

Can produce buggy code that is hard to write. If a coder forgets to signal() after a critical

Question 17

How do you initialise a semaphore?

Answer 17

If a semaphore is initialised to 1
- First call to wait goes through (semaphore goes to 0)
- Second call to wait blocks (semaphore value stays at 0, process goes on queue)
-if first process calls signal (semaphore value stays at 0 and wakes up second process)
This acts like a mutex lock and is known as a binary semaphore.

Question 18

What are monitors?

Answer 18

An extension of the monolithic monitor used in OS to allocate memory. These keep track of which process is allowed to access the shared data and when they can do it.

Question 19

Name and briefly explain the 4 conditions that need to hold for a deadlock to occur.

Answer 19

1. Mutex: at least 1 held resource must be non-shareable.
2. No pre-emption: resources cannot be preempted (no way to break priority or take a resource away once allocated)
3. Hold and Wait: there exists a process holding a resource and waiting for another resource.
4. Circular Wait: there exists a set of processes P1,P2,… Pn. such that P1 is wating for P2, P2 is waiting for P3, … and Pn is waiting for P1.

Question 20

Name any 1 of the 3 ways to prevent a deadlock from occuring.

Answer 20

1. Ignore the fact that a deadlock may occur-
   Write code, sometimes you have to reboot the sytem. this may work for some unimportant or simple applications where deadlock does not occur often and is a quite common approach.
2. Reactive -
   Periodically check for evidence of deadlock (e.g add timeouts to acquiring a lock, if you timeout it implies deadlock has occured and you must fo something) Recovery actions- reboot computer/ pcik a process to terminate (e.g a low priority one), which only works with some types of applications and may corrupt data,.
3. Proactive-
   Prevent 1 of the 4 conditions for deadlock. No single approach is appropriate (or possible) for all circumstances.

Question 21

In the proactive approach to dealing with a deadlock, explain how one of the 4 conditions of a deadlock can be prevented.

Answer 21

1. Locks themselves cannot be preempted but in order to prevent a deadlock, we preempt resources e.g if process A is waiting for a resource held by process B, then take the resource from B and give it to A. The problem with this is that it only works for some resources, it’s not possible if a resource cannot be saved and restored and there is an overhead cost for “preempt” and “restore”.
2. Elimiate Circular Wait: We do this by imposing an ordering resources (must acquire the highest ranking resource first). This introduced the Lock Hierarchy. By doing this we have elimiated circular dependency, which also means that you will need to lock a resource for a longer period of time.