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