CODEWITHSUNDEEP
concurrencysynchronizationterminology
sema
sema

Reputation: 532

Is a ticket lock bounded wait-free? (under certain assumptions)

I am talking about a ticket lock that might look as follows (in pseudo-C syntax):

    unsigned int ticket_counter = 0, lock_counter = 0;

void lock() {
    unsigned int my_ticket = fetch_and_increment(ticket_counter);

    while (my_ticket != lock_counter) {}
}

void unlock() {
    atomic_increment(lock_counter);
}

Let's assume such a ticket lock synchronizes access to a critical section S that is wait-free, i.e. executing the critical section takes exactly c cycles/instructions. Assuming, that there are at most p threads in the system, is the synchronization of S using the ticket lock bounded wait-free?

In my opinion, it is, since the ticket lock is fair and thus the upper bound for waiting is O(p * c).

Do I make a mistake? I am little bit confused. I always thought locking implies not to be (bounded) wait-free because of the following statement: "It is impossible to construct a wait-free implementation of a queue, stack, priority queue, set, or list from a set of atomic register." (Corollary 5.4.1 in Art of Multiprocessor Programming, Herlihy and Shavit)

However, if the ticket lock (and maybe any other fair locking mechanism) is bounded wait-free under the mentioned assumptions, it (might) enables the construction of bounded wait-free implementations of queue, stack, etc. (That's the question I am actually faced with.)

Recall the definition of bounded wait-free in "Art of Multiprocessor Programming", p.59 by Herlihy and Shavit:

"A method is wait-free if it guarantees that every call finishes its execution in a finite number of steps. It is bounded wait-free if there is a bound on the number of steps a method call can take."

Upvotes: 3

Views: 602

Answers (1)

janneb
janneb

Reputation: 37228

Well, I believe you are correct, with some caveats.

Namely, the bounded wait-free property holds only if the critical section S is non-preemptive, which I suppose you can guarantee only for kernel space code (by disabling interrupts in the critical section). Otherwise the OS might decide to switch to another thread while one thread is in the critical section, and then the wait time is unbounded, no?

Also, for kernel code, I suppose p is not the number of software threads but rather the number of hardware threads (or cores, for CPU's that don't support several threads per CPU core). Because at most p software threads will be runnable at a time, and as S is non-preemptive you have no sleeping threads waiting on the lock.

Upvotes: 1

Related Questions