JavaSpecialists.EU - Interlocker - Interleaving Threads

 by Heinz Kabutz 2010 
A few months ago, one of my subscribers sent me an interesting question. How can you alternately call a method from two threads? Imagine you have two threads, first thread 1 calls a method, then thread 2, then thread 1 again, and so on. One thread should never call the method twice in a row.

Mohammed sent me several different solutions to this puzzle. My first step was to make our testing a bit more robust, so that we could catch any mistakes early. I also spent a while renaming the classes, to make our intentions clearer. Lastly, I marked up the classes with the new jpatterns annotations to indicate where we were using which design patterns. Thejpatterns.org annotations are a new project started by The Java Specialist Club. You are welcome to participate in the project if you would like to.

Disclaimer: I cannot think of a practical application of where such an "interlocker" would be useful. However, some of the discoveries might be useful in highly communicative systems. such as the lock-free approach to solving the problem. Only use if you know exactly what you are doing :-)

As a first class, we define Interlocker, which uses the template method to start threads that will call the Runnables. The execute() method will block until all the threads have finished. The Runnable objects returned by the getRunnable() method should guarantee that the InterlockTask is called interleaved by the threads. They do not have to guarantee which thread starts, but the total call count must be correct.

package interlock;

import org.jpatterns.gof.*;

/**
 * This special executor guarantees that the call() method of the
 * task parameter is invoked in turns by two threads.  There is
 * probably no practical application for this class, except as a
 * learning experience.
 */
@TemplateMethodPattern.AbstractClass
public abstract class Interlocker {
  @TemplateMethodPattern.PrimitiveOperation
  protected abstract Runnable[] getRunnables(InterlockTask task);

  @TemplateMethodPattern.TemplateMethod
  public final  T execute(InterlockTask task)
      throws InterruptedException {
    Runnable[] jobs = getRunnables(task);
    Thread[] threads = new Thread[jobs.length];
    for (int i = 0; i < threads.length; i++) {
      threads[i] = new Thread(jobs[i]);
      threads[i].start();
    }
    for (Thread thread : threads) {
      thread.join();
    }
    return task.get();
  }
}
  
Before we look at some possible solutions, let us view the InterlockTask interface. It is self explanatory.
package interlock;

import org.jpatterns.gof.*;

@StrategyPattern.Strategy
public interface InterlockTask {
  boolean isDone();

  /**
   * The call() method is called interleaved by the the threads
   * in a round-robin fashion.
   */
  void call();

  /**
   * Returns the result after all the call()'s have completed.
   */
  T get();

  void reset();
}
  
In the first test case, we want to simply increment a value. Since we are accessing the field from multiple threads, we need to declare it as volatile, but since only one thread is invoking the call() method, we do not need to synchronize. Since this test does very little, we can also use it to measure the overhead of our thread coordination mechanism.
package interlock.test;

import org.jpatterns.gof.*;
import interlock.*;

@StrategyPattern.ConcreteStrategy

public class EmptyInterlockTask implements
    InterlockTask {
  public final int upto;
  private volatile int count;

  public EmptyInterlockTask(int upto) {
    this.upto = upto;
  }

  public boolean isDone() {
    return count >= upto;
  }

  public void call() {
    count++;
  }

  public Integer get() {
    return count;
  }

  public void reset() {
    count = 0;
  }
}
  
The next test verifies that the call() method was invoked by alternating threads. We do this by inserting the current call number into a LinkedHashMap, with the number as key and the thread as a value. Afterwards, when we call get(), we verify that the result is correct. This is returned in the VerifyResult object.
package interlock.test;

import org.jpatterns.gof.*;

import java.util.*;

import java.util.concurrent.atomic.*;

import interlock.*;

@StrategyPattern.ConcreteStrategy
public class InterleavedNumberTestingStrategy implements
    InterlockTask {
  public final int upto;
  private final Map numbers =
      new LinkedHashMap();
  private final AtomicInteger count = new AtomicInteger(0);

  public InterleavedNumberTestingStrategy(int upto) {
    this.upto = upto;
  }

  public boolean isDone() {
    return count.get() >= upto;
  }

  public void call() {
    int next = count.getAndIncrement();
    numbers.put(next, Thread.currentThread());
  }

  public VerifyResult get() {
    if (numbers.size() < upto) {
      return new VerifyResult("Only " + numbers.size() +
          " numbers were entered");
    }
    Object previous = null;
    int i = 0;
    for (Map.Entry entry : numbers.entrySet()) {
      if (i != entry.getKey()) {
        return new VerifyResult("numbers out of sequence");
      }
      if (entry.getValue() == previous) {
        return new VerifyResult("Did not alternate threads");
      }
      previous = entry.getValue();
      i++;
    }
    Set values = new HashSet(numbers.values());
    if (values.size() != 2) {
      return new VerifyResult(
          "More than two threads were inserting values");
    }
    return new VerifyResult();
  }

  public void reset() {
    numbers.clear();
    count.set(0);
  }
}


