最適なロールバック・ポイントを選択するネスティッド・トランザクショナル・メモリ

元データ 2009-07-28 一般社団法人情報処理学会

概要

並列プログラミングにおいて,ロックを用いた同期機構が広く用いられている.しかし,ロックを用いると,デッドロックや不要なロックによる並列性の低下が生じることがある.一方で,ロックを用いるよりも容易に速いプログラムを書ける,トランザクショナル・メモリを用いた同期機構が提案されている.トランザクショナル・メモリを用いた並列プログラミングでは,プログラマが排他制御したい一連の処理をトランザクションとして指定する.多くのトランザクショナル・メモリの手法では,トランザクションは一つのスレッドで投機実行され,他スレッドから見れば,アトミックに実行されているかのように実行される.そのため,並列に実行されている他スレッドの処理とトランザクションの処理が競合した場合,トランザクションの処理をすべて破棄し,初めから再実行する.プログラムの構成上,トランザクション実行中にトランザクションが呼び出されることがある.このようなネスティッド・トランザクションについてもトランザクションとして正しく実行される必要がある.最も外側のトランザクションのアトミシティのためにロールバック時のロールバック・ポイントを最も外側のトランザクション開始点とすれば,その内に含まれるトランザクションもアトミシティが保たれる.しかし,競合とは関係のない処理もまた再実行されることがある.本稿では,最適なロールバック・ポイントを選択するネスティッド・トランザクショナル・メモリを提案する.最も外側のトランザクション開始点にロールバックする必要がない場合,再実行される処理が最小限になるようなロールバック・ポイントをネスティッド・トランザクション開始点の中から選択することができる.

著者

五島 正裕 東京大学情報理工学系研究科
坂井 修一 東京大学大学院工学系研究科
塩谷 亮太 東京大学大学院情報理工学系研究科
五島 正裕 東京大学大学院情報理工学系研究科
坂井 修一 東京大学
塩谷 亮太 東京大学情報理工学系研究科:日本学術振興会
伊藤 悠二 東京大学大学院情報理工学系研究科
坂井 修一 東京大学 情報理工学系研究科
坂井 修一 東京大学大学院 情報理工学系研究科

関連論文

▼もっと見る