Οι οικονομικοί αλγόριθμοι αντιμετωπίζουν το κατανεμημένο σύστημα ως ανθρώπινη οικονομία. Οι κόμβοι του υπολογιστικού συστήματος διαθέτουν αγαθά (υπολογιστική δύναμη, εύρος ζώνης επικοινωνίας) τα οποία εμπορεύονται με στόχο τη μεγιστοποίηση των προσωπικών τους κερδών. Οι κλάσεις δοσοληψιών διαθέτουν ένα χρηματικό ποσό (κεφάλαιο) που το ισοκατανέμουν στις δοσοληψίες τους. Στόχος των κλάσεων δοσοληψιών είναι η εξυπηρέτηση των εργασιών τους με το μικρότερο εφικτό κόστος. Το κεφάλαιο κάθε κλάσης καθορίζεται από το διαχειριστή του συστήματος και αντικατοπτρίζει την προτεραιότητα και τις υπολογιστικές απαιτήσεις των δοσοληψιών της κλάσης. Οι κλάσεις δοσοληψιών έχουν τις ίδιες προτιμήσεις σε αγαθά (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
σε ιδανικό επεξεργαστή.
Utility Function = min{Ck}, for all k ε [1,N]
όπου Ck είναι η τιμή που προσφέρει ο επεξεργαστής Pk
min{Ck} = min{J * (STk + WTk)}
Η τιμή που προσφέρει ο κόμβος Pk είναι μια συνάρτηση του χρόνου αναμονής WTk και του αναμενόμενου χρόνου εξυπηρέτησης STk της δοσοληψίας j στον κόμβο. Ο χρόνος αναμονής ορίζεται ως το άθροισμα των αναμενομένων χρόνων εξυπηρέτησης των δοσοληψιών που έχουν δρομολογηθεί στον επεξεργαστή, βρίσκονται στην ουρά και περιμένουν να εξυπηρετηθούν. Ο πολλαπλασιαστής J έχει τιμή 1 δραχμή ανά δευτερόλεπτο.
Ο αλγόριθμος λοιπόν δρομολογεί τη δοσοληψία στον επεξεργαστή που προσφέρει μικρότερο κόστος εξυπηρέτησης (αναμενόμενος χρόνος απόκρισης). Αν μια δοσοληψία δε διαθέτει χρηματικό ποσό ανάλογο των απαιτήσεων κάποιου κόμβου απορρίπτεται από το σύστημα (abort).
Utility Function = min{Ck} =
= min{J * (STk + WTk + dak)} = min{J * (μi/rk +WTk + dak)}, for all k ε [1,N]
όπου Ck είναι η τιμή που προσφέρει ο επεξεργαστής Pk. Η τιμή αυτή είναι συνάρτηση του χρόνου αναμονής και εξυπηρέτησης της δοσοληψίας στον επεξεργαστή Pk καθώς και του χρόνου για τη μεταβίβαση της δοσοληψίας από την πηγή φόρτου Pα στον επεξεργαστή Pk. Ο πολλαπλασιαστής J έχει τιμή 1 δραχμή ανά δευτερόλεπτο.
Ο αλγόριθμος δρομολογεί την εργασία στον επεξεργαστή που διαθέτει το δεδομένο προς προσπέλαση και προσφέρει το ελάχιστο άθροισμα κόστους εξυπηρέτησης (αναμενόμενος χρόνος απόκρισης) και κόστους μεταβίβασης της δοσοληψίας. Αν μια δοσοληψία δε διαθέτει αρκετό κεφάλαιο ώστε να μπορεί να αγοράσει αγαθά από κάποιο κόμβο, απορρίπτεται από το σύστημα (abort).
Utility Function = min{Ck} = min{K * (STk + WTk)2 + J * dak)} =
= min{K * (μi/rk+ WTk)2 + J * dak)}, for all k ε [1,N]
όπου Ck είναι η τιμή που προσφέρει ο επεξεργαστής Pk. Η τιμή αυτή είναι συνάρτηση του χρόνου αναμονής WTk και του αναμενόμενου χρόνου εξυπηρέτησης STk της δοσοληψίας j καθώς και του χρόνου για τη μεταβίβαση της δοσοληψίας από την πηγή φόρτου Pα στον επεξεργαστή Pk. Ο πολλαπλασιαστής J έχει τιμή 1 δραχμή ανά δευτερόλεπτο ενώ ο πολλαπλασιαστής K έχει τιμή 1 δραχμή ανά (δευτερόλεπτο)2
Ο αλγόριθμος δρομολογεί την εργασία στον επεξεργαστή που διαθέτει το δεδομένο προς προσπέλαση και προσφέρει το ελάχιστο άθροισμα του τετραγώνου του κόστους εξυπηρέτησης (αναμενόμενος χρόνος απόκρισης) της δοσοληψίας και του κόστους για τη μεταβίβασή της. Η διαφορά του αλγορίθμου αυτού από αλγόριθμο COMM είναι ότι στην κοστολόγηση των υπηρεσιών του ο επεξεργαστής δίνει μεγαλύτερη βαρύτητα στον αναμενόμενο χρόνο απόκρισης της δοσοληψίας. Το κόστος μεταβίβασης επηρεάζει λιγότερο την επιλογή του ``πιο φθηνού'' επεξεργαστή.
Στους τρεις αλγορίθμους που περιγράφηκαν οι τιμές των αγαθών κάθε κόμβου αποτελούν συνάρτηση της ζήτησης που παρατηρείται στον κόμβο αυτό. Σε κάθε αλγόριθμο ο χρόνος αναμονής της δοσοληψίας j στον επεξεργαστή Pk αποτελεί παράμετρο για την κοστολόγηση των υπηρεσιών του επεξεργαστή. Η παράμετρος αυτή αντικατοπτρίζει τη ζήτηση αφού αποτελεί μέτρο του υπολογιστικού φόρτου που έχει ήδη δρομολογηθεί στον επεξεργαστή. Οι τιμές των αγαθών ενός επεξεργαστή διαμορφώνονται ώστε να αντικατοπτρίζουν και τις δυνατότητες προσφοράς του επεξεργαστή. Στην κοστολόγηση των υπηρεσιών του ένας επεξεργαστής Pk λαμβάνει υπόψη του τόσο το χρόνο αναμονής μιας καινούργιας δοσοληψίας όσο και το χρόνο εξυπηρέτησής της.
Παράμετρος για τον υπολογισμό των χρόνων αυτών αποτελεί η υπολογιστική δύναμη (CPU rate) του επεξεργαστή. Όσο μικρότερη τιμή λοιπόν προσφέρει ο επεξεργαστής Pk τόσο μικρότερο υπολογιστικό φόρτο διαθέτει (σε σχέση με την υπολογιστική του δύναμη) και τόσο περισσότερο υπολογιστικό χρόνο (CPU time) δύναται να διαθέσει σε μια καινούργια δοσοληψία. Οι επεξεργαστές εγγυώνται ότι δεν πρόκειται να απαιτήσουν από τη δοσοληψία j χρηματικό ποσό μεγαλύτερο της τιμής που πρόσφεραν για την εξυπηρέτησή της πριν ληφθεί η απόφαση δρομολόγησης (price guarantees). Η οικονομική πολιτική που ακολουθείται και στους τρεις αλγόριθμους (διαμόρφωση των τιμών των επεξεργαστών) οδηγεί τελικά το σύστημα σε κατάσταση ισορροπίας (equilibrium state) κατά την οποία σε κάθε επεξεργαστή η ζήτηση ισούται με την προσφορά.