Hacker News new | more | comments | ask | show | jobs | submit login
CPU Clocks and Clock Interrupts, and Their Effects on Schedulers (2015) (accu.org)
119 points by TN1ck 10 days ago | hide | past | web | favorite | 36 comments





Reading the article made me think again about realtime software/hardware/OS, which I absolutely never understood.

One one hand Wikipedia says "Real-time programs must guarantee response within specified time constraints, often referred to as "deadlines"." ( https://en.wikipedia.org/wiki/Real-time_computing )

On the other hand when I read Wikipedia's article "Real-time operating system" ( https://en.wikipedia.org/wiki/Real-time_operating_system ) my overall understanding is that there is no feature allowing a program/thread/function to enforce e.g. "I have to be executed within 3 milliseconds" nor that that would anyway be enforced by the OS at any cost (scheduler will prioritize higher-priority tasks).

Am I missing something?

Or maybe the statement "Real-time programs must guarantee response within specified time constraints" must be taken literally and the program/thread/function must be written in a way that when some timer expires (and a "terminate"-event is sent to it), it will stop doing whatever it's doing (and it will potentially send back some kind of (partial) result)?

As you can see, this theme confuses me :)

[EDIT: thank you guys! :) ]


Generally real-time systems are realtime at every level. The idea is that you don't have a situation where you need to send a terminate event, because the program would have already terminated.

The point of a realtime OS is not to make your programs run in real-time, but to make it possible for your programs to run in real-time. This is simply not possible on a general OS like Linux, because the kernel can always to do something else while your program is running.

Consider the software that drives the printhead in your printer. The timing here is critical. If a command gets sent too early or too late, the print will not come out right.

You probably don't want the OS to be what tells you to send a command every hundred millisecond. Getting this timing right is a core feature of your application, all you need from the OS is to not get in the way of your getting the timing right.

If you are in a state where you need to send a partial result then the program computing the result is likely not really realtime.


Thx >>The point of a realtime OS is not to make your programs run in real-time, but to make it possible for your programs to run in real-time.

So basically, if I program something and somehow set it to be "realtime" then I can be sure that it won't be suspended before it finishes whatever it is doing?

Such a condition cannot be kept indefinitely - soon or later there will be activities that will need the OS' attention (therefore my program will have to be suspended), no? (If yes then I have problems understanding the threshold...).


>So basically, if I program something and somehow set it to be "realtime" then I can be sure that it won't be suspended before it finishes whatever it is doing?

Not necessarily. The OS will provide guarantees about how when the program will be suspended and for how long. The strength of those guarantees will vary between systems, and it is a fuzzy line to decide at what point you have a realtime system.

One example of this is cheap smartphones. Most phones contain a separate baseband processor to control the phone's radio. Because of how critical timing is to radios, these processors will typically run some sort of realtime system. However, modern processors are powerful enough to run both the baseband code, and Android on the same processor.

The difficulty in doing so is that Android is very much not a realtime system, so trying to run the radio software as, say, a Linux kernel driver would be impossible.

The solution is to run both Android and the baseband under a realtime hypervisor. The hypervisor would then guarantee, for example, that every millisecond it will switch to the baseband code. The baseband still gets suspended while Android is running, but because it knows exactly how long it will be suspended and how long it has to do its work while it is not suspended, it is possible for it to do its timing critical job.

You could view this as the baseband having a lot of short-lived "jobs" that it finishes each time before loosing control. Another way to think about it (that is typically more realistic) is that the baseband has 1 longrunning job that involves a fair bit of waiting; and it can be suspended while it is waiting.

Depending on your architecture, you might have the baseband coorporativly suspend itself, or have the hypervisor preemptively suspend it (with well defined timings that the baseband was designed to work with)


> The difficulty in doing so is that Android is very much not a realtime system, so trying to run the radio software as, say, a Linux kernel driver would be impossible.

Not entirely true. Although Linux is not typically real-time you can achieve this by using SCHED_FIFO or SCHED_DEADLINE for a given process/thread.

Android in fact does this for things like audio or display composition.


Setting a Linux process to a "realtime" priority (using SCHED_FIFO, etc.) will put above all non-RT /userspace/ processes. But doing that still means that the kernel can preempt you, if it decides to.

