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

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

SMP recovery patch #2 (SMP is no longer broken !!!).
Fix missing KA2PA() operation in ap.S which was causing page faults during AP early initialization.
Fix bug in map_page_to_frame(): 'root' was interpretted as kernel address while read_dba() returns physical address.
Make references to page directory and page tables use kernel addresses instead of physical addresses.

Massive frame allocation code cleanup.
Basically revert to what we had had before implementation of userspace.

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