先來先服務

先來先服務的調度算法：最簡單的調度算法，既可以用於作業調度 ，也可以用於程序調度，當作業調度中採用該算法時，系統將按照作業到達的先後次序來進行調度，優先從後備隊列中，選擇一個或多個位於隊列頭部的作業，把他們調入內存，分配所需資源、創建進程，然後放入“就緒隊列”,直到該進程運行到完成或發生某事件堵塞後，進程調度程序才將處理機分配給其他進程。 ^[1] 

按照進程進入就緒隊列的先後順序調度並分配處理機執行。先來先服務調度算法是一種非搶佔式的算法，先進入就緒隊列的進程，先分配處理機運行。一旦一個進程佔有了處理機，它就一直運行下去，直到該進程完成工作或者因為等待某事件發生而不能繼續運行時才釋放處理機。

（1）系統只要有按FIFO規則建立的後備作業隊列或就緒進程隊列即可，就是一個作業控制塊JCB或進程控制塊PCB加入隊列時加在相應隊列末尾。

（2）調度退出隊列時從相應隊列首開始順序掃描，將相關的JCB或PCB調度移出相應隊列。

設處理機或系統資源為服務器,一個進程或一個作業為享受該服務器服務的顧客.這些顧客按 FCFS 方式排隊享受服務的系統模型為:

這裏 ,我們假定該系統模型中只有一個服務器 S.設新顧客到達等待隊列的時間與系統的當前狀態、以前的顧客到達時間都無關,也就是新顧客到達系統的時間是服從泊松分佈的.同時設服務器 S為顧客提供服務的概率也服從泊松分佈. ^[2] 

因顧客到達系統的時間服從泊松分佈,設 λ為到達率 ,

單位時間內顧客到達的期望值 ,即算術平均值為 :

即單位時間內顧客到達的平均值等於其到達率 .

同理,被服務器 S服務的顧客個數的平均值也等於其服務率 . ^[2] 

將上述單位時間換成任意時間 t,可得到在已知時間 t內 x個顧客到達的概率,從而 ,t時間內至少到達一個顧客的概率也可知。

如果把時間 t看成是固定的時間間隔 ,則有在任何時間間隔 t內至少有一個顧客到達的概率和t時間內至少到達一個顧客的概率相等,這個概率和上一次顧客到達的時刻無關,這個特性稱為無記憶特性或馬爾可夫性質.

根據概率P（x） , 可知其密度函數和t 的期望值。

即兩個連續到達的顧客之間的平均時間間隔為 1/ λ.同理,可得服務器服務時間的平均值為1/ μ.顯然,只有當 1/ μ<1/ λ也就是λ<μ時系統才是穩定的.否則,等待服務隊列將無限增長 . ^[2] 

設 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.

由於 λ和ρ中包含了λ1, λ2, μ1, μ2,所有作業的平均響應時間相同 ,從而,短作業在系統中的駐留平均時間與長作業的駐留平均時間相同 , 這對短作業是不利的. ^[2] 

有利於長作業（進程）而不利於短作業（進程）

有利於CPU繁忙型作業（進程）而不利於I/O繁忙型作業（進程）