Scheduling is the method by which work specified by some means is assigned to resources that complete the work.
A scheduler is what carries out the scheduling activity.
Schedulers are often implemented so they keep all computer resources busy allow multiple users to share system resources effectively, or to achieve a target quality of service.
CPU scheduling is a process which allows one process to use the CPU while the execution of another process is on hold (in waiting state) due to unavailability of any resource like I/O etc, thereby making full use of CPU.
CPU scheduling is to make the system efficient, fast and fair.
There are many different criteria’s to check when considering the “best” scheduling algorithms<
§ CPU utilization
To make out the best use of CPU and not to waste any CPU cycle, CPU would be working most of the time(Ideally 100% of the time). Considering a real system, CPU usage should range from 40% (lightly loaded) to 90% (heavily loaded.)
It is the total number of processes completed per unit time or rather say total amount of work done in a unit of time. This may range from 10/second to 1/hour depending on the specific processes.
§ Turnaround time
It is the amount of time taken to execute a particular process, i.e. The interval from time of submission of the process to the time of completion of the process.
§ Waiting time
The sum of the periods spent waiting in the ready queue amount of time a process has been waiting in the ready queue to acquire get control on the CPU.
§ Load average
It is the average number of processes residing in the ready queue waiting for their turn to get into the CPU.
§ Response time
Amount of time it takes from when a request was submitted until the first response is produced. Remember, it is the time till the first response and not the completion of process execution(final response).
There are different types of scheduling algorithum
§ First Come First Serve(FCFS) Scheduling
§ Shortest-Job-First(SJF) Scheduling
§ Priority Scheduling
§ Round Robin(RR) Scheduling
First Come First Serve(FCFS) Scheduling
· Jobs are executed on first come, first serve basis.
· Easy to understand and implement.
· Poor in performance as average wait time is high.
· Best approach to minimize waiting time.
· Actual time taken by the process is already known to processor.
· Impossible to implement.
· Priority is assigned for each process.
· Process with highest priority is executed first and so on.
· Processes with same priority are executed in FCFS manner.
· Priority can be decided based on memory requirements, time requirements or any other resource requirement.
Types of scheduling
§ Long-term Scheduling
§ Medium-term Scheduling
§ Short-term Scheduling
· Long term scheduling is performed when a new process is created. It is shown in the figure above.
· If the number of ready processes in the ready queue becomes very high, then there is a overhead on the operating system (i.e., processor) for maintaining long lists, context switching and dispatching increases.
· Therefore, allow only limited number of processes in to the ready queue.
· The “long-term scheduler” managers this. Long-term scheduler determines which programs are admitted into the system for processing.
· Once when admit a process or job, it becomes process and is added to the queue for the short-term scheduler.
· In some systems, a newly created process begins in a swapped-out condition, in which case it is added to a queue for the medium-term scheduler scheduling
· Medium-term scheduler scheduling manage queues to minimize queuing delay and to optimize performance.
· Medium-term scheduling is a part of the swapping function.
· When part of the main memory gets freed, the operating system looks at the list of suspend ready processes, decides which one is to be swapped in (depending on priority, memory and other resources required, etc).
· This scheduler works in close conjunction with the long-term scheduler.
· It will perform the swapping-in function among the swapped-out processes. Medium-term scheduler executes somewhat more frequently.
· Short-term scheduler is also called as dispatcher
· Short-term scheduler is invoked whenever an event occurs, that may lead to the interruption of the current running process.
· For example clock interrupts, I/O interrupts, operating system calls, signals, etc.
· Short-term scheduler executes most frequently.
· It selects from among the processes that are ready to execute and allocates the CPU to one of them.
· It must select a new process for the CPU frequently. It must be very fast.