Dr. Dobb's Journal - July 2008 - (Page 58)

Effective Concurrency Figure 3: Nonlocalized insertion into a red-black tree. node, is protected by its own mutex. Each thread that may add or remove nodes from the list takes a lock on the first node, then while still holding that, takes a lock on the next node; then it lets go of the first node and while still holding a lock on the second node, it takes a lock on the third node; and so on. (To delete a node requires locking three nodes.) While traversing the list, each such thread always holds at least two locks—and the locks are always taken in the same order. This technique delivers a number of benefits, including the following: • Multiple readers and writers can be actively doing work in the same list. • Readers and writers that are traversing the list in the same order will not pass each other. This can be useful to get deterministic results in concurrent code. In particular, the list’s semantics will be the same as if each thread acquired complete exclusion on the list and performed its complete pass in isolation, which is easy to reason about. • The locks taken on parts of the list won’t deadlock with each other, because multiple locks are acquired in the same order. • We can readily tune the code for better concurrency vs. lower locking overhead by choosing a suitable locking granularity: one lock for the whole list (no concurrency), a lock for each node in the list (maximum concurrency), or a lock for each chunk of some fixed or variable length (something in between). Aside: If we always traverse the list in the same order, why does the figure show a doubly linked list? Because not all operations need to take multiple locks; those that use individual segments or nodes in-place one at a time without taking more than one node’s or chunk’s lock at a time can traverse the list in any order without deadlock. (For more on avoiding deadlock, see [1].) 58 Dr. Dobb’s Journal l www.ddj.com l July 2008 Besides being well suited for concurrent traversal and update, linked lists also are cache-friendly on parallel hardware. When one thread removes a node, for example, the only memory that needs to be transferred to every other core that subsequently reads the list is the memory containing the two adjacent nodes. If the rest of the list hasn’t been changed, multiple cores can happily store read-only copies of the list in their caches without expensive memory fetches and synchronization. (Remember, writes are always more expensive than reads because writes need to be broadcast. In turn, “lots of writes” are always more expensive than “limited writes.”) Clearly, one benefit lists enjoy is that they are node-based containers: Each element is stored in its own node, unlike an array or vector where elements are contiguous and inserting or erasing typically involves copying an arbitrary number of elements to one side or the other of the inserted or erased value. We might therefore anticipate that perhaps all node-based containers will be good for concurrency. Unfortunately, we would be wrong. ed or erased node’s parent and/or uncle node, that node’s own parent and/or uncle, and so on to the grandparents and granduncles up the tree, possibly as far as the root. For example, consider Figure 3. To start with, the tree contains three nodes with the values 1, 2, and 3. To insert the value 4, we simply make it a child of node 3, as we would in a nonbalanced binary search tree. Clearly, that involves writing to node 3, to set its right-child pointer. However, to satisfy the red-black tree mechanics, we must also change node 3’s and node 1’s color to black. That adds overhead and loses some concurrency; for example, inserting 4 would conflict with adding 1.5 concurrently, because both inserts would need to touch both nodes 1 and 3. Next, to insert the value 5, we need to touch all but one of the nodes in the tree: We first make node 4 point to the new node 5 as its right child, then recolor both node 4 and node 3, and then because the tree is out of balance we also rotate 3-4-5 to make node 4 the root of that subtree, which means also touching node 2 to install node 4 as its new right child. So red-black trees cause some problems for concurrent code: • It’s hard to run updates truly concurrently because updates arbitrarily far apart in the tree can touch the same nodes—especially the root, but also other higher-level nodes to lesser degrees—and therefore contend with each other. We have lost the ability to make truly localized changes. • The tree performs extra internal housekeeping writes. This increases the amount of shared data that needs to be written and synchronized across caches to publish what would be a small update in another data structure. “But wait,” I can hear some people saying, “why can’t we just put a mutex inside each node and take the locks in a single direction (up the tree) like we could do with the linked list and hand-over-hand locking? Wouldn’t that let us regain the ability to have concurrent use of the data structure at least?” Short answer: That’s easy to do, but hard to do right. Unlike the linked list case, however: (a) you may need to take many Balanced Search Trees The story isn’t nearly as good for another popular data structure: the balanced search tree. (Important note: This section refers only to balanced trees; unbalanced trees that support localized updates don’t suffer from the problems we’ll describe next.) Consider a red-black tree: The tree stays balanced by marking each node as either “red” or “black,” and applying rules that call for optionally rebalancing the tree on each insert or erase to avoid having different branches of the tree become too uneven. In particular, rebalancing is done by rotating subtrees, which involves touching an insert- http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - July 2008

Dr. Dobb's Journal - July 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Developer’s Notebook Engineers Without Borders Conversations Patricia Tries Event-Based Architectures Graphs Versus Objects Lock-Free Queues Dr. Dobb’s Architecture & Design World Java and the Nokia N10 Internet Tablet Effective Concurrency The Agile Edge Swaine’s Flames

Dr. Dobb's Journal - July 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.