package interlock.test;

public class VerifyResult {
  private final boolean success;
  private final String failReason;

  private VerifyResult(boolean success, String failReason) {
    this.success = success;
    this.failReason = failReason;
  }

  public VerifyResult(String failReason) {
    this(false, failReason);
  }

  public VerifyResult() {
    this(true, null);
  }

  public boolean isSuccess() {
    return success;
  }

  public String getFailReason() {
    return failReason;
  }

  public String toString() {
    return success ? "Success" : "Failure - " + failReason;
  }
}
  
Another task could print the threads, for example:
// *snip*
  public boolean isDone() {
    return row.get() >= upto;
  }

  public void call() {
    System.out.println(Thread.currentThread().getName());
    row.incrementAndGet();
  }
  

Interlocker Solutions

The easiest solution is to use semaphores. We start with two semaphores. The first has 1 barrier, the second zero. From thread 1, we acquire semaphore 1, do the call(), then release semaphore 2. From thread 2, we acquire semaphore 2, do the call(), then release semaphore 1. The reason this works is that you can release a semaphore from a thread that has not acquired it. This is quite different to locks, where only the thread that acquired the lock can release it.
package interlock.impl;


import interlock.*;

import java.util.concurrent.*;

public class SemaphoreInterlocker extends Interlocker {
  private static class Job implements Runnable {
    private final InterlockTask task;
    private final Semaphore first;
    private final Semaphore second;

    public Job(InterlockTask task,
               Semaphore first, Semaphore second) {
      this.task = task;
      this.first = first;
      this.second = second;
    }

    public void run() {
      while (!task.isDone()) {
        first.acquireUninterruptibly();
        if (task.isDone()) return;
        task.call();
        second.release();
      }
    }
  }

  protected Runnable[] getRunnables(InterlockTask task) {
    Semaphore even = new Semaphore(1);
    Semaphore odd = new Semaphore(0);
    return new Runnable[]{
        new Job(task, even, odd),
        new Job(task, odd, even)
    };
  }
}    
  
When running this code, I noticed that it was rather slow. For example, to increment an int one million times took 4 seconds on my machine, of which most was context switching:
InterlockTask task = new EmptyInterlockTask(1000 * 1000);
Interlocker generator = new SemaphoreInterlocker();

long time = System.currentTimeMillis();
generator.execute(task);
time = System.currentTimeMillis() - time;
System.out.println(time);
  
The other solutions that we developed, using wait-notify and Java 5 Condition, were similar in performance characteristic. We will leave those Interlockers as an exercise for the reader :-) If you want to attempt them, remember the effects that spurious wakeups can have on your Object.wait() and Condition.await().

Lock Free Interlocker

I wanted to write a fast Interlocker implementation, ideally not locking at all and using a volatile field as a communication mechanism. Here is what I did:
package interlock.impl;

import interlock.*;

public class LockFreeInterlocker extends Interlocker {
  private volatile boolean evenHasNextTurn = true;

  private class Job implements Runnable {
    private final InterlockTask task;
    private final boolean even;

    private Job(InterlockTask task, boolean even) {
      this.task = task;
      this.even = even;
    }

    public void run() {
      while (!task.isDone()) {
        while (even ^ evenHasNextTurn);
        if (task.isDone()) {
          return;
        }
        task.call();
        evenHasNextTurn = !even;
      }
    }
  }

  protected Runnable[] getRunnables(InterlockTask task) {
    return new Runnable[]{
        new Job(task, true), new Job(task, false)
    };
  }
}
  
This approach to thread communication is faster when the call() method completes quickly. Since we are doing a busy wait, we will burn up CPU cycles in the waiting thread. For a long call() method, one of your CPUs would be running at 100% polling a field value. This is not a good idea unless you have lots of spare CPUs that you do not know what to do with. However, if you want to just do a very task inside call(), then this approah is substantially faster.
Where this might be handy is if you have a lot of thread communication that you need to speed up. Some financial applications might find this information useful.

Caveat: Livelock (or "unbreakable hard spin")

