Android Scheduler

[DK]

Android scheduler is using the Completely Fair Scheduling(CFS) right?
I would like to know how to add a process (application) to the rbtree
(the runqueue)? I would like to know how this can be done, before the
user starting that process.

[Tsai Gaggery]

I think android has no its own scheduler. It relies on Linux kernel to
do the process scheduling. Currently, the default Linux scheduler is
CFS.

2012/4/23 DK <kanis...@gmail.com>:

> --
> unsubscribe: android-kerne...@googlegroups.com
> website: http://groups.google.com/group/android-kernel

--
Regards,
Gaggery

[Deborah Falcone]

Android use Linux Scheduler CFS. 

Scheduler — 5 files — The Android kernel also contains slight changes to the CPU process scheduler and time-keeping algorithms. We don’t know the history of these changes, and the impact was not evident based on a cursory examination. 

One really crucial point of the completely fair scheduler is that sorting processes on the red-black tree is

based on the following key:

static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)

{

return se->vruntime - cfs_rq->min_vruntime;

}

Elements with a smaller key will be placed more to the left, and thus be scheduled more quickly.

Regards,

Deborah

2012/4/23 Tsai Gaggery <gagger...@gmail.com>

[DK]

Thanks Gaggery,

U mean Android has its own scheduler? Do you know how to add a process
to the CFS scheduler(rbtree). I mean if a user starts a process it
will be automatically added, but want to add it before the user starts
the process.

Regards,
Kanishka
On Apr 23, 8:07 pm, Tsai Gaggery <gaggery.t...@gmail.com> wrote:
> I thinkandroidhas no its ownscheduler. It relies on Linux kernel to

> do the process scheduling. Currently, the default Linuxscheduleris
> CFS.
>

> 2012/4/23 DK <kanishka...@gmail.com>:
>
> >Androidscheduleris using the Completely Fair Scheduling(CFS) right?

[DK]

Thanks Deborah,

What are these five files - sched.c, sched.h, sched_fair.c ??

Yes, rbtree sorts according to vruntime, and smallest is the left most
node and the scheduler just selects the left most node. right?

Any ideas on how to add a process to the rbtree? usually when a user
starts a process it is added, right? In my case user has not accessed
the process yet? wants it to be in the rbtree so that process starts
quickly when the user starts the process.

Regards,
Kanishka

On Apr 24, 2:04 am, Deborah Falcone <falconedebo...@gmail.com> wrote:
> Android use Linux Scheduler CFS.
>
> Scheduler — 5 files — The Android kernel also contains slight changes to
> the CPU process scheduler and time-keeping algorithms. We don’t know the
> history of these changes, and the impact was not evident based on a cursory
> examination.
>
> One really crucial point of the completely fair scheduler is that sorting
> processes on the red-black tree is
> based on the following key:
>
> static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
> {
> return se->vruntime - cfs_rq->min_vruntime;
>
> }
>
> Elements with a smaller key will be placed more to the left, and thus be
> scheduled more quickly.
>
> Regards,
> Deborah
>

> 2012/4/23 Tsai Gaggery <gaggery.t...@gmail.com>

>
>
>
>
>
>
>
> > I think android has no its own scheduler. It relies on Linux kernel to
> > do the process scheduling. Currently, the default Linux scheduler is
> > CFS.
>

> > 2012/4/23 DK <kanishka...@gmail.com>:

[Tsai Gaggery]

Hi DK,

I said Android "DOES NOT" has its own scheduler, it relies on the
Linux kernel to do process scheduling. I am not sure why you want to
add a process before user starts the process. But, if you just want to
execute a process before other user's application, you may modify the
init.rc or init.MACHINE_NAME.rc to achieve it.

regards,
Gaggery

2012/4/24 DK <kanis...@gmail.com>:

[Deborah Falcone]

Hi Kanishka,

Thanks Deborah,

What are these five files - sched.c, sched.h, sched_fair.c ??

 

I read part of Android source code and I find notice about scheduler in sched.h, sched_policy.h, sched_policy.c!

 

file:///C:/Users/Deborah/Desktop/SCHEDULER%20ANDROID/scheduler%20-%20Android%20Process%20Scheduling%20-%20Stack%20Overflow.htm

here there is information about difference between Android and Linux CFS's implementation.

 

Yes, rbtree sorts according to vruntime, and smallest is the left most
node and the scheduler just selects the left most node. right?

 

It's rigth. The key is:  vruntime - min_vruntime.

 

Any ideas on how to add a process to the rbtree?

 

The metod that add a process to runqueue is put_prev_task.

 

usually when a user starts a process it is added, right?

 

It's rigth! 

 

In my case user has not accessed the process yet? wants it to be in the rbtree so that process starts
quickly when the user starts the process.

I don't know how this can be done.

 

