JPH0398123A - 時刻スタンプ付き命令系列処理装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は時刻スタンプ付き命令系列処理装置に関する． 〔従来の技術〕 順不同で入力される、時刻スタンプ付き命令及び既に入
力した命令の取り消しを請求する命令を処理する方式と
して仮想時刻方式（ＤａｖｉｄＲ．Ｊｅｆｆｅｒｓｏｎ
，ＡＣＭ　　Ｔｒａｎｓａｃｔｉｏｎｓ　　ｏｎ　　Ｐ
ｒｏｇｒａｍｍｉｎｇＬａｎｇｕａ・ｇｅｓ　　ａｎｄ
　　Ｓｙｓｔｅｍ，Ｖｏｌ．７，Ｎｏ．３，ＪＵＬＹ　
　１９８５．Ｐａｇｅｓ　　４０４−４２５＞がある．
この仮想時刻方式を実行するためのシステムの楕戒は、
第１１図に示すように、入力された時刻スタンプ付き命
令を保持する命令系列保持部８０１と、前記命令系列保
持部に保持されている命令を実行する命令実行手段８０
４と、命令実行後の新しい状態と命令の実行に起因する
副作用を組にしてリスト構造で保持する状態遷移リスト
保持部８０２と、前記命令系列保持部と前記状態遷移リ
スト保持部を管理する情報管理手段８０３から構成され
る。

一レし待ヨじｖ１盲’ｃ　Ｌ　ｋ　Ｌ−ｋ−’ｃ七１し
セーし睦≠セ第１２図は命令系列保持部８０１と状態遷
移リスト保持部８０２に情報が保持されている状態の一
例を示す図であり、第１３図は命令系列保持部８０１に
格納される命令ノード８０５の構造を示す図である． 命令ノード８０５は命令を格納する命令スロットと時刻
スタンプを格納する時刻スタンプスロットから構成され
る．第１２図に示すように、命令系列保持部８０１には
命令ノード８０５が時刻スタンプ順にソートされて格納
される．命令ボインタ８０６は情報管理手段８０３が現
在注目している命令ノードを指している。

第１４図は状態遷移リスト保持部に格納される状態遷移
リストを構成する状態ノード８０７の構造を示す図であ
る。状態ノード８０７は、命令実行後の新しい状態を格
納する状態スロットと、命令の実行に起因する副作用を
格納する副作用スロットから構成される。第１２図に示
すように、状態遷移リスト保持部には状態ノード８０７
を要素とするリストが保持されている。また、状態ノー
ド８０７と命令ノード８０５には対応関係８０８がある
。

第１５図は情報処理手段８０３の動作を示すフローチャ
ートである。情報処理手段８０３は、ステップ９００で
命令ポインタを初期化し、ステップ９０１で命令あるい
は命令の取り消しの入力があるか調べ、入力がある場合
には入力処理部Ｂを実行する。入力がない場合には命令
実行処理Ｂを実行する。それぞれの処理をおこなったあ
とステップ９０１にもどり同様の処理を繰り返す。

第１６図は第１５図における入力処理Ｂの詳細を示すフ
ローチャートである．ステップ９０２では入力された命
令あるいは取り消される命令の時刻スタンプ（以後、「
入力の時刻スタンプ」と記す）が命令ポインタが指す命
令の時刻スタンプ以下かどうか調べ、小さい場合には、
ステップ９０３で入力の時刻スタンプより大きな時刻ス
タンプを持つ命令と対応関係を持つ状態ノードに格納さ
れている副作用を無効にし、その状態ノードを状態遷移
リスト保持部から削除し、命令ポインタを入力命令の時
刻スタンプよりも小さくかつ最大の時刻スタンプをもつ
命令を指させる。ステップ９０４では入力が命令の場合
にはステップ９０５へ分岐し、取り消しの場合にはステ
ップ９０６へ分岐する。ステップ９０５では入力された
命令を命令ポインタが指す位置の後ろに挿入する．ステ
ップ９０６では入力に該当する命令を削除する． 第１７図は第１５図における命令実行処理Ｂの詳細を示
すフローチャートである。ステップ９０７では命令ポイ
ンタが指す命令ノードより後に命令ノードがあるかどう
か調べ、ある場合にはステップ９０８に分岐し、ない場
合には命令実行処理Ｂを終了する．ステップ９０８では
命令ポインタを１つ後の命令に移動する。ステップ９０
９では命令ポインタが指す命令を命令実行手段４で実行
する。ステップ９１０では新しい状態ノードを作戒し、
命令実行後の新たな状態を状態部に格納し、命令実行に
起因する副作用を副作用部に格納する。ステップ９１１
ではこの新しく作或された状態ノードを状態遷移リスト
保持部の状態遷移リストの最後尾に追加する。

