Week 4 - Synchronization

Question 1

Other types of synchronization

Answer 1

thread i sends a message to thread j:

recieve operation in thread j cannot complete until send operation in thread i is reached.

Send cannot complete until thread j reaches recieve.

Join Synchronization: between parent and child threads. completes operation in parent when child terminates.

Barrier Synchronization:
across a group of N processes. no thread completes its barrier operation until all N threads have reached their barrier operation.

Question 2

General Synchronization

Answer 2

consists in a particular thread having to wait until some condition is created by one or more other threads.

Question 3

Dijkstra’s semaphores

Answer 3

are one rather general mechanism for achieving different kinds of synchronization.

P(S) decrease semaphore, but not below zero
V(S) increase semaphore.

Question 4

Notification synchronization

Answer 4

compare with send/receive synchronization.

Question 5

Resources

Answer 5

Computer systems have many kinds of resources, that can only be accessed by one process or thread at a time.

example: physical devices like printers.

if two threads update a shared data structure can corrupt.

Question 6

Deadlocks

Answer 6

Resource deadlocks can occur when processes (or threads) need to acquire access to more than one exclusive resource (printer or scanner for e.g.)

Question 7

Deadlock

Answer 7

Deadlock is a situation where a process or a set of processes wait indefinitely for an event that can never occur.

Question 8

Deadlock Modelling

Answer 8

Resource deadlock can be modelled using a Resource Allocation Graph, which shows:

• Which processes are requesting which resources.
• Which resources have been granted to which processes.

If graph contains no cycles = no deadlock.

If graph contains a cycle = deadlock.

Question 9

Resource Allocation Graphs (Revise directed graphs. SLIDE 15,16,17)

Question 10

Deadlock Detection and Recovery

Answer 10

Allows system to enter deadlock state.

Runs Detection algorithm periodically to check.

Performs Recovery scheme if deadlock.

To detect deadlock, search for a cycles in the Resource Allocation Graph.

Question 11

Deadlock Detection
(Slide 20)

Question 12

Deadlock Recovery

Answer 12

Crudely - kill processes until the deadlock cycle is eliminated.

“Survivors” get the resources.

Commonly used in Relational Database Management Systems, where transactions identified as causing deadlock can be “rolled back”.

Question 13

Deadlock Avoidance

Answer 13

The idea here is to keep the system “safe” – avoid entering “unsafe” states which may later turn into a deadlock.

-classic deadlock scenario of two processes sharing resources

-Each process has its own “instruction counter”.

-If we plot these as two axes of a graph, behaviour of whole system is represented as a trajectory in this graph, moving upwards and to the right.

Question 14

Two Processes and One Resource (Slide 23, 24)

Question 15

Two Processes and Two Resource (Slide 25, 26)

Question 16

Unsafe Region (Slide 27,28)

Question 17

Banker’s Algorithm (Dijkstra,1965)

Answer 17

Basic idea:

Requires all processes to declare the max # of resource units that they may request.

Keeps track of current allocation for each process and their current “needs” (“max” – “has”).

When receives a request, “pretend” to honor the request, and

Try to fulfill the “needs” of all other processes in some order so as to check whether or not granting the request will lead to a safe state.

If safe, grant request; otherwise, deny request.