• Read the fucking source code! –By 鲁迅
  • A picture is worth a thousand words. –By 高尔基

说明：

  1. Kernel版本：4.14
  2. ARM64处理器，Contex-A53，双核
  3. 使用工具：Source Insight 3.5， Visio

从这篇文章开始，将开始Linux调度器的系列研究了。
本文也会从一些基础的概念及数据结构入手，先打造一个粗略的轮廓，后续的文章将逐渐深入。

  • 从教科书上，我们都能知道：进程是资源分配的最小单位，而线程是CPU调度的的最小单位。
  • 进程不仅包括可执行程序的代码段，还包括一系列的资源，比如：打开的文件、内存、CPU时间、信号量、多个执行线程流等等。而线程可以共享进程内的资源空间。
  • 在Linux内核中，进程和线程都使用struct task_struct结构来进行抽象描述。
  • 进程的虚拟地址空间分为用户虚拟地址空间和内核虚拟地址空间，所有进程共享内核虚拟地址空间，没有用户虚拟地址空间的进程称为内核线程。

Linux内核使用task_struct结构来抽象，该结构包含了进程的各类信息及所拥有的资源，比如进程的状态、打开的文件、地址空间信息、信号资源等等。task_struct结构很复杂，下边只针对与调度相关的某些字段进行介绍。

  1. struct task_struct {
  2.     /* ... */
  3.     
  4.     /* 进程状态 */
  5.     volatile long           state;
  7.     /* 调度优先级相关，策略相关 */
  8.     int             prio;
  9.     int             static_prio;
  10.     int             normal_prio;
  11.     unsigned int            rt_priority;
  12.     unsigned int            policy;
  13.     
  14.     /* 调度类，调度实体相关，任务组相关等 */
  15.     const struct sched_class    *sched_class;
  16.     struct sched_entity     se;
  17.     struct sched_rt_entity      rt;
  18. #ifdef CONFIG_CGROUP_SCHED
  19.     struct task_group       *sched_task_group;
  20. #endif
  21.     struct sched_dl_entity      dl;
  22.     
  23.     /* 进程之间的关系相关 */
  24.         /* Real parent process: */
  25.     struct task_struct __rcu    *real_parent;
  27.     /* Recipient of SIGCHLD, wait4() reports: */
  28.     struct task_struct __rcu    *parent;
  30.     /*
  31.      * Children/sibling form the list of natural children:
  32.      */
  33.     struct list_head        children;
  34.     struct list_head        sibling;
  35.     struct task_struct      *group_leader;
  36.     
  37.     /* ... */
  38. }

  • 上图中左侧为操作系统中通俗的进程三状态模型，右侧为Linux对应的进程状态切换。每一个标志描述了进程的当前状态，这些状态都是互斥的；
  • Linux中的就绪态和运行态对应的都是TASK_RUNNING标志位，就绪态表示进程正处在队列中，尚未被调度；运行态则表示进程正在CPU上运行；

内核中主要的状态字段定义如下

  1. /* Used in tsk->state: */
  2. #define TASK_RUNNING            0x0000
  3. #define TASK_INTERRUPTIBLE      0x0001
  4. #define TASK_UNINTERRUPTIBLE        0x0002
  6. /* Used in tsk->exit_state: */
  7. #define EXIT_DEAD           0x0010
  8. #define EXIT_ZOMBIE         0x0020
  9. #define EXIT_TRACE          (EXIT_ZOMBIE | EXIT_DEAD)
  11. /* Used in tsk->state again: */
  12. #define TASK_PARKED         0x0040
  13. #define TASK_DEAD           0x0080
  14. #define TASK_WAKEKILL           0x0100
  15. #define TASK_WAKING         0x0200
  16. #define TASK_NOLOAD         0x0400
  17. #define TASK_NEW            0x0800
  18. #define TASK_STATE_MAX          0x1000
  20. /* Convenience macros for the sake of set_current_state: */
  21. #define TASK_KILLABLE           (TASK_WAKEKILL | TASK_UNINTERRUPTIBLE)
  22. #define TASK_STOPPED            (TASK_WAKEKILL | __TASK_STOPPED)
  23. #define TASK_TRACED         (TASK_WAKEKILL | __TASK_TRACED)
  25. #define TASK_IDLE           (TASK_UNINTERRUPTIBLE | TASK_NOLOAD)

  • 所谓调度，就是按照某种调度的算法，从进程的就绪队列中选取进程分配CPU，主要是协调对CPU等的资源使用。进程调度的目标是最大限度利用CPU时间。

内核默认提供了5个调度器，Linux内核使用struct sched_class来对调度器进行抽象：

  1. Stop调度器， stop_sched_class：优先级最高的调度类，可以抢占其他所有进程，不能被其他进程抢占；
  2. Deadline调度器， dl_sched_class：使用红黑树，把进程按照绝对截止期限进行排序，选择最小进程进行调度运行；
  3. RT调度器， rt_sched_class：实时调度器，为每个优先级维护一个队列；
  4. CFS调度器， cfs_sched_class：完全公平调度器，采用完全公平调度算法，引入虚拟运行时间概念；
  5. IDLE-Task调度器， idle_sched_class：空闲调度器，每个CPU都会有一个idle线程，当没有其他进程可以调度时，调度运行idle线程；

