Κεφάλαιο 5 | Ενότητα1 | Eρωτήσεις Επισκόπησης  | Επόμενο | Προηγούμενο |Λεξικό όρων

Θεωρήματα για υπολογισμό του χρόνου απόκρισης και του ρυθμού διαμεταγωγής

Εάν ένα σύστημα είναι σε σταθερή κατάσταση, τότε ο αριθμός των διεργασιών που μπαίνουν στο σύστημα πρέπει να είναι ίσος με τον αριθμό των διεργασιών που «φεύγουν» από αυτό.

Σχήμα 5.1.5 - Το Ι/Ο σύστημα ως μαύρο κουτί

Συνήθως ενδιαφερόμαστε για την πολύ μελλοντική ή την σταθερή κατάσταση ενός ολόκληρου Ι/Ο συστήματος περισσότερο από τις αρχικές συνθήκες με τις οποίες ξεκινάμε. Εκτός εάν κάνουμε την απλοποιητική υπόθεση ότι μελετάμε συστήματα σε ισορροπία : Ο ρυθμός της εισόδου πρέπει να είναι ίσος με τον ρυθμό της εξόδου.
Αυτό μας οδηγεί στον Little's Law (Νόμο του Little), ο οποίος συνδυάζει τον μέσο αριθμό των διεργασιών στο σύστημα, τον μέσο ρυθμό άφιξης των νέων διεργασιών και τον μέσο χρόνο εκτέλεσης μιας διεργασίας.

Μέσος αριθμός διεργασιών στο σύστημα = ρυθμός άφιξης * μέσο χρόνο απόκρισης

Ο Little's Law αναφέρεται σε κάθε σύστημα σε ισορροπία εφόσον δεν δημιουργούνται νέες διεργασίες ή δεν καταστρέφονται αυτές που υπάρχουν.

Σχήμα 5.1.6 - Το μοντέλο του μονού εξυπηρέτη. Σε αυτήν την περίπτωση μια αίτηση Ι/Ο «φεύγει» με την ολοκλήρωσή της από τον εξυπηρέτη

Ο Little's Law και μια σειρά ορισμών οδηγούν σε αρκετές χρήσιμες εξισώσεις. Ειδικότερα, δίνονται οι ακόλουθοι ορισμοί:

• Χρόνος(εξυπηρέτη): ο μέσος χρόνος για να εξυπηρετηθεί μια διαδικασία =
      Ρυθμός εξυπηρέτησης 1/ Χρόνος (εξυπηρέτη): (συμβολίζεται με μ)
• Χρόνος (ουράς): o μέσος χρόνος για κάθε διαδικασία στην ουρά.
• Χρόνος(συστήματος): o μέσος χρόνος ανά διεργασία στο σύστημα ή
      ο χρόνος απόκρισης (Χρόνος (ουράς)+Χρόνος (εξυπηρέτη) )
• Ρυθμός άφιξης: μέσος αριθμός διεργασιών που φτάνουν ανά δευτερόλεπτο (συμβολίζεται με λ).
• Μήκος (εξυπηρέτη): μέσος αριθμός διεργασιών σε εξυπηρέτηση.
• Μήκος (ουράς): μέσο μήκος ουράς.
• Μήκος (συστήματος): μέσος αριθμός διεργασιών στο σύστημα (Μήκος (εξυπηρέτη) +Μήκος (συστήματος))

Οι ακόλουθες διευκρινήσεις δίνονται προς αποφυγή παρανοήσεων:

Η πρόταση: “πόσο χρόνο πρέπει να περιμένει στην ουρά μια διεργασία πριν εξυπηρετηθεί”, αναφέρεται στο Χρόνο(ουράς), ενώ η ακόλουθη: “πόσο χρόνο χρειάζεται μια διεργασία μέχρι να ολοκληρωθεί ” αναφέρεται στο Χρόνο(συστήματος)

Χρησιμοποιώντας τους παραπάνω ορισμούς ο Little's Law μπορεί να επαναδιατυπωθεί ως εξής:

Μήκος (συστήματος ) = Ρυθμός άφιξης* Χρόνος (συστήματος)

Μπορούμε ακόμα να βρούμε πόσο απασχολημένο είναι ένα σύστημα από τον ακόλουθο τύπο:

