Java concurrency package: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Prn Dan Mo
No edit summary
mNo edit summary
 
(67 intermediate revisions by 5 users not shown)
Line 1: Line 1:
{{CZ:Special Topics 2010/EZnotice}}
 
{{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==
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.
 
=== 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<ref name=Arnold />:
* 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.<ref name=Deitel>Java: How to Program, Sixth Edition, Deitel, Pearson © 2005</ref>  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''.<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.
 
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.<ref name="J2SE Code Names">{{cite web|url=http://java.sun.com/j2se/codenames.html|title=J2SE Code Names|accessdate=2010-08-13|}}</ref>  J2SE 5.0 introduced the java.util.concurrent package, which was designed for concurrency.<ref name=Arnold>The Java Programming Language, Fourth Edition, Arnold, Addison-Wesley © 2006 Sun Microsystems, Inc.</ref>  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() {
    }
}
<ref name="Create Thread">{{cite web|url=http://www.exampledepot.com/egs/java.lang/BasicThread.html|title=Creating a Thread|}}</ref>
 
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,
 
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;<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.
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 <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:
 
Long oneMinute = TimeUnit.SECONDS.toMillis(60); // 60 seconds in ms


===Synchronizers===
===Synchronizers===
====Mutilthread Synchronization before Java 5====
====Mutilthread Synchronization before Java 5====
Before Java 5, multithreads are supported using the lock mechanism for synchronization.   
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 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”.
<ref name="Java Synchronization">
<ref name="Java Synchronization">
{{cite web|
{{cite web|
Line 19: 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 most commonly used methods including, '''wait()''', '''notify()''', and '''notifyAll()''' are used for  
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 37: 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 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  
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 51: 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=Unknown| }}  
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"/>
{{cite web|
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">
url= http://www.javamex.com/tutorials/synchronization_concurrency_5.shtml|
title=Problems with Java 1.4 synchronization model|
accessdate=2010-08-12 |
author=Unknown| }}
</ref> 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. <ref name="A Critique of Java for Concurrent Programming">
{{cite journal
{{cite journal
   | last = V.K.
   | last = V.K.
Line 80: Line 184:


====Java 5: Synchronizers====
====Java 5: Synchronizers====
In Java 5, the Java concurrent package provides four new classes including: '''semaphore''',  
In Java 5, the Java concurrency package provides four new classes including: '''semaphore''',  
'''countdownlatch''', '''cyclickbarrier''', and '''exchanger''', used for data synchronization  
'''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 89: 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 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  
“''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 102: 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 108: 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 stating below.  
   
   
''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 thread is
</ref>.  CyclicBarriers is useful when a fixed sized group of threads must
occasionally but must wait for each other in a program.  “The barrier is called cyclic because  
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 126: 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 136: Line 230:


===Concurrent Collections===
===Concurrent Collections===
As it is mentioned in the beginning of synchronizer, the lock mechanism is implemented in  
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 and “synchronized” method will lock the object that’s 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.
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  
"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 150: 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.  Here only basic concepts  
will be introduced here due to the complexity of this component in the Java concurrency package.   
will be introduced here due to that this component is a very advanced one in java concurrent package.   
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 website [http://download.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/package-summary.html Package java.util.concurrenct].


''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 164: Line 252:
accessdate=2010-08-12 |
accessdate=2010-08-12 |
author=Qusay H. Mahmoud| }}  
author=Qusay H. Mahmoud| }}  
</ref>.  So other threads don’t have to wait.  This provides the thread safety and also improves balances of the
</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.
{{cite web|
url= http://java.sun.com/developer/technicalArticles/J2SE/concurrency/|
title=Concurrent Programming with J2SE 5.0|
accessdate=2010-08-12 |
author=Qusay H. Mahmoud| }}
</ref>.  This means no modification will be allowed when using CopyOnWriteArrayList. Therefore this  
operation is immutable and also guarantees thread-safety.


''CopyOnWriteArraySet:''
''CopyOnWriteArraySet:''
It’s a data structure to protect the data during traversal for modification of the Array.  
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 results in a copy  
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 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
==Conclusion==
modifications need to be performed, we are talking a lot of copies as well which could be bad.
 
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.  


===Conclusion===
===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 our 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"/>.
{{cite web|
 
url= http://java.sun.com/developer/technicalArticles/J2SE/concurrency/|
===Advantages===
title=Concurrent Programming with J2SE 5.0|
The benefits of using java.util.concurrent package for developers include:
accessdate=2010-08-12 |
<ref name="Concurrent Programming with J2SE 5.0"/>
author=Qusay H. Mahmoud| }}</ref>.
* 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==


====Advantages====
[[Multithreading]]
The benefits of using java.util.concurrent package for developers include
<ref name="Concurrent Programming with J2SE 5.0">
{{cite web|
url= http://java.sun.com/developer/technicalArticles/J2SE/concurrency/|
title=Concurrent Programming with J2SE 5.0|
accessdate=2010-08-12 |
author=Qusay H. Mahmoud| }}</ref>
:*[[Shorter and less messy application code]]
:*[[Faster application implementation on schedule]]
:*[[More scalable in data synchronization]]
:*[[More readability and writ ability for development and debugging]]
:*[[Easier maintenance]]


====Unsolved Issue====
[[Java_programming_language|Java (programming language)]]
Java concurrent package is not god.  The common concurrent programming issue remains
unresolved.  Java concurrent package still does not ensure there won’t be any deadlock
or CPU starvation in an application.  It is developers’ responsibilities to take appropriate
actions to handle the concurrency and data synchronization in their applications.


==Links==
==External Links==


[http://www.javaconcurrencyinpractice.com/ Java Concurrency in Practice]
[http://www.javaconcurrencyinpractice.com/ Java Concurrency in Practice]
Line 227: Line 300:


==References==
==References==
<references/>
<references/>[[Category:Suggestion Bot Tag]]

Latest revision as of 12:01, 4 September 2024

This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.


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() {
    } 
}

[5]

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; } }

[6]

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

Multithreading

Java (programming language)

External Links

Java Concurrency in Practice

Lesson: Concurrency

Java Technology

References

  1. A Concise Guide to Concurrent Programming. Retrieved on 2010-08-13.
  2. 2.0 2.1 The Java Programming Language, Fourth Edition, Arnold, Addison-Wesley © 2006 Sun Microsystems, Inc.
  3. 3.0 3.1 3.2 Java: How to Program, Sixth Edition, Deitel, Pearson © 2005
  4. J2SE Code Names. Retrieved on 2010-08-13.
  5. 5.0 5.1 Creating a Thread.
  6. 6.0 6.1 Java theory and practice: Introduction to nonblocking algorithms.
  7. java.util.concurrent package.
  8. Gary Shute. Java Synchronization. Retrieved on 2010-08-12.
  9. J2SE API v1.4.2. Retrieved on 2010-08-12.
  10. 10.0 10.1 Neil Coffey. Problems with Java 1.4 synchronization model. Retrieved on 2010-08-12.
  11. V.K., Garg (September 2005). "A Critique of Java for Concurrent Programming". IEEE Computer Society 6 (9). Retrieved on 2010-08-12. [e]
  12. 12.0 12.1 J2SE API v5.0. Retrieved on 2010-08-12.
  13. 13.0 13.1 13.2 13.3 13.4 public class: CountDownLatch. Retrieved on 2010-08-12.
  14. 14.0 14.1 14.2 14.3 Qusay H. Mahmoud. Concurrent Programming with J2SE 5.0. Retrieved on 2010-08-12.