Next: 8. An Analysis of
Up: An Architecture for Parallel
Previous: 6. Process Management
This chapter discusses the treatment of devices and I/O under DSI.
We describe the stream I/O interface and its integration with
DSI's process model.
We then describe an implementation of input and output device
drivers and their interaction with other system processes.
We conclude with a discussion of the strengths and limitations
of I/O in DSI.
7. Device Management
DSI uses a character stream I/O interface;
all data is presented to, or issued from, the device drivers using
An input device driver appears as a producer,
reading bytes from the device and injecting a corresponding stream
of characters into the heap.
An output device driver consumes a stream of characters
and writes raw bytes to the device.
An input-output, or bidirectional device driver both produces
and consumes streams of characters.
The drivers convert between raw bytes and DSI characters because
the character representation is better suited for manipulation by
programs dealing with lists and atoms.
7.1 The DSI I/O Model
A DSI character is represented by a singleton literal (an
atom consisting of a single character),
as shown in figure 17.
DSI Character Representation
The DSI hash module contains a table of statically preallocated
The input driver converts a byte to a character by indexing into
this table with the byte.
Thus, an input driver is really just generating a stream spine with
the appropriate subreferences to existing identifiers.
Most DSI programs construct networks of streams that are
considerably more sophisticated than this.
These stream networks usually operate on higher level forms
The usual procedure is to parse the input stream into
atoms and forms,
process it through the network (evaluation) and convert the result back
into a character stream for the output driver.
Daisy provides four standard stream transducers for this purpose:
a scanner, a parser, a deparser and a descanner.
These filters were designed to support Daisy expressions,
but can be used for general scanning of atoms, etc.
Streams are naturally implemented in DSI using suspensions,
so a system with drivers reading characters from a keyboard and echoing
it to a terminal would look something like that depicted in
In the figure, DSI characters are shown as c's;
character substructure has been omitted for the sake of simplicity.
7.2 Device Drivers
Character Stream I/O
The input and output drivers are implemented in standard fashion
for DSI stream producers and consumers (respectively).
Suspending construction provides the synchronization and
blocking mechanisms required for transparently interfacing
other processes with the drivers.
Processes operating on an input stream are not aware of the embedded
driver suspension nor any accompanying I/O activity.
Similarly, output drivers blindly consume their argument streams
without regard to the source of that data;
all that is required is that the argument stream conform to a list
DSI supports the keyboard, terminal, TCP/IP stream sockets and
Unix pipes as I/O devices.
In addition, any file or device that can be accessed through the host's
filesystem and can be read or written as a serial byte stream can be
Actual I/O to the various devices is handled by the host interface
layer of the implementation, which provides a set of primitives
for the DSI drivers.
These primitives open and close devices, issue host I/O calls and
buffer data, much like the C stdio library.
The calls are listed in table 3.
Host Interface Layer I/O Calls
||Open /dev/tty for input.
||Open /dev/tty for output.
||Open a file for input.
||Open a file for output.
||Create a socket for incoming connections.
||Create a socket for outgoing connections.
||Make an incoming socket connection.
||Open a Unix pipe.
||Open a Unix pipe/pseudo-terminal.
||Close a file or device.
||Non-blocking check for input data.
||Issue disk read request.
||Get a character.
||Put a character.
||Check device or file status.
||Issue a short prompt to console.
DSI interfaces with these host I/O functions via device
A descriptor is represented by a unary cell with a host I/O handle
stored in the non-collectible data field.
The tail is used to store a prompt string (a MSG-list)
if the device (e.g. a terminal) supports one.
DSI Device Descriptors
The host I/O handle points to a structure containing information
about the device, such as its type, buffers, optimal blocksize,
and current state.
The host I/O routines in table 3 create and use this
information to handle differences between devices and to perform
efficient transfer and buffering for each device type.
The dvcin (input) and dvcout (output) modules define
system primitives for instantiating a stream process (producer or
consumer) of the appropriate device type.
The corresponding Daisy functions are listed in table
Daisy I/O Primitives
||Returns a buffered tty input stream.
||Returns a raw tty input stream.
||Returns a file input stream.
||Returns a pipe output stream.
||Writes a tty output stream.
||Writes a file output stream.
||Reads/writes a socket stream.
||Reads/writes a socket stream.
||Reads/writes a pipe stream.
||Reads/writes a pipe stream.
The following sections describe the operation of the driver processes
for input and output.
All input devices are handled by a single generic driver,
the input device manager.
When a DSI input primitive is invoked, it calls the appropriate host
I/O routine to obtain a native I/O handle (e.g. dski calls
It uses this handle to build a corresponding DSI descriptor.
The primitive then calls a device manager subroutine to make the
descriptor known to the device manager.
The device manager subroutine instantiates the input stream and
returns a reference to it.
The input primitive may return this stream, or filter it,
depending on the device (see 7.3.4 below).
7.3 Input Devices
The device manager configuration is shown in figure 20.
Input Device Handling
The device manager maintains a list of descriptor/stream
associations on the device list (DVCLST).
The stream part of the descriptor/stream pair is a reference to the
tail of the input stream of characters associated with the
When DVISCAN wakes up it scans the device list and polls each
descriptor in turn:
After it has processed the entire device list DVISCAN suspends
itself and awaits its next activation.
- If there is data pending, DVISCAN will enter an input loop,
reading raw bytes from the descriptor, converting them into DSI characters
and appending them onto the associated input stream.
When there is no more pending data to be read from a descriptor,
DVISCAN updates the tail reference in the descriptor/stream
pair and moves on to test the next descriptor in the device list.
- If the descriptor indicates an end-of-file or error condition
DVISCAN closes the descriptor, terminates the input stream
and deletes the device/stream pair from the device list.
DVISCAN is an example of a multi-way shared suspension;
the kernel retains a reference to it, and all low-level input streams
are formed by using the same reference.
DVISCAN can be activated in one of two ways:
by the kernel in response to receiving a SIG_IO signal,
or by a consumer process probing it as an argument stream.
In either case DVISCAN acts as described above,
servicing all descriptors with pending input.
This arrangement provides asynchronous I/O support,
since any input activity results in all descriptors being serviced.
There are three signals reserved for device handling.
SIG_IO should be implemented by a hardware interrupt or host
operating system exception that is asserted when there is
data ready to be read from an input device.
If the device is attached to a single processor, then only that
processor should receive the SIG_IO.
Otherwise, the signal may be multicast, and the processor which
"owns" the device manager suspension will activate it.
If there are multiple I/O channels that can be serviced concurrently
(perhaps on a processor network),
it might be desirable to have more than one instance of DVISCAN
This is not conceptually difficult, and would simply require that
each instance of DVISCAN manage a separate device list,
or that they coordinate to avoid corrupting a single shared device
The current implementation assumes a single instantiation of
Both the DVISCAN and DVCOUT will assert SIG_IOBLOCK
if there is no data to be read or the output device is not ready for
In either case the intent is to indicate that
no headway is currently possible in the current process chain.
Thus SIG_IOBLOCK is intended to signal a lateral scheduling
change (preemption), and is, in fact, handled like a timer signal.
Occasionally an input stream may become unreferenced while the device
or file is still open.
The device manager operates in conjunction with the garbage collector
to close these dangling file descriptors.
7.3.3 Garbage Collecting Devices
DVISCAN starts by loading the header cell of DVCLST
from a fixed heap location, and it finishes by clearing any references
to the device list before detaching itself.
The result is that unless DVISCAN is running, there are no device
list references in any suspensions in the system (although there
are references to the descriptors and input streams).
Thus, while descriptors, input streams, and the DVISCAN
suspension are marked by the garbage collector,
the spine and ribs of the device list are not
After the normal mark phase, the garbage collector makes a special
pass over the device list, checking to see if any spine/rib elements
have corresponding unmarked descriptors.
If so, it means that the corresponding input stream has been
The collector closes the unmarked descriptors and splices the
corresponding elements out of the device list.
The device list and the hash table
are the only two structures that are collected specially by the
The implementation is different, but the effect is identical
to that of the files demon in MultiScheme [Mil87].
This section describes the differences between the various kinds of
of input devices supported by DSI.
DSI relies on the host filesystem to manage files.
Disk input is handled on a per-file basis.
dski takes a host filesystem path as argument and creates a new
descriptor and DVISCAN stream for each open file.
It returns a stream of characters read from the file.
Keyboard input is differentiated from other kinds of input
in that it is implemented at a lower level.
Instead of relying on the host buffering to handle multiple instances
of keyboard input,
DSI requests a single stream of input and multiplexes the stream
220.127.116.11 Keyboard Input
At the lowest level, a DVISCAN input process presents a
single raw stream of characters issuing from the keyboard.
This stream is consumed by a single splitter process (SPLIT),
as shown in figure 21.
Input TTY Handling
SPLIT, like DVISCAN, is a multi-way shared suspension.
The splitter splits its input stream, serving up characters on demand
to whichever consumer happens to be coercing it at the moment.
To add another process into the keyboard input mix it suffices to
create a new trolly-car stream using the single SPLIT reference.
The splitter guarantees that no two clients will receive the same
The streams produced by SPLIT are also all raw character streams.
This is what you get using Daisy's rawtty primitive.
Raw character streams are not particularly useful as keyboard
Most operating systems will reserve certain characters for special
interpretation, such as interrupting processes, job control or
editing and buffering input.
DSI filters the raw stream using a standard keyboard filter
(KBDFLTR in figure 21).
KBDFLTR provides a filtered ("cooked") character stream,
which is what you get using Daisy's console primitive.
The functionality provided by KBDFLTR is fairly limited.
It issues a prompt and then attempts to read up to and including
a newline before detaching;
when it reawakens it will prompt again and iterate.
This simple interleaving of prompts and inputs is sufficient to
give programs the proper interactive feel,
something can be tricky in a lazy environment.
KBDFLTR also performs a few other character interpretations,
summarized in table 5.
Standard Keyboard Filter Actions
||Detach; prompt when awakened.
||end of file
||Escape the next character.
You will note that their isn't very much in the way of editing keys;
DSI relies on the host operating system to handle that.
It would not be difficult to do, however.
Using the rawtty primitive it is possible to write more complex
or special purpose filters in Daisy.
There also aren't any process termination interpretations such as the
Which process would this affect?
DSI's process model is vastly different from conventional systems;
there are many, many processes associated with any "job".
The Daisy Programmer's Manual [Joh89c] has
examples of how to do job control in Daisy using multisets.
7.4 Output Devices
An Output Process
Output devices are symmetrically constructed to input devices.
An output driver is a stream consumer of characters.
Each character is converted to a raw byte and written to the output
channel using the host I/O primitives which handle the proper
buffering for the device type (e.g. disks are written in blocks,
terminals are unbuffered. etc.).
As with input devices, output devices share a common generic output
driver (DVCOUT), with differences between devices contained in
the host I/O handle and handled at the host interface layer.
Unlike the input manager, the output driver is multiply
instantiated for each output occurrence;
that is, a new process is created for each consumer.
Output device primitives construct the appropriate descriptor,
create a suspension for the DVCOUT process, and give it a
That context is then probed to bootstrap the output process.
DVCOUT is a fairly simple loop.
It probes its input stream for a character and converts it to a
raw byte (see figure 17).
It then checks the status of its output descriptor:
If DVCOUT reaches the end of its input stream it converges
Note that DVCOUT may block, but never detaches;
that is, it is infinitely strict in its argument.
- If the descriptor is ready for writing the byte is emitted
using H_put and the process iterates.
- If the device is not ready for writing, DVCOUT signals
the kernel with a SIG_IOBLOCK, indicating that the process is
blocked and a lateral context switch is in order.
- If the device indicates an error, DVCOUT converges
to an erron.
This section describes the differences between the various kinds of
of output devices supported by DSI.
dsko takes a filename and a stream of characters as arguments.
It creates or truncates the named file and writes the characters to it.
It returns NIL after the last character is written.
Terminal output is the complement to keyboard input;
screen takes an input stream and writes it to the terminal,
returning NIL after the last character has been written.
Terminal output is not implemented at the same level of detail
as keyboard input, however.
If it were, multiple output streams would be merged by a MERGE
process into a single output stream before being delivered to a single
(tty) instantiation of DVCOUT.
As it is, DSI lets the host handle the multiplexing of outputs.
An upgrade to DSI's terminal output system is planned to make it
complementary to keyboard input.
The effect of output devices is more than just to output characters.
Because the output device driver is infinitely strict,
it presents a point source of continuous demand that propagates down
through its input stream and through the data space to the fringes of
the computation (and ultimately, to any input drivers).
It is the output devices which ultimately provide the impetus
for DSI's demand-driven behavior.
In between the the output drivers and the inputs, the user program
controls the direction of this demand flow.
Note that with the valid implementation of SIG_IO,
DSI's input drivers are event-driven rather then demand-driven.
This makes sense, given the transient nature of data on the I/O bus;
most devices implement some form of buffering, but will experience
overruns if their interrupts are not serviced in a timely manner.
In addition to input-only and output-only devices, DSI also supports
A bidirectional device is one that can be modeled as having
both input and output channels.
For example, although the display and keyboard are actually two
separate physical devices, under Unix they are integrated into a
single logical device (e.g. /dev/tty) from which you can read
and to which you can write.
There are two kinds of interfaces that can be used for bidirectional
devices in DSI.
One is to split the device into two logical devices corresponding
to its input and output components;
this is the basic approach used for terminals.
The read and write terminal I/O streams are accessed by separate input
(rawtty) and output
(screen) primitives, which create distinct input and
output driver suspensions, as described above.
Another approach to bidirectional devices is to model the device like
a stream transducer;
i.e. a driver process that is both a producer and consumer of
Figure 23 shows how this is implemented using a single
The driver multiplexes input and output functions;
the input stream is written to the device and the data read from
the device is appended to the output stream.
DSI provides two kinds of bidirectional "devices" in the
transducer-type interface: sockets and pipes.
DSI provides an interface to BSD-type stream sockets,
a high-level TCP/IP networking standard on many operating systems,
including most flavors of Unix.
Sockets provide full-duplex (bidirectional) data streams
between two points (sockets) over a network.
Two Daisy primitives provide access to the Unix socket interface.
Both socki and socko are higher-order
They both return functions (closures) that map character
streams to character streams;
i.e. they create a producer-consumer process as described above.
The input stream is the characters to write to the socket and
the output stream is the characters read from the socket.
The difference between socki and socko is in how the
socket connections are established;
socki accepts incoming connections (server-style) and
socko makes outgoing connections (client-style).
The socki primitive takes a port number as argument,
creates a socket, binds it to the port address on the host,
and returns a function.
When that function is applied to an input stream,
DSI watches the port, establishing the bidirectional data flow
when an incoming connection is made.
This action corresponds to the Unix accept call,
except that it does not block.
socko takes a list argument containing two items: a host name
and a port number on the network; it returns a function.
When that function is applied to a stream it tries to
connect to the named socket, and also establishes a
a bidirectional data stream.
Another useful bidirectional device interface provided in DSI is a
A Bidirectional Unix Pipe "Device"
Like the socket primitives, the pipe primitive is higher-order.
It takes a flat list of literal arguments which are intended to be the
elements of the argv argument vector passed to a forked
Unix process, and returns a function.
When that function is applied to a stream it creates a pipe, and
forks and execs a Unix process.
The forked process's I/O is redirected to the pipe, so that the input
stream to the pipe interface suspension (see figure 23)
is fed to the process's stdin, and the process's
stdout (and stderr) are returned through the
interface suspension as the output stream.
The connections are illustrated by figure 23.
Two variations on pipe are provided.
tpipe operates just like pipe, but opens a
pseudo-terminal between the process and the I/O streams.
This fools the forked process into thinking it is connected to an
actual tty device, which some Unix programs require to
exec is a first-order function for creating processes that
only write to stdout;
its argument is in the same format as the function returned by
DSI's I/O model reflects its roots in functional programming
The stream representation provides a non-temporal, applicative
interface to asynchronous device I/O that integrates well with DSI's
The stream interface is useful for a wide variety of devices,
but some devices work better with stream model than others.
In this section we will explore some of the limitations of stream
I/O under DSI.
This is an instance of more general problem involving non-strictness,
but it becomes particularly evident with interactive stream I/O.
Proper interleaving of input and output from a terminal is difficult
when there is no intuitive sense of the demand patterns ordering
execution of stream processes.
The most typical manifestations of this problems are that input is
requested before a prompt appears, prompts for various input channels
are interleaved (so that one does not know which input channel he
is typing to), and so on.
One solution to this problem is to insert explicit point-source
coercion or laziness operations into the code to achieve
the proper interleaving of prompts, input, and output
At best this is a trial and error, ad-hoc procedure.
Fortunately this problem is alleviated to a great extent by the
ubiquitous use of modern windowing shells.
The ability to direct I/O to individual windows usually does away
with the sorts of machinations just described and the vagaries
of multiplexing the console among many active I/O processes.
The xdsi interface allows DSI/Daisy programs to manipulate
multiple character-mode I/O windows under the X window
xdsi is implemented as a separate, non-integrated server that is
bundled with the DSI source distribution.
It relies on DSI's support for sockets (see above) to communicate
with programs running on DSI.
This arrangement nicely avoids the need to link in a number of large
host X libraries into the DSI host executable;
the only requirement is that the host operating system have
TCP/IP networking support.
It also makes possible a number of flexible connection arrangements.
DSI programs can connect to multiple xdsi servers
(usually on different workstations);
conversely, an xdsi server can be connected to multiple DSI
sessions (usually on different workstations or multiprocessors).
This flexibility provides different ways to experiment with applicative
operating systems, distributed computing, and other applications
of networked user I/O.
DSI programs establish a control stream with the xdsi server
by connecting to a specified socket address.
Over this stream it can send commands to create and manipulate input
and output windows on the display that xdsi is controlling;
the model is very similar to that used by the X window system itself.
Each window is associated with a DSI character stream.
Input windows are stream producers in DSI; output windows are stream
The streams interface in the normal way with user programs running
One of the problems alluded to above in the description of
terminal I/O is the difficulty of determining which process is
This is handled in xdsi by a special command on the control stream
which inverts the background and foreground of an input window.
The command is issued automatically by the xdsi interface in DSI
on behalf of the input window when demand is applied to the input
The effect allows the user to know which windows are requesting input.
A screen snapshot of the xdsi system in action is shown in figure
The screen shows several input and output windows connected to a
Daisy program which models a hardware blackjack machine.
The black windows are quiescent; the white windows are currently
An xdsi Session
(Click on the image to see a full screen 1280x1024 (124Kb) image)
As of this writing, xdsi only supports unidirectional text windows.
An obvious extension to this approach is to allow other specialized
types of windows, such as GUI widgets.
The xvi system [Sin91] is a windowing interface
for a lazy functional language that is also implemented
using a server approach (although in a more tightly coupled way than
It allows widgets and even lower level drawing to be controlled
from the language by interpreting text strings issued by the program
to the standard output, and parsing them calls to the X graphics
This approach requires a working knowledge of the widget and drawing
interfaces in C.
The eXene environment for CML [Rep91] is an example
of a more general lower level use of streams to control a GUI interface.
eXene models each window as a collection of streams:
mouse, keyboard and control streams.
Widget libraries can be created in CML using these stream interfaces.
Integrating non-character-oriented I/O devices is not superficially
difficult--it just involves streaming data other than characters
and converting it as appropriate in the driver.
This would require a less generalized driver to interface these
kinds of devices to the system.
For example, a plotter might consume a stream of commands and integer
For serial "stateless" devices, such as keyboards, mice, terminals,
or network sockets, the stream interface is a reasonably accurate
model of the underlying events.
For "stateful" devices, such as disks, the stream
interface provides only a limited subset of the device's capabilities.
Some devices, such as bitmapped displays, seem very unlikely to be
handled by a stream I/O interface under current technology, other
than at a high level, such as the xdsi interface.
Part of the problem is the large, stateful nature of a bitmapped
display memory and part can be attributed to processor speed and
bandwidth limitations of serializing a bitstream to the display.
Next: 8. An Analysis of
Up: An Architecture for Parallel
Previous: 6. Process Management