Latches

http://ydtech.blogspot.com/2010/06/countdownlatch-by-example.html

A latch is a boolean condition that is set at most once, ever. Once a single release is issued, all acquires will pass.

Latch is switch or gate
In concurrent programming, a latch is a type of "switch" or "gate". The latch is set up with a particular count value. The count is then counted down, and at strategic moments, a thread or threads waits for the countdown to reach zero before continuing to perform some process. Note that this is a one-off process: once the latch reaches zero, there is no way to reset the count.

So threads can then either count down on the latch or wait for it to reach 0. When the latch reaches 0, all waiting threads are released.

The CountDownLatch class allows one to prevent a set of threads from running until you are ready for them to. For example, you might want to create the threads and then do some initialization tasks before starting them all simultaneously.

CountDownLatch’s constructor takes an integer as a parameter which decides its behavior. Calling await() holds execution till countdownLatch’s count(constructor parameter) become zero and countdown() reduces the count on every call. So calling await() blocks the thread until the count reaches zero.  

Example

package com.vaani.countdown;

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class CountDownLatchDemo {

    public static void main(String[] args) throws Exception {
        int nThreads = 3;
        final CountDownLatch startLatch = new CountDownLatch(nThreads);
        final CountDownLatch endLatch = new CountDownLatch(nThreads);

        ExecutorService svc = Executors.newFixedThreadPool(nThreads);
        for (int i = 0; i < nThreads; i++) {
            svc.execute(new Runnable() {
                public void run() {
                    try {
                        log("At run()");
                        startLatch.countDown();
                        startLatch.await();

                        log("Do work");
                        Thread.sleep((int) (Math.random() * 1000));

                        log("Wait for end");
                        endLatch.countDown();
                        endLatch.await();

                        log("Done");
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                }
            });
            Thread.sleep(100);
        }
    }

    private static void log(String msg) {
        System.out.println(System.currentTimeMillis() + ": "
                + Thread.currentThread().getId() + " " + msg);
    }
}

In this code, you’ll see two latches get initialized. Each thread that starts up counts down on the latch and awaits the latch counting down to 0 (when all threads have been initialized). Similarly, each thread waits for all threads to complete at the same time.

Sample output of this program is:

1308458964186: 8 At run()
1308458964286: 9 At run()
1308458964386: 10 At run()
1308458964386: 8 Do work
1308458964386: 10 Do work
1308458964387: 9 Do work
1308458964952: 8 Wait for end
1308458965037: 9 Wait for end
1308458965277: 10 Wait for end
1308458965277: 9 Done
1308458965277: 8 Done
1308458965277: 10 Done

You can see that each thread hits run() at different times, but proceeds past the barrier at the same time. They each then do some random amount of work and wait for the latch, then proceed past it together.

In the example above, each thread waits forever for the latch to trigger. You can also choose to wait for a specified time period before giving up. And you can check the latch to see how many threads have arrived and are now waiting. Each CountDownLatch instance can only be used once and is then dead.

Download the source

You can download the source code of the above program from here.

EasyMock for Unit Tests

What is mock object?
A mock object is a dummy interface or class in which you define the dummy output of a certain method call. These objects can be provided to the class which should be tested to avoid any dependency to external data. The classical example is a mock object for a data provider. In production a real database is used but for testing a mock object simulates the database and ensures that the test conditions are always the same.

What is easy mock?
This basic requirement of creating mock object can be accomplished by using Easy mock. Easy mock is a library that helps to dynamically create mock objects. This way we can avoid much of the tedious work involved in manually coding mock objects. However, EasyMock itself is not the silver bullet, we still have to define expectations in test cases. Using EasyMock also means that you have make certain design changes (if your design follows the usual design principles you may not have to change much. Here's a sample Unit Test using EasyMock. You can download easymock from here.
Class Under Test
DateFormatter.java

import java.text.DateFormat;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Date;

public class DateFormatter {
  public static final String DATE_FORMAT = "MM/dd/yyyy";

  private DateFormatterHelper helper = null;

  public DateFormatter() {
  }

  public String convertToStandardFormat(String dateString, String format)
                                        throws ParseException {
    if (dateString == null || dateString.equals(""))
      return "";
    dateString = dateString == null ? "" : dateString;
    DateFormat df = helper.getDateFormat(format);
    Date date = df.parse(dateString);
    SimpleDateFormat sdf = new SimpleDateFormat(DATE_FORMAT);
    return sdf.format(date);
  }

  public DateFormatterHelper getHelper() {
    return helper;
  }

  public void setHelper(DateFormatterHelper helper) {
    this.helper = helper;
  }
}

Testing the class

Helper Class and Interface: If you are to mock any class using EasyMock, it is required that you have an interface for the class. If you are following the old design principle "program to an interface, not an implementation", you are good here.

package sample;

import java.text.DateFormat;

public interface DateFormatterHelper {
  public DateFormat getDateFormat(String format);
}

DateFormatterHelperImpl.java

public class DateFormatterHelperImpl 
                       implements DateFormatterHelper {

  public DateFormatterHelperImpl() {
  }

  public DateFormat getDateFormat(String format) {
    SimpleDateFormat sdf = new SimpleDateFormat(format);
    sdf.setCalendar(Calendar.getInstance());
    sdf.setLenient(false);
    return sdf;
  }
  

  public static void main(String args[]) {
    DateFormatterHelper helper = new DateFormatterHelperImpl();
    try {
          System.out.println(helper.
                getDateFormat("MM/dd/yyyy").parse("11/27/2008"));
        } catch (ParseException e) {
          // TODO Auto-generated catch block
          e.printStackTrace();
        }
    
  }

}

DateFormatterTests.java

import static org.junit.Assert.fail;

import java.text.ParseException;
import java.text.SimpleDateFormat;

import org.easymock.EasyMock;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

import sample.DateFormatter;
import sample.DateFormatterHelper;

public class DateFormatterTests {

  private DateFormatter formatter = null;

  DateFormatterHelper helper = null;

  @Before
  public void setUp() throws Exception {
    helper = EasyMock.createMock(DateFormatterHelper.class);
    formatter = new DateFormatter();
    formatter.setHelper(helper);
  }

  @Test
  public void testConvertToStandardFormat() {
    
    String formatted = null;
    try {
      EasyMock.expect(helper.getDateFormat("MM-dd-yyyy"))
            .andReturn(new SimpleDateFormat("MM-dd-yyyy"));
      EasyMock.replay(helper);
      formatted = formatter.
               convertToStandardFormat("11-27-2008", "MM-dd-yyyy");
    } catch (ParseException e) {
      e.printStackTrace();
      fail("Exception");
    }
    Assert.assertEquals(formatted, "11/27/2008");

  }
}

Note that in the EasyMock.expect method line, we use the "andReturn" method. This is to define the expected behavior when the method under test is invoked by the testcase. As can be expected, the replay method simply replays the pre-defined behavior when the actual call is made on the mock object.

Download the source
You can download the source code from here.

JUnit - Tutorial

Unit testing with JUnit 
A unit test is a piece of code written by a developer that tests a specific functionality in the code which is tested. Unit tests can ensure that functionality is working and can be used to validate that this functionality still works after code changes.

Setup JUnit in eclipse
Here we will see how to setup the test classes in eclipse:

1. Create a new project, name it whatever you want, say JUnitDemo.
   
2. It would be good to create the unit tests in a separate folder as a good practise. Create therefore a new source folder "test" via right mouse click on your project, select properties and choose the "Java Build Path". Select the tab source code. Press "Add folder" then then press "Create new folder". Create the folder "test".
   
3. Create the class to be tested - Add it to the normal source folder.
   public class Calc { public long add(int a, int b) { return a+b; } }
4. Tester class - Right click on test folder, and either make a new JUnit test case or a simple class and add @Test annotation on the methods of this class.
   import org.junit.Test; import static org.junit.Assert.assertEquals; public class CalcTest { @Test public void testAdd() { assertEquals(5, new Calc().add(2, 3)); } }
5. Now run the test class like this:
   
6. Now in the end you will see the following result as green if test was successful and red otherwise.
   

Creating the testee and tester class

1. The tests: Unlike in JUnit 3.x you don't have to extend TestCase to implement tests. A simple Java class can be used as a TestCase. The test methods have to be simply annotated with org.junit.Test annotation as shown below
   

   @Test
   public void emptyTest() {
    stack = new Stack<String>();
    assertTrue(stack.isEmpty());
   }
   

2. Using Assert Methods: In JUnit 4 test classes do not inherit from TestCase, as a result, the Assert methods are not available to the test classes. In order to use the Assert methods, you have to use either the prefixed syntax (Assert.assertEquals()) or, use a static import for the Assert class.
   

   import static org.junit.Assert.*;
   

   Now the assert methods may be used directly as done with the previous versions of JUnit.
3. Changes in Assert Methods: The new assertEquals methods use Autoboxing, and hence all the assertEquals(primitive, primitive) methods will be tested as assertEquals(Object, Object). This may lead to some interesting results. For example autoboxing will convert all numbers to the Integer class, so an Integer(10) may not be equal to Long(10). This has to be considered when writing tests for arithmetic methods. For example, the following Calc class and it's corresponding test CalcTest will give you an error.
   Calc.java
   

   public class Calc {
    public long add(int a, int b) {
     return a+b;
    }
   }
   

   
   CalcTest.java
   

   import org.junit.Test;
   import static org.junit.Assert.assertEquals;
   
   public class CalcTest {
    @Test
    public void testAdd() {
     assertEquals(5, new Calc().add(2, 3));
    }
   }
   

   
   You will end up with the following error.

   java.lang.AssertionError: expected:<5> but was:<5>

   
   This is due to autoboxing. By default all the integers are cast to Integer, but we were expecting long here. Hence the error. In order to overcome this problem, it is better if you type cast the first parameter in the assertEquals to the appropriate return type for the tested method as follows:
   

   assertEquals((long)5, new Calc().add(2, 3));
   

   
   There are also a couple of methods for comparing Arrays:
   

   public static void assertEquals(String message, Object[] expecteds, Object[] actuals);
   public static void assertEquals(Object[] expecteds, Object[] actuals);
   

4. Setup and TearDown: You need not have to create setup and teardown methods for setup and teardown. The @Before, @After and @BeforeClass, @AfterClass annotations are used for implementing setup and teardown operations. The @Before and @BeforeClass methods are run before running the tests. The @After and @AfterClass methods are run after the tests are run. The only difference being that the @Before and @After can be used for multiple methods in a class, but the @BeforeClass and @AfterClass can be used only once per class.
5. Parameterized Tests: JUnit 4 comes with another special runner: Parameterized, which allows you to run the same test with different data. For example, in the the following peice of code will imply that the tests will run four times, with the parameter "number" changed each time to the value in the array.
   

   @RunWith(value = Parameterized.class)
   public class StackTest {
    Stack<Integer> stack;
    private int number;
   
    public StackTest(int number) {
      this.number = number;
    }
   
    @Parameters
    public static Collection data() {
      Object[][] data = new Object[][] { { 1 }, { 2 }, { 3 }, { 4 } };
      return Arrays.asList(data);
    }
    ...
   }
   

   
   The requirement for parameterized tests is to
   • Have the annotation @RunWith for the Test Class
   • Have a public static method that returns a Collection for data. Each element of the collection must be an Array of the various paramters used for the test.
   • You will also need a public constructor that uses the parameters
6. Test Suites: In JUnit 3.8 you had to add a suite() method to your classes, to run all tests as a suite. With JUnit 4 you use annotations instead. To run the CalculatorTest and SquareTest you write an empty class with @RunWith and @Suite annotations.
   

   import org.junit.runner.RunWith;
   import org.junit.runners.Suite;
   @RunWith(Suite.class)
   @Suite.SuiteClasses({StackTest.class})
   public class AllTests {
   }
   

   
   The "Suite" class takes SuiteClasses as argument which is a list of all the classes that can be run in the suite. The following is a listing of the example StackTest used in the post:
   

Static imports with Eclipse

JUnit uses a lot of static methods and old Eclipse cannot automatically import static imports, but new one can. You can make the JUnit test methods available via the content assists.
Open the Preferences via Window -> Preferences and select Java > Editor > Content Assist > Favorites. Add then via "New Member" the methods you need. For example this makes the assertTrue, assertFalse and assertEquals method available.

You can now use Content Assist (Ctrl+Space) to add the method and the import.
I suggest to add at least the following new members.

• org.junit.Assert.assertTrue
• org.junit.Assert.assertFalse
• org.junit.Assert.assertEquals
• org.junit.Assert.fail

Annotations

The following give an overview of the available annotations in JUnit 4.x

Annotations

Annotation	Description
@Test public void method()	Annotation @Test identifies that this method is a test method.
@Before public void method()	Will perform the method() before each test. This method can prepare the test environment, e.g. read input data, initialize the class)
@After public void method()	Test method must start with test
@BeforeClass public void method()	Will perform the method before the start of all tests. This can be used to perform time intensive activities for example be used to connect to a database
@AfterClass public void method()	Will perform the method after all tests have finished. This can be used to perform clean-up activities for example be used to disconnect to a database
@Ignore	Will ignore the test method, e.g. useful if the underlying code has been changed and the test has not yet been adapted or if the runtime of this test is just to long to be included.
@Test(expected=IllegalArgumentException.class)	Tests if the method throws the named exception
@Test(timeout=100)	Fails if the method takes longer then 100 milliseconds

Assert statements

The following gives an overview of the available test methods:

Test methods

Statement	Description
fail(String)	Let the method fail, might be usable to check that a certain part of the code is not reached.
assertTrue(true);	True
assertsEquals([String message], expected, actual)	Test if the values are the same. Note: for arrays the reference is checked not the content of the arrays
assertsEquals([String message], expected, actual, tolerance)	Usage for float and double; the tolerance are the number of decimals which must be the same
assertNull([message], object)	Checks if the object is null
assertNotNull([message], object)	Check if the object is not null
assertSame([String], expected, actual)	Check if both variables refer to the same object
assertNotSame([String], expected, actual)	Check that both variables refer not to the same object
assertTrue([message], boolean condition)	Check if the boolean condition is true.

Download the source
The source code can be downloaded from here.

Synchronizing Threads : The producer consumer problem

The Producer generates an integer between 0 and 9 (inclusive), stores it in a CubbyHole object, and prints the generated number. To make the synchronization problem more interesting, the Producer sleeps for a random amount of time between 0 and 100 milliseconds before repeating the number generating cycle. Lets see what producer produces:

CubbyHole.java – Consumer product

public class CubbyHole {
    private int contents;
    private boolean available = false;
    //get and set methods are sync to put locks
    // on resource 
    public synchronized int get() {
        while (available == false) {
            try {
                wait();
            } catch (InterruptedException e) { }
        }
        available = false;
        notifyAll();
        return contents;
    }

    public synchronized void put(int value) {
        while (available == true) {
            try {
                wait();
            } catch (InterruptedException e) { }
        }
        contents = value;
        available = true;
        notifyAll();
    }
}

Producer.java

public class Producer extends Thread {
    private CubbyHole cubbyhole;
    private int number;
    public Producer(CubbyHole c, int number) {
        cubbyhole = c;
        this.number = number;
    }
    public void run() {
        for (int i = 0; i < 10; i++) {
            cubbyhole.put(i);
            System.out.println("Producer #" 
                       + this.number + " put: " + i);
            try {
                sleep((int)(Math.random() * 100));
            }
             catch (InterruptedException e) {
                // do something
             }
        }
    }
}

Consumer.java
The Consumer, being ravenous, consumes all integers from the CubbyHole (the exact same object into which the Producer put the integers in the first place) as quickly as they become available.

public class Consumer extends Thread {
    private CubbyHole cubbyhole;
    private int number;
    public Consumer(CubbyHole c, int number) {
        cubbyhole = c;
        this.number = number;
    }
    public void run() {
        int value = 0;
        for (int i = 0; i < 10; i++) {
            value = cubbyhole.get();
            System.out.println("Consumer #" + 
                 this.number + " got: " + value);
        }
    }
}

The Producer and Consumer in this example share data through a common CubbyHole object. And you will note that neither the Producer nor the Consumer makes any effort whatsoever to ensure that the Consumer is getting each value produced once and only once. The synchronization between these two threads actually occurs at a lower level, within the get and put methods of the CubbyHole object. However, let's assume for a moment that these two threads make no arrangements for synchronization and talk about the potential problems that might arise in that situation. One problem arises when the Producer is quicker than the Consumer and generates two numbers before the Consumer has a chance to consume the first one. Thus the Consumer would skip a number. Part of the output might look like this:

. . .

Consumer #1 got: 3
Producer #1 put: 4
Producer #1 put: 5
Consumer #1 got: 5

    . . .

Another problem that might arise is when the Consumer is quicker than the Producer and consumes the same value twice. In this situation, the Consumer would print the same value twice and might produce output that looked like this:

. . .

Producer #1 put: 4
Consumer #1 got: 4
Consumer #1 got: 4
Producer #1 put: 5

    . . .

Either way, the result is wrong. You want the Consumer to get each integer produced by the Producer exactly once. Problems such as those just described are called race conditions. They arise from multiple, asynchronously executing threads trying to access a single object at the same time and getting the wrong result. Race conditions in the producer/consumer example are prevented by having the storage of a new integer into the CubbyHole by the Producer be synchronized with the retrieval of an integer from the CubbyHole by the Consumer. The Consumer must consume each integer exactly once.
The activities of the Producer and Consumer must be synchronized in two ways. First, the two threads must not simultaneously access the CubbyHole. A Java thread can prevent this from happening by locking an object. When an object is locked by one thread and another thread tries to call a synchronized method on the same object, the second thread will block until the object is unlocked. Locking an Object discusses this.
And second, the two threads must do some simple coordination. That is, the Producer must have some way to indicate to the Consumer that the value is ready and the Consumer must have some way to indicate that the value has been retrieved. The Thread class provides a collection of methods--wait, notify, and notifyAll--to help threads wait for a condition and notify other threads of when that condition changes. Using the notifyAll and wait Methods has more information.

The Main Program

Here's a small stand-alone Java application that creates a CubbyHole object, a Producer, a Consumer, and then starts both the Producer and the Consumer.

public class ProducerConsumerTest {
    public static void main(String[] args) {
        CubbyHole c = new CubbyHole();
        Producer p1 = new Producer(c, 1);
        Consumer c1 = new Consumer(c, 1);
        p1.start();
        c1.start();
    }
}

The Output

Here's the output of ProducerConsumerTest.

Producer #1 put: 0
Consumer #1 got: 0
Producer #1 put: 1
Consumer #1 got: 1
Producer #1 put: 2
Consumer #1 got: 2
Producer #1 put: 3
Consumer #1 got: 3
Producer #1 put: 4
Consumer #1 got: 4
Producer #1 put: 5
Consumer #1 got: 5
Producer #1 put: 6
Consumer #1 got: 6
Producer #1 put: 7
Consumer #1 got: 7
Producer #1 put: 8
Consumer #1 got: 8
Producer #1 put: 9
Consumer #1 got: 9

 

Download the source-code

Please download the source code from here.

Understanding Thread Priority

Previously, this lesson claimed that threads run concurrently. While conceptually this is true, in practice it usually isn't. Most computer configurations have a single CPU, so threads actually run one at a time in such a way as to provide an illusion of concurrency. Execution of multiple threads on a single CPU, in some order, is called scheduling. The Java runtime supports a very simple, deterministic scheduling algorithm known as fixed priority scheduling. This algorithm schedules threads based on their priority relative to other runnable threads.
When a Java thread is created, it inherits its priority from the thread that created it. You can also modify a thread's priority at any time after its creation using the setPriority method. Thread priorities are integers ranging between MIN_PRIORITY and MAX_PRIORITY (constants defined in the Thread class). The higher the integer, the higher the priority. At any given time, when multiple threads are ready to be executed, the runtime system chooses the runnable thread with the highest priority for execution. Only when that thread stops, yields, or becomes not runnable for some reason will a lower priority thread start executing. If two threads of the same priority are waiting for the CPU, the scheduler chooses one of them to run in a round-robin fashion. The chosen thread will run until one of the following conditions is true:

• A higher priority thread becomes runnable.
• It yields, or its run method exits.
• On systems that support time-slicing, its time allotment has expired.

Then the second thread is given a chance to run, and so on, until the interpreter exits. The Java runtime system's thread scheduling algorithm is also preemptive. If at any time a thread with a higher priority than all other runnable threads becomes runnable, the runtime system chooses the new higher priority thread for execution. The new higher priority thread is said to preempt the other threads.

---

Rule of thumb: At any given time, the highest priority thread is running. However, this is not guaranteed. The thread scheduler may choose to run a lower priority thread to avoid starvation. For this reason, use priority only to affect scheduling policy for efficiency purposes. Do not rely on thread priority for algorithm correctness.

---

The 400,000 Micron Thread Race

This Java source code implements an applet that animates a race between two "runner" threads with different priorities. When you click the mouse down over the applet, it starts the two runners. The top runner, labelled "2", has a priority of 2. The second runner, labelled "3", has a priority of 3. Try this: Click the applet below to start the race.
This is the run method for both runners.

public int tick = 1;
public void run() {
    while (tick < 400000)
        tick++;
}

This run method simply counts from 1 to 400,000. The instance variable tick is public because the applet uses this value to determine how far the runner has progressed (how long its line is). In addition to the two runner threads, this applet also has a third thread that handles the drawing. The drawing thread's run method contains an infinite loop; during each iteration of the loop it draws a line for each runner (whose length is computed from the runner's tick variable), and then sleeps for 10 milliseconds. The drawing thread has a thread priority of 4--higher than either runner. So, whenever the drawing thread wakes up after 10 milliseconds, it becomes the highest priority thread, preempting whichever runner is currently running, and draws the lines. You can see the lines inch their way across the page
This is not a fair race because one runner has a higher priority than the other. Each time the drawing thread yields the CPU by going to sleep for 10 milliseconds, the scheduler chooses the highest priority runnable thread to run; in this case, it's always runner 3. Here is another version of the applet that implements a fair race, that is, both of the runners have the same priority and they have an equal chance of being chosen to run.
Try this: Click the mouse to start the race.

