Case Study One: The Winmany Server

Marc Horowitz

Section 4: Prof. Peter Elias

Luis Rodriguez

March 19, 1991 (extended until March 21)

1 Introduction

In the design of the Winmany server, the most signi�cant issues involved are derived from the issues of threads, locking, and synchronicity. This case study details my design in terms of data representations and locking, showing that it is both ef�cient and correct. I will be using C style declarations for my pseudo-code.

2 Data Represention

This section describes the contents of the major data type in the server. However, no rationale is presented until Section 4, when I describe exactly how the server handles locking shared resources.

The major data representation in the server is the representation of a window. The rep requires the following components.

Coord x,y,w,h; The location and size of the window, in tile units.

Tile *backingstore; A dynamically allocated array containing the contents of each tile ofthe window. A Tile is a tagged union containing either a char or a tilebits.

RequestQueue requests; The queue of requests pending on this window.

Window *partner; If this window is over or under another window, then this element points to that window’s window structure.

Position pos; If the window has a partner, this variable determines if the window is Over or Under its partner.

A RequestQueue is a queue of requests. It is described in detail in section 3.

3 Locking and Synchronicity

The speci�cations do not state if a request must be completed before the RPC returns to its caller. Since adding requests to force synchronization would complicate the server and force rewriting of clients, I chose to have each call return only when the action was completed or failed. In the case of failure, an exception handling mechanism needs to be added. In case of an error (for example, deleting an already deleted window), the server would signal an error back to the caller and continue on.

In order to provide for ordering of requests, while forcing the caller to block waiting for the completion of the request, a RequestQueue (RQ) is used. The thread which wishes an action to be performed calls a function to add a request to the queue. The call will not return until the request has been ful�lled.

The RQ is based on a normal queue, with mutexes protecting against multiple accesses, such as the one described in Birrell, 1989. A request is added to the queue as follows:

1. A mutex and condition associated with the request are created.

2. The mutex is locked.

3. The request, mutex, and condition are enqueued as a unit on the RQ, as described in Birrell.

4. The thread waits on the condition. Since only one thread can be waiting on a condition, only one thread will execute when it is signalled, and checking to see if the request has been completed is unnecessary. When the thread is signalled, any return or error status will have been encoded in the request.

5. The mutex is unlocked.

In this way, threads enqueue themselves on a RQ, waiting to be run. Obviously, something has to be executing the requests and signalling the conditions. Each RQ has one thread associated with it to perform these tasks. This thread continually executes the following algorithm:

1. Dequeue a request/mutex/condition, waiting if none is available.

2. Lock the mutex.

3. Perform the request, storing return or error status in the request.

4. Signal the condition, signifying that the request has been completed.

5. Unlock the mutex.

6. Repeat.

In addition, there is a special request for terminating the queue. After this request is enqueued, further requests will not be enqueued, but an error will be signalled immediately. Like any other request, the termination request will not continue until the thread has been terminated. When the thread executing the RQ sees the termination request in the queue, the loop servicing the queue exits to its caller.

4 Execution

Since there are so few calls available to the client, each is explained here. Implementation details are not given. Instead, synchronization and resource allocation are detailed.

4.1 Initialization

When the server is started, two threads are created. The �rst manages an RQ of requests for output to the display hardware (the display RQ). This RQ is necessary due to the constraints of the hardware. The second manages all window operations, such as creation, deletion, moving, and resizing (the con�gure RQ). This is necessary because the success of a window operation depends upon all the other windows, which means only one operation can take place at a time.

4.2 WindowCreate and WindowDelete

When WindowCreate is called, the thread enqueues a request on the con�gure RQ. This request, if overlapping and screen constraints allow, creates a Winmany window. When the request returns, the thread forks, and the child thread allocates the Window structure, and manages an RQ of requests for that window. The parent returns a handle to the client for use with that window. If the window cannot be created, then the thread does not fork, and an error is signalled to the caller.

When WindowDelete is called, the thread enqueues a termination request on the window’s RQ. When the request returns, the cleanup code has completed, so the thread can return to its caller.

When the window’s RQ receives a termination request (from a WindowDelete thread), it enqueues a request on the con�gure queue. This request does all the cleanup necessary to delete the window. It checks to see if the window is obscuring a partner window. If so, the thread enqueues a request in the display RQ to repaint the exposed area from the data in the partner’s backing store. It is necessary to enqueue this large request as a single request because otherwise, it would be possible for a new request to be overwritten by old data. Since the drawing requests maintain the backing store even if the window is obscured, these tiles are correct if blitted atomically. If the obscured window’s client has made a request to draw into the window, but this request has not been serviced, then the new tile will correctly overwrite the old tile. In all cases, the background is cleared, and partner pointers are updated. Finally, the window’s RQ’s thread is signalled.

4.3 WindowSize and WindowMove

Each of these calls enqueues a request on the window’s RQ. This request in turn enqueues a request on the con�gure queue to do the real work. When this request is serviced, if the request is invalid, an error is returned. Otherwise, the changes occur. Partner pointers are updated if necessary, and a single request containing all the backing store exposes and moves is enqueued on the display queue. When this completes, all of the nested requests complete, and the thread returns.

4.4 Drawing in Windows

These are this simplest of calls, since they do not require synchronization between windows. When a request is received, the request is enqueued on the window’s RQ. If the request is for a WindowPutGraphic, then RenderTile is called. Then, the tilebits or the character(s) are stored in backing store of the window. If the coordinates are not obscured by another window, requests are enqueued on the display RQ. If the request is one of WindowPutStr or WindowPutGraphic, each tile is a separate request. There is no possibility for a race condition, so this system allows more fair allocation of resources. If the request is WindowPutC, a single request is enqueued on the display RQ. When all display requests have returned, the thread returns from the caller.

5 Technical Issues

The design above assures both atomicity and synchronicity. Each part of the server which needs to have mutual exclusion has a thread running a RequestQueue which insures only one thread at a time is accessing the display, window, or other shared resource. Since the RQ will only allow one thread to access the resource at a time, access is both synchronous in the order requests were enqueued, and atomic,

There is an issue of ef�ciency. If many windows are created, then a thread is created for each, which can add up to a large number of threads. If many threads have requests pending, the number of context switches going on could make the performance of the server degrade badly. The best way to see if this is really an issue is to implement the Winmany server, and test its performance under different conditions. If context switches degrade performance signi�cantly, it may be necessary to rethink the implementation. This implementation is probably best on a system with a larger number of processors.

Another issue not addressed in this design is security. In this implementation, anybody who can make an RPC call to the server can do anything to any window. Given the lack of real calls (such as synthesizing events and querying window contents) the only attack which can be made is a denial-of-service attack. However, this is still a security problem, and if more calls are added to the protocol later, security can become more of an issue. The simplest implementation would involve having the client create a capability and pass it into the server when it created the window. The server could store this in the window structure, and only requests including the correct capability would be honored. All others would signal an error.