New Work on Affine Scheduler

Blog post by Dewey Taylor on Thu, 2011-10-27 01:01

When I first started working on the scheduler I didn't make a big deal about it, but when I did mention it I was quite surprised at the amount of interest there was in what I was doing. So much so that it was suggested that I start blogging about it, so here I am! I would like to take this time to introduce myself as well as the work that I am doing on the scheduler.

Who Am I?
My name is Dewey Taylor, but those on IRC know me as Duggan. I have a BS in CS and I am an original BeOS user starting with R5, so I was somewhat of a late-comer. I followed the Haiku project (then OpenBeOS) since it's inception from a distance but joined the community-proper about 4 or 5 years ago. My major focus has been on third-party native application development, but it's not uncommon for me to delve into the Haiku trunk as well.

What Am I NOT Doing?
There are a couple things I would like to make clear before I go into the details about the scheduler. There is an existing affine scheduler in the trunk which I am only modifying. This scheduler is not even enabled by default, but if you apply a patch which I submit it will be. I'm also not implementing a different scheduling algorithm, but just adding functionality around it.

What I AM Doing!
The first thing I've been working on has been hyperthreading. I've already implemented a cpu map to provide an indirection layer to map a logical cpu id to a ready queue bound to a physical core; that was the easy part. The hard part is using the CPUID instruction and APIC IDs to determine the topology of the processor(s) on the system. This is still quite buggy and likely will be completely reworked soon.

After that comes affinities to bind a thread to a specific core. There are two different types of affinities that can be applied on two different levels. First there are soft affinities which simply means the system would prefer to run a given thread on a particular core, but it's able to move if necessary. Hard affinities mean the thread must operate on that core so long as it's physically possible. As far as levels, the first level is the per-thread level and the second being the team level. Ideally the system would give all threads for the same team a soft affinity on the same core since it is common for threads in a team to share some memory space. This would allow data to remain cached as threads change, increasing execution speed. Another modification on this topic include adding API calls to modify affinities. Soft affinities for threads already exists but without proper load balancing, you wouldn't know it.

So on to load balancing... With the simple smp scheduler Haiku currently uses, threads suffer from what I call "bouncing thread syndrome" which occurs as an idle cpu pulls threads from other cpus, meaning threads are constantly bouncing from one cpu to the next. Proper load balancing will allow teams and threads to stay put when a particular core isn't overloaded, be pulled from an overworked core, or being pushed to a less busy core.

One more thing I would like to implement would be the dynamic shutdown and restart of unneeded cores. For example: if in a dual core system, all threads can run on one core, then move all threads to one core and shut the other down. If the one core becomes overloaded (stays busy over some threshold of time) then that other core should be restarted to alleviate the load on the first core.

What I MIGHT Be Doing...
There are some additional ideas I've been toying with too, but these will come much later (if at all):

At present, the scheduling system uses one global scheduler lock which I think would be better off as one lock per ready queue. My understanding is this idea isn't feasible, but I'd like to look into it anyway.

I may convert the ready queues into trees instead of lists, but this isn't particularly high on my list.

I may convert the topology data into a tree, but again, this isn't very high on my list.

An OO wrapper class would be a nice touch once everything else is done.

Conclusion
Real life has a tendency to get in the way at times, and right now work on the scheduler is slow for just that reason. In a couple days it will speed back up again though and there will be more blog entries as well as patches as work is done. For patches, more information, and to follow progress check out ticket #1069. I spend a reasonable amount of time in the official chatrooms on IRC so feel free to catch me there if you like!

Comments

Re: New Work on Affine Scheduler

Awesome.

Spreading out interrupt handlers on different cores would also be quite interesting btw. It would mean reconfiguring when enabling/disabling CPU's though.

Re: New Work on Affine Scheduler

At this point, the plan is to leave the interrupts alone. Each logical core will still have it's own interrupt.

EDIT: To further explain...
As instructions move through the various layers inside the CPU, "bubbles" tend to form as the various layers either do work or don't do work. Hyperthreading utilizes this by inserting additional commands from a separate thread to fill these bubbles. If one thread finishes execution, bocks. whatever, then those bubbles will still need to be filled as the other thread will continue to execute. Therefore, that logical processor will need to reschedule independently of the other and thus would require it's own interrupt.

