ユーザ空間でプロセスをスケジューリングする方法の模索

この記事では、ユーザ空間プログラムでプロセススケジューリングをある程度制御する方法について、15th ACM SIGOPS Asia-Pacific Workshop on Systems (APSys 2024) で発表した論文の大まかな日本語訳を元に紹介します。

以下、参考資料へのリンクです。よろしければ併せてご覧ください。

• 論文へのリンク
• 補足資料へのリンク
• 関連記事へのリンク

特に、技術的な背景情報は上記リンク先の関連記事にいくつか記載がありますので、こちらを読み始める前にそちらを見ていただくと良いかもしれません。

概要 (Abstract)

• この論文では、一般的な OS 機能のみを利用してユーザ空間でプロセススケジューリングポリシーを実装可能にするプログラミングテクニックを模索します。
• 我々はプロセスの優先度を操作することで特定のプロセススケジューリングポリシーを既存のカーネルのプロセススケジューラの上に実装する優先度昇降トリックという手法を提案します。
• 実験では、物理・仮想マシン両方の環境において、優先度昇降トリックの負荷を評価するとともに、三つの用途、マイクロ秒単位のタイムスライス、テーブルベースのスケジューリング、また適宜スレッドを切り替えることで head-of-line blocking を回避するスケジューリングが、通信を行うサーバプログラムの性能に寄与することを示します。

1 導入 (Introduction)

背景

• プロセススケジューリングは、複数プロセスが１つの CPU コアの上で動作することを可能にする上で必要な機能の一つです。
• プロセススケジューラと、スケジューリングポリシー・アルゴリズムは多くの場合で OS のカーネルの一部として実装されてきました。
• また、OS のカーネルに実装されているプロセススケジューラは、幅広い種類のプログラムが、最高ではないにしても十分に高い性能を発揮できるというような、一般性を設計の目標としている場合が多いです。
• 一方で、近年の研究では、特定のワークロードへ特化したプロセススケジューリングポリシーを採用することで、性能の向上が期待できるということが報告されています。

問題と関連研究

ですが、そのような特定のワークロードへ特化したプロセススケジューリングポリシーは、それらを実装すること、また利用することが困難である、という問題があります。

• 固有のカーネルもしくはハイパーバイザ拡張：これまでに提案されてきたスケジューリングの改善に寄与する仕組 [1, 4, 10, 22, 23, 24] の多くはカーネルまたハイパーバイザの公式のブランチにマージされていない独自の変更に依存しており、結果として、セキュリティ、安定性、将来のメンテナンスについての懸念から、多くの利用者にとって採用のハードルが高くなっています。
• 固有のユーザ空間ランタイム：ファイバーやコルーチンと呼ばれるようなユーザ空間におけるスレッド実装の上にスケジューリングの改善を行う提案 [9, 18, 20] も存在しますが、それらはスケジューリング対象となるユーザ空間プログラムが直接それら固有のユーザ空間スレッドランタイム実装を統合する必要があり、採用が困難である場合が多いです。
• 開発フレームワーク：研究コミュニティではプロセススケジューラを開発するためのフレームワーク [7, 11, 17] が提案されています。それら開発フレームワークはプロセススケジューラ開発の柔軟性を高める一方で、それらもカーネルの公式のブランチにマージされていない独自の変更に依存していることから、利用者にとって、それらフレームワークの上に実装されたシステムの利用が困難である場合が多いです。
• 一般的な OS 機能の利用：いくつかの既存研究では、一般的な OS 機能を利用してプロセススケジューリングポリシーを実装することを提案 [3, 5, 19] していますが、それら提案手法は、ストリーム処理 [3, 19] やサーバレス環境 [5] のような特定の用途のために設計されており、柔軟性が十分ではなく、例えば、過去に提案された通信システムの遅延を低減することを目指したスケジューリングポリシー [10] 等を実装するのは容易ではないというような課題があります（3.4 章）。

このように、過去の研究によって、特定のワークロードへ最適化されたプロセススケジューリングポリシーの利点が示されている一方で、簡単にプロセススケジューリングポリシーを開発・利用できる仕組みがないことで、それら最適化されたプロセススケジューリングポリシーの採用が困難になっていると考えます。

本研究

本研究では、上記の問題の解決に向けて、ユーザ空間で一般的な OS 機能のみを用いて、また、固有のユーザ空間ランタイムに必ずしも依存することなくプロセススケジューリングポリシーを実装する方法を模索し、優先度昇降トリック (priority elevation trick) を提案します。

2 優先度昇降トリック (The Priority Elevation Trick)

本取り組みの技術的な目標は、一般的な OS 機能のみを用いて、ユーザ空間プログラムが、特定の CPU コアの上で、特定の瞬間に実行されるプロセスを選択できるようにすることです。

基本的なアイデア

