いくつかのトランザクションの順序が重要な場合、どのようにキュー消費者をマルチスレッド化できますか？

私はオブジェクトのコレクションを操作するタスクのキューを持っています（例として、オブジェクトはアドレス帳のエントリです）。いくつかのトランザクションの順序が重要な場合、どのようにキュー消費者をマルチスレッド化できますか？

「Joeの電話番号を888-555-1212に更新する」タスクの例があります。

複数の "Update Joe's phone number ..."タスクを同時にキューに入れることはできますが、電話番号は異なります。この場合、最後に状態が正しいことを確実にするために更新を適用する必要があります（そして、議論のために、アドレス帳エントリのタスクとタイムスタンプにタイムスタンプを入れて捨てることはできません古いタスク）。

Joeの更新プログラムを適用してJaneの順序が間違っている更新プログラムを適用することは安全です。

私はキューのマルチスレッド処理をしたいと思いますが、私は人によるアクセスを同期させる必要があります。

このような種類の便利なライブラリはありますか？または、私はExecutorを使用し、Runnableのrun（）メソッドの "name"に自分自身の同期をとることに任せましたか？

出典

2013-08-20 Jared

擬似コードを入れて分かりやすくする方がいいでしょう。しかし、それは可能性ですか？：1人のエグゼキュータのように、複数のエグゼキュータを使用することは可能ですか？ 'JoeのアップデートをJoeのためにアップデートすると安全です.' –

実行可能ファイル内の名前を同期させても、順次実行が保証されないことに注意してください。エグゼキュータは、（エグゼキュータがシングルスレッドでない限り）サブミット順にタスクが実行されることを約束しません。 – Aurand

@Jose Renato：名前ごとに1つのスレッドを使用します。以下の答えを参照してください。各スレッドは順序の整合性を保証します。 –

-1

一つの可能性のある解決策

タスクはいくつかのクラスによってタスクグループはあなたの例では到着順（中のプロセスである必要はありタスクを識別するIDである

class Task { 
    Integer taskGroup; 
    // other 
}

に記載されていると仮定それぞれの "名前"は、それ自身のtaskGroupを定義することができます - より一般的には - 同じ名前を持つタスクは、同じtaskGroupに属します）。

mainTaskQueueをTaskオブジェクトのListとします。その後

taskGroupsQueues.get(taskGroup)順で動作するスレッドを作成し、各タスクグループについてtaskGroupsQueues
を言う、Map<Integer,List<Task>>を作成します。
メインスレッドは、単一のキューにメインキューからタスクを移動すると、単一のキューから取り出しmainTaskQueueあなたの主なタスクリストからtaskを削除し、taskGroups.get(task.taskGroup)
に追加し、同期する必要があります。

つまり、同じ名前のタスクは同じスレッドで実行されます。

メインスレッドがタスクの配布を実行する場合、何らかの負荷分散を実行することもできます。つまり、タスクが一貫性のために特定のキューに強制されない場合、そのタスクは短絡待ち行列。 Howerver、あなたの問題では、それがシングルスレッドになるかもしれません。つまり、同じtaskGroup（あなたのケース名で）に頼っているタスクしかないときです。

もう1つの可能な解決策

としてはincrement1sポストとAurandsコメントで指摘（テストしていない、ただの提案は）、トレッド内のタスクグループ（名前）の同期は、いくつかの問題があります。基本的に：executorが同じ名前で同期しようとする2つのスレッドを開始した可能性があるため、遅すぎます。ただし、エグゼキュータレベルでの実行順序を確認することもできます。たとえば、この投稿：Java Executors: how can I set task priority?（Executorに渡されたPriorityBlockingQueueを参照）を参照してください。

出典

2013-08-20 19:56:00

私はあなたの答えを正しく理解するならば、アドレス帳の1000個のエントリには常に1000個のスレッドが実行されており、さらに1000個のキュー（スレッドごとに1個）があることを意味します。少数のユーザーに限定されている場合、これは特定の質問に対しては機能しますが、それ以外の場合はスケーラビリティの問題があるようです。さらに、「キュー」のマップはおそらく実際のブロッキングキューの並行マップであり、リストのマップではありません。 –

これは良い点です。簡単な変更は、固定数のスレッドを使用し、taskGroupからthreadIDへのマッピングを維持することです。しかし、より最適な解決方法は、PriorityBlockingQueueを使用することです。 –

