1. 概要

Anticipatoryスケジューラでは、I/O RequestをDispatch(*1)するように要求があった時に、セクタ番号が近いなどもっと効率の良く処理できるRequestがすぐ後に発行されないか予測(Anticipation)を行なう。より良いRequestが来そうであれば、Dispatchを遅らせてより良いRequestが来るのを待ってI/Oを効率化していくのが特徴。予測はプロセス毎に管理しているI/Oの統計を使って行なう。

(*1) デバイスドライバのRequestQueueに入れること。

2. スケジューラの動作

2.1 Request種別

Requestの種別が同期I/O(I/O完了まで待つ)か非同期I/O(I/O完了まで待たない)かによってスケジューリングポリシーが変わる。

Read Requestは同期I/Oで、Write Requestは基本的に非同期I/Oとなる(O_SYNCが指定されている時は同期I/O)。ソース中では同期I/O(REQ_SYNC)はRead,非同期I/O(REQ_ASYNC)はWriteとしているので、以下でも暗黙的に同期I/O＝Read、非同期I/O＝Writeとする。

ReadRequestは後述のAnticipationを行いたくさんのRequestをDispatchするのではなく、DispatchするRequestは抑えて、できるだけElevator内でRequest順を効率化しようとする。I/Oが完了すると次のRequestをDispatch、というように少しずつDispatchする。

WriteRequestについては次々とDispatchしていく。

2.2 FIFO

I/O RequestがElevatorに入れられるとAnticipatory スケジューラでは内部のFIFOに入れる。FIFOは同期I/O,非同期I/O用にそれぞれ分かれている。

Anticipatoryスケジューラでは、後述のAnticipationを行い最後にDispatchしたRequestと近いセクタのRequestを次にDispatchしようとする。このため、先にElevatorに入れられたRequestの実行が後回しになることがあるが、遅延が無限に大きくならないようにFIFOにはタイマ値が存在する。FIFOに入れられたRequestはタイマ(arq->expires)を設定され、DispatchしようとしてRequestがExpireしていたらFIFOのRequestを優先してDispatchすることで遅延が大きくなりすぎないようにしている。

FIFOのExpireチェックはDispatchしようとした時のBatchの向きと同じFIFOについてだけチェックを行う。ReadFIFOのタイムアウトはReadBatchの間しかチェックしないしWriteFIFOのタイムアウトはWriteBatchの間しかチェックしない。このため read batch time > write expiration time や write batch time > read expiration time となるような設定は推奨されない。(逆方向のFIFOがExpireしても、現在のBatchがExpireするまでなかなか処理が回って来ないことになる)

2.3 Batch

RequestをDispatchする時は、同期I/Oなら同期I/Oを非同期I/Oなら非同期I/Oをある程度連続してDispatchする。この動作をBatchと呼ぶ。以下では同期I/OのBatchをReadBatch、非同期I/OのBatchをWriteBatchと呼ぶ。

Batchが開始するとExpireするまで同じ方向(*1)のRequestのみをDispatchする。Expire時刻はad->current_batch_expiresに格納されている。BatchがExpireすると他方向のBatchに切り替わる。Batchの方向が変わるときはDispatchしたRequestが全て完了するまで次のRequestはDispatchさせないようになっている。

ReadBatchはWriteFIFOにRequestがない時は、Expireタイマが更新されていくので、ReadRequestしか存在しない場合はExpireせずにDispatchし続ける。

WriteBatchにはExpireタイマ以外にもDispatchできるRequest数に制限(write_batch_count)が掛けられている。時間が残っている場合でも、DispatchしたRequest数が制限値を越えるとBatchが切り替わる。write_batch_countはReadBatchの最初のRequestのI/Oが完了した時にWriteBatchに使用した時間に応じて調整される。

*1 ソース中では同期、非同期ではなくRead,Writeという呼び方でBatchもDirectionで分けているので方向とここでも方向と呼ぶ。

2.4 Anticipation

AnticipatoryスケジューラではReadRequestのDispatch要求があった時に、現在のDispatch候補よりも(セクタ番号が近いなど)もっと効率的に処理できるRequestがすぐに来るのではないかということを予測(Anticipation)して、必要ならDispatchを遅らせて別のRequestを待つ。

AnticipationはReadRequest(同期I/O)についてのみ行う。WriteRequest(非同期I/O)については、I/Oのタイミングは自由度があるため、Anticipationは行わない。

2.4.1 Anticipationの開始

ReadRequestのDispatch要求があった時に、Anticipationを始めてより良いRequestを待つか、そのままDispatchするかを判定する(as_can_anticipate())。