• 一般的なカーネル空間のプロセススケジューラの挙動として、優先度が高いプロセスほど長い実行時間を付与します。
• ここで極端な場合について考えます。あるプロセスが他のプロセスと比較して、圧倒的に高い優先度が割り当てられていた場合、その優先度の高いプロセスがほとんどの時間スケジュールされ、それ以外のプロセスはほぼスケジュールされなくなります。
• つまり、我々が実行したいと思うプロセスと、それ以外のプロセスの間に十分に大きい優先度の差を設定することで、間接的に、カーネル空間のプロセススケジューラに対して、特定のタイミングで実行してほしいプロセスをリクエストできると考えられます。
• 提案手法である優先度昇降トリックではカーネルが提供する優先度設定の仕組みを用いて、ユーザ空間でプロセススケジューリングポリシーを実装します。

操作用インタフェース

今回はプロトタイプを Linux 上で実装し、特に、以下の機能をカーネル内のプロセススケジューラの挙動を操作するために利用します。

• sched_setscheduler：極端な優先度差を設定するために、スケジューリング対象のプロセスに、sched_setscheduler システムコールを用いて、最も高い優先度の値を持つプロセスを実行し続けるという特性を持つ SCHED_FIFO ポリシーを適用します。（SCHED_FIFO 含むリアルタイムスケジューリングポリシーの挙動についてはこちらの記事で紹介しておりますのでよろしければ併せてご覧ください。）
• sched_setaffinity：マルチコア環境において、カーネルのプロセススケジューラに対して、特定のプロセスを任意の CPU コアへ紐づけることをリクエストするために sched_setaffinity システムコールを利用します。

プロセスの種類

今回は、プロセスを二種類に分類し、それぞれ以下のように呼称します。

• 通常プロセス：文字通り通常のプロセスで、スケジューリングは行いません。
• スケジューラプロセス：通常プロセスをスケジューリングするプロセスです。

CPU コア割り当てパターン

優先度昇降トリックでは、二通りの CPU 割り当てパターンを採用することができ、以下のように呼称します。

• 共有（Shared）パターン：共有パターンでは、スケジューラプロセスと、そのスケジューラプロセスによってスケジュールされる通常プロセスが同じ CPU コアで動作します。マルチコア環境では、同一の設定を利用可能な CPU コア全てに適用します。
• 占有（Dedicated）パターン：占有パターンでは、スケジューラプロセスが１つの CPU コアを占有し、そのスケジューラプロセスがスケジュールする通常プロセスは別の CPU コアで動作させます。１つのスケジューラプロセスは複数 CPU コアで動作する通常プロセスをスケジューリングすることができます。

優先度の数値

優先度昇降トリックでは、少なくとも、高、中、低、の三種類の優先度の値を利用します。これらの値の設定に sched_setscheduler を利用します。

• 高：高の値は、スケジューラプロセスへ割り当てられます。
• 中：中の値は、スケジューラプロセスが実行を許可したプロセスへ割り当てられます。
• 低：低の値は、スケジューラプロセスが実行を許可していないプロセスへ割り当てられます。

優先度の初期設定

初期設定において、上記優先度の値をスケジューラ・通常プロセスそれぞれに割り当てます。この初期設定完了後、全ての通常プロセスは低の値が割り当てられ、結果として、SCHED_FIFO の特性により、高の値の優先度を持つスケジューラプロセスはいつでも動作したいと思ったタイミングで動作ができます。

CPU コア割り当てについての初期設定

ある程度典型的な設定において、特定の CPU コアにおけるスケジューリングを担当するスケジューラプロセスは、その CPU コアで動作させる通常プロセスのリストを保持しており、初期設定として、sched_setaffinity を用いてそれら通常プロセスをカーネルのプロセススケジューラに、その CPU コアへの紐付けを行うことをリクエストします。

優先度の昇降

特定の CPU コアにおけるスケジューリングを担当するスケジューラプロセスは、次に実行すべき通常プロセスを決定すると、その通常プロセスの優先度の値を、低から中へ上昇させます。もし、それまでその CPU コアで動作していた優先度に中の値を持つ通常プロセスがあれば、その通常プロセスの優先度の値を中から低へ下げます。これ以降のスケジューラプロセスの挙動は、採用している CPU コア割り当てパターンによって変わります。

