**BVT Scheduling** ================== # 0. Main idea: - each process has: + E: Effective virtual time + A: Actual virtual time - scheduling decision + made very C (context switch allowance, i.e quantum) + choose the one has smallest E - statistic update: (every C - actual real time??? RIGHT) + A = A + k*m, where k is actual time, m is the share proportion + E = A - (warp?W:0) > warp: if warp is enable > W: amount of warp back hence, if warp is on, than the process has higher properties to be selected - limit on the number of time you can warp back # 1. Benefit of BVT scheduling??? - support variety of workload - especially latency-sensitive threads (like streaming video, mp3) - what else??? What is good/bad ------------ - Good: + suppose latency-sensitive threads + parameters can be tweak to deal with various workload + deal with failure of high priority threads + Can control fair share over both SHORT and LONG term ~ short term: if care about low latency dispatch --> warp, and limits ~ long term: weight. - bad: + setting those parameters is like black art + "curse of generality" + how to set the weight, if you have new process run into the system # 2. BVT SCHEDULING # 2.1. WEIGHTED FAIR SHARING NOTE: if Warp Wi = 0, EVT = AVT, decision is based on smallest EVT (hence AVT) - The actual virtual time A: just like the pass in stride scheduling. - mi just like stride - Example: P1 has share 2, P2 has share 1 ==> m1 = 1, m2 = 2 P1 P2 Who runs? 0 0 P1 1 0 P2 1 2 P1 2 2 P1 3 2 P2 ... - Context switch allowance C, typically larger than mcu, is introduce to prevent two compute-bound threads at save AVT from thrashing CPU. + On each AVT update, switch from current thread i to runnable thread j if A(j) <= A(i) - C / wi + Example: P1 and P2 both currently has AVT = 10, P1 run firsts Every timer interrupt, schedule needs update the AVT of current thread, and choose who run next: A(P1) = 11, A(P2) = 10 But A(P2) < 11 - C / 2, for example C = 10, hence P1 is continue to run After a couple of times, The P2 will get run. - What if a thread sleep for a while, then wake up and become runnable? + the thread may monopolize the CPU, since its AVT hasn't increased during the sleeping time. P1 P2 P3 | | | | | | v 10 | | (sleep) | | | | | | | | wake v 90 v 100 10 // at this point, P1 will consume CPU for a while // till its AVT reach that of P2 and P3 + Solution: when wake up, A = max (A, SVT) SVT: scheduler virtual time: minimum AVT of any runnable thread (P2 P3) - What if a thread block during page fault (i.e. involuntarily)? + still consider as part of computation + hence, avoid the problem that a runnable batch losing a portion of its share by taking a page fault immediately after being dispatched. # 2.2 LOW LATENCY DISPATCH - For every thread: E = A - (warp? W: 0) + if warp is enable, and W > 0, than larger W give the thread higher chance to be dispatch + Hence, the higher the warp W, the lower the latency dispatch NOTE: The term latency dispatch confuse me. But in general, dispatch latency is the time when a thread wake up (become runnable), to the time the thread get CPU. - How this work? Look at Figure 3. The Mpeg player pattern is wakeup every 10ms, do some small work, and sleep, and wake up ... + Every time it wake up, its AVT is set to the smallest AVT of all runnable threads. Say if there are 10 threads has the smallest AVT, The mpeg play would have to compete with these threads, hence may need to wait more than 10ms to display a frame... - What if a threads monopolize CPU by tries to run in warped mode for long time? + warp time limit L: ~ thread i is allowed to run warped for at most Li time and, if it attempts to run warped longer, it is then unwarped by the scheduler, which dispatches the new lowest EVT thread + unwarp time requirement U ~ if thread i attempts to warp after having previously warped within Ui, the scheduler runs it unwarped until at least time Ui has passed. The unwarped time is measured from when a thread explicitly unwarps or blocks. ~ The Ui parameter prevents a periodic task from using excessive CPU in the short-term by waking up too frequently ~ See example in Section 2.2 + Hence, when a thread is allow to run in warped mode? ~ L and U are satisfied ~ warp flag is on NOTE: How to set these parameters for every thread in the system? HARD # 2.3 INTERRUPT SERVICE ROUTINES: ??? - live lock problem: interrupt routines blocking out other processing - Solution: give weight, warp, warp limits to interrupt routine. (am i right!) # 2.4 MULTIPROCESSOR SCHEDULING - add a migration penalty M E = A - (warp?W:0) + M - each processor run the earliest EVT thread of ALL the runnable thread - For example + CPU1 looks at the global queue, and choose one with smallest E This process may be in other processor, hence need to add migration cost - How to set M? + small on machines where fast response is critical + larger, on machines where throughput is critical NOTE: for me, setting M is still a black art. It depends on each apps... And how to set this correctly for all apps in the system is hard... # 2.5 MULTILEVEL SCHEDULING: This seems important, but i don't get it ... Damn! After third read: - the idea is like Nucleus, parent in charge of its children + first level scheduler: can control of set of thread + second level scheduler ... + key: each scheduler is assigned a share portion of CPU time, and using that share portion, each allocate it to its threads.s - some what similar to currency in lottery scheduling too. # 4. EXPERIMENT Dealing with infinite loop failure by high priority tasks is interesting: - Say a high priority (low-latency requirement) thread sleep for 99ms, wake up and server 1 seconds. This is given the very high warp and weight. - If there is a bug, or what every, this wakeup every 2ms, without care, this may starve other threads. + however, setting limit U help solve this problem # 6. CONFIGURING BVT Scheduling: - 3 parameters for each thread + CPU share + warp limits + response time Section 6.1.2 Good example about the network input thread - can be set so that it wake up and get dispatched every time a packet arrive - but it may even better to set up some limits, hence, the packets can be batch and process all at once. Response time: using warp value, can mimic priority based scheduler. How? Dig more... + higher priority mean high demand in response time + hence, higher Warp value (true?) Section 6.2.3 Good example on scheduling Google web server - serving short request and long request - provide good response time for short request ... - warp for thread that serve short request - Question: how to identify short response Section 6.3.1 Example on router software: combine of best effort and reserved effort schedulers - 2 level schedulers: + one for realtime (RE) + one for best effort + CPU is assigned based on share/weight Section 6.3.2 MLFQ applied to BVT - goal: setting warp value automatically, guessing which is interactive, which is batch ... - apply the same idea as MLFQ, when ever a process does not use its full time slice ...