Linux時間子系統之：Tick Device layer綜述

一、前言

時間子系統中的tick device layer主要涉及kernel/time/tick-*相關的檔案，本文的主要內容就是從high level層次（不糾纏在具體的每行程式碼）描述tick device layer的運作邏輯。

如果說每個.c檔案是一個模組的話，我們可以首先簡單描述tick device layer的各個模組。tick-common.c描述了tick device的一些通用操作，此外，該檔案還包括了週期性tick的程式碼。想要讓系統工作在tickless mode（更準確應該是Dynamic tick模組，也就是說根據系統的當前執行狀況，動態的啟停週期性tick）需要兩個模組的支援，分別是tick-oneshot.c和tick-sched.c。tick-oneshot.c主要是提供和tick device的one shot mode相關的操作介面函式。從字面上看，tick-sched.c是和tick的排程相關，所謂tick的排程包括兩個方面，一方面是在系統正常執行過程中，如何產生週期性的tick event，另一方面是在系統沒有任務執行，進入idle狀態的時候，如何停止週期性的tick，以及恢復的時候如何更新系統狀態（例如：jiffies等）。tick-broadcast.c和tick-broadcast-hrtimer.c是和tick broadcast相關，本文不會涉及這部分的內容，會有專門的檔案描述它。

本文的第二章描述了關於tick device概述性的內容，隨後在第三章描述了tick device layer是如何初始化的，由於tick device開始總是工作在periodic mode，因此，本章也就順便描述了週期性tick的運作。如果硬體以及系統配置允許，系統中的tick device會切換one shot mode，從而進入tickless mode，因此第四章描述了在配置了高精度timer的情況下，dynamic tick如何運作之機理，第五章和第四章類似，只不過描述的是沒有配置高精度timer的情況。

二、tick device概述以及軟體結構

雖然在periodic tick檔案中對tick device有一些描述，不過這裡再複習一次，這次不再細述資料結構而是從較高的層面來描述tick device的軟體結構。

1、什麼是tick

想要理解什麼是tick device，什麼是tickless kernel，首先當然要理解什麼是tick？要理解什麼是tick，首先要理解OS kernel是如何運作的。系統中有很多日常性的事情需要處理，例如：

－－－更新系統時間

－－－處理低精度timer

－－－處理正在執行行程的時間片資訊

系統在處理這些事情的時候使用了輪詢的方式，也就是說按照固定的頻率去做這些操作。這時候就需要HW的協助，一般而言，硬體會有HW timer（稱之system timer）可以週期性的trigger interrupt，讓系統去處理上述的日常性事務。每次timer中斷到來的時候，內核的各個模組就知道，一個固定的時間片已經過去。對於日常生活，tick這個概念是和鐘錶關聯的：鐘錶會發出週期性的滴答的聲音，這個聲音被稱為tick。CPU和OS kernel擴充套件了這個概念：週期性產生的timer中斷事件被稱為tick，而能夠產生tick的裝置就稱為tick device。

如何選擇tick的週期是需要在power comsuption、時間精度以及系統響應時間上進行平衡。我們考慮系統中基於tick的低精度timer模組，選擇較高的tick頻率會提高時間精度，例如對於，10ms的tick週期意味著低精度timer的時間精度就是10ms，設定3ms的低精度timer沒有任何意義。為了提高時間精度，我們可以提高tick的頻率，例如可以提升到1ms的tick，但是，這時更多的CPU的時間被花費在timer的中斷處理，實際上，當系統不繁忙的時候，並不是每一個tick都是那麼有意義，實際上大部分的tick到來的時候，OS kernel往往只是空轉，實際上並有什麼事情做，這對系統的power consumption是有害的。對於嵌入式裝置，週期性的tick對power consumption危害更大，因為對於嵌入式裝置，待機時間是一個很重要的指標，而週期性tick則意味著系統不可能真正的進入idle狀態，而是會週期性的被wakeup，這些動作會吃掉電池的電量。同理，對於排程器而言亦然。如果設定10ms的tick，分配每個行程的時間片精度只是10ms，排程器計算每個行程佔用CPU的時間也只能是以10ms為單位。為了提高行程時間片精度，我們可以提高tick的頻率，例如可以提升到1ms的tick，但是，這時更多的CPU的時間被花費在行程背景關係的切換上，但是，對應的好處是系統的響應時間會更短。

