CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Scalable and Lock-Free Concurrent Dictionaries

Håkan Sundell (Institutionen för datavetenskap, Datakommunikation och Distribuerade System) ; Philippas Tsigas (Institutionen för datavetenskap, Datakommunikation och Distribuerade System)
Proceedings of the 19th ACM Symposium on Applied Computing p. 1438-1445. (2004)
[Konferensbidrag, refereegranskat]

We present an efficient and practical lock-free implementation of a concurrent dictionary that is suitable for both fully concurrent (large multi-processor) systems as well as pre-emptive (multi-process) systems. Many algorithms for concurrent dictionaries are based on mutual exclusion. However, mutual exclusion causes blocking which has several drawbacks and degrades the system's overall performance. Non-blocking algorithms avoid blocking, and are either lock-free or wait-free. Our algorithm is based on the randomized sequential list structure called Skiplist, and implements the full set of operations on a dictionary that is suitable for practical settings. In our performance evaluation we compare our algorithm with the most efficient non-blocking implementation of dictionaries known. The experimental results clearly show that our algorithm outperforms the other lock-free algorithm for dictionaries with realistic sizes, both on fully concurrent as well as pre-emptive systems.

Nyckelord: Concurrent, non-blocking, dictionary, shared memory, skip list



Denna post skapades 2006-08-25.
CPL Pubid: 312

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för datavetenskap, Datakommunikation och Distribuerade System (2002-2004)

Ämnesområden

Information Technology

Chalmers infrastruktur