Process Synchronization: Question 2 (2017)

Solution

Here, we are given that all locks are non-reentrant, meaning that if a thread holds a lock A, it has to release lock A before it can acquire lock A again. If a thread tries to acquire a lock when it is not available, the thread blocks.

We are asked to mind the minimum value of x and y such that deadlock may occur. Here x denotes the number of threads and y denotes the number of locks used by the multi-threaded program P. In this problem, we have to think of scenarios in the program code through which deadlock may occur. Let us start from the minimum possible combination x=1 and y=1 (option D). Starting from this option helps us in a way. If we find a situation with x=1 and y=1 such that deadlock occurs, we need not check the other 3 options. We can immediately claim that option D is our answer.

If the program P executes with only 1 thread T and 1 lock A, let's see what can happen. Using the property of non-reentrant locks as given in the problem, we find that if the thread T tries to acquire lock A twice without releasing lock A in between, deadlock will occur as T will block. So, option D is the right answer.

Answer: Option D

Process Synchronization: Question 1 (2018)

Solutions to these questions are available on multiple websites across the Internet but during the examination, it is necessary to solve the questions in very quick time. Most questions on this topic are actually easy and can be solved quickly. In this series of posts, I will try to show how I would have solved the question during the exam (or how I solved it while practising).

Solution

We have to find a suitable combination of P, Q, R and S so that this is a solution to the Producer-Consumer problem. In the Producer-Consumer problem, we have a shared buffer (shared between Producer and Consumer). The Producer produces an item and places it in the buffer. At this point, buffer size reduces by 1. The consumer retrieves the item from the buffer. At this point, the buffer size increases by 1.

So, after producing an item, the producer should indicate so. How? It can invoke signal() on a semaphore indicating the number of items currently in the buffer. The value of this semaphore will increase by 1, indicating that the number of items in the buffer has increased by 1. Initially, the semaphore empty is 0, indicating that the buffer is currently empty. So, Q has to be signal(empty). So, the answer can be only between options B and C.

Let us consider option B. Here, Producer process deals with semaphore empty and Consumer process deals with semaphore full. There is no sharing. Clearly, this cannot be the answer. Option C is the solution. The semaphore full basically denotes the number of vacant spaces in the buffer. Initially, full has value N. When producer process wishes to create an item, it calls wait(full) and full reduces by 1. It then calls signal(empty) to indicate that the number of occupants in the buffer has now increased by 1.

The solution might seem long, but during the exam, collecting these thoughts together will not take more than 1 minute.

Answer: Option C

Click here to visit Question 2