ReadBatchでまだRequestがDispatchされていなければ、とりあえず一つ目をDispatchする。Dispatch済みなら最後にDispatchしたRequestと新たにDispatchしようとしているRequestを比較して、もっと良いRequest待った方が良いかを判断する。以下の状態ではAnticipationは必要ないものとしてすぐにDispatchする。

• 最後にDispatchされたRequestと同じプロセスからのRequestだった場合
• 最後にDispatchされたRequestとセクタが近い(*1)場合
• 次のRequestが来る前にAnticipationがタイムアウトしそうな場合(*2)

この判定は、as_can_anticipate()から呼び出されるas_can_break_anticipation()で判定している。

Anticipationが始まるとRequestのDispatchは抑止される。

as_can_anticipate(),as_can_break_anticipation()についてはAnticipatory I/Oスケジューラ その2参照。

(*1) 「近い」かどうかの判断にはI/O ContextのSeek Distance平均値が使用される。
(*2) タイムアウト前に次のRequestが来そうかどうかの判断にはI/O ContextのThink Time平均値が使用される。

2.4.2 Anticipationの終了

RequestがElevatorに入れらた時にAnticipation中だった場合、Anticipationを中断するかどうかを判断する。

以下の条件でAnticipationを中断してRequestをDispatchする。

• 最後にDispatchされたRequestと同じプロセスからのRequestだった場合
• 最後にDispatchされたRequestとセクタが近い場合
• 次のRequestが来る前にAnticipationがタイムアウトしそうな場合

これらの判定はas_can_break_anticipation()で行っている(Anticipationの開始判定と同じ)。詳細はAnticipatory I/Oスケジューラ その2参照。

また、一定時間Requestが入れられなかった場合も、Anticipationがタイムアウトして次のRequestをDispatchする。(as_antic_timeout())

2.5 DispatchするRequestの選択

DispatchするRequestはディスクヘッドのシークが効率的になるように基本的にセクタ番号順になるように選択されていく。セクタが戻る(BackSeekする)Requestについてはペナルティが加算され、その他のRequestとどちらが良いか比較され選択される。この処理はas_find_next_arq()で行われる。

次にDispatchするRequestの選択は以下のタイミングで行われ、選ばれたRequestはad->next_arq[]にキャッシュされ、Dispatchする際はここから取り出される。

• ElevatorにRequestが入れられた時 - as_update_arq()
• RequestをDispatchした時 - as_move_to_dispatch()

ただし、FIFO内のRequestがExpireしている場合は、FIFOのRequestからDispatchして、遅延が大きくならないようにしている。

2.5.1 Requestの選択ルールの詳細

as_find_next_arq()は最後にDispatchしたRequestのRBTreeで前か次どちらかのRequestを選ぶ(*1)。具体的には以下の表に示す評価値を比較して小さい方のRequestを選択する(as_choose_req())。

基本的に次のRequestを選ばれることになる。前方のセクタに対するRequestの場合はペナルティとして、BACK_PENALTYが乗ぜられるのでBackSeekするようなRequestは選ばれ難くなる。BackSeekする場合でもMAXBACK(1024*1024)を越える場合は評価値が無限大となり、選択の優先度としては最低になる。

最後にDispatchしたRequest(last)との 位置関係	評価値
lastより後にある場合	last<-->1st Sectorの距離
lastより前にある場合(MAXBACK以内)	(1st Sector<-->lastの距離) * BACK_PENALTY(2)
lastより前にある場合(MAXBACK以上)	∞(*2)

            |<---------->|<-->|
Sectors ....oooo....oooooo....oooooo...
            prev         last  next

.:Sector
o:Request

(*1) RBTreeはセクタ番号でソートされているので、前方もしくは後方の直近のセクタへのRequestが選ばれることになる。
(*2) 実装としてはr1_wrap,r2_wrapのフラグが立てられて処理される。

2.6 I/O Context

AnticipatoryスケジューラではI/O Contextと呼ぶプロセス毎のI/Oに関する統計値を管理する。I/O ContextにはThink Time,Seek Distanceの平均値を計算して保存しておく。この値はElevatorにRequestを入れた時に更新される(as_update_iohist ())。これらの値は、新しいRequestがElevatorに入れられてAnticipationを続けるか止めるかを判断するのに使われる(Anticipatory I/Oスケジューラ その2のas_can_break_anticipation()参照)。

Think Time

Seek Distance

3. データ構造

3.1 全体構造

AnticipatoryスケジューラはRequestQueue毎に図1に示すデータ構造を持つ。struct as_dataがスケジューラの管理データ。ここにRequest(struct as_rq)を管理するFIFO,RedBlackTree,ハッシュがある。

