Famine (informatique)

La famine est un problème que peut avoir un algorithme d'exclusion mutuelle, lorsqu'un processus est perpétuellement privé des ressources nécessaires afin de terminer son exécution. Il se produit lorsqu'un algorithme n'est pas équitable, c'est-à-dire qu'il ne garantit pas à tous les threads souhaitant accéder à une section critique une probabilité non nulle d'y parvenir en un temps fini.

Il est difficile de concevoir des systèmes à l'abri de famines. Pour le cas de l'exclusion mutuelle par exemple, il existe deux algorithmes garantissant qu'il ne se produira pas de famine, l'algorithme de Dekker et l'algorithme de Peterson, mais dans les deux cas, cette garantie est obtenue au prix d'une coûteuse attente active.

Causes possibles de famine

Une des causes possibles de famine provient d'algorithmes qui ne garantissent pas que les processus qui souhaitent entrer dans une section critique y entrent dans le même ordre que les demandes (c'est-à-dire un comportement FIFO). Un exemple typique de mécanisme de synchronisation qui ne garantit pas cet ordre est le synchronized du langage Java.

Voir aussi

• Luigi Zaffalon et Pierre Breguet, Programmation concurrente et temps réel avec ADA 95, Presses polytechniques et universitaires romandes, Lausanne, 1999
• Le problème du dîner des philosophes