Tickless kernels: Race conditions with the HLT instruction

[Cinolt]

Hello, I'm still in the process of getting down some of the theory regarding OS development.

The notion of the "tickless" kernel was interesting to me. Instead of having interrupts fired every so often, the kernel can simply issue a HLT instruction when all processes are waiting for something (like a disk controller to provide disk data to a buffer), and let interrupts come in to continue whatever it was waiting on.

But what about this scenario:

Code: Select all

request_disk_data();
issue_hlt();

Probably in most cases, the interrupt will come AFTER issue_hlt(), but what about if the interrupt comes AFTER request_disk_data() but BEFORE issue_hlt()? After receiving the interrupt, the kernel will potentially HLT for a long time if no other interrupts come in.

How do tickless kernels handle this scenario?

[dchapiesky]

a tickless kernel always has at least one scheduler running....

[Schol-R-LEA]

Two things to keep in mind about a tickless kernel, as well:

First, they don't get a 'heartbeat' for time slices, meaning that for applications, you have to assume cooperative multitasking as a degenerate case - if no interrupts occurred, the scheduling will only occur if a process cedes the processor. This is similar to how multitasking worked in MacOS prior to System 9 (which I think was fully pre-emptive; OS X certainly is, but it is based on a completely different kernel and codebase), and fully ensuring either fair scheduling or priority scheduling would require that compilers for it insert ceding calls to the scheduler (sleep, nice, what have you). It also means that a process that hangs, will continue to hang unless an interrupt is processed.

Second, it means that anything that needs to process a period of time needs to explicitly set a timer, complicating the implementation of a wait() or sleep() type system call.

[Brendan]

Hi,

But what about this scenario:

Code: Select all

request_disk_data();
issue_hlt();

That scenario is broken ("issue_hlt();" should not be used here).

First, consider the simpler case of asynchronous/non-blocking IO. A task asks the kernel to transfer some data to/from disk, the request gets put on some kind of queue, and the kernel returns back to the task. Eventually (possibly after many other requests for other tasks are finished) the request makes its way to the head of the disk driver's queue and is started, then finished. When the request is finished you send some kind of notification back to the task that made the request. This is simpler because it doesn't have anything (directly) to do with task switches or the scheduler or any timer.

For synchronous/blocking IO, it's similar. A task asks the kernel to transfer some data to/from disk (same as non-blocking), the request gets put on some kind of queue (same as non-blocking), eventually the request makes its way to the head of the disk driver's queue and is started then finished (same as non-blocking). The only difference is that after making the request you ask the scheduler to make the task block (so it gets no CPU time), and when the request is completed you unblock the task (instead of sending some sort of notification back to the task).

Notice that nothing I mentioned above (for both non-blocking and blocking) involves any "issue_hlt();".

Now, assume that your scheduler has some kind of "block_task()" function. When this is called the scheduler tries to find some other task to give CPU time. If there are no other tasks that want the CPU, then the CPU is idle. This is where "issue_hlt();" would be used - to wait until any IRQ handler to unblock a task. It doesn't matter if the IRQ is a timer IRQ where the IRQ handler unblocks a task that called "sleep()", or if the IRQ is a disk controller IRQ where the IRQ handler unblocks a task that was waiting for disk IO to complete.

The scheduler itself might use a timer to determine when the currently running task has used all the time it was given. This has nothing to do with "issue_hlt();" because "issue_hlt();" is only ever used (by the scheduler) when there is no task running.

Also note that "no task running" is important for power management, and the "issue_hlt();" is like a temporary placeholder. Eventually you'll want to use a simple loop for a brief amount of time (in the hope that a task unblocks very soon), then after being idle for a little while drop the CPU speed down and do "issue_hlt();" for a while, then after being idle for even longer drop the CPU speed down even more and do "issue_hlt();". Eventually, after CPU has been idle for long enough, you might put the CPU into a very deep sleep state (possibly including "effectively turned off" where you have to do the "INIT-SIPI-SIPI" sequence to get it back online). For power management it can also be nice to have some look-ahead - for example, check if a task that called "sleep()" will wake up soon before you decide to drop the CPU speed down (and if a task will wake up soon, leave the CPU speed how it is, or maybe increase CPU speed instead of reducing CPU speed).

Note: Before power management mattered; some OSs (including mine) used an "idle task" that never blocks. This made it easier to write the scheduler because the "no task running" was impossible. However, it's extremely difficult to implement power management properly if you have an "idle task" (you end up with a huge mess of race conditions, etc) so I'd recommend not using an "idle task" (even if you have no intention of supporting power management yet).


Cheers,

Brendan

[OSwhatever]

Probably in most cases, the interrupt will come AFTER issue_hlt(), but what about if the interrupt comes AFTER request_disk_data() but BEFORE issue_hlt()? After receiving the interrupt, the kernel will potentially HLT for a long time if no other interrupts come in.

