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

Περιγραφή Οικονομικών Αλγορίθμων Δρομολόγησης

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

Γενίκευση Συστήματος
Θεωρώ σύστημα N επεξεργαστών {P1,...,PN} όπου ri η υπολογιστική δύναμη (CPU rate) του επεξεργαστή Pi για i ε [1,N]. Η βάση δεδομένων αποτελείται από M σχέσεις δεδομένων {O1,...,OM} και S(Oi) το πλήθος των σελίδων του δεδομένου Oi, όπου iε [1,M] . Με eij συμβολίζεται ο σύνδεσμος επικοινωνίας (communication link) μεταξύ των επεξεργαστών Pi, Pj και dij είναι η καθυστέρηση του συνδέσμου επικοινωνίας eij. Εχουν οριστεί Λ κλάσεις δεδομένων {CA,...,CΛ} και μi είναι ο χρόνος εξυπηρέτησης (service time) δοσοληψίας της κλάσης Ci σε ιδανικό επεξεργαστή.

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

Παράμετρος για τον υπολογισμό των χρόνων αυτών αποτελεί η υπολογιστική δύναμη (CPU rate) του επεξεργαστή. Όσο μικρότερη τιμή λοιπόν προσφέρει ο επεξεργαστής Pk τόσο μικρότερο υπολογιστικό φόρτο διαθέτει (σε σχέση με την υπολογιστική του δύναμη) και τόσο περισσότερο υπολογιστικό χρόνο (CPU time) δύναται να διαθέσει σε μια καινούργια δοσοληψία. Οι επεξεργαστές εγγυώνται ότι δεν πρόκειται να απαιτήσουν από τη δοσοληψία j χρηματικό ποσό μεγαλύτερο της τιμής που πρόσφεραν για την εξυπηρέτησή της πριν ληφθεί η απόφαση δρομολόγησης (price guarantees). Η οικονομική πολιτική που ακολουθείται και στους τρεις αλγόριθμους (διαμόρφωση των τιμών των επεξεργαστών) οδηγεί τελικά το σύστημα σε κατάσταση ισορροπίας (equilibrium state) κατά την οποία σε κάθε επεξεργαστή η ζήτηση ισούται με την προσφορά.



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