2014-07-11 17:35:12 smallmelon 阅读数 1487
  • 定时器、看门狗和RTC-1.9.ARM裸机第九部分

    本期课程主要讲述SoC中的时间相关的外设,包括定时器、看门狗定时器和实时时钟RTC。首先讲述了定时器的基本概念,然后以PWM定时器为例详细讲解了定时器的使用及编程细节;看门狗定时器部分详细讲了看门狗的意义和常规工作形式;后2节课讲了RTC的概念、框图和编程方法

    7306 人正在学习 去看看 朱有鹏
大学无聊的时候看过linux内核的定时器,现在已经想不起来了,也不知道当时有没有看懂,现在想要模仿linux内核的定时器,用python写一个定时器,已经想不起来它的设计原理了,找了一篇blog,linux 内核定时器 timer_list详解

看了好一会才有些明白,开始参照着用python写了一个。如果在设计服务器的时候,有大量需要精确到秒和秒以下的事件,自己写一个定时器,维护一个类似与内核timer_vec的数据结构,处理服务的定时事件,还是蛮高效的。


附上python代码,github:点这里


2018-08-29 12:11:42 u014026685 阅读数 5862
  • 定时器、看门狗和RTC-1.9.ARM裸机第九部分

    本期课程主要讲述SoC中的时间相关的外设,包括定时器、看门狗定时器和实时时钟RTC。首先讲述了定时器的基本概念,然后以PWM定时器为例详细讲解了定时器的使用及编程细节;看门狗定时器部分详细讲了看门狗的意义和常规工作形式;后2节课讲了RTC的概念、框图和编程方法

    7306 人正在学习 去看看 朱有鹏

Linux下一种高效多定时器实现

作者:LouisozZ

日期:2018.08.29

运行环境说明

由于在 Linux 系统下一个进程只能设置一个时钟定时器,所以当应用需要有多个定时器来共同管理程序运行时,就需要自行实现多定时器管理。

本文就是基于这种需求,在实际编码工作的基础上总结而出,希望跟大家共享,也欢迎大家讨论指正。

多定时器原理

在一个进程只能有一个定时器的前提条件下,想要实现多定时器,就得用到那个进程能利用的唯一的定时器,这个定时器是由操作系统提供的,通过系统提供的接口来设置,常用的有 alarm() 和 setitimer(),不论用什么,后文统一称作系统定时接口,这两个接口的区别在很多博客里都有,不怎么清楚的可以自行搜索,这里就不再赘述(我比较懒,打字多对肾不好)。通过它们产生的定时信号作为基准时间,来管理实现多定时器。

举个栗子,糖炒板栗。利用系统定时接口设置了基准定时器,基准定时器每秒产生一个 SIGALRM 信号(系统时钟的超时时间到了之后会向进程发送信号以通知定时超时,alarm() 和 setitimer() 都是向进程发送 SIGALRM 信号,关于 Linux ‘信号’ 的内容,可以参考 《UNIX环境高级编程》),产生两个 SIGALRM 信号的时间间隔,就是多定时器的基准时间。当然,上述的基准时间是一秒,如果你是每隔 50ms 产生一个 SIGALRM 信号,那么多定时器的基准时间就是 50ms 。当有了基准时间之后,就可以对它进行管理,可以设置多个定时任务,现有两个定时任务,Timer1_Task , Timer2_Task, 其中 Timer1_Task 的定时时长为 10 个基准时间,Timer2_Task 为 15 个基准时间,则每产生 10 个 SIGALRM 信号,就表示 Timer1_Task 定时器超时到达,执行一次 Timer1_Task 的超时任务,每产生 15 个 SIGALRM 信号,则执行一次 Timer2_Task 超时任务,当产生的 SIGALRM 信号个数是 30 (10 和 15 的最小公倍数),则 Timer1_Task 和 Timer2_Task 的超时任务都要被执行。

好了,原理讲完了,下面就是本文的重点了。

————————————— 说重点专用阉割线 —————————————

————————————— 说重点专用分割线 —————————————

高效多定时器

数据结构

由一个全局链表 g_pTimeoutCheckListHead 来管理超时任务。链表的每个节点是一个 tMultiTimer 结构体:

    typedef void TimeoutCallBack(void*);    //回调函数格式
    typedef struct tMultiTimer
    {
        uint8_t nTimerID;       //设置宏定义
        uint32_t nInterval;     //定时时长
        uint32_t nTimeStamp;    //时间戳
        bool bIsSingleUse;      //是否单次使用
        bool bIsOverflow;       //用于解决计数溢出问题

        TimeoutCallBack *pTimeoutCallbackfunction;  //回调函数
        void* pTimeoutCallbackParameter;            //回调函数参数

        struct tMultiTimer* pNextTimer;             //双向链表后驱指针
        struct tMultiTimer* pPreTimer;              //双向链表前驱指针
        struct tMultiTimer* pNextHandle;            //二维链表相同超时Timer节点
    }tMultiTimer;

    tMultiTimer* g_pTimeoutCheckListHead;           //管理多定时器的全局链表
    bool g_bIs_g_nAbsoluteTimeOverFlow;             //基准时间计次器溢出标志位
    uint32_t g_nAbsoluteTime;                       //基准时间计次器

(各个成员变量的意义在后文会逐一介绍,客官莫急)

这个是一个二维双向链表,第一维根据时间戳,即绝对时间,按照先后顺序连接每一个 tMultiTimer 节点,当有多个超时任务的超时时刻是相同的时候,只有一个节点位于第一维,其余接在上一个相同超时时刻 tMultiTimer 节点的 pNextHandle 上,图示如下:
这里写图片描述

多定时管理流程

超时检测与运行

首先需要调用系统定时接口,设置进程的定时器,产生 SIGALRM 信号,每一次 SIGALRM 到来时,全局的基准时间计次器 g_nAbsoluteTime 自加,由于 g_nAbsoluteTime 是无符号类型,当其溢出时,是回到 0 ,每次溢出就把 g_bIs_g_nAbsoluteTimeOverFlow 取反。

每个  tMultiTimer 节点都有 :

    uint32_t nInterval;             //定时时长
    uint32_t nTimeStamp;        //时间戳

其中 nTimeStamp 这个值,是由 nInterval + g_nAbsoluteTime 计算而来,在把这个节点加入到全局链表的时刻计算的 ,这个和作为超时的绝对时间保存在结构体中,当计算的和溢出时,bIsOverflow 取反。通过这两个溢出标志位,可以用来解决溢出之后判断是否超时的问题,具体如下:

每一次基准时间超时,就检查链表的第一个节点的超时时间 nTimeStamp 是否小于全局绝对时间 g_nAbsoluteTime ,如果 g_bIs_g_nAbsoluteTimeOverFlow 与 bIsOverflow 不相等,则链表第一个节点的超时时间一定未到达,因为 bIsOverflow 的取反操作一定是先于 g_bIs_g_nAbsoluteTimeOverFlow ,如果一样则比较数值大小(初始化的时候两个溢出标志位是一样的)。当全局绝对时间大于等于第一个节点的时间戳,则把该节点及其 pNextHandle 指向的第二维链表取下,并更新 g_pTimeoutCheckListHead,然后依次执行所取下链表的回调函数。执行完之后(或者之前,根据实际情况定),判断 bIsSingleUse 成员变量,如果为 true 则表示是单次的计数器,仅执行一次,执行完回调之后则定时任务完成。如果是 false ,怎表示是定时任务,则重新执行一次添加超时任务。(添加超时任务看下一节)

添加超时任务

添加超时任务(添加一个 tMultiTimer 节点到全局链表 g_pTimeoutCheckListHead 中)的时候,指定超时时长,即间隔多少个基准时间,赋值给这个任务的成员变量 nInterval ,然后计算

    nTimeStamp = nInterval  + g_nAbsoluteTime; 
    if(nTimeStamp  < g_nAbsoluteTime) 
        bIsOverflow = ~bIsOverflow;

接着搜索 g_pTimeoutCheckListHead ,如果有相同时间戳,则添加到其 pNextHandle 指向位置,如果没有相同时间戳节点,找到比要插入的节点时间戳大的节点,然后把当前节点插入到其前方。

对于链表中已经有相同 ID 的 tMultiTimer 节点的情况,再次添加则表示更新该定时任务,取消之前的定时任务重新插入到链表中。

取消超时任务

直接把对应 ID 的 tMultiTimer 节点从 g_pTimeoutCheckListHead 链表中摘掉即可。

效率分析

g_pTimeoutCheckListHead 链表中的 tMultiTimer 节点数量,是总共设置的超时任务数量,假设为 n,添加一个超时任务(节点)的最坏情况是遍历 n 个节点。

检查是否有任务超时所用的时间是常数时间,只检查第一个节点。

对于定时任务的再次插入问题,如果定时任务间隔时间越短,其反复被插入的次数越多,但是由于定时时间短,所以在链表中的插入位置也就越靠前,将快速找到插入点;如果定时任务间隔时间越长,越可能遍历整个链表在末尾插入,但是由于间隔时间长,重复插入的频率则很低。

