01.10.
2010
Interprocess Types of Interaction
Communication between concurrent processes
resource sharing
communication
synchronization
Levels of Interaction Resource Sharing
mutual exclusion
interaction between processes on three levels two types of resources
processes not aware of each other (competing) can be used by more than one process at a time (e.g.
using system resources (moderated by operating system) reading from a file)
can be used by only one process at a time
processes indirectly aware of each other (sharing)
due to physical constraints (e.g. some I/O units)
resource sharing (through mutual exclusion and
if the actions of pne process interfered with those of another
synchronization) (e.g. writing to a shared memory location)
processes directly aware of each other synchronization
(communicating)
a process needs to proceed after another process
completes some actions
Example Example – Possible Errors
2 processes: Observer and Reporter observer reporter
counter shared variable counter 6
observer: reporter:
while TRUE { while TRUE { print (6)
observe; print_counter;
counter ++; counter=0; counter 7 7. is lost!
} }
counter 0
1
01.10.2010
Example – Possible Errors Example – Possible Errors
counter++ LOAD ACC, COUNTER P1: k=0 (intial value)
INC ACC while TRUE what about the values of k
SAVE COUNTER,ACC k=k+1; depending on the order
of P1 and P2 executions?
Race:
when processes access a shared variable
P2:
outcome depends on order and running speed of processes while TRUE SOLUTION: mutual
may be different for different runs k=k+1; exclusion
Sharing Synchronization
two types of sharing: programs should not be dependent on
READ (no need for mutual exclusion) running order of processes
WRITE (mutual exclusion needed) programs working together may need to be
for consistency synchronized at some points
mutual exclusion e.g. a program uses output calculated by another
synchronization program
Mutual Exclusion Example
P2:
critical section (CS): Part of code in a process in
P1: while TRUE {
which operations on shared resources are
<non-CS>
performed. mx_begin
while TRUE {
<CS ops>
<non-CS>
mx_end
mutual exclusion: only one process can execute a mx_begin <non-CS>
CS for a resource at a time <CS ops> }
mx_end
<non-CS>
}
2
01.10.2010
Mutual Exclusion – Possible
Problems
Mutual Exclusion
deadlock
more than one process requires the same resources mx_begin
each process does not release the resource required by the any processes in its CS which have not executed
other mx_end ?
Example: 3 processes and 3 resources if NOT
allow process to proceed into CS
P
1
R
1
leave mark for other processes
req(R1) req(R2)
P1() P2() P3()
req(R1); req(R2); req(R3);
mx_end
R P P R req(R2); req(R3); req(R1); allow any process waiting to go into CS to proceed
3 3 req(R3) 2 2
if not leave mark (empty)
Mutual Exclusion Implementation Mutual Exclusion Solutions
only one process may be in its CS
if a process wants to enter its CS and if there are no software based solutions
others executing their CS, it shouldn't wait
any process not executing its CS should not prevent hardware based solutions
another process from entering its own CS software and hardware based solutions
no assumptions should be made about the order and
speed of execution of processes
no process should stay in its CS indefinitely
no process should wait to enter its own CS indefinitely
A Software Based Solution A Software Based Solution
use a flag that shows whether a process is in its
CS or not: busy a possible error
busy TRUE : process in CS busy is also a shared variable!
busy FALSE : no process in CS Example:
- P1 checks and finds busy=FALSE
mx_begin: while (busy); - P1 interrupted
busy = TRUE; - P2 checks and finds busy=FALSE
- both P1 and P2 enter CS
wait until process in CS is finished
enter CS
mx_end: busy = FALSE;
3
01.10.2010
Solutions Requiring Busy Waiting Solutions Requiring Busy Waiting
global variable turn = 1;
Process 1: Process 2:
use up CPU time
local variables local variables
works properly but has limitations:
my_turn=1; my_turn=2;
processes enter their CS in turn
others_turn=2;
others_turn=1; depends on speed of process execution
depends on number of processes
mx_begin: while (turn != my_turn);
mx_end : turn = others_turn;
Solutions Requiring Busy Waiting Peterson Algorithm
shared variables:
first correct solution: Dekker algorithm req_1, req_2: bool and initialized to FALSE
turn: integer and initialized to “P1” or “P2”
Peterson algorithm (1981) P1:
similar approach mx_begin:
req_1 = TRUE;
simpler
turn = P2;
while (req_2 && turn==P2);
< CS >
mx_end: req_1 = FALSE;
Peterson Algorithm Peterson Algorithm
different scenarios: (different scenarios cntd.):
P1 is active, P2 is passive P1 and P2 want to enter CS at the same time
req_1=TRUE and turn=P2
req_2=FALSE so P1 proceeds after while loop P1: P2:
req_1=TRUE; req_2=TRUE;
P1 in CS, P2 wants to enter CS
turn=P2; turn=P1;
req_2=TRUE and turn=P1;
req_1=TRUE so P2 waits in while loop
P2 continues after P1 executes max_end order depends on which process assigns value to the turn
variable first.
4
01.10.2010
Hardware Based Solutions Hardware Based Solutions
with uninterruptable machine code instructions test_and_set(a): cc a
completed in one machine cycle a TRUE
e.g.: test_and_set with one machine instruction, contents of “a” copied into
busy waiting used condition code register and “a” is assigned TRUE
mx_begin: test_and_set(busy);
when a process exits CS, no mechanism to
determine which other process enters next while (cc) {
indefinite waiting possible test_and_set(busy);
disabling interrupts }
mx_end: busy=FALSE;
interferes with scheduling algorithm of operating
system busy: shared variable
cc: local condition code
Semaphores Semaphores
hardware and software based solution s: semaphore variable
no busy waiting special operations:
does not waste CPU time P (wait): when entering CS: mutex_begin
semaphore is a special variable V (signal): when leaving CS: mutex_end
only access through using two special operations P(s): V(s):
special operations cannot be interrupted if (s > 0) if(anyone_waiting_on_s)
operating system carries out special operations s=s-1; activate_next_in_line;
else else
wait_on_s; s=s+1;
Semaphores Example: Observer – Reporter
global variables:
counter: integer;
take on integer values (>=0) sem: semaphore;
created through a special system call process P1: process P2:
is assigned an initial value observe; ...
P(sem); P(sem);
binary semaphore: counter++; print(counter);
V(sem); counter=0;
can be 0/1 .... V(sem);
used for CS main_program:
counting semaphore: sem=1; counter=0;
activate(P1);
can be integers >=0 activate(P2);
5
01.10.2010
Example: Observer – Reporter
Synchronization with Semaphores
sample run:
P1: P(sem) ... sem=0; a process may require an event to proceed –
P2: P(sem) ... sem=0 so P2 is suspended process is suspended
P1: V(sem) ... P2 is waiting for sem; activate P2 e.g. process waiting for input
P2: V(sem) ... no one waiting; sem=1 another process detecting the occurence of
event wakes up suspended process
“suspend – wake-up” synchronization
Synchronization with Semaphores Semaphores
solution:
event:semaphore; event=0;
Initial value for semaphore:
=1 for mutual exclusion
process P1: process P2:
... ... =0 for synchronization
P(event); ...
... V(event);
...
more than two processes may be
synchronized
Semaphores
possible deadlock scenario:
x, y: semaphore;
x=1; y=1;
process 1: process 2: Pay
... ... attention to
P(x); P(y); the order of
P and V!
... ...
P(y); P(x);
... ...
V(x); V(y);
V(y); V(x);
... ...
