Tanpa futex, semua itu tidak berarti

• Ada kritik bahwa buku teks The Art of Multiprocessor Programming tidak membahas konsep futex, dan itu sangat disayangkan
• Futex adalah komponen inti untuk sinkronisasi yang efisien dalam pemrograman paralel modern, dengan kinerja yang lebih baik daripada lock lama berbasis System V
• Futex memiliki struktur yang memisahkan perolehan lock dari fungsi wait/wake, sehingga mengurangi system call dan overhead yang tidak perlu
• Termasuk penjelasan contoh dan teknik untuk langsung mengimplementasikan berbagai primitive konkurensi berbasis futex seperti spinlock, mutex, dan recursive lock
• Penulis menyoroti kesenjangan antara akademia dan praktik industri karena buku tersebut tidak membahas metodologi sinkronisasi modern yang penting untuk pekerjaan engineering nyata

---

Pendahuluan

• Phil Eaton memulai klub buku untuk 'The Art of Multiprocessor Programming, 2nd Edition'
• Buku ini dianggap sebagai buku teks otoritatif di bidang pemrograman paralel, tetapi penulis mengkritik kurangnya nilai praktis dalam isinya
• Secara khusus, penulis mengkritik bahwa meskipun buku ini ditujukan untuk mahasiswa tingkat akhir S1 dan mahasiswa pascasarjana, buku ini tidak membahas futex, sebuah teknik sinkronisasi inti

Apa itu futex — dan mengapa penting

• Futex adalah singkatan dari “fast user space mutex”, tetapi sebenarnya bukan mutex melainkan blok pembangun primitif sinkronisasi dengan dukungan OS untuk implementasi lock modern
• Di masa lalu, sebagian besar lock diimplementasikan berdasarkan semaphore dari System V IPC sehingga memiliki keterbatasan dalam efisiensi dan skalabilitas
• Ketika futex diperkenalkan di Linux pada tahun 2002, ia menunjukkan kinerja 20 hingga 120 kali lebih cepat dibanding lock System V dalam lingkungan dengan 1.000 pekerjaan simultan
• OS lain seperti Windows (2012) dan macOS (2016) juga mengadopsi mekanisme serupa
• Lock di library sistem yang banyak dipakai saat ini seperti pthreads menggunakan futex

Cara kerja futex dan apa yang membedakannya

• Semaphore tradisional menggabungkan lock dan penantian, tetapi futex memisahkan perolehan lock dari wait/wake
• Karena itu, delay dan system call yang tidak perlu dapat dikurangi, dan saat lock dilepas, jika dipastikan tidak ada thread yang menunggu maka tidak perlu masuk ke kernel
• Pemanggilan wait pada futex membuat thread “menunggu hanya ketika nilai di alamat memori tertentu berada pada status yang diinginkan”, dan juga mendukung timeout
• Pemanggilan wake pada futex membangunkan jumlah thread yang diinginkan dari daftar tunggu internal yang terhubung ke alamat memori tertentu
• Karena memerlukan verifikasi nilai aktual pada alamat memori, futex mencegah penantian yang tidak perlu jika status sudah berubah

Pemanfaatan nyata futex — implementasi langsung

• Karena futex adalah primitive tingkat rendah, digunakan tipe data atomic dengan mempertimbangkan isu urutan operasi memori pada compiler dan hardware
• Di Linux, system call futex harus dipanggil langsung lewat syscall, sedangkan di macOS digunakan antarmuka __ulock (belakangan ditambahkan API yang lebih mudah)
• Pada dasarnya, wait futex mengembalikan 0 saat berhasil dan kode error saat gagal (misalnya timeout)
• Operasi inti berbasis futex:
  • h4x0r_futex_wait_timespec() : menunggu jika nilai yang diharapkan cocok, dengan opsi timeout
  • h4x0r_futex_wake() : membangunkan 1 atau semua penunggu

Contoh praktik implementasi mutex/spinlock/recursive lock

Spinlock

• Bentuk lock paling sederhana, bekerja hanya dengan satu bit tunggal (atomic_fetch_or)
• Ia berputar dalam loop tanpa henti (“spin”) sampai mendapatkan lock, tetapi membuang CPU saat kontensi tinggi dan memiliki masalah struktural seperti pelepasan yang salah serta risiko deadlock saat dipanggil secara rekursif

Mutex hibrida (‘unsafe’ mutex)

