1. はじめに

  前回は I/O スケジューラの elevator_merged_fn メソッドの役割と CFQ における elevator_merged_fn メソッドの実装である cfq_allow_merge_fn メソッドの実装について見てきた。
  ここでは、I/O スケジューラにおける bio オブジェクトのリクエストオブジェクトに対するマージが行われてはならないケースについて記載していた。


2. 概要

  今回は elevator_dispatch_requests メソッドについて。前回同様に、その役割と CFQ における実装について見てゆく。
  まずは例によって、カーネルドキュメントからその処理の概要について把握する。以下がその内容になる。

elevator_dispatch_fn    fills the dispatch queue with ready requests.
        I/O schedulers are free to postpone requests by
        not filling the dispatch queue unless @force
        is non-zero.  Once dispatched, I/O schedulers
        are not allowed to manipulate the requests -
        they belong to generic dispatch queue.

  各 I/O スケジューラがこのメソッドで行う処理内容は、ディスパッチキューに入れる事らしい。この「ディスパッチキュー」について前回以前に説明なしでこれを紹介したが。I/O スケジューラから見た I/O ブロックレイヤのリクエストキュー (request_queue 型) オブジェクトの事をディスパッチキューとここでは言っている。
  そして、引数で渡される force 変数の値が 0 の時、I/O スケジューラはディスパッチキューに対するリクエストの挿入処理は自由に調節できると言っている。最後に、ディスパッチキューに送ったリクエストオブジェクトは I/O スケジューラの都合で変更してはいけないと言っている。
 

3. 学習内容のまとめ

  ドキュメントでも記載されているように、elevator_dispatch_fn メソッドでは、各 I/O スケジューラが持つリクエストオブジェクトをディスパッチキューに転送する処理を行う。
  処理内容は２通り存在し、このメソッドの第二引数の force 変数に 1 が設定された場合、I/O スケジューラが管理する全てのリクエストオブジェクトをディスパッチキューに転送する。force の値が 0 の場合、I/O スケジューラは独自の判断でディスパッチキューにリクエストオブジェクトを転送する (場合によっては何も転送しない) 処理を行う。


4. 内容詳細

  それでは CFQ における elevator_dispatch_requests メソッドの実装について、引数の force 変数に 1 が設定された場合の処理について見てゆく。以下がメソッドの実体の cfq_dispatch_requests() 関数のうち、force 変数に 1 が設定された時に関連するコード。

[ code 1 ]

1    static int cfq_dispatch_requests(struct request_queue *q, int force)
2    {
3      struct cfq_data *cfqd = q->elevator->elevator_data;
4      struct cfq_queue *cfqq;
5      int dispatched;
6   
7      if (!cfqd->busy_queues)
8        return 0;
9   
10     if (unlikely(force))
11       return cfq_forced_dispatch(cfqd);
12   
13     .. (略) ..
14   
15  }

  force 変数に 1 が設定された時 CFQ は、I/O スケジューラが管理する全てのリクエストオブジェクトをディスパッチキューに転送する処理を行う。

  コードの 7 行目で行っている cfq_data オブジェクトの busy_queues メンバのチェックは CFQ が持ついづれかのリクエストキューの中にリクエストオブジェクトが入っているかどうかを確認している。リクエストオブジェクトのキューへの挿入が完了した時、cfq_add_cfqq_rr() 関数 [2] が呼ばれ、cfq_data オブジェクトの busy_queues メンバの値をインクリメントする。逆に、cfq_del_rq_rb() [3] の処理が完了した時に busy_queues メンバの値はデクリメントされる。
  cfq_data オブジェクトの busy_queues メンバの値は、CFQ で管理するリクエストオブジェクトの数を表している。この値が 0 の時、CFQ 内部にはひとつもリクエストオブジェクトが存在しない事を意味する。

  そして 10 行目で force メンバの値を読み、判定が真の時に cfq_forced_dispatch() を実行する。この force 変数を囲んでいる unlikely マクロはコンパイラに対して、この判定がほとんどの場合偽である事を教えている。何故、こんなことをしているのか。
  かなり教科書的な話になるが。最近のアーキテクチャではマルチサイクルプロセッサが当り前である、シングルサイクルプロセッサでは１サイクル中に利用出来る CPU 内部の機能ユニットはひとつの命令によって占領されるが、マルチサイクルプロセッサでは、ひとつの CPU の同じクロック周期の間に、複数の命令によって複数の機能ユニットを使用できる。なので、複数の命令が同時に別々の処理 (命令フェッチやデコード処理など) が実行できる。
  これが世に言うパイプラインというやつなのだが。こいつは、逐次的な処理の場合には、同時に複数の命令を処理する事が出来てパフォーマンスが上がるが、if や while といったジャンプ命令がくると、パイプラインに溜った処理を実行する事が無いので、パイプライン処理が無駄になる (教科書的にはこいつの事を "ストール" とか言ったりする。パイプラインが細かければ細かい程、逐次処理のパフォーマンスは高いが、ストールによる損失は大きくなる)。
  ジャンプ命令が来てもパフォーマンスを落とさないために、昔の偉い人はジャンプ命令の予測を行うという事を考えた。この unlikely マクロの処理はその一環になる。つまり、発生するジャンプ処理のジャンプ先がほぼ確実にわかっていれば、そのジャンプ処理を含むパイプライン処理のパフォーマンスは逐次処理のそれと変わらなくなるから。

  ここで 11 行目で実行される cfq_forced_dispatch() 関数の処理を見てゆく。以下がそのコード。

