# HG changeset patch # User Daichi TOMA # Date 1391702546 -32400 # Node ID 88b11a3afb9341c744ddbac61734fd170947fcd7 # Parent e32c9a53310c4c9fbb6c26dc10f2cd49c698f338 describe deos diff -r e32c9a53310c -r 88b11a3afb93 paper/chapter1.tex --- a/paper/chapter1.tex Thu Feb 06 21:12:49 2014 +0900 +++ b/paper/chapter1.tex Fri Feb 07 01:02:26 2014 +0900 @@ -390,7 +390,8 @@ \end{lstlisting} Haskell で並列実行を行いたい場合は, 遅延評価に気をつける必要がある. -値が必要となるprintなどを行えば, 並列に実行可能な部分が並列に実行される. +rpar は単なるマーキングに過ぎず, rpar に渡したからといって直ちに並列実行が行われるわけではない. +rpar で作成した Eval モナドを runEval に渡したあと、値が必要となるprintなどを行えば, 並列に実行可能な部分が並列に実行される. また, rpar を使用する際, 別の計算の値に依存する計算がある場合, その2つの計算は並列実行できない. 例えば, ソースコード\ref{src:rpar}のような場合は並列実行ができない. diff -r e32c9a53310c -r 88b11a3afb93 paper/chapter2.tex --- 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 はロックの管理という煩雑な処理から逃れられるだけでなく, 並列性も向上する. +どのスレッドもリソースにアクセスするために待つ必要はない. ルートノードの情報の取得だけならば, 並列に取得できる. ルートノードの情報の更新の場合は, 他から変更があれば再度やり直すということが自動的に行われる. diff -r e32c9a53310c -r 88b11a3afb93 paper/chapter3.tex --- a/paper/chapter3.tex Thu Feb 06 21:12:49 2014 +0900 +++ b/paper/chapter3.tex Fri Feb 07 01:02:26 2014 +0900 @@ -1,5 +1,5 @@ \chapter{Haskellによる\\並列データベースの実装}\label{ch:impl} -本章では, 並列データベース Jungle の実装について述べる. +　本章では, 並列データベース Jungle の実装について述べる. \section{木構造データベース Jungle} 非破壊的木構造データベース Jungle は, Haskell で実装された並列データベースである. @@ -24,16 +24,29 @@ \begin{table}[!htbp] \label{tab:components} \begin{center} -\begin{tabular}{|c||c|} \hline -型名 & 概要 \\ \hline -Jungle & 木の作成・取得を担当する. \\ \hline -Tree & 木の名前とルートノードの情報を保持している. \\ \hline -Node & 基本的なデータ構造, 子と属性を任意の数持てる. \\ \hline +\begin{tabular}{|c||c|c|} \hline + 型名 & 概要 \\ \hline + Jungle & 木の作成・取得を担当する. \\ \hline + Tree & 木の名前とルートノードの情報を保持している. \\ \hline + Node & 基本的なデータ構造, 子と属性を任意の数持てる. \\ \hline \end{tabular} \end{center} \caption{Jungle が持つデータ型} \end{table} +\begin{table}[!htbp] +\label{tab:components} +\begin{center} +\begin{tabular}{|c||c|} \hline + 型名 & データ構造 \\ \hline + Jungle & Jungle (TVar (Map String Tree)) \\ \hline + Tree & Tree (TVar Node) String \\ \hline + Node & Node (Map Int Node) (Map String ByteString) \\ \hline +\end{tabular} +\end{center} +\caption{データ型のデータ構造} +\end{table} + \subsection{Jungle} Jungle は木構造の集まりを表現する. 木には名前がついており, Tree の情報と一緒に保持している. @@ -93,7 +106,7 @@ Jungle のデータ構造の Map の前に付いている TVar というのは, Transactional variablesの略で, STM で管理する変数に対して利用する. \subsubsection{Jungle と木の作成} -Jungle は, Mapで木を管理しているため, 複数の非破壊的木構造を持つことができる（図\ref{fig:jungle}）. +Jungle は, 複数の非破壊的木構造を持つため、Map で木を管理している（図\ref{fig:jungle}）. \begin{figure}[!htbp] \begin{center} diff -r e32c9a53310c -r 88b11a3afb93 paper/images/deos_proccess.pdf Binary file paper/images/deos_proccess.pdf has changed diff -r e32c9a53310c -r 88b11a3afb93 paper/images/deos_proccess.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/deos_proccess.xbb Fri Feb 07 01:02:26 2014 +0900 @@ -0,0 +1,8 @@ +%%Title: ./deos_proccess.pdf +%%Creator: extractbb 20130405 +%%BoundingBox: 0 0 712 413 +%%HiResBoundingBox: 0.000000 0.000000 712.000000 413.000000 +%%PDFVersion: 1.4 +%%Pages: 1 +%%CreationDate: Tue Feb 4 18:21:17 2014 + diff -r e32c9a53310c -r 88b11a3afb93 paper/introduciton.tex --- a/paper/introduciton.tex Thu Feb 06 21:12:49 2014 +0900 +++ b/paper/introduciton.tex Fri Feb 07 01:02:26 2014 +0900 @@ -1,8 +1,35 @@ \chapter{研究背景と目的} \label{ch:introduction} \pagenumbering{arabic} -　Web サービスの脆弱性狙った攻撃が頻繁に発生している. -脆弱性を悪用されると, Web サービス運営者は賠償など多大な損害を受ける可能性がある. +　ITシステムが巨大化していくにつれ, 障害発生事例が社会に与える影響もより大きな物となる. +それに伴い, ITシステムにおけるディペンダビリティへの注目が増している. + +そこで, DEOSプロジェクトはITシステムにおけるディペンダビリティを担保する技術体系をまとめ, 制度化, さらには事業化を目指している. +DEOSプロジェクトは2006年に独立行政法人科学技術機構(JST)はCRESTプログラムの1つとして始まったプロジェクトである. +DEOSプロジェクトは, 変化し続ける目的や環境の中でシステムを適切に対応させ, 継続的にユーザが求めるサービスを提供することができるシステムの構築法を開発することを目標としている\cite{deos2013}. +DEOSプロジェクトではそれらの技術体系を「オープンシステムディペンダビリティ」として定義し, それをDEOSプロセスとしてまとめた(図\ref{fig:deos_proccess}). + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.5]{images/deos_proccess.pdf} + \caption{DEOS プロセス} + \label{fig:deos_proccess} + \end{center} +\end{figure} + +DEOSプロセスには変化対応サイクルと障害対応サイクルの2つのサイクルがある. +変化対応サイクルは上流プロセスにおける対象システムのオープンシステムディペンダビリティを担保するためのプロセスである. +障害対応サイクルは対象システムの運用時に必要とされるプロセスである. +DEOSプロセスは企画や設計という上流からシステム運用までの対象システムのライフサイクル全体に係わる. +対象システムの運用は, ステークホルダからの対象システムに対する要求に関する +合意を始めとしたあらゆる議論に関する合意をベースに行われる. + +DEOS プロセスを構成している各(サブ)プロセスからアクセスが行われるデータベースとして D-ADD(DEOS Agreement Description Database)がある\cite{d_add2013}. +D-ADD はステークホルダ合意と対象システムに存在するプログラム・コード, 及び対象システムの運用状態との間の一貫性を常に保つための機構を提供する. +このようなデータベースは様々なデータを柔軟に格納する必要があり, データベーススキーマの頻繁な変化に対応する必要がある. +これらのデータベースは, Web からアクセスされることも想定される. +そのため, DEOSは Web サービスとして捉えることができる. + 純粋関数型プログラミング言語 Haskell は, バッファオーバーフローや, クロスサイトスクリプティング, SQL インジェクションを事前の型検査で防ぐことができる. つまり, Haskell を用いることで信頼性の高い Web サービスを開発できると言える. diff -r e32c9a53310c -r 88b11a3afb93 paper/master_paper.bib --- a/paper/master_paper.bib Thu Feb 06 21:12:49 2014 +0900 +++ b/paper/master_paper.bib Fri Feb 07 01:02:26 2014 +0900 @@ -40,12 +40,6 @@ note = "[Online; accessed 2-Feb-2014]" } -@misc{deos, - title = {{DEOS}}, - howpublished = "\url{http://www.dependable-os.net/osddeos/data.html}", - note = "[Online; accessed 29-Jan-2014]" -} - @article{shoshi:2010a, author = "玉城 将士 and 河野 真治", title = "Cassandraを使った{CMS}の{PC}クラスタを使ったスケーラビリティの検証", @@ -78,3 +72,14 @@ year = 2013 } + +@misc{deos2013, +author = "所 眞理雄", +title = "{DEOS プロジェクト研究成果集 Dependability Engineering for Open Systems}", +year = "2013" +} +@misc{d_add2013, +author = "{永山 辰巳, 横手 靖彦}", +title = "{オープンシステムディペンダビリティとD-Caseを繋ぐリポジトリ}", +year = "2013" +} diff -r e32c9a53310c -r 88b11a3afb93 paper/master_paper.pdf Binary file paper/master_paper.pdf has changed diff -r e32c9a53310c -r 88b11a3afb93 paper/thanx.tex --- a/paper/thanx.tex Thu Feb 06 21:12:49 2014 +0900 +++ b/paper/thanx.tex Fri Feb 07 01:02:26 2014 +0900 @@ -3,7 +3,7 @@ 本研究を行うにあたり, 日頃より多くの助言, ご指導いただきました河野真治助教授に心より感謝申し上げます. -本研究は, JST/CREST 研究領域「実用化を目指した組み込みシステム用ディペンダブル・ オペレーティングシステム」\cite{deos} D-ADD 研究チームとして実施しました. +本研究は, JST/CREST 研究領域「実用化を目指した組み込みシステム用ディペンダブル・ オペレーティングシステム」D-ADD 研究チームとして実施しました. 研究の機会を与えてくださった, 株式会社 Symphony の永山辰巳さんに感謝します. また, データベースの実装にあたり, 多くの議論にお付き合い頂いた大城信康さん, 並列信頼研究室の全てのメンバーに感謝いたします.