Linux Kernel(2.6)の実装に関するメモ書き

Anticipatory I/Oスケジューラ その2


Rev.17を表示中。最新版はこちら

Anticipatory I/Oスケジューラ の続き。

Elevatorとのインタフェース

Elavatorから呼び出されるAnticipatory I/Oスケジューラのルーチン群はstruct elevator_type iosched_as に定義されている。

.elevator_merge_fn = as_merge
bioを既存のRequestにMergeできるかチェックする。
Merge可能ならMerge先のRequestをreqに返す。

既存Requestの後にマージ(BackMerge)できる場合はELEVATOR_BACK_MERGEを返し、既存Requestの前にマージ(FrontMerge)できる場合は、ELEVATOR_FRONT_MERGEを返す。

FrontMergeの検索にはBIOの終端Sectorの次のSectorをKeyにRBTreeを検索してBIO→Requestが連続セクタになるRequestがないか探す。 - as_find_arq_rb()

BackMergeの検索にはBIOの先頭SectorでHashを検索してRequest→BIOが連続セクタになるRequestがないか探す。 - as_find_arq_hash()

実 際にはas_find_arq_rb(),as_find_arq_hash()で検索に行く前に、elv_try_last_merge()で最後に Mergeを行ったRequestに対して、Back/FrontMergeできないかチェックしている。連続ブロックにアクセスするような場合はここで Mergeの判定ができて検索処理が走らないようになっている。

.elevator_next_req_fn = as_next_request
次に実行すべきRequestを返す。

DispatchQueueにRequestがあればそれを返す。ない場合はas_dispatch_request()でRequestQueueから最適なRequestを選んでDispatchQueueへ入れた後、それを返す。

2.6.16を見たところなくなっている。代わりにas_dispatch_request()が直接呼ばれるようになっている。

.elevator_dispatch_fn = as_dispatch_request
Elevator内のRequestからどれかを選んでDispatchする。


if (force) {
// Anticipationを考慮せずに強制的にDispatch
return dispatched;
}

if (ad->batch_data_dir == REQ_ASYNC && !reads) {
}

/*
* 以下の条件のいずれかが成り立つ場合はDispatchしない
*
同期/非同期用のいずれかのFIFOが空
*
Anticipation中
*
Batchの向きが変更中
*/
if (!(reads || writes)
|| ad->antic_status == ANTIC_WAIT_REQ
|| ad->antic_status == ANTIC_WAIT_NEXT
|| ad->changed_batch)
return 0;

if (!(reads && writes && as_batch_expired(ad))) {
/*
* 以下のいずれかの条件が真
* ・同期I/O FIFOが空
* 非同期I/O FIFOが空
* Batchがまだ動作中
*/

// Dispatch対象のRequestを取りだし
arq = ad->next_arq[ad->batch_data_dir];

if (ad->batch_data_dir == REQ_SYNC &&
ad->antic_expire) {
// Batchが同期I/Oの場合
// Anticipationを行ないI/Oをした方がよいかをチェックする。

// FIFOがExpireしてたならAnticipationは行なわない。
// FIFOのRequestをDispatchする。
if (as_fifo_expired(ad, REQ_SYNC))
goto fifo_expired;

// Anticipationを始めた方がよいなら開始
if (as_can_anticipate(ad, arq)) {
as_antic_waitreq(ad);
return 0;
}
}

if (arq) {
// 同期I/O FIFOにRequestがあって、
// 非同期I/O FIFOにRequestがなければ
// BatchのExpireを延ばす
if (reads && !writes)
ad->current_batch_expires =
jiffies + ad->batch_expire[REQ_SYNC];
goto dispatch_request;
}
}

/*
* 以下でBatchの開始/向きの変更を行なう。
*/

if (reads) {
// Read FIFOにRequestがある

// Write FIFOにRequestがあり、現在のBatchがReadなら
// dispatch_writesに飛んで、BatchをWriteに変える。
if (writes && ad->batch_data_dir == REQ_SYNC)
goto dispatch_writes;

// さっきまでのBatchがWriteだったならReadに変更
if (ad->batch_data_dir == REQ_ASYNC) {
ad->changed_batch = 1;
}
// FIFOからDispatchするRequetを取りだす。
arq =
list_entry_fifo(ad->fifo_list[ad->batch_data_dir].next);
:
goto dispatch_request;
}

if (writes) {
// Write FIFOにRequestがある
dispatch_writes:
// さっきまでのBatchがReadだったならWriteに変更
if (ad->batch_data_dir == REQ_SYNC) {
ad->changed_batch = 1;
ad->new_batch = 0;
}
:
// DispatchするRequestを取りだし
arq = ad->next_arq[ad->batch_data_dir];
goto dispatch_request;
}

return 0;


dispatch_request:
if (as_fifo_expired(ad, ad->batch_data_dir)) {
fifo_expired:
// FIFOがExpireしている。
// FIFOのRequestを優先してDispatchするため
// FIFOからRequestを取り出し。

}

if (ad->changed_batch) {
// Batchの向きが変更

// Dispatch済みのRequestが残っているなら、
// まだ次のBatchを開始しない。

if (ad->nr_dispatched)
return 0;

// WriteBatchへの変更なら、Batchの終了タイマ設定 (*1)
if (ad->batch_data_dir == REQ_ASYNC)
ad->current_batch_expires = jiffies +
ad->batch_expire[REQ_ASYNC];
else
ad->new_batch = 1;
:
}