In this race, each time the drawing thread yields the CPU by going to sleep, there are two runnable threads of equal priority--the runners--waiting for the CPU; the scheduler must choose one of the threads to run. In this situation, the scheduler chooses the next thread to run in a round-robin fashion.

Selfish Threads

The Runner class used in the races above actually implements "socially-impaired" thread behavior. Recall the run method from the Runner class used in the races above:

public int tick = 1;
public void run() {
    while (tick < 400000)
        tick++;
}

The while loop in the run method is in a tight loop. Once the scheduler chooses a thread with this thread body for execution, the thread never voluntarily relinquishes control of the CPU--the thread continues to run until the while loop terminates naturally or until the thread is preempted by a higher priority thread. This thread is called a selfish thread. In some situations, having selfish threads doesn't cause any problems because a higher priority thread preempts the selfish one (just as the drawing thread in the RaceApplet preempts the selfish runners). However, in other situations, threads with CPU-greedy run methods, such as the Runner class, can take over the CPU and cause other threads to wait for a long time before getting a chance to run.

Time-Slicing

Some systems, such as Windows 95/NT, fight selfish thread behavior with a strategy known as time-slicing. Time-slicing comes into play when there are multiple "Runnable" threads of equal priority and those threads are the highest priority threads competing for the CPU. For example, this stand-alone Java program (which is based on the RaceApplet above) creates two equal priority selfish threads that have the following run method.

