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

Αναζήτηση

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

Χρονοδρομολόγηση κυκλικής επαναφοράς

Ο αλγόριθμος κυκλικής επαναφοράς (Round Robin - RR) έχει σχεδιασθεί ειδικά για συστήματα καταμερισμού χρόνου (time sharing) όπου δίνεται ένα μικρό ποσό χρόνου εναλλάξ σε κάθε διεργασία. Αυτό το μικρό ποσό χρόνου, όπως ήδη έχουμε πει, ονομάζεται κβάντο χρόνου (time quantum) και έχει συνήθως διάρκεια της τάξης των 10 msec. Η λίστα έτοιμων διεργασιών είναι η ουρά στην οποία περιμένουν οι διεργασίες. Κάθε φορά που περνά ένα κβάντο χρόνου, η ΚΜΕ διακόπτει την τρέχουσα διεργασία και την τοποθετεί στο τέλος της λίστας έτοιμων διεργασιών. Αφαιρεί στη συνέχεια τη διεργασία που βρίσκεται στην αρχή της ουράς και την παραχωρεί στην ΚΜΕ για το επόμενο κβάντο χρόνου.

Αν μια διεργασία ολοκληρώσει την εκτέλεσή της προτού τελειώσει το κβάντο χρόνου που της έχει παραχωρηθεί, απελευθερώνει οικειοθελώς την ΚΜΕ και το ΛΣ παραχωρεί την ΚΜΕ στην επόμενη έτοιμη διεργασία.

Αν υπάρχει μόνο μια διεργασία στο σύστημα, τότε της παραχωρούνται διαδοχικά κβάντα χρόνου.

Το πλάνο εκτέλεσης του παραδείγματος με τον αλγόριθμο κυκλικής επαναφοράς φαίνεται στο σχήμα, για κβάντο 5 μονάδων χρόνου. Παρατηρούμε ότι οι διεργασίες που εισάγονται στη λίστα έτοιμων διεργασιών την ώρα που κάποια άλλη εκτελείται πρέπει να περιμένουν να έρθει η σειρά τους για εκτέλεση μετά από 1, 2 ή και 3 κβάντα χρόνου. Αυτό συμβαίνει γιατί κάθε νέα διεργασία τοποθετείται στο τέλος της λίστας έτοιμων διεργασιών, οπότε πρέπει πρώτα να εκτελεστούν όλες όσες προηγούνται (για ένα κβάντο χρόνου η κάθε μια) και μετά αυτή.

Επίσης βλέπουμε ότι, αν μια διεργασία ολοκληρωθεί πριν τελειώσει το κβάντο χρόνου της (π.χ. η δ3 τελειώνει τη χρονική στιγμή 18 ενώ το κβάντο χρόνου τελείωνε στην 20), η ΚΜΕ παραχωρείται αμέσως για ένα ολόκληρο κβάντο χρόνου στην επόμενη διεργασία.

Όπως φαίνεται στο σχήμα, η δ1 περνά συνολικά 8 χρονικές μονάδες σε αναμονή, η δ2 περνά 20 χρονικές μονάδες, η δ3 7 και η δ4 20. Ο μέσος χρόνος αναμονής είναι λοιπόν (3+20+7+20)/4 = 12,5 μονάδες χρόνου. Αυτός είναι ένας μεγάλος μέσος χρόνος αναμονής, αλλά αντισταθμίζεται από το γεγονός ότι στους χρήστες δίνεται η εντύπωση ότι οι διεργασίες τους εκτελούνται όντως παράλληλα.

Από το σχήμα επίσης μπορούμε να υπολογίσουμε τους χρόνους απόκρισης για τις τέσσερις διεργασίες: 20 για τη δ1, 51 για τη δ2, 10 για τη δ3 και 31 για τη δ4. Ο μέσος χρόνος απόκρισης είναι λοιπόν (20+51+10+31)/4 = 28.

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

Αν αυτό έχει πολύ μεγάλη τιμή, τότε ο αλγόριθμος πρακτικά εκφυλίζεται στον αλγόριθμο εξυπηρέτησης με βάση τη σειρά άφιξης (FCFS), ο οποίος όπως είδαμε δεν έχει πολύ καλές επιδόσεις. Αν όμως, από την άλλη, το κβάντο χρόνου είναι πολύ μικρό, γίνονται πολλές εναλλαγές από τη μια διεργασία στην άλλη, οι οποίες επιβαρύνουν αρκετά το σύστημα. Πρέπει λοιπόν η τιμή του κβάντου χρόνου να είναι τέτοια ώστε η επιβάρυνση της εναλλαγής μεταξύ των διεργασιών να μην είναι σπουδαία. Ένας καλός κανόνας για τον προσδιορισμό ενός ικανοποιητικού κβάντου χρόνου απαιτεί να είναι μεγαλύτερο σε διάρκεια από το 80% των εκρήξεων ΚΜΕ των διαφόρων διεργασιών.

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