Compare-and-set — xotiradagi yoki versiyalangan obyektning joriy qiymatini kutilgan qiymat bilan solishtirib, ular teng bo‘lsagina yangi qiymatni atomar yozadigan operatsiyadir. U ko‘pincha CAS qisqartmasi bilan yuritiladi. Operatsiya muvaffaqiyat yoki muvaffaqiyatsizlikni qaytaradi; muvaffaqiyatsizlik boshqa bajaruvchi qiymatni oldin o‘zgartirganini bildirishi mumkin. CAS parallel algoritmlar va optimistic concurrency controlning asosiy primitive laridan biridir.
Ishlash ketma-ketligi
CAS uch argument bilan tasavvur qilinadi: manzil, kutilgan qiymat va yangi qiymat. Mantiqiy ko‘rinishi quyidagicha:
if *address == expected:
*address = desired
return success
else:
return failure
Oddiy if va yozuv orasiga boshqa oqim kirishi mumkin, CAS esa solishtirish va almashtirishni bo‘linmas qiladi. Muvaffaqiyatsiz oqim joriy qiymatni qayta o‘qib, yangi natijani hisoblaydi va qayta urinadi. Shu sikl lock ishlatmasdan atomar hisoblagich yoki pointer yangilashga imkon beradi.
Lock-free algoritmlar
Stack boshidagi pointer yangi tugunga o‘zgartirilayotganda CAS eski bosh hali o‘sha ekanini tekshiradi. Boshqa oqim oldin element qo‘shgan bo‘lsa, operatsiya rad etiladi va algoritm yangi bosh bilan takrorlanadi. To‘g‘ri qurilgan lock-free tizimda bir oqim to‘xtab qolsa ham, boshqa oqimlardan kamida biri oldinga siljiydi.
Bu xususiyat kutish yo‘q degani emas. Yuqori contentionda ko‘plab oqim bir qiymat ustida CAS bajarib, qayta-qayta yutqazishi mumkin. Exponential backoff, ma’lumotni shardlash yoki boshqa algoritm kesh liniyasi talashuvini kamaytiradi. Wait-free kafolat lock-freedan kuchliroq bo‘lib, har oqim cheklangan qadamda tugashini talab qiladi.
ABA muammosi
Oqim A qiymatini o‘qiydi, to‘xtab turadi; boshqa oqim qiymatni Adan Bga, keyin yana Aga aylantiradi. Birinchi oqim CAS qilganda qiymat kutilgan Aga teng va operatsiya muvaffaqiyatli bo‘ladi, lekin obyekt orada o‘zgarganini sezmaydi. Pointer tuzilmalarida eski manzil bo‘shatilib, boshqa obyektga qayta berilgan bo‘lishi mumkin.
Tagged pointer qiymatga versiya hisoblagichini qo‘shadi, shunda qaytgan A boshqa versiyaga ega bo‘ladi. Hazard pointer, epoch-based reclamation va garbage collection xotirani muddatidan oldin qayta ishlatmaslikka yordam beradi. Yechim til, pointer hajmi va xotira boshqaruviga bog‘liq.
Taqsimlangan qo‘llanish
HTTP API If-Match va ETag orqali obyekt versiyasi mos bo‘lsagina yangilashni qabul qilishi mumkin. Ma’lumotlar bazasida UPDATE ... WHERE id=? AND version=? bajarilib, ta’sirlangan satrlar soni tekshiriladi. Bu apparat CAS emas, ammo semantik jihatdan versiyani solishtirib shartli yozishdir.
Taqsimlangan omborda CAS linearizable bo‘lishi uchun konsensus yoki bitta ishonchli yetakchi kabi koordinatsiya talab qilishi mumkin. Faqat lokal replika bilan solishtirish bir vaqtda ikki joyda muvaffaqiyat berishi ehtimolini tug‘diradi. Hujjatda consistency modeli, timeoutdan keyingi noaniq natija va idempotent retry qoidalari ko‘rsatiladi.
Weak va strong CAS
Ayrim APIlar weak compare-exchangega hatto qiymat teng bo‘lsa ham spuriously muvaffaqiyatsiz bo‘lishga ruxsat beradi. U retry siklida apparat primitiveiga yaqin va samarali bo‘lishi mumkin. Strong variant bunday sababsiz rad etishni yashiradi va bir martalik shartli almashuv uchun qulay. Ikkalasi ham haqiqiy raqobat sabab muvaffaqiyatsiz bo‘lishi mumkin; return qiymati tekshirilmasdan yangi holatga erishildi deb bo‘lmaydi.
Memory ordering
CAS pointer qiymatini atomar almashtirsa ham, pointer ko‘rsatgan obyekt maydonlarining boshqa oqimga ko‘rinishi memory orderga bog‘liq. Publisher obyektni tayyorlab release semantikasi bilan nashr etadi, consumer acquire bilan qabul qiladi. Relaxed tartib faqat hisoblagich kabi boshqa xotira invariantiga bog‘lanmagan holatlarda yetarli bo‘lishi mumkin.
Bog‘liq tushunchalar
Atomic operation, Lock-free algorithm, ABA problem, Optimistic concurrency control, ETag, Linearizability, Memory ordering