Menerapkan Ring Buffer di Java

1. Ikhtisar

Dalam tutorial ini, kita akan belajar bagaimana menerapkan Ring Buffer di Java.

2. Penyangga Cincin

Ring Buffer (atau Circular Buffer) adalah struktur data melingkar terbatas yang digunakan untuk buffering data antara dua atau lebih utas . Saat kami terus menulis ke buffer cincin, itu membungkus saat mencapai akhir.

2.1. Bagaimana itu bekerja

Ring Buffer diimplementasikan menggunakan array berukuran tetap yang mengelilingi batas .

Terlepas dari array, itu melacak tiga hal:

  • slot berikutnya yang tersedia di buffer untuk memasukkan elemen,
  • elemen yang belum dibaca berikutnya di buffer,
  • dan akhir larik - titik di mana buffer membungkus sekitar awal larik

Mekanisme bagaimana buffer cincin menangani persyaratan ini bervariasi dengan implementasinya. Misalnya, entri Wikipedia tentang subjek menunjukkan metode yang menggunakan empat petunjuk.

Kami akan meminjam pendekatan dari implementasi Disruptor pada buffer cincin menggunakan urutan.

Hal pertama yang perlu kita ketahui adalah kapasitas - ukuran maksimum buffer yang tetap. Selanjutnya, kita akan menggunakan dua urutan yang meningkat secara monoton :

  • Write Sequence: mulai dari -1, bertambah 1 saat kita memasukkan elemen
  • Read Sequence: mulai dari 0, bertambah 1 saat kita mengkonsumsi sebuah elemen

Kita dapat memetakan urutan ke indeks dalam array dengan menggunakan operasi mod:

arrayIndex = sequence % capacity 

The operasi mod membungkus urutan sekitar batas-batas untuk mendapatkan slot di buffer :

Mari kita lihat bagaimana kita memasukkan elemen:

buffer[++writeSequence % capacity] = element 

Kami melakukan pra-penambahan urutan sebelum memasukkan elemen.

Untuk mengonsumsi elemen, kami melakukan kenaikan pasca:

element = buffer[readSequence++ % capacity] 

Dalam hal ini, kami melakukan kenaikan pasca pada urutan. Mengkonsumsi sebuah elemen tidak menghapusnya dari buffer - itu hanya tetap dalam array sampai ditimpa .

2.2. Buffer Kosong dan Penuh

Saat kita membungkus array, kita akan mulai menimpa data di buffer. Jika buffer penuh, kita dapat memilih untuk menimpa data terlama terlepas dari apakah pembaca telah mengonsumsinya atau mencegah penimpaan data yang belum dibaca .

Jika pembaca dapat melewatkan nilai menengah atau lama (misalnya, ticker harga saham), kita dapat menimpa data tanpa menunggu untuk dikonsumsi. Di sisi lain, jika pembaca harus menggunakan semua nilai (seperti transaksi e-commerce), kita harus menunggu (block / busy-wait) hingga buffer memiliki slot yang tersedia.

Buffer penuh jika ukuran buffer sama dengan kapasitasnya , di mana ukurannya sama dengan jumlah elemen yang belum dibaca:

size = (writeSequence - readSequence) + 1 isFull = (size == capacity) 

Jika urutan tulis tertinggal di belakang urutan baca, buffer kosong :

isEmpty = writeSequence < readSequence 

Buffer mengembalikan nilai null jika kosong.

2.2. Keuntungan dan kerugian

Buffer cincin adalah buffer FIFO yang efisien. Ini menggunakan larik berukuran tetap yang dapat dialokasikan sebelumnya di muka dan memungkinkan pola akses memori yang efisien. Semua operasi buffer adalah waktu konstan O (1) , termasuk mengonsumsi elemen, karena tidak memerlukan pergeseran elemen.

Di sisi lain, menentukan ukuran yang benar dari ring buffer sangat penting. Misalnya, operasi tulis dapat memblokir untuk waktu yang lama jika buffer berukuran di bawah dan pembacaannya lambat. Kita dapat menggunakan ukuran dinamis, tetapi itu akan membutuhkan data yang dipindahkan dan kita akan kehilangan sebagian besar keuntungan yang dibahas di atas.

3. Implementasi di Jawa

Sekarang setelah kita memahami cara kerja buffer ring, mari kita lanjutkan untuk mengimplementasikannya di Java.

