JavaMEでブロッキングキューを実装する方法：最適化する方法

Question

私はJava MEで単純なブロックキューを実装しようとしています。 JavaME APIでは、Java SEの並行性ユーティリティは利用できないため、以前のような待ち通知を使用する必要があります。

これは私の暫定的な実装です。私はnotifyAllの代わりにnotifyを使用しています。私のプロジェクトでは複数のプロデューサが存在し、単一のコンシューマしかないからです。

import java.util.Vector; 

    public class BlockingQueue {  
     private Vector queue = new Vector(); 
     private Object queueLock = new Object();  

     public void put(Object o){ 
      synchronized(queueLock){ 
       queue.addElement(o); 
       queueLock.notify(); 
      }  
     } 

     public Object take(){ 
      Object ret = null; 
      synchronized (queueLock) { 
       while (queue.isEmpty()){ 
        try { 
         queueLock.wait(); 
        } catch (InterruptedException e) {} 
       } 

       ret = queue.elementAt(0); 
       queue.removeElementAt(0); 
      } 
      return ret; 
     } 
    } 

私の主な質問はput方法についてです：それはリファレンスを無駄にもかかわらず、私は、読みやすさを向上させるために意図的に待機通知のためのオブジェクトを使用していました。 queue.addElement行を​​ブロックから除外できますか？もしそうならパフォーマンスは向上するでしょうか？

また、takeについても同様です。synchronized blockのうちqueueで2つの操作を実行できますか？

その他の最適化は可能ですか？

EDIT：
@Raamが正しく指摘したように、消費者スレッドは、waitで起床したときに餓死する可能性があります。では、これを防ぐための代替手段は何ですか？ （注：JavaMEでは、Java SEのこれらの優れたクラスはありません。古いJava v1.2と考えてください）

Answer 1

Vectorクラスはスレッドセーフであることを保証していません。それは、あなたがしたように。現在のソリューションにパフォーマンスの問題があるという証拠がない限り、私はそれについて心配しません。

補足として、notifyではなく、notifyAllを使用して複数のコンシューマをサポートしても問題ありません。

Answer 2

​​は、共有状態へのアクセスを保護し、アトミック性を保証するために使用されます。

Vectorのメソッドは既に同期されていることに注意してください。したがって、Vectorはそれ自身の共有状態自体を保護します。したがって、同期ブロックは操作のアトミック性を確保するためにのみ必要です。

の操作をtake()メソッドのsynchronizedブロックから移動することはできません。これは、アトミック性がそのメソッドの正確さのために重要であるためです。しかし、私が理解するところでは、put()メソッドの同期ブロックからキュー操作を移動できます（間違っている状況を想像することはできません）。 の同期とVectorの同期は、queueで暗黙的に同期するため、上記の理由は完全に理論的なものです。 したがって、提案された最適化は意味を持たない、その正確さはその二重同期の存在に依存します。

あなたにもqueueに同期させる必要があり、二重の同期を避けるために：

は

synchronized (queue) { ... } 

別のオプションは、非同期コレクションを使用することです（例えばArrayListなど）の代わりに、Vectorが、JavaMEのは、それをサポートしていません。 。この場合、同期化されたブロックは同期化されていないコレクションの共有状態も保護するため、提案された最適化を使用することはできません。

Answer 3

このアプローチではいくつかの問題があるようです。消費者が通知を見逃し、キューに要素がある場合でもキューを待機できるシナリオがあります。 年代順に

T1を次のシーケンスを考えてみましょう - 消費者はqueueLockを取得し、呼び出しは待機します。通知を待つスレッドをロックを解除し、原因となります待って

T2 - ワンプロデューサーはqueueLockを取得し、キューに要素を追加し、通話が

はT3通知 - 消費者のスレッドが通知され、取得しようとしますqueueLock他のプロデューサが同時に来ると失敗します。 （通知されたjava docから - 起動されたスレッドは、このオブジェクトで同期するために積極的に競合する可能性のある他のスレッドと通常の方法で競合します（例えば、起動されたスレッドは信頼できる特権を得ず、このオブジェクト。

T4 - 2番目のプロデューサが別の要素を追加し、通知を呼び出します。この通知は、コンシューマがqueueLockで待機している間は失われます。

理論的には、消費者が飢えている（永遠にqueueLockを取得しようとしている）可能性もあります。複数のプロデューサがキューに読み書きされていない要素をキューに追加してメモリ問題に遭遇することがあります。次のように

私は示唆しているいくつかの変更がある -

• キューに追加できるアイテムの数に上限を保管してください。
• コンシューマーが常にすべての要素を読み取るようにしてください。 Hereは、プロデューサ - コンシューマの問題をどのようにコード化できるかを示すプログラムです。

Answer 4

特にガベージコレクションのためにパフォーマンスの問題が発生しない限り、私はむしろベクトルよりもリンクリストを使用してキューを実装します（先入れ先出し）。

プロジェクト（または別のもの）が複数のコンシューマを取得したときに再利用されるコードも記述します。その場合、Java言語仕様はモニターを実装する方法を課していないことに注意する必要があります。実際には、どの消費者スレッドが通知を受けるかを制御しないことを意味します（既存のJava Virtual Machineの半分はFIFOモデルを使用してモニタを実装し、残りの半分はLIFOモデルを使用してモニタを実装します）

また、ブロッキングクラスを使用している場合は、InterruptedExceptionも処理することになっています。結局のところ、クライアントコードは、null Objectを処理しなければなりません。

ので、このような何か：

/*package*/ class LinkedObject { 

    private Object iCurrentObject = null; 
    private LinkedObject iNextLinkedObject = null; 

    LinkedObject(Object aNewObject, LinkedObject aNextLinkedObject) { 
     iCurrentObject = aNewObject; 
     iNextLinkedObject = aNextLinkedObject; 
    } 

    Object getCurrentObject() { 
     return iCurrentObject; 
    } 

    LinkedObject getNextLinkedObject() { 
     return iNextLinkedObject; 
    } 
} 

public class BlockingQueue { 
    private LinkedObject iLinkedListContainer = null; 
    private Object iQueueLock = new Object(); 
    private int iBlockedThreadCount = 0; 

    public void appendObject(Object aNewObject) { 
     synchronized(iQueueLock) { 
      iLinkedListContainer = new iLinkedListContainer(aNewObject, iLinkedListContainer); 
      if(iBlockedThreadCount > 0) { 
       iQueueLock.notify();//one at a time because we only appended one object 
      } 
     } //synchonized(iQueueLock) 
    } 

    public Object getFirstObject() throws InterruptedException { 
     Object result = null; 
     synchronized(iQueueLock) { 
      if(null == iLinkedListContainer) { 
       ++iBlockedThreadCount; 
       try { 
        iQueueLock.wait(); 
        --iBlockedThreadCount; // instead of having a "finally" statement 
       } catch (InterruptedException iex) { 
        --iBlockedThreadCount; 
        throw iex; 
       } 
      } 
      result = iLinkedListcontainer.getCurrentObject(); 
      iLinkedListContainer = iLinkedListContainer.getNextLinkedObject(); 
      if((iBlockedThreadCount > 0) && (null != iLinkedListContainer)) { 
       iQueueLock.notify(); 
      } 
     }//synchronized(iQueueLock) 
     return result; 
    } 

} 

私はあなたがsynchronizedブロックに以下のコードを入れしようとした場合、クラスはもはや正確ではないだろうと思います。