Homework — Semaphores

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

The C files are located in directory part-3/homework-semaphores/material/.

The general specifications of the POSIX functions are available at OpenGroup website

Overview

In this work, we will implement in practice (in C) the synchronization scenarii modeled in the TD about synchronisation: producer-consumer, rendez-vous, barber shop, dining philosophers, and bus station.

Semaphores

Here is a brief summary of the main system calls used to manipulate semaphores.

int sem_unlink(const char *name);
  • Remove the semaphore named by the string name.
    • Always remove semaphores before using them in order to start with a clean environment.
    • Check the returned value. If the semaphore cannot be removed, it is very likely that a process is still using it and that you should kill it.
sem_t *sem_open(const char *name, int oflag, mode_t mode, unsigned int value);
  • Create or open a named semaphore name.
    • name is the semaphore name. If it starts with a slash, e.g., /identifier, then the syscall creates a named semaphore, which can be used by unrelated processes: all processes opening the same named semaphore will share it (which is needed for synchronization purposes). Otherwise the semaphore is unnamed and can only be shared among threads sharing it in memory.
    • oflag is similar to the flag used with system call open().
    • The third parameter is the access mode given to the created file, for instance 0644.
    • The fourth parameter is critical as it represents the number of resources in the semaphore initially.
  • Example: fd = sem_open("/my-semaphore", O_CREAT, 0644, 1) creates a named semaphore called "/my-semaphore", with rw------- access mode and 1 initial resource. It can used as mutual exclusion for instance.
int sem_wait(sem_t *sem);

The sem_wait() function shall get a resource from the semaphore referenced by sem. If the semaphore value (that is the available resources) is currently zero or negative, then the calling thread shall not return from the call to sem_wait() until a resource becomes available.

int sem_post(sem_t *sem);

The sem_post() function shall put a resource in the semaphore referenced by sem. If the semaphore value (that is the available resources) resulting from this operation is positive, no process has been blocked while waiting for the semaphore; the semaphore value is simply incremented. If the semaphore value resulting from this operation is zero or negative, one of the blocked processes waiting for a resource will be woken up, return from its call to sem_wait().

Producer consumer

In this lab, we first study the array blocking queue, one of the best-known design patterns for implementing the producer-consumer model. The queue will be implemented as a circular buffer and we enforce synchronization features with semaphores. We recommend that you go back to the Synchronization TD to recall the properties and services we studied at the time.

Useful functions

Now you know that processes do not share memory space and therefore do not share variables. If they wish, they can share data via files. We provide four functions to help you writing and reading a shared variable or a shared array using a file:

int read_shared_var(char *name);
void write_shared_var(char *name, int value);
void read_shared_array(char *name, int *array, int size);
void write_shared_array(char *name, int *array, int size);

We also provide a function for generating a random integer value in a first ... last interval:

int value_between(int first, int last);

Implementation

We provide an incomplete implementation sem-prod-cons.c of the solution of the producer-consumer problem discussed in the Synchronization TD. This implementation does the following:

  • Provide on the command line the number of consumers (n_consumers) and producers (n_producers) and the size of the buffer.
  • Create n_consumers consumers and n_producers producers.
  • Each producer produces n_consumers items and so n_producers x n_consumers items are produced overall.
  • Each consumer consumes n_producers items and so n_producers x n_consumers items are consumed overall.
  • Then, consumers and producers terminate.
  1. Complete the implementation using the algorithmic solution from the TD on synchronization.
  2. Test with different scenarii.

Rendez-vous

The objective is to implement in C a rendez-vous mechanism as described in the Synchronization TD. We propose the following specification:

void rendez_vous(sem_t *i_arrive, sem_t *u_arrive);
  1. Implement the function rendez_vous() using the algorithmic solution from the Synchronization TD.
  2. Test it in the context of the next exercise.

Barber shop

We provide an incomplete implementation sem-barber.c of the barber shop solution discussed in the Synchronization TD.

  1. Complete the implementation using the algorithmic solution from the Synchronization TD.
  2. Test with different scenarii (different arguments on the command line).

Dining philosophers

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

We provide an incomplete sem-diner.c implementation of the philosophers diner solution discussed in the Synchronization TD. The solution we have chosen to implement is the one free of starvation and deadlock issues.

  1. Complete the implementation using the algorithmic solution from the Synchronization TD.
  2. Test with different scenarii.

Bus station

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

We provide an incomplete sem-bus.c implementation of the bus station solution discussed in the Synchronization TD. The solution we have chosen to implement is one in which a passenger already on the bus invites the next passenger to board if necessary. Note that the driver is considered to be the first passenger. The last passenger is responsible for asking the driver to leave the station.

  1. Complete the implementation using the algorithmic solution from the Synchronization TD.
  2. Test with different scenarii.