operating-systemscheduled-tasksmulticoresupercomputers

When is SJF worse than FCFS?

In operating systems of supercomputers, which handles a big quantity of tasks at the same time, is there any situation when SJF policy is taking longer than FCFS policy, speaking of waiting time metric?

It can be assumed that more than one core are present in the system.

Solution

  • First I thought that it is not possible, then I took some time and finally arrived at this result:

    Yes it can be.

    Suppose that ready queue is filled with processes with equal burst times(all = x):

    Process    Burst time
 P1          x
 P2          x
 P3          x
 P4          x
 .           .
 .           .
 .           .
 Pn          x

    Now in this case what FCFS would do, the process that would come first will be allocated the CPU and then the next process which comes first will be allocated the CPU and so on without wasting any time.

    But what SJF will do is :it will first find the job with the shortest burst time from the available jobs in the ready queue which in this case is wastage of time as all have equal burst times and SJF would end up traversing the ready queue without any fruitful result.