MIT 6.096:

Introduction to Interactive Programming

Laboratory 2: Nodes and Channels

Contents

Pre-Lab

A. Finger exercises

Question 1: How many Objects have been created after each line of the following code? How many labels? (Assume thay are executed in order.)
  1. Object foo, bar, baz; Objects: 0 Labels: 3
  2. foo = new Object(); Objects: 1 Labels: 3
  3. bar = foo; Objects: 1 Labels: 3
  4. Object fee = foo; Objects: 1 Labels: 4
  5. baz = new Object(); Objects: 2 Labels: 4
  6. foo = baz; Objects: 2 Labels: 5
Question 2: Construct a Counter class which supports an increment method. Where does the Counter's initial value come from? Is it statically or dynamically determined?

The minimum amount of code you needed to write was:

public class Counter {
int i = 0;
public void increment() {
i++;
}
}
Though many of you recognized this wasn't particularly useful (how do you find out the value of your counter?) and write something closer to:
public class Counter {
private int i = 0; // Note the use of the keyword private
public void increment() {
i++;
}
public int getValue() {
return i;
}
}
In either case the initial value of the counter comes from the line int i = 0; This is a statically determined value. To dynamically determine the value, you could have written the following:
public class Counter {
int i;
// Using a constructor...
public Counter(int startInt) {
i = startInt;
}
public void increment() {
i++;
}
}

B. Check-In Questions

  1. Your class implements NodeBehavior. What does this mean? In particular, what methods must your class have?

    2. implements NodeBehavior means that the class I write promises (to anyone using my class) to have an act method with the following signature:
      public void act (InputChannel[] inputChannels,
      OutputChannel[] outputChannels);
  2. Give a Java expression whose value is a single Object taken from a single InputChannel. This expression should be written in terms of the parameter to act, i.e., inputChannels. Don't worry about all of the things that could go wrong. Also don't worry about which Object you're getting.

    3. Assuming I name my variables as above, the following will do:
      inputChannels[0].readObject()
    Let's break this statement up. inputChannels is an array with members of type InputChannel. Thus, inputChannels[0] is a single Object of type InputChannel. On this particular InputChannel, we call its readObject method. Since the return type of readObject is Object, that is this statement's return type, too.

    The above expression retrieves an Object successfully when inputChannels[0] is...

Things could go wrong if any of the assertions above is not true. This is if inputChannel[0] is...
To write objects, we can use the following (assuming all variables have been appropiately initilized. i.e., o should be an Object you have previously read):
    outputChannels[0].writeObject(o)
This list of things that can go wrong (and the remedy) is:
  1. Always choose the first input or output, even if it disabled, empty, or full.
  2. Rotate through available inputs and outputs in cyclical fashon. Do some operation whereby all inputs and outputs are chosen equally often.
  1. Will be unfair and will lead to poor overall behavior because only a limited subset of the available inputs or outputs are used. Some channels will always be empty, others always full. The advantage, of course, is that this option is easy to write up.
  2. Should be fair and lead to overall good network performance in most situations. However, if some channels have heavy traffic and others only light traffic, this strategy will not "learn" and you may see some backups. This is the strategy IntermediateNodeBehavior actually uses.

Laboratory

We will attempt to build up a fully functional class from the most basic to the most robust. To begin, we create the following class, which has the minimal code to produce a valid, working NodeBehavior. This class will both build and run, though it isn't very exciting because it doesn't even attempt to move packets.
package BinSort;
public BoringNodeBehavior implements NodeBehavior {
public void act(InputChannel[] inputChannels,
OutputChannel[] outputChannels) {
// act is empty.
}
}

Implementing strategy #1:

