Αλγόριθμος Προγραμματισμού Round Robin με Παράδειγμα

Τι είναι ο Προγραμματισμός Round-Robin;

Το όνομα αυτού του αλγόριθμου προέρχεται από την αρχή του round-robin, όπου κάθε άτομο παίρνει ίσο μερίδιο από κάτι με τη σειρά. Είναι ο παλαιότερος, απλούστερος αλγόριθμος προγραμματισμού, ο οποίος χρησιμοποιείται κυρίως για πολλαπλές εργασίες.

Στον χρονοπρογραμματισμό Round-robin, κάθε έτοιμη εργασία εκτελείται μόνο σειρά προς σειρά σε μια κυκλική ουρά για ένα περιορισμένο χρονικό διάστημα. Αυτός ο αλγόριθμος προσφέρει επίσης εκτέλεση διεργασιών χωρίς διακοπή λειτουργίας.

Χαρακτηριστικά Προγραμματισμού Round-Robin

Ακολουθούν τα σημαντικά χαρακτηριστικά του Προγραμματισμού Round-Robin:

• Ο κυκλικός αλγόριθμος (round robin) είναι ένας προληπτικός αλγόριθμος.
• Η CPU μετατοπίζεται στην επόμενη διεργασία μετά από ένα καθορισμένο χρονικό διάστημα, το οποίο ονομάζεται κβάντο χρόνου/χρονικό κομμάτι.
• Η διεργασία που έχει προεπιλεγεί προστίθεται στο τέλος της ουράς.
• Το Round Robin είναι ένα υβριδικό μοντέλο που λειτουργεί με χρονισμό.
• Το χρονικό διάστημα θα πρέπει να είναι το ελάχιστο, το οποίο αντιστοιχεί σε μια συγκεκριμένη εργασία που πρέπει να διεκπεραιωθεί. Ωστόσο, ενδέχεται να διαφέρει από λειτουργικό σύστημα σε λειτουργικό σύστημα.
• Είναι ένας αλγόριθμος πραγματικού χρόνου που ανταποκρίνεται στο συμβάν εντός συγκεκριμένου χρονικού ορίου.
• Ο κυκλικός αλγόριθμος (round robin) είναι ένας από τους παλαιότερους, πιο δίκαιους και ευκολότερους αλγόριθμους.
• Είναι μια ευρέως χρησιμοποιούμενη μέθοδος χρονοπρογραμματισμού σε παραδοσιακά λειτουργικά συστήματα.

Παράδειγμα Προγραμματισμού Round-robin

Σκεφτείτε τις ακόλουθες τρεις διαδικασίες:

Βήμα 1) Η εκτέλεση ξεκινά με τη διαδικασία P1, η οποία έχει χρόνο ριπής 4. Εδώ, κάθε διεργασία εκτελείται για 2 δευτερόλεπτα. Οι P2 και P3 βρίσκονται ακόμα στην ουρά αναμονής.

Βήμα 2) Τη χρονική στιγμή = 2, το P1 προστίθεται στο τέλος της ουράς και το P2 ξεκινά την εκτέλεση.

Βήμα 3) Τη χρονική στιγμή = 4, το P2 προεπιλέγεται και προστίθεται στο τέλος της ουράς. Το P3 ξεκινά την εκτέλεση.

Βήμα 4) Τη χρονική στιγμή = 6, το P3 προεπιλέγεται και προστίθεται στο τέλος της ουράς. Το P1 ξεκινά την εκτέλεση.

Βήμα 5) Τη χρονική στιγμή = 8, το P1 έχει χρόνο burst 4. Έχει ολοκληρώσει την εκτέλεση. Το P2 ξεκινά την εκτέλεση.

Βήμα 6) Το P2 έχει χρόνο burst 3. Έχει ήδη εκτελεστεί για 2 διαστήματα. Τη χρονική στιγμή = 9, το P2 ολοκληρώνει την εκτέλεση. Στη συνέχεια, το P3 ξεκινά την εκτέλεση μέχρι να ολοκληρωθεί.