• 共有パターンを採用している場合：共有パターンが採用されている場合は、上記の優先度操作の後も、スケジューラプロセスは、それ自体が動作している CPU コアの上で最高優先度のプロセスであり続けるため、結果として、そのままではスケジューラプロセスが選択した通常プロセスへ処理が切り替わりません。なので、選択された通常プロセスへ処理を切り替えるために、スケジューラプロセスは sleep 系の関数や timerfd への read システムコールを呼び出すことで、カーネルのプロセススケジューラに対して、CPU サイクルを一定時間手放すことを許容する意思表示を行います。これにより、カーネルのプロセススケジューラは、スケジューラプロセスをスケジューリングの候補から外すとともに次に実行すべきプロセスを探しますが、SCHED_FIFO の最も優先度の値が高いプロセスを実行するという特性により、先ほどスケジューラプロセスが優先度を低から中へ繰り上げた通常プロセスが次に実行されるべきプロセスとして選択され、処理がそちらへ切り替わります。また、一定時間経過後、スケジューラプロセスが sleep から復帰すると、スケジューラプロセスの優先度が高であることから、それまで実行されていた優先度が中の通常プロセスはすぐに中断され、カーネルのプロセススケジューラは、スケジューラプロセスを実行します。ここで、スケジューラプロセスは上記ステップを繰り返すことで次に実行すべきプロセスの選択と切り替えを行うことができます。（この辺りの挙動については、こちらの記事に少し説明があります。）
• 占有パターンを採用している場合：占有パターンが採用されている場合、スケジューラプロセスと通常プロセスは別の CPU コアに紐づけられているため、スケジューラプロセスの実行は、選択された通常プロセスの実行を妨げないことから、通常プロセスを動作させるために、共有パターンの場合のような sleep 関数の呼び出し等は不要です。

利用可能なプログラミング言語

優先度昇降トリックは特定のプログラミング言語には依存せず、sched_setscheduler と sched_setaffinity システムコールを呼び出すことができるプログラミング言語であれば、優先度昇降トリックを使ってプロセススケジューリングポリシーを実装することが可能です。

適用可能な対象

• 優先度昇降トリックは sched_setscheduler と sched_setaffinity を通して制御可能な対象であれば適用可能です。
• 具体的には、一般的なプロセス、POSIX thread (pthread)、また、QEMU [2] 等の仮想化ソフトウェアが立ち上げる仮想 CPU （内部的には pthread であるため）に対して適用可能です。

既存のプログラムの変更

優先度昇降トリック自体は、通常プロセスとスケジューラプロセスが独立していることから、既存のプログラムに変更を加えずとも適用が可能です。一方で、優先度昇降トリックを実装の基礎として利用したプログラムを設計・実装することも可能です。前者は、3.1、3.2、3.3 章の実験で、後者は 3.4 章の実験に見られます。

制限・制約

優先度昇降トリックの制限・制約は、スケジューラプロセスが、通常プロセスのスリープと起床を効率よく検出する方法がなく、それらをスケジューリングの意思決定に含めることが困難であるという点です。ptrace や BPF [14] のような仕組みを利用することも考えられますが、それらには性能面での負荷が伴います。なので、優先度昇降トリックは、基本的には、select や poll のようなカーネルのイベント関連 API に強く依存するようなプログラムのためのプロセススケジューリングを行うような場合には向いていないと考えます。一方で、この制限・制約があったとしても、この優先度昇降トリック自体は有用な場合もあると考えられ、３章では、実験を通してその有用性を示します。

sched_ext との特性の比較

論文の査読期間に、sched_ext [15] という BPF プログラムで挙動を制御可能なスケジューリングクラスが Linux の公式ブランチに取り込まれる予定であるという発表がされました。sched_ext と優先度昇降トリックの主な違いは、sched_ext ではスケジューリングについての意思決定がカーネルの中で行われる一方、優先度昇降トリックでは、意思決定がユーザ空間で行われる点です。sched_ext の利点は、上記、優先度昇降トリックの制限・制約がないことです。一方で、BPF はシステムの性能低下に繋がるいくつかの制限 [16] があり、sched_ext はそれらを回避するのは困難です。また、カーネル空間はスケジューラにとって常に最適ではなく、例えば、カーネルをバイパスするような通信システムの用途では、ユーザ空間の方が意思決定に必要な情報へ効率良くアクセスできる場合もあります。これらのことから、sched_ext と優先度昇降トリックにはそれぞれ異なる最適な利用シナリオが存在すると考えます。

3 評価 (Evaluation)

優先度昇降トリックの評価結果を報告します。

実験環境

以下の設定の２台のマシンを利用し、通信を行う実験においては、片方をサーバマシン、もう一方をクライアントマシンとします。

• CPU：2 x 16-core Intel Xeon Gold 6326 CPU @ 2.90 GHz（合計 32 CPU コア）
• NIC：Mellanox ConnextX-5 100 Gpbs（２台のマシンはケーブルで直接接続）
• OS：Linux 6.2
• 仮想化ソフトウェア：QEMU [2]/KVM [12]

SCHED_FIFO を適用したプロセスがスロットリングの影響を受けないよう sched_rt_runtime_us のパラメータを設定します。（こちらのパラメータ設定についてはこちらの記事をご覧ください。）

我々が実験のために作成したプログラムは C 言語で実装されています。

3.1 負荷 (Overheads)

