|
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 should be avoided, as the CPU time spent waiting could have been reassigned to another task. Wikipedia does not have an article with this exact name. ...
In computer science the term Polling refers to actively sampling the status of an external device by a client program as a synchronous activity. ...
Software Engineering (SE) is the design, development, and documentation of software by applying technologies and practices from computer science, project management, engineering, application domains, interface design, digital asset management and other fields. ...
In computing, a process is a running instance of a program, including all variables and other states. ...
It has been suggested that IBM PC keyboard be merged into this article or section. ...
The term input has a variety of uses in different fields. ...
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. ...
In software engineering, a spinlock is a lock where the thread simply waits in a loop (spins) repeatedly checking until the lock becomes available. ...
Symmetric Multiprocessing, or SMP, is a multiprocessor computer architecture where two or more identical processors are connected to a single shared main memory. ...
CPU redirects here. ...
A thread in computer science is short for a thread of execution. ...
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. Look up C, c in Wiktionary, the free dictionary. ...
The integers are commonly denoted by the above symbol. ...
#include <stdio.h> #include <pthread.h> #include <unistd.h> volatile int i; /* 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 spin lock 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.n", i); return; } static void *f2() { sleep(60); /* sleep for 60 seconds. */ i = 99; printf("t2 changing the value of i to %d.n", i); return; } 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; } On a Unix-like system, you can compile the above code like so: $ 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: A Unix-like operating system is one that behaves in a manner similar to a Unix system, while not necessarily conforming to or being certified to any version of the Single UNIX Specification. ...
$ 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 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. In computing, a system call is the mechanism used by an application program to request service from the operating system, or more specifically, the operating system kernel. ...
In a multitasking computer system, processes may occupy a variety of states. ...
A signal is an asynchronous event transmitted between one process and another. ...
A race hazard (or race condition) is a flaw in a system or process where the output exhibits unexpected critical dependence on the relative timing of events. ...
Memory barrier, also known as membar or memory fence is a name for a class of instructions for a computer in computer architecture. ...
In computer science, priority inheritance is a method for eliminating priority inversion problems. ...
In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. ...
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 thread switching.
See also Synchronization is a problem in timekeeping which requires the coordination of events to operate a system in unison. ...
In software engineering, a spinlock is a lock where the thread simply waits in a loop (spins) repeatedly checking until the lock becomes available. ...
BogoMips (from bogus and MIPS) is an unscientific measurement of CPU speed made by the Linux kernel when it boots, to calibrate an internal busy-loop. ...
External links - Description from The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition
- Citations from CiteSeer
- Article "User-Level Spin Locks - Threads, Processes & IPC" by Gert Boddaert
- Course "Introduction to Multiprocessors: Algorithms, Data Structures, and Programming - Spin Locks and Contention" by Maurice Herlihy and Nir Shavit
- Austria SpinLock Class Reference
|
Feeds |
Contact