Prex Home / Browse Source - Prex Version: 0.9.0

root/sys/kern/sched.c

/* [<][>][^][v][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. runq_getbest
  2. runq_enqueue
  3. runq_insert
  4. runq_dequeue
  5. runq_remove
  6. wakeq_flush
  7. sched_setrun
  8. sched_swtch
  9. sleep_timeout
  10. sched_tsleep
  11. sched_wakeup
  12. sched_wakeone
  13. sched_unsleep
  14. sched_yield
  15. sched_suspend
  16. sched_resume
  17. sched_tick
  18. sched_start
  19. sched_stop
  20. sched_lock
  21. sched_unlock
  22. sched_getpri
  23. sched_setpri
  24. sched_getpolicy
  25. sched_setpolicy
  26. sched_dpc
  27. dpc_thread
  28. sched_init

   1 /*-
   2  * Copyright (c) 2005-2009, 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 assigned
  39  * between 0 and 255. The lower number means higher priority like BSD
  40  * UNIX.  The scheduler maintains 256 level run queues mapped to each
  41  * priority.  The lowest priority (=255) is used only for an idle
  42  * 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  *  - TS_RUN     Running or ready to run
  57  *  - TS_SLEEP   Sleep for some event
  58  *  - TS_SUSP    Suspend count is not 0
  59  *  - TS_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  *
  67  * (2) Preemption
  68  *      Higher priority thread becomes runnable.
  69  *
  70  * (3) Quantum expiration
  71  *      The thread consumes its time quantum.
  72  *
  73  * (4) Yield
  74  *      The thread releases CPU by itself.
  75  *
  76  * There are following three types of scheduling policies.
  77  *
  78  *  - SCHED_FIFO   First in-first-out
  79  *  - SCHED_RR     Round robin (SCHED_FIFO + timeslice)
  80  *  - SCHED_OTHER  Not supported now
  81  */
  82 
  83 #include <kernel.h>
  84 #include <event.h>
  85 #include <thread.h>
  86 #include <timer.h>
  87 #include <vm.h>
  88 #include <task.h>
  89 #include <sched.h>
  90 #include <hal.h>
  91 
  92 static struct queue     runq[NPRI];     /* run queues */
  93 static struct queue     wakeq;          /* queue for waking threads */
  94 static struct queue     dpcq;           /* DPC queue */
  95 static struct event     dpc_event;      /* event for DPC */
  96 static int              maxpri;         /* highest priority in runq */
  97 
  98 /*
  99  * Search for highest-priority runnable thread.
 100  */
 101 static int
 102 runq_getbest(void)
 103 {
 104         int pri;
 105 
 106         for (pri = 0; pri < MINPRI; pri++)
 107                 if (!queue_empty(&runq[pri]))
 108                         break;
 109         return pri;
 110 }
 111 
 112 /*
 113  * Put a thread on the tail of the run queue.
 114  * The rescheduling flag is set if the priority is beter
 115  * than the currently running thread.
 116  */
 117 static void
 118 runq_enqueue(thread_t t)
 119 {
 120 
 121         enqueue(&runq[t->priority], &t->sched_link);
 122         if (t->priority < maxpri) {
 123                 maxpri = t->priority;
 124                 curthread->resched = 1;
 125         }
 126 }
 127 
 128 /*
 129  * Insert a thread to the head of the run queue.
 130  * We assume this routine is called while thread switching.
 131  */
 132 static void
 133 runq_insert(thread_t t)
 134 {
 135 
 136         queue_insert(&runq[t->priority], &t->sched_link);
 137         if (t->priority < maxpri)
 138                 maxpri = t->priority;
 139 }
 140 
 141 /*
 142  * Pick up and remove the highest-priority thread
 143  * from the run queue.
 144  */
 145 static thread_t
 146 runq_dequeue(void)
 147 {
 148         queue_t q;
 149         thread_t t;
 150 
 151         q = dequeue(&runq[maxpri]);
 152         t = queue_entry(q, struct thread, sched_link);
 153         if (queue_empty(&runq[maxpri]))
 154                 maxpri = runq_getbest();
 155 
 156         return t;
 157 }
 158 
 159 /*
 160  * Remove the specified thread from the run queue.
 161  */
 162 static void
 163 runq_remove(thread_t t)
 164 {
 165 
 166         queue_remove(&t->sched_link);
 167         maxpri = runq_getbest();
 168 }
 169 
 170 /*
 171  * Wake up all threads in the wake queue.
 172  */
 173 static void
 174 wakeq_flush(void)
 175 {
 176         queue_t q;
 177         thread_t t;
 178 
 179         while (!queue_empty(&wakeq)) {
 180                 /*
 181                  * Set a thread runnable.
 182                  */
 183                 q = dequeue(&wakeq);
 184                 t = queue_entry(q, struct thread, sched_link);
 185                 t->slpevt = NULL;
 186                 t->state &= ~TS_SLEEP;
 187                 if (t != curthread && t->state == TS_RUN)
 188                         runq_enqueue(t);
 189         }
 190 }
 191 
 192 /*
 193  * Set the thread running:
 194  * Put a thread on the wake queue. This thread will be moved
 195  * to the run queue later in wakeq_flush().
 196  */
 197 static void
 198 sched_setrun(thread_t t)
 199 {
 200 
 201         enqueue(&wakeq, &t->sched_link);
 202         timer_stop(&t->timeout);
 203 }
 204 
 205 /*
 206  * sched_swtch - this is the scheduler proper:
 207  *
 208  * If the scheduling reason is preemption, the current thread
 209  * will remain at the head of the run queue.  So, the thread
 210  * still has right to run next again among the same priority
 211  * threads. For other scheduling reason, the current thread is
 212  * inserted into the tail of the run queue.
 213  */
 214 static void
 215 sched_swtch(void)
 216 {
 217         thread_t prev, next;
 218 
 219         /*
 220          * Put the current thread on the run queue.
 221          */
 222         prev = curthread;
 223         if (prev->state == TS_RUN) {
 224                 if (prev->priority > maxpri)
 225                         runq_insert(prev);      /* preemption */
 226                 else
 227                         runq_enqueue(prev);
 228         }
 229         prev->resched = 0;
 230 
 231         /*
 232          * Select the thread to run the CPU next.
 233          * If it's same with previous one, return.
 234          */
 235         next = runq_dequeue();
 236         if (next == prev)
 237                 return;
 238         curthread = next;
 239 
 240         /*
 241          * Switch to the new thread.
 242          * You are expected to understand this..
 243          */
 244         if (prev->task != next->task)
 245                 vm_switch(next->task->map);
 246         context_switch(&prev->ctx, &next->ctx);
 247 }
 248 
 249 /*
 250  * sleep_timeout - sleep timer is expired:
 251  *
 252  * Wake up the thread which is sleeping in sched_tsleep().
 253  */
 254 static void
 255 sleep_timeout(void *arg)
 256 {
 257         thread_t t = (thread_t)arg;
 258 
 259         sched_unsleep(t, SLP_TIMEOUT);
 260 }
 261 
 262 /*
 263  * sched_tsleep - sleep the current thread until a wakeup
 264  * is performed on the specified event.
 265  * This routine returns a sleep result.
 266  */
 267 int
 268 sched_tsleep(struct event *evt, u_long msec)
 269 {
 270         int s;
 271 
 272         ASSERT(evt != NULL);
 273 
 274         sched_lock();
 275         s = splhigh();
 276 
 277         /*
 278          * Put the current thread on the sleep queue.
 279          */
 280         curthread->slpevt = evt;
 281         curthread->state |= TS_SLEEP;
 282         enqueue(&evt->sleepq, &curthread->sched_link);
 283 
 284         /*
 285          * Program timer to wake us up at timeout.
 286          */
 287         if (msec != 0) {
 288                 timer_callout(&curthread->timeout, msec,
 289                               &sleep_timeout, curthread);
 290         }
 291 
 292         wakeq_flush();
 293         sched_swtch();          /* Sleep here. Zzzz.. */
 294 
 295         splx(s);
 296         sched_unlock();
 297         return curthread->slpret;
 298 }
 299 
 300 /*
 301  * sched_wakeup - wake up all threads sleeping on event.
 302  *
 303  * A thread can have sleep and suspend state simultaneously.
 304  * So, the thread may keep suspending even if it woke up.
 305  */
 306 void
 307 sched_wakeup(struct event *evt)
 308 {
 309         queue_t q;
 310         thread_t t;
 311         int s;
 312 
 313         ASSERT(evt != NULL);
 314 
 315         sched_lock();
 316         s = splhigh();
 317         while (!queue_empty(&evt->sleepq)) {
 318                 q = dequeue(&evt->sleepq);
 319                 t = queue_entry(q, struct thread, sched_link);
 320                 t->slpret = 0;
 321                 sched_setrun(t);
 322         }
 323         splx(s);
 324         sched_unlock();
 325 }
 326 
 327 /*
 328  * sched_wakeone - wake up one thread sleeping on event.
 329  *
 330  * The highest priority thread is woken among sleeping
 331  * threads. This routine returns the thread ID of the
 332  * woken thread, or NULL if no threads are sleeping.
 333  */
 334 thread_t
 335 sched_wakeone(struct event *evt)
 336 {
 337         queue_t head, q;
 338         thread_t top, t = NULL;
 339         int s;
 340 
 341         sched_lock();
 342         s = splhigh();
 343         head = &evt->sleepq;
 344         if (!queue_empty(head)) {
 345                 /*
 346                  * Select the highet priority thread in
 347                  * the sleep queue, and wake it up.
 348                  */
 349                 q = queue_first(head);
 350                 top = queue_entry(q, struct thread, sched_link);
 351                 while (!queue_end(head, q)) {
 352                         t = queue_entry(q, struct thread, sched_link);
 353                         if (t->priority < top->priority)
 354                                 top = t;
 355                         q = queue_next(q);
 356                 }
 357                 queue_remove(&top->sched_link);
 358                 top->slpret = 0;
 359                 sched_setrun(top);
 360         }
 361         splx(s);
 362         sched_unlock();
 363         return t;
 364 }
 365 
 366 /*
 367  * sched_unsleep - cancel sleep.
 368  *
 369  * sched_unsleep() removes the specified thread from its
 370  * sleep queue. The specified sleep result will be passed
 371  * to the sleeping thread as a return value of sched_tsleep().
 372  */
 373 void
 374 sched_unsleep(thread_t t, int result)
 375 {
 376         int s;
 377 
 378         sched_lock();
 379         if (t->state & TS_SLEEP) {
 380                 s = splhigh();
 381                 queue_remove(&t->sched_link);
 382                 t->slpret = result;
 383                 sched_setrun(t);
 384                 splx(s);
 385         }
 386         sched_unlock();
 387 }
 388 
 389 /*
 390  * Yield the current processor to another thread.
 391  *
 392  * Note that the current thread may run immediately again,
 393  * if no other thread exists in the same priority queue.
 394  */
 395 void
 396 sched_yield(void)
 397 {
 398 
 399         sched_lock();
 400 
 401         if (!queue_empty(&runq[curthread->priority]))
 402                 curthread->resched = 1;
 403 
 404         sched_unlock();         /* Switch a current thread here */
 405 }
 406 
 407 /*
 408  * Suspend the specified thread.
 409  * Called with scheduler locked.
 410  */
 411 void
 412 sched_suspend(thread_t t)
 413 {
 414 
 415         if (t->state == TS_RUN) {
 416                 if (t == curthread)
 417                         curthread->resched = 1;
 418                 else
 419                         runq_remove(t);
 420         }
 421         t->state |= TS_SUSP;
 422 }
 423 
 424 /*
 425  * Resume the specified thread.
 426  * Called with scheduler locked.
 427  */
 428 void
 429 sched_resume(thread_t t)
 430 {
 431 
 432         if (t->state & TS_SUSP) {
 433                 t->state &= ~TS_SUSP;
 434                 if (t->state == TS_RUN)
 435                         runq_enqueue(t);
 436         }
 437 }
 438 
 439 /*
 440  * sched_tick() is called from timer_clock() once every tick.
 441  * Check quantum expiration, and mark a rescheduling flag.
 442  * We don't need locking in here.
 443  */
 444 void
 445 sched_tick(void)
 446 {
 447 
 448         if (curthread->state != TS_EXIT) {
 449                 /*
 450                  * Bill time to current thread.
 451                  */
 452                 curthread->time++;
 453 
 454                 if (curthread->policy == SCHED_RR) {
 455                         if (--curthread->timeleft <= 0) {
 456                                 /*
 457                                  * The quantum is up.
 458                                  * Give the thread another.
 459                                  */
 460                                 curthread->timeleft += QUANTUM;
 461                                 curthread->resched = 1;
 462                         }
 463                 }
 464         }
 465 }
 466 
 467 /*
 468  * Setup the thread structure to start scheduling.
 469  */
 470 void
 471 sched_start(thread_t t, int pri, int policy)
 472 {
 473 
 474         t->state = TS_RUN | TS_SUSP;
 475         t->policy = policy;
 476         t->priority = pri;
 477         t->basepri = pri;
 478         if (t->policy == SCHED_RR)
 479                 t->timeleft = QUANTUM;
 480 }
 481 
 482 /*
 483  * Stop scheduling of the specified thread.
 484  */
 485 void
 486 sched_stop(thread_t t)
 487 {
 488 
 489         if (t == curthread) {
 490                 /*
 491                  * If specified thread is a current thread,
 492                  * the scheduling lock count is force set
 493                  * to 1 to ensure the thread switching in
 494                  * the next sched_unlock().
 495                  */
 496                 curthread->locks = 1;
 497                 curthread->resched = 1;
 498         } else {
 499                 if (t->state == TS_RUN)
 500                         runq_remove(t);
 501                 else if (t->state & TS_SLEEP)
 502                         queue_remove(&t->sched_link);
 503         }
 504         timer_stop(&t->timeout);
 505         t->state = TS_EXIT;
 506 }
 507 
 508 /*
 509  * sched_lock - lock the scheduler.
 510  *
 511  * The thread switch is disabled during scheduler locked.
 512  * Since the scheduling lock can be nested any number of
 513  * times, the caller has the responsible to unlock the same
 514  * number of locks.
 515  */
 516 void
 517 sched_lock(void)
 518 {
 519 
 520         curthread->locks++;
 521 }
 522 
 523 /*
 524  * sched_unlock - unlock scheduler.
 525  *
 526  * If nobody locks the scheduler anymore, it checks the
 527  * rescheduling flag and kick the scheduler if it's required.
 528  * This routine will be always called at the end of each
 529  * interrupt handler.
 530  */
 531 void
 532 sched_unlock(void)
 533 {
 534         int s;
 535 
 536         ASSERT(curthread->locks > 0);
 537 
 538         s = splhigh();
 539         if (curthread->locks == 1) {
 540                 wakeq_flush();
 541                 while (curthread->resched) {
 542                         /*
 543                          * Kick scheduler.
 544                          */
 545                         sched_swtch();
 546 
 547                         /*
 548                          * Now we run pending interrupts which fired
 549                          * during the thread switch. So, we can catch
 550                          * the rescheduling request from such ISRs.
 551                          * Otherwise, the reschedule may be deferred
 552                          * until _next_ sched_unlock() call.
 553                          */
 554                         splx(s);
 555                         s = splhigh();
 556                         wakeq_flush();
 557                 }
 558         }
 559         curthread->locks--;
 560         splx(s);
 561 }
 562 
 563 /*
 564  * Return the priority of the specified thread.
 565  */
 566 int
 567 sched_getpri(thread_t t)
 568 {
 569 
 570         return t->priority;
 571 }
 572 
 573 /*
 574  * sched_setpri - set priority of thread.
 575  *
 576  * Arrange to reschedule if the resulting priority is
 577  * better than that of the current thread.
 578  * Called with scheduler locked.
 579  */
 580 void
 581 sched_setpri(thread_t t, int basepri, int pri)
 582 {
 583 
 584         t->basepri = basepri;
 585 
 586         if (t == curthread) {
 587                 /*
 588                  * If we change the current thread's priority,
 589                  * rescheduling may be happened.
 590                  */
 591                 t->priority = pri;
 592                 maxpri = runq_getbest();
 593                 if (pri != maxpri)
 594                         curthread->resched = 1;
 595         } else {
 596                 if (t->state == TS_RUN) {
 597                         /*
 598                          * Update the thread priority and adjust
 599                          * the run queue position for new priority.
 600                          * The rescheduling flag may be set.
 601                          */
 602                         runq_remove(t);
 603                         t->priority = pri;
 604                         runq_enqueue(t);
 605                 } else
 606                         t->priority = pri;
 607         }
 608 }
 609 
 610 /*
 611  * Get the scheduling policy.
 612  */
 613 int
 614 sched_getpolicy(thread_t t)
 615 {
 616 
 617         return t->policy;
 618 }
 619 
 620 /*
 621  * Set the scheduling policy.
 622  */
 623 int
 624 sched_setpolicy(thread_t t, int policy)
 625 {
 626         int error = 0;
 627 
 628         switch (policy) {
 629         case SCHED_RR:
 630         case SCHED_FIFO:
 631                 t->timeleft = QUANTUM;
 632                 t->policy = policy;
 633                 break;
 634         default:
 635                 error = EINVAL;
 636                 break;
 637         }
 638         return error;
 639 }
 640 
 641 /*
 642  * Schedule DPC callback.
 643  *
 644  * DPC (Deferred Procedure Call) is used to call the specific
 645  * function at some later time with a DPC priority.
 646  * This routine can be called from ISR.
 647  */
 648 void
 649 sched_dpc(struct dpc *dpc, void (*fn)(void *), void *arg)
 650 {
 651         int s;
 652 
 653         ASSERT(dpc != NULL);
 654         ASSERT(fn != NULL);
 655 
 656         sched_lock();
 657 
 658         s = splhigh();
 659         dpc->func = fn;
 660         dpc->arg = arg;
 661         if (dpc->state != DPC_PENDING)
 662                 enqueue(&dpcq, &dpc->link);
 663         dpc->state = DPC_PENDING;
 664         splx(s);
 665 
 666         sched_wakeup(&dpc_event);
 667         sched_unlock();
 668 }
 669 
 670 /*
 671  * DPC thread.
 672  *
 673  * This is a kernel thread to process the pending call back
 674  * request in DPC queue. Each DPC routine is called with
 675  * the following conditions.
 676  *  - Interrupt is enabled.
 677  *  - Scheduler is unlocked.
 678  *  - The scheduling priority is PRI_DPC.
 679  */
 680 static void
 681 dpc_thread(void *dummy)
 682 {
 683         queue_t q;
 684         struct dpc *dpc;
 685 
 686         splhigh();
 687 
 688         for (;;) {
 689                 /*
 690                  * Wait until next DPC request.
 691                  */
 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                         spl0();
 703                         (*dpc->func)(dpc->arg);
 704                         splhigh();
 705                 }
 706         }
 707         /* NOTREACHED */
 708 }
 709 
 710 /*
 711  * Initialize the global scheduler state.
 712  */
 713 void
 714 sched_init(void)
 715 {
 716         thread_t t;
 717         int i;
 718 
 719         for (i = 0; i < NPRI; i++)
 720                 queue_init(&runq[i]);
 721 
 722         queue_init(&wakeq);
 723         queue_init(&dpcq);
 724         event_init(&dpc_event, "dpc");
 725         maxpri = PRI_IDLE;
 726         curthread->resched = 1;
 727 
 728         t = kthread_create(dpc_thread, NULL, PRI_DPC);
 729         if (t == NULL)
 730                 panic("sched_init");
 731 
 732         DPRINTF(("Time slice is %d msec\n", CONFIG_TIME_SLICE));
 733 }

/* [<][>][^][v][top][bottom][index][help] */