Χρονοπρογραμματισμός Διεργασιών — Έννοιες Λειτουργικών Συστημάτων

Ο χρονοπρογραμματισμός διεργασιών είναι η απόφαση του λειτουργικού συστήματος για το ποια έτοιμη διεργασία θα πάρει την CPU στη συνέχεια. Με απλά λόγια, είναι ο κανόνας που καθορίζει ποια εκτελείται τώρα και ποια περιμένει. Αυτός ο κανόνας αλλάζει τον χρόνο αναμονής, τον χρόνο απόκρισης, τη δικαιοσύνη και τη συνολική ρυθμαπόδοση.

Ο χρονοπρογραμματισμός διεργασιών έχει σημασία επειδή το ίδιο σύνολο διεργασιών μπορεί να ολοκληρωθεί με πολύ διαφορετική σειρά υπό FCFS, SJF ή round robin. Αν καταλάβεις αυτή τη μία ιδέα, τα περισσότερα παραδείγματα των βιβλίων γίνονται πολύ πιο εύκολα στην κατανόηση.

Τι σημαίνει ο χρονοπρογραμματισμός διεργασιών στα ΛΣ

Στο συνηθισμένο μοντέλο λειτουργικού συστήματος, οι διεργασίες μετακινούνται ανάμεσα σε καταστάσεις όπως ready, running και waiting. Ο χρονοπρογραμματιστής επιλέγει ανάμεσα στις έτοιμες διεργασίες.

Γι’ αυτό ο χρονοπρογραμματισμός διεργασιών συχνά ονομάζεται και χρονοπρογραμματισμός CPU. Δεν δημιουργεί νέα εργασία. Αποφασίζει τη σειρά με την οποία η εργασία που περιμένει θα εξυπηρετηθεί από την CPU.

Στα σύγχρονα συστήματα, ο πυρήνας συχνά χρονοπρογραμματίζει άμεσα νήματα, αλλά ο κλασικός όρος "χρονοπρογραμματισμός διεργασιών" παραμένει ο καθιερωμένος διδακτικός όρος.

Τι προσπαθεί να βελτιστοποιήσει ένας χρονοπρογραμματιστής

Ένας χρονοπρογραμματιστής συνήθως προσπαθεί να ισορροπήσει αρκετούς στόχους:

• μικρό χρόνο αναμονής
• γρήγορη απόκριση για διαδραστικές εργασίες
• καλή ρυθμαπόδοση
• δικαιοσύνη
• προβλέψιμη συμπεριφορά

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

Προεκτοπιστικός vs μη προεκτοπιστικός χρονοπρογραμματισμός

Ένας μη προεκτοπιστικός χρονοπρογραμματιστής αφήνει μια διεργασία που εκτελείται να κρατήσει την CPU μέχρι να ολοκληρώσει το CPU burst της ή να μπλοκάρει. Το first-come, first-served είναι το κλασικό παράδειγμα.

Ένας προεκτοπιστικός χρονοπρογραμματιστής μπορεί να διακόψει μια διεργασία που εκτελείται και να δώσει την CPU σε κάποια άλλη. Το round robin και πολλοί χρονοπρογραμματιστές προτεραιότητας το κάνουν αυτό.

Αυτή η διάκριση έχει σημασία επειδή ο χρόνος απόκρισης συχνά βελτιώνεται όταν το σύστημα επιτρέπεται να προεκτοπίζει εργασίες μεγάλης διάρκειας.

Συνήθεις αλγόριθμοι χρονοπρογραμματισμού διεργασιών

First-Come, First-Served

Το first-come, first-served, ή FCFS, εκτελεί τις διεργασίες με τη σειρά άφιξης. Είναι εύκολο να κατανοηθεί και απλό στην υλοποίηση, αλλά μια μεγάλη εργασία στην αρχή μπορεί να αναγκάσει κάθε μικρή εργασία πίσω της να περιμένει.

Shortest Job First

