These are technical reports for the joint University of Stirling and University of Sydney Grasshopper project.
The following technical reports are available:
Alan Dearle, John Rosenberg, Frans Hensksens, Francis Vaughan, Kevin Maciunas
In this paper, operating system support for persistent systems that execute on conventional hardware architectures is examined. The focus of the paper is to examine the inadequacies of traditional operating systems as vehicles for the construction of persistent systems. We concentrate on four major areas; namely, addressing, stability and resilience, process management and protection. We examine the consequences of making the operating system kernel itself persistent. We conclude by outlining the requirements which must be met by future operating systems designed to support orthogonal persistence.
Proceedings of the 25th Hawaii International Conference of System Sciences, Volume 1, ed. V. Milutinovic and B.D. Shriver, IEEE Computer Society Press, Hawaii, U.S.A, pp. 779-789, 1992
Francis Vaughan, Alan Dearle
Persistent programming systems are generally supported by an object store, an conceptually infinite object repository. Objects in such a repository cannot be directly accessed by user programs; to be manipulated they must be fetched from the object store into virtual memory. Thus, in these systems, two different kinds of object addresses may exist: those in the object store and those in virtual memory. The action of changing object store addresses into virtual memory addresses has become known as pointer swizzling and is the subject of this paper.
The paper investigates three approaches to pointer swizzling: a typical software address translation scheme, a technique for performing swizzling at page fault time and finally a new hybrid scheme which performs swizzling in two phases. The hybrid scheme supports arbitrarily large pointers and object repositories using conventional hardware. The paper concludes with a comparison of these approaches.
Proceedings of the 5th International Workshop on Persistent Object Systems, San Miniato, Italy, September 1992. To appear in Springer-Verlag Workshops in Computing series.
This technical report has been superseded by Grasshopper Technical Report GH-10 which appears in Computer Systems 7,3. GH-03 contains material not included in GH-10. In areas of conflict GH-10 is definitive.
Alan Dearle, Rex di Bona, James Farrow, Frans Henskens, Anders Lindstrom, John Rosenberg, Francis Vaughan
For ten years researchers have been attempting to construct programming language systems that support orthogonal persistence above conventional operating systems. This approach has proven to be poor; researchers invariably construct a complete abstract machine above the operating system with resulting loss of efficiency. This paper describes a new approach, the construction of an operating system designed to support orthogonal persistence. The operating system, Grasshopper, relies upon three powerful and orthogonal abstractions: containers, loci an capabilities. Containers provide the only abstraction over storage, loci are the agents of change, and capabilities are the means of access and protection in the system. This paper describes these three fundamental abstractions of Grasshopper, their rationale and how they are used.
Persistent systems support a single storage abstraction in which all data may be created and manipulated in a uniform manner, regardless of its longevity. Grasshopper is a new operating system specifically designed to support persistent systems on a conventional workstation platform. In this paper we describe the capability-based protection mechanism employed in Grasshopper. We show that this mechanism provides sufficient power and flexibility to handle a variety of protection scenarios.
Proceedings of the 6th International Workshop on Persistent Object Systems, Tarascon, France, September 1994. To appear in Springer-Verlag Workshops in Computing series.
In this paper we describe a new persistent distributed operating system. The Grasshopper system is designed to allow flexibility in the way in which persistence is provided. A key element of this flexibility is concerned with issues of global consistency. The Grasshopper kernels cooperate with user level entities in order to maintain and find globally consistent states using vector time. Further flexibility is provided by allowing the kernels to implement either eager or lazy consistency policies.
Proceedings of the Seventeenth Annual Computer Science Conference, ACSC-17, Part B, ed Gopal Gupta, Christchurch, New Zealand, pp 409-420, 1994.
Disk drivers are rapidly increasing in complexity and decreasing in understandability. We present a new design for the organisation of disk drivers based on a module paradigm. Disk drivers are constructed in modules that may be placed in the order that best fulfils an application's requirements. We show that a simple interface between the modules leads to a powerful mechanism for building disk drivers.
Proceedings of the Seventeenth Annual Computer Science Conference, ACSC-17, Part B, ed. Gopal Gupta, Christchurch, New Zealand, pp 355-362, 1994.
The Grasshopper operating system provides a flexible environment for conducting research into orthogonal persistence. In particular, it allows user-level software to perform memory management so that new techniques may be investigated without having to modify or even reboot the kernel. We describe the facilities provided to support this and show how they are used by both the kernel and user-level software.
Proceedings of the Seventeenth Annual Computer Science Conference, ACSC-17, Part B, ed. Gopal Gupta, Christchurch, New Zealand, pp 343-354, January 1994.
Alan Dearle, Rex di Bona, Anders Lindstrom, John Rosenberg, Francis Vaughan
Provision of orthogonal persistence as an intrinsic attribute of a new operating system (Grasshopper) is addressed. An abstraction of data called the container is used to represent all data within the operating system. A user level entity called the manager is responsible for the data within containers. Managers have low level access to physical memory through kernel supported abstract data types, providing for safe and efficient management of data in user address spaces. The system kernel, in consort with managers provides a mechanism in which managers are free to use different mechanisms to provide recoverable and stable container data, whilst ensuring that new global recoverable states are created. The mechanism provides explicit support for recovery from input logs as well as simple snapshots of container state. Managers are provided with mechanisms that allow them to control execution within containers ensuring deterministic replay from logs. The entire system provides an environment where user level code never perceives any artefact of the persistence or recovery mechanisms.
Anders Lindstrom, Alan Dearle, Rex di Bona, Stephen Norris, John Rosenberg, Francis Vaughan
The Grasshopper operating system provides explicit support for orthogonal persistence. A consequence of this is that the kernel itself must, in part, be persistent. To conform to the model of persistence in Grasshopper, the kernel persistent store must provide a means to stabilise entities independently of each other and must also be able to maintain an arbitrary number of versions for each entity. The design of the kernel persistent store is constrained by the need to be very efficient and to intrude as little as possible on the code using the store. Entities in the store reside at fixed, unique virtual addresses by which they are identified. This allows standard demand paging techniques are used making the store efficient and unobtrusive. Rather than provide for the independent stabilisation of individual data structures, the store provides regions, which are variable-size sets of possibly noncontiguous virtual pages, that may be stabilised independent of each other and that may have many versions. These regions, called persistent arenas, are used by higher-level software as pools for the allocation of smaller data structures that must logically be stabilised together.
Proceedings of the Eighteenth Australasian Computer Science Conference, ACSC-18, ed. Ramamohanarao Kotagiri, Glenelg, South Australia, pp 329-338, February 1995.
Alan Dearle, Rex di Bona, James Farrow, Frans Henskens, Anders Lindstrom, John Rosenberg, Francis Vaughan
For ten years researchers have been attempting to construct programming language systems that support orthogonal persistence above conventional operating systems. This approach has proven to be poor; researchers invariably construct a complete abstract machine above the operating system with resulting loss of efficiency. This paper describes a new approach, the construction of an operating system designed to support orthogonal persistence. The operating system, Grasshopper, relies upon three powerful and orthogonal abstractions: containers, loci and capabilities. Containers provide the only abstraction over storage, loci are the agents of change, and capabilities are the means of access and protection in the system. This paper describes these three fundamental abstractions of Grasshopper, their rationale and how they are used.
Computing Systems, 7(3), pp 289-312, Summer 1994
Anders Lindstrom, John Rosenberg, Alan Dearle
A key decision in the design of an operating system is which facilities to provide for the management and composition of the address space. A wide spectrum of schemes exist, ranging from the private process address space of Unix through to the recently revived single address space approach. This paper proposes a new model which provides a unified and generalised approach to address space management. The model presents a single abstraction of address spaces which are orthogonal to processes and may be composed in arbitrary ways. The power of the model is demonstrated by case studies which show how shared libraries, a Unix system and a single address space may be implemented.
Proceedings of the Fifth Workshop on Hot Topics in Operating Systems (HotOS-V), Orcas Island, Washington, pp 66-71, May 1995
The Grasshopper operating system supports persistence of all system entities including computations. It also makes strong guarantees about the consistency of the system after a restart. A central part of the im-plementation of this is the store used for kernel meta-data. The store is designed to accommodate a number of different consistency strategies which may be broadly classed as either pessimistic or optimistic. Existing persistent stores use pessimistic approaches which ensure that the the on-disk image of the store is al-ways consistent. An optimistic approach is one that does not guarantee a consistent on-disk image; any inconsistencies are eliminated at recovery time. The main benefit of this approach is the reduction of disk accesses during normal operation. Most existing persistent stores use shadow paging to move from one consistent state to the next. This is not possible when optimistic strategies are used. Therefore, the Grasshopper kernel store uses a new approach, based on multi-versioning and logging, that can support both pessimistic and optimistic consistency strategies.
Alan Dearle & David Hulse
Persistent object systems must provide some form of checkpointing to ensure that changes to persistent data are secured on non-volatile storage. When processes share or exchange modified data, mechanisms must be provided to ensure that they may be consistently checkpointed. This may be performed eagerly by synchronously checkpointing all dependent data. Alternatively, optimistic techniques may be used where processes are individually checkpointed and globally consistent states are found asynchronously. This paper examines two eager checkpointing techniques and describes a new optimistic technique. The technique is applicable in systems such as SASOS, where the notion of process and address space are decoupled.
David Hulse & Alan Dearle
Persistent stores have been implemented using a variety of storage technologies including shadow paging, log-based and log-structured approaches. Here we compare these approaches and advocate the use of log-structuring. The advantages of such a technique include efficient support for large (64 bit) address spaces, scalability and fast snapshot processing. We describe the architecture of a new log-structured persistent store and how it has been used to support resilient persistent processes in the context of the Grasshopper operating system. This store is based on the use of a log server which provides clients with private logical logs.
to appear in Proceedings 19th Australasian Computer Science Conference
J. Rosenberg, A. Dearle, D. Hulse, A. Lindstrom and S. Norris
The principal tasks of an operating system are to manage the resources of the system, maintain the permanent data of the system and to provide an efficient environment for the execution of user programs. In conventional operating systems these tasks are centred around the file system as the repository of permanent data and virtual memory as the execution environment. Persistent systems offer an alternative view in which the lifetime of data is separated from the access mechanism. In a persistent system all data, regardless of its lifetime, is created and manipulated in a uniform manner. When persistence is included as the basic abstraction of an operating system, many of the inadequacies of existing operating systems are eliminated and the tasks of an application developer are greatly simplified. This results in major improvements both in terms of program development time and execution efficiency. Grasshopper, a persistent operating system being developed by the authors, provides a testbed for the demonstration of these claims.
D. Hulse and A. Dearle
For persistent systems to be useful they must provide efficient snapshot and recovery mechanisms. This paper describes the design of the persistence architecture of the Grasshopper operating system which addresses these requirements. It shows how the major components of the architecture interact with one another and how it can be used to provide fast snapshot and recovery times. A novel feature of the architecture is the lazy recovery mechanism which delays the recovery of each component of the system until required.