Απασχόληση Εξυπηρέτη (ρ) = Ρυθμός άφιξης / Ρυθμός εξυπηρέτησης

Η τιμή του ρ πρέπει να είναι μεταξύ 0 και 1, διαφορετικά θα έφταναν περισσότερες διεργασίες από αυτές που θα μπορούσαν να εξυπηρετηθούν, οπότε το σύστημα δεν θα ήταν σε ισορροπία.

Ο τρόπος με τον οποίο η ουρά παραδίδει διεργασίες στον εξυπηρέτη (server) καλείται αλγόριθμος ουράς (queue discipline).

Ο πιο απλός και κοινός αλγόριθμος είναι η first-in-first-out (FIFO). Υιοθετώντας τον αλγόριθμο FIFO μπορούμε συνδέσουμε τον χρόνο αναμονής στην ουρά με τον μέσο αριθμό διεργασιών στην ουρά:

Χρόνος (συστήματος) = Μήκος (ουράς) * Χρόνος (εξυπηρέτη) +

    Mέσος χρόνος εξυπηρέτησης διεργασιών μετά την άφιξη μιας νέας διεργασίας

Για να υπολογίσουμε τον τελευταίο όρο της παραπάνω εξίσωσης χρειαζόμαστε δύο στοιχεία:

Weighted mean time =

Όπου Τ_i είναι ο χρόνος για μια διεργασία i και f_i είναι η συχνότητα της διεργασίας i.

Variance =

- Weighted mean time

Προκειμένου να απλοποιήσουμε τις μονάδες, χρησιμοποιούμε τον τύπο:

  squared coefficient of variance: C = variance / Weighted mean time [ (2)/(1) ]

Ολοκληρώνοντας, ο χρόνος αναμονής μιας νέας διεργασίας προκειμένου ο εξυπηρέτης (server) να ολοκληρώσει την προηγούμενη από αυτή διεργασία, καλείται Average residual service time και δίνεται από τον ακόλουθο τύπο:

Average residual service time=(1/2)* Weighted mean time*(1+ C )

Η θεωρία ουρών (queuing theory) είναι πιο αξιόπιστη όταν δεν χρειάζονται ακριβείς απαντήσεις. Τα αληθινά συστήματα είναι πολύ περίπλοκα ώστε η δοθείσα μέθοδο να επιτύχει μία ακριβή ανάλυση. Κατά συνέπεια, καταλήγουμε σε υποθέσεις για το μοντέλο της ουράς:

• Το σύστημα είναι σε ισορροπία
• Ο αριθμός των αιτήσεων είναι άπειρος.
• Ο εξυπηρέτης μπορεί να ασχολήθεί με τον επόμενο πελάτη αμέσως μετά το τέλος της ενασχόλησής του με τον προηγούμενο.
• Δεν υπάρχει όριο στο μήκος της ουράς και αυτή ακολουθεί τον αλγόριθμο FIFO.
• Όλες οι διεργασίες πρέπει να ολοκληρωθούν.

 

ΔΡΑΣΤΗΡΙΟΤΗΤΑ 7

Έστω ότι ο μέσος χρόνος για να ικανοποιηθεί μια αίτηση του δίσκου είναι 50ms και ένα σύστημα Ι/Ο με πολλούς δίσκους παίρνει περίπου 200 Ι/Ο αιτήσεις το δευτερόλεπτο. Να βρείτε ποιος είναι ο μέσος αριθμός των Ι/Ο αιτήσεων στον εξυπηρέτη του δίσκου;

 

ΑΠΑΝΤΗΣΗ ΔΡΑΣΤΗΡΙΟΤΗΤΑΣ 7

ΔΡΑΣΤΗΡΙΟΤΗΤΑ 8

Να βρείτε ένα τύπο για το μέσο χρόνο αναμονής στην ουρά (Χρόνος (ουράς)) σε σχέση με το μέσο χρόνο εξυπηρέτησης (Χρόνος (εξυπηρέτη)), την απασχόληση του εξυπηρέτη (server utilization) και την squared coefficient of variance.

 

ΑΠΑΝΤΗΣΗ ΔΡΑΣΤΗΡΙΟΤΗΤΑΣ 8