Mercurial > hg > Papers > 2024 > matac-master
changeset 50:0cea940227c4
...
| author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 30 Jan 2024 15:40:33 +0900 |
| parents | 9f0ef2d6ce2f |
| children | bc69a109778c |
| files | Paper/fig/rbtree_def.drawio Paper/fig/rbtree_def.pdf Paper/fig/rbtree_def.png Paper/master_paper.pdf Paper/master_paper.tex mindmaps/gears_fs_db.mm |
| diffstat | 6 files changed, 33 insertions(+), 91 deletions(-) [+] |
line wrap: on
line diff
--- a/Paper/fig/rbtree_def.drawio Tue Jan 30 14:32:19 2024 +0900 +++ b/Paper/fig/rbtree_def.drawio Tue Jan 30 15:40:33 2024 +0900 @@ -1,6 +1,6 @@ <mxfile host="65bd71144e"> <diagram id="PxV3Z1aBI1mM_MlTBdEj" name="Page-1"> - <mxGraphModel dx="276" dy="760" grid="1" gridSize="10" guides="1" tooltips="1" connect="1" arrows="1" fold="1" page="1" pageScale="1" pageWidth="827" pageHeight="1169" math="0" shadow="0"> + <mxGraphModel dx="661" dy="564" grid="1" gridSize="10" guides="1" tooltips="1" connect="1" arrows="1" fold="1" page="1" pageScale="1" pageWidth="827" pageHeight="1169" math="0" shadow="0"> <root> <mxCell id="0"/> <mxCell id="1" parent="0"/> @@ -11,7 +11,7 @@ <mxGeometry relative="1" as="geometry"/> </mxCell> <mxCell id="2" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="122.5" y="307.5" width="20" height="20" as="geometry"/> + <mxGeometry x="152.5" y="150" width="20" height="20" as="geometry"/> </mxCell> <mxCell id="11" style="edgeStyle=none;html=1;entryX=0.7;entryY=0.5;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" parent="1" source="3" target="8" edge="1"> <mxGeometry relative="1" as="geometry"/> @@ -20,126 +20,65 @@ <mxGeometry relative="1" as="geometry"/> </mxCell> <mxCell id="3" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="152.5" y="347.5" width="20" height="20" as="geometry"/> + <mxGeometry x="182.5" y="190" width="20" height="20" as="geometry"/> </mxCell> <mxCell id="4" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="92.5" y="347.5" width="20" height="20" as="geometry"/> + <mxGeometry x="122.5" y="190" width="20" height="20" as="geometry"/> </mxCell> <mxCell id="5" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="182.5" y="387.5" width="20" height="20" as="geometry"/> + <mxGeometry x="212.5" y="230" width="20" height="20" as="geometry"/> </mxCell> <mxCell id="8" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="122.5" y="387.5" width="20" height="20" as="geometry"/> + <mxGeometry x="152.5" y="230" width="20" height="20" as="geometry"/> </mxCell> - <mxCell id="41" style="edgeStyle=none;html=1;entryX=0.55;entryY=1;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" parent="1" source="43" target="47" edge="1"> - <mxGeometry relative="1" as="geometry"/> + <mxCell id="41" style="edgeStyle=none;html=1;entryX=0.366;entryY=0.463;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;startArrow=none;" parent="1" source="82" edge="1"> + <mxGeometry relative="1" as="geometry"> + <mxPoint x="103.75" y="160.0000000000001" as="targetPoint"/> + </mxGeometry> </mxCell> - <mxCell id="42" style="edgeStyle=none;html=1;entryX=0.45;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" parent="1" source="43" target="46" edge="1"> - <mxGeometry relative="1" as="geometry"/> + <mxCell id="92" style="html=1;fontFamily=Garamond;fontSize=14;endArrow=none;endFill=0;" edge="1" parent="1" source="43"> + <mxGeometry relative="1" as="geometry"> + <mxPoint x="162.5" y="160" as="targetPoint"/> + </mxGeometry> </mxCell> <mxCell id="43" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="170" y="105" width="20" height="20" as="geometry"/> - </mxCell> - <mxCell id="44" style="edgeStyle=none;html=1;entryX=0.7;entryY=0.5;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" parent="1" source="46" target="53" edge="1"> - <mxGeometry relative="1" as="geometry"/> - </mxCell> - <mxCell id="45" style="edgeStyle=none;html=1;entryX=0.4;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" parent="1" source="46" target="50" edge="1"> - <mxGeometry relative="1" as="geometry"/> - </mxCell> - <mxCell id="46" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="200" y="145" width="20" height="20" as="geometry"/> - </mxCell> - <mxCell id="86" style="edgeStyle=none;html=1;entryX=0.6;entryY=0.55;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" edge="1" parent="1" source="47" target="85"> - <mxGeometry relative="1" as="geometry"/> - </mxCell> - <mxCell id="47" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="70" y="145" width="20" height="20" as="geometry"/> - </mxCell> - <mxCell id="50" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="230" y="185" width="20" height="20" as="geometry"/> - </mxCell> - <mxCell id="53" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="170" y="185" width="20" height="20" as="geometry"/> + <mxGeometry x="122.5" y="110" width="20" height="20" as="geometry"/> </mxCell> <mxCell id="58" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.503;entryY=0.347;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;curved=1;dashed=1;fontSize=14;fontFamily=Garamond;" parent="1" source="54" target="43" edge="1"> <mxGeometry relative="1" as="geometry"/> </mxCell> <mxCell id="54" value="root" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="230" y="80" width="30" height="30" as="geometry"/> - </mxCell> - <mxCell id="61" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;dashed=1;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" parent="1" source="56" target="50" edge="1"> - <mxGeometry relative="1" as="geometry"/> - </mxCell> - <mxCell id="56" value="current" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="280" y="155" width="60" height="30" as="geometry"/> + <mxGeometry x="222.5" y="80" width="30" height="30" as="geometry"/> </mxCell> <mxCell id="66" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;entryX=0.704;entryY=0.481;entryDx=0;entryDy=0;entryPerimeter=0;dashed=1;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" parent="1" source="63" target="2" edge="1"> <mxGeometry relative="1" as="geometry"/> </mxCell> <mxCell id="63" value="grandparent" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="212.5" y="282.5" width="87.5" height="30" as="geometry"/> + <mxGeometry x="242.5" y="125" width="87.5" height="30" as="geometry"/> </mxCell> <mxCell id="67" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;dashed=1;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" parent="1" source="64" target="3" edge="1"> <mxGeometry relative="1" as="geometry"/> </mxCell> <mxCell id="64" value="parent" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="237.5" y="317.5" width="50" height="30" as="geometry"/> + <mxGeometry x="267.5" y="160" width="50" height="30" as="geometry"/> </mxCell> <mxCell id="68" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;dashed=1;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" parent="1" source="65" target="5" edge="1"> <mxGeometry relative="1" as="geometry"/> </mxCell> <mxCell id="65" value="current" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="252.5" y="357.5" width="55" height="30" as="geometry"/> + <mxGeometry x="282.5" y="200" width="55" height="30" as="geometry"/> </mxCell> <mxCell id="70" value="Parent RedBlackTree" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> <mxGeometry x="140" y="40" width="150" height="30" as="geometry"/> </mxCell> - <mxCell id="71" value="When rotating" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=14;fontFamily=Garamond;" parent="1" vertex="1"> - <mxGeometry x="147.5" y="240" width="102.5" height="30" as="geometry"/> - </mxCell> - <mxCell id="73" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" vertex="1" parent="1"> - <mxGeometry x="240" y="105" width="20" height="20" as="geometry"/> - </mxCell> - <mxCell id="90" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;dashed=1;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" edge="1" parent="1" source="74" target="73"> - <mxGeometry relative="1" as="geometry"/> - </mxCell> - <mxCell id="74" value="newNode" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=14;fontFamily=Garamond;" vertex="1" parent="1"> - <mxGeometry x="290" y="80" width="70" height="30" as="geometry"/> - </mxCell> - <mxCell id="76" style="edgeStyle=none;html=1;entryX=0.66;entryY=0.8;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" edge="1" parent="1" source="75" target="47"> - <mxGeometry relative="1" as="geometry"/> - </mxCell> - <mxCell id="75" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" vertex="1" parent="1"> - <mxGeometry x="100" y="105" width="20" height="20" as="geometry"/> - </mxCell> - <mxCell id="77" style="edgeStyle=none;html=1;entryX=0.45;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" edge="1" parent="1" target="81"> + <mxCell id="91" value="" style="edgeStyle=none;html=1;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" edge="1" parent="1" source="43" target="82"> <mxGeometry relative="1" as="geometry"> - <mxPoint x="110" y="115" as="sourcePoint"/> + <mxPoint x="131.25" y="120" as="sourcePoint"/> + <mxPoint x="103.75" y="160.0000000000001" as="targetPoint"/> </mxGeometry> </mxCell> - <mxCell id="79" style="edgeStyle=none;html=1;entryX=0.7;entryY=0.5;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" edge="1" parent="1" source="81" target="83"> - <mxGeometry relative="1" as="geometry"/> - </mxCell> - <mxCell id="80" style="edgeStyle=none;html=1;entryX=0.4;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;fontSize=14;fontFamily=Garamond;" edge="1" parent="1" source="81" target="82"> - <mxGeometry relative="1" as="geometry"/> - </mxCell> - <mxCell id="81" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" vertex="1" parent="1"> - <mxGeometry x="130" y="145" width="20" height="20" as="geometry"/> - </mxCell> <mxCell id="82" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" vertex="1" parent="1"> - <mxGeometry x="160" y="185" width="20" height="20" as="geometry"/> - </mxCell> - <mxCell id="83" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" vertex="1" parent="1"> - <mxGeometry x="100" y="185" width="20" height="20" as="geometry"/> - </mxCell> - <mxCell id="85" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;fontSize=14;fontFamily=Garamond;" vertex="1" parent="1"> - <mxGeometry x="40" y="185" width="20" height="20" as="geometry"/> - </mxCell> - <mxCell id="88" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.6;entryY=0.45;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;curved=1;dashed=1;fontSize=14;fontFamily=Garamond;" edge="1" parent="1" source="87" target="75"> - <mxGeometry relative="1" as="geometry"/> - </mxCell> - <mxCell id="87" value="previous" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=14;fontFamily=Garamond;" vertex="1" parent="1"> - <mxGeometry x="147.5" y="80" width="62.5" height="30" as="geometry"/> + <mxGeometry x="92.5" y="150" width="20" height="20" as="geometry"/> </mxCell> </root> </mxGraphModel>
--- a/Paper/master_paper.tex Tue Jan 30 14:32:19 2024 +0900 +++ b/Paper/master_paper.tex Tue Jan 30 15:40:33 2024 +0900 @@ -143,9 +143,6 @@ また，それを用いたレプリケーションやガベージコレクション， バックアップ機能の設計に関する考察を行った． - - - \chapter{軽量継続を基本とする言語CbC} Continuation based C(CbC)\cite{cbcllvm,cbc}はC言語の下位言語であり， @@ -331,7 +328,7 @@ 3行目の\texttt{\#impl as}はInterfaceの実装を記述する際に指定する． implの直後に実装したいInterfaceの仕様を指定し， asの後ろには実装の型名を記述する． -であるから，\texttt{\#impl "Queue.h" as "SingleLinkedQueue.h"}は仕様Queueの実装を +そのため，\texttt{\#impl "Queue.h" as "SingleLinkedQueue.h"}は仕様Queueの実装を SingleLinkedQueueとして定義することになる． 7行目の\texttt{createSingleLinkedQueue}はSingleLinkedQueueのコンストラクタを定義しており， DataGearのアロケートやCodeGearを保持するメソッドの初期化を行っている． @@ -400,8 +397,6 @@ それぞれのノードの役割は図\ref{fig:rbtree-def}のように示される． rootはRedBlackTreeの全てのノードを参照できる親ツリーのルートノードを指す． 読み込み中のノードはcurrentで指されており，追加するノードをnewNodeで表している． -previousは木を操作する以前の木を保持するノードであり， -これにより非破壊的な操作を可能とする． また，RedBlackTreeは挿入，更新，削除の際に木の回転操作を行う． その際，起点のノード(current)に対して親のノードをparent，祖父母のノードをgrandparentで指す． 8行目のnodeStackは木の操作時，木を辿るために使用するスタックである． @@ -420,6 +415,10 @@ \section{ALLOCATE} +DataGearをアロケートする際は図\ref{src:SingleLinkedQueue.cbc}の15行目にあるように， +\texttt{singleLinkedQueue->top = new Element();}のような形でnewキーワードを用いる． + + \lstinputlisting[label=src:allocate.h, caption=ALLOCATEの定義]{src/allocate.h} \chapter{GearsFileSystem}
--- a/mindmaps/gears_fs_db.mm Tue Jan 30 14:32:19 2024 +0900 +++ b/mindmaps/gears_fs_db.mm Tue Jan 30 15:40:33 2024 +0900 @@ -319,6 +319,9 @@ <node TEXT="ほとんどアクセスされないデータはGC対象から除く" ID="ID_285170374" CREATED="1699858262921" MODIFIED="1699858318515"/> </node> <node TEXT="Copyによってreplicationの作成が可能になる" ID="ID_572465203" CREATED="1701690510698" MODIFIED="1701690536500"/> +<node TEXT="ALLOCATE" ID="ID_1376691662" CREATED="1706594900483" MODIFIED="1706594903677"> +<node TEXT="" ID="ID_530570235" CREATED="1706594904365" MODIFIED="1706594904365"/> +</node> </node> <node TEXT="incrementalなTreeのcopy" ID="ID_1492567121" CREATED="1699869669939" MODIFIED="1699869692257"> <node TEXT="後からcommitできるかも" ID="ID_1849438115" CREATED="1699869742980" MODIFIED="1699869754391"/> @@ -400,7 +403,7 @@ </node> <node TEXT="評価方法" POSITION="right" ID="ID_1979397312" CREATED="1699850131177" MODIFIED="1699850137060"/> <node TEXT="章立て" POSITION="left" ID="ID_378600647" CREATED="1699848424709" MODIFIED="1706520588455" HGAP_QUANTITY="8 pt" VSHIFT_QUANTITY="-117 pt"> -<node TEXT="要旨" ID="ID_1862870052" CREATED="1705571598152" MODIFIED="1705571620770"> +<node TEXT="要旨" FOLDED="true" ID="ID_1862870052" CREATED="1705571598152" MODIFIED="1705571620770"> <node TEXT="CbCでGearsOSを開発している" ID="ID_1596447160" CREATED="1705571621398" MODIFIED="1705571639432"/> <node TEXT="OSの重要な機能の一つにファイルシステムがある" ID="ID_1812705807" CREATED="1705571640078" MODIFIED="1705571676397"> <node TEXT="プロセス管理やデータの保持" ID="ID_1002371513" CREATED="1705636979706" MODIFIED="1705636992169"/> @@ -423,6 +426,7 @@ <node TEXT="無いと" ID="ID_1503773801" CREATED="1705637772905" MODIFIED="1705637780271"> <node TEXT="不要なオブジェクトの解放漏れが発生" ID="ID_147194106" CREATED="1705638014648" MODIFIED="1705638069085"/> <node TEXT="フラグメンテーションが解決されない" ID="ID_376737325" CREATED="1705638069954" MODIFIED="1705638222328"/> +<node TEXT="メモリリーク" ID="ID_270293339" CREATED="1706590458024" MODIFIED="1706590461626"/> </node> </node> <node TEXT="バックアップ，レプリケーション，GCを実装したい" ID="ID_209049582" CREATED="1705636465798" MODIFIED="1705636493249"/>