some background on cpu scheduling ====================== resource scheduling vs. resource allocation preemptive vs. non-preemptive cpu scheduling target fair (no starving) throughput latency favor i/o background (remember those classic/old scheduling algorithms? non-preemptive ones, fcfs, shortest-job-first,.. what are the problems?) round-robin priority based linux has 40 static priority. The time slice length varies for different priorities. lottery scheduling target =========================================== adjust relative execution rate (dynamic, responsive, accurate) modular resource management no starvation basic idea ========== lottery ticket, random lottery more tickets => more frequent execution implementation (figure 3) backing tickets active amounts issued tickets exchange rate trust boundary advanced ========= transfer tickets (help address priority inversion, and others) ticket inflation, currency (provide insulation) compensation tickets (support I/O intenstive, interactive applications) it is a mechanism! =========== different application: mutex, memory resource favor i/o, fcfs ... limitation? ========== probablistic (no guarantee, bad for real-time) hard to have absolutely large ones (kernel lock ... :S) other scheduling algorithm ============ unix: rr, fair share micro-economics, multi-level feedback queue linux 2.4 --> 2.6 o(N) --> O(1) scheduling add i/o responsive add support for smp kernel threads are preemptive now