Pengantar Struktur Data Tanpa Kunci dengan Contoh Java

1. Perkenalan

Dalam tutorial ini, kita akan mempelajari apa itu struktur data non-pemblokiran dan mengapa mereka merupakan alternatif penting untuk struktur data konkuren berbasis kunci.

Pertama, kita akan membahas beberapa istilah seperti bebas halangan , bebas kunci , dan bebas menunggu .

Kedua, kita akan melihat blok bangunan dasar dari algoritma non-pemblokiran seperti CAS (bandingkan-dan-tukar).

Ketiga, kita akan melihat implementasi antrian bebas kunci di Java, dan terakhir, kita akan menjelaskan pendekatan tentang bagaimana mencapai kebebasan menunggu .

2. Terkunci versus Kelaparan

Pertama, mari kita lihat perbedaan antara utas yang diblokir dan utas kelaparan.

Pada gambar di atas, Thread 2 memperoleh kunci pada struktur data. Saat Thread 1 juga mencoba untuk mendapatkan kunci, maka Thread 2 harus menunggu hingga Thread 2 melepaskan kunci; itu tidak akan dilanjutkan sebelum bisa mendapatkan kunci. Jika kita menangguhkan Thread 2 saat masih terkunci, Thread 1 harus menunggu selamanya.

Gambar berikut mengilustrasikan kelaparan benang:

Di sini, Thread 2 mengakses struktur data tetapi tidak mendapatkan kunci. Thread 1 mencoba mengakses struktur data pada saat yang sama, mendeteksi akses bersamaan, dan segera kembali, memberi tahu thread bahwa ia tidak dapat menyelesaikan (merah) operasi tersebut. Thread 1 kemudian akan mencoba lagi hingga berhasil menyelesaikan operasi (hijau).

Keuntungan dari pendekatan ini adalah kita tidak membutuhkan kunci. Namun, yang dapat terjadi adalah jika Thread 2 (atau thread lain) mengakses struktur data dengan frekuensi tinggi, maka Thread 1 memerlukan banyak upaya hingga akhirnya berhasil. Kami menyebutnya kelaparan.

Nanti kita akan melihat bagaimana operasi bandingkan-dan-tukar mencapai akses non-pemblokiran.

3. Jenis Struktur Data Non-Pemblokiran

Kita dapat membedakan antara tiga tingkat struktur data non-pemblokiran.

3.1. Bebas Obstruksi

Kebebasan-penghalang adalah bentuk terlemah dari struktur data non-pemblokiran. Di sini, kami hanya mengharuskan utas dijamin untuk melanjutkan jika semua utas lainnya ditangguhkan .

Lebih tepatnya, utas tidak akan terus kelaparan jika semua utas lainnya ditangguhkan. Ini berbeda dengan menggunakan kunci dalam pengertian itu, bahwa jika utas menunggu kunci dan utas yang menahan kunci ditangguhkan, utas menunggu akan menunggu selamanya.

3.2. Bebas Kunci

Struktur data memberikan kebebasan kunci jika, kapan saja, setidaknya satu utas dapat dilanjutkan . Semua utas lainnya mungkin kelaparan. Perbedaan dengan kebebasan-obstruksi adalah bahwa setidaknya ada satu utas yang tidak kelaparan meskipun tidak ada utas yang ditangguhkan.

3.3. Bebas Menunggu

Struktur data bebas menunggu jika bebas kunci dan setiap utas dijamin akan dilanjutkan setelah sejumlah langkah terbatas, yaitu, utas tidak akan kelaparan untuk sejumlah langkah yang "terlalu besar".

3.4. Ringkasan

Mari kita rangkum definisi ini dalam representasi grafis:

Bagian pertama gambar menunjukkan kebebasan-gangguan karena Utas 1 (utas atas) dapat dilanjutkan (panah hijau) segera kami menangguhkan utas lainnya (di bawah dengan warna kuning).

Bagian tengah menunjukkan kebebasan kunci. Setidaknya Untaian 1 bisa maju sementara yang lain mungkin kelaparan (panah merah).

Bagian terakhir menunjukkan kebebasan menunggu. Di sini, kami menjamin bahwa Thread 1 dapat berlanjut (panah hijau) setelah periode kelaparan tertentu (panah merah).

4. Primitif Non-Blocking

Di bagian ini, kita akan melihat tiga operasi dasar yang membantu kita membangun operasi tanpa kunci pada struktur data.

4.1. Bandingkan dan Tukar

Salah satu operasi dasar yang digunakan untuk menghindari penguncian adalah operasi bandingkan-dan-tukar (CAS) .