[ code 2 ]

1    static int cfq_forced_dispatch(struct cfq_data *cfqd)
2    {
3      int dispatched = 0;
4      struct rb_node *n;
5   
6      while ((n = cfq_rb_first(&cfqd->service_tree)) != NULL) {
7        struct cfq_queue *cfqq = rb_entry(n, struct cfq_queue, rb_node);
8   
9        dispatched += __cfq_forced_dispatch_cfqq(cfqq);
10     }
11   
12     cfq_slice_expired(cfqd, 0);
13 
14     BUG_ON(cfqd->busy_queues);
15   
16     return dispatched;
17   }

  cfq_forced_dispatch() では 6 行目のループの判定処理で cfq_rb_first() を実行し、リクエストキューを表す rb (red-black) ツリーのノードを取得する。以下がそのコード

[ code 3 ]

1    static struct rb_node *cfq_rb_first(struct cfq_rb_root *root)
2    {
3      if (!root->left)
4        root->left = rb_first(&root->rb);
5    
6      return root->left;
7    }

  cfq_rb_root オブジェクトが持つ rb ツリーから、先頭ノードを表す rb_node オブジェクトを取得する。
  cfq_rb_root オブジェクトは、ルートノードの左側のノード情報をメンバに持っている。これは、CFQ のデータ構造に度々出てくる、探索処理を省略する為に用意されているものである。

  [ code 2 ] で示した cfq_forced_dispatch() では cfq_rb_first() で CFQ 内部のリクエストキューの rb ツリーノードを取得し、7 行目でリクエストキューオブジェクトを取得する。そして、__cfq_forced_dispatch_cfqq() 関数を呼び出す。以下がそのコード。

[ code 4 ]

