Search This Blog

Saturday, August 24, 2013

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

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