Some processes running in operating systems share resources. For two given processes, one reading data and one writing data
from the same memory location, process communication and synchronisation ensures orderly execution of these processes while
maintaining data consistency. Below is a discussion of various solutions to design issues associated with process communication
and synchronisation. Figure 1 shows a comparison of different synchronisation examples on different platforms.
Producer Consumer Problem ensures that the producer does not add data when the buffer is full and the consumer should not
take data when the buffer is empty. There are a number of software solutions to this problem:
? Semaphores – a variable or abstract data type (ADT) used to control access to a common resource in a concurrent system such
as a multiprogramming operating system.
? Monitors – this is a synchronisation construct that allows threads to have mutual exclusion and the ability to wait for a
condition to become true.
? Atomic transactions – this avoids atomic read and write access to shared variables, as each of the two count variables is
updated only by a single thread; these variables stay incremented so the relation remains correct when their values wrap
around on an integer overflow.
Critical-Section (CS) Problem – for a section of code, common to cooperating processes in which the processes may be
accessing common variables; the CS contains: an entry section code requesting entry into the CS; the critical section code in
which only one process can execute at any one time; exit section the end of the CS, releasing or allowing others in; remainder
section rest of the code after theCS. The CS must follow these three rules:
? Mutual Exclusion – only one process can execute in the critical section at a time.
? Progress – if no process is in the CS and another wishes to enter, the process selected to enter must be determined in a finite
amount of time.
? Bounded Wait – all requesters must eventually be let into the critical section.
Peterson’s Solution this is an algorithm with a bounded waiting for a set of processes which need to enter the CS. This is
appropriate for two processes which share two data items, executing critical and remainder sections. A flag array is maintained
which is by default false. Whenever a process enters the CS, its flag is set to true. For a process’ flag which wants to enter is set to
true. The turn variable is used to indicate the process exiting the CS.
Hardware can be used to resolve CS problems, however, these are not as easily implemented as software solutions:
? Uniprocessors disable interrupts while a process is using the CS; though this is a disadvantage in multiprocessor systems.
? Locking a process entering the CS and releasing it after leaving; this prevents multiple processes entering the CS.
? Atomic hardware instructions (non-interruptible instructions) in modern machines. While being carried out, other processes
cannot read or write until the atomic instruction has completed; these must complete or not occur.
Mutex locks are a software based solution. In this approach, the entry section of the code, a lock is acquired over the critical
resources modified and used inside the CS and in the exit section that lock is released. As the resource is locked while a process
executes its CS no other process can access it.
Semaphores are a more robust alternative to mutual exclusions, these are integer variables for which two (atomic) operations are
defined: wait and signal . The variable-changing steps must be indivisible. For the wait operation when the test proves false there
should be no interrupts before S is decremented. It is ok, however, for the busy loop to be interrupted when the test is true; this
prevents the system from hanging forever. Semaphores are mainly of two types: binary and counting .
Deadlock – when multiple processes are blocked, waiting for a resource that can only be freed by another (blocked) processes.
Starvation – when one or more processes gets blocked forever and never get a chance to take their turn in the CS. For example, in
the semaphores above, we did not specify the algorithms for adding processes to the waiting queue in the semaphores in the wait()
call, or selecting one to be removed from the queue in the signal() call. If the method chosen is a FIFO queue, then every process
will eventually get their turn, but if a LIFO queue is implemented instead, then the first process to start waiting could starve.
Bounded-Buffer Problem is a generalisation of the producer-consumer problem. Access is controlled to a shared group of buffers
of a limited size. In this solution, the two counting semaphores full and empty keep track of the current number of full and empty
buffers respectively (and initialised to 0 and N respectively). The binary semaphore mutex controls access to the CS; producer and
consumer processes nearly identical – producer thought of as producing full buffers, and consumer producing empty buffers.
Readers-Writers Problem similar to the Producer-Consumer problem except can have many concurrent readers and one
exclusive writer; locks are shared (for readers) and exclusive (for writer); two possible (contradictory) guidelines: no reader kept
waiting unless a writer holds the block (readers have precedence); if a writer is waiting for access, no new reader gains access
(writer has precedence).
Dining Philosophers Problem five philosophers sitting around a table; each has a plate with a chopstick to the right. There will
be a deadlock and starvation because of the limited number of chopsticks. Solutions: allowing only 4 philosophers to be hungry at
a time; allowing pickup only if both chopsticks are available (used in CS); odd number of philosophers always picks up left
chopstick first, even number of philosophers always picks up right chopstick first. Could use a set of five semaphores and have
each hungry philosopher first wait on their left chopstick then wait on their right chopstick.
? Reader writer locks
? Interrupt masks
? Condition variables
? Adaptive mutexes
? Reader-writer locks
Figure 1: Synchronisation examples on different operating system platforms