Busy waiting

In software engineering, busy-waiting, busy-looping or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input or a 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 external factors, such as the load on the operating system. As such, spinning as a time delay technique often produces unpredictable or even inconsistent results unless code is implemented to determine how quickly the processor can execute a "do nothing" loop, or the looping code explicitly checks a real-time clock.

Spinning can be a valid strategy in certain circumstances, most notably in the implementation of spinlocks within operating systems designed to run on SMP systems. In general, however, spinning is considered an anti-pattern and should be avoided,[1] as processor time that could be used to execute a different task is instead wasted on useless activity.

Example C code

The following C code examples illustrate 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 <pthread.h>
#include <unistd.h>
#include <stdlib.h>
 
volatile int i = 0; /* i is global, so it is visible to all functions.
                       It's also marked volatile, because it
                       may change in a way which is not predictable by the compiler,
                       here from a different thread. Thus preventing the compiler from
                       caching its value.*/
 
/* f1 uses a spinlock to wait for i to change from 0. */
static void *f1(void *p)
{
    while (i==0) {
        /* do nothing - just keep checking over and over */
    } 
    printf("i's value has changed to %d.\n", i);
    return NULL;
}

static void *f2(void *p)
{
    sleep(60);   /* sleep for 60 seconds */
    i = 99;
    printf("t2 has changed the value of i to %d.\n", i);
    return NULL;
}

int main()
{
    int rc;
    pthread_t t1, t2;

    rc = pthread_create(&t1, NULL, f1, NULL);
    if (rc != 0) {
        fprintf(stderr,"pthread f1 failed\n");
        return EXIT_FAILURE;
    }
 
    rc = pthread_create(&t2, NULL, f2, NULL);
    if (rc != 0) {
        fprintf(stderr,"pthread f2 failed\n");
        return EXIT_FAILURE;
    }
 
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    puts("All pthreads finished.");
    return 0;
}

In a use case like this, one can consider using C11's condition variables.

Alternatives

Most operating systems and threading libraries provide a variety of system calls that will block the process on an event, such as lock acquisition, timer changes, I/O availability or signals. Using such calls generally produces the simplest, most efficient, fair, and race-free result. 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 (e.g., sleep()) 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 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).

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

  1. ↑ https://www.kernel.org/doc/Documentation/volatile-considered-harmful.txt
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.