日常知識點之遺留問題梳理（定時器/時間輪定時器）

1：簡單基礎

定時器的核心知識點，對我來說就是獲取當前時間和設置回調函數。

簡單練習：

? c語言通過gettimeofday 獲取當前時間并進行處理

? 回調函數的定義（函數參數有必要適當存儲） typedef void(Timerfunc)(void p);

1.1 簡單源碼演示

#include <stdio.h>
#include <sys/time.h>
#include <unistd.h> //sleep
typedef unsigned long int uint64_t;
static uint64_t GetCurrentTime()
{struct timeval tv;gettimeofday(&tv, NULL);return tv.tv_sec * 1000 + tv.tv_usec / 1000;
}void callback(void * p)
{int * i = (int *)p;printf("callback %d\n", *i);
}int main()
{uint64_t mytest = 1;printf("%lu \n", GetCurrentTime());sleep(2);struct timeval tv;gettimeofday(&tv, NULL);printf("second: %ld\n", tv.tv_sec); // 秒printf("millisecond: %ld\n", tv.tv_sec * 1000 + tv.tv_usec / 1000); // 毫秒printf("microsecond: %ld\n", tv.tv_sec * 1000000 + tv.tv_usec); // 徽秒sleep(3); // 讓程序休眠3秒printf("---------------------sleep 3 second-------------------\n");gettimeofday(&tv, NULL);printf("second: %ld\n", tv.tv_sec); // 秒printf("millisecond: %ld\n", tv.tv_sec * 1000 + tv.tv_usec / 1000); // 毫秒printf("microsecond: %ld\n", tv.tv_sec * 1000000 + tv.tv_usec); // 徽秒
//回調函數的簡單定義和使用typedef void(*Timerfunc)(void* p);int func_para = 3;Timerfunc m_func = callback;void * para = (void*)&func_para;(*m_func)(para);return 0;
}

1.2 ：運行結果

root@aliy:/home/leetcode# ./get_time1 
1739506868441 
second: 1739506870
millisecond: 1739506870441
microsecond: 1739506870441927
---------------------sleep 3 second-------------------
second: 1739506873
millisecond: 1739506873442
microsecond: 1739506873442060
callback 3

2：借助已有的stl容器實現是最方便的

不知道哪里參考的一個代碼，借助了stl中的一個優先級隊列，就簡單整理一下吧。

回顧好久沒寫的細節：

0：優先級隊列 priority_queue 支持大堆小堆（自己定義比較函數）

1：鎖和條件變量條件變量的幾種信號等待方式。

2：chrono下的相關獲取時間的接口需要梳理一下。

3：std::function 和lamba需要回顧練習一下

4：stl的push時可以直接構造結構體對象，task_queue.push(Task{func, exec_time});

5：條件變量中的wait 以及wait_until

? ====》已經有喚醒 wait用條件等待防止虛假喚醒

? ====》wait_until 接口可以實現等待到特定時間后進行執行（系統調用內部定時器實現？會虛假喚醒嗎？）。和自己代碼實現時間差同功能

在這里插入圖片描述

2.1：練習源碼

都是C++11的東東需要回顧。

//定時器的簡單實現  借助stl容器，使用線程進行專門的定時器處理。//容器中保存了定時器的超時時間，以及對應的回調函數 
#include <stdio.h>
#include <iostream>
#include <functional>
#include <mutex>
#include <thread>
#include <chrono>
#include <vector>
#include <condition_variable>
#include <atomic>
#include <queue>class Timer{
private:std::thread worker;std::atomic<bool> stop;//鎖和條件變量std::mutex queue_mutex;std::condition_variable condition;struct Task{std::function<void(void)> func;//std::chrono::steady_clock 只能增加的單調時鐘  std::chrono::time_point表示某一刻的對象//這里時間的相關接口需要參考chronostd::chrono::time_point<std::chrono::steady_clock> exec_time;  //為了給wait_until做參數 直接指定bool operator >(const Task & other) const{return exec_time > other.exec_time;}};//優先隊列  用task為元素類型  以std::vector<Task> 進行存儲 按照默認的比較函數進行比較  實現最小堆std::priority_queue<Task, std::vector<Task>, std::greater<Task>> task_queue; //底層是堆的結構private:void run(){while(!stop){//這里進行死循環 或者加鎖條件變量實現隊列中任務的提取if(task_queue.empty()){std::unique_lock<std::mutex> lock(queue_mutex);//防止虛假喚醒condition.wait(lock, [this] {return !this->task_queue.empty() || this->stop;});//這里無法訪問類的成員變量 如何函數內部或者全局變量 即可以// condition.wait(lock, [] {//     return !task_queue.empty() || stop;// });}	if(task_queue.empty() || stop){return;}{// auto now  = std::chrono::steady_clock::now();auto exec_task_time = task_queue.top().exec_time; //目標執行的時間std::unique_lock<std::mutex> lock(queue_mutex);//注意第二個參數 是當前時間加上最大等待時間 if(condition.wait_until(lock, exec_task_time) == std::cv_status::timeout){auto task = task_queue.top();task_queue.pop();lock.unlock();task.func(); //這里沒有定義參數  可以定義參數為自己}}}}public:Timer():stop(false), worker(&Timer::run, this){}~Timer(){ //單例時才把構造函數析構函數設置為私有stop = true;condition.notify_all();worker.join();}static inline time_t get_Clock(){// 獲取當前時間點auto now = std::chrono::steady_clock::now();// 獲取從紀元到現在所經過的持續時間auto duration = now.time_since_epoch();//轉換為毫秒并返回return std::chrono::duration_cast<std::chrono::milliseconds>(duration).count();}void schedule(const std::function<void()> &func, int delay_ms){auto exec_time = std::chrono::steady_clock::now() +std::chrono::milliseconds(delay_ms);{std::unique_lock<std::mutex> lock(queue_mutex);task_queue.push(Task{func, exec_time}); //注意這里的細節}condition.notify_all();}
};int main()
{Timer timer;printf("now =   %lu \n", Timer::get_Clock());timer.schedule([](){printf("exec 1000  %lu \n", Timer::get_Clock());}, 1000);timer.schedule([](){printf("exec 3000  %lu \n", Timer::get_Clock());}, 3000);std::this_thread::sleep_for(std::chrono::seconds(5));return 0;
}

