3

Cで最早締切スケジューリングを実装したいのですが、ネット上でアルゴリズムを見つけることができません..

以下の例では、時間が 0 のときに A1 と B1 の両方が到着することがわかります。A1 は締め切りが最も早いため、最初にスケジュールされます。A1 が完了すると、B1 にプロセッサが渡されます。時間が 20 になると、A2 が到着します。A2 は B1 よりも早い期限を持っているため、B1 は中断され、A2 は完了まで実行できます。その後、時刻 30 で B1 が再開され、時刻 40 で A3 が到着します。ただし、B1 は終了期限が早く、時間 45 で完了するまで実行できます。次に、A3 にプロセッサが与えられ、時間 55 で終了します。しかし、解決策が思いつきません。アルゴリズム。ありがとう..

例のイメージ

例 http://imageshack.us/photo/my-images/840/scheduling.png/

4

2 に答える 2

4
  • プロセスが終了したとき (および開始時)、最も低いプロセスをprocessTimeToDeadline - processTimeToExecute新しい現在のプロセスとして取得します。
  • 新しいプロセスが到着したら、次の場合にのみ現在のプロセスを置き換えますnewProcessTimeToDeadline - newProcessTimeToExecute < currentProcessTimeToDeadline - currentProcessTimeStillNeededToExecute。

注: 複数の CPU でこれを行うと、NP 完全なマルチプロセッサ スケジューリングの問題が発生します。

于 2011-10-02T15:11:52.677 に答える