Round Robin

[GameTheory]

Καλησπερα σε ολους. Θα μπορουσε καποιος να με βοηθησει να ( να μου εξηγησει)  την μεθοδο Round Robin? Τις αλλες τις καταλαβα, απλα με τα κβαντα το εχασα εντελως. Ευχαριστω πολυ ,εκ των προτερον.

[Kostas93]

λοιπόν, σκέψου ότι οι διεργασίες μπαίνουν σε μια fifo.
Ορίζεις ένα κβάντο χρόνου, έστω x.

Με τη μέθοδο round robin θα ξεκινήσει να εκτελείται η πρώτη διεργασια που βρίσκεται στην fifo, για χρόνο ίσο με x, μετά αυτή θα πάει στο τέλος της fifo ((εάν δεν ολοκληρωθεί)-εαν ολοκληρωθεί θα βγει γενικά απο την fifo) και η επόμενη διεργασία θα ξεκινήσει να εκτελείται για χρόνο ίσο με x. Και συνεχίζει με τον ίδιο τρόπο. Θεωρείται πολύ δίκαιος αλγόριθμος, αλλά έχει και προβλήματα.

Εαν το κβάντο χρόνου (x) είναι μεγάλο, τότε μπορεί να δημιουργηθούν προβλήματα αλληλεπιδρασης με καποια εφαρμογή, πχ να παρατηρείς lag.
Εάν το κβάντο χρόνου (x) είναι μικρό, τότε θα έχουμε πολύ γρήγορες εναλλαγές μεταξύ των διεργασιών, αυτό μπορεί να δημιουργήσει πρόβλημα πχ στη cache όπου θα περνάνε συνέχεια νέα δεδομένα, μεγάλη χρηση cpu, κ.α.

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

Διεργασία 1 ---> Διεργασία 2 ---> Διεργασία 3
---Χρόνος 0-x---  ---Χρόνος x-2x--- ---Χρόνος 2x-3x--

 

Μετά ξαναπάμε στη σειρά αφού η 1 μετά απο x μπήκε στη θεση 3, και μετά απο 3x έφτασε πάλι στη πρώτη θέση της fifo
Διεργασία 1 ---> Διεργασία 2 ---> Διεργασία 3
---Χρόνος 3x-4x---  ---Χρόνος 4x-5x--- ---Χρόνος 5x-6x--

Έστω τώρα ότι τελείωσε η διεργασία 3, η fifo θα γίνει
Διεργασία 1 ---> Διεργασία 2
---Χρόνος 6x-7x-- --Χρόνος 7x-8x

Διεργασία 1 ---> Διεργασία 2
---Χρόνος 8x-9x-- --Χρόνος 9x-10x

και παει λέγοντας.
 Δε  μπορώ να κανω καλό παράδειγμα γιατί θα μου πάρει ώρα να το γράψω.

*εάν μια διεργασία ολοκληρωθεί πριν το τέλος του κβάνου χρόνου, τότε βγαίνει απο την fifo και ο χρονοδρομολογητής παίρνει την επόμενη διεργασία απο την fifo.
**φυσικά στη fifo συνεχώς προσθέτονται διεργασίες.

[GameTheory]

λοιπόν, σκέψου ότι οι διεργασίες μπαίνουν σε μια fifo.

Ορίζεις ένα κβάντο χρόνου, έστω x.

Με τη μέθοδο round robin θα ξεκινήσει να εκτελείται η πρώτη διεργασια που βρίσκεται στην fifo, για χρόνο ίσο με x, μετά αυτή θα πάει στο τέλος της fifo ((εάν δεν ολοκληρωθεί)-εαν ολοκληρωθεί θα βγει γενικά απο την fifo) και η επόμενη διεργασία θα ξεκινήσει να εκτελείται για χρόνο ίσο με x. Και συνεχίζει με τον ίδιο τρόπο. Θεωρείται πολύ δίκαιος αλγόριθμος, αλλά έχει και προβλήματα.

Εστω οτι εχουμε 5 διεργασιες. Και οριζουμε κβαντο χρονου  2.

-----------------------------------------------------------------------------------------------------------------

! Pr.!! Χρ.Αφ!! Χρ.Εκτ!! Χρ.Αν!! Χρ.Διεκ.!

! Α  !!    0          8                                    

! Β  !!    2          6                                    

! Γ  !!    4          3                                    

! Δ  !!    5          2                                    

! Ε  !!    7          1                                    

 

Το γραφημα GANT θα ειναι ετσι ?

^{0   1     2     3     4     5     6    7   8     9    10   11   12    13  14   15   16   17    18     19   20}

!Α ! Α ! Β! Β ! Γ ! Γ !Δ !Δ ! Ε ! Α! Α !Β ! Β ! Γ ! Α ! Α ! Β !  Β! Α  ! Α !

!   !    !    !    !    !    !   !   !    !    !    !    !    !    !    !    !    !     !     !    !

 

Ευχαριστω πολυ

[Kostas93]

με τη προυπόθεση ότι αυτό που έρχεται θα μπει πριν απο αυτό που υπάρχει ήδη, τότε φαίνεται οκ.

*εννοώ ότι πχ στο χρόνο άφιξης 2, στην fifo υπάρχει η Α και έρχεται ο Β, αν ο Β εκτελεστεί πριν τον Α, τότε ναι. Δηλαδή στη fifo να μπει πρώτα η νέα διεργασία και μετά να πάει στο τέλος η παλιά διεργασία.

Δε ξέρω αν έχετε κάνει κάποια παραδοχή πάνω σε αυτό, και δε θυμάμαι αν είναι fixed, καθώς έχω χρόνια που πέρασα το αντίστοιχο μάθημα.

[sundance_kid]

 

Η παραπάνω εικόνα απο το wikipedia, πιστεύω είναι η περιγραφικότερη για την κατανόηση RR αλγορίθμου.