多级时间轮实现框架
一. 多级时间轮实现框架
上图是5个时间轮级联的效果图。中间的大轮是工作轮，只有在它上的任务才会被执行；其他轮上的任务时间到后迁移到下一级轮上，他们最终都会迁移到工作轮上而被调度执行。
多级时间轮的原理也容易理解：就拿时钟做说明，秒针转动一圈分针转动一格；分针转动一圈时针转动一格；同理时间轮也是如此：当低级轮转动一圈时，高一级轮转动一格，同时会将高一级轮上的任务重新分配到低级轮上。从而实现了多级轮级联的效果。
1.1 多级时间轮对象
多级时间轮应该至少包括以下内容：
每一级时间轮对象轮子上指针的位置关于轮子上指针的位置有一个比较巧妙的办法：那就是位运算。比如定义一个无符号整型的数：
通过获取当前的系统时间便可以通过位操作转换为时间轮上的时间，通过与实际时间轮上的时间作比较，从而确定时间轮要前进调度的时间，进而操作对应时间轮槽位对应的任务。
为什么至少需要这两个成员呢？
定义多级时间轮，首先需要明确的便是级联的层数，也就是说需要确定有几个时间轮。轮子上指针位置，就是当前时间轮运行到的位置，它与真实时间的差便是后续时间轮需要调度执行，它们的差值是时间轮运作起来的驱动力。多级时间轮对象的定义
//实现5级时间轮 范围为0~ (2^8 * 2^6 * 2^6 * 2^6 *2^6)=2^32struct tvec_base{ unsigned long current_index; pthread_t thincrejiffies; pthread_t threadid; struct tvec_root tv1; /*第一个轮*/ struct tvec tv2; /*第二个轮*/ struct tvec tv3; /*第三个轮*/ struct tvec tv4; /*第四个轮*/ struct tvec tv5; /*第五个轮*/};1.2 时间轮对象
我们知道每一个轮子实际上都是一个哈希表，上面我们只是实例化了五个轮子的对象，但是五个轮子具体包含什么，有几个槽位等等没有明确(即struct tvec和struct tvec_root)。
#define tvn_bits 6#define tvr_bits 8#define tvn_size (1next = (ptr); (ptr)- >prev = (ptr); } while (0)static inline void__list_add(struct list_head *entry, struct list_head *prev, struct list_head *next){ next- >prev = entry; entry- >next = next; entry- >prev = prev; prev- >next = entry;}/** * insert a new element after the given list head. the new element does not * need to be initialised as empty list. * the list changes from: * head → some element → ... * to * head → new element → older element → ... * * example: * struct foo *newfoo = malloc(...); * list_add(&newfoo- >entry, &bar- >list_of_foos); * * @param entry the new element to prepend to the list. * @param head the existing list. */static inline voidlist_add(struct list_head *entry, struct list_head *head){ __list_add(entry, head, head- >next);}/** * append a new element to the end of the list given with this list head. * * the list changes from: * head → some element → ... → lastelement * to * head → some element → ... → lastelement → new element * * example: * struct foo *newfoo = malloc(...); * list_add_tail(&newfoo- >entry, &bar- >list_of_foos); * * @param entry the new element to prepend to the list. * @param head the existing list. */static inline voidlist_add_tail(struct list_head *entry, struct list_head *head){ __list_add(entry, head- >prev, head);}static inline void__list_del(struct list_head *prev, struct list_head *next){ next- >prev = prev; prev- >next = next;}/** * remove the element from the list it is in. using this function will reset * the pointers to/from this element so it is removed from the list. it does * not free the element itself or manipulate it otherwise. * * using list_del on a pure list head (like in the example at the top of * this file) will not remove the first element from * the list but rather reset the list as empty list. * * example: * list_del(&foo- >entry); * * @param entry the element to remove. */static inline voidlist_del(struct list_head *entry){ __list_del(entry- >prev, entry- >next);}static inline voidlist_del_init(struct list_head *entry){ __list_del(entry- >prev, entry- >next); init_list_head(entry);}static inline void list_move_tail(struct list_head *list, struct list_head *head){ __list_del(list- >prev, list- >next); list_add_tail(list, head);}/** * check if the list is empty. * * example: * list_empty(&bar- >list_of_foos); * * @return true if the list contains one or more elements or false otherwise. */static inline intlist_empty(struct list_head *head){ return head- >next == head;}/** * list_replace - replace old entry by new one * @old : the element to be replaced * @new : the new element to insert * * if @old was empty, it will be overwritten. */static inline void list_replace(struct list_head *old, struct list_head *new){ new- >next = old- >next; new- >next- >prev = new; new- >prev = old- >prev; new- >prev- >next = new;}/** * retrieve the first list entry for the given list pointer. * * example: * struct foo *first; * first = list_first_entry(&bar- >list_of_foos, struct foo, list_of_foos); * * @param ptr the list head * @param type data type of the list element to retrieve * @param member member name of the struct list_head field in the list element. * @return a pointer to the first list element. */#define list_first_entry(ptr, type, member) list_entry((ptr)- >next, type, member)static inline void list_replace_init(struct list_head *old, struct list_head *new){ list_replace(old, new); init_list_head(old);}/** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. */#define list_entry(ptr, type, member) ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)- >member)))/** * list_for_each - iterate over elements in a list * @pos: the &struct list_head to use as a loop counter. * @head: the head for your list. */#define list_for_each(pos, head) for (pos = (head)- >next; pos != (head); pos = pos- >next)/** * list_for_each_safe - iterate over elements in a list, but don't dereference * pos after the body is done (in case it is freed) * @pos: the &struct list_head to use as a loop counter. * @pnext: the &struct list_head to use as a pointer to the next item. * @head: the head for your list (not included in iteration). */#define list_for_each_safe(pos, pnext, head) for (pos = (head)- >next, pnext = pos- >next; pos != (head); pos = pnext, pnext = pos- >next)#ifdef __cplusplus}#endif#endif /* _blkid_list_h */这里面一般会用到一个重要实现：container_of, 它的原理这里不叙述
2.2 调试信息头文件: log.h
这个头文件实际上不是必须的，我只是用它来添加调试信息(代码中的errlog(), log()都是log.h中的宏函数)。它的效果是给打印的信息加上颜色，效果如下：
log.h的代码如下：
#ifndef _log_h_#define _log_h_#include #define col(x) �33[; #x m#define red col(31)#define green col(32)#define yellow col(33)#define blue col(34)#define magenta col(35)#define cyan col(36)#define white col(0)#define gray �33[0m#define errlog(fmt, arg...) do{ printf(red[#error: toeny sun:gray yellow %s:%d]:gray white fmt gray, __func__, __line__, ##arg);}while(0)#define log(fmt, arg...) do{ printf(white[#debug: toeny sun: gray yellow%s:%d]:gray white fmt gray, __func__, __line__, ##arg);}while(0)#endif2.3 时间轮代码: timewheel.c
/* *毫秒定时器 采用多级时间轮方式 借鉴linux内核中的实现 *支持的范围为1 ~ 2^32 毫秒(大约有49天) *若设置的定时器超过最大值 则按最大值设置定时器 **/#include #include #include #include #include #include #include list.h#include log.h #define tvn_bits 6#define tvr_bits 8#define tvn_size (1<2.4 编译运行
toney@ubantu:/mnt/hgfs/em嵌入式学习记录/4. timerwheel/2. 多级时间轮$ lsa.out list.h log.h mutitimewheel.ctoney@ubantu:/mnt/hgfs/em嵌入式学习记录/4. timerwheel/2. 多级时间轮$ gcc mutitimewheel.c -lpthreadtoney@ubantu:/mnt/hgfs/em嵌入式学习记录/4. timerwheel/2. 多级时间轮$ ./a.out [#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100从结果可以看出：如果添加的定时任务是比较耗时的操作，那么后续的任务也会被阻塞，可能一直到超时，甚至一直阻塞下去，这个取决于当前任务是否耗时。这个理论上是绝不能接受的：一个任务不应该也不能去影响其他的任务吧。但是目前没有对此问题进行改进和完善，以后有机会再继续完善吧。
风速仪如何选型
LoRa组网协议、能力和多点与单点工作的区别
基于Zynq的图形生成电路的软硬件设计
NANO SIM卡座是什么？
警惕“沉默性缺氧”，米尔T507-H核心板的监护仪方案
多级时间轮实现框架
2020年Q1季度我国能源需求下降，工业能源消费量同比下降4.3%
贴片电感和贴片电容的区别
印制电路板都有哪些标准
虹科案例 | Hitachi Zaxis 470 挖土机发动机故障动力损失诊断
高通骁龙835又一部新机诺基亚9跑分曝光 第一坐稳要起飞！
发改委：加快5G、一体化数据中心等新基建项目建设
蓝牙模块选择，电子工程师需要考虑哪些因素？
新技术和趋势推动工业PC市场向前发展
激光雷达传感技术的工作原理及其技术特点的分析
GPU只能整块购买吗，腾讯云GN7实例告诉你答案
高通 CES 发布会汇总：除了 5G 智能手机，高通用大篇幅介绍人和车未来的技术
ICO如何才会受到新加坡证券法的监管
“感测”并“看见”我们环境中的重要参数
氢能与燃料电池产业化难，水氢产业化之路另辟蹊径
上图是5个时间轮级联的效果图。中间的大轮是工作轮，只有在它上的任务才会被执行；其他轮上的任务时间到后迁移到下一级轮上，他们最终都会迁移到工作轮上而被调度执行。
多级时间轮的原理也容易理解：就拿时钟做说明，秒针转动一圈分针转动一格；分针转动一圈时针转动一格；同理时间轮也是如此：当低级轮转动一圈时，高一级轮转动一格，同时会将高一级轮上的任务重新分配到低级轮上。从而实现了多级轮级联的效果。
1.1 多级时间轮对象
多级时间轮应该至少包括以下内容：
每一级时间轮对象轮子上指针的位置关于轮子上指针的位置有一个比较巧妙的办法：那就是位运算。比如定义一个无符号整型的数：
通过获取当前的系统时间便可以通过位操作转换为时间轮上的时间，通过与实际时间轮上的时间作比较，从而确定时间轮要前进调度的时间，进而操作对应时间轮槽位对应的任务。
为什么至少需要这两个成员呢？
定义多级时间轮，首先需要明确的便是级联的层数，也就是说需要确定有几个时间轮。轮子上指针位置，就是当前时间轮运行到的位置，它与真实时间的差便是后续时间轮需要调度执行，它们的差值是时间轮运作起来的驱动力。多级时间轮对象的定义
//实现5级时间轮 范围为0~ (2^8 * 2^6 * 2^6 * 2^6 *2^6)=2^32struct tvec_base{ unsigned long current_index; pthread_t thincrejiffies; pthread_t threadid; struct tvec_root tv1; /*第一个轮*/ struct tvec tv2; /*第二个轮*/ struct tvec tv3; /*第三个轮*/ struct tvec tv4; /*第四个轮*/ struct tvec tv5; /*第五个轮*/};1.2 时间轮对象
我们知道每一个轮子实际上都是一个哈希表，上面我们只是实例化了五个轮子的对象，但是五个轮子具体包含什么，有几个槽位等等没有明确(即struct tvec和struct tvec_root)。
#define tvn_bits 6#define tvr_bits 8#define tvn_size (1next = (ptr); (ptr)- >prev = (ptr); } while (0)static inline void__list_add(struct list_head *entry, struct list_head *prev, struct list_head *next){ next- >prev = entry; entry- >next = next; entry- >prev = prev; prev- >next = entry;}/** * insert a new element after the given list head. the new element does not * need to be initialised as empty list. * the list changes from: * head → some element → ... * to * head → new element → older element → ... * * example: * struct foo *newfoo = malloc(...); * list_add(&newfoo- >entry, &bar- >list_of_foos); * * @param entry the new element to prepend to the list. * @param head the existing list. */static inline voidlist_add(struct list_head *entry, struct list_head *head){ __list_add(entry, head, head- >next);}/** * append a new element to the end of the list given with this list head. * * the list changes from: * head → some element → ... → lastelement * to * head → some element → ... → lastelement → new element * * example: * struct foo *newfoo = malloc(...); * list_add_tail(&newfoo- >entry, &bar- >list_of_foos); * * @param entry the new element to prepend to the list. * @param head the existing list. */static inline voidlist_add_tail(struct list_head *entry, struct list_head *head){ __list_add(entry, head- >prev, head);}static inline void__list_del(struct list_head *prev, struct list_head *next){ next- >prev = prev; prev- >next = next;}/** * remove the element from the list it is in. using this function will reset * the pointers to/from this element so it is removed from the list. it does * not free the element itself or manipulate it otherwise. * * using list_del on a pure list head (like in the example at the top of * this file) will not remove the first element from * the list but rather reset the list as empty list. * * example: * list_del(&foo- >entry); * * @param entry the element to remove. */static inline voidlist_del(struct list_head *entry){ __list_del(entry- >prev, entry- >next);}static inline voidlist_del_init(struct list_head *entry){ __list_del(entry- >prev, entry- >next); init_list_head(entry);}static inline void list_move_tail(struct list_head *list, struct list_head *head){ __list_del(list- >prev, list- >next); list_add_tail(list, head);}/** * check if the list is empty. * * example: * list_empty(&bar- >list_of_foos); * * @return true if the list contains one or more elements or false otherwise. */static inline intlist_empty(struct list_head *head){ return head- >next == head;}/** * list_replace - replace old entry by new one * @old : the element to be replaced * @new : the new element to insert * * if @old was empty, it will be overwritten. */static inline void list_replace(struct list_head *old, struct list_head *new){ new- >next = old- >next; new- >next- >prev = new; new- >prev = old- >prev; new- >prev- >next = new;}/** * retrieve the first list entry for the given list pointer. * * example: * struct foo *first; * first = list_first_entry(&bar- >list_of_foos, struct foo, list_of_foos); * * @param ptr the list head * @param type data type of the list element to retrieve * @param member member name of the struct list_head field in the list element. * @return a pointer to the first list element. */#define list_first_entry(ptr, type, member) list_entry((ptr)- >next, type, member)static inline void list_replace_init(struct list_head *old, struct list_head *new){ list_replace(old, new); init_list_head(old);}/** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. */#define list_entry(ptr, type, member) ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)- >member)))/** * list_for_each - iterate over elements in a list * @pos: the &struct list_head to use as a loop counter. * @head: the head for your list. */#define list_for_each(pos, head) for (pos = (head)- >next; pos != (head); pos = pos- >next)/** * list_for_each_safe - iterate over elements in a list, but don't dereference * pos after the body is done (in case it is freed) * @pos: the &struct list_head to use as a loop counter. * @pnext: the &struct list_head to use as a pointer to the next item. * @head: the head for your list (not included in iteration). */#define list_for_each_safe(pos, pnext, head) for (pos = (head)- >next, pnext = pos- >next; pos != (head); pos = pnext, pnext = pos- >next)#ifdef __cplusplus}#endif#endif /* _blkid_list_h */这里面一般会用到一个重要实现：container_of, 它的原理这里不叙述
2.2 调试信息头文件: log.h
这个头文件实际上不是必须的，我只是用它来添加调试信息(代码中的errlog(), log()都是log.h中的宏函数)。它的效果是给打印的信息加上颜色，效果如下：
log.h的代码如下：
#ifndef _log_h_#define _log_h_#include #define col(x) �33[; #x m#define red col(31)#define green col(32)#define yellow col(33)#define blue col(34)#define magenta col(35)#define cyan col(36)#define white col(0)#define gray �33[0m#define errlog(fmt, arg...) do{ printf(red[#error: toeny sun:gray yellow %s:%d]:gray white fmt gray, __func__, __line__, ##arg);}while(0)#define log(fmt, arg...) do{ printf(white[#debug: toeny sun: gray yellow%s:%d]:gray white fmt gray, __func__, __line__, ##arg);}while(0)#endif2.3 时间轮代码: timewheel.c
/* *毫秒定时器 采用多级时间轮方式 借鉴linux内核中的实现 *支持的范围为1 ~ 2^32 毫秒(大约有49天) *若设置的定时器超过最大值 则按最大值设置定时器 **/#include #include #include #include #include #include #include list.h#include log.h #define tvn_bits 6#define tvr_bits 8#define tvn_size (1<2.4 编译运行
toney@ubantu:/mnt/hgfs/em嵌入式学习记录/4. timerwheel/2. 多级时间轮$ lsa.out list.h log.h mutitimewheel.ctoney@ubantu:/mnt/hgfs/em嵌入式学习记录/4. timerwheel/2. 多级时间轮$ gcc mutitimewheel.c -lpthreadtoney@ubantu:/mnt/hgfs/em嵌入式学习记录/4. timerwheel/2. 多级时间轮$ ./a.out [#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100[#debug: toeny sun: mytimer:370]:100从结果可以看出：如果添加的定时任务是比较耗时的操作，那么后续的任务也会被阻塞，可能一直到超时，甚至一直阻塞下去，这个取决于当前任务是否耗时。这个理论上是绝不能接受的：一个任务不应该也不能去影响其他的任务吧。但是目前没有对此问题进行改进和完善，以后有机会再继续完善吧。
风速仪如何选型
LoRa组网协议、能力和多点与单点工作的区别
基于Zynq的图形生成电路的软硬件设计
NANO SIM卡座是什么？
警惕“沉默性缺氧”，米尔T507-H核心板的监护仪方案
多级时间轮实现框架
2020年Q1季度我国能源需求下降，工业能源消费量同比下降4.3%
贴片电感和贴片电容的区别
印制电路板都有哪些标准
虹科案例 | Hitachi Zaxis 470 挖土机发动机故障动力损失诊断
高通骁龙835又一部新机诺基亚9跑分曝光 第一坐稳要起飞！
发改委：加快5G、一体化数据中心等新基建项目建设
蓝牙模块选择，电子工程师需要考虑哪些因素？
新技术和趋势推动工业PC市场向前发展
激光雷达传感技术的工作原理及其技术特点的分析
GPU只能整块购买吗，腾讯云GN7实例告诉你答案
高通 CES 发布会汇总：除了 5G 智能手机，高通用大篇幅介绍人和车未来的技术
ICO如何才会受到新加坡证券法的监管
“感测”并“看见”我们环境中的重要参数
氢能与燃料电池产业化难，水氢产业化之路另辟蹊径