Αλγόριθμος SCAN

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

Περιγραφή

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

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

Παραλλαγές

Μια παραλλαγή του αλγόριθμου SCAN είναι ο αλγόριθμος C- SCAN όπου το C προέρχεται από την αγγλική λέξη circular (κυκλικός).

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

Παράδειγμα

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

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

SCAN

Ο αλγόριθμος SCAN θα εξυπηρετήσει τις παραπάνω αιτήσεις με την εξής σειρά:
30 --> 53 --> 76 --> 88 --> 199--> 11 --> 5 --> 2

C- SCAN

Ο αλγόριθμος C-scan θα εξυπηρετήσει τις παραπάνω αιτήσεις με την εξής σειρά:
30 --> 53 --> 76 --> 88 --> 199--> 0-> 2 --> 5 --> 11

Δείτε Επίσης

• FCFS
• SSTF
• LOOK

Πηγές

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