Check out the new USENIX Web site. next up previous
Next: Remaining Safety Issues Up: Automation of Persistence Previous: Memory Management


External Data

When a program communicates with its environment, this often involves the creation of some external state that is not under the control of the program's runtime system. In case of the Spotless VM this typically concerns PalmOS structures such as windows, forms or databases. In this section, we introduce a protocol that provides automatic control over the life cycle of external state.

In order for external state to use our protocol, it has to be encapsulated in an instance of a developer-defined class that implements the interface External as shown in figure 5. We then regard an External as consisting of two sub-states:

External state:
data external to the persistent store and references thereof. This also includes attributes representing operating system structures, such as a file descriptor or a form handle that will usually be invalid after the store has been suspended.

Internal state:
a representation of the external state that is not dependent on any data structures outside the control of the persistent store. The External must be able to reconstruct its exact external state from the internal state including, for example, the read/write position of a file handle.

An External has to synchronize its internal state with its external state when the store is suspended and vice versa when it is resumed. In order for this to be performed in a thread-safe manner Spotless was adapted to use a protocol adopted from the Tycoon-2 system [Weikard, 1998,Gawecki and Wienberg, 1998] and implemented in the ExternalManager singleton class.3

All state transitions of Externals are controlled by a global ExternalManager. By adhering to this control center's protocol, the external state of a computation can be internalized on suspension and re-established on resumption in a manner that prevents inconsistencies. Figures 5 and 6 show the pertinent interfaces.

Figure 5: The Interface for External Resources
\begin{figure}
\hbox{
\vbox{ \makebox[\columnwidth]{
\epsfig{figure=listing-external,width=\columnwidth}} } }
\end{figure}

Figure 6: Major Methods of the ExternalManager Class
\begin{figure}
\hbox{
\vbox{
\makebox[\columnwidth]{
\epsfig{figure=listing-externalmanager,width=\columnwidth} }
}
}
\end{figure}

All four methods shown in Figure 5 must be implemented by an External to participate in the External protocol. By calling the method createExternal, the ExternalManager asks the External to create its external state. An External representing a database would, for instance, issue the appropriate OS call to open the database. The call internalizeExternal tells the External to internalize all external state, e.g., read the position in a database into an slot so the current state can be reestablished later. By calling recreateExternal, the External is asked to recreate its external state from its current internal; and by calling destroyState, the External is asked to destroy its external state, e.g., close the associated database.

Figure 7: Life cycle of an External
\begin{figure}
\hbox{
\vbox{
\makebox[\columnwidth]{
\epsfig{figure=statechart,width=\columnwidth} }
}
}
\end{figure}

The above four methods are invoked exclusively by the ExternalManager during different state changes of the persistent store. This means that in order to create external state, the External has to register with the ExternalManager using the call createAndRegisterExternal. The ExternalManager will in turn call back to the External method createExternal. Unregistration is regulated in a similar manner.

Figure 8: Registering with the ExternalManager
\begin{figure}
\hbox{
\vbox{
\makebox[\columnwidth]{
\epsfig{figure=register,width=\columnwidth} }
}
}
\end{figure}

Figure 7 shows the major state transitions from the perspective of an External. Figures 8 and 9 show examples of a database class registering and unregistering with the ExternalManager.

Figure 9: Unregistering from the ExternalManager
\begin{figure}
\hbox{
\vbox{
\makebox[\columnwidth]{
\epsfig{figure=deregister,width=\columnwidth} }
}
}
\end{figure}

To avoid deadlocks at stabilization, the order in which the monitors (object locks engaged by the synchronized keyword) of the External and the ExternalManager are acquired is crucial. In the examples, a thick lifeline denotes a locked monitor, a thin one a free monitor.

The rationale for the stabilization protocol is as follows:

1.
While a mutator thread is performing work on an External, its could potentially be in an inconsistent state. This prevents us from simply stopping all mutator threads before stabilization, i.e. stabilization must be performed in the running system.
2.
After external state has been internalized, no mutator thread must be allowed to manipulate the External. Consequently, the stabilizing thread must hold on the External's monitor after internalization.
3.
No External may be registered or unregistered during stabilization. 4
This leads to the following protocol: when the Spotless store is stabilized (which is triggered by the user changing to another application), the ExternalManager is first locked. After that, it gives all registered Externals the chance to internalize their external state in the reverse order to that in which they registered with the ExternalManager. This is performed by (i) acquiring the External's monitor and (ii) sending the External the internalizeExternal message. At stabilization time, all Externals' monitors are held.

On application resumption the process proceeds in the reverse order. The ExternalManager will (iii) send the External the recreateExternal message and will then (iv) release the object's monitor. The recreation messages are sent in the same order in which the createExternal methods were once invoked.

To avoid deadlocks involving a stabilizing thread it is necessary that the ExternalManager object is always locked before the External. Note that the new, _open and _close methods in the examples are not synchronized. In general, no method that calls createAndRegisterExternal or unregisterAndDestroyExternal may synchronize on the External or else a deadlock is possible.

Figure 10 illustrates the stabilization process with two registered Externals. Note that the thick line representing the lock on the External is actually starting before the subsequent invocation of the stabilizeStore method and is held until the ExternalManager sends the recreateExternal call. Also note the use of persistent threads: the stabilizing thread is simply frozen by calling stabilizeStore; it holds on to its locks until it is resumed and then continues execution.

Figure 10: Performing the ExternalManager.stabilize Operation
\begin{figure}
\hbox{
\vbox{
\makebox[\columnwidth]{
\epsfig{figure=checkpoint,width=\columnwidth} }
}
}
\end{figure}

Recapping this section we observe that the External protocol offers a thread-safe way to manage a persistent application's external data. It provides an atomic registration/unregistration mechanism and is instrumental in preventing deadlocks and the persistence of inconsistent state.


next up previous
Next: Remaining Safety Issues Up: Automation of Persistence Previous: Memory Management

2001-02-27