[LCP]round-robin

[David Spencer]

Without the description in front of me I'd be guessing too.

A round robin implementation works from a list of jobs.  The processor
looks at each entry on the list in turn and performs action according to
the status of that item.  Having done that, it then jumps to the next
item in the list, returning to the top when it gets to the end (or a
more generic setup would use a circular list but jumping back to the top
of a straight list is a more familiar concept.)

In the case of a pre-emptive multitasking computer system, each process
that is ready to run is activated by the round robin, then at the end of
its timeslice, if it is still running, it is interrupted and the RR
jumps to the next process.  Arrival time and service time will be
related to list stats; the service time will either be the length of the
time slice or the time at which the time slice begins; the arrival time
is presumably the time at which the process is added to the list.  These
stats will be useful in determining how long a process will need to wait
before it is executed, and then how long it is likely to take to
complete although the (average?) length of the active list will need to
be known as well.  For a list 10 items long with a 100ms timeslice
(assuming the round robin overhead is insignificant) the expected
waiting time for any runnable process to be reactivated is 500ms or half
a second.  Users of GUIs expect a response well within 100ms so if the
list is 10 items long the timeslice should be no greater than 10ms (then
the MAXIMUM waiting time is 100ms, with the EXPECTED waiting time 50ms.)

Windows 3x is a co-operative multitasking system* - there is (probably)
still a round robin at the centre of the system but timeslicing is not
forced by interrupting the process but by allowing the process to return
control to the system.  This way it was easy for one process to lock up
the system by simply not returning control; it also made programming
more difficult because you would have to turn loops inside out so that
they would run a short time before returning control to the system.  The
16 bit subsystem within Win32 works the same way but this process
(called Windows on Windows, wow!) is pre-emptively multitasked with the
other processes on Win32, each of which runs within its own closed
system, so the likelyhood of one process stuffing the computer is
greatly reduced.

*Except for DOS boxes - in Win3x these were pre-emptively multitasked
with the Windows GUI and with each other, which is why you could run
multiple DOS applications under Windows.

For an interactive system such as a GUI, short timeslices are better
because the response time is high.  If the timeslices are too long, the
user will perceive the system to be "slow" because they get too long a
response to pressing a button.  The fact that the computer may have
performed trillions of floating point operations between the button
being pressed and displaying the results will not prevent the user
complaining the system is too slow!  On the other hand a batch
processing system is better with longer timeslices as less time is then
spent on the round robin overhead and more on solving the problem in
hand.  Perceived speed is not an issue here because the user submits a
job at one time and is expecting the answer back much later.

Timeslices should not be too short because the round robin overhead
would then become significant and consequently start slowing the
computer down.  In early versions* of Windows 3x, I could setup a few
DOS boxes, crank the timeslicing down to 10ms and watch the screen
redraw itself pixel-by-pixel!  Interesting, for the right sort of mind. 
Response time was of course absolutely ridiculous, measured with a
calendar and it would be often quicker to switch off and do a scandisk
than to wait for the computer to reverse the effect.

*Although pedantically it was not that the code was particularly badly
written but because of the speed of the computers back then.  A similar
effect can be seen today, but the Windows timeslicing can still only be
set down to 10ms and the computer can achieve much more in the time
available.

Dave.


Nicola ONOSE wrote:
> 
>   I know it sounds a little silly, but I received a description of
> a round-robin implementation and it is based on terms
> like "arrival time", "service time".
>  I can guess their meaning, but I am not very sure, so I would
> appreciate some help from anybody.
> 
> Thank you
> 
> Nicola
> 
> _______________________________________________
> This is the Linux C Programming List
> :  http://lists.linux.org.au/listinfo/linuxcprogramming List