Geri Dön

Gerçek zamanlı sistemlerde iş sıralama

Scheduling in real-time systems

  1. Tez No: 39283
  2. Yazar: VAHİDE UNUTMAZ
  3. Danışmanlar: DOÇ.DR. BÜLENT ÖRENCİK
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 1993
  8. Dil: Türkçe
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Belirtilmemiş.
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 111

Özet

ÖZET GERÇEK ZAMANLI SİSTEMLERDE İŞ SIRALAMA Gerçek zamanlı bilgisayar sistemleri, uçuş sistemlerinden nükleer enerji santrallarına, otomobilden fabrikalara geniş ve farklı düzeyde kontrol işlemlerinde kullanılırlar. Bu sistemlerde, sistem işlemlerinin doğruluğu sadece işlem sonucuna değil, aynı zamanda sonuçların hesaplandığı süreye de bağlıdır. Gerçek zamanlı sistemler, sonuç üretme sürelerine göre, Esnek Gerçek Zamanlı Sistemler ve Katı Gerçek Zamanlı Sistemler olmak üzere ikiye ayrılır. Esnek gerçek zamanlı sistemlerde, işlerin mümkün olduğu kadar kısa sürede tamamlanması istenir. Ancak kesin bir zaman kısıtlaması yoktur. Katı gerçek zamanlı sistemlerde ise işlerin, iş sonu süresi gibi kesin sınırları vardır. Bu sınırlar içinde işlerin tamamlanması gereklidir. Bu tür sistemlerde, işlerin iş sonu sürelerinden sonra bitirilmesi sisteminin bütününü etkileyen önemli problemlere yol açar. Her iş için belirlenen iş sonu sürelerinin karşılanması, katı gerçek zamanlı sistemlerde en önemli özelliktir. Birçok gerçek zamanlı sistemde işler, tanımlı çeşitli işlevlerden oluşur. Gerçek zamanlı işler varış yapısı ve iş sonu süresine bağlı olarak gruplara ayrıla bilir. Bir işin iş sonu süresi içinde karşılanması sistem için kritikse, bu işin iş sonu süresi katı (kesin) olarak kabul edilir. Bir işin iş sonu süresi içinde karşılanması istenip, gecikmelere izin verilebiliyorsa iş sonu süresi esnek olarak tanımlanır. Düzenli oluşan işlere, varış yapısı anlamında süreli (peryodik) işler denir, süreli işler sabit aralıklarla iş istekleri üretirler. Yeni bir iş isteği gelmeden bir önceki istedin karşılanmış olması gerekir. Bir başka deyişle, süreli işin iş sonu süresi, iş isteğinin tekrarlanma aralığına bağlıdır. süreli işlerin en belirgin kullanım alanı, belirli aralıklarla fiziksel bir büyüklüğün kontrol edilmesi ve gerçek zamanlı sistemin durumunun yenilenmesidir. Varış yapısı düzensiz olan, yani, sabit aralıklarla oluşmayan işlere süreli olmayan (aperyodik) işler denir.Bu işler, kullanıcı istekleri gibi rasgele olayların neden olduğu işlevleri gerçeklemek için kullanılır. Süreli olmayan işlerin genellikle iş sonu süreleri esnektir, süreli olmayan ancak katı iş sonu sürelerine sahip olan işlere“sporadic”işler denir. Gerçek zamanlı sistemlerde, zamanlama sınırlarının karşılanabilmesi için, bir iş sıralayıcısının, sisteme ilişkin tüm kaynakları kontrol etmesi ve aşağıdaki özellikleri sağlayan bir gerçek zamanlı iş sıralama algoritması kullanması gereklidir. - Katı zaman sınırlı işlerin iş sonu sürelerinin her durumda karşılanabilir olması, - Katı iş sonu süreli işler için yüksek verimli bir iş sıralamasına ulaşması, (Bu verimlilik çoğu kez algoritmanın uygulanılabilirliğinin göstergesidir.) - Esnek iş sonu süreli işler için, ortalama olarak, hızlı cevap süresinin sağlanması, Geçici aşırı yük durumlarında kararlılığını sürdürmesi. Gerçek zamanda iş sıralama için iki farklı yaklaşım sözkonusudur. Bunlar: - Dinamik iş sıralama yaklaşımı, - Statik iş sıralama yaklaşımı olarak sayılabilir. Dinamik iş sıralamada, sıralayıcının henüz sisteme girmemiş olan işler hakkında herhangi bir bilgisi yoktur; iş istekleri geldikçe yeni sıralamalar oluşturulur. Bu yaklaşımın iyi yanları; önceden işlerin özellikleri hakkında bir bilgiye ihtiyaç duyulmaması, esnek olması ve ortamda meydana gelen değişikliklere kolaylıkla uyum sağlayabilmesidir. Kötü yanları ise; gelecek işlere ait bilgi olmadığından işlerin sıralanabilirliğinin herzaman için garanti edilemez olmasıdır. Herhangi bir anda gelen işin özelliklerine bağlı olarak sistemdeki işlerin iş sonu sürelerinin kaçırılması durumu ortaya çıkabilir. Bunun yanısıra, dinamik sıralayıcının işleri sıralamak için çok kısa bir süresi vardır ve bazı zamanlarda, iş sıralama çok karmaşık olabileceğinden statik yaklaşımla uygun bir sıralama bulunabilmesine rağmen dinamik yaklaşımla zaman kısıtlaması nedeniyle tüm olasılıkların denenemez ve sonuçta uygun sıralama bulunamayabilir. -viii-Statik iş sıralamada ise, sistemdeki tüm işlerin özellikleri önceden bilinir. Bu yaklaşımın iyi yanı sistemdeki kaynakların paylaşımında önemli ölçüde zaman kazancı sağlamasıdır. Kötü yanları ise esnek olmaması ve değişen ortam koşullarına uyum sağlamanın zor olmasıdır. Gerçek zamanlı iş sıralama problemlerinde, sıralana cak olan işlerin durdurulabilir (preemptive) ya da durdurulamaz (nonpreemptive) olması kabul edilerek çözüm aranılır. Durdurulabilir gerçek zamanlı iş sıralaması, bir işin diğer bir işin çalışmasını kesip, merkezi işlem birimi ve dolayısıyla diğer kaynaklara sahip olabilmesi esasına dayanır. En erken iş sonu ilk (earliest deadline first), en gevşek ilk (least laxity first), monoton hızlı (rate monotonic) gibi algoritmalar bu tür uygulamalara yönelik olarak sunulmuşlardır. Durdurulamayan gerçek zamanlı iş sıralamasında, merkezi işlem birimde çalışmaya başlayan iş, çalışması sona erene kadar merkezi işlem birimine sahiptir. Durdurulamayan gerçek zamanlı sistemler, durdurulabilir olanlarına göre esneklik ve sıralanabilirlik açısından daha düşük düzeydedirler. Bu sistemlerdeki iş sıralama sının en iyi çözümü, polinom zamanda bulunamaz (NP- Complete). Buna karşılık, durdurulabilir gerçek zamanlı sistemlerde iş sıralaması çözümleri polinom zamanda bulunabilir. Bir iş kümesi içinde bazı işler, diğer işlerin sadece bir kısmını durdurulabilir, diğer kısmını durduru lamaz ise bu tür iş sıralamasına yarı -durdurulabilir (semi -preempt i ve) gerçek zamanlı iş sıralaması denir. Tezin kaynak tarama aşamasında gerçek zamanlı sistemlerde kullanılan çeşitli sıralama algoritmaları incelenmiştir. Daha önce de belirtildiği gibi gerçek zamanlı sistemlerde iş isteklerinin belli süreler içinde karşı lanması gerekir. Bu sebeple, işlerin kesin cevap sürelerinin önceden belirlenmesi istenir. Bu sürenin hesaplanması önemli bir problemdir. Bu sürenin hesaplan masında hem işlerin, hem gerçek zamanlı sistemin özellik lerinin bilimesi gerekir. Gerçek zamanlı bir sistem aşağıdaki özelliklere sahip olan işlerden oluşur; - Her iş sıra İle koşturulan bölümlerden oluşur, - İşler cihazları kullanabilirler, ix-Programdaki dosyalama işlemleriyle sistem tanıtım ları saklanabilir ya da yüklenebilir. Bunun dışında sıralama işlemi ve gerçek zaman sonuçlarını gösteren bir dosya da yaratılır. Bu dosya istendiğinde akışın birim zaman bazında adım adım incelenebilmesini sağlar. Bu tezde, gerçek zamanlı sistemlerde kullanılan sıralama algoritmaları incelenmiş, yukarıda tanıtılan, işlerin kesin cevap sürelerinin bulunmasına ve işlerin sıralanmasına yönelik yazılım gerçeklenmiştir. -xii-Burada, TOTR± : i. işin kaynak bölümleri için toplam işlemci süresi ihtiyacı (%100 işlemci kullanımı durumunda), TOTDj^ : i. işin cihaz kullanım süreleri toplamını, TOTN, : i. işin kaynak kullanılmayan bölümleri için top lam işlemci süresi ihtiyacı (%100 işlemci kullanımı duru munda), B± : i. işin diğer işler tarafından bekletilme veya yavaşlatılma süreleri toplamıdır. TOT^/ratej^ kesri ise i. işin kaynak bulunmayan bölümlerinin rate^^ oranında koşması süresini gösterir. Yukarıda sözü edilen algoritma ile katı gerçek zamanlı bir sistemde tek bir işlemci üzerinde koşan bir iş kümesindeki işlerin kesin cevap süreleri belirlenmek tedir. Bu tezde, adı geçen algoritma birden fazla işlemcili sistemlere uyarlanmıştır. Bu uyarlamada ele alınan çok işlemcili sistem, işlemciler ve bu işlemciler tarafından dışlamalı olarak kullanılabilen kaynak ve cihazlardan oluşmaktadır. Kaynaklar işlemci ile birlikte kullanılabilir olmalarına karşın cihazlar, işleri yürütmeye başladıklarında işlemciye gereksinim duymadan yaptıkları işe devam ederler. Bu fiziksel sistemde tanıtılan işler üç farklı bölümden oluşur: kaynak kullanmayan, kaynak kullanan ve cihaz kullanan. Her bir bölüm, yapısına göre birtakım parametrelere gerek duyar. Kaynakların ve cihazların numaraları ve kullanım süreleri (bölüm süreleri) belirtilirken, kaynak kullanmayan bölüm ler için kullanım sürelerinin belirtilmesi yeterlidir. Bu sistem üzerinde belirtilen işlerin kesin cevap sürelerini, geliştirilen algoritmaya uygun olarak bulan ve elde edilen sonuçları sınamak üzere, işleri gerçek zamanda sıralayarak cevap sürelerini m belirleyen bir benzeşim programı da geliştirilmiştir. İşlerin işlemci lere atanmasında, kesin cevap sürelerinin en büyüğünün en küçük olması kıstas olarak alınmıştır. Bu programda, kullanıcı menüler yardımıyla öncelikle sistemi ve işleri tanıtır. Bir sonraki adımda işlerin kesin cevap süreleri yukarıda belirtilen kıstasa uygun olarak bulunur. İş sıralama adımında ise, kesin cevap süreleri bulunan ve işlemcilere atanan işler gerçek zamanda sıralanarak cevap süreleri bulunur. Hazırlanan yazılım pencereler üzerinde çalışmaya yöneliktir. Böyle likle sıralamanın tüm aşamalarında kullanıcıya ayrıntılı değerlendirme yapabilmesi için akışı dondurma, etkin olan pencere üzerinde çalışma olanakları sağlanmıştır. -xi-Programdaki dosyalama işlemleriyle sistem tanıtım ları saklanabilir ya da yüklenebilir. Bunun dışında sıralama işlemi ve gerçek zaman sonuçlarını gösteren bir dosya da yaratılır. Bu dosya istendiğinde akışın birim zaman bazında adım adım incelenebilmesini sağlar. Bu tezde, gerçek zamanlı sistemlerde kullanılan sıralama algoritmaları incelenmiş, yukarıda tanıtılan, işlerin kesin cevap sürelerinin bulunmasına ve işlerin sıralanmasına yönelik yazılım gerçeklenmiştir. -xii-

Özet (Çeviri)

SUMMARY A real-time system is a system that performs its functions and responds within a predictable amount of time. Current real-time system examples include nuclear power plant control, industrial manufacturing control, medical monitoring, digital fly-by-wire avionics, weapon delivery systems and space navigation and guidance. Real-time systems can be classified as Soft-Real- Time Systems and Hard-Real -Time Systems with the criteria of response speed of the system. In a soft-real-time system, tasks have to be executed as quickly as possible, without explicit time constraints associated with them. On the other hand, in a hard-real-time system, tasks have explicit time constraints, such as deadlines, so that a task is considered to be of value only if it finishes before its deadline. A late result is often useless in such systems and a job missing its deadline may cause serious problems to the system. The most important issue in a hard real-time system is guaranteeing that all hard deadlines are met. Many real-time systems have a fixed number of tasks that perform well-defined functions. Each task generates service requests or jobs which have specific timing requirements like ready time and deadline. There must be a scheduler that coordinates the use of all of the system resources by using a scheduling algorithm, in order to meet the timing constraints of a real-time system tasks. Different types of algorithms are proposed for real-time systems having different properties. Some of these algorithms are surveyed in this thesis. A special algorithm for determining the guaran teed response times of fixed sets of tasks for a single processor system is entirely examined and it is extended for a multi processor system. A simulation program of this algorithm is also introduced in the thesis. -VI-

