Yin-Goo Yim, Dept. of Smart ICT Convergence, Konkuk University
Hyun-Chul Jo, Dept. of Computer Science and Engineering, Konkuk University
Hyun-Wook Jin, Dept. of Computer Science and Engineering, Konkuk University
Sang-Il Lee, Agency for Defense Development

Real-time improvements for Linux become more important as Linux is utilized in wider range of embedded systems than ever before. For example, recent extensions for process scheduling include the resource reservation framework for task groups (i.e., cgroup). Since the efforts for real-time improvements have actively carried on, it is natural to consider Linux as a potential operating system for "hard" real-time applications in the near future. However, still there are several features to be improved, because Linux is not initially designed for hard real-time systems.

In order to support hard real-time applications, we have to analyze whether given task groups are schedulable with requested CPU resources satisfying their requirements. However, the schedulability test implemented in the current Linux kernel has following limitations in terms of hard real-time:

1. The schedulability test of cgroup is overoptimistic: The current implementation of Linux task group scheduling only guarantees that task groups do not consume more CPU resources than reserved, while the schedulability test is simply passed if the total utilization is less than 100%. However, this cannot guarantee that all task groups can use the CPU resources as much as reserved for every period.
2. The schedulability test for cgroup does not consider SCHED_DEADLINE: In Linux, SCHED_DEADLINE is the highest priority scheduler, which is yet to be ready for cgroup. Therefore, the cgroup, which uses lower priority schedulers (e.g., SCHED_FIFO and SCHED_RR), should consider the CPU resources reserved by SCHED_DEADLINE in the schedulability test, but the current implementation does not.

In this paper, we address the above two issues and suggest a schedulability test tool for hard real-time systems. The schedulability analysis for periodic task groups has been studied by many researchers. These studies assume that tasks also follow a periodic task model and have isolated intra-group priorities. However, in Linux, although the CPU resources of a task group can be reserved with the period and runtime attributes of cgroup, the tasks are non-periodic processes but also are scheduled based on priorities of global scope. Thus, existing methodologies for schedulability test cannot be directly applied to Linux. To resolve this problem, we suggest following two main algorithms:

1. Algorithm to find the worst-case scenario of given task groups: In order to examine whether all task groups can constantly use entire reserved CPU resources for every period, we first need to know the worst-case scenario for given task groups. This algorithm efficiently finds the task combination that makes guaranteeing the CPU resources most difficult when the selected tasks consume most runtime of their group.
2. Algorithm for schedulability test for worst-case scenario: By using the task combination provided by the previous algorithm, we perform the actual schedulability test with the formulas suggested in this paper. Since SCHED_FIFO and SCHED_RR have different scheduling policies for same-priority tasks, we apply different formulas based on task's scheduler. The schedulability test also considers the CPU resources reserved by SCHED_DEADLINE.

We implemented the suggested algorithms as a user-level program. This tool gathers information for task groups through /sys and /proc file systems. We measured the overhead for schedulability test varying the number of task groups and tasks. The results showed that the overhead increased in proportional to the number of tasks while the impact of number of groups was negligible. In addition, we examined our tool with a large number of task sets and observed that less task sets were accepted as the number of task groups or the CPU utilization increased.

In summary, we suggest novel algorithms for schedulability analysis of Linux task groups, which guarantee that all real-time task groups can fully utilize their reserved CPU resources for every period. These algorithms are implemented in a new schedulability test tool for cgroup. Our study can contribute to enhance the performance guarantee of hard real-time applications running on Linux.