〔発明が解決しようとする課題〕

上述した従来の技術では、既に実行されてしまった命令
を取り消す場合と、既に実行された命令よりも前の時刻
スタンプを持つ命令が入力された場合、その時刻スタン
プ以降の命令の実行処理が総て無効にされ、状態遷移情
報は削除される。

したがって、取り消された命令と同じ内容で同じ時刻ス
タンプを持つ命令が再び入力されても、命令の処理を再
び行わなければならない。また、新たに入力された命令
が取り消された場合にも、すでに以前の状態は状態遷移
リスト保持部から削除されているので、処理を再び行わ
なければならない。

また、既に実行してしまった命令より前の時刻スタンプ
を持゜つ命令が入力された場合、その時刻に近い命令が
再び入力される可能性が高い。この場合、命令の実行を
進めてもそれらが無駄になる可能性が高いが、従来の技
術ではこれを避けられない。

〔課題を解決するための手段〕

第１図の本発明は、入力された時刻スタンプ付き命令系
列を保持する命令系列保持部と、前記命令系列保持部に
保持されている命令を実行する命令実行手段と、命令実
行後の新しい状態と命令の実行に起因する副作用を組に
して木構造で保持する状態遷移木保持部と、前記命令系
列保持部と前記状態遷移木保持部を管理する情報管理手
段を具備することを特徴とし、また、第２の本発明は、
入力された時刻スタンプ付き命令系列を保持する命令系
列保持部と、前記命令系列保持部に保持されている命令
を実行する命令実行手段と、命令実行後の新しい状態と
命令の実行に起因する副作用を組にして本構造で保持す
る状態遷移木保持部と、前記命令系列保持部と前記状態
遷移木保持部を管理する情報管理手段と、入力された前
記時刻スタンプ付き命令の時刻スタンプから命令実行部
の実行速度を決定する実行速度調整手段を具備すること
を特徴とする。

〔作用〕

第１の本発明では、一度行った命令の実行結果を状態遷
移木として保存するので、再びその結果が必要になった
場合に実行しなおす必要がない。

また、第２の本発明では、情報管理手段がらの情報に基
づいて実行速度調整手段が命令実行手段の処理速度を制
御することにより、無効になる計算をおこなう確立を減
少させることができる。

〔実施例〕

次に、本発明について図面を参照して説明する． 第１図は第１の本発明の一実施例を示す構成図で、１は
入力された時刻スタンプ付きの命令を保持する命令系列
保持部、４は前記命令系列保持部に保持されている命令
を実行する命令実行手段、２は命令実行後の新しい状態
と命令の実行に起因する副作用の組から構成される状態
ノードを本構造で保持する状態遷移木保持部、３は前記
命令保持部と前記状態遷移木保持部を管理する情報管理
手段３である。

第３図は命令系列保持部１と状態遷移木保持部２に情報
が保持されている状態の一例を示す図であり、第４図は
命令系列保持部１に格納される命令ノード１１の構造を
示す図である．命令ノード１１は命令を格納する命令ス
ロットと時刻スタンプを格納する時刻スタンプスロット
と命令の有効・取り消しを表すフラグを格納する有効性
スロットから構成される。第３図に示すように、命令系
列保持部１には命令ノード１１が時刻スタンプ順にソー
トされて格納される。