If we modify the LockFreeInterlocker slightly to use a boolean XOR instead of bitwise, then we can cause the JVM to hang up. I called this a livelock, for want of a better term. When I demonstrated this to Doug Lea, he named it an "unbreakable hard spin". Cliff Click also had a look at it and thinks it might be because the server hotspot compiler is not inserting a safepoint at the right place. This problem occurs in OpenJDK / Sun JDK server HotSpot compilers running on at least 2 physical cores and from JDK 1.6.0_14 onwards. Code available on request.


GWT 2.1 RC1 is now available

Posted by Chris Ramsdale - Monday, October 11, 2010 at 6:50:00 PM



Building on the three previous milestones, we're happy to announce the first release candidate (RC1) of GWT 2.1. While we're still focused on the overall theme of making it easier to build cloud portable business apps via some help from our friends at VMware and Spring, there are more than a few aspects that make this milestone a RC.

First we've rounded out the list of components and features that will ship with GWT 2.1. One of these components is a new Editor framework that allows you to bind your DTOs to a customizable UI which handles all of necessary grunt work of validating and syncing change sets. Another is the availability of theSafeHTML component and its integration within the cell-based widgets. After all, we've optimized these new widgets by injecting HTML, we better do it in a secure manner.

Along with the new components and features, we've solidified the Activities/PlacesRequestFactory, Editor framework, and Cell-based widget APIs. So, if you're looking to start a project with GWT 2.1, you can feel confident that your team won't have to refactor code because we've switched out interfaces between now and the final release.

Also, if you're looking to get started with GWT 2.1 we have an initial draft of the new Developer Guides. These can be found at the links below (the Editor framework Developer Guide is coming soon).
As with previous milestones, there will be an associated Spring Roo RC1 and SpringSource Tool Suite RC1, that will be available in the next few days. Keep your eye on the SpringSource blog, as Christian and Ben are active contributors.

GWT 2.1 RC is available on our Google Code download site and as version 2.1-SNAPSHOT in the Google Maven Snapshot Repository. We’d love to hear your feedback and thoughts on this release, and our GWT Developer Forum would be the best place to post this information.

New features:

Data Presentation Widgets
Data Presentation Widgets (Cell Widgets) allow developers to to create highly efficient views on top of large data sets. These widgets have two unique design strengths. One, they're able to render subsets of a dataset in the same way they would if they had fetched the entire dataset. For your end-users this means the initial load of a view is fast, even if that view is tied to millions of records on the backend. Secondly, cell widgets use a 'flyweight' design. Rather than being a container of other widgets, which can tend to be heavy, they build up chunks of HTML that is injected into the DOM. This not only speeds up initialization, but also reduces the event handling overhead that can slow down user experience when there are hundreds of widgets in a view.

MVP Framework (Activities and Places)

The MVP framework is an application framework that supports development of large scale GWT applications with the Model - View - Presenter pattern. The MVP framework provides a client-side EventBus, manages Activities, and synchronizes Places with browser history.
To make developing apps of this style easier, Spring Roo, though not required, can generate and maintain the boilerplate code associated with connecting your app's components with GWT's MVP Framework.

RequestFactory

RequestFactory is an alternative to GWT-RPC for creating data-oriented services. RequestFactory and its related interfaces (RequestContext and EntityProxy) make it easy to build data-oriented (CRUD) apps with an ORM-like interface on the client. It is designed to be used with an ORM layer like JDO or JPA on the server, although this is not required.

Server-side Speed Traces

We've mentioned before that Speed Tracer is a tool that helps you identify and fix performance problems in web applications. Until now the problems it can help you fix have be limited to client-side code.
With Speed Tracer, you can now view sever-side timing data for apps running on Google App Engine and SpringSource's TC Server Developer Edition. With this integration, you'll be able to view metrics for database calls, memcache hits, resources fetches, as well as other server-side service calls. The new metrics views are integrated into the existing Speed Tracer UI, all you need to do is navigate to the Network (resources) and you'll start see your server-side traces.

Logging

Logging of client-side code in GWT applications is new. Logging helps you understand how the application executes and make it easier to troubleshoot issues encountered by developers and users. In GWT, you can log client-side code directly to handlers on the client side, or you can use remote logging to log client-side code to handlers on the server side.
The logging framework emulates java.util.logging, so it uses the same syntax and has the same behavior as server side logging code. This allows you to share logging code between the client and server side code.

Safe HTML

