Serializing tokens

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (November 2014) (Learn how and when to remove this message) This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: "Serializing tokens" – news · newspapers · books · scholar · JSTOR (November 2014) (Learn how and when to remove this message) (Learn how and when to remove this message)

In computer science, serializing tokens are a concept in concurrency control arising from the ongoing development of DragonFly BSD. According to Matthew Dillon, they are most akin to SPLs, except a token works across multiple CPUs while SPLs only work within a single CPU's domain.

Serializing tokens allow programmers to write multiprocessor-safe code without themselves or the lower level subsystems needing to be aware of every single entity that may also be holding the same token.

Tokens and mutual exclusion (mutex) mechanisms are locks. Unlike mutexes, tokens do not exclude other threads from accessing the resource while they are blocked or asleep. A thread sharing resources with other threads can be stopped and started for a variety of reasons:

1. Timeslicing: the user space (US) scheduler tries to ensure that all threads get a fair chance to run, so it runs each thread for a brief period of time (a timeslice) and then switches to another thread.
2. Concurrent execution: in multiprocessor computers, a thread may be run at exactly the same time as another thread on a different CPU.
3. Preemption: a thread may preempt a lower-priority thread, such as a hardware interrupt or Light Weight Kernel Threads.
4. Voluntary blocking: a thread may sleep if it has to wait for something, has no work to do, or calls a function that blocks. Even the call to acquire a lock can block.

The following table summarizes the properties of tokens and mutexes.

Issues such as deadlock and priority inversion can be very difficult to avoid, and require coordination at many levels of the kernel. Because locking with tokens does not deadlock and acquired tokens need not be atomic when later operations block, it allow much simpler code than mutexes.

... If you look at FreeBSD-5, you will notice that FreeBSD-5 passes held mutexes down the subroutine stack quite often, in order to allow some very deep procedural level to temporarily release a mutex in order to switch or block or deal with a deadlock. There is a great deal of code pollution in FreeBSD-5 because of this (where some procedures must be given knowledge of the mutexes held by other unrelated procedures in order to function properly).

— Matthew Dillon

The following pseudocode and explanations illustrate how serializing tokens work.

lwkt_gettoken(T1);
iter = list1.head;

...
lwkt_gettoken(T1); // blocks
// waiting for token T1

lwkt_gettoken(T2); // blocks

// waiting for token T1

// waiting for T1 and T2

list1.head = list1.head.next;
lwkt_releasetoken(T1);

// get the new version of the head:
iter = list1.head; 
// make new list:
while (iter != null) {
    list2.tail = iter;
    iter = iter.next;
}
lwkt_releasetoken(T1);
lwkt_releasetoken(T2);

Mac OS X's Darwin kernel uses a similar technique (called a funnel) to serialize access to the BSD portion of the kernel.

• Lock-free and wait-free algorithms

• A mailing list thread where Matthew Dillon explains tokens in great detail Archived 2017-02-05 at the Wayback Machine
• Darwin Threading Architectures