31.8Lock‐FreeImplementationofaQueue 495
UINT32 head = m_head;
AllocRef alloc = m_pQueue[head % m_maxQueueSize];
UINT32 tail = m_tail;
if (head != m_head) continue;
if (head == m_tail)
{
if (m_pQueue[tail % m_maxQueueSize].arrayIndex ==
AllocRef::NullIndex)
if (tail == m_tail) continue; // Queue is empty.
CAS(&m_tail, tail, tail + 1);
}
if (alloc.arrayIndex != AllocRef::NullIndex)
{
if (CAS2(&m_pQueue[head % m_maxQueueSize].val, alloc.val,
AllocRef(AllocRef::NullIndex, alloc.version + 1).val))
{
CAS(&m_head, head, head+1);
T item = m_pItems[alloc.arrayIndex];
// Release index back to free list.
m_allocator.Free(alloc.arrayIndex);
return (item);
}
}
else if (m_pQueue[head % m_maxQueueSize].arrayIndex ==
AllocRef::NullIndex)
{
CAS(&m_head, head, head+1);
}
}
}
Listing 31.8. A lock-free, array-based producer-consumer queue.
When inserting an item, both the stack and queue continue spinning until
they are not full. When removing an item, both the stack and queue continue
496 31.Producer‐ConsumerQueues
spinning until they are not empty. To modify these methods to return an error
code instead, replace
continue with return at the appropriate locations. This is
a better strategy when data is being inserted and removed from the queue sporad-
ically, since the application can handle the best way to wait. For example, the
application can call
SwitchToThread() to allow the OS thread scheduler to yield
execution to another thread instead of pegging the processor at 100% with un-
necessary spinning.
31.9InterprocessCommunication
Both the semaphore-based model and the lock-free model can be extended for
use for interprocess communication. Win32 memory-mapped files can act as
shared storage for all the volatile and constant memory used by the algorithms.
To extend to the semaphore-based queue, replace the critical sections with named
mutexes and the semaphores with named semaphores. The queue will be man-
aged using kernel locks, and the head and tail offsets can be maintained as re-
served space in the memory-mapped file.
The lock-free implementation is handled similarly, except no locks are need-
ed, even across processes. However, just like the semaphore-based queue, the
lock-free queue requires all producers and consumers to use the same lock-free
code to ensure thread safety.
From the perspective of both algorithms, there are no differences between an
array in one process and the same array remapped in different processes, since
each algorithm is designed to operate using array indices instead of pointers.
References
[AMD 2010] AMD. AMD64 Architecture Programmer’s Manual Volume 2: System
Programming. Advanced Micro Devices, 2010. Available at http://support.amd.
com/us/Processor_TechDocs/24593.pdf.
[Colvin and Groves 2005] Robert Colvin and Lindsay Groves. “Formal Verification of
an Array-Based Nonblocking Queue.” Proceedings of Engineering of Complex
Computer Systems, June 2005.
[Dawson 2008] Bruce Dawson. “Lockless Programming Considerations for Xbox 360
and Microsoft Windows.” MSDN, June 2008. Available at http://msdn.microsoft.
com/en-us/library/ee418650%28VS.85%29.aspx.
References 497
[Intel 2010] Intel. Intel 64 and IA-32 Architectures. Software Developer’s Manual.
Volume 3A: System Programming Guide. Intel, 2010. Available at http://www.
intel.com/Assets/PDF/manual/253669.pdf.
[Leonard 2007] Tom Leonard. “Dragged Kicking and Screaming: Source Multicore.”
Game Developers Conference, 2007. Available at http://www.valvesoftware.com/
publications/2007/GDC2007_SourceMulticore.pdf.
[Newcomer 2001] Joseph M. Newcomer. “Using Semaphores: Multithreaded Produc-
er/Consumer.” The Code Project, June 14, 2001. Available at http://www.
codeproject.com/KB/threads/semaphores.aspx.
[Sedgewick 1998] Robert Sedgewick. Algorithms in C++, 3rd Edition. Reading, MA:
Addison-Wesley, 1998.
[Shafiei 2009] Niloufar Shafiei. “Non-blocking Array-Based Algorithms for Stacks and
Queues.” Proceedings of Distributed Computing and Networking, 2009.
[Shann et al. 2000] Chien-Hua Shann, Ting-Lu Huang, and Cheng Chen. “A Practical
Nonblocking Queue Algorithm using Compare-and-Swap.” Proceedings of Paral-
lel and Distributed Systems, 2000.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.