OSDev.org

The Place to Start for Operating System Developers
It is currently Sat Jun 12, 2021 8:19 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: A question about scheduling algorithms
PostPosted: Mon May 17, 2021 12:34 am 
Offline
Member
Member

Joined: Sun Jun 23, 2019 5:36 pm
Posts: 317
Location: North Dakota, United States
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?)


Top
 Profile  
 
 Post subject: Re: A question about scheduling algorithms
PostPosted: Mon May 17, 2021 8:45 am 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 1016
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.

_________________
Thou hast outraged, not insulted me, sir; but for that I ask thee not to beware of Starbuck; thou wouldst but laugh; but let Ahab beware of Ahab; beware of thyself, old man.


Top
 Profile  
 
 Post subject: Re: A question about scheduling algorithms
PostPosted: Mon May 17, 2021 10:43 am 
Offline
Member
Member
User avatar

Joined: Thu Oct 13, 2016 4:55 pm
Posts: 1512
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


Top
 Profile  
 
 Post subject: Re: A question about scheduling algorithms
PostPosted: Mon May 17, 2021 11:57 am 
Offline
Member
Member

Joined: Wed Oct 01, 2008 1:55 pm
Posts: 2625
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.


Top
 Profile  
 
 Post subject: Re: A question about scheduling algorithms
PostPosted: Mon May 17, 2021 1:39 pm 
Offline
Member
Member
User avatar

Joined: Thu Oct 13, 2016 4:55 pm
Posts: 1512
I agree, except with this one:
rdos wrote:
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


Top
 Profile  
 
 Post subject: Re: A question about scheduling algorithms
PostPosted: Tue May 18, 2021 2:01 pm 
Offline

Joined: Tue May 18, 2021 1:54 pm
Posts: 1
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group