Compare-and-swap

Résumé

Compare-and-swap (CAS) est une instruction atomique utilisée dans les systèmes multiprocesseurs ou multi-cœurs utilisant une mémoire partagée. Elle compare la valeur stockée à une adresse mémoire donnée à l'un de ses arguments et, en cas d'égalité, écrit une nouvelle valeur à cette adresse. Selon les implémentations, elle signale si l'écriture a réussi soit en renvoyant une valeur booléenne, soit en renvoyant la valeur lue en mémoire. L'instruction CAS simple ne présente presque aucun problème au niveau de la synchronisation de l'adresse mémoire auquel elle pointe, sauf dans un cas précis décrit comme le problème ABA (en). Architectures supportées Cette opération de synchronisation est supportée par plusieurs architectures contemporaines, notamment sur Intel, AMD, et Oracle. Sur les architectures de Intel et AMD, cette instruction est appelée CMPXCHG, tandis que sur Oracle SPARC systems, elle est appelée CAS. Leur fonctionnement reste globalement similaire. Contrairement

Source officielle

https://fr.wikipedia.org/wiki/Compare-and-swap

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (32)

Chargement

Afficher plus

Publications associées

Chargement

Personnes associées (4)

Personnes associées

Chargement

Unités associées (1)

Unités associées

Chargement

Concepts associés (16)

Concepts associés

Chargement

Cours associés (11)

Cours associés

Chargement

Séances de cours associées (20)

Séances de cours associées

Chargement

Publications associées (32)

The Disclosure Power of Shared Objects

Peva François Blanchard, Rachid Guerraoui, Julien Michel Stainer, Mihail Igor Zablotchi

Shared objects are the means by which processes gather and exchange information about the state of a distributed system. Objects that disclose more information about the system are therefore more desirable. In this paper, we propose the schedule reconstruction (SR) problem as a new metric for the disclosure power of shared memory objects. In schedule reconstruction, processes take steps which are interleaved to form a schedule; each process needs to be able to reconstruct the schedule up to its last step. We show that objects can be ranked in a hierarchy according to their ability to solve SR. In this hierarchy, stronger objects can implement weaker objects via a SR-based universal construction. We identify a connection between SR and consensus and prove that SR is at least as hard as consensus. Perhaps surprisingly, we show that objects that are powerful in solving consensus—such as compare-and-swap—are not always powerful in their ability to solve SR.

2017

Chargement

The Disclosure Power of Shared Objects

Peva François Blanchard, Rachid Guerraoui, Julien Michel Stainer, Mihail Igor Zablotchi

Shared objects are the means by which processes gather and exchange information about the state of a distributed system. Objects that disclose more information about the system—and thus provide a more centralized view—are therefore more desirable. In this paper, we propose the schedule reconstruction (SR) problem as a new metric for the disclosure power of shared memory objects. In schedule reconstruction, processes take steps which are interleaved to form a schedule; each process needs to be able to reconstruct the schedule up to its last step. We show that objects can be ranked in a hierarchy according to their ability to solve SR. In this hierarchy, stronger objects can implement weaker objects via a SR-based universal construction. We identify a connection between SR and consensus and prove that SR is at least as hard as consensus. Perhaps surprisingly, we show that objects that are powerful in solving consensus—such as compare-and-swap—are not always powerful in their ability to solve SR.

2017

Chargement

This paper studies obstruction-free software transactional memory systems (OFTMs). These systems are appealing, for they combine the atomicity property of transactions with a liveness property that ensures the commitment of every transaction that eventually encounters no contention. We precisely define OFTMs and establish two of their fundamental properties. First, we prove that the consensus number of such systems is 2. This indicates that OFTMs cannot be implemented with plain read/write shared memory, on the one hand, but, on the other hand, do not require powerful universal objects, such as compare-and-swap. Second, we prove that OFTMs cannot ensure disjoint-access-parallelism (in a strict sense). This may result in artificial "hot spots" and thus limit the performance of OFTMs.

2008

Chargement

Afficher plus