2、什麼是tickless？

tickless本質上上是去掉那個煩惱的滴答聲音。我睡覺的時候不怕噪音，但是非常怕有固定週期的滴答聲音，因此我需要一塊tickless的鐘錶。對於OS kernel而言，tickless也就是意味著沒有那個固定週期的timer interrupt事件，可是，沒有那個固定的tick，OS kernel如何運轉呢？我們還是選取上一節中的三個主題，進行逐一分析。

首先看看如何處理timer。各種驅動和核心模組（例如網路子系統的TCP模組）都有timer的需求，因此，時間子系統需要管理所有註冊到系統的timer。對於有tick的系統，在每個tick中scan所有的timer是一個順理成章的想法，如果檢查到timer超期（或者即將超期）系統會呼叫該timer的callback函式。當然，由於要在每個tick到來的時候檢查timer，因此效率非常重要，內核有一些有意思的設計，有興趣的讀者可以看看低精度timer的的scan過程。沒有tick怎麼辦？這時候需要找到所有timer中最近要超期的timer，將其時間值設定到實際的HW timer中就OK了，當然，這時候需要底層的HW timer支援one shot，也就是說，該timer的中斷就來一次，在該timer的的中斷處理中除了處理超期函式之外，還需要scan所有timer，找到最近要超期的timer，將其時間值設定到實際的HW timer中就OK了，然後不斷的重覆上面的過程就OK了。假設系統中註冊了1200ns, 1870ns, 2980ns, 4500ns, 5000ns和6250ns的timer，在一個HZ=1000的系統上，timer的超期都是在規則的tick時間點上，對於tickless的系統，timer的中斷不是均勻的，具體如下圖所示：

我們再來看看更新系統時間。對於有tick的系統，非常簡單，在每個tick到來的時候呼叫update_wall_time來更新系統時間，當然，由於是週期性tick，這時候每次都是累加相同的時間。對於tickless的系統，我們可以選擇在每個timer超期的中斷中呼叫update_wall_time來更新系統時間，不過，這種設計不好，一方面，如果系統中的timer數目太多，那麼update_wall_time呼叫太頻繁，而實際上是否系統需要這麼高精度的時間值呢？更重要的是：timer中斷到來是不確定的，和系統中的timer設定相關，有的時間段timer中斷比較頻繁，獲取的系統時間精度比較高，有的時間段，timer中斷比較稀疏，那麼獲取的系統時間精度比較低。

最後，我們來看排程器怎麼適應tickless。我們知道，除非你是一個完全基於優先順序的排程器，否則系統都會給行程分配一個時間片（time slice），當佔用CPU的時間片配額使用完了，該行程會掛入佇列，等待排程器分配下一個時間片，並排程執行。有tick當然比較簡單，在該tick的timer中斷中減去當前行程的時間片。沒有tick總是比較麻煩，我能想到的方法是：假設我們給行程分配40ms的時間片，那麼在排程該行程的時候需要設定一個40ms的timer，timer到期後，排程器選擇另外一個行程，然後再次設定timer。當然，如果沒有行程優先順序的概念（或者說優先順序僅僅體現在分配的時間片比較多的情況下），並且系統中處於runnable狀態的行程較少，整體的運作還是OK的。如果有優先順序概念怎麼辦？如果行程執行過程中被中斷打斷，切換到另外的行程怎麼辦？如果系統內的行程數目很多如何保證排程器的效能？算了，太複雜了，還是有tick比較好，因此實際中，linux kernel在有任務執行的時候還是會啟動週期性的tick。當然，世界上沒有絕對正確的設計，任何優雅的設計都是適用於一定的應用場景的。其實自然界的規律不也是這樣嗎？牛頓的定律也不是絕對的正確，僅僅適用於低速的場景，當物體運動的速度接近光速的時候，牛頓的經典力學定律都失效了。

3、核心中的tickless

