Implementowanie kolejki blokowania w JavaME: jak ją zoptymalizować?

Question

Próbuję zaimplementować prostą blokującą kolejkę w Java ME. W JavaME API narzędzia współbieżności Java SE są niedostępne, więc muszę używać wait-notify jak w dawnych czasach.

To jest moja wstępna realizacja. Używam notify zamiast notifyAll, ponieważ w moim projekcie jest wielu producentów, ale tylko jeden konsument. Kiedyś obiekt do wyczekiwania zawiadomić celowo w celu poprawienia czytelności, mimo to traci odniesienie:

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; 
     } 
    } 

Moje główne pytanie dotyczy sposobu put. Czy mogę wstawić linię queue.addElement z bloku synchronized? Czy poprawi się wydajność, jeśli tak?

To samo dotyczy take: czy mogę wykonać dwie operacje na queue z synchronized block?

Każda inna możliwa optymalizacja?

EDYCJA:
Jak słusznie zauważył @Raam, wątek konsumencki może głodować z głodu w trakcie budzenia w wait. Więc jakie są alternatywy, aby temu zapobiec? (Uwaga: W JavaME nie mam wszystkich tych ładnych klas z Java SE.) Pomyśl o tym jako o starej Javie v1.2)

Answer 1

Klasa Vector nie gwarantuje bezpieczeństwa wątku i należy zsynchronizować dostęp do tak, jak zrobiłeś. Jeśli nie masz dowodów na to, że twoje obecne rozwiązanie ma problemy z wydajnością, nie martwię się o to.

Na marginesie, nie widzę żadnej szkody przy używaniu notifyAll, a nie notify do obsługi wielu klientów.

Answer 2

synchronized służy do ochrony dostępu do stanu współdzielonego i zapewnienia atomowości.

Należy pamiętać, że metody Vector są już zsynchronizowane, dlatego Vector chroni własny własny stan udostępniony. Zatem bloki synchronizacji są potrzebne tylko do zapewnienia atomowości twoich operacji.

Z pewnością nie można przenieść operacji na queue ze zsynchronizowanego bloku w metodzie take(), ponieważ atomowość ma kluczowe znaczenie dla poprawności tej metody. Ale, o ile rozumiem, możesz przenieść operację kolejkowania z bloku zsynchronizowanego w metodzie put() (nie wyobrażam sobie sytuacji, kiedy może się nie udać).

Jednak rozumowanie powyższe jest czysto teoretyczna, ponieważ we wszystkich przypadkach trzeba podwójnej synchronizacji: Synchronizuj swoje na queueLock i metody Vector niejawnie zsynchronizować na queue. Dlatego proponowana optymalizacja nie ma sensu, jej poprawność zależy od obecności tej podwójnej synchronizacji.

Aby uniknąć podwójnej synchronizacji trzeba zsynchronizować na queue także:

synchronized (queue) { ... } 

Innym rozwiązaniem byłoby wykorzystanie niezsynchronizowanych kolekcji (takich jak ArrayList) zamiast Vector, ale JavaME nie obsługuje .W takim przypadku nie będzie można również skorzystać z proponowanej optymalizacji, ponieważ zsynchronizowane bloki chronią również stan współdzielenia niezsynchronizowanej kolekcji.

Answer 3

Wygląda na to, że z tym podejściem wiążą się pewne problemy. Możesz mieć scenariusze, w których konsument może nie otrzymywać powiadomień i czekać na kolejkę, nawet jeśli w kolejce znajdują się elementy. Rozważ następującą sekwencję w porządku chronologicznym.

T1 - Konsument przejmuje funkcję Queue Lock, a następnie wywołuje funkcję wait. Czekać będzie zwolnić blokadę i spowodować wątku czekać na zgłoszenia

T2 - Jeden producent nabywa queueLock i dodaje element do kolejki i zwraca zawiadomić

T3 - Gwint Konsument jest informowany i próbuje zdobyć queueLock ALE kończy się niepowodzeniem, ponieważ inny producent przychodzi w tym samym czasie. (od powiadomienia java doc - Przebudzony wątek będzie konkurował w zwykły sposób z innymi wątkami, które mogą aktywnie konkurować o synchronizację na tym obiekcie, na przykład przebudzony wątek nie ma żadnych wiarygodnych przywilejów lub wad w byciu kolejnym wątkiem do zablokowania ten obiekt.)

T4 - Drugi producent dodaje teraz kolejny element i wywołuje powiadomienia. Powiadomienie to zostaje utracone, gdy klient czeka na funkcję Queue Lock.

Tak więc teoretycznie możliwe jest, aby konsument mógł głodować (na zawsze utknąć próbując uzyskać funkcję queueLock), można również uruchomić problem z pamięcią, gdy wielu producentów dodaje elementy do kolejki, które nie są odczytywane i usuwane z kolejki.

Niektóre zmiany, które chciałbym zaproponować jest następująca -

• Trzymaj górną granicę liczby elementów, które można dodać do kolejki.
• Upewnij się, że konsument zawsze czyta wszystkie elementy. Here to program, który pokazuje, w jaki sposób można zakodować producent - problem konsumenta.

Answer 4

Chyba, że ​​masz problemy z wydajnością w szczególności ze względu na zbieranie śmieci, wolałbym użyć połączonej listy niż Vector zaimplementować kolejkę (first in, first out).

Chciałbym również napisać kod, który byłby ponownie użyty, gdy twój projekt (lub inny) otrzyma wielu klientów. Chociaż w tym przypadku musisz mieć świadomość, że specyfikacje języka Java nie narzucają sposobu na implementację monitorów. W praktyce oznacza to, że nie kontrolujesz, który wątek konsumencki zostanie powiadomiony (połowa istniejących monitorów maszyn wirtualnej maszyny wirtualnej używa modelu FIFO i innych pół-narzędziowych monitorów używających modelu LIFO).

Ja też uważam, że ktokolwiek używa klasy blokującej ma również poradzić sobie z wyjątkiem InterruptedException. W końcu kod klienta musiałby zajmować się zerowym zwracaniem obiektów w przeciwnym razie.

Tak, coś takiego:

/*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; 
    } 

} 

myślę, że jeśli starają się umieścić mniej kod w zsynchronizowanych bloki, klasy nie będą już poprawne.