Εξυπηρέτηση με βάση την προτεραιότητα

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

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

Ας δούμε πώς εκφράζονται οι τρεις προηγούμενοι αλγόριθμοι με βάση την προτεραιότητα:

- Στην εξυπηρέτηση με βάση τη σειρά άφιξης, όλες οι διεργασίες έχουν την ίδια προτεραιότητα, π.χ. 1. Έτσι κάθε φορά επιλέγεται για εκτέλεση η παλαιότερη.

- Στην εξυπηρέτηση με βάση τη διάρκεια, θέλουμε να εκτελείται πρώτη, να έχει δηλαδή τη μεγαλύτερη προτεραιότητα, η διεργασία με τη μικρότερη έκρηξη ΚΜΕ. Πρέπει δηλαδή η προτεραιότητα να είναι μια ποσότητα που μεγαλώνει όταν η έκρηξη ΚΜΕ μικραίνει. Η ποσότητα 1/(έκρηξη ΚΜΕ) έχει αυτή την ιδιότητα, αφού είναι αντιστρόφως ανάλογη της έκρηξης ΚΜΕ και επιλέγεται για να παραστήσει την προτεραιότητα.

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

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

Ένα πολύ ουσιαστικό πρόβλημα σε ορισμένους αλγορίθμους χρονοδρομολόγησης είναι ότι κάποια διεργασία με αρκετά μικρή προτεραιότητα μπορεί να αναμένει για την εκτέλεσή της επ' αόριστο. Κυρίως όταν οι προτεραιότητες είναι στατικές (όπως στην εξυπηρέτηση με βάση τη διάρκεια), σε ένα υπερφορτωμένο σύστημα, μια διεργασία με χαμηλή προτεραιότητα μπορεί πρακτικά να είναι αποκλεισμένη από την ΚΜΕ γιατί συνεχώς την υπερπηδούν άλλες, υψηλότερης προτεραιότητας.

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