In this Chapter we discuss concurrent programming again and show additional problems and how to overcome them.
Suppose that we have two robots Karel and Carol, each running in its own thread. Suppose that Karel sends a message to Carol. If we give the name KT to the thread that is executing Karel and CT to the one executing Carol, then the question arises which thread executes the method named in the message. The answer may be surprising at first, but understanding this is very important. Threads are a concept totally unrelated to object-orientation and therefore unrelated to our class structure. Threads execute code, not robots.
We, in effect, have two computers, one that we first hand to Karel and the other to Carol. Karel uses its computer to execute the code of its run method, and Carol does likewise. When we send any message, the computer follows the message path, so that the receiver of the message has a computer on which to execute the named method. When the method returns, the computer is passed back to the sender, along with any result.
This means that when Karel sends Carol a message, there are two computers simultaneously executing Carol's code. One (CT) is perhaps executing Carol's run method, and the other (KT) is executing some method of Carol's. However, from Carol's run method we may call, for example, other methods of Carol. This implies that we could have two computers executing the same method of Carol at the same time. If that method manipulates Carol's instance variables we can have serious problems, just as we had serious beeper problems in Chapter 8.
Imagine an account object that maintains information about a bank account. This will probably have a method public void deposit(Money m). Internally this method will need to get the current value of the account, add the amount m to it, and store the new sum as the current value. But this takes three steps. Suppose that we let two threads have simultaneous access to this method, perhaps because two different account owners make deposits at the same time from different ATM machines. Each thread could approximately simultaneously get the current value. Each could approximately simultaneously compute a new sum. Then each could approximately simultaneously write back that sum as the current value. Note that only one of the deposits would then be recorded, since each of these "transactions" started with the same current value.
If we are going to write safe concurrent programs we need to prevent such "race conditions" from occurring. We want the actions to be "serialized" somehow. In the account example, we want the system to behave in such a way that one of the deposits is completed before the other is begun.
In Java, one means of guaranteeing that multi threaded code performs correctly is to synchronize the methods. This is very easy to do, but has some consequences. The deposit method would be defined as follows.
public synchronized void deposit(Money m) { Money cv = getCurrentValue(); Money newValue = cv.addMoney(m); setCurrentValue(newValue); }
Synchronizing the method will guarantee that only one thread will be allowed to execute this code at the same time. Actually, it guarantees a bit more. It says that only one thread will be allowed to execute any synchronized method of this object at the same time. Other, non synchronized, methods can be executed simultaneously, however. A thread denied access will wait until the thread currently executing that code releases the lock it holds on the object.
If all methods of a class are synchronized and if all instance variables are private, then we can guarantee that only one thread can execute any of the code of the object at the same time. In fact, if we synchronized all methods of Carol, including its run method, then the Karel thread, KT, would wait forever (or at least until the run method of Carol terminates).
It is important to note that if we didn't synchronize deposit, but we did synchronize getCurrentValue, addMoney, and setCurrentValue, then we would not have prevented the transaction anomaly discussed earlier. We could still have the situation of a lost deposit. The problem isn't to prevent those individual parts to be executed one at a time, it is to prevent one of the transactions from getting a value until the other has written its new value. Therefore, how much we need to include in our synchronized methods depends on the problem at hand.
We should note that the main methods of UrRobot, such as move and pickBeeper are not synchronized, though the methods of the World that maintain information about beepers and such are synchronized.
In the Carol/Karel example of the previous Section, suppose all methods of Karel are synchronized, including the run method, and all methods of Carol are also. Suppose that Carol tries to send Karel a message. Then Carol will be stuck waiting--especially if the Karel run method is an infinite loop. If Karel then tries to send Carol a message, we will have the classic situation of deadlock. Each robot holds something that the other wants (the lock) and neither knows enough to give up its lock to let the other proceed. Those two threads, and therefore, perhaps, our entire program will simply stop making progress. Needless to say, this is a very undesirable situation.
Another deadlock situation can be made to occur frequently. Suppose that a non-synchronized method calls two synchronized methods of two objects x and y, say x.A(), and y.B(), in that order. Suppose another non-synchronized method calls the same two methods of the same two objects in the opposite order. If these two methods are called at about the same time by different clients, then deadlock could occur. One client will obtain a lock on x when it calls it's A method and the other will hold a lock on y from sending it the B message. Then each of these client threads will attempt to obtain the other lock. This will be deadlock and the two threads will stop making progress.
Once deadlock occurs, nothing will break it. The program will need to be halted and fixed. The programmer needs to prevent it by careful coding. One way to prevent deadlock is to guarantee that if any method must call two different synchronized methods, that all such methods do so in the same order. Deadlock would not occur if we had not switched the order of messages in the previous example. The second client would hold no locks, so the first could proceed. When it completed, the second could begin.
The easiest way to prevent deadlock is to prevent cross thread communication at all. If one thread is executing robot Karel, then no messages should be sent to Karel from other threads. If each robot is executing in its own thread, then no robot can send a message to any other robot. This is simple, but makes some problems very difficult to solve, as it seems to prevent any inter-robot communication.
So far we have seen two ways for robots to communicate. One is by sending messages, when one robot asks another to perform a service by asking it to execute one of its methods. The other way is indirectly through exchanging beepers on a corner. But there is a third way. We can use Java I/O facilities to establish a channel of communication between any two robots. The UrRobot class has some special methods to help with this.
A channel is a one-way communication link, sort of like a one-way phone line, by which one robot (or any object, actually) can send information to another. We shall set up channels which can be used to send String "messages" from one robot to another. Here, the word message is used in a completely different way from the usual meaning in object-oriented programming. This new message terminology comes from the theory and practice of concurrent programming. For us a message will just be a String that is passed from a sender to a receiver.
However, before the message can be passed, the channel must be established. For this to occur, the sender must have a reference to the receiver and must connect to it by calling its own connectTo method. This method is uses synchronized calls, so that many different robots, executing on many different threads, can safely execute it simultaneously. If aReceiver is another robot we can say:
BufferedWriter writer = connectTo(aReceiver, aStrategy);
This will internally ask aReceiver to accept a connection from this robot. The robot aReceiver will remember the connection. As indicated in the sample, the connectTo method returns a BufferedWriter to the calling robot. Here we save it in a variable named writer. (We will discuss the strategy parameter in the next section. For now assume it is null.)
Once the connection is established, the sender can write into the BufferedWriter and the receiver will be able to read the results from its own end, which will be a BufferedReader.
writer.write("Hello");// Don't do this.
However, the above will not guarantee that the message will be received, since the receiver is expecting full lines, and the above doesn't provide the end of line, nor does it necessarily actually send the message immediately, because of the buffering. The sender normally communicates with the receiver by calling its own send method, naming the BufferedWriter associated with the channel, and giving the String it wants sent.
send(writer, "Hello");
This will append an end of line to the communication, and flush the writer, forcing it to send the communciation. Note, that like the write method, the send method needs to be guarded by a try block since either can throw the IOException. This is because the channel might fail in some way.
There are a number of different ways to receive a communication. If we need to process the senders one at a time in strict rotation, the receiver can call waitForNextCommunciation. This method will return a String, which will be null if there are no senders connected, but will otherwise be the next communication from the next sender. The receiver will wait until this communication arrives if it isn't already there.
If you want to wait until some communication comes in, but you don't care from which sender, you can call waitForCommunication, which again will return null if there is no connected sender, but will otherwise block until some sender provides a communication.
Note, however, that if a receiver is blocked waiting for communication, and the sender closes the channel rather than writing to it, the receiver will be released from its block and will get a null string for its message.
Finally, you can ask to getNextCommunication, which will never block and will return a communication if available at that time, and null otherwise.
The receiver can do whatever it likes with the incoming message. Therefore, to be useful, the sender and receiver will need to agree on some protocol for interpreting the messages.
In this simple system, there is no way for the receiver to send a message back to the sender, though another channel in the other direction could be established if the receiver has a reference to the sender from which to set it up. Actually, the message (object-oriented, method invocation message) sent to the receiver when the connectTo method is called actually passes a reference to the sender along with the call, so this can be arranged when needed, though a method acceptConnectionFrom, will need to be overridden to achieve this.
What follows is a partial definition of a Mimic robot that can be sent messages about how to behave and it will obey them. Any robot that connects to such a robot can send it move, turn and shut messages and it will move, turnLeft, and turnOff, respectively.
public class Mimic extends AugmentedRobot
{ public Mimic(int street, int avenue, Direction direction, int beepers)
{ super(street, avenue, direction, infinity);
if(World.delay() == 0) World.setDelay(1); // May not run well at fastest speed.
World.setupThread(this);
}
public void run()
{ String res;
while (true)
{ if((res = waitForNextCommunication()) != null)
{ System.out.println(res);
putBeeper();
if(res.equals("move"))
move();
else if (res.equals("turn"))
turnLeft();
else if (res.equals("shut"))
turnOff();
}
Thread.yield();
}
}
}
The run method is an infinite loop that listens for incoming messages and interprets them and behaves accordingly. It ignores null messages and those not in its known list of commands.
To use this class, you must first create a new Mimic, giving it a name. Then pass this name (reference variable) to another robot which will execute the connectTo method. Then that other robot can direct the Mimic however it likes. Recall that one way for a robot to get a reference to another is to arrange for them to meet on the same corner and then one can execute its own neighbors() method. This was discussed in Chapter 4.
Here is an example of a class that can be used to control a Mimic. It is very much like our Choreographer of Chapter 4. We give it only a simple (sample) run method.
class Master extends AugmentedRobot
{ public Master(Mimic s, int street, int avenue, Direction direction, int beepers)
{ super(street, avenue, direction, beepers);
if(World.delay() == 0) World.setDelay(1); // May not run well at fastest speed.
World.setupThread(this);
try{ buf = connectTo(s, null);}catch(IOException e){System.out.println("can't");}
}
public void run()
{
move();
move();
move();
turnRight();
move();
move();
move();
turnOff();
}
public void move()
{ super.move();
try{send(buf, "move");}catch(IOException e){System.out.println("error move");}
}
public void turnLeft()
{ super.turnLeft();
try{ send(buf, "turn");}catch(IOException e){System.out.println("error turn");}
}
public void turnOff()
{ super.turnOff();
try{ send(buf, "shut");}catch(IOException e){System.out.println("error shut");}
}
private BufferedWriter buf = null;
}
There is another means of controlling a Mimic or other receiver robot. Any client can send a receiver an acceptConnection message and that client will then be able to send messages to the receiver. In order to use this message (method) the client will first need to establish a new PipedOutputStream and pass this along with the method call. We will discuss the PipeeOutputStream class in the next section.
PipedOutputStream out = new PipedOutputStream(); aReceiver.acceptConnection(out); BufferedWriter write = = new BufferedWriter(out);
Now, this client, whether a robot or not, can communicate with aReceiver by writing to the BufferedWriter write. Actually, you could write directly to the PipedOutputStream or layer a different Writer on top of the PipedOutputStream as well. However, you must be careful to append newline characters '\n' to the outputs and to flush the writer as well.
Sometimes the connection strategies provided by the UrRobot class are not adequate for the problem at hand. They all assume that there may be many senders and that the receiver doesn't need to send messages back to the sender. However, the actual situation may be more complex, and the UrRobot class has a very flexible mechanism for permitting the programmer to tailor a connection strategy to the problem at hand.
There is an interface defined within the UrRobot class named ConnectStrategy. Thus its full name is UrRobot.ConnectStrategy. The definition of this interface follows:
public interface ConnectStrategy
{ public void action(UrRobot sender, UrRobot receiver, BufferedReader manager);
} // Note: sender may be null.
To implement this interface requires that a class implement the action method with the given parameters. A sender will create an object that implements this interface and will then pass it (second parameter) in a connectTo message. The action method of this object calls a predetermined method of the receiver class. This method can do anything it likes within the receiver.
For example. Suppose we want a receiver class, say AReceiver, to be able to accept only a single connection and reject all later ones. We can give the receiver class a method:
public void acceptIfFirst(UrRobot sender, BufferedReader manager)
{ if(mySender == null) mySender = manager;
}
When this is called, it saves a reference to a buffered reader only if it hasn't already done so.
Then, a potential sender can connect to this receiver by implementing a connect strategy that will call this method.
class FirstStrategy implements UrRobot.ConnectStrategy
{ public void action(UrRobot sender, UrRobot receiver, BufferedReader manager)
{ ((AReceiver)receiver).acceptIfFirst(sender, manager);
}
}
A new object of this type will be created and passed in the connectTo message by the sender.
Finally, the receiver listens only to its mySender buffered reader with something like the following run method:
public void run()
{ String res;
while (true)
{ if(mySender == null) break;
try
{ if((res = mySender.readLine()) != null)
{
... interpret res and act on it.
}
} catch(IOException e) {System.out.println("done");return;}
Thread.yield();
}
}
Note that the idea here is an example of a standard design pattern called the Strategy Pattern. It lets the programmer tailor an action to the current circumstances without having to decide before hand on all of the possible variations that might be needed.
The action method is general enough that the receiver can do some quite sophisticated things when necessary. In particular, it receives a reference to the sender. Therefore it could test the sender somehow to see if it would accept the connection. It can also send a connection message back to the sender, so that two way communication can be achieved when needed.
A channel between two robots is composed of two parts. Together they constitute a pipe, which is a one-way I/O communication link that can be used to connect two threads. The sender holds a PipedOutputStream and the receiver holds a PipedInputStream. These are connected together when the acceptConnectionFrom or acceptConnection messages are sent from the sender to the receiver. These two classes, from java.io. implement standard ideas from the UNIX operating system in which the output from one process can be "piped into" the input to another, thereby making the second automatically process the input from the first.
Within the receiver, a new PipedInputStream is wrapped with a BufferedReader and the result is saved in a java.util.vector object. The PipedInputStream is also connected to the PipedOutputStream of the sender, completing the pipe. A vector object is an expandable array that can hold references to many objects at the same time in a sequential structure with rapid access.
The WaitForNextCommunication asks each of the BufferedReader objects in the vector if it has any communication pending. If not, it goes on to the next, but returns the first communication that it finds there. If none have any messages to deliver, then null is returned instead.
We use PipedInputStreams and PipedOutputStreams here, rather than PipedReaders and PipedWriters, since the former provide a means of asking if there is information in the channel, which we need.
As shown in the Mimic class, a receiver wishing to wait for communciation from a sender can wait in a loop that ignores null communications. There is, however, no way to wait for a communication from a specific sender. The Thread.yield() call in the loop will prevent the thread that is waiting from using up too much time on the real CPU while it waits.
collision
channel
deadlock
synchronized
1. Write and test a program that will deadlock. You may need to set up the deadlock situation repeatedly in a small loop to get it to actually occur. Make your robots do something visible so that you can see when they deadlock. Spinning in place is a good choice for this.