Αλγόριθμος Χρονοπρογραμματισμού εκ περιτροπής

Ο αλγόριθμος χρονοπρογραμματισμού Round-Robin, γνωστός και σαν αλγόριθμος RR - χρονοπρογραμματισμός εξυπηρέτησης εκ περιτροπής, είναι ένας από τους παλαιότερους, πιο δίκαιους και πιο διαδεδομένους αλγόριθμους χρονοπρογραμματισμού για διεργασίες ενός λειτουργικού συστήματος (ΛΣ)Milan Milenkovic, Operating Systems: Concepts and Design, McGraw-Hill 1987, σελ. 111, ISBN 9780070419209. Ο αλγόριθμος δεν προκαλεί στέρηση (starvation) και έχει σχετικά απλή και εύκολη υλοποίησηPhillip A. Laplante, Real-time systems design and analysis: An Engineers Handbook, Wiley-IEEE 2004, σελ. 91, ISBN 9780471228554.

Τρόπος λειτουργίας

Ο αλγόριθμος διατηρεί μια first-in-first-out (FIFO) ουρά για διεργασίες σε κατάσταση ετοιμότητας (ready). Στη συνέχεια, η διεργασία στην αρχή της ουράς εκτελείται για ένα κλάσμα χρόνου ("quantum") ή μέχρι να τεθεί υπό αναστολή (block). Αμέσως μετά τοποθετείται στο τέλος της ουράς και ο χρόνος δίνεται στην επόμενη διεργασία που βρίσκεται στην αρχήJean J. Labrosse, MicroCOS-II: The Real-Time Kernel, Newnes 2002, σελ. 45, ISBN 9781578201037.

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

Εξωτερικοί σύνδεσμοι
 An overview of the Round Robin scheduling algorithm - OSDEV Community

Παραπομπές

Κατηγορία:Αλγόριθμοι χρονοπρογραμματισμού