Mastering Concurrency in Operating Systems: Tips and Strategies
undefined
W
e
l
c
o
m
e
t
o
C
S
3
4
5
O
p
e
r
a
t
i
n
g
S
y
s
t
e
m
s
C
o
n
c
u
r
r
e
n
c
y
,
C
h
a
p
t
e
r
6
(
1
3
)
T
i
p
#
1
3
:
S
i
z
e
o
f
A
r
r
a
y
■
To get the size of an array of any data type, use the following
macro:
#define NUM_OF(x) (sizeof (x) / sizeof (*x))
The macro divides the length of the array to the size of its field.
Size of number[10] is 10
Size of teststr[20] is 20
2
Concurrency (13)
int main()
{ int number[10] = {1,1,1,1,1,1}; char *teststr[20] = {"","","","","","","","",""}; printf("Size of number[10] is %d\n", NUM_OF(number)); printf("Size of teststr[20] is %d\n", NUM_OF(teststr));}
Who has priority
Reader or Writer?
R
e
a
d
e
r
s
/
W
r
i
t
e
r
s
Semaphore rmutex=1, wmutex = 1;
integer readcount = 0;
Only one writer
at a time
More than one
reader at a time
The first reader
makes sure no
one can write
Last one out allows
writing again
R
e
a
d
e
r
s
h
a
v
e
p
r
i
o
r
i
t
y
!
(
w
r
i
t
e
r
s
s
u
b
j
e
c
t
t
o
s
t
a
r
v
a
t
i
o
n
!
)
Concurrency (13)
3
W
r
i
t
e
r
s
/
R
e
a
d
e
r
s
while(true)
{ wait(outerQ);wait(rsem);
wait(rmutex);
readcnt++
if (readcnt == 1)
wait(wsem);
signal(rmutex);
signal(rsem);
signal(outerQ);
READ
wait(rmutex);
readcnt--;
if(readcnt == 0)
signal(wsem);
signal(rmutex);
};
while(true)
{ wait(wmutex);writecnt++;
if (writecnt == 1)
wait(rsem);
signal(wmutex);
wait(wsem);
WRITE
signal(wsem);
wait(wmutex);
writecnt--;
if (writecnt == 0)
signal(rsem);
signal(wmutex);
};
Semaphore outerQ, rsem, rmutex, wmutex, wsem = 1;
Concurrency (13)
4
1
2
3
4
5
6
Disable
writers
Last reader out
allows writers
Wait here until
all readers done,
as well as
multiple writers
Last writer out
allows readers
Additional readers
queue here allowing
writers to jump ahead
of the readers
Once a writer
wants to
write – no
new readers
allowed
■
3 barbers, each with a barber chair
■
Haircuts vary in time
■
Sofa can hold 4 customers
■
Maximum of 20 in shop
■
Customers arrive randomly
■
Customers wait outside if necessary
■
When a chair is empty:
■
Customer sitting longest on sofa is served
■
Customer standing the longest sits down
■
After haircut, customer pays cashier at cash register
■
Barbers have to cut hair and cashier
■
Customer waits for receipt
■
Upon exit, new customer allowed in shop
Concurrency (13)
5
B
a
r
b
e
r
s
h
o
p
P
r
o
b
l
e
m
p
r
o
c
e
d
u
r
e
c
u
s
t
o
m
e
r
;
v
a
r
c
u
s
t
n
r
:
i
n
t
e
g
e
r
;
b
e
g
i
n
w
a
i
t
(
m
a
x
_
c
a
p
a
c
i
t
y
)
;
/
/
e
n
t
e
r
_
s
h
o
p
w
a
i
t
(
m
u
t
e
x
1
)
;
c
o
u
n
t
:
=
c
o
u
n
t
+
1
;
c
u
s
t
n
r
:
=
c
o
u
n
t
;
s
i
g
n
a
l
(
m
u
t
e
x
1
)
;
w
a
i
t
(
s
o
f
a
)
;
/
/
s
i
t
o
n
s
o
f
a
w
a
i
t
(
b
a
r
b
e
r
_
c
h
a
i
r
)
;
/
/
g
e
t
u
p
f
r
o
m
s
o
f
a
s
i
g
n
a
l
(
s
o
f
a
)
;
/
/
s
i
t
i
n
b
a
r
b
e
r
c
h
a
i
r
w
a
i
t
(
m
u
t
e
x
2
)
;
e
n
q
u
e
u
e
1
(
c
u
s
t
n
r
)
;
s
i
g
n
a
l
(
c
u
s
t
_
r
e
a
d
y
)
;
s
i
g
n
a
l
(
m
u
t
e
x
2
)
;
w
a
i
t
(
f
i
n
i
s
h
e
d
[
c
u
s
t
n
r
]
)
;
/
/
l
e
a
v
e
b
a
r
b
e
r
c
h
a
i
r
s
i
g
n
a
l
(
l
e
a
v
e
_
b
_
c
h
a
i
r
)
;
/
/
p
a
y
s
i
g
n
a
l
(
p
a
y
m
e
n
t
)
;
w
a
i
t
(
r
e
c
e
i
p
t
)
;
/
/
e
x
i
t
s
h
o
p
s
i
g
n
a
l
(
m
a
x
_
c
a
p
a
c
i
t
y
)
;
e
n
d
;
p
r
o
c
e
d
u
r
e
b
a
r
b
e
r
;
v
a
r
b
_
c
u
s
t
:
i
n
t
e
g
e
r
b
e
g
i
n
r
e
p
e
a
t
/
/
g
e
t
c
u
s
t
o
m
e
r
w
a
i
t
(
c
u
s
t
_
r
e
a
d
y
)
;
w
a
i
t
(
m
u
t
e
x
2
)
;
d
e
q
u
e
u
e
1
(
b
_
c
u
s
t
)
;
s
i
g
n
a
l
(
m
u
t
e
x
2
)
;
w
a
i
t
(
c
o
o
r
d
)
;
/
/
c
u
t
h
a
i
r
s
i
g
n
a
l
(
c
o
o
r
d
)
;
s
i
g
n
a
l
(
f
i
n
i
s
h
e
d
[
b
_
c
u
s
t
]
)
;
w
a
i
t
(
l
e
a
v
e
_
b
_
c
h
a
i
r
)
;
s
i
g
n
a
l
(
b
a
r
b
e
r
_
c
h
a
i
r
)
;
f
o
r
e
v
e
r
e
n
d
;
p
r
o
c
e
d
u
r
e
c
a
s
h
i
e
r
;
b
e
g
i
n
r
e
p
e
a
t
w
a
i
t
(
p
a
y
m
e
n
t
)
;
w
a
i
t
(
c
o
o
r
d
)
;
/
/
a
c
c
e
p
t
p
a
y
m
e
n
t
s
i
g
n
a
l
(
c
o
o
r
d
)
;
s
i
g
n
a
l
(
r
e
c
e
i
p
t
)
;
f
o
r
e
v
e
r
e
n
d
;
m
a
x
_
c
a
p
a
c
i
t
y
:
s
e
m
a
p
h
o
r
e
(
:
=
2
0
)
;
s
o
f
a
:
s
e
m
a
p
h
o
r
e
(
:
=
4
)
;
b
a
r
b
e
r
_
c
h
a
i
r
,
c
o
o
r
d
:
s
e
m
a
p
h
o
r
e
(
:
=
3
)
;
m
u
t
e
x
1
,
m
u
t
e
x
2
:
s
e
m
a
p
h
o
r
e
(
:
=
1
)
;
c
u
s
t
_
r
e
a
d
y
,
l
e
a
v
e
_
b
_
c
h
a
i
r
:
s
e
m
a
p
h
o
r
e
(
:
=
0
)
p
a
y
m
e
n
t
,
r
e
c
e
i
p
t
:
s
e
m
a
p
h
o
r
e
(
:
=
0
)
f
i
n
i
s
h
e
d
:
a
r
r
a
y
[
1
.
.
5
0
]
o
f
s
e
m
a
p
h
o
r
e
(
:
=
0
)
;
c
o
u
n
t
:
i
n
t
e
g
e
r
;
Concurrency (13)
6
F
a
i
r
B
a
r
b
e
r
s
h
o
p
Visitors try to enter the Jurassic Park at random
times. (Only a set number of visitors may be in the
park at any one time – OSHA requirements!)
Upon being allowed in
the park, a visitor
must get in line to
purchase a ticket.
After successfully obtaining a ticket
from a
driver
, the visitor gets in the museum line
and visits the museum. (A limited number of
visitors are allowed in the museum as well as
the gift shop.)
After visiting the
museum, the visitor
gets in the tour car
line to wait until
permitted to board a
tour car. (As a visitor
boards a tour car, he
returns his ticket.)
When the touring car is filled with visitors and a
driver is obtained, the car enters Jurassic Park
and runs a guided tour through the park.
When the tour car pulls
into the unloading station,
the visitors exit the tour
car. and the driver goes
to sleep awaiting new
duties. The tour car
pulls forward to be loaded
again.
After visiting the gift
shop, the visitors exit
the park.
After the visitors exit a tour
car, they get into the gift
shop line until they can visit
the gift shop.
Concurrency (13)
7
L
a
b
0
3
:
J
u
r
a
s
s
i
c
P
a
r
k
p
r
o
c
e
d
u
r
e
v
i
s
i
t
o
r
;
v
a
r
v
i
s
i
t
o
r
_
i
d
:
i
n
t
e
g
e
r
;
b
e
g
i
n
w
a
i
t
(
m
a
x
_
c
a
p
a
c
i
t
y
)
;
/
/
e
n
t
e
r
_
p
a
r
k
w
a
i
t
(
p
a
r
k
M
u
t
e
x
)
;
n
u
m
O
u
t
s
i
d
e
P
a
r
k
-
-
;
n
u
m
I
n
P
a
r
k
-
+
+
;
s
i
g
n
a
l
(
p
a
r
k
M
u
t
e
x
)
;
/
/
g
e
t
a
t
i
c
k
e
t
w
a
i
t
(
r
e
q
u
e
s
t
T
i
c
k
e
t
M
u
t
e
x
)
;
s
i
g
n
a
l
(
n
e
e
d
T
i
c
k
e
t
)
;
s
i
g
n
a
l
(
w
a
k
e
u
p
D
r
i
v
e
r
)
;
w
a
i
t
(
t
a
k
e
T
i
c
k
e
t
)
;
s
i
g
n
a
l
(
r
e
q
u
e
s
t
T
i
c
k
e
t
M
u
t
e
x
)
;
/
/
v
i
s
i
t
m
u
s
e
u
m
/
/
g
e
t
i
n
c
a
r
l
i
n
e
/
/
w
a
i
t
f
o
r
a
s
e
a
t
w
a
i
t
(
n
e
e
d
_
v
i
s
i
t
o
r
)
;
s
i
g
n
a
l
(
v
i
s
i
t
o
r
_
r
e
a
d
y
)
;
p
a
s
s
_
t
o
_
c
a
r
(
v
i
s
i
t
o
r
_
i
d
)
;
w
a
i
t
(
r
i
d
e
_
o
v
e
r
)
;
/
/
g
i
v
e
b
a
c
k
t
i
c
k
e
t
/
/
v
i
s
i
t
g
i
f
t
s
h
o
p
/
/
e
x
i
t
p
a
r
k
s
i
g
n
a
l
(
m
a
x
_
c
a
p
a
c
i
t
y
)
;
e
n
d
;
p
r
o
c
e
d
u
r
e
c
a
r
;
v
a
r
c
a
r
I
D
:
i
n
t
e
g
e
r
b
e
g
i
n
r
e
p
e
a
t
/
/
f
i
l
l
3
c
a
r
s
e
a
t
s
f
o
r
(
N
U
M
_
S
E
A
T
S
)
{w
a
i
t
(
f
i
l
l
S
e
a
t
[
c
a
r
I
D
]
)
;
s
i
g
n
a
l
(
n
e
e
d
_
v
i
s
i
t
o
r
)
;
w
a
i
t
(
v
i
s
i
t
o
r
_
r
e
a
d
y
)
;
s
a
v
e
_
V
i
s
i
t
o
r
(
v
i
s
i
t
o
r
I
D
)
;
s
i
g
n
a
l
(
s
e
a
t
F
i
l
l
e
d
[
c
a
r
I
D
]
)
;
}
p
a
s
s
_
t
o
_
p
a
r
k
(
c
a
r
D
o
n
e
)
;
s
i
g
n
a
l
(
c
a
r
R
e
a
d
y
)
;
/
/
e
n
j
o
y
r
i
d
e
w
a
i
t
(
c
a
r
D
o
n
e
)
;
s
i
g
n
a
l
(
e
a
c
h
v
i
s
i
t
o
r
I
D
)
;
f
o
r
e
v
e
r
e
n
d
;
m
a
x
_
c
a
p
a
c
i
t
y
:
s
e
m
a
p
h
o
r
e
(
:
=
2
0
)
;
p
a
r
k
M
u
t
e
x
,
r
e
q
u
e
s
t
T
i
c
k
e
t
M
u
t
e
x
:
s
e
m
a
p
h
o
r
e
(
:
=
1
)
;
n
e
e
d
T
i
c
k
e
t
,
w
a
i
t
T
i
c
k
e
t
:
s
e
m
a
p
h
o
r
e
(
:
=
0
)
p
r
o
c
e
d
u
r
e
d
r
i
v
e
r
;
v
a
r
c
a
r
I
D
:
i
n
t
e
g
e
r
b
e
g
i
n
r
e
p
e
a
t
w
a
i
t
(
w
a
k
e
u
p
D
r
i
v
e
r
)
;
i
f
(
t
r
y
l
o
c
k
(
n
e
e
d
_
t
i
c
k
e
t
)
)
{s
i
g
n
a
l
(
t
a
k
e
T
i
c
k
e
t
)
;
}
e
l
s
e
{s
i
g
n
a
l
(
d
r
i
v
e
r
_
r
e
a
d
y
)
;
w
a
i
t
(
r
i
d
e
_
o
v
e
r
)
;
{f
o
r
e
v
e
r
e
n
d
;
Concurrency (13)
8
J
u
r
a
s
s
i
c
P
a
r
k
M
e
s
s
a
g
e
P
a
s
s
i
n
g
■
Shared memory is useful in a threaded environment
■
Single atomic variables (semaphores, modes)
■
Memory mapping (data structures, messages)
■
Test-and-set (atomic instructions)
■
Fast – do not require data movement (reference)
■
Inter-process communication (IPC) used by processes
■
for processes inside the same computer
■
for processes in a distributed system
■
Message passing used by distributed systems (networks)
■
send(destination, message)
■
post(destination, message)
■
receive(source, message)
Concurrency (13)
9
S
y
n
c
h
r
o
n
i
z
a
t
i
o
n
■
For the sender: it is more natural not to be blocked
■
can send several messages to multiple destinations
■
sender usually expects acknowledgment of message receipt (in case receiver
fails)
■
PostMessage
() is asynchronous – returns immediately
■
SendMessage
() is synchronous –block until message delivered and processed
■
For the receiver: it is more natural to be blocked after issuing
ReceiveMessage
()
■
the receiver usually needs the info before proceeding
■
but could be blocked indefinitely if sender process fails before sending reply
Concurrency (13)
10
10
A
d
d
r
e
s
s
i
n
g
■
Middleware:
■
Software that acts as a bridge between an operating system or applications,
especially on a network.
■
Direct addressing:
■
When a specific process identifier is used for source/destination
■
But what about late binding (ie., a print server)?
■
Indirect addressing (more convenient):
■
Messages are sent to a shared
mailbox
(queue of messages)
■
Senders put messages in mailbox (produce), receivers pick them up (consume)
Concurrency (13)
11
11
■
A mailbox facilitates message deliveries
■
A mailbox can be private - one sender/receiver pair
■
A mailbox can be shared among several senders and receivers -
OS may then
allow the use of message types (for selection)
■
A mailbox
port
associates one receiver with multiple senders -
used for
client/server application: the receiver is the server
P
o
r
t
/
M
a
i
l
b
o
x
O
w
n
e
r
s
h
i
p
■
A port is usually owned and created
by the receiving process
■
The port is destroyed when the
receiver terminates
■
The OS creates a mailbox on
behalf of a process (which
becomes the owner)
■
The mailbox is destroyed at the
owner’s request or when the owner
terminates
Concurrency (13)
12
12
M
o
n
i
t
o
r
s
■
In concurrent programming (also known as parallel programming), a monitor is a
programming-language synchronization construct that provides equivalent
functionality to that of semaphores.
Concurrency (13)
13
13
■
ME threads that wait (block) for true conditions.
■
Thread-safe class (wrapped by mutual exclusive conditions)
■
Concurrent Pascal, Pascal-Plus, Modula, Java
■
A monitor is a software module containing:
■
one or more procedures, an initialization sequence, and local data variables
■
Mutex (lock) object and condition variables
■
Condition variable:
■
Container of threads that are waiting on a certain condition.
■
Threads temporarily give up exclusive access in order to wait for some
condition to be met.
■
Local variables accessible only by monitor’s procedures
■
A process enters the monitor by invoking one of its procedures
■
Only one process can be in the monitor at any one time
H
o
a
r
e
M
o
n
i
t
o
r
E
x
a
m
p
l
e
■
With a blocking condition variable, the signaling thread must wait outside
the monitor (at least) until the signaled thread relinquishes occupancy of
the monitor by either returning or by again waiting on a condition variable.
■
Monitors using blocking condition variables are often called Hoare-style
monitors or signal-and-urgent-wait monitors.
Concurrency (13)
14
14
A Hoare style monitor with two
condition variables a and b.
■
We assume there are two queues of threads
associated with each monitor object
■
e is the entrance queue
■
s is a queue of threads that have signaled.
■
All queues are typically guaranteed to be fair and, in
some implementations, may be guaranteed to be first
in first out.
■
Each operation runs in mutual exclusion to the
others; thus, restarted threads do not begin
executing until the operation is complete.)
Monitor boundedbuffer:
buffer:
array[0..k-1] of items
;
nextin:=0, nextout:=0, count:=0:
integer
;
notfull, notempty:
condition
;
Produce(v):
if (count = k)
cwait(notfull)
;
buffer[nextin] := v;
nextin := nextin+1 mod k;
count++;
csignal(notempty)
;
Consume(v):
if (count = 0)
cwait(notempty)
;
v := buffer[nextout];
nextout := nextout+1 mod k;
count--;
csignal(notfull)
;
M
o
n
i
t
o
r
f
o
r
t
h
e
P
/
C
p
r
o
b
l
e
m
Make threading system
release all locks;
sleep until condition is met.
Signal a consumer thread
or all consumer threads
that are blocked waiting for
non-empty buffer.
Concurrency (13)
15
15
C
o
n
c
l
u
s
i
o
n
■
Semaphores are a powerful tool for enforcing mutual exclusion and to
coordinate processes.
■
When wait(S) and signal(S) are scattered among several processes
■
Difficult to understand their effects.
■
Difficult to test.
■
Monitors make classes thread-safe and mutual exclusion more
controllable.
■
Usage must be correct in all the processes (everyone has to play by
the rules).
■
One bad (or malicious) process can fail the entire collection of processes
Concurrency (13)
16
16
D
e
l
t
a
C
l
o
c
k
Concurrency (13)
17
17
■
Problem: How to efficiently monitor multiple timed events?
■
Examples of timed events:
■
scheduling
■
real-time sequencing
■
timers
■
timeouts
■
Lists require each event timer to be decremented (
O(n)
) to
determine if time has expired.
■
Using a Delta Clock only requires decrementing the top entry (
O(1)
).
D
C
I
m
p
l
e
m
e
n
t
a
t
i
o
n
Concurrency (13)
18
18
Suppose:
Event1 occurs in 20 tics
Event2 occurs in 5 tics
Event3 occurs in 35 tics
Event4 occurs in 27 tics
Event 5 occurs in 27 tics
Event 6 occurs in 22 tics
N
o
t
i
c
e
t
h
a
t
E
v
e
n
t
1
o
c
c
u
r
s
1
5
t
i
c
s
a
f
t
e
r
E
v
e
n
t
2
A
n
d
t
h
a
t
E
v
e
n
t
6
o
c
c
u
r
s
2
t
i
c
s
a
f
t
e
r
E
v
e
n
t
1
What if Event7 occurs in 17 tics?
Event8 in 31 tics?
■
Thoroughly test the operation of your delta clock before proceeding.
■
os345p3.c
■
Print Delta Clock (dc): int P3_dc(int argc, char* argv[]);
■
Test Delta Clock (tdc): int P3_tdc(int argc, char* argv[]);
■
i
n
t
d
c
M
o
n
i
t
o
r
T
a
s
k
(
i
n
t
a
r
g
c
,
c
h
a
r
*
a
r
g
v
[
]
)
;
■
i
n
t
t
i
m
e
T
a
s
k
(
i
n
t
a
r
g
c
,
c
h
a
r
*
a
r
g
v
[
]
)
;
L
a
b
0
3
S
t
e
p
1
:
D
e
l
t
a
C
l
o
c
k
■
Implement delta clock.
■
Design data structure to hold delta times/events.
■
Program an insert delta clock function
■
insertDeltaClock(int time, Semaphore* sem);
■
High priority, mutex protected
■
Add 1/10 second function to decrement top event and
semSignal semaphore when 0
■
pollinterrupts or
■
High priority, mutex protected.
Concurrency (13)
19
19
C
h
a
p
t
e
r
6
C
o
n
c
u
r
r
e
n
c
y
:
D
e
a
d
l
o
c
k
a
n
d
S
t
a
r
v
a
t
i
o
n
Concurrency (13)
20
20
C
H
A
P
T
E
R
6
C
O
N
C
U
R
R
E
N
C
Y
:
D
E
A
D
L
O
C
K
A
N
D
S
T
A
R
V
A
T
I
O
N
21
21
C
S
3
4
5
Concurrency (13)
22
22
L
e
a
r
n
i
n
g
O
b
j
e
c
t
i
v
e
s
…
L
e
a
r
n
i
n
g
O
u
t
c
o
m
e
s
After completing this section, you should
be able to
■
List and explain the conditions of deadlock.
■
Define deadlock prevention and describe
deadlock prevention strategies related to each of
the conditions for deadlock.
■
Explain the difference between deadlock
prevention and deadlock avoidance.
■
Understand how an integrated deadlock strategy
can be designed.
■
Analyze the dining philosophers problem.
■
Explain the concurrency and synchronization
methods used in UNIX, Linux, Solaris, and
Windows 7.
T
o
p
i
c
s
Resources
Deadlock
Joint Process Diagrams
Deadlock Conditions
Circular Wait
Resource Allocation Graph
Handling Deadlock
Avoidance
Detection
Recovery
Concurrency (13)
23
23
Q
u
i
z
6
.
1
How could deadlock occur when
200K bytes of memory is available for
allocation by the system
Process 1 needs 140K in 80K, 60K blocks
Process 2 needs 150k in 70K, 80K blocks
How could deadlock occur when
Two processes need to communicate via
send/receive messages
Process 1 waits to hear from process 2
before sending data
Process 2 proceeds after hearing from
process 1
Concurrency (13)
24
24
T
y
p
e
s
o
f
R
e
s
o
u
r
c
e
s
■
Reusable Resources
■
Used by one process at a time and not depleted by that use
■
Processes obtain resources that they later release for reuse by other processes
■
Processor time, I/O channels, main and secondary memory, files, databases, and
semaphores
■
Deadlock occurs if each process holds one resource and requests the other
■
Consumable Resources
■
Created (produced) and destroyed (consumed) by a process
■
Interrupts, signals, messages, and information in I/O buffers
■
Deadlock may occur if a Receive message is blocking
■
May take a rare combination of events to cause deadlock
Concurrency (13)
25
25
F
o
l
l
o
w
t
h
e
R
u
l
e
s
…
■
System Model (Rules)
■
Process must request (and be granted) a resource before using it.
■
Process must release the resource when done.
■
Why??
■
Deadlock
■
A set of processes is in a deadlock state when every process in the set is
waiting for an event that can only be caused by another process in the set.
Concurrency (13)
26
26
1.
What are the resources?
2.
Where is mutual exclusion needed?
3.
What is required for deadlock to occur?
Q
u
i
z
6
.
2
Concurrency (13)
27
27
1.
What are the resources?
2.
Where is mutual exclusion needed?
3.
What is required for deadlock to occur?
ME
Q
u
i
z
6
.
2
(
s
o
l
u
t
i
o
n
)
Concurrency (13)
28
28
?
J
o
i
n
t
P
r
o
c
e
s
s
D
i
a
g
r
a
m
Progress
of Q
Release A
Release B
Get A
Get B
Get A
Get B
Release A
Release B
Progress
of P
Deadlock is only
inevitable if the joint
progress of the two
processes creates a
path that enters the
fatal region
.
Impossible joint
conditions are
grayed out.
Concurrency (13)
29
29
J
o
i
n
t
P
r
o
c
e
s
s
D
i
a
g
r
a
m
Progress
of Q
Release
A
Release
B
Get A
Get B
Get A
Get B
Release A
Release B
Progress
of P
A
Required
B
Required
A
Required
B
Required
No fatal region, as
there are “exit” paths
available.
Concurrency (13)
30
30
C
o
n
d
i
t
i
o
n
s
o
f
D
e
a
d
l
o
c
k
■
Necessary (but not sufficient)
■
Mutual exclusion – Everyone abides by the rules
■
only one process may use a resource at a time.
■
no process may access resource allocated to another.
■
Hold-and-wait
■
a process may hold allocated resources while awaiting assignment of other
resources.
■
No preemption
■
no resource can be forced to free a resource.
■
Circular wait (sufficient)
■
a closed chain of processes exists, such that each process holds at least one
resource needed by the next process in the chain (consequence of the first three
conditions)
■
Other conditions are necessary but not sufficient for deadlock - all four
conditions must hold for deadlock - Unresolvable circular wait is the definition of
deadlock!
Concurrency (13)
31
31
C
i
r
c
u
l
a
r
W
a
i
t
Concurrency (13)
32
32
R
e
s
o
u
r
c
e
A
l
l
o
c
a
t
i
o
n
G
r
a
p
h
Deadlocks can be described
using resource allocation graph.
Concurrency (13)
33
33
P
1
P
2
P
3
R
1
R
2
R
4
R
3
Is there a cycle (ie. some number
of vertices connected in a closed
chain)?
R
e
s
o
u
r
c
e
A
l
l
o
c
a
t
i
o
n
G
r
a
p
h
Is there deadlock?
If the graph contains a cycle, deadlock
MAY exist.
If a graph contains no cycles,
then no process in the system is
deadlocked.
Yes
Concurrency (13)
34
34
P
1
P
2
P
3
R
2
Is there a cycle?
Is there deadlock?
P
4
R
1
Yes
No
D
e
a
d
l
o
c
k
?
Concurrency (13)
35
35
T
r
a
f
f
i
c
I
n
t
e
r
s
e
c
t
i
o
n
Concurrency (13)
36
36
H
a
n
d
l
i
n
g
D
e
a
d
l
o
c
k
■
Four general approaches exist for dealing with deadlock.
1.
Prevent deadlock
■
by adopting a policy that eliminates one of the conditions.
2.
Avoid deadlock
■
by making the appropriate dynamic choices based on the current state of
resource allocation.
3.
Detect Deadlock
■
by checking whether conditions 1 through 4 hold and take action to recover.
4.
Ignore Deadlock
■
System may hang, so??
Concurrency (13)
37
37
Be Safe
Explore intricate concepts in operating systems concurrency from Chapter 6 of CS 345. Learn practical tips and techniques such as determining the size of arrays, managing readers and writers using semaphores, and tackling the Barbershop Problem. Dive into array manipulation, semaphore usage, and priority management between readers and writers.
Uploaded on Sep 26, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Welcome to CS 345 Operating Systems Concurrency, Chapter 6 (13)
Tip #13: Size of Array 2 Concurrency (13) To get the size of an array of any data type, use the following macro: #define NUM_OF(x) (sizeof (x) / sizeof (*x)) int main() { int number[10] = {1,1,1,1,1,1}; char *teststr[20] = {"","","","","","","","",""}; printf("Size of number[10] is %d\n", NUM_OF(number)); printf("Size of teststr[20] is %d\n", NUM_OF(teststr)); } Size of number[10] is 10 Size of teststr[20] is 20 The macro divides the length of the array to the size of its field.
Readers/Writers 3 Concurrency (13) Semaphore rmutex=1, wmutex = 1; integer readcount = 0; Only one writer at a time The first reader makes sure no one can write while(true) { wait(wmutex); <write to the data object> signal(wmutex); }; while(true) { wait(rmutex); readcount++; if (readcount == 1) wait(wmutex); signal(rmutex); <read the data> wait(rmutex); readcount--; if (readcount == 0) signal(wmutex); signal(rmutex); }; Writer Who has priority Reader or Writer? (writers subject to starvation!) Readers have priority! Last one out allows writing again Reader More than one reader at a time
Writers/Readers 4 Concurrency (13) Semaphore outerQ, rsem, rmutex, wmutex, wsem = 1; while(true) { wait(outerQ); wait(rsem); wait(rmutex); readcnt++ if (readcnt == 1) wait(wsem); signal(rmutex); signal(rsem); signal(outerQ); while(true) { wait(wmutex); writecnt++; if (writecnt == 1) wait(rsem); signal(wmutex); wait(wsem); Additional readers queue here allowing writers to jump ahead of the readers 6 Once a writer wants to write no new readers allowed 3 WRITE Disable writers 1 Wait here until all readers done, as well as multiple writers 4 signal(wsem); wait(wmutex); writecnt--; if (writecnt == 0) signal(rsem); signal(wmutex); }; READ wait(rmutex); readcnt--; if(readcnt == 0) signal(wsem); signal(rmutex); }; 5 Last reader out allows writers 2 Last writer out allows readers
Barbershop Problem 5 Concurrency (13) 3 barbers, each with a barber chair Haircuts vary in time Barber chairs Sofa can hold 4 customers Cashier Entrance Maximum of 20 in shop Customers arrive randomly Customers wait outside if necessary Exit Standing room area Sofa When a chair is empty: Customer sitting longest on sofa is served Customer standing the longest sits down After haircut, customer pays cashier at cash register Barbers have to cut hair and cashier Customer waits for receipt Upon exit, new customer allowed in shop
Fair Barbershop 6 Concurrency (13) procedure barber; var b_cust: integer begin repeat // get customer wait( cust_ready ); wait( mutex2 ); dequeue1( b_cust ); signal( mutex2 ); wait( coord ); // cut hair signal( coord ); signal( finished[b_cust] ); wait( leave_b_chair ); signal( barber_chair ); forever end; procedure customer; var custnr: integer; begin wait ( max_capacity ); // enter_shop wait( mutex1 ); count := count + 1; custnr := count; signal( mutex1 ); wait( sofa ); // sit on sofa wait( barber_chair ); // get up from sofa signal( sofa ); // sit in barber chair wait( mutex2 ); enqueue1( custnr ); signal( cust_ready ); signal( mutex2 ); wait( finished[custnr] ); // leave barber chair signal( leave_b_chair ); // pay signal( payment ); wait( receipt ); // exit shop signal( max_capacity ); end; Barber chairs Cashier Entrance Exit Standing room area Sofa max_capacity: semaphore (:=20); sofa: semaphore (:=4); barber_chair, coord: semaphore (:=3); mutex1, mutex2: semaphore (:=1); cust_ready, leave_b_chair: semaphore (:=0) payment, receipt: semaphore (:=0) finished: array [1..50] of semaphore (:=0); count: integer; procedure cashier; begin repeat wait( payment ); wait( coord ); // accept payment signal( coord ); signal( receipt ); forever end;
Lab 03: Jurassic Park 7 Concurrency (13) When the touring car is filled with visitors and a driver is obtained, the car enters Jurassic Park and runs a guided tour through the park. Visitors try to enter the Jurassic Park at random times. (Only a set number of visitors may be in the park at any one time OSHA requirements!) Upon being allowed in the park, a visitor must get in line to purchase a ticket. When the tour car pulls into the unloading station, the visitors exit the tour car. and the driver goes to sleep awaiting new duties. The tour car pulls forward to be loaded again. After visiting the museum, the visitor gets in the tour car line to wait until permitted to board a tour car. (As a visitor boards a tour car, he returns his ticket.) After successfully obtaining a ticket from a driver, the visitor gets in the museum line and visits the museum. (A limited number of visitors are allowed in the museum as well as the gift shop.) After the visitors exit a tour car, they get into the gift shop line until they can visit the gift shop. After visiting the gift shop, the visitors exit the park.
Jurassic Park 8 Concurrency (13) procedure car; var carID: integer begin repeat // fill 3 car seats for (NUM_SEATS) { wait ( fillSeat[carID] ); signal ( need_visitor ); wait ( visitor_ready ); save_Visitor( visitorID ); signal ( seatFilled[carID] ); } pass_to_park( carDone ); signal ( carReady ); // enjoy ride wait ( carDone ); signal ( each visitorID ); forever end; max_capacity: semaphore (:=20); parkMutex, requestTicketMutex: semaphore (:=1); needTicket, waitTicket: semaphore (:=0) procedure visitor; var visitor_id: integer; begin wait ( max_capacity ); // enter_park wait ( parkMutex ); numOutsidePark--; numInPark-++; signal ( parkMutex ); // get a ticket wait ( requestTicketMutex ); signal ( needTicket ); signal ( wakeupDriver ); wait ( takeTicket ); signal ( requestTicketMutex ); procedure driver; var carID: integer begin repeat wait ( wakeupDriver ); if ( trylock ( need_ticket ) ) { signal (takeTicket); } else { signal ( driver_ready ); wait ( ride_over ); { forever end; pass_to_car ( visitor_id ); wait ( ride_over ); // give back ticket // visit gift shop // exit park signal ( max_capacity ); end; // visit museum // get in car line // wait for a seat wait ( need_visitor ); signal ( visitor_ready );
Message Passing 9 Concurrency (13) Shared memory is useful in a threaded environment Single atomic variables (semaphores, modes) Memory mapping (data structures, messages) Test-and-set (atomic instructions) Fast do not require data movement (reference) Inter-process communication (IPC) used by processes for processes inside the same computer for processes in a distributed system Message passing used by distributed systems (networks) send(destination, message) post(destination, message) receive(source, message)
Synchronization 10 Concurrency (13) For the sender: it is more natural not to be blocked can send several messages to multiple destinations sender usually expects acknowledgment of message receipt (in case receiver fails) PostMessage() is asynchronous returns immediately SendMessage() is synchronous block until message delivered and processed For the receiver: it is more natural to be blocked after issuing ReceiveMessage() the receiver usually needs the info before proceeding but could be blocked indefinitely if sender process fails before sending reply
Addressing 11 Concurrency (13) Middleware: Software that acts as a bridge between an operating system or applications, especially on a network. Direct addressing: When a specific process identifier is used for source/destination But what about late binding (ie., a print server)? Indirect addressing (more convenient): Messages are sent to a shared mailbox (queue of messages) Senders put messages in mailbox (produce), receivers pick them up (consume) A mailbox facilitates message deliveries A mailbox can be private - one sender/receiver pair A mailbox can be shared among several senders and receivers - OS may then allow the use of message types (for selection) A mailbox port associates one receiver with multiple senders - used for client/server application: the receiver is the server
Port/Mailbox Ownership 12 Concurrency (13) A port is usually owned and created by the receiving process The port is destroyed when the receiver terminates The OS creates a mailbox on behalf of a process (which becomes the owner) The mailbox is destroyed at the owner s request or when the owner terminates
Monitors 13 Concurrency (13) In concurrent programming (also known as parallel programming), a monitor is a programming-language synchronization construct that provides equivalent functionality to that of semaphores. ME threads that wait (block) for true conditions. Thread-safe class (wrapped by mutual exclusive conditions) Concurrent Pascal, Pascal-Plus, Modula, Java A monitor is a software module containing: one or more procedures, an initialization sequence, and local data variables Mutex (lock) object and condition variables Condition variable: Container of threads that are waiting on a certain condition. Threads temporarily give up exclusive access in order to wait for some condition to be met. Local variables accessible only by monitor s procedures A process enters the monitor by invoking one of its procedures Only one process can be in the monitor at any one time
Hoare Monitor Example 14 Concurrency (13) With a blocking condition variable, the signaling thread must wait outside the monitor (at least) until the signaled thread relinquishes occupancy of the monitor by either returning or by again waiting on a condition variable. Monitors using blocking condition variables are often called Hoare-style monitors or signal-and-urgent-wait monitors. We assume there are two queues of threads associated with each monitor object e is the entrance queue s is a queue of threads that have signaled. All queues are typically guaranteed to be fair and, in some implementations, may be guaranteed to be first in first out. Each operation runs in mutual exclusion to the others; thus, restarted threads do not begin executing until the operation is complete.) A Hoare style monitor with two condition variables a and b.
Monitor for the P/C problem 15 Concurrency (13) Monitor boundedbuffer: buffer: array[0..k-1] of items; nextin:=0, nextout:=0, count:=0: integer; notfull, notempty: condition; Make threading system release all locks; sleep until condition is met. Produce(v): if (count = k) cwait(notfull); buffer[nextin] := v; nextin := nextin+1 mod k; count++; csignal(notempty); Signal a consumer thread or all consumer threads that are blocked waiting for non-empty buffer. Consume(v): if (count = 0) cwait(notempty); v := buffer[nextout]; nextout := nextout+1 mod k; count--; csignal(notfull);
Conclusion 16 Concurrency (13) Semaphores are a powerful tool for enforcing mutual exclusion and to coordinate processes. When wait(S) and signal(S) are scattered among several processes Difficult to understand their effects. Difficult to test. Monitors make classes thread-safe and mutual exclusion more controllable. Usage must be correct in all the processes (everyone has to play by the rules). One bad (or malicious) process can fail the entire collection of processes
Delta Clock 17 Concurrency (13) Problem: How to efficiently monitor multiple timed events? Examples of timed events: scheduling real-time sequencing timers timeouts Lists require each event timer to be decremented (O(n)) to determine if time has expired. Using a Delta Clock only requires decrementing the top entry (O(1)).
DC Implementation 18 Concurrency (13) Notice that Event1 occurs 15 tics after Event2 Suppose: 20 Event1 Event1 occurs in 20 tics Event2 occurs in 5 tics Event3 occurs in 35 tics Event4 occurs in 27 tics Event 5 occurs in 27 tics Event 6 occurs in 22 tics 5 Event2 5 Event2 35 Event3 5 12 Event2 Event7 5 12 3 Event2 Event7 Event1 27 Event4 15 3 2 Event1 Event1 Event6 2 2 5 Event6 Event6 Event4 27 Event5 5 5 0 Event4 Event4 Event5 And that Event6 occurs 2 tics after Event1 0 0 4 Event5 Event5 Event8 8 8 4 Event3 Event3 Event3 22 Event6 Linked List Delta Clock What if Event7 occurs in 17 tics? Event8 in 31 tics?
Lab 03 Step 1: Delta Clock 19 Concurrency (13) Implement delta clock. Design data structure to hold delta times/events. Program an insert delta clock function insertDeltaClock(int time, Semaphore* sem); High priority, mutex protected Add 1/10 second function to decrement top event and semSignal semaphore when 0 pollinterrupts or High priority, mutex protected. dc[5] dc[4] dc[3] dc[2] dc[1] dc[0] 10 / sem1 5 / sem2 0 / sem3 2 / sem4 4 Thoroughly test the operation of your delta clock before proceeding. os345p3.c Print Delta Clock (dc): int P3_dc(int argc, char* argv[]); Test Delta Clock (tdc): int P3_tdc(int argc, char* argv[]); int dcMonitorTask(int argc, char* argv[]); int timeTask(int argc, char* argv[]);
Concurrency (13) Chapter 6 Concurrency: Deadlock and Starvation 20
CHAPTER 6 CONCURRENCY: DEADLOCK AND STARVATION 21
CS 345 22 Concurrency (13) # 4 Project P1: Shell Stalling s Chapter 1: Computer System Overview 2: Operating System Overview 3: Process Description and Control 4: Threads 5: Concurrency: ME and Synchronization 6: Concurrency: Deadlock and Starvation 7: Memory Management 8: Virtual memory 9: Uniprocessor Scheduling 10: Multiprocessor and Real-Time Scheduling 11: I/O Management and Disk Scheduling 12: File Management Student Presentations 4 P2: Tasking 6 P3: Jurassic Park 6 P4: Virtual Memory 6 P5: Scheduling 8 P6: FAT 6
Learning Objectives 23 Concurrency (13) Topics Learning Outcomes After completing this section, you should be able to List and explain the conditions of deadlock. Define deadlock prevention and describe deadlock prevention strategies related to each of the conditions for deadlock. Explain the difference between deadlock prevention and deadlock avoidance. Understand how an integrated deadlock strategy can be designed. Analyze the dining philosophers problem. Explain the concurrency and synchronization methods used in UNIX, Linux, Solaris, and Windows 7. Resources Deadlock Joint Process Diagrams Deadlock Conditions Circular Wait Resource Allocation Graph Handling Deadlock Avoidance Detection Recovery
Quiz 6.1 24 Concurrency (13) How could deadlock occur when 200K bytes of memory is available for allocation by the system Process 1 needs 140K in 80K, 60K blocks Process 2 needs 150k in 70K, 80K blocks Process 2 Request 70K bytes Request 80K bytes Process 1 Request 80K bytes Request 60K bytes How could deadlock occur when Two processes need to communicate via send/receive messages Process 1 waits to hear from process 2 before sending data Process 2 proceeds after hearing from process 1 Process 1 Process 2 Receive(P1) Send(P1) Receive(P2) Send(P2)
Types of Resources 25 Concurrency (13) Reusable Resources Used by one process at a time and not depleted by that use Processes obtain resources that they later release for reuse by other processes Processor time, I/O channels, main and secondary memory, files, databases, and semaphores Deadlock occurs if each process holds one resource and requests the other Consumable Resources Created (produced) and destroyed (consumed) by a process Interrupts, signals, messages, and information in I/O buffers Deadlock may occur if a Receive message is blocking May take a rare combination of events to cause deadlock
Follow the Rules 26 Concurrency (13) System Model (Rules) Process must request (and be granted) a resource before using it. Process must release the resource when done. Why?? Deadlock A set of processes is in a deadlock state when every process in the set is waiting for an event that can only be caused by another process in the set. P2: holds R2, needs R3 P1: holds R1, needs R2 P4: needs R1 P3: holds R3, needs R1
Quiz 6.2 27 Concurrency (13) 1. 2. 3. What are the resources? Where is mutual exclusion needed? What is required for deadlock to occur?
Quiz 6.2 (solution) 28 Concurrency (13) 1. 2. 3. What are the resources? Where is mutual exclusion needed? What is required for deadlock to occur? ME
Joint Process Diagram 29 Concurrency (13) Progress of Q Impossible joint conditions are grayed out. 2 1 Release A Both P and Q have A A Release B Required Get A B P has B Q has A Q has A ? 5 Both P and Q have B P has B Required 4 Get B 6 3 Deadlock is only inevitable if the joint progress of the two processes creates a path that enters the fatal region. Progress of P Get A Get B Release A Release B A Required B Required
Joint Process Diagram 30 Concurrency (13) Progress of Q 2 1 3 Release A 6 Both P and Q have A A Release B Required Get A Both P and Q have B B Required 5 Get B 4 Progress of P Get A Release A Get B Release B No fatal region, as there are exit paths available. A B Required Required
Conditions of Deadlock 31 Concurrency (13) Necessary (but not sufficient) Mutual exclusion Everyone abides by the rules only one process may use a resource at a time. no process may access resource allocated to another. Hold-and-wait a process may hold allocated resources while awaiting assignment of other resources. No preemption no resource can be forced to free a resource. Circular wait (sufficient) a closed chain of processes exists, such that each process holds at least one resource needed by the next process in the chain (consequence of the first three conditions) Other conditions are necessary but not sufficient for deadlock - all four conditions must hold for deadlock - Unresolvable circular wait is the definition of deadlock!
Circular Wait 32 Concurrency (13) Resource A Process P1 Process P2 Resource B
Resource Allocation Graph 33 Concurrency (13) Deadlocks can be described using resource allocation graph. R1 R2 Vertices: circles are Processes, rectangles are Resources. P1 P2 P3 A directed edge from Pi to Rj indicates process Pi has requested an instance of resource Rj A directed edge from Rj to Pi indicates resource Rj has been allocated to process Pi R3 R4
Resource Allocation Graph 34 Concurrency (13) R1 R2 Is there a cycle (ie. some number of vertices connected in a closed chain)? If a graph contains no cycles, then no process in the system is deadlocked. P1 P2 P3 If the graph contains a cycle, deadlock MAY exist. R3 Yes Is there deadlock? R4
Deadlock? 35 Concurrency (13) P2 Is there a cycle? Yes R1 P1 P3 Is there deadlock? No R2 P4
Handling Deadlock 37 Concurrency (13) Four general approaches exist for dealing with deadlock. 1. Prevent deadlock by adopting a policy that eliminates one of the conditions. 2. Avoid deadlock by making the appropriate dynamic choices based on the current state of resource allocation. 3. Detect Deadlock by checking whether conditions 1 through 4 hold and take action to recover. 4. Ignore Deadlock System may hang, so??
