Hmmm; the Linux 2.6 scheduler does seem to have per-CPU run queues. That surprises me, since generally single-queue multi-server is much fairer and more efficient at allocating fungible resources. However, possibly the benefits of CPU affinity (mostly hot cache contents) trump that. And it's preemptive. So your task should in fact hit a cpu immediately (bumping the long-running task, whose priority will have been gradually raised (higher number, lower precedence)).

So yeah, there's something to explain there.

You're not short of memory for what's running, are you?