Changes in kernel/generic/src/proc/scheduler.c [ec8ef12:bea6233] in mainline
- File:
-
- 1 edited
-
kernel/generic/src/proc/scheduler.c (modified) (14 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/proc/scheduler.c
rec8ef12 rbea6233 70 70 atomic_size_t nrdy; /**< Number of ready threads in the system. */ 71 71 72 /** Carry out actions before new task runs. */ 73 static void before_task_runs(void) 74 { 75 before_task_runs_arch(); 76 } 77 72 78 /** Take actions before new thread runs. 73 79 * … … 84 90 85 91 #ifdef CONFIG_FPU_LAZY 86 /* 87 * The only concurrent modification possible for fpu_owner here is 88 * another thread changing it from itself to NULL in its destructor. 89 */ 90 thread_t *owner = atomic_load_explicit(&CPU->fpu_owner, 91 memory_order_relaxed); 92 93 if (THREAD == owner) 92 if (THREAD == CPU->fpu_owner) 94 93 fpu_enable(); 95 94 else … … 136 135 { 137 136 fpu_enable(); 138 139 /* We need this lock to ensure synchronization with thread destructor. */ 140 irq_spinlock_lock(&CPU->fpu_lock, false); 137 irq_spinlock_lock(&CPU->lock, false); 141 138 142 139 /* Save old context */ 143 thread_t *owner = atomic_load_explicit(&CPU->fpu_owner, memory_order_relaxed); 144 if (owner != NULL) { 145 fpu_context_save(&owner->fpu_context); 146 atomic_store_explicit(&CPU->fpu_owner, NULL, memory_order_relaxed); 147 } 148 149 irq_spinlock_unlock(&CPU->fpu_lock, false); 150 140 if (CPU->fpu_owner != NULL) { 141 irq_spinlock_lock(&CPU->fpu_owner->lock, false); 142 fpu_context_save(&CPU->fpu_owner->fpu_context); 143 144 /* Don't prevent migration */ 145 CPU->fpu_owner->fpu_context_engaged = false; 146 irq_spinlock_unlock(&CPU->fpu_owner->lock, false); 147 CPU->fpu_owner = NULL; 148 } 149 150 irq_spinlock_lock(&THREAD->lock, false); 151 151 if (THREAD->fpu_context_exists) { 152 152 fpu_context_restore(&THREAD->fpu_context); … … 156 156 } 157 157 158 atomic_store_explicit(&CPU->fpu_owner, THREAD, memory_order_relaxed); 158 CPU->fpu_owner = THREAD; 159 THREAD->fpu_context_engaged = true; 160 irq_spinlock_unlock(&THREAD->lock, false); 161 162 irq_spinlock_unlock(&CPU->lock, false); 159 163 } 160 164 #endif /* CONFIG_FPU_LAZY */ … … 178 182 * 179 183 */ 180 static thread_t *try_find_thread(int *rq_index) 181 { 182 assert(interrupts_disabled()); 184 static thread_t *find_best_thread(void) 185 { 183 186 assert(CPU != NULL); 184 187 185 if (atomic_load(&CPU->nrdy) == 0) 186 return NULL; 187 188 for (int i = 0; i < RQ_COUNT; i++) { 188 loop: 189 if (atomic_load(&CPU->nrdy) == 0) { 190 /* 191 * For there was nothing to run, the CPU goes to sleep 192 * until a hardware interrupt or an IPI comes. 193 * This improves energy saving and hyperthreading. 194 */ 195 irq_spinlock_lock(&CPU->lock, false); 196 CPU->idle = true; 197 irq_spinlock_unlock(&CPU->lock, false); 198 199 /* 200 * Go to sleep with interrupts enabled. 201 * Ideally, this should be atomic, but this is not guaranteed on 202 * all platforms yet, so it is possible we will go sleep when 203 * a thread has just become available. 204 */ 205 cpu_interruptible_sleep(); 206 207 /* Interrupts are disabled again. */ 208 goto loop; 209 } 210 211 assert(!CPU->idle); 212 213 unsigned int i; 214 for (i = 0; i < RQ_COUNT; i++) { 189 215 irq_spinlock_lock(&(CPU->rq[i].lock), false); 190 216 if (CPU->rq[i].n == 0) { … … 225 251 irq_spinlock_unlock(&thread->lock, false); 226 252 227 *rq_index = i;228 253 return thread; 229 254 } 230 255 231 return NULL; 232 } 233 234 /** Get thread to be scheduled 235 * 236 * Get the optimal thread to be scheduled 237 * according to thread accounting and scheduler 238 * policy. 239 * 240 * @return Thread to be scheduled. 241 * 242 */ 243 static thread_t *find_best_thread(int *rq_index) 244 { 245 assert(interrupts_disabled()); 246 assert(CPU != NULL); 247 248 while (true) { 249 thread_t *thread = try_find_thread(rq_index); 250 251 if (thread != NULL) 252 return thread; 253 254 /* 255 * For there was nothing to run, the CPU goes to sleep 256 * until a hardware interrupt or an IPI comes. 257 * This improves energy saving and hyperthreading. 258 */ 259 CPU->idle = true; 260 261 /* 262 * Go to sleep with interrupts enabled. 263 * Ideally, this should be atomic, but this is not guaranteed on 264 * all platforms yet, so it is possible we will go sleep when 265 * a thread has just become available. 266 */ 267 cpu_interruptible_sleep(); 268 } 269 } 270 271 static void switch_task(task_t *task) 272 { 273 /* If the task stays the same, a lot of work is avoided. */ 274 if (TASK == task) 275 return; 276 277 as_t *old_as = AS; 278 as_t *new_as = task->as; 279 280 /* It is possible for two tasks to share one address space. */ 281 if (old_as != new_as) 282 as_switch(old_as, new_as); 283 284 if (TASK) 285 task_release(TASK); 286 287 TASK = task; 288 289 task_hold(TASK); 290 291 before_task_runs_arch(); 256 goto loop; 292 257 } 293 258 … … 310 275 CPU->relink_deadline = CPU->current_clock_tick + NEEDS_RELINK_MAX; 311 276 312 /* Temporary cache for lists we are moving. */313 277 list_t list; 314 278 list_initialize(&list); 315 279 316 size_t n = 0; 317 318 /* Move every list (except the one with highest priority) one level up. */ 319 for (int i = RQ_COUNT - 1; i > start; i--) { 280 irq_spinlock_lock(&CPU->lock, false); 281 282 for (int i = start; i < RQ_COUNT - 1; i++) { 283 /* Remember and empty rq[i + 1] */ 284 285 irq_spinlock_lock(&CPU->rq[i + 1].lock, false); 286 list_concat(&list, &CPU->rq[i + 1].rq); 287 size_t n = CPU->rq[i + 1].n; 288 CPU->rq[i + 1].n = 0; 289 irq_spinlock_unlock(&CPU->rq[i + 1].lock, false); 290 291 /* Append rq[i + 1] to rq[i] */ 292 320 293 irq_spinlock_lock(&CPU->rq[i].lock, false); 321 322 /* Swap lists. */ 323 list_swap(&CPU->rq[i].rq, &list); 324 325 /* Swap number of items. */ 326 size_t tmpn = CPU->rq[i].n; 327 CPU->rq[i].n = n; 328 n = tmpn; 329 294 list_concat(&CPU->rq[i].rq, &list); 295 CPU->rq[i].n += n; 330 296 irq_spinlock_unlock(&CPU->rq[i].lock, false); 331 297 } 332 298 333 /* Append the contents of rq[start + 1] to rq[start]. */ 334 if (n != 0) { 335 irq_spinlock_lock(&CPU->rq[start].lock, false); 336 list_concat(&CPU->rq[start].rq, &list); 337 CPU->rq[start].n += n; 338 irq_spinlock_unlock(&CPU->rq[start].lock, false); 339 } 299 irq_spinlock_unlock(&CPU->lock, false); 340 300 } 341 301 … … 434 394 void scheduler_separated_stack(void) 435 395 { 396 task_t *old_task = TASK; 397 as_t *old_as = AS; 398 436 399 assert((!THREAD) || (irq_spinlock_locked(&THREAD->lock))); 437 400 assert(CPU != NULL); 438 401 assert(interrupts_disabled()); 402 403 /* 404 * Hold the current task and the address space to prevent their 405 * possible destruction should thread_destroy() be called on this or any 406 * other processor while the scheduler is still using them. 407 */ 408 if (old_task) 409 task_hold(old_task); 410 411 if (old_as) 412 as_hold(old_as); 439 413 440 414 if (THREAD) { … … 480 454 } 481 455 482 int rq_index; 483 THREAD = find_best_thread(&rq_index); 484 485 relink_rq(rq_index); 486 487 switch_task(THREAD->task); 456 THREAD = find_best_thread(); 457 458 irq_spinlock_lock(&THREAD->lock, false); 459 int priority = THREAD->priority; 460 irq_spinlock_unlock(&THREAD->lock, false); 461 462 relink_rq(priority); 463 464 /* 465 * If both the old and the new task are the same, 466 * lots of work is avoided. 467 */ 468 if (TASK != THREAD->task) { 469 as_t *new_as = THREAD->task->as; 470 471 /* 472 * Note that it is possible for two tasks 473 * to share one address space. 474 */ 475 if (old_as != new_as) { 476 /* 477 * Both tasks and address spaces are different. 478 * Replace the old one with the new one. 479 */ 480 as_switch(old_as, new_as); 481 } 482 483 TASK = THREAD->task; 484 before_task_runs(); 485 } 486 487 if (old_task) 488 task_release(old_task); 489 490 if (old_as) 491 as_release(old_as); 488 492 489 493 irq_spinlock_lock(&THREAD->lock, false); … … 519 523 520 524 #ifdef CONFIG_SMP 521 522 static thread_t *steal_thread_from(cpu_t *old_cpu, int i)523 {524 runq_t *old_rq = &old_cpu->rq[i];525 runq_t *new_rq = &CPU->rq[i];526 527 ipl_t ipl = interrupts_disable();528 529 irq_spinlock_lock(&old_rq->lock, false);530 531 /*532 * If fpu_owner is any thread in the list, its store is seen here thanks to533 * the runqueue lock.534 */535 thread_t *fpu_owner = atomic_load_explicit(&old_cpu->fpu_owner,536 memory_order_relaxed);537 538 /* Search rq from the back */539 list_foreach_rev(old_rq->rq, rq_link, thread_t, thread) {540 541 irq_spinlock_lock(&thread->lock, false);542 543 /*544 * Do not steal CPU-wired threads, threads545 * already stolen, threads for which migration546 * was temporarily disabled or threads whose547 * FPU context is still in the CPU.548 */549 if (thread->stolen || thread->nomigrate ||550 thread == fpu_owner) {551 irq_spinlock_unlock(&thread->lock, false);552 continue;553 }554 555 thread->stolen = true;556 thread->cpu = CPU;557 558 irq_spinlock_unlock(&thread->lock, false);559 560 /*561 * Ready thread on local CPU562 */563 564 #ifdef KCPULB_VERBOSE565 log(LF_OTHER, LVL_DEBUG,566 "kcpulb%u: TID %" PRIu64 " -> cpu%u, "567 "nrdy=%ld, avg=%ld", CPU->id, thread->tid,568 CPU->id, atomic_load(&CPU->nrdy),569 atomic_load(&nrdy) / config.cpu_active);570 #endif571 572 /* Remove thread from ready queue. */573 old_rq->n--;574 list_remove(&thread->rq_link);575 irq_spinlock_unlock(&old_rq->lock, false);576 577 /* Append thread to local queue. */578 irq_spinlock_lock(&new_rq->lock, false);579 list_append(&thread->rq_link, &new_rq->rq);580 new_rq->n++;581 irq_spinlock_unlock(&new_rq->lock, false);582 583 atomic_dec(&old_cpu->nrdy);584 atomic_inc(&CPU->nrdy);585 interrupts_restore(ipl);586 return thread;587 }588 589 irq_spinlock_unlock(&old_rq->lock, false);590 interrupts_restore(ipl);591 return NULL;592 }593 594 525 /** Load balancing thread 595 526 * … … 631 562 */ 632 563 size_t acpu; 564 size_t acpu_bias = 0; 633 565 int rq; 634 566 635 567 for (rq = RQ_COUNT - 1; rq >= 0; rq--) { 636 568 for (acpu = 0; acpu < config.cpu_active; acpu++) { 637 cpu_t *cpu = &cpus[ acpu];569 cpu_t *cpu = &cpus[(acpu + acpu_bias) % config.cpu_active]; 638 570 639 571 /* … … 649 581 continue; 650 582 651 if (steal_thread_from(cpu, rq) && --count == 0) 652 goto satisfied; 583 irq_spinlock_lock(&(cpu->rq[rq].lock), true); 584 if (cpu->rq[rq].n == 0) { 585 irq_spinlock_unlock(&(cpu->rq[rq].lock), true); 586 continue; 587 } 588 589 thread_t *thread = NULL; 590 591 /* Search rq from the back */ 592 link_t *link = list_last(&cpu->rq[rq].rq); 593 594 while (link != NULL) { 595 thread = (thread_t *) list_get_instance(link, 596 thread_t, rq_link); 597 598 /* 599 * Do not steal CPU-wired threads, threads 600 * already stolen, threads for which migration 601 * was temporarily disabled or threads whose 602 * FPU context is still in the CPU. 603 */ 604 irq_spinlock_lock(&thread->lock, false); 605 606 if ((!thread->wired) && (!thread->stolen) && 607 (!thread->nomigrate) && 608 (!thread->fpu_context_engaged)) { 609 /* 610 * Remove thread from ready queue. 611 */ 612 irq_spinlock_unlock(&thread->lock, 613 false); 614 615 atomic_dec(&cpu->nrdy); 616 atomic_dec(&nrdy); 617 618 cpu->rq[rq].n--; 619 list_remove(&thread->rq_link); 620 621 break; 622 } 623 624 irq_spinlock_unlock(&thread->lock, false); 625 626 link = list_prev(link, &cpu->rq[rq].rq); 627 thread = NULL; 628 } 629 630 if (thread) { 631 /* 632 * Ready thread on local CPU 633 */ 634 635 irq_spinlock_pass(&(cpu->rq[rq].lock), 636 &thread->lock); 637 638 #ifdef KCPULB_VERBOSE 639 log(LF_OTHER, LVL_DEBUG, 640 "kcpulb%u: TID %" PRIu64 " -> cpu%u, " 641 "nrdy=%ld, avg=%ld", CPU->id, thread->tid, 642 CPU->id, atomic_load(&CPU->nrdy), 643 atomic_load(&nrdy) / config.cpu_active); 644 #endif 645 646 thread->stolen = true; 647 thread->state = Entering; 648 649 irq_spinlock_unlock(&thread->lock, true); 650 thread_ready(thread); 651 652 if (--count == 0) 653 goto satisfied; 654 655 /* 656 * We are not satisfied yet, focus on another 657 * CPU next time. 658 * 659 */ 660 acpu_bias++; 661 662 continue; 663 } else 664 irq_spinlock_unlock(&(cpu->rq[rq].lock), true); 665 653 666 } 654 667 } … … 686 699 continue; 687 700 701 irq_spinlock_lock(&cpus[cpu].lock, true); 702 688 703 /* Technically a data race, but we don't really care in this case. */ 689 704 int needs_relink = cpus[cpu].relink_deadline - cpus[cpu].current_clock_tick; … … 711 726 irq_spinlock_unlock(&(cpus[cpu].rq[i].lock), false); 712 727 } 728 729 irq_spinlock_unlock(&cpus[cpu].lock, true); 713 730 } 714 731 }
Note:
See TracChangeset
for help on using the changeset viewer.
