Scheduling Algorithms
1 First Come First Serve (FCFS)
2 Shortest Job First (SJF)
3 Round Robin (RR)
4 Shortest Remaining Time Next (SRTN)
5 Priority Based Scheduling or Event Driven (ED) Scheduling
Now let’s discuss some processor scheduling algorithms again stating that the goal is to select the most appropriate process in the ready queue.
CPU scheduling deals with the problem of deciding which of the processes in the ready queue is to be allocated to the CPU. There are several scheduling algorithms which will be examined in this section. A major division among scheduling algorithms is that whether they support pre-emptive or non-preemptive scheduling discipline.
Preemptive scheduling: Preemption means the operating system moves a process from running to ready without the process requesting it. An OS implementing this algorithms switches to the processing of a new request before completing the processing of the current request. The preempted request is put back into the list of the pending requests. Its servicing would be resumed sometime in the future when it is scheduled again. Preemptive scheduling is more useful in high priority process which requires immediate response. For example, in Real time system the consequence of missing one interrupt could be dangerous.
Round Robin scheduling, priority based scheduling or event driven scheduling and SRTN are considered to be the preemptive scheduling algorithms.
Non–Preemptive scheduling: Processes A scheduling discipline is non-preemptive if once a process has been allotted to the CPU, the CPU cannot be taken away from the process. A non-preemptible discipline always processes a scheduled request to its completion. In non-preemptive systems, jobs are made to wait by longer jobs, but the treatment of all processes is fairer.
First come First Served (FCFS) and Shortest Job First (SJF), are considered to be the non-preemptive scheduling algorithms.
The decision whether to schedule preemptive or not depends on the environment and the type of application most likely to be supported by a given operating system.
.1 First-Come First-Serve (FCFS)
The simplest scheduling algorithm is First Come First Serve (FCFS). Jobs are scheduled in the order they are received. FCFS is non-preemptive. Implementation is easily accomplished by implementing a queue of the processes to be scheduled or by storing the time the process was received and selecting the process with the earliest time.
FCFS tends to favour CPU-Bound processes. Consider a system with a CPU-bound process and a number of I/O-bound processes. The I/O bound processes will tend to execute briefly, then block for I/O. A CPU bound process in the ready should not have to wait long before being made runable. The system will frequently find itself with all the I/O-Bound processes blocked and CPU-bound process running. As the I/O operations complete, the ready Queue fill up with the I/O bound processes.
Under some circumstances, CPU utilisation can also suffer. In the situation described above, once a CPU-bound process does issue an I/O request, the CPU can return to process all the I/O-bound processes. If their processing completes before the CPUbound process’s I/O completes, the CPU sits idle. So with no preemption, component utilisation and the system throughput rate may be quite low.
Example:
Calculate the turn around time, waiting time, average turnaround time, average waiting time, throughput and processor utilization for the given set of processes that arrive at a given arrive time shown in the table, with the length of processing time given in milliseconds:
Process Arrival Time Processing Time
P1 0 3
P2 2 3
P3 3 1
P4 5 4
P5 8 2
If the processes arrive as per the arrival time, the Gantt chart will be
P1 P2 P3 P4 P5
0 3 6 7 11 13
Time Process Turn around Time = Waiting Time =
Completed t(Process Completed) Turn around time –
–t(Process Submitted) Processing time
0 - - -
3 P1 3 – 0 = 3 3 – 3 = 0
6 P2 6 – 2 = 4 4 – 3 = 1
7 P3 7 – 1 = 6 6 – 1 = 5
11 P4 11– 4 = 7 7 – 4 = 3
13 P5 13 – 2 = 11 11– 2 = 9
WELLDONE
ReplyDelete