フィールド	説明
fifo_list[]	SubmitされたRequestが入れられるFIFO。struct as_rqがチェーンされる。 同期I/Oと非同期I/Oで区別される。(fifo_list[REQ_SYNC],fifo_list[REQ_ASYNC]) RequestをFIFOに入れると、RBTree,Hashにも挿入されて管理される。
next_arq[]	次にDispatchするRequest。 以下のタイミングで更新される。 ElevatorにRequestが入れられた時 - as_update_arq() Dispatchした時 - as_move_to_dispatch()
sort_list[]	RequestのRedBlackTree。Requestの開始セクタ番号をキーにしており、FrontMerge処理の検索に使用される。RBTreeも同期、非同期でそれぞれ存在する。
hash	Requestのハッシュテーブル。 Requestの終端セクタの次セクタ(sector + nr_sectors)をキーにする。 BackMergeの検索に使用される。
current_batch_expires	現在動作中のBatchの終了時刻
changed_batch	Batchの向き(SYNC,ASYNC)が変るときにセットされる。Batchが切り替わる際にDispatch済みのRequestが完了するのを待つために使用される。 このフラグが立っている最中はDispatchは抑止され、Dispatch済みのRequestの処理が全て完了するとクリアされて次のBatchを始められる。
new_batch	ReadBatchが始まって最初のRequestが完了するのを待つために使われる。 ReadBatchが始まるときにセットされ、Requestが完了するとクリアされる。
batch_data_dir	現在のBatchの向きを示す。
write_batch_count	1回のWriteBatchでDispatchできるRequest数の上限。 ReadBatchの最初のRequestが完了するとupdate_write_batch()で値が調整される。
current_write_count	現在のWriteBatchでDispatchできる残りのRequest数
antic_timer	Anticipating 終了タイマ。as_antic_waitnext()でAnticipatingを開始する時に設定される。 タイムアウトするとas_antic_timeout()が呼ばれる。
io_context	最後にDispatchしたRequestを発行したプロセスのI/O Contextを指す。AnticipationでRequestを待つ時にプロセスを識別するのに使う。非同期I/O(Write)だとNULL。
ioc_finished	ad->io_contextが指しているプロセスのI/Oが完了すると1になる。RequestをDispatchする時にクリアされる。
fifo_expire[]	FIFOのExpire時間。 Requestがスケジューラに入れられた時に、この時間がタイマ(arq->expires)に設定される。
batch_expire[]	BatchのExpire時間。
antic_expire	Anticipationを行う時間(ms)。 0だとAnticipationは抑止される。

3.2 スケジューラの状態

struct as_dataのantic_statusはスケジューラの状態を保持する。

状態	意味
ANTIC_OFF	通常状態。Anticipationはやっていない。
ANTIC_WAIT_REQ	Anticipating中。Dispatchは抑止される。 最後に発行したReadRequestがまだ完了していない。完了するとANTIC_WAIT_NEXTに遷移する。まだ、Requestが完了するまでタイマはかけない。(候補のプロセスが起床してから)
ANTIC_WAIT_NEXT	Anticipating中。Dispatchは抑止される。 最後のReadから次のReadを期待している状態？ タイマ(antic_timer)動作中 /* Currently anticipating a request vs last read (which has completed) */
ANTIC_FINISHED	Anticipatingが終了した。(タイムアウトしたか、適当なRequestが来た)

3.3 Requestの状態

状態	説明
AS_RQ_NEW	ElevatorにもRequestQueueにも登録されていない。
AS_RQ_QUEUED	Elevatorに入れられている(Schedulerの管轄)。
AS_RQ_DISPATCHED	Dispatchされている(RequestQueueの中にある)(デバイスドライバの管轄)。
AS_RQ_PRESCHED
AS_RQ_REMOVED
AS_RQ_MERGED
AS_RQ_POSTSCHED

3.4 I/O Context

I/Oの状態を管理するためのプロセス毎の情報エリア(デバイス単位ではない)。

Anticipatoryスケジューラではstruct as_io_contextの領域にThink Time,Seek Distanceの平均値を計算して保存しておく。このエリアはRequestをFIFOに入れる時に更新される(as_update_iohist())。

フィールド	意味
ttime_total	Think Time総時間。 更新の度に旧値を7/8にして新規Think Timeの1/8を加えて1/8ずつエージングしている。
ttime_samples	平均を計算するための分母。
ttime_mean	平均Think Time。
seek_total	Seek Distance合計値。 ttime_totalと同様1/8ずつエージングしている。
seek_samples	平均を計算するための分母。
seek_mean	平均Seek Distance

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

[その他]
Documentation/block/as-iosched.txt