Rendez Vous

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

Overview

Events S and T can be related so that one must follow the other in time. If so, these events are synchronous. If T is determined to necessarily follow S, write: S < T. Events which cannot be established as synchronous are concurrent

Within a thread, it is easy to establish what events are synchronous, as code flow is guaranteed to progress one line of code following another. (This is not really true, but the hardware will hide any surprising consequences of an out of order execution.)

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 < R < T, this is true for S, T and R regardless of whether they are events in thread A or B. 

A Rendez-Vous at R for threads A and B

         S     R  T
         |     |  |
A:   ----+-----+--+--------------
               |
               | 
B:   --------+-+-----+-----
             | |     |
             S R     T
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 each thread A and B we have X < V < P < Y. We wish to establish that these threads are rendez-vous'ing on the event R of both V's have happened. Letting A:V and B:V be the V event as occurs in each thread, X < R means X < A:V and X < B:V. And saying R < Y means A:V < Y and B:V < Y.

Because of code flow, it is immediate to establish A:X < A:V < A:Y and B:X < B:V < B:Y. We need something more to establish synchronicity between threads. We have the fact, by the working of the semaphores, that A:V < B:P and B:V < A:P. This bears a bit of explanation.

Although thread A arrives at A:P whenever, it will not proceed until the "other" semaphore has been signaled. This is done by B, which calls that semaphore "my". Hence this is the B:V event.

Therefore we have A:V < B:V < A:P < A:Y, and likewise B:V< A:V< B:P < B:Y. With the desired result that since A:V < A:Y and B:V < A:Y, then R < A:Y, and since B:V < A:V < B:P < B:Y, then B:V < Y and A:V < Y, or R < B:Y. 

A:         X       R            Y
           |       |            |
t:      ---+--+----+--------+---+-----
              |    |        |
B:            X    R        Y
Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 5 oct 2024
update: 5 oct 2024