Introduction to Scheduling

• In the beginning-there was no need for scheduling, since the users of computers lined up in front of the computer room or gave their job to an operator
• Batch processing-the jobs were executed in first come first served manner
• Multiprogramming-life became complicated!
• The scheduler is concerned with deciding policy, not providing a mechanism
• The dispatcher is the mechanism
• Dispatcher
  • Low-level mechanism
  • Responsibility: Context-switch
    • Save execution state of old process in PCB
    • Load execution state of new process from PCB to registers
    • Change scheduling state of process (running, ready, or blocked)
    • Switch from kernel to user mode
    • Jump to instruction in user process
• Scheduler
  • Higher-level policy
  • Responsibility: Deciding which process to run
• Scheduling refers to a set of policies and mechanisms to control the order of work to be performed by a computer system.
• Of all the resources of a computer system that are scheduled before use, the CPU is the far most important.
• But, other criteria may be important too (e.g.,memory)
• Multiprogramming is the (efficient) scheduling of the CPU
• Metrics
  • Execution time: $T_s$
  • Waiting time: time a thread waits for execution: $T_w$
  • Turnaround time: time a thread spends in the system (waiting plus execution time): $T_s+T_w=T_r$
  • Normalized turnaround time: $T_r/T_s$
• Process Behavior
  • The basic idea is to keep the CPU busy as much as possible by executing a (user) process until it must wait for an event and then switch to another process
  • Processes alternate between consuming CPU cycles (CPU-burst) and performing I/O (I/O-burst)
• Categories of Scheduling Algorithms (See Fig. 8)
  • In general, scheduling policies may be preemptive or non- preemptive
  • In a non-preemptive pure multiprogramming system, the short-term scheduler lets the current process run until it blocks, waiting for an event or a resource, or it terminates. First-Come-First-Served (FCFS), Shortest Job first (SJF). Good for ``background'' batch jobs.
  • Preemptive policies, on the other hand, force the currently active process to release the CPU on certain events, such as a clock interrupt, some I/O interrupts, or a system call. Round-Robin (RR), Priority Scheduling. Good for ``foreground'' interactive jobs
• Scheduling Algorithm Goals

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

  
  • 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
  • So, the design of a scheduler usually involves a careful balance of all requirements and constraints
  • The following is only a small subset of possible characteristics:I/O throughput, CPU utilization, response time (batch or interactive), urgency of fast response, priority, maximum time allowed, total time required.
  • Maximize:
    • CPU utilization
    • throughput (number of tasks completed per time unit, also called bandwidth)
  • Minimize:
    • Turnaround time (submission to completion, also called latency)
    • Waiting time (sum of time spent in Ready-queue)
    • Response time (time from start of request to production of first response, not full time for output)
  • Fairness:
    • every task should be handled eventually (no starvation)
    • tasks with similar characteristics should be treated equally
  • different type of systems have different priorities!