1    static inline int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq)
2    {
3      int dispatched = 0;
4   
5      while (cfqq->next_rq) {
6        cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);
7        dispatched++;
8      }
9   
10     BUG_ON(!list_empty(&cfqq->fifo));
11     return dispatched;
12   }

  __cfq_forced_dispatch_cfqq() では、CFQ のリクエストキューに属する全てのリクエストオブジェクトをディスパッチキューに転送させる。
  内部では 5 行目から 8 行目のループで表されるように、リクエストキューが参照する next_rq メンバ [struct request * 型] の参照が無くなるまで cfq_data オブジェクトが参照するディスパッチキューと cfq_queue->next_rq を引数に cfq_dispatch_insert() [4] を呼び出す。
  cfq_queue オブジェクトの next_rq メンバはキューが次に処理すべきリクエストオブジェクトを表し、なんらかの理由によってキューからこのリクエストが削除された場合には、cfq_find_next_rq() を呼び出して、対象の cfq_queue オブジェクトの next_rq メンバをその都度、更新しなければならない。この処理は cfq_dispatch_insert() から呼ばれる cfq_remove_request() [5] において行われる。
  ここでは CFQ において重要な特徴のひとつを教えてくれている。うまり、CFQ I/O スケジューラは、各キューに滞留しているリクエストオブジェクトの処理順序について次に処理するリクエストのみを把握しており、それ以外の滞留リクエストについては未定であって、次に処理されるリクエストが消えて初めて、cfq_queue 内部から次に処理されるリクエストオブジェクトを選出するという設計となっている。
  但しこれは cfq_queue オブジェクトの sort_list メンバで表される rb ツリーに登録されているリクエストオブジェクトの場合の話。cfq_queue オブジェクトでは、sort_list メンバ以外に fifo メンバによってリクエストオブジェクトを管理している。これが表すキューにリクエストオブジェクトの queuelist メンバのアドレスが登録されており、リクエスト "キュー" を実現している。

  [ code 2 ] で示した cfq_forced_dispatch() の 7 行目で実行される、上述の [ code 4 ] で示した __cfq_forced_dispatch_cfqq() によって、6 行目で取得した cfq_queue オブジェクトが持つリクエストオブジェクトは全てディスパッチキューに送られる。
  ここで改めて 6 行目から 10 行目のループがとても奇妙に見える。それは、ループの内部及び、ループの真偽の判定の度に呼び出される cfq_rb_first において、cfq_rb_root オブジェクトの left メンバの値は変えられていないので、一見すると毎回同じ値が選ばれて無限ループになるように思える。[ code 4 ] で見た 5 行目から 8 行目で表されるループのように。
  これが無限ループにならないのは、ループ中で呼び出される __cfq_forced_dispatch_cfqq() の内部処理に秘密がある。
  上述したように __cfq_forced_dispatch_cfqq() では、リクエストキューが溜めている全てのリクエストオブジェクトに対して cfq_dispatch_insert() を実行している。リクエストキューに属する最後のリクエストオブジェクトを対象とした cfq_dispatch_insert() 関数処理の内部では、cfq_cfqq_del_rr() 関数が実行される。
  cfq_cfqq_del_rr() では、対象のリクエストキューを cfq_data の service_tree メンバで表される rr ツリーから除き、service_tree オブジェクトの left メンバが表すノードが現在着目しているノードならば NULL を設定するという処理を行う。
  これにより、__cfq_forced_dispatch_cfqq() から返った後の判定処理において、cfq_rb_first() 関数は rb_first() を呼び出して別のリクエストキューを取得する事になる。
  cfq_data オブジェクトの service_tree メンバは、cfq_data オブジェクトが持つ cfq_queue オブジェクトを管理する rb ツリー構造のルートを表す。またこのツリーはラウンドロビンで選択される為、カーネル内部では rr ツリーと呼ばれている。cfq_service_tree_add() によってリストに cfq_queue オブジェクトが追加され、 cfq_del_cfqq_rr() 関数によって指定された cfq_queue オブジェクトが service_tree から除かれる。

  これが elevator_dispatch_requests メソッドにおいて、引数 force に 1 が指定された時の CFQ での実装である。force 変数に 0 が設定された時の処理については次回に示す。


[1] Documentation/block/biodoc.txt
[2] cfq_queue オブジェクトを、指定した cfq_data オブジェクトの管理下に追加する処理
[3] cfq_data オブジェクトの管理下にある cfq_queue オブジェクトを覗く処理
[4] http://dev.ariel-networks.com/Members/ohyama/25cbi-o-30b930b130e530fc30e9-305d306e5
[5] http://dev.ariel-networks.com/Members/ohyama/25cbi-o-30b930b130e530fc30e9-305d306e5