Αλγόριθμος Προγραμματισμού Προτεραιότητας: Προληπτικός, Μη Προληπτικός ΠΑΡΑΔΕΙΓΜΑ

Τι είναι ο Προγραμματισμός Προτεραιότητας;

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

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

Τύποι Προγραμματισμού Προτεραιότητας

Ο προγραμματισμός προτεραιότητας χωρίζεται σε δύο βασικούς τύπους:

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

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

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

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

Χαρακτηριστικά Προγραμματισμού Προτεραιότητας

Ένας αλγόριθμος CPU που προγραμματίζει τις διαδικασίες με βάση την προτεραιότητα.
Χρησιμοποιήθηκε σε Operaσυστήματα για την εκτέλεση διαδικασιών παρτίδας.
Εάν δύο εργασίες με την ίδια προτεραιότητα είναι ΕΤΟΙΜΕΣ, λειτουργεί σε α ΠΡΩΤΟΣ ΕΡΧΕΤΑΙ ΠΡΩΤΟΣ ΕΞΥΠΗΡΕΤΕΙΤΑΙ βάση.
Στον προγραμματισμό προτεραιότητας, εκχωρείται ένας αριθμός σε κάθε διεργασία που υποδεικνύει το επίπεδο προτεραιότητάς της.
Όσο χαμηλότερος είναι ο αριθμός, μεγαλύτερη είναι η προτεραιότητα.
Σε αυτόν τον τύπο αλγόριθμου προγραμματισμού, εάν φτάσει μια νεότερη διεργασία, η οποία έχει υψηλότερη προτεραιότητα από την τρέχουσα διεργασία, τότε η τρέχουσα διεργασία προκαταλαμβάνεται.

Παράδειγμα Προγραμματισμού Προτεραιότητας

Εξετάστε το ενδεχόμενο να ακολουθήσετε πέντε διαδικασίες P1 έως P5. Κάθε διαδικασία έχει τη μοναδική της προτεραιότητα, τον χρόνο ριπής και την ώρα άφιξης.

Διαδικασία	Προτεραιότητα	Ώρα έκρηξης	Ωρα άφιξης
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 σε έτοιμη ουρά. Οι Ρ2 και Ρ5 έχουν ίση προτεραιότητα. Η ώρα άφιξης του 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, το P5 έχει ολοκληρώσει την εκτέλεση και δεν έχει απομείνει καμία διαδικασία.

Βήμα 18) Ας υπολογίσουμε τον μέσο χρόνο αναμονής για το παραπάνω παράδειγμα.

Χρόνος αναμονής = ώρα έναρξης – ώρα άφιξης + χρόνος αναμονής για την επόμενη ριπή

P1 = o - o = o
P2 =4 - o + 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 επειδή κάποια άλλη διεργασία εκτελείται αυτήν τη στιγμή.
Εάν μια νέα διεργασία υψηλότερης προτεραιότητας συνεχίσει να έρχεται στην ουρά έτοιμων, τότε η διαδικασία που βρίσκεται σε κατάσταση αναμονής μπορεί να χρειαστεί να περιμένει για μεγάλο χρονικό διάστημα.

Περίληψη

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