内容简介:说明:从这篇文章开始,将开始Linux调度器的系列研究了。本文也会从一些基础的概念及数据结构入手,先打造一个粗略的轮廓,后续的文章将逐渐深入。Linux内核使用
背景
-
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()
函数,被唤醒的进程可能抢占当前的进程;
上述讲到的几个函数都是常用于调度时调用。此外,在创建新进程时,或是在内核抢占时,也会出现一些调度点。
本文只是粗略的介绍了一个大概,后续将针对某些模块进行更加深入的分析,敬请期待。
以上所述就是小编给大家介绍的《(一)Linux进程调度器-基础》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 处理器是如何调度进程的?
- linux内核实时进程的调度原理
- Java多线程并发:进程调度算法
- [译] Android display pipeline 本身以及进程调度
- 每天3分钟操作系统修炼秘籍(25):进程调度算法图解说明
- 负载均衡,cgroups,RT补丁-《Linux进程、线程和调度》系列9.22日第四节课ppt分享
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
精通数据科学:从线性回归到深度学习
唐亘 / 人民邮电出版社 / 2018-5-8 / 99.00元
数据科学是一门内涵很广的学科,它涉及到统计分析、机器学习以及计算机科学三方面的知识和技能。本书深入浅出、全面系统地介绍了这门学科的内容。 本书分为13章,最初的3章主要介绍数据科学想要解决的问题、常用的IT工具Python以及这门学科所涉及的数学基础。第4-7章主要讨论数据模型,主要包含三方面的内容:一是统计中最经典的线性回归和逻辑回归模型;二是计算机估算模型参数的随机梯度下降法,这是模型工......一起来看看 《精通数据科学:从线性回归到深度学习》 这本书的介绍吧!