定時(shí)器的實(shí)現(xiàn)原理

定時(shí)器的實(shí)現(xiàn)依賴的是CPU時(shí)鐘中斷，時(shí)鐘中斷的精度就決定定時(shí)器精度的極限。一個(gè)時(shí)鐘中斷源如何實(shí)現(xiàn)多個(gè)定時(shí)器呢？對(duì)于內(nèi)核，簡單來說就是用特定的數(shù)據(jù)結(jié)構(gòu)管理眾多的定時(shí)器，在時(shí)鐘中斷處理中判斷哪些定時(shí)器超時(shí)，然后執(zhí)行超時(shí)處理動(dòng)作。而用戶空間程序不直接感知CPU時(shí)鐘中斷，通過感知內(nèi)核的信號(hào)、IO事件、調(diào)度，間接依賴時(shí)鐘中斷。用軟件來實(shí)現(xiàn)動(dòng)態(tài)定時(shí)器常用數(shù)據(jù)結(jié)構(gòu)有：時(shí)間輪、最小堆和紅黑樹。

海量定時(shí)任務(wù) 、定時(shí)器設(shè)計(jì) 、 時(shí)間輪實(shí)現(xiàn)以及應(yīng)用精講

現(xiàn)場手撕定時(shí)器實(shí)現(xiàn)、 定時(shí)器實(shí)現(xiàn)方案（單線程、多線程）

Linux內(nèi)核定時(shí)器相關(guān)(Linux v4.9.7, x86體系架構(gòu))的一些相關(guān)代碼：

內(nèi)核啟動(dòng)注冊時(shí)鐘中斷

內(nèi)核時(shí)鐘中斷處理流程

內(nèi)核定時(shí)器時(shí)間輪算法

單層時(shí)間輪算法的原理比較簡單：用一個(gè)數(shù)組表示時(shí)間輪，每個(gè)時(shí)鐘周期，時(shí)間輪 current 往后走一個(gè)格，并處理掛在這個(gè)格子的定時(shí)器鏈表，如果超時(shí)則進(jìn)行超時(shí)動(dòng)作處理，然后刪除定時(shí)器，沒有則剩余輪數(shù)減一。原理如圖：

Linux 內(nèi)核則采用的是 Hierarchy 時(shí)間輪算法，Hierarchy 時(shí)間輪將單一的 bucket 數(shù)組分成了幾個(gè)不同的數(shù)組，每個(gè)數(shù)組表示不同的時(shí)間精度，Linux 內(nèi)核中用 jiffies 記錄時(shí)間，jiffies記錄了系統(tǒng)啟動(dòng)以來經(jīng)過了多少tick。下面是Linux 4.9的一些代碼：

Hierarchy 時(shí)間輪的原理大致如下，下面是一個(gè)時(shí)分秒的Hierarchy時(shí)間輪，不同于Linux內(nèi)核的實(shí)現(xiàn)，但原理類似。對(duì)于時(shí)分秒三級(jí)時(shí)間輪，每個(gè)時(shí)間輪都維護(hù)一個(gè)cursor，新建一個(gè)timer時(shí)，要掛在合適的格子，剩余輪數(shù)以及時(shí)間都要記錄，到期判斷超時(shí)并調(diào)整位置。原理圖大致如下:

定時(shí)器的使用方法

在Linux 用戶空間程序開發(fā)中，常用的定期器可以分為兩類：

1. 執(zhí)行一次的單次定時(shí)器 single-short；

2. 循環(huán)執(zhí)行的周期定時(shí)器 Repeating Timer；

其中，Repeating Timer 可以通過在 Single-Shot Timer 終止之后，重新再注冊到定時(shí)器系統(tǒng)里來實(shí)現(xiàn)。當(dāng)一個(gè)進(jìn)程需要使用大量定時(shí)器時(shí)，同樣利用時(shí)間輪、最小堆或紅黑樹等結(jié)構(gòu)來管理定時(shí)器。而時(shí)鐘周期來源則需要借助系統(tǒng)調(diào)用，最終還是從時(shí)鐘中斷。Linux 用戶空間程序的定時(shí)器可用下面方法來實(shí)現(xiàn)：

• 通過?alarm()?或?setitimer()?系統(tǒng)調(diào)用，非阻塞異步，配合?SIGALRM?信號(hào)處理；

• 通過?select()?或?nanosleep()?系統(tǒng)調(diào)用，阻塞調(diào)用，往往需要新建一個(gè)線程；

• 通過?timefd()?調(diào)用，基于文件描述符，可以被用于?select/poll?的應(yīng)用場景；

• 通過?RTC?機(jī)制, 利用系統(tǒng)硬件提供的?Real Time Clock?機(jī)制, 計(jì)時(shí)非常精確；

上面方法沒提 sleep()，因?yàn)?Linux 中并沒有系統(tǒng)調(diào)用 sleep()，sleep() 是在庫函數(shù)中實(shí)現(xiàn)，是通過調(diào)用 alarm() 來設(shè)定報(bào)警時(shí)間，調(diào)用 sigsuspend() 將進(jìn)程掛起在信號(hào) SIGALARM 上，而且 sleep() 也只能精確到秒級(jí)上，精度不行。當(dāng)使用阻塞調(diào)用作為定時(shí)周期來源時(shí)，可以單獨(dú)啟一個(gè)線程用來管理所有定時(shí)器，當(dāng)定時(shí)器超時(shí)的時(shí)候，向業(yè)務(wù)線程發(fā)送定時(shí)器消息即可。

一個(gè)基于時(shí)間輪的定時(shí)器簡單實(shí)現(xiàn)

在實(shí)際項(xiàng)目中，一個(gè)常用的做法是新起一個(gè)線程，專門管理定時(shí)器，定時(shí)來源使用 rtc、select 等比較精確的來源，定時(shí)器超時(shí)后向主要的 work 線程發(fā)消息即可，或者使用 timefd 接口。

LinuxC/C++服務(wù)器開發(fā)/架構(gòu)師 面試題、學(xué)習(xí)資料、教學(xué)視頻和學(xué)習(xí)路線圖（資料包括C/C++，Linux，golang技術(shù)，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協(xié)程，DPDK，ffmpeg等），免費(fèi)分享有需要的可以自行添加
學(xué)習(xí)交流群960994558