{"id":90,"date":"2018-07-19T06:07:12","date_gmt":"2018-07-19T06:07:12","guid":{"rendered":"http:\/\/csp3.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=90"},"modified":"2018-08-07T05:13:46","modified_gmt":"2018-08-07T05:13:46","slug":"process-synchronization","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/chapter\/process-synchronization\/","title":{"rendered":"Process Synchronization"},"content":{"raw":"
\r\n\r\n \r\n

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

Cooperating processes share data either directly or through files. When two or more processes access shared data concurrently, data inconsistency may result. Maintaining data consistency requires mechanisms that will ensure the orderly execution of cooperating processes. The section of code in each process in which the process accesses shared data is called the critical-section of the process. During the execution of a process, the process may access many such shared data or the same shared data a number of times. Thus, a process may execute critical-sections of code multiple times during its execution. \u00a0This module introduces the critical-section problem and discusses solutions to the critical-section problem.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n10.2\u00a0 Bounded-buffer problem\u00a0<\/strong>\r\n\r\n \r\n

To understand the critical-section problem, we will revisit the bounded-buffer problem we learnt in an earlier module. The shared-memory solution to the bounded-buffer problem, discussed in the earlier module, allows at most N \u2013 1 items in the buffer at the same time. The solution is as follows:<\/p>\r\n \r\n\r\nShared data:<\/strong>\r\n\r\n#define BUFFER_SIZE 10\r\n\r\ntypedef struct {\r\n\r\n. . .\r\n\r\n} item;\r\n\r\nitem buffer[BUFFER_SIZE];\r\n\r\nint in = 0;\r\n\r\nint out = 0;\r\n\r\n \r\n

There is a buffer of size BUFFER_SIZE (10), which is used by the producer and the consumer processes to place and remove items respectively. There are two variables in <\/em>and out<\/em>, which point to the locations\u00a0 in the buffer where the producer places\u00a0 items and the consumer consumes items respectively. Initially, in <\/em>and out <\/em>point to the same location in the buffer.<\/p>\r\n \r\n\r\nC<\/strong>od<\/strong>e for producer process: <\/strong>\r\n\r\nitem next Produced;\r\n\r\nwhile (1) {\r\n

while (((in + 1) % BUFFER_SIZE) == out) ; \/* do nothing *\/<\/p>\r\n

buffer[in] = nextProduced;<\/p>\r\n

in = (in + 1) % BUFFER_SIZE;<\/p>\r\n}\r\n\r\n<\/div>\r\n \r\n

When (<\/span>in <\/em>+ 1) % BUFFER_SIZE == <\/span>out<\/em>, buffer is full. The producer waits if the buffer is full. Else, the producer places the item in the location pointed to by the <\/span>in <\/em>variable and increments the <\/span>in <\/em>variable.<\/span><\/p>\r\n\r\n

\r\n\r\n \r\n\r\nCode for consumer process:Item nextConsumed;\r\n\r\nwhile (1) {\r\n

while (in == out); \/* do nothing *\/<\/p>\r\n

nextConsumed = buffer[out];<\/p>\r\n

out = (out + 1) % BUFFER_SIZE;<\/p>\r\n}\r\n\r\n \r\n

The buffer is empty when in <\/em>== out<\/em>. The consumer waits when the buffer is empty. If the buffer is not empty, the consumer consumes the item pointed to by the out <\/em>variable and increments the out <\/em>variable.<\/p>\r\n \r\n

Suppose the consumer had not consumed any data. Then, the initial location will be pointed to by the out <\/em>pointer. When the in <\/em>pointer is pointing to the N \u2013 1th location, the condition \u201c(in <\/em>+ 1) % BUFFER_SIZE == out<\/em>\u201d will be true and the producer will wait. Thus, this solution uses only N \u2013 1 locations of the buffer.<\/p>\r\n \r\n

A solution, where all N buffers are used is not simple. A solution is possible when we modify the producer-consumer code by adding a variable counter<\/em>, initialized to 0 and incrementing it each time a new item is added to the buffer. The code for the solution to the bounded buffer problem using the counter <\/em>variable is given below:<\/p>\r\n \r\n\r\n#define BUFFER_SIZE 10\r\n\r\ntypedef struct {\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 . . .\r\n\r\n} item;\r\n\r\nitem buffer[BUFFER_SIZE];\r\n\r\nint in = 0;\r\n\r\nint out = 0;\r\n\r\nint counter = 0;\r\n\r\n\/*Producer process<\/strong>\r\n

item nextProduced;<\/p>\r\n

while (1) {<\/p>\r\n

while (counter == BUFFER_SIZE); \u00a0\/* do nothing *\/<\/p>\r\n

buffer[in] = nextProduced;<\/p>\r\n

in = (in + 1) % BUFFER_SIZE;<\/p>\r\n

counter++;<\/p>\r\n

}<\/p>\r\n\/*Consumer process<\/strong>\r\n

item nextConsumed; while (1) {<\/p>\r\n

while (counter == 0); \u00a0\/* do nothing *\/<\/p>\r\n

nextConsumed = buffer[out];<\/p>\r\n

out = (out + 1) % BUFFER_SIZE;<\/p>\r\n

counter--;<\/p>\r\n

}<\/p>\r\n\r\n<\/div>\r\n \r\n

In this solution, the variable <\/span>counter is <\/em>shared between the producer and the consumer. Whenever the producer places an item in the buffer, it increases the value of the variable. When the consumer consumes an item from the buffer, it decreases the value of the <\/span>counter <\/em>variable. Thus, the value of the variable <\/span>counter <\/em>maintains the count of the items present in the buffer. Now, we will see how the increment and decrement operations performed on the variable <\/span>counter <\/em>can lead to inconsistencies.<\/span><\/p>\r\n\r\n

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

The statements \u201ccounter++;\u201d <\/strong>and \u201ccounter--;\u201d <\/strong>must be performed atomically<\/em>. Atomic operation means an operation that completes in its entirety without interruption. The reason for this is explained below:<\/p>\r\n \r\n\r\nThe statement \u201ccounter++<\/strong>\u201d may be implemented in machine language as:\r\n\r\n \r\n\r\nregister1 = counter <\/strong>\r\n\r\nregister1 = register1 + 1 <\/strong>\r\n\r\ncounter = register1\u00a0<\/strong>\r\n\r\n \r\n

Thus, it is seen that the single statement counter++ <\/strong>in the producer\u2019s code is not executed as a single instruction. Rather, it is executed in three different instructions. Similarly, the single statement counter-- <\/strong>in the consumer\u2019s code is implemented in three different instructions.<\/p>\r\n \r\n\r\nThe statement \u201ccounter--<\/strong>\" may be implemented as:\r\n\r\n \r\n\r\nregister2 = counter <\/strong>\r\n\r\nregister2 = register2 \u2013 1 <\/strong>\r\n\r\ncounter = register2\u00a0<\/strong>\r\n\r\n \r\n

If both the producer and consumer attempt to update the buffer concurrently, the assembly language statements may get interleaved. Interleaving depends upon how\u00a0 the producer and consumer processes are scheduled.<\/p>\r\n \r\n\r\nAssume counter <\/strong>is initially 5.\r\n\r\nOne such interleaving of statements is:\r\n\r\n \r\n\r\nproducer: register1 = counter <\/strong>(register1 = 5<\/em>)\r\n\r\nproducer: register1 = register1 + 1 <\/strong>(register1 = 6<\/em>)\r\n\r\nconsumer: register2 = counter <\/strong>(register2 = 5<\/em>)\r\n\r\nconsumer: register2 = register2 \u2013 1 <\/strong>(register2 = 4<\/em>)\r\n\r\nproducer: counter = register1 <\/strong>(counter = 6<\/em>)\r\n\r\nconsumer: counter = register2 <\/strong>(counter = 4<\/em>)\r\n\r\n \r\n

Thus, the value of counter <\/strong>may be either 4 or 6, where the correct result should be 5.<\/p>\r\n \r\n

This situation is called a race condition, that is, the situation where several processes access and manipulate shared data concurrently. The final value of the shared data depends upon which process finishes last. To prevent race conditions, concurrent processes must be synchronized. Thus, by understanding the above-mentioned race condition, the critical- section problem can be understood.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n10.3\u00a0 The Critical-Section Problem\u00a0<\/strong>\r\n\r\n \r\n

There are n <\/em>processes that compete to use some shared data. Each process has a code segment, called critical-section<\/em>, in which the shared data is accessed. Hence, the problem is to ensure that, when one process is executing in its critical-section, no other process is allowed to execute in its critical-section. In the above example, the critical-section of code for the producer is counter++ <\/em>and the critical-section of code for the consumer is counter--<\/em>. It should be ensured that when the producer is executing counter<\/em>++, the consumer should not be allowed to access counter<\/em>--.<\/p>\r\n \r\n\r\n10.3.1\u00a0 Solution to the Critical-Section Problem\u00a0<\/strong>\r\n\r\n \r\n\r\nAny solution to the critical-section problem should satisfy the following conditions:\r\n\r\n \r\n

Mutual Exclusion<\/strong>: If process P<\/em>i <\/em>is executing in its critical-section, then no other processes can be executing in their critical-sections.<\/p>\r\n \r\n

Progress<\/strong>: If no process is executing in its critical-section and there exist some processes that wish to enter their critical-section, then the selection of the processes that will enter the critical-section next cannot be postponed indefinitely.<\/p>\r\n \r\n

Bounded Waiting<\/strong>: After a process has made a request to enter its critical-section and before that request is granted, a bound must exist on the number of times that \u00a0other processes are allowed to enter their critical-sections.<\/p>\r\n \r\n

Many algorithms were designed by researchers to solve the critical-section problem. The initial attempt to solve the critical-section problem provided a two-process solution.<\/p>\r\n \r\n\r\nThe general structure of any process P<\/em>i (the other process being P<\/em>j) is given below:\r\n\r\n \r\n\r\nd<\/strong>o <\/strong>{\r\n

en<\/em>t<\/em>ry section<\/em><\/p>\r\n

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

e<\/em>x<\/em>i<\/em>t section<\/em><\/p>\r\n

remainder section<\/p>\r\n} while (1)<\/strong>;\r\n\r\n \r\n

Before entering the critical-section, each process executes a piece of code called the entry section <\/em>and after coming out of the critical-section, the process executes a piece of code called the exit section<\/em>. The entry and the exit sections of code help in providing synchronization between the two processes. In the solutions provided, the processes share some common variables to synchronize their actions. One of the solutions to the critical- section problem, providing a two-process solution is given in Algorithm 1. The two processes are P<\/em>0 and P<\/em>1.<\/p>\r\n \r\n\r\n10.3.2\u00a0 Algorithm 1<\/strong>\r\n\r\n \r\n\r\n\u2022\u00a0 Shared variables:\r\n

\u2013\u00a0\u00a0\u00a0\u00a0\u00a0 in<\/strong>t turn<\/strong>; (initially turn = 0)<\/strong><\/p>\r\n

\u2013\u00a0\u00a0\u00a0\u00a0\u00a0 turn - i <\/strong>\u00de P<\/em>i <\/em>can enter its critical-section<\/p>\r\n\r\n<\/div>\r\n \r\n

\u2022\u00a0 Process <\/span>P<\/em>i<\/em><\/p>\r\n

do { while (turn != i) ;<\/span><\/p>\r\n

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

turn = j;<\/span><\/p>\r\n

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

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

\r\n\r\n \r\n\r\nThe variable turn <\/em>is common between the two processes. The value of the variable\u00a0turn <\/em>can be initialized to either 0 or 1. In this example, the value of turn <\/em>is initialised to 0.\r\n\r\n \r\n

In this algorithm, the entry section is\u00a0 the code \u201cwhile (turn != i)<\/strong>;\u201d. Any process before entering the critical-section, executes the entry section. The process checks the value of turn<\/em>. If P<\/em>0 finds that the value of turn <\/em>is 0, it enters critical-section. If P<\/em>0 finds that the value of turn <\/em>is 1, it waits till the value of turn <\/em>becomes 1. Similar is the case with process P<\/em>1. Here, we need to note the semicolon (;) at the end of the while statement.<\/p>\r\n \r\n\r\n\u201cwhile (turn != i) ;\u201d\r\n\r\nis the same as\r\n\r\nwhile(turn!=i)\r\n\r\n{\r\n\r\n}\r\n\r\n \r\n

As long as the condition (turn !=i) in the while loop is true, the process continues to loop in while. Only when the condition becomes false, the process comes out of the while loop.<\/p>\r\n \r\n

Therefore, when P<\/em>0 executes the entry section, if the value of turn <\/em>is 0, the condition tu<\/strong>rn!=0 <\/strong>becomes false and therefore, P<\/em>0 comes out of the while loop and enters critical section. If the value of turn <\/em>is 1, the condition turn!=0 <\/strong>is true and therefore, P<\/em>0 continues to execute in the while loop till the value of turn <\/em>is changed to 0.<\/p>\r\n \r\n

When a process comes out of the critical-section, it executes the exit section. In this algorithm, the exit section is the code \u201cturn = j<\/strong>;\u201d. The process changes the value of turn<\/em>. That is, when process P<\/em>0 is in the critical-section, the value of turn <\/em>would have been 0. When it comes out of the critical-section, it changes the value of turn <\/em>to 1. Similarly, when process P<\/em>1 comes out of the critical-section, it changes the value of turn <\/em>to 0.<\/p>\r\n \r\n

This\u00a0 \u00a0algorithm\u00a0 \u00a0satisfies\u00a0 \u00a0the \u00a0mutual \u00a0exclusion \u00a0condition, \u00a0but \u00a0not \u00a0the \u00a0progress condition. This is explained below:<\/p>\r\n \r\n\r\nAlgorithm 1 \u2013 Mutual Exclusion\r\n\r\n \r\n\r\nP<\/em>0\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 turn\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 P<\/em>1\r\n\r\n0\r\n\r\nChecks turn\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Checks turn\r\n\r\nEnters CS\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 waits\r\n\r\nExits CS\r\n\r\nChanges turn\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Enters CS\r\n\r\n \r\n\r\nChecks turn<\/span>\r\n\r\nWaits \u2026\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u2026<\/span>\r\n\r\n<\/div>\r\n

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

According to the mutual exclusion condition, when process P<\/em>0 is in its critical-section, process P<\/em>1 should wait and vice versa. Here, the value of turn <\/em>is initialized to 0. \u00a0Both processes P<\/em>0 and P<\/em>1 \u00a0want to enter critical-section. Hence, they are in the entry sections of\u00a0their respective codes. Both the processes check the value of <\/span>turn<\/em>. Since the value of <\/span>turn <\/em>is 0, <\/span>P<\/em>0 comes of the loop (the condition <\/span>turn!=i <\/strong>becomes false). <\/span>P<\/em>0 enters its critical-section. At the same time, process <\/span>P<\/em>1 finds the value of <\/span>turn <\/em>to be 0 and waits (<\/span>turn != i <\/strong>is true for <\/span>P<\/em>1). When process <\/span>P<\/em>0 comes out of its critical-section, it changes the value of <\/span>turn <\/em>to 1 (<\/span>turn = j<\/strong>). Now process <\/span>P<\/em>1 comes out of the while loop and enters its critical-section. Thus, it seen that, when process <\/span>P<\/em>0 is in its critical-section, process <\/span>P<\/em>1 waits, and when process <\/span>P<\/em>1 is in its critical-section, process <\/span>P<\/em>0 \u00a0waits. Thus, mutual exclusion is satisfied.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nAlgorithm 1 \u2013 Progress\r\n\r\n \r\n\r\nP<\/em>0\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 turn\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0P<\/em>1<\/sub>\r\n\r\n0\r\n\r\nChecks turn\r\n\r\nEnters CS\r\n\r\nExits CS\r\n\r\nChanges turn\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 1\r\n\r\n \r\n\r\nP0 wants to enter CS\r\n\r\nChecks turn\r\n\r\nWaits \u2026\r\n\r\n \r\n

According to the progress requirement, if there is no process executing in its critical- section and if there are some processes that are wanting to enter their critical-sections, then the selection of the process that will enter the critical-section next cannot be postponed indefinitely. In the example shown above, process P<\/em>0 comes out of its critical-section and changes the value of turn <\/em>to 1. Process P<\/em>1 does not want to enter its critical-section. Now, process P<\/em>0 wants to enter its critical-section again. But P<\/em>0 cannot enter its critical-section because the value of turn <\/em>is\u00a0 1. Unless\u00a0 process P<\/em>1 enters its critical-section and exits its critical-section and then changes the value of turn to 0, P<\/em>0 cannot enter its critical-section. Thus, it is seen that there needs to be a strict alternation between the processes P<\/em>0 and P<\/em>1. After P<\/em>0 comes out of its critical-section, P<\/em>1 should enter its critical-section. Only after that, P<\/em>0 can enter its critical-section the second time. Thus, it is seen that the progress requirement is not satisfied by this algorithm. Since this algorithm does not satisfy all the requirements for a solution to the critical-section problem, it is not a proper solution.<\/p>\r\n \r\n\r\n10.4\u00a0 Summary\u00a0<\/strong>\r\n\r\n \r\n

This module discussed the need for process synchronization when cooperating processes share data. The portion of code in each process that\u00a0 involves the access of shared data is called the critical-section of code. The access of the critical-section of each process should be synchronized. Any solution to this critical-section problem should satisfy the mutual exclusion, progress and the bounded waiting requirements. This module discussed one such solution to the critical-section problem where only two processes are involved. We saw that this solution satisfies the mutual exclusion requirement but not the progress requirement.<\/p>\r\n \r\n\r\nReferences\u00a0<\/strong>\r\n\r\n \r\n\r\n1.\u00a0 Abraham Silberschatz, Peter B. Galvin, Greg Gagne, \u201cOperating System Concepts\u201d,\u00a0Ninth Edition, John Wiley & Sons Inc., 2012.<\/span>\r\n\r\n<\/div>\r\n

    \r\n \t
  1. William Stallings, \u00a0\u201cOperating \u00a0Systems: \u00a0Internals \u00a0and \u00a0Design \u00a0Principles\u201d, \u00a0Seventh Edition, Pearson, 2012.<\/li>\r\n<\/ol>","rendered":"
    \n

     <\/p>\n

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

     <\/p>\n

    Cooperating processes share data either directly or through files. When two or more processes access shared data concurrently, data inconsistency may result. Maintaining data consistency requires mechanisms that will ensure the orderly execution of cooperating processes. The section of code in each process in which the process accesses shared data is called the critical-section of the process. During the execution of a process, the process may access many such shared data or the same shared data a number of times. Thus, a process may execute critical-sections of code multiple times during its execution. \u00a0This module introduces the critical-section problem and discusses solutions to the critical-section problem.<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    10.2\u00a0 Bounded-buffer problem\u00a0<\/strong><\/p>\n

     <\/p>\n

    To understand the critical-section problem, we will revisit the bounded-buffer problem we learnt in an earlier module. The shared-memory solution to the bounded-buffer problem, discussed in the earlier module, allows at most N \u2013 1 items in the buffer at the same time. The solution is as follows:<\/p>\n

     <\/p>\n

    Shared data:<\/strong><\/p>\n

    #define BUFFER_SIZE 10<\/p>\n

    typedef struct {<\/p>\n

    . . .<\/p>\n

    } item;<\/p>\n

    item buffer[BUFFER_SIZE];<\/p>\n

    int in = 0;<\/p>\n

    int out = 0;<\/p>\n

     <\/p>\n

    There is a buffer of size BUFFER_SIZE (10), which is used by the producer and the consumer processes to place and remove items respectively. There are two variables in <\/em>and out<\/em>, which point to the locations\u00a0 in the buffer where the producer places\u00a0 items and the consumer consumes items respectively. Initially, in <\/em>and out <\/em>point to the same location in the buffer.<\/p>\n

     <\/p>\n

    C<\/strong>od<\/strong>e for producer process: <\/strong><\/p>\n

    item next Produced;<\/p>\n

    while (1) {<\/p>\n

    while (((in + 1) % BUFFER_SIZE) == out) ; \/* do nothing *\/<\/p>\n

    buffer[in] = nextProduced;<\/p>\n

    in = (in + 1) % BUFFER_SIZE;<\/p>\n

    }<\/p>\n<\/div>\n

     <\/p>\n

    When (<\/span>in <\/em>+ 1) % BUFFER_SIZE == <\/span>out<\/em>, buffer is full. The producer waits if the buffer is full. Else, the producer places the item in the location pointed to by the <\/span>in <\/em>variable and increments the <\/span>in <\/em>variable.<\/span><\/p>\n

    \n

     <\/p>\n

    Code for consumer process:Item nextConsumed;<\/p>\n

    while (1) {<\/p>\n

    while (in == out); \/* do nothing *\/<\/p>\n

    nextConsumed = buffer[out];<\/p>\n

    out = (out + 1) % BUFFER_SIZE;<\/p>\n

    }<\/p>\n

     <\/p>\n

    The buffer is empty when in <\/em>== out<\/em>. The consumer waits when the buffer is empty. If the buffer is not empty, the consumer consumes the item pointed to by the out <\/em>variable and increments the out <\/em>variable.<\/p>\n

     <\/p>\n

    Suppose the consumer had not consumed any data. Then, the initial location will be pointed to by the out <\/em>pointer. When the in <\/em>pointer is pointing to the N \u2013 1th location, the condition \u201c(in <\/em>+ 1) % BUFFER_SIZE == out<\/em>\u201d will be true and the producer will wait. Thus, this solution uses only N \u2013 1 locations of the buffer.<\/p>\n

     <\/p>\n

    A solution, where all N buffers are used is not simple. A solution is possible when we modify the producer-consumer code by adding a variable counter<\/em>, initialized to 0 and incrementing it each time a new item is added to the buffer. The code for the solution to the bounded buffer problem using the counter <\/em>variable is given below:<\/p>\n

     <\/p>\n

    #define BUFFER_SIZE 10<\/p>\n

    typedef struct {\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 . . .<\/p>\n

    } item;<\/p>\n

    item buffer[BUFFER_SIZE];<\/p>\n

    int in = 0;<\/p>\n

    int out = 0;<\/p>\n

    int counter = 0;<\/p>\n

    \/*Producer process<\/strong><\/p>\n

    item nextProduced;<\/p>\n

    while (1) {<\/p>\n

    while (counter == BUFFER_SIZE); \u00a0\/* do nothing *\/<\/p>\n

    buffer[in] = nextProduced;<\/p>\n

    in = (in + 1) % BUFFER_SIZE;<\/p>\n

    counter++;<\/p>\n

    }<\/p>\n

    \/*Consumer process<\/strong><\/p>\n

    item nextConsumed; while (1) {<\/p>\n

    while (counter == 0); \u00a0\/* do nothing *\/<\/p>\n

    nextConsumed = buffer[out];<\/p>\n

    out = (out + 1) % BUFFER_SIZE;<\/p>\n

    counter–;<\/p>\n

    }<\/p>\n<\/div>\n

     <\/p>\n

    In this solution, the variable <\/span>counter is <\/em>shared between the producer and the consumer. Whenever the producer places an item in the buffer, it increases the value of the variable. When the consumer consumes an item from the buffer, it decreases the value of the <\/span>counter <\/em>variable. Thus, the value of the variable <\/span>counter <\/em>maintains the count of the items present in the buffer. Now, we will see how the increment and decrement operations performed on the variable <\/span>counter <\/em>can lead to inconsistencies.<\/span><\/p>\n

    \n

     <\/p>\n

    The statements \u201ccounter++;\u201d <\/strong>and \u201ccounter–;\u201d <\/strong>must be performed atomically<\/em>. Atomic operation means an operation that completes in its entirety without interruption. The reason for this is explained below:<\/p>\n

     <\/p>\n

    The statement \u201ccounter++<\/strong>\u201d may be implemented in machine language as:<\/p>\n

     <\/p>\n

    register1 = counter <\/strong><\/p>\n

    register1 = register1 + 1 <\/strong><\/p>\n

    counter = register1\u00a0<\/strong><\/p>\n

     <\/p>\n

    Thus, it is seen that the single statement counter++ <\/strong>in the producer\u2019s code is not executed as a single instruction. Rather, it is executed in three different instructions. Similarly, the single statement counter– <\/strong>in the consumer\u2019s code is implemented in three different instructions.<\/p>\n

     <\/p>\n

    The statement \u201ccounter–<\/strong>” may be implemented as:<\/p>\n

     <\/p>\n

    register2 = counter <\/strong><\/p>\n

    register2 = register2 \u2013 1 <\/strong><\/p>\n

    counter = register2\u00a0<\/strong><\/p>\n

     <\/p>\n

    If both the producer and consumer attempt to update the buffer concurrently, the assembly language statements may get interleaved. Interleaving depends upon how\u00a0 the producer and consumer processes are scheduled.<\/p>\n

     <\/p>\n

    Assume counter <\/strong>is initially 5.<\/p>\n

    One such interleaving of statements is:<\/p>\n

     <\/p>\n

    producer: register1 = counter <\/strong>(register1 = 5<\/em>)<\/p>\n

    producer: register1 = register1 + 1 <\/strong>(register1 = 6<\/em>)<\/p>\n

    consumer: register2 = counter <\/strong>(register2 = 5<\/em>)<\/p>\n

    consumer: register2 = register2 \u2013 1 <\/strong>(register2 = 4<\/em>)<\/p>\n

    producer: counter = register1 <\/strong>(counter = 6<\/em>)<\/p>\n

    consumer: counter = register2 <\/strong>(counter = 4<\/em>)<\/p>\n

     <\/p>\n

    Thus, the value of counter <\/strong>may be either 4 or 6, where the correct result should be 5.<\/p>\n

     <\/p>\n

    This situation is called a race condition, that is, the situation where several processes access and manipulate shared data concurrently. The final value of the shared data depends upon which process finishes last. To prevent race conditions, concurrent processes must be synchronized. Thus, by understanding the above-mentioned race condition, the critical- section problem can be understood.<\/p>\n<\/div>\n

    \n

     <\/p>\n

    10.3\u00a0 The Critical-Section Problem\u00a0<\/strong><\/p>\n

     <\/p>\n

    There are n <\/em>processes that compete to use some shared data. Each process has a code segment, called critical-section<\/em>, in which the shared data is accessed. Hence, the problem is to ensure that, when one process is executing in its critical-section, no other process is allowed to execute in its critical-section. In the above example, the critical-section of code for the producer is counter++ <\/em>and the critical-section of code for the consumer is counter–<\/em>. It should be ensured that when the producer is executing counter<\/em>++, the consumer should not be allowed to access counter<\/em>–.<\/p>\n

     <\/p>\n

    10.3.1\u00a0 Solution to the Critical-Section Problem\u00a0<\/strong><\/p>\n

     <\/p>\n

    Any solution to the critical-section problem should satisfy the following conditions:<\/p>\n

     <\/p>\n

    Mutual Exclusion<\/strong>: If process P<\/em>i <\/em>is executing in its critical-section, then no other processes can be executing in their critical-sections.<\/p>\n

     <\/p>\n

    Progress<\/strong>: If no process is executing in its critical-section and there exist some processes that wish to enter their critical-section, then the selection of the processes that will enter the critical-section next cannot be postponed indefinitely.<\/p>\n

     <\/p>\n

    Bounded Waiting<\/strong>: After a process has made a request to enter its critical-section and before that request is granted, a bound must exist on the number of times that \u00a0other processes are allowed to enter their critical-sections.<\/p>\n

     <\/p>\n

    Many algorithms were designed by researchers to solve the critical-section problem. The initial attempt to solve the critical-section problem provided a two-process solution.<\/p>\n

     <\/p>\n

    The general structure of any process P<\/em>i (the other process being P<\/em>j) is given below:<\/p>\n

     <\/p>\n

    d<\/strong>o <\/strong>{<\/p>\n

    en<\/em>t<\/em>ry section<\/em><\/p>\n

    critical-section<\/p>\n

    e<\/em>x<\/em>i<\/em>t section<\/em><\/p>\n

    remainder section<\/p>\n

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

     <\/p>\n

    Before entering the critical-section, each process executes a piece of code called the entry section <\/em>and after coming out of the critical-section, the process executes a piece of code called the exit section<\/em>. The entry and the exit sections of code help in providing synchronization between the two processes. In the solutions provided, the processes share some common variables to synchronize their actions. One of the solutions to the critical- section problem, providing a two-process solution is given in Algorithm 1. The two processes are P<\/em>0 and P<\/em>1.<\/p>\n

     <\/p>\n

    10.3.2\u00a0 Algorithm 1<\/strong><\/p>\n

     <\/p>\n

    \u2022\u00a0 Shared variables:<\/p>\n

    \u2013\u00a0\u00a0\u00a0\u00a0\u00a0 in<\/strong>t turn<\/strong>; (initially turn = 0)<\/strong><\/p>\n

    \u2013\u00a0\u00a0\u00a0\u00a0\u00a0 turn – i <\/strong>\u00de P<\/em>i <\/em>can enter its critical-section<\/p>\n<\/div>\n

     <\/p>\n

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

    do { while (turn != i) ;<\/span><\/p>\n

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

    turn = j;<\/span><\/p>\n

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

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

    \n

     <\/p>\n

    The variable turn <\/em>is common between the two processes. The value of the variable\u00a0turn <\/em>can be initialized to either 0 or 1. In this example, the value of turn <\/em>is initialised to 0.<\/p>\n

     <\/p>\n

    In this algorithm, the entry section is\u00a0 the code \u201cwhile (turn != i)<\/strong>;\u201d. Any process before entering the critical-section, executes the entry section. The process checks the value of turn<\/em>. If P<\/em>0 finds that the value of turn <\/em>is 0, it enters critical-section. If P<\/em>0 finds that the value of turn <\/em>is 1, it waits till the value of turn <\/em>becomes 1. Similar is the case with process P<\/em>1. Here, we need to note the semicolon (;) at the end of the while statement.<\/p>\n

     <\/p>\n

    \u201cwhile (turn != i) ;\u201d<\/p>\n

    is the same as<\/p>\n

    while(turn!=i)<\/p>\n

    {<\/p>\n

    }<\/p>\n

     <\/p>\n

    As long as the condition (turn !=i) in the while loop is true, the process continues to loop in while. Only when the condition becomes false, the process comes out of the while loop.<\/p>\n

     <\/p>\n

    Therefore, when P<\/em>0 executes the entry section, if the value of turn <\/em>is 0, the condition tu<\/strong>rn!=0 <\/strong>becomes false and therefore, P<\/em>0 comes out of the while loop and enters critical section. If the value of turn <\/em>is 1, the condition turn!=0 <\/strong>is true and therefore, P<\/em>0 continues to execute in the while loop till the value of turn <\/em>is changed to 0.<\/p>\n

     <\/p>\n

    When a process comes out of the critical-section, it executes the exit section. In this algorithm, the exit section is the code \u201cturn = j<\/strong>;\u201d. The process changes the value of turn<\/em>. That is, when process P<\/em>0 is in the critical-section, the value of turn <\/em>would have been 0. When it comes out of the critical-section, it changes the value of turn <\/em>to 1. Similarly, when process P<\/em>1 comes out of the critical-section, it changes the value of turn <\/em>to 0.<\/p>\n

     <\/p>\n

    This\u00a0 \u00a0algorithm\u00a0 \u00a0satisfies\u00a0 \u00a0the \u00a0mutual \u00a0exclusion \u00a0condition, \u00a0but \u00a0not \u00a0the \u00a0progress condition. This is explained below:<\/p>\n

     <\/p>\n

    Algorithm 1 \u2013 Mutual Exclusion<\/p>\n

     <\/p>\n

    P<\/em>0\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 turn\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 P<\/em>1<\/p>\n

    0<\/p>\n

    Checks turn\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Checks turn<\/p>\n

    Enters CS\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 waits<\/p>\n

    Exits CS<\/p>\n

    Changes turn\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Enters CS<\/p>\n

     <\/p>\n

    Checks turn<\/span><\/p>\n

    Waits \u2026\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u2026<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    According to the mutual exclusion condition, when process P<\/em>0 is in its critical-section, process P<\/em>1 should wait and vice versa. Here, the value of turn <\/em>is initialized to 0. \u00a0Both processes P<\/em>0 and P<\/em>1 \u00a0want to enter critical-section. Hence, they are in the entry sections of\u00a0their respective codes. Both the processes check the value of <\/span>turn<\/em>. Since the value of <\/span>turn <\/em>is 0, <\/span>P<\/em>0 comes of the loop (the condition <\/span>turn!=i <\/strong>becomes false). <\/span>P<\/em>0 enters its critical-section. At the same time, process <\/span>P<\/em>1 finds the value of <\/span>turn <\/em>to be 0 and waits (<\/span>turn != i <\/strong>is true for <\/span>P<\/em>1). When process <\/span>P<\/em>0 comes out of its critical-section, it changes the value of <\/span>turn <\/em>to 1 (<\/span>turn = j<\/strong>). Now process <\/span>P<\/em>1 comes out of the while loop and enters its critical-section. Thus, it seen that, when process <\/span>P<\/em>0 is in its critical-section, process <\/span>P<\/em>1 waits, and when process <\/span>P<\/em>1 is in its critical-section, process <\/span>P<\/em>0 \u00a0waits. Thus, mutual exclusion is satisfied.<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    Algorithm 1 \u2013 Progress<\/p>\n

     <\/p>\n

    P<\/em>0\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 turn\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0P<\/em>1<\/sub><\/p>\n

    0<\/p>\n

    Checks turn<\/p>\n

    Enters CS<\/p>\n

    Exits CS<\/p>\n

    Changes turn\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 1<\/p>\n

     <\/p>\n

    P0 wants to enter CS<\/p>\n

    Checks turn<\/p>\n

    Waits \u2026<\/p>\n

     <\/p>\n

    According to the progress requirement, if there is no process executing in its critical- section and if there are some processes that are wanting to enter their critical-sections, then the selection of the process that will enter the critical-section next cannot be postponed indefinitely. In the example shown above, process P<\/em>0 comes out of its critical-section and changes the value of turn <\/em>to 1. Process P<\/em>1 does not want to enter its critical-section. Now, process P<\/em>0 wants to enter its critical-section again. But P<\/em>0 cannot enter its critical-section because the value of turn <\/em>is\u00a0 1. Unless\u00a0 process P<\/em>1 enters its critical-section and exits its critical-section and then changes the value of turn to 0, P<\/em>0 cannot enter its critical-section. Thus, it is seen that there needs to be a strict alternation between the processes P<\/em>0 and P<\/em>1. After P<\/em>0 comes out of its critical-section, P<\/em>1 should enter its critical-section. Only after that, P<\/em>0 can enter its critical-section the second time. Thus, it is seen that the progress requirement is not satisfied by this algorithm. Since this algorithm does not satisfy all the requirements for a solution to the critical-section problem, it is not a proper solution.<\/p>\n

     <\/p>\n

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

     <\/p>\n

    This module discussed the need for process synchronization when cooperating processes share data. The portion of code in each process that\u00a0 involves the access of shared data is called the critical-section of code. The access of the critical-section of each process should be synchronized. Any solution to this critical-section problem should satisfy the mutual exclusion, progress and the bounded waiting requirements. This module discussed one such solution to the critical-section problem where only two processes are involved. We saw that this solution satisfies the mutual exclusion requirement but not the progress requirement.<\/p>\n

     <\/p>\n

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

     <\/p>\n

    1.\u00a0 Abraham Silberschatz, Peter B. Galvin, Greg Gagne, \u201cOperating System Concepts\u201d,\u00a0Ninth Edition, John Wiley & Sons Inc., 2012.<\/span><\/p>\n<\/div>\n

      \n
    1. William Stallings, \u00a0\u201cOperating \u00a0Systems: \u00a0Internals \u00a0and \u00a0Design \u00a0Principles\u201d, \u00a0Seventh Edition, Pearson, 2012.<\/li>\n<\/ol>\n","protected":false},"author":4,"menu_order":7,"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-90","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\/90","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\/90\/revisions"}],"predecessor-version":[{"id":412,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/90\/revisions\/412"}],"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\/90\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/media?parent=90"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapter-type?post=90"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/contributor?post=90"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/license?post=90"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}