The second source of latency, as I mentioned,
is the kernel preemption latency. Now how do
we reduce the kernel preemption latency? Timer goes
off when the kernel is in the middle of
something and so we have to wait for the kernel to be ready to take that
interrupt. The first approach is the explicitly insert
preemption points in the kernel. So that it can
actually look for events that may have gone off
and take action. So that is the first approach.
The second approach is to allow preemption of the
kernel anytime the kernel is not manipulating shared data structures.
Now the reason why you don't want the kernel
to be preempted is because it is manipulating some
shared data structures and if you preempt that that
can result in some race conditions in the kernel. Bad
news. So what we want to do is, we want to make sure that the kernel is
not preempted while it is manipulating shared data
structures. But if it is not, then we
want to allow preemption. So these are two different approaches that can be
combined in order to reduce the latency associated with kernel
preemption. A technique, due to Robert Love, called the lock-breaking
preemptible kernel combines these two ideas. And by
combining these two ideas it reduces the spin lock
holding time in the kernel. The idea is
the following. So there will be a long critical
section in the kernel where in it is
manipulating some shared data structures, but it also doing
other things within this critical section. So what
we're going to do is apply these two principles and
break this long critical section as follows.
So we're going to change this critical section code
into two sections: you acquire the lock, you
manipulate the shared data structures, and you release
the lock. And the reason you're releasing the
lock is because you're done with manipulating the
shared data structures, and then we will reacquire
the lock, and finally release it. So essentially
we replaced this long critical section by two
shorter critical sections, one manipulating shared data and the
rest of the code here. What is the advantage
of doing this? What we can do is, at
this point, once we are done with manipulating
shared data, we release the lock and at this
point we can preempt the kernel safetly. And since
we can preempt the kernel at this point it's
a great opportunity to check for expired timers
at this point. If there are expired timers,
dispatch them, reprogram one-shot timers if need be.
All of that stuff can be done at this
point, and then you can come back, reacquire
the lock, and continue with the critical section.
So that's the idea of the lock breaking
preemptible kernel that combines these two ideas of explicit
insertion of preemption points and allowing preemption any time
the kernel is not manipulating shared data structures. The
third source of time latency I mentioned is the
scheduling latency, that is, the timer event goes off,
and we want to schedule the app that is
going to deal with the timer event as quickly
as possible, but the scheduler is in the way.
How do we quickly make sure that that app
gets scheduled? Firm timer implementation in TS Linux uses a combination of two
principles. One is called Proportional Period Scheduling
and in Proportional Period Scheduling what is
being done is that, when a task, so these things represent tasks T1
and T2, when a task starts up it is going to say that it needs
a certain proportion of the CPU time to be allocated to it in every
time quantum. So there are two parameters associated with proportional period
scheduling, Q and T. T is a time window, a time
quantum, and this is the time quantum that is exposed to an application.
And the application can say, within the time quantum T, I
need a certain proportion of the time for my task. So T1
might say that, in any time T, I need two thirds of the time to be
devoted to my task and if another task, T2, says in any time
period T, I need one-third of the CPU to be devoted to my task,
then these two requests can be obviously satisfied by
TS Linux because the two add to the periodicity of scheduling T. And this is
the idea behind proportional period scheduling, in which
what the scheduler does is admission control at
the time that a process starts up. If it asks for a certain proportion of time
it sees whether it is possible to satisfy
that request. So, for example, if already the
scheduler has promised T1 two-thirds of the time, and T2 comes along and says I
also need two-thirds of the time in
every period TS Linux is going to say uh-huh,
no, cannot do that, because it doesn't
have the capacity to accommodate both these requests
simultaneously. So that's the idea behind Proportional
Period Scheduling. So it provides temporal protection by
allocating each task a fixed proportion of the CPU during each task
period T. And both this Q and T parameters are adjustable parameters using a
feedback control mechanism. And so this,
in essence, improves the accuracy of scheduling
analysis that you can do on behalf
of processes that are time-sensitive. The second
technique that is used in TS Linux for reducing scheduling latency is to use
priority scheduling. And let me motivate that by introducing a problem
that plagues real time tasks and that is what is called priority inversion.
So here is a high priority task C1 and it needs some service.
And it gets that service by calling a server. And this call is a blocking
call to the server. And the server itself may be a low priority server.
For example, this client may contact a window manager to
say, I need a portion of the window and this
is what I want you to do in terms of
painting that portion of the window. That might be a
call that a high priority task is making to a
low priority server and this is a blocking call
and till the server is done with its work
the high priority task cannot continue execution. So if
you look at the timeline, C1 is running and
it makes a blocking call at this point and
the server takes over. And this is the service
time for the server to execute the blocking call
made by C1. So at the end of this service
time, C1 is ready to run again. But not so fast. It could be
that during the service time of this low priority server, on behalf of
C1, some of the higher priority tasks C2, which perhaps was waiting for some
I/O completion, becomes runnable again. If it
becomes runnable again, then this higher priority
task, compared to this server, is going to
preempt the server and take over the CPU.
So what happens at this point is that
this medium priority task, because it is higher
than the servers priority, it's going to take over,
preempting the server, and that is essentially a
priority inversion as far as C1 is concerned
because C1 is higher in priority than C2.
But unfortunately, at this point of time, the
server is the one that is scheduled and
that is lower priority than either of these
two guys. And therefore, C2 happily preempts the
server and takes over the CPU. But from the point of view of C1, that's a
priority inversion. And it is a time-sensitive task
that affects the sensitivity of the time-sensitive tasks.
This is where the priority-based scheduling of TSL saves the day for us.
Basically, the idea is that when C1 makes a request to the server, the server
is going to assume the priority of C1. Even though normally, it has a static
priority which is lower than the priority of C1. Because C1 is making this call,
the server's priority is going to be boosted to be the priority of C1
itself. So for the duration of the service time of the server the
priority of the server task is going to be the same as the priority
of C1, which is higher. Now, C2, when it becomes
runnable, it cannot preempt the server because the server is now running
at the priority of C1. And therefore, we avoid the priority inversion that
would have normally happened because of the
priority-based scheduling in TS linux, so the
upside is that there will be no
priority inversion with this priority-based scheduling mechanism
that is there in TS linux. So to recap, TS linux avoids scheduling latency
to shrink the distance between the event happening and event activation by doing
this admission control through the proportion period
scheduler and also it avoids priority inversion
by using this priority-based scheduling. So
these two mechanisms allow shrinking that distance
as well. The other advantage of the
Proportion Period Scheduling is that TS Linux
can have a control over how much of the CPU time is devoted to time-sensitive
tasks so that it can reserve a
portion of the time for throughput-oriented tasks. So
for instance, it could say, within any period T, I'm going to reserve a third of
the time for throughput-oriented tasks, so that
even if there are time-sensitive tasks running throughput-oriented
tasks are going to get their dibs for running on the CPU. And that way, we can
make sure that while supporting the timeliness of time sensitive tasks, TS-Linux
can also ensure that throughput oriented tasks
are able to make forward progress. So
the three ideas that are enshrined in
TS Linux, for dealing with time-sensitive tasks are,
first of all, coming up with the firm timer design that increases the
accuracy of the timer without exorbitant overhead in dealing with
one shock timer interrupts. Second, using a preemptible kernel to reduce
the kernel preemption latency and third,
using priority-based scheduling to avoid priority
inversion and guaranteeing a portion of the CPU time to be allowed for
time-sensitive tasks. Those are the ways
by which the distance between event happening
and event activation can be deduced and we can get good performance for
time-sensitive applications even though the operating system
is a commodity operating system like Linux.