Next

KWIC Implemented with Pipe Filter Architectural Style

Pipe and Filter Systems in General

In a pipe and filter style each component has a set of input streams and a set of output streams. A component reads streams of data on its input streams, processes the data and writes the resulting data on its output streams. Hence components are termed filters. The connectors of this style merge the streams together, i.e., they transmit outputs of one filter to inputs of another filter. Hence the connectors are termed pipes.

Among the important invariants of the style is the condition that filters must be independent entities: in particular, they should not share state with other filters. Another important invariant is that filters do not know the identity of their upstream and downstream filters. Thus, filters may not identify the components on the ends of their pipes.

Common specializations of this style include pipelines (see figure below), which restrict the topologies to linear sequences of filters; bounded pipes, which restrict the amount of data that can reside on a pipe; and typed pipes, which require that the data passed between two filters have a well-defined type.

The best-known examples of pipe and filter architectures are programs written in the Unix shell. Unix supports this style by providing a notation for connecting components (represented as Unix processes) and by providing run-time mechanisms for implementing pipes.

Architecture

Pipe and Filter KWIC system is composed of the following components:

• Input filter, which reads the content of a KWIC input file, parses it, and writes the parsed lines to its output stream.
• CircularShifter filter connected with a pipe to the output stream of Input filter. Thus, the lines produced by Input filter serve as input for CircularShifter filter. CircularShifter processes the input lines producing circular shifts of those lines. The produced shifts are written to the CircularShifter's output stream.
• Alphabetizer filter connected with a pipe to the output stream of CircularShifter filter. Thus, circular shifts produced by CircularShifter serve as input for Alphabetizer. Alphabetizer sorts these shifts alphabetically and writes them to its output stream.
• Output filter connected with a pipe to the output stream of Alphabetizer. Thus, Output reads sorted shifts from its input stream and writes them to the standard output.
• Master Control, which manages filter and pipe mechanism, by creating a pipeline of the above described filters.

Pipes in KWIC system

Pipes in the KWIC system are represented as instances of the Pipe class. An instance of the Pipe class is a composition of two streams: an input and an output stream. Pipe class connects these two streams in the following way. The data that is written to the input stream is transmitted to the output stream. In this way these data become available for reading from the output stream.

The Pipe class encapsulates the input and output streams as its private instance variables and provide just a simple public interface for writing and reading data to a pipe object. Thus, clients simply write some data to a pipe object by calling its write method. This data becomes then available for other clients, which can call the read method of the pipe object to retrieve the data.

There are few important properties of pipe objects:

• Pipe objects limit the amount of data they can hold. However, whenever clients read the data from a pipe, this data is considered "consumed" and the space that was occupied by the retrieved data is made free again.
• Pipe objects are synchronized. This has two major consequences. Firstly, there can be only one thread working with a pipe object at a specific moment, i.e, there can be only one thread currently writing or reading the data from a pipe object. Secondly, threads reading from an empty pipe or writing to a full pipe are blocked as long as there are not some data to read from the pipe, or there is no free space in the pipe to write the data. Thus, a pipe object may be seen as a typical shared synchronized data structure for producer/consumer multi-thread scenarios. Thus, a pipe object is always shared between a producer and a consumer thread, where the producer thread writes some data to the pipe, and the consumer thread "consumes" that data from the pipe.

Filters in KWIC System

Filters in the KWIC system are represented by an abstract class named Filter. An instance of Filter class is composed of:

• Input pipe object, from which the filter object reads the data
• Output pipe object, to which the filter object writes the processed data
• Thread of control. Each filter object runs in its own thread and is independent of any other filters in the system, i.e., it does not share state with other filters in the system.

The current implementation of the Filter class provides already the basic filter functionality. Thus, clients start the execution of the filter object by invoking its start method. In turn, this method starts the control thread, which consecutively invokes the filter's transform method.

In the current implementation the transform method is an abstract method, which means that subclasses of Filter class should provide a particular implementation for that specific filter object. For example, CircularShifter filter implements transform method in the following way. The lines retrieved from the input pipe are processed and circular shifts of those lines are made. Thereafter the produced shifts are written to the output pipe. Speaking more generally, subclasses of Filter class implement their transform methods in the following way: the data is retrieved from the input pipe, transformed (processed) and written out to the output pipe.

Filter objects may be combined into a typical producer/consumer scenario by simply sharing a pipe object. For example, we assign the output pipe of the first filter to the input pipe of the second filter. In that way whenever the first filter produces some data and writes it to its output pipe, this data is available for the second filter to consume it. Thus, we may combine a number of filters into a sequence (pipeline) to achieve the desired functionality of the system.

Pipeline in KWIC system

The current KWIC system utilizes a pipeline consisting of the following four filters:

• Input filter
• CircularShifter filter
• Alphabetizer filter
• Output filter

All KWIC filters are of course subclasses of abstract Filter class. These relationships are depicted on the following class diagram:

The four KWIC filters are connected by means of the following pipes:

• in_cs pipe, which is shared between Input and CircularShifter filter, i.e, this pipe is the output pipe for Input filter and the input pipe for CircularShifter filter.
• cs_al pipe, which is shared between CircularShifter and Alphabetizer filter, i.e, this pipe is the output pipe for CircularShifter filter and the input pipe for Alphabetizer filter.
• cs_ou pipe, which is shared between Alphabetizer and Output filter, i.e, this pipe is the output pipe for Alphabetizer filter and the input pipe for Output filter.

The following figure shows the current pipeline including the pipe names:

Next