Naoki Kurosawa
n-kur****@nri*****
2003年 12月 18日 (木) 19:29:09 JST
黒澤です。
ワークフローシステム構想その6
#絵がないとだんだんつらくなってきた…。
流量と優先度の制御についてです。
ワークフローシステム上で作成できるプロセス数は無制限。
同時に実行されるプロセス数は、ワークフローエンジンのスレッドプールサイズ
を調節することで流量を制御する。
一度にワークフローシステム上に作成できるプロセスの数と、
同時に実行されるプロセスの数は別物であることに注意。
作成できるプロセス数は無制限だが、
任意の瞬間を見たときに同時に動いているのはスレッドの数による。
その他の流量制御・優先度制御機能は以下の通り。
・プロセス定義に、デフォルト優先度を記述できる。
(優先度については後述)
・プロセス定義に、そのプロセスが同時に実行される最大数を記述できる。
※プロセスの作成自体は無制限。「同時に実行される数」の指定。
#以下の部分は現時点では理解しづらいかもしれません。
#スレッドプールだの何だのと、エンジンがどうできているかに依存する説明
#なので。
■優先度
ワークフロー・スレッドプールから出てきたスレッドが、どのプロセス
を実行するのかを制御することで、実行の優先度をプロセス間で調整。
優先度は、以下の5つ。
・Realtime
スレッドが割り当てられたら、プロセスのアクティビティが何かしらの待ち
処理に入らない限りそのスレッドはプロセスの処理をし続ける。
・High
・Normal
・Low
・Idle
Idle以外のプライオリティを持つプロセスが実行中でないときのみ
実行される。
Realtimeプライオリティは、ひとつのプロセスが終わるまでのスピードを重視
するオプション。
それ以外は、ワークフローシステム上のプロセス全体が並列で進むことを
重視するオプション。
High, Normal, Lowの優先度はスケジューラの動き(以下の説明)で説明。
■クォンタム
クォンタムとは、1つのプロセスが一度に実行される最小の時間(たとえば0.5秒
とか)。
プロセスにスレッドが割り当てられた瞬間から、経過時間を計測し始める。
1つアクティビティを実行し終えるたびに経過時間をチェックし、
クォンタムを超えたらそのプロセスの処理をいったん停止。
別のプロセスを処理する。
クォンタムの長さはプライオリティごとに定義される。
・Realtimeは無限
・High, Normal, Lowは設定可能
Highは400ms, Normalは200ms, Lowは100msなど
・Idleはゼロ
→つまり、1つアクティビティを実行するたび、そのプロセスの処理が
いったん停止される。
■実行頻度
RealtimeやHighプライオリティのプロセスが大量にあるとき、
それ以下のプライオリティのプロセスがまったく実行されない(CPU飢餓)状態
になってしまう。これを回避するため、実行頻度という考え方を導入する。
Realtimeプライオリティに10回割り当てたらHighプライオリティに1回割り当て
る、という具合。
設定値
・Realtime_High_Ratio
Highプライオリティに対するRealtimeプライオリティの倍率。
10とするとRealtimeに10回割り当てたらHighに1回割り当てる。
-1とすると無限大。Realtimeプライオリティに実行可能プロセスがある限り
Realtimeプロセスが実行され続ける。
0を指定してはならない。
・High_Normal_Ratio
Normalプライオリティに対するHighプライオリティの倍率。-1とすると無限大
・Normal_Low_Ratio
Lowプライオリティに対するNormalプライオリティの倍率。-1とすると無限大
■スレッド割り当てアルゴリズム
まず、プロセス群をプライオリティ毎にリストにしておく。
また、プライオリティごとにスレッド割り当て回数をカウントするカウンタを
用意しておく(Idle以外)。
スレッドプールにスレッドがあるとき、以下のようなアルゴリズムで
プロセスにスレッド割り当てを行う。
1.[Realtime割り当て]
i. Realtime_High_Ratioに指定された回数割り当てていたら、カウンタを
リセットし2番に移る。Realtime_High_Ratioが-1ならこの判断はなし。
ii.Realtimeプライオリティ・プロセスのリストの先頭をチェックし、
スレッドが割り当てられておらず、かつpull型アクティビティの待ち状態
でもなければ、そのプロセスをリストの最後尾に移し、カウンタリセット、
スレッド割り当て。
2.[High割り当て]
1番でスレッド割り当てされず…、
i. High_Normal_Ratioに指定された回数割り当てていたら、カウンタを
リセットし3番に移る。
ii.Highプライオリティ・プロセスのリストの先頭をチェックし、
スレッドが割り当てられておらず、かつpull型アクティビティの待ち状態
でもなければ、そのプロセスをリストの最後尾に移し、カウンタリセット、
スレッド割り当て。
3. [Normal割り当て]
以下同じ
4. [Low割り当て]
以下同じ
5. Idleプロセス以外が実行中でないかをチェック。
実行中なら6に移る。
実行中でなければIdleプライオリティ・プロセスのリストの先頭をチェック
し〜以下同じ。
6. 1〜5まででスレッド割り当てされなければもう一回だけ1〜4を実行する。
それでも割り当てられなければ、スレッドをプールにおいたままにする。
正確には、これと同時に
「プロセス定義に、そのプロセスが同時に実行される最大数を記述できる」
を実現する必要があるため、
ii「プロセスのリストの先頭をチェックし〜」のところを詳しく書くと、
そのプロセスが他に実行されている数をチェックし、既に最大数に達して
いたら、リストの次のエントリに移り、iiに戻る。
となります。
#「pull型アクティビティ」については「ワークフローシステム構想4(機能)」
#の「プロセスに含まれるアクティビティの実行制御」を参照。
--
Naoki Kurosawa <naoki_kuros****@ybb*****>, <n-kur****@nri*****>
Sharpen up JAVA skills. - Robocode Rumble-JP Project -
http://rumble-jp.sourceforge.jp/ http://robocode.ddo.jp/rumblejp/