Реализация синхронной очереди Ява


Я просто хочу убедиться, что нет никаких тупиков или несоответствия (код также доступен на GitHub).

Отказ от ответственности - в реальной жизни, я бы не реализовать очередь себя, но использовать существующую реализацию. Это просто подготовка к собеседованию.

package org.basic.concurrent;

import java.util.ArrayList;
import java.util.List;

public class SynchedQueue<T> {
    private final Object lock = new Object();
    private final Object full = new Object();
    private final Object free = new Object();

    private final List<T> buffer;
    private int head;
    private int tail;
    private int size;
    private final int capacity;

    public SynchedQueue(int capacity) {
        // http://stackoverflow.com/questions/4912088/how-to-create-a-fixed-size-generic-buffer-in-java
        buffer = new ArrayList<T>(capacity);
        for (int i = 0; i < capacity; ++i)
            buffer.add(null);
        this.capacity = capacity;
    }

    public void enqueue(T x) {
        if (x == null)
            throw new RuntimeException("Doesn't allow storing nulls");

        synchronized (lock) {
            while (!tryEnqueue(x)) {
                try {
                    free.wait();
                } catch (InterruptedException ignored) {
                }
            }
            full.notify();
        }
    }

    public T dequeue() {
        synchronized (lock) {
            while (true) {
                T item = tryDequeue();
                if (item != null)
                {
                    free.notify();
                    return item;
                }
                try {
                    full.wait();
                }
                catch (InterruptedException ignored) {}
            }
        }
    }

    private boolean tryEnqueue(T x) {
        assert size <= capacity;
        if (size >= capacity) {
            return false;
        }

        buffer.set(tail, x);
        tail = (tail + 1) % capacity;
        ++size;
        return true;
    }

    private T tryDequeue() {
        assert size >= 0;
        if (size == 0)
            return null;
        T item = buffer.get(head);
        head = (head + 1) % capacity;
        --size;
        return item;
    }
}


3002
8
задан 6 февраля 2011 в 07:02 Источник Поделиться
Комментарии
3 ответа

Я не закодированный в Java в течение нескольких лет, поэтому было бы неплохо узнать мнение другого человека, хотя некоторые моменты выделяются при чтении кода.


  • Мне кажется, что вы бы использовать ArrayList с с фиксированным размером, лично я бы просто использовать массив для буфера.

  • когда вы удалить, не перезаписать значение, пока вы не помещать поверх него. Это может показаться не проблема (и если вы только очереди просто типы вроде int и, его нет), но если вы используете ссылочные типы и очереди циклов медленно, то это означает, что вы держите ссылку на объект дольше, чем нужно, и он не может быть собрана.

  • Я немного волновался по поводу ловли выдачей InterruptedException в то время как(правда) петли без разрыва цикла. Самая распространенная причина, я видел, как для одного потока, чтобы прервать другой, когда прерывая нить хочет дать прерванную нить возможность с благодарностью завершить, но это позволит избежать такого варианта. Я думал о том, что может быть возвращено в таком случае и в конце концов решил, что может быть лучше, чтобы этот поток исключение и обрабатывается абонента.

4
ответ дан 6 февраля 2011 в 08:02 Источник Поделиться

Вы пробовали под управлением этой реализации? Он не сразу с Явы.яз.IllegalMonitorStateException , которые в соответствии с документацией составляет:


Брошенный, чтобы указать, что поток попытался ожидать на мониторе объекта или уведомить других потоков, ожидающих на мониторе объекта, не имея указанный монитор.

Проблема в том, что реализация синхронизирует на поле замка , но призывает оповестить() и ждать() на полный и бесплатный , не держа их замки. Когда вы это исправить, это важно иметь в виду, что вызов wait() автоматически освобождает блокировку объекта вы ждете, но не освобождает замки на другие объекты. Если вы не принимаете это во внимание, его довольно легко создать тупики.

Для удобства чтения, я рекомендую использовать Java-приложений.утиль.одновременно.замки.Состояние вместо того, чтобы ждать() и сообщить() , которые являются достаточно низком уровне и сложно рассуждать об этом. В самом деле, пример использования в Javadoc для Условия реализации ограниченного буфера.

У меня тоже есть эхо Брайана беспокойство: важно, что вы не молча глотать выдачей InterruptedException. У вас есть два варианта о том, как обрабатывать прерывания. Если вы хотите обработать исключение самостоятельно, то JCIP говорит, что вы должны установить прерванное состояние обратно.

catch (InterruptedException e)
{
Thread.interrupt();
// Handle the interruption
}

Другой выбор, который лучше, на мой взгляд, это просто распространить исключение. На Java построен в библиотеках использовать эту стратегию, для примера см. интерфейса blockingqueue.взять().

2
ответ дан 6 февраля 2011 в 06:02 Источник Поделиться


  1. Похоже, интерфейса blockingqueue не просто SynchQueue

  2. бросить новый к RuntimeException("не допускать хранение значений null"); - есть IllegalArgumnetException для этого.

  3. Было бы лучше добавить выдает InterruptedException в объявлении метода, а не заглатывать его.

  4. Вы собираетесь добавить/удалить из хвоста/головы из внутреннего буфера - класса LinkedList выглядит лучше варианты для внутреннего хранения. Вам не нужны тонны массива.Копия в этом случае. Она будет также удалить эти tryDequeue() и tryEnqueue() и существенно упростить код.

  5. Этот код не работает в одном случае резьба. Рассмотрим ситуацию, когда я называю метод enqueue() впервые на очереди, потом полный.оповестить() будет не сразу.

1
ответ дан 6 февраля 2011 в 08:02 Источник Поделиться