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