Chapter 5:
Remember:
• Multiprocessing: the management of multiple processes within a multiprocessor
• Multiprogramming: the management of multiple processes within a uniprocessor system
• Distributed processing: the management of multiple processes executing on multiple,
distributed computer systems
• Overlapping: the execution of multiple tasks concurrently but not simultaneously
• Interleaving: the execution of multiple tasks simultaneously
Concurrency in 3 different contexts:
1. Multiple applications: invented to allow processing time to be shared among active
applications
2. Structured applications: extension of modular design and structured programming
3. Operating system structure: OS themselves implemented as a set of processes or threads
Difficulties of concurrency:
1. Sharing of global resources
2. Difficult for the OS to manage the allocation of resources optimally
3. Difficult to locate programming error as results are deterministic and reproducible
Terms:
• Atomic operation: a function or action implemented as a sequence of one or more
instructions that appears to be indivisible
o No other processes can see an intermediate state or interrupt the operation
o Sequence of instructions is guaranteed to execute as a group, or not execute at all,
having no visible effect on the system
o Guarantees isolation from concurrent processes
• Critical section: a section of code within a process that requires access to shared
resources, and that must not be executed while another process is in a corresponding
section of code
• Deadlock: a situation in which two or more processes are unable to proceed because ach is
waiting for one of the others to do something
• Livelock: a situation in which two or more processes continuously change their state in
response to changes in the other process(es) without doing any useful work
• Mutual exclusion: the requirement that when one process is in a critical section that access
shared resources, no other process may be in a critical section that accesses any of those
shared resources
• Race condition: a situation in which multiple threads or processes read and write a shared
data item, and the final result depends on the relative timing of their execution
• Starvation: a situation in which a runnable process is overlooked indefinitely by the
scheduler although it is able to proceed, it is never chosen.
Mutual exclusion approaches:
• Software Approaches:
o Dekker’s Algorithm
o Peterson’s Algorithm
• Hardware approaches:
o Interrupt disabling
o Special Machine Instructions
▪ Compare and swap instruction
▪ Exchange Instruction
• Semaphores
• Monitors
• Message Passing
Dekker’s Algorithm:
Peterson’s Algorithm:
Process Interaction
Requirements for mutual exclusion:
• One process at a time is allowed into its critical section, among all processes that have
critical sections for the same resource of shared object
• A process that halts in its critical section must do so without interfering with other processes
• It must not be possible for a process requiring access to a critical section to be delayed
indefinitely (no deadlock or starvation)
• When no process is in a critical section any process that requests entry to its critical section
must be permitted to enter without delay
• No assumptions are made about relative process speeds or number of processors
• A process remains inside its critical section for a finite time only
How can we satisfy these requirements:
• Option 1: leave the responsibility with the processes that wish to execute concurrently
• Option 2: use of special-purpose machine instructions
Interrupt Disabling:
While (true) {
/* disable interrupts */;
/* critical section */;
/* enable interrupts */;
/* remainder */;
Special Machine Instructions:
Advantages of machine instruction approach:
• Applicable to any number of processes on either single processor or multiple processor
sharing main memory
• Simple and therefore easy to verify
• Can be used to support multiple critical sections, each critical section can be defined by its
own variable
Disadvantages of machine instruction approach:
• Busy waiting is employed => while a process is waiting for access to its critical section it
continues to consume processor time
• Starvation is possible => selection of processes is arbitrary, thus c=some can be indefinitely
denied access
• Deadlock is possible
Semaphores:
Terms:
• Semaphore: A variable that has an integer value upon which only three operations are
defined
o a semaphore may be initialised to a nonnegative integer value
o semWait operation decrements the semaphore value
o semSignal operation increments the semaphore value
• Binary semaphore: a semaphore that only take on the values 0 and 1
• Mutex: similar to a binary semaphore, a key difference is that the process that locks the
mutex (sets value to 0) must be the same one to unlock it (set value to 1)
• Condition variable: a data type that is used to block a process or thread until a particular
condition is true
• Event flags: a memory word used a synchronisation mechanism
o Application code may associate a different event with each bit in a flag
o Thread can wait either for a single event or a combination of events by checking one
or multiple bits in the corresponding flag
o Thread is blocked until all of the required bits are set (AND) or until at least one of
the bits is set (OR)
• Mailboxes / messages: a mean for two processes to exchange information that may be
used for synchronization
• Spinlocks: mutual exclusion mechanism in which a process executes in an infinite loop
waiting for the value of a lock variable to indicate availability
The producer consumer problem:
• General statement:
o One or more producers are generating data and placing these in a buffer
o A single consumer is taking items out of the buffer one at a time
o Only one producer or consumer may access the buffer at any one time
• The problem: ensure that the producer won’t try to add data into the buffer if it is full, and
the consumer won’t try remove data from an empty buffer
Monitors:
A programming language construct that provides equivalent functionality to that of a semaphore
and is easier to control
Implemented in: Concurrent Pascal, Pascal-Plus, Modula-2, Modula-3, Jave
Characteristics of a monitor:
• The local data variables are accessible only by the monitor’s procedures and not by any
external procedure
• A process enters the monitor by invoking one of its procedures
• Only one process may be executing in the monitor at a time; any other processes that have
invoked the monitor are blocked, waiting for the monitor to become available
Supports synchronisation by use of condition variables that are contained within the monitor and
accessible only within the monitor:
• cwait (c) : suspends execution of the calling process on condition c
• csignal (c) : resumes execution of some process blocked after a cwait on the same
condition
Message Passing:
Has further advantage that it lends itself to the implementation in distributed systems as well as in
shared-memory multiprocessor and uniprocessor systems
Actual function is normally provided in the form of a pair of primitives:
send (destination, message)
receive (source, message)
Design Characteristics of Massage Systems for InterProcess Communication and
Synchronization:
• Synchronization:
o Send
▪ Blocking
▪ Nonblocking
o Receive
▪ Blocking
▪ Nonblocking
▪ Test for arrival
• Addressing:
o Direct:
▪ Send
▪ Receive
• Explicit
• Implicit
o Indirect
▪ Static
▪ Dynamic
▪ Ownership
• Format:
o Content
o Length
▪ Fixed
▪ Variable
• Queueing Discipline:
o FIFO
o Priority
The Readers / Writers Problem:
General statement: There is a data area shared among a number of processes. There are a
number of processes that only read the data area (readers) and a number that only write to the
data area (writers)
Conditions that must be satisfied:
• Any number of readers may simultaneously read the file
• Only one writer at a time may write to the file
• If a writer is writing to the file, no reader may read it