While the kernel theoretically has the ability to preempt you, it's not supposed to when using a realtime priority thread. Per the RH realtime guide[[1]:

""" SCHED_FIFO and SCHED_RR threads will run until one of the following events occurs:

- The thread goes to sleep or begins waiting for an event

- A higher-priority realtime thread becomes ready to run

If one of these events does not occur, the threads will run indefinitely on that processor, and lower-priority threads will not be given a chance to run. This can result in system service threads failing to run, and operations such as memory swapping and filesystem data flushing not occurring as expected. """

SCHED_DEADLINE, which is newer and not mentioned in the guide, can provide a bit stronger guarantees because it can fail if it thinks the requirements you set aren't actually obtainable based on other system load (including high priority kernel tasks that might need to run, etc).

[1]: https://access.redhat.com/documentation/en-US/Red_Hat_Enterp...


This varies. On a multicore CPU it's possible that processes will actually be pinned to a core and those processes will have exclusive access to the CPU core (i.e nothing else will be scheduled on it). Real-time programs tend to avoid syscalls, etc. which cause a context switch so it is indeed possible to run a realtime program indefinitely without the OS stepping in.

It's tricky though because even things like dynamic memory allocation can have non-realtime behavior.


> Real-time programs tend to avoid syscalls, etc. which cause a context switch

That's not why they avoid syscalls. If you are running on a real time schedule there won't be a context switch in response to a syscall. They may, however, get blocked on kernel mutexes. So syscalls are avoided for the same reason user-space mutexes are avoided - being real-time doesn't help if you're blocked on a mutex.


>>Real-time programs tend to avoid syscalls, etc. which cause a context switch so it is indeed possible to run a realtime program indefinitely without the OS stepping in.

I guess that context switches would have to happen if e.g. 2 realtime programs, with the same priority etc..., would run concurrently on the same CPU - or would "the running program" (the one that managed to start first) be allowed by the OS(/HW?) to take total ownership of the CPU until it finishes running?


That "until it finishes running" bit is why you can't tackle realtime at just the kernel level or just within the process. You need to also consider the whole system—ensuring that the services you're trying to run as realtime processes actually fit within your hardware's performance envelope. If you have processes that need to be pinned to a CPU core and have exclusive use of that core, then you need to ensure that you don't try to run more of those on the system than you have CPU cores available to dedicate. If you're timesharing cores between multiple processes, you need to know that the processes sharing cores have timing requirements that can be satisfied by your available resources. The human in charge of the overall system design needs to be figuring out things like how many time slices per second each realtime process needs and how many microseconds of CPU time it needs in each time slice to complete its work.

At least in Linux, there are still os threads that will run on pinned, isolated CPUs. There's work being done to allow only the user thread to run, but last I checked it wasn't complete.

OSes and applications that get called real-time vary a lot.

But yes, when it is meant rigorously, you can definitely schedule a thing to run on exactly at particular times, preempting whatever lower priority thing was running before.

In my last embedded project that meant we had thing that got called every 64 microseconds -- and it was our job to ensure it finished in time for the next tick and also left enough CPU for all the other threads.


Thx >>and it was our job to ensure it finished in time for the next tick and also left enough CPU for all the other threads

Then, for the realtime program to run correctly, it would involve as well an understanding of all other processes/programs that are running at potentially the same time (e.g. "competitors" and "collaborators") and/or with the same or higher priorities, etc.., right?

Therefore, candidate summarized definition:

realtime (HW?/)OSs allow you to execute SW which will run with no interruption, as long as no other SW having the same or higher level of priority interferes?

Does it sound right?


Yes, you need to understand all the other processes, but in most cases, there are no other processes. You are writing everything the system is doing. It's up to you to determine what is running in each thread and set it's priority appropriately so that each thread has enough time to run. Real time OSes give you complete control. What you do with that control is up to you based on your needs.

>>but in most cases, there are no other processes

Cool (yes, I was wondering about the complexity :) ) Thank you!


> Then, for the realtime program to run correctly, it would involve as well an understanding of all other processes/programs that are running at potentially the same time

Yes, and the best way to understand things is to keep them simple.