Το shortest job first, ή SJF, προτιμά τη διεργασία με το μικρότερο CPU burst. Σε ένα απλοποιημένο πλαίσιο όπου τα μήκη των bursts είναι γνωστά με ακρίβεια, μπορεί να μειώσει τον μέσο χρόνο αναμονής. Στα πραγματικά συστήματα, αυτό το μήκος burst συνήθως πρέπει να εκτιμηθεί.

Round Robin

Το round robin δίνει σε κάθε έτοιμη διεργασία ένα μικρό χρονικό τμήμα που λέγεται quantum. Αν η διεργασία δεν ολοκληρωθεί μέσα σε αυτό το τμήμα, επιστρέφει στην ουρά ready. Αυτό συνήθως βελτιώνει τη δικαιοσύνη και την απόκριση για διαδραστικά φορτία εργασίας.

Priority Scheduling

Ο χρονοπρογραμματισμός προτεραιότητας εκτελεί πρώτα την έτοιμη διεργασία με την υψηλότερη προτεραιότητα. Μπορεί να είναι χρήσιμος όταν κάποιες εργασίες είναι σημαντικότερες από άλλες, αλλά αν οι διεργασίες χαμηλής προτεραιότητας περιμένουν υπερβολικά πολύ, εμφανίζεται ο κίνδυνος λιμοκτονίας.

Ένα λυμένο παράδειγμα με χρόνο αναμονής

Υποθέστε ότι τρεις διεργασίες φτάνουν όλες τη χρονική στιγμή $0$ και καθεμία χρειάζεται μόνο χρόνο CPU:

• $P_1$: $6\ \mathrm{ms}$
• $P_2$: $2\ \mathrm{ms}$
• $P_3$: $1\ \mathrm{ms}$

Υποθέστε ότι:

• υπάρχει μία CPU
• δεν υπάρχει μπλοκάρισμα λόγω I/O
• το κόστος εναλλαγής συμφραζομένων αγνοείται

Κάτω από αυτές τις συνθήκες, χρόνος αναμονής σημαίνει ο χρόνος που περνά μια διεργασία στην ουρά ready πριν εκτελεστεί. Ο χρόνος ολοκλήρωσης είναι

$$\text{turnaround time} = \text{completion time} - \text{arrival time}$$

FCFS

Αν χρησιμοποιηθεί FCFS, η σειρά είναι $P_1 \rightarrow P_2 \rightarrow P_3$.

Χρονοδιάγραμμα:

$$0 \to 6: P_1,\qquad 6 \to 8: P_2,\qquad 8 \to 9: P_3$$

Χρόνοι αναμονής:

• $P_1 = 0$
• $P_2 = 6$
• $P_3 = 8$

Μέσος χρόνος αναμονής:

$$\frac{0 + 6 + 8}{3} = \frac{14}{3}\ \mathrm{ms}$$

SJF

Αν χρησιμοποιηθεί μη προεκτοπιστικό SJF, η σειρά είναι $P_3 \rightarrow P_2 \rightarrow P_1$.

Χρονοδιάγραμμα:

$$0 \to 1: P_3,\qquad 1 \to 3: P_2,\qquad 3 \to 9: P_1$$

Χρόνοι αναμονής:

• $P_3 = 0$
• $P_2 = 1$
• $P_1 = 3$

Μέσος χρόνος αναμονής:

$$\frac{0 + 1 + 3}{3} = \frac{4}{3}\ \mathrm{ms}$$

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

Αυτό δεν σημαίνει ότι το SJF είναι πάντα η καλύτερη επιλογή στον πραγματικό κόσμο. Σημαίνει ότι, κάτω από τις παραδοχές αυτού του παραδείγματος, η σειρά χρονοπρογραμματισμού έχει πολύ μεγάλη σημασία.

Η βασική ιδέα που πρέπει να θυμάσαι

Σκέψου τον χρονοπρογραμματισμό διεργασιών ως την πειθαρχία ουράς για την CPU. Η ουρά ready μπορεί να περιέχει τις ίδιες εργασίες, αλλά ο κανόνας εξυπηρέτησης αυτής της ουράς αλλάζει αυτό που βιώνουν οι χρήστες.

