1.1Java Multithreading
1.1.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 View button is pressed.
In this section we will discuss two different implementations of the software: sequential and concurrent implementations. We will use LejOS and Java for SE 532.
1.1.2A 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 search for 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 35). The third segment is to make necessary turns based on the readings of the light sensors to follow the black line found in the second segment. This is a done with a while loop, and at the end of each loop it reads the status of the Run button. If the button is pressed, it turns off the motors and sensors and terminates the execution.
import josx.platform.rcx.*;public class Tracer implements ButtonListener {
private static final int BLACK_COLOR = 35;
private static final int MOTOR_SPEED = 7;
private int color1 = 0;
private int color2 = 0;
private boolean running = true;
public static void main(String args[]) throws InterruptedException {
Tracer roboDemo = new Tracer();
}
public Tracer() throws InterruptedException {
// First segment: initialization
Sensor.S1.setTypeAndMode(SensorConstants.SENSOR_TYPE_LIGHT,
SensorConstants.SENSOR_MODE_PCT);
Sensor.S1.activate();
Sensor.S2.setTypeAndMode(SensorConstants.SENSOR_TYPE_LIGHT,
SensorConstants.SENSOR_MODE_PCT);
Sensor.S2.activate();
Button.RUN.addButtonListener(this);
LCD.clear(); /* Clear the LCD display */
Motor.A.setPower(MOTOR_SPEED);
Motor.B.setPower(MOTOR_SPEED);
// second segment: search for the black line
color1 = Sensor.S1.readValue();
color2 = Sensor.S2.readValue();
while (color1 > BLACK_COLOR & color2 > BLACK_COLOR) {
TextLCD.print("srch");
Motor.A.backward();
Motor.B.forward();
color1 = Sensor.S1.readValue();
color2 = Sensor.S2.readValue();
Thread.sleep(100);
}
// third segment: follow the black line.
while (true) {
while (running) {
color1 = Sensor.S1.readValue();
color2 = Sensor.S2.readValue();
if (color1 <= BLACK_COLOR & color2 <= BLACK_COLOR) {
Motor.A.backward();
Motor.B.forward();
TextLCD.print("fwrd");
}
else if (color1 <= BLACK_COLOR) {
Motor.A.forward();
Motor.B.forward();
TextLCD.print("left");
}
else {
Motor.A.backward();
Motor.B.backward();
TextLCD.print("rght");
}
Thread.sleep(50);
}
TextLCD.print("stop");
Thread.sleep(100);
}
}
public void buttonPressed(Button b)
{
if (!running) {
running = true;
}
else {
stopMotors();
}
}
public void buttonReleased(Button b) {}
private void stopMotors() {
running = false;
Motor.A.stop();
Motor.B.stop();
}
}
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.
1.1.3A 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. A user-defined thread is normally a subclass of Thread. The most important method of Thread is run(), which is to be overridden by the user-defined thread to the real work assigned to it. 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, that 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 start() methods.
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++) {
TextLCD.print(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();
}
}
After a new thread is created, the parent and the child threads execute in the same memory space. In other words, global variables are all accessible to both threads.
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 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 View 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.
/**import josx.platform.rcx.*;
class SensorState {
public int left;
public int right;
public SensorState(int l, int r)
{
left = l; right = r;
}
}
class SensorMonitor extends Thread {
private SensorState sensorState;
private Sensor left;
private Sensor right;
public SensorMonitor(SensorState ss, Sensor left, Sensor right) {
this.left = left;
this.right = right;
this.sensorState = ss;
left.setTypeAndMode(SensorConstants.SENSOR_TYPE_LIGHT,
SensorConstants.SENSOR_MODE_PCT);
left.activate();
right.setTypeAndMode(SensorConstants.SENSOR_TYPE_LIGHT,
SensorConstants.SENSOR_MODE_PCT);
right.activate();
}
public void run() {
try {
while (true) {
sensorState.left = left.readValue();
sensorState.right = right.readValue();
sleep(25);
if (isInterrupted()) {break;}
}
}
catch (Exception e) {}
}
public void stopSensors() {
left.passivate();
right.passivate();
}
}
public class TracerThread extends Thread {
private static final int BLACK_COLOR = 35;
private static final int MOTOR_SPEED = 7;
private SensorState sensorState;
private Motor left, right;
public TracerThread(SensorState ss, Motor left, Motor right)
{
this.sensorState = ss;
this.left = left;
this.right = right;
left.setPower(MOTOR_SPEED);
left.setPower(MOTOR_SPEED);
}
public void run() {
try {
LCD.clear(); /* Clear the LCD display */
while (sensorState.left > BLACK_COLOR &
sensorState.right > BLACK_COLOR) {
TextLCD.print("srch");
left.backward();
right.B.forward();
Thread.sleep(100);
}
while (true) {
if (sensorState.left <= BLACK_COLOR &
sensorState.right <= BLACK_COLOR) {
left.backward();
right.forward();
TextLCD.print("fwrd");
}
else if (sensorState.left <= BLACK_COLOR) {
left.forward();
right.forward();
TextLCD.print("left");
}
else {
left.backward();
right.backward();
TextLCD.print("rght");
}
Thread.sleep(25);
if (isInterrupted()) {
break;
}
}
}
catch (Exception e) {}
}
public void stopMotors() {
left.stop();
right.stop();
}
public static void main(String args[])
throws InterruptedException {
SensorState sensorState = new SensorState(99, 99);
SensorMonitor monitor =
new SensorMonitor(sensorState, Sensor.S1, Sensor.S2);
monitor.start();
TracerThread tracer =
new TracerThread(sensorState, Motor.A, Motor.B);
tracer.start();
ButtonMonitor buttonMonitor =
new ButtonMonitor(monitor, tracer);
Button.VIEW.addButtonListener(buttonMonitor);
}
}
class ButtonMonitor implements ButtonListener {
private SensorMonitor monitor;
private TracerThread tracer;
public ButtonMonitor(SensorMonitor monitor, TracerThread tracer) {
this.monitor = monitor;
this.tracer = tracer;
}
public void buttonPressed(Button b)
{
tracer.stopMotors();
tracer.interrupt();
monitor.stopSensors();
monitor.interrupt();
}
public void buttonReleased(Button b) {}
}
1.1.4Scheduling 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 allocation time quantum, LeJOS preempts its execution and select next thread of the same priority for execution for up to a new time quantum.
The Thread class provides following methods for priority control.
- public final int getPrioity(); return the priority of the thread, and
- 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.
- 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 (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.
- 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.
- 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 TracerThread class.
public static void main(String args[])throws InterruptedException {
SensorState sensorState = new SensorState(99, 99);
SensorMonitor monitor =
new SensorMonitor(sensorState, Sensor.S1, Sensor.S2);
monitor.setPriority(9);
monitor.start();
TracerThread tracer =
new TracerThread(sensorState, monitor);
tracer.setPriority(8);
tracer.start();
ButtonMonitor buttonMonitor =
new ButtonMonitor(monitor, tracer);
Button.VIEW.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) 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 with the highest priority by LeJOS, the underling operating system.
1.1.5The 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, 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 what may happen.
MotorControllerSensorMonitor timeSensorState.left = left.readValue();
SensorState.right = right.readValue();
// do something
SensorState.left < 35
(1st part of the while condition)
SensorState.left = left.readValue();
SensorState.right = right.readValue();
SensorState.right <35
(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. For the program to work, it is obvious MotorController and SensorMonitor both need to be modified to accommodate the changes made to SensorState.
class Buffer {public int left;
public int right;
}
class SensorState {
public Buffer buf[2];
private int switch;
SensorState(int left, int right) {
buf[0] = new Buffer();
buf[1] = new Buffer();
buf[0].left = buf[1].left = left;
buf[0].right = buf[1].right = right;
this.switch = 0;
}
public void setValues(int left, int right) {
if (switch == 0) {
buf[0].left = left;
buf[0].right = right;
}
else {
buf[1].left = left;
buf[1].right = right;
}
}
public void getValues(Buffer buf) {
if (switch == 0) {
buf.left = buf[1].left;
buf.right = buf[1].right;
}
else {
buf.left = buf[0].left;
buf.right = buf[0].right;
}
switch = (switch + 1) % 2;
}
};
1.1.6Monitors and Java Synchronized Methods
The double buffer solution ensures that the motor controller always uses a pair of sensor readings that are gathered at the same time. However, it may not always use the pair of the most recent readings. Why?
Java implements the high-level synchronization primitive called monitors, proposed by Hoare and Brinch Hansen. A monitor consists of procedures and data members and it can only be accessed through its procedures. One critical property monitors have is that the procedures of the monitor can be executed by only one thread at a time. If another thread tries to call a procedure it has to wait until the thread completes the procedure. In other words, each monitor has a lock. When a thread tries to execute a procedure, the lock is checked. If the lock is not locked, then the thread locks the lock and then executes the procedure and possibly other procedures as well. If the lock is locked, then the calling thread is put to sleep on the monitor’s lock. When the thread, which possesses the lock, completes the procedure, it unlocks the lock and one of the waiting threads may acquire the lock and execute the procedure. Thus mutual exclusion to the access to a monitor is achieved by only allowing one thread to execute procedures of the monitor at a time.
Java implements monitors by using synchronized methods and private data members. To make objects of a Java class monitors we can declare its data members private to ensure they are not accessible directly by clients and qualify its methods with the keyword synchronized to ensure that they can only be executed mutually exclusively by one thread at a time. Like monitors, an object has a lock for all synchronized methods. The thread that first tries to execute a synchronized method acquires the lock and all other threads that try to execute any synchronized method of the object have to wait until the lock is unlocked. Please note that a thread may execute a non-synchronized method of the object no matter whether another thread possesses the lock of the object or not. Thus, if one wishes all methods of an object to be mutual exclusive, then one must declare all the methods synchronized.