Java concurrency package

From Citizendium
Revision as of 23:00, 13 August 2010 by imported>Michael T. Rakszawski (Fix grammar)
Jump to navigation Jump to search
All unapproved Citizendium articles may contain errors of fact, bias, grammar etc. A version of an article is unapproved unless it is marked as citable with a dedicated green template at the top of the page, as in this version of the 'Biology' article. Citable articles are intended to be of reasonably high quality. The participants in the Citizendium project make no representations about the reliability of Citizendium articles or, generally, their suitability for any purpose.

Nuvola apps kbounce green.png
Nuvola apps kbounce green.png
This article is currently being developed as part of an Eduzendium student project. The course homepage can be found at CZ:Special_Topics_2010.
To provide students with experience in collaboration, you are warmly invited to join in here, or to leave comments on the discussion page. The anticipated date of course completion is 13 August 2010. One month after that date at the latest, this notice shall be removed.
Besides, many other Citizendium articles welcome your collaboration!


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" [7]. 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 [8].

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”. [9]. When the synchronized keyword is used, the thread which invokes the synchronized method must obtain a lock for the object, which makes this thread the lock holder. The rule of thumb of 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” [10].

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” [11]. “Once a thread attempts to enter a synchronized block, it will hang until the lock is available.” [11] which causes low performance because all other threads that need the same object have to wait. Another issue is that missing appropriate notifications such as notify() or notifyAll() while programming can result in deadlock. [12]

Java 5: Synchronizers

In Java 5, the Java concurrency package provides four new classes including: semaphore, countdownlatch, cyclicbarrier, and exchanger, used for data synchronization [13].

Semaphore is a counting signal. It maintains a set of permits. The “parking garage” can be a good analogy as an example to explain it. We can 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” [14]. Something here that needs to be mentioned is that “CountDownLatch is a one-shot phenomenon” [14] meaning that the counter cannot be reused. If you need a counter that can be reset, consider using the CyclicBarrier method.

CyclicBarriers is an aid “which allows a set of threads to wait for each other to reach a common barrier point” [14]. CyclicBarriers is useful when a fixed sized group of 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” [14].

Exchanger is actually what the word looks like. “It is a synchronization point where two threads can exchange objects. Each thread presents some object on entry to the exchange method and receives the object presented by the other thread on return” [14].

Concurrent Collections

As 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”[13].

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” [15]. 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” [15]. 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 [15].

Advantages

The benefits of using java.util.concurrent package for developers include: [15]

  • 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. Java theory and practice: Introduction to nonblocking algorithms.
  7. Java theory and practice: Introduction to nonblocking algorithms.
  8. java.util.concurrent package.
  9. Gary Shute. Java Synchronization. Retrieved on 2010-08-12.
  10. J2SE API v1.4.2. Retrieved on 2010-08-12.
  11. 11.0 11.1 Unknown. Problems with Java 1.4 synchronization model. Retrieved on 2010-08-12.
  12. V.K., Garg (September 2005). "A Critique of Java for Concurrent Programming". IEEE Computer Society 6 (9). Retrieved on 2010-08-12. [e]
  13. 13.0 13.1 J2SE API v5.0. Retrieved on 2010-08-12.
  14. 14.0 14.1 14.2 14.3 14.4 public class: CountDownLatch. Retrieved on 2010-08-12.
  15. 15.0 15.1 15.2 15.3 Qusay H. Mahmoud. Concurrent Programming with J2SE 5.0. Retrieved on 2010-08-12. Cite error: Invalid <ref> tag; name "Concurrent Programming with J2SE 5.0" defined multiple times with different content Cite error: Invalid <ref> tag; name "Concurrent Programming with J2SE 5.0" defined multiple times with different content