Mutex Fairness Mitigation via Capacitors

Classic test-and-and-set locks\cite{tpds90-Anderson} are simple and exhibit low latency absent contention, and low handover latency under light contention, but may also admit long-term unfairness. Such unfairness can result in some threads starving, while other threads make progress resulting in a throughput disparity. This effect can persist over long periods. In turn, this can result in unpredictable performance, failure to adhere to service-level agreements (SLAs) and potential denial-of-service attacks \cite{CVE-DoS,eurosys20-patel}. We present \textbf{Capacitors}, a novel technique that allows an existing unfair lock algorithm, such as test-and-set locks, to be ``wrapped'' by a simple and efficient synchronization construct that enforces fairness, while still preserving desirable properties of the existing unfair lock.