9

On a pc (an OS of course) any C program becomes indeterministic in terms of timing. For instance a loop takes between 1.2 and 1.3 seconds depending on "how fast I am moving another window". It is because the OS makes processes (or threads) share processing power.

As far as RTOSs are concerned (on an embedded system), when we write a multithreading application, I think the same thing happens depending on how many threads are executing concurrently.

I do not have instruments to test this accurately on an embedded system. Thus, I wanted to ask. Is my concern reasonable or am I missing something very fundamental?

EDIT: I will give an example. we have task1(takes 10 ms) and task2(takes 20 ms). They started at the same time on separate two threads. My claim (also concern, not sure) is that task1 takes more than 10ms, because they share processing power with task2.

ozgur
  • 479
  • 5
  • 12
  • Determinism includes the set (and timing) of inputs – PlasmaHH Nov 25 '15 at 13:26
  • 3
    You are missing the *definition* of RTOS. ;-) – DrFriedParts Nov 25 '15 at 13:34
  • 1
    An RTOS is not used to run individual tasks that must meet individual timing requirements, it is used to run a system that must, as a whole, meet all its timing requirements. Deterministic doesn't mean 'independt off all circumstances', it means 'when I know the circumtances sufficiently well (that definitely includes higher-priority tasks) I can predict an upper bound.' – Wouter van Ooijen Nov 25 '15 at 18:20

5 Answers5

10

As far as RTOSs are concerned (on an embedded system), when we write a multithreading application, I think the same thing happens depending on how many threads are executing concurrently.

NOPE!

If that happens, then it isn't a REAL-TIME OS (RTOS).

The short-answer is that the definition of an RTOS has nothing to do with multi-tasking or priority. It is simply that all tasks have timing guarantees.

The rest of what you consider to be characteristics of an RTOS (prioritization, task completion, etc) are merely consequences (or features) of building a system where tasks must finish within the specified time interval.

Multi-tasking in an RTOS is conceptually simpler than in a soft-time OS as many of the complicating edge-cases are essentially not allowed.

DrFriedParts
  • 12,482
  • 36
  • 54
  • So, if task1 takes 10ms and task2 takes 20 ms separately. If they run at the same time (as two separate threads) would they still be complete in 10ms and 20ms respectively? – ozgur Nov 25 '15 at 14:33
  • @ozgur No, because at a minimum, regardless of whether the OS is a soft-RTOS, hard-RTOS or non-RTOS multitasker, every single task switch has overhead. Also, unless your system has multiple CPUs, the only way to get the appearance of the tasks executing concurrently is to switch quickly between them, which introduces said task switching overhead. For this reason, no matter how you slice it, a 10 ms task and a 20 ms task will always need more (though hopefully very little more) than 30 ms to complete. – user Nov 25 '15 at 15:08
  • @MichaelKjörling Your comment agrees with my concern, actually. We can never be sure about task completion time as long as there is a possibility of another thread can run concurrently. Am I right? – ozgur Nov 25 '15 at 15:11
  • @ozgur Pretty much the point of a RTOS is determinism. As someone else pointed out, in real-time applications you usually control all the executing code yourself, and can (and *do*) take steps to avoid unpredictability. Hence, broadly speaking, there *is* no "other thread that can run concurrently" unless you explicitly wrote that code yourself. – user Nov 25 '15 at 15:13
  • Borrowing from Wikipedia: "a real-time OS is valued more for how quickly or **how predictably it can respond than for the amount of work it can perform in a given period of time**.". https://en.wikipedia.org/wiki/Real-time_operating_system – user Nov 25 '15 at 15:14
  • 2
    Indeed, the whole point of an RTOS is to enforce that low-priority tasks will not run concurrently with high-priority tasks. – pjc50 Nov 25 '15 at 15:28
  • "the definition of an RTOS has nothing to do with multi-tasking or priority" +2 for that! Especially in the embedded world, anything that can provide some sort of multi-tasking advertises itself as RTOS, which is really not correct. – JimmyB Nov 25 '15 at 16:32
  • @pjc50 Generally, deterministic timing for allocating or accessing *OS managed resources* is the point. This includes CPU time as well as e.g. memory allocations or access to permanent storage, or any other hardware component. – JimmyB Nov 25 '15 at 16:38
  • 1
    @pjc50 - I think your comment is the critical point which is maybe getting lost. The question contains a fundamental misunderstanding. There is no 'task 1 started and task 2 started *at the same time*'; a higher priority task (T1) will stop/pre-empt a lower priority task (T2) until T1 is finished, or it is pre-empted by an even higher priority task (T0). Clearly, no OS can magically enable tasks which need more than the available resources to fulfil their timing, space, etc. resource constraints. – gbulmer Nov 25 '15 at 16:40
  • 2
    "no OS can magically enable tasks which need more than the available resources" -- Indeed, it can't. But a true RTOS will enable you to tell *beforehand* whether or not it is guaranteed that all your constraints will be met. – JimmyB Nov 25 '15 at 16:46
  • 1
    @ozgur: You're misunderstanding the applications that runs on RTOSes. Instead of having two tasks that takes 10ms and 20ms, typically applications on RTOSes have tasks that takes 0.01ms each but task 1 must execute EVERY 10ms and task2 must execute EVERY 20ms. Usually in real-time applications we never allow threads to run in parallel to share CPU power. Instead we run a thread for the shortest time possible then let it sleep. The point of the RTOS is that there are guarantees that when I ask it to wake me up in 10ms it will do that instead of at 10.01ms – slebetman Nov 26 '15 at 08:15
8

