Αλγόριθμος SSTF

Ο αλγόριθμος SSTF είναι ένας αλγόριθμος χρονοπρογραμματισμού ο οποίος έχει ως καθήκον να επιλέγει με ποια σειρά θα εξυπηρετηθούν οι αιτήσεις προς ένα σκληρό δίσκο που αφορούν εγγραφή και ανάγνωση σε αυτόν.

Περιγραφή

Το όνομά του αλγορίθμου SSTF προέρχεται από τα αρχικά των λέξεων Shortest Seek Time First και η αρχή λειτουργίας του είναι ιδιαίτερα εύκολη. Ο SSTF εξυπηρετεί πρώτα την αίτηση που βρίσκεται πιο κοντά στην κεφαλή του δίσκου την δεδομένη χρονική στιγμή μέχρις ότου να εξυπηρετηθούν όλες οι αιτήσεις. Η επιλογή του αιτήματος γίνεται με βάση τον χρόνο αναζήτησης, δηλαδή το πόσους κυλίνδρους (ίχνη) πρέπει να διανύσει η κεφαλή.

Παράδειγμα

Έστω σκληρός δίσκος με 200 ίχνη ο οποίος έχει μια δεδομένη στιγμή τις παρακάτω αιτήσεις: ίχνος 11, ίχνος 5, ίχνος 53, ίχνος 88, ίχνος 76, ίχνος 2.

Έστω ότι η κεφαλή την δεδομένη στιγμή είναι στο ίχνος 30.

SSTF

30 -- > 11 -- > 5 -- > 2 -- > 53 -- > 76 -- > 88

Απόδοση

Ο αλγόριθμος SSTF είναι σημαντικά καλύτερος σε σχέση με τον FCFS αφού ο χρόνος αναζήτησης συχνά μειώνεται και ως το 1/3 του χρόνου που χρειάζεται ο FCFS.

Σημαντικό όμως μειονέκτημα είναι ότι μπορεί να προκληθούν φαινόμενα λιμοκτονίας όπου μια αίτηση δεν θα εξυπηρετούνταν θεωρητικά ποτέ(πρακτικά μεγάλος χρόνος αναμονής) αφού θεωρητικά μπορεί να καταφθάνουν αιτήσεις προς τον δίσκο που είναι πιο κοντά στην κεφαλή τόσο γρήγορα όσο και αυτές εξυπηρετούνται.

Δείτε Επίσης

• FCFS
• SCAN
• LOOK

Πηγές

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