Transcript concurrency




Read about Therac-25 at
[http://www.ddj.com/cpp/184401630]
[http://sunnyday.mit.edu/papers/therac.pdf]



IPC (Interprocess Communication) mechanisms
[http://www.faqs.org/docs/kernel_2_4/lki-5.html]
[http://www.comptechdoc.org/os/linux/programming
/linux_pgcomm.html]




Processes are concurrent if they exist at the same
time.
Processes are asynchronous if NO timing
assumptions can be made regarding events that each
does. i.e. independent of each other.
Problems can occur if they access shared data.
Perhaps the most visible application of concurrency
is in gaming.
Example:

Two processes




one counts events
one logs the count at regular intervals
P1 (ex: count cars that pass, count lines of output)
P2 report counts at regular intervals (timer based)
P1 (Observer)
loop
(1)
end loop



P2 (Reporter)
loop
wait for event
x=x+1
(2)
(3)
end loop
sleep(time t)
print x
reset x to 0
Suppose x is 99 and is shared by P1 and P2
Order of events:1-2-3 or 2-3-1  works as expected
Order of events 2-1-3  last event is unreported


Worse scenario
Could get the following reports:
93 – 95 – 91 – 93 – 181 – 92 – 95.

What happened?
P1 (Observer)
loop
loop
wait for event
x=x+1
(1)
end loop




(2)
(3)
end loop
sleep(time t)
print x
reset x to 0
x=x+1 could be translated into machine code as
(1a)
move, Reg x
(1b)
add, Reg
1
(1c)
store, Reg x


P2 (Reporter)
Order of events is 1a-2-3-1b-1c
Resetting of x to 0 is lost!!
Solution:




if a process is modifying a shared variable, no other
process should access it.
This is called Mutual Exclusion.
A portion of code that accesses the shared data is
called a critical section.
No two processes should be executing their
respective critical sections at the same time.

Solution to the critical section problem must satisfy:



Mutual exclusion
Progress: Don’t wait if not necessary
Bounded waiting: to prevent starvation.

Need to implement entry and exit logic for
concurrent programs as shown:
While (1)
{
Entry section
Critical section
Exit section
Non critical section
}



Web site contains demos programs in Java that show
attempts at Mutual Exclusion among two or more
threads.
NOTE: Section 5.7 discusses a little about Java
threads and thread scheduling.
Mutual Exclusion. Just establishes the framework
and provides a chance to discuss Java Threads.
Algorithm_1




Enforces mutual exclusion
Does not satisfy the progress rule
forces threads to alternate entries into critical
sections
Thus, a thread must wait if it is not its turn.
Algorithm_2




Enforces mutual exclusion
Processes not forced to alternate
can result in deadlock
though may need to use a small time value to show
this.
Algorithm_3.





This is the book's Peterson's Solution implemented
in Java.
Enforces mutual exclusion
Enforces the progress rule
Works for 2 processes
Does not scale to more than 2 processes.
n-process mutual exclusion algorithm.
Developed by Edsgar Dijkstra in 1965.
shared data
status: array [0..n-1] of (idle, entering, inside)
turn : 0..n-1
enteringCriticalSection (for process i)
Repeat
status[i] = entering
while turn  i do
if (status[turn] == idle)
turn = i
status[i] = inside
j=0
while (j < n) and ( (j == i) or status[j]  inside)
j = j+1
until j == n
leavingCriticalSection(for process i)
status[i] = idle




See Dekkers in the collection of java projects.
This solution is subject to starvation or indefinite
postponement.
Other algorithms that improve on this have been
written by Donald Knuth, DeBruijn,
Eisenberg/McGuire and include Lamport’s Bakery
algorithm.
Should be able to find examples on the Internet.
Hardware Solutions:

testandset(a, b):



Implemented on early IBM machines.
This command sets a to b and sets b to true.
It’s atomic (uninterruptible) - a machine command.
enteringCriticalSection
testandset(status, inside)
do while (status)
testandset(status, inside)
leavingCriticalSection
inside = false

Many modern systems provide some type of
hardware or system level instructions to implement
Mutual Exclusion.



Project getAndSet and book figures 6.4 and 6.5 (page
216-217) simulate a hardware instruction with a Java
class.
The book example would lock up periodically
because the testandset method is not an
uninterruptible method. i.e. it is not a hardware
instruction.
However, it can be simulated by putting a public
synchronized qualifier on each Hardware Data
method. This means





Every java object has a lock.
Locks are generally ignored.
thread must own a lock to call any of the
synchronized methods.
If it does not then it waits in a queue until it can own
the lock.
Works much like a Monitor (discussed later).
Semaphores:




developed by Dijkstra in 1965
aid to synchronize processes and enforce mutual
exclusion.
name give to a device to control occupancy of
sections of railroad tracks.
A semaphore is a variable, s that can be operated on
only by two primitives (non-interruptible
commands)

Classic primitive operations:
P(s) (For the Dutch word Proberen meaning test)
If (s > 0) then s = s – 1
else wait until s > 0

Sometimes instead of a wait, the definition uses a
spinlock (busy wait loop). Book does this (p. 218)

Book uses acquire: that is, instead of writing P(s) the
book write s.acquire()
V(s) (For the Dutch word Verhogen meaning increment)
if a process is suspended, waiting on s, then wake it
else s = s + 1

If P(s) is defined using a spinlock then V(s) need only
increment the semaphore value (page 218)

Book uses release: That is, instead of writing V(s) the
book writes s.release()

binary semaphore


Value is 0 or 1
counting semaphore

Value can be any positive integer value.

To enforce Mutual exclusion
process code
:
:
P(s)
critical section
V(s)
:
:

Works for any number of processes
Java semaphores



Folder java semaphore shows a java semaphore
class from java.util.concurrent.Semaphore.
Similar to book figure 6.7.
Folder semaphore shows how a semaphore might be
implemented
Synchronization: The Producer/consumer
problem





Producer process creates or produces something
Consumer process uses or consumes something
Consumer cannot consume what has not been
produced
Producer cannot produce until the previous thing has
been consumed.
Their critical sections must alternate.
producer/consumer solution
Initially, set s=1 and t=0
Producer
Consumer
loop
:
:
P(s)
store result
V(t)
:
:
forever
loop
:
:
P(t)
get result
V(s)
:
:
forever
Bounded Buffer problem






Producer stores things into a circular queue
Consumer consumes from the circular queue
Each thing is consumed once
Producer cannot store more than the queue can hold
Consumer cannot use what has not yet been stored
there
Generalization of the producer/consumer problem

Solution is the same as that in the producerconsumer problem except initially set s=N (number
of buffers).
variations on the producer consumer problem:




Two producers (any order), one consumer, etc.
Two producers (fixed order), one consumer, etc.
Either of two producers (not both), one consumer,
etc.
Various combinations of one producer and two
consumers.
Readers and Writers problem



If a reader wants access, deny iff a writer is active
if a writer wants access, deny only iff a reader or
writer is active
The following solution is similar to book’s figures
6.15-6.19.
Writer
Reader
loop
:
:
P(wrt)
write result
V(wrt)
:
:
forever
loop
:
:
P(s)
readcount++
if readcount == 1
P(wrt)
V(s)
read data
P(s)
readcount-if readcount == 0
V(wrt)
V(s)
:
:
Forever

Linux Semaphores: see the Linux demos.