Real Time Operating Systems Scheduling Algorithms in Satellite Flight Software

Öz

Time-critical requirements of real time systems are provided by software applications running on real time operating systems. These software tasks must be scheduled based on software and hardware events. There are some services (priority based preemption etc.) in real time operating systems to control software tasks. But in some situations there is a need for scheduling algorithms in real time systems. This need arises especially when time-critical software tasks need to run at different working periods and on a specific timeline. Different scheduling algorithms can be selected to meet the requirements of the system. In space domain, especially on space segment, system have to be real-time and time-critical. This behavior is provided by flight software which is responsible for command, data acquisition, storage and autonomy capabilities of satellite. Most of these functionalities should be implemented as time critical manner. Main goals of this paper are providing analyze of Round Robin, Rate Monotonic, Deadline Monotonic, Earliest Deadline First, Least Laxity First ve Enhanced Least Laxity First scheduling algorithms using in real time operating systems, giving the method which is used to apply scheduling algorithms on RTEMS (Real-Time Executive for Multiprocessor Systems) which is a real time operating system and providing performance results of these scheduling algorithms obtained as a result of this application. In addition, the selection approach of scheduling algorithms considering the space domain is mentioned.

Anahtar Kelimeler

• Space Domain
• Operating System
• Task
• Scheduling Algorithms
• Round Robin Algorithm
• Rate Monotonic Algorithm
• Deadline Monotonic Algorithm
• Earliest Deadline First Algorithm
• Least Laxity First Algorithm
• Enhanced Least Laxity First Algorithm

Uydu Uçuş Yazılımında Gerçek Zamanlı İşletim Sistemleri Zamanlama Algoritmaları

Öz

Gerçek zamanlı sistemlerin zaman kritik ihtiyaçları gerçek zamanlı bir işletim sistemi üzerinde çalışan yazılım uygulamaları tarafından karşılanmaktadır. Zaman kritik ihtiyaçları karşılayacak olan yazılım görevlerinin belirli bir zaman çizelgesine göre çalışmalarının planlanması gerekmektedir. Bu planlamayı tetikleyen unsurlar donanım ve/veya yazılım tabanlı olaylardır. Gerçek zamanlı işletim sistemleri yazılım görevlerinin kontrolü ile ilgili altyapılar sunmakla (öncelik tabanlı çalıştırma vb.) beraber bazı durumlarda zamanlama algoritmalarının kullanılması ihtiyacı duyulmaktadır. Bu ihtiyaç özellikle zaman kritik yazılım görevlerinin farklı çalışma periyotlarında ve belirli bir zaman çizelgesinde çalışması gerektiğinde ortaya çıkmaktadır. Gerçek zamanlı sistemin ihtiyaçları doğrultusunda farklı zamanlama algoritmaları sistem ihtiyaçlarını karşılamak için seçilebilmektedir. Uzay alanında özellikle uydu platformlarında gerçek zamanlı işletim sistemi üzerinde çalışan uçuş yazılımı; uydunun operasyonu için gerekli olan komuta etme, veri alma, depolama ve otonomi kabiliyetlerini sağlamakta ve bu sayede uydudaki bütün alt sistemlerin kontrolünü gerçekleştirmektedir. Uçuş yazılımı bu işlemleri gerçekleştirirken uydunun zaman kritik ihtiyaçlarını karşılamaktan sorumludur. Bu makale gerçek zamanlı işletim sistemleri üzerinde çalışan Round Robin (Zaman Dilimli), Rate Monotonic (Oransal Monoton), Deadline Monotonic (Zaman Sınırı Monoton), Earliest Deadline First (En Yakın Zaman Sınırı Önce), Least Laxity First (En Az İhmal Edilebilir Önce) ve Enhanced Least Laxity First (Gelişmiş En Az İhmal Edilebilir Önce) zamanlama algoritmalarının karşılaştırmasını, bu algoritmaların gerçek zamanlı bir işletim sistemi olan RTEMS (Real-Time Executive for Multiprocessor Systems) üzerinde uygulanması için kullanılan yöntemi ve bu uygulama neticesinde elde edilen, algoritmalara ait performans sonuçlarını sunmayı amaçlamaktadır. Bunlara ek olarak uzay alanının ihtiyaçları göz önünde bulundurulduğunda bu algoritmalardan hangilerinin tercih edildiğinden bahsedilmektedir.

Anahtar Kelimeler

• Uzay alanı
• İşletim Sistemi
• İşlem
• Zamanlama Algoritmaları
• Round Robin algoritması
• Rate Monotonic Algoritması
• Deadline Monotonic Algoritması
• Earliest Deadline First Algoritması
• Least Laxity First Algoritması
• Enhanced Least Laxity First Aloritması

Kaynakça

1. ECSS-E-HB-40A - Software Engineering Handbook, 11 December 2013.
2. RTEMS Classic API Guide, Release 5.4007591, 5th Edition, September 2019.
3. A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 9th Edition, Wiley, 2012.
4. Vijayshree Shinde, Seema C. Biday, Comparison of Real Time Task Scheduling Algorithms, International Journal of Computer Applications (0975 – 8887) Volume 158 – No 6, January 2017.
5. Neil C. Audsley, Deadline Monotonic Scheduling, September 1990.
6. Lipika Datta, Efficient Round Robin Scheduling Algorithm with Dynamic Time Slice, International Journal of Education and Management Engineering, June 2015.
7. Andysah Putera, Utama Siahaan, Comparison Analysis of CPU Scheduling : FCFS, SJF and Round Robin, International Journal of Engineering Development and Research, 2016.
8. Yi Wang, Uppsala University, Scheduling Periodic Tasks http://user.it.uu.se/~yi/courses/rts/dvp-rts-08/notes/Scheduling-periodic.pdf, Last accessed: May 2020.

9. Frank Singhoff, University of Brest, France, Real-Time Scheduling Analysis, http://beru.univ-brest.fr/~singhoff/ENS/USTH/sched.pdf, Last accessed: May 2020.
10. Thomas Plagemann, University of Oslo, CPU Scheduling, https://www.uio.no/studier/emner/matnat/ifi/nedlagte-emner/INF3150/h05/undervisningsmateriale/cpu-scheduling1.pdf, Last accessed: May 2020.
11. Chenyang Lu, Washington University, Real-Time Scheduling, https://www.cse.wustl.edu/~lu/cse467s/slides/scheduling.pdf, Last accessed: May 2020.
12. Jens Hildebrandt, Frank Golatowski, Dirk Timmermann, Scheduling Coprocessor for Enhanced Least-Laxity-First Scheduling in Hard Real Time Systems, Proceedings – Euromicro Conference on Real Time Systems, Jaunary 1999
13. Andrew S. Tanenbaum, Herbert Bos, Modern Operatıng Systems, 4th Edition, Pearson, 2014.