Страусиный алгоритм - Ostrich algorithm

В Информатика, то страусиный алгоритм это стратегия игнорирования потенциальных проблем на том основании, что они могут быть чрезвычайно редкими. Он назван в честь эффект страуса что определяется как «засунуть голову в песок и сделать вид, что проблем нет». Он используется, когда более рентабельно допустить возникновение проблемы, чем пытаться ее предотвратить.

Использование с тупиками

Этот подход можно использовать при работе с тупиковые ситуации в параллельное программирование если считается, что они очень редки и их обнаружение или предотвращение обходятся дорого. Например, если каждый компьютер блокируется один раз в 10 лет, одна перезагрузка может быть менее болезненной, чем ограничения, необходимые для ее предотвращения.[1]

Набор процессов тупиковый если каждый процесс в наборе ожидает события, которое может вызвать только другой процесс в наборе. Обычно событие - это освобождение текущего удерживаемого ресурса, и ни один из процессов не может работать, освобождать ресурсы и пробуждаться.[2]

Алгоритм "страус" делает вид, что проблем нет, и его разумно использовать, если тупиковые ситуации возникают очень редко и стоимость их предотвращения будет высокой. В UNIX и Windows операционные системы используют этот подход.[3][нужен лучший источник ]

Хотя использование страусиного алгоритма - один из методов борьбы с тупиковые ситуации существуют другие эффективные методы, такие как динамическое избегание, алгоритм банкира, обнаружение и восстановление и предотвращение.[4]

Компромиссы

Хотя алгоритм Страуса эффективен, он торгует правильностью ради удобства. Тем не менее, поскольку алгоритм напрямую работает с крайними случаями, это не большой компромисс. Фактически, самый простой и наиболее часто используемый метод выхода из тупика - это перезагрузка.

Некоторые алгоритмы с плохой производительностью в худшем случае обычно используются, потому что они показывают плохую производительность только в искусственных случаях, которые не встречаются на практике; типичными примерами являются симплексный алгоритм и алгоритм вывода типов для Стандартный ML. Проблемы вроде целочисленное переполнение в языках программирования с целыми числами фиксированной ширины также часто игнорируются, потому что они возникают только в исключительных случаях, которые не возникают для практических входов.

Смотрите также

использованная литература

Заметки

  1. ^ Готтлиб, Аллан. "Операционные системы." Конспект лекций по ОС. Н.п, 2015. Пт. 8 января 2015 г. http://cs.nyu.edu/~gottlieb/courses/os/class-notes.html#ostrich
  2. ^ Университет Нового Южного Уэльса. https://cgi.cse.unsw.edu.au/~cs3231/14s1/lectures/lect05.pdf
  3. ^ Международный университет Флориды. Вычислительные и информационные науки. http://users.cis.fiu.edu/~sadjadi/Teaching/Operating%20Systems/Lectures/Chapter-03.ppt
  4. ^ Ближневосточный технический университет. http://www.ceng.metu.edu.tr/~genc/334/Ch_6_Deadlocks.ppt Тупики.