Zephyr内核Tickless详解

本文分析说明Zephyr内核Tickless的实现。

前文参考
[1] Zephyr Tick Clock简介
[2] Zephyr内核Timeout模块简介
[3] Zephyr电源管理-Tickless Idle

先看wiki上对Tickless kernel的描述”A tickless kernel is an operating system kernel in which timer interrupts do not occur at regular intervals, but are only delivered as required”
操作系统内核Timer中断不是周期性的产生，只在需要的时候产生。当内核不是Tickless的情况下，每个Tick都会产生一次中断，内核在中断内进行Timeout和调度的相关处理。但实际上Timeout并不会频繁到每个Tick都需要处理，每个Tick都中断一次都做的是无用功，中断时产生的上下文切换就是无必要的开销。由于内核会管理所有的Timeout，因此内核自己知道下一次Timeout是什么时候，通过设置timer过期时间可以让Timer在下一次Timeout的时候再产生中断，这就叫需要的时候产生，避免了不必要的Tick中断，也就是我们说的Tickless。
Zephyr内核支援Tickless， 并基于Tickless提供以下两个功能

• 运行时：减少不必要的Tick中断
• idle时：SOC进入idle，需要运行时从idle中唤醒

Tickless的实现依赖于硬件Timer，本文以Cortex-M的systick timer为基础进行分析。

配置

系统要支持Tickless，必须要有硬件timer支持sys clock，通过下面配置项进行配置：
CONFIG_SYS_CLOCK_EXISTS=y 配置启用系统时钟，kernel/Kconfig中是默认选中该项的
CONFIG_CORTEX_M_SYSTICK=y 选择系统时钟Timer为systick，不同的平台会用不同的Timer，可以参考文件drivers/timer/Kconfig，里面包含select TICKLESS_CAPABLE的timer就是支持Tickless的。
CONFIG_TICKLESS_KERNEL=y 配置启用Tickless，实际上只要配置的Timer支持TICKLESS_CAPABLE，kernel/Kconfig检查到有TICKLESS_CAPABLE就会将CONFIG_TICKLESS_KERNEL配置起来
因此只要配置了CONFIG_CORTEX_M_SYSTICK=y Zephyr就会以Tickless工作。
CONFIG_SYS_CLOCK_HW_CYCLES_PER_SEC=600000000 配置硬件时钟，这里为600M, CPU的工作频率，也是systick的时钟频率
CONFIG_SYS_CLOCK_TICKS_PER_SEC=10000 配置内核每秒有多少个Tick，一般情况下我们无需配置，在kernel/Kconfig对其有默认设置，非Tickless为100，Tickless情况下为10000，非Tickless的单个tick时间更短，原因后面会做说明。
在Tickless启用的情况下，600M的clock，一个tick有60000个硬件clock，对于精简指令系统来说一个tick可以执行60000条指令。

Tickless

Tickless就是在需要的时候产生中断，要实现这个目标需要以下两个支撑：

• Timer允许设置指定的时间产生中断
• 内核能够计算出何时需要产生中断

在Zephyr中是以tick为单位计算时间，在Tickless下硬件Timer的过期时间会跨多个Tick，因此更短的Tick可以提高精度，由于是多个Tick才会产生一次中断也不用担心Tick太短导致Timer中断变多。

计算何时需要产生中断

运行时

Zephyr在运行时，只有在处理内核对象注册Timeout的情况下才需要产生中断，从[2]中我们知道所有的timeout都被timeout list管理，因此通过timeout list就可以得到最近一次需要产生中断的时间。[2]中说明了这一流程：
内核对象通过z_add_timeout将timeout加入到timeout list， sys_clock_announce90中通过next_timeout()获取到最近一次需要中断的时间再通过sys_clock_set_timeout90设置下一次中断时间

static int32_t next_timeout(void)
{
	struct _timeout *to = first();	//从timeout list中取出最近一个要到期的timeout，timeout list的管理可以参考[2]
	int32_t ticks_elapsed = elapsed();
	
	//如果没有timeout要处理就按照最大时间设置产生Timer中断
	int32_t ret = to == NULL ? MAX_WAIT
		: CLAMP(to->dticks - ticks_elapsed, 0, MAX_WAIT);

	return ret;
}

