Реализация очереди блокировки в JavaME: как ее оптимизировать?
Я пытаюсь реализовать простую очередь блокировки в Java ME. В JavaME API утилиты параллелизма Java SE недоступны, поэтому я должен использовать ожидание-уведомление, как в старые времена.
Это моя предварительная реализация. я использую notify вместо notifyAll потому что в моем проекте есть несколько производителей, но только один потребитель. Я специально использовал объект wait-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 линия из synchronized блок? Будет ли производительность улучшаться, если так?
Также то же самое относится к take: Могу ли я взять две операции на queue вне synchronized block?
Любая другая возможная оптимизация?
РЕДАКТИРОВАТЬ:
Как правильно заметил @Raam, потребительский поток может голодать при пробуждении в wait, Так, каковы альтернативы, чтобы предотвратить это? (Примечание: в JavaME у меня нет всех этих хороших классов из Java SE. Думайте об этом как о старой Java v1.2)
4 ответа
synchronized используется для защиты доступа к общему состоянию и обеспечения атомарности.
Обратите внимание, что методы Vector уже синхронизированы, поэтому Vector защищает свое собственное общее государство. Таким образом, ваши блоки синхронизации нужны только для обеспечения атомарности ваших операций.
Вы, конечно, не можете перенести операции на queue из синхронизированного блока в вашем take() метод, потому что атомарность имеет решающее значение для правильности этого метода. Но, насколько я понимаю, вы можете перенести операцию очереди из синхронизированного блока в put() метод (я не могу представить ситуацию, когда это может пойти не так).
Однако приведенные выше соображения являются чисто теоретическими, потому что во всех случаях у вас есть двойная синхронизация: ваша синхронизация включена queueLock и методы Vector неявно синхронизировать по queue, Поэтому предложенная оптимизация не имеет смысла, ее правильность зависит от наличия этой двойной синхронизации.
Чтобы избежать двойной синхронизации, необходимо синхронизировать queue также:
synchronized (queue) { ... }
Другой вариант будет использовать несинхронизированный сбор (например, ArrayList) вместо Vector, но JavaME не поддерживает это. В этом случае вы также не сможете использовать предложенную оптимизацию, потому что синхронизированные блоки также защищают общее состояние несинхронизированной коллекции.
Класс Vector не гарантирует, что потокобезопасен, и вам следует синхронизировать доступ к нему, как вы это сделали. Если у вас нет доказательств того, что в вашем текущем решении есть проблемы с производительностью, я бы об этом не беспокоился.
С другой стороны, я не вижу вреда в использовании notifyAll скорее, чем notify для поддержки нескольких потребителей.
Если у вас нет проблем с производительностью, в частности, из-за сборки мусора, я бы предпочел использовать связанный список, а не Vector, для реализации очереди (сначала во-первых, то, во-первых).
Я также написал бы код, который будет использоваться повторно, когда ваш проект (или другой) получит несколько потребителей. Хотя в этом случае вы должны знать, что спецификации языка Java не навязывают способ реализации мониторов. На практике это означает, что вы не контролируете, какой потребительский поток получает уведомление (половина существующих виртуальных машин Java реализует мониторы с использованием модели FIFO, а другая половина реализует мониторы с использованием модели LIFO).
Я также думаю, что тот, кто использует блокирующий класс, также должен иметь дело с InterruptedException. В конце концов, клиентский код должен был бы иметь дело с нулевым возвратом объекта в противном случае.
Итак, как то так:
/*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;
}
}
Я думаю, что если вы попытаетесь поместить меньше кода в синхронизированные блоки, класс больше не будет корректным.
Кажется, есть некоторые проблемы с этим подходом. У вас могут быть сценарии, в которых потребитель может пропустить уведомления и ждать в очереди, даже если в очереди есть элементы. Рассмотрим следующую последовательность в хронологическом порядке
T1 - Потребитель получает queueLock и затем вызывает wait. Ожидание снимет блокировку и заставит поток ждать уведомления
T2 - один производитель получает queueLock и добавляет элемент в очередь и вызывает notify
T3 - Поток потребителя уведомляется, и попытка получить queueLock, НО, терпит неудачу, поскольку другой производитель приходит в то же самое время. (из документа notify java - пробужденный поток будет конкурировать обычным образом с любыми другими потоками, которые могут активно конкурировать за синхронизацию на этом объекте; например, пробужденный поток не имеет надежных привилегий или недостатков в том, чтобы быть следующим потоком для блокировки этот объект.)
T4 - Второй производитель теперь добавляет еще один элемент и вызывает notify. Это уведомление потеряно, поскольку потребитель ожидает очереди queueLock.
Таким образом, теоретически возможно, что потребитель голодает (навсегда застряв при попытке получить queueLock), также вы можете столкнуться с проблемой памяти, когда несколько производителей добавляют элементы в очередь, которые не читаются и не удаляются из очереди.
Некоторые изменения, которые я бы предложил, заключаются в следующем -
- Держите верхнюю границу для количества элементов, которые можно добавить в очередь.
- Убедитесь, что потребитель всегда читает все элементы. Вот программа, которая показывает, как проблема производителя - потребителя может быть закодирована.