Thread Scheduling

• 是排程執行緒，並非行程。
• 在M:M與M:One模組上，thread library scheduling讓user-level threads在LWP上執行：

1. 知道Process-Contention Scope(PCS)方法，排成在行程內。
2. 交給programmer來操作。

• Kernel thread是被排程給可使用的CPU，是System-Contention Scope(SCS)方法，全部threads交由系統操作。

Pthread Scheduling

• API允許確認在新增thread中是PCS或SCS方法：

1. PTHREAD_SCOPE_PROCESS排程threads就是使用PCS scheduling。
2. PTHREAD_SCOPE_SYSTEM排程threads就是使用SCS scheduling。

• 會受OS所限制：

1. 像是Linux和Mac OS X只能使用PTHREAD_SCOPE_SYSTEM。

Multiple-Processor Scheduling

• 當使用多重CPU時，CPU scheduling就會更複雜。
• Homogenous processor存在多重處理器內(multiprocessor)。
• Asymmetric multiprocessing(非對稱多重處理)：只有一個處理器存取系統data架構，能緩解共享data的需要。
• Symmetric multiprocessing(對稱多重處理，SMP)：每個處理器由自己做scheduling，且所有行程在共同的ready queue內，或每個ready queue有自己的private queue。
• Processor affinity：行程有affinity(姻親關係)給正確執行的處理器：

1. soft affinity
2. hard affinity
3. 包含多變化的processor sets

Multiple-Processoe Scheduling - Load Balancing

• 如果是SMP的話，需要保持所有CPU的下載效率。
• Load balancing(負載度)：讓工作量保持平均分配。
• Push migration：定期檢查每個處理器的工作下載，如果過多的話，將工作從過載的CPU內轉移到其他CPU中。
• Pull migration：從忙碌的CPU內，拉回正在等待被執行的工作到閒置的CPU中。

Multicore Processors

• 在同一個物理晶片上，放置多個處理器內核，這是目前的一種趨勢。
• 更快速而且低耗能。
• 當memory被取回時，利用memory停滯時間，取得其他行程中的progress。

Real-Time(即時) CPU Scheduling

• Soft real-time systems：不保證重要的real-time process會何時被排程。
• Hard real-time system：必須在dead line前完成工作。
• 有兩種延遲會造成影響：

1. Interrupt latency(中斷延遲)
2. Dispatch latency(調度延遲)

• 多了dead line的限制，要提高整體效率有困難。
• Conflict phase：

1. 任何可中斷的行程在kernel mode中執行。
2. 從低優先行程中釋放出資源，將資源放到高優先行程中使用。

Priority-based Scheduling

• 為了real-time scheduling，所以排程需要能夠支持可中斷且priority-based的排程。但只保證soft real-time。
• hard real-time必須要提供能符合dead line的能力。
• 如果process是週期性的需要CPU的話，那就需要進行週期性的檢查。

Virtualization and Scheduling

• Virtualization(虛擬化)的軟體排程會有multiple guests在CPU上。
• 每個guest在自己的scheduling上執行：

1. 不知道自己有權利能控制CPU，變執行Scheduler。
2. 導致反應時間不佳。

• 一個CPU上面有很多OS，且都有自己的排程方法。

Rate Montonic Scheduling

• 依照頻率大小，分配優先權。
• 最短執行時間 = 最高優先權
• 最長執行時間 = 最低優先權

Earliest Deadline First Schrduling(EDF)

• 依照優先權分配到各dead line上。
• 最早dead line = 最高優先權
• 最晚dead line = 最低優先權

Proportional Share Scheduling

• CPU的時間會被分配到所有在系統中的行程。

POSIX Real-Time Scheduling

• 是POSIX.1b的標準。
• API提供functions給real-time threads管理。
• 將real-time threads分成兩scheduling定義：

1. SCHED_FIFO：將threads使用FIFO方法進行排程到FIFO queue。
2. SCHED_RR：除非發生time-slice，否則給threads同等優先權。