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

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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.

 

• 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 producer- consumer 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 com- pleted, 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 synchroniza- tion mechanisms, is fraught with peril. It is very easy to find yourself with an implementation that inadver- tently 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

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of