En erken son teslim tarihi ilk zamanlama - Earliest deadline first scheduling

En erken son teslim tarihi ( EDF ) veya en az süre, işlemleri bir öncelik kuyruğuna yerleştirmek için gerçek zamanlı işletim sistemlerinde kullanılan dinamik bir öncelik zamanlama algoritmasıdır . Bir zamanlama olayı meydana geldiğinde (görev biter, yeni görev serbest bırakılır, vb.), son tarihine en yakın süreç için kuyruk aranır. Bu işlem, yürütme için planlanacak bir sonraki işlemdir.

EDF, şu anlamda, önleyici tek işlemciler üzerinde en uygun zamanlama algoritmasıdır: her biri bir varış zamanı, bir yürütme gereksinimi ve bir son tarih ile karakterize edilen bağımsız işlerin bir koleksiyonu , her şeyi sağlayacak şekilde (herhangi bir algoritma tarafından) programlanabilirse. İşler son teslim tarihlerine kadar tamamlanırsa, EDF bu iş koleksiyonunu, hepsinin son teslim tarihine kadar tamamlanması için planlayacaktır.

Dönemlerine eşit terminleri olan periyodik süreçleri çizelgeleme ile EDF'nin kullanım sınırı %100'dür. Bu nedenle, schedulability testi için EDF olduğu:

${\displaystyle U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq 1,}$

burada süreçlerin en kötü hesaplama süreleri ve bunların ilgili varışlar arası süreleri (göreceli sürelere eşit olduğu varsayılır). ${\displaystyle \sol\{C_{i}\sağ\}}$${\görüntüleme stili n}$${\displaystyle \sol\{T_{i}\sağ\}}$

Yani EDF, toplam CPU kullanımının %100'den fazla olmaması koşuluyla tüm son tarihlerin karşılandığını garanti edebilir . Hız monoton çizelgeleme gibi sabit öncelikli çizelgeleme teknikleriyle karşılaştırıldığında , EDF daha yüksek yüklemelerde sistemdeki tüm termin tarihlerini garanti edebilir.

EDF aynı zamanda önleyici olmayan tek işlemciler üzerinde en uygun zamanlama algoritmasıdır, ancak yalnızca boşta kalma süresine izin vermeyen zamanlama algoritmaları sınıfı arasındadır. Sürelerine eşit son tarihleri ​​olan periyodik süreçleri planlarken, EDF için yeterli (ancak gerekli olmayan) bir programlanabilirlik testi şu şekilde olur:

${\displaystyle U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq {1-p},}$

Burada p verilen olmayan preemption için ceza temsil eder, maks / dak . Bu faktör küçük tutulabilirse , düşük uygulama yüküne sahip olduğundan , önleyici olmayan EDF faydalı olabilir. ${\displaystyle \sol\{C_{i}\sağ\}}$ ${\displaystyle \sol\{T_{i}\sağ\}}$

Bununla birlikte, sistem aşırı yüklendiğinde, son teslim tarihlerini kaçıracak olan süreçler dizisi büyük ölçüde tahmin edilemez (bu, aşırı yüklenmenin meydana geldiği tam teslim tarihlerinin ve zamanın bir fonksiyonu olacaktır.) Bu, gerçek zamanlı bir sistem tasarımcısı için önemli bir dezavantajdır. Algoritmanın donanımda uygulanması da zordur ve farklı aralıklarda son teslim tarihlerini temsil etme konusunda zor bir sorun vardır (son tarihler, zamanlama için kullanılan saatin ayrıntı düzeyinden daha kesin olamaz). Şimdiye göre gelecekteki son tarihleri ​​hesaplamak için modüler bir aritmetik kullanılıyorsa, gelecekteki göreli bir son tarihi depolayan alan en azından (("süre" {tamamlanmaya kadar olan en uzun sürenin} * 2) + "şimdi" değerini barındırmalıdır. ). Bu nedenle EDF , endüstriyel gerçek zamanlı bilgisayar sistemlerinde yaygın olarak bulunmaz.

Bunun yerine, çoğu gerçek zamanlı bilgisayar sistemi, sabit öncelikli çizelgeleme (genellikle oran-monoton çizelgeleme ) kullanır. Sabit önceliklerle, aşırı yük koşullarının düşük öncelikli süreçlerin son teslim tarihlerini kaçırmasına neden olacağını, en yüksek öncelikli işlemin ise son teslim tarihini karşılayacağını tahmin etmek kolaydır.