Benzer Tezler

  1. Tez No

    35832

    Dağıtık gerçek-zamanlı sistemlerde statik iş dağıtımı

    Static scheduling in distributed real-time systems

    ÖZNUR ÖZKASAP

    Yüksek Lisans

    Türkçe

    Türkçe

    1994

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge Üniversitesi

    DOÇ.DR. KAYHAN ERCİYES

  2. Tez No

    540281

    Mikrofon dizilerinde ses kaynağının yerinin zaman farkı gecikmeleri kullanılarak bulunması

    Sound source localization using microphone arrays by tdoa method

    BİLGE MİNİSKER

    Yüksek Lisans

    Türkçe

    Türkçe

    2018

    Mühendislik Bilimleriİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    DOÇ. MÜRVET KIRCI

  3. Tez No

    83123

    Dağıtılmış sistemlerde ölümcül kilitlenme algoritmaları ve uygulanması

    Deadlock algorithms and their applications in distributed systems

    A. SEZGİN TEPE

    Yüksek Lisans

    Türkçe

    Türkçe

    1999

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. TEVFİK AKGÜN

  4. Tez No

    84019

    Development of an algorithm for the elimination of surface sorting in the stage of hidden surface removal in displaying constructive solid geometry (CSG) volumes and surfaces

    Yapısal katı geometri (CSG) hacim ve yüzeylerini görüntülemede görünmez yüzeylerin temizliği aşamasında oluşan yüzey sıralamasının ortadan kaldırılması için bir algoritmanın geliştirilmesi

    SEMA KOÇ

    Yüksek Lisans

    İngilizce

    İngilizce

    1999

    Elektrik ve Elektronik MühendisliğiGaziantep Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. ULUS ÇEVİK

  5. Tez No

    485234

    New approaches for quality of service provisioning in cognitive radio networks

    Bilişsel radyo ağlarında servis kalitesini yükseltmeye yönelik yeni yaklaşımlar

    GÜLNUR SELDA UYANIK

    Doktora

    İngilizce

    İngilizce

    2017

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. SEMA FATMA OKTUĞ

Geri Dön