So we now have Andrea Rigi who's going to give a talk on rustifying the Linux kernel scheduler.
So please give it up.
Hello, you can hear me, I guess.
So yeah, we're going to talk about scheduling kernel scheduler, but in raster.
How many kernel developers are here, or people that have played with the kernel?
A few?
Okay, that's good.
Okay, you don't need to understand the kernel.
That's a good thing.
Yeah, so here's the agenda.
I want to go to the cool stuff, but before going to the cool stuff, I need to tell you something
about scheduling in general, and then we see how we can use this technology called
the SKDX to basically implement a scheduler kernel scheduling rust.
But first of all, what is a scheduler?
So a scheduler is a kernel component that determines where each task needs to run, when, and
for a long.
So it seems fairly easy to conceptually speaking, but in practice it can be really hard.
Scheduling is a very known trivial problem, particularly because there are different
architectures, different workloads, and it's really difficult to model a scheduler that works
for everyone and in every possible scenarios.
So the challenges are fairness if you want to design a scheduler that is generic as
possible, because you need to give each task some chances to run after a while, like
you've got more than something so generic.
Now, so what's the situation in Linux?
The policy in Linux is to maintain just a single scheduler or one scheduler to rule the
wall.
We used to have CFS before six, six, now we have another scheduler called EVDF.
The first one is like the CFS stands for completely fair share scheduler or completely
fair scheduler, and it's based on fairness from the previous slide.
So it gives each task is like it's doing way if it bandwidth allocation to task that's
it.
Now, we move to EVDF, EVDF is a deadline-based scheduler, deadline allows to perform
better in latency, sensitive workloads, so it's for latency.
But I'm not going into details of these schedulers if you're interested in some details,
there's another talk tomorrow in the kernel development where I'm talking more about these
schedulers, and I'll play in video games.
But anyway, the fact is that there's just one scheduler, and therefore it's really difficult
to conduct experiments, because if you want to do some tests or experiments with the
Linux kernel, you need to patch the kernel, recompile, reboot the system.
It's not always easy to do, especially in production.
Even rebooting in production, if you think at large cloud environments, you reboot
your utility, warm the caches, you need to have a downtime, so it's really difficult to conduct
experiments, and it's really difficult to upstream changes, because you may find something
that works really well for you, but if it doesn't work for anyone, your change is not
going to get merged, because you may introduce regressions.
So the single Linux kernel scheduler is like, there are compromises, it's trying to do
the best, and it's the best generics scheduler that we may possibly have, but sometimes,
you may want to relax some constraints and say, I'm willing to accept to have it like
an unfair scheduler just to solve my problem.
And right now, I mean, in this situation, it was impossible to do that unless you maintain
your own scheduler.
Our big company is that can afford that, even if it's painful for big companies, because
maintaining a patch, so impactful as scheduler, it's not a joke, it's quite a tight time
consuming.
So here comes BPS, KDEX and BPF.
The next, for those that don't know, is a new technology in the Linux kernel that allows
you to implement a scheduling policy as a BPF program, and it needs to be GPLB2, by the way,
it's not like a software requirement.
Actually the BPF verifier would not accept your scheduler if it's not licensed as GPLB2.
So BPF, for those that, I think you're all familiar with BPF, I don't want to go,
no, okay.
BPF is like a GIT in the kernel.
You can see BPF is like kind of a virtual machine, and you can, you can write programs
in C, for example.
Our whole BQs, you can test things, you can test changes to the kernel without, without
crashing the kernel, so it's safe.
Of course, you can't write things at the trial in kernel memory, but you get read access
to kernel memory.
And Skatex, the leverage BPF, to give the connections to the scheduler called BX.
So the scheduler in the Linux kernel is implemented as a class, or as a struct of function
pointers, and those function pointers are via Skatex, the redirected to the BPF program.
That's how you can write a BPF program that implements your team called BX, that are
called by the Skatex, the technology, and that's how you can implement your scheduling
policy in BPF.
So of course the benefits of this technology are the fact that you can design custom schedulers.
You can load that demo runtime, you don't need to recompile the kernel or reboot, you
just start the program.
And of course, this leads to rapid experimentation, usually when you test the program
uses base, you know, you edit compile, run, and then edit compile run, so the turnaround
of this edit compile run cycle is really fast in user space.
It's really slow in kernel space because you need to reboot and whatnot.
But with this technology, you have the same feeling of developing like a user space application,
while instead you are actually changing kernel code, in particular the schedule.
So how does it work?
So there's a kernel component that runs in the kernel, kernel subsystem called Skatex.
And in BPF, you just need to implement a few callbacks.
For example, there's a callback called NQ that is invoked every kind of task once to run.
There's a callback called dispatch that is invoked every time a CPU is ready to accept tasks
and so on and so on.
So implementing this callback allows you to write a program in BPF that implements a scheduler.
But like I mentioned, there are restrictions because BPF, in order to provide this concept
of safety, added there's this project, RAS4 Linux, that tries to bring RAS to the kernel.
Here I'm trying to do the opposite, I'm trying to bring the kernel into RAS4.
Because RAS4 Linux is controversial, this is even more controversial.
So here's the idea.
I had to give you a little introduction about Skatex and BPF just to explain this slide.
Basically, so my idea was like, if we what if you use Skatex to implement a BPF scheduler
that does nothing, except to bounce all the scheduling events to a user space program.
Because a call feature of BPF is that the user space program that loads the BPF by code via
the BPF-C scroll shares the other space with BPF and BPF provides some data structures that are
called maps that can be used like a message passing interface between BPF and the user space program.
So the idea is like let's write a minimal layer in BPF that just bounces the scheduling
events to user space. And then the user space can take all the scheduling decisions.
So you actually implement the scheduling user space. You pass the results of the scheduling
back to the BPF and BPF will do the actions that are decided by the user space program
pass everything back to the kernel. And in this way, we have uploaded complexity from BPF
into a user space program. We can still load and unload the scheduler at runtime using the usual
like BPF scheduling way, but we have a user space program now. So that's like
micro-cernal vibes here because we're actually moving part of the kernel into user space.
The consequence of good consequence of these is that now we have unlocked the access to any kind
of libraries and languages because if the kernel scheduler is a user space program,
I can write this user space program in any language. I can write it in Python, in Java, in
Raster, for instance. And I can use all the user space libraries in Raster. We use crates. I can use
any kind of crates and whatnot. So yeah, we have seen like the previous slide
where there was only the left part. Now we have also the right part that is basically the scheduler.
And what I'm doing is like the BPF scheduler will share data is only implementing this kind of
message passing interface and it uses BPF which is a C library, but there's also
BPF at S that is the Rust binding to BPF. So user space program, user space scheduler becomes
the program down here. Where am I here? Down here. And yeah, and this is like a regular Rust program.
I can literally cargo build this thing and run and it will replace the internal scheduler
with my program. And so as a proof of concept, I implemented a scheduler that is called Rustland.
Because initially I implemented there was a scheduler called user land that was written in C.
So I decided to do the same with Rustland and it's called Rustland. The scheduler itself,
okay, so deadline-based scheduler. So it's better for latency. It's not fair.
In a position to the, to the internal scheduler, it's very unfair. It prioritizes latency
sensitive work to task a lot. But that's like the implementation of the scheduler is like
it's a secondary goal. I just wanted to prove that it was possible to implement a scheduler,
a kernel scheduler in user space using this technology. So this is more like a proof of concept.
It's supposed to be a proof of concept. And I tested this with like a video game because
I was like, well, with your game is cool. Let's see how fast a video game can go if I replace the
Linux scheduler with this complete mess that is moving everything to user space. And like I was expecting
to do like, I don't know, 5 FPS or something like that. But then I actually posted this video.
I was showing that this unusual, unusual workload where I'm playing through Raria, it's a video game,
while building the kernel, which is not something that you usually do because if you're a gamer,
I mean, you want to do gaming unless you're also a kernel developer and you'll be the kernel in the background.
But yeah, so the part on the left, the EVDF is the kernel is the ink kernel scheduler,
the default Linux scheduler. And there's this video that's also available on the schedule with website.
And shows that I mean, the game is very choppy and it's like 26 FPS, but it's not just choppy,
it's also very inconsistent. So it goes from 10 FPS to 40 FPS, sometime 30, 20.
So it's really a really bad gaming experience. And with the user space scheduler, with the
Rask scheduler is doing 60 FPS, which is insane. But the thing is like, it's just the scheduling algorithm,
that is different, and it's overly prioritizing latency sensitivity work. So it's just the scheduling,
but that was to prove that not that the schedule is better because it's better for this particular use case.
It's worse for everything else. But the point was it's possible to implement user space schedulers
that can outperform the internal scheduler, which is an interesting thing. Like, and this one,
you don't have to recompine the kernel, you just insert any, and it works. I was actually planning
to show you a demo if I can. Let's see if I can. So we have this fish tank. This is the default scheduler.
Let's see what happens if I start. Do you see it? Let me try to be in the kernel.
That's the same example, but showing live, it's more cool. You see the FPS goes 9 FPS, it's really bad.
Now, I should have here. Sorry, I prepared everything at advance, but I had to reboot.
So, okay, let's do, so Rastland is the scale. Okay, now let's go back to, okay, I start the
build. I'm doing 10 FPS. Now, I just start this program down here, which is the, okay,
now the Rast scheduler is going, and you see, it's going in 40 FPS.
You know, I don't care if the schedule is not fair. If I stop the program,
you see, it's going back to the bad performance. Start the program again, and it's going back to, so
I can, if you imagine doing these by changing also the schedule, this is really powerful,
because you can literally do this in production. If I intentionally insert a bug in my scheduler,
there's, so there are two things. There's a very fire that if there's a memory problem,
it won't load my scheduler. So I can see, and see, it's actually faster now, that's the,
it's which is live. Now, but the thing is, so why is it better? What is happening? Is it,
because Rast magic? No. Yeah, yes, some of them will say, yes, I wish I could say yes,
but unfortunately, the answer is, it's not really. So the trick is in the algorithm, right? It's
not in the language. The algorithm is different, and you can see here, this is a, this is a
professor, a big shout out to Google for making this tool, which is amazing. It helps you,
tracks all, what happens? Like what's on the, on the Y axis, you see all the CPUs, on the X axis,
you see the tasks. The yellowish one is the area, it's like the main thread, and you can see that
the top, that's the kernel scheduler, is trying to be fair with all the tasks that are running,
so all the, all the clang, that are compiling the kernel, and also the main terraria task,
are, you know, it's fair, it's a fair scatterer. So there are certain logics, like it's still
deadline based, so there are certain logic to prioritize latency for the terraria task, and you can
see, you know, periodically it gets some, some CPU time, but down below, Rastlin is just doing
a lot of time to the main terraria thread compared to the other tasks. It's also a lot more
bouncy, like it constantly bouncing the task here and there, which probably is not a good idea,
because for casual quality this is bad, but, you know, it's trying to find all the possible
freeze lots, and it's very work-conservant, so it's as soon as there a CPU available,
you can see that it's trying to schedule the main game thread into the CPU that is available,
so that that's why it's working better, but like what's the benefit of Rastlin, what's the
powerful thing about Rastlin? Because I thought, okay, this is a cool idea, why don't I
generalize this, and why don't I make like a crate that people can use to design, to write
their own scheduler, so I generalize the backend of this Rastlin scheduler, and I implemented
a Rastrate, a CX Rastlin Core, which is available in crates.io, and you can use this, like, you don't have
to learn like all these Skydex and BPF boilerplate, it provides an easier API, and the cool thing
is that you can literally like cargo unit your project, you use this crate, and I also wrote a
template, so you can literally get, it's on the top, you can get clone the template, and yeah,
just cargo build that, and the template, the template implements a five-scadler using the Rastlin
Core crate, so it's a really easy to understand template, and it is where you don't have to
learn anything about the underlying layers of Skydex and BPF kernel, it's a very abstracted interface,
and I think I have, okay, that's the design, basically, it's more in details, we have the
the coldbacks here that are implemented, like this is the BPF part, and the crate contains a
back end, which implements the BPF part, and then it's using the BPFRS to implement a front end,
and your program is here. Whoops, yeah, so this is cool, I wanted to show, like this is a
working five-scadler in SCX, implemented in SCX Rastlin Core, which fits in as light, so I thought
that was a cool achievement, this is a kernel scheduler, like we can run this, and it's like,
yeah, I can show you this, like it's in Rastlin scheduler,
so this program that runs here, it's printed some statistics, but basically it's the code is this one,
and right now we are doing this presentation, running a five-scadler implemented in Rast,
and what it's doing is just, you know, the Q task is just consuming task that wants to run,
select CPU is telling the back end, like give me a CPU that is available, is idle, and I assign
the task, the CPU to the task, if select CPU doesn't give me a CPU, I say, I tell the back end,
just dispatch this task in the first CPU available, then I assign a slide times lies that is
inversely proportional to the amount of tasks that are waiting in the waiting to be scheduled,
and then I dispatch a task in order, that's it, like that's a kernel scheduler written in Rastlin
that fits in a slide, I think it's pretty cool, and yeah, if you have questions,
actually, no, these are the cakeaways. I told this already, like the important part here is
Rastlin is not a better scheduler in general, it's just a proof of concept to show you the
potential of this technology that you can use, literally using production to do scheduling testing,
which never happened before, because scheduler was a very monolithic part in the Linux kernel
difficult to change. Rast itself doesn't make the scheduler better, but having access to Rast,
especially in user space, allows you to use the whole language without any restriction,
it's not like Rastlin, that still has restriction, it needs the proper abstraction to be implemented
in the kernel as kernel code, this one you're actually using space, so you don't have the Rastlin
of restrictions, it's easy to experiment, because it's like writing, I mean, the five
scheduler fits in as light, and you just need to compile and run and stop it whenever you want,
and potentially you can import any other create that you have access with a regular user space
program, you can import libraries, maybe if you're crazy enough you can plug an entire AI or a
large language model in this program that decides your scheduling, it's going to be more
CPU expensive than the task that you're trying to run, but I mean, that's like, yeah, let's get
x, there's a logic that says, if nothing is running, this patch the user space scheduler in the
first CPU available, and you know, the CPU user space scheduler will have like a queue internally,
which all with all the tasks that are waiting to run, so it's scheduled by the BFF program,
it runs, it tells the BFF program like, okay, this guy goes here, this guy goes here, then go,
and then BFF tells KDEX the results and the scheduling happens, but it's a good question, it's the
BFF backend that decides to schedule the user space program.
How can you tell that terraria has tighter deadlines than everything else?
Sorry, I can tell that the microphone is for the video, but you still need to speak up, so, okay,
so how can you tell that terraria has tighter deadlines than compiling the kernel?
Okay, the thing is like, usually tasks that voluntarily releases the CPU before their times
lies expires, their latency sensitivity, so let's say video games are very seek-lic and
all the words are very periodic, usually in this case, you know, you're supposed to render frames
at 60 FPS, so every one over 60 seconds, which is like 60 milliseconds, every 16 milliseconds
a task needs to run, usually the composer or ex-wailant needs to run and it needs to draw a frame,
send a frame to the video card, and then it's just leaping, so latency sensitivity tasks are
working in bars of CPUs and days leap, so if you find, if you model a deadline that prioritizes
this task that has this leap behavior, and you can do that by, for example, that there are
many ways, one is measuring out the average runtime between a wake up and asleep, if this average
time is very short, you're probably facing latency sensitivity tasks, and you can model the deadline
as, like, you can use a Viren time, which is a proportional fair share, and you add, for example,
the average of this average runtime, so if a task is using a small amount of time, it would get
a smaller deadline, and if a task is, like, a client that is building the kernel, it would use
its entire CPU, it's entire time's lies, so its deadline will be longer, and with this trick you
can prioritize the lift and sensing, it doesn't work every time, but that is the best, I mean,
you would need to predict the future to write the best deadline based algorithm, but that's the best you can do.
I imagine that you need some context switches between the VPS,
well, I won't be able to understand this thing, okay, I'm coming here, it's easy.
So I imagine that you need some context switches between the kernel space VPS, and the user space
scheduler, right? So how much of an overhead is it?
Yeah, so, yeah, it's a good question. Of course, the user space scheduler is a task in its own, so
there are context switches when you need to do scheduling, when you need to do scheduling decisions.
I mentioned, like, almost at the beginning that the scheduler itself is not a
CPU-intensive application, it works almost like a latency-sensitive task, that means,
when it needs to run, it needs to run, and then it just stops, it just, you know, the decisions
that the scheduler makes are very small, you know, you need to say, okay, this guy goes here, this
guy goes here, and then I go to sleep. So, the context switches at the end are not,
they don't impact much on the scheduler itself, but they can impact on the user space applications
that are running, specifically more interruptions you have, like if you decide to use a fine grain
times less, like a smaller times less, you would get more context switches, but this is,
it doesn't depend on the schedule, it's based on how small you define your times less, right?
So, a shorter times less would give you probably better performance in terms of responsiveness,
but you also have more over it, so the throughput would be worse, right?
And that, you know, the scheduler here is just yet another task that is running in the system,
but you have the same problem with the synchronous scheduler, because
at some point the synchronous scheduler would also run with the same constraint.
While running the scheduler, the same happens with the synchronous scheduler,
because, you know, you have, okay, you're like, I'm not switching to another task,
oh, yeah, I see what you mean, yeah, some switching to a different task, yes, that's correct.
So, potentially that could be, like the contest which penalty is bigger with this approach, yes, that's correct.
So, I have a question with regards to, yeah, okay, okay, I can speak louder.
How do you ship a six-risk land curve, for example? So, there are two questions behind.
Your BPS program, is it, is it written in rest or not, or is it to see?
No, okay, that's another question, okay, yeah, that's a question, and second question,
do you ship a blob in the crate, or is it built, how do you build it?
Yeah, so the BFF part is currently written in C, and what I ship is, is the dot C,
which is compile, like there's a build dot RS that calls Clang and compiles the BFF part,
and then it becomes BFF by code in your machine when you build it, and that's how it works.
Now, I'm looking at, there's a library called Aya that generates BFF code that actually,
so I was investigating if that would be probably better, because everything would be raster,
and then BFF, but that's like, that's the bike code, is the backhand.
And, yeah, probably it's not like a super polished crate, I'm sure there's something that is not.
Even if it passes like the cargo test and everything, but I'm not sure if it's properly polished,
because I'm shipping the dot C as an artifact that is included in the crate, which is compiled
when you build your schedule. But, for any reason, if the user space schedule is blocked,
the whole schedule, the system won't progress, everything would be dead blocked and blocked.
One thing is like page fault, let's say you do our locations in the user space
scheduler, and you eat the page fault. In order to resolve the page fault, you need to schedule
a kernel thread, but the scheduler is the guide that is blocked, so there's a dead look. That's
a problem, but that was solved. I solved this one using by, I'm locking all the memory of the user space
scheduler, so the backhand is actually unlocking all the memory. You can do a location, it's just,
they will happen in an arena of pre-allocated memory, and I'm using the, how's it called,
the global alok, which is an abstraction that allows you to read the direct, all the
locations. That was really cool, I didn't know that. I learned this in raster, I was like,
oh, raster is the best, because I can read the direct, like, all the locations into whatever
algorithm I want to use to do our locations, and I did this trick to solve the page fault problem.
Okay, if you have further questions, please find Andrea, in the hallway, or if you don't have
a hallway, I guess. But thank you very much.