3.1. Inisialisasi

Pertama, mari tentukan konstruktor yang menginisialisasi buffer dengan kapasitas yang telah ditentukan:

public CircularBuffer(int capacity) { this.capacity = capacity; this.data = (E[]) new Object[capacity]; this.readSequence = 0; this.writeSequence = -1; } 

Ini akan membuat buffer kosong dan menginisialisasi bidang urutan seperti yang dibahas di bagian sebelumnya.

3.3. Menawarkan

Selanjutnya, kita akan mengimplementasikan operasi penawaran yang memasukkan elemen ke dalam buffer di slot yang tersedia berikutnya dan mengembalikan nilai true saat berhasil. Ini mengembalikan false jika buffer tidak dapat menemukan slot kosong, artinya, kita tidak dapat menimpa nilai yang belum dibaca .

Mari kita terapkan metode penawaran di 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; } 

Jadi, kami menambah urutan penulisan dan menghitung indeks dalam larik untuk slot yang tersedia berikutnya. Kemudian, kami menulis data ke buffer dan menyimpan urutan penulisan yang diperbarui.

Mari kita coba:

@Test public void givenCircularBuffer_whenAnElementIsEnqueued_thenSizeIsOne() { CircularBuffer buffer = new CircularBuffer(defaultCapacity); assertTrue(buffer.offer("Square")); assertEquals(1, buffer.size()); } 

3.4. Poll

Finally, we'll implement the poll operation that retrieves and removes the next unread element. The poll operation doesn't remove the element but increments the read sequence.

Let's implement it:

public E poll() { boolean isEmpty = writeSequence < readSequence; if (!isEmpty) { E nextValue = data[readSequence % capacity]; readSequence++; return nextValue; } return null; } 

Here, we're reading the data at the current read sequence by computing the index in the array. Then, we're incrementing the sequence and returning the value, if the buffer is not empty.

Let's test it out:

@Test public void givenCircularBuffer_whenAnElementIsDequeued_thenElementMatchesEnqueuedElement() { CircularBuffer buffer = new CircularBuffer(defaultCapacity); buffer.offer("Triangle"); String shape = buffer.poll(); assertEquals("Triangle", shape); } 

4. Producer-Consumer Problem

We've talked about the use of a ring buffer for exchanging data between two or more threads, which is an example of a synchronization problem called the Producer-Consumer problem. In Java, we can solve the producer-consumer problem in various ways using semaphores, bounded queues, ring buffers, etc.

Let's implement a solution based on a ring buffer.

4.1. volatile Sequence Fields

Our implementation of the ring buffer is not thread-safe. Let's make it thread-safe for the simple single-producer and single-consumer case.

The producer writes data to the buffer and increments the writeSequence, while the consumer only reads from the buffer and increments the readSequence. So, the backing array is contention-free and we can get away without any synchronization.

But we still need to ensure that the consumer can see the latest value of the writeSequence field (visibility) and that the writeSequence is not updated before the data is actually available in the buffer (ordering).

We can make the ring buffer concurrent and lock-free in this case by making the sequence fields volatile:

private volatile int writeSequence = -1, readSequence = 0; 

In the offer method, a write to the volatile field writeSequence guarantees that the writes to the buffer happen before updating the sequence. At the same time, the volatile visibility guarantee ensures that the consumer will always see the latest value of writeSequence.

4.2. Producer

Let's implement a simple producer Runnable that writes to the ring buffer:

public void run() { for (int i = 0; i < items.length;) { if (buffer.offer(items[i])) { System.out.println("Produced: " + items[i]); i++; } } } 

The producer thread would wait for an empty slot in a loop (busy-waiting).

4.3. Consumer

We'll implement a consumer Callable that reads from the buffer:

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

Utas konsumen berlanjut tanpa mencetak jika menerima nilai null dari buffer.

Mari tulis kode driver kita:

executorService.submit(new Thread(new Producer(buffer))); executorService.submit(new Thread(new Consumer(buffer))); 

Menjalankan program produsen-konsumen kami menghasilkan keluaran seperti di bawah ini:

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. Kesimpulan

Dalam tutorial ini, kita telah belajar bagaimana menerapkan Ring Buffer dan mengeksplorasi bagaimana itu dapat digunakan untuk memecahkan masalah produsen-konsumen.

Seperti biasa, kode sumber untuk semua contoh tersedia di GitHub.