what's different between the Blocked and Busy Waiting?

Question

I known the implement of Busy Waiting. it's a death loop like this:

//main thread
while (true) {
    msg = msgQueue.next();
    msg.runnable.run();
}

//....msg queue
public Message next() {
    while (true) {
        if (!queue.isEmpty()) {
            return queue.dequeue();
        }
    }
}

so, the method "next()" just looks like blocked, actually it runs all the time. this was called "busy waiting" on book.

and what's the "process blocked"? what about its implement details? is a death loop too? or some others? like signal mechanism?

For instance: cat xxx | grep "abc"

process "cat" read a file and output them.

process "grep" waiting for input from "cat".

so before the "cat" output data, "grep" should be blocked, waiting for input and go on. what details about this "blocked", a death loop read the input stream all the time? or really stop running, waiting a signal to wake up it to run?

Maenad

Hello, everyone, now, I know what's differences:D, busy waiting is a loop, the cpu will execute it all the time, block is a kind of kernel/OS control, it won't waste cpu resource. – Maenad

Answer 1

The difference is basically in what happens to the process:

1. Busy Waiting

A process that is busy waiting is essentially continuously running, asking "Are we there yet? Are we there yet? How about now, are we there yet?" which consumes 100% of CPU cycles with this question:

bool are_we_there = false;
while(!are_we_there)
{
   // ask if we're there (without blocking)
    are_we_there = ask_if_we_are_there();
}

2. A process that is blocked (or that blocks)

A process that is blocked is suspended by the operating system and will be automatically notified when the data that it is waiting on becomes available. This cannot be accomplished without assistance from the operating system.

And example is a process that is waiting for a long-running I/O operation, or waiting for a timer to expire:

// use a system call to create a waitable timer
var timer = CreateWaitableTime()

// use another system call that waits on a waitable object
WaitFor(timer);  // this will block the current thread until the timer is signaled

// .. some time in the future, the timer might expire and it's object will be signaled
//    causing the WaitFor(timer) call to resume operation

UPDATE

Waitable objects may be implemented in different ways at the operating system level, but generally it's probably going to be a combination of hardware timers, interrupts and lists of waitable objects that are registered with the operating system by client code. When an interrupt occurs, the operating system's interrupt handler is called which in turn will scan though any waitable objects associated with that event, and invoke certain callback which in turn will eventually signal the waitable objects (put them in a signaled state). This is an over-simplification but if you'd like to learn more you could read up on interrupts and hardware timers.

Boo

umm... and OS how to do this? – Maenad

Answer 2

When you say "a process is blocked" you actually mean "a thread is blocked" because those are the only schedulable entities getting CPU time. When a thread is busy waiting, it wastes CPU time in a loop. When a thread is blocked, the kernel code inside the system call sees that data or lock is not immediately available so it marks the thread as waiting. It then jumps to the scheduler which picks up another thread ready for execution. Such a code in a blocking system call might look like this:

100:    if (data_available()) {
101:        return;
102:    } else {
103:        jump_to_scheduler();
104:    }

Later on the thread is rescheduled and restarts at line 100 but it immediately gets to the else branch and gets off the CPU again. When data becomes available, the system call finally returns.

Don't take this verbatim, it's my guess based on what I know about operating systems, but you should get the idea.

Savina