Gerçek zamanlı hesaplamada EDF zamanlaması ile ilgili önemli bir araştırma grubu vardır ; EDF'de süreçlerin en kötü durum tepki sürelerini hesaplamak , periyodik süreçler dışındaki diğer süreç türleriyle uğraşmak ve aşırı yüklenmeleri düzenlemek için sunucuları kullanmak mümkündür.

Örnek

Önleyici bir tek işlemcide programlanmış 3 periyodik işlemi düşünün. Yürütme süreleri ve periyotları aşağıdaki tabloda gösterildiği gibidir:

Bu örnekte, zaman birimleri, programlanabilir zaman dilimleri olarak kabul edilebilir . Son teslim tarihleri, her bir periyodik sürecin kendi periyodu içinde tamamlanması gerektiğidir.

zamanlama diyagramı

Örnek için olası bir programın bir bölümünü gösteren Zamanlama Şeması .

Zamanlama diyagramında, sütunlar zamanın sağa doğru artan zaman dilimlerini temsil eder ve süreçlerin tümü periyotlarına zaman dilimi 0'da başlar. Zamanlama diyagramının değişen mavi ve beyaz gölgesi, renk değişimlerinde son tarihlerle birlikte her işlemin periyodunu gösterir.

EDF tarafından programlanan ilk süreç P2'dir, çünkü süresi en kısadır ve bu nedenle en erken teslim tarihine sahiptir. Benzer şekilde, P2 tamamlandığında, P1 ve ardından P3 programlanır.

Zaman dilimi 5'te, hem P2 hem de P3 aynı son tarihe sahiptir ve zaman dilimi 10'dan önce tamamlanması gerekir, bu nedenle EDF ikisinden birini planlayabilir.

kullanım

Kullanım şöyle olacaktır:

${\displaystyle \left({\frac {1}{8}}+{\frac {2}{5}}+{\frac {4}{10}}\sağ)=\left({\frac {37 }{40}}\sağ)=0.925={\mathbf {92.5\%} }}$

Yana en sık birden sürelerinin 40, zamanlama deseni her 40 zaman dilimleri tekrarlayabilir. Ancak, bu 40 zaman diliminden yalnızca 37'si P1, P2 veya P3 tarafından kullanılır. Kullanım %92,5 ve %100'den fazla olmadığı için sistem EDF ile programlanabilir.

son tarih değişimi

EDF zamanlaması ile istenmeyen termin değişimleri meydana gelebilir. Bir süreç, daha erken bir son teslim tarihine sahip başka bir süreç lehine önceden planlanmış olarak kaldırılmasını önlemek için kritik bir bölüm içindeki paylaşılan bir kaynağı kullanabilir . Bu durumda, zamanlayıcının, kaynağı bekleyen diğer işlemler arasından çalışan işleme en erken son tarihi ataması önemli hale gelir. Aksi takdirde daha erken teslim tarihleri ​​olan süreçler onları kaçırabilir.

Bu, özellikle kritik bölümü çalıştıran işlemin tamamlanması ve kritik bölümünden çıkması için çok daha uzun bir süreye sahipse ve bu da paylaşılan kaynağın serbest bırakılmasını geciktirecekse önemlidir. Ancak süreç, daha erken teslim tarihlerine sahip olan ancak kritik kaynağı paylaşmayan diğerlerinin lehine yine de önceden alınabilir. Bu son teslim tarihi değişimi tehlikesi, sabit öncelikli önleyici çizelgeleme kullanıldığında önceliği tersine çevirmeye benzer .

Hazır kuyruğunda son tarih aramasını hızlandırmak için, kuyruk girişleri son tarihlerine göre sıralanır. Yeni bir sürece veya periyodik bir sürece yeni bir son tarih verildiğinde, daha sonraki bir son teslim tarihi ile ilk süreçten önce eklenir. Bu sayede en erken teslim tarihlerine sahip süreçler her zaman kuyruğun başında olur.

Reneging ile EDF kuyrukları için yoğun trafik analizi

Yenileme ile En Erken-Son Tarih-İlk (EDF) zamanlama ilkesi kapsamında tek sunuculu bir sıranın davranışının yoğun trafik analizinde , süreçlerin son tarihleri ​​vardır ve yalnızca son tarihleri ​​geçene kadar sunulur. Geçen süreler nedeniyle hizmet verilmeyen kalan iş olarak tanımlanan “yenilenen iş” oranı önemli bir performans ölçüsüdür.

Sabit öncelikli zamanlayıcılarla karşılaştırma

Sabit öncelikli bir önleyici çizelgelemenin (FPS) uygulanmasının, EDF gibi dinamik bir öncelik zamanlayıcıdan daha basit olduğu yaygın olarak kabul edilir . Ancak, sabit öncelik altında optimal bir çizelgelemenin maksimum kullanımını karşılaştırırken ( Hız-monotonik çizelgeleme tarafından verilen her iş parçacığının önceliği ile ), EDF %100'e ulaşabilirken Hız-monoton çizelgeleme için teorik maksimum değer yaklaşık %69'dur. .

