Mercurial > hg > Papers > 2024 > matac-master

changeset 60:6c5965c3539e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
make cover
author matac42 <matac@cr.ie.u-ryukyu.ac.jp>
date Mon, 05 Feb 2024 16:39:36 +0900
parents 7009a8e8d746
children e7961c306d28
files Paper/master_paper.pdf Paper/master_paper.sty Paper/master_paper.tex Paper/src/hello.cbc TODO.md mindmaps/gears_fs_db.mm
diffstat 6 files changed, 123 insertions(+), 9 deletions(-) [+]
line wrap: on
line diff
Binary file Paper/master_paper.pdf has changed
--- a/Paper/master_paper.sty	Sun Feb 04 12:22:50 2024 +0900
+++ b/Paper/master_paper.sty	Mon Feb 05 16:39:36 2024 +0900
@@ -168,7 +168,7 @@
         {\fontsize{16pt}{0pt}\bf\@eauthor\par}
 
         \vskip 1.5em
-        {\includegraphics[clip,keepaspectratio=true,scale=0.48]{fig/u-ryukyu-Mark.eps}}
+        {\includegraphics[clip,keepaspectratio=true,scale=0.60]{fig/u-ryukyu-Mark.eps}}
         \vskip 1.5em
 
         {\fontsize{16pt}{0pt}\bf\mc\university\\}
@@ -191,6 +191,51 @@
   \end{center}
 }
 
