Εξυπηρέτηση με βάση τη σειρά άφιξης

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

Ο αντίστοιχος αλγόριθμος χρονοδρομολόγησης ΚΜΕ ονομάζεται αλγόριθμος με βάση τη σειρά άφιξης (First Come First Served - FCFS). Η υλοποίησή του γίνεται πολύ εύκολα· η λίστα έτοιμων διεργασιών λειτουργεί όπως μια ουρά αναμονής.

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

Η επίδοση του αλγορίθμου αυτού αν κριθεί με βάση το χρόνο ανακύκλωσης (turnaround time) είναι χαμηλή, γιατί εξαναγκάζει ακόμα και διεργασίες με πολύ σύντομες εκρήξεις ΚΜΕ να αναμένουν για την εκτέλεση άλλων. Παρόμοιες επιδόσεις πετυχαίνει και με βάση τα υπόλοιπα κριτήρια αξιολόγησης που αναφέρθηκαν στο μάθημα αυτό· η χρησιμοποίηση π.χ. της ΚΜΕ μπορεί να είναι χαμηλή.

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

Στο σχήμα φαίνεται το σχεδιάγραμμα εκτέλεσης των τεσσάρων διεργασιών του παραδείγματος. Οι χρόνοι αναμονής είναι 0 για την πρώτη διεργασία, 12-6=6 για τη δεύτερη, 12+31-8=35 για την τρίτη και 12+31 +3-14=32 για την τέταρτη. Ο μέσος χρόνος αναμονής είναι λοιπόν (0+6+35+32)74 = 18,25. Παρατηρούμε επίσης ότι η διεργασία δ3, η οποία είχε διάρκεια μόνο 3, εξαναγκάστηκε να περιμένει για 35 χρονικές μονάδες για να εκτελεστεί, είχε δηλαδή τεράστια αναμονή σε σχέση με τη διάρκειά της.

Οι χρόνοι απόκρισης (χρόνος αναμονής + χρόνος εκτέλεσης) είναι: 12 για τη δ1, 37 για τη δ2, 38 για τη δ3 και 43 για τη δ4. Έτσι ο μέσος χρόνος απόκρισης είναι (12+37+38+43)74 = 32,5.