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

Process Synchronization--Part 6 (Semaphores-1)

In this post, we will look at a software solution to the n-process synchronization problem, semaphores.

A semaphore is an integer variable which can be accessed only through 2 atomic operations:-

1. wait()
2. signal()

So, if S is a semaphore variable, the only operations and the only 2 ways to access S is:-

1. wait(S)
2. signal(S)

The wait and signal operations on a semaphore variable S can be defined as follows:-

We should note that these operations will be called by processes. Also, S is a shared variable. So, all the n processes may execute statements like wait(S) and signal(S). 

Let us assume that S has been initialized with 1. Now, if a process invokes wait(S), S will become 0. Now, if another process invokes wait(S), it will start waiting in the infinite loop. When some process invokes signal(S), S will become 1 again, only then can an interested process which was waiting in the loop, proceed with its code segment after wait(S). 

**wait(S) and signal(S) need not be executed by the same process. For example, if Process P0 executes wait(S) when S is initially 1, S becomes 0. Now, if process P1 executes wait(S), it starts waiting in the infinite loop. If P0 now executes signal(S), S becomes 1 and P1 can now make S=0 and proceed with its code. But this signal(S) could have been done by some process other than P0 as well. This is a very important point which we must remember. So, from the above definition, we find that S can have a minimum value of 0 and its maximum value depends on how many processes perform signal(S).

Let us say we want to solve the n-process critical section problem using semaphores. So, as we have read earlier, any solution to the critical section problem must ensure that only 1 process is allowed to execute its critical section at any point of time.

To solve the critical section problem with n processes, code structure of any process Pi looks like this:-

We should note that for a software solution to work properly, the code must be correct, this should be kept in mind. The above code works as follows:-

• Initially S should be 1. This, in fact, is known as a Binary Semaphore as it can hold only 2 values, 0 and 1.
• Each process invokes wait(S) before accessing the critical section.
• Each process invokes signal(S) after accessing the critical section.
• A process gets the chance to enter its critical section only if S = 1, which means no other process is inside its critical section, as otherwise S would have been 0.
• When a process exits its critical section, it invokes signal(S) to make S = 1 so that some other process can enter its critical section (which process gets a chance is a matter of Scheduling and we will come back to it after some time).
• Mutual Exclusion holds as a process can enter only if S = 1. Once it enters, S becomes 0 and now no other process can enter as S is not equal to 1.
• An inherent assumption made in the above claim is that S = S + 1 and S = S - 1 are atomic statements. Also, there is no interruption when while(S<=0); statement is false and S = S - 1 is executed.
• Progress holds in above code. It is obvious.
• Bounded waiting may not hold. When a process P0 is inside its critical section, it has performed wait(S) and set S to 0. Until P0 sets S to 1 by signal(S) [acc, to above code] all the processes invoking wait(S) in the meantime will be blocked on this semaphore the details of which will have to be stored somehow. Bounded Waiting will depend on the Scheduling policy which we will get back to after some time.

So far, we have seen the concept of Semaphores, the concept of wait() and signal() operations defined on semaphore variables and a solution to the n-process critical section problem using semaphores. Now, we will see the actual implementation of Semaphores.

Implementation of Semaphores

We have stated that semaphores are integer variables with 2 operations defined on them. We have also seen that information about the processes blocked on a semaphore has to be stored along with the integer value so that they can resume operation once a process invokes signal(S).

So, we can define a semaphore has a structure (in C) or class (in Java) which has an integer data component and a pointer variable to construct a Linked List which will hold the processes which are blocked (after having invoked wait(S) on this particular semaphore. A possible implementation has been shown below and I have taken this diagram from the Operating System Course Notes of Dr. John T.Bell, Dept. of Computer Science, University of Illinois, Chicago.

Each semaphore has an integer value and also a pointer to construct a linked list which will hold processes which have invoked wait(S) when some process is already inside its critical section by having invoked wait(S) and setting it to 0.

In this implementation, the minimum value of S is not bounded. As and when new processes block, S value gets more and more negative. The last blocked process gets over when S increases from -1 to 0. At this point, only 1 process is inside its critical section using this semaphore and no process is blocked on this semaphore. Next time, when the current working process invokes signal(S), S comes back to 1 and everything is fine!

Phew! It was a bit of a roller-coaster ride I am sure :P 

But there is a problem. The line *remove a process P from S->list does not state in which order the processes are to be removed from the blocked list of a semaphore. If LIFO policy is followed, definitely starvation will occur. In this case, Bounded Waiting may not hold as well.

Deadlock Problem with Semaphores

R and S are semaphores. If process A executes wait(S), pre-empts, then process B executes wait(R), now both processes are in deadlock as neither A nor B can proceed as both R and S semaphores are already 'occupied'. This is an important problem which can occur with semaphore code.

We have seen binary semaphores and their applications. In the next post, we will see 2 other applications of semaphores.