Permissiveness in Transactional Memories

We introduce the notion of permissiveness in transactional memories (TM). Intuitively, a TM is permissive if it never aborts a transaction when it need not. More specifically, a TM is permissive with respect to a safety property p if the TM accepts every history that satisfies p. Permissiveness, like safety and liveness, can be used as a metric to compare TMs. We illustrate that it is impractical to achieve permissiveness deterministically, and then show how randomization can be used to achieve permissiveness efficiently. We introduce Adaptive Validation STM (AVSTM), which is probabilistically permissive with respect to opacity; that is, every opaque history is accepted by AVSTM with positive probability. Moreover, AVSTM guarantees lock freedom. Owing to its permissiveness, AVSTM outperforms other STMs by upto 40% in read dominated workloads in high contention scenarios. But, in low contention scenarios, the bookkeeping done by AVSTM to achieve permissiveness makes it, on average, 20-30% worse than existing STMs.

Publié dans:
Proceedings of the 22nd International Symposium on Distributed Computing
Présenté à:
DISC 2008, Arcachon, France, September 22-24, 2008

Note: Le statut de ce fichier est: Anyone

 Notice créée le 2008-08-07, modifiée le 2020-10-28

Télécharger le document

Évaluer ce document:

Rate this document:
(Pas encore évalué)