時間片輪轉調度

説到並行計算，尤其是單台計算機的並行計算，一定要先建立時間片的概念。

我們現在所用的，不管是Windows還是Linux，一般都稱為多任務操作系統，即，系統允許並行運行多個應用程序。

操作系統一般是按照一定策略，定期給每個活動的進程執行其內部程序的機會，並且每次只執行一小段時間，然後操作系統利用中斷強行退出執行，將當前程序信息壓棧，然後開始執行下一個進程的一小段程序。

通過這樣不斷快速的循環切換，每個程序都獲得執行，在用户看來，感覺到很多程序都在平行的執行，這就模擬了並行計算。

當然，新的多核CPU以及超線程CPU，內部就有超過1個的CPU執行體，運行時就不是模擬了，而是真的有兩個以上的程序在被執行。

當然在我們程序員看來，只需要理解程序是被操作系統片段執行的，每個片段就是一個時間片，就足夠了。

既然是片段執行，程序員就必須理解，在自己的程序運行時不是獨一無二的，我們看似很順暢的工作，其實是由一個個的執行片段構成的，我們眼中相鄰的兩條語句甚至同一個語句中兩個不同的運算符之間，都有可能插入其他線程或進程的動作。

時間片輪轉法（Round-Robin，RR）主要用於分時系統中的進程調度。為了實現輪轉調度，系統把所有就緒進程按先入先出的原則排成一個隊列。新來的進程加到就緒隊列末尾。每當執行進程調度時，進程調度程序總是選出就緒隊列的隊首進程，讓它在CPU上運行一個時間片的時間。時間片是一個小的時間單位，通常為10~100ms數量級。當進程用完分給它的時間片後，系統的計時器發出時鐘中斷，調度程序便停止該進程的運行，把它放入就緒隊列的末尾；然後，把CPU分給就緒隊列的隊首進程，同樣也讓它運行一個時間片，如此往復。 ^[1] 

採用此算法的系統，其程序就緒隊列往往按進程到達的時間來排序。進程調度程序總是選擇就緒隊列中的第一個進程，也就是説按照先來先服務原則調度，但一旦進程佔用處理機則僅使用一個時間片。在使用先一個時間片後，進程還沒有完成其運行，它必須釋放出處理機給下一個就緒的進程，而被搶佔的進程返回到就緒隊列的末尾重新排隊等待再次運行。

處理器同一個時間只能處理一個任務。處理器在處理多任務的時候，就要看請求的時間順序，如果時間一致，就要進行預測。挑到一個任務後，需要若干步驟才能做完，這些步驟中有些需要處理器參與，有些不需要（如磁盤控制器的存儲過程）。不需要處理器處理的時候，這部分時間就要分配給其他的進程。原來的進程就要處於等待的時間段上。經過周密分配時間，宏觀上就象是多個任務一起運行一樣，但微觀上是有先後的，就是時間片輪換。

時間片輪轉算法的基本思想是，系統將所有的就緒進程按先來先服務算法的原則，排成一個隊列，每次調度時，系統把處理機分配給隊列首進程，並讓其執行一個時間片。當執行的時間片用完時，由一個計時器發出時鐘中斷請求，調度程序根據這個請求停止該進程的運行，將它送到就緒隊列的末尾，再把處理機分給就緒隊列中新的隊列首進程，同時讓它也執行一個時間片。