Java Multithreading

Java Multithreading

Yaodong Bi

Department of Computing Sciences

University of Scranton

Scranton, PA 18510

November 7, 2018

1Line Tracing Robot

Line tracing robot is a robot that searches for a black line and then tries to follow it. The hardware of the robot consists of two motors and two light sensors. The light sensors detect the color of the floor and the robot makes turns based on the sensor readings. The robot stops when the LEFT button is pressed.

In this section we will discuss two different implementations of software: sequential and concurrent implementations.

2Hardware Design

The ground surface on which the robot (vehicle) runs is white with a circular black band. Line tracing robot consists of a NXT brick, two color/light sensor attached to input ports 1 and 2 as the left and right sensors, two servo motors mounted to output ports A and B to drive the left and right front wheels of the robot, respectively. The two color sensors are at the front of the vehicle, side by side to detect the color of the surface. It is intended that the black line would always be between the two sensors. When the left sensor detects black color and the right sensor detects white (or not black), the vehicle would turn left by stopping the left motor and running the right motor forward. The same logic follows for turning right and moving forward.

3A Sequential Design and Implementation

The following program shows a sequential design and implementation of the software for the line-tracing robot with LeJOS and Java. The design follows a round-robin software architecture. It polls the readings of the light sensors and makes decision based on the readings. The program can be divided into three functional segments. The first segment is to initialize the light sensors and motors. The second segment is a while loop used to find the black line. It compares the readings of the sensors and it keeps moving forward until one of the sensors has a reading of black color (reading is less than 5). The third segment is to make necessary turns based on the readings of the light sensors to follow the black line. This is a done with a while loop, and at the end of each loop it check the running flag to see if it should stop. A button listener is attached to the LEFT button. Once the button is pressed, the listener resets the running flag and stops all motors.

import lejos.nxt.*;
import lejos.nxt.addon.*;
publicclass Tracer implements ButtonListener {
privatestaticfinalint BLACK_COLOR = 5;
privatestaticfinalint MOTOR_SPEED = 100;
privateint leftColor = 0;
privateint rightColor = 0;
privateboolean running = true;
publicvoid start() throws InterruptedException {
// initialize sensors and motors
ColorSensor leftSensor = new ColorSensor(SensorPort.S1);
ColorSensor rightSensor = new ColorSensor(SensorPort.S2);
Motor.A.setSpeed(MOTOR_SPEED);
Motor.B.setSpeed(MOTOR_SPEED);
Button.LEFT.addButtonListener(this);
LCD.clear(); /* Clear the LCD display */
// find the black line
leftColor = leftSensor.getColorNumber();
rightColor = rightSensor.getColorNumber();
while (leftColor > BLACK_COLOR & rightColor > BLACK_COLOR) {
LCD.drawString("srch", 1, 5);
Motor.A.forward();
Motor.B.forward();
leftColor = leftSensor.getColorNumber();
rightColor = rightSensor.getColorNumber();
Thread.sleep(50);
}
// follow the black line
while (running) {
leftColor = leftSensor.getColorNumber();
rightColor = rightSensor.getColorNumber();
if (!isBlack(leftColor) & !isBlack(rightColor)) {
Motor.A.forward();
Motor.B.forward();
display(leftColor, rightColor, "forward");
} elseif (isBlack(leftColor) & !isBlack(rightColor)) {
Motor.A.forward();
Motor.B.stop();
display(leftColor, rightColor, "turn left");
} elseif (!isBlack(leftColor) & isBlack(rightColor)) {
Motor.A.stop();
Motor.B.forward();
display(leftColor, rightColor, "turn right");
} else {
Motor.A.forward();
Motor.B.forward();
display(leftColor, rightColor, "forward-LOST");
}
Thread.sleep(1);
}
display(leftColor, rightColor, "Stopped");
Thread.sleep(100);
}
privatevoid display(int left, int right, String dir) {
LCD.clear();
LCD.drawString(dir, 1, 5);
LCD.drawInt(left, 1, 6);
LCD.drawInt(right, 1, 7);
}
publicvoid buttonPressed(Button b) {
if (!running) {
running = true;
} else {
stopMotors();
}
}
publicvoid buttonReleased(Button b) {
}
privatevoid stopMotors() {
running = false;
Motor.A.stop();
Motor.B.stop();
}
privateboolean isBlack(int color) {
if (color < BLACK_COLOR)
returntrue;
else
returnfalse;
}
publicstaticvoid main(String args[]) throws InterruptedException {
Tracer roboDemo = new Tracer();
roboDemo.start();
}
}

