Compare-and-swap
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[1].
Leur fonctionnement reste globalement similaire. Contrairement à l'opération abstraite, l'instruction processeur prend 3 arguments : une adresse mémoire a, une valeur attendue e, et une valeur de mise à jour v, et retourne une valeur booléenne. Si la valeur contenue à l'adresse mémoire a contient la valeur attendue e, écrire la nouvelle valeur v à cette adresse et retourner vrai, sinon laisser la mémoire intacte et retourner faux.
Processeurs Intel
La premiĂšre instruction de type CAS est apparue en premier en 1989 sur le processeur Intel 80486.
Sur les processeurs Intel, il existe deux instructions similaires qui implémentent l'instruction CAS : CMPXCHG (compare and exchange) et CMPXCHG8B (compare and exchange 8 bytes). L'instruction CMPXCHG requiert 3 opérandes : une opérande de source dans un registre, une autre opérande de source dans le registre EAX et enfin une opérande de destination. Si les valeurs contenues dans l'opérande de destination et dans le registre EAX sont égales, alors l'opérande de destination est remplacée par la valeur de la deuxiÚme opérande de source (la valeur qui ne se trouve pas dans le registre EAX). Sinon, la valeur contenue dans l'opérande de destination est chargée dans le registre EAX[2].
Cette instruction est utilisĂ©e pour tester et modifier des sĂ©maphores. Si elle teste qu'un sĂ©maphore est libre, alors elle le marquera comme Ă©tant allouĂ©. Sinon elle renverra l'ID de son propriĂ©taire. Elle peut ĂȘtre utilisĂ©e tout aussi bien en architecture monocĆur qu'en multicĆurs. Dans ce dernier cas, un prĂ©fixe LOCK peut ĂȘtre ajoutĂ© devant l'instruction pour la forcer Ă ĂȘtre atomique.
Exemple d'utilisation
Voici un exemple d'utilisation tiré du noyau de Linux, la fonction rtc_cmos_read() , désassemblée, utilise l'instruction suivante[3] - [4] :
lock cmpxchg %edx, cmos_lock
On peut la lire de la façon suivante :
- prefix :
lock - opcode:
cmpxchg - source-operand:
%edx - destination-operand:
cmos_lock
Variantes
CMPXCHG8B fonctionne de maniĂšre similaire mais avec des valeurs 64-bit au lieu de valeurs 32-bit, elle peut Ă©galement ĂȘtre accompagnĂ© ou non du prĂ©fixe LOCK pour la forcer Ă agir de maniĂšre atomique. Elle prend Ă©galement 3 opĂ©randes : une valeur 64-bit dans EDX:EAX, une valeur 64-bit dans ECX:EBX, et une opĂ©rande de destination en mĂ©moire (dont la valeur n'est pas prĂ©cisĂ©e). L'instruction compare la valeur contenue dans EDX:EAX avec la valeur de l'opĂ©rande de destination. Si elles sont Ă©gales, la valeur des registres ECX:EBX est enregistrĂ©e dans l'opĂ©rande de destination, sinon la destination est chargĂ©e dans les registres EDX:EAX.
Il existe également une instruction uniquement disponible pour les architectures 64-bit, appelée CMPXCHG16B, qui est une extension de l'instruction CMPXCHG8B et opÚre sur des données de 128-bit.
ProblĂšme du Consensus
L'instruction Compare-and-Swap fait l'objet d'un théorÚme particulier en ce qui concerne le problÚme du consensus[5] - [6].
ThĂ©orĂšme â Un registre qui fournit Ă la fois les mĂ©thodes compareAndSwap() et Get() possĂšde un numĂ©ro de consensus infini.
ProblĂšme ABA
Le problĂšme ABA (en) rĂ©sulte d'un dĂ©faut liĂ© au fonctionnement mĂȘme de l'instruction CAS. Elle apparait communĂ©ment dans la situation suivante :
- Une application lit une valeur a d'une adresse mémoire donnée, et calcule une nouvelle valeur c pour cette adresse.
- Elle essaye de sauvegarder c, mais seulement si la valeur a à l'adresse mémoire n'a pas été changée depuis qu'elle a été lue.
- Pendant ce temps-là , un autre thread a réécrit l'adresse mémoire de a avec une valeur b, puis plus tard réécrit a à cet emplacement-là .
L'opĂ©ration CAS va remplacer a avec c, mais peut-ĂȘtre que l'application n'aura pas agit comme on s'y attendait. Par exemple, si l'adresse a mĂ©morise un pointeur, la nouvelle valeur a sera peut-ĂȘtre l'adresse d'un objet recyclĂ©.
Notes et références
- (en) Maurice Herlihy, Nir Shavit, Victor Luchangco et Michael Spear, The art of multiprocessor programming, Morgan Kaufmann, 2e Ă©d. (ISBN 978-0-12-415950-1), p. 529
- (en) Intel, IntelÂź 64 and IA-32 Architectures - Software Developerâs Manual - Combined Volumes:1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D and 4, Intel Corporation, , 5106 p. (lire en ligne), Vol.1 7-4 (pdf: p178), 7-5 (pdf: p179) ; Vol.2A 3-592 (pdf: p1186)
- (en) « Intelâs âcmpxchgâinstruction » [PDF], sur cs.ucdavis.edu (consultĂ© le )
- (en) « Linux kernel x86 - rtc.c » [html] (Code source du noyau Linux v5.12 en C), sur elixir.bootlin.com (consulté le )
- (en) Maurice Herlihy, Nir Shavit, Victor Luchangco et Michael Spear, The art of multiprocessor programming, Morgan Kaufmann, 2e Ă©d. (ISBN 978-0-12-415950-1), p. 119
- (en) Michael J. Fischer, Nancy A. Lynch et Michael S. Paterson, « Impossibility of Distributed Consensus with One Faulty Process », Journal of the ACM, Association for Computing Machinery, vol. 32, no 2,â , p. 374â382 (ISSN 0004-5411, DOI 10.1145/3149.214121, lire en ligne, consultĂ© le )