Προγραμματισμός CPU Algorithms in Operating Systems

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ελαχιστοποίηση

ΧΡΟΝΟΣ ΑΝΑΜΟΝΗΣ: Ο χρόνος αναμονής είναι ένα ποσό που χρειάζεται συγκεκριμένη διαδικασία για να περιμένει στην ουρά ετοιμότητας.

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

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

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

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

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

Τι είναι το Dispatcher;

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

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

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

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

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

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

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

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

Καθώς η διαδικασία εισέρχεται στην ουρά ετοιμότητας, το PCB (Μπλοκ Ελέγχου Διαδικασίας) συνδέεται με την ουρά της ουράς. Έτσι, όταν η CPU γίνει ελεύθερη, θα πρέπει να αντιστοιχιστεί στη διαδικασία στην αρχή της ουράς.

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

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

Συντομότερος Υπολειπόμενος Χρόνος

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Σύνοψη

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