CSE 130 Lecture Notes, June 5, 2002

CSE130 LECTURE NOTES

June 5, 2002

ANNOUNCEMENTS

(1) Remember that the final is in this room, at 7pm next Monday.

(2) CAPE should be coming today to do their evaluation.

(3) From the Engineering Student Services Staff: It's not too late to sign up for the 2002 JACOBS SCHOOL OF ENGINEERING GRADUATION and RECOGNITION BANQUET! We've extended the reservation deadline to Monday, June 10, 2002.

When: Saturday, June 15, 2002, 6:00pm (Reception), 7:00pm (Dinner & Program)
Where: San Diego Marriott-La Jolla
Cost: $15/student/faculty/staff, $25/guest

Make your reservation on-line now at http://www.jacobsschool.ucsd.edu/ESS/GradBanquet/ or come to the Engineering Student Services Office at EBU-I, Room 1400 (Open M-F, 8-12pm & 1-4:30pm). For more information Call (858) 534-6105 or Email: gradbanquet@soe.ucsd.edu.

CALL-BY-ENVIRONMENT VERSUS CALL-BY-MACRO

All the other parameter-passing methods are basically similar: they work by initializing the formal parameters as local names in an environment used for executing the called block. They are all variants of "call-by-environment."

Practical programming languages use call-by-environment, but call-by-macro is theoretically important because

it is a common informal way to reason about invocation: simulating mentally step-by-step what the function body does with the actual arguments in place of the formal parameters
it is used in the lambda calculus, which is the mathematically most abstract programming language
it is formally simpler: it doesn't introduce these complex objects called "environments"
it does appear in practical languages under the guise of macros.

In Algol 60, call-by-macro is called call-by-name, but implemented using higher-order functions (i.e. using function arguments).

Consider the pseudo-Pascal summation function using call-by-macro from before. This can be implemented using call-by-value with function arguments:

function sum (lo,hi:int; ref k:int; f:void->real);
    var s: real := 0;
begin
    for k := lo to hi do s := s + f();
    return s
end;
function f(): real;
begin
    return a[j]*b[j];
end;

The lesson to learn here is that higher-order functions give the functionality of call-by-macro.

HIGH-LEVEL CONCURRENT PROGRAMMING: TASKS

From a machine-level point of view, a process is one series of instructions being executed. From a high-level PL point of view, we will see that a process is similar to an object.

Processes have state: the values stored in the CPU registers, plus perhaps memory. Changing between processes is expensive because the state of one process has to be saved and the state of another has to be restored.

A "thread" is a lightweight process, i.e. one with only a small amount of state that needs to be saved and restored. Advantage: switching between lightweight processes is fast. The definition used by many authors is that each process has its own address space, while threads share memory, i.e. share one address space.

We'll look at tasks in Ada to show how how a process can be made similar to other high-level programming constructs.

TASKS IN ADA

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

A task is like an object and an entry is like a method for an object. Entries can have "in" and "out" parameters.

task buffer is
entry give (x: in item);
entry take (x: out item);
end buffer;

A task body consists of code that can "accept" entry calls at certain times during execution. The code below can only accept a "take" immediately after accepting a "give":

task body buffer is
    it: item;
begin
    loop
        accept give (x: in item) do
            it := x;
        end give;
        accept take (x: out item) do
            x := it;
        end take;
    end loop;
end buffer;

A MORE COMPLICATED EXAMPLE IN ADA

Here is the previous 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.

With message passing, threads send and receive data. Note that the word "message" here does not imply all of object-oriented programming. Sending is like writing, and receiving is like reading.

With shared memory, two (or more threads) use the same variable. To communicate, one thread assigns a new value to a variable, and another thread uses the value of the variable.

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:

Atomic

Consistent

Isolated

Durable

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.