問題タブ [round-robin]

レディ キューにプロセスが 1 つしかなく、ラウンド ロビン スケジューリングを使用するシステムで、コンテキスト スイッチは発生しますか?

単一プロセスの現在の CPU バーストが、ラウンドロビン アルゴリズムの複数のタイム スライスにまたがっているとします。

私の推論は以下の通りです

一般的なケースでタイマー割り込みが発生したときに実行される手順は次のとおりです。

1. 割り込みが発生します。カーネル モードに切り替える
2. OS は現在のコンテキストを PCB に保存します (現在のプロセスのレジスタ、プロセス状態、およびメモリ管理情報を保存します)
3. データや命令キャッシュ、TLB のフラッシュなど、多くのアーキテクチャ固有の操作を実行します。
4. 現在のプロセスを準備完了キューに入れる
5. 実行する新しいプロセスを選択してください
6. そのプロセスの PCB からコンテキストをロードする
7. ユーザーモードに切り替えます。新しいプロセスの実行を開始します

私は今、OS が最初に準備完了キューを検査し、他のプロセスがあるかどうかを確認することを考えています。何もない場合は、コンテキスト スイッチの必要はありません。したがって、タイマー割り込みの処理には、ユーザー モードとカーネル モード間の切り替え、準備完了の Q の確認、およびプロセスの実行を再開するためのユーザー モードへの切り替えが伴います。

これは何が起こるのですか？それとも、孤立したプロセスの現在の状態の不必要な保存と同じ状態の復元を含む適切なコンテキストの切り替えが行われますか?

後者が発生した場合、特別な理由はありますか?

この混乱は、そのような状況でのコンテキスト切り替えに費やされた時間の計算に関する試験問題の質問が原因で発生しました。与えられた答えは、コンテキストの切り替えが行われることを意味します。

カーネルコードを調べたことのある人がこれを理解できることを願っています。したがって、stackoverflowに関するこの質問。

ラウンド ロビン トーナメント アルゴリズムは、チームがゲームごとに対戦する場合にのみ機能します。しかし、同じゲームで 2 つ以上のチームが対戦するスポーツやゲームのトーナメントにどのように実装するのでしょうか。たとえば、2 対 n のチームが 2 対 n のゲームで対戦するペイントボール トーナメント。すべてのチームが可能な限り 1 回だけホーム チームになる必要があるという制約を引き続き維持します (チームを均等に分割できない場合は、ホーム チームにならないチームをできるだけ少なくしてもかまいません)。

何か案は？与えられたのは、チーム数、ゲーム数です。おそらく、ゲームごとのチーム数は与えられているかもしれません。

今朝、Linux のリアルタイム スケジューリングについて読みました。「Robert Love による Linux システム プログラミング」という本によると、そこには 2 つの主要なスケジューリングがあります。1 つは SCHED_FIFO、fifo で、2 番目は SCHED_RR、ラウンド ロビンです。そして、fifo と rr アルゴリズムがどのように機能するかを理解しました。しかし、システムコールがあるので、

プロセスのスケジューリング ポリシーを明示的に設定できます。そのため、場合によっては、root によって実行される 2 つのプロセスが異なるスケジューリング ポリシーを持つことがあります。1 つのプロセスが SCHED_FIFO を持ち、別のプロセスが SCHED_RR を持ち、同じ優先度を持つ。その場合、どのプロセスが最初に選択されますか？FIFO クラスのプロセスまたは RR クラスのプロセス? なんで？

この場合を考えてみましょう。A、B、Cの3つのプロセスがあります。すべてが同じ優先度を持っています。A と B は RR クラスのプロセスで、C は FIFO クラスのプロセスです。A と B は実行可能です (したがって、どちらもある時間間隔で交互に実行されます)。そして現在、Aは実行中です。これで C が実行可能になります。この場合、

コンピュータプロセッサには、実行するN個のタスクが与えられます（1≤N≤50,000）。i番目のタスクにはTi秒の処理時間が必要です（1≤Ti≤1,000,000,000）。プロセッサは次のようにタスクを実行します。各タスクは1からNまで順番に1秒間実行され、その後プロセッサはタスク1からこれを繰り返します。タスクが完了すると、それ以降は実行されません。反復。タスクごとに、タスクが完了してから経過した合計実行時間を決定します。入力

入力の最初の行には整数Nが含まれ、次のN行には整数T1からTNが含まれます。出力

N行を出力します。そのi番目には、タスクiが処理されたときに経過した時間を表す整数が含まれています。

例

入力： 5 8 1 3 3 8

出力： 22 2 11 12 23

2番目のタスクは最初の反復中に完了し、2秒で終了します。3番目の反復では、3番目と4番目のタスクはそれぞれ11秒と12秒で完了します。最後に、8回目の反復で、最初と最後のタスクはそれぞれ22秒と23秒で完了します。

アプローチは何ですか？

これは私のコードです：

しかし、これはspojでは受け入れられません...

Linuxカーネルで同時に機能する3つ以上のスケジューリングポリシーがありますか？FIFOとラウンドロビンは同じマシンで動作できますか？

問題 ：

A から E までの 5 つのバッチ ジョブがほぼ同時にコンピューター センターに到着します。実行時間は 10 分、6 分、2 分、4 分、8 分と見積もられています。それらの (外部で決定された) 優先順位は、それぞれ 3、5、2、1、および 4 であり、5 が最高の優先順位です。プロセスの平均所要時間を決定します。プロセス切り替えのオーバーヘッドを無視します。ラウンド ロビン スケジューリングでは、システムがマルチプログラミングであり、各ジョブが CPU を公平に配分すると仮定します。すべてのジョブは完全に CPU バウンドです。