与一种简单的定时器实现相比较:

    if(g_nAbsoluteTime  %  4)
    {
        Timer_Task_1();
    }
    if(g_nAbsoluteTime  %  17)
    {
        Timer_Task_2();
    }

这种简单实现来说,

1:每次添加、取消一个定时任务都需要修改定时器源码,复用性不高。

2:每次检查是否有任务超时需要遍历 n 个定时任务。

关于多线程下的一些坑

我在实际项目中使用的环境是多线程的,有四个,我把多定时器管理放在了单独的一个线程里。由于系统定时器接口产生的信号是发送给进程的,所以所有的线程都共享这个闹钟信号。一开始我是这么想的,定时器的默认动作是杀死进程,那么给每个线程添加信号捕捉函数,这样的话闹钟信号到了之后不管是那个线程接管了,都能到我指定的处理函数去,可是实际情况并非如此,进程仍然会被杀死。

后面我用了线程信号屏蔽,把非定时器线程都设置了信号屏蔽字,即闹钟信号不被别的线程可见,这样才能正常运行,至于第一种方法为何不行,现在我还没有找到原因,还是对 Linux 的信号机制不熟,以后看有时间的话把这里搞懂吧。

main.c

    //配置信号集
    sigset_t g_sigset_mask;
    sigemptyset(&g_sigset_mask);
    sigaddset(&g_sigset_mask,SIGALRM);

other_thread.c

    sigset_t old_sig_mask;
    if(err = pthread_sigmask(SIG_SETMASK,&g_sigset_mask,&old_sig_mask) != 0)
    {
        // pthread_sigmask 设置信号屏蔽
        return ;
    }

mulitimer_thread

void* MultiTimer_thread(void *parameter)
{
    int err,signo;
    struct itimerval new_time_value,old_time_value;

    new_time_value.it_interval.tv_sec = 0;
    new_time_value.it_interval.tv_usec = 1000;
    new_time_value.it_value.tv_sec = 0;
    new_time_value.it_value.tv_usec = 1;
    setitimer(ITIMER_REAL, &new_time_value,NULL);

    for(;;)
    {
        err = sigwait(&g_sigset_mask,&signo);//信号捕捉
        if(err != 0)
        {
            return ;
        }

        if(signo == SIGALRM)
        {
            SYSTimeoutHandler(signo);
        }
    }
    return ((void*)0);
}

multiTimer.c

#include "multiTimer.h"

/**
 * @function    把一个定时任务添加到定时检测链表中
 * @parameter   一个定时器对象,可以由全局变量 g_aSPPMultiTimer 通过 TIMER_ID 映射得到
*/
static void AddTimerToCheckList(tMultiTimer* pTimer)
{
    tMultiTimer* pEarliestTimer = NULL;
    tMultiTimer* pEarliestTimer_pre = NULL;

    CDebugAssert(pTimer->nInterval != 0);

    pTimer->nTimeStamp = g_nAbsoluteTime + pTimer->nInterval;
    if(pTimer->nTimeStamp < g_nAbsoluteTime)
        pTimer->bIsOverflow = !(pTimer->bIsOverflow);
    if(g_pTimeoutCheckListHead == NULL)
    {
        g_pTimeoutCheckListHead = pTimer;
        g_pTimeoutCheckListHead->pNextTimer = NULL;
        g_pTimeoutCheckListHead->pPreTimer = NULL;
        g_pTimeoutCheckListHead->pNextHandle = NULL;
        return;
    }
    else
    {
        pEarliestTimer = g_pTimeoutCheckListHead;
        while(pEarliestTimer != NULL)
        {
            //如果超时时间小于新加的timer则直接跳过;
            if((pEarliestTimer->bIsOverflow != pTimer->bIsOverflow) || (pEarliestTimer->nTimeStamp < pTimer->nTimeStamp))
            {
                pEarliestTimer_pre = pEarliestTimer;
                pEarliestTimer = pEarliestTimer->pNextTimer;
            }    
            else
            {
                if(pEarliestTimer->nTimeStamp == pTimer->nTimeStamp)    //超时时刻相等,直接添加到相同时刻处理列表的列表头
                {
                    pTimer->pNextHandle = pEarliestTimer->pNextHandle;
                    pEarliestTimer->pNextHandle = pTimer;
                    return;
                }
                else                                                    //找到了超时时刻大于新加入timer的第一个节点
                {
                    if(pEarliestTimer->pPreTimer == NULL)               //新加入的是最早到达超时时刻的,添加到链表头
                    {
                        pEarliestTimer->pPreTimer = pTimer;
                        pTimer->pNextTimer = pEarliestTimer;
                        pTimer->pPreTimer = NULL;
                        pTimer->pNextHandle = NULL;
                        g_pTimeoutCheckListHead = pTimer;
                        return;
                    }
                    else                                                //中间节点
                    {
                        pEarliestTimer->pPreTimer->pNextTimer = pTimer;
                        pTimer->pNextTimer = pEarliestTimer;
                        pTimer->pPreTimer = pEarliestTimer->pPreTimer;
                        pEarliestTimer->pPreTimer = pTimer;
                        pTimer->pNextHandle = NULL;
                        return;
                    }
                }
            }  
        }
        if(pEarliestTimer == NULL)                                      //新加入的timer超时时间是最晚的那个
        {
            pEarliestTimer_pre->pNextTimer = pTimer;
            pTimer->pPreTimer = pEarliestTimer_pre;
            pTimer->pNextTimer = NULL;
            pTimer->pNextHandle = NULL;
        }
        return;
    }
}

/**
 * @function    设置一个定时任务,指定超时间隔与回调函数,当超时到来,自动执行回调
 * @parameter1  TIMER_ID    
 * @parameter2  超时间隔时间
 * @parameter3  是否是一次性定时任务
 * @parameter4  回调函数,注意,回调函数的函数形式  void function(void*);
 * @parameter5  void* 回调函数的参数,建议用结构体强转成 void*,在回调函数中再强转回来  
 * @return      错误码 
*/
uint8_t SetTimer(uint8_t nTimerID,uint32_t nInterval,bool bIsSingleUse,TimeoutCallBack* pCallBackFunction,void* pCallBackParameter)
{
    printf("\nset timer %d\n",nTimerID);
    tMultiTimer* pChoosedTimer = NULL;
    pChoosedTimer = g_aSPPMultiTimer[nTimerID];
    pChoosedTimer->nInterval = nInterval;
    pChoosedTimer->bIsSingleUse = bIsSingleUse;
    pChoosedTimer->pTimeoutCallbackfunction = pCallBackFunction;
    pChoosedTimer->pTimeoutCallbackParameter = pCallBackParameter;

    //如果超时任务链表中已经有这个任务了,先取消,然后再设置,即重置超时任务
    if(pChoosedTimer->pNextTimer != NULL || pChoosedTimer->pPreTimer != NULL)
        CancelTimerTask(nTimerID,CANCEL_MODE_IMMEDIATELY);

    AddTimerToCheckList(pChoosedTimer);
    return 0;
}

/**
 * @function    取消超时检测链表中的指定超时任务
 * @parameter1  要取消的超时任务的ID
 * @parameter2  模式选择,是立即取消,还是下次执行后取消
 * @return      错误码
*/
uint8_t CancelTimerTask(uint8_t nTimerID,uint8_t nCancelMode)
{
    printf("\ncancle timer %d\n",nTimerID);
    tMultiTimer* pEarliestTimer = NULL;
    tMultiTimer* pHandleTimer = NULL;
    tMultiTimer* pHandleTimer_pre = NULL;
    tMultiTimer* pChoosedTimer = NULL;

    pEarliestTimer = g_pTimeoutCheckListHead;
    pChoosedTimer = g_aSPPMultiTimer[nTimerID];

    if(nCancelMode == CANCEL_MODE_IMMEDIATELY)
    {
        while(pEarliestTimer != NULL)
        {
            pHandleTimer = pEarliestTimer;
            pHandleTimer_pre = NULL;
            while(pHandleTimer != NULL)
            {
                if(pHandleTimer->nTimerID == nTimerID)
                {
                    if(pHandleTimer_pre == NULL)
                    {
                        if(pHandleTimer->pNextHandle != NULL)
                        {
                            pEarliestTimer = pHandleTimer->pNextHandle;
                            pEarliestTimer->pPreTimer = pHandleTimer->pPreTimer;
                            if(pHandleTimer->pPreTimer != NULL)
                                pHandleTimer->pPreTimer->pNextTimer = pEarliestTimer;
                            pEarliestTimer->pNextTimer = pHandleTimer->pNextTimer;
                            if(pHandleTimer->pNextTimer != NULL)
                                pHandleTimer->pNextTimer->pPreTimer = pEarliestTimer;
                            pHandleTimer->pNextTimer = NULL;
                            pHandleTimer->pPreTimer = NULL;
                            pHandleTimer->pNextHandle = NULL;
                        }
                        else
                        {
                            if(pEarliestTimer->pPreTimer == NULL)
                            {
                                g_pTimeoutCheckListHead = pEarliestTimer->pNextTimer;
                                g_pTimeoutCheckListHead->pPreTimer = NULL;
                                pEarliestTimer->pNextTimer = NULL;
                            }
                            else if(pEarliestTimer->pNextTimer == NULL)
                            {
                                pEarliestTimer->pPreTimer->pNextTimer = NULL;
                                pEarliestTimer->pPreTimer = NULL;
                            }
                            else
                            {
                                pEarliestTimer->pPreTimer->pNextTimer = pEarliestTimer->pNextTimer;
                                pEarliestTimer->pNextTimer->pPreTimer = pEarliestTimer->pPreTimer;
                                pEarliestTimer->pPreTimer = NULL;
                                pEarliestTimer->pNextTimer = NULL;
                            }
                        }
                    }
                    else
                    {
                        pHandleTimer_pre->pNextHandle = pHandleTimer->pNextHandle;
                        pHandleTimer->pNextHandle = NULL;
                    }
                    return 0;
                }
                else
                {
                    pHandleTimer_pre = pHandleTimer;
                    pHandleTimer = pHandleTimer_pre->pNextHandle;
                }
            }
            pEarliestTimer = pEarliestTimer->pNextTimer;
        }
        #ifdef DEBUG_PRINTF
        printf("\nThere is no this timer task!\n");
        #endif
        return 2;   //出错,超时检测链表中没有这个超时任务
    }
    else if(nCancelMode == CANCEL_MODE_AFTER_NEXT_TIMEOUT)
    {
        pChoosedTimer->bIsSingleUse = true;
        return 0;
    }
    else
    {
        return 1;   //出错,模式错误,不认识该模式
    }
}
/**
 * @function    定时器处理函数,用于检测是否有定时任务超时,如果有则调用该定时任务的回调函数,并更新超时检测链表
 *              更新动作:如果超时的那个定时任务不是一次性的,则将新的节点加入到检测超时链表中,否则直接删掉该节点;
 * @parameter   
 * @return
*/
void SYSTimeoutHandler(int signo)
{
    //printf("\nenter SYSTimeoutHandler\n");
    if(signo != SIGALRM)
        return;
    tMultiTimer* pEarliestTimer = NULL;
    tMultiTimer* pWaitingToHandle = NULL;
    tMultiTimer* pEarliestTimerPreHandle = NULL;

    if(g_pTimeoutCheckListHead != NULL)
    {
        if((g_pTimeoutCheckListHead->nTimeStamp <= g_nAbsoluteTime) && (g_pTimeoutCheckListHead->bIsOverflow == g_bIs_g_nAbsoluteTimeOverFlow))
        {
            pWaitingToHandle = g_pTimeoutCheckListHead;
            g_pTimeoutCheckListHead = g_pTimeoutCheckListHead->pNextTimer;
            if(g_pTimeoutCheckListHead != NULL)
                g_pTimeoutCheckListHead->pPreTimer = NULL;
            pWaitingToHandle->pNextTimer = NULL;

            pEarliestTimer = pWaitingToHandle;
            while(pEarliestTimer != NULL)
            {
                pEarliestTimerPreHandle = pEarliestTimer;
                pEarliestTimer = pEarliestTimer->pNextHandle;
                pEarliestTimerPreHandle->pNextHandle = NULL;
                pEarliestTimerPreHandle->pNextTimer = NULL;
                pEarliestTimerPreHandle->pPreTimer = NULL;
                pEarliestTimerPreHandle->pTimeoutCallbackfunction(pEarliestTimerPreHandle->pTimeoutCallbackParameter);
                if(!(pEarliestTimerPreHandle->bIsSingleUse))
                    AddTimerToCheckList(pEarliestTimerPreHandle);
            }
        }
    }

    g_nAbsoluteTime++;
    if(g_nAbsoluteTime == 0)
        g_bIs_g_nAbsoluteTimeOverFlow = !g_bIs_g_nAbsoluteTimeOverFlow;

    return ;
}

void CancleAllTimerTask()
{
    tMultiTimer* pEarliestTimer = NULL;
    tMultiTimer* pHandleTimer = NULL;

    while(g_pTimeoutCheckListHead != NULL)
    {
        pEarliestTimer = g_pTimeoutCheckListHead;
        g_pTimeoutCheckListHead = g_pTimeoutCheckListHead->pNextTimer;

        while(pEarliestTimer != NULL)
        {
            pHandleTimer = pEarliestTimer;
            pEarliestTimer = pEarliestTimer->pNextHandle;

            pHandleTimer->pNextHandle = NULL;
            pHandleTimer->pNextTimer = NULL;
            pHandleTimer->pPreTimer = NULL;
            pHandleTimer->bIsOverflow = false;
        }
    }
    g_bIs_g_nAbsoluteTimeOverFlow = false;
    g_nAbsoluteTime = 0;
    return;
}

void MultiTimerInit()
{
    g_pTimeoutCheckListHead = NULL;
    g_bIs_g_nAbsoluteTimeOverFlow = false;
    g_nAbsoluteTime = 0;
    for(uint8_t index = 0; index < MAX_TIMER_UPPER_LIMIT; index++)
    {
        g_aSPPMultiTimer[index] = (tMultiTimer*)CMALLOC(sizeof(tMultiTimer));
        g_aSPPMultiTimer[index]->nTimerID = g_aTimerID[index];
        g_aSPPMultiTimer[index]->nInterval = g_aDefaultTimeout[index];
        g_aSPPMultiTimer[index]->nTimeStamp = 0;
        g_aSPPMultiTimer[index]->bIsSingleUse = true;
        g_aSPPMultiTimer[index]->bIsOverflow = false;
        g_aSPPMultiTimer[index]->pTimeoutCallbackfunction = NULL;
        g_aSPPMultiTimer[index]->pTimeoutCallbackParameter = NULL;
        g_aSPPMultiTimer[index]->pNextTimer = NULL;
        g_aSPPMultiTimer[index]->pPreTimer = NULL;
        g_aSPPMultiTimer[index]->pNextHandle = NULL;
    }
    /*  如果预先规定了一些定时器,这个时候可以初始化除时间戳以外的其他值  */
    //开启应答超时任务
    //OPEN_MULTITIMER_MANGMENT();
}

multiTimer.h

#ifndef __MULTITIMER_H__
#define __MULTITIMER_H__

#define MAX_TIMER_UPPER_LIMIT   6

#define TIMER_0                 0
#define TIMER_1                 1       //timer ID
#define TIMER_2                 2
#define TIMER_3                 3
#define TIMER_4                 4
#define TIMER_5                 5

#define CANCEL_MODE_IMMEDIATELY         0xf9
#define CANCEL_MODE_AFTER_NEXT_TIMEOUT  0x9f

typedef void TimeoutCallBack(void*);

//========================================================
//                      timer结构定义
//========================================================
typedef struct tMultiTimer
{
    uint8_t nTimerID;       //
    uint32_t nInterval;     //定时时长
    uint32_t nTimeStamp;    //时间戳
    bool bIsSingleUse;      //是否单次使用
    bool bIsOverflow;       //用于解决计数溢出问题
    TimeoutCallBack *pTimeoutCallbackfunction;
    void* pTimeoutCallbackParameter;

    //双向链表指针
    struct tMultiTimer* pNextTimer;
    struct tMultiTimer* pPreTimer;
    //相同时间戳的下一个处理函数    这里可能会有隐藏的 bug,如果基础时间中断比较快,那么可能在处理多个同一时间节点的
    //回调函数的时候被下一次的中断打断,这里会引起时序错误,
    //解决方案有三种,
    //一是可以人为避免,不设置有公约数的定时时间,这样的话同一个时刻有多个定时任务的情况就小很多;
    //二是回调函数尽量少做事,快速退出定时处理函数;
    //三是另开一个线程,这个线程仅把回调函数放到一个队列中,另一个线程持续从队列中取回调函数执行,这个是没有问题的方案,但是需要支持多线程或者多任务,并且需要注意加锁
    struct tMultiTimer* pNextHandle;

}tMultiTimer;

//========================================================
//               实现多定时任务的相关变量
//========================================================

tMultiTimer* g_pTimeoutCheckListHead;
bool g_bIs_g_nAbsoluteTimeOverFlow;
uint32_t g_nAbsoluteTime;

//========================================================
//                      外部接口
//========================================================
void MultiTimerInit();
uint8_t SetTimer(uint8_t nTimerID,uint32_t nInterval,bool bIsSingleUse,TimeoutCallBack* pCallBackFunction,void* pCallBackParameter);
uint8_t CancelTimerTask(uint8_t nTimerID,uint8_t nCancelMode);
void CancleAllTimerTask();
void SYSTimeoutHandler(int signo);
#endif
2019-08-27 00:31:56 THEANARKH 阅读数 41
  • 定时器、看门狗和RTC-1.9.ARM裸机第九部分

    本期课程主要讲述SoC中的时间相关的外设,包括定时器、看门狗定时器和实时时钟RTC。首先讲述了定时器的基本概念,然后以PWM定时器为例详细讲解了定时器的使用及编程细节;看门狗定时器部分详细讲了看门狗的意义和常规工作形式;后2节课讲了RTC的概念、框图和编程方法

    7306 人正在学习 去看看 朱有鹏

