Is it Really Busy Waiting If I Thread.Sleep()?

Question

My question is a bit nit-picky on definitions:

Can the code below be described as "busy waiting"? Despite the fact that it uses Thread.Sleep() to allow for context switching?

while (true) {
    if (work_is_ready){
        doWork();
    }
    Thread.Sleep(A_FEW_MILLISECONDS);
}

PS - The current definition for busy waiting in Wikipedia suggests that it is a "less wasteful" form of busy waiting.

Jehiel

Answer 1

Any polling loop, regardless of the time between polling operations, is a busy wait. Granted, sleeping a few milliseconds is a lot less "busy" than no sleep at all, but it still involves processing: thread context switches and some minimal condition checking.

A non-busy wait is a blocking call. The non-busy version of your example would involve waiting on a synchronization primitive such as an event or a condition variable. For example, this pseudocode:

// initialize an event to be set when work is ready
Event word_is_ready;
work_is_ready.Reset();

// in code that processes work items
while (true)
{
    work_is_ready.Wait();  // non-busy wait for work item
    do_work();
}

The difference here is that there is no periodic polling. The Wait call blocks and the thread is never scheduled until the event is set.

Millham

c2.com (it seems to be authoritive software design site) does not agree with you. Here are their examples: BusyWaiting: while ( MyFileIsNotReady() ) { //Do nothing } and Polling: while ( MyFileIsNotReady() ) { Sleep(1000); }. I see that sleep is the only difference. – Megen

Answer 2

That's not busy waiting. Busy waiting, or spinning, involves the opposite: avoiding context switching.

If you want to allow other threads to run, if and only if other threads are ready to run, to avoid deadlock scenarios in single threaded CPUs (e.g., the current thread needs work_is_ready to be set to true, but if this thread doesn't give up the processor and lets others run, it will never be set to true), you can use Thread.Sleep(0).

A much better option would be to use SpinWait.SpinUntil

SpinWait.SpinUntil(() => work_is_ready);
doWork();

SpinWait emits a special rep; nop (repeat no-op) or pause instruction that lets the processor know you're busy waiting, and is optimized for HyperThreading CPUs. Also, in single core CPUs, this will yield the processor immediately (because busy waiting is completely useless if there's only one core).

---

But spinning is only useful if you're absolutely sure you won't be waiting on a condition for longer than it would take the processor to switch the context out and back in again. I.e., no more than a few microseconds.

If you want to poll for a condition every few milliseconds, then you should use a blocking synchronization primitive, as the wiki page suggests. For your scenario, I'd recommend an AutoResetEvent, which blocks the thread upon calling WaitOne until the event has been signaled (i.e, the condition has become true).

Read also: Overview of Synchronization Primitives

Tuberculous

I don't think spinning going to be more efficient over the period of "a few milliseconds". A context switch takes the core about 30 microseconds; spinning would waste all of the core's CPU cycles during the entire wait-time (3mS == 30,000 microseconds). Spinning only makes sense where the time spent spinning will be less than the time it would take to do a context-switch. – Segmentation

@JeremyFriesner You're absolutely right, I didn't realize the OP meant to wait that long. I'll update my answer soon. – Tuberculous

Answer 3

It depends on the operating system and the exact number of milliseconds you are sleeping. If the sleep is sufficiently long that the operating system can switch to another task, populate its caches, and usefully run that task until your task is ready-to-run again, then it's not busy waiting. If not, then it is.

To criticize this code, I would say something like this: "This code may busy wait if the sleep is too small to allow the core to do useful work between checks. It should be changed so that the code that makes this code need to do work triggers that response."

This poor design creates a needless design problem -- how long should the sleep be? If it's too short, you busy wait. If it's too long, the work sits undone. Even if it's long enough that you don't busy wait, you force needless context switches.

Rayford

Answer 4

When your code is sleeping for a moment, technically it will be in sleep state freeing up a CPU. While in busy waiting your code is holding the CPU until condition is met.

Can the code below be described as "busy waiting"? Despite the fact that it uses Thread.Sleep() to allow for context switching?

It is not busy waiting, rather polling which is more performant that busy waiting. There is a difference between both

Simply put, Busy-waiting is blocking where as Polling is non-blocking.

Nissa

Answer 5

Busy waiting is something like this:

for(;;) {
  if (condition) {
      break;
  }
}

The condition could be "checking the current time" (for example performance counter polling). With this you can get a very accurate pause in your thread. This is useful for example for low level I/O (toggling GPIOs etc.). Because of this your thread is running all the time, and if you are on cooperative multi threading, the you are fully in control, how long the thread will stay in that wait for you. Usually this kind of threads have a high priority set and are uninterruptible.

Now a non-busy waiting means, the thread is non-busy. It allows another threads to execute, so there is a context switch. To allow a context switch, in most languages and OS you can simply use a sleep(). There are another similar functions, like yield(), wait(), select(), etc. It depends on OS and language, if they are non-busy or busy implemented. But in my experience in all cases a sleep > 0 was always non-busy.

Advantage of non-busy waiting is allowing another threads to run, which includes idle threads. With this your CPU can go into power saving mode, clock down, etc. It can also run another tasks. After the specified time the scheduler tries to go back to your thread. But is is just a try. It is not exact and it may be a little bit longer, than your sleep defines.

I think. This is clear now.

And now the big question: Is this busy, or non-busy waiting:

for(;;) {
  if (condition) {
      break;
  }
  sleep(1);
}

The answer is: is is a non-busy waiting. sleep(1) allows the thread to perform a context-switch.

Now the next question: Is the second for() busy, or non-busy waiting:

function wait() {
  for(;;) {
    if (condition) {
        break;
    }
  }
}

for(;;) {
  wait();
  if (condition) {
    break;
  }
  sleep(1);
}

It is hard to say. It depends on the real execution time of the wait() function. If it does nothing, then the CPU is almost the entire time in sleep(1). And this would be a non-blocking for-loop. But if wait() is a heavy calculation function without allowing a thread context switch, then this whole for-loop may become a blocking function, even if there is a sleep(1). Think of the worst-case: the wait() function is never returning back to caller, because the condition isn't hit for a long time.

This here is hard to answer, because we don't know the conditions. You can imagine the problem, where you cannot answer the question, because you don't know the conditions, in the following way:

if (unkonwnCondition) {
  for(;;) {
    if (condition) {
        break;
    }
  }
} else {
  for(;;) {
    if (condition) {
        break;
    }
    sleep(1);
  }
}

As you see, its the same: because you don't know the conditions, you cannot say if the wait is busy or non-busy.

Bimanous