Χρονοπρογραμματισμός ΚΜΕ

Στην πληροφορική χρονοπρογραμματισμός ΚΜΕ (αγγλ.: scheduling) ονομάζεται η χαρακτηριστική δυνατότητα των λειτουργικών συστημάτων, υλοποιούμενη συνήθως από έναν μηχανισμό του πυρήνα ονόματι χρονοπρογραμματιστής, με την οποία συντονίζεται η συνύπαρξη πολλαπλών εκτελούμενων διεργασιών στη μνήμη του υπολογιστή. Με τον χρονοπρογραμματισμό επιτυγχάνεται επομένως η πολυδιεργασία (αγγλ.: multitasking), η οποία με τη σειρά της αποτελεί έναν τρόπο πρακτικής υλοποίησης ταυτοχρονισμού καθώς, είτε με κατάλληλη κατανομή του χρόνου του μοναδικού επεξεργαστή (ψευδοπαράλληλη εκτέλεση) είτε λόγω της ύπαρξης περισσοτέρων του ενός επεξεργαστών (παράλληλη εκτέλεση), είναι εφικτή η ταυτόχρονη εκτέλεση πολλαπλών διεργασιών στον ίδιο ηλεκτρονικό υπολογιστή.

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

Σε παλαιότερα υπολογιστικά συστήματα (των δεκαετιών του 1960 και του του 1970) ήταν σε χρήση ο όρος πολυπρογραμματισμός (αγγλ: multiprogramming) για να περιγράψει πολυδιεργασιακά αλλά μη προεκτοπιστικά συστήματα, όπου μία διεργασία απελευθέρωνε τον επεξεργαστή μόνο εκούσια (μέσω ρητής προγραμματιστικής εντολής) ή όταν ανεσταλλόταν η λειτουργία της (π.χ. κατά την αναμονή της για είσοδο ή έξοδο δεδομένων). Επίσης χρησιμοποιούνταν ο όρος χρονομερισμός (αγγλ: time-sharing) για αναφορά στον πολυπρογραμματισμό ή (αργότερα) την προεκτοπιστική πολυδιεργασία, όπου οι ψευδοπαράλληλα εκτελούμενες διεργασίες είχαν εκκινηθεί από διαφορετικούς χρήστες, οι οποίοι έτσι διαμοιράζονταν την υπολογιστική ισχύ ενός κεντρικού υπολογιστή.

Επισκόπηση

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

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

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

• Αλγόριθμος Χρονοπρογραμματισμού με Βάση τη Σειρά Άφιξης (First-Come,First-Served ή FCFS)

• Αλγόριθμος Χρονοπρογραμματισμού με Βάση τη Μικρότερη Διάρκεια Εκτέλεσης (Shortest Job First ή SJF)

• Αλγόριθμος Χρονοπρογραμματισμού με Βάση την Προτεραιότητα (Priority Scheduling)

• Αλγόριθμος Χρονοπρογραμματισμού εκ Περιτροπής (Round-Robin ή RR)

• Αλγόριθμος Χρονοπρογραμματισμού με Πολυεπίπεδες Ουρές (Multilevel Queue Scheduling Algorithm)

Πηγές

• Αρχιτεκτονική Υπολογιστών: Μια Δομημένη Προσέγγιση, Tanenbaum Andrew S., Εκδ. Κλειδάριθμος
• Σύγχρονα Λειτουργικά Συστήματα, Tanenbaum Andrew S., Εκδ. Κλειδάριθμος
• Λειτουργικά Συστήματα, 2η Ελληνική Έκδοση(Silberschatz,Galvin,Gagne) ISBN 978-960-411-692-8

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

• https://web.archive.org/web/20090422051757/http://www.osdcom.info/content/view/29/39 Μία επισκόπηση του χρονοπρογραμματισμού εκ περιτροπής