操作系统的定时器原理是,操作系统维护了一个定时器节点的链表,新增一个定时器节点时,设置一个jiffies值,这是触发定时中断的频率。linux0.11版本里是1秒触发100次,即10毫秒一次。加入新增一个定时器的jiffies值是2,那经过两次定时中断后就会被执行。jiffies值在每次定时中断时会加一。

_timer_interrupt:
	push %ds		# save ds,es and put kernel data space
	push %es		# into them. %fs is used by _system_call
	push %fs
	pushl %edx		# we save %eax,%ecx,%edx as gcc doesn't
	pushl %ecx		# save those across function calls. %ebx
	pushl %ebx		# is saved as we use that in ret_sys_call
	pushl %eax
	movl $0x10,%eax
	mov %ax,%ds
	mov %ax,%es
	movl $0x17,%eax
	mov %ax,%fs
	incl _jiffies
        ...

下面是定时器的结构图。
在这里插入图片描述

#define TIME_REQUESTS 64

// 定时器数组,其实是个链表
static struct timer_list {
	long jiffies;
	void (*fn)();
	struct timer_list * next;
} timer_list[TIME_REQUESTS], * next_timer = NULL;

void add_timer(long jiffies, void (*fn)(void))
{
	struct timer_list * p;

	if (!fn)
		return;
	// 关中断,防止多个进程”同时“操作
	cli();
	// 直接到期,直接执行回调
	if (jiffies <= 0)
		(fn)();
	else {
		// 遍历定时器数组,找到一个空项
		for (p = timer_list ; p < timer_list + TIME_REQUESTS ; p++)
			if (!p->fn)
				break;
		// 没有空项了
		if (p >= timer_list + TIME_REQUESTS)
			panic("No more time requests free");
		// 给空项赋值
		p->fn = fn;
		p->jiffies = jiffies;
		// 在数组中形成链表
		p->next = next_timer;
		// next_timer指向第一个节点,即最早到期的
		next_timer = p;
		/*
			修改链表,保证超时时间是从小到大的顺序
			原理:
				每个节点都是以前面一个节点的到时时间为坐标,节点里的jiffies即超时时间
				是前一个节点到期后的多少个jiffies后该节点到期。
		*/
		while (p->next && p->next->jiffies < p->jiffies) {
			// 前面的节点比后面节点大,则前面节点减去后面节点的值,算出偏移值,下面准备置换位置
			p->jiffies -= p->next->jiffies;
			// 先保存一下
			fn = p->fn;
			// 置换两个节点的回调
			p->fn = p->next->fn;
			p->next->fn = fn;
			jiffies = p->jiffies;
			// 置换两个节点是超时时间
			p->jiffies = p->next->jiffies;
			p->next->jiffies = jiffies;
			/*
				到这,第一个节点是最快到期的,还需要更新后续节点的值,其实就是找到一个合适的位置
				插入,因为内核是用数组实现的定时器队列,所以是通过置换位置实现插入,
				如果是链表,则直接找到合适的位置,插入即可,所谓合适的位置,
				就是找到第一个比当前节点大的节点,插入到他前面。
			*/
			p = p->next;
		}
		/*
			内核这里实现有个bug,当当前节点是最小时,需要更新原链表中第一个节点的值,,
			否则会导致原链表中第一个节点的过期时间延长,修复代码如下:
			if (p->next && p->next->jiffies > p->jiffies) {
				p->next->jiffies = p->next->jiffies - p->jiffies;
			}	
			即更新原链表中第一个节点相对于新的第一个节点的偏移,剩余的节点不需要更新,因为他相对于
			他前面的节点的偏移不变,但是原链表中的第一个节点之前前面没有节点,所以偏移就是他自己的值,
			而现在在他前面插入了一个节点,则他的偏移是相对于前面一个节点的偏移
		*/
	}
	sti();
}
// 定时中断处理函数
void do_timer(long cpl)
{
	extern int beepcount;
	extern void sysbeepstop(void);

	if (beepcount)
		if (!--beepcount)
			sysbeepstop();
	// 当前在用户态,增加用户态的执行时间,否则增加该进程的系统执行时间
	if (cpl)
		current->utime++;
	else
		current->stime++;
	// next_timer为空说明还没有定时节点
	if (next_timer) {
		// 第一个节点减去一个jiffies,因为其他节点都是相对第一个节点的偏移,所以其他节点的值不需要变
		next_timer->jiffies--;
		// 当前节点到期,如果有多个节点超时时间一样,即相对第一个节点偏移是0,则会多次进入while循环
		while (next_timer && next_timer->jiffies <= 0) {
			void (*fn)(void);
			
			fn = next_timer->fn;
			next_timer->fn = NULL;
			// 下一个节点
			next_timer = next_timer->next;
			// 执行定时回调函数
			(fn)();
		}
	}
	if (current_DOR & 0xf0)
		do_floppy_timer();
	// 当前进程的可用时间减一,不为0则接着执行,否则可能需要重新调度
	if ((--current->counter)>0) return;
	current->counter=0;
	// 是系统进程则继续执行
	if (!cpl) return;
	// 进程调度
	schedule();
}
2018-07-16 22:55:49 thisinnocence 阅读数 13856
  • 定时器、看门狗和RTC-1.9.ARM裸机第九部分

    本期课程主要讲述SoC中的时间相关的外设,包括定时器、看门狗定时器和实时时钟RTC。首先讲述了定时器的基本概念,然后以PWM定时器为例详细讲解了定时器的使用及编程细节;看门狗定时器部分详细讲了看门狗的意义和常规工作形式;后2节课讲了RTC的概念、框图和编程方法

    7306 人正在学习 去看看 朱有鹏

定时器的实现原理

定时器的实现依赖的是CPU时钟中断,时钟中断的精度就决定定时器精度的极限。一个时钟中断源如何实现多个定时器呢?对于内核,简单来说就是用特定的数据结构管理众多的定时器,在时钟中断处理中判断哪些定时器超时,然后执行超时处理动作。而用户空间程序不直接感知CPU时钟中断,通过感知内核的信号、IO事件、调度,间接依赖时钟中断。用软件来实现动态定时器常用数据结构有:时间轮、最小堆和红黑树。下面就是一些知名的实现:

Linux内核定时器相关(Linux v4.9.7, x86体系架构)的一些相关代码:

内核启动注册时钟中断

// @file: arch/x86/kernel/time.c - Linux 4.9.7
// 内核init阶段注册时钟中断处理函数
static struct irqaction irq0  = {
    .handler = timer_interrupt,
    .flags = IRQF_NOBALANCING | IRQF_IRQPOLL | IRQF_TIMER,
    .name = "timer"
};

void __init setup_default_timer_irq(void)
{
    if (!nr_legacy_irqs())
        return;
    setup_irq(0, &irq0);
}

// Default timer interrupt handler for PIT/HPET
static irqreturn_t timer_interrupt(int irq, void *dev_id)
{
    // 调用体系架构无关的时钟处理流程
    global_clock_event->event_handler(global_clock_event);
    return IRQ_HANDLED;
}

内核时钟中断处理流程

// @file: kernel/time/timer.c - Linux 4.9.7
/*
 * Called from the timer interrupt handler to charge one tick to the current
 * process.  user_tick is 1 if the tick is user time, 0 for system.
 */
void update_process_times(int user_tick)
{
    struct task_struct *p = current;

    /* Note: this timer irq context must be accounted for as well. */
    account_process_tick(p, user_tick);
    run_local_timers();
    rcu_check_callbacks(user_tick);
#ifdef CONFIG_IRQ_WORK
    if (in_irq())
        irq_work_tick();
#endif
    scheduler_tick();
    run_posix_cpu_timers(p);
}

/*
 * Called by the local, per-CPU timer interrupt on SMP.
 */
void run_local_timers(void)
{
    struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);

    hrtimer_run_queues();
    /* Raise the softirq only if required. */
    if (time_before(jiffies, base->clk)) {
        if (!IS_ENABLED(CONFIG_NO_HZ_COMMON) || !base->nohz_active)
            return;
        /* CPU is awake, so check the deferrable base. */
        base++;
        if (time_before(jiffies, base->clk))
            return;
    }
    raise_softirq(TIMER_SOFTIRQ); // 标记一个软中断去处理所有到期的定时器
}

内核定时器时间轮算法

单层时间轮算法的原理比较简单:用一个数组表示时间轮,每个时钟周期,时间轮 current 往后走一个格,并处理挂在这个格子的定时器链表,如果超时则进行超时动作处理,然后删除定时器,没有则剩余轮数减一。原理如图:
这里写图片描述
Linux 内核则采用的是 Hierarchy 时间轮算法,Hierarchy 时间轮将单一的 bucket 数组分成了几个不同的数组,每个数组表示不同的时间精度,Linux 内核中用 jiffies 记录时间,jiffies记录了系统启动以来经过了多少tick。下面是Linux 4.9的一些代码:

