Semaphore Implementation

Introduction

This assignment will require you to implement a semaphore using mutexes and condition variables, then use your semaphore to implement a producer/consumer queue (FIFO) data structure for passing data between threads. You will use POSIX mutexes, condition variables, and threads in this project.

Man page sections are noted as a number in square brackets after a keyword in this document. For example, pthread_create (3) indicates that the manual page for the pthread_create library function is found in section 3 of the Unix manual, and you can view it with the command man 3 pthread_create.

1 Getting Started

You should have already received a GitHub Classroom invitation. Follow it, then check out the given code.

The given code for this project contains two source files that you will have to modify, src/csesen.c and src/ pcq.c, as well as two header files, src/csesen.h and src/pcq.h that you should not. It also contains the source for five tests (two for the semaphore and three for the producer-consumer queue) that will run when you invoke make test. When you finish reading this handout, you should read both header files, the given tests, and the given sources before you begin implementation. You will find a variety of advice and clarifying comments in the given code.

2 Semaphores

The first part of this project requires you to implement a semaphore called CSE.Semaphore using the API defined in src/csesen.h. There are extensive comments in this file explaining the API and its usage. Your semaphore will be tested directly, and it will also be used as a tool for implementing the second part of this project.

You will find information on semaphores in the lecture slides, and CS:APP contains a detailed description of semaphores with some examples of how to use them correctly in Section 12.5. You should read Section 12.5 carefully before starting this project, and refer to it as necessary during your implementation. In particular, you will find the producer-consumer problem that is described in detail in Section 12.5.4 with example code in Figures 12.24 and 12.25 very useful. You may be able to use this code in your implementation with some modifications.

As discussed in class, an efficient semaphore can be created using a mutex and a condition variable. You should implement the semaphore for this project in precisely that fashion.

You may NOT use POSIX semaphores in your implementation of CSE.Semaphore.

2.1 POSIX Mutexes

The Pthread mutex API has some complicated options, but you will not need them for this project. In particular, you do not need to use mutex attributes, and can pass NULL for any pointer to pthread_mutex_attr_t. You should only need the functions pthread_mutex_init) [3], pthread_mutex_lock() [3], pthread_mutex_unlock() [3], and pthread_mutex_destroy) [3].

Note that POSIX mutexes are declared as type pthread_mutex-t, and then a pointer to the declared variable is passed to the functions that manipulate the mutex. See tests/counting-semaphore.c for an example of a typical mutex initialization and interaction.

2.2 POSIX Condition Variables

The condition variables provided with Pthreads are likewise more complicated than you will need. You may use NULL for condition variable attributes, as well, and you will not need the timed wait facility. You will use pthread_cond_init (3)pthread_cond_wait() [3]. pthread_cond_signal() [3], and possibly pthread_cond broadcast (3)

Like mutexes, POSIX condition variables are declared as their type (pthread_cond_t) and manipulated as the address of the declared variable. The provided test tests/counting-semaphores.c and tests/synchronous work.c contains examples of typical interactions with condition variables. In your semaphore implementation, you will need to utilize a condition variable to allow threads which are blocking on the semaphore to wait without busywaiting, but be awoken when they can safely enter the semaphore.

A typical use of a condition variable looks like these examples from tests/counting_semaphore.c; the first waits on a condition variable, and the second signals it:

/* Waiting */
pthread_mutex-lock (lock);
while (!quit) {
pthread_cond wait(&done, &lock);
}
pthread_mutex-unlock (&lock);

/* Signaling */
pthread_nutex-lock (&lock);
quit = 1;
pthread_nutex-unlock (&lock);
pthread.cond broadcast(&done);

Obviously, these two operations would have to be executed in different threads for this code to make sense!

3 Producer-Consumer Queues

The second part of this project requires you to use the semaphore that you created and likely other synchronization tools) to implement a producer-consumer queue implementing the API found in src/pc.h. This is a logical construction providing two basic operations:

• A producer can add an item to the queue. If there is room on the queue, this item will immediately be added, where it will wait to be retrieved by a consumer. If there is no room on the queue, the producer will block until room is available, and then insert its item normally. Each item is added to the tail of the queue.
• A consumer can remove an item from the queue. If at least one item is available on the queue, the consumer will immediately remove one item from the head of the queue and return it. If no items are available on the queue, the consumer will block until a producer places an item on the queue.

