問題タブ [queue]

私は私の質問を

Simple Queue Implementations の代わりに BlockingQueue Implementations をどこで使用する必要がありますか?

に

最後の要素にアクセスする時間など、さまざまな速度、同時実行性、またはその他のプロパティなどの側面を考慮して、Queue 実装に対する BlockingQueue の利点/欠点は何ですか。

私は両方の種類のキューを使用しました。Blocking Queue は通常、並行アプリケーションで使用されることを知っています。ByteBuffer オブジェクトのプレースホルダーが必要な単純な ByteBuffer プールを作成していました。最速でスレッドセーフなキューの実装が必要でした。要素への一定のアクセス時間を持つ ArrayList のような List 実装もあります。

BlockingQueue と Queue と List の実装の長所と短所について誰でも議論できますか?

現在、これらの ByteBuffer オブジェクトを保持するために ArrayList を使用しています。

これらのオブジェクトを保持するためにどのデータ構造を使用すればよいでしょうか?

ファイルに保存されているプロセスのリストから最初のプロセスを実行し、ファイルがキューであるかのように最初の行をすぐに削除し、「pop」と呼ぶにはどうすればよいですか?

単純なテキスト ファイルにリストされている最初のコマンドを、区切り文字として \n をポップな方法で呼び出したいと思います。

図1：

図 2:

次の方法で最初のコマンドをポップしpopcmdます。

図 3:

私は、キューの一般的なカーネル実装、つまり先入れ先出しデータ構造に関する情報を探していました。おそらく一般的に使用されるものであり、リンクされたリストの標準（list_head構造の形式）があるため、あるかもしれないと思いました。私が見つけられない標準的なキューの実装がありますか、それともリンクされたリストをキューとして使用し、最善を尽くすのが一般的な方法ですか?

簡単に言うと、私は、通常の理由で大規模な Web アプリケーションを書き直すプロジェクトに取り組んでいます。書き換えの主な目的は、単一のサーバーで実行されているこの大きな単一のアプリケーションを、多くのサーバーで実行できる多くの小さな分離アプリケーションに分離することです。

ここに私が望むものがあります：

HTTP私は主要な輸送メカニズムになりたいです。たとえば CMS などの 1 つのアプリケーションが更新されると、HTTP 経由でブローカーに連絡し、言うと、ブローカーは言うために a を"I've changed"送り返します。200 OK"thanks I got the message"

次に、ブローカーは、CMS の変更について知りたいと思っている他のアプリケーションのリストを調べ、メッセージについて知りたいとブローカーに伝えたときにアプリケーションが残した URL にメッセージを渡します。

他のアプリケーションは200 OK、メッセージを受信すると戻ります。そうでない場合、ブローカーはメッセージを保持し、誰かが次にそのアプリケーションに接続しようとするときに備えてキューに入れます。

問題は、どこから始めればよいのか、それを実現するために何が必要なのかさえわからないことです。私は 、 、 などを見てきましたがXMPP、ActiveMQ来年RabbitMQはMule ESBこのようなものと一緒に円を描いて過ごすことができることがわかります。

私は難しい方法でレッスンを学ぶことを避けたいので、誰かが個人的な経験からアドバイスを提供できますか.

最近ビデオ スクリプトを新しいサーバーにインストールしましたが、(mencoder を介して) 1 つのビデオの変換を開始し、終了する前に別のビデオを変換しようとするため、4+ を変換しようとします。同時にサーバーがシャットダウンします。スクリプト開発者は次のように述べています。

「各ビデオを PHP バックグラウンド プロセスで変換します。サーバー上の PHP バックグラウンド プロセスの数を制限し、それらをキューに入れる方法があるかもしれません。」

それで、これはどのように行われますか？

よろしく

Python コードでプライオリティ キューを使用する必要があります。

• プライオリティ キューの高速な実装を探しています
• 最適には、キューを一般的なものにしたいと考えています(つまり、指定された比較演算子を持つ任意のオブジェクトに対して適切に機能します)。

効率的なものを探し回って、 heapqに出くわしましたが、:

• heapqネイティブの Python で実装されている よりも高速なものを探しているので、高速ではありません。
• 良さそうですが、整数のみ指定されているようです。比較演算子を持つすべてのオブジェクトで機能すると思いますが、必要な比較演算子を指定していません。
• 更新: での比較ではheapq、チャーリー・マーティンが提案するように a を使用するか(priority, object)、単に__cmp__オブジェクトに実装することができます。

