What is busy spin in a multi-threaded environment?

Question

What is "Busy Spin" in multi-threaded environment?

How it is useful and how can it be implemented in java in a multi-threaded environment?

In what way can it be useful in improving the performance of an application?

Atlanta

Generally speaking, it's pure evil. – Endrin

(Perhaps you could provide a reference where you saw that it was "useful".) – Endrin

Answer 1

Some of the other answers miss the real problem with busy waiting.

Unless you're talking about an application where you are concerned with conserving electrical power, then burning CPU time is not, in and of itself, a Bad Thing. It's only bad when there is some other thread or process that is ready-to-run. It's really bad when one of the ready-to-run threads is the thread that your busy-wait loop is waiting for.

That's the real issue. A normal, user-mode program running on a normal operating system has no control over which threads run on which processors, a normal operating system has no way to tell the difference between a thread that is busy waiting and a thread that is doing work, and even if the OS knew that the thread was busy-waiting, it would have no way to know what the thread was waiting for.

So, it's entirely possible for the busy waiter to wait for many milliseconds (practically an eternity), waiting for an event, while the the only thread that could make the event happen sits on the sideline (i.e., in the run queue) waiting for its turn to use a CPU.

Busy waiting is often used in systems where there is tight control over which threads run on which processors. Busy waiting can be the most efficient way to wait for an event when you know that the thread that will cause it is actually running on a different processor. That often is the case when you're writing code for the operating system itself, or when you're writing an embedded, real-time application that runs under a real-time operating system.

---

Kevin Walters wrote about the case where the time to wait is very short. A CPU-bound, ordinary program running on an ordinary OS may be allowed to execute millions of instructions in each time slice. So, if the program uses a spin-lock to protect a critical section consisting of just a few instructions, then it is highly unlikely that any thread will lose its time slice while it is in the critical section. That means, if thread A finds the spin-lock locked, then it is highly likely that thread B, which holds the lock, actually is running on a different CPU. That's why it can be OK to use spin-locks in an ordinary program when you know it's going to run on a multi-processor host.

Anopheles

Answer 2

Busy spin is one of the techniques to wait for events without releasing CPU. It's often done to avoid losing data in CPU cached which is lost if the thread is paused and resumed in some other core.

So, if you are working on a low latency system where your order processing thread currently doesn't have any order, instead of sleeping or calling wait(), you can just loop and then again check the queue for new messages. It's only beneficial if you need to wait for a very small amount of time e.g. in microseconds or nanoseconds.

LMAX Disrupter framework, a high-performance inter-thread messaging library has a BusySpinWaitStrategy which is based on this concept and uses a busy spin loop for EventProcessors waiting on the barrier.

Drambuie

Answer 3

Busy-waiting or spinning is a technique in which a process repeatedly checks to see if a condition is true instead of calling wait or sleep method and releasing CPU.

1.It is mainly useful in multicore processor where condition is going to be true quite quickly i.e. in millisecond or micro second

2.Advantage of not releasing CPU is that, all cached data and instruction are remained unaffected, which may be lost, had this thread is suspended on one core and brought back to another thread

Boatel

Answer 4

A "busy spin" is constantly looping in one thread to see if the other thread has completed some work. It is a "Bad Idea" as it consumes resources as it is just waiting. The busiest of spins don't even have a sleep in them, but spin as fast as possible waiting for the work to get finished. It is less wasteful to have the waiting thread notified by the completion of the work directly and just let it sleep until then.

Note, I call this a "Bad Idea", but it is used in some cases on low-level code to minimize latency, but this is rarely (if ever) needed in Java code.

Willful

thanks to the reply , here you mean to say , signaling is better(using wait and notify/notifyAll) , rather than busy spin ? actually i am not getting why this busy spin come into the picture in the case thread waiting scenario . – Atlanta

Lets say you have a bunch of producer threads pushing work items into a (synchronized) queue and you have one consumer thread popping items out of the queue to service them. When the queue is empty your consumer thread should not be polling the queue for work items. Instead, signal the consumer in some way when a new item is added. – Center

@Center , polling(i think it is bust spin here) , is then unnecessary CPU resource consumer , which just continuously checking for the queue which holds the items. Actually i saw in some this disruptor please correct me , if it is different . – Atlanta

