/ 0
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:
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.
The structure of process Pi used in the bakery algorithm is as follows:
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.
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>
Google +