[發(fā)明專利]一種多線程環(huán)境下定時(shí)器的設(shè)置方法

無效

• 申請(qǐng)?zhí)枺?/td>: 201110282740.5
• 申請(qǐng)日: 2011-09-20
• 公開（公告）號(hào): CN103019805A
• 公開（公告）日: 2013-04-03
• 發(fā)明（設(shè)計(jì)）人: 田之進(jìn);梁平;寧學(xué)軍
• 申請(qǐng)（專利權(quán)）人: 佳都新太科技股份有限公司
• 主分類號(hào): G06F9/46
• 分類號(hào): G06F9/46
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)軟件領(lǐng)域，特別是涉及一種基于多線程操作系統(tǒng)環(huán)境下的定時(shí)器的設(shè)置方法。

背景技術(shù)

在軟件開發(fā)中經(jīng)常需要用到定時(shí)器，特別是在通信系統(tǒng)的設(shè)計(jì)中，有大量的定時(shí)要求。程序可能定時(shí)執(zhí)行一些任務(wù)，或者在通信的過程中，收發(fā)雙方都需要用到定時(shí)器：發(fā)送方發(fā)送消息以后有時(shí)候需要對(duì)方在約定的時(shí)間內(nèi)收到對(duì)方的回應(yīng)，如果在規(guī)定的時(shí)間內(nèi)收不到回應(yīng)，需要進(jìn)行適當(dāng)?shù)奶幚恚蛘咧匕l(fā)消息，或者進(jìn)入出錯(cuò)處理。在許多基于網(wǎng)絡(luò)通信的協(xié)議中，都有許多與定時(shí)器相關(guān)的規(guī)約，要實(shí)現(xiàn)這些協(xié)議，定時(shí)器的實(shí)現(xiàn)是最基本的要求之一。因此，定時(shí)器在現(xiàn)代程序設(shè)計(jì)中起著至關(guān)重要的作用。

定時(shí)器的設(shè)置方法，根據(jù)實(shí)現(xiàn)的復(fù)雜度、系統(tǒng)的規(guī)模、系統(tǒng)運(yùn)行的效率要求等，目前有很多種實(shí)現(xiàn)方法。其中一種使用比較普遍的方法是增量定時(shí)器。

在增量定時(shí)器的實(shí)現(xiàn)中，設(shè)計(jì)了一種存放定時(shí)器信息的數(shù)據(jù)結(jié)構(gòu)，我們把這個(gè)結(jié)構(gòu)叫做定時(shí)器控制塊(Timer?Control?Block，簡(jiǎn)稱TCB)，TCB記錄了單個(gè)定時(shí)器實(shí)例的唯一標(biāo)識(shí)(timer?ID)、定時(shí)器的超時(shí)時(shí)長(zhǎng)、定時(shí)器觸發(fā)時(shí)的操作。定時(shí)器超時(shí)觸發(fā)時(shí)的操作機(jī)制一般有兩種實(shí)現(xiàn)方法：一種是系統(tǒng)觸發(fā)執(zhí)行某個(gè)預(yù)先定義的方法，一種是系統(tǒng)發(fā)送某個(gè)預(yù)先定義的代表超時(shí)的消息給定時(shí)器的設(shè)置者。前者在TCB中定義一個(gè)函數(shù)的入口，后者在TCB中記錄定時(shí)器的設(shè)置者以及代表超時(shí)的消息的信息。前一種方法的好處是程序相對(duì)簡(jiǎn)單，但觸發(fā)函數(shù)的執(zhí)行有時(shí)候會(huì)影響定時(shí)器的精度，同時(shí)在多線程環(huán)境下可能存在資源競(jìng)爭(zhēng)的問題；后一種方法的好處是超時(shí)處理簡(jiǎn)單，對(duì)定時(shí)器的精度影響較小，缺點(diǎn)是需要在定時(shí)器中實(shí)現(xiàn)消息發(fā)送的機(jī)制，需要記錄定時(shí)器的設(shè)置者。在目前流行的多線程環(huán)境下，消息機(jī)制更容易發(fā)揮多線程的優(yōu)勢(shì)，因而獲得越來越多的使用。

