# 待ち行列理論 ## 定義 待ち行列理論(queueing theory)は、キュー(待ち行列)を持つシステムの数学的研究であり、キューの長さ・待機時間(レイテンシ)・使用率(時間ベース)を分析する方法を提供する。ソフトウェア・ハードウェアを問わず多くのコンピューティングコンポーネントはキューイングシステムとしてモデリングでき、複数のキューイングシステムからなるモデルはキューイングネットワークと呼ばれる。基礎となる数学的道具立てには確率分布・確率過程・アーランの C 式(アグナー・クラルプ・アーランが考案)・リトルの法則がある。リトルの法則は L = λW と表され、系内の平均要求数 L は平均到着率 λ と平均要求時間 W の積になる。L をキュー内の要求数、W をキュー内での平均待ち時間とすればキューに直接応用できる。キューイングシステムは到着過程(ランダム・固定・ポアソン過程等)・サービス時間分布(固定・指数分布等)・サービスセンター数の3要素によって分類され、ケンドールの記法 A/S/m で表記される。代表例は M/M/1(マルコフ到着・マルコフサービス・単一サーバー)、M/M/c(マルチサーバー版)、M/G/1(一般分布サービス時間)、M/D/1(決定論的サービス時間)であり、回転式ディスクの研究には一般に M/G/1 が使われる。M/D/1 モデルでサービス時間を一定として応答時間 r = s(2−ρ)/2(1−ρ)(s: サービス時間、ρ: 使用率)を計算すると、使用率60%を超えると平均応答時間が倍化し、80%を超えると3倍化するという非線形な劣化が明らかになる。これは、ディスクのようにプリエンプションできないキューイングシステムでは、使用率が100%に達する前に問題が顕在化する理由を説明する。(Source: [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 2 メソドロジ]] §2.6.5) 9章は待ち行列理論のディスクI/Oへの具体応用例を示す。ディスクの使用率は0%と100%の間、たとえば60%付近でも、オンディスクキューやOSのキューでキューイングされる可能性が高くなるためパフォーマンスが満足できない状態になるポイントが存在しうるとし、正確な値はディスク・ワークロード・レイテンシ要件によって変わるとしつつ、2章のM/D/1モデル(§2.6.5.2)を参照するよう促している。これは、M/D/1モデルが示す「使用率60%超で応答時間が倍化する」という数理的帰結が、9章のディスク使用率の実務的な解釈(「2秒以上100%が続けば高確率で問題」「環境によっては60%超でもキューイング増加によりパフォーマンスが低下する」)の理論的裏付けとして機能していることを示す。(Source: [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 9 ディスク]] §9.3.9, §9.5.3) ## 横断的知見 - 2章のM/D/1モデルが導く「使用率60%超で応答時間が倍化、80%超で3倍化」という数理的結論を、9章はディスクI/Oの実務的な使用率解釈にそのまま接続している。9章では「2秒以上ディスク使用率100%が続けば問題の可能性が非常に高い」「環境によっては60%超でもキューイング増加によりパフォーマンスが低下する」と述べており、これは2章の理論値と整合する。一方で9章は「正常/異常な値はワークロード・環境・レイテンシ要件によって変わる」と釘を刺しており、M/D/1モデルはあくまで単純化(サービス時間一定)であることを実務の文脈で再確認させている。(Source: [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 2 メソドロジ]] §2.6.5, [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 9 ディスク]] §9.3.9, §9.5.3) ## 未解決の問い - M/D/1 モデルはサービス時間を一定と仮定する単純化だが、実際のディスク I/O のようにサービス時間にばらつきがある M/G/1 や M/M/1 では、60% という劣化の境界値はどの程度変わるか。9章は回転磁気ディスクのサービス時間がキャッシュヒット/ミスで二峰分布になることを示しており(§9.3.2)、M/D/1の「決定論的サービス時間」という前提そのものがディスクI/Oの実態と乖離している可能性がある。 - 待ち行列理論に基づく使用率60%目標(例: Netflix の CPU 使用率60%を保つ ASG ポリシー)は、キューイングモデルの種類(M/D/1 か M/M/1 か)によってどこまで感度を持つか。 - 9章はディスクコントローラの使用率を時間ベースではなくスループット/稼働率の上限に対する割合として定義している(§9.5.2.2、→[[USE メソッド]])。この容量ベースの使用率に対して、M/D/1モデルの60%閾値のような待ち行列理論の帰結はどこまで転用できるか、本章・2章とも明示していない。 ## 関連 - [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 2 メソドロジ]] — 待ち行列理論とリトルの法則、M/D/1 分析の原典解説(§2.6.5)。 - [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 9 ディスク]] — ディスク使用率へのM/D/1モデルの実務応用(§9.3.9, §9.5.3)。 - [[アムダールの法則]] / [[ユニバーサルスケーラビリティ法則]] — 同章で扱われるスケーラビリティモデリングの別系統。 - [[USE メソッド]] — ディスクの使用率・飽和度チェックで待ち行列理論の帰結を利用するメソドロジ。 ## 出典 - [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 2 メソドロジ]] §2.6.5 - [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 9 ディスク]] §9.3.9, §9.5.3