\section{Other Approaches}

In this section we discuss other approaches for handling transactions
in a multiple processor setting. The principle issues addressed are
using the clarity of the functional programming style as much
as possible, and achieving a high degree of concurrency, specifically
overlapping the execution of transactions. First we consider ways
in which M-structures may be used to implement the
integer set example, then we discuss how it might be implemented
in a conventional shared-memory multiprocessor.

\subsection{Programming with M-Structures}

One alternative to extend functional programming for
nondeterminate computation is to introduce updateable objects
called {\em M-Structures}~\cite{Barth92}. Every M-structure
location is either {\em empty} or {\em full}.  An M-structure 
{\em take} operation on an empty
slot suspends. A {\em put} operation to an empty slot simply
writes a value in the slot and
makes the slot {\em full} if no pending {\em take} operations are waiting.
Otherwise, the value is passed to one of the suspended {\em take}
operations, and
the slot is again {\em empty}. A {\em put} to a full slot is an error.

Below is how the integer set example can be written
with M-structures.  Since search is a pure function (no M-structure
operation is needed), we only give code in Id for the insert operation.\footnote{
We expect to use the pH language \cite{NikhilEtAl94} to present this version
in the final paper.}
\begin{verbatim}
  define Insert set n =
    if (MNil? set) then
       MCons n nil
    else
      { m = set.MCons_1;
        IN
      if m > n then
      MCons n set
      else
L:      {set!MCons_2 = insert set!MCons_2 n;
       IN
          set
      }
    }
\end{verbatim}
Note that, in line {\tt L}, the `{\tt !}' on the left-hand-side means M-structure
{\em put} and on the right-hand side means an M-structure {\em take} operation.
See \cite{NikhilArv90} for cetails concerning I-structures
in Id. Note that the M-structure {\em put} operation is an
in-place update, so there is no copying.

To highlight the difference of the above code from our solution,
consider what happens when several concurrent insert
or search operations
are present. In our solution, once a command (insert or search)
is presented to the critical section, its effect is fully determined,
and the results do not depend on the relative speed of execution of each
command. The nondeterminacy is confined to  the interleaving
of the several commands by the operation of the {\tt Transact} module.

The same cannot be said for the M-structure solution.
In fact, if there are two concurrent insertions, say S1 and S2,
it is possible for S1 and S2 to continue to leapfrog each other toward
the end of the list.  The result of a concurrent search operation,
if present, depends on the speed of its execution relative to any
concurrent insert operations.

Our solution is consistent with the usual
semantics for database transaction processing. The results are
the same as in the sequential run in which each transaction is
executed completely before any other is allowed to start.
On the other hand, when M-structure operations are used to
modify parts of the shared state in place, we know of no
general methodology for ensuring that the semantics of
database transactions are satisfied.

It may be that our solution using a guard and
functional operations performs more memory allocation operations
than does the M-structure code using
transaction operations written in a non-functional style.
However, in our solution, additional memory is actually
needed only when overlapped transactions are in progress.
When such a situation arises, we suspect that
the M-structure code will incur some extra cost for M-structure coordination.
If this cost involves allocation steps it may as expensive as
copying. Of course, one alternative is to implement our {\tt Transact}
module using an M-structure variable in place of a guardian, but we
believe using the {\tt SWAP} operation is both simpler and more
efficient.


\subsection{Programming Integer Set in a Shared-Memory Environment}

Here we consider how multiple invocations of the insert and search
operations may be handled on a cache-coherent shared-memory
multiprocessor computer. We assume that all processors share
a common address space, so each processor is able to
execute any procedure present in the memory. We assume that
processes use the standard semaphore operations P and V to
implement the necessary coordination. The system must guarantee
(through its cache coherence machinery) that in execution of
the code sequences
{\small\begin{verbatim}
      P1             P2

    write x         P(s)
    V(s)            read x           
\end{verbatim}}
by processors P1 and P2, whenever execution of V
by P1 causes execution of P by P2, the value of x read by P2
is always identical to the value written by P1. (There must
be no failure due to races in the memory network.)

The simplest solution is to use a single mutual exclusion semaphore
that permits one process at a time to execute the insert or
search function. This has the drawback that no concurrency of
transaction execution is achieved, but the advantage that
only one instance of the list representing the integer set
exists at any time.

Now let us consider how we might construct an implementation 
such that transactions could overlap as in our solution
using a guardian. There are two parts to the problem.
The first is entering the
commands into a common stream. This part can be done using
a mutual exclusion semaphore guarding a critical section that appends
a new input record to a queue.

The second part is the coding of a daemon process that
will yield overlapped execution of the insert and search operations.
For concurrent operation of commands, we suppose a separate
process is associated with the execution of each transaction.
Two problems must be dealt with:
(1) Making sure that each process is given the right instance of
the set list. (2) Making sure that, if an insert operation is active,
then each subsequent operation waits at each node until the
node becomes defined.

Part (1) is done by a process that takes entries from the queue
and either (a) starts a search process using the current
list of set elements, or (b) initializes a new list and starts
an insert process building the new list from the current one; the
new list is made the current list for subsequent queue entries.
 
To do part (2), we need a synchronization mechanism that permits
any number of search and insert operations to pause at a list node
with undefined contents. These operation are allowed to continue
just when the creator of the node (some earlier insert process)
has defined the node contents, effectively simulating an I-structure
variable.

In summary, if concurrency of transactions is not essential,
transaction processing may be implemented using functional
operation modules and a single mutual exclusion semaphore.
However, it appears difficult to code for overlapped execution
of transactions (other than multiple readers) without resorting
to methods that lack the elegance and simplicity of the functional style.