Linux マシンでプロセッサ キューの長さ (実行する準備ができているが現在実行されていないプロセスの数) を特定しようとしています。Windows にはこのメトリックの WMI 呼び出しがありますが、Linux についてあまり知らないので、情報を得るために /proc と 'top' をマイニングしようとしています。CPU のキューの長さを決定する方法はありますか?

編集して追加: メトリックに関する Microsoft の言葉: 「準備はできているが、現在実行中の別のアクティブなスレッドのためにプロセッサで実行できない 1 つ以上のスレッドのコレクションは、プロセッサ キューと呼ばれます。」

同期 http リクエスト/レスポンス モデルを非同期キュー ベースのモデルに接続する良い方法は何ですか?

ユーザーの HTTP 要求が来ると、キュー (この場合はbeanstalkd ) に送られる作業要求が生成されます。ワーカーの 1 人がリクエストを受け取り、作業を行い、レスポンスを準備します。

キュー モデルはリクエスト/レスポンスではありません。レスポンスではなく、リクエストのみがあります。問題は、応答を HTTP の世界に戻し、ユーザーに戻すにはどうすればよいかということです。

アイデア:

1. Beanstalkd は、軽量のトピックまたはキュー (チューブと呼ばれます) をサポートしています。リクエストごとにチューブを作成し、ワーカーにそのチューブでメッセージを作成させ、http プロセスをチューブに置いて応答を待機させることができます。これは特に好きではありません。Apache プロセスがメモリを占有しているからです。

2. http クライアントに応答をポーリングさせます。ユーザーの最初の HTTP 要求は、キューでジョブを開始し、すぐに戻ります。クライアント (ユーザーのブラウザー) は定期的に応答をポーリングします。バックエンドでは、ワーカーはその応答を memcached に置き、nginx を memcached に接続して、ポーリングが軽量になるようにします。

3. コメットを使用します。2 番目のオプションに似ていますが、ポーリングを回避するためにより洗練された http 通信を使用します。

簡単でよく知っているので、私は2に傾いています（私はまだコメットを使用していません）。おそらく、私が思いもよらなかった、はるかに優れた明白なモデルもあると思います。どう思いますか？

更新:これが Hashed Timing Wheels の私の実装です。パフォーマンスと同時実行性を改善するアイデアがあれば教えてください。(2009 年 1 月 20 日)

更新: Hierarchical and Hashed Timing Wheelsを使用してこの問題を解決しました。(2009 年 1 月 19 日)

タイムアウト処理用に最適化された特別な目的のタイマーを Java で実装しようとしています。たとえば、ユーザーは期限のあるタスクを登録でき、タイマーは期限が過ぎたときにユーザーのコールバック メソッドに通知できます。ほとんどの場合、登録されたタスクは非常に短い時間内に完了するため、ほとんどのタスクはキャンセルされるか (例: task.cancel())、将来に再スケジュールされます (例: task.rescheduleToLater(1, TimeUnit.SECOND))。 .

このタイマーを使用して、アイドル状態のソケット接続を検出し (たとえば、10 秒以内にメッセージが受信されない場合に接続を閉じる)、書き込みタイムアウトを検出します (たとえば、書き込み操作が 30 秒以内に終了しない場合に例外を発生させます)。異常なネットワークの問題がない限り、タイムアウトは発生せず、クライアントはメッセージを送信し、応答が送信されます。

java.util.Timer または java.util.concurrent.ScheduledThreadPoolExecutor は、ほとんどのタスクがタイムアウトになると想定しているため、使用できません。タスクがキャンセルされた場合、キャンセルされたタスクは、ScheduledThreadPoolExecutor.purge() が呼び出されるまで内部ヒープに格納されます。これは非常にコストのかかる操作です。(O(NlogN) もしかして?)

CSクラスで学んだ従来のヒープまたは優先度キューでは、要素の優先度の更新は高価な操作でした（多くの場合、要素を削除して再挿入することによってのみ達成できるため、O（logN）新しい優先度値. フィボナッチヒープのようないくつかのヒープには、reduceKey() と min() 操作の O(1) 時間がありますが、少なくとも私が必要としているのは、高速な increaseKey() と min() (または reduceKey() と max()) です。 .

この特定のユースケースに対して高度に最適化されたデータ構造を知っていますか? 私が考えている戦略の 1 つは、すべてのタスクをハッシュ テーブルに保存し、すべてのタスクを 1 秒ごとに反復処理することですが、それほど美しいものではありません。