Concurrent processes
INTRODUCTION,
PARALLEL PROCESSING, A CONTROL STRUCTURE FOR
INDICATING PARALLELISM,
THE PRODUCER / CONSUMER PROBLEM,,
MUTUAL EXCLUSION, THE CRITICAL SECTION PROBLEM,
SEMAPHORES, CLASSICAL PROBLEMS IN CONCURRENCY,
INTER PROCESS COMMUNICATION, PROCESS GENERATION,
PROCESS SCHEDULING.
Process Concurrency and synchronization
Concurrent Processes
2
Precedence constraints within a program
S1 : a = x + y;
S2 : b = z + 1;
S3 : c = a - b;
S4 : w = c + 1;
What is the precedence constraint in above set of
instructions?
Process Concurrency and synchronization
Precedence Graph
3
A directed acyclic graph
Nodes corresponds to individual statement
An edge from node Si to node Sj means that Sj can be executed after Si has
completed.
S1
S2 S3 S4
S5
S6
Process Concurrency and synchronization
Bernstein Conditions
4
If
Ri = Read/input set of process Si
Wi = Write/output set of Si , then condition of COCURRENCY are
(BERNSTEIN CONDITIONS)
R(S1) ∩W(S2) = {}, S0
W(S1) ∩R(S2) = {}, AND
W(S1) ∩W(S2) = {}.
S1 S2 S3
S4
S5
Process Concurrency and synchronization
The Fork & Join Constructs
5
Specifications of Precedence Graph
The Fork & Join Constructs
FORK and JOIN were introduced in 1966 by Dennis and VanHorne. Though Fork has
the same name as an operation in Unix, you should think of them as totally
unrelated.
When the statement:
Fork(label); is executed by a thread of control, a second thread of control is started
from the statement with the specified label. The two threads execute concurrently.
When the statement:
Join(count); is executed, where count is an integer variable, the value of count is
decremented. If the resulting value is positive the executing thread is terminated.
Process Concurrency and synchronization
Fork & Join Constructs
6
Begin
Count CNT =2;
S1;
Fork L1; L1 : S3;
S2; Goto L2;
L2 : join (CNT);
S4;
End.
Process Concurrency and synchronization
More Fork & Join (Home Assignment)
7
Process Concurrency and synchronization
Cobegin – Coend (Parbegin– Parend)
8
Programming construct for
specifying concurrency, which is not
as AWKWARD as Fork – Join.
Does not create problems with Goto
(label) statements for fork – join.
Begin
S0;
Parbegin (cobegin)
S1; S2; S3; - - - Sn-1;
Parend;(coend)
Sn;
End.
Process Concurrency and synchronization
Write using parbegin – parend construct
9
Begin
S1;
cobegin
S3;
begin
S2;
S4;
cobegin S5; S6; coend;
end;
coend;
S7;
end.
Comment if you can specify the other precedence
graph in slide (9) in terms of parbegin – parend
construct.
Process Concurrency and synchronization
Critical Section?
Consumer Producer Example
10
#define BUFSZ 10
typedef struct { . . . } item;
item buffer[BUFSZ];
int in = 0;
int out = 0; BUSY WAITING
int counter = 0;
Producer Consumer
item nextProduced; item nextConsumed;
while (TRUE) { while (TRUE) {
while (counter = = BUFSZ); while (counter = = 0) ;
buffer[in] = nextProduced; nextConsumed = buffer[out];
in = (in + 1) % BUFSZ; out = (out + 1) % BUFSZ;
counter++; counter- -;
} }
Must protect the “counter write” critical section.
Process Concurrency and synchronization
Counter increment steps
11
Producer process Consumer Process
increments the counter decrements the counter
Counter ++ Counter - -
Register 1 = counter; Register 2 = counter;
Register 1 = Register 1+ 1; Register 2 = Register 2 - 1;
Counter = Register 1; Counter = Register 2;
Interrupt for context switch can occur at any instance, i.e.,
after any instruction for above two process running
concurrently.
Process Concurrency and synchronization
Bounded Buffer Example
12
If both the producer and consumer attempt to update the buffer concurrently,
the assembly language statements may get interleaved.
Interleaving depends upon how the producer and consumer processes are
scheduled.
Assume counter is initially 5. One interleaving of statements is:
producer: registeer1 = counter(register1 = 5)
producer: register1 = register1 + 1 (register1 = 6)
consumer: register2 = counter(register2 = 5)
consumer: register2 = register2 – 1 (register2 = 4)
producer: counter = register1 (counter = 6)
consumer: counter = register2 (counter = 4)
The value of count may be either 4 or 6, where the correct result should be 5.
Process Concurrency and synchronization
Solution to Critical Section
13
1. Mutual Exclusion - If process Pi is executing in its critical section,
then no other processes can be executing in their critical sections
2. Progress - If no process is executing in its critical section and there
exist some processes that wish to enter their critical section, then
the selection of the processes that will enter the critical section next
cannot be postponed indefinitely
3. Bounded Waiting - A bound must exist on the number of times
that other processes are allowed to enter their critical sections after
a process has made a request to enter its critical section and before
that request is granted
Assume that each process executes at a nonzero speed
No assumption concerning relative speed of the N processes
Process Concurrency and synchronization
General structure of a process
14
repeat
entry section
critical section
exit section
reminder section
until false
Process Concurrency and synchronization
Solution to Critical Section
15
Var turn = {0..1}; BUSY WAITING
Process 0 Process 1
while turn ≠ 0 do {}; while turn ≠ 1 do {};
CRITICAL SECTION CRITICAL SECTION
turn = 1; turn = 0;
REMAINDR SECTION REMAINDR SECTION
Begin
turn = 0 or 1;
Cobegin P0; P1; Coend; Problematic. HOW?
End.
Process Concurrency and synchronization
Solution to Critical Section
16
Var flag: array [0..1] of Boolean;
Process 0 Process 1
while flag[1] do {}; while flag[0] do {};
flag [0] = true; flag [1] = true;
CRITICAL SECTION CRITICAL SECTION
flag[0] = false; flag[1] = false;
REMAINDR SECTION REMAINDR SECTION
Still problematic. HOW?
Process Concurrency and synchronization
Peterson’s Algorithm for two process
17
var flag: array {0..1] of Boolean; begin flag[0] = false; flag[1] = false;
turn : 0..1; turn = 1;
parbegin P0; P1 parrend end
Process 0 Process 1
|| ||
begin begin
repeat repeat
flag [0] = true; flag [1] = true;
turn = 1; turn = 0;
while flag[1] and turn = 1 do {}; while flag[0] and turn = 0 do {};
CRITICAL SECTION CRITICAL SECTION
flag[0] = false; flag[1] = false;
REMAINDR SECTION REMAINDR SECTION
forever forever
end; end;
Process Concurrency and synchronization
Semaphores (Dijkstra 1930-2002)
18
Born in Rotterdam, The Netherlands
1972 recipient of the ACM Turing Award
Responsible for
The idea of building operating systems as explicitly synchronized
sequential processes
The formal development of computer programs
Best known for
His efficient shortest path algorithm
Having designed and coded the first Algol 60 compiler.
Famous campaign for the abolition of the GOTO statement
Slide taken with thanks from Silberschatz, Galvin & Gagne
Process Concurrency and synchronization
Semaphore
19
Synchronization tool that does not require busy waiting
Atomic operations
Semaphore S – integer variable
Two standard operations modify S: wait() and signal()
Originally called P() and V()
Also called down() and up()
The value of S can only be accessed through wait() and
signal()
(P) wait (S) { (V) signal (S) {
while S <= 0 do; S++;
S--; }
}
Slide taken with thanks from Silberschatz, Galvin & Gagne
Process Concurrency and synchronization
Semaphore Implementation with no Busy waiting
With each semaphore there is an associated waiting queue.
typedef struct{
int value;
struct process *list;
} semaphore;
Two operations on processes:
block – place the process invoking the operation on the
appropriate waiting queue.
wakeup – remove one of processes in the waiting queue and
place it in the ready queue.
Slide taken with thanks from Silberschatz, Galvin & Gagne
Process Concurrency and synchronization 20
Semaphore Implementation with no Busy waiting (Cont.)
Implementation of wait:
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
block();
}
}
Implementation of signal:
signal(semaphore *S) {
S->value++;
if (S->value > 0) {
remove a process P from S->list;
wakeup(P);
}
}
Slide taken with thanks from Silberschatz, Galvin & Gagne
Process Concurrency and synchronization 21
Semaphore as General Synchronization Tool
Counting semaphore – integer value can range over an unrestricted domain
Binary semaphore – integer value can range only between 0
and 1; can be simpler to implement
Also known as mutex locks
Can implement a counting semaphore S as a binary semaphore
Provides mutual exclusion
Semaphore mutex; // initialized to 1
do {
wait (mutex);
// Critical Section
signal (mutex);
// remainder section
} while (TRUE);
Slide taken with thanks from Silberschatz, Galvin & Gagne
Process Concurrency and synchronization 22
BOUNDED BUFFER, PRODUCER – CONSUMER SCENARIO
PRODUCER :
anytype item;
Repeat
{
INITIALIZATION: /* produce something */
item = produce();
shared binary semaphore mutex = 1; /* wait for an empty space */
wait(empty);
shared counting semaphore empty = MAX; /* store the item */
wait(mutex);
shared counting semaphore full = 0;
buffer[in] = item; in = in + 1 mod
shared anytype buffer[MAX]; MAX;
count = count + 1;
shared int in, out, count; signal(mutex);
/* report the new full slot */
signal(full);
}
Process Concurrency and synchronization 23 until done;
Bounded Buffer Solution
24
Producer: Consumer:
do { do {
// produce an item in nextp wait (full);
wait (empty); wait (mutex);
wait (mutex); // remove an item from buffer to nextc
// add the item to the buffer signal (mutex);
signal (mutex); signal (empty);
signal (full);
// consume the item in nextc
} while (TRUE);
} while (TRUE);
Slide taken with thanks from Silberschatz, Galvin & Gagne
Process Concurrency and synchronization
Uses of Semaphore for Process Synchronization
P1
a b
c
P2 P3
Write a concurrent construct
e f
d g for
P4
the shown precedence graph.
P5 h i P6
j
k l
P7
Process Concurrency and synchronization 25
Uses of Semaphore for Process Synchronization
Var a, b, c, d, e, f, g, h, I, j, k, l = 0 : Boolean / Binary Semaphore variables
Parbegin
{
{ P1; V(a); V(b); V(c);}
{ P(a); P2; V(d); V(e);}
{ P(b); P3; V(f); V(g);}
{ P(c); P(e); P(f); P4; V(h); V(i); V(j);}
{ P(d); P(h); P5; V(k);}
{ P(i); P(g); P6; V(l);}
{ P(j); P(k); P(l); P7; }
}
Parend.
Process Concurrency and synchronization 26
Hardware Solution to Critical Section
27
Remember the SOFTWARE INTERRUPTS of a
microprocessor?
Interrupt ENABLING and DISABLING of
ASSEMBLY language?
ARE these assembly language instructions
ATOMIC?
CAN these assembly language instructs be used
for achieving MUTUAL EXCLUSION?
Process Concurrency and synchronization
HARDWARE INSTRUCTIONS
28
Process Concurrency and synchronization
29
Process Concurrency and synchronization
30
Process Concurrency and synchronization
Dining Philosophers Problem
31
Process Concurrency and synchronization
The Problem
32
Devise a ritual (algorithm) that will allow the
philosophers to eat.
No two philosophers can use the same fork at the same time (mutual
exclusion)
No philosopher must starve to death (avoid deadlock and starvation
… literally!)
Slide taken with thanks from Silberschatz, Galvin & Gagne
Process Concurrency and synchronization
Avoiding deadlock (only 4 philosophers)
33
Process Concurrency and synchronization Slide taken with thanks from Silberschatz, Galvin & Gagne
Dining Philosophers: Solution
34
Process Concurrency and synchronization Slide taken with thanks from Silberschatz, Galvin & Gagne
35
Process Concurrency and synchronization Slide taken with thanks from Silberschatz, Galvin & Gagne
What's Wrong?
36
Process Concurrency and synchronization
Assignment 2
37
1. There are five unsuccessful (incomplete) attempt to solve Critical Section problem is
given in your book, we have discussed here only two. Write the remaining three and
explain clearly why they are not the good solutions.
2. Give the Peterson’s solution to Critical Section and explain how it meets mutual
exclusion, progress and bounded waiting criteria.
3. Explain what are Monitors in brief. Study Reader-Writer’s problem and give its
solutions using Monitors.
Process Concurrency and synchronization
38
End of the Unit
Process Concurrency and synchronization