Ostrich algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computer science, the ostrich algorithm is a strategy of ignoring potential problems on the basis that they may be exceedingly rare. It is named for the ostrich effect, i.e. "to stick one's head in the sand and pretend there is no problem." This assumes that it is more cost-effective to allow the problem to occur than to attempt its prevention.

This approach may be used in dealing with deadlocks in concurrent programming if deadlocks are believed to be very rare, and if the cost of detection or prevention is high.

Trade-offs[edit]

  • Convenience
  • Correctness

It is one of the methods of dealing with deadlocks. Other methods are: avoidance (banker's algorithm), prevention, detection and recovery.

Some algorithms with poor worst-case performance are commonly used because they only exhibit poor performance on artificial cases that do not occur in practice; typical examples are the simplex algorithm and the type-checking algorithm for Standard ML. Issues like integer overflow in programming languages with fixed-width integers are also frequently ignored because they occur only in exceptional cases that don't arise for practical inputs.

Hybrid approach[edit]

Hybrid approach to using Ostrich algorithm is determining that the exceedingly rare case does not happen, and then switching from another costly algorithm to this one. The trade-off here is that if circumstances change or are unaccounted for, the rare problem may re-occur.

An example can be found in the Non Hard-Locking ReadWriteLocker site, where one has the option to determine where deadlocks might occur, and then turn off deadlock detection once one determines it doesn't need to be used.

References[edit]