• Biasanya mencoba dulu dengan spinlock, lalu jika gagal sejumlah kali beralih ke futex untuk blocking yang efisien
• Jika tidak ada penunggu, system call yang tidak perlu bisa dihindari, dan untuk penunggu jumlah system call wake juga dapat diminimalkan
• Karena verifikasi kepemilikan yang ketat atau penanganan rekursi belum memadai, digunakan nama “unsafe”

Mutex dengan penghitung penunggu

• Satu bit dipakai untuk status lock, sisanya untuk menghitung jumlah penunggu, dengan tujuan mengurangi system call wake yang tidak perlu
• Tetap belum memiliki penanganan kepemilikan maupun rekursi

Mutex dengan manajemen kepemilikan

• Dengan nilai pthread_t, pemilik lock dan statusnya dilacak dengan jelas sehingga masalah dapat dideteksi saat unlock salah atau saat dipakai secara rekursif
• Perolehan lock, pelepasan, dan pengelolaan penunggu semuanya dikendalikan secara ketat dengan operasi atomic

Recursive lock

• Dengan menambahkan penghitung kedalaman (depth) per thread, thread yang sama bisa memperoleh lock yang bertumpuk
• Saat unlock, depth dikurangi, dan ketika menjadi 0 barulah unlock sebenarnya serta wake dijalankan
• Setiap operasi diimplementasikan dengan operasi atomic dan pemeriksaan kepemilikan yang ketat

Tugas yang tersisa dan realitas engineering di lapangan

• Jika thread pemilik lock berhenti secara abnormal atau mati, maka diperlukan daftar manajemen terpisah, callback saat terminasi, dan pengelolaan tambahan lainnya untuk mengelola lock
• Saat memakai mutex bersama antarproses, dibutuhkan pertimbangan tambahan untuk mengelola perubahan status
• POSIX RW lock tidak mendefinisikan perilaku tumpukan rekursif dan implementasinya berbeda-beda, sehingga dalam praktik sulit menjamin keamanannya
• Penulis mengkritik bahwa isu konkurensi yang benar-benar penting di lapangan (futex, recursive lock, asynchronous runtime, dan lain-lain) tidak dimasukkan buku itu ke dalam kurikulum

Kesimpulan

• 'The Art of Multiprocessor Programming' terlalu berat ke sejarah atau sudut pandang teoretis sehingga gagal memuat pengetahuan praktik penting dalam pemrograman paralel modern
• Jika komponen sinkronisasi inti seperti futex yang benar-benar digunakan di sistem tidak dibahas dengan semestinya, hal itu berpotensi menimbulkan dampak buruk nyata bagi generasi penerus
• Penulis menekankan perlunya memasukkan konsep-konsep terbaru dan melengkapi isi dengan materi yang lebih praktis

Referensi

• Contoh kode lengkap dapat dilihat di codeberg

[GN⁺]

Komentar Hacker News

• Windows memiliki fitur bernama WaitForMultipleObjects, dan Linux juga memperkenalkannya lewat Futex2 pada 5.16 (akhir 2021)
  tautan terkait
  Belakangan ini berbagai peningkatan telah dilakukan pada Futex2
  Dukungan NUMA akhirnya juga ditambahkan
  tautan terkait NUMA 1
  tautan terkait NUMA 2
  NUMA adalah faktor yang sangat penting bagi performa
  Saat io_uring diterapkan ke futex pada 6.7 (2024), hal itu membantu meningkatkan performa aio PostgreSQL
  tulisan terkait
  Pada 6.7 juga ditambahkan fitur small requeue dan single wait
  tautan terkait

  • Windows bukan baru menambahkan fitur WaitForMultipleObjects; fitur itu sudah ada sejak awal selama lebih dari 30 tahun
    WaitForMultipleObjects memang merupakan keunggulan Windows NT dibanding UNIX, tetapi IBM PL/I juga sudah memiliki fitur serupa pada 1965
    Fungsi 'wait' di UNIX adalah versi sederhana dari 'wait' di IBM PL/I, dan seperti banyak fitur lain yang diwarisi dari Multics, kemampuannya lebih lemah daripada model aslinya
    WaitForSingleObject dan WaitForMultipleObjects milik Microsoft juga bukan implementasi yang efisien, sehingga pada akhirnya mereka tetap perlu memperkenalkan WaitOnAddress yang setara dengan futex Linux
    Futex Linux punya keterbatasan berupa ukuran 32-bit dan hanya bisa menunggu satu event
    Memang mungkin mengimplementasikan penantian terhadap beberapa event dengan operasi bit atomik, tetapi itu tidak efisien sehingga masalah batas 32-bit menjadi makin terasa
    Senang melihat ada upaya menggabungkan sebagian keunggulan WaitForMultipleObjects ke dalam 'futex'
    Upaya seperti ini bukan meniru Windows, melainkan sebenarnya mengimplementasikan ulang teknik klasik yang sudah dikenal luas selama lebih dari 50 tahun, jauh lebih tua daripada Microsoft

  • Sayang sekali sampai sekarang masih belum ada fitur futex_swap
    diskusi terkait 1
    materi terkait 2

  • Futex tidak ada hubungannya dengan WFMO (WaitForMultipleObjects); konsep yang setara justru keyed events
    Di Linux, fitur yang setara dengan WFMO adalah select/poll/epoll

  • Dukungan futex di io_uring benar-benar fitur yang sangat bagus
    Saya memakainya saat bekerja dengan Ruby fibers untuk implementasi mutex dan queue
    lihat source code

