Java 101: Konkurensi Java tanpa rasa sakit, Bagian 2

Sebelumnya 1 2 3 4 Halaman 3 Berikutnya Halaman 3 dari 4

Variabel atom

Aplikasi multithread yang berjalan pada prosesor multicore atau sistem multiprosesor dapat mencapai pemanfaatan perangkat keras yang baik dan sangat dapat diskalakan. Mereka dapat mencapai tujuan ini dengan meminta utas menghabiskan sebagian besar waktu mereka untuk melakukan pekerjaan daripada menunggu pekerjaan selesai, atau menunggu untuk mendapatkan kunci untuk mengakses struktur data bersama.

Namun, mekanisme sinkronisasi tradisional Java, yang memberlakukan pengecualian timbal balik (utas yang menahan kunci yang menjaga sekumpulan variabel memiliki akses eksklusif ke sana) dan visibilitas (perubahan pada variabel yang dilindungi menjadi terlihat oleh utas lain yang kemudian memperoleh kunci), berdampak pemanfaatan dan skalabilitas perangkat keras, sebagai berikut:

  • Sinkronisasi bersyarat (beberapa utas terus-menerus bersaing untuk mendapatkan kunci) mahal dan akibatnya throughput menderita. Alasan utama dari pengeluaran ini adalah seringnya peralihan konteks yang terjadi; operasi pengalih konteks dapat memerlukan banyak siklus prosesor untuk diselesaikan. Sebaliknya, sinkronisasi yang tidak terkendali tidak mahal pada JVM modern.
  • Ketika utas yang memegang kunci tertunda (misalnya, karena penundaan penjadwalan), tidak ada utas yang memerlukan kunci itu yang membuat kemajuan, dan perangkat keras tidak digunakan sebaik mungkin.

Anda mungkin berpikir bahwa Anda dapat menggunakan volatilesebagai alternatif sinkronisasi. Namun, volatilevariabel hanya menyelesaikan masalah visibilitas. Mereka tidak dapat digunakan untuk mengimplementasikan urutan atomic baca-ubah-tulis dengan aman yang diperlukan untuk menerapkan penghitung dengan aman dan entitas lain yang memerlukan pengecualian bersama.

Java 5 memperkenalkan alternatif sinkronisasi yang menawarkan pengecualian timbal balik yang dikombinasikan dengan kinerja volatile. Ini variabel atom alternatif didasarkan pada instruksi membandingkan-dan-swap mikroprosesor dan sebagian besar terdiri dari jenis di java.util.concurrent.atomicpaket.

Memahami bandingkan-dan-tukar

The membandingkan-dan-swap (CAS) instruksi adalah instruksi yang tidak pernah terputus yang membaca lokasi memori, membandingkan nilai membaca dengan nilai yang diharapkan, dan toko nilai baru dalam lokasi memori ketika nilai membaca sesuai dengan nilai yang diharapkan. Jika tidak, tidak ada yang dilakukan. Instruksi mikroprosesor yang sebenarnya mungkin agak berbeda (misalnya, mengembalikan nilai benar jika CAS berhasil atau salah jika tidak, alih-alih nilai baca).

Petunjuk CAS mikroprosesor

Mikroprosesor modern menawarkan beberapa jenis instruksi CAS. Misalnya, mikroprosesor Intel menawarkan rangkaian cmpxchginstruksi, sedangkan mikroprosesor PowerPC menawarkan instruksi load-link (misalnya lwarx) dan store-conditional (misalnya stwcx) untuk tujuan yang sama.

CAS memungkinkan untuk mendukung urutan baca-ubah-tulis atomik. Anda biasanya akan menggunakan CAS sebagai berikut:

  1. Baca nilai v dari alamat X.
  2. Lakukan penghitungan beberapa langkah untuk mendapatkan nilai baru v2.
  3. Gunakan CAS untuk mengubah nilai X dari v ke v2. CAS berhasil ketika nilai X tidak berubah saat melakukan langkah-langkah ini.

Untuk melihat bagaimana CAS menawarkan kinerja (dan skalabilitas) yang lebih baik melalui sinkronisasi, pertimbangkan contoh penghitung yang memungkinkan Anda membaca nilai saat ini dan menambah penghitung. Kelas berikut mengimplementasikan penghitung berdasarkan synchronized:

Daftar 4. Counter.java (versi 1)

public class Counter { private int value; public synchronized int getValue() { return value; } public synchronized int increment() { return ++value; } }

Perselisihan yang tinggi untuk kunci monitor akan mengakibatkan pengalihan konteks yang berlebihan yang dapat menunda semua utas dan mengakibatkan aplikasi tidak berskala dengan baik.