For example you can haveone real time thread which gets absolute priority and meets hard deadlines while everything else runs whenever the OS can find time for it. Then your only two rules are (1) don't let the real-time thread starve the others completely, and (2) don't rely on timing from anything except the real-time thread.

> OSs allow you to execute SW which will run with no interruption, as long as no other SW having the same or higher level of priority interferes?

Yep. Any OS meeting that definition is real-time. Probably you could get away with a looser definition, but getting it right would be a rabbit-hole.


A practical example I once had to solve:

I was writing the BIOS/flash-loader/debugger code for a Z80 clone[1] we made. The compiler send instruction packets over the RS-232 serial port at 115200 kBd (kbaud). Using 8N1, this is 12800 B/s which means we have a deadline to read the current byte out of the serial port register ever 78us or data will be lost as the new incoming byte on the serial port is written to the port's IO register.

This sounded like a lot of time, until I was informed some of the boards we sold ran at (iirc) 128kHz. After accounting for memory access time and the runtime of relevant instructions, it worked out that we had at most a budget of 60-70 instructions/byte, which wasn't anywhere close to enough to process the byte (including a simple checksum). Even using a normal ISR wasn't possible: the usual register push/pop would have a major portion of our instruction budget. I ended up dedicating a set of registers to receiving the bytes in realtime into as buffer, while processing the data non-realtime using the remaining registers.

Depending on how strict your deadlines are, "realtime" can mean accounting for every clock cycle the CPU is running. An OS (realtime or otherwise) is for people with softer deadlines and CPU time to spare.

[1] https://en.wikipedia.org/wiki/Rabbit_2000


Real time OSes have an all or nothing response to real time tasks. They either take it to run on the specified time, or they fail with some error.

The OSes also take into their hands to enforce that the tasks will finish at the time they asked for. What means that they either terminate by themselves, or the OS will terminate them, again with some explicit error.


Thx but well, this kind of goes frontally against the other 2 answers I got (I understood that nothing ever gets explicitly terminated by the OS and I felt happy with that approach as it kind of made sense to me, but some now strong doubts are coming back again...).

Realtime doesn't mean error free. A realtime OS might provide some form of a watchdog feature where it can detect when a program fails to meet its deadline. Think of it like a segfault in a traditional system. If everyone did their job correctly, it would never come up, but people make mistakes and it is better to detect them and fail in a controlled manner than it is not notice and fail in unpredictable ways.

Oh, I've read them now. There are some answers about something we used to call "soft real time". Those OSes (Linux was one, for a while, it's not anymore) will have some processes marked as real time, and change the scheduling so that they will execute right at the correct moments. The gotcha is that there can not be many real time processes, since the OS has no way to resolve a conflict between them.

What I described is called "hard real time". It is indeed a very different thing. Both kinds of OSes are in current use, on different niches.


> nor that that would anyway be enforced by the OS at any cost (scheduler will prioritize higher-priority tasks).

When sorted against ordinary time-sharing program priorities, any real-time task is a higher priority.


If your interest is in waking at a certain time, you should use APIs like `clock_nanosleep(..., TIMER_ABSTIME)` (POSIX.1-2001) which let you say at what time you would prefer to be awakened, instead of APIs which just say for how long you would like to sleep. (looks like the C++ spelling is std::this_thread::sleep_until)

... and you'll be woken up at some point after the time you requested, at which point you'll be referred back to the article to find out why.

I must have missed any mention of tickless schedulers which seem to dominate modern systems because its more efficient both in power costs (allowing the cpu to go into deeper sleeps) and generally for performance/throughput tasks in a system with low CPU contention (because the scheduler never runs).

Something that anyone who writes embedded code should be acutely aware of!

Clocks -> threads -> processes -> schedulers -> storage -> interrupts -> networks. An OS curriculum in a nutshell.


Do you have any good/favorite textbooks (or other resources) to learn those from?

"For the purposes of this discussion I’m going to assume a generic version of sleep() that accepts a parameter representing time in milliseconds. The concepts scale up or down with the scale of the parameter." Nice write-up, but no version of sleep() accepts a parameter representing time in milliseconds. Many embedded platforms have no sleep() function. Most recently, I had to implement it (and usleep) on MSP-430.

Oh dear, you sound quite confused.

