Scheduling in Interactive Systems

• Round-Robin Scheduling (RR) (See Fig. 2)
  • RR reduces the penalty that short jobs suffer with FCFS by preempting running jobs periodically
  • Scheduled thread is given a time slice
  • The CPU suspends the current job when the reserved quantum (time-slice) is exhausted
  • The job is then put at the end of the ready queue if not yet completed
  • Advantages;
    • no starvation
    • Fair allocation of CPU across jobs
    • Low average waiting time when job lengths vary widely
  • Disadvantages;
    • Poor average waiting time when job lengths are identical; Imagine 10 jobs each requiring 10 time slices, all complete after about 100 time slices, even FCFS is better!
    • The critical issue with the RR policy is the length of the quantum. If it is too short, then the CPU will be spending more time on context switching. Otherwise, interactive processes will suffer

  Figure 2: An example to Round Robin.

  
• Priority Scheduling (See Fig. 3)
  • Each process is assigned a priority (e.g., a number)
  • The ready list contains an entry for each process ordered by its priority
  • The process at the beginning of the list (highest priority) is picked first
    • Scheduler will always choose a thread of higher priority over one of lower priority
    • Implemented via multiple FCFS ready queues (one per priority)
  • Lower-priority may suffer starvation
  • A variation of this scheme allows preemption of the current process when a higher priority process arrives
  • Another variation of the policy adds an aging scheme where the priority of a process increases as it remains in the ready queue; hence, will eventually execute to completion

  Figure 3: An example to Priority-based Scheduling.

  
• Multiple Queues (See Fig. 4)
  • Multi-Level Queue (MLQ) scheme solves the mix job problem (e.g., batch, interactive, and CPU-bound) by maintaining separate ``ready'' queues for each type of job class and apply different scheduling algorithms to each
  • Multi-level feedback queue
    • this is a variation of MLQ where processes (jobs) are not permanently assigned to a queue when they enter the system
    • In this approach, if a process exhausts its time quantum (i.e., it is CPU-bound), it is moved to another queue with a longer time quantum and a lower priority
    • The last level usually uses FCFS algorithm in this scheme

  Figure 4: Multi-level queue and Multi-level feedback queue (lower).

  
• Lottery Scheduling
  • Implemented guaranteed access to resources is, in general, difficult!
  • process gets ``lottery tickets'' for various resources
  • more lottery tickets imply better access to resource
  • Advantages: Simple, Highly responsive, Allows cooperating processes/threads to implement individual scheduling policy (exchange of tickets)
  • Process A: 15% of CPU time, Process B: 25% of CPU time, Process C: 5% of CPU time, Process D: 55% of CPU time How many tickets should each process get to achieve this?