I’m Takahiro from TIER IV’s system software team. In this tech blog, I’d like to introduce a project led by one of my team’s student engineers, exploring a way to customize the Linux kernel scheduler from user space.
The system software team researches and develops specialized OS mechanisms for Autoware-based autonomous driving systems. A key area of focus is task schedulers, which are critical to meet the real-time constraints of autonomous driving systems.
There are various options for the OS that powers Autoware, the Linux kernel being one such option. In a previous article, we introduced plugsched, a technique for live-updating the Linux kernel scheduler. This time, as a comparison, we’ll take a closer look at ghOSt, a method proposed in a paper presented at SOSP 2021: “ghOSt: Fast and Flexible User-Space Delegation of Linux Scheduling.” It is an innovative approach that enables the Linux kernel scheduler to operate as a user-space application.
Running the scheduler as an application offers several advantages:
Of course, there are also drawbacks. The main disadvantage:
The overhead introduced by ghOSt has been evaluated, and the results presented in a paper indicate that ghOSt delivers sufficient performance for scheduling at the microsecond scale. Compared to the default kernel scheduler, the ghOst scheduler incurs overhead from two sources: the double context switches between kernel mode and user mode, and the cost of message communication. According to the measurements in the paper, both operations take approximately hundreds of nanoseconds, suggesting that the overhead is negligible.
In other words, ghOSt is a technology that simplifies the development of specialized schedulers without significant overhead. A simple FIFO scheduler can be written in around 200 lines of code.
It is useful for implementing application-specific schedulers. When implementing a scheduler tailored to a specific application in the Linux kernel, the chances of it being merged into the mainline kernel are very low. As a result, developing an application-specific scheduler typically requires working outside the mainline kernel. However, this approach comes with the added cost of keeping up with kernel version changes, which can significantly increase development overhead. The ghOst framework enables the separation of scheduler implementation from the kernel, thereby reducing development costs.
The ghOst scheduler is composed of user space and kernel space components that work cooperatively. In the paper, the thread running the scheduler on the user side is referred to as an "agent."
The user-side mission is to monitor the state and priority of the application's threads, picking the next thread to execute, and communicate this to the kernel. The kernel-side mission involves communicating with the user side and performing the actual scheduling operation.
The following mechanism is used to exchange the information necessary for scheduling between the kernel and the agent:
The ghOSt scheduler can be broadly classified into two types: per-CPU and centralized.
This approach schedules tasks locally at each CPU. Each agent manages and allocates resources for its assigned CPU. Load balancing is achieved through migration of scheduled threads across agents.
In this approach, a single agent manages all other CPUs but CPU0. By dedicating one CPU exclusively to the agent, we can minimize the overhead of context switching between the agent and the kernel. This article is only focusing on per-CPU schedulers.
In ghOst, CPUs can be divided into multiple groups, each running a different scheduler. These groups are called Enclaves, and schedulers are attached to them.
In the figure below, Enclave1 can be created to manage CPUs 0 to 2, and Enclave 2 to manage only CPU 3. For example, a CFS could run in Enclave 1, and a FIFO scheduler could run in Enclave 2. This setup allows for easy management of different schedulers within the same system.
The general flow of the scheduler in operation is as follows:
In other words, at the time of scheduling, the execution switches to the agent thread, where processing is done on the user side. Afterward, it returns to the kernel side, and a context switch is carried out.
The kernel that provides the ghOSt functionality is available in the ghost-kernel repository, and can be tried out on Ubuntu 20.04 LTS. Implementations of schedulers that run on the user side are available in the ghost-userspace repository, including FIFO scheduler and CFS.
This section introduces how to install ghost-kernel on Ubuntu 20.04 LTS and running the ghost-userspace scheduler.
Follow the steps below to build and install:
Once the ghost-kernel is installed, reboot the system. This completes the preparation on the kernel side.
The installation steps are as follows:
A point to note during the build process is that the versions of ghost-kernel and ghost-userspace need to be consistent. The version is defined in the following macro in include/uapi/linux/ghost.h.
Once the build completes successfully, a scheduler named bazel-bin/fifo_per_cpu_agent should be generated. This is the binary for the per-CPU FIFO scheduler. Administrator privileges are required to load the scheduler, so run it with sudo.
The scheduler can now run as an application on the ghost-kernel.
The build and execution of the per-CPU FIFO scheduler are as follows:
The output "Initialization complete, ghOSt active." means that the initialization process has completed and the scheduler has started running. Once the scheduler starts, tasks with the scheduling policy SCHED_GHOST (=18) will be managed by this scheduler.
However, it may be difficult to see how the scheduler works in this state, so I tried the following experiment. You can specify which CPUs the scheduler operates on by using the command-line argument --ghost_cpus=0-1,4. This would make the scheduler run only on CPUs 0, 1, and 4. For this experiment, I ran the scheduler with the command-line argument --ghost_cpus=0 to make it operate only on CPU 0.
Afterward, I implemented a program called simple_bash that launches a bash with the scheduling policy set to SCHED_GHOST, and ran a busy loop with that bash.
Since the program performing the busy loop is managed by the ghOSt scheduler, I was able to observe that it was continuously running on CPU 0.
Next, I will introduce how to implement a custom scheduler in ghOSt.
We implement our scheduler in C++ using the ghost-userspace library. While schedulers can be implemented in any programming language as mentioned above, implementing one from scratch requires developing low-level components such as system call wrappers. Therefore, we recommend using the existing ghost-userspace implementation to avoid this overhead.
While implementing a scheduler requires the implementation of several classes, this article focuses on the essential components. The ‘Scheduler’ class is fundamental to the scheduler's operation. To implement a custom scheduler, you need to create a derived class from this ‘Scheduler’ class. In this tutorial, we will create a derived class called ‘TutorialScheduler’.
The main scheduling logic is implemented in the ‘Schedule’ member function. This function is called at each scheduling point. Our tutorial implementation is as follows:
Another important part of the scheduler implementation is the member function for message processing. The member function DispatchMessage parses raw messages and calls dedicated member functions based on the message type. For example, when a new task comes under the control of the ghOSt scheduler, a TASK_NEW message is sent, triggering the member function TutorialScheduler::TaskNew. The scheduler changes the task status and manipulates the run queue within these member functions.
An example implementation of TaskNew is as follows:
For this implementation, we created a simple FIFO scheduler by implementing a member variable ‘rq_’ of type ‘std::deque’ in the ‘TutorialScheduler’ class, where tasks are pushed. If you need to assign priorities based on certain metrics and select tasks with the highest priority, a priority queue can be utilized instead. Since the scheduler is implemented as a user-space application, we can leverage various libraries, which proves to be beneficial.
To implement a fully functioning scheduler, it is necessary to implement synchronization processing with the kernel. The implementation process is lengthy, so I have not included an explanation here.
This post introduced a way to use ghOSt to implement a scheduler in user space, with an eye on custom implementations of Linux task schedulers specialized for autonomous driving applications. Moving forward, the system software team will continue evaluating core technologies and researching new OS mechanisms, contributing to the development of operating systems for autonomous mobility services.
At TIER IV, we harness cutting-edge research and technology to drive the development of autonomous vehicles. The system software team is seeking hackers to help customize the Linux kernel specifically for autonomous driving. If this blog piqued your interest, we’d love to hear from you!
Takahiro Ishikawa | System Software Team
A specialist in operating and real-time systems, Takahiro joined TIER IV in April 2022, following a stint as a part-time engineer from 2020. He holds a master's degree from the Graduate School of Information Science and Technology at the University of Tokyo and is currently enrolled in a PhD program. At TIER IV, he is responsible for low-level software related to Autoware's real-time performance.
TIER IV is always on the lookout for passionate individuals to join our journey. If you share our vision of making autonomous driving accessible to all, get in touch.
Visit our careers page to view all job openings.
If you’re uncertain about which roles align best with your experience, or if the current job openings don’t quite match your preferences, register your interest here. We’ll get in touch if a role that matches your experience becomes available, and schedule an informal interview.
Inquiries
Social Media
X (Japan/Global) | LinkedIn | Facebook | Instagram | YouTube
More