ラウンドロビンスケジューリングとは何ですか?

https://stackoverflow.com/questions/79389

09-06-2019
|

質問

マルチタスクオペレーティングシステムのコンテキストでは、ラウンドロビンスケジューリングという用語を聞くことがあります。それは何を指しますか?
他にどのようなスケジュール設定がありますか?

解決

ラウンドロビンスケジューリング

あなたが 100 人のゲストからなるパーティーのホストである場合、ラウンドロビンスケジュールでは、ゲスト 1 人あたり 1 分 (固定量) を費やすことになります。各ゲストを 1 人ずつ診察し、100 分後には各ゲストと 1 分間過ごしたことになります。さらに詳しくウィキペディア.

優先順位ベースのスケジューリングなど、他にも多くのタイプのスケジューリングがあります。最も重要な人から）、先着順、締め切りが早い順（つまり、早く帰る人が先）などまずはグーグルでスケジュールアルゴリズムを検索するか、チェックアウトしてください。ウィキペディアでスケジュールを設定する

他のヒント

私の知る限り、タイムスライスは実際のラウンドロビンスケジューリングシステムに固有のものです。

私は、次のような InSciTek Jeff の示唆に同意しません。はラウンドロビンスケジューリング:

つまり、ラウンドロビンローテーションで同じ優先度の各タスクは、リソースブロッキング条件に達するまで実行を許可されてから、ローテーションの次のタスクに譲ることができます。

これがどうしてラウンドロビンとみなされるのかわかりません。これは実際にはプリエンプティブなスケジューリングです。ただし、ラウンドロビンスケジューリングとプリエンプティブスケジューリングの両方の要素を含むスケジューリングアルゴリズムを使用することは可能です。ラウンドロビンスケジューリングとプリエンプションが両方とも有効になっている場合 (ラウンドロビンはデフォルトで無効になっています)、VxWorks はこれを行います。ラウンドロビンスケジューリングを有効にする方法は、ゼロ以外の値を指定することです。 カーネルタイムスライス.

私はこの声明に同意します。

したがって、タイムスライスベースのスケジューリングはラウンドロビンスケジューリングを意味しますが、ラウンドロビンスケジューリングは均等な時間ベースのタイムスライスを必要としません。

均等な時間を必要としないというのは正しいです。プリエンプションはそれを台無しにする可能性があります。実際、VxWorks では、ラウンドロビンスケジューリング中にタスクがプリエンプトされた場合、タスクが再び制御を取得すると、割り当てられた残りの時間実行されます。

Inscitek Jeff（コメントの特権はありません）に向けられた編集はい、タスクロック/割り込みの無効化について言及していましたが、明らかにそれほどうまく表現していませんでした。2 番目のコメントで私を先取りしました (笑)。私は、タイムスライスなしでラウンドロビンスケジューリングが存在できると信じているという、より重要な点について議論したいと考えています。それとも、均等時間ベースのタイムスライスを意味したのでしょうか?私は前者には同意しませんが、後者には同意します。私は学ぶことに熱心です。ありがとう。

ジェフに向けた編集 2:

ラウンドロビンはタイムスライスなしでも存在できます。これはまさに、kernelTimeSlice が無効 (ゼロ) の場合に VxWorks で起こることです。

私はこの意見に同意しません。見るこのドキュメントセクション 2.2.3 の「ラウンドロビンスケジューリング」の見出しを参照してください。

Round-Robinスケジューリングでは、時間のスライスを使用して、同じ優先順位を持つすべてのタスクにCPUの公正な割り当てを実現します。各タスクは、同じ優先順位を持つタスクのグループで、定義されたインターバルまたは時間スライスに対して実行されます。ラウンドロビンのスケジューリングは、kerneltimeslice（）を呼び出すことにより有効になります。これは、時間のスライスまたは間隔でパラメーターを使用します。...] Round-Robinスケジューリングが有効になり、実行されるタスクの先制が有効になっている場合、システムのティックハンドラーはタスクのタイムスライスカウントを増加させます。

タイムスライスはラウンドロビンスケジューリングに固有のものです。それ以外の場合は、タスクに依存して CPU 制御を放棄することになりますが、ラウンドロビンスケジューリングはこれを解決することを目的としています。

ここの回答と Wikipedia の記事でも、ラウンドロビンスケジューリングには定期的なタイムスライスが本質的に含まれると説明されています。これは非常に一般的ですが、ラウンドロビンスケジューリングとタイムスライスは、ない全く同じことです。確かに、タイムスライスを意味のあるものにするためには、各タスクをローテーションするときにラウンドロビンスケジューリングが暗黙的に指定されますが、タイムスライスを使用せずにラウンドロビンスケジューリングを実行することもできます。つまり、ラウンドロビンローテーションで同じ優先順位の各タスクは、リソースブロック状態に達するまで実行を許可され、リソースブロック状態に達した場合にのみローテーションで次のタスクが実行されます。つまり、同じ優先度のタスクが存在する場合、再スケジュールポイントは次のようになります。ない時間先制。

上記のアイデアは、実際に特に Wind River の VxWorks カーネルの場合に実現されます。優先順位スキーム内では、各優先順位のタスクはラウンドロビンで実行されますが、カーネルでその機能を特に有効にしない限り、タイムスライスは行われません。この柔軟性の理由は、十分に制限された時間内にブロックに実行されることがすでにわかっているタイムスライスタスクのオーバーヘッドを回避するためです。

したがって、タイムスライスベースのスケジューリングはラウンドロビンスケジューリングを意味しますが、ラウンドロビンスケジューリングは等しい時間ベースのタイムスライスを必要としません。

意見。2 つのメカニズムが 1 つに絡み合っているように見えます。OP の元のアサーション「マルチタスクオペレーティングシステムのコンテキスト内」のみを仮定すると、

1 - ラウンドロビンスケジューラは、常に循環キュー内の次のアイテムをスケジュールします。

2 - スケジューラがスケジューリングを実行するための制御をどのように取り戻すかは別個であり、無関係です。

2 の最も一般的な方法が、リソースを待機するタイムスライス/イールドであることに私は同意しませんが、前述したように、他にも方法があります。私の記憶が間違っていなければ、最初の Mac はタイムスライシングを利用しておらず、自発的なイールド/リソース待ちのイールドを使用していました (20 歳以上の脳細胞は時々間違っている可能性があります;)。

ラウンドロビンは、優先順位なしで時間をジョブ間で均等に分割する単純なスケジューリングアルゴリズムです。

たとえば、5 つのプロセスが実行されている場合、各プロセスは単位時間の 1/5 だけ実行されてから、別のプロセスの実行が許可されます。ラウンドロビンは通常、OS での実装が簡単です。

実際のところ、プリエンプティブスケジューリングとラウンドロビンが混同されています。実際、RR はプリエンプティブスケジューリングの一部です。

ラウンドロビンスケジューリングは、クォンタム (CPU が一度に任意のプロセスに与える最大時間) とも呼ばれるタイムシェアリングに基づいています。キュー内には複数のプロセス (完了までに異なる時間が必要なバースト時間) があり、CPU はそれらすべてを処理する必要があるため、クォンタム値に基づいてすべてのプロセスに等しい時間を与えるためにプロセス間を切り替え続けます。このタイプのスケジューリングは、ラウンドロビンスケジューリングとして知られています。ラウンドロビンのスケジューリングを簡単に理解するには、この簡単なビデオをチェックしてください。 https://www.youtube.com/watch?v=9hw-_qJ55K4

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow