Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

Interview Question I'll Probably Never Use

An chained hash table is usually protected against concurrent access in one of two ways: a mutex (lock) on the table as a whole, or a lock per hash table bucket. The latter introduces deadlock concerns if a process needs to access two or more buckets simultaneously.

Problem:

A keychain is a sequence of integers stored in a hash table. Each element of the keychain serves as the lookup key for the next element.

e.g., For keychain [17, 35, 9], lookup(17)=35, lookup(35)=9, lookup(9)=None

How can we implement the "add keychain", "retrieve keychain" (given first key), and "delete keychain" operations so that they are atomic and deadlock-free, without resorting to a single lock on the entire data structure?


My solution:

The usual procedure for avoiding deadlock (rather than detecting and breaking it) is to acquire resources in a fixed order so that no two threads can simultaneously wait for resources that the other holds.

If there is a lock per hash table bucket (or a mapping from hash table buckets to a linear array of keys) then we can adopt this strategy. So for "add keychain" we need only hash each element of the chain, acquire the bucket locks in numerical order, and perform the insert operations.

For the other two operations, however, we don't know all the buckets that will be touched in advance. If we acquire bucket locks one at a time as we follow the keychain, a thread might acquire them out of order and cause a deadlock. Instead we iteratively build a set of locks.

1. Lock all buckets in set S (initially empty), in increasing order
2. Follow the keychain as far as we can while still locking buckets in increasing order, adding each bucket we visit to S.
3. If the next key is not deadlock-safe, then add the unsafe bucket to S, release all locks, and start over on step 1.
4. If we reach the end of the keychain, perform the desired operation and then release all locks in S.

On each iteration, the size of set S increases by at least 1. This ensures that no matter what modifications take place to the hash table, the algorithm will eventually terminate. (i.e., no livelock.)

I think proof-of-progress reasoning is fun. ;)
Tags: algorithm, geek, interviews, programming
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments