基于链表的时间片程序

Sun_Fly · 发表于 2017-5-11 15:47:58

本帖最后由 Sun_Fly 于 2017-5-11 15:51 编辑

链表+时间片。实现了轮转执行多个任务。自己写的代码，分享给需要的人看。其中参考了本论坛大虾@FreeRTOS[mw_shl_code=c,true]extern volatile uint32_t g_tick_tick ;
typedef struct Task_Struct{
      uint16_t id;
      uint32_t NeedTime;
      uint16_t LineName;
      uint32_t Get_Tick;
      void (*func) (void);
      struct Task_Struct * p_next;
}Task_Struct;
Task_Struct head;
Task_Struct *p_head = &head;

void task_add(uint16_t id,uint32_t NeedTime,TaskFunc_t func) {
      Task_Struct *p_Task_Struct = (Task_Struct *)malloc(sizeof(Task_Struct));
      Task_Struct *p_temp = p_head;
      p_Task_Struct->id = id;
      p_Task_Struct->NeedTime = NeedTime;
      p_Task_Struct->LineName = 0;
      p_Task_Struct->func = func;
      p_Task_Struct->p_next = NULL;
      while (p_temp ->p_next) {
            p_temp = p_temp->p_next;
      }
      p_temp->p_next = p_Task_Struct;//链表最后加入了新节点
}

void task_execute(Task_Struct* p_temp, uint32_t tick){
//       printf("%d\n",p_temp->LineName);
      switch(p_temp->LineName){
            case 0:
                     while(1){
                              do{
                                    p_temp->Get_Tick = tick;
                                    p_temp->LineName = 1; case 1:
                                    if(g_tick_tick - p_temp->Get_Tick > p_temp->NeedTime){
                                             p_temp->func();
                                             p_temp->LineName = 0;
                                             break;
                                    }
                                    return;
                              }while(0);
                     }
      }

}

void task_run(void) {
      Task_Struct *p_temp = p_head;
      while (p_temp->p_next) {
            task_execute(p_temp->p_next,g_tick_tick);
            p_temp = p_temp->p_next;
      }
}[/mw_shl_code]
在主函数中用task_add(id,多久执行一次，执行的函数),添加需要执行的任务，有几个任务就添加几个任务，while(1)中调用task_run

ianhom · 发表于 2017-5-15 12:55:59

本帖最后由 ianhom 于 2017-5-15 12:59 编辑

我的想法就是在链表加入新节点时，在节点内容初始化部分就可以更新p_Task_Struct->Get_Tick，新节点加入那刻就可以计时，而在func函数被更新后，更新p_Task_Struct->Get_Tick的值。我稍微改写了一下代码，这样比我文字描述更清楚点。

[mw_shl_code=c,true]
extern volatile uint32_t g_tick_tick ;
typedef struct Task_Struct
{
struct Task_Struct * p_next;
void (*func) (void);
uint32_t Get_Tick;
uint32_t NeedTime;
uint16_t id;                               /* 移除了linenumber */
}Task_Struct;
Task_Struct head;
Task_Struct *p_head = &head;

void task_add(uint16_t id,uint32_t NeedTime,TaskFunc_t func)
{
Task_Struct *p_Task_Struct = (Task_Struct *)malloc(sizeof(Task_Struct));
Task_Struct *p_temp = p_head;
p_Task_Struct->id = id;
p_Task_Struct->NeedTime = NeedTime;
p_Task_Struct->Get_Tick = g_tick_tick;       /* 创建新节点的时候就记录下启动时间点 */
p_Task_Struct->func = func;
p_Task_Struct->p_next = NULL;
while (p_temp->p_next)
{
      p_temp = p_temp->p_next;
}
p_temp->p_next = p_Task_Struct;//链表最后加入了新节点
}

void task_execute(Task_Struct* p_temp)    /* 移除了tick入参 */
{
if(g_tick_tick - p_temp->Get_Tick > p_temp->NeedTime)
{
      p_temp->func();
      p_temp->Get_Tick = g_tick_tick;       /*func执行完后更新启动时间点 */
}
return;
}