Αν σε ενδιαφέρει περισσότερο η γρήγορη πρώτη απόκριση, μπορεί να προτιμήσεις συχνό διαμοιρασμό. Αν σε ενδιαφέρει περισσότερο η γρήγορη ολοκλήρωση πολλών σύντομων εργασιών, μπορεί να προτιμήσεις μια πολιτική που ευνοεί τα μικρά bursts. Αν σε ενδιαφέρει ο αυστηρός χρονισμός, μπορεί να χρειάζεσαι έναν διαφορετικό χρονοπρογραμματιστή.

Συνηθισμένα λάθη σε προβλήματα χρονοπρογραμματισμού

Η υπόθεση ότι μία πολιτική είναι η καλύτερη για τα πάντα

Δεν υπάρχει ένας μοναδικός νικητής για κάθε φορτίο εργασίας. Μια πολιτική μπορεί να φαίνεται εξαιρετική ως προς τον μέσο χρόνο αναμονής και παρ’ όλα αυτά να είναι κακή ως προς τη δικαιοσύνη ή τις προθεσμίες.

Σύγχυση ανάμεσα σε χρόνο αναμονής, χρόνο απόκρισης και χρόνο ολοκλήρωσης

Αυτά τα μεγέθη σχετίζονται αλλά δεν είναι ταυτόσημα. Ειδικά, ο χρόνος απόκρισης συνήθως σημαίνει τον χρόνο μέχρι την πρώτη εξυπηρέτηση από την CPU ή την πρώτη ορατή απόκριση, ενώ ο χρόνος ολοκλήρωσης μετρά ολόκληρη την εργασία από την άφιξη μέχρι την ολοκλήρωση.

Παράβλεψη της συνθήκης πίσω από τον τύπο

Τα μεγέθη έχουν νόημα μόνο κάτω από τις δοσμένες παραδοχές. Αν ένα πρόβλημα περιλαμβάνει μπλοκάρισμα I/O, διαφορετικούς χρόνους άφιξης ή επιβάρυνση από εναλλαγές συμφραζομένων, το χρονοδιάγραμμα και τα αποτελέσματα αλλάζουν.

Να ξεχνάς αν η πολιτική είναι προεκτοπιστική

Το SJF και το shortest remaining time first δεν είναι ο ίδιος κανόνας. Ο χρονοπρογραμματισμός προτεραιότητας επίσης συμπεριφέρεται διαφορετικά ανάλογα με το αν μια εργασία υψηλότερης προτεραιότητας μπορεί να διακόψει την τρέχουσα.

Πού χρησιμοποιείται ο χρονοπρογραμματισμός διεργασιών

Ο χρονοπρογραμματισμός διεργασιών έχει σημασία οπουδήποτε ένα λειτουργικό σύστημα πρέπει να μοιράσει τον χρόνο της CPU:

• επιτραπέζια και κινητά συστήματα που χρειάζονται εφαρμογές με καλή απόκριση
• εξυπηρετητές που διαχειρίζονται πολλά αιτήματα
• συστήματα batch που ενδιαφέρονται για τη ρυθμαπόδοση
• συστήματα πραγματικού χρόνου που ενδιαφέρονται για εγγυήσεις χρονισμού

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

Δοκίμασε τη δική σου εκδοχή

Άλλαξε το παράδειγμα ώστε το $P_2$ να φτάνει αργότερα, ή αντικατάστησε το FCFS με round robin χρησιμοποιώντας quantum $2\ \mathrm{ms}$, και δες πώς αλλάζει το μοτίβο αναμονής. Αν θέλεις ένα ακόμη βήμα αφού το κάνεις με το χέρι, δοκίμασε τη δική σου εκδοχή στο GPAI Solver και σύγκρινε το χρονοδιάγραμμα που προέβλεψες με αυτό που υπολογίστηκε.