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

Ανάλυση


tabular4

Πίνακας 5

Στον Πίνακα 5 παραθέτονται τα αποτελέσματα προσομοίωσης τριών συστημάτων επεξεργασίας δοσοληψιών στα οποία η δρομολόγηση εργασιών γίνεται με βάση τον οικονομικό αλγόριθμο ECO. Τα συστήματα αυτά εικονίζονται στο Σχήμα 3.5.

  
Figure 3.14: Μοντέλα Ανάλυσης

Τα συστήματα διαφέρουν μόνο στην ανάθεση των σχέσεων της βάσης στους κόμβους. Κάθε σύστημα αποτελείται από 5 κόμβους P1, P2, P3, P4, P5. Ο κόμβος P1 λειτουργεί ως πηγή φόρτου ενώ οι κόμβοι P2, P3, P4, P5 εκτελούν δοσοληψίες. Κάθε κόμβος έχει ένα επεξεργαστή 55MIPS. Έχουν οριστεί δύο κλάσεις δοσοληψιών CA, CB. Η κλάση CA ζητά να προσπελάσει τη σχέση Α ενώ η κλάση CB ζητά να προσπελάσει τη σχέση Β. Παρατηρούμε ότι μικρότερο μέσο χρόνο απόκρισης παρουσιάζουν οι δοσοληψίες που εξυπηρετούνται στο σύστημα 2 (ανεξάρτητα από την κλάση στην οποία ανήκουν).

Η ανάλυση των τριών συστημάτων επεξεργασίας δοσοληψιών με βάση τη θεωρία ουρών αποδεικνύει την ορθότητα των αποτελεσμάτων των προσομοιώσεων. Κάθε κόμβος των συστημάτων αυτών έχει έναν επεξεργαστή και μία ουρά αναμονής για τις δοσοληψίες που του ανατείθονται. Ο ρυθμός άφιξης δοσοληψιών στη πηγή φόρτου ακολουθεί Poisson κατανομή. Ο παραγόμενος φόρτος διασπάται σε επιμέρους κατανομές Poisson πριν ανατεθεί στους επεξεργαστές του συστήματος. Διαπιστώνουμε λοιπόν οτι οι ουρές αναμονής των κόμβων συμπεριφέρονται ως Μ/Μ/1 ουρές. Με βάση τη θεωρία ουρών το πρόβλημα της κατανομής του φόρτου σε κάθε ένα από αυτά τα συστήματα ορίζεται ως εξής :

min T
given λA, λB, μA, μB
constraints λA = Σ λAi and λB = Σ λBj, for i,j ε [1,4]

Όπου Τ είναι ο μέσος χρόνος απόκρισης των δοσοληψιών, λA, λB είναι οι ρυθμοί άφιξης των κλάσεων CA, CB αντίστοιχα ενώ μA, μB είναι οι χρόνοι εξυπηρέτησης των δοσοληψιών των κλάσεων CA, CB αντίστοιχα σε ιδανικό επεξεργαστή Pi (ri = 1). Με λAi συμβολίζεται ο ρυθμός άφιξης δοσοληψιών της κλάσης CA στον κόμβο Pi όπου iε [1,4]. Αναζητείται λοιπόν διάνυσμα ανάθεσης φόρτου στους 4 επεξεργαστές (λA1*, λA2*, λA3*, λA4*, λB1*, λB2*, λB3*, λB4*) το οποίο να δίνει ελάχιστο μέσο φόρτο απόκρισης των δοσοληψιών του συστήματος.

Για το Πρώτο Μοντέλο έχουμε :
λA = λA1 + λA2 + λA3
λB = λB3 + λB4

N1 = λA1/(μAA1) + λA2/(μAA2) + (λA3 + λB3)/(((λA3AB3B)/(λA3B3)) - (λA3B3)) + λB4/(μBB4)

όπου N1 είναι ο αναμενόμενος αριθμός δοσοληψιών στο σύστημα ενώ ο μέσος χρόνος απόκρισης των δοσοληψιών του συστήματος είναι
T1 = N1 / (λAB)

Ανάλογα για το Δεύτερο Μοντέλο έχουμε :
λA = λA1 + λA2 + λA3
λB = λB2 + λB3 + λB4

N2 = λA1/(μAA1) + (λA2 + λB2)/(((λA2AB2B)/(λA2B2)) - (λA2B2))
+ (λA3 + λB3)/(((λA3AB3B)/(λA3B3)) - (λA3B3)) + λB4/(μBB4)

T2 = N2 / (λAB)

ενώ για το Τρίτο Μοντέλο έχουμε :
λA = λA1 + λA2
λB = λB3 + λB4

N3 = λA1/(μAA1) + λA2/(μAA2) + λB3/(μBB3) + λB4/(μBB4)

T3 = N3 / (λAB)

Τα τρία προβλήματα ελαχιστοποίησης απλοποιούνται αφού λA = λB και μA = μB για κάθε σύστημα. Επιλύουμε το πρόβλημα ελαχιστοποίησης του μέσου χρόνου απόκρισης δοσοληψιών των τριών συστημάτων. Αποδεικνύεται ότι T2 < T3 < T1. Η διαπίστωση αυτή είναι σύμφωνη με τα αποτελέσματα των προσομοιώσεων.



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