Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinin çeşitli alanlarında kullanılan bir yaklaşımdır. Bu yaklaşıma göre bir kaynak veya bir isıraya ilk gelenin ilk önce işini bitirerek çıkması hedeflenir.

Örneğin CPU Scheduling (İşlemci zamanlama) problemi sırasında işlemciye gelen işlemlerin hangi sıra ile çalışacağı bu algoritmaya göre belirlenirse ilk gelen iş bitmeden ikinci iş başlayamaz.

Bir sıra (queue) için benzeri durum düşünülürse sıraya ilk giren ilk çıkar (first in first out, FIFO fifo)

İşlemci zamanlama (CPU Scheduling) algoritması olarak kullanılmasını aşağıdaki örnek üzerinden anlamaya çalışalım:

Örneğin işlemciye aşağıdaki işlemler verilen sıra ile gelmiş olsunlar ve yanlarında verilen zaman kadar işlemcide çalışarak bitecek olsunlar:

İşlem CPU Zamanı
A 10
B 15
C 7

Yukarıdaki bu işlemlerin çalışma sırası ve zamanları aşağıda verildiği şekildedir:

Zaman İşlem Çalışma Kalan
0 A 10 0
10 B 15 0
25 C 7 0

Görüldüğü üzere kesintisiz (nonpreemptive) bir zamanlama algoritması olan FSFC algoritmasında bir işlem, işlemci tarafından kabul edildikten sonra bitene kadar başka bir işlem araya giremez.

Okuyucu bu çalışma tablosunu round robin algoritmasındaki tablo ile karşılaştırarak farkı daha iyi anlayabilir.

Yorumlar

  1. Caner Aslan

    (Resimdeki soruda öncelik sıralaması aynı olan 2 proses bulunmaktadır bu 5 prosesin fcfs,round robin,en kısa iş ilk önce,kalan zamanı az olana göre sıralamasını ve ortalama bekleme sürelerini bulabilir misiniz ?) Acil cevap verirseniz çok önemli hocam sınavım var. Şimdiden teşekkür ederim.

  2. Caner Aslan

    Bu arada fcfs ‘de öncelik derecesi önemli midir ?Geliş zamanları aynı olan 5 prosesin sadece öncelik dereceleri farklıya bunu fifo’ya göre nasıl sıralarız ?

  3. Şadi Evren ŞEKER

    fifo veya fcfs için bu soruda istenen işlemden başlanabilir. Yani işlemler aynı sırada geldiği için dispatcher istediği işlemi seçerek (rasgele) başlayabilir ve sonraki işlem de yine aynı zamanda geldikleri için rasgele seçilecek ve sonraki de… böylece 5 işlem rasgele seçilerek çalışacaktır. Yani fcfs için istediğiniz işlemi seçip başlayıp sonrakileri de keyfi olarak seçerek devam edebilirsiniz.

    Sizin için problem olduğunu düşündüğüm durum aynı önceliğe sahip olması durumu. Bu durum SJF zamanlama yöntemi (iki adet aynı zamana sahip iş olduğu için p2 ve p4 için 1 zaman) veya öncelik zamanlamasına göre (iki adet aynı önceliğe sahip iş olduğu için p1 ve p3 için 3 öncelik) sorun olabilir.

    Bu tip eşit öncelik durumlarında rasgele bir seçim yapılarak çalıştırılır. Yani mesela SJF yönteminde en kısa işi ilk çalıştıracağız ve elimizde 1,1,2,5,10 uzunluğunda işler var, burada iki tane 1 olduğuna göre hangisini önce başlatacağız? derseniz hangisi olduğu önemli değildir istediğinizi seçebilirsiniz.

    Burada belki ufak bir not, bazı kitaplarda listedeki sıralamaya göre önce gelen çalıştırılıyor (mesela listede p2, p4’ten önce yazıldığı için bunu seçerek yazan kitaplar var ama teorik olarak aralarında fark olmadığını kabul edebiliriz.

    Sorunuzun çözümüne gelince SJF için aşağıdaki şekilde çözelim:

    p2, p4, p3, p5 , p1 sırası ile çalışacaklardır (p4, p2, p3, p5, p1 sırası da doğrudur). ortalama bekleme için de hesap yapmamız gerekiyor.

    bekleme zamanları (waiting time)
    p2 = 0
    P4 = 1 (p2’nin bitmesini bekleyeceği için 1 zaman)
    P3 = 2 (p2 ve p4’ün bitmesini bekleyeceği için 1+1 = 2)
    p5 = 1 + 1 + 2 = 4
    P1 = 1 + 1 + 2 + 5 = 9
    toplam bekleme süresi = 0 + 1 + 2 + 4 + 9 = 16
    ortalama bekleme süresi 16 / 5 = 3.2 olarak bulunacaktır.

    çözümün başında “p4, p2, p3, p5, p1 sırası da doğrudur” demiştik, dilerseniz bu sıralamaya göre de ortalama bekleme süresini hesaplayabilirsiniz ve sonucun aynı çıktığını göreceksiniz.

    diğer zamanlama yöntemlerine göre de benzer şekilde çözmeyi deneyin sorunuz olursa veya çözümünüzü buradan paylaşırsanız bakıp cevaplamaya çalışırım.

    sınavınızda başarılar.

  4. nur

    Merhaba, iş sıralaması (fifo, en kisa iş. ..) ile ilgili videonuz var mi? Weating time kismini anlayamadim ve aciklamali bir sekilde anlatiminiz var mi ?

nur için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir