Any reference model makes assumptions about the environments to which it applies. Our reference model, in particular, was affected significantly by the following considerations, most of which have only recently begun to impact the design of interactive software:

In addition, two other factors are of great concern to the user interface developer, namely:

To best describe the various levels of ``I/O'' involved in an interactive dialogue, one can consider the relevant hardware and software as consisting of four major components:

Finally, while we have used the expression ``the dialogue manager'' above, the system is not constrained to supporting only one dialogue manager at a time [25]. Suppose, for example, a user interface developer is testing a new dialogue manager; she would like to run it ``on top of'' the existing dialogue manager in order to have a stable base to fall back on. Alternatively, consider a situation where the user wishes to invoke a backward-compatible ``shell,'' such as the UNIX c-shell. Such a ``shell'' is a dialogue manager. Thus, one can imagine a system supporting multiple dialogue managers simultaneously; only for expository purposes will we continue to use the singular.

The principal motivation for the decomposition of function proposed above is, simply, that it appears that many existing architectures for interactive software can be defined in terms of it. That is, it can be demonstrated to serve its principal purpose as a reference model!

A secondary motivation is to provide the converse, a basis for a well-structured, modular architecture — not just a model to which existing architectures can be compared. The OSI Reference Model has been used in this way to create the ISO protocol suite. We differ from that progression, however, in that we reject the notion of a layered architecture in which to get to layer N the application must ``go through'' layer N+1 (and vice versa, depending on the direction of control flow). Rather, as shown in Figure 1(a), each ``layer'' or module is assumed to have a well-defined interface, to which the application has direct access.

This bias in favor of ``modularity'' vs. ``layering'' has two beneficial side effects with respect to compatibility with existing software. First, applications that were written prior to the introduction of a dialogue manager can continue to function in the context of an existing workstation agent (or window system). Similarly, applications may continue to access devices directly, if necessary. Naturally, in that case, the user should beware of running any other application that uses the same devices at the same time.

The reader may have noticed that the expression ``UIMS'' has yet to appear in the presentation of the reference model. Indeed, our group decided that ``UIMS'' should either be scrapped altogether or used to refer to the combination of the dialogue manager, workstation agent and workstation manager as discussed above. That is, if ``user interface management system'' is to be applied solely to software (and not to include support mechanisms external to the computer), then it should be applied to all software that provides for the management of user interfaces. The remainder of this document uses the expression ``UIMS'' in precisely that manner — in contrast to the typical use of ``UIMS'' to mean what is referred to here as the ``dialogue manager.''

We propose that the workstation agent should, as a minimum, offer one class of (composite) virtual input device, namely, one that interleaves events from all real hardware devices into a single stream. Thus, the interface to clients is a stream interface. A client must ``read'' the stream to receive input.4 Naturally, a client may choose to open multiple such streams, perhaps one for each window. Other features pertaining to input handling are best described working from the hardware up. To illustrate these features, we will describe how the WA handles a mouse event (refer to Figure 2).

A mouse event, on arrival at the WA, is analyzed to determine which client (or clients) are interested in the event. Multiple clients may be associated with a single window, for example, if one client is responsible for lexical feedback (echo), while a different client is responsible for semantic feedback. Alternatively, there could be a client responsible for the mouse echo for all windows; it would receive a copy of all mouse events, and so be able to update the cursor position on the screen in parallel with another copy of the event being sent to other clients.

The determination of which clients are interested in the event is a three-step process. First, the WA determines the window (or windows) in which the mouse is positioned when the event occurred. Second, the WA determines which of the clients associated with those windows are interested in input from the device that generated the event. If there is more than one such client, the event is replicated, with a copy being targeted for each client. This then is the demultiplexing stage — the single stream of mouse input branches into several streams, one for each client. Of course, if there are no clients interested in an event, it is discarded.5

At this point, a copy of the input event has been produced for each interested client. The final step in client determination is to determine, for each client selected thus far, whether the client is interested in this particular event. That is, in general, a client may specify a filter that performs an action that is dependent on the actual input values as well as on the originating input device and the client's specifications for that device.6 For example, it would be quite reasonable for an input event to be discarded if it is not ``significantly different'' from the most recent previous reading in the client's queue. Alternatively, the ``new'' event (the one being processed) might cause the ``old'' event (the one in the queue) to be discarded. The measure of ``significant difference'' may well vary from one client to another; a typical measure for the mouse would be distance moved since last event, or whether a button transition had occurred.

