Round-robin planlama - Round-robin scheduling

Bu makale, bilgi işlemde planlama hakkındadır. Diğer kullanımlar için bkz. Round-robin (belirsizliği giderme).
Quantum = 3 ile bir Round Robin önleyici zamanlama örneği.

Round-robin (RR), tarafından kullanılan algoritmalardan biridir süreç ve ağ planlayıcıları içinde bilgi işlem.[1][2]Terim genellikle kullanıldığı için, zaman dilimleri (zaman miktarı olarak da bilinir)[3] her işleme eşit bölümlerde ve döngüsel sırayla atanır, tüm süreçleri öncelik (Ayrıca şöyle bilinir döngüsel yürütme ). Round-robin planlaması basittir, uygulaması kolaydır ve açlık -Bedava. Round-robin çizelgeleme, bilgisayar ağlarında veri paketi çizelgeleme gibi diğer çizelgeleme problemlerine uygulanabilir. O bir işletim sistemi kavram.

Algoritmanın adı, sıralı diğer alanlardan bilinen, her bir kişinin sırayla bir şeyden eşit pay aldığı ilke.

Süreç planlama

Ana makale: Süreç planlayıcı

Süreçleri adil bir şekilde planlamak için, bir döngüsel programlayıcı genellikle zaman paylaşımı, her işe bir zaman aralığı vermek veya kuantum[4] (CPU zamanı ödeneği) ve o zamana kadar tamamlanmadığı takdirde işi durdurma. Bu işleme bir sonraki zaman aralığı atandığında iş devam ettirilir. Süreç, atfedilen kuantum zamanı sırasında durumunu sonlandırır veya bekleme durumuna değiştirirse, programlayıcı yürütmek için hazır kuyruğundaki ilk işlemi seçer. Zaman paylaşımının yokluğunda veya miktar işlerin boyutlarına göre büyükse, büyük işler üreten bir süreç diğer süreçlere göre tercih edilirdi.

Round-robin algoritması, zaman kotası sona erdiğinde zamanlayıcı işlemi CPU'dan çıkarmaya zorladığından, önceden belirlenmiş bir algoritmadır.

Örneğin, zaman aralığı 100 milisaniyeyse ve job1 Tamamlanması 250 ms'lik bir süre alır, sıralı zamanlayıcı işi 100 ms sonra askıya alır ve diğer işlere CPU'daki sürelerini verir. Diğer işler eşit paylara sahip olduktan sonra (her biri 100 ms), job1 başka bir tahsisat alacak İşlemci zaman ve döngü tekrarlanacaktır. Bu işlem, iş bitene kadar devam eder ve CPU'da daha fazla zamana gerek kalmaz.

  • Job1 = 250 ms'yi tamamlamak için toplam süre (kuantum 100 ms).
  1. İlk tahsis = 100 ms.
  2. İkinci tahsis = 100 ms.
  3. Üçüncü tahsis = 100 ms ancak job1 50 ms sonra kendini sonlandırır.
  4. Toplam CPU süresi job1 = 250 ms

Round-robin planlamasını anlamak için 100 ms'lik kuantum süresiyle sürecin varış zamanı ve yürütme zamanını içeren aşağıdaki tabloyu göz önünde bulundurun:

İşlem adıVarış zamanıYürütme zamanı
P00250
P150170
P213075
P3190100
P4210130
P535050
Round Robin Zamanlama

Diğer bir yaklaşım, kuantum boyutu sürecin boyutuyla orantılı olacak şekilde tüm süreçleri eşit sayıda zamanlama kuantumuna bölmektir. Dolayısıyla tüm süreçler aynı anda biter.

Ağ paketi planlaması

Ana makale: Ağ planlayıcı

İçinde en iyi çaba paket değiştirme ve diğeri istatistiksel çoklama, round-robin planlama, bir alternatif olarak kullanılabilir. ilk gelen alır kuyruk.

