無料Wikiサービス | デモページ
Linux Kernel(2.6)の実装に関するメモ書き
リンク
最近更新したページ
検索

Read Ahead


概要

ファイルのRead処理ではファイルを後ろの方へシーケンシャルに読んでいくことが多いため、LinuxカーネルはファイルのあるブロックをReadすると、指定されたブロックから先のブロックもまとめてReadする(先読み)ようになっている。これには、以下のようなメリットがある。

  • ファイルはディスク上に連続ブロックに配置されている可能性が高いため、ディスクヘッドの動きを小さくなりI/Oが効率化できる。
  • ディスクへのI/O回数をまとめることでI/Oが効率化できる。
  • 先にデータを読み込んで置くことで、アプリケーションが頻繁にI/O待ちしなくて済むようになる。

基本動作

Read Ahead動作では、Current windowとAhead windowの2種類のWindowを管理する(図1)。Current windowはアプリケーションがReadしている領域で、Ahead windowはRead I/Oを行っている領域。Current WindowとAhead Windowは隣接しており、アプリケーションのReadがAhead windowに到達すると、Ahead windowがCurrent windowになり(*1)、新しいAhead windowが作成されてRead I/Oが開始される。


図1 Current WindowとAhead Window

(*1) Read I/Oは終了していない可能性もある。その場合ページはロックされている。


実装

page_cache_readahead(*mapping, *ra, *filp, offset, req_size)

先読みを行なう大元のルーチン。
mappingで指定されるファイルのアドレス空間のoffsetページからreq_sizeページの先読みを要求する。本関数は先読みした分だけReadAheadのポインタ(ra->prev_page)を進め、Current Windowを読みきった場合に、新しいAhead Windowを作成してRead I/Oを発行する(詳細は下記3.参照)。I/O完了は待たずにリターンする。

本関数は主に以下の3種類に条件分けされ処理を行っている。

1. ファイル先頭への初回アクセスの場合
ファイル全体へのReadアクセスが発生すると仮定して、Windowサイズを大きめにとってI/Oを開始する。

2. 前回のRead Aheadからアクセス位置が連続していない
ランダムアクセスであると判断してReadAheadを抑止する。

3. 通常のシーケンシャルRead(上記以外)
先読みしてRead Pointerであるra->prev_pageを進めた結果、まだCurrent Window内であればなにもしない。このとき、Ahead Windowの領域に対してはI/O処理中(既に完了している可能性もある)。
Ahead Windowに到達していた場合、Ahead WindowをCurrent Window に変更する。そして、make_ahead_window()で新しいAhead Windowを作成して、この領域に対してRead I/Oを発行する。この時、新しいCurrent Windowはまだ、Read I/Oが完了していない可能性がある。I/Oが完了していなかったらページはロックされている。

本関数ではI/Oを行う前に空のPageCacheが作成されるので、Current Window,Ahead Windowの領域に対しては必ずPageCacheが存在することになる。このため、 page_cache_readahead()の呼び出し元は先読みを要求した領域については、通常PageCacheが存在していることを期待できる(Uptodate状態とは限らない)。もし存在しなかった場合は、メモリ不足、I/Oの頻発でPageCacheが多くなった、などの理由によりPageCacheが回収されてしまったことになる。この場合、呼び出し元はhandle_ra_miss()でキャッシュミスを通知することで、次のAhead Windowのサイズを縮めることができる。

page_cache_readahead()の処理の概要


/* 前回の先読みからシーケンシャルなアクセスになっているかチェック */
sequential = (offset == ra->prev_page + 1);
ra->prev_page = offset;

/* Read Aheadを行う最大のページ数(128kb分) */
max = get_max_readahead(ra);
/* 先読みするサイズを決定 */
newsize = min(req_size, max);
:
/* どこまで先読みしたかを保存 */
ra->prev_page += newsize - 1;

if (sequential && ra->size == 0) {
    /* ファイル先頭への初回アクセス時の処理 */
    /* 初回のWindow サイズ */
    ra->size = get_init_ra_size(newsize, max);
    ra->start = offset;
    if (!blockable_page_cache_readahead(mapping, filp, offset,
                                        ra->size, ra, 1))
        goto out;
    :
    goto out;
}
if (!sequential) {
    /* ランダムアクセス時の処理 */
    ra_off(ra);  /* Read AheadをDisable */
    /* 要求された分はRead */
    blockable_page_cache_readahead(mapping, filp, offset,
                                   newsize, ra, 1);
    goto out;
}

/* 以下はReadAheadの基本ケースの処理 */

/* ahead windowがまだ作成されていなければ
 * 作成してI/O開始。
 */
if (ra->ahead_start == 0) {
    if (!make_ahead_window(mapping, filp, ra, 0))
        goto out;
}

/* current windowを読みきって、ahead windowに到達したら
 * 現在のahead windowをcurrent windowにして
 * make_ahead_window()で新しいahead windowを作成。
 * ahead windowのRead I/Oも開始される。
 */
if (ra->prev_page >= ra->ahead_start) {
    ra->start = ra->ahead_start;
    ra->size = ra->ahead_size;
    make_ahead_window(mapping, filp, ra, 0);
}
out:
    return ra->prev_page + 1;
make_ahead_window(*mapping, *filp, *ra, force)
次のAhead Windowを作成して、Windowの領域に対してI/Oを開始(blockable_page_cache_readahead())する。
Windowサイズは少しずつ大きくしていくが、handle_ra_miss()でキャッシュミスが通知されていた場合は、小さくしてPageCacheの使用量を抑えようとする。

blockable_page_cache_readahead(*mapping, *filp, offset, nr_to_read, block)
指定ファイル(mapping)のページオフセットoffsetからnr_to_read分のデータを先読みする。処理の実体は__do_page_cache_readahead()。

__do_page_cache_readahead(*mapping, *filp, offset, nr_to_read)
指定された領域のうち、PageCacheが存在しないページについてだけ、ページを作成しread_pages()を呼び出してRead処理を行う。

read_pages(*mapping, *filp, *pages, nr_pages)

ページデータの読みこみルーチン。
ファイルのページリード用ハンドラ(mapping->a_ops->readpages)を呼び出して(*1)、Readを開始する。readpagesハンドラでは指定されたpagesのページにデータを読み込むRead I/Oを発行する。

(*1) do_generic_mapping_read()でmapping->a_ops->readpage()を呼び出す際は、ページをロックしてから呼び出していたが、mapping->a_ops->readpages()を呼び出す際は、ページをロックしていない。readpagesを呼び出した先でロックされている。(例えば、Ext2 FSではreadpagesはext2_readpages()を呼び出し、mpage_readpages()を呼び出す。mpage_readpages()はI/Oを開始する前にadd_to_page_cache()でページをPageCacheに登録してページがロックされる。)

関連ページ

generic_file_read()


最終更新 2007/02/16 19:03:01 - kztomita
(2007/02/11 20:09:39 作成)
添付ファイル
window.png - kztomita