Mercurial > hg > Papers > 2024 > matac-master

changeset 69:1c462e445437

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
jungle
author matac42 <matac@cr.ie.u-ryukyu.ac.jp>
date Mon, 12 Feb 2024 11:51:36 +0900
parents bb16877f26a3
children 3c3fa9356d61
files Paper/master_paper.pdf Paper/master_paper.sty Paper/master_paper.tex Paper/reference.bib TODO.md mindmaps/gears_fs_db.mm
diffstat 6 files changed, 87 insertions(+), 52 deletions(-) [+]
line wrap: on
line diff
Binary file Paper/master_paper.pdf has changed
--- a/Paper/master_paper.sty	Wed Feb 07 17:47:20 2024 +0900
+++ b/Paper/master_paper.sty	Mon Feb 12 11:51:36 2024 +0900
@@ -112,7 +112,7 @@
 
 % 専攻
 \def\course{工学専攻知能情報プログラム}
-\def\ecourse{Computer Science and Intelligent Systems Course}
+\def\ecourse{Computer Science and Intelligent Systems Program}
 
 % 署名
 \def\commission{論　文　審　査　会}
--- a/Paper/master_paper.tex	Wed Feb 07 17:47:20 2024 +0900
+++ b/Paper/master_paper.tex	Mon Feb 12 11:51:36 2024 +0900
@@ -117,7 +117,9 @@
 拡張を比較的容易に可能とする．
 
 OSの重要な機能の1つとしてファイルシステムが挙げられる．
-ファイルシステムはOSのプロセスやユーザーデータの管理に必要な機能である．
+OSの機能は多岐に渡り，複雑であるためOS全体を検証することは非常に難しいとされる．
+そのため，OSのコンポーネントの中でも特に重要で全体に影響を及ぼすファイルシステムを検証することが，
+OSを検証するための最初の課題として取り上げられる\cite{10.1007/s00165-006-0022-3}．
 ファイルシステムには可変長の文字列を格納するファイルと，
 そのファイルにアクセスするための名前管理の機能がある．
 ファイルの名前の一貫性は名前管理によって保証される．
@@ -133,14 +135,26 @@
 データをある形式で保持する仕組みであるという本質的な部分において違いはない．
 よって，ファイルシステムとDBを同一のシステムとして実装することが可能であると考える．
 
-ファイルシステムはOSにおいて重要な機能であるためGearsOSにおいても実装をする必要があると考えられ，
-当研究室では分散ファイルシステムやi-nodeを用いたファイルシステムの設計をしてきた\cite{cfile, directory}．
+当研究室におけるDBに関する取り組みとして木構造分散データベースJungleが挙げられる\cite{christie}．
+Jungleは非破壊RedBlackTreeを基本構造とし，木構造を直接扱うデータベースである．
+木構造を扱うことによって，XMLやJsonで記述された構造をデータベースの設計をすることなく読み込むことが可能である
+といった特徴を持つ．
+分散フレームワークAliceによって分散構成をとり，
+その仕組みの改良版として分散フレームワークChristieが開発された．
+Christieは木構造などのデータ構造をネットワーク上でやり取りすることができ，
+GearsOSの分散ファイルシステムとして使えるのが望ましい．
+
+
+ファイルシステムはGearsOSにおいても実装をする必要があると考えられ，
+当研究室ではGearsOSにおける，
+分散ファイルシステムやi-nodeを用いたファイルシステムの設計をしてきた\cite{cfile, file, directory}．
 それらのファイルシステムは基本構造として非破壊RedBlackTreeを持つ．
 しかし，非破壊RedBlackTreeはデータが無尽蔵に増加するため，実用上の問題があると言える．
 よって，データの増加を防ぐような仕組みが必要である．
 また，本システムにはデータの多重度や一貫性を確保するための機能がないため実装したい．
-本研究では，GearsOSのデータの多重度や一貫性の確保，
-非破壊RedBlackTreeの無尽蔵な増加を防ぐためのGCとレプリケーション，バックアップ機構の設計を行い，
+本研究では，実用的なGearsOSのファイルシステムの構築を目指し，
+データの多重度や一貫性の確保，非破壊RedBlackTreeの無尽蔵な増加を防ぐためのGCとレプリケーション，
+バックアップ機構の設計を行い，
 それらを実現するために必要なRedBlackTreeのコピーの仕組みの設計，構築，考察を行った．
 
 \chapter{軽量継続を基本とする言語CbC}
@@ -500,7 +514,7 @@
 \section{非破壊RedBlackTreeによる構成}
 
 ディスク上とメモリ上でデータの構造は，RedBlackTreeに統一する．
