CPU Scheduling Algorithm ? | FCFS,SJF,Round Robbin,Multilevel Queue

CPU Scheduling Algorithm ?

cpu-scheduling-algorithm

CPU Scheduling Algorithm:-

CPU Scheduling Algorithm is given below:-

First-Come First-Served Scheduling:-

The process which comes first is executed first. The simplest CPU scheduling algorithm is the first-come, first-served (FCFS) scheduling algorithm. With this scheme, the process that requests the CPU first is allocated the CPU first. The implementation of the FCFS policy is easily managed with a FIFO queue. When a process enters the ready queue, its PCB is linked onto the tail of the queue. When the CPU is free, it is allocated to the process at the head of the queue. The running process is then removed from the queue. The code for FCFS scheduling is simple to write and understand. The average waiting time under the FCFS policy, however, is often quite long.

Consider the following set of processes that arrive at time 0, with the length of the CPU-burst time given in milliseconds:

  Process                        Burst Time

PI                                 24

P2                                3

P3                                3

If the processes arrive in the order PI, P2, P3, and are served in FCFS order, we get the result shown in the following Gantt chart:

cpu-scheduling-algorithm

The waiting time is 0 milliseconds for process PI, 24 milliseconds for process PZ, and 27 milliseconds for process P3. Thus, the average waiting time is (0 + 24 + 27)/3 = 17 milliseconds. If the processes arrive in the order P2, P3, Pl, however, the results will be as shown in the following Gantt chart:

cpu-scheduling-algorithm

The average waiting time is now (6 + 0 + 3)/3 = 3 milliseconds. This reduction is substantial. Thus, the average waiting time under an FCFS policy is generally not minimal and may vary substantially if the process CPU-burst times vary greatly.

Shortest-Job-First Scheduling:-

The job has bees shortest execution time will be executed first.

This algorithm associated with each process the length of the latter’s next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If two processes have the same length next CPU burst, FCFS scheduling is used to break the tie. Note that a more appropriate term would be the shortest next CPU burst because the scheduling is done by examining the length of the next CPU burst of a process, rather than its total length. We use the term SJF because most people and textbooks refer to this type of scheduling discipline as SJF.

 

As an example, consider the following set of processes, with the length of the CPU-burst time given in milliseconds:

Process                        Burst Time

PI                                 6

p2                               8

p3                                7

p4                                3

 

Using SJF scheduling, we would schedule these processes according to the

following Gantt chart:

cpu-scheduling-algorithm

The waiting time is 3 milliseconds for process PI, 16 milliseconds for process P2,9 milliseconds for process PS, and 0 milliseconds for process Pq. Thus, the average waiting time is (3 + 16 + 9 + 0)/4 = 7 milliseconds.

Priority Scheduling:-

Each process is given by a priority(an integer from 0 to 4095). The process having highest priority will be executed first. If two process having same priority then FCFS is used to break the time.

Some systems use low numbers to represent low priority; others use low numbers for high priority. This difference can lead to confusion. In this text, we use low numbers to represent high priority. As an example, consider the following set of processes, assumed to have arrived at time 0, in the order PI, P2, …, Ps, with the length of the CPU-burst time given in milliseconds:

 

Process                        Burst                Time Priority

P1                                10                    3

p2                               1                      1

p3                                2                      4

P4                               1                      5

P5                               5                      2

Using priority scheduling, we would schedule these processes according to the following Gantt chart:

CPU Scheduling Algorithm

The average waiting time is 8.2 milliseconds. Priorities can be defined either internally or externally. Internally defined priorities use some measurable quantity or quantities to compute the priority of a process.

Round-Robin Scheduling:-

It is a preempted form of the FCFS algorithm. A fixed CPU time called as time quantum is given to each process.

This algorithm generally used in Timesharing OS.

To implement RR scheduling, we keep the ready queue as a FIFO queue of processes. New processes are added to the tail of the ready queue. The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after 1-time quantum, and dispatches the process.

Consider the following set of processes that arrive at time 0, with the length of the CPU-burst time given in milliseconds:

Process                        Burst Time

PI                                 24

P2                                3

P3                                3

If we use a time quantum of 4 milliseconds, then process P1 gets the first 4 milliseconds. Since it requires another 20 milliseconds, it is preempted after the first time quantum, and the CPU is given to the next process in the queue, process P2. Since process P2 does not need 4 milliseconds, it quits before its time quantum expires. The CPU is then given to the next process, process P3. Once each process has received 1-time quantum, the CPU is returned to process P1 for an additional time quantum. The resulting RR schedule is

CPU Scheduling Algorithm

The average waiting time is 17/3 = 5.66 milliseconds.

In the RR algorithm, no process is allocated the CPU for more than 1 time quantum in a row. If a process’ CPU burst exceeds 1-time quantum, that process is preempted and is put back in the ready queue. The RR scheduling algorithm is preemptive.

Multilevel Queue Scheduling

Another class of scheduling algorithms has been created for situations in which processes are easily classified into different groups. For example, a common division is made between foreground (or interactive) processes and background (or batch) processes. These two types of processes have different response-time requirements, and so might have different scheduling needs. In addition, foreground processes may have priority (or externally defined) over background processes.

Note:-

Preemptive Vs Non-Preemptive Scheduling

The Scheduling algorithms can be divided into two categories with respect to how they deal with clock interrupts.

Non-preemptive SchedulingA scheduling discipline is non-preemptive if once a process has been used the CPU, the CPU cannot be taken away from that process.

Preemptive Scheduling: A scheduling discipline is preemptive if once a process has been used in the CPU, the CPU can be taken away.

 

Also Read: What is CPU scheduling?

Also Read: What is the Scheduler?

Also Read: What is a process ?

basicittopic

basicittopic

A Computer Science Study for IT students and people of IT community