Zephyr内核时间片实现分析

Creative Commons
本作品采用知识共享署名
发表于 | 分类于 | | 阅读次数：

本文分析Zephyr内核时间片的实现原理。

Zephyr的时间片是用于解决同优先级抢占式线程长时间占用CPU的问题，调度器将CPU时间以tick为单位切分为时间片，让同优先级的线程以时间片使用CPU，具体有如下特性:

  1. 只适用于抢占式线程
  2. 低于指定优先级的线程才会执行时间片
  3. 运行时可以改变时间片的大小
  4. 线程一个时间片内可以被高优先级线程抢占，一个时间片执行完后主动让出CPU给其它同优的先级线程
  5. 内核的时间片算法不能确保一组同等优先级的线程获得公平的 CPU 时间

配置

相关配置项可以参考kernel/kconfig

依赖配置

时间片由系统时钟支持，因此CONFIG_SYS_CLOCK_EXISTS=y是必须的，由于时间片只使用于抢占式线程因此CONFIG_NUM_PREEMPT_PRIORITIES不能为0.

直接相关配置

CONFIG_TIMESLICING=y配置启用时间片，Zephyr默认是启用的
CONFIG_TIMESLICE_SIZE=0配置时间片大小，默认是0表示时间片无穷大(相当于是无时间片功能)，单位为ms，代码中会转为ticks，因此会有误差
CONFIG_TIMESLICE_PRIORITY 支持时间片线程的最高优先级，只有小于等于该优先级的线程才会使用时间片。配置取值范围为0~CONFIG_NUM_PREEMPT_PRIORITIES

代码分析

内核全局的维护一个slice_time和slice_max_prio分别用于保存时间片的大小和允许执行时间片的最大线程优先级。
这两个全局变量在运行时可以使用k_sched_time_slice_set设置，在调度初始化时z_sched_init用k_sched_time_slice_set(CONFIG_TIMESLICE_SIZE, CONFIG_TIMESLICE_PRIORITY)设置为默认配置的值
每一颗CPU维护一个slice_ticks，记录当前时间片还是多少个tick，每当一次tick发生时slice_ticks就会减1，直到slice_ticks为0时，切换到其它同优先级线程执行。
当一个正在使用时间片的线程因为非时间片到的原因发生了调度(高优先级线程抢占, 等待)，该线程时间片剩余未用的tick将被清0，下一次调度该线程时将重新执行一个完整的时间片。这也就是前面提到的不能保证同一组同优先级的线程获得公平的CPU时间的原因。

本文主要分析时间片如何生效，调度的细节可以参考[1]。为了方便讨论，本文不分析Tickless情况下的时间片。

设置时间片

在调度器初始化和运行时都会使用k_sched_time_slice_set设置时间片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void k_sched_time_slice_set(int32_t slice, int prio)
{
	LOCKED(&sched_spinlock) {
		_current_cpu->slice_ticks = 0;
		//将ms转换为tick，设置时间片tick数
		slice_time = k_ms_to_ticks_ceil32(slice);
		
		//tickless的情况下不运行slice_time为1个tick，这样将导致tickless无效
		if (IS_ENABLED(CONFIG_TICKLESS_KERNEL) && slice > 0) {
			slice_time = MAX(2, slice_time);
		}
		//设置时间片线程优先级
		slice_max_prio = prio;
		
		//更新_current_cpu->slice_ticks，因为重新设置了时间片大小，因此要对slice_ticks进行更新
		z_reset_time_slice();
	}
}

slice_time更新

在z_reset_time_slice中计算一个时间片的初始化大小

1
2
3
4
5
6
7
void z_reset_time_slice(void)
{
	if (slice_time != 0) {
		_current_cpu->slice_ticks = slice_time + sys_clock_elapsed();
		z_set_timeout_expiry(slice_time, false);
	}
}

对于非Tickless的情况，sys_clock_elapsed()和z_set_timeout_expiry(slice_time, false)都无效，因此_current_cpu->slice_ticks就是slice_time。

时间片如何生效

在非Tickless下，每个Tick都会产生一个中断，例如RT1052目前使用的就是systick timer来产生tick中断，当每个tick中断发生时将执行cortex_m_systick.c中的sys_clock_isr中断服务函数：
sys_clock_isr->sys_clock_announce(1)->z_time_slice(ticks) 最后通过z_time_slice让时间片生效

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void z_time_slice(int ticks)
{
    //对于非tickless， ticks只会是1
	k_spinlock_key_t key = k_spin_lock(&sched_spinlock);

	if (slice_time && sliceable(_current)) {
        //如果支持时间片
		if (ticks >= _current_cpu->slice_ticks) {
            //如果当前cpu的时间片slice_ticks耗尽，会将当前的线程移除并重新加入到就绪列队，相当于是让出了cpu，参考[1]
			move_thread_to_end_of_prio_q(_current);
            //slice_time更新, 复位时间片
			z_reset_time_slice();
		} else {
            //如果当前时间片没有耗尽，从slice_ticks减去已经执行的tick数
			_current_cpu->slice_ticks -= ticks;
		}
	} else {
        //不支持时间片
		_current_cpu->slice_ticks = 0;
	}
	k_spin_unlock(&sched_spinlock, key);
}

判断线程是否支持时间片

1
2
3
4
5
6
7
static inline int sliceable(struct k_thread *thread)
{
	return is_preempt(thread)       //只有可抢占式线程支持时间片
		&& !z_is_thread_prevented_from_running(thread)      //正常运行的线程才能支持时间片
		&& !z_is_prio_higher(thread->base.prio, slice_max_prio) //高于指定时间片优先级的线程才能支持时间片
		&& !z_is_idle_thread_object(thread);  //idle线程不支持时间片
}

当发生调度时会更新时间片，由于_current_cpu->slice_ticks是以CPU为单位全局的记录时间片消耗情况，被抢占线程的剩余的时间片会被舍去，这将导致同优先级的线程不能获得公平的CPU时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void update_cache(int preempt_ok)
{
    //调度时获取下一个最合适的线程
	struct k_thread *thread = next_up();

	if (should_preempt(thread, preempt_ok)) {
#ifdef CONFIG_TIMESLICING
        //如果下一个调度的线程会抢占当前线程，重新计算时间片
		if (thread != _current) {
			z_reset_time_slice();
		}
#endif
		update_metairq_preempt(thread);
		_kernel.ready_q.cache = thread;
	} else {
		_kernel.ready_q.cache = _current;
	}
}

关于Tickless

同时开启时间片和Tickless主要考虑2方面：

  1. Tickless要考虑时间片长短，避免中断间隔长度超过时间片长度。
  2. z_time_slice处理的两次tickless中断的多个tick数，当复位时间片时，ticks已经被消耗了一部分，为了避免多计算时间片长度需要考虑这一部分。
    更详细的细节将在Tickless一文中分析。

参考

https://docs.zephyrproject.org/latest/reference/kernel/scheduling/index.html?highlight=slicing#preemptive-time-slicing
https://docs.zephyrproject.org/latest/reference/kernel/timing/clocks.html?highlight=slicing#time-slicing