// @file: kernel/time/timer.c - Linux 4.9.7
/*
 * The timer wheel has LVL_DEPTH array levels. Each level provides an array of
 * LVL_SIZE buckets. Each level is driven by its own clock and therefor each
 * level has a different granularity.
 */

/* Size of each clock level */
#define LVL_BITS    6
#define LVL_SIZE    (1UL << LVL_BITS)

/* Level depth */
#if HZ > 100
# define LVL_DEPTH  9
# else
# define LVL_DEPTH  8
#endif

#define WHEEL_SIZE  (LVL_SIZE * LVL_DEPTH)

struct timer_base {
    spinlock_t      lock;
    struct timer_list   *running_timer;
    unsigned long       clk;
    unsigned long       next_expiry;
    unsigned int        cpu;
    bool            migration_enabled;
    bool            nohz_active;
    bool            is_idle;
    DECLARE_BITMAP(pending_map, WHEEL_SIZE);
    struct hlist_head   vectors[WHEEL_SIZE];
} ____cacheline_aligned;

Hierarchy 时间轮的原理大致如下,下面是一个时分秒的Hierarchy时间轮,不同于Linux内核的实现,但原理类似。对于时分秒三级时间轮,每个时间轮都维护一个cursor,新建一个timer时,要挂在合适的格子,剩余轮数以及时间都要记录,到期判断超时并调整位置。原理图大致如下:
这里写图片描述

定时器的使用方法

在Linux 用户空间程序开发中,常用的定期器可以分为两类:

  1. 执行一次的单次定时器 single-short;
  2. 循环执行的周期定时器 Repeating Timer;

其中,Repeating Timer 可以通过在Single-Shot Timer 终止之后,重新再注册到定时器系统里来实现。当一个进程需要使用大量定时器时,同样利用时间轮、最小堆或红黑树等结构来管理定时器。而时钟周期来源则需要借助系统调用,最终还是从时钟中断。Linux用户空间程序的定时器可用下面方法来实现:

  • 通过alarm()setitimer()系统调用,非阻塞异步,配合SIGALRM信号处理;
  • 通过select()nanosleep()系统调用,阻塞调用,往往需要新建一个线程;
  • 通过timefd()调用,基于文件描述符,可以被用于 select/poll 的应用场景;
  • 通过RTC机制, 利用系统硬件提供的Real Time Clock机制, 计时非常精确;

上面方法没提sleep(),因为Linux中并没有系统调用sleep(),sleep()是在库函数中实现,是通过调用alarm()来设定报警时间,调用sigsuspend()将进程挂起在信号SIGALARM上,而且sleep()也只能精确到秒级上,精度不行。当使用阻塞调用作为定时周期来源时,可以单独启一个线程用来管理所有定时器,当定时器超时的时候,向业务线程发送定时器消息即可。

一个基于时间轮的定时器简单实现

#include <stdio.h>
#include <signal.h>
#include <stdlib.h>
#include <unistd.h>

#define TIME_WHEEL_SIZE 8

typedef void (*func)(int data);

struct timer_node {
    struct timer_node *next;
    int rotation;
    func proc;
    int data;
};

struct timer_wheel {
    struct timer_node *slot[TIME_WHEEL_SIZE];
    int current;
};

struct timer_wheel timer = {{0}, 0};

void tick(int signo)
{
    // 使用二级指针删进行单链表的删除
    struct timer_node **cur = &timer.slot[timer.current];
    while (*cur) {
        struct timer_node *curr = *cur;
        if (curr->rotation > 0) {
            curr->rotation--;
            cur = &curr->next;
        } else {
            curr->proc(curr->data);
            *cur = curr->next;
            free(curr);
        }
    }
    timer.current = (timer.current + 1) % TIME_WHEEL_SIZE;
    alarm(1);
}

void add_timer(int len, func action)
{
    int pos = (len + timer.current) % TIME_WHEEL_SIZE;
    struct timer_node *node = malloc(sizeof(struct timer_node));

    // 插入到对应格子的链表头部即可, O(1)复杂度
    node->next = timer.slot[pos];
    timer.slot[pos] = node;
    node->rotation = len / TIME_WHEEL_SIZE;
    node->data = 0;
    node->proc = action;
}

 // test case1: 1s循环定时器
int g_sec = 0;
void do_time1(int data)
{
    printf("timer %s, %d\n", __FUNCTION__, g_sec++);
    add_timer(1, do_time1);
}

// test case2: 2s单次定时器
void do_time2(int data)
{
    printf("timer %s\n", __FUNCTION__);
}

// test case3: 9s循环定时器
void do_time9(int data)
{
    printf("timer %s\n", __FUNCTION__);
    add_timer(9, do_time9);
}

int main()
{
    signal(SIGALRM, tick);
    alarm(1); // 1s的周期心跳

    // test
    add_timer(1, do_time1);
    add_timer(2, do_time2);
    add_timer(9, do_time9);

    while(1) pause();
    return 0;
}

在实际项目中,一个常用的做法是新起一个线程,专门管理定时器,定时来源使用rtc、select等比较精确的来源,定时器超时后向主要的work线程发消息即可,或者使用timefd接口。

参考:

2012-10-19 23:05:01 DroidPhone 阅读数 70050
  • 定时器、看门狗和RTC-1.9.ARM裸机第九部分

    本期课程主要讲述SoC中的时间相关的外设,包括定时器、看门狗定时器和实时时钟RTC。首先讲述了定时器的基本概念,然后以PWM定时器为例详细讲解了定时器的使用及编程细节;看门狗定时器部分详细讲了看门狗的意义和常规工作形式;后2节课讲了RTC的概念、框图和编程方法

    7306 人正在学习 去看看 朱有鹏

上一篇文章,我介绍了传统的低分辨率定时器的实现原理。而随着内核的不断演进,大牛们已经对这种低分辨率定时器的精度不再满足,而且,硬件也在不断地发展,系统中的定时器硬件的精度也越来越高,这也给高分辨率定时器的出现创造了条件。内核从2.6.16开始加入了高精度定时器架构。在实现方式上,内核的高分辨率定时器的实现代码几乎没有借用低分辨率定时器的数据结构和代码,内核文档给出的解释主要有以下几点:

  • 低分辨率定时器的代码和jiffies的关系太过紧密,并且默认按32位进行设计,并且它的代码已经经过长时间的优化,目前的使用也是没有任何错误,如果硬要基于它来实现高分辨率定时器,势必会打破原有的时间轮概念,并且会引入一大堆#if--#else判断;
  • 虽然大部分时间里,时间轮可以实现O(1)时间复杂度,但是当有进位发生时,不可预测的O(N)定时器级联迁移时间,这对于低分辨率定时器来说问题不大,可是它大大地影响了定时器的精度;
  • 低分辨率定时器几乎是为“超时”而设计的,并为此对它进行了大量的优化,对于这些以“超时”未目的而使用定时器,它们大多数期望在超时到来之前获得正确的结果,然后删除定时器,精确时间并不是它们主要的目的,例如网络通信、设备IO等等。

为此,内核为高精度定时器重新设计了一套软件架构,它可以为我们提供纳秒级的定时精度,以满足对精确时间有迫切需求的应用程序或内核驱动,例如多媒体应用,音频设备的驱动程序等等。以下的讨论用hrtimer(high resolution timer)表示高精度定时器。
/*****************************************************************************************************/
声明:本博内容均由http://blog.csdn.net/droidphone原创,转载请注明出处,谢谢!
/*****************************************************************************************************/

1.  如何组织hrtimer?

我们知道,低分辨率定时器使用5个链表数组来组织timer_list结构,形成了著名的时间轮概念,对于高分辨率定时器,我们期望组织它们的数据结构至少具备以下条件:

  • 稳定而且快速的查找能力;
  • 快速地插入和删除定时器的能力;
  • 排序功能;

内核的开发者考察了多种数据结构,例如基数树、哈希表等等,最终他们选择了红黑树(rbtree)来组织hrtimer,红黑树已经以库的形式存在于内核中,并被成功地使用在内存管理子系统和文件系统中,随着系统的运行,hrtimer不停地被创建和销毁,新的hrtimer按顺序被插入到红黑树中,树的最左边的节点就是最快到期的定时器,内核用一个hrtimer结构来表示一个高精度定时器:

struct hrtimer {
	struct timerqueue_node		node;
	ktime_t				_softexpires;
	enum hrtimer_restart		(*function)(struct hrtimer *);
	struct hrtimer_clock_base	*base;
	unsigned long			state;
        ......
};
定时器的到期时间用ktime_t来表示,_softexpires字段记录了时间,定时器一旦到期,function字段指定的回调函数会被调用,该函数的返回值为一个枚举值,它决定了该hrtimer是否需要被重新激活:

