Mercurial > hg > Papers > 2024 > matac-master
view mindmaps/gears_fs_db.mm @ 28:4b5c140233f3
...
| author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 16 Jan 2024 20:24:32 +0900 |
| parents | ff89b92c159f |
| children | 92e8cd87fb2b |
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="1702111913150" 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" 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> </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="現状" ID="ID_932050028" CREATED="1703310897416" MODIFIED="1703310899956"> <node TEXT="" ID="ID_166710427" CREATED="1703310900268" MODIFIED="1703310900268"/> </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> <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" 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="1699849522647"> <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="1699849638042"> <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> <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> <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="章立て" POSITION="left" ID="ID_378600647" CREATED="1699848424709" MODIFIED="1702112473403"> <node TEXT="Gears OSのファイルシステムとDB" FOLDED="true" 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" FOLDED="true" 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> <node TEXT="GearsOSのファイルシステム(現状の話" FOLDED="true" ID="ID_667012992" CREATED="1701694178540" MODIFIED="1704630791818"> <node TEXT="GearsOSのファイルシステム" ID="ID_188577314" CREATED="1704630094596" MODIFIED="1704630099465"> <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とレプリケーション" FOLDED="true" ID="ID_1092227909" CREATED="1701690558237" MODIFIED="1704632532265" HGAP_QUANTITY="16.25 pt" VSHIFT_QUANTITY="-1.5 pt"> <node TEXT="ファイルシステムの信頼性" FOLDED="true" ID="ID_200982245" CREATED="1704630258973" MODIFIED="1704630267498"> <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="1704630382753"/> <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="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> <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="1704692777490"> <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> </node> <node TEXT="CopyRedBlackTreeの実装" FOLDED="true" ID="ID_1619882257" CREATED="1701697553803" MODIFIED="1703491075408" VSHIFT_QUANTITY="-4.5 pt"> <node TEXT="コピーのアルゴリズム" ID="ID_64994373" CREATED="1703491215841" MODIFIED="1703491223454"> <node TEXT="アルゴリズム" ID="ID_972208221" CREATED="1699849518269" MODIFIED="1699849522647"> <node TEXT="左側を深さ優先で辿る" ID="ID_239741561" CREATED="1699849525266" MODIFIED="1699849604742"> <node TEXT="Stack push" ID="ID_1718409210" CREATED="1699849778090" MODIFIED="1699849781012"/> </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> <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 TEXT="Stackを2つ使うならば" ID="ID_804128791" CREATED="1699849785880" MODIFIED="1699850937824"> <node TEXT="全体のStack" ID="ID_1465604948" CREATED="1699850965212" MODIFIED="1699858010811"> <node TEXT="originの木を辿るために使う" ID="ID_1918769190" CREATED="1699858046929" MODIFIED="1699858071837"/> </node> <node TEXT="途中のStack" ID="ID_1149999446" CREATED="1699850966215" MODIFIED="1699858024318"> <node TEXT="右側を呼び出す際にそれまでの左側部分木を保持" ID="ID_225633027" CREATED="1699851138198" MODIFIED="1699858042178"/> </node> </node> </node> </node> <node TEXT="コード説明" ID="ID_1352482727" CREATED="1704630501155" MODIFIED="1704630507416"/> <node TEXT="証明のしやすさについて" ID="ID_2776247" CREATED="1703492904417" MODIFIED="1703492910899"> <node TEXT="Stackの使用に関して" ID="ID_432827984" CREATED="1703492856041" MODIFIED="1703492863503"/> </node> </node> <node TEXT="信頼性" ID="ID_1221084016" CREATED="1702289777950" MODIFIED="1702289781581"> <node TEXT="モデル検査とAgdaによる実装" ID="ID_1438858883" CREATED="1702289781790" MODIFIED="1702289794818"/> </node> <node TEXT="評価" ID="ID_1053436711" CREATED="1702112499515" MODIFIED="1702112509004"/> <node TEXT="今後" ID="ID_87524419" CREATED="1702112509364" MODIFIED="1702112512270"/> </node> <node TEXT="修論で言いたいこと" POSITION="left" 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> </map>