Refactors misc test cases
[libcds.git] / cds / sync / ticket_lock.h
1 #ifndef _TICKET_LOCK_H
2 #define _TICKET_LOCK_H
3
4 #include "backoff.h"
5 #include <atomic>
6
7 namespace cds_others {
8
9 class TicketLock {
10   /**
11      This ticket lock implementation is derived from the original Mellor-Crummey
12      & Scott paper <Algorithms for Scalable Synchronization on SharedMemory
13      Multiprocessors> in 1991. It assumes that the ticket and turn counter are
14      large enough to accommodate the maximum number of simultaneous requests for
15      the lock.
16   */
17 public:
18   TicketLock() {
19     ticket.store(0, std::memory_order_relaxed);
20     turn.store(0, std::memory_order_relaxed);
21   }
22
23   void lock() {
24     // First grab a ticket
25     unsigned my_ticket = ticket.fetch_add(1, std::memory_order_relaxed);
26     // Spinning for my turn
27     ExpBackoff backoff;
28     while (true) {
29       unsigned my_turn = turn.load(std::memory_order_acquire);
30       if (my_turn == my_ticket) {
31         // Now it's my turn
32         return;
33       } else {
34         backoff();
35       }
36     }
37   }
38
39   void unlock() {
40     unsigned my_turn = turn.load(std::memory_order_relaxed);
41     turn.store(my_turn + 1, std::memory_order_release);
42   }
43
44 private:
45   std::atomic_uint ticket;
46   std::atomic_uint turn;
47 };
48
49 } // namespace cds_others
50
51 #endif