Question

1 - [30 pts] Scheduling Algorithms Comparison Assume that we have 5 independent and aperiodic tasks (T1, ... , Ts) and they arrive to the system at times indicated below. Each task will run for the amount of execution time listed and is assigned a priority ranging from 0 (highest) to 10 (lowest), i.e. lower value means higher priority. There are no other tasks scheduled to arrive to the system until T1, ... , Ts complete. Task Arrival Time Execution Time Priority T1 0 8 10 T2 1 4 2 T3 2 1 10 T4 3 2 1 T5 4 2 5 a) [20 pts] Show the execution of these tasks using the following scheduling algorithms: i. FCFS ü. SJF (if tasks have the same execution time, apply FCFS as a tie-break rule) iii. SRTF (preemptive SJF, if tasks have the same remaining execution time, apply FCFS as a tie-break rule) iv. Preemptive priority (i.e. at any time, choose the task with the highest priority. If priorities are equal, apply FCFS as a tie-break rule) b) [4 pts] What is the turnaround time of each task for each algorithm from part a)? c) [4 pts] What is the waiting time of each task for each algorithm from part a)? d) [2 pts] Which scheduling algorithm results in the lowest average waiting time across 5 tasks? Does this align with the theoretical information we saw in class? Note: You can ignore context switch overhead.

Answer 1

a)

i) FCFS

T1

T2

T3

T4

T5

0--------------------8--------------------12-------------------13---------------------15------------------17

ii) SJF

T1

T3

T4

T5

T2

0--------------------8--------------------9-------------------11---------------------13---------------------17

iii)SRTF

T1

T2

T3

T4

T5

T2

T1

0------------- 1---------------2---------------3---------------5--------------7---------------10------------17

iv) Premptive Priority

T1

T3

T5

T2

T4

0--------------------8--------------------9-------------------11---------------------15---------------------17

b)Turnaround time

FCFS

T1 = 8-0 = 8

T2 = 12-1 = 11

T3 = 13-2 = 11

T4 = 15-3 = 12

T5 = 17-4 = 13

SJF

T1 = 8-0 = 8

T2 = 17-1 = 16

T3 = 9-2 = 7

T4 = 11-3 = 8

T5 = 13-4 = 9

SRTF

T1 = 17-0 = 17

T2 = 10-1 = 9

T3 = 3-2 = 1

T4 = 5-3 = 2

T5 = 7-4 = 3

Premptive Priority

T1 = 8-0 = 8

T2 = 15-1 = 14

T3 = 9-2 = 7

T4 = 17-3 = 14

T5 = 11-4 = 7

c) Waiting Time

FCFS

T1 = 0-0 = 0

T2 = 8-1 = 7

T3 = 12-2 = 10

T4 = 13-3 = 10

T5 = 15-4 = 11

SJF

T1 = 0-0 = 0

T2 = 13-1 = 12

T3 = 8-2 = 6

T4 = 9-3 = 6

T5 = 11-4 = 7

SRTF

T1 = 10-0 = 10

T2 = 7-1 = 6

T3 = 2-2 = 0

T4 = 3-3 = 0

T5 = 5-4 = 1

Premptive Priority

T1 = 0-0 = 0

T2 = 11-1 = 10

T3 = 8-2 = 6

T4 = 15-3 = 12

T5 = 9-4 = 5

d)

SRTF has the lowest average time. Yes, it is theoretically true.

Do ask if any doubt. Please up-vote.