Busy waiting

In software engineering, busy waiting or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as waiting for keyboard input or waiting for a lock to become available. It can also be used to delay execution for some amount of time; this was necessary on old computers that had no method of waiting a specific length of time other than by repeating a useless loop a specific number of times, but on modern computers with clocks and different processor speeds, this form of time delay is often inaccurate and a sign of a naïve attempt at programming. Spinning can be a valid strategy in certain special circumstances, most notably in the implementation of spinlocks within operating systems designed to run on SMP systems. In general, however, it is considered an anti-pattern and should be avoided, as the CPU time spent waiting could have been reassigned to another task.

Example C code

The C code below shows two threads that share a global integer i. The first thread uses busy waiting to check for a change in the value of i.

#include <stdio.h> #include #include volatile int i = 0; /* i is global, so it is visible to all functions. It's also marked volatile, because it will change in a way which is not predictable by the compiler (here: from a different thread). */ /* t1 uses a spinlock to wait for i to change from 0. */ static void *f1() { while (i=0) { /* do nothing - just keep checking over and over */ } printf("i's value has changed to %d. ", i); return NULL; } static void *f2() { sleep(60); /* sleep for 60 seconds */ i = 99; printf("t2 has changed the value of i to %d. ", i); return NULL; } int main() { int rc; pthread_t t1, t2; rc = pthread_create(&t1, NULL, f1, NULL); if (rc != 0) puts("pthread foo failed."); rc = pthread_create(&t2, NULL, f2, NULL); if (rc != 0) puts("pthread bar failed."); pthread_join(t1, NULL); pthread_join(t2, NULL); puts("All pthreads finished."); return 0; }

On a Unix-like system, you can compile the above code like this: $ cc spinlock.c -lpthread

CPU utilization

In the above code, the second thread immediately goes to sleep for 60 seconds. Meanwhile, the first thread checks repeatedly if the second thread has changed the value of i.

You can use the top or uptime utility found on Unix-like operating systems to see how this program utilizes the CPU. Run the program like this: $ uptime; ./a.out ; uptime 13:25:47 up 53 days, 23:50, 4 users, load average: 0.00, 0.00, 0.00 t2 has changed the value of i to 99. i's value has changed to 99. All pthreads finished. 13:26:47 up 53 days, 23:51, 4 users, load average: 0.75, 0.21, 0.07

Of course, every system will return slightly different numbers, but the important thing to notice is that before we ran the program, the system load average for the previous 60 seconds was 0.00. After the program ran, the system load average bumped up to 0.75 for the last minute.

Alternatives to busy waiting

Most operating systems and threading libraries provide a wide set of system calls which will block the process on an event, such as lock acquisitions, timers, I/O availability, or signals. This is often the simplest, most efficient, fair, and race-free way. A single call checks, informs the scheduler of the event it is waiting for, inserts a memory barrier where applicable, and may perform a requested I/O operation before returning. Other processes can use the CPU while the caller is blocked. The scheduler is given the information needed to implement priority inheritance or other mechanisms to avoid starvation.

Busy waiting itself can be made much less wasteful by using a "delay" function found on most operating systems. This puts a thread to sleep for a specified time, during which the thread will waste no CPU time. If the loop is checking something simple then it will spend most of its time asleep and will not waste a large proportion of the available CPU time. It will still consume some CPU time though.

When busy waits are appropriate

In low-level hardware driver programming, sometimes busy waits are actually desirable. It is not practical to implement hardware interrupt-based signalling for every hardware device, particularly for devices that are seldom accessed. Sometimes it is necessary to write some sort of control data to a hardware device and then read back some sort of status data, which is not valid until several, perhaps even tens of clock cycles later. The programmer could call an operating system delay function, but more time would be spent simply performing the function call (let alone switching to an interim thread) than is required by the hardware. In such cases, it is common to implement a busy wait that keeps reading the status data until it is valid. Calling a delay function in this case would actually waste CPU time due to the comparatively large overhead involved in the function call and context switching.

ee also

*BogoMips
*Polling (computer science)
*Spinlock
*Synchronization

External links

* [http://www.opengroup.org/onlinepubs/009695399/functions/pthread_spin_lock.html Description] from The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition
*Article " [http://codeproject.com/threads/spinlocks.asp User-Level Spin Locks - Threads, Processes & IPC] " by Gert Boddaert
*Course " [http://www.cs.brown.edu/courses/cs176/spin.pdf Introduction to Multiprocessors: Algorithms, Data Structures, and Programming - Spin Locks and Contention] " by Maurice Herlihy and Nir Shavit
* [http://austria.sourceforge.net/dox/html/classSpinLock.html Austria SpinLock Class Reference]