HomeQuestions?




A Tiling and Overlapping Window System




James L. Peterson




Software Technology Program
Microelectronics and Computer Technology Corporation (MCC)
3500 West Balcones Center
Austin, Texas 78759




20 November 1986





Introduction

Window systems are becoming quite commonplace. A window system controls access to a display terminal, allocating space on the display to multiple activities. This allows the (human) user to have several (possibly unrelated) programs running at the same time. The output of each program is displayed in its own window.

For example, Figure 1 illustrates an example display from a Sun workstation with 4 windows. One window runs a Unix shell process, another is an editor for this paper, a third is the formated version of this paper, and the fourth is a trace of cpu utilization.


Figure 1. Tiled Windows.


Window systems greatly improve the ease of working with a multi-process interactive computer system. Especially with a large high-resolution display, it is possible to have many windows on the display at the same time.

Initially, it is possible to create new windows by simply reallocating display space from any existing windows. This is a tiled window layout: each window is completely visible at all times. Figure 1 is a tiled layout.

Eventually, however, even with a large display (such as the Sun) and much sooner on a small display (such as the Macintosh), the user will want to open one more window when all display space is already allocated. A tiled layout is constrained by the sum of the size of all windows being no more than the total display size. In this case, the user can do one of several things:

  1. Attach additional displays to the system. A well-designed window system should be able to handle multiple displays as if they were one (larger) pool of display space to allocate. Of course this requires additional hardware, space, and money.

  2. Reduce the size of an existing window or set of windows, giving the display space to the new window.

The second alternative is the more common solution. Each window has some minimal reasonable size, however, depending on what the user is trying to do. Eventually some window or set of windows will have to be made smaller than its minimal size. In this case a number of alternatives are also available:

  1. A window can simply be made too small to be currently useful. It still occupies some display space, but when the user actively needs that window, it will need to be made larger. This, of course, will make some other set of windows too small, requiring them to be made larger when they are to be used, and so on.

  2. A window can be hidden (off-screen) with no display space allocated to it. When it is to be actively used, it will need to be re-allocated display space, taking that space away from some other window.

  3. The window can be hidden (off-screen) and replaced by an icon. The icon represents the window and takes some (hopefully small) display space. The presence of the icon reminds the user of the hidden window. To use the window, it must be opened which re-allocates display space to the window, again taking that space away from some other window.

  4. Windows can be allowed to overlap. An overlapping window layout allows windows to be placed "on top of" other windows, obscuring the overlapped parts of "lower" windows. To see the entire window, obscured windows must be brought to the top of the display, which will then obscure parts of other windows.

These mechanisms can, of course, be combined in many systems, so that a window system may allow windows to be made too small, hidden, overlapped, or represented by icons at the same time.

The debate between overlapped and tiled window layouts seems to be be in large part a religious argument: some people prefer overlapped windows while others prefer tiled windows [Hopgood et al 1986]. Some research indicates that many people will request an overlapped window layout even though they are more efficient with a tiled layout [Bly and Rosenberg 1986]. The best system might then be neither a tiled nor an overlapped system, but one which allows the user to select either (or both) layout approach.

In this note, we suggest a window layout model which is both tiled and overlapped. We then describe an implementation of this model. Our implementation is a modification of the Andrew window system [Gosling and Rosenthal 1984; Morris et al 1986] running on a Sun workstation with a color display.

Overlapped and Tiled Window Layout

Over several years of working with the Andrew window system, I found the following to be a common way of using the system. Over time, I used the computer system for several unrelated tasks. Each task might require several windows simultaneously. For example, a simple programming task might require an editor window on the program, a shell window for compilation and program execution, and a window to display the output of the program under development. All of these windows are needed at the same time and should be tiled to allow easy and immediate access.

A more complex programming task might require several editor windows on several related program files, windows displaying help information about system calls and libraries and several output windows to allow the current output to be viewed and compared with previous program outputs. Another task might be reading system bulletin boards with additional windows to send and read mail. Electronic mail often requires several windows since a mail inquiry may require searching through the file system to find relevant information for the reply.

In general, each task requires a set of windows. The tasks partition the complete set of windows for a user. Thus the tasks of a user define a partition of windows into window sets.

The set of windows for a particular task may change, over time, as new windows become necessary for a task, are used, and eventually are no longer necessary and are deleted. However, windows seldom move from one task set to another, in my experience. Occasionally, a window which is part of one task set may become the center of a separate task (a large sub-goal or digression from the original task) and may then result in the creation of a separate set of windows for this new task.

Since each window for a particular task is necessary for that task, the windows within a window set should be tiled. However, the window set of one task is unrelated to the window set of another task, and since the user can only direct his attention to one task at a time (with relatively infrequent and obvious switching between tasks), separate window sets can be overlapped.

Tasks may be long-lived or short-lived. I may be working on several projects at a time (working on a program, writing a technical paper, preparing class notes, reading mail -- which tends to spawn many short-lived tasks -- and so on), so I may have several window sets. Some window sets last for weeks while others are created, used, and deleted in minutes.

In the extremes, this layout model includes both traditional tiled and overlapped systems. If all windows are in the same window set, the layout is completely tiled. If each window is in its own window set (a singleton set), the layout can be completely overlapped.

Implementation

