Annotation of prex-old/sys/kern/sched.c, Revision 1.1.1.1
1.1 nbrk 1: /*-
2: * Copyright (c) 2005-2007, 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 based
38: * multi level queue. Each thread is assigned the priority between
39: * 0 and 255. The lower number means higher priority like BSD unix.
40: * The scheduler maintains 256 level run queues mapped to each priority.
41: * The lowest priority (=255) is used only by an idle thread.
42: *
43: * All threads have two different types of priorities:
44: *
45: * - Base priority
46: * This is a static priority used for priority computation. A user
47: * mode program can change this value via system call.
48: *
49: * - Current priority
50: * An actual scheduling priority. A kernel may adjust this priority
51: * dynamically if it's needed.
52: *
53: * Each thread has one of the following state.
54: *
55: * - TH_RUN Running or ready to run
56: * - TH_SLEEP Sleep for some event
57: * - TH_SUSPEND Suspend count is not 0
58: * - TH_EXIT Terminated
59: *
60: * The thread is always preemptive even in the kernel mode.
61: * There are following 4 reasons to switch thread.
62: *
63: * 1) Block
64: * Thread is blocked for sleep or suspend.
65: * It is put on the tail of the run queue when it becomes
66: * runnable again.
67: *
68: * 2) Preemption
69: * If higher priority thread becomes runnable, the current
70: * thread is put on the the _head_ of the run queue.
71: *
72: * 3) Quantum expiration
73: * If the thread consumes its time quantum, it is put on
74: * the tail of the run queue.
75: *
76: * 4) Yield
77: * If the thread releases CPU by itself, it is put on
78: * the tail of the run queue.
79: *
80: * There are following three types of scheduling policies.
81: *
82: * - SCHED_FIFO First in-first-out
83: * - SCHED_RR Round robin (SCHED_FIFO + timeslice)
84: * - SCHED_OTHER Another scheduling (not supported)
85: */
86:
87: #include <kernel.h>
88: #include <queue.h>
89: #include <event.h>
90: #include <irq.h>
91: #include <thread.h>
92: #include <timer.h>
93: #include <vm.h>
94: #include <task.h>
95: #include <system.h>
96: #include <sched.h>
97:
98: static struct queue runq[NR_PRIOS]; /* run queues */
99: static struct queue wakeq; /* queue for waking threads */
100: static struct queue dpcq; /* queue for DPC threads */
101: static int top_prio; /* highest priority in runq */
102:
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: * The rescheduling flag is set if the priority is better than
122: * the currently running process.
123: */
124: static void
125: runq_enqueue(thread_t th)
126: {
127:
128: enqueue(&runq[th->prio], &th->link);
129: if (th->prio < top_prio) {
130: top_prio = th->prio;
131: cur_thread->need_resched = 1;
132: }
133: }
134:
135: /*
136: * Insert a thread to the head of the run queue.
137: * We don't change rescheduling flag here because this is called
138: * while thread switching.
139: */
140: static void
141: runq_insert(thread_t th)
142: {
143:
144: queue_insert(&runq[th->prio], &th->link);
145: if (th->prio < top_prio)
146: top_prio = th->prio;
147: }
148:
149: /*
150: * Pick up and remove the highest-priority thread from the run
151: * queue. At least, an idle thread will be returned because it
152: * always residents in the lowest priority queue.
153: */
154: static thread_t
155: runq_dequeue(void)
156: {
157: queue_t q;
158: thread_t th;
159:
160: q = dequeue(&runq[top_prio]);
161: th = queue_entry(q, struct thread, link);
162: if (queue_empty(&runq[top_prio]))
163: top_prio = runq_top();
164: return th;
165: }
166:
167: /*
168: * Remove the specified thread from the run queue.
169: */
170: static void
171: runq_remove(thread_t th)
172: {
173:
174: queue_remove(&th->link);
175: top_prio = runq_top();
176: }
177:
178: /*
179: * Process all pending woken threads.
180: * Rescheduling flag may be set.
181: * Note: The thread may be still in a suspend state after wakeup.
182: */
183: static void
184: wakeq_flush(void)
185: {
186: queue_t q;
187: thread_t th;
188:
189: while (!queue_empty(&wakeq)) {
190: /*
191: * Set a thread runnable.
192: */
193: q = dequeue(&wakeq);
194: th = queue_entry(q, struct thread, link);
195: th->sleep_event = 0;
196: th->state &= ~TH_SLEEP;
197:
198: if (th != cur_thread && th->state == TH_RUN)
199: runq_enqueue(th);
200: }
201: }
202:
203: /*
204: * sleep_expire - sleep timer is expired:
205: * @arg: thread to unsleep.
206: *
207: * Wake up the passed thread that is sleeping in sched_tsleep().
208: */
209: static void
210: sleep_expire(void *arg)
211: {
212:
213: sched_unsleep((thread_t)arg, SLP_TIMEOUT);
214: }
215:
216: /*
217: * sched_switch - This routine is called to reschedule the CPU.
218: *
219: * If the scheduling reason is preemption, the current thread
220: * will remain at the head of the run queue. So, the thread
221: * still has right to run first again among the same priority
222: * threads. For other scheduling reason, the current thread is
223: * inserted into the tail of the run queue.
224: */
225: static void
226: sched_switch(void)
227: {
228: thread_t prev, next;
229:
230: ASSERT(irq_level == 0);
231:
232: prev = cur_thread;
233: if (prev->state == TH_RUN) {
234: if (prev->prio > top_prio)
235: runq_insert(prev); /* preemption */
236: else
237: runq_enqueue(prev);
238: }
239: prev->need_resched = 0;
240:
241: /*
242: * This is the scheduler proper.
243: */
244: next = runq_dequeue();
245: if (next == prev)
246: return;
247: cur_thread = next;
248:
249: if (prev->task != next->task)
250: vm_switch(next->task->map);
251:
252: context_switch(&prev->context, &next->context);
253: }
254:
255: /*
256: * sched_tsleep - sleep the current thread until a wakeup is
257: * performed on the specified event.
258: * @timeout: time out value in msec. (0 means no timeout)
259: *
260: * This routine returns a sleep result. If the thread is woken
261: * by sched_wakeup()/sched_wakeone(), it returns 0. Otherwise,
262: * it will return the result value which is passed by sched_unsleep().
263: * We allow calling sched_sleep() with interrupt disabled.
264: *
265: * sched_sleep() is also defined as a wrapper macro for sched_tsleep()
266: * without timeout.
267: * Note that all sleep requests are interruptible with this kernel.
268: */
269: int
270: sched_tsleep(struct event *evt, u_long timeout)
271: {
272: int s;
273:
274: ASSERT(irq_level == 0);
275: ASSERT(evt);
276:
277: sched_lock();
278: interrupt_save(&s);
279: interrupt_disable();
280:
281: cur_thread->sleep_event = evt;
282: cur_thread->state |= TH_SLEEP;
283: enqueue(&evt->sleepq, &cur_thread->link);
284:
285: if (timeout != 0) {
286: timer_callout(&cur_thread->timeout, sleep_expire,
287: cur_thread, timeout);
288: }
289: wakeq_flush();
290: sched_switch(); /* Sleep here. Zzzz.. */
291:
292: interrupt_restore(s);
293: sched_unlock();
294: return cur_thread->sleep_result;
295: }
296:
297: /*
298: * sched_wakeup - wake up all threads sleeping on event.
299: *
300: * A thread can have sleep and suspend state simultaneously.
301: * So, the thread does not always run even if it woke up.
302: *
303: * Since this routine can be called from ISR at interrupt level, it
304: * should not touch any data of runq. Otherwise, we must frequently
305: * disable interrupts while accessing runq. Thus, this routine will
306: * temporary move the waking thread into wakeq, and the thread is
307: * moved to runq at more safer time in wakeq_flush().
308: *
309: * The woken thread will be put on the tail of runq regardless
310: * of its policy. If woken threads have same priority, next running
311: * thread is selected by FIFO order.
312: */
313: void
314: sched_wakeup(struct event *evt)
315: {
316: queue_t q;
317: thread_t th;
318:
319: irq_lock();
320: while (!queue_empty(&evt->sleepq)) {
321: /*
322: * Move a sleeping thread to the wake queue.
323: */
324: q = dequeue(&evt->sleepq);
325: th = queue_entry(q, struct thread, link);
326: th->sleep_result = 0;
327: enqueue(&wakeq, q);
328: timer_stop(&th->timeout);
329: }
330: irq_unlock();
331: }
332:
333: /*
334: * sched_wakeone - wake up one thread sleeping for the event.
335: *
336: * The highest priority thread is woken among sleeping threads.
337: * sched_wakeone() returns the thread ID of the woken thread, or
338: * NULL if no threads are sleeping.
339: */
340: thread_t
341: sched_wakeone(struct event *evt)
342: {
343: queue_t head, q;
344: thread_t top, th = NULL;
345:
346: irq_lock();
347: head = &evt->sleepq;
348: if (!queue_empty(head)) {
349: /*
350: * Select the highet priority thread in
351: * the sleeping threads, and move it to
352: * the wake queue.
353: */
354: q = queue_first(head);
355: top = queue_entry(q, struct thread, link);
356: while (!queue_end(head, q)) {
357: th = queue_entry(q, struct thread, link);
358: if (th->prio < top->prio)
359: top = th;
360: q = queue_next(q);
361: }
362: queue_remove(&top->link);
363: enqueue(&wakeq, &top->link);
364: timer_stop(&top->timeout);
365: }
366: irq_unlock();
367: return th;
368: }
369:
370: /*
371: * sched_unsleep - cancel sleep.
372: *
373: * sched_unsleep() removes the specified thread from its sleep
374: * queue. The specified sleep result will be passed to the sleeping
375: * thread as a return value of sched_tsleep().
376: */
377: void
378: sched_unsleep(thread_t th, int result)
379: {
380: sched_lock();
381: if (th->state & TH_SLEEP) {
382: irq_lock();
383: queue_remove(&th->link);
384: th->sleep_result = result;
385: enqueue(&wakeq, &th->link);
386: timer_stop(&th->timeout);
387: irq_unlock();
388:
389: }
390: sched_unlock();
391: }
392:
393: /*
394: * Yield the current processor to another thread.
395: *
396: * If a thread switching occurs, the current thread will be moved
397: * on the tail of the run queue regardless of its policy.
398: * Note that the current thread may run immediately again, if no
399: * other thread exists in the same priority queue.
400: */
401: void
402: sched_yield(void)
403: {
404: ASSERT(irq_level == 0);
405:
406: sched_lock();
407:
408: if (!queue_empty(&runq[cur_thread->prio]))
409: cur_thread->need_resched = 1;
410:
411: sched_unlock(); /* Switch current thread here */
412: }
413:
414: /*
415: * Suspend the specified thread.
416: * The scheduler must be locked before calling this routine.
417: * Note that the suspend count is handled in thread_suspend().
418: */
419: void
420: sched_suspend(thread_t th)
421: {
422: ASSERT(cur_thread->lock_count > 0);
423:
424: if (th->state == TH_RUN) {
425: if (th == cur_thread)
426: cur_thread->need_resched = 1;
427: else
428: runq_remove(th);
429: }
430: th->state |= TH_SUSPEND;
431: }
432:
433: /*
434: * Resume the specified thread.
435: * The scheduler must be locked before calling this routine.
436: */
437: void
438: sched_resume(thread_t th)
439: {
440: ASSERT(cur_thread->lock_count > 0);
441:
442: if (th->state & TH_SUSPEND) {
443: th->state &= ~TH_SUSPEND;
444: if (th->state == TH_RUN)
445: runq_enqueue(th);
446: }
447: }
448:
449: /*
450: * sched_tick() is called from timer_tick() once every tick.
451: * Check quantum expiration, and mark a rescheduling flag.
452: * We don't need locking in here.
453: */
454: void
455: sched_tick(void)
456: {
457:
458: cur_thread->total_ticks++;
459:
460: if (cur_thread->policy == SCHED_RR) {
461: if (--cur_thread->ticks_left <= 0) {
462: cur_thread->ticks_left = QUANTUM;
463: cur_thread->need_resched = 1;
464: }
465: }
466: }
467:
468: /*
469: * Set up stuff for thread scheduling.
470: */
471: void
472: sched_start(thread_t th)
473: {
474:
475: th->state = TH_RUN | TH_SUSPEND;
476: th->policy = SCHED_RR;
477: th->prio = PRIO_USER;
478: th->base_prio = PRIO_USER;
479: th->ticks_left = QUANTUM;
480: }
481:
482: /*
483: * Stop thread scheduling.
484: */
485: void
486: sched_stop(thread_t th)
487: {
488: ASSERT(irq_level == 0);
489: ASSERT(cur_thread->lock_count > 0);
490:
491: if (th == cur_thread) {
492: /*
493: * If specified thread is current thread, the
494: * scheduling lock count is force set to 1 to
495: * ensure the thread switching in the next
496: * sched_unlock().
497: */
498: cur_thread->lock_count = 1;
499: cur_thread->need_resched = 1;
500: } else {
501: if (th->state == TH_RUN)
502: runq_remove(th);
503: else if (th->state & TH_SLEEP)
504: queue_remove(&th->link);
505: }
506: timer_stop(&th->timeout);
507: th->state = TH_EXIT;
508: }
509:
510: /*
511: * sched_lock - lock the scheduler.
512: *
513: * The thread switch is disabled during scheduler locked. This
514: * is mainly used to synchronize the thread execution to protect
515: * global resources. Even when scheduler is locked, any interrupt
516: * handler can run. So, we have to use irq_lock() to synchronize
517: * a global data with ISR.
518: *
519: * Since the scheduling lock can be nested any number of times,
520: * the caller has the responsible to unlock the same number of
521: * locks.
522: */
523: void
524: sched_lock(void)
525: {
526:
527: cur_thread->lock_count++;
528: }
529:
530: /*
531: * sched_unlock - unlock scheduler.
532: *
533: * If nobody locks the scheduler anymore, it runs pending wake
534: * threads and check the reschedule flag. The thread switch is
535: * invoked if the rescheduling request exists.
536: *
537: * Note that this routine will be called at the end of the
538: * interrupt handler.
539: */
540: void
541: sched_unlock(void)
542: {
543: int s;
544:
545: ASSERT(cur_thread->lock_count > 0);
546:
547: interrupt_save(&s);
548: interrupt_disable();
549:
550: if (cur_thread->lock_count == 1) {
551: wakeq_flush();
552: while (cur_thread->need_resched) {
553:
554: /* Kick scheduler */
555: sched_switch();
556:
557: /*
558: * Now we run pending interrupts which fired
559: * during the thread switch. So, we can catch
560: * the rescheduling request from such ISRs.
561: * Otherwise, the reschedule may be deferred
562: * until _next_ sched_unlock() call.
563: */
564: interrupt_restore(s);
565: interrupt_disable();
566: wakeq_flush();
567: }
568: }
569: cur_thread->lock_count--;
570:
571: interrupt_restore(s);
572: }
573:
574: int
575: sched_getprio(thread_t th)
576: {
577:
578: return th->prio;
579: }
580:
581: /*
582: * sched_setprio - set priority of thread.
583: * @base: Base priority
584: * @prio: Current priority
585: *
586: * Thread switch may be invoked here by priority change.
587: * Called with scheduler locked.
588: */
589: void
590: sched_setprio(thread_t th, int base, int prio)
591: {
592:
593: th->base_prio = base;
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->need_resched = 1;
604: } else {
605: if (th->state == TH_RUN) {
606: /*
607: * Update the thread priority and adjust the
608: * 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->ticks_left = QUANTUM;
634: th->policy = policy;
635: break;
636: default:
637: err = -1;
638: break;
639: }
640: return err;
641: }
642:
643: /*
644: * DPC thread
645: *
646: * This is a kernel thread to process the pending call back request
647: * within DPC queue. Each DPC routine is called with the following
648: * conditions.
649: * - Interrupt is enabled.
650: * - Scheduler is unlocked.
651: */
652: static void
653: dpc_thread(u_long unused)
654: {
655: queue_t q;
656: struct dpc *dpc;
657:
658: for (;;) {
659:
660: /* Wait until next DPC request. */
661: sched_sleep(&dpc_event);
662:
663: while (!queue_empty(&dpcq)) {
664: q = dequeue(&dpcq);
665: dpc = queue_entry(q, struct dpc, link);
666: dpc->state = DPC_FREE;
667:
668: interrupt_enable();
669: (*dpc->func)(dpc->arg);
670: interrupt_disable();
671: }
672: }
673: /* NOTREACHED */
674: }
675:
676: /*
677: * Qeueue DPC (Deferred Procedure Call) request
678: *
679: * Call function at some later time in a DPC priority. This is
680: * typically used by device drivers to do the low-priority jobs.
681: * This routine can be called from ISR.
682: */
683: void
684: sched_dpc(struct dpc *dpc, void (*func)(void *), void *arg)
685: {
686: ASSERT(dpc);
687: ASSERT(func);
688:
689: irq_lock();
690: dpc->func = func;
691: dpc->arg = arg;
692: if (dpc->state != DPC_PENDING)
693: enqueue(&dpcq, &dpc->link);
694: dpc->state = DPC_PENDING;
695: sched_wakeup(&dpc_event);
696: irq_unlock();
697: }
698:
699: /*
700: * Initialize the global scheduler state.
701: */
702: void
703: sched_init(void)
704: {
705: int i;
706:
707: for (i = 0; i < NR_PRIOS; i++)
708: queue_init(&runq[i]);
709:
710: queue_init(&wakeq);
711: queue_init(&dpcq);
712: event_init(&dpc_event, "dpc");
713: top_prio = PRIO_IDLE;
714: cur_thread->need_resched = 1;
715:
716: /*
717: * Create a DPC thread.
718: */
719: if (kernel_thread(PRIO_DPC, dpc_thread, 0) == NULL)
720: panic("sched_init");
721:
722: printk("Time slice is %d msec\n", CONFIG_TIME_SLICE);
723: }
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-old / sys / kern