Mercurial > hg > Papers > 2024 > matac-master
annotate Paper/master_paper.tex @ 36:5294b155ad72
fix: chapter1 last
| author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 19 Jan 2024 18:09:30 +0900 |
| parents | 02f0474a58c4 |
| children | 727091139c84 |
| 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を指定している． |
| 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 | |
| 26 | 321 次にInterfaceの実装について説明する． |
| 322 Queue Interfaceの実装の1つであるSingleLinkedQueueをソースコード\ref{src:SingleLinkedQueue.cbc}に示す． | |
| 24 | 323 |
| 324 \lstinputlisting[label=src:SingleLinkedQueue.cbc, caption=Queueのインターフェース]{src/SingleLinkedQueue.cbc} | |
| 23 | 325 |
| 26 | 326 3行目の\texttt{\#impl as}はInterfaceの実装を記述する際に指定する． |
| 327 implの直後に実装したいInterfaceの仕様を指定し， | |
| 328 asの後ろには実装の型名を記述する． | |
| 329 であるから，\texttt{\#impl "Queue.h" as "SingleLinkedQueue.h"}は仕様Queueの実装を | |
| 330 SingleLinkedQueueとして定義することになる． | |
| 331 7行目の\texttt{createSingleLinkedQueue}はSingleLinkedQueueのコンストラクタを定義しており， | |
| 332 DataGearのアロケートやCodeGearを保持するメソッドの初期化を行っている． | |
| 333 8，9行目ではnewでアロケートを行っている． | |
| 334 アロケートのようなメタレベルの処理はノーマルレベルには記述されない． | |
| 335 そのためこのnewはC言語のnewとは違うGearsOS独自の記述であり， | |
| 336 実際にはメタレベルにアロケートを行う処理を挿入している． | |
| 337 10〜16行目ではSingleLinkedQueueで使用するCodeGearとDataGearを | |
| 28 | 338 queueのメソッドとして初期化している． |
| 26 | 339 CodeGearはQueueの仕様で記述したCodeGearと一致している． |
| 340 \texttt{C\_}で始まる記述にはenum CodeにおけるCodeGearの整数を格納している． | |
| 341 CodeGearはenum Codeで整数と対応付けられており， | |
| 342 この整数を元にCodeGearが参照される． | |
| 343 20行目以降では\texttt{putSingleLinkedQueue}や\texttt{takeSingleLinkedQueue} | |
| 344 のように，仕様で記述されたCodeGearを実装している． | |
| 345 | |
| 23 | 346 |
| 347 \section{GearsOSのRedBlackTree} | |
| 9 | 348 |
| 28 | 349 Red-black tree(赤黒木)は二分探索木の一種で， |
| 350 ノードに赤か黒の色を付けて色に関するいくつかの条件をもつデータ構造である． | |
| 351 木に対する探索，挿入，削除操作における最悪計算量がO(log n)であるため， | |
| 352 赤黒木は大規模なデータを扱う際に効率的なデータ構造となる． | |
| 27 | 353 |
| 28 | 354 GearsOSのRedBlackTreeはGearsFileSystemで用いられる重要な構造の1つであり， |
| 355 ディレクトリ構造を表現するために使用されている． | |
| 356 GearsOSにおけるTreeの仕様記述をソースコード\ref{src:Tree.h}に， | |
| 357 RedBlackTreeの実装の記述の一部をソースコード\ref{src:RedBlackTreeImpl.cbc}に示す． | |
| 358 | |
| 27 | 359 \lstinputlisting[label=src:Tree.h, caption=Treeの仕様]{src/Tree.h} |
| 28 | 360 \lstinputlisting[label=src:RedBlackTreeImpl.cbc, caption=RedBlackTreeの実装]{src/RedBlackTreeImpl.cbc} |
| 27 | 361 |
| 28 | 362 ソースコード\ref{src:Tree.h}より，Treeはtree DataGearと |
| 363 put，get，remove，nextの4つのCodeGearを持っていることがわかる． | |
| 364 ソースコード\ref{src:RedBlackTreeImpl.cbc}の4行目から， | |
| 365 RedBlackTreeはTreeの仕様の実装であることがわかり， | |
| 366 13〜16行目で仕様に対応するCodeGearを初期化している． | |
| 27 | 367 |
| 29 | 368 \chapter{GearsFileSystem} |
| 369 | |
| 370 ファイルシステムはOSにおいてユーザーやアプリケーションが使用するファイルや | |
| 371 プロセスの管理に用いられる重要なシステムである． | |
| 372 そのため，GearsOSにおいてもi-nodeを用いたディレクトリシステムや， | |
| 373 DataGearManagerによる分散ファイルシステムの仕組みをもつ， | |
| 374 GearsFileSystemの取り組みがいくつかされてきた． | |
| 375 | |
| 376 \section{i-nodeを用いたディレクトリシステム} | |
| 377 | |
| 378 GearsFileSystemにはi-nodeを用いたディレクトリの仕組みが存在する\cite{directory}． | |
| 379 i-nodeは主にUnix系のファイルシステムで用いられる， | |
| 380 ファイルの属性情報が書かれたデータである． | |
| 381 inodeにおけるファイルの属性情報は表\ref{table:inode}のようなものがある． | |
| 382 またinodeは識別番号としてinode numberを持つ． | |
| 383 inode numberは一つのファイルシステム内で一意の番号であり，\emph{ls -i}コマンドで確認可能である． | |
| 384 inodeはファイルシステム始動時にinode領域をディスク上に確保する． | |
| 385 そのためinode numberには上限があり，それに伴いファイルシステム上で扱えるファイル数の上限も決まる． | |
| 386 inode numberの最大値は\emph{df -i}コマンドで確認可能である． | |
| 387 | |
| 388 \begin{table}[htpb] | |
| 389 \begin{center} | |
| 390 \small | |
| 391 \begin{tabular}[htpb]{|c||c|} | |
| 392 \hline | |
| 393 File Types & directoryやregular fileなど，ファイルの種類 \\ | |
| 394 \hline | |
| 395 Permissions & read write executeの実行可否\\ | |
| 396 \hline | |
| 397 UID & ファイル所有者のID \\ | |
| 398 \hline | |
| 399 GID & ファイル所有グループのID \\ | |
| 400 \hline | |
| 401 File Size & ファイルのサイズ \\ | |
| 402 \hline | |
| 403 Time Stamps & ファイル作成，編集日時 \\ | |
| 404 \hline | |
| 405 Number of link & ハードリンクの数 \\ | |
| 406 \hline | |
| 407 Location on hard disk & データのアドレス\\ | |
| 408 \hline | |
| 409 \end{tabular} | |
| 410 \caption{inodeでのファイル属性情報} | |
| 411 \label{table:inode} | |
| 412 \end{center} | |
| 413 \end{table} | |
| 414 | |
| 415 GearsFileSystemではi-nodeをi-node numberがkey， | |
| 416 i-nodeでのファイル属性情報をvalueであるノードを持つinode treeをRedBlackTreeで表現している． | |
| 417 また，ファイル名からi-node numberを検索するためのindex treeも同じRedBlackTreeで表現している． | |
| 31 | 418 データ構造にRedBlackTreeのみを用いているのは， |
| 29 | 419 ls，cd，mkdirといった，ディレクトリ操作を行うためのUnix Likeなユーザーインターフェースをもつ． |
| 31 | 420 図\ref{fig:GearsDir}にGears Directoryの処理の例を示す． |
| 421 | |
| 422 \begin{figure}[ht] | |
| 423 \begin{center} | |
| 424 \includegraphics[width=160mm]{fig/gears_dir.png} | |
| 425 \end{center} | |
| 426 \caption{i-nodeを用いたディレクトリシステムの処理の流れ} | |
| 427 \label{fig:GearsDir} | |
| 428 \end{figure} | |
| 29 | 429 |
| 32 | 430 lsコマンドはディレクトリ内のファイルやファイル自体の情報を出力するコマンドである． |
| 431 \texttt{ls hoge.txt}を実行すると\textcircled{\scriptsize 1}index treeを参照し， | |
| 432 ファイル名hoge.txtからi-node numberの2を取得する． | |
| 433 次に，\textcircled{\scriptsize 2}i-node treeを参照し， | |
| 434 i-node numberを元にファイルの属性を取得し，lsコマンドの場合はそれを出力する． | |
| 435 | |
| 11 | 436 \section{DataGearManagerによる分散ファイルシステム} |
| 437 \section{非破壊RedBlackTreeによる構成} | |
| 15 | 438 |
| 439 ディスク上とメモリ上でデータの構造は，RedBlackTreeに統一する． | |
| 440 一般的に，ディスク上のデータ構造としてB-Treeが用いられることが多い． | |
| 441 なぜならば，HDDを用いる場合はブロックへのアクセス回数を減らしデータアクセスの時間を短くするために， | |
| 442 B-Treeのようなノードを複数持つことができる構造が効果的だからである． | |
| 443 その点ではRedBlackTreeはB-Treeに劣る． | |
| 444 しかしながら，SSDはランダムアクセスによってデータにアクセスするため， | |
| 445 RedBlackTreeでなくB-Treeを用いる利点は少ないと考える． | |
| 446 よって，ディスク上とメモリ上のデータ構造をRedBlackTreeに統一することが考えられる． | |
| 447 そうすることによって，ディスク上とメモリ上のデータのやりとりは単純なコピーで実装できる． | |
| 448 | |
| 11 | 449 \section{RedBlackTreeのトランザクション} |
| 9 | 450 |
| 451 トランザクションはDBの重要な機能の一つである． | |
| 452 データの競合を防ぎ信頼性を向上させ，DBとしても扱えるよう | |
| 453 トランザクションの仕組みを考える必要がある． | |
| 454 今回，ファイルシステムは全てRedBlackTreeで実装するため， | |
| 455 RedBlackTreeのノードに対するトランザクションを考える． | |
| 456 | |
| 457 トランザクションをwriteとreadに分けて考える． | |
| 458 writeする場合，トランザクションはRedBlackTreeのルートの置き換えと対応する． | |
| 459 writeするために，まずルートを生やし書き込みが終わった後ルートを置き換える． | |
| 460 そのため，書き込みの並列度はルートの数と一致する． | |
| 461 しかしながら，ルートの置き換えは競合的なので， | |
| 462 複数プロセスから同時に書き込みを行っても1つしか成功しない． | |
| 463 よって，単一のRedBlackTreeに複数の書き込みポイントを作り， | |
| 464 並行実行可能にする必要がある． | |
| 465 | |
| 466 % TODO: writeトランザクションの図を入れたい | |
| 467 | |
| 468 RedBlackTreeに複数の書き込みポイントを作るために， | |
| 469 キーごとのルートを作成する． | |
| 470 ノードはそれぞれがキーとRedBlackTreeを持つ状態になる． | |
| 471 writeする際は，そのキーのルートを置き換える． | |
| 472 それによって，RedBlackTreeは複数の書き込みポイントを持つことができ， | |
| 473 writeを並行実行することが可能となる． | |
| 474 | |
| 475 図\ref{fig:Transaction}にトランザクショナルなwrite操作を表す． | |
| 476 Aの木はファイルシステム全体を表すRedBlackTreeである． | |
| 477 ノードNのデータに対して書き込みすることを考えると， | |
| 478 キーがaであるBの木のルートからロックしCの木を作成して， | |
| 479 Bの木からCの木のルートに入れ替えることで書き込みを行う． | |
| 480 この書き込みを行っている際， | |
| 481 Aの木のノードはロックしないのでAの木のどのノードに対しても並行して書き込み可能となる． | |
| 482 | |
| 483 \begin{figure}[ht] | |
| 484 \begin{center} | |
| 12 | 485 \includegraphics[width=100mm]{fig/transaction.drawio.pdf} |
| 9 | 486 \end{center} |
| 487 \caption{トランザクショナルなwrite操作} | |
| 488 \label{fig:Transaction} | |
| 489 \end{figure} | |
| 490 | |
| 491 % TODO: read時常に最新の情報が取れないことを説明する図を入れたい | |
| 492 | |
| 493 readはデータに変更を加えないため，複数同時に同じノードを読み込むことが可能である． | |
| 494 しかし，常に最新の情報を読み込めるとは限らない． | |
| 495 最新の情報が欲しい場合は書き込みを一旦止めるような処理が必要になる． | |
| 496 | |
| 11 | 497 \section{ディスク上とメモリ上のデータ構造} |
| 9 | 498 |
| 11 | 499 |
| 500 ファイルシステムは全てRedBlackTreeで構成する． | |
| 501 それにより，プログラムの証明がより簡単になるからである． | |
| 502 また，ファイルシステムとDBはデータを保管するという本質的な役割は同じである． | |
| 503 よって，それらはまとめてRedBlackTreeで構成する． | |
| 504 | |
| 505 ファイルシステムとDBの違いとして，スキーマが挙げられる． | |
| 506 DBは事前にスキーマを定義し，それに沿ってデータを挿入，参照する． | |
| 507 対して，ファイルシステムにはスキーマに当たるものがなく， | |
| 508 データはファイルパスによって管理される． | |
| 509 スキーマを定義することによってデータは構造化され， | |
| 510 構造化されたデータは非構造化データと比較して， | |
| 511 インデックスを作成することが容易であり，データの検索性が向上する利点がある． | |
| 512 しかしながら，スキーマはDBの運用中に変更されることがあり， | |
| 513 スキーマを変更した以前へロールバックができない問題がある． | |
| 514 | |
| 515 ロールバックがスキーマの変更によって出来なくなることは信頼性に問題があると考えると， | |
| 516 スキーマを定義する必要のないスキーマレスなDBが必要になる． | |
| 517 ファイルシステムはスキーマレスなDBといえるので，ファイルシステムを構築しつつ | |
| 518 DBがスキーマによって実現していた機能を付け加えることを試みる． | |
| 519 | |
| 520 RedBlackTreeは実装によって，操作が破壊的なものとそうでないものがある． | |
| 521 今回用いるのは，非破壊的な実装のRedBlackTreeである． | |
| 522 図\ref{fig:TreeEdit}は非破壊的編集を行うRedBlackTreeを表している． | |
| 523 編集前の木構造の6のノードをAにアップデートすることを考える． | |
| 524 まず，ルートノードからアップデートしたいノード6までをコピーする． | |
| 525 その後，コピーしたもののノード6をAにアップデートする． | |
| 526 これにより，アップデート前のノード6を破壊することなくAにアップデートが可能である． | |
| 527 参照する時は，黒のルートノードから辿れば古い6が，赤のルートノードから辿れば新しいAが見える． | |
| 528 この仕組みは，データのバックアップやDBのロールバックに用いることが可能だと考える． | |
| 529 | |
| 530 \begin{figure}[ht] | |
| 531 \begin{center} | |
| 12 | 532 \includegraphics[width=160mm]{fig/nonDestroyTreeEdit.pdf} |
| 11 | 533 \end{center} |
| 534 \caption{非破壊的なTree編集} | |
| 535 \label{fig:TreeEdit} | |
| 536 \end{figure} | |
| 537 | |
| 538 | |
| 14 | 539 \chapter{GearsFileSystemにおけるGCとレプリケーション} |
| 21 | 540 |
| 14 | 541 \section{ファイルシステムの信頼性に関する機能} |
| 542 | |
| 543 ファイルシステムはデータを保持することを基本的な機能としている． | |
| 544 信頼性に関する機能など，その他の機能は追加機能として実装する． | |
| 545 ファイルシステムやDBにおける信頼性に関する追加機能として， | |
| 546 システムの電源断時にデータが残るpersistency， | |
| 547 データを書き込めたかどうかを判定するatomic write， | |
| 548 1つのノードが失われた際にデータを保護する多重性， | |
| 549 複数のコピーを調停するコミット機構などが挙げられる． | |
| 15 | 550 |
| 14 | 551 現状のGearsOSには分散ファイルシステムの通信機能やUnix Likeな |
| 552 インターフェースを持つi-nodeファイルシステムの基本機能は存在するものの， | |
| 553 多重性やメモリ管理などの信頼性を確保するための機能が存在しない． | |
| 554 データの多重度を確保するための一般的な手法として， | |
| 555 データのバックアップやシステム自体のレプリケーションをすることが挙げられる． | |
| 556 メモリ管理の機能としてはガーベージコレクションが挙げられる． | |
| 15 | 557 ガベージコレクションは通常プログラム言語のレイヤで行われる． |
| 558 これらの機能を実装することでファイルシステムの信頼性を高めたい． | |
| 14 | 559 |
| 16 | 560 \section{メモリの管理手法} |
| 14 | 561 |
| 15 | 562 GCのアルゴリズムは大きく分けてMark \& Sweep GC，Reference counting GC， |
| 563 Copying GCの3つの種類が存在する． | |
| 20 | 564 Mark \& Sweep GCはマークフェーズとスイープフェーズからなる。 |
| 565 マークフェーズはヒープ上でルートから参照することができるオブジェクト全てにマークをし， | |
| 566 その後、スイープフェーズでマークされていないオブジェクトを | |
| 567 使用されていないオブジェクトのリストであるフリーリストに接続することでGCを行う． | |
| 568 Reference counting GCはオブジェクトの被参照数を表すReference counterを用いるGCである． | |
| 569 新たに参照される度にReference counterをインクリメントし， | |
| 570 参照が外れる度にデクリメントする． | |
| 571 そのようにして，カウンターが0になった時点でフリーリストに接続することでGCを行う． | |
| 15 | 572 CopyingGCはメモリ上のヒープ領域をFrom領域とTo領域に分割し， |
| 20 | 573 ルートから参照できるオブジェクトをFrom領域からTo領域にコピーする． |
| 574 From領域を参照していたポインタはTo領域のオブジェクトを参照するように置き換える． | |
| 575 その後，From領域とTo領域を入れ替えることでGCを行う． | |
| 15 | 576 |
| 20 | 577 一般的にこれらのGC手法は複数を組み合わせて用いられる． |
| 578 世代別GCではオブジェクトの生存期間によって適用するGCアルゴリズムを使い分ける． | |
| 579 アロケートされてすぐのオブジェクトを新世代オブジェクト， | |
| 580 任意の回数のGCを生き残ったオブジェクトを旧世代オブジェクトとし， | |
| 581 それぞれの特性に合ったGCアルゴリズムを適用する． | |
| 582 すぐに回収されることが多い新世代オブジェクトはCopying GCで網羅的にGCをし， | |
| 583 長く生き残る旧世代オブジェクトはMark \& Sweep GCで適宜回収するなどが例として挙げられる． | |
| 584 このように複数のGCアルゴリズムを組み合わせることで， | |
| 585 それぞれのアルゴリズムの利点を享受できる． | |
| 586 | |
| 587 また，メモリ管理手法としてRust言語の所有権がある． | |
| 588 所有権ではメモリを所有する変数がスコープを抜ける時に， | |
| 589 同時にメモリも解放する． | |
| 590 そのためRustではGCの仕組みを必要とせず， | |
| 591 より高速にメモリの管理を行うことができる． | |
| 15 | 592 |
| 16 | 593 \section{GearsFileSystemのGC} |
| 594 | |
| 20 | 595 GearsFileSystemのGCはCopying GCを基本的なアルゴリズムとする． |
| 21 | 596 他のGC手法と比較して参照できるオブジェクトをコピーするだけであるため， |
| 597 実装が簡単で，より高いスループットが期待できる． | |
| 598 Mark \& Sweep GCやReference counting GCの場合は， | |
| 599 GCを複数フェーズで実装したり，カウンターの扱いについて考える必要がある． | |
| 600 また，同様の構造をコピーするのみで実装することによって， | |
| 601 データの透過性の確保がしやすい． | |
| 602 ファイルやディレクトリを表現するRedBlackTreeは全てのデータの参照を持つ． | |
| 603 そのため，オブジェクトルートからオブジェクトを辿ってコピーを行うCopying GCとの相性が良い． | |
| 15 | 604 |
| 21 | 605 一般的なCopying GCではFrom領域上のオブジェクトをTo領域にコピーする形で実装される． |
| 606 一方，GearsFileSystemではファイルやディレクトリの基本構造であるRedBlackTreeをコピーする． | |
| 607 ファイルやディレクトリの操作を行うFromのRedBlackTreeから， | |
| 608 ルートから辿れるノードのみをToのRedBlackTreeとしてコピーする． | |
| 609 それにより，辿れなかったノード，つまり参照されていないノードはコピーされず， | |
| 610 不要なオブジェクトが回収された状態となる． | |
| 611 | |
| 612 \begin{figure}[ht] | |
| 613 \begin{center} | |
| 614 \includegraphics[width=160mm]{fig/rbtree_gc.png} | |
| 615 \end{center} | |
| 616 \caption{RedBlackTReeのCopyによるGC} | |
| 617 \label{fig:TreeCopyGC} | |
| 618 \end{figure} | |
| 619 | |
| 620 DBの重要な機能の一つにロールバックがある． | |
| 621 RDBのロールバックは， | |
| 622 コミットするまではトランザクションの開始時点に戻ることができる機能を持つ． | |
| 623 コミットが完了するとそれ以前の状態に戻すことはできないが， | |
| 624 データのバックアップをとっておくことで復元を行う． | |
| 625 | |
| 626 今回は，RedBlackTreeのルートノードがデータのバージョンの役割を果たしていることを利用し， | |
| 627 データの復元が行える仕組みを構築することを考える． | |
| 628 非破壊的なTree編集はアップデートのたびに，ルートノードを増やす． | |
| 629 つまり，ルートノードはアップデートのログと言えその時点のデータのバージョンを表していると考えることができる． | |
| 630 よって，ロールバックを行いたい場合は参照を過去のルートノードに切り替える． | |
| 631 | |
| 632 ルートノードはデータのアップデート時に増えるため， | |
| 633 データが際限なく増加していく問題がある． | |
| 634 この問題はCopyingGCを行うことによって解決する． | |
| 635 まず，RedBlackTreeを丸ごとコピーして最新のルートを残して他のルートは削除する． | |
| 636 その後，コピーしたものはバックアップないしログとしてディスクに書き込む． | |
| 637 そうすることで，データの増加によるリソースの枯渇を防ぎ， | |
| 638 かつデータのログ付きバックアップを作成することで信頼性の向上が期待できる． | |
| 14 | 639 |
| 640 | |
| 641 \section{GearsFileSystemのレプリケーション} | |
| 11 | 642 |
| 22 | 643 \begin{figure}[ht] |
| 644 \begin{center} | |
| 645 \includegraphics[width=160mm]{fig/rbtree_replica.png} | |
| 646 \end{center} | |
| 647 \caption{Copyのアルゴリズム} | |
| 648 \label{fig:CopyAlgo} | |
| 649 \end{figure} | |
| 21 | 650 |
| 11 | 651 \chapter{CopyRedBlackTreeの実装} |
| 14 | 652 |
| 653 データのバックアップやレプリケーション，GCの機能を実装するためには， | |
| 654 データのコピーをする必要がある． | |
| 655 GearsOSのファイルシステムにおいて，データは全てRedBlackTreeに格納される． | |
| 656 しかしながら，現状のRedBlackTreeには木をコピーする機能が無い． | |
| 657 よって，RedBlackTreeに木のコピー機能を実装する必要がある． | |
| 658 | |
| 19 | 659 \lstinputlisting[label=src:CopyRedBlackTree.cbc, caption=CopyRedBlackTreeの実装]{src/CopyRedBlackTree.cbc} |
| 660 | |
| 11 | 661 \section{コピーのアルゴリズム} |
| 19 | 662 |
| 663 \lstinputlisting[label=src:CopyRedBlackTree.cbc, caption=CopyRedBlackTreeのアルゴリズム]{src/copyAlgorithm.cbc} | |
| 664 | |
| 665 \begin{figure}[ht] | |
| 666 \begin{center} | |
| 667 \includegraphics[width=160mm]{fig/copy_algo.png} | |
| 668 \end{center} | |
| 669 \caption{Copyのアルゴリズム} | |
| 670 \label{fig:CopyAlgo} | |
| 671 \end{figure} | |
| 672 | |
| 11 | 673 \section{Stackの使用に関して} |
| 674 \section{証明のしやすさについて} | |
| 675 | |
| 676 | |
| 677 | |
| 678 % TODO: バックアップのフローを図にしたい | |
| 679 | |
| 680 | |
| 681 \chapter{まとめと今後の課題} | |
| 682 | |
| 683 本論文ではGearsOSのファイルシステムとDBの設計について説明した． | |
| 684 今後，実装を行いながら設計と動作の確認，計測を行い， | |
| 685 設計の意図が反映されていることやプログラムの検証ができることを確認する必要がある． | |
| 686 | |
| 687 また，今後の課題や議題として次のようなものが挙げられる． | |
| 688 | |
| 689 \section{ファイルシステムにおけるスキーマ} | |
| 9 | 690 |
| 691 従来のRDBのようなスキーマが存在すると， | |
| 692 個別にバックアップなどを取らない限り | |
| 693 スキーマの変更以前にロールバックすることができない． | |
| 694 しかしながら，実際運用する上でスキーマを変更することは多々ある． | |
| 695 これは，データの信頼性を低下させると考える． | |
| 696 また，DB上のデータ構造とプログラム上で扱うデータ構造に差が生まれる | |
| 697 インピーダンスミスマッチが発生し，DBのデータをプログラムが扱う際に | |
| 698 その差を埋めるような変換を必要とする場合が生まれる． | |
| 699 一方で，スキーマがあることによってデータに対して高度な操作を行うことができ， | |
| 700 また，インデックスを容易に作成することができるといったメリットがある． | |
| 701 よって，スキーマフルなDBとスキーマレスなDBはそれぞれメリットデメリットがあり， | |
| 702 状況によって使い分けるのが良いと考える． | |
| 703 | |
| 704 今回は，非構造化データ内であれば構造化データを扱うことが可能であることと， | |
| 705 信頼性を保証したいという点から， | |
| 706 スキーマレスなDBとしてのファイルシステムを考える． | |
| 707 しかしながら，トランザクションの仕組みを作る上でRedBlackTreeに対し， | |
| 708 キーを設定することから完全なスキーマレスとは言えない構成となる． | |
| 709 | |
| 710 GearsOSのデータは全てDataGearで表される． | |
| 711 よって，GearsOSにおけるファイルシステムはDataGearの集合となる． | |
| 712 スキーマレスとはキーがない状態のことといえるが， | |
| 713 DataGearはキーが設定されていないため，その集合自体にスキーマは無い． | |
| 714 そのことから，GearsOSにおけるスキーマとはDataGear上のキーの構成であることがわかる． | |
| 715 なお，今回のRedBlackTreeによる構成の場合，キーはRedBlackTreeを指す． | |
| 716 DataGearはKernelのContextからプロセスのContextを経由して全て繋がっている． | |
| 717 よって，KernelのContext上にキーを用いたDataGearの参照を書き込む． | |
| 718 | |
| 11 | 719 \section{RedBlackTreeによる権限の表現} |
| 9 | 720 |
| 721 ファイルの権限はファイルシステムの重要な機能の一つであるため実装する必要がある． | |
| 722 今回のRedBlackTreeによる構成の場合，木のルートの所持者を設定することが | |
| 723 ファイルに対して権限を設定することにあたる． | |
| 724 ルートに対してアクセスする権限がなければ， | |
| 725 読み書きができないといった実装になると考える． | |
| 726 \section{データクエリ言語} | |
| 727 | |
| 728 ユーザーやアプリケーションがDBのデータにアクセスするための言語設計を | |
| 729 する必要がある． | |
| 730 RedBlackTreeのキーを用いたインデックスに対応し， | |
| 731 従来のSQLと比較してより柔軟なクエリを実行できることを目指したい． | |
| 732 | |
| 733 \section{ログなどの時系列データの保存} | |
| 734 | |
| 735 時系列データは通常のデータと違った保存の方法を考えることができる． | |
| 736 時系列に並んでいることを生かしたデータの保存方式や， | |
| 737 時間経過に伴うデータの重要性の変化を考慮に入れたデータ圧縮の方法をとることで， | |
| 738 より効率的な保存が可能だと考える． | |
| 739 | |
| 740 \section{スタンドアロンなDB} | |
| 741 | |
| 742 MySQLやPostgreSQLなどはOSの機能としてではなく， | |
| 743 それ自体が一つのアプリケーションとして自立的に動作している． | |
| 744 自立的に動作するのは，データのポータビリティを向上させるためである． | |
| 745 スタンドアロンなDBの形にするか， | |
| 746 その他の方法でポータビリティを向上させる手法を考えたい． | |
|
2
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
747 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
748 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
749 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
750 % %謝辞 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
751 \input{chapter/thanks.tex} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
752 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
753 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
754 %参考文献 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
755 \nocite{*} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
756 \bibliography{reference} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
757 \bibliographystyle{junsrt} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
758 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
759 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
760 %発表履歴 |
| 20 | 761 \input{chapter/history.tex} |
| 762 \addcontentsline{toc}{chapter}{研究関連論文業績} | |
|
2
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
763 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
764 %付録 |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
765 \addcontentsline{toc}{chapter}{付録} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
766 \appendix |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
767 \input{chapter/appendix.tex} |
|
c8151a82f313
copy tex files from ikki master
matac42 <matac@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
768 \end{document} |