https://linux.die.net/man/3/usleep https://pubs.opengroup.org/onlinepubs/9699919799/functions/n... Which is POSIX, which is supported by a number of OSes, such as QNX, Linux, BSDs, and countless others.

https://docs.microsoft.com/en-us/windows/desktop/api/synchap...

http://www.ertl.jp/ITRON/SPEC/FILE/mitron-400e.pdf See page 43 on "Standard Profile"

https://www.ee.ryerson.ca/~courses/ee8205/Data-Sheets/Tornad...

MSP-430 is not an OS, it is a microcontroller, so your comment makes absolutely no sense. Ironically one of the most popular open source MSP-430 OSes is FreeRTOS.. which of course has vTaskDelay.

Like name an OS (RTOS or otherwise) that does not have an API to sleep for millisecond periods? Not saying none exist, but, it's probably easier to name the exceptions.


> Like name an OS (RTOS or otherwise) that does not have an API to sleep for millisecond periods?

ooh! I worked on one.

Cooperative multithreading, you could schedule a task (callback function) to be called in 'n' hundreds of microseconds.

There was a scheduler that would drop the entire CPU to a super low power state if no tasks were scheduled to happen anytime soon (and set a HW timer to wake the CPU when more tasks were going to come due), but there was no "user land" API to sleep the entire system.

Sleeping the entire system when battery life is important (better to do as much work during each CPU wake cycle as possible, then drop back down to super low sleep for extended periods of time), and when other code needs to run, is rather rude, so we didn't allow it.


Nothing in the generic spec for a "sleep" function specifies you can't drop to a low power state if there is nothing to do. To varying degrees that is how sleep functions work on general purpose OSes. The CPU doesn't just spin for extended periods of time when there is nothing to do (it may spin for short waits). A "schedule a task to be called in 'n' hundreds of microseconds" is effectively a "sleep" function, the use of an explicit callback (PC) vs implicitly saving the PC of the thread is a mere implementation detail.

It served a similar purpose, if no one else scheduled anything anytime soon.

The schedule task function in this particular embedded OS actually didn't guarantee it'd call you at the specified timeout, the contract was that it'd invoke the callback no sooner than the specified timeout!

Timer coalescing and all that.

Irritated the heck out of the traditional embedded engineers when they first got introduced to it though. "I know this operation will take this many microseconds, can't I just sleep until it is done and the results are waiting for me?"

Not allowed! Plenty of old school engineers are used to just spinning the CPU while waiting for something to happen!


> didn't guarantee it'd call you at the specified timeout, the contract was that it'd invoke the callback no sooner than the specified timeout!

This is the contract for sleep on just about every general purpose OS preemptive or cooperative, and what would be assumed in the original article.

> I know this operation will take this many microseconds, can't I just sleep until it is done and the results are waiting for me?"

I mean now we're just conflating so many things. What you describe here is the essence of a hard real-time OS. It's quite orthogonal to the issue of ensuring low power. Since there are plenty of systems that require both.

> Plenty of old school engineers I can assure you there are plenty of old school engineers that can get an MCU to run for months on a couple AA batteries. They're not spinning a 20MHz CPU in a busy-loop most of the time.


> I can assure you there are plenty of old school engineers that can get an MCU to run for months on a couple AA batteries. They're not spinning a 20MHz CPU in a busy-loop most of the time.

Oh sure, the good ones aren't, but I've met more than one who thinks spinning is A-OK, especially if they haven't done battery powered stuff before!

As an example, we had a heck of a time finding a non-blocking power loss resistant file system. Ending up having to write our own. (Not an easy choice, a lot of vendors were talked to) We went to the traditional embedded file vendors at the time (hopefully things have changed) and across the board asking for a (NOR) Flash file system that could handle sudden power loss, but without the file system needing any blocking, was met with stares of "why would you want that?"

Of course a lot of embedded works uses interrupts, but on more than one occasion we encountered bugs when doing things "the correct way" and comments from our suppliers that were basically summed up as "well if you weren't so insistent on everything being async..."


I am not confused, but perhaps you did not understand my meaning. There is no version of "sleep()" that accepts an argument in anything other than seconds. Of course Microsoft has "Sleep()" which does, and of course "usleep()" and "nanosleep()" do. Is this unclear?



Applications are open for YC Summer 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: