Round Robin Scheduling Question?

This is a discussion on Round Robin Scheduling Question? within the Tech Board forums, part of the Community Boards category; I'm having a bit of trouble understanding how average wait time is calculated with round robin. Using the example below ...

  1. #1
    Registered User
    Join Date
    Aug 2010
    Posts
    11

    Round Robin Scheduling Question?

    I'm having a bit of trouble understanding how average wait time is calculated with round robin.

    Using the example below

    http://i54.tinypic.com/2rhrd49.png

    I simply do not know how the wait times of P1 =16 + 12 + 8 + 4 = 40?

    What is the formula?

    This is for Operating Systems concepts.

  2. #2
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    Process 1(P1) runs for 4 slices, then execution is taken away for 16(+16), then it runs for 4 more, after which execution is taken away for 8(+8), itruns, execution is taken away... you get the pattern.

  3. #3
    Registered User
    Join Date
    Aug 2010
    Posts
    11
    Herm.. Pardon my slowness but i'm still not able to visualize or see what exactly is happening.
    Care to elaborate a bit more with examples?

  4. #4
    Registered User
    Join Date
    Aug 2010
    Posts
    11
    Iv'e found many examples on the web, who also do not explain how these numbers were obtained.

  5. #5
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    It's just the sum of all the time slices given to other processes. For P1, it would be the sum of all the slices given to P2, P3, P4, and P5. For Pn, it would be the sum of time slices given to all the processes except process n itself.

    Scheduling Algorithms - OSDev Wiki

  6. #6
    Registered User
    Join Date
    Sep 2010
    Posts
    2

    count

    Look at the picture and count.
    When process P1 is waiting the other processes are running. Other processes are running
    in times :
    from 4 to 20 = 16
    from 24 to 36 = 12
    from 40 to 48 = 8
    from 52 to 56 = 4
    The total waiting time of process P1 is the sum of waiting periods 16 + 12 + 8 + 4 = 40

    Analogically count waiting times for other processes.

  7. #7
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,248
    Each process is given a division of time. The divisions are:

    P1 gets 20
    P2 gets 12
    P3 gets 8
    P4 gets 16
    P5 gets 4

    These processes are scheduled around and around in the same order. So every 20+12+8+16+4 time units, each process has executed once. Suppose you wanted to know the time that P1 was NOT executing. That would be the total time of each cycle (20+12+8+16+4) minus the time that P1 WAS executing (20), which is 16+12+8+4.

    The average wait time of any process is the weighted average of the wait times of each process, since each process executed for a different amount of time.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    Registered User
    Join Date
    Aug 2010
    Posts
    11
    "Suppose you wanted to know the time that P1 was NOT executing. "

    I see how that works for P1.. but P2 would be 60-12 48. The example says P2 is 32.

    "Look at the picture and count." I guess its that simple!

  9. #9
    Registered User
    Join Date
    Aug 2010
    Posts
    11
    If anyone has good examples I can use to practice i would appreciate it.

    What happens if the process runtime is less than the time quantum? Does the next process run immediately or wait until the time quantum slot is up?

  10. #10
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,074
    Quote Originally Posted by jeffc1 View Post
    "Suppose you wanted to know the time that P1 was NOT executing. "

    I see how that works for P1.. but P2 would be 60-12 48. The example says P2 is 32.

    "Look at the picture and count." I guess its that simple!
    The reason it's 32 and not 48 is because P2 completes before the 60 intervals being depicted. P2 completes at 44 intervals.

    44 - 12 = 32

    What the image says is correct about all wait times. Let me draw you a more verbose set of images for your example to help you see it.
    Attached Images Attached Images  
    Last edited by SlyMaelstrom; 10-08-2010 at 04:17 PM.
    Sent from my iPad®

  11. #11
    Registered User
    Join Date
    Aug 2010
    Posts
    11
    Thanks < I appreciate the time you guys took to help me out. Its one of those things that are so simple, certain texts dont even bother to explain, yet can mean the difference between getting the answer right or complexly wrong.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A question about a question
    By hausburn in forum C++ Programming
    Replies: 3
    Last Post: 04-25-2010, 05:24 AM
  2. SDL buffer channels question
    By TriKri in forum Game Programming
    Replies: 3
    Last Post: 12-09-2009, 04:52 PM
  3. Newbie question, C #
    By mate222 in forum C# Programming
    Replies: 4
    Last Post: 12-01-2009, 05:24 AM
  4. Scheduling
    By Jules in forum Tech Board
    Replies: 4
    Last Post: 01-18-2004, 12:47 PM
  5. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM

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