本節我們主要來看看核心中的tickless的情況。傳統的unix和舊的linux（2000年初之前的）都是有tick的（對於新的核心，配置CONFIG_HZ_PERIODIC的情況下也是有tick的），新的linux kernel中增加了tickless的選項：

－－－CONFIG_NO_HZ_IDLE

－－－CONFIG_NO_HZ_FULL

CONFIG_NO_HZ_IDLE是說在系統dile的時候是沒有tick的，當然，在系統執行的時候還是有tick的，因此，我們也稱之dynamic tick或者NO HZ mode。3.10版本之後，引入一個full tickless mode，聽起來好象任何情況下都是沒有tick的，不過實際上也沒有那麼強，除了CPU處於idle的時候可以停下tick，當CPU上有且只有一個行程執行的時候，也可以停下週期性tick，其他的情況下，例如有多個行程等待排程執行，都還是有tick的。這個配置實際上只是對High-performance computing (HPC)有意義的，因此不是本文的重點。

4、tick device概述

Tick device是能夠提供連續的tick event的裝置。目前linux kernel中有periodic tick和one-shot tick兩種tick device。periodic tick可以按照固定的時間間隔產生tick event。one-shot tick則是設定後只能產生一次tick event，如果要連續產生tick event，那麼需要每次都進行設定。

每一個cpu都有屬於自己的tick device。定義為tick_cpu_device。每一個tick device都有自己的型別（periodic或者one-shot），每一個tick device其實就是一個clock event device（增加了表示mode的member），不同型別的tick device有不同的event handler。對於periodic型別的tick裝置，其clock event device的event handler是tick_handle_periodic（沒有配置高精度timer）或者hrtimer_interrupt（配置了高精度timer）。對於one-shot型別的tick裝置，其clock event device的event handler是hrtimer_interrupt（配置了高精度timer）或者tick_nohz_handler（沒有配置高精度timer）。

Tick Device模組負責管理系統中的所有的tick裝置，在SMP環境下，每一個CPU都自己的tick device，這些tick device中有一個被選擇做global tick device，該device負責維護整個系統的jiffies以及更新哪些基於jiffies進行的全系統統計資訊。

三、kernel如何初始化tick device layer以及週期性tick的運作？

如果把tick device的邏輯當初一個故事，那麼故事的開始來自clockevent device layer。每當底層有新的clockevent device加入到系統中的時候，會呼叫clockevents_register_device或者clockevents_config_and_register向通用clockevent layer註冊一個新的clockevent裝置，這時候，會呼叫tick_check_new_device通知tick device layer有新貨到來。如果tick device和clockevent device你情我願，那麼就會呼叫tick_setup_device函式setup這個tick device了。一般而言，剛系統初始化的時候，所有cpu的tick device都沒有匹配clock event device，因此，該cpu的local tick device也就是global tick device了。而且，如果tick device是新婚（匹配之前，tick device的clock event device等於NULL），那麼tick device的樣式將被設定為TICKDEV_MODE_PERIODIC，即便clock event有one shot能力，即便系統配置了NO HZ。好吧，反正無論如何都需要從週期性tick開始，那麼看看如何進行週期性tick的初始化的。

tick_setup_periodic函式用來設定一個periodic tick device。當然，最重要的設定event handler，對於週期性tick device，其clock event device的handler被設定為tick_handle_periodic。光有handler也不行，還得kick off底層的硬體，讓其週期性的產生clock event，這樣才能推動系統的運作（這是透過呼叫clockevent device layer的介面函式完成的）。

最後，我們思考一個問題：系統啟動過程中，什麼時候開始有tick？多核系統，BSP首先啟動，在其初始化過程中會呼叫time_init，這裡會啟動clocksource的初始化過程。這時候，週期性的tick就會開始了。在某個階段，其他的processor會啟動，然後會註冊其自己的local timer，這樣，各個cpu上的tick就都啟動了。

四、設定了高精度timer的情況下，dynamic tick如何運作？

1、軟體層次

下麵的這幅圖是以tick device為核心，描述了該模組和其他時間子系統模組的互動過程（配置高精度timer和dynamic tick的情況）：

