第九天 CPU Scheduling--中

昨天我們說完前兩個演算法，今天從第三個開始繼續講：

1. FCFS — First Come First-Served

2. SJF — Shortest-Job-First(exponential averaging)

3. Priority scheduling
   依據優先權來排順序，以整數代表優先權，數字越小優先權越高。

4. RR(Round Robin)
   給每個process一個固定的時間(time quantum ,q)執行，如果執行不完就再去排隊。如果有n個process在ready queue，每個process有1/n CPU時間，一定不會等超過(n-1)q的時間。以下有例圖，q=4:
   
   雖然平均完成時間比SJF高，但這種的回應比較好。而這個演算法要注意的是，q應該要 > context switch time(平均10 usec內)

5. Multilevel queue
   這種演算法將ready queue分成兩個：Foreground(需要交談的)、Background(可以批次的)。而這兩種queue有各自運用的演算法。而在排程時，這兩種queue之間要先做優先順序的排程、CPU時間的分配。

• Foreground：RR演算法、高優先、80%的CPU時間
• Background：FCFS演算法、低優先、20％的CPU時間

6. Multilevel feedback queue
   因為Multilevel queue的順序是固定的，有時還是需要調整一下順序，所以產生Multilevel feedback queue演算法，所以他是一種動態的排程機制。但這種演算法需要考量：

• 有幾個queue
• 每個queue的演算法
• 什麼時候要把順序往前調
• 什麼時候要把順序往後調
• queue的選擇

以上把演算法給講完啦！現在我們來說說其他的排程吧！

• Thread scheduling：
  執行緒的排程要把user-level threads跟kernel thread分開來說明：
  在user-level threads：
  是在LWP(lightweight process)內執行。如果在many-to-one跟many-to-many model下，就必須經過排程，叫做Process-Contention Scope(PCS)，而會由programmer來做順序的調整。
  在kernel thread：
  在可得到的CPU進行排程，叫做System-Contention Scope(SCP)，由system來排。
  Pthread scheduling：
  Pthread的排程可以thread創建時，可選擇PCS或是SCP，但是有些有特別指定要用哪種。
  而在Linux跟Mac OS X兩種作業系統下，只允許用PCS。

講完執行緒的排程，現在來說多處理器的排程！

• Multiple-Processor Scheduling：
  多處理器的排程會比較複雜，而processor可能會是以下幾種型態：

1. Homogeneous processors：用同樣一顆CPU
2. Asymmetric multiprocessing：非對稱，有一個CPU主導可存data structure，data sharing也由他負責
3. Symmetric multiprocessing(SMP)：對稱，沒個process自己做自己的排程(常看到)
4. Processor affinity：有著不同的關係，soft affinity或是hard affinity

說到這就要講個東西—NUMA：
NUMA，Non-uniform memory access，是將系統分成很多個節點(node)，節點內部存取的時間，比跟節點外的存取時間快很多！以下有例圖：

如果在SMP下，要保持每個CPU有最好的效率，需要考慮load balancing(平衡每個CPU)，會有週期性的push migration跟pull migration。

push migration：如果有很閒的CPU，會把一些process push到上面。
pull migration：如果有在閒置的processor，會pull等待的task來做。

Multicore Processors會將multiple processor trend到一個chip上，跟傳統的Multiprocessor比起來快很多，而且也比較省power。

明天我們來說最後一部分吧！