The X Window System ROBERT W. SCHEIFLER MIT Laboratory for Computer Science and JIM GETTYS Digital Equipment Corporation and MIT Project Athena An overview of the X Window System is presented, focusing on the system substrate and the low- level facilities provided to build applications and to manage the desktop. The system provides high- performance, high-level, device-independent graphics. A hierarchy of resizable, overlapping windows allows a wide variety of application and user interfaces to be built easily. Network-transparent access to the display provides an important degree of functional separation, without significantly affecting performance, which is crucial to building applications for a distributed environment. To a reasonable extent, desktop management can be custom-tailored to individual environments, without modifying the base system and typically without affecting applications. Categories and Subject Descriptors: C.2.2 [Computer-Communication Networks]: Network Pro- tocols-protocol architecture; C.2.4 [Computer-Communication Networks]: Distributed Sys- terns-distributedapplications; D.4.4 [Operating Systems]: Communication Management-network communication; terminal management; H.1.2 [Models and Principles]: User/Machine Systems- human factors; 1.3.2 [Computer Graphics]: Graphics Systems-distributed/network graphics; 1.3.4 [Computer Graphics]: Graphics Utilities-graphics packages; software support; 1.3.6 [Computer Graphics]: Methodology and Techniques-device independence; interaction techniques General Terms: Design, Experimentation, Human Factors, Standardization Additional Key Words and Phrases: Virtual terminals, window managers, window systems 1. INTRODUCTION The X Window System (or simply X) developed at MIT has achieved fairly widespread popularity recently, particularly in the UNIX1 community. In this paper we present an overview of X, focusing on the system substrate and the low-level facilities provided to build applications and to manage the desktop. In X, this base window system provides high-performance graphics to a hierarchy of resizable windows. Rather than mandate a particular user interface, X provides primitives to support several policies and styles. Unlike most window systems, the base system in X is defined by a network protocol: asynchronous ‘UNIX is a trademark of AT&T Bell Laboratories. Authors’ addresses: R. W. Scheifler, 545 Technology Square, Cambridge, MA 02139; J. Gettys, Project Athena, MIT, Cambridge, MA 02139. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 0 1987 ACM 0730-03Ol/S6/0400-0079 $00.75 ACM Transactions on Graphics, Vol. 5, No. 2, April 1986, Pages 79-109.
`
`Page 1 of 31
`
`SONY EXHIBIT 1021
`
`

