电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 使用完全公平调度程序（CFS）进行多任务处理（2）重要的 CFS 数据结构 [打印本页]

作者: look_w 时间: 2018-5-22 15:21 标题: 使用完全公平调度程序（CFS）进行多任务处理（2）重要的 CFS 数据结构

重要的 CFS 数据结构对于每个 CPU，CFS 使用按时间排序的红黑（red-black）树。
红黑树的 Wikipedia 定义根据的解释，红黑树 是一种自平衡二叉搜索树，这种数据结构可用于实现关联数组。对于每个运行中的进程，在红黑树上都有一个节点。红黑树上位于最左侧的进程表示将进行下一次调度的进程。红黑树比较复杂，但它的操作具有良好的最差情况（worst-case）运行时，并且在实际操作中非常高效：它可以在 O(log n) 时间内搜索、插入和删除，其中 n 表示树元素的数量。叶节点意义不大并且不包含数据。为节省内存，有时使用单个哨兵（sentinel）节点执行所有叶节点的角色。内部节点到叶节点的所有引用都指向哨兵节点。

该树方法能够良好运行的原因在于：

红黑树可以始终保持平衡。
由于红黑树是二叉树，查找操作的时间复杂度为对数。但是，除了最左侧查找以外，很难执行其他查找，并且最左侧的节点指针始终被缓存。
对于大多数操作，红黑树的执行时间为 O(log n)，而以前的调度程序通过具有固定优先级的优先级数组使用 O(1)。O(log n) 行为具有可测量的延迟，但是对于较大的任务数无关紧要。Molnar 在尝试这种树方法时，首先对这一点进行了测试。
红黑树可通过内部存储实现 — 即不需要使用外部分配即可对数据结构进行维护。

让我们了解一下实现这种新调度程序的一些关键数据结构。
struct task_struct 的变化 CFS 去掉了 struct prio_array，并引入调度实体（scheduling entity）和调度类（scheduling classes），分别由 struct sched_entity 和 struct sched_class 定义。因此，task_struct 包含关于 sched_entity 和 sched_class 这两种结构的信息：
清单 1. task_struct 结构

1
2
3
4
5
6
7
8

struct task_struct { /* Defined in 2.6.23:/usr/include/linux/sched.h */
....
- struct prio_array *array;
+ struct sched_entity se;
+ struct sched_class *sched_class;
....
....
};

struct sched_entity 该结构包含了完整的信息，用于实现对单个任务或任务组的调度。它可用于实现组调度。调度实体可能与进程没有关联。
清单 2. sched_entity 结构

1
2
3
4
5
6
7
8
9

struct sched_entity { /* Defined in 2.6.23:/usr/include/linux/sched.h */
long wait_runtime; /* Amount of time the entity must run to become completely */
                  /* fair and balanced.*/
s64 fair_key;
struct load_weight load;       /* for load-balancing */
struct rb_node run_node;          /* To be part of Red-black tree data structure */
unsigned int on_rq;
....
};

struct sched_class 该调度类类似于一个模块链，协助内核调度程序工作。每个调度程序模块需要实现 struct sched_class 建议的一组函数。
清单 3. sched_class 结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

struct sched_class { /* Defined in 2.6.23:/usr/include/linux/sched.h */
   struct sched_class *next;
   void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
   void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
   void (*yield_task) (struct rq *rq, struct task_struct *p);

   void (*check_preempt_curr) (struct rq *rq, struct task_struct *p);

   struct task_struct * (*pick_next_task) (struct rq *rq);
   void (*put_prev_task) (struct rq *rq, struct task_struct *p);

   unsigned long (*load_balance) (struct rq *this_rq, int this_cpu,
               struct rq *busiest,
               unsigned long max_nr_move, unsigned long max_load_move,
               struct sched_domain *sd, enum cpu_idle_type idle,
               int *all_pinned, int *this_best_prio);

   void (*set_curr_task) (struct rq *rq);
   void (*task_tick) (struct rq *rq, struct task_struct *p);
   void (*task_new) (struct rq *rq, struct task_struct *p);
};

我们来看一下清单 3 中的函数：

enqueue_task：当某个任务进入可运行状态时，该函数将得到调用。它将调度实体（进程）放入红黑树中，并对 nr_running 变量加 1。
dequeue_task：当某个任务退出可运行状态时调用该函数，它将从红黑树中去掉对应的调度实体，并从 nr_running 变量中减 1。
yield_task：在 compat_yield sysctl 关闭的情况下，该函数实际上执行先出队后入队；在这种情况下，它将调度实体放在红黑树的最右端。
check_preempt_curr：该函数将检查当前运行的任务是否被抢占。在实际抢占正在运行的任务之前，CFS 调度程序模块将执行公平性测试。这将驱动唤醒式（wakeup）抢占。
pick_next_task：该函数选择接下来要运行的最合适的进程。
load_balance：每个调度程序模块实现两个函数，load_balance_start() 和 load_balance_next()，使用这两个函数实现一个迭代器，在模块的 load_balance 例程中调用。内核调度程序使用这种方法实现由调度模块管理的进程的负载平衡。
set_curr_task：当任务修改其调度类或修改其任务组时，将调用这个函数。
task_tick：该函数通常调用自 time tick 函数；它可能引起进程切换。这将驱动运行时（running）抢占。
task_new：内核调度程序为调度模块提供了管理新任务启动的机会。CFS 调度模块使用它进行组调度，而用于实时任务的调度模块则不会使用这个函数。

运行队列中与 CFS 有关的字段对于每个运行队列，都提供了一种结构来保存相关红黑树的信息。
清单 4. cfs_rq 结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

struct cfs_rq {/* Defined in 2.6.23:kernel/sched.c */
   struct load_weight load;
   unsigned long nr_running;

   s64 fair_clock; /* runqueue wide global clock */
   u64 exec_clock;
   s64 wait_runtime;
   u64 sleeper_bonus;
   unsigned long wait_runtime_overruns, wait_runtime_underruns;

   struct rb_root tasks_timeline; /* Points to the root of the rb-tree*/
   struct rb_node *rb_leftmost; /* Points to most eligible task to give the CPU */
   struct rb_node *rb_load_balance_curr;
#ifdef CONFIG_FAIR_GROUP_SCHED
   struct sched_entity *curr; /* Currently running entity */
   struct rq *rq;    /* cpu runqueue to which this cfs_rq is attached */
   ...
   ...
#endif
};

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)