Scheduling is the method by which work specified by some means is assigned to resources that complete the work. The resources may be virtual computation elements such as threads, processes or data flows, which are in turn scheduled onto hardware resources such as processors, network links or expansion cards.
A scheduler is what carries out the scheduling activity. Schedulers are often implemented so they keep all compute resources busy; allow multiple users to share system resources effectively, or to achieve a target quality of service. Scheduling is fundamental to computation itself, and an intrinsic part of the execution model of a language.
Objectives of Scheduling:
• Policy enforcement
• Response Time
• Turnaround time
There are different scheduling policies which are described below:
First Come First Serve (FCFS)
Shortest Job First (SJF)
Round Robin scheduling
First Come First Serve (FCFS):
First-Come-First-Served algorithm is the simplest scheduling algorithm is the simplest scheduling algorithm. Processes are dispatched according to their arrival time on the ready queue. Being a non-pre-emptive discipline, once a process has a CPU, it runs to completion. The FCFS scheduling is fair in the formal sense or human sense of fairness but it is unfair in the sense that long jobs make short jobs wait and unimportant jobs make important jobs wait. FCFS is more predictable than most of other schemes since it offers time. FCFS scheme is not useful in scheduling interactive users because it cannot guarantee good response time.The code for FCFS scheduling is simple to write and understand.
One of the major drawbacks of this scheme is that the average time is often quite long. The First-Come-First-Served algorithm is rarely used as a master scheme in modern operating systems but it is often embedded within other schemes.
• Easy to implement
• It is very simple
• It is also intuitively fair
• Problematic with some time sharing systems
• Average waiting time is very large
• Due to these reasons, performance gets affected or degraded
Shortest Job First (SJF):
Shortest-Job-First (SJF) is a non-preemptive discipline in which waiting job (or process) with the smallest estimated run-time-to-completion is run next. In other words, when CPU is available, it is assigned to the process that has smallest next CPU burst. The SJF scheduling is especially appropriate for batch jobs for which the run times are known in advance. Since the SJF scheduling algorithm gives the minimum average time for a given set of processes, it is probably optimal. The SJF algorithm favors short jobs (or processors) at the expense of longer ones.The obvious problem with SJF scheme is that it requires precise knowledge of how long a job or process will run, and this information is not usually available. The best SJF algorithm can do is to rely on user estimates of run times.
• Overall performance is significantly improved in terms of response time.
• It is having least average waiting time, average turnaround time and average response time.
• There is a risk of starvation of longer processes
• It is difficult to know the length of the next CPU burst time.
Each process is assigned a priority, and priority is allowed to run. Equal-Priority processes are scheduled in FCFS order. The shortest-Job-First (SJF) algorithm is a special case of general priority scheduling algorithm. An SJF algorithm is simply a priority algorithm where the priority is the inverse of the (predicted) next CPU burst. That is, the longer the CPU burst, the lower the priority and vice versa. Priority can be defined either internally or externally. Internally defined priorities use some measurable quantities or qualities to compute priority of a process.
• Priority scheduling provides a good mechanism where the relative importance of each process may be precisely defined.
• If high priority processes use up a lot of CPU time, lower priority processes may starve and be postponed indefinitely. The situation where a process never gets scheduled to run is called starvation.
• Another problem with priority scheduling is deciding with process gets which priority level assigned to it.
Round Robin scheduling: One of the oldest, simplest, fairest and most widely used algorithms is round robin (RR). In the round robin scheduling, processes are dispatched in a FIFO manner but are given a limited amount of CPU time called a time-slice or a quantum. If a process does not complete before its CPU-time expires, the CPU is pre-empted and given to the next process waiting in a queue. The pre-empted process is then placed at the back of the ready list. Round Robin Scheduling is pre-emptive (at the end of time-slice) therefore it is effective in time-sharing environments in which the system needs to guarantee reasonable response times for interactive users. The only interesting issue with round robin scheme is the length of the quantum. Setting the quantum too short causes too many context switches and lower the CPU efficiency. On the other hand, setting the quantum too long may cause poor response time and approximates FCFS. In any event, the average waiting time under round robin scheduling is often quite long.
• Round Robin scheduling is fair in that every process gets an equal share of the CPU.
• It is easy to implement and if we know the number of processes on the ready list, we can know the worst case response time for process.
• Giving every process an equal share of the CPU is not always a good idea. For instance, highly interactive processes will get scheduled no more frequently than CPU bound processes.
|Complexity||Simplest scheduling algorithm||Difficult to understand and code||Difficult to understand||Performance depends upon the size of time quantum.|
|Allocation||It allocates the CPU in the order in which they arrives||CPU is allocated to the process with least CPU burst time||Based on priority, the higher priority job can run first||Pre-emption takes place after a fixed period of time|
|Application||Good for non-interactive system||Good for non-interactive system||Good for non-interactive system||Good for interactive system|
|Waiting Time||Average waiting time is large||Average waiting time is small||Average waiting time is small||Average waiting time is large|
|Usability||Never recommended when performance is major issue||Problem is to know the length of time for which the CPU is needed by the process||Can sometimes become a biggest cause of starvation||If time quantum size is large then this algorithm become same as FCFS algorithm and its performance degrades|
|Type of System||Suitable for batch system||Suitable for batch system||Based on priority||Suitable for time sharing system|