Re: New Work on Affine Scheduler

tqh wrote:

Spreading out interrupt handlers on different cores would also be quite interesting btw. It would mean reconfiguring when enabling/disabling CPU's though.

Not really, Haiku's enabling and disabling of CPUs isn't like an OS with hot-plug CPU support. It just sets some flags for the scheduler to politely tell it to avoid using the "switched off" core. The existing scheduler ignores this for processes which have hard affinity to a specific CPU core.

Re: New Work on Affine Scheduler

In addition to telling the scheduler to not use the core, I would also like to halt the unused core entirely if possible. Threads with hard affinities running on cores scheduled to be shut down is a problem however. Since I'm not really working on this specific set of problems right now, their resolution is not particularly high on my to-do list but will be when I get there.

Re: New Work on Affine Scheduler

I'm not sure I understand schedulers that well but if you had a lock per queue I would assume that would mean that it would break IPC between the cores/HThreading since one core could write to ram the other has locked and such.

Re: New Work on Affine Scheduler

That's where the concept of thread safety comes in and the use of mutices.

EDIT: To further explain...
Individual queue locks would only lock the queues being used as the rescheduler works. This would allow other CPUs that are in no way concerned with the work being done by the current CPU to reschedule without problem. However, if a thread/team is being pushed or pulled to/from another CPUs queue, both the current queue and that queue would have to be locked, but that would only temporarily prevent the one other CPU from scheduling as opposed to all other CPUs. Otherwise, thread safety is mostly left up to the application developer which is the importance of ensuring you use mutices properly while working in critical sections.

Sorry about the initially short responses, guys!

Re: New Work on Affine Scheduler

I don't know much about schedulers either. One possible benefit of switching off cores/cpu's is the cores will not overheat as much because they would not be under full load! Another plus is that with inactive cores shut down, the system would use less power!

I can also see a very noticeable increase of performance and efficiency with your Affine Scheduler. Load balancing threads amongst all the cores when under heavy load would cut execution time considerably.

Overall, I think your affine scheduler would be a great addition to Haiku! You have my vote!

Re: New Work on Affine Scheduler

Thank you very much :) However, please remember the affine scheduler itself is not my work. I'm merely adding to the existing affine scheduler which was developed by others. At present, any increase in performance while using the affine scheduler is due to the affine scheduler itself, not my modifications. The patch I submitted is a first attempt at determining the processor topology of the system and while it doesn't work correctly, the system doesn't crash either so it's *usable* but it doesn't do anything special at present either.

Re: New Work on Affine Scheduler

Is it possible to add a software switch/preference app to switch between schedulers?

Or at worse a control statement in the ~/home/config/settings/drivers/kernel file?

Re: New Work on Affine Scheduler

I think it's possible but it really wouldn't be wise. Users really wouldn't have any need to switch from one scheduler to the next. The only benefit I can see is to compare schedulers but it would just be too difficult to set that up for that reason. There is the idea though that as heterogenous systems become more prevalent to have several schedulers running in parallel for different processors. I think doing away with the global scheduler lock (again, if it's possible) is a step in the right direction towards that, but I don't have any intentions of working on heterogenous topologies anytime soon.

Re: New Work on Affine Scheduler

This is really cool work, so hats off to you for taking this under your wing.

I am working on some SMP application stuff that would benefit from your scheduling work and from access to the API.

Eventually I would like to put together an SMP benchmark suite, and it would be cool if the scheduler was optimized for the new AMD Bulldozer CPU, which has special scheduling needs.

Re: New Work on Affine Scheduler

Thanks!

Unfortunately I'm not planning on doing much work on special architectures like the Bulldozer, and to be honest I really haven't looked at the Bulldozer to see what it would require. I'm not saying never, but I am saying that right now my focus is on getting this functionality implemented on the majority of existing architectures. If it turns out later that I have some free time to spend on it, demand is high enough, and I feel confident that I could do it, I very well may work on implementing support for some special architectures.

Best of luck on your project! Stay tuned for when the affinity stuff gets implemented...