Monthly Archives: December 2024

Hello eBPF: Writing a Lottery Scheduler in Pure Java with bpf_for_each Support (18)

Posted on by

Welcome back to my hello-ebpf series. Last week, we learned about lottery schedulers and how to implement one with sched-ext and hello-ebpf. But there was one major issue when writing the scheduler in Java: hello-ebpf lacked support for the bpf_for_each macro. This is what this weeks short blog post is all about.

To loop over all elements in the scheduling queue, to pick a random one, we had to write inline C code. A simplified version without scheduling priorities looks like the following:

@Override
public void dispatch(int cpu, Ptr<TaskDefinitions.task_struct> prev) {
    String CODE = """
        // pick a random task struct index
        s32 random = bpf_get_prandom_u32() % 
            scx_bpf_dsq_nr_queued(SHARED_DSQ_ID);
        struct task_struct *p = NULL;
        bpf_for_each(scx_dsq, p, SHARED_DSQ_ID, 0) {
            // iterate till we get to this number
            random = random - 1;
            // and try to dispatch it
            if (random <= 0 && 
              tryDispatching(BPF_FOR_EACH_ITER, p, cpu)) {
                return 0;
            }
       };
       return 0;
       """;
}

This surely works, but inline C code is not the most readable and writing it is error-prone. I’ve written on this topic in my post Hello eBPF: Write your eBPF application in Pure Java (12) before. So what was keeping us from supporting the bpf_for_each macro? Support for lambdas as arguments to built-in bpf functions.

Lottery Scheduler in Pure Java

May I introduce you know the support for directly passed lambda expressions: This let’s us define a bpf_for_each_dsq function and to write a simple lottery scheduler in pure Java:

Continue reading →

Hello eBPF: Writing a Lottery Scheduler in Java with sched-ext (17)

Posted on by

Welcome back to my hello-ebpf series. Last week, I showed you how to create a custom Linux scheduler with a simple web API to control the task scheduling using sched-ext. Just so you know: A talk based on this blog post got accepted in the Testing and Continuous Delivery dev room at FOSDEM 2025. But this is not what I’m going to talk about in this blog post; instead, this article is on a topic that I covered almost exactly eleven years ago on this very blog: Lottery scheduling. We’ll extend the taskcontrol project covered in last week’s post with a new scheduler.

Foundations and Retrospektive

Eleven years ago, I was a student in Professor Frank Bellosa‘s operating systems course, learning about different schedulers. I wrote a blog post on a scheduler that I found particularly interesting: the lottery scheduler. I could write a new introduction to lottery scheduling, but I can also delegate this task to my old self:

I currently have a course covering operating systems at university. We learn in this course several scheduling algorithms. An operating system needs these kind of algorithms to determine which process to run at which time to allow these process to be executed “simultaniously” (from the users view).

Good scheduling algorithms have normally some very nice features:

  • They avoid the starving of one process (that one process can’t run at all and therefore makes no progress).
  • That all processes run the approriate percentage (defined by it’s priority) of time in each bigger time interval.

But they are maybe not only useful for operating systems but also for people like me. Probably they could help me to improve the scheduling of my learning.

An algorithm that seems to be suited best for this purpose is called lottery scheduling (pdf). It’s an algorithm that gives a each process some lottery tickets (their number resembles the priority of the process). Every time the algorithm has to choose a new process to run, it simply picks a lottery ticket randomly and returns the process that owns the ticket. A useful addition is (in scenarios with only a few tickets) to remove the tickets that are picked temporarily from the lottery pot and put them back again, when the pot is empty.

Real life practice in lottery scheduling

We can visualize this similarly to the FIFO scheduler from last week’s blog post:

Visualization of lottery scheduling with sched-ext

This is a truly random scheduler, making it great for testing applications with random scheduling orders. This is why it’s a great addition to the taskcontrol project.

Continue reading →

Hello eBPF: Control task scheduling with a custom scheduler written in Java (16)

Posted on by

Welcome back to my hello-ebpf series. A few weeks ago, I showed you how to write a minimal Linux scheduler in both Java and C using the new Linux scheduler extensions. Before we start: The Linux kernel with sched-ext support has finally been released, so the next Ubuntu version will probably have support for writing custom Linux schedulers out-of-the-box.

In this week’s blog posts, I’ll show you how to use a custom scheduler to control the execution of tasks and processes. The main idea is that I want to be able to tell a task (a single thread of a process) or a task group (usually a process) to stop for a few seconds. This can be helpful for testing the behaviour of programs in scheduling edge cases, when for example a consumer thread isn’t scheduled as it used to be normally.

Of course, we can achieve this without a custom Linux scheduler: We can just send the task a POSIX SIGSTOP signal and a SIGCONT signal when we want to continue it. But where is the fun in that? Also, some applications (I look at you, OpenJDK) don’t like it when you send signals to them, and they will behave strangely, as they can observe the signals.

Idea

I showed before that we can write schedulers ourselves, so why not use them for this case? The main idea is to only schedule processes in the scheduler that are allowed to be scheduled, according to a task (and task group) settings BPF map:

This is essentially our minimal scheduler, with one slight modification that I show you later.

And yes, the tasks are not stopped immediately, but with a maximum of 5ms scheduling intervals, we only have a small delay.

I implemented all this in the taskcontrol project, which you can find on GitHub. This is where you also find information on the required dependencies and how to install a 6.12 Kernel if you’re on Ubuntu 24.10.

Continue reading →