Annotation of prex/sys/kern/sched.c, Revision 1.1
1.1 ! nbrk 1: /*-
! 2: * Copyright (c) 2005-2008, Kohsuke Ohtani
! 3: * All rights reserved.
! 4: *
! 5: * Redistribution and use in source and binary forms, with or without
! 6: * modification, are permitted provided that the following conditions
! 7: * are met:
! 8: * 1. Redistributions of source code must retain the above copyright
! 9: * notice, this list of conditions and the following disclaimer.
! 10: * 2. Redistributions in binary form must reproduce the above copyright
! 11: * notice, this list of conditions and the following disclaimer in the
! 12: * documentation and/or other materials provided with the distribution.
! 13: * 3. Neither the name of the author nor the names of any co-contributors
! 14: * may be used to endorse or promote products derived from this software
! 15: * without specific prior written permission.
! 16: *
! 17: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
! 18: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
! 19: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
! 20: * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
! 21: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
! 22: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
! 23: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
! 24: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
! 25: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
! 26: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
! 27: * SUCH DAMAGE.
! 28: */
! 29:
! 30: /*
! 31: * sched.c - scheduler
! 32: */
! 33:
! 34: /**
! 35: * General design:
! 36: *
! 37: * The Prex scheduler is based on the algorithm known as priority
! 38: * based multi level queue. Each thread has its own priority
! 39: * assigned between 0 and 255. The lower number means higher
! 40: * priority like BSD unix. The scheduler maintains 256 level run
! 41: * queues mapped to each priority. The lowest priority (=255) is
! 42: * used only for an idle thread.
! 43: *
! 44: * All threads have two different types of priorities:
! 45: *
! 46: * Base priority:
! 47: * This is a static priority used for priority computation.
! 48: * A user mode program can change this value via system call.
! 49: *
! 50: * Current priority:
! 51: * An actual scheduling priority. A kernel may adjust this
! 52: * priority dynamically if it's needed.
! 53: *
! 54: * Each thread has one of the following state.
! 55: *
! 56: * - TH_RUN Running or ready to run
! 57: * - TH_SLEEP Sleep for some event
! 58: * - TH_SUSPEND Suspend count is not 0
! 59: * - TH_EXIT Terminated
! 60: *
! 61: * The thread is always preemptive even in the kernel mode.
! 62: * There are following 4 reasons to switch thread.
! 63: *
! 64: * (1) Block
! 65: * Thread is blocked for sleep or suspend.
! 66: * It is put on the tail of the run queue when it becomes
! 67: * runnable again.
! 68: *
! 69: * (2) Preemption
! 70: * If higher priority thread becomes runnable, the current
! 71: * thread is put on the _head_ of the run queue.
! 72: *
! 73: * (3) Quantum expiration
! 74: * If the thread consumes its time quantum, it is put on
! 75: * the tail of the run queue.
! 76: *
! 77: * (4) Yield
! 78: * If the thread releases CPU by itself, it is put on the
! 79: * tail of the run queue.
! 80: *
! 81: * There are following three types of scheduling policies.
! 82: *
! 83: * - SCHED_FIFO First in-first-out
! 84: * - SCHED_RR Round robin (SCHED_FIFO + timeslice)
! 85: * - SCHED_OTHER Another scheduling (not supported)
! 86: */
! 87:
! 88: #include <kernel.h>
! 89: #include <queue.h>
! 90: #include <event.h>
! 91: #include <irq.h>
! 92: #include <thread.h>
! 93: #include <timer.h>
! 94: #include <vm.h>
! 95: #include <task.h>
! 96: #include <system.h>
! 97: #include <sched.h>
! 98:
! 99: static struct queue runq[NPRIO]; /* run queues */
! 100: static struct queue wakeq; /* queue for waking threads */
! 101: static struct queue dpcq; /* DPC queue */
! 102: static int top_prio; /* highest priority in runq */
! 103: static struct event dpc_event; /* event for DPC */
! 104:
! 105: /*
! 106: * Search for highest-priority runnable thread.
! 107: */
! 108: static int
! 109: runq_top(void)
! 110: {
! 111: int prio;
! 112:
! 113: for (prio = 0; prio < MIN_PRIO; prio++)
! 114: if (!queue_empty(&runq[prio]))
! 115: break;
! 116: return prio;
! 117: }
! 118:
! 119: /*
! 120: * Put a thread on the tail of the run queue.
! 121: */
! 122: static void
! 123: runq_enqueue(thread_t th)
! 124: {
! 125:
! 126: enqueue(&runq[th->prio], &th->link);
! 127: if (th->prio < top_prio) {
! 128: top_prio = th->prio;
! 129: cur_thread->resched = 1;
! 130: }
! 131: }
! 132:
! 133: /*
! 134: * Insert a thread to the head of the run queue.
! 135: * We assume this routine is called while thread switching.
! 136: */
! 137: static void
! 138: runq_insert(thread_t th)
! 139: {
! 140:
! 141: queue_insert(&runq[th->prio], &th->link);
! 142: if (th->prio < top_prio)
! 143: top_prio = th->prio;
! 144: }
! 145:
! 146: /*
! 147: * Pick up and remove the highest-priority thread
! 148: * from the run queue.
! 149: */
! 150: static thread_t
! 151: runq_dequeue(void)
! 152: {
! 153: queue_t q;
! 154: thread_t th;
! 155:
! 156: q = dequeue(&runq[top_prio]);
! 157: th = queue_entry(q, struct thread, link);
! 158: if (queue_empty(&runq[top_prio]))
! 159: top_prio = runq_top();
! 160: return th;
! 161: }
! 162:
! 163: /*
! 164: * Remove the specified thread from the run queue.
! 165: */
! 166: static void
! 167: runq_remove(thread_t th)
! 168: {
! 169:
! 170: queue_remove(&th->link);
! 171: top_prio = runq_top();
! 172: }
! 173:
! 174: /*
! 175: * Process all pending woken threads.
! 176: */
! 177: static void
! 178: wakeq_flush(void)
! 179: {
! 180: queue_t q;
! 181: thread_t th;
! 182:
! 183: while (!queue_empty(&wakeq)) {
! 184: /*
! 185: * Set a thread runnable.
! 186: */
! 187: q = dequeue(&wakeq);
! 188: th = queue_entry(q, struct thread, link);
! 189: th->slpevt = NULL;
! 190: th->state &= ~TH_SLEEP;
! 191: if (th != cur_thread && th->state == TH_RUN)
! 192: runq_enqueue(th);
! 193: }
! 194: }
! 195:
! 196: /*
! 197: * sched_switch - this is the scheduler proper:
! 198: *
! 199: * If the scheduling reason is preemption, the current
! 200: * thread will remain at the head of the run queue. So,
! 201: * the thread still has right to run first again among
! 202: * the same priority threads. For other scheduling reason,
! 203: * the current thread is inserted into the tail of the run
! 204: * queue.
! 205: */
! 206: static void
! 207: sched_switch(void)
! 208: {
! 209: thread_t prev, next;
! 210:
! 211: /*
! 212: * Move a current thread to the run queue.
! 213: */
! 214: prev = cur_thread;
! 215: if (prev->state == TH_RUN) {
! 216: if (prev->prio > top_prio)
! 217: runq_insert(prev); /* preemption */
! 218: else
! 219: runq_enqueue(prev);
! 220: }
! 221: prev->resched = 0;
! 222:
! 223: /*
! 224: * Select the thread to run the CPU next.
! 225: */
! 226: next = runq_dequeue();
! 227: if (next == prev)
! 228: return;
! 229: cur_thread = next;
! 230:
! 231: /*
! 232: * Switch to the new thread.
! 233: * You are expected to understand this..
! 234: */
! 235: if (prev->task != next->task)
! 236: vm_switch(next->task->map);
! 237: context_switch(&prev->ctx, &next->ctx);
! 238: }
! 239:
! 240: /*
! 241: * sleep_expire - sleep timer is expired:
! 242: *
! 243: * Wake up the thread which is sleeping in sched_tsleep().
! 244: */
! 245: static void
! 246: sleep_expire(void *arg)
! 247: {
! 248:
! 249: sched_unsleep((thread_t)arg, SLP_TIMEOUT);
! 250: }
! 251:
! 252: /*
! 253: * sched_tsleep - sleep the current thread until a wakeup
! 254: * is performed on the specified event.
! 255: *
! 256: * This routine returns a sleep result. If the thread is
! 257: * woken by sched_wakeup() or sched_wakeone(), it returns 0.
! 258: * Otherwise, it will return the result value which is passed
! 259: * by sched_unsleep(). We allow calling sched_sleep() with
! 260: * interrupt disabled.
! 261: *
! 262: * sched_sleep() is also defined as a wrapper macro for
! 263: * sched_tsleep() without timeout. Note that all sleep
! 264: * requests are interruptible with this kernel.
! 265: */
! 266: int
! 267: sched_tsleep(struct event *evt, u_long msec)
! 268: {
! 269:
! 270: ASSERT(irq_level == 0);
! 271: ASSERT(evt);
! 272:
! 273: sched_lock();
! 274: irq_lock();
! 275:
! 276: cur_thread->slpevt = evt;
! 277: cur_thread->state |= TH_SLEEP;
! 278: enqueue(&evt->sleepq, &cur_thread->link);
! 279:
! 280: if (msec != 0) {
! 281: /*
! 282: * Program timer to wake us up at timeout.
! 283: */
! 284: timer_callout(&cur_thread->timeout, msec, &sleep_expire,
! 285: cur_thread);
! 286: }
! 287: wakeq_flush();
! 288: sched_switch(); /* Sleep here. Zzzz.. */
! 289:
! 290: irq_unlock();
! 291: sched_unlock();
! 292: return cur_thread->slpret;
! 293: }
! 294:
! 295: /*
! 296: * sched_wakeup - wake up all threads sleeping on event.
! 297: *
! 298: * A thread can have sleep and suspend state simultaneously.
! 299: * So, the thread does not always run even if it woke up.
! 300: *
! 301: * Since this routine can be called from ISR at interrupt
! 302: * level, there may be contention for access to some data.
! 303: * Thus, this routine will temporary move the waking thread
! 304: * into wakeq, and they will be moved to runq at more safer
! 305: * time in wakeq_flush().
! 306: *
! 307: * The woken thread will be put on the tail of runq
! 308: * regardless of its scheduling policy. If woken threads have
! 309: * same priority, next running thread is selected by FIFO order.
! 310: */
! 311: void
! 312: sched_wakeup(struct event *evt)
! 313: {
! 314: queue_t q;
! 315: thread_t th;
! 316:
! 317: ASSERT(evt);
! 318:
! 319: sched_lock();
! 320: irq_lock();
! 321: while (!queue_empty(&evt->sleepq)) {
! 322: /*
! 323: * Move a sleeping thread to the wake queue.
! 324: */
! 325: q = dequeue(&evt->sleepq);
! 326: th = queue_entry(q, struct thread, link);
! 327: th->slpret = 0;
! 328: enqueue(&wakeq, q);
! 329: timer_stop(&th->timeout);
! 330: }
! 331: irq_unlock();
! 332: sched_unlock();
! 333: }
! 334:
! 335: /*
! 336: * sched_wakeone - wake up one thread sleeping on event.
! 337: *
! 338: * The highest priority thread is woken among sleeping
! 339: * threads. This routine returns the thread ID of the
! 340: * woken thread, or NULL if no threads are sleeping.
! 341: */
! 342: thread_t
! 343: sched_wakeone(struct event *evt)
! 344: {
! 345: queue_t head, q;
! 346: thread_t top, th = NULL;
! 347:
! 348: sched_lock();
! 349: irq_lock();
! 350: head = &evt->sleepq;
! 351: if (!queue_empty(head)) {
! 352: /*
! 353: * Select the highet priority thread in
! 354: * the sleep queue, and wakeup it.
! 355: */
! 356: q = queue_first(head);
! 357: top = queue_entry(q, struct thread, link);
! 358: while (!queue_end(head, q)) {
! 359: th = queue_entry(q, struct thread, link);
! 360: if (th->prio < top->prio)
! 361: top = th;
! 362: q = queue_next(q);
! 363: }
! 364: queue_remove(&top->link);
! 365: top->slpret = 0;
! 366: enqueue(&wakeq, &top->link);
! 367: timer_stop(&top->timeout);
! 368: th = top;
! 369: }
! 370: irq_unlock();
! 371: sched_unlock();
! 372: return th;
! 373: }
! 374:
! 375: /*
! 376: * sched_unsleep - cancel sleep.
! 377: *
! 378: * sched_unsleep() removes the specified thread from its
! 379: * sleep queue. The specified sleep result will be passed
! 380: * to the sleeping thread as a return value of sched_tsleep().
! 381: */
! 382: void
! 383: sched_unsleep(thread_t th, int result)
! 384: {
! 385:
! 386: sched_lock();
! 387: if (th->state & TH_SLEEP) {
! 388: irq_lock();
! 389: queue_remove(&th->link);
! 390: th->slpret = result;
! 391: enqueue(&wakeq, &th->link);
! 392: timer_stop(&th->timeout);
! 393: irq_unlock();
! 394: }
! 395: sched_unlock();
! 396: }
! 397:
! 398: /*
! 399: * Yield the current processor to another thread.
! 400: *
! 401: * Note that the current thread may run immediately again,
! 402: * if no other thread exists in the same priority queue.
! 403: */
! 404: void
! 405: sched_yield(void)
! 406: {
! 407:
! 408: sched_lock();
! 409:
! 410: if (!queue_empty(&runq[cur_thread->prio]))
! 411: cur_thread->resched = 1;
! 412:
! 413: sched_unlock(); /* Switch current thread here */
! 414: }
! 415:
! 416: /*
! 417: * Suspend the specified thread.
! 418: * Called with scheduler locked.
! 419: */
! 420: void
! 421: sched_suspend(thread_t th)
! 422: {
! 423:
! 424: if (th->state == TH_RUN) {
! 425: if (th == cur_thread)
! 426: cur_thread->resched = 1;
! 427: else
! 428: runq_remove(th);
! 429: }
! 430: th->state |= TH_SUSPEND;
! 431: }
! 432:
! 433: /*
! 434: * Resume the specified thread.
! 435: * Called with scheduler locked.
! 436: */
! 437: void
! 438: sched_resume(thread_t th)
! 439: {
! 440:
! 441: if (th->state & TH_SUSPEND) {
! 442: th->state &= ~TH_SUSPEND;
! 443: if (th->state == TH_RUN)
! 444: runq_enqueue(th);
! 445: }
! 446: }
! 447:
! 448: /*
! 449: * sched_tick() is called from timer_tick() once every tick.
! 450: * Check quantum expiration, and mark a rescheduling flag.
! 451: * We don't need locking in here.
! 452: */
! 453: void
! 454: sched_tick(void)
! 455: {
! 456:
! 457: /* Profile running time. */
! 458: cur_thread->time++;
! 459:
! 460: if (cur_thread->policy == SCHED_RR) {
! 461: if (--cur_thread->timeleft <= 0) {
! 462: /*
! 463: * The quantum is up.
! 464: * Give the thread another.
! 465: */
! 466: cur_thread->timeleft += QUANTUM;
! 467: cur_thread->resched = 1;
! 468: }
! 469: }
! 470: }
! 471:
! 472: /*
! 473: * Set up stuff for thread scheduling.
! 474: */
! 475: void
! 476: sched_start(thread_t th)
! 477: {
! 478:
! 479: th->state = TH_RUN | TH_SUSPEND;
! 480: th->policy = SCHED_RR;
! 481: th->prio = PRIO_USER;
! 482: th->baseprio = PRIO_USER;
! 483: th->timeleft = QUANTUM;
! 484: }
! 485:
! 486: /*
! 487: * Stop thread scheduling.
! 488: */
! 489: void
! 490: sched_stop(thread_t th)
! 491: {
! 492:
! 493: if (th == cur_thread) {
! 494: /*
! 495: * If specified thread is current thread,
! 496: * the scheduling lock count is force set
! 497: * to 1 to ensure the thread switching in
! 498: * the next sched_unlock().
! 499: */
! 500: cur_thread->locks = 1;
! 501: cur_thread->resched = 1;
! 502: } else {
! 503: if (th->state == TH_RUN)
! 504: runq_remove(th);
! 505: else if (th->state & TH_SLEEP)
! 506: queue_remove(&th->link);
! 507: }
! 508: timer_stop(&th->timeout);
! 509: th->state = TH_EXIT;
! 510: }
! 511:
! 512: /*
! 513: * sched_lock - lock the scheduler.
! 514: *
! 515: * The thread switch is disabled during scheduler locked.
! 516: * This is mainly used to synchronize the thread execution
! 517: * to protect global resources. Even when scheduler is
! 518: * locked, an interrupt handler can run. So, we have to
! 519: * use irq_lock() to synchronize a global data with ISR.
! 520: *
! 521: * Since the scheduling lock can be nested any number of
! 522: * times, the caller has the responsible to unlock the same
! 523: * number of locks.
! 524: */
! 525: void
! 526: sched_lock(void)
! 527: {
! 528:
! 529: cur_thread->locks++;
! 530: }
! 531:
! 532: /*
! 533: * sched_unlock - unlock scheduler.
! 534: *
! 535: * If nobody locks the scheduler anymore, it checks the
! 536: * rescheduling flag and kick scheduler if it's marked.
! 537: *
! 538: * Note that this routine will be always called at the end
! 539: * of each interrupt handler.
! 540: */
! 541: void
! 542: sched_unlock(void)
! 543: {
! 544: int s;
! 545:
! 546: ASSERT(cur_thread->locks > 0);
! 547:
! 548: interrupt_save(&s);
! 549: interrupt_disable();
! 550:
! 551: if (cur_thread->locks == 1) {
! 552: wakeq_flush();
! 553: while (cur_thread->resched) {
! 554:
! 555: /* Kick scheduler */
! 556: sched_switch();
! 557:
! 558: /*
! 559: * Now we run pending interrupts which fired
! 560: * during the thread switch. So, we can catch
! 561: * the rescheduling request from such ISRs.
! 562: * Otherwise, the reschedule may be deferred
! 563: * until _next_ sched_unlock() call.
! 564: */
! 565: interrupt_restore(s);
! 566: interrupt_disable();
! 567: wakeq_flush();
! 568: }
! 569: }
! 570: cur_thread->locks--;
! 571:
! 572: interrupt_restore(s);
! 573: }
! 574:
! 575: int
! 576: sched_getprio(thread_t th)
! 577: {
! 578:
! 579: return th->prio;
! 580: }
! 581:
! 582: /*
! 583: * sched_setprio - set priority of thread.
! 584: *
! 585: * The rescheduling flag is set if the priority is
! 586: * better than the currently running thread.
! 587: * Called with scheduler locked.
! 588: */
! 589: void
! 590: sched_setprio(thread_t th, int baseprio, int prio)
! 591: {
! 592:
! 593: th->baseprio = baseprio;
! 594:
! 595: if (th == cur_thread) {
! 596: /*
! 597: * If we change the current thread's priority,
! 598: * rescheduling may be happened.
! 599: */
! 600: th->prio = prio;
! 601: top_prio = runq_top();
! 602: if (prio != top_prio)
! 603: cur_thread->resched = 1;
! 604: } else {
! 605: if (th->state == TH_RUN) {
! 606: /*
! 607: * Update the thread priority and adjust
! 608: * the run queue position for new priority.
! 609: */
! 610: runq_remove(th);
! 611: th->prio = prio;
! 612: runq_enqueue(th);
! 613: } else
! 614: th->prio = prio;
! 615: }
! 616: }
! 617:
! 618: int
! 619: sched_getpolicy(thread_t th)
! 620: {
! 621:
! 622: return th->policy;
! 623: }
! 624:
! 625: int
! 626: sched_setpolicy(thread_t th, int policy)
! 627: {
! 628: int err = 0;
! 629:
! 630: switch (policy) {
! 631: case SCHED_RR:
! 632: case SCHED_FIFO:
! 633: th->timeleft = QUANTUM;
! 634: th->policy = policy;
! 635: break;
! 636: default:
! 637: err = -1;
! 638: break;
! 639: }
! 640: return err;
! 641: }
! 642:
! 643: /*
! 644: * Schedule DPC callback.
! 645: *
! 646: * DPC (Deferred Procedure Call) is used to call the specific
! 647: * function at some later time with a DPC priority. It is also
! 648: * known as AST or SoftIRQ in other kernels. DPC is typically
! 649: * used by device drivers to do the low-priority jobs without
! 650: * degrading real-time performance.
! 651: * This routine can be called from ISR.
! 652: */
! 653: void
! 654: sched_dpc(struct dpc *dpc, void (*func)(void *), void *arg)
! 655: {
! 656: ASSERT(dpc);
! 657: ASSERT(func);
! 658:
! 659: irq_lock();
! 660: /*
! 661: * Insert request to DPC queue.
! 662: */
! 663: dpc->func = func;
! 664: dpc->arg = arg;
! 665: if (dpc->state != DPC_PENDING)
! 666: enqueue(&dpcq, &dpc->link);
! 667: dpc->state = DPC_PENDING;
! 668:
! 669: /* Wake DPC thread */
! 670: sched_wakeup(&dpc_event);
! 671:
! 672: irq_unlock();
! 673: }
! 674:
! 675: /*
! 676: * DPC thread.
! 677: *
! 678: * This is a kernel thread to process the pending call back
! 679: * request within DPC queue. Each DPC routine is called with
! 680: * the following conditions.
! 681: * - Interrupt is enabled.
! 682: * - Scheduler is unlocked.
! 683: */
! 684: static void
! 685: dpc_thread(void *arg)
! 686: {
! 687: queue_t q;
! 688: struct dpc *dpc;
! 689:
! 690: for (;;) {
! 691: /* Wait until next DPC request. */
! 692: sched_sleep(&dpc_event);
! 693:
! 694: while (!queue_empty(&dpcq)) {
! 695: q = dequeue(&dpcq);
! 696: dpc = queue_entry(q, struct dpc, link);
! 697: dpc->state = DPC_FREE;
! 698:
! 699: /*
! 700: * Call DPC routine.
! 701: */
! 702: interrupt_enable();
! 703: (*dpc->func)(dpc->arg);
! 704: interrupt_disable();
! 705: }
! 706: }
! 707: /* NOTREACHED */
! 708: }
! 709:
! 710: /*
! 711: * Initialize the global scheduler state.
! 712: */
! 713: void
! 714: sched_init(void)
! 715: {
! 716: thread_t th;
! 717: int i;
! 718:
! 719: for (i = 0; i < NPRIO; i++)
! 720: queue_init(&runq[i]);
! 721: queue_init(&wakeq);
! 722: queue_init(&dpcq);
! 723: event_init(&dpc_event, "dpc");
! 724: top_prio = PRIO_IDLE;
! 725: cur_thread->resched = 1;
! 726:
! 727: /* Create a DPC thread. */
! 728: th = kthread_create(dpc_thread, NULL, PRIO_DPC);
! 729: if (th == NULL)
! 730: panic("sched_init");
! 731:
! 732: DPRINTF(("Time slice is %d msec\n", CONFIG_TIME_SLICE));
! 733: }
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to sched.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / prex / sys / kern