+
+\newcommand{\makecover} {
+  \newpage\null
+  \thispagestyle{empty}
+  \vskip 1cm%
+
+  \begin{center}%
+    \let\footnote\thanks
+        {\fontsize{16pt}{0pt}\bf\thesis\\}
+        \vskip 0.5em
+        {\fontsize{16pt}{0pt}\bf\ethesis}
+        \vskip 1.5em
+        {\fontsize{18pt}{0pt}\bf\mc\@title\\}
+        \vskip 0.5em
+        {\fontsize{18pt}{0pt}\bf{\@etitle}}
+        \vskip 1.8em
+
+        {\fontsize{14pt}{0pt}\mc\@year\\}
+        {\fontsize{14pt}{0pt}\@eyear}
+        \vskip 1.0em
+
+        {\fontsize{16pt}{0pt}\bf\mc\@author\par}
+        \vskip 0.5em
+        {\fontsize{16pt}{0pt}\bf\@eauthor\par}
+
+        \vskip 1.5em
+        {\includegraphics[clip,keepaspectratio=true,scale=0.60]{fig/u-ryukyu-Mark.eps}}
+        \vskip 1.5em
+
+        {\fontsize{16pt}{0pt}\bf\mc\university\\}
+        \vskip 0.5em
+        {\fontsize{16pt}{0pt}\bf\mc\department\\}
+        \vskip 0.5em
+        {\fontsize{16pt}{0pt}\bf\mc\course}
+        \vskip 1.8em
+
+        {\fontsize{16pt}{0pt}\textbf\ecourse\\}
+        \vskip 0.5em
+        {\fontsize{16pt}{0pt}\textbf\edepartment\\}
+        \vskip 0.5em
+        {\fontsize{16pt}{0pt}\textbf\euniversity}
+        \vskip 0.8em
+  \end{center}
+}
+
 \newcommand{\makecommission} {
   \noindent
   論文題目:GearsOS のファイルシステムにおける GC とレプリケー
--- a/Paper/master_paper.tex	Sun Feb 04 12:22:50 2024 +0900
+++ b/Paper/master_paper.tex	Mon Feb 05 16:39:36 2024 +0900
@@ -65,6 +65,8 @@
 \makeindex
 \begin{document}
 %rome
+\makecover
+
 \maketitle
 
 \pagenumbering{roman}
@@ -200,7 +202,7 @@
 add1は処理の最後にadd2 CodeGearへgotoを行う．
 その際Output DataGear out\_nをadd2のInput DataGearとして渡す．
 このようにCbCではCodeGearのOutput DataGearを次のCodeGearのInput DataGearとして渡すことを繰り返すことで処理を進め，
-最後はexitへgotoすることで処理を終了する．
+最後はexit\_codeへgotoすることで処理を終了する．
 
 \lstinputlisting[caption=CbCのプログラム例,label=src:cbc]{src/hello.cbc}
 
@@ -598,6 +600,9 @@
 
 \section{DataGearManagerによる分散ファイルシステム}
 
+本研究室では，一木 貴裕\cite{cfile}GearsOSの分散ファイルシステム設計が行われた．
+
+
 \chapter{GearsFileSystemにおけるGCとレプリケーション}
 
 本章ではRedBlackTreeのCopyによるGCとレプリケーションの基本設計を述べる．
@@ -926,19 +931,42 @@
 
 \section{swap}
 
-ソースコード\ref{}に
+swapはコピー自体に関する機能ではなく，Copying GCの動作を想定した機能を実装したものである．
+Copying GCがFrom領域とTo領域を入れ替えるように，
+コピー前後の木を入れ替える動作をする．
+swapは実際にはswap，swap1，swap2のような複数のCodeGearで構成されている．
+ソースコード\ref{src:swap.cbc}に木の入れ替え処理を行うswap2 CodeGearを示す．
+3行目のtoTreeは，toStackにpushした新しい木のルートノードに当たるノードである．
+4行目で新規にRedBlackTreeを作成し，5行目でtoTreeをnewRedBlackTreeのrootに設定している．
+その後，7行目でtreeにnewRedBlackTreeを指定することで木の入れ替えを行なっている．
+
+\lstinputlisting[label=src:swap.cbc, caption=swap2 CodeGear(木の入れ替え処理部分)]{src/swap.cbc}
 
 \chapter{評価}
 
-\section{テストコード}
 
 \section{非破壊RedBlackTreeの増大抑制}
 
+今回はCopyRedBlackTreeの実装によって，
+コピー先の木はコピー時にrootから参照可能であったノードのみを持ち，
+参照されていないノードが排除されているため，
+コピーをすることで参照する木の増大を防ぐことが可能である．
+しかし，コピー元の木やゴミのメモリ領域を再利用する仕組みがないため，
+メモリ領域の使用量の軽減にはつながっていない．
+現状は同一Context上のCode Tableのヒープ領域に木をコピーしている．
+別Contextへ木をコピーし，
+コピー元のContext自体を廃棄する仕組みを実装することでメモリ領域の再利用が可能であると考える．
+
+\section{RedBlackTreeの持続性}
+
+
+
 \section{ヒープオーバーフロー問題}
 
 \section{Stackの使用}
 
-\section{RedBlackTreeの持続性}
+
+\section{同一Contextへのコピー}
 
 \chapter{まとめと今後の課題}
 
--- a/Paper/src/hello.cbc	Sun Feb 04 12:22:50 2024 +0900
+++ b/Paper/src/hello.cbc	Mon Feb 05 16:39:36 2024 +0900
@@ -10,7 +10,7 @@
 
 __code end(int in_n) {
     printf("%d", n);
-    goto exit(0);
+    goto exit_code();
 }
 
 int main(int argc, char *arcv[]) {
--- a/TODO.md	Sun Feb 04 12:22:50 2024 +0900
+++ b/TODO.md	Mon Feb 05 16:39:36 2024 +0900
@@ -15,6 +15,7 @@
 - [x] 一度通して見直し(2024/01/30)
 
 - [x] 別Contextへの書き込み
+
 - [ ] DGMによる分散ファイルシステム
 - [ ] 実装の説明
 - [ ] 評価
--- a/mindmaps/gears_fs_db.mm	Sun Feb 04 12:22:50 2024 +0900
+++ b/mindmaps/gears_fs_db.mm	Mon Feb 05 16:39:36 2024 +0900
@@ -850,7 +850,7 @@
 </node>
 </node>
 </node>
-<node TEXT="CopyRedBlackTreeの実装" POSITION="right" ID="ID_1875155929" CREATED="1706686273106" MODIFIED="1706691080675" HGAP_QUANTITY="-10.75 pt" VSHIFT_QUANTITY="267.74999 pt">
+<node TEXT="CopyRedBlackTreeの実装" FOLDED="true" POSITION="right" ID="ID_1875155929" CREATED="1706686273106" MODIFIED="1707024295815" HGAP_QUANTITY="-10.75 pt" VSHIFT_QUANTITY="267.74999 pt">
 <node TEXT="説明" ID="ID_1618684595" CREATED="1706689938660" MODIFIED="1706689944053">
 <node TEXT="TreeのAPIのひとつとして実装" ID="ID_1013219955" CREATED="1706934961492" MODIFIED="1706934969874"/>
 <node TEXT="アルゴリズム" ID="ID_73867053" CREATED="1706934970286" MODIFIED="1706934976931"/>
@@ -900,7 +900,7 @@
 <node TEXT="swap2" ID="ID_524874877" CREATED="1706690594880" MODIFIED="1706690620487"/>
 </node>
 </node>
-<node TEXT="CodeGearの遷移図" ID="ID_1817152324" CREATED="1706690760642" MODIFIED="1706690766522">
+<node TEXT="CodeGearの遷移図" ID="ID_1817152324" CREATED="1706690760642" MODIFIED="1707024295813">
 <node TEXT="4つのフェーズ" ID="ID_659102113" CREATED="1706692593057" MODIFIED="1706692597444">
 <node TEXT="leftDown" ID="ID_1733945258" CREATED="1706692652301" MODIFIED="1706692657973"/>
 <node TEXT="rightDown" ID="ID_576929999" CREATED="1706692658387" MODIFIED="1706692661892"/>
@@ -950,6 +950,46 @@
 <node TEXT="tree-&gt;rootを書き換えて，途中のノードからコピーできるみたいなの作りたい" ID="ID_1603927493" CREATED="1706692686178" MODIFIED="1706692704418"/>
 </node>
 <node TEXT="評価" POSITION="right" ID="ID_1699170037" CREATED="1706803749390" MODIFIED="1706803756057">
+<node TEXT="説明" ID="ID_1332913546" CREATED="1707024290462" MODIFIED="1707024304655">
+<node TEXT="テストコード" ID="ID_83989606" CREATED="1707024312272" MODIFIED="1707024315913">
+<node TEXT="いくつかの考えられる木の形はテストした" ID="ID_401372478" CREATED="1707024501611" MODIFIED="1707024539431">
+<node TEXT="15パターン" ID="ID_1060583266" CREATED="1707036504432" MODIFIED="1707036508605"/>
+<node TEXT="動作した" ID="ID_854834536" CREATED="1707024607282" MODIFIED="1707024611419"/>
+<node TEXT="検証漏れは否めない" ID="ID_1172918896" CREATED="1707024655533" MODIFIED="1707024662259"/>
+<node TEXT="コピーを定理証明で検証する必要がありそう" ID="ID_518078514" CREATED="1707024673942" MODIFIED="1707024691543"/>
+</node>
+<node TEXT="ある程度大きな木のテストもした" ID="ID_1277626903" CREATED="1707024543799" MODIFIED="1707024606136">
+<node TEXT="一定の大きさまでは動作した" ID="ID_1432110604" CREATED="1707024612762" MODIFIED="1707024620823"/>
+<node TEXT="ヒープオーバーフロー問題がある" ID="ID_850593668" CREATED="1707024336504" MODIFIED="1707024633289"/>
+<node TEXT="Contextのヒープ領域の上限がある" ID="ID_1897190409" CREATED="1707024637878" MODIFIED="1707024736757"/>
+<node TEXT="上限を拡大する仕組みがいる" ID="ID_37519178" CREATED="1707024740319" MODIFIED="1707024747188"/>
+</node>
+</node>
+<node TEXT="非破壊RedBlackTreeの増大抑制" ID="ID_529836819" CREATED="1707024322382" MODIFIED="1707024336261">
+<node TEXT="Copyによって参照される木の増大は防がれる" ID="ID_1864064653" CREATED="1707024754607" MODIFIED="1707024920464"/>
+<node TEXT="しかし，ゴミの再利用ができない" ID="ID_1451664377" CREATED="1707024791454" MODIFIED="1707024807406"/>
+<node TEXT="GCとしては不十分" ID="ID_379609728" CREATED="1707024927318" MODIFIED="1707024931544"/>
+<node TEXT="ゴミをフリーリストなどに接続する必要がある" ID="ID_891844429" CREATED="1707024810210" MODIFIED="1707024822315"/>
+<node TEXT="もしくは，別Contextへのコピーができていれば，Contextごと捨てることが考えられる" ID="ID_1594506897" CREATED="1707024822639" MODIFIED="1707024844218"/>
+</node>
+<node TEXT="同一ContextへのCopy" ID="ID_1254085673" CREATED="1707024372861" MODIFIED="1707024381556">
+<node TEXT="現状は同一Contextにコピーされている" ID="ID_309717594" CREATED="1707024852535" MODIFIED="1707024863311"/>
+<node TEXT="別Contextにする必要がある" ID="ID_275256559" CREATED="1707024863869" MODIFIED="1707024890077">
+<node TEXT="ゴミ再利用のため" ID="ID_1756005796" CREATED="1707024890463" MODIFIED="1707024901662"/>
+<node TEXT="レプリケーションのため" ID="ID_107480701" CREATED="1707024969329" MODIFIED="1707024973700"/>
+</node>
+<node TEXT="ALLOCATEの修正がいる" ID="ID_823404339" CREATED="1707024986029" MODIFIED="1707024994422"/>
+</node>
+<node TEXT="Stackの使用" ID="ID_1762844508" CREATED="1707024350775" MODIFIED="1707024356847">
+<node TEXT="軽量継続の利点はcall stackなどの状態をもたいないことにある" ID="ID_1185503713" CREATED="1707025000678" MODIFIED="1707025032692"/>
+<node TEXT="しかし，Stackを使用している" ID="ID_206860039" CREATED="1707025033563" MODIFIED="1707025074768"/>
+<node TEXT="明示的に使用しており，CodeGear自体が状態を持っているわけではないので問題ない" ID="ID_1843110566" CREATED="1707025055736" MODIFIED="1707025100382"/>
+<node TEXT="SingleLinkedStackの操作もCodeGearの遷移で行われている" ID="ID_1840403810" CREATED="1707025106566" MODIFIED="1707025121167"/>
+</node>
+<node TEXT="RedBlackTreeの持続性" ID="ID_661781686" CREATED="1707024357426" MODIFIED="1707024367737">
+<node TEXT="単純なコピーで実装したため，データの持続性が保たれている" ID="ID_1984829925" CREATED="1707025135915" MODIFIED="1707025157178"/>
+</node>
+</node>
 <node TEXT="テストは動いた" ID="ID_1202499591" CREATED="1706803764279" MODIFIED="1706803770865">
 <node TEXT="ノード数ごとのテストができる" ID="ID_405894808" CREATED="1706804393369" MODIFIED="1706804408856"/>
 <node TEXT="Copy機能自体は実装できたと言える" ID="ID_1634077677" CREATED="1706804577635" MODIFIED="1706804588696"/>
@@ -964,7 +1004,7 @@
 </node>
 </node>
 <node TEXT="ノード数6317でsegmentation faultする" ID="ID_1114925075" CREATED="1706803771828" MODIFIED="1706803794161">
-<node TEXT="SingleLinkedStackの制約がある" ID="ID_1126882824" CREATED="1706804328812" MODIFIED="1706804337539"/>
+<node TEXT="ヒープオーバーフローしている" ID="ID_1734933152" CREATED="1707023327807" MODIFIED="1707023333799"/>
 </node>
 <node TEXT="同じContextにコピーしてしまっている" ID="ID_917538944" CREATED="1706803805237" MODIFIED="1706803821463">
 <node TEXT="ALLOCATEの改造が必要" ID="ID_1305277586" CREATED="1706804450792" MODIFIED="1706804461228"/>