Döngüsel zamanlama sağlayan bir çoklayıcı, anahtar veya yönlendirici, her veri akışı için ayrı bir kuyruğa sahiptir; burada bir veri akışı, kaynağı ve hedef adresi ile tanımlanabilir. Algoritma, kuyrukta veri paketleri bulunan her etkin veri akışının, paketleri periyodik olarak tekrarlanan bir sırayla paylaşılan bir kanalda aktarırken sırayla almasına izin verir. Planlama iş tasarrufu yani bir akış paketlerden çıkarsa, bir sonraki veri akışı onun yerini alacaktır. Bu nedenle programlama, bağlantı kaynaklarının kullanılmamasını önlemeye çalışır.

Round-robin planlama sonuçları max-min adalet en uzun süre beklemiş olan veri akışına programlama önceliği verildiğinden, veri paketleri eşit boyutta ise. Veri paketlerinin boyutunun bir işten diğerine büyük ölçüde değişmesi arzu edilmeyebilir. Büyük paketler üreten bir kullanıcı, diğer kullanıcılara göre tercih edilir. Bu durumda adil kuyruk tercih edilebilir.

Garantili veya farklılaştırılmış hizmet kalitesi sunuluyorsa ve yalnızca en iyi şekilde iletişim sağlanmıyorsa, defisit round robin (DRR) çizelgeleme, ağırlıklı yuvarlak robin (WRR) planlama veya ağırlıklı adil kuyruk (WFQ) düşünülebilir.

İçinde Çoklu erişim Paylaşılan bir fiziksel ortama birkaç terminalin bağlandığı ağlar, döngüsel programlama tarafından sağlanabilir jetonlu geçiş kanal erişimi gibi şemalar jeton yüzük, veya tarafından yoklama veya bir merkezi kontrol istasyonundan kaynak ayırma.

Birçok istasyonun bir frekans kanalını paylaştığı merkezi bir kablosuz paket radyo ağında, bir merkezi baz istasyonundaki bir programlama algoritması, mobil istasyonlar için sıralı bir şekilde zaman dilimleri ayırabilir ve adalet sağlayabilir. Ancak, eğer bağlantı uyarlaması kullanıldığında, belirli bir miktardaki verinin "pahalı" kullanıcılara iletilmesi diğerlerine göre çok daha uzun zaman alacaktır çünkü kanal koşulları farklıdır. Kanal koşulları iyileştirilene kadar iletimle beklemek veya en azından daha ucuz kullanıcılara programlama önceliği vermek daha verimli olacaktır. Round-robin planlaması bunu kullanmaz. Daha yüksek verim ve sistem spektrumu verimliliği kanala bağlı programlama, örneğin bir orantılı olarak adil algoritma veya maksimum verim planlama. İkincisinin istenmeyen olarak nitelendirildiğini unutmayın. açlık planlaması. Bu tür programlama, dairesel kuyruk veri yapısı aracılığıyla uygulanabilen bilgisayarlardaki İşletim Sistemleri için en temel algoritmalardan biridir.

Ayrıca bakınız

Referanslar

  1. ^ Arpacı-Dusseau, Remzi H .; Arpacı-Dusseau, Andrea C. (2014), İşletim Sistemleri: Üç Kolay Parça [Bölüm: Planlamaya Giriş] (PDF), Arpacı-Dusseau Kitapları
  2. ^ Guowang Miao, Jens Zander, Ki Won Sung ve Ben Slimane, Mobil Veri Ağlarının Temelleri, Cambridge University Press, ISBN  1107143217, 2016.
  3. ^ Stallings, William (2015). İşletim Sistemleri: İç Parçalar ve Tasarım İlkeleri. Pearson. s. 409. ISBN  978-0-13-380591-8.
  4. ^ Silberschatz, Abraham; Galvin, Peter B .; Gagne, Greg (2010). "Süreç Planlama". İşletim Sistemi Kavramları (8. baskı). John Wiley & Sons (Asya). s. 194. ISBN  978-0-470-23399-3. 5.3.4 Round Robin Planlama

Dış bağlantılar