The program controls the robot pretty well. When the robot is placed in the center of the black belt of the Lego test paper, it moves forward until it finds the black belt and then it follows it.

4A Concurrent Design and Implementation

A thread in Java is like a process; it can be executed independent of other threads. A thread may be designed to perform a simple, atomic task.

Java provides the Thread class for thread creation, control, and termination. There are two ways to create a new thread. One way is instantiate a class that extendsThread and the other way is define a class that implements the Runnable interface and then pass an instance of the class to a constructor of Thread. The most important method of Threadand Runnableis run(), which is to be overridden by the user-defined thread to do the real work the thread is intended to. The start() method of Thread is to start the execution of the thread. It first requests the JVM to allocate memory space for the new thread and then invokes the run() method of the thread.

The following is a Java program, TwoHello, which displays on the LCD greetings to “Tom” and “Clark” at the rate of once every 3 seconds and one every 2 seconds, respectively. The TwoHello class extends Thread and it defines its own run() method. The run() method prints the name stored in the object at the specified rate. The main()function instantiates two instances of the TwoHello class and then starts their execution by calling their respective start() methods. After a thread is created, it does not automatically start its execution. It must call the start().

import josx.platform.rcx.*;
public class TwoHello extends Thread {
private String name;
private int delay;
public TwoHello(String name, int delay) {
this.name = name;
this.delay = delay;
}
public void run(){
try {
for (int i=0; i < 5; i++) {
System.out.println(name);
sleep(delay*1000);
}
} catch (InterruptedException e) {
return;
}
}
public static void main(String argv[]) {
TwoHello h1 = new TwoHello("Tom", 3);
TwoHello h2 = new TwoHello("Clark", 2);
h1.start();
h2.start();
}
}

The fundamental difference between process and thread is that each process has its own memory space independent of other processes’ and all threads in the same share the same memory space. In other words, all thread in a process shared all global variables in the process. When two processes want to use memory for data exchange, they must ask the operating system to allocate a memory segment that is to be shared by the two processes.

Now let us take a look how we can use threads in real-time systems design. For the black line-tracing robot, we used a sequential program that polls the readings of the sensors, and based on them makes a decision on turns and then loops back. Now let us design the robot using threads. Assume there is an object; call it sensorState that stores the current readings of the two light sensors. Then logically a sensor monitor, call it SensorMonitor, can be used to read the sensors and store the values in sensorState. Reading sensor values and storing them in the object would the only responsibility of the SensorMonitor. We also need a driver that can read the sensor value (stored in sensorState, which is analogous to the dashboard of the car) and make turns. Let us call this driver MotorController. Its responsibility is also very straightforward, reading the sensor values from sensorState and then determines which way to go. There is another function that is used to stop the robot, a monitor to monitor whether a button (in this example, the LEFT button) is pressed or not. Once it is pressed, the robot should stop, i.e., stop the motors and turn off the sensors.

The following program implements this design with three threads. The SensorState class defines the sensor state. It declares two public data members for the values of the left and right sensors, so they can be accessed directly by the motor controller and sensor monitor.

