2009年6月19日 星期五

Time service的設計想法

micro c/os II的方式:

進行delay的安排時,只把task移出ready queue、在TCB內記錄要delay多久,最後重新呼叫scheduler

對於delay的處理方式則是每tick都線性的去找所有TCB,去扣除時間紀錄,如果扣完則放入ready queue,並在最後要求排程。


BSD的方式:

利用一個linked listdelay的安排,每個節點都記錄與前一個節點的相對delay時間,如果要新加一個delayprocess,則必須線性的去追那個linked list,找到相應的時間區段,如果該區段已有node,則將node分割。

對於delay的處理方式則是去處理linked list的開頭就好,把delay時間扣完就移除node重新排程。


想法:

因為進行TickISR的頻率比OSTimeDly還要來的高,因此BSD的這種在TickISR節省時間的方式其實相對的划算,不過由於micro c/os IItask只有64個,這種時間上的浪費也不會明顯,因此大概還在可以接受的範圍。

幾個critical section保護方式的評估

disable/enable interrupt:

效果最直接,但是代價也最大,一旦將中斷停掉,運行一個process就絕不會受任何東西干擾,也不會引發context switch,但是會因忽略掉中斷而影響到系統效能,其影響大小與停掉的時間成正比,在多處理器的狀況甚至必須牽一髮而動全身的影響到所有CPU才能確保沒有process去同時存取critical section,代價相當龐大,因此能避則避,使用的區段也越短越好。


lock/unlock scheduler:

代價比前者小些,而且對中斷的處理依然能進行,但是反過來說,卻也因此保護不了ISR會去動到的部份,使用的時機必須去注意,此外,也可能造成本來就沒有存取到該區域的process即便有更高的優先權,也拿不到它應有的CPU執行時間,對於系統排程而言是一種損失。


semaphore:

也是代價相對較小的保護方式,在可動用的名額不足的情形下,將會被系統放入waiting queue中等待,但是依然無法防止被ISR修改,而且執行的overheadlock/unlock scheduler大些。


大致上來說每種做法都各有優缺點,使用的時機與方式最好視狀況來衡量。

blocking I/O

此處的blocking指的是process停住了,process進行此類I/O之時,如果沒有辦法立即取得它想要的資源時,將會被系統排入waiting queue內部進行等待,此種狀況對process而言就是被blocking


一旦進入了此種狀態,要離開的方法有:


1.系統給了它所需的資源

2.被強制中斷(如因為time out而收到signal之類的)


與其反面的構想有Asynchronous I/O method 就是通稱的 non-blocking I/O
會讀進資料到指定位置,但是並不會去進行等待,當下可能沒讀到任何東西,
但是之後的資料接收可以另外安排。

context switch

流程:

1.push register的內容進入stack

2.stack pointer存到TCB之中

3.切換stack為高優先權的taskstack

4.popregister的值

5.interrupt return


構想:

利用了stack來保存各register的值,維持了運算的內容與狀態,為的是等到切換回來時又能夠再次pop回來,而stack的位置則由每個taskTCB各自去保存。


猜測:

不直接把放在TCB內大概是因為一個task不一定會用到所有的register,如果用這種作法會造成空間浪費;或者是單純不希望眾多TCB把記憶體容量占用過多。

tick ISR作法的優缺評估

一氣呵成型:

優點為對中斷而言,它的處理都會是即時的,也就是說,它不用考慮系統排程的因素,因此對於tick ISR這種處理時間中斷的制度,可以免去時間不準確的問題,而且因為不用經歷context switch,其代價與處理時間是較少的;不過,其缺點在於disable掉中斷的連續時間相對長,因此中間被忽略掉的中斷會較多,而且因為一tick就必須處理一次,就想法上而言是相當可惜的。


top half + bottom half:

因為被拆成2部分,使得連續disable interrupt的時間相對短,因此系統效能得到部分提升為其優點,不過對於tick ISR這種處理時間的工作,會有時間計算失真的可能性,因為其計算時間的OSTimeTick是放在bottom half內,而bottom half的處理時間視系統的排程而定,即便設定較高優先權,依然有不即時的狀況,不過一般而言似乎視為可忽視的誤差,此外,由於context switch的數量較多,因此overhead大了些。


linux就是採用top half + bottom half的方式來設計ISR,即便是在spin lock中,也有分成只disablebottom half,但繼續接受IRQ(top half的功能)的版本,以及2者都disable掉的版本。

bottom half

所謂的bottom half,是與top half為一組的ISR處理方式,bottom half負責的工作是整個ISR所要作的主體工作的部份,比如說處理tick中斷的bottom half,其內部的主要工作就是去呼叫OSTimeTick(),它的特性為能夠被系統排程器所排程,不過由於它對中斷而言並不是第一線的ISR處理,因此內部若會改變process的狀態的話,必須自行呼叫scheduler去重新排程,才能夠達到完整的效果。


想法:

它與top half之間的時間關係並非絕對連續,也因此,它對於中斷而言,處理的並不即時,如此一來,如果越希望bottom half能即時處理,給bottom half的優先權就得設得越高才行,反過來說,如果對於即時性的需求略微低些的中斷,其bottom half的優先權應該可以設得比需求高的中斷的bottom half相對低一點才是。


top half

負責的工作:

1.儲存裝置相關資料

2.bottom half喚起

3.加入排程


它是ISR的最前端,負責接收中斷的請求,目的在於避免讓interrupt被停掉太久 以藉此增加作業系統的效能,因此它內部的工作只負責把bottom half加入排程,一次工作的時間都相當的短暫。

此外,因為top halfbottom half兩者是獨立運行的,即便是bottom half在工作的途中,top half依然可以繼續接受中斷請求,增加要排程的interrupt handler,減少了不能即時處理而遺漏掉的機會,這也正是上面所說的能夠增加效能的原因。

但是相對的,對中斷而言,只有top half是即時的,與bottom half的時間差因為受系統排程影響,是無法預估的。