CPU Scheduling Algorithms in Operating System

Scheduling:

Scheduling is a fundamental operating system function. Almost all computer resources are scheduled before use.

CPU Scheduling:

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, CPU is always scheduled before use.

Types of CPU Scheduling:

There are mainly two types of CPU Scheduling Scheme.

  • Non-Preemptive Scheduling
  • Preemptive Scheduling
  • Non-Preemptive Scheduling:

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

    Preemptive Scheduling:

    In the Preemptive Scheduling, the CPU can release the processes even in the middle of executing. Some running task is interrupted for some time and resumed it later when the priority task has finished its execution.

    Some following schedulers are given :

    1. Short-term scheduler
    2. Long-term scheduler
    3. Medium-term scheduler

    Short-term scheduler:

    The function of 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 called CPU Scheduler.

    Long-term scheduler:

    The function of the Long-term scheduler is that selects the job from the pool of jobs and loaded these jobs into main memory (ready queue) of the computer. So, the Long-term scheduler is also called job scheduler.

    Medium-term scheduler:

    If a process requests an I/O in the middle of the execution, then the process removed from the main memory and loaded into waiting for a queue. When the I/O operation completed, then the job moved from waiting for the queue to ready queue that is called Medium-term scheduler.

    Types of CPU Scheduling Algorithms:

    1. First Come First Serve Scheduling Algorithm
    2. Shortest Job First Scheduling Algorithm
    3. Round Robin Scheduling Algorithm
    4. Priority Scheduling Algorithm
    5. Multilevel Queue Scheduling Algorithm

    First Come First Serve (FCFS) Scheduling:

    First Come First Serve Scheduling is the simplest CPU scheduling algorithm. The criteria of 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 request the CPU then it is loaded 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 is given in milliseconds (ms).

    Burst time:

    The burst time is the time required 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 served in FCFS order.
    Now, We have to calculate the average waiting time, average response time.
    FCFS

  • Average Turn Around Time:
  • Turn Around Time = Finished time - Arrival time
    Turn Around Time for P1 = 5 - 0 = 5
    Turn Around Time for P2 = 29 - 0 = 29
    Turn Around Time for P3 = 45 - 0 = 45
    Turn Around Time for P4 = 55 - 0 = 55
    Turn Around Time for P5 = 58 - 0 = 58
    

    Average Turn Around Time =(5+29+45+55+58)/5 = 38.4 ms

  • Average Waiting Time:
  • Waiting Time = Starting time - Arrival time
    Waiting Time for P1 = 0
    Waiting Time for P2 = 5 - 0
    Waiting Time for P3 = 29 - 0
    Waiting Time for P4 = 45 - 0
    Waiting Time for P5 = 55 - 0
    

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

  • Average Response Time:
  • Response Time = First response - Arrival time
    Response Time for P1 = 0
    Response Time for P2 = 5 - 0
    Response Time for P3 = 29 - 0
    Response Time for P4 = 45 - 0
    Response Time for P5 = 55 - 0
    

    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 having the smallest CPU burst, CPU is assigned to that process next. If two process having the same CPU burst time, FCFS is used to break the tie.

    ProcessBurst Time (ms)
    P15
    P224
    P316
    P410
    P53

    Now we have to calculate the average waiting time, average turn around time, average response time.
    SJF

  • Average Waiting Time:
  • Waiting time = Starting time - Arrival time
    Waiting time for P1 = 3 - 0 = 3
    Waiting time for P2 = 34 - 0 = 34
    Waiting time for P3 = 18 - 0 = 18
    Waiting time for P4 = 8 - 0 = 8
    Waiting time for P5 = 0
    

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

  • Average Turn Around Time:
  • Turn around time = Finish time - Arrival time
    Turn around time for P1 = 8 - 0 = 8
    Turn around time for P2 = 58 - 0 = 58
    Turn around time for P3 = 34 - 0 = 34
    Turn around time for P4 = 18 - 0 = 18
    Turn around time for P5 = 3 - 0 = 3
    

    Average Turn Around Time = (8+58+34+18+3)/5 = 24.2 ms

  • Average Response Time:
  • Response time = First response time - Arrival time
    Response time for P1 = 3 - 0 = 3
    Response time for P2 = 34 - 0 = 34
    Response time for P3 = 18 - 0 = 18
    Response time for P4 = 8 - 0 = 8
    Response time for P5 = 0 
    

    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 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 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 are assigned to process P1 when time quantum is expired, 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 turn around time, average response time.
    Round Robin

  • Average Waiting Time :
  • Waiting time for P1 = 0+(15-5)+(24-20) = 14
    Waiting time for P2 = 5+(20-10) = 15
    Waiting time for P3 = 10+(21-15) = 16
    

    Average Waiting Time = (14+15+16)/3 = 15 ms

  • Average Turn Around Time :
  • Turn around time for P1 = 44
    Turn around time for P2 = 21
    Turn around time for P3 = 24
    

    Average Turn Around Time = (44+21+24)/3 = 29.66 ms

  • Average Response Time :
  • Response time for P1 = 0
    Response time for P2 = 5
    Response time for P3 = 10
    

    Average Response Time = (0+5+10)/3 = 5 ms

    Priority Scheduling:

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

  • Internal Priority
  • External Priority
  • Internal priority

    It can be defined as some measurable quantities or qualities to compute the priority of a process.

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

    External Priority

    It means that it is external to the operating system, the CPU is allocated to the process with the highest priority. External priority can be defined 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 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 turn around time.
    Priority Scheduling

  • Average Waiting Time:
  • Waiting time for P1 = 3
    Waiting time for P2 = 13
    Waiting time for P3 = 25
    Waiting time for P4 = 0
    Waiting time for P5 = 9
    

    Average Turn Waiting Time = (3+13+25+0+9)/5 = 10 ms

  • Average Turn Waiting Time:
  • Turn Waiting Time for P1 = 9
    Turn Waiting Time for P2 = 25
    Turn Waiting Time for P3 = 26
    Turn Waiting Time for P4 = 3
    Turn Waiting Time for P5 = 13
    

    Average Turn Waiting Time = (9+25+26+3+13)/5 = 15.2 ms

    Multilevel Queue Scheduling:

    In a Multilevel Queue Scheduling, the ready queue is partitioned into the number of ready queues. Each ready queue has 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 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.
    multilevel-queue scheduling
    The systems process queue having the highest priority of all, and student process queue having the lowest priority of all. Each queue has an absolute priority queue.