OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 2:33 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 5 posts ] 
Author Message
 Post subject: Scheduler run queue access on SMP
PostPosted: Mon Dec 14, 2020 3:32 pm 
Offline
Member
Member

Joined: Tue Feb 18, 2020 3:29 pm
Posts: 1071
Hello,
I am redesigning my model of scheduler development in favor of a better system. Currently, I am a bit confused about one thing. Every CPU, IMO, should have lockless access to its run queue. But what if a thread on a different CPU tries to unblock a thread on that CPU? It now must access another CPU's run queue! I have a few solutions that I would like suggestions on:

Make that CPU send an IPI to the CPU it is trying to unblock the thread on. That IPI handler would, with ints disabled, add that thread to the run queue. The only issue is that interrupts have a large overhead.

Bite the bullet and make run queues be access with locks. Seems inefficient and bug prone, however.

Any other ideas?
nexos

_________________
"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: Scheduler run queue access on SMP
PostPosted: Wed Dec 16, 2020 5:16 am 
Offline
Member
Member

Joined: Mon Jul 05, 2010 4:15 pm
Posts: 595
I'm not sure if I understand the issue correctly. Locking isn't that evil, especially in the kernel. Another CPU can push a thread on the queue for another CPU regardless what algorithm you use. You can either use a lockless queue or you can use a locked queue. Locking in the kernel is easy as you just need a spinlock and disable the interrupts for a short time. List operations are short enough not causing too much trouble.

Implementing the same in userspace is more complicated as you don't have the same opportunity to disable interrupts.


Top
 Profile  
 
 Post subject: Re: Scheduler run queue access on SMP
PostPosted: Wed Dec 16, 2020 10:57 am 
Offline
Member
Member

Joined: Thu May 17, 2007 1:27 pm
Posts: 999
In general this is a hard problem and there is no good solution. Your observations are correct: either you need to ask other CPUs to migrate threads via IPIs (high overhead), you can go lockless or you have to accept the possibility that one CPU can stall another for a few 100 ns. Lockless queues are quite possible but everything becomes a lot harder if you're not doing round-robin. For example, for a CFS-style scheduler, you need a heap or balanced tree data structure and doing that in a lockless way is really hard (at least if it should also be fast).

_________________
managarm: Microkernel-based OS capable of running a Wayland desktop (Discord: https://discord.gg/7WB6Ur3). My OS-dev projects: [mlibc: Portable C library for managarm, qword, Linux, Sigma, ...] [LAI: AML interpreter] [xbstrap: Build system for OS distributions].


Top
 Profile  
 
 Post subject: Re: Scheduler run queue access on SMP
PostPosted: Wed Dec 16, 2020 2:22 pm 
Offline
Member
Member

Joined: Wed Oct 01, 2008 1:55 pm
Posts: 3191
nexos wrote:
Hello,
I am redesigning my model of scheduler development in favor of a better system. Currently, I am a bit confused about one thing. Every CPU, IMO, should have lockless access to its run queue. But what if a thread on a different CPU tries to unblock a thread on that CPU? It now must access another CPU's run queue! I have a few solutions that I would like suggestions on:

Make that CPU send an IPI to the CPU it is trying to unblock the thread on. That IPI handler would, with ints disabled, add that thread to the run queue. The only issue is that interrupts have a large overhead.

Bite the bullet and make run queues be access with locks. Seems inefficient and bug prone, however.

Any other ideas?
nexos


I use a temporary queue (rather a 256 entry array) for threads that have become active, either from IRQs or from another core. The implementation is lock-free and so doesn't need a spinlock which makes the scheduler simpler. The core owing the temporary queue will empty it and put the threads in it's local scheduler queue. When a core activates a thread on another core it will send an IPI to the target core after it has added the thread to it's temporary queue.


Top
 Profile  
 
 Post subject: Re: Scheduler run queue access on SMP
PostPosted: Wed Dec 23, 2020 7:20 am 
Offline
Member
Member

Joined: Tue Feb 18, 2020 3:29 pm
Posts: 1071
I think what I'm going to do is use spinlocks on the queue, but assign one CPU queue per proximity domain. This queue will be allocated in its domain's heap area, which will make things more efficient. Every domain will have one CPU nominated to handle scheduling. Note that every CPU queue will have a maximum of 4 CPUs using it to reduce contention. CPUs outside this queue will have to send an IPI to work with this queue. Btw, @Korona, what solution do you use in managarm?

_________________
"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  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 posts ] 

All times are UTC - 6 hours


Who is online

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