enum hrtimer_restart {
	HRTIMER_NORESTART,	/* Timer is not restarted */
	HRTIMER_RESTART,	/* Timer must be restarted */
};
state字段用于表示hrtimer当前的状态,有几下几种位组合:

#define HRTIMER_STATE_INACTIVE	0x00  // 定时器未激活
#define HRTIMER_STATE_ENQUEUED	0x01  // 定时器已经被排入红黑树中
#define HRTIMER_STATE_CALLBACK	0x02  // 定时器的回调函数正在被调用
#define HRTIMER_STATE_MIGRATE	0x04  // 定时器正在CPU之间做迁移
hrtimer的到期时间可以基于以下几种时间基准系统:

enum  hrtimer_base_type {
	HRTIMER_BASE_MONOTONIC,  // 单调递增的monotonic时间,不包含休眠时间
	HRTIMER_BASE_REALTIME,   // 平常使用的墙上真实时间
	HRTIMER_BASE_BOOTTIME,   // 单调递增的boottime,包含休眠时间
	HRTIMER_MAX_CLOCK_BASES, // 用于后续数组的定义
};
和低分辨率定时器一样,处于效率和上锁的考虑,每个cpu单独管理属于自己的hrtimer,为此,专门定义了一个结构hrtimer_cpu_base:

struct hrtimer_cpu_base {
        ......
	struct hrtimer_clock_base	clock_base[HRTIMER_MAX_CLOCK_BASES];
};
其中,clock_base数组为每种时间基准系统都定义了一个hrtimer_clock_base结构,它的定义如下:

struct hrtimer_clock_base {
	struct hrtimer_cpu_base	*cpu_base;  // 指向所属cpu的hrtimer_cpu_base结构
        ......
	struct timerqueue_head	active;     // 红黑树,包含了所有使用该时间基准系统的hrtimer
	ktime_t			resolution; // 时间基准系统的分辨率
	ktime_t			(*get_time)(void); // 获取该基准系统的时间函数
	ktime_t			softirq_time;// 当用jiffies
	ktime_t			offset;      // 
};
active字段是一个timerqueue_head结构,它实际上是对rbtree的进一步封装:
struct timerqueue_node {
	struct rb_node node;  // 红黑树的节点
	ktime_t expires;      // 该节点代表队hrtimer的到期时间,与hrtimer结构中的_softexpires稍有不同
};

struct timerqueue_head {
	struct rb_root head;          // 红黑树的根节点
	struct timerqueue_node *next; // 该红黑树中最早到期的节点,也就是最左下的节点
};
timerqueue_head结构在红黑树的基础上,增加了一个next字段,用于保存树中最先到期的定时器节点,实际上就是树的最左下方的节点,有了next字段,当到期事件到来时,系统不必遍历整个红黑树,只要取出next字段对应的节点进行处理即可。timerqueue_node用于表示一个hrtimer节点,它在标准红黑树节点rb_node的基础上增加了expires字段,该字段和hrtimer中的_softexpires字段一起,设定了hrtimer的到期时间的一个范围,hrtimer可以在hrtimer._softexpires至timerqueue_node.expires之间的任何时刻到期,我们也称timerqueue_node.expires为硬过期时间(hard),意思很明显:到了此时刻,定时器一定会到期,有了这个范围可以选择,定时器系统可以让范围接近的多个定时器在同一时刻同时到期,这种设计可以降低进程频繁地被hrtimer进行唤醒。经过以上的讨论,我们可以得出以下的图示,它表明了每个cpu上的hrtimer是如何被组织在一起的:

                                                       图 1.1  每个cpu的hrtimer组织结构

总结一下:

  • 每个cpu有一个hrtimer_cpu_base结构;
  • hrtimer_cpu_base结构管理着3种不同的时间基准系统的hrtimer,分别是:实时时间,启动时间和单调时间;
  • 每种时间基准系统通过它的active字段(timerqueue_head结构指针),指向它们各自的红黑树;
  • 红黑树上,按到期时间进行排序,最先到期的hrtimer位于最左下的节点,并被记录在active.next字段中;
  • 3中时间基准的最先到期时间可能不同,所以,它们之中最先到期的时间被记录在hrtimer_cpu_base的expires_next字段中。

2.  hrtimer如何运转

hrtimer的实现需要一定的硬件基础,它的实现依赖于我们前几章介绍的timekeeper和clock_event_device,如果你对timekeeper和clock_event_device不了解请参考以下文章:Linux时间子系统之三:时间的维护者:timekeeperLinux时间子系统之四:定时器的引擎:clock_event_device。hrtimer系统需要通过timekeeper获取当前的时间,计算与到期时间的差值,并根据该差值,设定该cpu的tick_device(clock_event_device)的下一次的到期时间,时间一到,在clock_event_device的事件回调函数中处理到期的hrtimer。现在你或许有疑问:前面在介绍clock_event_device时,我们知道,每个cpu有自己的tick_device,通常用于周期性地产生进程调度和时间统计的tick事件,这里又说要用tick_device调度hrtimer系统,通常cpu只有一个tick_device,那他们如何协调工作?这个问题也一度困扰着我,如果再加上NO_HZ配置带来tickless特性,你可能会更晕。这里我们先把这个疑问放下,我将在后面的章节中来讨论这个问题,现在我们只要先知道,一旦开启了hrtimer,tick_device所关联的clock_event_device的事件回调函数会被修改为:hrtimer_interrupt,并且会被设置成工作于CLOCK_EVT_MODE_ONESHOT单触发模式。

2.1  添加一个hrtimer

要添加一个hrtimer,系统提供了一些api供我们使用,首先我们需要定义一个hrtimer结构的实例,然后用hrtimer_init函数对它进行初始化,它的原型如下:

void hrtimer_init(struct hrtimer *timer, clockid_t which_clock,
			 enum hrtimer_mode mode);
which_clock可以是CLOCK_REALTIME、CLOCK_MONOTONIC、CLOCK_BOOTTIME中的一种,mode则可以是相对时间HRTIMER_MODE_REL,也可以是绝对时间HRTIMER_MODE_ABS。设定回调函数:
timer.function = hr_callback;

如果定时器无需指定一个到期范围,可以在设定回调函数后直接使用hrtimer_start激活该定时器:

int hrtimer_start(struct hrtimer *timer, ktime_t tim,
			 const enum hrtimer_mode mode);
如果需要指定到期范围,则可以使用hrtimer_start_range_ns激活定时器:

hrtimer_start_range_ns(struct hrtimer *timer, ktime_t tim,
			unsigned long range_ns, const enum hrtimer_mode mode);
要取消一个hrtimer,使用hrtimer_cancel:

int hrtimer_cancel(struct hrtimer *timer);
以下两个函数用于推后定时器的到期时间:

extern u64
hrtimer_forward(struct hrtimer *timer, ktime_t now, ktime_t interval);

/* Forward a hrtimer so it expires after the hrtimer's current now */
static inline u64 hrtimer_forward_now(struct hrtimer *timer,
				      ktime_t interval)
{
	return hrtimer_forward(timer, timer->base->get_time(), interval);
}
以下几个函数用于获取定时器的当前状态:

static inline int hrtimer_active(const struct hrtimer *timer)
{
	return timer->state != HRTIMER_STATE_INACTIVE;
}

static inline int hrtimer_is_queued(struct hrtimer *timer)
{
	return timer->state & HRTIMER_STATE_ENQUEUED;
}

static inline int hrtimer_callback_running(struct hrtimer *timer)
{
	return timer->state & HRTIMER_STATE_CALLBACK;
}
hrtimer_init最终会进入__hrtimer_init函数,该函数的主要目的是初始化hrtimer的base字段,同时初始化作为红黑树的节点的node字段:

static void __hrtimer_init(struct hrtimer *timer, clockid_t clock_id,
			   enum hrtimer_mode mode)
{
	struct hrtimer_cpu_base *cpu_base;
	int base;

	memset(timer, 0, sizeof(struct hrtimer));

	cpu_base = &__raw_get_cpu_var(hrtimer_bases);

	if (clock_id == CLOCK_REALTIME && mode != HRTIMER_MODE_ABS)
		clock_id = CLOCK_MONOTONIC;

	base = hrtimer_clockid_to_base(clock_id);
	timer->base = &cpu_base->clock_base[base];
	timerqueue_init(&timer->node);
        ......
}

hrtimer_start和hrtimer_start_range_ns最终会把实际的工作交由__hrtimer_start_range_ns来完成:

