Synchronization and Concurrency for User-level Systems

April 26, 2006
William N. Scherer III | University of Rochester

Concurrency in user applications is on the rise. Modern computers have multiple hardware threads per processor and multiple processors per chip, each of which may switch to a different software thread many times per second. Applications of the future will be heavily multithreaded. My research aims to make such programs easier to write and more resilient to the performance programs historically caused by preemption. After surveying work in several areas (including preemption-tolerant locks and contention management for software transactional memory) I will focus in this talk on dual data structures, which extend the utility and performance of concurrent libraries.

Traditional fine-grain locking is prone to deadlock, non-composability, priority inversion, convoying, and intolerance of thread failure, preemption, and even page faults. Nonblocking algorithms avoid these limitations by ensuring that the delay or failure of a thread never prevents the system as a whole from making forward progress. We broaden the range of known nonblocking algorithms by introducing a design methodology that supports partial operations in concurrent objects with standard linearizability theory. We define dual data structures as concurrent objects that may hold data and requests. We present lock-free versions of several dual data structures, including dual stacks, dual queues, exchangers, and synchronous queues. Our exchangers and synchronous queues will appear in Java 6.

Speaker Details

William N. Scherer III was born in Baltimore, Maryland on September 3, 1971. He attended the Carleton College from 1989 to 1993, receiving a Bachelor of Arts in Computer Science in 1993. He came to the University of Rochester in the Fall of 2000 and began graduate studies in Computer Science. He pursued his research in synchronization under the direction of Professor Michael L. Scott. He received a PhD in Computer Science from the University of Rochester in March 2006.