Once it has been decided that the event should be queued for the client, it is entered in the queue in time-sequence order with input from all other devices. This is the multiplexing stage, and is the final step in the input flow through the WA. Subsequently, the event will be returned to the client in response to a ``read'' request.

A final desirable feature is support for out-of-band data. For example, a CTRL-C typed on a keyboard, indicating an abort request, should be processed before any pending events. The necessary input might be inserted at the head of the client's input queue, or it might be sent using an asynchronous event notification mechanism distinct from the stream interface we have discussed thus far. For reasons of simplicity, we advocate the former approach, relying on the client-side interface routines to accommodate out-of-band data. On the other hand, since out-of-band data often means that pending events should be flushed or modified in some other way, the client interface should provide the corresponding functionality.

Although we know of no current system that adheres precisely to the above description, the input models adopted by the Adagio project [41,42] and by the ANSI X3H3.6 Committee on Display Management for Graphical Devices differ only slightly. TheWA [30], X [38], and NeWS [21] differ in more details but are similar in spirit — including having adopted the notion of a single composite virtual input device.

The workstation agent is responsible for posting images on a display, sending controls to a sound generator and managing all other devices capable of providing feedback to the user. It is not our intention in this section to describe the media-dependent output primitives available to clients of the WA, but rather to discuss one of the most controversial issues in ``window system'' design: retention, the degree to which information needed to generate the output should be retained in the WA. As in the previous discussion, what follows looks at the case of the output being graphical or textual, and being displayed on a window of a graphics display, although many of the ideas presented are applicable to other media.

There are four principal levels of retention:

If the WA does not retain any portion of the image that it has placed on the screen, the application must then be responsible for all window regeneration whenever that becomes necessary. The WA's role becomes one of an informer — it informs the application that its window (or a specific portion of its window) has been destroyed, and must be replaced. It is then up to the application to enter the necessary information into its output stream that will cause the WA to repair or replace the contents of the window. The application module must keep, at all times, enough information to regenerate the image on the screen. This is the approach taken in SunWindows [40], X [38], and Andrew [22], for example.

Alternatively, the WA may keep a bitmap representation of the full window, including that part of the window covered by other windows. In this case, window movements do not require any work from the application, but any pan, scroll, zoom or resize of the window will require the application to take on the responsibility of redrawing the window. This approach was taken, for example, in the Teletype 5620 (formerly the Blit) [35].

The WA may keep a partially structured representation of the contents of the screen. For example, a WA handling a text window may keep the textual representation of the contents of the window. In this situation, the WA can handle any regeneration of the output unless a ``fault''occurs — analogous to a page fault — where the WA requires information from the application which precedes or follows that portion of the output structure retained by the WA.

A model of full retention can be illustrated with the idea of the WA having a built-in implementation of PHIGS [11]. Such a WA would retain the complete structure, the model, of a 3-D graphics image. The WA would be able to redisplay the 3-D image independently after any window modification mentioned above, or after such window parameter changes such as movement of the viewpoint or modification of the display attributes. Moreover, it would be possible for the WA to provide multiple independent views of the same image — independent of the application. This is the approach taken (for graphics) in the Virtual Graphics Terminal Service (VGTS) [28,34] and its successor, The Workstation Agent (TheWA) [30]. It is also an approach that can be taken in NeWS (formerly SunDew) [21], where Postscript [1] is supported rather than PHIGS.

The tradeoffs between these approaches are significant. For example, complete retention allows for rapid reposting of the window when it is moved, changes size or is uncovered — in contrast to the sometimes excruciating slowness with which a screen is refreshed when no information is retained. This is especially advantageous when the application is running on a machine remote from that running the WA (cf. [28,29,34]). However, the method used for this retention is highly dependent on the types of applications being supported and may lead to a high degree of redundancy — data structures in the application plus display file in the WA plus frame buffer, for example. Consequently, the idea of ``forcing'' such complexity upon all applications is inappropriate.

Fortunately, as demonstrated by TheWA and NeWS, it is possible for a single workstation agent to implement multiple retention models simultaneously. Indeed, the approach is to provide multiple classes of virtual output devices for each real output device. For example, TheWA supports one class of virtual output device that emulates the store of a VT-100 and one class that emulates a PHIGS-like structured display file. However, adding this much complexity to the workstation agent may be inappropriate in some situations, especially if memory space is a concern.

