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
,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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller mpumi__tshabalala. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.70. You're not tied to anything after your purchase.
