proto.lib

Bakery Algorithm - Loại trừ tương hỗ không cần atomic

Mỗi thread lấy một số thứ tự như xếp hàng ở tiệm bánh, chỉ vào critical section khi giữ số nhỏ nhất; giải quyết mutual exclusion mà không cần hardware atomics.

ConcurrencyNâng cao2026-07-07
Bakery Algorithm - Loại trừ tương hỗ không cần atomic

Tags

#mutual-exclusion#bakery-algorithm#lock-free#ticket#lamport

Tài liệu tham khảo

Mở rộng

Animation gốc là một file HTML tự chứa, có thể nhúng lại ở bất kỳ trang nào khác. Mở file gốc

Liên quan

ConcurrencyNâng cao

Double-Word CAS: cập nhật nhiều trường không cần lock

Một con trỏ cùng một bộ đếm phiên bản (version) được đóng gói vào hai word liền kề để một lệnh compare-and-swap rộng (double-word CAS / DWCAS, ví dụ cmpxchg16b) cập nhật đồng thời cả hai — đây là cách version tag đánh bại ABA problem và cách cặp head/tail của hàng đợi giới hạn giữ tính nhất quán.

#double-word-cas#cmpxchg16b#version-counter#tagged-pointer
ConcurrencyNâng cao

Priority Queue đồng thời bằng Skip List (không phải 1 heap)

Một binary heap có một root duy nhất mà mọi thread phải chạm vào, nên priority queue đồng thời thường dùng skip list với insert/delete lock-free bằng CAS ở từng level, hoặc nhiều hàng đợi per-thread kèm work-stealing — đánh đổi để "phần tử nhỏ nhất" chỉ còn là gần đúng dưới tải đồng thời.

#skip-list#priority-queue#lock-free#cas
ConcurrencyNâng cao

Bitmap allocator không lock bằng CAS

Cấp một slot từ một pool dùng chung mà không cần lock: free set là bitmap gồm nhiều word, một thread quét tìm word có bit trống và chiếm bit đó bằng compare-and-swap, thử lại nếu va (collision); mỗi thread bắt đầu quét từ một offset khác nhau (hoặc trong vùng riêng) để tránh tranh chấp cùng word đầu tiên.

#bitmap-allocator#compare-and-swap#lock-free#id-allocation