Contention Management

From Multicore
Jump to: navigation, search

Overview

There are actually degrees of nonblocking algorithms[1]. A synchronization technique is wait-free if it ensures that every thread will continue to make progress in the face of arbitrary delay of other threads. It is lock-free if it ensures only that some thread always makes progress. Although wait-free synchronization is the ideal behavior, lock-free synchronization is acceptable for practical purposes. Nonetheless, correctness requirement and performance management is intermingled in these two synchronization methods. With lock-free synchronization, one must not only ensure that the algorithm functions correctly, but also guard against livelock. With wait-free synchronization one must additionally ensure that every thread makes progress in bounded time. Mixture of these two requiremenst makes the implementation complicated.


Obstruction-free, on the contrary, separates performance features from correctness substrate. A synchronization method is obstruction-free if it guarantees progress for any thread that (eventually) executes in isolation. This requirement is strong enough to avoid the problems associated with locks, but it is weaker than previous nonblocking properties, allowing greater flexibility. Obstruction-free software transactional memories are accompanied by a contention manager to maximize system throughput.


When transactions collide, contention manager decides whether to abort the offending transaction or not. Based on the correctness substrate provided by obstruction-free implementation, contention manager can aggressively apply heuristics without worrying for the correctness of the implementation.


Contention Manager Implementations

Scherer and Scott describes a list of contention managers in [2]. Following are the contention managers described in the article.


Polite

The polite manager uses exponential backoff to resolve conflicts. Backoff time increases exponentilly as the number of failed attempt to aquire an object increases. After m rounds of trial to aquiare an object, the manager aborts the opponent.


Karma

The Karma contention manager gives priority to a transaction that has done more work. Karma manager aborts young transactions in favor of older transactions that is (possibly) near the final stage of commit. As a rough approximation for amount of work done, the contention manager keeps track of the number of objects the transaction has opened. It increments the priority with each object opened, and resets to zero when transaction commits. Note that the policy does not reset the priority when the transaction aborts; this gives a boost to a transaction's next attempt to complete.

Eruption

Kindergarten

Timestamp

PublishedTimestamp

Polka

References

  1. M. Herlihy, V. Luchangco, and M. Moir. Obstruction-free synchronization: double-ended queues as an example. International Conference on Distributed Computing Systems, pages 522-529. IEEE, 2003.
  2. William N. Scherer, III , Michael L. Scott, Advanced contention management for dynamic software transactional memory, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA