Mercurial > hg > Papers > 2024 > matac-master
view mindmaps/gears_fs_db.mm @ 51:bc69a109778c
png to pdf
| author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 30 Jan 2024 19:51:40 +0900 |
| parents | 0cea940227c4 |
| children | 886c8902f16e |
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="1706520588455" 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="別ContextへのCopy" POSITION="right" ID="ID_1256969896" CREATED="1706608691732" MODIFIED="1706610433076"> <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="Contextキュー" ID="ID_441803002" CREATED="1706610609324" MODIFIED="1706610615562"/> <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> <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の種類" ID="ID_1746770811" CREATED="1704695739812" MODIFIED="1704696582051"> <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="1704696594363"> <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は併用される" 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によるレプリケーション" 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> <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="1701696321975" HGAP_QUANTITY="29 pt" VSHIFT_QUANTITY="134.25 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="1703315085575"> <node TEXT="ikkiさんの研究" ID="ID_557379148" CREATED="1704630869165" MODIFIED="1704630876474"/> <node TEXT="DataGearManager" ID="ID_521285238" CREATED="1705646099321" MODIFIED="1705646107853"> <node TEXT="" ID="ID_1859471968" CREATED="1705646108176" MODIFIED="1705646108176"/> </node> <node TEXT="分散ファイルシステムのトポロジー形成" ID="ID_1837705741" CREATED="1704631962837" MODIFIED="1704631974676"/> <node TEXT="Christieを用いている" ID="ID_703384422" CREATED="1704631982827" MODIFIED="1704631995001"/> </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="実装" POSITION="left" ID="ID_1462455862" CREATED="1706417525408" MODIFIED="1706520562138"> <node TEXT="CopyRedBlackTreeの実装" FOLDED="true" ID="ID_1619882257" CREATED="1701697553803" MODIFIED="1706520562137" VSHIFT_QUANTITY="-4.5 pt"> <node TEXT="実装方法" 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）" 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="コピーのアルゴリズム" ID="ID_64994373" CREATED="1703491215841" MODIFIED="1703491223454"> <node TEXT="アルゴリズム" ID="ID_972208221" CREATED="1699849518269" MODIFIED="1699849522647"> <node TEXT="Stackを使う" 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="左側を深さ優先で辿る" ID="ID_239741561" CREATED="1699849525266" MODIFIED="1699849604742"> <node TEXT="子にcurrentを付け替えて親をnodeStackにpush" ID="ID_1852624670" CREATED="1706417608144" MODIFIED="1706417658172"/> <node TEXT="nodeStackはcurrentより以前のノードを持つ" ID="ID_304892775" CREATED="1706417633577" MODIFIED="1706417700399"/> <node TEXT="allocateした新しいnodeはinputStackにpush" ID="ID_749123856" CREATED="1706418475694" MODIFIED="1706418497889"/> </node> <node TEXT="アロケートしたノードは別のContext上に作る" 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方向に木を戻る" 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="コード説明" 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 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> <node TEXT="動作確認" ID="ID_793097790" CREATED="1706419438278" MODIFIED="1706419442565"> <node TEXT="テストケース" ID="ID_596576048" CREATED="1706420024765" MODIFIED="1706420029622"/> </node> <node TEXT="証明のしやすさについて" 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> <node TEXT="評価" 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> </node> </map>