Java concurrency package: Difference between revisions
imported>Kevin Meredith (→Timing) |
Pat Palmer (talk | contribs) (dealing with ref errors) |
||
(39 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
{{TOC|right}} | {{TOC|right}} | ||
The '''Java concurrency package''' is a library supporting threading and parallel programming in the Java programming language. | The '''Java concurrency package''' is a library supporting threading and parallel programming in the [[Java_programming_language|Java programming language]]. | ||
==Introduction== | ==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."<ref name="Matuszek">{{cite web|url=http://www.cis.upenn.edu/~matuszek/cis700-2010/Pages/concise_concurrency.html|title=A Concise Guide to Concurrent Programming|accessdate=2010-08-13|}}</ref> 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. | 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."<ref name="Matuszek">{{cite web|url=http://www.cis.upenn.edu/~matuszek/cis700-2010/Pages/concise_concurrency.html|title=A Concise Guide to Concurrent Programming|accessdate=2010-08-13|}}</ref> 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. | ||
Line 16: | Line 16: | ||
* Starvation | * Starvation | ||
A ''race condition'' occurs when two threads try to access the same resource. This may cause an unexpected result. | A ''race condition'' occurs when two threads try to access the same resource. This may cause an unexpected result in program execution. | ||
''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''. | ||
Line 26: | Line 26: | ||
===Thread Safety=== | ===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 | Programming languages are constantly being modified to support multithreaded programming and concurrency. The development of concurrency capabilities also comes with putting thread safety measures in place to avoid or prevent the common dangers. Thread safety generally takes two forms<ref name=Arnold />: | ||
* Lock-based synchronization | * Lock-based synchronization | ||
* Sophisticated data structures | * Sophisticated data structures | ||
Line 40: | Line 40: | ||
Java was built to support concurrency in that all Java applications contain ''threads of execution''.<ref name=Deitel /> 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.<ref name=Deitel /> Objects that are ''Runnable'' can be executed by a thread. | Java was built to support concurrency in that all Java applications contain ''threads of execution''.<ref name=Deitel /> 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.<ref name=Deitel /> Objects that are ''Runnable'' can be executed by a thread. | ||
However, the ''Runnable'' interface had limited | public class MyThreadingExample implements Runnable { | ||
. | |||
. | |||
. | |||
} | |||
However, even though it supported concurrency, the ''Runnable'' interface had limited capabilities. It allowed simple locks to 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 these limited capabilities and made significant improvements to the concurrency support with the introduction of J2SE 5.0. | |||
==Improved Concurrency Support in Java 5== | ==Improved Concurrency Support in Java 5== | ||
Line 54: | Line 60: | ||
==Five Main Components== | ==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 | 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=== | ||
Executors handle Runnable interfaces by providing high-level thread management, cradle-to-grave | Executors handle Runnable interfaces by providing high-level thread management, cradle-to-grave. Runnable interfaces define a block of code that shall be run when a thread starts. Consider this example. | ||
// This class extends Thread | // This class extends Thread | ||
class BasicThread1 extends Thread { | class BasicThread1 extends Thread { | ||
Line 66: | Line 71: | ||
} | } | ||
} | } | ||
<ref name="Create Thread">{{cite web|url=http://www.exampledepot.com/egs/java.lang/BasicThread.html|title=Creating a Thread|}}</ref> | |||
<ref>url =http://www.exampledepot.com/egs/java.lang/BasicThread.html | |||
A Java-focused web site 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”. <ref name="Create Thread"/> 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, | 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); | Executor executor = some Executor factory method; | ||
In | exector.execute (aRunnable); | ||
In summary, the bottom line is that Executors make life easier for the concurrent Java programmer by dealing with the low-level details of thread management. | |||
===Queues=== | ===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 | 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 a non-blocking queue. | ||
The following scenario demonstrates why queues are required in a multi-processor environment. | The following scenario demonstrates why queues are required in a multi-processor environment. | ||
Line 87: | Line 94: | ||
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. | 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;<br /> | |||
public int getValue() { | |||
return value.get(); | |||
}<br /> | |||
public int increment() { | |||
int v; | |||
do { | |||
v = value.get(); | |||
} | |||
while (!value.compareAndSet(v, v + 1)); | |||
return v + 1; | |||
} | |||
} | |||
<ref name="non-blocking">{{ cite web| url =http://www.ibm.com/developerworks/java/library/j-jtp04186/index.html| title = Java theory and practice: Introduction to nonblocking algorithms|}} </ref> | |||
This class, NonBlockingCounter, makes use of atomic operations. An atomic operation provides "atomic read-modify-write operations for safely updating shared variables without locks" <ref name="non-blocking" />. The all at once characteristic appeals to concurrency since race conditions pose a significant danger to concurrent programs. 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. | |||
This class, NonBlockingCounter, makes use of atomic operations. An atomic operation | |||
Next, a simple getValue() function gets created that simply returns the value of the AtomicInteger value. | Next, a simple getValue() function gets created that simply returns the value of the AtomicInteger value. | ||
Finally, the increment() function gets | Finally, the increment() function gets defined. 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 | In summary, the java.util.concurrent package offers non-blocking and blocking queues to making sound concurrent programs. | ||
===Timing=== | ===Timing=== | ||
Besides Executors to manage low-level thread operations, and Queues to prevent race conditions, the java.util.concurrent package offers a helpful TimeUnit class simplifies conversion | Besides Executors to manage low-level thread operations, and Queues to prevent race conditions, the java.util.concurrent package offers a helpful TimeUnit class that simplifies conversion between units of time, e.g. seconds to nanoseconds. TimeUnit delivers value to a programmer by making it easier to specify time intervals, says Oracle's man page for the java.util.concurrent package <ref>{{cite web| | ||
url= http://download-llnw.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/package-summary.html | | |||
title = java.util.concurrent package|}} | |||
</ref>. | |||
Life without the TimeUnit class involves non-trivial computation of time intervals. | |||
Consider the ease of making a single minute in millseconds: | Consider the ease of making a single minute in millseconds: | ||
Long oneMinute = TimeUnit.SECONDS.toMillis(60); // 60 seconds in ms | Long oneMinute = TimeUnit.SECONDS.toMillis(60); // 60 seconds in ms | ||
===Synchronizers=== | ===Synchronizers=== | ||
====Mutilthread Synchronization before Java 5==== | ====Mutilthread Synchronization before Java 5==== | ||
In Java versions before Java 5, multithreads are supported using the lock mechanism for synchronization. Locks are implemented in the 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”. | |||
Locks are implemented in | |||
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”. | |||
<ref name="Java Synchronization"> | <ref name="Java Synchronization"> | ||
{{cite web| | {{cite web| | ||
Line 135: | Line 140: | ||
accessdate=2010-08-12 | | accessdate=2010-08-12 | | ||
author=Gary Shute| }} | author=Gary Shute| }} | ||
</ref>. When the | </ref>. 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 the synchronized method is that only one thread can hold this lock at a time. | ||
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 | Three commonly used methods, namely '''wait()''', '''notify()''', and '''notifyAll()''', are used for resource communication between threads. | ||
resource communication between threads. | |||
“The wait() method can only be invoked by the object's lock holder. It causes current thread | “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” | ||
to wait until another thread invokes the notify() method or the notifyAll() method for this | |||
object” | |||
<ref name="J2SE API v1.4.2"> | <ref name="J2SE API v1.4.2"> | ||
{{cite web| | {{cite web| | ||
Line 153: | Line 152: | ||
</ref>. | </ref>. | ||
The notify() method wakes up one thread and only the notified thread can go ahead and do | The notify() method wakes up one thread, and only the notified thread can go ahead and do something. If there is more than one thread waiting on this object’s waiting queue, one of them is selected to be woken up. notify() wakes up the first thread in the waiting queue. | ||
something. If there | |||
of them is selected to be | |||
The notifyAll() method wakes up all threads in the wait set. notifyAll() is normally used | 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. | ||
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” | One of the biggest issues of the synchronized method is that it is an “all-or-nothing thing” | ||
<ref name="Problems with Java 1.4 synchronization model"> | <ref name="Problems with Java 1.4 synchronization model"> | ||
{{cite web| | {{cite web| | ||
Line 167: | Line 162: | ||
title=Problems with Java 1.4 synchronization model| | title=Problems with Java 1.4 synchronization model| | ||
accessdate=2010-08-12 | | accessdate=2010-08-12 | | ||
author= | author=Neil Coffey| }} | ||
</ref>. | </ref>. | ||
“Once a thread attempts to enter a synchronized block, it will hang until the lock is available.” | “Once a thread attempts to enter a synchronized block, it will hang until the lock is available.” | ||
<ref name="Problems with Java 1.4 synchronization model"> | <ref name="Problems with Java 1.4 synchronization model"/> | ||
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 can result in deadlock. <ref name="A Critique of Java for Concurrent Programming"> | |||
Another issue is that missing appropriate notifications such as notify() or notifyAll() while | |||
programming | |||
{{cite journal | {{cite journal | ||
| last = V.K. | | last = V.K. | ||
Line 196: | Line 184: | ||
====Java 5: Synchronizers==== | ====Java 5: Synchronizers==== | ||
In Java 5, the Java | In Java 5, the Java concurrency package provides four new classes including: '''semaphore''', | ||
'''countdownlatch''', ''' | '''countdownlatch''', '''cyclicbarrier''', and '''exchanger''', used for data synchronization | ||
<ref name="J2SE API v5.0"> | <ref name="J2SE API v5.0"> | ||
{{cite web| | {{cite web| | ||
Line 205: | Line 193: | ||
</ref>. | </ref>. | ||
''Semaphore'' is a counting signal. It maintains a set of permits. The “parking garage” can be | ''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 imagine that the permits in a semaphore are similar to the permits required to park in a parking garage with limited capacity. 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 only have space for other cars when some permits are returned. Semaphore work in a similar fashion. | ||
a good analogy as an example to explain it. We can | |||
garage capacity, the garage is full. No parking permit can be issued. The garage will have | |||
“''CountDownLatch'' is a synchronization aid that allows one or more threads to wait until a set | “''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” | ||
of operations being performed in other threads completes. It is initialized with a given count” | |||
<ref name="public class: CountDownLatch"> | <ref name="public class: CountDownLatch"> | ||
{{cite web| | {{cite web| | ||
Line 218: | Line 201: | ||
title=public class: CountDownLatch| | title=public class: CountDownLatch| | ||
accessdate=2010-08-12 |}} | accessdate=2010-08-12 |}} | ||
</ref>. Something here that needs to be mentioned that “CountDownLatch is a one-shot phenomenon” | </ref>. Something here that needs to be mentioned is that “CountDownLatch is a one-shot phenomenon” | ||
<ref name="public class: CountDownLatch"> | <ref name="public class: CountDownLatch"> | ||
{{cite web| | {{cite web| | ||
Line 224: | Line 207: | ||
title=public class: CountDownLatch| | title=public class: CountDownLatch| | ||
accessdate=2010-08-12 |}} | accessdate=2010-08-12 |}} | ||
</ref> meaning that the counter cannot be reused. If you need a counter that can be reset, consider | </ref> meaning that the counter cannot be reused. If you need a counter that can be reset, consider using the CyclicBarrier method. | ||
using the CyclicBarrier method | |||
''CyclicBarriers'' is an aid “which allows a set of threads to wait for each other to reach a | ''CyclicBarriers'' is an aid “which allows a set of threads to wait for each other to reach a common barrier point” <ref name="public class: CountDownLatch"> | ||
common barrier point” <ref name="public class: CountDownLatch"> | |||
{{cite web| | {{cite web| | ||
url= http://www.docjar.com/docs/api/java/util/concurrent/CountDownLatch.html| | url= http://www.docjar.com/docs/api/java/util/concurrent/CountDownLatch.html| | ||
title=public class: CountDownLatch| | title=public class: CountDownLatch| | ||
accessdate=2010-08-12 |}} | accessdate=2010-08-12 |}} | ||
</ref>. CyclicBarriers is useful when a fixed sized group of | </ref>. CyclicBarriers is useful when a fixed sized group of threads must | ||
occasionally | occasionally wait for each other in a program. “The barrier is called cyclic because it can be re-used after the waiting threads are released” <ref name="public class: CountDownLatch"> | ||
it can be re-used after the waiting threads are released” <ref name="public class: CountDownLatch"> | |||
{{cite web| | {{cite web| | ||
url= http://www.docjar.com/docs/api/java/util/concurrent/CountDownLatch.html| | url= http://www.docjar.com/docs/api/java/util/concurrent/CountDownLatch.html| | ||
Line 242: | Line 222: | ||
</ref>. | </ref>. | ||
''Exchanger'' is actually what the word looks like. “It is a synchronization point where two | ''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” <ref name="public class: CountDownLatch"> | ||
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” <ref name="public class: CountDownLatch"> | |||
{{cite web| | {{cite web| | ||
url= http://www.docjar.com/docs/api/java/util/concurrent/CountDownLatch.html| | url= http://www.docjar.com/docs/api/java/util/concurrent/CountDownLatch.html| | ||
Line 252: | Line 230: | ||
===Concurrent Collections=== | ===Concurrent Collections=== | ||
As | As mentioned in the beginning of the Synchronizer section, a lock mechanism is implemented in “synchronized” classes before Java 5. In such cases, the “synchronized” method will lock the object that has been | ||
“synchronized” classes before Java 5 | accessed by a thread. When the object is locked by one thread, other threads which need to access the same object must wait until the object is available. Note that only the resources in the object are protected by the lock. Other resources outside the object are not protected. | ||
accessed by a thread. When | |||
access the same object | |||
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 | "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”<ref name="J2SE API v5.0"> | ||
a single lock, at the expense of poorer scalability”<ref name="J2SE API v5.0"> | |||
{{cite web| | {{cite web| | ||
url= http://download.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/package-summary.html| | url= http://download.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/package-summary.html| | ||
Line 266: | Line 240: | ||
</ref>. | </ref>. | ||
Java realized this issue and therefore enhanced it by supplying some more collection implementations | Java realized this issue and therefore enhanced it by supplying some more collection implementations such as ConcurrentHashMap, CopyOnWriteArrayList, and CopyOnWriteArraySet. Only basic concepts | ||
such as ConcurrentHashMap, CopyOnWriteArrayList , and CopyOnWriteArraySet. | will be introduced here due to the complexity of this component in the Java concurrency package. | ||
will be introduced here due to | For more information, please refer to the J2SE 5.0 official web site for the [http://download.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/package-summary.html java.util.concurrent] package. | ||
For more information, please refer to J2SE 5.0 official | |||
''ConcurrentHashMap:'' | ''ConcurrentHashMap:'' | ||
“It synchronizes different segments in a hash table, not the whole object. Therefore, other | “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” | ||
threads can still access other segments that are not in synchronization” | |||
<ref name="Concurrent Programming with J2SE 5.0"> | <ref name="Concurrent Programming with J2SE 5.0"> | ||
{{cite web| | {{cite web| | ||
Line 280: | Line 252: | ||
accessdate=2010-08-12 | | accessdate=2010-08-12 | | ||
author=Qusay H. Mahmoud| }} | author=Qusay H. Mahmoud| }} | ||
</ref>. | </ref>. Other threads do not have to wait. This provides thread safety and also improves performance. | ||
performance. | |||
''CopyOnWriteArrayList:'' | ''CopyOnWriteArrayList:'' | ||
“It uses a reference to the state of the array at the point that the iterator was created. This | “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” | ||
array never changes during the lifetime of the iterator, so interference is impossible” | <ref name="Concurrent Programming with J2SE 5.0"/> | ||
<ref name="Concurrent Programming with J2SE 5.0"> | . This means no modification will be allowed when using CopyOnWriteArrayList. Therefore this operation is immutable and also guarantees thread-safety. | ||
operation is immutable and also guarantees thread-safety. | |||
''CopyOnWriteArraySet:'' | ''CopyOnWriteArraySet:'' | ||
This is a data structure used to protect the data during traversal for modification of an array. | |||
With CopyOnWriteArraySet, any changes in the data structure during traversal | With CopyOnWriteArraySet, any changes in the data structure during traversal result in a copy being made for the modification. However, there is something more to keep in mind. This technique is used assuming that there will not be many changes being made. If many modifications need to be performed, the CopyOnWriteArraySet will create many copies, which could be bad. | ||
being made for the modification. However, there is something | |||
is used assuming | |||
modifications need to be performed, | |||
==Conclusion== | ==Conclusion== | ||
The Java concurrency package provided in J2SE 5.0 and beyond is a powerful tool, but it does not prevent all concurrency dangers from becoming a reality. | |||
===Capability=== | ===Capability=== | ||
Java 5 still supports the standard concurrent unities which are contained in the previous | 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 | 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 | development in Java easier by providing those high-quality implementations for the data | ||
synchronization mechanisms <ref name="Concurrent Programming with J2SE 5.0" | synchronization mechanisms <ref name="Concurrent Programming with J2SE 5.0"/>. | ||
===Advantages=== | ===Advantages=== | ||
The benefits of using java.util.concurrent package for developers include | The benefits of using java.util.concurrent package for developers include: | ||
<ref name="Concurrent Programming with J2SE 5.0" | <ref name="Concurrent Programming with J2SE 5.0"/> | ||
* Shorter and less messy application code | |||
* Faster application implementation on schedule | |||
* More scalable in data synchronization | |||
* More readability and write ability for development and debugging | |||
* Easier maintenance | |||
===Unsolved Issue=== | ===Unsolved Issue=== |
Latest revision as of 10:32, 26 July 2024
![](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 in program execution.
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 putting thread safety measures in place to avoid or prevent 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.
public class MyThreadingExample implements Runnable { . . . }
However, even though it supported concurrency, the Runnable interface had limited capabilities. It allowed simple locks to 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 these limited capabilities 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. 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 web site 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”. [5] 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 summary, the bottom line is that Executors make life easier for the concurrent Java programmer by dealing with the low-level details of thread management.
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 a non-blocking queue.
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; } }
This class, NonBlockingCounter, makes use of atomic operations. An atomic operation provides "atomic read-modify-write operations for safely updating shared variables without locks" [6]. The all at once characteristic appeals to concurrency since race conditions pose a significant danger to concurrent programs. 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 defined. 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 summary, the java.util.concurrent package offers non-blocking and blocking queues to making sound concurrent programs.
Timing
Besides Executors to manage low-level thread operations, and Queues to prevent race conditions, the java.util.concurrent package offers a helpful TimeUnit class that simplifies conversion between units of time, e.g. seconds to nanoseconds. TimeUnit delivers value to a programmer by making it easier to specify time intervals, says Oracle's man page for the java.util.concurrent package [7].
Life without the TimeUnit class involves non-trivial computation of time intervals.
Consider the ease of making a single minute in millseconds:
Long oneMinute = TimeUnit.SECONDS.toMillis(60); // 60 seconds in ms
Synchronizers
Mutilthread Synchronization before Java 5
In Java versions before Java 5, multithreads are supported using the lock mechanism for synchronization. Locks are implemented in the 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”. [8]. 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 the synchronized method is that only one thread can hold this lock at a time.
Three commonly used methods, namely 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” [9].
The notify() method wakes up one thread, and only the notified thread can go ahead and do something. If there is more than one thread waiting on this object’s waiting queue, one of them is selected to be woken 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 the synchronized method is that it is an “all-or-nothing thing” [10]. “Once a thread attempts to enter a synchronized block, it will hang until the lock is available.” [10]
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 can result in deadlock. [11]
Java 5: Synchronizers
In Java 5, the Java concurrency package provides four new classes including: semaphore, countdownlatch, cyclicbarrier, and exchanger, used for data synchronization [12].
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 imagine that the permits in a semaphore are similar to the permits required to park in a parking garage with limited capacity. 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 only have space for other cars when some permits are returned. Semaphore work in a similar fashion.
“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” [13]. Something here that needs to be mentioned is that “CountDownLatch is a one-shot phenomenon” [13] meaning that the counter cannot be reused. If you need a counter that can be reset, consider using the CyclicBarrier method.
CyclicBarriers is an aid “which allows a set of threads to wait for each other to reach a common barrier point” [13]. CyclicBarriers is useful when a fixed sized group of threads must occasionally wait for each other in a program. “The barrier is called cyclic because it can be re-used after the waiting threads are released” [13].
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” [13].
Concurrent Collections
As mentioned in the beginning of the Synchronizer section, a lock mechanism is implemented in “synchronized” classes before Java 5. In such cases, the “synchronized” method will lock the object that has been accessed by a thread. When the object is locked by one thread, other threads which need to access the same object must wait until the object is available. Note that only the resources in the object are protected by the lock. Other resources outside the object are not protected.
"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”[12].
Java realized this issue and therefore enhanced it by supplying some more collection implementations such as ConcurrentHashMap, CopyOnWriteArrayList, and CopyOnWriteArraySet. Only basic concepts will be introduced here due to the complexity of this component in the Java concurrency package. For more information, please refer to the J2SE 5.0 official web site for the java.util.concurrent package.
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” [14]. Other threads do not have to wait. This provides thread safety and also improves 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” [14] . This means no modification will be allowed when using CopyOnWriteArrayList. Therefore this operation is immutable and also guarantees thread-safety.
CopyOnWriteArraySet: This is a data structure used to protect the data during traversal for modification of an array. With CopyOnWriteArraySet, any changes in the data structure during traversal result in a copy being made for the modification. However, there is something more to keep in mind. This technique is used assuming that there will not be many changes being made. If many modifications need to be performed, the CopyOnWriteArraySet will create many copies, which could be bad.
Conclusion
The Java concurrency package provided in J2SE 5.0 and beyond is a powerful tool, but it does not prevent all concurrency dangers from becoming a reality.
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 [14].
Advantages
The benefits of using java.util.concurrent package for developers include: [14]
- Shorter and less messy application code
- Faster application implementation on schedule
- More scalable in data synchronization
- More readability and write ability for development and debugging
- Easier maintenance
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.
- ↑ 5.0 5.1 Creating a Thread.
- ↑ 6.0 6.1 Java theory and practice: Introduction to nonblocking algorithms.
- ↑ java.util.concurrent package.
- ↑ Gary Shute. Java Synchronization. Retrieved on 2010-08-12.
- ↑ J2SE API v1.4.2. Retrieved on 2010-08-12.
- ↑ 10.0 10.1 Neil Coffey. 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]
- ↑ 12.0 12.1 J2SE API v5.0. Retrieved on 2010-08-12.
- ↑ 13.0 13.1 13.2 13.3 13.4 public class: CountDownLatch. Retrieved on 2010-08-12.
- ↑ 14.0 14.1 14.2 14.3 Qusay H. Mahmoud. Concurrent Programming with J2SE 5.0. Retrieved on 2010-08-12.