A shared ticket lock that is fair for readers and writers

Question

I'm writing a very simple, shared ticket lock whose goal is to be fair for both readers and writers in the order they arrive.

• Everyone gets in the same line
• Line-contiguous reader groups get concurrent access
• A writer waits for all readers ahead of it and then gets access
• After a writer unlocks, the next contiguous reader group gets access

// SharedTicketLock.h
#pragma once
#include <atomic>
#include <thread>

class SharedTicketLock {
    std::atomic<uint16_t> next_ticket{0};
    std::atomic<uint16_t> now_serving{0};
    std::atomic<uint16_t> served{0};

public:
    void writer_lock(){
        uint16_t my_ticket = next_ticket.fetch_add(2);
        while (now_serving.load() != my_ticket || now_serving.load() != served.load()){
            std::this_thread::yield();
        }
    }

    void reader_lock(){
        uint16_t my_ticket = next_ticket.fetch_add(1);
        while (now_serving.load() != my_ticket){
            std::this_thread::yield();
        }
        now_serving.fetch_add(1);
    }

    void writer_unlock(){
        now_serving.fetch_add(2);
        served.fetch_add(2);
    }

    void reader_unlock(){
        served.fetch_add(1);
    }
};

• We add an additional atomic counter to the traditional ticket lock: served to track the number of readers in the critical section.
• Writers take out two tickets: next_ticket.fetch_add(2), while readers take out just one.
• Readers enter when now_serving equals my_ticket.
• Writers enter when now_serving equals my_ticket as well as when now_serving equals served, indicating all previous entrants have left the critical section.
• When a reader locks, it immediately increments now_serving, which in this implementation is used to determine the in-flight readers and signals to the next entrant that if they are a reader, they may enter. If the next entrant is a writer, it must wait for now_serving and served to be equal.
• When a writer locks, it does not increment now_serving, creating a two-ticket gap between the entrant after the writer and causing everyone to wait.
• When a reader unlocks, it increments served, which is used by writers to know when all readers before its ticket count have left.
• When a writer unlocks, it double increments both next_ticket and now_serving, signaling to the next entrant that a writer has left the critical section and they may now enter.
• If the next entrants are readers, they will all enter as each one increments now_serving and checks for a 1 ticket gap.
• Ticket overflow is handled implicity as only equality checks are made.

Is my reasoning sound on this?

Answer 1

Why skip tickets?

I don't see why writers need to take two tickets. You only need one, and the write can block subsequent readers and writers by just not incrementing now_serving in writer_lock(), which is already what you are doing.

It is inefficient

There is no guarantee what the order is in which threads yield a processor core to each other. In fact, there is no guarantee that the operating system will yield in a round-robin way, so several threads might be stuck in a busy-loop while the thread that's next in line to call now_serving.fetch_add(1) is not being scheduled. There is also a possibility that you yield to a process that is not involved with the locks, but is getting a long time slice. This all means that even if there are only readers, it might take a long time before reader_lock() returns.

Like spin locks, ticket locks work best if you can guarantee there is only one thread per core trying to take a lock. Even then, I would only use them if fairness is really important.

Use std::size_t for the ticket numbers

While it is unlikely you will have more than \$2^{16}\$ threads, consider that someone someday might use your ticket lock with that many, or that an attacker might find a way to cause that many threads to be spawned. In that case, the ticket numbers will wrap, and things might then proceed in the wrong order. To be on the safe side, just use std::size_t. That will still make SharedTicketLock fit within a single cache line on almost any contemporary CPU, so it will likely have little to no impact on performance.

Think about alignment

Make sure that either all atomic variables are on the same cache line, or that they each are on a different cache line. The former reduces the number of cache lines needed to be kept in sync, the latter allows a thread to modify one variable while another accesses another variable, without the cores themselves being blocked waiting for exclusive access to those cache lines.

Use the alignas() specifier along with std::hardware_destructive_interference_size on each atomic variable, or use alignas() and std::hardware_constructive_interference_size on the whole class.

It is not lock-free

You tagged the question lock-free, implying that you think your code is lock-free. However, it is not. Of course, you are implementing a ticket lock, so that is already a hint, but even if there are no writers, consider that one reader thread might be destroyed or suspended in reader_lock() right before it calls now_serving.fetch_add(1). This causes any other reader thread that calls reader_lock() to block, halting system-wide progress.