Scheduling Criteria

• Different CPU scheduling algorithms have different properties, and the choice of a particular algorithm may favour one class of processes over another.
• In choosing which algorithm to use in a particular situation, we must consider the properties of the various algorithms.
  • CPU utilization. We want to keep the CPU as busy as possible. Conceptually, CPU utilization can range from 0 to 100 percent. In a real system, it should range from 40 percent (for a lightly loaded system) to 90 percent (for a heavily used system).
  • Throughput. If the CPU is busy executing processes, then work is being done. One measure of work is the number of processes that are completed per time unit, called throughput. For long processes, this rate may be one process per hour; for short transactions, it may be 10 processes per second.
  • Turnaround time. From the point of view of a particular process, the important criterion is how long it takes to execute that process. The interval from the time of submission of a process to the time of completion is the turnaround time.
    • $T_r=T_s+T_w$
    • $T_s$ :Execution time.
    • $T_w$ :Waiting time.
  • Waiting time. The CPU scheduling algorithm does not affect the amount of time during which a process executes or does I/O; it affects only the amount of time that a process spends waiting in the ready queue.
  • Response time. In an interactive system, turnaround time may not be the best criterion. Often, a process can produce some output fairly early and can continue computing new results while previous results are being output to the user. Thus, another measure is the time from the submission of a request until the first response is produced.
• A typical scheduler is designed to select one or more primary performance criteria and rank them in order of importance. One problem in selecting a set of performance criteria is that they often conflict with each other. For example, increased processor utilization is usually achieved by increasing the number of active processes, but then response time decreases.
• It is desirable to maximize CPU utilization and throughput and to minimize turnaround time, waiting time, and response time.
• In most cases, we optimize the average measure. However, under some circumstances, it is desirable to optimize the minimum or maximum values rather than the average. For example, to guarantee that all users get good service, we may want to minimize the maximum response time.
• A scheduling algorithm that maximizes throughput may not necessarily minimize turnaround time.
  • Given a mix of short jobs and long jobs, a scheduler that always ran short jobs and never ran long jobs might achieve an excellent throughput (many short jobs per hour) but at the expense of a terrible turnaround time for the long jobs.
  • If short jobs kept arriving at a steady rate, the long jobs might never run, making the mean turnaround time infinite while achieving a high throughput.
• Investigators have suggested that, for interactive systems (such as time-sharing systems), it is more important to minimize the variance in the response time than to minimize the average response time.
• Some goals of the scheduling algorithm under different circumstances, see Fig. 5.4.

  Figure 5.4: Some goals of the scheduling algorithm under different circumstances.

  
• Under all circumstances, fairness is important. Another general goal is keeping all parts of the system busy when possible. If the CPU and all the I/O devices can be kept running all the time, more work gets done per second.