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

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

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