CSE130 LECTURE NOTES

December 8, 1999
 
 

ADMINISTRATION

See the main web page for announcements regarding Friday and Monday sections.
 
 

A MORE COMPLICATED EXAMPLE IN ADA

Here is last Monday's example extended to allow the producer to get ahead of the consumer, using a buffer of items that have been produced but not yet consumed.

Remember that in Ada, a task specification looks like an abstract type (ADT) specification. The outside world (i.e. any other task) interacts with a task by calling its "entries".

task body buffer is
    size: constant integer := 10;
    b: array (1..size) of item;
    n: integer range 0..size := 0;
    inloc, outloc: integer range 1..size := 1;
begin
    loop
        select
            when n < size =>
                accept give (x: in item) do
                    b(inloc) := x;
                end give;
                n := n+1;
                inloc := (inloc mod size) + 1;
            or when n > 0 =>
                accept take (x: out item) do
                    x := b(outloc);
                end take;
                n := n-1;
                outloc := (outloc mod size) + 1;
        end select;
    end loop;
end buffer;
Note that "off by one" mistakes are easy in the code above. Ada helps in detecting these mistakes by allowing precise, explicit subranges for integer variables.
 
 

THE "RENDEZVOUS" IDEA

"Rendezvous" is a French word that means "appointment". The idea is that when two threads want to communicate, they need to set up an appointment, i.e. they need to synchronize.

Synchronization means reaching the same point at the same time. One thread must do a "send" at the same time (or immediately before) the other does a "receive".

An Ada rendezvous is like a telephone call: during the rendezvous the caller and the callee are synchronized. The caller chooses the callee and knows which task this is. The callee does not know who the caller is.

A caller can be a hardware interrupt or a trap (i.e. an interrupt generated by low-level software).

Execution of the caller of an entry is suspended while the callee is executing code between the accept line and the corresponding end.

"Mutual exclusion" means that only one thread at a time can have access to a resource.  Concurrent programming always involves mutual exclusion.  Mutual exclusion can be guaranteed if a resource is only manipulated inside accept blocks.
 
 

TASK TYPES

Since a task is similar to an object, it makes sense to have sets of tasks, which are similar to classes.  It also makes sense to have pointers to tasks, and to create tasks dynamically, i.e. at run-time.  In Ada we can write
task type printer is
    entry init(id: string);
    entry print(s: string);
end printer;

task body printer is
    ...
begin
    accept init(id: string) do
        ...
    end init;
    ...
end printer;

type printerptr is access printer;
p := new printer;  p.init("123.456.000.000");
q := new printer;

Note that in Ada pointers are dereferenced automatically when this makes sense from the syntactic context.
 
 

SHARED MEMORY VERSUS PASSING MESSAGES

The Ada approach to tasking is high-level.  It generalizes both shared-memory and message-passing approaches to concurrent programming. As a high-level approach to parallel programming, it is not clear how to implement Ada tasking very efficiently.  On different computers, the most efficient implementation method may be very different.

In general, message-passing can be implemented using shared memory: first the sender sets the value of a variable to be the message, then the receiver uses the variable.

Conversely, shared memory can be simulated using message-passing, with a third thread.
 
 

MUTUAL EXCLUSION

Mutual exclusion is the foundation of correct concurrent programming.  With shared memory, if two processes try to make an assignment to a variable at the same time, the result would be chaos.

An operation is called atomic if it is guaranteed to be performed "all or nothing", i.e. with mutual exclusion.

Typically the most primitive concurrent programming operation, implemented in hardware, is "test and set". In pseudo-code this operation on a shared register X is

if X == 0 then { X := 1; return 0 }
else return 1
"Test and set" is implemented by the CPU in hardware to be atomic. It can be used to build more complicated atomic operations.
 
 

THE DATABASES APPROACH TO HIGH-LEVEL CONCURRENT PROGRAMMING

Compare to the ACID properties of database transactions: If the database system guarantees that a piece of code labeled as a transaction has the atomic, isolated, and durable properties.  The program chooses which pieces of code are large enough to be considered consistent.  S/he encloises these blocks with keywords like begin and commit.  Anywhere inside the block the programmer can write rollback.

See The four ACID properties by Jim Gray.
 
 

Copyright (c) 1999 by Charles Elkan.