Changes between Version 1 and Version 2 of ClientSched
- Timestamp:
- Apr 25, 2007, 12:47:16 PM (17 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
ClientSched
v1 v2 1 1 = Client scheduling policies = 2 2 3 This document describes three related parts of the BOINC core client: '''CPU scheduling policy''':: 3 This document describes three related parts of the BOINC core client: 4 5 '''CPU scheduling policy''':: 4 6 Of the results that are runnable, which ones to execute? BOINC will generally execute NCPUS results at once, where NCPUS is the minimum of the physical number of CPUs (counting hyperthreading) and the user's 'max_cpus' general preference. 5 7 '''CPU scheduling enforcement''':: … … 7 9 '''Work-fetch policy''':: 8 10 When should the core client ask a project for more work, which project should it ask, and how much work should it ask for? 11 9 12 The goals of these policies are (in descending priority): 10 11 13 12 14 1. Results should be completed and reported by their deadline (because results reported after their deadline may not have any value to the project and may not be granted credit). … … 19 21 In previous versions of BOINC, the core client attempted to maintain at least one result for each attached project, and would do weighted round-robin CPU scheduling among all projects. In some scenarios (any combination of slow computer, lots of projects, and tight deadlines) a computer could miss the deadlines of all its results. The new policies solve this problem as follows: 20 22 21 22 23 * Work fetch is limited to ensure that deadlines can be met. A computer attached to 10 projects might have work for only a few (perhaps only one) at a given time. 23 24 * If deadlines are threatened, the CPU scheduling policy optimizes the likelihood of meeting deadlines, at the expense of variety. 24 25 25 26 26 == Concepts and terms == 27 27 28 28 === Wall CPU time === 29 29 '''Wall CPU time''' is the amount of wall-clock time a process has been runnable at the OS level. The actual CPU time may be less than this, e.g. if the process does a lot of paging, or if other (non-BOINC) processing jobs run at the same time. 30 30 31 31 BOINC uses wall CPU time as the measure of CPU resource usage. Wall CPU time is more fair than actual CPU time in the case of paging apps. In addition, the measurement of actual CPU time depends on apps to report it correctly, and they may not do this. 32 32 33 34 33 === Normalized CPU time === 35 The '''normalized CPU time''' of a result is an estimate of the wall time it will take to complete, taking into account 36 34 The '''normalized CPU time''' of a result is an estimate of the wall time it will take to complete, taking into account 37 35 38 36 * the fraction of time BOINC runs ('on-fraction') … … 40 38 * CPU efficiency (the ratio of actual CPU to wall CPU) 41 39 42 but not taking into account the project's resource share. 40 but not taking into account the project's resource share. 41 43 42 === Project-normalized CPU time === 44 The '''project-normalized CPU time''' of a result is an estimate of the wall time it will take to complete, taking into account the above factors plus the project's resource share relative to other potentially runnable projects. 43 44 The '''project-normalized CPU time''' of a result is an estimate of the wall time it will take to complete, taking into account the above factors plus the project's resource share relative to other potentially runnable projects. 45 45 46 46 The 'work_req' element of a scheduler RPC request is in units of project-normalized CPU time. In deciding how much work to send, the scheduler must take into account the project's resource share fraction, and the host's on-fraction and active-fraction. … … 48 48 For example, suppose a host has 1 GFLOP/sec CPUs, the project's resource share fraction is 0.5, the host's on-fraction is 0.8 and the host's active-fraction is 0.9. Then the expected processing rate per CPU is 49 49 50 51 50 {{{ 52 51 (1 GFLOP/sec)*0.5*0.8*0.9 = 0.36 GFLOP/sec 53 52 }}} 54 If the host requests 1000 project-normalized CPU seconds of work, the scheduler should send it at least 360 GFLOPs of work. 53 54 If the host requests 1000 project-normalized CPU seconds of work, the scheduler should send it at least 360 GFLOPs of work. 55 55 56 === Result states === 56 R is '''runnable''' if 57 58 R is '''runnable''' if 57 59 * Neither R nor R.project is suspended, and 58 60 * R's input files have been downloaded, and 59 61 * R hasn't finished computing 60 62 61 63 R is '''nearly runnable''' if 62 64 * Neither R nor R.project is suspended, and 63 65 * None of R's input files is in a 'download deferred' state. 64 66 * R hasn't finished computing 65 67 66 67 68 === Project states === 68 P is '''runnable''' if 69 70 P is '''runnable''' if 69 71 * P has at least one runnable result (this implies that P is not suspended). 70 72 71 73 P is '''downloading''' if 72 74 * P is not suspended, and 73 75 * P has at least one result whose files are being downloaded and none of the downloads is deferred. 74 76 75 77 P is '''fetchable''' (i.e. the work-fetch policy allows work to be fetched from it) if 76 78 * P is not suspended, and 77 79 * P is not deferred (i.e. its minimum RPC time is in the past), and … … 80 82 * a fetch of P's master file is not pending 81 83 82 84 P is '''latency-limited''' if 83 85 * The client's last scheduler RPC to P returned a 'no work because of deadlines' flag, and 84 86 * the RPC reply's delay request has not yet elapsed. 85 87 86 This means that P has work available, but didn't send any because the work's deadlines couldn't be met given the existing work queue. P is '''potentially runnable''' if 87 88 This means that P has work available, but didn't send any because the work's deadlines couldn't be met given the existing work queue. P is '''potentially runnable''' if 88 89 89 90 * P is either runnable, downloading, fetchable, overworked, or latency-limited. 90 91 91 This means that, to the best of the client's knowledge, it could do work for P if it wanted to. 92 This means that, to the best of the client's knowledge, it could do work for P if it wanted to. 93 92 94 === Debt === 93 Intuitively, a project's 'debt' is how much work is owed to it, relative to other projects. BOINC uses two types of debt; each is defined for a set S of projects. In each case, the debt is recalculated periodically as follows: 95 96 Intuitively, a project's 'debt' is how much work is owed to it, relative to other projects. BOINC uses two types of debt; each is defined for a set S of projects. In each case, the debt is recalculated periodically as follows: 94 97 * A = the wall CPU time used by projects in S during this period 95 98 * R = sum of resource shares of projects in S … … 100 103 * P.debt is normalized so that the mean or minimum is zero. 101 104 102 '''Short-term debt''' is used by the CPU scheduler. It is adjusted over the set of runnable projects. It is normalized so that minimum short-term debt is zero, and maximum short-term debt is no greater than 86,400 (i.e. one day). '''Long-term debt''' is used by the work-fetch policy. It is defined for all projects, and adjusted over the set of potentially runnable projects. It is normalized so that average long-term debt, over all project, is zero. 103 105 '''Short-term debt''' is used by the CPU scheduler. It is adjusted over the set of runnable projects. It is normalized so that minimum short-term debt is zero, and maximum short-term debt is no greater than 86,400 (i.e. one day). 106 107 '''Long-term debt''' is used by the work-fetch policy. It is defined for all projects, and adjusted over the set of potentially runnable projects. It is normalized so that average long-term debt, over all project, is zero. 104 108 105 109 == Round-robin simulation == 106 The CPU scheduling and work fetch policies use the results of a simulation of weighted round-robin scheduling applied to the set of nearly runnable results. The simulation takes into account on-fraction and active-fraction. It produces the following outputs: 107 110 111 The CPU scheduling and work fetch policies use the results of a simulation of weighted round-robin scheduling applied to the set of nearly runnable results. The simulation takes into account on-fraction and active-fraction. It produces the following outputs: 108 112 109 113 * deadline_missed(R): whether result R misses its deadline. … … 114 118 In the example below, projects A and B have resource shares 2 and 1 respectively. A has results A1 and A2, and B has result B1. The computer has two CPUs. From time 0 to 4 all three results run with equal weighting. At time 4 result A2 finishes. From time 4 to 8, project A gets only a 0.5 share because it has only one result. At time 8, result A1 finishes. 115 119 116 In this case, shortfall(A) is 4, shortfall(B) is 0, and total_shortfall is 2. [[Image(http://boinc.berkeley.edu/rr_sim.png)]] 117 120 In this case, shortfall(A) is 4, shortfall(B``) is 0, and total_shortfall is 2. 121 122 [[Image(http://boinc.berkeley.edu/rr_sim.png)]] 118 123 119 124 == CPU scheduling policy == 120 The CPU scheduler uses an earliest-deadline-first (EDF) policy for results that are in danger of missing their deadline, and weighted round-robin among other projects if additional CPUs exist. This allows the client to meet deadlines that would otherwise be missed, while honoring resource shares over the long term. The scheduling policy is: 121 125 126 The CPU scheduler uses an earliest-deadline-first (EDF) policy for results that are in danger of missing their deadline, and weighted round-robin among other projects if additional CPUs exist. This allows the client to meet deadlines that would otherwise be missed, while honoring resource shares over the long term. The scheduling policy is: 122 127 123 128 1. Set the 'anticipated debt' of each project to its short-term debt 124 129 1. Let P be the project with the earliest-deadline runnable result among projects with deadlines_missed(P)>0. Let R be P's earliest-deadline runnable result not scheduled yet. Tiebreaker: least index in result array. 125 1. If such an R exists, schedule R, 130 1. If such an R exists, schedule R, decrement P's anticipated debt, and decrement deadlines_missed(P). 126 131 1. If there are more CPUs, and projects with deadlines_missed(P)>0, go to 1. 127 132 1. If all CPUs are scheduled, stop. 128 1. If there is a result R that is currently running, and has been running for less than the CPU scheduling period,schedule R and go to 5.133 1. If there is a result R that is currently running, and has been running for less than the CPU scheduling period, schedule R and go to 5. 129 134 1. Find the project P with the greatest anticipated debt, select one of P's runnable results (picking one that is already running, if possible, else the one received first from the project) and schedule that result. 130 135 1. Decrement P's anticipated debt by the 'expected payoff' (the scheduling period divided by NCPUS). … … 135 140 136 141 == CPU schedule enforcement == 137 The CPU scheduler decides what results should run, but it doesn't enforce this decision. This enforcement is done by a separate '''scheduler enforcement function''', which is called by the CPU scheduler at its conclusion. Let X be the set of scheduled results that are not currently running, let Y be the set of running results that are not scheduled, and let T be the time the scheduler last ran. The enforcement policy is as follows: 138 142 143 The CPU scheduler decides what results should run, but it doesn't enforce this decision. This enforcement is done by a separate '''scheduler enforcement function''', which is called by the CPU scheduler at its conclusion. Let X be the set of scheduled results that are not currently running, let Y be the set of running results that are not scheduled, and let T be the time the scheduler last ran. The enforcement policy is as follows: 139 144 140 145 1. If deadline_missed(R) for some R in X, then preempt a result in Y, and run R (preempt the result with the least CPU wall time since checkpoint). Repeat as needed. 141 146 1. If there is a result R in Y that checkpointed more recently than T, then preempt R and run a result in X. 142 147 143 144 148 == Work-fetch policy == 145 A project P is '''overworked''' if 146 147 148 * P.long_term_debt This condition occurs if P's results run in EDF mode (and in extreme cases, when a project with large negative LTD is detached). The work-fetch policy avoids getting work from overworked projects. This prevents a situation where a project with short deadlines gets more than its share of CPU time. 149 A project P is '''overworked''' if 150 151 * P.long_term_debt < -sched_period 152 153 This condition occurs if P's results run in EDF mode (and in extreme cases, when a project with large negative LTD is detached). The work-fetch policy avoids getting work from overworked projects. This prevents a situation where a project with short deadlines gets more than its share of CPU time. 149 154 150 155 The work-fetch policy uses the functions 151 156 152 153 157 {{{ 154 158 frs(project P) 155 159 }}} 156 P's fractional resource share among fetchable projects. The work-fetch policy function is called every few minutes (or as needed) by the scheduler RPC polling function. It sets the variable '''P.work_request_size''' for each project P, which is the number of seconds of work to request if we do a scheduler RPC to P. This is computed as follows: 157 160 161 P's fractional resource share among fetchable projects. 162 163 The work-fetch policy function is called every few minutes (or as needed) by the scheduler RPC polling function. It sets the variable '''P.work_request_size''' for each project P, which is the number of seconds of work to request if we do a scheduler RPC to P. This is computed as follows: 158 164 159 165 {{{ … … 181 187 and are proportional to P.resource_share 182 188 }}} 183 For non-CPU-intensive projects, P.work_request_size is set to 1 if P has no nearly-runnable result, otherwise 0. 189 190 For non-CPU-intensive projects, P.work_request_size is set to 1 if P has no nearly-runnable result, otherwise 0. 184 191 185 192 The scheduler RPC mechanism may select a project to contact because of a user request, an outstanding trickle-up message, or a result that is overdue for reporting. If it does so, it will also request work from that project. Otherwise, the RPC mechanism chooses the project P for which 186 187 193 188 194 {{{ … … 190 196 P.long_term_debt + shortfall(P) is greatest 191 197 }}} 192 and requests work from that project. Note: P.work_request_size is in units of normalized CPU time, so the actual work request (which is in units of project-normalized CPU time) is P.work_request_size divided by P's resource share fraction relative to potentially runnable projects. 198 199 and requests work from that project. Note: P.work_request_size is in units of normalized CPU time, so the actual work request (which is in units of project-normalized CPU time) is P.work_request_size divided by P's resource share fraction relative to potentially runnable projects. 200 193 201 ---- 194 202 195 203 == Scheduler work-send policy == 196 NOTE: the following has not been implemented, and is independent of the above policies. 204 205 NOTE: the following has not been implemented, and is independent of the above policies. 197 206 198 207 The scheduler should avoid sending results whose deadlines are likely to be missed, or which are likely to cause existing results to miss their deadlines. This will be accomplished as follows: 199 200 201 * Scheduler requests includes connection period, list of queued result (with estimated time remaining and deadline) and project resource fractions. 202 * The scheduler won't send results whose deadlines are less than now + min_queue. 203 * The scheduler does an EDF simulation of the initial workload to determine by how much each result misses its deadline. For each result R being considered for sending, the scheduler does an EDF simulation. If R meets its deadline and no result misses its deadline by more than it did previously, R is sent. 204 * If the scheduler has work but doesn't send any because of deadline misses, it returns a 'no work because of deadlines' flag. If the last RPC to a project returned this flag, it is marked as latency-limited and accumulates LTD. 205 208 * Scheduler requests includes connection period, list of queued result (with estimated time remaining and deadline) and project resource fractions. 209 * The scheduler won't send results whose deadlines are less than now + min_queue. 210 * The scheduler does an EDF simulation of the initial workload to determine by how much each result misses its deadline. For each result R being considered for sending, the scheduler does an EDF simulation. If R meets its deadline and no result misses its deadline by more than it did previously, R is sent. 211 * If the scheduler has work but doesn't send any because of deadline misses, it returns a 'no work because of deadlines' flag. If the last RPC to a project returned this flag, it is marked as latency-limited and accumulates LTD. 206 212 207 213 ---- 208 214 209 215 == Describing scenarios == 210 We encourage the use of the following notation for describing scheduling scenarios (times are given in hours): 216 217 We encourage the use of the following notation for describing scheduling scenarios (times are given in hours): 211 218 212 219 P(C, D, R) 213 220 214 221 This describes a project with 215 216 222 217 223 * C = CPU time per task … … 219 225 * R = fractional resource share 220 226 221 227 A scenario is described by a list of project, plus the following optional parameters: 222 228 * NCPUS: number of CPUS (default 1) 223 229 * min_queue … … 225 231 * cpu_scheduling_period 226 232 227 233 An example scenario description is: 228 234 {{{ 229 235 P1(1000, 2000, .5) … … 235 241 236 242 === Scenario 1 === 237 238 239 243 240 244 {{{ … … 246 250 cpu_scheduling_period = 1 247 251 }}} 248 Typically one CPU will process 6-minute tasks for P1, and the other CPU will alternate between P2 and P3. It's critical that the scheduler run each task of P2 and P3 for the full CPU scheduling period. If we went strictly by debt, we'd end up switching between them every 6 minutes, and both P2 and P3 would have to resume from a checkpoint each time. For some apps (e.g. Einstein@home) resuming from a checking takes several minutes. So we'd end up wasting most of the time on one CPU. 249 252 253 Typically one CPU will process 6-minute tasks for P1, and the other CPU will alternate between P2 and P3. It's critical that the scheduler run each task of P2 and P3 for the full CPU scheduling period. If we went strictly by debt, we'd end up switching between them every 6 minutes, and both P2 and P3 would have to resume from a checkpoint each time. For some apps (e.g. Einstein@home) resuming from a checking takes several minutes. So we'd end up wasting most of the time on one CPU.
