JGameGrid
 
 

The source code of all examples is included in the JGameGrid distribution.

Ex19: Multithreading Issues

In modern GUI-based programs there is no way to circumvent a modest knowledge of concurrency. In applications with a GUI at least two threads are involved: the application thread that executes the main class constructor and the so-called Event Dispatch Thread (EDT) that executes all GUI callback methods (for mouse, keyboard, menu, button events). With JGameGrid there is a third thread running: the animation thread that executes each actor's act() method and the collision event methods.

In principle the running code of one thread may be interrupted any time by another thread and resumed at a later moment. Compared to strictly sequential programs, multithreaded programs requires a new way of thinking that is unusual for beginners which are "von Neumann minded": Programs will do this, and then this, and then this.

Because in JGameGrid all act() methods are executed by the same animation thread, they execute sequentially (determined by the "act-order"). So one actor can not interrupt an another one, and all actors must collaborate friendly by not executing long lasting code in their act() method. The best design to circumvent concurrency is to use the application thread for initializing purposes and let it run to an end. All other actions are performed in the act() methods. In this case the program is completely free of multithreading issues.

Multithreading issues have to be considered

  • when the application thread continues to run (normally in an endless loop)
  • when mouse, keyboard or Xbox controller callbacks are used
  • when an own thread is started

In multithreaded programs special care must be taken to avoid interruption of "critical section" where several lines of program must be executed by the same thread in order to maintain a well-defined state. Java provides a pretty simple synchronization mechanism between different threads using the keyword synchronized. Unfortunately too much synchronization leads to deadlocks that cause the program to hang unpredictably.

In order to avoid synchronization and deadlocks and simplify the programming for beginners, the methods of class Actor and some methods of class GameGrid are thread-safe. This means that these classes can be used by different threads without bothering with multithreading problems. We demonstrate an otherwise risky program where 50 new diamond actors are created by the single mouse click. The act() method of each diamond is responsible to change its sprite image (showing a rotation effect) and to remove the diamond from the scene when it leaves the visible game grid. Because both, creating and deleting actors, modify the GameGrid's internal structure, without internal synchronization concurrent access violations would occur.

import ch.aplu.jgamegrid.*;
import java.awt.*;

public class Ex19 extends GameGrid implements GGMouseListener
{
  // Runs in application thread
  public Ex19()
  {
    super(600, 600, 1, null, false);
    setBgColor(Color.blue);
    setSimulationPeriod(30);
    addMouseListener(this, GGMouse.lPress);
    show();
    doRun();
  }

  // Runs in Event Dispatch Thread (EDT)
  public boolean mouseEvent(GGMouse mouse)
  {
    for (int i = 0; i < 50; i++)
    {
      addActor(new Diamond(), 
               toLocationInGrid(mouse.getX(), mouse.getY()),
               360 *Math.random());
      Thread.currentThread().yield(); 
    }
    return true;
  }

  public static void main(String[] args)
  {
    new Ex19();
  }
}

Calling Thread.yield() may improve the time behavior on slower CPUs, because it invites the animation thread to run during the somewhat time-consuming creation of the diamonds. The Diamond class is simple. It uses 4 sprite images that are cycled.

import ch.aplu.jgamegrid.*;

public class Diamond extends Actor
{
  public Diamond()
  {
    super("sprites/diamond.gif", 4); // 4 sprites
  }

  // Runs in animation thread
  public void act()
  {
    if (!isMoveValid())
      removeSelf();
    else
    {
      showNextSprite();
      move();
    }
  }
}

 

jgamegrid17

Execute the program locally using WebStart. Click rapidly into playground.

 

Ex20: Synchronizing

Even synchronizing can be avoided in many cases, you are not completely immune of concurrency problems. It is fun to construct a program that fails due to concurrent accesses. In the following demonstration an instance variable index and a Actor array is used. Clicking the mouse selects the current actor by cycling through the index variable. Nothing evil, isn't it? The act() method moves the selected actor back and forth.

import ch.aplu.jgamegrid.*;
import java.awt.*;

public class Ex20 extends GameGrid implements GGMouseListener
{
  private int index = 0;
  private Actor actors[] = new Actor[2];

  // Runs in application thread
  public Ex20()
  {
    super(600, 600, 1, null, false);
    setBgColor(Color.blue);
    setSimulationPeriod(30);
    addMouseListener(this, GGMouse.lPress);
    actors[0] = new Actor("sprites/ball_0.gif");
    actors[1] = new Actor("sprites/ball_1.gif");
    for (Actor actor : actors)
      addActor(actor, new Location(300, 300));
    show();
    doRun();
  }

