Χρονοπρογραμματισμός ΚΜΕ: Διαφορά μεταξύ των αναθεωρήσεων

Στην [[επιστήμη υπολογιστών]] '''χρονοπρογραμματισμός''' (αγγλ. scheduling) ονομάζεται η αρμοδιότητα των [[λειτουργικό σύστημα|λειτουργικών συστημάτων]], υλοποιούμενη συνήθως από έναν μηχανισμό του [[πυρήνας (υπολογιστές)|πυρήνα]] ονόματι ''χρονοπρογραμματιστής'', με την οποία συντονίζεται η συνύπαρξη πολλαπλών εκτελούμενων [[διεργασία (υπολογιστές)|διεργασιών]] στη μνήμη του υπολογιστή (χαρακτηριστικό γνωστό ως '''[[ταυτοχρονισμός]]''', '''[[πολυδιεργασία]]''' ή '''πολυπρογραμματισμός'''). Έτσι, είτε με κατάλληλη κατανομή του χρόνου του μοναδικού επεξεργαστή (''ψευδοπαράλληλη εκτέλεση'') είτε λόγω της ύπαρξης [[παράλληλο σύστημα|άνωπερισσοτέρων του ενός επεξεργαστών]] (''παράλληλη εκτέλεση''), είναι εφικτή η ταυτόχρονη εκτέλεση πολλαπλών διεργασιών στον ίδιο [[ηλεκτρονικός υπολογιστής|ηλεκτρονικό υπολογιστή]].

Στα σύγχρονα ''προεκτοπιστικά'' (preemptive) λειτουργικά συστήματα, στον [[επεξεργαστής|επεξεργαστή]] συμβαίνει αυτόματη εναλλαγή διεργασιών κάθε λίγες διακοπές του ρολογιού (στην αρχή κάθε «χρονικού κβάντου») ώστε να επιτευχθεί η ψευδοπαράλληλη εκτέλεση πολλαπλών διεργασιών. Στην πραγματικότητα οι διεργασίες εναλλάσσονται στον επεξεργαστή με εξαιρετικά μεγάλη συχνότητα (συνήθως το κβάντο διαρκεί κάποια millisecond). Η εναλλαγή αυτή ονομάζεται '''θεματική εναλλαγή''' (context switch) και, προκειμένου να είναι εφικτή, πρέπει όλες οι πληροφορίες που είναι αποθηκευμένες στην τοπική μνήμη του επεξεργαστή για την εκτελούμενη διεργασία, ο(στους [[μετρητής προγράμματοςκαταχωρητής|καταχωρητές]]) καιγια τατην περιεχόμεναεκτελούμενη των [[καταχωρητής|καταχωρητών]]διεργασία, να αποθηκευτούν σε έναν χώρο κάπου στην [[κύρια μνήμη]] κατά τη θεματική εναλλαγή. Έτσι, όταν έρθει ξανά η σειρά αυτής της διεργασίας να εκτελεστεί, θα μπορούν να φορτωθούν πάλι πίσω στους καταχωρητές και η εκτέλεση να συνεχίσει από εκεί που σταμάτησε.

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

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

Ο αλγόριθμος διατηρεί μια [[FIFO]] [[ουρά (υπολογιστές)|ουρά]] για διεργασίες έτοιμες προς εκτέλεση («ready»). Στη συνέχεια, η διεργασία στην αρχή της ουράς εκτελείται για ένα κλάσμα χρόνου (το κβάντο) ή μέχρι να τεθεί υπό αναστολή (block). Αμέσως μετά τοποθετείται στο τέλος της ουράς και ο χρόνος δίνεται στην επόμενη διεργασία που βρίσκεται στην αρχή<ref>Jean J. Labrosse, ''MicroCOS-II: The Real-Time Kernel'', Newnes 2002, σελ. 45, ISBN 9781578201037</ref>. ΤοΗ μόνομόνη σημαντικό στοιχείοπαράμετρος του αλγορίθμου είναι το μήκος του κβάντου. Μικρό κβάντο έχει ως αποτέλεσμα πολλές θεματικές εναλλαγές, οι οποίες απασχολούν για μεγάλο ποσοστό χρόνου την [[Κεντρική μονάδα επεξεργασίας|ΚΜΕ]]. Στο άλλο άκρο ωστόσο, μεγάλο κβάντο μπορεί να προκαλέσει προβλήματα στην αλληλεπίδραση των χρηστών με το σύστημα (π.χ. παρατηρούμενη υστέρηση κατά την πληκτρολόγηση).