Skip to content

A Locked Queue in a concurrent FIFO queue that uses locks and conditions to block enqueue when queue is full, and dequeue when it is empty.

License

Notifications You must be signed in to change notification settings

javaf/locked-queue

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

5 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Locked Queue uses locks and conditions to block when queue is empty, or it is full. Just as locks are inherently vulnerable to deadlock, Condition objects are inherently vulnerable to lost wakeups in which one or more threads wait forever without realizing that the condition for which they are waiting has become true.

This queue signals "not empty" whenever an item is added to the queue, and "not full" whenever an item is removed from the queue. However, consider an optimization, where you only signal "not empty" if the queue was empty. Bang! Lost wakeup is suddenly possible.

To see how that is possible, consider 2 consumers A & B and 2 producers C & D. When queue is empty and both A & B have to remove(), they are blocked until C or D can add(). If C add()s, followed by D, only 1 "not empty" condition would be active causing C to wakeup, but not D.

Hence, one needs to be careful when working with both locks and condition objects.

The functionality of this queue is similar to BlockingQueue and does not suffer from the lost wakeup problem.

Course: Concurrent Data Structures, Monsoon 2020
Taught by: Prof. Govindarajulu Regeti

add():
1. Acquire lock before any action.
2. Wait for queue being not full.
3. Add item to queue.
4. Release the lock.
remove():
1. Acquire lock before any action.
2. Wait for queue being not empty.
3. Remove item from queue.
4. Release the lock.

See LockedQueue.java for code, Main.java for test, and repl.it for output.

references

About

A Locked Queue in a concurrent FIFO queue that uses locks and conditions to block enqueue when queue is full, and dequeue when it is empty.

Topics

Resources

License

Stars

Watchers

Forks

Languages