Regards,

Deborah

[Kanishka Ariyapala]

Hi Gaggery,

Thanks for the reply.
Sori for the miss understanding. init.rc won't work I guess. I want
some thing done at the kernel level(scheduler) I mean like telling the
scheduler about a process and the scheduler adding it to the red-black
tree of the CFS.

Regards,
Kanishka

[Kanishka Ariyapala]

Hi Deborah,

Thanks for the reply and the reference link,
What I want to do is something like this, tell the scheduler about a
process(which is not started yet) and the scheduler adding it to the
rbtree. Any reference material you know of achieving this?

Regards,
Kanishk

On 4/24/12, Deborah Falcone <falcone...@gmail.com> wrote:
> Hi Kanishka,
>
> Thanks Deborah,
>>
>> What are these five files - sched.c, sched.h, sched_fair.c ??
>>
>>
> I read part of Android source code and I find notice about scheduler

> in *sched.h,
> sched_policy.h, sched_policy.c*!

>
> file:///C:/Users/Deborah/Desktop/SCHEDULER%20ANDROID/scheduler%20-%20Android%20Process%20Scheduling%20-%20Stack%20Overflow.htm
> here there is information about difference between Android and Linux CFS's
> implementation.
>
>
>> Yes, rbtree sorts according to vruntime, and smallest is the left most
>> node and the scheduler just selects the left most node. right?
>>
>

> It's rigth. The key is: *vruntime - min_vruntime*.

>
>
>>
>> Any ideas on how to add a process to the rbtree?
>
>
> The metod that add a process to runqueue is put_prev_task.
>
>
>> usually when a user starts a process it is added, right?
>
>
> It's rigth!
>
>
>> In my case user has not accessed the process yet? wants it to be in the
>> rbtree so that process starts
>> quickly when the user starts the process.
>>
>> I don't know how this can be done.
>
> Regards,
> Deborah
>

[Tim Bird]

On 04/24/2012 10:12 AM, Kanishka Ariyapala wrote:
> Hi Deborah,
>
> Thanks for the reply and the reference link,
> What I want to do is something like this, tell the scheduler about a
> process(which is not started yet) and the scheduler adding it to the
> rbtree. Any reference material you know of achieving this?

I don't think there's any way (currently) to accomplish this.

The scheduler only works with processes that exist. There's
no notion that I'm aware of to "pre-schedule" a process, before
any of the kernel data structures for it exist.

Sorry, but I came into the middle of the discussion. What
are you actually trying to accomplish? Do you want some historical
information about the process, or about systemwide scheduling
to be present at the time the process eventually gets started?
Is the process starting too slowly? Are you trying to adjust
the priority of other processes, as if the non-existent one
were already present in the system?

Maybe what you need, instead of a placeholder for a non-existent
process, is just a tweak to the scheduler algorithms to create the
desired scheduling effect once the process comes into existence.
It really doesn't make sense to make the scheduler aware of
a process that doesn't exist. IMHO, you need to think of a different
way to attack whatever problem you're trying to address.

-- Tim

=============================
Tim Bird
Architecture Group Chair, CE Workgroup of the Linux Foundation
Senior Staff Engineer, Sony Network Entertainment
=============================

[Tsai Gaggery]

I think it may not reasonable to do this, because you have to make
sure the process that you would like to add to rb-tree (run queue)
will not go to "sleep" (once you call some kernel APIs that may get
into sleep). When this process uses this kind of kernel API and yield
the CPU resources, the scheduler will remove this process out of run
queue until it wake up. So, it may hard to make sure this process is
exactly in rb-tree while "other user application" starting, right?

2012/4/25 Kanishka Ariyapala <kanis...@gmail.com>:

[Kanishka Ariyapala]

Thanks Tim for the detailed answer and the questions. It shed some
light on me too. I didn't tell why I wanted to pre -schedule a
process.

My final year project is a context-aware OS, which is too big to
handle so I scaled it down to only one aspect of the OS, scheduling.
So am trying to achieve context-aware scheduling. I want to give
priority to certain applications depending on the context, such as
home, office, driving etc. I will predefine what applications will be
run in these contexts. So when you are in that context these
applications have high priority and others have low priority. How ever
the user may not have started the application yet, so I THOUGHT that
if by keeping it in the run queue(rbtree) I will get better start up
time and responsiveness.

My goal is to make those processes(apps defined for that context) in
the running sate(high priority) ready to be run(when the user clicks
on it) and to decrease the priority of other apps(not defined for that
contexts) along with the other normal OS processes.

I plan to collect the data for context using the sensor's in the
Android, for the beginning with the GPS.

In your questions you have attacked the exact point I want! "a tweak

to the scheduler algorithms to create the desired scheduling effect

once the process comes into existence." under a particular context.

