Les propriétés des sémaphores

Effets de P et V sur NF :

• Cas de l’opération P :
  NP = NP + 1;
  Si compteur = 0 c’est à dire compteur0 + NV = NP alors NF = NF +1;
  (un nouveau processus va pouvoir franchir la barrière)
  
  
• Cas de l’opération V :
  NV = NV + 1;
  Si compteur < 0 c’est à dire NP > compteur0 + NV alors NF = NF +1;
  (un nouveau processus va pouvoir franchir la barrière)

Théorème1
Enoncé :
P et V laissent invariante la relation : NF == min (NP, Compteur0 + NV)

Démonstration:
Nous savons que NF est égale à l’une des deux valeurs suivantes :
        NP
        compteur0 + NV

Cette relation reste vérifiée après l’exécution d’une opération P.

On constate à nouveau que cette relation reste vérifiée après l’exécution d’une opération V.
Cette relation demeure vraie dans chaque cas.

Théorème2
Enoncé :
Si le compteur d‘un sémaphore est négatif alors :
¦compteur¦== nombre des processus bloqués dans la file d’attente de ce sémaphore. Avec ¦compteur¦est la valeur absolue du compteur.

Démonstration:
Nous savons que : compteur == compteur0 + NV – NP
Comme le compteur est négatif, alors : compteur0 + NV < NP
Nous savons par ailleurs que : NF == min (NP, Compteur0 + NV). D’où on peut déduire que NF == compteur0 + NV

Ces deux résultats permettent d’écrire
Compteur == compteur0 + NV – NP
             == NF – NP


¦Compteur¦ == - compteur
/*car le compteur est négatif*/
Donc :
¦Compteur¦ == NP – NF
                == nombre de processus demandant - nombre de processus ayant franchi effectivement la barrière