Task Scheduling Based On Multilevel Queue Scheduling Computer Science Essay
Abstract— This paper gives the survey on task scheduling. The different scheduling used to schedule task based on priority, time and deadline. To achieve that techniques such as First In First Out, Shortest Job first, Round Robin Scheduling, Multilevel Queue Scheduling are discussed. Among these techniques, the technique named Multilevel Feedback Queue scheduling is proposed as a good scheduling technique along with the future work.
Keywords— FCFS, Context Switching, Starvation, inflexible, SJF, Multilevel queue.
INTRODUCTION
Scheduling is a basic concept in computer multiprocessor and multitasking operating systems. Scheduling refers to the way processes are ordered to run on the CPUs, since there are typically many more processes running than there are available CPUs.
It also states that when an activity should start or end depending on its duration, predecessor activity, predecessor relationships, resource availability and especially the target completion which is consider as deadline.
The scheduler is concerned mainly with Throughput, Latency, Turn around, Response Time and Fairness. Throughput describes that number of processes that complete their execution per time unit. Latency, specifically illustrates about turn around and response time. In Turnaround, total time between submission of a process and its completion is described and the response time deals with the amount of time it takes from when a request was submitted until the first response is produced. Finally, fairness tells about the equal CPU time to each process (or more generally appropriate times according to each process’ priority).In practice, these goals often conflict (e.g. throughput versus latency), thus a scheduler will implement a suitable compromise.
In real-time environments, such as mobile devices for automatic control in industry (for example robotics), the scheduler also must ensure that processes can meet deadlines; this is crucial for keeping the system stable. Scheduled tasks are sent to mobile devices and managed through an administrative back end.
Types of Operating System Schedulers:
Long – Term Scheduler:
The long term scheduler is otherwise called admission scheduler. This scheduler decides which process or job has to be admitted first to the ready queue. Because while executing a program, which process to be run is authorized or delayed by long term scheduler. The degree of concurrency is maintained and it checks whether high or low amount of processes are to be executed concurrently. It also dictates how the split between CPU intensive and IO intensive is to be handled. It is useful for the real time process to get enough CPU time to finish their tasks in the modern OS’s. The GUI interfaces becomes slow if the real time scheduling is not proper.
Long-term scheduling is also important in large-scale systems such as batch processing systems, computer clusters, supercomputers and render farms.In these cases, special purpose job scheduler software is typically used to assist these functions, in addition to any underlying admission scheduling support in the operating system.
Long term scheduling obviously controls the degree of multiprogramming in multitasking systems, following certain policies to decide whether the system can honor a new job submission or, if more than one job is submitted, which of them should be selected. The need for some form of compromise between degree of multiprogramming and throughput seems evident, especially when one considers interactive systems. The higher the number of processes, in fact, the smaller the time each of them may control CPU for, if a fair share of responsiveness is to be given to all processes. Moreover we have already seen that a too high number of processes causes waste of CPU time for system housekeeping chores (trashing in virtual memory systems is a particularly nasty example of this). However, the number of active processes should be high enough to keep the CPU busy servicing the payload (i.e. the user processes) as much as possible, by ensuring that – on average – there always be a sufficient number of processes not waiting for I/O.
Short-term Scheduler:
The short-term scheduler (also known as the CPU scheduler) decides which of the ready, in-memory processes are to be executed (allocated a CPU) next following a clock interrupt, an IO interrupt, an operating system call or another form of signal. Thus the short-term scheduler makes scheduling decisions much more frequently than the long-term or mid-term schedulers – a scheduling decision will at a minimum have to be made after every time slice, and these are very short. This scheduler can be preemptive, implying that it is capable of forcibly removing processes from a CPU when it decides to allocate that CPU to another process, or non-preemptive in which case the scheduler is unable to “force” processes off the CPU. In most cases short-term scheduler is written in assembler because it is critical part of operating system.
II.ANALYSIS
In this part, we will discuss about different types of scheduler and their usage.
Each Technique is compared with different performance metrics such as Throughput, CPU utilization, Turnaround time, waiting time and response time.
First Come First Severed (FCFS)
This technique is a basic one, and commonly used scheduler. Based on the order the job arrives, the task be scheduled. To maintain this queue will be handled. The entire ready task is put inside the queue, according to the arrival of jobs.
To describe this sample source code along with the Gantt Chart.
Sample Code:
queue_Fifo q; //The processes inside the queue
task_Include(procs) // method to include a process into the queue
{
q.include_Tail(procs); //Inserting the new coming process at the tail end
q.size++; //Reporting
}
Rescheduling(){ // To remove the process from the queue
P=q.head_Exclude();
Reporting;
return P;
}
Example:
Consider four tasks P,Q,R and S. Each task requires some amount of time to complete the task. It is shown below.
Table 1
Task Schedule
Task
Time Unit
P
9
Q
5
R
10
S
6
Gantt Chart:
P
Q
R
S
0 9 14 24 30
Fig 1. FCFS Example
In the above example, the incoming task is included in the queue one by one. It executes based on the time units. The drawback of this the task which has to finish first has to wait until its time reach. Another problem is overhead occurs between the processes which leads to Context Switching.
Performance Evaluation:
Table 2
Performance Metric 1
performance metrics
First In First Out
Throughout
4/(30+3cs)
CPU utilization
30/(30+3cs)
Turnaround time
(9+14+24+29+6cs)/4=19 Omitting cs
Waiting time
(0+9+14+24+6cs)/4=11.75 Omitting cs
Response Time
(0+9+cs+14+2cs+24+3cs)/4=11.75 Omitting cs
Shortest Job First (SJF)
To overcome the problem of first one we are going for shortest job first technique. In this scheduler, a sorted list is maintained. In the list all the task which has least time unit will be scheduled first. This technique is useful because the task which has earliest time unit got the opportunity to execute. To describe this sample source code along with the Gantt Chart.
Sample Code:
sort_List SL; //Data Structure for sorted list
task_Include (procs, expected_runtime)
{
// method to include a process into the sorted list.
SL.insert(procs, procs.runtime);
}
//Inserting the newcoming process into the sorted list
Rescheduling(){
// To remove the shortest job from the list.
return SL.remove_head();
}
Example:
Consider four tasks P,Q,R and S. Each task requires some amount of time to complete the task which is given in table 1.
Gantt Chart:
Q
S
P
R
0 5 11 20 30
Fig 2. SJF Example
In this scheduler, the new incoming shortest job will be included in the list which leads to the problem named Starvation.
In Starvation, the job which has longest time to finish the execution will be waiting because all the newly arrived jobs will enter into the list. Therefore, the longest job will starve to get the resource.
Performance Evaluation:
Table 3
Performance Metric 3
performance metrics
First In First Out
Throughout
4/(30+3cs)
CPU utilization
30/(30+3cs)
Turnaround time
(5+11+cs+20+2cs+30+3cs)/4=16.5 Omitting cs
Waiting time
(0+5+cs+11+2cs+24+3cs)/4=10 Omitting cs
Response Time
(0+5+cs+11+2cs+24+3cs)/4=10 Omitting cs
Round Robin Scheduling
In time-sharing systems, the Round robin technique is very much successful. The jobs will be preempted.
For each task, particular time slot will be given. The job should be finished within that time, otherwise the other jobs will be preempted and the old task should wait until it gets the new slot.This will be achieved using queue
Sample Code:
queue_Fifo fq; //First in first out queue
task_Include(procs) // method to include a task into the queue
{
q.include_Tail(procs); //Inserting the new coming process at the tail end
}
Rescheduling(y){
// To remove the next process and run it
If(y==timer)
task_Include(current);
set_Timer(time_quanta);
return fq.remove_head();
}
Example
Here also the same four task will be taken and based on time quanta 3 and 6 the task be scheduled.
If Time quanta=3,
P
Q
R
S
P
Q
R
S
P
R
0 3 6 9 12 15 16 19 21 23 26
Fig 3. RR Example TQ=3
If time quanta=6,
P
Q
R
S
P
R
0 6 10 16 21 23 26
Fig 4. RR Example TQ=6
Performance Evaluation:
Table 3
Performance Metric 3
performance metrics
First In First Out
Throughout
4/(26+9cs)
CPU utilization
26/(26+9cs)
Turnaround time
(23+16+26+21)/4=21.5 Omitting cs
Waiting time
(15+12+17+16)/4=15 Omitting cs
Response Time
(0+3+6+9)/4=4.5 Omitting cs
Priority(PRI)
In this method a priority is fixed to each and every process. To implement this Shortest job first(SJF) algorithm is used. If two jobs are having the same priority the scheduled will be done based on FCFS queue. In some cases, the jobs be preempted eventhough it has the higher priority.
To describe this sample source code along with the Gantt Chart.
Sample Code:
PRI (L,M,H(RR))
queue_Fifo fq[3]; //The processes inside the queue
task_Include(procs, pri) // method to include a process into the queue
{
fq[pri].include_Tail(procs);
//Inserting the new coming process at the tail end
}
Rescheduling(y) {
// To remove the next process and run it
If(y==timer)
task_Include(current, current.pri);
set_Timer(time_quanta);
for pri=H to L
if(fq[pri].empty())
return fq[pri].remove_head();
}
Example:
Consider four tasks P,Q,R and S. Each task requires some amount of time to complete the task. It is shown below.
Gantt Chart:
For Time quanta=6
P
P
R
Q
R
S
0 6 8 14 18 21 26
Fig 4. PRI Example TQ=6
In the above example, the incoming task is included in the queue one by one. It executes based on the priority assigned to each task. The drawback of this the task is once the higher priority job finish its execution the lower priority jobs gets the chance of doing its execution.
Performance Evaluation:
Table 4
Performance Metric 4
performance metrics
First In First Out
CPU utilization
26/(26+4cs)
Response Time
(0+8+14+21+4cs)/4=10.75 Omitting cs
Multilevel Queue Scheduling
In Multilevel queue scheduling each process is divided into different groups. It is divided into the following processes:
SYSTEM PROCESSES
INTERACTIVE PROCESSES
INTERACTIVE EDITING PROCESSES
BATCH PROCESSES
STUDENT PROCESSES
Fig 5. Multilevel Queue scheduling Process groups.
In the above diagram, the foreground queue is called interactive and background queue is called batch. These two plays a major role in scheduling. The jobs are assigned to separate queues. The assigning be done based on memory size, process type and process priority. The vital one is each queue uses its own scheduling policy based on the need of the task. It can either do preemptively or non-preemptively.
Possibilities:
There are two possibilities to choose the scheduling algorithm:
Each queue has absolute priority; once the higher priority job queue becomes empty it won’t go for lower priority jobs.
Eg. In the Fig.5. The batch processes won’t get the chance of execution until the system, interactive and interactive editing processes finish its execution.
Each queue gets some CPU time when there is a time slice between queues after that it can be scheduled the processes in the queue.
Eg. If 70% of CPU time is given to foreground queue, it uses round robin scheduling.
Rest 30% be allotted to background queue which uses FIFO scheduling.
The main drawback of this scheduling is, it is not flexible. To overcome this we are going for multilevel feedback scheduling.
III.PROPOSED ALGORITHM
Comparing with different task scheduling, the proposed algorithm which can be used in task scheduling is multilevel feedback queue scheduling.
To overcome the inflexibility of multilevel queue scheduling, the multilevel feedback queue scheduling came into pass. In this, the process can move between various queues. Here separate queues will be used for handling the process, it automatically adjust the priority of the jobs. The process is either I/O bound or CPU bound. Based on the process type, the scheduling algorithm such as round- robin, FCFS be used which maintains the flexibility.
It gives preference on short jobs, I/O bound processes and schedule the process according to the nature of the process. It is described based on number of queues, the scheduling policy, a method used to upgrade, degrade or introduce a process and the inter scheduling between the queues.
Steps in Multilevel Feedback queue:
The new incoming process is added to the queue tail.
At one stage, the process comes to the top of the queue and that will be assigned to the CPU.
The process leaves the system once it completes its execution.
When the process relinquishes control, it leaves the queuing network and once it becomes ready it enters into the queue level.
When the process is having quantum time it will be preempted, and enter into the lower level of queue.
This will be repeated until the process completes or it reaches the base level queue.
Example
Consider three queues,
Q0- Round robin TQ: 8 milliseconds
Q1- Round robin TQ: 16 milliseconds
Q2- FCFS
TQ=8
TQ=16
FCFS
If the new job comes it enters into the queue Q0 and served as FCFS. When it gains CPU, it gets the tine quanta as 8 milliseconds. If the job is not completed within 8 milliseconds, the job moves to the queue Q1.
At Q1 job is again served as FCFS and received the time quanta of 16 milliseconds. If it is not complete it will preempt to queue Q2.
IV.CONCLUSION AND FUTURE WORK
From the different view of task scheduling, multilevel feedback scheduling is considered as the good one in assignment of task. This will be implemented in real time systems for the assignment of task.
Order Now