In class, we discussed some possible solutions to hw8 (semaphores). You'll find a traditional textbook description of mutexes and semaphores here, for background reading: http://ostep.org All of the chapters of that textbook under "Concurrency" are relevant to our class. The chapters of special interest are: Thread API: pthread_create Locks: test-and-set, spinlock, mutexes Semaphores: semaphores Condition Variables: monitors [to be convered in a future lecture] In Part I: As a rough outline, the solutions in class were based on the code below. (Note that 'man sem_wait' tells us that it should actually return 'int', and that when '*sem' or 'count', we just block without further decrementing count. I prefer to also decrement count, so that '*sem == -5' means that 5 threads are blocked on this semapahore. In your homework, you can choose any reasonable definition of sem_wait, as long as your solution works for producer-consumer.) mutex_t mut; void sem_post(sem_t *sem) { pthread_mutex_lock(&mut); *sem = *sem + 1; pthread_mutex_unlock(&mut); } void sem_wait(sem_t *sem) { pthread_mutex_lock(&mutex); int mysem = *sem; // Save the *sem I saw on entry. *sem = *sem - 1; if (*sem < 0) { pthread_mutex_unlock(&mutex); while (*sem < mysem) {} // When we return from while: *sem >= mysem // In this case, we are guaranteed that we don't need to wait any more. pthread_mutex_lock(&mutex); } pthread_mutex_unlock(&mutex); } As we saw, the code above mostly works, but if there are four or more threads, and if two threads are posting while the rest are waiting, then we can hit a bug. It might happen that thread A and thread B both call sem_post() before any thread in sem_wait() can execute. Then *sem will increase by two instead of by 1. To fix this, you'll need to add extra logic that keeps track of the number of pending posts generated by sem_post, and then decrement the number of pending posts when a thread in sem_wait stops being blocked. You must still fix this last bug. NOTE: If your semaphore must have a count and a pending_posts, try: > struct mysem { > int count; > int pending_posts; > } > typedef struct mysem sem_t; > > foo(sem_t *sem) { > sem->count // (*sem).count > sem->pending_posts // (*sem).pending_posts > } ==== In part II, you must use your version of sem_post and sem_wait to solve the producer consumer problem for the case of two threads (one producer, and one consumer). Recall that you will want to use two semaphores. If the buffer has N slots, then you will want to initialize the semaphores as follows: sem_t sem_prod = N; // This counts the number of empty slots available for // the producer to produce. Initially, there are N slots, // since all slots are empty, and we can produce into // them. sem_t sem_cons = 0; // This counts the number of full slots available for // the consumer to consume. Initially, there are zero. You must choose an appropriate data structure for the N slots of the buffer. One good choice is a circular buffer, which can implement a FIFO queue that has a bounded buffer. (Recall that the producer-consumer problem is also called a bounded-buffer problem.) int buf[N]; int first_occupied_slot = 0; int first_empty_slot = 0; void add(int val) { buf[first_empty_slot] = val; first_empty_slot++; if (first_empty_slot >= N) first_empty_slot = 0; } int rem() { int val = buf[first_occpuied_slot]; first_occupied_slot++; if (first_occupied_slot >= N) first_occupied_slot = 0; return val; } Your semaphore code will guarentee that the indexes, first_empty_slot and first_occupied_slot, remain consistent. So, you won't need a separate 'valid' bit to decide if a slot is still being used. ==== In part III, you must solve it in the case of many threads. In this case, it will not be enough to simply use two semaphores, one for the producers and one for the consumers. You will also need to add one or more mutexes in case multiple producers try to produce simultaneously into the same slot in the buffer, or in case multiple consumers try to simultaneously consume.