Process Scheduling Algoithms:
Round Robin:
each process gets a strict amount of time on the CPU
(its quantum is typically 10 to 100 ms)
seems fair
easy to implement
Round Robin is pre-emptive - its specifically designed for time-sharing systems
there is no risk of starvation*
but if the timeslice is too big round robin tends to a FCFS system
if the quantum is too small, RR tends to become
Typically Round Robin has a better average response time than a SJF - Shortest Job First system.
A potential deficiency of Round Robin: processes that are IO-bound* often do not use their full quantum before being interrupted by an IO operation. Once blocked and evicted, they then get moved to the back of the queue, so their spot in the queue is essentially lost to another process. they go 'hungry' for CPU time
so Round Robin as a scheduling algorithm is not really as fair as it might initially seem.
* Starvation / indefinite blocking : can occur when a scheduling system leaves a lower priority job indefinitely
* IO bound Process - the process spends more time frequently interrupted by IO operations, and subject to context switches thus often doesn't use its full quantum of CPU time.
* CPU bound process - spends more time on average being executed in the CPU,
than being interrupted by IO operations.
Youtube videos of scheduling algorithms in action:
SRTF https://www.youtube.com/watch?v=67ZDlvwgSV8SRTF
(Priority Scheduling, a 'pre-emptive verison' of SJF)
Round Robin
https://www.youtube.com/watch?v=GjrxO-PDPdk
Saturday, August 24, 2013
Friday, August 23, 2013
Edsger W. Dijkstra.
...the manuscripts of Edsger W. Dijkstra, 1930–2002
http://www.cs.utexas.edu/users/EWD/
example of pathfinding from macha
Vimeo Animation: https://vimeo.com/10569955
http://www.cs.utexas.edu/users/EWD/
example of pathfinding from macha
Vimeo Animation: https://vimeo.com/10569955
Subscribe to:
Posts (Atom)