Idle时

当idle线程运行时，说明现在系统无其它线程运行可以进入idle，在Tickless电源管理配置打开后，会通过下面流程设置下一次中断时间，并在设置好中断Timer后让CPU进入idle状态，详细可以参考价[3]
pm_save_idle->pm_system_suspend->z_set_timeout_expiry->sys_clock_set_timeout

static void pm_save_idle(void)
{
#ifdef CONFIG_PM
	//获取下一次中断产生的时间，z_get_next_timeout_expiry就是直接调用的next_timeout
	int32_t ticks = z_get_next_timeout_expiry();
	_kernel.idle = ticks;

	if (pm_system_suspend(ticks) == PM_STATE_ACTIVE) {
		k_cpu_idle();
	}
#endif
}

下面只列出pm_system_suspend中与Tickless相关的代码

enum pm_state pm_system_suspend(int32_t ticks)
{
	...

	if (ticks != K_TICKS_FOREVER) {
		
		__ASSERT(z_power_state.min_residency_us >=
			z_power_state.exit_latency_us,
			"min_residency_us < exit_latency_us");

		//这里的ticks就是下一次中断的时间，因为从idle状态唤醒需要时间，所以设置到timer的时间要将唤醒的延迟时间扣除
		//z_set_timeout_expiry调用的就是sys_clock_set_timeout，设置下一次中断时间
		z_set_timeout_expiry(ticks -
		     k_us_to_ticks_ceil32(z_power_state.exit_latency_us), true);
	}

	...
}

Systick设置中断时间

在非Tickless的情况下systick每个tick产生一次中断，在Ticless下Zephyr对systick进行了设计，让其可以支持在指定Tick数后产生中断，这就是前文提到的sys_clock_set_timeout。
由于systick只有24bit,可计数clock为0xFFFFFF，一个tick有60000个硬件clock，因此systick一轮最多可以定时0xFFFFFF/60000 = 279 tick，在cortex_m_systick.c中取的是278

#define COUNTER_MAX 0x00ffffff
#define MAX_TICKS ((COUNTER_MAX / CYC_PER_TICK) - 1)

Systick到期时会自动加载LOAD寄存器进行下一轮计时产生中断sys_clock_isr

sys_clock_set_timeout

sys_clock_set_timeout有下面特性：

• idle情况，ticks为K_TICKS_FOREVER时，将停止systick timer
• 非idle情况下，当ticks大于MAX_TICKS时systick按MAX_TICKS定时

void sys_clock_set_timeout(int32_t ticks, bool idle)
{
	//Tickless下，无需Timer中断(K_TICKS_FOREVER)，且要进入idle时，会将SysTick Timer停止
	if (IS_ENABLED(CONFIG_TICKLESS_KERNEL) && idle && ticks == K_TICKS_FOREVER) {
		SysTick->CTRL &= ~SysTick_CTRL_ENABLE_Msk;
		last_load = TIMER_STOPPED;
		return;
	}

//SysTick按指定时间产生中断只在Tickless下有小
#if defined(CONFIG_TICKLESS_KERNEL)
	uint32_t delay;
	uint32_t val1, val2;
	uint32_t last_load_ = last_load;

	//systick只有24bit, 当定时的Tick超过24bit可计时，以最大24bit计时产生中断
	ticks = (ticks == K_TICKS_FOREVER) ? MAX_TICKS : ticks;
	ticks = CLAMP(ticks - 1, 0, (int32_t)MAX_TICKS);

	k_spinlock_key_t key = k_spin_lock(&lock);

	//从上一次中断到当前走过多少clock
	uint32_t pending = elapsed();

	val1 = SysTick->VAL;

	//计算总计走了多少个clock，cycle_count只有32bit，因此也会发生溢出循环
	cycle_count += pending;
	overflow_cyc = 0U;

	//从上一次中断到当前走了多少个tick，本来就是前面的pending，这样做是为了检查cycle_count溢出循环
	uint32_t unannounced = cycle_count - announced_cycles;

	
	if ((int32_t)unannounced < 0) {
		//如果发生了溢出cycle_count比announced_cycles小，设置定时器定时一小段时间，让announced_cycles也溢出循环，方便计算
		last_load = MIN_DELAY;
	} else {
		//因为每次中断都是按tick处理，而unannounced可能不是tick对齐的，所以这里加入unannounced进行对齐就算
		delay = ticks * CYC_PER_TICK;
		delay += unannounced;
		delay =
		 ((delay + CYC_PER_TICK - 1) / CYC_PER_TICK) * CYC_PER_TICK;
		delay -= unannounced;
		
		//delay时间不能比MIN_DELAY小
		delay = MAX(delay, MIN_DELAY);
		
		//delay时间不能比MAX_CYCLES大
		if (delay > MAX_CYCLES) {
			last_load = MAX_CYCLES;
		} else {
			last_load = delay;
		}
	}

	val2 = SysTick->VAL;

	//重新装载LOAD
	SysTick->LOAD = last_load - 1;
	SysTick->VAL = 0; /* resets timer to last_load */

	//在重新设置期间，systick任然在计数，要将这部分流逝的tick加到cycle_count总数中。
	if (val1 < val2) {
		cycle_count += (val1 + (last_load_ - val2));
	} else {
		cycle_count += (val1 - val2);
	}
	k_spin_unlock(&lock, key);
#endif
}

