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 2 (Turn Variable Solution)

Till now, we have covered the Introduction to Process Synchronization up to the Critical Section Problem. Before reading this post, please read the following post on Process Synchronization:-

• Part 1: The Critical Section Problem

In this post, we will see the 1st solution to the 2-process synchronization problem which uses a shared variable turn. We name the 2 processes P0 and P1.

Turn Variable Solution to 2-process Synchronization Problem

The solution code can be shown by the diagram below:-

Analysis

• turn is a shared boolean variable which can hold the value either 0 or 1
• Process P0 waits in an infinite loop until turn value is 0, only then can it enter the Critical Section
• When P0 exits Critical Section, it sets turn = 1 to enable Process P1 to enter the Critical Section
• The code is extremely symmetric and easy to understand. Please observe it with some time in hand.

We will now analyze the Turn Variable algorithm with respect to the 3 conditions in our previous post.

Mutual Exclusion

Let Process P0 be in its critical section. This means that turn = 0 at the moment. Until and unless P0 exits critical section and sets turn = 1, Process P1 cannot enter the critical section. The analysis is similar if we start with process P1. So, mutual exclusion HOLDS.

Progress

Let Process P0 be inside its critical section. It finishes its critical section and sets turn = 1. Now, let us assume P0 again wants to enter its critical section. It will not be able to, as long as Process P1 enters its critical section at least once and sets turn = 0 after exiting. So, if Process P1 is not interested to enter its critical section, in a way, it is blocking the entry of an interested process P0 to the critical section even though there is no process currently in its critical section. So, Progress DOES NOT HOLD.

BOUNDED WAITING

Here, we find that strict alternation exists. In other words, the only possible execution sequence is one process followed by the other. So, bounded waiting definitely HOLDS.

Conclusion

This is an incorrect solution to the 2-process synchronization problem as Progress does not hold. In the next post, we will analyze the exact reason why this problem is occurring and try to develop a better solution.

      Was it a nice read? Please subscribe to the blog by clicking on the 'Follow' button on the right hand side of this page. You can also subscribe by email by entering your email id in the box provided. In that case, you will be updated via email as and when new posts are published.Also, please like the Facebook Page for this blog at Gate Computer Science Ideas. Cheers!



Click here to read Part 3

Process Synchronization- Part 1 (The Critical Section Problem)

This topic is extremely important for GATE. Also, most of us find it confusing. In this series, we will try to cover the basic essentials required to solve GATE questions (trust me, not much depth in this topic is needed for GATE!). The topics will include the following:-

• Race Condition and The Critical Section Problem
• Solutions to the 2-process Synchronization Problem
• Hardware solutions including the Test, Set and Lock (TSL)
• Semaphores, Mutexes and the difference between them
• Applications of Semaphores
• A couple of classic synchronization problems 
• Very important previous GATE questions

Race Condition

Most of us are familiar with the notion of a process. A process can be thought of as a program in execution. In a uni-processing environment, only 1 process can be running at a time. Suppose there are 10 processes to be executed on a certain computer. Process 1 starts executing and in the midst of its execution, it requires some I/O time. So, during this time, if we keep the CPU idle, it will be a wastage and we will obtain reduced throughput. What we can do is, some other process can execute on CPU in the mean time. In this way, the CPU is always kept busy (that is the aim).

But this constant getting-in and throwing-out of processes from the CPU comes with a price. When there are so many processes executing with an effective idea of togetherness, consistency can be hard to achieve, especially when there are shared variables involved. Also, depending on order of execution of processes, the results obtained may be different. We will examine all these ideas.

Let us consider the famous Producer-Consumer problem to understand what a race condition is. While we do not need to analyze the exact code for this problem, we must understand intuitively what the problem is. In the Producer-Consumer problem, there are 2 processes, a Producer process and a Consumer process. Also, we have an array/buffer of items, let us consider the array to be infinite for now. 

To maintain the number of items available in the buffer/array, a shared variable count is needed. It is a shared variable because both the processes should be able to modify it. When the Producer process produces an item and places it on the buffer, it should increment by 1 (execute the statement count++). When the Consumer process takes up an item from the buffer, it should decrement count by 1 (execute the statement count--).

