In this Chapter we introduce what has been up to now considered a very advanced topic. Real computer systems today run so fast that they can devote small bits of time to many users in quick succession and it seems as if the entire computer is dedicated to each user. Even more interesting, they can let several "processes" operate with seeming simultaneity for each user. This is called concurrent programming and we will introduce it here, with some of its pitfalls.
When a program is to run several pieces at the same time, the individual parts are called threads (threads of control). Each thread in a robot program is just like a task: a sequence of robot instructions executed one after the other until the end. We can make a task run in its own thread quite easily. Suppose we again take up the house building task of Chapter 4.
The one of our Carpenter robots needed to make two windows. Suppose we write a task function to do just this. This can be a static method of our Main class.
public static void carpenterTask()
{ Carpenter Linda = new Carpenter(1, 1, North, infinity);
Linda.moveToFirstWindow();
Linda.makeWindow();
Linda.moveToNextWindow();
Linda.makeWindow();
}
We next need to create a Runnable class that can be used to control a thread. Such a class implments the Runnable interface and has a run method.
class CarpenterRunner implements Runnable
{ public void run()
{ Main.carpenterTask();
}
}
We could have actually avoided writing the carpenterTask method and just put its statements into this run method.
Finally, from our main task function we need to create a new CarpenterRunner and tell the world to run it in a new thread.
public static void main(String [] args)
{ …
CarpenterRunner r = new CarpenterRunner();
World.setupThread(r);
…
}
Now this task will run in its own thread along with other threads that we start in the same way. This same thread could be used to control one or more robots. Each thread behaves like an independent main task block, but, of course, all such threads run in the same world. If we make several such threads for our house building task, it will seem like the workers are working all at once.
One especially nice way to make concurrent robot programs is to let each robot be controlled by its own thread. Each robot then behaves much more like an independent being than has been possible up to now. This is like the helicopter pilot reading a robot's messages to it all at once and then setting it on its way, rather than reading one message at a time and waiting for it to complete.
One simple example is to write a class of robots that can race each other to some goal. For example, suppose we start a Racer robot on 1st street and 1st avenue and another on 2nd street and 1st avenue. Both robots face East. Somewhere in front of each is a beeper. We start them up simultaneously, each in its own thread and see who gets there first.
To arrange this, we are going to do two things differently in the Racer class. We are going to tell the World to run this robot in its own thread and we are going to give the class its own run method. (Note that ur_Robot itself implements the Runnable interface, which is what makes this possible.)
class Racer extends Robot
{ public Racer(int Street, int Avenue, Direction direction, int beepers)
{ super(Street, Avenue, direction, beepers);
World.setupThread(this);
}
public void race()
{ while(! nextToABeeper())
move();
pickBeeper();
turnOff();
}
public void run()
{ race();
}
}
Then, all we need to do in the main task block is to create our robots. We don't actually even need to name them, but we will here.
public static void main(String [] args)
{ Racer first = new Racer(1, 1, East, 0);
Racer second = new Racer(2, 1, East, 0);
}
They will automatically start themselves up, since we told the world to run them in the Racer constructor.
Robots have a very rudimentary way to communicate with each other. They can meet on a corner and exchange beepers. This can be the basis of sophisticated programs. Here we show part of a simple relay race in which three robots exchange a beeper (the baton) when the first runs up to the second and the second then runs up to the third.
public class RelayRacer extends Robot
{ public RelayRacer(int street, int avenue, Direction direction, int beepers)
{ super(street, avenue, direction, beepers);
World.setupThread(this);
}
public void run()
{ while(!nextToABeeper())
{ spin();
}
pickBeeper();
runToRobot();
putBeeper();
turnOff();
}
private void spin()
{ turnAround();
turnAround();
}
private void turnAround()
{ turnLeft();
turnLeft();
}
private void runToRobot()
{ move();
while(! nextToARobot())
{ move();
}
}
}
If we start one of these on a corner that contains a beeper, facing down a street that contains another of these then the relay will begin properly. You will need to do some additional things to make it end properly, however.
When threads run concurrently it is usually impossible to predict the order of operations of the individual instructions in different threads. This sometimes leads to undesirable effects in which two things happen in the wrong order. It is generally difficult to reason about the interleaving of concurrent operations because there are so many possibilities. This needs to be carefully controlled. For example, if two computers are connected to the same printer, and the print driver on each isn't careful, it would be possible for two users to print at about the same time and have the individual characters of the two documents interleaved on the output. The usual method of controlling this kind of thing is to have a queue that holds requests to print. A newly arriving print request is put into the back of the queue and the printer takes requests from the front. Eventually each request works its way to the front and gets printed. But, if the print driver isn't careful and two print requests arrive at about the same time, the print queue can get corrupted.
In this section we are going to illustrate one classic problem with concurrency, called race conditions. Since we are using robots we can do this by actually holding races. The term however, applies whenever the interleaving of operations can cause something to happen at an unexpected time.
Suppose we take our Racer robots of Section 8.2 and make them race to pick up the same beeper. We can start one at 10th street and 1st avenue and the other at 1st street and 10th avenue, racing for a single beeper at the origin. We don't know which will reach the beeper first and pick it up. But the other will slam into the end wall, since it won't see any beeper at all. The first robot to get there will pick it up. Since we aren't going to be sending any messages to these robots, we won't even name them. They will be anonymous.
public static void main(String [] args)
{ new Racer(10, 1, South, 0);
new Racer(1, 10, West, 0);
}
Actually, it is possible for both robots to arrive at about the same time and each check to see if there was a beeper there and each find that there was and only then, each try to pick it up. Thus, one of them would do an error shutoff while trying to pick up a beeper that it just checked for and found, rather than when trying to walk through a wall.
Here is another example, contributed by Byron Weber Becker of University of Waterloo.
public class BadThreadRobot extends Robot
{ public BadThreadRobot(int street, int avenue, Direction direction, int beepers)
{ super(street, avenue, direction, beepers);
World.setupThread(this);
}
public void run()
{ pickBeeper();
move();
for(int i=0; i<10000; i++)
{ turnLeft();
turnLeft();
if (nextToABeeper())
{ pickBeeper();
} else
{ putBeeper();
}
move();
turnLeft();
turnLeft();
move();
Thread.yield(); // May not be needed.
}
move();
turnOff();
}
}
Notice that if such a robot successfully picks up a beeper from the first corner, then it should execute to completion with no errors. Assuming a robot can pick up a beeper from its starting corner, it then goes to another corner and either takes a beeper or leaves a beeper depending on whether or not one is already there. It then leaves, comes back and checks again. One robot will execute this just fine. When a second robot is introduced, however, it can "steal" a beeper from the corner between the time the other robot checks and actually picks it up. The other robot then performs an error shutoff.
To see this happen, create two such robots and arrange them so that they will
meet on the same corner to place their beepers.
World.placeBeepers(2,3,1); World.placeBeepers(3,4,1); new BadThreadRobot(2, 3, East, 0); new BadThreadRobot(3, 4, South, 0);
This is nearly guaranteed to fail as you can see by trying it.
Another classic concurrency problem is deadlock. This occurs when different threads hold some resources (say a beeper) that the other threads need and each waits (forever) for the others to release the resource. One classic illustration of this is called Dining Philosophers.
In the traditional story we have a group of philosophers who alternately think and eat. Each has a place at the table and between each pair of places there is a fork. Each philosopher will think for a while and then decide it wants to eat. To do so, however requires picking up both forks by its place, one at a time. If it doesn't get a fork it waits for the philosopher next to it to put down that fork and then it picks up the fork and continues. When it finishes, it puts down its forks, again, one at a time.
The problem arises when each philosopher has picked up its left fork and reaches for the right one. Each will wait for a fork and none will put one down. This is deadlock. Here is a class that illustrates this example. Note, that it won't deadlock every time. Also note that the run method in the class never ends. You will have to stop the program yourself.
public class Philosopher extends AugmentedRobot
{ public Philosopher(int street, int avenue, Direction direction)
{ super(street, avenue, direction, 0);
World.setupThread(this);
}
public void run()
{ while(true)
{ think(d.roll());
getForks();
eat(d.roll());
putForks();
}
}
private void think(int time)
{ for(int i = 0; i < time; ++i)
{ backUp();
move();
}
}
private void eat(int time)
{ for(int i = 0; i < time; ++i)
{ move();
backUp();
}
}
private void getForks()
{ turnLeft();
move();
while(! anyBeepersInBeeperBag())
{ while(! nextToABeeper()) ; // nothing
pickBeeper();
}
turnAround();
move();putBeeper();
move();
while(! anyBeepersInBeeperBag())
{ while(! nextToABeeper()) ; // nothing
pickBeeper();
}
turnAround();
move();
putBeeper();
turnRight();
showState("Eat ");
}
private void putForks()
{ pickBeeper();
pickBeeper();
turnLeft();
move();
putBeeper();
turnAround();
move();
move();
putBeeper();
turnAround();
move();
turnRight();
showState("Think ");
}
private Die d = new Die(6);
}
The Die class isn't shown here, but it simulates
the rolling of a single die (one of a pair of Dice) to achieve randomization.
Thus, the philosophers seem to eat and think for random periods of time. To start
up the simulation, you need to say something like:
public static void main(String [] args)
{ World.placeBeepers(2, 2, 1);
World.placeBeepers(2, 4, 1);
World.placeBeepers(4, 2, 1);
World.placeBeepers(4, 4, 1);
Philosopher p1 = new Philosopher(2, 3, North);
Philosopher p2 = new Philosopher(3, 2, East);
Philosopher p3 = new Philosopher(4, 3, South);
Philosopher p4 = new Philosopher(3, 4, West);
}If you make the Die one or two sided instead of six sided you greatly increase the chance of deadlock.
NOTE that the AugmentedRobot just provides some simple methods like turnRight and turnAround that we commonly use.
concurrent
race condition
deadlock
thread
1 Run a super duper steeplechase relay race with three robots that run in concurrent threads. See problem 6.11 and problem 6.27.
2. Have two sets of three robots each race against each other in a super duper steeplechase relay tournament.
3. Do Problem 9 of Chapter 4 again, where the two Spy robots run in different threads.
4. Do Problem 11 of Chapter 4 again, where each of the four robots runs in a separate thread.
5. Repeat Problem 4, except that each robot starts at an arbitrary location and each runs in a separate thread. They rendezvous at the origin to exchange strategies.