上圖中，紅色邊框的模組是per cpu的模組，所謂per cpu就是說每個cpu都會維護屬於一個自己的物件。例如，對於tick device，每個CPU都會維護自己的tick device，不過，為了不讓圖片變得太大，上圖只畫了一個CPU的情況，其他CPU的動作是類似。為何clock event沒有被塗上紅色的邊框呢？實際上clock event device並不是per cpu的，有些per cpu的local timer，也有global timer，如果硬體設計人員願意的話，一個CPU可以有多個local timer，系統中所有的timer硬體被抽象成一個個的clock event device進行系統級別的管理，每個CPU並不會特別維護一個屬於自己的clock event device。弱水三千，只取一瓢。每個CPU只會在眾多clock event device中選取那個最適合自己的clock event device構建CPU local tick device。

tick device系統的驅動力來自中斷子系統，當HW timer（tick device使用的那個）超期會觸發中斷，因此會呼叫hrtimer_interrupt來驅動高精度timer的運轉（執行超期timer的call back函式）。而在hrtimer_interrupt中會掃描儲存高精度timer的紅黑樹，找到下一個超期需要設定的時間，呼叫tick_program_event來設定下一次的超期事件，你知道的，這是我們的tick device工作在one shot mode，需要不斷的set next expire time，才能驅動整個系統才會不斷的向前。

傳統的低精度timer是週期性tick驅動的，但是，目前tick 處於one shot mode，怎麼辦？只能是模擬了，Tick device layer需要設定一個週期性觸發的高精度timer，在這個timer的超期函式中（tick_sched_timer）執行進行原來週期性tick的工作，例如觸發TIMER_SOFTIRQ以便推動系統低精度timer的運作，更新timekeeping模組中的real clock。

2、如何切換到tickless

我們知道，開始tick device總是工作在週期性tick的mode，一切就像過去一樣，無論何時，系統總是有那個週期性的tick到來。這個週期性的tick是由於硬體timer的中斷推動，該HW Timer的中斷會註冊soft irq，因此，HW timer總會週期性的觸發soft irq的執行，也就是run_timer_softirq函式。在該函式中會根據情況將hrtimer切換到高精度樣式（hrtimer也有兩種mode，一種高精度mode，一種是低精度mode，系統總是從低精度mode開始）。在系統切換到高精度timer mode的時候（hrtimer_switch_to_hres），由於高精度timer必須需要底層的tick device執行在one shot mode，因此，這時會呼叫tick_switch_to_oneshot函式將該CPU上的tick device的mode切換置one shot（Note：這時候event handler設定為hrtimer_interrupt）。同樣的，底層的clock event device也會被設定為one shot mode。一旦進入one shot mode，那個週期性到來的timer中斷就會消失了，從此係統只會根據系統中的hrtimer的設定情況來一次性的設定底層HW timer的觸發。

3、如何產生週期性tick

雖然tick device以及底層的HW timer都工作在one shot mode，看起來系統的HW timer中斷都是按需產生，多麼美妙。但是，由於各種原因（此處省略3000字），在系統執行過程中，那個週期性的tick還需要保持，因此，在切換到one shot mode的同時，也會呼叫tick_setup_sched_timer函式建立一個sched timer（一個普通的hrtimer而已），該timer的特點就是每次超期後還會呼叫hrtimer_forward，不斷的將自己掛回hrtimer的紅黑樹，於是乎，tick_sched_do_timer介面按照tick的週期不斷的被呼叫，從而模擬了週期性的tick。

4、在idle的時候如何停掉tick

我們知道，各個cpu上的swapper行程（0號行程，又叫idle行程）最後都是會執行cpu_idle_loop函式，該函式在真正執行cpu idle指令之前會呼叫tick_nohz_idle_enter，在該函式中，sched timer會被停掉，因此，週期性的HW timer不會再來，這時候將cpu從idle中喚醒的只能是和實際上系統中的hrtimer中的那個最近的超期時間有關。

5、如何恢復tick

概念同上，當從idle中醒來，tick_nohz_idle_exit函式被呼叫，重建sched timer，一切恢復了原狀。

五、沒有設定高精度timer的情況下，dynamic tick如何運作？

  這部分留給有興趣的讀者自己學習吧。