From 775ca7a6b283339019783af24c4c424cdb0cebd1 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Mon, 2 Jan 2012 10:03:37 +0000 Subject: time sharing --- kernel/kernel.c | 189 ++++++++++++++++++++++++++++---------------------------- 1 file changed, 94 insertions(+), 95 deletions(-) (limited to 'kernel/kernel.c') diff --git a/kernel/kernel.c b/kernel/kernel.c index dc29f57..7d2d6c2 100644 --- a/kernel/kernel.c +++ b/kernel/kernel.c @@ -27,10 +27,9 @@ #include "stack.h" #include "queue.h" -#define DEBUG 1 -#define NPRIO 2 +#define DEBUG 0 -enum State { TERMINATED, RTR, RUNQ, SLEEPING, WAITING }; +enum State { TERMINATED, RUNQ, TIMEQ, WAITQ, SIGNAL }; #define LO8(x) ((uint8_t)((uint16_t)(x))) #define HI8(x) ((uint8_t)((uint16_t)(x) >> 8)) @@ -44,14 +43,15 @@ struct task { uint16_t sp; /* stack pointer */ uint8_t state; uint8_t prio; - SIMPLEQ_ENTRY(task) link; + uint8_t sema; + TAILQ_ENTRY(task) link; }; struct kernel { - SIMPLEQ_HEAD(, task) runq[NPRIO]; - struct task *last; /* last allocated task */ + TAILQ_HEAD(queue, task) runq[PRIORITIES], timeq, waitq[SEMAPHORES]; + struct task task[1 + TASKS]; + struct task *nextfree; struct task *current; - struct task task[TASKS + 1]; uint16_t cycles; uint8_t *freemem; uint8_t semaphore[SEMAPHORES]; @@ -64,62 +64,90 @@ ISR(TIMER1_OVF_vect) ISR(TIMER1_COMPA_vect, ISR_NAKED) { - struct task *tp; + struct task *tp, *tmp; int32_t dist; uint32_t now; uint16_t nexthit; uint8_t prio; - /* save context */ PUSH_ALL(); - now = NOW(kernel.cycles, TCNT1); #if DEBUG PORTB ^= _BV(PB1); /* DEBUG */ #endif - /* save stack pointer and drop task from run-queue */ kernel.current->sp = SP; - if (kernel.current->state == RUNQ) - kernel.current->state = RTR; - SIMPLEQ_REMOVE_HEAD(&kernel.runq[kernel.current->prio], link); + TAILQ_REMOVE(&kernel.runq[kernel.current->prio], kernel.current, link); nexthit = 0xffff; - prio = 0; - - /* walk through tasks and assemble run-queue */ - for (tp = &kernel.task[1]; tp <= kernel.last; tp++) { - if (tp->state == SLEEPING) { - dist = DISTANCE(now, tp->release); - if (dist <= 0) - tp->state = RTR; - else if (dist < nexthit) - nexthit = dist; - } - if (tp->state == RTR) { - /* find highest priority */ - if (tp->prio > prio) - prio = tp->prio; - /* put task on queue */ - SIMPLEQ_INSERT_TAIL(&kernel.runq[tp->prio], tp, link); + + /* release waiting tasks */ + TAILQ_FOREACH_SAFE(tp, &kernel.timeq, link, tmp) { + dist = DISTANCE(now, tp->release); + if (dist <= 0) { tp->state = RUNQ; - } + TAILQ_REMOVE(&kernel.timeq, tp, link); + TAILQ_INSERT_TAIL(&kernel.runq[tp->prio], tp, link); + } else if (dist < nexthit) + nexthit = dist; + else + break; } - /* idle if all queues empty */ - if (prio == 0 && SIMPLEQ_EMPTY(&kernel.runq[prio])) { - SIMPLEQ_INSERT_TAIL(&kernel.runq[prio], kernel.task, link); - kernel.task->state = RUNQ; +again: + switch (kernel.current->state) { + case RUNQ: + TAILQ_INSERT_TAIL(&kernel.runq[kernel.current->prio], kernel.current, link); + break; + case TIMEQ: + TAILQ_FOREACH(tp, &kernel.timeq, link) + if (DISTANCE(kernel.current->release, tp->release) > 0) + break; + + if (tp) + TAILQ_INSERT_BEFORE(tp, kernel.current, link); + else + TAILQ_INSERT_TAIL(&kernel.timeq, kernel.current, link); + break; + case WAITQ: + if (kernel.semaphore[kernel.current->sema] == 0) { + /* occupy semaphore */ + kernel.semaphore[kernel.current->sema] = 1; + kernel.current->state = RUNQ; + goto again; /* put current task back on runq */ + } else + TAILQ_INSERT_TAIL(&kernel.waitq[kernel.current->sema], kernel.current, link); + break; + case SIGNAL: + tp = TAILQ_FIRST(&kernel.waitq[kernel.current->sema]); + if (tp) { + tp->state = RUNQ; + TAILQ_REMOVE(&kernel.waitq[kernel.current->sema], tp, link); + TAILQ_INSERT_TAIL(&kernel.runq[tp->prio], tp, link); + /* occupy semaphore */ + kernel.semaphore[kernel.current->sema] = 1; + } else + kernel.semaphore[kernel.current->sema] = 0; + + kernel.current->state = RUNQ; + goto again; /* put current task back on runq */ + default: + break; } - /* pick highest priority and restore stack pointer */ - kernel.current = SIMPLEQ_FIRST(&kernel.runq[prio]); + for (prio = 0; prio < PRIORITIES - 1; prio++) + if (!TAILQ_EMPTY(&kernel.runq[prio])) + break; + + if (TAILQ_EMPTY(&kernel.runq[prio])) + TAILQ_INSERT_TAIL(&kernel.runq[prio], &kernel.task[0], link); + + kernel.current = TAILQ_FIRST(&kernel.runq[prio]); SP = kernel.current->sp; OCR1A = (uint16_t)(now + nexthit); - /* restore context */ POP_ALL(); reti(); } @@ -127,7 +155,7 @@ ISR(TIMER1_COMPA_vect, ISR_NAKED) void init(uint8_t stack) { - uint8_t prio; + uint8_t i; cli(); @@ -142,19 +170,22 @@ init(uint8_t stack) DDRB |= _BV(PB1); /* DEBUG */ #endif - for (prio = 0; prio < NPRIO; prio++) - SIMPLEQ_INIT(&kernel.runq[prio]); + memset(&kernel, 0, sizeof(kernel)); - kernel.cycles = 0; - kernel.freemem = (void *)(RAMEND - stack); - kernel.task->release = 0; - kernel.task->prio = 0; - kernel.task->state = RUNQ; - SIMPLEQ_INSERT_TAIL(&kernel.runq[0], kernel.task, link); + for (i = 0; i < PRIORITIES; i++) + TAILQ_INIT(&kernel.runq[i]); + TAILQ_INIT(&kernel.timeq); + for (i = 0; i < SEMAPHORES; i++) + TAILQ_INIT(&kernel.waitq[i]); - kernel.last = kernel.task; - kernel.current = kernel.task; + kernel.nextfree = &kernel.task[1]; + kernel.freemem = (void *)(RAMEND - stack); + kernel.current = &kernel.task[0]; + kernel.current->state = TERMINATED; + kernel.current->prio = PRIORITIES - 1; + kernel.current->release = 0; + TAILQ_INSERT_TAIL(&kernel.runq[PRIORITIES - 1], &kernel.task[0], link); sei(); } @@ -183,70 +214,37 @@ exec(void (*fun)(void *), void *args, uint8_t stack, uint8_t prio) sp -= 6; memset(sp, 0, 6); /* r26-r31 */ - t = ++kernel.last; - - t->release = 0; - - if (prio >= NPRIO) - prio = NPRIO - 1; + t = kernel.nextfree++; + t->release = NOW(kernel.cycles, TCNT1); t->prio = prio; - - t->state = RTR; - + t->sema = 0; t->sp = (uint16_t)sp; /* SP */ + t->state = TIMEQ; + TAILQ_INSERT_TAIL(&kernel.timeq, t, link); SCHEDULE(); } -#if 0 -void -semaphore(uint8_t sema, uint8_t val) -{ - cli(); - - kernel.semaphore[sema] = val; - - sei(); -} - void wait(uint8_t sema) { cli(); - if (kernel.semaphore[sema] == 0) { - kernel.running->state = WAITQ + sema; - SCHEDULE(); - } else { - --kernel.semaphore[sema]; - sei(); - } + kernel.current->sema = sema; + kernel.current->state = WAITQ; + + SCHEDULE(); } void signal(uint8_t sema) { - struct task *t, *rtr; - cli(); - rtr = kernel.task; - - for (t = &kernel.task[1]; t <= kernel.last; t++) { - if (t->state == WAITQ + sema) - if (DISTANCE(t->deadline, rtr->deadline) > 0) - rtr = t; - } + kernel.current->state = SIGNAL; - if (rtr != kernel.task) { - rtr->state = RUNQ; - SCHEDULE(); - } else { - ++kernel.semaphore[sema]; - sei(); - } + SCHEDULE(); } -#endif void sleep(uint32_t ticks) @@ -254,7 +252,7 @@ sleep(uint32_t ticks) cli(); kernel.current->release += ticks; - kernel.current->state = SLEEPING; + kernel.current->state = TIMEQ; SCHEDULE(); } @@ -271,6 +269,7 @@ suspend(void) cli(); kernel.current->state = TERMINATED; + SCHEDULE(); } -- cgit v1.2.3