Please help me find a real-time operating system (preferably open source) to start off with. Searching through Google provides a lot of options and I am very confused by the different platforms.
My requirement is only that it has to run code in a real-time operating system that spawns 4 threads. All these threads have a different set of code and are completely independent. They don't cause any IO requests. For example, thread 1 generates a number series, thread 2 multiplies a large matrix, and so on. If we consider that each of these threads takes 4, 5, 7, and 9 seconds to complete if executed serially, can the same results be achieved and guaranteed if all the threads are running simultaneously?
Anyway, a briefer, the hardware cause the problem. No caches, no pipeline -> essentially Pushners works from 1989 holds http://link.springer.com/article/10.1007%2FBF00571421
Concerning Open Source RTOS, try, for examplel Xenomai or RTAI (extensions to the Linux kernel). Tried them out a decade ago, but my knowledge is not current.
Finally, have a look at a real-time systems handbook, for example, https://www.ece.cmu.edu/~ece749/docs/RTSHandbook.pdf
Oh, I forgot, true parallelism may be counterproductive, that is, it can be easier to meet deadlines on a single core rather than scheduling on multiple cores (there is an article somewhere on this problem). Anyway, the scheduling problem may easily become NP-complete in itself, the three processor precedence constrained scheduling mentioned briefly in http://dx.doi.org.login.libraryproxy.his.se/10.1145/1077464.1077476
The predictability of a real-time system is not related to multi-threaded applications; most of the real-time applications ARE multi-threaded in the sens that the application contains a number of threads or tasks that should be executed in a concurrent manner. In order to guarantee the execution time real-time systems use a scheduler; the scheduler may be part of the operating system or it may be part of the application. In case the application is executed on a single processor (more precisely one CPU, or core) there are a number of classical scheduling algorithms such as Rate Monotonic (RM) or Earliest Deadline First (EDF) that can find a feasible schedule that can guarantee the fulfillment of deadlines. In case of multiprocessor systems the scheduling problem is a little bit more complicated but there are solutions for particular task or thread setup.
In your case with 4 threads, if you want to achieve the same execution time as in a sequential case probably you have to use a multicore platform (e.g. quad-core).
Another parameter which significantly influence the schedulability of a set of tasks (and consequently if the WCE T- worst case execution time - of each thread is guaranteed) is the periodicity of threads or tasks - how often the threads are activated.
Most of the scheduling algorithms that offer guarantees regarding execution time are taking into consideration the periods of the threads.
So, as conclusion it is not a question of operating system, is more about a good scheduling strategy.
There are two main points, why multi threading is non-deterministic:
* On the higher level of the threads themselves, shared resources may lead to race conditions, etc.
* On the lower level of scheduling, the scheduling algorithm might be indeterministic, etc.
@Armin, shared resource can be handled in a deterministic fashion via priority inheritance ceiling protocols or similar.
WHat exactly do you mean with that the lower level of scheduling can be indeterministic?
Yes, there are mechanisms to mitigate these effects. But not every RTOS does for instance does implement priority ceiling protocols. Some are subject to priority inversion. Same for scheduling. Not every RTOS scheduler might provide sufficient temporal guarantees. Some might jitter too much for a particular application, even though they implement a real-time scheduling strategy. An example here would be the class of Linux RTOS variants. They realize many mechanisms that qualify them as RTOS, but in terms of actual guarantees they vary a lot.
The intention of my previous post was to give Bishwajit a hint in which direction to look when considering different RTOSes for his application.
If the hardware does not introduce indeterminism (cache, pipes, as Jonas said) the system can be analyzable. The MAST tool http://mast.unican.es/ can help you to model your system (distributed systems can be also modeled) and to perform the schedulability analysis.
- Badges
- Science topic
- Similar topics
- Organizational Psychology
- Training