source: mainline/kernel/generic/src/proc/scheduler.c@ fbaf6ac

ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since fbaf6ac was fbaf6ac, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 3 years ago

Streamline thread load-balancing
  • Property mode set to 100644
File size: 15.8 KB
Line 
1/*
2 * Copyright (c) 2010 Jakub Jermar
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup kernel_generic_proc
30 * @{
31 */
32
33/**
34 * @file
35 * @brief Scheduler and load balancing.
36 *
37 * This file contains the scheduler and kcpulb kernel thread which
38 * performs load-balancing of per-CPU run queues.
39 */
40
41#include <assert.h>
42#include <atomic.h>
43#include <proc/scheduler.h>
44#include <proc/thread.h>
45#include <proc/task.h>
46#include <mm/frame.h>
47#include <mm/page.h>
48#include <mm/as.h>
49#include <time/timeout.h>
50#include <time/delay.h>
51#include <arch/asm.h>
52#include <arch/faddr.h>
53#include <arch/cycle.h>
54#include <atomic.h>
55#include <synch/spinlock.h>
56#include <config.h>
57#include <context.h>
58#include <fpu_context.h>
59#include <halt.h>
60#include <arch.h>
61#include <adt/list.h>
62#include <panic.h>
63#include <cpu.h>
64#include <stdio.h>
65#include <log.h>
66#include <stacktrace.h>
67
68static void scheduler_separated_stack(void);
69
70atomic_size_t nrdy; /**< Number of ready threads in the system. */
71
72/** Take actions before new thread runs.
73 *
74 * Perform actions that need to be
75 * taken before the newly selected
76 * thread is passed control.
77 *
78 * THREAD->lock is locked on entry
79 *
80 */
81static void before_thread_runs(void)
82{
83 before_thread_runs_arch();
84
85#ifdef CONFIG_FPU_LAZY
86 if (THREAD == CPU->fpu_owner)
87 fpu_enable();
88 else
89 fpu_disable();
90#elif defined CONFIG_FPU
91 fpu_enable();
92 if (THREAD->fpu_context_exists)
93 fpu_context_restore(&THREAD->fpu_context);
94 else {
95 fpu_init();
96 THREAD->fpu_context_exists = true;
97 }
98#endif
99
100#ifdef CONFIG_UDEBUG
101 if (THREAD->btrace) {
102 istate_t *istate = THREAD->udebug.uspace_state;
103 if (istate != NULL) {
104 printf("Thread %" PRIu64 " stack trace:\n", THREAD->tid);
105 stack_trace_istate(istate);
106 }
107
108 THREAD->btrace = false;
109 }
110#endif
111}
112
113/** Take actions after THREAD had run.
114 *
115 * Perform actions that need to be
116 * taken after the running thread
117 * had been preempted by the scheduler.
118 *
119 * THREAD->lock is locked on entry
120 *
121 */
122static void after_thread_ran(void)
123{
124 after_thread_ran_arch();
125}
126
127#ifdef CONFIG_FPU_LAZY
128void scheduler_fpu_lazy_request(void)
129{
130 fpu_enable();
131 irq_spinlock_lock(&CPU->fpu_lock, false);
132
133 /* Save old context */
134 if (CPU->fpu_owner != NULL) {
135 irq_spinlock_lock(&CPU->fpu_owner->lock, false);
136 fpu_context_save(&CPU->fpu_owner->fpu_context);
137
138 /* Don't prevent migration */
139 CPU->fpu_owner->fpu_context_engaged = false;
140 irq_spinlock_unlock(&CPU->fpu_owner->lock, false);
141 CPU->fpu_owner = NULL;
142 }
143
144 irq_spinlock_lock(&THREAD->lock, false);
145 if (THREAD->fpu_context_exists) {
146 fpu_context_restore(&THREAD->fpu_context);
147 } else {
148 fpu_init();
149 THREAD->fpu_context_exists = true;
150 }
151
152 CPU->fpu_owner = THREAD;
153 THREAD->fpu_context_engaged = true;
154 irq_spinlock_unlock(&THREAD->lock, false);
155
156 irq_spinlock_unlock(&CPU->fpu_lock, false);
157}
158#endif /* CONFIG_FPU_LAZY */
159
160/** Initialize scheduler
161 *
162 * Initialize kernel scheduler.
163 *
164 */
165void scheduler_init(void)
166{
167}
168
169/** Get thread to be scheduled
170 *
171 * Get the optimal thread to be scheduled
172 * according to thread accounting and scheduler
173 * policy.
174 *
175 * @return Thread to be scheduled.
176 *
177 */
178static thread_t *find_best_thread(void)
179{
180 assert(CPU != NULL);
181
182loop:
183 if (atomic_load(&CPU->nrdy) == 0) {
184 /*
185 * For there was nothing to run, the CPU goes to sleep
186 * until a hardware interrupt or an IPI comes.
187 * This improves energy saving and hyperthreading.
188 */
189 CPU->idle = true;
190
191 /*
192 * Go to sleep with interrupts enabled.
193 * Ideally, this should be atomic, but this is not guaranteed on
194 * all platforms yet, so it is possible we will go sleep when
195 * a thread has just become available.
196 */
197 cpu_interruptible_sleep();
198
199 /* Interrupts are disabled again. */
200 goto loop;
201 }
202
203 assert(!CPU->idle);
204
205 unsigned int i;
206 for (i = 0; i < RQ_COUNT; i++) {
207 irq_spinlock_lock(&(CPU->rq[i].lock), false);
208 if (CPU->rq[i].n == 0) {
209 /*
210 * If this queue is empty, try a lower-priority queue.
211 */
212 irq_spinlock_unlock(&(CPU->rq[i].lock), false);
213 continue;
214 }
215
216 atomic_dec(&CPU->nrdy);
217 atomic_dec(&nrdy);
218 CPU->rq[i].n--;
219
220 /*
221 * Take the first thread from the queue.
222 */
223 thread_t *thread = list_get_instance(
224 list_first(&CPU->rq[i].rq), thread_t, rq_link);
225 list_remove(&thread->rq_link);
226
227 irq_spinlock_pass(&(CPU->rq[i].lock), &thread->lock);
228
229 thread->cpu = CPU;
230 thread->priority = i; /* Correct rq index */
231
232 /* Time allocation in microseconds. */
233 uint64_t time_to_run = (i + 1) * 10000;
234
235 /* This is safe because interrupts are disabled. */
236 CPU->preempt_deadline = CPU->current_clock_tick + us2ticks(time_to_run);
237
238 /*
239 * Clear the stolen flag so that it can be migrated
240 * when load balancing needs emerge.
241 */
242 thread->stolen = false;
243 irq_spinlock_unlock(&thread->lock, false);
244
245 return thread;
246 }
247
248 goto loop;
249}
250
251static void switch_task(task_t *task)
252{
253 /* If the task stays the same, a lot of work is avoided. */
254 if (TASK == task)
255 return;
256
257 as_t *old_as = AS;
258 as_t *new_as = task->as;
259
260 /* It is possible for two tasks to share one address space. */
261 if (old_as != new_as)
262 as_switch(old_as, new_as);
263
264 if (TASK)
265 task_release(TASK);
266
267 TASK = task;
268
269 task_hold(TASK);
270
271 before_task_runs_arch();
272}
273
274/** Prevent rq starvation
275 *
276 * Prevent low priority threads from starving in rq's.
277 *
278 * When the function decides to relink rq's, it reconnects
279 * respective pointers so that in result threads with 'pri'
280 * greater or equal start are moved to a higher-priority queue.
281 *
282 * @param start Threshold priority.
283 *
284 */
285static void relink_rq(int start)
286{
287 if (CPU->current_clock_tick < CPU->relink_deadline)
288 return;
289
290 CPU->relink_deadline = CPU->current_clock_tick + NEEDS_RELINK_MAX;
291
292 /* Temporary cache for lists we are moving. */
293 list_t list;
294 list_initialize(&list);
295
296 size_t n = 0;
297
298 /* Move every list (except the one with highest priority) one level up. */
299 for (int i = RQ_COUNT - 1; i > start; i--) {
300 irq_spinlock_lock(&CPU->rq[i].lock, false);
301
302 /* Swap lists. */
303 list_swap(&CPU->rq[i].rq, &list);
304
305 /* Swap number of items. */
306 size_t tmpn = CPU->rq[i].n;
307 CPU->rq[i].n = n;
308 n = tmpn;
309
310 irq_spinlock_unlock(&CPU->rq[i].lock, false);
311 }
312
313 /* Append the contents of rq[start + 1] to rq[start]. */
314 if (n != 0) {
315 irq_spinlock_lock(&CPU->rq[start].lock, false);
316 list_concat(&CPU->rq[start].rq, &list);
317 CPU->rq[start].n += n;
318 irq_spinlock_unlock(&CPU->rq[start].lock, false);
319 }
320}
321
322void scheduler(void)
323{
324 ipl_t ipl = interrupts_disable();
325
326 if (atomic_load(&haltstate))
327 halt();
328
329 if (THREAD) {
330 irq_spinlock_lock(&THREAD->lock, false);
331 }
332
333 scheduler_locked(ipl);
334}
335
336/** The scheduler
337 *
338 * The thread scheduling procedure.
339 * Passes control directly to
340 * scheduler_separated_stack().
341 *
342 */
343void scheduler_locked(ipl_t ipl)
344{
345 assert(CPU != NULL);
346
347 if (THREAD) {
348 /* Update thread kernel accounting */
349 THREAD->kcycles += get_cycle() - THREAD->last_cycle;
350
351#if (defined CONFIG_FPU) && (!defined CONFIG_FPU_LAZY)
352 fpu_context_save(&THREAD->fpu_context);
353#endif
354 if (!context_save(&THREAD->saved_context)) {
355 /*
356 * This is the place where threads leave scheduler();
357 */
358
359 /* Save current CPU cycle */
360 THREAD->last_cycle = get_cycle();
361
362 irq_spinlock_unlock(&THREAD->lock, false);
363 interrupts_restore(THREAD->saved_ipl);
364
365 return;
366 }
367
368 /*
369 * Interrupt priority level of preempted thread is recorded
370 * here to facilitate scheduler() invocations from
371 * interrupts_disable()'d code (e.g. waitq_sleep_timeout()).
372 *
373 */
374 THREAD->saved_ipl = ipl;
375 }
376
377 /*
378 * Through the 'CURRENT' structure, we keep track of THREAD, TASK, CPU, AS
379 * and preemption counter. At this point CURRENT could be coming either
380 * from THREAD's or CPU's stack.
381 *
382 */
383 current_copy(CURRENT, (current_t *) CPU->stack);
384
385 /*
386 * We may not keep the old stack.
387 * Reason: If we kept the old stack and got blocked, for instance, in
388 * find_best_thread(), the old thread could get rescheduled by another
389 * CPU and overwrite the part of its own stack that was also used by
390 * the scheduler on this CPU.
391 *
392 * Moreover, we have to bypass the compiler-generated POP sequence
393 * which is fooled by SP being set to the very top of the stack.
394 * Therefore the scheduler() function continues in
395 * scheduler_separated_stack().
396 *
397 */
398 context_t ctx;
399 context_save(&ctx);
400 context_set(&ctx, FADDR(scheduler_separated_stack),
401 (uintptr_t) CPU->stack, STACK_SIZE);
402 context_restore(&ctx);
403
404 /* Not reached */
405}
406
407/** Scheduler stack switch wrapper
408 *
409 * Second part of the scheduler() function
410 * using new stack. Handling the actual context
411 * switch to a new thread.
412 *
413 */
414void scheduler_separated_stack(void)
415{
416 assert((!THREAD) || (irq_spinlock_locked(&THREAD->lock)));
417 assert(CPU != NULL);
418 assert(interrupts_disabled());
419
420 if (THREAD) {
421 /* Must be run after the switch to scheduler stack */
422 after_thread_ran();
423
424 switch (THREAD->state) {
425 case Running:
426 irq_spinlock_unlock(&THREAD->lock, false);
427 thread_ready(THREAD);
428 break;
429
430 case Exiting:
431 irq_spinlock_unlock(&THREAD->lock, false);
432 waitq_close(&THREAD->join_wq);
433
434 /*
435 * Release the reference CPU has for the thread.
436 * If there are no other references (e.g. threads calling join),
437 * the thread structure is deallocated.
438 */
439 thread_put(THREAD);
440 break;
441
442 case Sleeping:
443 /*
444 * Prefer the thread after it's woken up.
445 */
446 THREAD->priority = -1;
447 irq_spinlock_unlock(&THREAD->lock, false);
448 break;
449
450 default:
451 /*
452 * Entering state is unexpected.
453 */
454 panic("tid%" PRIu64 ": unexpected state %s.",
455 THREAD->tid, thread_states[THREAD->state]);
456 break;
457 }
458
459 THREAD = NULL;
460 }
461
462 THREAD = find_best_thread();
463
464 irq_spinlock_lock(&THREAD->lock, false);
465 int priority = THREAD->priority;
466 irq_spinlock_unlock(&THREAD->lock, false);
467
468 relink_rq(priority);
469
470 switch_task(THREAD->task);
471
472 irq_spinlock_lock(&THREAD->lock, false);
473 THREAD->state = Running;
474
475#ifdef SCHEDULER_VERBOSE
476 log(LF_OTHER, LVL_DEBUG,
477 "cpu%u: tid %" PRIu64 " (priority=%d, ticks=%" PRIu64
478 ", nrdy=%zu)", CPU->id, THREAD->tid, THREAD->priority,
479 THREAD->ticks, atomic_load(&CPU->nrdy));
480#endif
481
482 /*
483 * Some architectures provide late kernel PA2KA(identity)
484 * mapping in a page fault handler. However, the page fault
485 * handler uses the kernel stack of the running thread and
486 * therefore cannot be used to map it. The kernel stack, if
487 * necessary, is to be mapped in before_thread_runs(). This
488 * function must be executed before the switch to the new stack.
489 */
490 before_thread_runs();
491
492 /*
493 * Copy the knowledge of CPU, TASK, THREAD and preemption counter to
494 * thread's stack.
495 */
496 current_copy(CURRENT, (current_t *) THREAD->kstack);
497
498 context_restore(&THREAD->saved_context);
499
500 /* Not reached */
501}
502
503#ifdef CONFIG_SMP
504
505static thread_t *steal_thread_from(cpu_t *old_cpu, int i)
506{
507 runq_t *old_rq = &old_cpu->rq[i];
508 runq_t *new_rq = &CPU->rq[i];
509
510 irq_spinlock_lock(&old_rq->lock, true);
511
512 /* Search rq from the back */
513 list_foreach_rev(old_rq->rq, rq_link, thread_t, thread) {
514
515 irq_spinlock_lock(&thread->lock, false);
516
517 /*
518 * Do not steal CPU-wired threads, threads
519 * already stolen, threads for which migration
520 * was temporarily disabled or threads whose
521 * FPU context is still in the CPU.
522 */
523 if (thread->stolen || thread->nomigrate || thread->fpu_context_engaged) {
524 irq_spinlock_unlock(&thread->lock, false);
525 continue;
526 }
527
528 thread->stolen = true;
529 thread->cpu = CPU;
530
531 irq_spinlock_unlock(&thread->lock, false);
532
533 /*
534 * Ready thread on local CPU
535 */
536
537#ifdef KCPULB_VERBOSE
538 log(LF_OTHER, LVL_DEBUG,
539 "kcpulb%u: TID %" PRIu64 " -> cpu%u, "
540 "nrdy=%ld, avg=%ld", CPU->id, thread->tid,
541 CPU->id, atomic_load(&CPU->nrdy),
542 atomic_load(&nrdy) / config.cpu_active);
543#endif
544
545 /* Remove thread from ready queue. */
546 old_rq->n--;
547 list_remove(&thread->rq_link);
548
549 irq_spinlock_pass(&old_rq->lock, &new_rq->lock);
550
551 /* Append thread to local queue. */
552 list_append(&thread->rq_link, &new_rq->rq);
553 new_rq->n++;
554
555 irq_spinlock_unlock(&new_rq->lock, true);
556
557 atomic_dec(&old_cpu->nrdy);
558 atomic_inc(&CPU->nrdy);
559
560 return thread;
561 }
562
563 irq_spinlock_unlock(&old_rq->lock, true);
564 return NULL;
565}
566
567/** Load balancing thread
568 *
569 * SMP load balancing thread, supervising thread supplies
570 * for the CPU it's wired to.
571 *
572 * @param arg Generic thread argument (unused).
573 *
574 */
575void kcpulb(void *arg)
576{
577 size_t average;
578 size_t rdy;
579
580loop:
581 /*
582 * Work in 1s intervals.
583 */
584 thread_sleep(1);
585
586not_satisfied:
587 /*
588 * Calculate the number of threads that will be migrated/stolen from
589 * other CPU's. Note that situation can have changed between two
590 * passes. Each time get the most up to date counts.
591 *
592 */
593 average = atomic_load(&nrdy) / config.cpu_active + 1;
594 rdy = atomic_load(&CPU->nrdy);
595
596 if (average <= rdy)
597 goto satisfied;
598
599 size_t count = average - rdy;
600
601 /*
602 * Searching least priority queues on all CPU's first and most priority
603 * queues on all CPU's last.
604 */
605 size_t acpu;
606 int rq;
607
608 for (rq = RQ_COUNT - 1; rq >= 0; rq--) {
609 for (acpu = 0; acpu < config.cpu_active; acpu++) {
610 cpu_t *cpu = &cpus[acpu];
611
612 /*
613 * Not interested in ourselves.
614 * Doesn't require interrupt disabling for kcpulb has
615 * THREAD_FLAG_WIRED.
616 *
617 */
618 if (CPU == cpu)
619 continue;
620
621 if (atomic_load(&cpu->nrdy) <= average)
622 continue;
623
624 if (steal_thread_from(cpu, rq) && --count == 0)
625 goto satisfied;
626 }
627 }
628
629 if (atomic_load(&CPU->nrdy)) {
630 /*
631 * Be a little bit light-weight and let migrated threads run.
632 *
633 */
634 scheduler();
635 } else {
636 /*
637 * We failed to migrate a single thread.
638 * Give up this turn.
639 *
640 */
641 goto loop;
642 }
643
644 goto not_satisfied;
645
646satisfied:
647 goto loop;
648}
649#endif /* CONFIG_SMP */
650
651/** Print information about threads & scheduler queues
652 *
653 */
654void sched_print_list(void)
655{
656 size_t cpu;
657 for (cpu = 0; cpu < config.cpu_count; cpu++) {
658 if (!cpus[cpu].active)
659 continue;
660
661 /* Technically a data race, but we don't really care in this case. */
662 int needs_relink = cpus[cpu].relink_deadline - cpus[cpu].current_clock_tick;
663
664 printf("cpu%u: address=%p, nrdy=%zu, needs_relink=%d\n",
665 cpus[cpu].id, &cpus[cpu], atomic_load(&cpus[cpu].nrdy),
666 needs_relink);
667
668 unsigned int i;
669 for (i = 0; i < RQ_COUNT; i++) {
670 irq_spinlock_lock(&(cpus[cpu].rq[i].lock), false);
671 if (cpus[cpu].rq[i].n == 0) {
672 irq_spinlock_unlock(&(cpus[cpu].rq[i].lock), false);
673 continue;
674 }
675
676 printf("\trq[%u]: ", i);
677 list_foreach(cpus[cpu].rq[i].rq, rq_link, thread_t,
678 thread) {
679 printf("%" PRIu64 "(%s) ", thread->tid,
680 thread_states[thread->state]);
681 }
682 printf("\n");
683
684 irq_spinlock_unlock(&(cpus[cpu].rq[i].lock), false);
685 }
686 }
687}
688
689/** @}
690 */
Note: See TracBrowser for help on using the repository browser.