Busy waiting

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]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Busy-Waiting — Aktives Warten auch busy waiting genannt bezeichnet eine Aktivität eines Programms, mit der die Zeit bis zur Erfüllung einer Bedingung aktiv durch Ausführung von Anweisungen, welche den Zustand des Programms nicht verändern, überbrückt wird.… …   Deutsch Wikipedia

  • Busy Waiting — Aktives Warten auch busy waiting genannt bezeichnet eine Aktivität eines Programms, mit der die Zeit bis zur Erfüllung einer Bedingung aktiv durch Ausführung von Anweisungen, welche den Zustand des Programms nicht verändern, überbrückt wird.… …   Deutsch Wikipedia

  • busy — bus|y1 [ bızi ] adjective *** 1. ) having many things to do: The parents of young children are always busy. a busy doctor He is an extremely busy man. busy with: Irina and Marcus were busy with preparations for their wedding. a ) not able to do a …   Usage of the words and phrases in modern English

  • busy — I UK [ˈbɪzɪ] / US adjective Word forms busy : adjective busy comparative busier superlative busiest *** Metaphor: Being very busy at work is like being covered with things or surrounded by something such as water or the ground, so that you cannot …   English dictionary

  • Busy line interrupt — is a function on land line telephones that allows a caller to interrupt a phone conversation of another caller, [ [http://www.icc.illinois.gov/downloads/public/edocket/115077.pdf INWARD ASSISTANCE OPERATOR SERVICES] ] especially one who does not… …   Wikipedia

  • Waiting For Now — Infobox Album | Name = Waiting For Now Type = Album Artist = Bryan Greenberg Released = March 23rd, 2007 Genre = Alternative Writer = Bryan Greenberg Last album = Waiting For Now (2007) Next album = Hmmm... Single (2007) Misc = Extra album cover… …   Wikipedia

  • All the Plans or Boy In Waiting — Infobox Album Name = All the plans or Boy In Waiting Type = studio Artist = Starsailor Released = Start date|2009 Recorded = 2007 2008 Genre = Alternative rock, Piano rock Length = Label = EMI ] Producer = Steve Osborne Reviews = Last album = On… …   Wikipedia

  • Call waiting — (or catch phone in Japan), in telephony, is a feature on some telephone networks. If a calling party places a call to a called party which is otherwise engaged, and the called party has the call waiting feature enabled, the called party is able… …   Wikipedia

  • My Love Is Waiting — Single by Marvin Gaye from the album Midnight Love Released 1983 Recorded Ohain, Belgium (Studio Katy), 1982 …   Wikipedia

  • Camp-on busy signal — In telecommunication, the term camp on busy signal has the following meanings: *A signal that informs a busy telephone user that another call originator is waiting for a connection. Synonym: call waiting *A teleprinter exchange facility signal… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”