Writing a simple task scheduler. Help me reason about code (:

Go To Last Post
3 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

(editied because it looked hideous)

 

I've been at it for a couple days now, refreshing my memories of C, or rather learning anew. I'm building upon the tinythreads kernel and I've (I think) successfully added the ability to postpone a thread's execution. Yeah I know why re-invent the wheel etc, but it's for learning!

 

Okay, basically the preemption from the start worked in a round-robin fashion, a call to yield (from the currently running thread or via interrupt) preempted the running thread and switched to the next, the one which just ran was placed in the back of the queue of threads. Simple.

 

The mission is to be able to "skip" a thread in the queue based on, in this case, whether a wish to delay the thread in question has been made. Also, to optimize, I would like to skip the "main" or "default" thread, since it does nothing but sleep.

 

A thread is a struct containing some stuff. This scheduler just says which thread to prioritize, it doesn't do any context switching.

 

thread scheduler(thread *queue) {         // a thread is also a queue.. It's a linked list, so each thread has a "next" thread and so on, 
                                             eventually ending in a 0 (defined as NULL).
    thread q = *queue;                                     // ah, pointers -.- q is actually pointing towards the real queue now right? 
                                                              So much for functions without side-effects D:
    thread p = *queue;                                     // .. and p will point.. to.. oh my brain.. does q affect p? 
                                                              p and q now are tha same adress right?
    thread prio = NULL;                                    // lucky C is so loosely typed eh? :D or not.. 
                                                              prio is going to be the prioritized thread in the end.
    while (q) {                                            // while there's still a thread attached to the tail..
        q->delay -= q->delay ? 1 : 0 ;                     // reduce the initial delay given to the thread when spawned.
        prio = (q->delay || q->is_main) ? prio : q ;       // prio ⇒ ¬(q->delay ∨ q->is_main), there shall be no delay and not the main thread
        q = q->next;                                       // q is now the tail.. and so on
    }
    if (!prio)                                             // if prio still isn't instantiated.. 
                                                              right? anything other than 0 will be regarded as true by the if-statement?
        while (p) {                                        // let p soar through the queue again
            prio = p->is_main ? p : current ;              // if you find main, assign it to prio. 
                                                              If not, main must be running, assign current to prio.
            p = p->next;
        }
    return prio;
}

Phew, hope you're still there.. Is there anything I've missed here, which I haven't thought of? Any simplifications I can make..? The code is working, but you wouldn't think much of me if you knew how many prototypes i hade before I just said **** it, I'm keeping it simple, stupid!

Also, it's hard to test whether main is actually only running when nothing else could.

 

Oh and, as you can see, the delay is just a measurement of how many times yield has been invoked, and since the WDT is the one doing the yields, it can be seen as a "delay".

 

Thanks for your help.

sol i sinne - brun inne

Last Edited: Wed. Jan 14, 2015 - 01:45 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

What you have is a cooperative scheduler. Without wait queues (like time delays, I/O event wait).

Have you reviewed several the more complete open source cooperative schedulers?

Some old and good.

 

Then graduate to preemptive schedulers.

 

One clever one I recall, for AVRs, was SEOS. It's in the projects section.

As is OPEX.

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

No, the kernel is preemptive, it can be cooperatively multitasked aswell, but that's not what I'm going for here.

 

This is just the code to decide which task to run next.

sol i sinne - brun inne

Last Edited: Wed. Jan 14, 2015 - 03:30 AM