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

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

Προγραμματισμός CPU είναι μια διαδικασία προσδιορισμού της διεργασίας που θα κατέχει την CPU για εκτέλεση ενώ μια άλλη διεργασία βρίσκεται σε αναμονή. Η κύρια εργασία του χρονοπρογραμματισμού της CPU είναι να διασφαλιστεί ότι κάθε φορά που η CPU παραμένει αδρανής, το λειτουργικό σύστημα επιλέγει τουλάχιστον μία από τις διεργασίες που είναι διαθέσιμες στην ουρά έτοιμης εκτέλεσης. Η διαδικασία επιλογής εκτελείται από τον χρονοπρογραμματιστή της 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 στη διεργασία. Ο αποστολέας θα πρέπει να είναι γρήγορος, ώστε να μπορεί να εκτελείται σε κάθε διακόπτη περιβάλλοντος. Η καθυστέρηση αποστολής είναι ο χρόνος που χρειάζεται ο χρονοπρογραμματιστής της CPU για να σταματήσει μια διεργασία και να ξεκινήσει μια άλλη.

Λειτουργίες που εκτελεί ο αποστολέας:

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

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

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

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

Χρονοδρομολόγηση Algorithms

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Χαρακτηριστικά του Προγραμματισμού Ουρών Πολλαπλών Επιπέδων

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

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

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

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

Συχνές Ερωτήσεις