Problèmes de synchronisation

Considérons le cas de deux processus P1 et P2 suivants :

A1, A2, B1 et B2 sont des instructions atomiques. Dans un système multiprogrammé/temps partagé, ces 2 processus peuvent s’exécuter selon l’un des schémas suivants :

• A1 ; A2 ; B1 ; B2 ;
• A1 ; B1 ; A2 ; B2 ;
• A1 ; B1 ; B2 ; A2 ;
• B1 ; B2 ; A1 ; A2 ;
• B1 ; A1 ; B2 ; A2 ;
• B1 ; A1 ; A2 ; B2 ;
• ... ... ...

On parle d’un entrelacement non déterministe.

Pour que cette application soit valide, il faut que toutes les séquences possibles donnent le même résultat spécifié par le problème. La validité du résultat ne peut pas être garantie si ces instructions manipulaient des données communes aux deux processus.

Exemple :
Considérons le cas de deux processus P1 et P2 utilisant une variable commune N. N est une variable, à valeurs entières, supposée être initialisée à zéro. Les codes de P1 et de P2 contiennent chacun une instruction permettant d’incrémenter la valeur de N.

Le résultat de l’application précédente (valeur finale de N) peut être 1 ou 2 en fonction de la séquence (ordre des instructions) exécutée.
En effet, l’instruction N = N+1 n’est pas une instruction atomique. Elle peut être remplacée par le compilateur par une séquence identique à la séquence suivante :

LDA N /*charger l’accumulateur par la valeur de la case mémoire N* /
ADA# 1 /*additionner 1 à la valeur de l’accumulateur */
STA N /*stocker la valeur de l’accumulateur dans la case mémoire N*/

Le problème, mentionné plus-haut (les résultats), vient précisément de la non-atomicité de cette instruction. Durant son exécution, elle peut être interrompue conduisant ainsi à l’activation de l’autre processus. Si une première interruption se produit après «LDA N» et avant «ADA# 1» du premier processus faisant passer l’unité centrale au deuxième processus et si une deuxième interruption se produit après le «STA N» du deuxième processus alors la valeur obtenue à la fin par N serait 1 au lieu de 2.
Sans précautions particulières, le résultat final dépend donc de certains facteurs aléatoires (instants d’occurrence des interruptions).

Il faut noter que cette dépendance des facteurs aléatoires n’est pas acceptable.