aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2011-12-20 15:48:12 +0000
committerDimitri Sokolyuk <demon@dim13.org>2011-12-20 15:48:12 +0000
commit3a6e29a51edf91d1174e1eab05adb86de7356c16 (patch)
tree1da008db472cfaa7e9095cacd3378a4584cce646
parent0851cd0d947e3e2f35e0ab776526ab58f80c4d8c (diff)
time-sharing: wighted round-robin scheduler with single-linked run-queue
-rw-r--r--kernel/adc.c4
-rw-r--r--kernel/clock.c4
-rw-r--r--kernel/ctrl.c4
-rw-r--r--kernel/dmx.c20
-rw-r--r--kernel/heartbeat.c12
-rw-r--r--kernel/kernel.c200
-rw-r--r--kernel/kernel.h10
-rw-r--r--kernel/lcd3.c56
-rw-r--r--kernel/ppm.c10
-rw-r--r--kernel/rgb.c20
10 files changed, 146 insertions, 194 deletions
diff --git a/kernel/adc.c b/kernel/adc.c
index 7a11447..a4c7540 100644
--- a/kernel/adc.c
+++ b/kernel/adc.c
@@ -32,8 +32,6 @@ adc(void *arg)
ADCSRA |= (_BV(ADEN) | ADC_FLAGS);
- update(0, DL);
-
for (;;) {
if (bit_is_clear(ADCSRA, ADSC)) {
cli();
@@ -43,6 +41,6 @@ adc(void *arg)
ADMUX = i;
ADCSRA |= _BV(ADSC);
}
- update(MSEC(500 / ADCCHANNELS), DL);
+ sleep(MSEC(500 / ADCCHANNELS));
}
}
diff --git a/kernel/clock.c b/kernel/clock.c
index 7283368..4515d55 100644
--- a/kernel/clock.c
+++ b/kernel/clock.c
@@ -30,8 +30,6 @@ clock(void *arg)
d = h = m = s = 0;
- update(0, SEC(500));
-
for (;;) {
s += 1;
if (s == 60) {
@@ -50,6 +48,6 @@ clock(void *arg)
sprintf(a->lcd->first, "%8lx%8x", now(), a->adc->value[0]);
sprintf(a->lcd->second, "%4d:%.2d:%.2d:%.2d", d, h, m, s);
- update(SEC(1), MSEC(500));
+ sleep(SEC(1));
}
}
diff --git a/kernel/ctrl.c b/kernel/ctrl.c
index a44c9b1..1f802db 100644
--- a/kernel/ctrl.c
+++ b/kernel/ctrl.c
@@ -26,8 +26,6 @@ ctrl(void *arg)
{
struct ctrlarg *a = arg;
- update(now(), MSEC(500));
-
for (;;) {
sprintf(a->lcd->first, "%8lx", now());
sprintf(a->lcd->second, "%4d:%.2d:%.2d:%.2d",
@@ -35,6 +33,6 @@ ctrl(void *arg)
a->clock->h,
a->clock->m,
a->clock->s);
- update(MSEC(500), MSEC(750));
+ sleep(MSEC(500));
}
}
diff --git a/kernel/dmx.c b/kernel/dmx.c
index 1a6297a..031417d 100644
--- a/kernel/dmx.c
+++ b/kernel/dmx.c
@@ -44,31 +44,31 @@ main()
init_uart();
#if 1
- exec(heartbeat, STACK, 0);
+ exec(heartbeat, STACK, 0, LOW);
#endif
#if 1
- exec(rgb, STACK + 16, &rgbargs);
- exec(pwm, STACK, &pwmargs[0]);
- exec(pwm, STACK, &pwmargs[1]);
- exec(pwm, STACK, &pwmargs[2]);
+ exec(rgb, STACK + 16, &rgbargs, LOW);
+ exec(pwm, STACK, &pwmargs[0], HIGH);
+ exec(pwm, STACK, &pwmargs[1], HIGH);
+ exec(pwm, STACK, &pwmargs[2], HIGH);
#endif
#if 1
- exec(adc, STACK, &adcarg);
+ exec(adc, STACK, &adcarg, LOW);
#endif
#if 1
- exec(lcd, STACK, &lcdarg);
- exec(clock, STACK + 48, &clockarg);
+ exec(lcd, STACK, &lcdarg, LOW);
+ exec(clock, STACK + 48, &clockarg, LOW);
#endif
#if 0
- exec(cmd, STACK, &rgbargs);
+ exec(cmd, STACK, &rgbargs, LOW);
#endif
#if 0
- exec(ppm, STACK, &ppmarg);
+ exec(ppm, STACK, &ppmarg, LOW);
#endif
for (;;)
diff --git a/kernel/heartbeat.c b/kernel/heartbeat.c
index 16dbb0e..7540ddc 100644
--- a/kernel/heartbeat.c
+++ b/kernel/heartbeat.c
@@ -30,21 +30,17 @@ heartbeat(void *arg)
DDRB |= _BV(PIN);
PORTB &= ~_BV(PIN);
-#define DL MSEC(5)
-
- update(0, DL);
-
for (;;) {
PORTB |= _BV(PIN);
- update(MSEC(100), DL);
+ sleep(MSEC(100));
PORTB &= ~_BV(PIN);
- update(MSEC(50), DL);
+ sleep(MSEC(50));
PORTB |= _BV(PIN);
- update(MSEC(100), DL);
+ sleep(MSEC(100));
PORTB &= ~_BV(PIN);
- update(MSEC(500), DL);
+ sleep(MSEC(500));
}
}
diff --git a/kernel/kernel.c b/kernel/kernel.c
index e408016..bf7af98 100644
--- a/kernel/kernel.c
+++ b/kernel/kernel.c
@@ -25,10 +25,9 @@
#include <avr/interrupt.h>
#include "kernel.h"
#include "stack.h"
+#include "queue.h"
-#define SLACK 1
-
-enum State { TERMINATED, RUNQ, TIMEQ, WAITQOFFSET };
+enum State { TERMINATED, RUNQ, TIMEQ, WAITQ };
#define LO8(x) ((uint8_t)((uint16_t)(x)))
#define HI8(x) ((uint8_t)((uint16_t)(x) >> 8))
@@ -39,18 +38,18 @@ enum State { TERMINATED, RUNQ, TIMEQ, WAITQOFFSET };
struct task {
uint32_t release;
- uint32_t deadline;
-#if SLACK
- int32_t slack;
-#endif
uint16_t sp; /* stack pointer */
+ uint32_t time; /* stack pointer */
uint8_t state;
+ uint8_t prio;
+ SIMPLEQ_ENTRY(task) link;
};
struct kernel {
- struct task *running;
- struct task *last;
+ SIMPLEQ_HEAD(, task) runq;
+ struct task *last; /* last allocated task */
struct task task[TASKS + 1];
+ uint32_t lasthit;
uint16_t cycles;
uint8_t *freemem;
uint8_t semaphore[SEMAPHORES];
@@ -63,51 +62,54 @@ ISR(TIMER1_OVF_vect)
ISR(TIMER1_COMPA_vect, ISR_NAKED)
{
- struct task *t;
- struct task *rtr;
+ struct task *tp;
+ int32_t dist;
uint32_t now;
- uint32_t nexthit;
+ uint16_t nexthit;
+ /* save context */
PUSH_ALL();
now = NOW(kernel.cycles, TCNT1);
- nexthit = EPOCH + now;
- /* update idle task */
- kernel.task->deadline = nexthit;
+ PORTB ^= _BV(PB1); /* DEBUG */
+
+ /* save stack pointer */
+ tp = SIMPLEQ_FIRST(&kernel.runq);
+ tp->sp = SP;
+ tp->state = TIMEQ;
+ tp->time += DISTANCE(kernel.lasthit, now);
+ /* drop current task from run-queue */
+ SIMPLEQ_REMOVE_HEAD(&kernel.runq, link);
+
+ kernel.lasthit = now;
+ nexthit = 0xffff;
+
+ /* walk through tasks and assemble run-queue */
+ for (tp = &kernel.task[1]; tp <= kernel.last; tp++) {
+ if (tp->state != TIMEQ)
+ continue;
+ dist = DISTANCE(now, tp->release);
+ if (dist <= 0) {
+ tp->state = RUNQ;
+ if (tp->prio == HIGH)
+ SIMPLEQ_INSERT_HEAD(&kernel.runq, tp, link);
+ else
+ SIMPLEQ_INSERT_TAIL(&kernel.runq, tp, link);
+ } else if (dist < nexthit)
+ nexthit = dist;
+ }
- rtr = kernel.task;
- t = kernel.running;
- do {
- if (++t > kernel.last)
- t = kernel.task;
-
- /* release tasks from time-wait-queue */
- if (t->state == TIMEQ) {
- if (DISTANCE(t->release, now) > 0)
- t->state = RUNQ;
- else if (DISTANCE(t->release, nexthit) > 0)
- nexthit = t->release;
- }
-
- /* find next task to run */
- if (t->state == RUNQ) {
-#if SLACK
- if (t->slack < rtr->slack)
-#else
- if (DISTANCE(t->deadline, rtr->deadline) > 0)
-#endif
- rtr = t;
- }
- } while (t != kernel.running);
+ /* idle if empty */
+ if (SIMPLEQ_EMPTY(&kernel.runq))
+ SIMPLEQ_INSERT_HEAD(&kernel.runq, &kernel.task[0], link);
- /* switch task */
- kernel.running->sp = SP;
- SP = rtr->sp;
- kernel.running = rtr;
+ /* restore stack pointer */
+ SP = SIMPLEQ_FIRST(&kernel.runq)->sp;
- OCR1A = (uint16_t)nexthit;
-
+ OCR1A = (uint16_t)(now + nexthit);
+
+ /* restore context */
POP_ALL();
reti();
}
@@ -122,24 +124,27 @@ init(uint8_t stack)
TCCR1A = 0; /* normal operation */
TCCR1B = TIMER_FLAGS; /* prescale */
TIMSK = (_BV(OCIE1A) | _BV(TOIE1)); /* enable interrupts */
+ OCR1A = 0; /* default overflow */
+
+ DDRB |= _BV(PB1); /* DEBUG */
+
+ SIMPLEQ_INIT(&kernel.runq);
+ kernel.lasthit = 0;
kernel.cycles = 0;
kernel.freemem = (void *)(RAMEND - stack);
kernel.last = kernel.task;
- kernel.running = kernel.task;
+ kernel.last->release = 0;
+ kernel.last->prio = 0;
+ kernel.last->state = RUNQ;
- /* Initialize idle task (task 0) */
- kernel.running->deadline = EPOCH;
-#if SLACK
- kernel.running->slack = EPOCH;
-#endif
- kernel.running->state = RUNQ;
+ SIMPLEQ_INSERT_HEAD(&kernel.runq, kernel.last, link);
sei();
}
void
-exec(void (*fun)(void *), uint8_t stack, void *args)
+exec(void (*fun)(void *), uint8_t stack, void *args, uint8_t prio)
{
struct task *t;
uint8_t *sp;
@@ -165,10 +170,7 @@ exec(void (*fun)(void *), uint8_t stack, void *args)
t = ++kernel.last;
t->release = 0;
- t->deadline = EPOCH;
-#if SLACK
- t->slack = 0;
-#endif
+ t->prio = prio;
t->state = TIMEQ;
t->sp = (uint16_t)sp; /* SP */
@@ -176,6 +178,7 @@ exec(void (*fun)(void *), uint8_t stack, void *args)
SCHEDULE();
}
+#if 0
void
semaphore(uint8_t sema, uint8_t val)
{
@@ -192,7 +195,7 @@ wait(uint8_t sema)
cli();
if (kernel.semaphore[sema] == 0) {
- kernel.running->state = WAITQOFFSET + sema;
+ kernel.running->state = WAITQ + sema;
SCHEDULE();
} else {
--kernel.semaphore[sema];
@@ -210,7 +213,7 @@ signal(uint8_t sema)
rtr = kernel.task;
for (t = &kernel.task[1]; t <= kernel.last; t++) {
- if (t->state == WAITQOFFSET + sema)
+ if (t->state == WAITQ + sema)
if (DISTANCE(t->deadline, rtr->deadline) > 0)
rtr = t;
}
@@ -223,81 +226,27 @@ signal(uint8_t sema)
sei();
}
}
-
-void
-set(uint32_t release, uint32_t deadline)
-{
- struct task *t;
- uint32_t now;
-
- cli();
-
- now = NOW(kernel.cycles, TCNT1);
- t = kernel.running;
-#if SLACK
- t->slack = DISTANCE(now, t->deadline);
#endif
- t->state = TIMEQ;
- t->release = release;
- t->deadline = deadline;
-
- SCHEDULE();
-}
void
-update(uint32_t release, uint32_t deadline)
+sleep(uint32_t ticks)
{
- struct task *t;
- uint32_t now;
+ struct task *tp;
cli();
- now = NOW(kernel.cycles, TCNT1);
- t = kernel.running;
-#if SLACK
- t->slack = DISTANCE(now, t->deadline);
-#endif
- t->state = TIMEQ;
- t->release += release;
- t->deadline = t->release + deadline;
+ tp = SIMPLEQ_FIRST(&kernel.runq);
+ tp->release += ticks;
+ tp->time = 0;
+ tp->state = TIMEQ;
SCHEDULE();
}
uint32_t
-deadline(void)
-{
- uint32_t ret;
-
- cli();
- ret = kernel.running->deadline;
- sei();
-
- return ret;
-}
-
-uint32_t
-release(void)
-{
- uint32_t ret;
-
- cli();
- ret = kernel.running->release;
- sei();
-
- return ret;
-}
-
-uint32_t
now(void)
{
- uint32_t ret;
-
- cli();
- ret = NOW(kernel.cycles, TCNT1);
- sei();
-
- return ret;
+ return NOW(kernel.cycles, TCNT1);
}
void
@@ -305,19 +254,12 @@ suspend(void)
{
cli();
- kernel.running->state = TERMINATED;
-
+ SIMPLEQ_FIRST(&kernel.runq)->state = TERMINATED;
SCHEDULE();
}
uint8_t
running(void)
{
- uint8_t ret;
-
- cli();
- ret = kernel.running - kernel.task;
- sei();
-
- return ret;
+ return SIMPLEQ_FIRST(&kernel.runq) - &kernel.task[0];
}
diff --git a/kernel/kernel.h b/kernel/kernel.h
index 74e8444..84c0f39 100644
--- a/kernel/kernel.h
+++ b/kernel/kernel.h
@@ -89,22 +89,20 @@
#define SEC1(T) ((uint32_t)(T) * ((F_CPU / 10) / PRESCALE))
#define SEC0(T) ((uint32_t)(T) * ((F_CPU / 1) / PRESCALE))
+enum Prio { LOW, HIGH };
+
/* __BEGIN_DECLS */
void init(uint8_t stack);
-void exec(void (*fun)(void *), uint8_t stack, void *args);
+void exec(void (*fun)(void *), uint8_t stack, void *args, uint8_t prio);
void semaphore(uint8_t semnbr, uint8_t initVal);
void wait(uint8_t semnbr);
void signal(uint8_t semnbr);
void suspend(void);
-
-void set(uint32_t release, uint32_t deadline);
-void update(uint32_t release, uint32_t deadline);
+void sleep(uint32_t ticks);
uint32_t now(void);
-uint32_t release(void);
-uint32_t deadline(void);
uint8_t running(void);
/* __END_DECLS */
diff --git a/kernel/lcd3.c b/kernel/lcd3.c
index 863e1d4..e12a408 100644
--- a/kernel/lcd3.c
+++ b/kernel/lcd3.c
@@ -59,17 +59,47 @@
#define CLOCK PD6
#define E PD7
-#define write_cmd(x, delay) do { write_byte((x), 0); _delay_us(delay); } while (0)
-#define write_data(x) do { write_byte((x), 1); _delay_us(43); } while (0)
-#define move(line, row) do { write_cmd(SET_DDRAM_ADDRESS | ((line) << 6) | (row), 39); } while (0)
-#define clear() do { write_cmd(CLEAR_DISPLAY, 1530); } while (0)
-#define home() do { write_cmd(RETURN_HOME, 1530); } while (0)
-
-
-/* recomended cycle 1us: 450ns on, 450ns off. this is beyond our resolution */
-#define wait_short() do { _NOP(); } while (0)
-#define strobe(port, bit) do { port |= _BV(bit); wait_short(); port &= ~_BV(bit); } while (0)
-#define setif(cond, port, bit) do { if (cond) port |= _BV(bit); else port &= ~_BV(bit); } while (0)
+#define write_cmd(x, delay) do { \
+ write_byte((x), 0); \
+ _delay_us(delay); \
+} while (0)
+
+#define write_data(x) do { \
+ write_byte((x), 1); \
+ _delay_us(43); \
+} while (0)
+
+#define move(line, row) do { \
+ write_cmd(SET_DDRAM_ADDRESS | ((line) << 6) | (row), 39); \
+} while (0)
+
+#define clear() do { \
+ write_cmd(CLEAR_DISPLAY, 1530); \
+} while (0)
+
+#define home() do { \
+ write_cmd(RETURN_HOME, 1530); \
+} while (0)
+
+
+/* recomended cycle 1us: 450ns on, 450ns off.
+ * this is beyond our resolution */
+#define wait_short() do { \
+ _NOP(); \
+} while (0)
+
+#define strobe(port, bit) do { \
+ port |= _BV(bit); \
+ wait_short(); \
+ port &= ~_BV(bit); \
+} while (0)
+
+#define setif(cond, port, bit) do { \
+ if (cond) \
+ port |= _BV(bit); \
+ else \
+ port &= ~_BV(bit); \
+} while (0)
static void
write_byte(uint8_t byte, uint8_t rs)
@@ -107,7 +137,7 @@ lcd(void *arg)
PORTDIR |= (_BV(DATA) | _BV(CLOCK) | _BV(E));
/* task init: wait >40ms */
- update(MSEC(40), MSEC(500));
+ sleep(MSEC(40));
/* 8 bit, 2 line, 5x8 font */
write_cmd(FUNCTION_SET | DATA_LENGTH_8BIT | TWO_LINES, 39);
@@ -130,6 +160,6 @@ lcd(void *arg)
for (;;) {
mvputs(0, 0, a->first);
mvputs(1, 0, a->second);
- update(MSEC(40), MSEC(40)); /* 25Hz */
+ sleep(MSEC(40));
}
}
diff --git a/kernel/ppm.c b/kernel/ppm.c
index bfbf109..3225dd4 100644
--- a/kernel/ppm.c
+++ b/kernel/ppm.c
@@ -41,8 +41,6 @@ ppm(void *arg)
DDRB |= _BV(DDB1);
OFF;
- update(0, DL);
-
/* frame length 20ms, channel 0.7-1.7ms, stop 0.3 ms */
for (;;) {
t = FRAME;
@@ -57,19 +55,19 @@ ppm(void *arg)
/* start frame 0.3ms low */
SWITCH;
- update(DELIM, DL);
+ sleep(DELIM);
/* channel frame 0.7..1.7ms high */
SWITCH;
- update(n, DL);
+ sleep(n);
}
/* sync frame */
SWITCH;
- update(DELIM, DL);
+ sleep(DELIM);
SWITCH;
- update(t - DELIM, DL);
+ sleep(t - DELIM);
}
}
diff --git a/kernel/rgb.c b/kernel/rgb.c
index d4872b4..82ddbc8 100644
--- a/kernel/rgb.c
+++ b/kernel/rgb.c
@@ -30,20 +30,18 @@ rgb(void *arg)
uint16_t i = 0;
uint8_t r, g, b, v = 0;
- update(0, MSEC(50));
-
for (;;) {
i = (i + 1) % 360;
hsv(&r, &g, &b, i, v, v);
- cli();
+ //cli();
a->r = r;
a->g = g;
a->b = b;
v = *a->v >> 2; /* 10bit to 8bit */
- sei();
+ //sei();
- update(MSEC(40), MSEC(50));
+ sleep(MSEC(40));
}
}
@@ -57,23 +55,19 @@ pwm(void *arg)
DDRB |= _BV(a->pin);
PORTB &= ~_BV(a->pin);
-#define DL SEC4(1)
-
- update(now(), DL);
-
for (;;) {
- cli();
+ //cli();
v = *a->value;
- sei();
+ //sei();
if ((on = SEC2(v) / UINT8_MAX)) {
PORTB |= _BV(a->pin);
- update(on, DL);
+ sleep(on);
}
if ((off = SEC2(UINT8_MAX - v) / UINT8_MAX)) {
PORTB &= ~_BV(a->pin);
- update(off, DL);
+ sleep(off);
}
}
}