在没有调用sys_clock_set_timeout的情况下，每次中断时更新cycle_count和announced_cycles，每次中断后announced_cycles和cycle_count是相等的，在调用sys_clock_set_timeout后cycle_count被重新设置，以上流程如下图：

1. 进入函数时，记录下当前systick值为val1
2. 计算从最近一次中断到现在执行了多少个clock
3. 根据设置的tick数计算下一次中断的时间
4. 下一次中断的时间要做tick对齐得到delay
5. 获取当前systick值val2, val2-val1就是函数执行时间
6. 将delay设置到systick的load中开始计时
7. 将cycle_count更新

关于elapsed

elapsed用于获取最近一次设置LOAD寄存器到当前执行了的clock数量

static uint32_t elapsed(void)
{
	uint32_t val1 = SysTick->VAL;	/* A */
	uint32_t ctrl = SysTick->CTRL;	/* B */
	uint32_t val2 = SysTick->VAL;	/* C */

	//判断Timer在elapsed中到期，如果发生到期，需要将上一次的计时last_load加入到overflow_cyc中
	if ((ctrl & SysTick_CTRL_COUNTFLAG_Msk)
	    || (val1 < val2)) {
		overflow_cyc += last_load;

		/* We know there was a wrap, but we might not have
		 * seen it in CTRL, so clear it. */
		(void)SysTick->CTRL;
	}

	return (last_load - val2) + overflow_cyc;
}

执行elapsed有两种情况：

1. 在isr中执行，此时是timer到期，因此必定有COUNTFLAG标记
2. 在thread中执行，在执行elapsed前都会锁中断，执行过程中及时timer到期也不会进入isr，timer到期有几种情况：
   – 在A前到期：必定有COUNTFLAG标记
   – 在A和B之间到期：必定有COUNTFLAG标记，且val1<val2
   – 在B和C之间到期：没有COUNTFLAG标记，但val1val2，到期将在下一次执行时判断

硬件Timer定时长短的影响

通过sys_clock_set_timeout来设置期望的ticks后产生中断，从前文知道systick可以定时的最大长度为MAX_TICKS也就是MAX_TICKS=278tick。但如果需要的tickless的ticks数超过MAX_TICKS会怎么处理呢？
我们假设线程tickless要求的ticks为1000, 该情况下systick会以278tick最大定时长度定时产生中断，会每278tick产生一次tick中断，直到1000个tick执行完毕。

sys_clock_isr()
{
	if (TICKLESS) {
		dticks = (cycle_count - announced_cycles) / CYC_PER_TICK;
		announced_cycles += dticks * CYC_PER_TICK;
		
		//此处中断传入278tick
		sys_clock_announce(dticks);
	}
}

