In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, serializing tokens are a concept in concurrency control arising from the ongoing development of
DragonFly BSD
DragonFly BSD is a free and open-source Unix-like operating system forked from FreeBSD 4.8. Matthew Dillon, an Amiga developer in the late 1980s and early 1990s and FreeBSD developer between 1994 and 2003, began working on DragonFly BSD in ...
. According to
Matthew Dillon
Matthew Dillon (born 1966) is an American software engineer known for Amiga software, contributions to FreeBSD and for starting and leading the DragonFly BSD project since 2003.
Biography
Dillon studied electronic engineering and computer scie ...
, they are most akin to
SPLs, except a token works across multiple
CPUs
A central processing unit (CPU), also called a central processor, main processor, or just processor, is the primary Processor (computing), processor in a given computer. Its electronic circuitry executes Instruction (computing), instructions ...
while SPLs only work within a single CPU's domain.
Serializing tokens allow programmers to write
multiprocessor
Multiprocessing (MP) is the use of two or more central processing units (CPUs) within a single computer system. The term also refers to the ability of a system to support more than one processor or the ability to allocate tasks between them. The ...
-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.
Comparison with mutual exclusion (mutex)
Tokens and
mutual exclusion
In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters a critical section while a concurr ...
(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:
# 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.
# Concurrent execution: in multiprocessor computers, a thread may be run at exactly the same time as another thread on a different CPU.
# Preemption: a thread may preempt a lower-priority thread, such as a hardware interrupt or
Light Weight Kernel Threads
Light Weight Kernel Threads (LWKT) is a computer science term and from DragonFly BSD in particular. LWKTs differ from normal kernel threads in that they can preempt normal kernel threads. According to Matt Dillon, DragonFlyBSD creator:
Se ...
.
# 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
Deadlock commonly refers to:
* Deadlock (computer science), a situation where two processes are each waiting for the other to finish
* Deadlock (locksmithing) or deadbolt, a physical door locking mechanism
* Political deadlock or gridlock, a si ...
and
priority inversion
In computer science, priority inversion is a scenario in scheduling in which a high-priority task is indirectly superseded by a lower-priority task, effectively inverting the assigned priorities of the tasks. This violates the priority model tha ...
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.
Example
The following
pseudocode
In computer science, pseudocode is a description of the steps in an algorithm using a mix of conventions of programming languages (like assignment operator, conditional operator, loop) with informal, usually self-explanatory, notation of actio ...
and explanations illustrate how serializing tokens work.
Prior art in the Darwin kernel
Mac OS X
macOS, previously OS X and originally Mac OS X, is a Unix, Unix-based operating system developed and marketed by Apple Inc., Apple since 2001. It is the current operating system for Apple's Mac (computer), Mac computers. With ...
's
Darwin kernel uses a similar technique (called a
funnel
A funnel is a tube or pipe that is wide at the top and narrow at the bottom, used for guiding liquid or powder into a small opening.
Funnels are usually made of stainless steel, aluminium, glass, or plastic. The material used in its constructi ...
) to serialize access to the
BSD
The Berkeley Software Distribution (BSD), also known as Berkeley Unix or BSD Unix, is a discontinued Unix operating system developed and distributed by the Computer Systems Research Group (CSRG) at the University of California, Berkeley, beginni ...
portion of the kernel.
See also
*
Lock-free and wait-free algorithms
In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking i ...
References
A mailing list thread where Matthew Dillon explains tokens in great detail{{Webarchive, url=https://web.archive.org/web/20170205112223/http://thread.gmane.org/gmane.os.dragonfly-bsd.kernel/4436 , date=2017-02-05
Concurrency control