Mercurial > hg > Papers > 2024 > matac-master

changeset 13:7d7117822000

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
...
author matac42 <matac@cr.ie.u-ryukyu.ac.jp>
date Mon, 08 Jan 2024 13:04:35 +0900
parents e0bcf9dbc62c
children 55c06ff63041
files Paper/master_paper.pdf mindmaps/gears_fs_db.mm
diffstat 2 files changed, 128 insertions(+), 20 deletions(-) [+]
line wrap: on
line diff
Binary file Paper/master_paper.pdf has changed
--- a/mindmaps/gears_fs_db.mm	Sun Jan 07 19:55:48 2024 +0900
+++ b/mindmaps/gears_fs_db.mm	Mon Jan 08 13:04:35 2024 +0900
@@ -347,7 +347,7 @@
 </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" ID="ID_446325287" CREATED="1701690660393" MODIFIED="1701690902283">
+<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">
@@ -388,39 +388,147 @@
 <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="処理の単位CodeGear" ID="ID_1818389006" CREATED="1703307708710" MODIFIED="1703307746215"/>
-<node TEXT="データの単位DataGear" ID="ID_1930250223" CREATED="1703307746950" MODIFIED="1703307753688"/>
-<node TEXT="ノーマルレベルとメタレベルの切り分け" ID="ID_719507396" CREATED="1703308470210" MODIFIED="1703308478844">
-<node TEXT="リフレクション" ID="ID_355579006" CREATED="1703308504930" MODIFIED="1703308513027"/>
+<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 TEXT="CbCの現状" ID="ID_950222443" CREATED="1703307926203" MODIFIED="1703307929709"/>
 </node>
 <node TEXT="信頼性の保証を目的としたGearsOS" ID="ID_1315567458" CREATED="1701692210913" MODIFIED="1703311040671">
 <node TEXT="3種類のGearsOS" ID="ID_1326415213" CREATED="1703309744902" MODIFIED="1703309750565"/>
-<node TEXT="メタ処理を記述するmetaGear" ID="ID_1666892566" CREATED="1703309692742" MODIFIED="1703309713823"/>
+<node TEXT="メタ処理を記述するmetaGear" FOLDED="true" ID="ID_1666892566" CREATED="1703309692742" MODIFIED="1703309713823">
+<node TEXT="ノーマルレベルとメタレベルの切り分け" ID="ID_719507396" CREATED="1703308470210" MODIFIED="1703308478844">
+<node TEXT="リフレクション" ID="ID_355579006" CREATED="1703308504930" MODIFIED="1703308513027"/>
+</node>
+</node>
 <node TEXT="CodeGearの遷移" ID="ID_1403713795" CREATED="1703310522532" MODIFIED="1703310534184"/>
 <node TEXT="全てのGearを参照するContext" ID="ID_91888278" CREATED="1703309731224" MODIFIED="1703310166027"/>
-<node TEXT="GearsOSの記述例" ID="ID_227287316" CREATED="1703310975416" MODIFIED="1703310983579"/>
-<node TEXT="GearsOSの現状" ID="ID_468728002" CREATED="1703310866177" MODIFIED="1703310871670"/>
+<node TEXT="GearsOSのinterface" ID="ID_227287316" CREATED="1703310975416" MODIFIED="1704626095237"/>
+<node TEXT="GearsOSのRedBlackTree" ID="ID_894257471" CREATED="1704625749056" MODIFIED="1704625759342">
+<node TEXT="Treeを継承している" ID="ID_830044324" CREATED="1704625938387" MODIFIED="1704625986222"/>
+<node TEXT="Treeはput, get, removeを持つ" ID="ID_325206226" CREATED="1704625785328" MODIFIED="1704625993146"/>
+<node TEXT="Copyがない" ID="ID_1861504637" CREATED="1704625774975" MODIFIED="1704625778526"/>
+</node>
+</node>
+<node TEXT="GearsOSのファイルシステム(現状の話" 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とレプリケーション" ID="ID_1092227909" CREATED="1701690558237" MODIFIED="1704632532265" HGAP_QUANTITY="16.25 pt" VSHIFT_QUANTITY="-1.5 pt">
+<node TEXT="ファイルシステムの信頼性" ID="ID_200982245" CREATED="1704630258973" MODIFIED="1704630267498">
+<node TEXT="信頼性に関する追加機能" ID="ID_1574949535" CREATED="1704630312069" MODIFIED="1704630320377"/>
+<node TEXT="これらは実装されていない" ID="ID_878946385" CREATED="1704630323433" MODIFIED="1704630331968"/>
+<node TEXT="実装するためにはデータのCopyが必要" ID="ID_822351907" CREATED="1704630337081" MODIFIED="1704630382753"/>
+<node TEXT="現状はTreeにCopyがない" ID="ID_65833123" CREATED="1704630383271" MODIFIED="1704630397371"/>
+<node TEXT="" ID="ID_1314300132" CREATED="1704632535428" MODIFIED="1704632535428"/>
+</node>
+<node TEXT="RedBlackTreeは単なる2分木" ID="ID_1037813952" CREATED="1704632767323" MODIFIED="1704632780206"/>
+<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="アルゴリズム" ID="ID_1656007390" CREATED="1699849518269" MODIFIED="1699849522647">
+<node TEXT="左側を深さ優先で辿る" ID="ID_1668782448" CREATED="1699849525266" MODIFIED="1699849604742">
+<node TEXT="Stack push" ID="ID_687427551" CREATED="1699849778090" MODIFIED="1699849781012"/>
 </node>
