![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to sched_prim.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GnuMach] / Gnu-Mach / kern|
Return to sched_prim.c CVS log | Up to [GnuMach] / Gnu-Mach / kern |
1.1 root 1: /*
2: * Mach Operating System
3: * Copyright (c) 1993-1987 Carnegie Mellon University
4: * All Rights Reserved.
5: *
6: * Permission to use, copy, modify and distribute this software and its
7: * documentation is hereby granted, provided that both the copyright
8: * notice and this permission notice appear in all copies of the
9: * software, derivative works or modified versions, and any portions
10: * thereof, and that both notices appear in supporting documentation.
11: *
12: * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
13: * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
14: * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
15: *
16: * Carnegie Mellon requests users of this software to return to
17: *
18: * Software Distribution Coordinator or [email protected]
19: * School of Computer Science
20: * Carnegie Mellon University
21: * Pittsburgh PA 15213-3890
22: *
23: * any improvements or extensions that they make and grant Carnegie Mellon
24: * the rights to redistribute these changes.
25: */
26: /*
27: * File: sched_prim.c
28: * Author: Avadis Tevanian, Jr.
29: * Date: 1986
30: *
31: * Scheduling primitives
32: *
33: */
34:
35: #include <cpus.h>
36: #include <simple_clock.h>
37: #include <mach_fixpri.h>
38: #include <mach_host.h>
39: #include <hw_footprint.h>
40: #include <fast_tas.h>
41: #include <power_save.h>
42:
43: #include <mach/machine.h>
44: #include <kern/ast.h>
45: #include <kern/counters.h>
46: #include <kern/cpu_number.h>
47: #include <kern/lock.h>
48: #include <kern/macro_help.h>
49: #include <kern/processor.h>
50: #include <kern/queue.h>
51: #include <kern/sched.h>
52: #include <kern/sched_prim.h>
53: #include <kern/syscall_subr.h>
54: #include <kern/thread.h>
55: #include <kern/thread_swap.h>
56: #include <kern/time_out.h>
57: #include <vm/pmap.h>
58: #include <vm/vm_kern.h>
59: #include <vm/vm_map.h>
60: #include <machine/machspl.h> /* For def'n of splsched() */
61:
62: #if MACH_FIXPRI
63: #include <mach/policy.h>
64: #endif /* MACH_FIXPRI */
65:
66:
67: extern int hz;
68:
69: int min_quantum; /* defines max context switch rate */
70:
71: unsigned sched_tick;
72:
73: #if SIMPLE_CLOCK
74: int sched_usec;
75: #endif /* SIMPLE_CLOCK */
76:
77: thread_t sched_thread_id;
78:
79: void recompute_priorities(void); /* forward */
80: void update_priority(thread_t);
81: void set_pri(thread_t, int, boolean_t);
82: void do_thread_scan(void);
83:
84: thread_t choose_pset_thread();
85:
86: timer_elt_data_t recompute_priorities_timer;
87:
88: #if DEBUG
89: void checkrq(run_queue_t, char *);
90: void thread_check(thread_t, run_queue_t);
91: #endif
92:
93: /*
94: * State machine
95: *
96: * states are combinations of:
97: * R running
98: * W waiting (or on wait queue)
99: * S suspended (or will suspend)
100: * N non-interruptible
101: *
102: * init action
103: * assert_wait thread_block clear_wait suspend resume
104: *
105: * R RW, RWN R; setrun - RS -
106: * RS RWS, RWNS S; wake_active - - R
107: * RN RWN RN; setrun - RNS -
108: * RNS RWNS RNS; setrun - - RN
109: *
110: * RW W R RWS -
111: * RWN WN RN RWNS -
112: * RWS WS; wake_active RS - RW
113: * RWNS WNS RNS - RWN
114: *
115: * W R; setrun WS -
116: * WN RN; setrun WNS -
117: * WNS RNS; setrun - WN
118: *
119: * S - - R
120: * WS S - W
121: *
122: */
123:
124: /*
125: * Waiting protocols and implementation:
126: *
127: * Each thread may be waiting for exactly one event; this event
128: * is set using assert_wait(). That thread may be awakened either
129: * by performing a thread_wakeup_prim() on its event,
130: * or by directly waking that thread up with clear_wait().
131: *
132: * The implementation of wait events uses a hash table. Each
133: * bucket is queue of threads having the same hash function
134: * value; the chain for the queue (linked list) is the run queue
135: * field. [It is not possible to be waiting and runnable at the
136: * same time.]
137: *
138: * Locks on both the thread and on the hash buckets govern the
139: * wait event field and the queue chain field. Because wakeup
140: * operations only have the event as an argument, the event hash
141: * bucket must be locked before any thread.
142: *
143: * Scheduling operations may also occur at interrupt level; therefore,
144: * interrupts below splsched() must be prevented when holding
145: * thread or hash bucket locks.
146: *
147: * The wait event hash table declarations are as follows:
148: */
149:
150: #define NUMQUEUES 59
151:
152: queue_head_t wait_queue[NUMQUEUES];
153: decl_simple_lock_data(, wait_lock[NUMQUEUES])
154:
155: /* NOTE: we want a small positive integer out of this */
156: #define wait_hash(event) \
157: ((((int)(event) < 0) ? ~(int)(event) : (int)(event)) % NUMQUEUES)
158:
159: void wait_queue_init(void)
160: {
161: register int i;
162:
163: for (i = 0; i < NUMQUEUES; i++) {
164: queue_init(&wait_queue[i]);
165: simple_lock_init(&wait_lock[i]);
166: }
167: }
168:
169: void sched_init(void)
170: {
171: recompute_priorities_timer.fcn = (int (*)())recompute_priorities;
172: recompute_priorities_timer.param = (char *)0;
173:
174: min_quantum = hz / 10; /* context switch 10 times/second */
175: wait_queue_init();
176: pset_sys_bootstrap(); /* initialize processer mgmt. */
177: queue_init(&action_queue);
178: simple_lock_init(&action_lock);
179: sched_tick = 0;
180: #if SIMPLE_CLOCK
181: sched_usec = 0;
182: #endif /* SIMPLE_CLOCK */
183: ast_init();
184: }
185:
186: /*
187: * Thread timeout routine, called when timer expires.
188: * Called at splsoftclock.
189: */
190: void thread_timeout(
191: thread_t thread)
192: {
193: assert(thread->timer.set == TELT_UNSET);
194:
195: clear_wait(thread, THREAD_TIMED_OUT, FALSE);
196: }
197:
198: /*
199: * thread_set_timeout:
200: *
201: * Set a timer for the current thread, if the thread
202: * is ready to wait. Must be called between assert_wait()
203: * and thread_block().
204: */
205:
206: void thread_set_timeout(
207: int t) /* timeout interval in ticks */
208: {
209: register thread_t thread = current_thread();
210: register spl_t s;
211:
212: s = splsched();
213: thread_lock(thread);
214: if ((thread->state & TH_WAIT) != 0) {
215: set_timeout(&thread->timer, t);
216: }
217: thread_unlock(thread);
218: splx(s);
219: }
220:
221: /*
222: * Set up thread timeout element when thread is created.
223: */
224: void thread_timeout_setup(
225: register thread_t thread)
226: {
227: thread->timer.fcn = (int (*)())thread_timeout;
228: thread->timer.param = (char *)thread;
229: thread->depress_timer.fcn = (int (*)())thread_depress_timeout;
230: thread->depress_timer.param = (char *)thread;
231: }
232:
233: /*
234: * assert_wait:
235: *
236: * Assert that the current thread is about to go to
237: * sleep until the specified event occurs.
238: */
239: void assert_wait(
240: event_t event,
241: boolean_t interruptible)
242: {
243: register queue_t q;
244: register int index;
245: register thread_t thread;
246: #if MACH_SLOCKS
247: register simple_lock_t lock;
248: #endif /* MACH_SLOCKS */
249: spl_t s;
250:
251: thread = current_thread();
252: if (thread->wait_event != 0) {
253: panic("assert_wait: already asserted event %#x\n",
254: thread->wait_event);
255: }
256: s = splsched();
257: if (event != 0) {
258: index = wait_hash(event);
259: q = &wait_queue[index];
260: #if MACH_SLOCKS
261: lock = &wait_lock[index];
262: #endif /* MACH_SLOCKS */
263: simple_lock(lock);
264: thread_lock(thread);
265: enqueue_tail(q, (queue_entry_t) thread);
266: thread->wait_event = event;
267: if (interruptible)
268: thread->state |= TH_WAIT;
269: else
270: thread->state |= TH_WAIT | TH_UNINT;
271: thread_unlock(thread);
272: simple_unlock(lock);
273: }
274: else {
275: thread_lock(thread);
276: if (interruptible)
277: thread->state |= TH_WAIT;
278: else
279: thread->state |= TH_WAIT | TH_UNINT;
280: thread_unlock(thread);
281: }
282: splx(s);
283: }
284:
285: /*
286: * clear_wait:
287: *
288: * Clear the wait condition for the specified thread. Start the thread
289: * executing if that is appropriate.
290: *
291: * parameters:
292: * thread thread to awaken
293: * result Wakeup result the thread should see
294: * interrupt_only Don't wake up the thread if it isn't
295: * interruptible.
296: */
297: void clear_wait(
298: register thread_t thread,
299: int result,
300: boolean_t interrupt_only)
301: {
302: register int index;
303: register queue_t q;
304: #if MACH_SLOCKS
305: register simple_lock_t lock;
306: #endif /* MACH_SLOCKS */
307: register event_t event;
308: spl_t s;
309:
310: s = splsched();
311: thread_lock(thread);
312: if (interrupt_only && (thread->state & TH_UNINT)) {
313: /*
314: * can`t interrupt thread
315: */
316: thread_unlock(thread);
317: splx(s);
318: return;
319: }
320:
321: event = thread->wait_event;
322: if (event != 0) {
323: thread_unlock(thread);
324: index = wait_hash(event);
325: q = &wait_queue[index];
326: #if MACH_SLOCKS
327: lock = &wait_lock[index];
328: #endif /* MACH_SLOCKS */
329: simple_lock(lock);
330: /*
331: * If the thread is still waiting on that event,
332: * then remove it from the list. If it is waiting
333: * on a different event, or no event at all, then
334: * someone else did our job for us.
335: */
336: thread_lock(thread);
337: if (thread->wait_event == event) {
338: remqueue(q, (queue_entry_t)thread);
339: thread->wait_event = 0;
340: event = 0; /* cause to run below */
341: }
342: simple_unlock(lock);
343: }
344: if (event == 0) {
345: register int state = thread->state;
346:
347: reset_timeout_check(&thread->timer);
348:
349: switch (state & TH_SCHED_STATE) {
350: case TH_WAIT | TH_SUSP | TH_UNINT:
351: case TH_WAIT | TH_UNINT:
352: case TH_WAIT:
353: /*
354: * Sleeping and not suspendable - put
355: * on run queue.
356: */
357: thread->state = (state &~ TH_WAIT) | TH_RUN;
358: thread->wait_result = result;
359: thread_setrun(thread, TRUE);
360: break;
361:
362: case TH_WAIT | TH_SUSP:
363: case TH_RUN | TH_WAIT:
364: case TH_RUN | TH_WAIT | TH_SUSP:
365: case TH_RUN | TH_WAIT | TH_UNINT:
366: case TH_RUN | TH_WAIT | TH_SUSP | TH_UNINT:
367: /*
368: * Either already running, or suspended.
369: */
370: thread->state = state &~ TH_WAIT;
371: thread->wait_result = result;
372: break;
373:
374: default:
375: /*
376: * Not waiting.
377: */
378: break;
379: }
380: }
381: thread_unlock(thread);
382: splx(s);
383: }
384:
385: /*
386: * thread_wakeup_prim:
387: *
388: * Common routine for thread_wakeup, thread_wakeup_with_result,
389: * and thread_wakeup_one.
390: *
391: */
392: void thread_wakeup_prim(
393: event_t event,
394: boolean_t one_thread,
395: int result)
396: {
397: register queue_t q;
398: register int index;
399: register thread_t thread, next_th;
400: #if MACH_SLOCKS
401: register simple_lock_t lock;
402: #endif /* MACH_SLOCKS */
403: spl_t s;
404: register int state;
405:
406: index = wait_hash(event);
407: q = &wait_queue[index];
408: s = splsched();
409: #if MACH_SLOCKS
410: lock = &wait_lock[index];
411: #endif /* MACH_SLOCKS */
412: simple_lock(lock);
413: thread = (thread_t) queue_first(q);
414: while (!queue_end(q, (queue_entry_t)thread)) {
415: next_th = (thread_t) queue_next((queue_t) thread);
416:
417: if (thread->wait_event == event) {
418: thread_lock(thread);
419: remqueue(q, (queue_entry_t) thread);
420: thread->wait_event = 0;
421: reset_timeout_check(&thread->timer);
422:
423: state = thread->state;
424: switch (state & TH_SCHED_STATE) {
425:
426: case TH_WAIT | TH_SUSP | TH_UNINT:
427: case TH_WAIT | TH_UNINT:
428: case TH_WAIT:
429: /*
430: * Sleeping and not suspendable - put
431: * on run queue.
432: */
433: thread->state = (state &~ TH_WAIT) | TH_RUN;
434: thread->wait_result = result;
435: thread_setrun(thread, TRUE);
436: break;
437:
438: case TH_WAIT | TH_SUSP:
439: case TH_RUN | TH_WAIT:
440: case TH_RUN | TH_WAIT | TH_SUSP:
441: case TH_RUN | TH_WAIT | TH_UNINT:
442: case TH_RUN | TH_WAIT | TH_SUSP | TH_UNINT:
443: /*
444: * Either already running, or suspended.
445: */
446: thread->state = state &~ TH_WAIT;
447: thread->wait_result = result;
448: break;
449:
450: default:
451: panic("thread_wakeup");
452: break;
453: }
454: thread_unlock(thread);
455: if (one_thread)
456: break;
457: }
458: thread = next_th;
459: }
460: simple_unlock(lock);
461: splx(s);
462: }
463:
464: /*
465: * thread_sleep:
466: *
467: * Cause the current thread to wait until the specified event
468: * occurs. The specified lock is unlocked before releasing
469: * the cpu. (This is a convenient way to sleep without manually
470: * calling assert_wait).
471: */
472: void thread_sleep(
473: event_t event,
474: simple_lock_t lock,
475: boolean_t interruptible)
476: {
477: assert_wait(event, interruptible); /* assert event */
478: simple_unlock(lock); /* release the lock */
479: thread_block((void (*)()) 0); /* block ourselves */
480: }
481:
482: /*
483: * thread_bind:
484: *
485: * Force a thread to execute on the specified processor.
486: * If the thread is currently executing, it may wait until its
487: * time slice is up before switching onto the specified processor.
488: *
489: * A processor of PROCESSOR_NULL causes the thread to be unbound.
490: * xxx - DO NOT export this to users.
491: */
492: void thread_bind(
493: register thread_t thread,
494: processor_t processor)
495: {
496: spl_t s;
497:
498: s = splsched();
499: thread_lock(thread);
500: thread->bound_processor = processor;
501: thread_unlock(thread);
502: (void) splx(s);
503: }
504:
505: /*
506: * Select a thread for this processor (the current processor) to run.
507: * May select the current thread.
508: * Assumes splsched.
509: */
510:
511: thread_t thread_select(
512: register processor_t myprocessor)
513: {
514: register thread_t thread;
515:
516: myprocessor->first_quantum = TRUE;
517: /*
518: * Check for obvious simple case; local runq is
519: * empty and global runq has entry at hint.
520: */
521: if (myprocessor->runq.count > 0) {
522: thread = choose_thread(myprocessor);
523: myprocessor->quantum = min_quantum;
524: }
525: else {
526: register processor_set_t pset;
527:
528: #if MACH_HOST
529: pset = myprocessor->processor_set;
530: #else /* MACH_HOST */
531: pset = &default_pset;
532: #endif /* MACH_HOST */
533: simple_lock(&pset->runq.lock);
534: #if DEBUG
535: checkrq(&pset->runq, "thread_select");
536: #endif /* DEBUG */
537: if (pset->runq.count == 0) {
538: /*
539: * Nothing else runnable. Return if this
540: * thread is still runnable on this processor.
541: * Check for priority update if required.
542: */
543: thread = current_thread();
544: if ((thread->state == TH_RUN) &&
545: #if MACH_HOST
546: (thread->processor_set == pset) &&
547: #endif /* MACH_HOST */
548: ((thread->bound_processor == PROCESSOR_NULL) ||
549: (thread->bound_processor == myprocessor))) {
550:
551: simple_unlock(&pset->runq.lock);
552: thread_lock(thread);
553: if (thread->sched_stamp != sched_tick)
554: update_priority(thread);
555: thread_unlock(thread);
556: }
557: else {
558: thread = choose_pset_thread(myprocessor, pset);
559: }
560: }
561: else {
562: register queue_t q;
563:
564: /*
565: * If there is a thread at hint, grab it,
566: * else call choose_pset_thread.
567: */
568: q = pset->runq.runq + pset->runq.low;
569:
570: if (queue_empty(q)) {
571: pset->runq.low++;
572: thread = choose_pset_thread(myprocessor, pset);
573: }
574: else {
575: thread = (thread_t) dequeue_head(q);
576: thread->runq = RUN_QUEUE_NULL;
577: pset->runq.count--;
578: #if MACH_FIXPRI
579: /*
580: * Cannot lazy evaluate pset->runq.low for
581: * fixed priority policy
582: */
583: if ((pset->runq.count > 0) &&
584: (pset->policies & POLICY_FIXEDPRI)) {
585: while (queue_empty(q)) {
586: pset->runq.low++;
587: q++;
588: }
589: }
590: #endif /* MACH_FIXPRI */
591: #if DEBUG
592: checkrq(&pset->runq, "thread_select: after");
593: #endif /* DEBUG */
594: simple_unlock(&pset->runq.lock);
595: }
596: }
597:
598: #if MACH_FIXPRI
599: if (thread->policy == POLICY_TIMESHARE) {
600: #endif /* MACH_FIXPRI */
601: myprocessor->quantum = pset->set_quantum;
602: #if MACH_FIXPRI
603: }
604: else {
605: /*
606: * POLICY_FIXEDPRI
607: */
608: myprocessor->quantum = thread->sched_data;
609: }
610: #endif /* MACH_FIXPRI */
611: }
612:
613: return thread;
614: }
615:
616: /*
617: * Stop running the current thread and start running the new thread.
618: * If continuation is non-zero, and the current thread is blocked,
619: * then it will resume by executing continuation on a new stack.
620: * Returns TRUE if the hand-off succeeds.
621: * Assumes splsched.
622: */
623:
624: boolean_t thread_invoke(
625: register thread_t old_thread,
626: continuation_t continuation,
627: register thread_t new_thread)
628: {
629: /*
630: * Check for invoking the same thread.
631: */
632: if (old_thread == new_thread) {
633: /*
634: * Mark thread interruptible.
635: * Run continuation if there is one.
636: */
637: thread_lock(new_thread);
638: new_thread->state &= ~TH_UNINT;
639: thread_unlock(new_thread);
640:
641: if (continuation != (void (*)()) 0) {
642: (void) spl0();
643: call_continuation(continuation);
644: /*NOTREACHED*/
645: }
646: return TRUE;
647: }
648:
649: /*
650: * Check for stack-handoff.
651: */
652: thread_lock(new_thread);
653: if ((old_thread->stack_privilege != current_stack()) &&
654: (continuation != (void (*)()) 0))
655: {
656: switch (new_thread->state & TH_SWAP_STATE) {
657: case TH_SWAPPED:
658:
659: new_thread->state &= ~(TH_SWAPPED | TH_UNINT);
660: thread_unlock(new_thread);
661:
662: #if NCPUS > 1
663: new_thread->last_processor = current_processor();
664: #endif /* NCPUS > 1 */
665:
666: /*
667: * Set up ast context of new thread and
668: * switch to its timer.
669: */
670: ast_context(new_thread, cpu_number());
671: timer_switch(&new_thread->system_timer);
672:
673: stack_handoff(old_thread, new_thread);
674:
675: /*
676: * We can dispatch the old thread now.
677: * This is like thread_dispatch, except
678: * that the old thread is left swapped
679: * *without* freeing its stack.
680: * This path is also much more frequent
681: * than actual calls to thread_dispatch.
682: */
683:
684: thread_lock(old_thread);
685: old_thread->swap_func = continuation;
686:
687: switch (old_thread->state) {
688: case TH_RUN | TH_SUSP:
689: case TH_RUN | TH_SUSP | TH_HALTED:
690: case TH_RUN | TH_WAIT | TH_SUSP:
691: /*
692: * Suspend the thread
693: */
694: old_thread->state = (old_thread->state & ~TH_RUN)
695: | TH_SWAPPED;
696: if (old_thread->wake_active) {
697: old_thread->wake_active = FALSE;
698: thread_unlock(old_thread);
699: thread_wakeup((event_t)&old_thread->wake_active);
700:
701: goto after_old_thread;
702: }
703: break;
704:
705: case TH_RUN | TH_SUSP | TH_UNINT:
706: case TH_RUN | TH_UNINT:
707: case TH_RUN:
708: /*
709: * We can`t suspend the thread yet,
710: * or it`s still running.
711: * Put back on a run queue.
712: */
713: old_thread->state |= TH_SWAPPED;
714: thread_setrun(old_thread, FALSE);
715: break;
716:
717: case TH_RUN | TH_WAIT | TH_SUSP | TH_UNINT:
718: case TH_RUN | TH_WAIT | TH_UNINT:
719: case TH_RUN | TH_WAIT:
720: /*
721: * Waiting, and not suspendable.
722: */
723: old_thread->state = (old_thread->state & ~TH_RUN)
724: | TH_SWAPPED;
725: break;
726:
727: case TH_RUN | TH_IDLE:
728: /*
729: * Drop idle thread -- it is already in
730: * idle_thread_array.
731: */
732: old_thread->state = TH_RUN | TH_IDLE | TH_SWAPPED;
733: break;
734:
735: default:
736: panic("thread_invoke");
737: }
738: thread_unlock(old_thread);
739: after_old_thread:
740:
741: /*
742: * call_continuation calls the continuation
743: * after resetting the current stack pointer
744: * to recover stack space. If we called
745: * the continuation directly, we would risk
746: * running out of stack.
747: */
748:
749: counter_always(c_thread_invoke_hits++);
750: (void) spl0();
751: call_continuation(new_thread->swap_func);
752: /*NOTREACHED*/
753: return TRUE; /* help for the compiler */
754:
755: case TH_SW_COMING_IN:
756: /*
757: * Waiting for a stack
758: */
759: thread_swapin(new_thread);
760: thread_unlock(new_thread);
761: counter_always(c_thread_invoke_misses++);
762: return FALSE;
763:
764: case 0:
765: /*
766: * Already has a stack - can`t handoff.
767: */
768: break;
769: }
770: }
771:
772: else {
773: /*
774: * Check that the thread is swapped-in.
775: */
776: if (new_thread->state & TH_SWAPPED) {
777: if ((new_thread->state & TH_SW_COMING_IN) ||
778: !stack_alloc_try(new_thread, thread_continue))
779: {
780: thread_swapin(new_thread);
781: thread_unlock(new_thread);
782: counter_always(c_thread_invoke_misses++);
783: return FALSE;
784: }
785: }
786: }
787:
788: new_thread->state &= ~(TH_SWAPPED | TH_UNINT);
789: thread_unlock(new_thread);
790:
791: /*
792: * Thread is now interruptible.
793: */
794: #if NCPUS > 1
795: new_thread->last_processor = current_processor();
796: #endif /* NCPUS > 1 */
797:
798: /*
799: * Set up ast context of new thread and switch to its timer.
800: */
801: ast_context(new_thread, cpu_number());
802: timer_switch(&new_thread->system_timer);
803:
804: /*
805: * switch_context is machine-dependent. It does the
806: * machine-dependent components of a context-switch, like
807: * changing address spaces. It updates active_threads.
808: * It returns only if a continuation is not supplied.
809: */
810: counter_always(c_thread_invoke_csw++);
811: old_thread = switch_context(old_thread, continuation, new_thread);
812:
813: /*
814: * We're back. Now old_thread is the thread that resumed
815: * us, and we have to dispatch it.
816: */
817: thread_dispatch(old_thread);
818:
819: return TRUE;
820: }
821:
822: /*
823: * thread_continue:
824: *
825: * Called when the current thread is given a new stack.
826: * Called at splsched.
827: */
828: void thread_continue(
829: register thread_t old_thread)
830: {
831: register continuation_t continuation = current_thread()->swap_func;
832:
833: /*
834: * We must dispatch the old thread and then
835: * call the current thread's continuation.
836: * There might not be an old thread, if we are
837: * the first thread to run on this processor.
838: */
839:
840: if (old_thread != THREAD_NULL)
841: thread_dispatch(old_thread);
842: (void) spl0();
843: (*continuation)();
844: /*NOTREACHED*/
845: }
846:
847:
848: /*
849: * thread_block:
850: *
851: * Block the current thread. If the thread is runnable
852: * then someone must have woken it up between its request
853: * to sleep and now. In this case, it goes back on a
854: * run queue.
855: *
856: * If a continuation is specified, then thread_block will
857: * attempt to discard the thread's kernel stack. When the
858: * thread resumes, it will execute the continuation function
859: * on a new kernel stack.
860: */
861:
862: void thread_block(
863: continuation_t continuation)
864: {
865: register thread_t thread = current_thread();
866: register processor_t myprocessor = cpu_to_processor(cpu_number());
867: register thread_t new_thread;
868: spl_t s;
869:
870: check_simple_locks();
871:
872: s = splsched();
873:
874: #if FAST_TAS
875: {
876: extern void recover_ras();
877:
878: if (csw_needed(thread, myprocessor))
879: recover_ras(thread);
880: }
881: #endif /* FAST_TAS */
882:
883: ast_off(cpu_number(), AST_BLOCK);
884:
885: do
886: new_thread = thread_select(myprocessor);
887: while (!thread_invoke(thread, continuation, new_thread));
888:
889: splx(s);
890: }
891:
892: /*
893: * thread_run:
894: *
895: * Switch directly from the current thread to a specified
896: * thread. Both the current and new threads must be
897: * runnable.
898: *
899: * If a continuation is specified, then thread_block will
900: * attempt to discard the current thread's kernel stack. When the
901: * thread resumes, it will execute the continuation function
902: * on a new kernel stack.
903: */
904: void thread_run(
905: continuation_t continuation,
906: register thread_t new_thread)
907: {
908: register thread_t thread = current_thread();
909: register processor_t myprocessor = cpu_to_processor(cpu_number());
910: spl_t s;
911:
912: check_simple_locks();
913:
914: s = splsched();
915:
916: while (!thread_invoke(thread, continuation, new_thread))
917: new_thread = thread_select(myprocessor);
918:
919: splx(s);
920: }
921:
922: /*
923: * Dispatches a running thread that is not on a runq.
924: * Called at splsched.
925: */
926:
927: void thread_dispatch(
928: register thread_t thread)
929: {
930: /*
931: * If we are discarding the thread's stack, we must do it
932: * before the thread has a chance to run.
933: */
934:
935: thread_lock(thread);
936:
937: if (thread->swap_func != (void (*)()) 0) {
938: assert((thread->state & TH_SWAP_STATE) == 0);
939: thread->state |= TH_SWAPPED;
940: stack_free(thread);
941: }
942:
943: switch (thread->state &~ TH_SWAP_STATE) {
944: case TH_RUN | TH_SUSP:
945: case TH_RUN | TH_SUSP | TH_HALTED:
946: case TH_RUN | TH_WAIT | TH_SUSP:
947: /*
948: * Suspend the thread
949: */
950: thread->state &= ~TH_RUN;
951: if (thread->wake_active) {
952: thread->wake_active = FALSE;
953: thread_unlock(thread);
954: thread_wakeup((event_t)&thread->wake_active);
955: return;
956: }
957: break;
958:
959: case TH_RUN | TH_SUSP | TH_UNINT:
960: case TH_RUN | TH_UNINT:
961: case TH_RUN:
962: /*
963: * No reason to stop. Put back on a run queue.
964: */
965: thread_setrun(thread, FALSE);
966: break;
967:
968: case TH_RUN | TH_WAIT | TH_SUSP | TH_UNINT:
969: case TH_RUN | TH_WAIT | TH_UNINT:
970: case TH_RUN | TH_WAIT:
971: /*
972: * Waiting, and not suspended.
973: */
974: thread->state &= ~TH_RUN;
975: break;
976:
977: case TH_RUN | TH_IDLE:
978: /*
979: * Drop idle thread -- it is already in
980: * idle_thread_array.
981: */
982: break;
983:
984: default:
985: panic("thread_dispatch");
986: }
987: thread_unlock(thread);
988: }
989:
990:
991: /*
992: * Define shifts for simulating (5/8)**n
993: */
994:
995: shift_data_t wait_shift[32] = {
996: {1,1},{1,3},{1,-3},{2,-7},{3,5},{3,-5},{4,-8},{5,7},
997: {5,-7},{6,-10},{7,10},{7,-9},{8,-11},{9,12},{9,-11},{10,-13},
998: {11,14},{11,-13},{12,-15},{13,17},{13,-15},{14,-17},{15,19},{16,18},
999: {16,-19},{17,22},{18,20},{18,-20},{19,26},{20,22},{20,-22},{21,-27}};
1000:
1001: /*
1002: * do_priority_computation:
1003: *
1004: * Calculate new priority for thread based on its base priority plus
1005: * accumulated usage. PRI_SHIFT and PRI_SHIFT_2 convert from
1006: * usage to priorities. SCHED_SHIFT converts for the scaling
1007: * of the sched_usage field by SCHED_SCALE. This scaling comes
1008: * from the multiplication by sched_load (thread_timer_delta)
1009: * in sched.h. sched_load is calculated as a scaled overload
1010: * factor in compute_mach_factor (mach_factor.c).
1011: */
1012:
1013: #ifdef PRI_SHIFT_2
1014: #if PRI_SHIFT_2 > 0
1015: #define do_priority_computation(th, pri) \
1016: MACRO_BEGIN \
1017: (pri) = (th)->priority /* start with base priority */ \
1018: + ((th)->sched_usage >> (PRI_SHIFT + SCHED_SHIFT)) \
1019: + ((th)->sched_usage >> (PRI_SHIFT_2 + SCHED_SHIFT)); \
1020: if ((pri) > 31) (pri) = 31; \
1021: MACRO_END
1022: #else /* PRI_SHIFT_2 */
1023: #define do_priority_computation(th, pri) \
1024: MACRO_BEGIN \
1025: (pri) = (th)->priority /* start with base priority */ \
1026: + ((th)->sched_usage >> (PRI_SHIFT + SCHED_SHIFT)) \
1027: - ((th)->sched_usage >> (SCHED_SHIFT - PRI_SHIFT_2)); \
1028: if ((pri) > 31) (pri) = 31; \
1029: MACRO_END
1030: #endif /* PRI_SHIFT_2 */
1031: #else /* defined(PRI_SHIFT_2) */
1032: #define do_priority_computation(th, pri) \
1033: MACRO_BEGIN \
1034: (pri) = (th)->priority /* start with base priority */ \
1035: + ((th)->sched_usage >> (PRI_SHIFT + SCHED_SHIFT)); \
1036: if ((pri) > 31) (pri) = 31; \
1037: MACRO_END
1038: #endif /* defined(PRI_SHIFT_2) */
1039:
1040: /*
1041: * compute_priority:
1042: *
1043: * Compute the effective priority of the specified thread.
1044: * The effective priority computation is as follows:
1045: *
1046: * Take the base priority for this thread and add
1047: * to it an increment derived from its cpu_usage.
1048: *
1049: * The thread *must* be locked by the caller.
1050: */
1051:
1052: void compute_priority(
1053: register thread_t thread,
1054: boolean_t resched)
1055: {
1056: register int pri;
1057:
1058: #if MACH_FIXPRI
1059: if (thread->policy == POLICY_TIMESHARE) {
1060: #endif /* MACH_FIXPRI */
1061: do_priority_computation(thread, pri);
1062: if (thread->depress_priority < 0)
1063: set_pri(thread, pri, resched);
1064: else
1065: thread->depress_priority = pri;
1066: #if MACH_FIXPRI
1067: }
1068: else {
1069: set_pri(thread, thread->priority, resched);
1070: }
1071: #endif /* MACH_FIXPRI */
1072: }
1073:
1074: /*
1075: * compute_my_priority:
1076: *
1077: * Version of compute priority for current thread or thread
1078: * being manipulated by scheduler (going on or off a runq).
1079: * Only used for priority updates. Policy or priority changes
1080: * must call compute_priority above. Caller must have thread
1081: * locked and know it is timesharing and not depressed.
1082: */
1083:
1084: void compute_my_priority(
1085: register thread_t thread)
1086: {
1087: register int temp_pri;
1088:
1089: do_priority_computation(thread,temp_pri);
1090: thread->sched_pri = temp_pri;
1091: }
1092:
1093: /*
1094: * recompute_priorities:
1095: *
1096: * Update the priorities of all threads periodically.
1097: */
1098: void recompute_priorities(void)
1099: {
1100: #if SIMPLE_CLOCK
1101: int new_usec;
1102: #endif /* SIMPLE_CLOCK */
1103:
1104: sched_tick++; /* age usage one more time */
1105: set_timeout(&recompute_priorities_timer, hz);
1106: #if SIMPLE_CLOCK
1107: /*
1108: * Compensate for clock drift. sched_usec is an
1109: * exponential average of the number of microseconds in
1110: * a second. It decays in the same fashion as cpu_usage.
1111: */
1112: new_usec = sched_usec_elapsed();
1113: sched_usec = (5*sched_usec + 3*new_usec)/8;
1114: #endif /* SIMPLE_CLOCK */
1115: /*
1116: * Wakeup scheduler thread.
1117: */
1118: if (sched_thread_id != THREAD_NULL) {
1119: clear_wait(sched_thread_id, THREAD_AWAKENED, FALSE);
1120: }
1121: }
1122:
1123: /*
1124: * update_priority
1125: *
1126: * Cause the priority computation of a thread that has been
1127: * sleeping or suspended to "catch up" with the system. Thread
1128: * *MUST* be locked by caller. If thread is running, then this
1129: * can only be called by the thread on itself.
1130: */
1131: void update_priority(
1132: register thread_t thread)
1133: {
1134: register unsigned int ticks;
1135: register shift_t shiftp;
1136: register int temp_pri;
1137:
1138: ticks = sched_tick - thread->sched_stamp;
1139:
1140: assert(ticks != 0);
1141:
1142: /*
1143: * If asleep for more than 30 seconds forget all
1144: * cpu_usage, else catch up on missed aging.
1145: * 5/8 ** n is approximated by the two shifts
1146: * in the wait_shift array.
1147: */
1148: thread->sched_stamp += ticks;
1149: thread_timer_delta(thread);
1150: if (ticks > 30) {
1151: thread->cpu_usage = 0;
1152: thread->sched_usage = 0;
1153: }
1154: else {
1155: thread->cpu_usage += thread->cpu_delta;
1156: thread->sched_usage += thread->sched_delta;
1157: shiftp = &wait_shift[ticks];
1158: if (shiftp->shift2 > 0) {
1159: thread->cpu_usage =
1160: (thread->cpu_usage >> shiftp->shift1) +
1161: (thread->cpu_usage >> shiftp->shift2);
1162: thread->sched_usage =
1163: (thread->sched_usage >> shiftp->shift1) +
1164: (thread->sched_usage >> shiftp->shift2);
1165: }
1166: else {
1167: thread->cpu_usage =
1168: (thread->cpu_usage >> shiftp->shift1) -
1169: (thread->cpu_usage >> -(shiftp->shift2));
1170: thread->sched_usage =
1171: (thread->sched_usage >> shiftp->shift1) -
1172: (thread->sched_usage >> -(shiftp->shift2));
1173: }
1174: }
1175: thread->cpu_delta = 0;
1176: thread->sched_delta = 0;
1177: /*
1178: * Recompute priority if appropriate.
1179: */
1180: if (
1181: #if MACH_FIXPRI
1182: (thread->policy == POLICY_TIMESHARE) &&
1183: #endif /* MACH_FIXPRI */
1184: (thread->depress_priority < 0)) {
1185: do_priority_computation(thread, temp_pri);
1186: thread->sched_pri = temp_pri;
1187: }
1188: }
1189:
1190: /*
1191: * run_queue_enqueue macro for thread_setrun().
1192: */
1193: #if DEBUG
1194: #define run_queue_enqueue(rq, th) \
1195: MACRO_BEGIN \
1196: register unsigned int whichq; \
1197: \
1198: whichq = (th)->sched_pri; \
1199: if (whichq >= NRQS) { \
1200: printf("thread_setrun: pri too high (%d)\n", (th)->sched_pri); \
1201: whichq = NRQS - 1; \
1202: } \
1203: \
1204: simple_lock(&(rq)->lock); /* lock the run queue */ \
1205: checkrq((rq), "thread_setrun: before adding thread"); \
1206: enqueue_tail(&(rq)->runq[whichq], (queue_entry_t) (th)); \
1207: \
1208: if (whichq < (rq)->low || (rq)->count == 0) \
1209: (rq)->low = whichq; /* minimize */ \
1210: \
1211: (rq)->count++; \
1212: (th)->runq = (rq); \
1213: thread_check((th), (rq)); \
1214: checkrq((rq), "thread_setrun: after adding thread"); \
1215: simple_unlock(&(rq)->lock); \
1216: MACRO_END
1217: #else /* DEBUG */
1218: #define run_queue_enqueue(rq, th) \
1219: MACRO_BEGIN \
1220: register unsigned int whichq; \
1221: \
1222: whichq = (th)->sched_pri; \
1223: if (whichq >= NRQS) { \
1224: printf("thread_setrun: pri too high (%d)\n", (th)->sched_pri); \
1225: whichq = NRQS - 1; \
1226: } \
1227: \
1228: simple_lock(&(rq)->lock); /* lock the run queue */ \
1229: enqueue_tail(&(rq)->runq[whichq], (queue_entry_t) (th)); \
1230: \
1231: if (whichq < (rq)->low || (rq)->count == 0) \
1232: (rq)->low = whichq; /* minimize */ \
1233: \
1234: (rq)->count++; \
1235: (th)->runq = (rq); \
1236: simple_unlock(&(rq)->lock); \
1237: MACRO_END
1238: #endif /* DEBUG */
1239: /*
1240: * thread_setrun:
1241: *
1242: * Make thread runnable; dispatch directly onto an idle processor
1243: * if possible. Else put on appropriate run queue (processor
1244: * if bound, else processor set. Caller must have lock on thread.
1245: * This is always called at splsched.
1246: */
1247:
1248: void thread_setrun(
1249: register thread_t th,
1250: boolean_t may_preempt)
1251: {
1252: register processor_t processor;
1253: register run_queue_t rq;
1254: #if NCPUS > 1
1255: register processor_set_t pset;
1256: #endif /* NCPUS > 1 */
1257:
1258: /*
1259: * Update priority if needed.
1260: */
1261: if (th->sched_stamp != sched_tick) {
1262: update_priority(th);
1263: }
1264:
1265: assert(th->runq == RUN_QUEUE_NULL);
1266:
1267: #if NCPUS > 1
1268: /*
1269: * Try to dispatch the thread directly onto an idle processor.
1270: */
1271: if ((processor = th->bound_processor) == PROCESSOR_NULL) {
1272: /*
1273: * Not bound, any processor in the processor set is ok.
1274: */
1275: pset = th->processor_set;
1276: #if HW_FOOTPRINT
1277: /*
1278: * But first check the last processor it ran on.
1279: */
1280: processor = th->last_processor;
1281: if (processor->state == PROCESSOR_IDLE) {
1282: simple_lock(&processor->lock);
1283: simple_lock(&pset->idle_lock);
1284: if ((processor->state == PROCESSOR_IDLE)
1285: #if MACH_HOST
1286: && (processor->processor_set == pset)
1287: #endif /* MACH_HOST */
1288: ) {
1289: queue_remove(&pset->idle_queue, processor,
1290: processor_t, processor_queue);
1291: pset->idle_count--;
1292: processor->next_thread = th;
1293: processor->state = PROCESSOR_DISPATCHING;
1294: simple_unlock(&pset->idle_lock);
1295: simple_unlock(&processor->lock);
1296: return;
1297: }
1298: simple_unlock(&pset->idle_lock);
1299: simple_unlock(&processor->lock);
1300: }
1301: #endif /* HW_FOOTPRINT */
1302:
1303: if (pset->idle_count > 0) {
1304: simple_lock(&pset->idle_lock);
1305: if (pset->idle_count > 0) {
1306: processor = (processor_t) queue_first(&pset->idle_queue);
1307: queue_remove(&(pset->idle_queue), processor, processor_t,
1308: processor_queue);
1309: pset->idle_count--;
1310: processor->next_thread = th;
1311: processor->state = PROCESSOR_DISPATCHING;
1312: simple_unlock(&pset->idle_lock);
1313: return;
1314: }
1315: simple_unlock(&pset->idle_lock);
1316: }
1317: rq = &(pset->runq);
1318: run_queue_enqueue(rq,th);
1319: /*
1320: * Preempt check
1321: */
1322: if (may_preempt &&
1323: #if MACH_HOST
1324: (pset == current_processor()->processor_set) &&
1325: #endif /* MACH_HOST */
1326: (current_thread()->sched_pri > th->sched_pri)) {
1327: /*
1328: * Turn off first_quantum to allow csw.
1329: */
1330: current_processor()->first_quantum = FALSE;
1331: ast_on(cpu_number(), AST_BLOCK);
1332: }
1333: }
1334: else {
1335: /*
1336: * Bound, can only run on bound processor. Have to lock
1337: * processor here because it may not be the current one.
1338: */
1339: if (processor->state == PROCESSOR_IDLE) {
1340: simple_lock(&processor->lock);
1341: pset = processor->processor_set;
1342: simple_lock(&pset->idle_lock);
1343: if (processor->state == PROCESSOR_IDLE) {
1344: queue_remove(&pset->idle_queue, processor,
1345: processor_t, processor_queue);
1346: pset->idle_count--;
1347: processor->next_thread = th;
1348: processor->state = PROCESSOR_DISPATCHING;
1349: simple_unlock(&pset->idle_lock);
1350: simple_unlock(&processor->lock);
1351: return;
1352: }
1353: simple_unlock(&pset->idle_lock);
1354: simple_unlock(&processor->lock);
1355: }
1356: rq = &(processor->runq);
1357: run_queue_enqueue(rq,th);
1358:
1359: /*
1360: * Cause ast on processor if processor is on line.
1361: *
1362: * XXX Don't do this remotely to master because this will
1363: * XXX send an interprocessor interrupt, and that's too
1364: * XXX expensive for all the unparallelized U*x code.
1365: */
1366: if (processor == current_processor()) {
1367: ast_on(cpu_number(), AST_BLOCK);
1368: }
1369: else if ((processor != master_processor) &&
1370: (processor->state != PROCESSOR_OFF_LINE)) {
1371: cause_ast_check(processor);
1372: }
1373: }
1374: #else /* NCPUS > 1 */
1375: /*
1376: * XXX should replace queue with a boolean in this case.
1377: */
1378: if (default_pset.idle_count > 0) {
1379: processor = (processor_t) queue_first(&default_pset.idle_queue);
1380: queue_remove(&default_pset.idle_queue, processor,
1381: processor_t, processor_queue);
1382: default_pset.idle_count--;
1383: processor->next_thread = th;
1384: processor->state = PROCESSOR_DISPATCHING;
1385: return;
1386: }
1387: if (th->bound_processor == PROCESSOR_NULL) {
1388: rq = &(default_pset.runq);
1389: }
1390: else {
1391: rq = &(master_processor->runq);
1392: ast_on(cpu_number(), AST_BLOCK);
1393: }
1394: run_queue_enqueue(rq,th);
1395:
1396: /*
1397: * Preempt check
1398: */
1399: if (may_preempt && (current_thread()->sched_pri > th->sched_pri)) {
1400: /*
1401: * Turn off first_quantum to allow context switch.
1402: */
1403: current_processor()->first_quantum = FALSE;
1404: ast_on(cpu_number(), AST_BLOCK);
1405: }
1406: #endif /* NCPUS > 1 */
1407: }
1408:
1409: /*
1410: * set_pri:
1411: *
1412: * Set the priority of the specified thread to the specified
1413: * priority. This may cause the thread to change queues.
1414: *
1415: * The thread *must* be locked by the caller.
1416: */
1417:
1418: void set_pri(
1419: thread_t th,
1420: int pri,
1421: boolean_t resched)
1422: {
1423: register struct run_queue *rq;
1424:
1425: rq = rem_runq(th);
1426: th->sched_pri = pri;
1427: if (rq != RUN_QUEUE_NULL) {
1428: if (resched)
1429: thread_setrun(th, TRUE);
1430: else
1431: run_queue_enqueue(rq, th);
1432: }
1433: }
1434:
1435: /*
1436: * rem_runq:
1437: *
1438: * Remove a thread from its run queue.
1439: * The run queue that the process was on is returned
1440: * (or RUN_QUEUE_NULL if not on a run queue). Thread *must* be locked
1441: * before calling this routine. Unusual locking protocol on runq
1442: * field in thread structure makes this code interesting; see thread.h.
1443: */
1444:
1445: struct run_queue *rem_runq(
1446: thread_t th)
1447: {
1448: register struct run_queue *rq;
1449:
1450: rq = th->runq;
1451: /*
1452: * If rq is RUN_QUEUE_NULL, the thread will stay out of the
1453: * run_queues because the caller locked the thread. Otherwise
1454: * the thread is on a runq, but could leave.
1455: */
1456: if (rq != RUN_QUEUE_NULL) {
1457: simple_lock(&rq->lock);
1458: #if DEBUG
1459: checkrq(rq, "rem_runq: at entry");
1460: #endif /* DEBUG */
1461: if (rq == th->runq) {
1462: /*
1463: * Thread is in a runq and we have a lock on
1464: * that runq.
1465: */
1466: #if DEBUG
1467: checkrq(rq, "rem_runq: before removing thread");
1468: thread_check(th, rq);
1469: #endif /* DEBUG */
1470: remqueue(&rq->runq[0], (queue_entry_t) th);
1471: rq->count--;
1472: #if DEBUG
1473: checkrq(rq, "rem_runq: after removing thread");
1474: #endif /* DEBUG */
1475: th->runq = RUN_QUEUE_NULL;
1476: simple_unlock(&rq->lock);
1477: }
1478: else {
1479: /*
1480: * The thread left the runq before we could
1481: * lock the runq. It is not on a runq now, and
1482: * can't move again because this routine's
1483: * caller locked the thread.
1484: */
1485: simple_unlock(&rq->lock);
1486: rq = RUN_QUEUE_NULL;
1487: }
1488: }
1489:
1490: return rq;
1491: }
1492:
1493:
1494: /*
1495: * choose_thread:
1496: *
1497: * Choose a thread to execute. The thread chosen is removed
1498: * from its run queue. Note that this requires only that the runq
1499: * lock be held.
1500: *
1501: * Strategy:
1502: * Check processor runq first; if anything found, run it.
1503: * Else check pset runq; if nothing found, return idle thread.
1504: *
1505: * Second line of strategy is implemented by choose_pset_thread.
1506: * This is only called on processor startup and when thread_block
1507: * thinks there's something in the processor runq.
1508: */
1509:
1510: thread_t choose_thread(
1511: processor_t myprocessor)
1512: {
1513: thread_t th;
1514: register queue_t q;
1515: register run_queue_t runq;
1516: register int i;
1517: register processor_set_t pset;
1518:
1519: runq = &myprocessor->runq;
1520:
1521: simple_lock(&runq->lock);
1522: if (runq->count > 0) {
1523: q = runq->runq + runq->low;
1524: for (i = runq->low; i < NRQS ; i++, q++) {
1525: if (!queue_empty(q)) {
1526: th = (thread_t) dequeue_head(q);
1527: th->runq = RUN_QUEUE_NULL;
1528: runq->count--;
1529: runq->low = i;
1530: simple_unlock(&runq->lock);
1531: return th;
1532: }
1533: }
1534: panic("choose_thread");
1535: /*NOTREACHED*/
1536: }
1537: simple_unlock(&runq->lock);
1538:
1539: pset = myprocessor->processor_set;
1540:
1541: simple_lock(&pset->runq.lock);
1542: return choose_pset_thread(myprocessor,pset);
1543: }
1544:
1545: /*
1546: * choose_pset_thread: choose a thread from processor_set runq or
1547: * set processor idle and choose its idle thread.
1548: *
1549: * Caller must be at splsched and have a lock on the runq. This
1550: * lock is released by this routine. myprocessor is always the current
1551: * processor, and pset must be its processor set.
1552: * This routine chooses and removes a thread from the runq if there
1553: * is one (and returns it), else it sets the processor idle and
1554: * returns its idle thread.
1555: */
1556:
1557: thread_t choose_pset_thread(
1558: register processor_t myprocessor,
1559: processor_set_t pset)
1560: {
1561: register run_queue_t runq;
1562: register thread_t th;
1563: register queue_t q;
1564: register int i;
1565:
1566: runq = &pset->runq;
1567:
1568: if (runq->count > 0) {
1569: q = runq->runq + runq->low;
1570: for (i = runq->low; i < NRQS ; i++, q++) {
1571: if (!queue_empty(q)) {
1572: th = (thread_t) dequeue_head(q);
1573: th->runq = RUN_QUEUE_NULL;
1574: runq->count--;
1575: /*
1576: * For POLICY_FIXEDPRI, runq->low must be
1577: * accurate!
1578: */
1579: #if MACH_FIXPRI
1580: if ((runq->count > 0) &&
1581: (pset->policies & POLICY_FIXEDPRI)) {
1582: while (queue_empty(q)) {
1583: q++;
1584: i++;
1585: }
1586: }
1587: #endif /* MACH_FIXPRI */
1588: runq->low = i;
1589: #if DEBUG
1590: checkrq(runq, "choose_pset_thread");
1591: #endif /* DEBUG */
1592: simple_unlock(&runq->lock);
1593: return th;
1594: }
1595: }
1596: panic("choose_pset_thread");
1597: /*NOTREACHED*/
1598: }
1599: simple_unlock(&runq->lock);
1600:
1601: /*
1602: * Nothing is runnable, so set this processor idle if it
1603: * was running. If it was in an assignment or shutdown,
1604: * leave it alone. Return its idle thread.
1605: */
1606: simple_lock(&pset->idle_lock);
1607: if (myprocessor->state == PROCESSOR_RUNNING) {
1608: myprocessor->state = PROCESSOR_IDLE;
1609: /*
1610: * XXX Until it goes away, put master on end of queue, others
1611: * XXX on front so master gets used last.
1612: */
1613: if (myprocessor == master_processor) {
1614: queue_enter(&(pset->idle_queue), myprocessor,
1615: processor_t, processor_queue);
1616: }
1617: else {
1618: queue_enter_first(&(pset->idle_queue), myprocessor,
1619: processor_t, processor_queue);
1620: }
1621:
1622: pset->idle_count++;
1623: }
1624: simple_unlock(&pset->idle_lock);
1625:
1626: return myprocessor->idle_thread;
1627: }
1628:
1629: /*
1630: * no_dispatch_count counts number of times processors go non-idle
1631: * without being dispatched. This should be very rare.
1632: */
1633: int no_dispatch_count = 0;
1634:
1635: /*
1636: * This is the idle thread, which just looks for other threads
1637: * to execute.
1638: */
1639:
1640: void idle_thread_continue(void)
1641: {
1642: register processor_t myprocessor;
1643: register volatile thread_t *threadp;
1644: register volatile int *gcount;
1645: register volatile int *lcount;
1646: register thread_t new_thread;
1647: register int state;
1648: int mycpu;
1649: spl_t s;
1650:
1651: mycpu = cpu_number();
1652: myprocessor = current_processor();
1653: threadp = (volatile thread_t *) &myprocessor->next_thread;
1654: lcount = (volatile int *) &myprocessor->runq.count;
1655:
1656: while (TRUE) {
1657: #ifdef MARK_CPU_IDLE
1658: MARK_CPU_IDLE(mycpu);
1659: #endif /* MARK_CPU_IDLE */
1660:
1661: #if MACH_HOST
1662: gcount = (volatile int *)
1663: &myprocessor->processor_set->runq.count;
1664: #else /* MACH_HOST */
1665: gcount = (volatile int *) &default_pset.runq.count;
1666: #endif /* MACH_HOST */
1667:
1668: /*
1669: * This cpu will be dispatched (by thread_setrun) by setting next_thread
1670: * to the value of the thread to run next. Also check runq counts.
1671: */
1672: while ((*threadp == (volatile thread_t)THREAD_NULL) &&
1673: (*gcount == 0) && (*lcount == 0)) {
1674:
1675: /* check for ASTs while we wait */
1676:
1677: if (need_ast[mycpu] &~ AST_SCHEDULING) {
1678: (void) splsched();
1679: /* don't allow scheduling ASTs */
1680: need_ast[mycpu] &= ~AST_SCHEDULING;
1681: ast_taken();
1682: /* back at spl0 */
1683: }
1684:
1685: /*
1686: * machine_idle is a machine dependent function,
1687: * to conserve power.
1688: */
1689: #if POWER_SAVE
1690: machine_idle(mycpu);
1691: #endif /* POWER_SAVE */
1692: }
1693:
1694: #ifdef MARK_CPU_ACTIVE
1695: MARK_CPU_ACTIVE(mycpu);
1696: #endif /* MARK_CPU_ACTIVE */
1697:
1698: s = splsched();
1699:
1700: /*
1701: * This is not a switch statement to avoid the
1702: * bounds checking code in the common case.
1703: */
1704: retry:
1705: state = myprocessor->state;
1706: if (state == PROCESSOR_DISPATCHING) {
1707: /*
1708: * Commmon case -- cpu dispatched.
1709: */
1710: new_thread = (thread_t) *threadp;
1711: *threadp = (volatile thread_t) THREAD_NULL;
1712: myprocessor->state = PROCESSOR_RUNNING;
1713: /*
1714: * set up quantum for new thread.
1715: */
1716: #if MACH_FIXPRI
1717: if (new_thread->policy == POLICY_TIMESHARE) {
1718: #endif /* MACH_FIXPRI */
1719: /*
1720: * Just use set quantum. No point in
1721: * checking for shorter local runq quantum;
1722: * csw_needed will handle correctly.
1723: */
1724: #if MACH_HOST
1725: myprocessor->quantum = new_thread->
1726: processor_set->set_quantum;
1727: #else /* MACH_HOST */
1728: myprocessor->quantum =
1729: default_pset.set_quantum;
1730: #endif /* MACH_HOST */
1731:
1732: #if MACH_FIXPRI
1733: }
1734: else {
1735: /*
1736: * POLICY_FIXEDPRI
1737: */
1738: myprocessor->quantum = new_thread->sched_data;
1739: }
1740: #endif /* MACH_FIXPRI */
1741: myprocessor->first_quantum = TRUE;
1742: counter(c_idle_thread_handoff++);
1743: thread_run(idle_thread_continue, new_thread);
1744: }
1745: else if (state == PROCESSOR_IDLE) {
1746: register processor_set_t pset;
1747:
1748: pset = myprocessor->processor_set;
1749: simple_lock(&pset->idle_lock);
1750: if (myprocessor->state != PROCESSOR_IDLE) {
1751: /*
1752: * Something happened, try again.
1753: */
1754: simple_unlock(&pset->idle_lock);
1755: goto retry;
1756: }
1757: /*
1758: * Processor was not dispatched (Rare).
1759: * Set it running again.
1760: */
1761: no_dispatch_count++;
1762: pset->idle_count--;
1763: queue_remove(&pset->idle_queue, myprocessor,
1764: processor_t, processor_queue);
1765: myprocessor->state = PROCESSOR_RUNNING;
1766: simple_unlock(&pset->idle_lock);
1767: counter(c_idle_thread_block++);
1768: thread_block(idle_thread_continue);
1769: }
1770: else if ((state == PROCESSOR_ASSIGN) ||
1771: (state == PROCESSOR_SHUTDOWN)) {
1772: /*
1773: * Changing processor sets, or going off-line.
1774: * Release next_thread if there is one. Actual
1775: * thread to run is on a runq.
1776: */
1777: if ((new_thread = (thread_t)*threadp)!= THREAD_NULL) {
1778: *threadp = (volatile thread_t) THREAD_NULL;
1779: thread_setrun(new_thread, FALSE);
1780: }
1781:
1782: counter(c_idle_thread_block++);
1783: thread_block(idle_thread_continue);
1784: }
1785: else {
1786: printf(" Bad processor state %d (Cpu %d)\n",
1787: cpu_state(mycpu), mycpu);
1788: panic("idle_thread");
1789: }
1790:
1791: (void) splx(s);
1792: }
1793: }
1794:
1795: void idle_thread(void)
1796: {
1797: register thread_t self = current_thread();
1798: spl_t s;
1799:
1800: stack_privilege(self);
1801:
1802: s = splsched();
1803: self->priority = 31;
1804: self->sched_pri = 31;
1805:
1806: /*
1807: * Set the idle flag to indicate that this is an idle thread,
1808: * enter ourselves in the idle array, and thread_block() to get
1809: * out of the run queues (and set the processor idle when we
1810: * run next time).
1811: */
1812: thread_lock(self);
1813: self->state |= TH_IDLE;
1814: thread_unlock(self);
1815: current_processor()->idle_thread = self;
1816: (void) splx(s);
1817:
1818: counter(c_idle_thread_block++);
1819: thread_block(idle_thread_continue);
1820: idle_thread_continue();
1821: /*NOTREACHED*/
1822: }
1823:
1824: /*
1825: * sched_thread: scheduler thread.
1826: *
1827: * This thread handles periodic calculations in the scheduler that
1828: * we don't want to do at interrupt level. This allows us to
1829: * avoid blocking.
1830: */
1831: void sched_thread_continue(void)
1832: {
1833: while (TRUE) {
1834: (void) compute_mach_factor();
1835:
1836: /*
1837: * Check for stuck threads. This can't be done off of
1838: * the callout queue because it requires operations that
1839: * can't be used from interrupt level.
1840: */
1841: if (sched_tick & 1)
1842: do_thread_scan();
1843:
1844: assert_wait((event_t) 0, FALSE);
1845: counter(c_sched_thread_block++);
1846: thread_block(sched_thread_continue);
1847: }
1848: }
1849:
1850: void sched_thread(void)
1851: {
1852: sched_thread_id = current_thread();
1853:
1854: /*
1855: * Sleep on event 0, recompute_priorities() will awaken
1856: * us by calling clear_wait().
1857: */
1858: assert_wait((event_t) 0, FALSE);
1859: counter(c_sched_thread_block++);
1860: thread_block(sched_thread_continue);
1861: sched_thread_continue();
1862: /*NOTREACHED*/
1863: }
1864:
1865: #define MAX_STUCK_THREADS 16
1866:
1867: /*
1868: * do_thread_scan: scan for stuck threads. A thread is stuck if
1869: * it is runnable but its priority is so low that it has not
1870: * run for several seconds. Its priority should be higher, but
1871: * won't be until it runs and calls update_priority. The scanner
1872: * finds these threads and does the updates.
1873: *
1874: * Scanner runs in two passes. Pass one squirrels likely
1875: * thread ids away in an array, and removes them from the run queue.
1876: * Pass two does the priority updates. This is necessary because
1877: * the run queue lock is required for the candidate scan, but
1878: * cannot be held during updates [set_pri will deadlock].
1879: *
1880: * Array length should be enough so that restart isn't necessary,
1881: * but restart logic is included. Does not scan processor runqs.
1882: *
1883: */
1884:
1885: boolean_t do_thread_scan_debug = FALSE;
1886:
1887: thread_t stuck_threads[MAX_STUCK_THREADS];
1888: int stuck_count = 0;
1889:
1890: /*
1891: * do_runq_scan is the guts of pass 1. It scans a runq for
1892: * stuck threads. A boolean is returned indicating whether
1893: * it ran out of space.
1894: */
1895:
1896: boolean_t
1897: do_runq_scan(
1898: run_queue_t runq)
1899: {
1900: register spl_t s;
1901: register queue_t q;
1902: register thread_t thread;
1903: register int count;
1904:
1905: s = splsched();
1906: simple_lock(&runq->lock);
1907: if((count = runq->count) > 0) {
1908: q = runq->runq + runq->low;
1909: while (count > 0) {
1910: thread = (thread_t) queue_first(q);
1911: while (!queue_end(q, (queue_entry_t) thread)) {
1912: /*
1913: * Get the next thread now, since we may
1914: * remove this thread from the run queue.
1915: */
1916: thread_t next = (thread_t) queue_next(&thread->links);
1917:
1918: if ((thread->state & TH_SCHED_STATE) == TH_RUN &&
1919: sched_tick - thread->sched_stamp > 1) {
1920: /*
1921: * Stuck, save its id for later.
1922: */
1923: if (stuck_count == MAX_STUCK_THREADS) {
1924: /*
1925: * !@#$% No more room.
1926: */
1927: simple_unlock(&runq->lock);
1928: splx(s);
1929: return TRUE;
1930: }
1931: /*
1932: * We can`t take the thread_lock here,
1933: * since we already have the runq lock.
1934: * So we can`t grab a reference to the
1935: * thread. However, a thread that is
1936: * in RUN state cannot be deallocated
1937: * until it stops running. If it isn`t
1938: * on the runq, then thread_halt cannot
1939: * see it. So we remove the thread
1940: * from the runq to make it safe.
1941: */
1942: remqueue(q, (queue_entry_t) thread);
1943: runq->count--;
1944: thread->runq = RUN_QUEUE_NULL;
1945:
1946: stuck_threads[stuck_count++] = thread;
1947: if (do_thread_scan_debug)
1948: printf("do_runq_scan: adding thread %#x\n", thread);
1949: }
1950: count--;
1951: thread = next;
1952: }
1953: q++;
1954: }
1955: }
1956: simple_unlock(&runq->lock);
1957: splx(s);
1958:
1959: return FALSE;
1960: }
1961:
1962: void do_thread_scan(void)
1963: {
1964: register spl_t s;
1965: register boolean_t restart_needed = 0;
1966: register thread_t thread;
1967: #if MACH_HOST
1968: register processor_set_t pset;
1969: #endif /* MACH_HOST */
1970:
1971: do {
1972: #if MACH_HOST
1973: simple_lock(&all_psets_lock);
1974: queue_iterate(&all_psets, pset, processor_set_t, all_psets) {
1975: if (restart_needed = do_runq_scan(&pset->runq))
1976: break;
1977: }
1978: simple_unlock(&all_psets_lock);
1979: #else /* MACH_HOST */
1980: restart_needed = do_runq_scan(&default_pset.runq);
1981: #endif /* MACH_HOST */
1982: if (!restart_needed)
1983: restart_needed = do_runq_scan(&master_processor->runq);
1984:
1985: /*
1986: * Ok, we now have a collection of candidates -- fix them.
1987: */
1988:
1989: while (stuck_count > 0) {
1990: thread = stuck_threads[--stuck_count];
1991: stuck_threads[stuck_count] = THREAD_NULL;
1992: s = splsched();
1993: thread_lock(thread);
1994: if ((thread->state & TH_SCHED_STATE) == TH_RUN) {
1995: /*
1996: * Do the priority update. Call
1997: * thread_setrun because thread is
1998: * off the run queues.
1999: */
2000: update_priority(thread);
2001: thread_setrun(thread, TRUE);
2002: }
2003: thread_unlock(thread);
2004: splx(s);
2005: }
2006: } while (restart_needed);
2007: }
2008:
2009: #if DEBUG
2010: void checkrq(
2011: run_queue_t rq,
2012: char *msg)
2013: {
2014: register queue_t q1;
2015: register int i, j;
2016: register queue_entry_t e;
2017: register int low;
2018:
2019: low = -1;
2020: j = 0;
2021: q1 = rq->runq;
2022: for (i = 0; i < NRQS; i++) {
2023: if (q1->next == q1) {
2024: if (q1->prev != q1)
2025: panic("checkrq: empty at %s", msg);
2026: }
2027: else {
2028: if (low == -1)
2029: low = i;
2030:
2031: for (e = q1->next; e != q1; e = e->next) {
2032: j++;
2033: if (e->next->prev != e)
2034: panic("checkrq-2 at %s", msg);
2035: if (e->prev->next != e)
2036: panic("checkrq-3 at %s", msg);
2037: }
2038: }
2039: q1++;
2040: }
2041: if (j != rq->count)
2042: panic("checkrq: count wrong at %s", msg);
2043: if (rq->count != 0 && low < rq->low)
2044: panic("checkrq: low wrong at %s", msg);
2045: }
2046:
2047: void thread_check(
2048: register thread_t th,
2049: register run_queue_t rq)
2050: {
2051: register unsigned int whichq;
2052:
2053: whichq = th->sched_pri;
2054: if (whichq >= NRQS) {
2055: printf("thread_check: priority too high\n");
2056: whichq = NRQS-1;
2057: }
2058: if ((th->links.next == &rq->runq[whichq]) &&
2059: (rq->runq[whichq].prev != (queue_entry_t)th))
2060: panic("thread_check");
2061: }
2062: #endif /* DEBUG */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.