CS604 - Operating Systems - Lecture Handout 20

User Rating:  / 0
PoorBest 

Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems

Summary

  • 2-Process Critical Section Problem (continued)
  • n-Process Critical Section Problem
  • The Bakery Algorithm

2-Process Critical Section Problem (continued)

We discussed two solutions for the 2-process critical section problem in lecture 19 but both were not acceptable because they did not satisfy the progress condition. Here is a good solution for the critical section problem that satisfies all three requirements of a good solution.

Algorithm 3

The processes share two variables:

boolean flag[2];
int turn;

The boolean array of ‘flag’ is initialized to false, whereas ‘turn’ maybe 0 or 1. The structure of the process is as follows:

Algorithm 3

To enter its critical section, Pi sets flag[i] to true, and sets ‘turn’ to j, asserting that if the other process wishes to enter its critical section, it may do so. If both try to enter at the same time, they will attempt to set ‘turn’ to i and j. However, only one of these assignments will last, the other will occur but be overwritten instantly. Hence, the eventual value of ‘turn’ will decide which process gets to enter its critical section.
To prove mutual exclusion, note that Pi enters its critical section only if either flag[j]=false or turn=i. Also, if both processes were executing in their critical sections at the same time, then flag[0]= = flag[1]= = true. These two observations suggest that P0 and P1 could not have found both conditions in the while statement true at the same time, since the value of ‘turn’ can either be 0 or 1. Hence only one process say P0 must have successfully exited the while statement. Hence mutual exclusion is preserved.
To prove bounded wait and progress requirements, we note that a process Pi can be prevented the critical section only if it is stuck in the while loop with the condition flag[j]= =true and turn=j. If Pj is not ready to enter the critical section, then flag[j]=flase and Pi can enter its critical section. If Pj has set flag[j]=true and is also executing its while
statement then either turn=i or turn=j. If turn=i then Pi enters its critical section, otherwise Pj. However, whenever a process finishes executing in its critical section, lets assume Pj, it resets flag[j] to false allowing Pi to enter its critical section. If Pj resets flag[j]=true, then it must also set ‘turn’ to i, and since Pi does not change the value of ‘turn’ while executing in its while statement, Pi will enter its critical section (progress) after at most one entry by Pj (bounded waiting).

N-Process Critical Section Problem

In this section we extend the critical section problem of two processes to include n processes. Consider a system of n processes (Po, P1 …… Pn-1). Each process has a segment of code called a critical section in which the process may be changing common variables, updating a table, writing a file and so on. The important feature of the system in that, when one process enters its critical section, no other process is allowed to execute in its critical section. Thus the execution of critical sections by the processes is mutually exclusive in time. The critical section problem is to design a protocol to serialize executions of critical sections. Each process must request permission to enter its critical
section. Many solutions are available in the literature to solve the N-process critical section problem. We will discuss a simple and elegant solution, known as the Bakery algorithm.

The Bakery Algorithm

The bakery algorithm is due to Leslie Lamport and is based on a scheduling algorithm commonly used in bakeries, ice-cream stores, and other locations where order must be made out of chaos. On entering the store, each customer receives a number. The customer with the lowest number is served next. Before entering its critical section, process
receives a ticket number. Holder of the smallest ticket number enters its critical section.
Unfortunately, the bakery algorithm cannot guarantee that two processes (customers) will not receive the same number. In the case of a tie, the process with the lowest ID is served first. If processes Pi and Pj receive the same number, if i < j, then Pi is served first; else Pj is served first. The ticket numbering scheme always generates numbers in the increasing order of enumeration; i.e., 1, 2, 3, 4, 5 ...

Since process names are unique and totally ordered, our algorithm is completely deterministic. The common data structures are:

boolean choosing [n];
int number[n];

Initially these data structures are initialized to false and 0, respectively. The following notation is defined for convenience:

  • (ticket #, process id #)
  • (a,b) < (c,d) if a<c or if a= =c and b<d.
  • notation is defined for convenience

The structure of process Pi used in the bakery algorithm is as follows:

structure of process Pi

To prove that the bakery algorithm is correct, we need to first show that if Pi is in its critical section and Pk has already chosen its number k!=0, then ((number [i],i) < (number[k],k)). Consider Pi in its critical section and Pk trying to enter its critical section.
When process Pk executes the second while statement for j= = i it finds that,

  • number[i] != 0
  • (number[i],i) < (number[k],k)

Thus it keeps looping in the while statement until Pi leaves the Pi critical section. Hence mutual exclusion is preserved. For progress and bounded wait we observe that the processes enter their critical section on a first come first serve basis.
Following is an example of how the Bakery algorithm works. In the first table, we show that there are five processes, P0 through P4. P1’s number is 0 because it is not interested in getting into its critical section at this time. All other processes are interested in entering their critical sections and have chosen non-zero numbers by using the max() function in their entry sections.

Bakery algorithm works

The following table shows the status of all the processes as they execute the ‘for’ loops in their entry sections. The gray cells show processes waiting in the second while loops in their entry sections. The table shows that P0 never waits for any process and is, therefore, the first process to enter its critical section, while all other processes wait in
their second while loops for j = = 0, indicating that they are waiting for P0 to get out of its critical section and then they would make progress (i.e., they will get out the while loop, increment j by one, and continue their execution).
You can make the following observations by following the Bakery algorithm closely with the help of this table:

  • P1 not interested to get into its critical section ⇒ number[1] is 0
  • P2, P3, and P4 wait for P0
  • P0 gets into its CS, get out, and sets its number to 0
  • P3 get into its CS and P2 and P4 wait for it to get out of its CS
  • P2 gets into its CS and P4 waits for it to get out
  • P4 gets into its CS
  • Sequence of execution of processes: <P0, P3, P2, P4>

Bakery algorithm closely