-
Notifications
You must be signed in to change notification settings - Fork 0
Two Lock Queue
Mykhailo Sobko edited this page Sep 3, 2022
·
5 revisions
Implementation here
It is a simple concurrent First-In-First-Out (FIFO) queue using two mutexes. It is based on a singly linked list with the support for blocking dequeues.
Separate mutexes are used for the head and tail to allow complete concurrency between enqueues and dequeues. As in the non-blocking queue, we keep a dummy node at the beginning of the list. Because of the dummy node, enqueuers never have to access the head, and dequeuers never have to access the tail, thus avoiding potential deadlock problems that arise from processes trying to acquire the locks in different orders.
It is described in the same paper as the Michael & Scott lock-free queue. The dummy node concept is also explained here.
- Concurrent Queue Algorithms: https://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf
- M&S Queue: https://github.com/alorthius/libmtds/wiki/M&S-Queue