Sequence counter dapat memungkinkan reader menyalin shared state tanpa mengambil lock milik writer. Reader mengambil nilai counter, menyalin field yang dilindungi, lalu mengambil nilai counter sekali lagi. Nilai genap yang sama pada kedua observasi menandakan tidak ada writer yang overlap dengan proses penyalinan berdasarkan kontrak sinkronisasi. Nilai yang berubah atau ganjil memaksa reader membuang snapshot dan mengulang operasi.

Pola ini memindahkan pekerjaan dari kepemilikan lock pada sisi reader, tetapi tidak menghapus sinkronisasi. Writer tetap memerlukan serialisasi, transisi counter memerlukan semantik memory ordering yang terdefinisi, dan data yang dilindungi harus tetap aman diakses selama write yang overlap. Constraint tersebut membuat sequence counter cocok untuk sebagian snapshot yang dominan dibaca, tetapi tidak aman untuk data yang lifetime-nya dapat berakhir saat reader masih mengaksesnya.

Counter menandai aktivitas writer, bukan kepemilikan objek

Protokol yang umum memakai nilai sequence berupa integer. Writer mengubah nilai dari genap menjadi ganjil sebelum memutasi state yang dilindungi, lalu memajukannya ke nilai genap berikutnya setelah mutasi selesai.

Reader menerima snapshot hanya ketika observasi awal dan akhir sama serta bernilai genap:

repeat:
    a = sequence
    if a is odd:
        retry

    local_x = shared_x
    local_y = shared_y

    b = sequence
until a == b and b is even

Counter tidak memberikan akses eksklusif kepada reader. Writer dapat berjalan ketika reader menyalin shared_x dan shared_y. Tahap validasi mendeteksi overlap tersebut dan mencegah snapshot campuran digunakan.

Perbedaan itu memisahkan sequence counter dari reader-writer lock. Read lock mencegah writer yang mengikuti kontrak memasuki critical section. Sequence counter mengizinkan overlap dan membuat reader bertanggung jawab menolak salinan yang mungkin tidak konsisten.

Serialisasi writer merupakan bagian dari protokol

Encoding ganjil/genap mengasumsikan satu writer memiliki interval mutasi pada satu waktu. Jika dua writer secara independen mengubah counter dan field yang dilindungi, nilai sequence tidak lagi menyediakan batas sederhana di sekitar satu mutasi yang koheren.

Desain praktis karena itu menserialisasi writer memakai lock atau mekanisme lain. Sequence counter kemudian menggambarkan state dari write section yang telah diserialisasi tersebut kepada reader tanpa lock.

Secara konseptual:

writer lock acquired
sequence becomes odd
mutate protected fields
sequence becomes even
writer lock released

Operasi ordering yang tepat tidak dapat disimpulkan dari pseudocode ini. Bahasa, runtime, library, atau primitive kernel harus mendefinisikan atomic access dan barrier yang diperlukan. Load dan store integer biasa bukan pengganti yang portabel ketika bahasa pemrograman mengizinkan data race menghasilkan undefined behavior atau ketika hardware memory model dapat mengekspos operasi dalam urutan yang melanggar protokol.

Memory ordering menghubungkan validasi dengan field yang disalin

Dua pembacaan counter yang sama hanya berguna jika memory model mengikat keduanya dengan akses data di antaranya. Reader tidak boleh mengobservasi nilai counter akhir dengan cara yang membiarkan akses field terlindungi keluar dari interval validasi yang dimaksud. Writer juga memerlukan ordering yang menempatkan mutasi state di antara transisi yang menandai write aktif dan write selesai.

Implementasi menangani kebutuhan ini melalui barrier khusus primitive atau aturan atomic ordering. API sequence count Linux, misalnya, menyediakan operasi dengan kebutuhan ordering yang didefinisikan kernel alih-alih meminta pemanggil merakit protokol dari load dan store sembarang.

Pada level bahasa, aturannya dapat lebih ketat. Dalam C atau C++, pembacaan dan penulisan konkuren terhadap objek non-atomic tanpa relasi sinkronisasi yang valid dapat menjadi data race dengan undefined behavior. Algoritma yang menyerupai sequence counter kernel karena itu tidak otomatis valid pada C++ user space hanya karena machine instruction yang dihasilkan tampak masuk akal pada satu prosesor.

Implementasi harus memenuhi kedua lapisan: language memory model dan kontrak sinkronisasi target.

Retry mengganti blocking dengan pekerjaan yang dapat berulang

Reader biasanya tidak menunggu sambil memegang read section milik sequence counter. Jika reader melihat nilai ganjil atau mendeteksi perubahan nilai setelah menyalin data, operasi diulang.

Sifat tersebut mencegah reader secara langsung memblokir writer melalui kepemilikan reader lock. Konsekuensinya, penyelesaian reader bergantung pada aktivitas writer. Saat write berlangsung terus-menerus, reader dapat membuang beberapa snapshot sebelum memperoleh satu snapshot stabil.

