I need the code in the zipfile to be completed according to the handout. The handout and zipfile are attached. It should be a simple code satisfying all the requirements and no imports should be added. Please don't use POSIX semaphores to implement PCQueue and in the implementation of CSE_semaphore
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. Youmay NOT use POSIX semaphores in your implementation of CSE_Semaphore. 2.1 POSIXMutexes 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. 1 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 con- tains examples of typical interactions with condition variables. In your semaphore implementation, you will need to utilize a condition variable to allow threadswhich are blocking on the semaphore towait 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 firstwaits 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 queue. If there is room on the queue, this itemwill 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 itemproduced 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 theywere inserted, and that all items on the queue are removed in the order theywere 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. 2 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_Semaphoremeans struct CSE_Semaphore * • PCQueuemeans 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, youmaychoose tousePOSIXsemaphores to implementyourPCQueue, in return foragradingpenalty. 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 amultithreaded 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 MemoryManagement Each of the two constructions in this project defines a create and destroy function. Your implementation should allocate anymemory 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 Youmust complete the APIs for both CSE_Semaphore and PCQueue as provided in the header files in the given code. In particular, you must implement: • CSE_Semaphore csesem_create(int count) 3 • void csesem_wait(CSE_Semaphore sem) • void csesem_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_Semaphore 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!) 7 Grading This project is worth 5% of your final course grade. The points will be assigned as follows, although the Auto- grader score will not reflect the handout quiz: Points Description 2 Handout Quiz 7 CSE_Semaphore provides counting semaphore semantics 1.5 CSE_Semaphore destroys cleanly 8 PCQueue provides producer-consumer queue semantics 1.5 PCQueue destroys cleanly If you choose to use POSIX semaphores to implement your PCQueue, your project score will be reduced by 4 points. A Resources As mentioned in Section 2 of this document, Section 12.5 of CS:APP contains detailed information about the operation and usage of semaphores. Section 12.3 of the text discusses threads and the POSIX thread creation and manipulation API. You should plan to read both Section 12