• Buku itu sendiri mengatakan agar menggunakan struktur sinkronisasi yang disediakan library/bahasa/sistem, bukan mengimplementasikannya langsung
  Fokus utama buku itu ada pada konsep concurrency secara umum, bukan platform tertentu
  Sayang penulis artikel membingkainya dengan oposisi yang agak berlebihan
  Akan lebih baik kalau tulisan ini dibahas dari sudut pandang kolaboratif seperti "hal-hal yang tidak dibahas TAoMP"
  Cukup mencolok bahwa blog ini baru dibuat, Phil yang mengunggah tulisan ini, dan Phil juga yang mempromosikan tulisan lainnya

  • Saya yang menulis artikel itu, dan saya menulisnya karena kecewa setelah membaca bukunya
    Saya merasa masalahnya adalah baik di akademia maupun industri, kita tidak benar-benar belajar hal-hal yang praktis dan berguna
    Jadi maksudnya bukan gaya "ayo pelajari futex!"
    Saya memang sangat kecewa pada bukunya sampai-sampai menunda tulisan lain dan menulis ini lebih dulu
    Saya memang punya hubungan dengan Phil karena dulu pernah bekerja bersama, tetapi sejauh ini saya tidak kesulitan mendapatkan pembaca untuk tulisan saya

  • Saya rasa bagian yang dulu menyebut gaya sysv bahkan tidak layak disebut dinosaurus itu memang terlalu keras
    Itu bagian yang butuh lebih banyak kerendahan hati

• Hal paling keren dari futex adalah strukturnya yang handle-less
  Ia memberi perilaku dasar yang sangat berguna sebagai pengawas memori berbasis kernel tanpa perlu alokasi/dealokasi lewat syscall
  Jika tidak ada thread yang menunggu, semuanya dibersihkan dengan rapi, dan jika tidak ada contention, kernel bahkan tidak menyadari keberadaan mutex itu sendiri
  Saya penasaran dengan analisis detail tentang bagaimana kernel mengelola futex dengan performa tinggi
  Hari ini saya baru tahu soal futex2
  dokumentasi terkait

  • Betul, dan kita juga tidak ingin setiap kali thread terblokir pada lock, kernel memanggil malloc() untuk mengalokasikan data
    Untuk mencegah itu, banyak OS mengalokasikan 'queue object' saat thread dibuat, lalu ketika thread tersebut menemui contested lock, objek itu dipasangkan ke lock
    Jadi ada linked list berisi queue object milik berbagai thread yang terhubung ke lock, dan setiap kali sebuah thread dibangunkan, ia membawa satu objek keluar
    Saat thread berakhir, tidak ada jaminan ia akan mendapatkan kembali objek yang semula dibuat untuknya; objek-objek itu bisa tertukar di tengah jalan
    Solaris pertama kali memperkenalkan struktur seperti ini (turnstile), dan BSD juga mengadopsi cara tersebut
    lihat Solaris internals
    materi PDF BSD

  • Antrean tunggu dalam kernel Unix awal juga menggunakan cara seperti ini

