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:
The following table summarizes the properties of tokens and mutexes.
| Serializing tokens | Mutexes | ||
|---|---|---|---|
| Timeslicing | Works | Works | |
| Concurrent execution | Works | Works | |
| Preemption | Works | Works | |
| Voluntary blocking | Fails | Works | |
| Avoids deadlock | Yes | No | |
| Avoids priority inversion | Yes | No |
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.
The following pseudocode and explanations illustrate how serializing tokens work.
| Thread A | Thread B | Action | |
|---|---|---|---|
lwkt_gettoken(T1); iter = list1.head; | ... lwkt_gettoken(T1); // blocks // waiting for token T1 | A acquires token T1 and uses it to get synchronized access to list1, which is shared by both threads. | |
lwkt_gettoken(T2); // blocks | // waiting for token T1 | A's call to lwkt_gettoken(T2) is a blocking function, so A goes to sleep and temporarily loses its tokens. It will be awakened when the scheduler sees that both T1 and T2 are available. | |
// waiting for T1 and T2 | list1.head = list1.head.next; lwkt_releasetoken(T1); | B acquires T1 and modifies list1. Note that A's "iter" still points to the old head of the list. | |
// 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);
| The scheduler sees that both T1 and T2 are available, so it wakes up thread A. Since A was coded correctly, it refreshes its iterator with the new head of list1, and does some nonblocking operations on it. Note that it would have been better form for A to simply ask for both tokens at the start. |
Mac OS X's Darwin kernel uses a similar technique (called a funnel) to serialize access to the BSD portion of the kernel.