How do tickless kernels handle this scenario?

This is not a problem. The interrupt controller will raise the interrupt line and the hlt instruction will exit immediately. Interrupts are lowered when they are acknowledged, usually both to the interrupt controller and device that caused the interrupt needs to be acknowledged;

[DavidCooper]

I asked the same question last year, and tsdnz answered it like this:-

After enable interrupts one instruction will be executed without interrupts.

Use assembly: sti; hlt;

https://www.tptp.cc/mirrors/siyobik.inf ... n/STI.html

That gives you a simple way to avoid the problem (you can check to see if there's work to be done while interrupts are disabled for a moment, then enable interrupts again and go straight into the halt instruction before an interrupt is allowed to act), but another way is for the interrupt routine to force a task switch which prevents the return from the interrupt coming back to the bit of code containing the hlt instruction (which should only exist in an idle task that runs if there's no work needing to be done - this task is nothing more than a hlt instruction built into an infinite loop) - as soon as there's work to do, that task is switched out and the hlt cannot run until that idle task is switched back in.

[Cinolt]

Thank you all for the input.

I should have clarified that for starters I only wanted to consider the case of a "single-task" system like DOS rather than multi-tasking like Linux/Windows (perhaps I was a bit misleading in OP). So indeed I assume there is no "scheduler". And as DavidCooper pointed out the STI HLT sequence removes the race condition I was worried about.

[Korona]

First, they don't get a 'heartbeat' for time slices, meaning that for applications, you have to assume cooperative multitasking as a degenerate case - if no interrupts occurred, the scheduling will only occur if a process cedes the processor.

That's a misconception. "Ticklessness" does not mean that there are no timer interrupts (and thus preemptive task switches). It just means that those interrupts do not occur at a fixed rate. For example a scheduler might calculate at each task switch the time that the new task has to "catch up" compared to other tasks (because it spent time blocking while other tasks were running) and adjust the time slice accordingly. Or it might decide to not enforce time slices at all because it detects that only one task is running at the current priority level. The motivation behind ticklessness is increasing the scheduling granularity from 10s of milliseconds to nano-/microseconds.

The scheduler itself might use a timer to determine when the currently running task has used all the time it was given. This has nothing to do with "issue_hlt();" because "issue_hlt();" is only ever used (by the scheduler) when there is no task running.

This is a crucial point. HLT has nothing to do with ticklessness. HLT is used to not waste power when there is nothing to do.

I should have clarified that for starters I only wanted to consider the case of a "single-task" system like DOS rather than multi-tasking like Linux/Windows (perhaps I was a bit misleading in OP). So indeed I assume there is no "scheduler". And as DavidCooper pointed out the STI HLT sequence removes the race condition I was worried about.

As ticklessness is a property of the scheduler and a single tasking OS does not have a scheduler speaking about a tickless single-tasking OS does not make sense at all.

As a side note:

This is not a problem. The interrupt controller will raise the interrupt line and the hlt instruction will exit immediately. Interrupts are lowered when they are acknowledged, usually both to the interrupt controller and device that caused the interrupt needs to be acknowledged;

Not only would this be inefficient, it also does not work because interrupts are not reissued until EOI is sent. A HLT loop is usually exited by the interrupt handler tearing down the idle context and switching to a different context. This functionality has to be implemented anyways because you often want to switch tasks after an interrupt (because a higher priority task was unblocked by the interrupt handler). Note that MONITOR/MWAIT can be used to optimize this path for other-CPU wake ups on modern processors.

[Brendan]

Hi,

I should have clarified that for starters I only wanted to consider the case of a "single-task" system like DOS rather than multi-tasking like Linux/Windows (perhaps I was a bit misleading in OP). So indeed I assume there is no "scheduler". And as DavidCooper pointed out the STI HLT sequence removes the race condition I was worried about.

As ticklessness is a property of the scheduler and a single tasking OS does not have a scheduler speaking about a tickless single-tasking OS does not make sense at all.

Tickless is a property of timer code. If you have something like "asynchronous timer events" (used by the single task and by device drivers for alarms, time-outs, etc) then it still makes sense even if the scheduler isn't using it or if the scheduler doesn't exist.


Cheers,

Brendan

[onlyonemac]

It also means that a process that hangs, will continue to hang unless an interrupt is processed.

That's surprisingly not as much of a problem in a GUI system as you might expect. As soon as the user wiggles the mouse or presses a key to say "hey, what's going on here?" the system will receive the interrupt and be able to say "oh hold on, that process has been running for far too long, maybe it's hung" and take appropriate action. Not the best user experience, but my point is that if applications are reasonably stable then this could actually work in a GUI environment.

Where you're going to run into trouble is with background tasks like file downloads, syncing, disk indexing, playing music, and so on which need to continue reliably even if the foreground task isn't releasing the CPU like it should (either because it's badly-written or because it's hung).