2.2 ：運行結果

oot@aliy:/home/leetcode# g++ my_timer1.c -o my_timer -std=c++11
root@aliy:/home/leetcode# ./my_timer 
now =   16306525752 
exec 1000  16306526753 
exec 3000  16306528753

3：總結一些其他遺留

定時器的實現中，往往需要數據結構配合。（時間戳和回調需要支持排序需要方便插入）

1：紅黑樹存儲數據結構比如set map mutilset mutilmap 以及nginx下封裝的紅黑樹。

2：使用最小堆進行存儲。

3：跳表（有序，可以快速插入參考redis中的跳表源碼）/時間輪定時器。

3.1：時間輪定時器

在這里插入圖片描述

3.2：一個來自別人的demo代碼練習

在這里插入圖片描述

std::vector 模擬數據結構

這樣設計有最大超時時間限制吧，然后輪詢也有精度。

存儲的是節點指針，增加引用計數實現多次執行，類型心跳

//時間輪定時器  采用（數組+鏈表）鏈表結合vector的方式存儲數據結構   采用輪詢的方式處理事件#include <unistd.h>
#include <iostream>
#include <vector>
#include <list>
using namespace std;#include <sys/time.h>//同一個指針對象 多次加入只是引用計數增加  執行次數增加。
class CTimerNode {
public:CTimerNode(int fd) : id(fd), ref(0) {}void Offline() {this->ref = 0;}//通過引用計數的方式  確定是否銷毀該對象  加入時++  消費時--  //可能多次加入定時器 bool TryKill() {if (this->ref == 0) return true;DecrRef();if (this->ref == 0) {cout << id << " is killed down" << endl;return true;}cout << id << " ref is " << ref << endl;return false;}void IncrRef() {this->ref++;}protected:void DecrRef() {this->ref--;}private:int ref;int id;
};const int TW_SIZE = 16;
const int EXPIRE = 10;
const int TW_MASK = TW_SIZE - 1;
static size_t iRealTick = 0;
//鏈表的節點
typedef list<CTimerNode*> TimeList;
typedef TimeList::iterator TimeListIter;
//用vector+list 構造時間輪數據結構 
typedef vector<TimeList> TimeWheel;void AddTimeout(TimeWheel &tw, CTimerNode *p) {if (p) {p->IncrRef();TimeList &le = tw[(iRealTick+EXPIRE) & TW_MASK]; //基于當前的時間  放入對應的list中  le.push_back(p);}
}// 用來表示delay時間后調用 
void AddTimeoutDelay(TimeWheel &tw, CTimerNode *p, size_t delay) {if (p) {p->IncrRef();TimeList &le = tw[(iRealTick+EXPIRE+delay) & TW_MASK];le.push_back(p);}
}//命中 
void TimerShift(TimeWheel &tw)
{size_t tick = iRealTick;iRealTick++;TimeList &le = tw[tick & TW_MASK];  //每次向前走一個//循環遍歷輪子 消費輪子中的第一個節點對應的list中的所有事件TimeListIter iter = le.begin();for (; iter != le.end();iter++) {CTimerNode *p = *iter;if (p && p->TryKill()) {delete p;}}le.clear();
}static time_t current_time() {time_t t;struct timeval tv;gettimeofday(&tv, NULL);t = (time_t)tv.tv_sec;return t; //這里返回的是秒
}int main ()
{TimeWheel tw(TW_SIZE);CTimerNode *p = new CTimerNode(10001);AddTimeout(tw, p); //加入時間輪定時器中AddTimeoutDelay(tw, p, 5);  //對象已經存在  5s后執行對應的回調time_t start = current_time();for (;;) {time_t now = current_time();//這里以秒為單位   進行依次命中輪詢if (now - start > 0) {for (int i=0; i<now-start; i++)TimerShift(tw);start = now;cout << "check timer shift " << iRealTick <<  endl;}usleep(2500); //2500 微妙  =2.5ms}return 0;
}

3.3 :demo運行

同一個TimerNode節點，只是把指針加入了時間輪中。

每次處理節點時根據引用計數進行判斷了。

root@aliy:/home/leetcode# ./wheel_timer 
check timer shift 1
check timer shift 2
check timer shift 3
check timer shift 4
check timer shift 5
check timer shift 6
check timer shift 7
check timer shift 8
check timer shift 9
check timer shift 10
10001 ref is 1
check timer shift 11
check timer shift 12
check timer shift 13
check timer shift 14
check timer shift 15
10001 is killed down