Εισαγωγή στα Λειτουργικά Συστήματα
Γεια σου Χαμπρ! Θα ήθελα να επιστήσω την προσοχή σας μια σειρά άρθρων-μεταφράσεων μιας ενδιαφέρουσας κατά τη γνώμη μου λογοτεχνίας - της ΟΣΤΕΠ. Αυτό το υλικό εξετάζει αρκετά βαθιά τη δουλειά λειτουργικών συστημάτων που μοιάζουν με unix, δηλαδή την εργασία με διεργασίες, διάφορους χρονοπρογραμματιστές, μνήμη και άλλα παρόμοια στοιχεία που συνθέτουν ένα σύγχρονο λειτουργικό σύστημα. Μπορείτε να δείτε το πρωτότυπο όλων των υλικών εδώ . Σημειώστε ότι η μετάφραση έγινε αντιεπαγγελματικά (αρκετά ελεύθερα), αλλά ελπίζω να διατήρησα το γενικό νόημα.
Εργαστήριο για αυτό το θέμα μπορείτε να βρείτε εδώ:
Άλλα μέρη:
Μπορείτε επίσης να δείτε το κανάλι μου στο =)
Εισαγωγή στο Scheduler
Η ουσία του προβλήματος: Πώς να αναπτύξετε μια πολιτική χρονοπρογραμματισμού
Πώς πρέπει να σχεδιάζονται τα υποκείμενα πλαίσια πολιτικής χρονοπρογραμματιστή; Ποιες πρέπει να είναι οι βασικές παραδοχές; Ποιες μετρήσεις είναι σημαντικές; Ποιες βασικές τεχνικές χρησιμοποιήθηκαν στα πρώιμα υπολογιστικά συστήματα;
Υποθέσεις φόρτου εργασίας
Πριν συζητήσουμε πιθανές πολιτικές, ας κάνουμε πρώτα μερικές απλοποιητικές παρεκκλίσεις σχετικά με τις διεργασίες που εκτελούνται στο σύστημα, οι οποίες ονομάζονται συλλογικά φόρτο εργασίας. Ο καθορισμός του φόρτου εργασίας είναι ένα κρίσιμο μέρος των πολιτικών δημιουργίας και όσο περισσότερα γνωρίζετε για τον φόρτο εργασίας, τόσο καλύτερη είναι η πολιτική που μπορείτε να γράψετε.
Ας κάνουμε τις ακόλουθες υποθέσεις σχετικά με τις διεργασίες που εκτελούνται στο σύστημα, που μερικές φορές ονομάζονται επίσης θέσεις εργασίας (καθήκοντα). Σχεδόν όλες αυτές οι υποθέσεις δεν είναι ρεαλιστικές, αλλά είναι απαραίτητες για την ανάπτυξη της σκέψης.
- Κάθε εργασία εκτελείται για το ίδιο χρονικό διάστημα,
- Όλες οι εργασίες ορίζονται ταυτόχρονα,
- Η εργασία που έχει ανατεθεί λειτουργεί μέχρι την ολοκλήρωσή της,
- Όλες οι εργασίες χρησιμοποιούν μόνο CPU,
- Ο χρόνος εκτέλεσης κάθε εργασίας είναι γνωστός.
Μετρήσεις χρονοδιαγράμματος
Εκτός από ορισμένες υποθέσεις σχετικά με το φορτίο, χρειάζεται ένα άλλο εργαλείο για τη σύγκριση διαφορετικών πολιτικών προγραμματισμού: μετρήσεις προγραμματιστή. Μια μέτρηση είναι απλώς ένα μέτρο για κάτι. Υπάρχει ένας αριθμός μετρήσεων που μπορούν να χρησιμοποιηθούν για τη σύγκριση προγραμματιστών.
Για παράδειγμα, θα χρησιμοποιήσουμε μια μέτρηση που ονομάζεται χρόνος ολοκλήρωσης (χρόνος ολοκλήρωσης). Ο χρόνος διεκπεραίωσης της εργασίας ορίζεται ως η διαφορά μεταξύ του χρόνου ολοκλήρωσης της εργασίας και του χρόνου άφιξης της εργασίας στο σύστημα.
Tturnaround=TCompletion−Tarrival
Εφόσον υποθέσαμε ότι όλες οι εργασίες έφτασαν ταυτόχρονα, τότε Ta=0 και επομένως Tt=Tc. Αυτή η τιμή θα αλλάξει φυσικά όταν αλλάξουμε τις παραπάνω παραδοχές.
Μια άλλη μέτρηση - δικαιοσύνη (δικαιοσύνη, ειλικρίνεια). Η παραγωγικότητα και η δικαιοσύνη είναι συχνά αντίθετα χαρακτηριστικά στον προγραμματισμό. Για παράδειγμα, ο προγραμματιστής μπορεί να βελτιστοποιήσει την απόδοση, αλλά με το κόστος της αναμονής για την εκτέλεση άλλων εργασιών, μειώνοντας έτσι τη δικαιοσύνη.
FIRST IN FIRST OUT (FIFO)
Ο πιο βασικός αλγόριθμος που μπορούμε να εφαρμόσουμε ονομάζεται FIFO ή first come (in), first service (out). Αυτός ο αλγόριθμος έχει πολλά πλεονεκτήματα: είναι πολύ εύκολος στην εφαρμογή του και ταιριάζει με όλες τις υποθέσεις μας και κάνει τη δουλειά αρκετά καλά.
Ας δούμε ένα απλό παράδειγμα. Ας πούμε ότι τέθηκαν 3 εργασίες ταυτόχρονα. Αλλά ας υποθέσουμε ότι η εργασία Α έφτασε λίγο νωρίτερα από όλες τις άλλες, επομένως θα εμφανιστεί στη λίστα εκτέλεσης νωρίτερα από τις άλλες, όπως ακριβώς το Β σε σχέση με το C. Ας υποθέσουμε ότι καθεμία από αυτές θα εκτελεστεί για 10 δευτερόλεπτα. Ποιος θα είναι ο μέσος χρόνος για την ολοκλήρωση αυτών των εργασιών σε αυτήν την περίπτωση;
Μετρώντας τις τιμές - 10+20+30 και διαιρώντας με το 3, παίρνουμε τον μέσο χρόνο εκτέλεσης του προγράμματος ίσο με 20 δευτερόλεπτα.
Τώρα ας προσπαθήσουμε να αλλάξουμε τις υποθέσεις μας. Συγκεκριμένα, η υπόθεση 1 και επομένως δεν θα υποθέτουμε πλέον ότι κάθε εργασία χρειάζεται τον ίδιο χρόνο για να εκτελεστεί. Πώς θα αποδώσει η FIFO αυτή τη φορά;
Όπως αποδεικνύεται, διαφορετικοί χρόνοι εκτέλεσης εργασιών έχουν εξαιρετικά αρνητικό αντίκτυπο στην παραγωγικότητα του αλγορίθμου FIFO. Ας υποθέσουμε ότι η εργασία Α θα χρειαστούν 100 δευτερόλεπτα για να ολοκληρωθεί, ενώ οι Β και Γ θα χρειαστούν ακόμα 10 δευτερόλεπτα το καθένα.
Όπως φαίνεται από το σχήμα, ο μέσος χρόνος για το σύστημα θα είναι (100+110+120)/3=110. Αυτό το αποτέλεσμα ονομάζεται εφέ συνοδείας, όταν ορισμένοι βραχυπρόθεσμοι καταναλωτές ενός πόρου θα κάνουν ουρά μετά από έναν βαρύ καταναλωτή. Είναι σαν την ουρά στο παντοπωλείο όταν υπάρχει ένας πελάτης μπροστά σου με ένα γεμάτο καλάθι. Η καλύτερη λύση στο πρόβλημα είναι να προσπαθήσετε να αλλάξετε την ταμειακή μηχανή ή να χαλαρώσετε και να αναπνεύσετε βαθιά.
Πρώτα η πιο σύντομη εργασία
Είναι δυνατόν να λυθεί με κάποιο τρόπο μια παρόμοια κατάσταση με διαδικασίες βαρέων βαρών; Σίγουρα. Ένας άλλος τύπος προγραμματισμού ονομάζεταιΠρώτα η πιο σύντομη εργασία (SJF). Ο αλγόριθμός του είναι επίσης αρκετά πρωτόγονος - όπως υποδηλώνει το όνομα, οι πιο σύντομες εργασίες θα ξεκινήσουν πρώτα, η μία μετά την άλλη.
Σε αυτό το παράδειγμα, το αποτέλεσμα της εκτέλεσης των ίδιων διεργασιών θα είναι μια βελτίωση στον μέσο χρόνο εκτέλεσης του προγράμματος και θα είναι ίσο με 50 αντί για 110, που είναι σχεδόν 2 φορές καλύτερο.
Έτσι, για τη δεδομένη υπόθεση ότι όλες οι εργασίες φτάνουν την ίδια στιγμή, ο αλγόριθμος SJF φαίνεται να είναι ο βέλτιστος αλγόριθμος. Ωστόσο, οι υποθέσεις μας εξακολουθούν να μην φαίνονται ρεαλιστικές. Αυτή τη φορά αλλάζουμε την υπόθεση 2 και αυτή τη φορά φανταζόμαστε ότι οι εργασίες μπορούν να υπάρχουν ανά πάσα στιγμή, και όχι όλες ταυτόχρονα. Σε τι προβλήματα μπορεί να οδηγήσει αυτό;
Ας φανταστούμε ότι η εργασία Α (100c) φτάνει πρώτη και αρχίζει να εκτελείται. Στο t=10, φτάνουν οι εργασίες Β και Γ, καθεμία από τις οποίες θα διαρκέσει 10 δευτερόλεπτα. Άρα ο μέσος χρόνος εκτέλεσης είναι (100+(110-10)+(120-10))3 = 103. Τι θα μπορούσε να κάνει ο προγραμματιστής για να το βελτιώσει;
Πρώτα ο συντομότερος χρόνος για την ολοκλήρωση (STCF)
Προκειμένου να βελτιώσουμε την κατάσταση, παραλείπουμε την υπόθεση 3 ότι το πρόγραμμα έχει ξεκινήσει και εκτελείται μέχρι την ολοκλήρωση. Επιπλέον, θα χρειαστούμε υποστήριξη υλικού και, όπως μπορείτε να μαντέψετε, θα χρησιμοποιήσουμε χρονοδιακόπτη για να διακόψετε μια εργασία που εκτελείται και εναλλαγή περιβάλλοντος. Έτσι, ο χρονοπρογραμματιστής μπορεί να κάνει κάτι τη στιγμή που φτάνουν οι εργασίες Β, Γ - να σταματήσει να εκτελεί την εργασία Α και να βάλει τις εργασίες Β και Γ σε επεξεργασία και, μετά την ολοκλήρωσή τους, να συνεχίσει την εκτέλεση της διαδικασίας Α. Ένας τέτοιος χρονοπρογραμματιστής ονομάζεται STCFή Πρώτα προληπτική εργασία.
Το αποτέλεσμα αυτού του σχεδιασμού θα είναι το ακόλουθο αποτέλεσμα: ((120-0)+(20-10)+(30-10))/3=50. Έτσι, ένας τέτοιος προγραμματιστής γίνεται ακόμα πιο βέλτιστος για τις εργασίες μας.
Χρόνος μετρικής απόκρισης
Έτσι, εάν γνωρίζουμε το χρόνο εκτέλεσης των εργασιών και ότι αυτές οι εργασίες χρησιμοποιούν μόνο CPU, το STCF θα είναι η καλύτερη λύση. Και μια φορά στα πρώτα χρόνια, αυτοί οι αλγόριθμοι λειτουργούσαν αρκετά καλά. Ωστόσο, ο χρήστης περνά πλέον τον περισσότερο χρόνο του στο τερματικό και αναμένει μια παραγωγική διαδραστική εμπειρία. Έτσι γεννήθηκε μια νέα μέτρηση - χρόνος απόκρισης (απάντηση).
Ο χρόνος απόκρισης υπολογίζεται ως εξής:
Tresponse=Tfirstrun−Tarrival
Έτσι, για το προηγούμενο παράδειγμα, ο χρόνος απόκρισης θα είναι: A=0, B=0, C=10 (abg=3,33).
Και αποδεικνύεται ότι ο αλγόριθμος STCF δεν είναι τόσο καλός σε μια κατάσταση όπου φτάνουν 3 εργασίες ταυτόχρονα - θα πρέπει να περιμένει μέχρι να ολοκληρωθούν πλήρως οι μικρές εργασίες. Έτσι, ο αλγόριθμος είναι καλός για τη μέτρηση του χρόνου ολοκλήρωσης, αλλά κακός για τη μέτρηση διαδραστικότητας. Φανταστείτε να καθόσαστε σε ένα τερματικό προσπαθώντας να πληκτρολογήσετε χαρακτήρες σε ένα πρόγραμμα επεξεργασίας και έπρεπε να περιμένετε περισσότερα από 10 δευτερόλεπτα επειδή κάποια άλλη εργασία καταλάμβανε τη CPU. Δεν είναι πολύ ευχάριστο.
Επομένως, αντιμετωπίζουμε ένα άλλο πρόβλημα - πώς μπορούμε να δημιουργήσουμε έναν προγραμματιστή που να είναι ευαίσθητος στο χρόνο απόκρισης;
έγγραφο φέρων τας υπογραφάς εν κύκλω
Αναπτύχθηκε ένας αλγόριθμος για την επίλυση αυτού του προβλήματος έγγραφο φέρων τας υπογραφάς εν κύκλω (RR). Η βασική ιδέα είναι αρκετά απλή: αντί να εκτελούμε εργασίες μέχρι να ολοκληρωθούν, θα εκτελέσουμε την εργασία για μια συγκεκριμένη χρονική περίοδο (που ονομάζεται time slice) και στη συνέχεια θα μεταβούμε σε άλλη εργασία από την ουρά. Ο αλγόριθμος επαναλαμβάνει την εργασία του μέχρι να ολοκληρωθούν όλες οι εργασίες. Σε αυτήν την περίπτωση, ο χρόνος εκτέλεσης του προγράμματος πρέπει να είναι πολλαπλάσιος του χρόνου μετά τον οποίο ο χρονοδιακόπτης θα διακόψει τη διαδικασία. Για παράδειγμα, εάν ένας χρονοδιακόπτης διακόπτει μια διαδικασία κάθε x=10ms, τότε το μέγεθος του παραθύρου εκτέλεσης διεργασίας θα πρέπει να είναι πολλαπλάσιο του 10 και να είναι 10,20 ή x*10.
Ας δούμε ένα παράδειγμα: Οι εργασίες ABC φτάνουν ταυτόχρονα στο σύστημα και κάθε μία από αυτές θέλει να εκτελεστεί για 5 δευτερόλεπτα. Ο αλγόριθμος SJF θα ολοκληρώσει κάθε εργασία μέχρι την ολοκλήρωση πριν ξεκινήσει μια άλλη. Αντίθετα, ο αλγόριθμος RR με ένα παράθυρο εκκίνησης = 1s θα περάσει από τις εργασίες ως εξής (Εικ. 4.3):
(Ξανά SJF (Κακό για τον χρόνο απόκρισης)
(Round Robin (Καλό για χρόνο απόκρισης)
Ο μέσος χρόνος απόκρισης για τον αλγόριθμο RR είναι (0+1+2)/3=1, ενώ για τον SJF (0+5+10)/3=5.
Είναι λογικό να υποθέσουμε ότι το χρονικό παράθυρο είναι μια πολύ σημαντική παράμετρος για το RR· όσο μικρότερο είναι, τόσο μεγαλύτερος είναι ο χρόνος απόκρισης. Ωστόσο, δεν πρέπει να το κάνετε πολύ μικρό, καθώς ο χρόνος εναλλαγής περιβάλλοντος θα παίξει επίσης ρόλο στη συνολική απόδοση. Έτσι, η επιλογή του χρόνου παραθύρου εκτέλεσης ορίζεται από τον αρχιτέκτονα του λειτουργικού συστήματος και εξαρτάται από τις εργασίες που σχεδιάζονται να εκτελεστούν σε αυτό. Η εναλλαγή πλαισίου δεν είναι η μόνη λειτουργία υπηρεσίας που χάνει χρόνο - το τρέχον πρόγραμμα λειτουργεί σε πολλά άλλα πράγματα, για παράδειγμα, διάφορες κρυφές μνήμες και με κάθε διακόπτη είναι απαραίτητο να αποθηκεύσετε και να επαναφέρετε αυτό το περιβάλλον, το οποίο μπορεί επίσης να πάρει πολλά χρόνος.
Το RR είναι ένας εξαιρετικός προγραμματιστής αν μιλούσαμε μόνο για τη μέτρηση χρόνου απόκρισης. Πώς θα συμπεριφερθεί όμως η μέτρηση χρόνου εκτέλεσης εργασιών με αυτόν τον αλγόριθμο; Εξετάστε το παραπάνω παράδειγμα, όταν ο χρόνος λειτουργίας των A, B, C = 5s και φτάσετε την ίδια στιγμή. Η εργασία Α θα τελειώσει στα 13, η Β στα 14, η Γ στα 15 δευτερόλεπτα και ο μέσος χρόνος διεκπεραίωσης θα είναι 14 δευτερόλεπτα. Έτσι, ο RR είναι ο χειρότερος αλγόριθμος για τη μέτρηση κύκλου εργασιών.
Σε γενικότερους όρους, οποιοσδήποτε αλγόριθμος τύπου RR είναι δίκαιος· διαιρεί εξίσου τον χρόνο της CPU μεταξύ όλων των διεργασιών. Και έτσι, αυτές οι μετρήσεις συνεχώς συγκρούονται μεταξύ τους.
Έτσι, έχουμε αρκετούς αντιπαραβαλλόμενους αλγόριθμους και ταυτόχρονα απομένουν αρκετές υποθέσεις - ότι ο χρόνος εργασίας είναι γνωστός και ότι η εργασία χρησιμοποιεί μόνο την CPU.
Μίξη με I/O
Πρώτα απ 'όλα, ας αφαιρέσουμε την υπόθεση 4 ότι η διαδικασία χρησιμοποιεί μόνο την CPU· φυσικά, αυτό δεν συμβαίνει και οι διεργασίες μπορούν να έχουν πρόσβαση σε άλλο εξοπλισμό.
Τη στιγμή που οποιαδήποτε διεργασία ζητά μια λειτουργία I/O, η διαδικασία εισέρχεται στην κατάσταση αποκλεισμού, περιμένοντας να ολοκληρωθεί η I/O. Εάν το I/O σταλεί στον σκληρό δίσκο, τότε μια τέτοια λειτουργία μπορεί να διαρκέσει έως και αρκετά ms ή περισσότερο και ο επεξεργαστής θα είναι αδρανής αυτήν τη στιγμή. Κατά τη διάρκεια αυτής της περιόδου, ο προγραμματιστής μπορεί να απασχολήσει τον επεξεργαστή με οποιαδήποτε άλλη διαδικασία. Η επόμενη απόφαση που θα πρέπει να πάρει ο χρονοπρογραμματιστής είναι πότε η διαδικασία θα ολοκληρώσει το I/O της. Όταν συμβεί αυτό, θα προκύψει μια διακοπή και το λειτουργικό σύστημα θα θέσει τη διαδικασία που κάλεσε το I/O σε κατάσταση ετοιμότητας.
Ας δούμε ένα παράδειγμα πολλών προβλημάτων. Κάθε ένα από αυτά απαιτεί 50ms χρόνο CPU. Ωστόσο, το πρώτο θα έχει πρόσβαση στο I/O κάθε 10ms (το οποίο θα εκτελείται επίσης κάθε 10ms). Και η διαδικασία Β χρησιμοποιεί απλώς έναν επεξεργαστή 50ms χωρίς I/O.
Σε αυτό το παράδειγμα θα χρησιμοποιήσουμε τον προγραμματιστή STCF. Πώς θα συμπεριφερθεί ο χρονοπρογραμματιστής εάν ξεκινήσει μια διεργασία όπως το Α σε αυτόν; Θα κάνει τα εξής: πρώτα θα επεξεργαστεί πλήρως τη διαδικασία Α και στη συνέχεια τη διαδικασία Β.
Η παραδοσιακή προσέγγιση για την επίλυση αυτού του προβλήματος είναι να αντιμετωπίζεται κάθε υποεργασία των 10 ms της διαδικασίας Α ως ξεχωριστή εργασία. Έτσι, όταν ξεκινάμε με τον αλγόριθμο STJF, η επιλογή μεταξύ μιας εργασίας 50 ms και μιας εργασίας 10 ms είναι προφανής. Στη συνέχεια, όταν ολοκληρωθεί η δευτερεύουσα εργασία Α, θα εκκινηθεί η διεργασία Β και το I/O. Μετά την ολοκλήρωση της εισόδου/εξόδου, θα είναι σύνηθες να ξεκινά ξανά η διαδικασία Α των 10 ms αντί της διαδικασίας Β. Με αυτόν τον τρόπο, είναι δυνατή η εφαρμογή επικάλυψης, όπου η CPU χρησιμοποιείται από μια άλλη διεργασία ενώ η πρώτη περιμένει την I/O. Και ως αποτέλεσμα, το σύστημα χρησιμοποιείται καλύτερα - τη στιγμή που οι αλληλεπιδραστικές διεργασίες περιμένουν I/O, μπορούν να εκτελεστούν άλλες διεργασίες στον επεξεργαστή.
Το Oracle δεν υπάρχει πια
Τώρα ας προσπαθήσουμε να απαλλαγούμε από την υπόθεση ότι ο χρόνος εκτέλεσης της εργασίας είναι γνωστός. Αυτή είναι γενικά η χειρότερη και πιο μη ρεαλιστική υπόθεση σε ολόκληρη τη λίστα. Στην πραγματικότητα, στο μέσο συνηθισμένο λειτουργικό σύστημα, το ίδιο το λειτουργικό σύστημα συνήθως γνωρίζει πολύ λίγα για το χρόνο εκτέλεσης των εργασιών, οπότε πώς μπορείτε να δημιουργήσετε έναν χρονοπρογραμματιστή χωρίς να γνωρίζετε πόσο χρόνο θα χρειαστεί για να εκτελεστεί η εργασία; Ίσως θα μπορούσαμε να χρησιμοποιήσουμε κάποιες αρχές RR για να λύσουμε αυτό το πρόβλημα;
Σύνολο
Εξετάσαμε τις βασικές ιδέες του προγραμματισμού εργασιών και εξετάσαμε 2 οικογένειες προγραμματιστών. Το πρώτο ξεκινά πρώτα τη συντομότερη εργασία και έτσι αυξάνει τον χρόνο διεκπεραίωσης, ενώ η δεύτερη διχάζεται μεταξύ όλων των εργασιών εξίσου, αυξάνοντας τον χρόνο απόκρισης. Και οι δύο αλγόριθμοι είναι κακοί όταν οι αλγόριθμοι της άλλης οικογένειας είναι καλοί. Εξετάσαμε επίσης πώς η παράλληλη χρήση CPU και I/O μπορεί να βελτιώσει την απόδοση, αλλά δεν λύθηκε το πρόβλημα με τη διόραση του λειτουργικού συστήματος. Και στο επόμενο μάθημα θα δούμε έναν σχεδιαστή που κοιτάζει στο άμεσο παρελθόν και προσπαθεί να προβλέψει το μέλλον. Και ονομάζεται ουρά ανατροφοδότησης πολλαπλών επιπέδων.
Πηγή: www.habr.com