Process Scheduling Algorithms Examples

This is a one of the rarest examples of all process scheduling algorithm that you can found in Internet.
Digitized from my own Operating System lecture notes actually (before I send them to recycling center).
:)

First you must know why, process scheduling is important. In the past (i.e 1950 or 1960's -ish, there are computer existed already but it is far too slow to be compared with your dear truly Casio 5700), a computer which might be as big as your home is capable of doing one task at the time which we called batch processing which as you might suspect is quite ineffective.

So some sort of computer scientist developed a system which enabled several users/programs runs concurrently on a computer system and each programs takes a slices of available processing time. The distribution of time sharing system gives the illusion to user that (s)he is running multiple program at  the same time.

Without wasting more time, here is a brief example of process scheduling algorithm
---------------------------------------------------------
|Process     |Arrival Time     |Processing Time|
---------------------------------------------------------
|A              |0                      |3                       |
|B              |1                      |6                       |
|C              |4                      |4                       |
|D              |6                      |2                       |
--------------------------------------------------------

(1) Plot the execution time for following algorithms

(i) First Come First Served
(ii) Shortest Job First
(iii) Shortest Remaining Time
(iv) Round Robin (quantum =1)

(i) All are executed as they received in order

-----------------------
|A   |B      |C    |D  |
-----------------------
0    3      9      13  15

(ii) *At time 0, A runs because it is only choice
     *At time 3, B is only process in the queue
     *At time 9, D runs first because D is shorter than C

------------------------
|A   |B      |D  |C    |
------------------------
0   3        9   11     15

(iii) *At time 0, A runs because it is the only choice
      *A runs even though B arrives because A got 2 times left compared to B (6)
      *At time 4, C overtake B because C still has 4 times left compared to B (5)
      *At time 6, C overtake D because C still has 2 times left (D=2)
      *At time 8, D overtakes B because D still has 2 times left compared to B(5)

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

|A   |B |C    |D  |B     |

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

0   3   4     8   10    15

(iv) *Each time slices cannot be more than two (minimum is one)

---------------------------------
|A  |B |A |B  |C  |D  |B  |C  |
---------------------------------
0   2  4  5   7  9    11  13  15

(2) What is average turn around time for 4 algorithms in (1)?

Formula for average turn around time is
[ Time Process Enter Sequences - Time Process Exit Sequences ]/[Number of Processes]
(i)   ( [3-0]+ [9-1]+    [13-4]+ [15-6] )/4 = 7.25
(ii)  ( [3-0]+ [9-1]+    [15-4]+ [11-6] )/4 = 6.75
(iii) ( [3-0]+ [15-1]+  [8-4]+   [10-6] )/4 = 6.25
(iv) ( [5-0]+ [13-1]+  [15-4]+ [11-6] )/4=8.25

(3) What is the wait time for each processes for 4 algorithms in (1)

Formula for wait time is
[ Turnaround Time ]- [ Execution Time ]

(i)   A:[3-3]=0   B:[8-6]=2   C:[9-4]=5    D:[9-2]=7
(ii)  A:[3-3]=0   B:[8-6]=2   C:[11-4]=7  D:[5-2]=3
(iii) A:[3-3]=0   B:[14-6]=8  C:[4-4]=0   D:[4-2]=2
(iv) A:[5-3]=2   B:[12-6]=6  C:[11-4]=7 D:[5-2]=3

(4) What is average throughput for 4 algorithms in (1)?
Same

15 time units / 4 jobs = 3.754 time units / jobs



^_^ Bye bye OS lectures notes. Gonna miss you .... erm not ... well sort of.