Ada Rendezvous

- by Wen Gong

Be sure to look at the PostScript file that contains additional information.

Ada uses either monitors or a mechanism called rendezvous to achieve its synchronization. Ada rendezvous is introduced by C. A. R. Hoare in Communicating Sequential Processes (CSP).

In Ada, concurrent processes are called tasks. Normally, there is a task called coordinating task, which consists of local variables and routines that access shared resources. Other tasks access shared resources through entry calls to the coordinating task.

Synchronization in rendezvous mechanism is achieved by blocking. A task making an entry call to another task is blocked until its corresponding rendezvous occurs. An Ada rendezvous occurs when control reaches an accept statement in a task, and another task executes the corresponding entry call statement. At this time, the statements enclosed by accept statement in one task are executed. When control reaches the end of that accept statement, the task making entry call is unblocked.

An ada task has the following structure:
Task Specification
	task [type] <name> is
	entry specification
	end;

Task Body
	task body <name> is
	Declaration of local variables
	begin
	list of statements
	exceptions
	exception handlers
	end;

An entry in a task is implemented through accept statement. The format of an accept statement is similar to a procedure in Pascal programming language. The syntax of an accept statement is:

	accept <entry name> (<formal parameters>) do
		body of the accept statement
	end <entry name>;

Accept statements can only appear in task body. Some task may not contain any accept statements at all. To make an entry call for an accept statement B in task A, caller does B.A (<list of actual parameters>).

Accept statements are executed in sequential order in a task. The order of execution can be changed by using Select statements. Select statement in Ada is like an alternative command of CSP. It allows a group of accept statements to be executed in any order. There are three types of select statements, which are: select_wait, conditional_entry_call, and timed_entry_call. The syntax of a select_ wait statement is:

	select_statement := select <select_alternative>
		{ or <select_alternative> } 
		[else <statements> }
		end select;
	select_alternative := [when <condition> = >]
		<accept_statement> {<list of parameters>}

<condition> here can be referred as a guard -- accept statement is not executed if the condition is not true. When the condition is true, the accept statement is said to be Open. Only when an accept statement is open, and rendezvous occurs, can the accept statement be executed.

A select statement is executed in the following manner:

All the guards are evaluated to determine what accept statements are open;
If rendezvous is possible for an open statement, that accept statement is selected for execution; If more than one statement can be selected, then one of them is randomly chosen for execution;
If no accept statement can be executed, "else..." is executed;
If no "else..." alternative, and no statement is open, then an exception is raised.

Drawbacks of Ada rendezvous are:

It is slow. All Ada tasks are active, they are concurrent processes. Coordinating tasks therefore compete with user tasks.
There are frequent context switch, which is expensive. At least one context switch is necessary every time a rendezvous occurs.

A good example of using Ada rendezvous to synchronize processes is the solution to producer/consumer problem:

                  task bounded_buffer is
                          entry  store (x: buffer);
                          entry  remove (y: buffer);

                  end;
                  task body bounded_buffer is
                  ring: [0..9] of buffer;
                  head, tail: integer;
                  head : = 0;   tail := 0;
                  begin
                  loop
                      select
                         when head < tail + 10 = >
                         accept  store (x: buffer);      

                             ring[head mod 10] := x;
                             head := head + 1;
                          end  store;
                      or
                          when tail < head = >
                          accept  remove (y: buffer);       
                             ring[tail mod 10];
                             tail := tail + 1;
                          end  remove;
                      end select;
                  end loop
                  end bounded_buffer;

  task body producer is                task body consumer is
  item: integer;                       item: integer;
  begin                                begin
    loop                               loop
       generate item;                     bounded_buffer.remove(item); 
       bounded_buffer.insert(item);       use item;
    end loop;                          end loop;
    end producer;                     end consumer;

Questions:

In producer/consumer example, if a consumer is blocked on bounded_buffer.remove call, when will it be unblocked?
What at least one context switch is necessary every time a rendezvous occurs?
How may deadlock occur in Ada Rendezvous? give an example.
When would exception occur?
What are the drawbacks for Ada Rendezvous?

References:

Hilzer, Jr., R. C., "Synchronization of the Producer/Consumer Problem Using Semaphores, Monitors, and the Ada Rendezvous," Operating Systems Review, vol. 26, no. 3, July 1992, pp. 31 - 39.
Singhal, Mukesh, & Shivaratri, N. G., "Advanced Concepts in Operating Systems," Chapter 2, pp. 33 - 36.
Cooling, J. E., "Introduction to Ada," Chapter 14, pp441 - 494.
Keeffe, D., Tomlinson, G. M., "Pulse: An Ada-based Distributed Operating System."
Gehani, Narain, "Ada Concurrent Programming," Chapter 1 - 3.

Go Back to the Operating Systems page.

Last updated: 24 Jan 1995 / schmidt@cs.vt.edu