For all of the effort spent ensuring that this algorithm would be
correctly threadsafe, I messed up the order of operations within a
single thread when porting to the new approach.

Fix that up.

Also: fix some overzealous asserting in the testcases.  Since shutdown
is now lazy, we can never surely say !is_running at any particular point
in time.