Basics of Scheduling Algorithms


What are Scheduling Algorithms?

According to the degree of multi-programming, we try to keep multiple processes in the ready queue before sending them for processing. Ready queue is present inside RAM. We use different algorithms in operating system to execute processes in effective and efficient manner. These algorithms are known as scheduling algorithms.

Scheduling Algorithms are the ways of selecting a process from ready queue and put it in the CPU.

There are two main categories of scheduling algorithms-

1. Pre-emptive:

A process already in running queue can be sent back to ready queue. That process remains in ready queue till it gets its next chance to execute.

It's type includes:

a. SRTF- Shortest Remaining Time First

In this method, processes are executed which are closest to completion.

b. LRTF- Longest Remaining Time First

The process with the maximum remaining time gets executed first

c. Round Robin

Round Robin is the oldest and simplest scheduling algorithm. The algorithm gets its name from the round-robin principle, where each person in turn gets something evenly distributed. This is mainly used for multitasking scheduling algorithms.

d. Priority based

Priority scheduling is a technique for scheduling processes based on priority. In this way, the scheduler chooses tasks to run according to their priority. Processes with higher priority run first, jobs with the same priority run on round-robin or First Come First Serve basis. Priority can be set based on memory requirements, time requirements, etc.

2. Non-preemptive:

A process already in running queue will not be sent back to ready queue until and unless it is completed. In this case a process running in CPU does not interrupt in the middle of execution.

It's type includes:

a. FCFS- First Come First Serve:

The process which requests CPU first gets CPU allocation first.

b. SJF- Shortest Job First

The process with the shortest running time should be chosen to run next.

c. LJF- Longest Job First

This algorithm is based upon the fact that the process with the largest burst time is processed first.

d. HRRN- Highest Response Ratio Next

The CPU is assigned to the next process that has the highest response ratio.

e. Multilevel Queue

This algorithm divides the queue into several separate queues. In this method, processes are assigned to queues based on certain properties of the process (process priority, amount of memory, etc.).

Let's discuss few important terms related to scheduling.

1. Arrival Time-

The point of time at which a process enters ready queue.

2. Burst Time-

The time duration required by a process to get executed on CPU.

3. Completion Time-

The point of time at which a process completes its execution.

4. Turn around time-

It is the sum of times spent by the process waiting to get into memory, waiting in the ready queue, executing in CPU, and waiting for I/O; i.e. how long it takes to execute a process. {Completion time}-{Arrival time}

5. Waiting Time-

It is the time spent by a process waiting in the ready queue. {Turn around time}-{Burst time}

6. Response Time-

{The time at which a process het's CPU for the first time}-{Arrival time}

Thank you for reading!

Happy Learning :)