Rendez Vous

by: Burt Rosenberg

at: university of miami

last-update: 5 oct 2024
28 sep 2026

Overview

We define the rendez-vous and use PV semaphores to implement the rendez-vous. The idea is two threads should proceed to a certain location in their code, and wait until all threads have arrived at that point.

The threads proceed concurrently, that is, the events in the threads occur without any required ordering relationship between the threads. Events S and T can be ordered by the time at which they occurred. If S occurs before T in time we write S <_t T.

If the ordering of the evens S and T is guaranteed, we call S and T synchronous events and write S < T.

Within a thread, it is easy to establish what events are synchronous, as the line by line execution of the the code provides this ordering.

It might be required that a time ordering be established (or more generally, some dependency) between and S and T in different threads, say A and B. One solution is the rendez-vous. A Rendez-vous is an event R known to both threads and for any synchronous fact,

S_A, S_B < R < T_A, T_B.

It is sufficient to establish the following,

S_A, S_B < T_A, T_B.

since by non-clairvoyance we would have,

S_A, S_B <_t T_A, T_B.

as well. Then R can be any time greater than the later of S_A and S_B and the earliest of T_A, T_B.

A Rendez-Vous at R for threads A and B

         SA    R  TA
         |     |  |
A:   ----+-----+--+--------------
               |
               | 
B:   -------+--+-----+-----
            |  |     |
           SB  R    TB

We propose to create a rendez-vous using two PV semaphores.

The threads are created with two PV semaphores which are share.
The A semaphore is called the my semaphore in A, and is called the other semaphore in B.
Likewise the B semaphore is called the my semaphore in B and the other semaphore in A.
The semaphores are created with count zero, hence are both at first locked.

Each thread has this code,


       ~~~ X ~~~ my.V() ~~~~~~~~ other.P() ~~~~~~~ Y ~~~~~~~~

For thread A we have

A:X < A:V < A:P < A:Y

and likewise for thread B,

B:X < B:V < B:P < B:Y

Note that the event P will mean the succesful moving on from the P call.

Because of the PV semaphores we have,

A:V < B:P and B:V < A:P

This is because, no matter when A begins the A:P event, it will not proceed until thread B signals A's semaphore, that is, after the B:V event. Likewise fo the B:P event.

Therefore we have

A:X < A:V < B:P < B:Y

and

B:X < B:V < A:P < A:Y

Which can be summarized as,

A:X, B:X < A:Y, B:Y

as was required for the rendez-vous.

A:         X       R            Y
           |       |            |
t:      ---+--+----+--------+---+-----
              |    |        |
B:            X    R        Y

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 5 oct 2024
update: 28 sep 2026

Rendez Vous

by: Burt Rosenberg at: university of miami last-update: 5 oct 2024 28 sep 2026

Overview

by: Burt Rosenberg

at: university of miami

last-update: 5 oct 2024
28 sep 2026