T-106.420 assignment 3 — Tuple space

In this assignment, you will implement an interprocess communication mechanism and use it for a simple chat system.

Background

You have been assigned to write a prototype for a new platform-independent chat system that is intended to allow users to participate in a conversation from a wide range of devices. To make it easier to balance the load between servers and make the system less dependent on a specific communcations mechanism, your boss has decreed that you use tuple spaces to distribute messages. Your job is to implement a basic tuple space system (the design team is still arguing about which tuple space implementation to use) and get the message distribution part of the chat system running.

Task description

Your task is to write a simple tuple space implementation using standard Java synchronisation mechanisms and use it for the message passing part of a simple chat system. The tuple space implementation should be thread-safe, but it need not be capable of communication between virtual machines.

Tuple space API

Your tuple space implementation must conform to the following specification (Java source):

All the classes below are in package tuplespaces.

public class TupleSpace
- public TupleSpace()
  - Create an empty tuple space.
- public Object[] get(Object[] pattern)
  - Remove and return a tuple (an array of entries) matching pattern (which may not be null) from tuple space. Block until one is available. A tuple matches a pattern if both have the same amount of entries and every entry matches. A null entry in the pattern matches any object in that entry in the tuple. Any other object p in the pattern matches any object t in the corresponding entry in the tuple for which p.equals(t). The semantics of equals are those defined in the Java API description.
- public void put(Object[] tuple)
  - Insert tuple in tuple space. tuple is an array of any length (except zero) and is not null. tuple may not contain null values. You may assume that objects stored in the tuple space do not change (especially not in regard to equals or hashCode).

Chat system

The chat system is based on channels (identified by Strings) to which messages can be sent. It is also possible to listen to a channel. When a listener connects to a channel, it is sent a log of the n last messages sent to the channel (where n is a value specified at server startup). After that, the listener receives all messages sent to the channel until it leaves the channel.

The chat system must be conform to the following:

All the classes below are in package chat:

public class ChatServer
- public ChatServer(int rows, String[] channelNames)
  - Create a new chat server with a set of channels identified by the Strings in channelNames and a buffer of rows messages for each channel (the rows last messages should be sent to new listeners connecting to the channel).
- public void writeMessage(String channel, String message)
  - Write message message to channel channel.
- public ChatListener openConnection(String channel)
  - Open a listening connection to channel.
public class ChatListener
- You may assume that each ChatListener is used by only one thread.
- public String getNextMessage()
  - Get the next message from the channel. If no message exists, wait until it appears.
- public void closeConnection()
  - Close the ChatListener.

All parameters above are non-null. For testing purposes, you can use this simple chat system user interface. To start it, run:

java chatui.ChatUI <buffer size> [<channel name 1> [<channel name 2> [...]]]

Communication

The chat system should use tuples to communicate between threads. In other words, the system should be designed in a such a way that processes on different machines can share channels if a mechanism is added to the code to connect to a distributed tuple space and use that instead of the student's implementation (serialisation and transmission of data as needed is assumed to be solved by the tuple space implementation; this primarily means that you should not modify data that is referred to by tuples in the space).

Concurrency and synchronisation requirements

Synchronisation in the tuple space system should be done using the basic Java synchronisation primitives (those built into the language and java.lang, not java.util.concurrent). Inefficient solutions, such as polling and busy-waiting, will be rejected. Use of unsafe methods such as java.lang.Thread.destroy() will also lead to rejection.

The chat system should use tuple spaces for synchronisation. Each ChatListener is used by only one thread at a time. However, a ChatServer and its associated ChatListeners may be used by multiple threads.

Error handling

To keep this assignment simple, you may ignore many of the errors a tuple space implementation may face. For example, the put and get operations in this simplified implementation should not fail. In a real distributed tuple space implementation, many bad things can happen such as connection failures and timeouts.

Throwing exceptions in the case of invalid parameters is recommended but not required.

Style requirements

The program should be written in clear, reasonably object-oriented Java. We will not accept programs that are hard to read, violate basic object-oriented programming principles or contain a large amount of repeated code with minor variations. Cryptic method and variable names should not be used.

Explanatory comments are required for code that is not self-explanatory to a programmer fluent in Java. However, you should not clutter your program by stating the obvious. As an example, Javadoc comments describing the syntax of trivial methods (such as accessors) will be tolerated but are discouraged.

Documentation

You must provide a PDF file in which you explain how your solution works. In particular, you should explain how your tuple space implementation is synchronised and how its operations work and how your chat system uses the tuple space for message passing and synchronisation.

Language

Comments, variable and method names and documentation may be written in English, Swedish or Finnish. You should avoid mixing these languages, but you may use different languages for different aspects of the assignment (e.g. code in English, documentation in Swedish and comments in either of the two is fine).

Hints

Although it is possible to create a fast tuple matching algorithm using a lot of indexing, this assignment is not about indexing. An algorithm that performs reasonably well in most cases is enough for our purposes. Optimising for your chat implementation is a good idea.
Testing your tuple space implementation with a lot of concurrent threads putting and getting tuples at once is a very good idea.
Tuples can easily be used like semaphores, so similar synchronisation techniques apply.
A chat channel is like a bounded buffer, except it has multiple readers that all get the same data. Test accordingly.

Submission

Before the deadline (2006-01-16 03:00), you must submit a gzipped tar archive containing your solution using the form below. The archive must contain the following files:

`tuplespaces/`	The Java (version 1.4 or earlier) source code of your tuple space implementation (the directory corresponds to the `tuplespaces` package).
`chat/`	The Java (version 1.4 or earlier) source code of your chat system implementation (the directory corresponds to the `chat` package).
`description.pdf`	A PDF containing the documentation for your solution.

Your program will be compiled and run with the standard library and testing code included in the classpath.

You may work in pairs. The grading does not depend on whether you are working alone or in a pair.

Results will be sent to <student number>@students.hut.fi.

Page last updated by Jan Lönnberg 2005-12-17.