int __hrtimer_start_range_ns(struct hrtimer *timer, ktime_t tim,
		unsigned long delta_ns, const enum hrtimer_mode mode,
		int wakeup)
{
        ......        
        /* 取得hrtimer_clock_base指针 */
        base = lock_hrtimer_base(timer, &flags); 
        /* 如果已经在红黑树中,先移除它: */
        ret = remove_hrtimer(timer, base); ......
        /* 如果是相对时间,则需要加上当前时间,因为内部是使用绝对时间 */
        if (mode & HRTIMER_MODE_REL) {
                tim = ktime_add_safe(tim, new_base->get_time());
                ......
        } 
        /* 设置到期的时间范围 */
        hrtimer_set_expires_range_ns(timer, tim, delta_ns);
        ...... 
        /* 把hrtime按到期时间排序,加入到对应时间基准系统的红黑树中 */
        /* 如果该定时器的是最早到期的,将会返回true */
        leftmost = enqueue_hrtimer(timer, new_base);
        /* 
        * Only allow reprogramming if the new base is on this CPU. 
        * (it might still be on another CPU if the timer was pending) 
        * 
        * XXX send_remote_softirq() ?
        * 定时器比之前的到期时间要早,所以需要重新对tick_device进行编程,重新设定的的到期时间
        */
        if (leftmost && new_base->cpu_base == &__get_cpu_var(hrtimer_bases))
                hrtimer_enqueue_reprogram(timer, new_base, wakeup);
        unlock_hrtimer_base(timer, &flags);
        return ret;
}

2.2  hrtimer的到期处理

高精度定时器系统有3个入口可以对到期定时器进行处理,它们分别是:

  • 没有切换到高精度模式时,在每个jiffie的tick事件中断中进行查询和处理;
  • 在HRTIMER_SOFTIRQ软中断中进行查询和处理;
  • 切换到高精度模式后,在每个clock_event_device的到期事件中断中进行查询和处理;

低精度模式  因为系统并不是一开始就会支持高精度模式,而是在系统启动后的某个阶段,等待所有的条件都满足后,才会切换到高精度模式,当系统还没有切换到高精度模式时,所有的高精度定时器运行在低精度模式下,在每个jiffie的tick事件中断中进行到期定时器的查询和处理,显然这时候的精度和低分辨率定时器是一样的(HZ级别)。低精度模式下,每个tick事件中断中,hrtimer_run_queues函数会被调用,由它完成定时器的到期处理。hrtimer_run_queues首先判断目前高精度模式是否已经启用,如果已经切换到了高精度模式,什么也不做,直接返回:

void hrtimer_run_queues(void)
{

	if (hrtimer_hres_active())
		return;
如果hrtimer_hres_active返回false,说明目前处于低精度模式下,则继续处理,它用一个for循环遍历各个时间基准系统,查询每个hrtimer_clock_base对应红黑树的左下节点,判断它的时间是否到期,如果到期,通过__run_hrtimer函数,对到期定时器进行处理,包括:调用定时器的回调函数、从红黑树中移除该定时器、根据回调函数的返回值决定是否重新启动该定时器等等:

	for (index = 0; index < HRTIMER_MAX_CLOCK_BASES; index++) {
		base = &cpu_base->clock_base[index];
		if (!timerqueue_getnext(&base->active))
			continue;

		if (gettime) {
			hrtimer_get_softirq_time(cpu_base);
			gettime = 0;
		}

		raw_spin_lock(&cpu_base->lock);

		while ((node = timerqueue_getnext(&base->active))) {
			struct hrtimer *timer;

			timer = container_of(node, struct hrtimer, node);
			if (base->softirq_time.tv64 <=
					hrtimer_get_expires_tv64(timer))
				break;

			__run_hrtimer(timer, &base->softirq_time);
		}
		raw_spin_unlock(&cpu_base->lock);
	}
上面的timerqueue_getnext函数返回红黑树中的左下节点,之所以可以在while循环中使用该函数,是因为__run_hrtimer会在移除旧的左下节点时,新的左下节点会被更新到base->active->next字段中,使得循环可以继续执行,直到没有新的到期定时器为止。

高精度模式  切换到高精度模式后,原来给cpu提供tick事件的tick_device(clock_event_device)会被高精度定时器系统接管,它的中断事件回调函数被设置为hrtimer_interrupt,红黑树中最左下的节点的定时器的到期时间被编程到该clock_event_device中,这样每次clock_event_device的中断意味着至少有一个高精度定时器到期。另外,当timekeeper系统中的时间需要修正,或者clock_event_device的到期事件时间被重新编程时,系统会发出HRTIMER_SOFTIRQ软中断,软中断的处理函数run_hrtimer_softirq最终也会调用hrtimer_interrupt函数对到期定时器进行处理,所以在这里我们只要讨论hrtimer_interrupt函数的实现即可。

hrtimer_interrupt函数的前半部分和低精度模式下的hrtimer_run_queues函数完成相同的事情:它用一个for循环遍历各个时间基准系统,查询每个hrtimer_clock_base对应红黑树的左下节点,判断它的时间是否到期,如果到期,通过__run_hrtimer函数,对到期定时器进行处理,所以我们只讨论后半部分,在处理完所有到期定时器后,下一个到期定时器的到期时间保存在变量expires_next中,接下来的工作就是把这个到期时间编程到tick_device中:

void hrtimer_interrupt(struct clock_event_device *dev)
{
        ......
	for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++) {
                ......
		while ((node = timerqueue_getnext(&base->active))) {
                        ......
			if (basenow.tv64 < hrtimer_get_softexpires_tv64(timer)) {
				ktime_t expires;

				expires = ktime_sub(hrtimer_get_expires(timer),
						    base->offset);
				if (expires.tv64 < expires_next.tv64)
					expires_next = expires;
				break;
			}

			__run_hrtimer(timer, &basenow);
		}
	}

	/*
	 * Store the new expiry value so the migration code can verify
	 * against it.
	 */
	cpu_base->expires_next = expires_next;
	raw_spin_unlock(&cpu_base->lock);

	/* Reprogramming necessary ? */
	if (expires_next.tv64 == KTIME_MAX ||
	    !tick_program_event(expires_next, 0)) {
		cpu_base->hang_detected = 0;
		return;
	}
如果这时的tick_program_event返回了非0值,表示过期时间已经在当前时间的前面,这通常由以下原因造成:

  • 系统正在被调试跟踪,导致时间在走,程序不走;
  • 定时器的回调函数花了太长的时间;
  • 系统运行在虚拟机中,而虚拟机被调度导致停止运行;
为了避免这些情况的发生,接下来系统提供3次机会,重新执行前面的循环,处理到期的定时器:

	raw_spin_lock(&cpu_base->lock);
	now = hrtimer_update_base(cpu_base);
	cpu_base->nr_retries++;
	if (++retries < 3)
		goto retry;
如果3次循环后还无法完成到期处理,系统不再循环,转为计算本次总循环的时间,然后把tick_device的到期时间强制设置为当前时间加上本次的总循环时间,不过推后的时间被限制在100ms以内:

	delta = ktime_sub(now, entry_time);
	if (delta.tv64 > cpu_base->max_hang_time.tv64)
		cpu_base->max_hang_time = delta;
	/*
	 * Limit it to a sensible value as we enforce a longer
	 * delay. Give the CPU at least 100ms to catch up.
	 */
	if (delta.tv64 > 100 * NSEC_PER_MSEC)
		expires_next = ktime_add_ns(now, 100 * NSEC_PER_MSEC);
	else
		expires_next = ktime_add(now, delta);
	tick_program_event(expires_next, 1);
	printk_once(KERN_WARNING "hrtimer: interrupt took %llu ns\n",
		    ktime_to_ns(delta));
}

3.  切换到高精度模式

上面提到,尽管内核配置成支持高精度定时器,但并不是一开始就工作于高精度模式,系统在启动的开始阶段,还是按照传统的模式在运行:tick_device按HZ频率定期地产生tick事件,这时的hrtimer工作在低分辨率模式,到期事件在每个tick事件中断中由hrtimer_run_queues函数处理,同时,在低分辨率定时器(时间轮)的软件中断TIMER_SOFTIRQ中,hrtimer_run_pending会被调用,系统在这个函数中判断系统的条件是否满足切换到高精度模式,如果条件满足,则会切换至高分辨率模式,另外提一下,NO_HZ模式也是在该函数中判断并切换。

void hrtimer_run_pending(void)
{
	if (hrtimer_hres_active())
		return;
        ......
	if (tick_check_oneshot_change(!hrtimer_is_hres_enabled()))
		hrtimer_switch_to_hres();
}
因为不管系统是否工作于高精度模式,每个TIMER_SOFTIRQ期间,该函数都会被调用,所以函数一开始先用hrtimer_hres_active判断目前高精度模式是否已经激活,如果已经激活,则说明之前的调用中已经切换了工作模式,不必再次切换,直接返回。hrtimer_hres_active很简单:

DEFINE_PER_CPU(struct hrtimer_cpu_base, hrtimer_bases) = {
        ......
}

static inline int hrtimer_hres_active(void)
{
	return __this_cpu_read(hrtimer_bases.hres_active);
}
hrtimer_run_pending函数接着通过tick_check_oneshot_change判断系统是否可以切换到高精度模式,

