\documentstyle[6.033-ps,palatino,12pt]{article}
\title{Case Study One: The Winmany Server}
\date{March 19, 1991 (extended until March 21)}

\def\code#1{{\tt #1}}

\parindent=0in
\setallmargins{1.25in}
\def\baselinestretch{1.8}

\begin{document}
\titlepage

\section{Introduction}

In the design of the Winmany server, the most significant 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 efficient and
correct.  I will be using C style declarations for my pseudo-code.

\section{Data Represention}

This section describes the contents of the major data type in the
server.  However, no rationale is presented until Section
\ref{sect:exec}, 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.

\def\nl{\hfill\newline}
\begin{description}
\item[\code{Coord x,y,w,h;}]\nl
The location and size of the window, in tile units.

\item[\code{Tile *backingstore;}]\nl
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. 

\item[\code{RequestQueue requests;}]\nl
The queue of requests pending on this window.

\item[\code{Window *partner;}]\nl
If this window is over or under another window, then this element
points to that window's window structure.

\item[\code{Position pos;}]\nl
If the window has a partner, this variable determines if the window is
\code{Over} or \code{Under} its partner.
\end{description}

A \code{RequestQueue} is a queue of requests.  It is described in
detail in section \ref{sect:rq}.

\section{Locking and Synchronicity} \label{sect:rq}

The specifications 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
\code{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 fulfilled.

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:

\begin{enumerate}
\item A mutex and condition associated with the request are
created.

\item The mutex is locked.

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

\item 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.

\item The mutex is unlocked.
\end{enumerate}

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:

\begin{enumerate}
\item Dequeue a request/mutex/condition, waiting if none is available.

\item Lock the mutex.

\item Perform the request, storing return or error status in the
request.

\item Signal the condition, signifying that the request has been
completed.

\item Unlock the mutex.

\item Repeat.
\end{enumerate}

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.

\section{Execution} \label{sect:exec}

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.

\subsection{Initialization}

When the server is started, two threads are created.  The first
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 configure 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.

\subsection{WindowCreate and WindowDelete}

When \code{WindowCreate} is called, the thread enqueues a request on
the configure 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 \code{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 \code{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
\code{WindowDelete} thread), it enqueues a request on the configure 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.

\subsection{WindowSize and WindowMove}

Each of these calls enqueues a request on the window's RQ.  This
request in turn enqueues a request on the configure 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.

\subsection{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
\code{WindowPutGraphic}, then \code{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
\code{WindowPutStr} or \code{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 \code{WindowPutC}, a single request is enqueued on the display
RQ.  When all display requests have returned, the thread returns from
the caller.

\section{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 \code{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 efficiency.  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 significantly, 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.

\end{document}
