A ring buffer, also known as a circular buffer or cyclic buffer, that stores elements in a fixed-size, circular arrangement. Following image depicts a ring buffer of capacity to store 11 elements.
Key characteristics of ring buffer
1. Fixed Size
Ring buffer is fixed in size. Once the buffer is full, either you can replace the old elements or you can wait until the elements in buffer are consumed.
2. Circular in nature
Buffer is organized in a circular ring like fashion.
3. FIFO behaviour
Elements are consumed in First-In, First-Out order. Elements which are added first are consumed first.
4. Efficient for sequential access applications
RingBuffers are used to sequential access applications. In video streaming applications, where data is continuously arriving and being processed, a ring buffer can be more efficient than other data structures.
5. Efficient space usage
Unlike conventional arrays or buffers that can experience wasted space as elements are added or removed, ring buffers seamlessly employ their fixed-size storage without any gaps.
6. Easy to implement
Simple to implement.
When is the ring-buffer empty?
A ring buffer is considered empty when the read_pointer is equal to the write_pointer. This can be expressed mathematically as:
read_pointer == write_pointer
When the producer add elements to the buffer, the write_pointer will move ahead. After adding four elements a, b, c and d, ring buffer looks like below.
Assume consumer processed 2 elements from the buffer, then the ring buffer looks like below.
When is the buffer full?
A ring buffer is considered full when the write_pointer is one position behind the read_pointer. This can be expressed mathematically as:
(write_pointer + 1) % buffer_size == read_pointer
Find the below working application.
RingBuffer.java
package com.sample.app.collections;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class RingBuffer<T> {
private int bufferSize;
private Object[] buffer;
private int writePointer = 0;
private int readPointer = 0;
private final Lock LOCK = new ReentrantLock();
public RingBuffer(int capacity) {
this.bufferSize = capacity;
this.buffer = new Object[capacity];
}
public boolean publish(T item) {
LOCK.lock();
try {
// Check if the buffer is full
if ((writePointer + 1) % bufferSize == readPointer) {
return false;
}
// Add item to the buffer
buffer[writePointer] = item;
writePointer = (writePointer + 1) % bufferSize;
System.out.println("Published: " + item);
return true;
} finally {
LOCK.unlock();
}
}
public T consume() {
LOCK.lock();
try {
// Check if the buffer is empty
if (readPointer == writePointer) {
return null;
}
// Retrieve item from the buffer
T item = (T) buffer[readPointer];
readPointer = (readPointer + 1) % bufferSize;
return item;
} finally {
LOCK.unlock();
}
}
}
Producer.java
package com.sample.app.tasks;
import com.sample.app.collections.RingBuffer;
import com.sample.app.util.TimerUtil;
public class Producer implements Runnable {
private RingBuffer<String> buffer;
public Producer(RingBuffer<String> buffer) {
this.buffer = buffer;
}
@Override
public void run() {
for (int i = 0; i < 10; i++) {
boolean ispublished = buffer.publish("Event " + i);
if(!ispublished) {
System.out.println("Buffer is full. Producer waiting...");
TimerUtil.sleepNMilliseconds(100);
i--;
continue;
}
}
}
}
Consumer.java
package com.sample.app.tasks;
import com.sample.app.collections.*;
import com.sample.app.util.TimerUtil;
public class Consumer implements Runnable {
private RingBuffer<String> buffer;
public Consumer(RingBuffer<String> buffer) {
this.buffer = buffer;
}
@Override
public void run() {
for (int i = 0; i < 10; i++) {
String itemRead = buffer.consume();
if (itemRead == null) {
TimerUtil.sleepNMilliseconds(100);
i--;
System.out.println("Buffer is empty. Consumer waiting...");
continue;
}
System.out.println("Consumed: " + itemRead);
}
}
}
App.java
package com.sample.app;
import com.sample.app.collections.RingBuffer;
import com.sample.app.tasks.Consumer;
import com.sample.app.tasks.Producer;
public class App {
public static void main(String[] args) {
RingBuffer<String> buffer = new RingBuffer<>(5);
// Create and start producer and consumer threads
Thread producerThread = new Thread(new Producer(buffer));
Thread consumerThread = new Thread(new Consumer(buffer));
producerThread.start();
consumerThread.start();
try {
producerThread.join();
consumerThread.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
Sample Output
Published: Event 0 Published: Event 1 Published: Event 2 Published: Event 3 Buffer is full. Producer waiting... Consumed: Event 0 Consumed: Event 1 Consumed: Event 2 Consumed: Event 3 Buffer is empty. Consumer waiting... Published: Event 4 Published: Event 5 Published: Event 6 Published: Event 7 Buffer is full. Producer waiting... Consumed: Event 4 Consumed: Event 5 Consumed: Event 6 Consumed: Event 7 Buffer is empty. Consumer waiting... Published: Event 8 Published: Event 9 Buffer is empty. Consumer waiting... Consumed: Event 8 Consumed: Event 9
You can download this example from this link.
No comments:
Post a Comment