  We consider scheduling in the M/G/1 queue with unknown job sizes. It is known
that the Gittins policy minimizes mean response time in this setting. However,
the behavior of the tail of response time under Gittins is poorly understood,
even in the large-response-time limit. Characterizing Gittins's asymptotic tail
behavior is important because if Gittins has optimal tail asymptotics, then it
simultaneously provides optimal mean response time and good tail performance.
  In this work, we give the first comprehensive account of Gittins's asymptotic
tail behavior. For heavy-tailed job sizes, we find that Gittins always has
asymptotically optimal tail. The story for light-tailed job sizes is less
clear-cut: Gittins's tail can be optimal, pessimal, or in between. To remedy
this, we show that a modification of Gittins avoids pessimal tail behavior
while achieving near-optimal mean response time.
