Process Synchronisation & Concurrency

Question 1

Processes or threads: three basic interactions

Answer 1

• Unaware of each other – They must use shared resources independently,
  without interfering and leave them intact for others.
• Directly aware of each other – They cooperate by communicating, e.g.
  exchanging messages
• Indirectly aware of each other – They work on common data and build
  some result together via the data (“stigmergy” in biology).

Question 2

What is a Race Condition?

Answer 2

A situation – when multiple processes read and write data such that
the final result depends on the order of execution of the instructions – is known as a race condition
* Generally, problematic race conditions may occur whenever
resources and/or data are shared
* By processes/threads unaware/indirectly aware of each other
* Synchronisation of processes – aim to guards against race conditions
occurring

Question 3

The Critical Section Problem—the Protocol to allow multiple processes to cooperate. What conditions must be met?

Answer 3

1.Mutual Exclusion – If a process is executing its critical section,
no other processes are allowed to execute their critical section

2. Progress - If no process is in the critical section, others should
   not be indefinitely prevented from entering.
3. Bounded Waiting – Must not be possible for a process wishing to
   enter its critical section to be indefinitely blocked (deadlock and
   starvation – future weeks lecture)

Question 4

Critical Section Potential Solution’s 5 points

Answer 4

1. Disabling hardware interrupts
2. Simple lock variable (unprotected)
3. Indivisible lock variable (TSL)
4. no-TSL toggle for two threads
5. Peterson’s no-TSL, no alternation

Question 5

What are Semaphores?

Answer 5

A semaphore is a low-level synchronisation primitive used to
control access.

Question 6

What do Semaphores do?

Answer 6

Special integer variable with only three possible operations:
1. Initialisation (to a non-negative number)
* And accessed via two atomic operations
2. Wait – which decrements the value
* If the value becomes negative, the process calling it becomes blocked
3. Signal – which increments the value
* If the value becomes positive, a process which has previously been blocked by this
semaphore becomes unblocked

Question 7

Interesting properties of semaphores 3 points

Answer 7

• No way of knowing if a process will block when it calls wait
• After a process calls signal, if this wakes up another process, no way of knowing which will run
• When a process calls signal, no way of knowing whether this unblocks another process

Question 8

What monitors?

Answer 8

• A monitor is a higher-level synchronisation construct that
  combines mutual exclusion and condition variables.
• Monitors encapsulate data structures that are not externally
  accessible

Question 9

How do Monitors work?

Answer 9

A thread enters the monitor by calling one of its methods.
* If another thread is already executing a method, the new thread
is blocked and added to a waiting queue.
* Once the current thread exits the monitor, the next thread in the queue is
unblocked and allowed to proceed.

Question 10

Readers-Writers Problem

Answer 10

1. Any number of readers may simultaneously read the file
2. Only one writer at a time may write to the file
3. If a writer is writing to the file – no reader may read it

Question 11

Dining Philosophers Problem

Answer 11

• Five philosophers round the
  table
• Each has a plate and a fork * To eat – requires two forks * Effective resource sharing
  without leading to deadlock,
  starvation or livelock

Question 12

Dining Philosophers Problem Solution

Answer 12

• Allow at most 4 philosophers (N-1) to
  be sitting simultaneously at the table.
• Allow a philosopher to pick up the forks
  only if both are available (picking must
  be done in a critical section).
• Use an asymmetric solution – an odd
• numbered philosopher picks up first
  the left chopstick and then the right
  chopstick. Even-numbered philosopher picks up first the right
  chopstick and then the left chopstick.

Question 13

Single Lane Bridge

Answer 13

• A bridge over a river is only wide enough to permit a single lane of traffic
• Consequently, cars can only move concurrently if they are moving in the same direction
• A safety violation occurs if two cars moving in different directions enter the bridge at the same time
• Challenges Resource contention and Efficiency

Question 14

Single Lane Bridge – Key Challenges

Answer 14

• Deadlock:
• Without proper synchronisation, cars from both directions might block each other indefinitely.
• Avoid this by ensuring only one direction can access the bridge at a time.
• Starvation:
• Favouring one direction too much can starve the other side. Introduce fairness mechanisms like alternating access or prioritizing the longer queue.
• Efficiency:
• Minimize waiting time and ensure
  the bridge