アルゴリズム詳細

以下にその大雑把なアルゴリズムを示す。アルゴリズム中に付いている◆印は同期書き込みを、◇印は遅延書き込みを表す。

  ext2_new_inode(親ディレクトリのiノード, 生成するファイルタイプ)
      メモリiノードを確保(get_empty_inode関数)
      if(生成するファイルがディレクトリ?) {
           1ブロックグループあたりの平均フリーinode数を計算
           for(全てのブロックグループ) {
               ブロックグループディスクリプタ読み込み(ext2_get_group_desc関数)
               平均以上のinodeがあり、最も空きブロックの多いブロックグループを求める。
           }
      } else {
           親ディレクトリが属するブロックグループディスクリプタ読み込み(ext2_get_group_desc関数)
           if(同じブロックグループ内にフリーinodeがある) {
                このブロックグループを候補とする。
           } else {
                for(ブロックグループをquadratic hash検索) {
                      ブロックグループディスクリプタ読み込み(ext2_get_group_desc関数)
                      空きiノードがあるブロックグループを候補とする
                }
           }
           if(それでも候補のブロックグループが見つからない) {
               for(全てのブロックグループ) {
                     ブロックグループディスクリプタ読み込み(ext2_get_group_desc関数)
                     空きiノードがあるブロックグループを候補とする
               }
           }
      }
      候補のブロックグループのiノードビットマップを読み込む(load_inode_bitmap関数)
      iノードビットマップ内のフリーなビットを見つけ、予約する。
      ◇iノードビットマップの遅延書き込み要求(mark_buffer_dirty)
      if(SYNCマウント?) {
           ◆iノードビットマップをディスクに書き込み(ll_rw_block関数、wait_on_buffer関数)
      }
      ブロックグループディスクリプタが管理するフリーiノード数を1減らす
      ◇ブロックグループディスクリプタの属するバッファを遅延書き込み要求(mark_buffer_dirty)
      スーパブロックが管理するフリーiノード数を1減らす
      ◇スーパブロックを遅延書き込み要求(mark_buffer_dirty)
      メモリiノード初期化し、iノードハッシュに登録
      ◇メモリiノードの遅延書き込み要求(mark_inode_dirty)
      return メモリiノード

(NIS)HirokazuTakahashi
2000年12月09日 (土) 23時55分06秒 JST
1