Test-and-set
L'instruction test-and-set est une instruction atomique utilisée en informatique dans les systèmes multiprocesseurs ou multi-cœurs utilisant une mémoire partagée, elle sert à écrire une valeur prédéterminée dans un emplacement mémoire et retourner la valeur d'origine de cet emplacement. Elle possède le nombre de consensus numéro deux[1].
Elle opère sur un seul mot mémoire (un octet ou byte) qui peut soit valoir vrai (true) soit faux (false), parfois noté 0 et 1 dans certain langages comme le C. Quand elle est appelée, elle remplace atomiquement la valeur mémorisée par la nouvelle valeur donnée en argument, et renvoie la valeur mémorisée précédente.
Elle permet de protéger une adresse mémoire en cas d'accès concurrents : si plusieurs processus tentent d'accéder à la même adresse mémoire et qu'un processus est en train d'exécuter une instruction test-and-set sur cette même adresse mémoire, alors aucun autre processus ne peut exécuter une autre instruction test-and-set jusqu'à ce que le premier processus aie terminé d'exécuter son instruction.
Code
- Exemple de pseudo-implémentation de la fonction en C (le C pur ne permettant pas réellement d'implémenter un test-and-set atomique) :
int test_and_set (int *verrou){
// -- DĂ©but de la partie atomique --
// Ceci est du pseudocode, montré ici juste pour illustrer le principe.
// S'il était utilisé normalement dans un compilateur,
// les garanties nécessaires d'atomicité, non-usage de cache, non-réorganisation par l'optimiseur etc.
// ne seraient pas fournies.
int old = *verrou;
*verrou = 1; // positionne le verrou à 1 pour dire qu'on veut occuper la SC (nb: ne change pas sa valeur si *verrou vaut déjà 1 car un autre processus est en SC)
// -- Fin de la partie atomique --
return old; // renvoie l'ancienne valeur (c'est-à -dire 1 (vrai) si et seulement si il y avait déjà un processus en SC à l'entrée dans test_and_set)
}
Utilisation
L'instruction test-and-set est notamment utilisée pour écrire des Spinlock (trad: Verrou par rotation). Le verrou est libre lorsque la valeur du mot est faux, et occupé lorsqu'elle est vrai. Dans une implémentation possible, une méthode lock() (trad. verrouiller) tente de manière répétée d'exécuter l'instruction test-and-set sur le mot jusqu'à ce qu'elle retourne faux, autrement dit jusqu'à ce que le verrou soit libéré. Pour le libérer, la méthode unlock() (trad. déverrouiller) change la valeur du mot en faux[1].
Exemples d'utilisation
- En C (en utilisant le pseudo-code présenté précédemment)
int lock(int *lock)
{
while (test_and_set(lock) == 1);
}
- En Java, en utilisant la classe AtomicBoolean du package
java.util.concurrent:
public class TestAndSetLock implements Lock {
AtomicBoolean etat = new AtomicBoolean(false);
public void lock() {
while (etat.getAndSet(true)) {}
}
public void unlock() {
etat.set(false);
}
}
Note: l'instruction getAndSet(true) en Java fonctionne de manière équivalente à l'instruction test-and-set(true).
Voir aussi
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. 150