如果你想周期性的做一些事情，那么必然，會(huì)與時(shí)間產(chǎn)生聯(lián)系。比如，每天早晨7點(diǎn)吃早餐，每天晚上10點(diǎn)進(jìn)入夢(mèng)鄉(xiāng)。當(dāng)然，如果你有伴侶的話，晚上這個(gè)時(shí)間可能不會(huì)這么固定。

計(jì)算機(jī)對(duì)時(shí)間的控制比人的感覺更加準(zhǔn)確一些，但我們依然難以做到絕對(duì)精確的調(diào)度，這涉及到了終極的哲學(xué)問題。了解問題產(chǎn)生的原因，比問題本身的現(xiàn)象更加有難度，下面我們就來聊一下這個(gè)問題。

假設(shè)，我有一個(gè)任務(wù)，要求每60秒執(zhí)行一次，你要如何設(shè)計(jì)?

很多Javaer會(huì)自然的想到Timer和ScheduledExecutorService，不過，這也只能說明你了解一些API而已，在絕對(duì)精度的調(diào)度面前，它們都不能滿足需求。

一個(gè)例子

下面這段代碼，將開啟一個(gè)5秒間隔的執(zhí)行器，然后記錄實(shí)際的間隔時(shí)間和期望的偏移量。

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);
    }
}

我們把時(shí)間細(xì)分一下，然后打印每個(gè)間隔之間的秒數(shù)和納秒數(shù)，你將發(fā)現(xiàn)一些不同尋常的東西。

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)

可以看到，秒數(shù)是以5秒5秒的速度增長，但實(shí)際的執(zhí)行時(shí)間，如果放大到納秒，它表現(xiàn)出很沒有規(guī)律的分布。

為了得到較為可信的數(shù)據(jù)，實(shí)際上，我把這個(gè)任務(wù)跑了1天，到最后，整個(gè)偏移量最大達(dá)了57ms。

先不談Java線程的調(diào)度，在操作系統(tǒng)上有誤差。就拿操作系統(tǒng)本身來說，由于有虛擬內(nèi)存、線程池、各種驅(qū)動(dòng)的存在，我們常用的Windows和Linux，都不是實(shí)時(shí)操作系統(tǒng)。

其主要等待方法，就是在DelayedWorkQueue的take方法里，使用了ConditionObject的awaitNanos方法。

再往下找的話，那就是LockSupport的parkNanos方法。繼續(xù)向下跟，那就是unsafe，本質(zhì)上是一個(gè)native函數(shù)。

public native void park(boolean isAbsolute, long time);

第一個(gè)參數(shù)是是否是絕對(duì)時(shí)間，第二個(gè)參數(shù)是等待時(shí)間值。如果isAbsolute是true則會(huì)實(shí)現(xiàn)毫秒定時(shí)。如果isAbsolute是false則會(huì)實(shí)現(xiàn)納秒定時(shí)。納秒，可以說是精度很高了。

在jdk源碼中，我們找到了具體的native函數(shù)。就拿linux來說，文件就躺在./os/posix/os_posix.cpp，最終就是調(diào)用pthread_cond_timedwait。

所有的編程都是面向glibc編程，沒跑了。

pthread_cond_timedwait

一般來說，平臺(tái)會(huì)提供sleep、pthread_cond_wait、pthread_cond_timedwait等函數(shù)供用戶使用，實(shí)現(xiàn)線程的等待和喚醒。

其中pthread_cond_timedwait就是使用最廣泛的那一枚。通過使用perf記錄堆棧調(diào)用，我們可以看到大體的函數(shù)調(diào)用棧。

javac Main
java Main
ps -ef| grep java
perf record -g -a  -p 2019961
perf report

對(duì)于了解Linux內(nèi)部運(yùn)行原理的同學(xué)來說，通過上面的函數(shù)調(diào)用，就可以看出這里主要是使用了Linux的futex機(jī)制，而futex的兩個(gè)主要方法就是futex_wait和futex_wake。

我們先不管這些亂七八糟的同步術(shù)語和函數(shù)的版本差異，在kernel/futex/waitwake.c (Linux-5.16.12)中，我們能夠看到相關(guān)的函數(shù)調(diào)用。

所謂的等待計(jì)數(shù)器，就是在下面這段代碼中設(shè)置的。

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;
}

時(shí)間輪

所以問題終于聚焦到我們本文的主題上了。

hrtimers，是Linux下一個(gè)高分辨率的定時(shí)器。hrtimer結(jié)構(gòu)(也就是上面代碼的&timeout->timer)，其中有一個(gè)function參數(shù)，會(huì)接受一個(gè)回調(diào)函數(shù)，在定時(shí)器觸發(fā)時(shí)，將會(huì)被調(diào)用。

在聊高分辨率的定時(shí)器之前，得首先聊一下低分辨率的定時(shí)器。在早期的Linux版本中，定時(shí)器是基于CPU的HZ來實(shí)現(xiàn)的，也就是tick周期。

很明顯的，這個(gè)tick的周期的最小值，就是1/CPU主頻。不過現(xiàn)在的CPU主頻都是GHz來算了，所以精度相對(duì)來說還不錯(cuò)，能達(dá)到納秒級(jí)別。