-一般的に，ディスク上のデータ構造としてB-Treeが用いられることが多い．
+一般的に，ディスク上のデータ構造としてB-Treeが用いられることが多い\cite{10.1145/2501620.2501623}．
 なぜならば，HDDを用いる場合はブロックへのアクセス回数を減らしデータアクセスの時間を短くするために，
 B-Treeのようなノードを複数持つことができる構造が効果的だからである．
 その点ではRedBlackTreeはB-Treeに劣る．
@@ -508,6 +522,20 @@
 RedBlackTreeでなくB-Treeを用いる利点は少ないと考える．
 よって，ディスク上とメモリ上のデータ構造をRedBlackTreeに統一することが考えられる．
 そうすることによって，ディスク上とメモリ上のデータのやりとりは単純なコピーで実装できる．
+図\ref{fig:TreeEdit}は非破壊的編集を行うRedBlackTreeを表している．
+編集前の木構造の6のノードをAにアップデートすることを考える．
+まず，ルートノードからアップデートしたいノード6までをコピーする．
+その後，コピーしたもののノード6をAにアップデートする．
+これにより，アップデート前のノード6を破壊することなくAにアップデートが可能である．
+参照する時は，黒のルートノードから辿れば古い6が，赤のルートノードから辿れば新しいAが見える．
+
+\begin{figure}[ht]
+  \begin{center}
+      \includegraphics[width=150mm]{fig/nonDestroyTreeEdit.pdf}
+  \end{center}
+  \caption{非破壊的なTree編集}
+  \label{fig:TreeEdit}
+\end{figure}
 
 \section{RedBlackTreeのトランザクション}
 
@@ -578,25 +606,8 @@
 ロールバックがスキーマの変更によって出来なくなることは信頼性に問題があると考えると，
 スキーマを定義する必要のないスキーマレスなDBが必要になる．
 ファイルシステムはスキーマレスなDBといえるので，ファイルシステムを構築しつつ
-DBがスキーマによって実現していた機能を付け加えることを試みる．
+DBがスキーマによって実現していた機能を付け加えることを考えたい．
 
-RedBlackTreeは実装によって，操作が破壊的なものとそうでないものがある．
-今回用いるのは，非破壊的な実装のRedBlackTreeである．
-図\ref{fig:TreeEdit}は非破壊的編集を行うRedBlackTreeを表している．
-編集前の木構造の6のノードをAにアップデートすることを考える．
-まず，ルートノードからアップデートしたいノード6までをコピーする．
-その後，コピーしたもののノード6をAにアップデートする．
-これにより，アップデート前のノード6を破壊することなくAにアップデートが可能である．
-参照する時は，黒のルートノードから辿れば古い6が，赤のルートノードから辿れば新しいAが見える．
-この仕組みは，データのバックアップやDBのロールバックに用いることが可能だと考える．
-
-\begin{figure}[ht]
-  \begin{center}
-      \includegraphics[width=150mm]{fig/nonDestroyTreeEdit.pdf}
-  \end{center}
-  \caption{非破壊的なTree編集}
-  \label{fig:TreeEdit}
-\end{figure}
 
 \section{DataGearManagerによる分散ファイルシステム}
 
--- a/Paper/reference.bib	Wed Feb 07 17:47:20 2024 +0900
+++ b/Paper/reference.bib	Mon Feb 12 11:51:36 2024 +0900
@@ -25,7 +25,7 @@
   howpublished = {http://www.cr.ie.u-ryukyu.ac.jp/hg/Gears/GearsAgda/}
 }
 
-@misc{garbtree,
+@article{garbtree,
   author  = {森 逸汰, 河野 真治(琉球大学)},
   title   = {GearsAgdaによるRed Black Treeの検証},
   journal = {情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)},
@@ -33,7 +33,7 @@
   year    = 2023
 }
 
-@misc{gearscodemngment,
+@article{gearscodemngment,
   author  = {仲吉 菜々子, 河野 真治(琉球大学)},
   title   = {Gears OSのCodeGear Management},
   journal = {情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)},
@@ -92,22 +92,6 @@
   year    = 2020
 }
 