• Dalam paper futex orisinal tahun 2002 pun efisiensi futex sudah dibuktikan dengan jelas, dan pada pengujian 1000 task paralel performanya 20–120 kali lebih cepat daripada lock sysv
  Tetapi secara praktik baseline-nya bukanlah lock sysv
  Dalam kenyataannya, saat mengimplementasikan lock tanpa futex, kebanyakan pendekatan tetap tidak masuk kernel pada fast path dan hanya berpindah ke kernel untuk menunggu pada slow path; satu-satunya perbaikan futex adalah ukuran struktur data user-space yang menandai status menunggu lock menjadi lebih kecil
  Alternatif lain seperti thin locks (cara yang dipakai JVM) atau ParkingLot (implementasi sepenuhnya di userland) juga bisa berjalan tanpa futex OS

  • Dari pengalaman saya, kebanyakan orang pada praktiknya memang mempelajari primitive bawaan yang disediakan di lapangan, jadi fokusnya menjadi pada apa yang disediakan standard library bahasa mereka
    Artinya, alur perpindahan dari sysv ke futex memang dominan, dan belakangan memang ada pendekatan kustom, tetapi arus utamanya tetap futex
    Kalau membuat scheduler userland sendiri mungkin implementasi terpisah juga memungkinkan, tetapi saya rasa kebanyakan orang akan memakai cara menulis ke file descriptor dan mengelola queue sendiri
    Saya ragu seberapa besar keuntungan dari cara seperti itu

  • Pada praktiknya, lock modern apa pun pada akhirnya akan memakai futex di dalamnya jika tersedia
    Karena di Linux futex adalah cara menunggu yang paling efisien, pada slow (down) path selalu lebih baik menggunakan futex
    Hal seperti thread.park() di level bahasa kemungkinan besar juga berjalan di atas futex

  • Saya penasaran apakah JVM masih memakai thin lock
    Dulu saya pernah menemukan referensi bahwa JVM memanggil futex; saya ingin tahu apakah sekarang sudah bermigrasi ke thin lock
    diskusi Stack Overflow terkait

• Implementasi nyata dari [recursive locks] tidak konsisten bahkan antar-standar, dan karena dianggap sulit, dalam banyak kasus malah tidak didefinisikan sama sekali
  Sikap seperti ini cukup membuat frustrasi
  Semacam, "karena implementor OS atau bahasa mungkin tidak bisa mengimplementasikan fitur X dengan benar, biarkan saja developer aplikasi yang menanganinya sendiri"
  Akhirnya pengguna downstream praktis tidak punya pilihan selain mengganti vendor

  • Jika standar diberi terlalu banyak batasan, kemungkinan implementasi yang lebih baik bisa tertutup
    Sebagai contoh, hash table dan regular expression standar C++ jauh lebih lambat daripada implementasi pihak ketiga karena terlalu banyak batasan
    Kalau ada batasan tertentu (misalnya harus memakai chaining) atau jaminan fitur tertentu, implementasi alternatif yang berperforma tinggi bisa terhalang
    Untuk recursive rwlock juga mungkin saja ada implementasi yang mengorbankan performa atau lebih sedikit pemeriksaan, jadi menurut saya tidak perlu menutup berbagai kemungkinan arah

  • Secara pribadi saya rasa recursive lock memang sebaiknya tidak dipakai sejak awal, jadi saya tidak merasa spesifikasi dukungannya perlu dimasukkan ke standar

  • Kalau ingin memahami fenomena worse is better lebih jauh, lihat saja wiki
    Saya juga tidak terlalu menyukainya, tetapi itulah kenyataan yang tidak bisa dihindari

• Saya jadi penasaran dengan keterbatasan futex di Linux yang hanya mendukung int 32-bit, lalu mencarinya
  Dalam diskusi dukungan 64-bit, Linus menyebut bahwa di user-space cukup gunakan atomic 64-bit dan pakai 32-bit bawahnya saja untuk futex
  Namun di C/C++, atomic dengan ukuran campuran dianggap undefined behavior, dan implementasi semaphore glibc juga bekerja seperti itu
  Pada integer 64-bit, 32-bit atas dipakai sebagai waiter count, 32-bit bawah sebagai nilai semaphore, dan futex hanya digunakan pada 32-bit bawah
  Saya penasaran apakah ini perilaku yang terdefinisi di gcc, atau tidak masalah karena melintasi batas proses (kernel process), atau justru glibc sendiri juga memakai undefined behavior