Alternatif CAS membutuhkan implementasi instruksi bandingkan-dan-tukar. Kelas berikut mengemulasi CAS. Ia menggunakan synchronizedalih-alih instruksi perangkat keras yang sebenarnya untuk menyederhanakan kode:

Daftar 5. EmulatedCAS.java

public class EmulatedCAS { private int value; public synchronized int getValue() { return value; } public synchronized int compareAndSwap(int expectedValue, int newValue) { int readValue = value; if (readValue == expectedValue) value = newValue; return readValue; } }

Di sini, valuemengidentifikasi lokasi memori, yang dapat diambil oleh getValue(). Juga, compareAndSwap()mengimplementasikan algoritma CAS.

Kelas berikut menggunakan EmulatedCASuntuk mengimplementasikan non- synchronizedcounter (berpura-pura EmulatedCAStidak memerlukan synchronized):

Daftar 6. Counter.java (versi 2)

public class Counter { private EmulatedCAS value = new EmulatedCAS(); public int getValue() { return value.getValue(); } public int increment() { int readValue = value.getValue(); while (value.compareAndSwap(readValue, readValue+1) != readValue) readValue = value.getValue(); return readValue+1; } }

Countermengenkapsulasi sebuah EmulatedCASinstance dan mendeklarasikan metode untuk mengambil dan menambah nilai counter dengan bantuan dari instance ini. getValue()mengambil "nilai penghitung saat ini" dari instance dan increment()dengan aman menambah nilai penghitung.

increment()berulang kali memanggil compareAndSwap()sampai readValuenilainya tidak berubah. Kemudian bebas untuk mengubah nilai ini. Jika tidak ada kunci yang terlibat, pertengkaran dihindari bersama dengan peralihan konteks yang berlebihan. Performa meningkat dan kodenya lebih skalabel.

ReentrantLock dan CAS

Anda sebelumnya telah mempelajari bahwa ReentrantLockmenawarkan kinerja yang lebih baik daripada di synchronizedbawah pertengkaran thread tinggi. Untuk meningkatkan kinerja, ReentrantLocksinkronisasi dikelola oleh subkelas dari java.util.concurrent.locks.AbstractQueuedSynchronizerkelas abstrak . Pada gilirannya, kelas ini memanfaatkan kelas yang tidak berdokumen sun.misc.Unsafedan compareAndSwapInt()metode CAS -nya .

Menjelajahi paket variabel atom

Anda tidak harus menerapkan compareAndSwap()melalui Antarmuka Asli Java yang tidak dapat dibawa. Sebaliknya, Java 5 menawarkan dukungan ini melalui java.util.concurrent.atomic: toolkit kelas yang digunakan untuk pemrograman tanpa kunci, aman untuk variabel tunggal.

Menurut java.util.concurrent.atomicJavadoc, kelas-kelas ini

memperluas gagasan volatilenilai, bidang, dan elemen array yang juga menyediakan operasi pembaruan bersyarat atom dari formulir boolean compareAndSet(expectedValue, updateValue). Metode ini (yang bervariasi dalam jenis argumen di berbagai kelas) secara atomis menetapkan variabel ke updateValuejika saat ini memegang expectedValue, melaporkan benar pada keberhasilan.

Paket ini menawarkan kelas untuk jenis Boolean ( AtomicBoolean), integer ( AtomicInteger), long integer ( AtomicLong) dan reference ( AtomicReference). Ini juga menawarkan versi array dari integer, long integer, dan referensi ( AtomicIntegerArray,, AtomicLongArraydan AtomicReferenceArray), kelas referensi yang dapat ditandai dan diberi stempel untuk memperbarui sepasang nilai ( AtomicMarkableReferencedan AtomicStampedReference), dan banyak lagi.

Menerapkan bandingkanAndSet ()

Java mengimplementasikan compareAndSet()melalui konstruksi asli tercepat yang tersedia (misalnya, cmpxchgatau load-link / store-conditional) atau (dalam kasus terburuk) spin lock .

Pertimbangkan AtomicInteger, yang memungkinkan Anda memperbarui intnilai secara atomik. Kita dapat menggunakan kelas ini untuk mengimplementasikan penghitung yang ditunjukkan pada Listing 6. Kode 7 menyajikan kode sumber yang setara.

Daftar 7. Counter.java (versi 3)

import java.util.concurrent.atomic.AtomicInteger; public class Counter { private AtomicInteger value = new AtomicInteger(); public int getValue() { return value.get(); } public int increment() { int readValue = value.get(); while (!value.compareAndSet(readValue, readValue+1)) readValue = value.get(); return readValue+1; } }

