Prex Home / Browse Source - Prex Version: 0.9.0

root/sys/kern/sched.c

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  */
  30 /*
  31  * sched.c - scheduler
  32  */
  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  */
  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>
  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 */
  98 /*
  99  * Search for highest-priority runnable thread.
 100  */
 101 static int
runq_getbest(void)
 103 {
 104         int pri;
 106         for (pri = 0; pri < MINPRI; pri++)
 107                 if (!queue_empty(&runq[pri]))
 108                         break;
 109         return pri;
 110 }
 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
runq_enqueue(thread_t t)
 119 {
enqueue(&runq[t->priority], &t->sched_link);
 122         if (t->priority < maxpri) {
maxpri = t->priority;
curthread->resched = 1;
 125         }
 126 }
 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
runq_insert(thread_t t)
 134 {
queue_insert(&runq[t->priority], &t->sched_link);
 137         if (t->priority < maxpri)
maxpri = t->priority;
 139 }
 141 /*
 142  * Pick up and remove the highest-priority thread
 143  * from the run queue.
 144  */
 145 static thread_t
runq_dequeue(void)
 147 {
queue_t q;
thread_t t;
q = dequeue(&runq[maxpri]);
t = queue_entry(q, struct thread, sched_link);
 153         if (queue_empty(&runq[maxpri]))
maxpri = runq_getbest();
 156         return t;
 157 }
 159 /*
 160  * Remove the specified thread from the run queue.
 161  */
 162 static void
runq_remove(thread_t t)
 164 {
queue_remove(&t->sched_link);
maxpri = runq_getbest();
 168 }
 170 /*
 171  * Wake up all threads in the wake queue.
 172  */
 173 static void
wakeq_flush(void)
 175 {
queue_t q;
thread_t t;
 179         while (!queue_empty(&wakeq)) {
 180                 /*
 181                  * Set a thread runnable.
 182                  */
q = dequeue(&wakeq);
t = queue_entry(q, struct thread, sched_link);
t->slpevt = NULL;
t->state &= ~TS_SLEEP;
 187                 if (t != curthread && t->state == TS_RUN)
runq_enqueue(t);
 189         }
 190 }
 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
sched_setrun(thread_t t)
 199 {
enqueue(&wakeq, &t->sched_link);
timer_stop(&t->timeout);
 203 }
 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
sched_swtch(void)
 216 {
thread_t prev, next;
 219         /*
 220          * Put the current thread on the run queue.
 221          */
prev = curthread;
 223         if (prev->state == TS_RUN) {
 224                 if (prev->priority > maxpri)
runq_insert(prev);      /* preemption */
 226                 else
runq_enqueue(prev);
 228         }
prev->resched = 0;
 231         /*
 232          * Select the thread to run the CPU next.
 233          * If it's same with previous one, return.
 234          */
next = runq_dequeue();
 236         if (next == prev)
 237                 return;
curthread = next;
 240         /*
 241          * Switch to the new thread.
 242          * You are expected to understand this..
 243          */
 244         if (prev->task != next->task)
vm_switch(next->task->map);
context_switch(&prev->ctx, &next->ctx);
 247 }
 249 /*
 250  * sleep_timeout - sleep timer is expired:
 251  *
 252  * Wake up the thread which is sleeping in sched_tsleep().
 253  */
 254 static void
sleep_timeout(void *arg)
 256 {
thread_t t = (thread_t)arg;
sched_unsleep(t, SLP_TIMEOUT);
 260 }
 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
sched_tsleep(struct event *evt, u_long msec)
 269 {
 270         int s;
ASSERT(evt != NULL);
sched_lock();
s = splhigh();
 277         /*
 278          * Put the current thread on the sleep queue.
 279          */
curthread->slpevt = evt;
curthread->state |= TS_SLEEP;
enqueue(&evt->sleepq, &curthread->sched_link);
 284         /*
 285          * Program timer to wake us up at timeout.
 286          */
 287         if (msec != 0) {
timer_callout(&curthread->timeout, msec,
 289                               &sleep_timeout, curthread);
 290         }
wakeq_flush();
sched_swtch();          /* Sleep here. Zzzz.. */
splx(s);
sched_unlock();
 297         return curthread->slpret;
 298 }
 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
sched_wakeup(struct event *evt)
 308 {
queue_t q;
thread_t t;
 311         int s;
ASSERT(evt != NULL);
sched_lock();
s = splhigh();
 317         while (!queue_empty(&evt->sleepq)) {
q = dequeue(&evt->sleepq);
t = queue_entry(q, struct thread, sched_link);
t->slpret = 0;
sched_setrun(t);
 322         }
splx(s);
sched_unlock();
 325 }
 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  */
thread_t
sched_wakeone(struct event *evt)
 336 {
queue_t head, q;
thread_t top, t = NULL;
 339         int s;
sched_lock();
s = splhigh();
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                  */
q = queue_first(head);
top = queue_entry(q, struct thread, sched_link);
 351                 while (!queue_end(head, q)) {
t = queue_entry(q, struct thread, sched_link);
 353                         if (t->priority < top->priority)
top = t;
q = queue_next(q);
 356                 }
queue_remove(&top->sched_link);
top->slpret = 0;
sched_setrun(top);
 360         }
splx(s);
sched_unlock();
 363         return t;
 364 }
 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
sched_unsleep(thread_t t, int result)
 375 {
 376         int s;
sched_lock();
 379         if (t->state & TS_SLEEP) {
s = splhigh();
queue_remove(&t->sched_link);
t->slpret = result;
sched_setrun(t);
splx(s);
 385         }
sched_unlock();
 387 }
 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
