The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
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

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

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

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


    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


Suppose we allow the processes to take `turns'

while (alive) {
   while ( turn != 0 ) ;     // wait until turn = 0
   CS() ;                    // enter the critical section
   turn = 1 ;                // other process's turn

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

while (alive) {
   while ( flag1 ) ;   // wait until flag1 = false
   flag0 = TRUE ;
   CS() ;
   flag0 = FALSE ;

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)

while (alive) {
   flag0 = TRUE ;
   while ( flag1 ) ;   // wait until flag1 = false
   CS() ;
   flag0 = FALSE ;

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")

while (alive) {
   flag0 = TRUE ;
   turn = 1 ;
   while ( flag1 && turn == 1 ) ;   // wait until flag1 = FALSE 
   CS() ;                           //            or turn = 0
   flag0 = FALSE ;

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
exit:    lock = FALSE;

How it works:

Suppose we hit `entry' and lock is
posted Feb 1, 2016 in Operating System by Active (3,293 points) | 118 views

1 Comment

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,430 questions
53,616 answers
70,892 users