SafeHtml provides a library that, when used with the coding guidelines, supports the development of GWT applications that are free from a large class of XSS vulnerabilities. It provides this benefit while minimizing overhead in runtime and development effort. This class of potential XSS vulnerabilities in GWT apps arises from the use of methods that cause the browser to evaluate their argument as HTML, for example, setInnerHTML and setHTML, as well as the constructors of HTML-containing widgets such as HTML.






Cool development tools from Google

The classic GWT tools:

SDK


The Google Web Toolkit SDK contains the core libraries and compiler that you need to write web applications. See the Release Notes for this latest version.

Speed Tracer


Speed Tracer is a Chrome Extension that allows you to pinpoint performance problems in your
web applications.

Plugin for Eclipse


The Google Plugin for Eclipse provides IDE support for Google Web Toolkit and App Engine web projects.

New tools:

GWT Designer


Create rich web applications with GWT Designer, a powerful set of Eclipse-based development tools that enables Java developers to quickly create Ajax web applications using the Google Web Toolkit (GWT). -- ex-Instantiations --

WindowTester Pro


Streamline testing of Java rich client applications with WindowTester Pro, including tools for automated recording, test generation, code coverage and playback of GUI interactions that can occur within an application. WindowTester Pro includes support for SWT and Swing.

CodePro AnalytiX


Employ the comprehensive automated software code quality and security analysis toolkit CodePro AnalytiX to automatically improve software quality, reliability, and maintainability in developer applications.

Cloud portability from Google and VMware

Develop and deploy rich web apps for your enterprise, across multiple environments and devices.

Google and VMware have enhanced our open source Java development tools, allowing enterprise developers to rapidly build rich web apps, run them on multiple devices, and deploy them on-premise or in the cloud of your choice. Familiar tools turn Java developers into cloud developers, and standard APIs avoid cloud lock-in.
  • Spring Roo

    With Spring Roo, a next-generation rapid application development tool, Java developers can easily build full Java applications in minutes, using the Java Persistence API (JPA) to connect them to new or existing databases. Roo outputs standard Java code, so it’s easy to refine the back end with the SpringSource Tool Suite and the front end with the Google Web Toolkit SDK, using Roo as much or as little as desired.
  • SpringSource Tool Suite

  • Using the Eclipse-based SpringSource Tool Suite, developers can now choose to deploy their application on Google App Engine for Business, a VMware environment (your vSphere infrastructure, your choice of vCloud partners, or VMforce), or other infrastructure such as Amazon EC2. We call this cloud portability.
  • Google App Engine for Business

  • Google App Engine for Business enables organizations to build and host web apps on the same systems that power Google applications and includes new enterprise-level features, a 99.9% uptime SLA, support and flat-rate pricing. Google App Engine for Business is a first-class choice for deploying enterprise apps to the cloud as part of a cloud portability strategy, whether for seasonal apps, bursty apps, disaster recovery, or simply for friction-free deployment of new apps.


I don't know about you regarding the GWT Designer, but I tried it some time ago, and it worked very well with the standard GWT widgets, supported pretty well the widgets from GWT-Ext library, with small bugs, which were fixed along ... and now we can use the ones from GXT (ext-ExtJs or Scencha nowadays). It's a good prototype-maker though.

The tester tool seems a good alternative to FireFox plugin called Selenium (http://seleniumhq.org/)  -- need to have a careful look at it.

What's more interesting is the CodePro tool, which helps you to clean up your code of potential bugs or bad coding habits. It's very very good tool.

So, we need to used them daily to improve the result of our work -- the software application.

Cheers!

Cool Movie Browser

Cool Movie Browser is discovering and gathering all your video files, which are distributed on different computers and hard-drives, into a single place. After that, you can play them in your favorite (you choose) media player application (VLC Player, Windows Media Player, QuickTime Player etc.)



The last version 1.2.101005 has added the online sport TV panel, which gives you all the live streams from net with the games of the day.

As said, it allows you to play each movie with its own media player (i.e. you can set .avi files to be played with VLC Player, and all .mpg movies with Windows Media Player).

For each discovered movie it will bring the poster image from the "cloud" (Internet), so you don't have to worry about identifying quickly your preferred TV show.

Also, you can create and manage (create, edit, delete, reorder, play) your own playlists.


Buzz: This application can centralize different kind of files, not only movies. Because it's flexible and configurable, we can choose the extension of the file, which we need to see (.doc), and instead of setting the command line for WMPlayer, we can put the one for Office Word. Doing this you can easily manage all Word documents from your different hard-drives, in one single place. Indeed it's cool!