Study on Delay Characteristics of Scheduling for Real-Time Systems

遅延特性に関する研究

Study on Delay Characteristics of Scheduling for Real-Time Systems

2007 年 2 月

早稲田大学大学院 国際情報通信研究科 国際情報通信学専攻

分散コンピューティングシステム研究 II

花田 真樹

第1_{章 序論} 1

1.1 研究の背景と目的 . . . . 1

1.1.1 情報処理システムにおける性能解析手法の現状. . . . 2

1.1.2 通信ネットワークにおける性能解析手法の現状. . . . 3

1.1.3 本論文の目的 . . . . 4

1.2 本論文の構成 . . . . 5

第2章 従来研究 8 2.1 まえがき . . . . 8

2.2 待ち行列理論 . . . . 8

2.2.1 待ち行列モデル . . . . 8

2.2.2 出生死滅過程 . . . . 9

2.2.3 M/M/1 . . . . 11

2.2.4 M/M/s . . . . 12

2.2.5 M/G/1 . . . . 13

2.3 リアルタイムスケジューリング理論 . . . . 20

2.3.1 リアルタイムタスクの時間属性 . . . . 20

2.3.2 EDF . . . . 20

2.3.3 最適性とスケジュール可能性 . . . . 21

2.4 ネットワークQoS技術 . . . . 24

2.4.1 QoSの定義 . . . . 24

2.4.2 QoSアーキテクチャ . . . . 24

2.4.3 トラヒックシェーピング . . . . 26

2.4.4 パケットスケジューリング方式 . . . . 29

2.5 むすび . . . . 42

第3章 非割込み型EDFスケジューリングの近似解析 44 3.1 まえがき . . . . 44

3.2 システムモデル . . . . 45

3.3 待ち時間の条件付き分布と期待値の導出 . . . . 46

3.3.1 待ち時間の各要素. . . . 47

3.3.2 待ち時間の条件付き分布と期待値 . . . . 51

3.4 デッドラインミス率と平均遅延時間 . . . . 52

3.5 待ち時間の条件付き分布の近似 . . . . 52

i

3.5.2 境界条件の特定のための近似的な定義 . . . . 54

3.6 複数サーバモデル . . . . 56

3.6.1 待ち時間の条件付き分布と期待値の導出 . . . . 57

3.6.2 デッドラインミス率と平均遅延時間 . . . . 59

3.6.3 待ち時間の条件付き分布の近似 . . . . 59

3.7 シミュレーションと評価 . . . . 60

3.7.1 前提 . . . . 60

3.7.2 単一サーバモデル. . . . 61

3.7.3 複数サーバモデル. . . . 66

3.8 非割込み型EDFスケジューリングと他のスケジューリング方式の比較 . . . 68

3.8.1 平均応答時間 . . . . 69

3.9 むすび . . . . 72

第4章 非割込み型EDFスケジューリングにおける性能予測：理論と実装 76 4.1 まえがき . . . . 76

4.2 RTLinux . . . . 76

4.2.1 概要 . . . . 76

4.2.2 スケジューリング方式 . . . . 77

4.2.3 割込み処理 . . . . 77

4.3 実装と実験 . . . . 77

4.3.1 実システムにおける割込みハンドラとタスク . . . . 77

4.3.2 実装 . . . . 78

4.3.3 実験 . . . . 79

4.4 むすび . . . . 83

第5章 遅延保証を目的とした出力レート制御方式ORC-GPS 84 5.1 まえがき . . . . 84

5.2 従来方式とその問題点 . . . . 85

5.2.1 Generalized Processor Sharing (GPS) . . . . 85

5.2.2 Earliest Deadline First (EDF) . . . . 87

5.3 Output Rate-Controlled Generalized Processor Sharing (ORC-GPS) . . . . 88

5.3.1 アプローチ . . . . 88

5.3.2 サービス制御法 . . . . 89

5.3.3 単一ノードでの最大遅延 . . . . 89

5.3.4 End-to-End最大遅延 . . . . 94

5.4 従来方式とORC-GPSの比較 . . . . 98

5.4.1 g_i がρ_iより大きい場合について . . . . 99

5.4.2 g_i がρ_iより小さい場合について . . . . 109

5.5 むすび . . . . 115

第6章 結論 117

ii

謝辞 122

参考文献 123

研究業績 127

図目次 128

表目次 131

iii

第 1 _{章 序論}

1.1 研究の背景と目的

現在，我々の周りにはリアルタイム性を必要とする様々な情報通信システムが広く存在し ている．例えば，プラント制御システム，航空管制システム，ビデオ会議システム，電話シ ステム，銀行のATMシステムなどである．これらのシステムは時間制約の課せられたリア ルタイムシステムに分類される．一般的なシステムでは論理的な正確さが求められるのに対 して，リアルタイムシステムでは論理的な正確さに加えて，時間的な正確さを求められる.

近年のコンピュータの高性能化やネットワークの広帯域化に伴い，制御分野に加えて様々 な分野でのリアルタイム性が重要視されている．最近では，携帯情報機器でも高速処理が行 えるようになり，様々な通信インターフェースが搭載され，音声，画像，映像などのリアル タイムデータが扱われるようになってきている．また，将来的には，家庭内でも家電機器，

AV機器，PC系機器など各種の情報家電機器がネットワークを介して接続され，リアルタ イムな情報のやりとりが必要となってくると予想される．本論文では，このようなリアルタ イム性の要求されるシステムにおける遅延保証を行うための基礎的な技術の提案および解析 に主眼を置く．特に，リアルタイム性を向上させるためには，システムにおける資源（CPU 資源やネットワーク帯域資源）をどのように割当てるかを決定するスケジューリング方式が 重要となるので，スケジューリング方式に注目した提案および解析を行う．本論文の提案お よび解析を用いることにより，システムの開発者はシステムのリアルタイム性を向上させ，

より性能のよいシステムの開発や構築が行えるようになり，システムを利用するユーザはス トレスを感じることなく，快適にシステムを利用することができるようになる．

