Operating Systems: Chapter 5 to Chapter 9

Chapter 5: Part 1
Concurrency: Mutual Exclusion and Synchronization (Section5.1-5.3)

Multiple Processes
o OS design in concerned with management of processes and threads
o Multiprogramming
 Management of multiple processes within a uniprocessor system
o Multiprocessing
 Management of multiple processes within a multiprocessor
o Distributed Processing
 Management of multiple processes executing on multiple, distributed
computer systems
 Example: recent proliferation of cluster

Concurrency in 3 different contexts
1. Multiple applications
o Purpose: allow processing time to be shared among active applications
2. Structured applications
o Extension of modular design and structures programming
3. Operating system structure (where the need arises)
o OS implemented as a set of processes/threads




Atomic operation, critical section, deadlock, livelock, mutual exclusion, race condition, starvation

,Mutual Exclusion: Software Approaches
o Software approaches can be implemented for concurrent processes that execute on a single-
processor/multiprocessor machine which shared main memory
o These approaches assume mutual exclusion at memory access level
o Simultaneous accesses (reading/writing) to the same location in memory is
serialized by some sort of memory arbiter, although the other of access granting in
not specified ahead of time
o No other support in hardware, OS or programming language is assumed
o Dijkstra (Computer Scientist) reported an algorithm for mutual exclusion for 2 processes,
designed by the Dutch mathematician Dekker
o Solutions were developed in stages
o Advantage: illustrating many common bugs encountered in developing concurrent
programs
o FLAWS




o Attempt1 – not suitable for concurrent
 P1 forced to wait until P0 requires access
 If 1 process fails, the others are permanently blocked
 Stored name when we need info




o Attemp2 – does not guarantee mutual exclusion
 Use Boolean vector flag – to keep track of process states and not block
others if 1 fails
 Flag[0] – process 0
 can check content of other process but can’t alter it
 false = proceed to critical section by setting itself to be true
 once left the critical section, set flag to false
 Possible to have 2 processes set as true (violates intent)
 if fails after set to true (just about enter critical section), then other
processes will be permanently blocked

, o Attempt3
 Once P0 has set flag to true, then P1 can’t entre critical section until the
other has left its critical section and set flag to false
 Guarantee mutual exclusion
 Problem: if both set to true at same time, then each process will block each
other, infinite loop – deadlock




o Attempt4
 Close but still flawed
 Mutual exclusion is guaranteed
 If both processes set their flags to be true at the same time, they check each
other in the while loop and each processes sets its flag to false. This is
happening SIMULTANEOUSLY (livelock – both carrying a meaningless
process)
 They are both asking each other to go through the door, persistently
o Correct
o Checks to see which of the 2 processes that have set themselves to true, has the most
insistent need to entre its critical section
o Make use of turn variable to say whether or not it’s the processes
turn to go
 0 = go
 1 = no
o Most correct
 It is clear to see that
it allows for mutual
exclusion
 It caters for all kinds
of locking
 Can be applied to
>2 processes

, Principles of concurrency
o Interleaving and overlapping
o Viewed as an example of concurrent processing
o Present the same problems
o Uniprocessor – relative speed of execution of processes can’t be predicted
o Depends on activities of other processes
o Way OS handles interrupts
o Scheduling policies of OS

Difficulty of concurrency
o Sharing of global resources
o Diff for OS to manage the allocation of resources optimally
o Diff to locate programming errors as results are not deterministic and reproducible

Race condition
o Occurs when multiple processes or threads read and write data items
o So that, the final result depends on the order of execution
o “loser” of the race is the process that updates last and will determine the final value
of the variable
o Example: varA gets a value from P1 but then P2 gives it a value, the loser (P2) will
determine the value of varA

Operating System concerns
o Design and management issues raised by existence of concurrency
o OS must:
o Be able to keep track of various processes
o Allocate and de-allocate resources for each active process
o Protect the data and physical resources of each process against unintended
interference by other processes
o Functioning of a process, and the output it produces, must be independent of the
speed at which its execution is carried out relative to the speed of other concurrent
processes




Process interaction:
Processes unaware, indirectly aware, and directly aware of each other