Lecture Notes for Concurrent Programming

4 June 2002 - A Model for Concurrent Execution

1. concurrent traces

   1. a concurrent computation is set of sequential computations

   2. the sequential computations must interact, although not all the time

   3. let them execute at the same time, but what does that mean

   4. the interleaved model of concurrent execution

      1. roll an n-sided die, execute an action from the corresponding sequential computation

      2. however, any method may be possible, including sequential execution

2. two problems - interference and synchronization

   1. interference

      1. the critical references in two actions

         1. a write reference in one and a read or write reference in the other

         2. a read reference in one and a write reference in the other.

      2. two actions without critical references may be executed concurrently

         1. they are independent of one another - nothing in common

      3. two actions with one critical reference may be executed concurrently

         1. something in common, but so what

   2. synchronization

      1. the processes are coordinating to solve a problem - produce-consumer programs

      2. the coordination condition may involve critical references

3. two solutions - atomicity and waiting

   1. atomicity

      1. atomic actions do not coincide

      2. atomicity solves interference - atomic actions have no critical references

         1. an atomic action may read and write variables without interruption

      3. at most once actions appear to be atomic - they are limited, however

      4. actions in a execution trace should be atomic - the granularity will vary

         1. the finer the granularity, the greater the concurrency

         2. the larger the granularity, the easier to design

      5. angle brackets <> enclose an atomic action

   2. condition waiting

      1. the wait B statement - execution does not pass until B is true

      2. think of it as while (B) ; but more efficient (spin looping)

      3. B may contain critical references (may? probably!)

4. the await statement - combine synchronization and atomiticiy

   1. concurrent programs need to

      1. creating larger-grain atomic actions

      2. wait for other processes

   2. examples

      1. the atm problem - moving money from savings to checking

      2. manipulating a linked list

   3. the await statement provides both atomicity and synchronization

      1. <wait b; s>

         1. atomically evaluate b

         2. if b is true, execute s in the same atomic action; go on to the following statement

         3. if b is false, abandon execution and remain at the await.

      2. the delay condition wait b indicates synchronization - note the atomic execution

      3. angle brackets <> indicate atomic execution

         1. without the delay condition the await statement represents unconditional atomic execution

5. scheduling - which shall be next

   1. the scheduler determines which process gets to execute next

   2. fairness - every process gets to execute

   3. eligible statements - conditional and unconditional

   4. unconditional fairness - all unconditional atomic actions are eventually executed

   5. weak fairness (justice) - always enabled conditional atomic actions are eventually executed

   6. strong fairness - infinitely enabled conditional atomic actions are eventually executed

   7. unconditional is simple and not useful; strong is hard and useful

This page last modified on 10 June 2002.