Sporadic scheduling
The sporadic scheduling strategy is a real-time capable scheduling method that is specified in the POSIX standard 1003.1b. The aim is to treat acyclic (sporadic) tasks as if they were cyclic.
In systems that have real-time requirements - which means that certain tasks must be completed at defined times at the latest - special requirements are placed on the scheduling process: This regulates the allocation of the limited “ CPU ” resource to the running processes. The tasks to be completed can be roughly divided into two groups: On the one hand, there are cyclical tasks such as B. Measured value recordings that occur regularly in certain time periods. On the other hand, there are tasks that occur sporadically or acyclically, such as B. Error situations that must also be responded to. Since sporadic tasks occur unplanned, their processing can prevent the timely processing of the cyclical tasks. This is where Sporadic Scheduling comes in.
motivation
The assumption that all tasks can be processed cyclically is often unrealistic. A scheduling method is therefore required which ensures that it can react to acyclic events even in the case of cyclic tasks without influencing the timeliness of the cyclic tasks. Other scheduling strategies, such as B. Priority scheduling or deadline scheduling are conditionally suitable for this task. However, they make real-time verification for the system considerably more difficult .
principle
Each cyclical task is modeled with a minimum process time and the determined maximum processing time. The tasks that can occur acyclically and thus have a variable process time are also modeled as cyclic tasks. All these cyclical tasks are given their priorities according to the rate monotonic assumption , which links the priority to the process time. Since all processes are now implemented as cyclical tasks, the utilization can be calculated from the sum of the ratios of the processing time to the process time. Should this workload be violated by a task violating its process time, the triggering task is penalized and its priority is reduced. It follows from this that only the sporadic task violates its timeliness condition when the utilization is 100%.
Real-time proof
Since all tasks are processed cyclically and their priorities were assigned according to the rate-monotonic assumption, real-time proof of the sufficient scheduling condition can be provided. In addition, the 1st real-time condition must be checked.
Conversion of acyclic to cyclic tasks
For sporadic tasks, additional information must be made for the scheduler in order to be able to manage them cyclically. In addition to the priority of the cyclical process, a process time must be determined that reflects an estimate of the frequency of this event. In order to limit the execution time, a process time for this task must be known to the scheduler . If the task is not completed in the specified time, the task is automatically downgraded to a configured background priority.
Implementation in POSIX
The following values must be specified in POSIX for each sporadic task:
- Replenishment Period: [T] The assumed process time: the task can use up its execution time C within this time
- Initial Budget: [C] Execution time that a thread with normal priority runs within the replenishment period before it is set to the lower priority L.
- Priority: [N] Priority with which the thread runs as long as its initial budget is not used up.
- Low Priority: [L] Priority to which the thread is set as soon as its execution time is used up.
- Maximum number of pending replenishments: Limitation of the system overhead by limiting the number of replenishments.
| time | action |
|---|---|
| t0 | Task gets CPU |
| t1 | CPU is withdrawn. For time t0 + T, it is planned to increase C by the computing time used (t1-t0). |