預測SJF進程的CPU突發時間


SJF演算法是最好的排程演算法之一,因為它提供了最大的吞吐量和最少的等待時間,但是該演算法的問題是,CPU的突發時間無法預先知道。

我們可以估算某個進程的CPU爆發時間。 有多種技術可用於假定進程的CPU突發時間。假設需要準確以便最佳地利用演算法。

有以下技術用於假定某個進程的CPU爆發時間。

1. 靜態技術

進程大小

可以根據其大小預測進程的爆發時間。 如果有兩個進程T_OLDT_New,並且舊進程的實際突發時間為20秒,進程的大小為20 KB。 我們知道P_NEW的大小是21 KB。 那麼P_New具有類似突發時間20秒的概率是最大的。

If,     P_OLD → 20 KB   
P_New → 21 KB   
BT(P_OLD) → 20 Secs  
Then,   
BT(P_New) → 20 secs

因此,在這項技術中,我們實際上根據新進程的相似大小的舊進程的突發時間來預測新進程的爆發時間。

進程型別

也可以根據其型別預測過程的爆發時間。進程可以是以下定義的各種型別。

  • OS進程
    進程可以是排程程式,編譯器,程式管理器和更多系統進程等作業系統進程。 它們的爆發時間通常較低,例如:3到5個單位時間。

  • 使用者進程
    使用者發起的進程稱為使用者進程。 可以有三種型別的過程如下。

    • 互動進程
      互動式進程是與使用者不時互動的進程或執行完全取決於使用者輸入的進程,例如各種遊戲就是這樣的進程。 爆發時間需要降低,因為它們不需要CPU很長時間,它們主要取決於使用者與進程的互動性,因此它們主要是IO系結進程。

    • 前台進程
      前台進程是使用者用來執行其需求的進程,例如MS Office,編輯器,實用程式軟體等。這些型別的進程有更高的突發時間,因為它們是CPU和IO系結進程的完美組合。

    • 後台進程
      後台進程支援其他進程的執行。 它們以隱藏模式工作。 例如,金鑰記錄器是記錄使用者按下的金鑰和使用者在系統上的活動的過程。 它們主要是CPU系結的進程,需要更長的CPU時間。

動態技術

簡單平均
在簡單的平均中,給出了n個進程P(i)……. P(n)的列表。 令T(i)表示過程P(i)的突發時間。 假設τ(n)表示Pth過程的預測突發時間。 然後根據簡單平均,過程n + 1的預測突發時間將被計算為,

τ(n+1) = (1/n) ∑ T(i)

其中,0 <= i <= n並且ΣT(i)是到目前為止所有可用過程的實際突發時間的總和。

指數平均或時效

令Tn為第n個過程的實際突發時間.τ(n)為第n個過程的預測突發時間,則下一個過程(n + 1)的CPU突發時間將被計算為,

τ(n+1) = α. Tn + (1-α) . τ(n)

其中,α是平滑。 它的值在0和1之間。