Yazan : Şadi Evren ŞEKER

Bir zamanlama (scheduling) algoritmasıdır. Özellikle işletim sistemi tasarımında işlemcinin (CPU) zamanlamasında kullanılan meşhur algoritmalardan birisidir. Bu algoritmaya göre sırası gelen işlem, işlemcide işi bitmese bile belirli bir zaman biriminden sonra (time quadrant) işlemciyi terk etmek zorundadır.

Bu sayed işletim sisteminde kıtlık (Starvation) olma ihtimali kalmaz. Çünkü hiç bir zaman bir işlemin CPU’yu alıp diğer işlemlere sıra gelmesini engellemesi mümkün olmaz.

Örneğin aşağıda süreleri verilen işlemlerin aynı anda bekleme sırasına (Ready queue) geldiğini düşünelim ve round robin algoritmasına göre nasıl bir sıra ile çalıştırılacağına bakalım.

İşlem

CPU Zamanı

A

10

B

15

C

7

Yukarıda verilen bu işlemlerin Round Robin algoritmasına göre CPU’da çalışma süreleri ve sırasıyla CPU’da yer değiştirmeleri (context switch)  aşağıda verilmiştir:

Zaman

İşlem

Çalışma

Kalan

0

A

3

7

3

B

3

12

6

C

3

4

9

A

3

4

12

B

3

9

15

C

3

1

18

A

3

1

21

B

3

6

24

C

1

0

25

A

1

0

26

B

3

3

29

B

3

0

Yorumlar

  1. Şadi Evren ŞEKER Article Author

    Tam olarak nasıl bir koda ihtiyacınız var? Yani simülasyon şeklinde round robin algoritmasını simüle etmeniz mi gerekiyor?

    Simülasyonda bile kullanılacak kütüphanelere göre çok çeşitlilik var. Mesela pthread ile bir zamanlar yazmıştım sanırım. Basitçe threadlerden birisi işletim sistemininin çekirdeği (kernel) simüle ediyor, diğer gelen iler ise bu thread tarafından çalıştırılıyor. Thread sleep() fonksiyonu sayesinde belirli aralarda uyandırlıp çalışıtırılıyor veya uyutuluyor. Neticede bu "belirli aralıklar" sizin time quadrantınız olmuş oluyor. Biraz gayret gösterip basit şekli ile kodlarsanız yazmanıza yardımcı olmaya çalışırım.

    Başarılar

  2. Muhammed Koyuncu

    Merhaba Hocam şu soruyu cevabını anlatabilir misiniz?
    İşlem no Geliş Süresi Servis Süresi
    1 0 3
    2 2 6
    3 4 4
    4 6 5
    5 8 2

    RounRobin algoritması kullanılarak Zaman Dilimi=1 seçilirse 4 numaralı işin bitim zamanı nedir?

  3. bilgisaybilgisay

    Merhaba Muhammed Bey,

    Sorunun çözümü aşağıdaki şekilde yapılabilir:

    Zaman Çalışan işlem (Bu işlem çalıştıktan sonra kalan)
    0 1(2)
    1 1(1)
    2 2(5)
    3 1(0) --> P1 Bitti
    4 3(3)
    5 2(4)
    6 4(4)
    7 3(2)
    8 5(1)
    9 2(3)
    10 4(3)
    11 3(1)
    12 5(0) --> P5 bitti
    13 2(2)
    14 4(2)
    15 3(0) --> P3 bitti
    16 2(1)
    17 4(1)
    18 2(0) --> P2 bitti
    19 4(0) --> P4 bitti

    dolayısıyla P4'ün bitiş zamanı 20'dir. Yani P4, 19 zamanına başlarken 1 süre kalmış olarak başlar, 19 zamanını bitirince p4'de bitmiş olur (20 zamanının başlangıcında).
    Sırasıyla işlemlerin bitiş zamanları aşağıadki şekilde verilebilir:

    P1 -> 4
    P2 -> 19
    P3 -> 16
    p4 -> 20
    p5 -> 12

    Burada dikkat edilecek olan nokta, verilen işlem sürelerinin işe başlanan süreler olduğudur. Mesela 0 zamanında henüz hiçbirşey yapılmamış durumda, 0 zamanında gelen P1'in 1 birim çalışması için 1 birim zaman geçmesi gerekir.

    Mesela elimizde bir tane işlem (process) olsa ve 0 zamanında gelse ve çalışma süresi 1 olsa, bitişi 1 zamanında olacaktır 0 değil. 1 zaman geçip çalıştıktan sonra bitti diyebiliriz. Aynı şekilde P4'de 19. zamana başlandığında hala 1 zaman çalışma ihtiyacı bulunmaktadır, 19. zamana girilir P4 son 1 zamanını çalıştırır ve biter, şu durumda P4'ün bitişi 20. zamandadır.

  4. Bartuhan

    Bana şu sorunun çözümünde yardımcı olursanız sevinirim
    Proses geliş süresi işlem süresi
    P1 0 8
    P2 1 5
    P3 2 4
    P4 3 3
    P5 4 2

    1. Şadi Evren ŞEKERŞadi Evren ŞEKER

      round robin algoritmasının çalışmasını görebilmek için değiştirme zamanının (time quadrant) verilmesi gerekir. Soruda bu kısım eksik olduğu için tam bir çözüm elde edilemez. Ancak sorunuza cevap olması için tq=3 olarak alalım ve çözmeye çalışalım.

      öncelikle p1 çalışacak çünkü sistede bir tek o var.
      0 P1
      3 p2
      6 p3
      9 p4
      12 p5 (burada p5 2 süresine ihtiyaç duyduğu için tq=3'ten önce bitecek)
      14 p1
      17 p2 (yine p2'den 2 birim iş kaldığından erken bitecek)
      19 p3
      20 p1 (p4 ve p5 daha önce bittiler)
      22 bütün işlemler bitmiştir.

      Başarılar

  5. student

    Merhaba, şöyle bir soru var : "Bir sistemde t=0 anında dört tane process A,B,C,D işleri, işlemcide çalışmak için hazır durumda kuyrukta beklemektedir.
    Kuyrukta sırayla A B C D işi yer almaktadır (ilk çalıştırılacak olan A dır). A :200 ms , B:300 ms, C:60 ms, D:120 ms kullanmak istemektedir.
    Sistemde round-robin zaman scheduling kullanılmaktadır. Zaman dilimi (time quantum):50 ms ise her bir iş için bitiş zamanını ms cinsinden yazınız."
    Bu soruya cevap olarak aşağıdaki çizelgeyi hazırladım doğru olup olmadığını kontrol edebilir misiniz ? Teşekkür ederim
    Sıra İşlem Zaman Açıklama
    0 A 50 kalan:150
    1 B 100 kalan:250
    2 C 150 kalan:10
    3 D 200 kalan:70
    4 A 250 kalan:100
    5 B 300 kalan:200
    6 C 310 C biter, bitiş zamanı:310 ms
    7 D 360 kalan:20
    8 A 410 kalan:50
    9 B 460 kalan:150
    10 D 480 D biter, D bitiş zamanı:480 ms
    11 A 530 A biter, A bitiş zamanı:530 ms
    12 B 580 kalan:100
    13 B 630 kalan:50
    14 B 680 B biter, B bitiş zamanı:680 ms

Bir Cevap Yazın

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


+ 5 = oniki