One possible approach to the combining of a standard graphics system (SGS) with the WA is to place the SGS between the WA and the devices. This permits the WA to communicate with the devices through the SGS, using existing software, and certainly gives it access to multiple input and output devices if they are available. At the higher level, the WA allows its clients to specify policies for using and controlling shared interactive resources. This approach yields a degree of device independence in one direction, and possible compatibility with the standard graphics system in the other.

KI [10] and MS Windows [33] are examples of this approach. At the heart of the KI system is GKS, which provides a set of device-independent functions for graphical data processing. On top of GKS are the KI kernel commands, which allow interactive use of the GKS functions with a common set of commands in addition to system functions for echoes, error messages and end-user defined dialogues.

There are several pitfalls to this approach. Current SGS's do not provide the functionality to readily implement the input model we have described above. Either the WA must live with the input model of the graphics package or it must define a new model and provide the mapping between the two. Also, SGS's do not normally provide proper windowing capabilities for graphics devices. For example, GKS was not designed to be run on workstations that might dynamically change size. Another problem, in CGI, is that the limited capability of device drivers may restrict the system's ability to take advantage of the increasing hardware support for complex graphic functions such as clipping to complex boundaries. In brief, we do not believe this to be a viable approach in most situations.

The second approach is to treat the SGS as a layer between the workstation agent and its clients, albeit a layer bypassed when required. The WA interacts directly with the hardware devices, providing its own graphics routines, font files and color maps. Consequently, it is able to implement input and output models other than (and presumably better than) existing standards. However, for each desired SGS a standard library is provided, which can be linked with the client to provide a ``front end'' that makes the WA look like the SGS. In situations where the SGS expects exclusive control of a device, some support may be required in the WA.

X is an example of this approach. While providing its own graphics interface, the X distribution includes a number of front end libraries. NeWS is another example in this category. Any SGS can be implemented on top of the PostScript graphics primitives due to the high level of abstraction it provides. The associated code can either be linked with the client or downloaded into the NeWS server itself, as discussed below.

The major advantage of this approach is that the WA can support applications written for any SGS for which an appropriate front end has been written — one that must include a mapping from the WA's input model to the one required for the SGS. Moreover, the WA can be ported to other systems independent of the SGS and more easily modified to accommodate new styles of interaction.

The final approach to accommodating existing standards is to embed the SGS inside the workstation agent. The principal advantage of this approach is reducing the potential for redundancy, particularly of data structures. For example, if PHIGS were embedded inside the workstation agent, then it is reasonable for the workstation agent to retain all output in structured display files, with the corresponding performance advantages discussed above. If, instead, the workstation agent adopted a different retention model and PHIGS were implemented in client libraries, then the data would be have to be stored both in structured display files within the client (library) and in the appropriate output structures within the WA.

The principal disadvantage of this approach is considerably increasing the size and complexity of the WA compared to the previous approaches. Nevertheless, it is the approach taken by the VGTS and TheWA, with considerable success. Moreover, it is an approach that could easily be taken with NeWS.

In addition to considering standard graphics packages, we must take account of the recent work by the ANSI X3H3.6 Committee on Display Management for Graphical Devices [39]. This work has focused on a variety of issues discussed in this report, primarily input models and allocation of the display between multiple applications. Indeed, their input model and display resource arbiter are quite similar to the input model and workstation manager, respectively, described here. Although this effort is still in an early stage, the obvious overlap between their work and the work reported in this paper makes it imperative that each group (participants at Seattle and members of X3H3.6) continue to track the work of the other group.

Historically, there have been four principal motivations for composing software systems out of multiple interacting processes:

Unfortunately (for the case of multi-process structuring), most if not all the benefits of modular decomposition accrue to contemporary data abstraction languages. Moreover, many early concurrent programming mechanisms, especially message-based systems, gained a reputation for poor performance and difficult-to-get-right programming.

