TD — Synchronization

All the solutions are available in the part-3 tarball.

Overview

In this lab, we first study the blocking queue, one of the best-known design patterns for implementing the producer-consumer model. We implement it with semaphores.

Next, we study the rendez-vous mechanism to easily solve two synchronisation problems of the dayly life, the barber shop and the bus station.

Finally, we study the ultra-classical dining philosophers problem, which highlights two major synchronisation problems: starvation and deadlock.

Note: in the following, all requests to "model" or "implement" a solution, refers to solutions in pseudo-code using the synchronization tools seen during the course lectures (e.g., semaphores), not implementation in concrete programming languages (e.g., C). A separate homework is dedicated to how to use OS semaphores from the C programming language.

Producer consumer model

The aim is to implement a fixed-size blocking buffer service. This concurrency design pattern is probably the advanced synchronization mechanisms you should be familiar with. It was popularized by Java with its ArrayBlockingQueue service. The buffer will be implemented as a circular buffer and we enforce synchronization problems with semaphores.

This circular buffer consists of a fixed-size max_size array, an index first (or start) designating the first full slot in the array, an index last (or end) designating the last full slot in the array and size the number of full slots in the buffer. As we are implementing a circular buffer, to store a new element, a producer appends it at the end of the full slots. When the producer reaches the end of the array, it stores this element at the start of the array in a circular fashion. To remove an element, a consumer removes it at the start of the full slots. When the consumer reaches the end of the array, it removes this element at the start of the array in a circular fashion. Thus, we assert (first + size) % max_size == (1 + last) % max_size. When the producer stores an element in a full buffer, it blocks until an empty slot becomes available. When a consumer removes an element in an empty buffer, it blocks until a full slot becomes available.

  1. Propose a first implementation that implements the behaviour above without considering synchronisation issues.
  2. Extend this implementation by considering that two producers (resp. two consumers) can store (resp. remove) data at the same time in the buffer. Use synchronisation mechanisms and provide their initialisation.
  3. Extend this implementation by considering that a producer has to block when the buffer is full.
  4. Extend this implementation by considering that a consumer has to block when the buffer is empty.

Rendez-vous

The objective is to implement a rendez-vous mechanism (or "handshake"). Two processes have a rendez-vous at some point of execution, when neither is allowed to proceed until both have arrived. We enforce proper synchronisation with semaphores.

  1. Provide a way for the first process to wait for the second one.
  2. Provide a way for the second process to wait for the first one. Beware of deadlock.

Barber shop

In a barber shop, there is a barber, a chair in which the customer sits to have his or her hair done and N seats in the waiting room. We want to model the system in the following manner:

  • If a customer arrives:
    • if one of the N seats is free, the customer sits and waits in the waiting room to be invited by the barber,
    • otherwise, he or she leaves (immediately).
  • If the chair is free:
    • the barber invites the first customer waiting to get the chair,
    • he or she waits for this customer to sit on the chair.
  • If the customer sits on the chair:
    • the barber brushes the customer for m minutes, and then invites him or her to leave the chair.
    • the customer waits for the barber to invite him or her to leave the chair and then leaves the shop.
  1. Model the waiting room with a mutual exclusion mechanism.
  2. Model the interactions between the barber and the customer with rendez-vous.

Dining philosophers

(Optional exercise, to go further in the understanding of the course topics.)

Five philosophers dine together at the same table. Each philosopher has his own plate on the table. There is a fork between each plate. The dish served is a kind of spaghetti that must be eaten with two forks. (Don't ask: philosophers, like engineers, can be weird in their own ways.) Each philosopher can only think and eat alternately. Moreover, a philosopher can only eat his spaghetti if he or she has both their left and right fork. The two forks will therefore only be available when their two nearest neighbors are thinking and not eating. When a philosopher has finished eating, he or she puts down both forks.

  1. We propose the following algorithm. A philosopher does the following:
    • Pick the left fork, if available; otherwise, think until it becomes available.
    • Pick the right fork, if available; otherwise think until it becomes available.
    • Eat and then put down the forks in the same order they were picked up.
    • Repeat.
  2. Give a scenario that would raise a critical issue.
  3. We propose to give a unique identifier to each fork. A philosopher does the following:
    • Pick the fork with the smallest id; otherwise, think until it becomes available.
    • Pick the other fork; otherwise, think until it becomes available.
    • Eat and then put down the forks in the same order they were picked up.
    • Repeat.
  4. Explain how it improves the behaviour.

Bus station

(Optional exercise, to go further in the understanding of the course topics.)

A passenger arriving at the bus station queues in the boarding area. The bus arrives with N seats available. The boarding process is as follows:

  • When the bus arrives, users already present board as long as there are seats available and passengers in the queue.
  • Once there are no more seats available or no more passengers in the queue, the bus departs.

We consider two alternative approaches:

  1. The bus driver invites all passengers in the boarding area to board, as there are seats available and passengers in the queue.
    • If either condition is not met, the driver leaves.
  2. The bus driver invites the first passenger to board if there is a seat available and a passenger in the queue. Then, the last passenger to board invites the next passenger to board if there is a seat available and a passenger in the queue.
    • If one of the two conditions is not met, the driver leaves or the last passenger asks the driver to leave.

Exercises:

  1. Model the problem with mutual exclusion and rendez-vous for the first approach.
  2. Model the problem with mutual exclusion and rendez-vous for the second approach.