A window manager for workstations with bitmapped displays has been developed. It exploits the inter process communication mechanism of the 4.2 Berkeley Unix system, and the DARPA TCP/IP protocols to support remote access to windows. One user level window manager process runs on each workstation; it tiles the screen(s) with windows, and manages a mouse, keyboard and pop-up menus. Client processes make remote procedure calls requesting the window manager to create or destroy windows, and to draw text and graphics in them. The window manager asynchronously requests clients to redraw their images when windows change size.
You will get a better Gorilla effect if you use as big a piece of paper as possible.
Kunihiko Kasahara, Creative Origami.
The style of interactive user interface exploiting multiple windows, multiple processes, bitmap graphics, pop-up menus, and a mouse originated with the Xerox Alto, and has traditionally been confined to environments that, like the Alto, provide the application with memory bandwidth access to the bitmap.
Two examples demonstrate that a careful choice of interface substantially reduces the bandwidth requirement. Pike's window manager [51] for the Bell Labs BLIT terminal [50] provides multiple processes with a low level interface to a set of overlapping windows. All obscured pixels are remembered in the terminal, so that the window system can recover from changes in window arrangement without intervention by the application. The system provides adequate performance despite being driven over an RS232 link.
In a recent paper [36] Lantz and Nowicki describe a window system for a network including powerful personal workstations providing multiprocess interaction. Their system (VGTS) supports remote and distributed access to windows, and provides adequate performance despite the limited network bandwidth by maintaining a structured display file. The application specifies modifications to this file; the window system is responsible for recreating the image from the display file when required.
We present a window system that supports remote and distributed access to windows using the same underlying network technology as VGTS, but provides applications with a much lower level interface, similar to that of the BLIT. It differs from both systems, however, in that the window system maintains no memory of the image in a window other than the actual pixels. The application is notified whenever the window must be redrawn, and it must recreate the entire image. Despite this, the system provides adequate performance for many advanced user interface techniques, such as WYSIWYG editors. It also differs from both systems in that it is implemented entirely at user level in an unmodified widely used Unix system, Berkeley's 4.2 BSD [31].
After eighteen months of production use on a network of about 80 workstations, it supports a wide range of applications. Examples include a document preparation system providing dynamically reformatted text editing, diagram editing, and page preview facilities, an iconic interface to Unix commands, help facilities, mail, bulletin board and conference call programs, terminal emulator, clock, performance monitor, database query programs, and a range of educational applications. Client processes using the window manager to perform bitmap operations are portable, in the sense that they will run without source modification on any 4.2BSD system on the network, and device independent, in that they can have no a priori knowledge of the hardware being managed on their behalf.
The user of a workstation running this window manager sees one or more screens tiled with windows. The windows completely cover the screen, without overlapping one another. A user's initial window layout is specified in a profile file, though it may be changed at any time. Each window has a headline, containing an identification of the client program attached to it, and the machine the client is running on. As the mouse is moved, a cursor tracks it on the screen, changing as it moves from window to window, or as clients use it as a feedback mechanism. Characters typed on the keyboard appear in the window containing the cursor, assuming the window is one to which it is sensible to type. Characters typed at the clock, for example, simply disappear.
When the mouse buttons are pressed, various window-specific things happen; menus pop up, items are selected, objects move, and so on. Menus normally pop up on the down stroke of the middle mouse button. They appear near the cursor, overlapping the windows under them. A selection is made on the up stroke of the button whereupon the menu vanishes. While the mouse button is down the menu item under the cursor is highlighted. Menus form a hierarchy: any menu item may have a submenu, which will pop up nearby when the cursor is in the parent. If the cursor is moved into the submenu, the process repeats.
Using a window menu that appears when the middle button is pressed in a window headline, the user can change the size of a window and reposition it. A window may be hidden; it then appears as an item in a submenu and will reappear when selected. New windows may appear on the screen at any time, as client processes request them. They cause existing windows to be resized or hidden at the whim of the window manager; creating a window does not involve interaction with the user. In fact, users cannot create windows directly; they can only create processes that will create windows.
The client program interacts with the window manager by means of function calls, file descriptors, and signals. The design of this interface has two objectives.
The simplicity of the window manager client interface achieves three objectives:
Viewing resource requests as hints has three effects:
Clients see windows as rectangular spaces of integer coordinates in which they can draw. The window manager ensures that the origin of the space is at the top left of the allocated screen space, and that output outside the rectangle from the origin to (Xsize, Ysize) is clipped away. The client may inquire the values of Xsize and Ysize if it wishes to adjust its image to fit the allocated space.
Each pixel in this array may be regarded as containing one of a contiguous range of indices into the colour map. The client may hint as to the number of indices it requires, and inquire as to how many it has actually been given. It can manipulate the colour map entries corresponding to its current set of indices. On a monochrome display or a colour display without a hardware colour map manipulating these entries will have no visible effect.
Characters may be drawn into this pixel space in any of several fonts. A client may define a font using a string name (eg TimesRoman12), and the result will be a handle that may be used to select it. The window manager will use its best efforts to supply a suitable approximation. The client may inquire about the bounding box of any character in the font.
Whenever the window manager changes the allocation of resources so as to affect a particular client, that client is notified. It is expected to inquire what the new allocation is and redraw the image in its window to suit. The values that may have changed when a notification is received are:
Some of the functions used to pass control information between the client and the window manager are:
Define Window takes only one parameter, the host on which the window is to be created. It creates an inter process communication (IPC) channel between this process (the application) and the window manager process on the named host. It returns a handle giving access to the window's resources, actually a pointer to a structure containing information including the Unix file descriptor for the IPC channel.
Many parameters affect the initial allocation of resources to a newly created window. Conceptually, they are all defaulted, and the client must use the normal window manager calls to request changes. In practice, the window manager uses lazy evaluation of window creation, so that change requests made early in a window's history are likely to affect its initial allocation. Clients need not know the complete parameter set, an important consideration in an evolving system.
Clients are expected to deal with windows of any size. The size specification given in SetDimensions is only a hint. Either the user or the window manager may decide to change the size of the window, disregarding the hint. Clients allocated windows they cannot readily use are free to ask the user to change their size.
Notification that resource allocations have changed (for example, that a window has changed size) could be either synchronous, via synthetic input events, or asynchronous, via a Unix signal. Only asynchronous notification is currently implemented. The window manager makes no attempt to preserve the contents of the window being resized (or having other resources changed). There are two reasons for this apparent lack of courtesy:
A client may have many windows, but the window manager calls affect only the selected window. Newly created windows are selected automatically, but other windows may be selected at any time. This technique is common in graphics packages [5] [24]; it allows complex lookups without severe performance costs and shortens parameter lists (and thus messages).
Among the functions setting the attributes applied to graphic output are:
DefineFont takes as its only parameter the name of the font to be defined. For example TimesRoman12b defines 12 point Times Roman bold. If the font library does not contain exactly the required font, something close will be substituted. For example, TimesRoman12 may be substituted for TimesRoman12b if no boldface Times Roman exists. It returns a handle that can be used to select the font.
The value returned by DefineFont is actually a pointer to a structure that describes in great detail the properties of the font. It is important to note that fonts are window-specific. DefineFont("TimesRoman12b") in two different windows might return two different values if, for example, the windows were on two displays with different properties. Since the user may reposition a window from one display to another, the values in the font structure may change dynamically. They are obtained from the window manager, and are updated when the client is notified of a font change.
The client draws using a functional interface. The primitives available are:
Text is output using the normal Unix write system calls on the file descriptor for the window's IPC channel. It appears at the current (x,y) position using the selected font. There are routines for drawing strings relative to a positioning parameter. These apply only to the selected window. For example:
DrawString ( WindowWidth/2, WindowHeight/2,
BetweenLeftAndRight|Between TopAndBaseline, "Center");
draws the string Center centred vertically and horizontally in the current window. Use of DrawString obviates the need to remember parameters from the font structures that may change at any time.
Characters typed on the keyboard are routed by the window manager to the process owning the window containing the cursor. The client process can read them from the file descriptor for the window's IPC channel in the normal way.
When a menu item is selected, the effect is as if the response string had been typed. In this way, menus can easily be added to existing programs.
Whenever an interesting mouse event occurs, the untypeable character MouseInputToken appears in the input stream. The client should then call SawMouse to decode the following few characters. Interest masks and actions are composed by or-ing together values including LeftButton, DownMovement and UpTransition.
The window manager process maintains the state of all windows, performs all the primitive graphic operations, receives all mouse inputs, and routes keystrokes, menu selections, and redraw requests to the clients. It communicates with the clients via a remote procedure call (RPC) mechanism implemented using 4.2BSD sockets.
The client interface was designed with the idea of implementing it by mapping the bitmap and the display device registers into each client process. Unfortunately, the SUN 1.5 hardware we had could not save and restore the display registers on context switches, so the display could be mapped into at most one process. Thus, the window manager is currently implemented as a single user-process that communicates with the screen, mouse, keyboard and all the clients. We use the SUN-supplied device driver to map the bitmap and the display device registers into the window manager's address space. All other I/O uses standard 4.2BSD system calls. No kernel changes are needed.
A socket, as defined by 4.2BSD, is one end of a communication path. It has an associated type, naming domain, and protocol. The type defines the semantics of I/O operations on the socket; we use stream sockets, providing byte streams much like pipes. Every socket has a name and a protocol in some domain; we use the Internet naming domain and the TCP/IP protocol for compatibility with other machines. A socket may be connected to another socket having the same domain/protocol pair. A connection between sockets within one machine is much like a named pipe in other Unix systems. In fact, 4.2BSD implements pipes as connected pairs of sockets. The socket mechanism is especially elegant in that it makes inter-machine boundaries transparent. Neither the client nor the window manager really knows whether there is a machine boundary between them.
All window manager calls in the client turn into messages sent via these pipeline connections. (The RPC protocol is asymmetric, in that the window manager may not call the client.) The RPC protocol supports C-style parameter passing, with at most one variable-length argument (typically a string). Functions may return results directly, or through pointer arguments. The common operations are output primitives and attribute selections, which do not return values. These are accumulated in stdio buffers until explicitly flushed, or until a result is required. Typical interactions between the window manager and the client consist of a single message from the client containing many operations.
When the client requests the creation of a window, a communication path is set up to the window manager which creates a structure in its address space describing the properties of the window, but does not actually create a visible window until a request is received that requires its existence. Thus, the window creation heuristics can use any information sent to the window manager in the meantime.
The window creation heuristics use four parameters: the minimum height and width, and the preferred height and width. We have tried several sets of heuristics. The most complex, and one of the shortest lived, involved considering each window to be a rectangular frame with springs holding the sides apart. A system of equations was relaxed to minimize the energy in the compression of the springs. This was very uncomfortable to use - it almost always completely rearranged all windows every time a new window was created. The present heuristics pick one window and split it to give some of its area to the new window. The window to split, and the position and orientation of the split, are determined by minimizing an error function that attempts to balance areas and preserve aspect ratios.
Since the most frequent request to the window manager is to draw characters, the performance of this operation is crucial. Just as the remote procedure call mechanism batches together window manager requests, character drawing requests are batched together. The lowest level routines that draw characters then receive long strings. This allows the precomputation costs to be spread over many characters: clipping is done based on strings, not characters; and some RasterOp setup is removed from the inner loop.
A fon as used by DefineFont and the character drawing routines is broken into two parts: some general information about the font as a whole and an array of icons. The general information includes the name of the font and a maximal bounding box for all of the icons in the font. An icon is a drawing, in some representation, that may be placed on the screen. Usually these icons correspond to the shapes of characters from the ASCII character set, but they need not. There are many representations possible for an icon. For example, they may be described by a bitmap specially aligned for the SUN hardware or they may be described by a set of vectors. Icons are split into two parts: the type specific part, and the generic part.
The type specific part of an icon contains all the information that depends on the type of representation used for the icon, while the generic part contains the information that is independent of the representation. When a client program defines a font, the information returned to it contains only the generic information for each icon in the font: all of the type specific information is eliminated. This allows the window manager to implement a font in a way that is tuned to each type of display device while insulating clients from the differences and still allowing them sophisticated access to the properties of the font.
One of our applications is an editor [[23], similar in spirit to Bravo [35] or LisaWrite [8]. It deals with kerned, proportionally spaced fonts, left and right justification and filling, using redefinable style sheets similar to those of the Scribe [54] document formatter. Unlike Scribe, where formatting is a batch process, it reformats the document at every keystroke. One might expect that this would be feasible only if the editor had full knowledge of, and an intimate association with the hardware. However, only a small performance degradation is imposed by using IPC channels and our window manager.
The editor is fast enough to be used as a general user interface tool, in effect a replacement for the Unix teletype driver. Users generally use the Unix shell via a typescript manager implemented from the same code. It keeps a complete transcript of their session, permits scrolling, string search, and text to be cut and pasted. (The window manager provides a ring of cut buffers, permitting text cut from one window to be pasted into another, even across machine boundaries.)
Another application is a diagram editor, implementing primitives such as lines, arcs, ovals, boxes, arrows, and text. The primitives may be collected into symbols; both primitives and symbols may be placed in the diagram and linked by connectivity constraints at magic dots. Objects stay connected even though the dots are moved. The window manager supports this adequately except that dragging objects around the screen is too slow. (The mouse event has to pass through the window manager on its way to the diagram editor, and the response has to pass through the window manager on the way back. Three processes must be scheduled.) As a result, almost all users turn dragging off.
It is usual for window managers to permit windows to overlap [9] [38]. Tiling window managers are rare. Our decision to experiment with tiling was based on two observations of overlapping window managers in use:
It seems that only transient windows overlap others; the reason they do so is the disproportionate number of interactions needed to adjust the layout.
In contrast, the constraint that windows must tile the screen allows the window manager to use heuristics when allocating space for new windows, and to adjust the screen layout autonomously. The heuristics need not be complex, the user can override the window manager's decisions if the investment in interaction would payoff. A common complaint from users is that the layout process is unpredictable. We are experimenting with Cedar-style fixed-width columns of windows as an alternative. Clients are, of course, unaware of the layout policies being followed by the window manager.
Because the interface is at a very low level, the window manager provides clients with very few services. Fortunately, this has not deterred people from writing client programs. For many clients, the use of clipped and shifted pixel coordinates is natural and efficient. We expect also to provide a higher level interface, supporting floating point coordinate spaces, by means of a library.
It can be claimed that the requirement to redraw the window makes client programs more difficult to write, but experience with this and other systems [57] does not support the claim. Programs need to be restructured, moving the code that initially calculates scales and draws borders to a procedure that can be re-executed. It is more a matter of discipline than of extra work. New programs have no difficulty meeting this requirement.
Device independence is essential; the campus network will be an open system, and applications must operate on incompatible workstations. All access to the display hardware is mediated by the window manager, effectively insulating applications from its peculiarities [14]. The window manager currently has device drivers for three SUN displays, the earlier 1024 × 800 monochrome display with RasterOp hardware [10], the more recent 1152 × 900 monochrome display without RasterOp hardware, and the 640 × 480 colour, and for the MicroVAX display. Experience shows that it can normally be ported to a new display in less than a week.
When we discovered that we would have to implement the window manager using inter process communication (IPC) rather than direct access to the hardware, we expected the performance to be unacceptable. Traditionally, the use of IPC in Unix systems has had severe performance penalties. But, to our surprise, the performance of the window manager is respectable. Common operations. such as drawing text, scrolling and clearing windows are almost indistinguishable from the same operation performed directly on the hardware. Line drawing, and small RasterOps between the screen and client address space also work well. Drawing grids of individual points, and large RasterOps between the screen and a client run much too slowly, because of the large volume of data that must flow through the IPC connection.
Window manager calls which return values, requiring a full handshake between the two processes, typically take about 19ms each if both the client and the window manager are on the same machine. This slows to 22ms if they are on different machines. Most operations, however, do not return results and therefore do not require a full handshake. Notable among these are the frequently used drawing and attribute selection functions.
The Emacs text editor [22] provides an example of performance. It takes 360ms to redraw the screen completely when it is run on a SUN with direct access to the display. The same test under the window manager takes 530ms. This is 47% slower, which is hardly perceptible. Performing this test again with Emacs and the window manager on different machines yields an interesting result: the full redraw takes 390ms. Only 8% slower - the two machines are effectively dividing the computational load.
One item in the window manager's menu sends a redraw signal to all visible windows. With a typical screen layout of 6 windows, this takes about 2 seconds, scheduling among the window manager and the clients to repaint every pixel.
The reasons for the acceptable performance are simple:
Eventually we would like to move to a hybrid implementation: one in which a client may choose to use direct device access if the window is local. Even if direct device access is possible, most clients are unlikely to use it. Few need the extra performance, and loading the extra graphics library will make them much bigger. Above all, most will prefer to remain device independent.
There is a limit to the number of simultaneous clients that the window manager may service. It is imposed by the limit on the number of open file descriptors available to a Unix process. Each socket accessible to a Unix process uses one file descriptor. Typically Unix processes are limited to 20 file descriptors. The implementation of 4.2BSD allows this limit to be increased by recompiling the kernel, but only to 30. Normally the limit is not a problem; more than a half-dozen windows visible on the screen looks cluttered and confusing.
Unfortunately, we would like to support a large number of hidden windows, and each of these also takes up a file descriptor. We do not know of a satisfactory solution to the problem. One possibility that we considered was to use connectionless datagram sockets. The window manager would need only one socket on which to receive from all of its clients. The problem here is that at present only unreliable datagrams are implemented; datagrams get through with some probability between 0 and 1, exclusive.
An alternative is to pass the descriptors for closed windows in messages to another process. The window manager can then close the descriptor, sharing the limit on file descriptors among the visible windows only. We plan to experiment with a receiving process that maintains a window full of icons representing hidden windows and returns the appropriate descriptor to the window manager when one is selected for exposure.
Bob Sproull has been an invaluable source of advice. The other members of the ITC's User Interface group, Fred Hansen, Tom Peters, and James Peterson, rushed in where others feared to tread, and suffered the consequences. Bob Sidebotham, Andrew Palay, and Bruce Lucas have all implemented significant parts of the system as it now stands.
| Function | Description |
|---|---|
| wm_AcquireInputFocus() | force input focus to the current window |
| wm_AddMenu(s) | add s to menus in the current window |
| wm_BrushRegion(id) | brush save buffer id using mouse |
| wm_ClearWindow() | make the current window all white |
| c = wm_DefineColor(r,g,b) | get handle for colour (r,g,b) |
| wm_DefineColorElement(i,r,g,b) | colour element i becomes (r,g,b) |
| f = wm_DefineFont(f) | get handle for font f |
| wm_DefineRegion(id,x,y,w,h) | rectangle becomes region id |
| wm_DeleteWindow() | destroy the current window |
| wm_DisableInput() | typeing in the current window discarded |
| wm_DisableNewlines() | text off bottom lost (not scrolled) |
| wm_DragRegion(id) | drag save buffer id using mouse |
| wm_DrawString(x,y,op,s) | draw string s at (x,y) with alignment op |
| wm_DrawTo(x,y) | line from the current position to (x,y) |
| wm_Dump Region(id fn) | write save buffer id to file fn |
| wm_EnableInput() | typeing in the current window obtainable |
| wm_ExposeMe() | make the current window visible |
| wm_FillTrapezoid(xl,yl,w1,x2,y2,w2,f,c) | fill trapezoid with char c in font f |
| Ip = wm_FontStruct(f) | get pointer to info about font f |
| wm_ForgetRegion(id) | destroy save buffer id |
| wm_GetColorIndices(n) | *n gets size of colour map for the current window |
| wm_GetColorMap(n,cp) | fill cp[] with n colour map entries |
| wm_GetDimensions(w,h) | set (w,h) to size of the current window |
| wm_GiveupInputFocus() | previous window regains input focus |
| wm_HideMe() | make the current window invisible |
| wm_HandleAcquisition() | |
| fp = wm_infile(w) | get input file pointer for window w |
| wm_InvertRaster(dx,dy,w,h) | invert colours in destination |
| wm_LinkRegion(n,o) | region n becomes part of region o |
| wm_LoadRegion(id,fn) | read save buffer id from file fn |
| wm_MoveTo(x,y) | set the current position to (x,y) |
| wm_NameRegion(id,s) | region id gets name s |
| w = wm_NewWindow(h) | create window on host h |
| fp = wm_outfile(w) | output file pointer for window w |
| wm_print(x,y,op,f,a,...) | like print(f,a...) |
| wm_RasterOp(sx,sy,dx,dy,w,h) | perform current op on source and destination |
| wm_RasterSmash(dx,dy,w,h) | perform current op on destination |
| wm_ReadFromCutBuffer(n) | get size and contents of cut buffer n steps away |
| wm_RestoreRegion(id,x,y) | copy from save buffer id to screen |
| wm_RotateCutRing(n) | rotate the ring of cut buffers n steps |
| wm_Save Region(id,x,y,w,h) | save rectangle in buffer id |
| wm_SaveMouse(action,w,y) | decode mouse event from winin |
| wm_SelectColorlndex(e) | new output in colour index e |
| wm_SelectFont(f) | new output in font f |
| wm_SelectRegion(id) | current region of the current window becomes id |
| wm_Select Window(w) | make w the current window |
| wm_SetCharShim(s) | s pixels of shim between printing chars |
| wm_SetClipRectangle(x,y,w,h) | clip to rectangle within the current window |
| wm_SetCursor(f,c) | set cursor to char c in font f |
| wm_SetDimensions(minx,maxx,miny,maxy) | set preferred size of the current window |
| wm_SetFunction(f) | set current op to f |
| wm_SetMenuPrefix(s) | |
| wm_SetMouseGrid(n) | set mouse motion granularity to n |
| wm_SetMouseInterest(mask) | set mask for interesting mouse events |
| wm_SetMousePrefix(p) | |
| wm_SetPixelDepth(n) | set preferred depth of the current window |
| wm_SetProgramName(s) | set name in headline to s |
| wm_SetRawlnput() | do not buffer chars typed to the current window |
| wm_SetSpaceShim(s) | s pixels of shim between space chars |
| wm_SetStandardCursor(c) | set cursor to char c in font icon12 |
| wm_SetTitle(s) | set title in headline to s |
| wm_StdioWindow() | stdin/stdout is a window - select it |
| wm_StringWidth(s,x,y) | set (x,y) to far end of string s |
| wm_WriteToCutBuffer() | following null-terminated bytes to cut buffer |
| wm_ZoomFrom(x,y,w,h) |