Mercurial > hg > Papers > 2024 > matac-master
view mindmaps/gears_fs_db.mm @ 61:e7961c306d28
DGM
| author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 06 Feb 2024 18:57:11 +0900 |
| parents | 6c5965c3539e |
| children | f293f6b6da96 |
line wrap: on
line source
<map version="freeplane 1.9.8"> <!--To view this file, download free mind mapping software Freeplane from https://www.freeplane.org --> <node TEXT="GearsOS上のファイルシステムとDBの信頼性(仮)" FOLDED="false" ID="ID_452131666" CREATED="1610381621610" MODIFIED="1707115980864" STYLE="oval"> <font SIZE="18"/> <hook NAME="MapStyle" zoom="0.8"> <properties edgeColorConfiguration="#808080ff,#ff0000ff,#0000ffff,#00ff00ff,#ff00ffff,#00ffffff,#7c0000ff,#00007cff,#007c00ff,#7c007cff,#007c7cff,#7c7c00ff" associatedTemplateLocation="template:/standard-1.6-noEdgeColor.mm" fit_to_viewport="false"/> <map_styles> <stylenode LOCALIZED_TEXT="styles.root_node" STYLE="oval" UNIFORM_SHAPE="true" VGAP_QUANTITY="24 pt"> <font SIZE="24"/> <stylenode LOCALIZED_TEXT="styles.predefined" POSITION="right" STYLE="bubble"> <stylenode LOCALIZED_TEXT="default" ID="ID_207122690" COLOR="#000000" STYLE="fork"> <arrowlink SHAPE="CUBIC_CURVE" COLOR="#000000" WIDTH="2" TRANSPARENCY="200" DASH="" FONT_SIZE="9" FONT_FAMILY="SansSerif" DESTINATION="ID_207122690" STARTARROW="DEFAULT" ENDARROW="NONE"/> <font NAME="SansSerif" SIZE="10" BOLD="false" ITALIC="false"/> <richcontent CONTENT-TYPE="plain/auto" TYPE="DETAILS"/> <richcontent TYPE="NOTE" CONTENT-TYPE="plain/auto"/> </stylenode> <stylenode LOCALIZED_TEXT="defaultstyle.details"/> <stylenode LOCALIZED_TEXT="defaultstyle.attributes"> <font SIZE="9"/> </stylenode> <stylenode LOCALIZED_TEXT="defaultstyle.note" COLOR="#000000" BACKGROUND_COLOR="#ffffff" TEXT_ALIGN="LEFT"/> <stylenode LOCALIZED_TEXT="defaultstyle.floating"> <edge STYLE="hide_edge"/> <cloud COLOR="#f0f0f0" SHAPE="ROUND_RECT"/> </stylenode> <stylenode LOCALIZED_TEXT="defaultstyle.selection" BACKGROUND_COLOR="#4e85f8" BORDER_COLOR_LIKE_EDGE="false" BORDER_COLOR="#4e85f8"/> </stylenode> <stylenode LOCALIZED_TEXT="styles.user-defined" POSITION="right" STYLE="bubble"> <stylenode LOCALIZED_TEXT="styles.topic" COLOR="#18898b" STYLE="fork"> <font NAME="Liberation Sans" SIZE="10" BOLD="true"/> </stylenode> <stylenode LOCALIZED_TEXT="styles.subtopic" COLOR="#cc3300" STYLE="fork"> <font NAME="Liberation Sans" SIZE="10" BOLD="true"/> </stylenode> <stylenode LOCALIZED_TEXT="styles.subsubtopic" COLOR="#669900"> <font NAME="Liberation Sans" SIZE="10" BOLD="true"/> </stylenode> <stylenode LOCALIZED_TEXT="styles.important" ID="ID_3752836"> <icon BUILTIN="yes"/> <arrowlink COLOR="#003399" TRANSPARENCY="255" DESTINATION="ID_3752836"/> </stylenode> </stylenode> <stylenode LOCALIZED_TEXT="styles.AutomaticLayout" POSITION="right" STYLE="bubble"> <stylenode LOCALIZED_TEXT="AutomaticLayout.level.root" COLOR="#000000" STYLE="oval" SHAPE_HORIZONTAL_MARGIN="10 pt" SHAPE_VERTICAL_MARGIN="10 pt"> <font SIZE="18"/> </stylenode> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,1" COLOR="#0033ff"> <font SIZE="16"/> </stylenode> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,2" COLOR="#00b439"> <font SIZE="14"/> </stylenode> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,3" COLOR="#990000"> <font SIZE="12"/> </stylenode> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,4" COLOR="#111111"> <font SIZE="10"/> </stylenode> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,5"/> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,6"/> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,7"/> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,8"/> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,9"/> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,10"/> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,11"/> </stylenode> </stylenode> </map_styles> </hook> <node TEXT="Gears OS" FOLDED="true" POSITION="right" ID="ID_1060626979" CREATED="1699848393025" MODIFIED="1702111913149" HGAP_QUANTITY="-5.5 pt" VSHIFT_QUANTITY="-72.75 pt"> <node TEXT="特徴" ID="ID_943482341" CREATED="1702111230723" MODIFIED="1702111233987"> <node TEXT="metaGear" ID="ID_160728835" CREATED="1702111234234" MODIFIED="1702111815711"> <node TEXT="データの整合性" ID="ID_1532293232" CREATED="1702111816103" MODIFIED="1702111830986"/> <node TEXT="資源管理" ID="ID_820593070" CREATED="1702111831179" MODIFIED="1702111834866"/> </node> <node TEXT="Context" ID="ID_447263401" CREATED="1702111711616" MODIFIED="1702111713867"> <node TEXT="プロセスに相当" ID="ID_119342897" CREATED="1702111732662" MODIFIED="1702111736239"/> <node TEXT="実行するCG, 使用するDG全てを持つ" ID="ID_1243433858" CREATED="1702111736575" MODIFIED="1702111762536"/> </node> <node TEXT="3種類のGearsOS" ID="ID_1110454361" CREATED="1702111776755" MODIFIED="1702111782168"> <node TEXT="GearsOS" ID="ID_1417588174" CREATED="1702111873653" MODIFIED="1702111876220"> <node TEXT="ユーザーレベルタスクマネジメントの実装を目的とする" ID="ID_916197337" CREATED="1702112069451" MODIFIED="1702112079145"/> <node TEXT="CbC実装" ID="ID_939823586" CREATED="1702112086168" MODIFIED="1702112090340"/> <node TEXT="本研究のメイン対象" ID="ID_179232110" CREATED="1702112096195" MODIFIED="1702112110097"/> </node> <node TEXT="GearsAgda" ID="ID_1260602460" CREATED="1702111876582" MODIFIED="1702111879424"> <node TEXT="Agda実装" ID="ID_1598980937" CREATED="1702112014204" MODIFIED="1702112017570"/> <node TEXT="形式手法による証明を目的とする" ID="ID_1299519318" CREATED="1702112017959" MODIFIED="1702112029698"/> </node> <node TEXT="CbC_x.v6" ID="ID_473963560" CREATED="1702111879786" MODIFIED="1702112199760"> <node TEXT="スタンドアロンOSの開発を目的とする" ID="ID_1891291526" CREATED="1702112042696" MODIFIED="1702112054326"/> </node> </node> <node TEXT="信頼性の保証を目的としている" ID="ID_489283513" CREATED="1702111964176" MODIFIED="1702111972169"/> <node TEXT="interface" ID="ID_1090553760" CREATED="1705044283721" MODIFIED="1705044286729"> <node TEXT="モジュール化の仕組み" ID="ID_1650605077" CREATED="1705044424301" MODIFIED="1705044435039"> <node TEXT="Javaのクラスのような仕組み" ID="ID_1592717534" CREATED="1705044987112" MODIFIED="1705045006109"/> <node TEXT="使用するDGとCGをまとめる" ID="ID_616289115" CREATED="1705045011571" MODIFIED="1705045022968"/> </node> <node TEXT="DGの構造とCGの型の集合を定義する" ID="ID_613772826" CREATED="1705044331294" MODIFIED="1705044457429"/> <node TEXT="APIがCGで表現される" ID="ID_1438000127" CREATED="1705044643957" MODIFIED="1705044655030"/> <node TEXT="仕様と実装を分けて記述する" ID="ID_447965145" CREATED="1705044468383" MODIFIED="1705044490619"> <node TEXT="仕様の定義方法" ID="ID_382365488" CREATED="1705045039309" MODIFIED="1705045049695"/> <node TEXT="実装の定義方法" ID="ID_710439475" CREATED="1705045050343" MODIFIED="1705045054967"/> </node> <node TEXT="interface->methodで呼び出せる" ID="ID_717163611" CREATED="1705044776612" MODIFIED="1705044788098"/> <node TEXT="code next" ID="ID_966484010" CREATED="1705044813010" MODIFIED="1705044818116"/> <node TEXT="..." ID="ID_267004486" CREATED="1705044819091" MODIFIED="1705044978009"/> <node TEXT="implementの型定義" ID="ID_1147136141" CREATED="1705658008073" MODIFIED="1705658014391"/> </node> </node> <node TEXT="ファイルシステムとDB" ID="ID_1884932719" CREATED="1699849849835" MODIFIED="1699849855383"> <node TEXT="RedBlackTreeを基本構造とする" ID="ID_224748942" CREATED="1699849885632" MODIFIED="1699849902671"/> <node TEXT="user interface" ID="ID_1064201171" CREATED="1702117030490" MODIFIED="1702117056047"> <node TEXT="学部の時のやつ" ID="ID_1607825727" CREATED="1702117042878" MODIFIED="1702117046968"/> </node> <node TEXT="複数のreplicationを持てていない" ID="ID_787621439" CREATED="1699849855878" MODIFIED="1699849873297"/> <node TEXT="GCがない" ID="ID_1300729095" CREATED="1699849873756" MODIFIED="1699849878570"> <node TEXT="RustのようなGCを持たないシステムも存在する" ID="ID_417147063" CREATED="1701692764078" MODIFIED="1701692773562"> <node TEXT="GCなくても良いのでは？という疑問が生まれる" ID="ID_660130313" CREATED="1701692778839" MODIFIED="1701692788086"/> <node TEXT="CbR?" ID="ID_1404954258" CREATED="1701692790720" MODIFIED="1701692795814"/> </node> </node> <node TEXT="RedBlackTreeのコピーによって" ID="ID_116893075" CREATED="1699849908039" MODIFIED="1699849924661"> <node TEXT="replication作成" ID="ID_1170481289" CREATED="1699849924973" MODIFIED="1699849930140"/> <node TEXT="GC" ID="ID_1741645302" CREATED="1699849930484" MODIFIED="1699849933881"> <node TEXT="Copying GC" ID="ID_937412490" CREATED="1699850770149" MODIFIED="1699850779042"/> </node> <node TEXT="replicationとGCを同一システムで実現する利点は？" ID="ID_184373863" CREATED="1701692556651" MODIFIED="1701692583435"> <node TEXT="今の所GCするとそれをreplicationとしても扱えるという感じ" ID="ID_214758450" CREATED="1701692591670" MODIFIED="1701692621085"/> <node TEXT="逆に、分ける意味がないのか" ID="ID_587144816" CREATED="1701692621555" MODIFIED="1701692633777"/> <node TEXT="同時にできるのであればその方が効率良い" ID="ID_298223735" CREATED="1701692637636" MODIFIED="1701692696469"/> </node> </node> </node> <node TEXT="CbC" ID="ID_740206957" CREATED="1701695838712" MODIFIED="1701695841654"> <node TEXT="Cの下位言語" ID="ID_1949462311" CREATED="1702109769687" MODIFIED="1702109804650"> <node TEXT="CのLLVMに変更を加えている" ID="ID_591487528" CREATED="1702110861488" MODIFIED="1702110890767"/> </node> <node TEXT="処理の単位 CodeGear" ID="ID_1551166772" CREATED="1702109805037" MODIFIED="1702109818187"> <node TEXT="DataGearが入力される" ID="ID_1020316470" CREATED="1702110084628" MODIFIED="1702110125371"> <node TEXT="inputDataGear" ID="ID_1437736688" CREATED="1702110190302" MODIFIED="1702110196899"/> </node> <node TEXT="DataGearを出力する" ID="ID_1796772165" CREATED="1702110099792" MODIFIED="1702110112391"> <node TEXT="outputDataGear" ID="ID_1734410453" CREATED="1702110197415" MODIFIED="1702110202862"/> </node> <node TEXT="CodeGearをDataGearの一種と捉えることも可能" ID="ID_1871025096" CREATED="1702110136840" MODIFIED="1702110151771"/> </node> <node TEXT="データの単位 DataGear" ID="ID_771276269" CREATED="1702109818490" MODIFIED="1702109832058"> <node TEXT="構造体で表現される" ID="ID_870047835" CREATED="1702110827132" MODIFIED="1702110833094"/> <node TEXT="" ID="ID_1157018642" CREATED="1702110833322" MODIFIED="1702110833322"/> </node> <node TEXT="ノーマルレベルとメタレベルの切り分け" ID="ID_1583866878" CREATED="1702109839193" MODIFIED="1702109847067"/> <node TEXT="__code" ID="ID_1535719892" CREATED="1702109980407" MODIFIED="1702109984940"/> <node TEXT="gotoによる軽量継続" ID="ID_1041460941" CREATED="1702109847380" MODIFIED="1702109854199"> <node TEXT="call stackを持たない" ID="ID_1868821185" CREATED="1702109894715" MODIFIED="1702109901816"/> <node TEXT="LLVMのsetjmpとlongjmp" ID="ID_1689168618" CREATED="1702109904182" MODIFIED="1702110048454"/> <node TEXT="tail callっぽい" ID="ID_1025227356" CREATED="1702110686327" MODIFIED="1702110691940"> <node TEXT="tailcall忘れた時はここをみる" ID="ID_1334629625" CREATED="1702110692360" MODIFIED="1702110703733"> <node TEXT="http://www.nct9.ne.jp/m_hiroi/func/abcerl02.html" ID="ID_1874667604" CREATED="1702110709856" MODIFIED="1702110709856" LINK="http://www.nct9.ne.jp/m_hiroi/func/abcerl02.html"/> </node> <node TEXT="再帰呼び出しして、返り値をそのまま返す" ID="ID_801162080" CREATED="1702110795575" MODIFIED="1702110816945"/> </node> </node> <node TEXT="現状" ID="ID_1373082100" CREATED="1702110955427" MODIFIED="1702110958434"> <node TEXT="http://www.cr.ie.u-ryukyu.ac.jp/hg/CbC/CbC_llvm/" ID="ID_797243399" CREATED="1702111010437" MODIFIED="1702111010437" LINK="http://www.cr.ie.u-ryukyu.ac.jp/hg/CbC/CbC_llvm/"/> <node TEXT="clang llvm 18.0.0" ID="ID_762978767" CREATED="1702111146287" MODIFIED="1702111160675"/> </node> <node TEXT="関連" ID="ID_416590732" CREATED="1703308253194" MODIFIED="1703308255811"> <node TEXT="AspectJ" ID="ID_1370782910" CREATED="1703308256121" MODIFIED="1703308259210"> <node TEXT="リフレクション" ID="ID_96315745" CREATED="1703308259675" MODIFIED="1703308340272"/> <node TEXT="CbCはリフレクションしやすい" ID="ID_1614355873" CREATED="1703308341219" MODIFIED="1703308355429"/> <node TEXT="metaを書ける部分がリフレクション" ID="ID_195416108" CREATED="1703308357434" MODIFIED="1703308372053"/> <node TEXT="AOP" ID="ID_770917898" CREATED="1703308974828" MODIFIED="1703308978370"> <node TEXT="アスペクト志向プログラミング" ID="ID_1702082447" CREATED="1703308978573" MODIFIED="1703308988562"/> </node> <node TEXT="記法" ID="ID_582319031" CREATED="1703308588273" MODIFIED="1703308590240"> <node TEXT="@Aspect" ID="ID_201521343" CREATED="1703308932008" MODIFIED="1703308939119"/> <node TEXT="Advice" ID="ID_1105819991" CREATED="1703308939534" MODIFIED="1703308947617"/> <node TEXT="PointCut" ID="ID_1656105549" CREATED="1703308947870" MODIFIED="1703308951334"/> <node TEXT="JoinPoint" ID="ID_1355814265" CREATED="1703308951712" MODIFIED="1703308972859"/> </node> </node> </node> </node> <node TEXT="i-nodeを用いたファイルシステム" ID="ID_1473698899" CREATED="1703314946289" MODIFIED="1703492949059"> <node TEXT="matacの研究" ID="ID_618829953" CREATED="1704631158641" MODIFIED="1704631166543"/> <node TEXT="i-nodeとは" ID="ID_496468764" CREATED="1705550651509" MODIFIED="1705550655963"> <node TEXT="ファイルのメタ情報" ID="ID_699874175" CREATED="1705550695362" MODIFIED="1705550701308"/> </node> <node TEXT="UIがある" ID="ID_1360221597" CREATED="1705551534208" MODIFIED="1705551536722"> <node TEXT="mkdir, ls, cd" ID="ID_332425690" CREATED="1704631167036" MODIFIED="1704632106399"/> </node> <node TEXT="非破壊RedBlackTreeで構成される" ID="ID_527215616" CREATED="1704632128347" MODIFIED="1704632244845"/> </node> </node> <node TEXT="ファイルシステム" POSITION="right" ID="ID_1877138212" CREATED="1699848400796" MODIFIED="1699848405514"> <node TEXT="可変長文字列を格納するファイル" ID="ID_1080516331" CREATED="1699849063058" MODIFIED="1699849081419"> <node TEXT="構造化されていないデータ" ID="ID_989502084" CREATED="1699854164275" MODIFIED="1699854171408"/> </node> <node TEXT="ファイルにアクセスするための名前管理" ID="ID_1768633329" CREATED="1699849081914" MODIFIED="1699849094907"> <node TEXT="linux" ID="ID_1049908119" CREATED="1699857284972" MODIFIED="1699857288270"> <node ID="ID_1495135529" CREATED="1699857288486" MODIFIED="1699857326105"><richcontent TYPE="NODE"> <html> <head> </head> <body> <p> /<font color="#000000">home/matac/ws/</font> </p> </body> </html> </richcontent> </node> </node> </node> <node TEXT="同時アクセス時の名前管理の一貫性保証" ID="ID_1592817213" CREATED="1699849095540" MODIFIED="1699849111381"/> <node TEXT="ファイルに同時に書き込まれた時の一貫性の保証は無い" ID="ID_760250864" CREATED="1699849111930" MODIFIED="1699849133659"> <node TEXT="書き込み制御のロック機構がある" ID="ID_1546654520" CREATED="1699849148263" MODIFIED="1699849162973"/> </node> </node> <node TEXT="DB" POSITION="right" ID="ID_149657016" CREATED="1699848406699" MODIFIED="1699848407993"> <node TEXT="レコード" ID="ID_1205240345" CREATED="1699849182564" MODIFIED="1699849185575"> <node TEXT="入力の属性名と型の組" ID="ID_249604408" CREATED="1699849185821" MODIFIED="1699849209586"/> </node> <node TEXT="テーブル" ID="ID_156913568" CREATED="1699849219044" MODIFIED="1699849228825"> <node TEXT="特定の属性をキーとする" ID="ID_415589337" CREATED="1699849229049" MODIFIED="1699849235367"/> </node> <node TEXT="直列化可能性" ID="ID_1355828962" CREATED="1699849247355" MODIFIED="1699849253883"> <node TEXT="Serializability" ID="ID_429588711" CREATED="1699849254710" MODIFIED="1699849318311"/> <node TEXT="複数のトランザクションが並行実行される際の処理結果の正しさを保証する基準" ID="ID_749156965" CREATED="1699849319073" MODIFIED="1699849354090"/> </node> <node TEXT="正規形" ID="ID_1482959686" CREATED="1699854183342" MODIFIED="1699854192704"/> </node> <node TEXT="ファイルシステムとDBの違い" POSITION="right" ID="ID_1607395441" CREATED="1699851419940" MODIFIED="1699851427585"> <node TEXT="データの格納形式" ID="ID_2838179" CREATED="1699851427818" MODIFIED="1699851444191"> <node TEXT="文字列かレコードか" ID="ID_6405282" CREATED="1699851446861" MODIFIED="1699851462681"/> </node> <node TEXT="データアクセス方法" ID="ID_1258040613" CREATED="1699851466951" MODIFIED="1699851472419"> <node TEXT="read, write" ID="ID_823556495" CREATED="1699851468816" MODIFIED="1699851490085"/> <node TEXT="SQL" ID="ID_1745553035" CREATED="1699851490559" MODIFIED="1699851500567"/> </node> <node TEXT="直列化可能性保証方法" ID="ID_1245227752" CREATED="1699851504126" MODIFIED="1699851516763"> <node TEXT="record, table lock" ID="ID_1269582911" CREATED="1699852009313" MODIFIED="1699852028994"/> <node TEXT="ファイルロック" ID="ID_765600991" CREATED="1699852050399" MODIFIED="1699852055041"/> </node> </node> <node TEXT="ファイルシステムとDBの追加機能" POSITION="right" ID="ID_1823247462" CREATED="1699851812550" MODIFIED="1699851823299"> <node TEXT="電源を切った時にデータが残る" ID="ID_1444181613" CREATED="1699851823510" MODIFIED="1699851836412"> <node TEXT="persistency" ID="ID_603526007" CREATED="1699851837510" MODIFIED="1699851840636"/> </node> <node TEXT="書き込めたかどうかを判定する" ID="ID_1468638907" CREATED="1699851851054" MODIFIED="1699851859966"> <node TEXT="atomic write" ID="ID_514160473" CREATED="1699851860291" MODIFIED="1699851864956"/> </node> <node TEXT="一つのノードが失われた時にデータを保護する" ID="ID_369826358" CREATED="1699851869445" MODIFIED="1699851882668"> <node TEXT="多重性" ID="ID_1986614934" CREATED="1699851883681" MODIFIED="1699851887639"/> </node> <node TEXT="複数のコピーを調停するコミット機構" ID="ID_422231006" CREATED="1699851890504" MODIFIED="1699851906965"/> </node> <node TEXT="信頼性" POSITION="right" ID="ID_696728353" CREATED="1699848408447" MODIFIED="1699848413804"> <node TEXT="向上手法" ID="ID_1020078491" CREATED="1699848491366" MODIFIED="1699848496923"> <node TEXT="証明" ID="ID_1018661667" CREATED="1699848497270" MODIFIED="1699848503341"> <node TEXT="Gears Agda" ID="ID_1165126463" CREATED="1699848504251" MODIFIED="1699848509993"/> <node TEXT="invariantを使う" ID="ID_92873298" CREATED="1699848511299" MODIFIED="1699848516818"/> </node> <node TEXT="テスト" ID="ID_853686057" CREATED="1699848525221" MODIFIED="1699848530154"/> <node TEXT="モデル検査" ID="ID_465552896" CREATED="1699848530425" MODIFIED="1699848536874"/> </node> <node TEXT="システム全体で向上させる必要がある" ID="ID_1629969942" CREATED="1699848909002" MODIFIED="1699848931988"> <node TEXT="システムの構成要素" ID="ID_677210990" CREATED="1699848935984" MODIFIED="1699848942782"> <node TEXT="アプリケーション" ID="ID_1491167091" CREATED="1699848943269" MODIFIED="1699848949144"/> <node TEXT="OS" ID="ID_419231398" CREATED="1699848949689" MODIFIED="1699848952218"/> <node TEXT="ファイルシステム" ID="ID_1950317269" CREATED="1699848952489" MODIFIED="1699849002048"/> <node TEXT="DB" ID="ID_92392900" CREATED="1699849003252" MODIFIED="1699849004419"/> <node TEXT="メモリ" ID="ID_1964952999" CREATED="1699849004786" MODIFIED="1699849010256"/> <node TEXT="SSD" ID="ID_1413092539" CREATED="1699849010790" MODIFIED="1699849015545"/> <node TEXT="分散ノード" ID="ID_1536068993" CREATED="1699849016080" MODIFIED="1699849022165"/> <node TEXT="ネットワーク" ID="ID_1088702523" CREATED="1699849022619" MODIFIED="1699849027379"/> </node> </node> <node TEXT="向上手法をシステム全体に適用したい" ID="ID_829551002" CREATED="1699850006058" MODIFIED="1699850017727"/> </node> <node TEXT="RedBlackTree" FOLDED="true" POSITION="right" ID="ID_858040690" CREATED="1699848437129" MODIFIED="1699848446060"> <node TEXT="Copy" ID="ID_76598812" CREATED="1699848476363" MODIFIED="1699848479936"> <node TEXT="単なる2分木のコピー" ID="ID_1535596989" CREATED="1699849455588" MODIFIED="1699849469353"/> <node TEXT="Stack無しで書くとおそらく結構複雑" ID="ID_527329681" CREATED="1699849470075" MODIFIED="1699857892247"/> <node TEXT="木を辿るためにStackを使う" ID="ID_788381426" CREATED="1699849561986" MODIFIED="1699849582652"> <node TEXT="コピー後に消されるので使って良い" ID="ID_1063130872" CREATED="1701690823328" MODIFIED="1701690834394"/> </node> <node TEXT="アルゴリズム" ID="ID_529312839" CREATED="1699849518269" MODIFIED="1705568929841"> <node TEXT="左側を深さ優先で辿る" ID="ID_468694757" CREATED="1699849525266" MODIFIED="1699849604742"> <node TEXT="Stack push" ID="ID_1123969398" CREATED="1699849778090" MODIFIED="1699849781012"/> </node> <node TEXT="アロケートしたノードは別のContext上に作る" ID="ID_320048499" CREATED="1699849620905" MODIFIED="1705568929840"> <node TEXT="GCのため" ID="ID_1239006804" CREATED="1699849638520" MODIFIED="1699849668501"/> <node TEXT="Copy後古いContextを消す" ID="ID_1485480555" CREATED="1699849646521" MODIFIED="1699849693755"/> <node TEXT="メモリ管理をモナドで表していることになる" ID="ID_1271994335" CREATED="1699849705089" MODIFIED="1699849715878"/> </node> <node TEXT="リーフまで降りたらroot方向に木を戻る" ID="ID_976293319" CREATED="1699849731393" MODIFIED="1699849765553"> <node TEXT="Stack pop" ID="ID_1123748609" CREATED="1699849765982" MODIFIED="1699849773214"/> <node TEXT="右側を呼び出す" ID="ID_831164108" CREATED="1699849789218" MODIFIED="1699849803550"/> </node> <node TEXT="Stackを2つ使うならば" ID="ID_472848117" CREATED="1699849785880" MODIFIED="1699850937824"> <node TEXT="全体のStack" ID="ID_315508287" CREATED="1699850965212" MODIFIED="1699858010811"> <node TEXT="originの木を辿るために使う" ID="ID_824722897" CREATED="1699858046929" MODIFIED="1699858071837"/> </node> <node TEXT="途中のStack" ID="ID_1421142933" CREATED="1699850966215" MODIFIED="1699858024318"> <node TEXT="右側を呼び出す際にそれまでの左側部分木を保持" ID="ID_929949795" CREATED="1699851138198" MODIFIED="1699858042178"/> </node> </node> </node> <node TEXT="Copy前後の同一性確認が必要" ID="ID_1150089347" CREATED="1699849956727" MODIFIED="1699849974942"/> <node TEXT="Copy中の変更" ID="ID_492731672" CREATED="1699849982760" MODIFIED="1699849992692"/> <node TEXT="毎回全てをGCするか" ID="ID_1696799143" CREATED="1699858222922" MODIFIED="1699858309153"> <node TEXT="アクセス頻度によって世代分けする" ID="ID_158787872" CREATED="1699858236610" MODIFIED="1699858248665"/> <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="newキーワード" ID="ID_530570235" CREATED="1706594904365" MODIFIED="1706595448461"> <node TEXT="ビルド時にALLOCATEマクロに変換される" ID="ID_623043043" CREATED="1706595552557" MODIFIED="1706595577359"/> <node TEXT="ノーマルレベルでDataGearをアロケートするための記法" ID="ID_362901607" CREATED="1706596365202" MODIFIED="1706596395063"> <node TEXT="Contextを直接操作しないため" ID="ID_1055024443" CREATED="1706596414453" MODIFIED="1706596425766"/> </node> </node> <node TEXT="ALLOCATEマクロ" ID="ID_346737816" CREATED="1706595448876" MODIFIED="1706595584544"> <node TEXT="ContextのDataGearを格納するヒープ領域の操作を行う" ID="ID_1958985951" CREATED="1706595584911" MODIFIED="1706595611261"/> <node TEXT="context" ID="ID_438391456" CREATED="1706595611804" MODIFIED="1706595614332"> <node TEXT="対象のコンテキスト" ID="ID_1413190219" CREATED="1706595614591" MODIFIED="1706595621981"/> </node> <node TEXT="t" ID="ID_1020756504" CREATED="1706595623941" MODIFIED="1706595625229"> <node TEXT="対象のDataGear" ID="ID_1121535546" CREATED="1706595625594" MODIFIED="1706595632821"/> </node> </node> </node> </node> <node TEXT="incrementalなTreeのcopy" ID="ID_1492567121" CREATED="1699869669939" MODIFIED="1699869692257"> <node TEXT="後からcommitできるかも" ID="ID_1849438115" CREATED="1699869742980" MODIFIED="1699869754391"/> <node TEXT="commitのシーケンスをとっておく" ID="ID_921049246" CREATED="1699869765723" MODIFIED="1699869778036"> <node TEXT="Treeとは別にオペレーションのリストがある" ID="ID_1770284118" CREATED="1699869879779" MODIFIED="1699869889686"> <node TEXT="これもcopyが必要" ID="ID_230010982" CREATED="1699869957930" MODIFIED="1699869963814"/> </node> <node TEXT="RedBlackTree with commtted operation" ID="ID_888988533" CREATED="1699869899048" MODIFIED="1699869915123"> <node TEXT="番号" ID="ID_1935233472" CREATED="1699869923512" MODIFIED="1699869928338"/> <node TEXT="insert, delete" ID="ID_1668599725" CREATED="1699869929471" MODIFIED="1699869933942"/> </node> </node> </node> <node TEXT="証明しやすい" ID="ID_1313077784" CREATED="1699849438956" MODIFIED="1699849443715"/> <node TEXT="全ての操作が最悪でもO(log n)" ID="ID_1382477887" CREATED="1699855369743" MODIFIED="1699855390827"/> <node TEXT="GearsFileSystemで用いられる重要な構造" ID="ID_1889670571" CREATED="1705393830088" MODIFIED="1705393854760"/> <node TEXT="GearsOSのRedBlackTree" ID="ID_1808262456" CREATED="1704625749056" MODIFIED="1704625759342"> <node TEXT="Tree仕様" ID="ID_247537990" CREATED="1705298991306" MODIFIED="1705299008258"> <node TEXT="Tree.h" ID="ID_1679703570" CREATED="1705299046915" MODIFIED="1705299050496"> <node TEXT="仕様の定義" ID="ID_1409400056" CREATED="1705299053969" MODIFIED="1705299066971"/> </node> </node> <node TEXT="RedBlackTree実装" ID="ID_1365581239" CREATED="1704625938387" MODIFIED="1705299021394"> <node TEXT="RedBlackTree.h" ID="ID_514994168" CREATED="1705057440091" MODIFIED="1705057447006"> <node TEXT="implの型定義ファイル" ID="ID_884167229" CREATED="1705299034323" MODIFIED="1705299041442"/> </node> </node> <node TEXT="Tree interface" ID="ID_1582061146" CREATED="1705050144077" MODIFIED="1705050161749"> <node TEXT="DG" ID="ID_1117156367" CREATED="1705050163353" MODIFIED="1705050166212"/> <node TEXT="CG" ID="ID_892070786" CREATED="1705050166599" MODIFIED="1705050168009"/> </node> </node> <node TEXT="Red-black tree(一般的な説明)" ID="ID_89990981" CREATED="1705402671067" MODIFIED="1705402684466"> <node TEXT="二分探索木" ID="ID_899325725" CREATED="1705402685486" MODIFIED="1705402941637"/> <node TEXT="ノードに赤or黒の色をつける" ID="ID_594853418" CREATED="1705402942420" MODIFIED="1705402969509"/> <node TEXT="探索，挿入，削除操作のオーダーが最悪の場合でもO(log n)" ID="ID_1352435743" CREATED="1705402694002" MODIFIED="1705402896426"/> <node TEXT="データ構造の一つ" ID="ID_1144589445" CREATED="1705402772112" MODIFIED="1705402780832"/> </node> <node TEXT="rootを保持する構造がほしい" ID="ID_1410049473" CREATED="1705991762051" MODIFIED="1705991775332"> <node TEXT="バージョンを参照するため" ID="ID_1632488340" CREATED="1705991775778" MODIFIED="1705991782869"/> </node> </node> <node TEXT="Rustの所有権" POSITION="right" ID="ID_612327915" CREATED="1704949737149" MODIFIED="1704949745661"> <node TEXT="メモリを所有する変数のスコープを抜けるとメモリも解放される" ID="ID_972875880" CREATED="1704949746103" MODIFIED="1704949765401"/> <node TEXT="スマートポインタ" ID="ID_403762806" CREATED="1704949766082" MODIFIED="1704949771866"/> </node> <node TEXT="RBTreeを用いたCopying GC" POSITION="right" ID="ID_704559305" CREATED="1699854075442" MODIFIED="1699857013558"> <node TEXT="RBTreeのコピーをする" ID="ID_541742554" CREATED="1699857015273" MODIFIED="1699857026447"/> <node TEXT="データは全てRedBlackTreeで表現される" ID="ID_1145318684" CREATED="1699857027634" MODIFIED="1699857056196"> <node TEXT="ただし、木の操作にStackを用いる" ID="ID_1170936451" CREATED="1699857056714" MODIFIED="1699857067513"/> </node> <node TEXT="木自体がオブジェクトルートになる" ID="ID_1404066066" CREATED="1699857074069" MODIFIED="1699857087072"> <node TEXT="正確なGC" ID="ID_462996564" CREATED="1699857087449" MODIFIED="1699857104930"/> </node> </node> <node TEXT="コピーのベンチマーカー" POSITION="right" ID="ID_1415317998" CREATED="1699856883382" MODIFIED="1699856891252"> <node TEXT="ある程度大きな木を用意" ID="ID_1884791368" CREATED="1699857682191" MODIFIED="1699857700584"> <node TEXT="ある程度とは" ID="ID_1182141688" CREATED="1699857704166" MODIFIED="1699857711215"/> </node> <node TEXT="単純にコピーにかかる時間を測定" ID="ID_846596778" CREATED="1699857700957" MODIFIED="1699857730588"/> <node TEXT="比較対象は？" ID="ID_963832906" CREATED="1699857731316" MODIFIED="1699857739036"/> </node> <node TEXT="ディスク上とメモリ上のデータ構造" POSITION="right" ID="ID_1874111745" CREATED="1699850217484" MODIFIED="1699850230859"> <node TEXT="同一のRedBlackTree" ID="ID_1633724271" CREATED="1699850231118" MODIFIED="1699850243142"/> <node TEXT="persistent memoryを想定" ID="ID_719479083" CREATED="1699850243592" MODIFIED="1699850261924"/> </node> <node TEXT="先行研究" POSITION="right" ID="ID_1807805275" CREATED="1699850150666" MODIFIED="1699850155227"> <node TEXT="GearsOS の分散ファイルシステム設計" ID="ID_1737093216" CREATED="1701692836825" MODIFIED="1701692838439"> <node TEXT="一木 貴裕" ID="ID_976656831" CREATED="1701692838974" MODIFIED="1701692861473"/> <node TEXT="修論" ID="ID_1407964942" CREATED="1701692861994" MODIFIED="1701692868384"/> </node> <node TEXT="Gearsos における i-node を用いた file system の設計" ID="ID_152975250" CREATED="1701692905310" MODIFIED="1701692912376"> <node TEXT="又吉 雄斗" ID="ID_537151466" CREATED="1701692914641" MODIFIED="1701692923391"/> <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> </node> <node TEXT="評価方法" POSITION="right" ID="ID_1979397312" CREATED="1699850131177" MODIFIED="1699850137060"/> <node TEXT="erasure coding" POSITION="right" ID="ID_1412038732" CREATED="1706607173301" MODIFIED="1706607177606"/> <node TEXT="章立て" POSITION="left" ID="ID_378600647" CREATED="1699848424709" MODIFIED="1706520588455" HGAP_QUANTITY="8 pt" VSHIFT_QUANTITY="-117 pt"> <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"/> </node> <node TEXT="FSはGearsOSでも設計実装がされている" ID="ID_213132822" CREATED="1705571677040" MODIFIED="1705571697134"> <node TEXT="i-node directory system" ID="ID_581456334" CREATED="1705637000846" MODIFIED="1705637008111"/> <node TEXT="DataGearManagerを用いた分散ファイルシステム" ID="ID_428549418" CREATED="1705637008536" MODIFIED="1705637025285"/> </node> <node TEXT="FSの信頼性に関する機能がない" ID="ID_1765028343" CREATED="1705571772335" MODIFIED="1705571797140"> <node TEXT="多重性" ID="ID_1553948100" CREATED="1705637129978" MODIFIED="1705637132992"> <node TEXT="バックアップ" ID="ID_1196024079" CREATED="1705571952708" MODIFIED="1705571955785"/> <node TEXT="レプリケーション" ID="ID_693585860" CREATED="1705571956248" MODIFIED="1705571960387"/> </node> <node TEXT="一貫性" ID="ID_465667054" CREATED="1705637437811" MODIFIED="1705637441519"> <node TEXT="トランザクション" ID="ID_793477817" CREATED="1705637062637" MODIFIED="1705637066804"/> </node> </node> <node TEXT="メモリ管理機能もない" ID="ID_582237136" CREATED="1705636449288" MODIFIED="1705636458393"> <node TEXT="GC" ID="ID_504953107" CREATED="1705636459464" MODIFIED="1705636461733"/> <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"/> <node TEXT="実装したい機能は基本的にRedBlackTreeのコピー操作となる" ID="ID_401787855" CREATED="1705636494950" MODIFIED="1705636514799"/> <node TEXT="しかし現状のRedBlackTreeにCopyの機能がない" ID="ID_1368822025" CREATED="1705636520674" MODIFIED="1705636536996"/> <node TEXT="追加機能を実装するにあたりCopyRBTreeが必要" ID="ID_104907185" CREATED="1705571941402" MODIFIED="1705571990070"/> <node TEXT="CopyRedBlackTreeを実装した" ID="ID_832191870" CREATED="1705571803160" MODIFIED="1705571938071"/> <node TEXT="CopyRedBlackTreeの設計，構築，考察を述べる" ID="ID_1223240785" CREATED="1705636541738" MODIFIED="1705636559635"/> </node> <node TEXT="Gears OSのファイルシステムとDB" ID="ID_446325287" CREATED="1701690660393" MODIFIED="1701690902283"> <node TEXT="重要なシステムの障害" ID="ID_780032066" CREATED="1704365424619" MODIFIED="1704365554685"> <node TEXT="例" ID="ID_561763413" CREATED="1704365743851" MODIFIED="1704365747240"> <node TEXT="全銀システム" ID="ID_380458549" CREATED="1704365488518" MODIFIED="1704365500548"> <node TEXT="https://www.zengin-net.jp/announcement/pdf/announcement_20231201.pdf" ID="ID_622498163" CREATED="1704365947486" MODIFIED="1704365947486" LINK="https://www.zengin-net.jp/announcement/pdf/announcement_20231201.pdf"/> </node> <node TEXT="ANAの国内線システム" ID="ID_227546985" CREATED="1704365556083" MODIFIED="1704366884696"> <node TEXT="https://www.anahd.co.jp/group/pr/202304/notification-2.html?_gl=1*1h2jfg0*_ga*MTkwMjE0OTIwNC4xNjgwOTIwMTUx*_ga_32F297W9WL*MTY4MDkyMDI2My4xLjEuMTY4MDkyMDMwNy4wLjAuMA.." ID="ID_918028332" CREATED="1704366735088" MODIFIED="1704366735088" LINK="https://www.anahd.co.jp/group/pr/202304/notification-2.html?_gl=1*1h2jfg0*_ga*MTkwMjE0OTIwNC4xNjgwOTIwMTUx*_ga_32F297W9WL*MTY4MDkyMDI2My4xLjEuMTY4MDkyMDMwNy4wLjAuMA.."/> </node> <node TEXT="電子決済システム" ID="ID_271892958" CREATED="1704365579825" MODIFIED="1704366979311"> <node TEXT="https://www.glory.co.jp/news/detail/id=2017" ID="ID_650733639" CREATED="1704367245326" MODIFIED="1704367245326" LINK="https://www.glory.co.jp/news/detail/id=2017"/> </node> </node> <node TEXT="これらは社会に多大な影響を与える" ID="ID_1496226551" CREATED="1704365759256" MODIFIED="1704365779957"/> <node TEXT="よってシステムの高い信頼性が求められる" ID="ID_1365357344" CREATED="1704365780499" MODIFIED="1704365831219"/> </node> <node TEXT="システム全体の信頼性を上げたい" ID="ID_1572843196" CREATED="1703313460915" MODIFIED="1703313713692"> <node TEXT="システムにあるさまざまな要素" ID="ID_1198542652" CREATED="1704365155193" MODIFIED="1704365166358"> <node TEXT="アプリケーション" ID="ID_727581223" CREATED="1704365166793" MODIFIED="1704365223650"/> <node TEXT="OS" ID="ID_1417760159" CREATED="1704365224002" MODIFIED="1704365225602"/> <node TEXT="ファイルシステム" ID="ID_153728143" CREATED="1704365226160" MODIFIED="1704365231311"/> <node TEXT="DB" ID="ID_323366858" CREATED="1704365231782" MODIFIED="1704365232994"/> <node TEXT="メモリ" ID="ID_402756754" CREATED="1704365233331" MODIFIED="1704365236964"/> <node TEXT="SSD" ID="ID_404429414" CREATED="1704365237202" MODIFIED="1704365243718"/> <node TEXT="分散ノード" ID="ID_1628174426" CREATED="1704365244457" MODIFIED="1704365249457"/> <node TEXT="ネットワーク" ID="ID_1337491308" CREATED="1704365250196" MODIFIED="1704365253472"/> </node> <node TEXT="全体の信頼性を上げる必要がある" ID="ID_355799274" CREATED="1704365894036" MODIFIED="1704365915131"/> </node> <node TEXT="ファイルシステムとDBの信頼性を考える" ID="ID_1355454563" CREATED="1703313715002" MODIFIED="1703313723643"> <node TEXT="システムにおいて重要なFSとDBの信頼性を保証したい" ID="ID_1811829647" CREATED="1704365294814" MODIFIED="1704365332688"/> </node> <node TEXT="ファイルシステムとは" ID="ID_1898416034" CREATED="1703313727821" MODIFIED="1703313734372"/> <node TEXT="DBとは" ID="ID_101598045" CREATED="1703313734729" MODIFIED="1703313737449"/> <node TEXT="ファイルシステムとDBの違い" ID="ID_1786247161" CREATED="1703313740484" MODIFIED="1703313748867"/> <node TEXT="ファイルシステムとDBが持つ追加機能" ID="ID_1094923931" CREATED="1703313749849" MODIFIED="1703313784209"/> <node TEXT="GearsOSを使って実現する" ID="ID_646654551" CREATED="1703313787540" MODIFIED="1703313833292"/> <node TEXT="信頼性を向上する手法" ID="ID_578834327" CREATED="1703313866689" MODIFIED="1703313878304"/> <node TEXT="GearsOSのファイルシステムとDBの現状" ID="ID_90571671" CREATED="1703313901390" MODIFIED="1703313918619"/> <node TEXT="RedBlackTreeのコピーの実装" ID="ID_227598094" CREATED="1703313929273" MODIFIED="1703313941132"/> </node> <node TEXT="軽量継続を基本とする言語CbC" ID="ID_1037072660" CREATED="1701690246173" MODIFIED="1703311032386"> <node TEXT="軽量継続を基本とする言語CbC" ID="ID_1137662194" CREATED="1704620254613" MODIFIED="1704620265899"> <node TEXT="Cの下位言語" ID="ID_367988382" CREATED="1704620272383" MODIFIED="1704620280501"/> <node TEXT="軽量継続を基本とする" ID="ID_772545453" CREATED="1704620285878" MODIFIED="1704620291664"/> </node> <node TEXT="Gearの概念" ID="ID_1818389006" CREATED="1703307708710" MODIFIED="1704622216143"/> <node TEXT="gotoによる軽量継続" ID="ID_726882949" CREATED="1703307895880" MODIFIED="1703307911540"/> <node TEXT="CodeGearの記述例" ID="ID_1731637915" CREATED="1703307784821" MODIFIED="1703307887307"/> </node> <node TEXT="信頼性の保証を目的としたGearsOS" ID="ID_1315567458" CREATED="1701692210913" MODIFIED="1703311040671"> <node TEXT="3種類のGearsOS" ID="ID_1326415213" CREATED="1703309744902" MODIFIED="1703309750565"> <node TEXT="Gears Agda" ID="ID_1385168402" CREATED="1705044105795" MODIFIED="1705044111649"/> <node TEXT="Gears OS" ID="ID_1367848198" CREATED="1705044112079" MODIFIED="1705044114581"/> <node TEXT="CbC_x.v6" ID="ID_323899306" CREATED="1705044116042" MODIFIED="1705044124351"/> </node> <node TEXT="メタ処理を記述するmetaGear" FOLDED="true" ID="ID_1666892566" CREATED="1703309692742" MODIFIED="1703309713823"> <node TEXT="ノーマルレベルとメタレベルの切り分け" ID="ID_719507396" CREATED="1703308470210" MODIFIED="1703308478844"/> <node TEXT="CbCによって容易に切り分け可能" ID="ID_1803106515" CREATED="1704785297162" MODIFIED="1704785306308"/> </node> <node TEXT="全てのGearを参照するContext" FOLDED="true" ID="ID_91888278" CREATED="1703309731224" MODIFIED="1705052148391"> <node TEXT="全てのCodeGear, DataGearの参照を持つ" ID="ID_816175749" CREATED="1704777710835" MODIFIED="1704777722631"/> <node TEXT="従来OSのプロセスに相当する概念" ID="ID_485427631" CREATED="1704777731086" MODIFIED="1704777739954"/> <node TEXT="Contextにも種類がある" ID="ID_309360319" CREATED="1704787077056" MODIFIED="1704787082791"/> <node TEXT="Gearの概念ではmetaDataGearにあたる" ID="ID_1983036538" CREATED="1704777794150" MODIFIED="1704777819739"/> <node TEXT="ノーマルレベルから直接参照されない" ID="ID_280262393" CREATED="1704777824342" MODIFIED="1705052148391"/> <node TEXT="metaCodeGearから参照される" ID="ID_526551168" CREATED="1704777838132" MODIFIED="1704778973371"/> <node TEXT="ノーマルレベルから直接参照されるとどうなるか" ID="ID_1998855779" CREATED="1704778991437" MODIFIED="1704779001760"> <node TEXT="ノーマルレベルでメタレベルを書き換えることが可能になる" ID="ID_517717354" CREATED="1704779027195" MODIFIED="1704779037558"/> <node TEXT="メタレベルを分けた意味がなくなる" ID="ID_1293544989" CREATED="1704779038072" MODIFIED="1704779046632"/> </node> <node TEXT="Contextを含めたGear遷移" ID="ID_1897519980" CREATED="1704779305504" MODIFIED="1704779324312"/> </node> <node TEXT="モジュール化の仕組みinterface" FOLDED="true" ID="ID_979914453" CREATED="1705044283721" MODIFIED="1705045105599"> <node TEXT="モジュール化の仕組み" ID="ID_1323690074" CREATED="1705044424301" MODIFIED="1705044435039"> <node TEXT="Javaのクラスのような仕組み" ID="ID_515246380" CREATED="1705044987112" MODIFIED="1705045006109"/> <node TEXT="使用するDGとCGをまとめる" ID="ID_1867289776" CREATED="1705045011571" MODIFIED="1705045022968"/> </node> <node TEXT="DGの構造とCGの型の集合を定義する" ID="ID_1609812236" CREATED="1705044331294" MODIFIED="1705044457429"/> <node TEXT="APIがCGで表現される" ID="ID_1744335025" CREATED="1705044643957" MODIFIED="1705044655030"/> <node TEXT="仕様と実装を分けて記述する" ID="ID_1841677639" CREATED="1705044468383" MODIFIED="1705044490619"> <node TEXT="仕様の定義方法" ID="ID_554139727" CREATED="1705045039309" MODIFIED="1705045049695"/> <node TEXT="実装の定義方法" ID="ID_1845996229" CREATED="1705045050343" MODIFIED="1705045054967"/> </node> <node TEXT="interface->methodで呼び出せる" ID="ID_1716944029" CREATED="1705044776612" MODIFIED="1705044788098"/> <node TEXT="code next" ID="ID_493231617" CREATED="1705044813010" MODIFIED="1705044818116"/> <node TEXT="..." ID="ID_1146219373" CREATED="1705044819091" MODIFIED="1705044978009"> <node TEXT="Contextから値を取り出す" ID="ID_1241470700" CREATED="1705049804204" MODIFIED="1705049810183"/> <node TEXT="次のCodeGearのinputDataGearは不定である" ID="ID_574655805" CREATED="1705049810780" MODIFIED="1705049835325"/> </node> <node TEXT="実装" ID="ID_1727927338" CREATED="1705050293688" MODIFIED="1705050297703"> <node TEXT="#impl as" ID="ID_1508543884" CREATED="1705052044177" MODIFIED="1705052048026"> <node TEXT="interfaceの実装を書く場合に記述する" ID="ID_1568057342" CREATED="1705055994617" MODIFIED="1705056004662"/> <node TEXT="implの後ろに実装したいinterface名する" ID="ID_138244749" CREATED="1705056004945" MODIFIED="1705056045083"/> <node TEXT="asの後ろに実装の型名を記述する" ID="ID_238410525" CREATED="1705056022794" MODIFIED="1705056041152"/> <node TEXT="昔はInterfaceという記述だった" ID="ID_1185735068" CREATED="1705396899032" MODIFIED="1705396911079"/> <node TEXT="清水によって追加された記法" ID="ID_1097652467" CREATED="1705397130415" MODIFIED="1705397143359"/> </node> <node TEXT="create" ID="ID_115012523" CREATED="1705052063509" MODIFIED="1705052066013"> <node TEXT="コンストラクタである" ID="ID_690330298" CREATED="1705056555895" MODIFIED="1705056577812"/> <node TEXT="newでアロケートする" ID="ID_663793410" CREATED="1705056567012" MODIFIED="1705056582003"> <node TEXT="実際にはメタレベルで処理される" ID="ID_521085278" CREATED="1705056608304" MODIFIED="1705056635911"/> </node> </node> <node TEXT="queue->" ID="ID_1223273790" CREATED="1705052048517" MODIFIED="1705052055499"> <node TEXT="C_" ID="ID_1002337273" CREATED="1705052125563" MODIFIED="1705052140851"/> <node TEXT="enumでCodeGearを指す" ID="ID_722629480" CREATED="1705057162117" MODIFIED="1705057195759"/> </node> <node TEXT="CodeGearの実装を以下に記述する" ID="ID_766959044" CREATED="1705057211644" MODIFIED="1705057226837"/> <node TEXT="SingleLinkedQueue.h" ID="ID_626185032" CREATED="1705052116061" MODIFIED="1705052122797"> <node TEXT="implementの型定義ファイル" ID="ID_1696501093" CREATED="1705057355651" MODIFIED="1705057369742"/> </node> <node TEXT="return必要？" ID="ID_368470184" CREATED="1705391830441" MODIFIED="1705391835590"/> </node> </node> <node TEXT="GearsOSのRedBlackTree" ID="ID_594513732" CREATED="1705400358246" MODIFIED="1705400364641"/> <node TEXT="ALLOCの説明" ID="ID_957488458" CREATED="1706417138929" MODIFIED="1706417138929"/> </node> <node TEXT="GearsOSのファイルシステムとDB(現状の話" ID="ID_667012992" CREATED="1701694178540" MODIFIED="1705549429213"> <node TEXT="GearsOSのファイルシステムとDB" ID="ID_188577314" CREATED="1704630094596" MODIFIED="1705549436675"> <node TEXT="ファイルシステムはOSの重要な機能である" ID="ID_46805604" CREATED="1704630103040" MODIFIED="1704630119191"/> <node TEXT="分散ファイルシステムとi-nodeを用いたファイルシステムが存在する" ID="ID_1509553363" CREATED="1704630119858" MODIFIED="1704630152926"/> </node> <node TEXT="DataGearManagerによる分散ファイルシステム" ID="ID_540180010" CREATED="1703315001066" MODIFIED="1703315085575"> <node TEXT="ikkiさんの研究" ID="ID_404932730" CREATED="1704630869165" MODIFIED="1704630876474"/> <node TEXT="分散ファイルシステムのトポロジー形成" ID="ID_807263501" CREATED="1704631962837" MODIFIED="1704631974676"/> <node TEXT="Christieを用いている" ID="ID_1388003233" CREATED="1704631982827" MODIFIED="1704631995001"/> </node> <node TEXT="i-nodeを用いたファイルシステム" ID="ID_1851664363" CREATED="1703314946289" MODIFIED="1703492949059"> <node TEXT="matacの研究" ID="ID_179513787" CREATED="1704631158641" MODIFIED="1704631166543"/> <node TEXT="mkdir, ls, cd" ID="ID_1106903899" CREATED="1704631167036" MODIFIED="1704632106399"/> <node TEXT="非破壊RedBlackTree" ID="ID_262332331" CREATED="1701696133124" MODIFIED="1704630442271"/> <node TEXT="非破壊RedBlackTreeで構成される" ID="ID_113040530" CREATED="1704632128347" MODIFIED="1704632244845"/> <node TEXT="ディスク上とメモリ上のデータ構造" ID="ID_683338430" CREATED="1701696165502" MODIFIED="1701696179372"/> <node TEXT="RedBlackTreeのトランザクション" ID="ID_1088328123" CREATED="1701696247760" MODIFIED="1702112463420" HGAP_QUANTITY="14.75 pt" VSHIFT_QUANTITY="3.75 pt"/> </node> </node> <node TEXT="GearsFileSystemにおけるGCとレプリケーション" ID="ID_1092227909" CREATED="1701690558237" MODIFIED="1705569492385" HGAP_QUANTITY="16.25 pt" VSHIFT_QUANTITY="-1.5 pt"> <node TEXT="ファイルシステムの信頼性" FOLDED="true" ID="ID_200982245" CREATED="1704630258973" MODIFIED="1706091519737"> <node TEXT="信頼性に関する追加機能" ID="ID_1574949535" CREATED="1704630312069" MODIFIED="1704630320377"/> <node TEXT="GCやレプリケーションの機能がない" ID="ID_878946385" CREATED="1704630323433" MODIFIED="1704632961588"/> <node TEXT="実装するためにはデータのCopyが必要" ID="ID_822351907" CREATED="1704630337081" MODIFIED="1706091519737"/> <node TEXT="現状はTreeにCopyがない" ID="ID_65833123" CREATED="1704630383271" MODIFIED="1704630397371"/> <node TEXT="Copyを実装したい" ID="ID_1314300132" CREATED="1704632535428" MODIFIED="1704632976417"/> </node> <node TEXT="GCの種類" FOLDED="true" ID="ID_1746770811" CREATED="1704695739812" MODIFIED="1706686162814"> <node TEXT="CopyingGCとは" ID="ID_344664264" CREATED="1704692777863" MODIFIED="1704692782352"> <node TEXT="正確なGC" ID="ID_267216671" CREATED="1704696904268" MODIFIED="1704696908732"/> <node TEXT="ヒープ領域をFrom領域とTo領域に分割" ID="ID_1262852949" CREATED="1704711856815" MODIFIED="1704711932146"/> <node TEXT="ルートから参照できるオブジェクトをFrom領域からTo領域にコピーする" ID="ID_1311182649" CREATED="1704711932613" MODIFIED="1704711957213"/> </node> <node TEXT="Reference counting GC" ID="ID_776539806" CREATED="1704696590166" MODIFIED="1706686162814"> <node TEXT="オブジェクトの被参照数を表すカウンタを用いる" ID="ID_166536665" CREATED="1704710714477" MODIFIED="1704710852447"/> <node TEXT="被参照数が0になった時オブジェクトが解放される" ID="ID_1678718232" CREATED="1704711836498" MODIFIED="1704711854290"/> <node TEXT="循環参照をGCできない" ID="ID_1787181256" CREATED="1706091526719" MODIFIED="1706091542945"/> </node> <node TEXT="Mark \& Sweep GC" ID="ID_715438606" CREATED="1704696594768" MODIFIED="1704696598757"> <node TEXT="マークフェーズとスイープフェーズからなる" ID="ID_1584128194" CREATED="1704710119330" MODIFIED="1704710167419"/> <node TEXT="マークフェーズ" ID="ID_393316688" CREATED="1704710141321" MODIFIED="1704710158148"> <node TEXT="生きているオブジェクト全てにマークをつける" ID="ID_684669159" CREATED="1704710178984" MODIFIED="1704710191749"/> </node> <node TEXT="スイープフェーズ" ID="ID_1823266942" CREATED="1704710168764" MODIFIED="1704710173540"> <node TEXT="マークがつけられなかったオブジェクトを回収する" ID="ID_1569463715" CREATED="1704710220250" MODIFIED="1704710369400"/> </node> </node> </node> <node TEXT="GCは併用される" FOLDED="true" ID="ID_1496671439" CREATED="1704696631667" MODIFIED="1704696640285"> <node TEXT="一般的にGCは組み合わせで使われる" ID="ID_1275851809" CREATED="1704776562321" MODIFIED="1704776594813"/> <node TEXT="例えば世代別GC" ID="ID_1572156993" CREATED="1704776595339" MODIFIED="1704776711350"/> <node TEXT="メジャーGCでMark & Sweep GC" ID="ID_118548516" CREATED="1704776713708" MODIFIED="1704776746730"/> <node TEXT="マイナーでCopying GC" ID="ID_332663516" CREATED="1704776747163" MODIFIED="1704776761598"/> <node TEXT="それぞれのGCの利点を享受できる" ID="ID_704438541" CREATED="1704776762298" MODIFIED="1704776776709"/> </node> <node TEXT="Rustのスマートポインタ" ID="ID_881149259" CREATED="1704696608959" MODIFIED="1704696615328"/> <node TEXT="CopyingGCを用いる" FOLDED="true" ID="ID_1639428535" CREATED="1704692768575" MODIFIED="1705569492385"> <node TEXT="どのように利用するか" ID="ID_549509034" CREATED="1704696775586" MODIFIED="1704696779463"> <node TEXT="通常のCopyingGCではヒープ領がコピーされる" ID="ID_830576894" CREATED="1704692782815" MODIFIED="1704692814222"/> <node TEXT="GearsFileSystemの場合は木をコピーする" ID="ID_1003156855" CREATED="1704692814851" MODIFIED="1704692831840"/> <node TEXT="参照しているオブジェクトは木のルートから辿れる" ID="ID_1653048898" CREATED="1704696789481" MODIFIED="1704696806177"/> <node TEXT="辿れるノードのみコピーするだけでGCになる" ID="ID_355389629" CREATED="1704696807343" MODIFIED="1704696829530"/> <node TEXT="RedBlackTreeのコピーを用いる" ID="ID_1495626047" CREATED="1704630409263" MODIFIED="1704632465291"> <node TEXT="Copy" ID="ID_1713857745" CREATED="1699848476363" MODIFIED="1699848479936"> <node TEXT="単なる2分木のコピー" ID="ID_1165724596" CREATED="1699849455588" MODIFIED="1699849469353"/> <node TEXT="Stack無しで書くとおそらく結構複雑" ID="ID_1214201745" CREATED="1699849470075" MODIFIED="1699857892247"/> <node TEXT="木を辿るためにStackを使う" ID="ID_278711519" CREATED="1699849561986" MODIFIED="1699849582652"> <node TEXT="コピー後に消されるので使って良い" ID="ID_841332618" CREATED="1701690823328" MODIFIED="1701690834394"/> </node> <node TEXT="Copy前後の同一性確認が必要" ID="ID_659073251" CREATED="1699849956727" MODIFIED="1699849974942"/> <node TEXT="Copy中の変更" ID="ID_58260128" CREATED="1699849982760" MODIFIED="1699849992692"/> <node TEXT="毎回全てをGCするか" ID="ID_1441955822" CREATED="1699858222922" MODIFIED="1699858309153"> <node TEXT="アクセス頻度によって世代分けする" ID="ID_1844124057" CREATED="1699858236610" MODIFIED="1699858248665"/> <node TEXT="ほとんどアクセスされないデータはGC対象から除く" ID="ID_279065121" CREATED="1699858262921" MODIFIED="1699858318515"/> </node> <node TEXT="Copyによってreplicationの作成が可能になる" ID="ID_1531756423" CREATED="1701690510698" MODIFIED="1701690536500"/> <node TEXT="incrementalなTreeのcopy" ID="ID_1594894473" CREATED="1699869669939" MODIFIED="1699869692257"> <node TEXT="後からcommitできるかも" ID="ID_1694113573" CREATED="1699869742980" MODIFIED="1699869754391"/> <node TEXT="commitのシーケンスをとっておく" ID="ID_251890400" CREATED="1699869765723" MODIFIED="1699869778036"> <node TEXT="Treeとは別にオペレーションのリストがある" ID="ID_1030866225" CREATED="1699869879779" MODIFIED="1699869889686"> <node TEXT="これもcopyが必要" ID="ID_247714394" CREATED="1699869957930" MODIFIED="1699869963814"/> </node> <node TEXT="RedBlackTree with commtted operation" ID="ID_118589427" CREATED="1699869899048" MODIFIED="1699869915123"> <node TEXT="番号" ID="ID_1574803424" CREATED="1699869923512" MODIFIED="1699869928338"/> <node TEXT="insert, delete" ID="ID_252146025" CREATED="1699869929471" MODIFIED="1699869933942"/> </node> </node> </node> </node> <node TEXT="RedBlackTreeは単なる2分木" ID="ID_1037813952" CREATED="1704632767323" MODIFIED="1704632780206"/> </node> </node> <node TEXT="なぜCopyingGCなのか" ID="ID_1226680678" CREATED="1704696722580" MODIFIED="1704696736347"> <node TEXT="全てのデータはRedBlackTreeに格納される" ID="ID_1096077315" CREATED="1704710451766" MODIFIED="1704710463902"> <node TEXT="(使用中のデータ)" ID="ID_55750630" CREATED="1704710470136" MODIFIED="1704710480143"/> </node> <node TEXT="木を辿れば全ての生きているオブジェクトを参照することが可能" ID="ID_1690086792" CREATED="1704710464413" MODIFIED="1704710513053"> <node TEXT="正確なGC" ID="ID_1987344082" CREATED="1704710533695" MODIFIED="1704710540754"/> <node TEXT="なのでCopyingGCを簡単に適用できる" ID="ID_1935146464" CREATED="1704710513688" MODIFIED="1704710568354"/> </node> <node TEXT="Mark & Sweep GCよりもスループットが出ると考える" ID="ID_613272796" CREATED="1704956892675" MODIFIED="1704956939092"> <node TEXT="RedBlackTreeは全てのファイルを持つため大きい" ID="ID_908438870" CREATED="1704956939482" MODIFIED="1704956974993"/> <node TEXT="参照されているノードのみをコピーするだけのCopying GCの方が相性が良い" ID="ID_502796047" CREATED="1704956975764" MODIFIED="1704957000536"/> </node> </node> <node TEXT="GC併用はしないのか" ID="ID_939269191" CREATED="1704696736711" MODIFIED="1704776977043"> <node TEXT="今回は単純な実装をしたい" ID="ID_91131104" CREATED="1704776780918" MODIFIED="1704776789505"> <node TEXT="単なる木のコピー" ID="ID_532595291" CREATED="1704776790471" MODIFIED="1704776797065"/> <node TEXT="証明のしやすさにつながる" ID="ID_297159546" CREATED="1704776798186" MODIFIED="1704776845819"/> </node> <node TEXT="併用するとバックアップやレプリケーションは別の仕組みにする必要がある" ID="ID_896411663" CREATED="1704957031261" MODIFIED="1704957059039"/> </node> <node TEXT="Rustの所有権のような仕組みにしないのか" ID="ID_110730790" CREATED="1704696742911" MODIFIED="1704954332719"> <node TEXT="単純な実装にしたい" ID="ID_1639528076" CREATED="1704955568322" MODIFIED="1704955577331"/> <node TEXT="コピーでやる方がデータの透過性を維持しやすい" ID="ID_104562515" CREATED="1704955577814" MODIFIED="1704955770934"/> <node TEXT="コピーの方がバックアップやレプリケーションも同様の仕組みで実装できる" ID="ID_1846713241" CREATED="1704955771362" MODIFIED="1704955798240"/> </node> <node TEXT="バックアップとして扱うことも可能" ID="ID_1170979330" CREATED="1704954394351" MODIFIED="1704954402539"> <node TEXT="メモリ上とディスク上のデータ構造が同一" ID="ID_1687864170" CREATED="1704955435232" MODIFIED="1704955460360"/> <node TEXT="GCで木をコピーするようにバックアップ用のコピーを作成可能" ID="ID_1027992110" CREATED="1704955460903" MODIFIED="1704955483078"/> <node TEXT="From領域をバックアップとして扱うことも考えられる" ID="ID_834146670" CREATED="1704955483744" MODIFIED="1704955507082"/> <node TEXT="RedBlackTree自体が非破壊" ID="ID_1343358619" CREATED="1704955507787" MODIFIED="1704955517941"> <node TEXT="データの履歴を持っている" ID="ID_996919473" CREATED="1704955518379" MODIFIED="1704955535054"/> <node TEXT="バージョンを持ったバックアップになる" ID="ID_813768933" CREATED="1704955535459" MODIFIED="1704955560610"/> </node> </node> </node> <node TEXT="CopyRedBlackTreeによるレプリケーション" FOLDED="true" 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"/> <node TEXT="RedBlackTreeで構成されたディレクトリシステム" ID="ID_1425337861" CREATED="1705985761147" MODIFIED="1705985786882"> <node TEXT="なのでRedBlackTreeのコピーで単純に実装できる" ID="ID_1509690636" CREATED="1705985788492" MODIFIED="1705985812755"/> </node> </node> <node TEXT="メモ" ID="ID_1983774695" CREATED="1705551362475" MODIFIED="1705551366046"> <node TEXT="i-node treeをbackup, replication, gc可能であることを書きたい" ID="ID_559931709" CREATED="1705551366386" MODIFIED="1705551399134"/> </node> <node TEXT="別Contextへのコピー" FOLDED="true" ID="ID_399369896" CREATED="1706681655595" MODIFIED="1706686153089"> <node TEXT="Contextとデータの関係" ID="ID_886743343" CREATED="1706682841186" MODIFIED="1706682863894"> <node TEXT="ContextはCode tableとData tableをそれぞれ持つ" ID="ID_21894122" CREATED="1706682868410" MODIFIED="1706682889001"/> <node TEXT="ALLOCATIONするとData tableのヒープ領域に，そのDataGear分の領域が確保される" ID="ID_1585444915" CREATED="1706682889540" MODIFIED="1706682925919"/> <node TEXT="Contextが複数ある場合" ID="ID_1471440079" CREATED="1706682969341" MODIFIED="1706682981045"> <node TEXT="ContextキューでContextが切り替えられる" ID="ID_1985467145" CREATED="1706682982216" MODIFIED="1706683001147"/> </node> </node> <node TEXT="別Contextにコピーするとよい" ID="ID_1876841083" CREATED="1706681659200" MODIFIED="1706682209127"/> <node TEXT="別Contextでなかった場合" ID="ID_560608920" CREATED="1706681671376" MODIFIED="1706681678666"> <node TEXT="gcの場合" ID="ID_923875693" CREATED="1706682243505" MODIFIED="1706682247016"> <node TEXT="コピーがContextのヒープ領域を共有してしまう" ID="ID_413051853" CREATED="1706681679033" MODIFIED="1706681732770"/> <node TEXT="GCにおけるコンパクションがしづらい" ID="ID_1314661404" CREATED="1706681733377" MODIFIED="1706681761877"/> </node> <node TEXT="レプリケーションの場合" ID="ID_527622333" CREATED="1706682256823" MODIFIED="1706682272029"> <node TEXT="別ノードでは別のContextが動いている" ID="ID_1828450915" CREATED="1706682266069" MODIFIED="1706682286844"/> <node TEXT="なのでそもそもレプリケーションできない" ID="ID_1204637406" CREATED="1706682287142" MODIFIED="1706682340929"/> </node> </node> <node TEXT="別にすると" ID="ID_1006310926" CREATED="1706681763993" MODIFIED="1706681768496"> <node TEXT="gcの場合" ID="ID_1630524955" CREATED="1706681768979" MODIFIED="1706681890584"> <node TEXT="ヒープ領域が完全に分けられる" ID="ID_1953838327" CREATED="1706681878410" MODIFIED="1706681904308"/> <node TEXT="前のContextから切り替えることでFrom To入れ替えができる" ID="ID_1098995506" CREATED="1706681905021" MODIFIED="1706682233872"/> </node> <node TEXT="レプリケーションの場合" ID="ID_1369269729" CREATED="1706682237947" MODIFIED="1706682320750"> <node TEXT="レプリケーションできるようになる" ID="ID_194880813" CREATED="1706682321617" MODIFIED="1706682348973"/> </node> </node> <node TEXT="バックアップの場合" ID="ID_747644249" CREATED="1706683084193" MODIFIED="1706683089437"> <node TEXT="ディスクを仮想的な別Contextのヒープ領域として捉える" ID="ID_875066740" CREATED="1706683089813" MODIFIED="1706683124532"/> <node TEXT="リストアは" ID="ID_640003323" CREATED="1706683937466" MODIFIED="1706683941551"> <node TEXT="" ID="ID_1334338074" CREATED="1706684991839" MODIFIED="1706684991839"/> </node> </node> </node> </node> <node TEXT="CopyRedBlackTreeの実装" ID="ID_1054164602" CREATED="1706417542077" MODIFIED="1706417548592"> <node TEXT="実装方法" ID="ID_1491466672" CREATED="1705735668943" MODIFIED="1705735677711"> <node TEXT="Tree InterfaceのAPIにCopyを追加する" ID="ID_535524915" CREATED="1705735678228" MODIFIED="1705735715335"/> <node TEXT="RedBlackTreeのコピーとして実装する" ID="ID_878630835" CREATED="1706417169892" MODIFIED="1706417179625"/> </node> <node TEXT="copyの使用方法" ID="ID_712774381" CREATED="1706429162944" MODIFIED="1706429182896"/> <node TEXT="アルゴリズム" ID="ID_1706301205" CREATED="1706424874581" MODIFIED="1706424880284"/> <node TEXT="それぞれのCodeGearの説明" ID="ID_1262953034" CREATED="1706424910753" MODIFIED="1706424918004"/> <node TEXT="コード説明" ID="ID_1503273394" CREATED="1706424889067" MODIFIED="1706424905285"/> </node> <node TEXT="評価" ID="ID_1053436711" CREATED="1702112499515" MODIFIED="1702112509004"> <node TEXT="信頼性" ID="ID_1221084016" CREATED="1702289777950" MODIFIED="1702289781581"> <node TEXT="モデル検査とAgdaによる実装" ID="ID_1438858883" CREATED="1702289781790" MODIFIED="1702289794818"/> <node TEXT="copyの信頼性は？" ID="ID_1159602829" CREATED="1706417738889" MODIFIED="1706417747056"/> <node TEXT="RedBlackTreeの信頼性は定理証明する" ID="ID_12400408" CREATED="1706417749855" MODIFIED="1706417762632"/> </node> <node TEXT="実装" ID="ID_484711889" CREATED="1706520630447" MODIFIED="1706520633279"> <node TEXT="&ALLOCATION" ID="ID_1081895195" CREATED="1706521406980" MODIFIED="1706521412797"/> </node> </node> <node TEXT="今後" ID="ID_87524419" CREATED="1702112509364" MODIFIED="1702112512270"/> </node> <node TEXT="修論で言いたいこと" POSITION="right" ID="ID_1194781583" CREATED="1701690732709" MODIFIED="1706679669392" HGAP_QUANTITY="15.5 pt" VSHIFT_QUANTITY="-0.75 pt"> <node TEXT="RedBlackTreeのCopyでreplicationによる信頼性の向上とGCの仕組みを実装した" ID="ID_729318951" CREATED="1701690742376" MODIFIED="1701691473760"/> <node TEXT="ファイルシステムとDBを同一システムとして実装してしまおうという試みの一部" ID="ID_803529790" CREATED="1701693180112" MODIFIED="1701696299725"/> </node> <node TEXT="DataGearManagerによる分散ファイルシステム" POSITION="right" ID="ID_1005780153" CREATED="1703315001066" MODIFIED="1706679671263" HGAP_QUANTITY="10.25 pt" VSHIFT_QUANTITY="-8.25 pt"> <node TEXT="ikkiさんの研究" ID="ID_557379148" CREATED="1704630869165" MODIFIED="1704630876474"/> <node TEXT="Christieを参考にしている" ID="ID_703384422" CREATED="1704631982827" MODIFIED="1707116511976"/> <node TEXT="DataGearManager" ID="ID_521285238" CREATED="1705646099321" MODIFIED="1705646107853"> <node TEXT="DataGearのPoolをノード間で接続" ID="ID_1859471968" CREATED="1705646108176" MODIFIED="1707116184443"/> <node TEXT="Take，Putでデータの取得追加を行う" ID="ID_1980726218" CREATED="1707116184919" MODIFIED="1707116258104"/> </node> <node TEXT="TopologyManager" ID="ID_1529059839" CREATED="1707116524108" MODIFIED="1707116543452"> <node TEXT="CGのトポロジー形成を行う" ID="ID_265704638" CREATED="1707117106960" MODIFIED="1707117117959"/> </node> <node TEXT="Socketによる通信の仕組み" ID="ID_593040069" CREATED="1707116002953" MODIFIED="1707116014736"/> <node TEXT="分散ファイルシステムのトポロジー形成" ID="ID_1837705741" CREATED="1704631962837" MODIFIED="1704631974676"/> </node> <node TEXT="実行したCodeGearを出力する仕組みが欲しい" POSITION="right" ID="ID_566018654" CREATED="1706690111878" MODIFIED="1706690124375"> <node TEXT="毎回printfするの面倒" ID="ID_402999765" CREATED="1706690125223" MODIFIED="1706690134582"/> </node> <node TEXT="別ContextへのCopy" FOLDED="true" POSITION="right" ID="ID_1256969896" CREATED="1706608691732" MODIFIED="1706691074851" HGAP_QUANTITY="14.75 pt" VSHIFT_QUANTITY="21 pt"> <node TEXT="新たにヒープ領域を確保することによりコンパクションされる" ID="ID_1570751579" CREATED="1706610433391" MODIFIED="1706610495922"> <node TEXT="少なくとも論理的には" ID="ID_1203172749" CREATED="1706610530004" MODIFIED="1706610535897"/> </node> <node TEXT="別ノードにコピーすることが可能になる" ID="ID_18132759" CREATED="1706610497553" MODIFIED="1706610550820"> <node TEXT="別ノードは別のContextを持っているため" ID="ID_261769933" CREATED="1706610552438" MODIFIED="1706610561888"/> </node> <node TEXT="無尽蔵に大きくなるデータ" ID="ID_371220284" CREATED="1706610724283" MODIFIED="1706610735719"> <node TEXT="ある地点で分離可能であるように区切る必要がある" ID="ID_31321201" CREATED="1706610736028" MODIFIED="1706610750038"/> <node TEXT="仮想的に別ContextのData tableを用意" ID="ID_517308151" CREATED="1706610750494" MODIFIED="1706610780803"> <node TEXT="Data table同士を接続してデータを持続させる" ID="ID_109885431" CREATED="1706610791990" MODIFIED="1706610969823"/> </node> </node> <node TEXT="ディスクへの書き込み" ID="ID_1313978495" CREATED="1706611103173" MODIFIED="1706611107617"> <node TEXT="リストア方法" ID="ID_1201150664" CREATED="1706611422642" MODIFIED="1706611428892"> <node TEXT="Contextヒープとディスク上のデータ形式がbit単位で一致していればコピーするだけで済む......" ID="ID_1094786351" CREATED="1706611580254" MODIFIED="1706611621038"/> </node> <node TEXT="リストアのタイミング" ID="ID_484916387" CREATED="1706611430637" MODIFIED="1706611800129"> <node TEXT="特定のバージョンをリストアしたい" ID="ID_1574892385" CREATED="1706684999835" MODIFIED="1706685007273"/> <node TEXT="現在のバージョンを別バージョンに切り替える時は書き込みの一貫性を確保する必要がある" ID="ID_1994863120" CREATED="1706685007752" MODIFIED="1706685069287"> <node TEXT="書き込みが行われている際にリストアしてしまうと書き込み先がずれてしまう" ID="ID_610035180" CREATED="1706685087059" MODIFIED="1706685104511"/> </node> </node> </node> <node TEXT="Contextキュー" ID="ID_1047057445" CREATED="1706679759621" MODIFIED="1706679771873"> <node TEXT="Contextが順次参照される" ID="ID_1047250748" CREATED="1706679793618" MODIFIED="1706679812635"/> <node TEXT="単純にコピーするだけであればコピー元->コピー先の実行でよい" ID="ID_1030846182" CREATED="1706679825615" MODIFIED="1706679860026"> <node TEXT="read replicaは問題ない" ID="ID_759103130" CREATED="1706679997994" MODIFIED="1706680004839"/> </node> <node TEXT="writeノードを増やす場合は？" ID="ID_398140096" CREATED="1706680011118" MODIFIED="1706680102288"> <node TEXT="トランザクション管理が必要" ID="ID_934097308" CREATED="1706680102768" MODIFIED="1706680740608"/> <node TEXT="ACID" ID="ID_668349518" CREATED="1706680871405" MODIFIED="1706680874016"/> </node> </node> <node TEXT="説明" ID="ID_1566388365" CREATED="1706681655595" MODIFIED="1706681658850"> <node TEXT="Contextとデータの関係" ID="ID_1454555004" CREATED="1706682841186" MODIFIED="1706682863894"> <node TEXT="ContextはCode tableとData tableをそれぞれ持つ" ID="ID_1112158379" CREATED="1706682868410" MODIFIED="1706682889001"/> <node TEXT="ALLOCATIONするとData tableのヒープ領域に，そのDataGear分の領域が確保される" ID="ID_1845935915" CREATED="1706682889540" MODIFIED="1706682925919"/> <node TEXT="Contextが複数ある場合" ID="ID_1202004282" CREATED="1706682969341" MODIFIED="1706682981045"> <node TEXT="ContextキューでContextが切り替えられる" ID="ID_1938589889" CREATED="1706682982216" MODIFIED="1706683001147"/> </node> </node> <node TEXT="別Contextにコピーするとよい" ID="ID_497217227" CREATED="1706681659200" MODIFIED="1706682209127"/> <node TEXT="別Contextでなかった場合" ID="ID_814918893" CREATED="1706681671376" MODIFIED="1706681678666"> <node TEXT="gcの場合" ID="ID_1798592055" CREATED="1706682243505" MODIFIED="1706682247016"> <node TEXT="コピーがContextのヒープ領域を共有してしまう" ID="ID_754213404" CREATED="1706681679033" MODIFIED="1706681732770"/> <node TEXT="GCにおけるコンパクションがしづらい" ID="ID_638713116" CREATED="1706681733377" MODIFIED="1706681761877"/> </node> <node TEXT="レプリケーションの場合" ID="ID_1498053901" CREATED="1706682256823" MODIFIED="1706682272029"> <node TEXT="別ノードでは別のContextが動いている" ID="ID_662166719" CREATED="1706682266069" MODIFIED="1706682286844"/> <node TEXT="なのでそもそもレプリケーションできない" ID="ID_381677948" CREATED="1706682287142" MODIFIED="1706682340929"/> </node> </node> <node TEXT="別にすると" ID="ID_652852110" CREATED="1706681763993" MODIFIED="1706681768496"> <node TEXT="gcの場合" ID="ID_239429338" CREATED="1706681768979" MODIFIED="1706681890584"> <node TEXT="ヒープ領域が完全に分けられる" ID="ID_1991432215" CREATED="1706681878410" MODIFIED="1706681904308"/> <node TEXT="前のContextから切り替えることでFrom To入れ替えができる" ID="ID_1287374124" CREATED="1706681905021" MODIFIED="1706682233872"/> </node> <node TEXT="レプリケーションの場合" ID="ID_1842008675" CREATED="1706682237947" MODIFIED="1706682320750"> <node TEXT="レプリケーションできるようになる" ID="ID_1747513810" CREATED="1706682321617" MODIFIED="1706682348973"/> </node> </node> <node TEXT="バックアップの場合" ID="ID_1960787415" CREATED="1706683084193" MODIFIED="1706683089437"> <node TEXT="ディスクを仮想的な別Contextのヒープ領域として捉える" ID="ID_212019334" CREATED="1706683089813" MODIFIED="1706683124532"/> <node TEXT="リストアは" ID="ID_716224417" CREATED="1706683937466" MODIFIED="1706683941551"> <node TEXT="" ID="ID_1748042011" CREATED="1706684991839" MODIFIED="1706684991839"/> </node> </node> </node> </node> <node TEXT="CopyRedBlackTreeの実装" FOLDED="true" POSITION="right" ID="ID_1875155929" CREATED="1706686273106" MODIFIED="1707115980863" HGAP_QUANTITY="29 pt" VSHIFT_QUANTITY="157.49999 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"/> <node TEXT="登場する主なCodeGear" ID="ID_1955149593" CREATED="1706934987471" MODIFIED="1706935007665"/> <node TEXT="CodeGearのおおまかな遷移" ID="ID_872667908" CREATED="1706935010066" MODIFIED="1706935017591"/> <node TEXT="実装詳細" ID="ID_1895012245" CREATED="1707013282802" MODIFIED="1707013287360"> <node TEXT="ALLOCATION" ID="ID_1410128784" CREATED="1706935157942" MODIFIED="1706935161703"> <node TEXT="3箇所でアロケーションが実行される" ID="ID_987986764" CREATED="1707013312935" MODIFIED="1707013333262"/> <node TEXT="メタでは&ALLOCATIONが呼び出される" ID="ID_1299023885" CREATED="1707013338704" MODIFIED="1707013352784"/> <node TEXT="同じContextにアロケーションしている" ID="ID_333936053" CREATED="1707013353271" MODIFIED="1707013372674"/> </node> <node TEXT="swap" ID="ID_861618575" CREATED="1707013292638" MODIFIED="1707013295916"> <node TEXT="ひとまずコピー前の木とコピー後の木を入れ替える操作をしている" ID="ID_434898110" CREATED="1707013376738" MODIFIED="1707013398965"/> <node TEXT="これはGCを想定している" ID="ID_1298895362" CREATED="1707013399773" MODIFIED="1707013407108"/> </node> </node> </node> <node TEXT="Tree InterfaceのAPIにCopyを追加する" ID="ID_746343495" CREATED="1705735678228" MODIFIED="1705735715335"> <node TEXT="tree->copy" ID="ID_1447270137" CREATED="1706690663705" MODIFIED="1706690668279"/> <node TEXT="copyの使用方法" ID="ID_1242421499" CREATED="1706429162944" MODIFIED="1706429182896"/> </node> <node TEXT="アルゴリズム" ID="ID_13939041" CREATED="1706424874581" MODIFIED="1706424880284"> <node TEXT="深さ優先探索" ID="ID_1402042091" CREATED="1706690644933" MODIFIED="1706690656698"/> <node TEXT="left側から" ID="ID_1254260732" CREATED="1706694298682" MODIFIED="1706694301659"/> <node ID="ID_1690021005" CREATED="1706707317006" MODIFIED="1706707352275"><richcontent TYPE="NODE"> <html> <head> </head> <body> <p> 単純に2分木として扱える<content ename="content"/> </p> </body> </html> </richcontent> </node> </node> <node TEXT="説明したいCodeGear" ID="ID_560487748" CREATED="1706424910753" MODIFIED="1706690491719"> <node TEXT="ALLOCATE部分" ID="ID_109587235" CREATED="1706690492043" MODIFIED="1706690497935"> <node TEXT="copyRedBlackTree" ID="ID_1627803921" CREATED="1706690548342" MODIFIED="1706690550357"/> <node TEXT="leftDown1" ID="ID_502748318" CREATED="1706690515305" MODIFIED="1706690519288"/> <node TEXT="rightDown1" ID="ID_637234507" CREATED="1706690521535" MODIFIED="1706690525673"/> </node> <node TEXT="swap部分" ID="ID_921375688" CREATED="1706690590468" MODIFIED="1706690593805"> <node TEXT="swap2" ID="ID_524874877" CREATED="1706690594880" MODIFIED="1706690620487"/> </node> </node> <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"/> <node TEXT="up" ID="ID_1479524994" CREATED="1706692662332" MODIFIED="1706692663819"/> <node TEXT="swap" ID="ID_1491257973" CREATED="1706692664212" MODIFIED="1706692666506"/> </node> <node TEXT="Allocateのタイミングは？" ID="ID_115162340" CREATED="1706694324952" MODIFIED="1706694330149"/> </node> <node TEXT="2つのStackの状態" ID="ID_1242761849" CREATED="1706690782698" MODIFIED="1706690788011"> <node TEXT="nodeStack" ID="ID_490511205" CREATED="1706690792199" MODIFIED="1706690798537"/> <node TEXT="toStack" ID="ID_623970278" CREATED="1706690798816" MODIFIED="1706690800978"/> </node> <node TEXT="ALLOCATION" ID="ID_1483360062" CREATED="1706689945370" MODIFIED="1706689948913"> <node TEXT="同じContextにコピーしている" ID="ID_392545374" CREATED="1706689949866" MODIFIED="1706689961356"/> <node TEXT="別ContextにコピーするためにはGearsに手を入れる必要がある" ID="ID_763880859" CREATED="1706689961906" MODIFIED="1706690001831"> <node TEXT="別ContextをALLOCATIONに渡す" ID="ID_1985803376" CREATED="1706690009989" MODIFIED="1706690022323"/> <node TEXT="Contextを指定するのはmetaCG" ID="ID_137198073" CREATED="1706694338887" MODIFIED="1706694354687"/> <node TEXT="Node名みたいなのが必要かも" ID="ID_540200114" CREATED="1706694364436" MODIFIED="1706694370106"> <node TEXT="CGMのポート番号とか" ID="ID_1761248908" CREATED="1706694443389" MODIFIED="1706694454281"/> </node> </node> </node> <node TEXT="test" ID="ID_1700130711" CREATED="1706690975424" MODIFIED="1706690978243"> <node TEXT="一応のテストケース" ID="ID_1423214579" CREATED="1706692239367" MODIFIED="1706692246372"> <node TEXT="ノード数" ID="ID_1964840725" CREATED="1706692262124" MODIFIED="1706692264486"> <node TEXT="3" OBJECT="java.lang.Long|3" ID="ID_1422106160" CREATED="1706692264846" MODIFIED="1706692266248"/> <node TEXT="7" OBJECT="java.lang.Long|7" ID="ID_1488274279" CREATED="1706692266663" MODIFIED="1706692268000"/> <node TEXT="6316" OBJECT="java.lang.Long|6316" ID="ID_1200028911" CREATED="1706692268482" MODIFIED="1706692382199"/> <node TEXT="6317" OBJECT="java.lang.Long|6317" ID="ID_564805681" CREATED="1706692273753" MODIFIED="1706692277339"/> </node> <node TEXT="木のパターンでやりたい" ID="ID_267932296" CREATED="1706692282451" MODIFIED="1706692290220"/> </node> </node> <node TEXT="記述時に気づいた言語バグ" ID="ID_696764717" CREATED="1706418932388" MODIFIED="1706418940900"> <node TEXT="ifにてnextを持つCGへのgotoをするとうまく変換されない" ID="ID_1841484842" CREATED="1706418941366" MODIFIED="1706418994628"/> <node TEXT="gotoする時にCGを3つ以上チェーンできない" ID="ID_694782376" CREATED="1706419095962" MODIFIED="1706419119983"> <node TEXT="tree->nodeStack->push" ID="ID_319569355" CREATED="1706419141188" MODIFIED="1706419149014"/> </node> </node> <node TEXT="実行" ID="ID_24457646" CREATED="1706691161304" MODIFIED="1706691165601"> <node TEXT="ある程度のノード数で死ぬ" ID="ID_1253513150" CREATED="1706691166430" MODIFIED="1706691176293"> <node TEXT="6317ノードで死ぬ" ID="ID_521488303" CREATED="1706691448672" MODIFIED="1706691457416"/> <node TEXT="自分のPCの場合ね" ID="ID_1439726075" CREATED="1706804928850" MODIFIED="1706804935765"/> <node TEXT="stack pushで死んでる" ID="ID_1846037284" CREATED="1706692200303" MODIFIED="1706692222314"/> </node> </node> <node TEXT="tree->rootを書き換えて，途中のノードからコピーできるみたいなの作りたい" ID="ID_1603927493" CREATED="1706692686178" MODIFIED="1706692704418"/> </node> <node TEXT="評価" FOLDED="true" 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="11パターン" ID="ID_1060583266" CREATED="1707036504432" MODIFIED="1707110133774"/> <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"/> <node TEXT="簡易的なGCが動いている" ID="ID_704013046" CREATED="1706804595729" MODIFIED="1706804604559"> <node TEXT="コンパクションはない" ID="ID_939217579" CREATED="1706804607969" MODIFIED="1706804614954"/> <node TEXT="ゴミ回収はできている" ID="ID_438397032" CREATED="1706804615468" MODIFIED="1706804622473"/> <node TEXT="GCのタイミングは任意" ID="ID_918294092" CREATED="1706804639963" MODIFIED="1706804646867"/> </node> <node TEXT="テストの信頼性は?" ID="ID_428926632" CREATED="1706804959873" MODIFIED="1706804965869"> <node TEXT="最低限この動きはできるというだけ" ID="ID_145622094" CREATED="1706804966639" MODIFIED="1706804977026"/> <node TEXT="やはり形式手法は必要" ID="ID_1575995886" CREATED="1706804978051" MODIFIED="1706804999903"/> </node> </node> <node TEXT="ノード数6317でsegmentation faultする" ID="ID_1114925075" CREATED="1706803771828" MODIFIED="1706803794161"> <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"/> <node TEXT="逆にいうとそれだけでできるのではないか" ID="ID_786333116" CREATED="1706804465061" MODIFIED="1706804472295"/> <node TEXT="swapは本当はcontextの切り替えになる" ID="ID_249775448" CREATED="1707013430414" MODIFIED="1707013442111"/> </node> <node TEXT="Copyは今の所定理証明による検証の取り組みがない" ID="ID_675344411" CREATED="1706803925820" MODIFIED="1706803957592"> <node TEXT="本当に？" ID="ID_528512336" CREATED="1706803974168" MODIFIED="1706803977559"/> </node> <node TEXT="Stackを2つ使ってしまっている" ID="ID_889084804" CREATED="1706803988558" MODIFIED="1706803997484"> <node TEXT="ただし意図的に使っているので問題ない" ID="ID_1884311787" CREATED="1706803999517" MODIFIED="1706804014274"/> <node TEXT="明示的か" ID="ID_1006194673" CREATED="1706804559088" MODIFIED="1706804564677"/> </node> <node TEXT="RedBlackTreeの持続性が確保されている" ID="ID_112618752" CREATED="1706804159260" MODIFIED="1706804178604"> <node TEXT="データの持続性が確保されている" ID="ID_1798002678" CREATED="1706804178925" MODIFIED="1706804203150"/> <node TEXT="RedBlackTreeの定理証明で信頼性の保証ができる" ID="ID_1622345824" CREATED="1706804209147" MODIFIED="1706804229389"/> </node> <node TEXT="Gearsプログラミング自体について" ID="ID_424525642" CREATED="1706804107829" MODIFIED="1706804119366"> <node TEXT="ここは書かないかもしれない" ID="ID_1637182359" CREATED="1706804119674" MODIFIED="1706804126007"/> <node TEXT="抽象化が難しかったな" ID="ID_1418365356" CREATED="1706804126380" MODIFIED="1706804276211"> <node TEXT="でも最終的にはまとまりが出た" ID="ID_532008539" CREATED="1706804872043" MODIFIED="1706804885296"/> </node> <node TEXT="言語自体のバグも結構ある" ID="ID_1604283539" CREATED="1706804276815" MODIFIED="1706804285667"/> <node TEXT="テストコードを書くのが難しいのは課題だろう" ID="ID_1712432030" CREATED="1706804412648" MODIFIED="1706804423393"> <node TEXT="書きやすい仕組みを作るだけでも研究になるだろうな" ID="ID_1529940310" CREATED="1706804425672" MODIFIED="1706804438455"/> </node> </node> <node TEXT="評価はCopy自体とそれを利用する際に関し書く" ID="ID_1931339592" CREATED="1706803834583" MODIFIED="1706803855478"> <node TEXT="それ以外はまとめと今後の課題に書く" ID="ID_1941288242" CREATED="1706803862696" MODIFIED="1706803878303"/> </node> </node> <node TEXT="まとめ" POSITION="right" ID="ID_969454179" CREATED="1706956147118" MODIFIED="1706956151175"> <node TEXT="非破壊RedBlackTreeの増大を防ぐ仕組みを構築できた" ID="ID_418966492" CREATED="1706956585170" MODIFIED="1706956610719"/> <node TEXT="" ID="ID_1469214452" CREATED="1706956615904" MODIFIED="1706956615904"/> </node> <node TEXT="今後の課題" POSITION="right" ID="ID_912711900" CREATED="1706956151544" MODIFIED="1706956155177"> <node TEXT="別コンテキストへのコピー" ID="ID_1209930854" CREATED="1706956313462" MODIFIED="1706956324424"/> <node TEXT="GearsOS全体をGCすることも考えられる" ID="ID_1250275844" CREATED="1707013490904" MODIFIED="1707013522142"/> <node TEXT="非破壊Stackの扱い" ID="ID_1644568533" CREATED="1706956401644" MODIFIED="1706956408706"> <node TEXT="freelistを作成する？" ID="ID_1571509667" CREATED="1706956417754" MODIFIED="1706956422304"/> </node> </node> <node TEXT="バックアップやGCのタイミング" FOLDED="true" POSITION="left" ID="ID_1968325106" CREATED="1705995867783" MODIFIED="1705995947002"> <node TEXT="木の操作の度にGCしていては効率が悪い" ID="ID_1270257607" CREATED="1705995886579" MODIFIED="1705995983113"> <node TEXT="システムの状態によって処理を切り替える" ID="ID_835268540" CREATED="1705995987307" MODIFIED="1705995998232"/> <node TEXT="メモリがこれくらい使われている" ID="ID_708465587" CREATED="1705996000486" MODIFIED="1705996008587"/> <node TEXT="木の高さがこれくらい" ID="ID_1934598628" CREATED="1705996009257" MODIFIED="1705996031354"/> </node> <node TEXT="なのでGCのタイミング調整が必要" ID="ID_170776289" CREATED="1705996050869" MODIFIED="1705996064159"/> <node TEXT="GCを実行するか否かを切り替える必要がある" ID="ID_1199737568" CREATED="1705996069993" MODIFIED="1705996085988"/> <node TEXT="処理を切り替える方法" ID="ID_1407643935" CREATED="1705996106051" MODIFIED="1705996112103"> <node TEXT="popWhenEmpty" ID="ID_1257912829" CREATED="1705995877759" MODIFIED="1705995885499"> <node TEXT="Stackの状態によって処理を切り替える" ID="ID_886354624" CREATED="1705995949042" MODIFIED="1705995962045"/> </node> <node TEXT="つまりContextの状態で切り替えることは可能" ID="ID_329144789" CREATED="1705996126760" MODIFIED="1705996137063"/> <node TEXT="足りないのは" ID="ID_1622130118" CREATED="1705996115915" MODIFIED="1705996119770"> <node TEXT="物理的なシステムの状態を検知する" ID="ID_1564229654" CREATED="1705996138349" MODIFIED="1705996160843"> <node TEXT="meta的" ID="ID_1276371991" CREATED="1705996165959" MODIFIED="1705996168549"/> </node> <node TEXT="木の状態を知る" ID="ID_1036632951" CREATED="1705996178150" MODIFIED="1705996183527"/> </node> </node> </node> <node TEXT="レプリケーション手法" FOLDED="true" POSITION="left" ID="ID_1667606869" CREATED="1705990967981" MODIFIED="1705990975745"> <node TEXT="bin log" ID="ID_1578494368" CREATED="1705990975951" MODIFIED="1705990978180"/> <node TEXT="WAL" ID="ID_173341311" CREATED="1705991115261" MODIFIED="1705991117448"> <node TEXT="Write Ahead Logging" ID="ID_885834048" CREATED="1705991256045" MODIFIED="1705991267446"/> <node TEXT="書き込み前にログを作成する" ID="ID_420054269" CREATED="1705991269014" MODIFIED="1705991282168"/> </node> <node TEXT="postgres" ID="ID_1145631818" CREATED="1705990978764" MODIFIED="1705991044845"> <node TEXT="ストリーミング" ID="ID_185225230" CREATED="1705991045169" MODIFIED="1705991049261"> <node TEXT="クラスタ単位のWALを使用" ID="ID_408924701" CREATED="1705991149565" MODIFIED="1705991173466"/> </node> <node TEXT="ロジカル" ID="ID_1849732950" CREATED="1705991049947" MODIFIED="1705991052987"> <node TEXT="DBやテーブル単位のWALを使用" ID="ID_978332518" CREATED="1705991174849" MODIFIED="1705991208124"/> </node> </node> </node> <node TEXT="実装" FOLDED="true" POSITION="left" ID="ID_1462455862" CREATED="1706417525408" MODIFIED="1706520562138"> <node TEXT="CopyRedBlackTreeの実装" ID="ID_1619882257" CREATED="1701697553803" MODIFIED="1706520562137" VSHIFT_QUANTITY="-4.5 pt"> <node TEXT="実装方法" FOLDED="true" ID="ID_1774988166" CREATED="1705735668943" MODIFIED="1705735677711"> <node TEXT="Tree InterfaceのAPIにCopyを追加する" ID="ID_95904284" CREATED="1705735678228" MODIFIED="1705735715335"/> <node TEXT="RedBlackTreeのコピーとして実装する" ID="ID_748405331" CREATED="1706417169892" MODIFIED="1706417179625"/> </node> <node TEXT="使い方（test）" FOLDED="true" ID="ID_952766134" CREATED="1706417138868" MODIFIED="1706417138868"> <node TEXT="Copy()にはtree以外何も渡さない" ID="ID_1081702361" CREATED="1706417367338" MODIFIED="1706417401749"> <node TEXT="何か渡すことも考えられる" ID="ID_1227095307" CREATED="1706417402206" MODIFIED="1706417409509"/> <node TEXT="GCする場合とreplicationする場合で動作を切り替えるとか" ID="ID_431028898" CREATED="1706417409901" MODIFIED="1706417421736"/> </node> </node> <node TEXT="コピーのアルゴリズム" FOLDED="true" ID="ID_64994373" CREATED="1703491215841" MODIFIED="1706691006775"> <node TEXT="アルゴリズム" ID="ID_972208221" CREATED="1699849518269" MODIFIED="1706691006775"> <node TEXT="Stackを使う" FOLDED="true" ID="ID_799370781" CREATED="1706417204202" MODIFIED="1706417282682"> <node TEXT="2つのStack" ID="ID_1829045504" CREATED="1706417283299" MODIFIED="1706417289209"> <node TEXT="nodeStack" ID="ID_651682201" CREATED="1706417210255" MODIFIED="1706417229905"> <node TEXT="From木を辿るためのStack" ID="ID_1782478294" CREATED="1706417237281" MODIFIED="1706417257704"/> </node> <node TEXT="inputStack" ID="ID_1409216675" CREATED="1706417230497" MODIFIED="1706417233217"> <node TEXT="To木にAllocationするための木" ID="ID_602717814" CREATED="1706417260099" MODIFIED="1706417273222"/> </node> </node> <node TEXT="SingleLinkedStack" ID="ID_1528506233" CREATED="1706417294502" MODIFIED="1706417299177"/> </node> <node TEXT="左側を深さ優先で辿る" FOLDED="true" ID="ID_239741561" CREATED="1699849525266" MODIFIED="1706690997244"> <node TEXT="子にcurrentを付け替えて親をnodeStackにpush" ID="ID_1852624670" CREATED="1706417608144" MODIFIED="1706417658172"/> <node TEXT="nodeStackはcurrentより以前のノードを持つ" ID="ID_304892775" CREATED="1706417633577" MODIFIED="1706690997243"/> <node TEXT="allocateした新しいnodeはinputStackにpush" ID="ID_749123856" CREATED="1706418475694" MODIFIED="1706418497889"/> </node> <node TEXT="アロケートしたノードは別のContext上に作る" FOLDED="true" ID="ID_573859973" CREATED="1699849620905" MODIFIED="1699849638042"> <node TEXT="GCのため" ID="ID_259949416" CREATED="1699849638520" MODIFIED="1699849668501"/> <node TEXT="Copy後古いContextを消す" ID="ID_1297792398" CREATED="1699849646521" MODIFIED="1699849693755"/> <node TEXT="メモリ管理をモナドで表していることになる" ID="ID_152951728" CREATED="1699849705089" MODIFIED="1699849715878"/> <node TEXT="ALLOCで別のContextに書き込むようにしたいな" ID="ID_1289215093" CREATED="1706417832741" MODIFIED="1706417849017"/> <node TEXT="別ノードに書き込むことになるのでそのままreplicationになる" ID="ID_1997482213" CREATED="1706508692481" MODIFIED="1706508711469"/> </node> <node TEXT="リーフまで降りたらroot方向に木を戻る" FOLDED="true" ID="ID_1233772087" CREATED="1699849731393" MODIFIED="1699849765553"> <node TEXT="Stack pop" ID="ID_1907664340" CREATED="1699849765982" MODIFIED="1699849773214"/> <node TEXT="右側を呼び出す" ID="ID_1658933965" CREATED="1699849789218" MODIFIED="1699849803550"/> </node> </node> </node> <node TEXT="コード説明" FOLDED="true" ID="ID_1352482727" CREATED="1704630501155" MODIFIED="1704630507416"> <node TEXT="ALLOCATEの部分" ID="ID_933840077" CREATED="1706418297855" MODIFIED="1706418365645"> <node TEXT="" ID="ID_1621850954" CREATED="1706503638877" MODIFIED="1706503638877"/> </node> <node TEXT="stackの操作" ID="ID_1586156552" CREATED="1706418375086" MODIFIED="1706418391025"> <node TEXT="結構面倒......" ID="ID_1797610218" CREATED="1706418380222" MODIFIED="1706418386258"/> </node> <node TEXT="copied flag" ID="ID_1969296096" CREATED="1706418407467" MODIFIED="1706418411865"/> <node TEXT="CodeGear数" ID="ID_1895007656" CREATED="1706419226010" MODIFIED="1706419230666"/> <node TEXT="swap" ID="ID_1623826858" CREATED="1706419333510" MODIFIED="1706419355159"> <node TEXT="木の切り替え" ID="ID_1128223367" CREATED="1706419356104" MODIFIED="1706419360642"/> </node> <node TEXT="それぞれのCodeGearの説明" ID="ID_1842361863" CREATED="1706419379317" MODIFIED="1706419389831"> <node TEXT="up" ID="ID_1622585016" CREATED="1706419390124" MODIFIED="1706419396255"/> <node TEXT="leftDown" ID="ID_1893485106" CREATED="1706419396762" MODIFIED="1706419399051"/> <node TEXT="rightDown" ID="ID_1843132193" CREATED="1706419399509" MODIFIED="1706419403818"/> <node TEXT="swap" ID="ID_11264463" CREATED="1706419404827" MODIFIED="1706419406275"/> </node> </node> <node TEXT="動作確認" FOLDED="true" ID="ID_793097790" CREATED="1706419438278" MODIFIED="1706691045584"> <node TEXT="テストケース" ID="ID_596576048" CREATED="1706420024765" MODIFIED="1706691045584"/> </node> </node> </node> <node TEXT="評価" FOLDED="true" POSITION="left" ID="ID_186645686" CREATED="1706418118012" MODIFIED="1706418120523"> <node TEXT="スタックを使ってることに関して" ID="ID_1617928125" CREATED="1706417138929" MODIFIED="1706417138929"/> <node TEXT="フラグメンテーション解消できてないことにかんして" ID="ID_912797279" CREATED="1706417138929" MODIFIED="1706417138929"/> <node TEXT="GearsFileSystemで重要なCopyの機能を実装できた" ID="ID_1040965600" CREATED="1706418258268" MODIFIED="1706418270889"/> <node TEXT="copy機能が追加されたことにより信頼性を確保する機能が実装できるようになるだろう" ID="ID_759285029" CREATED="1706424528708" MODIFIED="1706424548485"/> <node TEXT="今回は簡易的なGCに留まる" ID="ID_945220922" CREATED="1706424556818" MODIFIED="1706424564389"/> <node TEXT="ここまで動作確認はした" ID="ID_1964377761" CREATED="1706424650365" MODIFIED="1706424656184"/> <node TEXT="証明のしやすさについて" FOLDED="true" ID="ID_2776247" CREATED="1703492904417" MODIFIED="1703492910899"> <node TEXT="Stackの使用に関して" ID="ID_432827984" CREATED="1703492856041" MODIFIED="1703492863503"> <node TEXT="使用していることを明示しているので問題ない" ID="ID_203410953" CREATED="1706418581660" MODIFIED="1706418592724"/> <node TEXT="それはそれで証明する必要があるんだけども" ID="ID_1283008974" CREATED="1706418601289" MODIFIED="1706418613023"/> <node TEXT="単方向結合だからStackが必要になってる" ID="ID_375847761" CREATED="1706418656484" MODIFIED="1706418674708"/> <node TEXT="ノードを双方向結合すれば...いやむずいか" ID="ID_1860358006" CREATED="1706418675221" MODIFIED="1706418808704"/> <node TEXT="状態はある程度に限られる" ID="ID_1218545539" CREATED="1706418867539" MODIFIED="1706418877317"/> </node> </node> </node> </node> </map>