Busy waiting
|
|
In software engineering, busy waiting is a technique where 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. In a multithreaded program, busy waiting is efficient if the threads are only likely to be waiting for a very short period of time, as it avoids the overhead of operating system process re-scheduling. For longer waits, it should be avoided, as the CPU time spent waiting could have been reassigned to another program.
| Contents |
Example C code
The C code below shows two threads that share a global integer i. The first thread uses a busy waiting to check for a change in the value of i.
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
int i; /* i is global, so it is visible to all functions. */
/* t1 uses spin lock to wait for i to change from 0. */
static void *f1()
{
while (i == 0) {} /* just keep checking over and over. */
printf("i's value has changed to %d.\n", i);
return NULL;
}
static void *f2()
{
sleep(60); /* sleep for 60 seconds. */
i = 99;
printf("t2 changing the value of i to %d.\n", i);
return NULL;
}
int main() {
int x;
pthread_t t1, t2;
i = 0; /* set global int i to 0. */
x = pthread_create(&t1, NULL, f1, NULL);
if (x != 0) printf("pthread foo failed.\n");
x = pthread_create(&t2, NULL, f2, NULL);
if (x != 0) printf("pthread bar failed.\n");
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("all pthreads finished.\n");
return 0;
}
You can compile the above code like so:
$ gcc 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 linux program uptime 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 changing 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
One alternative is using signals and the pause system call. We could change the above code so the first thread would pause, then the second thread will raise a signal to announce that it changed the value of i. The signal would cause the first thread to leave the paused state and resume execution.
See also
External links
- Description (http://www.opengroup.org/onlinepubs/009695399/functions/pthread_spin_lock.html) from The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition
- Citations from CiteSeer (http://citeseer.ist.psu.edu/cis?q=spin+and+lock)
- Article "User-Level Spin Locks - Threads, Processes & IPC (http://codeproject.com/threads/spinlocks.asp)" by Gert Boddaert
- Course "Introduction to Multiprocessors: Algorithms, Data Structures, and Programming - Spin Locks and Contention (http://www.cs.brown.edu/courses/cs176/spin.pdf)" by Maurice Herlihy and Nir Shavit
- Austria SpinLock Class Reference (http://austria.sourceforge.net/dox/html/classSpinLock.html)de:Aktives Warten