遅れ

• まず、優先度昇降トリック自体がスケジューリングにどの程度の遅延の要因となるかを調べます。
• 実験のために二つのスケジューリング対象を同一の CPU コアの上で動作させます。それらスケジューリング対象は busy ループを実行します。
• スケジューリング対象については、二つの、独立したプロセス、同一のプロセスに属する pthread、異なる仮想マシンに属する vCPU、の三通りについて計測します。
• スケジューリング対象がプロセスと vCPU の場合は、それらとは独立したスケジューラプロセスがスケジューリングを行い、pthread の場合は、スケジューリング対象の pthread が属するのと同じプロセスの中で、スケジューリングを行う pthread （スケジューラ pthread と呼びます）を立ち上げます。
• スケジューラプロセス・pthread は、5 マイクロ秒ごとに実行されるスケジューリング対象を切り替えます。共有パターンが適用されている場合には、5 マイクロ秒を指定して usleep 関数を呼び出し、占有パターンが適用されている場合には、5 マイクロ秒経過するまで現在時刻を確認し続けます。

スケジューリング対象	パターン	スケジューリング対象が一度スケジュールされてから（実行され始めてから）切り替えられるまで（deschedule されるまで）の時間（マイクロ秒）	スケジューリング対象が切り替えられてから（deschedule されてから）再スケジュールされるまで（再度実行されるまで）のインターバル（マイクロ秒）
プロセス	共有	5.5	9.6
プロセス	占有	5.0	5.0
pthread	共有	5.5	9.2
pthread	占有	5.0	5.0
vCPU	共有	7.2	14.4
vCPU	占有	5.0	5.0

• 結果は上のテーブルのようになりました。標準偏差はどの場合も１マイクロ秒以下でした。
• 理想的には、スケジューリング対象が一度スケジュールされてから（実行され始めてから）切り替えられるまで（deschedule されるまで）の時間と、スケジューリング対象が切り替えられてから（deschedule されてから）再スケジュールされるまで（再度実行されるまで）のインターバルの両方は 5 マイクロ秒です。
• この理想的な切り替えは、占有パターンが適用されたときには達成できましたが、共有パターンが適用された場合には、遅れが観測されました。
• また、他の切り替え頻度、10 マイクロ秒、20 マイクロ秒、50 マイクロ秒、100 マイクロ秒、150 マイクロ秒の場合の計測も行いましたが、それらどの場合においても、共有パターン適用時に、プロセス、pthread、vCPU それぞれの場合について、スケジューリング対象が一度スケジュールされてから（実行され始めてから）切り替えられるまで（deschedule されるまで）の時間が 0.5 マイクロ秒、0.5 マイクロ秒、2.2 マイクロ秒 が増加、スケジューリング対象が切り替えられてから（deschedule されてから）再スケジュールされるまで（再度実行されるまで）のインターバルは 4.6 マイクロ秒、4.2 マイクロ秒、9.4 マイクロ秒の増加が観測されました。一方で、占有パターンが適用された場合にこれらの増加は見られませんでした。

CPU サイクル

• 次に、優先度昇降トリックが消費する CPU サイクルを調べます。
• 二つのスケジューリング対象を実行し、片方で busy ループ、もう一方で sysbench [13] の CPU ベンチマークを実行します。
• 上記の遅れの計測で利用したスケジューラプロセスを利用して二つのスケジューリング対象を異なる頻度で切り替えます。

• sysbench のスコアは上のようになりました。縦軸に表示されている値は、実験で得られた sysbench のベンチマークスコアを、sysbench を実行するスケジューリング対象が１CPU コアを占有した時の性能で割ったものです。
• 各線の説明として Process はスケジューリング対象がプロセスの時、vCPU は仮想 CPU が対象の時で、Shared は共有パターン適用時で、Dedicated は占有パターンが適用されていることを表します。
• 二つのスケジューリング対象が公平に１つの CPU コアを共有しているため、理想的には、上のグラフの数値は 0.5 であるべきで、観測された値と 0.5 との差が優先度昇降トリック実行のために消費された CPU サイクル（時間）を表すものであると考えられます。
• 基本的に、高い頻度での切り替えは大きなベンチマークスコアの低下に繋がる傾向が見られます。
• スケジューリング対象が vCPU の場合の方がプロセスの場合と比較して大きなスコアの低下が見られます。これは、ホストと仮想マシン間でのコンテキスト切り替えコストによるものと考えられます。
• 占有パターンは、共有パターンの場合と比較して、スコアの低下が低く抑えられています。
• ですが、注意として、共有パターンでは、スケジューラプロセスが sysbench が動作しているのとは別の CPU コアで動作するため、このグラフにはスケジューラプロセス自体が消費した CPU サイクルが反映されていません。一方、占有パターンでは、スケジューラプロセスが消費した CPU サイクルはこのグラフに見られるスコア低下に反映されています。