Note that, because every producer places items on the tail of the queue and every consumer retrieves from the head, this provides first-in first-out (FIFO) semantics for items placed on the queue. The first item produced will be the first item consumed, and so on and so forth.

Your implementation does not need to guarantee any particular ordering between different producers or consumers, but it does need to guarantee that all items placed on the queue by the same producer are placed in the order that they were inserted, and that all items on the queue are removed in the order they were inserted. This means that you do not have to do anything special when waking threads that are blocked on the semaphore, you can simply allow the Pthreads implementation to wake whichever thread it wakes.

The item stored each slot of your producer-consumer queue is a single pointer of type void * You may use this to store a pointer to any data structure, or to store an integer by casting the integer to and from void * when using the queue.

There is an example of producer-consumer queues in CS:APP, Section 12.5.4, which is in your required readings. You will not be able to use the example code from the text directly, because it uses POSIX semaphores (instead of CSE.Semaphore, which you must use) and because it stores integers.

3.1 Pointer typedefs and Encapsulation

The data structure types in this project use typedef. In particular, the following typedefs appear in the given headers:

typedef struct CSE Semaphore *CSE.Semaphore;
typedef struct PCQueue *PCQueue;

These typedefs define the following equivalences:

• CSE_Semaphore means struct CSE_Semaphore *
• PCQueue means struct PCQueue *

This allows code that uses these types to be less verbose and more clear in its actual purpose. You may use these typedefs anywhere in your implementation and tests.

Another benefit of this construction is that the public interfaces for your semaphore and producer-consumer queues speak in terms only of pointers to structures which are not defined in the public interface. This provides encapsulation of your implementation; no code external to csesem.c can manipulate the inner data structures of your semaphore, and no code external to pcq.c can manipulate the inner data structure of your producerconsumer queue. This technique is often used in C. You can find more information about this technique and how it is used in this project in the respective headers.

3.2 Partial Implementation

If your CSE Semaphore implementation is sufficiently incomplete that it prevents your PCQueue from being completed, you may choose to use POSIX semaphores to implement your PCQueue, in return for a grading penalty. You may not use POSIX semaphores to implement CSE_Semaphore! The grading penalty is described below, in Section 7

4 Coordinated Destruction of Resources

The destruction of resources in a multithreaded environment, and particularly the destruction of synchronization mechanisms, is fraught with peril. It is very easy to find yourself with an implementation that inadvertently accesses released resources or freed memory during the process of destroying synchronization tools.

Think carefully about what resources are accessed when and by which threads, and arrange your code to ensure that all threads that might access a resource are notified that it is going to be destroyed and have been given an opportunity to release it before it is actually destroyed. You may find flags or counters in conjunction with condition variables useful for coordinating destruction of your producer-consumer queue, in particular.

5 Memory Management

Each of the two constructions in this project defines a create and destroy function. Your implementation should allocate any memory that it needs on create, and free it on destroy for a given type. You should not use any global or static global variables in this project. All of the state for any semaphore or queue should be stored in the memory that is allocated on create.

You should use the standard dynamic allocator (e.g., malloc() or calloc() and free) to manage this memory.

6 Requirements

You must complete the APIs for both CSE_Semaphore and PCQueue as provided in the header files in the given code. In particular, you must implement:

• CSESemaphore csesen_create(int count)
• void csesem_wait(CSE_Senaphore sem)
• void csesen_post(CSE_Semaphore sem)
• void csesem_destroy (CSE-Semaphore sem)
• PCQueue pcq.create(int slots)
• void pcq-insert(PCQueue pcq, void *data)
• void *pcq_retrieve(PCQueue pcq)
• void pcq_destroy (PCQueue pcq)

The complete specifications for these functions are in their respective header files.

As this API does not provide a way to report errors, you are not required to handle resource allocation errors (e.g., failures of memory allocation or pthreads creation functions) or application errors in accessing your implementation. You may assume that the application uses the API correctly as specified in the header files. In particular, the .create functions will always run to completion before any other function is called on a CSE Senaphore or PCQueue object, and no new accesses to the objects will be performed after the destroy functions have been invoked. (Note that there may be threads already accessing or blocked on your semaphore or queue when it is destroyed, and that it must handle that correctly!)