FCFS (First Come First Served – İlk Gelen Önce) Algoritması
Proseslerin eş öncelikli olarak ele alındığı ve hazır (read) kuyruğuna geliş sırasında işletildiği, çok yalın bir planlama algoritmasıdır. Bir prosesin, sisteme ilk kez sunulma, başlatılan bir giriş/ çıkış işleminin sonlanması, zamanuyumlamanın gerçekleşmesi gibi herhangi bir nedenle hazır kuyruğuna bağlanması gerektiğinde, bu algoritma gereğince, kuyruğa sonuncu öge olarak bağlanır. İşletilmekte olan prosesin, kendi istemiyle CPU’yu bırakması sonucu, kuyruk başında yer alan proses CPU’ya anahtarlanır.
İlk gelen önce algoritması, Proseslerin eş öncelikli olması nedeniyle kesintili bir algoritma değildir. Gerçekleştirimi çok yalın ve kısa bir biçimde yapılabilen bu algoritma, yönetimini üstlendiği tüm prosesleri, niteliklerini gözetmeksizin aynı öncelikle ele alması nedeniyle, genelde yüksek başarım sağlayan bir algoritma değildir.
Örnek 1:
Proseslerin, P1, P2, P3 sırasıyla geldiğini varsayalım.Gannt Grafiği;
Bekleme süresi; P1 = 0; P2 = 24; P3 = 27
Ortalama bekleme süresi; ( 0 + 24 + 27 ) / 3 = 17
Proseslerin, P2, P3, P1 sırasıyla geldiğini varsayalım.Gannt Grafiği;
Bekleme süresi; P1 = 6; P2 =0; P3 = 3
Ortalama bekleme süresi; ( 6 + 0 + 3 ) / 3 = 3
Görüleceği üzere, FCFS algoritmasında ortalama bekleme süresi daima minimum olmayabilir. Çünkü görevlerin geliş sırasına bağımlıdır.
Örnek 2:
Bekleme sırasına giren ilk proses P1’dir. Bekleme sırasından çıkarılan P1 işlemciye yüklenir ve işlemci 7 birim zaman boyunca P1’i çalıştırır.
Bu sırada geçen 1 birimlik zaman içerisinde P0, 2 birimlik zamanın ardından P3 ve 7 birimlik zamanın ardından P2 prosesleri bekleme sırasına giriş yapar. Bekleme sırasına giriş yapan her proses bu sıranın en sonuna eklenir. Oluşturulan bekleme sırası {P0, P3, P2}. P1 işlemciden çıktığı anda sırada bekleyen ilk proses P0, işlemciye alınır.
P0 işlemciye alındıktan sonra geçen 1 birimlik zaman içerisinde bekleme sırasına P4 girer ve bu proses sıranın en sonuna eklenir. Yeni bekleme sırası {P3, P2, P4}. P0 işlemciden çıktığı anda sırada bekleyen ilk proses P3, işlemciye alınır.
Önceki adımlarda olduğu gibi işlemci sırada bekleyen prosesleri işlem süreleri boyunca çalıştırmaya devam eder.
Bekleme süresi;
P0 prosesin bekleme sırasına giriş yapması gereken zaman proses tablosunda görüldüğü üzere 1 birim zamandır ancak P0’ın işlemciye 7 birim zamanda girmiştir. Bu sebepten dolayı P0’ın bekleme süresi (7-1) 6 birim zaman olarak kaydedilir.
P1 prosesin bekleme sırasına giriş ve işlemciye giriş zamanları aynı olduğu için P1’de herhangi bir gecikme söz konusu olmamıştır. Bu sebepten dolayı gecikme zamanı 0 olur.
P2 prosesin işlemciye alınma zamanı tabloda 7 olarak verilmiştir ancak oluşan gecikmeden ötürü P2 işlemciye 15 birim zamanda girmiştir. P2’nin bekleme süresi (15-7) 8 birimdir.
P3 prosesin işlemciye alınma zamanı tabloda 2 olarak verilmiştir ancak oluşan gecikmeden ötürü P3 işlemciye 12 birim zamanda girmiştir. P3′ün bekleme süresi (12-2) 10 birimdir.
P4 prosesin işlemciye alınma zamanı tabloda 8 olarak verilmiştir ancak oluşan gecikmeden ötürü P4 işlemciye 17 birim zamanda girmiştir. P4′ün bekleme süresi (17-8) 9 birimdir.
Ortalama bekleme süresi;
İşlemciye giren her prosesin bekleme süresi toplanır ve aritmetik ortalamaları alınır:
(6+0+8+10+9) / 5 = 6.6 birim
Örnek 3:
Bekleme süresi; P0 = 0; P1 = (3-2)=1; P2 = (9-4)=5; P3 = (13-6)=7; P4 = (18-8)=10
Ortalama bekleme süresi; ( 0 + 1 + 5 + 7 + 10) / 5 = 4.6
<< Planlama Algoritmaları | LIFO (Last In First Out – Son Gelen Önce) Algoritması >>
