Αλγόριθμοι προγραμματισμού CPU σε λειτουργικά συστήματα

Τι είναι ο προγραμματισμός CPU;

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

Σε αυτό το σεμινάριο προγραμματισμού CPU, θα μάθετε:

• Τι είναι ο προγραμματισμός της CPU;
• Τύποι προγραμματισμού CPU
• Σημαντικές ορολογίες προγραμματισμού CPU
• Κριτήρια προγραμματισμού CPU
• Χρονόμετρο διαστήματος
• Τι είναι το Dispatcher;
• Τύποι αλγορίθμου προγραμματισμού CPU
• Ο πρώτος στη σειρά εξυπηρετείται πρώτος
• Συντομότερος χρόνος που απομένει
• Προγραμματισμός βάσει προτεραιότητας
• Προγραμματισμός Round-Robin
• Πιο σύντομη εργασία πρώτα
• Προγραμματισμός ουρών πολλαπλών επιπέδων
• Ο σκοπός ενός αλγορίθμου προγραμματισμού

Τύποι προγραμματισμού CPU

Ακολουθούν δύο είδη μεθόδων προγραμματισμού:

Προληπτικός προγραμματισμός

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

Μη Προληπτικός Προγραμματισμός

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

Όταν ο προγραμματισμός είναι Προληπτικός ή Μη Προληπτικός;

Για να προσδιορίσετε εάν ο προγραμματισμός είναι προληπτικός ή μη προληπτικός, λάβετε υπόψη αυτές τις τέσσερις παραμέτρους:

1. Μια διαδικασία αλλάζει από την εκτέλεση σε κατάσταση αναμονής.
2. Η συγκεκριμένη διαδικασία αλλάζει από την κατάσταση λειτουργίας σε κατάσταση ετοιμότητας.
3. Η συγκεκριμένη διαδικασία αλλάζει από την κατάσταση αναμονής στην κατάσταση ετοιμότητας.
4. Η διαδικασία ολοκλήρωσε την εκτέλεση και τερματίστηκε.

Ισχύουν μόνο οι όροι 1 και 4, ο προγραμματισμός ονομάζεται μη προληπτικός.

Όλοι οι άλλοι προγραμματισμοί είναι προληπτικοί.

Σημαντικές ορολογίες προγραμματισμού CPU

• Ώρα ριπής / Ώρα εκτέλεσης: Είναι ένας χρόνος που απαιτείται από τη διαδικασία για την ολοκλήρωση της εκτέλεσης. Ονομάζεται επίσης χρόνος λειτουργίας.
• Ώρα άφιξης: όταν μια διαδικασία εισέρχεται σε κατάσταση ετοιμότητας
• Χρόνος ολοκλήρωσης: όταν ολοκληρωθεί η διαδικασία και βγείτε από ένα σύστημα
• Πολυπρογραμματισμός: Ένας αριθμός προγραμμάτων που μπορούν να είναι παρόντα στη μνήμη ταυτόχρονα.
• Εργασίες: Είναι ένας τύπος προγράμματος χωρίς καμία αλληλεπίδραση χρήστη.
• Χρήστης: Είναι ένα είδος προγράμματος που έχει αλληλεπίδραση με τον χρήστη.
• Διαδικασία: Είναι η αναφορά που χρησιμοποιείται τόσο για εργασία όσο και για χρήστη.
• Κύκλος ριπής CPU / IO: Χαρακτηρίζει την εκτέλεση της διαδικασίας, η οποία εναλλάσσεται μεταξύ της δραστηριότητας CPU και I / O. Οι χρόνοι CPU είναι συνήθως μικρότεροι από τους χρόνους I / O.

Κριτήρια προγραμματισμού CPU

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

Αυξάνω στον ανώτατο βαθμό:

Χρήση CPU: Η χρήση της CPU είναι το κύριο καθήκον στο οποίο το λειτουργικό σύστημα πρέπει να διασφαλίσει ότι η CPU παραμένει όσο το δυνατόν πιο απασχολημένη. Μπορεί να κυμαίνεται από 0 έως 100 τοις εκατό. Ωστόσο, για το RTOS, μπορεί να κυμαίνεται από 40 τοις εκατό για χαμηλό επίπεδο και 90 τοις εκατό για το σύστημα υψηλού επιπέδου.

Throughput: Ο αριθμός διεργασιών που ολοκληρώνουν την εκτέλεση ανά μονάδα χρόνου είναι γνωστός. Έτσι, όταν η CPU είναι απασχολημένη με την εκτέλεση της διαδικασίας, εκείνη τη στιγμή, η εργασία γίνεται και η εργασία που ολοκληρώνεται ανά μονάδα χρόνου ονομάζεται Throughput.

