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

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

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

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

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

Σκεφτείτε αυτό μετά από τρεις διαδικασίες

Ουρά διαδικασίας	Ώρα έκρηξης
P1	4
P2	3
P3	5

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

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

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

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

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

Βήμα 6) Το P2 έχει χρόνο ριπής 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.
• Ασχολείται με όλες τις διαδικασίες χωρίς καμία προτεραιότητα
• Εάν γνωρίζετε τον συνολικό αριθμό διεργασιών στην ουρά εκτέλεσης, τότε μπορείτε επίσης να υποθέσετε τον χρόνο απόκρισης στη χειρότερη περίπτωση για την ίδια διαδικασία.
• Αυτή η μέθοδος προγραμματισμού δεν εξαρτάται από το χρόνο ριπής. Γι' αυτό είναι εύκολα εφαρμόσιμο στο σύστημα.
• Μόλις εκτελεστεί μια διεργασία για ένα συγκεκριμένο σύνολο της περιόδου, η διεργασία προκρίνεται και μια άλλη διεργασία εκτελείται για τη συγκεκριμένη χρονική περίοδο.
• Επιτρέπει στο λειτουργικό σύστημα να χρησιμοποιεί τη μέθοδο εναλλαγής περιβάλλοντος για την αποθήκευση καταστάσεων προεπιλεγμένων διεργασιών.
• Παρέχει την καλύτερη απόδοση όσον αφορά τον μέσο χρόνο απόκρισης.

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

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

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

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

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

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

Φόρμουλα:

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

Σύνοψη

• Το όνομα αυτού του αλγόριθμου προέρχεται από την αρχή του round-robin, όπου κάθε άτομο παίρνει ίσο μερίδιο από κάτι με τη σειρά.
• Το Round Robin είναι ένας από τους παλαιότερους, πιο δίκαιους και ευκολότερους αλγόριθμους και ευρέως χρησιμοποιούμενες μεθόδους προγραμματισμού στα παραδοσιακά OS.
• Το Round Robin είναι ένας προληπτικός αλγόριθμος
• Το μεγαλύτερο πλεονέκτημα της μεθόδου προγραμματισμού στρογγυλής περιπέτειας είναι ότι εάν γνωρίζετε τον συνολικό αριθμό διεργασιών στην ουρά εκτέλεσης, τότε μπορείτε επίσης να υποθέσετε τον χρόνο απόκρισης στη χειρότερη περίπτωση για την ίδια διαδικασία.
• Αυτή η μέθοδος αφιερώνει περισσότερο χρόνο στην εναλλαγή περιβάλλοντος
• Η καθυστέρηση στη χειρότερη περίπτωση είναι ένας όρος που χρησιμοποιείται για τον μέγιστο χρόνο που απαιτείται για την εκτέλεση όλων των εργασιών.