{"id":95,"date":"2018-07-19T06:26:00","date_gmt":"2018-07-19T06:26:00","guid":{"rendered":"http:\/\/csp3.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=95"},"modified":"2018-08-07T05:18:29","modified_gmt":"2018-08-07T05:18:29","slug":"process-synchronization-solutions-i","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/chapter\/process-synchronization-solutions-i\/","title":{"rendered":"Process Synchronization \u2013 Solutions I"},"content":{"raw":"
\r\n\r\n \r\n

11.1\u00a0 Introduction<\/strong><\/p>\r\n \r\n

When two or more concurrent processes communicate among themselves, they share data when they access common variables and data structures. Hence, there is a need for\u00a0<\/span>synchronization between the processes. The portion of code in each of the processes where\u00a0<\/span>they access the common data structures or variables is called their respective critical sections of code. If there is no proper synchronization between the processes when they access their critical sections of code, inconsistency of data may result. Hence, any solution to the critical section problem should satisfy the mutual exclusion, progress and bounded waiting conditions. In the previous module (Module 10), we learnt a solution to the critical section problem, which provided a solution when only two processes were involved. This module is a continuation of the previous module and describes different other solutions to the critical-section problem and explains how the solutions satisfy mutual exclusion, progress and bounded waiting requirements.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n11.2\u00a0 Solution 2<\/strong>\r\n\r\n \r\n

In the solution to the critical section problem that we learnt in the previous module, we learnt a solution when only two processes were involved. That solution made use of a variable called \u2018turn<\/em>\u2019 to provide synchronization. But that solution satisfied only the mutual exclusion requirement.<\/p>\r\n \r\n

In this second solution, a Boolean array called \u2018flag<\/em>\u2019 is used to provide synchronization. This is also a solution when only two processes are involved. The solution is given below:<\/p>\r\n \r\n\r\nShared variables<\/strong>\r\n

boolean flag[2];\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/* initially flag [0] = flag [1] = false*\/<\/strong><\/p>\r\n

flag [i] = true\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/* P<\/em><\/strong>i <\/strong>ready to enter its critical section*\/<\/strong><\/p>\r\n \r\n\r\nProcess\u00a0<\/span>P<\/em>i:<\/span><\/strong>\r\n\r\ndo {<\/span>\r\n

flag[i] := true; <\/span><\/p>\r\n

while (flag[j]) ;<\/span><\/p>\r\n,<\/span>\r\n

critical section <\/span><\/p>\r\n

flag [i] = false;<\/span><\/p>\r\n

remainder section<\/span><\/p>\r\n

} while (1);<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

Here, the array flag <\/em>is common to both the processes which use this algorithm to solve the critical section problem. The array has two elements flag[0] and flag[1]. Initially, both of the\u00a0elements are initialized to false.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

Suppose P<\/em>i and P<\/em>j are the two processes that want to synchronize. If process (P<\/em>i) wants to enter the critical section, P<\/em>i sets the value of flag[i] to true. P<\/em>i then checks if flag[j] is true or false. If the other process, P<\/em>j is currently in its critical section, flag[j] is true. As long as P<\/em>j is in its critical section, P<\/em>i is stuck in the while loop. When P<\/em>j comes out of its critical section, flag[j] is made false. P<\/em>i, which is now executing while (flag[j]); <\/em>comes out of the while loop and enters its critical section. After executing the critical section and after coming out of the critical section, process P<\/em>i executes the exit section. In the exit section, P<\/em>i changes back the value of flag[i] to false (flag[i] was changed to true by P<\/em>i in its entry section).<\/p>\r\n \r\n

We now see whether all the three conditions\u2014mutual exclusion, progress and bounded waiting\u2014are satisfied by this algorithm. Let P<\/em>0 and P<\/em>1 be the two processes that are to be synchronized. To show that the algorithm in solution 2 satisfies mutual exclusion, one possible sequence of execution of the two processes is given below:<\/p>\r\n \r\n\r\nAlgorithm 2 \u2013 Mutual Exclusion\r\n\r\n<\/div>\r\n

\r\n

\"\"<\/p>\r\nAccording to the mutual exclusion requirement, when process P<\/em>0 is in its critical section, process P<\/em>1 should wait and vice versa.\r\n\r\n \r\n

Here, initially, both flag[0] and flag[1] are false. When process P<\/em>0 \u00a0wants to enter its critical section, P<\/em>0 changes flag[0] to true. P<\/em>0 then checks the value of flag[1]. Since P<\/em>1 is still not competing to enter the critical section, flag[1] is false. Since the value of flag[1] is false, in process P<\/em>0, the condition inside the while loop becomes false (while(flag[1])) and process P<\/em>0 comes out of the while loop. P<\/em>0 now enters its critical section. Now, when P<\/em>0 is in the critical section, if P<\/em>1 wants to enter its critical section, P<\/em>1 changes the value of flag[1] to true and checks the value of flag[0] inside the while loop. Since the value of flag[0] is true, the condition inside the while loop remains true. Therefore, P<\/em>1 continues to execute inside the while loop. When P<\/em>0 comes out of its critical section, P<\/em>0 changes the value of flag[0] to false. That is, process P<\/em>1 waits till process P<\/em>0 comes out of its critical section. Thus, it is seen that, when process P<\/em>0 is in its critical section, process P<\/em>1 is not allowed to enter its critical section. Therefore, mutual exclusion is satisfied.<\/p>\r\n \r\n\r\nLet us see how the algorithm satisfies the progress requirement.\r\n\r\n \r\n\r\nAlgorithm 2\u2013Progress<\/span>\r\n\r\n<\/div>\r\n

\r\n

\"\"<\/p>\r\nProgress is not satisfied\r\n\r\n \r\n

According to the progress requirement, when two processes are competing to enter the critical section, the decision as to which process will enter the critical section first, should not be postponed indefinitely. In the example shown above, both the processes P<\/em>0 and P<\/em>1 want to enter the critical section at the same time. P<\/em>0 sets the value of flag[0] to true. Suppose, there is a context switch, P<\/em>1 is assigned the CPU and P<\/em>1 also sets the value of flag[1] to true. Now both the processes continue to wait in their respective while <\/em>loops. Both the processes are unable to proceed further. Thus, the progress requirement is not satisfied.<\/p>\r\n \r\n

We will now see another solution to the critical section problem. This solution combines the features used in solutions 1 and 2 to provide a solution to the critical section problem.<\/p>\r\n \r\n\r\n11.3\u00a0 Solution 3\u00a0<\/strong>\r\n\r\n \r\n

Similar to the previous two solutions, this is also a solution when only two processes compete to execute their respective critical sections of code. This solution makes use of the variable turn <\/em>and the flag <\/em>array used in solution 1 and solution 2 respectively. The solution is given below:<\/p>\r\n\"\"\r\n

In this solution, a variable turn and a Boolean array flag are used to provide a solution to\u00a0<\/span>the critical section problem. Let <\/span>P<\/em>i and <\/span>P<\/em>j be the two processes competing to enter the critical section. Initially, the values of flag[i] and flag [j] are set to false. The initial value of turn can be either i or j. If process <\/span>P<\/em>i wants to enter its critical section, <\/span>P<\/em>i sets the value of flag[i] to true and changes the value of turn to j. Now <\/span>P<\/em>i checks if the value of flag[j] is true and the value of turn is\u00a0<\/span>j. If process <\/span>P<\/em>j is not competing to enter the critical section and hence is not yet in the entry section, the value of flag[j] would not have been modified. It would still remain as false. Since flag[j] is false, the condition in the while loop for process <\/span>P<\/em>i (flag[j] && turn) becomes false and process <\/span>P<\/em>i enters the critical section.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

Now, when process P<\/em>i is in its critical section, let us see what happens if P<\/em>j wants to enter its critical section. P<\/em>j sets flag[j] to true and changes turn to i. P<\/em>j checks the condition in the while loop (flag [i] && turn == i). Since flag[i] is true and turn is equal to i, P<\/em>j waits in the while loop. P<\/em>j continues to wait in the while loop as long as P<\/em>i is in its critical section. When P<\/em>i comes out of its critical section, P<\/em>i changes the value of flag[i] to false in its exit section. When flag[i] becomes false, the condition (flag [i] && turn == i) in the while loop becomes false for process\u00a0P<\/em>j. Hence, P<\/em>j comes out of the while loop and enters its critical section.<\/p>\r\n \r\n

We now see whether all the three conditions\u2014mutual exclusion, progress and bounded waiting\u2014are satisfied by this algorithm. Let P<\/em>0 and P<\/em>1 be the two processes that are competing to enter the critical section.<\/p>\r\n\"\"\r\n

The above scenario shows how mutual exclusion is satisfied. Initially, flag[0] and flag[1] are false. Let the value of turn be 0. If process <\/span>P<\/em>0 wants to enter its critical section, it changes the value of flag[0] to true and the value of turn to 1. Process <\/span>P<\/em>1 is not yet competing to enter its critical section. <\/span>P<\/em>0 checks the value of flag[1] and the value of turn in the while loop. As flag[1] is false and turn = 1, the condition (flag[1] && turn==j) becomes false. That is, even though the value of turn==j is true (here, j=1, since <\/span>P<\/em>0 is executing), the value of flag[1] is false. Therefore, the process <\/span>P<\/em>0 comes out of the while loop and enters its critical section.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

When P<\/em>0 is in the critical section, let P<\/em>1 want to enter its critical section. P<\/em>1 changes flag[1] to true and changes turn to 0. In the condition inside the while loop, P<\/em>1 checks (flag[0] && turn=0). Since flag[0] is true and turn is 0, both the checks are true and the condition remains true. P<\/em>1 continues to wait in the while loop. When P<\/em>0 comes out of critical section, it changes flag[0] to false. Now the condition (flag[0] && turn=0), which is being checked by P<\/em>1 becomes false. P<\/em>1 now enters its critical section.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

Thus it is seen that when P<\/em>0 is in its critical section, P<\/em>1 is not allowed to enter its critical section. P<\/em>1 is allowed to enter its critical section only after P<\/em>0 comes out of its critical section. Thus, mutual exclusion is satisfied.<\/p>\r\n \r\n\r\nWe now look at another scenario to understand that the algorithm satisfies mutual exclusion.\r\n\r\n \r\n\r\nAlgorithm 3 \u2013 Mutual Exclusion<\/strong>\r\n\r\n \r\n\r\nScenario 2:<\/strong>\r\n\r\n<\/div>\r\n

\r\n

\"\"<\/p>\r\n

In this scenario, initially, both flag[0] and flag[1] are false. Process <\/span>P<\/em>0 wants to enter its critical section, changes flag[0] to true and turn to 1. Immediately, there is a context switch and <\/span>P<\/em>1 starts executing. <\/span>P<\/em>1 changes flag[0] to true and changes turn to 0. Now, the value of flag[0] and flag[1] are true. The value of turn now decides the process that can enter its critical section. When <\/span>P<\/em>1 checks the condition in its while loop (flag[0] && turn==0), both flag[0] and turn==0 are true. <\/span>P<\/em>1 waits in the while loop. When <\/span>P<\/em>0 checks its while loop (flag[1] && turn==1), the condition flag[1] is true, but the condition turn==1 is false. Therefore, <\/span>P<\/em>0 comes out of the while loop and enters its critical section. When <\/span>P<\/em>0 comes out of its critical section, it changes the value of flag[0] to false and then <\/span>P<\/em>1 can enter its critical section. Thus, it is seen that only one process is allowed to enter its critical section at a particular time and hence, mutual exclusion is satisfied.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nAlgorithm 3 \u2013 Progress<\/strong>\r\n\r\n \r\n\r\nLet us now see how progress is satisfied using the sequence shown below:\r\n\r\n<\/div>\r\n

\"\"<\/p>\r\n

In the scenario explained above, initially, both flag[0] and flag[1] are false. Process <\/span>P<\/em>0 wants to enter its critical section and changes flag[0] to true. Immediately, there is a context switch and <\/span>P<\/em>1 starts executing. <\/span>P<\/em>1 changes flag[1] to true. Again, there is a context switch and <\/span>P<\/em>0 changes turn to 1. There is a context switch again and <\/span>P<\/em>1 changes turn to 0. Now, the values of flag[0] and flag[1] are true. Still, based on the value of turn, one of the two processes can enter the critical section. In algorithm 2, we saw that progress is not satisfied when both the processes set the value of flag[0] and flag[1] to true at the same time. Thus, in this algorithm, the decision as to which process can enter the critical section is not postponed indefinitely. Hence, the progress requirement is satisfied.<\/span><\/p>\r\n\r\n

\r\n\r\n \r\n\r\nAlgorithm 3 \u2013 Progress<\/strong>\r\n\r\n \r\n\r\nAnother scenario to explain progress is given below:\r\n\r\n \r\n\r\nScenario 2:\r\n\r\n\"\"\r\n

In the scenario shown above, both P<\/em>0 and P<\/em>1 want to enter their respective critical sections. Initially, flag0] and flag[1] are false and turn is 0. flag[0] is changed to true by P<\/em>0 and flag[1] is changed to true by P<\/em>1. P<\/em>1 changes turn to 0. Then, P<\/em>0 changes turn to 1. In the while loop of P<\/em>0, flag[1] is true and turn is equal to 1. Since both the conditions are true, the condition checked in the while loop is true. Therefore, P<\/em>0 continues to wait in the while loop. In the while loop of P<\/em>1, flag[0] is true, but the value of turn is not equal to 0. Since one of the conditions is not true, the condition checked in the while loop is false and P<\/em>1 comes out of the while loop. P<\/em>1 enters its critical section. Thus, it is seen that the value of turn decides which process enters the critical section. The value of turn is based on which process sets the value of turn finally.<\/p>\r\n \r\n\r\nAlgorithm 3 \u2013 Bounded Waiting\u00a0<\/strong>\r\n\r\n \r\n

For the bounded waiting requirement, after a process has requested to enter its critical section, the amount of time the process waits should be limited. We will now see how the algorithm satisfies bounded waiting.<\/p>\r\n\r\n<\/div>\r\n

\"\"<\/p>\r\n

To understand that bounded waiting is satisfied, P<\/em>0 first requests to enter its critical section and then, P<\/em>1 tries to enter its critical section twice. We need to understand that after P<\/em>0 requests to enter its critical section, P<\/em>1 is not allowed to enter its critical section more than once.<\/p>\r\n \r\n

Initially, flag[0] and flag[1] are false. Let the value of turn be 0 initially. P<\/em>0 changes the value of flag[0] to true. Then there is a context switch and P<\/em>1 changes flag[1] to true. P<\/em>1 changes turn to 0. Now, again there is a context switch and P<\/em>0 changes the value of turn to 1. P<\/em>0 waits in the while loop. P<\/em>1 can now enter its critical section. P<\/em>1 comes out of its critical section and changes the value of flag[1] to false. Suppose P<\/em>1 continues to use the CPU and wants to enter its critical section again. P<\/em>1 changes the value of flag[1] to true and the value of turn to 0. Now, P<\/em>1 cannot enter its critical section unless P<\/em>0 enters its critical section, comes out and changes the value of flag[0] to true. P<\/em>1 is not allowed to enter critical section twice after P<\/em>0 had requested to enter critical section. Thus, bounded waiting requirement is satisfied.<\/p>\r\n \r\n

5.3\u00a0 Summary<\/strong><\/p>\r\n \r\n

This module discussed two solutions to the critical section problem. But both of these solutions work when there are only two processes. The first solution discussed in this module satisfies the mutual exclusion requirement but does not satisfy the progress requirement. The second solution discussed in this module satisfies all the three requirements.<\/p>\r\n \r\n

References<\/strong><\/p>\r\n\r\n

    \r\n \t
  1. Abraham Silberschatz, Peter B. Galvin, Greg Gagne, \u201cOperating System Concepts\u201d, Ninth Edition, John Wiley & Sons Inc., 2012.<\/li>\r\n \t
  2. William Stallings, \u201cOperating Systems: Internals and Design Principles\u201d, Seventh Edition, Pearson, 2012.<\/li>\r\n<\/ol>","rendered":"
    \n

     <\/p>\n

    11.1\u00a0 Introduction<\/strong><\/p>\n

     <\/p>\n

    When two or more concurrent processes communicate among themselves, they share data when they access common variables and data structures. Hence, there is a need for\u00a0<\/span>synchronization between the processes. The portion of code in each of the processes where\u00a0<\/span>they access the common data structures or variables is called their respective critical sections of code. If there is no proper synchronization between the processes when they access their critical sections of code, inconsistency of data may result. Hence, any solution to the critical section problem should satisfy the mutual exclusion, progress and bounded waiting conditions. In the previous module (Module 10), we learnt a solution to the critical section problem, which provided a solution when only two processes were involved. This module is a continuation of the previous module and describes different other solutions to the critical-section problem and explains how the solutions satisfy mutual exclusion, progress and bounded waiting requirements.<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    11.2\u00a0 Solution 2<\/strong><\/p>\n

     <\/p>\n

    In the solution to the critical section problem that we learnt in the previous module, we learnt a solution when only two processes were involved. That solution made use of a variable called \u2018turn<\/em>\u2019 to provide synchronization. But that solution satisfied only the mutual exclusion requirement.<\/p>\n

     <\/p>\n

    In this second solution, a Boolean array called \u2018flag<\/em>\u2019 is used to provide synchronization. This is also a solution when only two processes are involved. The solution is given below:<\/p>\n

     <\/p>\n

    Shared variables<\/strong><\/p>\n

    boolean flag[2];\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/* initially flag [0] = flag [1] = false*\/<\/strong><\/p>\n

    flag [i] = true\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/* P<\/em><\/strong>i <\/strong>ready to enter its critical section*\/<\/strong><\/p>\n

     <\/p>\n

    Process\u00a0<\/span>P<\/em>i:<\/span><\/strong><\/p>\n

    do {<\/span><\/p>\n

    flag[i] := true; <\/span><\/p>\n

    while (flag[j]) ;<\/span><\/p>\n

    ,<\/span><\/p>\n

    critical section <\/span><\/p>\n

    flag [i] = false;<\/span><\/p>\n

    remainder section<\/span><\/p>\n

    } while (1);<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    Here, the array flag <\/em>is common to both the processes which use this algorithm to solve the critical section problem. The array has two elements flag[0] and flag[1]. Initially, both of the\u00a0elements are initialized to false.<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    Suppose P<\/em>i and P<\/em>j are the two processes that want to synchronize. If process (P<\/em>i) wants to enter the critical section, P<\/em>i sets the value of flag[i] to true. P<\/em>i then checks if flag[j] is true or false. If the other process, P<\/em>j is currently in its critical section, flag[j] is true. As long as P<\/em>j is in its critical section, P<\/em>i is stuck in the while loop. When P<\/em>j comes out of its critical section, flag[j] is made false. P<\/em>i, which is now executing while (flag[j]); <\/em>comes out of the while loop and enters its critical section. After executing the critical section and after coming out of the critical section, process P<\/em>i executes the exit section. In the exit section, P<\/em>i changes back the value of flag[i] to false (flag[i] was changed to true by P<\/em>i in its entry section).<\/p>\n

     <\/p>\n

    We now see whether all the three conditions\u2014mutual exclusion, progress and bounded waiting\u2014are satisfied by this algorithm. Let P<\/em>0 and P<\/em>1 be the two processes that are to be synchronized. To show that the algorithm in solution 2 satisfies mutual exclusion, one possible sequence of execution of the two processes is given below:<\/p>\n

     <\/p>\n

    Algorithm 2 \u2013 Mutual Exclusion<\/p>\n<\/div>\n

    \n

    \"\"<\/p>\n

    According to the mutual exclusion requirement, when process P<\/em>0 is in its critical section, process P<\/em>1 should wait and vice versa.<\/p>\n

     <\/p>\n

    Here, initially, both flag[0] and flag[1] are false. When process P<\/em>0 \u00a0wants to enter its critical section, P<\/em>0 changes flag[0] to true. P<\/em>0 then checks the value of flag[1]. Since P<\/em>1 is still not competing to enter the critical section, flag[1] is false. Since the value of flag[1] is false, in process P<\/em>0, the condition inside the while loop becomes false (while(flag[1])) and process P<\/em>0 comes out of the while loop. P<\/em>0 now enters its critical section. Now, when P<\/em>0 is in the critical section, if P<\/em>1 wants to enter its critical section, P<\/em>1 changes the value of flag[1] to true and checks the value of flag[0] inside the while loop. Since the value of flag[0] is true, the condition inside the while loop remains true. Therefore, P<\/em>1 continues to execute inside the while loop. When P<\/em>0 comes out of its critical section, P<\/em>0 changes the value of flag[0] to false. That is, process P<\/em>1 waits till process P<\/em>0 comes out of its critical section. Thus, it is seen that, when process P<\/em>0 is in its critical section, process P<\/em>1 is not allowed to enter its critical section. Therefore, mutual exclusion is satisfied.<\/p>\n

     <\/p>\n

    Let us see how the algorithm satisfies the progress requirement.<\/p>\n

     <\/p>\n

    Algorithm 2\u2013Progress<\/span><\/p>\n<\/div>\n

    \n

    \"\"<\/p>\n

    Progress is not satisfied<\/p>\n

     <\/p>\n

    According to the progress requirement, when two processes are competing to enter the critical section, the decision as to which process will enter the critical section first, should not be postponed indefinitely. In the example shown above, both the processes P<\/em>0 and P<\/em>1 want to enter the critical section at the same time. P<\/em>0 sets the value of flag[0] to true. Suppose, there is a context switch, P<\/em>1 is assigned the CPU and P<\/em>1 also sets the value of flag[1] to true. Now both the processes continue to wait in their respective while <\/em>loops. Both the processes are unable to proceed further. Thus, the progress requirement is not satisfied.<\/p>\n

     <\/p>\n

    We will now see another solution to the critical section problem. This solution combines the features used in solutions 1 and 2 to provide a solution to the critical section problem.<\/p>\n

     <\/p>\n

    11.3\u00a0 Solution 3\u00a0<\/strong><\/p>\n

     <\/p>\n

    Similar to the previous two solutions, this is also a solution when only two processes compete to execute their respective critical sections of code. This solution makes use of the variable turn <\/em>and the flag <\/em>array used in solution 1 and solution 2 respectively. The solution is given below:<\/p>\n

    \"\"<\/p>\n

    In this solution, a variable turn and a Boolean array flag are used to provide a solution to\u00a0<\/span>the critical section problem. Let <\/span>P<\/em>i and <\/span>P<\/em>j be the two processes competing to enter the critical section. Initially, the values of flag[i] and flag [j] are set to false. The initial value of turn can be either i or j. If process <\/span>P<\/em>i wants to enter its critical section, <\/span>P<\/em>i sets the value of flag[i] to true and changes the value of turn to j. Now <\/span>P<\/em>i checks if the value of flag[j] is true and the value of turn is\u00a0<\/span>j. If process <\/span>P<\/em>j is not competing to enter the critical section and hence is not yet in the entry section, the value of flag[j] would not have been modified. It would still remain as false. Since flag[j] is false, the condition in the while loop for process <\/span>P<\/em>i (flag[j] && turn) becomes false and process <\/span>P<\/em>i enters the critical section.<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    Now, when process P<\/em>i is in its critical section, let us see what happens if P<\/em>j wants to enter its critical section. P<\/em>j sets flag[j] to true and changes turn to i. P<\/em>j checks the condition in the while loop (flag [i] && turn == i). Since flag[i] is true and turn is equal to i, P<\/em>j waits in the while loop. P<\/em>j continues to wait in the while loop as long as P<\/em>i is in its critical section. When P<\/em>i comes out of its critical section, P<\/em>i changes the value of flag[i] to false in its exit section. When flag[i] becomes false, the condition (flag [i] && turn == i) in the while loop becomes false for process\u00a0P<\/em>j. Hence, P<\/em>j comes out of the while loop and enters its critical section.<\/p>\n

     <\/p>\n

    We now see whether all the three conditions\u2014mutual exclusion, progress and bounded waiting\u2014are satisfied by this algorithm. Let P<\/em>0 and P<\/em>1 be the two processes that are competing to enter the critical section.<\/p>\n

    \"\"<\/p>\n

    The above scenario shows how mutual exclusion is satisfied. Initially, flag[0] and flag[1] are false. Let the value of turn be 0. If process <\/span>P<\/em>0 wants to enter its critical section, it changes the value of flag[0] to true and the value of turn to 1. Process <\/span>P<\/em>1 is not yet competing to enter its critical section. <\/span>P<\/em>0 checks the value of flag[1] and the value of turn in the while loop. As flag[1] is false and turn = 1, the condition (flag[1] && turn==j) becomes false. That is, even though the value of turn==j is true (here, j=1, since <\/span>P<\/em>0 is executing), the value of flag[1] is false. Therefore, the process <\/span>P<\/em>0 comes out of the while loop and enters its critical section.<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    When P<\/em>0 is in the critical section, let P<\/em>1 want to enter its critical section. P<\/em>1 changes flag[1] to true and changes turn to 0. In the condition inside the while loop, P<\/em>1 checks (flag[0] && turn=0). Since flag[0] is true and turn is 0, both the checks are true and the condition remains true. P<\/em>1 continues to wait in the while loop. When P<\/em>0 comes out of critical section, it changes flag[0] to false. Now the condition (flag[0] && turn=0), which is being checked by P<\/em>1 becomes false. P<\/em>1 now enters its critical section.<\/p>\n<\/div>\n

    \n

     <\/p>\n

    Thus it is seen that when P<\/em>0 is in its critical section, P<\/em>1 is not allowed to enter its critical section. P<\/em>1 is allowed to enter its critical section only after P<\/em>0 comes out of its critical section. Thus, mutual exclusion is satisfied.<\/p>\n

     <\/p>\n

    We now look at another scenario to understand that the algorithm satisfies mutual exclusion.<\/p>\n

     <\/p>\n

    Algorithm 3 \u2013 Mutual Exclusion<\/strong><\/p>\n

     <\/p>\n

    Scenario 2:<\/strong><\/p>\n<\/div>\n

    \n

    \"\"<\/p>\n

    In this scenario, initially, both flag[0] and flag[1] are false. Process <\/span>P<\/em>0 wants to enter its critical section, changes flag[0] to true and turn to 1. Immediately, there is a context switch and <\/span>P<\/em>1 starts executing. <\/span>P<\/em>1 changes flag[0] to true and changes turn to 0. Now, the value of flag[0] and flag[1] are true. The value of turn now decides the process that can enter its critical section. When <\/span>P<\/em>1 checks the condition in its while loop (flag[0] && turn==0), both flag[0] and turn==0 are true. <\/span>P<\/em>1 waits in the while loop. When <\/span>P<\/em>0 checks its while loop (flag[1] && turn==1), the condition flag[1] is true, but the condition turn==1 is false. Therefore, <\/span>P<\/em>0 comes out of the while loop and enters its critical section. When <\/span>P<\/em>0 comes out of its critical section, it changes the value of flag[0] to false and then <\/span>P<\/em>1 can enter its critical section. Thus, it is seen that only one process is allowed to enter its critical section at a particular time and hence, mutual exclusion is satisfied.<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    Algorithm 3 \u2013 Progress<\/strong><\/p>\n

     <\/p>\n

    Let us now see how progress is satisfied using the sequence shown below:<\/p>\n<\/div>\n

    \"\"<\/p>\n

    In the scenario explained above, initially, both flag[0] and flag[1] are false. Process <\/span>P<\/em>0 wants to enter its critical section and changes flag[0] to true. Immediately, there is a context switch and <\/span>P<\/em>1 starts executing. <\/span>P<\/em>1 changes flag[1] to true. Again, there is a context switch and <\/span>P<\/em>0 changes turn to 1. There is a context switch again and <\/span>P<\/em>1 changes turn to 0. Now, the values of flag[0] and flag[1] are true. Still, based on the value of turn, one of the two processes can enter the critical section. In algorithm 2, we saw that progress is not satisfied when both the processes set the value of flag[0] and flag[1] to true at the same time. Thus, in this algorithm, the decision as to which process can enter the critical section is not postponed indefinitely. Hence, the progress requirement is satisfied.<\/span><\/p>\n

    \n

     <\/p>\n

    Algorithm 3 \u2013 Progress<\/strong><\/p>\n

     <\/p>\n

    Another scenario to explain progress is given below:<\/p>\n

     <\/p>\n

    Scenario 2:<\/p>\n

    \"\"<\/p>\n

    In the scenario shown above, both P<\/em>0 and P<\/em>1 want to enter their respective critical sections. Initially, flag0] and flag[1] are false and turn is 0. flag[0] is changed to true by P<\/em>0 and flag[1] is changed to true by P<\/em>1. P<\/em>1 changes turn to 0. Then, P<\/em>0 changes turn to 1. In the while loop of P<\/em>0, flag[1] is true and turn is equal to 1. Since both the conditions are true, the condition checked in the while loop is true. Therefore, P<\/em>0 continues to wait in the while loop. In the while loop of P<\/em>1, flag[0] is true, but the value of turn is not equal to 0. Since one of the conditions is not true, the condition checked in the while loop is false and P<\/em>1 comes out of the while loop. P<\/em>1 enters its critical section. Thus, it is seen that the value of turn decides which process enters the critical section. The value of turn is based on which process sets the value of turn finally.<\/p>\n

     <\/p>\n

    Algorithm 3 \u2013 Bounded Waiting\u00a0<\/strong><\/p>\n

     <\/p>\n

    For the bounded waiting requirement, after a process has requested to enter its critical section, the amount of time the process waits should be limited. We will now see how the algorithm satisfies bounded waiting.<\/p>\n<\/div>\n

    \"\"<\/p>\n

    To understand that bounded waiting is satisfied, P<\/em>0 first requests to enter its critical section and then, P<\/em>1 tries to enter its critical section twice. We need to understand that after P<\/em>0 requests to enter its critical section, P<\/em>1 is not allowed to enter its critical section more than once.<\/p>\n

     <\/p>\n

    Initially, flag[0] and flag[1] are false. Let the value of turn be 0 initially. P<\/em>0 changes the value of flag[0] to true. Then there is a context switch and P<\/em>1 changes flag[1] to true. P<\/em>1 changes turn to 0. Now, again there is a context switch and P<\/em>0 changes the value of turn to 1. P<\/em>0 waits in the while loop. P<\/em>1 can now enter its critical section. P<\/em>1 comes out of its critical section and changes the value of flag[1] to false. Suppose P<\/em>1 continues to use the CPU and wants to enter its critical section again. P<\/em>1 changes the value of flag[1] to true and the value of turn to 0. Now, P<\/em>1 cannot enter its critical section unless P<\/em>0 enters its critical section, comes out and changes the value of flag[0] to true. P<\/em>1 is not allowed to enter critical section twice after P<\/em>0 had requested to enter critical section. Thus, bounded waiting requirement is satisfied.<\/p>\n

     <\/p>\n

    5.3\u00a0 Summary<\/strong><\/p>\n

     <\/p>\n

    This module discussed two solutions to the critical section problem. But both of these solutions work when there are only two processes. The first solution discussed in this module satisfies the mutual exclusion requirement but does not satisfy the progress requirement. The second solution discussed in this module satisfies all the three requirements.<\/p>\n

     <\/p>\n

    References<\/strong><\/p>\n

      \n
    1. Abraham Silberschatz, Peter B. Galvin, Greg Gagne, \u201cOperating System Concepts\u201d, Ninth Edition, John Wiley & Sons Inc., 2012.<\/li>\n
    2. William Stallings, \u201cOperating Systems: Internals and Design Principles\u201d, Seventh Edition, Pearson, 2012.<\/li>\n<\/ol>\n","protected":false},"author":4,"menu_order":8,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-mary-anitha-rajam"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-95","chapter","type-chapter","status-publish","hentry","contributor-dr-mary-anitha-rajam"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/95","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":5,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/95\/revisions"}],"predecessor-version":[{"id":413,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/95\/revisions\/413"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/95\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/media?parent=95"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapter-type?post=95"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/contributor?post=95"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/license?post=95"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}