輪轉策略

輪轉策略（Round-Robin）簡稱為RR，在RR里面，每個準備就緒的任務只能在有限的時間內運行，也就是說不管這個任務完成與否，都會切換任務到下一個。
由于它要頻繁的切換隊列，我們可以把準備就緒的隊列視為FIFO隊列，假設任務A需要30ms，cpu的時間切片為10ms，那么它執行到10ms時，cpu便會產生一個中斷信號，此時任務A來到隊尾，任務B接著上去。這樣做看似雨露均沾，它的平均等待時間確實比較長的。假設使用4ms的時間片，A、B、C的任務時間分別為10ms，15ms，20ms，那么它在采用RR策略下的平均等待時間為(6+11+16)/3=11ms
一般來說CPU的調度時間小于切片時間,如果我們最關心的指標是操作系統的調度時間，那么使用RR顯然不是一個明智的選擇。

公平策略的得與失

RR策略是一種公平策略，使用任何一種公平策略的時候就要考慮到小任務不會被優先處理，這在某一種程度上是令人難受的，但這也是現實世界的哲學，沒有什么算法是十全十美的，我們更多的是要結合使用場景來選擇對當前場景最有利的算法。
優化了周轉時間比如SJF，STCF優化了中轉時間，但對響應時間不利
優化了響應時間比如RR優化了響應時間，但由于頻繁切換任務浪費的時間，對周轉時間不利。

多級反饋隊列

多級反饋隊列的出現主要是為了平衡周轉時間與響應時間，這里涉及到一個MLFQ的概念，它是把所有待處理的任務都分成隊列，然后給每個隊列標上不同的優先級。
MLFQ(Multilevel Feedback Queue Scheduling)先處理優先級最高的隊列，將優先級較低的隊列放到后面處理，如果遇到兩個優先級一樣的隊列就會采用輪詢的方式來處理

比例分額

并不是我們所有的算法目的都是為了在周轉時間與響應時間之間找到一個平衡點，有時候只需要保準CPU對每一個任務都有一波雨露均就可以了。用一個直接粗暴的方法，每隔一段時間隨機抽取一個任務處理，這個被稱作彩票處理方法，隨機方法具有輕量的特性，它無需比較數據庫中任務的大小，直接利用隨機數抽取。
這里會用到步長調度算法。步長調度也很簡單。系統中的每個工作都有自己的步長，這個值與票數值成反比。在上面的例子中，A、B、C這3個工作的票數分別是100、50和250，我們通過用一個大數分別除以他們的票數來獲得每個進程的步長。比如用10000除以這些票數值，得到了3個進程的步長分別為100、200和40。我們稱這個值為每個進程的步長（stride）。每次進程運行后，我們會讓它的計數器 [稱為行程（pass）值] 增加它的步長，記錄它的總體進展。

多核處理器調度

初學者編寫程序時，大多數情況下編寫的程序都是單核調度的，增加了CPU的個數并沒有對你這個程序運行有任何作用，為了解決這個問題不得不重寫應用程序，讓其采用多線程的方式執行。
程序第一次讀取數據，花費時間比較長，讀取之后你會把它放在緩存中，以防后續再有程序想要讀取它， 這個叫做時間局限性；空間局限性是指，程序讀取了這個地址的數據，它接下來很有可能讀取這個地址周圍地址的數據，這兩種局部性存在于絕大多數系統，這只是在一個處理器的情況下，當有多個處理器的時候情況會變成怎樣？

緩存一致性

存在這樣一種情況，當程序A想要修改在內存上的一個數據，由于這個數據不在CPU的cache里面，我們便會首先訪問內存并且修改數據，把數據位置從d轉移到$D$假設這個時候，操作系統中斷了這個任務的操作，這時候第二個任務也要來修改這個數據，那么它肯定在d處是找不到這個數據的，但是它不知道d處已經發生了變化，還會從d處讀取一個過時的數據。
解決這個問題的方法是監控內存的訪問，硬件可以保證獲得正確的數據，并保證共享內存的唯一性。在基于總線的系統中，一種方式是使用總線窺探（bus snooping）[G83]。每個緩存都通過監聽鏈接所有緩存和內存的總線，來發現內存訪問。如果CPU發現對它放在緩存中的數據的更新，會作廢（invalidate）本地副本（從緩存中移除），或更新（update）它（修改為新值）。

同步

在跨CPU訪問數據的時候，會涉及到互斥原語，這里說幾種CPU鎖的結構

互斥鎖

不管是互斥鎖還是自旋鎖，加鎖的目的就是保證共享資源在任意時間里，只有一個線程訪問，這樣就可以避免多線程導致共享數據錯亂的問題。
互斥鎖，確保同一時間只有一個線程訪問數據。對共享資源的訪問，先對互斥量進行加鎖，如果互斥量已經上鎖，調用線程會阻塞，直到互斥量被解鎖。在完成了對共享資源的訪問后，要對互斥量進行解鎖

自旋鎖

當一個線程在獲取鎖的時候，如果鎖已經被其它線程獲取，那么該線程將循環等待，然后不斷的判斷鎖是否能夠被成功獲取，直到獲取到鎖才會退出循環。 獲取鎖的線程一直處于活躍狀態，但是并沒有執行任何有效的任務，使用這種鎖會造成 busy-waiting 。

總結

以上是生活随笔為你收集整理的常见操作系统调度算法研究（2)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。