リアルタイムシステムでは要求される性能を満足しているかを検証することが重要とな る．これまでに，システムの性能を求める手段として，（1）実際のシステムを試作し，測定 する手法，（2）シミュレーションによって求める手法，（3）数理的解析によって求める手法 などが用いられている．（1）は非常にコストがかかる．（2）はある程度のコストが必要であ り，モデル化が重要となる．（3）は解析されていないモデルも多く，適用できない場合も多 い．しかしながら，数理的解析では，現実的でないとしても，容易な見通しが得られ，複 雑な現象を理解する手助けとなる．また，最適性や比較の検討を行う場合には特に有効な 手段となり得る．これまでに，システム性能評価の基礎として，待ち行列理論（トラヒック 理論）やリアルタイムスケジューリング理論が研究されている．待ち行列理論は20世紀初 頭に電話システムの性能解析のために考案されたためにトラヒック理論とも呼ばれており，

サービス窓口の客，インターネットのパケット，交通システムの車，コンピュータシステム のジョブなどのように，イベントが確率的に発生し，これらが資源の競合をするシステムの モデル化と性能の解析を行うものである．待ち行列理論のコンピュータシステムへの応用 に関しては，従来の単一待ち行列モデルや多重プログラミングシステムのモデル化である

る．さらに，従来のFirst Come First Service（FCFS）に加えて，スケジューリング方式と して，優先権スケジューリング（HOL優先権）[1]，Shortest Processing Time（SPT）[2]， Shortest Remaining Process Time First（SRPT）[3]，Processor Sharing（PS）[4, 5]を用 いた場合のシステムの平均的な性能を解析する研究も数多く行われている．一方，リアルタ イムスケジューリング理論は1970年代から研究が始まり，決められたタスクセット（例え ば，周期タスク）に対してリアルタイムスケジューリングを適用した場合の最適性の証明や スケジュール可能性を解析したものである．代表的なリアルタイムスケジューリング方式と して，Rate Monotonic（RM）[6]，Earliest Deadline First（EDF）[7]，Least Laxity First

（LLF）がある．RMは周期タスクに対し，周期の短いタスクに高い優先順位をつける割込 み可能な方式であり，プロセッサの処理能力の69%以下ならば全てのタスクはデッドライン を守ることができる[6]．EDFはデッドラインの早い順に優先順位をつける割込み可能な方 式であり，最適なスケジューリング方式である．非周期タスクに対しては最大遅れを最小に することに関して最適であり，周期タスクに対してはプロセッサの処理能力の100%まで全 てのタスクはデッドラインを守ることができる[7]．このように，リアルタイムスケジュー リング理論では，ある決められた時刻に終了しなければならないハードリアルタイムシステ ムを主な対象とし，最適性の証明やスケジュール可能性に主眼を置いている．

1.1.1 情報処理システムにおける性能解析手法の現状

ここ数年，ビデオ会議システムなどのように，音声，画像，映像を含めたマルチメディア データを処理するマルチメディアシステムが増加しており，このようなある決められた時刻 に必ず終了する必要のないソフトリアルタイムシステムを対象とした解析が重要になってき ている．

待ち行列理論では，サービス規律としてFCFSなどの非リアルタイム系のスケジューリン グ方式が用いられており，リアルタイムスケジューリングを適用した研究がほとんど行われ ていない．また，主にシステムの平均的な性能に主眼を置いており，デッドラインを想定し ていないために，リアルタイム性に対する議論も不十分である．このため，従来の待ち行列 理論をそのままソフトリアルタイムシステムの解析に適用するのは困難である．

リアルタイムスケジューリング理論では，制御系システムなどのハードリアルタイムシス テムが主な対象であり，このようなシステムではセンサーの監視など所定のタスクを周期的 に実行することが多いために，決められたタスクセットを前提としている．一方，マルチメ ディアシステムなどのソフトリアルタイムシステムではユーザからの要求などが主なイベ ントとなる．よって，タスクが確率的に発生するようなシステムを扱う必要があるが，この 理論ではこれらを扱っていない．また，デッドライン保証の観点から，最適性の証明やスケ ジュール可能性などに主眼を置いているために，システムの平均的な性能に対する議論が不 十分である．よって，従来のリアルタイムスケジューリング理論をそのままソフトリアルタ イムシステムの解析に適用するのは困難である．

1.1.2 通信ネットワークにおける性能解析手法の現状

通信分野では，従来の電話ネットワークに加えてインターネットに代表されるIPベースの データ系通信ネットワークが広く利用されてきている．それに伴い，待ち行列理論でも様々 なシステムモデルが提案され，パケット交換ネットワークにおけるシステム性能を解析する 研究が行われてきている．さらに，音声，画像，映像など様々なリアルタイムデータをネッ トワーク上で伝送することが一般的となり，サービス品質（Quality of Service）の保証に関 する研究も1980年代後半から現在まで盛んに行われている．特に，1990年代後半にIETF での標準化が開始されて以来，インターネット上のQoSに関する技術に関しても多く提案 され，公開されている．

要求されるQoSはアプリケーションによって異なる．テレビ会議，音声伝送などではパ ケットの発生がランダムであり，ある程度小さな値の最大遅延を保証する必要がある．また，

音声放送，ストリーミングなどでは平均遅延が小さいことは必ずしも重要ではなく，最大遅 延（遅延の上界）が保証されることが必要である．

このように，リアルタイムデータを扱う場合，最大遅延に関するQoS保証が特に重要と なる．待ち行列理論では主にシステムの平均的な性能に主眼を置いており，様々なバースト 的なトラヒックが流入するネットワークにおいてEnd-to-End最大遅延などの絶対的性能を 解析するのは困難である[8]．リアルタイムスケジューリング理論では，最大遅延保証の観 点から研究が進められているが，周期タスクなどの決められたタスクセットが前提となって おり，同様に様々なバースト的なトラヒックが流入するネットワークにおける解析を行うの は困難である[8]．このような背景から，トラヒックシェーパと各種のスケジューリング方 式を組み合わせて，ネットワークで発生する最大遅延を求める研究が多く行われている．