3.2 マイクロ秒単位のタイムスライス (Microsecond-scale Time Slicing)

• 過去の研究 [1, 23] では、マイクロ秒単位のタイムスライスを適用すると、性能が向上するワークロードがあることが示されています。
• 一方で、現状、Linux で一般的な設定方法で適用可能な最小のタイムスライスは１ミリ秒です。この値は、カーネルのコンパイル時のパラメータである CONFIG_HZ の値に起因し、カーネルのビルドシステムによって設定可能な値の範囲が限定されています。
• これは、ソースコードが改変されていない Linux が動作している多くのサーバにおいて、既存の設定用インタフェースを利用した方法ではマイクロ秒単位のタイムスライスを採用できないということを意味すると考えられます。
• 優先度昇降トリックを利用すると、上記の制約があったとしても、ソースコードの改変を施していない Linux 上でマイクロ秒でのタイムスライスを適用できます。
• ここでは、優先度昇降トリックにより実現されたマイクロ秒単位のタイムスライスがアプリケーション性能にどのような影響があるかを調べます。

ベンチマーク

• 実験のために、簡単なサーバプログラムを実装しました。このプログラムはユーザ空間で iip [25] という自作した TCP/IP スタック（こちらについては、この記事をご覧ください）を動作させ、パケット I/O には Data Plane Development Kit (DPDK) [8] を利用します。このサーバプログラムは 64 バイトの TCP ペイロードを返す簡易な HTTP サーバとして機能します。
• サーバマシン上で上記のサーバプログラムと、単純な busy ループを実行するプログラムを同じ１つの CPU コア上で動作させ、これら二つを実行するプロセスをスケジューラプロセスによって切り替えます。
• ベンチマーククライアントとして、クライアントマシンの 32 CPU コア全てを利用し、wrk2 [6, 21] を実行し、128 並列 TCP 接続を通してサーバプログラムへリクエストを送ります。

結果

• 結果は上のようになりました。４つのグラフはそれぞれスケジューリング対象がプロセスの場合と仮想 CPU の場合について、CPU コア割り当てパターンが共有 (Shared) パターンと占有 (Dedicated) パターンが適用された場合の結果です。
• 短いタイムスライスは基本的に遅延を下げる効果が見られます。
• スループットは上で計測した各タイムスライスごとの CPU サイクル消費を反映していそうです。
• ただ、100 マイクロ秒と 150 マイクロ秒の時の差に見られるように、長いタイムスライスが常に高いスループットに繋がるというわけでもないようです。
• この実験を通して、タイムスライス設定はアプリケーション性能において重要であり、優先度昇降トリックはそれをマイクロ秒単位で設定可能にしていることを確認しました。

3.3 テーブルベースのスケジューリング (Table-driven Scheduling)

• 過去の研究 [22] により、固定のスケジューリングテーブルを元にした、テーブルベースのスケジューリングがアプリケーション性能に貢献することが示されています。
• ですが、一般的なカーネル空間のプロセススケジューラはテーブルベースのスケジューリングを可能にするようなインタフェースを提供していません。
• ここでは、優先度昇降トリックを利用してテーブルベースのスケジューリングを実装し、アプリケーション性能についての影響を調べます。

ベンチマーク

• 今回の実験では、３つの A、B、C で識別されるスケジューリング対象を同一の CPU コア上で動作させます。A は上述のサーバプログラムを実行し、B と C は busy ループを実行します。
• また、CPU 時間の割り当て設定として、A が 50%、B と C はそれぞれ 25% ずつ CPU サイクルを消費するようにするとします。
• この場合、A、B、C の各タイムスライスごとの実行の順番として、A-A-B-C と A-B-A-C の二通りが考えられます。
• ここでは、優先度昇降トリックを利用して上記 A-A-B-C と A-B-A-C の二通りのスケジューリングテーブルをスケジューラプロセスへ実装しました。
• サーバ側はタイムスライスを 50 マイクロ秒に設定し、クライアントは先ほどと同じ wrk2 を利用してサーバプログラムの性能を計測しました。

結果

• 結果は上のようになりました。４つのグラフはスケジューリング対象がプロセス・仮想 CPU の場合と、共有・占有パターンがそれぞれ適用された場合の結果を表示したものです。
• A-B-A-C の場合は A-A-B-C の場合と比較して常に低い 99 パーセンタイル遅延が観測されています。
• これは、A が A-A-B-C の場合は 100 マイクロ秒おきにしかスケジュールされない一方、A-B-A-C の場合は 50 マイクロ秒おきに実行されるため 99 パーセンタイル遅延が低く抑えられていると考えられます。
• 優先度昇降トリックによって実現されたテーブルベースのスケジューリングがアプリケーションの性能に寄与することを確認できました。

