operating-system - ラウンド ロビン スケジューリングとは

Question

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

Answer 1

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

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

優先度ベース (つまり、最も重要な人が最初)、先着順、最も早い締め切り (つまり、最も早い人が最初に出発する) など、スケジューリングには他にも多くの種類があります。スケジューリング アルゴリズムについては、Wikipedia でスケジューリングを確認してください。

Answer 2

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

私は、以下がラウンドロビン スケジューリングであるという InSciTek Jeff の示唆に同意しません。

つまり、ラウンド ロビン ローテーションで同じ優先順位の各タスクを、ローテーションで次のタスクに移行する前に、リソースのブロック状態に達するまで実行を許可できます。

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

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

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

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

InSciTek Jeff 宛ての編集 (私はコメント権限を持っていません) はい、タスクのロック/割り込みの無効化について言及していましたが、明らかにそれをうまく表現できませんでした。あなたは2番目のコメントで私を先取りしました（ハ！）。タイム スライスなしでラウンド ロビン スケジューリングが可能であるとあなたが信じているという、より重要な点について議論したいと思います。それとも、同じ時間ベースのタイム スライスを意味していましたか? 私は前者には同意しませんが、後者には同意します。私は学びたいと思っています。ありがとう。

ジェフに向けられた Edit2:

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

私はこの声明に同意しません。このドキュメントのセクション 2.2.3 を参照してください。見出しは Round-Robin Scheduling です。

ラウンド ロビン スケジューリングでは、タイム スライスを使用して、優先度が同じすべてのタスクに CPU を公平に割り当てます。同じ優先度を持つタスクのグループ内の各タスクは、定義された間隔またはタイム スライスで実行されます。ラウンド ロビン スケジューリングは、タイム スライスまたは間隔のパラメータを取る kernelTimeSlice( ) を呼び出すことによって有効になります。[...] ラウンド ロビン スケジューリングが有効で、実行中のタスクに対してプリエンプションが有効になっている場合、システム ティック ハンドラーはタスクのタイム スライス カウントをインクリメントします。

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

Answer 3

ここでの回答とウィキペディアの記事でさえ、定期的なタイムスライスを本質的に含むラウンドロビンスケジューリングについて説明しています。これは非常に一般的なことですが、ラウンドロビン スケジューリングとタイムスライスはまったく同じではないと思います。確かに、タイムスライスを意味のあるものにするために、各タスクにローテーションするときにラウンドロビン スケジューリングが暗示されますが、タイムスライスなしでラウンド ロビン スケジューリングを行うことができます。つまり、ラウンド ロビン ローテーションで同じ優先度の各タスクをリソース ブロック条件に達するまで実行し、次にローテーションで次のタスクを実行することができます。つまり、同じ優先順位のタスクが存在する場合、再スケジュール ポイントは時間優先ではありません。

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

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

Answer 4

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

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

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

2の最も一般的な方法が、リソースを待機するタイムスライス/歩留まりであることに同意しませんが、すでに述べたように、他の方法もあります。私が最初のMacがタイムスライシングを利用しなかったと誤解しない限り、彼らは自発的な利回り/リソースを待つ利回りを使用しました（20歳以上の脳細胞は時々間違っている可能性があります;）。

Answer 5

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

Answer 6

ラウンド ロビンは単純なスケジューリング アルゴリズムであり、優先度のないジョブ間で時間が均等に分割されます。

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