OSDev.org

The Place to Start for Operating System Developers
It is currently Wed Aug 17, 2022 11:24 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 10 posts ] 
Author Message
 Post subject: Is there any good scheduling algorithms for micro kernel
PostPosted: Wed Jun 29, 2022 7:02 am 
Offline

Joined: Wed Jun 29, 2022 2:17 am
Posts: 20
I think I'm caught in a paradox

I want to execute processes called by other processes as more as possible
But on the other hand, I need to prevent other processes from starvation

Is there any good scheduling algorithms can meet my requirements?

_________________
I'm a new man to develop operating system.


Top
 Profile  
 
 Post subject: Re: Is there any good scheduling algorithms for micro kernel
PostPosted: Wed Jun 29, 2022 12:28 pm 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 1307
Round robin is a nice and simple choice for starters. You keep all currently runnable processes in a list. New processes are added at the end of the list, processes that get scheduled in are removed from the front. If a process is scheduled out that is still runnable, it is also added to the back of the list.

That means, any process that becomes runnable will be scheduled once all the processes in front of it in the queue have had their turn. No process can starve.

The algorithm in this form does not admit any priorities, but that is for a later day to solve. Algorithm also does not allow for a preference for any CPU or NUMA node. You may need something more complicated when the time comes and you truly care. But this algorithm should get you started at least.

The choice of scheduling algorithm has little to do with IPC, BTW, since the calling process will be suspended waiting for the answer, and the called process will become runnable if it isn't already. As long as you do not make tasks wait for the end of their time slice to be scheduled out, all is well.

_________________
Carpe diem!


Top
 Profile  
 
 Post subject: Re: Is there any good scheduling algorithms for micro kernel
PostPosted: Wed Jun 29, 2022 12:44 pm 
Offline
Member
Member
User avatar

Joined: Fri Jun 11, 2021 6:02 am
Posts: 48
Location: Belgium
I'm also working on a microkernel and currently I use a very simple round-robin queue with weak references to all threads. Threads that don't have to wake up yet are simply skipped over and any dead threads are removed lazily. This is obviously not efficient but it works well enough for now.

I don't have any concrete plans for a new scheduler yet, but I'll likely split it in two parts: a linked chain for runnable threads only and a priority queue with the "sleep until" time as key.

theflysong wrote:
I want to execute processes called by other processes as more as possible
But on the other hand, I need to prevent other processes from starvation