1GHz=1000MHz，1MHz=1000kHz，1kHz=1000Hz

一個(gè)jiffy = 1/HZ

低分辨率的定時(shí)器，還有一個(gè)非常著名的時(shí)間輪算法，將定時(shí)任務(wù)散列在長度有限的環(huán)形數(shù)組中。然后，在此基礎(chǔ)上再參考日常生活中水表的方式，通過低刻度走得快的輪子帶動(dòng)高一級(jí)刻度輪子走動(dòng)的方法，像齒輪一樣帶動(dòng)更高級(jí)別的齒輪，這樣就可以避免輪子過大的問題。

其實(shí)這個(gè)也很好理解。假如我們把1天的時(shí)間，每一秒都刻在鐘表上，需要86400個(gè)刻度。但其實(shí)，我們的鐘表只需要60個(gè)刻度就能完成一天的循環(huán)。

Linux的定時(shí)器，將時(shí)間輪分為了9層，可以說精度很高了。

#define WHEEL_SIZE (LVL_SIZE * LVL_DEPTH)

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

這些細(xì)節(jié)很多，我們抽另外的文章講解，別忘了關(guān)注xjjdog。

hrtimer

相比較低精度(也不算低了)的時(shí)間輪設(shè)計(jì)，hrtimer又做了哪些，才稱之為高精度呢?

組織hrtimer的，其實(shí)是一棵紅黑樹(timerqueue_node)，這是在比較了hash、跳表、堆等數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上的最終選擇。高精度的代碼幾乎全是重寫的，大多數(shù)能夠?qū)崿F(xiàn)O(1)時(shí)間復(fù)雜度的操作。

高精度定時(shí)器的主要任務(wù)，不是實(shí)現(xiàn)時(shí)間片上的精度，而是在執(zhí)行增刪改查的時(shí)候，能夠提供穩(wěn)定、快速的功能。即使是排序，也應(yīng)該盡量的減少時(shí)間耗費(fèi)，因?yàn)檎{(diào)度代碼執(zhí)行時(shí)間的不穩(wěn)定，同樣會(huì)影響整個(gè)調(diào)度系統(tǒng)的穩(wěn)定性。

timerqueue_head結(jié)構(gòu)在紅黑樹的基礎(chǔ)上，增加了一個(gè)next字段，用于保存樹中最先到期的定時(shí)器節(jié)點(diǎn)，算是對(duì)紅黑樹小小的改造。這些改造在效率上都是立竿見影的，效果就像B+ Tree對(duì)B Tree的改造一樣。

從下面這些結(jié)構(gòu)體，可以大體看出紅黑樹的組織方式。

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))));

我們?cè)賮砜匆幌耯rtimer的結(jié)構(gòu)體，發(fā)現(xiàn)里面有一個(gè)_softexpires，同時(shí)，它的成員變量node里，也有一個(gè)叫做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為了增加調(diào)度的效率所做的一些妥協(xié)。它表示，我們的任務(wù)，可以在_softexpires和expires之間的任何時(shí)刻到期。expires被稱作硬到期時(shí)間，是任務(wù)到期的最后時(shí)間。有了這樣的設(shè)計(jì)，就可以避免進(jìn)程被hrtimer頻繁的喚醒，減少contextswitch。

我們可以從perf得到的hrtimer_set_expires_range_ns函數(shù)中窺探到這兩個(gè)時(shí)間點(diǎn)的設(shè)定。這本質(zhì)上也是一種對(duì)時(shí)間齊功能。

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的設(shè)定非常有意思，在不同的硬件設(shè)備上，它的值都不同，表示最小的調(diào)度精度。這也是我們最上面的Java程序，在執(zhí)行的時(shí)候，引起時(shí)間抖動(dòng)的根本原因。

End

聊到這里，我想你應(yīng)該能夠想到，世界上根本就沒有準(zhǔn)確的調(diào)度。只不過隨著主頻的增加，我們可以將精度控制在一定范圍內(nèi)。

且不說時(shí)間本身準(zhǔn)不準(zhǔn)，僅僅是這時(shí)間片的細(xì)分，就使得目前的PC機(jī)，在微觀世界上的時(shí)間誤差將變的無比巨大，進(jìn)行高頻率的的精度調(diào)度幾乎是不可能完成的事。

世界上最準(zhǔn)的鐘表，每150億年才會(huì)減少一秒。但1秒也是時(shí)間，我們依然能夠用語言表達(dá)出來。糾結(jié)準(zhǔn)實(shí)時(shí)性是一個(gè)永遠(yuǎn)沒有盡頭的答案，除非我們能夠操縱原子。再加上任務(wù)調(diào)度代碼本身耗時(shí)的不確定性，目前的調(diào)度器維持在納秒精度，已經(jīng)算是一個(gè)奇跡。

世界本身就是人粗略的觀測，何況是人所造出的機(jī)器呢。

作者簡介：小姐姐味道 (xjjdog)，一個(gè)不允許程序員走彎路的公眾號(hào)。聚焦基礎(chǔ)架構(gòu)和Linux。十年架構(gòu)，日百億流量，與你探討高并發(fā)世界，給你不一樣的味道。我的個(gè)人微信xjjdog0，歡迎添加好友，進(jìn)一步交流。