注文要素がキューから取得されるという前提が、実行される順序です。これは無効です。 – Aurand

この問題を解決する簡単な方法は、実行中の処理スレッドの数に等しい配列内のサブキューを維持することです。 1つのマスタースレッドが単一のメインキューから項目を取り出し、オブジェクトキーのhashCode（タスクを識別し関連付けるhashCode）のモジュロを介してインデックスされたサブキューにサブスレッドを追加します。

など。

int queueIndex = myEntity.getKey().hashCode() % queues.length;

1つのスレッドだけがそのキューを処理し、同じエンティティのすべてのタスクがそのキューに送信されるため、競合状態は発生しません。

この解決策は、一部のスレッドが他のスレッドより大きなキューになる可能性があるため、不完全です。実際には、これは問題になることはまずありませんが、考慮する必要があります。簡単な解決策と

問題：（Aurandが指摘したように）単一のキューのオフのアイテムを引っ張った後、影響を受けたエンティティのための明確な何かにロックの

単純ソリューションは、競合状態を持っています。与えられた：

task1と task2の両方が同じエンティティ entity1を編集し、キュー上で動作 thread1と thread2がある

Master Queue [ Task1(entity1), Task2(entity1), ... ]

、その後、イベントの予想/所望の配列は次のとおりです。

スレッド1は、タスク1を取りますentity1上
スレッド1ロック
スレッド1がentity1
のThを編集READ1がentity1
のロックを解除するスレッド2は
スレッド2がentity1
スレッド2はロックが、それは、スレッドのrunメソッドの最初のステートメントである場合でも、entity1

のロックを解除を編集entity1タスク2

スレッド2ロックを取ります

スレッド1がタスク1をとります。
スレッド2が
スレッド2が編集entity1タスク2
スレッド2ロックを取るentity1
スレッド2が
スレッド1が編集entity1 entity1
スレッド1のロックロックを解除entity1
スレッド1は

entity1

はこれを避けるためにロックを解除します、各スレッドはキューからタスクを取得する前に何か（例えばキュー）をロックする必要があります。親ロックを保持したままエンティティのロックを取得します。しかし、この親ロックを保持してエンティティロックを取得するのを待っている間は、すべてをブロックしたくないので、エンティティロックを試してから、取得に失敗した場合（おそらく別のキューに入れる）。全体的に状況は軽微ではありません。

出典

2013-08-21 17:07:05

あなたの答えは私のものと似ているようです。メインスレッド（単一スレッド）がキューからタスクを同時に引き出すワーカースレッドではなく、ワーカースレッド（編集エンティティ）にタスクを配布することで、「タスクとロックを取る」問題を改善できます。 - これは私が私の答えで何を意味したのか、なぜそれが下の票を引き起こしたのかわからない。申し訳ありませんが、それはばかげた考えだった。 –

@ChristianFries私はあなたの答えに投票していませんでした。「タスクを取ってからロックする」という私のコメントは、キューからオブジェクトを取り出した後に 'name'をロックするというオリジナルのポスター（質問者の質問）に関するものです。そうするとAurandによって指摘された微妙な競争条件があり、私の答えで詳述されています。 –

申し訳ありませんが、オリジナルの質問が、実行可能ファイル内のエンティティで同期するという考えを明示的に持ち上げたことに気付かなかったのです。今、私はあなたがなぜ（不必要に欠陥のある）解決策をもたらしたのかを見ています。（残念ながら、あなたの投稿が編集されない限り、私は投票を元に戻すことができませんが、句読記号だけを変更してもそうします）。 W.r.t.その同期には、私の解決策では、メインスレッドにタスクを分散することで回避します（それぞれのキューで同期化）。したがって、各ワーカースレッドは必要なものだけを見て、メインスレッドは順序の一貫性を保証します。 –

このような競合は、各オブジェクトにバージョンを割り当てることによって常に解決されます。すべての更新版で増分されます。したがって、1つのアップデートが間違った時間に到着した場合、それは却下されたり遅延されたりする可能性があります。どのような方法でも、どの更新が最初で、どちらが更新であるかを判断する方法が必要です。この方法はoptimistic lockingと呼ばれています。

出典

2013-08-25 11:17:10 Mikhail

いくつかのトランザクションの順序が重要な場合、どのようにキュー消費者をマルチスレッド化できますか？

答えて

関連する問題