概念的引入
說到並行計算,尤其是單台計算機的並行計算,一定要先建立時間片的概念。
我們現在所用的,不管是Windows還是Linux,一般都稱為多任務作業系統,即,系統允許並行運行多個應用程式。
作業系統一般是按照一定策略,定期給每個活動的進程執行其內部程式的機會,並且每次只執行一小段時間,然後作業系統利用中斷強行退出執行,將當前程式信息壓棧,然後開始執行下一個進程的一小段程式。
通過這樣不斷快速的循環切換,每個程式都獲得執行,在用戶看來,感覺到很多程式都在平行的執行,這就模擬了並行計算。
當然,新的多核CPU以及超執行緒CPU,內部就有超過1個的CPU執行體,運行時就不是模擬了,而是真的有兩個以上的程式在被執行。
當然在我們程式設計師看來,只需要理解程式是被作業系統片段執行的,每個片段就是一個時間片,就足夠了。
既然是片段執行,程式設計師就必須理解,在自己的程式運行時不是獨一無二的,我們看似很順暢的工作,其實是由一個個的執行片段構成的,我們眼中相鄰的兩條語句甚至同一個語句中兩個不同的運算符之間,都有可能插入其他執行緒或進程的動作。
基本概念
時間片輪轉法(Round-Robin,RR)主要用於分時系統中的進程調度。為了實現輪轉調度,系統把所有就緒進程按先入先出的原則排成一個佇列。新來的進程加到就緒佇列末尾。每當執行進程調度時,進程調度程式總是選出就緒佇列的隊首進程,讓它在CPU上運行一個時間片的時間。時間片是一個小的時間單位,通常為10~100ms數量級。當進程用完分給它的時間片後,系統的計時器發出時鐘中斷,調度程式便停止該進程的運行,把它放入就緒佇列的末尾;然後,把CPU分給就緒佇列的隊首進程,同樣也讓它運行一個時間片,如此往復。
進程調度
採用此算法的系統,其程式就緒佇列往往按進程到達的時間來排序。進程調度程式總是選擇就緒佇列中的第一個進程,也就是說按照先來先服務原則調度,但一旦進程占用處理機則僅使用一個時間片。在使用先一個時間片後,進程還沒有完成其運行,它必須釋放出處理機給下一個就緒的進程,而被搶占的進程返回到就緒佇列的末尾重新排隊等待再次運行。
處理器同一個時間只能處理一個任務。處理器在處理多任務的時候,就要看請求的時間順序,如果時間一致,就要進行預測。挑到一個任務後,需要若干步驟才能做完,這些步驟中有些需要處理器參與,有些不需要(如磁碟控制器的存儲過程)。不需要處理器處理的時候,這部分時間就要分配給其他的進程。原來的進程就要處於等待的時間段上。經過周密分配時間,巨觀上就象是多個任務一起運行一樣,但微觀上是有先後的,就是時間片輪換。
實現思想
時間片輪轉算法的基本思想是,系統將所有的就緒進程按先來先服務算法的原則,排成一個佇列,每次調度時,系統把處理機分配給佇列首進程,並讓其執行一個時間片。當執行的時間片用完時,由一個計時器發出時鐘中斷請求,調度程式根據這個請求停止該進程的運行,將它送到就緒佇列的末尾,再把處理機分給就緒佇列中新的佇列首進程,同時讓它也執行一個時間片。