Αλγόριθμος SCAN

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

Περιγραφή

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

Παραλλαγές

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

Παράδειγμα

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

SCAN

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

C- SCAN

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

Δείτε Επίσης

• FCFS
• SSTF
• LOOK

Πηγές

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