Βήμα 7) Ας υπολογίσουμε τον μέσο χρόνο αναμονής για το παραπάνω παράδειγμα.

Wait time
P1 = 0 + 4 = 4
P2 = 2 + 4 = 6
P3 = 4 + 3 = 7

Πλεονεκτήματα του προγραμματισμού Round-robin

Ακολουθούν τα πλεονεκτήματα/οφέλη της μεθόδου προγραμματισμού Round-robin:

• Δεν αντιμετωπίζει τα ζητήματα της λιμοκτονίας ή του φαινομένου της νηοπομπής.
• Όλες οι εργασίες λαμβάνουν μια δίκαιη κατανομή της CPU.
• Ασχολείται με όλες τις διαδικασίες χωρίς καμία προτεραιότητα.
• Εάν γνωρίζετε τον συνολικό αριθμό διεργασιών στην ουρά εκτέλεσης, τότε μπορείτε επίσης να υποθέσετε τον χρόνο απόκρισης στη χειρότερη περίπτωση για την ίδια διαδικασία.
• Αυτή η μέθοδος προγραμματισμού δεν εξαρτάται από τον χρόνο burst. Γι' αυτό είναι εύκολα εφαρμόσιμη στο σύστημα.
• Μόλις εκτελεστεί μια διεργασία για ένα συγκεκριμένο σύνολο της περιόδου, η διεργασία προκρίνεται και μια άλλη διεργασία εκτελείται για τη συγκεκριμένη χρονική περίοδο.
• Επιτρέπει στο λειτουργικό σύστημα να χρησιμοποιεί τη μέθοδο εναλλαγής περιβάλλοντος για την αποθήκευση καταστάσεων προκαθορισμένων διεργασιών.
• Παρέχει την καλύτερη απόδοση όσον αφορά τον μέσο χρόνο απόκρισης.

Μειονεκτήματα του Round-robin Προγραμματισμού

Ακολουθούν τα μειονεκτήματα/μειονεκτήματα της χρήσης του προγραμματισμού Round-robin:

• Εάν ο χρόνος τεμαχισμού του λειτουργικού συστήματος είναι χαμηλός, η έξοδος του επεξεργαστή θα μειωθεί.
• Αυτή η μέθοδος αφιερώνει περισσότερο χρόνο στην εναλλαγή συμφραζομένων.
• Η απόδοσή του εξαρτάται σε μεγάλο βαθμό από το κβαντικό του χρόνου.
• Δεν μπορούν να τεθούν προτεραιότητες για τις διαδικασίες.
• Ο χρονοπρογραμματισμός με κυκλική μέθοδο (round-robin) δεν δίνει ιδιαίτερη προτεραιότητα σε πιο σημαντικές εργασίες.
• Μειώνει την κατανόηση.
• Ένα χαμηλότερο κβάντο χρόνου έχει ως αποτέλεσμα υψηλότερο overhead εναλλαγής περιβάλλοντος στο σύστημα.
• Η εύρεση του σωστού κβάντου χρόνου είναι αρκετά δύσκολη υπόθεση σε αυτό το σύστημα.

Χειρότερη λανθάνουσα περίπτωση

Αυτός ο όρος χρησιμοποιείται για τον μέγιστο χρόνο που απαιτείται για την εκτέλεση όλων των εργασιών.

• dt = Υποδηλώνει τον χρόνο ανίχνευσης όταν μια εργασία εισάγεται στη λίστα
• st = Υποδηλώνει τον χρόνο εναλλαγής από τη μία εργασία στην άλλη
• et = Δηλώνει τον χρόνο εκτέλεσης της εργασίας

Φόρμουλα:

Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti  + eti) N} + tISR
tISR = sum of all execution times

Συχνές Ερωτήσεις