`

`80 l FL W. Scheifler and J. Gettys stream-based interprocess communication replaces the traditional procedure call or kernel call interface. An application can utilize windows on any display in a network in a device-independent, network-transparent fashion. Interposing a network connection greatly enhances the utility of the window system, without significantly affecting performance. The performance of existing X implemen- tations is comparable to that of contemporary window systems and, in general, is limited by display hardware rather than network communication. For example, 19,500 characters per second and 3500 short vectors per second are possible on Digital Equipment Corporation’s VAXStation-II/GPX, both locally and over a local-area network, and these figures are very close to the limits of the display hardware. X is the result of two separate groups at MIT having a simultaneous need for a window system. In the summer of 1984, the Argus system [16] at the Laboratory for Computer Science needed a debugging environment for multiprocess distrib- uted applications, and a window system seemed the only viable solution. Project Athena [4] was faced with dozens, and eventually thousands, of workstations with bitmap displays and needed a window system to make the displays useful. Both groups were starting with the Digital VSlOO display [14] and VAX hardware, but it was clear at the outset that other architectures and displays had to be supported. In particular, IBM workstations with bitmap displays of unknown type were expected eventually within Project Athena. Portability was therefore a goal from the start. Although all of the initial implementation work was for Berkeley UNIX, it was clear that the network protocol should not depend on aspects of the operating system. The name X derives from the lineage of the system. At Stanford University, Paul Asente and Brian Reid had begun work on the W window system [3] as an alternative to VGTS [13, 221 for the V system [5]. Both VGTS and W allow network-transparent access to the display, using the synchronous V communi- cation mechanism. Both systems provide “text” windows for ASCII terminal emulation. VGTS provides graphics windows driven by fairly high-level object definitions from a structured display file; W provides graphics windows based on a simple display-list mechanism, with limited functionality. We acquired a UNIX- based version of W for the VSlOO (with synchronous communication over TCP [24] produced by Asente and Chris Kent at Digital’s Western Research Labora- tory. From just a few days of experimentation, it was clear that a network- transparent hierarchical window system was desirable, but that restricting the system to any fixed set of application-specific modes was completely inadequate. It was also clear that, although synchronous communication was perhaps accept- able in the V system (owing to very fast networking primitives), it was completely inadequate in most other operating environments. X is our “reaction” to W. The X window hierarchy comes directly from W, although numerous systems have been built with hierarchy in at least some form [ll, 15, 18, 28, 30, 32-361. The asynchronous communication protocol used in X is a significant improvement over the synchronous protocol used in W, but is very similar to that used in Andrew [lo, 201. X differs from all of these systems in the degree to which both graphics functions and “system” functions are pushed back (across the network) as application functions, and in the ability to tailor desktop management transparently. ACM Transactions on Graphics, Vol. 5, No. 2, April 1986.
`
`Page 2 of 31
`
`

`

`The X Window System l 81 The next section presents several high-level requirements that we believe a window system must satisfy to be a viable standard in a network environment, and indicates where the design of X fails to meet some of these requirements. In Section 3 we describe the overall X system model and the effect of network- based communication on that model. Section 4 describes the structure of windows, and the primitives for manipulating that structure. Section 5 explains the color model used in X, and Section 6 presents the text and graphics facilities. Section 7 discusses the issues of window exposure and refresh, and their resolution in X. Section 8 deals with input event handling. In Section 9 we describe the mechanisms for desktop management. This paper describes the version’ of X that is currently in widespread use. The design of this version is inadequate in several respects. With our experience to date, and encouraged by the number of universities and manufacturers taking a serious interest in X, we have designed a new version that should satisfy a significantly wider community. Section 10 discusses a number of problems with the current X design and gives a general idea of what changes are contemplated. 2. REQUIREMENTS A window system contains many interfaces. A programming interface is a library of routines and types provided in a programming language for interacting with the window system. Both low-level (e.g., line drawing) and high-level (e.g., menus) interfaces are typically provided. An application interface is the mechanical interaction with the user and the visual appearance that is specific to the application. A management interface is the mechanical interaction with the user, dealing with overall control of the desktop and the input devices. The manage- ment interface defines how applications are arranged and rearranged on the screen, and how the user switches between applications; an individual application interface defines how information is presented and manipulated within that application. The user interface is the sum total of all application and management interfaces. Besides applications, we distinguish three major components of a window system. The window manager3 implements the desktop portion of the manage- ment interface; it controls the size and placement of application windows, and also may control application window attributes, such as titles and borders. The input manager implements the remainder of the management interface; it con- trols which applications see input from which devices (e.g., keyboard and mouse). The base window system is the substrate on which applications, window managers, and input managers are built. In this paper we are concerned with the base window system of X, with the facilities it provides to build applications and managers. The following require- ments for the base window system crystallized during the design of X (a few were not formulated until late in the design process): 1. The system should be implementable on a variety of displays. The system should work with nearly any bitmap display and a variety of input devices. Our design focused on workstation-class display technology likely to be available in a ’ Version 10. 3 Some people use this term for what we call the base window system; that is not the meaning here. ACM Transactions on Graphics, Vol. 5, No. 2, April 1986.
`
`Page 3 of 31
`
`

`

`82 l R. W. Scheifler and J. Gettys university environment over the next few years. At one end of the spectrum is a simple frame buffer and monochrome monitor, driven directly by the host CPU with no additional hardware support. At the other end of the spectrum is a multiplane display with color monitor, driven by a high-performance graphics coprocessor. Input devices, such as keyboards, mice, tablets, joysticks, light pens, and touch screens, should be supported. 2. Applications must be device independent. There are several aspects to device independence. Most important, it must not be necessary to rewrite, recompile, or even relink an application for each new hardware display. Nearly as important, every graphics function defined by the system should work on virtually every supported display; the alternative, which is to use GKS-style inquire operations [12] to determine the set of implemented functions at run time, leads to tedious case analysis in every application and to inconsistent user interfaces. A third aspect of device independence is that, as far as possible, applications should not need dual control paths to work on both monochrome and color displays. 3. The system must be network transparent. An application running on one machine must be able to utilize a display on some other machine, nor should it be necessary for the two machines to have the same architecture or operating system. There are numerous examples of why this is important: a compute-intensive VLSI design program executing on a mainframe, but displaying results on a workstation; an application distributed over several stand-alone processors, but interacting with a user at a workstation; a professor running a program on one workstation, presenting results simultaneously on all student workstations. In a network environment, there are certain to be applications that must run on particular machines or architectures. Examples include proprietary software, applications depending on specific architectural properties, and programs manip- ulating large databases. Such applications still should be accessible to all users. In a truly heterogeneous environment, not all programming languages and programming systems are supported on all machines, and it is very undesirable to have to write an interactive front end in multiple languages in order to make the application generally available. With network-transparent access, this is not necessary; a single front end written in the same language as the application suffices. One might think that remote display will be extremely infrequent, and that performance is therefore much less important than for local display. Experience at MIT, however, indicates that many users routinely make use of the remote display capabilities in X, and that the performance of remote display is quite important. The desktop display, although physically connected to a single com- puter, is used as a true network virtual terminal; indeed, the idea of an X server (see the next section) built into a Blit-like terminal [23] is an intriguing one. 4. The system must support multiple applications displaying concurrently. For example, it should be possible to display a clock with a sweep second hand in one window, while simultaneously editing a file in another window. ACM Transactions on Graphics, Vol. 5, No. 2, April 1986.
`
`Page 4 of 31
`
`

`

`The X Window System l 83 5. The system should be capable of supporting many different application and management interfaces. No single user interface is “best”; different communities have radically different ideas about user interfaces. Even within a single com- munity, “experts” and “novices” place different demands on an interface. Instead of mandating a particular user interface, the base window system should support a wide range of interfaces. To achieve this, the system must provide hooks (mechanism) rather than religion (policy). For example, since menu styles and semantics vary dramatically among different user interfaces, the base window system must provide primitives from which menus can be built, instead of just providing a fixed menu facility. The system should be designed in such a way that it is possible to implement management policy in a way that is external to the base window system and external to applications. Applications should be largely independent of manage- ment policy and mechanism; applications should react to management decisions, rather than direct those decisions. For example, an application needs to be informed when one of its windows is resized and should react by reformatting the information displayed, but involvement of the application should not be required in order for the user to change the size. Making applications management independent, as well as device independent, facilitates the sharing of applications among diverse cultures. 6. The system must support overlapping windows, including output to partially obscured windows. This is in some sense a by-product of the previous require- ment, but it is important enough to merit explicit statement. Not all user interfaces allow windows to overlap arbitrarily. However, even interfaces that do not allow application windows to overlap typically provide some form of pop-up menu that overlaps application windows. If such menus are built from windows, then support for overlapping windows must exist. 7. The system should support a hierarchy of resizable windows, and an appli- cation should be able to use many windows at once. Subwindows provide a clean, powerful mechanism for exporting much of the basic system machinery back to the application for direct use. Many applications make use of their own window- like abstractions; some even implement what is essentially another window system, nested within the “real” window system. It is important to support arbitrary levels of nesting. What is viewed as a single window at one abstraction level may well require multiple subwindows at a lower level. By providing a true window hierarchy, application windows can be implemented as true windows within the system, freeing the application from duplicating machinery such as clipping and input control. 8. The system should provide high-performance, high-quality support for text, 2-D synthetic graphics, and imaging. The base window system must provide “immediate” or “transparent” graphics: The application describes the image precisely, and the system does not attempt to second-guess the application. The use of high-level models, whereby the application describes what it wants in terms of fairly abstract objects and the system determines how best to render the ACM Transactions on Graphics, Vol. 5, No. 2, April 1986.
`
`Page 5 of 31
`
`

`

`a4 l R. W. Scheifler and J. Gettys image, cannot be imposed as the only form of graphics interface. Such models generally fail to provide adequate support for some important class of applica- tions, and different user communities tend to have strong opinions about which model is “best.” It is extremely important to provide high-level models, but they should be built in layers on top of the base window system. Support for 3-D graphics is not listed as a requirement, but this is not to say it is unimportant. We simply have not considered 3-D graphics, owing to lack of expertise and lack of time. 9. The system should be extensible. For example, the core system may not support 3-D graphics, but it should be possible to extend the system with such support. The extension mechanism should allow communities to extend the system noncooperatively, yet allow such independent extensions to be merged gracefully. We believe that a window system must satisfy these requirements to be a viable standard in an environment of high-performance workstations and mainframes connected via high-performance local-area networks. X satisfies most of these requirements, but currently fails to satisfy a few owing to practical considerations of staffing and time constraints: The design and much of the implementation of the base window system were to be handled solely by the first author; it was important to get a working system up fairly quickly; and the immediate applica- tions only required relatively simple text and graphics support. As a result, X is not designed to handle high-end color displays or to deal with input devices other than a keyboard and mouse, some support for high-quality text and graphics is missing, X only provides support for one class of management policy, and no provision has been made for extensions. As discussed in Section 10, these and other problems are being addressed in a redesign of X. 3. SYSTEM MODEL The X window system is based on a client-server model (see Figure 1); this model follows naturally from requirements 2 and 3 in the previous section. For each physical display, there is a controlling server. A client application and a server communicate over a reliable duplex (S-bit) byte stream. A simple block- stream protocol is layered on top of the byte stream. If the client and server are on the same machine, the stream is typically based on a local interprocess communication (IPC) mechanism; otherwise a network connection is established between the pair. Requiring nothing more than a reliable duplex byte stream (without urgent data) for communication makes X usable in many environ- ments. For example, the X protocol can be used over TCP [24], DECnet [38], and Chaos [ 191. Multiple clients can have connections open to a server simultaneously, and a client can have connections open to multiple servers simultaneously. The essen- tial tasks of the server are to multiplex requests from clients to the display, and demultiplex keyboard and mouse input back to the appropriate clients. Typically, . . the server is implemented as a single sequential process, using round-robin scheduling among the clients, and this centralized control trivially solves many ACM Transactions on Graphics, Vol. 5, No. 2, April 1986.
`
`Page 6 of 31
`
`

`

`The X Window System l 85 Application GKS library X VDI X library Pseudo ttY Text editor VT100 Window emulator manager Text library X library X library X library Network X server Device library Keyboard Mouse f \ Screen L 1 Fig. 1. System structure. synchronization problems; however, a multiprocess server has also been imple- mented. Although one might place the server in the kernel of the operating system in an attempt to increase performance, a user-level server process is vastly easier to debug and maintain, and performance under UNIX in fact does not seem to suffer. Similar performance results have been obtained in Andrew [lo]. Various tricks are used in both clients and server to optimize performance, principally by minimizing the number of operating system calls [9]. The server encapsulates the base window system. It provides the fundamental resources and mechanisms, and the hooks required to implement various user interfaces. All device dependencies are encapsulated by the server; the commu- nication protocol between clients and server is device independent. By placing all device dependencies on one end of a network connection, applications are truly device independent. The addition of a new display type simply requires the addition of a new server implementation; no application changes are required. Of course, the server itself is designed as device-independent code layered on ACM Transactions on Graphics, Vol. 5, No. 2, April 1986.
`
`Page 7 of 31
`
`

`

`86 ’ R. W. Scheifler and J. Gettys top of a device-dependent core, so only the “back end” of the server need be reimplemented for each new display.4 3.1 Network Considerations It is extremely important for the server to be robust with respect to client failures. The server and the network protocol must be designed so that the server never trusts clients to provide correct data. As a corollary, the protocol must be designed in such a way that, if the server ever has to wait for a response from a client, it must be possible to continue servicing other clients. Without this property a buggy client or a network failure could easily cause the entire display to freeze up. Byte ordering [6] is a standard problem in network communication: When a 16- or 32-bit quantity is transmitted over an &bit byte stream, is the most significant byte transmitted first (big-endian byte order) or is the least significant byte transmitted first (little-endian byte order)? Some machines with byte- addressable memory use big-endian order internally, and others use little-endian order. If a single order is chosen for network communication, some machines will suffer the overhead of swapping bytes, even when communicating with a machine using the same internal byte order. Such an approach also means that both parties in the communication must worry about byte order. The X protocol uses a different approach. The server is designed to accept both big-endian and little-endian connections. For example, using TCP this is accomplished by having the server listen on two distinct ports; little-endian clients connect to the server on one port, and big-endian clients connect on the other. Clients always transmit and receive in their native byte order. The server alone is responsible for byte swapping, and byte swapping only occurs between dissimilar architectures. This eliminates the byte swapping overhead in the most common situations and greatly simplifies the building of client-side interface libraries in various programming languages. X is not unique in its use of this trick; the current VGTS implementation uses the same trick, and similar protocol optimizations have been used in various network-based applications. Another potential problem in protocol design is word alignment. In particular, some architectures require 16-bit quantities to be aligned on 16-bit boundaries and 32-bit quantities to be aligned on 32-bit boundaries in memory. To allow efficient implementations of the protocol across a spectrum of 16- and 32-bit architectures, the protocol is defined to consist of blocks that are always multiples of 32 bits, and each 16- and 32-bit quantity within a block is aligned on 16- and 32-bit boundaries, respectively. X is designed to operate in an environment where the interprocess communi- cation round-trip time is between 5 and 50 milliseconds (ms), both for local and for network communication. We also assume that data transmission rates are comparable to display rates; for example, to transmit and display 5000 characters per second, a data rate of approximately 50 kilobits per second (kbits/s) will be needed, and to transmit and display 20,000 characters per second, a data rate of ’ A back end has been implemented using a programming interface to X itself, such that a complete “recursive” X server executes inside a window of another X server. ACM Transactions on Graphics, Vol. 5, No. 2, April 1986.
`
`Page 8 of 31
`
`

`

`The X Window System l 87 approximately 200 kbits/s will be needed. Networks and protocol implementa- tions with these characteristics are now quite commonplace. For example, workstations running Berkeley UNIX, connected via lo-megabit-per-second (Mbit/s) local area networks, typically have round-trip times of 15 to 30 ms, and data rates of 500 kbits/s to 1 Mbit/s. The round-trip time is important in determining the form of the communica- tion protocol. Text and graphics are the most common requests sent from a client to the server; examples of individual requests might be to draw a string of text or to draw a line. Such requests could be sent either synchronously, in which case the client sends a request only after receiving a reply from the server to the previous request, or they could be sent asynchronously, without the server generating any replies. However, since the requests are sent over a reliable stream, they are guaranteed to arrive and arrive in order, so replies from the server to graphics requests serve no useful purpose. Moreover, with round-trip times over 5 ms, output to the display must be asynchronous, or it will be impossible to drive high-speed displays adequately. For example, at 80 characters per request and a 25-ms round-trip time, only 3200 characters per second can be drawn synchronously, whereas many hardware devices are capable of displaying between 5000 and 30,000 characters per second. Similarly, polling the server for keyboard and mouse input would be unaccept- able in many applications, particularly those written in sequential languages. For example, an application attempting to provide real-time response to input has to poll periodically for input during screen updates. For an application with a single thread of control, this effectively results in synchronous output and consequent performance loss. Hence, input must be generated asynchronously by the server, so that applications need at most perform local polling. The round-trip time is also important in determining what user interfaces can be supported without embedding them directly in the server. The most important concern is whether remote, application-level mouse tracking is feasible. By tracking, we do not mean maintaining the cursor image on the screen as the user moves the mouse; that function is performed autonomously by the X server, often directly in hardware. Rather, applications track the mouse by animating some other image on the screen in real time as the mouse moves. For round-trip times under 50 ms, tracking is perfectly reasonable, driven either by motion events generated by the server or by continuous polling from the application. With a refresh occurring up to 30 times every second, remote tracking is demonstrably “instantaneous” with mouse motion. For tracking to be effective, however, relatively little time can be spent updating the display at each movement, so typically only relatively small changes can be made to the screen while tracking. This is certainly the case for simple tracking, such as rubber banding window outlines and highlighting menu items. It might be argued that the ability to run application-specific code in the server is required for acceptable hand-eye coordination during more complex tracking. For exam- ple, NeWS [31] provides such a mechanism in a novel way. However, we are not convinced there are sufficient benefits to justify such complexity. Typically, complex tracking is bound intimately to application-specific data structures and knowledge representations. The information needed by the front end for tracking ACM Transactions on Graphics, Vol. 5, No. 2, April 1986.
`
`Page 9 of 31
`
`

`

`88 l R. W. Scheifler and J. Gettys is intertwined with the information needed by the back end for the “real” work; the information cannot be reasonably separated or duplicated. It is simply unreasonable to believe that applications will download large, complex front ends into a server; communication round-trip times are a reality that cannot be escaped. 3.2 Resources The basic resources provided by the server are windows, fonts, mouse cursors, and offscreen images; later sections describe each of these. Clients request creation of a resource by supplying appropriate parameters (such as the name of the font); the server allocates the resource and returns a 29-bit5 unique identifier used to represent it. The use and interpretation of a resource identifier are independent of any network connection. Any client that knows (or guesses) the identifier for a resource can use and manipulate the resource freely, even if it was created by another client. This capability is required to allow window managers to be written independently of applications, and to allow multiprocess applications to manipulate shared resources. However, to avoid problems asso- ciated with clients that fail to clean up their resources at termination (which is all too common in operating systems where users can unilaterally abort pro- cesses), the maximum lifetime of a resource is always tied to the connection over which it was created. Thus, when a client terminates, all of the resources it created are destroyed automatically. Access control is performed only when a client attempts to establish a connec- tion to the server; once the connection is established, the client can freely manipulate any resource. Since accidental manipulation of some other client’s resource is extremely unlikely (both in theory and in practice), we believe introducing access control on a per-resource basis would only serve to decrease performance, not to significantly increase security or robustness. The current access control mechanism is based simply on host network addresses, as this information is provided by most network stream protocols, and there seems to be no widely used or even widely available user-level authentication mechanism. Host-based access control has proved to be marginally acceptable in a workstation environment, but is rather unacceptable for time-shared machines.6 Each client-generated protocol request is a simple data block consisting of an opcode, some number of fixed-length parameters, and possibly a variable-length parameter. For example, to display text in a window, the fixed-length parameters include the drawing color and the identifiers for the window and the font, and the variable-length parameter is the string of characters. All operations on a resource explicitly contain the identifier of the resource as a parameter. In this way, an application can multiplex use of many windows over a single network connection. This multiplexing makes it easy for the client to control the time order of updates to multiple windows; if a separate stream was used for each window, time order could not be controlled without strong guarantees from the stream mechanism. Similarly, each input event generated by the server contains 5 To simplify implementation in languages built with garbage collection, high-order bits are not used. 6 It is interesting that professors at MIT have argued vociferously to disable all access control. ACM Transactions on Graphics, Vol. 5, No. 2, April 1966.
`
`Page 10 of 31
`
`

`

`The X Window System l 89 the identifier of the window in which the event occurred. Multiplexing over a single stream allows the client to act on events from multiple windows in correct time order; again, the use of a stream per window would not allow such ordering, even if the events carry timestamps. Numerous UNIX-based window systems [17,20,21,30,36] use file or channel descriptors to represent windows; window creation involves an interaction with the o