パスワードを忘れた? アカウント作成
584041 journal

tarosukeの日記: talosという名の俺OS

日記 by tarosuke

n木メモリ管理の続き。

チェックするべき階層がわかっているので、スキャンする時には基本的にブロックサイズ毎に飛び飛びにチェックする。しかしながらこれだけでは不足だ。新規に枝を作成する必要がある事を証明するには全領域をスキャンしなければならず、階層が深い場合にはそれだけ時間がかかる。それに、領域を割り付ける時にページを有効にするのでこれだけでは無効ページに触れてしまう。

そこでスキャンする前にそこが枝かどうかチェックし、枝でなければその分スキップする。これでだいぶ速くなる。問題はスキップする量だ。

いや、スキップする量は一意には決まるまい。なぜなら枝のあるなしは先頭を除いて予測不能だから。ということはつまり(微妙に論理が飛躍してはいるが)再帰によるスキャンの方が適切ということになる。つまり、必要なサイズの深さまでは単純に枝をスキャンして再帰するわけだ。で、ブロックを確保できたら戻り値で知らせる。再帰の戻り値が失敗を示している限りスキャンを続行、戻り値が成功であればそれを自身の戻り値とする。てなところか。

ここまでがメモリ確保の前半部分(必要な領域が存在する場合)。前半が失敗すると後半の処理に入り、枝を生成する。枝を生成するための領域が確保できなかったら更に上位階層から枝を生成する必要があるわけで、こっちもやっぱり再帰向きだなぁ...

しかしなぁ...他の数値計算みたいな処理はだいたい自明な事は自明に、というか人間の思考とアルゴリズムがあんまり解離してないのに、この手の処理は人間には自明な事を調べさせなきゃならないのでかなり異質に感じるぞ。なんつーか、微妙な不毛さがハノイの塔に似てるなぁ...

まーだまだ続くよぅ

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
typodupeerror

私は悩みをリストアップし始めたが、そのあまりの長さにいやけがさし、何も考えないことにした。-- Robert C. Pike

読み込み中...