The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
101 views
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
posted Feb 1, 2016 in Operating System by Active (3,279 points) | 101 views
0
Like
0
Love
0
Haha
0
Wow
0
Angry
0
Sad

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

44,317 questions
49,814 answers
164,546 comments
65,866 users