CPU Scheduling Algorithms in Operating System

CPU Scheduling:

Scheduling is a fundamental operating system function. Almost all computer resources are scheduled before use. CPU Scheduling is the basis of the Multi-Programmed Operating System. If a process (job) is waiting for an I/o request, then the CPU switches from that job to another job. So, the CPU is always scheduled before use.

Types of CPU Scheduling in OS:

In OS, There are mainly two types of CPU Scheduling Scheme.

i. Non-Preemptive Scheduling: In Non-Preemptive Scheduling, the CPU assigns to a process, the processor does not release until the completion of that process. The CPU will assign to some other job only after the previous job has finished.

ii. Preemptive Scheduling: In Preemptive Scheduling, the CPU can release the processes even in the middle of executing. Some running tasks interrupt for some time and resume later when the priority task has finished its execution.

Some following schedulers are given below:

1. Short-term scheduler: The function of a Short-term scheduler is that select a job from the ready queue and it gives them control of CPU to that process with the help of ‘Dispatcher’. That’s why the Short-term scheduler is also say a CPU Scheduler.

2. Long-term scheduler: The function of the Long-term scheduler is that select the job from the pool of jobs and load these jobs into the main memory (ready queue) of the computer. So, the Long-term scheduler is also say a job scheduler.

3. Medium-term scheduler: If a process requests an I/O in the middle of the execution, then the process removes from the main memory and load into waiting for a queue. When the I/O operation is complete, then the job moves from waiting for the queue to the ready queue that says a Medium-term scheduler.

CPU Scheduling Algorithms:

CPU Scheduling algorithms are the algorithms which uses for assigning the system resources to processes in an operating system. In Operating System, there are mainly five types of CPU Scheduling Algorithms.

First Come First Serve (FCFS) Scheduling:

First Come First Serve Scheduling is the simplest CPU scheduling algorithm. The criteria of the First Come First Serve Scheduling algorithm are the process that requests the CPU first is holds the CPU or which process enters the ready queue first is served first. The operating system maintains a data structure that is a ready queue. If a process requests the CPU then it loads into the ready queue which process is the head of the ready queue, connect the CPU to that process.

ProcessBurst Time (ms)
P15
P224
P316
P410
P53

Consider the following set of processes that arrive at time o, the length of the CPU burst time in milliseconds (ms).

Burst time:

The burst time is the require-time of the CPU to execute that job. Generally, it’s unit milliseconds (ms). If the processes arrive in the order P!, P2, P3, P4, P5 and it serves in FCFS order.

FCFS

Now, We have to calculate the average waiting time, average response time.

CPU Scheduling Algorithms in Operating System

Average Response Time =(0+5+29+45+55)/5 = 26.8 ms

Shortest Job First (SJF) Scheduling:

Shortest Job First Scheduling is non-preemptive scheduling. The criteria of Shortest Job First Scheduling algorithm is that which process has the smallest CPU burst, CPU assigns to that process next. If two processes have the same CPU burst time, FCFS uses to break the tie.

ProcessBurst Time (ms)
P15
P224
P316
P410
P53

SJF

Now we have to calculate the average waiting time, average turnaround time, average response time.

CPU Scheduling Algorithms in Operating System

Average Response Time = (3+34+18+8+0)/5 = 12.6 ms

Round Robin (RR) Scheduling:

Round Robin Scheduling (RR) is a preemptive scheduling algorithm, it is designed especially for time-sharing systems. In the Round Robin Scheduling algorithm, the CPU switches between the processes. When the time quantum is expired, the CPU switches to another job. If the process may have a CPU burst of less than a one-time quantum then the process releases the CPU voluntarily. The scheduled will then proceed to the next process in the ready queue.

ProcessBurst Time
P130
P26
P38

The first 5 milliseconds assigns to process P1 when the time quantum expires, the CPU switches from process P1 to P2. When the time quantum of P2 expired, the process switches to process P3. Now we have to calculate the average waiting time, average turnaround time, average response time.

Round Robin

RR Burst time

Priority Scheduling:

Priority Scheduling can be either preemptive or non-preemptive. When a process arrives at the ready queue its priority. There are basically two types of Priorities, these are:

i. Internal Priority: It can define as some measurable quantities or qualities to compute the priority of a process.

  • Memory Requirements
  • Time Limits
  • CPU and I/O Requirements
  • File Requirements

    ii. External Priority: External priority means that it is external to the operating system, the CPU allocates to the process with the highest priority. It can define as some measurable quantities or qualities to compute the priority of a process.

  • The ratio of average I/O burst to average CPU burst
  • Importance of process
  • Consider the below problem for a better understanding of the priority scheduling algorithm:

    ProcessBurst Time (ms)Priority
    P162
    P2124
    P315
    P431
    P543

    Out of the five processes, P4 has the highest priority, so allocate the CPU to process P4 first. The next priority goes to P1 next. Continue this process until the five processes are completed. Now we have to calculate the average waiting time, average turnaround time.

    Priority Scheduling

    Priority Burst time

    Multilevel Queue Scheduling:

    In a Multilevel Queue Scheduling, the ready queue partitions into the number of ready queues. Each ready queue has a Multilevel Queue Scheduling algorithm.

    Example: The ready queue is partitioned into 4 ready queues.

    1. The first ready queue for the system process.
    2. The Second ready queue for foreground jobs (iterative process).
    3. The third ready queue for background jobs (Batch process)
    4. The fourth ready queue for the student process.

    The system process queue may follow FCFS, the interactive process may follow SJF, The background jobs queue may follow Round Robin and the student’s process may follow the SRT algorithm.
    CPU Scheduling Algorithms in Operating System
    The systems process queue has the highest priority of all, and the student process queue has the lowest priority of all. Each queue has an absolute priority queue.