Τεχνικές Χρονοδρομολόγησης Εφαρμογών Για Δίκαιη Κατανομή Πόρων Σε Πολυπύρηνες Αρχιτεκτονικές

Abstract

Η χρονοδρομολόγηση είναι μια διαδικασία, η οποία αφορά το διαμοιρασμό πόρων σε εργασίες ανά τακτά χρονικά διαστήματα, με σκοπό τη βελτιστοποίηση ορισμένων στόχων. Ένας τομέας, στον οποίο χρησιμοποιείται κυρίως, είναι τα υπολογιστικά συστήματα. Όσον αφορά μονοπύρηνες αρχιτεκτονικές έχουν αναπτυχθεί τεχνικές χρονοδρομολόγησης, οι οποίες ανταπεξέρχονται αποδοτικά στο διαμοιρασμό του χρόνου του πυρήνα ανάμεσα στις διεργασίες του συστήματος. Η ανάγκη όμως για εξυπηρέτηση μεγαλύτερου φόρτου εργασίας οδήγησε τους κατασκευαστές στη δημιουργία πολυπύρηνων αρχιτεκτονικών ενσωματώνοντας πολλούς πυρήνες μέσα σε ένα ολοκληρωμένο κύκλωμα (CMP). Αντίθετα με τα συμμετρικά πολυπύρηνα συστήματα (SMP), οι πυρήνες των CMPs δεν θεωρούνται ανεξάρτητες μονάδες εφόσον μοιράζονται στοιχεία της αρχιτεκτονικής, όπως το τελευταίο επίπεδο κρυφής μνήνης και το δίαυλο μνήμης. Στα πολυπύρηνα συστήματα αυτά (CMP) ενσωματώθηκαν, αυτούσιες ή με λίγες αλλαγές, οι τεχνικές χρονοδρομολόγησης, που είχαν υλοποιηθεί στις συμμετρικές (SMP) αρχιτεκτονικές. Εκτελώντας προγράμματα παράλληλα σε πυρήνες που μοιράζονται στοιχεία υπάρχει πιθανότητα να παρατηρήσουμε μείωση στην απόδοσή τους λόγω ανταγωνισμού μεταξύ τους. Υιοθετώντας τεχνικές που δε λαμβάνουν υπόψιν τους τον ανταγωνισμό αυτόν, θεωρώντας τους πυρήνες απομονωμένες μονάδες που δεν μοιράζονται στοιχεία, οδηγούμαστε σε αποτελέσματα που δεν πληρούν τις αρχές της χρονοδρομολόγησης. Μερικά προβλήματα που δημιουργούνται είναι τα εξής: πολύ χαμηλή απόδοση των εφαρμογών, άνισος διαμοιρασμός των πυρήνων μεταξύ τους και συνεπώς απρόβλεπτη και ασταθής συμπεριφορά του συστήματος.Ο σκοπός αυτής της διπλωματικής είναι να παρουσιάσουμε τεχνικές που βελτιώνουν την άνιση κατανομή των πόρων, λαμβάνοντας υπόψιν την διαμάχη των διεργασιών για τα μοιραζόμενα στοιχεία του τσιπ και τις καταστροφικές συνέπειες που αυτή αποφέρει στην αξιοπιστία του συστήματος. Επικεντρωνόμαστε σε τεχνικές που προσφέρουν δικαιοσύνη στις εφαρμογές με τους παρακάτω τρόπους. Στην πρώτη προσέγγιση σχεδιάζουμε έναν χρονοδρομολογητή που προταιρεότητα του είναι να αποφύγει τον ανταγωνισμό των διεργασιών, βασισμένοι σε ένα σχήμα ταξινόμησης και σε ένα μοντέλο που προβλέπει πως οι διάφορες κατηγορίες διεργασιών αλληλεπιδρούν. Η επόμενη μέθοδος προσπαθεί να διαχειριστεί τον ανταγωνισμό των διεργασιών. Λαμβάνει υπόψιν τη μείωση της απόδοσης των διεργασιών και τις ευνοεί αναλόγως. Αυτο το επιτυγχάνει δίνοντας ευκαιρία συχνότερης εκτέλεσης σε εκείνες που υποφέρουν περισσότερο, σε βάρος εκείνων που εκτελούνται με υψηλότερη απόδοση. Τέλος επεκτείναμε την δεύτερη τεχνική μας, έτσι ώστε να αποφεύγει μέρος του ανταγωνισμού και να διαχειρίζεται το υπόλοιπο.Δοκιμάζοντας τις τεχνικές μας σε μια ποικιλία πειραμάτων και συγκρίνοντας τα αποτελέσματα με χρονοδρομολογητή που χρησιμοποιείται σε εμπορικά πολυπύρηνα συστήματα (Linux scheduler), καταλήξαμε στο εξής συμπέρασμα. Οι προτεινόμενες εναλλακτικές είναι ικανές να βελτιώσουν σε μεγάλο βαθμό την άνιση κατανομή των πόρων και να προσφέρουν αξιοπιστία στην απόδοση του συστήματος.