SANIC TEEM - Rob Kelly and Ian Neal
CSE325
Lab Project 3


The SANIC TEEM Producer / Consumer Experiment For Great Good, hereafter called
"the program", is a multithreaded program designed solely to explore
multithreaded programming and all the inherent synchronization problems that
arise. The program uses a shared buffer created by the main thread, and then
spawns new producer and consumer threads that add to and remove from that
buffer, respectively.  It takes three arguments: the number of producers, the
number of consumers, and whether to use a First In Last Out style queue (usually
called a stack) for the buffer (the alternative is First In First Out, or a
standard queue).  The main thread will wait a full five minutes to exit, as per
the specifications.  Of note is that, since one can specify more producers than
consumers, not every generated element is consumed, and since one can specify
more consumers than producers, a few producers might be hanging waiting for
elements that will never be generated. These threads are cancelled and cleaned
up after the 5-minute sleep.


BUILDING
  `make` to build the project normally, producing the executable binary `p3`.
  `make clean` to clean up build files.
  `make test` to run a set of deployment tests, checking for memory leaks.

USAGE
  `p3 [PRODUCERS] [CONSUMERS] [IS_FIFO]`
  Where PRODUCERS is the number of producer threads to spawn, CONSUMERS is the
  number of consumer threads and IS_FIFO is 0 to use a FIFO buffer, 1 for FILO.

EXAMPLES
  $ ./p3 9 9 1
  item 1858107848 added by producer 2: buffer = [ 1858107848 ]
  item 1858107848 removed by consumer 5: buffer = [ ]
  item 593819124 added by producer 4: buffer = [ 593819124 ]
  item 593819124 removed by consumer 7: buffer = [ ]
  item 218603148 added by producer 1: buffer = [ 218603148 ]
  item 218603148 removed by consumer 8: buffer = [ ]
  item 1425938399 added by producer 7: buffer = [ 1425938399 ]
  item 1200801987 added by producer 5: buffer = [ 1425938399 1200801987 ]
  item 1020928305 added by producer 9: buffer = [ 1425938399 1200801987 1020928305 ]
  item 271728317 added by producer 3: buffer = [ 1425938399 1200801987 1020928305 271728317 ]
  item 271728317 removed by consumer 9: buffer = [ 1425938399 1200801987 1020928305 ]
  item 1020928305 removed by consumer 4: buffer = [ 1425938399 1200801987 ]
  item 1693828948 added by producer 8: buffer = [ 1425938399 1200801987 1693828948 ]
  item 1373493830 added by producer 6: buffer = [ 1425938399 1200801987 1693828948 1373493830 ]
  item 1373493830 removed by consumer 2: buffer = [ 1425938399 1200801987 1693828948 ]
  item 1693828948 removed by consumer 3: buffer = [ 1425938399 1200801987 ]
  item 1200801987 removed by consumer 1: buffer = [ 1425938399 ]
  item 1425938399 removed by consumer 6: buffer = [ ]

  $ ./p3 1 2 0
  item 1585306676 added by producer 1: buffer = [ 1585306676 ]
  item 1585306676 removed by consumer 2: buffer = [ ]

  $ ./p3 4 1 1
  item 1050311717 added by producer 2: buffer = [ 1050311717 ]
  item 1050311717 removed by consumer 1: buffer = [ ]
  item 500374754 added by producer 1: buffer = [ 500374754 ]
  item 1423504565 added by producer 3: buffer = [ 500374754 1423504565 ]
  item 1463404585 added by producer 4: buffer = [ 500374754 1423504565 1463404585 ]

IMPLEMENTATION
  The key component of this project is the set of mechanisms used to synchronize
  the buffer between the producer and consumer pthreads. Three synchronization
  structures are used to ensure that no buffer operations interfere: two
  semaphores, one for producers and one for consumers, and a mutex lock for
  buffer operations. The buffer mutex lock is handled entirely within the buffer
  and its helper functions - inserting and removing elements from the buffer
  locks the mutex, ensuring those operations act atomically with respect to
  other pthreads. The producer and consumer semaphores work together to prevent
  race conditions in buffer modification, while simultaneously providing buffer
  bounds checking as an added bonus. The production semaphore is initialized to
  the buffer capacity, and the consumer semaphore is initialized to 0. Producers
  lock the production semaphore on entering a critical section, and unlock the
  consumer semaphore on leaving. Consumer semaphore behavior is the same, but
  vice-versa. In this way, the producer and consumer pthreads block until the
  buffer is in a state where they can perform their operation. One side-effect
  of this implementation is that pthreads may end up blocking indefinitely; for
  instance, if the number of consumers is greater than the number of producers,
  whatever consumer threads are left over at the end will block indefinitely.
  This is not a bug, but a necessary consequence of the project specification,
  and is resolved during the thread clean-up process performed by the main
  thread after sleeping for 300 seconds.
  With the exception of the synchronization mechanisms, this program is very
  minimal. pthreads are produced by the main thread, run their predefined
  routines, and are cleaned up at the end of execution. The buffer structure is
  implemented as a wrapper of the Linux TAILQ structure, which is defined by
  <sys/queue.h>. A nice benefit of implementing the buffer in this way rather
  than as an array is that the buffer size may be adjusted dynamically. Though
  the buffer size is defined explicitly to be 10 in `p3.c`, it can be redefined
  to any positive integer without issue.

BUGS
  None known. The program runs without memory leaks - however, if execution is
  interrupted during the main thread's 300-second long sleep, some resources
  will naturally not be freed.

(Easter eggs! For extra fun, try running the program with big numbers; semaphores (and a mutex internal to the queue) keep the buffer from overfilling, since sem_wait is blocking and so is mutex_lock.)