int tick_check_oneshot_change(int allow_nohz)
{
	struct tick_sched *ts = &__get_cpu_var(tick_cpu_sched);

	if (!test_and_clear_bit(0, &ts->check_clocks))
		return 0;

	if (ts->nohz_mode != NOHZ_MODE_INACTIVE)
		return 0;

	if (!timekeeping_valid_for_hres() || !tick_is_oneshot_available())
		return 0;

	if (!allow_nohz)
		return 1;

	tick_nohz_switch_to_nohz();
	return 0;
}
函数的一开始先判断check_clock标志的第0位是否被置位,如果没有置位,说明系统中没有注册符合要求的时钟事件设备,函数直接返回,check_clock标志由clocksource和clock_event_device系统的notify系统置位,当系统中有更高精度的clocksource被注册和选择后,或者有更精确的支持CLOCK_EVT_MODE_ONESHOT模式的clock_event_device被注册时,通过它们的notify函数,check_clock标志的第0为会置位。

如果tick_sched结构中的nohz_mode字段不是NOHZ_MODE_INACTIVE,表明系统已经切换到其它模式,直接返回。nohz_mode的取值有3种:

  • NOHZ_MODE_INACTIVE    // 未启用NO_HZ模式
  • NOHZ_MODE_LOWRES    // 启用NO_HZ模式,hrtimer工作于低精度模式下
  • NOHZ_MODE_HIGHRES   // 启用NO_HZ模式,hrtimer工作于高精度模式下
接下来的timerkeeping_valid_for_hres判断timekeeper系统是否支持高精度模式,tick_is_oneshot_available判断tick_device是否支持CLOCK_EVT_MODE_ONESHOT模式。如果都满足要求,则继续往下判断。allow_nohz是函数的参数,为true表明可以切换到NOHZ_MODE_LOWRES 模式,函数将进入tick_nohz_switch_to_nohz,切换至NOHZ_MODE_LOWRES 模式,这里我们传入的allow_nohz是表达式:

(!hrtimer_is_hres_enabled())

所以当系统不允许高精度模式时,将会在tick_check_oneshot_change函数内,通过tick_nohz_switch_to_nohz切换至NOHZ_MODE_LOWRES 模式,如果系统允许高精度模式,传入的allow_nohz参数为false,tick_check_oneshot_change函数返回1,回到上面的hrtimer_run_pending函数,hrtimer_switch_to_hres函数将会被调用,已完成切换到NOHZ_MODE_HIGHRES高精度模式。好啦,真正的切换函数找到了,我们看一看它如何切换:

首先,它通过hrtimer_cpu_base中的hres_active字段判断该cpu是否已经切换至高精度模式,如果是则直接返回:

static int hrtimer_switch_to_hres(void)
{
	int i, cpu = smp_processor_id();
	struct hrtimer_cpu_base *base = &per_cpu(hrtimer_bases, cpu);
	unsigned long flags;

	if (base->hres_active)
		return 1;
接着,通过tick_init_highres函数接管tick_device关联的clock_event_device:

	local_irq_save(flags);

	if (tick_init_highres()) {
		local_irq_restore(flags);
		printk(KERN_WARNING "Could not switch to high resolution "
				    "mode on CPU %d\n", cpu);
		return 0;
	}
tick_init_highres函数把tick_device切换到CLOCK_EVT_FEAT_ONESHOT模式,同时把clock_event_device的回调handler设置为hrtimer_interrupt,这样设置以后,tick_device的中断回调将由hrtimer_interrupt接管,hrtimer_interrupt在上面已经讨论过,它将完成高精度定时器的调度和到期处理。

接着,设置hres_active标志,以表明高精度模式已经切换,然后把3个时间基准系统的resolution字段设为KTIME_HIGH_RES:

	base->hres_active = 1;
	for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++)
		base->clock_base[i].resolution = KTIME_HIGH_RES;
最后,因为tick_device被高精度定时器接管,它将不会再提供原有的tick事件机制,所以需要由高精度定时器系统模拟一个tick事件设备,继续为系统提供tick事件能力,这个工作由tick_setup_sched_timer函数完成。因为刚刚完成切换,tick_device的到期时间并没有被正确地设置为下一个到期定时器的时间,这里使用retrigger_next_event函数,传入参数NULL,使得tick_device立刻产生到期中断,hrtimer_interrupt被调用一次,然后下一个到期的定时器的时间会编程到tick_device中,从而完成了到高精度模式的切换:
	tick_setup_sched_timer();
	/* "Retrigger" the interrupt to get things going */
	retrigger_next_event(NULL);
	local_irq_restore(flags);
	return 1;
}

整个切换过程可以用下图表示:


                                                                             图3.1  低精度模式切换至高精度模式

4.  模拟tick事件

根据上一节的讨论,当系统切换到高精度模式后,tick_device被高精度定时器系统接管,不再定期地产生tick事件,我们知道,到目前的版本为止(V3.4),内核还没有彻底废除jiffies机制,系统还是依赖定期到来的tick事件,供进程调度系统和时间更新等操作,大量存在的低精度定时器也仍然依赖于jiffies的计数,所以,尽管tick_device被接管,高精度定时器系统还是要想办法继续提供定期的tick事件。为了达到这一目的,内核使用了一个取巧的办法:既然高精度模式已经启用,可以定义一个hrtimer,把它的到期时间设定为一个jiffy的时间,当这个hrtimer到期时,在这个hrtimer的到期回调函数中,进行和原来的tick_device同样的操作,然后把该hrtimer的到期时间顺延一个jiffy周期,如此反复循环,完美地模拟了原有tick_device的功能。下面我们看看具体点代码是如何实现的。

在kernel/time/tick-sched.c中,内核定义了一个per_cpu全局变量:tick_cpu_sched,从而为每个cpu提供了一个tick_sched结构, 该结构主要用于管理NO_HZ配置下的tickless处理,因为模拟tick事件与tickless有很强的相关性,所以高精度定时器系统也利用了该结构的以下字段,用于完成模拟tick事件的操作:

struct tick_sched {
	struct hrtimer			sched_timer;
	unsigned long			check_clocks;
	enum tick_nohz_mode		nohz_mode;
        ......
};
sched_timer就是要用于模拟tick事件的hrtimer,check_clock上面几节已经讨论过,用于notify系统通知hrtimer系统需要检查是否切换到高精度模式,nohz_mode则用于表示当前的工作模式。

上一节提到,用于切换至高精度模式的函数是hrtimer_switch_to_hres,在它的最后,调用了函数tick_setup_sched_timer,该函数的作用就是设置一个用于模拟tick事件的hrtimer:

void tick_setup_sched_timer(void)
{
	struct tick_sched *ts = &__get_cpu_var(tick_cpu_sched);
	ktime_t now = ktime_get();

	/*
	 * Emulate tick processing via per-CPU hrtimers:
	 */
	hrtimer_init(&ts->sched_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
	ts->sched_timer.function = tick_sched_timer;

	/* Get the next period (per cpu) */
	hrtimer_set_expires(&ts->sched_timer, tick_init_jiffy_update());

	for (;;) {
		hrtimer_forward(&ts->sched_timer, now, tick_period);
		hrtimer_start_expires(&ts->sched_timer,
				      HRTIMER_MODE_ABS_PINNED);
		/* Check, if the timer was already in the past */
		if (hrtimer_active(&ts->sched_timer))
			break;
		now = ktime_get();
	}

#ifdef CONFIG_NO_HZ
	if (tick_nohz_enabled)
		ts->nohz_mode = NOHZ_MODE_HIGHRES;
#endif
}
该函数首先初始化该cpu所属的tick_sched结构中sched_timer字段,把该hrtimer的回调函数设置为tick_sched_timer,然后把它的到期时间设定为下一个jiffy时刻,返回前把工作模式设置为NOHZ_MODE_HIGHRES,表明是利用高精度模式实现NO_HZ。

接着我们关注一下hrtimer的回调函数tick_sched_timer,我们知道,系统中的jiffies计数,时间更新等是全局操作,在smp系统中,只有一个cpu负责该工作,所以在tick_sched_timer的一开始,先判断当前cpu是否负责更新jiffies和时间,如果是,则执行更新操作:

static enum hrtimer_restart tick_sched_timer(struct hrtimer *timer)
{
        ......

#ifdef CONFIG_NO_HZ
	if (unlikely(tick_do_timer_cpu == TICK_DO_TIMER_NONE))
		tick_do_timer_cpu = cpu;
#endif

	/* Check, if the jiffies need an update */
	if (tick_do_timer_cpu == cpu)
		tick_do_update_jiffies64(now);
然后,利用regs指针确保当前是在中断上下文中,然后调用update_process_timer:

	if (regs) {
                ......
		update_process_times(user_mode(regs));
		......
	}
最后,把hrtimer的到期时间推进一个tick周期,返回HRTIMER_RESTART表明该hrtimer需要再次启动,以便产生下一个tick事件。

	hrtimer_forward(timer, now, tick_period);

	return HRTIMER_RESTART;
}
关于update_process_times,如果你你感兴趣,回看一下本系列关于clock_event_device的那一章:Linux时间子系统之四:定时器的引擎:clock_event_device中的第5小节,对比一下模拟tick事件的hrtimer的回调函数tick_sched_timer和切换前tick_device的回调函数tick_handle_periodic,它们是如此地相像,实际上,它们几乎完成了一样的工作。

没有更多推荐了,返回首页