// RequestをDispatch
as_move_to_dispatch(ad, arq);

return 1;

(*1) ReadBatchの場合は、最初のRequestをDispatchしてI/Oが完了した時に終了タイマが設定される。new_batchは最初のRequestの完了を待つためのフラグ。

.elevator_add_req_fn = as_add_request
I/Oスケジューラ(Elevator)にRequestを入れる。
  • Requestの状態をAS_RQ_NEWにする。
  • as_update_iohist()
    • I/O Contextの統計値(ThinkTime, SeekDistance)を更新。
  • RequestをRBTree,Hashに入れる
  • RequestのFIFOタイマ(arq->expires)を設定する
  • RequestをFIFOに入れる
  • as_update_arq()
    • ad->next_arq[]更新
    • Anticipation中(ANTIC_WAIT_REQかANTIC_WAIT_NEXT)だったら、期待していたRequestなのかをチェックして必要ならAnticipationを中断
  • Requestの状態をAS_RQ_QUEUEDにする

.elevator_completed_req_fn = as_completed_request
I/O Requestが完了すると呼び出される。

.elevator_latter_req_fn = as_latter_request
スケジューラ内のrqの次のRequestを返す。

Anticipatoryスケジューラでは、次にSector#の大きいRequest(RBTreeの次のノードのRequest)を返す。


内部の関連関数

as_antic_waitnext()
すぐに効率のよいRequestがSubmitされることを期待してAnticipatingを開始する。
  • タイマ(ad->antic_timer)をad->antic_expire後に設定
  • ANTIC_WAIT_NEXT状態に遷移
タイマ(ad->antic_timer)が満了すると、as_antic_timeout()が呼ばれる。
このルーチンはANTIC_OFFかANTIC_WAIT_REQ状態から呼ばれる。

as_antic_waitreq()
Anticipation を開始する。as_antic_waitnext()はANTIC_WAIT_NEXT状態に遷移するが、本ルーチンは、最後にDispatchした Requestが同期I/OでそのI/Oがまだ完了していない場合は、ANTIC_WAIT_REQに遷移する。

as_antic_timeout()
ad->antic_timerのハンドラ。as_antic_waitnext()で開始したAnticipatingの終了処理を行なう。

Anticipating中(ANTIC_WAIT_REQかANTIC_WAIT_NEXT)だったら以下の処理を行なう。
  • ANTIC_FINISHED状態に遷移
  • RequestをDispatch (*1)
(*1) 実際にはWorkQueueで処理しているのでDispatchされるタイミングは非同期。kblockd_schedule_work(&ad ->antic_work)でWorkQueueをスケジュールしている。Workのハンドラはas_work_handler()。

as_work_handler()
kblockd_schedule_work(&ad->antic_work)でスケジュールされるWorkQueueのハンドラ。ドライバのI/O Request処理ルーチン(q->request_fn(q)(*2))を呼び出してI/Oを行なう。

(*2) request_fnはデバイスドライバがblk_init_queue()でRequestQueueを作成する時に指定されるデバイスドライバのI/O Request処理ルーチン。elv_next_request()でElevatorのRequestをDispatchしてRequestQueueに入れてI/Oを実行していく。

as_move_to_dispatch()
指定RequestをDispatchQueue(q->queue_head)へ移動する。
  • Anticipation停止(as_antic_stop())
  • ANTIC_OFF状態に遷移
  • ad->last_sector[]更新
  • ad->io_contextの更新(同期I/OならRequestのio_contextを指し、非同期I/OならNULLにする)
  • ad->next_arq[]更新
  • RequestをFIFO,RBTree,Hashから削除
  • elv_dispatch_sort()を呼んでRequestQueue(rq->queuelist)へ移動。
  • RequestをAS_RQ_DISPATCHED状態にする
as_completed_request()

as_can_anticipate()
Anticipationを始めた方がよいかRequestをすぐに実行した方が良いかを判定する。

以下のいずれかの条件が成り立つと0を返す(すぐにRequestを実行した方がよい)。
  • 最後にDispatchしたRequestが非同期I/O(Write I/O)
  • スケジューラの状態がANTIC_FINISHED状態
  • as_can_break_anticipation()が真
as_can_break_anticipation()
Anticipationを中断するかどうかを判定する。期待(Anticipation)していたRequestだった場合は1を返してAnticipationを中断させる。

RequestがElevatorに入れられた時、Anticipation中だったらAnticipationを中断するかどうかを判定するために呼び出される。

以下のいずれかの条件が成り立つと1を返す(Anticipation中断)。
  • Elevatorに入れられたRequestが最後にDispatchしたRequestと同じプロセスからのものだった
  • 最後にDispatchしたRequestが完了して且つAnticipationがExpireしている
  • プロセスが他にもElevatorにRequestを入れている
  • プロセスが他にもRequestをDispatchしてまだ完了していないものがある
  • Elevatorに入れられたRequestが同期I/Oで最後にDispatchされたRequestとセクタ番号が近い(as_close_req()が真)
  • ThinkTimeの平均値がAnticipationの時間(antic_expire)を越えた

[関連ページ]
I/Oスケジューラ
Anticipatory I/Oスケジューラ


最終更新 2006/07/19 19:37:29 - kztomita
(2006/07/16 17:48:27 作成)


リンク
最近更新したページ
検索