-
先來先服務
鎖定
- 中文名
- 先來先服務
- 外文名
- first-come first-service
- 優 勢
- 簡單,易於編碼實現
- 分 類
- 準則
- 優 點
- 有利於長作業以及CPU繁忙的作業
- 缺 點
- 不利於短作業以及I/O繁忙的作業
- 縮 寫
- FCFS
先來先服務基本思想
先來先服務的調度算法:最簡單的調度算法,既可以用於作業調度 ,也可以用於程序調度,當作業調度中採用該算法時,系統將按照作業到達的先後次序來進行調度,優先從後備隊列中,選擇一個或多個位於隊列頭部的作業,把他們調入內存,分配所需資源、創建進程,然後放入“就緒隊列”,直到該進程運行到完成或發生某事件堵塞後,進程調度程序才將處理機分配給其他進程。
[1]
先來先服務關鍵要領
按照進程進入就緒隊列的先後順序調度並分配處理機執行。先來先服務調度算法是一種非搶佔式的算法,先進入就緒隊列的進程,先分配處理機運行。一旦一個進程佔有了處理機,它就一直運行下去,直到該進程完成工作或者因為等待某事件發生而不能繼續運行時才釋放處理機。
(2)調度退出隊列時從相應隊列首開始順序掃描,將相關的JCB或PCB調度移出相應隊列。
先來先服務系統模型
這裏 ,我們假定該系統模型中只有一個服務器 S.設新顧客到達等待隊列的時間與系統的當前狀態、以前的顧客到達時間都無關,也就是新顧客到達系統的時間是服從泊松分佈的.同時設服務器 S為顧客提供服務的概率也服從泊松分佈.
[2]
先來先服務響應時間計算
(1) 單位時間顧客到達的平均值和顧客被服務的平均值
因顧客到達系統的時間服從泊松分佈,設 λ為到達率 ,
單位時間內顧客到達的期望值 ,即算術平均值為 :
即單位時間內顧客到達的平均值等於其到達率 .
(2)兩個連續到達的顧客之間的平均時間間隔和服務器服務時間的平均值
將上述單位時間換成任意時間 t,可得到在已知時間 t內 x個顧客到達的概率,從而 ,t時間內至少到達一個顧客的概率也可知。
如果把時間 t看成是固定的時間間隔 ,則有在任何時間間隔 t內至少有一個顧客到達的概率和t時間內至少到達一個顧客的概率相等,這個概率和上一次顧客到達的時刻無關,這個特性稱為無記憶特性或馬爾可夫性質.
根據概率P(x) , 可知其密度函數和t 的期望值。
(3)系統在穩定狀態下響應時間的計算
設 Si為系統的一個狀態,表示等待服務的隊列中有 i-1個顧客,服務器中有 1個顧客存在.再設系統在 t時間內處於狀態Si的概率為Pi(t).
系統在穩定狀態下,系統內不存在顧客的概率為 1 -ρ,而系統內存在顧客的概率為ρ.系統內顧客的算術平均值是:
上述按FCFS方式排列和調度 ,並只有一個服務器的系統稱為M/M/1系統 .第一個字母M表示顧客到達時間間隔是指數分佈 ,具有馬爾可夫性質 ,第二個字母 M表示從服務器離開的顧客的時間間隔服從指數分佈 ,具有馬爾可夫性質 ,第三個數字 1表示只有一個服務器.
設響應時間 R為從顧客到達等待隊列後開始到離開服務器的時間.系統進入穩定狀態之後 ,系統中的顧客數 n和平均響應時間 R 之間存在一個非常簡單的關係:n =λR , λ為顧客的平均到達率.可以求出M/M/1系統的平均響應時間為:
R=n/λ=
·(1/λ)=1/μ(1-ρ)
由此可以看出 ,M/M/1系統的服務性能是由 ρ決定的.如果 ρ趨近 1,即 λ趨近 μ,則響應時間急劇增大 ,系統性能變差.而當 ρ小於 1/2時 ,等待隊列中為空的可能性較大 ,因為平均響應時間小於平均服務時間的2倍 .
[2]
先來先服務對短作業影響
設短作業的到達率和服務率分別為(λ1, μ1),長作業的到達率和服務率為(λ2, μ2),且兩者都服從泊松分佈 ,則 二者的合成仍是泊松過程 ,
一般來説,短作業的服務時間1/μ1遠小於長作業1/μ2,先來先服務調度策略的響應時間R為:
R=n/λ=
·(1/λ)=1/μ(1-ρ),其中λ=λ1+λ2,μ=μ1+μ2.
先來先服務優缺點
有利於長作業(進程)而不利於短作業(進程)
有利於CPU繁忙型作業(進程)而不利於I/O繁忙型作業(進程)
- 參考資料
-
- 1. 湯小丹,梁紅兵,哲鳳屏,湯子瀛.計算機操作系統.西安:西安電子科技大學出版社,2014:89-90
- 2. 先來先服務(FCFS)調度算法響應時間的計算 .知網[引用日期2016-11-19]