CODEWITHSUNDEEP
calgorithmdata-structuresconcurrency
zwol
zwol

Reputation: 140669

Interrupt-safe set scan

I need a data structure fulfilling these somewhat unusual (AFAIK) requirements:

  1. Supported operations are Insert(set, item), Delete(set, item), and ForAll(set, operation)
  2. Insert and Delete are rare operations. It is typical for the set to contain only one item.
  3. Implementation must be feasible in C; in particular, no garbage collection for you.
  4. ForAll must be safe to execute from an asynchronous signal handler, whose invocation may have interrupted an Insert or Delete.

That last requirement is the killer, of course. I have a toy implementation that throws a global lock around a global linked list, but that's going to deadlock if the signal handler interrupts a critical section.

(I am aware of all the problems with executing any code in a signal handler; for purpose of this question, let's focus on how you make ForAll crash- and deadlock-safe when it might have interrupted an Insert or Delete.)

Upvotes: 4

Views: 174

Answers (2)

quaint
quaint

Reputation: 131

I'm sure Jim's approach is fine, but with small sets and infrequent updates, you might be happier implementing the simplest form of software transactional memory.

  1. Read the pointer to the current version of the structure.
  2. Make a copy of that version and update it.
  3. Compare-and-swap in the update. If the CAS fails, go back to step 1.

Asynchronous scans are trivial – read and go. Without garbage collection, you'll need to use something like SafeRead and Release from the paper Jim linked.

Upvotes: 1

Jim Mischel
Jim Mischel

Reputation: 134015

If the sets are typically small, such that a linear search of the list is fast enough in the Insert and Delete methods, then you can use a lock-free linked list implementation that uses compare-and-swap. A search gives a number of explanations and examples.

http://www.google.com/search?q=lock+free+linked+list

All updates to the list are done as atomic operations (compare-and-swap), so an interrupt won't cause a problem.

Upvotes: 6

Related Questions