Ostrich algorithm
Encyclopedia
In computer science
, the ostrich algorithm is a strategy of ignoring potential problems on the basis that they may be exceedingly rare - "to stick your head in the sand and pretend that 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 deadlock
s in concurrent programming if deadlocks are believed to be very rare, and if the cost of detection or prevention is high.
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.
An example can be found in the Non Hard-Locking ReadWriteLockerhttp://nohardlockrwlocker.codeplex.com/ site, where you have the option to determine where deadlocks might occur, and then turn off deadlock detection once you determine it doesn't need to be used.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the ostrich algorithm is a strategy of ignoring potential problems on the basis that they may be exceedingly rare - "to stick your head in the sand and pretend that 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 deadlock
Deadlock
A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
s in concurrent programming if deadlocks are believed to be very rare, and if the cost of detection or prevention is high.
Trade-offs
- Convenience
- Correctness
It is one of the methods of dealing with deadlocks. Other methods are: avoidance (banker's algorithm
Banker's algorithm
The Banker's algorithm is a resource allocation & deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of pre-determined maximum possible amounts of all resources, and then makes a "safe-state" check to test for possible deadlock conditions...
), 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
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....
and the type-checking algorithm for Standard ML
Standard ML
Standard ML is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.SML is a modern descendant of the ML...
. Issues like integer overflow
Integer overflow
In computer programming, an integer overflow occurs when an arithmetic operation attempts to create a numeric value that is too large to be represented within the available storage space. For instance, adding 1 to the largest value that can be represented constitutes an 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
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 ReadWriteLockerhttp://nohardlockrwlocker.codeplex.com/ site, where you have the option to determine where deadlocks might occur, and then turn off deadlock detection once you determine it doesn't need to be used.