However, more recent concurrent programming environments have, in general, overcome their performance and programming problems. That does not necessarily mean that passing a message is as cheap as a procedure call, for example, but that overall system performance degradation, if it occurs, is outweighed by the advantages of multi-process structuring. In particular, data abstraction by itself does not help when the system in question must deal with multiple threads of control — for example, input from multiple devices or output from multiple applications. In that case multiple processes, one for each thread, say, are preferred over one process that needs to multiplex itself between the threads — from an ease-of-programming point of view [13,19,27,31]. Without employing multiple processes it is also impossible to distribute a software system across multiple processors and, therefore, impossible to take advantage of any available parallelism.

Finally, suppose there were only two modules to worry about, the application and the workstation agent. There are three basic ways to ``connect'' these two modules:

Without repeating all the arguments, method 1 is simply incompatible with current trends in operating system design, and should not be considered for any but the most specialized applications environments. Experience with SunWindows provides ample evidence that method 2 suffers from three severe disadvantages [37]:

That leaves method 3, and the success of Andrew [22], X [38], NeWS [21], and other server-based window systems — for UNIX — leave little doubt as to the superiority of that method over the others — for any multi-tasking environment.

Therefore, we see no realistic alternative to employing multiple processes in the construction of interactive software — in the context of emerging hardware environments. The real issue is how to do so in such a way as to gain the indicated advantages while avoiding the twin perils of poor performance and ``difficult-to-get-right'' programming.

Historically, the mechanisms and paradigms for concurrent programming have fallen into three broad classes, based on their underlying memory architecture:

The first two classes represent two ends of the spectrum, with competing advantages and disadvantages. In shared-memory-based systems the interface to the various process interaction mechanisms is the procedure call. Data need never be copied, and creating, destroying and switching between processes in the same address space do not require significant memory map manipulation; hence the expression ``lightweight process.'' In disjoint-address-space-based systems the interface is the message,8 data needs to be copied, and creating, destroying and switching between processes requires a significant amount of memory map manipulation; hence the expression ``heavyweight process.'' Consequently, shared-memory-based mechanisms typically offer superior performance. Disjoint-address-space-based mechanisms, on the other hand, offer transparent distribution and better protection.

Achieving a more balanced mix of advantages and disadvantages suggests a hybrid system. In such systems, teams of (lightweight) processes share a single address space and may employ shared-memory-based mechanisms to interact with each other. Processes on separate teams interact via messages.9 A team, then, resides on a single host (including shared-memory multiprocessors) and its constituent processes can interact efficiently by virtue of their shared address space. However, the software system as a whole can still be distributed (and possibly made more reliable) by placing different teams on different hosts.

A typical server, for example, might employ separate processes on the same team for each outstanding ``connection'' (open resource) — each dialogue, or each display file, or each input stream, for example. In addition, helper processes might be employed as timers or to perform operations concurrently with the main server, such as repainting the contents of one window concurrent with processing updates to the display file associated with another window. In either case, each process can be ``single-threaded'' — taking a request and processing it to completion before asking for another request — and therefore be almost as easy to program as a typical sequential program. The choice of message-passing paradigm — in particular, whether asynchronous or synchronous — can lead to additional simplification; the reader is referred to [4] for an overview of the relevant issues.

The hybrid ``teams of processes'' paradigm was pioneered in the Thoth operating system [13,15] and employed in all of its descendants, including the V-System [6] and Harmony [20]. Examples of interactive software constructed for these systems are discussed in [5,7,9,24,25,41,42]. The same basic paradigm has also been adopted for the Argus [32], Eden [3], Verdix Ada [43], and Mach [36] systems, as well as by the innumerable groups who have developed ``lightweight process packages'' for UNIX — including those employed internal to the X and NeWS window servers. It should come as no surprise, then, that it is the basic paradigm we advocate for multi-process structuring.10

If the reader remains unconvinced as to the viability of the ``teams of processes'' paradigm for multi-process structuring of interactive software, it is probably due to remaining doubts as to the efficiency of interprocess communication between disjoint address spaces. We offer several observations to assuage those doubts. First, the reader should remember that the ability to distribute software across multiple processors, without fine-tuning the software for the particular hardware environment, can in fact improve performance — by virtue of parallelism or access to more powerful processors. Second, increasingly efficient techniques are being developed for exchanging messages between processes on the same machine. For example, numerous systems exist which, running on Motorola 68020-class hardware, can execute complete send - receive - reply transactions in under 1 millisecond. More importantly, evidence is accumulating that, whatever the costs of interprocess communication, it represents but a small piece of overall computation time (cf. [14,17,29]).