But count++ and count-- are not atomic statements at the Assembly Language Level. In other words, these statements are individually executed as a series of 3 atomic statements shown below:-

Let initial value of count be 18. We have numbered the statements from 1 to 6 for ease of analysis. Note that atomic statements can be individually in any order, which means that after execution of statement 1, the Producer process may be pre-empted while the Consumer process executes statement 4. So, (1,2,3,4,5,6) is a possible execution sequence. Also, (1,4,2,5,3,6) is another possible execution sequence.

When the sequence (1,2,3,4,5,6) occurs, the following happens:-

• reg1 = 18
• reg1 = 18+1 = 19
• count = 19
• reg2 = 19
• reg2 = 19-1 =18
• count = 18           (final value of count is 18-->correct)

So we find that the desired result is obtained. Now, let us see what happens when the sequence (1,2,4,5,3,6) occurs:-

• reg1 = 18
• reg2 = 18
• reg1 = 18+1 = 19
• reg2 = 18-1 = 17
• count = reg1 = 19
• count = reg2 = 17  (final value of count is 17--> incorrect)

If we interchange the final 2 statements in the above sequence so that (1,2,4,5,6,3) occurs, the following happens:-

• reg1 = 18
• reg2 = 18
• reg1 = 18+1 = 19
• reg2 = 18-1 = 17
• count = reg2 = 17
• count = reg1 = 19       (final value of count is 17--> incorrect)

So, in both the above cases, the final value of count is inconsistent and undesired. Depending on which process executes last, the final value of count is changing. This is called a race condition.

Race condition is a situation where several processes access and manipulate shared data concurrently. The final value of the shared data depends on the process which finishes last. Concurrent processes must be synchronized to prevent race conditions.

The Critical Section Problem

Suppose there are n processes, each having a particular section of code where it accesses shared variables. So, each process has a code segment where it accesses shared data which is called the critical section. We must ensure that when 1 process is executing in its critical section, no other process must be allowed to execute in its critical section.

The general code structure of process i can be shown by the diagram below:-

The entry section is usually used to obtain locks on shared variables and permission to access the Critical Section. 

The exit section is usually used to release locks on shared variables so that other processes can access their critical sections.

The remainder section is a code segment not related to the critical section.

The code is shown in a do-while loop with the assumption that a process will end when it executes some code in its remainder section which causes it to terminate.

Critical Section Problem Solution Requirements

Any solution to a critical section problem must satisfy the following 2 conditions mandatorily:-

• Mutual Exclusion: When a process i is executing in its critical section, no other process should be allowed to enter its critical section.
  
• Progress: If no process is in its critical section and we have some process which is interested to enter its critical section, only those processes not in their remainder section should be allowed to participate in the decision of which process will get the chance to enter the critical section next. In other words, only those processes which are interested to enter the critical section should be able to influence which process gets the chance to enter the critical section. A non-interested process should not be able to block an interested process from entering the critical section.

**Note: If there is INFINITE WAITING TIME TO MAKE ABOVE DECISION (which also includes the notion of DEADLOCK)  to make above decision, that means there is NO PROGRESS. This particular point is very important for GATE.

A solution to the critical section problem should ideally satisfy another condition known as Bounded Waiting the definition of which is not the same across textbooks. We can think of bounded waiting as the assurance implicit to the process that there will be a bound (finite upper limit even if it is a very high number) on the number of times other processes are allowed to enter the critical section after that process has requested to enter the critical section and before that request is granted.

In this post, we have seen up to the Critical Section Problem. In the next post, we will see various solutions to the 2-process Synchronization problem where we have only 2 processes.

Click here to read Part 2

Was it a nice read? Please subscribe to the blog by clicking on the 'Follow' button on the right hand side of this page. You can also subscribe by email by entering your email id in the box provided. In that case, you will be updated via email as and when new posts are published.Also, please like the Facebook Page for this blog at Gate Computer Science Ideas. Cheers!