Scheduling Creteria 衡量標準

在介紹演算法之前必須要先了解怎麼樣去比較演算法的好壞，衡量scheduling algorithm通常會比較以下這幾個值：

• CPU utilization :CPU 使用率 (越高越好)
• Throughput :每單位時間內完成的工作量，以Scheduling來講就是每個時間單位完成的process (越高越好)
• Turnaround time: 每一個平均job從提交到完成的執行時間 (越短越好)
• Waiting time: 所有在ready queue裡的process總計的等待時間 (越短越好)
• Response time: 在Process被提交後到首次回應的時間 (越短越好)

First Come First Served (FCFS)

概念非常簡單有如其名，最先進來的Process就先做，其壞處是假若目前進來的Process有一個非常長的burst time，後面進來的process就會全部被卡在那邊，造成平均的Waiting time(AWT)很長。

Shortest-Job-First (SJF)

SJF的主要目標是改良FCFS演算法在平均等待時間(AWT)太長的缺點，其概念是只做當下burst time最短的Process，因此在preemptibe 和non-preemptive會有所差別囉。preemptibe會在發現有其他burst time比較短的process可以做的時候，馬上打斷目前的工作，並且去執行最短的那個，non-preemptive則會等到當前在做的CPU burst過了，才從剩下的挑最短的來做。這個方法不一定會是最好的，因為有可能會犧牲Response Time。

Approximate Shortest-Job-First

這個方法在解決SJF的一個困難點，在還沒執行Process並無法很明確的知道需要的burst time，Approximate指的是用過去的burst time來預測時間到底是多長，根據那個時間來做shortest-job-first。

Priority Scheduling

在runtime的時候會給予每個process一個priority的值，scheduler會針對這個值去做排序，這個值可能會受到很多東西影響，像是這個Process的重要性，像是系統在執行的process就會比user執行的還高，還有process的waiting time等等，當一個process等得越久，優先度就越高。

Priority Scheduling也有分為preemptive和non-preemptive的，可能執行到一半跑出一個priority很高的，就打斷目前執行到一半的prcoess這樣，當前比較知名的作業系統都會使用到這個方法。

Mixing - Multilevel Queue Scheduling

Ready queue會被切割成好幾個不同的queue，並且他們有不一樣的層級(system process -> interactive processes -> interactive editing processes -> batch processes -> student processes)，也有屬於每個queue自己的scheduling algorithm，process不能在不同層級的queue裡面移動，但也不會使用queue的層級去選擇哪個先做。

每個queue會有一個固定的CPU time，就在這些被分配的時間去消耗queue裡面的process，這樣的方法會比較符合使用者需求，作業系統更可以去決定哪一個Process是比較重要的。

Multilevel Feedback queue schedul

與Multilevel Queue Scheduling一樣會把Prcoess放入好幾個不同層級的queue當中，由最高層級的queue開始做到最低層級的queue，一定要把某個層級全部做完才能去下一個queue，但process可以在各個level之間的queue移動。為什麼要這樣設計是因為很多資訊需要在run time的時候才能收集。