// SensorState
class SensorState {
publicint left;
publicint right;
public SensorState(int l, int r)
{
left = l; right = r;
}
}
publicclassMotorControllerextends Thread {
privatestaticfinalint BLACK_COLOR = 5;
privatestaticfinalint MOTOR_SPEED = 60;
private SensorState sensorState;
private Motor left, right;
publicMotorController(SensorState ss, Motor left, Motor right) {
this.sensorState = ss;
this.left = left;
this.right = right;
left.setSpeed(MOTOR_SPEED);
right.setSpeed(MOTOR_SPEED);
}
publicvoid run() {
try {
LCD.clear(); /* Clear the LCD display */
while (true) {
if (!isBlack(sensorState.left) & !isBlack(sensorState.right)) {
left.forward();
right.forward();
display(sensorState, "forward");
} elseif (isBlack(sensorState.left) & !isBlack(sensorState.right)) {
left.forward();
right.stop();
display(sensorState, "turn left");
} elseif (!isBlack(sensorState.left) & isBlack(sensorState.right)) {
left.stop();
right.forward();
display(sensorState, "turn right");
} else {
left.forward();
right.forward();
display(sensorState, "forward - LOST");
}
Thread.sleep(4);
if (isInterrupted()) {
stopMotors();
break;
}
}
} catch (Exception e) {
}
}
privateboolean isBlack(int color) {
if (color < BLACK_COLOR)
returntrue;
else
returnfalse;
}
privatevoid display(SensorState s, String dir) {
LCD.clear();
LCD.drawString(dir, 1, 5);
LCD.drawInt(s.left, 1, 6);
LCD.drawInt(s.right, 1, 7);
}
publicvoid stopMotors() {
left.stop();
right.stop();
}
publicstaticvoid main(String args[]) throws InterruptedException {
SensorState ss = new SensorState(99, 99);
ColorSensor leftSensor = new ColorSensor(SensorPort.S1);
ColorSensor rightSensor = new ColorSensor(SensorPort.S2);
SensorMonitor monitor = new SensorMonitor(ss, leftSensor, rightSensor);
monitor.start();
MotorController tracer = newMotorController(s, Motor.A, Motor.B);
tracer.start();
ButtonMonitor buttonMonitor = new ButtonMonitor(monitor, tracer);
Button.LEFT.addButtonListener(buttonMonitor);
}
}
import lejos.nxt.addon.*;
class SensorMonitor extends Thread {
private SensorState sensorState;
private ColorSensor left;
private ColorSensor right;
public SensorMonitor(SensorState ss, ColorSensor left, ColorSensor right) {
this.left = left;
this.right = right;
this.sensorState = ss;
}
publicvoid run() {
try {
while (true) {
sensorState.left = left.getColorNumber();
sensorState.right = right.getColorNumber();
sleep(25);
if (isInterrupted()) {break;}
}
Thread.sleep(2);
}
catch (Exception e) {}
}
}
import lejos.nxt.Button;
import lejos.nxt.ButtonListener;
class ButtonMonitor implements ButtonListener {
private SensorMonitor monitor;
privateMotorController tracer;
public ButtonMonitor(SensorMonitor monitor, MotorController tracer) {
this.monitor = monitor;
this.tracer = tracer;
}
publicvoid buttonPressed(Button b) {
tracer.interrupt();
monitor.interrupt();
}
publicvoid buttonReleased(Button b) {
}
}

5Scheduling and Priority Assignment

LeJOS employs a preemptive priority-based scheduling algorithm for threads. There are 10 different priority levels from 1 to 10 with 10 as the highest priority. With preemptive priority scheduling, when a thread with a higher priority than the current running thread is ready for execution, it preempts the execution of the current running thread and takes the CPU. For threads with same priority, LeJOS employs the round-robin scheduling algorithm (The size of time quantum is unknown.) Each thread runs for up to one time quantum. If it does not release the CPU by the end of the allocated time quantum, LeJOS preempts its execution and selects next thread of the same priority for execution for up to a new time quantum.

The Thread class provides following methods for priority control.

1. public final int getPrioity(); return the priority of the thread, and

1. public final void setPriority(int newPriority); sets the priority of the thread to newPriority. It throws IllegalArgumentException if newPriority is not in the range of [MIN_PRIORITY=1, MAX_PRIORITY=10] inclusive. When a child thread is created, the child inherits the parent thread’s priority.

The Thread class also provides methods for scheduling control.

1. public static void sleep(long milliseconds) throws InterruptedException; puts the calling thread to sleep for at least milliseconds. The “at least” here means that the thread may not wake up and/or execute in the exact specified time. (Why?)

When a thread is in sleep, it no longer competes for CPU time until it wakes up. If the thread is interrupted (interrupts will be discussed shortly) while it is in sleep, an InterruptedException will be thrown and the thread wakes up and returns from sleep(). InterruptedException must be caught or re-thrown by the function in which sleep() is invoked.

