{"id":136,"date":"2018-07-19T07:11:43","date_gmt":"2018-07-19T07:11:43","guid":{"rendered":"http:\/\/csp3.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=136"},"modified":"2018-08-07T05:30:40","modified_gmt":"2018-08-07T05:30:40","slug":"process-synchronization-solutions-iii","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/chapter\/process-synchronization-solutions-iii\/","title":{"rendered":"Process Synchronization \u2013 Solutions III"},"content":{"raw":"
\r\n\r\n \r\n

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

Cooperating processes may share data among themselves. Cooperating processes use common variables and data structures for sharing data. In a process, that portion of code where the process accesses shared data is called the critical section of the process. If there is no proper synchronization between the processes when they access their critical sections of code, then inconsistency of data may result. We saw a few solutions to the critical section problem in the previous modules (Modules 10, 11 and 12). In this module, we continue to learn more solutions to solve the critical section problem when there are multiple (>=2) processes. The Test And Set and Swap are two hardware instructions that can be executed atomically and can provide solution to the critical section problem. We can use these special instructions to solve the critical section problem.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n13.2\u00a0 Swap instruction<\/strong>\r\n\r\n \r\n

The Swap instruction is defined as follows:<\/p>\r\nvoid Swap(boolean &a, boolean &b)\r\n\r\n{<\/strong>\r\n\r\nboolean temp = a; <\/strong>\r\n\r\na = b;<\/strong>\r\n\r\nb = temp;<\/strong>\r\n\r\n}<\/strong>\r\n\r\n \r\n

The Swap instruction takes two Boolean variables and swaps the value of the variables. The swapping is done atomically.<\/p>\r\n \r\n\r\n13.2.1 Solution to the Critical Section Problem Using the Swap Instruction\u00a0<\/strong>\r\n\r\n \r\n

A solution to the critical section problem using the Swap instruction is explained in this section. This is a multiple-process solution. More than two processes competing to enter their critical sections can use this solution to solve the critical section problem.<\/p>\r\n \r\n\r\nShared data:\r\n\r\n \r\n

boolean lock; \/* <\/strong>(initialized to false<\/strong>) *\/<\/p>\r\n \r\n\r\nThe algorithm for process P<\/em>i <\/em>is given below:\r\n

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

key = true;<\/strong><\/p>\r\n

w<\/strong>hile (key == true)<\/strong><\/p>\r\n

Swap(lock, key);<\/strong><\/p>\r\n

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

lock=false;<\/span><\/strong><\/p>\r\n

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

}\u00a0<\/span><\/p>\r\n\r\n<\/div>\r\n \r\n\r\nIn this algorithm, lock is a shared variable and key is a variable local to each process. When process P<\/em>i executes this algorithm, it changes the value of its local variable key to true. Then, as long as key is true, P<\/em>i keeps swapping the values of lock and key.\r\n\r\n \r\n\r\nIf the value of lock is true, even though lock and key are swapped, the value of key remains true. This makes process P<\/em>i to continue to check in the while loop.\r\n\r\n \r\n\r\nIf the value of lock is false, swapping lock and key will change the value of key to false and the value of lock to true. This makes the process\u00a0 P<\/em>i\u00a0 \u00a0to come out of the while loop (while(key==true) becomes while(false)). If P<\/em>i \u00a0comes out of the while loop, it enters its critical section. The value of lock remains true during this time.\r\n\r\n \r\n\r\nWhen P<\/em>i comes out of its critical section, it changes the value of lock to false.\r\n\r\n \r\n\r\n13.2.2. Mutual Exclusion\u00a0<\/strong>\r\n\r\n \r\n\r\nLet us now see how this algorithm satisfies mutual exclusion.\r\n\r\n \r\n\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 P<\/em><\/strong>0<\/sub>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 <\/strong>key(P<\/em><\/strong>0<\/strong><\/sub>)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0lock\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0key(P<\/em><\/strong>1<\/strong>)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 P<\/em><\/strong>1<\/strong>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
<\/td>\r\n<\/td>\r\nfalse<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\ntrue<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
Swap<\/td>\r\nfalse<\/td>\r\ntrue<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\ntrue<\/td>\r\n<\/td>\r\n<\/tr>\r\n
In CS<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nSwap<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\ntrue<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nwaits<\/td>\r\n<\/tr>\r\n
Out of CS<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\nfalse<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\ntrue<\/td>\r\nfalse<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nIn CS<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n

Let two processes <\/span>P<\/em>0 and <\/span>P<\/em>1 compete to enter their respective critical sections. Each of the two processes has its own local key variable. Initially, lock is false. The key variables of each of the two processes are true initially. <\/span>P<\/em>0 wants to enter critical section first. <\/span>P<\/em>0 executes Swap(key(<\/span>P<\/em>0), lock). This will make the value of lock true and the value of key false. As key becomes false, <\/span>P<\/em>0 comes out of the while loop and enters its critical section. Suppose, <\/span>P<\/em>1 wants to enter its critical section when <\/span>P<\/em>0 is in its critical section. <\/span>P<\/em>1 sets the value of its key to true. <\/span>P<\/em>1 executes Swap(key(<\/span>P<\/em>1), lock). Since the value of lock is currently true, the value of key also continues to be true. <\/span>P<\/em>1 continues to execute in the while loop. When <\/span>P<\/em>0 comes out of its critical section, it changes the value of lock to false. Now <\/span>P<\/em>1, executing in the while loop, swaps lock and its key. <\/span>P<\/em>1\u2019s key becomes false and <\/span>P<\/em>1 comes out of the while loop and enters critical section. Thus, it is seen that <\/span>P<\/em>1 is not allowed to enter its critical section when <\/span>P<\/em>0 is in its critical section. When one process is in its critical section, the value of lock is true and no other process can enter its critical section. Thus, mutual exclusion is satisfied.<\/span><\/p>\r\n\r\n

\r\n\r\n \r\n\r\n13.2.3 Swap \u2013 Bounded Waiting<\/strong>\r\n\r\n \r\n\r\nWe now see if this algorithm satisfies the bounded waiting requirement.\r\n\r\n \r\n\r\n\u00a0 \u00a0 \u00a0 P<\/em><\/strong>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 <\/strong>key(P<\/em><\/strong>0<\/strong>)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0lock\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0key(P<\/em><\/strong>1<\/strong>)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 P<\/em><\/strong>1<\/strong>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
<\/td>\r\n<\/td>\r\nfalse<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\ntrue<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
Swap<\/td>\r\nfalse<\/td>\r\ntrue<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\ntrue<\/td>\r\n<\/td>\r\n<\/tr>\r\n
In CS<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nSwap<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\ntrue<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nWaits<\/td>\r\n<\/tr>\r\n
Out of CS<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
Swap<\/td>\r\nfalse<\/td>\r\ntrue<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
In CS<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nStill waits<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n

Let P<\/em>0 and P<\/em>1 be two processes that are competing to access their respective critical sections. Initially, lock is false. Initially, the key variable of each of the two processes is true. P<\/em>0 wants to enter its critical section first. P<\/em>0 executes Swap(key(P<\/em>0), lock). This makes the value of lock true and the value of key false. As key becomes false, P<\/em>0 comes out of the while loop and enters its critical section. Let P<\/em>1 want to enter its critical section when P<\/em>0 is in its critical section. P<\/em>1 sets the value of its key to true. P<\/em>1 executes Swap(key(P<\/em>1), lock). Since the value of lock is currently true, the value of key also continues to be true. P<\/em>1\u00a0 continues to execute in the while loop. When P<\/em>0 comes out of its critical section, it changes the value of lock to false. Let P<\/em>0 continue to use the CPU without context switch. Say, P<\/em>0 wants to enter its critical section again. Since the value of lock is currently false, P<\/em>0 can enter its critical section again. Process P<\/em>1 continues to wait. Since there was no context switch after P<\/em>0 came out of its critical section and P<\/em>0 changed lock to true, P<\/em>1 could not come out of the while loop. Thus, even though P<\/em>1 had requested to enter its critical section, P<\/em>0 is allowed to enter its critical section again and again. Therefore, the bounded waiting requirement is not satisfied.<\/p>\r\n \r\n

Thus, it is seen that this algorithm does not satisfy the bounded waiting requirement, though it satisfies the mutual exclusion requirement.<\/p>\r\n \r\n\r\n13.3\u00a0 TestandSet - Bounded-Waiting - Mutual Exclusion\u00a0<\/strong>\r\n\r\n \r\n\r\nThe algorithm given below makes use of the TestAndSet instruction and satisfies all the three requirements for a solution to the critical section problem. This is also a solution when there are n <\/em>processes.\r\n\r\n \r\n\r\nThe shared variables used in the algorithm are as follows:\r\n\r\n \r\n

boolean waiting[n];\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/\/initially false <\/strong><\/p>\r\n

boolean lock\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 \/\/initially false\u00a0<\/strong><\/p>\r\n \r\n\r\nThe algorithm for process P<\/em>i is given below:\r\n\r\ndo {\r\n

waiting[i] = TRUE; key = TRUE;<\/span><\/p>\r\n

while (waiting[i] && key) \u00a0key = TestAndSet(lock); <\/span><\/p>\r\n

waiting[i] = FALSE;<\/span><\/p>\r\n

\/\/ critical section j = (i + 1) % n;<\/span><\/p>\r\n

while ((j != i) && !waiting[j])\u00a0\u00a0\u00a0\u00a0 j = (j + 1) % n;<\/span><\/p>\r\n

if (j == i)<\/span><\/p>\r\n

lock = FALSE;<\/span><\/p>\r\n

else<\/span><\/p>\r\n

waiting[j] = FALSE;<\/span><\/p>\r\n

\/\/ remainder section<\/span><\/p>\r\n} while (TRUE);<\/span>\r\n\r\n<\/div>\r\n

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

The algorithm given above is for process P<\/em>i. waiting <\/em>is an array with \u2018n<\/em>\u2019 elements, where n <\/em>is the number of processes competing to enter their respective critical sections. lock <\/em>is a Boolean variable. Each line in the algorithm is explained below:<\/p>\r\n \r\n\r\nwaiting[i] = TRUE;\r\n\r\n \r\n\r\nProcess P<\/em>i before checking to enter its critical section sets the value of waiting[i] to true.\r\n\r\n \r\n\r\nkey = TRUE;\r\n\r\n \r\n\r\nkey is a variable local to process P<\/em>i. It is set to true.\r\n\r\n \r\n\r\nwhile (waiting[i] && key)\u00a0\u00a0 key = TestAndSet(lock);\r\n\r\n \r\n

For process P<\/em>i, waiting[i] and key are true, initially. Therefore, the condition (waiting[i] && key<\/em>) is true. Since this condition is true, P<\/em>i executes TestAndSet(lock). Initially, lock is false. Since lock is false, TestAndSet(lock) returns false and the value of lock is changed to true. The return value is assigned to key. Thus, key is now assigned the value \u2013 false. Now, the condition (waiting[i] && key<\/em>) becomes false. Process P<\/em>i comes out of the while loop.<\/p>\r\n \r\n

If lock is true, TestAndSet(lock) returns true. Therefore, key is assigned true. The condition in the while loop remains true. Process P<\/em>i continues to execute in while loop.<\/p>\r\n \r\n\r\nwaiting[i] = FALSE;After coming out of the while loop, P<\/em>i changes waiting[i] to false and enters its critical section.\r\n\r\n \r\n

Process P<\/em>i, after coming out of its critical section, checks if any other process is waiting to enter its critical section. If any other process is waiting to enter its critical section, P<\/em>i changes the value of waiting <\/em>of that process to false. Else, changes the value of lock to false. Changing the value of waiting <\/em>of a process to false will make that waiting process to come out of the while loop and enter its critical section. If no process is waiting, the value of lock is changed to false. This paves the way for any other process wanting to enter its critical section, to enter its critical section in future.<\/p>\r\n \r\n

j = (i + 1) % n;<\/span><\/p>\r\n \r\n

The next process <\/span>P<\/em>j to be checked is found. j is found by incrementing i.<\/span><\/p>\r\n \r\n

while ((j != i) && !waiting[j])\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 j = (j + 1) % n;<\/span><\/p>\r\n\r\n<\/div>\r\n

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

P<\/em>i checks if waiting[j] is true, for every other process j. If true, P<\/em>i comes out of its while loop. This means that there is another process j in its entry section waiting to enter its critical section. If waiting[j] is not true, process j is not in its entry section. Therefore, the other processes are checked one after the other. When j becomes equal to i, it means that all other processes have been checked already. There is no other process waiting in its entry section.<\/p>\r\n \r\n\r\nif (j == i)<\/strong>\r\n

lock = FALSE;<\/strong><\/p>\r\nelse<\/strong>\r\n

w<\/strong>a<\/strong>iting[j] = FALSE;<\/strong><\/p>\r\n\r\n<\/div>\r\n

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

If j==i, there is no other process in its entry section and lock is made false. Else, waiting[j] (j is the process waiting in its entry section) is made false.<\/p>\r\n \r\n\r\n13.3.1\u00a0 Mutual exclusion\u00a0<\/strong>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
w<\/strong>a<\/strong>iting[0]<\/strong><\/td>\r\nP<\/em><\/strong>0<\/strong><\/td>\r\nkey(0)<\/strong><\/td>\r\nlock<\/strong><\/td>\r\nkey(1)<\/strong><\/td>\r\nP<\/em><\/strong>1<\/strong><\/td>\r\nw<\/strong>a<\/strong>iting[1]<\/strong><\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\nfalse<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
false<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nfalse<\/td>\r\n<\/tr>\r\n
true<\/td>\r\n<\/td>\r\ntrue<\/td>\r\n<\/td>\r\ntrue<\/td>\r\n<\/td>\r\ntrue<\/td>\r\n<\/tr>\r\n
<\/td>\r\nTestAndSet(lock)<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\nfalse<\/td>\r\ntrue<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
false<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\nEnters CS<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nTestAndSet(lock)<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nTrue<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nWaits<\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n

The sequence given above shows how the algorithm satisfies the mutual exclusion requirement. Let P<\/em>0 and P<\/em>1 be the two processes competing to enter their respective critical sections. Initially, lock, waiting[0] and waiting[1] are false. P<\/em>0 changes waiting[0] and its local variable key(0) to true. P<\/em>0 then executes TestAndSet(lock). Since lock is false, TestAndSet(lock) returns false and the value is assigned to key(0). The value of lock is changed to true. Since key(0) becomes false, P<\/em>0 comes out of its while loop, changes waiting[0] to false and enters its critical section. While P<\/em>0 is in its critical section, let P<\/em>1 want to enter its critical section. P<\/em>1 changes waiting[1] and its local variable key(1) to true. P<\/em>0 then executes TestAndSet(lock). Since lock is true, TestAndSet(lock) returns true and the value \u2018true\u2019 is assigned to key(0). Since key(0) is true, P<\/em>1 continues to execute in its while loop. Thus, when one process is in its critical section, the other processes are not allowed to enter their respective critical sections. Thus,\u00a0mutual exclusion is satisfied.<\/span><\/p>\r\n\r\n<\/div>\r\n \r\n

13.3.2\u00a0 Progress \u2013 Scenario 1<\/strong><\/p>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
w<\/strong>a<\/strong>iting[0]<\/strong><\/td>\r\nP<\/em><\/strong>0<\/strong><\/sub><\/td>\r\nkey(0)<\/strong><\/td>\r\nlock<\/strong><\/td>\r\nkey(1)<\/strong><\/td>\r\nP<\/em><\/strong>1<\/strong><\/sub><\/td>\r\nw<\/strong>a<\/strong>iting[1]<\/strong><\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\nfalse<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
false<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nfalse<\/td>\r\n<\/tr>\r\n
true<\/td>\r\n<\/td>\r\ntrue<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\ntrue<\/td>\r\n<\/td>\r\ntrue<\/td>\r\n<\/tr>\r\n
<\/td>\r\nTestAndSet(lock)<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\nfalse<\/td>\r\ntrue<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
false<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\nEnters CS<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nTestAndSet(lock)<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nTrue<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nWaits<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\nOut of CS<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nfalse<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nEnters CS<\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n

The sequence given above, shows how the algorithm satisfies the progress requirement. Let P<\/em>0 and P<\/em>1 be the two processes competing to enter their respective critical sections. Initially, lock, waiting[0] and waiting[1] are false. P<\/em>0 changes waiting[0] and its local variable key(0) to true. Now, there is a context switch and P<\/em>1 changes waiting[1] and key(1) to true. Again, there is a context switch and P<\/em>0 executes TestAndSet(lock). Since lock is false, TestAndSet(lock) returns false and the value \u2018false\u2019 is assigned to key(0). The value of lock is changed to true. Since key(0) becomes false, P<\/em>0 comes out of while loop, changes waiting[0] to false and enters its critical section. Now, if P<\/em>1 gets the CPU, it executes TestAndSet(lock). Since lock is true, TestAndSet(lock) returns true and the value \u2018true\u2019 is assigned to key(0). Since key(0) is true, P<\/em>1 continues to execute in its while loop. When P<\/em>0 comes out of its critical section, it checks if the waiting value of any other process is true. This checking is done one process after the other. In this example, since there are only two processes, the waiting status of P<\/em>1 is checked. Since waiting[1] is true, !waiting[1] is false. This makes the condition in the while loop false for P<\/em>0. P<\/em>0 comes out of the while loop and changes waiting[1] to false. When waiting[1] becomes false, P<\/em>1 comes out of the while loop while (waiting[i] && key) key = TestAndSet(lock);<\/strong>. P<\/em>1 enters its critical section. Hence, there is progress.<\/p>\r\n \r\n

13.3.3 Progress \u2013 Scenario 2<\/strong><\/p>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
w<\/strong>a<\/strong>iting[0]<\/strong><\/td>\r\nP<\/em><\/strong>0<\/strong><\/td>\r\nkey(0)<\/strong><\/td>\r\nlock<\/strong><\/td>\r\nkey(1)<\/strong><\/td>\r\nP<\/em><\/strong>1<\/strong><\/td>\r\nw<\/strong>a<\/strong>iting[1]<\/strong><\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\nfalse<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
false<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\nfalse<\/td>\r\n<\/tr>\r\n
true<\/td>\r\n<\/td>\r\ntrue<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\nTestAndSet(lock)<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\nfalse<\/td>\r\ntrue<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
false<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\nEnters CS<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\nOut of CS<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\nNo other process is waiting<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n
<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n

Another sequence of execution to show that progress is satisfied is given above. Let P<\/em>0 and P<\/em>1 be the two processes competing to enter their respective critical sections. Initially, lock, waiting[0] and waiting[1] are false. P<\/em>0 changes waiting[0] and its local variable key(0) to true. Since lock is false, TestAndSet(lock) returns false and the value is assigned to key(0). The value of lock is changed to true. Since key(0) becomes false, P<\/em>0\u00a0 comes out of the while loop, changes waiting[0] to false and enters its critical section. When P<\/em>0 comes out of its critical section, it checks if the waiting value of any other process is true. This checking is done one process after the other. In this example, since there are only two processes, the waiting status of P<\/em>1 is checked. Since waiting[1] is false, !waiting[1] becomes true. This makes the condition in the while loop true for P<\/em>0. So, P<\/em>0 executes j=j +1 % n. j was 1 earlier. Now, it becomes 0. Since j becomes equal to i, P<\/em>0 comes out of the while loop and changes lock to false. Since lock is changed to false, any process can enter its critical section in future.<\/p>\r\n \r\n

13.3.4\u00a0 Bounded waiting:<\/strong><\/p>\r\n \r\n

After a process comes out of its critical section, it checks if the next process is waiting to enter its critical section. Similarly, every other process is checked. Only if no other process is in the entry section, the value of lock is changed to false. Thus, when there are n <\/em>processes, a process may have to wait for n<\/em>\u20131 critical section executions before its turn to enter critical section. Thus, the bounded waiting requirement is satisfied.<\/p>\r\n \r\n

13.4 Summary<\/strong><\/p>\r\n \r\n

In this module, we first learned a solution to the critical section problem using the Swap instruction. But the solution did not satisfy the bounded waiting requirement. Next, we learned a solution to the critical section problem using the TestAndSet instruction that 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<\/ol>","rendered":"
    \n

     <\/p>\n

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

     <\/p>\n

    Cooperating processes may share data among themselves. Cooperating processes use common variables and data structures for sharing data. In a process, that portion of code where the process accesses shared data is called the critical section of the process. If there is no proper synchronization between the processes when they access their critical sections of code, then inconsistency of data may result. We saw a few solutions to the critical section problem in the previous modules (Modules 10, 11 and 12). In this module, we continue to learn more solutions to solve the critical section problem when there are multiple (>=2) processes. The Test And Set and Swap are two hardware instructions that can be executed atomically and can provide solution to the critical section problem. We can use these special instructions to solve the critical section problem.<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    13.2\u00a0 Swap instruction<\/strong><\/p>\n

     <\/p>\n

    The Swap instruction is defined as follows:<\/p>\n

    void Swap(boolean &a, boolean &b)<\/p>\n

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

    boolean temp = a; <\/strong><\/p>\n

    a = b;<\/strong><\/p>\n

    b = temp;<\/strong><\/p>\n

    }<\/strong><\/p>\n

     <\/p>\n

    The Swap instruction takes two Boolean variables and swaps the value of the variables. The swapping is done atomically.<\/p>\n

     <\/p>\n

    13.2.1 Solution to the Critical Section Problem Using the Swap Instruction\u00a0<\/strong><\/p>\n

     <\/p>\n

    A solution to the critical section problem using the Swap instruction is explained in this section. This is a multiple-process solution. More than two processes competing to enter their critical sections can use this solution to solve the critical section problem.<\/p>\n

     <\/p>\n

    Shared data:<\/p>\n

     <\/p>\n

    boolean lock; \/* <\/strong>(initialized to false<\/strong>) *\/<\/p>\n

     <\/p>\n

    The algorithm for process P<\/em>i <\/em>is given below:<\/p>\n

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

    key = true;<\/strong><\/p>\n

    w<\/strong>hile (key == true)<\/strong><\/p>\n

    Swap(lock, key);<\/strong><\/p>\n

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

    lock=false;<\/span><\/strong><\/p>\n

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

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

     <\/p>\n

    In this algorithm, lock is a shared variable and key is a variable local to each process. When process P<\/em>i executes this algorithm, it changes the value of its local variable key to true. Then, as long as key is true, P<\/em>i keeps swapping the values of lock and key.<\/p>\n

     <\/p>\n

    If the value of lock is true, even though lock and key are swapped, the value of key remains true. This makes process P<\/em>i to continue to check in the while loop.<\/p>\n

     <\/p>\n

    If the value of lock is false, swapping lock and key will change the value of key to false and the value of lock to true. This makes the process\u00a0 P<\/em>i\u00a0 \u00a0to come out of the while loop (while(key==true) becomes while(false)). If P<\/em>i \u00a0comes out of the while loop, it enters its critical section. The value of lock remains true during this time.<\/p>\n

     <\/p>\n

    When P<\/em>i comes out of its critical section, it changes the value of lock to false.<\/p>\n

     <\/p>\n

    13.2.2. Mutual Exclusion\u00a0<\/strong><\/p>\n

     <\/p>\n

    Let us now see how this algorithm satisfies mutual exclusion.<\/p>\n

     <\/p>\n

    \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 P<\/em><\/strong>0<\/sub>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 <\/strong>key(P<\/em><\/strong>0<\/strong><\/sub>)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0lock\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0key(P<\/em><\/strong>1<\/strong>)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 P<\/em><\/strong>1<\/strong><\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
    <\/td>\n<\/td>\nfalse<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\ntrue<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    Swap<\/td>\nfalse<\/td>\ntrue<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\ntrue<\/td>\n<\/td>\n<\/tr>\n
    In CS<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\nSwap<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\ntrue<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\nwaits<\/td>\n<\/tr>\n
    Out of CS<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\nfalse<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\ntrue<\/td>\nfalse<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\nIn CS<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

     <\/p>\n

    Let two processes <\/span>P<\/em>0 and <\/span>P<\/em>1 compete to enter their respective critical sections. Each of the two processes has its own local key variable. Initially, lock is false. The key variables of each of the two processes are true initially. <\/span>P<\/em>0 wants to enter critical section first. <\/span>P<\/em>0 executes Swap(key(<\/span>P<\/em>0), lock). This will make the value of lock true and the value of key false. As key becomes false, <\/span>P<\/em>0 comes out of the while loop and enters its critical section. Suppose, <\/span>P<\/em>1 wants to enter its critical section when <\/span>P<\/em>0 is in its critical section. <\/span>P<\/em>1 sets the value of its key to true. <\/span>P<\/em>1 executes Swap(key(<\/span>P<\/em>1), lock). Since the value of lock is currently true, the value of key also continues to be true. <\/span>P<\/em>1 continues to execute in the while loop. When <\/span>P<\/em>0 comes out of its critical section, it changes the value of lock to false. Now <\/span>P<\/em>1, executing in the while loop, swaps lock and its key. <\/span>P<\/em>1\u2019s key becomes false and <\/span>P<\/em>1 comes out of the while loop and enters critical section. Thus, it is seen that <\/span>P<\/em>1 is not allowed to enter its critical section when <\/span>P<\/em>0 is in its critical section. When one process is in its critical section, the value of lock is true and no other process can enter its critical section. Thus, mutual exclusion is satisfied.<\/span><\/p>\n

    \n

     <\/p>\n

    13.2.3 Swap \u2013 Bounded Waiting<\/strong><\/p>\n

     <\/p>\n

    We now see if this algorithm satisfies the bounded waiting requirement.<\/p>\n

     <\/p>\n

    \u00a0 \u00a0 \u00a0 P<\/em><\/strong>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 <\/strong>key(P<\/em><\/strong>0<\/strong>)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0lock\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0key(P<\/em><\/strong>1<\/strong>)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 P<\/em><\/strong>1<\/strong><\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
    <\/td>\n<\/td>\nfalse<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\ntrue<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    Swap<\/td>\nfalse<\/td>\ntrue<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\ntrue<\/td>\n<\/td>\n<\/tr>\n
    In CS<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\nSwap<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\ntrue<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\nWaits<\/td>\n<\/tr>\n
    Out of CS<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    Swap<\/td>\nfalse<\/td>\ntrue<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    In CS<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\nStill waits<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

     <\/p>\n

    Let P<\/em>0 and P<\/em>1 be two processes that are competing to access their respective critical sections. Initially, lock is false. Initially, the key variable of each of the two processes is true. P<\/em>0 wants to enter its critical section first. P<\/em>0 executes Swap(key(P<\/em>0), lock). This makes the value of lock true and the value of key false. As key becomes false, P<\/em>0 comes out of the while loop and enters its critical section. Let P<\/em>1 want to enter its critical section when P<\/em>0 is in its critical section. P<\/em>1 sets the value of its key to true. P<\/em>1 executes Swap(key(P<\/em>1), lock). Since the value of lock is currently true, the value of key also continues to be true. P<\/em>1\u00a0 continues to execute in the while loop. When P<\/em>0 comes out of its critical section, it changes the value of lock to false. Let P<\/em>0 continue to use the CPU without context switch. Say, P<\/em>0 wants to enter its critical section again. Since the value of lock is currently false, P<\/em>0 can enter its critical section again. Process P<\/em>1 continues to wait. Since there was no context switch after P<\/em>0 came out of its critical section and P<\/em>0 changed lock to true, P<\/em>1 could not come out of the while loop. Thus, even though P<\/em>1 had requested to enter its critical section, P<\/em>0 is allowed to enter its critical section again and again. Therefore, the bounded waiting requirement is not satisfied.<\/p>\n

     <\/p>\n

    Thus, it is seen that this algorithm does not satisfy the bounded waiting requirement, though it satisfies the mutual exclusion requirement.<\/p>\n

     <\/p>\n

    13.3\u00a0 TestandSet – Bounded-Waiting – Mutual Exclusion\u00a0<\/strong><\/p>\n

     <\/p>\n

    The algorithm given below makes use of the TestAndSet instruction and satisfies all the three requirements for a solution to the critical section problem. This is also a solution when there are n <\/em>processes.<\/p>\n

     <\/p>\n

    The shared variables used in the algorithm are as follows:<\/p>\n

     <\/p>\n

    boolean waiting[n];\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/\/initially false <\/strong><\/p>\n

    boolean lock\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 \/\/initially false\u00a0<\/strong><\/p>\n

     <\/p>\n

    The algorithm for process P<\/em>i is given below:<\/p>\n

    do {<\/p>\n

    waiting[i] = TRUE; key = TRUE;<\/span><\/p>\n

    while (waiting[i] && key) \u00a0key = TestAndSet(lock); <\/span><\/p>\n

    waiting[i] = FALSE;<\/span><\/p>\n

    \/\/ critical section j = (i + 1) % n;<\/span><\/p>\n

    while ((j != i) && !waiting[j])\u00a0\u00a0\u00a0\u00a0 j = (j + 1) % n;<\/span><\/p>\n

    if (j == i)<\/span><\/p>\n

    lock = FALSE;<\/span><\/p>\n

    else<\/span><\/p>\n

    waiting[j] = FALSE;<\/span><\/p>\n

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

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

    \n

     <\/p>\n

    The algorithm given above is for process P<\/em>i. waiting <\/em>is an array with \u2018n<\/em>\u2019 elements, where n <\/em>is the number of processes competing to enter their respective critical sections. lock <\/em>is a Boolean variable. Each line in the algorithm is explained below:<\/p>\n

     <\/p>\n

    waiting[i] = TRUE;<\/p>\n

     <\/p>\n

    Process P<\/em>i before checking to enter its critical section sets the value of waiting[i] to true.<\/p>\n

     <\/p>\n

    key = TRUE;<\/p>\n

     <\/p>\n

    key is a variable local to process P<\/em>i. It is set to true.<\/p>\n

     <\/p>\n

    while (waiting[i] && key)\u00a0\u00a0 key = TestAndSet(lock);<\/p>\n

     <\/p>\n

    For process P<\/em>i, waiting[i] and key are true, initially. Therefore, the condition (waiting[i] && key<\/em>) is true. Since this condition is true, P<\/em>i executes TestAndSet(lock). Initially, lock is false. Since lock is false, TestAndSet(lock) returns false and the value of lock is changed to true. The return value is assigned to key. Thus, key is now assigned the value \u2013 false. Now, the condition (waiting[i] && key<\/em>) becomes false. Process P<\/em>i comes out of the while loop.<\/p>\n

     <\/p>\n

    If lock is true, TestAndSet(lock) returns true. Therefore, key is assigned true. The condition in the while loop remains true. Process P<\/em>i continues to execute in while loop.<\/p>\n

     <\/p>\n

    waiting[i] = FALSE;After coming out of the while loop, P<\/em>i changes waiting[i] to false and enters its critical section.<\/p>\n

     <\/p>\n

    Process P<\/em>i, after coming out of its critical section, checks if any other process is waiting to enter its critical section. If any other process is waiting to enter its critical section, P<\/em>i changes the value of waiting <\/em>of that process to false. Else, changes the value of lock to false. Changing the value of waiting <\/em>of a process to false will make that waiting process to come out of the while loop and enter its critical section. If no process is waiting, the value of lock is changed to false. This paves the way for any other process wanting to enter its critical section, to enter its critical section in future.<\/p>\n

     <\/p>\n

    j = (i + 1) % n;<\/span><\/p>\n

     <\/p>\n

    The next process <\/span>P<\/em>j to be checked is found. j is found by incrementing i.<\/span><\/p>\n

     <\/p>\n

    while ((j != i) && !waiting[j])\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 j = (j + 1) % n;<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    P<\/em>i checks if waiting[j] is true, for every other process j. If true, P<\/em>i comes out of its while loop. This means that there is another process j in its entry section waiting to enter its critical section. If waiting[j] is not true, process j is not in its entry section. Therefore, the other processes are checked one after the other. When j becomes equal to i, it means that all other processes have been checked already. There is no other process waiting in its entry section.<\/p>\n

     <\/p>\n

    if (j == i)<\/strong><\/p>\n

    lock = FALSE;<\/strong><\/p>\n

    else<\/strong><\/p>\n

    w<\/strong>a<\/strong>iting[j] = FALSE;<\/strong><\/p>\n<\/div>\n

    \n

     <\/p>\n

    If j==i, there is no other process in its entry section and lock is made false. Else, waiting[j] (j is the process waiting in its entry section) is made false.<\/p>\n

     <\/p>\n

    13.3.1\u00a0 Mutual exclusion\u00a0<\/strong><\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n
    w<\/strong>a<\/strong>iting[0]<\/strong><\/td>\nP<\/em><\/strong>0<\/strong><\/td>\nkey(0)<\/strong><\/td>\nlock<\/strong><\/td>\nkey(1)<\/strong><\/td>\nP<\/em><\/strong>1<\/strong><\/td>\nw<\/strong>a<\/strong>iting[1]<\/strong><\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\nfalse<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    false<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nfalse<\/td>\n<\/tr>\n
    true<\/td>\n<\/td>\ntrue<\/td>\n<\/td>\ntrue<\/td>\n<\/td>\ntrue<\/td>\n<\/tr>\n
    <\/td>\nTestAndSet(lock)<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\nfalse<\/td>\ntrue<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    false<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\nEnters CS<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nTestAndSet(lock)<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\nTrue<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nWaits<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

     <\/p>\n

    The sequence given above shows how the algorithm satisfies the mutual exclusion requirement. Let P<\/em>0 and P<\/em>1 be the two processes competing to enter their respective critical sections. Initially, lock, waiting[0] and waiting[1] are false. P<\/em>0 changes waiting[0] and its local variable key(0) to true. P<\/em>0 then executes TestAndSet(lock). Since lock is false, TestAndSet(lock) returns false and the value is assigned to key(0). The value of lock is changed to true. Since key(0) becomes false, P<\/em>0 comes out of its while loop, changes waiting[0] to false and enters its critical section. While P<\/em>0 is in its critical section, let P<\/em>1 want to enter its critical section. P<\/em>1 changes waiting[1] and its local variable key(1) to true. P<\/em>0 then executes TestAndSet(lock). Since lock is true, TestAndSet(lock) returns true and the value \u2018true\u2019 is assigned to key(0). Since key(0) is true, P<\/em>1 continues to execute in its while loop. Thus, when one process is in its critical section, the other processes are not allowed to enter their respective critical sections. Thus,\u00a0mutual exclusion is satisfied.<\/span><\/p>\n<\/div>\n

     <\/p>\n

    13.3.2\u00a0 Progress \u2013 Scenario 1<\/strong><\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
    w<\/strong>a<\/strong>iting[0]<\/strong><\/td>\nP<\/em><\/strong>0<\/strong><\/sub><\/td>\nkey(0)<\/strong><\/td>\nlock<\/strong><\/td>\nkey(1)<\/strong><\/td>\nP<\/em><\/strong>1<\/strong><\/sub><\/td>\nw<\/strong>a<\/strong>iting[1]<\/strong><\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\nfalse<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    false<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nfalse<\/td>\n<\/tr>\n
    true<\/td>\n<\/td>\ntrue<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\ntrue<\/td>\n<\/td>\ntrue<\/td>\n<\/tr>\n
    <\/td>\nTestAndSet(lock)<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\nfalse<\/td>\ntrue<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    false<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\nEnters CS<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nTestAndSet(lock)<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\nTrue<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nWaits<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\nOut of CS<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nfalse<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nEnters CS<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

     <\/p>\n

    The sequence given above, shows how the algorithm satisfies the progress requirement. Let P<\/em>0 and P<\/em>1 be the two processes competing to enter their respective critical sections. Initially, lock, waiting[0] and waiting[1] are false. P<\/em>0 changes waiting[0] and its local variable key(0) to true. Now, there is a context switch and P<\/em>1 changes waiting[1] and key(1) to true. Again, there is a context switch and P<\/em>0 executes TestAndSet(lock). Since lock is false, TestAndSet(lock) returns false and the value \u2018false\u2019 is assigned to key(0). The value of lock is changed to true. Since key(0) becomes false, P<\/em>0 comes out of while loop, changes waiting[0] to false and enters its critical section. Now, if P<\/em>1 gets the CPU, it executes TestAndSet(lock). Since lock is true, TestAndSet(lock) returns true and the value \u2018true\u2019 is assigned to key(0). Since key(0) is true, P<\/em>1 continues to execute in its while loop. When P<\/em>0 comes out of its critical section, it checks if the waiting value of any other process is true. This checking is done one process after the other. In this example, since there are only two processes, the waiting status of P<\/em>1 is checked. Since waiting[1] is true, !waiting[1] is false. This makes the condition in the while loop false for P<\/em>0. P<\/em>0 comes out of the while loop and changes waiting[1] to false. When waiting[1] becomes false, P<\/em>1 comes out of the while loop while (waiting[i] && key) key = TestAndSet(lock);<\/strong>. P<\/em>1 enters its critical section. Hence, there is progress.<\/p>\n

     <\/p>\n

    13.3.3 Progress \u2013 Scenario 2<\/strong><\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
    w<\/strong>a<\/strong>iting[0]<\/strong><\/td>\nP<\/em><\/strong>0<\/strong><\/td>\nkey(0)<\/strong><\/td>\nlock<\/strong><\/td>\nkey(1)<\/strong><\/td>\nP<\/em><\/strong>1<\/strong><\/td>\nw<\/strong>a<\/strong>iting[1]<\/strong><\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\nfalse<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    false<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nfalse<\/td>\n<\/tr>\n
    true<\/td>\n<\/td>\ntrue<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\nTestAndSet(lock)<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\nfalse<\/td>\ntrue<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    false<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\nEnters CS<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\nOut of CS<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\nNo other process is waiting<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

     <\/p>\n

    Another sequence of execution to show that progress is satisfied is given above. Let P<\/em>0 and P<\/em>1 be the two processes competing to enter their respective critical sections. Initially, lock, waiting[0] and waiting[1] are false. P<\/em>0 changes waiting[0] and its local variable key(0) to true. Since lock is false, TestAndSet(lock) returns false and the value is assigned to key(0). The value of lock is changed to true. Since key(0) becomes false, P<\/em>0\u00a0 comes out of the while loop, changes waiting[0] to false and enters its critical section. When P<\/em>0 comes out of its critical section, it checks if the waiting value of any other process is true. This checking is done one process after the other. In this example, since there are only two processes, the waiting status of P<\/em>1 is checked. Since waiting[1] is false, !waiting[1] becomes true. This makes the condition in the while loop true for P<\/em>0. So, P<\/em>0 executes j=j +1 % n. j was 1 earlier. Now, it becomes 0. Since j becomes equal to i, P<\/em>0 comes out of the while loop and changes lock to false. Since lock is changed to false, any process can enter its critical section in future.<\/p>\n

     <\/p>\n

    13.3.4\u00a0 Bounded waiting:<\/strong><\/p>\n

     <\/p>\n

    After a process comes out of its critical section, it checks if the next process is waiting to enter its critical section. Similarly, every other process is checked. Only if no other process is in the entry section, the value of lock is changed to false. Thus, when there are n <\/em>processes, a process may have to wait for n<\/em>\u20131 critical section executions before its turn to enter critical section. Thus, the bounded waiting requirement is satisfied.<\/p>\n

     <\/p>\n

    13.4 Summary<\/strong><\/p>\n

     <\/p>\n

    In this module, we first learned a solution to the critical section problem using the Swap instruction. But the solution did not satisfy the bounded waiting requirement. Next, we learned a solution to the critical section problem using the TestAndSet instruction that 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<\/ol>\n","protected":false},"author":4,"menu_order":10,"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-136","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\/136","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\/136\/revisions"}],"predecessor-version":[{"id":415,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/136\/revisions\/415"}],"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\/136\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/media?parent=136"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapter-type?post=136"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/contributor?post=136"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/license?post=136"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}