Hacker News Reader

So how would context switching occur if not initiated by an interrupt?

Most context switches are actually triggered by a thread blocking. In a completely tickless OS you'd also set a one-shot preemption timer whenever a thread starts running (this used to be expensive, but Intel recently added the TSC deadline timer).

Doesn't it already use a preemption timer? If not, how does the kernel regain control once it schedules a piece of non-kernel code aside from that code blocking?

I haven't kept up with Linux specifically. In a tick-based OS, every tick can trigger the scheduler and the scheduler can decide to preempt. In a tickless OS you need a hardware preemption timer (otherwise the scheduler may never be invoked).

This is the key sticky bit. With hardware support for pre-emption it can work. I saw a very clever hack on a CPU for doing T1 processing (the telecoms protocol) which basically had four tasks that 'could' run and the engineer used the hardware data watch breakpoint (up to four addresses) which would interrupt to a vector when data changed at that address. This combined with the serdes interrupt for line data basically allowed everyone to 'sleep' most of the time.

Clever system but very very very difficult to maintain.

Surely the ordinary regular tick would use exactly the same hardware to get the regular tick interrupt as the tickless one would use to get an irregular preemption tick?

(I suppose I sort of don't get why this is a big deal - theoretically, I mean. Of course changing a system as widely-used as Linux is probably a challenge itself.)

I think the issue is that you don't necessarily know when you need to preempt before hand. For example, if you are a normal computer idling, in theory you do not need to do anything until something happens. However, you need to constantly check to see if anything happened, and the process of checking is doing something. With hardware support, you can skip checking when nothing happened.

This allows for better power management since the hardware has a better understanding the state of the system. When a system is idle now the hardware is also idle and can put itself to sleep.

You don't know when to preempt - but that's what the timer is for. It would be something of an emergency measure, because most of the time, most threads go to sleep for some other reason than running out of time. (Of course, if a thread regularly exceeds its time slice, the computer won't go into an idle state - but that's the right thing for it to do, because it isn't idle.)

As for checking for something happening, do you need to poll for this? I don't think it's necessary in the general case. Perhaps there is some broken hardware that doesn't support interrupts, but I have a hard time believing that's very common. Aside from that, nothing ever happens except by request, and (if structured right - not that I'm suggesting this is automatically easy) polling is unnecessary.

Isn't a timer just scheduled interrupt?

I suspect you can infer a subscription when a thread goes to sleep. It's probably waiting on some kind of synchronization primitive (and I guess I/O would count), or has explicitly slept for a period.

You still need a timer, I think, but it doesn't have to be a fixed frequency. It gets set to the time slice period when each new thread is scheduled, and if it fires before the thread has given up its time slice then a new thread is selected. (Ideally this behaviour should be relatively rare.)

I wonder if any general-purpose OS kernel is ahead of Linux in this area.

I doubt it. Being the most popular (and open source) kernel means that anyone looking to experiment or improve in this area will almost definitively go to Linux. Combine that with the fact that Linux has major corporate support, and many of those sponsors have an interest in the kernel being good, it is not surprising that Linux is doing well in this area.

However, this also means that the kernel is (in some ways) optimized for more server/super computer type stuff which prefers throughput over latency, at the expense of desktop/smartphone use, which prefers low latency over throughput.

Of course, in many cases there is an option between approaches (either at compile or run time). In the case of the scheduler however, they decided not to support multiple implementations in the mainline. This leaves us with the highly complicated implementation suitable for high end computer, and not the simpler Brain Fuck Scheduler (BFS) that shows minor improvements in desktop use.

Of course, using BFS is only a patch away, and several desktop distributions do use it.

Do you consider xnu to be general purpose? OS X/iOS have been tickless for a long, long time.

This is why power management has been superior in OS X/iOS.

I wrote an emulator for a Prime minicomputer (1975-1992 era). The Prime had built-in instructions for process coordination via semaphores. So when a process issued a WAIT instruction to wait on an event (semaphore), the microcode scheduler looked through the ready list to find the next eligible process to run. At the end of the ready list is the "backstop" process, the lowest priority process; it is always ready to run. The backstop process would look through other scheduling queues (just a semaphore with a list of processes waiting on it) for processes that had exhausted their timeslice, give them a new timeslice, and execute the NFYE instruction to put the process on the ready list. The NFYE instruction would actually switch to the new process, because that process had a higher priority than the backstop process.

There was a periodic timer process on the Prime, that ran at the highest priority. It was used for things like waking up driver processes periodically, in case an IO device was hung and didn't interrupt like it should have, and for waking up processes that were sleeping until a certain time passed (sleep call).

I think it was advanced for its time. If you want to read more about it, here's a link to the Prime System Architecture Guide:

http://bitsavers.trailing-edge.com/pdf/prime/doc/DOC9473-2LA...