Editing Thundering herd problem

{{short description|Resource allocation problem in computer science}}
In [[computer science]], the '''thundering herd problem''' occurs when a large number of processes or threads waiting for an event are awakened when that event occurs, but only one process is able to handle the event. When the processes wake up, they will each try to handle the event, but only one will win. All processes will compete for resources, possibly freezing the computer, until the herd is calmed down again.<ref>{{cite web |title=Thundering Herd Problem |url=http://www.catb.org/jargon/html/T/thundering-herd-problem.html |website=The Jargon File (version 4.4.7) |accessdate=9 July 2019}}</ref>

== Mitigation ==
The Linux kernel serializes responses for requests to a single file descriptor, so only one thread or process is woken up.<ref>{{cite web |url=https://stackoverflow.com/a/23002010/56280|title=Does the Thundering Herd Problem exist on Linux anymore|website=stackoverflow.com|access-date=2019-07-09}}</ref> For epoll() in version 4.5 of the Linux kernel, the EPOLLEXCLUSIVE flag was added. Thus several epoll sets (different threads or different processes) may wait on the same resource and only one set will be woken up.  For certain workloads this flag can give significant processing time reduction.<ref>{{Cite web|last=Madars|first=Vitolins|date=2015-12-05|title=EPOLLEXCLUSIVE Linux Kernel patch testing|url=https://mvitolin.wordpress.com/2015/12/05/endurox-testing-epollexclusive-flag/|archive-url=|archive-date=|access-date=2020-08-11|website=mvitolin|language=en}}</ref>

Similarly in Microsoft Windows, [[Input/output completion port|I/O completion ports]] can mitigate the thundering herd problem, as they can be configured such that only one of the threads waiting on the completion port is woken up when an event occurs.<ref>{{Cite web|url=https://xania.org/200807/iocp|title=IO Completion Ports — Matt Godbolt's blog |website=xania.org|access-date=2019-01-23}}</ref>

In systems that rely on a backoff mechanism (e.g. [[exponential backoff]]), the clients will retry failed calls by waiting a specific amount of time between consecutive retries. In order to avoid the thundering herd problem, [[jitter]] can be purposefully introduced in order to break the synchronization across the clients, thereby avoiding collisions. In this approach, randomness is added to the wait intervals between retries, so that clients are no longer synchronized.

== See also ==

* [[Process management (computing)]]
* [[Lock convoy]]
* [[Sleeping barber problem]]
* [[TCP global synchronization]]
* [[Cache stampede]]

==References==
<references />

==External links==
* [https://lkml.org/lkml/2004/5/2/108 A discussion of this observation on Linux]
* [https://www.baeldung.com/resilience4j-backoff-jitter Better Retries with Exponential Backoff and Jitter]
[[Category:Concurrency control]]