Scheduling is the process of determining which processes will actually run when there are multiple runnable processes. It is very important because it can have a big effort on the resource utilization and good performance of the system. The part of operating system that makes this decision is called scheduler. The algorithm it uses is called scheduling algorithm.
With batch system having input in the form of card, the scheduling algorithm was simple just a single or one process at a time and the user wait to run another process. With time sharing system the scheduling algorithm a more complex, as there are multiple users waiting for services. Now as the operating system become more sophisticated they started supporting multiprogramming for maximum CPU utilization.
Various criteria come to mind as to what constitute a good scheduling algorithm.
Some of the possibilities are:
- Make sure each process get equal access to the CPU.
- Keep the CPU busy 100 % of the time.
- Minimize response time for interactive users.
- Minimize the time batch user must wait for I/O.
- Maximize the number of jobs processed per hour.
- Long term scheduling
- Medium term scheduling
- Short time scheduling
- Short time scheduling
- Long term scheduling
Also known as job scheduling, determine which jobs or process shall be allowed to complete foe system resources. Once the job scheduler makes a job active, it stays until it terminate. The main objective of job scheduler is to provide the medium- term scheduler with an appropriate number of jobs. Too few jobs, and the CPU ma=y sit idle because all the jobs are blocked. Too many jobs and the memory management system become overloaded.
Medium term scheduling is also known as swapper, swap process in and out of memory. Any memory management that supports multiprogramming can use swapping to allow more process to share a system.
Short term scheduling is also known as dispatcher, allocate the CPU to a process that is loaded into main memory and ready to run. Typically the dispatcher allocates the CPU for a fixed maximum amount of time. A process that must be release the CPU after exhausting its time slot returns to the pool of processes from which the dispatcher selects the process to execute.
Objectives of scheduling
There could be many objectives that must be considered in the design of scheduling:-
Fairness: – make sure that each process gets its fair share of CPU.
Predictable: – a given job should be run in about the same amount of time.
Throughput: – Maximum number of job should be processed per unit time.
Efficiency: – keeps the CPU busy 100 percent of the time.
Resources: – scheduling mechanism should keep the resource of the system busy.
Priorities: – scheduling mechanism should favor the higher priority processes.
If the CPU is busy in execution of process then work is being done. Work can be measured as number of jobs done per unit time is called throughput. For very long processes, this rate varies from one process per hours but for short transaction, throughput is 10 processes per second.
Let us consider a multiprogramming operating system which starts its operation at t0 and stop at time to after processing a collection of programs (pi) containing n program.
Its throughput is given by:-
Throughput=number of program completed / total time taken
Number of jobs done per unit time is called throughput.
Different criteria have been suggested for comparison of CPU scheduling algorithm.
- CPU utilization: – we have to keep CPU as busy as possible; it may range from 1 to 100 %.
- Throughput: – it is a measure of work in terms of number of process completed per time unit. For long processes, this rate may be 1 process per hour, for short transaction throughput might be 10 processes per second.
- Turn around time: – is defined as interval between the time of submission and completion of the job and should be as less as possible.
- Waiting time: – it is the sum of the time interval for which the process has to wait in ready queue. The CPU scheduling algorithm should try to make this time as less as possible for a given process.
- Response time: – it is defined as the time interval between the job submission and the first response produced by the job.
The amount of time interval assigned to each process is called quantum size, which is allowed to run. If the process is still running at the end of the quantum, the CPU is preempted and given to another process. If the process is blocked or finished before, the quantum has elapsed.
Type of scheduling
Basically, there are two types of scheduling algorithm:-
- Preemptive scheduling
- Non- preemptive scheduling
Even if the CPU has been allocated to a certain process, it can be snatched from the process any time either due to the time constrain or due to priority reason. It implies that if process with higher priority become ready for its execution, the process which is currently using the cpu will be forced to give up the cpu so that higher priority job can run fast.
In case of non-preemptive scheduling once the CPU has been allocated to a process, the process keeps the CPU until it terminates or its transition to be blocked state. This means that once CPU is allocated to a process, this process can use the CPU for its own execution till it willingly surrenders or leave the CPU.
- Processes Scheduling queue As processes enter the system they put in job queue....
- Mutual Exclusion of Processes Mutual exclusion is a mechanism to ensure that only one...
- Introduction to Processes in operating system Early computer system allowed any one program to be...
- Types of operating systems An operating system can also be divided into many types...
- Dekker’s Algorithm Dekker’s Algorithm Dijktra reported on algorithm for mutual exclusion for...