解決策 #1次の解決策は、このページからのものです。

ラウンド ロビンの場合、最初の 10 分間、各ジョブは CPU の 1/5 を取得します。10 分が経過した時点で、C が終了します。次の 8 分間、各ジョブは CPU の 1/4 を取得し、その後 D が終了します。次に、残りの 3 つのジョブのそれぞれが、B が終了するまで 6 分間、CPU の 1/3 を取得します。5 つのジョブの終了時間は 10、18、24、28、30 で、平均 22 分です。

解決策 #2次の解決策は、ここのコーネル大学から提供されていますが、これは異なります (そして、これは私にとってより理にかなっています)。

ターンアラウンド タイムとは、ジョブが到着してからジョブが完了するまでの時間です。すべてのジョブが時間 0 に到着すると想定しているため、ターンアラウンド タイムは単純にジョブが完了する時間になります。(a) ラウンド ロビン: 以下の表は、各タイム クォンタムで処理されるジョブの内訳を示しています。* は、そのクォンタム中にジョブが完了することを示します。

結果は異なります。たとえば、最初の例では C は 10 分後に終了しますが、2 番目の例では C は 8 分後に終了します。

どれが正しいのですか、なぜですか? 私は混乱しています..事前に感謝します!

問題 ：

A から E までの 5 つのバッチ ジョブがほぼ同時にコンピューター センターに到着します。実行時間は 10 分、6 分、2 分、4 分、8 分と見積もられています。それらの (外部で決定された) 優先順位は、それぞれ 3、5、2、1、および 4 であり、5 が最高の優先順位です。プロセスの平均所要時間を決定します。プロセス切り替えのオーバーヘッドを無視します。ラウンド ロビン スケジューリングでは、システムがマルチプログラミングであり、各ジョブが CPU を公平に配分すると仮定します。すべてのジョブは完全に CPU バウンドです。

解決策 #1次の解決策は、このページからのものです。

ラウンド ロビンの場合、最初の 10 分間、各ジョブは CPU の 1/5 を取得します。10 分が経過した時点で、C が終了します。次の 8 分間、各ジョブは CPU の 1/4 を取得し、その後 D が終了します。次に、残りの 3 つのジョブのそれぞれが、B が終了するまで 6 分間、CPU の 1/3 を取得します。5 つのジョブの終了時間は 10、18、24、28、30 で、平均 22 分です。

解決策 #2次の解決策はコーネル大学から提供されたもので、ここで見つけることができます。問題がまったく同じ形式で与えられていても、明らかに以前のものとは異なります(ちなみに、この解決策は私にとってより理にかなっています)。

ターンアラウンド タイムとは、ジョブが到着してからジョブが完了するまでの時間です。すべてのジョブが時間 0 に到着すると想定しているため、ターンアラウンド タイムは単純にジョブが完了する時間になります。(a) ラウンド ロビン: 以下の表は、各タイム クォンタムで処理されるジョブの内訳を示しています。* は、そのクォンタム中にジョブが完了することを示します。

結果は異なります。たとえば、最初の例では C は 10 分後に終了しますが、2 番目の例では C は 8 分後に終了します。

どれが正しいのですか、なぜですか? 私は混乱しています..事前に感謝します!

私はいくつかのランダムな Icecast プレイリスト (ここで入手可能: http://dir.xiph.org/index.php ) を調べていますが、多くのプレイリストに同じ mp3 ファイルのリストが含まれているように見えるのはなぜでしょうか。

例えば：

GET http://dir.xiph.org/listen/193289/listen.m3u

価値があるのは、Icecast ストリームは、これらの Shoutcast タイプのライブ ストリーム (インターネット上のライブ ラジオを考えてください) を再生することを目的としているため、さまざまなトラックのリストがないことは理にかなっています..しかし、それらの繰り返しは何ですか? 異なるビットレートですか、それとも単なるミラーリングですか?

モバイルアプリ内でこれらのmp3の1つをストリーミングしようとしているので、これらすべてを尋ねているので、使用するURLをどうにかして把握する必要があるかどうか疑問に思っています...

HAProxy をロードバランサーとして使用したい。haproxy の背後に 2 つの rabbitmq サーバーを配置したいと考えています。両方の rabbitmq サーバーは、EC2 の異なるインスタンス上にあります。このリファレンスに従って HAProxy サーバーを構成しました。私は動作しますが、問題はメッセージがラウンドロビン パターンで公開されないことです。メッセージは 1 つのサーバーでのみ公開されます。私の要件に別の構成はありますか?

/etc/haproxy/haproxy.cfg の私の構成

アップデート：

これについていくつかの研究開発を行ったところ、HAProxy が rabbitmq サーバー上の接続でラウンド ロビンであることがわかりました。例: 10 の接続を要求すると、2 つの rabbitmq サーバーを介して 10 の接続をラウンドロビンし、メッセージを公開します。

しかし、問題は、HAProxy サーバーによって管理されるべき接続ではなく、メッセージをラウンドロビンしたいことです。つまり、一度に 1000 メッセージを HAProxy に送信すると、500 メッセージがウサギ サーバー 1 に送信され、500 メッセージがウサギ サーバー 2 に送信されます。私が従わなければならない構成は何ですか？

アップデート：

バランシングで leastconn もテストしましたが、HAProxy の動作は予期しないものでした。その質問をserverfault.comに投稿しました