Αλγόριθμος Χρονοπρογραμματισμού με βάση τη σειρά άφιξης

Ο Αλγόριθμος Χρονοπρογραμματισμού με Βάση τη Σειρά Άφιξης ή αλλιώς FCFS (First-Come,First-Served) είναι ένας αλγόριθμος χρονοπρογραμματισμού της ΚΜΕ(Κεντρικής μονάδας επεξεργαστή) και αποτελεί τον απλούστερο τρόπο χρονοπρογραμματισμού της ΚΜΕ.

Περιγραφή

Για την υλοποίηση του αλγορίθμου FCFS είναι αναγκαία μια ουρά FIFO οπού εκεί θα μπαίνουν οι διεργασίες που είναι έτοιμες προς εκτέλεση. Μόλις μια διεργασία μπει στην ουρά έτοιμων διεργασιών το PCB της θα μπει στο τέλος της ουράς αυτής απο όπου η ΚΜΕ θα αναλαμβάνει τις προς εκτέλεση διεργασίες.

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

Παράδειγμα

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

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

P1: 0 ms

P2: 20 ms

P3: 22 ms

Μέσος χρόνος αναμονής: (0 + 20 + 22)/3 = 42/3 = 14 ms

Αν όμως οι παραπάνω διεργασίες είχαν έρθει με την σειρά P3,P2,P1 οι χρόνοι αναμονής θα ήταν οι εξής:

P3: 0 ms

P2: 2 ms

P1: 4 ms

Μέσος χρόνος αναμονής: (0 + 2 + 4)/3 = 6/3 = 2 ms

Συμπέρασμα

Ο χρόνος αναμονής για τον Αλγόριθμος Χρονοπρογραμματισμού με Βάση τη Σειρά Άφιξης είναι συχνά μεγάλος.

Δείτε Επίσης

• Αλγόριθμος Χρονοπρογραμματισμού με Βάση τη Μικρότερη Διάρκεια Εκτέλεσης(Shortest Job First ή SJF)

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

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

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

Πηγές

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