Listing 7 is very similar to Listing 6 except that it replaces EmulatedCAS with AtomicInteger. Incidentally, you can simplify increment() because AtomicInteger supplies its own int getAndIncrement() method (and similar methods).

Fork/Join framework

Computer hardware has evolved significantly since Java's debut in 1995. Back in the day, single-processor systems dominated the computing landscape and Java's synchronization primitives, such as synchronized and volatile, as well as its threading library (the Thread class, for example) were generally adequate.

Multiprocessor systems became cheaper and developers found themselves needing to create Java applications that effectively exploited the hardware parallelism that these systems offered. However, they soon discovered that Java's low-level threading primitives and library were very difficult to use in this context, and the resulting solutions were often riddled with errors.

What is parallelism?

Parallelism is the simultaneous execution of multiple threads/tasks via some combination of multiple processors and processor cores.

The Java Concurrency Utilities framework simplifies the development of these applications; however, the utilities offered by this framework do not scale to thousands of processors or processor cores. In our many-core era, we need a solution for achieving a finer-grained parallelism, or we risk keeping processors idle even when there is lots of work for them to handle.

Professor Doug Lea presented a solution to this problem in his paper introducing the idea for a Java-based fork/join framework. Lea describes a framework that supports "a style of parallel programming in which problems are solved by (recursively) splitting them into subtasks that are solved in parallel." The Fork/Join framework was eventually included in Java 7.

Overview of the Fork/Join framework

The Fork/Join framework is based on a special executor service for running a special kind of task. It consists of the following types that are located in the java.util.concurrent package:

  • ForkJoinPool: an ExecutorService implementation that runs ForkJoinTasks. ForkJoinPool provides task-submission methods, such as void execute(ForkJoinTask task), along with management and monitoring methods, such as int getParallelism() and long getStealCount().
  • ForkJoinTask: an abstract base class for tasks that run within a ForkJoinPool context. ForkJoinTask describes thread-like entities that have a much lighter weight than normal threads. Many tasks and subtasks can be hosted by very few actual threads in a ForkJoinPool instance.
  • ForkJoinWorkerThread: a class that describes a thread managed by a ForkJoinPool instance. ForkJoinWorkerThread is responsible for executing ForkJoinTasks.
  • RecursiveAction: an abstract class that describes a recursive resultless ForkJoinTask.
  • RecursiveTask: an abstract class that describes a recursive result-bearing ForkJoinTask.

The ForkJoinPool executor service is the entry-point for submitting tasks that are typically described by subclasses of RecursiveAction or RecursiveTask. Behind the scenes, the task is divided into smaller tasks that are forked (distributed among different threads for execution) from the pool. A task waits until joined (its subtasks finish so that results can be combined).

ForkJoinPool manages a pool of worker threads, where each worker thread has its own double-ended work queue (deque). When a task forks a new subtask, the thread pushes the subtask onto the head of its deque. When a task tries to join with another task that hasn't finished, the thread pops another task off the head of its deque and executes the task. If the thread's deque is empty, it tries to steal another task from the tail of another thread's deque. This work stealing behavior maximizes throughput while minimizing contention.

Using the Fork/Join framework

Fork/Join was designed to efficiently execute divide-and-conquer algorithms, which recursively divide problems into sub-problems until they are simple enough to solve directly; for example, a merge sort. The solutions to these sub-problems are combined to provide a solution to the original problem. Each sub-problem can be executed independently on a different processor or core.

Lea's paper presents the following pseudocode to describe the divide-and-conquer behavior:

Result solve(Problem problem) { if (problem is small) directly solve problem else { split problem into independent parts fork new subtasks to solve each part join all subtasks compose result from subresults } }

The pseudocode presents a solve method that's called with some problem to solve and which returns a Result that contains the problem's solution. If the problem is too small to solve via parallelism, it's solved directly. (The overhead of using parallelism on a small problem exceeds any gained benefit.) Otherwise, the problem is divided into subtasks: each subtask independently focuses on part of the problem.

Operation fork launches a new fork/join subtask that will execute in parallel with other subtasks. Operation join delays the current task until the forked subtask finishes. At some point, the problem will be small enough to be executed sequentially, and its result will be combined along with other subresults to achieve an overall solution that's returned to the caller.

The Javadoc for the RecursiveAction and RecursiveTask classes presents several divide-and-conquer algorithm examples implemented as fork/join tasks. For RecursiveAction the examples sort an array of long integers, increment each element in an array, and sum the squares of each element in an array of doubles. RecursiveTask's solitary example computes a Fibonacci number.

Kode 8 menyajikan aplikasi yang menunjukkan contoh pengurutan dalam konteks non-fork / join serta fork / join. Ini juga menyajikan beberapa informasi waktu untuk membedakan kecepatan penyortiran.