Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Serializing tokens
open-in-new
<h2 id="comparison-with-mutual-exclusion-mutex">Comparison with mutual exclusion (mutex)</h2> <p>Tokens and <a href="/facts/Mutual_exclusion/1dwvCxDW">mutual exclusion</a> (mutex) mechanisms are <a href="/facts/Lock_(computer_science)/e3a9gnJT">locks</a>. 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: </p> <ol><li>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.</li> <li>Concurrent execution: in multiprocessor computers, a thread may be run at exactly the same time as another thread on a different CPU.</li> <li>Preemption: a thread may preempt a lower-priority thread, such as a hardware interrupt or <a href="/facts/Light_Weight_Kernel_Threads/cK3Cc2rj">Light Weight Kernel Threads</a>.</li> <li>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.</li></ol> <p>The following table summarizes the properties of tokens and mutexes. </p> Serializing Tokens vs Mutexes<table><tbody><tr><th> </th><th>Serializing tokens</th><th>Mutexes</th></tr><tr><th>Timeslicing</th><td>Works</td><td>Works</td></tr><tr><th>Concurrent execution</th><td>Works</td><td>Works</td></tr><tr><th>Preemption</th><td>Works</td><td>Works</td></tr><tr><th>Voluntary blocking</th><td>Fails</td><td>Works</td></tr><tr><th>Avoids deadlock</th><td>Yes</td><td>No</td></tr><tr><th>Avoids priority inversion</th><td>Yes</td><td>No</td></tr></tbody></table> <p>Issues such as <a href="/facts/Deadlock_(computer_science)/YDpdfnPP">deadlock</a> and <a href="/facts/Priority_inversion/9gSnYRRf">priority inversion</a> 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. </p> <blockquote><p>... 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).</p>— Matthew Dillon</blockquote> <h2 id="example">Example</h2> <p>The following <a href="/facts/Pseudocode/XgN19duK">pseudocode</a> and explanations illustrate how serializing tokens work. </p> Example PseudoCode using serializing tokens<table><tbody><tr><th>Thread A</th><th>Thread B</th><th>Action</th></tr><tr><td>lwkt_gettoken(T1);iter = list1.head;</td><td>...lwkt_gettoken(T1); // blocks// waiting for token T1</td><td>A acquires token T1 and uses it to get synchronized access to list1, which is shared by both threads.</td></tr><tr><td>lwkt_gettoken(T2); // blocks</td><td>// waiting for token T1</td><td>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.</td></tr><tr><td>// waiting for T1 and T2</td><td>list1.head = list1.head.next;lwkt_releasetoken(T1);</td><td>B acquires T1 and modifies list1. Note that A's "iter" still points to the old head of the list.</td></tr><tr><td>// 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);</td><td> </td><td>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.</td></tr></tbody></table> <h2 id="prior-art-in-the-darwin-kernel">Prior art in the Darwin kernel</h2> <p><a href="/facts/Mac_OS_X/Y93vVpTm">Mac OS X</a>'s <a href="/facts/Darwin_(operating_system)/DogI3ptd">Darwin</a> kernel uses a similar technique (called a <a href="/facts/Funnel_(Concurrent_computing)/nnfkdfRj">funnel</a>) to serialize access to the <a href="/facts/BSD/XQKcURrh">BSD</a> portion of the kernel. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Lock-free_and_wait-free_algorithms/KhLDma0v">Lock-free and wait-free algorithms</a></li></ul> <ul><li><a href="http://thread.gmane.org/gmane.os.dragonfly-bsd.kernel/4436">A mailing list thread where Matthew Dillon explains tokens in great detail</a> <a href="https://web.archive.org/web/20170205112223/http://thread.gmane.org/gmane.os.dragonfly-bsd.kernel/4436">Archived</a> 2017-02-05 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a></li> <li><a href="https://developer.apple.com/technotes/tn/tn2028.html">Darwin Threading Architectures</a></li></ul>