@Atlanta The disruptor you mention is actually a good example for this answer: it has both the busy spin implementation (high CPU usage) and an alternative wait for notification implementation (low CPU usage). – Roaring

Answer 5

Spin Waiting is that you constantly wait for a condition comes true. The opposite is waiting for a signal (like thread interruption by notify() and wait()).

There are two ways of waiting, first semi-active (sleep / yield) and active (busy waiting).

On busy waiting a program idles actively using special op codes like HLT or NOP or other time consuming operations. Other use just a while loop checking for a condition comming true.

The JavaFramework provides Thread.sleep, Thread.yield and LockSupport.parkXXX() methods for a thread to hand over the cpu. Sleep waits for a specific amount of time but alwasy takes over a millisecond even if a nano second was specified. The same is true for LockSupport.parkNanos(1). Thread.yield allows for a resolution of 100ns for my example system (win7 + i5 mobile).

The problem with yield is the way it works. If the system is utilized fully yield can take up to 800ms in my test scenario (100 worker threads all counting up a number (a+=a;) indefinitively). Since yield frees the cpu and adds the thread to the end of all threads within its priority group, yield is therefore unstable unless the cpu is not utilized to a certain extend.

Busy waiting will block a CPU (core) for multiple milliseconds.

The Java Framework (check Condition class implementations) uses active (busy) wait for periodes less then 1000ns (1 microsecond). At my system an average invocation of System.nanoTime takes 160ns so busy waiting is like checking the condition spend 160ns on nanoTime and repeat.

So basically the concurrency framework of Java (queues etc) has something like wait under a microsecond spin and hit the waiting periode within a N granulairty where N is the number of nanoseconds for checking time constraints and wait for one ms or longer (for my current system).

So active busy waiting increases utilization but aid in the overall reactiveness of the system.

While burning CPU time one should use special instructions reducing the power consumption of the core executing the time consuming operations.

Aciculum

Answer 6

Busy spinning/waiting is normally a bad idea from a performance standpoint. In most cases, it is preferable to sleep and wait for a signal when you are ready to run, than to do spinning. Take the scenario where there are two threads, and thread 1 is waiting for thread 2 to set a variable (say, it waits until var == true. Then, it would busy spin by just doing

while (var == false)
    ;

In this case, you will take up a lot of time that thread 2 can potentially be running, because when you wake up you are just executing the loop mindlessly. So, in a scenario where you are waiting for something like this to happen, it is better to let thread 2 have all control by putting yourself to sleep and having it wake you up when it is done.

BUT, in rare cases where the time you need to wait is very short, it is actually faster to spinlock. This is because of the time it takes to perform the signalng functions; spinning is preferable if the time used spinning is less than the time it would take to perform the signaling. So, in that way it may be beneficial and could actually improve performance, but this is definitely not the most frequent case.

Prosperity

Would while (var == false) Thread.yield(); be good when the time to wait is short instead of very short? Or is there no (good) case for Thread.yield() when spinning? – Roaring

Answer 7

Busy spin is nothing but looping over until thread(s) completes. E.g. You have say 10 threads, and you want to wait all the thread to finish and then want to continue,

while(ALL_THREADS_ARE_NOT_COMPLETE);
//Continue with rest of the logic

For example in java you can manage multiple thread with ExecutorService

    ExecutorService executor = Executors.newFixedThreadPool(10);
    for (int i = 0; i < 10; i++) {
        Runnable worker = new WorkerThread('' + i);
        executor.execute(worker);
    }
    executor.shutdown();
    //With this loop, you are looping over till threads doesn't finish.
    while (!executor.isTerminated());

It is a to busy spins as it consumes resources as CPU is not sitting ideal, but keeping running over the loop. We should have mechanism to notify the main thread (parent thread) to indicate that all thread are done and it can continue with the rest of the task.

With the preceding example, instead of having busy spin, you can use different mechanism to improve performance.

   ExecutorService executor = Executors.newFixedThreadPool(10);
    for (int i = 0; i < 10; i++) {
        Runnable worker = new WorkerThread('' + i);
        executor.execute(worker);
    }
    executor.shutdown();
    try {
           executor.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS);
    } catch (InterruptedException e) {
        log.fatal("Exception ",e);
    }

Obaza

We have the countDownLatch or cyclicbarrier or even we have the join method for this to achieve , may i know in what way this busy waiting is more better than above said sync tools provided in built by jdk – Atlanta