It's not true that tasks in an RTOS are automatically deterministic, but it's possible to put much tighter constraints on when and how often tasks run. An RTOS will usually provide for hard priorities for tasks; at any time the ready task with the highest priority is running. The author of the code also has total control over what set of tasks are running; you can reasonably expect there are no high priority background tasks that might interrupt your code to, say, swap data to disk, unless you wrote them.

On top of this, some RTOSes provide for cooperative multitasking. In contrast to preemptive multitasking, with cooperative multitasking a task will continue executing until it voluntarily gives up control of the CPU.

Nick Johnson
  • 7,739
  • 3
  • 28
  • 44
7

An RTOS doesn't usually guarantee throughput, instead it allows you to guarantee latency.

This is usually achieved by a priority system, such as here in FreeRTOS:

The FreeRTOS scheduler ensures that tasks in the Ready or Running state will always be given processor (CPU) time in preference to tasks of a lower priority that are also in the ready state. In other words, the task placed into the Running state is always the highest priority task that is able to run.

Suppose you have a priority 1 task that takes 10ms to handle an event, a priority 2 task that takes 100ms to handle a different event, and a background priority 3 task. If you're expecting to get one priority 1 event no more than every second, you can say that the worst case to handle a priority 2 event is 10ms+100ms. The priority 3 task may be arbitrarily slowed down by events, but you don't care - because it's low priority.

pjc50
  • 46,540
  • 4
  • 64
  • 126
  • In your example, are task with priority 1 and task with priority 2 running at the same time(two thread started at the same time)? – ozgur Nov 25 '15 at 14:38
  • 1
    Potentially yes, or the priority 1 starting while the priority 2 is running. This example assumes a single CPU. Note that the example spec also limits the amount of the P1 task that can run - if you get a P1 event every 10ms and it takes 10ms to handle, *nothing else will ever run*. – pjc50 Nov 25 '15 at 14:44
  • Okay, here is my question. task1(10ms) started at the same time task2(100ms) started. I believe task1 takes more than 10ms beause they are sharing processing power with task 2. I hope I made myself clear. – ozgur Nov 25 '15 at 14:54
  • I think the point being made is that the scheduler won't run task 1 and 2 at the same time. It will run task 1 (higher priority) first and queue task 2. 10ms later, when task 1 completes, it runs task 2. – michaelyoyo Nov 25 '15 at 15:17
  • 1
    Yes, it won't interleave execution of task1 and task2. If a P1 task is runnable, no P2 tasks will be scheduled until it's complete. If a P2 task is already running, it will be pre-empted and paused until all P1 work is complete. – pjc50 Nov 25 '15 at 15:26
4

I'd rather this be a comment but it takes too many characters. Anyways, ozgur, judging by the questions in your comment responses you seem to be missing the point that you can't simply say my thread takes this long to run and expect it to magically work in conjunction with other threads all thanks to the OS. You have to design your threads and analyze them for the worst case performance. If the worst-case doesn't meet your requirements then you need to redesign your threads.

So rather than simply say thread 1 takes 10 ms to complete and thread 2 takes 20 ms, you have to also say thread 1 must execute every 15 ms. thread 2 must execute every 40 ms. thread 3 must execute every 500 ms, threadN must execute every 1500 ms. Then you allocate time for how long each thread can take to complete in the worst case scenario. You put all that together, identify the worst possible scenarios and then you have to make sure every thread meets its timing requirements. This analysis is also where you identify if some threads need to be higher priority than others in order to meet their timing requirements.

For example, thread5 is running gets interrupted by thread 4 which gets interrupted by thread 3 which gets interrupted by threadN might be one worst case scenario. You put all this on a timeline and verify that even in this worst case scenario every thread meets its timing requirements. You can ensure the threads complete this worst case scenario deterministically by using the scheduler and priorities in a real-time OS. That determinism is what makes for a real-time OS.

If you make threads the same priority then you have lost some (if not all) of that determinism because the scheduler may be free to choose whichever thread it wants to run next.

In an OS like Windows, not only can you not specify when each thread will run, you can't even guarantee that your application is going to be running at any point in time. The OS could halt your application and run some background service whenever it chooses. In other words, there is no determinism. Thus, Windows is not a real-time OS. Although, if your timing requirements are large, like (thread1 runs every 10 seconds, thread2 runs every 15 seconds) then you can essentially treat Windows like a real-time OS as long as you account for the slop and approximately every 10 or 15 seconds (give or take a few hundred milliseconds and an occasional missed window) is good enough.

Dunk
  • 171
  • 4
1

Although other answers have stated that in the "real world" your scenario is not possible, to be able to answer your question, we have to build a hypothetical system.

Our system consists of a gun that shoots balls at a steady rate, two boxes that "catch" the balls and advance one step with each ball caught. The gun can be switched to fire at one of the boxes but it looses one ball each time it is switched. The first box will need 1000 steps (balls) to reach its end and box 2 will need 2000.

Scenario 1 (tasks one after the other):
- gun shoots 1000 balls at box 1, switches (costs 1 ball) and shoots 2000 balls at box 2, for a total of 3001 balls.

Scenario 2 (tasks "simultaneous"):
- gun shoots 5 balls at one box, switches and shoots 5 balls at the other box to give the appearance of simultaneity. The switching cost is (1000/5 x 2 =) 400 balls. So, after shooting 2400 balls, box 1 will reach its end and box 2 will need an additional 1000 balls to reach its end, for a total of 3400 balls.

Applying these results to your scenario, Task 1 and first half of Task 2 would complete after 24 ms, and second half of Task 2 would complete in an additional 10ms for a total of 34ms. This clearly shows that the time required to complete the tasks increases due to the time lost in switching between tasks. These results are also equivalent to Task 1 taking 12ms and Task 2 taking 22ms, to complete.

Guill
  • 2,430
  • 10
  • 6