A question about scheduling algorithms

[Ethin]

I'm hoping to implement a true preemptive scheduler, 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. I'd look at something like the Linux scheduler but I'd probably get confused at trying to figure out how it works. 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?)

[nullplan]

Simple scheduler? Round robin. All runnable tasks are in a circular doubly linked list. That list is never empty, since the idle task is always runnable. Scheduler maintains a pointer to the current task and to the idle task. Whenever a task is unblocked, it is added to the list in front of the idle task, and if the current task is the idle task, the current task is retired. Scheduler only has to switch to the next task, literally. In case the list is down to just the idle task, you switch from idle to idle, but so what? You're not doing anything productive, anyway.

This algorithm does not admit any priorities. All tasks are treated the same. If priorities are important to you, you may want to switch to a priority queue. Each runnable task is enqueued in the PQ with its priority as key. Every time the task is not taken, the key is increased, until eventually, any task will end up at the peak of the PQ. The currently running task is removed from the PQ, and may be added again with its priority as key when it gets scheduled out.

The Linux schedulers are pretty far out. I had heard a description of the CFQ scheduler, but it made no sense in detail: You maintain a binary tree of all tasks, keyed by runtime. Since in a binary tree, the smallest element is always the left most one, that is always the task with the least run time, and that is the task you schedule in. However, I have no idea what they mean by "run time" here. It can't be absolute CPU time, since in that case CPU intensive, long running processes (e.g. my Firefox instances) would just starve. I also fail to see why a binary tree is better for this application than a priority queue.

[bzt]

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).

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: Select all

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;
}

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).

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

[rdos]

The actual code that switches tasks (and the lists, PQs or whatever it uses) is what makes up the actual preemptive multitasking implementation.The scheduler, particularly when it comes to SMP where tasks might need to be migrated between cores, is a set of software that makes more long term decision about where threads should run and possibly adjust priorities and other attributes that doesn't need to be evaluated in real-time. I've separated those into two different modules. The actual code that setup up preemtion timers and picks the next thread is a bit time critical, and I have that in assembler. The scheduler, OTOH, is not time critical and I have implemented it in C, and it uses load & execution history to move threads between cores. It also handles starting more cores as load increases. For scheduling, I use fixed priorities, and those just consists of lists and so the scheduler is not doing anything with those.

[bzt]

I agree, except with this one:

The scheduler, OTOH, is not time critical

That's not true. Whenever a task switch code is called, scheduler_pick is also called (simply to get the task to switch to), therefore I'd argue that at a minimum scheduler_pick must be O(1). It's good to have scheduler_enqueue or scheduler_dequeue O(1) too (depends on the algorithm and data structure choosen, both can't be O(1) unfortunately), but that's not a must because lists are modified rarely compared to picking the next task from the list (which happens at the same frequency as task switches).

Cheers,
bzt

[SelmaAdam]

The best pick is Round robin which is a pre-emptive algorithm.A round robin is an arrangement of choosing all elements in a group equally in some rational order, usually from the top to the bottom of a list and then starting again at the top of the list and so on.Hope this helps.