CPU SCHEDULING ALGORITHAM:
When a computer is multi programmed, it frequently has multiple processes competing for the CPU at the same time. This Situation occurs whenever two or more processes are simultaneously in the ready state. If only one CPU is available, a choice has to be made which process to run next. The part of the operating system that makes the choice is called the Scheduler and the algorithm it used is called the Scheduling algorithm.
1. Non Preemptive Scheduling:
In this type of scheduling, a scheduled job always completes before another scheduling decision is made. Therefore, finishing order of jobs is also same as their scheduling order. The Scheduling techniques which use non-preemptive scheduling are:
(i).First come First Serve(FCFS) Scheduling
(ii). Shortest Job Next (SJN) Scheduling
(iii). Deadline Scheduling .
First Come First Served (FCFS) Scheduling:
This is the simplest scheduling technique which is managed by FIFO (First In First Out.) That is, the process, which requests the CPU first. A queue in which all the processes, that want CPU time, are entered. The CPU executes the job in the readly queue one by one. Batch processing is one obvious example of FCFS scheduling in which all jobs in the batch are executed one by one. But turnaround time for the very first job in the batch is executed one by one.
Shortest Job Next(SJN) Scheduling:
In SJN scheduling , whenever a new job is to be admitted, the shortest of the arrived jobs is selected and given the CPU time. Throughput remains the same as in FCFS scheduling but waiting time improves. SJN associates with each job the length of its next CPU burst. ( CPU burst is the CPU time required by a job to execute its continuous executable part e.g If there are three executable statements and then two I/O, Executable part after I/O).
When the CPU is available, it is allocated to the job with smallest next CPU burst.
In deadline Scheduling the job with the earliest deadline is selected for scheduling. Deadline of a job is the time limit within which job much be over. If a job overshoots its deadline, it is said to be Deadline over run is calculated as
Where K is deadline overrun; C is job completion time D is deadline for a job.
In contrast to non-preemptive scheduling, a scheduling decision can be made even while the job is executing whereas in non-preemptive scheduling, a scheduling decision is made only after job completes its execution. Therefore, preemptive scheduling may force a job in execution of some other job can be undertaken, in order to improve throughput considerably.
1. Round Robin Scheduling
2. Response Ratio Scheduling
Round Robin Scheduling :
Round Robin scheduling is aimed at giving all programs equal opportunity to make progress. This is implemented by ensuring opportunity to make progress. This is implemented by ensuring that no program gets a second opportunity to execute unless all other programs have had at least one opportunity. A small unit of time, called a time quantum or time slice, is defined. The ready queue(queue of program waiting for CPU time) is treated as a circular queue. The programs in the ready queue are processed for the defined time slice. One by one.
Actual progress made by each job depends upon its capacity to utilize the processor. It implies that turnaround time of a job also depends upon its nature (CPU bound, I/O bound etc.) Thus a short job may not get better turnaround time than a long job.
To overcome this drawback of Round Robin Scheduling, a strategy known as the Least Completed Next(LCN) was mooted.
Response Ratio Scheduling:
Response Ratio is calculated as
Response Ratio=Elapse time/Execution time received
The job with highest response ration is preferred over others. When a short job arrives, its response ratio is high, so it is scheduled for execution immediately. A longer job would achieve high enough ratio only after a subsequent wait. Thus, the Highest Response Ratio Next(HRN) policy subsumes the desirable aspects of both SJN/STG and LCN scheduling policies.