Σμικροποιώ:

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

Χρόνος απόκρισης: Πρόκειται για το χρονικό διάστημα κατά το οποίο το αίτημα υποβλήθηκε μέχρι την πρώτη απάντηση.

Χρόνος ανακύκλωσης: Ο χρόνος ανακύκλωσης είναι ένας χρόνος για την εκτέλεση μιας συγκεκριμένης διαδικασίας. Είναι ο υπολογισμός του συνολικού χρόνου που αφιερώνεται για να μπείτε στη μνήμη, να περιμένετε στην ουρά και να εκτελείτε στη CPU. Η περίοδος μεταξύ του χρόνου υποβολής της διαδικασίας έως τον χρόνο ολοκλήρωσης είναι ο χρόνος ανακύκλωσης.

Χρονόμετρο διαστήματος

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

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

Τι είναι το Dispatcher;

Είναι μια μονάδα που παρέχει έλεγχο της CPU στη διαδικασία. Το Dispatcher πρέπει να είναι γρήγορο, ώστε να μπορεί να τρέχει σε κάθε διακόπτη περιβάλλοντος. Η καθυστέρηση αποστολής είναι ο χρόνος που απαιτείται από τον προγραμματιστή CPU για να σταματήσει μια διαδικασία και να ξεκινήσει μια άλλη.

Λειτουργίες που εκτελούνται από το Dispatcher:

• Εναλλαγή περιβάλλοντος
• Μετάβαση σε λειτουργία χρήστη
• Μετακίνηση στη σωστή θέση στο πρόσφατα φορτωμένο πρόγραμμα.

Τύποι αλγορίθμου προγραμματισμού CPU

Υπάρχουν κυρίως έξι τύποι αλγορίθμων προγραμματισμού διεργασιών

1. First Come First Serve (FCFS)
2. Προγραμματισμός συντομότερης-πρώτης εργασίας (SJF)
3. Συντομότερος χρόνος που απομένει
4. Προγραμματισμός προτεραιότητας
5. Προγραμματισμός Round Robin
6. Προγραμματισμός ουράς πολλαπλών επιπέδων

Ο πρώτος στη σειρά εξυπηρετείται πρώτος

Το First Come First Serve είναι η πλήρης μορφή του FCFS. Είναι ο ευκολότερος και πιο απλός αλγόριθμος προγραμματισμού CPU. Σε αυτόν τον τύπο αλγορίθμου, η διαδικασία που ζητά την CPU παίρνει πρώτα την κατανομή της CPU. Αυτή η μέθοδος προγραμματισμού μπορεί να διαχειριστεί με μια ουρά FIFO.

Καθώς η διαδικασία εισέρχεται στην έτοιμη ουρά, το PCB του (Process Control Block) συνδέεται με την ουρά της ουράς. Έτσι, όταν η CPU γίνεται δωρεάν, θα πρέπει να εκχωρηθεί στη διαδικασία στην αρχή της ουράς.

Χαρακτηριστικά της μεθόδου FCFS:

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

Συντομότερος χρόνος που απομένει

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

Χαρακτηριστικά της μεθόδου προγραμματισμού SRT:

• Αυτή η μέθοδος εφαρμόζεται κυρίως σε περιβάλλοντα παρτίδας όπου απαιτείται να προτιμηθούν σύντομες εργασίες.
• Αυτή δεν είναι μια ιδανική μέθοδος για την εφαρμογή του σε ένα κοινό σύστημα όπου ο απαιτούμενος χρόνος CPU είναι άγνωστος.
• Συσχετίστε με κάθε διαδικασία όσο το μήκος της επόμενης ριπής της CPU. Έτσι, το λειτουργικό σύστημα χρησιμοποιεί αυτά τα μήκη, πράγμα που βοηθά στον προγραμματισμό της διαδικασίας με το συντομότερο δυνατό χρόνο.

Προγραμματισμός βάσει προτεραιότητας

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

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

Προγραμματισμός Round-Robin

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

Χαρακτηριστικά του προγραμματισμού Round-Robin

• Το Round Robin είναι ένα υβριδικό μοντέλο που βασίζεται στο ρολόι
• Το χρονικό διάστημα πρέπει να είναι το ελάχιστο, το οποίο έχει ανατεθεί για επεξεργασία μιας συγκεκριμένης εργασίας. Ωστόσο, μπορεί να διαφέρει για διαφορετικές διαδικασίες.
• Είναι ένα σύστημα πραγματικού χρόνου που ανταποκρίνεται στο συμβάν εντός συγκεκριμένου χρονικού ορίου.

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