public void run() {
    while (tick < 400000) {
        tick++;
        if ((tick % 50000) == 0)
            System.out.println("Thread #" + num + ", 
                                     tick = " + tick);
    }
}    

This run contains a tight loop that increments the integer tick and every 50,000 ticks prints out the thread's identifier and its tick count. When running this program on a time-sliced system, you will see messages from both threads intermingled with one another. Like this:

Thread #1, tick = 50000
Thread #0, tick = 50000
Thread #0, tick = 100000
Thread #1, tick = 100000
Thread #1, tick = 150000
Thread #1, tick = 200000
Thread #0, tick = 150000
Thread #0, tick = 200000
Thread #1, tick = 250000
Thread #0, tick = 250000
Thread #0, tick = 300000
Thread #1, tick = 300000
Thread #1, tick = 350000
Thread #0, tick = 350000
Thread #0, tick = 400000
Thread #1, tick = 400000

This output is produced because a time-sliced system divides the CPU into time slots and iteratively gives each of the equal-and-highest priority threads a time slot in which to run. The time-sliced system iterates through the equal-and-highest priority threads, allowing each one a bit of time to run, until one or more of them finishes or until a higher priority thread preempts them. Notice that time-slicing makes no guarantees as to how often or in what order threads are scheduled to run. When running this program on a non-time-sliced system, however, you will see messages from one thread finish printing before the other thread ever gets a chance to print one message. Like this:

Thread #0, tick = 50000
Thread #0, tick = 100000
Thread #0, tick = 150000
Thread #0, tick = 200000
Thread #0, tick = 250000
Thread #0, tick = 300000
Thread #0, tick = 350000
Thread #0, tick = 400000
Thread #1, tick = 50000
Thread #1, tick = 100000
Thread #1, tick = 150000
Thread #1, tick = 200000
Thread #1, tick = 250000
Thread #1, tick = 300000
Thread #1, tick = 350000
Thread #1, tick = 400000

This is because a non-time-sliced system chooses one of the equal-and-highest priority threads to run and allows that thread to run until it relinquishes the CPU (by sleeping, yielding, finishing its job) or until a higher priority preempts it.

---

Note: The Java runtime does not implement (and therefore does not guarantee) time-slicing. However, some systems on which you can run Java do support time-slicing. Your Java programs should not rely on time-slicing as it may produce different results on different systems.

---

Try this: Compile and run the RaceTest and SelfishRunner classes on your computer. Can you tell if you have a time-sliced system?
As you can imagine, writing CPU-intensive code can have negative repercussions on other threads running in the same process. In general, you should try to write "well-behaved" threads that voluntarily relinquish the CPU periodically and give other threads an opportunity to run. In particular, you should never write Java code that relies on time-sharing--this will practically guarantee that your program will give different results on different computer systems.
A thread can voluntarily yield the CPU without going to sleep or some other drastic means by calling the yield method. The yield method gives other threads of the same priority a chance to run. If there are no equal priority threads that are runnable, then the yield is ignored.
Try this: Rewrite the SelfishRunner class to be a PoliteRunner by calling the yield method from the run method. Be sure to modify the main program to create PoliteRunners instead of SelfishRunners. Compile and run the new classes on your computer. Now isn't that better?

Summary

• Most computers have only one CPU, so threads must share the CPU with other threads. The execution of multiple threads on a single CPU, in some order, is called scheduling. The Java runtime supports a very simple, deterministic scheduling algorithm known as fixed priority scheduling.
  
• Each Java thread is given a numeric priority between MIN_PRIORITY and MAX_PRIORITY (constants defined in the Thread class). At any given time, when multiple threads are ready to be executed, the thread with the highest priority is chosen for execution. Only when that thread stops, or is suspended for some reason, will a lower priority thread start executing.
  
• Scheduling of the CPU is fully preemptive. If a thread with a higher priority than the currently executing thread needs to execute, the higher priority thread is immediately scheduled.
  
• The Java runtime will not preempt the currently running thread for another thread of the same priority. In other words, the Java runtime does not time-slice. However, the system implementation of threads underlying the Java Thread class may support time-slicing. Do not write code that relies on time-slicing.
  
• In addition, a given thread may, at any time, give up its right to execute by calling the yield method. Threads can only yield the CPU to other threads of the same priority--attempts to yield to a lower priority thread are ignored.
  
• When all the runnable threads in the system have the same priority, the scheduler chooses the next thread to run in a simple, non-preemptive, round-robin scheduling order.

Download

Download the full source code here.

Implementing the Runnable Interface

The Clock applet shown below displays the current time and updates its display every second. You can scroll this page and perform other tasks while the clock continues to update because the code that updates the clock's display runs within its own thread.
The Clock applet uses a different technique than SimpleThread for providing the run method for its thread. Instead of subclassing Thread, Clock implements the Runnable interface (and therefore implements the run method defined in it). Clock then creates a thread with itself as the Thread's target. When created in this way, the Thread gets its run method from its target. The code that accomplishes this is shown in bold here:

import java.awt.Graphics;
import java.util.*;
import java.text.DateFormat;
import java.applet.Applet;

public class Clock extends Applet implements Runnable {
    private Thread clockThread = null;
    public void start() {
        if (clockThread == null) {
            clockThread = new Thread(this, "Clock");
            clockThread.start();
        }
    }
    public void run() {
        Thread myThread = Thread.currentThread();
        while (clockThread == myThread) {
            repaint();
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e){
            // the VM doesn't want us to sleep anymore,
            // so get back to work
            }
        }
    }
    public void paint(Graphics g) {
        // get the time and convert it to a date
        Calendar cal = Calendar.getInstance();
        Date date = cal.getTime();
        // format it and display it
        DateFormat dateFormatter = DateFormat.getTimeInstance();
        g.drawString(dateFormatter.format(date), 5, 10);
    }
    // overrides Applet's stop method, not Thread's
    public void stop() {
        clockThread = null;
    }
}

