Busy-wait
   HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
and
software engineering Software engineering is a systematic engineering approach to software development. A software engineer is a person who applies the principles of software engineering to design, develop, maintain, test, and evaluate computer software. The term '' ...
, busy-waiting, busy-looping or spinning is a technique in which a
process A process is a series or set of activities that interact to produce a result; it may occur once-only or be recurrent or periodic. Things called a process include: Business and management *Business process, activities that produce a specific se ...
repeatedly checks to see if a condition is true, such as whether
keyboard Keyboard may refer to: Text input * Keyboard, part of a typewriter * Computer keyboard ** Keyboard layout, the software control of computer keyboards and their mapping ** Keyboard technology, computer keyboard hardware and firmware Music * Musi ...
input or a
lock Lock(s) may refer to: Common meanings *Lock and key, a mechanical device used to secure items of importance *Lock (water navigation), a device for boats to transit between different levels of water, as in a canal Arts and entertainment * ''Lock ...
is available. Spinning can also be used to generate an arbitrary time delay, a technique that was necessary on systems that lacked a method of waiting a specific length of time. Processor speeds vary greatly from computer to computer, especially as some processors are designed to dynamically adjust speed based on current workload. Consequently, spinning as a time-delay technique can produce unpredictable or even inconsistent results on different systems unless code is included to determine the time a processor takes to execute a "do nothing"
loop Loop or LOOP may refer to: Brands and enterprises * Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live * Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets * Loop Mobile, an ...
, or the looping code explicitly checks a
real-time clock A real-time clock (RTC) is an electronic device (most often in the form of an integrated circuit) that measures the passage of time. Although the term often refers to the devices in personal computers, servers and embedded systems, RTCs are pr ...
. In most cases spinning is considered an
anti-pattern An anti-pattern in software engineering, project management, and business processes is a common response to a recurring problem that is usually ineffective and risks being highly counterproductive. The term, coined in 1995 by computer programmer An ...
and should be avoided, as processor time that could be used to execute a different task is instead wasted on useless activity. Spinning can be a valid strategy in certain circumstances, most notably in the implementation of
spinlock In software engineering, a spinlock is a lock that causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking whether the lock is available. Since the thread remains active but is not performing a useful task, ...
s within operating systems designed to run on SMP systems.


Example C code

The following C code examples illustrate two threads that share a global
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
i. The first thread uses busy-waiting to check for a change in the value of i: #include #include #include #include #include /* i is global, so it is visible to all functions. It makes use of the special * type atomic_int, which allows atomic memory accesses. */ atomic_int i = 0; /* f1 uses a spinlock to wait for i to change from 0. */ static void *f1(void *p) static void *f2(void *p) int main() In a use case like this, one can consider using
C11 C11, C.XI, C-11 or C.11 may refer to: Transport * C-11 Fleetster, a 1920s American light transport aircraft for use of the United States Assistant Secretary of War * Fokker C.XI, a 1935 Dutch reconnaissance seaplane * LET C-11, a license-build var ...
's
condition variables In concurrent programming, a monitor is a synchronization construct that allows threads to have both mutual exclusion and the ability to wait (block) for a certain condition to become false. Monitors also have a mechanism for signaling other th ...
.


Alternatives

