Remember the Fairness Policy
It is wise to keep in mind the fairness policy when using concurrent data structures such as ArrayBlockingQueue to support thread safety. You need to make a decision: when multiple threads are waiting for the same lock, which thread is granted the lock?
The reentrantLocks (as in JDK 1.5) class offers two fairness options:
- Fair Lock: This option grants the lock to the longest-waiting thread and thus avoids thread starvation.
- Nonfair Lock: This option does not guarantee any particular access order.
Overall, throughput using fair locks may be degraded under heavy contention (for instance, when multiple threads require the same lock), due to the time differentiation between when a suspended thread is ready to run and when it actually runs. However, if you opt for the fair lock policy, every candidate thread gets a CPU share, regardless of the priority of other waiting threads. You must evaluate this tradeoff based on how much latency a thread can endure.
A Non-blocking Algorithm (Lock Free and Wait Free)
Non-blocking algorithms are both lock- and wait-free because they don't use synchronization primitives such as mutexes or semaphores (as of JDK 1.5) or synchronized constructs.
Because locks are not involved, these implementations are immune to deadlocks but may require repeated retries which can result in thread starvation. Coordination between these threads is accomplished through an atomic operation called compare and swap (CAS). This enables the implementations to maintain thread safety. ConcurrentLinkedQueue is an example that uses this algorithm.
The Big-O Notation: Quantifying Performance
Big-O notation helps you to compare the efficiency of methods across Collection implementations, so that you can pick and choose the right one, based on the problem set. For example, the contains(element) method in the Collection API has a time efficiency of O(n). This means that, in the worst case, you have to search the whole collection, where n represents the number of elements in the collection.
In most collections, size() generally takes a single operation (return the count variable containing the size) and thus has the efficiency of O(1). However, in some implementations (like ConcurrentLinkedQueue), size() has an efficiency of O(n)—due to the need to count the elements. Several terms describe commonly used Big-O efficiencies:
| Notation |
Name |
| O(1) |
constant |
| O(n) |
linear |
| O(log(n)) |
logarithmic |
Now it's time to learn how to use Queue collections in the context of the above design parameters of memory consistency, iteration protection, thread fairness, blocking and non-blocking algorithms, and efficiency as described by Big-O notation.
New on the Java Boutique:
New Review:
Time Management Made Easy with the Quartz Enterprise Job Scheduler
Why not just use the Java timer API? This open source scheduling
API boasts simplicity, ease-of-integration, a well-rounded feature
set, and it's free!
New Applet:
Reverse Complement
Reverse Complement is a simple applet that converts DNA or RNA
sequences into three useful formats.
Elsewhere on internet.com:
WebDeveloper Java
Lots of Java information on webdeveloper.com
WDVL Java
Thorough Java resource at the Web Developer's Virtual Library.
ScriptSearch Java
Hundreds of free Java code files to download.
jGuru: Your View of the Java Universe
Customizable portal with online training, FAQs, regular news updates, and tutorials.