The Clock applet's run method loops until the browser asks it to stop. During each iteration of the loop, the clock repaints its display. The paint method figures out what time it is, formats it in a localized way, and displays it. You'll see more of the Clock applet in The Life Cycle of a Thread which uses it to teach you about the life of a thread.

Deciding to Use the Runnable Interface

You have now seen two ways to provide the run method for a Java thread:

1. Subclass the Thread class defined in the java.lang package and override the run method.
   
   

   ---

   
   Example: See the SimpleThread class described in Subclassing Thread and Overriding run.
   

   ---

   
   
   
2. Provide a class that implements the Runnable interface (also defined in the java.lang package) and therefore implements the run method. In this case, a Runnable object provides the run method to the thread.
   
   

   ---

   
   Example: See the Clock applet just shown.
   

   ---

   
   

There are good reasons for choosing either of these options over the other. However, for most cases, including that of the Clock applet, the following rule of thumb will guide you to the best option.

---

Rule of Thumb: If your class must subclass some other class (the most common example being Applet), you should use Runnable as described in option #2.

---

To run in a Java-enabled browser, the Clock class has to be a subclass of the Applet class. Also, the Clock applet needs a thread so that it can continuously update its display without taking over the process in which it is running. (Some browsers might create a new thread for each applet so as to prevent a misbehaved applet from taking over the main browser thread. However, you should not count on this when writing your applets; your applets should create their own threads when doing computer-intensive work.) But since the Java language does not support multiple class inheritance, the Clock class cannot be a subclass of both Thread and Applet. Thus the Clock class must use the Runnable interface to provide its threaded behavior.

