Thanks for the introduction, so for those of you who never heard about sculptors, let me very
briefly summarize it in a few words. So sculptors, this is showcase of the genotOS framework
as a dust stop list and the genotOS framework is characterized by being a component-based operating
system framework which follows a hierarchical distribution of resources and it also has supports
of several microcolors. And as a side note what I also want to add, because we had this in
previous talk, the framework heavily uses asynchronous communication between components
and tries to avoid synchronous IPC wherever possible. So the official sculpt image that we
we publish twice a year that for X86 uses the Nova Microhypervisor, we also have to talk today about
that. It's an older version of the Nova Microhypervisor, which has been modified a bit and for
arm platforms we use a custom kernel, which we also use as a vehicle for test driving new ideas.
So and this is also what this talk will be about. So it's about a custom kernel.
But first, since the talk is about scheduling, let's go a little bit into the user perspective
what happens if you install a component. On to sculptors is the user is faced with the decision
in which scheduling group to run a component. Therefore scheduling groups, driver for latency
sensitive components, multimedia for audio video and stuff like that, default is for basic
test of applications, just balance computing and background, of course for some background
best effort cast. And the scheduling groups are then mapped to scheduling priorities on
underlying kernel. And since most microcolors that are supported using fixed priority,
based scheduling, we have the issue that for instance a broken device driver, the
device drivers from the Linux kernel, broken device driver can lead to starvation of the
lower priorities. So when designing and implementing the genotes custom kernel,
in roundabout 2014, the idea came up to add quotas to a priority-based scheduling.
So by setting a quota for a component, when the component exceeds its quota,
it's scheduling is degraded so basically then it's scheduled on a background in round
roll and manner. This effectively mitigates the broken device driver scenario that I mentioned
before and also nicely enables the hierarchical distribution of quotas. But unfortunately,
downside is that setting these quotas requires tuning for the workload that you're running and
also for the platform you're running on. So finding the values that work for every workload and
a platform is, yeah, it's not possible basically. So it also requires tuning. So for a dash of
wares which you want to run everything on, this is turned out to be not the the best solution.
So let's take a step back. What do we actually want to have? So first of all, we want to have
a fair scheduling on a dash of wares that's very important. So if every component gets a fair
share of the CPU, you prevent starvation. And also some threads need to get a low latency
and other threads don't care much about latency, they just want to do some computing.
What's also important to us is that it's easy for the user to configure. So we want
don't want to confront the user with a lot of decisions how to set scheduling parameters and so on.
And lastly, it should also be robust against misconfiguration. So if you don't get it right,
it should degrade gracefully and not be broken entirely. So actually two years ago,
here at Foster, Stefan and I had the idea to revise the scheduling of the custom kernel and
yeah, how did we do that? So first of all, when you set out to do this, you do some research,
you review what's what's currently the the newest and what's also what's in the literature
or what are the basic things. So let's start with a very simple one. I think everyone should
know round Robin scheduling just to summarize every threat, every component or every tag gets
they take turns, each threat gets an equal share and you have six times less length. That's pretty
easy, that's very fair. But if one thread should get a little bit more than the other,
then you need to add weights. So if you add weights, so you start, then each threat gets a
share of the CPU that's proportional to the weight. As soon as you do this, however, you
can come up with different schemes of interleaving. So in this example here, if we have the
three threats A, B, and C, A has a weight of four, B and C, both have quite of two.
Then we can have this interleaving scheme shown here to the right, so we run A, B, C,
and then two times A. This would be one super schedule, if you say so.
The downside here is that you see the distance between two executions of B differs. So B actually gets
some sort of a varying latency. You can do this more uniformly, for instance, with this schedule
where the distance between two executions of B is equal to last. How this is typically implemented,
it's round based implementation, which has the downside that when you add threats, which you do
when you have a running dynamic workloads, when you add threats, then the number or the number of rounds
that you need for the schedule might change, and then it's not trivial to transition between
these scenarios. So what you found is what I call here virtual time scheduling, which is a nice trick
to come up with similar schedule as we saw before on the way to front Robin, but much easier to
implement. So each threat has a weight and virtual time, and this schedule simply picks
one of the threats, which has the minimum virtual time and the system on the CPU.
And then when it rendered threat, the virtual time of the threat is increased by the real time
that it ran divided by the weight of the threat. So simple idea. So let's look at it in example.
Let's say we run each threat for four units of real time here. So we start, all threats start
with the same virtual time. It's zero, and we first run A for real time units set, and so because
A has threat has weight of four, it's virtual time is only increased by one. So then we take B,
it's virtual time is increased by two, similar for C, and now A has the minimum virtual time,
again we pick it, and let's say we run it again for four real time units, and then after that
we switch to B. So this is kind of random in this example, because it also choose to choose A,
A again, let's say we choose B, and then C again, and now when A is turned comes up again,
we run it twice because after running it for four real time units, it still has the minimum
virtual time, it's selected again. So as you see, we come with a similar, we come up with a similar schedule,
as we saw software for on the way to wrong Robin. So when putting this idea into practice,
of course there are more detailed questions that we have to answer. So one of this is how to assign
the weights to the threats. I mentioned before that with this assignment of quota, so somehow you
need to come up with sensible values. Also you have to determine the length of the time slice
for which each threat is scheduled. Also what do we do when threats are sleeping? And actually
and also the last most important point here is what was our initial requirement, how can we tune
this to achieve better latency or lower latency for some threats and maybe higher latency for others?
There we found two existing, particularly interesting solutions. One is the EVDF, which is
a new replacement for the Linux completely first scheduler, and we found the BVT which stands for
borrowed virtual time, and this is actually what we ended up using when implementing and designing
our new scheduler. There approach that we took here was not to jump in right away and implemented,
but of course we started with some sort of experimentation, simulate some scenarios, play with
parameters just to understand what this scaling scheme does and if check double check whether
this is really what we want to have. So let's start with the weight assignment. So the
proportional share that threat gets in the system is the result of the sum of the weights of threats,
the active threats divided by the weight of the threat. So when we add threats, the proportional
share of the threat actually changes. For instance, if we add more threats to the default scheduling group,
the share of the driver scaling group would shrink. So this is not what we want. We could,
of course we would come up with some reassignment scheme to reassign the weights, but this would
unnecessarily complicate the implementation here. So what we ended up doing is
employing a hierarchical scheduling scheme where we assign a fixed proportional share for the groups,
the four groups that I mentioned in the beginning, and within the groups we decided to use equal
weights for every threat. So every threat in the group, every threat gets the same share,
and this nicely relieves the user from any decision apart from in which scaling group to run a component.
About the time slice length, when you think about that, you can come up with a couple of
different options here. One is that we have showed in the example before, just pick a constant time slice
length. We could also make this threat specific, or somehow derive it from the weight.
One interesting aspect that comes from the BVT scheme here is that it's the idea of eliminating context
switches to the same threat. So in the example that we had before, where a runs two times in the row,
we could also determine the first place that we run for prices long.
And how this is done in BVT is that when we pick a threat to run, we let a catch up in
the virtual time until it has a catch it, catch it up with the minimum virtual time of the other
and then execute it for a constant real time longer. So let's show an example again.
We have the same weights as before. We pick a first, it runs for four real time units and after that,
we pick B. And now B first catches up with the, or yeah, it cannot catch up actually because
C still has the minimum virtual time. So it's the same scenario for B here. So it runs for four real
time units and then for C, we have the situation that now the minimum virtual time is defined by
A. So C runs until it reached the virtual time of one and then we add four real time units.
After that, we similar thing for A and then B can run again. So what we end up here is
on what we see here in the schedule is that in the beginning, when all star or threat start with
the same both at the time, the time slices are a bit smaller, but over some iterations, they get
some bigger chunks of time to execute. So far we, in the examples, we assume that
all threats just want to do computing, but in reality, of course threats sleep, so they could
unready and get ready again, signal by by something. So let's look at some examples here, let's say
A gets unready, B is scheduled and A becomes ready when B is currently executed. So in this scenario, A
would need to wait until it's virtual time is the minimum virtual time system before it can
run again. So there's some latency waiting involved here. Another situation would be
if A gets unready and gets ready after this point where it has a virtual time in the system.
So in this case, we can raise the question, how long to execute A4. Here it's important that
the sleeping time is not taking into account because otherwise if I would sleep for a couple of minutes,
it could also run for a couple of minutes exclusively and that's not what we want, right? So
the approach that's taken here by the BVT is that we just increase the minimum virtual time of A,
or increase the virtual time of A to the current minimum when A becomes ready and effectively,
then we have the proportion of share is maintained among all action threads.
What you also see here in the examples, as I already mentioned, is that there's some latency.
So in the left case, A has to wait until it has the minimum virtual time and in the left case,
if A needs a bit more execution time to finish but it only gets a smaller time slice when it becomes
ready than it has to wait for the executions of BNC here. So how can we tune this to achieve
lower latency? So we could just maybe we could just move some of the later time slices of A
more to the front and this nice trick in BVT, how this is achieved, it's by assigning a warp value
to each thread and with this warp value, the effect is virtual time of a thread is reduced by this warp value.
So as a result, the thread is one hand preferred in the scheduling decision and when it's
scheduled, it also increases the length of its time slice. And in scopes, we actually apply this
idea on the group level, so each group gets a warp value and we then derive the warp state
from the thread within the group with the lowest virtual time. And there's also a time limit for
warping so that for instance a driver thread in the broken driver scenario should not consume
all this warping benefit of the entire group because they are other threads that when they get activated,
they want to get this warping benefit so there's a time limit is thread runs for too long
then it's warping status disabled. And with this basis, I want to hand over to two steps on
where some more practical details for you. Thank you, thank you for waiting.
So in the few remaining minutes, I would like to talk about practical considerations,
so what do you need to consider when using this new conception using our custom kernel and the
short answer is not much because if you are using scalt or as already, then you actually do not
have to change anything within it. So there's no new configuration options or means that both
are the user to choose in between those warp and weight values for scheduling groups and
to decide what scheduling groups to use. In contrast to this, we use predefined scheduling groups
surprisingly those four groups already used on a much higher level in the scalt configuration.
So if you configure scalt and spawn new components, you have to choose in between those components
and they should decide and those scheduling groups already. It's of course a little bit different
if you are using the genotOS framework basically without scalt, if you tailor your own scenario,
then you should keep in mind how those hierarchical priorities are mapped to those scheduling groups.
And this I want to show you next. So in scalt, we have actually two
priority levels that are important. The very first one is spawned by the top level in it,
which creates the static portion of the system and it has of course it's a privileged level
it starts with, so it's priority level it starts with and it has it defines another one
minor priority level where most of the components reside in. And so the very first one,
which is actually the top level in itself and the timer driver, they get this driver scheduling group
and or they decide in the scheduling group of the drivers and the rest in the modern media group.
And one of the important components over here is the runtime in it process which spawns all dynamic
stuff which is going on in the system. So let's have a look at this. Surprisingly this does not
only have four priority levels but the runtime in it process itself already gains the multimedia
scheduling groups and we define a lower priority levels from driver to background underneath
because to be to stay compliant to the other corners which use linear order of priorities
and to fit this scheme. Because priority levels need to be in the order of two we have
three segments which are used actually in scout. So whenever you are using so what you should
take from the slide if you are not using status then you should keep in mind that whenever you
go away from the scheme you might get unexpected results when your components reside in anything
in the queen. So those unused segments actually land in the spec round group again.
Let's showcase something with it. I mean it won't be that fancy like the demonstration before
but we will do our best and when preparing this talk we are trying to showcase all some of the
latency advantages and what we find out is pretty hard to demonstrate this stuff. So we concentrate
on the fairness and what you see here is a simple measure like demonstration example which is
pre-configured to stay in the background, schedule and group and it doesn't use the GPU it just
uses the CPU for this animation and it takes as much as it can from the CPU.
Which you can see in this simple top component over here. So it's nearly eating up the whole CPU
and yeah run as much frames as it can and if I start another one in another group in the default
group then you will see okay it's getting slower the other one is still smooth and we have like
five times of the CPU usage on this newly spawned component which is due to the fact
that the weight of the default group is five and if you compare it to this first one the weight is one.
So it's in a line with the weights and values of both groups and if times left I start another one
but I have to configure it I think. So we just start another one of these components
and do not use the GPU again but the CPU and I will put it on the same CPU number six
and attitude so now we have two components running in this default group and as you can see in
here on the load the background group is not affected it still gets it's 5 CPU share the others
have to split in between so quite simple okay so that's the end of the talk if you want to
try this out everything we have shown here live on the Scott OS system using our own
kernel can be used by just downloading this image and yeah now we are open for questions thank you for
attention
would it make sense to implement some kind of mechanism that would allow the user space
in a task some root task to to basically upload a share unit algorithm into the kernel
like what what the reason for Linux kernel can do with ebp yeah
well I have to repeat the question whether it would be fine to upload some
scheduling algorithms into the kernel so well I cannot answer this actually I don't I would
from from my intuition I would say it would get too complicated the mechanism and I do not want to
have it like complicated like this what we think actually about or what we might think about in the
future is to gain some configuration option it's compliant with the rest but gives you more
in three or hands to just configure different scheduling groups and your two your needs
and maybe I'll read the question so so maybe if you already have some sort of hierarchical
scheduling maybe the via using different parameters in different contexts you might you might
be able to add up to different workloads dynamically right maybe yes
how elaborate where these guest inmates like how much work did you do on them
so the question was how to how elaborate were the estimates so for basically it's the weights
and and the the more values we can go to the slide so the weights come from experience that we
had before when we used the quarter base scheduling where to note that well if there are a lot
of driver work it's good it's important work if driver's not fast enough you can crash so
having a a last wait for for the driver and reserve for that is a good option and so
but the the numbers are relatively random right for the warps value it's so maybe yeah a good
estimate so what you get basically with this setting is that for instance the default group
gets a benefit of 10 milliseconds over the background so when it's when it gets ready the the
group it can execute for 10 milliseconds without any interruption of the background scheduling
and well if you look at time-slides configurations also that we we have so we have this this
constant fixed length that thread runs ahead of another one that's five milliseconds in our
configuration so the the average time-slides length is around this all of magnitude of
10 milliseconds so this is the idea that we put into that that the default group here gets
benefit of uninterrupted full length time-slides right and you can yeah go on with this
multimedia then also gets 10 milliseconds benefit uninterrupted from default for 20 milliseconds
uninterrupted from background and and so on so this is more the the line of thinking behind that
yeah so so the question is in a multiple setting where the the limits and the the settings are
different or or the same right so of course those those parameters are the same the virtual
time as you have seen if a thread is blocking or if you would transfer to another CPU for instance
and it would get the actual last virtual time of this scheduler so the scheduler knows what is
the recent lowest virtual time and we would gain it from from that one so no the a thread which
comes becomes blocked doesn't take away its virtual time
it's hard to repeat the the question we have a good idea so I just tried to answer so
the questions whether we have some some some priority boosting things like that so basically
this this warping is kind of the idea of priority boosting for for certain time right
we don't have a boosting scheme so we have helping in the system so if you do some
synchronous IPC then you the the the called thread is running on your time slice but
yeah for for asynchronous signal we don't have thing like that but you could imagine to implement
something like that yeah