  // Runs in EDT
  public boolean mouseEvent(GGMouse mouse)
  {
    index++; 
    doSomething();
    if (index == 2)
      index = 0;
    return true;
  }

  private void doSomething()
  {
    delay(50);
  }

  // Runs in animate thread
  public void act()
  {
    Actor actor = actors[index];
    actor.move();
    if (!actor.isInGrid())
      actor.setDirection(actor.getDirection() + 180);
  }

  public static void main(String[] args)
  {
    new Ex20();
  }
}

Execute the program locally using WebStart. Click rapidly into playground.

The program crashes with an ArrayIndexOutOfBoundsException. Why?

jgamegridtut18

 

For "thread-aware" programmers the bug is evident: Reading and modifyng the state variable index must be "atomic": After incrementing the index in the mouse callback method, resetting the variable to zero when it reaches 2 should not be interrupted by the animate thread. Otherwise an illegal value of 2 may be read. Synchronizing both, mouseEvent() and act(), will solve the problem. By the way, because index is used by two threads, it should be declared volatile. Otherwise the program may still fail on certain machines, because the current value may not be visible from both threads.

(It is true that we provoke the crash by introducing doSomething(), but even if you remove it and you cannot reproduce the crash, you cannot guarantee that it never happens.)

The correct program is the following:

import ch.aplu.jgamegrid.*;
import java.awt.*;

public class Ex20a extends GameGrid implements GGMouseListener
{
  private volatile int index = 0;
  private Actor actors[] = new Actor[2];

  public Ex20a()
  {
    super(600, 600, 1, null, false);
    setBgColor(Color.blue);
    setSimulationPeriod(30);
    addMouseListener(this, GGMouse.lPress);
    actors[0] = new Actor("sprites/ball_0.gif");
    actors[1] = new Actor("sprites/ball_1.gif");
    for (Actor actor : actors)
      addActor(actor, new Location(300, 300));
    show();
    doRun();
  }

  public synchronized boolean mouseEvent(GGMouse mouse)
  {
    index++;
    doSomething();
    if (index == 2)
      index = 0;
    return true;
  }

  private void doSomething()
  {
    delay(50);
  }

  public synchronized void act()
  {
    Actor actor = actors[index];
    actor.move();
    if (!actor.isInGrid())
      actor.setDirection(actor.getDirection() + 180);
  }

  public static void main(String[] args)
  {
    new Ex20a();
  }
}

Execute the program locally using WebStart. Click rapidly into playground.

 

Ex21: Deadlocks

Using concurrency the risk of deadlocks is the programmer's nightmare. This happens typically in the following situation: Two threads need two resources (data, object instances, etc.) to fulfill their task. If one of the resources is unavailable (in use), the thread must wait until the resource is available. What happens if the first thread gets the first resource and the second thread gets the second resource? Yes: both threads are waiting indefinitely and the program hangs. (The most famous example of a deadlock is discussed in the "Dining philosophers problem".) In former days demonstrations of concurrency and deadlocks were presented using console programs where the current state was written to a text console. It is much more realistic and impressive to present deadlocks using graphics. With JGameGrid a graphics based program is merely more complicated than a console program.

We model a dining couple (man, woman) sitting at a table. There are two table settings, a single fork and a single knife that have to be shared. Each person needs both of them to start eating. If the two persons are not "synchronized" (they may talk together or observe rules), a deadlock causing "starvation" may occur: The man gets one item and the woman gets the other one, but both are waiting to obtain both items.

In our demonstration the man and the woman are instances of the Person class that models an active object using an own internal thread. This is easily accomplished by implementing Runnable and creating/starting the thread in the eat() method. The thread's run() method uses a endless loop where the persons request a knife and a fork and start to eat after they got both. We introduce some delays to model the "personality" of the persons. In our first attempt we do nothing to coordinate the persons (synchronized is commented-out).

import ch.aplu.jgamegrid.*;

public class Person extends Actor implements Runnable
{
  private String gender;
  private Fork fork;
  private Knife knife;
  private int delayTime;
  private boolean haveFork = false;
  private boolean haveKnife = false;
  private Thread t;

  public Person(String gender, Fork fork, Knife knife, int delayTime)
  {
    super(gender.equals("man") ? "sprites/man.gif" : "sprites/woman.gif", 4);
    this.gender = gender;
    this.fork = fork;
    this.knife = knife;
    this.delayTime = delayTime;
  }

  public Thread getThread()
  {
    return t;
  }

