Process Synchronization-Part 3 (Flag Array 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

In the previous post, we discussed a solution to the 2-process synchronization problem which did not satisfy PROGRESS. Let us examine why the problem arose.

In the solution above, no process is being made to state explicitly that it is interested to enter its critical section. An inherent assumption is being made that both the processes will always be interested to enter their critical section but this might not be the case. In our next solution, we try to rectify this problem using a 2-element boolean flag array.

• flag[0] = 1 means Process P0 is interested to enter its critical section
• flag[0] = 0 means Process P0 is not interested to enter its critical section
• flag[1] = 1 means Process P1 is interested to enter its critical section
• flag[1] = 0 means Process P1 is not interested to enter its critical section

Analysis

• Before attempting to enter its critical section, each process sets its flag variable to true indicating that it is interested to enter its critical section.
• Each process than waits in a loop until the other process has its flag value to false. This means that a process will wait in the loop as long as the other process has set its flag value to true and has not yet set it to false, meaning that the other process is currently holding the pass to enter critical section.
• Let us say Process P1 has set its flag value to true which means it has executed the statement flag[1] = true;
• Now, it gets pre-empted and Process P0 enters the scene and sets flag[0] = true;
• Process P0 will then enter the waiting loop until Process P1 comes back, enters critical section, exits and sets flag[1] = false;
• So, in this solution, the process which sets its flag value to true earlier will get to enter its critical section earlier.

Mutual Exclusion

Suppose Process P0 is currently inside its critical section. This means it has set flag[0] to true. If Process P1 now attempts to enter its critical section, it will wait in the loop because flag[0] will be true as long as P0 is inside its critical section. So, mutual exclusion HOLDS.

Progress

We need to analyze a few things here.

• Let P0 be interested to enter its critical section while P1 is not yet in the scene.
• P0 sets flag[0] = true;
• while(flag[1]==true) is false so it exits waiting loop and enters critical section.
• P0 sets flag[0] to false;
• Now, let us say P0 wants to enter its critical section once again.
• P0 sets flag[0] = true;
• while(flag[1]==true) is false so it exits waiting loop and enters critical section.
• P0 sets flag[0] to false;

So, a non-interested process P1 has not blocked an interested process P0 from entering its critical section.

**Whenever I use the term 'enter its critical section', it means that a particular process is entering its own critical section. Note that a process can enter only its own critical section. A critical section of a process is a code segment of the process which accesses shared variables. A process is a program in execution. A program consists of lines of code. Ok! Enough :P

So, for now, we can think that this solution satisfies progress. But we must analyze another situation before concluding the same.

• Let P0 be interested to enter its critical section while P1 is not yet in the scene.
• P0 sets flag[0] = true;
• At this point somehow P0 gets pre-empted, P1 enters the scene and executes flag[1] = true;
• So, now, flag[0] and flag[1] are both true;
• Now, if P0 comes back and starts executing from where it left off, which means from the while(flag[1]==true); statement, it finds that flag[1] is true and it has to wait. If P0 gets pre-empted and P1 comes, P1 has to wait as well as flag[0] is also true. So, we have a DEADLOCK situation and so, PROGRESS is not satisfied by this solution.

Bounded Waiting

We know that the definition of bounded waiting says that there should be a finite bound on the number of times other processes are allowed to enter their critical sections after the said process has exhibited its interest to join the critical section and before it is granted the chance. Here, each process exhibits its interest by setting its flag to true. And, this should hold for all processes.

Let us suppose P1 has set its flag to true and has then pre-empted. Now, if P0 comes, executes its critical section, and exits after setting flag[0] to true, instantly P1 can be granted the chance as it can now come out of the waiting loop. So, bounded waiting HOLDS.

Conclusion

So, even now, we do not have a correct solution to the 2-process synchronization problem. In the next post, we will look at Peterson's Solution which makes a small modification to the algorithm described in this post, to provide a correct 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 4