CPU Scheduling and Scheduling Algorithms

CPU Scheduling and Scheduling Algorithms

Whenever the CPU becomes idle, it is the job of the CPU Scheduler ( a.k.a. the short-term scheduler ) to select another process from the ready queue to run next.

The storage structure for the ready queue and the algorithm used to select the next process are not necessarily a FIFO queue. There are several alternatives to choose from.

There are several different criteria to consider when trying to select the “best” scheduling algorithm for a particular situation and environment, including:

    • CPU utilization – Ideally the CPU would be busy 100% of the time, so as to waste 0 CPU cycles. On a real system CPU usage should range from 40% ( lightly loaded ) to 90% ( heavily loaded. )
    • Throughput – Number of processes completed per unit time. May range from 10 / second to 1 / hour depending on the specific processes.
    • Turnaround time – Time required for a particular process to complete, from submission time to completion. ( Wall clock time. )
    • Waiting time – How much time processes spend in the ready queue waiting their turn to get on the CPU.
      • Load average – The average number of processes sitting in the ready queue waiting their turn to get into the CPU. Reported in 1-minute, 5-minute, and 15-minute averages by “uptime” and “who”. )
    • Response time – The time taken in an interactive program from the issuance of a command to the commence of a response to that command.

There are six popular process scheduling algorithms which we are going to discuss in this chapter −

  • First-Come, First-Served (FCFS) Scheduling
  • Shortest-Job-Next (SJN) Scheduling
  • Priority Scheduling
  • Shortest Remaining Time
  • Round Robin(RR) Scheduling
  • Multiple-Level Queues Scheduling

These algorithms are either non-preemptive or preemptive. Non-preemptive algorithms are designed so that once a process enters the running state, it cannot be preempted until it completes its allotted time, whereas the preemptive scheduling is based on priority where a scheduler may preempt a low priority running process anytime when a high priority process enters into a ready state.

1.First-Come First-Serve Scheduling, FCFS:
  • FCFS is very simple – Just a FIFO queue, like customers waiting in line at the bank or the post office or at a copying machine.
  • Unfortunately, however, FCFS can yield some very long average wait times, particularly if the first process to get there takes a long time

2.Shortest-Job-First Scheduling, SJF
  • The idea behind the SJF algorithm is to pick the quickest fastest little job that needs to be done, get it out of the way first, and then pick the next smallest fastest job to do next.

3.Priority Scheduling

  • Priority scheduling is a more general case of SJF, in which each job is assigned a priority and the job with the highest priority gets scheduled first.
  • Note that in practice, priorities are implemented using integers within a fixed range, but there is no agreed-upon convention as to whether “high” priorities use large numbers or small numbers.

4.Round Robin Scheduling

  • Round robin scheduling is similar to FCFS scheduling, except that CPU bursts are assigned with limits called time quantum.
  • When a process is given the CPU, a timer is set for whatever value has been set for a time quantum.
    • If the process finishes its burst before the time quantum timer expires, then it is swapped out of the CPU just like the normal FCFS algorithm.
    • If the timer goes off first, then the process is swapped out of the CPU and moved to the back end of the ready queue.
  • The ready queue is maintained as a circular queue, so when all processes have had a turn, then the scheduler gives the first process another turn, and so on.

5.Multilevel Queue Scheduling

  • When processes can be readily categorized, then multiple separate queues can be established, each implementing whatever scheduling algorithm is most appropriate for that type of job, and/or with different parametric adjustments.
  • Scheduling must also be done between queues, that is scheduling one queue to get time relative to other queues. Two common options are strict priority ( no job in a lower priority queue runs until all higher priority queues are empty ) and round-robin ( each queue gets a time slice in turn, possibly of different sizes. )

Next :Threads in Operating system