0:00

[MUSIC]

Â So in this next series of lectures we're going to see the important topic of

Â scheduling.

Â In particular, today we're going to see single-processor scheduling.

Â But let's start from a, a higher level.

Â So why do you need scheduling at all?

Â Well, many cloud computing system, you have multiple tasks to schedule.

Â For instance, if we just consider your laptop or workstation or even your mobile

Â device, there are multiple processes that are running on that device.

Â On your laptop, you know, you have your browser running,

Â your your editor running you, you maybe you have an IDE running.

Â And essentially the operating system needs to

Â schedule these processes across the limited resources that it has.

Â Primarily the main resource is the processor or the CPU and

Â if you have a single core OS or

Â a single core machine, then you have a particular series of scheduling problems.

Â And of course you might have a multicore machine where you might be able to

Â schedule multiple processes simultaneously.

Â But once again, typically the number of processes

Â is much more than the number of processors that you have,

Â the number of CPU that you have, and so scheduling here becomes a challenge.

Â In a cloud computing cluster, you might have a Hadoop job running.

Â And that Hadoop job has multiple tasks,

Â so the cluster needs to decide where to schedule each task of the Hadoop job.

Â You might have multiple Hadoop jobs, each with their own tasks.

Â And that they might be competing for resources and

Â now the cloud scheduler needs to decide

Â where to schedule these different tasks of these different Hadoop jobs.

Â 1:39

You have a large number of tasks and there are limited resources that these tasks

Â absolutely need so each task typically needs some amount of processing capacity,

Â a processor some amount of memory, and of course it needs disk and network as well.

Â But typically scheduling algorithms vary about processor and

Â memory because these are the resources for where which there is most connection.

Â There are two goals of scheduling algorithms.

Â The first is to

Â 2:02

increase the throughput on the number of jobs you can execute per time unit.

Â And related to that is releasing the response time or

Â releasing the time that it takes one job to complete in your system.

Â Essentially we'll just take into account the completion time of jobs.

Â The second is high utilization of resources.

Â You want your resource to be utilized as much as possible.

Â You want your, all of your processors to be utilized 100% of the time,

Â all of your memory to be utilized 100% of the time, so

Â that you're making the most out of the resources that you invested your money in.

Â 2:34

So, let's look at single-processor scheduling in the lecture.

Â So, you have just one processor in this particular problem and

Â you might have multiple tasks that are trying to compete for these resources.

Â In this example, I have three tasks.

Â Task 1, Task 2, Task 3.

Â Task 1 arrives at times 0.

Â It has a running time of 10 time units.

Â Task 2 arrives at time 6.

Â It has a running of 5 time units.

Â And Task 3 arrives at time 8.

Â It has a running time of 3 time units.

Â 3:07

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.

Â 5:08

So in this particular approach, again you maintain all the tasks in a queue,

Â but not in the order of arrival.

Â Instead you maintain the the tasks in increasing order of running time.

Â So tasks that are shorter are maintained towards the head of the queue and

Â tasks that are longer are maintained at the tail of the queue.

Â Whenever the processor is free, you de-queue the head task and

Â you schedule it on the processor.

Â So once again let's go to an example of your three tasks, Tasks 1, 2, and 3,

Â with task lengths of 10, 5, and 3.

Â The arrival times here are all zeros because I want to show you an example

Â where the STF scheduling algorithm in fact has to make decisions among tasks.

Â And so here on Task 3 which has the shortest length is chosen to run first.

Â It starts running at time 0 and ends at time 3.

Â At which point Task 2 which is the next shortest task is scheduled.

Â It runs from time 3, finishes at time 8, and finally Task 1,

Â the longest task is run from time 8 to time 18.

Â So this is the shortest task first scheduling algorithm, STF,

Â sometimes this is, this algorithm, is also known as SJF, or

Â shortest job first scheduling algorithm, but we'll stick with STF

Â because I want to maintain the uniformity of terminology here.

Â 6:14

So why does STF do better than FIFO?

