Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why the ArrayBlockingQueue is called a bounded queue while a LinkedBlockingQueue is called an unbounded blocking queue?

As far as I know both the linked list and array can grow without bounds or am I wrong ? But when I have gone through the documentation in the Executor Service I see this :

Unbounded queues. Using an unbounded queue (for example a LinkedBlockingQueue without a predefined capacity) will cause new tasks to wait in the queue when all corePoolSize threads are busy. Thus, no more than corePoolSize threads will ever be created. (And the value of the maximumPoolSize therefore doesn't have any effect.)

So does the Unbounded Queue property changes when the LinkedBlockingQueue has a defined capacity ?

And this written for ArrayBlockingQueue:

Bounded queues. A bounded queue (for example, an ArrayBlockingQueue) helps prevent resource exhaustion when used with finite maximumPoolSizes, but can be more difficult to tune and control. Queue sizes and maximum pool sizes may be traded off for each other: Using large queues and small pools minimizes CPU usage, OS resources, and context-switching overhead, but can lead to artificially low throughput. If tasks frequently block (for example if they are I/O bound), a system may be able to schedule time for more threads than you otherwise allow. Use of small queues generally requires larger pool sizes, which keeps CPUs busier but may encounter unacceptable scheduling overhead, which also decreases throughput.

like image 272
Geek Avatar asked Aug 06 '12 14:08

Geek


People also ask

What is bounded queue and unbounded queue?

Bounded Queues are queues which are bounded by capacity that means we need to provide the max size of the queue at the time of creation. For example ArrayBlockingQueue (see previous example). Unbounded Queues are queues which are NOT bounded by capacity that means we should not provide the size of the queue.

What is difference between ArrayBlockingQueue and LinkedBlockingQueue in Java concurrency?

ArrayBlockingQueue is bounded which means the size will never change after its creation. LinkedBlockingQueue is optionally bounded which means it can optionally have an upper bound if desired.

What is a bounded queue?

A bounded queue is a queue limited to a fixed number of items. There are several efficient implementations of FIFO queues. An efficient implementation is one that can perform the operations—en-queuing and de-queuing—in O(1) time.

What is bounded blocking queue?

A blocking queue is defined as a queue which blocks the caller of the enqueue method if there's no more capacity to add the new item being enqueued. Similarly, the queue blocks the dequeue caller if there are no items in the queue.


2 Answers

other answer is very right! I provide another way to explain. well, I also get confused by the term "unbound and bound" passed. you can look at the source code blew.

    /** The queued items */
final Object[] items;

/** items index for next take, poll, peek or remove */
int takeIndex;

/** items index for next put, offer, or add */
int putIndex;

/** Number of elements in the queue */
int count;

from the source code, we can see the array is final, so we can not resize the array. if use LinkedBlockingQueue, we can always add more elements...and in the source code, the next reference is not final. NOTE, in theory, LinkedBlockingQueue is not unbounded. because it can only store MAX_INTEGER minus 8 elements. from javadoc, the unbounded queue is PriorityBlockingQueue. but the PriorityBlockingQueue also can only store MAX_INTEGER -8 elements. so i think there is no perfect unbounded queue...

like image 81
wannibar Avatar answered Nov 03 '22 00:11

wannibar


Why do you think that an ArrayBlockingQueue can grow without bounds? From its own documentation:

This is a classic "bounded buffer", in which a fixed-sized array holds elements inserted by producers and extracted by consumers. Once created, the capacity cannot be increased. Attempts to put an element into a full queue will result in the operation blocking; attempts to take an element from an empty queue will similarly block.

In other words, once it gets full, it's full - it doesn't grow.

Are you getting confused with an ArrayList by any chance - which is also backed by an array, but which expands this as required?

So does the Unbounded Queue property changes when the LinkedBlockingQueue has a defined capacity ?

Yes, hence why it's described as "optionally-bounded" in its Javadocs. Furthermore, the docs state that (emphasis mine):

The optional capacity bound constructor argument serves as a way to prevent excessive queue expansion. The capacity, if unspecified, is equal to Integer.MAX_VALUE. Linked nodes are dynamically created upon each insertion unless this would bring the queue above capacity.

like image 30
Andrzej Doyle Avatar answered Nov 03 '22 01:11

Andrzej Doyle