void task_run(void)
{
Task_Struct *p_temp = p_head;
while (p_temp->p_next)
{
      task_execute(p_temp->p_next); /* 若task_execute在其他地方没有调用，可以考虑直接使用task_execute函数内容替换函数调用 */
      p_temp = p_temp->p_next;
}
}
[/mw_shl_code]

关于“最小剩余时间”的写法很多，我之前试写了一个小的os，里面的时间管理部分，欢迎一起讨论

https://github.com/ianhom/MOE/blob/master/Core/MOE_Timer.c
https://github.com/ianhom/MOE/blob/master/Core/MOE_Timer.h

ianhom · 发表于 2017-5-11 16:18:02

赞！感谢分享！

ianhom · 发表于 2017-5-11 16:23:28

一点小小的建议
重新调整一下struct Task_Struct结构的成员顺序，32位平台下可以有优化结构体size

Sun_Fly · 发表于 2017-5-11 16:29:58

ianhom 发表于 2017-5-11 16:23
一点小小的建议
重新调整一下struct Task_Struct结构的成员顺序，32位平台下可以有优化结构体size

嗯，谢谢指导，结构体有对齐和补齐，我写代码的时候就是想到哪个成员添加哪个成员，没来得及优化，

翱翔云端的鸟 · 发表于 2017-5-11 16:55:15

赞！感谢分享 mark下！有时间我也来学习下

shikihane · 发表于 2017-5-11 16:58:19

带抢占不

Sun_Fly · 发表于 2017-5-11 17:21:37

shikihane 发表于 2017-5-11 16:58
带抢占不

NeedTime，这个成员，需要的时间时间短的肯定先运行。

Sun_Fly · 发表于 2017-5-12 15:17:27

yklstudent 发表于 2017-5-12 14:53
看了楼主的链表+时间片程序架构很有感触，在楼主的基础上改良了一下，希望跟客户多交流学习
void sTaskLis ...

pvTaskPoint，确实需要一个这样的中间变量，感谢分享，你链表指针用的比我好多了。

Sun_Fly · 发表于 2017-5-12 17:03:42

yklstudent 发表于 2017-5-12 15:37
相互学习，这个代码应该可以继续完善和优化。。。

嗯，我也就是写了个开头，期待大神的完善。

lison0103 · 发表于 2017-5-12 17:11:16

mark!谢谢分享~

ianhom · 发表于 2017-5-12 23:55:14

学习一下，感觉蛮有意思的
有个问题想请教一下，
在函数task_add中为什么不直接更新Get_Tick的值呢，这样在task_execute中就不需要p_temp->LineName的case0和case1，而在计时结束运行完func后，再次更新Get_Tick，这样task_execute函数会简短点，Task_Struct结构体中也不需要p_temp->LineName。目前看来LineName的作用就是区分两个状态：case 0--需要更新“计时启动时间点”；case 1--“计时启动时间点”已经更新；而这两种状态在代码中其他地方也有提现：case0:需要更新“计时启动时间点”有两个时机，一个是初始化时在add task的时候，还有一个在func被执行之后需要重新更新。在这两个时机或位置处理case0的工作，其余的时间都是case1的状态。
可能我还没有参透楼主原设计思路，或有其他妙用之处，还望楼主讲解。

PS. if(g_tick_tick - p_temp->Get_Tick > p_temp->NeedTime)这样的比较其实空跑了很多次，需要这样不停的轮寻检查每个节点，可以考虑一下“最小剩余时间”的概念，当前所有节点中距离计时结束最短的剩余时间（要注意这个时间的更新问题）记录下来，那在这个时间到达之前，可以不用轮训所有节点，可以利用这些时间做低功耗休眠。

Sun_Fly · 发表于 2017-5-15 10:18:19

我是这样设计的，task_add 这个函数是的功能是增加新的节点，也就是给这个链表加入一个成员，参数固定即可。task_execute是链表成员函数。
你说的最小剩余时间这个有听说过，但是没用过，我觉得可以，能贴出来说一下吗？

Sun_Fly · 发表于 2017-5-15 10:18:31

ianhom 发表于 2017-5-12 23:55
学习一下，感觉蛮有意思的
有个问题想请教一下，
在函数task_add中为什么不直接更新Get_Tick的值呢，这样 ...

我是这样设计的，task_add 这个函数是的功能是增加新的节点，也就是给这个链表加入一个成员，参数固定即可。task_execute是链表成员函数。
你说的最小剩余时间这个有听说过，但是没用过，我觉得可以，能贴出来说一下吗？

loudianxin · 发表于 2017-5-17 08:54:15

标记学习下

hojo · 发表于 2017-5-26 12:19:15

mark一下，以后来学习

liuchang · 发表于 2017-5-26 18:01:17

本帖最后由 liuchang 于 2017-5-26 19:53 编辑

ianhom 发表于 2017-5-15 12:55
我的想法就是在链表加入新节点时，在节点内容初始化部分就可以更新p_Task_Struct->Get_Tick，新节点加入那 ...

每次看过你的帖子,我必定会认真阅读,经常聆听大神指导,无比感激......

小弟在大神的代码基础之上,稍加修改,如有问题,还请大神多多指教...谢谢...

1>sys_ticks必须为uint64_t类型(额,我的sys_ticks++是放在一个10ms的中断里,这样的话,sys_ticks溢出时间为497天,也就一年多时间而已).

2>新增一个删除任务节点函数(额,既然有增加节点,毫无理由应当有删除节点才对)

3>我将链表按照时间进行排序,比如有3个定时任务,1s,5s,3s,那么将按照1s,3s,5s进行排序(我觉得这样会提高链表的遍历效率,并且这个排序工作是在初始化时完成的,不会带来CPU额外开销).
4>回调函数增加回调形参,这还是有必要的.

5>我将struct结构体中成员id给删除了,说实话,这个成员没有啥用...

6>我将数据结构名称和函数名称给统一命名,我觉得这样会更好看...

代码放在下一楼

liuchang · 发表于 2017-5-26 18:03:43

本帖最后由 liuchang 于 2017-5-26 18:04 编辑

[mw_shl_code=c,true]#include <stm32f10x.h>

typedef void (*soft_timer_cb_fn)(void *soft_timer_fn_arg);

typedef enum soft_timer_result
{
      SOFT_TIMER_OK = 0,
      SOFT_TIMER_MEM,
      SOFT_TIMER_PARA,
      SOFT_TIMER_OTHER
}soft_timer_result_t;

typedef struct soft_timer
{
      uint32_t time;
      uint64_t tick;
      soft_timer_cb_fn soft_timer_cb;
      void * soft_timer_arg;
      struct soft_timer * next;
}soft_timer_t;

soft_timer_result_t soft_timer_task_add(uint32_t time, soft_timer_cb_fn soft_timer_cb, void * soft_timer_arg);
soft_timer_result_t soft_timer_task_delete(uint32_t time);
soft_timer_result_t soft_timer_task_exec(void);

extern uint64_t sys_ticks;

#endif[/mw_shl_code]

[mw_shl_code=c,true]#include <stdlib.h>
#include "soft_timer.h"

uint64_t sys_ticks;
soft_timer_t * soft_timer_hdr;

soft_timer_result_t soft_timer_task_add(uint32_t time, soft_timer_cb_fn soft_timer_cb, void * soft_timer_arg)
{
      soft_timer_t * cur = NULL;
      soft_timer_t * tmp = NULL;
      soft_timer_t ** link = &soft_timer_hdr;

      while ((cur=*link)!=NULL && (cur->time<time))
      {
            link = &(cur->next);
      }

      tmp = (soft_timer_t *)malloc(sizeof(soft_timer_t));
      if (tmp == NULL) return SOFT_TIMER_MEM;

      tmp->next = cur;
      *link = tmp;

      tmp->time = time;
      tmp->tick = sys_ticks;
      tmp->soft_timer_cb = soft_timer_cb;
      tmp->soft_timer_arg = soft_timer_arg;

      return SOFT_TIMER_OK;
}

