In the name of God
University of UAJ&K
neelum campus
Introduction to
Bakery Algorithm
By:
Mehdi Hussain # 36
Khizar Hayyat # 25
Anees Mehdi # 35
Supervisor :
Prof. [Link].
Spring 2017
Class presentation for the course: “ Operating System”
All the materials are copy rights of their respective authors as listed in references.
Contants:
Critical Section
Hardware Requirements for Bakery Algorithm
Software Requirements for Bakery Algorithm
Introduction to Bakery Algorithm
Bakery Algorithm Notations
Bakery Algorithm Data Structure
2
CRITICAL SECTION :
Critical section is a code segment that accesses
shared variables and has to be executed an
atomic action.
Only one process must be executing its critical
section at a given time.
3
CRITICAL SECTION Example :
Do
{
Entry section
Critical section
Exit section
Remainder-section
}
While (true)
4
CRITICAL SECTION Solutions Criteria:
[Link] exclusion:
Only one process should
execute in its critical section.
[Link]:
If no process is executing in its
critical section and some process wish to
enter the critical section. Then only those
processes that are not executing in its
remainder section can participate.
5
CRITICAL SECTION Solutions Criteria:
[Link] waiting:
There is a limit on the
number of times that other process are
allowed to enter their critical section.
6
Hardware Requirements for Bakery Algorithm
•Computers (Laptop ) recent version.
•Ram 4 GB require
•Hard Drive: 30 GB require
7
Software Requirements for Bakery Algorithm
•Operating System : Unix/linux
•Front End: Vmware Workstaion
•Back End :Fedora
•Language : C/C++
8
Introduction to Bakery Algorithm:
What is Bakery algorithm?
Devised by “Leslie Lamport”
Before entering its critical section, process
receives a ticket number. Holder of the
smallest ticket number enters the critical
section.
If processes Pi and Pj receive the same
number, if i < j, then Pi is served first; else Pj
is served first.
9
Bakery Algorithm
Pj
Pi
The ticket numbering scheme always generates numbers in the
increasing order of enumeration; i.e., 1, 2, 3, 4, 5 ..
10
Bakery Algorithm
Notations (ticket #, process id #)
(a,b) < (c,d) if a < c or
if a == c and b < d
max (a0,…, an-1) is a number, k, such
that k ≥ ai for i = 0, …, n–1
11
Bakery Algorithm
(Ticket # 25, p1) (Ticket # 24, p2)
in the above diagram we can see that there are two processes p1 and
[Link] process p2 will go to the critical section because it has lowest ticket
number.
12
Bakery Algorithm
(Ticket # 24, p1) (Ticket # 24, p2)
In the above diagram we can see that there are two processes p1 and
[Link] process p1 & p2 have same ticket number .Then process ID will be
checked. P1 process has lowest ID and will go to critical section first
13
Bakery Algorithm
Data Structures
boolean choosing[n];
int number[n];
These data structures are initialized
to false and 0, respectively
14
Bakery Algorithm
Structure of Pi
do {
choosing[i] = true;
number[i] = max(number[0],
number[1], …,
number [n – 1]) + 1;
choosing[i] = false;
15
Bakery Algorithm
for (j = 0; j < n; j++) {
while (choosing[j]) ;
while ( (number[j] != 0) &&
((number[j], j) < (number[i], i)) ) ;
}
Critical Section
16
Bakery Algorithm
number[i] = 0;
[Link]
remainder section
} while (1);
17
Bakery Algorithm
Process Number
P0 3
P1 0
P2 7
P3 4
P4 8
18
Bakery Algorithm
P0 P2 P3 P4
(3,0) < (3,0) (3,0) < (7,2) (3,0) < (4,3) (3,0) < (8,4)
Number[1] = 0 Number[1] = 0 Number[1] = 0 Number[1] = 0
(7,2) < (3,0) (7,2) < (7,2) (7,2) < (4,3) (7,2) < (8,4)
(4,3) < (3,0) (4,3) < (7,2) (4,3) < (4,3) (4,3) < (8,4)
(8,4) < (3,0) (8,4) < (7,2) (8,4) < (4,3) (8,4) < (8,4)
19
Bakery Algorithm
20
21
