Return to sched_prim.c CVS log

Up to [Apple Darwin 0.x] / kernel / kern

Annotation of kernel/kern/sched_prim.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.