アクティブデータ構造とは、内部操作を実行するスレッドまたはプロセスが関連付けられたデータ構造です。 [1]より具体的には、アクティブデータ構造は、1つ以上の同時実行プロセスと、それらのプロセスに関連付けられたデータを含むコンピューティングリソースに関連付けられています。通信は、共有メモリやメッセージパッシングではなく、リモートプロシージャコールを使用してモデル化されます。アクティブデータ構造の内部はRPCインターフェースの背後に隠されており、同時にアクセスできます。一般的な例としては、データベースやファイルシステムが挙げられます。アクティブデータ構造は、リソースがアイドル状態になっているときにメンテナンスを実行し、データの複数のビューを提供できます。[2]
例
ハードウェアまたはオペレーティングシステムによって提供されるキューは、通常、無制限ではなく、有限の容量を持ちます。アプリケーションがキューアイテムを決して失わないという強い要件を持っていると仮定します。その場合、キューがいっぱいになった場合にアイテムを大容量ストレージメディアに保存するように書き込みプロセスを変更し、読み取りプロセスでアイテムを読み戻す必要があります。アクティブデータ構造の概念を用いると、大容量ストレージへのアイテムの保存と取得を管理する「アクティブキュー」を検討できます。実行中のプロセスが2つではなく3つになったため、同期がより複雑になる可能性がありますが、アクティブキューを使用するための高レベルのリーダー/ライター抽象化は依然として単純かつ明確です。
形式化
自己調整計算とは、内部状態を維持し、ゼロから再計算するよりも効率的に新しい入力に適応できる増分計算プログラムを作成するための手法です。これは、データ構造の典型的な代数的特徴付けに時間の概念を導入することで、アクティブデータ構造を形式化できることを示唆しています。具体的には、カナト・タンウォンサンは、アクティブデータ構造は以下の3つのメタ演算を持つ代数であると提案しています。[3]
- perform("operation i (·)", t) は、時刻 t に操作 operation iを実行します。operation i (·) が値 r iを返す場合、メタ操作は値 r iを返します。
- メタ操作undo(t)は、時刻tにおける操作を元に戻す操作です。これは増分計算のモデル化に使用されます。
- メタ操作 update(t) は、データ構造に時刻 t まで「同期」するよう指示します。これには他のプロセスに関する情報も組み込まれます。
参照
参考文献
- ^ 「アクティブデータ構造」xlinux.nist.gov。
- ^ Andrews, Gregory R.; Dobkin, David P. (1981年3月9日). アクティブデータ構造. 第5回国際ソフトウェア工学会議, ICSE 1981. IEEEコンピュータソサエティ. pp. 354– 362.
- ^ Tangwongsan, Kanat (2006年5月5日). アクティブデータ構造と動的および運動学的アルゴリズムへの応用(PDF) (論文).
この記事には、Paul E. Black著「Active Data Structure」（アルゴリズムとデータ構造の辞書、NIST）のパブリックドメイン資料が含まれています。