EDF'nin görevlerin periyodikliği konusunda herhangi bir özel varsayımda bulunmadığını unutmayın; bu nedenle, periyodik ve periyodik olmayan görevlerin programlanması için kullanılabilir.

EDF zamanlamasını uygulayan çekirdekler

EDF uygulamaları, ticari gerçek zamanlı çekirdeklerde yaygın olmasa da, burada EDF uygulayan açık kaynaklı ve gerçek zamanlı çekirdeklerin birkaç bağlantısı:

• SHARK SHaRK RTOS, EDF zamanlaması ve kaynak rezervasyonu zamanlama algoritmalarının çeşitli versiyonlarını uygular
• ERIKA Enterprise , OSEK API'sine benzer bir API ile küçük mikro denetleyiciler için optimize edilmiş bir EDF uygulaması sağlayan ERIKA Enterprise .
• Everyman Çekirdeği Everyman Çekirdeği, kullanıcının yapılandırmasına bağlı olarak ya EDF ya da Son Tarih Monotonik zamanlama uygular.
• MaRTE OS MaRTE OS, Ada uygulamaları için bir çalışma zamanı görevi görür ve EDF dahil olmak üzere çok çeşitli zamanlama algoritmaları uygular.
• AQuoSA projesi EDF zamanlama yetenekleri ile işlem zamanlayıcı zenginleştirmek Linux çekirdeğine bir modifikasyonu oluşturmaktadır. Programlamanın zamanlaması, yukarıdaki zor gerçek zamanlı İşletim Sistemleri durumunda olduğu kadar kesin olamaz, ancak öngörülebilirliği büyük ölçüde artıracak ve böylece multimedya uygulamalarının gerçek zamanlı gereksinimlerini karşılayacak kadar yeterince kesindir. AQuoSA, uygun şekilde tasarlanmış bir erişim kontrol modeli ile bir sistem üzerinde imtiyazsız kullanıcılara kontrollü bir şekilde gerçek zamanlı çizelgeleme olanağı sağlayan birkaç projeden biridir.
• Linux çekirdeği bir erken tarihi ilk uygulama adında vardır ÇIZ SON TARİH sürümü 3.14 beri mevcuttur.
• Gerçek zamanlı zamanlayıcı bağlamında geliştirilen IRMOS Avrupa Projesi Linux çekirdeği için bir çoklu işlemci gerçek zamanlı zamanlayıcı, özellikle zamansal izolasyon için uygun ve aynı zamanda karmaşık çok dişli yazılım bileşenleri ve tüm QoS garanti provizyon olan sanal makineleri . Örneğin, ana bilgisayar işletim sistemi olarak Linux ve hiper yönetici olarak KVM kullanıldığında, IRMOS, bireysel VM'lere zamanlama garantileri sağlamak ve aynı zamanda istenmeyen zamansal müdahaleleri önlemek için performanslarını izole etmek için kullanılabilir . IRMOS, birleşik bir EDF/FP hiyerarşik zamanlayıcıya sahiptir . Dış seviyede, mevcut CPU'larda bölümlenmiş bir EDF zamanlayıcı vardır. Ancak, rezervasyonlar çoklu CPU'dur ve her bir dış EDF rezervasyonuna eklenen iş parçacıklarını (ve/veya süreçleri) programlamak için iç düzeyde çoklu işlemciler üzerinden global FP kullanılır. Konuyla ilgili genel bir bakış ve kısa bir eğitim için lwn.net'teki bu makaleye de bakın .
• Xen'in bir süredir bir EDF zamanlayıcısı var. Adam sayfası kısa bir açıklama içerir.
• Bell Labs Plan 9 işletim sistemi EDFI bir şekilde birleştiren "hafif gerçek zamanlı zamanlama protokolü bu son tarih miras üzerinde paylaşılan kaynakları ile birleştirir EDF."
• RTEMS : EDF zamanlayıcı 4.11 sürümünde mevcut olacaktır. RTEMS Süper Çekirdek
• Litmus-RT , çok işlemcili gerçek zamanlı zamanlama ve senkronizasyona odaklanan Linux çekirdeğinin gerçek zamanlı bir uzantısıdır. Gerçek zamanlı algoritma seti, Partitioned-EDF, Global-EDF ve Clustered-EDF zamanlayıcılarını içerir.

Ayrıca bakınız

• Dinamik öncelik zamanlaması

Referanslar