BFQ I / Oスケジューラの方が優れています

KMSは、アトミック操作に加えて、Linuxワークステーションユーザー向けに、入出力サブシステム用のBFQ （Budget Fair Queue）スケジューラーという別の便利なイノベーションを最近導入しました。 これは、9年ほど前にデビューしたデフォルトのCFQ（完全に公平なキュー）の改善ですが、バージョン4.12でのみメインブランチに導入されました。

プランナーの原則について話す前に、Paolo Valente開発者デモをチェックしてください。これにより、継続する意欲が高まります。 スクリーンショットは、CFQとBFQの 2つのスケジューラのディスクからファイルを読み取るための10個のバックグラウンドタスクを持つプレーヤーの開始を示しています。 それらのどれがそのような負荷で開始しなかったと思いますか？

アルゴリズムについて簡単に説明します。 CFQと同様に、同期リクエストはタスクキューにグループ化され、非同期リクエストはデバイスごとにグループ化されます。 次に、 BFQは、タイムスタンプに基づいて新しいタスク用に単純なラウンドロビンスケジューラーを変換します。これにより、アルゴリズムは、ディスクセクターがメジャーとして機能する予算を基礎として使用します。 タスクの性質と動作に応じて、予算が変更される可能性があり、 BFQはディスクデータのフローがタスク間で適切に分散されるようにします。

BFQは常に 1つのタスクでのみ機能します。 デバイスドライバーが次のタスクを処理する準備ができると、アルゴリズムはキューからC-LOOK



指定された順序で最初のタスクを照会し、実行のためにドライバーに渡します。

バジェットプランナーポリシー

擬似コードのアルゴリズムの個々の側面を詳しく見てみましょう。 add_request



関数add_request



新しいRリクエストをadd_request



他のリクエストが受信されていない場合は、それだけです。

 active_appl = none ; //     remaining_budget = 0 ; //    //:  ,    add_request(int i, request R) { appl = applications[i] ; //   i //     R; enqueue(R, appl.queue) ; if (appl.queue.size == 1) { //   if (appl != active_appl) b-wf2q+_insert(appl) ; else //   if(waiting_for_next_req()) //  unset_timer() ; //   } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

論理スケジューラー 。

図では、矢印はリクエストからディスクデバイスへのパスを示し、楕円はアルゴリズムと操作を示します。

すべてのアプリケーションがアイドル状態の場合、またはアクティブなアプリケーションが次のリクエストを待機している場合、 dispatch



関数はno request



返しno request



。 一方、割り当てられた予算内でリクエストを処理できなかった場合、アプリケーションはリストから削除されます。 関数呼び出しb−wf2q+update_vfintime