void sys_clock_announce(int32_t ticks)
{
	k_spinlock_key_t key = k_spin_lock(&timeout_lock);

	
	announce_remaining = ticks;
	//第一次announce_remaining为278
	//第二次announce_remaining为278
	//第三次announce_remaining为278
	//第四次announce_remaining为166

	//第一次时first()->dticks为1000, 不会进入循环
	//第二次时first()->dticks为722, 不会进入循环
	//第三次时first()->dticks为444, 不会进入循环
	//第四次时first()->dticks为166, 进入循环
	while (first() != NULL && first()->dticks <= announce_remaining) {
		struct _timeout *t = first();
		int dt = t->dticks;

		//达到Tickless要求
		curr_tick += dt;
		announce_remaining -= dt;
		t->dticks = 0;
		remove_timeout(t);

		k_spin_unlock(&timeout_lock, key);
		t->fn(t);
		key = k_spin_lock(&timeout_lock);
	}

	//第一次时first()->dticks 1000扣除278,剩余为722
	//第二次时first()->dticks 722扣除278,剩余为444
	//第三次时first()->dticks 444扣除278,剩余为166
	if (first() != NULL) {
		first()->dticks -= announce_remaining;
	}

	//更新系统累计执行的tick数
	curr_tick += announce_remaining;
	announce_remaining = 0;

	//第一次next_timeout()拿到的是722，被设置下去，大于278, 因此任然按278tick定时
	//第二次next_timeout()拿到的是444，被设置下去，大于278, 因此任然按278tick定时
	//第三次next_timeout()拿到的是166，小于于278, 按166tick定时
	sys_clock_set_timeout(next_timeout(), false);

	k_spin_unlock(&timeout_lock, key);
}

对于idle也类似，CPU每278个tick会从idle状态下唤醒，idle thread又重新设置systick，再进入idle。
由此可以看出当tick timer的定时长度比较小时，在Tickless过程中任然会产生中断有额外开销，而对于idle来说再期望的idle期间设备也会被多次唤醒。
为了解决该问题可以选择计数位数更多的硬件Timer或者降低硬件Timer的时钟，例如目前zephyr正在对rt系列的soc进行这方面的修改，将tick Timer换为32bit的GPT, 时钟将为32786Hz，最长的定时时间可以达到36小时。

时间片和Tickless

我们知道在没有Tickless的情况下，每个Tick都会产生中断，时间片会在每个中断中进行更新。但Tickless下只会在预定的tick到来后才会产生中断，此时可能已经超过了当前线程允许的时间片大小，因此在计算下一次tickless的tick时需要考虑当前时间片：

static int32_t next_timeout(void)
{
	struct _timeout *to = first();
	int32_t ticks_elapsed = elapsed();
	int32_t ret = to == NULL ? MAX_WAIT
		: CLAMP(to->dticks - ticks_elapsed, 0, MAX_WAIT);

#ifdef CONFIG_TIMESLICING
	//当有时间片存在时，且剩余的时间片小于下一次tickless的tick数，则以较小的slice_ticks作为timer定时设置
	if (_current_cpu->slice_ticks && _current_cpu->slice_ticks < ret) {
		ret = _current_cpu->slice_ticks;
	}
#endif
	return ret;
}

非时间片到引发调度时需要为下一个线程重设时间片, 设置时间片时会加上从上一次中断到现在经过的tick数

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);
	}
}

通过下图分析原因：

假设一个时间片4个tick

1. A线程执行3个tick后，在a时刻切换到线程B运行，使用z_reset_time_slice重设thread B的时间片
2. 由于重设时间片，原本再b要发生的时间片tickless中断不再发生
3. 在c处发生其它tickless中断，此时线程B只执行了3个tick还不到一个时间片
4. 在c处，送到sys_clock_announce的是dticks=6(包含了A执行了的3个时间片)，
5. 如果B第一次的_current_cpu->slice_ticks被设置为slice_time=4，那么此时z_time_slice会判断到dticks>_current_cpu->slice_ticks完成一个时间片，但实际线程B还没有执行完一个时间片

基于以上分析我们可知道：在时间片执行过程中切换线程后，下一次tick中断计算的tick数会包含上一个线程已经执行了的时间片，计算切换后线程运行的时间片应该扣出这一部分。在代码实现上为了简洁，就在current_cpu->slice_ticks中直接加上了这一部分来达到相同的效果。