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

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

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