4 ms·
Sometimes the producer has to insert something in the middle of the queue, is it possible to make this queue lock free?
by chj 14y ago
Sometimes the producer has to insert something in the middle of the queue, is it possible to make this queue lock free?
- ams6110 14y agoIt's not really a queue then, is it?
- spenczar5 14y agoSure it is. Priority queues are a common example of this behavior, and they're still queues. chj's question is interesting. It's not obvious how to build a lock-free code in the original article's framework if you aren't representing your queue as a list, but many queues are not represented this way. If you need this 'insert in the middle of the queue' operation, you probably aren't representing your queue as with a linked list since insertion will be inefficient - chances are you're using a heap.
- NeutronBoy 14y agoYou could maintain separate queues for each priority, and always process them from the top down.
- chj 14y agoOK, now I guess event queue can also be lock free. Use one lock free queue as the article described for incoming events from the producer, and another queue with the event sorted by the consumer.
- chj 14y agoThis sounds great for priority queues. But how about an event queue, where every event has a time tag?