Αλγόριθμος SCAN

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

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

Περιγραφή[Επεξεργασία | επεξεργασία κώδικα]

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

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

Παραλλαγές[Επεξεργασία | επεξεργασία κώδικα]

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

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

Παράδειγμα[Επεξεργασία | επεξεργασία κώδικα]

Έστω σκληρός δίσκος με 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

Δείτε Επίσης[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. Λειτουργικά Συστήματα, 2η Ελληνική Έκδοση (Silberschatz, Galvin, Gagne), σελ. 606-607.

Πηγές[Επεξεργασία | επεξεργασία κώδικα]

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