soft_timer_result_t soft_timer_task_delete(uint32_t time)
{
      soft_timer_t * cur = NULL;
      soft_timer_t ** link = &soft_timer_hdr;

      while ((cur=*link)!=NULL && (cur->time!=time))
      {
            link = &(cur->next);
      }

      if (cur->time == time)
      {
            *link = cur->next;
            free(cur);
      }

      return SOFT_TIMER_OK;
}

soft_timer_result_t soft_timer_task_exec(void)
{
      soft_timer_t * cur = soft_timer_hdr;

      for (; cur; cur=cur->next)
      {
            if (sys_ticks - cur->tick >= cur->time)
            {
                     cur->soft_timer_cb(cur->soft_timer_arg);
                     cur->tick = sys_ticks;
            }
      }

      return SOFT_TIMER_OK;
}
[/mw_shl_code]

Sun_Fly · 发表于 2017-5-27 09:39:42

liuchang 发表于 2017-5-26 18:03
[mw_shl_code=c,true]#include

typedef void (*soft_timer_cb_fn)(void *soft_timer_fn_arg);

结构体中的fuc函数必须是无返回，无参数的，这样添加的时候会方便很多，ID号只是为了以后扩展多个不同类型做的，再复杂点还需要优先级。当然就是扩展了，这还只是一个初步的东西。相互学习。想要减少CPU工作，可以考虑13搂的说法，加入最小时间概念。我当初也就是用到这部分了，看了比较精髓的代码，然后写的这部分简单的东西，大家相互学习。

ianhom · 发表于 2017-5-27 10:04:26

本帖最后由 ianhom 于 2017-5-27 10:18 编辑

liuchang 发表于 2017-5-26 18:01
每次看过你的帖子,我必定会认真阅读,经常聆听大神指导,无比感激......

小弟在大神的代码基础之上,稍加 ...

感谢关注，你才是专研的大神，你的每个帖子都很深入很实用

1>sys_ticks必须为uint64_t类型(额,我的sys_ticks++是放在一个10ms的中断里,这样的话,sys_ticks溢出时间为497天,也就一年多时间而已).
小弟我有点不解，为什么“必须”是64位类型，溢出一次有什么影响？
个人感觉10ms的颗粒度有点大，现在的操作系统都追求在不太拖累效率的情况，尽可能的有更细的时间颗粒度，比如zephyr就实现了ms和us级定时。现在MCU主频都蛮高的，1ms内能做很多操作。目前我很多项目使用的1ms中断基本不影响效率。

2>新增一个删除任务节点函数(额,既然有增加节点,毫无理由应当有删除节点才对)
估计楼主仅展示了关键部分的代码，所以没有把节点删除的部分贴出来

3>我将链表按照时间进行排序,比如有3个定时任务,1s,5s,3s,那么将按照1s,3s,5s进行排序(我觉得这样会提高链表的遍历效率,并且这个排序工作是在初始化时完成的,不会带来CPU额外开销).
在软件定时器设计中，排序是常用且很实用的设计，LiteOS中的时间管理就是排序的设计，可以参考一下。排序的好处就是头结点总是最快计时结束的节点，所以每次只需要对头节点的时间进行检查即可，而不用历遍链表。而在周期定时调度的时间片程序设计中，我们可以看一下排序的效果，任务A定时1s执行一次，任务B定时5秒执行一次，任务C定时3秒执行一次，在启动这三个任务后，排序将变成ACB，而真正的执行顺序是AAACAABACAAACAB.....
第0秒排序为 A(剩1秒)，C(剩3秒)，B(剩5秒)
第1秒排序为 A(剩0秒，然后重计1秒)，C(剩2秒)，B(剩4秒)
第2秒排序为 A(剩0秒，然后重计1秒)，C(剩1秒)，B(剩3秒)
第3秒排序为 A(剩0秒，然后重计1秒)，C(剩0秒，然后重计3秒)，B(剩2秒)
第4秒排序为 A(剩0秒，然后重计1秒)，B(剩1秒)，C(剩2秒)， //此处就需要重新排序
....
实际上只要任一个节点计时结束并重新计时，就需要对链表进行排序。同理，新增加定时器节点也要进行一次新的排序。排序确实比整链表历遍更有效率，但为了处理好各种细节，代码也更复杂，ROM消耗更大，运行中也有一定额外开销，排序操作时间不确定。