  public void eat()
  {
    t = new Thread(this);
    t.start();
  }

  private boolean requestFork()
  {
    if (fork.isInUse())
      return false;
    fork.use(true);
    return true;
  }

  private boolean releaseFork()
  {
    if (!fork.isInUse())
      return false;
    fork.use(false);
    return true;
  }

  private boolean requestKnife()
  {
    if (knife.isInUse())
      return false;
    knife.use(true);
    return true;
  }

  private boolean releaseKnife()
  {
    if (!knife.isInUse())
      return false;
    knife.use(false);
    return true;
  }

  public void run()
  {
    while (true)
    {
 //     synchronized (gameGrid)
      {
        if (!haveFork)
        {
          haveFork = requestFork();
          if (haveFork && !haveKnife)
          {
            show(1);
            gameGrid.refresh();
          }
        }
        delay(delayTime);  // Time to wait before requesting knife
        if (!haveKnife)
        {
          haveKnife = requestKnife();
          if (haveKnife && !haveFork)
          {
            show(2);
            gameGrid.refresh();
          }
        }

        if (haveFork && haveKnife)  // We have fork and knife, so we can eat
        {
          show(3);
          gameGrid.refresh();
          int delay = (int)(delayTime * (Math.random() + 1));
          delay(delay);  // Eating time somewhat random

          releaseFork();
          haveFork = false;
          show(2);
          gameGrid.refresh();
          delay(delayTime);  // Time to wait to give back knife

          releaseKnife();
          haveKnife = false;
          show(0);
          gameGrid.refresh();
        }
      }
      delay(1000);  // Time to wait until next request
    }
  }
} 

Because the GameGrid's doRun() is not executed (nor the Run button hit), the internal animation thread will not refresh the window automatically. We have to do it manually by calling gameGrid.refresh(). To show the different states of the persons we use an actor with 4 sprite images:

  • no item in hand
  • fork in hand
  • knife in hand
  • both items in hand

The Fork and Knife classes are actors too. They are hidden when used by one of the persons.

import ch.aplu.jgamegrid.*;

public class Fork extends Actor
{
  private boolean inUse = false;

  public Fork()
  {
    super("sprites/fork.gif");
  }

  public boolean isInUse()
  {
    return inUse;
  }

  public void use(boolean b)
  {
    inUse = b;
    if (inUse)
      hide();
    else
      show();
    gameGrid.refresh();
  }
}


import ch.aplu.jgamegrid.*;

public class Knife extends Actor
{
  private boolean inUse = false;

  public Knife()
  {
    super("sprites/knife.gif");
  }

   public boolean isInUse()
  {
    return inUse;
  }

  public void use(boolean b)
  {
    inUse = b;
    if (inUse)
      hide();
    else
      show();
    gameGrid.refresh();
  }
}

 

The application class constructor creates all necessary objects and calls the eat() methods. The main thread then loops to display the current thread states in the title bar.

import ch.aplu.jgamegrid.*;

public class DiningCouple extends GameGrid
{
  private final int delayTimeMan = 1000;
  private final int delayTimeWoman = 3000;

  public DiningCouple()
  {
    super(500, 300, 1, null, false);
    addActor(new Actor("sprites/table.gif"), new Location(250, 200));

    Fork fork = new Fork();
    addActor(fork, new Location(230, 200));
    Knife knife = new Knife();
    addActor(knife, new Location(270, 200));

    Person man = new Person("man", fork, knife, delayTimeMan);
    Person woman = new Person("woman", fork, knife, delayTimeWoman);
    addActor(man, new Location(170, 80));
    addActor(woman, new Location(330, 80));
    show();
    delay(2000);

    man.eat();
    woman.eat();

    while (true)
    {
     Thread.State manState = man.getThread().getState();
      Thread.State womanState = woman.getThread().getState();
      setTitle("Thread States: Man: " + manState + ", Woman: " + womanState);
      delay(200);
    }
  }

  public static void main(String[] args)
  {
    new DiningCouple();
  }
}

When executing, neither the man nor the woman are happy because, before long, a deadlock occurs.

Execute the deadlock-prone program locally using WebStart. (Sprites images from Threadnocchio (modified)).

jgamegridtut21

Deadlock: Both threads are in TIMED_WAITING state

When the critical block is synchronized, each person's thread must wait to get the lock (monitor) from the gameGrid instance before entering the block. Just adding one line of code resolves the problem.

Execute the deadlock-free program locally using WebStart.

jgamegridtut20

No deadlock: Man's thread is in the BLOCKED state, but may execute as soon as the lock is free