Linux内核提供了一些调度策略供用户程序来选择调度器，其中Stop调度器和IDLE-Task调度器，仅由内核使用，用户无法进行选择：

  • SCHED_DEADLINE：限期进程调度策略，使task选择Deadline调度器来调度运行；
  • SCHED_RR：实时进程调度策略，时间片轮转，进程用完时间片后加入优先级对应运行队列的尾部，把CPU让给同优先级的其他进程；
  • SCHED_FIFO：实时进程调度策略，先进先出调度没有时间片，没有更高优先级的情况下，只能等待主动让出CPU；
  • SCHED_NORMAL：普通进程调度策略，使task选择CFS调度器来调度运行；
  • SCHED_BATCH：普通进程调度策略，批量处理，使task选择CFS调度器来调度运行；
  • SCHED_IDLE：普通进程调度策略，使task以最低优先级选择CFS调度器来调度运行；

  • 每个CPU都有一个运行队列，每个调度器都作用于运行队列；
  • 分配给CPU的task，作为调度实体加入到运行队列中；
  • task首次运行时，如果可能，尽量将它加入到父task所在的运行队列中（分配给相同的CPU，缓存affinity会更高，性能会有改善）；

Linux内核使用struct rq结构来描述运行队列，关键字段如下：

  1. /*
  2.  * This is the main, per-CPU runqueue data structure.
  3.  *
  4.  * Locking rule: those places that want to lock multiple runqueues
  5.  * (such as the load balancing or the thread migration code), lock
  6.  * acquire operations must be ordered by ascending &runqueue.
  7.  */
  8. struct rq {
  9.     /* runqueue lock: */
  10.     raw_spinlock_t lock;
  12.     /*
  13.      * nr_running and cpu_load should be in the same cacheline because
  14.      * remote CPUs use both these fields when doing load calculation.
  15.      */
  16.     unsigned int nr_running;
  17.     
  18.     /* 三个调度队列：CFS调度，RT调度，DL调度 */
  19.     struct cfs_rq cfs;
  20.     struct rt_rq rt;
  21.     struct dl_rq dl;
  23.     /* stop指向迁移内核线程， idle指向空闲内核线程 */
  24.     struct task_struct *curr, *idle, *stop;
  25.     
  26.     /* ... */
  27. }

  • 利用任务分组的机制，可以设置或限制任务组对CPU的利用率，比如将某些任务限制在某个区间内，从而不去影响其他任务的执行效率；
  • 引入task_group后，调度器的调度对象不仅仅是进程了，Linux内核抽象出了sched_entity/sched_rt_entity/sched_dl_entity描述调度实体，调度实体可以是进程或task_group；
  • 使用数据结构struct task_group来描述任务组，任务组在每个CPU上都会维护一个CFS调度实体、CFS运行队列，RT调度实体，RT运行队列；

Linux内核使用struct task_group来描述任务组，关键的字段如下：

  1. /* task group related information */
  2. struct task_group {
  3.     /* ... */
  5.     /* 为每个CPU都分配一个CFS调度实体和CFS运行队列 */
  6. #ifdef CONFIG_FAIR_GROUP_SCHED
  7.     /* schedulable entities of this group on each cpu */
  8.     struct sched_entity **se;
  9.     /* runqueue "owned" by this group on each cpu */
  10.     struct cfs_rq **cfs_rq;
  11.     unsigned long shares;
  12. #endif
  14.     /* 为每个CPU都分配一个RT调度实体和RT运行队列 */
  15. #ifdef CONFIG_RT_GROUP_SCHED
  16.     struct sched_rt_entity **rt_se;
  17.     struct rt_rq **rt_rq;
  19.     struct rt_bandwidth rt_bandwidth;
  20. #endif
  22.     /* task_group之间的组织关系 */
  23.     struct rcu_head rcu;
  24.     struct list_head list;
  26.     struct task_group *parent;
  27.     struct list_head siblings;
  28.     struct list_head children;
  30.     /* ... */
  31. };

调度程序依靠几个函数来完成调度工作的，下边将介绍几个关键的函数。

  1. 主动调度 – schedule()
  • schedule()函数，是进程调度的核心函数，大体的流程如上图所示。
  • 核心的逻辑：选择另外一个进程来替换掉当前运行的进程。进程的选择是通过进程所使用的调度器中的pick_next_task函数来实现的，不同的调度器实现的方法不一样；进程的替换是通过context_switch()来完成切换的，具体的细节后续的文章再深入分析。
  1. 周期调度 – schedule_tick()
  • 时钟中断处理程序中，调用schedule_tick()函数；
  • 时钟中断是调度器的脉搏，内核依靠周期性的时钟来处理器CPU的控制权；
  • 时钟中断处理程序，检查当前进程的执行时间是否超额，如果超额则设置重新调度标志(_TIF_NEED_RESCHED)；
  • 时钟中断处理函数返回时，被中断的进程如果在用户模式下运行，需要检查是否有重新调度标志，设置了则调用schedule()调度；
  1. 高精度时钟调度 – hrtick()
  • 高精度时钟调度，与周期性调度类似，不同点在于周期调度的精度为ms级别，而高精度调度的精度为ns级别；
  • 高精度时钟调度，需要有对应的硬件支持；
  1. 进程唤醒时调度 – wake_up_process()
  • 唤醒进程时调用wake_up_process()函数，被唤醒的进程可能抢占当前的进程；

上述讲到的几个函数都是常用于调度时调用。此外，在创建新进程时，或是在内核抢占时，也会出现一些调度点。

本文只是粗略的介绍了一个大概，后续将针对某些模块进行更加深入的分析，敬请期待。

版权声明：本文为LoyenWang原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/LoyenWang/p/12249106.html