My objective is to maintain a durable priority queue in a storage medium that has no locking mechanism. (Although the storage medium itself is actually backed by a database, I'm not allowed to interact with the database directly. Yes, asinine, I know. If I could I wouldn't be trying to implement my own mutex.) I may have one or more "producers" that can write into the queue, and one or more "consumers" trying to perform an operation based on the item at the head of the queue. Once the operation completes will the item be removed from the queue. No other "consumer" must do the same operation in parallel. Should the operation not be completed, due to "process" crashes or user initiated terminations, the operation should be retried the next time a "consumer" comes back online. I figured I'd tackle issue of retrying later by using the same strategy used by databases to by replaying its logs.)
Some of the things I've already considered:
- Lamport's Distributed Mutual Exclusion Algorithm. Again I don't know how many "nodes" there are to send the requests to, and I can be left hanging with "nodes" just terminating effectively randomly.
- Lock free queues. On the plus side, I don't have to know how many producers/consumers. On the downside, all the literature I've run across requires atomic primitives like compare&swap.
- Use Windows Workflow Foundation, implement my own persistent service, and assume that WWF's calls to my custom persistence services knows how to handle potentially colliding writes into the common durable storage medium.
It's possible, I maybe too fixated on using Lamport's Bakery Algorithm because of the little jewel floating before my eyes by Lamport's reflections about his algorithm:
What is significant about the bakery algorithm is that it implements mutual exclusion without relying on any lower-level mutual exclusion.