Wednesday, November 19, 2014 — 3:30 PM EST
David R. Cheriton School of Computer Science
University of Waterloo
3:30pm, Wednesday, November 19
Software solutions for mutual exclusion developed over a 30-year period,
starting with complex ad-hoc algorithms and progressing to simpler formal ones. While it is easy to dismiss software solutions for mutual exclusion, as this family of algorithms is antiquated and most platforms support atomic hardware instructions, there is still a need for these algorithms in threaded, embedded systems running on low-cost processors lacking atomic instructions; e.g., low-cost devices like basic cell phones, cameras, printers, music players, toys, and even singing greeting cards. While N-thread solutions are usually short (10-25 lines of code), each is ingenious with exceptionally subtle aspects, often making it difficult to prove correctness or construct an implementation.
The talk presents a survey of existing algorithms, with explanations of the intuition behind the algorithms and how they work. In the existing algorithms, several errors were found and corrections made, as well as a few small improvements; two new high-performance algorithms were developed. Finally, high and low contention experiments were performed to compare the algorithms and contrast them with three common locks based on hardware atomic instructions. The results show our two new algorithms are highly competitive with an equivalent hardware lock (Mellor-Crummey and Scott) over a range of 1--32 processors on both AMD and SPARC processors. Hence, threading is a viable alternative to event-driven programming for complex embedded systems without atomic instructions.
DC - William G. Davis Computer Research Centre
200 University Avenue WestWaterloo, ON N2L 3G1