分時作業系統排程演算法

　　分時作業系統採用時間片輪轉的方式為使用者提供服務，那麼你瞭解什麼是時間片輪轉排程嗎?下面由小編為大家整理了分時作業系統的排程演算法的相關知識，希望對大家有幫助!

　　分時作業系統的排程演算法詳解

　　時間片的概念，可以用來部分解釋本書開始時的一句話："在資料傳輸領域，你親眼看見的，都不是真的"。在巨集觀上：我們可以同時開啟多個應用程式，每個程式並行不悖，同時執行。但是在微觀上：由於只有一個CPU，一次只能處理程式要求的一部分，如何處理公平，一種方法就是引入時間片，每個程式輪流執行。

　　概念的引入

　　說到平行計算，尤其是單臺計算機的平行計算，一定要先建立時間片的概念。我們現在所用的，不管是Windows還是Linux，一般都稱為多工作業系統，即，系統允許並行執行多個應用程式。作業系統一般是按照一定策略，定期給每個活動的程序執行其內部程式的機會，並且每次只執行一小段時間，然後作業系統利用中斷強行退出執行，將當前程式資訊壓棧，然後開始執行下一個程序的一小段程式。通過這樣不斷快速的迴圈切換，每個程式都獲得執行，在使用者看來，感覺到很多程式都在平行的執行，這就模擬了平行計算。當然，新的多核CPU以及超執行緒CPU，內部就有超過1個的CPU執行體，執行時就不是模擬了，而是真的有兩個以上的程式在被執行。當然在我們程式設計師看來，只需要理解程式是被作業系統片段執行的，每個片段就是一個時間片，就足夠了。既然是片段執行，程式設計師就必須理解，在自己的程式執行時不是獨一無二的，我們看似很順暢的工作，其實是由一個個的執行片段構成的，我們眼中相鄰的兩條語句甚至同一個語句中兩個不同的運算子之間，都有可能插入其他執行緒或程序的動作。

　　基本概念

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

　　程序排程

　　採用此演算法的系統，其程式就緒佇列往往按程序到達的時間來排序。程序排程程式總是選擇就緒佇列中的第一個程序，也就是說按照先來先服務原則排程，但一旦程序佔用處理機則僅使用一個時間片。在使用先一個時間片後，程序還沒有完成其執行，它必須釋放出處理機給下一個就緒的程序，而被搶佔的程序返回到就緒佇列的末尾重新排隊等待再次執行。處理器同一個時間只能處理一個任務。處理器在處理多工的時候，就要看請求的時間順序，如果時間一致，就要進行預測。挑到一個任務後，需要若干步驟才能做完，這些步驟中有些需要處理器參與，有些不需要***如磁碟控制器的儲存過程***。不需要處理器處理的時候，這部分時間就要分配給其他的程序。原來的程序就要處於等待的時間段上。經過周密分配時間，巨集觀上就象是多個任務一起執行一樣，但微觀上是有先後的，就是時間片輪換。

　　的實現思想

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