Our implementation of the window sets model of overlapped and tiled window layout defines a number of virtual screens. A virtual screen is the save size as the physical display screen.

At any given time, the user has selected a particular virtual screen. The selected virtual screen is shown on the physical display. If the user changes the selected virtual screen, the contents of the old virtual screen are saved and the newly selected virtual screen is displayed.

The physical display can be thought of as a viewing port onto the virtual screens: it can allow the user to see any one of the virtual screens at a time, but only one. Alternatively, the virtual screens can be considered to be paged into and out of the physical display, much like a demand-paged memory management system.

Virtual screens are selected (in our implementation) by the user. We have two selection methods.

  1. A set of function buttons on the keyboard can select a particular virtual screen, causing it to be displayed. For example, on our Sun workstations, function keys F1, F2, F3, ..., F8 can be used to select and display the associated virtual screen.

  2. We also use the mouse to select virtual screens. If the mouse moves "off the edge" of the current virtual screen, a table is consulted to determine a new virtual screen. The table defines the topology of the virtual screens. In our implementation, the user can define, for each virtual screen, the virtual screen to its left, right, above and below.

Using either, or both, of these techniques, the user can quickly select from the set of virtual screens. Each window set is tiled onto a virtual screen. When the user switches from one virtual screen to another, the corresponding window set immediately appears.

There are many ways to actually display a selected virtual screen on the physical display. This is the key to the window set model. Switching from one virtual screen to another must appear almost instantaneous.

Our first approach was to simply ask the client program for each window in the selected window set to re-display itself. This requires no extra work for the window manager and each client program should be prepared to redraw itself when necessary anyway. However, this approach can be painfully slow. The process for each window in the selected window set must be signaled by the window manager, scheduled by the operating system, paged in by the paging algorithms, and then must recompute its display image.

Our next approach to switching virtual screens is to maintain an up-to-date image of each virtual screen in memory and to copy this image to the physical display as necessary. When a new virtual screen is selected, the old virtual screen must be copied from the physical display into memory and the new virtual screen must be copied onto the physical display. If a copy of the current virtual screen is kept updated in memory as well as on the screen, then only one copy is needed. Even so, this approach is too slow for large bit-mapped displays, such as the Sun. For small, character oriented displays, the performance of this approach is quite reasonable.

With a little hardware help, the copying can be completely avoided. For example, if the display is refreshed from main memory, then we need only to be able to reset where in memory the display is located. This is easily supplied by a base register. With a base register, each virtual screen is continually updated in main memory. To switch from one virtual screen to another, we need only change the base register to point to the memory for the selected virtual screen. The display change is effectively instantaneous (one screen refresh time).

In general, the virtual screen model cannot be efficiently implemented without hardware help, and few displays provide such hardware base registers. However many color display terminals provide hardware which is almost as good, although it was not provided for this reason. The Sun color display, for example, is typical of many color displays. The display needs 24 bits per display pixel: 8 bits of red, 8 bits of green, and 8 bits of blue. To reduce memory requirements, however, only 8 bits is stored for each pixel. This 8-bit value is an index (0 to 255) into a color map table of 24-bit color values. By reloading the color map, any color can be obtained, but only 256 distinct colors may be on the screen at any one time.

The sun color display allows the color display memory to be viewed as 8 1-bit bit planes -- each bit plane is the size of the physical display. The color map index for a given pixel is determined by the 8-bit value selected by picking one bit from each bit plane to define the 8-bit color map index.

At MCC, we have modified the Andrew window manager to consider each of the separate bit planes as a separate virtual screen, allowing up to 8 virtual screens. Each virtual screen is black and white (not color) and so only needs one bit to specify each pixel. Each virtual screen is kept updated in the appropriate bit plane of the display memory.

A given virtual screen can be selected and displayed by careful setting of the color map. For example, suppose that the first 128 entries of the color map are set to black and the last 128 entries are set to white. For this color map, only the bits in the top bit plane can affect the color displayed on the screen. That is, any 8-bit color index of the form 0xxxxxxx will display black and any 8-bit color index of the form 1xxxxxxx will display white. Only the top bit plane (the first virtual screen) affects the image on the display. Similarly if all even (xxxxxxx0) color map entries are set black and all odd (xxxxxxx1) color map entries are set white, only the bottom bit plane (the last virtual screen) defines the image on the display.


Figure 2. Each bit plane of the color display memory can store a separate black and white virtual screen.


In general, a specific pattern of black/white color map entries can be defined for each bit plane (virtual screen) to make it visible on the display (and all others invisible). Changing to a new virtual screen only requires loading a new color map, a very fast operation.

Notice that it is not necessary to restrict virtual screens to black and white -- any two colors (background/foreground) will do. In fact, we find it convenient to define each virtual screen to have different background/foreground colors to aid in identifying them.

In general, it would be possible to break an 8-bit color map up into a number of colored virtual screens also. For example, one 8-bit color map could provide:

Summary

Both tiled and overlapped window layout systems are in use. We have suggested that window layout which is both tiled and overlapped might be preferable, and presented a model of such as system based upon window sets. All windows within a window set are tiled, but separate window sets may be overlapped. We have implemented such a system on a color display by using the color map to select and display a particular virtual screen. Each window set is tiled onto a virtual screen; virtual screens overlap.

Bibliography

HomeComments?