I will say, I'd like to reserve the last five minutes of the presentation to do that if that's okay.
So, I'm going to be talking about scheduling yesterday I did a session in the Rast dev room.
It was mostly focused using Skatex to do user space scheduling in Rast.
This one is more focused on scheduling for gaming.
So, no Rasta is just playing C and BPF.
Here's the agenda.
So, a few things about gaming, gaming those Linux is becoming a serious business.
Like, a few years ago, we didn't have much reality for gaming or Linux.
Now, we have the distinct deck which is a big reality for gaming.
We have a lot of technologies in user space that are helping to make the gaming experience more appealing and better in general.
We can play any game, like, try AAA games in Linux devices.
And also on the GPU side, we had many improvements for the drivers.
So, the good thing about gaming, there's a nice way to measure the performance of a game that is using the frame per second.
So, our eye perceives changes in light of around like 60 frames per second.
That's the ideal, well, then we are all different, of course, it may change from a person to another.
But in average, if you play a game at 60 FPS, it means that your eye is kind of sampling at the same frequency.
So, you perceive this fluidity, like, you don't see the lagging basically.
And this is a very broad way of identifying the gaming experience.
Like, if you play a game at 30 FPS, let's say, it's an acceptable play style.
It's an acceptable experience, not incredibly satisfying, but still acceptable.
60 FPS is probably acceptable.
120 FPS, you go twice, the is something rate over high.
That's probably required if you do a competitive gaming stuff like that.
But, of course, this is like a generic way just to give an under, which sometimes you need to, like, go a little deeper on that.
So, for example, here's, like, I don't know if you can see, but there's a scheduler on the top.
The same game plays played with two different schedulers.
In the first case, this scheduler is able to achieve, like, an average of 67 FPS.
And in the second case, it's achieving, like, an average of 55 FPS.
So, for what I said earlier, you're tempted to say, well, the first scheduler is much better, because it gives you a higher average FPS.
But in reality, if you try to play a game in the first case, it's really bad, because sometimes you can see, like,
down here, you're going to 30 FPS, and then you jump to over 60, and then you go down to 30.
Again, this gives you, like, the impression that even the time is kind of stretching and, and, and, and it enlarging,
and you perceive like this, a stopter behavior, even if the average FPS is more than 60.
The second one is instead, it's not 60, but you have this experience of consistency and fluidity.
And your brain is, would be more pleased to play a game with the second case, more than the first one.
So, that's, like, usually we call this, the P99 latency, or tail latency, like, you want to, that's also a nice measure to, like, to, like, to bench, right here to measure, like, the game, the gaming experience.
And usually the P99 latency means that you're measuring the, the, the smaller one percent of FPS across the entire run.
So, yeah, that's it.
The average FPS gives you a measure of throughput, like, how much power you can, you can push on to playing, when playing a game, and the P99 FPS gives you a better measure of consistency.
They're both important. If you have to pick between the two, usually it's much better to prioritize consistency.
Of course, if you, if you go, like, one FPS, yeah, you're probably consistent, so that, usually, like, the best is the mix of the two.
So, white scheduling is so important. If, like, most, you know, nowadays, most of the work is done by the GPU, which implements, like, the physique mechanics and, and whatnot.
But at the end of CPU is always the manager, meaning that often, like, the game engine is implemented by the CPU, which drives, like, all the other components.
State manager for the game is all implemented in the CPU. All the processing is not implemented by the GPU.
And usually games are very cyclic, very periodically. There's a main loop that waits, then it receives an input as seen, and then it updates all the different objects in the scene, and maybe it passes the scene to the GPU for rendering, for example.
And then it receives something back, and it sends something to the compositor, and then it goes back to the beginning.
So, it's like a giant looper that is constantly sleeping, and then doing a burst of activity and then sleeping again.
So, if you find a way to classify this kind of tasks and the scheduler can, like, boost this pattern of, like, being periodic and releasing, operating in short bursts and releasing the CPU often, we can probably make the gaming experience better.
That's the idea. So, we can see, for example, here, this is a video game, and we can see that this is a perfecter to be a big shout out to Google for making this tool is really helpful to visualize what is happening with scheduling.
And as you can see here, this greenish, blueish, little bar, little squares here, and that's ex-wailant is the compositor, is the task that is sending to the graphic card to the video like every single frame.
And it's operating everything, like, every 16.6, the repeating milliseconds, it's sending, it's doing some CPU activity, like, here, here, here, very periodic.
And it's not using an entire time's lies, it's just using a little bit of time's lies, and then it goes back to sleep.
So, the 16.6 is exactly one over 60, so that's the 60 FPS, right? It's operating at 60 FPS, so every 60 millisecond is doing something.
If I try to overload the system, this is, like, the same game, but with a kernel build running in the background.
You can see that it's still trying to go every 16 millisecond, but it's very fragmented, meaning that sometimes it's not even able to complete, like, the drawing of a frame, other times it's able, but it misses the next deadline.
So, that's very inconsistent, you don't get 60 FPS in this case, and that can be a problem in some cases.
So, why is this happening? We need to see how the Linux scheduler is working.
So, the idea in the Linux kernel is that we need to have one scheduler to rule the mode, meaning that we don't support pluggable schedulers, or we use to not support pluggable schedulers.
So, why is that? For many reasons, one of them is a valid concern, like, is to avoid fragmentation.
If we allow pluggable schedulers, like, each component is going to implement their own scheduler, and we don't can join forces to have, like, a single good scheduler.
The other reason is to avoid to add complexity to a critical component in the kernel that should be considered entirely as a whole path.
But the downside of that is that we need to design a scheduler that works for everyone, so it needs to be a generic as possible.
And the best thing you can do is to design a completely first scheduler. That's the best way that is doing like weighted bandwidth CPU bandwidth allocation. That's the best way.
You can, you may find some solution that works really well for your use case, but if it has the potential to regress somebody else's worker is not going to be accepted, because we can't regress the scheduler.
So, sometimes it's three difficult to upstream scheduling changes, because you need to convince everyone that, like, this is the best for everyone.
You know, it needs to run on HPCC systems, on this phone, on this laptop, servers, gaming platforms, whatever.
And in addition to that, it's also difficult to conduct experiments. We have seen in the previous talk, like, you know, you need to rebuild the kernel deploy reboot.
You may have tooling or certain scripts on what not that can help you to speed up this process, but it's still like you still don't have the feeling of having like an edit compile test workflow that you usually have with user space applications.
So, a consequence of that is there are some out of three kernel schedulers that are maintained by outside of the main line three.
And lots of experimental things, even if experiments are difficult, again, to conduct.
So, like I was saying, what the best thing you can do is to, for the provider to implement a generic scheduler is to implement a completely first scheduler.
And so, this is the equation that drives pretty much all the schedulers, at least in Linux or all the recent schedulers.
It seems scary, but it's not.
Meaning, okay, forget about the integral, let's assume the weights, W are just the weights or priorities for tasks.
Basically, what you do, you can see here, you have an interval T1 minus T0.
You scale this time by the task weights divided by the sum of all the tasks in the system.
Meaning, if they have, like, oh, everyone is the same weight, they would get one over N, the amount of time.
So, the time is proportionally assigned to task.
If there's one that has, like, twice the weight compared to the others, it would get twice the amount of time compared to the others.
That's it, it's not complicated at all.
And, and how do, how would Linux is implementing this, or how usually you can implement this concept of fair, bent CPU bandwidth allocation, using something that is called viran time.
Basically, the idea, without going too much into details, let's just want to give you the intuition here.
We can fix, like, a baseline weight that is traditionally is 100.
And then we charge, we account the time, the runtime used by each task.
By scaling, the time interval that the task is using, inversely, proportional to its weight.
And that's how intuitively you can see, so this is the same formula, basically, it's just a different implementation.
But I just wanted to introduce the concept of virtual runtime or viran time, because it's, like, how Linux scheduling works, like, in pretty much all the schedules.
And, basically, intuitively, you can see that in this case, if the weight of the task is really big,
it's time will go slower, so you account less time to the task and it would get, oh, yeah, I forgot to say that, you schedule the one that has this smaller viran time.
So, if the time is going slowly for a task, it would be scheduled more often than another has a smaller weight, because it would get, it's accounted time will be bigger than the others.
Basically, that's the idea. And you can play with priorities when you set the nice of a task, this is what happens under the hood.
This is how the CFS scheduler was implemented, completely fair scheduler, this one, before six weeks.
Now, we have VVDF, and VVDF is the same, it's still based on viran time, but it's a deadline, I'll deadline based scheduler.
Now, without going too much into detail, the deadline is determined as the viran time here,
plus a scale the amount of time the task is requesting.
So, let's say if a task is requesting a small amount of time, likes the way land that we have seen earlier, it would get a shorter deadline.
Therefore, it would get more chances to be scheduled.
If a task is requesting a lot of time, like bigger times lies, it would get a deadline that is bigger, so it will get less chances to be scheduled.
In addition to that, because this is how that line is implemented, and this is how you prioritize more latency.
The whole thing about the whole motivation about EVDF is to be better for latency.
There's also the concept of lag, which is like this is not the definition that is in the paper, but it's more understandable into it.
Basically, it's the difference between the ideal time and the actual time that a task got.
The lag determines the eligibility thing, meaning that you can schedule a task only if it has a lot greater than zero.
Meaning that you can schedule a task only if it got less time than the ideal time that it should have gotten, and it's a way to enforce fairness more.
And this is actually hard to inform us in terms of latency, but it's a good compromise to still be completely fair, like CFS, so we don't regret, for example, server workload.
It's still a completely fair scheduler in generic enough.
But at the same time, we can allow tasks that are requesting shorter times lies to go more often.
So it's a trade-off, it's a little compromise, we prioritize latency more, but at the same time, we're still enforce fairness.
So there are improvements in terms of latency and gaming, but it's still not ideal, and it's not ideal because we need to enforce fairness, because the scheduler is just one, and it needs to be fair.
So here comes the scheduler extra, the scheduler is a new technology in the Linux kernel, that allows you to implement different scheduling policies as BFF programs.
I'm not going to marching to details on this because it's not that much time, this is about scheduling a gaming, but basically you can write a program as a BFF program, load that dynamically in the kernel, and this program would replace the actual synchronous scheduler.
At runtime, you don't have to reboot, just when you've done your experiments, you control see your program, and everything will, all the tasks will be moved back into the default scheduler.
Of course, the major benefit is rapid experimentation, it's safe because BFF is like the BFF program runs inside something like a sandbox environment so you can't crash the kernel.
And you're forced to use GPLB2, you can only load GPLB2 BFF scheduler, otherwise there's a very fired, there's in kernel verified that would reject your scheduler if it's not GPLB2.
So the idea is that we can use SKDX to relax the fairness constraint here, and implement our own scheduler, which is more aggressive, because sometimes we don't really care about fairness, if it's not fair, whatever.
So we can use this idea to design a scheduler that is more suitable for gaming, for example, and so these are a few things that seems to work really well for gaming.
Of course, detecting lazy and sensitive tasks is the key, and over prioritizing these tasks, paying the fairness constraint is actually a winning situation for this use case.
So the idea is to detect, for example, when tasks are often releasing the CPU, detecting voluntary content switches, those that have high rate of voluntary content switches can be prioritized more, and in this way you get tasks simply gets more chances to run the task that you care, if you have like in presence of background noise other tasks running in the system.
Other techniques like tracking this leap wake up frequency, because that's the same thing that you get in the user work workflow, when there's like, you know, the main thread loop that waits for the scene updates the scenes and the scene to the composer and whatnot.
And if you have a lot of tasks running in the system, it might be a good idea ought to scale the times lies that you assign, which task by inversion proportionate amount of tasks that are running in the system.
So this thing seems according to our experiments, these strategies seem to work really well for gaming.
So this is an idea that we came up with, it's just an example, we tested, there are many, many different schedulers in the SEX, right, point of schedule, this is one of them, and it's basically it's similar to EVDF, but there's not the eligibility constraint, like every task can just, we just use the deadline.
And the deadline is determined by the VLAN time, so there's still a little bit of fairness, like the scheduler is not completely unfair.
There's still some fairness, and this is the VLAN time VT, and there's also a delta VT, this is basically the amount of time from when the task becomes runnable.
So let's say you have a wake up, for example, until the time when the task voluntarily releases the CPU.
So if you have a latency sensitive task which operates in small CPU bars, and then it goes back to sleeper, the second element here will be really short, and then you have the VLAN time that gives you fairness.
Two combined together, you can see right, the deadline becomes shorter, if the second part is really small, so a task that has used less amount of times lies before would get a shorter deadline.
Therefore, it will run more often than other tasks that have used the whole times lies, because they would get bigger like these.
Is it fair? No, but okay.
And yeah, let's show that there's a demo, I don't know if it works.
Okay, so this is, I'm playing like, can you see that? Or maybe, maybe, because here it is, it's better. So I'm building the kernel, while playing counter strike.
And amazing, right? Amazing performance for FPS. This is way below the acceptable range.
So I'm starting a BFF lambda is a scheduler at runtime, then I die because I'm bad at this game, but anyway, now I'm going 30 FPS, which is not great, but still, you know, it's still better than going for FPS.
And I'm building the kernel in background with make dash j, 30.
So this is Baldur's Gate 3, another triple A game, 6 FPS without doing anything, of course.
Now I build the kernel again, and with EVDF, I go to 30 FPS, which is acceptable, but I mean, I'm in the character creator menu, so it's okay, whatever.
Then I start BFF lambda, and now I'm like 60 FPS solid, like, and if you plot the graph about P99, it's like super consistent.
So this is cyberpunk, by the way, bit kudos to the cyberpunk developers. This is going 20 FPS, but I can barely know if it's that. I don't know, they do some black magic to, so even if the FPS is crappy, but the game is still fluid.
But again, I run the kernel build, and with BFF lambda, it's going 60 FPS again.
So BFF lambda, but anyway, the thing is like, so BFF is just using this algorithm, which, so one question could be like, why don't you upstream these and you replace the internal scheduler, because that would be a terrible idea.
BFF is great for this particular workload. It's not great in general, it's great to prioritize latency sense, to over prioritize latency sense, it works.
But the good thing about SKDX is that you can load schedules depending on your particular use case, and in this case, it seems to work, and it's just this algorithm right here.
So conclusion, can SKDX help gaming only. So this was a very extreme situation, right, building the kernel while gaming.
I mean, if you do that, you deserve to get for FPS. Why are you doing that?
But jokes aside, so you need to look at the bigger picture, like this is the idea to minimize the P99 latency.
You may have a system that runs the game, but there are other things running in the background. Let's say an update is starting the background.
If you're alone in your game in your room and there's an update and you lose some frames, whatever, but there are other scenarios.
So it's a competitive, it's possible, for example, competitive gaming being able to minimize the impact of potential OS noise or background noise can be relevant.
Also the fact about, you know, project these into a totally different scenario, where you have latency sensitivity workload and CPU intensive workload.
That's the same, like it's a game, but you can map a similar scenario and have cases where you want to prioritize latency over throughput and you have both workloads at the same time running in the system.
There's also the fact that many other factors are involved nowadays in gaming platforms, but in systems in general, like topological complexity, power saving, energy efficiency, whatever, and different kind of workloads.
So being able to have a technology that allows you to switch between different schedulers can be interesting.
And yes, scheduling specialization could be the key to get a better gaming experience or better experience with specific workloads.
Okay, how much time do we have? 10 minutes, 10 minutes, okay.
I would say let's do the five minutes, we give away, where's your honest? There you go, okay, your honest have the price.
So we have two winners, oh, let's see if I can show.
So we got two.
So we got two submissions, one called weird the prior scheduling, I love the name.
The other one is, okay, I can describe the other one.
Let's, so we have two, I don't, I just, okay, this one wins, he Madrid, where's the Madrid?
Okay, you win, so that's, yeah, no, no.
So the idea was to show that it's a technology that it makes really accessible to do scheduling.
And I love the second poor request, because the description, so I don't know if you guys know who, if you know them, Michael, who's easy, are they here?
Now whatever, if you know them, tell them to come and get a T-shirt, but I love the description that says like,
not sure if it makes sense, again, but I think they call me, they say, I don't have any experience with scheduling, but I came up with this idea.
And actually, it actually works, it's a working scheduler.
So this is like a scheduler with two priority accused, one for the kernel threads and another for the regular tasks, which is a cool idea.
We like that, so we would like to give a T-shirt.
So one is the one submitted by Madrid, so this is actually a cool idea, I think we should implement this, like in production for real.
The idea is to use the CPU max concurrency, is Mathieu here, Mathieu, where's Mathieu, I so Mathieu.
Whatever, well that CPU max concurrency allows you to set the concurrency level per C group.
So the idea was to pass this concurrency value from the host into the guest, and the guest would run a scheduler to match the concurrency level,
and basically dynamically scale the VCPUs without actually scaling the VCPUs.
So it's a fast way to adjust the CPUs used by a guest by passing this information in the kernel,
which is a, I think it's a cool idea.
So yeah, you can either.
Yeah, and thanks for submitting the ideas.
Questions?
Thank you for the talk.
I thought that you also, it's great, right?
But think about pinning the pinning to certain core, basically, so core and pinning as task tool as certain core.
So it constantly helps otherwise it at my system, and it loses the CPU cash internal factor.
Yeah, so core pinning is a good idea for cash locality.
Truly found, so it's interesting, because in some games we found that the opposite is actually better,
and because you know, the Linux category uses a run Q per CPU, and it has a, or per entity, per scheduling entity, let's say,
and there's a load balance here that the term is like when a Q becomes too overloaded, it migrates tasks.
We try to, most of the scatterers that we have in Skatex, they just use a single rescue to, and then they spread tasks around the available CPUs.
Of course, this provides a better core utilization, so it's more work-onserving.
With the downside of degrading the cash locality benefits, because you're spreading tasks around.
This works really well, for example, in builders, if you do a parallel kernel builder, you can save a few seconds, like over, over, well.
Let's say, a few seconds over as small kernel builders, if your kernel build takes five minutes, it would save like five seconds, let's say.
In games, with some games, like, for example, counter-strike, this is not a good strategy, but yours is better.
So, pinning tasks.
Other games, especially when you have a lot to go today, more and more, the post-shashes have a lot of low cuts.
Oh, yeah, yeah, exactly.
But good question, yeah, yeah.
The schedulers you're proposing and trying, isn't that just a fancy way of bypassing a real-time system, and the kernel real-time exchanges now have been permanently streamlined, so isn't that the go-to solution?
Yeah, so real-time is, that's interesting, like, you can say you can use the real-time or the scared RT class to say, okay, I have something that is really critical.
I just assigned the task to the real-time scared class, and it will always win over everything else, which is acceptable in some cases.
But, like, this doesn't scale really well.
For instance, if you have just a single task or a few subset of tasks that you can move and promote to the scared RT class that works.
But, like, there are systems, for example, VR assets, let's say, they have the game, they have telemetry, they have cameras, they have audio.
You start to, you know, some app tasks that they each one things that, oh, I'm the most important in the system, therefore, I need to be real-time.
Oh, I'm also important, so I need to be real-time.
So, at some point, you don't scale.
And so, there are cases where you need a more generic systematic approach, where you can model, like, for example, this thing, it's more effective, let's say, and you don't have to do anything.
Hi, thanks for the talk.
I'm curious, and it might seem like a very weird use case.
But, I could see myself running a build in the background using half my course while gaming.
So, I'm curious, what was the performance change regarding the build, like, you were compiling the Linux kernel?
How much time extra did that cost while you were gaming?
Is it actually a feasible strategy or would I need to wait 10x the time to actually earn a build?
No, it's actually, it's actually interesting because, yes, of course, the kernel build is going to take longer.
But, not that long because coincidentally, what you're doing, you're also prioritizing those tasks during the build that have latency requirements.
And sometimes, like, let's say you have a short compilation unit that would immediately release the CPU.
You end up prioritizing that, and it's not affecting the game that much.
Maybe you lose like one FPS, but that's fine because you're also modeling the tasks that are not the game.
But, for a coincidence, they end up using the latency sensitivity pattern because they are short.
So, let's say, if I have to do an advantage estimate, your kernel build time would be, let's say, 20% slower.
But, your game is like, if you see, like, you go from 4 FPS to 30 or from 30 to 60.
So, your game is two times faster, let's say, if faster, it's not the right term, but whatever.
Your game is twice as fast as normally, and your kernel build is like 20% slower.
So, it's still a trade-off, but not bad.
All right, well off time. Thank you very much.
Thank you very much.