0 前言

接上一篇文章：進程調度（2a）：SJF（短任務優先） 算法 原理與實踐

1 前提鋪墊

與上一篇同。

2 STCF 原理

STCF（Shortest Time-to-Completion First）最短完成時間優先。

2.1 算法

還記得上一個算法SJF嗎？它是非搶占式的，只能傻傻地等著長任務A完成，這顯然是“懦弱”的，并且降低了系統的效率，因此，讓我們給它添加一個搶占功能吧！

搶占什么呢？當然是A了，還是用上次的例子

• A：100
• B：10
• C：20

A在0時刻到達并執行，B和C在10時刻到達。之前B和C只能等著A結束執行再按照B、C的順序執行，現在，我們有搶占功能了！

在時刻10的時候，Scheduler（調度器）發現B和C的執行時間比A短，那么好，A你就不要再執行了，讓B先來吧！ 這里，我們也使用到了上下文切換機制，先保存了A執行的狀態，等B、C執行完，再讓A繼續執行。

一個問題：究竟是識別A剩余執行時間，還是全部執行時間，又或者什么呢？A、B和C的執行時間，系統又怎樣得知？這些我們以后再談，并且這設計到了具體實現的層次，現在，我們的假設還是運行時間是已知的，并且是在抽象層次在談論。

這樣，看起來就比之前的SJF棒多了！起碼它學會了“搶車位”。

現在，Average Turnaround Time = （10 + 30 + 130）/ 3 = 56.67，要知道，之前可是110。

不過，這個算法也會有一些問題，我們下面說一下。

2.2 缺點：長任務“饑餓”

試想一下，對于一個長任務，如果有遠遠不斷地短任務進入，那么這個長任務可能永遠不會被執行了……（它也太慘了……）

不僅如此，對于一個交互型程序來說，與用戶交互的響應時間（我們下一講說這個指標，簡單來說，就是用戶發送命令，到看見屏幕產生變化的時間，這應該很快才對）就會非常長，想象一下，你敲擊鍵盤的字母A后，等待10s才看見屏幕上顯示了A……這簡直讓人發瘋！

說明：在原書中沒有給出STCF算法的模擬，因此暫時沒有實踐內容，不過因為該算法與SJF的區別就在于搶占，因此比較容易理解。

2.3 關注點：順序執行的打破

我們之前看到的進程，都是從一開始執行，就一直執行到完成才停止，這個過程并不需要上下文切換機制（前面的篇章好像寫錯了……），而這一次，我們看到了任務A被分成了兩段來執行，這時候就使用到了上下文切換機制了，被打斷的A，必須要保存現場，然后下一次被執行的時候，恢復現場繼續執行。

這也是我們第一次見到，多個任務不是順序執行的，而是切換執行的，下一篇輪轉算法，你將更清晰地體會到這一點！

3 核心思想

STCF與SJF本質是一樣的，區別就是，前者是搶占式，后者是非搶占式的。

核心思想就是，讓運行時間短的任務先執行。

這樣做的缺點也分析過，長任務可能一直得不到執行，后續我們會解決這個問題的。

4 預告：進程調度（3）：RR（輪轉） 算法 原理與實踐

我們接下來會使用輪轉算法解決交互式程序的響應時間問題。這樣能讓用戶獲得很好的體驗。

下一篇鏈接：RR（輪轉） 算法 原理與實踐