Parallel and Distributed Systems Lab (PDSL)

Home Up Contents

Research - Lock Free Structures



Lock-Free Data Structures for Parallel Computing 

Work on lock-free techniques has been with us for approximately 20 years. Lock-free techniques are used for synchronizing access to in-memory data structures by concurrent processes without the need for using locks. The motivation for doing so lies in the potential for deadlock when using locks and also in the existence of a number of undesirable scheduling-related anomalies (such as priority inversion and convoying) related to the use of locks. Recently, the need for developing lock-free algorithms has increased significantly with the growing prevalence of use of both small and large scale shared memory multiprocessors to solve computationally intense problems involving shared, complex data structures.

Specific sub-areas of interest

Work on Lock-Free data structures for parallel computing within the PDSL began about 10 years ago with a single interested MSc student, Mr. Mohammad Farook. He worked on improving lock-free linked lists (extending work done by Valois, et al) under the supervision of Dr. Graham. The area lay dormant within the lab for close to 5 years before being picked up by Ms. Jianwen Ma, an MSc student co-supervised by Dr. Graham and Dr. Helen Cameron (Dept. of Computer Science). Ms. Ma developed a lock-free insertion algorithm for Red-Black trees (a type of balanced binary tree) using only CAS (Compare And Swap) type primitives. This work was improved and extended to support lock-free deletions by Mr. Jong Ho Kim, another MSc student co-supervised by Drs. Graham and Cameron. Currently, Ms. Afroza Sultana, another MSc student (again co-supervised by Drs. Graham and Cameron) is working on developing lock-free algorithms for a new form of binary search tree based on a combination of the B-Link tree structure and Valois' lock-free linked list. This new structure is being explicitly designed to provide high levels of locality of reference to make its execution performance on shared memory machines (especially NUMA machines) efficient.

Our Publications on Lock-Free Data Structures

bulletRelated Papers
bulletRelated Presentations
bulletOther Related Publications

Related Work on Lock-Free Data Structures

bulletLinks on Lock-Free Data Structures

For More Information Contact:

Parallel and Distributed Systems Lab
E2-556 EITC University of Manitoba, Winnipeg, MB, Canada R3T 2N2
Tel: 204-474-8837
FAX: 204-474-7609


Send mail to with questions or comments about this web site.
Last modified: 03/23/06