Queue Lock — lock olishni kutayotgan threadlarni mantiqiy navbatga joylab, ownershipni tartibli va kamroq cache contention bilan uzatadigan synchronization primitive. MCS va CLH locklar mashhur queue-lock algoritmlaridir.
Navbat modeli
Oddiy test-and-set lockda barcha waiter bitta cache line’ni aylantiradi. Queue lockda har thread o‘z node’i yoki predecessor holatida spin qiladi; unlock faqat navbatdagi successorni uyg‘otadi.
MCS mexanizmi
MCS lock atomic swap bilan node’ni tailga qo‘shadi. Oldingi node successor linkini oladi, waiter esa o‘z locked flagida kutadi. Unlock successor ko‘rinmagan race’da tailni CAS bilan bo‘shatadi yoki linkni kutadi.
CLH va topology
CLH lock waiterga predecessor node’ni beradi va u predecessor holatida spin qiladi. NUMA tizimda MCSning local node spinningi qulayroq bo‘lishi mumkin. Aniq performance topology va memory modelga bog‘liq.
Fairness
Queue lock odatda FIFOga yaqin fairness beradi va starvationni kamaytiradi. Biroq owner preempt qilinsa navbatning qolgan qismi kutadi. Priority-aware tizimda priority inversion alohida boshqariladi.
Bekor qilish
Cancellation va timeout queue’dan o‘rta node’ni olib tashlashni murakkablashtiradi. Ko‘p implementatsiya oddiy non-cancellable critical section yoki qo‘shimcha state machine ishlatadi.
Tekshiruv
Sinov mutual exclusion, FIFO handoff, high contention, owner preemption, NUMA va memory-order visibilityni qamraydi. Cache-line transfer va p99 wait time o‘lchanadi.
Amaliy nazorat
Queue Lock bilan ishlaydigan tizim per-waiter node va atomic tailni aniq lifecycle va version bilan yuritadi. Pointer, mapping, navbat yoki exception holati boshqa qatlamga uzatilganda ownership hamda permission shartlari yo‘qolmaydi. Debug rejimda manzil, obyekt identifikatori va state transition qayd etiladi; production log ASLR, maxfiy ma’lumot va raw pointerlarni ochib yubormaydigan shaklga keltiriladi. Eskirgan handle yoki metadata reuse qilinmasligi uchun generation, build-id yoxud reference hisobidan foydalaniladi.
Muhim xavf — navbat linki yo‘qolishi yoki weak memory ordering. Bunday vaziyatda tizim taxmin bilan davom etmaydi: access fault, aniq error, konservativ fallback yoki nazoratli cleanup qo‘llanadi. Signal/fault kelgan nuqta har doim asl buzilish joyi emas; allocation, mapping va oxirgi ownership amallari trace’i tashxisga yordam beradi. Parallel accessda lock, atomic ordering va lifetime birgalikda tekshiriladi. Timeout yoki null check memory safetyning o‘rnini bosa olmaydi.
Sifat nazorati FIFO handoff va contention benchmark orqali bajariladi. Sinovlar normal holat bilan birga nol uzunlik, page boundary, alignment, juda katta offset, concurrent close/free, permission o‘zgarishi va platforma farqlarini qamraydi. Correctness avval etalon hamda invariant bilan tekshiriladi, keyin page fault, cache miss, contention, latency yoki xotira sarfi o‘lchanadi. Sanitizer, fault injection va malformed-input fuzzing topgan minimal holat doimiy regressiya testiga aylantiriladi.
MCS lockda har kutuvchi o‘z node’iga spin qiladi, shu bois bitta global cache line ustidagi trafik kamayadi. Unlock amali voris hali linklanmagan bo‘lsa tailni compare-and-swap bilan bo‘shatishga urinadi; bu muvaffaqiyatsiz bo‘lsa voris ko‘rinishini kutadi. Ana shu oraliq noto‘g‘ri ishlansa wakeup yo‘qolishi mumkin. Benchmark faqat throughputni emas, kutish vaqtining taqsimoti, cache-coherence hodisalari va egasi deschedule bo‘lgandagi convoy ta’sirini ham ko‘rsatishi kerak. Queue lock qisqa kritik bo‘lim va yuqori contentionda foydali, ammo past contentionda oddiy mutexdan qimmatroq bo‘lishi mumkin.
Bog‘liq tushunchalar
MCS lock, CLH lock, spinlock, mutual exclusion, fairness, atomic operation