トラヒックシェーパは，ネットワークに流入するトラヒックの最大レート，平均レートお よび最大バースト長に対して制限を加えるものである．トラヒックシェーピングを行うこと によりネットワークに流入するトラヒック特性が明らかになるので最大遅延保証が可能と なる．代表的なトラヒックシェーパとして，Leaky Bucket，Dual Leaky Bucket，Multiple Leaky Bucketなどがある．

また，スケジューリング方式に注目すると，次のように大きく2つの種類に分類される．

1つは各フロー¹ に重みを割り当て，サービスレートを制御する方式であり，コンピュータ 上のタスクスケジューリングであるProcessor Sharingを一般化したGeneralized Processor Sharing（GPS）[9, 10]である．もう1つは各フローにデッドラインを割り当て，デッドライ ンにより制御する方式であり，上述したリアルタイムシステムで用いられるEDF[7, 11, 12]

である．

GPSはパケット長を無限小と仮定した流体モデルを用いている．これは，パケット長を考 慮しないので，あるフローのパケットをサービス中でもそのフローより高い優先度を持つフ ローのパケットによる割込みを許可する割込み型と同等の概念である[13]．パケット長を考 慮したGPSの近似形（非割込み型GPS）として，Packet-by-Packet Generalized Processor Sharing（PGPS）[9, 10, 14]，Self-Clocked Fair Queueing（SCFQ）[15]，Worst-case Fair

1フローとは送信ホストから受信ホストへの一つのコネクション上で送られる時間的にまとまったパケットの 集合でQoS的に同じ取扱いを必要とするものとして定義される．また，本論文ではセッションをフローと同じ 意味で用いる．

つの近似形として，Round Robin型があり，Weighted Round Robin（WRR）[18]，Deflicit Round Robin（DRR）[19]などがある．これらの研究では，パケット長を考慮することに よるGPSとのシステム性能の差分が主な評価基準となっている．

EDFに関してもパケット長を無限小と仮定した流体モデルを用いている．つまり，割込 み型EDFである．また，様々なモデルに対するEDFのデッドラインの割り当て方法を議論 した各種スケジューリング方式が存在する．代表的な方式として，Delay Earliest Due Date

（Delay-EDD）[11, 12]，Rate-Controlled Earliest Deadline First（RC-EDF）[20, 21, 22]， Deadline-Curve Earliest Deadline First（DC-EDF）[23]などがある．各種パケットスケ ジューリング方式の原型であるGPSとEDFに注目すると，これらは本来異なる目的で設 計されたために，その性質に大きな違いがある．

GPSはサービスの公平性（帯域保証）を主な目的としており，最低保証レートや任意の時 間におけるサービス量（以下，サービス曲線と呼ぶ）が厳密に求められる．よって，各ノー ドでの最低保証レートや任意の時間におけるサービス量（サービス曲線）を厳密に予測でき ることから，End-to-End最大遅延も小さく見積もることが可能となる．これを予測性と呼 ぶ．その反面，固定の優先度を用いるためにバックログがなくなるまでサービスレートが変 化しないので，最大遅延が大きくなる可能性がある．

逆に，EDFは遅延保証を目的としており，遅延保証を行うために動的にサービスレート が変化するので，最低保証レートや任意の時間におけるサービス量を厳密に求めることは困 難である．デッドラインまでゆとりのあるフローはサービスが後回しにされ，最悪の場合，

ある時間では全くサービスが行われない（サービスレートが0になる）可能性も考えられ る．そのために，各ノードでの最低保証レートや任意の時間におけるサービス量（サービス 曲線）を予測できないことから，End-to-End最大遅延が各ノードで発生する最大遅延の単 純な合計となり，過大な見積もりとなる．その反面，動的にサービスレートが変化させて遅 延保証を行うために，単一ノードにおける最大遅延を最も小さくすることが可能である．こ れを最適性と呼ぶ．

1.1.3 本論文の目的

本論文では，リアルタイム性の要求されるシステムにおける遅延保証を行うための基礎的 な技術の提案および解析に主眼を置く．特に，リアルタイム性を向上させるためには，シス テムにおける資源（CPU資源やネットワーク帯域資源）をどのように割当てるかを決定す るスケジューリング方式の選定が重要となるので，本論文ではスケジューリング方式に注目 した提案や解析を行う．

本論文ではまず，タスクが確率的（ランダム）に発生する情報処理システムを対象とし，

リアルタイムスケジューリングを適用した場合のシステム性能に関する解析を行う．リアル タイムスケジューリングとしては最適なスケジューリング方式であるEDFを用いる．また，

実システムでは割込み処理やコンテキストスイッチのオーバーヘッドがかかるため，解析結 果が実システムの実測データとは一致しない可能性がある．そこで，EDFを行うタスクス ケジューラをリアルタイムOS上に実装し，解析の有効性を検証する．

つぎに，通信ネットワークにおいて最大遅延保証を行う上で，これまでのパケットスケ ジューリング方式がもつ問題点を解決した新しい方式ORC-GPSを提案する．つまり，前節 で述べた予測性と最適性を考慮した方式である．従来のスケジューリング方式と比較して，

その有効性を示す．

1.2 本論文の構成

本論文の概要を以下に述べる．

第1章は「序論」であり，研究の背景と目的，及び論文の概要について述べている．

第2章は「従来研究」と題し，本論文において前提となる各理論やネットワークQoS技 術について述べている．

第3章は「非割込み型EDFスケジューリングの近似解析」と題し，タスクが確率的（ラ ンダム）に発生する情報処理システムを対象とし，リアルタイムスケジューリング（非割込 み型EDF）を適用した場合のシステム性能を明らかにしている．従来の待ち行列の理論で 用いられてきたモデルと異なる点は，タスクの属性として，到着過程と実行時間過程に加え て，デッドラインを考慮する必要があるということである．ここでは，実行時間の長いタス ク程，長い相対デッドラインをもつと考え，相対デッドラインが実行時間の固定倍数と仮定 している．解析のアプローチとしては，EDFは優先権スケジューリングの一種とみなすこ とができる．そこで，一般的な優先権スケジューリング（HOL優先権[1]）の各クラスの平 均待ち時間導出の枠組みを拡張した新たな枠組を提案し，解析を行い，その有効性を示して いる[24]．

