Rendezvous

Mandatory assignment

A mutex lock is meant to be taken and released, always in that order, by each task that uses the shared resource it protects. In general, semaphores should not be used to enforce mutual exclusion. The correct use of a semaphore is to signaling from one task to another, i.e., a task either signal or wait, not both.

In this assignment you will solve the rendezvous problem using semaphores. This problem clearly demonstrates the type of synchronization that can be provided by semaphores.

Supported platforms

You will only be able to work on this assignment using one of the supported platforms.

The department Linux system

The provided code has been developed and tested on the department Linux system but will most likely work on any Linux system.

If you use macOS you can use the provided platform independent semaphore library, see this post on Piazza for more information.

If you use Windows you must use the department Linux system for this assignment. You may still use your private computer to access the department Linux system using SSH but make sure to log in to one of the Linux hosts.

Overview

File to use
module-4/mandatory/src/rendezvous.c
Description
In this program, a process creates two threads, and waits for their termination. Each thread performs five iterations. In each iteration the threads print their iteration number and sleeps for some random amount of time.

Compile and run

In the terminal, navigate to the module-4/mandatory directory. Use make to compile the program.

$ make

The executable will be named rendezvous and placed in the bin sub directory. Run the program from the terminal.

$ ./bin/rendezvous

Questions

Run the programs several times and study the source code. Think about the following questions.

  • Could you predict the output before execution? Why?
  • Adjust the sleeping duration of one thread (or both threads) to have a different output (ie. another interleaving of the tasks traces). Could you predict this output? Why?

Desired behaviour - rendezvous

We now want to make the two threads have a rendezvous after each iteration, i.e., the two threads A and B should perform their iterations in lockstep. Lockstep means that they both first perform iteration 0, then iteration 1, then iteration 2, etc. For each iteration the order between A and B should not be restricted.

The following is an example of a valid trace of execution: A0, B0, B1, A1, B2 A2. The following are examples of invalid traces of execution: A0, A1, B0, B1 and A0, B0, B1, B2.

Hint

Implement the desired behaviour using two semaphores.

Compile and run

Compile and run the program.

$ make
$ ./bin/rendezvous

Questions

Change the threads sleeping durations.

  • Does the output change?
  • What are the possible outputs?