|
Highly concurrent dynamic linear hashing is important for
databases designed to support a large number of users and
variability in the size of the databases. Previous concurrent
linear hashing relies typically on locking techniques to
achieve mutual exclusion: a process trying to read or modify
the hash- file will first lock relevant parts of that hashfile
to prevent interference from other processes. However, locking
is poorly suited for multiprocessor systems. A serious
disadvantage of locking is that a process holding a lock can
unexpectedly delay the progress of other processes. The
unexpected delay can result in priority inversion, convoying,
and deadlock which can degrade the performance of the system
down to an untolerated level. A lock-free implementation, on
the other hand, does not require mutual exclusion, and
guarantees that any process can access the hashfile at any time
to execute its operation. This paper presents a lock-free
implementation of dynamic linear hashing on multiprocessor
systems. We assume the multiprocessor system has a shared
memory that supports load_linked, store_conditional and
check_valid sychronization primitives. Concurrent operations
are coordinated via synchronization primitives. Our lock-free
implementation achieves high degree of concurrency, is non-
blocking and fault tolerant, and is suitable for multiprocessor
systems.
|