1. Types of Scheduling
   1. Scheduling is about selecting which process runs.
   2. Goal is to optimize a set of criteria
      1. fair
      2. No starvation
      3. Efficient
      4. low overhead
      5. Respect priorities
   3. Types:
      1. Long term- decide who gets executed at all. (who goes from New to Ready and who goes from New to ready/suspend). Keeps a limit on the number of processes going.
      2. Medium term - who gets brought into memory (Ready/Suspend to Ready or Blocked/Suspend to Blocked) Keeps a limit of the time wasted swapping
      3. Short term - who actually executes (goes from Ready to Running). The dispatcher. Acts on any event.
      4. I/O- who gets control of the I/O channels.
2. Scheduling algorithms
   1. Start with short-term
   2. User oriented (response time) vs. System Oriented (efficiency)
   3. User:
      1. Turnaround time - time start to finish
      2. Response time
      3. Meets deadlines.
      4. Predictability
   4. Priorities -
      1. Process with higher priorities run before low.
      2. Multiple queues.
      3. Starvation - allow priorities to change based of execution history.
      
   5. w:time spent waiting so far, e: time spent executing so far, s:total time, e+future.
   6. FCFS - first come, first served
   7. Round Robin - If quantum is too large, I/O bound processes are penalized, too small and too much time wasted in overhead.
   8. Virtual Round Robin - 2 ready queues: if a job was blocked for I/O it goes on the I/O job ready queue, which has higher priority.
   9. Shortest Process next - favor short jobs by letting them run first.
      1. Long processes can be starved.
      2. How do we know? For batch jobs, creator specifies.
      3. For I/O jobs, look at the "bursts" of CPU activity.
      4. We could keep a running average of that job in the past: \[\begin{aligned} S_{n+1} =& \frac{1}{n}\sum^n_{i=1}T_i\\ &\text{which can be re-written as}\\ S_{n+1}=& \frac{1}{n} T_n + \frac{n - 1}{n} S_n\\ =&\alpha T_n + (1 - \alpha)S_n\\ \end{aligned} \]
      5. The second version weights all instances equally, but we might wish to weigh more recent runs more, so we can use a tunable parameter to adjust how much each factor weighs.
   10. Shortest Remaining Time - Preemptive version of SPN
   11. Highest Response Ratio Next: \(R = \frac{w + s}{s}\). Short jobs initially favored, but as a job waits, w grows, and the ratio gets larger.
   12. These all assume we know a lot about the future... If we don't, we try to approximate it. Feedback Scheduling - Multiple queues.
       1. Jobs start at the highest priority queue.
       2. if a job does not use entire quantum but blocks (not for I/O), it will be rescheduled on same queue.
       3. If job uses quantum, it is rescheduled on lower priority queue.
       4. If a job blocks for I/O, it is rescheduled on a higher queue.
       5. At the bottom is a round-robin queue.
   13. Performance modeling
       
       
   14. Fair Share - tasks are often made up of several processes, or in the case of linux, individually scheduled threads.
       1. We may want to schedule based on these groups.
       2. Priority of process is sum of base priority + portion of time spent running + portion of time other processes in group spent running.
3. Linux Scheduling
   1. 1.2 Round Robin
   2. 2.2 Separate queues for real-time and batch tasks.
   3. 2.4 \(O(n)\) Epoch- if process doesn't use all its timeslice, the remaining is added to its next timeslice. Each process was evaluated based on priority and history at each switch. Slow.
   4. 2.6 \(O(1)\) Multi-level queue system, complex heuristics to select queue for process.
   5. 2.6.21 "Completely Fair Scheduler" Keep track of processor time. Implement the priority queue with a red-black tree. (WHY!?) Priority is managed by giving higher priority tasks more time on the CPU. It also allocates time on CPU based on group, for fair sharing.