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 |
sadece teşekkür ederim saol:):)
iyi günler. SPF schedulingi koymanız mümkünmü?
SPF (shortest process first) zamanlaması zaten sitede SJF (shortest job first) zamanlaması olarak yayınlanmıştır. Bağlantısı aşağıdadır:
http://www.bilgisayarkavramlari.com/2008/11/19/en-kisa-is-ilk-shortest-job-first/
başarılar
Şadi Bey Merhaba;
Bu problemin ortalama zamanını hesaplamasını nasıl yapıyoruz?
sanırım işlemci zamanlamasını soruyorsunuz, aşağıdaki bağlantıya bir bakın eksik / anlaşılmayan birşey olursa ve yazarsanız sevinirim cevaplamaya çalışırım.
http://www.bilgisayarkavramlari.com/2010/03/20/islemci-zamanlari-cpu-timing/
başarılar
teşekkürler
iyi günler hocam bana roun robin in java kodu lazım yarmdcı olablrmsnz acaba ?
Hocam round-robin in c kodu lazim yardimci olabilirmisiniz acaba ?
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
Evet hocam ama tread le degil proses ile kid yazmam gerekiyor
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?
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.
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
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
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