Προσομοίωση και αποτίμηση της απόδοσης μεθόδων χρονοδρομολόγησης σε κατανεμημένα συστήματα πραγματικού χρόνου

Abstract

The rapid technological advances and the inherent need of most of today's applications for high quality results within strict timing constraints, have made the use of distributed real-time systems vital in our daily life. Avoiding missed deadlines, the complex structure of the workload, the heterogeneity of the computing resources, the need for fault tolerance and the efficient management of overload conditions, are major challenges in distributed real-time systems, which require the employment of appropriate scheduling methods. In order to effectively address these issues, in this thesis we propose and investigate novel scheduling strategies in distributed real-time systems. The performance evaluation of the various policies is performed by simulation. In distributed real-time systems, the workload often consists of complex jobs, which comprise frequently communicating parallel tasks. During the execution of a job, transient failures may occur, due to software faults. In order to improve the system performance and fault tolerance, we propose gang scheduling policies that utilize imprecise computations. The proposed scheduling strategies are compared to other policies that do not employ imprecise computations, under various failure probabilities. Another type of complex workload that is usually used in distributed real-time systems, is a workload that consists of directed acyclic graphs of component tasks. For the scheduling of such complex jobs, we propose algorithms that utilize imprecise computations. The proposed scheduling strategies take into account the effect of input error on the processing time of the component tasks. To further investigate the effect of input error, as well as the effect of heterogeneity of the computing resources on the performance of distributed real-time systems, we examine the scheduling of directed acyclic graphs in a heterogeneous system, utilizing the imprecise computations technique and different input error limits. In the case where the workload consists of directed acyclic graphs, idle time slots may form in the task execution schedule of the system. Hence, we investigate the improvement that can be gained in the performance of a heterogeneous distributed real-time system, by exploiting idle time slots during the scheduling of task graphs. A component task may be inserted into an idle time slot, by employing various bin packing techniques. In order to combine the advantages of both the imprecise computations technique and the idle time slot utilization with bin packing policies, we propose strategies for the scheduling of real-time directed acyclic graphs in a heterogeneous cluster, that combine these techniques for the exploitation of idle time slots.

Οι ραγδαίες τεχνολογικές εξελίξεις και η ανάγκη πολλών εφαρμογών σήμερα για παραγωγή αποτελεσμάτων υψηλής ποιότητας εντός αυστηρών χρονικών περιορισμών, έχουν καταστήσει τη χρήση των κατανεμημένων συστημάτων πραγματικού χρόνου ζωτικής σημασίας στην καθημερινή μας ζωή. Η αποφυγή εκπρόθεσμων αποτελεσμάτων, η σύνθετη δομή του φόρτου εργασιών, η ετερογένεια των υπολογιστικών πόρων, η ανάγκη για ανοχή σε σφάλματα και η αποτελεσματική διαχείριση συνθηκών υψηλού φόρτου, αποτελούν σημαντικές προκλήσεις στα κατανεμημένα συστήματα πραγματικού χρόνου, οι οποίες καθιστούν επιτακτική την ανάγκη εφαρμογής κατάλληλων μεθόδων χρονοδρομολόγησης. Με στόχο την αποτελεσματική αντιμετώπιση των προκλήσεων αυτών, στη διατριβή αυτή προτείνονται και εξετάζονται μέθοδοι χρονοδρομολόγησης εργασιών σε κατανεμημένα συστήματα πραγματικού χρόνου. Η αποτίμηση της απόδοσης των διάφορων πολιτικών γίνεται με τη χρήση μοντέλων προσομοίωσης. Στα κατανεμημένα συστήματα πραγματικού χρόνου, ο φόρτος εργασιών συχνά αποτελείται από σύνθετες εργασίες, οι οποίες αποτελούν ομάδα από παράλληλες συνεργαζόμενες διεργασίες που απαιτούν συχνή επικοινωνία μεταξύ τους. Κατά την εκτέλεση μιας εργασίας, ενδέχεται να παρουσιαστούν παροδικές βλάβες, λόγω σφαλμάτων λογισμικού. Με στόχο τη βελτίωση της απόδοσης και της ανοχής στα σφάλματα, προτείνονται μέθοδοι χρονοδρομολόγησης εργασιών τύπου ομάδας, οι οποίες κάνουν χρήση ανακριβών υπολογισμών. Οι πολιτικές που προτείνονται συγκρίνονται με αντίστοιχες μεθόδους χρονοδρομολόγησης που δεν κάνουν χρήση ανακριβών υπολογισμών. Ένας άλλος τύπος σύνθετων εργασιών που χρησιμοποιείται συχνά στα κατανεμημένα συστήματα πραγματικού χρόνου, είναι οι εργασίες με δομή κατευθυνόμενου άκυκλου γράφου επιμέρους διεργασιών. Για τη χρονοδρομολόγησή τους, προτείνονται μέθοδοι που κάνουν χρήση ανακριβών υπολογισμών. Στις πολιτικές χρονοδρομολόγησης που προτείνονται, λαμβάνεται υπόψη η επίδραση του ενδεχόμενου σφάλματος των δεδομένων εισόδου στο χρόνο επεξεργασίας των επιμέρους διεργασιών. Για την περαιτέρω διερεύνηση της επίδρασης του σφάλματος δεδομένων εισόδου, καθώς και της ετερογένειας των υπολογιστικών πόρων στην απόδοση των κατανεμημένων συστημάτων πραγματικού χρόνου, μελετάται η χρονοδρομολόγηση κατευθυνόμενων άκυκλων γράφων διεργασιών σε ένα ετερογενές σύστημα, όπου γίνεται χρήση ανακριβών υπολογισμών και διαφορετικών επιτρεπτών ορίων σφάλματος δεδομένων εισόδου. Στην περίπτωση που οι εργασίες αποτελούν κατευθυνόμενους άκυκλους γράφους διεργασιών, ενδέχεται να παρουσιαστούν αδρανή διαστήματα στο χρονοδιάγραμμα εκτέλεσης διεργασιών του συστήματος. Για το λόγο αυτό, εξετάζεται η βελτίωση που μπορεί να επιτευχθεί στην απόδοση ενός ετερογενούς κατανεμημένου συστήματος πραγματικού χρόνου, με την εκμετάλλευση των αδρανών διαστημάτων κατά τη χρονοδρομολόγηση κατευθυνόμενων άκυκλων γράφων. Οι διεργασίες τοποθετούνται στα αδρανή διαστήματα με τη χρήση τεχνικών επίλυσης του προβλήματος τοποθέτησης σε κάδους (bin packing). Με στόχο την εκμετάλλευση των πλεονεκτημάτων τόσο της χρήσης ανακριβών υπολογισμών, όσο και της αξιοποίησης των αδρανών διαστημάτων με μεθόδους bin packing, προτείνονται πολιτικές χρονοδρομολόγησης κατευθυνόμενων άκυκλων γράφων διεργασιών πραγματικού χρόνου σε μια ετερογενή συστοιχία επεξεργαστών, οι οποίες συνδυάζουν τις δύο πιο πάνω τεχνικές για την εκμετάλλευση των αδρανών διαστημάτων.