how list_head structure used for scheduling in kernel

Question

I have read a few things from which I can make out that instead of scheduling a task with a scheduling policy it is better that we schedule an entity with a scheduling policy. The advantages being that you can schedule many things with the same scheduling policy. So there are two entities defined for two scheduling policies(CFS and RT) namely as sched_entity and sched_rt_entity. The code for CFS entity is (from v3.5.4)

struct sched_entity {
    struct load_weight  load;       /* for load-balancing */
    struct rb_node      run_node;
    struct list_head    group_node;
    unsigned int        on_rq;

    u64         exec_start;
    u64         sum_exec_runtime;
    u64         vruntime;
    u64         prev_sum_exec_runtime;

    u64         nr_migrations;


#ifdef CONFIG_SCHEDSTATS
    struct sched_statistics statistics;
#endif

#ifdef CONFIG_FAIR_GROUP_SCHED
    struct sched_entity *parent;
    /* rq on which this entity is (to be) queued: */
    struct cfs_rq       *cfs_rq;
    /* rq "owned" by this entity/group: */
    struct cfs_rq       *my_q;
#endif
};

and for RT(real time) entity is

struct sched_rt_entity {
     struct list_head run_list;
     unsigned long timeout;
     unsigned int time_slice;

     struct sched_rt_entity *back;
     #ifdef CONFIG_RT_GROUP_SCHED
     struct sched_rt_entity  *parent;
     /* rq on which this entity is (to be) queued: */
     struct rt_rq            *rt_rq;
     /* rq "owned" by this entity/group: */
     struct rt_rq            *my_q;
     #endif
};

Both of these uses the list_head structures defined in ./include/linux/types.h

struct list_head {
     struct list_head *next, *prev;
};

I honestly do not understand how any such thing is going to be scheduled. Can anyone explain how this is working.

P.S.:

Moreover, I am really having a hard time understanding the meaning of the names of data members. Can anyone suggest a good read for understanding kernel structures so that I can figure out these things a bit easily. Most of the time I spend is wasted in searching what a data member could mean.

score 2 · Accepted Answer · edited Nov 08 '14 at 11:01

2

Scheduling entities were introduced in order to implement group scheduling, so that CFS (or RT scheduler) will provide fair CPU time for individual tasks but also fair CPU time to groups of tasks. Scheduling entity may be either a task or group of tasks.

struct list_head is just Linux way to implement linked list. In the code you posted fields group_node and run_list allow to create lists of struct sched_entity and struct sched_rt_entity. More information can be found here.

Using these list_heads scheduling entities are stored in certain scheduler related data structures, for example cfs_rq.cfs_tasks if an entity is a task enqueued using account_entity_enqueue().

Always up to date documentation of Linux kernel can be found within its sources. In this case you should check this directory and especially this file which describes CFS. There is also an explanation of task groups.

EDIT: task_struct contains a field se of type struct sched_entity. Then, having an address to a sched_entity object using container_of macro it is possible to retrieve an address to the task_struct object, see task_of(). (address of sched_entity object - offset of se in task_struct = address of task_struct object) This is quite common trick used also in the implementation of lists I mentioned earlier in this answer.

edited Nov 08 '14 at 11:01

Ramzi Khahil

4,932
4
35
69

answered Oct 07 '12 at 22:19

Paweł Dziepak

2,062
1
16
17

Thanks it helped but it gave rise to another doubt. Where is the information about the task or group to be scheduled. I do not see any links to, for example task_struct, which is the thing to be scheduled by the policy. – Aman Deep Gautam Oct 07 '12 at 22:28
Also on similar grounds I have this doubt: You said "`group_node` and `run_list` allow to create lists of `struct sched_entity` and `struct sched_rt_entity`" but then by parsing the so formed list through these pointers just give me `list_head` pointers. How do you get the next or previous `sched_entity`. – Aman Deep Gautam Oct 07 '12 at 22:43
`container_of` allows you to get an address of parent structure. See my updated answer and also this: http://stackoverflow.com/questions/5145027/when-do-you-use-container-of-macro – Paweł Dziepak Oct 07 '12 at 22:48
thanks. got it. I was going through the links you provided. I think they do not have got much of implementation details, they are rather more inclined to show design features. But anyway it helped a bit. – Aman Deep Gautam Oct 07 '12 at 22:57
You might want to check Linux Kernel Development (3 ed.) by Robert Love. I do not own that book but it the most recent description of Linux kernel internals I am aware of. – Paweł Dziepak Oct 07 '12 at 23:07
Unfortunately that book does not have much on what I really want. – Aman Deep Gautam Oct 07 '12 at 23:14

how list_head structure used for scheduling in kernel

1 Answers1