How do we maintain order of elements in a Bounded Blocking Queue

user_4719856 0
Viewed 308

A queue by virtue of its definition should be a FIFO kind of structure. While we make it blocking, it means that several threads might be blocked on adding new elements, when the size of the queue is equal to MAX_LIMIT of queue size. Now if one element got dequeued from the queue, how do we ensure that the thread which was waiting for the first time is able to execute.

concurrency queue multithreading java
2 Answers

If you read the documentation of a particular implementation, you will e.g. find:

  • ArrayBlockingQueue

    This class supports an optional fairness policy for ordering waiting producer and consumer threads. By default, this ordering is not guaranteed. However, a queue constructed with fairness set to true grants threads access in FIFO order. Fairness generally decreases throughput but reduces variability and avoids starvation.

  • LinkedBlockingQueue

    No fairness guarantees are available.

  • SynchronousQueue

    This class supports an optional fairness policy for ordering waiting producer and consumer threads. By default, this ordering is not guaranteed. However, a queue constructed with fairness set to true grants threads access in FIFO order.

user_52211490

See @Andreas' answer for a summary of how regular queue classes handle this.

But I'm going to suggest an alternative approach / way of looking at this.

You are proposing a scenario where threads are blocking because they can't add to a queue. If this is occurring, then your biggest problem from a performance perspective is the resources and locks used / held by the blocked threads.

In general, there are two possible causes for this:

  1. You have a short-term imbalance between the rate at which queue entries are being added and removed. This can be solved by simply increasing the queue bounds.

  2. You have a long-term imbalance between the rate at which queue entries are being added and removed. This can only be solved by adding more consumer threads and/or removing worker threads.

The point is that if you can make threads not need to block, you don't need to worry about the fairness of blocked thread.

The other issue is whether fairness actually matters. Does it really matter that entries are added to the queue in a strictly fair fashion? Does it impact on the correctness of the application? (Will the users be able to tell when their request is held back ... or overtakes another user's request?)

(I can imagine some scenarios where strict fairness is a requirement. But they are a tiny minority.)

And if strict fairness is a requirement, what about the handling of the request that happens before the request is added to the queue. Does that need to be fair too? Because the JVM and the OS do not provide any guarantees that thread scheduling is fair.

Basically, making request handling totally fair is an intractable problem. So for most scenarios there is little point in implementing strict fairness of FIFO queue submission.

user_1399850
Related