16 ms·
Nearly full tickless operation in Linux 3.10
- ChuckMcM 13y agoOne wonders if you can go to a full 'subscribe' model which a bunch of pre-emptive OSes use, which says "I need to run in 'x' nS" or "I need to run when interrupt 'y' fires." and then they don't get any cycles at all until they need them, and at that time they are arbitrated. The challenge of course is priority inversion, which is to say that low priority thread A gets started on an otherwise idle processor and then higher priority thread B wants to run, except there isn't a 'tick' where the processor periodically checks to see that the highest priority thread is running. Now your low priority thread is running in preference to the high priority thread. You can finesse some of that by interrupting on thread state change (which has its own issues since sometimes threads have to run to know they want to change their state) but you're still stuck somewhere between ticks when threads are sleeping and full tickless. Not surprisingly its kind of like building asynchronous hardware in hardware description languages. I'm glad to see the experiments continue.
- DigitalJack 13y agoSo how would context switching occur if not initiated by an interrupt?
- wmf 13y agoMost 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).
- glhaynes 13y agoDoesn'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?
- wmf 13y agoI 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).
- ChuckMcM 13y agoThis 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.
- to3m 13y agoSurely 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.)
- gizmo686 13y agoI 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.
- adestefan 13y agoThis 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.
- DigitalJack 13y agoIsn't a timer just scheduled interrupt?
- mwcampbell 13y agoI wonder if any general-purpose OS kernel is ahead of Linux in this area.
- gizmo686 13y agoI 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.
- cokernel_hacker 13y agoDo you consider xnu to be general purpose? OS X/iOS have been tickless for a long, long time.
- adestefan 13y agoThis is why power management has been superior in OS X/iOS.
- prirun 13y agoI 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_System_Arch_Ref_Guide_Aug87.pdf http://bitsavers.trailing-edge.com/pdf/prime/doc/DOC9473-2LA...
- to3m 13y agoI 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.)
- phaemon 13y agoThis is one of the reasons I prefer to use Linux over systems such as Windows or OSX. I love the public discussion over the direction of technical details; the to-and-fro on the benefits of esoteric technologies. The whole openness of the culture.
- mrb 13y agoThere is not much discussion about Windows internals, not only because they are not shared, but also because quite frankly the Windows kernel evolves slower than the Linux kernel in terms of new algorithms implemented. For example it is almost certain that Microsoft never tested I/O schedulers, process schedulers, filesystem optimizations, TCP/IP stack tweaks for wireless networks, etc, as much as the Linux community did. One can tell just by seeing the sheer amount of intense competition and interest amongst Linux kernel developers to research all these areas. The net result of that is a generally acknowledged fact that Windows is slower than Linux when running complex workloads that push network/disk/cpu scheduling to its limit: https://news.ycombinator.com/item?id=3368771 https://news.ycombinator.com/item?id=3368771 A really concrete and technical example is the network throughput in Windows Vista which is degraded when playing audio! http://blogs.technet.com/b/markrussinovich/archive/2007/08/27/1833290.aspx http://blogs.technet.com/b/markrussinovich/archive/2007/08/2... Note: my post may sound I am freely bashing Windows, but I am not. This is the cold hard truth. Countless of multi-platform developers will attest to this, me included. I can't even remember the number of times I have written a multi-platform program in C or Java that always runs slower on Windows than on Linux, across dozens of different versions of Windows and Linux. The last time I troubleshooted a Windows performance issue, I found out it was the MFT of an NTFS filesystem was being fragmented; this to say I am generally regarded as the one guy in the company who can troubleshoot any issue, yet I acknowledge I can almost never get Windows to perform as good as, or better than Linux, when there is a performance discrepancy in the first place.
- chinpokomon 13y agoWell Mark's post was interesting, but this is also old news now, is it not? Microsoft has had two OS updates since then and hot fixes and service packs. The biggest difference I see is that the Linux Kernel can be tweaked to specific performance characteristics at build time, whereas Windows can only be altered by runtime configuration. depending on what you might want to change, you may not have that capability. Going back to the article about network latency while playing media, the breakdown seems to show that this was a bug, and bugs happen. To Linux's credit, those bugs are probably patched more quickly and even if it hasn't been promoted to release, if someone has made a patch, you can incorporate your own fix. If not, the landscape doesn't look any different for Linux vs. Windows in that regard.
- zokier 13y agoThe advantages of full tickless elude me somewhat. Single percent performance gain does not seem worth the effort, so what else? For real-time operation tickless may make sense, but on the other hand idk how much ticking interferes currently RT processes on linux.
- IgorPartola 13y agoI was under the impression that tickless operation would translate to better power savings, but I may be wrong on this.
- acallan 13y agoPrecisely. The latency of some of the more aggressive power states exceeds the resolution of most OS tick timers, so they are often aborted for no good reason. So, as I'm typing this reply, in-between keystrokes, voltage to the CPU can be killed (not just clock-gated).
- cpeterso 13y agoI know the Linux's default scheduler ticks are, depending on the platform, ~10 ms or less. How long are the latencies of the slower power state changes?
- wmf 13y agoThe tick is every 1 ms and C6 wakeup latency can be over 100 us, so ticks could suck over 10% of your performance (and plenty of energy).
- sliverstorm 13y agoHmm. Completely brown-out the CPU in between keypresses? I always heard cold starts are very very slow (compared to regular operation). While I guess I don't have a measure for how slow, it seems unlikely that if a user is typing at 360CPM (60WPM * ~7), that you will be able to completely shut off the CPU much.
- losethos 13y agoMany people at www.osdev.org make priority queues. "I'll have 8 queues... no 32 priority queues!" Giggle God says... 21:3 And Joab answered, The LORD make his people an hundred times so many more as they be: but, my lord the king, are they not all my lord's servants? why then doth my lord require this thing? why will he be a cause of trespass to Israel? 21:4 Nevertheless the king's word prevailed against Joab. Wherefore Joab departed, and went throughout all Israel, and came to Jerusalem. 21:5 And Joab gave the sum of the number of the people unto David. And all they of Israel were a thousand thousand and an hundred thousand men that drew sword: and Judah was four hundred threescore and ten thousand men that drew sword. 21:6 But Levi and Benjamin counted he not among them: for the king's word was abominable to Joab. 21:7 And God was displeased with this thing; therefore he smote Israel. ---- Some people like to measure everything. LOL
- lallysingh 13y agoPosting a subscriber link to HN is a bit abusive, no? Quoting: The "subscriber link" mechanism allows an LWN.net subscriber to generate a special URL for a subscription-only article. That URL can then be given to others, who will be able to access the article regardless of whether they are subscribed. This feature is made available as a service to LWN subscribers, and in the hope that they will use it to spread the word about their favorite LWN articles. If this feature is abused, it will hurt LWN's subscription revenues and defeat the whole point. Subscriber links may go away if that comes about.
- bmm6o 13y ago> This feature is made available [...] in the hope that they will use it to spread the word about their favorite LWN articles Emphasis mine. Can you make a case for it being "abusive" in the context of the full text? I take it to mean generating an excessive number of links, not posting one link to a wide audience.
- lallysingh 13y agoI took it as sending the occasional article to people you know. Not as a way to poke a hole through the paywall and send (via HN) it to thousands and thousands of people.
- amboar 13y agocorbet has previously posted subscriber-only articles to hn, which I think is a reasonable endorsement of the action. Separately, there's pretty much no better linux news source, and imo subscription is worthwhile.
- corbet 13y agoFWIW I (as the editor of LWN and the author of the article) do not mind the posting of this link. It has brought in 16,000 people (at last count), many of whom are probably unfamiliar with LWN. Some subscriptions have been sold in the process. Certainly I don't want large amounts of our content to be distributed this way, but an occasional posting that puts an LWN article at #1 on HN is going to do us far more good than harm. (That said, I do appreciate your concern!)
- stcredzero 13y agoHow is 1 process per CPU not a "real load?" How about a server or a VM on that processor?
- claudius 13y agoYou will always have more than one process running, if only for the kernel threads handling filesystems, networking etc., so you can only get that if you have at the very least two CPUs. And even then you usually have more processes than CPUs and the ‘application’ split up in various processes that in turn require scheduling by the kernel.
- stcredzero 13y agoYes, but specialized server installations where multi-core CPUs have one process sitting on one core are still "real" loads. They're just specialized and not the common case.
- dchichkov 13y agoKudos to Frederic. It was quite an effort: https://lkml.org/lkml/2012/8/18/77 https://lkml.org/lkml/2012/8/18/77 And! Yes! Finally. Our 'isolated' cores are finally ours. Bare metal. No more jitter. Thank you for everyone who put that together. Your efforts are really appreciated!
- swah 13y agoAnyone knows if the paid OSes have this?
- gizmo686 13y agoWell, if your RedHat and are paying someone to work on this feature in Linux, then yes. [1] Irrespective of my disclaimer, many companies are investing many smart people in making Linux work well. Anyway, I've heard rumors that Windows 8 has this, but I can't find a good source on that (admittedly, I'm spoiled with GNU/Linux where it does not take much work to find this stuff). [1] I just pieced this together, so take it with a grain of salt. Following the e-mail at [2], I guessed that Frederic Weisbecker was running this project. Googling him brought me to his github profile [3] which indicates he is with RedHat. Anyone who actually knows what is going on please confirm or correct this. [2] http://lwn.net/Articles/549592/ http://lwn.net/Articles/549592/ [3] https://github.com/fweisbec https://github.com/fweisbec
- dantle 13y agoWindows 8 pushes out the tick. See "Idle Hygiene" here: http://blogs.msdn.com/b/b8/archive/2011/11/08/building-a-power-smart-general-purpose-windows.aspx http://blogs.msdn.com/b/b8/archive/2011/11/08/building-a-pow...
- blinkingled 13y agoYou sure about that? I read that section and it seems to be about idle duration whereas this is about turning off the timer interrupt on non-idle CPUs.
- dantle 13y agoYou're right, FULL_NO_HZ isn't mentioned in the blog I linked. It's more similar to CONFIG_NO_HZ.