Serializing tokens

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 vs. Mutexes[edit]

Tokens are similar to mutexes in that they can, if used correctly, prevent multiple threads from accessing a shared resource at the same time. Unlike mutexes, however, they do NOT exclude other threads from accessing the resource while they are blocked or asleep. In general terms, they're both locks: your thread gets a lock (which prevents other threads from having it), does some work, and then releases it for another thread to use.

It's important here to recall how threads interact with each other when sharing resources. There are a number of ways that a thread can be stopped and another thread to be started:

  1. Timeslicing: the 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, your thread may also be run at exactly the same time as another thread on a different CPU.
  3. Preemption: A thread may be preempted by a higher priority thread, such as a hardware interrupt or LWKT.
  4. Voluntary Blocking: A thread may voluntarily block (aka "go to sleep") if it has to wait for something, has no work to do, or calls a function that blocks-- note that even the call to acquire a lock can block.

Remember: the purpose of a lock is to keep other threads out while your thread is working on something. This table summarizes the situations in which tokens and mutexes work correctly to keep other threads "out".

Serializing Tokens vs Mutexes
  Serializing Tokens Mutexes
Timeslicing Works Works
Concurrent Execution Works Works
Preemption Works Works
Voluntary Blocking FAILS Works

So what's the big deal? It seems like mutexes are the clear winner-- and in some cases it's important to be able to block and keep a lock. However, they also cause problems such as Deadlocks and Priority inversions. Dealing with these issues is very difficult and requires coordination at many different levels of the kernel:

In fact, the fact that tokens do not deadlock coupled with the fact that there is no expectation of atomicity for earlier acquired tokens when later operations block leads to a great deal of code simplification. 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

Serializing Tokens In Action[edit]

To show how serializing tokens actually work, let's see some pseudocode and what's going on behind the scenes.

Example PseudoCode using Serializing Tokens
Thread A Thread B Behind the Scenes
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.

Prior art in the Darwin kernel[edit]

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

See also[edit]

References[edit]