Εισαγωγή στα Λειτουργικά Συστήματα
Γεια σου Χαμπρ! Θα ήθελα να επιστήσω την προσοχή σας μια σειρά άρθρων-μεταφράσεων μιας ενδιαφέρουσας κατά τη γνώμη μου λογοτεχνίας - της ΟΣΤΕΠ. Αυτό το υλικό εξετάζει αρκετά βαθιά τη δουλειά λειτουργικών συστημάτων που μοιάζουν με unix, δηλαδή την εργασία με διεργασίες, διάφορους χρονοπρογραμματιστές, μνήμη και άλλα παρόμοια στοιχεία που συνθέτουν ένα σύγχρονο λειτουργικό σύστημα. Μπορείτε να δείτε το πρωτότυπο όλων των υλικών εδώ . Σημειώστε ότι η μετάφραση έγινε αντιεπαγγελματικά (αρκετά ελεύθερα), αλλά ελπίζω να διατήρησα το γενικό νόημα.
Εργαστήριο για αυτό το θέμα μπορείτε να βρείτε εδώ:
Άλλα μέρη:
Μπορείτε επίσης να δείτε το κανάλι μου στο =)
Σχεδιασμός: Ουρά ανατροφοδότησης πολλαπλών επιπέδων
Σε αυτή τη διάλεξη, θα μιλήσουμε για τα προβλήματα ανάπτυξης μιας από τις πιο διάσημες προσεγγίσεις
προγραμματισμός, που ονομάζεται Ουρά σχολίων πολλαπλών επιπέδων (MLFQ). Ο προγραμματιστής MLFQ περιγράφηκε για πρώτη φορά το 1962 από τον Fernando J. Corbató σε ένα σύστημα που ονομάζεται
Συμβατό σύστημα χρονομερισμού (CTSS). Αυτά τα έργα (συμπεριλαμβανομένων μεταγενέστερων έργων
Multics) στη συνέχεια προτάθηκαν για βραβείο Turing. Ο σχεδιαστής ήταν
στη συνέχεια βελτιώθηκε και απέκτησε την εμφάνιση που μπορεί να βρεθεί ήδη
ορισμένα σύγχρονα συστήματα.
Ο αλγόριθμος MLFQ προσπαθεί να λύσει 2 θεμελιώδη επικαλυπτόμενα προβλήματα.
Πρώτα, προσπαθεί να βελτιστοποιήσει τον χρόνο διεκπεραίωσης, ο οποίος, όπως συζητήσαμε στην προηγούμενη διάλεξη, βελτιστοποιείται με τη μέθοδο της εκκίνησης από την αρχή της ουράς περισσότερο
σύντομες εργασίες. Ωστόσο, το λειτουργικό σύστημα δεν γνωρίζει πόσο καιρό θα τρέχει αυτή ή εκείνη η διαδικασία και αυτό
απαραίτητες γνώσεις για τη λειτουργία των αλγορίθμων SJF, STCF. κατά δεύτερο λόγο, προσπαθεί το MLFQ
Κάντε το σύστημα να ανταποκρίνεται στους χρήστες (για παράδειγμα, για όσους κάθονται και
κοιτάζοντας την οθόνη ενώ περιμένετε να ολοκληρωθεί η εργασία) και έτσι ελαχιστοποιήστε το χρόνο
απάντηση. Δυστυχώς, αλγόριθμοι όπως ο RR μειώνουν τον χρόνο απόκρισης, αλλά
έχουν κακή επίδραση στη μέτρηση του χρόνου διεκπεραίωσης. Εξ ου και το πρόβλημά μας: Πώς να σχεδιάσουμε
χρονοπρογραμματιστή που θα ανταποκρίνεται στις απαιτήσεις μας και ταυτόχρονα δεν γνωρίζει τίποτα
τη φύση της διαδικασίας, γενικά; Πώς μπορεί ο προγραμματιστής να μάθει τα χαρακτηριστικά των εργασιών,
που λανσάρει και άρα λαμβάνει καλύτερες αποφάσεις προγραμματισμού;
Η ουσία του προβλήματος: Πώς να προγραμματίσετε τη ρύθμιση των εργασιών χωρίς τέλεια γνώση;
Πώς να σχεδιάσετε έναν προγραμματιστή που ελαχιστοποιεί ταυτόχρονα τον χρόνο απόκρισης
για διαδραστικές εργασίες και ταυτόχρονα ελαχιστοποιεί τον χρόνο διεκπεραίωσης χωρίς να το γνωρίζει
γνώση του χρόνου εκτέλεσης εργασιών;
Σημείωση: μαθαίνοντας από προηγούμενα γεγονότα
Η ουρά MLFQ είναι ένα εξαιρετικό παράδειγμα συστήματος που έχει εκπαιδευτεί
γεγονότα του παρελθόντος για να προβλέψουμε το μέλλον. Τέτοιες προσεγγίσεις είναι συχνά
που βρέθηκαν στο ΛΣ (Και πολλοί άλλοι κλάδοι στην επιστήμη των υπολογιστών, συμπεριλαμβανομένων των κλάδων
προβλέψεις υλικού και αλγόριθμοι προσωρινής αποθήκευσης). Παρόμοια ταξίδια
ενεργοποιείται όταν οι εργασίες έχουν φάσεις συμπεριφοράς και επομένως είναι προβλέψιμες.
Ωστόσο, θα πρέπει να είναι κανείς προσεκτικός με αυτή την τεχνική, γιατί οι προβλέψεις είναι πολύ εύκολες.
μπορεί να αποδειχθεί λάθος και να οδηγήσει το σύστημα σε χειρότερες αποφάσεις από ό
θα ήταν καθόλου χωρίς γνώση.
MLFQ: Βασικοί κανόνες
Εξετάστε τους βασικούς κανόνες του αλγορίθμου MLFQ. Και παρόλο που οι υλοποιήσεις αυτού του αλγορίθμου
υπάρχουν αρκετές, οι βασικές προσεγγίσεις είναι παρόμοιες.
Στην υλοποίηση που θα εξετάσουμε, το MLFQ θα έχει αρκετές
ξεχωριστές ουρές, καθεμία από τις οποίες θα έχει διαφορετική προτεραιότητα. Οποτεδήποτε,
η εργασία έτοιμη για εκτέλεση βρίσκεται στην ίδια ουρά. Το MLFQ χρησιμοποιεί προτεραιότητες,
για να αποφασίσετε ποια εργασία θα εκτελεστεί για εκτέλεση, π.χ. εργασία με υψηλότερο
προτεραιότητα (μια εργασία από την ουρά με την υψηλότερη προτεραιότητα) θα ξεκινήσει στην πρώτη
Ουρά.
Φυσικά, μπορεί να υπάρχουν περισσότερες από μία εργασίες σε μια συγκεκριμένη ουρά, έτσι
άρα θα έχουν την ίδια προτεραιότητα. Σε αυτή την περίπτωση, θα χρησιμοποιηθεί ο μηχανισμός
RR για προγραμματισμό εκκίνησης μεταξύ αυτών των εργασιών.
Έτσι καταλήγουμε σε δύο βασικούς κανόνες για το MLFQ:
- Κανόνας 1: Εάν προτεραιότητα(Α) > Προτεραιότητα(Β), η εργασία Α θα εκτελεστεί (το Β όχι)
- Κανόνας 2: Εάν προτεραιότητα(Α) = Προτεραιότητα(Β), τα Α&Β ξεκινούν με χρήση RR
Με βάση τα παραπάνω, τα βασικά στοιχεία για τον σχεδιασμό ενός MLFQ είναι
αποτελούν προτεραιότητες. Αντί να δίνεται σταθερή προτεραιότητα στο καθένα
εργασία, το MLFQ αλλάζει την προτεραιότητά του ανάλογα με την παρατηρούμενη συμπεριφορά.
Για παράδειγμα, εάν μια εργασία τερματίζεται συνεχώς από τη CPU ενώ περιμένει την είσοδο στο πληκτρολόγιο,
Το MLFQ θα κρατήσει υψηλή προτεραιότητα της διαδικασίας γιατί έτσι
διαδραστική διαδικασία θα πρέπει να λειτουργήσει. Αν, αντίθετα, το καθήκον είναι συνεχώς και
είναι εντατική CPU για μεγάλο χρονικό διάστημα, το MLFQ θα το υποβαθμίσει
μια προτεραιότητα. Έτσι, το MLFQ θα μελετήσει τη συμπεριφορά των διεργασιών τη στιγμή που εκτελούνται.
και χρησιμοποιήστε συμπεριφορές.
Ας σχεδιάσουμε ένα παράδειγμα για το πώς μπορεί να φαίνονται οι ουρές κάποια στιγμή
ώρα και μετά λαμβάνετε κάτι σαν αυτό:
Σε αυτό το σχήμα, 2 διεργασίες Α και Β βρίσκονται στην ουρά με την υψηλότερη προτεραιότητα. Επεξεργάζομαι, διαδικασία
Το C βρίσκεται κάπου στη μέση και η διαδικασία D βρίσκεται στο τέλος της ουράς. Συμφωνα με τα ΠΑΡΑΠΑΝΩ
περιγραφές του αλγορίθμου MLFQ, ο προγραμματιστής θα εκτελεί εργασίες μόνο με την υψηλότερη
προτεραιότητα σύμφωνα με το RR, και οι εργασίες Γ, Δ θα είναι εκτός εργασίας.
Φυσικά, ένα στατικό στιγμιότυπο δεν θα δώσει μια πλήρη εικόνα του πώς λειτουργεί το MLFQ.
Είναι σημαντικό να κατανοήσουμε ακριβώς πώς αλλάζει η εικόνα με την πάροδο του χρόνου.
Προσπάθεια 1: Πώς να αλλάξετε την προτεραιότητα
Σε αυτό το σημείο, πρέπει να αποφασίσετε πώς το MLFQ θα αλλάξει το επίπεδο προτεραιότητας
task (και συνεπώς τη θέση της εργασίας στην ουρά) κατά τη διάρκεια του κύκλου ζωής της. Για
Από αυτό, πρέπει να έχετε κατά νου τη ροή εργασίας: ένα ορισμένο ποσό
διαδραστικές εργασίες με σύντομους χρόνους εκτέλεσης (και συνεπώς συχνή απελευθέρωση
CPU) και αρκετές μεγάλες εργασίες που χρησιμοποιούν την CPU όλο το χρόνο εργασίας τους, ενώ
Ο χρόνος απόκρισης για τέτοιες εργασίες δεν είναι σημαντικός. Και έτσι μπορείτε να κάνετε την πρώτη προσπάθεια
εφαρμόστε τον αλγόριθμο MLFQ με τους ακόλουθους κανόνες:
- Κανόνας 3: Όταν μια εργασία εισέρχεται στο σύστημα, τοποθετείται στην ουρά με την υψηλότερη
- προτεραιότητα.
- Κανόνας 4α: Εάν μια εργασία χρησιμοποιεί ολόκληρο το χρονικό παράθυρο, τότε
- η προτεραιότητα μειώνεται.
- Κανόνας 4β: Εάν μια Εργασία απελευθερώσει τη CPU πριν λήξει το χρονικό της παράθυρο, τότε την
- παραμένει με την ίδια προτεραιότητα.
Παράδειγμα 1: Ενιαία μακροχρόνια εργασία
Όπως μπορείτε να δείτε σε αυτό το παράδειγμα, η εργασία κατά την αποδοχή ορίζεται με την υψηλότερη
προτεραιότητα. Μετά από ένα χρονικό παράθυρο 10 ms, η διαδικασία υποβαθμίζεται σε προτεραιότητα.
προγραμματιστής. Μετά το επόμενο χρονικό παράθυρο, η εργασία υποβαθμίζεται τελικά σε
χαμηλότερη προτεραιότητα στο σύστημα, όπου παραμένει.
Παράδειγμα 2: Πήρε μια σύντομη εργασία
Ας δούμε τώρα ένα παράδειγμα του τρόπου με τον οποίο το MLFQ θα προσπαθήσει να προσεγγίσει το SJF. Σε αυτό
για παράδειγμα, δύο εργασίες: Α, που είναι μια μακροχρόνια εργασία συνεχώς
καταλαμβάνει CPU και B, που είναι μια σύντομη διαδραστική εργασία. Υποθέτω
ότι ο Α είχε ήδη τρέξει για αρκετό καιρό μέχρι να φτάσει η εργασία Β.
Αυτό το γράφημα δείχνει τα αποτελέσματα του σεναρίου. Εργασία Α, όπως κάθε εργασία,
η χρήση της CPU ήταν στο κάτω μέρος. Η εργασία Β θα φτάσει τη στιγμή Τ=100 και θα
τοποθετείται στην ουρά υψηλότερης προτεραιότητας. Επειδή ο χρόνος λειτουργίας είναι σύντομος,
θα ολοκληρωθεί πριν φτάσει στην τελευταία ουρά.
Από αυτό το παράδειγμα, θα πρέπει να κατανοήσετε τον κύριο στόχο του αλγορίθμου: αφού ο αλγόριθμος δεν το κάνει
γνωρίζει μια μεγάλη ή μια σύντομη εργασία, τότε πρώτα από όλα υποθέτει ότι η εργασία
σύντομο και του δίνει την ύψιστη προτεραιότητα. Αν είναι πραγματικά μια σύντομη εργασία, τότε
θα εκτελεστεί γρήγορα, διαφορετικά εάν είναι μια μακρά εργασία θα κινηθεί αργά
σε προτεραιότητα κάτω και σύντομα θα αποδείξει ότι είναι πράγματι ένα μακρύ έργο που δεν το κάνει
απαιτεί απάντηση.
Παράδειγμα 3: Τι γίνεται με το I/O;
Τώρα ας δούμε ένα παράδειγμα I/O. Όπως αναφέρεται στον κανόνα 4β,
εάν μια διεργασία απελευθερώνει τον επεξεργαστή χωρίς να έχει χρησιμοποιήσει πλήρως τον χρόνο του επεξεργαστή,
τότε παραμένει στο ίδιο επίπεδο προτεραιότητας. Ο σκοπός αυτού του κανόνα είναι αρκετά απλός.
- εάν η διαδραστική εργασία εκτελεί πολλές εισόδους/εξόδους, για παράδειγμα, σε αναμονή
από τα πλήκτρα του χρήστη ή το ποντίκι, μια τέτοια εργασία θα απελευθερώσει τον επεξεργαστή
πριν από το παραχωρημένο παράθυρο. Δεν θα θέλαμε να μειώσουμε την προτεραιότητα μιας τέτοιας εργασίας,
και έτσι θα παραμείνει στο ίδιο επίπεδο.
Αυτό το παράδειγμα δείχνει πώς θα λειτουργούσε ο αλγόριθμος με τέτοιες διεργασίες - διαδραστική εργασία Β, η οποία χρειάζεται μόνο την CPU για 1ms πριν την εκτέλεση
Διαδικασία I/O και μια μακρά εργασία Α, η οποία χρησιμοποιεί την CPU όλη την ώρα.
Το MLFQ διατηρεί τη διαδικασία Β στην υψηλότερη προτεραιότητα καθώς συνεχίζει
απελευθερώστε την CPU. Εάν το B είναι μια διαδραστική εργασία, τότε ο αλγόριθμος σε αυτήν την περίπτωση έχει φτάσει
σκοπός του είναι να ξεκινήσει γρήγορα διαδραστικές εργασίες.
Προβλήματα με τον τρέχοντα αλγόριθμο MLFQ
Στα προηγούμενα παραδείγματα, δημιουργήσαμε μια βασική έκδοση του MLFQ. Και φαίνεται ότι αυτός
κάνει τη δουλειά του καλά και δίκαια, κατανέμοντας τον χρόνο της CPU δίκαια μεταξύ τους
μεγάλες εργασίες και επιτρέποντας σύντομες εργασίες ή εργασίες που έχουν μεγάλη πρόσβαση
σε I/O για γρήγορη επεξεργασία. Δυστυχώς, αυτή η προσέγγιση περιέχει πολλά
σοβαρά προβλήματα.
Πρώτα, το πρόβλημα της πείνας: εάν το σύστημα θα έχει πολλά διαδραστικά
εργασίες, θα καταναλώσουν όλο το χρόνο της CPU και επομένως ούτε ένα μεγάλο χρονικό διάστημα
η εργασία δεν θα έχει την ευκαιρία να εκτελεστεί (πεθαίνουν από την πείνα).
κατά δεύτερο λόγο, οι έξυπνοι χρήστες θα μπορούσαν να γράψουν τα προγράμματά τους έτσι ώστε
ξεγελάσει τον προγραμματιστή. Ο δόλος έγκειται στο να κάνεις κάτι για να εξαναγκάσεις
χρονοπρογραμματιστή για να δώσει στη διαδικασία περισσότερο χρόνο CPU. Ο αλγόριθμος που
που περιγράφεται παραπάνω είναι αρκετά ευάλωτο σε τέτοιες επιθέσεις: πριν από το χρονικό παράθυρο είναι πρακτικά
ολοκληρώθηκε, πρέπει να εκτελέσετε μια λειτουργία I/O (σε ορισμένους, ανεξάρτητα από το αρχείο)
και έτσι να ελευθερωθεί η CPU. Μια τέτοια συμπεριφορά θα σας επιτρέψει να μείνετε στα ίδια
η ίδια η ουρά και πάλι λαμβάνετε μεγαλύτερο ποσοστό χρόνου CPU. Αν γίνει
αυτό είναι σωστό (π.χ. τρέξτε το 99% του χρόνου παραθύρου πριν απελευθερώσετε την CPU),
μια τέτοια εργασία μπορεί απλά να μονοπωλήσει τον επεξεργαστή.
Τέλος, ένα πρόγραμμα μπορεί να αλλάξει τη συμπεριφορά του με την πάροδο του χρόνου. Αυτά τα καθήκοντα
που χρησιμοποιούσε την CPU μπορεί να γίνει διαδραστική. Στο παράδειγμά μας, παρόμοια
οι εργασίες δεν θα λάβουν την αντιμετώπιση που τους αξίζει από τον προγραμματιστή όπως άλλοι
(πρωτότυπες) διαδραστικές εργασίες.
Ερώτηση προς το κοινό: ποιες επιθέσεις στον προγραμματιστή θα μπορούσαν να γίνουν στον σύγχρονο κόσμο;
Προσπάθεια 2: Αυξήστε την προτεραιότητα
Ας προσπαθήσουμε να αλλάξουμε τους κανόνες και να δούμε αν μπορούμε να αποφύγουμε προβλήματα
πείνα. Τι μπορούμε να κάνουμε για να διασφαλίσουμε ότι σχετίζεται
Οι εργασίες της CPU θα πάρουν το χρόνο τους (ακόμα και αν όχι πολύ).
Ως απλή λύση στο πρόβλημα, μπορείτε να προτείνετε περιοδικά
να αυξήσει την προτεραιότητα όλων αυτών των εργασιών στο σύστημα. Υπάρχουν πολλοί τρόποι
Για να το πετύχουμε αυτό, ας προσπαθήσουμε να εφαρμόσουμε κάτι απλό ως παράδειγμα: μετάφραση
όλες οι εργασίες ταυτόχρονα με την υψηλότερη προτεραιότητα, εξ ου και ο νέος κανόνας:
- Rule5: Μετά από κάποιο διάστημα S, μεταφέρετε όλες τις εργασίες στο σύστημα στην υψηλότερη ουρά.
Ο νέος μας κανόνας λύνει δύο προβλήματα ταυτόχρονα. Πρώτον, οι διαδικασίες
εγγυημένο ότι δεν θα λιμοκτονήσει: οι εργασίες στην υψηλότερη ουρά θα μοιραστούν
χρόνος επεξεργαστή σύμφωνα με τον αλγόριθμο RR και έτσι θα λάβουν όλες οι διεργασίες
χρόνος επεξεργαστή. Δεύτερον, εάν κάποια διαδικασία που χρησιμοποιήθηκε προηγουμένως
μόνο ο επεξεργαστής γίνεται διαδραστικός, θα παραμείνει στην ουρά με το υψηλότερο
προτεραιότητα αφού λάβετε μια ώθηση στην υψηλότερη προτεραιότητα.
Εξετάστε ένα παράδειγμα. Σε αυτό το σενάριο, σκεφτείτε μια μεμονωμένη διαδικασία χρησιμοποιώντας
CPU και δύο διαδραστικές, σύντομες διαδικασίες. Αριστερά στο σχήμα, το σχήμα δείχνει τη συμπεριφορά χωρίς ενίσχυση προτεραιότητας, και έτσι η μακροχρόνια εργασία αρχίζει να λιμοκτονεί μετά την άφιξη δύο διαδραστικών εργασιών στο σύστημα. Στο σχήμα στα δεξιά, κάθε 50ms εκτελείται μια αύξηση προτεραιότητας και έτσι όλες οι διεργασίες είναι εγγυημένο ότι λαμβάνουν χρόνο επεξεργαστή και θα ξεκινούν περιοδικά. 50ms σε αυτή την περίπτωση λαμβάνεται ως παράδειγμα, στην πραγματικότητα αυτός ο αριθμός είναι κάπως υψηλότερος.
Είναι προφανές ότι η προσθήκη του χρόνου περιοδικής ανόδου S οδηγεί σε
λογική ερώτηση: ποια τιμή πρέπει να οριστεί; Ένα από τα άξια
οι μηχανικοί συστημάτων John Ousterhout αναφέρθηκαν σε παρόμοιες ποσότητες σε συστήματα ως voo-doo
σταθερά, αφού κατά κάποιο τρόπο απαιτούσαν μαύρη μαγεία για το σωστό
έκθεση. Και, δυστυχώς, το S έχει τέτοια γεύση. Αν ορίσετε και την τιμή
μεγάλες - μεγάλες εργασίες θα λιμοκτονήσουν. Και αν το βάλεις πολύ χαμηλά,
Οι διαδραστικές εργασίες δεν θα λαμβάνουν τον κατάλληλο χρόνο CPU.
Προσπάθεια 3: Καλύτερη Λογιστική
Τώρα έχουμε ένα ακόμη πρόβλημα να λύσουμε: πώς να μην το κάνουμε
επιτρέπεται να εξαπατήσουμε τον προγραμματιστή μας; Οι ένοχοι για αυτό το ενδεχόμενο είναι
κανόνες 4α, 4β που επιτρέπουν σε μια εργασία να διατηρήσει την προτεραιότητά της ελευθερώνοντας τον επεξεργαστή
πριν από τη λήξη του προβλεπόμενου χρόνου. Πώς να το αντιμετωπίσετε;
Η λύση σε αυτή την περίπτωση μπορεί να θεωρηθεί μια καλύτερη καταμέτρηση του χρόνου CPU σε κάθε μία
Επίπεδο MLFQ. Αντί να ξεχνάτε τον χρόνο που χρησιμοποίησε το πρόγραμμα
επεξεργαστή για το εκχωρημένο διάστημα, θα πρέπει να το λάβετε υπόψη και να το αποθηκεύσετε. Μετά
η διαδικασία έχει εξαντλήσει τον καθορισμένο χρόνο της, θα πρέπει να υποβιβαστεί στην επόμενη
επίπεδο προτεραιότητας. Τώρα δεν έχει σημασία πώς θα χρησιμοποιήσει η διαδικασία το χρόνο της - πώς
υπολογισμός συνεχώς στον επεξεργαστή ή ως σύνολο κλήσεων. Ετσι,
Ο κανόνας 4 πρέπει να ξαναγραφεί ως εξής:
- Rule4: Αφού μια εργασία εξαντλήσει τον εκχωρημένο χρόνο της στην τρέχουσα ουρά (ανεξάρτητα από το πόσες φορές έχει αποδεσμεύσει την CPU), η προτεραιότητα μιας τέτοιας εργασίας μειώνεται (μετακινείται στο κάτω μέρος της ουράς).
Ας δούμε ένα παράδειγμα:
»
Το σχήμα δείχνει τι συμβαίνει εάν προσπαθήσετε να ξεγελάσετε τον προγραμματιστή
αν ήταν με τους προηγούμενους κανόνες 4α, το 4β θα ήταν το αποτέλεσμα στα αριστερά. Με καινούργια
ο κανόνας είναι το αποτέλεσμα είναι στα δεξιά. Πριν από την προστασία, οποιαδήποτε διαδικασία θα μπορούσε να καλέσει I/O πριν την ολοκλήρωση και
κυριαρχούν έτσι στην CPU, αφού ενεργοποιηθεί η προστασία, ανεξαρτήτως συμπεριφοράς
I/O, θα συνεχίσει να κατέβει στην ουρά και έτσι δεν θα μπορεί να κάνει ανέντιμα
ανάληψη πόρων CPU.
Βελτίωση MLFQ και άλλα θέματα
Με τις παραπάνω βελτιώσεις προκύπτουν νέα προβλήματα: ένα από τα κύρια
ερωτήσεις - πώς να παραμετροποιήσετε έναν τέτοιο χρονοπρογραμματιστή; Εκείνοι. Πόσο πρέπει να είναι
ουρές; Ποιο θα πρέπει να είναι το μέγεθος του παραθύρου του προγράμματος μέσα στην ουρά; Πως
το πρόγραμμα θα πρέπει συχνά να δίνεται προτεραιότητα για την αποφυγή της πείνας και
να ληφθεί υπόψη η αλλαγή στη συμπεριφορά του προγράμματος; Σε αυτά τα ερωτήματα, δεν υπάρχει κάτι απλό
απόκριση και μόνο πειράματα με φορτία και επακόλουθη διαμόρφωση
ο προγραμματιστής μπορεί να οδηγήσει σε κάποια ικανοποιητική ισορροπία.
Για παράδειγμα, οι περισσότερες υλοποιήσεις MLFQ σάς επιτρέπουν να εκχωρείτε διαφορετικά
χρονικά διαστήματα για διαφορετικές ουρές. Ουρές υψηλής προτεραιότητας συνήθως
μικρά διαστήματα. Αυτές οι ουρές αποτελούνται από διαδραστικές εργασίες,
η εναλλαγή μεταξύ των οποίων είναι αρκετά ευαίσθητη και πρέπει να πάρει 10 ή λιγότερο
Κυρία. Αντίθετα, οι ουρές χαμηλής προτεραιότητας αποτελούνται από μακροχρόνιες εργασίες που χρησιμοποιούν
ΕΠΕΞΕΡΓΑΣΤΗΣ. Και σε αυτή την περίπτωση, τα μεγάλα χρονικά διαστήματα ταιριάζουν πολύ καλά (100ms).
Σε αυτό το παράδειγμα, υπάρχουν 2 εργασίες που έχουν λειτουργήσει στην ουρά 20 υψηλής προτεραιότητας
ms χωρισμένο σε παράθυρα 10ms. 40 ms στη μεσαία ουρά (παράθυρο 20 ms) και στην ουρά χαμηλής προτεραιότητας
Το παράθυρο χρόνου ουράς έγινε 40ms όπου οι εργασίες ολοκλήρωσαν την εργασία τους.
Η υλοποίηση του MLFQ στο Solaris OS είναι μια κατηγορία χρονοδιαγραμμάτων κοινής χρήσης.
Ο προγραμματιστής θα παρέχει ένα σύνολο πινάκων που καθορίζουν ακριβώς πώς θα έπρεπε
αλλάξτε την προτεραιότητα της διαδικασίας κατά τη διάρκεια της ζωής της, ποιο θα πρέπει να είναι το μέγεθος
το παράθυρο που πρέπει να εκχωρηθεί και πόσο συχνά θα αυξάνονται οι προτεραιότητες εργασιών. Διαχειριστής
Το σύστημα μπορεί να αλληλεπιδράσει με αυτόν τον πίνακα και να κάνει τον προγραμματιστή να συμπεριφέρεται
διαφορετικά. Από προεπιλογή, αυτός ο πίνακας έχει 60 ουρές με σταδιακή αύξηση
μέγεθος παραθύρου από 20 ms (υψηλής προτεραιότητας) έως αρκετές εκατοντάδες ms (χαμηλής προτεραιότητας) και
επίσης με την ενίσχυση όλων των εργασιών μία φορά ανά δευτερόλεπτο.
Άλλοι προγραμματιστές MLFQ δεν χρησιμοποιούν πίνακα ή κάποιο συγκεκριμένο
κανόνες που περιγράφονται σε αυτή τη διάλεξη, αντίθετα, υπολογίζουν τις προτεραιότητες χρησιμοποιώντας
μαθηματικούς τύπους. Για παράδειγμα, ο προγραμματιστής στο FreeBSD χρησιμοποιεί έναν τύπο για
τον υπολογισμό της τρέχουσας προτεραιότητας εργασίας με βάση το πόσο η διαδικασία
χρησιμοποιούσε την CPU. Επιπλέον, η χρήση της CPU σαπίζει με την πάροδο του χρόνου, και έτσι
Έτσι, η αύξηση προτεραιότητας είναι κάπως διαφορετική από αυτή που περιγράφηκε παραπάνω. Αυτό είναι αλήθεια
που ονομάζονται αλγόριθμοι αποσύνθεσης. Από την έκδοση 7.1, το FreeBSD χρησιμοποιεί τον προγραμματιστή ULE.
Τέλος, πολλοί σχεδιαστές έχουν άλλα χαρακτηριστικά. Για παράδειγμα, μερικοί
οι προγραμματιστές επιφυλάσσουν υψηλότερα επίπεδα για τη λειτουργία του λειτουργικού συστήματος και έτσι
Έτσι, καμία διεργασία χρήστη δεν μπορεί να έχει την υψηλότερη προτεραιότητα
Σύστημα. Ορισμένα συστήματα σάς επιτρέπουν να δίνετε συμβουλές για βοήθεια
ο προγραμματιστής να ιεραρχήσει σωστά. Για παράδειγμα, χρησιμοποιώντας την εντολή όμορφη
μπορείτε να αυξήσετε ή να μειώσετε την προτεραιότητα μιας εργασίας και έτσι να αυξήσετε ή να μειώσετε
μειώστε τις πιθανότητες του προγράμματος για χρόνο CPU.
MLFQ: Περίληψη
Περιγράψαμε μια προσέγγιση σχεδιασμού που ονομάζεται MLFQ. Το όνομά του
συνάπτεται στην αρχή της λειτουργίας - έχει πολλές ουρές και χρησιμοποιεί ανατροφοδότηση
να ιεραρχήσει μια εργασία.
Η τελική μορφή των κανόνων θα είναι η εξής:
- Rule1: Εάν προτεραιότητα(Α) > Προτεραιότητα(Β), η εργασία Α θα εκτελεστεί (το Β όχι)
- Rule2: Εάν προτεραιότητα(Α) = Προτεραιότητα(Β), τα Α&Β ξεκινούν με χρήση RR
- Rule3: Όταν μια εργασία εισέρχεται στο σύστημα, τοποθετείται στην ουρά υψηλότερης προτεραιότητας.
- Rule4: Αφού μια εργασία εξαντλήσει τον εκχωρημένο χρόνο της στην τρέχουσα ουρά (ανεξάρτητα από το πόσες φορές έχει αποδεσμεύσει την CPU), η προτεραιότητα μιας τέτοιας εργασίας μειώνεται (μετακινείται στο κάτω μέρος της ουράς).
- Rule5: Μετά από κάποιο διάστημα S, μεταφέρετε όλες τις εργασίες στο σύστημα στην υψηλότερη ουρά.
Το MLFQ είναι ενδιαφέρον για τον ακόλουθο λόγο - αντί να απαιτεί γνώση σχετικά
φύση της εργασίας εκ των προτέρων, ο αλγόριθμος μαθαίνει την προηγούμενη συμπεριφορά της εργασίας και θέτει
προτεραιότητες αναλόγως. Έτσι, προσπαθεί να κάθεται σε δύο καρέκλες ταυτόχρονα - για να επιτύχει απόδοση για μικρές εργασίες (SJF, STCF) και ειλικρινά να τρέχει μεγάλες,
Εργασίες φόρτωσης CPU. Ως εκ τούτου, πολλά συστήματα, συμπεριλαμβανομένων των BSD και των παραγώγων τους,
Τα Solaris, Windows, Mac χρησιμοποιούν κάποια μορφή αλγορίθμου ως προγραμματιστή
Το MLFQ ως βάση.
Πρόσθετα υλικά:
- (υπολογισμός)
Πηγή: www.habr.com