1

次のような構造体の両端キューを使用します。

struct{
    int ID;
    int arrivalTime;
    int burstTime;
};

入力が次のようになるように、構造体の両端キューをどのようにステップスルーしますか?

0 0 3
1 5 2
3 8 4

各行がそれぞれ構造体の ID、arrivalTime、burstTime である場合、次のように出力できます。

Time 0 Process 0 is running
Time 2 Process 0 is running
Time 3 Processor is Idle
Time 5 Process 1 is running
Time 7 Processor is Idle
Time 8 Process 3 is running
Time 10 Process 3 is running

この出力は 2 のタイム クォンタムを想定しています。これを 1 つの deque だけで行う方法はありますか、またはこれを処理するための FIFO キューとして別のデッキを作成する方が簡単でしょうか? 経過時間を追跡するために整数が必要になることはわかっていますが、それ以外は、この問題が本当に私を困惑させています。私を失望させるのはアイドル時間です。C++ コードや疑似コードでさえ、どんなヘルプも本当に役に立ちます。ありがとう！

4

1 に答える 1

0

経過時間を追跡するために整数が必要になることはわかっています

経過時間、現在のプロセス、次のプロセスの 3 つの値から始めます。スケジューリング ループは次のようになります。簡単にするために、次のプロセスを選択するロジックをスタンドアロン関数に入れました。

time = 0;
currentProcess = deque.end();
while(some processes remaining)
{
    nextProcess = getNextProcess(time, currentProcess, deque);

    if(nextProcess->arrivalTime > time)
    {
        // nothing to do now
        // advance time by smaller of quota or nextProcess->arrivalTime
    } else {
        // at least one process has work ready
        if(currentProcess != nextProcess)
        {
            // preemt currentProcess
            // start nextProcess
            // advance time by the smaller of quota or nextProcess->burstTime
            // reduce nextProcess->burstTime by the time advanced
        } else {
            // continue with current process for quota or its remaining burstTime
            // reduce its burstTime
        }
    }

    currentProcess = nextProcess;
}

実装getNextProcessは優先度の基準によって異なります。単純なアプローチは次のようになります。

  • 位置からdeque開始しcurrentProcess + 1ます。最後まで来たら、最初から続けます。
  • arrivalTimeより大きい最小のプロセスに注意してくださいtime。呼びましょうclosestCandidate
  • arrivalTime <= timeとで適切なプロセスを見つけたら、それburstTime > 0を返します
  • currentProcess再度ヒットした場合は、currentProcessとのclosestCandidateどちらが処理に適しているかを判断し、それを返します。

最後に行うことは、ループ条件を効果的に実装することです。私はあなたが理解するためにそれを残しておきます.

注:dequeここで最適なコンテナーかどうかはわかりませんforward_list。プロセスが終了したら、プロセスを使用して削除する可能性があります。両端キューでもこれを行うことができますが、それは O(n) 操作です。

于 2012-10-10T14:11:23.873 に答える