書き込み保留を用いた逐次化グラフスケジューリング

• Item type: SIG Technical Reports(1)
• 公開日: 1996-07-12
• タイトル: 書き込み保留を用いた逐次化グラフスケジューリング
• タイトル / 言語: en
• タイトル: A Scheduling Method using Serialization Graph Testing with Write Deferring
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学基礎工学部情報科学科
• 著者所属: 大阪大学基礎工学部情報科学科
• 著者所属: 大阪大学基礎工学部情報科学科
• 著者所属(英): en
• 著者所属(英): Depertment of Information and Computer Science, Faculty of Engineering Science Osaka University
• 著者所属(英): en
• 著者所属(英): Depertment of Information and Computer Science, Faculty of Engineering Science Osaka University
• 著者所属(英): en
• 著者所属(英): Depertment of Information and Computer Science, Faculty of Engineering Science Osaka University
• 著者名: 多田, 知正; 樋口, 昌宏; 藤井, 護
• 著者名(英): Harumasa, Tada; Masahiro, Higuchi; Mamoru, Fujii
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: データベースの無矛盾性を保存するようなスケジューリングアルゴリズムがいくつが知られている．その中で逐次化グラフ検査を用いたスケジューリングアルゴリズムはトランザクションの高い並行性を達成することが知られているが，この方法にはいくつかの問題点がある．すなわち，逐次化グラフの検査に時間がかかるためデータベースに対する操作が遅れてしまうことと，生成される実行がサイト故障などの障害から回復できない場合が存在することである．一方，楽観的並行制御と呼ばれる方法はすべての操作を直ちに実行できる特徴がある．また局所的コピーを用いて実際のデータベースへの書き込み操作を遅らせることにより，障害からの回復が可能な実行を得ることを可能にしている．そこで，この方法を逐次化グラフを用いたアルゴリズムに適用し，書き込み保留逐次化グラフ検査というアルゴリズムを提案する．このアルゴリズムによって，先に述べた逐次化グラフ検査の問題点を解決することができる．本稿では，このアルゴリズムの基本アルゴリズムといくつかの変形を示す．また，他のアルゴリズムと比較することにより，このアルゴリズムの有効性を示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Several scheduling algorithms for preserving database consistency are known. It is known that Serialization Graph Teting (SGT) achieves higher concurrency of transactions than other scheduling algorithms. However, it has some drawbacks. First, operations are delayed for a long time to check the serialization graph. Second, executions produced by SGT may be unrecoverable from some failures. On the other hand, under Optimistic Concurrency Control (OCC), all operations are executed immediately. Moreover, OCC produces recoverable executions by deferring substantial write operations using local copies. Therefore, we applied OCC approach to SGT and propose an algorithm which we call Serialization Graph Testing with Write Deferring (SGT-WD). SGT-WD overcomes above drawbacks of SGT. In this paper, we show the basic algorithm and some variant of SGT-WD. We compare SGT-WD with other algorithms, and show that it is more useful than those algorithms.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10116224
• 書誌情報: 情報処理学会研究報告マルチメディア通信と分散処理（DPS）; 巻 1996, 号 63(1996-DPS-077), p. 49-54, 発行日 1996-07-12
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会