computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...

, the ostrich algorithm is a strategy of ignoring potential problems on the basis that they may be exceedingly rare. It is named after the

ostrich effect In behavioral finance, the ostrich effect is the attempt made by investors to avoid negative financial information. The name comes from the common (but false) legend that ostriches bury their heads in the sand to avoid danger. Originally the term ...

which is defined as "to stick one's head in the sand and pretend there is no problem". It is used when it is more cost-effective to allow the problem to occur than to attempt its prevention.

Use with deadlocks

This approach may be used in dealing with

deadlock In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lo ...

s in

concurrent programming Concurrent means happening at the same time. Concurrency, concurrent, or concurrence may refer to: Law * Concurrence, in jurisprudence, the need to prove both ''actus reus'' and ''mens rea'' * Concurring opinion (also called a "concurrence"), a ...

if they are believed to be very rare and the cost of detection or prevention is high. For example, if each PC deadlocks once per 10 years, a single reboot may be less painful than the restrictions needed to prevent it. A set of processes is

ed if each process in the set is waiting for an event that only another process in the set can cause. Usually the event is the release of a currently held resource and none of the processes can run, release resources, and be awakened. The ostrich algorithm pretends there is no problem and is reasonable to use if deadlocks occur very rarely and the cost of their prevention would be high. The

UNIX Unix (; trademarked as UNIX) is a family of multitasking, multiuser computer operating systems that derive from the original AT&T Unix, whose development started in 1969 at the Bell Labs research center by Ken Thompson, Dennis Ritchie, a ...

and

Windows Windows is a group of several proprietary graphical operating system families developed and marketed by Microsoft. Each family caters to a certain sector of the computing industry. For example, Windows NT for consumers, Windows Server for ...

operating systems take this approach. Although using the ostrich algorithm is one of the methods of dealing with

s, other effective methods exist such as dynamic avoidance,

banker's algorithm Banker's algorithm, sometimes referred to as the detection algorithm, is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of predetermined maximum possible amount ...

, detection and recovery, and prevention.Middle East Technical University. Deadlocks.
/ref>

Trade-offs

Although efficient, using the Ostrich algorithm trades correctness for convenience. Yet since the algorithm directly deals with extreme cases it is not a large trade-off. In fact, the simplest and most used method to recover from a deadlock is a reboot. 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 In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are no ...

and the type-inference algorithm for

Standard ML Standard ML (SML) 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 ...

Quicksort Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...

is a sorting algorithm widely accepted as the fastest comparison based sorting algorithm has worst case performance on par with bubblesort which is widely regarded as one of the worst sorting algorithms, but this behavior is expected to occur only very rarely on certain types of input. Issues like

integer overflow In computer programming, an integer overflow occurs when an arithmetic operation attempts to create a numeric value that is outside of the range that can be represented with a given number of digits – either higher than the maximum or lower t ...

in programming languages with fixed-width integers are also frequently ignored because they occur only in exceptional cases that do not arise for practical inputs.

References

{{reflist

External links

Ostrich algorithmNon-Hard Locking Read-Write LockerDeadlock Basics + Modelling + Ostrich Algorithm
Concurrent algorithms

Use with deadlocks

Trade-offs

See also

References

External links