Refactors misc test cases

[libcds.git] / cds / sync / ticket_lock.h

diff --git a/cds/sync/ticket_lock.h b/cds/sync/ticket_lock.h
new file mode 100644 (file)
index 0000000..233b440
--- /dev/null
+++ b/cds/sync/ticket_lock.h
@@ -0,0 +1,51 @@
+#ifndef _TICKET_LOCK_H
+#define _TICKET_LOCK_H
+
+#include "backoff.h"
+#include <atomic>
+
+namespace cds_others {
+
+class TicketLock {
+  /**
+     This ticket lock implementation is derived from the original Mellor-Crummey
+     & Scott paper <Algorithms for Scalable Synchronization on SharedMemory
+     Multiprocessors> in 1991. It assumes that the ticket and turn counter are
+     large enough to accommodate the maximum number of simultaneous requests for
+     the lock.
+  */
+public:
+  TicketLock() {
+    ticket.store(0, std::memory_order_relaxed);
+    turn.store(0, std::memory_order_relaxed);
+  }
+
+  void lock() {
+    // First grab a ticket
+    unsigned my_ticket = ticket.fetch_add(1, std::memory_order_relaxed);
+    // Spinning for my turn
+    ExpBackoff backoff;
+    while (true) {
+      unsigned my_turn = turn.load(std::memory_order_acquire);
+      if (my_turn == my_ticket) {
+        // Now it's my turn
+        return;
+      } else {
+        backoff();
+      }
+    }
+  }
+
+  void unlock() {
+    unsigned my_turn = turn.load(std::memory_order_relaxed);
+    turn.store(my_turn + 1, std::memory_order_release);
+  }
+
+private:
+  std::atomic_uint ticket;
+  std::atomic_uint turn;
+};
+
+} // namespace cds_others
+
+#endif