An Operating System Supporting Optimistic/Speculative Processing Based on the Parallel World Model

Yasushi Shinjo
Institute of Information Sciences and Electronics
University of Tsukuba
Tsukuba, Ibaraki 305, Japan
Fax: +81 298 53 5206
E-Mail: yas@is.tsukuba.ac.jp
URL: http://www.is.tsukuba.ac.jp/~yas/

Optimistic (speculative) processing

Optimistic (speculative) processing is processing that is started eagerly before it is know to be required. I am developing an operating system which supports optimistic processing at the level of processes and files. In environments which consists of networked workstations, many CPU and memory resources are not used. By using such idle resources for optimistic processing, outward appearance execution times of applications can be shortened.

The parallel world model

I am developing an operating system supporting optimistic processing at the level of files and processes based on the parallel world model. This system provides multiple execution application environments called worlds. A world is a container of files and processes (Figure 1). The term world is derived from parallel world (parallel universe) in science fiction.

DAG of worlds

Figure 1: a DAG of worlds

There are three operations for worlds:

  1. world_create()
  2. world_delete()
  3. world_merge()
A new world can be created based on other worlds. In this case, the new world is a child world of the base worlds, and the base worlds are parents worlds of the news world. By using the parent-child relation, all worlds in the system construct world-dag,a DAG (Directed Acyclic Graph) (Figure 1). Each world holds the differences to its parents. In a world, the contents of its ancestors can be accessed except for overridden ones by itself.

Optimistic processing and implementation

Optimistic processing can be performed by using the parallel world model as follows:

  1. A new world for optimistic processing is created.
  2. Processes for optimistic processing are executed in the new child world. The results (files and processes) are placed in the child world, and cannot be accessed by the parent mandatory world.
  3. When the results are known to be required, the child world is merged into the parent world, and the results appear in the parent world.
  4. When the results are known to be not required, the child world is deleted.

    The main application of this system is the speculative make (the UNIX make utility). The speculative make creates worlds and starts processing described in Makefile in the new worlds before the user types "make" into a shell. The speculative make maintains a DAG of worlds which is similar to the DAG of file dependency. The speculative make merges the worlds which contain requested files into the parent mandatory world.

    I have proposed an implementation method of the file system for optimistic processing based on the parallel world model. In this method, the name resolution module (namei() in UNIX) is changed. File names in the mandatory world are stored in regular directory files in disks and those in optimistic worlds are stored in a table in the main memory.

    Selected papers on optimistic processing

    Ideas of an Operating System Supporting Speculative Processing

    Takashi Nerome, Hajime Toma, Yasushi Shinjo, Seiki Kyan, and Kenji Onaga

    SWoPP'94, IPSJ SIG Notes, 94-ARC-107-12, Vol.94,No.66, pp.89-96 (Jul. 1994).

    Abstract Speculative processing is processing that is started eagerly before it is known to be required. Speculative processing makes it possible to reduce turnaround time by using surplus computer resources. Speculative processing with pre-execution is discussed. The speculative version of the make application of UNIX is designed, and its model of execution is shown. Issues for supporting speculative processing in multiprogramming environments are discussed. In this paper, the idea of "world" is introduced to deal with speculative processing.

    Body in Japanese.

    Operations of Worlds and Processes in an Operating System Supporting Speculative Processing

    Masaya Mizobuchi, Yasushi Shinjo, Hajime Toma, Takashi Nerome, Seiki Kyan and Kenji Onaga

    IPSJ SIG Notes, 95-OS-69-18, Vol.95,No.69 (June 1995).

    Abstract Speculative processing is processing that is started eagerly before it is known to be required. We are developing an operating system that supports process-level speculative processing. We use the idea of worlds to deal with the speculative processing. A world is a box that contains some processes and files. This paper describes interfaces, attributes, and implementations of world objects and process objects.

    Body in Japanese.

    The File System of an Operating System Supporting Speculative Processing

    Hajime Toma, Yasushi Shinjo, Masaya Mizobuchi, Takashi Nerome, Seiki Kyan and Kenji Onaga

    SWoPP'95, IPSJ SIG Notes, 95-OS-70-3, Vol.95,No.70 (Aug 1995).

    Abstract Speculative processing is processing that is started eagerly before it is known to be required. We are developing an operating system that supports process-level speculative processing. We introduced the idea of worlds to deal with speculative processing. A world is a container which contains processes and files. This paper describes the interface and implementation of the file system of this operating system. The feature of the interface is that files are identified by their names and worlds. In this implementation, the name subsystem plays the main role.

    Body in Japanese.

    The implementation of Speculative Make using a DAG of Worlds

    Takashi Nerome, Yasushi Shinjo, Hajime Toma Masaya Mizobuchi, Seiki Kyan and Kenji Onaga

    SWoPP'95, IPSJ SIG Notes, 95-OS-70-4, Vol.95,No.70 (Aug. 1995).

    Abstract Speculative processing is processing that is started eagerly before it is known to be required. Speculative processing using surplus computer resources makes it possible to reduce apparent execution time for users. We are implementing an operating system that supports speculative processes. In the operating system, the idea of worlds is introduced. A world is a container of files and processes. Worlds construct a DAG. As an application of the operating system, Speculative Make is being implemented. In this paper, how Speculative Make manipulates worlds is shown. We made a simulation of Speculative Make , we show its result and we estimate performance of Speculative Make.

    Body in Japanese.

    The Implementation of a Distributed File System Supporting the Parallel World Model

    Jun Sun, Yasushi Shinjo and Kozo Itano

    In Proceedings of The Third International Workshop on Advanced Parallel Processing Technologies, Oct.19-21, 1999. (Changsha, China)

    The parallel world model allows users to create, delete and merge multiple execution environments of processes called `worlds'. Its applications include optimistic processing and safe update of software packages. This paper presents the implementation of a distributed file system supporting this model. Unlike previous methods, the parallel world model is realized at the level of file body after name resolution. This enables usage of block-level copy-on-write to enhance the performance of the write operation. A lazy method is used to shorten the response times of applications. Experiments have been done to measure the performance of the file system.

    Body in English.

    [PDF] [PostScript(.ps)] [Gzip-ed PostScript(.ps.gz)]

    Other papers.

    Back to research interests page.

    Back to home page.

    Last updated: 2000/06/09 23:25:16
    Yasushi Shinjo / <yas@is.tsukuba.ac.jp>