Algorithme de l'autruche

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].

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.

• (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).

• Principe de bout en bout