cds/misc/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