Το SJF είναι μια πλήρης μορφή του (Shortest job first) είναι ένας αλγόριθμος προγραμματισμού στον οποίο η διαδικασία με τον μικρότερο χρόνο εκτέλεσης θα πρέπει να επιλεγεί για εκτέλεση στη συνέχεια. Αυτή η μέθοδος προγραμματισμού μπορεί να είναι προληπτική ή μη προληπτική. Μειώνει σημαντικά τον μέσο όρο του χρόνου αναμονής για άλλες διεργασίες που αναμένουν εκτέλεση

Χαρακτηριστικά του προγραμματισμού SJF

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

Προγραμματισμός ουρών πολλαπλών επιπέδων

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

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

Χαρακτηριστικό του προγραμματισμού ουρών πολλαπλών επιπέδων:

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

Ο σκοπός ενός αλγορίθμου προγραμματισμού

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

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

Περίληψη:

• Ο προγραμματισμός CPU είναι μια διαδικασία προσδιορισμού της διαδικασίας που θα διαθέτει η CPU για εκτέλεση, ενώ μια άλλη διαδικασία είναι σε αναμονή.
• Στον Προληπτικό Προγραμματισμό, οι εργασίες ανατίθενται κυρίως με τις προτεραιότητές τους.
• Στη μέθοδο μη προληπτικού προγραμματισμού, η CPU έχει εκχωρηθεί σε μια συγκεκριμένη διαδικασία.
• Ο χρόνος ριπής είναι ένας χρόνος που απαιτείται για την ολοκλήρωση της διαδικασίας. Ονομάζεται επίσης χρόνος λειτουργίας.
• Η χρήση της CPU είναι το κύριο καθήκον στο οποίο το λειτουργικό σύστημα πρέπει να διασφαλίσει ότι η CPU παραμένει όσο το δυνατόν πιο απασχολημένη
• Ο αριθμός των διεργασιών που ολοκληρώνουν την εκτέλεση ανά μονάδα χρόνου είναι γνωστός.
• Ο χρόνος αναμονής είναι ένα ποσό που πρέπει να περιμένει μια συγκεκριμένη διαδικασία στην έτοιμη ουρά.
• Πρόκειται για ένα χρονικό διάστημα κατά το οποίο το αίτημα υποβλήθηκε μέχρι την πρώτη απάντηση.
• Ο χρόνος ανακύκλωσης είναι ένας χρόνος για την εκτέλεση μιας συγκεκριμένης διαδικασίας.
• Η διακοπή του χρονοδιακόπτη είναι μια μέθοδος που σχετίζεται στενά με την προτίμηση,
• Ένας διεκπεραιωτής είναι μια ενότητα που παρέχει έλεγχο της CPU στη διαδικασία.
• Έξι τύποι αλγορίθμων προγραμματισμού διεργασιών είναι:
• First Come First Serve (FCFS), 2) Shorting-Job-First (SJF) Προγραμματισμός 3) Συντομότερος χρόνος που απομένει 4) Προγραμματισμός προτεραιότητας 5) Προγραμματισμός Round Robin 6) Προγραμματισμός ουράς πολλαπλών επιπέδων
• Στη μέθοδο First Come First Serve, η διαδικασία που ζητά την CPU λαμβάνει πρώτα την κατανομή της CPU.
• Στο συντομότερο χρόνο που απομένει, η διαδικασία θα κατανεμηθεί στην εργασία, η οποία βρίσκεται πλησιέστερα στην ολοκλήρωσή της.
• Στο, Προγραμματισμός προτεραιότητας ο προγραμματιστής επιλέγει τις εργασίες που θα λειτουργούν σύμφωνα με την προτεραιότητα.
• Στο, αυτός ο προγραμματισμός Round Robin λειτουργεί κατ 'αρχήν, όπου κάθε άτομο παίρνει το ίδιο μερίδιο σε κάτι με τη σειρά
• Στη συντομότερη εργασία πρώτα, ο συντομότερος χρόνος εκτέλεσης θα πρέπει να επιλεγεί για επόμενη εκτέλεση
• Στον προγραμματισμό πολλαπλών επιπέδων, η μέθοδος χωρίζει την έτοιμη ουρά σε διάφορες ξεχωριστές ουρές. Σε αυτήν τη μέθοδο, οι διαδικασίες εκχωρούνται σε μια ουρά με βάση μια συγκεκριμένη ιδιότητα
• Η CPU χρησιμοποιεί προγραμματισμό για να βελτιώσει την αποτελεσματικότητά της.