Podejście probabilistyczne do zagadnień szeregowania zadań w systemach czasu rzeczywistego

• Autorzy: Gajer M.

Warianty tytułu

EN

Probabilistic approach to task scheduling in the real-time systems

• Języki publikacji: PL

Abstrakty

PL

Systemy czasu rzeczywistego znajdują coraz powszechniejsze zastosowanie w urządzeniach telekomunikacyjnych, instalacjach militarnych, lotnictwie oraz w nowoczesnych zakładach produkcyjnych. Uogólniona teoria szeregowania według monotonicznego tempa (GRMS) stanowi stosunkowo nowe osiągnięcie informatyki teoretycznej, które wywołało duży wpływ na kierunek rozwoju wielu praktycznie zrealizowanych systemów czasu rzeczywistego. W artykule zaprezentowano podstawy teorii szregowania zadań GRMS. Następnie zaprezentowano nowatorskie statystyczne podejście do zagadnień związanych z procesem szeregowania zadań. Uzyskane rezultaty pozwalają na udzielenie odpowiedzi na pytanie dotyczące wartości prawdopodobieństwa zdarzenia polegającego na tym, że zadany w sposób arbitralny zbiór zadań okresowych będzie szeregowalny w przypadku zastosowania algorytmu GRMS. Wykazano, że wartość tego prawdopodobieństwa zależy w sposób istotny od stopnia ziarnistości zadań oraz od wartości współczynnika łącznego wykorzystania czasu pracy procesora przez wszystkie zadania.

EN

At present the real-time systems constitute the well-defined class of computer systems. The real-time systems are getting moreand more popular in many fields of industry and communication. The real-time systems are used to control telecommunication devices and systems, defence systems, avionics and modern factories. In fact many modern facilities cannot do without them. For example without the real-time systems there would be no nuclear power plants, space ships, modern factories with robots etc. In the case of the real-time systems the computer program is organized into a set of task. Each task performs one of the system functions. In most cases the tasks are realized as periodic tasks. At the beginning of a periodic task some sensors are scanned, then some computations are performed, and in the end of the task the calculated control values are sent to the actuators. These operations are repeated continuously with a given period. Each task posses its deadline point, before which its execution must be finish. The most often the deadline is equal to elapse of the period time of the task. A very important matter is to guarantee that all the task are to be finished before their deadline points. In the case of the hard real-time systems any exceeding task deadline is absolutely intolerable. Such event if happens may lead to uncontrollable behavior of the system, which can cause a disaster, for example an aircraft crash, a loss of human life etc. To guarantee that the task deadlines will be always met, the task scheduling theory was developed. The main goal of the task scheduling theory is to demonstrate at the system development phase that under all the possible to foreseen circumstances the task deadlines will always be met. The so-called Generalized Rate-Monotonic Scheduling (GRMS) theory is a recent development that has had a large impact on the development of the real-time systems. The main ideals of the Generalized Rate-Monotonic Scheduling are the following. Each task is assigned a priority. The more often the task is activated, it is the shorter period it has, it is assigned the higher priority. In a given moment only the task with the highest priority is performed. Any activation of the task with higher priority is ready for the execution. The Generalized Rate-Monotonic Scheduling gives the sufficient condition on the task set schedulability. This condition says that the set of task is always schedulable if no more than 69% some sets of task may be not schedulable and some of them may be still schedulable, but this must be checked in each individual case. In the paper the thorough overview of the Generalized Rate-Monotonic Scheduling is presented. Further this author has proposed a novel statistical approach to periodic task scheduling. The purpose is to answer the question about the value of probability that the task set which uses more than 69% of the processor time is scheduable. In the paper this probability values were measured during the computer simulations of the scheduling process and put into tables. The conducted numerical experiments revealed that the value of probability depends strongly on the tasks granularity level, it is the granularity is finer the probability that the set of tasks is schedulable is higher.

Słowa kluczowe

PL

systemy czasu rzeczywistego; szeregowanie zadań; analiza szeregowalności; uogólniona teoria szeregowania zadań według monotonicznego tempa

EN

real-time systems; task scheduling; schedulability analysis; generalised rate - monotonic scheduling theory

• Wydawca: Wydawnictwo Naukowe PWN SA
• Czasopismo: Kwartalnik Elektroniki i Telekomunikacji
• Rocznik: 2003
• Tom: Vol. 49, z. 1
• Strony: 33--45
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Gajer M.

• Katedra Automatyki AGH, Al. Mickiewicza 30, 30-059 Kraków

Bibliografia

• 1. J. Zalewski: What every engineer needs to know about rate-monotonic scheduling: A tutorial. The University of Texas of the Permian Basin, Odessa, TX, 1995
• 2. K. Ramamrjtham: Scheduling algorithms and operatin systems support for real-time systems. Proceedings of the IEEE, vol. 82, no. 1, January 1994, pp. 55-67
• 3. K. G. Shin, P. Ramanathan: Real-time computing: A new discipline of computer science and engineering. Proceedings of the IEEE, vol. 82, no. 1, January 1994, pp. 6-23
• 4. T. Szmuc, G. Motet: Specyfikacja i projektowanie oprogramowania czasu rzeczywistego. Krakowskie Centrum Informatyki Stosowanej, Kraków, 1998
• 5. J. H. Lala, R. E. Harper: Architectural principles for safety-critical real-time applications. Proceedings of the IEEE, vol. 82, no. 1, January 1994, pp. 25-40
• 6. J. W. S. Liu, W. K. Shih, K. J. Lin, R. Bettati, J. Y. Chung: Imprecise Computations. Proceedings of the IEEE, vol. 82, no. 1, January 1994, pp. 83-93
• 7. N. Suri, M. M. Hugue, C. J. Walter: Synchronization issues in real-time systems. Proceedings of the IEEE, vol. 82, no. 1, January 1994, pp. 41-53
• 8. J. Werewka: Zagadnienia alokacji zadań w rozproszonych systemach komputerowych czasu rzeczywistego. Elektrotechnika, T. 14, Z. 4, Wydawnictwo AGH, Kraków, 1995, ss. 479-488
• 9. L. Sha, R. Rajkumar, S. S. Sathaye: Generalized rate-monotonic scheduling theory: A framework for developing real-time systems. Proceedings of the IEEE, vol. 82, no. 1, January 1994, pp. 68-82
• 1O. S. Tanenbaum: Rozproszone systemy operacyjne. Wydawnictwo Naukowe PWN, Warszawa, 1997
• 11 . P. Czajka, J. R. Nawrocki: Szeregowanie zadań o okresach binarnych w systemach silnie uwarunkowanych czasowo. I Krajowa Konferencja: Metody i Systemy Komputerowe w Badaniach Naukowych i Projektowaniu Inżynierskim, Kraków, 1997, ss. 669-676
• 12. J. Werewka, S. Żaba: Szeregowanie wiadomości w rozproszonych systemach czasu rzeczywistego wykorzystujących magistrale miejscowe. Kwartalnik Elektroniki i Telekomunikacji, T. 45, Z. 1, Wydawnictwa Naukowe PWN, Warszawa, 1999, ss. 25-50