CSE 220: Systems Programming
Programming Assignment 5: Synchronization: Semaphores and Producer-Consumer Queues
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/csesem.c and src/ pcq.c, as well as two header files, src/csesem.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/csesem.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.
POSIX Mutexes
The Pthread mutex API has some complicated options, but you will not need them for this project. In partic- ular, 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.
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 con- tains 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 busy-
waiting, 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_ mutex_ lock (& lock ); quit = 1; pthread_ mutex_ 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 synchro- nization tools) to implement a producer-consumer queue implementing the API found in src/pcq.h. This is a logical construction providing two basic operations:
A producer can add an item to the 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 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 con- sumers, 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 read- ings. 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.
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
