OS近距離：Linux的時間，可能并不像你想的那么可靠！
如果你想周期性的做一些事情，那么必然，會與時間產生聯系。比如，每天早晨7點吃早餐，每天晚上10點進入夢鄉。當然，如果你有伴侶的話，晚上這個時間可能不會這么固定。
計算機對時間的控制比人的感覺更加準確一些，但我們依然難以做到絕對精確的調度，這涉及到了終極的哲學問題。了解問題產生的原因，比問題本身的現象更加有難度，下面我們就來聊一下這個問題。
假設，我有一個任務，要求每60秒執行一次，你要如何設計?
很多Javaer會自然的想到Timer和ScheduledExecutorService，不過，這也只能說明你了解一些API而已，在絕對精度的調度面前，它們都不能滿足需求。
一個例子
下面這段代碼，將開啟一個5秒間隔的執行器，然后記錄實際的間隔時間和期望的偏移量。
public class Main {
private static ScheduledExecutorService schedule = Executors.newScheduledThreadPool(1);
private static LinkedBlockingDeque<Long> q = new LinkedBlockingDeque<>();
public static void main(String[] args) {
final long rateNano = TimeUnit.SECONDS.toNanos(5);
final Random r = new Random();
final AtomicLong offset = new AtomicLong(0);
final AtomicLong max = new AtomicLong(0);
schedule.scheduleAtFixedRate(()->{
try {
long eventTime = System.nanoTime();
long nanoOffset = q.size() == 0 ? rateNano : (eventTime - q.pollLast());
offset.addAndGet(nanoOffset);
offset.addAndGet(-rateNano);
max.set(Math.max(max.get(), Math.abs(offset.get())));
System.out.println(TimeUnit.NANOSECONDS.toSeconds(eventTime)+ "(s) #"
+ nanoOffset + "(us),"
+ offset.get() + "(us),"
+ max.get() + "(us)"
);
q.offer(eventTime);
Thread.sleep(r.nextInt(500));
} catch (InterruptedException e) {
e.printStackTrace();
}
}, 0, rateNano, TimeUnit.NANOSECONDS);
}
}
我們把時間細分一下，然后打印每個間隔之間的秒數和納秒數，你將發現一些不同尋常的東西。
978048(s) #4996295958(us),-688459(us),57185541(us)
978053(s) #5002982917(us),2294458(us),57185541(us)
978058(s) #5000489208(us),2783666(us),57185541(us)
978063(s) #4997937167(us),720833(us),57185541(us)
978068(s) #5002287042(us),3007875(us),57185541(us)
978073(s) #4999411375(us),2419250(us),57185541(us)
可以看到，秒數是以5秒5秒的速度增長，但實際的執行時間，如果放大到納秒，它表現出很沒有規律的分布。
為了得到較為可信的數據，實際上，我把這個任務跑了1天，到最后，整個偏移量最大達了57ms。
先不談Java線程的調度，在操作系統上有誤差。就拿操作系統本身來說，由于有虛擬內存、線程池、各種驅動的存在，我們常用的Windows和Linux，都不是實時操作系統。
其主要等待方法，就是在DelayedWorkQueue的take方法里，使用了ConditionObject的awaitNanos方法。
再往下找的話，那就是LockSupport的parkNanos方法。繼續向下跟，那就是unsafe，本質上是一個native函數。
public native void park(boolean isAbsolute, long time);
第一個參數是是否是絕對時間，第二個參數是等待時間值。如果isAbsolute是true則會實現毫秒定時。如果isAbsolute是false則會實現納秒定時。納秒，可以說是精度很高了。
在jdk源碼中，我們找到了具體的native函數。就拿linux來說，文件就躺在./os/posix/os_posix.cpp，最終就是調用pthread_cond_timedwait。
所有的編程都是面向glibc編程，沒跑了。
pthread_cond_timedwait
一般來說，平臺會提供sleep、pthread_cond_wait、pthread_cond_timedwait等函數供用戶使用，實現線程的等待和喚醒。
其中pthread_cond_timedwait就是使用最廣泛的那一枚。通過使用perf記錄堆棧調用，我們可以看到大體的函數調用棧。
javac Main
java Main
ps -ef| grep java
perf record -g -a -p 2019961
perf report
對于了解Linux內部運行原理的同學來說，通過上面的函數調用，就可以看出這里主要是使用了Linux的futex機制，而futex的兩個主要方法就是futex_wait和futex_wake。
我們先不管這些亂七八糟的同步術語和函數的版本差異，在kernel/futex/waitwake.c (Linux-5.16.12)中，我們能夠看到相關的函數調用。
所謂的等待計數器，就是在下面這段代碼中設置的。
struct hrtimer_sleeper *
futex_setup_timer(ktime_t *time, struct hrtimer_sleeper *timeout,
int flags, u64 range_ns)
{
if (!time)
return NULL;
hrtimer_init_sleeper_on_stack(timeout, (flags & FLAGS_CLOCKRT) ?
CLOCK_REALTIME : CLOCK_MONOTONIC,
HRTIMER_MODE_ABS);
/*
* If range_ns is 0, calling hrtimer_set_expires_range_ns() is
* effectively the same as calling hrtimer_set_expires().
*/
hrtimer_set_expires_range_ns(&timeout->timer, *time, range_ns);
return timeout;
}
時間輪
所以問題終于聚焦到我們本文的主題上了。
hrtimers，是Linux下一個高分辨率的定時器。hrtimer結構(也就是上面代碼的&timeout->timer)，其中有一個function參數，會接受一個回調函數，在定時器觸發時，將會被調用。
在聊高分辨率的定時器之前，得首先聊一下低分辨率的定時器。在早期的Linux版本中，定時器是基于CPU的HZ來實現的，也就是tick周期。
很明顯的，這個tick的周期的最小值，就是1/CPU主頻。不過現在的CPU主頻都是GHz來算了，所以精度相對來說還不錯，能達到納秒級別。
1GHz=1000MHz，1MHz=1000kHz，1kHz=1000Hz
一個jiffy = 1/HZ
低分辨率的定時器，還有一個非常著名的時間輪算法，將定時任務散列在長度有限的環形數組中。然后，在此基礎上再參考日常生活中水表的方式，通過低刻度走得快的輪子帶動高一級刻度輪子走動的方法，像齒輪一樣帶動更高級別的齒輪，這樣就可以避免輪子過大的問題。
其實這個也很好理解。假如我們把1天的時間，每一秒都刻在鐘表上，需要86400個刻度。但其實，我們的鐘表只需要60個刻度就能完成一天的循環。
Linux的定時器，將時間輪分為了9層，可以說精度很高了。
#define WHEEL_SIZE (LVL_SIZE * LVL_DEPTH)
/* Level depth */
#if HZ > 100
# define LVL_DEPTH 9
# else
# define LVL_DEPTH 8
#endif
這些細節很多，我們抽另外的文章講解，別忘了關注xjjdog。
hrtimer
相比較低精度(也不算低了)的時間輪設計，hrtimer又做了哪些，才稱之為高精度呢?
組織hrtimer的，其實是一棵紅黑樹(timerqueue_node)，這是在比較了hash、跳表、堆等數據結構基礎上的最終選擇。高精度的代碼幾乎全是重寫的，大多數能夠實現O(1)時間復雜度的操作。
高精度定時器的主要任務，不是實現時間片上的精度，而是在執行增刪改查的時候，能夠提供穩定、快速的功能。即使是排序，也應該盡量的減少時間耗費，因為調度代碼執行時間的不穩定，同樣會影響整個調度系統的穩定性。
timerqueue_head結構在紅黑樹的基礎上，增加了一個next字段，用于保存樹中最先到期的定時器節點，算是對紅黑樹小小的改造。這些改造在效率上都是立竿見影的，效果就像B+ Tree對B Tree的改造一樣。
從下面這些結構體，可以大體看出紅黑樹的組織方式。
struct timerqueue_node {
struct rb_node node;
ktime_t expires;
};
struct timerqueue_head {
struct rb_root_cached rb_root;
};
struct rb_root_cached {
struct rb_root rb_root;
struct rb_node *rb_leftmost;
};
struct rb_node {
unsigned long __rb_parent_color;
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
我們再來看一下hrtimer的結構體，發現里面有一個_softexpires，同時，它的成員變量node里，也有一個叫做expires的變量。
struct hrtimer {
struct timerqueue_node node;
ktime_t _softexpires;
enum hrtimer_restart (*function)(struct hrtimer *);
struct hrtimer_clock_base *base;
u8 state;
u8 is_rel;
u8 is_soft;
u8 is_hard;
};
這是hrtimer為了增加調度的效率所做的一些妥協。它表示，我們的任務，可以在_softexpires和expires之間的任何時刻到期。expires被稱作硬到期時間，是任務到期的最后時間。有了這樣的設計，就可以避免進程被hrtimer頻繁的喚醒，減少contextswitch。
我們可以從perf得到的hrtimer_set_expires_range_ns函數中窺探到這兩個時間點的設定。這本質上也是一種對時間齊功能。
static inline void hrtimer_set_expires_range_ns(struct hrtimer *timer, ktime_t time, u64 delta)
{
timer->_softexpires = time;
timer->node.expires = ktime_add_safe(time, ns_to_ktime(delta));
}
delta的設定非常有意思，在不同的硬件設備上，它的值都不同，表示最小的調度精度。這也是我們最上面的Java程序，在執行的時候，引起時間抖動的根本原因。
End
聊到這里，我想你應該能夠想到，世界上根本就沒有準確的調度。只不過隨著主頻的增加，我們可以將精度控制在一定范圍內。
且不說時間本身準不準，僅僅是這時間片的細分，就使得目前的PC機，在微觀世界上的時間誤差將變的無比巨大，進行高頻率的的精度調度幾乎是不可能完成的事。
世界上最準的鐘表，每150億年才會減少一秒。但1秒也是時間，我們依然能夠用語言表達出來。糾結準實時性是一個永遠沒有盡頭的答案，除非我們能夠操縱原子。再加上任務調度代碼本身耗時的不確定性，目前的調度器維持在納秒精度，已經算是一個奇跡。
世界本身就是人粗略的觀測，何況是人所造出的機器呢。
作者簡介：小姐姐味道 (xjjdog)，一個不允許程序員走彎路的公眾號。聚焦基礎架構和Linux。十年架構，日百億流量，與你探討高并發世界，給你不一樣的味道。我的個人微信xjjdog0，歡迎添加好友，進一步交流。
