（一）Linux进程调度器-基础
2012 年 8 月 2 日
背景
-
Read the fucking source code!
–By 鲁迅 -
A picture is worth a thousand words.
–By 高尔基
说明：
- Kernel版本：4.14
- ARM64处理器，Contex-A53，双核
- 使用工具：Source Insight 3.5， Visio
1. 概述
从这篇文章开始，将开始Linux调度器的系列研究了。本文也会从一些基础的概念及数据结构入手，先打造一个粗略的轮廓，后续的文章将逐渐深入。
2. 概念
2.1 进程
- 从教科书上，我们都能知道：进程是资源分配的最小单位，而线程是CPU调度的的最小单位。
- 进程不仅包括可执行程序的代码段，还包括一系列的资源，比如：打开的文件、内存、CPU时间、信号量、多个执行线程流等等。而线程可以共享进程内的资源空间。
-
在Linux内核中，进程和线程都使用
struct task_struct
结构来进行抽象描述。 - 进程的虚拟地址空间分为用户虚拟地址空间和内核虚拟地址空间，所有进程共享内核虚拟地址空间，没有用户虚拟地址空间的进程称为内核线程。
Linux内核使用 task_struct
结构来抽象，该结构包含了进程的各类信息及所拥有的资源，比如进程的状态、打开的文件、地址空间信息、信号资源等等。 task_struct
结构很复杂，下边只针对与调度相关的某些字段进行介绍。
struct task_struct { /* ... */ /* 进程状态 */ volatile long state;
/* 调度优先级相关，策略相关 */ int prio; int static_prio; int normal_prio; unsigned int rt_priority; unsigned int policy; /* 调度类，调度实体相关，任务组相关等 */ const struct sched_class *sched_class; struct sched_entity se; struct sched_rt_entity rt; #ifdef CONFIG_CGROUP_SCHED struct task_group *sched_task_group; #endif struct sched_dl_entity dl; /* 进程之间的关系相关 */ /* Real parent process: */ struct task_struct __rcu *real_parent;
/* Recipient of SIGCHLD, wait4() reports: */ struct task_struct __rcu *parent;
/* * Children/sibling form the list of natural children: */ struct list_head children; struct list_head sibling; struct task_struct *group_leader; /* ... */ }
2.2 进程状态
- 上图中左侧为操作系统中通俗的进程三状态模型，右侧为Linux对应的进程状态切换。每一个标志描述了进程的当前状态，这些状态都是互斥的；
-
就绪态 运行态 TASK_RUNNING 就绪态 运行态
内核中主要的状态字段定义如下
/* Used in tsk->state: */ #define TASK_RUNNING 0x0000 #define TASK_INTERRUPTIBLE 0x0001 #define TASK_UNINTERRUPTIBLE 0x0002
/* Used in tsk->exit_state: */ #define EXIT_DEAD 0x0010 #define EXIT_ZOMBIE 0x0020 #define EXIT_TRACE (EXIT_ZOMBIE | EXIT_DEAD)
/* Used in tsk->state again: */ #define TASK_PARKED 0x0040 #define TASK_DEAD 0x0080 #define TASK_WAKEKILL 0x0100 #define TASK_WAKING 0x0200 #define TASK_NOLOAD 0x0400 #define TASK_NEW 0x0800 #define TASK_STATE_MAX 0x1000
/* Convenience macros for the sake of set_current_state: */ #define TASK_KILLABLE (TASK_WAKEKILL | TASK_UNINTERRUPTIBLE) #define TASK_STOPPED (TASK_WAKEKILL | __TASK_STOPPED) #define TASK_TRACED (TASK_WAKEKILL | __TASK_TRACED)
#define TASK_IDLE (TASK_UNINTERRUPTIBLE | TASK_NOLOAD)
2.3 scheduler 调度器
- 所谓调度，就是按照某种调度的算法，从进程的就绪队列中选取进程分配CPU，主要是协调对CPU等的资源使用。进程调度的目标是最大限度利用CPU时间。
内核默认提供了5个调度器，Linux内核使用 struct sched_class
来对调度器进行抽象：
-
Stop调度器， stop_sched_class
：优先级最高的调度类，可以抢占其他所有进程，不能被其他进程抢占； -
Deadline调度器， dl_sched_class
：使用红黑树，把进程按照绝对截止期限进行排序，选择最小进程进行调度运行； -
RT调度器， rt_sched_class
：实时调度器，为每个优先级维护一个队列； -
CFS调度器， cfs_sched_class
：完全公平调度器，采用完全公平调度算法，引入虚拟运行时间概念； -
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调度器
来调度运行；
2.4 runqueue 运行队列
- 每个CPU都有一个运行队列，每个调度器都作用于运行队列；
- 分配给CPU的task，作为调度实体加入到运行队列中；
- task首次运行时，如果可能，尽量将它加入到父task所在的运行队列中（分配给相同的CPU，缓存affinity会更高，性能会有改善）；
Linux内核使用 struct rq
结构来描述运行队列，关键字段如下：
/* * This is the main, per-CPU runqueue data structure. * * Locking rule: those places that want to lock multiple runqueues * (such as the load balancing or the thread migration code), lock * acquire operations must be ordered by ascending &runqueue. */ struct rq { /* runqueue lock: */ raw_spinlock_t lock;
/* * nr_running and cpu_load should be in the same cacheline because * remote CPUs use both these fields when doing load calculation. */ unsigned int nr_running; /* 三个调度队列：CFS调度，RT调度，DL调度 */ struct cfs_rq cfs; struct rt_rq rt; struct dl_rq dl;
/* stop指向迁移内核线程， idle指向空闲内核线程 */ struct task_struct *curr, *idle, *stop; /* ... */ }
2.5 task_group 任务分组
- 利用任务分组的机制，可以设置或限制任务组对CPU的利用率，比如将某些任务限制在某个区间内，从而不去影响其他任务的执行效率；
-
task_group sched_entity/sched_rt_entity/sched_dl_entity task_group
-
使用数据结构
struct task_group
来描述任务组，任务组在每个CPU上都会维护一个CFS调度实体、CFS运行队列，RT调度实体，RT运行队列
；
Linux内核使用 struct task_group
来描述任务组，关键的字段如下：
/* task group related information */ struct task_group { /* ... */
/* 为每个CPU都分配一个CFS调度实体和CFS运行队列 */ #ifdef CONFIG_FAIR_GROUP_SCHED /* schedulable entities of this group on each cpu */ struct sched_entity **se; /* runqueue "owned" by this group on each cpu */ struct cfs_rq **cfs_rq; unsigned long shares; #endif
/* 为每个CPU都分配一个RT调度实体和RT运行队列 */ #ifdef CONFIG_RT_GROUP_SCHED struct sched_rt_entity **rt_se; struct rt_rq **rt_rq;
struct rt_bandwidth rt_bandwidth; #endif
/* task_group之间的组织关系 */ struct rcu_head rcu; struct list_head list;
struct task_group *parent; struct list_head siblings; struct list_head children;
/* ... */ };
3. 调度程序
调度程序依靠几个函数来完成调度工作的，下边将介绍几个关键的函数。
-
主动调度 –
schedule()
-
schedule()
函数，是进程调度的核心函数，大体的流程如上图所示。 -
核心的逻辑：选择另外一个进程来替换掉当前运行的进程。进程的选择是通过进程所使用的调度器中的
pick_next_task
函数来实现的，不同的调度器实现的方法不一样；进程的替换是通过context_switch()
来完成切换的，具体的细节后续的文章再深入分析。
-
周期调度 –
schedule_tick()
-
时钟中断处理程序中，调用
schedule_tick()
函数； - 时钟中断是调度器的脉搏，内核依靠周期性的时钟来处理器CPU的控制权；
-
时钟中断处理程序，检查当前进程的执行时间是否超额，如果超额则设置重新调度标志(
_TIF_NEED_RESCHED
)； -
时钟中断处理函数返回时，被中断的进程如果在用户模式下运行，需要检查是否有重新调度标志，设置了则调用
schedule()
调度；
-
高精度时钟调度 –
hrtick()
- 高精度时钟调度，与周期性调度类似，不同点在于周期调度的精度为ms级别，而高精度调度的精度为ns级别；
- 高精度时钟调度，需要有对应的硬件支持；
-
进程唤醒时调度 –
wake_up_process()
-
唤醒进程时调用
wake_up_process()
函数，被唤醒的进程可能抢占当前的进程；
上述讲到的几个函数都是常用于调度时调用。此外，在创建新进程时，或是在内核抢占时，也会出现一些调度点。
本文只是粗略的介绍了一个大概，后续将针对某些模块进行更加深入的分析，敬请期待。
About The Author
