next up previous
Next: Περιγραφή Οικονομικών Αλγορίθμων Δρομολόγησης Up: Οικονομία Κατανομής Φόρτου Εργασιών Previous: Οικονομία Κατανομής Φόρτου Εργασιών

Περιγραφή Προβλήματος

Ας θεωρήσουμε το κατανεμημένο σύστημα (Σχήμα 3.1) που αποτελείται από 5 επεξεργαστές P1, P2, P3, P4, P5. Η υπολογιστική δύναμη του επεξεργαστή Pi καθορίζεται από την παράμετρο ri όπου i ε [1,5]. Ο επεξεργαστής P1 περιορίζεται στη δρομολόγηση δοσοληψιών σε άλλους κόμβους ενώ οι υπόλοιποι επεξεργαστές εξυπηρετούν δοσοληψίες. Οι επεξεργαστές συνδέονται με ένα ``point-to-point'' δίκτυο το οποίο καθορίζεται από το σύνολο ακμών E = {eij} όπου i,j ε [1,5]. Η ακμή eij παριστά ένα μονόδρομο σύνδεσμο επικοινωνίας μεταξύ των επεξεργαστών Pi και Pj. Ο σύνδεσμος αυτός παρουσιάζει καθυστέρηση dij seconds per byte. Η βάση δεδομένων αποτελείται από 5 σχέσεις O1, O2, O3, O4, O5 αντίγραφα των οποίων έχουν ανατεθεί σε όλους τους κόμβους. Εχουν οριστεί δύο κλάσεις δοσοληψιών CA και CB. Οι δοσοληψίες της κλάσης CA προσπελαύνουν κάποιο από τα δεδομένα O1, O3, O5 ενώ οι δοσοληψίες της κλάσης CB προσπελαύνουν κάποιο από τα δεδομένα O1, O2, O4, O5. Θεωρούμε ότι οι υπολογιστικές απαιτήσεις των δοσοληψιών είναι γνωστές κατά την είσοδό τους στο σύστημα. Ο υπολογιστικός χρόνος που απαιτείται για την εξυπηρέτηση δοσοληψίας της κλάσης CA σε ιδανικό επεξεργαστή Pi (ri = 1) είναι μA ενώ αντίστοιχα μB είναι ο χρόνος που απαιτείται για την εξυπηρέτηση δοσοληψίας της κλάσης CB. Ο επεξεργαστής P1 (πηγή φόρτου) παράγει δοσοληψίες των κλάσεων CA και CB με ρυθμούς λA και λB αντίστοιχα.

Το πρόβλημα της κατανομής του φόρτου των εργασιών (load balancing problem) σε αυτό το κατανεμημένο σύστημα ορίζεται ως η ελαχιστοποίηση του μέσου χρόνου απόκρισης (average responce time) των κλάσεων CA και CB. Ο χρόνος απόκρισης μιας δοσοληψίας j (της κλάσης Cj) σε ένα επεξεργαστή Pi ορίζεται ως το άθροισμα του χρόνου αναμονής της δοσοληψίας j (waiting time) και του χρόνου εξυπηρέτησης της δοσοληψίας (service time) στον επεξεργαστή Pi Δεδομένα του προβλήματος θεωρούνται οι ρυθμοί άφιξης λA και λB των δύο κλάσεων καθώς και οι χρόνοι εξυπηρέτησης μAA, μBB στον επεξεργαστή Pi δοσοληψιών των κλάσεων CA και CBαντίστοιχα.

Αναζητείται λοιπόν αλγόριθμος δρομολόγησης ο οποίος επιτυγχάνει επίλυση του υπό μελέτη προβλήματος. Ενας απλός παραδοσιακός αλγόριθμος δρομολόγησης που θα μπορούσε να χρησιμοποιηθεί είναι η ισοκατανομή του πλήθους των δοσοληψιών στους διαθέσιμους επεξεργαστές. Η ανάθεση των δεδομένων στο υπό μελέτη σύστημα (πλήρη αντιγραφή των σχέσεων της βάσης σε όλους τους κόμβους) επιτρέπει την εφαρμογή του αλγορίθμου αυτού. Πιο πολύπλοκες και δικαιότερες προσεγγίσεις λαμβάνουν υπόψη την υπολογιστική δύναμη και τον υπάρχοντα φόρτο των επεξεργαστών, τον αναμενόμενο χρόνο εξυπηρέτησης της δρομολογούμενης δοσοληψίας (service time) σε κάθε επεξεργαστή καθώς και την καθυστέρηση για τη μεταβίβαση της εργασίας στους επεξεργαστές. Οι παραπάνω παράμετροι είναι απαραίτητες για την ισοκατανομή του φόρτου του συστήματος όταν οι κλάσεις δοσοληψιών που έχουν οριστεί προσπελαύνουν διαφορετικά δεδομένα, έχουν διαφορετικό ρυθμό άφιξης και διαφορετικό χρόνο εξυπηρέτησης και οι κόμβοι του συστήματος έχουν διαφορετική υπολογιστική δύναμη, αποθηκευτική χωρητικότητα, κ.λ.π..