Most operating systems and threading libraries provide a variety of
system call In computing, a system call (commonly abbreviated to syscall) is the programmatic way in which a computer program requests a service from the operating system on which it is executed. This may include hardware-related services (for example, acc ...
s that will
block Block or blocked may refer to: Arts, entertainment and media Broadcasting * Block programming, the result of a programming strategy in broadcasting * W242BX, a radio station licensed to Greenville, South Carolina, United States known as ''96.3 ...
the process on an event, such as lock acquisition, timer changes, I/O availability or
signals In signal processing, a signal is a function that conveys information about a phenomenon. Any quantity that can vary over space or time can be used as a signal to share messages between observers. The ''IEEE Transactions on Signal Processing'' ...
. Using such calls generally produces the simplest, most efficient, fair, and
race Race, RACE or "The Race" may refer to: * Race (biology), an informal taxonomic classification within a species, generally within a sub-species * Race (human categorization), classification of humans into groups based on physical traits, and/or s ...
-free result. A single call checks, informs the scheduler of the event it is waiting for, inserts a
memory barrier In computing, a memory barrier, also known as a membar, memory fence or fence instruction, is a type of barrier instruction that causes a central processing unit (CPU) or compiler to enforce an ordering constraint on memory operations issued b ...
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 In real-time computing, priority inheritance is a method for eliminating unbounded priority inversion. Using this programming method, a process scheduling algorithm increases the priority of a process (A) to the maximum priority of any other proce ...
or other mechanisms to avoid
starvation Starvation is a severe deficiency in caloric energy intake, below the level needed to maintain an organism's life. It is the most extreme form of malnutrition. In humans, prolonged starvation can cause permanent organ damage and eventually, dea ...
. Busy-waiting itself can be made much less wasteful by using a delay function (e.g.,
sleep() A computer program (process, task, or thread) may sleep, which places it into an inactive state for a period of time. Eventually the expiration of an interval timer, or the receipt of a signal or interrupt causes the program to resume execution. ...
) found in 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 waste very little CPU time. In programs that never end (such as operating systems), infinite busy waiting can be implemented by using unconditional jumps as shown by this NASM syntax: jmp $. The CPU will unconditionally
jump Jumping is a form of locomotion or movement in which an organism or non-living (e.g., robotic) mechanical system propels itself through the air along a ballistic trajectory. Jump or Jumping also may refer to: Places * Jump, Kentucky or Jump S ...
to its own position forever. A busy wait like this can be replaced with: sleep: hlt jmp sleep For more information, see
HLT (x86 instruction) In the x86 computer architecture, HLT (halt) is an assembly language instruction which halts the central processing unit (CPU) until the next external interrupt is fired. Interrupts are signals sent by hardware devices to the CPU alerting it that ...
.


Appropriate usage

In low-level programming, busy-waits may actually be desirable. It may not be desirable or practical to implement interrupt-driven processing for every hardware device, particularly those that are seldom accessed. Sometimes it is necessary to write some sort of control data to hardware and then fetch device status resulting from the write operation, status that may not become valid until a number of machine cycles have elapsed following the write. The programmer could call an operating system delay function, but doing so may consume more time than would be expended in spinning for a few clock cycles waiting for the device to return its status.


See also

*
Polling (computer science) Polling, or polled operation, in computer science, refers to actively sampling the status of an external device by a client program as a synchronous activity. Polling is most often used in terms of input/output (), and is also referred to as p ...
*
Non-blocking I/O In computer science, asynchronous I/O (also non-sequential I/O) is a form of input/output processing that permits other processing to continue before the transmission has finished. A name used for asynchronous I/O in the Windows API is overlappe ...
*
Spinlock In software engineering, a spinlock is a lock that causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking whether the lock is available. Since the thread remains active but is not performing a useful task, ...
*
BogoMips BogoMips (from "bogus" and MIPS) is a crude measurement of CPU speed made by the Linux kernel when it boots to calibrate an internal busy-loop. An often-quoted definition of the term is "the number of million times per second a processor can do ...
*
volatile variable In computer programming, particularly in the C, C++, C#, and Java programming languages, the volatile keyword indicates that a value may change between different accesses, even if it does not appear to be modified. This keyword prevents an opti ...
*
Synchronization (computer science) In computer science, synchronization refers to one of two distinct but related concepts: synchronization of processes, and synchronization of data. ''Process synchronization'' refers to the idea that multiple processes are to join up or handshak ...
*
Peterson's algorithm Peterson's algorithm (or Peterson's solution) is a concurrent programming algorithm for mutual exclusion that allows two or more processes to share a single-use resource without conflict, using only shared memory for communication. It was formulated ...


References

{{Reflist


External links


Description
from The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition *Article
User-Level Spin Locks - Threads, Processes & IPC
by
Gert Boddaert Gert is a mainly masculine given name (Hypocorism, short form of Gerrit, Gerard, etc.) with some female bearers (short for Gertrude (given name), Gertrude). Since 1993 no one in Sweden has been baptised as Gert according to the Swedish Bureau o ...

Austria SpinLock Class Reference
Anti-patterns Concurrency control Articles with example C code