Ce programme C ne se compile pas :
int main(){
printf("%u",a);
return 0;
}
On a le message d'erreur à la compilation :
variable1.c:5:17:
error: ‘a’ undeclared
(first use in this function)
L'erreur vient de ce que si on veut afficher la valeur d'une variable, il faut que cette variable existe. Si on essaye d'y accéder avant sa naissance, il est normal que l'on n'y arrive pas.
Par contre, si on fait d'abord naître une variable en déclarant son type :
int main(){
int a;
printf("a == %u\n",a);
return 0;
}
Le programme se compile correctement, mais avec un avertissement :
variable1.c:6:5:
warning: ‘a’ is used uninitialized in this function
[-Wuninitialized]
Et, quand on l'exécute, on a un résultat imprévisible :
a == 3075806205
ou
a == 3075707901
Pour rendre ce programme déterministe, il faut donner une valeur à la variable :
int main(){
int a;
a = 2;
printf("a == %u\n",a);
return 0;
}
Par contre la variable b déclarée dans
une fonction disparaît après l'appel à cette fonction :
void mondeB(){
int b = 3;
}
int main(){
int a, b;
a = 2;
printf("a == %u\n",a);
mondeB();
printf("b == %u\n",b);
return 0;
}
L'affichage obtenu ressemble à
a == 2 b == 3216992892
En C, une variable a une
durée de vie finie, entre sa première affectation
qui correspond à sa naissance, ses affectations
successives correspondant à sa vie et la fin de
l'appel de la fonction (return) qui met fin à la vie de la
variable.
Dans le sujet de Capes 2020,
il est considéré qu'en Python chaque variable a plusieurs vies,
allant chacune d'une affectation (la variable apparaît
à gauche du =) à une utilisation dans une
autre affectation (la variable apparaît à droite du
= dans une expression servant à affecter une
autre variable).
Lorsqu'une variable est déclarée à l'intérieur
d'une fonction, elle est créée lorsqu'on appelle la
fonction et détruite après return.
Par exemple la variable b de la fonction
main() n'est pas la même que celle de
la fonction mondeB qui, elle, n'est accessible
que depuis le monde B (celui de l'appel de la fonction
mondeB()) :
int mondeB(){
int b = 3;
printf("b == %u\n",b);
return b+2;
}
int main(){
int a,b;
a = 2;
printf("%u\n",mondeB());
printf("b == %u\n",b);
return 0;
}
donne un affichage comme
b == 3 5 b == 3214315900
Pour aller plus loin, voici un troisième monde
C
en Python :
La visibilité des variables est représentée dans
ce graphe de Kripke (le monde A est main()) :
La variable c du monde C est visible
dans le monde C mais pas dans les autres mondes. Il y
a deux variables a, l'une dans le monde
A (monde global : a==2 dans ce monde) et une
autre dans le monde C. Cette dernière n'est visible
que dans le monde C.
La variable b est visible dans le monde
B mais aussi dans le monde C depuis lequel on peut voir
dans le monde B. Par contre la variable b
n'est pas visible depuis le monde A. Cette situation
évoque le théodicée de Leibniz.
Deux processus 🐮add3 et 🐵mul8 se partagent une variable
compteur initialisée à 0, et ont pour but
commun d'arriver à donner à cette variable la valeur
14. Mais
add3 ne sait qu'incrémenter 3 fois la variable (ce qui revient à lui additionner 3),mul8 ne sait que doubler 3 fois la variable (ce qui revient à la multiplier par 8).On peut simuler ces personnages par des threads :
from threading import *
compteur = 0
def add3():
global compteur
for _ in range(3):
compteur += 1
def mul8():
global compteur
for _ in range(3):
compteur *= 2
vache = Thread(target=add3)
singe = Thread(target=mul8)
vache.start()
singe.start()
Si add3 fait son travail d'abord, la variable
est égale à 3 au moment où 🐵mul8 effectue
le sien, et cela aura pour effet qu'à la fin la variable
vaudra 3×8==24 et non 14. Si par contre on confie le travail
d'abord à 🐵mul8, la variable aura été doublée
3 fois et restera nulle puisque 8×0==0, et ensuite lorsque
🐮add3 s'occupe de cette variable, le résultat
final sera 3 et non 14 : pour que 🐮add3
et 🐵mul8 réussissent à faire atteindre
la valeur 14 à la variable, ils doivent synchroniser
leurs tâches ou laisser un gestionnaire de tâches
les synchroniser. Les possibilités sont les suivantes :
En fait c'est plus compliqué que cela : pour incrémenter la variable, 🐮 va
alors que pour doubler la variable, 🐵 va
Si l'un des deux lit la variable avant que l'autre ait injecté la nouvelle valeur, le contenu lu ne sera pas à jour et l'une des opérations ne sera pas effectuée. Par exemple, voici un scénario possible :
Dans ce cas, au final, c'est comme si 🐮add3
n'avait bouclé que deux fois au lieu de trois, et
était une 🐮add2 (voire moins si le
phénomène se reproduisait).
Pour éviter ce genre de problème, il faut qu'entre la lecture et l'écriture de la variable, celle-ci soit réservée au thread qui s'en occupe. Cette période de temps est appelée section critique et on veut éviter qu'un thread puisse entrer en section critique avant qu'un autre en soit sorti.
Une métaphore parlante est celle où 🐮 et 🐵 veulent
chacun faire 3 fois une course à la boulangerie. Chaque
fois que l'un des deux entre dans la boulangerie, la
boulangère (le système d'exploitation) ferme la porte
à clé et retourne le panneau
ouvert
pour montrer le verso
fermé
à la place. La boulangère a verrouillé (locked) la porte.
On peut aussi imaginer un système de jeton, que la boulangère donne au client qu'elle veut servir. Il suffit qu'il n'y ait qu'un seul jeton pour qu'un seul client soit servi à la fois. On représente ce système par un réseau de Petri (🐮 est à gauche et 🐵 est à droite) :
Comme il y a deux transitions actives, à ce stade, chacun des clients peut prendre le jeton pour être servi. Par exemple si c'est 🐮 le jeton passe à gauche et 🐵 ne peut plus le prendre :
À ce stade la seule évolution possible (en vert en haut) est que 🐮 rende le jeton et revienne à l'état précédent. Si par contre c'est 🐵 qui avait pris le jeton :
alors la seule évolution possible est qu'il rende le jeton une fois servi et qu'on revienne à l'état initial.
Cette situation ou l'utilisation d'une variable par
un des threads exclut que l'autre thread y ait accès,
est appelé exclusion mutuelle et abrégée en
mutex.
Le réseau de Petri ci-dessus n'a que 3 états possibles, il s'agit donc d'un automate dont voici le graphe :
La faiblesse d'un mutex est qu'il n'empêche pas 🐮 de verrouiller le mutex sitôt après l'avoir libéré. C'est comme si le client juste devant moi à la boulangerie se rendait compte au moment où il vient juste de payer qu'il a oublié d'acheter un croissant et demande à ne pas refaire la queue. D'ailleurs si 🐵 ne prend jamais le jeton on dit qu'il a faim et les algorithmes ci-dessous visent à empêcher la famine.
Peterson propose que chacun des threads s'occupe
lui-même du verrou, qui est donc une variable globale
nommée mutex :
from threading import * from random import * from time import * compteur = 0 mutex = 'additionner'
On en profite pour ajouter un peu de hasard ce qui
permet d'éviter les situations trop particulières.
Le thread 🐮add3 a maintenant un code plus
complexe puisqu'il doit attendre le déverouillage pour
commencer son travail :
def add3():
global compteur
global mutex
for _ in range(3):
while mutex != 'additionner':
pass
sleep(1e-4*random())
compteur += 1
mutex = 'multiplier'
Dès que 🐮add3 a effectué une incrémentation,
il réserve lui-même la priorité à 🐵mul8
qui fera de même une fois qu'il aura doublé la
variable :
def mul8():
global compteur
global mutex
sleep(5e-5*random())
for _ in range(3):
while mutex != 'multiplier':
pass
sleep(1e-4*random())
compteur *= 2
mutex = 'additionner'
Avec ça le script
vache = Thread(target=add3) singe = Thread(target=mul8) vache.start() singe.start() sleep(0.2)
permet bien d'avoir compteur==14 à
la fin.
L'algorithme de Peterson est risqué parce qu'en
cas de bogue (par exemple s'il manque la dernière
ligne de la fonction add3() et que 🐮
oublie de rendre le jeton), on risque la boucle sans
fin :
mul8 attend le verrou puisque mutex=='additionner',add3 effectue ses trois incrémentations puis s'arrête.Lamport propose alors de remplacer le verrou par une file de priorité, ce qui revient à déléguer la gestion des verrous au gestionnaire des tâches (la boulangère).
Au lieu de demander le jeton, chaque thread obtient
un numéro comme à la boulangerie. Pour cela on utilise
le variable globale compteur que l'on incrémente
pour avoir le numéro de priorité du thread (plus le numéro
est petit et plus on est prioritaire). Par exemple
(le système d'ordonnancement est représenté par 🐱)
Après ça si 🐵 prend encore une numéro celui-ci sera supérieur à 3 qui est le numéro de 🐮 : il n'y a pas de risque de famine.
Mais on a vu plus haut qu'il y a un risque que
Dans ce cas de non atomicité, deux threads différents ont le même numéro d'attente. Auquel des deux 🐱 doit-il donner la priorité ?
La solution de Lamport consiste à ordonner les
threads (ici par ordre alphabétique) pour trancher.
Comme singe vient avant vache
dans l'ordre alphabétique, c'est 🐵 qui passe avant
🐮 car le couple (2,singe) est inférieur au couple
(2,vache).
L'ordre lexicographique donne une priorité calculable s'il n'y a pas d'égalité possible entre identifiants des threads. Pour cela on définit un entier à la création du thread, ce qui fait que chaque identifiant est unique.
Pour éviter le problème d'accès simultané à une
variable globale, Dijkstra propose le concept de
sémaphore. C'est un entier qui représente
le nombre de verrous disponibles. La valeur initiale
par défaut est 1 donc le sémaphore est égal à 1 lorsque
le verrou est libre et zéro lorsqu'il est réservé.
On prend le verrou par acquire (pour rendre
le sémaphore égal à 0) et on le rend par
release qui le rend à nouveau égal à 1 :
from threading import * compteur = Semaphore(1) compteur.acquire() print(compteur._Semaphore__value) compteur.release() print(compteur._Semaphore__value)
affiche
0 1
alors que
compteur = Semaphore(1) compteur.acquire() print(compteur._Semaphore__value) compteur.release() print(compteur._Semaphore__value) compteur.acquire() print(compteur._Semaphore__value) compteur.release() print(compteur._Semaphore__value)
donne
0 1 0 1
Si on essaye de réserver plus souvent le sémaphore qu'il a été libéré, le programme bloque. Par contre si on ne fait que libérer le sémaphore, cela incrémente sa valeur :
from threading import * compteur = Semaphore(0) print(compteur._Semaphore__value) compteur.release() print(compteur._Semaphore__value) compteur.release() print(compteur._Semaphore__value) compteur.release() print(compteur._Semaphore__value)
donne
0 1 2 3
Pour acquérir plusieurs fois le sémaphore sans blocage, il suffit de l'initialiser à plus que 5 :
from threading import * compteur = Semaphore(5) print(compteur._Semaphore__value) compteur.acquire() print(compteur._Semaphore__value) compteur.acquire() print(compteur._Semaphore__value) compteur.release() print(compteur._Semaphore__value) compteur.release() print(compteur._Semaphore__value) compteur.release() print(compteur._Semaphore__value)
donne
5 4 3 4 5 6
Les threads de Python sont des objets (de classe
Thread) donc ont un cycle de vie. Lorsqu'on
instancie un thread, il a un identifiant (ce qui permet
de lui appliquer l'algorithme de Lamport) et cet
identifiant est un entier. Cependant :
def cheshire():
print('Alice allez-vous jouer au criquet chez la Reine ?')
chat = Thread(target=cheshire)
print(chat)
print(chat.getName())
print(chat.ident)
print(chat.is_alive())
donne
Thread-1 None False
Lorsqu'un thread a été créé, il n'a pas encore
d'identifiant et sa méthode is_alive()
renvoie la valeur False ce qui signifie
que le thread n'est pas encore vivant. Pour cela, il
faut attendre sa naissance.
Pour faire vivre un thread il faut invoquer sa
méthode start() ce qui a pour effet de le faire naître :
chat = Thread(target=cheshire) print(chat.getName()) chat.start() print(chat.ident) print(chat.is_alive())
ce qui donne
Thread-1 Alice, allez-vous jouer au criquet chez la Reine ? -1222141120 False
Si on exécute plusieurs fois le script, le thread
est toujours nommé Thread-1 mais son identifiant
est différent à chaque exécution du script.
Lorsque le thread a fini son activité il n'est plus considéré comme vivant :
from threading import * from time import * chat = Thread(target=cheshire) print(chat.getName()) chat.start() sleep(0.2) print(chat.ident) print(chat.is_alive())
donne
Thread-1 Alice, allez-vous jouer au criquet chez la Reine ? -1221813440 False
Un thread, une fois qu'il a fini son travail, a
toujours son identifiant (ce qui évite de donner
l'identifiant à un autre thread et permet d'appliquer
l'algorithme de Lamport), mais sa méthode
is_alive() renvoie False
ce qui veut dire qu'il n'est plus vivant.
Le script
from threading import * from time import * chat = Thread(target=cheshire) chat.start() sleep(0.2) print(chat.is_alive()) chat.start()
donne
Alice, allez-vous jouer au criquet chez la Reine ? False Traceback (most recent call last): File "mutex7.py", line 8, inchat.start() File "/usr/lib/python2.7/threading.py", line 739, in start raise RuntimeError("threads can only be started once") RuntimeError: threads can only be started once
Autrement dit, le chat est dans l'état décrit dans
la pièce de Molière puisque la méthode
is_alive() renvoie False,
mais comme il a toujours un nom et un identifiant
(et accessoirement une méthode is_alive())
il est peut-être plutôt comme celui de Schrödinger.
Néanmoins on ne peut le traiter comme un zombie puisque
si on essaye de le relancer on a un message d'erreur
rappelant qu'un thread ne peut être lancé qu'une fois.