-<node TEXT="GearsFileSystem" ID="ID_667012992" CREATED="1701694178540" MODIFIED="1701694184160">
-<node TEXT="DataGearManagerによる分散ファイルシステム" ID="ID_540180010" CREATED="1703315001066" MODIFIED="1703315085575"/>
-<node TEXT="i-nodeを用いたファイルシステム" ID="ID_1851664363" CREATED="1703314946289" MODIFIED="1703492949059"/>
-<node TEXT="非破壊RedBlackTreeによる構成" ID="ID_262332331" CREATED="1701696133124" MODIFIED="1701696237170"/>
-<node TEXT="RedBlackTreeのトランザクション" ID="ID_1088328123" CREATED="1701696247760" MODIFIED="1702112463420" HGAP_QUANTITY="14.75 pt" VSHIFT_QUANTITY="3.75 pt"/>
-<node TEXT="ディスク上とメモリ上のデータ構造" ID="ID_683338430" CREATED="1701696165502" MODIFIED="1701696179372"/>
+<node TEXT="アロケートしたノードは別のContext上に作る" ID="ID_143303559" CREATED="1699849620905" MODIFIED="1699849638042">
+<node TEXT="GCのため" ID="ID_938753766" CREATED="1699849638520" MODIFIED="1699849668501"/>
+<node TEXT="Copy後古いContextを消す" ID="ID_743040439" CREATED="1699849646521" MODIFIED="1699849693755"/>
+<node TEXT="メモリ管理をモナドで表していることになる" ID="ID_4878265" CREATED="1699849705089" MODIFIED="1699849715878"/>
+</node>
+<node TEXT="リーフまで降りたらroot方向に木を戻る" ID="ID_1651314723" CREATED="1699849731393" MODIFIED="1699849765553">
+<node TEXT="Stack pop" ID="ID_657141661" CREATED="1699849765982" MODIFIED="1699849773214"/>
+<node TEXT="右側を呼び出す" ID="ID_412841654" CREATED="1699849789218" MODIFIED="1699849803550"/>
+</node>
+<node TEXT="Stackを2つ使うならば" ID="ID_179912595" CREATED="1699849785880" MODIFIED="1699850937824">
+<node TEXT="全体のStack" ID="ID_605104581" CREATED="1699850965212" MODIFIED="1699858010811">
+<node TEXT="originの木を辿るために使う" ID="ID_742122803" CREATED="1699858046929" MODIFIED="1699858071837"/>
+</node>
+<node TEXT="途中のStack" ID="ID_1233298698" CREATED="1699850966215" MODIFIED="1699858024318">
+<node TEXT="右側を呼び出す際にそれまでの左側部分木を保持" ID="ID_573311498" CREATED="1699851138198" MODIFIED="1699858042178"/>
+</node>
+</node>
 </node>
-<node TEXT="GearsFileSystemにおけるGCとレプリケーションの仕組み" ID="ID_1092227909" CREATED="1701690558237" MODIFIED="1702112470212" HGAP_QUANTITY="16.25 pt" VSHIFT_QUANTITY="-1.5 pt">
-<node TEXT="CopyRedBlackTreeによるGCの仕組み" ID="ID_694714867" CREATED="1701696212033" MODIFIED="1703491006779"/>
+<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>
+<node TEXT="CopyRedBlackTreeによるGCの仕組み" ID="ID_694714867" CREATED="1701696212033" MODIFIED="1703491006779">
+<node TEXT="CopyingGCを使用する" ID="ID_1956008882" CREATED="1704630535071" MODIFIED="1704630542771"/>
+<node TEXT="ディスク上とメモリ上の構造が同じ" ID="ID_1708669942" CREATED="1704630543186" MODIFIED="1704630559778">
+<node TEXT="データの一貫性" ID="ID_1054564074" CREATED="1704630577917" MODIFIED="1704630584566"/>
+</node>
+<node TEXT="" ID="ID_722857782" CREATED="1704630560764" MODIFIED="1704630560764"/>
+</node>
 <node TEXT="CopyRedBlackTreeによるレプリケーションの仕組み" ID="ID_1106336919" CREATED="1703490971550" MODIFIED="1703491035629"/>
 </node>
 <node TEXT="CopyRedBlackTreeの実装" 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_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 TEXT="証明のしやすさについて" ID="ID_2776247" CREATED="1703492904417" MODIFIED="1703492910899"/>
+</node>
 </node>
 <node TEXT="信頼性" ID="ID_1221084016" CREATED="1702289777950" MODIFIED="1702289781581">
 <node TEXT="モデル検査とAgdaによる実装" ID="ID_1438858883" CREATED="1702289781790" MODIFIED="1702289794818"/>