Post on 07-Apr-2018
8/6/2019 Tema 5.1 S5
1/42
Concurrency: Mutual Exclusion
and Synchronization
Chapter 5
8/6/2019 Tema 5.1 S5
2/42
Concurrency
Communication among processes
Sharing of and competing for resources
Synchronization of multiple processes Allocation of processor time
8/6/2019 Tema 5.1 S5
3/42
Concurrency
Multiple applications
Multiprogramming
Structured applicationApplication can be a set of concurrent
processes
Operating-system structure
Operating system is a set of processes or
threads
8/6/2019 Tema 5.1 S5
4/42
Difficulties with Concurrency
Sharing global resources
Management of allocation of resources
Programming errors difficult to locate
8/6/2019 Tema 5.1 S5
5/42
A Simple Example
void echo()
{
in = getchar();chout = in;
putchar(chout);
}
8/6/2019 Tema 5.1 S5
6/42
A Simple Example
Process P1 Process P2
. .
in = getchar(); .
. in = getchar();
. chout = in;
. putchar(chout);
chout = in; .
putchar(chout); .
8/6/2019 Tema 5.1 S5
7/42
8/6/2019 Tema 5.1 S5
8/42
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.
8/6/2019 Tema 5.1 S5
9/42
Operating System Concerns
Keep track of active processes
Allocate and deallocate resources
Processor time
Memory Files
I/O devices
Protect data and resources
Result of process must be independent of thespeed of execution of other concurrentprocesses
8/6/2019 Tema 5.1 S5
10/42
Process Interaction
Processes unaware of each other:
Independent process not intended to work
together. Competition.
Processes indirectly aware of each other:
Share access to some object, such as an I/O
buffer. Cooperation.
Process directly aware of each other:
Communicate each other by PID and are
designed to work jointly. Cooperation.
8/6/2019 Tema 5.1 S5
11/42
Competition Among
Processes forR
esources Three control problems:Mutual Exclusion
Critical sections
Only one program at a time is allowed in its critical
section
Example only one process at a time is allowed to
send command to the printer
DeadlockStarvation
8/6/2019 Tema 5.1 S5
12/42
Mutual exclusion
Requirement that when one process is in
a critical section that accesses shared
resources, no other process may be in a
critical section that accesses any of those
shared resources.
8/6/2019 Tema 5.1 S5
13/42
Critical section
Section of code within a process
Requires access to shared resources
May not be executed while anotherprocess is in a corresponding section of
code.
8/6/2019 Tema 5.1 S5
14/42
Deadlock
Two or more processes are unable to
proceed because each is waiting for one
of the others to do something.
8/6/2019 Tema 5.1 S5
15/42
Starvation
Runnable process is overlooked
indefinitely by the scheduler.
Although it is able to proceed, it is neverchosen.
8/6/2019 Tema 5.1 S5
16/42
Cooperation Among Processes
by Sharing Processes interact with other processeswithout being explicitly aware of them.
Writing must be mutually exclusive Critical sections are used to provide data
integrityentercritical()
exitcritical()
8/6/2019 Tema 5.1 S5
17/42
Cooperation Among Processes
by Communication Messages are passedMutual exclusion is not a control
requirement
Possible to have deadlockEach process waiting for a message from
the other process
Possible to have starvation
Two processes sending message to eachother while another process waits for amessage
8/6/2019 Tema 5.1 S5
18/42
Requirements for Mutual
Exclusion Only one process at a time is allowed inthe critical section for a resource
A process that halts in its non-criticalsection must do so without interfering
with other processes
No deadlock or starvation
8/6/2019 Tema 5.1 S5
19/42
Requirements for Mutual
Exclusion A process must not be delayed access toa critical section when there is no other
process using it
No assumptions are made about relative
process speeds or number of processes
A process remains inside its critical
section for a finite time only
8/6/2019 Tema 5.1 S5
20/42
First Attempt
Busy Waiting
Process is always checking to see if it can
enter the critical section
Process can do nothing productive until it
gets permission to enter its critical section
8/6/2019 Tema 5.1 S5
21/42
Second Attempt
Each process can examine the others statusbut cannot alter it
When a process wants to enter the critical
section it checks the other processes first If no other process is in the critical section, it
sets its status for the critical section
This method does not guarantee mutual
exclusion Each process can check the flags and then
proceed to enter the critical section at the sametime
8/6/2019 Tema 5.1 S5
22/42
Correct Solution
Each process gets a turn at the critical
section
If a process wants the critical section, it
sets its flag and may have to wait for its
turn
8/6/2019 Tema 5.1 S5
23/42
Semaphores
Special variable called a semaphore is
used for signaling
If a process is waiting for a signal, it is
suspended until that signal is sent
Wait (Proberen) and signal (Verhogen)
operations cannot be interrupted
Queue is used to hold processes waiting
on the semaphore
8/6/2019 Tema 5.1 S5
24/42
Semaphores
Semaphore is a variable that has an
integer value
May be initialized to a nonnegative number
Wait operation decrements the semaphore
value, if the value becomes negative, the
process is blocked.
Signal operation increments semaphorevalue. If the value is less than or equal to
zero, then a process blocked by semWait is
unblocked.
8/6/2019 Tema 5.1 S5
25/42
Semaphores
Binary semaphore or mutex
May be initialized to 0 or 1
Wait operation checks the semaphore value.
If the value is 0 the process is blocked. If
the value is 1 then the value is changed to 0
and the process continues.
Signal operation checks to see if anyprocess are blocked on this semaphore. If
so, then a process is unblocked. If no
processes are blocked, then the value of the
semaphore is set to 1.
8/6/2019 Tema 5.1 S5
26/42
Semaphores
A semaphore whose definition includes
the FIFO policy is called strong
semaphore.
A weak semaphore does not specify the
order in which the processes are
removed from the queue.
8/6/2019 Tema 5.1 S5
27/42
Producer/Consumer Problem
One or more producers are generating
data and placing these in a buffer
A single consumer is taking items out of
the buffer one at time
Only one producer or consumer may
access the buffer at any one time
8/6/2019 Tema 5.1 S5
28/42
Producer
producer:
while (true) {
/* produce item v */b[in] = v;
in++;
}
8/6/2019 Tema 5.1 S5
29/42
Consumer
consumer:
while (true) {
while (in
8/6/2019 Tema 5.1 S5
30/42
Monitors
Monitor is a software module
Chief characteristics
Local data variables are accessible only bythe monitor
Process enters monitor by invoking one of
its procedures
Only one process may be executing in themonitor at a time
8/6/2019 Tema 5.1 S5
31/42
Monitors
Monitor supports synchronization by the
use of conditional variables that are
contained within the monitor and
accessible only within the monitor.
8/6/2019 Tema 5.1 S5
32/42
Monitors
Condition variables are operated by:
cwait(c): Suspend execution of the calling
process on condition c. The monitor is
available for use by another process.
csignal(c): Resume execution of some
process blocked after a cwait on the same
condition.
8/6/2019 Tema 5.1 S5
33/42
8/6/2019 Tema 5.1 S5
34/42
Monitors
Advantages:
All of the synchronization functions are confined tothe monitor.
Easier to verify that the synchronization has been
done correctly.
Easier to detect bugs.
Once a monitor is correctly programmed, access tothe protected resource is correct for access from all
process. Contrast: With semaphores, resource access is correct
only if all of the process that access the resource areprogrammed correctly.
8/6/2019 Tema 5.1 S5
35/42
Message Passing
Enforce mutual exclusion
Cooperating processes may need to
exchange information
Lends itself to implementation in
Distributed systems, shared-memory
multiprocessor and uniprocessor
send (destination, message)
receive (source, message)
8/6/2019 Tema 5.1 S5
36/42
Synchronization
Sender and receiver may or may not be
blocking (waiting for message)
Blocking send, blocking receive
Both sender and receiver are blocked until
message is delivered
Called a rendezvous
Tight synchronization.
8/6/2019 Tema 5.1 S5
37/42
Synchronization
Nonblocking send, blocking receive
Sender continues processing such as
sending messages as quickly as possible
Receiver is blocked until the requested
message arrives
Nonblocking send, nonblocking receive
Neither party is required to wait
8/6/2019 Tema 5.1 S5
38/42
Addressing
Direct addressing
send primitive includes a specific identifier
of the destination process
receive primitive could know ahead of time
from which process a message is expected
receive primitive could use source
parameter to return a value when the receiveoperation has been performed
8/6/2019 Tema 5.1 S5
39/42
Addressing
Indirect addressing
messages are sent to a shared data structure
consisting of queues
queues are called mailboxes
one process sends a message to the mailbox
and the other process picks up the message
from the mailbox
8/6/2019 Tema 5.1 S5
40/42
8/6/2019 Tema 5.1 S5
41/42
Message Format
8/6/2019 Tema 5.1 S5
42/42
Dining Philosophers Problem