Changes in kernel/generic/src/proc/scheduler.c [bea6233:ec8ef12] in mainline
- File:
-
- 1 edited
-
kernel/generic/src/proc/scheduler.c (modified) (14 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/proc/scheduler.c
rbea6233 rec8ef12 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 78 72 /** Take actions before new thread runs. 79 73 * … … 90 84 91 85 #ifdef CONFIG_FPU_LAZY 92 if (THREAD == CPU->fpu_owner) 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) 93 94 fpu_enable(); 94 95 else … … 135 136 { 136 137 fpu_enable(); 137 irq_spinlock_lock(&CPU->lock, false); 138 139 /* We need this lock to ensure synchronization with thread destructor. */ 140 irq_spinlock_lock(&CPU->fpu_lock, false); 138 141 139 142 /* Save old context */ 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); 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 151 151 if (THREAD->fpu_context_exists) { 152 152 fpu_context_restore(&THREAD->fpu_context); … … 156 156 } 157 157 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); 158 atomic_store_explicit(&CPU->fpu_owner, THREAD, memory_order_relaxed); 163 159 } 164 160 #endif /* CONFIG_FPU_LAZY */ … … 182 178 * 183 179 */ 184 static thread_t *find_best_thread(void) 185 { 180 static thread_t *try_find_thread(int *rq_index) 181 { 182 assert(interrupts_disabled()); 186 183 assert(CPU != NULL); 187 184 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++) { 185 if (atomic_load(&CPU->nrdy) == 0) 186 return NULL; 187 188 for (int i = 0; i < RQ_COUNT; i++) { 215 189 irq_spinlock_lock(&(CPU->rq[i].lock), false); 216 190 if (CPU->rq[i].n == 0) { … … 251 225 irq_spinlock_unlock(&thread->lock, false); 252 226 227 *rq_index = i; 253 228 return thread; 254 229 } 255 230 256 goto loop; 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(); 257 292 } 258 293 … … 275 310 CPU->relink_deadline = CPU->current_clock_tick + NEEDS_RELINK_MAX; 276 311 312 /* Temporary cache for lists we are moving. */ 277 313 list_t list; 278 314 list_initialize(&list); 279 315 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 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--) { 293 320 irq_spinlock_lock(&CPU->rq[i].lock, false); 294 list_concat(&CPU->rq[i].rq, &list); 295 CPU->rq[i].n += n; 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 296 330 irq_spinlock_unlock(&CPU->rq[i].lock, false); 297 331 } 298 332 299 irq_spinlock_unlock(&CPU->lock, false); 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 } 300 340 } 301 341 … … 394 434 void scheduler_separated_stack(void) 395 435 { 396 task_t *old_task = TASK;397 as_t *old_as = AS;398 399 436 assert((!THREAD) || (irq_spinlock_locked(&THREAD->lock))); 400 437 assert(CPU != NULL); 401 438 assert(interrupts_disabled()); 402 403 /*404 * Hold the current task and the address space to prevent their405 * possible destruction should thread_destroy() be called on this or any406 * 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);413 439 414 440 if (THREAD) { … … 454 480 } 455 481 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); 482 int rq_index; 483 THREAD = find_best_thread(&rq_index); 484 485 relink_rq(rq_index); 486 487 switch_task(THREAD->task); 492 488 493 489 irq_spinlock_lock(&THREAD->lock, false); … … 523 519 524 520 #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 to 533 * 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, threads 545 * already stolen, threads for which migration 546 * was temporarily disabled or threads whose 547 * 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 CPU 562 */ 563 564 #ifdef KCPULB_VERBOSE 565 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 #endif 571 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 525 594 /** Load balancing thread 526 595 * … … 562 631 */ 563 632 size_t acpu; 564 size_t acpu_bias = 0;565 633 int rq; 566 634 567 635 for (rq = RQ_COUNT - 1; rq >= 0; rq--) { 568 636 for (acpu = 0; acpu < config.cpu_active; acpu++) { 569 cpu_t *cpu = &cpus[ (acpu + acpu_bias) % config.cpu_active];637 cpu_t *cpu = &cpus[acpu]; 570 638 571 639 /* … … 581 649 continue; 582 650 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 651 if (steal_thread_from(cpu, rq) && --count == 0) 652 goto satisfied; 666 653 } 667 654 } … … 698 685 if (!cpus[cpu].active) 699 686 continue; 700 701 irq_spinlock_lock(&cpus[cpu].lock, true);702 687 703 688 /* Technically a data race, but we don't really care in this case. */ … … 726 711 irq_spinlock_unlock(&(cpus[cpu].rq[i].lock), false); 727 712 } 728 729 irq_spinlock_unlock(&cpus[cpu].lock, true);730 713 } 731 714 }
Note:
See TracChangeset
for help on using the changeset viewer.
