Skip to main content
 首页 » 操作系统

Linux进程调度器之基础_学习笔记

2022年07月19日25kuangbin

一、学习笔记

Kernel版本:4.14

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

2. 概念
2.1 进程

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

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 进程状态

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

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

/* 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 来对调度器进行抽象:

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

struct sched_class stop_sched_class; 
struct sched_class dl_sched_class; 
struct sched_class rt_sched_class; 
struct sched_class fair_sched_class; /*kernel 4.19*/ 
struct sched_class idle_sched_class;

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

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

注:RT进程优先级:[0..99];普通进程优先级: [100..139],默认优先级120。定位位置include\linux\sched\prio.h

注:用户空间设置调度策略和优先级的函数,如 sched_setscheduler 设置的RT优先级数值直接写到 task->rt_priority 里面,RT线程的task->prio = 99 - task->rt_priority,task->prio的数值越小,RT优先级越高。task->prio的值可以在cat /proc/<pid>/sched中看到。有这个转换的目的是让在用户空间进行代码设置的时候,sched_param.sched_priority的数值越大,对应的优先级越大。可以看到migration线程的优先级是0(最大)。


2.4 runqueue 运行队列

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

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

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 任务分组

(1) 利用任务分组的机制,可以设置或限制任务组对CPU的利用率,比如将某些任务限制在某个区间内,从而不去影响其他任务的执行效率;
(2) 引入 task_group 后,调度器的调度对象不仅仅是进程了,Linux内核抽象出了 sched_entity/sched_rt_entity/sched_dl_entity 描述调度实体,调度实体可以是进程或 task_group;
(3) 使用数据结构 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. 调度程序

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

3.1 主动调度 - schedule()

(1) schedule()函数,是进程调度的核心函数,大体的流程如上图所示。
(2)核心的逻辑:选择另外一个进程来替换掉当前运行的进程。进程的选择是通过进程所使用的调度器中的 pick_next_task 函数来实现的,不同的调度器实现的方法不一样;进程的替换是通过 context_switch() 来完成切换的,具体的细节后续的文章再深入分析。


3.2 周期调度 - schedule_tick()

(1) 时钟中断处理程序中,调用 schedule_tick()函数;
(2) 时钟中断是调度器的脉搏,内核依靠周期性的时钟来处理器CPU的控制权;
(3) 时钟中断处理程序,检查当前进程的执行时间是否超额,如果超额则设置重新调度标志(_TIF_NEED_RESCHED);
(4) 时钟中断处理函数返回时,被中断的进程如果在用户模式下运行,需要检查是否有重新调度标志,设置了则调用 schedule()调度;


3.3 高精度时钟调度 - hrtick()

(1) 高精度时钟调度,与周期性调度类似,不同点在于周期调度的精度为ms级别,而高精度调度的精度为ns级别;
(2) 高精度时钟调度,需要有对应的硬件支持;

3.4 进程唤醒时调度 - wake_up_process()

(1) 唤醒进程时调用 wake_up_process()函数,被唤醒的进程可能抢占当前的进程;

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

参考:(一)Linux进程调度器-基础

fair_sched_class

如果我们失败了并且做了一部分,请回滚。


本文参考链接:https://www.cnblogs.com/hellokitty2/p/14296028.html