MSpace - DSpace at UofM >
Faculty of Graduate Studies (Electronic Theses and Dissertations) >
FGS - Electronic Theses & Dissertations (Public) >

Please use this identifier to cite or link to this item:

Title: Fast lock-free linked lists in distributed shared memory systems
Authors: Farook, Mohammad
Issue Date: 1-Feb-1998
Abstract: In shared memory systems concurrent processes operate on shared data structures. The consistency of the data structures is maintained by mutual exclusion, which is implemented by locking. Locking is an easy way of ensuring consistency of the shared data structures, but it has several drawbacks. The major drawback is that it increases the latency of all the processes as the shared data structure is accessed in a serial manner. It might also result in deadlocks when the process currently accessing the shared data structure is pre-empted or terminated. An alternate approach to avoid mutual exclusion by locking is by implementing lock-free data structures. This is possible by using basic synchronization primitives such as Compare & Swap and Double Compare & Swap. Processes can concurrently read and write on these data structures and also maintain the consistency of the data structure. Lock-free data structures reduces the latency of the processes and avoids deadlocks. This thesis presents lock-free linked listsalong with the algorithms that operate on them. The algorithms were simulated and were compared with Greenwald & Cheriton's and Valois' algorithms. The design of the linked lists along with the effective and efficient use of the synchronization primitives in the algorithms provides a improved performance over the other two algorithms. The correctness of the algorithms is also presented in the thesis.
Appears in Collection(s):FGS - Electronic Theses & Dissertations (Public)

Files in This Item:

File Description SizeFormat
MQ32107.pdf3.66 MBAdobe PDFView/Open
View Statistics

Items in MSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! MSpace Software Copyright © 2002-2010  Duraspace - Feedback