Creators: Chris St. Jacques, Jose Perez, Thomas Markes

• The part of the OS that manages time and its relation to other resources is called the scheduler.
  • Obviously time is a unique resource because it can’t be accumulated/saved/cached.
  • Tradeoff between high-quality and fast scheduling.
• You can schedule many resources: for now, look at CPU(as a unit).
• No matter how many CPUs you have there are always times when there are too many processes to run.
  • You have this problem regardless of the # of CPUs.
  • We are simplifying the problem by assuming there is only one CPU.
  • We could also use Unix processes.
  • Scheduler decides which one runs now.
• Threads: like processes but stripped down.
  • They have a virtual CPU, but they don’t have file descriptors, signal handling, parent process, etc.
  • Another term for threads is “lightweight processes”.
  • Threads share memory => They are not isolated (this is bad, causes race conditions).
  • Positive-better performance IF done right.

• We trust the threads to help out the scheduler.
• Ex: every now and then, thread will issue a system call (this is often and natural: cat,emacs,etc.).
• Exceptions: lots of computation, programs with bugs
• Exceptions can use yield which is a NOP syscall used only to cooperate with other threads
• Advantage: you get locking for free as long as you do not execute a syscall in a critical section
• The thread that has control is always known and will never be interrupted by an arbitrary timer.
• Vulnerable to uncooperative “vampires” taking over
• Safer than preemptive in the fact that race conditions are less likely
• Single core suitable

• O.S arranges for a timer interrupt (acts like an INT instruction once every 10 ms)
• This takes over the kernel, saves the old context, and then restores context.
• The old context and the one being restored do not necessarily have to be the same (they can be from different threads).
• Doesn’t solve the infinite loop problem, just puts it off
• Uncooperative threads consume resources => manual kill still needed or time limit (SIGXCPU).
• The problem with a time limit is that it is arbitrary and is always wrong (too long or too short), but better than alternative.
• Multicore suitable

• Inverse of threading (no threads)
• Divide your program into small chunks called “callbacks” which are triggered by events.
• Callbacks never block (no waiting just run and exit).
• Instead, callbacks schedule requests and terminate.
• This is an alternative to threading.
• Advantages: Blocking not needed and simple
• Disadvantages: really constrains program and assumes single core
  • Ex: serious computation on Mathematica would require a series of scheduled callbacks

Scheduling n CPUs > n runnable threads
Threads can have other states: zombie, blocked, waiting, timer wait, runnable, etc

What we need:
Policies- choose which threads to run
Mechanisms- low level implementation to make it actually work

• Long term (hours/days)- control admission to system, smart + slow
• Medium term (seconds)- Which processes reside in RAM?
• Short term (ms)- which threads have CPU?, simple + fast

• They’re heuristic.
• They’re hard to fix.

• Fairness – Everybody who wants to run should eventually get a chance
• Maximize throughput/utilization - keep CPU busy!

Average wait time: 3 + 1.5k
Worst case: 8 + 3k
Turnaround is 'Avg runtime' + 'Avg wait time'

Average wait time: 2.25 + 1.5k

(+) SJF always dominates FCFS in average wait time
(-) SJF is unfair: a job might wait forever