-@article{xv6kernel,
-  author  = {坂本 昂弘 (琉球大学工学部情報工学科), 桃原 優 (琉球大学大学院理工学研究科情報工学専攻), 河野 真治 (琉球大学工学部情報工学科)},
-  journal = {情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)},
-  title   = {継続を用いた xv6 kernel の書き換え},
-  month   = {May},
-  year    = 2019
-}
-
-@article{xv6component,
-  author  = {清水 隆博，河野 真治(琉球大学)},
-  journal = {情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)},
-  title   = {xv6の構成要素の継続の分析},
-  month   = {May},
-  year    = 2020
-}
-
 @misc{xv6,
   author       = {{Russ Cox, Frans Kaashoek, Robert Morris}},
   title        = {xv6 a simple, Unix-like teaching operating system},
--- a/TODO.md	Wed Feb 07 17:47:20 2024 +0900
+++ b/TODO.md	Mon Feb 12 11:51:36 2024 +0900
@@ -24,7 +24,7 @@
 - [x] レプリケーションとDGM通信の話を入れる
 - [x] 評価
 - [x] まとめと今後の課題
-- [ ] 4章......
+- [x] 4.4
 
 確認したいこと
 
@@ -39,6 +39,14 @@
 - [x] __codeのフォントを直す
 - [x] AspectJの引用
 - [x] CbCの記述例(exit code)
-- [ ] 英語の文献をもっと入れよう
+- [x] 「そうなってしまっている」みたいな書き方を避ける
+
+文献整理(4章を書くためにも......)
+
+- [x] 関連研究にjungle
+- [x] 参照されているか確認する
+- [x] 信頼性とどうつながるかを言及する
 - [ ] LFSやFilesystem Fragmentationへ言及する
-- [ ] 「そうなってしまっている」みたいな書き方を避ける
\ No newline at end of file
+  - Scale and Performance in a Filesystem Semi-Microkernel
+- [ ] GearsAgdaのことを書く(何を書く？)
+- [ ] 今後の課題追加
--- a/mindmaps/gears_fs_db.mm	Wed Feb 07 17:47:20 2024 +0900
+++ b/mindmaps/gears_fs_db.mm	Mon Feb 12 11:51:36 2024 +0900
@@ -412,7 +412,23 @@
 <node TEXT="卒論" ID="ID_1486800431" CREATED="1701692926762" MODIFIED="1701692930073"/>
 </node>
 <node TEXT="参考文献" ID="ID_1704420848" CREATED="1702289534980" MODIFIED="1702289539226">
-<node TEXT="AspectJ" ID="ID_682948653" CREATED="1702289539526" MODIFIED="1702289543447"/>
+<node TEXT="AspectJ" ID="ID_682948653" CREATED="1702289539526" MODIFIED="1702289543447">
+<node TEXT="リフレクション" ID="ID_1995111059" CREATED="1707303928449" MODIFIED="1707303982772"/>
+</node>
+<node TEXT="BTRFS" ID="ID_1614431311" CREATED="1707303820403" MODIFIED="1707303827963">
+<node TEXT="B-TreeのFilesystem" ID="ID_1637660960" CREATED="1707303916679" MODIFIED="1707303923840"/>
+</node>
+<node TEXT="build averifiable filesysmte" ID="ID_351808459" CREATED="1707303849739" MODIFIED="1707303864754">
+<node TEXT="filesystemをvelifyする取り組みは良いチャレンジ" ID="ID_1164383625" CREATED="1707303900261" MODIFIED="1707303914660"/>
+</node>
+</node>
+<node TEXT="Jungle" ID="ID_1256633010" CREATED="1707697007038" MODIFIED="1707697010064">
+<node TEXT="分散ファイルシステムとDBが一体となっている" ID="ID_1826578281" CREATED="1707698420118" MODIFIED="1707698433605"/>
+<node TEXT="Christieの前身" ID="ID_723120347" CREATED="1707700703988" MODIFIED="1707700711775"/>
+<node TEXT="Javaで記述する" ID="ID_1375184387" CREATED="1707700712575" MODIFIED="1707700859983"/>
+<node TEXT="Aliceで分散構成をとる" ID="ID_1364155188" CREATED="1707700862356" MODIFIED="1707700897852"/>
+<node TEXT="AliceとJungleを合体させて改良したのがChristie" ID="ID_580838272" CREATED="1707700905389" MODIFIED="1707700926493"/>
+<node TEXT="非破壊的RedBlackTreeを基本構造とする" ID="ID_1189580672" CREATED="1707700927004" MODIFIED="1707701119748"/>
 </node>
 </node>
 <node TEXT="評価方法" POSITION="right" ID="ID_1979397312" CREATED="1699850131177" MODIFIED="1699850137060"/>
@@ -696,7 +712,7 @@
 </node>
 </node>
 </node>
-<node TEXT="CopyRedBlackTreeによるレプリケーション" FOLDED="true" ID="ID_1106336919" CREATED="1703490971550" MODIFIED="1704973002324">
+<node TEXT="CopyRedBlackTreeによるレプリケーション" ID="ID_1106336919" CREATED="1703490971550" MODIFIED="1704973002324">
 <node TEXT="GCとほとんど同じ仕組みで実装する" ID="ID_1738615864" CREATED="1704973003111" MODIFIED="1704973021762"/>
 <node TEXT="実際にはCopy時に送信を同時に行う" ID="ID_1536582463" CREATED="1704973022427" MODIFIED="1704974557823"/>
 <node TEXT="socket通信が使える" ID="ID_703110643" CREATED="1705985752084" MODIFIED="1705985760495"/>
@@ -1056,7 +1072,7 @@
 <node TEXT="それ以外はまとめと今後の課題に書く" ID="ID_1941288242" CREATED="1706803862696" MODIFIED="1706803878303"/>
 </node>
 </node>
-<node TEXT="まとめと今後の課題" POSITION="right" ID="ID_912711900" CREATED="1706956151544" MODIFIED="1707213611142">
+<node TEXT="まとめと今後の課題" FOLDED="true" POSITION="right" ID="ID_912711900" CREATED="1706956151544" MODIFIED="1707213611142">
 <node TEXT="非破壊RedBlackTreeの増大を防ぐ仕組みを構築できた" ID="ID_418966492" CREATED="1706956585170" MODIFIED="1706956610719"/>
 <node TEXT="別コンテキストへのコピー" ID="ID_1209930854" CREATED="1706956313462" MODIFIED="1706956324424"/>
 <node TEXT="GearsOS全体をGCすることも考えられる" ID="ID_1250275844" CREATED="1707013490904" MODIFIED="1707013522142"/>
@@ -1081,16 +1097,32 @@
 </node>
 </node>
 <node TEXT="ヒープオーバーフロー問題" ID="ID_1520918245" CREATED="1707285616558" MODIFIED="1707285622872">
-<node TEXT="ALLOCATEに限界がある" ID="ID_145024116" CREATED="1707286144904" MODIFIED="1707286157215"/>
+<node TEXT="Contextにおいて，DataGearを格納するヒープ領域がオーバーフローする" ID="ID_1897126966" CREATED="1707291645187" MODIFIED="1707291668041"/>
+<node TEXT="ALLOCATEに限界がある" ID="ID_145024116" CREATED="1707286144904" MODIFIED="1707286157215">
+<node TEXT="領域拡張機能がない" ID="ID_398334930" CREATED="1707291676098" MODIFIED="1707291682705"/>
+</node>
 <node TEXT="ヒープ領域の追加機構がないため必要である" ID="ID_1200324860" CREATED="1707286157588" MODIFIED="1707286202952"/>
 </node>
-<node TEXT="GCとレプリケーションの実装" ID="ID_1710394671" CREATED="1707286605335" MODIFIED="1707286619440"/>
-<node TEXT="GearsOSのプログラミング" ID="ID_1522560459" CREATED="1707285716374" MODIFIED="1707285722515">
 <node TEXT="テストケースの生成" ID="ID_508754044" CREATED="1707285602305" MODIFIED="1707285611890">
 <node TEXT="10パターンあたりで1000行のテストコードになった" ID="ID_310747926" CREATED="1707286211702" MODIFIED="1707286225014"/>
 <node TEXT="動作確認を困難にしている" ID="ID_729064103" CREATED="1707286242799" MODIFIED="1707286251072"/>
 <node TEXT="もっと簡潔に書ける仕組みが必要である" ID="ID_1162968810" CREATED="1707286225521" MODIFIED="1707286238147"/>
 </node>
+<node TEXT="GCとレプリケーションの実装" ID="ID_1710394671" CREATED="1707286605335" MODIFIED="1707286619440">
+<node TEXT="今回は簡易的なswapの実装まで行った．" ID="ID_1766016847" CREATED="1707291693108" MODIFIED="1707291717793"/>
+<node TEXT="GCとレプリケーションを実装したい" ID="ID_398459676" CREATED="1707291718649" MODIFIED="1707291726995"/>
+<node TEXT="GC" ID="ID_52826664" CREATED="1707291727402" MODIFIED="1707291729042">
+<node TEXT="Contextの廃棄" ID="ID_222728417" CREATED="1707291729227" MODIFIED="1707291750597"/>
+<node TEXT="フリーリスト" ID="ID_1484227551" CREATED="1707291751028" MODIFIED="1707291755510"/>
+<node TEXT="GCのタイミング機構" ID="ID_73958490" CREATED="1707291756430" MODIFIED="1707291772097"/>
+<node TEXT="GearsOS全体をGCすることも考えられる" ID="ID_23255429" CREATED="1707291784849" MODIFIED="1707291797381"/>
+</node>
+<node TEXT="レプリケーション" ID="ID_1307940903" CREATED="1707291803936" MODIFIED="1707291808069">
+<node TEXT="別ノードでコピーの実行" ID="ID_55786671" CREATED="1707291808610" MODIFIED="1707291819132"/>
+<node TEXT="ノード間の通信機能" ID="ID_1367716807" CREATED="1707291820003" MODIFIED="1707291969617">
+<node TEXT="プロトコルを決める" ID="ID_935003650" CREATED="1707291979910" MODIFIED="1707291986835"/>
+</node>
+</node>
 </node>
 </node>
 </node>