Â Well STF in fact that can be proved, formally proved, to create the shortest or

Â the smallest average completion time among all possible scheduling approaches for

Â a single processor system.

Â So given a single processor system and a bunch of tasks that you need to schedule,

Â among all the possible scheduling strategies that you might have,

Â the STF strategy gives you the smallest average completion time.

Â 6:38

For instance, for our previous example, the, the average completion time of STF

Â is the sum of the three completion times for the three tasks, divided by 3, which

Â happens to be, 18 plus 8 plus 3, divided by 3, which is 29 by 3, which is 9.66.

Â And this is much smaller than the completion time of 14.33 which we had for

Â the FIFO/FCFS approach.

Â The other nice thing about STF is that it is

Â actually a special case of what is known as priority scheduling.

Â In this particular STF scheduling approach, we sorted the tasks

Â according to the running time, and in fact we treated the running time as a priority.

Â But instead the priority might be specified by the user, for

Â instance the user might specify a higher priority for interactive tasks that

Â involve keyboard and mouse input, but a lower priority for background batch tasks

Â that don't require any user input but have an output at the end of the long run.

Â You always place the higher priority tasks at the head of the queue and

Â whenever those tasks, I wanted to compute you let them run on the processor.

Â 7:35

A third scheduling algorithm is what is known as round-robin scheduling algorithm.

Â In this case scheduling algorithm you allow tasks to be run

Â in pieces or in chunks.

Â In other words you split up a task into small quanta, and the quanta may be used

Â as small time units as just say one time unit as in our example here.

Â And you run only a portion of the task at the head of the queue.

Â When that portion of the task is done you preempt that task.

Â In other words you save the task of that, and the state of that task and

Â then you add it add the task back again to the, to the end of the queue.

Â You take the head of the queue task again, whatever task happens to be at the head of

Â the queue, and then you start running that task at the processor.

Â In order to run this again we need to bring back in the saved

Â state of that task if it was preempted in the past.

Â So again in our example, we go back to our example of three tasks, 1, 2 and

Â 3 which arrive at times 0, 6, and 8 respectively.

Â So Task 1 arrives first, it's the only one so it's run so

Â that it occupies the entire processor until time 6.

Â At which point of time Task 2 arrives, and so Task 2 is now run for one time unit.

Â And then when it's run for one time unit, it is put back at the end of the queue and

Â Task 1 is allowed to run, at this point of time, Task 1 has run for

Â 6 plus one 7 time units.

Â Task 2 has run for only one time unit.

Â Then at time 8, Task 3 arrives and now it is allowed to run for

Â one time unit because it's at the head of the queue, now after it runs for

Â one time unit it's put at the tail of the queue and now Task 1 and

Â Task 2 are allowed to run, and then again Task 3.

Â So this pattern repeats again.

Â 9:02

Then again you have other three tasks to run.

Â And at this point of time, Task 1 is run for nine time units.

Â You have 6 plus 3 greens, that's 9 greens.

Â Task 2 is run for 3 time units.

Â And Task 3, it has the blue ones, has run, has run for 3 time units.

Â And units 1, 2, and 3.

Â And so Task 3 is actually done at time 15, 'kay?

Â 9:41

So when do you prefer round-robin and when do you prefer shortest task first or FIFO?

Â Well, round-robin is more preferable for interactive applications,

Â applications that need, periodically need to, a, access to the processor so

Â that they can run and process things like the keyboard input and

Â the mouse input the and so on and so forth, 'kay?

Â These are applications where the user needs quick responses from the system.

Â On the other hand, FIFO or shortest tasks first is more preferable for

Â batch applications where the user submits a job, goes away for a while, and

Â comes back later on to get the result.

Â For these you don't necessarily need to have applications that

Â that run in quanta, but it can give them access to the CPU all at once.

Â And in fact, there are many hybrid scheduling approaches that combine both

Â the round-robin that we have seen and the FIFO/STF that we have seen,

Â these are known as hierarchical approaches.

Â