Αλγόριθμος Προγραμματισμού Προτεραιότητας: Προληπτικός, Μη Προληπτικός
Ναθάνιελ Μπρουκς
⚡ Έξυπνη Σύνοψη
Ο Προγραμματισμός Προτεραιότητας είναι μια μέθοδος προγραμματισμού CPU που επιλέγει διεργασίες με βάση την προτεραιότητα, εκτελώντας πρώτα τις εργασίες υψηλότερης προτεραιότητας. Μπορεί να είναι προληπτική ή μη προληπτική, και οι διεργασίες με ίση προτεραιότητα διεκπεραιώνονται με σειρά προτεραιότητας ή με βάση την αρχή της κυκλικής προσέγγισης.
Τι είναι ο Προγραμματισμός Προτεραιότητας;
Προγραμματισμός προτεραιότητας είναι μια μέθοδος προγραμματισμού διαδικασιών που βασίζεται στην προτεραιότητα. Σε αυτόν τον αλγόριθμο, ο προγραμματιστής επιλέγει τις εργασίες που θα λειτουργήσουν σύμφωνα με την προτεραιότητα.
Οι διαδικασίες με υψηλότερη προτεραιότητα θα πρέπει να εκτελούνται πρώτα, ενώ οι θέσεις εργασίας με ίσες προτεραιότητες εκτελούνται σε κυκλική βάση ή FCFS. Η προτεραιότητα εξαρτάται από τις απαιτήσεις μνήμης, τις απαιτήσεις χρόνου κ.λπ.
Τύποι Προγραμματισμού Προτεραιότητας
Ο προγραμματισμός κατά προτεραιότητα χωρίζεται σε δύο κύριους τύπους:
Προληπτικός Προγραμματισμός
Στον Προληπτικό Προγραμματισμό, οι εργασίες ανατίθενται κυρίως με τις προτεραιότητές τους. Μερικές φορές είναι σημαντικό να εκτελέσετε μια εργασία με υψηλότερη προτεραιότητα πριν από μια άλλη εργασία χαμηλότερης προτεραιότητας, ακόμα κι αν η εργασία χαμηλότερης προτεραιότητας εξακολουθεί να εκτελείται. Η εργασία χαμηλότερης προτεραιότητας διατηρείται για κάποιο χρονικό διάστημα και συνεχίζεται όταν η εργασία υψηλότερης προτεραιότητας ολοκληρώσει την εκτέλεσή της.
Μη Προληπτικός Προγραμματισμός
Σε αυτόν τον τύπο μεθόδου προγραμματισμού, η CPU έχει ανατεθεί σε μια συγκεκριμένη διεργασία. Η διεργασία που κρατά την CPU απασχολημένη θα την απελευθερώσει είτε αλλάζοντας το περιβάλλον είτε τερματίζοντας. Είναι η μόνη μέθοδος που μπορεί να χρησιμοποιηθεί για διάφορες πλατφόρμες υλικού. Αυτό συμβαίνει επειδή δεν χρειάζεται ειδικό υλικό (για παράδειγμα, χρονοδιακόπτη) όπως ο προληπτικός προγραμματισμός.
Χαρακτηριστικά Προγραμματισμού Προτεραιότητας
- Ένας αλγόριθμος CPU που προγραμματίζει τις διαδικασίες με βάση την προτεραιότητα.
- Χρησιμοποιείται σε Operaσυστήματα για την εκτέλεση διαδικασιών παρτίδας.
- Εάν δύο εργασίες με την ίδια προτεραιότητα είναι ΕΤΟΙΜΕΣ, λειτουργεί σε α ΠΡΩΤΟΣ ΕΡΧΕΤΑΙ ΠΡΩΤΟΣ ΕΞΥΠΗΡΕΤΕΙΤΑΙ βάση.
- Στον προγραμματισμό προτεραιότητας, εκχωρείται ένας αριθμός σε κάθε διεργασία που υποδεικνύει το επίπεδο προτεραιότητάς της.
- Όσο χαμηλότερος είναι ο αριθμός, τόσο υψηλότερη είναι η προτεραιότητα.
- Σε αυτόν τον τύπο αλγορίθμου χρονοπρογραμματισμού, εάν φτάσει μια νεότερη διεργασία που έχει υψηλότερη προτεραιότητα από την τρέχουσα διεργασία, τότε η τρέχουσα διεργασία προαποκλείεται.
Παράδειγμα Προγραμματισμού Προτεραιότητας
Θεωρήστε τις ακόλουθες πέντε διεργασίες P1 έως P5. Κάθε διεργασία έχει τη δική της μοναδική προτεραιότητα, χρόνο burst και χρόνο άφιξης.
| Διαδικασία | Προτεραιότητα | Ώρα έκρηξης | Ωρα άφιξης |
|---|---|---|---|
| P1 | 1 | 4 | 0 |
| P2 | 2 | 3 | 0 |
| P3 | 1 | 7 | 6 |
| P4 | 3 | 4 | 11 |
| P5 | 2 | 2 | 12 |
Βήμα 0) Τη χρονική στιγμή = 0, φτάνουν οι διεργασίες P1 και P2. Η P1 έχει υψηλότερη προτεραιότητα από την P2. Η εκτέλεση ξεκινά με τη διεργασία P1, η οποία έχει χρόνο έκρηξης 4.
Βήμα 1) Τη χρονική στιγμή = 1, δεν φτάνει καμία νέα διεργασία. Η εκτέλεση συνεχίζεται με P1.
Βήμα 2) Τη στιγμή 2, δεν έρχεται νέα διαδικασία, επομένως μπορείτε να συνεχίσετε με το P1. Το P2 βρίσκεται στην ουρά αναμονής.
Βήμα 3) Τη χρονική στιγμή 3, δεν φτάνει καμία νέα διεργασία, επομένως μπορείτε να συνεχίσετε με την P1. Η διεργασία P2 βρίσκεται ακόμα στην ουρά αναμονής.
Βήμα 4) Τη στιγμή 4, το P1 έχει ολοκληρώσει την εκτέλεσή του. Το P2 ξεκινά την εκτέλεση.
Βήμα 5) Τη χρονική στιγμή = 5, δεν φτάνει καμία νέα διεργασία, επομένως συνεχίζουμε με το P2.
Βήμα 6) Τη χρονική στιγμή = 6, φτάνει το P3. Το P3 έχει υψηλότερη προτεραιότητα (1) σε σύγκριση με το P2 που έχει προτεραιότητα (2). Το P2 προλαμβάνεται και το P3 ξεκινά την εκτέλεσή του.
| Διαδικασία | Προτεραιότητα | Ώρα έκρηξης | Ωρα άφιξης |
|---|---|---|---|
| P1 | 1 | 4 | 0 |
| P2 | 2 | 1 στα 3 σε εκκρεμότητα | 0 |
| P3 | 1 | 7 | 6 |
| P4 | 3 | 4 | 11 |
| P5 | 2 | 2 | 12 |
Βήμα 7) Τη χρονική στιγμή 7, δεν φτάνει καμία νέα διεργασία, επομένως συνεχίζουμε με την P3. Η P2 βρίσκεται στην ουρά αναμονής.
Βήμα 8) Τη χρονική στιγμή = 8, δεν φτάνει καμία νέα διεργασία, επομένως μπορούμε να συνεχίσουμε με το P3.
Βήμα 9) Τη χρονική στιγμή = 9, δεν εμφανίζεται καμία νέα διεργασία, επομένως μπορούμε να συνεχίσουμε με το P3.
Βήμα 10) Στο χρονικό διάστημα 10, δεν εμφανίζεται καμία νέα διεργασία, επομένως συνεχίζουμε με το P3.
Βήμα 11) Τη χρονική στιγμή = 11, το P4 φτάνει με προτεραιότητα 4. Το P3 έχει υψηλότερη προτεραιότητα, επομένως συνεχίζει την εκτέλεσή του.
| Διαδικασία | Προτεραιότητα | Ώρα έκρηξης | Ωρα άφιξης |
|---|---|---|---|
| P1 | 1 | 4 | 0 |
| P2 | 2 | 1 στα 3 σε εκκρεμότητα | 0 |
| P3 | 1 | 2 στα 7 σε εκκρεμότητα | 6 |
| P4 | 3 | 4 | 11 |
| P5 | 2 | 2 | 12 |
Βήμα 12) Τη χρονική στιγμή = 12, φτάνει το P5. Το P3 έχει υψηλότερη προτεραιότητα, επομένως συνεχίζει την εκτέλεση.
Βήμα 13) Τη χρονική στιγμή = 13, το P3 ολοκληρώνει την εκτέλεση. Έχουμε τα P2, P4, P5 στην ουρά ετοιμότητας. Τα P2 και P5 έχουν ίση προτεραιότητα. Η ώρα άφιξης του P2 είναι πριν από το P5, επομένως το P2 ξεκινά την εκτέλεση.
| Διαδικασία | Προτεραιότητα | Ώρα έκρηξης | Ωρα άφιξης |
|---|---|---|---|
| P1 | 1 | 4 | 0 |
| P2 | 2 | 1 στα 3 σε εκκρεμότητα | 0 |
| P3 | 1 | 7 | 6 |
| P4 | 3 | 4 | 11 |
| P5 | 2 | 2 | 12 |
Βήμα 14) Τη χρονική στιγμή = 14, η διεργασία P2 έχει ολοκληρώσει την εκτέλεσή της. Οι διεργασίες P4 και P5 βρίσκονται σε κατάσταση αναμονής. Η διεργασία P5 έχει την υψηλότερη προτεραιότητα και ξεκινά την εκτέλεση.
Βήμα 15) Τη χρονική στιγμή = 15, η P5 συνεχίζει την εκτέλεση.
Βήμα 16) Τη χρονική στιγμή = 16, η P5 ολοκληρώνει την εκτέλεσή της. Η P4 είναι η μόνη διεργασία που απομένει. Ξεκινά την εκτέλεση.
Βήμα 17) Τη χρονική στιγμή = 20, η P4 έχει ολοκληρώσει την εκτέλεση και δεν έχει απομείνει καμία διεργασία.
Βήμα 18) Ας υπολογίσουμε τον μέσο χρόνο αναμονής για το παραπάνω παράδειγμα.
Χρόνος αναμονής = ώρα έναρξης – ώρα άφιξης + χρόνος αναμονής για την επόμενη ριπή
P1 = 0 - 0 = 0 P2 = 4 - 0 + 7 = 11 P3 = 6 - 6 = 0 P4 = 16 - 11 = 5 Average Waiting time = (0 + 11 + 0 + 5 + 2)/5 = 18/5 = 3.6
Πλεονεκτήματα του προγραμματισμού προτεραιότητας
Ακολουθούν τα οφέλη/πλεονεκτήματα της χρήσης της μεθόδου προγραμματισμού κατά προτεραιότητα:
- Εύχρηστη μέθοδος προγραμματισμού.
- Οι διεργασίες εκτελούνται με βάση την προτεραιότητα, επομένως οι διεργασίες υψηλής προτεραιότητας δεν χρειάζεται να περιμένουν πολύ, γεγονός που εξοικονομεί χρόνο.
- Αυτή η μέθοδος παρέχει έναν καλό μηχανισμό όπου η σχετική σημασία κάθε διεργασίας μπορεί να οριστεί με ακρίβεια.
- Κατάλληλο για εφαρμογές με κυμαινόμενες απαιτήσεις χρόνου και πόρων.
Μειονεκτήματα του προγραμματισμού προτεραιότητας
Ακολουθούν τα μειονεκτήματα/μειονεκτήματα του προγραμματισμού κατά προτεραιότητα:
- Εάν το σύστημα τελικά καταρρεύσει, όλες οι διαδικασίες χαμηλής προτεραιότητας χάνονται.
- Εάν οι διεργασίες υψηλής προτεραιότητας απαιτούν πολύ χρόνο CPU, τότε οι διεργασίες χαμηλότερης προτεραιότητας μπορεί να λιμοκτονήσουν και θα αναβληθούν για αόριστο χρονικό διάστημα.
- Αυτός ο αλγόριθμος προγραμματισμού μπορεί να αφήσει ορισμένες διαδικασίες χαμηλής προτεραιότητας να περιμένουν επ' αόριστον.
- Μια διεργασία θα αποκλειστεί όταν είναι έτοιμη να εκτελεστεί, αλλά πρέπει να περιμένει για την CPU επειδή κάποια άλλη διεργασία εκτελείται αυτήν τη στιγμή.
- Εάν μια νέα διεργασία υψηλότερης προτεραιότητας συνεχίσει να έρχεται στην ουρά έτοιμων, τότε η διαδικασία που βρίσκεται σε κατάσταση αναμονής μπορεί να χρειαστεί να περιμένει για μεγάλο χρονικό διάστημα.
