In computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, serializing tokens are a concept in concurrency control arising from the ongoing development of DragonFly BSD

DragonFly BSD

DragonFly BSD is a free Unix-like operating system created as a fork of FreeBSD 4.8. Matthew Dillon, an Amiga developer in the late 1980s and early 1990s and a FreeBSD developer between 1994 and 2003, began work on DragonFly BSD in June 2003 and announced it on the FreeBSD mailing lists on July...

. According to Matthew Dillon

Matt Dillon (computer scientist)

Matthew Dillon is a computer scientist living in Berkeley, California. He is best known for his contributions to FreeBSD and for starting the DragonFly BSD project....

, they are most akin to SPLs, except a token works across multiple CPUs

Central processing unit

The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...

 while SPLs only work within a single CPU's domain.

Serializing tokens allow programmers to write multiprocessor

Multiprocessor

Computer system having two or more processing units each sharing main memory and peripherals, in order to simultaneously process programs.Sometimes the term Multiprocessor is confused with the term Multiprocessing....

-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

Mutual exclusion

Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...

 

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

Lock (computer science)

In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...

: 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
   Light Weight Kernel Threads
   Light Weight Kernel Threads or LWKT is a term from computer science in general and in DragonFlyBSD in particular. LWKTs differ from normal kernel threads in that they can preempt normal kernel threads. According to Matt Dillon, DragonFlyBSD creator:...
   
   .
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 Deadlock

Deadlock

A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...

s and Priority inversion

Priority inversion

In computer science, priority inversion is a problematic scenario in scheduling when a higher priority task is indirectly preempted by a lower priority task effectively "inverting" the relative priorities of the two tasks....

s. Dealing with these issues is very difficult and requires coordination at many different levels of the kernel:
Obviously Matt has reason to promote his own solution to deadlocking, but he has a point: serializing tokens do a fine job of locking out other threads as long as you don't block while holding them. If you do, another thread will steal the lock and possibly change the data you were working on. You will reacquire the token when you are awakened, but you will have to make sure that your data is still consistent.

Serializing Tokens In Action

To show how serializing tokens actually work, let's see some pseudocode

Pseudocode

In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...

 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

Mac OS X

Mac OS X

Mac OS X is a series of Unix-based operating systems and graphical user interfaces developed, marketed, and sold by Apple Inc. Since 2002, has been included with all new Macintosh computer systems...

's Darwin

Darwin (operating system)

Darwin is an open source POSIX-compliant computer operating system released by Apple Inc. in 2000. It is composed of code developed by Apple, as well as code derived from NeXTSTEP, BSD, and other free software projects....

 kernel uses a similar technique (called a funnel

Funnel (Concurrent computing)

In Computer Science, a funnel is a synchronization primitive used in kernel development to protect system resources. First used on Digital UNIX as a way to "funnel" device driver execution onto a single processor, funnels are now used in the Mac OS X kernel to serialize access to the BSD portion of...

) to serialize access to the BSD portion of the kernel.