第4章は「非割込み型EDFスケジューリングにおける性能予測：理論と実装」と題し，非 割込み型EDFを行うタスクスケジューラをリアルタイムOS上に実装し，システム性能を 理論解析と実測データの両面から評価している．第3章では非割込み型EDFスケジューリ ングの解析を行ったが，実システムでは割込み処理やコンテキストスイッチのオーバーヘッ ドがかかるため，解析結果が実システムの実測データとは一致しない可能性がある．そこ で，本章では非割込み型EDFスケジューリングを行うスケジューラを，リアルタイムアプ リケーション構築の際のプラットフォームであるRTLinux上に実装し，割込み処理やコン テキストスイッチが性能にどのような影響を与えるかを検証し，第3章で行った理論解析の 適応範囲を示している[25]．

第5章は「遅延保証を目的とした出力レート制御方式」と題し，通信ネットワークにおい て最大遅延保証を行うパケットスケジューリングである従来方式（GPSとEDF）の問題点 を指摘し，その問題点を解決した新しい方式ORC-GPSを提案している．ORC-GPSでは，

GPSと同様に重みに従ったサービスを行う．しかし，GPSのように常に重みに従ったサー ビスを行うと各セッションの最大遅延が不必要に増加してしまうので，ORC-GPSでは，各 セッションにおいて他のセッションの最大遅延を不必要に増加させないようにサービスの制 限を行う．本章ではEnd-to-End最大遅延の算出を行い，従来のスケジューリング方式と比 較し，その有効性を示している[26]．

第6章は「結論」であり，本論文で得られた成果をまとめ，考察を行い，今後の課題を示 している．

図1.1: 各章の構成

第 2 _{章 従来研究}

2.1 まえがき

本章では，待ち行列理論，リアルタイムスケジューリング理論，ネットワークQuality of Service（QoS）技術について述べる．待ち行列理論[27, 1, 28, 29, 30, 31, 32, 33]では，まず，

基本的なモデルの主要な解析結果について述べる．次に，スケジューリング方式として，優 先権スケジューリング（HOL優先権）[1]，Shortest Processing Time（SPT）[2]，Shortest Remaining Process Time First（SRPT）[3]，Processor Sharing（PS）[4, 5]を適用したモ デルの主要な解析結果について述べる．リアルタイムスケジューリング理論[34, 35, 36]で は，Earilest Deadline First（EDF）[7]に関する基本的な性質について述べる．最適性の証 明やスケジュール可能性などを中心に述べる．これらの解析結果は第3章の非割込み型EDF スケジューリングの解析の基礎となる．ネットワークQoS技術[37]では，QoSの定義，QoS アーキテクチャおよびそれを構成する各機構について述べる．さらに，各種パケットスケ ジューリング方式について詳細に説明し，各スケジューリング方式によって発生する最大遅 延について述べる．これらは第5章で述べる提案方式の基礎となる．

2.2 待ち行列理論

2.2.1 待ち行列モデル

典型的な待ち行列モデルの例として，銀行の例がある．銀行には，客が来て，窓口に並び，

順番がくれば，窓口でサービスを受け，サービスが終われば，銀行から客は去っていく．こ のシステムをモデル化したのが，待ち行列モデルである（図2.1）．

コンピュータシステム分野では，客はプロセス（あるいはタスク），窓口はCPU（あるい は処理装置），サービス時間は実行時間（あるいは処理時間），到着は発生といった用語が，

また，通信ネットワークでは，客はパケット，窓口は回線，サービス時間はパケットの送信 時間といった用語が用いられるが，ここでは，なるべく待ち行列理論の習慣に沿って，客，

窓口，サービス時間といった用語を用いる．

待ち行列モデルの形態を表すために次に示すKendallの記法が用いられる．その記法を以 下に記す．

A/B/C/K/m/Z A:到着時間間隔分布

B :サービス時間(処理時間)分布

C:サービス窓口(処理装置)の数 K :システムの容量

m:システムに到着する客の数

Z :サービス規律(スケジューリング方式)

A/B/Cで表される場合は，Kとmが無限でありZがFCFSの場合である．A，Bとして

一般的に用いられる分布を以下に記す．

GI :各到着時間間隔がお互い独立な一般分布 G:一般分布

H_k:k次の超指数分布 E_k:k次のアーラン分布

M :指数分布

D:一定分布

U :一様分布

. . .

客 待ち行列

窓口1

窓口s 到着

サービス 退却

退却

図2.1: 待ち行列モデル

2.2.2 出生死滅過程

出生死滅過程は，状態E_kからの遷移が隣り合う状態E_k+1，E_k，E_k−1にだけしか許さな いマルコフ過程である（図2.2）．マルコフ過程とは，将来の状態が過去の履歴によらず，現 在の状態によってのみ決まる確率過程である．システムにk人がいて，1人が到着するまで の時間間隔は平均1/λ_kの指数分布であり，1人が終了するまでの時間間隔は平均1/µ_kの指 数分布であるとする．この時，時間∆tの間に起きる各確率は次のようになる．

• 時間∆tの間にただ1人も到着しない確率: 1−λ_k∆t+o(∆t)

• 時間∆tの間にただ1人だけ到着する確率: λ_k∆t+o(∆t)

0 1 2 ・・・・ n-1 n ・・

µ0 µ1 µn

図2.2: 出生死滅過程

• 時間∆tの間に2人以上到着する確率: o(∆t)

• 時間∆tの間にただ1人も終了しない確率: 1−µ_k∆t+o(∆t)

• 時間∆tの間にただ1人だけ終了する確率: µ_k∆t+o(∆t)

• 時間∆tの間に2人以上終了する確率: o(∆t)

以上より，時刻tにおいて状態E_kである確率をP_k(t)と表記すると，次式が成り立つ．こ こで，lim_∆t→0o(∆t)/∆t= 0である．