The remaining observations pertain to the situation where large numbers of separate events must be exchanged, as when many input or output events are being generated. If a separate message is sent for every event, then performance (in a single-machine environment) will naturally be slower than if each event resulted in a procedure call. Two fundamental techniques limit this degradation. First, wherever possible, multiple events should be batched in a single message. Second, wherever possible, messages should be pipelined; that is, replies should be eliminated. Experiments with the VGTS have shown order-of-magnitude performance improvement due to application of these techniques [29]. Similar observations have been made with respect to X and Andrew [22,37].

Applying the above techniques to a UIMS, we postulate the existence of at least three distinct teams (address spaces). One team contains the workstation agent, one contains the dialogue manager and there is one team for each application including the workstation manager. Within the workstation agent team, separate (lightweight) processes may be used for each device, or even for each input or output stream. However, each has access to the same queues, for example, by virtue of their shared address space. Similarly, within the dialogue manager team, separate processes may be used for each dialogue, but each has access to the shared databases needed to maintain user profiles, dialogue specifications and the like. The resulting architecture is precisely that of Figure 1(b), where ovals correspond to teams and the interconnections correspond to message paths (possibly hidden by stream interfaces or the like).

If, for efficiency reasons, three disjoint address spaces prove too many, we believe that a merger of the workstation agent and dialogue manager would be preferable, in most case, to a merger of the application and the dialogue manager. This merger still permits the UIMS to be run on one host, while the application(s) are distributed. From our experience, the required communication bandwidth within the UIMS is considerably higher than the necessary communication bandwidth between applications and the UIMS. Moreover, as in the case of SunWindows, merging the dialogue manager with the applications typically means merging each application with (a copy of) the dialogue manager, leading to a high degree of redundancy and potential synchronization problems. On the other hand, our experience may not bear out in the event that the dialogue manager becomes more tightly coupled with the application, as proposed in [16].

Fortunately, we believe that the cost of using disjoint address spaces in many systems is already sufficiently low as to render the efficiency argument moot, and that this trend will continue. Experience with the VGTS, TheWA, X, Andrew, NeWS and Adagio all support this observation, at least with respect to the use of disjoint address spaces for applications and the workstation agent.

Our proposed input model for the WA is based on reliable streams of input events. Physical devices produce events that ultimately are consumed by one or several clients at higher levels. By continuously monitoring the event stream, clients do, in principle, know the current state of the device. If, however, there are many events pending on the stream, this is no longer the case. To handle such situations, it may be necessary to let clients directly sample virtual devices. This can be done by adding additional ``entry points'' to the WA or by having ``modal'' streams.

With the exception of the QWERTY keyboard, physical input devices do not strongly follow any standards. For reasons of device independence the WA might define a set of logical input events onto which physical events may be mapped. The required functionality must permit the detection of state transitions of the physical devices and map these into the set of logical input events

While systems such as NeWS support the equivalent of procedural keymaps — where a client-provided function is executed on receipt of a particular physical event — we tend to believe that such functionality is best placed in the dialogue manager.

Direct manipulation interaction often uses a cut-and-paste paradigm to exchange information between different applications. In situations where the WA is retaining the output structures for the applications being modified11 and there is no additional semantic information associated with those structures, cut-and-paste can be effected entirely within the WA. This may even be true in the case of cutting information represented in one medium and pasting it (back) using another medium.

In most situations, however, applications expect to be informed as to all input, and both cutting and pasting constitute input. Sometimes, as when pasting text at the insertion point of the ``active'' window, the text can simply be inserted into the (active) client's input queue. In other situations the data may have to be handled ``out of band.'' If the operation is legal for the given application, it must update its internal data structures to reflect the user interaction. Otherwise, the application must undo the cut-and-paste operation as effected by the WA. In short, implementing universal cut-and-paste remains a open problem.

Different input devices may provide different types of information. For instance, a pointing device must contain a location, whereas a keyboard event may only contain its ASCII value. Event streams must accommodate events from all devices, so a choice must be made between placing variant records in the event stream or defining a single record format that accommodates all possible events. NeWS, in particular, takes the latter approach to its extreme, by encoding the entire state of the keyboard in every event record. It remains to be seen what effect this has on performance.