aboutsummaryrefslogtreecommitdiff
path: root/kernel/kernel.c
diff options
context:
space:
mode:
Diffstat (limited to 'kernel/kernel.c')
-rw-r--r--kernel/kernel.c189
1 files changed, 94 insertions, 95 deletions
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();
}