Ide dari bandingkan-dan-tukar adalah, bahwa sebuah variabel hanya diperbarui jika ia masih memiliki nilai yang sama seperti pada saat kita mengambil nilai variabel dari memori utama. CAS adalah operasi atomik, yang berarti pengambilan dan pembaruan bersama adalah satu operasi tunggal :

Di sini, kedua utas mengambil nilai 3 dari memori utama. Thread 2 berhasil (hijau) dan memperbarui variabel menjadi 8. Karena CAS pertama dengan thread 1 mengharapkan nilainya tetap 3, CAS gagal (merah). Oleh karena itu, Thread 1 mengambil nilainya lagi, dan CAS kedua berhasil.

Hal yang penting di sini adalah bahwa CAS tidak memperoleh kunci pada struktur data tetapi mengembalikan nilai true jika pembaruan berhasil, jika tidak maka akan mengembalikan false .

Potongan kode berikut menguraikan cara kerja CAS:

volatile int value; boolean cas(int expectedValue, int newValue) { if(value == expectedValue) { value = newValue; return true; } return false; }

Kami hanya memperbarui nilai dengan nilai baru jika masih memiliki nilai yang diharapkan, jika tidak, mengembalikan salah . Potongan kode berikut menunjukkan bagaimana CAS dapat dipanggil:

void testCas() { int v = value; int x = v + 1; while(!cas(v, x)) { v = value; x = v + 1; } }

Kami mencoba memperbarui nilai kami sampai operasi CAS berhasil, yaitu mengembalikan nilai true .

Namun, ada kemungkinan utas terjebak dalam kelaparan . Hal ini dapat terjadi jika thread lain melakukan CAS pada variabel yang sama pada waktu yang sama, sehingga operasi tidak akan pernah berhasil untuk thread tertentu (atau membutuhkan waktu yang tidak wajar untuk berhasil). Namun, jika bandingkan-dan-tukar gagal, kami tahu bahwa utas lain telah berhasil, oleh karena itu kami juga memastikan kemajuan global, seperti yang diperlukan untuk kebebasan kunci.

Penting untuk dicatat bahwa perangkat keras harus mendukung bandingkan-dan-tukar , untuk membuatnya benar-benar operasi atom tanpa menggunakan penguncian.

Java menyediakan implementasi bandingkan-dan-tukar di kelas sun.misc.Unsafe . Namun, dalam banyak kasus, kita tidak boleh menggunakan kelas ini secara langsung, melainkan variabel Atom.

Selain itu, bandingkan-dan-tukar tidak mencegah masalah ABA. Kami akan melihatnya di bagian berikut.

4.2. Load-Link / Store-Conditional

Alternatif untuk membandingkan-dan-swap adalah load-link / store-conditional . Mari kita lihat kembali bandingkan-dan-tukar . Seperti yang telah kita lihat sebelumnya, CAS hanya memperbarui nilai jika nilai di memori utama masih sesuai dengan yang kita harapkan.

Namun CAS juga berhasil jika nilainya telah berubah, dan, sementara itu, telah kembali ke nilai sebelumnya.

Gambar di bawah mengilustrasikan situasi ini:

Keduanya, thread 1 dan Thread 2 membaca nilai variabel, yaitu 3. Kemudian Thread 2 melakukan CAS, yang berhasil mengatur variabel ke 8. Kemudian lagi, Thread 2 melakukan CAS untuk mengatur variabel kembali ke 3, yang berhasil juga. Terakhir, Thread 1 melakukan CAS, mengharapkan nilai 3, dan berhasil juga, meskipun nilai variabel kami dimodifikasi dua kali di antaranya.

This is called the A-B-A problem. This behavior might not be a problem depending on the use-case, of course. However, it might not be desired for others. Java provides an implementation of load-link/store-conditional with the AtomicStampedReference class.

4.3. Fetch and Add

Another alternative is fetch-and-add. This operation increments the variable in the main memory by a given value. Again, the important point is that the operation happens atomically, which means no other thread can interfere.

Java provides an implementation of fetch-and-add in its atomic classes. Examples are AtomicInteger.incrementAndGet(), which increments the value and returns the new value; and AtomicInteger.getAndIncrement(), which returns the old value and then increments the value.

5. Accessing a Linked Queue from Multiple Threads

To better understand the problem of two (or more) threads accessing a queue simultaneously, let's look at a linked queue and two threads trying to add an element concurrently.

The queue we'll look at is a doubly-linked FIFO queue where we add new elements after the last element (L) and the variable tail points to that last element:

