Improving Pinwheel Density Bounds for Small Minimums

Abstract

The density bound for schedulability for general pinwheel instances is $\frac{5}{6}$, but density bounds better than $\frac{5}{6}$ can be shown for cases in which the minimum element $m$ of the instance is large. Several recent works have studied the question of the 'density gap' as a function of $m$, with best known lower and upper bounds of $O\left(\frac{1}{m}\right)$ and $O\left(\frac{1}{\sqrt{m}}\right)$. We prove a density bound of $0.84$ for $m=4$, the first $m$ for which a bound strictly better than $\frac{5}{6}=0.8\overline{3}$ can be proven. In doing so, we develop new techniques, particularly a fast heuristic-based pinwheel solver and an unfolding operation.