Mercurial > hg > Papers > 2024 > matac-master
annotate Paper/master_paper.tex @ 24:f0c0e873e3c1
...
| author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 12 Jan 2024 18:52:08 +0900 |
| parents | fadf02ce5925 |
| children | 905910e9fb04 |
| 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つとしてファイルシステムが挙げられる． | |
| 121 ファイルシステムはOSのプロセスやユーザーデータの管理などに必要不可欠であるため， | |
| 122 GearsOSにおいても実装をする必要があると考えられ， | |
| 123 当研究室では分散ファイルシステムやi-nodeを用いたファイルシステムの設計がされてきた\cite{cfile, directory}． | |
| 9 | 124 |
| 12 | 125 ファイルシステムには可変長の文字列を格納するファイルと， |
| 126 そのファイルにアクセスするための名前管理の機能がある． | |
| 127 ファイルの名前の一貫性は名前管理によって保証される． | |
| 128 しかし，ファイルに同時に書き込まれた際の一貫性を保証する機能を | |
| 129 ファイルシステムとしては持っておらず， | |
| 130 ファイルの書き込みを制御するロック機構をアプリケーションが持つことによって， | |
| 131 ファイルの一貫性を保証している．ファイルシステムによく似たものとしてDBが挙げられる． | |
| 132 DBは入力の属性名と型の組み合わせを複数持つレコードと， | |
| 133 特定の属性をキーとしたテーブルがある． | |
| 134 また，レコードのinsert，delete，updateの直列化可能性を保証する機能を持つ． | |
| 135 ファイルシステムとDBは格納するものの形式やそれにアクセスする方法， | |
| 136 直列化可能性を保証する手法が異なるが， | |
| 137 データをある形式で保持する仕組みであるという本質的な部分において違いはない． | |
| 138 よって，ファイルシステムとDBを同一のシステムとして実装することが可能であると考える． | |
| 9 | 139 |
| 12 | 140 データのレプリケーションやガベージコレクションの仕組みに必要である， |
| 141 RedBlackTreeのCopyの仕組みを実装した． | |
| 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 | |
| 23 | 280 \section{モジュール化の仕組みinterface} |
| 281 | |
| 282 Gears OSにはモジュール化の仕組みであるinterfaceという概念が存在する． | |
| 283 モジュール化とはJavaのクラスのように複数のメソッドや属性を1つの機能として | |
| 284 まとめて記述することである． | |
| 285 GearsOSではinterfaceによって，DataGearやCodeGearを複数まとめてモジュール化する． | |
| 286 interfaceは仕様と実装を分けて記述する． | |
| 287 例としてqueue interfaceの仕様記述部分をソースコード\ref{src:Queue.h}に示す． | |
| 288 | |
| 289 \lstinputlisting[label=src:Queue.h, caption=Queueのインターフェース]{src/Queue.h} | |
| 290 | |
| 291 interfaceの仕様はC言語の構造体定義の形で記述する． | |
| 292 2，3行目はDataGearを記述しており，DataGearは\texttt{union Data*}型で表現する． | |
| 293 ここにはinterfaceにおいて，CodeGearが使用するDataGearを列挙する． | |
| 294 5行目から10行目まではCodeGearの型を記述しており，\texttt{\_\_code}型で表現する． | |
| 295 ここに列挙したCodeGearはinterfaceのAPIとして機能する． | |
| 296 interfaceのAPIの呼び出し例をソースコード\ref{exinterface}に示す． | |
| 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 | |
| 306 4行目でgotoによってqueue interfaceのtake CodeGearに継続するよう記述している． | |
| 307 takeのinputDataGearにはodgCommitCPUWorker4 CodeGearを指定している． | |
| 308 ソースコード\ref{src:Queue.h}の仕様記述ではtakeにはqueue，data，nextがinputDataGearの型として指定されている． | |
| 309 しかし，実際に呼び出す際にはnextに当たるodgCommitCPUWorker4のみを渡している． | |
| 310 仕様記述の際に全てのCodeGearの第1引数(inputDataGear)に渡している\texttt{Impl* queue}は， | |
| 311 仕様から実装のCodeGearにgotoするために必要な記述である． | |
| 312 軽量継続において，CodeGearを跨いで状態を保持することはできない． | |
| 313 よって仕様から実装に遷移するためには，実装のCodeGearをinput DataGearとして渡す必要がある． | |
| 314 inputDataGearのnextはCodeGearの処理が終わった際に次にgotoするCodeGearを指定する． | |
| 315 よって，take CodeGearの処理が全て終了すると，次にodgCommitCPUWorker4へgotoする． | |
| 316 nextは\texttt{next(...)}と引数に\texttt{...}が渡される． | |
| 24 | 317 これは仕様を記述する時点では不定である次に遷移するCodeGearのinputDataGearを表現している． |
| 318 GearsOSでgotoする際は実際にはContextから必要な値を取り出す． | |
| 319 よって，\texttt{...}は必要な値をContextから取り出すことを意味している． | |
| 320 | |
| 321 次にinterfaceの実装似ついて説明する． | |
| 322 Queue interfaceの実装の一つであるSingleLinkedQueueをソースコード\ref{src:SingleLinkedQueue.cbc}に示す． | |
| 323 | |
| 324 \lstinputlisting[label=src:SingleLinkedQueue.cbc, caption=Queueのインターフェース]{src/SingleLinkedQueue.cbc} | |
| 23 | 325 |
| 326 | |
| 327 \section{GearsOSのRedBlackTree} | |
| 9 | 328 |
| 14 | 329 \chapter{GearsOSのファイルシステム} |
| 11 | 330 \section{DataGearManagerによる分散ファイルシステム} |
| 331 \section{i-nodeを用いたファイルシステム} | |
| 332 \section{非破壊RedBlackTreeによる構成} | |
| 15 | 333 |
| 334 ディスク上とメモリ上でデータの構造は，RedBlackTreeに統一する． | |
| 335 一般的に，ディスク上のデータ構造としてB-Treeが用いられることが多い． | |
| 336 なぜならば，HDDを用いる場合はブロックへのアクセス回数を減らしデータアクセスの時間を短くするために， | |
| 337 B-Treeのようなノードを複数持つことができる構造が効果的だからである． | |
| 338 その点ではRedBlackTreeはB-Treeに劣る． | |
| 339 しかしながら，SSDはランダムアクセスによってデータにアクセスするため， | |
| 340 RedBlackTreeでなくB-Treeを用いる利点は少ないと考える． | |
| 341 よって，ディスク上とメモリ上のデータ構造をRedBlackTreeに統一することが考えられる． | |
| 342 そうすることによって，ディスク上とメモリ上のデータのやりとりは単純なコピーで実装できる． | |
| 343 | |
| 11 | 344 \section{RedBlackTreeのトランザクション} |
| 9 | 345 |
| 346 トランザクションはDBの重要な機能の一つである． | |
| 347 データの競合を防ぎ信頼性を向上させ，DBとしても扱えるよう | |
| 348 トランザクションの仕組みを考える必要がある． | |
| 349 今回，ファイルシステムは全てRedBlackTreeで実装するため， | |
| 350 RedBlackTreeのノードに対するトランザクションを考える． | |
| 351 | |
| 352 トランザクションをwriteとreadに分けて考える． | |
| 353 writeする場合，トランザクションはRedBlackTreeのルートの置き換えと対応する． | |
| 354 writeするために，まずルートを生やし書き込みが終わった後ルートを置き換える． | |
| 355 そのため，書き込みの並列度はルートの数と一致する． | |
| 356 しかしながら，ルートの置き換えは競合的なので， | |
| 357 複数プロセスから同時に書き込みを行っても1つしか成功しない． | |
| 358 よって，単一のRedBlackTreeに複数の書き込みポイントを作り， | |
| 359 並行実行可能にする必要がある． | |
| 360 | |
| 361 % TODO: writeトランザクションの図を入れたい | |
| 362 | |
| 363 RedBlackTreeに複数の書き込みポイントを作るために， | |
| 364 キーごとのルートを作成する． | |
| 365 ノードはそれぞれがキーとRedBlackTreeを持つ状態になる． | |
| 366 writeする際は，そのキーのルートを置き換える． | |
| 367 それによって，RedBlackTreeは複数の書き込みポイントを持つことができ， | |
| 368 writeを並行実行することが可能となる． | |
| 369 | |
| 370 図\ref{fig:Transaction}にトランザクショナルなwrite操作を表す． | |
| 371 Aの木はファイルシステム全体を表すRedBlackTreeである． | |
| 372 ノードNのデータに対して書き込みすることを考えると， | |
| 373 キーがaであるBの木のルートからロックしCの木を作成して， | |
| 374 Bの木からCの木のルートに入れ替えることで書き込みを行う． | |
| 375 この書き込みを行っている際， | |
| 376 Aの木のノードはロックしないのでAの木のどのノードに対しても並行して書き込み可能となる． | |
| 377 | |
| 378 \begin{figure}[ht] | |
| 379 \begin{center} | |
| 12 | 380 \includegraphics[width=100mm]{fig/transaction.drawio.pdf} |
| 9 | 381 \end{center} |
| 382 \caption{トランザクショナルなwrite操作} | |
| 383 \label{fig:Transaction} | |
| 384 \end{figure} | |
| 385 | |
| 386 % TODO: read時常に最新の情報が取れないことを説明する図を入れたい | |
| 387 | |
| 388 readはデータに変更を加えないため，複数同時に同じノードを読み込むことが可能である． | |
| 389 しかし，常に最新の情報を読み込めるとは限らない． | |
| 390 最新の情報が欲しい場合は書き込みを一旦止めるような処理が必要になる． | |
| 391 | |
| 11 | 392 \section{ディスク上とメモリ上のデータ構造} |
| 9 | 393 |
| 11 | 394 |
| 395 ファイルシステムは全てRedBlackTreeで構成する． | |
| 396 それにより，プログラムの証明がより簡単になるからである． | |
| 397 また，ファイルシステムとDBはデータを保管するという本質的な役割は同じである． | |
| 398 よって，それらはまとめてRedBlackTreeで構成する． | |
| 399 | |
| 400 ファイルシステムとDBの違いとして，スキーマが挙げられる． | |
| 401 DBは事前にスキーマを定義し，それに沿ってデータを挿入，参照する． | |
| 402 対して，ファイルシステムにはスキーマに当たるものがなく， | |
| 403 データはファイルパスによって管理される． | |
| 404 スキーマを定義することによってデータは構造化され， | |
| 405 構造化されたデータは非構造化データと比較して， | |
| 406 インデックスを作成することが容易であり，データの検索性が向上する利点がある． | |
| 407 しかしながら，スキーマはDBの運用中に変更されることがあり， | |
| 408 スキーマを変更した以前へロールバックができない問題がある． | |
| 409 | |
| 410 ロールバックがスキーマの変更によって出来なくなることは信頼性に問題があると考えると， | |
| 411 スキーマを定義する必要のないスキーマレスなDBが必要になる． | |
| 412 ファイルシステムはスキーマレスなDBといえるので，ファイルシステムを構築しつつ | |
| 413 DBがスキーマによって実現していた機能を付け加えることを試みる． | |
| 414 | |
| 415 RedBlackTreeは実装によって，操作が破壊的なものとそうでないものがある． | |
| 416 今回用いるのは，非破壊的な実装のRedBlackTreeである． | |
| 417 図\ref{fig:TreeEdit}は非破壊的編集を行うRedBlackTreeを表している． | |
| 418 編集前の木構造の6のノードをAにアップデートすることを考える． | |
| 419 まず，ルートノードからアップデートしたいノード6までをコピーする． | |
| 420 その後，コピーしたもののノード6をAにアップデートする． | |
| 421 これにより，アップデート前のノード6を破壊することなくAにアップデートが可能である． | |
| 422 参照する時は，黒のルートノードから辿れば古い6が，赤のルートノードから辿れば新しいAが見える． | |
| 423 この仕組みは，データのバックアップやDBのロールバックに用いることが可能だと考える． | |
| 424 | |
| 425 \begin{figure}[ht] | |
| 426 \begin{center} | |
| 12 | 427 \includegraphics[width=160mm]{fig/nonDestroyTreeEdit.pdf} |
| 11 | 428 \end{center} |
| 429 \caption{非破壊的なTree編集} | |
| 430 \label{fig:TreeEdit} | |
| 431 \end{figure} | |
| 432 | |
| 433 | |
| 14 | 434 \chapter{GearsFileSystemにおけるGCとレプリケーション} |
| 21 | 435 |
| 14 | 436 \section{ファイルシステムの信頼性に関する機能} |
| 437 | |
| 438 ファイルシステムはデータを保持することを基本的な機能としている． | |
| 439 信頼性に関する機能など，その他の機能は追加機能として実装する． | |
| 440 ファイルシステムやDBにおける信頼性に関する追加機能として， | |
| 441 システムの電源断時にデータが残るpersistency， | |
| 442 データを書き込めたかどうかを判定するatomic write， | |
| 443 1つのノードが失われた際にデータを保護する多重性， | |
| 444 複数のコピーを調停するコミット機構などが挙げられる． | |
| 15 | 445 |
| 14 | 446 現状のGearsOSには分散ファイルシステムの通信機能やUnix Likeな |
| 447 インターフェースを持つi-nodeファイルシステムの基本機能は存在するものの， | |
| 448 多重性やメモリ管理などの信頼性を確保するための機能が存在しない． | |
| 449 データの多重度を確保するための一般的な手法として， | |
| 450 データのバックアップやシステム自体のレプリケーションをすることが挙げられる． | |
| 451 メモリ管理の機能としてはガーベージコレクションが挙げられる． | |
| 15 | 452 ガベージコレクションは通常プログラム言語のレイヤで行われる． |
| 453 これらの機能を実装することでファイルシステムの信頼性を高めたい． | |
| 14 | 454 |
| 16 | 455 \section{メモリの管理手法} |
| 14 | 456 |
| 15 | 457 GCのアルゴリズムは大きく分けてMark \& Sweep GC，Reference counting GC， |
| 458 Copying GCの3つの種類が存在する． | |
| 20 | 459 Mark \& Sweep GCはマークフェーズとスイープフェーズからなる。 |
| 460 マークフェーズはヒープ上でルートから参照することができるオブジェクト全てにマークをし， | |
| 461 その後、スイープフェーズでマークされていないオブジェクトを | |
| 462 使用されていないオブジェクトのリストであるフリーリストに接続することでGCを行う． | |
| 463 Reference counting GCはオブジェクトの被参照数を表すReference counterを用いるGCである． | |
| 464 新たに参照される度にReference counterをインクリメントし， | |
| 465 参照が外れる度にデクリメントする． | |
| 466 そのようにして，カウンターが0になった時点でフリーリストに接続することでGCを行う． | |
| 15 | 467 CopyingGCはメモリ上のヒープ領域をFrom領域とTo領域に分割し， |
| 20 | 468 ルートから参照できるオブジェクトをFrom領域からTo領域にコピーする． |
| 469 From領域を参照していたポインタはTo領域のオブジェクトを参照するように置き換える． | |
| 470 その後，From領域とTo領域を入れ替えることでGCを行う． | |
| 15 | 471 |
| 20 | 472 一般的にこれらのGC手法は複数を組み合わせて用いられる． |
| 473 世代別GCではオブジェクトの生存期間によって適用するGCアルゴリズムを使い分ける． | |
| 474 アロケートされてすぐのオブジェクトを新世代オブジェクト， | |
| 475 任意の回数のGCを生き残ったオブジェクトを旧世代オブジェクトとし， | |
| 476 それぞれの特性に合ったGCアルゴリズムを適用する． | |
| 477 すぐに回収されることが多い新世代オブジェクトはCopying GCで網羅的にGCをし， | |
| 478 長く生き残る旧世代オブジェクトはMark \& Sweep GCで適宜回収するなどが例として挙げられる． | |
| 479 このように複数のGCアルゴリズムを組み合わせることで， | |
| 480 それぞれのアルゴリズムの利点を享受できる． | |
| 481 | |
| 482 また，メモリ管理手法としてRust言語の所有権がある． | |
| 483 所有権ではメモリを所有する変数がスコープを抜ける時に， | |
| 484 同時にメモリも解放する． | |
| 485 そのためRustではGCの仕組みを必要とせず， | |
| 486 より高速にメモリの管理を行うことができる． | |
| 15 | 487 |
| 16 | 488 \section{GearsFileSystemのGC} |
| 489 | |
| 20 | 490 GearsFileSystemのGCはCopying GCを基本的なアルゴリズムとする． |
| 21 | 491 他のGC手法と比較して参照できるオブジェクトをコピーするだけであるため， |
| 492 実装が簡単で，より高いスループットが期待できる． | |
| 493 Mark \& Sweep GCやReference counting GCの場合は， | |
| 494 GCを複数フェーズで実装したり，カウンターの扱いについて考える必要がある． | |
| 495 また，同様の構造をコピーするのみで実装することによって， | |
| 496 データの透過性の確保がしやすい． | |
| 497 ファイルやディレクトリを表現するRedBlackTreeは全てのデータの参照を持つ． | |
| 498 そのため，オブジェクトルートからオブジェクトを辿ってコピーを行うCopying GCとの相性が良い． | |
| 15 | 499 |
| 21 | 500 一般的なCopying GCではFrom領域上のオブジェクトをTo領域にコピーする形で実装される． |
| 501 一方，GearsFileSystemではファイルやディレクトリの基本構造であるRedBlackTreeをコピーする． | |
| 502 ファイルやディレクトリの操作を行うFromのRedBlackTreeから， | |
| 503 ルートから辿れるノードのみをToのRedBlackTreeとしてコピーする． | |
| 504 それにより，辿れなかったノード，つまり参照されていないノードはコピーされず， | |
| 505 不要なオブジェクトが回収された状態となる． | |
| 506 | |
| 507 \begin{figure}[ht] | |
| 508 \begin{center} | |
| 509 \includegraphics[width=160mm]{fig/rbtree_gc.png} | |
| 510 \end{center} | |
| 511 \caption{RedBlackTReeのCopyによるGC} | |
| 512 \label{fig:TreeCopyGC} | |
| 513 \end{figure} | |
| 514 | |
| 515 DBの重要な機能の一つにロールバックがある． | |
| 516 RDBのロールバックは， | |
| 517 コミットするまではトランザクションの開始時点に戻ることができる機能を持つ． | |
| 518 コミットが完了するとそれ以前の状態に戻すことはできないが， | |
| 519 データのバックアップをとっておくことで復元を行う． | |
| 520 | |
| 521 今回は，RedBlackTreeのルートノードがデータのバージョンの役割を果たしていることを利用し， | |
| 522 データの復元が行える仕組みを構築することを考える． | |
| 523 非破壊的なTree編集はアップデートのたびに，ルートノードを増やす． | |
| 524 つまり，ルートノードはアップデートのログと言えその時点のデータのバージョンを表していると考えることができる． | |
| 525 よって，ロールバックを行いたい場合は参照を過去のルートノードに切り替える． | |
| 526 | |
| 527 ルートノードはデータのアップデート時に増えるため， | |
| 528 データが際限なく増加していく問題がある． | |
| 529 この問題はCopyingGCを行うことによって解決する． | |
| 530 まず，RedBlackTreeを丸ごとコピーして最新のルートを残して他のルートは削除する． | |
| 531 その後，コピーしたものはバックアップないしログとしてディスクに書き込む． | |
| 532 そうすることで，データの増加によるリソースの枯渇を防ぎ， | |
| 533 かつデータのログ付きバックアップを作成することで信頼性の向上が期待できる． | |
| 14 | 534 |
| 535 | |
| 536 \section{GearsFileSystemのレプリケーション} | |
| 11 | 537 |
| 22 | 538 \begin{figure}[ht] |
| 539 \begin{center} | |
| 540 \includegraphics[width=160mm]{fig/rbtree_replica.png} | |
| 541 \end{center} | |
| 542 \caption{Copyのアルゴリズム} | |
| 543 \label{fig:CopyAlgo} | |
| 544 \end{figure} | |
| 21 | 545 |
| 11 | 546 \chapter{CopyRedBlackTreeの実装} |
| 14 | 547 |
| 548 データのバックアップやレプリケーション，GCの機能を実装するためには， | |
| 549 データのコピーをする必要がある． | |
| 550 GearsOSのファイルシステムにおいて，データは全てRedBlackTreeに格納される． | |
| 551 しかしながら，現状のRedBlackTreeには木をコピーする機能が無い． | |
| 552 よって，RedBlackTreeに木のコピー機能を実装する必要がある． | |
| 553 | |
| 19 | 554 \lstinputlisting[label=src:CopyRedBlackTree.cbc, caption=CopyRedBlackTreeの実装]{src/CopyRedBlackTree.cbc} |
| 555 | |
| 11 | 556 \section{コピーのアルゴリズム} |
| 19 | 557 |
| 558 \lstinputlisting[label=src:CopyRedBlackTree.cbc, caption=CopyRedBlackTreeのアルゴリズム]{src/copyAlgorithm.cbc} | |
| 559 | |
| 560 \begin{figure}[ht] | |
| 561 \begin{center} | |
| 562 \includegraphics[width=160mm]{fig/copy_algo.png} | |
| 563 \end{center} | |
| 564 \caption{Copyのアルゴリズム} | |
| 565 \label{fig:CopyAlgo} | |
| 566 \end{figure} | |
| 567 | |
| 11 | 568 \section{Stackの使用に関して} |
| 569 \section{証明のしやすさについて} | |
| 570 | |
| 571 | |
| 572 | |
| 573 % TODO: バックアップのフローを図にしたい | |
| 574 | |
| 575 | |
| 576 \chapter{まとめと今後の課題} | |
| 577 | |
| 578 本論文ではGearsOSのファイルシステムとDBの設計について説明した． | |
| 579 今後，実装を行いながら設計と動作の確認，計測を行い， | |
| 580 設計の意図が反映されていることやプログラムの検証ができることを確認する必要がある． | |
| 581 | |
| 582 また，今後の課題や議題として次のようなものが挙げられる． | |
| 583 | |
| 584 \section{ファイルシステムにおけるスキーマ} | |
| 9 | 585 |
| 586 従来のRDBのようなスキーマが存在すると， | |
| 587 個別にバックアップなどを取らない限り | |
| 588 スキーマの変更以前にロールバックすることができない． | |
| 589 しかしながら，実際運用する上でスキーマを変更することは多々ある． | |
| 590 これは，データの信頼性を低下させると考える． | |
| 591 また，DB上のデータ構造とプログラム上で扱うデータ構造に差が生まれる | |
| 592 インピーダンスミスマッチが発生し，DBのデータをプログラムが扱う際に | |
| 593 その差を埋めるような変換を必要とする場合が生まれる． | |
| 594 一方で，スキーマがあることによってデータに対して高度な操作を行うことができ， | |
| 595 また，インデックスを容易に作成することができるといったメリットがある． | |
| 596 よって，スキーマフルなDBとスキーマレスなDBはそれぞれメリットデメリットがあり， | |
| 597 状況によって使い分けるのが良いと考える． | |
| 598 | |
| 599 今回は，非構造化データ内であれば構造化データを扱うことが可能であることと， | |
| 600 信頼性を保証したいという点から， | |
| 601 スキーマレスなDBとしてのファイルシステムを考える． | |
| 602 しかしながら，トランザクションの仕組みを作る上でRedBlackTreeに対し， | |
| 603 キーを設定することから完全なスキーマレスとは言えない構成となる． | |
| 604 | |
| 605 GearsOSのデータは全てDataGearで表される． | |
| 606 よって，GearsOSにおけるファイルシステムはDataGearの集合となる． | |
| 607 スキーマレスとはキーがない状態のことといえるが， | |
| 608 DataGearはキーが設定されていないため，その集合自体にスキーマは無い． | |
| 609 そのことから，GearsOSにおけるスキーマとはDataGear上のキーの構成であることがわかる． | |
| 610 なお，今回のRedBlackTreeによる構成の場合，キーはRedBlackTreeを指す． | |
| 611 DataGearはKernelのContextからプロセスのContextを経由して全て繋がっている． | |
| 612 よって，KernelのContext上にキーを用いたDataGearの参照を書き込む． | |
| 613 | |
| 11 | 614 \section{RedBlackTreeによる権限の表現} |
| 9 | 615 |
| 616 ファイルの権限はファイルシステムの重要な機能の一つであるため実装する必要がある． | |
| 617 今回のRedBlackTreeによる構成の場合，木のルートの所持者を設定することが | |
| 618 ファイルに対して権限を設定することにあたる． | |
| 619 ルートに対してアクセスする権限がなければ， | |
| 620 読み書きができないといった実装になると考える． | |
| 621 \section{データクエリ言語} | |
| 622 | |
| 623 ユーザーやアプリケーションがDBのデータにアクセスするための言語設計を | |
| 624 する必要がある． | |
| 625 RedBlackTreeのキーを用いたインデックスに対応し， | |
| 626 従来のSQLと比較してより柔軟なクエリを実行できることを目指したい． | |
| 627 | |
| 628 \section{ログなどの時系列データの保存} | |
| 629 | |
| 630 時系列データは通常のデータと違った保存の方法を考えることができる． | |
| 631 時系列に並んでいることを生かしたデータの保存方式や， | |
| 632 時間経過に伴うデータの重要性の変化を考慮に入れたデータ圧縮の方法をとることで， | |
| 633 より効率的な保存が可能だと考える． | |
| 634 | |
| 635 \section{スタンドアロンなDB} | |
| 636 | |
| 637 MySQLやPostgreSQLなどはOSの機能としてではなく， | |
| 638 それ自体が一つのアプリケーションとして自立的に動作している． | |
| 639 自立的に動作するのは，データのポータビリティを向上させるためである． | |
| 640 スタンドアロンなDBの形にするか， | |
| 641 その他の方法でポータビリティを向上させる手法を考えたい． | |
|
2
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
642 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
643 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
644 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
645 % %謝辞 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
646 \input{chapter/thanks.tex} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
647 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
648 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
649 %参考文献 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
650 \nocite{*} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
651 \bibliography{reference} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
652 \bibliographystyle{junsrt} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
653 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
654 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
655 %発表履歴 |
| 20 | 656 \input{chapter/history.tex} |
| 657 \addcontentsline{toc}{chapter}{研究関連論文業績} | |
|
2
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
658 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
659 %付録 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
660 \addcontentsline{toc}{chapter}{付録} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
661 \appendix |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
662 \input{chapter/appendix.tex} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
663 \end{document} |