source: mainline/src/proc/scheduler.c@ f2ffad4

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since f2ffad4 was f2ffad4, checked in by Jakub Jermar <jakub@…>, 20 years ago

For each architecture, add function/macro FADDR that calculates absolute address of a function referenced by void (* f)(void).
IA-32 and MIPS gcc's use direct addressing (f == FADDR(f)) while IA-64 gcc uses indirect addressing (f != FADDR(f)).

Tweaks in IA-64 Makefile.inc to declare constant gp and main Makefile to consider ASFLAGS when compiling .s targets.
  • Property mode set to 100644
File size: 12.2 KB
Line 
1/*
2 * Copyright (C) 2001-2004 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#include <proc/scheduler.h>
30#include <proc/thread.h>
31#include <proc/task.h>
32#include <cpu.h>
33#include <mm/vm.h>
34#include <config.h>
35#include <context.h>
36#include <func.h>
37#include <arch.h>
38#include <arch/asm.h>
39#include <list.h>
40#include <panic.h>
41#include <typedefs.h>
42#include <mm/page.h>
43#include <synch/spinlock.h>
44#include <arch/faddr.h>
45
46#ifdef __SMP__
47#include <arch/smp/atomic.h>
48#endif /* __SMP__ */
49
50/*
51 * NOTE ON ATOMIC READS:
52 * Some architectures cannot read __u32 atomically.
53 * For that reason, all accesses to nrdy and the likes must be protected by spinlock.
54 */
55
56spinlock_t nrdylock;
57volatile int nrdy;
58
59void before_thread_runs(void)
60{
61 before_thread_runs_arch();
62 fpu_context_restore(&(THREAD->saved_fpu_context));
63}
64
65
66void scheduler_init(void)
67{
68 spinlock_initialize(&nrdylock);
69}
70
71/* cpu_priority_high()'d */
72struct thread *find_best_thread(void)
73{
74 thread_t *t;
75 runq_t *r;
76 int i, n;
77
78loop:
79 cpu_priority_high();
80
81 spinlock_lock(&CPU->lock);
82 n = CPU->nrdy;
83 spinlock_unlock(&CPU->lock);
84
85 cpu_priority_low();
86
87 if (n == 0) {
88 #ifdef __SMP__
89 /*
90 * If the load balancing thread is not running, wake it up and
91 * set CPU-private flag that the kcpulb has been started.
92 */
93 if (test_and_set(&CPU->kcpulbstarted) == 0) {
94 waitq_wakeup(&CPU->kcpulb_wq, 0);
95 goto loop;
96 }
97 #endif /* __SMP__ */
98
99 /*
100 * For there was nothing to run, the CPU goes to sleep
101 * until a hardware interrupt or an IPI comes.
102 * This improves energy saving and hyperthreading.
103 * On the other hand, several hardware interrupts can be ignored.
104 */
105 cpu_sleep();
106 goto loop;
107 }
108
109 cpu_priority_high();
110
111 for (i = 0; i<RQ_COUNT; i++) {
112 r = &CPU->rq[i];
113 spinlock_lock(&r->lock);
114 if (r->n == 0) {
115 /*
116 * If this queue is empty, try a lower-priority queue.
117 */
118 spinlock_unlock(&r->lock);
119 continue;
120 }
121
122 spinlock_lock(&nrdylock);
123 nrdy--;
124 spinlock_unlock(&nrdylock);
125
126 spinlock_lock(&CPU->lock);
127 CPU->nrdy--;
128 spinlock_unlock(&CPU->lock);
129
130 r->n--;
131
132 /*
133 * Take the first thread from the queue.
134 */
135 t = list_get_instance(r->rq_head.next, thread_t, rq_link);
136 list_remove(&t->rq_link);
137
138 spinlock_unlock(&r->lock);
139
140 spinlock_lock(&t->lock);
141 t->cpu = CPU;
142
143 t->ticks = us2ticks((i+1)*10000);
144 t->pri = i; /* eventually correct rq index */
145
146 /*
147 * Clear the X_STOLEN flag so that t can be migrated when load balancing needs emerge.
148 */
149 t->flags &= ~X_STOLEN;
150 spinlock_unlock(&t->lock);
151
152 return t;
153 }
154 goto loop;
155
156}
157
158/*
159 * This function prevents low priority threads from starving in rq's.
160 * When it decides to relink rq's, it reconnects respective pointers
161 * so that in result threads with 'pri' greater or equal 'start' are
162 * moved to a higher-priority queue.
163 */
164void relink_rq(int start)
165{
166 link_t head;
167 runq_t *r;
168 int i, n;
169
170 list_initialize(&head);
171 spinlock_lock(&CPU->lock);
172 if (CPU->needs_relink > NEEDS_RELINK_MAX) {
173 for (i = start; i<RQ_COUNT-1; i++) {
174 /* remember and empty rq[i + 1] */
175 r = &CPU->rq[i + 1];
176 spinlock_lock(&r->lock);
177 list_concat(&head, &r->rq_head);
178 n = r->n;
179 r->n = 0;
180 spinlock_unlock(&r->lock);
181
182 /* append rq[i + 1] to rq[i] */
183 r = &CPU->rq[i];
184 spinlock_lock(&r->lock);
185 list_concat(&r->rq_head, &head);
186 r->n += n;
187 spinlock_unlock(&r->lock);
188 }
189 CPU->needs_relink = 0;
190 }
191 spinlock_unlock(&CPU->lock);
192
193}
194
195/*
196 * The scheduler.
197 */
198void scheduler(void)
199{
200 volatile pri_t pri;
201
202 pri = cpu_priority_high();
203
204 if (haltstate)
205 halt();
206
207 if (THREAD) {
208 spinlock_lock(&THREAD->lock);
209 fpu_context_save(&(THREAD->saved_fpu_context));
210 if (!context_save(&THREAD->saved_context)) {
211 /*
212 * This is the place where threads leave scheduler();
213 */
214 before_thread_runs();
215 spinlock_unlock(&THREAD->lock);
216 cpu_priority_restore(THREAD->saved_context.pri);
217 return;
218 }
219 THREAD->saved_context.pri = pri;
220 }
221
222 /*
223 * We may not keep the old stack.
224 * Reason: If we kept the old stack and got blocked, for instance, in
225 * find_best_thread(), the old thread could get rescheduled by another
226 * CPU and overwrite the part of its own stack that was also used by
227 * the scheduler on this CPU.
228 *
229 * Moreover, we have to bypass the compiler-generated POP sequence
230 * which is fooled by SP being set to the very top of the stack.
231 * Therefore the scheduler() function continues in
232 * scheduler_separated_stack().
233 */
234 context_save(&CPU->saved_context);
235 CPU->saved_context.sp = (__address) &CPU->stack[CPU_STACK_SIZE-8];
236 CPU->saved_context.pc = FADDR(scheduler_separated_stack);
237 context_restore(&CPU->saved_context);
238 /* not reached */
239}
240
241void scheduler_separated_stack(void)
242{
243 int priority;
244
245 if (THREAD) {
246 switch (THREAD->state) {
247 case Running:
248 THREAD->state = Ready;
249 spinlock_unlock(&THREAD->lock);
250 thread_ready(THREAD);
251 break;
252
253 case Exiting:
254 frame_free((__address) THREAD->kstack);
255 if (THREAD->ustack) {
256 frame_free((__address) THREAD->ustack);
257 }
258
259 /*
260 * Detach from the containing task.
261 */
262 spinlock_lock(&TASK->lock);
263 list_remove(&THREAD->th_link);
264 spinlock_unlock(&TASK->lock);
265
266 spinlock_unlock(&THREAD->lock);
267
268 spinlock_lock(&threads_lock);
269 list_remove(&THREAD->threads_link);
270 spinlock_unlock(&threads_lock);
271
272 spinlock_lock(&THREAD->cpu->lock);
273 if(THREAD->cpu->fpu_owner==THREAD) THREAD->cpu->fpu_owner=NULL;
274 spinlock_unlock(&THREAD->cpu->lock);
275
276
277 free(THREAD);
278
279 break;
280
281 case Sleeping:
282 /*
283 * Prefer the thread after it's woken up.
284 */
285 THREAD->pri = -1;
286
287 /*
288 * We need to release wq->lock which we locked in waitq_sleep().
289 * Address of wq->lock is kept in THREAD->sleep_queue.
290 */
291 spinlock_unlock(&THREAD->sleep_queue->lock);
292
293 /*
294 * Check for possible requests for out-of-context invocation.
295 */
296 if (THREAD->call_me) {
297 THREAD->call_me(THREAD->call_me_with);
298 THREAD->call_me = NULL;
299 THREAD->call_me_with = NULL;
300 }
301
302 spinlock_unlock(&THREAD->lock);
303
304 break;
305
306 default:
307 /*
308 * Entering state is unexpected.
309 */
310 panic("tid%d: unexpected state %s\n", THREAD->tid, thread_states[THREAD->state]);
311 break;
312 }
313 THREAD = NULL;
314 }
315
316 THREAD = find_best_thread();
317
318 spinlock_lock(&THREAD->lock);
319 priority = THREAD->pri;
320 spinlock_unlock(&THREAD->lock);
321
322 relink_rq(priority);
323
324 spinlock_lock(&THREAD->lock);
325
326 /*
327 * If both the old and the new task are the same, lots of work is avoided.
328 */
329 if (TASK != THREAD->task) {
330 vm_t *m1 = NULL;
331 vm_t *m2;
332
333 if (TASK) {
334 spinlock_lock(&TASK->lock);
335 m1 = TASK->vm;
336 spinlock_unlock(&TASK->lock);
337 }
338
339 spinlock_lock(&THREAD->task->lock);
340 m2 = THREAD->task->vm;
341 spinlock_unlock(&THREAD->task->lock);
342
343 /*
344 * Note that it is possible for two tasks to share one vm mapping.
345 */
346 if (m1 != m2) {
347 /*
348 * Both tasks and vm mappings are different.
349 * Replace the old one with the new one.
350 */
351 if (m1) {
352 vm_uninstall(m1);
353 }
354 vm_install(m2);
355 }
356 TASK = THREAD->task;
357 }
358
359 THREAD->state = Running;
360
361 #ifdef SCHEDULER_VERBOSE
362 printf("cpu%d: tid %d (pri=%d,ticks=%d,nrdy=%d)\n", CPU->id, THREAD->tid, THREAD->pri, THREAD->ticks, CPU->nrdy);
363 #endif
364
365 context_restore(&THREAD->saved_context);
366 /* not reached */
367}
368
369#ifdef __SMP__
370/*
371 * This is the load balancing thread.
372 * It supervises thread supplies for the CPU it's wired to.
373 */
374void kcpulb(void *arg)
375{
376 thread_t *t;
377 int count, i, j, k = 0;
378 pri_t pri;
379
380loop:
381 /*
382 * Sleep until there's some work to do.
383 */
384 waitq_sleep(&CPU->kcpulb_wq);
385
386not_satisfied:
387 /*
388 * Calculate the number of threads that will be migrated/stolen from
389 * other CPU's. Note that situation can have changed between two
390 * passes. Each time get the most up to date counts.
391 */
392 pri = cpu_priority_high();
393 spinlock_lock(&CPU->lock);
394 count = nrdy / config.cpu_active;
395 count -= CPU->nrdy;
396 spinlock_unlock(&CPU->lock);
397 cpu_priority_restore(pri);
398
399 if (count <= 0)
400 goto satisfied;
401
402 /*
403 * Searching least priority queues on all CPU's first and most priority queues on all CPU's last.
404 */
405 for (j=RQ_COUNT-1; j >= 0; j--) {
406 for (i=0; i < config.cpu_active; i++) {
407 link_t *l;
408 runq_t *r;
409 cpu_t *cpu;
410
411 cpu = &cpus[(i + k) % config.cpu_active];
412 r = &cpu->rq[j];
413
414 /*
415 * Not interested in ourselves.
416 * Doesn't require interrupt disabling for kcpulb is X_WIRED.
417 */
418 if (CPU == cpu)
419 continue;
420
421restart: pri = cpu_priority_high();
422 spinlock_lock(&r->lock);
423 if (r->n == 0) {
424 spinlock_unlock(&r->lock);
425 cpu_priority_restore(pri);
426 continue;
427 }
428
429 t = NULL;
430 l = r->rq_head.prev; /* search rq from the back */
431 while (l != &r->rq_head) {
432 t = list_get_instance(l, thread_t, rq_link);
433 /*
434 * We don't want to steal CPU-wired threads neither threads already stolen.
435 * The latter prevents threads from migrating between CPU's without ever being run.
436 * We don't want to steal threads whose FPU context is still in CPU
437 */
438 spinlock_lock(&t->lock);
439 if ( (!(t->flags & (X_WIRED | X_STOLEN))) && (!(t->fpu_context_engaged)) ) {
440 /*
441 * Remove t from r.
442 */
443
444 spinlock_unlock(&t->lock);
445
446 /*
447 * Here we have to avoid deadlock with relink_rq(),
448 * because it locks cpu and r in a different order than we do.
449 */
450 if (!spinlock_trylock(&cpu->lock)) {
451 /* Release all locks and try again. */
452 spinlock_unlock(&r->lock);
453 cpu_priority_restore(pri);
454 goto restart;
455 }
456 cpu->nrdy--;
457 spinlock_unlock(&cpu->lock);
458
459 spinlock_lock(&nrdylock);
460 nrdy--;
461 spinlock_unlock(&nrdylock);
462
463 r->n--;
464 list_remove(&t->rq_link);
465
466 break;
467 }
468 spinlock_unlock(&t->lock);
469 l = l->prev;
470 t = NULL;
471 }
472 spinlock_unlock(&r->lock);
473
474 if (t) {
475 /*
476 * Ready t on local CPU
477 */
478 spinlock_lock(&t->lock);
479 #ifdef KCPULB_VERBOSE
480 printf("kcpulb%d: TID %d -> cpu%d, nrdy=%d, avg=%d\n", CPU->id, t->tid, CPU->id, CPU->nrdy, nrdy / config.cpu_active);
481 #endif
482 t->flags |= X_STOLEN;
483 spinlock_unlock(&t->lock);
484
485 thread_ready(t);
486
487 cpu_priority_restore(pri);
488
489 if (--count == 0)
490 goto satisfied;
491
492 /*
493 * We are not satisfied yet, focus on another CPU next time.
494 */
495 k++;
496
497 continue;
498 }
499 cpu_priority_restore(pri);
500 }
501 }
502
503 if (CPU->nrdy) {
504 /*
505 * Be a little bit light-weight and let migrated threads run.
506 */
507 scheduler();
508 }
509 else {
510 /*
511 * We failed to migrate a single thread.
512 * Something more sophisticated should be done.
513 */
514 scheduler();
515 }
516
517 goto not_satisfied;
518
519satisfied:
520 /*
521 * Tell find_best_thread() to wake us up later again.
522 */
523 CPU->kcpulbstarted = 0;
524 goto loop;
525}
526
527#endif /* __SMP__ */
Note: See TracBrowser for help on using the repository browser.