sched_yield(void)
 397 {
sched_lock();
 401         if (!queue_empty(&runq[curthread->priority]))
curthread->resched = 1;
sched_unlock();         /* Switch a current thread here */
 405 }
 407 /*
 408  * Suspend the specified thread.
 409  * Called with scheduler locked.
 410  */
 411 void
sched_suspend(thread_t t)
 413 {
 415         if (t->state == TS_RUN) {
 416                 if (t == curthread)
curthread->resched = 1;
 418                 else
runq_remove(t);
 420         }
t->state |= TS_SUSP;
 422 }
 424 /*
 425  * Resume the specified thread.
 426  * Called with scheduler locked.
 427  */
 428 void
sched_resume(thread_t t)
 430 {
 432         if (t->state & TS_SUSP) {
t->state &= ~TS_SUSP;
 434                 if (t->state == TS_RUN)
runq_enqueue(t);
 436         }
 437 }
 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
sched_tick(void)
 446 {
 448         if (curthread->state != TS_EXIT) {
 449                 /*
 450                  * Bill time to current thread.
 451                  */
curthread->time++;
 454                 if (curthread->policy == SCHED_RR) {
 455                         if (--curthread->timeleft <= 0) {
 456                                 /*
 457                                  * The quantum is up.
 458                                  * Give the thread another.
 459                                  */
curthread->timeleft += QUANTUM;
curthread->resched = 1;
 462                         }
 463                 }
 464         }
 465 }
 467 /*
 468  * Setup the thread structure to start scheduling.
 469  */
 470 void
sched_start(thread_t t, int pri, int policy)
 472 {
t->state = TS_RUN | TS_SUSP;
t->policy = policy;
t->priority = pri;
t->basepri = pri;
 478         if (t->policy == SCHED_RR)
t->timeleft = QUANTUM;
 480 }
 482 /*
 483  * Stop scheduling of the specified thread.
 484  */
 485 void
sched_stop(thread_t t)
 487 {
 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                  */
curthread->locks = 1;
curthread->resched = 1;
 498         } else {
 499                 if (t->state == TS_RUN)
runq_remove(t);
 501                 else if (t->state & TS_SLEEP)
queue_remove(&t->sched_link);
 503         }
timer_stop(&t->timeout);
t->state = TS_EXIT;
 506 }
 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
sched_lock(void)
 518 {
curthread->locks++;
 521 }
 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
sched_unlock(void)
 533 {
 534         int s;
ASSERT(curthread->locks > 0);
s = splhigh();
 539         if (curthread->locks == 1) {
wakeq_flush();
 541                 while (curthread->resched) {
 542                         /*
 543                          * Kick scheduler.
 544                          */
sched_swtch();
 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                          */
splx(s);
s = splhigh();
wakeq_flush();
 557                 }
 558         }
curthread->locks--;
splx(s);
 561 }
 563 /*
 564  * Return the priority of the specified thread.
 565  */
 566 int
sched_getpri(thread_t t)
 568 {
 570         return t->priority;
 571 }
 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
sched_setpri(thread_t t, int basepri, int pri)
 582 {
t->basepri = basepri;
 586         if (t == curthread) {
 587                 /*
 588                  * If we change the current thread's priority,
 589                  * rescheduling may be happened.
 590                  */
t->priority = pri;
maxpri = runq_getbest();
 593                 if (pri != maxpri)
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                          */
runq_remove(t);
t->priority = pri;
runq_enqueue(t);
 605                 } else
t->priority = pri;
 607         }
 608 }
 610 /*
 611  * Get the scheduling policy.
 612  */
 613 int
sched_getpolicy(thread_t t)
 615 {
 617         return t->policy;
 618 }
 620 /*
 621  * Set the scheduling policy.
 622  */
 623 int
sched_setpolicy(thread_t t, int policy)
 625 {
 626         int error = 0;
 628         switch (policy) {
 629         case SCHED_RR:
 630         case SCHED_FIFO:
t->timeleft = QUANTUM;
t->policy = policy;
 633                 break;
 634         default:
error = EINVAL;
 636                 break;
 637         }
 638         return error;
 639 }
 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
sched_dpc(struct dpc *dpc, void (*fn)(void *), void *arg)
 650 {
 651         int s;
ASSERT(dpc != NULL);
ASSERT(fn != NULL);
sched_lock();
s = splhigh();
dpc->func = fn;
dpc->arg = arg;
 661         if (dpc->state != DPC_PENDING)
enqueue(&dpcq, &dpc->link);
dpc->state = DPC_PENDING;
splx(s);
sched_wakeup(&dpc_event);
sched_unlock();
 668 }
 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
dpc_thread(void *dummy)
 682 {
queue_t q;
 684         struct dpc *dpc;
splhigh();
 688         for (;;) {
 689                 /*
 690                  * Wait until next DPC request.
 691                  */
sched_sleep(&dpc_event);
 694                 while (!queue_empty(&dpcq)) {
q = dequeue(&dpcq);
dpc = queue_entry(q, struct dpc, link);
dpc->state = DPC_FREE;
 699                         /*
 700                          * Call DPC routine.
 701                          */
spl0();
 703                         (*dpc->func)(dpc->arg);
splhigh();
 705                 }
 706         }
 707         /* NOTREACHED */
 708 }
 710 /*
 711  * Initialize the global scheduler state.
 712  */
 713 void
sched_init(void)
 715 {
thread_t t;
 717         int i;
 719         for (i = 0; i < NPRI; i++)
queue_init(&runq[i]);
queue_init(&wakeq);
queue_init(&dpcq);
event_init(&dpc_event, "dpc");
maxpri = PRI_IDLE;
curthread->resched = 1;
t = kthread_create(dpc_thread, NULL, PRI_DPC);
 729         if (t == NULL)
panic("sched_init");
DPRINTF(("Time slice is %d msec\n", CONFIG_TIME_SLICE));
 733 }