Embedded Talks Ep 4: Scheduling Algorithms
An operating system must provide an scheduler that is tasked with job of handling multiple process/tasks
Before we dive into such schedulers and their algorithms we need to understand few concepts before hand
Workload:
Processes/Tasks running on the system are collectively called workload , Determining the workload is a critical part of building policies for the scheduler. For better understanding of algorithms discussed later we make following assumptions.
Scheduling Metrics:
Beyond making workload assumptions,we also need one concept to unable us to compare different scheduling policies i.e Scheduling Metric , A metric is something that is used to measure something for now we will use a simple metric called TURN AROUND TIME
The turn around time of a job is defined as
T(turnaround)= T(completion) - T(arrival)
Since we have assume that each job arrive at same time so
T(turnaround)=T(completion) - 0 ,= T(completion)
First In ,First Out (FIFO):
The most basic algorithm a scheduler can have is FIFO often called First come First served, It is very simple and easiest to understand , Lets look at simple example We have two job A and B arrive at same time A takes hold of cpu first hence it is processed and then B gets processed and both takes same amount of completion time say 20 so their average,
(20+20)/2 =20 the turn around time
But there is a catch/issue with this approach if A takes a 100 then task B is starved and the turn around metric average is now , Task B turn around time rose from 20 to 120 since it waited for completion 100 cycles
(100+120)/2= 110 This feels like grocery store line where people with smaller cart are just waiting for huge cart to end .
Shortest Job First:
To solve the FIFO problem as simple approach is to complete short job first and then do the bigger heavy load tasks,
with this our turn around time got reduce Task B get completed first taking 20 cycles and task A takes 100 cycles
(20+100)/2=60
This works great but only under the assumption that arrival time for both tasks is 0 that is they arrive at same time
But this is not a realistic approach if the tasks arrive at different time then what will happen let say task A takes the cpu first and then Task B takes it Now task A takes 100 cycles for completion and takes B arrive at T10 takes 120 cycles for completion.
(100 +(120-10))/2 =105 turn around time
Shortest Time to Completion First(STCF):
Apart from context switching discussed in ep3 and timer interrupts a scheduler can preempt job meaning it can stop Task A and run Task B and then run task A later, Shortest Job First is by definition a non preemptive algorithm thus it suffer from problem discussed earlier
The STCF cooperates preemptive scheduling basically it adds preemption to shortest job first algorithm ,Any time a new job enters it determines the remaining jobs and new job which has the least time left and schedules that one to run,
So basically in our example above task A will get preempt Task B will run and then reaming of Task A will run
(100 +(20-10))/2= 55 cycles as turn around time
Results are much improved but once again with our assumption that all job arrive at same time , However with introduction of time-shared machines changed all that . Now users would sit at a terminal and demanded interactive performance and thus a new metric was born RESPONSE TIME
T(response)=T(first-run) - T(arrival)
e.g if now if task A arrive at 0 and task B arrive at 10 and other job C arriving at time 10 then response time for each job is
0+0+10/3 = 3.33 sec average response time, Thus we have another problem how can we built scheduler sensitive to time response.
ROUND ROBIN:
Tasks are selected for execution in a fixed sequence. On each clock tick, the current task is discontinued, and the next is allowed to start execution.
The idea is simple instead of running the job to completion we run the job for a time slice and then switches to the next job in run queue.
To understand this better lets look at example. Assume three job A, B,C arrive at same time in system and each wishes to run for 5 seconds , An SJF scheduler will run each job to completion before running another in Contrast RR with a time slice of 1 seconds would cycle through jobs quickly
now average response time will be 0+1+2/3 =1 and for SJF 0+5+10/3 =5 as you can see the length of time slice is critical for RR the short it is the better however making it too short is problematic suddenly the context switch will dominate overall performance.