1

構造体のベクトルがあり、構造体は次のようになっています。

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

ベクトルにこのデータを入力した後:

1 1 5
2 3 2
3 5 10

ここで、各行は個々の構造体の ID、arrivalTime、および burstTime です。「for」ループまたは「while」ループを使用して、ベクトルのインデックスをステップ実行し、次のようなものを出力できる方法でデータを計算するにはどうすればよいでしょうか。

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

SJF と RR のスケジューリングは非常に似ていることを知っていますが、RR にはタイム クォンタムがあり、別のプロセスによってプリエンプトされる前にプロセスが任意の時間制限よりも長く続くことはありません。それを念頭に置いて、SJF を実装した後、RR は SJF アルゴリズムを少し変更するだけで簡単に実現できると思います。

SJF の実装について私が考えた方法は、最初に到着時間に基づいてベクトルをソートし、次に 2 つ以上のベクトル インデックスが同じ到着時間を持つ場合は、最初に最も短い burstTime に基づいてソートすることです。その後、使用して

int currentTime = 0;

どのくらいの時間が経過したかを追跡し、

int i = 0;

ベクトルのインデックスとして使用し、「while」ループを制御するには、上記の目的の出力を出力できるアルゴリズムをどのように実装すればよいでしょうか? 私は何が起こる必要があるかについての一般的な考えを持っていますが、機能する方法でコードにすべてをレイアウトすることはできないようです.

currentTime が次に早いarrivalTimeよりも小さい場合は常に、プロセッサがアイドル状態であり、currentTime をこのarrivalTimeに設定する必要があることを意味します。

vector[i+1].arrivalTime < currentTime + vector[i].burstTime の場合、vector[i].burstTime を vector[i+1].arrivalTime - currentTime に設定し、currentTime を vector[i に設定する必要があります。 +1].arrivalTime、次に currentTime とプロセス ID を出力します

これらは実装する単純な数学演算であることは知っていますが、自分が望むように機能するようにすべてをレイアウトする方法を考えることができません。それがループする方法と、いくつかのプロセスが同じ到着時間を持つことが時々ある方法は、私をうんざりさせます。何が起こっているかを追跡するために、さらに変数が必要ですか? バースト時間の短い新しいプロセスによってプロセスがプリエンプトされて中断されるたびに、ベクター内のすべてのアイテムの到着時間をシフトする必要がありますか? C++ コードまたは疑似コードでさえ、どんな助けでも大歓迎です。SJF がどのように機能するかという概念についてはかなりしっかりしているように感じますが、理解していることをコードに変換するのに苦労しています。

ありがとう!

4

1 に答える 1

1

SJF と RR のスケジューリングは非常に似ていることを知っていますが、RR にはタイム クォンタムがあり、別のプロセスによってプリエンプトされる前にプロセスが任意の時間制限よりも長く続くことはありません。

それは正しくないと思います。少なくともそれは私がそれを学んだ方法ではありません。RR は、SJF よりも FCFS (先着順) に近いです。

SJF を実装する 1 つの方法は、実行時間に基づいて着信ジョブを保留リストに挿入することです。新しいジョブの実行時間が最後のジョブの実行時間よりも長い場合、挿入位置は最後になります。それ以外の場合は、受信ジョブよりも実行時間が長い最初のジョブの前になります。スケジューリングは簡単です。保留リストの先頭にあるジョブを削除し、そのジョブを実行して完了するだけです。実行時間の長いジョブよりも短いジョブが次々と入ってきて処理されると、実行時間の長いジョブは実行されない可能性があります。

ラウンド ロビンを実装する 1 つの方法は、FCFS と同様に FIFO を使用することです。新しいジョブはキューの最後に追加されます。スケジューリングも簡単です。キューの先頭にあるジョブを削除して処理します。これまでのところ、これはまさに FCFS が行うことです。2 つの違いは、RR にはジョブを実行できる時間に制限があることです。ジョブが終了するまでに一定時間以上かかる場合、ジョブはその時間だけ実行され、キューの最後に追加されます。この定式化では、タイム クォンタムが最も長く実行されているジョブの実行時間よりも長い場合、RR は FCFS と同等であることに注意してください。

SJF のように、これらの不完全なジョブをプロセス リストの途中に挿入することもできると思いますが、それは私にはあまりラウンドロビン的ではないように思われ、スケジューリングはかなり面倒です。「常に先頭でジョブを実行する」というスケジューリング ルールを使用することはできませんでした。

于 2012-10-09T10:02:47.583 に答える