So one of the basic scheduling algorithm's is what is known as fi, FIFO, or
first in first out.
This is also known as FCFS or first come first serve.
So in this algorithm you maintain the tasks in a queue,
in the order in which the tasks arrive.
So tasks that arrived earlier are ahead in the queue.
Tasks that arrived later are later on in the queue.
Whenever a processor is free, you de-queue the task at the head of the queue and
you schedule it on the processor.
So for instance, at 0 when Task 1 arrives, place it in the queue.
It's the only task right now and so it executes until time inter, time time 6.
At the point Task 2 arrives, it's placed in the queue, but then Task 1
is still executing on the processor so Task 1 is allowed to complete.
At time 8 the Task 3 arrives and it's added to the queue but after Task 2.
At time 10 when Task 1 finishes, the head of the queue is Task 2, so
that's dequeued and it's scheduled on the processor.
It runs until completion, which happens at time 15, at which time, once again,
the header of the queue,
which is Task 3 now, is dequeued as is scheduled on the processor.
Task 3 finishes at time 18.
So Task 1 finished at time 10.
Task 2, which arrived second, finished at time 15.
Task 3, which arrive, which arrived last, finished at time 15.
This is the FIFO algorithm and even though, we are discussing it for
a single processor now you're here, FIFO is in fact used by a variety of different
cloud computing schedulers, including the Hadoop scheduler.
So how about the performance of FIFO or FCFS?
Well the average completion time, which is really what we care about,
we want the completion time to be as small as possible may be kind of high for FIFO.
For instance, for example, the average completion time can be calculated by
adding the completion times for the three tasks and then divided, dividing them by
3, so that's 10 plus 15 plus 18 divided by 3, or 43 by 3, or 14.33 time units.
This is not, this is on the higher side, I'm telling you.
But, you know, can we do better than 14.33?
What is another scheduling algorithm that is better, that does better than 14.33?
Well that better scheduling algorithm is known as shortest task first.