Αν οι σχέσεις της βάσης δεδομένων δεν είχαν αντιγραφεί σε όλους τους κόμβους του συστήματος το πρόβλημα της ελαχιστοποίησης του μέσου χρόνου απόκρισης των κλάσεων δοσοληψιών CA και CB θα ήταν πιο πολύπλοκο. Σε ανάλογη περίπτωση ο αλγόριθμος δρομολόγησης θα έπρεπε να γνωρίζει ποιό δεδομένο επιθυμεί να προσπελάσει κάθε δοσοληψία καθώς και τους κόμβους στους οποίους έχει ανατεθεί το δεδομένο αυτό.

Ας θεωρήσουμε ότι στο προηγούμενο σύστημα οι σχέσεις της βάσης δεδομένων δεν έχουν αντιγραφεί σε όλους τους κόμβους του συστήματος. Συγκεκριμένα, οι σχέσεις Ο1 και Ο5 έχουν ανατεθεί στον κόμβο P2, οι σχέσεις Ο2 και Ο3 στους κόμβους P3 και P4 αντίστοιχα ενώ αντίγραφα όλων των σχέσεων της βάσης έχουν αποθηκευτεί στον κόμβο P5 (Σχήμα 3.2). Για λόγους απλοποίησης του προβλήματος κάνουμε επίσης τις ακόλουθες παραδοχές

Το πρόβλημα της ελαχιστοποίησης του μέσου χρόνου απόκρισης των κλάσεων δοσοληψιών CA και CB δεν επιλύεται με ισοκατανομή των εργασιών στους 4 επεξεργαστές P2, P3, P4, P5. Οι επεξεργαστές P2, P5 που διαθέτουν περισσότερα δεδομένα έχουν τη δυνατότητα να εξυπηρετήσουν περισσότερες δοσοληψίες και να επιτύχουν (κατά κανόνα) μικρότερο χρόνο απόκρισης για τις δοσοληψίες αυτές (για κάθε επεξεργαστή ορίζεται ο βαθμός πολυπρογραμματισμού που καθορίζει το μέγιστο πλήθος δοσοληψιών που μπορούν να είναι ταυτόχρονα ενεργές στον επεξεργαστή).

Ο αλγόριθμος δρομολόγησης που θα μπορούσε να επιλύσει το πρόβλημα θα έπρεπε να γνωρίζει το φόρτο που έχει συσσωρευτεί σε κάθε κόμβο, για κάθε μία από τις σχέσεις που έχουν ανατεθεί στον κόμβο (ουρές αναμονής για κάθε σχέση του κόμβου).

Ακόμη κι αν σχεδιαστεί αλγόριθμος δρομολόγησης που λαμβάνει υπόψη τις αναφερόμενες παραμέτρους και επιλύει το πρόβλημα της κατανoμής του φόρτου εργασιών σε ένα κατανεμημένο σύστημα ένα διαφορετικό σχήμα ανάθεσης των δεδομένων μπορεί να οδηγήσει σε βελτιωμένη λύση (μικρότερο μέσο χρόνο απόκρισης των κλάσεων δοσοληψιών).

Στο κεφάλαιο αυτό ασχολούμαστε με τη σχεδίαση οικονομικών αλγορίθμων δρομολόγησης οι οποίοι εφαρμόζονται σε κατανεμημένο σύστημα για το οποίο καθορίζονται διαφορετικά σχήματα ανάθεσης. Η μελέτη των αποτελεσμάτων των προσομοιώσεων που διεξάγονται μας δίνουν τη δυνατότητα να εντοπίσουμε το συνδυασμό αλγορίθμου δρομολόγησης και σχήματος ανάθεσης για τον οποίο επιτυγχάνεται ελάχιστος μέσος χρόνος απόκρισης των κλάσεων δοσοληψιών του συστήματος, και να μελετήσουμε τη συμπεριφορά των οικονομικών αλγορίθμων.



Anastasiadi Anastasia
Tue Nov 12 16:13:18 EET 1996