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

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

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

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

Στο παράδειγμα που χρησιμοποιήθηκε και προηγουμένως, η διεργασία δ1 φθάνει τη χρονική στιγμή 0 και αρχίζει να εκτελείται. Τη χρονική στιγμή 6 φθάνει η διεργασία δ2, που θα έχει διάρκεια 31 μονάδες. Στη δ1 απομένουν 6 μονάδες για να τελειώσει, λιγότερες από το χρόνο της δ2, οπότε η δ1 συνεχίζει να εκτελείται. Τη χρονική στιγμή 8 όμως φθάνει η διεργασία δ3 με διάρκεια 3, ενώ στην δ1 απομένουν 4 χρονικές μονάδες εκτέλεσης. Έτσι η δ1 διακόπτεται και αρχίζει να εκτελείται η δ3, η οποία ολοκληρώνεται τη στιγμή 11. Τότε υπάρχουν δυο διεργασίες για εκτέλεση: η δ1, στην οποία απομένουν 4 χρονικές μονάδες για να ολοκληρωθεί, και η δ2 η οποία απαιτεί 31 χρονικές μονάδες. Επιλέγεται βέβαια η δ1 και αρχίζει να εκτελείται. Τη χρονική στιγμή 14, και ενώ η δ1 εκτελείται ακόμα, φθάνει στη λίστα έτοιμων διεργασιών η δ4 που απαιτεί 11 χρονικές μονάδες. Αφού στη δ1 απομένει μόνο μια χρονική μονάδα το ΛΣ δεν τη διακόπτει και την αφήνει να ολοκληρωθεί. Όταν τελειώσει, οι υποψήφιες διεργασίες είναι: η δ2 με διάρκεια 31 και η δ4 με διάρκεια 11. Επιλέγεται η δ4 και αφού ολοκληρωθεί εκτελείται και η δ2.

Η δ1 περνά σε αναμονή για 3 χρονικές μονάδες, κατά τις οποίες εκτελείται η δ3 (που δεν περιμένει καθόλου). Η δ2 περιμένει για 20 χρονικές μονάδες και η δ4 για μια. Ο μέσος χρόνος αναμονής είναι (3+20+0+1)/4 = 6. Αυτός είναι καλύτερος και από τον καλύτερο μη διακοπτό αλγόριθμο, τον SJF, που είχε μέσο χρόνο αναμονής 6,25.

Η διεργασία δ1 έχει χρόνο απόκρισης 15, η δ2 51, η δ3 3 και η δ4 12. Έτσι, ο μέσος χρόνος απόκρισης είναι (15+51+3+12)/4 = 20,25, καλύτερος και αυτός από όλους τους μη διακοπτούς αλγορίθμους (αν και η διαφορά του από το μη διακοπτό SJF είναι ελάχιστη). Βέβαια στους υπολογισμούς μας δεν έχουμε λάβει υπόψη την επιβάρυνση που προκαλεί η εκτέλεση του χρονοδρομολογητή.