Автор оригинала: Priyank Srivastava.
1. Обзор
В этом уроке мы узнаем, как реализовать кольцевой буфер в Java.
2. Кольцевой Буфер
Кольцевой буфер (или круговой буфер) – это ограниченная круговая структура данных, которая используется для буферизации данных между двумя или более потоками . Когда мы продолжаем запись в кольцевой буфер, он оборачивается, когда достигает конца.
2.1. Как Это Работает
Кольцевой буфер реализован с использованием массива фиксированного размера, который обтекает границы .
Помимо массива, он отслеживает три вещи:
- следующий доступный слот в буфере для вставки элемента,
- следующий непрочитанный элемент в буфере,
- и конец массива – точка, в которой буфер оборачивается к началу массива
Механика того, как кольцевой буфер обрабатывает эти требования, зависит от реализации. Например, в записи Wikipedia по этому вопросу показан метод, использующий четыре указателя.
Мы позаимствуем этот подход из реализации Disruptor кольцевого буфера с использованием последовательностей.
Первое, что нам нужно знать, – это емкость-фиксированный максимальный размер буфера. Далее, мы будем использовать две монотонно возрастающие | последовательности :
- Последовательность записи: начиная с -1, увеличивается на 1, когда мы вставляем элемент
- Последовательность чтения: начиная с 0, увеличивается на 1 по мере потребления элемента
Мы можем сопоставить последовательность с индексом в массиве с помощью операции mod:
arrayIndex = sequence % capacity
Операция mod обертывает последовательность вокруг границ, чтобы получить слот в буфере :
Давайте посмотрим, как мы вставим элемент:
buffer[++writeSequence % capacity] = element
Мы предварительно увеличиваем последовательность перед вставкой элемента.
Чтобы потреблять элемент, мы делаем постинкремент:
element = buffer[readSequence++ % capacity]
В этом случае мы выполняем последующее приращение последовательности. Потребление элемента не удаляет его из буфера – он просто остается в массиве до тех пор, пока не будет перезаписан .
2.2. Пустые и Полные буферы
Когда мы обернем массив, мы начнем перезаписывать данные в буфере. Если буфер заполнен, мы можем либо перезаписать самые старые данные независимо от того, потребил ли их читатель, либо предотвратить перезапись данных, которые не были прочитаны .
Если читатель может позволить себе пропустить промежуточные или старые значения (например, тикер цены акций), мы можем перезаписать данные, не дожидаясь их использования. С другой стороны, если читатель должен потреблять все значения (как в случае с транзакциями электронной коммерции), мы должны ждать (блокировать/занят-ждать), пока в буфере не появится свободный слот.
Буфер заполнен , если размер буфера равен его емкости , где его размер равен количеству непрочитанных элементов:
size = (writeSequence - readSequence) + 1 isFull = (size == capacity)
Если последовательность записи отстает от последовательности чтения, буфер пуст :
isEmpty = writeSequence < readSequence
Буфер возвращает значение null , если он пуст.
2.2. Преимущества и недостатки
Кольцевой буфер-это эффективный буфер FIFO. Он использует массив фиксированного размера, который может быть предварительно выделен заранее и обеспечивает эффективный шаблон доступа к памяти. Все буферные операции являются постоянными по времени O(1) , включая потребление элемента, так как для этого не требуется смещение элементов.
С другой стороны, определение правильного размера кольцевого буфера имеет решающее значение. Например, операции записи могут блокироваться в течение длительного времени, если размер буфера невелик, а чтение происходит медленно. Мы можем использовать динамический размер, но для этого потребуется перемещение данных, и мы упустим большинство преимуществ, описанных выше.
3. Реализация на Java
Теперь, когда мы поняли, как работает кольцевой буфер, давайте перейдем к его реализации в Java.
3.1. Инициализация
Во-первых, давайте определим конструктор, который инициализирует буфер с предопределенной емкостью:
public CircularBuffer(int capacity) {
this.capacity = (capacity < 1) ? DEFAULT_CAPACITY : capacity;
this.data = (E[]) new Object[this.capacity];
this.readSequence = 0;
this.writeSequence = -1;
}
Это создаст пустой буфер и инициализирует поля последовательности, как описано в предыдущем разделе.
3.2. Предложение
Далее мы реализуем операцию offer , которая вставляет элемент в буфер в следующем доступном слоте и возвращает true при успешном выполнении. Он возвращает false , если буфер не может найти пустой слот, то есть мы не можем перезаписать непрочитанные значения .
Давайте реализуем метод offer в Java:
public boolean offer(E element) {
boolean isFull = (writeSequence - readSequence) + 1 == capacity;
if (!isFull) {
int nextWriteSeq = writeSequence + 1;
data[nextWriteSeq % capacity] = element;
writeSequence++;
return true;
}
return false;
}
Итак, мы увеличиваем последовательность записи и вычисляем индекс в массиве для следующего доступного слота. Когда мы записываем данные в буфер и сохраняем обновленную последовательность записи.
Давайте попробуем:
@Test
public void givenCircularBuffer_whenAnElementIsEnqueued_thenSizeIsOne() {
CircularBuffer buffer = new CircularBuffer<>(defaultCapacity);
assertTrue(buffer.offer("Square"));
assertEquals(1, buffer.size());
}
3.3. Опрос
Наконец, мы реализуем операцию poll , которая извлекает и удаляет следующий непрочитанный элемент. Операция poll не удаляет элемент, а увеличивает последовательность чтения .
Давайте его реализуем:
public E poll() {
boolean isEmpty = writeSequence < readSequence;
if (!isEmpty) {
E nextValue = data[readSequence % capacity];
readSequence++;
return nextValue;
}
return null;
}
Здесь мы считываем данные в текущей последовательности чтения, вычисляя индекс в массиве. Затем мы увеличиваем последовательность и возвращаем значение, если буфер не пуст.
Давайте проверим это:
@Test
public void givenCircularBuffer_whenAnElementIsDequeued_thenElementMatchesEnqueuedElement() {
CircularBuffer buffer = new CircularBuffer<>(defaultCapacity);
buffer.offer("Triangle");
String shape = buffer.poll();
assertEquals("Triangle", shape);
}
4. Проблема Производитель-Потребитель
Мы говорили об использовании кольцевого буфера для обмена данными между двумя или более потоками, что является примером проблемы синхронизации, называемой проблемой Производитель-Потребитель . В Java мы можем решить проблему производителя-потребителя различными способами, используя семафоры , ограниченные очереди , кольцевые буферы и т. Д.
Давайте реализуем решение, основанное на кольцевом буфере.
4.1. изменчивые поля Последовательности
Наша реализация кольцевого буфера не является потокобезопасной. Давайте сделаем его потокобезопасным для простого случая с одним производителем и одним потребителем.
Производитель записывает данные в буфер и увеличивает последовательность записи , в то время как потребитель только читает из буфера и увеличивает последовательность чтения . Таким образом, резервный массив свободен от конфликтов, и мы можем уйти без какой-либо синхронизации.
Но нам все равно нужно убедиться, что потребитель может видеть последнее значение поля последовательность записи ( видимость ) и что Последовательность записи не обновляется до того, как данные будут фактически доступны в буфере ( упорядочение ).
В этом случае мы можем сделать кольцевой буфер параллельным и свободным от блокировки, сделав поля последовательности изменчивыми :
private volatile int writeSequence = -1, readSequence = 0;
В методе offer запись в volatile поле последовательность записи гарантирует, что запись в буфер произойдет до обновления последовательности. В то же время гарантия видимости volatile гарантирует, что потребитель всегда будет видеть последнее значение writeSequence .
4.2. Производитель
Давайте реализуем простой производитель Runnable , который записывает данные в кольцевой буфер:
public void run() {
for (int i = 0; i < items.length;) {
if (buffer.offer(items[i])) {
System.out.println("Produced: " + items[i]);
i++;
}
}
}
Поток-производитель будет ждать пустого слота в цикле (занято-ожидание).
4.3. Потребитель
Мы реализуем потребитель Вызываемый , который считывает данные из буфера:
public T[] call() {
T[] items = (T[]) new Object[expectedCount];
for (int i = 0; i < items.length;) {
T item = buffer.poll();
if (item != null) {
items[i++] = item;
System.out.println("Consumed: " + item);
}
}
return items;
}
Поток-потребитель продолжает работу без печати, если он получает значение null из буфера.
Давайте напишем наш код драйвера:
executorService.submit(new Thread(new Producer(buffer))); executorService.submit(new Thread(new Consumer (buffer)));
Выполнение нашей программы “производитель-потребитель” дает результат, как показано ниже:
Produced: Circle Produced: Triangle Consumed: Circle Produced: Rectangle Consumed: Triangle Consumed: Rectangle Produced: Square Produced: Rhombus Consumed: Square Produced: Trapezoid Consumed: Rhombus Consumed: Trapezoid Produced: Pentagon Produced: Pentagram Produced: Hexagon Consumed: Pentagon Consumed: Pentagram Produced: Hexagram Consumed: Hexagon Consumed: Hexagram
5. Заключение
В этом уроке мы узнали, как реализовать кольцевой буфер, и изучили, как его можно использовать для решения проблемы “производитель-потребитель”.
Как обычно, исходный код для всех примеров доступен на GitHub .