You are here: Home / RTLWS 1999-2017 / RTLWS Submitted Papers / 
2022-07-04 - 05:44

Dates and Events:

OSADL Articles:

2022-01-13 12:00

Phase #3 of OSADL project on OPC UA PubSub over TSN successfully completed

Another important milestone on the way to interoperable Open Source real-time Ethernet has been reached

2021-02-09 12:00

Open Source OPC UA PubSub over TSN project phase #3 launched

Letter of Intent with call for participation is now available

2016-11-12 12:00

Raspberry Pi and real-time Linux

Let's have a look at the OSADL QA Farm data

2016-09-17 12:00

Preemption latency of real-time Linux systems

How to measure it – and how to fix it, if it's too high?

Real Time Linux Workshops

1999 - 2000 - 2001 - 2002 - 2003 - 2004 - 2005 - 2006 - 2007 - 2008 - 2009 - 2010 - 2011 - 2012 - 2013 - 2014 - 2015 - 2017

17th Real Time Linux Workshop, October 21 to 22, 2015 at the Virtual Vehicle Research Center, Graz, Austria

Announcement - Call for participation (ASCII) - Hotels - Directions - Agenda - Paper Abstracts - Presentations - Registration - Abstract Submission - Exhibitors and Sponsors - Gallery

Schedulability Analysis of Linux Task Groups for Hard Real-Time Systems

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.