Διδακτικά Βιβλία του Παιδαγωγικού Ινστιτούτου

Αναζήτηση

Βρες
Εμφάνιση

Εξυπηρέτηση με βάση το λόγο απόκρισης

Στους δυο αλγορίθμους που παρουσιάστηκαν οι παράμετροι που λαμβάνονται υπόψη είναι δύο:

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

- Στην εξυπηρέτηση με βάση τη διάρκεια, ο αλγόριθμος ελέγχει τη διάρκεια της επόμενης έκρηξης ΚΜΕ και επιλέγει τη διεργασία με τη μικρότερη έκρηξη.

Βλέπουμε λοιπόν ότι οι δυο αλγόριθμοι είναι μάλλον μονόπλευροι ως προς τη χρονοδρομολόγηση ΚΜΕ. Μια μέση λύση θα προσπαθούσε να λάβει υπόψη και τις δύο αυτές παραμέτρους, συνδυάζοντάς τις σε μία. Αυτή η παράμετρος είναι ο λόγος απόκρισης (response ratio) και είναι: [pic]

Ο αλγόριθμος που βασίζεται στο λόγο απόκρισης ονομάζεται αλγόριθμος εξυπηρέτησης με βάση το λόγο απόκρισης (Highest Response Ratio First, HRF), και επιλέγει για εκτέλεση εκείνη τη διεργασία που έχει το μεγαλύτερο λόγο απόκρισης.

Στο παράδειγμά μας, η διεργασία δ1 που φθάνει πρώτη για εκτέλεση καταλαμβάνει την ΚΜΕ. Όσο αυτή εκτελείται, φθάνουν οι δ2 και δ3. Όταν η δ1 ολοκληρωθεί, η δ2 θα έχει χρόνο αναμονής 6 και η δ3 θα έχει 4. Ο λόγος απόκρισης για τη δ2 θα είναι λοιπόν 1+6/31 = 1,19 και για τη δ3 θα είναι 1+4/3 = 2,33. Επιλέγεται λοιπόν η δ3 για εκτέλεση, κατά τη διάρκεια της οποίας φθάνει η δ4. Όταν και η δ3 τελειώσει τη χρονική στιγμή 15, η δ2 θα έχει περάσει 15-6 = 9 χρονικές μονάδες σε αναμονή και η δ4 1. Ο λόγος απόκρισης για τη δ2 θα είναι τώρα 1 +9/31 = 1,29 και για τη δ4 θα είναι 1+1/11 = 1,09. Αυτή τη φορά λοιπόν επιλέγεται η δ2 για εκτέλεση και τελευταία εκτελείται η δ4. Η ακολουθία εκτέλεσης φαίνεται στο σχήμα.

Ο χρόνος αναμονής για τη δ2 είναι (12+3)-6 = 9, για τη δ3 είναι 12-8 = 4 και για τη δ4 είναι (12+3+31)-14 = 32. Έτσι ο μέσος χρόνος αναμονής είναι (0+9+4+32)/4 = 11,25 μεγαλύτερος από το χρόνο της εξυπηρέτησης με βάση τη διάρκεια, αλλά καλύτερος από την εξυπηρέτηση με βάση τη σειρά άφιξης.

Οι χρόνοι απόκρισης εδώ είναι 12 για τη δ1, 40 για τη δ2, 7 για τη δ3 και 43 για τη δ4. Έτσι ο μέσος χρόνος απόκρισης γίνεται (12+40+7+43)/4 = 25,5.

Συνοπτικά, τα αποτελέσματα για τους τρεις αλγορίθμους φαίνονται στον πίνακα που ακολουθεί. Καλύτερος από τους τρεις για το συγκεκριμένο παράδειγμα είναι ο αλγόριθμος εξυπηρέτησης με βάση τη διάρκεια και για τα δυο κριτήρια αξιολόγησης.