Menghapus node dari struktur data lock-free tidak membuat memorinya langsung aman untuk digunakan kembali. Thread lain mungkin sudah memegang alamat node tersebut dan masih akan mengaksesnya. Jika thread penghapus membebaskan alokasi terlalu cepat, pembaruan atomik yang benar dapat diikuti use-after-free.

Hazard pointer memisahkan penghapusan logis dari reklamasi fisik. Reader memublikasikan alamat yang hendak diakses ke hazard slot yang ditentukan. Thread lain dapat melepas node dari struktur dan menaruhnya pada retired list, tetapi reklamasi menunggu sampai pemindaian memastikan tidak ada hazard slot yang melindungi alamat itu.

Protokol ini menangani masa hidup memori. Ia tidak menggantikan aturan atomik yang menjaga kebenaran struktur data itu sendiri.

Pointer dapat tetap dipakai setelah keluar dari struktur

Bayangkan stack lock-free dengan head berupa pointer atomik. Reader dapat memulai operasi pop seperti berikut:

p = head.load()
next = p.next

Load pada head dan pembacaan p.next merupakan dua operasi terpisah. Di antara keduanya, thread lain dapat menghapus p. Jika penghapusan sekaligus membebaskan p, operasi kedua dapat mengakses storage yang masa hidupnya sudah berakhir.

Menyimpan seluruh node yang sudah dilepas selamanya memang menghindari fault langsung, tetapi hanya menukar masalah safety dengan kebocoran memori tanpa batas. Skema reklamasi memerlukan kondisi yang menyatakan bahwa tidak ada reader aktif yang masih dapat memakai objek retired.

Hazard pointer menyediakan kondisi tersebut melalui publikasi eksplisit.

Publikasi memerlukan loop validasi

Memublikasikan hazard setelah membaca shared pointer belum cukup. Node dapat dilepas di antara load awal dan publikasi. Karena itu, pola akuisisi lazim memublikasikan alamat lalu memvalidasinya:

repeat:
    p = head.load(acquire)
    hazard.store(p, seq_cst_or_required_order)
until p == head.load(acquire)

if p != null:
    next = p.next

Memory order yang tepat bergantung pada algoritma dan implementasi. Inti protokolnya tetap sama: ambil kandidat, publikasikan, lalu pastikan sumber bersama masih menunjuk kandidat yang sama sebelum mengakses field yang memerlukan perlindungan.

Jika validasi gagal, reader mengulang dengan nilai baru. Thread yang sudah me-retire node lama harus memperhitungkan hazard yang terpublikasi sebelum melakukan reklamasi.

Hazard slot dikosongkan ketika reader tidak lagi membutuhkan objek tersebut:

hazard.store(null, required_order)

Mengosongkannya terlalu awal membuka kembali celah masa hidup. Membiarkannya terisi terlalu lama tetap aman bagi reader itu, tetapi dapat menunda reklamasi.

Retirement berbeda dari reklamasi

Compare-and-swap yang berhasil dapat melepaskan node dari struktur:

if CAS(head, p, next):
    retire(p)

retire(p) tidak boleh diperlakukan sebagai free(p). Node retired tetap dialokasikan selama alamatnya mungkin muncul di hazard slot mana pun.

Implementasi umumnya mengumpulkan node retired lalu memindai hazard record secara batch. Secara konseptual, pemindaian membentuk kumpulan alamat terlindungi dan mereklamasi node retired yang tidak ada di kumpulan tersebut:

protected = snapshot_all_hazards()

for node in retired:
    if node.address not in protected:
        reclaim(node)
    else:
        keep_retired(node)

Batching mengamortisasi biaya pemindaian. Konsekuensinya, pemakaian memori sementara dapat lebih besar daripada jumlah node yang saat itu masih dapat dijangkau dari struktur data.

Hazard record merupakan bagian dari protokol

Setiap thread atau operasi yang berpartisipasi memerlukan akses ke hazard record yang masa hidupnya juga dikelola dengan aman. Record tidak boleh hilang ketika peserta lain masih mungkin memindainya.

Sistem dapat memakai sekumpulan slot per-thread yang dibatasi, registry yang dapat digunakan kembali, atau skema pengelolaan record stabil lainnya. Pilihan tersebut memengaruhi biaya registrasi, jumlah perlindungan serentak, dan cleanup ketika thread berakhir.