• Saya juga merekomendasikan C++ Concurrency in Action karya Anthony Williams; meski tidak membahas futex atau cara mengimplementasikan synchronization primitive secara langsung, buku itu membahas hal-hal yang lebih dekat dengan praktik nyata seperti memory ordering dan SMR yang dibutuhkan untuk struktur lock-free
  Jika membutuhkan sudut pandang yang lebih berfokus pada hardware, saya juga merekomendasikan buku gratis Paul McKenney, "Is Parallel Programming Hard, And, If So, What Can You Do About It?"
  Buku ini juga tidak mendalami futex, tetapi mengarahkan pembaca ke "Futexes Are Tricky" karya Ulrich Drepper
  TAOMPP cocok untuk membahas konsep concurrency tingkat tinggi, dan memang tidak tepat jika diharapkan memuat detail implementasi level OS
  Bagaimanapun juga, Peterson lock atau bakery lock memang tidak berguna untuk penggunaan nyata, tetapi mempelajari pembuktiannya sangat membantu memahami algoritme concurrency di dunia nyata

  • Bakery lock bagus untuk spin lock, dan ramah cache
    Reader/writer spin lock juga bisa diimplementasikan, tetapi hasilnya akan strict FIFO
    Di user space, mungkin saja menghubungkan futex ke spin wait bakery lock, tetapi itu sangat tidak efisien
    Futex memang sejak awal tidak dirancang untuk penggunaan seperti ini (spin waiting)
    Struktur lock-free, hazard pointer, RCU* dan sejenisnya juga tetap tricky
    Bahkan wait-free hazard pointer pun sebenarnya bisa dibuat
    *Untuk RCU, copy-on-write memang intuitif, tetapi jika update terlalu sering, biayanya akan meningkat

• Seperti halnya Windows 8 memperkenalkan hal yang mirip futex, Win32 critical section pada awalnya berbasis semaphore kernel
  Namun saya penasaran struktur seperti apa yang dipakai SRW lock yang diperkenalkan di Vista

  • Baik CRITICAL_SECTION maupun SRWLock tidak masuk ke kernel jika tidak ada contention
    SRWLock berbasis keyed event, sedangkan CRITICAL_SECTION saat gagal akan membuat kernel object secara on-demand lalu memanggilnya, dengan fallback ke keyed event

• Dalam implementasi futex Linux tahun 2014, pada salah satu kerentanan yang ditemukan Pinkie Pie, aturan requeue-once hanya diizinkan untuk futex yang diberikan ke futex_wait_requeue_pi
  Requeue dari A ke B lalu lagi dari B ke C tidak dimungkinkan, tetapi pengalihan ulang dari B ke B tetap dimungkinkan
  Dalam kondisi tertentu, ada bug yang membuat fungsi cleanup tidak dipanggil, sehingga pointer menjadi dangling
  Kasus terkait bisa dilihat di sini
  isu terkait

• Ada orang yang tidak terlalu khawatir soal integritas data akibat thread yang crash, tetapi selama seluruh proses tidak ikut mati, masalah pembersihan lock tetap ada
  Solusi untuk itu adalah robust lock
  Daftar held futex didaftarkan ke kernel, dan lewat sys_set_robust_list bit terkait diproses saat thread berakhir untuk membangunkan pihak yang menunggu

  • Kelemahan terbesar pendekatan robust lock adalah resource yang dilindungi lock itu sendiri kemungkinan besar sudah berada dalam keadaan tidak konsisten
    Kalau kita tidak tahu pasti kenapa thread itu crash, data itu bisa saja sudah tidak utuh sehingga tidak mungkin dipulihkan
    Karena itu, dalam banyak kasus mungkin justru lebih masuk akal mematikan seluruh aplikasi
    Fitur cleanup/recovery berbasis robust lock memang keren, tetapi mungkin 95% engineer tidak akan benar-benar merancang struktur data yang robust
    4% lainnya mungkin tidak punya cukup waktu, dan hanya 1% sisanya yang benar-benar melakukannya dengan baik lalu mendapat manfaat besar

  • Saat menggunakan futex antarproses (status lintas proses), pendekatan yang bisa dipakai adalah watchdog process membuka Unix domain socket (SOCK_STREAM atau SOCK_SEQPACKET) untuk masing-masing proses guna mendeteksi crash dan membersihkan status per proses

  • Saya juga memang sengaja membatasi pembahasan mutex hanya sampai batas proses karena khawatir diskusinya akan melebar tanpa ujung