Process Synchronization--Part 4 (Peterson's Solution)

Till now, we have discussed the following posts on Process Synchronization. Before reading this post, please read the following post on Process Synchronization:-

• Part 1: The Critical Section Problem
• Part 2: Turn Variable Solution
• Part 3: Flag Array Solution

The solution to the 2-process synchronization problem discussed in the previous post did not satisfy progress as it could lead to a deadlock situation. In this post, we discuss Peterson's solution, which satisfies Mutual Exclusion, Progress and Bounded Waiting.

Analysis

• This solution uses both the turn variable and flag array approaches.
• There is a small change in the waiting loop condition as well compared to the previous solution.
• Let us consider process P0.
• First, it expresses interest to enter the critical section by setting flag[0] = true
• Then, it sets turn variable to 1.
• P0 enters the waiting loop and it will continue to wait only if turn is 1 AND flag[1] =1.
• We know that P0 had set turn to 1 in previous statement
• But it will wait in the loop only if flag[1] = 1 which means P0 will wait only if P1 had expressed interest to enter the critical section EARLIER than P0.
• So, in Peterson's Solution, the process which expresses interest earlier will get the chance to enter critical section earlier.

Mutual Exclusion

MUTUAL EXLCUSION HOLDS which we can prove by an argument similar to the one used for the previous solution.

Progress

The difference between Peterson's solution and the previous algorithm is that here, there is a turn variable which can hold either 0 or 1. It cannot hold both values at the same time. As the value of turn

is used in an AND (mandatory) condition in the waiting loop, at least 1 process will be able to proceed to its critical section, so there will be no deadlock. Combining this idea with the general proof of progress in the previous algorithm, we see that PROGRESS HOLDS.

Bounded Waiting

We find here that each process sets turn to the other process' desirable value. For example, P0 sets turn to 1 and P1 sets turn to 0. So, if P1 is interested to enter the critical section (if it has set flag[1] to true) and P0 is currently inside the critical section, P1 will be allowed to enter right after P0 exits and sets turn to 1. So, P1 will enter (if it wanted to !) before P0 enters again.So, BOUNDED WATING HOLDS.

So, we reach the end of the 2-process synchronization problem. In the next post, we will discuss a solution to the critical section problem when more than 2 processes are involved, using something called Semaphores. We will also see that Semaphores can be used for other applications as well.

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 5