Ini merupakan pertukaran sifat progress, bukan konkurensi tanpa biaya. Reader-writer lock dapat mengantrekan partisipan dan menerapkan kebijakan lock. Reader sequence counter justru melakukan pekerjaan spekulatif yang hasilnya dapat dibatalkan. Biayanya bergantung pada ukuran snapshot, frekuensi write, scheduling, dan perilaku retry dari implementasi.

Critical section writer yang panjang memiliki dampak khusus. Nilai sequence ganjil memberi tanda bahwa state terlindungi sedang dalam transisi, sehingga reader dapat melakukan spin atau retry sampai writer memublikasikan nilai genap. Kode dengan pola ini perlu memperhitungkan konteks scheduling yang dapat menunda writer setelah sequence ditandai ganjil.

Lifetime pointer merupakan hazard terpisah

Mendeteksi mutasi konkuren tidak membuat memory access yang tidak aman menjadi aman. Misalnya, sebuah field terlindungi berisi pointer. Reader dapat menyalin pointer tersebut, lalu writer menghapus dan membebaskan objek yang dirujuk sebelum reader memvalidasi nilai sequence.

Reader pada akhirnya mungkin mendeteksi perubahan counter, tetapi dereference terhadap storage yang sudah dibebaskan sebelum validasi telah menjadi operasi yang tidak valid. Retry tidak dapat membatalkan akses yang sudah terjadi.

Kondisi ini membentuk batas ketat untuk state yang cocok dilindungi. Sequence counter sesuai secara natural untuk nilai yang tetap addressable selama reader menyalinnya: counter, timestamp, tuple koordinat, scalar konfigurasi, dan field in-place lain merupakan bentuk yang umum. Struktur yang kaya pointer memerlukan mekanisme lifetime terpisah jika objek dapat direklamasi secara konkuren.

Reference counting, hazard pointer, epoch-based reclamation, skema bergaya RCU, atau lock dapat memberikan jaminan lifetime pada desain yang sesuai. Sequence counter masih dapat memvalidasi konsistensi logis, tetapi tidak dapat menggantikan memory reclamation.

Snapshot koheren dapat mencakup beberapa field

Properti yang berguna tidak terbatas pada satu scalar. Pertimbangkan state yang memuat timestamp dasar dan conversion factor yang harus berasal dari update yang sama. Membaca setiap field secara independen dapat menggabungkan nilai dari generasi writer yang berbeda.

Pembacaan dengan sequence counter memperlakukan grup tersebut sebagai satu snapshot optimistis:

s0 = begin_read()
base = state.base
scale = state.scale
offset = state.offset
retry = read_changed(s0)

Jika retry bernilai false sesuai kontrak primitive, field yang disalin berasal dari interval observasi tanpa write. Jika writer overlap dengan proses penyalinan, reader membuang ketiga nilai sekaligus.

Hal ini membuat invariant yang dilindungi menjadi eksplisit. Batas sinkronisasi adalah relasi antar-field, bukan sekadar atomic access pada setiap field secara individual. Menjadikan setiap scalar atomic dapat mencegah akses scalar yang torn, tetapi masih dapat mengizinkan kombinasi nilai yang tidak pernah ada sebagai satu logical state.

Wraparound memberi batas pada argumen validasi

Nilai sequence memiliki lebar terbatas. Setelah cukup banyak transisi writer, counter dapat wrap dan pada akhirnya mengulangi nilai sebelumnya. Implementasi karena itu bergantung pada kondisi yang mencegah satu reader melintasi cukup banyak write yang selesai hingga counter kembali ke nilai observasi yang sama dalam satu percobaan read.

Batas tepatnya bergantung pada lebar counter dan semantik primitive. Kondisi ini menjadi alasan lain untuk memakai abstraksi sequence count yang terdefinisi, bukan memperlakukan kesamaan dua integer sembarang sebagai bukti konkurensi yang universal.

Untuk read section yang singkat dan counter dengan ukuran memadai, implementasi dapat membuat kondisi tersebut praktis. Kondisi itu tetap merupakan prasyarat, bukan sifat matematis dari counter berhingga.

Batas validasi menentukan state yang dapat dipercaya reader

Sequence counter paling presisi jika diperlakukan sebagai mekanisme validasi snapshot. Mekanisme ini menyatakan bahwa reader hanya boleh memakai state yang telah disalin setelah membuktikan, sesuai aturan ordering primitive, bahwa tidak ada writer terserialisasi yang overlap dengan proses penyalinan.

Sequence counter tidak menserialisasi writer, mempertahankan lifetime objek, membuat akses data race pada level bahasa menjadi legal, atau menjamin jumlah percobaan reader yang tetap. Setiap properti tersebut memerlukan bagian desain lain.

Pemisahan itu merupakan nilai rekayasa utama dari pola ini. Writer exclusion, memory ordering, konsistensi snapshot, progress, dan reclamation tetap menjadi kontrak yang berbeda. Sequence counter menangani satu kontrak dengan baik: mendeteksi bahwa pembacaan spekulatif melintasi batas mutasi.

Rekayasa Perangkat Lunak Konkurensi Sinkronisasi Memory Ordering