CMSC 421 Operating Systems Lecture Notes
(c) 1994 Howard E. Motteler
Interprocess Communication
===========================
(Section 2.2 in Tannenbaum)
Interprocess communication is fundamental to
- client-server applications (e.g. X windows)
- modern threaded operating system design
- many systems utilities in *any* OS (e.g. print spoolers)
- parallel processing
There are two general models of interprocess communication
- Shared memory with synchronization operations
- Message passing
Shared Memory with Synchronization Operations
==============================================
Shared memory must be managed carefully.
Example of 2 processes writing to a shared buffer:
Suppose that both the pointer p and the buffer it points to are
shared by processes P0 and P1
[ show pix of buffer and pointers ]
Suppose that
- P0 contains *p++ = a ;
- P1 contains *p++ = b ;
If both P0 and P1 execute these statements once, we expect
- p is incremented twice
- both a and b are saved (in some order)
The statement *p++ = a typically is implemented by at least
two machine instructions
- *p = a ;
- p++ ;
Consider the following possible sequence of events, where two
processes both copy data to a buffer
P0: P1:
: |
*p = a ; |
(context switch) time
: |
*p = b ; |
p++ ; V
:
(context switch)
p++ ;
:
The value `a' has been overwritten by `b'
This is sometimes called a "race condition," because the
final result depends on instruction timing
The *last* variable assigned "wins", i.e., gets saved
Mutual Exclusion in Critical Sections
--------------------------------------
A ``critical section'' is a part of a program that accesses
shared data
A program can have several critical sections for different
data
The ``mutual exclusion problem'' is to find a way to guarantee
that only one process at a time can access the shared data
A solution to the mutual exclusion problem should satisfy
1. `mutual exclusion:' only one process in a critical
section at a time
2. `progress:' a process outside a critical section can't
hold up others that want into that critical section
3. `bounded waiting:' a process waiting to enter a
critical section eventually gets in
4. `timing:' no assumptions are made about speed, timing,
or number of CPUs
Disabling Interrupts
--------------------
The simplest way to get mutual exclusion is to disable
interrupts when a processes enters a critical section
Without clock interrupts, there's no context switch
Problem: user would need special `enter' and `exit' critical
section commands, and these commands could be used to hog the
CPU
Disabling interrupts is sometimes useful for the kernel itself
Two-process software solutions to the Mutual Exclusion Problem
---------------------------------------------------------------
We will try and develop some code to ``guard'' a critical
section, so it can be shared by two processes
All these methods use ``busy waiting'' which is sometimes
unavoidable.
Simple Locks
------------
Suppose we have a shared `lock' variable, initially 0 and set to
1 whenever a process is in its CS
P0, P1:
while ( lock != 0 ) ; // wait until lock is 0
lock = 1 // set lock
CS() ; // enter the critical section
lock = 0 ; // reset lock
Problem:
P0: P1:
finds lock = 0,
(context switch)
finds lock = 0,
sets lock = 1,
enters CS
(context switch)
sets lock = 1,
enters CS
Mutual exclusion fails just as in our initial example
with the shared buffer
Alternation
-----------
Suppose we allow the processes to take `turns'
P0:
while (alive) {
while ( turn != 0 ) ; // wait until turn = 0
CS() ; // enter the critical section
turn = 1 ; // other process's turn
P1:
while (alive) {
while ( turn != 1 ) ; // wait until turn = 1
CS() ; // enter the critical section
turn = 0 ; // other process's turn
Mutual exclusion is satisfied, but `progress' fails
Suppose P0 enters and leaves its critical section
Then P0 cannot re-enter the critical section until P1 enters and
leaves its critical section
Flags for `in the CS'
---------------------
Idea: use two flags, both FALSE initially; flag0 is true
when P0 is in CS, flag 1 is true when P1 is in the CS
P0:
while (alive) {
while ( flag1 ) ; // wait until flag1 = false
flag0 = TRUE ;
CS() ;
flag0 = FALSE ;
}
P1:
while (alive) {
while ( flag0 ) ; // wait until flag0 = false
flag1 = TRUE ;
CS() ;
flag1 = FALSE ;
}
Mutual exclusion fails:
P0 does `while' test, finds flag1 = FALSE
P1 does `while' test, finds flag0 = FALSE
P0 sets flag0 = TRUE and enters CS
P1 sets flag1 = TRUE and enters CS
Flags for `want to enter' (similar to previous example)
--------------------------------------------------------
P0:
while (alive) {
flag0 = TRUE ;
while ( flag1 ) ; // wait until flag1 = false
CS() ;
flag0 = FALSE ;
}
P1:
while (alive) {
flag1 = TRUE ;
while ( flag0 ) ; // wait until flag0 = false
CS() ;
flag1 = FALSE ;
}
In this case `progress' fails
P0 sets flag0 = true
P1 sets flag1 = true
and both are stuck!
Peterson's Solution
-------------------
Use both a turn and flag variables; both flags are initially
FALSE. (Flags are for "want to enter")
P0:
while (alive) {
flag0 = TRUE ;
turn = 1 ;
while ( flag1 && turn == 1 ) ; // wait until flag1 = FALSE
CS() ; // or turn = 0
flag0 = FALSE ;
}
P1:
while (alive) {
flag1 = TRUE ;
turn = 0 ;
while ( flag0 && turn == 0 ) ; // wait until flag0 = FALSE
CS() ; // or turn = 1
flag1 = FALSE ;
}
Partial analysis
-Suppose P0 wants CS, and P1 is not in and does not want CS:
Then P0 enters CS, as flag1 is FALSE (part of progress)
-Suppose P0 wants CS, and P1 is in CS.
Then P0 waits for flag1 to go FALSE (mutual exclusion)
-Suppose both P0 and P1 want CS
Then the *first* one to set turn is the one to get in
(mutual exclusion & progress)
P0 flag0 = TRUE;
P1 flag1 = TRUE;
P0 turn = 1;
P1 turn = 0; P1 is second to set turn
P0 while (flag1 && turn == 1) false, turn is 0, so enter CS
P1 while (flag0 && turn == 0) true, loop until P0 leaves CS,
enter CS when flag0 goes FALSE
Must check bounded waiting:
- Suppose both P0 and P1 want to enter the CS
- P0 sets turn=1, P1 sets turn=0, P0 enters CS
- P1 is waiting in while loop for either flag0 to be FALSE,
or for turn to be 1
- Suppose P0 exits CS
- P0 sets flag0 = FALSE;
- Suppose P1 is unlucky
- P0 sets flag0 = TRUE before next P1 test
- P0 sets turn = 1
- P1 enters CS on turn = 1
Hardware for Critical Sections
-------------------------------
The `Test & Set Lock' Instruction
---------------------------------
Suppose we have a machine instruction TSL(v)
that `atomically' (i.e., uninterruptibly)
- sets v to TRUE
- returns the old value of v
Then it is very easy to protect a critical section with a
`lock' variable:
entry: while TSL(lock); // wait until lock is FALSE
CS();
exit: lock = FALSE;
How it works:
Suppose we hit `entry' and lock is