3.4 Head-of-Line Blocking を回避するスケジューリング (Preemptive Scheduling)

• 過去の研究 [10] では、リクエストに対してレスポンスを返すようなサーバプログラムが特にリクエストの処理時間にばらつきがある場合に、サーバプログラムのスレッドがある処理に時間がかかるリクエストへの対応にかかりっきりになってしまい、後続のリクエストへの応答が大幅に遅れてしまう head-of-line blocking という問題を緩和するために、あるスレッドが一つのリクエストに対する処理時間が閾値を超えた時にそのスレッドの実行を中断し、別のスレッドへ切り替えて、後続のリクエストを処理するようにすることで head-of-line blocking による遅延の増加を低減できることが示されています。
• ここでは、優先度昇降トリックを用いて、同様の機能を実装し、性能についての分析を行います。

実装

今回の実装では先の実験で利用したサーバプログラムを拡張します。また、CPU コア割り当てパターンとして、共有パターンを適用します。

• pthread のタイプ：この実装では、worker、dispatcher、switcher の三種類の pthread を利用します。一つの CPU コア上には、複数の worker、一つの dispatcher、一つの switcher pthread が動作し、スケジューリングは dispatcher pthread によって行われます。
  • worker pthread：worker pthread はアプリケーション水準のリクエストを処理します。この中に TCP/IP やパケット I/O についての処理は含まれていません。worker pthread  はそれぞれ現在リクエストを処理しているかどうかを表すフラグを保持しています。
  • dispatcher pthread：dispatcher pthread は受信したパケットに対して TCP/IP の処理を行い、アプリケーション水準のリクエストを抽出し、それをリクエストキューを通じて、worker pthread へ渡すとともに、その worker pthread を優先度昇降トリックを用いてスケジュール・実行します。worker pthread は受け取ったリクエストの処理が完了すると、完了キューを通して dispatcher pthread へ通知し、dispatcher pthread はその完了キューの状態に合わせてクライアントへレスポンスデータを送信します。
  • switcher pthread：switcher pthread は、設定された閾値以上の間、継続して動作し続けた worker pthread を優先度昇降トリックを使って切り替えます。switcher pthread はそれが実行するループの中で timerfd に対して read システムコールを呼び出し、通常はスリープ状態になっています。
• 四つの優先度の値：この実装では、４つの優先度の値、１、２、３、４を利用します。値の大きい方が高い優先度を表すとします。４は、switcher pthread、３は dispatcher pthread が実行を許可した worker pthread、２は dispatcher pthread、１は dispatcher pthread によって実行が許可されていない worker pthread に割り当てられます。システム初期化後は、全ての worker pthread が優先度１を持つようになっており、また、先述の通り switcher pthread は通常時はスリープ状態になっているため、優先度２を持つ dispatcher pthread が実行されます。
• dispatcher pthread のループの上半分：dispatcher pthread が実行するループの上半分では、受信したパケットについて TCP/IP の処理を行い、アプリケーション水準のリクエストを抽出します。そのリクエストをリクエストキューへ追加した後、現在、リクエストを処理していない worker pthread を一つ選び、その worker pthread の優先度の値を１から３へ上昇させることで、選択された worker pthread へ処理を切り替えます。
• worker pthread のループ：worker pthread のループでは、まず、リクエストキューからリクエストを取り出し、そのリクエストのための処理を始める前に、switcher pthread がスリープするために read している timerfd が一定時間経過後に switcher pthread を起床させるよう設定し、リクエスト処理完了後にこの timerfd が switcher pthread を起床させる設定を解除します。この後ループの最初に戻りますが、リクエストキューが空になった場合には、worker pthread は自らの優先度の値を３から１へ下げることで、処理を dispatcher pthread へ戻します。
• switcher pthread のループ：worker pthread が timerfd の設定をキャンセルする前に、設定した時間が経過した場合、switcher pthread が起床します。switcher pthread は実行されていた worker pthread の優先度の値を３から１へ下げます。この後、switcher pthread は再度、timerfd に対して read システムコールを発行し、スリープ状態に入ります。そうすると、、処理が dispatcher pthread へ戻ります。
• dispatcher pthread のループ下半分：dispatcher pthread は、worker pthread が switcher pthread によって実行が中断された場合には、別の worker pthread を選択し優先度昇降トリックを使ってスケジュール・実行します。リクエストキューから全てのリクエストが取り出された後で、まだリクエストへの対応を行なっている worker pthread が存在した場合には、dispatcher pthread はそれぞれを設定された時間だけ動作させます。ループの最後で、完了キューの状態に応じて、クライアントに対してレスポンスデータを送信します。

ベンチマーク

