Ethin wrote:
I'm hoping to implement a true preemptive scheduler,
There's no such thing. There's cooperative multitasking and preemptive multitasking, and there's the scheduler, those are unrelated.
- Multitasking is the implementation of interrupting a task and switch to another;
- Scheduler is merely responsible for picking the next task (unrelated to the multitasking method).
Ethin wrote:
but I always seem to get stuck on the scheduler algorithm part. I've thought about the multilevel feedback queue algorithm as well as a more exotic one, Lottery scheduling, but I've never implemented a scheduler before and so don't really have any idea on what data structure to use or what's fastest.
Don't be your own enemy, make things simple (K.I.S.S.). All you need is getting the next pid from a stack each time you call the scheduler. A very very very minimal implementation could be (note I've haven't tested this code just wrote it for demonstration):
Code:
pid_t *queue;
int queue_len, queue_ptr = 0;
/* get the next pid from queue O(1) */
pid_t scheduler_pick_next_task()
{
pid_t ret = queue[queue_ptr++];
if(queue_ptr >= queue_len) queue_ptr = 0;
return ret;
}
/* add a pid to the queue O(1) */
void scheduler_enqueue(pid_t pid)
{
queue = k_realloc(queue, (queue_len + 1) * sizeof(pid_t));
queue[queue_len++] = pid;
}
/* remove a pid from queue O(n) */
void scheduler_dequeue(pid_t pid)
{
int i;
for(i = 0; queue[i] != pid; i++);
for(; i < queue_len; i++) queue[i] = queue[i + 1];
queue_len--;
if(queue_ptr >= queue_len) queue_ptr = 0;
}
Ethin wrote:
Could someone describe typical implementations of good schedulers and possibly point me to simpler examples that are, hopefully, well-documented? (Also, is the multitasking tutorial on the wiki still of any use?)
As I've said, it just picks the next task, there's not much documentation for that. For a simple example, take a look above, or take a look at Minix's
pick_proc() function (and the accompanion enqueue() and dequeue() functions which handle the list).
nullplan wrote:
Simple scheduler? Round robin. All runnable tasks are in a circular doubly linked list.
Yes, but actually you don't even need a linked list for that. A simple array of pids will do just fine.
Cheers,
bzt