next up previous
Next: Οικονομικός αλγόριθμος αντιγραφής δεδομένων Up: Οικονομία Διαχείρισης Δεδομένων Previous: Οικονομία Διαχείρισης Δεδομένων

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

Ας θεωρήσουμε το κατανεμημένο σύστημα επεξεργασίας δοσοληψιών του Σχήματος 4.1 που αποτελείται από 4 κόμβους P1, P2, P3, P4. Κάθε κόμβος διαθέτει έναν επεξεργαστή και μία πηγή φόρτου. Η υπολογιστική δύναμη του επεξεργαστή Pi καθορίζεται από την παράμετρο ri, όπου i ε [1,4]. Οι κόμβοι συνδέονται με ένα ``point-to-point δίκτυο το οποίο καθορίζεται από το σύνολο ακμών E = eij, όπου i,j ε [1,4]. Η ακμή eij παριστά το μονόδρομο σύνδεσμο επικοινωνίας μεταξύ των επεξεργαστών Pi, Pj. Ο σύνδεσμος αυτός παρουσιάζει καθυστέρηση dij seconds per byte. Η βάση δεδομένων αποτελείται από 4 σχέσεις O1, O2, O3, O4, οι οποίες έχουν ανατεθεί στους κόμβους P1, P2, P3, P4 αντίστοιχα. Εχουν οριστεί 2 κλάσεις δοσοληψιών CA, CB . Οι δοσοληψίες της κλάσης CA προσπελαύνουν κάποιο από τα δεδομένα O1, O2, ενώ οι δοσοληψίες της κλάσης CB προσπελαύνουν κάποιο από τα δεδομένα O1, O3, O4. Θεωρούμε οτι οι υπολογιστικές απαιτήσεις των δοσοληψιών είναι γνωστές κατά την είσοδό τους στο σύστημα. Ο υπολογιστικός χρόνος που απαιτείται για την εξυπηρέτηση δοσοληψίας της κλάσης CA σε ιδανικό επεξεργαστή Pi (ri = 1) είναι μA ενώ αντίστοιχα μB είναι ο χρόνος που απαιτείται για την εξυπηρέτηση δοσοληψίας της κλάσης CB. Ο ρυθμός άφιξης δοσοληψιών στους κόμβους του συστήματος παρουσιάζει μεταβολές στο χρόνο και είναι διαφορετικός για κάθε κλάση του συστήματος. Θεωρούμε οτι ο ρυθμός άφιξης δοσοληψιών της κλάσης CA είναι κάθε χρονική στιγμή ίδιος για όλους τους κόμβους του συστήματος. Ανάλογα ο ρυθμός άφιξης δοσοληψιών της κλάσης CB είναι κάθε χρονική στιγμή ίδιος για όλους τους κόμβους του συστήματος. Το πρόβλημα της διαχείρισης δεδομένων σε αυτό το κατανεμημένο σύστημα ορίζεται ως η ελαχιστοποίηση του μέσου χρόνου απόκρισης των κλάσεων δοσοληψιών CA, CB έχοντας τις ακόλουθες παραμέτρους ελέγχου : Ο χρόνος απόκρισης μιας δοσοληψίας j (της κλάσης Cj) στον επεξεργαστή Pi ορίζεται ως το άθροισμα του χρόνου αναμονής της δοσοληψίας (waiting time) στον επεξεργαστή Pi και του χρόνου εξυπηρέτησης (μi/ri) της δοσοληψίας (service time) στον επεξεργαστή. Δεδομένα του προβλήματος θεωρούνται οι ρυθμοί άφιξης λAj, λBj των δοσοληψιών των κλάσεων CA, CB αντίστοιχα τη χρονική στιγμή tj. Γνωρίζουμε επίσης και τους χρόνους εξυπηρέτησης μA/ri, μB/ri των δοσοληψιών των κλάσεων CA, CB αντίστοιχα στον επεξεργαστή Pi. Το πρόβλημα της διαχείρισης των δεδομένων του συστήματος θα επιλυθεί με τη σχεδίαση ενός δυναμικού αλγορίθμου αντιγραφής των σχέσεων της βάσης και δρομολόγησης των εργασιών στους κόμβους του συστήματος (dynamic replication and routing algorithm). Ο αλγόριθμος αυτός είναι ευαίσθητος στις μεταβολές του φόρτου του συστήματος και βασιζόμενος κυρίως σε αυτές θα παίρνει αποφάσεις για την αντιγραφή των σχέσεων της βάσης δεδομένων και για την δρομολόγηση των δοσοληψιών ώστε να επιταχύνεται ο χρόνος εκτέλεσης των εργασιών του συστήματος. Ο αλγόριθμος θα πρέπει να λαμβάνει επίσης υπόψη, τον υπάρχοντα φόρτο των επεξεργαστών, τον αναμενόμενο χρόνο εξυπηρέτησης της δρομολογούμενης δοσοληψίας σε κάθε επεξεργαστή, καθώς και την καθυστέρηση για την μεταβίβαση της δοσοληψίας σε κάθε επεξεργαστή. Θα πρέπει επίσης να γνωρίζει το φόρτο που έχει συσσωρευτεί σε κάθε κόμβο για κάθε μία από τις σχέσεις που διαθέτει ο κόμβος καθώς και τη διαφορά φόρτου που παρουσιάζουν οι κλάσεις δοσοληψιών.

Οι περισσότερες από τις αναφερθείσες παραμέτρους δεν είναι σταθερές στο χρόνο οπότε ο αλγόριθμος θα πρέπει να αντιλαμβάνεται τις μεταβολές τους.

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



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