1. public static void sleep(long milliseconds, int nanoseconds) throws InterruptedException; is the same as the above sleep method exception that this method can specify the number of nanoseconds to be delayed in addition to the specified milliseconds. Nanoseconds must be in the range of [0, 999999] inclusive.

1. public static void yield(); causes the calling thread to yield or release the CPU so that other runnable threads with the same priority level can have a chance using the CPU. The yielding thread may acquire the CPU right away it is the only thread in its priority level.

To determine the priority for each thread we need to determine the criticalness and urgency of each thread in relation to other threads. For the line tracing robot, ButtonMonitor should have the highest priority among the threads is because, when the button is pressed, we don’t wish the robot to move any further so it should be executed whenever it is ready or the button is pressed. SensorMonitor should have the second highest priority since we want the MotorController to use latest readings from the sensors. MotorController has the lowest priority among the three. ButtonMonitor, SensorMonitor, and MotorController have the priority assigned 10, 9, and 8, respectively. The following code segment shows the modified version of the main() method of the MotorController class.

public static void main(String args[])
throws InterruptedException {
SensorState ss = new SensorState(99, 99);
SensorMonitor monitor =
new SensorMonitor(ss, Sensor.S1, Sensor.S2);
monitor.setPriority(9);
monitor.start();
MotorController tracer =
new MotorController(ss, monitor);
tracer.setPriority(8);
tracer.start();
ButtonMonitor buttonMonitor =
new ButtonMonitor(monitor, tracer);
Button.LEFT.addButtonListener(buttonMonitor);
}

Observant readers may have noticed that the ButtonMonitor’s priority is not set in the code shown above. Then how is it done? The point I am trying to make here is that, when we design real-time applications, we must know how the underlining operating system (in our example, LeJOS) works and what the operating system provides us as system designer and implementer. LeJOS executes all event listeners in a thread at the highest priority (MAX_PRIORITY = 10) when the listened event occurs. Thus, although the above code does not set ButtonMonitor’s priority, its buttonPressed() method will be executed as a thread with the highest priority by LeJOS, the underling operating system.

6The Double Buffer Technique

The program shown above seems work fine at first look. However, with further inspection, we will find that MotorController may not always use the sensor readings correctly. The SensorMonitor has a higher priority than MotorController, and so it may preempt the execution of MotorController. When such a preemption occurs right after MotorController had just read the left sensor value and before the right sensor, MotorController would use a value of the left sensor that gathered 25 milliseconds earlier than the right sensor. The following diagram illustrates how this may happen.

MotorControllerSensorMonitor time

SensorState.left = left.getColorNumber();
SensorState.right = right.readValue();
// do something
isBlack(sensorState.left)
(1st part of the while condition)
SensorState.left = left.readValue();
SensorState.right = right.getColorNumber();
isBlack(sensorState.left)
(2nd part of the while condition)

At time t1 (on the right side) SensorMonitor read the readings and stored them in SensorState. When MotorController executed its second while loop sometime after t1, it checked the left sensor value first which was gathered at t1, and before it checked the right sensor value, it is preempted by SensorMonitor at t2, which read a new pair of sensor readings. When MotorController got the CPU back after t2, it checked the right sensor value, which was collected at t2. Thus the MotorController used the reading of the left sensor collected at t1 and the reading of the right sensor at t2.

There are at least three ways to solve the problem. One is called the double buffer technique, another is to use Java synchronized methods, and the last is to use semaphores, which will be discussed in next section. With the double buffer technique, instead of using one buffer for the shared data between two threads, two buffers and a flag are used and the flag is used to indicate which thread is to use which of the two buffers.

The following shows a modified version of the SensorState. It contains an array of two buffers (buf[2]) for the two buffers and an integer variable, switch, to indicate which buffer the sensor monitor is supposed to store next pair of readings. Two methods are introduced, setValues(), for the sensor monitor to store new readings, and getValues(), for the motor controller to read the stored readings. The setValues() checks the value of switch to determine where to store the readings. The getValues() also checks the value of switch to find out which buffer it is supposed to read from, and after reading the values it changes switch to point to the other buffer. In essence, the sensor monitor would use the same buffer for new readings until the motor controller has used the other buffer.