SpinLock: While loop (tght spin) is running! Only one thread among many CAS calls will succeed, others will fail.

• CAS -> lock: unfortunate interleaving between the data being modified // compare and swap
• Store() -> unlock

• use backoff to slow down the loop: aggressive try will burn a lot of cpu cycles

• When the spinlock is effective?
  • when you are going to acquire the lock very soon!

    t1 cas’es the data -> t2 trys to cas the data -> fail (loop)

• Downfall
  • CAS is unfair!
  • not fair acquisition of the lock to the thread
  • CPU cacheline bouncing

TicketLock: fairness! - old = FAA(&location, constant) // fetch and add: atomically adding constant, return old value - FAA is guaranteed to succeed: might have some delay, but it will succeed. - Stages - Issue the ticket using FAA instruction (ticket 3, ticket 4, etc.) - lock: when cur’s ticket number equals - unsafe unlock - api misuse: calling unlock with wrong ticket number - fake token: token could be corrupted - What if the thread with lock panicks? - std implements poisoned lock!

• c.f. implementing try_lock for ticketlock? (non-blocking) (cur, next) = (4, 4) -> CAS((4, 4), (4, 5))

• CLHLock : Linked list of critical sections

  reduces the overhead of cacheline bouncing: each thread is waiting for different lock location CS1 -> CS2 -> CS3 append self to the end of the linked list

• lock: insert new node
  • previous node modifies the next node’s locked flag after the previous section ends
  • the lock node is pinned to the critical section
• Implementation
  • tail: AtomicPtr<CachePadded<Node>>
  • let prev = self.tail.swap(node, Ordering::AcqRel); // getting the value and swapping it with node value
  • prev -> newnode