Beberapa objek yang harus dilindungi pada saat bersamaan memerlukan beberapa slot atau protokol traversal yang berbeda. Traversal linked structure, misalnya, dapat perlu melindungi node saat ini dan successor selama perpindahan perlindungan. Algoritma harus menetapkan referensi mana yang dilindungi pada setiap batas dereference.

API hazard pointer yang menyembunyikan batasan ini di balik tipe pointer biasa dapat mempermudah kesalahan pemakaian. Publikasi, validasi, kepemilikan slot, dan pelepasan tetap merupakan operasi semantik walaupun library membungkusnya dengan abstraksi yang lebih aman.

Pemindaian reklamasi memerlukan aturan safety yang koheren

Scanner tidak harus memperoleh snapshot global atomik dari seluruh hazard slot dalam arti biasa. Namun, aturan memory ordering harus mencegah node direklamasi ketika reader secara sah masih dapat melanjutkan akses dengan node tersebut terlindungi.

Jaminan itu berasal dari protokol lengkap: publikasi dan validasi oleh reader, retirement oleh remover, observasi oleh scanner, serta ordering constraint yang menghubungkan langkah-langkah tersebut. Memilih operasi relaxed secara terpisah hanya karena setiap field bersifat atomik dapat merusak relasi yang dibutuhkan.

Memory order yang tepat berbeda menurut platform, memory model bahasa, dan algoritma hazard pointer yang digunakan. Implementasi sebaiknya mengikuti protokol yang sudah memiliki dasar pembuktian, bukan menebak ordering dari intuisi terhadap prosesor tertentu.

Batas ini juga berlaku pada pengujian. Stress test dapat menampakkan race, tetapi keberhasilan stress test tidak membuktikan kebenaran memory ordering.

Penggunaan ulang alamat membuat pointer stale berbahaya

Allocator dapat memakai kembali alamat yang sudah direklamasi untuk objek lain. Raw pointer yang stale kemudian dapat memiliki nilai numerik yang sama dengan alamat valid, padahal menunjuk lifetime yang berbeda.

Kondisi ini berkaitan dengan kegagalan bergaya ABA, tetapi keduanya bukan persoalan yang sama. Versioned pointer dapat membedakan sebagian transisi state tanpa membuat objek aman untuk diakses. Hazard pointer dapat mempertahankan alokasi yang terlindungi tetap hidup tanpa otomatis membuktikan seluruh invarian compare-and-swap pada algoritma di sekitarnya.

Desain lock-free dapat membutuhkan protokol reklamasi sekaligus pertahanan terpisah terhadap ambiguitas riwayat state.

Progress perlu mencakup kerja reklamasi

Container lock-free dapat memiliki operasi update non-blocking sementara reklamasi menambahkan kerja bersama. Pemindaian hazard record memerlukan waktu yang bergantung pada jumlah record relevan, dan retired list memakai memori sampai proses pemindaian berjalan.

Hal itu tidak otomatis membatalkan klaim lock-free untuk operasi struktur data, tetapi istilah progress perlu menyatakan bagian mana yang dicakup. Registrasi, alokasi, reklamasi, dan perilaku allocator dapat memiliki progress property yang berbeda dari loop compare-and-swap utama.

Batas operasional juga penting. Thread yang berhenti sambil membiarkan hazard tetap terpublikasi dapat menahan node retired tertentu dari reklamasi. Kondisi ini biasanya tidak menghentikan update lock-free yang tidak terkait, tetapi memori tertahan dapat bertambah jika objek terlindungi atau peserta yang berhenti terus terakumulasi.

Reklamasi aman adalah batas kepemilikan

Hazard pointer memberi jaminan yang sempit: node yang dipilih untuk reklamasi tidak sedang dilindungi reader yang berpartisipasi sesuai protokol. Jaminan itu bergantung pada setiap jalur dereference yang memublikasikan perlindungan dengan benar dan setiap jalur reklamasi yang memeriksa domain perlindungan yang sama.

Hazard pointer tidak membuat akses pointer sembarang menjadi aman, tidak memperbaiki sinkronisasi yang hilang, dan tidak membuktikan kebenaran transisi logis struktur data. Perannya spesifik: menjembatani interval antara pelepasan objek dari shared reachability dan berakhirnya masa hidup storage objek.

Dalam kode lock-free, interval tersebut merupakan bagian dari algoritma, bukan pekerjaan cleanup setelahnya.

Rekayasa Perangkat Lunak Concurrency Algoritma Lock-Free Reklamasi Memori