Today I am not going to advertise any book from Amazon like I usually do, with a summary of some book and the affiliate link.
Today I am going to post the summary of my notes about the Real-Time Operating Systems Course I attended at the my university: despite the main reason I am writing summaries is to get some bucks with the Amazon affiliate program, I enjoy posting summary because while re-writing (they are usually originally written into paper) and re-reading them, I refresh my memory about the topic.
The topic of today is real-time in computer systems. I beg your perdon in advance because I will be very general about the topic, not getting into much detail about it: this is just supposed to be an introduction to the real-time topic.
When talking about real-time we introduce the time variable into system. If we are talking about hard real-time we have critical jobs that are supposed to be executed within a certain moment, or the job will be considered failed. On the contrary, the soft real-time does not guarantee that a job will be executed within a certain moment, but only that it will be executed as soon as possible.
It is important to point out that Real Time systems are not “faster” than traditional systems, they are just more predictable (we can just affirm something about the moment some task is going to be completed).
However, time is not the only constraint, we also can have precedence contraints or contraints related to shared resources. Shared resources will have a dedicated paragraph later.
It is a software that arranges the order of execution of the tasks, according to an scheduling algorithm. Those algoritm could be:
- preemptive: it can interrupt the execution of a task when a new task with higher priority arrives
- non preemptive: it can not interrupt the execution of a task when a new higher priority task arrives
- offline: the scheduling is done before the activation of the first task
- online: the scheduling is done whenever a task ends or a new task arrives
- optimal: it minimizes a cost function, finding the best scheduling according to a certain algorithm
- euristic: it does not guarantee the best scheduling, it just tries to optimize the scheduling
Non real-time algorithms’ family includes, amongst the others, FCFS (First Come First Served), SJF (Short Job First), Round Robin (FCFS where every task does not run until it is completed, it runs only for a quantum of time).
Besides non real-time algorithms there are some dedicated real-time algorithms, for example (there are a lot of them):
- EDF (Earliest Deadline First): the task with the closest deadline is executed first. It could be both preemptive or not preemptive, but in this case it is not optimal.
- EDF*: EDF with precedence constraints
- Rate Monotonic: scheduling for periodic tasks, each task has a fixed priority proportional to its frequency.
In case of a mixed set of periodic and aperiodic tasks, some kind of artifice is used in order to schedule them together: in the simplest version, all the aperiodic tasks are served when there are no periodic tasks waiting to be executed. In this case, the execution of the aperiodic tasks could be delayed a lot.
To solve this issue, there is a version of the mixed task real-time algorithm where we have an dummy periodic task, inside whom the aperiodic task are inserted.
When the resources are mutually exclusive, it is important to have some kind of mechanism to avoid the Priority Inversion issue (when a lower priority task gets the control of a resource inside its Critical section and does not release it to an higher priority task that arrives later, gaining without rights an higher priority towards the second task.
There are several solutions at this:
- NPP (non preemptive): a task inside its critical section can not be preempted: it gains the highest priority
- HLP (highest locker priority): the task does not gain the highest priority in assolute, but the highest priority amongst all the tasks that require the shared resource
- PIP (priority inheritance protocol): the task currently in execution inherit the highest priority of all the tasks that require the used resource
- PCP (priority ceiling protocol): extension of the PIP, with a rule that deny to a task to enter in its critical section if it has not a priority high enough
- SRP (stack resource policy): a task is not halted when it attempts to enter the critical section (like in PIP), but before, right at the moment when it attempts to preempt the task in execution
Real time Linux
Linux is a system well suited to handle real-time tasks: despite on the mainline just few real-time functionalities are introduced, thanks to its open-source nature and its monolithic kernel (suited for embedded systems) Linux is a good candidate to be transformed into a Real-Time Operating System. In this direction, there are different real-time solutions, both open source and commercial, for example RTLinux, Xenomai.
Most of these solutions consist in real time patches that handle interrupts, separating and handling in different ways standard tasks and real-time tasks.