P₀(t+ ∆t) = P₀(t)[1−λ₀∆t] +P₁(t)[µ₁∆t] +o(∆t), P_k(t+ ∆t) = P_k−1(t)[λ_k−1∆t+o(∆t)]

+ P_k+1(t)[µ_k+1∆t+o(∆t)]

+ P_k(t)[1−λ_k∆t+o(∆t)][1−µ_k∆t+o(∆t)].

∆t→0とすると，

dP₀(t)

dt = −λ₀P₀(t) +µ₁P₁(t), dP_k(t)

dt = −(λ_k+µ_k)P_k(t) +λ_k−1P_k−1(t) +µ_k+1P_k+1(t),(k= 1,2, ...).

平衡状態では，^dP_dt^k(t) = 0,(k= 0,1,2, ...)である．したがって，

0 = µ₁P₁(t)−λ₀P₀(t),

0 = −(λ_k+µ_k)P_k(t) +λ_k−1P_k−1(t) +µ_k+1P_k+1(t),(k= 1,2, ...).

これより，状態E_kである確率P_kは，次のように求められる．

P_k = λ_k−1 µ_k

λ_k−2 µ_k−1 . . .λ₀

µ₁ =P₀Π^k_i=1λ_i−1

µ_i , (2.1)

X∞

k=0

P_k = 1, (2.2)

P₀ = 1

1 +^P∞_k=1Π^k_i=1^λ_µⁱ⁻¹

i

. (2.3)

2.2.3 M/M/1

客の到着分布が独立で同一の生起率λのポアソン分布，窓口におけるサービス時間も独立 で同一のパラメタµの指数分布に従う，窓口が1つ（単一サーバ）の場合である（図2.3）．

客 待ち行列

窓口 到着

サービス 退却

[ポアソン分布]

[指数分布]

図2.3: M/M/1

出生死滅過程において，到着時間間隔の平均もサービス時間の平均もシステムの状態によ らず一定であると考えることができるので，次式が成り立つ．

λ_k = λ,(k= 0,1,2, ...), µ_k = µ,(k= 0,1,2, ...).

出生死滅過程(式(2.1)，式(2.2)，式(2.3))より，次式となる．

P_k = P₀(λ

µ)^k,(k= 1,2, ...), (2.4)

P₀ = 1

1 +^P∞_k=1(^λ_µ)^k = 1−λ

µ. (2.5)

ここで，ρ= ^λ_µとすると，

ρ= 1−P₀. (2.6)

ρは窓口が空いていない確率，すなわち，窓口の利用率である．これから，

P_k= (1−ρ)ρ^k,(k= 0,1,2, ...). (2.7) 上記より求められる主要な性能指標を表2.1に示す．

表2.1: 主要な性能指標（M/M/1）

平均待ち客数L 平均系内客数N 平均待ち時間W 平均滞在時間T

ρ²

1−ρ ρ

1−ρ ρ²

λ(1−ρ)

1/µ 1−ρ

また，待ち時間分布，滞在時間分布は以下である．

• 待ち時間分布W(x)

W(x) = 1−e^{−(µ−λ)x}. (2.8)

• 滞在時間分布T(x)

T(x) = 1−ρe^{−(µ−λ)x}. (2.9)

客の到着分布が独立で同一の生起率λのポアソン分布，窓口におけるサービス時間も独立 で同一のパラメタµの指数分布に従う，窓口が複数（複数サーバ）の場合である（図2.4）．

客 待ち行列

到着

退却

[ポアソン分布]

[指数分布]

. . . 窓口1

窓口s

サービス 退却

図2.4: M/M/s

出生死滅過程において，到着時間間隔の平均もサービス時間の平均もシステムの状態によ らず一定なので，次式が成り立つ．

λ_k = λ,(k= 0,1,2, ...), µ_k =