對(duì)一個(gè)通用的定時(shí)器管理方法來說，以下操作是必須提供的：

1)設(shè)置定時(shí)器，setTimer(timer?ID，interval)。設(shè)置一個(gè)定時(shí)器實(shí)例，其中timer?ID為定時(shí)器的唯一標(biāo)識(shí)，interval為定時(shí)器的指定時(shí)長(zhǎng)；

2)清除定時(shí)器，clearTimer(timerID)。在定時(shí)器超時(shí)前，根據(jù)已知的timerID查找到定時(shí)器實(shí)例，并將其刪除；

3)超時(shí)檢查和處理。將定時(shí)器的時(shí)長(zhǎng)劃分為若干個(gè)時(shí)間相等的時(shí)間片，在每個(gè)時(shí)間片內(nèi)檢查所管理的定時(shí)器實(shí)例是否有超時(shí)，如果有，則觸發(fā)超時(shí)處理。

增量定時(shí)器的實(shí)現(xiàn)原理是，通過一個(gè)雙向鏈表管理一個(gè)定時(shí)器控制塊(TCB)的集合，對(duì)定時(shí)器的管理也就是對(duì)這些TCB的操作。增量定時(shí)器在每個(gè)TCB中記錄的時(shí)間間隔是當(dāng)前TCB相對(duì)于它前面一個(gè)將要超時(shí)的TCB的時(shí)間的差值。在多線程的環(huán)境下，一般設(shè)置一個(gè)獨(dú)立的線程，這個(gè)線程執(zhí)行一個(gè)死循環(huán)：先定時(shí)等待一個(gè)時(shí)間片(timerTick)(一般用sleep()類的系統(tǒng)調(diào)用)，接下來將雙向鏈表頭指針的第一個(gè)TCB的interval減去timerTick，然后檢查interval是否大于0。如果不大于0則說明這個(gè)定時(shí)器超時(shí)，執(zhí)行相應(yīng)的超時(shí)處理，并將這個(gè)TCB從鏈表中刪除。因?yàn)榭赡苡卸鄠€(gè)定時(shí)器同時(shí)超時(shí)，因此第一個(gè)超時(shí)的定時(shí)器處理完以后，還需要繼續(xù)從雙向鏈表頭部檢查其他TCB是否也超時(shí)了，直到遇到第一個(gè)沒有超時(shí)的TCB或者遍歷到鏈表結(jié)尾為止。

定時(shí)器設(shè)置方法的性能指標(biāo)一般從空間和時(shí)間兩個(gè)維度進(jìn)行衡量。空間復(fù)雜度指的是算法用于存儲(chǔ)定時(shí)器集合的數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間的度量；時(shí)間復(fù)雜度是指該算法管理特定數(shù)量的定時(shí)器的最大執(zhí)行時(shí)間的度量。

當(dāng)系統(tǒng)中所需要的定時(shí)器數(shù)量非常龐大時(shí)，系統(tǒng)的時(shí)間開銷將隨之增大。假設(shè)TCB的個(gè)數(shù)為n，增量定時(shí)器的setTimer操作為O(n)，clearTimer操作為O(n)，超時(shí)檢查和處理為O(1)。由于clearTimer操作是根據(jù)timerID來查找的，所以通過t?imerID對(duì)TCB進(jìn)行索引可以提高clearTimer操作的時(shí)間性能到O(log_en)的水平，而setTimer不變。這樣，當(dāng)定時(shí)器的設(shè)置和清除操作非常頻繁的時(shí)候，定時(shí)器的性能可能成為系統(tǒng)運(yùn)行的瓶頸。

綜上所述，基于timerID索引的增量定時(shí)器的設(shè)置方法雖然原理簡(jiǎn)單，結(jié)構(gòu)清晰，對(duì)系統(tǒng)的空間開銷不大，但由于setTimer操作的開銷是O(n)，當(dāng)TCB的個(gè)數(shù)很大的時(shí)候，對(duì)系統(tǒng)的時(shí)間性能的影響是非常大的，有必要加以解決。

發(fā)明內(nèi)容