第５図は状態遷移木保持部２に格納される状態遷移本を
構成する状態ノード１２の構造を示す図である．状態ノ
ード１２は、この状態ノード１２が対応している命令ノ
ード１１へのポインタを格納する命令スロットと、命令
実行後の新しい状態を格納する状態スロットと、命令の
実行に起因する副作用を格納する副作用スロットと、親
ノードへのポインタを格納する親ノードスロットと、子
供ノードへのポインタ群を格納する子供ノードスロット
から構成される。第３図に示すように、状態遷移木保持
部２には木の出発点となる空の状態ノードをルートとし
、状態ノード１２をノードとする木が保持されている．
状態ノードボイタ１３は情報管理部が現在注目している
状態ノードを指している． 第６図は情報処理手段３の動作を示すフローチャートで
ある．情報処理手段３は、ステップ１００で状態遷移木
保持部２に空の状態ノードを作成し、状態ポインタ１３
でこの状態ノードを指す．ステップ１０１で命令の入力
あるいは命令の取り消しの入力が有るかどうか調べ、入
力がある場合には入力処理Ａに実行する。入力がない場
合には命令実行処理Ａを実行する。各々の手続きをおこ
なったあとステップ１０１にもどり同様の処理を繰り返
す。

第７図は第１６図における入力処理Ａの詳細を示すフロ
ーチャートである．ステップ１０２では入力が命令の場
合にはステップ１０３に分岐し、入力が命令の取り消し
の場合にはステップ１０８に分岐する． ステップ１０３では、命令系列保持部１に入力された命
令と同一の命令で同一の時刻スタンプを持ちかつ取り消
し状態にある命令ノードが存在するかどうか調べる．条
件を満たす命令が存在する場合にはステップ１０４に、
存在しない場合にはステップ１０６に分岐する． ステップ１０４では状態ノードポインタが指す命令ノー
ドがステップ１０３で見つけた命令ノードより後の命令
ノードのであるあいだロールバック処理を繰り返す．ス
テップ１０５ではステップ１０３で見つけた命令ノード
の有効性スロットに「有効」を代入する。

ステップ１０６では、命令ポインタが指す命令ノードの
時刻スタンプが入力された命令の時刻スタンプより大き
いあいだロールパック処理を繰り返す．ステップ１０７
では新たな命令ノードを作成し命令スロットと時刻スタ
ンプスロットには入力された命令とその時刻スタンプを
代入し有効性スロットに「有効」を代入し、状態ノード
ポインタが指す状態ノードの命令スロットが指す命令ノ
ードの次に新たに作った命令ノードを挿入する。

ステップ１０８では命令ポインタが指す命令ノー′ドが
取り消し対象のノードあるいはそれ以後の命令ノードで
あるあいだロールパック処理を繰り返す．ステップ１０
９では取り消し対象の命令ノードの有効性スロットに「
取り消し」を代入する． 第８図は第１７図におけるロールパック処理の詳細を示
すフローチャートである．ステップ１１０では命令ポイ
ンタが指す命令ノードの副作用を無効にする．ステップ
１１１では状態ノードポインタが指す状態ノードの親ノ
ードを、状態ノードポインタが指すようにする． 第９図は第６図における実行処理Ａの詳細を示すフロー
チャートである。ステップ１１２では状態ノードポイン
タが指す状態ノードの命令ポインタが指す命令ノード以
後の中で有効性スロットに「有効」が代入されている最
初の命令ノードを捜す。見つかった場合にはステップ１
１３に分岐する。見つからない場合には実行処理Ａを終
了する． ステップ１１３では状態ノードポインタが指す状態ノー
ドの子ノードの中にステップ１１２で見つけた命令を実
行しているものがあるかどうか調べ、見つかった場合に
はステップ１１４に分岐する．見つからない場合にはス
テップ１１６に分岐する． ステップ１１４では状態ノードポインタステップ１１３
で見つかった状態ノードを指すようにし、ステップ１１
５でステップ１１３で見つかった状態ノードの副作用を
有効にする． ステップ１１６では、ステップ１１２で見つかった命令
を実行し、ステップ１１７では新たな状態ノードを作威
して、命令を実行した後の状態を状態スロットに格納し
、命令の実行に起因する副作用を副作用スロットに格納
し、命令スロットにステップ１１２で見つかった命令を
代入し、親ノードスロットに状態ノードポインタが指す
状態ノードを代入する． ステップ１１８では、ステップ１１７で作威した状態ノ
ードを状態ノードポインタが指す状態ノードの子ノード
として登録し、状態ノードポインタがこの新たに作成し
たノードを指すようにする． 第２図は、第２の本発明の一実施例を示す構成図で、１
は入力された時刻スタンプ付きの命令を保持する命令系
列保持部、４は前記命令系列保持部に保持されている命
令を実行する命令実行手段、２は命令実行後の新しい状
態と命令の実行に起因する副作用の組から構成される状
態ノードを本構造で保持する状態遷移木保持部、３は前
記命令保持部と前記状態遷移木保持部を管理する情報管
理手段、５は入力された時刻スタンプ付き命令の時刻ス
タンプから命令実行手段の実行速度を決定する実行速度
調整手段である。