4>回调函数增加回调形参,这还是有必要的.
恩，对回调函数而言，有入参比较灵活一点。不过楼主没有贴出全部源码，作为时间片多任务程序而言，这里的回调可以理解为独立的任务，对任务传递参数还是有很多方法的。

5>我将struct结构体中成员id给删除了,说实话,这个成员没有啥用...
ID还是有用途的，可以作为任务ID，任务之间通讯可以使用到这个ID。如果作为操作系统中的软件定时器来使用，这一个ID可以标记关心这个定时事件的任务编号。

以上仅是我个人的一点经验，不一定应用到所有场景。
关于软件定时器，我的Github有一点记录，还望大神指导

也可以在qq里聊：16163184
https://github.com/ianhom/MOE/blob/master/Core/MOE_Timer.c
https://github.com/ianhom/MOE/blob/master/Documents/Design_Record.md/#关于定时器

Sun_Fly · 发表于 2017-5-27 10:15:40

ianhom 发表于 2017-5-27 10:04
感谢关注，你才是专研的大神，你的每个帖子都很深入很实用

1>sys_ticks必须为uint64_t类型(额,我的s ...

源码属于公司，我只能照着我的理解，加上查阅一些资料把代码写出来，源码其实非常复杂，链表中还有子链表，添加任务的时候添加到子链表中，主链表管大分支任务，子链表做小任务，这ID在这是非常重要的，我只能说我写的这个代码，只是一个入门级别的。源码的代码扩展性能非常之高。

ianhom · 发表于 2017-5-27 10:20:48

Sun_Fly 发表于 2017-5-27 10:15
源码属于公司，我只能照着我的理解，加上查阅一些资料把代码写出来，源码其实非常复杂，链表中还有子链表 ...

恩，可以看出楼主只是贴出关键部分做了分享交流，相信全套的源代码是强大而周全的

liuchang · 发表于 2017-5-27 11:13:41

ianhom 发表于 2017-5-27 10:04
感谢关注，你才是专研的大神，你的每个帖子都很深入很实用

1>sys_ticks必须为uint64_t类型(额,我的s ...

感谢大神回复,小弟受益良多...

1>sys_ticks溢出的确对结果没有影响.
因为是sys_tick是unsigned类型,0x0000 0000-0xFFFF FFFF仍然是=1的,这个是小弟理解错了

2>关于节点排序,其实我的想法是这样的(这个代码,小弟目前还写不出来,但我能表达下我的意思...)

A任务定时1s B任务定时5s C任务定时3s
那我就将ABC任务进行排序A(1)->C(3-1)->B(5-3)
工作思想:每次链表不需要遍历完整的所有节点,每次只需要将对应节点中的cnts--.
如果cnts==0时将链表从当前节点移动到下一个节点.
如果到达最后一个节点,再回到第一个节点(也就是单链表循环了)
我觉得这样会大大提高代码执行效率,毕竟如果节点很多,如此遍历所有节点,开销肯定不小的...
可是这部分代码小弟没有写出来...

3>关于ID部分,因为我只是将该部分代码当做是一个"纯粹的"软件定时器,所以没用上,不代表别人需要...这个是我表述问题...

再次感谢大神,欢迎指正...