Linux Kernel Documents
Fork
edit{{{ comment
h2w-title:メモリ確保アルゴリズム詳細
}}}
=== メモリ確保アルゴリズム詳細 === #SECTION043121300000000000000
下記do_try_to_free_pages関数は、ユーザメモリ、バッファキャッシュ などをを検索し、優先度の低いものからどんどん解放する。目的の解放数が達成できるまでの間、何度も繰り返す。(現コンフィギュレーションでは、SWAP_CLUSTER_MAX 32）
実際の解放処理を担当する関数に、渡す引数に解放優先度を 渡すようになっており、繰り返す毎にどんどん高い解放処理の 優先度を与える。
{{{
do_try_to_free_pages(){for(解放優先度を6から0まで変化させつつ) {/*キャッシュメモリの解放*/while (shrink_mmap(解放優先度)) {if (解放数の総計がSWAP_CLUSTER_MAXを超えたら)return }/*共有メモリのスワップ*/while (shm_swap(解放優先度)) {if (解放数の総計がSWAP_CLUSTER_MAXを超えたら)return }/*swapアウトによる空きメモリの生成*/while (swap_out(解放優先度)) {if (解放数の総計がSWAP_CLUSTER_MAXを超えたら)return }/* ディレクトリエントリキャッシュの解放 */shrink_dcache_memory(解放優先度)}}
}}}
shrink_mmap関数は、各種キャッシュメモリ用のページであれば、解放を試みる。スワップキャッシュ、最近参照されていないキャッシュが 優先的に解放される。ページは様々なキャッシュ域（スワップキャッシュ、バッファキャッシュ、ページキャッシュ）として利用されている。
ページが最近参照されたかどうかを示すためにpage構造体中に 参照ビット(PG_referenced)を持っており、これらキャッシュを参照する 度(find_page関数)にこのビットを立てるようにしている。shrink_mmap関数では、この参照ビットが立っているページは解放の対象外と している。また同時に参照ビットのクリアを行う。
再度shrink_mmap関数でページが検索さるまでの間に、一度も参照されていないと そのキャッシュ域は解放されてしまう。
{{{
shrink_mmap(解放優先度, ....){解放優先度を元に今回検索対象とするページ数を求める。(解放優先度0の場合は、全ての物理メモリnum_physpages)前回の検索終了点から、mem_mapを検索する while(検索対象のページのある間) {if (I/O中のページ(PageLocked関数)なら) continue if (複数のプロセスがこのページを参照) continue if (スワップキャッシュ(PageSwapCache関数)なら) {if (複数のプロセスから参照、かつ最近参照されている) continue スワップキャッシュを削除(delete_from_swap_cache関数)return 1 }if (最近参照されたページなら) continue if (バッファキャッシュ用のページなら) {if(バッファ域が小さい(buffer_under_min関数)なら) continue バッファの解放に挑戦(try_to_free_buffers関数)if (解放に失敗した) continue return 1 }if (ページキャッシュ用のページなら) {if(ページキャッシュ域が小さい(pgcache_under_min関数)なら) continue ページキャッシュから解放(remove_inode_page関数)return 1 }}return 0;}
}}}
swap_out関数は、もっともスワップすべきページを持っている プロセスを探し出し、そのプロセスにスワップアウトの要求を出す。
{{{
swap_out(解放優先度, ...){解放優先度を元に今回スワップアウト対象とするタスク数を求める。(解放優先度0の場合は、全てのタスクnr_tasks)for (上記タスク数) {全てのタスク(プロセス)の中で、多くの物理ぺーじを持ちながら しばらくスワップされていないものを選び出す。プロセスにスワップアウト要求を出す(swap_out_process関数)if (スワップアウト成功) return 1 }return 0;}
}}}
プロセスに出されたスワップアウト要求は以下のように分解され、最終的にはプロセス内のページに対するスワップ要求(try_to_swap_out関数)になる。
swap_out_process関数 → swap_out_vma関数 → swap_out_pgd関数 →swap_out_pmd関数 → try_to_swap_out関数
{{{
try_to_swap_out(タスク, 仮想空間管理構造体, アドレスaddress, ...){if(有効なページ(pte_present関数)ではない) return 0 if(I/O中のページ(PageLocked関数)なら) return 0 if(最近アクセスのあったページ(pte_young関数)なら) {pteからアクセスビットを落とす(pte_mkold関数)ページ構造体に参照ビット(PG_referenced)を立てる return 0 }if (既にスワップキャッシュ上にある(PageSwapCache関数)) {スワップブロックの参照数を上げる(swap_duplicate関数)pteに上記スワップブロックを設定(set_pte関数)ページの解放(__free_page関数)return 0 }if (このページに一度も書きこみが行われていない(pte_dirty関数)) {pteのクリア(pte_clean関数)ページの解放(__free_page関数)return 0 }if (仮想空間管理構造体が、swapoutオペレーションを持っている) {pteのクリア(pte_clean関数)swapoutオペレーションを呼び出す ページの解放(__free_page関数)return 1 }スワップデバイス上の空きブロックを検索(get_swap_page関数)pteに上記スワップブロックを設定(set_pte関数)スワップブロックの参照数を上げる(swap_duplicate関数)/* プロセスからの参照分と、スワップキャッシュからの * 参照分を合わせて2となる */スワップ対象の物理ページをスワップキャッシュに移す(add_to_swap_cache関数)ページにI/O中フラグPG_Lockedを立てる。物理ページの内容をスワップブロックに書きこむ(rw_swap_page関数)ページの解放(__free_page関数)return 1 }
}}}
----
''(NIS)HirokazuTakahashi [[BR]]2000年06月11日 (日) 22時29分57秒 JST''