You may want to look into time slice donation: every thread has a limited amount of time to run, but can choose to immediately start running another thread with the remainder of its time slice. This way you can achieve low latency (which I assume is what you're after) yet it won't affect any other threads since they get to keep their time slice.

_________________
My OS is Norost B (website, Github, sourcehut)


Top
 Profile  
 
 Post subject: Re: Is there any good scheduling algorithms for micro kernel
PostPosted: Thu Jun 30, 2022 5:21 am 
Offline

Joined: Wed Jun 29, 2022 2:17 am
Posts: 20
Demindiro wrote:
I'm also working on a microkernel and currently I use a very simple round-robin queue with weak references to all threads. Threads that don't have to wake up yet are simply skipped over and any dead threads are removed lazily. This is obviously not efficient but it works well enough for now.

I don't have any concrete plans for a new scheduler yet, but I'll likely split it in two parts: a linked chain for runnable threads only and a priority queue with the "sleep until" time as key.

theflysong wrote:
I want to execute processes called by other processes as more as possible
But on the other hand, I need to prevent other processes from starvation


You may want to look into time slice donation: every thread has a limited amount of time to run, but can choose to immediately start running another thread with the remainder of its time slice. This way you can achieve low latency (which I assume is what you're after) yet it won't affect any other threads since they get to keep their time slice.


The evil process could create hundreds of process and let them donate all the slice to it.so that it can take up lots of time

_________________
I'm a new man to develop operating system.


Top
 Profile  
 
 Post subject: Re: Is there any good scheduling algorithms for micro kernel
PostPosted: Thu Jun 30, 2022 5:22 am 
Offline

Joined: Wed Jun 29, 2022 2:17 am
Posts: 20
nullplan wrote:
Round robin is a nice and simple choice for starters. You keep all currently runnable processes in a list. New processes are added at the end of the list, processes that get scheduled in are removed from the front. If a process is scheduled out that is still runnable, it is also added to the back of the list.

That means, any process that becomes runnable will be scheduled once all the processes in front of it in the queue have had their turn. No process can starve.

The algorithm in this form does not admit any priorities, but that is for a later day to solve. Algorithm also does not allow for a preference for any CPU or NUMA node. You may need something more complicated when the time comes and you truly care. But this algorithm should get you started at least.

The choice of scheduling algorithm has little to do with IPC, BTW, since the calling process will be suspended waiting for the answer, and the called process will become runnable if it isn't already. As long as you do not make tasks wait for the end of their time slice to be scheduled out, all is well.


Thanks.I have tried the round robin before.So I want to try something else.

_________________
I'm a new man to develop operating system.


Top
 Profile  
 
 Post subject: Re: Is there any good scheduling algorithms for micro kernel
PostPosted: Thu Jun 30, 2022 6:03 am 
Offline
Member
Member
User avatar

Joined: Fri Jun 11, 2021 6:02 am
Posts: 48
Location: Belgium
theflysong wrote:
The evil process could create hundreds of process and let them donate all the slice to it.so that it can take up lots of time


If the process can abuse that it can just as easily just spawn a bunch of threads doing nothing but waste cycles.

If you're worried about fairly distributing execution time you will need process groups (or something similar) and adjustable priorities for each group.

Also, know that it's easy to grind a system to a halt by spawning a couple dozen threads (depending on CPU) and having them do an unaligned `lock cmpxchg` on a page boundary in a loop. (For extra fun, play some music on that same machine).

_________________
My OS is Norost B (website, Github, sourcehut)


Top
 Profile  
 
 Post subject: Re: Is there any good scheduling algorithms for micro kernel
PostPosted: Thu Jun 30, 2022 2:38 pm 
Offline
Member
Member
User avatar

Joined: Mon May 22, 2017 5:56 am
Posts: 637
Location: Oscillating between two different potentials
I'm learning about some fun and exciting new kinds of forkbomb in this thread, but not so much about schedulers! :lol: But seriously, I think an evil process getting more than its fair share of time is a security and administration issue - be careful what you install.

I had some ideas about this way back in the past when I knew basically nothing. They involved iterating over the whole process list on every task switch, checking how much time a process has had recently. I guess that's not very efficient? IDK but it seems to be done more simply in real OSs.

_________________
Crunchy Kaph — An experimental Forth environment for certain PPC Macs.
"May wisdom, fun, and the greater good shine forth in all your work." — Leo Brodie


Top
 Profile  
 
 Post subject: Re: Is there any good scheduling algorithms for micro kernel
PostPosted: Fri Jul 01, 2022 6:11 am 
Offline
Member
Member

Joined: Tue Feb 18, 2020 3:29 pm
Posts: 954
This is where prioritized schedulers and dynamic priority computation become important. Of course, this won't stop a fork bomb, but it should stop a greedy process that creates 50 threads to monopolize the CPU. Note that I guess these threads could manipulate the heuristics involved with the computation, but that would be quite tricky to do.

_________________
"How did you do this?"
"It's very simple — you read the protocol and write the code." - Bill Joy
Projects: NexNix | libnex | nnpkg


Top
 Profile  
 
 Post subject: Re: Is there any good scheduling algorithms for micro kernel
PostPosted: Fri Jul 01, 2022 5:02 pm 
Offline
Member
Member
User avatar

Joined: Sun Feb 18, 2007 7:28 pm
Posts: 1557
Hi,

Although it is subject to change, we currently use 4 levels of queues where level 0 is FCFS (First Come First Serve), level 1 is PRI (Priority), level 2 is RR (Round Robin) and Level 3 is planned to be SJF (Shortest Job First). The Schedule function just goes through these 4 levels of priority. A thread can be moved from a queue by lowing or raising its priority which in turns changes how it gets scheduled.

_________________
OS Development Series | Wiki | os | ncc
char c[2]={"\x90\xC3"};int main(){void(*f)()=(void(__cdecl*)(void))(void*)&c;f();}


Top
 Profile  
 
 Post subject: Re: Is there any good scheduling algorithms for micro kernel
PostPosted: Fri Jul 01, 2022 11:11 pm 
Offline

Joined: Wed Jun 29, 2022 2:17 am
Posts: 20
neon wrote:
Hi,

Although it is subject to change, we currently use 4 levels of queues where level 0 is FCFS (First Come First Serve), level 1 is PRI (Priority), level 2 is RR (Round Robin) and Level 3 is planned to be SJF (Shortest Job First). The Schedule function just goes through these 4 levels of priority. A thread can be moved from a queue by lowing or raising its priority which in turns changes how it gets scheduled.


I think it would be a good scheduling algorithms for me.I will try it.Thanks.

_________________
I'm a new man to develop operating system.


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

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 2 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