From 3a6e29a51edf91d1174e1eab05adb86de7356c16 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Tue, 20 Dec 2011 15:48:12 +0000 Subject: time-sharing: wighted round-robin scheduler with single-linked run-queue --- kernel/adc.c | 4 +- kernel/clock.c | 4 +- kernel/ctrl.c | 4 +- kernel/dmx.c | 20 +++--- kernel/heartbeat.c | 12 ++-- kernel/kernel.c | 200 +++++++++++++++++++---------------------------------- kernel/kernel.h | 10 ++- kernel/lcd3.c | 56 +++++++++++---- kernel/ppm.c | 10 ++- kernel/rgb.c | 20 ++---- 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 #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); } } } -- cgit v1.2.3