Java concurrency package: Difference between revisions
imported>Kevin Meredith (→Queues) |
imported>Michael T. Rakszawski (Added example code using Runnable) |
||
Line 20: | Line 20: | ||
''Deadlock'' occurs when two or more threads are waiting for resources that are occupied by one another. This often causes computers to ''freeze''. | ''Deadlock'' occurs when two or more threads are waiting for resources that are occupied by one another. This often causes computers to ''freeze''. | ||
'' | ''Livelock'' is the condition when two or more threads are trying to avoid deadlock but prevent normal execution by doing so. | ||
''Starvation'' occurs when a thread is denied a resource. | ''Starvation'' occurs when a thread is denied a resource. |
Revision as of 21:19, 13 August 2010
To provide students with experience in collaboration, you are warmly invited to join in here, or to leave comments on the discussion page. The anticipated date of course completion is 13 August 2010. One month after that date at the latest, this notice shall be removed. Besides, many other Citizendium articles welcome your collaboration! |
![](http://s9.addthis.com/button1-share.gif)
The Java concurrency package is a library supporting threading and parallel programming in the Java programming language.
Introduction
As more and more computers are built with multi-core processors, concurrency has become an important topic in the field of computer science. Concurrency is "two or more threads running asynchronously, on one or more cores, usually in the same computer."[1] In contrast to linear programming, concurrent programming allows for the use of multiple processing resources to solve a problem, provided the software is built to take advantage of it.
Dangers of Concurrency
In concurrent programming, threads perform small packages of work. However, managing threads can be complicated, and if not managed correctly, can cause problems such as:
- Race conditions
- Deadlock
- Livelock
- Starvation
A race condition occurs when two threads try to access the same resource. This may cause an unexpected result.
Deadlock occurs when two or more threads are waiting for resources that are occupied by one another. This often causes computers to freeze.
Livelock is the condition when two or more threads are trying to avoid deadlock but prevent normal execution by doing so.
Starvation occurs when a thread is denied a resource.
Thread Safety
Programming languages are constantly being modified to support multithreaded programming and concurrency. The development of concurrency capabilities also comes with thread safety in order to avoid the common dangers. Thread safety generally takes two forms[2]:
- Lock-based synchronization
- Sophisticated data structures
Lock-based synchronization takes place when objects are limited to being modified by only one thread at a time. This prevents data from being corrupted by other threads that may want to access the resource at the same time.
Sophisticated data structures provide ways for programmers to handle threads without managing every minor detail of their communication and activities. These may include variations of queues, maps, or other data structures that are built specifically to handle concurrency.
Brief History of Concurrent Programming
Historically, concurrency has been implemented via the operating system.[3] It was only understood by experienced systems programmers who had to made system calls to manage threads. As the years passed, new programming languages appeared that provided built-in support for concurrency. Java is one example.
Introduction of Java
Java was built to support concurrency in that all Java applications contain threads of execution.[3] From its introduction, Java supported primitive multithreaded programming via the Runnable interface, which is part of the java.lang package. The Runnable interface provides the most basic functionality for multithreading.[3] Objects that are Runnable can be executed by a thread.
However, the Runnable interface had limited concurrency capabilities. Simple locks could be put in place on objects. Programmers had to use methods such as wait(), notify(), and notifyAll() to control locking and communication between threads. The Java developers noticed this and made significant improvements to the concurrency support with the introduction of J2SE 5.0.
Improved Concurrency Support in Java 5
J2SE 5.0 was released on September 29, 2004.[4] J2SE 5.0 introduced the java.util.concurrent package, which was designed for concurrency.[2] The package includes a number of standardized extensible frameworks. It contains five main components:
- Executors
- Queues
- Timing
- Synchronizers
- Concurrent Collections
Using the java.util.concurrent package, programmers can take advantage of sophisticated data structures that are built specifically for concurrent programming. A comprehensive list of the objects and methods available in the java.util.concurrent package can be found on the Java API.
Five Main Components
The Java API lists five main components of the java.util.concurrent package. Each of these five components is briefly described in this section
Executors
Executors handle Runnable interfaces by providing high-level thread management, cradle-to-grave of a thread’s life. Runnable interfaces define a block of code that shall be run when a thread starts. Consider this example,
// This class extends Thread
class BasicThread1 extends Thread {
// This method is called when the thread runs
public void run() {
}
}
A Java-focused website delivers the gist of Executors, “The new Executor framework solves all those [thread management] problems in a way that decouples task submission from the mechanics of how each task will be run, including the details of thread use, scheduling, etc”. [6] Without executors, a call to start a thread might look like this: new Thread (aRunnableObject).start (); Executors, which abstract the manual, non-trivial management of threads, would make this call to achieve the above result, Executor executor = some Executor factory method; exector.execute (aRunnable); In sum, the bottom line is that Executors make life easier for the concurrent Java programmer by dealing with the low-level details of thread management. [7]
Queues
Besides Executor, the thread management class, java.util.concurrent provides both blocking and non-blocking queues. This section illustrates the need for queues, namely a blocking queue example and sample code on non-blocking queues.
The following scenario demonstrates why queues are required in a multi-processor environment.
In this example, consider two people that have distinct jobs – one eats plates of food that are put on a table, and the other cooks plates of food and puts on a table. The table can only hold five plates of food at a time. What this means is that plates of food will fall on the ground if more than five are placed on it. As a result, a problem can arise when the cook makes plates of food faster than the eater can finish them. Eventually, the cook may exceed the five-plate capacity of the table, leading to a mess. On the other hand, the eater may eat plates of food faster than the cook can make them. If the cook does not hurry up, the eater may eat the table!
In order to solve the varying rates of the cook and eater, a blocking, i.e. waiting, queue gets created. A blocking queue, in the situation above, would require the cook to refrain from putting a plate of food on a table that already has five plates on it, i.e. reached capacity. Additionally, a blocking queue prevents the eater from biting into the table because the queue defines that the eater cannot try to eat zero plates. In sum, a blocking queue requires that the cook and eater (or threads) wait if the queue is either empty or full.
On the flip side, non-blocking queues do not require that critical sections get locked, which is how blocking-queues behave in the above example. The reason for implementing locks and blocking queues is to prevent race conditions. Now, let’s take at look at source code for implementation of a non-blocking queue. NonblockingCounter is not part of the java.util.concurrent package, however this example demonstrates the concept of a non-blocking queue.
public class NonblockingCounter {
private AtomicInteger value;
public int getValue() {
return value.get();
}
public int increment() {
int v;
do {
v = value.get();
}
while (!value.compareAndSet(v, v + 1));
return v + 1;
}
}
[8]
This class, NonBlockingCounter, makes use of atomic operations. An atomic operation means that the underlying assembly code fulfills the high-level programming language in a single line of code. The all at once characteristic appeals to concurrency since race conditions are a significant threat to a concurrent program. If an operation gets performed at one step, then there’s no threat of a race condition where multiple threads are accessing the same shared code region.
Next, a simple getValue() function gets created that simply returns the value of the AtomicInteger value.
Finally, the increment() function gets made. In this function, v calls value.get(), thus getting the value of value. After the value of v is checked, it then checks the value of v again to determine whether it has changed since last checking it. If the value changed, then it’s likely that another thread just called increment() successfully. If value gets incremented by another thread, it’s necessary to get the value again and calling while(!compareAndSet …) until it’s confirmed that value has not changed since we got its value. Again, the while(!value.compareAndSet(v, v+1)) checks to make sure that value has not changed since it was last checked by v = value.get(). Lastly, the program return v+1, thus increment value, when the while(!value.compareAndSet …) is true.
In sum, the java.util.concurrent package offers non-blocking and blocking queues to making sound concurrent programs.
Timing
TBD
Synchronizers
Mutilthread Synchronization before Java 5
Before Java 5, multithreads are supported using the lock mechanism for synchronization. Locks are implemented in Synchronized method. This mechanism “ensures that only one Java thread can execute an object's synchronized methods at a time” and “also allows threads to wait for resources to become available, and allows the thread that makes resources available to notify other threads that are waiting for the resources”. [9]. When the synchronized keyword is used, the thread which invokes the synchronized method must obtain a lock for the object which makes this thread the lock holder. The rule of thumb of synchronized method is that only one thread can hold this lock at a time.
Three most commonly used methods including, wait(), notify(), and notifyAll() are used for resource communication between threads.
“The wait() method can only be invoked by the object's lock holder. It causes current thread to wait until another thread invokes the notify() method or the notifyAll() method for this object” [10].
The notify() method wakes up one thread and only the notified thread can go ahead and do something. If there are more than one thread waiting on this object’s waiting queue, one of them is selected to be woke up. notify() wakes up the first thread in the waiting queue.
The notifyAll() method wakes up all threads in the wait set. notifyAll() is normally used when there are many threads to wake up simultaneously. Which thread gets the right to go ahead to execute depends upon thread property such as their priority.
One of the biggest issues of synchronized method is that it is an “all-or-nothing thing” [11]. “Once a thread attempts to enter a synchronized block, it will hang until the lock is available.” [11] which causes low performance because all other threads that need the same object have to wait. Another issue is that missing appropriate notifications such as notify() or notifyAll() while programming probably results in deadlock. [12]
Java 5: Synchronizers
In Java 5, the Java concurrent package provides four new classes including: semaphore, countdownlatch, cyclickbarrier, and exchanger, used for data synchronization [13].
Semaphore is a counting signal. It maintains a set of permits. The “parking garage” can be a good analogy as an example to explain it. We can think of that the permits in semaphore equals to the capability in a garage. If the permits that have been issued reach the maximum garage capacity, the garage is full. No parking permit can be issued. The garage will have some space for other cars when some permits are returned.
“CountDownLatch is a synchronization aid that allows one or more threads to wait until a set of operations being performed in other threads completes. It is initialized with a given count” [14]. Something here that needs to be mentioned that “CountDownLatch is a one-shot phenomenon” [14] meaning that the counter cannot be reused. If you need a counter that can be reset, consider using the CyclicBarrier method stating below.
CyclicBarriers is an aid “which allows a set of threads to wait for each other to reach a common barrier point” [14]. CyclicBarriers is useful when a fixed sized group of thread is occasionally but must wait for each other in a program. “The barrier is called cyclic because it can be re-used after the waiting threads are released” [14].
Exchanger is actually what the word looks like. “It is a synchronization point where two threads can exchange objects. Each thread presents some object on entry to the exchange method and receives the object presented by the other thread on return” [14].
Concurrent Collections
As it is mentioned in the beginning of synchronizer, the lock mechanism is implemented in “synchronized” classes before Java 5 and “synchronized” method will lock the object that’s been accessed by a thread. When an object is locked by one thread, other threads which need to access the same object are going to wait until the object is available. Also, only the resources in the object are protected. Other resources outside the object are not.
"Synchronized classes can be useful when you need to prevent all access to a collection through a single lock, at the expense of poorer scalability”[13].
Java realized this issue and therefore enhanced it by supplying some more collection implementations such as ConcurrentHashMap, CopyOnWriteArrayList , and CopyOnWriteArraySet. Here only basic concepts will be introduced here due to that this component is a very advanced one in java concurrent package. For more information, please refer to J2SE 5.0 official website Package java.util.concurrenct.
ConcurrentHashMap: “It synchronizes different segments in a hash table, not the whole object. Therefore, other threads can still access other segments that are not in synchronization” [15]. So other threads don’t have to wait. This provides the thread safety and also improves balances of the performance.
CopyOnWriteArrayList: “It uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible” [15]. This means no modification will be allowed when using CopyOnWriteArrayList. Therefore this operation is immutable and also guarantees thread-safety.
CopyOnWriteArraySet: It’s a data structure to protect the data during traversal for modification of the Array. With CopyOnWriteArraySet, any changes in the data structure during traversal results in a copy being made for the modification. However, there is something we have to keep in mind. This is used assuming in that there won’t be too many changes being made. If a lot of possible modifications need to be performed, we are talking a lot of copies as well which could be bad.
Conclusion
Capability
Java 5 still supports the standard concurrent unities which are contained in the previous version and has introduced the new java.util.concurrent package to make the life of concurrent development in Java easier by providing those high-quality implementations for the data synchronization mechanisms [15].
Advantages
The benefits of using java.util.concurrent package for developers include [15]
Unsolved Issue
The Java concurrency package is not a fix-all. Many of the common concurrent programming issues remain unresolved. The Java concurrency package still does not ensure there will not be any deadlock or CPU starvation in an application. It is the responsibility of developers to take appropriate actions to handle concurrency and data synchronization in their applications.
Related Articles
External Links
References
- ↑ A Concise Guide to Concurrent Programming. Retrieved on 2010-08-13.
- ↑ 2.0 2.1 The Java Programming Language, Fourth Edition, Arnold, Addison-Wesley © 2006 Sun Microsystems, Inc.
- ↑ 3.0 3.1 3.2 Java: How to Program, Sixth Edition, Deitel, Pearson © 2005
- ↑ J2SE Code Names. Retrieved on 2010-08-13.
- ↑ url =http://www.exampledepot.com/egs/java.lang/BasicThread.html, title = Creating a Thread
- ↑ url =http://www.exampledepot.com/egs/java.lang/BasicThread.html, title = Creating a Thread
- ↑ url = http://download-llnw.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/package-summary.htm, title = Package java.util.concurrent
- ↑ url =http://www.ibm.com/developerworks/java/library/j-jtp04186/index.html, title - Java theory and practice: Introduction to nonblocking algorithms
- ↑ Gary Shute. Java Synchronization. Retrieved on 2010-08-12.
- ↑ J2SE API v1.4.2. Retrieved on 2010-08-12.
- ↑ 11.0 11.1 Unknown. Problems with Java 1.4 synchronization model. Retrieved on 2010-08-12.
- ↑ V.K., Garg (September 2005). "A Critique of Java for Concurrent Programming". IEEE Computer Society 6 (9). Retrieved on 2010-08-12. [e]
- ↑ 13.0 13.1 J2SE API v5.0. Retrieved on 2010-08-12.
- ↑ 14.0 14.1 14.2 14.3 14.4 public class: CountDownLatch. Retrieved on 2010-08-12.
- ↑ 15.0 15.1 15.2 15.3
Qusay H. Mahmoud. Concurrent Programming with J2SE 5.0. Retrieved on 2010-08-12.
Cite error: Invalid
<ref>
tag; name "Concurrent Programming with J2SE 5.0" defined multiple times with different content Cite error: Invalid<ref>
tag; name "Concurrent Programming with J2SE 5.0" defined multiple times with different content