は、アプリケーションのタイムスタンプを更新し、リクエストが処理されている間の有効な時間のみが考慮されるようにします。 アプリケーションが要求キューのリセットに失敗したという事実は、要求パッケージが割り当てられた予算を超えたことを意味します。 したがって、予算は 、特定のしきい値レベルB _i、maxを超えない特定の値だけ増加する必要があります 。

 request dispatch() { // if (all_applic_are_idle() OR waiting_for_next_req()) return no_request ; if(active_appl ! = none AND remaining budget < C−LOOK next req (active_appl.queue).size ) { b−wf2q+update_vfintime(active_appl, active_appl.budget − remaining_budget); if(active_appl.budget + BUDG_INC_STEP <= active_appl. max_budget) active_appl.budget += BUDG INC STEP ; else active_appl.budget = active_appl.max budget ; b−wf2q+ insert(active_appl) ; active_appl = none ; } if (active_appl == none ) { //       b-wf2q+ active_appl = b−wf2q+ get_next_application() ; remaining budget = active_appl.budget ; } //          next_request = dequeue_next_req(active_appl.queue) ; remaining budget −= next_request.size; if(is empty (active_appl.queue)) set_timer(T_wait) ; //    //   b-wf2q+ b-wf2q+_inc_tot_service(next_request.size) ; return next_request ;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

さらに、新しい予算を持つアプリケーションは、スケジューラB-WF ² Q +に分類されます。 現在、B-WF ² Q +スケジューラーのキューからアクティブなアプリケーションが残っていない場合、次が実行され、すべてが新しくなります-アクティブなアプリケーションの場合、次のリクエストRは類似したものの文字列から取得され、予算が割り当てられます。

最後に、アクティブなアプリケーションキューが使い果たされています。 新しいタイマーは現在の時間+ T _waitに等しく設定され、新しいリクエストがない場合、 timer_expiration



関数が機能します。 アプリケーションはアイドル状態であると宣言され、新しい予算は前の予算と同じ新しい予算を受け取ります。

 timer_expiration() active_appl.budget = active_appl.budget − remaining_budget ; b-wf2q+_update_vfintime(active_appl, active_appl.budget); active_appl = none ; //   , //dispatch()   .
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

また、内部アルゴリズムC-LOOK B-WF ² Q +に言及する価値があります。

• C-LOOK（Circular LOOK）は、ディスクヘッドが一方の端から他方の端に移動し、着信要求を処理するディスクスケジューラです。 次に、最後の要求の後、C-SCANアルゴリズムとは異なり、 フィニッシュラインに到達することなく 、反対方向に方向を変更します。
• B-WF ² Q + WF ² Q +パケットスケジューラのブロックスケジューラバージョン。 Weighted Fair Queueアルゴリズムを使用すると、チャネルの一部が割り当てられる割合に応じて、各スレッドの優先順位または重みを設定できます。

それで、取引は何ですか？

ここで、ボロミアの写真を投稿する必要があります。ボロミアは、いらいらして、メインのLinuxカーネルブランチにスケジューラを追加するだけではいけないと言っています。 鏡の輝きになめられたコードに加えて、ここでは忍耐と高度なソーシャルコミュニケーションスキルが必要です。 長い間BFQをピクルスにする必要がある具体的な理由はなく、著者の柔軟性のない永続性を称賛することだけが残っています。 BFQは以前のブロックデバイスAPIしか使用できなかったため、新しい最高のスケジューラーの受け入れを拒否した公式の理由は、新しいマルチキューAPIのサポートの欠如です。 幸いなことに、 マルチキューAPIメンテナーのJens Axboe が救助に来て、一緒になって望みの結果を達成しました。

Hitachi HDDでgnome-terminalアプリケーションを起動します（小さい方が良い） 。

現時点では、これらのディストリビューションのユーザーは、USBフラッシュドライブからファイルをコピーしたり、大規模なアーカイブを展開したり、I / Oリソースを必要とするその他の操作をしながら、安全に映画を見ることができます。 それらでは、 BFQスケジューラーがデフォルトで使用されます 。

• マンジャロ
• マゲイア
• オープンマンドリバ
• サバヨン
• Arch Linux ARM
• ローザ

Hitachi HDDでのパフォーマンス（多いほど良い） 。

オプションで、 BFQスケジューラは次の場所で利用できます。

• アーチ
• openSUSE
• PCLinuxOS
• ジェンツー

いくつかの簡単な手順が必要です 。 まず、GRUBブートローダーの行を次のように変更します。

 GRUB_CMDLINE_LINUX="scsi_mod.use_blk_mq=1"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、再起動後、必要なスケジューラの存在を確認します。

 (5:500)$ sudo cat /sys/block/sda/queue/scheduler noop bfq deadline [cfq]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

デフォルトのスケジューラを変更します。

 (5:501)$ sudo echo bfq > /sys/block/sda/queue/scheduler
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ファイル/path/to/rules.d/60-scheduler.rules



作成してudev



ルールを適用することにより、これをより徹底的に行うことができます。

 ACTION=="add|change", KERNEL=="sd[az]", ATTR{queue/scheduler}="bfq"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

関連資料

• BFQの前進
• バジェットフェアキューイング（BFQ）Storage-I / Oスケジューラー
• 公平な帯域幅分散を備えた高スループットのディスクスケジューリング
• Linux 4.12カーネルの最大の魅力