• サーバマシンは上記の実装を１CPU コアを利用して実行します。クライアントマシンは wrk2 を使って負荷をかけます。
• 実験には、過去の研究で採用されている設定を利用します。この設定では、リクエストの 99.5% は 0.5 マイクロ秒で処理が完了し、残りの 0.5% の処理には 500 マイクロ秒を要します。この設定はグラフ中では bimodal と記載します。また、全てのリクエストが 0.5 マイクロ秒で処理が完了する場合（グラフ中では fixed と記載）についても計測します。

結果

• 結果は上のようになりました。w/ preemption という表記が上記の head-of-line blocking 回避の最適化を含む実装を利用した場合で、w/o preemption 表記はその最適化をしていない実装の性能です。
• 二つの fixed の場合の違いは、worker pthread による timerfd 操作のコストから来ています。
• head-of-line blocking 回避の最適化を含む実装の二つの場合の違いは、ワークロードが１リクエスト 500 マイクロ秒を要する処理を含むかどうかの違いから来ています。
• bimodal の場合に、head-of-line blocking 回避の最適化が含まれていない場合は、99 パーセンタイル遅延の値が 500 マイクロ秒を超えています。一方、最適化が適用されている場合は、500 マイクロ秒より小さく抑えられています。この結果から、優先度昇降トリックを用いて実装された機構が head-of-line blocking 問題に起因する遅延の低減に寄与することが確認できました。

4 まとめ (Conclusion)

本論文では一般的な OS 機能を用いるだけでもユーザ空間のプログラムがある程度プロセススケジューリングを制御可能であることを示しました。

執筆者は優先度昇降トリックは多くの用途において必要十分な柔軟性と機能性を備えていると考えており、手軽なプロセススケジューリングポリシーの実装方法を探している研究者や開発者の人たちのお役に立てばと思っております。

参考文献

