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

Ο αλγόριθμος χρονοπρογραμματισμού Round-Robin, γνωστός και σαν αλγόριθμος RR - χρονοπρογραμματισμός εξυπηρέτησης εκ περιτροπής, είναι ένας από τους παλαιότερους, πιο δίκαιους και πιο διαδεδομένους αλγόριθμους χρονοπρογραμματισμού για διεργασίες ενός λειτουργικού συστήματος (ΛΣ)[1]. Ο αλγόριθμος δεν προκαλεί στέρηση (starvation) και έχει σχετικά απλή και εύκολη υλοποίηση[2].

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

Επεξεργασία

Ο αλγόριθμος διατηρεί μια first-in-first-out (FIFO) ουρά για διεργασίες σε κατάσταση ετοιμότητας (ready). Στη συνέχεια, η διεργασία στην αρχή της ουράς εκτελείται για ένα κλάσμα χρόνου ("quantum") ή μέχρι να τεθεί υπό αναστολή (block). Αμέσως μετά τοποθετείται στο τέλος της ουράς και ο χρόνος δίνεται στην επόμενη διεργασία που βρίσκεται στην αρχή[3].

Αποδοτικότητα αλγορίθμου

Επεξεργασία

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

Εξωτερικοί σύνδεσμοι

Επεξεργασία

Παραπομπές

Επεξεργασία
  1. Milan Milenkovic, Operating Systems: Concepts and Design, McGraw-Hill 1987, σελ. 111, ISBN 9780070419209
  2. Phillip A. Laplante, Real-time systems design and analysis: An Engineers Handbook, Wiley-IEEE 2004, σελ. 91, ISBN 9780471228554
  3. Jean J. Labrosse, MicroCOS-II: The Real-Time Kernel, Newnes 2002, σελ. 45, ISBN 9781578201037