Algorithme de l'autruche
Cet article est orphelin. Moins de trois articles lui sont liés ().
Vous pouvez aider en ajoutant des liens vers [[Algorithme de l'autruche]] dans les articles relatifs au sujet.
Pour les articles homonymes, voir Autruche (homonymie).
En informatique, l'algorithme de l'autruche est une stratégie consistant à ignorer les problèmes potentiels en partant du principe qu'ils sont extrêmement rares. Il tire son nom de l'effet autruche qui est défini comme « se mettre la tête dans le sable et prétendre qu'il n'y a pas de problème »[1]. Il est utilisé lorsqu'il est plus rentable de laisser le problème survenir que de tenter de le prévenir.
Utilisation pour les interblocages[modifier | modifier le code]
Cette approche peut être utilisée pour traiter les blocages dans la programmation concurrente s'ils sont considérés comme très rares et que le coût de détection ou de prévention est élevé. Par exemple, si chaque PC se bloque une fois tous les 10 ans, le redémarrage peut être moins dérangeant que les restrictions nécessaires pour l'empêcher[2].
Un ensemble de processus est interbloqué si chaque processus de l'ensemble attend un événement que seul un autre processus de l'ensemble peut provoquer. Habituellement, l'événement est la libération d'une ressource actuellement détenue et aucun des processus ne peut s'exécuter, libérer des ressources et être réveillé[3].
L'algorithme de l'autruche prétend qu'il n'y a pas de problème et est raisonnable à utiliser si les blocages se produisent très rarement et que le coût de leur prévention serait élevé. Les systèmes d'exploitation Unix et Microsoft Windows adoptent cette approche[3].
Bien que l'utilisation de l'algorithme de l'autruche soit l'une des méthodes de traitement des Interblocages, d'autres méthodes efficaces existent telles que l'évitement dynamique, l'algorithme du banquier, la détection et la récupération, et la prévention[3].
Compromis[modifier | modifier le code]
Bien qu'efficace, l'utilisation de l'algorithme d'autruche remplace l'exactitude par la commodité. Pourtant, comme l'algorithme traite directement les cas extrêmes, ce n'est pas un gros compromis. En fait, la méthode la plus simple et la plus utilisée pour récupérer d'un blocage est un redémarrage.
Certains algorithmes avec de mauvaises performances dans le pire des cas sont couramment utilisés, car ils ne présentent de mauvaises performances que sur des cas artificiels qui ne se produisent pas dans la pratique. Des exemples typiques sont l'algorithme du simplexe et l'algorithme d'inférence de type pour le standard ML. Des problèmes tels que le dépassement d'entier dans les langages de programmation avec des entiers à largeur fixe sont également fréquemment ignorés, car ils ne surviennent que dans des cas exceptionnels qui ne se posent pas pour des entrées pratiques.
Notes et références[modifier | modifier le code]
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Ostrich algorithm » (voir la liste des auteurs).
- « Méfiez-vous de l'autruche! », sur www.revuegestion.ca, (consulté le )
- « OS 202 Class Notes », sur cs.nyu.edu (consulté le )
- (en) The University of New South Wales, Deadlocks, 53 p. (lire en ligne [PDF])
