Module-3:
Operating Systems
BACSE106
LECTURE 3:
Process Synchronization-Bakery Algorithm, Synchronization Hardware
Course Instructor:-
Dr. [Link],
Professor,
SCOPE, VIT, Vellore.
Syllabus
Module:3 Process Synchronization 9 hours
IPC: Shared memory, message passing - Race condition – Critical
section problem - Peterson's solution – Bakery Algorithm - Hardware
synchronization: Test-and-Set, Swap - Mutex locks - Semaphores –
Classical synchronization problems: Bounded buffer, Readers-Writers,
Dining Philosophers – Monitors.
Bakery Algorithm in Process Synchronization
• The Bakery Algorithm is a simple process synchronization algorithm which
is used for preventing the problem of race conditions in critical sections of
the program or in an operating system.
• The bakery algorithm is a mutual exclusion algorithm. Hence, it allows
multiple processes to access the critical section of the program in a right
manner. This algorithm operates by giving a unique number to each
process that requests for accessing to the critical section.
• The bakery algorithm is based on the first come first serve property.
Therefore, the process with the smallest number is given priority to access
the critical section first. In case when two or more processes assigned the
same number, then the process with lowest process ID is given priority.
• In this algorithm, two arrays are maintained, one array is of flags to
indicate that a process is currently being requesting to enter to the critical
section, and another array is of numbers that indicate the order of
processes in which they have requested to enter the critical section.
• When a process requests to access the critical section, it first sets
its flag to true and then selects the largest number in the array
and increases it by one to obtain its own unique number. This
process then waits to get access to the critical section.
• When the process has entered the critical section, its flag is set
to false which indicates that this process is no longer need to
access the critical section. Hence, the process releases its
number so that the other processes can use it.
• Fundamentally, the bakery algorithm in process synchronization
ensures that no two processes can access the critical section
simultaneously. Although, the bakery algorithm is not free from
the problem of starvation, i.e. in this algorithm, a process may
have to wait for indefinitely long time if the assigned number is
too high.
Cont’d
The execution of the above code is explained below −
• Initially, the process sets its "choosing" variable to be true that indicates
that it is intended to enter the critical section
• After that it is assigned a highest number according to the other processes
• The "choosing" variable is then set to false which indicates that it has a
number assigned to it. This is the most important part of the bakery
algorithm.
• The objective of the first three lines of the code is that if a process is
modifying its number then at that time some other process should not be
allowed to check its old number which is now out of use
• After that the numbers of processes are checked where process with
lowest number or process ID gets inside the critical section.
Cont’d
Cont’d
Bakery algorithm
In this algorithm, two arrays are maintained, one array is of flags to indicate that a process is currently being requesting to
enter to the critical section, and another array is of numbers that indicate the order of processes in which they have
requested to enter the critical section.
Numerical: What order the processes enter into Critical section? Use
Bakery Algorithm
Key Rules of Bakery Algorithm:
•A process with number = 0 is not
competing for the critical section.
•Among competing processes, the
one with the lowest number enters
first.
•If two processes have the same
number, the one with the lower
process ID wins.
Cont’d
Cont’d
Synchronization Hardware
• We have just described one software-based solution to the critical-section
problem
• However, as mentioned, software-based solutions such as Peterson’s are not
guaranteed to work on modern computer architectures
• In the following discussions, we explore several more solutions to the critical-
section problem using techniques ranging from hardware to software-based APIs
available to both kernel developers and application programmers
• All these solutions are based on the premise of locking —that is, protecting
critical regions through the use of locks
• As we shall see, the designs of such locks can be quite sophisticated
• We start by presenting some simple hardware instructions that are available on
many systems and showing how they can be used effectively in solving the
critical-section problem
• Hardware features can make any programming task easier and improve system
efficiency
• The critical-section problem could be solved simply in a single-
processor environment if we could prevent interrupts from occurring
while a shared variable was being modified
• In this way, we could be sure that the current sequence of
instructions would be allowed to execute in order without
preemption
• No other instructions would be run, so no unexpected modifications
could be made to the shared variable. This is often the approach
taken by non-preemptive kernels
• Unfortunately, this solution is not as feasible in a multiprocessor environment.
• Disabling interrupts on a multiprocessor can be time consuming, since the
message is passed to all the processors
• This message passing delays entry into each critical section, and system efficiency
decreases
• Also consider the effect on a system’s clock if the clock is kept updated by
interrupts
• Many modern computer systems therefore provide special hardware
instructions that allow us either to test and modify the content of a word or to
swap the contents of two words atomically—that is, as one uninterruptible unit
• We can use these special instructions to solve the critical-section problem in a
relatively simple manner
• Rather than discussing one specific instruction for one specific machine, we
abstract the main concepts behind these types of instructions by describing the
test and set() and compare and swap() instructions
• The test and set() instruction can be defined as shown in Figure
• The important characteristic of this instruction is that it is executed
atomically
• Thus, if two test and set() instructions are executed simultaneously (each
on a different CPU), they will be executed sequentially in some arbitrary
order
• If the machine supports the test and set() instruction, then we can
implement mutual exclusion by declaring a boolean variable lock, initialized
to false
• The structure of process Pi is shown
• The compare and swap() instruction, in contrast to the test and set()
instruction, operates on three operands; it is defined in Figure
• The operand value is set to new value only if the expression (*value
== expected) is true
• Regardless, compare and swap() always returns the original value of
the variable value
• Like the test and set() instruction, compare and swap() is executed atomically
• Mutual exclusion can be provided as follows: a global variable (lock) is
declared and is initialized to 0
• The first process that invokes compare and swap() will set lock to 1
• It will then enter its critical section, because the original value of lock was
equal to the expected value of 0
• Subsequent calls to compare and swap() will not succeed, because lock now
is not equal to the expected value of 0
• When a process exits its critical section, it sets lock back to 0, which allows
another process to enter its critical section.
Cont’d
• Although these algorithms satisfy the mutual-exclusion requirement, they do
not satisfy the bounded-waiting requirement
• In Figure, we present another algorithm using the test and set() instruction
that satisfies all the critical-section requirements
• The common data structures are
• These data structures are initialized to false
• To prove that the mutual exclusion requirement is met, we note that process Pi
can enter its critical section only if either waiting[i] == false or key == false
• The value of key can become false only if the test and set() is executed
• The first process to execute the test and set() will find key == false; all others must
wait
• The variable waiting[i] can become false only if another process leaves its critical
section; only one waiting[i] is set to false, maintaining the mutual-exclusion
requirement
• To prove that the progress requirement is met, we note that the arguments
presented for mutual exclusion also apply here, since a process exiting the critical
section either sets lock to false or sets waiting[j] to false
• Both allow a process that is waiting to enter its critical section to proceed
Cont’d
• To prove that the bounded-waiting requirement is met, we note that,
when a process leaves its critical section, it scans the array waiting in
the cyclic ordering (i + 1, i + 2, ..., n − 1, 0, ..., i − 1)
• It designates the first process in this ordering that is in the entry
section (waiting[j] == true) as the next one to enter the critical section
• Any process waiting to enter its critical section will thus do so within n
− 1 turns
Mutex Locks
• The hardware-based solutions to the critical-section problem presented
are complicated as well as generally inaccessible to application
programmers
• Instead, operating-systems designers build software tools to solve the
critical-section problem
• The simplest of these tools is the mutex lock
• In fact, the term mutex is short for mutual exclusion
• Use the mutex lock to protect critical regions and thus prevent race
conditions
• That is, a process must acquire the lock before entering a critical section; it
releases the lock when it exits the critical section
• The acquire() function acquires the lock, and the release() function
releases the lock, as illustrated in Figure
• A mutex lock has a boolean variable available whose value indicates if
the lock is available or not
• If the lock is available, a call to acquire() succeeds, and the lock is
then considered unavailable
• A process that attempts to acquire an unavailable lock is blocked
until the lock is released
• The definition of acquire() is as follows:
Cont’d
• Calls to either acquire() or release() must be performed atomically.
• Thus, mutex locks are often implemented using one of the hardware mechanisms
described in Section
• The main disadvantage of the implementation given here is that it requires busy waiting
• While a process is in its critical section, any other process that tries to enter its critical
section must loop continuously in the call to acquire()
• In fact, this type of mutex lock is also called a spinlock because the process “spins” while
waiting for the lock to become available
• We see the same issue with the code examples illustrating the test and set() instruction
and the compare and swap() instruction
• This continual looping is clearly a problem in a real multiprogramming system, where a
single CPU is shared among many processes
• Busy waiting wastes CPU cycles that some other process might be able to use
productively
• Spinlocks do have an advantage, however, in that no context switch is
required when a process must wait on a lock, and a context switch
may take considerable time
• Thus, when locks are expected to be held for short times, spinlocks
are useful
• They are often employed on multiprocessor systems where one
thread can “spin” on one processor while another thread performs its
critical section on another processor