Download

Download the source code from here. Also see Clock applet here (soon to be added).

Subclassing Thread and Overriding run

The first way to customize what a thread does when it is running is to subclass Thread (itself a Runnable object) and override its empty run method so that it does something. Let's look at the SimpleThread class, the first of two classes in this example, which does just that:
SimpleThread.java

public class SimpleThread extends Thread {
    public SimpleThread(String str) {
        super(str);
    }
    public void run() {
        for (int i = 0; i < 10; i++) {
            System.out.println(i + " " + getName());
            try {
                sleep((int)(Math.random() * 1000));
            } catch (InterruptedException e) {
                //don't swallow
              }
        }
        System.out.println("DONE! " + getName());
    }
}

The first method in the SimpleThread class is a constructor that takes a String as its only argument. This constructor is implemented by calling a superclass constructor and is interesting to us only because it sets the Thread's name, which is used later in the program. The next method in the SimpleThread class is the run method. The run method is the heart of any Thread and where the action of the Thread takes place. The run method of the SimpleThread class contains a for loop that iterates ten times. In each iteration the method displays the iteration number and the name of the Thread, then sleeps for a random interval of up to 1 second. After the loop has finished, the run method prints DONE! along with the name of the thread. That's it for the SimpleThread class.
The TwoThreadsTest class provides a main method that creates two SimpleThread threads: one is named "Jamaica" and the other is named "Fiji". (If you can't decide on where to go for vacation you can use this program to help you decide--go to the island whose thread prints "DONE!" first.)
TwoThreads.java

public class TwoThreadsTest {
    public static void main (String[] args) {
        new SimpleThread("Jamaica").start();
        new SimpleThread("Fiji").start();
    }
}

The main method also starts each thread immediately following its construction by calling the start method. To save you from typing in this program, click here for the source code to the SimpleThread class and here for the source code to the TwoThreadsTest program. Compile and run the program and watch your vacation fate unfold. You should see output similar to the following:

0 Jamaica
0 Fiji
1 Fiji
1 Jamaica
2 Jamaica
2 Fiji
3 Fiji
3 Jamaica
4 Jamaica
4 Fiji
5 Jamaica
5 Fiji
6 Fiji
6 Jamaica
7 Jamaica
7 Fiji
8 Fiji
9 Fiji
8 Jamaica
DONE! Fiji
9 Jamaica
DONE! Jamaica

(Looks like I'm going to Fiji!!) Notice how the output from each thread is intermingled with the output from the other. This is because both SimpleThread threads are running concurrently. Thus, both run methods are running at the same time and each thread is displaying its output at the same time as the other.

---

Try This: Change the main program so that it creates a third thread with the name "Bora Bora". Compile and run the program again. Does this change the island of choice for your vacation? Here's the code for the new main program, which is now named ThreeThreadsTest.

public class ThreeThreadsTest {
    public static void main (String[] args) {
        new SimpleThread("Jamaica").start();
        new SimpleThread("Fiji").start();
        new SimpleThread("Bora Bora").start();
    }
}

Output:

0 Jamaica
0 Fiji
1 Jamaica
1 Fiji
2 Jamaica
2 Fiji
3 Fiji
3 Jamaica
4 Fiji
4 Jamaica
5 Jamaica
6 Jamaica
5 Fiji
7 Jamaica
6 Fiji
8 Jamaica
9 Jamaica
7 Fiji
8 Fiji
9 Fiji
DONE! Fiji
DONE! Jamaica

 

---

Now, let's look at another example, the Clock applet, that uses the other technique for providing a run method to a Thread.  See – Implementing the runnable interface.

Download the source code

You can download the source code from here.

ArrayDeque

ArrayDeque is an implementation of the 'Deque' interface i.e. java.util.ArrayDeque implements a double-ended queue, which allows efficient insertion and deletion at both ends. This an excellent choice for stacks and queues.
Double Ended Queue's extend 'Queue' and support adding and removing elements from both ends. In a Queue, you can add from one end and remove from the other. Also, Deque's can be used as a Queue and also a 'Stack'. ArrayDeque has no capacity restrictions like some other data structures (although you can specify that in one of its constructors). ArrayDeque is not threadsafe, as other collections like HashMap, et al. If you want it thread-safe, use 'LinkedBlockingQueue', which implements the 'BlockingQueue' interface, which further extends from 'Deque' interface.
An ArrayDeque has these characteristics:

• Stack or queue. Supports operations to efficiently add, examine, or remove elements from either end.
• Automatically expands as data is added to either the front or back. No capacity limit.
• Good performance
  • Adding, examining, or deleting and element at either end of an ArrayDeque is O(1).
  • Generally faster than Stack.
  • Generally faster than LinkedList for queue operations.
• Iteration - ArrayDeque implements Iterable, so can be traversed using a foreach loop or iterator. It also provides a descendingIterator() method for iterating in reverse order. So, a 'Deque' can be traversed from both directions programmatically using 'iterator' and 'descendingIterator' methods.
• As with the other collections classes, only Object types are supported.
• No indexed access is permitted.
• No sorting is possible -- deques are not lists.

Deque vs LinkedList
 Deque is doubly linked and can be compared to 'LinkedList', which also implements a 'Deque', apart from List. In LinkedList, you can access an element randomly, by the element's index, which you cant do in Deque's. It was designed this way to make it more efficient.

Terminology

What are the ends called? The terminology of stacks and queues and lists is not standardized, so you'll see various terms for the ends.

• Front = head = start = first.
• Back = tail = end = last.

Common ArrayDeque methods and constructors

Here are some of the most useful ArrayDeque methods. Assume these declarations. Note that E is the notation for the type of an element in a collection.

int i;
boolean b;
ArrayDeque a;
E e;
Iterator iter;
E[] earray;
Object[] oarray;

Result	Method	Description
Constructors
a =	new ArrayDeque()	Creates ArrayDeque with initial default capacity.
a =	new ArrayDeque(cap)	Creates ArrayDeque with initial int capacity cap.
a =	new ArrayDeque(coll)	Creates ArrayDeque from the Collection coll.
Operations on the front (head, start, first)
	a.addFront(e)	adds e to the front of ArrayDeque a
b =	a.offerFirst(e)	Same as addFront. With capacity limited deques (not ArrayDeque) can return false.
e =	a.getFirst()	Returns, but does not remove, first element. Throws exception if deque is empty.
e =	a.element()	Same as getFirst.
e =	a.peekFirst()	Same as getFirst, but returns null if deque is empty.
e =	a.peek()	Same as peekFirst.
e =	a.removeFirst()	Returns and removes first element. Throws exception if deque is empty.
e =	a.remove()	Same as pollFirst.
e =	a.pollFirst()	Returns and removes first element. Returns null if deque is empty.
e =	a.poll()	Same as pollFirst.
e =	a.pop()	Same as removeFirst.
e =	a.push(e)	Same as addFront.
Operations on the back (tail, end, last)
	a.addLast(e)	adds e to the end of ArrayDeque a
	a.add(e)	Same as addLast.
b =	a.offerLast(e)	Same as addLast. With capacity limited deques (not ArrayDeque) can return false.
b =	a.offer(e)	Same as offerLast.
e =	a.getLast()	Returns, but does not remove, last element. Throws exception if deque is empty.
e =	a.peekLast()	Same as getLast, but returns null if deque is empty.
e =	a.removeLast()	Returns and removes last element. Throws exception if deque is empty.
e =	a.pollLast()	Returns and removes last element. Returns null if deque is empty.
Turning into an array
oarray =	a.toArray()	Returns values in array of objects.
earray =	a.toArray(E[])	The array parameter should be of the E class. Returns values in that array (or a larger array is allocated if necessary).
Iterators
iter =	a.iterator()	Returns an Iterator for forward traversal.
iter =	a.descendingIterator()	Returns an Iterator for backward traversal.
Searching
b =	a.contains(e)	Returns true if ArrayDeque a contains e
b =	a.removeFirstOccurrence(e)	Removes e from deque starting at beginning. Returns true if successful.
b =	a.removeLastOccurrence(e)	Removes e from deque starting at end. Returns true if successful.
b =	a.remove(e)	Same as removeFirstOccurrence().
Removing elements
Other
i =	a.size()	Returns the number of elements in ArrayDeque a.
	a.clear()	removes all elements from ArrayDeque a

To get successive elements from an ArrayDeque - Several ways

Use either the foreach loop or an Iterator.

1. foreach loop. This is fast and works for all kinds of lists, but is not entirely flexible (only sequential forward with no deletions, additions, or multiple references). This should be your first choice in programming. Works efficiently with both ArrayDeque and LinkedList.

   ArrayDeque a = new ArrayDeque();
   . . .
   for (String s : a) {
   System.out.println(s);
   }

2. Iterator - Allows simple forward traversal. Can be used for the largest number of other kinds of data structures. This example uses an Iterator to print all elements (Strings) in an ArrayDeque. It uses hasNext(), which returns true if there are more elements, and next(), which returns the next element. Works with both ArrayDeque and LinkedList.
   

   for (Iterator iter = a.iterator(); iter.hasNext();  ) {
   System.out.println(iter.next());
   }

3. ListIterator - Allows traversal of the ArrayDeque, but it is more general than a simple Iterator, allowing inserts and deletes (although both are very slow for an ArrayDeque). It also allows bidirectional traversal. Works efficiently with both ArrayDeque and LinkedList.

ArrayDeque example in java

package collection;

import java.util.ArrayDeque;
import java.util.Iterator;

public class ArrayDequeDemo
{
    public static void main(String[] args)
    {   
        ArrayDeque arrDeque = new ArrayDeque();

        arrDeque.add("mercedes");
        arrDeque.add("porsche");
        arrDeque.add("audi");

        for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
            System.out.println(iter.next());
        }

        System.out.println();

        arrDeque.addLast("bmw");
        arrDeque.add("PORSCHE");
        arrDeque.addLast("Ferrari");

        for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
            System.out.println(iter.next());
        }

        System.out.println();

        for(Iterator descendingIter = arrDeque.descendingIterator();descendingIter.hasNext();) {
            System.out.println(descendingIter.next());
        }

        System.out.println();
        System.out.println("First Element : " + arrDeque.getFirst());
        System.out.println("Last Element : " + arrDeque.getLast());
        System.out.println("Contains \"porsche\" : " + arrDeque.contains("porsche"));

        arrDeque.addFirst("porsche");

        System.out.println();

        for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
            System.out.println(iter.next());
        }

        arrDeque.removeLastOccurrence("porsche");

        System.out.println();

        for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
            System.out.println(iter.next());
        }

        arrDeque.removeFirstOccurrence("porsche");
        System.out.println();

        for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
            System.out.println(iter.next());
        }

        System.out.println();
        System.out.println("Popped Element : " + arrDeque.pop());

        arrDeque.push("porsche");       
        System.out.println();

        for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
            System.out.println(iter.next());
        }

        System.out.println("\n Size of Array Deck : " + arrDeque.size());

        System.out.println("\n Peek : " + arrDeque.peek());

        System.out.println("\n Peek First : " + arrDeque.peekFirst());
        System.out.println("\n Peek Last : " + arrDeque.peekLast());

        System.out.println();

        for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
            System.out.println(iter.next());
        }

        System.out.println("\n Poll First : " + arrDeque.pollFirst());
        System.out.println("\n Poll Last : " + arrDeque.pollLast());

        System.out.println();

        for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
            System.out.println(iter.next());
        }

        System.out.println("\n Poll : " + arrDeque.poll());

        System.out.println("\n Peek First : " + arrDeque.peekFirst());
        System.out.println("\n Peek Last : " + arrDeque.peekLast());

        arrDeque.offerFirst("porsche");
        arrDeque.offerLast("what the heck?");

        System.out.println();

        for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
            System.out.println(iter.next());
        }

        System.out.println("\n Get First : " + arrDeque.getFirst());
        System.out.println("\n Get Last : " + arrDeque.getLast());

        System.out.println("\n Element : " + arrDeque.element());

        Object[] objArray = arrDeque.toArray();
        System.out.println("\n Object Array Size : " + objArray.length);

        String[] strArray = (String[]) arrDeque.toArray(new String[0]);
        System.out.println("\n String Array Size : " + strArray.length);

        ArrayDeque arrDequeClone = arrDeque.clone();
        System.out.println("Clone Size : " + arrDequeClone.size());

        System.out.println("arrDeque == arrDequeClone : " + (arrDeque == arrDequeClone));

        System.out.println("arrDeque.equals(arrDequeClone) : " + arrDeque.equals(arrDequeClone));
    }
}

See Oracle/Sun's website for more on this.