Mercurial > hg > Papers > 2014 > toma-master
diff paper/chapter2.tex @ 48:88b11a3afb93
describe deos
author | Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 07 Feb 2014 01:02:26 +0900 |
parents | e32c9a53310c |
children | 0a8d66c9ccd1 |
line wrap: on
line diff
--- a/paper/chapter2.tex Thu Feb 06 21:12:49 2014 +0900 +++ b/paper/chapter2.tex Fri Feb 07 01:02:26 2014 +0900 @@ -37,7 +37,7 @@ \end{figure} この編集方法を用いた場合, 閲覧者が木構造を参照してる間に, 木の変更を行っても問題がない. -閲覧者は木が変更されたとしても, 保持しているルートノードから整合性を崩さずに参照が可能である. +閲覧者は木が変更されたとしても, 保持しているルートノードから整合性を崩さずに参照が可能である(図\ref{fig:nondestructive_tree_modification_in_lace}). 排他制御をせずに並列に読み書きが可能であるため, スケーラブルなシステムに有用である. 元の木構造は破壊されることがないため, 自由にコピーを作成しても構わない. したがってアクセスの負荷の分散も可能である. @@ -55,20 +55,21 @@ 非破壊的木構造では, ルートノードの管理が重要である. ルートノードは, 木の最新の状態を更新・参照するのに使う. ルートノードの情報は, 全てのスレッドで共有する必要があり, スレッドセーフに取り扱う必要がある. -一度ルートノードの情報を取得すれば, その後は排他制御なしに木構造へアクセスできる(図\ref{fig:rootnode}). +一度ルートノードの情報を取得すれば, その後は自由に木構造へアクセスできる(図\ref{fig:rootnode}). \begin{figure}[!htbp] \begin{center} \includegraphics[scale=0.6]{./images/rootnode.pdf} \end{center} - \caption{排他制御なしの非破壊的木構造のアクセス} + \caption{非破壊的木構造のアクセス} \label{fig:rootnode} \end{figure} -ルートノードはスレッド間で共有する状態を持つため, Haskell では IO モナドを用いる必要がある. +ルートノードはスレッド間で共有する状態を持つため, Haskell では IO モナドを用いて状態を扱う必要がある. これには, Haskell のソフトウェア・トランザクショナル・メモリ(STM)を利用する. -STM は排他制御を行わず, スレッドセーフに状態を扱うことができる. +STM はブロックせず, スレッドセーフに状態を扱うことができる. STM を利用することでロック忘れによる競合状態や, デッドロックといった問題から解放される. + STM は, STM モナドという特殊なモナドの中でのみ変更できる. STM モナドの中で変更したアクションのブロックを atomically コンビネータを使ってトランザクションとして実行する. (atomically コンビネータを用いることで IO モナドとして返される). いったんブロック内に入るとそこから出るまでは, そのブロック内の変更は他のスレッドから見ることはできない. @@ -79,7 +80,8 @@ \item そうでなければ, 変更を実際に実行せずに破棄し, アクションのブロックを再度実行する. \end{itemize} -STM は排他制御を行わないため, 簡単に扱うことができる. +STM はロックの管理という煩雑な処理から逃れられるだけでなく, 並列性も向上する. +どのスレッドもリソースにアクセスするために待つ必要はない. ルートノードの情報の取得だけならば, 並列に取得できる. ルートノードの情報の更新の場合は, 他から変更があれば再度やり直すということが自動的に行われる.