• [1] Jeongseob Ahn, Chang Hyun Park, Taekyung Heo, and Jaehyuk Huh. 2018. Accelerating critical OS services in virtualized systems with flexible micro-sliced cores. In Proceedings of the Thirteenth EuroSys Conference (Porto, Portugal) (EuroSys ’18). Association for Computing Machinery, New York, NY, USA, Article 29, 14 pages. https://doi.org/10.1145/3190508.3190521
• [2] Fabrice Bellard. 2005. QEMU, a Fast and Portable Dynamic Translator. In 2005 USENIX Annual Technical Conference (USENIX ATC 05). USENIX Association, Anaheim, CA, 41–46. https://www.usenix.org/conference/2005-usenix-annual-technical-conference/qemu-fast-and-portable-dynamic-translator
• [3] Fausto Frasca, Vincenzo Gulisano, Gabriele Mencagli, Dimitris Palyvos-Giannas, and Massimo Torquati. 2023. Accelerating Stream Processing Queries with Congestion-aware Scheduling and Real-time Linux Threads. In Proceedings of the 20th ACM International Conference on Computing Frontiers (Bologna, Italy) (CF ’23). Association for Computing Machinery, New York, NY, USA, 144–153. https://doi.org/10.1145/3587135.3592202
• [4] Joshua Fried, Zhenyuan Ruan, Amy Ousterhout, and Adam Belay.2020. Caladan: Mitigating Interference at Microsecond Timescales. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). USENIX Association, 281–297. https://www.usenix.org/conference/osdi20/presentation/fried
• [5] Yuqi Fu, Li Liu, Haoliang Wang, Yue Cheng, and Songqing Chen. 2022. SFS: smart OS scheduling for serverless functions. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis (Dallas, Texas) (SC ’22). IEEE Press, Article 42, 16 pages.
• [6] Will Glozer. 2012. wrk: Modern HTTP benchmarking tool. https://github.com/wg/wrk.
• [7] Jack Tigar Humphries, Neel Natu, Ashwin Chaugule, Ofir Weisse, Barret Rhoden, Josh Don, Luigi Rizzo, Oleg Rombakh, Paul Turner, and Christos Kozyrakis. 2021. ghOSt: Fast & Flexible User-Space Delegation of Linux Scheduling. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles (Virtual Event, Germany) (SOSP ’21). Association for Computing Machinery, New York, NY, USA, 588–604. https://doi.org/10.1145/3477132.3483542
• [8] Intel. 2010. Data Plane Development Kit. https://www.dpdk.org/.
• [9] Rishabh Iyer, Musa Unal, Marios Kogias, and George Candea. 2023. Achieving Microsecond-Scale Tail Latency Efficiently with Approximate Optimal Scheduling. In Proceedings of the 29th Symposium on Operating Systems Principles (Koblenz, Germany) (SOSP ’23). Association for Computing Machinery, New York, NY, USA, 466–481. https://doi.org/10.1145/3600006.3613136
• [10] Kostis Kaffes, Timothy Chong, Jack Tigar Humphries, Adam Belay, David Mazières, and Christos Kozyrakis. 2019. Shinjuku: Preemptive Scheduling for μsecond-scale Tail Latency. In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19). USENIX Association, Boston, MA, 345–360. https://www.usenix.org/conference/nsdi19/presentation/kaffes
• [11] Kostis Kaffes, Jack Tigar Humphries, David Mazières, and Christos Kozyrakis. 2021. Syrup: User-Defined Scheduling Across the Stack. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles (Virtual Event, Germany) (SOSP ’21). Association for Computing Machinery, New York, NY, USA, 605–620. https://doi.org/10.1145/3477132.3483548
• [12] Avi Kivity, Yaniv Kamay, Dor Laor, Uri Lublin, and Anthony Liguori. 2007. KVM: the Linux Virtual Machine Monitor. In Proceedings of the 2007 Ottawa Linux Symposium (OLS’-07).
• [13] Alexey Kopytov. 2004. Sysbench: Scriptable database and system performance benchmark. https://github.com/akopytov/sysbench.
• [14] StevenMcCanneandVanJacobson.1993.TheBSDPacketFilter:ANew Architecture for User-level Packet Capture. In USENIX Winter 1993 Conference (USENIX Winter 1993 Conference). USENIX Association, San Diego,CA. https://www.usenix.org/conference/usenix-winter-1993-conference/bsd-packet-filter-new-architecture-user-level-packet
• [15] Meta Platforms, Inc. 2022. sched_ext. https://github.com/sched-ext.
• [16] Sebastiano Miano, Xiaoqi Chen, Ran Ben Basat, and Gianni Antichi. 2023. Fast In-kernel Traffic Sketching in eBPF. SIGCOMM Comput. Commun. Rev. 53, 1 (apr 2023), 3–13. https://doi.org/10.1145/3594255.3594256
• [17] Samantha Miller, Anirudh Kumar, Tanay Vakharia, Ang Chen, Danyang Zhuo, and Thomas Anderson. 2024. Enoki: High Velocity Linux Kernel Scheduler Development. In Proceedings of the Nineteenth European Conference on Computer Systems (Athens, Greece) (EuroSys ’24). Association for Computing Machinery, New York, NY, USA, 962–980. https://doi.org/10.1145/3627703.3629569
• [18] Amy Ousterhout, Joshua Fried, Jonathan Behrens, Adam Belay, and Hari Balakrishnan. 2019. Shenango: Achieving High CPU Efficiency for Latency-sensitive Datacenter Workloads. In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19). USENIX Association, Boston, MA, 361–378. https://www.usenix.org/conference/nsdi19/presentation/ousterhout
• [19] Dimitris Palyvos-Giannas, Gabriele Mencagli, Marina Papatriantafilou, and Vincenzo Gulisano. 2021. Lachesis: a middleware for customizing OS scheduling of stream processing queries. In Proceedings of the 22nd International Middleware Conference (Québec city, Canada) (Middleware ’21). Association for Computing Machinery, New York, NY, USA, 365–378. https://doi.org/10.1145/3464298.3493407
• [20] Henry Qin, Qian Li, Jacqueline Speiser, Peter Kraft, and John Ousterhout. 2018. Arachne: Core-Aware Thread Management. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18). USENIX Association, Carlsbad, CA, 145–160. https://www.usenix.org/conference/osdi18/presentation/qin
• [21] Gil Tene and Mike Barker. 2014. wrk2: A constant throughput, correct latency recording variant of wrk. https://github.com/giltene/wrk2.
• [22] Manohar Vanga, Arpan Gujarati, and Björn B. Brandenburg. 2018. Tableau: a high-throughput and predictable VM scheduler for high-density workloads. In Proceedings of the Thirteenth EuroSys Conference (Porto, Portugal) (EuroSys ’18). Association for Computing Machinery, New York, NY, USA, Article 28, 16 pages. https://doi.org/10.1145/3190508.3190557
• [23] Cong Xu, Sahan Gamage, Hui Lu, Ramana Kompella, and Dongyan Xu. 2013. vTurbo: Accelerating Virtual Machine I/O Processing Using Designated Turbo-Sliced Core. In 2013 USENIX Annual Technical Conference (USENIX ATC 13). USENIX Association, San Jose, CA, 243–254. https://www.usenix.org/conference/atc13/technical-sessions/presentation/xu
• [24] Cong Xu, Sahan Gamage, Pawan N. Rao, Ardalan Kangarlou, Ramana Rao Kompella, and Dongyan Xu. 2012. vSlicer: latency-aware virtual machine scheduling via differentiated-frequency CPU slicing. In Proceedings of the 21st International Symposium on High-Performance Parallel and Distributed Computing (Delft, The Netherlands) (HPDC ’12). Association for Computing Machinery, New York, NY, USA, 3–14. https://doi.org/10.1145/2287076.2287080
• [25] Kenichi Yasukata. 2023. iip: an integratable TCP/IP stack. https://github.com/yasukata/iip.