Scheduling

Scheduling

1. CPU-bound

   • Have long CPU burst and thus infrequent I/O waits.

2. I/O bound

   • Have short CPU burst and thus frequent I/O waits.

3. non-preemptive

   • Scheduling algorithm picks a process to run and then just lets it run until it blocks or voluntarily releases the CPU. E Even if ti runs for many hours, it will not be forcibly suspended.
   • In effect, no scheduling decisions are made during clock interrupts. After clock-interrupt processing has been finished, the process that was running before the interrupt is resumed, unless a higher-priority process was waiting for a now-satisfied timeout.

4. preemptive

   • Scheduling algorithm picks a process and lets it run for a maximum of some fixed time. If it is still running at the end of the time interval, it is suspended and the scheduler picks another process to run.
   • Doing preemptive scheduling requires having a clock interrupt occur at the end of the time interval to give control of the CPU back to the scheduler. If no clock is available, non-preemptive scheduling is the only option.

5. Batch

   • Throughput
     • Maximize jobs per hour.
   • Turnaround time
     • Minimize time between submission and termination.
   • CPU utilization
     • Keep the CPU busy all the time.

6. Interactive

   • Response time
     • Respond to requests quickly.
   • Proportionality
     • Meet users' expectations.

7. Real time

   • Meeting deadlines
     • Avoid losing data.
   • Predictability
     • Avoid quality degradation in multimedia systems.

8. All systems

   • Fairness
     • Giving each process a fair share of the CPU.
   • Balance
     • Keeping all parts of the system busy.
   • Policy enforcement
     • Seeing that stated policy is carried out.

9. Batch System Scheduling

   • First-Come, First-Served
     • non-preemptive
     • Advantages:1.Easy to understand and equally easy to program.2.Fair (iPhone)
     • Disadvantages: If there are many I/O-bound processes, it will take a lot of time to finish computing.
   • Shortest Job First
     • non-preemptive It produces the minimum average response time for batch systems.
   • Shortest Remaining Time Next
     • preemptive version of shortest job first. The scheduler always chooses the process whose remaining run time is the shortest. 

10. Interactive Systems

    • Round-Robin
      • Each process is assigned a time interval, called it quantum, during which ti is allowed to run. If the process is still running at the end of the quantum, the CPU is preempted and given to another process. If the process has blocked or finished before the quantum has elapsed, the CPU switching is done when the process blocks, of course.
      • Setting the quantum too short causes too many process switches and lower the CPU efficiency, but setting it too long may cause poor response to short interactive requests. A quantum around 20-50 msec is often a reasonable compromise. 
    • Priority Scheduling
      • Round-Robin scheduling makes the implicit assumption that all processes are equally important. The basic idea: each process is assigned a priority and the runnable process with the highest priority is allowed to run. 
      • To prevent high-priority processes from running indefinitely, the scheduler may decrease the priority of the currently running process at each clock tick. If this action causes its priority to drop below that of the next highest process, a process switch occurs.
      • Alternatively, each process may be assigned a maximum time quantum that it is allowed to run.  When this quantum s used up, the next-highest-priority process is given a chance to run.
      • It is often convenient to group processes into priority classes and use priority scheduling among the classes but round-robin scheduling within each class.
      • Multiple Queues
        • It is more efficient to give CPU-bound processes a large quantum once in a while, rather than giving them small quanta frequently to reduce swapping. On the other hand, giving all processes a large quantum would mean poor response time.
        • The solution is to set up priority classes. Processes in the highest class were run for one quantum.  Processes in the next-highest class were run for two quanta. Processes in the next one were run for four quanta. Whenever a process used up all the quanta allocated to it, it was moved down one class.
        • As the process sank deeper into the priority queues, it would be run less and less frequently, saving the CPU for short, interactive processes.
    • Shortest Process Next
      • If we regard the execution of each command as a separate "job", then we can minimize overall response time by running the shortest one first. The problem is figuring out which of the currently runnable processes is the shortest one.
      • Make estimate based on past behavior and run the process with the shortest estimated running time. The technique of estimating the next value in a series by taking the weighted average of the current measured value and the previous estimate is called aging.
    • Guaranteed Scheduling
      • Scheduling is to make real promises to users about performance and then live up to those promises.
      • Realistic promise: Every user/process among n users/processes will receive about 1/n of the CPU power.
    • Lottery Scheduling
      • The basic idea is to give processes lottery tickets for various system resources, such as CPU time. Whenever a scheduling decision has to be made, a lottery ticket is chosen at random, and the process holding that ticket get the resource.
      • More important processes can be given extra tickets, to increase their odds of winning.
      • Cooperating processes may exchange tickets if they wish.
    • Fair-Share Scheduling
      • In this model, each user is allocated some fraction of the CPU and the scheduler picks processes in such a way as to enforce it.

11. when to schedule

    • process creatoin
    • process exit
    • process blocked
    • completion interrupt