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

Ο Αλγόριθμος Χρονοπρογραμματισμού με Βάση τη Σειρά Άφιξης ή αλλιώς 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

ΣυμπέρασμαΕπεξεργασία

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

Δείτε ΕπίσηςΕπεξεργασία

ΠηγέςΕπεξεργασία

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