Mercurial > hg > Papers > 2024 > matac-master
annotate Paper/master_paper.tex @ 47:49c1503c9176
...
| author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 29 Jan 2024 18:45:13 +0900 |
| parents | 9baf70df56fa |
| children | 9f0ef2d6ce2f |
| rev | line source |
|---|---|
|
2
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 \documentclass[12pt,a4paper,platex]{jreport} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 \usepackage{master_paper} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 \usepackage{ascmac} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 \usepackage[dvipdfmx]{graphicx} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 \usepackage{here} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 \usepackage{listings} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 \usepackage{comment} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8 \usepackage{url} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9 \usepackage[deluxe, multi]{otf} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13 %\input{dummy.tex} %% font |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15 |
| 14 | 16 \jtitle{GearsOSのファイルシステムにおけるGCとレプリケーション} |
| 17 \etitle{GC and Replication in the File System of GearsOS} | |
|
2
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
18 \year{2024年 3月} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
19 \eyear{March 2024} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
20 \author{又吉 雄斗} |
| 6 | 21 \eauthor{Matayoshi Yuto} |
| 22 \chife{指導教員：教授 和田 知久} | |
| 23 \echife{Supervisor: Prof. Wada Tomohisa} | |
|
2
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
25 \marklefthead{% 左上に挿入 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
26 \begin{minipage}[b]{.4\textwidth} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
27 琉球大学大学院学位論文(修士) |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
28 \end{minipage}} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
29 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
30 % \markleftfoot{% 左下に挿入 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
31 % \begin{minipage}{.8\textwidth} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32 % Gears OS の Paging |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33 % \end{minipage}} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35 \newcommand\figref[1]{図 \ref{fig:#1}} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
36 \newcommand\coderef[1]{ソースコード \ref{code:#1}} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
38 \lstset{ |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
39 frame=single, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
40 keepspaces=true, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41 stringstyle={\ttfamily}, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42 commentstyle={\ttfamily}, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
43 identifierstyle={\ttfamily}, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
44 keywordstyle={\ttfamily}, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
45 basicstyle={\ttfamily}, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46 breaklines=true, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 xleftmargin=0zw, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
48 xrightmargin=0zw, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
49 framerule=.2pt, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
50 columns=[l]{fullflexible}, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
51 numbers=left, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
52 stepnumber=1, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
53 numberstyle={\scriptsize}, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
54 numbersep=1em, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
55 language={}, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
56 tabsize=4, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
57 lineskip=-0.5zw, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
58 escapechar={@}, |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
59 } |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 \def\lstlistingname{ソースコード} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
61 \def\lstlistlistingname{ソースコード目次} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
62 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
63 %%% 索引のために以下の2行を追加 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
64 \usepackage{makeidx,multicol} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
65 \makeindex |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
66 \begin{document} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
67 %rome |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
68 \maketitle |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
69 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
70 \pagenumbering{roman} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
71 \setcounter{page}{0} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
72 \newpage |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
73 \makecommission |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
74 %\input{chapter/signature.tex} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
76 \newpage |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
77 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
78 %要旨 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
79 \input{chapter/abstract.tex} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
80 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81 \mainmatter |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
82 %目次 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
83 \tableofcontents |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
84 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
85 %図目次 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
86 \listoffigures |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
87 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
88 %リスト目次 |
| 24 | 89 \lstlistoflistings |
|
2
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
90 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
91 %chapters |
| 9 | 92 |
| 93 \chapter{GearsOSにおけるファイルシステムとDB} | |
| 94 | |
| 12 | 95 情報システムの信頼性を確保することは重要な課題である． |
| 96 2023年には銀行システムや航空機の旅客システム， | |
| 97 電子決済システムなどで障害が発生した\cite{zengin,ana,glory}． | |
| 98 信頼性の高いシステムを構築することは， | |
| 99 これらのような社会的影響のあるシステムの重大な障害発生防止につながり， | |
| 100 サービス提供者や受容者の機会的，経済的損失を防ぐことにつながる． | |
| 101 情報システムはアプリケーション，OS，DB，メモリやSSDなどのハードウェア， | |
| 102 分散ノードやネットワークなどさまざまな要素で構成される． | |
| 103 それらのうちどれか1つでも信頼性を損なうと， | |
| 104 システム全体の信頼性の低下につながる． | |
| 105 情報システム全体の信頼性を確保するためには， | |
| 106 これらの要素それぞれにおいて，信頼性を保証する必要がある． | |
| 9 | 107 |
| 108 当研究室では，信頼性の保証を目的としたGearsOSを開発している． | |
| 12 | 109 GearsOSは，定理証明やモデル検査などの形式手法を用いて信頼性を保証できることを目標としている．\cite{modelcheck}． |
| 110 一般的に信頼性を保証する手法としてテストコードを用いることが挙げられる． | |
| 111 しかしながら，OSなどの大規模なソフトウェアにおいて人力で記述するテストコードのみでは | |
| 112 カバレッジが不十分であり，検証漏れが発生する可能性がある． | |
| 113 GearsOSではテストコードに加え，形式手法を用いることでより高い信頼性の保証を目指している． | |
| 114 GearsOSは当研究室で開発しているプログラム言語であるContinuation based C(CbC)で記述されており， | |
| 115 ノーマルレベルとメタレベルを容易に切り分けることを可能とする拡張性を有す． | |
| 116 CbCによって本来行いたい処理をノーマルレベルで記述し， | |
| 117 信頼性を保証するための処理をメタレベルで記述するといった書き分け， | |
| 118 拡張を比較的容易に可能とする． | |
| 119 | |
| 120 OSの重要な機能の1つとしてファイルシステムが挙げられる． | |
| 36 | 121 ファイルシステムはOSのプロセスやユーザーデータの管理に必要な機能である． |
| 12 | 122 ファイルシステムには可変長の文字列を格納するファイルと， |
| 123 そのファイルにアクセスするための名前管理の機能がある． | |
| 124 ファイルの名前の一貫性は名前管理によって保証される． | |
| 125 しかし，ファイルに同時に書き込まれた際の一貫性を保証する機能を | |
| 126 ファイルシステムとしては持っておらず， | |
| 127 ファイルの書き込みを制御するロック機構をアプリケーションが持つことによって， | |
| 128 ファイルの一貫性を保証している．ファイルシステムによく似たものとしてDBが挙げられる． | |
| 129 DBは入力の属性名と型の組み合わせを複数持つレコードと， | |
| 130 特定の属性をキーとしたテーブルがある． | |
| 131 また，レコードのinsert，delete，updateの直列化可能性を保証する機能を持つ． | |
| 132 ファイルシステムとDBは格納するものの形式やそれにアクセスする方法， | |
| 133 直列化可能性を保証する手法が異なるが， | |
| 134 データをある形式で保持する仕組みであるという本質的な部分において違いはない． | |
| 135 よって，ファイルシステムとDBを同一のシステムとして実装することが可能であると考える． | |
| 9 | 136 |
| 36 | 137 ファイルシステムはOSにおいて重要な機能であるためGearsOSにおいても実装をする必要があると考えられ， |
| 138 当研究室では分散ファイルシステムやi-nodeを用いたファイルシステムの設計がされてきた\cite{cfile, directory}． | |
| 139 しかしながら，データの多重度や一貫性を確保するための機能がないため実装したい． | |
| 140 本研究では，データのレプリケーションやガベージコレクションの仕組みに必要である， | |
| 141 RedBlackTreeのCopyの仕組みを設計，構築を行った． | |
| 12 | 142 |
| 143 | |
| 144 | |
| 9 | 145 |
| 10 | 146 \chapter{軽量継続を基本とする言語CbC} |
| 147 | |
| 12 | 148 Continuation based C(CbC)\cite{cbcllvm,cbc}はC言語の下位言語であり， |
| 149 関数呼び出しを行わない軽量な継続を基本とするプログラミング言語である． | |
| 150 CbCは処理の単位のCodeGear，データの単位のDataGearといったGearの概念をもつ． | |
| 151 CodeGearはC言語などにおける関数と違い，gotoによるjmp命令が用いられ， | |
| 152 プログラムの継続においてコールスタックを持たない． | |
| 153 これを通常の関数による継続と区別して，軽量継続と呼ぶ． | |
| 154 軽量継続によってリフレクションのような処理の挿入や切り分けを容易にしている． | |
| 155 | |
| 156 \section{Gearの概念} | |
| 9 | 157 |
| 12 | 158 CbCには処理の単位のCodeGearとデータの単位であるDataGearという概念が存在する． |
| 9 | 159 CodeGearは\emph{\_\_code}という記述で宣言することができる． |
| 12 | 160 CbCはC言語の下位言語であるため，通常の関数も使用することは可能だが， |
| 161 基本的にCodeGearの単位でプログラミングを行う． | |
| 162 DataGearはCodeGearで入出力される変数データである． | |
| 163 図\ref{fig:dgcg}はCodeGearとDataGearの入出力の関係を表している． | |
| 164 CodeGearはDataGearを複数入力として受け取ることができ， | |
| 165 別のDataGearに複数書き込み出力することができる． | |
| 9 | 166 特に，入力のDataGearをInput DataGear，出力のDataGearをOutput DataGearと呼ぶ． |
| 12 | 167 gotoで次のCodeGearに遷移する際，Output DataGearを次のCodeGearのInput DataGearとして渡すことができる． |
| 9 | 168 |
| 169 \begin{figure}[ht] | |
| 170 \begin{center} | |
| 12 | 171 \includegraphics[width=100mm]{fig/cgdg.pdf} |
| 9 | 172 \end{center} |
| 173 \caption{CodeGearと入出力の関係図} | |
| 174 \label{fig:dgcg} | |
| 175 \end{figure} | |
| 176 | |
| 12 | 177 \section{gotoによる軽量継続} |
| 178 | |
| 9 | 179 CodeGearから次のCodeGearに遷移していく一連の動作を継続と呼ぶ． |
| 180 通常の関数の場合，関数から次の関数へ遷移する時にfunction callが行われる． | |
| 181 function callは前の関数へ戻る場合があり，そのためにcall stackを保存する． | |
| 182 他方，CbCの継続はfunction callをせずにgotoによるjmpで行われる． | |
| 12 | 183 jmpはfunction callと異なり，call stackによる変数などの環境を保存しない． |
| 9 | 184 よって，CbCのgotoによる継続はfunction callによる継続と比較して軽量であるといえる． |
| 185 そのことから，CbCにおける継続をfunction callによる継続と区別して，軽量継続と呼ぶ． | |
| 12 | 186 軽量継続の利点としてリフレクションのような処理をより柔軟に行える点が挙げられる． |
| 187 リフレクションはプログラム自身のメタデータを分析し， | |
| 188 それによってプログラムを実行時に書き換える一種のメタプログラミング手法である． | |
| 189 一般的にクラスやメソッド，関数の単位で書き換えが行われる． | |
| 190 手法の例としてJavaにおけるAspectJライブラリを用いたプログラミングが挙げられる． | |
| 191 軽量継続の場合，CodeGear遷移のどの地点においてもメタな処理を挿入することが可能であるため， | |
| 192 より柔軟なリフレクションが可能と考える。 | |
| 193 | |
| 194 | |
| 195 \section{CodeGearの記述例} | |
| 9 | 196 |
| 197 CbCのプログラム例をソースコード\ref{src:cbc}に示す． | |
| 198 まずmain関数においてadd1 CodeGearへgotoを行う． | |
| 199 その際add1へInput DataGearとしてnを渡す． | |
| 200 Cのgotoが\emph{goto label;}という記法で，ラベリングした箇所へjmpを行うのに対し， | |
| 201 CbCのgotoは\emph{goto add1(n);}という記法で，add1 CodeGearへn DataGearを渡してjmpを行う． | |
| 202 add1は処理の最後にadd2 CodeGearへgotoを行う． | |
| 203 その際Output DataGear out\_nをadd2のInput DataGearとして渡す． | |
| 204 このようにCbCではCodeGearのOutput DataGearを次のCodeGearのInput DataGearとして渡すことを繰り返すことで処理を進める． | |
| 205 | |
| 206 \lstinputlisting[caption=CbCのプログラム例,label=src:cbc]{src/hello.cbc} | |
| 207 | |
| 208 \chapter{信頼性の保証を目的としたGearsOS} | |
| 209 | |
| 210 GearsOS\cite{gears,gearsos,cr}は当研究室で開発している，信頼性と拡張性の両立を目的としたOSである． | |
| 211 GearsOSにはGearという概念があり，実行の単位をCodeGear，データの単位をDataGearと呼ぶ． | |
| 212 軽量継続を基本とし，stackを持たない代わりに全てをContext経由で実行する． | |
| 213 同様にGearの概念を持つContinuation based C（CbC）で記述されており，ノーマルレベルとメタレベルの処理を切り分けることが容易である． | |
| 214 また，GearsOSは現在開発途上であり，OSとして動作するために今後実装しなければならない機能がいくつか残っている． | |
| 215 | |
| 12 | 216 \section{3種類のGearsOS} |
| 217 | |
| 218 GearsOSには現在3つの種類がある． | |
| 18 | 219 1つ目が形式手法による信頼性の向上を目的とした，GearsAgdaと呼ばれるGearsOSである\cite{gearsagda}． |
| 220 これは，Agdaによって実装されており， | |
| 221 森 逸汰によるGearsAgdaによるRed Black Treeの検証などの取り組みがされている\cite{garbtree}． | |
| 222 2つ目はスタンドアロンOSの開発を目的とした，CbC\_xv6と呼ばれるGearsOSがある\cite{cbcxv6}． | |
| 223 これは，教育用に開発されたx.v6\cite{xv6}をCbCで書き換える形で実装している． | |
| 224 CbC\_xv6では仲吉 菜々子によるGears OSのCodeGear Managementの取り組みがされている\cite{gearscodemngment}． | |
| 225 3つ目はユーザーレベルタスクマネジメントの実装を目的としたGearsOSがある． | |
| 12 | 226 これは，CbCによって実装されており， |
| 18 | 227 分散ファイルシステムの設計やRedBlackTreeでのディレクトリシステムの構築などの取り組みがされている\cite{cfile, directory}． |
| 228 | |
| 229 本研究では，CbCによって実装されたユーザーレベルタスクマネジメント実装のGearsOSを対象に | |
| 230 ファイルシステムのレプリケーションやGC機能の実装を考える． | |
| 231 以下，GearsOSはユーザーレベルタスクマネジメント実装のGearsOSを指す． | |
| 12 | 232 |
| 233 \section{メタ処理を記述するmetaGear} | |
| 234 | |
| 235 図\ref{fig:meta-cgdg}はCodeGearの遷移とMetaCodeGearの関係を表している． | |
| 236 OSのプログラムはユーザーが実際に行いたい処理を表現するノーマルレベルと， | |
| 237 カーネルが行う処理を表現するメタレベルが存在する． | |
| 238 ノーマルレベルで見るとCodeGearがDataGearを受け取り， | |
| 239 処理後にDataGearを次のCodeGearに渡すという動作をしているように見える． | |
| 240 しかしながら，実際にはデータの整合性の確認や資源管理などのメタレベルの処理が存在し， | |
| 241 それらの計算はMetaCodeGearで行われる． | |
| 242 その際，MetaCodeGearに渡されるDataGearのことは特にMetaDataGearと呼ばれる． | |
| 243 また，CodeGearの前に実行されるMetaCodeGearは特にstubCodeGearと呼ばれ， | |
| 244 メタレベルを含めるとstubCodeGearとCodeGearを交互に実行する形で遷移していく． | |
| 18 | 245 |
| 12 | 246 \begin{figure}[ht] |
| 247 \begin{center} | |
| 248 \includegraphics[width=160mm]{fig/meta-cg-dg.pdf} | |
| 249 \end{center} | |
| 250 \caption{CodeGearとMetaCodeGearの関係} | |
| 251 \label{fig:meta-cgdg} | |
| 252 \end{figure} | |
| 253 | |
| 254 \section{全てのGearを参照するContext} | |
| 255 | |
| 9 | 256 ContextはGearsOS上全てのCodeGear，DataGearの参照を持ち，CodeGearとDataGearの接続に用いられる． |
| 257 OS上の処理の実行単位で，従来のOSにおけるプロセスに相当する機能であるといえる． | |
| 258 また，CodeGearをDataGearの一種であると考えると，ContextはGearの概念ではMetaDataGearに当たる． | |
| 259 Contextはノーマルレベルから直接参照されず，必ずMetaDataGearとしてMetaCodeGearから参照される． | |
| 260 それは，ノーマルレベルのCodeGearがContextを直接参照してしまうと， | |
| 261 メタレベルを切り分けた意味がなくなってしまうためである． | |
| 262 | |
| 263 図\ref{fig:context}はContextを参照する流れを表したものである． | |
| 264 まずCodeGearがOutputDataGearへデータをoutputする． | |
| 265 stubCodeGearはInputDataGear（前のCodeGearのOutputDataGear）とOutputDataGearをContextから参照し，次のCodeGearへgotoを行う． | |
| 266 CodeGearでの処理後，OutputDataGearへデータをoutputする． | |
| 267 | |
| 268 Contextはいくつかの種類に分けることができる． | |
| 269 OS全体のContextを管理するKernel Contextやユーザープログラムごとに存在するUser Context， | |
| 270 CPUやGPUごとに存在するCPU Contextがある． | |
| 18 | 271 |
| 9 | 272 \begin{figure}[ht] |
| 273 \begin{center} | |
| 12 | 274 \includegraphics[width=150mm]{fig/context.pdf} |
| 9 | 275 \end{center} |
| 276 \caption{Contextを参照する流れ} | |
| 277 \label{fig:context} | |
| 278 \end{figure} | |
| 279 | |
| 26 | 280 \section{モジュール化の仕組みInterface} |
| 23 | 281 |
| 26 | 282 Gears OSにはモジュール化の仕組みであるInterfaceという概念が存在する． |
| 23 | 283 モジュール化とはJavaのクラスのように複数のメソッドや属性を1つの機能として |
| 284 まとめて記述することである． | |
| 26 | 285 GearsOSではInterfaceによって，DataGearやCodeGearを複数まとめてモジュール化する． |
| 286 Interfaceは仕様と実装を分けて記述する． | |
| 287 例としてQueue Interfaceの仕様記述部分をソースコード\ref{src:Queue.h}に示す． | |
| 23 | 288 |
| 289 \lstinputlisting[label=src:Queue.h, caption=Queueのインターフェース]{src/Queue.h} | |
| 290 | |
| 26 | 291 Interfaceの仕様はC言語の構造体定義の形で記述する． |
| 23 | 292 2，3行目はDataGearを記述しており，DataGearは\texttt{union Data*}型で表現する． |
| 26 | 293 ここにはInterfaceにおいて，CodeGearが使用するDataGearを列挙する． |
| 294 5行目から10行目まではCodeGearの引数型を記述しており，\texttt{\_\_code}型で表現する． | |
| 295 ここに列挙したCodeGearはInterfaceのAPIとして機能する． | |
| 296 InterfaceのAPIの呼び出し例をソースコード\ref{exinterface}に示す． | |
| 23 | 297 |
| 298 \begin{lstlisting}[label=exinterface,frame=lrbt,caption={Interfaceの呼び出し}] | |
| 299 __code odgCommitCPUWorker3(struct CPUWorker* worker, struct Context* task) { | |
| 300 int i = worker->loopCounter; | |
| 301 struct Queue* queue = GET_WAIT_LIST(task->data[task->odg+i]); | |
| 302 goto queue->take(odgCommitCPUWorker4); | |
| 303 } | |
| 304 \end{lstlisting} | |
| 305 | |
| 26 | 306 4行目でgotoによってqueue Interfaceのtake CodeGearに継続するよう記述している． |
| 23 | 307 takeのinputDataGearにはodgCommitCPUWorker4 CodeGearを指定している． |
| 37 | 308 ソースコード\ref{src:Queue.h}の仕様記述ではtakeにはqueue，nextがinputDataGearの型として指定されている． |
| 23 | 309 しかし，実際に呼び出す際にはnextに当たるodgCommitCPUWorker4のみを渡している． |
| 310 仕様記述の際に全てのCodeGearの第1引数(inputDataGear)に渡している\texttt{Impl* queue}は， | |
| 311 仕様から実装のCodeGearにgotoするために必要な記述である． | |
| 312 軽量継続において，CodeGearを跨いで状態を保持することはできない． | |
| 313 よって仕様から実装に遷移するためには，実装のCodeGearをinput DataGearとして渡す必要がある． | |
| 37 | 314 このImplの第1引数はstubCodeGearで自動挿入されるため， |
| 315 実際にAPIを使用する際は渡す必要がない． | |
| 23 | 316 inputDataGearのnextはCodeGearの処理が終わった際に次にgotoするCodeGearを指定する． |
| 317 よって，take CodeGearの処理が全て終了すると，次にodgCommitCPUWorker4へgotoする． | |
| 318 nextは\texttt{next(...)}と引数に\texttt{...}が渡される． | |
| 24 | 319 これは仕様を記述する時点では不定である次に遷移するCodeGearのinputDataGearを表現している． |
| 320 GearsOSでgotoする際は実際にはContextから必要な値を取り出す． | |
| 321 よって，\texttt{...}は必要な値をContextから取り出すことを意味している． | |
| 322 | |
| 26 | 323 次にInterfaceの実装について説明する． |
| 324 Queue Interfaceの実装の1つであるSingleLinkedQueueをソースコード\ref{src:SingleLinkedQueue.cbc}に示す． | |
| 24 | 325 |
| 326 \lstinputlisting[label=src:SingleLinkedQueue.cbc, caption=Queueのインターフェース]{src/SingleLinkedQueue.cbc} | |
| 23 | 327 |
| 26 | 328 3行目の\texttt{\#impl as}はInterfaceの実装を記述する際に指定する． |
| 329 implの直後に実装したいInterfaceの仕様を指定し， | |
| 330 asの後ろには実装の型名を記述する． | |
| 331 であるから，\texttt{\#impl "Queue.h" as "SingleLinkedQueue.h"}は仕様Queueの実装を | |
| 332 SingleLinkedQueueとして定義することになる． | |
| 333 7行目の\texttt{createSingleLinkedQueue}はSingleLinkedQueueのコンストラクタを定義しており， | |
| 334 DataGearのアロケートやCodeGearを保持するメソッドの初期化を行っている． | |
| 335 8，9行目ではnewでアロケートを行っている． | |
| 336 アロケートのようなメタレベルの処理はノーマルレベルには記述されない． | |
| 337 そのためこのnewはC言語のnewとは違うGearsOS独自の記述であり， | |
| 338 実際にはメタレベルにアロケートを行う処理を挿入している． | |
| 339 10〜16行目ではSingleLinkedQueueで使用するCodeGearとDataGearを | |
| 28 | 340 queueのメソッドとして初期化している． |
| 26 | 341 CodeGearはQueueの仕様で記述したCodeGearと一致している． |
| 342 \texttt{C\_}で始まる記述にはenum CodeにおけるCodeGearの整数を格納している． | |
| 343 CodeGearはenum Codeで整数と対応付けられており， | |
| 344 この整数を元にCodeGearが参照される． | |
| 345 20行目以降では\texttt{putSingleLinkedQueue}や\texttt{takeSingleLinkedQueue} | |
| 346 のように，仕様で記述されたCodeGearを実装している． | |
| 37 | 347 15，16行目では実装の型定義で定義されたその実装独自のDataGearを初期化している． |
| 348 実装の型定義はソースコード\ref{src:SingleLinkedQueue.h}の通りである． | |
| 26 | 349 |
| 37 | 350 \lstinputlisting[label=src:SingleLinkedQueue.h, caption=SingleLinkedQueueの型定義]{src/SingleLinkedQueue.h} |
| 351 | |
| 352 3行目にあるように，実装の型定義ではimplキーワードで実装した型名を指定する． | |
| 353 4，5行目でSingleLinkedQueueが独自にもつtop，lastのDataGearを記述している． | |
| 23 | 354 |
| 355 \section{GearsOSのRedBlackTree} | |
| 9 | 356 |
| 28 | 357 Red-black tree(赤黒木)は二分探索木の一種で， |
| 358 ノードに赤か黒の色を付けて色に関するいくつかの条件をもつデータ構造である． | |
| 359 木に対する探索，挿入，削除操作における最悪計算量がO(log n)であるため， | |
| 360 赤黒木は大規模なデータを扱う際に効率的なデータ構造となる． | |
| 27 | 361 |
| 28 | 362 GearsOSのRedBlackTreeはGearsFileSystemで用いられる重要な構造の1つであり， |
| 363 ディレクトリ構造を表現するために使用されている． | |
| 38 | 364 GearsOSにおけるTreeの仕様記述をソースコード\ref{src:Tree.h}に示す． |
| 28 | 365 |
| 27 | 366 \lstinputlisting[label=src:Tree.h, caption=Treeの仕様]{src/Tree.h} |
| 37 | 367 |
| 368 ソースコード\ref{src:Tree.h}より，Treeはtree DataGearと | |
| 369 put，get，remove，nextの4つのCodeGearをAPIとして持っていることがわかる． | |
| 370 他にも探索や木のローテートを行うCodeGearが実装されているが， | |
| 371 RedBlackTreeのAPIとして提供しているのはput，get，removeの3つであり， | |
| 372 RedBlackTree Interfaceの使用者は木に対してこの3つの操作ができる． | |
| 373 それぞれノードの挿入，取得，削除を行うCodeGearである． | |
| 374 取得は，指定したnodeと一致するノードを木から探し， | |
| 375 存在すればそのまま返す． | |
| 38 | 376 次に，RedBlackTreeの実装の記述の一部をソースコード\ref{src:RedBlackTreeImpl.cbc}に示す． |
| 377 | |
| 28 | 378 \lstinputlisting[label=src:RedBlackTreeImpl.cbc, caption=RedBlackTreeの実装]{src/RedBlackTreeImpl.cbc} |
| 27 | 379 |
| 28 | 380 ソースコード\ref{src:RedBlackTreeImpl.cbc}の4行目から， |
| 40 | 381 RedBlackTreeはTreeの実装であることがわかり， |
| 28 | 382 13〜16行目で仕様に対応するCodeGearを初期化している． |
| 40 | 383 19，20行目ではRedBlackTreeが実装で持つ変数を初期化している． |
| 38 | 384 次に，RedBlackTreeの実装の型定義をソースコード\ref{src:RedBlackTree.h}に示す． |
| 385 | |
| 386 \lstinputlisting[label=src:RedBlackTree.h, caption=RedBlackTreeの実装の型定義]{src/RedBlackTree.h} | |
| 387 | |
| 388 \begin{figure}[ht] | |
| 389 \begin{center} | |
| 47 | 390 \includegraphics[width=100mm]{fig/rbtree_def.pdf} |
| 38 | 391 \end{center} |
| 39 | 392 \caption{RedBlackTreeのノードの種類} |
| 38 | 393 \label{fig:rbtree-def} |
| 394 \end{figure} | |
| 37 | 395 |
| 39 | 396 2〜7行目はRedBlackTreeが持つノードを表しており， |
| 397 それぞれのノードの役割は図\ref{fig:rbtree-def}のように示される． | |
| 398 rootはRedBlackTreeの全てのノードを参照できる親ツリーのルートノードを指す． | |
| 46 | 399 読み込み中のノードはcurrentで指されており，追加するノードをnewNodeで表している． |
| 400 previousは木を操作する以前の木を保持するノードであり， | |
| 401 これにより非破壊的な操作を可能とする． | |
| 39 | 402 また，RedBlackTreeは挿入，更新，削除の際に木の回転操作を行う． |
| 46 | 403 その際，起点のノード(current)に対して親のノードをparent，祖父母のノードをgrandparentで指す． |
| 404 8行目のnodeStackは木の操作時，木を辿るために使用するスタックである． | |
| 39 | 405 9行目のfindNodeNextはfindNode CodeGearを実行後，次に実行するCodeGearを保持する． |
| 406 10行目のresultはノードを探索する際のノードの比較結果を保持する． | |
| 407 | |
| 44 | 408 ソースコード\ref{src:RedBlackTree.h}にある通り， |
| 409 RedBlackTreeはNode構造体を複数持つ． | |
| 410 ソースコード\ref{src:Node.h}にNodeの型定義を示す． | |
| 411 | |
| 412 \lstinputlisting[label=src:Node.h, caption=Nodeの型定義]{src/Node.h} | |
| 413 | |
| 414 1，2行目よりノードのキーがint型であり，valueとしてDataGearのポインタを持つことがわかる． | |
| 415 また，3〜7行目よりleft，rightで子のNodeのポインタを持つことによって木構造を構築し， | |
| 416 enum ColorでRedBlackTreeとして必要なノードの色を表現していることがわかる． | |
| 417 | |
| 46 | 418 \section{ALLOCATE} |
| 419 | |
| 47 | 420 \lstinputlisting[label=src:allocate.h, caption=ALLOCATEの定義]{src/allocate.h} |
| 421 | |
| 29 | 422 \chapter{GearsFileSystem} |
| 423 | |
| 424 ファイルシステムはOSにおいてユーザーやアプリケーションが使用するファイルや | |
| 425 プロセスの管理に用いられる重要なシステムである． | |
| 426 そのため，GearsOSにおいてもi-nodeを用いたディレクトリシステムや， | |
| 427 DataGearManagerによる分散ファイルシステムの仕組みをもつ， | |
| 428 GearsFileSystemの取り組みがいくつかされてきた． | |
| 429 | |
| 430 \section{i-nodeを用いたディレクトリシステム} | |
| 431 | |
| 432 GearsFileSystemにはi-nodeを用いたディレクトリの仕組みが存在する\cite{directory}． | |
| 433 i-nodeは主にUnix系のファイルシステムで用いられる， | |
| 434 ファイルの属性情報が書かれたデータである． | |
| 435 inodeにおけるファイルの属性情報は表\ref{table:inode}のようなものがある． | |
| 436 またinodeは識別番号としてinode numberを持つ． | |
| 437 inode numberは一つのファイルシステム内で一意の番号であり，\emph{ls -i}コマンドで確認可能である． | |
| 438 inodeはファイルシステム始動時にinode領域をディスク上に確保する． | |
| 439 そのためinode numberには上限があり，それに伴いファイルシステム上で扱えるファイル数の上限も決まる． | |
| 440 inode numberの最大値は\emph{df -i}コマンドで確認可能である． | |
| 441 | |
| 442 \begin{table}[htpb] | |
| 443 \begin{center} | |
| 444 \small | |
| 445 \begin{tabular}[htpb]{|c||c|} | |
| 446 \hline | |
| 447 File Types & directoryやregular fileなど，ファイルの種類 \\ | |
| 448 \hline | |
| 449 Permissions & read write executeの実行可否\\ | |
| 450 \hline | |
| 451 UID & ファイル所有者のID \\ | |
| 452 \hline | |
| 453 GID & ファイル所有グループのID \\ | |
| 454 \hline | |
| 455 File Size & ファイルのサイズ \\ | |
| 456 \hline | |
| 457 Time Stamps & ファイル作成，編集日時 \\ | |
| 458 \hline | |
| 459 Number of link & ハードリンクの数 \\ | |
| 460 \hline | |
| 461 Location on hard disk & データのアドレス\\ | |
| 462 \hline | |
| 463 \end{tabular} | |
| 464 \caption{inodeでのファイル属性情報} | |
| 465 \label{table:inode} | |
| 466 \end{center} | |
| 467 \end{table} | |
| 468 | |
| 469 GearsFileSystemではi-nodeをi-node numberがkey， | |
| 470 i-nodeでのファイル属性情報をvalueであるノードを持つinode treeをRedBlackTreeで表現している． | |
| 471 また，ファイル名からi-node numberを検索するためのindex treeも同じRedBlackTreeで表現している． | |
| 31 | 472 データ構造にRedBlackTreeのみを用いているのは， |
| 29 | 473 ls，cd，mkdirといった，ディレクトリ操作を行うためのUnix Likeなユーザーインターフェースをもつ． |
| 31 | 474 図\ref{fig:GearsDir}にGears Directoryの処理の例を示す． |
| 475 | |
| 476 \begin{figure}[ht] | |
| 477 \begin{center} | |
| 478 \includegraphics[width=160mm]{fig/gears_dir.png} | |
| 479 \end{center} | |
| 480 \caption{i-nodeを用いたディレクトリシステムの処理の流れ} | |
| 481 \label{fig:GearsDir} | |
| 482 \end{figure} | |
| 29 | 483 |
| 32 | 484 lsコマンドはディレクトリ内のファイルやファイル自体の情報を出力するコマンドである． |
| 485 \texttt{ls hoge.txt}を実行すると\textcircled{\scriptsize 1}index treeを参照し， | |
| 486 ファイル名hoge.txtからi-node numberの2を取得する． | |
| 487 次に，\textcircled{\scriptsize 2}i-node treeを参照し， | |
| 488 i-node numberを元にファイルの属性を取得し，lsコマンドの場合はそれを出力する． | |
| 489 | |
| 11 | 490 \section{非破壊RedBlackTreeによる構成} |
| 15 | 491 |
| 492 ディスク上とメモリ上でデータの構造は，RedBlackTreeに統一する． | |
| 493 一般的に，ディスク上のデータ構造としてB-Treeが用いられることが多い． | |
| 494 なぜならば，HDDを用いる場合はブロックへのアクセス回数を減らしデータアクセスの時間を短くするために， | |
| 495 B-Treeのようなノードを複数持つことができる構造が効果的だからである． | |
| 496 その点ではRedBlackTreeはB-Treeに劣る． | |
| 497 しかしながら，SSDはランダムアクセスによってデータにアクセスするため， | |
| 498 RedBlackTreeでなくB-Treeを用いる利点は少ないと考える． | |
| 499 よって，ディスク上とメモリ上のデータ構造をRedBlackTreeに統一することが考えられる． | |
| 500 そうすることによって，ディスク上とメモリ上のデータのやりとりは単純なコピーで実装できる． | |
| 501 | |
| 11 | 502 \section{RedBlackTreeのトランザクション} |
| 9 | 503 |
| 504 トランザクションはDBの重要な機能の一つである． | |
| 505 データの競合を防ぎ信頼性を向上させ，DBとしても扱えるよう | |
| 506 トランザクションの仕組みを考える必要がある． | |
| 507 今回，ファイルシステムは全てRedBlackTreeで実装するため， | |
| 508 RedBlackTreeのノードに対するトランザクションを考える． | |
| 509 | |
| 510 トランザクションをwriteとreadに分けて考える． | |
| 511 writeする場合，トランザクションはRedBlackTreeのルートの置き換えと対応する． | |
| 512 writeするために，まずルートを生やし書き込みが終わった後ルートを置き換える． | |
| 513 そのため，書き込みの並列度はルートの数と一致する． | |
| 514 しかしながら，ルートの置き換えは競合的なので， | |
| 515 複数プロセスから同時に書き込みを行っても1つしか成功しない． | |
| 516 よって，単一のRedBlackTreeに複数の書き込みポイントを作り， | |
| 517 並行実行可能にする必要がある． | |
| 518 | |
| 519 % TODO: writeトランザクションの図を入れたい | |
| 520 | |
| 521 RedBlackTreeに複数の書き込みポイントを作るために， | |
| 522 キーごとのルートを作成する． | |
| 523 ノードはそれぞれがキーとRedBlackTreeを持つ状態になる． | |
| 524 writeする際は，そのキーのルートを置き換える． | |
| 525 それによって，RedBlackTreeは複数の書き込みポイントを持つことができ， | |
| 526 writeを並行実行することが可能となる． | |
| 527 | |
| 528 図\ref{fig:Transaction}にトランザクショナルなwrite操作を表す． | |
| 529 Aの木はファイルシステム全体を表すRedBlackTreeである． | |
| 530 ノードNのデータに対して書き込みすることを考えると， | |
| 531 キーがaであるBの木のルートからロックしCの木を作成して， | |
| 532 Bの木からCの木のルートに入れ替えることで書き込みを行う． | |
| 533 この書き込みを行っている際， | |
| 534 Aの木のノードはロックしないのでAの木のどのノードに対しても並行して書き込み可能となる． | |
| 535 | |
| 536 \begin{figure}[ht] | |
| 537 \begin{center} | |
| 47 | 538 \includegraphics[width=150mm]{fig/transaction.png} |
| 9 | 539 \end{center} |
| 540 \caption{トランザクショナルなwrite操作} | |
| 541 \label{fig:Transaction} | |
| 542 \end{figure} | |
| 543 | |
| 544 % TODO: read時常に最新の情報が取れないことを説明する図を入れたい | |
| 545 | |
| 546 readはデータに変更を加えないため，複数同時に同じノードを読み込むことが可能である． | |
| 547 しかし，常に最新の情報を読み込めるとは限らない． | |
| 548 最新の情報が欲しい場合は書き込みを一旦止めるような処理が必要になる． | |
| 549 | |
| 11 | 550 \section{ディスク上とメモリ上のデータ構造} |
| 9 | 551 |
| 11 | 552 |
| 553 ファイルシステムは全てRedBlackTreeで構成する． | |
| 554 それにより，プログラムの証明がより簡単になるからである． | |
| 555 また，ファイルシステムとDBはデータを保管するという本質的な役割は同じである． | |
| 556 よって，それらはまとめてRedBlackTreeで構成する． | |
| 557 | |
| 558 ファイルシステムとDBの違いとして，スキーマが挙げられる． | |
| 559 DBは事前にスキーマを定義し，それに沿ってデータを挿入，参照する． | |
| 560 対して，ファイルシステムにはスキーマに当たるものがなく， | |
| 561 データはファイルパスによって管理される． | |
| 562 スキーマを定義することによってデータは構造化され， | |
| 563 構造化されたデータは非構造化データと比較して， | |
| 564 インデックスを作成することが容易であり，データの検索性が向上する利点がある． | |
| 565 しかしながら，スキーマはDBの運用中に変更されることがあり， | |
| 566 スキーマを変更した以前へロールバックができない問題がある． | |
| 567 | |
| 568 ロールバックがスキーマの変更によって出来なくなることは信頼性に問題があると考えると， | |
| 569 スキーマを定義する必要のないスキーマレスなDBが必要になる． | |
| 570 ファイルシステムはスキーマレスなDBといえるので，ファイルシステムを構築しつつ | |
| 571 DBがスキーマによって実現していた機能を付け加えることを試みる． | |
| 572 | |
| 573 RedBlackTreeは実装によって，操作が破壊的なものとそうでないものがある． | |
| 574 今回用いるのは，非破壊的な実装のRedBlackTreeである． | |
| 575 図\ref{fig:TreeEdit}は非破壊的編集を行うRedBlackTreeを表している． | |
| 576 編集前の木構造の6のノードをAにアップデートすることを考える． | |
| 577 まず，ルートノードからアップデートしたいノード6までをコピーする． | |
| 578 その後，コピーしたもののノード6をAにアップデートする． | |
| 579 これにより，アップデート前のノード6を破壊することなくAにアップデートが可能である． | |
| 580 参照する時は，黒のルートノードから辿れば古い6が，赤のルートノードから辿れば新しいAが見える． | |
| 581 この仕組みは，データのバックアップやDBのロールバックに用いることが可能だと考える． | |
| 582 | |
| 583 \begin{figure}[ht] | |
| 584 \begin{center} | |
| 47 | 585 \includegraphics[width=150mm]{fig/nonDestroyTreeEdit.pdf} |
| 11 | 586 \end{center} |
| 587 \caption{非破壊的なTree編集} | |
| 588 \label{fig:TreeEdit} | |
| 589 \end{figure} | |
| 590 | |
| 41 | 591 \section{DataGearManagerによる分散ファイルシステム} |
| 11 | 592 |
| 14 | 593 \chapter{GearsFileSystemにおけるGCとレプリケーション} |
| 21 | 594 |
| 44 | 595 本章ではRedBlackTreeのCopyによるGCとレプリケーションの基本設計を述べる． |
| 596 GC，レプリケーション，バックアップをRedBlackTreeのコピーを基礎とする， | |
| 597 統一的な仕組みにより実装することが考えられる． | |
| 598 | |
| 14 | 599 \section{ファイルシステムの信頼性に関する機能} |
| 600 | |
| 601 ファイルシステムはデータを保持することを基本的な機能としている． | |
| 602 信頼性に関する機能など，その他の機能は追加機能として実装する． | |
| 603 ファイルシステムやDBにおける信頼性に関する追加機能として， | |
| 604 システムの電源断時にデータが残るpersistency， | |
| 605 データを書き込めたかどうかを判定するatomic write， | |
| 606 1つのノードが失われた際にデータを保護する多重性， | |
| 607 複数のコピーを調停するコミット機構などが挙げられる． | |
| 15 | 608 |
| 14 | 609 現状のGearsOSには分散ファイルシステムの通信機能やUnix Likeな |
| 610 インターフェースを持つi-nodeファイルシステムの基本機能は存在するものの， | |
| 611 多重性やメモリ管理などの信頼性を確保するための機能が存在しない． | |
| 612 データの多重度を確保するための一般的な手法として， | |
| 613 データのバックアップやシステム自体のレプリケーションをすることが挙げられる． | |
| 614 メモリ管理の機能としてはガーベージコレクションが挙げられる． | |
| 15 | 615 ガベージコレクションは通常プログラム言語のレイヤで行われる． |
| 42 | 616 これらの機能をファイルシステムのレベルで実装することで， |
| 617 より信頼性の高いファイルシステムを構築したい． | |
| 14 | 618 |
| 16 | 619 \section{メモリの管理手法} |
| 14 | 620 |
| 15 | 621 GCのアルゴリズムは大きく分けてMark \& Sweep GC，Reference counting GC， |
| 622 Copying GCの3つの種類が存在する． | |
| 20 | 623 Mark \& Sweep GCはマークフェーズとスイープフェーズからなる。 |
| 624 マークフェーズはヒープ上でルートから参照することができるオブジェクト全てにマークをし， | |
| 625 その後、スイープフェーズでマークされていないオブジェクトを | |
| 626 使用されていないオブジェクトのリストであるフリーリストに接続することでGCを行う． | |
| 627 Reference counting GCはオブジェクトの被参照数を表すReference counterを用いるGCである． | |
| 628 新たに参照される度にReference counterをインクリメントし， | |
| 629 参照が外れる度にデクリメントする． | |
| 630 そのようにして，カウンターが0になった時点でフリーリストに接続することでGCを行う． | |
| 15 | 631 CopyingGCはメモリ上のヒープ領域をFrom領域とTo領域に分割し， |
| 20 | 632 ルートから参照できるオブジェクトをFrom領域からTo領域にコピーする． |
| 633 From領域を参照していたポインタはTo領域のオブジェクトを参照するように置き換える． | |
| 634 その後，From領域とTo領域を入れ替えることでGCを行う． | |
| 15 | 635 |
| 20 | 636 一般的にこれらのGC手法は複数を組み合わせて用いられる． |
| 637 世代別GCではオブジェクトの生存期間によって適用するGCアルゴリズムを使い分ける． | |
| 638 アロケートされてすぐのオブジェクトを新世代オブジェクト， | |
| 639 任意の回数のGCを生き残ったオブジェクトを旧世代オブジェクトとし， | |
| 640 それぞれの特性に合ったGCアルゴリズムを適用する． | |
| 641 すぐに回収されることが多い新世代オブジェクトはCopying GCで網羅的にGCをし， | |
| 642 長く生き残る旧世代オブジェクトはMark \& Sweep GCで適宜回収するなどが例として挙げられる． | |
| 643 このように複数のGCアルゴリズムを組み合わせることで， | |
| 644 それぞれのアルゴリズムの利点を享受できる． | |
| 645 | |
| 646 また，メモリ管理手法としてRust言語の所有権がある． | |
| 647 所有権ではメモリを所有する変数がスコープを抜ける時に， | |
| 648 同時にメモリも解放する． | |
| 649 そのためRustではGCの仕組みを必要とせず， | |
| 650 より高速にメモリの管理を行うことができる． | |
| 15 | 651 |
| 16 | 652 \section{GearsFileSystemのGC} |
| 653 | |
| 20 | 654 GearsFileSystemのGCはCopying GCを基本的なアルゴリズムとする． |
| 21 | 655 他のGC手法と比較して参照できるオブジェクトをコピーするだけであるため， |
| 656 実装が簡単で，より高いスループットが期待できる． | |
| 657 Mark \& Sweep GCやReference counting GCの場合は， | |
| 658 GCを複数フェーズで実装したり，カウンターの扱いについて考える必要がある． | |
| 659 また，同様の構造をコピーするのみで実装することによって， | |
| 660 データの透過性の確保がしやすい． | |
| 661 ファイルやディレクトリを表現するRedBlackTreeは全てのデータの参照を持つ． | |
| 662 そのため，オブジェクトルートからオブジェクトを辿ってコピーを行うCopying GCとの相性が良い． | |
| 15 | 663 |
| 21 | 664 一般的なCopying GCではFrom領域上のオブジェクトをTo領域にコピーする形で実装される． |
| 665 一方，GearsFileSystemではファイルやディレクトリの基本構造であるRedBlackTreeをコピーする． | |
| 666 ファイルやディレクトリの操作を行うFromのRedBlackTreeから， | |
| 667 ルートから辿れるノードのみをToのRedBlackTreeとしてコピーする． | |
| 668 それにより，辿れなかったノード，つまり参照されていないノードはコピーされず， | |
| 669 不要なオブジェクトが回収された状態となる． | |
| 670 | |
| 671 \begin{figure}[ht] | |
| 672 \begin{center} | |
| 673 \includegraphics[width=160mm]{fig/rbtree_gc.png} | |
| 674 \end{center} | |
| 675 \caption{RedBlackTReeのCopyによるGC} | |
| 676 \label{fig:TreeCopyGC} | |
| 677 \end{figure} | |
| 678 | |
| 679 DBの重要な機能の一つにロールバックがある． | |
| 680 RDBのロールバックは， | |
| 681 コミットするまではトランザクションの開始時点に戻ることができる機能を持つ． | |
| 682 コミットが完了するとそれ以前の状態に戻すことはできないが， | |
| 683 データのバックアップをとっておくことで復元を行う． | |
| 684 | |
| 43 | 685 RedBlackTreeのルートノードがデータのバージョンの役割を果たしていることを利用し， |
| 686 データの復元が行える仕組みを考える． | |
| 21 | 687 非破壊的なTree編集はアップデートのたびに，ルートノードを増やす． |
| 688 つまり，ルートノードはアップデートのログと言えその時点のデータのバージョンを表していると考えることができる． | |
| 689 よって，ロールバックを行いたい場合は参照を過去のルートノードに切り替える． | |
| 690 | |
| 691 ルートノードはデータのアップデート時に増えるため， | |
| 692 データが際限なく増加していく問題がある． | |
| 693 この問題はCopyingGCを行うことによって解決する． | |
| 694 まず，RedBlackTreeを丸ごとコピーして最新のルートを残して他のルートは削除する． | |
| 695 その後，コピーしたものはバックアップないしログとしてディスクに書き込む． | |
| 696 そうすることで，データの増加によるリソースの枯渇を防ぎ， | |
| 697 かつデータのログ付きバックアップを作成することで信頼性の向上が期待できる． | |
| 14 | 698 |
| 699 | |
| 700 \section{GearsFileSystemのレプリケーション} | |
| 11 | 701 |
| 42 | 702 DBの多重性を確保する機能としてレプリケーションがある． |
| 703 レプリケーションはデータや状態が等しいレプリカを別のノードに生成する機能である． | |
| 704 レプリケーション機能があることによって，地理的に距離のあるノードにレプリカを設置することが可能になり， | |
| 705 災害などによって発生するシステム障害を防止することや， | |
| 706 アクセス分散によるネットワーク負荷の低減につながる． | |
| 707 そのため，GearsFileSystemにおいてもレプリケーションの機能を実装したい． | |
| 43 | 708 |
| 42 | 709 GearsFileSystemではディレクトリをRedBlackTreeによって構成しており， |
| 710 RedBlackTreeから全てのデータにアクセス可能である． | |
| 711 よって，RedBlackTreeのコピーを行うことによって， | |
| 712 FileSystemのレプリカを作成することが可能であると考えられる． | |
| 713 GearsFileSystemのレプリケーションの基本設計を図\ref{fig:RBTreeReplica}に示す． | |
| 714 | |
| 22 | 715 \begin{figure}[ht] |
| 716 \begin{center} | |
| 717 \includegraphics[width=160mm]{fig/rbtree_replica.png} | |
| 718 \end{center} | |
| 42 | 719 \caption{GearsFileSystemのレプリケーションの基本設計} |
| 720 \label{fig:RBTreeReplica} | |
| 22 | 721 \end{figure} |
| 21 | 722 |
| 42 | 723 基本的には図\ref{fig:TreeCopyGC}に示されているGCの仕組みと同様で， |
| 724 RedBlackTreeのCopyで構成される． | |
| 725 レプリケーションにおいてコピー元をメイン，コピーをレプリカと呼ぶ場合， | |
| 726 Node1がメインでNode2がレプリカとなる． | |
| 727 Node1はGCの仕組みと同様であり，違いはNode2にもコピーを行う部分である． | |
| 728 このように，GCとレプリケーションを同様の仕組みで実装することが考えられる． | |
| 729 しかし，Node2にコピーを行う際はNode1とNode2間で操作やデータを送信するための | |
| 730 通信の仕組みが必要である． | |
| 731 レプリケーションを実装する際は通信の仕組みについて考える必要がある． | |
| 732 | |
| 43 | 733 既存のDBにおけるレプリケーション手法は同期のタイミングやレプリカの作成単位によっていくつか種類がある． |
| 734 | |
| 735 \section{コピー実行のタイミング} | |
| 736 | |
| 47 | 737 TODO: ここはContextレベルに書き直す |
| 738 | |
| 43 | 739 GCやレプリケーション，バックアップはそれを実行するタイミングが重要である． |
| 740 GCはメモリの使用状況に応じて実行される． | |
| 741 例えば，RedBlackTreeに新規ノードを追加する際にメモリが不足した場合などが | |
| 742 GCを実行するタイミングとして挙げられる． | |
| 743 レプリケーションは同期のタイミングがあり，同期型，非同期型，準同期型が挙げられる． | |
| 744 また，バックアップは1日に1回，週に1回など定期的な実行をする． | |
| 745 そのため，RedBlackTreeのコピーにコピー実行のタイミングを制御する機構が必要である． | |
| 746 GearsOSは拡張性の高いCbCによって記述され，本来実行したい処理に追加の処理を挿入することが比較的容易に可能である． | |
| 747 図\ref{fig:GCTiming}にGC実行処理の挿入の仕組みの例を示す． | |
| 748 | |
| 749 \begin{figure}[ht] | |
| 750 \begin{center} | |
| 751 \includegraphics[width=160mm]{fig/timing.png} | |
| 752 \end{center} | |
| 753 \caption{GC実行処理の挿入} | |
| 754 \label{fig:GCTiming} | |
| 755 \end{figure} | |
| 42 | 756 |
| 43 | 757 矢印は軽量継続であり， |
| 758 \textcircled{\scriptsize 1}ではメモリアロケーションを必要とする本来行いたい処理を表している． | |
| 759 \textcircled{\scriptsize 2}はメモリ使用率をチェックするCodeGearを挿入し， | |
| 760 使用率が80\%以上の場合にGCを実行する． | |
| 761 メモリ使用率をチェックするCodeGearは条件によって実行するCodeGearを切り替えるものであり， | |
| 762 既存のGearsOSのコードにもこのような処理を行うものは存在し， | |
| 763 例としてSingleLinkedStackのコードの一部をソースコード\ref{src:isEmpty.cbc}に示す． | |
| 764 | |
| 765 \lstinputlisting[label=src:isEmpty.cbc, caption=実行するCodeGearの切り替えのコード]{src/isEmpty.cbc} | |
| 766 | |
| 767 CodeGearは遷移先のCodeGearの参照を持つ必要があるため， | |
| 768 inputDataGearとしてnextとwhenEmptyを渡している． | |
| 769 条件分岐は通常のif文で行われ，条件ごとに次のCodeGearを指定している． | |
| 770 | |
| 771 このようにして，条件分岐をして実行するCodeGearを切り替えることができる． | |
| 772 しかし，GCは本来行いたい処理ではなくメタレベルの処理である． | |
| 773 そのため，GCへの切り替えにおいてソースコード\ref{src:isEmpty.cbc}のようなコードを記述すると， | |
| 774 ノーマルレベルとメタレベルが混在するCodeGearとなってしまう問題がある． | |
| 775 | |
| 776 | |
| 777 | |
| 11 | 778 \chapter{CopyRedBlackTreeの実装} |
| 14 | 779 |
| 780 データのバックアップやレプリケーション，GCの機能を実装するためには， | |
| 781 データのコピーをする必要がある． | |
| 782 GearsOSのファイルシステムにおいて，データは全てRedBlackTreeに格納される． | |
| 783 しかしながら，現状のRedBlackTreeには木をコピーする機能が無い． | |
| 784 よって，RedBlackTreeに木のコピー機能を実装する必要がある． | |
| 46 | 785 CopyRedBlackTreeの実装について述べる． |
| 14 | 786 |
| 46 | 787 \section{Tree InterfaceのCopy API} |
| 788 | |
| 789 CopyRedBlackはTree InterfaceのAPIの1つとして実装した． | |
| 790 ソースコード\ref{src:TreeCopy.h}にCopy APIを追加したTree Interfaceの仕様定義を示す． | |
| 791 | |
| 792 \lstinputlisting[label=src:TreeCopy.h, caption=Tree Interfaceの使用定義(Copy追加後)]{src/TreeCopy.h} | |
| 793 | |
| 794 10行目にcopy()が追加されており，inputDataGearは\emph{\_\_code} nextのみとしている． | |
| 795 これにより， | |
| 796 \texttt{goto tree->copy(next);}といった記述でRedBlackTreeのコピーを行うことができる． | |
| 797 次にRedBlackTreeの実装の型定義をソースコード\ref{src:CopyRedBlackTree.h}に示す． | |
| 798 9，12行目にある通り，コピー時に使用するtoStackを1つと | |
| 799 木のコピーが完了しているかどうかを示すcopiedフラグを追加している． | |
| 800 今回の実装ではStackを2つ使用する． | |
| 801 追加したtoStackの他に，元からRedBlackTreeの操作に使用しているnodeStackを用いる． | |
| 802 これらのStackはdataとしてNode構造体のポインタを持つ． | |
| 803 | |
| 804 \lstinputlisting[label=src:CopyRedBlackTree.h, caption=RedBlackTreeの実装の型定義(Copy追加後)]{src/CopyRedBlackTree.h} | |
| 805 | |
| 806 % \lstinputlisting[label=src:CopyRedBlackTree.cbc, caption=CopyRedBlackTreeの実装]{src/CopyRedBlackTree.cbc} | |
| 19 | 807 |
| 11 | 808 \section{コピーのアルゴリズム} |
| 19 | 809 |
| 46 | 810 コピーは2つのStackを使用し，left方向から深さ優先でRedBlackTreeのノードをリーフ方向に降りながら行う． |
| 811 図\ref{fig:TreeAndStack}にコピー時のある地点でのコピー元の木と2つのStackの状態を例示する． | |
| 812 leftDownを2回行い，\texttt{tree->current}がkeyが1のノードを指している． | |
| 813 この時，木を辿るためのnodeStackは\texttt{tree->current}以前に辿った3と2のノードが積まれている． | |
| 814 toStackにはコピー元の木のノードとkey，value，colorの値が同じでアドレスが異なるノードが積まれている． | |
| 815 ノードは辿った際にコピーを行いtoStackへと積むため，すでに辿った3，2，1のノードが積まれている． | |
| 816 葉ノードまでたどり着いた時やleft，rightがすでに辿ったノードだった場合はupでroot方向に戻る． | |
| 817 その際は，\texttt{tree->current}を親ノードに付け替え，nodeStackとtoStackを1回popする． | |
| 818 toStackは新規にアロケートした子ノードと親ノードを接続したり， | |
| 819 すでにノードをアロケートしているかどうかを判断するなど， | |
| 820 コピー先の木を操作したり状態を確認したりするために必要である． | |
| 821 例えば，upする場合はコピー元のrightノードの存在を確認し， | |
| 822 toStackのtopをみてすでにrightノードを新規にアロケートしているかを見ることで， | |
| 823 さらにupするかどうかを判断するなどがある． | |
| 19 | 824 |
| 825 \begin{figure}[ht] | |
| 826 \begin{center} | |
| 46 | 827 \includegraphics[width=150mm]{fig/copy_algo4.png} |
| 19 | 828 \end{center} |
| 46 | 829 \caption{コピー元のTreeと2つのStackの状態の例} |
| 830 \label{fig:TreeAndStack} | |
| 19 | 831 \end{figure} |
| 832 | |
| 46 | 833 図\ref{fig:CopyCGTransition}にCopy時のCodeGearの大まかな遷移を示す． |
| 834 四角ノードがCodeGear，丸ノードが遷移条件を表す． | |
| 835 それらを囲む四角はCodeGearの遷移をLeftDown，RightDown，Upの3つのフェーズに区切ったもので， | |
| 836 図を簡略化するためのものである． | |
| 837 フェーズの四角に矢印が向くと，フェーズが持つStart(オレンジで示される箇所)から遷移が始まる． | |
| 838 青のStart，EndはCopyの始めと終わりである． | |
| 839 実際にはleftDownなどはleftDown1，leftDown2のような複数のCodeGearで構成され， | |
| 840 それぞれでStackの操作やアロケート，ノードの存在確認を行う． | |
| 841 Upはすでに木全体を辿ったかどうかを判定し， | |
| 842 辿っていた場合はswap CodeGearへ遷移を行う． | |
| 843 swapはコピー元の木とコピー先の木を入れ替える． | |
| 844 これはCopying GCにおけるFrom領域とTo領域を入れ替える操作を想定している． | |
| 11 | 845 |
| 46 | 846 \begin{figure}[ht] |
| 847 \begin{center} | |
| 848 \includegraphics[width=160mm]{fig/copy_algo3.png} | |
| 849 \end{center} | |
| 850 \caption{Copy時のCodeGearの大まかな遷移} | |
| 851 \label{fig:CopyCGTransition} | |
| 852 \end{figure} | |
| 11 | 853 |
| 46 | 854 \section{コピーの実装の詳細} |
| 855 | |
| 11 | 856 |
| 857 | |
| 858 \chapter{まとめと今後の課題} | |
| 859 | |
| 44 | 860 本研究ではGearsOSのファイルシステムであるGearsFileSystemにおける |
| 861 GCとレプリケーションについての考察，CopyRedBlackTreeの実装と考察を行った． | |
| 11 | 862 |
| 863 また，今後の課題や議題として次のようなものが挙げられる． | |
| 864 | |
| 865 \section{ファイルシステムにおけるスキーマ} | |
| 9 | 866 |
| 867 従来のRDBのようなスキーマが存在すると， | |
| 868 個別にバックアップなどを取らない限り | |
| 869 スキーマの変更以前にロールバックすることができない． | |
| 870 しかしながら，実際運用する上でスキーマを変更することは多々ある． | |
| 871 これは，データの信頼性を低下させると考える． | |
| 872 また，DB上のデータ構造とプログラム上で扱うデータ構造に差が生まれる | |
| 873 インピーダンスミスマッチが発生し，DBのデータをプログラムが扱う際に | |
| 874 その差を埋めるような変換を必要とする場合が生まれる． | |
| 875 一方で，スキーマがあることによってデータに対して高度な操作を行うことができ， | |
| 876 また，インデックスを容易に作成することができるといったメリットがある． | |
| 877 よって，スキーマフルなDBとスキーマレスなDBはそれぞれメリットデメリットがあり， | |
| 878 状況によって使い分けるのが良いと考える． | |
| 879 | |
| 880 今回は，非構造化データ内であれば構造化データを扱うことが可能であることと， | |
| 881 信頼性を保証したいという点から， | |
| 882 スキーマレスなDBとしてのファイルシステムを考える． | |
| 883 しかしながら，トランザクションの仕組みを作る上でRedBlackTreeに対し， | |
| 884 キーを設定することから完全なスキーマレスとは言えない構成となる． | |
| 885 | |
| 886 GearsOSのデータは全てDataGearで表される． | |
| 887 よって，GearsOSにおけるファイルシステムはDataGearの集合となる． | |
| 888 スキーマレスとはキーがない状態のことといえるが， | |
| 889 DataGearはキーが設定されていないため，その集合自体にスキーマは無い． | |
| 890 そのことから，GearsOSにおけるスキーマとはDataGear上のキーの構成であることがわかる． | |
| 891 なお，今回のRedBlackTreeによる構成の場合，キーはRedBlackTreeを指す． | |
| 892 DataGearはKernelのContextからプロセスのContextを経由して全て繋がっている． | |
| 893 よって，KernelのContext上にキーを用いたDataGearの参照を書き込む． | |
| 894 | |
| 11 | 895 \section{RedBlackTreeによる権限の表現} |
| 9 | 896 |
| 897 ファイルの権限はファイルシステムの重要な機能の一つであるため実装する必要がある． | |
| 898 今回のRedBlackTreeによる構成の場合，木のルートの所持者を設定することが | |
| 899 ファイルに対して権限を設定することにあたる． | |
| 900 ルートに対してアクセスする権限がなければ， | |
| 901 読み書きができないといった実装になると考える． | |
| 902 \section{データクエリ言語} | |
| 903 | |
| 904 ユーザーやアプリケーションがDBのデータにアクセスするための言語設計を | |
| 905 する必要がある． | |
| 906 RedBlackTreeのキーを用いたインデックスに対応し， | |
| 907 従来のSQLと比較してより柔軟なクエリを実行できることを目指したい． | |
| 908 | |
| 909 \section{ログなどの時系列データの保存} | |
| 910 | |
| 911 時系列データは通常のデータと違った保存の方法を考えることができる． | |
| 912 時系列に並んでいることを生かしたデータの保存方式や， | |
| 913 時間経過に伴うデータの重要性の変化を考慮に入れたデータ圧縮の方法をとることで， | |
| 914 より効率的な保存が可能だと考える． | |
| 915 | |
| 916 \section{スタンドアロンなDB} | |
| 917 | |
| 918 MySQLやPostgreSQLなどはOSの機能としてではなく， | |
| 919 それ自体が一つのアプリケーションとして自立的に動作している． | |
| 920 自立的に動作するのは，データのポータビリティを向上させるためである． | |
| 921 スタンドアロンなDBの形にするか， | |
| 922 その他の方法でポータビリティを向上させる手法を考えたい． | |
|
2
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
923 |
| 43 | 924 \section{GCタイミングに必要な処理の自動挿入} |
| 925 | |
|
2
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
926 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
927 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
928 % %謝辞 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
929 \input{chapter/thanks.tex} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
930 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
931 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
932 %参考文献 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
933 \nocite{*} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
934 \bibliography{reference} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
935 \bibliographystyle{junsrt} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
936 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
937 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
938 %発表履歴 |
| 20 | 939 \input{chapter/history.tex} |
| 940 \addcontentsline{toc}{chapter}{研究関連論文業績} | |
|
2
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
941 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
942 %付録 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
943 \addcontentsline{toc}{chapter}{付録} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
944 \appendix |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
945 \input{chapter/appendix.tex} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
946 \end{document} |