/ 0
Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems
Summary
- Hardware based solutions
- Semaphores
- Semaphore based solutions for the critical section problem
Hardware Solutions
In lecture 21 we started discussing the hardware solutions for the critical section problem.
We discussed two possible solutions but realized that whereas both solutions satisfied the
mutual exclusion and bounded waiting conditions, neither satisfied the progress
condition. We now describe a solution that satisfies all three requirements of a solution to
the critical section problem.
Algorithm 3
In this algorithm, we combine the ideas of the first two algorithms. The common data structures used by a cooperating process are:
The structure of process Pi is:
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
TestAndSet is executed. The first process to execute the TestAndSet instruction will find
key= =false; all others must wait. The variable waiting[i] can only become false if
another process leaves its critical section; only one waiting[i] is set to false, maintaining
the mutual exclusion requirement.
To prove 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.
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, 1, …, i-1). It designates the first process it sees that is in its entry section with
waiting[j]=true as the next one to enter its critical section. Any process waiting to do so
will enter its critical section within n-1 turns.
Semaphores
Hardware solutions to synchronization problems are not easy to generalize to more complex problems. To overcome this difficulty we can use a synchronization tool called a semaphore. A semaphore S is an integer variable that, apart from initialization is accessible only through two standard atomic operations: wait and signal. These operations were originally termed P (for wait) and V (for signal). The classical definitions of wait and signal are:
Modifications to the integer value of the semaphore in the wait and signal operations
must be executed indivisibly. That is, when one process is updating the value of a
semaphore, other processes cannot simultaneously modify that same semaphore value. In
addition, in the case of the wait(S), the testing of the integer value of S (S<=0) and its
possible modification (S--) must also be executed without interruption.
We can use semaphores to deal with the n-process critical section problem. The n
processes share a semaphore, mutex (standing for mutual exclusion) initialized to 1. Each
process Pi is organized as follows:
As was the case with the hardware-based solutions, this is not a good solution
because even though it satisfies mutual exclusion and progress, it does not satisfy
bounded wait.
In a uni-processor environment, to ensure atomic execution, while executing wait and
signal, interrupts can be disabled. In case of a multi-processor environment, to ensure
atomic execution is one can lock the data bus, or use a soft solution such as the Bakery
algorithm.
The main disadvantage of the semaphore discussed in the previous section 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 entry code. 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
may be able to use productively. This type of semaphore is also called a spinlock
(because the process spins while waiting for the lock). Spinlocks are useful in
multiprocessor systems. The advantage of a spinlock is that no context switch is required
when a process must wait on a lock, and a context switch may take considerable time.
This is, spinlocks are useful when they are expected to be held for short times. The
definition of semaphore should be modified to eliminate busy waiting. We will discuss
the modified definition of semaphore in the next lecture.
Google +