Χρονοπρογραμματισμός
Στην επιστήμη υπολογιστών χρονοπρογραμματισμός (αγγλ. scheduling) ονομάζεται η χαρακτηριστική δυνατότητα των λειτουργικών συστημάτων, υλοποιούμενη συνήθως από έναν μηχανισμό του πυρήνα ονόματι χρονοπρογραμματιστής, με την οποία συντονίζεται η συνύπαρξη πολλαπλών εκτελούμενων διεργασιών στη μνήμη του υπολογιστή. Με τον χρονοπρογραμματισμό επιτυγχάνεται επομένως η πολυδιεργασία, η οποία με τη σειρά της αποτελεί έναν τρόπο πρακτικής υλοποίησης ταυτοχρονισμού καθώς, είτε με κατάλληλη κατανομή του χρόνου του μοναδικού επεξεργαστή (ψευδοπαράλληλη εκτέλεση) είτε λόγω της ύπαρξης περισσοτέρων του ενός επεξεργαστών (παράλληλη εκτέλεση), είναι εφικτή η ταυτόχρονη εκτέλεση πολλαπλών διεργασιών στον ίδιο ηλεκτρονικό υπολογιστή.
Στα σύγχρονα προεκτοπιστικά (preemptive) λειτουργικά συστήματα, στον επεξεργαστή συμβαίνει αυτόματη εναλλαγή διεργασιών κάθε λίγες διακοπές του ρολογιού (στην αρχή κάθε «χρονικού κβάντου») ώστε να επιτευχθεί η ψευδοπαράλληλη εκτέλεση πολλαπλών διεργασιών. Στην πραγματικότητα οι διεργασίες εναλλάσσονται στον επεξεργαστή με εξαιρετικά μεγάλη συχνότητα (συνήθως το κβάντο διαρκεί κάποια millisecond). Η εναλλαγή αυτή ονομάζεται θεματική εναλλαγή (context switch) και, προκειμένου να είναι εφικτή, πρέπει όλες οι πληροφορίες που είναι αποθηκευμένες στην τοπική μνήμη του επεξεργαστή (στους καταχωρητές) για την εκτελούμενη διεργασία, να αποθηκευτούν σε έναν χώρο κάπου στην κύρια μνήμη κατά τη θεματική εναλλαγή. Έτσι, όταν έρθει ξανά η σειρά αυτής της διεργασίας να εκτελεστεί, θα μπορούν να φορτωθούν πάλι πίσω στους καταχωρητές και η εκτέλεση να συνεχίσει από εκεί που σταμάτησε.
Σε παλαιότερα υπολογιστικά συστήματα (των δεκαετιών του 1960 και του του 1970) ήταν σε χρήση ο όρος πολυπρογραμματισμός για να περιγράψει πολυδιεργασιακά αλλά μη προεκτοπιστικά συστήματα, όπου μία διεργασία απελευθέρωνε τον επεξεργαστή μόνο εκούσια (μέσω ρητής προγραμματιστικής εντολής) ή όταν ανεσταλλόταν η λειτουργία της (π.χ. κατά την αναμονή της για είσοδο ή έξοδο δεδομένων).
Πίνακας περιεχομένων |
Επισκόπηση [Επεξεργασία]
Το ποια διεργασία εκτελείται κάθε στιγμή καθορίζεται από τον χρονοπρογραμματιστή του συστήματος, η συμπεριφορά του οποίου συνήθως δεν μπορεί να προβλεφθεί ή να τροποποιηθεί από τον χρήστη. Προκειμένου να λειτουργεί αυτός ο μηχανισμός, εσωτερικά ο πυρήνας διατηρεί λίστες με εκτελούμενες, εκτελέσιμες και εν αναμονή διεργασίες (οι εκτελούμενες κάθε στιγμή μπορούν να είναι περισσότερες από μία, αν είναι διαθέσιμοι τουλάχιστον δύο επεξεργαστές). Η μετάβαση μίας διεργασίας από τη μία κατάσταση στην άλλη λαμβάνει χώρα αυτόματα, μέσω του μηχανισμού εναλλαγής που χρησιμοποιεί ο χρονοπρογραμματιστής, ενώ ο τελευταίος μπορεί να ακολουθεί διάφορους αλγορίθμους για να λαμβάνει αποφάσεις κατανομής του χρόνου του επεξεργαστή σε εκτελούμενα προγράμματα.
Ο απαιτούμενος για τη θεματική εναλλαγή χρόνος είναι ουσιαστικά χαμένος χρόνος, μία επιβάρυνση για το σύστημα αφού κατά τη διάρκεια αυτής της διαδικασίας δεν εκτελούνται υπολογισμοί των χρηστών. Το πόσο μεγάλος θα είναι αυτός ο χρόνος εξαρτάται από την υποστήριξη που παρέχει το υλικό (π.χ. ειδικές εντολές για διευκόλυνση της θεματικής εναλλαγής) και από την πολυπλοκότητα της υλοποίησης του χρονοπρογραμματιστή και του επιλεγμένου αλγορίθμου.
Πολιτικές [Επεξεργασία]
Προεκτοπιστικές πολιτικές [Επεξεργασία]
Χρονοπρογραμματισμός εκ περιτροπής (Round-Robin) [Επεξεργασία]
Ο αλγόριθμος χρονοπρογραμματισμού Round-Robin, γνωστός και σαν αλγόριθμος RR ή χρονοπρογραμματισμός εκ περιτροπής, είναι ένας από τους παλαιότερους, πιο δίκαιους και πιο διαδεδομένους αλγόριθμους χρονοπρογραμματισμού διεργασιών ενός λειτουργικού συστήματος[1]. Ο αλγόριθμος δεν προκαλεί στέρηση (starvation) και έχει σχετικά απλή και εύκολη υλοποίηση[2].
Ο αλγόριθμος διατηρεί μια FIFO ουρά για διεργασίες έτοιμες προς εκτέλεση («ready»). Στη συνέχεια, η διεργασία στην αρχή της ουράς εκτελείται για ένα κλάσμα χρόνου (το κβάντο) ή μέχρι να τεθεί υπό αναστολή (block). Αμέσως μετά τοποθετείται στο τέλος της ουράς και ο χρόνος δίνεται στην επόμενη διεργασία που βρίσκεται στην αρχή[3]. Η μόνη παράμετρος του αλγορίθμου είναι το μήκος του κβάντου. Μικρό κβάντο έχει ως αποτέλεσμα πολλές θεματικές εναλλαγές, οι οποίες απασχολούν για μεγάλο ποσοστό χρόνου την ΚΜΕ. Στο άλλο άκρο ωστόσο, μεγάλο κβάντο μπορεί να προκαλέσει προβλήματα στην αλληλεπίδραση των χρηστών με το σύστημα (π.χ. παρατηρούμενη υστέρηση κατά την πληκτρολόγηση).
Μη προεκτοπιστικές πολιτικές [Επεξεργασία]
Πηγές [Επεξεργασία]
- Αρχιτεκτονική Υπολογιστών: Μια Δομημένη Προσέγγιση, Tanenbaum Andrew S., Εκδ. Κλειδάριθμος
- Σύγχρονα Λειτουργικά Συστήματα, Tanenbaum Andrew S., Εκδ. Κλειδάριθμος
Παραπομπές [Επεξεργασία]
- ↑ Milan Milenkovic, Operating Systems: Concepts and Design, McGraw-Hill 1987, σελ. 111, ISBN 9780070419209
- ↑ Phillip A. Laplante, Real-time systems design and analysis: An Engineers Handbook, Wiley-IEEE 2004, σελ. 91, ISBN 9780471228554
- ↑ Jean J. Labrosse, MicroCOS-II: The Real-Time Kernel, Newnes 2002, σελ. 45, ISBN 9781578201037
Εξωτερικοί σύνδεσμοι [Επεξεργασία]
- http://www.osdcom.info/content/view/29/39/ Μία επισκόπηση του χρονοπρογραμματισμού εκ περιτροπής
