internal22-198-メモリ確保アルゴリズム詳細 - Linux Kernel Documents Wiki - Linux Kernel Documents

メモリ確保アルゴリズム詳細

下記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
2000年06月11日 (日) 22時29分57秒 JST1