CPU SCHEDULING

CPU Scheduling

CPU scheduling is a process which allows one process to use the CPU while the execution of another process is on hold(in waiting state) due to unavailability of any resource like I/O etc, thereby making full use of CPU. The aim of CPU scheduling is to make the system efficient, fast and fair.

Scheduling Criteria

There are many different criterias to check when considering the "best" scheduling algorithm :
  • CPU utilization
    To make out the best use of CPU and not to waste any CPU cycle, CPU would be working most of the time(Ideally 100% of the time). Considering a real system, CPU usage should range from 40% (lightly loaded) to 90% (heavily loaded.)
  • Throughput
    It is the total number of processes completed per unit time or rather say total amount of work done in a unit of time. This may range from 10/second to 1/hour depending on the specific processes.
  • Turnaround time
    It is the amount of time taken to execute a particular process, i.e. The interval from time of submission of the process to the time of completion of the process(Wall clock time).
  • Waiting time
    The sum of the periods spent waiting in the ready queue amount of time a process has been waiting in the ready queue to acquire get control on the CPU.
  • Load average
    It is the average number of processes residing in the ready queue waiting for their turn to get into the CPU.
  • Response time
    Amount of time it takes from when a request was submitted until the first response is produced. Remember, it is the time till the first response and not the completion of process execution(final response).
In general CPU utilization and Throughput are maximized and other factors are reduced for proper optimization.

Scheduling Algorithms

We'll discuss four major scheduling algorithms here which are following :
  1. First Come First Serve(FCFS) Scheduling
  2. Shortest-Job-First(SJF) Scheduling
  3. Priority Scheduling
  4. Round Robin(RR) Scheduling
  5. Multilevel Queue Scheduling

First Come First Serve(FCFS) Scheduling

  • Jobs are executed on first come, first serve basis.
  • Easy to understand and implement.
  • Poor in performance as average wait time is high.
First Come First Serve(FCFS) Scheduling

Shortest-Job-First(SJF) Scheduling

  • Best approach to minimize waiting time.
  • Actual time taken by the process is already known to processor.
  • Impossible to implement.
Shortest-Job-First(SJF) Scheduling

In Preemptive Shortest Job First Scheduling, jobs are put into ready queue as they arrive, but as a process with short burst time arrives, the existing process is preemptied.
Preemptive Shortest-Job-First(SJF) Scheduling

Priority Scheduling

  • Priority is assigned for each process.
  • Process with highest priority is executed first and so on.
  • Processes with same priority are executed in FCFS manner.
  • Priority can be decided based on memory requirements, time requirements or any other resource requirement.
Priority Scheduling

Round Robin(RR) Scheduling

  • A fixed time is allotted to each process, called quantum, for execution.
  • Once a process is executed for given time period that process is preemptied and other process executes for given time period.
  • Context switching is used to save states of preemptied processes.
Round Robin(RR) Scheduling

Multilevel Queue Scheduling

  • Multiple queues are maintained for processes.
  • Each queue can have its own scheduling algorithms.
  • Priorities are assigned to each queue.
Subscribe to: Posts (Atom)