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

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

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

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

一個例子

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

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ù)和納秒數(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秒的速度增長，但實際的執(zhí)行時間，如果放大到納秒，它表現(xiàn)出很沒有規(guī)律的分布。

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

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

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

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

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

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

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

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

pthread_cond_timedwait

一般來說，平臺會提供sleep、pthread_cond_wait、pthread_cond_timedwait等函數(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

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

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

所謂的等待計數(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;
}

時間輪

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

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

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

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

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

一個jiffy = 1/HZ

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

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

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

#define WHEEL_SIZE (LVL_SIZE * LVL_DEPTH)

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

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

hrtimer

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

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

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

timerqueue_head結(jié)構(gòu)在紅黑樹的基礎(chǔ)上，增加了一個next字段，用于保存樹中最先到期的定時器節(jié)點，算是對紅黑樹小小的改造。這些改造在效率上都是立竿見影的，效果就像B+ Tree對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))));

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

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

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í)行的時候，引起時間抖動的根本原因。

End

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

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

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

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

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