Εξυπηρέτηση με βάση τη διάρκεια

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

Ο αλγόριθμος εξυπηρέτησης με βάση τη διάρκεια (Shortest Job First - SJF), κατατάσσει τις διεργασίες κατά αύξουσα σειρά διάρκειας. Πρώτα εκτελείται η συντομότερη διεργασία, μετά αυτή με την αμέσως μεγαλύτερη διάρκεια κ.ο.κ. Τελευταία εκτελείται αυτή με τη μεγαλύτερη διάρκεια.

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

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

Η εκτέλεση των διεργασιών του παραδείγματος με τον αλγόριθμο εξυπηρέτησης με βάση τη διάρκεια φαίνεται στο σχήμα. Η σειρά εκτέλεσης των διεργασιών είναι δ1, δ3, δ4, δ2. Η δ1 επειδή είναι μόνη της πρώτη δεν περιμένει καθόλου, η δ2 περιμένει για (12+3+11)-6 = 20, η δ3 για 12-8 = 4 και η δ4 για (12+3)-14 = 1. Ο μέσος χρόνος αναμονής είναι λοιπόν (0+20+4+1)/4 = 6,25· πολύ μικρότερος από τον αντίστοιχο για την εξυπηρέτηση με βάση τη σειρά άφιξης, και ο μικρότερος δυνατός.

Οι χρόνοι απόκρισης είναι: 12 για τη δ1, 51 για τη δ2, 7 για τη δ3 και 12 για τη δ4. Ο μέσος χρόνος απόκρισης είναι (12+51+7+12)/4 = 20,5, πολύ καλύτερος επίσης από την εξυπηρέτηση με βάση τη σειρά άφιξης.

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