第１０図は実行速度調整手段５の動作を示すフローチャ
ートである。ステップ１１９では情報管理手段３でロー
ルパックが発生するのを待ち、ロルーバックが発生する
とステップ１２０で命令実行手段の実行速度を一定時間
低下させる。

〔発明の効果〕

第１の本発明においては、状態遷移を本構造ですべて保
存しているので、同じ命令系列の実行が必要になった場
合には、保存してある状態ノードを、ステップ１０５、
ステップ１１５で再利用することができ、実行を再びお
こなう必要ない。

第２の本発明においては、ロールパックが発生したとき
に実行速度調整手段５が実行速度を低下させるので、無
駄になる処理を行う可能性を低くおさえることができる
。

【図面の簡単な説明】

第１図は第１の本発明の一実施例を示す構成図、第２図
は第２の本発明の一実施例を示す構成図、第３図は命令
系列保持部と状態遷移木保持部に保持されるデータ構造
の一例を示す図、第４図は命令ノードのデータ構造を示
す図、第５図は状態ノードのデータ構造を示す図、第６
図〜第９チャート、第ｌ１図は従来の装置の一実施例を
示す構成図、第１２図は従来の装置の命令系列保持部と
状態遷移リスト保持部に保持されるデータ構造の一例を
示す図、第１３図は従来の命令ノードのデータ構造を示
す図、第１４図は従来の状態ノードのデータ構造を示す
図、第１５図〜第１７図は従来の情報管理手段の動作を
示すフローチャートである。 １・・・命令系列保持部、２・・・状態遷移木保持部、
３・・・情報管理手段、４・・・命令実行手段、５・・
・実行速度調整手段、１１・・・命令ノード、１２・・
・状態ノード、１３・・・状態ノードポインタ、８０１
・・・従来の命令系列保持手段、８０２・・・状態遷移
リスト保持部、８０３・・・従来の情報管理手段、８０
４・・・命令実行手段、８０５・・・従来の命令ノード
、８０６・・・命令ポインタ、８０７・・・状態ノード
、８０８・・・対応関係。 尤 １ Ｒ

Claims (2)

【特許請求の範囲】
1. （１）入力された時刻スタンプ付き命令系列を保持する
   命令系列保持部と、前記命令系列保持部に保持されてい
   る命令を実行する命令実行手段と、命令実行後の新しい
   状態と命令の実行に起因する副作用を組にして木構造で
   保持する状態遷移木保持部と、前記命令系列保持部と前
   記状態遷移木保持部を管理する情報管理手段から構成さ
   れることを特徴とする時刻スタンプ付き命令系列処理装
   置。
2. （２）入力された時刻スタンプ付き命令系列を保持する
   命令系列保持部と、前記命令系列保持部に保持されてい
   る命令を実行する命令実行手段と、命令実行後の新しい
   状態と命令の実行に起因する副作用を組にして木構造で
   保持する状態遷移木保持部と、前記命令系列保持部と前
   記状態遷移木保持部を管理する情報管理手段と、入力さ
   れた前記時刻スタンプ付き命令の時刻スタンプから命令
   実行部の実行速度を決定する実行速度調整手段から構成
   されることを特徴とする時刻スタンプ付き命令系列処理
   装置。