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的時間差因為受系統排程影響,是無法預估的。

lazy context switch

最早為用於FPU的制度,後來用途已延伸,需要硬體的支援(要能把FPU disable enable)才能做到。


構想:

因為會用到FPUprocess不很多、同一process連續用到FPU的機率較高,故都先定為disable等到要用到再去enable並紀錄owner,如果被context switch時,FPU又會被disable掉,等到下次被取用時,就會去check owner是否相同,如果對不上,才會對FPU進行context switch,如果對上了,則可以省去對FPU context switch的一大串動作。


以上的構想前提都在於因為會用到FPUprocess不很多、同一process連續用到FPU的機率較高這句,如果前提不成立的話,此制度反而是白費工,至於前提的來源大概是統計與經驗法則吧。

2009年6月18日 星期四

buddy system

概念:

memory不斷用對半分的概念拆小,拆成同大小的區塊被稱為buddy,所能分成的最小單位為page,在linux中與slab共同配合使用。


理:

1.把可用空間分割為block來管理,每個block大小都為2的次方.

2.最初不切割空間,只構築空間list(小到大),並把完整的大小掛在表尾.

3.在要求空間後去查表,到大小最剛好的空間編號處,若已有空block可用,則取得,不然則往下查表到有空block的編號,把該block不斷對半分並掛到新的適合編號處,直到目標編號有空block能用為止.

4.長時間下來,一個編號處的空block可能有多個,是用link方式串接著

5.釋放掉空間時,則藉由它的大小去查表,掛回到適當的編號


以上課的說法來看,buddy system算是中盤商的話,slab就是小盤商,從buddy system接手區塊,然後負責做更小的區塊分配。

spinlock

要防止一個結構被多個process同時存取有多種方法,而spinlock就是其中的一種;要防止被多process同時存取,最簡單的方法大概是把中斷都disable掉,不過這作法會讓系統效能大跌,如果在多處理器的情況下,甚至還得把每個處理器的中斷都disable掉,才能夠確保沒有多process同時存取的可能,不過如此一來,付出的代價就過高了,這種情形下,像spinlock這種方法就顯的相對實用,因為它不會把所有的CPU中斷都停掉。spinlock說直接點就是在資源被釋放前不斷的去做空循環檢查,內部由組合語言寫成。

使用例:

linux中最常被使用的是spin lock irqsave和與其相對應的spin unlock irqrestore

使用法為:

spinlock_t xxx lock = SPIN_LOCK_UNLOCKED;

unsigned long flags;

spin lock irqsave (&xxx lock, flags);

/*critical section*/

….

spin unlock irqrestore (&xxx lock, flags);

以上動作就能把critical section內的資料保護住,確保無論是讀還是寫,能存取到要保護的資料的總共只會有一個人,宣告unsigned long flags的用途在於讓目標CPU的中斷disable掉之前,先把CPUflag值先存進去,等到要回復時再還原。