Linux kernel分析之定時器 巧妙的定時器算法：內核中經常要用到各種定時器。比如nanosleep()系統調用，讓當前進程睡眠一段時間，再把它喚醒。即在expires時刻(以時鐘滴答為單位)，自動調用wake_up_process。最直接的思路是定義一個定時器，里面有function(函數指針)，data(函數參數)，expires(調用時刻)。然后排成一個鏈表。每次時鐘中斷發生時，掃描整個鏈表，發現有觸發的定時器，就調用function(data)。尋找觸發的定時器的時間復雜度O(N)。N是定時器數量。明顯，這個算法效率太低。
改進：事實上我們只對最快觸發的定時器感興趣，所以在插入元素時就對元素進行排序。這樣，每次時鐘中斷，只要檢查鏈表中第一個定時器就行。尋找觸發的定時器的時間復雜度O(1)。但是每次插入和刪除操作的時間復雜度又變成O(N)了。這個算法還是不好。繼續改進：把數據結構改成優先隊列(最小堆)，這樣插入刪除操作的時間復雜度為O(logN)。尋找觸發的定時器的時間復雜度O(1)。
有沒有可能繼續改進呢?墻上的掛鐘給人以靈感。當秒針飛快走動時，分針走的很慢，而時針幾乎不動。這提醒我們要區別對待定時器。要把定時器劃分成不同區間。對最早可能觸發的定時器頻繁掃描(就像秒針)，而對很晚才觸發的定時器隔一段時間再掃描(就像分針)。
基本思路：2^8-1個時鐘滴答內觸發的定時器放到第一組，2^8~2^14-1個時鐘滴答內觸發的定時器放到第二組，依次類推，最后分成五組。第一組每個時鐘中斷都要檢查，第二組則每2^8=256個時鐘中斷檢查一次，依次類推。每組中有256個隊列。那么檢查每一組是否意味著檢查這256個隊列?不是的。事實上，根據觸發時間，我們可以把定時器放到對應的隊列中(如在第一組中，把觸發時間為expires的定時器放到第expires%256個隊列
中)。那么我們在檢查每一組時，只要掃描其中一個隊列就可以了。對于第一組，被檢查到的定時器需要執行定時器函數。對于其它組，則意味著“升級”(跳到前一組，由于臨近觸發而受到更頻繁的檢查)。
可以看出，這個算法中，尋找觸發的定時器的時間復雜度接近O(m)(m是第一組每個隊列中定時器的個數，其它組的操作幾乎可以忽略)。而這個m在絕大部分情況下接近1。插入和刪除操作的時間復雜度也為O(1)。這是迄今為止最好的算法。
從中也可以看出，把一個大隊列分割成幾個小隊列，可以極大的降低算法的時間復雜度，提高效率。2.6內核中，調度算法也采用了類似的思想。
主要還是使用分治的思想，將大的數據的數據轉換成小數據單元進行處理。
看文倉www.kanwencang.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20170204/97766.html
文章列表
留言列表