To add a new element, the threads need to perform three steps: 1) create the new elements (N and M), with the pointer to the next element set to null; 2) have the reference to the previous element point to L and the reference to the next element of L point to N (M, respectively). 3) Have tail point to N (M, respectively):

What can go wrong if the two threads perform these steps simultaneously? If the steps in the above picture execute in the order ABCD or ACBD, L, as well as tail, will point to M. N will remain disconnected from the queue.

If the steps execute in the order ACDB, tail will point to N, while L will point to M, which will cause an inconsistency in the queue:

Of course, one way to solve this problem is to have one thread acquire a lock on the queue. The solution we'll look at in the following chapter will solve the problem with the help of a lock-free operation by using the CAS operation we've seen earlier.

6. A Non-Blocking Queue in Java

Let's look at a basic lock-free queue in Java. First, let's look at the class members and the constructor:

public class NonBlockingQueue { private final AtomicReference
    
      head, tail; private final AtomicInteger size; public NonBlockingQueue() { head = new AtomicReference(null); tail = new AtomicReference(null); size = new AtomicInteger(); size.set(0); } }
    

The important part is the declaration of the head and tail references as AtomicReferences, which ensures that any update on these references is an atomic operation. This data type in Java implements the necessary compare-and-swap operation.

Next, let's look at the implementation of the Node class:

private class Node { private volatile T value; private volatile Node next; private volatile Node previous; public Node(T value) { this.value = value; this.next = null; } // getters and setters }

Here, the important part is to declare the references to the previous and next node as volatile. This ensures that we update these references always in the main memory (thus are directly visible to all threads). The same for the actual node value.

6.1. Lock-Free add

Our lock-free add operation will make sure that we add the new element at the tail and won't be disconnected from the queue, even if multiple threads want to add a new element concurrently:

public void add(T element) { if (element == null) { throw new NullPointerException(); } Node node = new Node(element); Node currentTail; do { currentTail = tail.get(); node.setPrevious(currentTail); } while(!tail.compareAndSet(currentTail, node)); if(node.previous != null) { node.previous.next = node; } head.compareAndSet(null, node); // for inserting the first element size.incrementAndGet(); }

The essential part to pay attention to is the highlighted line. We attempt to add the new node to the queue until the CAS operation succeeds to update the tail, which must still be the same tail to which we appended the new node.

6.2. Lock-Free get

Similar to the add-operation, the lock-free get-operation will make sure that we return the last element and move the tail to the current position:

public T get() { if(head.get() == null) { throw new NoSuchElementException(); } Node currentHead; Node nextNode; do { currentHead = head.get(); nextNode = currentHead.getNext(); } while(!head.compareAndSet(currentHead, nextNode)); size.decrementAndGet(); return currentHead.getValue(); }

Again, the essential part to pay attention to is the highlighted line. The CAS operation ensures that we move the current head only if no other node has been removed in the meantime.

Java already provides an implementation of a non-blocking queue, the ConcurrentLinkedQueue. It's an implementation of the lock-free queue from M. Michael and L. Scott described in this paper. An interesting side-note here is that the Java documentation states that it's a wait-free queue, where it's actually lock-free. The Java 8 documentation correctly calls the implementation lock-free.

7. Wait-Free Queues

As we've seen, the above implementation is lock-free, however, not wait-free. The while loops in both the add and get method can potentially loop for a long time (or, though unlikely, forever) if there are many threads accessing our queue.

How can we achieve wait-freedom? The implementation of wait-free algorithms, in general, is quite tricky. We refer the interested reader to this paper, which describes a wait-free queue in detail. In this article, let's look at the basic idea of how we can approach a wait-free implementation of a queue.

A wait-free queue requires that every thread makes guaranteed progress (after a finite number of steps). In other words, the while loops in our add and get methods must succeed after a certain number of steps.

In order to achieve that, we assign a helper thread to every thread. If that helper thread succeeds to add an element to the queue, it will help the other thread to insert its element before inserting another element.

As the helper thread has a helper itself, and, down the whole list of threads, every thread has a helper, we can guarantee that a thread succeeds the insertion latest after every thread has done one insertion. The following figure illustrates the idea:

Of course, things become more complicated when we can add or remove threads dynamically.

8. Conclusion

Dalam artikel ini, kami melihat dasar-dasar struktur data non-pemblokiran. Kami menjelaskan berbagai level dan operasi dasar seperti bandingkan-dan-tukar .

Kemudian, kami melihat implementasi dasar antrean bebas kunci di Java. Terakhir, kami menguraikan gagasan tentang cara mencapai kebebasan menunggu .

Kode sumber lengkap untuk semua contoh dalam artikel ini tersedia di GitHub.