( kµ, (k= 0,1,2...);

sµ, (k=s, s+ 1, ...).

出生死滅過程(式(2.1)，式(2.2)，式(2.3))より，ρ=λ/µとすると，次式が成り立つ．

P_k =

( P₀^ρ_k!^k, (k= 0,1,2..., s−1);

P_0s!s(k−s)^ρk , (k=s, s+ 1, ...), (2.10)

P₀ = 1

P_s−1

k=0ρ^k

k! +(s−1)!(s−ρ)^ρs

. (2.11)

上記より求められる主要な性能指標を表2.2に示す．

表2.2: 主要な性能指標（M/M/s）

平均待ち客数L 平均系内客数N 平均待ち時間W 平均滞在時間T P₀(s−1)!(sµ−λ)^{λµρs 2}

P_∞

k=1kP_k=L+_µ^{λ L}_λ W + ¹_µ

また，待ちが生じる確率，待ち時間分布，滞在時間分布は以下である．

• 待ちが生じる確率P_s

P_s= X∞

k=s

P_k=P₀ µρ^s

(s−1)!(sµ−λ). (2.12)

• 待ち時間分布W(x)

W(x) = 1−P_se^{−(sµ−λ)x}. (2.13)

• 滞在時間分布T(x) T(x) =





1−^{λ/µ−s+(1−P}_λ/µ+1−s^s)e^−µt+_λ/µ+1−s^Ps e^{−(sµ−λ)t}, (λ/µ6=s−1);

1−(1 +P_sµt)e^−µt, (λ/µ=s−1). (2.14)

2.2.5 M/G/1

客の到着分布が独立で同一の生起率λのポアソン分布，窓口におけるサービス時間は一般 分布に従う，窓口が1台（単一サーバ）の場合である．以下より，サービス規律別に分類し て示す．

M/G/1/∞/∞/FCFS

FCFS（First Come First Served）は到着順にサービスを行うスケジューリング方式であ る．到着する客に番号をつけ，k番目の客のサービス終了直後の客数をn_kとおき，k番目の 客のサービス時間中に到着した客数をa_kとおく．k番目の客のサービス終了直後に待ち行 列があれば，次の客のサービスが終わるときにはその間にきたa_k+1人だけ増え，k+ 1番目 の客が1人だけ減るので（図2.5），

n_k+1 =n_k+a_k+1−1,(n_k>0) (2.15) となる．

一方，客が出て行った後に誰も残らないならば，次に来た客(k+ 1)番目の客は直ちにサー ビスを受け始めるので，そのサービスが終わったときには，そのサービス中にきたa_k+1人 の人々がそのまま残される（図2.6）．したがって，次式が成り立つ．

n_k+1=a_k+1,(n_k= 0). (2.16)

式(2.15)，式(2.16)をまとめると，次式となる．

n_k+1 = n_k+a_k+1−U(n_k) ここで，

U(x) =





1, (x >0);

0, (x≤0) である．

ak+1

nj nk

nk+1

j番目の客 k番目の客 k+1番目の客 1番目の客

の到着

k番目の客 の到着

時間

図2.5: サービス終了後のパターン1(n_k>0)

ak+1

n^k+1 nk=0

j番目の客 k番目の客 k+1番目の客 k番目の客のサービス終了

図2.6: サービス終了後のバターン2(n_k= 0)

定常状態では，サービス時間の密度関数をb(x)とすると，次式が成り立つ．

E(n_k+1) = E(n_k) =N, E(U(n_k)) = λ

µ, E(a_k+1) =

Z _∞

0

X∞

k=0

k(λx)^k

k! e^−λxb(x)dx= λ µ.

さらに，次式も成り立つ．

E(n²_k+1) = E({n_k+a_k+1−U(n_k)}²)

= E(n²_k) +E(a²_k+1) +E(U(n_k)²) + 2E(n_ka_k+1)−2E(n_kU(n_k))−2E(a_k+1U(n_k)).

n_kとa_k+1は独立であるので，次式が成り立つ．

E(n²_k+1) = E(n²_k),

E(U(n_k)²) = E(U(n_k)) = λ µ,

E(n_ka_k+1) = E(n_k)E(a_k+1) =Nλ µ, E(n_kU(n_k)) = E(n_k) =N,

E(a_kU(n_k)) = E(a_k+1)E(U(n_k)) =ρ², E(a²_k+1) =

Z _∞

0

X∞

k=0

k²(λx)^k

k! e^−λxb(x)dx=λ²b₂+λ µ.

よって，

0 =λ²b₂+ρ+ρ+ 2ρN−2N−2ρ² (2.17) である．

式(2.17)を解くと，主要な性能指標は表2.3のようになる．ここで，b₂はサービス時間の 2次のモーメントであり，Cは変動係数(=標準偏差/平均値)とする．

表2.3: 主要な性能指標（M/G/1）

平均待ち客数L 平均系内客数N 平均待ち時間W 平均滞在時間T

λ²b2+2ρ−2ρ²

2(1−ρ) λ²b2

2(1−ρ) 1

µ

h

1 +^ρ(1+C_2(1−ρ)^{2)i ρ(1+C}_2(1−ρ)²⁾

また，サービス時間の分布関数をB(x)，そのラプラス変換をB^∗(s)とした場合，待ち時 間分布，滞在時間分布のラプラス変換は以下のように与えられる．

• 待ち時間分布W^∗(x)

W^∗(x) = (1−ρ)s

s−λ+λB^∗(s). (2.18)

• 滞在時間分布T^∗(x)

T^∗(x) = (1−ρ)sB^∗(s)

s−λ+λB^∗(s). (2.19)

M/G/1/∞/∞/PS

タイムシェアリングシステム等では，ラウンドロビン（RR: Round Robin）が用いられ ている．ジョブの処理の開始から一定の時間経過までにそのジョブの処理が終了しなかった 場合，その処理を中断し，そのジョブを待ち行列の最後尾につける．ラウンドロビン方式の 一定時間の大きさを限りなく小さくした極限の場合には単純な結果となる．この極限の方式 がプロセッサシェアリング（PS: Processor Sharing）方式である（図2.7）．

客の到着が生起率λのポアソン分布で，サービス時間が独立で平均値が1/µである場合，

システム内の客数分布は，式(2.7)となる．サービス時間xの客の平均滞在時間と平均滞在 時間は以下で与えられる．

客 待ち行列

窓口 到着

サービス 退却

[ポアソン分布]

[一般分布]

図2.7: M/G/1/∞/∞/PS

• サービス時間xの客の平均滞在時間T(x) T(x) = x

1−ρ. (2.20)

• 平均滞在時間T

T = 1/µ

1−ρ. (2.21)

M/G/1/∞/∞/Priority

これは優先権スケジューリング（Priority）である．また，優先権スケジューリングはHOL

優先権（Head Of the Line）とも呼ばれる．到着する客が複数のクラスに分かれる場合，ク

ラスごとの要求が異なる場合がある．最も単純な方法は単にクラス間に優先権を付け，その 順序でサービスを行う方式である．現在サービス中の客よりも，高い優先順位をもった客が 到着した場合の方式によって2つに分類される．1つはサービス中の客はそのままサービス を続行する非割込み型であり，もう1つはサービス中の客を一時中断し，高い優先権の客の サービスが終了してから再開する割込み型である．

客がK個の異なったクラスに分類される場合を考える．クラスiの客の到着は生起率λ_i のポアソン分布とする．サービス時間の分布関数はB_i(x)で表され，その平均を1/λ_i，2次 モーメントをb_2iとする．ここでは，次の表記を用いる．

ρ_i = λ_i

µ_i :クラスiの客の利用率

N_i :システム内に滞在するクラスiの客数の平均 T_i:クラスiの客がシステム内に滞在する時間の平均

L_i :待ち行列内でサービス待ち中のクラスiの客の人数の平均

W_i :待ち行列内でサービス待ち中のクラスiの客の待ち行列内での待ち時間の平均 リトルの公式より，次式が成り立つ．

N_i =λ_iT_i,(i= 1,2, ..., K), L_i =λ_iW_i,(i= 1,2, ..., K).

また，次式が成り立つ．

T_i=W_i+ 1

µ_i,(i= 1,2, ..., K).

• 非割込み型

到着したクラスiの客の待ち時間は，現在，サービス中の客が終了するまでの時間（W_o） と，自分以上の優先度をもつ現在待っている客のサービス時間（W1_i）と，自分が待っ ている間に到着する自分より高い優先度をもつ客のサービス時間（W2_i）からなる．

クラスjの待ち客数の平均値はL_j =λ_jW_jであり，クラスjの客1人のサービス時間 の平均値は1/µ_jである．

クラスiの客は，それより，高い優先度をもつ客のサービス時間だけ待たされること になるので，

W1_i= Xi

j=1

1

µ_jλ_jW_j = Xi

j=1

ρ_jW_j,(i= 1,2, ..., K) (2.22) となる．

クラスiの待ち時間はW_iであり，クラスjの待ち客数の平均値はL_j =λ_jW_iである．

クラスjの客1人のサービス時間の平均値は1/µ_jである．

クラスiの客は，それより，高い優先度をもつ客のサービス時間だけ待たされること になるので， 次式が成り立つ．

W2_i = Xi−1

j=1

1

µ_jλ_jW_i = Xi−1

j=1

ρ_jW_i,(i= 2,3, ..., K). (2.23)

また，W_i=W_o+W1_i+W2_iであるので，

W_i=W_o+ Xi

j=1

ρ_jW_j+

i−1X

j=1

ρ_jW_i,(i= 1,2, ..., K) (2.24) が成り立つ．

クラスiの客の平均待ち時間W_iは，式(2.24)より，次式となる．

W_i= W_o

(1−^Pi−1_j=1ρ_j)(1−^Pi_j=1ρ_j),(i= 1,2, ..., K) (2.25) ただし，

W_o= XK

j=1

ρ_j

à b_2j 2(1/µ_j)

!

= 1 2

XK

j=1

λ_jb_2j である．

到着したクラスiの客の滞在時間T_iは，サービス時間の平均値は1/µ_iと，自分以上 の優先度をもつ現在システム内にいる客のサービス時間（T1_i）と，自分が待っている 間に到着する自分より高い優先度をもつ客のサービス時間（T2_i）からなる．

T1_iは，クラスi+ 1, i+ 2, ..., KがないとしたときのF CF Sの場合の待ち時間の平均 に等しいと考えられる．すなわち，

T1_i= W_oi

(1−^Pi_j=1ρ_j),(i= 1,2, ..., K) (2.26) ただし，

W_oi = 1 2

Xi

j=1

λ_jb_2j である．

T_iの間に，クラスjの客は平均してλ_jT_i個到着する．よって，次式が成り立つ．

T2_i = Xi−1

j=1

1

µ_jλ_jT_i =

i−1X

j=1

ρ_jT_i. (2.27)

T_i= 1/µ_i+T1_i+T2_iであるので，

T_i = 1

µ_i + W_oi

(1−^Pi_j=1ρ_j) +

i−1X

j=1

1

µ_jλ_jT_i,(i= 1,2, ..., K) (2.28) である．

クラスiの客の平均滞在時間T_iは，式(2.28)より，次式となる．

T_i= (1/µ_i)(1−^Pi_j=1ρ_j) +W_oi

(1−^Pi−1_j=1ρ_j)(1−^Pi_j=1ρ_j),(i= 1,2, ..., K). (2.29) M/G/1/∞/∞/SPT

SPTはサービス時間の最も小さい客を最優先する非割込み型スケジューリング方式であ る．SJF（Shortest Job First）とも呼ばれる．サービス時間をxとし，xのサービス時間を もつ客の平均到着率をλ(x)とする．前章で与えたλ_iはサービス時間が(x, x+dx)の間に なる客の到着率λ(x)dxに対応する．客の全員の平均到着率をλとすると，次式となる．

λ= Z _∞

0 λ(x)dx. (2.30)

また，サービス時間の分布関数をB(x)，サービス時間の密度関数をb(x)とすると，

λ(x) =λdB(x)

dx =λb(x) (2.31)

である．また，各クラスの客の利用率ρ(x)は，

ρ(x) =λ(x)x (2.32)

となる．式(2.25)の分母の(^Pi_j=1ρ_j)と(^Pi−1_j=1ρ_j)にあたる部分は，式(2.31)，式(2.32)よ り，次式となる．

Xi

j=1

ρ_j → Z _x+

0 ρ(y)dy, (2.33)

i−1X

j=1

ρ_j → Z _x−

0 ρ(y)dy. (2.34)

サービス時間xの客の平均待ち時間は次式となる．

W(x) = W_o

³

1−λ^R₀^x−yb(y)dy^{´ ³}1−λ^R₀^x+yb(y)dy^´ (2.35) ただし，

W_o = Z _∞

0 ρ(y)y

2dy= λ 2

Z _∞

0 y²b(y)dy (2.36)

である．

したがって，サービス時間xの客の平均滞在時間は次式となる．

T(x) =x+ W_o

³

1−λ^R₀^x−yb(y)dy^{´ ³}1−λ^R₀^x+yb(y)dy^´. (2.37)

M/G/1/∞/∞/SRPT

SRPTは残余サービス時間の最も小さい客を最優先する割込み型スケジューリング方式で ある．サービス時間の分布関数をB(x)，サービス時間の密度関数をb(x)とすると，サービ ス時間xの客の平均滞在時間は次式で与えられる．

T(x) = Z _x

0

1

1−λ^R₀^xyb(y)dydt+ b₂(x) +x²(1−B(x))

³

1−λ^R₀^x−yb(y)dy^{´ ³}1−λ^R₀^x+yb(y)dy^´ (2.38) ただし，

b₂(x) = Z _x

0 y²b(y)dy (2.39)

である．

2.3.1 リアルタイムタスクの時間属性

リアルタイムタスクJ_iは，表2.4で示す時間属性で特徴付けられる．これらの時間属性 の関係を図2.8に示す．添字のiは，i番目のタスクを表す．リアルタイムタスクには，周期 タスク，非周期タスク，散発タスクという分類がある．

1. 周期タスク

一定周期で起動されるタスク 2. 非周期タスク

不規則に外部の要求があるたびに起動されるタスク 3. 散発タスク

非周期のタスクの一種で最小起動間隔がある場合のタスク

また，表2.4以外の時間属性として，周期T_i，フェーズφ_iなどの属性がある．周期とは周 期タスクの起動間隔であり，フェーズとは，周期タスクが一番始めに起動された時刻である．

running

Ci

si fi

ai di

running

C_i

si fi

ai d_i

Li

ready

Xi

図2.8: リアルタイムタスクの時間属性

2.3.2 EDF

EDFはタスクが動的に到着し，割込みが認められている場合に，単一プロセッサにおい てn個のタスクセットをスケジュールするアルゴリズムである．EDFは次の規則に従う[7]． 任意の到着時刻でn個の独立なタスクセットが与えられた時，任意の時点での全ての実行可 能タスクの中で，最も早い絶対デッドラインを持つタスクを実行する．EDFは最大遅れを 最小にする点で最適となる．

また，EDFはデッドライン以外の条件は使用しないので，周期タスクにも適用可能であ る．EDFの計算量はO(n²)となる．

表2.4: 時間属性 時間属性 説明

起動時刻a_i タスクが実行の準備ができる時間．リクエストタイム（Request time），

またはリリースタイム（Release time）とも呼ばれ，r_i で表される．

実行時間C_i プロセッサがタスクを中断することなく実行するのに必要な時間 デッドラインd_i システムに被害を与えずに，タスクが終了するまでの時間

開始時刻s_i タスクが実行を開始する時間 終了時刻f_i タスクが実行を終了する時間

遅れL_i L_i =f_i−d_iは，デッドラインに関してタスク実行の遅れを表している．

デッドラインより先に終了したならば，遅れは負になる．

余裕時間X_i X_i =d_i−a_i−C_i は，タスクがデッドライン内で終了するために， 起動 が遅れることのできる最大時間

2.3.3 最適性とスケジュール可能性

スケジュール可能性とはあるタスクセットにおいて，各タスクのデッドラインを満足する スケジュールができることである．

• スケジュール可能性に関する最適性

Dertouzosによって与えられた証明で，EDFがスケジュール可能性の点で最適である

ということが示されている[34, 35]．これは，タスクセットJ においてスケジュール 可能なスケジュールが存在するならば，EDFはそれを見つけることができるというこ とを表している．証明を拡張して，EDFが最大遅れを最小にするということを示すこ とも可能である．

σを一般的なアルゴリズムAによって与えられるスケジュールとし，σ_EDF をEDFに よって与えられるスケジュールとする．証明では，以下の略語を用いる．

– σ(t): 時間[t, t+ 1)での実行するタスク

– E(t):時刻 tにおいて，最も早いデッドラインをもつ実行可能なタスク

– t_E(t): タスクE(t)の次のタスクが，現在のスケジュールにおいて実行を開始す る時刻

もし，σ 6= σ_EDF ならば，σにはσ(t) 6= E(t) なる時刻tが存在する．σ(t)とE(t) の転置によって，最大遅れが増加しないことを基本的な考え方として証明する．も し，スケジュールσが時刻tで開始し，Dがタスクセット内で最も遅いデッドライン

（D= max_id_i）であるならば，σ_EDF は，高々D回の置換によってσから得られる．

任意のスケジュールσをEDFに変換するアルゴリズムが以下である．

Algorithm: interchange {

if(σ(t)6=E(t)) { σ(t_E) =σ(t);

σ(t) =E(t);

} } }

各時点tにおいて，このアルゴリズムは時点tでスケジュールされるタスクσ(t)が最 も早いデッドラインE(t)であるかどうかを調べる．もしそうであるならば何もせず，

そうでなければtとt_Eのタスクが入れ替わる．上記以降の入れ替えによって最大遅れ が増加することは絶対にない．したがって，EDFは最適である．

図2.9にこのアルゴリズムの適用例を示す．図2.9の(a)に対してEDFに変換するア ルゴリズムを適用すると，時刻t= 4で最初の転置が行われる．この時，実際にはJ₄ にプロセッサが割当てられているが，時刻t_E = 4でスケジュールされているJ₂が最 も早いデッドラインを持つので，その結果として，黒で示した2つの時間で実行され るタスクが入れ替わり，(b)で示したようにスケジュールされる．このアルゴリズムは t=Dまでの全ての時間で適用される．

• スケジュール可能性の判定

EDFは非周期タスク，つまり事前に起動時間がわからない場合に適用できるスケジュー リング方式である．EDFを動的スケジューリングとして用いる場合には，スケジュー ル可能性の判定も動的に行うことになる．J を前もって保証された現在のアクティブ なタスクセットとし，J_newを新たに到着したタスクとする．J_newがシステムに入る のを認めるために，新たなタスクセットJ⁰ =J∪ {J_new}がスケジュール可能である かどうかを保証しなければならない．タスクセットJ⁰はEDFによってスケジュール 可能であり，最悪ケースにおいてJ⁰の全てのタスクがデッドライン前に終了すること を示す必要がある．このことは，各タスクに対して最悪終了時間f_iがデッドラインd_i より小さい，または等しいことを意味する．

一般性を欠くことなく，J₁が最も早いデッドラインを持つようにJ⁰（J_newを含む）内 の全てのタスクが，デッドラインの早い順に並べられていると仮定する．さらに，タ スクが割込み可能なので，時刻tでJ_newが到着したときにはいくつかのタスクが部分 的に実行されている．c_i(t)をタスクJ_iの残余実行時間とすると，時刻tでタスクJ_i の最悪終了時刻は次のように求められる．

f_i = Xi

k=1

c_k(t) +t. (2.40)

したがって，スケジュール可能性は以下の条件によって保証されることになる．

∀i= 1, ..., n, Xi

k=1

c_k(t) +t≤d_i. (2.41)

図2.9: 最大遅れが増加しない基本的な考え