Αλγόριθμος Χρονοπρογραμματισμού με Βάση τη Μικρότερη Διάρκεια Εκτέλεσης

Ο Αλγόριθμος Χρονοπρογραμματισμού με Βάση τη Μικρότερη Διάρκεια Εκτέλεσης ή αλλιώς SJF(Shortest Job First) είναι ένας αλγόριθμος χρονοπρογραμματισμού της ΚΜΕ(Κεντρικής μονάδας επεξεργαστή) ο οποίος βασίζεται στη διάρκεια του επόμενου ξεσπάσματος μιας διεργασίας.

Περιγραφή

Για την υλοποίηση του αλγορίθμου SJF λαμβάνεται υπόψη η διάρκεια του επόμενου ξεσπάσματος της ΚΜΕ για μια διεργασία, και όχι η συνολική διάρκειά της,και επιλέγεται η διεργασία με τον μικρότερο χρόνο επόμενου ξεσπάσματος ΚΜΕ. Αν δυο διεργασίες έχουν ίδιο χρόνο ξεσπάσματος ΚΜΕ τότε χρησιμοποιείται ο Αλγόριθμος Χρονοπρογραμματισμού με Βάση τη Σειρά Άφιξης για να γίνει η επιλογή μιας διεργασίας. Ο SFJ οδηγεί σε starvation όσο μπαίνουν διεργασίες με μικρότερο χρόνο εκτέλεσης.

Παράδειγμα

Έστω οι διεργασίες P1, P2, P3, P4, οι οποίες καταφτάνουν ταυτόχρονα στην ΚΜΕ και έχουν χρόνους ξεσπάσματος 20 ms, 3 ms, 5 ms και 2 ms αντίστοιχα.

Αν οι παραπάνω διεργασίες εξυπηρετηθούν με τον Αλγόριθμος Χρονοπρογραμματισμού με Βάση τη Μικρότερη Διάρκεια Εκτέλεσης θα έχουμε τους εξής χρόνους αναμονής:

P1: 10 ms

P2: 2 ms

P3: 5 ms

P4: 0 ms

Μέσος χρόνος αναμονής: (10 + 2 + 5 + 0)/4 = 4,25 ms

Για τις ίδιες διεργασίες αν χρησιμοποιούσαμε τον Αλγόριθμο Χρονοπρογραμματισμού με Βάση τη Σειρά Άφιξης θα είχαμε μέσο χρόνο αναμονής 17,75 ms.

Συμπέρασμα

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

Παραλλαγές

Ο Αλγόριθμος Χρονοπρογραμματισμού με Βάση τη Μικρότερη Διάρκεια Εκτέλεσης μπορεί να εφαρμοστεί και με διακοπές.

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

Δείτε Επίσης

• Αλγόριθμος Χρονοπρογραμματισμού με Βάση τη Σειρά Άφιξης (First-Come,First-Served ή FCFS)

• Αλγόριθμος Χρονοπρογραμματισμού με Βάση την Προτεραιότητα (Priority Scheduling)

• Αλγόριθμος Χρονοπρογραμματισμού εκ Περιτροπής (Round-Robin ή RR)

• Αλγόριθμος Χρονοπρογραμματισμού με Πολυεπίπεδες Ουρές (Multilevel Queue Scheduling Algorithm)

Πηγές

• Λειτουργικά Συστήματα, 2η Ελληνική Έκδοση (Silberschatz, Galvin, Gagne) σελ. 225-228, ISBN 978-960-411-692-8.