So far I have been trying to understand the scheduling process and was
looking for a way to add a process to the scheduler, but it is not
that simple because a have initialize data structures(like
task_struct) and then to be put in to the rbtree. Also to make it the
left most node as far as possible.

In your opinion how do you think I should proceed?

Regards,
Kanishka

[Kanishka Ariyapala]

Yes you have a point there, once other user applications are starting
and the process I have added may be pushed to sleep (waiting for some
resource) it will not be in the rb tree.

However what I am trying to achieve is context-aware scheduling. By
context I mean office, home, driving etc. So under that context to
pre-schedule some applications I have predefined for those contexts,
or give high priority(for this you need to have this in the run
queue,rty?) and give other user applications low priority.

How do you think I should approach this?

Also I have some trouble with debugging the kernel, you need to use
printk to print data structures, process flow etc, rty? have you used
it or do u have any idea? or any other way of achieving this?

Regards,
Kanishka

[Tim Bird]

On 04/25/2012 01:09 AM, Kanishka Ariyapala wrote:
> Yes you have a point there, once other user applications are starting
> and the process I have added may be pushed to sleep (waiting for some
> resource) it will not be in the rb tree.
>
> However what I am trying to achieve is context-aware scheduling. By
> context I mean office, home, driving etc. So under that context to
> pre-schedule some applications I have predefined for those contexts,
> or give high priority(for this you need to have this in the run
> queue,rty?) and give other user applications low priority.
>
> How do you think I should approach this?

I would be tremendously surprised if the delay at startup had
much to do with scheduling, rather than latencies related to
demand-paging the program into memory. You might want to profile
the actual application startup (with a tracer or perf) and see
where the startup costs actually are. (Just the ftrace function
tracer should be quite useful to see what the kernel is up to
during your application load.) I have a hunch you'll find
the startup cost is in the memory loading and initial application
initialization.

If you want to pre-load data to reduce the memory loading cost,
try reading ahead the data. See
http://elinux.org/Android_Boot-time_Readahead for some information
on this topic.

[David Ahern]

On 4/25/12 1:49 AM, Kanishka Ariyapala wrote:
> My goal is to make those processes(apps defined for that context) in
> the running sate(high priority) ready to be run(when the user clicks
> on it) and to decrease the priority of other apps(not defined for that
> contexts) along with the other normal OS processes.
>
> I plan to collect the data for context using the sensor's in the
> Android, for the beginning with the GPS.
>
> In your questions you have attacked the exact point I want! "a tweak
> to the scheduler algorithms to create the desired scheduling effect
> once the process comes into existence." under a particular context.
>
> So far I have been trying to understand the scheduling process and was
> looking for a way to add a process to the scheduler, but it is not
> that simple because a have initialize data structures(like
> task_struct) and then to be put in to the rbtree. Also to make it the
> left most node as far as possible.
>
> In your opinion how do you think I should proceed?

Have you thought of using cgroups for this? Create a cgroup for each
context, assign the running apps to the cgroup and adjust shares to
effectively increase the priority of the apps.

David

[DK]

Thanks Tim for the insights. I thought pre-scheduling would, putting
it into the run queue would load the apps in to memory because they
are in the running state(not actually running but ready to run) isn't
that the case. My question dosen't pre-scheduling do the read ahead?

Thanks for pointing the kernel debug tools, what can I use for reading
the source code? Where I can see all the method calls, will eclipse
do? Since am working on a virtual machine(Linux) and inside it the
android emulator, is there any tool or way to see what registers are
being used likewise(specially for the android emulator). Like the once
you get for embedded development(mplab for example). If there is no
such tool what is general practice in kernel debugging?

Thanks David for pointing out cgroups I will look into it.

Regards,
Kanishka

[Chris Stratton]

On Wednesday, April 25, 2012 11:57:37 AM UTC-4, tbird20d wrote:

> However what I am trying to achieve is context-aware scheduling. By
> context I mean office, home, driving etc. So under that context to
> pre-schedule some applications I have predefined for those contexts,
> or give high priority(for this you need to have this in the run
> queue,rty?) and give other user applications low priority.

I would be tremendously surprised if the delay at startup had
much to do with scheduling, rather than latencies related to
demand-paging the program into memory.

I would agree the suspicion, but maybe the OP's idea can be adapted to addressing the loading delay instead by extending a mechanism android already uses.

Specifically, there are tweaks (principally to the OOM killer values) which do things like try to keep the "home" application in memory (ie, keep it's process around for re-use) so that restarting the home application is very quick.

On a customized (rooted) device, it might be possible to switch in different sets of values for different situations, in order to keep an additional app in memory as well/instead. 

Of course if you run another app that needs most of the physical memory on the device, the desire to keep the home or whatever app available will loose out to the requirement to run the app the user has currently chosen to use.