Now we try to implement strategy #1 from above. We will read from a single input, and write to a single output. Here's our first attempt:
package Binsort;
public Strategy1_1 implements NodeBehavior {

Object o; // storage for the object we will read/write

public void act(InputChannel[] inputChannels,
OutputChannel[] outputChannels) {
// first we try to read a packet, catching the
// necesssary exceptions
try {
o = inputChannel[0].readObject();
} catch (ChannelEmptyException e1) {
} catch (ChannelDisabledException e2) {}

// now we have a packet, so we try to write it.
try {
outputChannels[0].writeObject(o);
} catch (ChannelFullException e3) {
} catch (ChannelDisabledException e4) {
}
}

Alas, we find that while we seem to do okay in certain circumstances, our code can crash, eat packets, or create them. How can we fix this? Well, the first problem, our code can crash, is caused by the lines where we access the 1st element of the array (either the input or the output) whithout ensuring that that channel even exists! Imagine the situation where there are no inputs or outputs. Does it make sense to access the first (non-existant) element? We remedy the situation with the following modifications:
package Binsort;
public Strategy1_2 implements NodeBehavior {

Object o; // storage for the object we will read/write

public void act(InputChannel[] inputChannels,
OutputChannel[] outputChannels) {
// first we try to read a packet, catching the
// necesssary exceptions
try {
// check for at least one input
if (inputChannels.length != 0) {
o = inputChannel[0].readObject();
}
} catch (ChannelEmptyException e1) {
} catch (ChannelDisabledException e2) {}

// now we have a packet, so we try to write it.
try {
// check for at least one output
if (outputChannels.length != 0) {
outputChannels[0].writeObject(o);
}
} catch (ChannelFullException e3) {
} catch (ChannelDisabledException e4) {
}
}

Now we need to take care of the problems where we create and destroy packets. How do we create packets? Well, suppose we have read a packet and successfully written it. Our act method is called again and this time we fail to successfully read a packet, but Object o is still successfully written to the output channel. Oops! We need to prevent this double (or triple, or quadruple, or...) writing somehow. The following does the trick. Now whenever we write a packet we prevent ourselves from ever writing it again by unsticking our label and checking to make sure we only write packets if Object o is non-null.
package Binsort;
public Strategy1_3 implements NodeBehavior {

Object o; // storage for the object we will read/write

public void act(InputChannel[] inputChannels,
OutputChannel[] outputChannels) {
// first we try to read a packet, catching the
// necesssary exceptions
try {
// check for at least one input
if (inputChannels.length != 0) {
o = inputChannel[0].readObject();
}
} catch (ChannelEmptyException e1) {
} catch (ChannelDisabledException e2) {}

// now we have a packet, so we try to write it.
try {
// check for at least one output, and check to make sure
// we have a packet ready to write.
if ((outputChannels.length != 0) && (o != null)) {
outputChannels[0].writeObject(o);
// if no exception is thrown, we have successfully written
// the packet, so unstick the label from the Object.
o = null;
}
} catch (ChannelFullException e3) {
} catch (ChannelDisabledException e4) {
}
}

The final problem we face is that our node sometimes eats packets, meaning that not every packet that enters via one of the inputChannels makes it to an OutputChannel. Borrowing from the above code, though, we can see that the problem is that we read a packet, regardless of whether or not we wrote the one we already had. To prevent this, only do a readObject if o is null (has been written). This final implementation fo our first strategy is thus:
package Binsort;
public Strategy1_4 implements NodeBehavior {

Object o; // storage for the object we will read/write

public void act(InputChannel[] inputChannels,
OutputChannel[] outputChannels) {
// first we try to read a packet, catching the
// necesssary exceptions
try {
// check for at least one input, and make sure we're not
// already holding an Object.
if ((inputChannels.length != 0) && (o == null)) {
o = inputChannel[0].readObject();
}
} catch (ChannelEmptyException e1) {
} catch (ChannelDisabledException e2) {}

// now we have a packet, so we try to write it.
try {
// check for at least one output, and check to make sure
// we have a packet ready to write.
if ((outputChannels.length != 0) && (o != null)) {
outputChannels[0].writeObject(o);
// if no exception is thrown, we have successfully written
// the packet, so unstick the label from the Object.
o = null;
}
} catch (ChannelFullException e3) {
} catch (ChannelDisabledException e4) {
}
}

Implementing strategy #2

As mentioned above, strategy #2 is used by IntermediateNodeBehavior. This is a bit more complex, but doable if you've managed to get strategy #1 us and working. The differences are in these areas: class IntermediateNodeBehavior implements NodeBehavior
{
// flag to tell us whether we should read or write
private boolean readToWrite;

// counters to determine which input/output to write to first
private int nextInIndex, nextOutIndex;

// the packet we read/write
private Object packetToBeSent;

private void readFromChannel(InputChannel[] inputChannels)
{
// if there's no input channel, exit right away. Note that this
// is not strictly necessary (the for loop is correct even for
// the case where we have length == 0.)
if (inputChannels.length == 0) return;

// try to read from each InputChannel. Stop when either:
// 1. a packet has been successfully read, or
// 2. when we have tried each input channel at least once.
for (int i = 0; i < inputChannels.length && !readToWrite; i++)
{
try
{
packetToBeSent =
inputChannels[ nextInIndex ].readObject();
readyToWrite = true;
}
catch(ChannelEmptyException exc) {}
catch(ChannelDisabledException exc2) {}

// Increment the channel we will read from, modulo length
nextInIndex = (nextInIndex + 1) % inputChannels.length;
}
}

private void writeToChannel(OutputChannel[] outputChannels)
{
// If there's no out channel, exit right away. As above, this
// is not stricly necessary.
if (outputChannels.length == 0) return;

// try to write to each OutputChannel. Stop when either:
// 1. a packet has been successfully written, or
// 2. when we have tried each out channel at least once.
for (int i = 0; i < outputChannels.length && readToWrite; i++)
{
try
{
outputChannels[ nextOutIndex ].writeObject( packetToBeSent );
readyToWrite = false;
}
catch(ChannelFullException exc) {}
catch(ChannelDisabledException exc2) {}

// Increment the channel we will write to, modulo length;
nextOutIndex = ++nextOutIndex % outputChannels.length;
}
}

public void act(InputChannel[] inputs,
OutputChannel[] outputs)
{
if (readToWrite) { writeToChannel( outputs ); }
else /* not readToWrite */ { readFromChannel( inputs ); }
}
}

Important Note:

IntermediateNodeBehavior is not necessarily the best, most efficient, or most "correct" implementation of NodeBehavior. Many of you have code that is as effective in moving packets. Your code is correct too. The code we have given you here is one possible solution, and probably could be improved upon. Indeed, some of the things included in our code are unnessary for correctness, but were included to make what was happening mroe clear. For instance, we do not really need to have the lines:

if (inputChannels.length == 0) return;
if (outputChannels.length == 0) return;
becuase the for loop that follows would correctly exit without ever attempting a read/writeObject. So, if you think your implementation is better than ours, let us know and we'll post it to the homepage.

This course is a part of Lynn Andrea Stein's Rethinking CS101 project at the MIT AI Lab and the Department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology.