前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >从零手写操作系统之RVOS软件定时器实现-08

从零手写操作系统之RVOS软件定时器实现-08

作者头像
大忽悠爱学习
发布2023-10-11 08:39:34
2280
发布2023-10-11 08:39:34
举报
文章被收录于专栏:c++与qt学习
从零手写操作系统之RVOS软件定时器实现-08

本系列参考: 学习开发一个RISC-V上的操作系统 - 汪辰 - 2021春 整理而来,主要作为xv6操作系统学习的一个前置基础。

RVOS是本课程基于RISC-V搭建的简易操作系统名称。

课程代码和环境搭建教程参考github仓库: https://github.com/plctlab/riscv-operating-system-mooc/blob/main/howto-run-with-ubuntu1804_zh.md

前置知识:


定时器分类

  • 硬件定时器:芯片本身提供的定时器,一般由外部晶振提供,提供寄存器设置超时时间,并采用外部中断 方式通知 CPU,参考硬件定时器一节的介绍。优点是精度高,但定时器个数受硬件芯片的设计限制。
  • 软件定时器:操作系统中基于硬件定时器提供的功能,采用软件方式实现。扩展了硬件定时器的限制,可以提供数目更多(几乎不受限制)的定时器;缺点是精度较低,必须是 Tick 的整数倍。

软件定时器的分类

在这里插入图片描述
在这里插入图片描述

本节采用超时函数运行在中断上下文环境中,因为比较简单。

软件定时器设计与实现

code/os/10-swtimer/os.h

代码语言:javascript
复制
/* software timer */
struct timer {
	//定时器超时后,任务执行器函数的入口地址
	void (*func)(void *arg);
	//参数
	void *arg;
	//超时计数器
	uint32_t timeout_tick;
};
//创建一个软件定时器任务 --- 任务执行器函数入口地址,函数实参,超时时间
extern struct timer *timer_create(void (*handler)(void *arg), void *arg, uint32_t timeout);
//删除一个软件定时器任务
extern void timer_delete(struct timer *timer);

code/os/10-swtimer/timer.c

  • timer.c文件是硬件定时器小节新增的,用于实现对硬件定时器模块支持
代码语言:javascript
复制
//最多支持同时存在10个软件定时器
#define MAX_TIMER 10
//采用数组存放软件定时器列表
static struct timer timer_list[MAX_TIMER];

code/os/10-swtimer/timer.c

代码语言:javascript
复制
//在原有的硬件定时器初始化逻辑之上,增加对软件定时器模块初始化支持
void timer_init()
{
    //初始化所有软件定时器任务
	struct timer *t = &(timer_list[0]);
	for (int i = 0; i < MAX_TIMER; i++) {
	    //将每个任务的func和arg清空
		t->func = NULL; /* use .func to flag if the item is used */
		t->arg = NULL;
		t++;
	}
    
    //--------------------下面是硬件定时器模块的初始化逻辑---------------------------------

	/*
	 * On reset, mtime is cleared to zero, but the mtimecmp registers 
	 * are not reset. So we have to init the mtimecmp manually.
	 */
	//硬件定时器模块初始化---传入interval间隔大约为1s
	timer_load(TIMER_INTERVAL);

	/* enable machine-mode timer interrupts. */
	//设置mie寄存器的MTIE位为1,开启时钟中断
	w_mie(r_mie() | MIE_MTIE);
}

/* load timer interval(in ticks) for next timer interrupt.*/
void timer_load(int interval)
{
	/* each CPU has a separate source of timer interrupts. */
	//获取当前hartId
	int id = r_mhartid();
	//设置mtimecmp寄存器的值为mtime寄存器的值+interval
	*(uint64_t*)CLINT_MTIMECMP(id) = *(uint64_t*)CLINT_MTIME + interval;
}

code/os/10-swtimer/timer.c

代码语言:javascript
复制
//创建软件定时器任务
struct timer *timer_create(void (*handler)(void *arg), void *arg, uint32_t timeout)
{
	/* TBD: params should be checked more, but now we just simplify this */
	if (NULL == handler || 0 == timeout) {
		return NULL;
	}

	/* use lock to protect the shared timer_list between multiple tasks */
	//使用锁来保护对共享软件定时器任务列表的操作---此处采用关中断实现
	spin_lock();
    //从软件定时器数组中寻找到第一个空位
	struct timer *t = &(timer_list[0]);
	for (int i = 0; i < MAX_TIMER; i++) {
		if (NULL == t->func) {
			break;
		}
		t++;
	}
	//如果没有剩余空位,那么返回NULL,表示软件定时器数组满了,创建失败
	if (NULL != t->func) {
		spin_unlock();
		return NULL;
	}
    //初始化软件定时任务
	t->func = handler;
	t->arg = arg;
	//_tick变量,记录系统从启动开始到现在为止,产生的时钟中断次数
	//_tick + timeout表示,从现在开始的第timeout次时钟中断后,软件定时器任务到期
	//由于本课程中默认设置时钟中断间隔为1s,所以等同于说: 软件定时器任务timeout秒后被调用执行
	t->timeout_tick = _tick + timeout;
    //释放锁
	spin_unlock();
	return t;
}

//--------------------下面是硬件定时器小节添加的逻辑---------------------------------

//用于记录
static uint32_t _tick = 0;

//发生定时器中断时,会调用该处理函数
void timer_handler() {
    //不断累加,记录系统从启动开始到现在为止,产生的时钟中断次数
	_tick++;
	printf("tick: %d\n", _tick);
	//本节在定时器中断处理函数中新增对软件定时器任务到期检查
	timer_check();
	//重置下一次时钟中断发生时间 -- 1s发生一次
	timer_load(TIMER_INTERVAL);
	//进行任务调度
	schedule();
}

code/os/10-swtimer/timer.c

代码语言:javascript
复制
void timer_delete(struct timer *timer)
{
    //使用锁来保护对共享软件定时器任务列表的操作---此处采用关中断实现
	spin_lock();
	struct timer *t = &(timer_list[0]);
	for (int i = 0; i < MAX_TIMER; i++) {
	    //定位到目标软件定时器,然后清空func和arg即可
		if (t == timer) {
			t->func = NULL;
			t->arg = NULL;
			break;
		}
		t++;
	}
    //释放锁
	spin_unlock();
}

软件定时器调用流程

在这里插入图片描述
在这里插入图片描述
  1. 时钟中断发生,调用timer_handler函数
  2. timer_handler函数中首先增加tick数,然后判断是否存在到期的软件定时器
  3. 如果存在,则直接在中断上下文环境中执行我们的软件定时器任务
代码语言:javascript
复制
/* this routine should be called in interrupt context (interrupt is disabled) */
static inline void timer_check()
{
	struct timer *t = &(timer_list[0]);
	for (int i = 0; i < MAX_TIMER; i++) {
		if (NULL != t->func) {
		    //判断是否有软件定时器任务到期
			if (_tick >= t->timeout_tick) {
				//发现一个到期的软件定时器任务,触发任务执行
				t->func(t->arg);

				/* once time, just delete it after timeout */
				//只会触发一次,触发后,就删除当前定时器任务
				t->func = NULL;
				t->arg = NULL;
                //跳出循环,一次时钟中断,最多执行一个到期的定时器任务
				break;
			}
		}
		t++;
	}
}

timer_check函数处理思路很简单,如下图所示:

在这里插入图片描述
在这里插入图片描述

增加对周期性定时任务支持

code/os/10-swtimer/timer.c

  • timer结构体中新增两个属性,用于记录当前任务是否为周期性任务和周期性任务触发间隔
代码语言:javascript
复制
/* software timer */
struct timer {
	void (*func)(void *arg);
	void *arg;
	//是否为周期性任务
	uint32_t period;
	//周期性触发间隔
	uint32_t period_time;
	//下一次触发时机
	uint32_t timeout_tick;
};
  • 定时任务创建:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
  • timer_check函数中增加对周期性任务和一次性任务的区分处理
代码语言:javascript
复制
/* this routine should be called in interrupt context (interrupt is disabled) */
static inline void timer_check()
{
	struct timer *t = &(timer_list[0]);
	for (int i = 0; i < MAX_TIMER; i++) {
		if (NULL != t->func) {
			if (_tick >= t->timeout_tick) {
				t->func(t->arg);
                //非周期性任务,执行完直接删除
				if(t->period<=0){
                    /* once time, just delete it after timeout */
				    t->func = NULL;
				    t->arg = NULL;
					t->period=0;
					t->period_time=0;
				}else{
					//更新周期性任务下一次触发的时间
					t->timeout_tick=_tick+t->period_time;
				}
				break;
			}
		}
		t++;
	}
}

测试

user.c文件中,我们在任务0中创建定时器任务,然后测试其执行效果:

代码语言:javascript
复制
#include "os.h"
#define DELAY 4000

void timer_func(void *arg)
{
	if (NULL == arg)
		return;
	printf("%s\n",arg);
}

void user_task0(void)
{
	uart_puts("Task 0: Created!\n");
    //创建一个周期性任务
	struct timer *t1 = timer_create(timer_func,"task 1", 3,1);
	if (NULL == t1) {
		printf("timer_create() failed!\n");
	}
	//下面创建两个一次性定时任务
	struct timer *t2 = timer_create(timer_func, "task 2", 5,0);
	if (NULL == t2) {
		printf("timer_create() failed!\n");
	}
	struct timer *t3 = timer_create(timer_func, "task 3", 7,0);
	if (NULL == t3) {
		printf("timer_create() failed!\n");
	}
	while (1) {
		uart_puts("Task 0: Running... \n");
		task_delay(DELAY);
	}
}

void user_task1(void)
{
	uart_puts("Task 1: Created!\n");
	while (1) {
		uart_puts("Task 1: Running... \n");
		task_delay(DELAY);
	}
}

/* NOTICE: DON'T LOOP INFINITELY IN main() */
void os_main(void)
{
	task_create(user_task0);
	task_create(user_task1);
}

期望效果是任务1,在tick=3的倍数时,周期性执行;任务2在tick=5时,执行一次,任务3在tick=7时执行一次:

在这里插入图片描述
在这里插入图片描述

优化点

我们目前使用数组结构来管理我们的软件定时器列表,在软件定时器任务的创建,删除,查找过程中都涉及到大量遍历操作,虽然实现简单,但是效率很低。

如果要进行优化,有两个简单的思路:

  • 定时器按照超时时间排序,这样可以加速中断处理上下文判断是否存在到期的软件定时器任务
  • 链表方式对定时器实现管理,更加灵活
在这里插入图片描述
在这里插入图片描述

但是,光是单链表还不足以满足我们的需求,因为单链表的遍历效率同样很低。

可以考虑跳跃表(SkipList),通过多级链表形成类似B+ Tree的索引结构,加速CRUD的过程:

在这里插入图片描述
在这里插入图片描述

跳跃表实现相较于红黑树而言,实现更简单,并且查询复杂度也是O(logn),大家可以尝试在本节代码基础上,采用跳跃表作为软件定时器列表底层实现。

还有一个优化点就是大家可以尝试将定时任务执行挪动到任务执行上下文中去,可以考虑每个定时任务创建一个进程执行,或者采用生产者消费者模型:

  • 设置一个队列,当timer_check函数检查到有到期的定时任务时,就丢到队列中去
  • 然后可以是单进程或者多进程组成进程池,在队列中有任务中时,就唤醒生产者进行消费
  • 没有任务时,就挂起当前进程
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-10-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 从零手写操作系统之RVOS软件定时器实现-08
  • 定时器分类
  • 软件定时器的分类
  • 软件定时器设计与实现
    • 软件定时器调用流程
      • 增加对周期性定时任务支持
        • 测试
          • 优化点
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档