Navigate to either /herlihy or /unbounded. Once there, simply run "make" in your favorite shell.

There are several entry points to see the algorithm at work.

In either /herlihy or /unbounded, you can run any of the test programs. I would recommend test/stress; these are most up-to-date with my current deque spec in both cases, and are more general than test/serial or test/concurrent, which are unit tests.

In /unbounded, you can also run exp/nonblock to see that the deque is working. Options for unbounded/exp/nonblock are as follows:

• t: set the number of pthreads to use
• e: choose which experiment to run ("timing" or "throughput")
• w: choose which workflow to use ("stack", "queue", or "random")
• o: when e = "timing", o represents number of ops all threads perform; when e = "throughput", o represents the number of seconds the program should run in total.

• README.md :: this file.
• writeup.tex :: LaTeX file of final writeup for project.
• citations.bib :: bibliography for writeup.
• herlihy/ :: a bounded deque implementaiton used as a starting point.
  • Makefile :: for all subdirectories.
  • etc/ :: directory for miscellaneous files related but not crucial to algorithm.
  • exp/ :: code for timing and throughput experiments.
    • mutex.cc :: timing experiment for nonblocking algorithm + mutexes.
    • nonblock.cc :: timing experiment for purely nonblocking algorithm.
  • src/ :: code for the actual deque algorithm.
    • deque.cc :: contains algorithm for Herlihy bounded deque.
    • deque.h :: structs, enums, and prototypes for deque.cc.
  • test/ :: various testing code for algorithm
    • serial.cc :: sanity testing deque in a non-concurrent setting.
    • concurrent.cc :: lightly tests some boundary cases in a concurrent setting.
    • stress.cc :: aggressively test deque. do massive number of operations and check consistency.
• unbounded/ :: an unbounded deque implementaiton based on Herlihy.
  • Makefile :: for all subdirectories.
  • etc/ :: directory for miscellaneous files related but not crucial to algorithm.
  • exp/ :: code for timing and throughput experiments.
    • mutex.cc :: timing and throughput experiments for c++std deque + mutexes.
    • nonblock.cc :: timing and throughput experiments for purely nonblocking algorithm.
  • prof/ :: various profiling information.
  • src/ :: code for the actual deque algorithm.
    • deque.cc :: contains algorithm for Herlihy bounded deque.
    • deque.h :: structs, enums, and prototypes for deque.cc.
  • test/ :: various testing code for algorithm
    • serial.cc :: sanity testing deque in a non-concurrent setting.
    • concurrent.cc :: lightly tests some boundary cases in a concurrent setting.
    • stress.cc :: aggressively test deque. do massive number of operations and check consistency.

There have been several revisions to the project report since last submission:

• Minor revision to the abstract.
• Description of unbounded algorithm changed.
• Results section completely overhauled; new plots added.
• Future work section added.
• Pseudocode in final figure modified to reflect current algorithm.